Simultaneous analysis of Lasso and Dantzig selector

Introduction

Let us specialize to the case of linear regression with many covariates, \mbox{\boldmathy}=X\beta+\mbox{\boldmathw} where $X$ is the $n\times M$ deterministic design matrix, with $M$ possibly much larger than $n$, and $w$ is a vector of i.i.d. standard normal random variables. This is the situation considered most recently by Candes and Tao ct07 and Meinshausen and Yu my06. Here sparsity specifies that the high-dimensional vector $\beta$ has coefficients that are mostly 0.

In the nonparametric regression model, we prove sparsity oracle inequalities for the Dantzig selector, that is, bounds on the prediction loss in terms of the best possible (oracle) approximation under the sparsity constraint.

Similar sparsity oracle inequalities are proved for the Lasso in the nonparametric regression model, and this is done under more general assumptions on the design matrix than in btw07.

We prove that, for nonparametric regression, the Lasso and the Dantzig selector are approximately equivalent in terms of the prediction loss.

We begin, in the next section, by defining the Lasso and Dantzig procedures and the notation. In Section 3 we present our key geometric assumptions. Some sufficient conditions for these assumptions are given in Section 4, where they are also compared to those of ct07 and my06 as well as to ones appearing in btw07 and btw06b. We note a weakness of our assumptions, and hence of those in the papers we cited, and we discuss a way of slightly remedying them. Sections 5, 6 give some equivalence results and sparsity oracle inequalities for the Lasso and Dantzig estimators in the general nonparametric regression model. Section 7 focuses on the linear regression model and includes a final discussion. Two important technical lemmas are given in Appendix B as well as most of the proofs.

Definitions and notation

Let $(Z_{1},Y_{1}),$ $\ldots,(Z_{n},Y_{n})$ be a sample of independent random pairs with

Depending on the statistical targets, the dictionary $\mathcal{F}_{M}$ can contain qualitatively different parts. For instance, it can be a collection of basis functions used to approximate $f$ in the nonparametric regression model (e.g., wavelets, splines with fixed knots, step functions). Another example is related to the aggregation problem where the $f_{j}$ are estimators arising from $M$ different methods. They can also correspond to $M$ different values of the tuning parameter of the same method. Without much loss of generality, these estimators $f_{j}$ are treated as fixed functions: the results are viewed as being conditioned on the sample the $f_{j}$ are based on.

The selection of the dictionary can be very important to make the estimation of $f$ possible. We assume implicitly that $f$ can be well approximated by a member of the span of $\mathcal{F}_{M}$. However this is not enough. In this paper, we have in mind the situation where $M\gg n$, and $f$ can be estimated reasonably only because it can approximated by a linear combination of a small number of members of $\mathcal{F}_{M}$, or in other words, it has a sparse approximation in the span of ${\mathcal{F}}_{M}$. But when sparsity is an issue, equivalent bases can have different properties: a function which has a sparse representation in one basis may not have it in another one, even if both of them span the same linear space.

Consider the matrix $X=(f_{j}(Z_{i}))_{i,j}$, $i=1,\dots,n$, $j=1,\dots,M$ and the vectors \mbox{\boldmathy}=(Y_{1},\dots,Y_{n})^{T}, {\mbox{\boldmathf}}=(f(Z_{1}),\dots,f(Z_{n}))^{T}, \mbox{\boldmathw}=(W_{1},\dots,W_{n})^{T}. With this notation,

where $r>0$ is some tuning constant, and introduce the corresponding Lasso estimator

The criterion in (2.1) is convex in $\beta$, so that standard convex optimization procedures can be used to compute $\widehat{\beta}_{L}$. We refer to os00a; os00b; ehjt04; t05; fjht07; mvb08 for detailed discussion of these optimization problems and fast algorithms.

A necessary and sufficient condition of the minimizer in (2.1) is that 0 belongs to the subdifferential of the convex function $\beta\mapsto n^{-1}|y-X\beta|_{2}^{2}+2r|D^{1/2}\beta|_{1}$. This implies that the Lasso selector $\widehat{\beta}_{L}$ satisfies the constraint:

where $\widehat{\beta}_{D}=(\widehat{\beta}_{1,D},\dots,\widehat{\beta}_{M,D})$ is the Dantzig selector. By the definition of Dantzig selector, we have $|\widehat{\beta}_{D}|_{1}\leq|\widehat{\beta}_{L}|_{1}$.

The Dantzig selector is computationally feasible, since it reduces to a linear programming problem ct07.

Finally for any $n\geq 1$, $M\geq 2$, we consider the Gram matrix

and let $\phi_{\max}$ denote the maximal eigenvalue of $\Psi_{n}$.

Restricted eigenvalue assumptions

We now introduce the key assumptions on the Gram matrix that are needed to guarantee nice statistical properties of Lasso and Dantzig selector. Under the sparsity scenario we are typically interested in the case where $M>n$, and even $M\gg n$. Then the matrix $\Psi_{n}$ is degenerate, which can be written as

Clearly, ordinary least squares does not work in this case, since it requires positive definiteness of $\Psi_{n}$, i.e.

One of the properties of both the Lasso and the Dantzig selector is that, for the linear regression model, the residuals \mbox{\boldmath\delta}=\hat{\beta}_{L}-\beta and \mbox{\boldmath\delta}=\hat{\beta}_{D}-\beta satisfy, with probability close to 1,

where $J_{0}=J(\beta)$ is the set of non-zero coefficients of the true parameter $\beta$ of the model. For the linear regression model, the vector of Dantzig residuals $\delta$ satisfies (3.2) with probability close 1 if $c_{0}=1$ and $M$ is large (cf. (B.9) and the fact that $\beta$ of the model satisfies the Dantzig constraint with probability close 1 if $M$ is large). A similar inequality holds for the vector of Lasso residuals \mbox{\boldmath\delta}=\widehat{\beta}_{L}-\beta, but this time with $c_{0}=3$, cf. Corollary B.2.

Now, consider for example, the case where the elements of the Gram matrix $\Psi_{n}$ are close to those of a positive definite $M\times M$ matrix $\Psi$. Denote by $\varepsilon_{n}\stackrel{{\scriptstyle\triangle}}{{=}}\max_{i,j}|(\Psi_{n}-\Psi)_{i,j}|$ the maximal difference between the elements of the two matrices. Then for any $\delta$ satisfying (3.2) we get

Thus, for $\delta$ satisfying (3.2) which are the vectors that we have in mind, and for $\varepsilon_{n}|J_{0}|$ small enough, the LHS of (3.3) is bounded away from 0. It means that we have a kind of “restricted” positive definiteness which is valid only for the vectors satisfying (3.2). This suggests the following conditions that will suffice for the main argument of the paper. We refer to these conditions as restricted eigenvalue (RE) assumptions.

For some integer $s$ such that $1\leq s\leq M$, and a positive number $c_{0}$ the following condition holds:

The integer $s$ here plays the role of an upper bound on the sparsity ${\cal M}(\beta)$ of a vector of coefficients $\beta$.

Note that if Assumption $\text{RE}(s,c_{0})$ is satisfied with $c_{0}\geq 1$, then

In words, the square submatrices of size $\leq 2s$ of the Gram matrix are necessarily positive definite. Indeed, suppose that for some \mbox{\boldmath\delta}\neq 0 we have simultaneously {\cal M}(\mbox{\boldmath\delta})\leq 2s and X\mbox{\boldmath\delta}=0. Partition J(\mbox{\boldmath\delta}) in two sets: J(\mbox{\boldmath\delta})=I_{0}\cup I_{1}, such that $|I_{i}|\leq s$, $i=0,1$. Without loss of generality, suppose that |\mbox{\boldmath\delta}_{I_{1}}|_{1}\leq|\mbox{\boldmath\delta}_{I_{0}}|_{1}. Since, clearly, |\mbox{\boldmath\delta}_{I_{1}}|_{1}=|\mbox{\boldmath\delta}_{I_{0}^{c}}|_{1} and $c_{0}\geq 1$, we have |\mbox{\boldmath\delta}_{I_{0}^{c}}|_{1}\leq c_{0}|\mbox{\boldmath\delta}_{I_{0}}|_{1}. Hence $\kappa(s,c_{0})=0$, a contradiction.

Note also that Assumptions $\text{RE}(s^{\prime},c_{0})$ and $\text{RE}(s^{\prime},m,c_{0})$ imply Assumptions $\text{RE}(s,c_{0})$ and $\text{RE}(s,m,c_{0})$ respectively if $s^{\prime}>s$.

Discussion of the RE assumptions

There exist several simple sufficient conditions for Assumptions $\text{RE}(s,c_{0})$ and $\text{RE}(s,m,c_{0})$ to hold. Here we discuss some of them.

For a real number $1\leq u\leq M$ we introduce the following quantities that we will call restricted eigenvalues:

Denote by $X_{J}$ the $n\times|J|$ submatrix of $X$ obtained by removing from $X$ the columns that do not correspond to the indices in $J$, and for $1\leq m_{1},m_{2}\leq M$ introduce the following quantities called restricted correlations:

In Lemma 4.1 below we show that a sufficient condition for $\text{RE}(s,c_{0})$ and $\text{RE}(s,s,c_{0})$ to hold is given, for example, by the following assumption on the Gram matrix.

for some integer $1\leq s\leq M/2$ and a constant $c_{0}>0$.

This condition with $c_{0}=1$ appeared in ct07, in connection with the Dantzig selector. Assumption 1 is more general: we can have here an arbitrary constant $c_{0}>0$ which will allow us to cover not only the Dantzig selector but also the Lasso estimators, and to prove oracle inequalities for the prediction loss when the model is nonparametric.

Our second sufficient condition for $\text{RE}(s,c_{0})$ and $\text{RE}(s,m,c_{0})$ does not need bounds on correlations. Only bounds on the minimal and maximal eigenvalues of “small” submatrices of the Gram matrix $\Psi_{n}$ are involved.

for some integers $s,m$ such that $1\leq s\leq M/2$, $m\geq s$, and $s+m\leq M$, and a constat $c_{0}>0$.

Assumption 2 can be viewed as a weakening of the condition on $\phi_{\min}$ in my06. Indeed, taking $s+m=s\log n$ (we assume w.l.o.g. that $s\log n$ is an integer and $n>3$) and assuming that $\phi_{\max}(\cdot)$ is uniformly bounded by a constant we get that Assumption 2 is equivalent to

where $c>0$ is a constant. The corresponding slightly stronger assumption in my06 is stated in asymptotic form (for $s=s_{n}\to\infty$):

The following two constants are useful when Assumptions 1 and 2 are considered:

The next lemma shows that if Assumptions 1 or 2 are satisfied, then the quadratic form $x^{T}\Psi_{n}x$ is positive definite on some restricted sets of vectors $x$. The construction of the lemma is inspired by Candes and Tao ct07 and covers, in particular, the corresponding result in ct07.

Fix an integer $1\leq s\leq M/2$ and a constant $c_{0}>0$.

The proof of the lemma is given in Appendix A.

There exist other sufficient conditions for Assumptions $\text{RE}(s,c_{0})$ and $\text{RE}(s,m,c_{0})$ to hold. We mention here three of them implying Assumption $\text{RE}(s,c_{0})$. The first one is the following b07.

Assumption 3. For an integer $s$ such that $1\leq s\leq M$ we have

To argue that Assumption 3 implies $\text{RE}(s,c_{0})$ it suffices to remark that

Another type of assumption related to “mutual coherence” det04 is discussed in the connection to Lasso in btw07; btw06b. We state it in two different forms given below.

Assumption 4. For an integer $s$ such that $1\leq s\leq M$ we have

It is easy to see that Assumption 4 implies $\text{RE}(s,c_{0})$. Indeed, if (4.1) holds,

If all the diagonal elements of matrix $X^{T}X/n$ are equal to 1 (and thus $\theta_{1,1}$ coincides with the mutual coherence det04), a simple sufficient condition for Assumption $\text{RE}(s,c_{0})$ to hold is stated as follows.

Assumption 5. All the diagonal elements of the Gram matrix $\Psi_{n}$ are equal to 1 and for an integer $s$ such that $1\leq s\leq M$ we have

In fact, separating the diagonal and off-diagonal terms of the quadratic form we get

Combining this inequality with (4.2) we see that Assumption $\text{RE}(s,c_{0})$ is satisfied whenever (4.3) holds.

Unfortunately, Assumption $\text{RE}(s,c_{0})$ has some weakness. Let, for example, $f_{j}$, $j=1,\dots,2^{m}-1$, be the Haar wavelet basis on $$($M=2^{m}$) and consider$Z_{i}=i/n$,$i=1,\dots,n$. If$M\gg n$, it is clear that$\phi_{\min}(1)=0$since there are functions$f_{j}$on the highest resolution level whose supports (of length$M^{-1}$) contain no points$Z_{i}$. So, none of the Assumptions 1 – 4 holds. A less severe although similar situation is when we consider step functions:$f_{j}(t)=I_{\{t$for$t\in$. It is clear that$\phi_{\min}(2)=O(1/M)$, although sparse representation in this basis is very natural. Intuitively, the problem arises only because we include very high resolution components. Therefore, we may try to restrict the set$J_{0}$in$\text{RE}(s,c_{0})$to low resolution components, which is quite reasonable because the “true” or “interesting” vectors of parameters$\beta$are often characterized by such$J_{0}$. This idea is formalized in Section 6, cf. Corollary 6.2, see also a remark after Theorem 7.2 in Section 7.

Approximate equivalence

In this section we prove a type of approximate equivalence between the Lasso and the Dantzig selector. It is expressed as closeness of the prediction losses $\|\widehat{f}_{D}-f\|_{n}^{2}$ and $\|\widehat{f}_{L}-f\|_{n}^{2}$ when the number of non-zero components of the Lasso or the Dantzig selector is small as compared to the sample size.

Let $W_{i}$ be independent ${\mathcal{N}}(0,\sigma^{2})$ random variables with $\sigma^{2}>0$. Fix $n\geq 1$, $M\geq 2$. Let Assumption $\text{RE}(s,1)$ be satisfied with $1\leq s\leq M$. Consider the Dantzig estimator $\widehat{f}_{D}$ defined by (2.5) – (2.4) with

where $A>2\sqrt{2}$, and the Lasso estimator $\widehat{f}_{L}$ defined by (2.1) – (2.2) with the same $r$.

If ${\cal M}(\widehat{\beta}_{L})\leq s$, then with probability at least $1-M^{1-A^{2}/8}$ we have

Note that the RHS of (5.1) is bounded by a product of three factors (and a numerical constant which, unfortunately, equals at least 128). The first factor, ${\cal M}(\widehat{\beta}_{L})\sigma^{2}/n\leq s\sigma^{2}/n$, corresponds to the error rate for prediction in regression with $s$ parameters. The two other factors, $\log M$ and $f^{2}_{\max}/\kappa^{2}(s,1)$, can be regarded as a price to pay for the large number of regressors. If the Gram matrix $\Psi_{n}$ equals the identity matrix (the white noise model), then there is only the $\log M$ factor. In the general case, there is another factor, $f^{2}_{\max}/\kappa^{2}(s,1)$ representing the extent to which the Gram matrix is ill-posed for estimation of sparse vectors.

We also have the following result that we state for simplicity under the assumption that $\|f_{j}\|_{n}=1,\ j=1,\ldots,M$. It gives a bound in the spirit of Theorem 5.1 but with ${\cal M}(\widehat{\beta}_{D})$ rather than ${\cal M}(\widehat{\beta}_{L})$ on the right hand side.

Let the assumptions of Theorem 5.1 hold, but with $\text{RE}(s,5)$ in place of $\text{RE}(s,1)$, and let $\|f_{j}\|_{n}=1,\ j=1,\ldots,M$. If ${\cal M}(\widehat{\beta}_{D})\leq s$, then with probability at least $1-M^{1-A^{2}/8}$ we have

Remark. The approximate equivalence is essentially that of the rates as Theorem 5.1 exhibits. A statement free of ${\cal M}(\beta)$ holds for linear regression, see discussion after Theorem 7.2 and Theorem 7.3 below.

Oracle inequalities for prediction loss

Here we prove sparsity oracle inequalities for the prediction loss of Lasso and Dantzig estimators. These inequalities allow us to bound the difference between the prediction errors of the estimators and the best sparse approximation of the regression function (by an oracle that knows the truth, but is constrained by sparsity). The results of this section, together with those of Section 5, show that the distance between the prediction losses of Dantzig and Lasso estimators is of the same order as the distances between them and their oracle approximations.

A general discussion of sparsity oracle inequalities can be found in t06. Such inequalities have been recently obtained for the Lasso type estimators in a number of settings btw04; btw06a; btw07; btw06b; btw07a; k06; vdg06. In particular, the regression model with fixed design that we study here is considered in btw04; btw06a; btw07. The assumptions on the Gram matrix $\Psi_{n}$ in btw04; btw06a; btw07 are more restrictive than ours: in those papers either $\Psi_{n}$ is positive definite or a mutual coherence condition similar to (4.3) is imposed.

Let $W_{i}$ be independent ${\mathcal{N}}(0,\sigma^{2})$ random variables with $\sigma^{2}>0$. Fix some $\varepsilon>0$ and integers $n\geq 1$, $M\geq 2$, $1\leq s\leq M$. Let Assumption $\text{RE}(s,(3+4/\varepsilon)f_{\max}/f_{\min})$ be satisfied. Consider the Lasso estimator $\widehat{f}_{L}$ defined by (2.1) – (2.2) with

for some $A>2\sqrt{2}$. Then, with probability at least $1-M^{1-A^{2}/8}$, we have

where $\kappa=\kappa(s,(3+4/\varepsilon)f_{\max}/f_{\min})$, and $C(\varepsilon)>0$ is a constant depending only on $\varepsilon$.

We now state as a corollary a softer version of Theorem 6.1 that can be used to eliminate the pathologies mentioned at the end of Section 4. For this purpose we define

In similar way, we define ${\mathcal{J}}_{s,\gamma,m,c_{0}}$ and $\Lambda_{s,\gamma,m,c_{0}}$ corresponding to Assumption $\text{RE}(s,m,c_{0})$.

Let $W_{i}$, $s$ and the Lasso estimator $\widehat{f}_{L}$ be the same as in Theorem 6.1. Then, for all $n\geq 1$, $\varepsilon>0$, and $\gamma>0$, with probability at least $1-M^{1-A^{2}/8}$ we have

where $\bar{\Lambda}_{s,\gamma,\varepsilon}=\{\beta\in\Lambda_{s,\gamma,(3+4/\varepsilon)f_{\max}/f_{\min}}:\,{\cal M}(\beta)\leq s\}$.

To obtain this corollary it suffices to observe that the proof of Theorem 6.1 goes through if we drop Assumption $\text{RE}(s,(3+4/\varepsilon)f_{\max}/f_{\min})$ but we assume instead that $\beta\in\Lambda_{s,\gamma,(3+4/\varepsilon)f_{\max}/f_{\min}}$ and we replace $\kappa(s,(3+4/\varepsilon)f_{\max}/f_{\min})$ by $\gamma$.

Let $W_{i}$ be independent ${\mathcal{N}}(0,\sigma^{2})$ random variables with $\sigma^{2}>0$. Fix some $\varepsilon>0$ and integers $n\geq 1$, $M\geq 2$. Let $f$ obey the weak sparsity assumption for some $C_{0}<\infty$ and some $s$ such that $1\leq s\max\{C_{1}(\varepsilon),1\}\leq M$ where

and $C(\varepsilon)$, $\kappa$ are the constants in Theorem 6.1. Suppose further that Assumption $\text{RE}(s\max\{C_{1}(\varepsilon),1\},(3+4/\varepsilon)f_{\max}/f_{\min})$ is satisfied. Consider the Dantzig estimator $\widehat{f}_{D}$ defined by (2.5) – (2.4) with

and $A>2\sqrt{2}$. Then, with probability at least $1-M^{1-A^{2}/8}$, we have

Here $C_{2}(\varepsilon)=16C_{1}(\varepsilon)+C(\varepsilon)$ and $\kappa_{0}=\kappa(\max(C_{1}(\varepsilon),1)s,(3+4/\varepsilon)f_{\max}/f_{\min})$.

Special case: parametric estimation in linear regression

In this section we assume that the vector of observations \mbox{\boldmathy}=(Y_{1},\dots,Y_{n})^{T} is of the form

We consider dimension $M$ that can be of order $n$ and even much larger. Then $\beta^{*}$ is, in general, not uniquely defined. For $M>n$, if (7.1) is satisfied for $\beta^{*}=\beta_{0}$ there exists an affine space ${\cal U}=\{\beta^{*}:X\beta^{*}=X\beta_{0}\}$ of vectors satisfying (7.1). The results of this section are valid for any $\beta^{*}$ such that (7.1) holds. However, we will suppose that Assumption $\text{RE}(s,c_{0})$ holds with $c_{0}\geq 1$ and that ${\cal M}(\beta^{*})\leq s$. Then the set ${\cal U}\cap\{\beta^{*}:{\cal M}(\beta^{*})\leq s\}$ reduces to a single element (cf. Remark 2 at the end of this section). In this sense, there is a unique sparse solution of (7.1).

Our goal in this section, unlike that of the previous ones, is to estimate both $X\beta^{*}$ for the purpose of prediction and $\beta^{*}$ itself for purpose of model selection. We will see that meaningful results are obtained when the sparsity index ${\cal M}(\beta^{*})$ is small.

It will be assumed throughout this section that the diagonal elements of the Gram matrix $\Psi_{n}=X^{T}X/n$ are all equal to 1 (this is equivalent to the condition $\|f_{j}\|_{n}=1,\ j=1,\ldots,M,$ in the notation of previous sections). Then the Lasso estimator of $\beta^{*}$ in (7.1) is defined by

The correspondence between the notation here and that of the previous sections is the following:

The Dantzig selector for linear model (7.1) is defined by

is the set of all $\beta$ satisfying the Dantzig constraint.

We first get bounds on the rate of convergence of Dantzig selector.

Let $W_{i}$ be independent ${\mathcal{N}}(0,\sigma^{2})$ random variables with $\sigma^{2}>0$, let all the diagonal elements of the matrix $X^{T}X/n$ be equal to 1, and ${\cal M}(\beta^{*})\leq s$, where $1\leq s\leq M$, $n\geq 1$, $M\geq 2$. Let Assumption $\text{RE}(s,1)$ be satisfied. Consider the Dantzig selector $\widehat{\beta}_{D}$ defined by (7.3) with

and $A>\sqrt{2}$. Then, with probability at least $1-M^{1-A^{2}/2}$, we have

If Assumption $\text{RE}(s,m,1)$ is satisfied, then with the same probability as above, simultaneously for all $1<p\leq 2$ we have

Note that, since $s\leq m$, the factor in curly brackets in (7.6) is bounded by a constant independent of $s$ and $m$. Under Assumption 1 in Section 4 with $c_{0}=1$ (which is less general than $\text{RE}(s,s,1)$, cf. Lemma 4.1(i)) a bound of the form (7.6) for the case $p=2$ is established by Candes and Tao ct07.

Bounds on the rate of convergence of the Lasso selector are quite similar to those obtained in Theorem 7.1. They are given by the following result.

Let $W_{i}$ be independent ${\mathcal{N}}(0,\sigma^{2})$ random variables with $\sigma^{2}>0$. Let all the diagonal elements of the matrix $X^{T}X/n$ be equal to 1, and ${\cal M}(\beta^{*})\leq s$ where $1\leq s\leq M$, $n\geq 1$, $M\geq 2$. Let Assumption $\text{RE}(s,3)$ be satisfied. Consider the Lasso estimator $\widehat{\beta}_{L}$ defined by (7.2) with

and $A>2\sqrt{2}$. Then, with probability at least $1-M^{1-A^{2}/8}$, we have

If Assumption $\text{RE}(s,m,3)$ is satisfied, then with the same probability as above, simultaneously for all $1<p\leq 2$ we have

Inequalities of the form similar to (7.7) and (7.8) can be deduced from the results of btw06a under more restrictive conditions on the Gram matrix (the mutual coherence assumption, cf. Assumption 5 of Section 4).

Assumptions $\text{RE}(s,1)$ respectively $\text{RE}(s,3)$ can be dropped in Theorem 7.1 and 7.2 if we assume $\beta^{*}\in\Lambda_{s,\gamma,c_{0}}$ with $c_{0}=1$ or $c_{0}=3$ as appropriate. Then (7.4), (7.5) or respectively (7.7), (7.8) hold with $\kappa=\gamma$. This is analogous to Corollary 6.2. Similarly (7.6) and (7.10) hold with $\kappa=\gamma$ if $\beta^{*}\in\Lambda_{s,\gamma,m,c_{0}}$ with $c_{0}=1$ or $c_{0}=3$ as appropriate.

Observe that combining Theorems 7.1 and 7.2 we can immediately get bounds for the differences between Lasso and Dantzig selector $|\widehat{\beta}_{L}-\widehat{\beta}_{D}|_{p}^{p}$ and $|X(\widehat{\beta}_{L}-\widehat{\beta}_{D})|_{2}^{2}$. Such bounds have the same form as those of Theorems 7.1 and 7.2, up to numerical constants. Another way of estimating these differences follows directly from the proof of Theorem 7.1. It suffices to observe that the only property of $\beta^{*}$ used in that proof is the fact that $\beta^{*}$ satisfies the Dantzig constraint on the event of given probability, which is also true for the Lasso solution $\widehat{\beta}_{L}$. So, we can replace $\beta^{*}$ by $\widehat{\beta}_{L}$ and $s$ by ${\cal M}(\widehat{\beta}_{L})$ everywhere in Theorem 7.1. Generalizing a bit more, we easily derive the following fact.

The result of Theorem 7.1 remains valid if we replace there $|\widehat{\beta}_{D}-\beta^{*}|_{p}^{p}$ by $\sup\{|\widehat{\beta}_{D}-\beta|_{p}^{p}:\,\beta\in\Lambda,{\cal M}(\beta)\leq s\}$ for $1\leq p\leq 2$ and $|X(\widehat{\beta}_{D}-\beta^{*})|_{2}^{2}$ by $\sup\{|X(\widehat{\beta}_{D}-\beta)|_{2}^{2}:\,\beta\in\Lambda,{\cal M}(\beta)\leq s\}$ respectively. Here $\Lambda$ is the set of all vectors satisfying the Dantzig constraint.

Theorems 7.1 and 7.2 only give non-asymptotic upper bounds on the loss, with some probability and under some conditions. The probability depends on $M$ and the conditions depend on $n$ and $M$: recall that Assumptions RE($s,c_{0}$) and RE($s,m,c_{0}$) are imposed on the $n\times M$ matrix $X$. To deduce asymptotic convergence (as $n\to\infty$ and/or as $M\to\infty$) from Theorems 7.1 and 7.2 we would need some very strong additional properties, such as simultaneous validity of Assumption RE($s,c_{0}$) or RE($s,m,c_{0}$) (with one and the same constant $\kappa$) for infinitely many $n$ and $M$.

Note that Assumptions RE($s,c_{0}$) or RE($s,m,c_{0}$) do not imply identifiability of $\beta^{*}$ in the linear model (7.1). However, the vector $\beta^{*}$ appearing in the statements of Theorems 7.1 and 7.2 is uniquely defined because we suppose there in addition that ${\cal M}(\beta^{*})\leq s$ and $c_{0}\geq 1$. Indeed, if there exists a $\beta^{\prime}$ such that $X\beta^{\prime}=X\beta^{*}$, and ${\cal M}(\beta^{\prime})\leq s$ then in view of assumption $\text{RE}(s,c_{0})$ with $c_{0}\geq 1$ we have necessarily $\beta^{*}=\beta^{\prime}$ (cf. discussion following the definition of $\text{RE}(s,c_{0})$). On the other hand, Theorem 7.3 applies to certain values of $\beta$ that do not come from the model (7.1) at all.

For the smallest value of $A$ (which is $A=2\sqrt{2}$) the constants in the bound of Theorem 7.2 for the Lasso are larger than the corresponding numerical constants for the Dantzig selector given in Theorem 7.1, again for the smallest admissible value $A=\sqrt{2}$. On the contrary, the Dantzig selector has certain defects as compared to Lasso when the model is nonparametric, as discussed in Section 6. In particular, to obtain sparsity oracle inequalities for the Dantzig selector we need some restrictions on $f$, for example the weak sparsity property. On the other hand, the sparsity oracle inequality (6.1) for the Lasso is valid with no restriction on $f$.

The proofs of Theorems 7.1 and 7.2 differ mainly in the value of the tuning constant: $c_{0}=1$ in Theorem 7.1 and $c_{0}=3$ in Theorem 7.2. Note that since the Lasso solution satisfies the Dantzig constraint we could have obtained a result similar to Theorem 7.2, though with less accurate numerical constants, by simply conducting the proof of Theorem 7.1 with $c_{0}=3$. However, we act differently: we deduce (B.30) directly from (B.1), and not from (B.25). This is done only for the sake of improving the constants: in fact, using (B.25) with $c_{0}=3$ would yield (B.30) with the doubled constant on the right hand side.

A

Proof of Lemma 4.1. Consider a partition $J_{0}^{c}$ into subsets of size $m$, with the last subset of size $\leq m$: $J_{0}^{c}=\cup_{k=1}^{K}J_{k}$ where $K\geq 1$, $|J_{k}|=m$ for $k=1,\dots,K-1$ and $|J_{K}|\leq m$, such that $J_{k}$ is the set of indices corresponding to $m$ largest in absolute value coordinates of $\delta$ outside $\cup_{j=1}^{k-1}J_{j}$ (for $k<K$) and $J_{K}$ is the remaining subset. We have

We will prove first part (ii) of the lemma. Since for $k\geq 1$ the vector \mbox{\boldmath\delta}_{J_{k}} has only $m$ non-zero components we obtain

Next, as in ct07, we observe that |\mbox{\boldmath\delta}_{J_{k+1}}|_{2}\leq|\mbox{\boldmath\delta}_{J_{k}}|_{1}/\sqrt{m}, $k=1,\dots,K-1$, and therefore

where we used (4.1). From (A.1) – (A.3) we find

The proof of part (i) is analogous. The only difference is that we replace in the above argument $m$ by $s$ and instead of (A.2) we use the following bound (cf. ct07):

B Two lemmata and the proofs of the results

Fix $M\geq 2$ and $n\geq 1$. Let $W_{i}$ be independent ${\mathcal{N}}(0,\sigma^{2})$ random variables with $\sigma^{2}>0$ and let $\widehat{f}_{L}$ be the Lasso estimator defined by (2.2) with

where $\phi_{\max}$ denotes the maximal eigenvalue of the matrix $X^{T}X/n$.

The result (B.1) is essentially Lemma 1 from btw06b. For completeness, we give its proof. Set $r_{n,j}=r\|f_{j}\|_{n}$. By definition,

Define the random variables $V_{j}=n^{-1}\sum_{i=1}^{n}f_{j}(Z_{i})W_{i},\quad 1\leq j\leq M,$ and the event

Using an elementary bound on the tails of Gaussian disribution we find that the probability of the complementary event \mbox{\mathcal{A}}^{c} satisfies

where $\eta\sim{\mathcal{N}}(0,1)$. On the event $\mathcal{A}$ we have

Adding the term $\sum_{j=1}^{M}r_{n,j}|\widehat{\beta}_{j,L}-\beta_{j}|$ to both sides of this inequality yields, on $\mathcal{A}$,

Now, $|\widehat{\beta}_{j,L}-\beta_{j}|+|\beta_{j}|-|\widehat{\beta}_{j,L}|=0$ for $j\not\in J(\beta)$, so that on $\mathcal{A}$ we get (B.1).

To prove (B.2) it suffices to note that on $\mathcal{A}$ we have

Now, \mbox{\boldmathy}={\mbox{\boldmathf}}+\mbox{\boldmathw}, and (B.2) follows from (2.3), (B.5).

We finally prove (B.3). The necessary and sufficient condition for $\widehat{\beta}_{L}$ to be the Lasso solution can be written in the form

where ${\mathbf{x}}_{(j)}$ denotes the $j$th column of $X$, $j=1,\dots,M$. Next, (B.5) yields that on $\mathcal{A}$ we have

Since the matrices $X^{T}X/n$ and $XX^{T}/n$ have the same maximal eigenvalues,

and we deduce (B.3) from the last two displays. ∎

Let the assumptions of Lemma B.1 be satisfied and $\|f_{j}\|_{n}=1,j=1,\dots,M$. Consider the linear regression model \mbox{\boldmathy}=X\beta+\mbox{\boldmathw}. Then, with probability at least $1-M^{1-A^{2}/8}$, we have

where $J_{0}=J(\beta)$ is the set of non-zero coefficients of $\beta$ and \mbox{\boldmath\delta}=\widehat{\beta}_{L}-\beta.

Use the first inequality in (B.1) and the fact that $f=f_{\beta}$ for the linear regression model. ∎

and set \mbox{\boldmath\delta}=\widehat{\beta}_{D}-\beta, $J_{0}=J(\beta)$. Then

Further, let the assumptions of Lemma B.1 be satisfied with $A>\sqrt{2}$. Then with probability of at least $1-M^{1-A^{2}/2}$ we have

Inequality(B.9) follows immediately from the definition of Dantzig selector, cf. ct07. To prove (B.10) consider the event

Set \mbox{\boldmath\delta}=\widehat{\beta}_{L}-\widehat{\beta}_{D}. We have

where the last inequality holds with probability at least $1-M^{1-A^{2}/2}$. Since the Lasso solution $\widehat{\beta}_{L}$ satisfies the Dantzig constraint, we can apply Lemma B.3 with $\beta=\widehat{\beta}_{L}$, which yields

with $J_{0}=J(\widehat{\beta}_{L})$. By Assumption $\text{RE}(s,1)$ we get

where $\kappa=\kappa(s,1)$. Using (B.12) and (B.13) we obtain

Finally, from (B.11) and (B.14) we get that, with probability at least $1-M^{1-A^{2}/2}$,

where the RHS follows (B.2), (B.10), and another application of (B.14). This proves one side of the inequality.

To show the other side of the bound on the difference, we act as in (B.11), up to the inversion of roles of $\widehat{\beta}_{L}$ and $\widehat{\beta}_{D}$, and we use (B.2). This yields that, with probability at least $1-M^{1-A^{2}/8}$,

This is analogous to (B.11). Paralleling now the proof leading to (B.15) we obtain

The theorem now follows from (B.15) and (B.17). ∎

Set again \mbox{\boldmath\delta}=\widehat{\beta}_{L}-\widehat{\beta}_{D}. We apply (B.1) with $\beta=\widehat{\beta}_{D}$ which yields that, with probability at least $1-M^{1-A^{2}/8}$,

where now $J_{0}=J(\widehat{\beta}_{D})$. Consider the two cases: (i) \|\widehat{f}_{D}-f\|_{n}^{2}>2r|\mbox{\boldmath\delta}_{J_{0}}|_{1} and (ii) \|\widehat{f}_{D}-f\|_{n}^{2}\leq 2r|\mbox{\boldmath\delta}_{J_{0}}|_{1}. In case (i) inequality (B.16) with $f_{\max}=1$ immediately implies

and the theorem follows. In case (ii) we get from (B.18) that

and thus |\mbox{\boldmath\delta}_{J_{0}^{c}}|_{1}\leq 5|\mbox{\boldmath\delta}_{J_{0}}|_{1}. We can therefore apply Assumption $\text{RE}(s,5)$ which yields, similarly to (B.14),

where $\kappa=\kappa(s,5)$. Plugging (B.19) into (B.16) we finally get that, in case (ii),

and from the second inequality in (B.1) that

In case (B.23), the result of the theorem trivially follows from (B.21). So, we will only consider the case (B.24). All the subsequent inequalities are valid on the event \mbox{\mathcal{A}}\cap\mbox{\mathcal{A}}_{1} where \mbox{\mathcal{A}}_{1} is defined by (B.24). On this event we get from (B.21) that

which implies |\mbox{\boldmath\delta}_{J_{0}^{c}}|_{1}\leq(3+4/\varepsilon)|\mbox{\boldmath\delta}_{J_{0}}|_{1}. Then for \mbox{\boldmath\delta}^{\prime}=D^{-1/2}\mbox{\boldmath\delta}=\widehat{\beta}_{L}-\beta we have |\mbox{\boldmath\delta}_{J_{0}^{c}}^{\prime}|_{1}\leq(3+4/\varepsilon)(f_{\max}/f_{\min})|\mbox{\boldmath\delta}_{J_{0}}^{\prime}|_{1}. We now use Assumption $\text{RE}(s,(3+4/\varepsilon)f_{\max}/f_{\min})$. This yields

where $\kappa=\kappa(s,(3+4/\varepsilon)f_{\max}/f_{\min})$. Combining this with (B.22) and using that |\mbox{\boldmath\delta}_{J_{0}}|_{2}\leq f_{\max}|\mbox{\boldmath\delta}_{J_{0}}^{\prime}|_{2} we find

This inequality is of the same form as (A.4) in btw07. A standard decoupling argument as in btw07 using inequality $2xy\leq x^{2}/b+by^{2}$ with $b>1$, $x=r\kappa^{-1}\sqrt{{\cal M}(\beta)}$, and $y$ being either $\|\widehat{f}_{L}-f\|_{n}$ or $\|{f}_{\beta}-f\|_{n}$ yields that

Taking $b=1+2/\varepsilon$ in the last display finishes the proof of the theorem. ∎

where $\kappa_{0}=\kappa(\max(C_{1}(\varepsilon),1)s,3+4/\varepsilon)$. Applying Theorem 6.1 once again we get the result. ∎

Set \mbox{\boldmath\delta}=\widehat{\beta}_{D}-\beta^{*} and $J_{0}=J(\beta^{*})$. Using Lemma B.3 with $\beta=\beta^{*}$ we get that on the event $\mathcal{B}$ (i.e., with probability at least $1-M^{1-A^{2}/2}$): (i) \frac{1}{n}|X^{T}X\mbox{\boldmath\delta}|_{\infty}\leq 2r, and (ii) inequality (4.1) holds with $c_{0}=1$. Therefore, on $\mathcal{B}$ we have

since $c_{0}=1$. From Assumption $\text{RE}(s,1)$ we get that

where $\kappa=\kappa(s,1)$. This and (B.25) yield that, on $\mathcal{B}$,

The first inequality in (B.26) implies (7.5). Next, (7.4) is straightforward in view of the second inequality in (B.26) and of the following relations (with $c_{0}=1$):

that hold on $\mathcal{B}$. It remains to prove (7.6). It is easy to see that the $k$th largest in absolute value element of \mbox{\boldmath\delta}_{J_{0}^{c}} satisfies |\mbox{\boldmath\delta}_{J_{0}^{c}}|_{(k)}\leq|\mbox{\boldmath\delta}_{J_{0}^{c}}|_{1}/k. Thus

and since (4.1) holds on $\mathcal{B}$ (with $c_{0}=1$) we find

On the other hand, it follows from (B.25) that

Combining this inequality with Assumption $\text{RE}(s,m,1)$ we obtain that, on $\mathcal{B}$,

Recalling that $c_{0}=1$ and applying the last inequality together with (B.28) we get

It remains to note that (7.6) is a direct consequence of (7.4) and (B.29). This follows from the fact that inequalities $\sum_{j=1}^{M}a_{j}\leq b_{1}$ and $\sum_{j=1}^{M}a_{j}^{2}\leq b_{2}$ with $a_{j}\geq 0$ imply

Set \mbox{\boldmath\delta}=\widehat{\beta}_{L}-\beta^{*} and $J_{0}=J(\beta^{*})$. Using (B.1) where we put $\beta=\beta^{*}$, $r_{n,j}\equiv r$ and $\|{f}_{\beta}-f\|_{n}=0$ we get that, on the event $\mathcal{A}$,

and (4.1) holds with $c_{0}=3$ on the same event. Thus, by Assumption $\text{RE}(s,3)$ and the last inequality we obtain that, on $\mathcal{A}$,

where $\kappa=\kappa(s,3)$. The first inequality here coincides with (7.8). Next, (7.9) follows immediately from (B.3) and (7.8). To show (7.7) it suffices to note that on the event $\mathcal{A}$ the relations (B.27) hold with $c_{0}=3$, to apply the second inequality in (B.31) and to use (B.4).

Finally, the proof of (7.10) follows exactly the same lines as that of (7.6): the only difference is that one should set $c_{0}=3$ in (B.28), (B.29), as well as in the display preceding (B.28).

References