Testing noisy low-degree polynomials for sparsity

Abstract

We consider the problem of testing whether an unknown low-degree polynomial $p$ over ${\mathbb{R}}^n$ is sparse versus far from sparse, given access to noisy evaluations of the polynomial $p$ at \emph{randomly chosen points}. This is a property-testing analogue of classical problems on learning sparse low-degree polynomials with noise, extending the work of Chen, De, and Servedio (2020) from noisy \emph{linear} functions to general low-degree polynomials. Our main result gives a \emph{precise characterization} of when sparsity testing for low-degree polynomials admits constant sample complexity independent of dimension, together with a matching constant-sample algorithm in that regime. For any mean-zero, variance-one finitely supported distribution $\mathbf{X}$ over the reals, degree $d$, and any sparsity parameters $s\le T$, we define a computable function ${\mathrm{MSG}}_{\mathbf{X},d}(\cdot )$, and: - For $T\ge {\mathrm{MSG}}_{\mathbf{X},d}(s)$, we give an $O_{s,\mathbf{X},d}(1)$-sample algorithm that distinguishes whether a multilinear degree-$d$ polynomial over ${\mathbb{R}}^n$ is $s$-sparse versus $\epsilon$-far from $T$-sparse, given examples $(\mathbf{x},p(\mathbf{x})+\mathrm{noise}{)}_{\mathbf{x}\sim {\mathbf{X}}^{\otimes n}}$. Crucially, the sample complexity is \emph{completely independent} of the ambient dimension $n$. - For $T\le {\mathrm{MSG}}_{\mathbf{X},d}(s)-1$, we show that even without noise, any algorithm given samples $(\mathbf{x},p(\mathbf{x}){)}_{\mathbf{x}\sim {\mathbf{X}}^{\otimes n}}$ must use $\hat{I}{\text{c◯}}_{\mathbf{X},d,s}(\log n)$ examples. Our techniques employ a generalization of the results of Dinur et al. (2007) on the Fourier tails of bounded functions over $\{0,1{\}}^n$ to a broad range of finitely supported distributions, which may be of independent interest.

63 pages