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 ∈ ℝN × d and measurements or labels y ∈ ℝN where y = X w* + ξ, 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· ||X w* − X w||22. 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 logd/є) samples. Computationally, this currently needs dΩ(k) run-time. Alternately, with N = O(d), we can get polynomial-time. 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 do(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, logd, 1/є) samples and run-time poly(d,N). This run-time holds for any design matrix X with condition number up to 2poly(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(logd); e.g., as studied in compressed sensing), or those with special structural properties.