On the conditions used to prove oracle results for the Lasso

Introduction

In this paper we revisit some sufficient conditions for oracle inequalities for the Lasso in regression and examine their relations. Such oracle results have been derived, among others, by Bunea et al. 2007c, van de Geer 2008, Zhang and Huang 2008, Meinshausen and Yu 2009, Bickel et al. 2009, and for the related Dantzig selector by Candès and Tao 2007 and Koltchinskii 2009b. Furthermore, variable selection properties of the Lasso have been studied by Meinshausen and Bühlmann 2006, Zhao and Yu 2006, Lounici 2008, Zhang 2009 and Wainwright 2009. Our main aim is to present an overview of the relations (of which some are known and some are new), and to emphasize that that sufficient conditions for oracle inequalities hold in fairly general situations.

The Lasso, which we at first only study in a noiseless situation, is defined as follows. Let ${\cal X}$ be some measurable space, $Q$ be a probability measure on ${\cal X}$, and $\|\cdot\|$ be the $L_{2}(Q)$ norm. Consider a fixed dictionary of functions $\{\psi_{j}\}_{j=1}^{p}\subset L_{2}(Q)$, and linear functions

We let $S:=\{j:\ \beta_{j}^{0}\not=0\}$ be its active set, and $s:=|S|$ be the sparsity index of $f^{0}$.

For some fixed $\lambda>0$, the Lasso for the noiseless problem is

the vector with non-zero entries in the set ${\cal N}$ (hence, for example $\beta_{S}^{0}=\beta^{0}$).

Definition: Sparsity constant and sparsity oracle inequality. The sparsity constant $\phi_{0}$ is the largest value $\phi_{0}>0$ such that Lasso with $\beta^{*}$ and $f^{*}$ satisfies the $\phi_{0}$-sparsity oracle inequality

Restricted eigenvalue conditions (see Koltchinskii 2009a; Koltchinskii 2009b and Bickel et al. 2009) have been developed to derive lower bounds for the sparsity constant. We will present these conditions in the next section. Irrepresentable conditions (see Zhao and Yu 2006) are tailored for proving variable selection, i.e., showing that $S_{*}=S$, or, more more modestly, that the symmetric difference $S_{*}\triangle S$ is small.

We start out with, in Section 2, an overview of the conditions we will compare, and some pointers to the literature. Once the conditions are made explicit, we give in Subsection 2.2 a summary of the various relations. Figure 1 displayed there enables to see these at a single glance. We give a proof of each of the indicated (numbered) implications. Sections 3 - 9 rigorously deal with all the different cases. The weakest condition is a compatibility condition. Stronger conditions can rule out many interesting cases. We illustrate in Section 10 that one may check compatibility using approximations. We give several examples, where the compatibility condition holds. We also give an example where the compatibility condition yields a major improvement to the oracle result, as compared to the restricted eigenvalue condition. The noisy case, studied briefly in Section 11, poses no additional theoretical difficulties. A lower bound on the regularization parameter $\lambda$ is required, and implications become somewhat more technical because all further results depend on this lower bound. Section 12 discusses the results.

2 Some notation

For a vector $v$, we invoke the usual notation

The entries of $\Sigma$ are denoted by $\sigma_{j,k}:=(\psi_{j},\psi_{k})$, with $(\cdot,\cdot)$ being the inner product in $L_{2}(Q)$.

To clarify the notions we shall use, consider for a moment a partition of the form

where $\Sigma_{1,1}$ is an $N\times N$ matrix, $\Sigma_{2,1}$ is a $(p-N)\times N$ matrix and $\Sigma_{1,2}:=\Sigma_{2,1}^{T}$ is its transpose, and where $\Sigma_{2,2}$ is a $(p-N)\times(p-N)$ matrix. Such partitions will be play an important role in the sections to come.

More generally, for a set ${\cal N}\subset\{1,\ldots,p\}$ with size $N$, we introduce the $N\times N$ matrix

We let $\Lambda_{\rm min}^{2}(\Sigma_{1,1}({\cal N}))$ be the smallest eigenvalue of $\Sigma_{1,1}({\cal N})$. Throughout, we assume that, for the fixed active set $S$, the smallest eigenvalue $\Lambda_{\rm min}^{2}(\Sigma_{1,1}(S))$ is strictly positive, i.e., that $\Sigma_{1,1}(S)$ is non-singular.

We sometimes identify $\beta_{\cal N}$ with the vector $|{\cal N}|$-dimensional vector $\{\beta_{j}\}_{j\in{\cal N}}$, and write e.g.,

An overview of definitions

Definition: Compatibility condition. We call

The bound $\|\beta_{S}\|_{1}\leq\sqrt{s}\|\beta_{S}\|_{2}$ (which holds for any $\beta$) leads to two successively stronger versions of restricted eigenvalues. We moreover consider supsets ${\cal N}$ of $S$ with size at most $N$. Throughout in our definitions, $N\geq s$. We will only invoke $N=s$ and $N=2s$ (for simplicity).

If $N=s$, we necessarily have ${\cal N}\backslash S=\emptyset$. In that case, we let $\min_{j\in{\cal N}\backslash S}|\beta_{j}|=0$, i.e., ${\cal R}(L,S,S)={\cal R}(L,S)$ (${\cal R}_{\rm adaptive}(L,S,S)={\cal R}_{\rm adaptive}(L,S)$).

The restricted eigenvalue condition is from Bickel et al. 2009 and Koltchinskii 2009b. We complement it with the adaptive restricted eigenvalue condition. The name of the latter is inspired by the fact that this strengthened version is useful for the development of theory for the adaptive Lasso (Zou 2006) which we do not show in this paper.

Definition: (Adaptive) restricted eigenvalue. We call

the $(L,S,N)$-restricted eigenvalue, and, similarly,

the adaptive $(L,S,N)$-restricted eigenvalue. The (adaptive) $(L,S,N)$-restricted eigenvalue condition holds if $\phi(L,S,N)>0$ ($\phi_{\rm adaptive}(L,S,N)>0$) .

We introduce the (adaptive) restricted regression condition to clarify various connections between different assumptions.

Definition: (Adaptive) restricted regression. The $(L,S,N)$-restricted regression is

The adaptive $(L,S,N)$-restricted regression is

The (adaptive) $(L,S,N)$-restricted regression condition holds if $\vartheta(L,S,N)<1$ ($\vartheta_{\rm adaptive}(L,S,N)<1$).

Note that ${(f_{\beta_{\cal N}},f_{\beta_{{\cal N}^{c}}})/\|f_{\beta_{\cal N}}\|^{2}}$ equals the coefficient when regressing $f_{\beta_{{\cal N}^{c}}}$ onto $f_{\beta_{\cal N}}$.

Of course all these definitions depend on the Gram matrix $\Sigma$. In Sections 10 and 11, we make this dependence explicit by adding the argument $\Sigma$, e.g. the $(\Sigma,L,S)$-compatibility condition, etc.

When $L=1$, the argument $L$ is omitted, e.g. $\phi_{\rm compatible}(S):=\phi_{\rm compatible}(1,S)$, and e.g., the $S$-compatibility condition is then the condition $\phi_{\rm compatible}(S)>0$. The case $L>1$ is mainly needed to handle the situation with noise, and $L<1$ is of interest when studying the adaptive Lasso (but we do not develop its theory in this paper).

We now present some definitions from Candès and Tao 2005.

Definition: Restricted orthogonality constant. The quantity

is called the $(S,N)$-restricted orthogonality constant. We moreover define

Definition: Restricted isometry constant. The $N$-restricted isometry constant is the smallest value of $\delta_{N}$ such that for all ${\cal N}$ with $|{\cal N}|\leq N$,

Definition: Uniform eigenvalue. The $(S,N)$-uniform eigenvalue is

As mentioned before, we always assume that $\Lambda(S,s)>0$.

Definition: Weak restricted isometry. The weak $(S,N)$-restricted isometry constant is

The weak $(L,S,N)$-restricted isometry property holds if $\vartheta_{\rm weak-RIP}(S,N)<1/L$.

Definition: Restricted isometry property. The RIP constant is

The restricted isometry property, shortly RIP, holds if $\vartheta_{\rm RIP}<1$.

An irrepresentable condition can be found in Zhao and Yu 2006. We use a modified version which involves only the design but not the true coefficient vector $\beta^{0}$ (whereas its sign vector appears in Zhao and Yu 2006). The reason is that most other conditions considered in this paper do not depend on $\beta^{0}$ as well. Our $(L,S,N)$-irrepresentable condition with $L=1$ and $N=s$ is only slightly stronger than the condition in Zhao and Yu 2006.

Definition: Irrepresentable condition. Part 1. We call

the $(S,N)$-uniform irrepresentable constant. The $(L,S,N)$-uniform irrepresentable condition is met, if $\vartheta_{\rm irrepresentable}(S,N)<1/L$. Part 2. We say that the $(L,S,N)$-irrepresentable condition is met, if for some ${\cal N}\supset S$ with $|{\cal N}|\leq N$, and all vectors $\tau_{\cal N}$ satisfying $\tau_{\cal N}\in\{-1,1\}^{|{\cal N}|}$, we have

Part 3. We say that the weak $(S,N)$-irrepresentable condition is met, if for all $\tau_{S}\in\{-1,1\}^{s}$, and for some ${\cal N}\supset S$ with $|{\cal N}|\leq N$, and for some $\tau_{{\cal N}\backslash S}\in\{-1,1\}^{|{\cal N}\backslash S|}$, we have

Finally, we present coherence conditions, which are in the spirit of Bunea et al. 2007b; Bunea et al. 2007c. Cai et al. 2009b derive an oracle result under a tight coherence condition.

Definition: Coherence. The $(L,S)$-mutual coherence condition holds if

The $(L,S)$-cumulative coherence condition holds if

(Oracle inequality) We have for the Lasso in (1),

Moreover, letting ${\cal N}_{*}\backslash S$ being the set of the $N-s$ largest coefficients $|\beta_{j}^{*}|$, $j\in S^{c}$,

Proof of Lemma 2.1. The first assertion follows from the Basic Inequality

using the definition of the Lasso in (1), which implies

Note that the last inequality holds because $\beta^{*}-\beta^{0}\in{\cal R}(S)$ which follows by its preceding inequality:

and using $\phi_{\rm compatible}(S)\geq\phi(S,N)$. $\sqcup\mkern-12.0mu\sqcap$

where the last inequality is using the first assertion in Lemma 2.1. We also note that the second assertion in Lemma 2.1 has most statistical importance for the case with $N=s$. We will need the case $N=2s$ later in our proofs.

Meinshausen and Bühlmann 2006 and Zhao and Yu 2006 prove that the irrepresentable condition is sufficient and essentially necessary for variable selection, i.e., for achieving $S_{*}=S$. We will also present a self-contained proof in Section 6 where we will show that the $(S,s)$-irrepresentable condition is sufficient and the weak $(S,s)$-irrepresentable condition is essentially necessary for variable selection.

Bickel et al. 2009 prove oracle inequalities under the restricted eigenvalue condition. They assume

(where $L$ can be taken equal to one in the noiseless case).

The restricted isometry property from Candès and Tao 2005, abbreviated to RIP, also requires uniformity in $S$. They assume the RIP

They show that the RIP implies exact reconstruction of $\beta^{0}$ from $f^{0}$ by linear programming (that is, by minimizing $\|\beta\|_{1}$ subject to $\|f_{\beta}-f^{0}\|=0$). Cai et al. 2009a prove this result assuming $\delta_{N}+\theta_{s,N}<1$ for $N=1.25s$ only; see also Cai et al. 2009 for an earlier result. It is clear that $1-\delta_{N}\leq\Lambda^{2}(S,N)$, i.e., the restricted isometry constants are more demanding than uniform eigenvalues. Candès and Tao 2005 furthermore show that

See also Figure 1. They prove that the RIP is sufficient for establishing oracle inequalities for the Dantzig selector. Koltchinskii 2009a and Bickel et al. 2009 show that

Thus, the weak $(S,2s)$-restricted isometry property implies the $(S,2s)$-restricted eigenvalue condition. See also Figure 1.

Bunea et al. 2007a; Bunea et al. 2007b; Bunea et al. 2007c show that their coherence conditions imply oracle results and refinements (see also Section 4 for their condition on the diagonal of $\Sigma$). Candès and Plan 2009 weaken the coherence conditions by restricting the parameter space for the regression coefficient $\beta$.

Finally, it is clear that $\phi_{\rm adaptive}(L,S,N)\leq\phi(L,S,N)\leq\phi_{\rm compatible}(L,S)$, i.e.,

adaptive restricted eigenvalue condition $\Rightarrow$

restricted eigenvalue condition $\Rightarrow$

It is easy to see that $\vartheta(L,S,N)$ and $\vartheta_{\rm adaptive}(L,S,N)$ scale with $L$, i.e., we have

We let for any $\beta$, $r_{j}(\beta):={\rm rank}(|\beta_{j}|)$, $j\in S^{c}$, if we put the coefficients in decreasing order. Let ${\cal N}_{0}(\beta)$ be the set of the $s$ largest coefficients in $S^{c}$:

Put ${\cal N}(\beta):={\cal N}_{0}(\beta)\cup S$. Further, assuming without loss of generality that $p=(K+2)s$ for some integer $K\geq 0$, we let for $k=1,\ldots,K$,

We have for any any $r\geq 1$, and $1/r+1/q=1$, and any $\beta$, and for ${\cal N}:={\cal N}(\beta)$, and ${\cal N}_{k}:={\cal N}_{k}(\beta)$, $k=0,1,\ldots,K$, the bound

This result is from Bickel et al. 2009. The proof we give is essentially the same as theirs.

2 Summary of the results

The following figure summarizes the results.

Our conclusion is that (perhaps not surprising) the compatibility condition is the least restrictive, and that many sufficient conditions for compatibility may be somewhat too harsh (see also our discussion in Section 12).

The restricted regression condition implies the restricted eigenvalue condition

Let $f_{1}$ and $f_{2}$ by two functions in $L_{2}(P)$. Suppose for some $0<\vartheta<1$.

Proof. Write the projection of $f_{2}$ on $f_{1}$ as

be the projection of $f_{1}+f_{2}$ on $f_{1}$. Then

It is then straightforward to derive the following result.

A similar result is true for the adaptive versions. In other words, the (adaptive) restricted regression condition implies the (adaptive) restricted eigenvalue condition.

SS-coherence conditions imply adaptive (S,s)(S,s)-restricted regression conditions

Bunea et al. 2007a; Bunea et al. 2007b; Bunea et al. 2007c establish oracle results under a condition which we refer to as the restricted diagonal condition. They provide coherence conditions for verifying the restricted diagonal condition.

Definition: Restricted diagonal condition. We say that the $S$-restricted diagonal condition holds if for some constant $\varphi(S)>0$

is positive semi-definite. Here $\iota:=(1,\ldots,1)^{T}$ (so $\iota_{j,S}={\rm l}\{j\in S\}$).

We now show that coherence conditions actually imply restricted regression conditions. First, we consider some matrix norms in more detail. Let $1\leq q\leq\infty$, and $r$ be its conjugate, i.e.,

Some properties. The quantity $\|\Sigma_{1,2}({\cal N})\|_{2,2}^{2}$ is the largest eigenvalue of the matrix $\Sigma_{1,2}({\cal N})\Sigma_{2,1}({\cal N})$. We further have for $1\leq q<\infty$,

so for replacing $\|\Sigma_{1,2}({\cal N})\|_{2,\infty}$ by $\|\Sigma_{1,2}({\cal N})\|_{2,q}$, $q<\infty$, one might have to pay a price.

For all $1\leq q\leq\infty$, the following inequality holds:

Proof of Lemma 4.1. Take $r$ such that $1/q+1/r=1$. Let ${\cal N}\supset S$, with $|{\cal N}|=s$ and let $\beta\in{\cal R}_{\rm adaptive}(S,{\cal N})$.

We let $f_{\cal N}:=f_{\beta_{\cal N}}$, $f_{{\cal N}^{c}}:=f_{\beta_{{\cal N}^{c}}}$.

One of the consequences is in the spirit of the mutual coherence condition in Bunea et al. 2007b.

With $q=1$ and $N=s$, the coherence lemma is similar to the cumulative local coherence condition in Bunea et al. 2007c. We also consider the case $N=2s$.

The coherence lemma with $q=2$ is a condition about eigenvalues (recall that $\|\Sigma_{1,2}({\cal N})\|_{2,2}^{2}$ equals the largest eigenvalue of $\Sigma_{1,2}({\cal N})\Sigma_{2,1}({\cal N})$). The bound is then much rougher than the one following from the weak $(S,2s)$-restricted isometry condition, which we derive in Lemma 7.1.

The adaptive (S,s)(S,s)-restricted regression condition implies the (S,s)(S,s)-uniform irrepresentable condition

(Use Cauchy-Schwarz inequality for bounding the first factor). Furthermore, for any constant $c$,

Take $c=\sqrt{s}\|\beta_{S}\|_{2}$ to find

The (S,s)(S,s)-irrepresentable condition is sufficient and essentially necessary for variable selection

An important characterization of the solution $\beta^{*}$ can be derived from the Karush-Kuhn-Tucker (KKT) conditions which in our context involves subdifferential calculus: see Bertsimas and Tsitsiklis 1997.

Here $\|\tau^{*}\|_{\infty}\leq 1$, and moreover

For ${\cal N}\supset S$, we write the projection of a function $f$ on the space spanned by $\{\psi_{j}\}_{j\in{\cal N}}$ as $f^{P_{\cal N}}$, and the anti-projection as $f^{A_{\cal N}}:=f-f^{P_{\cal N}}$. Hence, we note that

Suppose $\Sigma_{1,1}^{-1}({\cal N})$ exists. We have

Proof of Lemma 6.1. By the KKT conditions, we must have

(leaving the second equality untouched). Hence, multiplying the first equality by $-(\beta_{{\cal N}^{c}}^{*})^{T}\Sigma_{2,1}({\cal N})$, and the second by $(\beta_{{\cal N}^{c}}^{*})^{T}$,

where we invoked that $\beta_{j}^{*}\tau_{j}^{*}=|\beta_{j}^{*}|$. Adding up the two equalities gives

We now connect the irrepresentable condition to variable selection. Define

Part 1. Suppose the $(S,N)$-uniform irrepresentable condition holds. Then $|S_{*}\backslash S|\leq N-s$. Part 2. Suppose the $(S,N)$-irrepresentable condition holds and

Then $S_{*}\supset S$ and $|S_{*}|\leq N$. Part 3. Conversely, suppose that $S_{*}\supset S$ and $|S_{*}|\leq N$, and $\Lambda(S,N)>0$. Then

then $\tau_{S_{*}}^{*}=\tau_{S_{*}}^{0}$, where $\tau_{S_{*}}^{0}:={\rm sign}(\beta_{S_{*}}^{0})$.

A special case is $N=s$. In Part 1, we then obtain that $S_{*}\subset S$, i.e., no false positive selections. Moreover, Part 2 then proves $S_{*}=S$ and Part 3 assumes $S_{*}=S$.

Part 1. Let ${\cal N}\supset S$ be a set of size at most $N$, such that

By Lemma 6.1, we now have that if $\|\beta_{{\cal N}^{c}}^{*}\|_{1}>0$

which is a contradiction. Hence $\|\beta_{{\cal N}^{c}}^{*}\|_{1}=0$, i.e., $S_{*}\subset{\cal N}$.

Part 3. Because $\Lambda(S,N)>0$, and $|S_{*}|\leq N$, we know that $\Sigma_{1,1}^{-1}(S_{*})$ exists. Because $S_{*}\supset S$, we have $\beta_{S_{*}^{c}}^{*}=\beta_{S_{*}^{c}}^{0}=0$, so the KKT conditions take the form

and, inserting this in the second KKT equality,

So when $|\beta^{0}|_{\rm min}>\lambda\sqrt{N}/(2\Lambda^{2}(S,N))$, we have $\tau_{S_{*}}^{*}=\tau_{S_{*}}^{0}$.

The weak (S,2​s)(S,2s)-restricted isometry property implies the (S,2​s)(S,2s)-restricted regression condition

Proof of Lemma 7.1. Let $\beta$ be an arbitrary vector. satisfying $\|\beta_{S^{c}}\|_{1}\leq\sqrt{s}\|\beta_{S}\|_{2}$. From Lemma 2.2,

Hence, using the definition of the restricted orthogonality constant $\theta(S,2s)$, and of the $(S,2s)$-uniform eigenvalue $\Lambda^{2}(S,2s)$,

Together with Corollary 3.1, we can now conclude that when $\vartheta_{\rm weak-RIP}(S,2s)<1/L$, one has

This result is from Koltchinskii 2009a and Bickel et al. 2009.

The restricted isometry property with small constants implies the weak (S,2​s)(S,2s)-irrepresentable condition

We start with two preparatory lemmas. Recall that

where $A_{S}$ denotes the anti-projection defined in Section 6.

The next result shows that if the constants are small enough, then there will be no more than $s$ false positives. We define

For $j\in S_{*}\backslash S$ we have by the KKT conditions

Suppose now that $|S_{*}\backslash S|\geq s$. Then there is a subset ${\cal N}^{\prime}$ of $S_{*}\backslash S$, with size $|{\cal N}^{\prime}|=s$, and we have

This is a contraction, and hence $|S_{*}\backslash S|<s$. $\sqcup\mkern-12.0mu\sqcap$

Suppose that $\alpha(S)<1$, see (4). Then the weak $(S,2s)$-irrepresentable condition holds.

Proof of Theorem 8.1. As $\alpha(S)<1$, we know that $\phi(S,2s)>0$. Take an arbitrary $\tau_{S}^{0}\in\{-1,1\}^{s}$, and a $\beta_{0}$ satisfying $\beta_{S}^{0}=\beta^{0}$, ${\rm sign}(\beta_{S}^{0})=\tau_{S}^{0}$, and

Hence, we must have $S_{*}\supset S$, and $\tau_{S}^{*}=\tau_{S}^{0}$. Moreover, by Lemma 8.3, $|S_{*}|<2s$. By Part 3 of Lemma 6.2, we must have

Since $\tau_{S}^{0}=\tau_{S}^{*}$ is arbitrary and $\tau_{S_{*}}^{*}\in\{-1,1\}^{|S_{*}|}$, we conclude that the weak $(S,2s)$-irrepresentable condition holds (in fact the weak $(S,2s-1)$-irrepresentable condition holds).

The RIP is the condition $\vartheta_{\rm RIP}<1$, or equivalently

Candès and Tao 2005 show that $\delta_{2s}\leq\theta_{s}+\delta_{s}$. The restricted isometry constant $\delta_{s}$ has to be less than one, so we may use the bound $1+\delta_{s}\leq 2$. Moreover, it is clear that $\theta(S,N)\leq\theta_{s,N}$, and $\Lambda^{2}(S,N)\geq 1-\delta_{N}$. Inserting these bounds in Corollary 7.1 we find

For example, if $\delta_{s}\leq\sqrt{2}-1$ and $\theta_{s,2s}\leq{1\over 16}$, we get (invoking $\theta_{s,s}\leq\theta_{s,2s}$)

We conclude that the RIP with small enough constants implies the weak $(S,2s)$-irrepresentable condition.

As Candès and Tao 2005 show, the RIP implies exact recovery. To complete the picture, we now show that the $(S,s)$-irrepresentable condition also implies exact recovery.

where, as before $f^{0}=f_{\beta^{0}}$ with $\beta^{0}=\beta_{S}^{0}$. Let $\beta^{\rm LP}$ be the minimizer of the linear programming problem.

Suppose the $(S,s)$-irrepresentable condition holds. Then one has exact recovery, i.e., $\beta^{\rm LP}=\beta^{0}$.

Proof of Lemma 8.4. This follows from Candès and Tao 2005. They show that $\beta^{\rm LP}=\beta^{0}$ if one can find a $g\in L_{2}(P)$, such that (i) $(\psi_{j},g)=\tau_{j}^{0}$, for all $j\in S$, (ii) $|(\psi_{j},g)|<1$ for all $j\notin S$, where, as before, $\tau_{S}^{0}:={\rm sign}(\beta_{S}^{0})$. The $(S,s)$-irrepresentable condition says that this is true for $g=f_{b_{S}}$, where $b_{S}=\Sigma_{1,1}^{-1}(S)\tau_{S}^{0}$. $\sqcup\mkern-12.0mu\sqcap$

The (S,s)(S,s)-uniform irrepresentable condition implies the SS-compatibility condition

By multiplying by $(\beta_{S}^{\diamond})^{T}$, we obtain

The restriction $\|\beta_{S}^{\diamond}\|_{1}=1$ gives

Hence, by multiplying with $(\tau_{S}^{\diamond})^{T}$,

Here, we applied that the $(S,s)$-uniform irrepresentable condition, with $\vartheta=\vartheta_{\rm irrepresentable}(S,s)$, and the condition $\|\beta_{S^{c}}\|_{1}\leq L$. Thus

Because $1-L\vartheta>0$ and $(\tau_{S}^{\diamond})^{T}\Sigma_{1,1}^{-1}(S)\tau_{S}^{\diamond}\geq 0$, this implies that $\lambda<0$, and in fact that

where $(f_{S^{c}}^{\diamond})^{P_{S}}$ is the projection of $f_{S^{c}}^{\diamond}$ on the space spanned by $\{\psi_{k}\}_{k\in S}$. Again, by the $(S,s)$-uniform irrepresentable condition and by $\|\beta_{S^{c}}^{\diamond}\|_{1}\leq L$,

Finally note that $\|f^{\diamond}\|^{2}=\phi_{\rm compatible}^{2}(L,S)/s$. $\sqcup\mkern-12.0mu\sqcap$

Verifying the compatibility and restricted eigenvalue condition

A first, rather trivial, observation is that if $\Sigma$ is non-singular, the restricted eigenvalue condition holds for all $L$, $S$ and $N$, with $\phi^{2}(L,S,N)\geq\Lambda_{\rm min}^{2}(\Sigma)$, the latter being the smallest eigenvalue of $\Sigma$. If $\Sigma$ is the population covariance matrix of a random design, i.e., the probability measure $Q$ is the theoretical distribution of observed co-variables in ${\cal X}$, assuming positive definiteness of $\Sigma$ is not very restrictive. We will present some examples in Section 10.2. Compatibility conditions for the population Gram matrix are of direct relevance if one replaces $L_{2}$-loss by robust convex loss (van de Geer 2008). But, as we will show in the next subsection, even if $\Sigma$ corresponds to the empirical covariance matrix of a fixed design, i.e., the measure $Q$ is the empirical measure $Q_{n}$ of $n$ observed co-variables in ${\cal X}$, the compatibility and restricted eigenvalue condition is often “inherited” from the population version. Therefore, even for fixed designs (and singular $\Sigma$), the collection of cases where compatibility or restricted eigenvalue conditions hold is quite large.

For two (positive semi-definite) matrices $\Sigma_{0}$ and $\Sigma_{1}$, we define the supremum distance

and similarly, $\forall\ {\cal N}\supset S,\ |{\cal N}|=N$, and $\forall\ \beta\in{\cal R}(L,S,{\cal N})$,

and $\forall\ {\cal N}\supset S,\ |{\cal N}|=N$, and $\forall\ \beta\in{\cal R}_{\rm adaptive}(L,S,{\cal N})$,

But if $\beta\in{\cal R}(L,S)$, it holds that $\|\beta_{S^{c}}\|_{1}\leq L\|\beta_{S}\|_{1}$, and hence

The second result can be shown in the same way, and the third result as well as for $\beta\in{\cal R}_{\rm adaptive}(L,S,{\cal N})$, it holds that $\|\beta_{S^{c}}\|_{1}\leq L\sqrt{s}\|\beta_{S}\|_{2}$, and hence

and the same result holds for the adaptive version.

where ${\bf X}=(X_{i,j})$ is a $(n\times p)$-matrix whose columns consist of i.i.d. ${\cal N}(0,1)$-distributed entries (but allowing for dependence between columns). We denote by $\Sigma$ the population covariance matrix of a row of ${\bf X}$. Using a union bound, it is not difficult to show that for all $t>0$, and for

This implies that if the smallest eigenvalue $\Lambda_{\rm min}^{2}(\Sigma)$ of $\Sigma$ is bounded away from zero, and if the sparsity $s$ is of smaller order $o(\sqrt{n/\log p})$, then the restricted eigenvalue condition holds with constant $\phi(S,N)$ not much smaller than $\Lambda_{\rm min}(\Sigma)$. The result can be extended to distributions with Gaussian tails.

2 Some examples

In the following, our discussion mainly applies for $\Sigma$ being the population covariance matrix. For $\Sigma$ being the empirical covariance matrix, the assumptions in the discussion below are unrealistic, but as seen in the previous section, the population properties can have important implications for the restricted eigenvalues of the empirical covariance matrix.

with $0<\rho<1$, and $\iota:=(1,\ldots,1)^{T}$ a vector of 1’s. Then the smallest eigenvalue of $\Sigma$ is $\Lambda_{\rm min}^{2}(\Sigma)=1-\rho$, so the $(L,S,N)$-restricted eigenvalue condition holds with $\phi^{2}(L,S,N)\geq 1-\rho$. The uniform $(S,s)$-irrepresentable condition is always met. The largest eigenvalue of $\Sigma$ is $(1-\rho)+\rho p$. Hence, the restricted isometry constants $\delta_{s}$ are defined only for $\rho<1/(s-1)$.

In this example, $\Sigma$ is a Toeplitz matrix, defined as follows. Consider a positive definite function

which is symmetric ($R(k)=R(-k)$) and sufficiently regular in the following sense. The corresponding spectral density

is assumed to exist, to be continuous and periodic, and

is assumed unique, with $f(\gamma_{0})=M>0$. Moreover, we suppose that $f_{\rm spec}(\cdot)$ is $(2\alpha)$ continuously differentiable at $\gamma_{0}$, with $f^{(2\alpha)}(\gamma_{0})>0$. A Toeplitz matrix is

where $R(\cdot)$ satisfies the conditions described above (in terms of the spectral density). A special case arises with $\sigma_{j,k}=\rho^{|j-k|}$ for some $0\leq\rho<1$. The smallest eigenvalue $\Lambda_{\rm min}^{2}(\Sigma)$ of $\Sigma$ is bounded away from zero where the bound is independent of $p$ (Parter 1961).

Consider a matrix $\Sigma$ which is of block structure form:

where the $\Sigma_{j}$ are $(m\times m)$ covariance matrices ($j=1,\ldots,k$) (the restriction to having the same dimension $m$ can be easily dropped) and $km=p$. If the minimal eigenvalues satisfy

then the minimal eigenvalue of $\Sigma$ is also bounded from below by $\eta^{2}>0$. When $m$ is much smaller than $p$, it is (much) less restrictive that small $m\times m$ covariance matrices $\Sigma_{j}$ have well-behaved minimal eigenvalues than large $p\times p$ matrices.

This example presents a case where the compatibility condition holds, but where the uniform irrepresentable constant is very large. We also calculate the adaptive restricted regression. Let the first $s$ indices $\{1,\ldots,s\}$ be the active set $S$ and suppose that

where $I$ is the $(s\times s)$-identity matrix, and

with $0\leq\rho<1$, and with $b_{1}$ an $s$-vector and $b_{2}$ a $(p-s)$-vector, satisfying $\|b_{1}\|_{2}=\|b_{2}\|_{2}=1$. Moreover, $\Sigma_{2,2}$ is some $(p-s)\times(p-s)$-matrix, with ${\rm diag}(\Sigma_{2,2})=I$, and with smallest eigenvalue $\Lambda_{\rm min}^{2}(\Sigma_{2,2})$. One easily verifies that

Moreover, for $b_{1}:=(1,1,\ldots,1)^{T}/\sqrt{s}$ and $b_{2}:=(1,0,\ldots,0)^{T}$, and $\rho>1/\sqrt{s}$, the $(S,s)$-uniform irrepresentable condition does not hold, as in that case

However, for any $N>s$, the $(S,N)$-uniform irrepresentable condition does hold. We moreover have

i.e. (since $\Lambda(S,s)=1$), the bounds of Lemma 4.1 and Theorem 5.1 are strict in this example.

We recall that $\phi_{\rm compatible}(S)\geq\phi(S,s)$. Here is an example where the compatibility condition holds with reasonable $\phi_{\rm compatible}^{2}(S)$, but where the restricted eigenvalue $\phi^{2}(S,s)$ is very small. Assume $s>2$. Let the first $s$ indices $\{1,\ldots,s\}$ be the active set $S$ with corresponding $(s\times s)$ covariance matrix $\Sigma_{1,1}$, and suppose that

Hence, for example when $1-\rho=3/(s-2)$, we get

Clearly, for large $s$, this means that $\phi_{\rm compatible}(S)$ is much better behaved than $\phi(S,s)$. Note that large $s$ in this example (with $1-\rho=3/(s-2)$) corresponds to a correlation $\rho$ close to one, i.e., to a case where $\Sigma$ is “almost” singular.

Adding noise

where $Q_{n}$ is the empirical measure $Q_{n}:=\sum_{i=1}^{n}\delta_{X_{i}}/n$. The $L_{2}(Q_{n})$-norm is denoted by $\|\cdot\|_{n}$. We moreover let $(\cdot,\cdot)_{n}$ be the $L_{2}(Q_{n})$-inner product.

As before, we write $f^{0}=f_{\beta^{0}}$ and now, $\hat{f}=f_{\hat{\beta}}$. We consider

as the noise. Moreover, we write (with some abuse of notation)

Here is a simple example which shows how $\lambda_{0}$ behaves in the case of i.i.d. standard normal errors.

Suppose that $\epsilon_{1},\ldots,\epsilon_{n}$ are i.i.d. ${\cal N}(0,1)$-distributed, and that $\hat{\sigma}_{j,j}=1$ for all $j$. Then we have for all $t>0$, and for

Proof. As $\hat{\sigma}_{j,j}=1$, we know that $V_{j}:=\sqrt{n}(\psi_{j},\epsilon)_{n}$ is ${\cal N}(0,1)$-distributed. So

Take $\lambda>\lambda_{0}$, and define $L:=(\lambda+\lambda_{0})/(\lambda-\lambda_{0})$. Then

Now, insert $\lambda=\lambda_{0}{(L+1)/(L-1)}$. $\sqcup\mkern-12.0mu\sqcap$

Observe that the $S$-compatibility condition now involves the matrix $\hat{\Sigma}$, which is definitely singular when $p>n$. However, we have seen in the previous section that, also for such $\hat{\Sigma}$, compatibility conditions and restricted eigenvalue conditions hold in fairly general situations.

2 Noisy KKT

The KKT conditions in the noisy case become

where $\|\hat{\tau}\|_{\infty}\leq 1$, and $\hat{\tau}_{j}:={\rm sign}(\hat{\beta}_{j})$ whenever $\hat{\beta}_{j}\not=0$.

To avoid too many repetitions, let us only formulate the noisy version of a part of Part 1 of Lemma 6.2.

Take $\lambda>\lambda_{0}$, and define $L:=(\lambda+\lambda_{0})/(\lambda-\lambda_{0})$. Suppose the uniform $(\hat{\Sigma},L,S,s)$-irrepresentable condition holds. Then $\hat{S}\subset S$.

Proof of Lemma 11.3. This follows from a straightforward generalization of Lemma 6.1, where the equalities now become inequalities:

Here, $f^{\hat{A}_{S}}$ is the anti-projection of $f$, in $L_{2}(Q_{n})$, on the space spanned by $\{\psi_{j}\}_{j\in S}$.

Take $\lambda>\lambda_{0}$, and define $L:=(\lambda+\lambda_{0})/(\lambda-\lambda_{0})$. Suppose that

We conclude that the KKT conditions in the noisy case can be exploited in the same way as in the case without noise, albeit that one needs to adjust the constants (making the conditions more restrictive).

Discussion

We show how various conditions for Lasso oracle results relate to each other, as illustrated in Figure 1. Thereby, we also introduce the restricted regression condition.

For deriving oracle results for prediction and estimation, the compatibility condition is the weakest. Looking at the derivation of the oracle result in Lemma 2.1, no substantial room seems to be left to improve the condition. The restricted eigenvalue condition is slightly stronger but in some cases, as demonstrated in Example 10.5, the compatibility condition is a real improvement.

For variable selection with the Lasso, the irrepresentable condition is sufficient (assuming sufficiently large non-zero regression coefficients) and essentially necessary. We present the, perhaps not unexpected, but as yet not formally shown, result that the irrepresentable condition is always stronger than the compatibility condition.

We illustrate in Section 10 how - in theory - one can verify the compatibility condition. If the sparsity is of small order $o(\sqrt{n/\log p})$, we can approximate the empirical Gram matrix by the population analogue. It is then much more easy and realistic that the population Gram matrix has sufficiently regular behavior, as illustrated with our examples in Section 10.2. We believe moreover that a sparsity bound of small order $o(\sqrt{n/\log p})$ covers a large area of interesting statistical problems. With larger $s$, the statistical situation is comparable to one of a nonparametric model with “(effective) smoothness less than 1/2”, leading to very slow convergence rates. In contrast, for example in decoding problems, sparseness up to the linear-in-$n$ regime can be very important. Moreover, in the case of robust convex loss, one may apply the compatibility condition directly to the population matrix, i.e., the sparsity regime $s=o(\sqrt{n/\log p})$ can be relaxed for such loss functions (see van de Geer 2008). We therefore conclude that oracle results for the Lasso hold under quite general design conditions.

A final remark is that in our formulation, the compatibility condition and restricted eigenvalue condition depend on the sparsity $s$ as well as on the active set $S$. As $S$ is unknown, this means that for a practical guarantee, the conditions should hold for all $S$. Moreover, one then needs to assume the sparsity $s$ to be known, or at least a good upper bound needs to be given. Such strong requirements are the price for practical verifiability. We however believe that in statistical modeling, non-verifiable conditions are allowed and in fact common practice. Moreover, our model assumes a sparse linear “truth” with “true” active set $S$, only for simplicity. Without such assumptions, there is no “true” $S$, and the oracle inequality concerns a trade-off between sparse approximation and estimation error, see for example van de Geer 2008.

References