# On the Power of Preconditioning in Sparse Linear Regression

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 91 references that are in the map.
- First posted on arXiv 17 Jun 2021.

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

- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path](https://mlsanity.com/paper/2011.05365/) (2020)
- [Learning Some Popular Gaussian Graphical Models without Condition Number Bounds](https://mlsanity.com/paper/1905.01282/) (2019)
- [Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds](https://mlsanity.com/paper/1805.02677/) (2018)
- [On the Prediction Performance of the Lasso](https://mlsanity.com/paper/1402.1700/) (2014)
- [Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators](https://mlsanity.com/paper/1503.03188/) (2015)
- [Structured Sparse Regression via Greedy Hard-Thresholding](https://mlsanity.com/paper/1602.06042/) (2016)
- [Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm](https://mlsanity.com/paper/1711.04952/) (2017)
- [Polynomial Bounds for the Grid-Minor Theorem](https://mlsanity.com/paper/1305.6577/) (2013)

## Built on by (most cited first, 15 of 15)

- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles](https://mlsanity.com/paper/2309.09457/) (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)
- [On the design-dependent suboptimality of the Lasso](https://mlsanity.com/paper/2402.00382/) (2024)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [Sparse Linear Regression and Lattice Problems](https://mlsanity.com/paper/2402.14645/) (2024)
- [Unfolding-Aided Bootstrapped Phase Retrieval in Optical Imaging](https://mlsanity.com/paper/2203.01695/) (2022)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Lasso and Partially-Rotated Designs](https://mlsanity.com/paper/2505.11093/) (2025)
- [Sparse Linear Regression is Easy on Random Supports](https://mlsanity.com/paper/2511.06211/) (2025)

## Abstract (arXiv)

Sparse linear regression is a fundamental problem in high-dimensional statistics, but strikingly little is known about how to efficiently solve it without restrictive conditions on the design matrix. We consider the (correlated) random design setting, where the covariates are independently drawn from a multivariate Gaussian N(0,Sigma) with Sigma : n × n, and seek estimators hatw minimizing (hatw-w^*)TSigma(hatw-w^*), where w^* is the k-sparse ground truth. Information theoretically, one can achieve strong error bounds with O(k log n) samples for arbitrary Sigma and w^*; however, no efficient algorithms are known to match these guarantees even with o(n) samples, without further assumptions on Sigma or w^*. As far as hardness, computational lower bounds are only known with worst-case design matrices. Random-design instances are known which are hard for the Lasso, but these instances can generally be solved by Lasso after a simple change-of-basis (i.e. preconditioning). In this work, we give upper and lower bounds clarifying the power of preconditioning in sparse linear regression. First, we show that the preconditioned Lasso can solve a large class of sparse linear regression problems nearly optimally: it succeeds whenever the dependency structure of the covariates, in the sense of the Markov property, has low treewidth -- even if Sigma is highly ill-conditioned. Second, we construct (for the first time) random-design instances which are provably hard for an optimally preconditioned Lasso. In fact, we complete our treewidth classification by proving that for any treewidth-t graph, there exists a Gaussian Markov Random Field on this graph such that the preconditioned Lasso, with any choice of preconditioner, requires Omega(t1/20) samples to recover O(log n)-sparse signals when covariates are drawn from this model.