On tight bounds for the Lasso

arXiv:1804.00989v1 [] 3 Apr 2018

Sara van de Geer1
April 3, 2018
Abstract We present upper and lower bounds for the prediction error of the
Lasso. For the case of random Gaussian design, we show that under mild conditions the prediction error of the Lasso is up to smaller order terms dominated by
the prediction error of its noiseless counterpart. We then provide exact expressions for the prediction error of the latter, in terms of compatibility constants.
Here, we assume the active components of the underlying regression function
satisfy some “betamin” condition. For the case of fixed design, we provide upper
and lower bounds, again in terms of compatibility constants. As an example,
we give an up to a logarithmic term tight bound for the least squares estimator
with total variation penalty.
Keywords and phrases. compatibility, Lasso, linear model, lower bound
MSC 2010 Subject classifications. 62J05, 62J07

1

Introduction

Let X ∈ Rn×p be an input matrix and β 0 ∈ Rp a vector of unknown coefficients.
Consider an n-vector of noisy observations
Y = Xβ 0 + ǫ
where the noise ǫ ∈ Rn is a vector of i.i.d. standard Gaussians independent of
X. The Lasso estimator β̂ is


2
β̂ ∈ arg min kY − Xbk2 + 2λkbk1
(1)
b∈Rp

with λ > 0 a regularization parameter (Tibshirani [1996]). Its prediction error
is kX(β̂ − β 0 )k22 . Main aim of this paper is to provide lower bounds for this
prediction error, bounds which show that compatibility constants necessarily
enter into the picture.
The results of this paper can be summarized as follows. Firstly, suppose the
design is random and that Σ0 := EX
I T X/n exists. Let β ∗ be the noiseless Lasso
for random design


1/2
∗
0 2
β ∈ arg min nkΣ0 (b − β )k2 + 2λkbk1 .
(2)
b∈Rp

For the case where the rows of X are i.i.d N (0, Σ0 ), we show in Theorem 4.3
√
1/2
that kX(β̂ − β 0 )k2 is up to lower order terms equal to nkΣ0 (β ∗ − β 0 )k2 .
1
Research supported by Isaac Newton Institute for Mathematical Sciences, program Statistical Scalability, EPSRC Grant Number LNAG/036 RG91310.

1

This result is true under the condition that (after normalizing the co-variance
matrix Σ0 to having bounded entries) the largest eigenvalue Λ2max of Σ0 is of
small order log n, and under some mild condition on the growth of the compatibility constants as n increases. Secondly, we provide in Theorem 5.1 exact
expressions for the prediction error of the noiseless Lasso in terms of compatibility constants. We require here “betamin” conditions, which roughly say that
the non-zero coefficients of β 0 should have the appropriate signs and remain
above the noise level in absolute value. Thirdly, for the case of fixed design, we
present upper and lower bounds for the prediction error kX(β̂ − β 0 )k22 in terms
of weighted compatibility constants. Theorem 7.1 states the lower bounds, assuming again certain betamin conditions. The upper bounds we present are
similar to those obtained the literature and presented for completeness. They
are in Corollary 8.1. As an illustration we consider least squares estimation
with a (one-dimensional) total variation penalty. We arrive in Corollary 9.1 at
lower and upper bounds that are the same up to a logarithmic term.
There are general upper bounds in the literature, in particular sharp oracle
bounds as in Koltchinskii et al. [2011] (see also Giraud [2014], Theorem 4.1 or
van de Geer [2016], Theorem 2.2). The oracle bounds involve a compatibility constant, and an improved version of this constant has been developed in
Sun and Zhang [2012], Belloni and Wang [2014] and Dalalyan et al. [2017].
Main theme of this paper is to gain further insight into the role of the compatibility constant when applying the Lasso and to see how it occurs in lower
bounds. In Zhang et al. [2014] it is shown that for a given sparsity level, there
is a design and a lower bound for the mean prediction error in the noisy case,
that holds for any polynomial time algorithm. This lower bound is close to the
known upper bounds and in particular shows that compatibility conditions or
restricted eigenvalue conditions cannot be avoided. This has also been shown
by Bellec [2017], where a choice of the particular vector of regression coefficients
β 0 leads to a lower bound matching the upper bound. We further elaborate on
this issue, and provide lower bounds that hold for a large class of vectors β 0 .
To get an idea of the flavour of the type of bounds we are after, we present in
Theorem 1.1 the case of random design. Details of its proof can be found in
Subsection 11.9. We provide more explicit statements in Theorem 4.3.
Throughout the paper, the active set of β 0 is denoted by S0 := {j : βj0 6= 0}.
Its size is denoted by s0 := |S0 |. Our betamin condition is as follows (its meaning should become more clear after looking at Section 3 where compatibility
constants are defined).
Condition 1.1 Let


X
X
1/2
|bj | = 1
|bj | −
b ∈ arg min kΣ0 bk2 :
∗

j∈S0

j ∈S
/ 0

and for j ∈ S0 let zj∗ be the sign of b∗j . We say that β 0 satisfies the betamin

2

condition for the noiseless case with random design if
zj∗ βj0 >

zj∗ b∗j
1/2
kΣ0 bk22

λ
, ∀j ∈ S0 .
n

Theorem 1.1 Let the rows of X be i.i.d. N (0, Σ0 ), let kΣ0 k∞ be the maximal
entry in the co-variance matrix Σ0 and Λ2max be its largest eigenvalue. For
S ⊂ {1, . . . , p}, let κ2 (S) be the compatibility constant defined in Definition 3.1.
Suppose that
Λ2max /kΣ0 k∞ = o(log(2p)),
and
max



kΣ0 k∞
κ2 (S)



log(2p)|S|
: S ⊂ {1, . . . , p}, |S| ≤
n



 
Λ2max
4s0 = o(1).
κ2 (S0 )

For some t > 0, take the tuning parameter λ to satisfy



q
p
1/2
1/2
3kΣ0 k∞
2n(log(2p) + t) + 2(log(2p) + t) ≤ λ = O
kΣ0 k∞ log(2p) .

Then, under Condition 1.1 (the betamin condition for the noiseless case with
random design), we have
kX(β̂ − β 0 )k22 =

λ2 /n
1/2

kΣ0 b∗ k22

(1 + oIP (1)) + OIP (1)

1/2

(where in fact s0 kΣ0 b∗ k22 = κ2 (S0 )).

2

Organization of the paper

In Section 3 the definition of compatibility constants is given and also some
of their properties are discussed. Section 4 shows that for the case of random
design the squared “bias” of the Lasso dominates its “variance”. Section 5
then gives expressions for this “bias”, i.e. for the noiseless Lasso. Here, we
examine fixed design but the results carry over immediately to random design.
In Section 6 the result of Section 5 is illustrated with the total variation penalty
(in one dimension). Section 7 presents lower bounds for the case of fixed design,
and Section 8 presents some upper bounds. Corollary 8.1 is essentially as in
the papers Sun and Zhang [2012], Belloni and Wang [2014] and Dalalyan et al.
[2017], albeit that do not consider the approximately sparse case. Section 9
has upper and lower bounds for the least squares estimator with total variation
penalty in the noisy case. Section 10 concludes. Section 11 contains the proofs.

3

Compatibility constants

We introduce some notation in order to be able to define the compatibility
constants. This notation will also be helpful at other places. For S ⊂ {1, . . . , p}
3

and a vector b ∈ Rp let bS ∈ Rp be the vector with entries bj,S := bj l{j ∈ S},
j = 1, . . . , p. We apply the same notation for the |S|-dimensional vector {bj }j∈S .
We moreover write b−S := bS c where S c is the the complement of the set S.

3.1

Theoretical compatibility constants

The population version of the compatibility constant will be used for the case of
random design X. We call the population version the theoretical compatibility
constant.
Definition 3.1 Let Σ0 := EX
I T X/n (assumed to exist). Let S ⊂ {1, . . . , p} be
a set of indices and u ≥ 0 be a constant. The theoretical compatibility constant
is


1/2

κ2 (u, S) := min |S|kΣ0 bk22 : kbS k1 − ukb−S k1 = 1 .

For u = 1 we write κ(1, S) =: κ(S).

3.2

Empirical compatibility constants

For a vector w we let W := diag(w) be the diagonal matrix with w on the
diagonal.
Definition 3.2 (Belloni and Wang [2014], Dalalyan et al. [2017]) Let S ⊂
{1, . . . , p} be a set of indices and w ∈ Rp−|S| be a vector of non-negative weights.
The (empirical) compatibility constant is is


2
2
κ̂ (w, S) := min |S|kXbk2 /n : kbS k1 − kW b−S k1 = 1 .
For the case where w = 1 where 1 denotes a vector with all entries equal to
one, put κ̂2 (S) := κ̂2 (1, S).

3.3

Some properties of compatibility constants

One readily sees that the theoretical and empirical compatibility constants differ
only in terms of the matrix used in the quadratic form (which is Σ0 in the
theoretical case and the Gram matrix Σ̂ := X T X/n in the empirical case).
Thus, when discussing their basic properties it suffices to deal with only one of
the two. In this section, we therefore restrict attention to the empirical version
κ̂(w, S). Note that we have generalized the empirical version as compared to
the theoretical one, by considering general weight vectors, not just constant
vectors. With some abuse of notation, we write κ̂(u, S) = κ̂(u1, S) when the
weights are the constant vector u1 (it should be clear from the context what is
meant).
The empirical compatibility constant as given in Definition 3.2 is from Belloni and Wang
[2014] or Dalalyan et al. [2017]. Another version, from for instance van de Geer
4

[2007] or van de Geer [2016] and its references, is presented in the next definition.
Definition 3.3 Let S ⊂ {1, . . . , p} be a set of indices and u > 0 be a constant.
The (older) compatibility constant is


2
2
φ̂ (u, S) := min |S|kXbk2 /n : kbS k1 = 1, kb−S k1 ≤ 1/u .
Let φ̂2 (S) := φ̂2 (1, S) be the compatibility constant for the case u = 1.
The constant φ̂(u, S) compares, for b’s satisfying a “cone condition” kb−S k1 ≤
kbS k1 /u, the ℓ2 -norm kXbk2 with the ℓ1 -norm kbS k1 . The constant κ̂(u, S)
is similar, but takes in the comparison more advantage of a “cone condition” kbS k1 − ukb−S k1 > 0. When κ̂2 (S) > 0 the null space property holds
(Donoho and Tanner [2005]). We will need throughout that the compatibility
constant is strictly positive at S0 (if it is zero our results cease to be of any
interest). This means that we implicitly require throughout
Condition 3.1 The matrix of XST0 XS0 is invertible.
Here, for any S ⊂ {1, . . . , p} the matrix XS = {Xj }j∈S is the n × |S| matrix
consisting of the columns of X corresponding to the set S.
The newer version κ̂(u, S) is an improvement over φ̂(u, S) in the sense that
κ̂(u, S) is the larger of the two.
Lemma 3.1 For all u > 0 it is true that
κ̂2 (u, S) ≥ φ̂2 (u, S).
Let now for some v > 0


2
b ∈ arg min kXbk2 : kbS k1 − vkb−S k1 = 1 .
∗

Then by definition
κ̂2 (v, S) = |S|kXb∗ k22 /n.
The restriction kbS k1 − vkb−S k1 = 1 does not put any bound on the ℓ1 -norm
of b∗S . However, if there is a little room to spare, its ℓ1 -norm is bounded. This
will be useful to understand the betamin conditions (Conditions 1.1 and 5.1).
For simplicity we examine only the value v = 1.
Lemma 3.2 Let


2
b ∈ arg min kXbk2 /n : kbS k1 − kb−S k1 = 1 .
∗

Then for 0 ≤ u < 1

kb∗S k1 ≤

κ̂(S) − uκ̂(u, S)
.
(1 − u)κ̂(u, S)
5

3.4

Comparing empirical and theoretical and compatibility

Having random quadratic forms in mind, the fact that kbS k1 − kb−S k1 = 1 gives
no bound on the ℓ1 -norm can be a problem. Again, if there is a little room to
spare in the value of u in the compatibility constant, one does get a bound on
the ℓ1 -norm. We show this in Lemma 3.3, and with this tool in hand we lower
bound the empirical compatibility constant in terms of the theoretical one in
Lemma 3.4.
Lemma 3.3 Let v > u > 0. Then


κ̂2 (v, S) ≥ min |S|kXbk22 /n : kbS k1 −ukb−S k1 = 1, kbk1 ≤ 1+(1+u)/(v−u) .
The following lemma will be applied when bounding the prediction error of β̂
in terms of that of the noiseless Lasso β ∗ . The lemma may also be of interest
in itself with applications elsewhere.
Lemma 3.4 Suppose the rows of X are i.i.d. N (0, Σ0 ). Let kΣ0 k∞ be the
largest entry in the matrix Σ0 . For v > u, (1 + u)/(v − u) = O(1) and


kΣ0 k∞ s log(2p)
= o(1),
κ2 (u, S)
n
it is true with probability tending to one that
κ̂2 (v, S) ≥ (1 − η)2 κ2 (u, S).
where η = o(1).

4

Comparison with the noiseless Lasso when the design is random

In this section we assume that the rows of X are i.i.d. copies of a Gaussian
row vector with mean zero and co-variance matrix Σ0 . We denote the largest
eigenvalue of Σ0 by Λ2max and let kΣ0 k∞ be its largest entry. We define a
noiseless version β ∗ of the Lasso where also the random design is replaced by
its population counterpart:


1/2
β ∗ ∈ arg min nkΣ0 (b − β 0 )k22 + 2λkbk1 .
b∈Rp

The normalization with n is to put things on the scale of the empirical version,
as EX
I T X = nΣ0 . One may think of kX(β ∗ −β 0 )k2 as “bias” and kX(β̂−β ∗ )k22 as
“variance”. We first investigate in some detail the “variance” part in Theorems
4.1 and 4.2. Then we apply the triangle inequality as a way to establish that
the squared “bias” dominates the “variance”, see Theorem 4.3.

6

Theorem 4.1 Suppose that

 2

 
kΣ0 k∞ log(2p)|S|
Λmax
2
ρ := max
: S ⊂ {1, . . . , p}, |S| ≤
4s0 = o(1).
κ2 (S)
n
κ2 (S0 )
Take for some t > 0
λ≥
and define

1/2
3kΣ0 k∞



p


2n(log(2p) + t) + 2(log(2p) + t)

p
√
γ := (2Λmax ) n/λ + (2/kΣ0 k1/2
∞ )ρλ/ n log(2p).

Then we have for all x > 0 with probability at least 1−4 exp[−t]−exp[−x]−o(1)
that
√
√
1/2
kX(β̂ − β ∗ )k2 ≤ γ nkΣ0 (β ∗ − β 0 )k2 + 2x.
Using concentration of measure, one can remove the dependency of the confidence level on the value of t. This value appears in the choice of the tuning
parameter λ. We make some rather arbitrary choices for the constants.
Theorem 4.2 With the conditions and notations of Theorem 4.1, and assuming in addition that 4 exp[−t] < 1/8 (say), for n large enough and for all x > 0,
with probability at least 1 − 2 exp[−x],
p
√
√
1/2
kX(β̂ − β ∗ )k2 ≤ γ nkΣ0 (β ∗ − β 0 )k2 + 4 log 2 + 2x.
We can now make a type of bias-variance decomposition. The triangle inequality
tells us that
kX(β̂ − β 0 )k2 − kX(β ∗ − β 0 )k2 ≤ kX(β̂ − β ∗ )k2 .
We then approximate the empirical “bias” kX(β ∗ − β 0 )k2 by the theoretical
√
1/2
“bias” nkΣ0 (β ∗ −β0 )k2 (which is easy as β ∗ and β 0 are non-random vectors),
and use Theorem 4.1 or 4.2 to bound the “variance” kX(β̂ − β ∗ )k22 .
Theorem 4.3 With the conditions and notations of Theorem 4.2, we have for
n sufficiently large, for all x > 0 with probability at least 1 − 2 exp[−x]
kX(β̂ − β 0 )k2 −

√

1/2

nkΣ0 (β ∗ − β 0 )k2

p
√
√
1/2
≤ (γ + o(1)) nkΣ0 (β ∗ − β 0 )k2 + 4 log 2 + 2x.

Corollary 4.1 Recall that we defined γ as
p
√
γ := (2Λmax ) n/λ + (2/kΣ0 k1/2
∞ )ρλ/ n log(2p).

Therefore, with the conditions and notations of Theorem 4.3, and assuming in
addition
7

- Λ2max /kΣ0 k∞ = o(log(2p)),
and
p
- λ = o( kΣ0 k∞ n log(2p))/ρ,
we get with probability at least 1 − 2 exp[−x]
p
√
√
√
1/2
1/2
kX(β̂ −β 0 )k2 − nkΣ0 (β ∗ −β 0 )k2 = o( nkΣ0 (β ∗ −β 0 )k2 )+4 log 2+ 2x.

In words: the squared “bias” dominates the “variance”.

Remark 4.1 With the help of Lemma 12.5, one may also prove bounds for
√
nkΣ0 (β̂ − β 0 )k2 to complete those for of kX(β̂ − β 0 )k2 . We refrain from
doing this here to avoid digressions.

5

The noiseless case with fixed design

In this section we study fixed design X and the noiseless Lasso


∗
0 2
∗
β ∈ arg min kX(b − β )k2 + 2λ kbk1 .
b∈Rp

(3)

In principle the noiseless Lasso considered here differs from (2), although one
can say that for fixed design Σ̂ = E
I Σ̂ =: Σ0 , with Σ̂ := X T X/n being the Gram
matrix. In what follows in this section, we do not use any specific properties of
Σ̂ and the theory goes through for any positive semi-definite matrix, Σ say. In
the upcoming illustration on functions of bounded variation, the fixed design
setup is the natural one.
Note that we supplied the tuning parameter λ∗ with a supscript ∗. This is
because in Theorem 8.1 we consider a case with different tuning parameters for
the noisy and the noiseless case, say λ and λ∗ .
The Karush-Kuhn-Tucker (KKT) conditions for the noiseless Lasso read
X T X(β ∗ − β 0 ) + λ∗ ζ ∗ = 0, ζ ∗ ∈ ∂kβ ∗ k1 ,

(4)

where ∂kbk1 denotes the sub-differential of b 7→ kbk1 :


p
T
∂kbk1 = z ∈ R : z b = kbk1 , kzk∞ ≤ 1 .
Recall that
κ̂2 (S) = |S|kXb∗ k22 /n
where



b∗ ∈ arg minp kXbk2 : kbS k1 − kb−S k1 = 1 .
b∈R

(5)

Note that b∗ given in (5) is not unique, for example we can flip the signs of b∗
(i.e., replace b∗ by −b∗ ).
8

In Theorem 5.1 below we give a tight result for the noiseless case under the
condition that the active coefficients in β 0 are sufficiently large in absolute
value: Condition 5.1. Here sufficiently large depends on the magnitude of the
entries of a solution b∗ of (5) with S = S0 . Therefore, it is of interest to know
how large b∗ is. Lemma 3.2 considers its ℓ1 -norm, and in view of this lemma we
conclude that if there is a little room to spare, the ℓ1 -norm of kb∗S k1 is bounded,
or - in other words - {b∗j |S|}j∈S is bounded “on average”.
For the next condition it is useful to know that we show in Lemma 11.6 that for
b∗ given in (5), each coefficient b∗j with j ∈ S is nonzero (provided κ̂2 (S) > 0).
Condition 5.1 Suppose κ̂2 (S0 ) > 0. Let b∗ satisfy (5) with S = S0 . Denote,
for j ∈ S0 , the sign of b∗j as zj∗ . We say that β 0 satisfies the betamin condition
for the noiseless case with fixed design if
zj∗ βj0 >

zj∗ b∗j s0 λ∗
∀ j ∈ S0 .
κ̂2 (S0 ) n

Here is the main theorem for the noiseless case.
Theorem 5.1 Suppose κ̂2 (S0 ) > 0. Let b∗ satisfy (5) with S = S0 . If β 0
satisfies Condition 5.1 (the betamin condition for the noiseless case with fixed
design), then there exists a solution β ∗ of the KKT conditions (4) such that
kX(β ∗ − β 0 )k22 =

6

s0 λ∗2
.
κ̂2 (S0 ) n

The total variation penalty in the noiseless case

In this section Theorem 5.1 is illustrated with the total variation penalty. For
a vector f ∈ Rn , its total variation is defined as
TV(f ) :=

n
X
i=2

|fi − fi−1 |.

Fix a vector f 0 ∈ Rn and let f ∗ ∈ Rn is the least squares approximation of f 0
with total variation penalty


∗
0 2
∗
: f ∈ arg min kf − f k2 + 2λ TV(f ) .
(6)
f ∈Rn

Theorem 6.1 presents an explicit expression for the compatibility constant
κ̂2 (S0 ) where S0 is the set consisting of the locations of the jumps of f 0 . Invoking Theorem 5.1 one then arrives at an explicit expression for kf ∗ − f 0 k22
provided the jumps of f 0 are sufficiently large, see Corollary 6.1.
First, we need to rewrite problem (6) as a (noiseless) Lasso problem. Indeed,
for j = 1 . . . , n,
n
X
(fi − fi−1 )l{j ≥ i} =: (Xb)j ,
fj =
i=1

9

where Xj,i = l{j ≥ i} and bi = fi − fi−1 , with f0 := 0. Hence we can say that
f 0 = Xβ 0 and f ∗ = Xβ ∗ with


n
X
∗
0 2
∗
|bi | .
β := arg min kX(b − β )k2 + 2λ
b∈Rn

i=2

Note that the first coefficient b1 is not penalized. It is therefore typically active,
and we consider the active set as the location of the jumps augmented with the
index {1}. We slightly adjust the definition of the compatibility constant to
deal with the a coefficient without penalty: we set for S ⊂ {2, . . . , n}


2
2
κ (S) := min |S ∪ {1}|kXbk2 : kbS k1 − kb−(S∪{1}) k1 = 1 .
(7)
Let now S := {d1 + P
1, d1 + d2 + 1, . . . , d1 + · · · + ds + 1} for some {dj }sj=1 ⊂
{2, . . . , n} satisfying sj=1 dj + 2 < n. The set S represents locations of jumps,
d1 is the locationP
of the first jump and {dj }sj=2 are the distances between jumps.
Let ds+1 := n − sj=1 dj the distance between the last jump and the end point.
For simplicity we assume that dj is even for all j ∈ {2, . . . , s}.

Theorem 6.1 The compatibility constant κ̂2 (S) is, up the constant 4 and the
scaling by 1/n, the harmonic mean of of the distances between jumps, including
the distance between starting point and first jump and last jump and endpoint:
κ̂2 (S) =
In fact

n
d1

+

s+1
Ps 4n
j=2 dj

+

n
ds+1

.

κ̂2 (S) = (s + 1)kXb∗ k22 /n

where b∗j = 0 for all j ∈
/ S and b∗ = b̃/kb̃k1 with

n
2n
+
,
d1
d2


2n 2n
= −
+
,
d2
d3
..
.


2n
n
= (−1)s+1
+
.
ds
ds+1

b̃d1 +1 =
b̃d2 +1

b̃ds

Corollary 6.1 Suppose f 0 jumps at S0 := S = {d1 + 1, d1 + d2 + 1, . . . , d1 +
· · · + ds + 1}, with s = s0 . Assume f 0 alternates between jumps up and jumps
down. Suppose moreover that


2n λ∗
n
0
0
+
,
|fd1 +1 − fd1 | ≥
d1
d2 n


2n 2n λ∗
0
0
,
+
|fd2 +1 − fd2 | ≥
d2
d3 n
..
. 
 ∗
2n
λ
n
0
0
+
.
|fds +1 − fds | ≥
0
0
ds0
ds0 +1 n
10

Then by Theorem 5.1 combined with Theorem 6.1

 ∗2
s0
X
n
4n
λ
n
∗
0 2
kf − f k2 =
.
+
+
d1
dj
ds0 +1 n
j=2

At this
√ point it may be helpful to look how this normalizes. Say we choose0
∗
= O(s0 + 1). Then the jumps of f
λ = n log n. Suppose max1≤j≤s0 +1 n/dj p
are required to be of order at least (s0 + 1) log n/n. We then obtain


kf ∗ − f 0 k22 = O (s0 + 1)2 log n .

7

A lower bound in the noisy case with fixed design

We now turn to the Lasso β̂ in the noisy case, given by


2
β̂ ∈ arg min kY − Xbk2 + 2λkbk1
b∈Rp

where
Y = Xβ 0 + ǫ.
We investigate the case of fixed design X. Recall that we assume throughout
i.i.d. standard Gaussian noise.

7.1

Towards betamin conditions

Consider some vector v̄ ∈ Rp−s0 with 0 < v̄j < 1 for all j. This vector represents
the “noise” that is to be overruled by the penalty. Define the collection of
weights


W(v̄) :=

w ∈ Rp−s0 : 1 − v̄j ≤ wj ≤ 1 + v̄j ∀ j .

Let for W̄ := diag(1 + v̄)


∗
2
b (v̄) ∈ arg min kXbk2 : kbS0 k1 −kW̄ b−S0 k1 = 1 , zj∗ (v̄) := sign(b∗j (v̄)), j ∈ S0 .
Then by definition κ̂2 (1 + v̄, S0 ) = s0 kXb∗ (v̄)k22 /n. We remark here that by a
slight adjustment of Lemma 11.6, the assumption κ̂(1 + v̄, S0 ) > 0 ensures that
b∗j (v̄) 6= 0 for all j ∈ S0 .
For w ∈ W(v̄) we define the convex problem with linear and convex constraints


2
∗T
b(w) ∈ arg min kXbk2 : zS0 (v̄)bS0 − kW b−S0 k1 ≥ 1 .
Finally, define
bj (v̄) := max |bj (w)|/kXb(w)k22 , j ∈ S0 .
w∈W(v̄)

11

7.2

Projections

We denote the projection of X−S0 on the space spanned by the columns of XS0
by X−S0 PXS0 . The projection is always defined but as it is implicitly assumed
that XST0 XS0 is invertible (Condition 3.1), we can clarify what we mean by
projection by writing
X−S0 PXS0 := XS0 (XST0 XS0 )−1 XST0 X−S0 .
The anti-projection is denoted by
X−S0 AXS0 = X−S0 − X−S0 PXS0 .
We define the matrix
V−S0 ,−S0 :=
=



T 



X−S0 AXS0
X−S0 AXS0


T
T
−1 T
X−S0 I − XS0 (XS0 XS0 ) XS0 X−S0 ,

and let {vj2 }j ∈S
/ 0 be the diagonal elements of this matrix.

7.3

A lower bound

The main result for the noisy case is presented in the next theorem. Here, we
use the notations and definitions of the previous two subsections.
Theorem 7.1 Take for some t > 0,
λ > kv−S0 k∞
Define
v̄j := vj
and
ūj := uj

p

p

p

2(log(2p) + t).

(8)

2(log(2p) + t)/λ, j ∈
/ S0

2(log(2p) + t)/λ, j ∈ S0 .

where {uj }j∈S0 are the diagonal elements of the matrix (XST0 XS0 )−1 . Assume
that κ̂(1 + v̄, S0 ) > 0 and that the following betamin condition holds:
|βj0 | > λ(bj (v̄) + ūj ), sign(βj0 ) = zj∗ (v̄) ∀j ∈ S0 .
Then for all x > 0 with probability at least 1 − exp[−t] − exp[−x] there is a
solution β̂ of the KKT conditions such that
r
r
√
s0
λ2 √
0
s
−
2x.
(9)
−
kX(β̂ − β )k2 ≥
0
κ̂2 (1 + v̄, S0 ) n
Note that for j ∈ S0 , the quantity uj is the variance of the ordinary least
squares estimator of βj0 for the case S0 is known. Thus the betamin condition
of Theorem 7.1 needs that the magnitude of the active coefficients should exceed
the noise level of the ordinary least squares estimator for known S0 .
12

8

Comparison with the noiseless Lasso when the design is fixed

This section studies the case of fixed design and compares the noisy Lasso


2
β̂ := arg minp kY − Xbk2 + 2λkbk1
b∈R

with the noiseless Lasso


0 2
∗
β := arg minp kX(b − β )k2 + 2λ kbk1
∗

b∈R

where λ∗ ≤ λ. We let S∗ be active set of β ∗ and its cardinality s∗ := |S∗ |.
We investigate the error kX(β̂ − β ∗ )k2 in Theorem 8.1. For λ∗ = 0 we see
that β ∗ = β 0 and then Theorem 8.1 gives a bound for kX(β̂ − β 0 )k2 . This
is elaborated upon in Corollary 8.1. The case λ∗ = λ is detailed in Corollary
8.2. The error kX(β̂ − β ∗ )k22 can then seen as “variance” and kX(β ∗ − β 0 )k2 as
“bias”.

8.1

Projections

We now introduce some notations and definitions similar to the ones in Subsections 7.2, now for general S instead of just S = S0 . The projection of X−S on
the space spanned by the columns of XS is denoted by X−S PXS . Recall that
such projections are defined, also if XS does not have full column rank. The
anti-projection is
X−S AXS := X−S − X−S PXS .
Define the matrix
S
V−S,−S
:=


T 

X−S AXS
X−S AXS

and let {(vjS )2 }j ∈S
/ be the diagonal elements of this matrix.

8.2

Upper bound

Recall the KKT conditions for β ∗ as given in (4), involving the vector ζ ∗ in the
sub-differential ∂kβ ∗ k1 .
Theorem 8.1 Fix a set S with cardinality |S| = s. Assume that that for some
t>0
p
S
(10)
λ > kv−S
k∞ 2(log(2p) + t)
and write

v̄jS := vjS

p

2(log(2p) + t)/λ, j ∈
/ S.

13

(11)

Suppose that
λ∗ |ζj∗ |/λ < 1 − v̄jS ∀ j ∈
/ S.

Define

1 − v̄jS − λ∗ |ζj∗ |/λ
:=
, j∈
/ S.
1 − λ∗ /λ
We have for all x with probability at least 1 − exp[−t] − exp[−x]
r
r
√
s
(λ − λ∗ )2 √
kX(β̂ − β ∗ )k2 ≤
s
+
2x.
+
κ̂2 (w̄S , S)
n
w̄jS

(12)

Corollary 8.1 If we take the tuning parameter λ∗ of the noiseless Lasso equal
to zero, Theorem 8.1 gives the following: with probability at least 1 − exp[−t] −
exp[−x]
p
p
√
√
kX(β̂ − β 0 )k2 ≤ s0 /κ̂2 (1 − v̄, S0 ) λ2 /n + s0 + 2x.
This result is comparable to results in Sun and Zhang [2012], Belloni and Wang
[2014] and Dalalyan et al. [2017], albeit that we do not deal with the extension to
the approximately sparse case. One may check that the the combined conclusions
of this corollary with that of Theorem 7.1 also hold with probability at least
1 − exp[−t] − exp[−x].

Corollary 8.2 We can also take λ∗ = λ in Theorem 8.1. We then formally
put w̄jS = ∞ for all j ∈
/ S and we put κ̂(w̄) = ∞ as well. Let S with |S| = s.
Assume that
/S
(13)
|ζj∗ | < 1 − v̄jS ∀ j ∈

(this implies S ⊃ S∗ ). We have with probability at least 1 − exp[−t] − exp[−x]
√
√
kX(β̂ − β ∗ )k2 ≤ s + 2x.

√
Corollary 8.2 is of interest only when s is small enough This is the case if
Σ̂ := X T X/n has a well behaved maximal eigenvalue Λ̂2max . Indeed, one can
show in the same way as in Lemma 11.2 (where Σ̂ is replaced by Σ0 ) that


n
Λ̂2max
kX(β ∗ − β 0 k22 .
s≤
S
2
(1 − kv̄ k∞ ) λ2
Thus if Λ̂2max /(kΣ̂k∞ (1 − kv̄ S k∞ )2 ) = o(log(2p)), then s = o(kX(β ∗ − β 0 )k22 ).
However, for the case of fixed design, one might not want to impose such eigenvalue conditions. Alternatively, one may want to resort to irrepresentable con/ S, the projection of the j th
ditions. To this end, fix a set S ⊃ S0 . Let for j ∈
column Xj on XS be denoted by
Xj PXS := XS γS,j .
Then it is not difficult to see that for j ∈
/ S |ζj∗ | ≤ kγS,j k1 . In other words, a
sufficient condition for (13) to hold is the irrepresentable condition
kγS,j k1 ≤ 1 − v̄jS , ∀j ∈
/ S.

We conclude that under irrepresentable conditions the squared “bias” kX(β ∗ −
β 0 )k22 dominates the “variance” kX(β̂ − β ∗ )k2 .
14

9

The total variation penalty in the noisy case

We continue with the total variation penalty of Section 6, but now in a noisy
setting:
Y = f 0 + ǫ,
where f 0 ∈ Rn is an unknown vector. The least squares estimator with total
variation penalty is


2
ˆ
f ∈ arg min kY − f k2 + 2λTV(f ) .
(14)
f ∈Rn

As has become clear from the previous sections, to assess the prediction error
in the noisy case one needs to evaluate the compatibility constant κ̂(w, S) with
weights wj 6= 1 for j ∈
/ S. For the upper bound on the prediction error, we
need lower bounds on κ̂(w, S). These are derived in Dalalyan et al. [2017],
Proposition 2. We re-derive (and slightly improve) their result using a different
proof (the proof in Dalalyan et al. [2017] applies a probabilistic argument).
Suppose as in Section 6 that the locations of the jumps are S :=P
{d1 +1, d1 +d2 +
1, . . . , d1 +· · ·+dsP
+1} for some {dj }sj=1 ⊂ {2, . . . , n} satisfying sj=1 dj +2 < n.
Let ds+1 := n − sj=1 dj . Assume again for simplicity that dj is even for all
j ∈ {2, . . . , s}.
Lemma 9.1 Let w1 , . . . , wn be non-negative weights. We have
v
u n
√
√
X
s+1
s+1 u
≤ kwk∞
+ tn
(wi − wi−1 )2 ,
κ̂(w, S)
κ̂(S)
i=2

where as in Theorem 6.1

s

n X 4n
n
s+1
=
+
+
.
κ̂2 (S)
td
dj
ds+1
j=2

Corollary 9.1 Using the notation of Section 8 suppose that λ satisfies (10)
with and let v̄ = v̄ S0 be given in (11), both with S := S0 . Define v̄i = 0 for all
i ∈ S0 . We then have with wi := 1 − v̄i , j ∈
/ S0 ∪ {1}, w1 = w2 and wi = 1,
i ∈ S0 that
|wi − wi−1 | ≤ |vi − vi−1 |/kvk∞ , i = {2, . . . , n}.
In Dalalyan et al. [2017] it is shown in their Proposition 3 that
n
X
(vi − vi−1 )2 /kvk2∞ ≤ (s0 + 1)log n.
i=2

Hence one obtains from Lemma 9.1 with S = S0 , combined with Corollary 8.1,
s
r
√
s0 + 1
s0 + 1
(s0 + 1) log n
≤
+
κ̂(1 − v̄, S0 )
κ̂(S0 )
n
15

where as before

s

0
X
s0 + 1
n
n
4n
=
+
+
.
2
κ̂ (S0 )
d1
dj
ds0 +1

j=2

Thus, with probability at least 1 − exp[−t] − exp[−x]
r
s

√
√
(s
+
1)
(s0 + 1) log n
0
0
+
+
kfˆ − f k2 ≤ λ
+
s
2x.
0
nκ̂2 (S0 )
n
Theorem 6.1 implies that
κ̂(1 + v̄, S0 ) ≤ κ̂(S0 ).
Recall that for the combined conclusion of Theorem 7.1 and Corollary 8.1 we
do not have to change the confidence level (which is 1 − exp[−t] − exp[−x]). We
therefore obtain that if the jumps of f 0 are sufficiently large in absolute value,
as given in Theorem 7.1, then with probability at least 1 − exp[−t] − exp[−x]
s
s
√
√
√
√
s0 + 1
s0 + 1
0
ˆ − f k2 ≤ λ
s
−
2x
≤
k
f
s
+
2x
−
+
λ
0
0
nκ̂2 (S0 )
nκ̂2 (S0 )
r
(s0 + 1) log n
.
+ λ
n

10

Conclusion

This paper establishes that in a sense the squared “bias” of the Lasso dominates the “variance”. Moreover, lower bounds for the prediction error are
given. These lower often match up to constants or logarithmic factors the
upper bounds, or are in fact tight up to smaller order terms. The bounds
show that compatibility constants necessarily enter into the picture. The lower
bounds require “betamin” conditions, and - for the case of random design - also
certain sparsity conditions. It is as yet unclear what can be said when betamin
conditions to hold. In combination with this, it would also be of great interest
to know what happens when the regression coefficients are not (approximately)
sparse. As far as we know the question to what extend the Lasso will have large
prediction error when sparseness assumptions are violated (i.e. when the Lasso
is used in a scenario not meant for it) is still open.
Acknowledgements: We thank Rico Zenklusen from the Institute of Operations Research, ETH Zürich, and Hamza Fawzi from Department of Applied
Mathematics and Theoretical Physics at the University of Cambridge, for very
helpful discussions.

16

11

Proofs

11.1

Proofs of the lemmas in Section 3

Proof of Lemma 3.1. We have to show that κ̂2 (u, S) ≥ φ̂2 (u, S). Write


A := b : kb−S k1 ≤ kbS k1 /u, kbS k1 > 0
and
B :=



b : kbS k1 − ukb−S k1 > 0 .

Then
B ⊂ A.
Thus


|S|kXbk22 /n
φ̂ (u, S) = min
: b∈A
kbS k21


|S|kXbk22 /n
≤ min
: b∈B
kbS k21
2

= κ̂2 (u, S).

⊓
⊔

Proof of Lemma 3.2. This lemma bounds the ℓ1 -norm of the minimizer b∗ if
there is a little room to spare. We have
p
|S|/nkXb∗ k2 /κ̂(u, S)
kb∗S k1 − ukb∗−S k1 ≤
= κ̂(S)/κ̂(u, S).

On the other hand
kb∗S k1 − ukb∗−S k1 = kb∗S k1 − kb∗−S k1 + (1 − u)kb∗−S k1
= 1 + (1 − u)kb∗−S k1 .

Thus
kb∗−S k1 ≤
yielding

κ̂(S) − κ̂(u, S)
,
(1 − u)κ̂(u, S)

kb∗S k1 = 1 + kb∗−S k1 ≤

κ̂(S) − uκ̂(u, S)
.
(1 − u)κ̂(u, S)

⊓
⊔

Proof of Lemma 3.3. This lemma shows that one has a bound for the ℓ1 norm in the “cone condition” if there is a little room to spare. Consider a vector
b ∈ Rp satisfying
kbS k1 − vkb−S k1 = 1.
17

Since
kbS k1 − vkb−S k1 = kbS k1 − ukb−S k1 − (v − u)kb−S k1
we obtain
(v − u)kb−S k1 = kbS k1 − ukb−S k1 − 1 ≤ kbS k1 − ukb−S k1 .
Moreover, clearly
kbS k1 − ukb−S k1 = (v − u)kb−S k1 + 1 ≥ 1.
It follows that



min kXbk2 : kbS k1 − vkb−S k1 = 1



≥ min kXbk2 : (v − u)kb−S k1 ≤ kbS k1 − ukb−S k1 , kbS k1 − ukb−S k1 ≥ 1 .
Suppose now that for some c > 1
(v − u)kb−S k1 ≤ kbS k1 − ukb−S k1 , kbS k1 − ukb−S k1 = c.
Define
b̃ := b/c.
Then
(v − u)kb̃−S k1 ≤ 1, kb̃S k1 − ukb̃−S k1 = 1.
Moreover
kXbk2 = ckX b̃k2 > kX b̃k2 .
Therefore


min kXbk2 : (v − u)kb−S k1 ≤ kbS k1 − ukb−S k1 , kbS k1 − ukb−S k1 ≥ 1


= min kXbk2 : (v − u)kb−S k1 ≤ 1, kbS k1 − ukb−S k1 = 1 .
But if (v − u)kb−S k1 ≤ 1 and kbS k1 − ukb−S k1 = 1 we see that
kbk1 ≤ kbS k1 + kb−S k1 = 1 + (1 + u)kb−S k1
≤ 1 + (1 + u)/(v − u).

⊓
⊔
Proof of Lemma 3.4. This lemma lower bounds the empirical compatibility
constant by the theoretical one. Here is a proof. If kbS k1 − ukb−S k1 = 1 we
know that
√
1/2
1 ≤ kΣ0 bk2 s/κ(u, S).
It therefore follows from Lemma 3.3 that


1/2
2
2
κ̂ (v, S) ≥ |S|kXbk2 /n : kbS k1 − ukb−S k1 = 1, kbk1 ≤ M (u, v)kΣ0 bk2
18

where
p
√
M (u, v) := (1 + (1 + u)/(v − u)) s/κ(u, S) = o( n/(kΣ0 k∞ log(2p))).
p
In view of Lemma 12.5 we know that when M = o( n/(kΣ0 k∞ log(2p)), then
with probability tending to one
inf

1/2
kbk1 ≤M kΣ0 bk2

kXbk22 /n
1/2

kΣ0 bk22

≥ (1 − ηM )2

for suitable ηM = o(1). Hence with probability tending to one


1/2
2
min kXbk2 /n : kbS k1 − ukb−S k1 = 1, kbk1 ≤ M (u, v)kΣ0 bk2


1/2 2
≥ (1−ηM (u,v) ) min kΣ0 bk2 : kbS k1 −ukb−S k1 = 1 = (1−ηM (u,v) )2 κ2 (u, S).
2

⊓
⊔

11.2

Proof of Theorem 4.1.

The proof is organized as follows. We first present a bound for kΣ0 (β ∗ −β0 )k2 in
Lemma 11.1. This will be used to bound later the number of active variables s∗
of β ∗ , or rather some extended version of it involving sub-differential calculus,
see Lemma 11.2. We then establish in Lemma 11.3 a deterministic bound
assuming we are on some subset of the underlying probability space. Then in
Lemma 11.4 we show that this subset has large probability.
The noiseless Lasso β ∗ given in (2) satisfies the KKT conditions
nΣ0 (β ∗ − β 0 ) + λζ ∗ = 0, ζ ∗ ∈ ∂kβ ∗ k1 ,

(15)

where ∂kbk1 is the sub-differential of b 7→ kbk1 :


∂kbk1 := z : kzk∞ ≤ 1, z T b = kbk1 .
This will be used in Lemma 11.2 and again in Lemma 11.3. In the latter we
also invoke the KKT conditions for β̂
X T X(β̂ − β 0 ) + λζ̂ = X T ǫ, ζ̂ ∈ ∂kβ̂k1 .
11.2.1

A bound for the number of active variables of β ∗

First we bound the prediction error of β ∗ .
Lemma 11.1 Suppose κ2 (S0 ) > 0. Then
1/2

nkΣ0 (β ∗ − β 0 )k22 ≤
19

s 0 λ2
.
κ2 (S0 ) n

(16)

Proof of Theorem 11.1. This follows from a slight adjustment of Theorem
8.1 in this paper. This is a big detour however, so let us present a self-contained
proof as well. By the KKT conditions (15)
∗
−(β ∗ − β 0 )T ζ ∗ ≤ kβ 0 k1 − kβ ∗ k1 ≤ kβS∗ 0 − β 0 k1 − kβ−S
k .
0 1
1/2

So if kΣ0 (β ∗ − β 0 )k22 > 0 we obtain by the definition of the compatibility
constant κ2 (S0 ) that
√
1/2
1/2
nkΣ0 (β ∗ − β 0 )k22 ≤ λ s0 kΣ0 (β ∗ − β 0 )k2 /κ(S0 ).
⊓
⊔

This yields the result of the lemma.

Consider the set S∗ := {βj∗ 6= 0} of active coefficients of β ∗ . We bound the
size of this set. In fact we look at bound for the size of a potentially larger
set, namely the set S∗ (ν) := {j : |ζj∗ | ≥ 1 − ν} where 0 ≤ ν < 1 is arbitrary.
Note that indeed S∗ ⊂ S∗ (ν). We pin down the value of ν to ν = 1/2 but the
argument goes through for other values if one adjusts the constants accordingly.
We still keep the symbol ν at places to facilitate tracking the constants.
Lemma 11.2 We have that
|S∗ (ν)| ≤

s0
Λ2max
Λ2max n2 1/2 ∗
0 2
kΣ
(β
−
β
)k
≤
.
2
0
2
2
2
2
(1 − ν) λ
(1 − ν) κ (S0 )

Proof of Lemma 11.2. Since
kζ ∗ k22 ≥ kζS∗∗ (ν) k22 ≥ (1 − ν)2 |S∗ (ν)|
it follows from the KKT conditions (15) that
(1 − ν)2 |S∗ (ν)| ≤ kΣ0 (β ∗ − β 0 )k22

2
n2
1/2 ∗
2
0 2n
≤
Λ
kΣ
(β
−
β
)k
max
2 2.
0
λ2
λ

The proof is completed by applying the upper bound of Lemma 11.1
1/2

kΣ0 (β ∗ − β 0 )k22 ≤

s0
κ2 (S

λ2
.
2
0) n
⊓
⊔

11.2.2

Projections

Let S := S∗ (ν), s := |S| (where ν = 1/2). Set
U(S) := kǫPXS k2
where ǫPXS is the projection of ǫ on the space spanned by the columns of XS .
Denote the anti-projection of X−S on this space by
X−S AXS := X−S − X−S PXS .
20

11.2.3

Choice of λ

Recall we take for some t > 0


p
1/2
λ ≥ 3kΣ0 k∞
2(log(2p) + t) + 2(log(2p) + t) .
11.2.4

The sets T1 , T2 and T3

Write
v0 :=

kΣ0 k1/2
∞



p


2n(log(2p) + t) + 2(log(2p) + t) /λ.

We now define a suitable subset of the underlying probability space, on which
we can derive the searched for inequality. This subset will be the intersection
of the following sets:


√
√
T
T1 :=
k(X−S AXS ) ǫk∞ ≤ λv0 , U(S) ≤ s + 2x ,


T
∗
0
T2 :=
k(X X − nΣ0 )(β − β )k∞ ≤ λδ ,


2
2 2
T3 :=
κ̂ ((v − v0 − δ)/δ, S) ≥ (1 − η) κ (S) ,
1/2

where x > 0 is arbitrary, δ := kΣ0 (β ∗ −β 0 )k2 , and where η ∈ (0, 1) is arbitrary.
We pin down η to η = 1/2 like we did with ν. We require that ν − v0 − 2δ > 0.
Since ν = 1/2 and v0 ≤ 1/3 this is the case for δ ≤ 1/(12). In view of Lemma
11.1, Theorem 4.1 is about the case δ = o(1), so δ ≤ 1/(12) will be true for n
sufficiently large.
11.2.5

Deterministic part

Lemma 11.3 On T1 ∩ T2 ∩ T3 it holds that


√
r
√
√
λ
Λmax
n
s
∗
nδ + 2x.
+
kX(β̂ − β )k2 ≤
2
(1 − ν) λ
κ (S) (1 − η)n
Proof of Lemma 11.3. The KKT conditions (15) and (16), for β ∗ and β̂
respectively, are
X T X(β ∗ − β 0 ) + λζ ∗ = Z,

with Z := (X T X − nΣ0 )(β ∗ − β 0 ), and

X T X(β̂ − β 0 ) + λζ̂ = X T ǫ.
So subtracting the first from the second
X T X(β̂ − β ∗ ) + λζ̂ − λζ ∗ = X T ǫ − Z.
21

Multiplying with β̂ − β ∗ yields
kX(β̂ − β ∗ )k22 + λ(β̂ − β ∗ )T (ζ̂ − ζ ∗ ) = (β̂ − β ∗ )T (X T ǫ − Z).

(17)

We write (as in the proof of Theorem 8.1) with S := S∗ (ν), s := |S|,
XS b̂S := XS (β̂S − βS∗ ) + (X−S PXS )β̂−S .
∗ = 0. Therefore
Since |ζj∗ | ≤ 1 − ν < 1 for all j ∈
/ S, it must be true that β−S

X(β̂ − β ∗ ) = XS b̂S + (X−S AXS )β̂−S .
So
T
(β̂ − β ∗ )T X T ǫ = b̂TS XST ǫ + β̂−S
(X−S AXS )T ǫ.

We use that (on T1 )
b̂TS XST ǫ ≤ U(S)kXS b̂S k2

≤ U(S)kX(β̂ − β ∗ )k2
√
√
≤ ( s + 2x)kX(β̂ − β ∗ )k2

and
T
β̂−S
(X−S AXS )T ǫ ≤ kβ̂−S k1 k(X−S AXS )T ǫk∞ ≤ λv0 kβ̂−S k1 .

Moreover (on T2 )
−(β̂ − β ∗ )T Z ≤ kβ̂ − β ∗ k1 kZk∞ ≤ λδkβ̂ − β ∗ k1 .
Then
(β̂ − β ∗ )T (ζ ∗ − ζ̂) = β̂ T ζ ∗ − β ∗T ζ ∗ + β ∗T ζ̂ − β̂ T ζ̂

= β̂ T ζ ∗ − kβ ∗ k1 + β ∗T ζ̂ − kβ̂k1

≤ kβ̂S k1 − kβS∗ k1 + kβS∗ k1 − kβ̂S k1

T
∗
+ β̂−S
ζ−S
− kβ̂S k1

T
∗
= β̂−S
ζ−S
− kβ̂S k1

≤ (1 − ν)kβ̂−S k1 − kβ̂−S k1

= −νkβ̂−S k1 .
Inserting these bounds in (17) gives

√ √
kX(β̂ − β ∗ )k22 + λ(ν − v0 − δ)kβ̂−S k1 ≤ ( s + 2x)kX(β̂ − β ∗ )k2 + λδkβ̂S − βS∗ k1 .
If

√
√
kX(β̂ − β ∗ )k2 ≤ ( s + 2x)
√
we are done as by Lemma 11.2, s ≤ Λmax δn/((1 − ν)λ). If
√
√
kX(β̂ − β ∗ )k2 > ( s + 2x)
22

we get
(ν − v0 − δ)kβ̂−S k1 < δkβ̂S − βS∗ k1
or
kβ̂S − β ∗ k1 − ((ν − v0 − δ)/δ)kβ̂−S k1 > 0.
But (on T3 )
kβ̂S − βS∗ k1 − ((ν − v0 − δ)/δ)kβ̂−S k1
√
skX(β̂ − β ∗ )k2
≤ √
nκ̂((ν − v0 − δ)/δ), S)
√
skX(β̂ − β ∗ )k2
≤ √
.
nκ(S)(1 − η)
This gives
√
√ √
√
kX(β̂ − β ∗ )k2 ≤ s + 2x + λδ s/( nκ(S)(1 − η)).
√
Again, by Lemma 11.2, s ≤ Λmax δn/((1 − ν)λ). We see that


√
√
√
√
Λmax
n
s
λ
∗
kX(β̂ − β )k2 ≤
nδ + 2x.
+
(1 − ν) λ
κ(S)(1 − η) (1 − η)n
⊓
⊔
11.2.6

Random part

We apply the tools of Section 12.
Lemma 11.4 It holds that


IP T1 ∩ T2 ∩ T3 ≥ 1 − 4 exp[−t] − exp[−x] − o(1).
Proof of Lemma 11.4 . We first show that IP(T1 ) ≥ 1 − 2 exp[−t] − exp[−x].
One component of this is to show that with probability at least 1 − 2 exp[−t]
k(X−S AXS )T ǫk∞ ≤ λv0 .
For a square matrix B, let diag(B) be its diagonal. By Lemma 12.1 we know
that with probability at least 1 − exp[−t]
p
k(X−S AXS )T ǫk∞ ≤ kdiag((X−S AXS )T (X−S AXS ))k1/2
2(log(2p) + t).
∞
But

kdiag((X−S AXS )T (X−S AXS ))k∞ ≤ kdiag(X T X)k∞ .
Moreover in view of Lemma 12.2, and using the union bound, with probability
at least 1 − exp[−t]
1/2
diag(kX T X)k∞
−

√

1/2
nkdiag(Σ0 )k1/2
∞ ≤ kΣ0 k∞

23

p

2(log(2p) + t).

So with probability at least 1 − 2 exp[−t]


p
T
1/2
2n(log(2p) + t) + 2(log(2p) + t) ≤ λv0 .
k(X−S AXS ) ǫk∞ ≤ kΣ0 k∞
The second component is to show that
√
√
IP(U(S) ≤ s + 2x) ≤ exp[−x],

but this follows immediately from Lemma 12.2.
Next we show that IP(T2 ) ≤ 2 exp[−t]. Set Z := (X T X − nΣ0 )(β ∗ − β 0 ).
Clearly X(β ∗ − β 0 ) is a Gaussian vector with i.i.d. entries with mean zero and
1/2
variance kΣ0 (β ∗ −β 0 )k22 . Hence, applying Lemma 12.3 with σu2 ≤ kΣ0 k∞ , σv2 =
1/2
kΣ0 (β ∗ − β 0 )k22 and using the union bound, we obtain that with probability
at least 1 − 2 exp[−t]


p
1/2 ∗
1/2
0
2n(log(2p) + t + log(2p) + t .
kZk∞ ≤ 3kΣ0 k∞ kΣ0 (β − β )k2
Finally, the result IP(T3 ) = 1 − o(1) follows from Lemma 3.4.
11.2.7

⊓
⊔

Collecting the pieces

Combining Lemma 11.3 with Lemma 11.4 completes the proof of Theorem 4.1.

11.3

Proof of Theorems 4.2 and 4.3

We use the concentration of measure, Lemma 12.4.
Proof of Theorem 4.2. Let m∗ := E(kX(
I
β̂ − β ∗ )k2 |X). Then we have (by
Lemma 12.4) that with probability at least 1 − 1/8 − 3/4 − o(1)
p
kX(β̂ − β ∗ )k2 ≥ m∗ − 2 log 2
as well as (by Theorem 4.1),

Thus

p
√
1/2
kX(β̂ − β ∗ )k2 ≤ γ nkΣ0 (β ∗ − β 0 )k2 + 2 log 2.
p
√
1/2
m∗ ≤ γ nkΣ0 (β ∗ − β 0 )k2 + 4 log 2.

Applying again Lemma 12.4 we see that


p
√
√
1/2 ∗
0
∗
IP kX(β̂ − β )k ≥ γ nkΣ0 (β − β )k2 + 4 log 2 + 2x


∗

∗

≤ IP kX(β̂ − β )k ≥ m +
24

√

2x



≤ 2 exp[−x].

⊓
⊔
Proof of Theorem 4.3. By the triangle inequality
kX(β̂ − β 0 )k2 − kX(β ∗ − β 0 )k2 ≤ kX(β̂ − β ∗ )k2 .
By Lemma 12.2, with with probability at least 1 − 2/n
kX(β ∗ − β 0 )k2 −

√

p
1/2
1/2
nkΣ0 (β ∗ − β 0 )k2 ≤ ( 2 log n)kΣ0 (β ∗ − β 0 )k2 .

So with probability at least 1 − 4 exp[−t] − exp[−x] − o(1) − 2/n (subtracting
the term 2/n to follow the argument, as of course it can be included in the o(1)
term)
1/2

kX(β̂ −β 0 )k2 −kΣ0 (β ∗ −β 0 )k2 ≤ (γ+

p

√
√
1/2
2 log n/n) nkΣ0 (β ∗ −β 0 )k2 + 2x.

Let m0 := E(kX(
I
β̂ − β 0 )k2 |X). Using the same arguments as in Theorem 4.2,
we arrive at
p
p
p
√
1/2
m0 − 2 log 2 ≤ (1 + γ + 2 log n/n) nkΣ0 (β ∗ − β 0 )k2 + 2 log 2
and

(1 − γ −
or
m0 −

√

p

p
p
√
1/2
2 log n/n) nkΣ0 (β ∗ − β 0 )k2 − 2 log 2 ≤ m0 + 2 log 2,

1/2

nkΣ0 (β ∗ − β 0 )k2 ≤ (γ +

p
p
√
1/2
2 log n/n) nkΣ0 (β ∗ − β 0 )k2 + 4 log 2.

Thus, inserting the triangle inequality
kX(β̂ − β 0 )k2 −

√
1/2
nkΣ0 (β ∗ − β 0 )k2

≤

kX(β̂ − β 0 )k2 − m0 + m0 −

≤

kX(β̂ − β 0 )k2 − m0 + (γ +

√

p

1/2

nkΣ0 (β ∗ − β 0 )k2

p
√
1/2
2 log n/n) nkΣ0 (β ∗ − β 0 )k2 + 4 log 2.

Apply Lemma 12.4 again to finalize the result.

11.4

⊓
⊔

Proof of Theorem 5.1

To establish Theorem 5.1, we first need to study the minimizer b∗ in (5). The
minimization


2
min kXbk2 : kbS k1 − kb−S k1 = 1
25

has non-convex constraints. If we fix the signs within S of a possible solution
b, one can reformulate it as a convex problem with convex constraints. This is
done in Lemma 11.5. We then show that b∗j 6= 0 for all j ∈ S in Lemma 11.6.
This is important because given the signs within S of a potential solution b,
we want the restrictions on these signs to be non-active so that the Lagrangian
formulation is of a similar form as the KKT conditions (4) for the noiseless
Lasso. This Lagrangian form is then given in Lemma 11.8 with Lemma 11.7
serving as a preparation. The Lagrangian form of Lemma 11.8 with S = S0 in
a sense resembles the KKT conditions (4) when the active coefficients in the
vector βS0 have appropriate signs and |βj0 | is for j ∈ S0 large enough. This
allows one to find a solution β ∗ of the KKT conditions (4) with the prescribed
prediction error.
11.4.1

Non-sparseness within S

Our first step is to ascertain that a solution


∗
b ∈ arg minp kXbk2 : kbS k1 − kb−S k1 = 1
b∈R

can be found by searching over (at most) 2|S| convex problems with convex constraints. This is done in the next lemma, where we also show that the equality
constraint kbS k1 − kb−S k1 = 1 can be replaced by an inequality constraint
kbS k1 − kb−S k1 ≥ 1.
Lemma 11.5 We have


2
min kXbk2 : kbS k1 − kb−S k1 = 1


2
= min kXbk2 : kbS k1 − kb−S k1 ≥ 1


2
=
min min kXbk2 : zj bS − kb−S k1 ≥ 1, zj bj ≥ 0 ∀ j ∈ S .
zS ∈{±1}|S|

b

Proof of Lemma 11.5. To show that the equality constraint can be turned
into an inequality constraint let us consider some b ∈ Rp for which it holds that
kbS k1 − kb−S k1 = c, where c is a constant bigger than 1. Let b̃ := b/c. Then


kb̃S k1 − kb̃−S k1 = kbS k1 − kb−S k1 /c = 1.
Moreover
kX b̃k2 = kXbk2 /c < kXbk2 .
Thus the first equality of the lemma must be true.
We now show the second equality of the lemma. If for some zS ∈ {±1} it holds
that zj bj ≥ 0 for all j ∈ S, we have zST bS = kbS k1 . Conversely, if we define
26

for j ∈ S with bj 6= 0, zj := bj /|bj | as the sign of bj , and define zj ∈ {±1}
arbitrarily for j ∈ S with bj = 0, then we have zj bj ≥ 0 for all j ∈ S. Thus




T
b : kbS k1 − kb−S k1 ≥ 1 = ∪zS ∈{±1}|S| b : zS bS − kb−S k1 ≥ 1, zj bj ≥ 0 .
⊓
⊔

We establish in the next lemma that sign constraints on b∗S are not active: b∗S
is so to speak maximally non-sparse. We assume that κ̂2 (S) > 0, so for S = S0
we implicitly assume Condition 3.1.

Lemma 11.6 Suppose that κ̂(S) 6= 0. Then for any minimizer b∗ of the problem


min kXbk2 : kbS k1 − kb−S k1 = 1

it holds that b∗j 6= 0 for all j ∈ S.

Remark 11.1 A (very) special case of Lemma 11.6 is the minimization problem


∗
2
bS ∈ arg min kbS k2 : kbS k1 = 1 .

Clearly the solution has |b∗j | = 1/|S| =
6 0 for all j ∈ S. More generally, for
the case without “b−S -part” one can apply a geometric argument to show that
whenever XST XS is non-singular
b∗S ∈ arg min{kXbS k2 : kbS k1 = 1}
must have all its components in S nonzero. Indeed , let r := kXb∗S k2 . Then r >
0 by the non-singularity of XST XS . Let E be the ellipsoid E := {bS : kXbS k2 ≤ r}
and B := {bS : kbS k1 ≤ 1}. It is easy to see that E must be included in B. Now
b∗S is a point on the boundary of both E and B, so any supporting hyperplane to
and B must also be supporting to E. The key observation is that any point on
the boundary of E has a unique supporting hyperplane (given by the gradient of
the quadratic form); and that points on the boundary of B that have a unique
supporting hyperplane are exactly those points with no zero entry.
Proof of Lemma 11.6. We use the representation of Lemma 11.5. Let zS∗ ∈
{±1}|S| satisfy zS∗T b∗S = kb∗S k1 and zj∗ b∗j ≥ 0 for all j ∈ S. Then b∗ is a solution
of the convex minimization problem with (linear and) convex constraints


2
∗T
∗
min kXbk2 : zS bS − kb−S k1 ≥ 1, zj bj ≥ 0, ∀ j ∈ S .
Note that in the minimization, one may replace the inequality constraint zS∗T bS −
kb−S k1 ≥ 1 by an inequality constraint zS∗T bS − kb−S k1 = 1. This follows from
the same arguments as used in the proof of Lemma 11.5. A reason to replace the
equality constraint by an inequality constraint is that the restrictions become
convex.

27

The solution of the convex problem with convex constraints can be found using
Lagrange multipliers λ̃ and µS , where λ̃ ≥ 0 and where µS is an |S|-vector with
non-negative entries. The Lagrangian formulation is




X
2
∗T
∗
min kXbk2 + 2λ̃ kb−S k1 − zS bS − 1 − 2
µj,S zj bj .
j∈S

Because the inequality constraint can be replaced by an equality constraint, we
know that in fact λ̃ > 0. The Lagrangian formulation has has KKT conditions
X T Xb∗ = λ̃z ∗ + diag(µS )zS∗ ,
∗ is an element of the sub-differential
where z−S

−∂kb∗−S k1



∗
T ∗
= z−S : kz−S k1 ≤ 1, z−S b−s = −kb−S k1 .

It follows that for j ∈ S

b∗j 6= 0 ⇒ µj,S = 0.

Let N := {j ∈ S : b∗j = 0}. Then we have by the above argument
∗
(X T Xb∗ )−N = λ̃z−N
∗
∗
(X T Xb∗ )N = λ̃zN
+ diag(µN )zN
.

The tangent plane of {b : kXbk2 = kXb∗ k2 } at b∗ is
U := {u = b∗ + v : v T X T Xb∗ = 0}.
The idea of the proof is now to take an element u = b∗ + tv in this tangent plane
with t > 0 and with vj 6= 0 for at least one j ∈ N and such that vj 6= 0 has the
same sign as b∗j for all j ∈ S\N . For j ∈
/ S we take vj = 0. Then b̃ := b∗ + tv
has kb̃S k1 − kb̃−S k1 > 1 and this leads for a suitable scale t to
kX b̃k2

kb̃S k1 − kb̃−S k1

< kXb∗ k2 .

Let us now work out this idea. It cannot be true that b∗j = 0 for all j ∈ S as
kb∗S k1 ≥ 1. Hence S\N 6= ∅. Take (for example) vj = zj∗ for all j ∈ S\N . Then
T
∗
∗T
∗
vS\N
zS\N
= zS\N
zS\N
= |S\N |.

Now λ̃ > 0 and the entries of µN are all positive as well (since µj = 0 for some
j ∈ N would imply b∗j = 0 for this j, which is not possible by the definition of
N ). Therefore we can choose
T
∗
∗
vN
(λ̃zN
+ diag(µN )zN
) = −λ̃|S\N |.

28

Then at least one entry of vN has to be non-zero and moreover
T
∗
T
∗
∗
v T X T Xb∗ = λ̃vS\N
zS\N
+ vN
(λ̃zN
+ diag(µN )zN
)

= λ̃|S\N | − λ̃|S\N |
= 0.

We thus have for all t > 0
kX(b∗ + tv)k22 = kXb∗ k22 + t2 kXvk22 .
Moreover
kb∗S + tvS k1 = kb∗S\N k1 + tkvS\N k1 + tkvN k1
= kb∗S k1 + tkvk1 .

Therefore
kb∗S + tvS k1 − kb∗−S k1 = kb∗S k1 − kb∗−S k1 + tkvk1
= 1 + tkvk1 .

It follows that
(kb∗S

kX(b∗ + tv)k22
+ tvS k1 − kb∗−S k1 )2

kXb∗ k22 + t2 kXvk22
.
(1 + tkvk1 )2

=
Define

A := kXb∗ k22 + t2 kXvk22 − kXb∗ k22 (1 + tkvk1 )2
=

=

t2 kXvk22 − 2tkXb∗ k22 kvk1 − t2 kXb∗ k22 kvk21

t2 (kXvk22 − kXb∗ k22 kvk21 ) − 2tkXb∗ k22 kvk21 .

We will show that for suitable t > 0 the constant A is strictly negative. This
means
kX(b∗ + tv)k22 < kXb∗ k22 (kb∗S + tvS k1 − kb∗−S k1 )2
and so we arrive at a contradiction. To show A < 0 we distinguish two cases.
If
kXvk22 ≤ kXb∗ k22 kvk21
then A < 0 for all t > 0. If
kXvk22 > kXb∗ k22 kvk21
then A < 0 for all t satisfying
0<t<

2kXb∗ k22 kvk21
.
kXvk22 − kXb∗ k22 kvk21

Here we used the assumption that kXb∗ k22 > 0 so that the above right hand
side is indeed strictly positive.
⊓
⊔
29

11.4.2

Lagrangian form

We now present the Lagrangian form given the signs within the set S and given
that within the set S the solution has non-zero entries. Let for each zS ∈ {±1}|S|


∗
2
T
b (zS ) ∈ arg min kXbk2 : zS bS − kb−S k1 ≥ 1, zj bj ≥ 0, ∀ j ∈ S .
Define
ZS :=



|S|

zS ∈ {−1, 1}

:

zj b∗j (zS )


>0∀j∈S .

Lemma 11.7 We have for all zS ∈ ZS

X T Xb∗ (zS ) = z ∗ (zS )kXb∗ (zS )k22

∗ (z ) ∈ −∂kb∗ (z )k .
where zS∗ (zS ) = zS and z−S
S
−S S 1

Proof of Lemma 11.7. To prove this result it is useful to repeat some arguments of the proof of Lemma 11.6. The convex minimization problem with
(linear and) convex constraints


min kXbk22 : zST bS − kb−S k1 ≥ 1, zj bj ≥ 0, ∀ j ∈ S
can be solved using Lagrange multipliers λ̃ and µS , where λ̃ > 0 and µS is an
|S|-vector with non-negative entries. The Lagrangian formulation is




X
2
T
min kXbk2 + 2λ̃ kb−S k1 − zS bS − 1 − 2
µj,S zj bj .
j∈S

This has KKT conditions
X T Xb∗ (zS ) = λ̃z ∗ + diag(µS )zS ,
∗
∗ (z ) depends on z and is an element of the
where zS∗ = zS and z−S
= z−S
S
S
sub-differential


∗
T
∗
∗
−∂kb−S (zS )k1 = z−S : kz−S k∞ ≤ 1, z−S b−S (zS ) = −kb−S k1 .

It follows that for j ∈ S

b∗j (zS ) 6= 0 ⇒ µj,S = 0.

The assumption that zS ∈ ZS thus gives µS = 0. The KKT conditions then
read
X T Xb∗ (zS ) = λ̃z ∗ .
One sees that
1 = z ∗T b∗ (zS ) = b∗T (zS )X T Xb∗ (zS )/λ̃ = kXb∗ (zS )k22 /λ̃.
This gives
λ̃ = kXb∗ (zS )k22 .

⊓
⊔

We apply the above lemma with zS := ∂kb∗S k1 . This gives the following result.
30

Lemma 11.8 Suppose κ̂(S) 6= 0. Let


∗
2
b ∈ arg min kXbk2 : kbS k1 − kb−S k1 = 1
Then
X T Xb∗ = z ∗ kXb∗ k22 .

∗ ∈ −∂kb∗ k .
where zS∗ = ∂kb∗S k1 and z−S
−S 1

Proof of Lemma 11.8. By Lemma 11.6, for each


∗
2
b ∈ arg min kXbk2 : kbS k1 − kb−S k1 = 1
it holds that b∗j =
6 0 for all j ∈ S. We can therefore define zj∗ := b∗j /|b∗j | for all
j ∈ S and then zS∗ = ∂kb∗S k1 ∈ ZS . The result now follows from Lemma 11.7.
⊓
⊔
11.4.3

Finalizing the proof of Theorem 5.1.

With the help of Lemma 11.8 we are now in the position to prove Theorem 5.1.
Proof of Theorem 5.1. Let b∗ and z ∗ be as in Lemma 11.8, with S = S0 .
Define
b∗ s0 λ∗
.
β′ = β0 − 2
κ̂ (S0 ) n
Then
λ∗ X T Xb∗ s0
nκ̂2 (S0 )
λ∗ X T Xb∗
= −
kXb∗ k22
= −λ∗ z ∗ .

X T X(β ′ − β 0 ) = −

Let S∗ := {j : b∗j 6= 0}. Then by Lemma 11.6, S0 ⊂ S∗ . Furthermore

∗ 0
∗ ∗
∗ 2

zj βj − λzj bj /kXb k2 > 0
zj∗ βj′ = −λ∗ zj∗ b∗j /kXb∗ k22 > 0


0

j ∈ S0
j ∈ S∗ \S0 .
j∈
/ S∗

It follows that z ∗ ∈ ∂kβ ′ k1 . Thus, β ′ =: β ∗ is a solution of the KKT conditions
(4) with ζ ∗ = z ∗ . It holds moreover that
kX(β ∗ − β 0 )k22 =

λ∗2 s0
λ∗2 kXb∗ k22
=
.
nκ̂2 (S0 )
kXb∗ k42
⊓
⊔

31

11.5

Proof of Theorem 6.1.

The proof of Theorem 6.1 consists of several steps. First we note that, given
the sizes of its jumps, the total variation of a function is the smallest when this
function is decreasing or increasing. This is stated in Lemma 11.9 as a trivial
fact. As a consequence, if one subtracts from an arbitrary function value - or
minus this value - the total variation, the result will be at most the average
of the absolute values. This is shown in Lemma 11.10. Lemma 11.10 is then
applied at each jump separately, as kbS k1 − kb−S k1 in this example amounts to
subtracting at each jump some total variation to the left or to the right of this
jump. Lemma 11.11 shows how this works for one jump. Then Theorem 6.1
is in part proved by applying this lemma to each jump. This leads to a lower
bound for κ̂2 (S). The proof is completed by showing that this lower bound is
achieved by the vector b∗ as given in Theorem 6.1.
For f ∈ Rn we define the ordered vector
f(1) ≤ · · · ≤ f(n) ,
with arbitrary ordering within ties.
Lemma 11.9 It holds that
T V (f ) ≥ f(n) − f(1)
with equality if f is increasing or decreasing.
⊓
⊔

Proof of Lemma 11.9. Trivial.
Lemma 11.10 It holds for any j ∈ {1, . . . , n} that
n

fj − TV(f ) ≤ f(1) ≤

1X
|fi |,
n
i=1

and

n

−fj − TV(f ) ≤ −f(n) ≤

1X
|fi |.
n
i=1

Proof of Lemma 11.10. We have from Lemma 11.9 that TV(f ) ≥ f(n) − f(1) .
Moreover, fj ≤ f(n) . Thus
fj − TV(f ) ≤ fj − (f(n) − f(1) )

≤ f(n) − (f(n) − f(1) )

= f(1) .

P
Case 1: if f(1) < 0 obviously f(1) < n1 ni=1 |fi |.
Case 2: if f(1) ≥ 0 then fi ≥ 0 for all i and then
f(1) ≤

n
X

fi /n =

n
X
i=1

i=1

32

|fi |/n.

In the same way
−fj − TV(f ) ≤ −fj − (f(n) − f(1) )

≤ −f(1) − (f(n) − f(1) )

Case 1: if f(n)
Case 2: if f(n)

= −f(n) .
P
> 0 then −f(n) < n1 ni=1 |fi |.
≤ 0 then fi ≤ 0 for all i and then
−f(n) ≤ −

n
X

fi /n =

n
X

|fi |/n.

i=1

i=1

⊓
⊔

Pn

Lemma 11.11 Let f ∈ Rn with total variation
TV(f ) = i=2 |fi − fi−1 | and
Pm
g ∈ Rm with total variation TV(g) =
|g
− gi−1 |. Then for any j ∈
i
i=2
{1, . . . , n} and k ∈ {1, . . . , m}
n

m

i=1

i=1

1 X
1X
|fi | +
|gi |.
n
m

|fj − gk | − TV(f ) − TV(g) ≤

Proof of Lemma 11.11. Suppose without loss of generality that fj ≥ gk .
Then by Lemma 11.10
|fj − gk | − TV(f ) − TV(g) = (fj − TV(f )) + (−gk − TV(g))
}
| P {z
} | P {z
≤

n
X

1
n

≤

n
i=1

i=1

≤

|fi |/n

|fi | +

1
m

m
X
i=1

m
i=1

|gi |/m

|gi |.

⊓
⊔

Proof of Theorem 6.1. Let for j = 2, . . . , s, uj ∈ N satisfy 1 ≤ uj ≤ dj − 1.
We may write for f = Xb,
kbS k1 − kb−(S∪{1}) k1
= |fd1 +1 − fd1 | −

d1
X
i=2

|fi − fi−1 | −

+ |fd1 +d2 +1 − fd1 +d2 | −
···

dX
1 +d2

i=d1 +u2 +1

dX
1 +u2

i=d1 +2

|fi − fi−1 | −

+ |fd1 +···+ds−1 +1 − fd1 +···+ts−1 |
d1 +···+ds−1

−

X

i=d1 +···+ds−2 +us−1 +1

−

d1 +···+d
X s

i=d1 +···+ds−1 +us +1

|fi − fi−1 | −
33

d1 +d
2 +u3
X

i=d1 +d2 +2

|fi − fi−1 |

d1 +···+ds−1 +us

|fi − fi−1 | −

+ |fd1 +···+ds +1 − fd1 +···+ds |

|fi − fi−1 |

X

i=d1 +···+ds−1 +2

n
X

i=d1 +···+ds +2

|fi − fi−1 |

|fi − fi−1 |

≤
+

d1
d1 +u2
1 X
1 X
|fi | +
|fi |
d1
u2
i=1

1
d2 − u2

···
+

+

≤

i=d1 +1

dX
1 +d2

i=d1 +u2 +1

1
ds−1 − us−1
1
ds − us

1
|fi | +
u3

d1 +d
2 +u3
X

i=d1 +d2 +1

|fi |

d1 +···+ds−1

X

i=d1 +···+ds−2 +us−1 +1
d1 +···+d
X s

i=d1 +···+ds−1 +us +1

|fi | +

|fi | +

1
us

X

i=d1 +···+ds−1 +1
n
X

1
ds+1

d1 +···+ds−1 +us

i=d1 +···+ds +1

|fi |

|fi |

s

1
1
1
1
1
1
1
+
+
+ ··· +
+
+
+
d1 u2 d2 − u2
ds−1 − us−1 us ds − us ds+1
v
u n
uX
|fi |2 ,
×t
i=1

where in the first inequality we applied Lemma 11.11 and the second one follows
from the Cauchy-Schwarz inequality. The assumption that for all j ∈ {2, . . . , s}
that dj is even allows us to take uj = dj /2 to arrive at
κ2 (S) ≥

n
d1

+

s+1
Ps 4n
j=2 dj

+

n
ds+1

.

Now for the reverse inequality, let b̃ be given as in the theorem and and f˜ := X b̃.
Then f˜ is equal to


− dn1
i = 1, . . . , d1




2n

i = d1 + 1, . . . , d1 + d2

 d2
.
.
f˜i = ..

Ps−1
Ps


2n
s

i = j=1 dj + 1, . . . , j=1 dj
(−1) ds


P

(−1)s+1 n
i = s d + 1, . . . , n
j=1 j

ds+1

34

By the definition of f˜ = X b̃,
kb̃S k1 =

s
X
j=1

n
2n
+
d1
d2

|f˜dj +1 − f˜dj | =

2n 2n
+
d2
d3
..
.
2n
2n
+
+
ds−1
ds
2n
n
+
+
ds
ds+1
s
X
4n
n
n
+
+
,
=
d1
dj
ds+1

+

j=2

and also
n
X
i=1

f˜i2 = d1 f˜t21 + · · · + ds+1 f˜d2s+1
s

=

X n2
n2
n2
+4
+
.
d1
dj
ds+1
j=2

Note also that
kb̃−(S∪{1}) k1
=

d1
X
i=2

|f˜i − f˜i−1 | +

= 0

d2
X

i=d1 +2

|f˜i − f˜i−1 | + · · · +

n
X

i=d1 +···+ds +2

|f˜i − f˜i−1 |

It follows that
(s + 1)kX b̃k22 /n
(kb̃S k1 − kb̃−(S∪{1}) k1 )2

=

=

11.6

Pn

˜2
i=1 fi /n

2
˜
˜
j=1 |fdj +1 − fdj |


Ps
n
d1

+

s+1
Ps 4n
j=2 dj

+

n
ds+1

.
⊓
⊔

Proof of Theorem 7.1.

To prove Theorem 7.1, we first establish the Lagrangian form of the minimization problem where we have the convex constraint zS∗T0 (v̄)bS0 − kW b−S0 k1 ≥ 1.
Then we recall the projections and we introduce a subset T of the underlying
probability space where the lower bound of Theorem 7.1 holds. The latter is
shown in Lemma 11.13. Finally, we show that the subset T has large probability.
35

11.6.1

Lagrangian form

Recall for w ∈ W(v̄) the convex problem with linear and convex constraints


2
∗T
b(w) ∈ arg min kXbk2 : zS0 (v̄)bS0 − kW b−S0 k1 ≥ 1 .
Note that here we do not require the positivity constraint zj∗T (v̄)bj ≥ 0 for all
j ∈ S0 . The next lemma gives its Lagrangian form. This form plays in the proof
of Theorem 7.1 the same role as in the proof of Theorem 5.1 for the noiseless
version. We also show that for w ∈ W(v̄) the minimum kXb(w)k22 is not larger
than kXb∗ (v̄)k22 (recall that by definition κ̂2 (1 + v̄, S0 ) = s0 kXb∗ (v̄)k22 /n).
Lemma 11.12 We have
X T Xb(w) = kXb(w)k22 W z(w),
with
zS0 (w) = zS∗ 0 (v̄), z−S0 (w) ∈ −∂kb−S0 (w)k1 .
Moreover, for w ∈ W(v̄)
s0 kXb(w)k22 /n ≤ κ̂2 (1 + v̄, S0 ).
Proof of Lemma 11.12. The problem


min kXbk22 : zS∗T0 (v̄)bS0 − kW b−S0 k1 ≥ 1
has Lagrangian
X T Xb(w) = λ̃W z(w)
with zS0 (w) = zS∗ 0 (v̄) and z−S0 (w) ∈ −∂kb−S0 (w)k1 . Moreover
kXb(w)k22 = λ̃b(w)T W z(w) = zS∗T0 (v̄)bS0 − kW b−S0 k1 = 1
because the minimum is reached at the boundary. So
λ̃ = kXb(w)k22 .
To obtain the second statement of the lemma, we use similar arguments as in
the proof of Lemma 3.1. We have


kXbk2
∗T
kXb(w)k2 = minp ∗T
: zS0 (v̄)bS0 − kW−S0 b−S0 k1 > 0
b∈R
zS0 (v̄)bS0 − kW−S0 b−S0 k1
But for w ∈ W and w̄ := 1 + v̄, we know
kW b−S0 k1 ≤ kW̄ b−S0 k1
and so
zS∗T0 (v̄)bS0 − kW b−S0 k1 > zS∗T0 (v̄)bS0 − kW̄ b−S0 k1 .
36

Let



∗T
A := b : zS0 (v̄)bS0 − kW b−S0 k1 > 0

and



∗T
B := b : zS0 (v̄)bS0 − kW̄ b−S0 k1 > 0 .

Then B ⊂ A. Hence
kXbk2
− kW b−S0 k1

kXb(w)k2 = min

zS∗T0 (v̄)bS0

≤ min

zS∗T0 (v̄)bS0

b∈A

b∈B

kXbk2
− kW b−S0 k1

kXbk2
− kW̄ b−S0 k1

≤ min

zS∗T0 (v̄)bS0
kXb∗ (v̄)k2
b∈B

=
=

√
nκ̂(1 + v̄, S0 )
.
√
s0
⊓
⊔

11.6.2

Projections

Recall the notation of Subsection 7.2 and that moreover the diagonal elements
of the matrix (XST0 XS0 )−1 are denoted by {u2j }j∈S0 . We write
ûS0 := (XST0 XS0 )−1 XST0 ǫ.
We denote the projection of ǫ on the space spanned by the columns of XS0 by
ǫPXS0 := XS0 (XST0 XS0 )−1 XST0 ǫ = XS0 ûS0
and write
U(S0 ) := kǫPXS0 k2 .
11.6.3

Choice of λ

Recall that we require that for some t > 0
p
λ > kv−S0 k∞ 2(log(2p) + t).
11.6.4

The set T

Recall
ūj := uj

p

2(log(2p) + t)/λ, j ∈ S0 , v̄j := vj
37

p
2(log(2p) + t)/λ, j ∈
/ S0 . (18)

Let T be the set
T

:=
∩



|ûj | ≤ λūj ∀j ∈ S0

 

√
√
|v̂j | ≤ λv̄j ∀j ∈
/ S0 ∩ U(S0 ) ≤ s0 + 2x .

We show in Subsection 11.6.6 that IP(T ) ≥ 1 − exp[−t] − exp[−x].
11.6.5

Deterministic part

The idea is now to incorporate the noisy part of the KKT conditions for the
noisy Lasso into a weighted sub-differential, creating in that way KKT conditions of the same for as the noiseless KKT conditions (see (19) in the proof). To
do so, we first put part of the noise in the vector β 0 without adding additional
non-zeros. This makes it possible not to change the sub-differential at S0 . The
rewriting of the KKT conditions make them resemble the Lagrangian form of
Lemma 11.12.
We will use the KKT conditions (16) for β̂:
−X T (Y − X β̂) = −λζ̂, ζ̂ ∈ ∂kβ̂k1 .
Lemma 11.13 Suppose we are on the set T defined in Subsection 11.6.4. Then
under the conditions of Theorem 7.1
√
√
λ s0
0
+ 2x
kX(β̂ − β )kn ≥ √
nκ̂(1 + v̄, S)
Proof of Lemma 11.13. Set
0
β̂S0 0 := β 0 + ûS0 , β̂−S
:= 0.
0

Then
Y

= Xβ 0 + ǫ
= XS0 βS0 0 + XS0 ûS0 + ǫAXS0
= X β̂ 0 + ǫAXS0 .

The KKT conditions (16) are
−X T (Y − X β̂) = −λζ̂.
We have
Y − X β̂ = −X(β̂ − β̂ 0 ) − ǫAXS0 .
Therefore
−X T (Y − X β̂) = X T X(β̂ − β̂ 0 ) − X T (ǫAXS0 ).
38

But
XST0 (ǫAXS0 ) = 0,
and
T
T
T
X−S
(ǫAXS0 ) = X−S
− X−S
XS0 (XST0 XS0 )−1 XST0 ǫ
0
0
0

= (X−S0 AXS0 )T ǫ.

Hence the KKT conditions read
X T X(β̂ − β̂ 0 ) = −λζ̂ + v̂,
where
v̂S0 = 0, v̂−S0 = (X−S0 AXS0 )T ǫ.
Set Ŝ := {j : β̂j 6= 0} and define for all j ∈ Ŝ\S0
ŵj := 1 + v̂j /(λζ̂j ).
By assumption (since we are on T ) |v̂j | < λv̄j . so ŵj ≥ 1 − v̄j for all j ∈ Ŝ\S0 .
For j ∈
/ Ŝ ∪ S0 we define
ŵj := max{|1 + v̂j /λ|, 1 − v̄j }.
Then for j ∈
/ Ŝ ∪ S0
λζ̂j + v̂j = λ|ζ̂j + v̂j /λ|sign(ζ̂j + v̂j /λ)
(
ŵj sign(ζ̂j + v̂j /λ),
=
|ζ̂ +v̂ /λ|
ŵj j1−v̄jj sign(ζ̂j + v̂j /λ)

|ζ̂j + v̂j /λ| ≥ 1 − v̄j

|ζ̂j + v̂j /λ| ≤ 1 − v̄j

= ŵj ζ̃j ,
where
ζ̃j :=

(
sign(ζ̂j + v̂j /λ),
|ζ̂j +v̂j /λ|
1−v̄j sign(ζ̂j

+ v̂j /λ)

|ζ̂j + v̂j /λ| ≥ 1 − v̄j

|ζ̂j + v̂j /λ| ≤ 1 − v̄j

.

One readily verifies that (on T ) ŵj ≤ 1 + v̄j for all j ∈
/ S0 . Taking ζ̃j = ζ̂j for
j ∈ S ∪ S0 we arrive at the KKT conditions
X T X(β̂ − β̂ 0 ) = −λŴ ζ̃, ζ̃ ∈ ∂kβ̂k1

(19)

and where Ŵ = diag(ŵ) with ŵ ∈ W(v̄). Let now S0+ := {j ∈ S0 : zj∗ (v̄)bj (ŵ) >
0} and S0− := {j ∈ S0 : zj∗ (v̄)bj (ŵ) ≤ 0}. Take
β ′ = β̂ 0 − λbj (ŵ)/kXb(ŵ)k22 .
Case 1 Let j ∈ S0 . By our condition on β 0 we know that for j ∈ S0 , |βj0 | >
λ|bj (ŵ)|/kXb(ŵ)k22 + |ûS0 |, so |β̂j0 | ≥ |βj0 | − |ûS0 | > λ|bj (ŵ)|/kXb(ŵ)k22 . If
zj∗ (v̄) = 1 and bj (ŵ) > 0, then β̂j0 > 0 and
βj′ = |β̂ 0 | − λ|bj (ŵ)|/kXb(ŵ)k22 > 0.
39

If zj∗ (v̄) = 1 and bj (ŵ) ≤ 0, then β̂j0 > 0 and we have
βj′ = |β̂j0 | + λ|bj (ŵ)|/kXb(ŵ)k22 > 0.
If zj∗ (v̄) = −1 and bj (ŵ) < 0, then β̂j0 < 0 and
βj′ = −|β̂ 0 | + λ|bj (ŵ)|/kXb(ŵ)k22 < 0.
If zj∗ (v̄) = −1 and bj (ŵ) ≥ 0, then β̂j0 < 0 and
βj′ = −|β̂ 0 | − λ|bj (ŵ)|/kXb(ŵ)k22 < 0.
Case 2 Let now j ∈
/ S0 . Then
βj′ = −λbj (ŵ)/kXb(ŵ)k22 ,
so
zj (ŵ)βj′ = −λzj (ŵ)bj (ŵ)/kXb(ŵ)k22 > 0.
Thus
z(ŵ) ∈ ∂kβ ′ k1 .
Furthermore, by the first part of Lemma 11.12,
X T X(β ′ − β̂ 0 ) = −λX T Xb(ŵ)/kXb(ŵ)k2 = satisf ies − λŴ z(ŵ).
So β ′ =: β̂ satisfies the KKT conditions with ζ̃ = z(ŵ). We further have
kX(β̂ − β̂ 0 )k22 = λ2 bT (ŵ)Ŵ z(ŵ)/kXb(ŵ)k22
= λ2 /kXb(ŵ)k2

≥ λ2 s0 /(nκ̂2 (1 + v̄, S0 ))
where in the last step we used the second part of Lemma 11.12. Finally, by the
triangle inequality
kX(β̂ − β 0 )k2 ≥ kX(β̂ − β̂ 0 )k2 − U(S0 )
√
λ s0
− U(S0 )
≥ √
nκ̂(1 + v̄, S0 )
√
√
λ s0
√
≥ √
− s0 − 2x.
nκ̂(1 + v̄, S0 )
⊓
⊔
11.6.6

Random part

In Lemma 11.13, we showed that the conclusion (9) of Theorem 7.1 holds on
the set T . This subsection obtains that IP(T ) ≥ 1 − exp[−t] + exp[−x].
40

Lemma 11.14 It holds that
IP(T ) ≥ 1 − exp[−t] − exp[−x].
Proof of Lemma 11.14. Apply Lemma 12.1 with Zj = ûj /uj for j ∈ S0 and
Zj = v̂j /vj for j ∈
/ S0 to find that with probability at least 1 − exp[−t]
|ûj | ≤ λūj ∀j ∈ S0 , |v̂j | ≤ λv̄j ∀j ∈
/ S0 .
Furthermore, the random variable U2 (S0 ) has a chi-squared distribution with s0
degrees of freedom. Lemma 12.2 gives that with probability at least 1−exp[−x],
√
√
U(S0 ) ≤ s0 + 2x.
⊓
⊔
11.6.7

Collecting the pieces

Combining Lemma 11.13 with Lemma 11.14 completes the proof of Theorem
7.1.

11.7

Proof of Theorem 8.1.

The proof is along the lines of Theorem 4.1.
11.7.1

Comparing the KKT conditions

We compare the KKT conditions for the noisy Lasso with those for the noiseless
Lasso.
Lemma 11.15 It holds that
kX(β̂ − β ∗ )k22 + λkβ̂k1 − λ∗ β̂ T z ∗ ≤ (β̂ − β ∗ )T X T ǫ + (λ − λ∗ )kβ ∗ k1 .
Proof of Lemma 11.15. The KKT conditions (16) for β̂ can be written as
X T X(β̂ − β 0 ) + λζ̂ = X T ǫ.
where ζ̂ ∈ ∂kβ̂k1 . By the KKT conditions (4) for β ∗
X T X(β ∗ − β 0 ) + λ∗ ζ ∗ = 0.
Hence, taking the difference
X T X(β̂ − β ∗ ) + λζ̂ − λ∗ ζ ∗ = X T ǫ.
Multiply by (β̂ − β ∗ )T to find
kX(β̂ − β ∗ )k22 + λ(β̂ − β ∗ )T ζ̂ − λ∗ (β̂ − β ∗ )T ζ ∗ = (β̂ − β ∗ )T X T ǫ.
41

But
λ(β̂ − β ∗ )T ζ̂ − λ∗ (β̂ − β ∗ )T ζ ∗

= λkβ̂k1 − λ∗ β̂ T ζ ∗ + λ∗ kβ ∗ k1 − λβ ∗T ζ̂

= λkβ̂k1 − λ∗ β̂ T ζ ∗ + λkβ ∗ k1 − λβ ∗T ζ̂ − (λ − λ∗ )kβ ∗ k1

≥ λkβ̂k1 − λ∗ β̂ T ζ ∗ − (λ − λ∗ )kβ ∗ k1
where we used that
kβ ∗ k1 − β ∗T ζ̂ ≥ 0.
Therefore

kX(β̂ − β ∗ )k22 + λkβ̂k1 − λ∗ β̂ T z ∗ ≤ (β̂ − β ∗ )T X T ǫ + (λ − λ∗ )kβ ∗ k1 .
⊓
⊔
11.7.2

Projections

Recall the notation of Subsection 8.1. We let moreover v̂−S0 be the vector
S
v̂−S
:= (X−S AXS )T ǫ.

As before, we denote the projection of ǫ on the space spanned by the columns
of XS by ǫPXS and write
U(S) := kǫPXS k2 .
11.7.3

Choice of λ

Recall that we require that for some t > 0
p
S
λ > kv−S
k∞ 2(log(2p) + t).
11.7.4

The set T S

Recall
v̄ S := vjS
Let

p

2(log(2p) + t)/λ, j ∈
/ S.

T S := {|v̂j | ≤ λv̄j ∀ j ∈
/ S} ∩ {U(S) ≤
11.7.5

√

s+

√

2x}.

Deterministic part

Lemma 11.16 On the set T S it holds that
p
√
√
kX(β̂ − β ∗ )k2 ≤ s + 2x + (λ − λ∗ ) s/n/κ̂(w̄S , S).
42

Proof of Lemma 11.16. Since S∗ ⊂ S
X(β̂ − β ∗ ) = XS b̂S + X−S AXS β̂−S
where
XS b̂S = XS (β̂S − βS∗ ) + (X−S PXS )β̂−S .
In view of Lemma 11.15,
kX(β̂ − β ∗ )k22 + λkβ̂k1 − λ∗ β T z ∗

T
≤ b̂TS XST ǫ + X−S AXS β̂S ǫ + (λ − λ∗ )kβ ∗ k1
By the Cauchy-Schwarz inequality and since we are on T S
√
√
√
√
b̂TS XST ǫ ≤ U(S)kX b̂S k2 ≤ ( s + 2x)kX b̂S k2 ≤ ( s + 2x)kX(β̂ − β ∗ )k2
where in the last inequality we used Pythagoras rule. Moreover, by the definiS and since we are on the set T S
tion of v̂−S


X−S AXS β̂−S

T

T
S
ǫ = β̂−S
v̂−S
≤λ

X
j ∈S
/

S
v̄−S
|β̂j |.

On the other hand,
∗T
λkβ̂−S k1 − λ∗ ζ−S
β̂−S ≥ λ

X
(1 − λ∗ |ζj∗ |/λ)|β̂j |
j ∈S
/

and
(λ − λ∗ )kβ ∗ k1 − λkβ̂S k1 + λ∗ z ∗T β̂S ≤ (λ − λ∗ )kβ̂S − βS∗ k1 .

√ √
If kX(√
β̂ −β ∗ )k2 ≤ s+ 2x we are done. Suppose therefore that kX(β̂ −β ∗ k2 >
√
s + 2x. Then we see that
√
√
kX(β̂ − β ∗ )k22 − ( s + 2x)kX(β̂ − β ∗ )k2


√
√
∗
∗
= kX(β̂ − β )k2 kX(β̂ − β )k2 − s − 2x
> 0.

But then
λ

X
(1 − v̄jS − λ∗ |ζj∗ |/λ)|β̂j | < (λ − λ∗ )kβ̂S − β ∗ k1 .
j ∈S
/

or

kβ̂S − βS∗ k1 − kW̄ S β̂−S k1 > 0.
Then
p
kβ̂S − βS∗ k1 − kW̄ S β̂−S k1 ≤ ( s/n)kX(β̂ − β ∗ )k2 /κ̂(w̄S , S).
43

We thus arrive at
kX(β̂ − β ∗ )k22


p
√
√
∗
S
≤
s + 2x + (λ − λ ) s/n/κ̂(w̄ , S) kX(β̂ − β ∗ )k2

or

kX(β̂ − β ∗ )k2 ≤

11.7.6

√

s+

√

p
2x + (λ − λ∗ ) s/n/κ̂(w̄S , S).

⊓
⊔

Random part

Lemma 11.17 We have
IP(T S ) ≥ 1 − exp[−t] − exp[−x].
Proof of Lemma 11.17. This follows from Lemma 12.1 and Lemma 12.2. ⊓
⊔
11.7.7

Finalizing the proof of Theorem 8.1

Combine Lemma 11.16 with Lemma 11.17.

11.8

Proof of the lemma in Section 9

Proof of Lemma 9.1. Write gi := wi fi , i = 1, . . . , n and uj := dj /2, j =
2, . . . , s. Then we have
s
X
j=1

|gdj +1 − gdj | −

≤
+

+

i=2

|gi − gi−1 | −

j+1
s−1 dX
X

j=2 i=dj +1

d1
d1 +u2
1 X
1 X
|gi | +
|gi |
d1
u2
i=1

1
d2 − u2

···
+

d1
X

|gi − gi−1 | −

n
X

i=ds +1

|gi − gi−1 |

i=d1 +1

dX
1 +d2

i=d1 +u2 +1

|gi | +

1
u3

d1 +d
2 +u3
X

i=d1 +d2 +1

|gi |

d1 +···+ds−1

1
ds−1 − us−1

i=d1 +···+ds−2 +us−1 +1

1
ds − us

d1 +···+d
X s

X

i=d1 +···+ds−1 +us +1

|gi | +

44

|gi | +
1

ds+1

1
us

d1 +···+ds−1 +us

X

i=d1 +···+ds−1 +1
n
X

i=d1 +···+ds +1

|gi |

|gi |

≤



d1
d1 +u2
1 X
1 X
2
w + 2
wi2
d21 i=1 i
u2
i=d1 +1

1
(d2 − u2 )2

+

1
(ds−1 − us−1 )2

+

wi2

i=d1 +u2 +1

···

+

dX
1 +d2

1
+ 2
u3

d1 +d
2 +u3
X

wi2

i=d1 +d2 +1

d1 +···+ds−1

X

wi2 +

i=d1 +···+ds−2 +us−1 +1
d1 +···+d
X s

1
1
wi2 + 2
(ds − us )2
ds+1
i=d1 +···+ds−1 +us +1
X
1/2
n
fi2
×

1
u2s

d1 +···+ds−1 +us

X

wi2

i=d1 +···+ds−1 +1
n
X

wi2

i=d1 +···+ds +1

1/2

i=1

≤

r

n
n
n
n
n
n
n
+
+
+ ··· +
+
+
+
d1 u2 d2 − u2
ds−1 − us−1 us ds − us ds+1
v
u n
uX
×t
|fi |2 /n
i=1

×kwk∞ .
Moreover
s
X
j=1

wdj +1 |fdj +1 − fdj | −

−

j+1
s−1 dX
X

≤

s
X

+

j=2 i=dj +1

j=1

n
X
i=2

d1
X

wi |fi − fi−1 | −

|gdj +1 − gdj | −

d1
X
i=2

i=2

wi |fi − fi−1 |

n
X

i=ds +1

wi |fi − fi−1 |

|gi − gi−1 | −

j+1
s−1 dX
X

j=2 i=dj +1

|gi − gi−1 | −

n
X

i=ds +1

|wi − wi−1 ||fi−1 |,

and
n
X
i=2

v
v
u n
u n
uX
uX
2
2
t
|wi − wi−1 ||fi−1 | ≤
(wi − wi−1 ) t
fi−1
i=2

i=2

v
v
u n
u n
uX
uX
2
t
(wi − wi−1 ) t
fi2
≤
i=2

45

i=1

|gi − gi−1 |

Thus we conclude
s
X
j=1

−

d1
X
i=2

wdj +1 |fdj +1 − fdj |
wi |fi − fi−1 | −

j+1
s−1 dX
X

j=2 i=dj +1

wi |fi − fi−1 | −

n
X

i=ds +1

wi |fi − fi−1 |

v
v
v
u n
u n
u
s
X
X
u
uX
u1
1
4
2
t
t


kwk∞
≤
fi2 /n.
+
+
+ n
(wi − wi−1 ) t
d1
dj
ds+1


j=2

i=2

i=1

⊓
⊔

11.9

Proof of Theorem 1.1

This follows from Corollary 4.1 combined with Theorem 5.1, where in the latter
we replace Σ̂ := X T X/n by the population version Σ0 . This works because we
replaced Condition 5.1 by its population counterpart Condition 1.1.

12

Tools from probability theory

We first present three standard lemmas for Gaussian random variables, Lemmas
12.1, 12.2 and 12.3. These three lemmas are followed by a concentration of
measure result and a result for Gaussian quadratic forms.
Lemma 12.1 Let Z1 , . . . , Zp be standard normal random variables. Then it
holds for all t > 0 that


p
IP max |Zj | ≥ 2(log(2p) + t) ≤ exp[−t].
1≤j≤p

Proof of Lemma 12.1. For each t > 0
√
IP(|Z1 | ≥ 2t) ≤ 2 exp[−t].
So by the union bound, for any t > 0,


p
p
IP max |Zj | > 2(log(2p) + t)
≤ pIP(|Z1 | ≥ 2(log(2p) + t))
1≤j≤p

≤ 2p exp[−(log(2p + t)] = exp[−t].
⊓
⊔

Lemma 12.2 Let Z := (Z1 , . . . , ZT )T be a vector with i.i.d. standard Gaussian
entries. Then it holds for all x > 0 that


√
√
IP kZk2 ≥ T + 2x ≤ exp[−x]
46

and



√
√
IP |kZk2 − T | ≥ 2x ≤ 2 exp[−x].

Proof of Lemma 12.2. This follows from concentration of measure (Borell
[1975], Giné and Nickl [2015], Theorem 2.5.7) because the map Z 7→ kZk2
is Lipschitz. Alternatively, one may apply Lemma 1 in Laurent and Massart
[2000].
⊓
⊔
Lemma 12.3 Let (U, V ) ∈ Rn×2 have i.i.d Gaussian rows with mean zero and
covariance matrix
 2

σu σuv
.
σuv σv2
Then for all t > 0, with probability at least 1 − 4 exp[−t]


√
T
2nt + t .
|U V − nσuv | ≤ 3σu σv
Proof of Lemma 12.3. By standard arguments (see van de Geer [2017] for
tracking down some constants) one can derive that with probability at least
1 − 4 exp[−t]
√
|U T V − nσuv | ≤ (σu σv + 2|σu,v |) 2nt + (σu σv + 2|σu,v |)t.
We simplify this to: with probability at least 1 − 4 exp[−t]


√
T
2nt + t .
|U V − nσuv | ≤ 3σu σv
⊓
⊔
This is the concentration of measure lemma that we use in Section 4.
Lemma 12.4 For any b ∈ Rp and all x > 0, we have


√
IP kX(β̂ − b)k2 ≥ mb + 2x ≤ exp[−x]
and



√
IP kX(β̂ − b)k2 − mb ≥ 2x ≤ 2 exp[−x]

where mb := E(kX(
I
β̂ − b)k2 |X).
Proof of Lemma 12.4. This follows from concentration of measure see e.g.
Borell [1975], or Giné and Nickl [2015], Theorem 2.5.7, as the map ǫ 7→ kX(β̂ −
b)k2 is Lipschitz, see also van de Geer and Wainwright [2017].
⊓
⊔
Finally, we give a result for Gaussian quadratic forms.

47

Lemma 12.5 Let X have i.i.d. N (0, Σ0 )-distributed rows and let M be a (sequence of ) constant(s) such that


M 2 = o n/(kΣ0 k∞ log(2p)) .
Then, for a suitable sequence ηM = o(1), with probability tending to one
inf

1/2
kbk1 ≤M kΣ0 bk2

kXbk22 /n
1/2
kΣ0 bk22

≥ (1 − ηM )2 .

Proof of Lemma 12.5. See for example Chapter 16 in van de Geer [2016]
and its references, or van de Geer and Muro [2014].
⊓
⊔

References
P. C. Bellec. Optimistic lower bounds for convex regularized least-squares.
arXiv preprint arXiv:1703.01332, 2017.
V. Belloni, A.and Chernozhukov and L. Wang. Pivotal estimation via squareroot lasso in nonparametric regression. Annals of Statistics, 42(2):757–788,
2014.
C. Borell. The Brunn-Minkowski inequality in Gauss space. Inventiones Mathematicae, 30(2):207–216, 1975.
A. S. Dalalyan, M. Hebiri, and J. Lederer. On the prediction performance of
the lasso. Bernoulli, 23(1):552–581, 2017.
D.L. Donoho and J. Tanner. Neighborliness of randomly projected simplices
in high dimensions. Proceedings of the National Academy of Sciences of the
United States of America, 102(27):9452–9457, 2005.
E. Giné and R. Nickl. Mathematical Foundations of Infinite-Dimensional Models. Cambridge University Press, 2015.
C. Giraud. Introduction to High-Dimensional Statistics, volume 138. CRC
Press, 2014.
V. Koltchinskii, K. Lounici, and A.B. Tsybakov. Nuclear-norm penalization
and optimal rates for noisy low-rank matrix completion. Annals of Statistics,
39(5):2302–2329, 2011.
B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by
model selection. Annals of Statistics, pages 1302–1338, 2000.
T. Sun and C.-H. Zhang. Scaled sparse linear regression. Biometrika, 99:879–
898, 2012.
R. Tibshirani. Regression analysis and selection via the Lasso. Journal of the
Royal Statistical Society Series B, 58:267–288, 1996.
48

S. van de Geer. Estimation and Testing Under Sparsity: Ecole dEté de Probabilités de Saint-Flour XLV-2016. Springer Science & Business Media, 2016.
S. van de Geer. On the efficiency of the de-biased lasso, 2017. arXiv:1708.07986.
S. van de Geer and A. Muro. On higher order isotropy conditions and lower
bounds for sparse quadratic forms. Electronic Journal of Statistics, 8:3031–
3061, 2014.
S. van de Geer and M. Wainwright. On concentration for (regularized) emprircal
risk minimization. Sankhyā, 79-A:159–200, 2017.
S.A. van de Geer. The deterministic Lasso. In JSM proceedings, 2007, 140.
American Statistical Association, 2007.
Y. Zhang, M. Wainwright, and M. Jordan. Lower bounds on the performance
of polynomial-time algorithms for sparse linear regression. In COLT, pages
921–948, 2014.

49

