Sparse Linear Regression Is Easy on Random Supports

Sparse linear regression is one of the most basic questions in machine learning and statistics. Here, we are given as input a design matrix X ∈ R N ×d and measurements or labels y ∈ R N where y = Xw * + ξ, and ξ is the noise in the measurements. Importantly, we have the additional constraint that the unknown signal vector w * is sparse: it has k non-zero entries where k is much smaller than the ambient dimension. Our goal is to output a prediction vector w that has small prediction error: 1 N • ∥Xw * -X w∥ 2 2 . Information-theoretically, we know what is best possible in terms of measurements: under most natural noise distributions, we can get prediction error at most ϵ with roughly N = O(k log d/ϵ) samples. Computationally, this currently needs d Ω(k) run-time. Alternately, with N = O(d), we can get polynomialtime. Thus, there is an exponential gap (in the dependence on d) between the two and we do not know if it is possible to get d o(k) run-time and o(d) samples.

We give the first generic positive result for worst-case design matrices X: For any X, we show that if the support of w * is chosen at random, we can get prediction error ϵ with N = poly(k, log d, 1/ϵ) samples and run-time poly(d, N ). This run-time holds for any design matrix X with condition number up to 2 poly(d) .

Previously, such results were known for worst-case w * , but only for random design matrices from well-behaved families, matrices that have a very low condition number (poly(log d); e.g., as studied in compressed sensing), or those with special structural properties.