Distribution Free Fourier Sparsity Testing

Learning functions $ f : \mathbb{F}_2^n \to \mathbb{R} $ with sparse Fourier representations plays a central role in computational learning theory, as such functions capture many natural concept classes in machine learning. In recent years, Fourier sparsity has also been studied from the related perspective of property testing, where the goal is to determine, given query access to a function, whether it is $ s $-Fourier-sparse or far from every such function under an appropriate distance measure. Such testers can serve as a preprocessing step for model selection in agnostic learning of Fourier-sparse functions, where validating the structural assumption is crucial before applying computationally expensive learning algorithms. However, all prior work on testing Fourier sparsity considers distance with respect to the uniform distribution over the hypercube. In this work, we initiate the study of Fourier sparsity testing in the distribution-free setting, the property-testing analogue of the PAC+MQ learning framework. In this model, the tester is given oracle access to an unknown function and sample access to an arbitrary and unknown input distribution, and must distinguish $ s $-Fourier-sparse functions from those that are $ \delta $-far from every such function with respect to the underlying distribution. We design a nonadaptive randomized tester that succeeds with high probability using $ \widetilde{O}((s/\delta)^4) $ oracle queries and $ \widetilde{O}(1/\delta) $ samples from the unknown distribution.