# Average case analysis of Lasso under ultra-sparse conditions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 40 references that are in the map.
- First posted on arXiv 25 Feb 2023.

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

- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [A framework to characterize performance of LASSO algorithms](https://mlsanity.com/paper/1303.7291/) (2013)
- [False Discoveries Occur Early on the Lasso Path](https://mlsanity.com/paper/1511.01957/) (2015)
- [Finite Sample Analysis of Approximate Message Passing Algorithms](https://mlsanity.com/paper/1606.01800/) (2016)
- [Ising Model Selection Using ℓ1-Regularized Linear Regression: A Statistical Mechanics Analysis](https://mlsanity.com/paper/2102.03988/) (2021)
- [Learning performance in inverse Ising problems with sparse teacher couplings](https://mlsanity.com/paper/1912.11591/) (2019)
- [Structure Learning in Inverse Ising Problems Using ℓ2-Regularized Linear Estimator](https://mlsanity.com/paper/2008.08342/) (2020)

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

- [A High Dimensional Statistical Model for Adversarial Training: Geometry and Trade-Offs](https://mlsanity.com/paper/2402.05674/) (2024)
- [On the Geometry of Regularization in Adversarial Training: High-Dimensional Asymptotics and Generalization Bounds](https://mlsanity.com/paper/2410.16073/) (2024)
- [On the Existence of Consistent Adversarial Attacks in High-Dimensional Linear Classification](https://mlsanity.com/paper/2506.12454/) (2025)
- [Non-negative Elastic Net Decoding for Information Retrieval](https://mlsanity.com/paper/2606.17910/) (2026)
- [Transfer Learning in ℓ1 Regularized Regression: Hyperparameter Selection Strategy based on Sharp Asymptotic Analysis](https://mlsanity.com/paper/2409.17704/) (2024)

## Abstract (arXiv)

We analyze the performance of the least absolute shrinkage and selection operator (Lasso) for the linear model when the number of regressors N grows larger keeping the true support size d finite, i.e., the ultra-sparse case. The result is based on a novel treatment of the non-rigorous replica method in statistical physics, which has been applied only to problem settings where N ,d and the number of observations M tend to infinity at the same rate. Our analysis makes it possible to assess the average performance of Lasso with Gaussian sensing matrices without assumptions on the scaling of N and M, the noise distribution, and the profile of the true signal. Under mild conditions on the noise distribution, the analysis also offers a lower bound on the sample complexity necessary for partial and perfect support recovery when M diverges as M = O(log N). The obtained bound for perfect support recovery is a generalization of that given in previous literature, which only considers the case of Gaussian noise and diverging d. Extensive numerical experiments strongly support our analysis.