Detecting Low-Degree Truncation

Abstract

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution $\mathcal{D}$ over ${\mathbb{R}}^n$ and a collection of data points in ${\mathbb{R}}^n$, distinguish between the two possibilities that (i) the data was drawn from $\mathcal{D}$, versus (ii) the data was drawn from $\mathcal{D}{|}_S$, i.e. from $\mathcal{D}$ subject to truncation by an unknown truncation set $S\subseteq {\mathbb{R}}^n$. We study this problem in the setting where $\mathcal{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 ${\mathbb{R}}^n$). Our main results are an efficient algorithm when $\mathcal{D}$ is a hypercontractive distribution, and a matching lower bound: $\bullet$ For any constant $d$, we give a polynomial-time algorithm which successfully distinguishes $\mathcal{D}$ from $\mathcal{D}{|}_S$ using $O(n^{d/2})$ samples (subject to mild technical conditions on $\mathcal{D}$ and $S$); $\bullet$ Even for the simplest case of $\mathcal{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 $\hat{I}\text{c◯}(n^{d/2})$ samples.

36 pages; small correction to Theorem 3