Detecting Low-Degree Truncation

We consider the following basic, and very broad, statistical problem: Given a known highdimensional distribution D over R n and a collection of data points in R n , 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 ⊆ R n .

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 R n ). 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(n d/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 Ω(n d/2 ) samples.