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

Abstract

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