3
[2402.08133] Detecting Low-Degree Truncation
source link: https://arxiv.org/abs/2402.08133
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Computational Complexity
[Submitted on 12 Feb 2024]
Detecting Low-Degree Truncation
We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution D over Rn and a collection of data points in Rn, distinguish between the two possibilities that (i) the data was drawn from D, versus (ii) the data was drawn from D|S, i.e. from D subject to truncation by an unknown truncation set S⊆Rn.
We study this problem in the setting where D is a high-dimensional i.i.d. product distribution and S is an unknown degree-d polynomial threshold function (one of the most well-studied types of Boolean-valued function over Rn). Our main results are an efficient algorithm when D is a hypercontractive distribution, and a matching lower bound:
∙ For any constant d, we give a polynomial-time algorithm which successfully distinguishes D from D|S using O(nd/2) samples (subject to mild technical conditions on D and S);
∙ Even for the simplest case of D being the uniform distribution over {+1,−1}n, we show that for any constant d, any distinguishing algorithm for degree-d polynomial threshold functions must use Ω(nd/2) samples.
| Comments: | 36 pages |
| Subjects: | Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2402.08133 [cs.CC] |
| (or arXiv:2402.08133v1 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2402.08133 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK