The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning

Marco Leo, Andrea MontanariThe Annals of Statistics 2021 · DOI · arXiv

Abstract

The Lasso is a popular regression method for high-dimensional problems in which the number of parameters $\theta_1,\dots,\theta_N$, is larger than the number $n$ of samples: $N>n$. A useful heuristics relates the statistical properties of the Lasso estimator to that of a simple soft-thresholding denoiser, in a denoising problem in which the parameters $(\theta_i)_{i\le N}$ are observed in Gaussian noise, with a carefully tuned variance. Earlier work confirmed this picture in the limit $n,N\to\infty$, pointwise in the parameters $\theta$ and in the value of the regularization parameter. Here, we consider a standard random design model and prove exponential concentration of its empirical distribution around the prediction provided by the Gaussian denoising model. Crucially, our results are uniform with respect to $\theta$ belonging to $\ell_q$ balls, $q\in[0,1]$, and with respect to the regularization parameter. This allows us to derive sharp results for the performances of various data-driven procedures to tune the regularization. Our proofs make use of Gaussian comparison inequalities, and in particular of a version of Gordon’s minimax theorem developed by Thrampoulidis, Oymak and Hassibi, which controls the optimum value of the Lasso optimization problem. Crucially, we prove a stability property of the minimizer in Wasserstein distance that allows one to characterize properties of the minimizer itself.

Bridging Theory and Practice in High-Dimensional Regression

In high-dimensional regression, the challenge is to recover a signal $\theta$ from fewer samples than parameters ($N > n$). The Lasso has become the standard tool for this task, utilizing $\ell_1$ regularization to promote sparsity. However, the practical success of the Lasso depends entirely on the selection of the regularization parameter $\lambda$.

For years, researchers have relied on a "denoising heuristic": the idea that the Lasso estimator behaves as if we were simply observing the true parameters in Gaussian noise and applying a soft-thresholding filter. While earlier work proved this for a fixed signal $\theta$ and a fixed $\lambda$ (pointwise convergence), it failed to explain what happens when we use the data itself to pick $\lambda$—which is the standard approach in practice. This paper addresses the need for uniform convergence, ensuring the heuristic holds across entire ranges of $\lambda$ and signal types.

Technical Foundations: Stability and Uniformity

The authors employ a sophisticated toolkit from high-dimensional probability to establish these foundations:

  • Gaussian Comparison Inequalities: By using a refined version of Gordon’s minimax theorem, the authors relate the complex Lasso optimization problem to a much simpler "scalar" optimization problem.
  • Local Stability: A key technical innovation. The authors prove that the Lasso cost function is "stable"—meaning if an estimator is far from the predicted theoretical distribution, the cost function value must be significantly higher than the minimum. This allows them to characterize the minimizer itself, not just the minimum value.
  • Wasserstein Distance: They use the $W_2$ metric to quantify how closely the empirical distribution of the Lasso coefficients matches the predicted Gaussian denoising model.
  • Uniformity Proofs: By using $\epsilon$-nets and Lipschitz continuity arguments, they extend pointwise results to hold uniformly over $\ell_q$ balls (for $q \in [0,1]$) and regularization intervals.

Empirical Validation of Adaptive Tuning

The paper solidifies the "Approximate Message Passing" (AMP) view, proving that the high-dimensional Lasso problem effectively "decouples" into $N$ independent scalar denoising problems. By proving uniform concentration, the authors provide the first rigorous justification for using adaptive tuning procedures like SURE (Stein’s Unbiased Risk Estimate) and $k$-fold Cross-Validation.

Risk comparison for Lasso tuning methods across independent and correlated designs.

As shown in the figure above, the theoretical "risk curves" (red line) perfectly track the actual performance of adaptive Lasso across various sampling rates $\delta = n/N$. This holds true for both standard independent designs and correlated designs, which often present challenges for theoretical models. The authors prove that $\lambda$ chosen via SURE or Cross-Validation asymptotically achieves the same risk as the theoretically optimal (but usually unknown) $\lambda$.

Conclusion and Future Directions

This work provides the necessary mathematical "green light" for data-driven Lasso tuning. While the core proofs rely on Gaussian design matrices, simulations suggest the results are robust even under correlation. Future work may extend this "local stability" framework to other regularized M-estimators, such as Slope or square-root Lasso, further bridging the gap between high-dimensional probability theory and practical statistical engineering.

Summary updated

Abstract

The Lasso is a popular regression method for high-dimensional problems in which the number of parameters θ1,…,θN, is larger than the number n of samples: N>n. A useful heuristics relates the statistical properties of the Lasso estimator to that of a simple soft-thresholding denoiser, in a denoising problem in which the parameters (θi)i≤N are observed in Gaussian noise, with a carefully tuned variance. Earlier work confirmed this picture in the limit n,N→∞, pointwise in the parameters θ and in the value of the regularization parameter. Here, we consider a standard random design model and prove exponential concentration of its empirical distribution around the prediction provided by the Gaussian denoising model. Crucially, our results are uniform with respect to θ belonging to ℓq balls, q∈[0,1], and with respect to the regularization parameter. This allows us to derive sharp results for the performances of various data-driven procedures to tune the regularization. Our proofs make use of Gaussian comparison inequalities, and in particular of a version of Gordon’s minimax theorem developed by Thrampoulidis, Oymak and Hassibi, which controls the optimum value of the Lasso optimization problem. Crucially, we prove a stability property of the minimizer in Wasserstein distance that allows one to characterize properties of the minimizer itself.
BibTeX
@article{leo2021distribution,
  author = {Marco Leo and Andrea Montanari},
  title = {{The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning}},
  journal = {The Annals of Statistics},
  year = {2021},
  doi = {10.1214/20-aos2038},
}
Figure