# A framework to characterize performance of LASSO algorithms

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2013.

## Built on by (most cited first, 30 of 40)

- [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions](https://mlsanity.com/paper/2106.03791/) (2021)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Don't Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification](https://mlsanity.com/paper/2102.07856/) (2021)
- [Phase Transitions in Transfer Learning for High-Dimensional Perceptrons](https://mlsanity.com/paper/2101.01918/) (2021)
- [On the Inherent Regularization Effects of Noise Injection During Training](https://mlsanity.com/paper/2102.07379/) (2021)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [On double-descent in uncertainty quantification in overparametrized models](https://mlsanity.com/paper/2210.12760/) (2022)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Understanding the Under-Coverage Bias in Uncertainty Estimation](https://mlsanity.com/paper/2106.05515/) (2021)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [Mitigating multiple descents: A model-agnostic framework for risk monotonization](https://mlsanity.com/paper/2205.12937/) (2022)
- [Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy](https://mlsanity.com/paper/2208.09550/) (2022)
- [Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning](https://mlsanity.com/paper/2107.05143/) (2021)
- [Minimum ℓ1-norm interpolators: Precise asymptotics and multiple descent](https://mlsanity.com/paper/2110.09502/) (2021)
- [Regularized Linear Regression for Binary Classification](https://mlsanity.com/paper/2311.02270/) (2023)
- [Asymptotic normality of robust M-estimators with convex penalty](https://mlsanity.com/paper/2107.03826/) (2021)
- [Beyond Independent Measurements: General Compressed Sensing with GNN Application](https://mlsanity.com/paper/2111.00327/) (2021)
- [Observable adjustments in single-index models for regularized M-estimators](https://mlsanity.com/paper/2204.06990/) (2022)
- [A New Central Limit Theorem for the Augmented IPW Estimator: Variance Inflation, Cross-Fit Covariance and Beyond](https://mlsanity.com/paper/2205.10198/) (2022)
- [Average case analysis of Lasso under ultra-sparse conditions](https://mlsanity.com/paper/2302.13093/) (2023)
- [High-dimensional logistic regression with missing data: Imputation, regularization, and universality](https://mlsanity.com/paper/2410.01093/) (2024)
- [On how to avoid exacerbating spurious correlations when models are overparameterized](https://mlsanity.com/paper/2206.12739/) (2022)
- [A Novel Gaussian Min-Max Theorem and its Applications](https://mlsanity.com/paper/2402.07356/) (2024)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [High-Dimensional Statistics: Reflections on Progress and Open Problems](https://mlsanity.com/paper/2605.05076/) (2026)
- [Quantum Algorithms for the Pathwise Lasso](https://mlsanity.com/paper/2312.14141/) (2023)
- [Few-shot Multi-Task Learning of Linear Invariant Features with Meta Subspace Pursuit](https://mlsanity.com/paper/2409.02708/) (2024)
- [One-Bit Quantization and Sparsification for Multiclass Linear Classification with Strong Regularization](https://mlsanity.com/paper/2402.10474/) (2024)

## Abstract (arXiv)

In this paper we consider solving noisy under-determined systems of linear equations with sparse solutions. A noiseless equivalent attracted enormous attention in recent years, above all, due to work of citeCRT,CanRomTao06,DonohoPol where it was shown in a statistical and large dimensional context that a sparse unknown vector (of sparsity proportional to the length of the vector) can be recovered from an under-determined system via a simple polynomial ℓ1-optimization algorithm. citeCanRomTao06 further established that even when the equations are noisy, one can, through an SOCP noisy equivalent of ℓ1, obtain an approximate solution that is (in an ℓ2-norm sense) no further than a constant times the noise from the sparse unknown vector. In our recent works citeStojnicCSetam09,StojnicUpper10, we created a powerful mechanism that helped us characterize exactly the performance of ℓ1 optimization in the noiseless case (as shown in citeStojnicEquiv10 and as it must be if the axioms of mathematics are well set, the results of citeStojnicCSetam09,StojnicUpper10 are in an absolute agreement with the corresponding exact ones from citeDonohoPol). In this paper we design a mechanism, as powerful as those from citeStojnicCSetam09,StojnicUpper10, that can handle the analysis of a LASSO type of algorithm (and many others) that can be (or typically are) used for "solving" noisy under-determined systems. Using the mechanism we then, in a statistical context, compute the exact worst-case ℓ2 norm distance between the unknown sparse vector and the approximate one obtained through such a LASSO. The obtained results match the corresponding exact ones obtained in citeBayMon10,DonMalMon10. Moreover, as a by-product of our analysis framework we recognize existence of an SOCP type of algorithm that achieves the same performance.