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

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 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 to characterize properties of the minimizer itself.

arXiv comment68 pages, 2 figures

References in corpus (8)

• Simultaneous analysis of Lasso and Dantzig selector
• Message Passing Algorithms for Compressed Sensing
• On the conditions used to prove oracle results for the Lasso
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Regularization Techniques for Learning with Matrices
• Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization

Cited by in corpus (6)

• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Sensitivity of ${\ell }_1$ minimization to parameter choice
• Sharp Analysis of RLS-based Digital Precoder with Limited PAPR in Massive MIMO
• Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective