Sparse Linear Regression is Easy on Random Supports

2025/11/09 by Chandrasekaran, Gautam, Meka, Raghu, Stavropoulos, Konstantinos
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2511.06211

Abstract

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 \widehatw that has small prediction error: (1)/(N)⋅ ‖X w^* - X \widehatw‖²₂. 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 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 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.

Citations

• Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
• Sparse Linear Regression and Lattice Problems
• Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
• Feature Adaptation for Sparse Linear Regression
• Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression
• On the Power of Preconditioning in Sparse Linear Regression
• The Fine-Grained Hardness of Sparse Linear Regression
• Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators
• Variable Selection is Hard
• Lower bounds on the performance of polynomial-time algorithms for sparse\n linear regression
• Fast-rate and optimistic-rate error bounds for L1-regularized regression
• Minimax rates of estimation for high-dimensional linear regression over ℓ_q-balls
• The Dantzig selector: Statistical estimation when p is much larger than n
• Decoding by Linear Programming
• Sparse Approximate Solutions to Linear Systems

Related

• Sparse Linear Regression and Lattice Problems
• The Fine-Grained Hardness of Sparse Linear Regression
• Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
• On the Power of Preconditioning in Sparse Linear Regression
• Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators