Detecting Low-Degree Truncation

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution cal D over ℝn and a collection of data points in ℝn, distinguish between the two possibilities that (i) the data was drawn from cal D, versus (ii) the data was drawn from cal D|S, i.e. from cal D subject to truncation by an unknown truncation set S subseteq ℝn. We study this problem in the setting where cal 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 ℝn). Our main results are an efficient algorithm when cal D is a hypercontractive distribution, and a matching lower bound: bullet For any constant d, we give a polynomial-time algorithm which successfully distinguishes cal D from cal D|S using O(nd/2) samples (subject to mild technical conditions on cal D and S); bullet Even for the simplest case of cal D being the uniform distribution over +1, -1n, we show that for any constant d, any distinguishing algorithm for degree-d polynomial threshold functions must use Omega(nd/2) samples.