The Squared-Error of Generalized LASSO: A Precise Analysis

Introduction

for some nonnegative penalty parameter $\lambda$.

2. Motivation

The LASSO problem can be viewed as a “merger" of two closely related problems, which have both recently attracted a lot of attention by the research community; the problems of noiseless CS and that of proximal denoising.

In the noiseless CS problem one wishes to recover $\mathbf{x}_{0}$ from the random linear measurements $\mathbf{y}=\mathbf{A}\mathbf{x}_{0}$. A common approach is solving the following convex optimization problem

A critical performance criteria for the problem (1.2) concerns the minimum number of measurements needed to guarantee successful recovery of $\mathbf{x}_{0}$ . Here, success means that $\mathbf{x}_{0}$ is the unique minimizer of (1.2), with high probability, over the realizations of the random matrix $\mathbf{A}$.

2.2 Proximal denoising

A closely related approach to estimate $\mathbf{x}_{0}$, which requires prior knowledge $f(\mathbf{x}_{0})$ about the signal of interest $\mathbf{x}_{0}$, is solving the constrained denoising problem:

2.3 The “merger" LASSO

The Generalized LASSO problem is naturally merging the problems of noiseless CS and proximal denoising. The compressed nature of measurements, poses the question of finding the minimum number of measurements required to recover $\mathbf{x}_{0}$ robustly, that is with error proportional to the noise level. When recovery is robust, it is of importance to be able to explicitly characterize how good the estimate is. In this direction, when $\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{m})$, a common measure of performance for the LASSO estimate $\mathbf{x}^{*}_{LASSO}$ is defined to be the normalized squared error (NSE) :

This is exactly the main topic of this work: proving precise bounds for the NSE of the Generalized LASSO problem.

3. Three Versions of the LASSO Problem

C-LASSO: Assumes a-priori knowledge of $f(\mathbf{x}_{0})$ and solves,

4. Relevant Literature

Precise characterization of the NSE of the LASSO is closely related to the precise performance analysis of noiseless CS and proximal denoising. To keep the discussion short, we defer most of the comments on the connections of our results to these problems to the main body of the paper. Table 1 provides a summary of the relevant literature and highlights the area of our contribution.

5. Contributions

This section summarizes our main contributions. In short, this work:

generalizes the results of on the constrained LASSO for arbitrary convex functions; proves that the worst case NSE is achieved when the noise level $\sigma\rightarrow 0$, and derives sharp bounds for it.

analyzes the regime in which stable estimation of $\mathbf{x}_{0}$ fails.

6. Motivating Examples

Before going into specific examples, it is instructive to consider the scenario where $f(\cdot)=0$. This reduces the problem to a regular least-squares estimation problem, the analysis of which is easy to perform. When $m<n$, the system is underdetermined, and one cannot expect $\mathbf{x}^{*}$ to be a good estimate. When $m\geq n$, the estimate can be given by $\mathbf{x}^{*}=(\mathbf{A}^{T}\mathbf{A})^{-1}\mathbf{A}^{T}\mathbf{y}$. In this case, the normalized mean-squared-error takes the form,

How does this result change when a nontrivial convex function $f(\cdot)$ is introduced?

Let $m>6dr$. Denote the LASSO estimate by $\mathbf{X}_{c}^{*}$ and use $\|\cdot\|_{F}$ for the Frobenius norm of a matrix. Then,

Note how (1.9)-(1.11) are similar in nature to (1.8).

Our Approach

A key idea behind our approach is using the linearization of the convex structure inducing function $f(\cdot)$ around the vector of interest $\mathbf{x}_{0}$ :

$\partial f(\mathbf{x}_{0})$ denotes the subdifferential of $f(\cdot)$ at $\mathbf{x}_{0}$ and is always a compact and convex set . Throughout, we assume that $\mathbf{x}_{0}$ is not a minimizer of $f(\cdot)$, hence, $\partial f(\mathbf{x}_{0})$ does not contain the origin. From convexity of $f(\cdot)$, $f(\mathbf{x})\geq\hat{f}(\mathbf{x})$, for all $\mathbf{x}$. What is more, when $\|\mathbf{x}-\mathbf{x}_{0}\|$ is sufficiently small, then $\hat{f}(\mathbf{x})\approx f(\mathbf{x})$. We substitute $f(\cdot)$ in (2.1) by its first-order approximation ${\hat{f}}(\cdot)$, to get a corresponding “Approximated LASSO" problem. To write the approximated problem in an easy-to-work-with format, recall that $\mathbf{y}=\mathbf{A}\mathbf{x}_{0}+\mathbf{z}=\mathbf{A}\mathbf{x}_{0}+\sigma\mathbf{v}$, for $\mathbf{v}\sim\mathcal{N}(0,\mathbf{I}_{m})$ and change the optimization variable from $\mathbf{x}$ to $\mathbf{w}=\mathbf{x}-\mathbf{x}_{0}$:

2. Importance of σ→0→𝜎0\sigma\rightarrow 0

3. Gordon’s Lemma

Perhaps the most important technical ingredient of the analysis presented in this work is a lemma proved by Gordon in . Gordon’s Lemma establishes a very useful (probabilistic) inequality for Gaussian processes.

It is worth mentioning that the “escape through a mesh" lemma, which has been the backbone of the approach introduced by Stojnic (and subsequently refined in ) for computing an asymptotic upper bound to the minimum number of measurements required in the Noiseless CS problem, is a corollary of Lemma 2.1

For the purposes of our analysis, we require a slight modification of this lemma. To avoid technicalities at this stage, we defer its precise statement to Section 5.3. Here, it suffices to observe that the original Gordon’s Lemma 2.1 is (almost) directly applicable to the LASSO problem in (2.3). First, write $\|\mathbf{A}\mathbf{w}-\sigma\mathbf{v}\|=\max_{\|\mathbf{a}\|=1}{\mathbf{a}^{T}[\mathbf{A},-\mathbf{v}]\begin{bmatrix}\mathbf{w}\\ \sigma\end{bmatrix}}$ and take function $\psi(\cdot)$ in the lemma to be $\sup_{\mathbf{s}\in{\lambda}\partial f(\mathbf{x}_{0})}\mathbf{s}^{T}\mathbf{w}$. Then, the optimization problem in the left hand side of (2.4) takes the format of the LASSO problem in (2.3), except for the “distracting" factor $\|\mathbf{x}\|g$. A simple argument shows that this term can be discarded without affecting the essence of the probabilistic statement of Lemma 2.1. Details being postponed to the later sections (cf. Section 5), Corollary 2.1 below summarizes the result of applying Gordon’s Lemma to the LASSO problem.

Let $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m})$, $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{n})$ and $h\sim\mathcal{N}(0,1)$ be independent of each other. Define the following optimization problem:

Corollary 2.1 establishes a probabilistic connection between the LASSO problem and the minimization (2.5). In the next section, we argue that the latter is much easier to analyze than the former. Intuitively, the main reason is that instead of an $m\times n$ matrix, (2.5) only involves two vectors of sizes $m\times 1$ and $n\times 1$. Even more, those vectors have independent standard normal entries and are independent of each other, which greatly facilitates probabilistic statements about the value of $\hat{\mathcal{L}}(\mathbf{g},\mathbf{h})$. Due to its central role in our analysis, we often refer to problem (2.5) as “key optimization" or “lower key optimization". The term “lower" is attributed to the fact that analysis of (2.5) results in a probabilistic lower bound for the optimal cost of the LASSO problem.

4. Analyzing the Key Optimization

The maximin problem that appears in the objective function of the optimization above has a simple solution. It can be shown that

Let $\hat{\mathbf{w}}(\mathbf{g},\mathbf{h})$ be a minimizer of the problem in (2.5). If $\|\mathbf{g}\|>\text{{dist}}(\mathbf{h},{\lambda}\partial f(\mathbf{x}_{0}))$, then,

4.2 Probabilistic Analysis

Assume that $(1-\epsilon_{L})m\geq{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})\geq\epsilon_{L}m$ for some constant $\epsilon_{L}>0$. DefineObserve that the dependence of $\eta$ and $\gamma$ on ${\lambda}$, $m$ and $\partial f(\mathbf{x}_{0})$, is implicit in this definition. ,

Then, for any $\epsilon>0$, there exists a constant $c>0$ such that, for sufficiently large $m$, with probability $1-\exp(-cm)$,

Remark: In Lemma 2.3, the condition “$(1-\epsilon_{L})m\geq{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$” ensures that $\|\mathbf{g}\|>\text{{dist}}(\mathbf{h},{\lambda}\partial f(\mathbf{x}_{0}))$ (cf. Lemma 2.2) with high probability over the realizations of $\mathbf{g}$ and $\mathbf{h}$.

5. Connecting back to the LASSO: The “Predictive Power of Gordon’s Lemma”

Let us recap the last few steps of our approach. Application of Gordon’s Lemma to the approximated LASSO problem in (2.3) introduced the simpler lower key optimization (2.5). Without much effort, we found in Lemma 2.3 that its cost $\hat{\mathcal{L}}(\mathbf{g},\mathbf{h})$ and the normalized squared norm of its minimizer $\frac{\|\hat{\mathbf{w}}(\mathbf{g},\mathbf{h})\|^{2}}{\sigma^{2}}$ concentrate around $\sigma\eta$ and $\gamma$, respectively. This brings the following question:

Assume $(1-\epsilon_{L})m\geq{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})\geq\epsilon_{L}m$ for some constant $\epsilon_{L}>0$ and $m$ is sufficiently large. Then, for any $\epsilon>0$, there exists a constant $c>0$ such that, with probability $1-\exp(-cm)$,

But is that all? A major part of our technical analysis in the remainder of this work involves showing that the connection between the LASSO problem and the simple optimization (2.5) is much deeper than Lemma 2.4 predicts. In short, under certain conditions on ${\lambda}$ and $m$ (similar in nature to those involved in the assumption of Lemma 2.4), we prove that the followings are true:

6. Synopsis of the Technical Framework

We highlight the main steps of the technical framework.

7. Gaussian Squared Distance and Related Quantities

The Gaussian squared distance to the ${\lambda}$-scaled set of subdifferential of $f(\cdot)$ at $\mathbf{x}_{0}$,

Let $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{n})$. Then, define,

Suppose $\partial f(\mathbf{x}_{0})$ is nonempty and does not contain the origin. Then,

${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ is a strictly convex function of ${\lambda}\geq 0$, and is differentiable for ${\lambda}>0$.

$\frac{\partial{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})}{\partial{\lambda}}=-\frac{2}{{\lambda}}{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})$.

Main Results

This section provides the formal statements of our main results. A more elaborate discussion follows in Section 4.

Before stating our results, we repeat our basic assumptions on the model of the LASSO problem. Recall the definitions of the three versions of the LASSO problem as given in (1.5), (1.6) and (1.7). Therein, assume:

$\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{m})$,

$\partial f(\mathbf{x}_{0})$ does not contain the origin.

2. C-LASSO

Furthermore, there exists a deterministic number $\sigma_{0}>0$ (i.e. independent of $\mathbf{A},\mathbf{v}$) such that, if $\sigma\leq\sigma_{0}$, with the same probability,

Suppose $m>\min_{{\lambda}\geq 0}{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$. Define ${\mathcal{R}}_{\text{ON}}$ as follows,

Remark: Section 8 fully characterizes ${\mathcal{R}}_{\text{ON}}$ and shows that it is an open interval.

Assume there exists a constant $\epsilon_{L}>0$ such that $(1-\epsilon_{L})m\geq\max\{{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda}),$ ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})+{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})\}$ and ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})\geq\epsilon_{L}m$. Further, assume that $m$ is sufficiently large. Then, for any $\epsilon>0$, there exists a constant $C=C(\epsilon,\epsilon_{L})>0$ and a deterministic number $\sigma_{0}>0$ (i.e. independent of $\mathbf{A},\mathbf{v}$) such that, whenever $\sigma\leq\sigma_{0}$, with probability $1-\exp(-C\min\{m,\frac{m^{2}}{n}\})$,

For any ${\lambda}\in{\mathcal{R}}_{\text{ON}}$, define

Assume $(1-\epsilon_{L})m\geq\min_{{\lambda}\geq 0}{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})\geq\epsilon_{L}m$ for a constant $\epsilon_{L}>0$ and $m$ is sufficiently large. For any value of the penalty parameter $\tau>0$, we claim that, the expression,

5. Converse Results

6. Remarks

A detailed discussion of the results follows in Section 4. Before this, the following remarks are in place.

$\bullet~{}~{}$ Known results in the noiseless CS problem (1.2) quantify the minimum number of measurements required for successful recovery of the signal of interest. Our Theorems 3.1 and 3.2 hold in the regime where this minimum number of measurements required grows proportional to the actual number of measurements $m$. As Theorem 3.4 shows, when $m$ is less than the minimum number of measurements required, then the LASSO programs fails to stably estimate $\mathbf{x}_{0}$.

$\bullet~{}~{}$ In Theorem 3.2, the exponent in the probability expression grows as $\min\{m,\frac{m^{2}}{n}\}$. This implies that, we require $m$ to grow at least linearly in $\sqrt{n}$.

The optimal penalty parameter $\lambda_{\text{best}}$ that minimizes the NSE is in ${\mathcal{R}}_{\text{ON}}$.

7. Paper Organization

Discussion of the Results

This section contains an extended discussion on the results of this work. We elaborate on their interpretation and implications.

Next, we identify three important values of the penalty parameter ${\lambda}$, needed to describe the distinct regions of operation of the estimator.

$\lambda_{\text{best}}$ : We show that $\lambda_{\text{best}}$ is optimal in the sense that the NSE is minimized for this particular choice of the penalty parameter. This also explains the term “best" we associate with it.

$\lambda_{{\max}}$ : Over ${\lambda}\geq\lambda_{\text{best}}$, the equation $m={\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ has a unique solution. We denote this solution by $\lambda_{{\max}}$. For values of ${\lambda}$ larger than $\lambda_{{\max}}$, we have $m\leq{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$.

$\lambda_{\text{crit}}$ : Over $0\leq{\lambda}\leq\lambda_{\text{best}}$, if $m\leq n$, the equation $m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})={\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})$ has a unique solution which we denote $\lambda_{\text{crit}}$. Otherwise, it has no solution and $\lambda_{\text{crit}}:=0$.

See Figure 4 for an illustration of the definitions above and Section 8 for the detailed proofs of the statements.

2.2 Characterizing the NSE in each Region

which is the standard approach to solving the noiseless linear inverse problems (recall (1.2)). We prove that this reduction is indeed true for values of ${\lambda}$ sufficiently small (see Lemma 9.2), while our empirical observations suggest that the claim is valid for all ${\lambda}\in{\mathcal{R}}_{\text{OFF}}$. Proving the validity of the claim would show that when $\sigma\rightarrow 0$, the NSE is $\frac{{\mathbf{D}}_{f}(\mathbf{x}_{0},\lambda_{\text{crit}})}{m-{\mathbf{D}}_{f}(\mathbf{x}_{0},\lambda_{\text{crit}})}$, for all ${\lambda}\in{\mathcal{R}}_{\text{OFF}}$. Interestingly, this would also give the NSE formula for the particularly interesting problem (• ‣ 4.2.2). Simulation results in Section 13 validate the claim.

${\mathcal{R}}_{\text{ON}}$: Begin with observing that ${\mathcal{R}}_{\text{ON}}$ is a nonempty and open interval. In particular, $\lambda_{\text{best}}\in{\mathcal{R}}_{\text{ON}}$ since $m>{\mathbf{D}}_{f}(\mathbf{x}_{0},\lambda_{\text{best}})$. We prove that for all ${\lambda}\in{\mathcal{R}}_{\text{ON}}$ and $\sigma$ is sufficiently small,

Also, empirical observations suggest that 4.2 holds for arbitrary $\sigma$ when $\approx$ replaced with $\lesssim$. Finally, we should note that the NSE formula $\frac{{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})}{m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})}$ is a convex function of ${\lambda}$ over ${\mathcal{R}}_{\text{ON}}$.

${\mathcal{R}}_{\infty}$: Empirically, we observe that the stable recovery of $\mathbf{x}_{0}$ is not possible for ${\lambda}\in{\mathcal{R}}_{\infty}$.

2.3 Optimal Tuning of the Penalty Parameter

$\lim_{{\lambda}\rightarrow\lambda_{{\max}}}{\text{map}}({\lambda})=\infty$,

Section 11 proves these properties and more, and contains a short technical discussion that motivates the proposed mapping function.

3.2 Proposed Formula

3.3 A rule of thumb for the optimal penalty parameter

4. Closed Form Calculations of the Formulae

draw a vector $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{n})$,

return the solution of the convex program $\min_{\mathbf{s}\in\partial f(\mathbf{x}_{0})}{\|\mathbf{h}-{\lambda}\mathbf{s}\|^{2}}$.

Summing up, our proposed formulae for the NSE of the LASSO problems can be effectively calculated, either analytically or numerically.

5. Translating the Results

Multiplying the objective with $\sqrt{m}$, we obtain,

Observe that, $\sqrt{m}\mathbf{A}^{\prime}$ is now statistically identical to $\mathbf{A}$. Hence, Theorem 3.2 is applicable under the mapping $\sigma\leftarrow\sqrt{m}\sigma^{\prime}$ and ${\lambda}\leftarrow\sqrt{m}{\lambda}^{\prime}$. Consequently, the NSE formula for the new setting for $\sqrt{m}{\lambda}^{\prime}\in{\mathcal{R}}_{\text{ON}}$ can be given as,

In general, reducing the signal power $\|\mathbf{A}\mathbf{x}_{0}\|^{2}$ by a factor of $m$, amplifies the proposed NSE upper bound by $m$ times and the penalty parameters should be mapped as $\tau\longleftrightarrow m\tau^{\prime}$ and ${\lambda}\longleftrightarrow\sqrt{m}{\lambda}^{\prime}$.

Applying Gordon’s Lemma

First, we introduce the basic notation that is used throughout the technical analysis of our results. Some additional notation, specific to the subject of each particular section is introduced later therein. To make explicit the variance of the noise vector $\mathbf{z}$, we denote $\mathbf{z}=\sigma\mathbf{v}$, where $\mathbf{v}\sim\mathcal{N}(0,\mathbf{I}_{m})$. Also, we reserve the variables $\mathbf{h}$ and $\mathbf{g}$ to denote i.i.d. Gaussian vectors in $\mathbf{R}^{n}$ and $\mathbf{R}^{m}$, respectively. In similar flavor, reserve the variable $\mathbf{s}$ to describe the subgradients of $f$ at $\mathbf{x}_{0}$. Finally, the Euclidean unit ball and unit sphere are respectively denoted as

For each candidate solution $\mathbf{x}$ of the LASSO algorithm, denote $\mathbf{w}=\mathbf{x}-\mathbf{x}_{0}$. Solving for $\mathbf{w}$ is clearly equivalent to solving for $\mathbf{x}$, but simplifies considerably the presentation of the analysis. Under this notation, $\|\mathbf{y}-\mathbf{A}\mathbf{x}\|=\|\mathbf{A}\mathbf{w}-\sigma\mathbf{v}\|.$ Furthermore, it is convenient to subtract the constant factor ${\lambda}f(\mathbf{x}_{0})$ from the objective function of the LASSO problem and their approximations. In this direction, define the following “perturbation" functions:

2. The Approximate LASSO Problem

Similarly, the approximated C-LASSO writes

3. Technical Tool: Gordon’s Lemma

As already noted the most important technical ingredient underlying our analysis is a Lemma proved by Gordon in ; recall Lemma 2.1 in Section 2. In fact, Gordon’s key Lemma 2.1 is a Corollary of a more general theorem which establishes a probabilistic comparison between two centered Gaussian processes. The theorem was proved by Gordon in and is stated below for completeness.

Let $\left\{X_{ij}\right\}$ and $\left\{Y_{ij}\right\}$, $1\leq i\leq n$, $1\leq j\leq m$, be two centered Gaussian processes which satisfy the following inequalities for all choices of indices

for all choices of $\lambda_{ij}\in\mathbf{R}$.

Application of Gordon’s Theorem 5.1 to specific Gaussian processes results in Gordon’s Lemma 2.1 . In this work, we require a slightly modified version of this lemma, namely Lemma 5.1. The key idea is of course the same as in the original lemma, but the statement is modified to fit the setup of the current paper.

The proof of Lemma 5.1 closely parallels the proof of Lemma 5.1 in . We defer the proof to Section C in the Appendix.

4. Simplifying the LASSO objective through Gordon’s Lemma

Section 2.6 introduced the technical framework. Key feature in this framework is the application of Gordon’s Lemma. In particular, we apply Gordon’s Lemma three times: once each for the purposes of the lower bound, the upper bound and the deviation analysis. Each application results in a corresponding simplified problem, which we call “key optimization". The analysis is carried out for that latter one as opposed to the original and more complex LASSO problem. In this Section, we show the details of applying Gordon’s Lemma and we identify the corresponding key optimizations. Later, in Section 6, we focus on the approximate LASSO problem and we show that in that case, the key optimizations are amenable to detailed analysis.

where $p:\mathbf{R}^{n}\rightarrow\mathbf{R}\cup\infty$ is a proper convex function . Choose the penalty function $p(\cdot)$ in the generic formulation (5.7) accordingly to end up with (5.3), (5.4), (5.5) or (5.6). To retrieve (5.4) and (5.6), choose $p(\mathbf{w})$ as the indicator function of the sets $\left\{\mathbf{w}|f_{p}(\mathbf{w})\leq 0\right\}$ and $\left\{\mathbf{w}|\hat{f}_{p}(\mathbf{w})\leq 0\right\}$ .

The following corollary is a direct application of Lemma 5.1 to $\mathcal{F}(\mathbf{A},\mathbf{v})$ in (5.7).

Let $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m})$, $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{n})$ and $h\sim\mathcal{N}(0,1)$ and assume all $\mathbf{g},\mathbf{h},h$ are independently generated. Let

4.2 Upper Bound

Similar to the lower bound derived in the previous section, we derive an upper bound for $\mathcal{F}(\mathbf{A},\mathbf{v})$. For this, we need to apply Gordon’s Lemma to $-\mathcal{F}(\mathbf{A},\mathbf{v})$ and use the dual formulation of it. Lemma D in the Appendix shows that the dual of the minimization in (5.7) can be written as

Lemma 5.1 requires the set over which maximization is performed to be compact. We thus apply Lemma 5.1 to the restricted problem,

Notice, that this still gives a valid lower bound to $-\mathcal{F}(\mathbf{A},\mathbf{v})$ since the optimal cost of this latter problem is no larger than $-\mathcal{F}(\mathbf{A},\mathbf{v})$. In Section 6, we will choose $C_{up}$ so that the resulting lower bound is as tight as possible.

Let $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m})$, $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{n})$ and $h\sim\mathcal{N}(0,1)$ and assume all $\mathbf{g},\mathbf{h},h$ are independently generated. Let,

4.3 Deviation Analysis

Of interest in the deviation analysis of the LASSO problem (cf. Step 4 in Section 2.6) is the analysis of a restricted version of the $LASSO$ problem, namely

$\delta_{dev}>0$ is any arbitrary small constant and $C_{dev}>0$ a constant that will be chosen carefully for the purpose of the deviation analysis . We establish a high probability lower bound for (5.11). As usual, we apply Lemma 5.1 to our setup, to conclude the following.

Let $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m})$, $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{n})$ and $h\sim\mathcal{N}(0,1)$ and assume all $\mathbf{g},\mathbf{h},h$ are independently generated. Let

Follows from Lemma 5.1 following exactly the same steps as in the proof of Corollary 5.1. ∎

4.4 Summary

We summarize the results of Corollaries 5.1, 5.2 and 5.3 in Lemma 5.2. Adding to a simple summary, we perform a further simplification of the corresponding statements. In particular, we discard the “distracting" term $\sigma h$ in Corollaries 5.1 and 5.3, as well as the term $\min_{0\leq\alpha\leq 1}\alpha\sigma h$ in Corollary 5.2. Recall the definitions of the key optimizations $\mathcal{{L}}$, $\mathcal{{U}}$ and $\mathcal{{L}}_{dev}$ in (5.8), (5.10) and (5.12).

Let $\mathbf{g}\sim\mathcal{N}(0,{\bf{I}}_{m})$ and $\mathbf{h}\sim\mathcal{N}(0,{\bf{I}}_{n})$ be independently generated. Then, for any positive constant $\epsilon>0$, the following are true:

For $h\sim\mathcal{N}(0,1)$ and all $\epsilon>0$,

Combine this with Corollary 5.1 to conclude with the first statement of Lemma 5.2. The proof of the third statement of the Lemma follows the exact same steps applied this time to Corollary 5.3. For the second statement write,

and use (5.13) as above. To conclude, combine with the statement of Corollary 5.2. ∎

After Gordon’s Lemma: Analyzing the Key Optimizations

to correspond to (5.6) and (5.5), when setting $\mathcal{C}=\text{cone}(\partial f(\mathbf{x}_{0}))$ and $\mathcal{C}={\lambda}\partial f(\mathbf{x}_{0})$, respectively.

2. Some Notation

The distance of $\mathbf{x}$ to the set $\mathcal{C}$ can then be written as,

Now, let $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{n})$. The following quantities are of central interest throughout the paper:

On the same lines, define ${\mathbf{P}}_{f}(\mathbf{x}_{0},{\lambda}):=\mathbf{P}({\lambda}\partial f(\mathbf{x}_{0}))$.

3. Analysis

We perform a detailed analysis of the three key optimization problems $\hat{\mathcal{L}}$, $\hat{\mathcal{U}}$ and $\hat{\mathcal{L}}_{dev}$. For each one of them we summarize the results of the analysis in Lemmas 6.1, 6.2 and 6.3 below. Each Lemma includes three statements. In the first, we reduce the corresponding key optimization problem to a scalar optimization. Next, we compute the optimal value of this optimization in a deterministic setup. We convert this into a probabilistic statement in the last step, which is directly applicable in Lemma 5.2. Eventhough, we are eventually interested only in this last probabilistic statement, we have decided to include all three steps in the statement of the Lemmas in order to provide some further intuition into how they nicely build up to the desired result. All proofs of the lemmas are deferred to Section E in the Appendix.

Let $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m})$ and $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{n})$ and

Denote $\hat{\mathbf{w}}_{low}(\mathbf{g},\mathbf{h})$ its optimal value. The following are true:

Scalarization: $\hat{\mathcal{L}}(\mathbf{g},\mathbf{h})=\min_{\alpha\geq 0}\left\{\sqrt{\alpha^{2}+\sigma^{2}}\|\mathbf{g}\|-\alpha\cdot\text{{dist}}(\mathbf{h},\mathcal{C})\right\}$

Deterministic result: If $\|\mathbf{g}\|^{2}>\text{{dist}}(\mathbf{h},\mathcal{C})^{2},$ then,

Probabilistic result: Assume that $m\geq{\mathbf{D}}(\mathcal{C})+\epsilon_{L}m$ for some $\epsilon_{L}\geq 0$. Then, for any $\epsilon>0$, there exist $c_{1},c_{2}>0$ such that, for sufficiently large $m$,

3.2 Upper Key Optimization

Let $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m})$, $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{n})$ and

Scalarization: $\hat{\mathcal{U}}(\mathbf{g},\mathbf{h})=-\min_{0\leq\alpha\leq 1}\left\{-\alpha\cdot\sqrt{C_{up}^{2}+\sigma^{2}}~{}\|\mathbf{g}\|+C_{up}\text{{dist}}(\alpha\mathbf{h},\mathcal{C})\right\}.$

Deterministic result: If $\mathbf{h}\notin\mathcal{C}$ and

Probabilistic result: Assume $m\geq\max\left\{{\mathbf{D}}(\mathcal{C}),{\mathbf{D}}(\mathcal{C})+{\mathbf{C}}(\mathcal{C})\right\}+\epsilon_{L}m$ for some $\epsilon_{L}>0$. Set

Then, for any $\epsilon>0$, there exist $c_{1},c_{2}>0$ such that for sufficiently large ${\mathbf{D}}(\mathcal{C})$,

where $\gamma(m,n)=m$ if $\mathcal{C}$ is a cone and $\gamma(m,n)=\min\left\{m,\frac{m^{2}}{n}\right\}$ otherwise.

3.3 Deviation Key Optimization

Let $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m})$ and $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{n})$ and

$\delta_{dev}>0$ is any arbitrary small constant and $C_{dev}>0$. The following are true:

Scalarization: $\hat{\mathcal{L}}_{dev}(\mathbf{g},\mathbf{h})=\min_{\alpha\in S_{dev}}\left\{\sqrt{\alpha^{2}+\sigma^{2}}\|\mathbf{g}\|-\alpha\cdot\text{{dist}}(\mathbf{h},\mathcal{C})\right\}.$

Probabilistic result: Assume $(1-\epsilon_{L})m>{\mathbf{D}}(\mathcal{C})>\epsilon_{L}m$, for some $\epsilon_{0}>0$ and set

Then, for all $\delta_{dev}>0$ there exists $t>0$ and $c_{1},c_{2}>0$ such that,

4. Going Back: From the Key Optimizations to the Squared Error of the LASSO

Application of Gordon’s Lemma to $\hat{{\mathcal{F}}}(\mathbf{A},\mathbf{v})$ introduced the three key optimizations in Lemma 5.2. Next, in Lemmas 6.1, 6.2 and 6.3 we carried out the analysis of those problems. Here, we combine the results of the four Lemmas mentioned above in order to evaluate $\hat{{\mathcal{F}}}(\mathbf{A},\mathbf{v})$ and to compute an exact value for the norm of its optimizer $\hat{\mathbf{w}}(\mathbf{A},\mathbf{v})$. Lemma 6.4 below formally states the results of the analysis and the proof of it follows.

Assume $m\geq\max\left\{{\mathbf{D}}(\mathcal{C}),{\mathbf{D}}(\mathcal{C})+{\mathbf{C}}(\mathcal{C})\right\}+\epsilon_{L}m$ and ${\mathbf{D}}(\mathcal{C})\geq\epsilon_{L}m$ for some $\epsilon_{L}>0$. Also, assume $m$ is sufficiently large and let $\gamma(m,n)=m$ if $\mathcal{C}$ is a cone and $\min\{m,\frac{m^{2}}{n}\}$ else. Then, the following statements are true.

For any $\epsilon>0$, there exist constants $c_{1},c_{2}>0$ such that

with probability $1-c_{1}\exp(-c_{2}\gamma(m,n))$.

For any $\delta_{dev}>0$ and all $\mathbf{w}\in{\mathcal{C}}$ satisfying

there exists constant $t(\delta_{dev})>0$ and $c_{1},c_{2}>0$ such that

with probability $1-c_{1}\exp(-c_{2}\gamma(m,n))$.

For any $\delta>0$, there exist constants $c_{1},c_{2}>0$ such that

with probability $1-c_{1}\exp(-c_{2}\gamma(m,n))$.

We prove each one of the three statements of Theorem 6.4 sequentially. Assume the regime where $m\geq\max\left\{{\mathbf{D}}(\mathcal{C}),{\mathbf{D}}(\mathcal{C})+{\mathbf{C}}(\mathcal{C})\right\}+\epsilon_{L}m$ and ${\mathbf{D}}(\mathcal{C})\geq\epsilon_{L}m$ for some $\epsilon_{L}>0$ and also $m$ is sufficiently large.

1. Proof of (6.11): Consider any $\epsilon^{\prime}>0$. First, we establish a high probability lower bound for $\hat{{\mathcal{F}}}(\mathbf{A},\mathbf{v})$. From Lemma 6.1,

with probability $1-\exp(-\mathcal{O}\left(m\right)).$ Combine this with the first statement of Lemma 5.2 to conclude that

Similarly, for a high probability upper bound for $\hat{{\mathcal{F}}}(\mathbf{A},\mathbf{v})$ we have from Lemma 6.2, that

with probability $1-\exp\left(-\mathcal{O}\left(\gamma(m,n)\right)\right)$. Combine this with the second statement of Lemma 5.2 to conclude that

with the same probability. To conclude the proof of (6.11) fix any positive constant $\epsilon>0$, and observe that by choosing $\epsilon^{\prime}=\epsilon\frac{\sqrt{\epsilon_{L}}}{1+\sqrt{\epsilon_{L}}}$ in (6.15) and (6.16) we ensure that $\epsilon^{\prime}\left(1+\frac{\sqrt{m}}{\sqrt{m-{\mathbf{D}}(\mathcal{C})}}\right)\leq\epsilon$. It then follows from (6.15) and (6.16) that there exist $c_{1},c_{2}>0$ such that

with probability $1-c_{1}\exp\left(-c_{2}{\gamma(m,n)}\right)$.

2. Proof of (6.13): Fix any $\delta_{dev}>0$. In accordance to its definition in previous sections define the set

Clearly, for all $\mathbf{w}$ such that $\|\mathbf{w}\|\in S_{dev}$ we have,

Combining this with the third statement of Lemma 5.2, it suffices for the proof of (6.13) to show that there exists constant $t(\delta_{dev})>0$ such that

with probability $1-\exp\left(-\mathcal{O}\left(m\right)\right)$.

To show (6.18), start from Lemma 6.3 which gives that here exists $t^{\prime}(\delta_{dev})>0$, such that

with probability $1-\exp(-\mathcal{O}\left(m\right)).$ Furthermore, from the first statement of Lemma 6.4,

with probability $1-\exp\left(-\mathcal{O}\left(\gamma(m,n)\right)\right)$. Finally, choose $t=\frac{t^{\prime}}{4}\sqrt{\epsilon_{L}}$ to ensure that

Combine (6.19), (6.20) and (6.21) to conclude that (6.18) indeed holds with the desired probability.

3. Proof of (6.14): The third statement of Lemma 6.4 is a simple consequence of its second statement. Fix any $\epsilon>0$. The proof is by contradiction. Assume that $\hat{\mathbf{w}}(\mathbf{A},\mathbf{v})$ does not satisfy (6.14). It then satisfies (6.12) for $\delta_{dev}=\epsilon$. Thus, it follows from the second statement of Lemma 6.4, that there exists $t(\epsilon)>0$ such that

with probability $1-\exp\left(-\mathcal{O}\left(\gamma(m,n)\right)\right)$. This is a contradiction and completes the proof.

The NSE of the C-LASSO

In this section, we prove the second statement of Theorem 3.1, namely (3.2). We restate the theorem here for ease of reference.

Recall the definition of the approximated C-LASSO problem in (5.6). As it has been argued previously, this is equivalent to the generic problem (6.2) with $\mathcal{C}=\text{cone}\{\partial f(\mathbf{x}_{0})\}$. Hence, to calculate its NSE we will simply apply the results we obtained throughout Section 6. We first start by mapping the generic formulation in Section 6 to the C-LASSO.

Let $\mathcal{C}=\text{cone}\{\partial f(\mathbf{x}_{0})\}$. Then,

The first statement follows by definition of the quantities involved. The second statement is a direct consequence of Moreau’s decomposition theorem (Fact A.1) applied on the closed and convex cone $\text{cone}\{\partial f(\mathbf{x}_{0})\}$. The last statement follows easily after taking expectation in both sides of the equality in the second statement. ∎

With this mapping, we can directly apply Lemma 6.4, where $\mathcal{C}$ is a cone, to conclude with the desired result. The following corollary summarizes the result.

2. Original C-LASSO Problem

In this section we prove (3.2). For the proof we rely on Corollary 7.1. First, we require the introduction of some useful concepts from convex analysis.

The tangent cone of $\mathcal{C}$ at $\mathbf{x}^{*}$ is defined as

where $Cl(\cdot)$ denotes the closure of a set. By definition, tangent cone $\mathcal{T}_{\mathcal{C}}(\mathbf{x}^{*})$ and feasible set $F_{\mathcal{C}}(\mathbf{x}^{*})$ should be close to each other around a small neighborhood of . The following proposition is a corollary of Proposition F.1 of and shows that the elements of tangent cone, that are close to the origin, can be uniformly approximated by the elements of the feasible set.

Let $\mathcal{C}$ be a closed convex set and $\mathbf{x}^{*}\in\mathcal{C}$. For any $\delta>0$, there exists $\epsilon>0$ such that

for all $\mathbf{u}\in\mathcal{T}_{\mathcal{C}}(\mathbf{x}^{*})$ with $\|\mathbf{u}\|\leq\epsilon$.

Assume $\mathcal{C}$ is the descent set of $f$ at $\mathbf{x}_{0}$, namely, $\mathcal{C}=\left\{\mathbf{x}~{}|~{}f(\mathbf{x})\leq f(\mathbf{x}_{0})\right\}$ for some convex function $f(\cdot)$. In this case, we commonly refer to $\mathcal{T}_{\mathcal{C}}(\mathbf{x}_{0})$ as the “tangent cone of $f(\cdot)$ at $\mathbf{x}_{0}$" and denote it by $\mathcal{T}_{f}(\mathbf{x}_{0})$. Under the condition that $\mathbf{x}_{0}$ is not a minimizer of $f(\cdot)$, the following lemma relates $\mathcal{T}_{f}(\mathbf{x}_{0})$ to the cone of the subdifferential.

2.2 Proof of Theorem 3.1: Small σ𝜎\sigma regime

We prove here the second part of Theorem 3.1, namely (3.2). For a proof of (3.1) see Section 10. For the purposes of the proof, we will use \mathcal{C}=\{\mathbf{x}\big{|}f(\mathbf{x})\leq f(\mathbf{x}_{0})\}. Recall that we denote the minimizers of the C-LASSO and approximated C-LASSO by $\mathbf{w}_{c}^{*}$ and $\hat{\mathbf{w}}_{c}$, respectively. Also, for convenience denote

Recalling the definition of the approximated C-LASSO problem in (5.6), we may write

where for the last equality we have used Lemma 7.2. Hence,

After Corollary 7.1, $\|\hat{\mathbf{w}}_{c}\|^{2}$ concentrates around $\sigma^{2}\eta_{c}$. We will argue that, in the small noise regime, we can translate our results to the original problem in a smooth way. Assume that the statements of Corollary 7.1, hold with high probability for some arbitrary $\epsilon_{1},\epsilon_{2}>0$. It suffices to prove that for any $\epsilon_{3}>0$ there exists $\sigma_{0}>0$ such that

for all $\sigma<\sigma_{0}$. To begin with, fix a $\delta>0$, the value of which is to be determined later in the proof. As an immediate implication of Proposition 7.1, there exists $\sigma_{0}$ such that

for all $\mathbf{w}\in\mathcal{T}_{\mathcal{C}}(\mathbf{x}_{0})$ satisfying $\|\mathbf{w}\|\leq C=C(\sigma_{0},\epsilon_{2}):=\sigma_{0}\sqrt{(1+\epsilon_{2})\eta_{c}}$.

Now, fix any $\sigma<\sigma_{0}$. We will make use of the fact that the following three events hold with high probability.

Using Corollary 7.1, with high probability $\hat{\mathbf{w}_{c}}$ satisfies,

$\mathbf{A}$ has independent standard normal entries. Hence, its spectral norm satisfies $\|\mathbf{A}\|_{2}\leq 2(\sqrt{n}+\sqrt{m})$ with probability $1-\exp(-\mathcal{O}\left(\max\{m,n\}\right))$, .

Using (6.13) of Lemma 6.4 with $\mathcal{C}=\text{cone}(\partial f(\mathbf{x}_{0}))$, there exists a constant $t=t(\epsilon_{3})$ so that for all $\mathbf{w}$ satisfying $|\frac{\|\mathbf{w}\|^{2}}{\sigma^{2}}-\eta_{c}|\geq\epsilon_{3}$, we have,

Consider the projection of $\hat{\mathbf{w}}_{c}$ on the set of feasible directions $F_{\mathcal{C}}(\mathbf{x}_{0})$,

First, we show that $\|\mathbf{A}\mathbf{p}(\hat{\mathbf{w}}_{c})-\sigma\mathbf{v}\|$ is not much larger than the objective of the approximated problem, namely $\hat{{\mathcal{F}}}_{c}(\mathbf{A},\mathbf{v})$. Indeed,

The first inequality is an application of the triangle inequality and the second one follows from (7.7). For the third inequality, we have used (7.1) and combined (7.4) with (7.5).

Next, we show that if (7.3) was not true then a suitable choice of $\delta$ would make $\|\mathbf{A}\mathbf{p}(\hat{\mathbf{w}}_{c})-\sigma\mathbf{v}\|$ much larger than the optimal $\hat{{\mathcal{F}}}_{c}(\mathbf{A},\mathbf{v})$ than (7.2.2) allows. Therefore, concluding a desired contradiction. More precisely, assuming (7.3) does not hold, we have

The first inequality above follows since $\mathbf{p}(\hat{\mathbf{w}}_{c})\in F_{\mathcal{C}}(\mathbf{x}_{0})$ and from the optimality of $\mathbf{w}_{c}^{*}\in F_{\mathcal{C}}(\mathbf{x}_{0})$. To get the second inequality, recall that (7.3) is not true. Also, from (7.2), $\max_{\mathbf{s}\in\text{cone}(\partial f(\mathbf{x}_{0}))}\mathbf{s}^{T}\mathbf{w}^{*}_{c}=\max_{\mathbf{s}\in(\mathcal{T}(\mathbf{x}_{0}))^{\circ}}\mathbf{s}^{T}\mathbf{w}^{*}_{c}=0$. Combine these and invoke (7.6).

To conclude, choose $\sigma_{0}$ sufficiently small to ensure $\delta<\frac{t(\epsilon_{3})\sqrt{m}}{2(\sqrt{m}+\sqrt{n})\sqrt{(1+\epsilon_{2})\eta_{c}}}$ and combine (7.2.2) and (7.2.2) to obtain the following contradiction.

$\sigma_{0}$ is a deterministic number that is a function of $m,n,f,\mathbf{x}_{0},\epsilon_{3}$.

${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})+2{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})+{\mathbf{P}}_{f}(\mathbf{x}_{0},{\lambda})=n$.

${\mathbf{D}}_{f}(\mathbf{x}_{0},0)=n$ , ${\mathbf{P}}_{f}(\mathbf{x}_{0},0)=0$, and ${\mathbf{C}}_{f}(\mathbf{x}_{0},0)=0$.

$\lim_{{\lambda}\rightarrow\infty}{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})=\infty,~{}\lim_{{\lambda}\rightarrow\infty}{\mathbf{P}}_{f}(\mathbf{x}_{0},{\lambda})=\infty,\text{ and }\lim_{{\lambda}\rightarrow\infty}{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})=-\infty.$

${\mathbf{P}}_{f}(\mathbf{x}_{0},{\lambda})$, ${\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})$ and ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ are all continuous functions of ${\lambda}\geq 0$.

${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ is strictly convex and attains its minimum at a unique point. Denote $\lambda_{\text{best}}$ the unique minimizer of ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$.

${\mathbf{P}}_{f}(\mathbf{x}_{0},{\lambda})$ is an increasing function for ${\lambda}\geq 0$.

${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ is differentiable for ${\lambda}>0$. For ${\lambda}>0$,

For ${\lambda}=0$, interpret $\frac{d{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})}{d{\lambda}}$ as a right derivative.

${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})+{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})$ is strictly decreasing for ${\lambda}\in[0,\lambda_{\text{best}}]$.

Some of the statements in Lemma 8.1 are easy to prove, while others require more work. Statements $5$ and $7$ have been recently proved in . We defer the proofs of all statements to Appendix G.

2. Key Values of the Penalty Parameter

We define three key values of the regularizer ${\lambda}$. The main work is devoted to showing that those definitions are well established.

The second key parameter $\lambda_{{\max}}$ is defined as the unique ${\lambda}\geq\lambda_{\text{best}}$ that satisfies ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})=m$. We formally repeat this definition in the following Lemma.

Suppose ${\mathbf{D}}_{f}(\mathbf{x}_{0},\lambda_{\text{best}})<m$ and consider the following equation over ${\lambda}\geq\lambda_{\text{best}}$:

Equation (8.1) has a unique solution, which we denote $\lambda_{{\max}}$.

We make use of Lemma 8.1. First, we show that equation (8.1) has at most one solution: ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ is a strictly convex function of ${\lambda}\geq 0$ and thus strictly increasing for ${\lambda}\geq\lambda_{\text{best}}$. Next, we show that (8.1) has at least one solution. From assumption, $\mathbf{D}(\mathbf{x}_{0},\lambda_{\text{best}})<m$. Also, $\lim_{{\lambda}\rightarrow\infty}\mathbf{D}(\mathbf{x}_{0},\lambda_{\text{best}})=\infty$. Furthermore, ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ is continuous in ${\lambda}$. Combining those facts and using the intermediate value theorem we conclude with the desired result. ∎

The third key parameter $\lambda_{\text{crit}}$ is defined to be the unique ${\lambda}\leq\lambda_{\text{best}}$ that satisfies $m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})={\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})$ when $m\leq n$ or to be 0 when $m>n$. We formally repeat this definition in the following Lemma.

Suppose $\mathbf{D}(\mathbf{x}_{0},\lambda_{\text{best}})<m$ and consider the following equation over $0\leq{\lambda}\leq\lambda_{\text{best}}$:

If $m\leq n$, then (8.2) has a unique solution, which we denote as $\lambda_{\text{crit}}$.

If $m>n$, then (8.2) has no solution. Then $\lambda_{\text{crit}}=0$.

We repeatedly make use of Lemma 8.1. For convenience define the function

for ${\lambda}\in[0,\lambda_{\text{best}})$. The function $g({\lambda})$ has the following properties over ${\lambda}\in[0,\lambda_{\text{best}}]$:

$g(\lambda_{\text{best}})={\mathbf{D}}_{f}(\mathbf{x}_{0},\lambda_{\text{best}})<m$.

If $m\leq n$, from the intermediate value Theorem it follows that (8.2) has at least one solution. This solution is unique since $g({\lambda})$ is strictly decreasing.

If $m>n$, since $g({\lambda})\leq n$ for all ${\lambda}\in[0,\lambda_{\text{best}}]$, it is clear that (8.2) has no solution. ∎

$\mathcal{R}_{OFF}=\left\{{\lambda}~{}|~{}0\leq{\lambda}\leq\lambda_{\text{crit}}\right\},$

$\mathcal{R}_{ON}=\left\{{\lambda}~{}|~{}\lambda_{\text{crit}}<{\lambda}<\lambda_{{\max}}\right\},$

$\mathcal{R}_{\infty}=\left\{{\lambda}~{}|~{}{\lambda}\geq\lambda_{{\max}}\right\}.$

Remark: The definition of ${\mathcal{R}}_{\text{ON}}$ in Definition 8.1 is consistent to the Definition in 3.1. In other words, $\lambda_{\text{crit}}\leq{\lambda}\leq\lambda_{{\max}}$ if and only if $m\geq\max\{{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda}),{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})+{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})\}$. This follows after combining Lemmas 8.2 and 8.3 with the Lemma 8.4 below.

$m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})\leq{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})$ for all ${\lambda}\in\mathcal{R}_{OFF}$ if $\lambda_{\text{crit}}\neq 0$.

$m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})>\max\{0,{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})\}$ for all ${\lambda}\in\mathcal{R}_{ON}$,

$m\leq{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ for all ${\lambda}\in\mathcal{R}_{\infty}$.

We prove the statements in the order they appear. We use Lemma 8.1 throughout.

1. The function ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})+{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})$ is strictly decreasing in $[0,\lambda_{\text{best}}]$. Thus, assuming $\lambda_{\text{crit}}\neq 0$, ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})+{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})\geq{\mathbf{D}}_{f}(\mathbf{x}_{0},\lambda_{\text{crit}})+{\mathbf{C}}_{f}(\mathbf{x}_{0},\lambda_{\text{crit}})=m$ for all ${\lambda}\in[0,\lambda_{\text{crit}}]$.

2. Since ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ is strictly convex, $m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ is strictly concave and has a unique maximum at $\lambda_{\text{best}}$. Therefore, for all ${\lambda}\in[\lambda_{\text{crit}},\lambda_{{\max}}]$,

Furthermore, ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})+{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})$ is strictly decreasing in $[0,\lambda_{\text{best}}]$. Thus, ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})+{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})<{\mathbf{D}}_{f}(\mathbf{x}_{0},\lambda_{\text{crit}})+{\mathbf{C}}_{f}(\mathbf{x}_{0},\lambda_{\text{crit}})\leq m$ for all ${\lambda}\in(\lambda_{\text{crit}},\lambda_{\text{best}}]$. For ${\lambda}\in[\lambda_{\text{best}},\lambda_{{\max}})$, we have $m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})>0\geq{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})$.

3. ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ is strictly convex. Hence, $m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ is strictly decreasing in $[\lambda_{\text{best}},\infty)$. This proves that $m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})\leq m-{\mathbf{D}}_{f}(\mathbf{x}_{0},\lambda_{{\max}})=0$ for all ${\lambda}\geq\lambda_{{\max}}$.

We split our analysis in three sections, one for each of the three regions ${\mathcal{R}}_{\text{OFF}}$, ${\mathcal{R}}_{\text{ON}}$ and ${\mathcal{R}}_{\infty}$. We start from ${\mathcal{R}}_{\text{ON}}$, for which the analysis is similar in nature to C-LASSO.

Let $m\geq\min_{{\lambda}\geq 0}{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ and assume there exists constant $\epsilon_{L}>0$ such that $(1-\epsilon_{L})m\geq\max\{{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda}),$ ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})+{\mathbf{C}}_{f}(\mathbf{x}_{0},{\lambda})\}$ and ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})\geq\epsilon_{L}m$. Further assume that $m$ is sufficiently large. Then, for any constants $\epsilon_{1},\epsilon_{2}>0$, there exist constants $c_{1},c_{2}>0$ such that with probability $1-c_{1}\exp(-c_{2}\min\{m,\frac{m^{2}}{n}\})$,

Next, we use Corollary 9.1 to prove Theorem 3.2. To do this, we will first relate $f(\cdot)$ and $\hat{f}(\cdot)$. The following result shows that, $f(\cdot)$ and $\hat{f}(\cdot)$ are close around a sufficiently small neighborhood of $\mathbf{x}_{0}$.

In particular, the subdifferential $\partial f(\mathbf{x})$ is nonempty.

Proposition 9.1 considers a fixed direction $\mathbf{v}$, and compares $f(\mathbf{x}_{0}+\epsilon\mathbf{v})$ and $\hat{f}(\mathbf{x}_{0}+\epsilon\mathbf{v})$. We will need a slightly stronger version which says $\hat{f}(\cdot)$ is a good approximation of $f(\cdot)$ at all directions simultaneously. The following proposition is a restatement of Lemma 2.1.1 of Chapter VI of .

for all $\sigma<\sigma_{0}$. To begin with, fix a $\delta>0$, the value of which is to be determined later in the proof. As an immediate implication of Proposition 9.2, there exists $\sigma_{0}$ such that

1.3 A Property of the NSE Formula

Theorem 3.2 shows that the asymptotic NSE formula in ${\mathcal{R}}_{\text{ON}}$ is $\frac{{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})}{m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})}$. The next lemma provides a useful property of this formula as a function of ${\lambda}$ on ${\mathcal{R}}_{\text{ON}}$.

$\frac{{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})}{m-{\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})}$ is a convex function of ${\lambda}$ over ${\mathcal{R}}_{\text{ON}}$.

From 8.1, ${\mathbf{D}}_{f}(\mathbf{x}_{0},{\lambda})$ is a strictly convex function of ${\lambda}$. Also, $\frac{x}{m-x}$ is an increasing function of $x$ over $0\leq x<m$ and its second derivative is $\frac{m}{(m-x)^{3}}$ which is strictly positive over ${\mathcal{R}}_{\text{ON}}$. Consequently, the asymptotic NSE formula is a composition of an increasing convex function with a convex function, and is thus itself convex. ∎

When $m\leq\alpha n$ for some constant $0<\alpha<1$, $\sqrt{n}-\sqrt{m}=\mathcal{O}\left(\sqrt{n}\right)$. Then, from standard concentration results (see ), with probability $1-\exp(-\mathcal{O}\left(n\right))$, minimum singular value $\sigma_{min}(\mathbf{A})$ of $\mathbf{A}$ satisfies

The inequality in (9.14) follows from Lipschitzness of $f(\cdot)$, while we use (9.13) to find (9.15). For the sake of contradiction, assume that $\|\mathbf{p}\|\neq 0$, then (9.15) reduces to $0>0$, clearly, a contradiction. ∎

Constrained-LASSO Analysis for Arbitrary σ𝜎\sigma

In Section 7 we proved the first part of Theorem 3.1, which refers to the case where $\sigma\rightarrow 0$. Here, we complete the proof of the Theorem by showing (3.1), which is to say that the worst case NSE of the C-LASSO problem is achieved as $\sigma\rightarrow 0$. In other words, we prove that our exact bounds for the small $\sigma$ regime upper bound the squared error, for arbitrary values of the noise variance. The analysis relies, again, on the proper application of Gordon’s Lemma.

We begin with describing some notation used throughout this section. First, we denote

Also, recall the definitions of the “perturbation" functions $f_{p}(\cdot)$ and $\hat{f}_{p}(\cdot)$ in (5.1) and (5.2). Finally, we will be making use of the following functions:

Using this notation, and denoting the optimal cost of the (original) C-LASSO (see (1.5)) as $\mathcal{F}_{c}^{*}(\mathbf{A},\mathbf{v})$, we write

2. Lower Key Optimization

As a first step in our proof, we apply Gordon’s Lemma to the original C-LASSO problem in (10.3). Recall, that application of Corollary 5.1 to the approximated problem resulted in the following key optimization:

Denote the minimizer of (10.4), as $\hat{\mathbf{w}}_{low}$. Using Corollary 5.1, the lower key optimization corresponding to the original C-LASSO has the following form:

For the proof of Lemma 10.1, we require the following result on the tangent cone of the feasible set of (10.5).

We need to characterize the feasible set $F_{\mathcal{C}}(\mathbf{w}^{*})$.

Now, assume $f(\mathbf{x}_{0}+\mathbf{w}^{*})=f(\mathbf{x}_{0})$. Then, F_{\mathcal{C}}(\mathbf{w}^{*})=\{\mathbf{u}\big{|}f(\mathbf{x}_{0}+\mathbf{w}^{*}+\mathbf{u})\leq f(\mathbf{x}_{0})=f(\mathbf{x}_{0}+\mathbf{w}^{*})\}=F_{\mathcal{C}^{\prime}}(\mathbf{x}_{0}+\mathbf{w}^{*}), where $F_{\mathcal{C}^{\prime}}(\mathbf{x}_{0}+\mathbf{w}^{*})$ denotes the set of feasible directions in $\mathcal{C}^{\prime}:=\{\mathbf{x}|f(\mathbf{x})\leq f(\mathbf{x}_{0}+\mathbf{w}^{*})\}$ at $\mathbf{x}_{0}+\mathbf{w}^{*}$. Thus, $\mathcal{T}_{\mathcal{C}}(\mathbf{w}^{*})=\mathcal{T}_{\mathcal{C}^{\prime}}(\mathbf{x}_{0}+\mathbf{w}^{*})=\text{cone}(\partial f(\mathbf{x}_{0}+\mathbf{w}^{*}))^{\circ}$, where the last equality follows from Lemma 7.2, and the fact that $\mathbf{x}_{0}+\mathbf{w}^{*}$ is not a minimizer of $f(\cdot)$ as $f(\mathbf{x}_{0})=f(\mathbf{x}_{0}+\mathbf{w}^{*})$. ∎