# Sparse Linear Regression is Easy on Random Supports

arXiv: https://arxiv.org/abs/2511.06211 · HTML: https://mlsanity.com/paper/2511.06211/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 40 references that are in the map.
- First posted on arXiv 9 Nov 2025.

## Builds on (most cited first, 10 of 10)

- [Learning Some Popular Gaussian Graphical Models without Condition Number Bounds](https://mlsanity.com/paper/1905.01282/) (2019)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [On the Prediction Performance of the Lasso](https://mlsanity.com/paper/1402.1700/) (2014)
- [The Fine-Grained Hardness of Sparse Linear Regression](https://mlsanity.com/paper/2106.03131/) (2021)
- [Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators](https://mlsanity.com/paper/1503.03188/) (2015)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression](https://mlsanity.com/paper/2402.14103/) (2024)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [Sparse Linear Regression and Lattice Problems](https://mlsanity.com/paper/2402.14645/) (2024)

## Abstract (arXiv)

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^* + xi, and xi 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: frac1N· |X w^* - X widehatw|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 log d/ε) samples. Computationally, this currently needs dOmega(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, log d, 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(log d); e.g., as studied in compressed sensing), or those with special structural properties.