Slope meets Lasso: improved oracle bounds and optimality

Introduction

As a by-product, we cover some other related issues of independent interest:

We give a comparative analysis of conditions, under which oracle bounds for the Lasso and Slope estimators can be obtained showing, in particular, that several known conditions are equivalent.

Due to the new techniques, we obtain bounds in probability with fast rate $(s/n)\log(p/s)$ at any level of confidence while using the same tuning parameter. As opposed to the previous work on the Lasso, the level of confidence is not linked to the tuning parameter of the method. As a corollary, this implies rate optimal bounds on any moments of the estimation and prediction errors.

Statement of the problem and organization of the paper

Two estimators will be studied in this paper: the Lasso estimator and the Slope estimator. The Lasso estimator ${\boldsymbol{\hat{\beta}}}$ is a solution of the minimization problem

where $\lambda>0$ is a tuning parameter. Section 4 studies the prediction and estimation performance of the Lasso estimator with tuning parameter of order $\sigma\sqrt{\log(p/s)/n}$, where $s\in\{1,\dots,p\}$ is a sparsity parameter which is supposed to be known. In Section 5 we propose an adaptive choice of this parameter. Section 5 defines an estimator $\hat{s}$ valued in $\{1,\dots,p\}$ and studies the performance of the Lasso estimator with a data-driven tuning parameter of order $\sigma\sqrt{\log(p/\hat{s})/n}$.

where the maximum is taken over all permutations $\phi=(\phi(1),\dots,\phi(p))$ of $\{1,\dots,p\}$. The Slope estimator ${\boldsymbol{\hat{\beta}}}$ is defined as a solution of the minimization problem

Section 6 establishes oracle inequalities and estimation error bounds for the Slope estimator with tuning parameters

Notation and preliminaries

If ${\boldsymbol{\xi}}\sim{\cal N}({\boldsymbol{0}},\sigma^{2}I_{n\times n})$ it follows from the inequality $\|{\boldsymbol{x}}_{j}\|_{n}\leq 1$ that the random variables $g_{j}$ are zero mean Gaussian with variance at most $\sigma^{2}$. We denote by ${\boldsymbol{g}}^{\sharp}=(g^{\sharp}_{1},\dots,g^{\sharp}_{p})$ a non-increasing rearrangement of $(|g_{1}|,\dots,|g_{p}|)$. We also use the notation

The following bounds on the sum $\sum_{j=1}^{s}\log(2p/j)$ will be useful. From Stirling’s formula, we easily deduce that $s\log(s/e)\leq\log(s!)\leq s\log(s)$ and thus

where $(u_{1}^{\sharp},\dots,u_{p}^{\sharp})$ is a non-increasing rearrangement of $(|u_{1}|,\dots,|u_{p}|)$.

The tuning parameter of the Lasso need not be tied to a confidence level

In this section, we denote by ${\boldsymbol{\hat{\beta}}}$ the Lasso estimator defined by (2.1) and provide improved probability estimate for the performance of the Lasso estimator with tuning parameter of order $\sigma\sqrt{2\log p}$. First, we state a version of the Restricted Eigenvalue condition that we will refer to in the sequel. Let $s\in\{1,\dots,p\}$, and let $c_{0}>0$ be a constant.

which is the standard cone of the $RE$ condition as introduced in . One minor difference from is that in (3.1) we have $|{\boldsymbol{\delta}}|_{2}$ rather than $|{\boldsymbol{\delta}}_{J_{*}}|_{2}$ in the denominator. This only modifies the constant $\kappa(s,c_{0})$ by factor $\sqrt{1+c_{0}}$. Indeed, for any ${\boldsymbol{\delta}}\in{\cal C}_{RE}^{\prime}(s,c_{0})$,

Consider the following result based on , which is representative of the non-asymptotic bounds obtained so far for the prediction performance of the Lasso.

Let $p\geq 4$, $s\in\{1,...,p\}$, $\varepsilon>0$ and set $c_{0}=1+1/\epsilon$. For any $\delta\in(0,1/2)$ and $\varepsilon\in(0,1)$, the Lasso estimator (2.1) with tuning parameter

satisfies with probability $1-2\delta$ the oracle inequality

A notable feature of Proposition 3.1 and of other non-asymptotic bounds for the Lasso available in the literature is that the confidence level $1-2\delta$ is tied to the tuning parameter $\lambda$, cf. (3.3). If a confidence level closer to one is desired (i.e., smaller $\delta$), the previous results suggest that the tuning parameter should be increased according to the relationship (3.3) between $\lambda$ and $\delta$. We claim that it is not needed. Indeed, the following proposition holds.

Let $p\geq 2$, $s\in\{1,...,p\}$, $\varepsilon>0$ and set $c_{0}=1+1/\epsilon$. Let ${\boldsymbol{\hat{\beta}}}$ be the Lasso estimator (2.1) with tuning parameter

holds with probability at least $1-\delta$.

The proof of Proposition 3.2 is given in Appendix I. Let us highlight some features of Proposition 3.2 that are new.

Second, the probability that an oracle inequality with error term of order $s\log(p)/n$ holds is substantially closer to 1 than it was commonly understood before. For example, take $\delta=p^{-s}$, which balances the remainder term in (3.6). Then, Proposition 3.2 yields that the Lasso estimator with tuning parameter (3.5) converges with the rate smaller than $s\log(p)/n$ up to a multiplicative constant. On the other hand, the choice $\delta=p^{-s}$ in Proposition 3.1 yields only a suboptimal rate of order $s^{2}\log(p)/n$.

The constant term 2.8 in (3.6) is negligible. Thus, in asymptotic regimes where $p\rightarrow\infty$ or $\delta\rightarrow 0$, the constant term 2.8 is dominated by $\sqrt{\log p}$ or $\sqrt{\log(1/\delta)}$. If we ignore this constant term, the bound (3.6) strictly improves upon (3.4).

In spite of these improvements, the result of Proposition 3.2 is not completely satisfying since only the rate $s\log(p)/n$ and not the optimal rate $(s/n)\log(p/s)$ is proved. In the next section, we show that the optimal rate can be achieved by the Lasso estimator with tuning parameter of the order $\sigma\sqrt{\log(p/s)/n}$.

Optimal rates for the Lasso estimator

In this section, we denote by ${\boldsymbol{\hat{\beta}}}$ the Lasso estimator defined by (2.1), and we derive upper bounds for its prediction and estimation errors. As usual in the Lasso context, the argument contains two main ingredients. First, all randomness is removed from the problem by reducing the consideration to a suitably chosen random event of high probability. Second, the error bounds are derived on this event by a purely deterministic argument. In our case, such a deterministic argument is given in Theorem 4.2 below, while the “randomness removing tool” is provided by the next theorem. As we will see in Section 6, this theorem is common to the study of both the Lasso and the Slope estimators.

is of probability at least $1-{\delta_{0}/2}$.

Under the $SRE$ condition, we now establish a deterministic result, which is central in our argument. We first introduce some notation. Let $\gamma\in(0,1)$ be a constant. For any tuning parameter $\lambda>0$, set

For given $s\in\{1,\dots,p\}$, the following theorem holds under the condition

Let $s\in\{1,\dots,p\}$, $\gamma\in(0,1)$ and $\tau\in[0,1-\gamma)$. Assume that the $SRE(s,c_{0})$ condition holds with $c_{0}=c_{0}(\gamma,\tau)=\frac{1+\gamma+\tau}{1-\gamma-\tau}$. Let $\lambda$ be a tuning parameter such that (4.5) holds. Let $\delta_{0}\in(0,1)$. Then, on the event (4.1), the Lasso estimator ${\boldsymbol{\hat{\beta}}}$ with tuning parameter $\lambda$ satisfies

Theorem 4.2 is proved in Appendix B. Before the statement of its corollaries, a few comments are in order.

The conclusions of Theorem 4.2 hold on the event (4.1), which is independent of $\gamma$ and $\tau$. Thus, on the event (4.1), for all choices of $\tau,\gamma$ and $\lambda$ such that (4.5) holds, the oracle inequality (4.6) and the estimation bound (4.7) are satisfied.

The constants $\gamma$ and $\tau$ are such that $\gamma+\tau<1$. For the ease of presentation, the particular choice $\gamma=1/2$ and $\tau=1/4$ will be used below to derive two corollaries of Theorem 4.2. If $\gamma=1/2$ and $\tau=1/4$, then the constants in Theorem 4.2 have the form

while inequality (4.7) can be transformed into

where we have used that $\theta^{2}(s,c_{0})\leq\theta^{2}(s,\frac{1+\gamma}{1-\gamma})$.

We now take a closer look at the constant $C_{\gamma,\tau}(s,\lambda,\delta_{0})$. This constant is always greater than or equal to $(1+\gamma+\tau)^{2}/\theta^{2}(s,c_{0})$. Furthermore, the value

is the smallest $\delta_{0}\in(0,1)$ such that $C_{\gamma,\tau}(s,\lambda,\delta_{0})=(1+\gamma+\tau)^{2}/\theta^{2}(s,c_{0})$. If $\lambda$ satisfies (4.5), then

Using these remarks we obtain the following corollary of Theorems 4.1 and 4.2 with the choice $\gamma=1/2,\tau=1/4$, and $\delta_{0}=\delta_{0}^{*}$.

Let $s\in\{1,\dots,p\}$. Assume that the $SRE(s,7)$ condition holds. Let ${\boldsymbol{\hat{\beta}}}$ be the Lasso estimator with tuning parameter $\lambda$ satisfying (4.5) for $\gamma=1/2$. Then, with probability at least $1-{\frac{1}{2}}\left(\frac{s}{2ep}\right)^{\frac{s}{\theta^{2}(s,7)}}$, we have

Since $\theta^{2}(s,7)\leq 1$, the probability in Corollary 4.3 is greater than $1-{\frac{1}{2}}\left(\frac{s}{2ep}\right)^{s}.$ If the tuning parameter is chosen such that (4.5) holds with equality, then $\lambda^{2}s$ is equal to

Finally, the conclusions of Theorem 4.2 hold for all $\delta_{0}\leq\delta_{0}^{*}$. This allows us to integrate the oracle inequality (4.6) and the estimation bound (4.7) to obtain the following results in expectation.

Let $s\in\{1,\dots,p\}$. Assume that the $SRE(s,7)$ condition holds. Let ${\boldsymbol{\hat{\beta}}}$ be the Lasso estimator with tuning parameter $\lambda$ satisfying (4.5) for $\gamma=1/2$. Then,

In this section, the variance $\sigma$ was supposed to be known. The case of unknown $\sigma$ can be treated in a standard way as described, for example, in . Namely, we replace $\sigma$ in (4.5) by a suitable statistic $\hat{\sigma}$. For example, it can be shown that under the $RE$ condition, the scaled Lasso estimator $\hat{\sigma}^{S}$ is such that $\sigma/2\leq\hat{\sigma}^{S}\leq 2\sigma$ with high probability provided that $s\leq cn$ for some constant $c>0$, cf. [11, Sections 5.4 and 5.6.2]. Then, replacing $\sigma$ by $\hat{\sigma}\triangleq 2\hat{\sigma}^{S}$ in the expression for $\lambda$, cf. (4.5), we obtain that under the same mild conditions, Corollary 4.3 remains valid with this choice of $\lambda$ independent of $\sigma$, up to a change in numerical constants. This remark also applies to upper bounds in probability obtained in the next sections.

Aggregated Lasso estimator and adaptation to sparsity

We denote by ${\boldsymbol{\hat{\beta}}}_{s}$ the Lasso estimator with tuning parameter

and we set for brevity $\theta_{*}=\theta(2s_{*},7)$. We will assume that $\theta_{*}>0$. Then, $\theta^{2}(s,7)\geq\theta_{*}>0$, $s=1,\dots,2s_{*}$. It follows from Corollary 4.3 that for any $s=1,\dots,2s_{*}$

Let $s_{*}\in\{2,\dots,p\}$ be such that $\theta_{*}>0$ and $s_{*}\leq p/(2e)$. Then there exists an absolute constant $C_{1}>0$ such that, for $C_{0}$ given in (5.3) and all $s=1,\dots,s_{*}$,

where $C_{0}^{\prime}=49(4+\sqrt{2})/(4\theta_{*})$. Second, analogously to (5.4), we have for all $s=1,\dots,s_{*}$, $1\leq q\leq 2$,

The proof of this theorem is given in Appendix C. Due to (5.9) and (5.10), it is quite analogous to the proof of Theorem 5.1.

Optimal rates for the Slope estimator

This condition is stated for any weights $\lambda_{1}\geq\dots\geq\lambda_{p}\geq 0$ but we will use it only for $\lambda_{j}$ given in (2.5) and in that case the cone is equivalently defined as

Let us compare the $WRE$ condition with the $SRE$ condition. Assume that ${\boldsymbol{\delta}}$ belongs to the cone ${\cal C}_{SRE}(s,c_{0})$, that is, $|{\boldsymbol{\delta}}|_{1}\leq(1+c_{0})\sqrt{s}|{\boldsymbol{\delta}}|_{2}$. Then also $\sum_{j=s+1}^{p}\delta_{j}^{\sharp}\leq{(1+c_{0})}\sqrt{s}|{\boldsymbol{\delta}}|_{2}$, and we have

where the last inequality follows from (2.7). For the first $s$ components, the Cauchy-Schwarz inequality yields

Combining the last two displays we find that ${\boldsymbol{\delta}}\in{\cal C}_{WRE}(s,{1+c_{0}})$. Thus, ${\cal C}_{SRE}(s,c_{0})\subseteq{\cal C}_{WRE}(s,{1+c_{0}})$, so that the $WRE(s,1+c_{0})$ condition implies the $SRE(s,c_{0})$ condition. A more detailed comparison between these two conditions as well as examples of random matrices, for which both conditions hold are given in Section 8. We are now ready to state our main result on the Slope estimator.

Let $s\in\{1,\dots,p\}$, $\gamma\in(0,1)$ and $\tau\in[0,1-\gamma)$. Set $c_{0}=c_{0}(\gamma,\tau)=\frac{1+\gamma+\tau}{1-\gamma-\tau}$. Let the tuning parameters $\lambda_{j}$ be defined by (2.5) with constant

Let $\delta_{0}\in(0,1)$. Then, on the event (4.1), the Slope estimator ${\boldsymbol{\hat{\beta}}}$ that minimizes (2.4) with the weights $\lambda_{1},\dots,\lambda_{p}$ satisfies

The proof of Theorem 6.1 is given in Section D. It follows the same route as the proof of Theorem 4.2. Since $\lambda_{1},\dots,\lambda_{p}$ satisfy (2.5) then by (2.7), for all $s=1,\dots,p$ we have

Let $s\in\{1,\dots,p\}$. Assume that the $WRE(s,7)$ condition holds. Let ${\boldsymbol{\hat{\beta}}}$ be the Slope estimator with tuning parameters $\lambda_{1},\dots,\lambda_{p}$ satisfying (2.5) for $A\geq{2(4+\sqrt{2})}$. Then, with probability at least $1-{\frac{1}{2}}\left(\frac{s}{2p}\right)^{\frac{s}{\vartheta^{2}(s,7)}}$, we have

The fact that Theorems 4.1 and 6.1 hold for any $\delta_{0}\in(0,1)$ allows us to integrate the bounds (6.2) and (6.4) to obtain the following oracle inequalities and bounds on the estimation error in expectation.

Let $s\in\{1,\dots,p\}$. Assume that the $WRE(s,7)$ condition holds. Let ${\boldsymbol{\hat{\beta}}}$ be the Slope estimator with tuning parameters $\lambda_{1},\dots,\lambda_{p}$ satisfying (2.5) for $A\geq{2(4+\sqrt{2})}$. Then,

Since ${\boldsymbol{\hat{\beta}}}$ does not depend on $s$, the first inequality in Corollary 6.3 and (6.5) imply a “balanced” oracle inequality:

if $\vartheta^{2}(|{\boldsymbol{\beta}}|_{0},7)\neq 0$ and $C(|{\boldsymbol{\beta}}|_{0})=\infty$ otherwise. This formulation might be of interest in the context of aggregation as explained, for example, in .

Corollaries 6.2 and 6.3 are the analogs of Corollaries 4.3 and 4.4 for the Lasso. The proof of Corollary 6.3 is omitted. It is deduced from Theorem 6.1 exactly in the same way as Corollary 4.4 is deduced from Theorem 4.2 in Section B.

Minimax lower bounds

The bound (7.2) now follows from (7.4) and (7) in view of [25, Theorem 2.7]. ∎

Assumptions on the design matrix

Along with the $RE$ and $SRE$ conditions defined in Section 4 we consider here the $s$-sparse eigenvalue condition defined as follows, for any $s\in\{1,\dots,p\}$.

Let $c_{0}>0$ and $s\in\{1,\dots,p\}$. We have the following implications.

If condition $SRE(s,c_{0})$ holds then condition $RE(s,c_{0})$ holds and $\kappa(s,c_{0})\geq\theta(s,c_{0})$.

If condition $RE(s,c_{0})$ holds then the $s$-sparse eigenvalue condition holds and $\bar{\theta}_{\min}(s)\geq\kappa(s,c_{0})$.

Let $\theta_{1}>0$. If the $s$-sparse eigenvalue condition holds with $\bar{\theta}_{\min}(s)\geq\theta_{1}$ then the $SRE(s_{1},c_{0})$ condition holds and $\theta(s_{1},c_{0})\geq\theta_{1}/\sqrt{2}$ for $s_{1}\leq(s-1)\theta_{1}^{2}/(2c_{0}^{2})$.

The message of the above proposition is that the three conditions – $RE(s,c_{0})$, $SRE(s,c_{0})$ and the $s$-sparse eigenvalue condition – are equivalent up to absolute constants. This equivalence has two main consequences for the results of the present paper.

First, the results on the Lasso in Sections 4 and 5 are proved under the $SRE(s,c_{0})$ condition. The above equivalence shows that, for some integer $s_{1}$, which is of the same order as $s$, the oracle inequalities and the estimation bounds of Sections 4 and 5 are valid under the Restricted Eigenvalue condition $RE(s_{1},c_{0})$.

In conclusion, for a large class of random matrices with i.i.d. rows, condition $SRE(s,c_{0})$ holds with high probability if

2 Design conditions for the Slope estimator

Theorem 6.1 and Corollaries 6.2, 6.3 establish prediction and estimation bounds for the Slope estimator under the $WRE(s,c_{0})$ condition. It was explained in Section 6 that the $WRE(s,c_{0})$ condition implies the $SRE(s,1+c_{0})$ condition. The converse is not true – there is no equivalence between the two conditions. However, a simple observation leads to the following sufficient condition for $WRE(s,c_{0})$.

Let $s\in\{1,\dots,p\}$, $c_{0}>0$, and let the weights $\lambda_{j}$ be defined by (2.5). Set $s_{2}={\lceil s\log(2ep/s)/\log 2\rceil}$. If the $SRE(s_{2},c_{0})$ condition holds then the $WRE(s,c_{0})$ condition holds, and $\vartheta(s,c_{0})\geq\theta(s_{2},c_{0})$.

If ${\boldsymbol{\delta}}\in{\cal C}_{WRE}(s,c_{0})$, then

This, together with (2.5) and (2.7) imply $|{\boldsymbol{\delta}}|_{1}\leq(1+c_{0})\sqrt{s\log(2ep/s)/\log 2}|{\boldsymbol{\delta}}|_{2}$. Thus, ${\boldsymbol{\delta}}\in{\cal C}_{SRE}(s_{2},c_{0})$. ∎

Assume that the covariance matrix $\Sigma$ satisfies

then, with probability at least $1-3\exp(-C^{\prime}n/L^{4})$ we have

Extension to sub-gaussian noise

The goal of this section is to show that all results of the present paper extend to subgaussian noise. This is due to the following analog of Theorem 4.1.

Let $\delta_{0}\in(0,1)$. Assume that the components of ${\boldsymbol{\xi}}=(\xi_{1},\dots,\xi_{n})$ are independent, with zero mean, and subgaussian in the sense that, for some $\sigma>0$,

The proof of Theorem 9.1 relies on the following deviation inequality, which is proved in Appendix H using symmetrization and contraction arguments.

where ${\boldsymbol{z}}$ is a standard normal $\mathcal{N}({\boldsymbol{0}},I_{n\times n})$ random vector.

Appendix A Preliminaries for the proofs

where ${\boldsymbol{u}}={\boldsymbol{\hat{\beta}}}-{\boldsymbol{\beta}}=(u_{1},\dots,u_{p})$ and $(u_{1}^{\sharp},\dots,u_{p}^{\sharp})$ is a non-increasing rearrangement of $(|u_{1}|,\dots,|u_{p}|)$. If $\lambda_{1}=\dots=\lambda_{p}=\lambda$ for some $\lambda>0$, then $|\cdot|_{*}=\lambda|\cdot|_{1}$ and (A.1) yields

Let $\phi$ be any permutation of $\{1,\dots,p\}$ such that

By (2.3) applied to $|{\boldsymbol{\hat{\beta}}}|_{*}$, we have

since $u_{\phi(j)}=\hat{\beta}_{\phi(j)}-\beta_{\phi(j)}$ for $j=1,\dots,s$ and $u_{\phi(j)}=\hat{\beta}_{\phi(j)}$ for all $j>s$. Since the sequence $\lambda_{j}$ is non-increasing we have $\sum_{j=1}^{s}\lambda_{j}|u_{\phi(j)}|\leq\sum_{j=1}^{s}\lambda_{j}u_{j}^{\sharp}$. Next, the fact that permutation $\phi$ satisfies (A.3) implies $\sum_{j=s+1}^{p}\lambda_{j}u_{j}^{\sharp}\leq\sum_{j=s+1}^{p}\lambda_{j}|u_{\phi(j)}|$. Finally, $\sum_{j=1}^{s}\lambda_{j}u_{j}^{\sharp}\leq(\sum_{j=1}^{s}\lambda_{j}^{2})^{1/2}|{\boldsymbol{u}}|_{2}$ by the Cauchy-Schwarz inequality. ∎

To complete the proof, notice that by definition of the subdifferential of $h$ at ${\boldsymbol{\hat{\beta}}}$, we have $({\boldsymbol{\beta}}-{\boldsymbol{\hat{\beta}}})^{T}{\boldsymbol{v}}\leq h({\boldsymbol{\beta}})-h({\boldsymbol{\hat{\beta}}}).$ ∎

This lemma is proved in the discussion after equation (1.6) in [17, page 21].

Appendix B Proofs for the Lasso estimator

Let ${\boldsymbol{u}}={\boldsymbol{\hat{\beta}}}-{\boldsymbol{\beta}}$ and assume that $|{\boldsymbol{\beta}}|_{0}\leq s$. Define

Using the Cauchy-Schwarz inequality, it is easy to see that

where $H(\cdot)$ is defined in (2.8), and the last inequality follows from (2.7) and (4.5).

On the event (4.1), using (B.3) and Lemma A.1 we obtain

By definition of $\delta(\lambda)$, we have

Case $G({\boldsymbol{u}})>F({\boldsymbol{u}})$. Then,

Case $G({\boldsymbol{u}})\leq F({\boldsymbol{u}})$. In this case, we get

If $\triangle\leq 0$, then (B.6) holds trivially.

Combining (B.5) and (B.6) with (B.1) completes the proof of (4.6).

To prove (B.8), we take $\tau=0$, and consider the cases (i) and (ii) as above with ${\boldsymbol{u}}={\boldsymbol{\hat{\beta}}}-{\boldsymbol{\beta}}^{*}$.

If $G({\boldsymbol{u}})>F({\boldsymbol{u}})$, then from (B.1) and (B.5) with $\tau=0$ and ${\boldsymbol{\beta}}={\boldsymbol{\beta}}^{*}$ we get

If $G({\boldsymbol{u}})\leq F({\boldsymbol{u}})$, then it follows from (B.1) with ${\boldsymbol{\beta}}={\boldsymbol{\beta}}^{*}$ that $\triangle^{*}\geq 0$ almost surely, and thus $\triangle\geq\triangle^{*}\geq 0$. Hence, ${\boldsymbol{u}}={\boldsymbol{\hat{\beta}}}-{\boldsymbol{\beta}}^{*}\in{\cal C}_{SRE}(s,\frac{1+\gamma}{1-\gamma})$. Thus, we can apply the $SRE(s,\frac{1+\gamma}{1-\gamma})$ condition, which yields

where the second inequality is due to the combination of (B.1) and (B.6) with ${\boldsymbol{\beta}}={\boldsymbol{\beta}}^{*}$, $\tau=0$.

Putting together (B.9) and (B.10) proves (B.8). To conclude, it is enough to notice that $\theta^{2}(s,\frac{1+\gamma}{1-\gamma})\geq\theta^{2}(s,c_{0})$ and then to bound $|{\boldsymbol{\hat{\beta}}}-{\boldsymbol{\beta}}^{*}|_{q}$ from above using (B.7), (B.8) and the norm interpolation inequality $|{\boldsymbol{\hat{\beta}}}-{\boldsymbol{\beta}}^{*}|_{q}\leq|{\boldsymbol{\hat{\beta}}}-{\boldsymbol{\beta}}^{*}|_{1}^{2/q-1}|{\boldsymbol{\hat{\beta}}}-{\boldsymbol{\beta}}^{*}|_{2}^{2-2/q}.$ ∎

Let $\gamma=1/2$, $\tau=1/4$, and let $\delta_{0}^{*}$ be defined in (4.10). Set

with probability at least $1-\frac{e^{-t}}{2}$. To prove (4.14), it remains to note that

Appendix C Lasso with adaptive choice of λ𝜆\lambda

On the event $\{\hat{m}\leq m_{0}\}$ we have

where $c^{\prime}>2$ is an absolute constant. We deduce that, on the event $\{\hat{m}\leq m_{0}\}$,

Case $s<b_{M}$. Then, by definition of $m_{0}$ we have $b_{m_{0}}/2=b_{m_{0}-1}\leq s<b_{m_{0}}$. Since the function $w(\cdot)$ is increasing on $[1,p]$, we easily deduce that

Case $s\in[b_{M},s_{*}]$. Then, $b_{m_{0}}=b_{M}\leq s$, while $s\leq 2b_{M}$. Therefore, in this case $b_{m_{0}}\leq s<2b_{m_{0}}$, which implies

In both cases (i) and (ii), we have $w(s)\geq w(b_{m_{0}})/\sqrt{2}.$ This remark and the fact that (C.4) holds on the event $\{\hat{m}\leq m_{0}\}$ imply

Next, in both cases (i) and (ii), we have $s\leq 2b_{m_{0}}$, which implies that ${\boldsymbol{\beta}}^{*}\in B_{0}(2b_{m_{0}})$. Using this fact together with (C.5) and (5.4) we obtain

where we have used that the function $b\mapsto\left(b/p\right)^{b}$ is decreasing on the interval $[1,p/e]$ and, in both cases (i) and (ii), $2b_{m_{0}}\leq 2s_{*}\leq p/e$.

Now, from the definition of $\hat{m}$ we obtain

where we have used that $b_{k}>b_{k-1}$ and the monotonicity of $w(\cdot)$. Thus,

The double sum in (C.7) is non-zero only if $m_{0}<M$. This implies that $s<b_{m_{0}}$, and hence ${\boldsymbol{\beta}}^{*}\in B_{0}(b_{m_{0}})\subset B_{0}(b_{k})$ for all $k\geq m_{0}$. Therefore, using (5.2) we obtain

Recall that $M\leq\log_{2}(2p)$. Note also that the function $b\mapsto\left(\frac{b}{p}\right)^{b}$ is decreasing on the interval $[1,p/e]$, while $b_{j}\leq s_{*}$ for all $j$ and $s_{*}\leq p/e$ by assumption. Finally, in both cases (i) and (ii), $b_{m_{0}}\leq 2s$. Using these remarks we get

Combining this bound with (C.6) and (C.1) where we set $a={\sqrt{2}}({\sqrt{2}}+c^{\prime})w(s)$ proves (5.7). Finally, inequality (5.8) follows from (C.9) and the relations $\{{\hat{s}}\leq s\}=\{b_{\hat{m}-1}\leq s\}=\{b_{\hat{m}}/2\leq s\}\supseteq\{b_{\hat{m}}\leq b_{m_{0}}\}=\{\hat{m}\leq m_{0}\}$. ∎

Appendix D Proofs for the Slope estimator

If $\triangle\leq 0$ then (6.2) holds trivially in view of (D.1). If $\triangle>0$, then ${\boldsymbol{u}}$ belongs to the cone ${\cal C}_{WRE}(s,c_{0})$, and we can use the $WRE(s,c_{0})$ condition, which yields

Combining the last inequality with (D.3) and (D.1) completes the proof of (6.2).

Appendix E Bound on the stochastic error

Here, we prove Theorem 4.1. The proof is based on a sequence of propositions.

Let $g_{1},\dots,g_{p}$ be zero-mean Gaussian random variables with variance at most $\sigma^{2}$. Denote by $(g_{1}^{\sharp},\dots,g_{p}^{\sharp})$ be a non-increasing rearrangement of $(|g_{1}|,\dots,|g_{p}|)$. Then

Under the assumptions of Proposition E.1,

Proposition E.1 with $t=16/3$, and the inequality $(g_{j}^{\sharp})^{2}\leq\frac{1}{j}\sum_{k=1}^{j}(g_{k}^{\sharp})^{2}$ imply

Let $q\geq 0$ be the integer such that $2^{q}\leq p<2^{q+1}$. Applying (E.3) to $j=2^{l}$ for $l=0,\dots,q-1,$ and using the union bound, we obtain that the event

Thus, on the event $\Omega_{0}$ we have $g_{j}^{\sharp}\leq 4\sigma\sqrt{\log(2p/j)}$ for all $j=1,\dots,p$. ∎

Appendix F Tools for lower bounds

for any two distinct elements $\boldsymbol{\omega}$ and $\boldsymbol{\omega}^{\prime}$of $\Omega$.

The proof of this lemma is omitted since it closely follows the argument in [26, p.79–80].

Appendix G Random design matrices

It follows from (cf., for instance, Theorem 1.12 in ) that for all $u>0$, with probability at least $1-2\exp(-C_{2}\min(u^{2},u\sqrt{n}))$,

By (G.2), if we take $u=\sqrt{n}/(4C_{1}L^{2})$ and if the number of observations $n$ satisfies $n\geq 64{(C_{1}\vee C_{1}^{2})}L^{2}\gamma^{2}$, then with probability at least $1-2\exp(-C_{3}n/L^{4})$,

In this proof, we set $g_{j}={\boldsymbol{z}}^{T}\Sigma^{1/2}{\boldsymbol{e}}_{j}$, $j=1,\dots,p$. As $\Sigma_{jj}\leq 1$, the variance of $g_{j}$ is at most 1. By Proposition E.2, the event

has probability at least $1/2$. On the event $\Omega_{0}$, for all ${\boldsymbol{v}}\in T$ we have

In conclusion, both inequalities in (8.6) are satisfied if

Since $\kappa^{2}\leq 1$, $L\geq 1$, and $s\log(2ep/s)\geq\log p$ the inequality in the last display is satisfied if (8.5) holds for some large enough absolute constant $C>0$. ∎

Appendix H Subgaussian noise

To prove Proposition 9.2, we need the following lemma.

Let $\sigma>0$, $z\sim\mathcal{N}(0,1)$, and let $\xi_{i}$ be a random variable satisfying (9.1). Then

By homogeneity, it is enough to consider $\sigma=1$. From a standard lower bound on the Gaussian tail probability, cf. [2, Formula 7.1.13], we get

Let $\eta>0$. Let $(\varepsilon_{1},\dots,\varepsilon_{n})$ be a vector of i.i.d. Rademacher variables independent of ${\boldsymbol{\xi}}$. The symmetrization inequality, cf., e.g. [12, Theorem 2.1], yields

Since $U$ is a subset of the unit sphere, the function $f:{\boldsymbol{z}}\rightarrow\sup_{{\boldsymbol{u}}\in U}{\boldsymbol{z}}^{T}{\boldsymbol{u}}$ is $1$-Lipschitz. Thus, by [6, Theorem 5.5], the right hand side of the previous display is bounded from above by

Let $N(\cdot)$ be defined in (E.5) and let ${\boldsymbol{z}}$ be a standard normal $\mathcal{N}({\boldsymbol{0}},I_{n\times n})$ random vector. It follows from (E.6) and Proposition E.2 that

Appendix I Lasso with universal tuning parameter

Let ${\boldsymbol{u}}={\boldsymbol{\hat{\beta}}}-{\boldsymbol{\beta}}$ and define the function $f$ as follows:

Since the function $f$ is 1-Lipschitz, by the Gaussian concentration bound [17, inequality (1.4)] we have, for all $\delta\in(0,1)$,

To complete the proof, it remains to show that

Thus, by definition of the median, an upper bound on $\operatorname{Med}[f({\boldsymbol{\xi}})]$ is given by an upper bound on $f({\boldsymbol{\xi}})$ on the event $\Omega_{1}\cap\Omega_{2}$:

Acknowledgement. This work was supported by GENES and by the French National Research Agency (ANR) under the grants IPANEMA (ANR-13-BSH1-0004-02) and Labex Ecodec (ANR-11-LABEX-0047). It was also supported by the ”Chaire Economie et Gestion des Nouvelles Données”, under the auspices of Institut Louis Bachelier, Havas-Media and Paris-Dauphine.

References