# The Oracle Inequalities on Simultaneous Lasso and Dantzig Selector in High-Dimensional Nonparametric Regression

Authors: Shiqing Wang; Limin Su
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

During the last few years, a great deal of attention has been focused on Lasso and Dantzig selector in high-dimensional linear regression when the number of variables can be much larger than the sample size. Under a sparsity scenario, the authors (see, e.g., Bickel et al., 2009, Bunea et al., 2007, Candes and Tao, 2007, Candès and Tao, 2007, Donoho et al., 2006, Koltchinskii, 2009, Koltchinskii, 2009, Meinshausen and Yu, 2009, Rosenbaum and Tsybakov, 2010, Tsybakov, 2006, van de Geer, 2008, and Zhang and Huang, 2008) discussed the relations between Lasso and Dantzig selector and derived sparsity oracle inequalities for the prediction risk and bounds on theLp estimation loss. In this paper, we point out that some of the authors overemphasize the role of some sparsity conditions, and the assumptions based on this sparsity condition may cause bad results. We give better assumptions and the methods that avoid using the sparsity condition. As a comparison with the results by Bickel et al., 2009, more precise oracle inequalities for the prediction risk and bounds on the Lp estimation loss are derived when the number of variables can be much larger than the sample size.


---

## Body

## 1. Introduction

During the last few years, a great deal of attention has been focused on theL1 penalized least squares (Lasso) estimator of parameters in high-dimensional linear regression when the number of variables can be much larger than the sample size (e.g., see [1–12]). Quite recently, Candes and Tao [13] have proposed the Dantzig estimate for such linear models, and other authors [1, 6, 14–22] have discussed the Dantzig estimate and established the properties under a sparsity scenario, that is, when the number of nonzero components of the true vector of parameters is small.Lasso estimators have also been studied in the nonparametric regression setup (see [23–26]). In particular, Bunea et al. [23, 24] obtain sparsity oracle inequalities for the prediction loss in this context and point out the implications for minimax estimation in classical nonparametric regression settings as well as for the problem of aggregation of estimators. Modified versions of Lasso estimators (nonquadratic terms and/or penalties slightly different from L1) for nonparametric regression with random design are suggested and studied under prediction loss in Koltchinskii [27] and van de Geer [28]. Sparsity oracle inequalities for the Dantzig selector with random design are obtained by Koltchinskii [29]. In linear fixed design regression, Meinshausen and Yu [7] establish a bound on the L2 loss for the coefficients of Lasso that are quite different from the bound on the same loss for the Dantzig selector proven in Candes and Tao [13]. Bickel et al. [15] show that, under a sparsity scenario, the Lasso and the Dantzig selector exhibit similar behavior, both for linear regression and for nonparametric regression models, for L2 prediction loss, and for Lp loss in the coefficients for 1≤p≤2. In the nonparametric regression model, they prove sparsity oracle inequalities for the Lasso and the Dantzig selector. Moreover, the Lasso and the Dantzig selector are approximately equivalent in terms of the prediction loss. They develop geometrical assumptions that are considerably weaker than those of Candes and Tao [13] for the Dantzig selector and Bunea et al. [23] for the Lasso.We give the assumptions equivalent with assumptions by Bickel et al. [15] and derive oracle inequalities that are more precise than Bickel et al.’s [15] for the prediction risk in the general nonparametric regression model and bounds that are more precise than Bickel et al.’s [15] on the Lp estimation loss in the linear model when the number of variables can be much larger than the sample size. We begin, in the next section, by defining the Lasso and Dantzig procedures and the notation. In Section 3, we present our key three assumptions and discuss the relations between the assumptions and assumptions by Bickel et al. [15]. In Section 4, we give some equivalent results and sparsity oracle inequalities for the Lasso and Dantzig estimators in the general nonparametric regression model and improve corresponding results by Bickel et al. [15]. The concluding remarks are given in Section 5.


## 2. Definitions and Notations

Unless stated otherwise, all of our notations, definitions, and terminologies follow Bickel et al. [15]. Let (Z1,Y1),…,(Zn,Yn) be a sample of independent random pairs with
(1)Yi=f(Zi)+Wi,i=1,…,n,
where f:ℤ→ℝ is an unknown regression function to be estimated, ℤ is a Borel subset of ℝd, the Zi’s are fixed elements in ℤ, and the regression errors Wi are Gaussian. Let FM={f1,…,fM} be a finite dictionary of functions fj:ℤ→ℝ, j=1,…,M. We assume throughout that M≥2.Consider the matrixX=(fj(Zi)), i=1,…,n, j=1,…,M and the vectors y=(Y1,…,Yn)T, f=(f(Z1),…,f(Zn))T, and w=(W1,…,Wn)T. With the notation
(2)y=f+w,
we will write |x|p for the Lp norm of x∈ℝM, 1≤p≤∞. The notation ∥·∥n stands for the empirical norm
(3)∥g∥n=1n|g|22
for any g:ℤ→ℝ. We suppose that ∥fj∥n≠0, j=1,…,M. Set
(4)fmax=max1≤j≤M∥fj∥n,fmin=min1≤j≤M∥fj∥n.For anyβ=(β1,…,βM)T∈ℝM and Z∈ℤ, define fβ(Z)=∑j=1Mβjfj(Z) and fβ=(fβ(Z1),…,fβ(Zn))T=Xβ. The estimates we consider are all of the form fβ~(·), where β~ is data determined. Since we consider mainly sparse vectors β~, it will be convenient to define the following. Let
(5)M(β)=∑j=1MI{βJ≠0}=|J(β)|
denote the number of nonzero coordinates of β, where I{·} denotes the indicator function, J(β)={j∈{1,…,M}:βj≠0}, and |J| denotes the cardinality of J. For a vector δ∈ℝM and a subset J⊂{1,…,M}, we denote by δJ the vector in ℝM that has the same coordinates as δ on J and zero coordinates on the complement Jc of J.Define the Lasso solutionβ^L=(β^1,L,…,β^M,L)T by
(6)β^L=arg minβ∈ℝM{1n|y-Xβ|22+2r∑j=1M∥fj∥n|βj|},
where r>0 is some tuning constant, and introduce the corresponding Lasso estimator
(7)f^L(Z)=fβ^L(Z)=∑j=1Mβ^j,Lfj(Z).
The Dantzig selector is defined by
(8)β^D=arg min{|β|1:1n|D-1/2XT(y-Xβ)|∞≤r},
where D is the diagonal matrix
(9)D=diag{∥f1∥n2,∥f2∥n2,…,∥fM∥n2}.
The Dantzig estimator is defined by
(10)f^D(Z)=fβ^D(Z)=∑j=1Mβ^j,Dfj(Z),
where β^D=(β^1,D,…,β^M,D)T is the Dantzig selector.We refer to Bickel et al. [15] for detailed discussion of the Dantzig constraint and the constraint that the Lasso selector satisfies.Finally, for anyn≥1, M≥2, we consider the Gram matrix
(11)Ψn=1nXTX=(1n∑i=1nfj(Zi)fk(Zi)),1≤j,k≤M,
and let ϕmax denote the maximal eigenvalue of Ψn.


## 3. Discussion of the Assumptions

Under the sparsity scenario, we are typically interested in the case whereM>n and even M≫n. Here, sparsity specifies that the high-dimensional vector β has coefficients that are mostly 0. Clearly, the matrix Ψn is degenerate, and ordinary least squares do not work in this case, since the require positive definiteness of Ψn. That is,
(12)minδ∈ℝM,δ≠0|Xδ|2n|δ|2>0.
It turns out that the Lasso and Dantzig selector require much weaker assumptions. The idea by Bickel et al. [15] is that the minimum in (12) be replaced by the minimum over a restricted set of vectors, and the norm |δ|2 in the denominator of the condition be replaced by the L2 norm of only a part of δ. This is feasible. Because for the linear regression model, the residuals δ=β^L-β and δ=β^D-β satisfy
(13)|δJ0c|1≤c0|δJ0|1
with c0=1 by Candes and Tao [13] and c0=3 by Bickel et al. [15], respectively, where c0>0 and J0=J(β) is the set of nonzero coefficients of the true parameter β of the model; therefore, for any δ satisfying (13), we have
(14)δTΨnδ|δ|22≥δTΨδ|δ|22-εn(1+c0)2|J0|,
where Ψ is a positive definite matrix and εn=max|(Ψn-Ψ)ij|. Thus, we have a kind of “restricted” positive definiteness if εn|J0| is small enough. This results in the following restricted eigenvalue (RE) assumption.Assumption RE(s,c0) (Bickel et al. [15]). For some integer s such that 1≤s≤M and a positive number c0, the following condition holds:
(15)κ(s,c0)≜minJ0⊆{1,2,…,M},|J0|≤sminδ≠0,|δJ0c|1≤c0|δJ0|1|Xδ|2n|δJ0|2>0.
The purpose of giving this assumption may be in order to facilitate the use of |δJ0c|1≤c0|δJ0|1 since they frequently use it in the proofs of their theorems and so do Candes and Tao [13].Note that the role of|δJ0c|1≤c0|δJ0|1 is only to restrict set of vectors; that is, {δ∈ℝM:δ≠0} restricts to {δ∈ℝM:δ≠0,|δJ0c|1≤c0|δJ0|1}. Therefore, it is not necessary that the norm |δ|2 in the denominator of (12) be replaced by the L2 norm of only a part of δ. We give the following assumptions.Assumption REτ1(s,c0). For some integer s such that 1≤s≤M and a positive number c0, the following condition holds:
(16)τ1(s,c0)≜minJ0⊆{1,2,…,M},|J0|≤sminδ≠0,|δJ0c|1≤c0|δJ0|1|Xδ|2n|δJ0|1>0.Assumption REτ2(s,c0). For some integer s such that 1≤s≤M and a positive number c0, the following condition holds:
(17)τ2(s,c0)≜minJ0⊆{1,2,…,M},|J0|≤sminδ≠0,|δJ0c|1≤c0|δJ0|1|Xδ|2n|δ|1>0.Assumption REτ3(s,c0). For some integer s such that 1≤s≤M and a positive number c0, the following condition holds:
(18)τ3(s,c0)≜minJ0⊆{1,2,…,M},|J0|≤sminδ≠0,|δJ0c|1≤c0|δJ0|1|Xδ|2n|δ|2>0.Note thatτ2(s,c0)≤τ1(s,c0)≤κ(s,c0) and τ2(s,c0)≤τ3(s,c0)≤κ(s,c0) since |δJ0|2≤|δJ0|1≤|δ|1 and |δJ0|2≤|δ|2≤|δ|1. Moreover, it is easy to see that for fixed n, the four assumptions are equivalent, and those assumptions 1–5 by Bickel et al. [15] are all sufficient conditions for assumptions REτ1(s,c0), REτ2(s,c0), and REτ3(s,c0).In Section4, we will see that REτ1(s,c0) and REτ2(s,c0) are all better than κ(s,c0) since they use |δJ0c|1≤c0|δJ0|1 and |δJ0|1≤|J0|1/2|δJ0|2 as little as possible. Therefore, the inequalities given are more precise.


## 4. Comparisons with the Results by Bickel et al.

In the following, we give a bound of the prediction losses∥f^L-f∥n2 with respect to ∥f^D-f∥n2 when the number of nonzero components of the Lasso or the Dantzig selector is small as compared to the sample size.Theorem 1.
LetWi be independent N(0,σ2) random variables with σ2>0. Fix n≥1, M≥2. Let assumption RE(s,c0) or REτ1(s,c0) be satisfied with 1≤s≤M, where c0>0, and let ∥fj∥n=1, j=1,…,M. Consider the Lasso estimator f^L defined by (6)-(7) with
(19)r=AσlogMn,
where A>22, and consider the Dantzig estimator f^D defined by (10) with the same r. If M(β^D)≤s, then, with probability at least 1-M1-A2/8, one has
(20)∥f^L-f∥n2≤∥f^D-f∥n2+9A2σ2nlogMτ12(s,c0)≤∥f^D-f∥n2+9A2M(β^D)σ2nlogMκ2(s,c0).Proof.
Setδ=β^L-β^D. We apply (B.1) by Bickel et al. [15] with β=β^D, which yields that, with probability at least 1-M1-A2/8,
(21)∥f^L-f∥n2≤∥f^D-f∥n2+4r|δJ0|1-r|δ|1,
where J0=J(β^D). From (B.16) by Bickel et al. [15], we have
(22)∥f^L-f∥n2≤∥f^D-f∥n2+3r|δ|1-1n|Xδ|22.
Then,
(23)∥f^L-f∥n2≤∥f^D-f∥n2+3r|δJ0|1-14n|Xδ|22.≤∥f^D-f∥n2+(3r|δJ0|1n|Xδ|2)2≤∥f^D-f∥n2+9r2τ12(s,c0)≤∥f^D-f∥n2+9r2M(β^D)κ2(s,c0).Corollary 2.
Let the conditions of Theorem1 hold, but with RE(s,5) in place of RE(s,c0). If M(β^D)≤s, then, with probability at least 1-M1-A2/8, one has
(24)∥f^L-f∥n2≤∥f^D-f∥n2+9A2M(β^D)σ2nlogMκ2(s,5).This corollary greatly improves Theorem5.2 by Bickel et al. [15]. The right-hand side of the inequality of Theorem 5.2 is
(25)10∥f^D-f∥n2+81A2M(β^D)σ2nlogMκ2(s,5).A general discussion of sparsity oracle inequalities can be found in Tsybakov [30]. Here, we prove a sparsity oracle inequality for the prediction loss of the Lasso estimators. Such inequalities have been recently obtained for the Lasso-type estimators in a number of settings, see [15, 23, 24, 27, 28].Theorem 3.
LetWi be independent N(0,σ2) random variables with σ2>0. Fix integers n≥1, M≥2, 1≤s≤M. Let assumption RE(s,c0) or REτ1(s,c0) be satisfied, where c0>0. Consider the Lasso estimator f^L defined by (6)-(7) with
(26)r=AσlogMn
for some A>22. Then, with probability at least 1-M1-A2/8, one has
(27)∥f^L-f∥n2≤∥fβ-f∥n2+9fmax2A2σ2τ12(s,c0)logMn≤∥fβ-f∥n2+9fmax2A2σ2κ2(s,c0)M(β)logMn.Proof.
Fix an arbitraryβ∈ℝM with M(β)≤s. Set δ=D1/2(β^L-β), J0=J(β), where D1/2=diag{||f1||n,…,||fM||n}. On the event A in p1723 by Bickel et al. [15], we get, from the first line in (B.1) by Bickel et al. [15], that
(28)∥f^L-f∥n2≤∥fβ-f∥n2+4r|δJ0|1-r|δ|1.
Since
(29)|f-Xβ^L|22=|f-Xβ|22-2δTD-1/2XT(f-Xβ^L)-|XD-1/2δ|22,
then
(30)∥f^L-f∥n2≤∥fβ-f∥n2∥f^L-f∥n2≤+2n|δ|1|D-1/2XT(f-Xβ^L)|∞-1n|XD-1/2δ|22.
From (8) and (B.5) by Bickel et al. [15], we have
(31)1n|D-1/2XT(f-Xβ^L)|∞≤3r2,1n|XD-1/2δ|22=1nδTD-1/2XTXD-1/2δ≥1nfmax2|Xδ|22.
Thus,
(32)∥f^L-f∥n2≤∥fβ-f∥n2+3r|δ|1-1n|XD-1/2δ|22≤∥fβ-f∥n2+3r|δ|1-1nfmax2|Xδ|22.
From (28) and (32), we have
(33)∥f^L-f∥n2≤∥fβ-f∥n2+3r|δJ0|1-14nfmax2|Xδ|22≤∥fβ-f∥n2+(3r|δJ0|1nfmax|Xδ|2)2≤∥fβ-f∥n2+9r2fmax2τ12(s,c0)≤∥fβ-f∥n2+9r2fmax2κ2(s,c0)M(β).Corollary 4.
Let the conditions of Theorem3 hold, but with RE(s,3+4/ε) in place of RE(s,c0). Then, with probability at least 1-M1-A2/8, one has
(34)∥f^L-f∥n2≤∥fβ-f∥n2+9fmax2A2σ2κ2(s,3+4/ε)M(β)logMn.This corollary greatly improves Theorem6.1 by Bickel et al. [15]. The right-hand side of the inequality of Theorem 6.1 is
(35)(1+ε)infβ∈ℝM,M(β)≤s{C(ε)fmax2A2σ2κ2(s,3+4/ε)∥fβ-f∥n2+C(ε)fmax2A2σ2κ2(s,3+4/ε)M(β)logMn},
where (1+ε)C(ε)=4(ε+2)2/ε>9.In the following, we assume that the vector of observationsy=(Y1,…,Yn)T is of the form
(36)y=Xβ*+w,
where X is an n×M deterministic matrix, β*∈ℝM, and w=(W1,…,Wn)T. We consider dimension M that can be of order n and even much larger. Then, β* is, in general, not uniquely defined. For M>n, if (36) is satisfied for β*=β0, then there exists an affine space U={β*:Xβ*=Xβ0} of vectors satisfying (36). The Lasso estimator of β* in (36) is defined by
(37)β^L=arg minβ∈ℝM{1n|y-Xβ|22+2r|β|1}.
The correspondence between the notation here and that of the previous is
(38)∥fβ∥n2=1n|Xβ|22,∥fβ-f∥n2=1n|X(β-β*)|22,∥f^L-f∥n2=1n|X(β^L-β*)|22.Theorem 5.
LetWi be independent N(0,σ2) random variables with σ2>0. Let all the diagonal elements of the matrix XTX/n be equal to 1, and let M(β*)≤s, where 1≤s≤M, n≥1, M≥2. Let assumption RE(s,c0) or REτ1(s,c0) be satisfied, where c0>0. Consider the Lasso estimator β^L defined by (37) with
(39)r=AσlogMn
and A>22. Then, with probability at least 1-M1-A2/8, one has
(40)|β^L-β*|1≤4Aτ12(s,c0)σlogMn≤4Aκ2(s,c0)σslogMn,(41)|X(β^L-β*)|22≤144A225τ12(s,c0)σ2logM≤144A225κ2(s,c0)σ2slogM,(42)M(β^L)≤576ϕmax25τ12(s,c0)≤576ϕmax25κ2(s,c0)s.Proof.
Setδ=β^L-β*and J0=J(β*). Using (B.1) and (B.2) by Bickel et al. [15], where we put β=β*, rn,j≡r, and ∥fβ-f∥n=0, we get that, on the event A (i.e., with probability at least 1-M1-A2/8),
(43)1n|Xδ|22≤4r|δJ0|1-r|δ|1.
From (B.16) by Bickel et al. [15], we have
(44)2n|Xδ|22≤3r|δ|1.
Then,
(45)1n|Xδ|22≤125r|δJ0|1.
By assumption RE(s,c0) or REτ1(s,c0), we obtain that, on A,
(46)τ12(s,c0)|δJ0|12≤1n|Xδ|22≤125r|δJ0|1.
Thus,
(47)|δJ0|2≤|δJ0|1≤125τ12(s,c0)r≤125κ2(s,c0)rs,1n|Xδ|22≤14425τ12(s,c0)r2≤14425κ2(s,c0)r2s.
From (43), we have
(48)r|δ|1≤4r|δJ0|1-1n|Xδ|22≤(2r|δJ0|1n|Xδ|2)2≤4r2τ12(s,c0)≤4sr2κ2(s,c0).
Thus,
(49)|δ|1≤4rτ12(s,c0)≤4srκ2(s,c0).
The inequalities (49) and (47) coincide with (40) and (41), respectively. Next, (42) follows immediately from (B.3) in Bickel et al. [15] and (41).Corollary 6.
Let the conditions of Theorem5 hold, but with RE(s,3) in place of RE(s,c0). Then, with probability at least 1-M1-A2/8, one has
(50)|β^L-β*|1≤4Aκ2(s,3)σslogMn,(51)|X(β^L-β*)|22≤144A225κ2(s,3)σ2slogM,(52)M(β^L)≤576ϕmax25κ2(s,c0)s.This corollary improves Theorem7.2 by Bickel et al. [15]. The right-hand sides of the inequalities of Theorem 7.2 are
(53)16Aκ2(s,3)σslogMn,16A2κ2(s,3)σ2slogM,64ϕmaxκ2(s,3)s,
respectively. That is, they are 4, 25/9, and 25/9 times as large as (50)–(52), respectively.


## 5. Conclusions

We point out that|δJ0c|1≤c0|δJ0|1 with c0=1 by Candes and Tao [13] and c0=3 by Bickel et al. [15] are only the sufficient condition of Lasso and Dantzig selector. Their role should not be overemphasized. That is, |δJ0c|1≤c0|δJ0|1 should not be deliberately used in any case for solving inequality. We should use |δJ0c|1≤c0|δJ0|1 as little as possible when proving inequalities.In fact, the corresponding results have been enlarged due to the use of|δJ0c|1≤c0|δJ0|1 when solving the problems of Lasso and Dantzig selector. When proving sparsity oracle inequalities for the prediction loss and bounds on the Lp estimation loss, using again |δJ0c|1≤c0|δJ0|1 must be to enlarge the inequalities again and to result in reduced accuracy.We have seen that REτ1(s,c0) and REτ2(s,c0) are all much better than κ(s,c0) since in REτ1(s,c0) and REτ2(s,c0) the use of |δJ0c|1≤c0|δJ0|1 and |δJ0|1≤|J0|1/2|δJ0|2 is less. Therefore, the inequalities given are more precise.



---

*Source: 571361-2013-06-06.xml*