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

Introduction

for $\sigma\geq 0$, $z\sim\mathcal{N}(0,{\rm I}_{n})$, and $\theta^{\star}$ a vector with $s_{0}$ non-zero entries. Then, a theorem of Bickel, Ritov and Tsybakov implies that, with high probability,

for some constants $c_{0}$, $C$ that depend on the specific assumptions on the design. (The normalization of is recovered by setting $\sigma^{2}=\sigma^{2}_{\#}/n$, where $\sigma_{\#}^{2}$ is the noise variance of .)

Unfortunately, this analysis provides limited insight into the choice of the regularization parameter $\lambda$ which –in practice– can impact significantly the estimation accuracy. As an example, Fig. 3 reports the result of a small simulation in which we compare four different methods of selecting $\lambda$. The bound of Eq. (3) suggests to set $\lambda=\sigma\sqrt{c_{0}\log N}$. For the standard random design used in the left frame, the optimal constant is expected to be $c_{0}=2$ . We compare this method to three procedures that adapt the choice of $\lambda$ to the data: cross validation (CV), Stein’s Unbiased Risk Estimate (SURE), and a procedure that minimizes an estimate of the risk (EST). We refer to the next sections for further details on these methods. Note that all of these adaptive procedures significantly outperform the ‘theory driven’ $\lambda$: over a broad range of sample sizes $n$, the resulting estimation error is $2$ to $3$ times smaller. Further, the error achieved by these methods is quite close to the Bayes optimum.

These empirical observations are not captured by the bound (3), or by similar results.

An alternative style of analysis postulates an idealized model for the data and derives asymptotically exact results. Throughout this paper we will consider the simplest of such models, by assuming that design matrix to have i.i.d. entries $X_{ij}\sim\mathcal{N}(0,1/n)$. While this assumption is likely to be violated in practice, it allows to derive useful insights that are mathematically consistent, and susceptible of being generalized to a broader context. This type of analysis was first carried out in the context of the Lasso in and then extended to a number of other problems, see e.g. . As an example, Figure 1 reports the predictions of this analysis for the risk of the three adaptive procedure for selecting $\lambda$. The agreement with the numerical simulations is excellent.

Unfortunately, the results in (and in follow-up work) do not allow to derive in a mathematically rigorous way curves such as the ones in Figure 1. In fact earlier results hold ‘pointwise’ over $\lambda$ and hence do not apply to adaptive procedures to select $\lambda$. Further they provide asymptotic estimates ‘pointwise’ over $\theta$, and hence do not allow to compute –for instance– minimax risk.

where the vector $\widehat{\theta}^{d}_{\lambda}$ is also referred to as the ‘debiased Lasso’ . The above identity holds for arbitrary $\alpha,\tau>0$. However, predicts that the distribution of the debiased estimator $\widehat{\theta}^{d}_{\lambda}$ simplifies dramatically for specific choices of these parameters.

Namely, let $\Theta$ be a random variable with distribution given by the empirical distribution of $(\theta_{i})_{i\leq N}$ (i.e., $\Theta=\theta_{i}$ with probability $1/N$, for $i\in\{1,\dots,N\}$) and let $Z\sim\mathcal{N}(0,1)$ be independent of $\Theta$. Define $\alpha_{*},\tau_{*}$ to be the solution of the following system of equations (we refer to Section 3.1 for a discussion of existence and uniqueness):

This is an asymptotic result, which holds along sequences of problems with: $(i)$ Converging aspect ratio $n/N\to\delta\in(0,\infty)$; $(ii)$ Fixed regularization $\lambda\in(0,\infty)$; $(iii)$ Parameter vectors $\theta^{\star}=\theta^{\star}(n)$ whose empirical distribution converges (weakly) to a limit law $p_{\Theta}$. As emphasized above, this does not allow deduce the behavior of the Lasso with adaptive choices of $\lambda$ (there could be deviations from the above limits for exceptional values of $\lambda$), or to compute the minimax risk (there could be deviations for exceptional vectors $\theta^{\star}$).

The importance of establishing uniform convergence with respect to the regularization parameter $\lambda$ was recently emphasized by Mousavi, Maleki, and Baraniuk . Among other results, these authors derive a uniform convergence statement for the related approximate message passing (AMP) algorithm. However, in order to establish uniform convergence, they have to construct an ad-hoc smoothing of the quantity of interest, which is roughly equivalent to discretizing the corresponding tuning parameter.

In this paper, we obtain uniform (in $\lambda$) convergence results for the Lasso, hence providing a sound mathematical basis to the comparison of various adaptive procedures, as well as to the study of minimax risk.

The rest of the paper is organized as follows. Section 2 reviews related work. We state our main theoretical results in Section 3. In Section 4 we apply these results to two types of statistical questions: estimating the risk and noise level, and selecting $\lambda$ through adaptive procedures. Further, we illustrate our results in numerical simulations. Finally, Section 5 outlines the main proof ideas, with most technical legwork deferred to the appendices.

Related work

There is –by now– a substantial literature on determining exact asymptotics in high-dimensional statistical models, and a number of mathematical techniques have been developed for this task. We will only provide a few pointers focusing on high-dimensional regression problems.

The original proof of was based on an asymptotically exact analysis of an approximate message passing (AMP) algorithm that was first proposed in to minimize the Lasso cost function. Variants of AMP have been developed in a number of contexts, opening the way to the analysis of various statistical estimation problems. A short list includes generalized linear models , phase retrieval , robust regression , logistic regression , generalized compressed sensing . This approach is technically less direct than others, but has the advantage of providing an efficient algorithm, and is and not necessarily limited to convex problems (see for a non-convex example).

As mentioned above, our work was partially motivated by the recent results of Mousavi, Maleki, and Baraniuk that establish a form of uniformity for the AMP estimates –but not for the Lasso solution. It would be interesting to understand whether the approach of could also be used to obtain uniform results for the Lasso or other statistical estimators.

Here we follow a different route that exploits powerful Gaussian comparison inequalities first proved by Gordon . Gordon inequality allows to bound the distribution of a minimax value, i.e. the value of a random variable $G_{*}=\min_{i\leq N}\max_{j\leq M}G_{ij}$, where $(G_{ij})_{i\leq N,j\leq M}$ is a Gaussian process, in terms of a similar quantity for a ‘simpler’ Gaussian process. The use of Gordon’s inequality in this context was pioneered by Stojnic and then developed by a number of authors in the context of regularized regression , M-estimation , generalized compressed sensing , binary compressed sensing and so on. The key idea is to write the optimization problem of interest as a minimax problem, and then apply a suitable version of Gordon’s inequality. A matching bound is obtained by convex duality and then a second application of Gordon’s inequality. In particular, convexity of the cost function of interest is a crucial ingredient.

While the Gaussian comparison inequality provides direct access to the value of the optimization problem, understanding the properties of the estimator can be more challenging. In this paper we identify a property (that we call local stability) that allows to transfer information on the minimum (the Lasso cost) into information about the minimizer (the Lasso estimator). We believe this strategy can be applied to other examples beyond the Lasso.

Independently, a different approach based on leave-one-out techniques was developed by El Karoui in the context of ridge-regularized robust regression .

Finally, a parallel line of research determines exact asymptotics for Bayes optimal estimation, under a model in which the coordinates of $\theta$ are i.i.d. with common distribution $p_{\Theta}$. In particular, the asymptotic Bayes optimal error for linear regression with random designs was recently determined in . Of course –in general– Bayes optimal estimation requires knowledge of the distribution $p_{\Theta}$, and is not computationally efficient. We will use this Bayes-optimal error as a benchmark of our adaptive procedures. Generalizations of these results were also obtained in for other regression problems. A successful approach to these models uses smart interpolation techniques that generalize ideas in spin-glass theory.

Main results

As stated above, we consider the standard linear model (2) where $y=X\theta^{\star}+\sigma z$ , with noise $z\sim\mathcal{N}(0,{\rm I}_{n})$, and $X$ a Gaussian design: $(X_{i,j})_{i\leq n,j\leq N}\overset{\text{\tiny i.i.d.}}{\sim}\mathcal{N}(0,1/n)$. The Lasso estimator is defined by

By Jensen’s inequality we have for $p\geq p^{\prime}>0$, $\mathcal{F}_{p}(\xi)\subset\mathcal{F}_{p^{\prime}}(\xi)$.

A crucial role in our results is provided by the following max-min problem:

The expectation above is with respect to $(\Theta,Z)\sim\widehat{\mu}_{\theta^{\star}}\otimes\mathcal{N}(0,1)$, where $\widehat{\mu}_{\theta^{\star}}$ denotes the empirical distribution of the entries of the vector $\theta^{\star}$:

The max-min (8) is achieved at a unique couple $(\beta_{*}(\lambda),\tau_{*}(\lambda))$. Moreover, $(\tau_{*}(\lambda),\beta_{*}(\lambda))$ is also the unique couple $(\beta,\tau)\in(0,+\infty)^{2}$ that verify

We will also use the notation $\alpha_{*}(\lambda)=\lambda/\beta_{*}(\lambda)$ and

We will sometimes omit the dependency on $\lambda$ and write simply $\alpha_{*},\beta_{*},\tau_{*},s_{*}$. The distribution $\mu^{*}_{\lambda}$ defined below will correspond (see Theorem 3.1 in the next section) to the limit of the empirical distribution of the entries of $(\widehat{\theta}_{\lambda},\theta^{\star})$.

We denote by $\mu_{\lambda}^{*}$ the law of the couple $\left(\eta\big(\Theta+\tau_{*}(\lambda)Z,\,\alpha_{*}(\lambda)\tau_{*}(\lambda)\big),\ \Theta\right)$, where $(\Theta,Z)\sim\widehat{\mu}_{\theta^{\star}}\otimes\mathcal{N}(0,1)$.

2 Results

Assume that $\mathcal{D}=\mathcal{F}_{p}(\xi)$ for some $\xi>0$ and $p>0$. Then there exists constants $C,c>0$ that only depend on $\Omega$, such that for all $\epsilon\in(0,\frac{1}{2}]$

It is worth emphasizing in what sense Theorem 3.1 is uniform with respect to $\lambda\in[\lambda_{\min},\lambda_{\max}]$ and to $\theta^{\star}\in\mathcal{D}$:

Uniformity with respect to $\lambda$. We bound (in probability) the maximum (over $\lambda$) deviation between the empirical distribution $\widehat{\mu}_{(\widehat{\theta}_{\lambda},\theta^{\star})}$ and the predicted distribution $\mu^{*}_{\lambda}$. (The supremum over $\lambda$ is ‘inside’ the probability.)

Uniformity with respect to $\theta^{\star}$. We bound the maximum probability (over $\theta^{\star}$) of a deviation between $\widehat{\mu}_{(\widehat{\theta}_{\lambda},\theta^{\star})}$ and $\mu^{*}_{\lambda}$. (The supremum over $\theta^{\star}$ is ‘outside’ the probability.)

The reader might wonder whether it is possible to strengthen this result and bound the maximum deviation over $\theta^{\star}$ (‘move the supremum over $\theta^{\star}$ inside’). The answer is negative. In particular, we can choose the support of $\theta^{\star}$ to coincide with a submatrix of $X$ with atypically small minimum singular value. This will result in larger estimation error $\|\widehat{\theta}_{\lambda}-\theta^{\star}\|_{2}$, and hence in a large Wasserstein distance $W_{2}(\widehat{\mu}_{(\widehat{\theta}_{\lambda},\theta^{\star})},\mu^{*}_{\lambda})$.

In order to see this, it is sufficient to consider the vector

In Appendix F.1, we prove that (for this choice of $\theta^{\star}$) there exists a constant $c_{0}$ such that $W_{2}(\widehat{\mu}_{(\widehat{\theta}_{\lambda},\theta^{\star})},\mu^{*}_{\lambda})\geq\sqrt{k/N}$ with probability at least $1-e^{-c_{0}k}$ for all $N$ large enough.

Assume here that $\mathcal{D}$ is either $\mathcal{F}_{0}(s)$ or $\mathcal{F}_{p}(\xi)$ for some $0\leq s<s_{\rm max}(\delta)$ and $\xi>0,p>0$. There exists constants $C,c>0$ that only depend on $\Omega$, such that for all $\epsilon\in(0,1]$

where $q=0$ if $\mathcal{D}=\mathcal{F}_{0}(s)$ and $q=(1/p-1)_{+}$ if $\mathcal{D}=\mathcal{F}_{p}(\xi)$.

The statement (14) is proved in Appendix C.2, while (15)-(16) are proved in Appendix D.

So far we focused on the Lasso estimator $\widehat{\theta}_{\lambda}$. The debiased Lasso estimator is defined as

This estimator plays a crucial role in the construction of confidence intervals and $p$-values , and provide an explicit construction of the ‘direct observations’ model in the sense that $\widehat{\theta}_{\lambda}^{d}$ is approximately distributed as $\mathcal{N}(\theta^{\star},\tau_{*}{\rm I})$. We let $\mu^{(d)}_{\lambda}$ be the law of the couple $\big(\Theta+\tau_{*}(\lambda)Z,\ \Theta\big)$, where $(\Theta,Z)\sim\hat{\mu}_{\theta^{\star}}\otimes\mathcal{N}(0,1)$.

Applications

In order to select the regularization parameter and to evaluate the quality of the Lasso solution $\widehat{\theta}_{\lambda}$, it is useful to estimate the risk and noise level. The paper developed a suite of estimators of these quantities based on the asymptotic theory of . The same paper also proposed generalizations of these estimators to correlated designs. Here we revisit these estimators and prove stronger guarantees. First, we obtain quantitative bound on the consistency rate of our estimators. Second, our results are uniform over $\lambda$, which justifies using these estimators to select $\lambda$.

Let us start with the estimation of $\tau_{*}(\lambda)$ which plays a crucial role in the asymptotic theory. We define

We will see with Theorem F.1 presented in Appendix F.4 that

Further, by Theorem 3.2, we have $\frac{1}{\sqrt{n}}\|y-X\widehat{\theta}_{\lambda}\|=\beta_{*}(\lambda)+o_{n}(1)$. Recall that by (9) we have $\beta_{*}(\lambda)=\tau_{*}(\lambda)\big(1-\frac{1}{\delta}s_{*}(\lambda)\big)$. We deduce $\widehat{\tau}(\lambda)=\tau_{*}(\lambda)+o_{n}(1)$. More precisely we have the following consistency result.

Assume here that $\mathcal{D}$ is either $\mathcal{F}_{0}(s)$ or $\mathcal{F}_{p}(\xi)$ for some $0\leq s<s_{\rm max}(\delta)$ and $\xi>0,p>0$. There exists constants $C,c>0$ that only depend on $\Omega$ such that for all $\epsilon\in(0,1]$

where $q=0$ if $\mathcal{D}=\mathcal{F}_{0}(s)$ and $q=(1/p-1)_{+}$ if $\mathcal{D}=\mathcal{F}_{p}(\xi)$.

Assume here that $\mathcal{D}$ is either $\mathcal{F}_{0}(s)$ or $\mathcal{F}_{p}(\xi)$ for some $0\leq s<s_{\rm max}(\delta)$ and $\xi>0,p>0$. There exists constants $C,c>0$ such that for all $\epsilon\in(0,1]$,

where $q=0$ if $\mathcal{D}=\mathcal{F}_{0}(s)$ and $q=(1/p-1)_{+}$ if $\mathcal{D}=\mathcal{F}_{p}(\xi)$.

Corollary 4.2 is proved in Appendix F.6. Since by Corollary 4.2, Corollary 4.1, Theorem 3.2 we have with high probability $\widehat{R}(\lambda)\simeq\frac{1}{N}\|\widehat{\theta}_{\lambda}-\theta^{\star}\|^{2}\simeq\delta(\tau_{*}(\lambda)^{2}-\sigma^{2})\simeq\delta(\widehat{\tau}(\lambda)^{2}-\sigma^{2})$, the estimator

is a consistent estimator of the noise level $\sigma^{2}$.

There exists constants $C,c>0$ that only depend on $\Omega$, such that for all $\epsilon\in(0,1]$

Finally, we consider the prediction error $\|X\theta^{\star}-X\widehat{\theta}_{\lambda}\|$. Stein Unbiased Risk Estimator (SURE) provides a general method to estimate the prediction error, see e.g. . In the present case, it takes the form

Tibshirani and Taylor proved that $\widehat{P}^{\rm SURE}(\lambda)$ is an unbiased estimator of the prediction error, namely

The next result establishes consistency, uniformly over $\lambda$ and $\theta^{\star}$, with quantitative concentration estimates.

Assume here that $\mathcal{D}$ is either $\mathcal{F}_{0}(s)$ or $\mathcal{F}_{p}(\xi)$ for some $0\leq s<s_{\rm max}(\delta)$ and $\xi>0,p>0$. There exists constants $C,c>0$ that only depend on $\Omega$ such that for all $\epsilon\in(0,1]$

where $q=0$ if $\mathcal{D}=\mathcal{F}_{0}(s)$ and $q=(1/p-1)_{+}$ if $\mathcal{D}=\mathcal{F}_{p}(\xi)$.

The same result holds if $\sigma$ in (18) is replaced by an estimator of the noise level satisfying the same consistency condition as $\widehat{\sigma}$ defined by (17) (cf. Corollary 4.3).

This corollary follows simply from Theorem F.1 and Theorem 3.2.

Notice that exact unbiasedness of $\widehat{P}^{\rm SURE}(\lambda)$ only holds if the noise $z$ in the linear model (2) is Gaussian . In contrast, it is not hard to generalize the proofs in the present paper to include other noise distributions.

2 Adaptive selection of λ\lambda

As anticipated, we can use our uniform bounds to select $\lambda$ through an adaptive procedure. We discuss here three such procedures, that have already been illustrated in Figure 1: $(i)$ Selecting $\lambda$ by minimizing the estimate $\widehat{\tau}(\lambda)$, we denote this by $\widehat{\lambda}^{\rm EST}$; $(ii)$ Select $\lambda$ as to minimize Stein’s Unbiased Risk Estimate $\widehat{P}^{\rm SURE}(\lambda)$, $\widehat{\lambda}^{\rm SURE}$; $(iii)$ Select $\lambda$ by $k$-fold cross-validation, $\widehat{\lambda}^{k\text{-CV}}$. We will next describe these procedures in greater detail, and state the corresponding guarantees.

The next result is an immediate consequence of Theorem 3.2 and Corollary 4.1:

Assume here that $\mathcal{D}$ is either $\mathcal{F}_{0}(s)$ or $\mathcal{F}_{p}(\xi)$ for some $0\leq s<s_{\rm max}(\delta)$ and $\xi>0,p>0$. There exists constants $C,c>0$ that only depend on $\Omega$ such that for all $\epsilon\in(0,1]$

where $q=0$ if $\mathcal{D}=\mathcal{F}_{0}(s)$ and $q=(1/p-1)_{+}$ if $\mathcal{D}=\mathcal{F}_{p}(\xi)$.

Here, it is understood that we can use either $\sigma$ or $\widehat{\sigma}(\lambda)$, cf. Eq. (17), in the definition of $\widehat{P}^{\rm SURE}$. We deduce from Corollary 4.4:

Assume here that $\mathcal{D}$ is either $\mathcal{F}_{0}(s)$ or $\mathcal{F}_{p}(\xi)$ for some $0\leq s<s_{\rm max}(\delta)$ and $\xi>0,p>0$. There exists constants $C,c>0$ that only depend on $\Omega$ such that for all $\epsilon\in(0,1]$

where $q=0$ if $\mathcal{D}=\mathcal{F}_{0}(s)$ and $q=(1/p-1)_{+}$ if $\mathcal{D}=\mathcal{F}_{p}(\xi)$.

Cross-validation. We analyze now $k$-fold Cross Validation. Let $k\geq 2$ and define $n_{k}=n(k-1)/k$. We partition the rows of $X$ in $k$ groups: we obtain $k$-submatrices of size $(n/k)\times N$ that we denote $X^{(1)},\dots,X^{(k)}$. Let us also write for $i\in\{1,\dots,k\}$, $X^{(\text{-}i)}$ for the submatrix of $X$ obtained by removing the rows $X^{(i)}$. We denote by $y^{(i)}$, $z^{(i)}$ and $y^{(\text{-}i)}$, $z^{(\text{-}i)}$ the corresponding subvectors of $y$ and $z$.

The estimator $\widehat{R}^{k\text{-CV}}$ of the risk using $k$-fold cross validation if defined as follows. For $i=1,\dots,k$ solve the Lasso problem

The next Proposition shows that $\widehat{R}^{k\text{-CV}}(\lambda)$ is equal to the true risk (shifted by $\delta\sigma^{2}$) up to $O(k^{-1/2})$.

There exists constants $c,C>0$ that depend only on $\Omega$, such that for all $k\geq 2$ such that $s_{\rm max}\big((k-1)\delta/k\big)>s$ in the case where $\mathcal{D}=\mathcal{F}_{0}(s)$, we have

where $q=0$ if $\mathcal{D}=\mathcal{F}_{0}(s)$ and $q=(1/p-1)_{+}$ if $\mathcal{D}=\mathcal{F}_{p}(\xi)$.

Proposition 4.3 is proved in Appendix F.7. It follows from Proposition 4.3 that with high probability,

3 Numerical experiments

In this Section we compare numerically various different choices for the regularization parameter $\lambda$, namely $\widehat{\lambda}^{\rm EST}$, $\widehat{\lambda}^{\rm SURE}$ and $\widehat{\lambda}^{k\text{-CV}}$, presented in the previous section. For these experiments we take the components $\theta_{1}^{\star},\dots,\theta_{N}^{\star}$ to be i.i.d. from

Within this probabilistic model, we can compare achieved by our various choice of $\lambda$ to the Bayes optimal error (Minimal Mean Squared Error):

where the minimum is taken over all estimators $\widehat{\theta}$ (i.e. measurable functions of $X,y$). The limit of the MMSE has been recently computed by and . Recall, that given two random variables $U,V$, their mutual information is the Kullback-Leibler divergence between their joint distribution and the product of the marginals: $I(U;V)\equiv D_{\mbox{\tiny\rm KL}}(p_{U,V}\|p_{U}\times p_{V})$.

Figure 1 reports the risk achieved by the various choices of $\lambda$ as a function of the number of samples per dimension $\delta$. We also compare the data-driven procedures of the previous section to the theory-driven choice $\lambda=\sigma\sqrt{2\log N}$. In the left frame, we consider uncorrelated random designs: $X_{i,j}\overset{\text{\tiny i.i.d.}}{\sim}\mathcal{N}(0,1/n)$. On the right, we consider i.i.d. Gaussian rows with covariance structure determined by an auto-regressive model. Explicitly, the columns $(X_{j})_{1\leq j\leq N}$ of $X$ are generated according to:

where $u_{j}\overset{\text{\tiny i.i.d.}}{\sim}\mathcal{N}(0,{\rm I}/n)$ and $\phi=2$. For both types of designs, $\widehat{\lambda}^{\rm EST}$, $\widehat{\lambda}^{\rm SURE}$ and $\widehat{\lambda}^{k\text{-CV}}$ perform similarly, and substantially outperform the theoretical choice $\lambda=\sigma\sqrt{2\log N}$.

For uncorrelated designs, the resulting risk is closely tracked by the asymptotic theory, and is surprisingly close to the asymptotic prediction for the Bayes risk ${{\rm MMSE}}_{N}$.

While our theory does not cover the case of correlated designs, the qualitative behavior is remarkably similar. We also observed that in this case, the risk estimator $\widehat{R}(\lambda)$ is not consistent but its minimum is roughly located at the same value of $\lambda$ as for uncorrelated designs.

Next we study adaptivity to sparsity. On Figure 2, we plot the risk as a function of the sparsity of the signal $\theta^{\star}$. We compare the three adaptive procedures (namely, $\widehat{\lambda}^{\rm EST}$, $\widehat{\lambda}^{\rm SURE}$ and $\widehat{\lambda}^{k\text{-CV}}$), to the following choice

where $s_{0}<s_{\rm max}(\delta)$ is a nominal value for the sparsity (in Figure 2, we use $s_{0}=0.3$). The value $\lambda^{\rm MM}(s_{0})$ is expected to be asymptotically minimax optimal over $\mathcal{F}_{0}(s_{0})$ .

Also in this example, adaptive procedures dramatically outperform the fixed choice $\lambda=\sigma\sqrt{2\log N}$, and also the minimax optimal $\lambda$ at the nominal sparsity level.

Proof strategy

As mentioned above, our proofs are based on Gaussian comparison inequalities, and in particular on Gordon’s min-max theorem . In this section we review the application of this inequality to the Lasso as developed in . We then discuss the limitations of earlier work, which does not characterize the empirical distribution of the Lasso estimator $\widehat{\theta}_{\lambda}$ (or need extra sparsity assumptions ) nor uniform bounds as in Theorem 3.1. A key challenge is related to the fact that the Lasso cost function (1) is convex but not strongly convex. Hence, a small change in $\lambda$ could cause a priori a large change in the minimizer $\widehat{\theta}_{\lambda}$.

In order to overcome these problems, we establish a property that we call ‘local stability.’ Namely, if the empirical distribution of $(\widehat{\theta}_{\lambda},\theta^{\star})$ deviates from our prediction, then the value of the optimization problem increases significantly. This implies that the empirical distribution is stable with respect to perturbations of the cost (e.g. changes in $\lambda$). Gordon’s comparison is again crucial to prove this stability property.

Finally, we describe how local stability is used to prove the theorems in the previous sections. A full description of the proofs is provided in the appendices.

It is more convenient (but equivalent) to study $\widehat{w}_{\lambda}=\widehat{\theta}_{\lambda}-\theta^{\star}$ instead of $\widehat{\theta}_{\lambda}$. The vector $\widehat{w}_{\lambda}$ is the minimizer of the cost function

Following , we rewrite the minimization of $\mathcal{C}_{\lambda}$ as a saddle point problem:

We apply the following Theorem from which improves over Gordon’s Theorem by exploiting convex duality.

For the reader’s convenience, we provide in Appendix G.3 a proof of this theorem.

Because of Gordon’s Theorem, it suffices now to study (see Corollary 5.1 below) for $(g,g^{\prime},h)\sim\mathcal{N}(0,\mathbf{I}_{N})\otimes\mathcal{N}(0,1)\otimes\mathcal{N}(0,\mathbf{I}_{n})$.

Let us suppose that $X,z,g,h,g^{\prime}$ live on the same probability space and are independent. Let $\epsilon\in(0,1]$. Let $\sigma_{\rm max}(X)$ denote the largest singular value of the matrix $X$. By tightness we can find $K>0$ such that the event

Since the sets $D\cap B(0,R_{1})$ and $B(0,R_{3})$ are compact, one can apply Theorem 5.1 to $c_{\lambda}$ and $l_{\lambda}$ and obtain:

The Corollary follows then from the fact one can take $\epsilon$ arbitrarily small. $\square$

2 Local stability

for some $\epsilon>0$. Using Gordon’s min-max Theorem (Corollary 5.1) we will be able to show

It remains now to study the cost function $L_{\lambda}$, which is much simpler. This is done in Appendix B. The key step will be to establish the following ‘local stability’ result (the next statement is an immediate consequence of Proposition B.1 and Theorem B.1 in the appendices. We prove in fact that the cost function $L_{\lambda}$ is strongly convex on a neighborhood of its minimizer.).

The minimizer $w^{*}_{\lambda}=\arg\min_{w}L_{\lambda}(w)$ exists and is almost surely unique. Further, there exists constants $\gamma,c,C>0$ that only depend on $\Omega$ such that for all $\theta^{\star}\in\mathcal{D}$, all $\lambda\in[\lambda_{\rm min},\lambda_{\rm max}]$ and all $\epsilon\in(0,1]$

We do not obtain an equally strong result for the cost function $\mathcal{C}_{\lambda}(w)$, but we prove the following statement, which is sufficient for obtaining uniform control (for the sake of argument, we focus here on the domain $\mathcal{F}_{p}(\xi)$ and control of the empirical distribution).

Assume that $\mathcal{D}=\mathcal{F}_{p}(\xi)$ for some $\xi,p>0$. There exists constants $C,c,\gamma>0$ that only depend on $\Omega$ such that for all $\epsilon\in(0,\frac{1}{2}]$

3 Sketch of proof of main results

For the sake of simplicity, we will illustrate the prove strategy by considering the empirical distribution of $\widehat{w}_{\lambda}=\widehat{\theta}_{\lambda}-\theta^{\star}$, as the argument is similar for other quantities. According to Theorem 3.1, this should be well approximated by $\overline{\mu}_{\lambda}$ that is the law of $\widehat{\Theta}-\Theta$, when $(\widehat{\Theta},\Theta)\sim\mu_{\lambda}^{*}$, cf. Definition 3.3.

As anticipated, Eq. (25) and Theorem 5.2, allow to control $W_{2}(\widehat{\mu}_{\widehat{w}_{\lambda}},\overline{\mu}_{\lambda})$ for a fixed $\lambda$ ($\widehat{\mu}_{\widehat{w}_{\lambda}}$ denotes the empirical distribution of the entries of $\widehat{w}_{\lambda}$). Namely, we can define $D_{{\varepsilon}}$ to be the set of vectors $w$ such that $W_{2}(\widehat{\mu}_{w},\overline{\mu}_{\lambda})\geq{\varepsilon}>0$. We then prove that the minimizer $w^{*}_{\lambda}$ of $L_{\lambda}$ has empirical distribution close to $\overline{\mu}_{\lambda}$, and therefore by Theorem 5.2, $L_{\lambda}(w)>L_{\lambda}(w^{*}_{\lambda})+\gamma\epsilon$ for all $w\in D_{\epsilon}$, with high probability. This imply that the right-hand side of (25) is very small and we deduce that, with high probability, all minimizers or near minimizers of $\mathcal{C}_{\lambda}(w)$ have empirical distribution close to $\overline{\mu}_{\lambda}$,

We now would like to prove Theorem 3.1 and show that with high probability $\widehat{\mu}_{\widehat{w}_{\lambda}}\approx\overline{\mu}_{\lambda}$, uniformly in $\lambda\in[\lambda_{\rm min},\lambda_{\rm max}]$. To do so, we apply the above argument for $\lambda=\lambda_{1},\dots,\lambda_{k}$, where $\lambda_{1},\dots,\lambda_{k}$ is an $\epsilon$-net of $[\lambda_{\rm min},\lambda_{\rm max}]$. This implies that, with high probability for $\lambda\in\{\lambda_{1},\dots,\lambda_{k}\}$, $W_{2}(\widehat{\mu}_{\widehat{w}_{\lambda_{i}}},\overline{\mu}_{\lambda_{i}})\leq{\varepsilon}$. Next, for $\lambda\in[\lambda_{i},\lambda_{i+1}]$, we show that

Consequently if $|\lambda_{i+1}-\lambda_{i}|=O(\epsilon)$ (using again Eq. (25) and Theorem 5.2), we obtain that $W_{2}(\widehat{\mu}_{\widehat{w}_{\lambda}},\overline{\mu}_{\lambda_{i}})=O(\epsilon)$ and therefore $W_{2}(\widehat{\mu}_{\widehat{w}_{\lambda}},\overline{\mu}_{\lambda})=O(\epsilon)$. We conclude that $W_{2}(\widehat{\mu}_{\widehat{w}_{\lambda}},\overline{\mu}_{\lambda})=O(\epsilon)$ for all $\lambda\in[\lambda_{\rm min},\lambda_{\rm max}]$, with high probability, which is the desired claim.

If the strategy exposed above allows to obtain the risk of the Lasso and the empirical distribution of its coordinates, it is not enough to get its sparsity $\|\widehat{\theta}_{\lambda}\|_{0}$ or to obtain the empirical distribution of the debiased lasso

Therefore, we will need to analyze the vector

The detailed analysis is done in Section E.

Acknowledgements

This work was partially supported by grants NSF DMS-1613091, NSF CCF-1714305 and NSF IIS-1741162 and ONR N00014-18-1-2729.

Appendix A Study of the scalar optimization problem

In this section we study the scalar optimization problem (8):

admits a unique positive solution $\alpha_{\rm min}=\alpha_{\rm min}(\delta)>0$.

More generally, we will always write $\alpha=\lambda/\beta$. We prove in this section the following theorem and some auxiliary results.

The max-min (8) is achieved at a unique couple $(\beta_{*},\tau_{*})$ and $0<\beta_{*}<\beta_{\rm max}$. Moreover, $(\tau_{*},\beta_{*})$ is also the unique couple in $(0,+\infty)^{2}$ that verify

If $\beta>\beta_{\rm max}$, $\displaystyle\psi_{\lambda}(\beta,\tau)\xrightarrow[\tau\to+\infty]{}-\infty\,.$

Proof . By (28) and the fact that $\Delta_{\alpha}(0)=\frac{1}{2}+\alpha\phi(\alpha)-(\alpha^{2}+1)\Phi(-\alpha)$ by Lemma F.13, we get that for all $\beta,\tau>0$

Using the definition of $\beta_{\rm max}$: if $\beta>\beta_{\rm max}$ then $\alpha<\alpha_{\rm min}$ and therefore $\frac{\delta}{2}+\alpha\phi(\alpha)-(\alpha^{2}+1)\Phi(-\alpha)<0$. If $\beta=\beta_{\rm max}$, $\frac{\delta}{2}+\alpha\phi(\alpha)-(\alpha^{2}+1)\Phi(-\alpha)=0$. It remains to compute the limit of $\xi_{\alpha}(\tau)$ as $\tau\to\infty$.

Using the expression (see Lemma F.13) of the left-and right-derivatives of $\Delta_{\alpha}$ at $0$, we have almost-surely:

$w^{*}(\alpha,\tau)$ is the minimizer of $w\mapsto\frac{w^{2}}{2\tau}\beta-\beta Zw+\lambda|w+\Theta|$ (recall that we always write $\alpha=\lambda/\beta$).

If $\beta\geq\beta_{\rm max}$ the equation

does not admits any solution on $(0,+\infty)$. For all $\beta\in(0,\beta_{\rm max})$, the function $\psi_{\lambda}(\beta,\cdot)$ admits a unique minimizer $\tau_{*}(\beta)$ on $(0,+\infty)$ that is also the unique solution of (29). Moreover, $\alpha\mapsto\tau_{*}(\alpha)$ is $\mathcal{C}^{\infty}$ on $(\alpha_{\rm min},+\infty)$ and for all $\alpha>\alpha_{\rm min}$

Proof . Most of this lemma was already proved in , we however provide a full proof for completeness. We have to study the fixed point equation

where $\alpha=\lambda/\beta$. We can compute $F_{\alpha}$ explicitly:

where we used the notation $x=\frac{\Theta}{\tau}$. We can then compute the derivatives:

$F_{\alpha}$ is therefore concave. By dominated convergence

Since $F_{\alpha}(0)=\sigma^{2}>0$ and by concavity of $F_{\alpha}$, the fixed point equation admits a unique solution $\tau_{*}(\alpha)$ if and only is $\beta\in(0,\beta_{\rm max})$. In that case we have also $F_{\alpha}^{\prime}(\tau_{*}(\alpha))<1$.

Let us now assume that $\beta\in(0,\beta_{\rm max})$. We have almost-surely

Since $|w^{*}(\alpha,\tau)|\leq\alpha\tau+\tau|Z|$, we have by derivation under the expectation

Consequently, $\tau_{*}(\beta)$ is the unique minimizer of $\psi_{\lambda}(\beta,\cdot)$ over $(0,+\infty)$.

Let us now compute $\frac{\partial\tau_{*}^{2}}{\partial\alpha}$. Since $F_{\alpha}$ is a $\mathcal{C}^{\infty}$ function of $\tau^{2}$, one can apply the implicit function theorem to obtain that the mapping $\alpha\mapsto\tau_{*}(\alpha)^{2}$ is $\mathcal{C}^{\infty}$ and moreover:

By concavity on has that $F^{\prime}_{\alpha}(\tau_{*}^{2}(\alpha))$ is smaller than the slope of the line between the points of coordinates $(0,\sigma^{2})$ and $(\tau_{*}^{2}(\alpha),\tau_{*}^{2}(\alpha))$:

The result follows then from the fact that $\frac{\partial\tau_{*}^{2}}{\partial\alpha}(\alpha)=2\tau_{*}(\alpha)\frac{\partial\tau_{*}}{\partial\alpha}(\alpha)$. $\square$

The function $\Psi_{\lambda}$ is differentiable on $(0,\beta_{\rm max})$ with derivative

Proof . $\Psi_{\lambda}$ is differentiable on $(0,\beta_{\rm max})$ (because of Lemma A.5) with derivative

because of (29). The second equality follows by Gaussian integration by parts. $\square$

Indeed, when $\beta\to 0^{+}$, $\alpha=\lambda/\beta\to+\infty$ and $|\frac{\Theta}{\tau_{*}(\alpha)}|\leq\frac{|\Theta|}{\sigma}$. Therefore by Lemma A.6 we obtain

By concavity, we deduce that $\beta_{*}\in(0,\beta_{\rm max})$. $\square$

The function $\lambda\mapsto\beta_{*}(\lambda)$ is $\mathcal{C}^{\infty}$ and is $2\alpha_{\rm min}^{-1}$-Lipschitz over $(0,+\infty)$. $\lambda\mapsto\alpha_{*}(\lambda)$ is $\mathcal{C}^{\infty}$ over $(0,+\infty)$ and strictly increasing.

Proof . Let us define $\gamma_{*}(\lambda)=\beta_{*}(\lambda)/\lambda$. $\gamma_{*}(\lambda)$ is the unique maximizer of

One deduces that $\lambda\mapsto\alpha_{*}(\lambda)=\gamma_{*}(\lambda)^{-1}$ is $\mathcal{C}^{\infty}$ and strictly increasing and that $\lambda\mapsto\beta_{*}(\lambda)=\lambda\gamma_{*}(\lambda)$ is $\mathcal{C}^{\infty}$. Moreover

Proof of Theorem A.1. By Corollary A.1, the maximum in $\beta$ in (8) is achieved at a unique $\beta_{*}\in(0,\beta_{\rm max})$. To this $\beta_{*}$ corresponds a unique $\tau_{*}(\beta_{*})$ that achieves the minimum in (8), by Lemma A.5. By (29) and (34) we obtain that $(\tau_{*}(\beta_{*}),\beta_{*})$ is solution of the system (27). Let now $(\tau,\beta)\in(0,+\infty)^{2}$ be another solution of (27). $\tau$ is therefore solution of (29) which gives that $\beta\in(0,\beta_{\rm max})$ and $\tau=\tau_{*}(\beta)$ by Lemma A.5. The second equality in (27) gives that $\Psi_{\lambda}^{\prime}(\beta)=0$ and thus that $\beta=\beta_{*}$ by strong concavity of $\Psi_{\lambda}$. We conclude $(\tau,\beta)=(\tau_{*}(\beta_{*}),\beta_{*})$. $\square$

A.2 Control on β∗,τ∗\beta_{*},\tau_{*}

The goal of this section is to show that $\beta_{*}$ and $\tau_{*}$ remain bounded when $\theta^{\star}$ varies in $\mathcal{D}$.

There exists constants $\beta_{\rm min},\tau_{\rm max}>0$ that only depend on $\Omega$ such that for all $\theta^{\star}\in\mathcal{D}$ and all $\lambda\in[\lambda_{\rm min},\lambda_{\rm max}]$,

To prove Theorem A.2, we separate the case where $\mathcal{D}=\mathcal{F}_{p}(\xi)$ (where it follows from Lemma A.9 and Corollary A.2 below) from the case where $\mathcal{D}=\mathcal{F}_{0}(s)$ (where it follows from Lemmas A.11 and A.12).

Proof . Using the optimality condition (29) of $\tau_{*}(\beta)$, we have for all $\beta\in(0,\beta_{\rm max})$

and we obtain the Lemma by putting this together with (38) and (37). $\square$

The next Lemma summarizes the main properties of $H_{\alpha}$.

$H_{\alpha}$ is a continuous, even function and for $x>0$

$H_{\alpha}$ is therefore $1$-Lipschitz. $H_{\alpha}$ admits a maximum at $0$ and

Moreover $H_{\alpha}(x)\xrightarrow[x\to+\infty]{}-\alpha$.

Proof . Let $\beta\in(0,\beta_{\rm max})$. By Lemma A.6 we have

As $\beta\to 0$, $\alpha\geq\lambda_{\rm min}/\beta\to+\infty$. Since $g_{\alpha}(K)\xrightarrow[\alpha\to+\infty]{}0$ there exists $\beta_{0}=\beta_{0}(K,\lambda_{\rm min},\delta)>0$ such that for all $\beta\in(0,\beta_{0})$, $g_{\alpha}(K)\leq\frac{\delta}{4}$. Thus for all $\beta\in(0,\beta_{0})$,

Let $\beta_{\rm min}=\min(\frac{\sigma}{2},\beta_{0})$. We conclude that for all $\beta\in(0,\beta_{\rm min})$, $\Psi_{\lambda}^{\prime}(\beta)>0$. By concavity we have then that $\beta_{*}\geq\beta_{\rm min}$. The other inequality $\beta_{*}<\beta_{\rm max}$ was already proved in Corollary A.1.

Since $\alpha_{*}\leq\lambda_{\rm max}/\beta_{\rm min}$ and $\phi(\alpha_{*})-\alpha_{*}\Phi(-\alpha_{*})>0$ (because $\alpha_{*}>\alpha_{\rm min}$), we can find a constant $t=t(\delta,\sigma,\lambda_{\rm min},\lambda_{\rm max},p,\xi)\geq\xi$ such that

Consequently by Lemma A.2 and Lemma A.7 we have

A.2.3 On sparse balls

$M_{s}$ corresponds to the worst mean squared error achievable by soft-thresholding with threshold $\alpha$ to estimate a vector $\theta^{\star}\in\mathcal{F}_{0}(s)$ from the observations $y=\theta^{\star}+w$, where $w\sim\mathcal{N}(0,I_{N})$, see .

Then there exists $\alpha\geq 0$ such that $M_{s}(\alpha)<\delta$.

which gives $M_{s}(\alpha)<\delta$. $\square$

We assume in this section that $s<s_{\rm max}(\delta)$. Let us compute the derivatives

Notice that $M_{s}(\alpha)=\frac{1}{2}\big(\alpha M_{s}^{\prime}(\alpha)+M_{s}^{\prime\prime}(\alpha)\big)$. Let $\alpha_{0}$ be the unique $\alpha>0$ such that $M_{s}^{\prime}(\alpha)=0$ and let $\alpha_{1}<\alpha_{2}$ be such that $M_{s}(\alpha_{1})=M_{s}(\alpha_{2})=\delta$. We can then easily plot the variations of $M_{s}$:

Proof . We already proved in Corollary A.1 that $\beta_{*}(\lambda)<\lambda/\alpha_{\rm min}$. For all $0<\beta<\lambda/\alpha_{\rm min}$, we have by Lemma A.6

Let $\beta_{0}=\beta_{0}(\lambda_{\rm min},\delta,s)>0$ such that for all $\beta\in(0,\beta_{0})$, $2\Phi(-\alpha)\leq\frac{1}{2}(\delta-s)$. For all $\beta\in(0,\beta_{0})$ we have then

Let $\beta_{\rm min}=\min(\frac{\sigma(\delta-s)}{2\delta},\beta_{0})$: for all $\beta\in(0,\beta_{\rm min})$, $\Psi_{\lambda}^{\prime}(\beta)>0$. By concavity we conclude that $\beta_{*}\geq\beta_{\rm min}$. $\square$

Proof . By (28) we have for all $\beta,\tau>0$

Proof . The inequality (39) simply follows from the previous lemma and from the fact that

by Lemma A.2. Let us prove (40). By Lemma A.7, we have

which proves (40). To prove (41) we use the optimality condition at $\beta_{*}$:

Combining this inequality with (42) leads to (41). $\square$

Proof . Let $(\beta_{*},\tau_{*})$ be the unique optimal couple and recall $\alpha_{*}=\lambda/\beta_{*}$. We distinguish 3 cases:

Case 1: $\alpha_{*}\geq\alpha_{0}$. In that case $\frac{1}{2}M_{s}^{\prime\prime}(\alpha_{*})\leq M_{s}(\alpha_{0})<\delta$. The inequality (41) gives

which gives $\tau_{*}(\beta_{*})\leq\frac{\beta_{\rm max}}{\delta-M_{s}(\alpha_{0})}$.

Case 2: $\alpha_{*}\in[(\alpha_{1}+\alpha_{0})/2,\alpha_{0}]$. In that case $\delta-M_{s}(\alpha_{*})\geq c>0$, for some constant $c=c(\delta,s)>0$. Now, by (39)

Case 3: $\alpha_{*}<(\alpha_{1}+\alpha_{0})/2$. In that case $M_{s}^{\prime}(\alpha_{*})\leq-c$, for some constant $c=c(\delta,s)>0$. Consequently by (40) we get

A.3 Dependency in λ\lambda

The mapping $\lambda\mapsto\tau_{*}(\lambda)$ is $\mathcal{C}^{\infty}$ and $M$-Lipschitz on $[\lambda_{\rm min},\lambda_{\rm max}]$, for some constant $M(\Omega)>0$.

Proof . The first point has already been by Proposition A.1. $\lambda\mapsto\tau_{*}(\lambda)$ is the composition of the mappings $\lambda\mapsto\alpha_{*}(\lambda)$ and $\alpha\mapsto\tau_{*}(\alpha)$, that are both $\mathcal{C}^{\infty}$ by Lemma A.5 and Proposition A.1. Compute the derivative:

Recall that $\alpha_{*}(\lambda)=\lambda/\beta_{*}(\lambda)$. Thus

Since by Theorem A.2, $\tau_{*}(\alpha_{*})\leq\tau_{\rm max}(\Omega)$ and $\alpha_{*}\leq\lambda_{\rm max}/\beta_{\rm min}(\Omega)$, the derivative of $\tau_{*}$ with respect to $\lambda$ is bounded on $[\lambda_{\rm min},\lambda_{\rm max}]$. $\square$

Appendix B Study of Gordon’s optimization problem for w^λ\widehat{w}_{\lambda}

The goal of this section is to prove that, with high probability, the minimizer of $L_{\lambda}$ is close to $\mathsf{w}_{\lambda}$ and that $L_{\lambda}$ is strongly convex around $\mathsf{w}_{\lambda}$.

Case 1: there exists a minimizer $w$ such that $\sqrt{\frac{\|w\|^{2}}{n}+\sigma^{2}}\ \frac{\|h\|}{\sqrt{n}}-\frac{1}{n}g^{{\sf T}}w+\frac{g^{\prime}\sigma}{\sqrt{n}}>0$. In that case, there exist a neighborhood $O_{w}$ of $w$ such that for all $w^{\prime}\in O_{w}$

Thus for all $w^{\prime}\in O_{w}$, $L_{\lambda}(w^{\prime})=\frac{1}{2}a(w^{\prime})^{2}+\frac{\lambda}{n}|w^{\prime}+\theta^{\star}|-\frac{\lambda}{n}|\theta^{\star}|$. Recall that the composition of a strictly convex function and a strictly increasing function is strictly convex. $L_{\lambda}$ is therefore strictly convex on $O_{w}$ because $a$ is strictly convex and remains strictly positive on $O_{w}$ and because $x>0\mapsto x^{2}$ is strictly increasing. $w$ is thus the only minimizer of $L_{\lambda}$.