# On the design-dependent suboptimality of the Lasso

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 29 references that are in the map.
- First posted on arXiv 1 Feb 2024.

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

- [Marginal Singularity, and the Benefits of Labels in Covariate-Shift](https://mlsanity.com/paper/1803.01833/) (2018)
- [Optimally tackling covariate shift in RKHS-based nonparametric regression](https://mlsanity.com/paper/2205.02986/) (2022)
- [Near-Optimal Linear Regression under Distribution Shift](https://mlsanity.com/paper/2106.12108/) (2021)
- [A new similarity measure for covariate shift with applications to nonparametric regression](https://mlsanity.com/paper/2202.02837/) (2022)
- [Pseudo-Labeling for Kernel Ridge Regression under Covariate Shift](https://mlsanity.com/paper/2302.10160/) (2023)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [Maximum Likelihood Estimation is All You Need for Well-Specified Covariate Shift](https://mlsanity.com/paper/2311.15961/) (2023)
- [On the Prediction Performance of the Lasso](https://mlsanity.com/paper/1402.1700/) (2014)
- [Tight Lower Bound on the Probability of a Binomial Exceeding its Expectation](https://mlsanity.com/paper/1306.1433/) (2013)
- [Out of the Ordinary: Spectrally Adapting Regression for Covariate Shift](https://mlsanity.com/paper/2312.17463/) (2023)

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

- [Distributionally robust risk evaluation with an isotonic constraint](https://mlsanity.com/paper/2407.06867/) (2024)
- [SODAs: Sparse Optimization for the Discovery of Differential and Algebraic Equations](https://mlsanity.com/paper/2503.05993/) (2025)
- [Mallows-type model averaging: Non-asymptotic analysis and all-subset combination](https://mlsanity.com/paper/2505.02637/) (2025)

## Abstract (arXiv)

This paper investigates the effect of the design matrix on the ability (or inability) to estimate a sparse parameter in linear regression. More specifically, we characterize the optimal rate of estimation when the smallest singular value of the design matrix is bounded away from zero. In addition to this information-theoretic result, we provide and analyze a procedure which is simultaneously statistically optimal and computationally efficient, based on soft thresholding the ordinary least squares estimator. Most surprisingly, we show that the Lasso estimator -- despite its widespread adoption for sparse linear regression -- is provably minimax rate-suboptimal when the minimum singular value is small. We present a family of design matrices and sparse parameters for which we can guarantee that the Lasso with any choice of regularization parameter -- including those which are data-dependent and randomized -- would fail in the sense that its estimation rate is suboptimal by polynomial factors in the sample size. Our lower bound is strong enough to preclude the statistical optimality of all forms of the Lasso, including its highly popular penalized, norm-constrained, and cross-validated variants.