Testing Noisy Low-Degree Polynomials for Sparsity

We consider the problem of testing whether an unknown low-degree polynomial p over R n is sparse versus far from sparse, given access to noisy evaluations of the polynomial p at randomly chosen points. This is a natural property-testing version of various well-studied problems about learning low-degree sparse polynomials in the presence of noise, and is a generalization of the work of Chen, De, and Servedio [CDS20], on testing noisy linear functions for sparsity, to the more challenging setting of low-degree polynomials.

Our main result gives a precise characterization of when sparsity testing for low-degree polynomials can be carried out with constant sample complexity independent of dimension, along with a constant-sample algorithm for this problem in the parameter regime where this is possible. In more detail, for any mean-zero variance-one finitely supported distribution X over the reals, any degree parameter d, and any sparsity parameters s and T ≥ s, we define a computable function Max-Sparsity-Gap X,d (•), and:

• For T ≥ Max-Sparsity-Gap X,d (s) we give an O s,X,d (1)-sample algorithm for the problem of distinguishing whether a multilinear degree-d polynomial over R n is s-sparse versus ε-far from T -sparse, given independent labeled examples (x, p(x) + noise) x∼X ⊗n . (Crucially, this sample complexity is completely independent of the ambient dimension n.) On the other hand,

• For T ≤ Max-Sparsity-Gap X,d (s) -1, we show that even in the absence of noise, any algorithm for distinguishing whether a multilinear degree-d polynomial is s-sparse versus ε-far from T -sparse, given independent labeled examples (x, p(x)) x∼X ⊗n , must use Ω X,d,s (log n) examples.

Our techniques employ a generalization of the results of Dinur, Friedgut, Kindler, and O'Donnell [DFKO07] on the Fourier tails of bounded functions over ±1 n to a broad range of finitely supported distributions, which may be of independent interest.