Testing noisy linear functions for sparsity

Xue Chen, Anindya De, Rocco A. Servedio

We consider the following basic inference problem: there is an unknown high-dimensional vector $w\in {\mathbb{R}}^n$, and an algorithm is given access to labeled pairs $(x,y)$ where…