Debiasing the Debiased Lasso with Bootstrap
Sai Li∗

arXiv:1711.03613v1 [] 9 Nov 2017

Department of Statistics and Biostatistics, Rutgers University
November 13, 2017

Abstract
In this paper, we prove that under proper conditions, bootstrap can further debias the
debiased Lasso estimator for statistical inference of low-dimensional parameters in highdimensional linear regression. We prove that the required sample size for inference with
bootstrapped debiased Lasso, which involves the number of small coefficients, can be of smaller
order than the existing ones for the debiased Lasso. Therefore, our results reveal the benefits
of having strong signals. Our theory is supported by results of simulation experiments, which
compare coverage probabilities and lengths of confidence intervals with and without bootstrap,
with and without debiasing.

1

Introduction

High-dimensional linear regression is a highly active aera of research in statstics and machine
learning. When the dimension p of the model is larger than the sample size n, regularized least square
estimators are typically used when the signal is believed to be sparse. Properties of regularized least
square estimators in prediction, coefficient estimation and variable selection have been extensively
studied. However, regularized methods do not directly provide valid inference procedures, such as
confidence intervals and hypothesis testing.
Among the regularized regression procedures, the Lasso (Tibshirani, 1996) is one of the most
popular methods as it is computationally manageable and theoretically well-understood. However,
the limiting distribution of the Lasso estimator (Knight and Fu, 2000) depends on unknown
parameters in low-dimensional settings and is not available in high-dimensional settings. Chatterjee
and Lahiri (2010) showed the inconsistency of residual bootstrap for the Lasso if at least one true
coefficient is zero in fixed-dimensional settings. Thus, there is substantial difficulty in drawing valid
inference based on the Lasso estimates directly.

1.1

Debiased Lasso

In the p  n scenario, Zhang and Zhang (2014) proposed to construct confidence intervals for
regression coefficients and their low-dimensional linear combinations by “debiasing” regularized
estimators, such as the Lasso. Such estimators are known as the “debiased Lasso” or the “desparsified Lasso”.
∗

Email: sl1022@rutgers.edu

1

Along this line of research, many recent papers study computational algorithms and theories
for the debiased Lasso and its extensions beyond linear models. Van de Geer et al. (2014) proved
asymptotic efficiency of the debiased Lasso estimator in linear models and for convex loss functions.
Javanmard and Montanari (2014a) carefully studied a quadratic programming in Zhang and Zhang
(2014) to generate a direction for debiasing the Lasso and demonstrated its benefits. Jankova and
Van De Geer (2015) and Ren et al. (2015) proved asymptotic efficiency of the debiased Lasso in
estimating individual entries of a precision matrix. Mitra and Zhang (2016) proposed to debias a
scaled group Lasso for chi-squared-based statistical inference for large variable groups. Fang et al.
(2016) considered statistical inference with the debiased Lasso in high-dimensional Cox model.
Chernozhukov et al. (2017) studied debiased method in a semiparametric model with machine
learning approaches.
The sample size requirement for asymptotic normality in aforementioned papers is typically
n  (s log p)2 , where s is the number of nonzero regression coefficients. However, it is known that
point estimation consistency of the Lasso estimators holds with n  s log p. Therefore, it becomes
an intriguing question whether it is possible to conduct statistical inference of individual coefficients
in the regime s log p  n . (s log p)2 .
Very little work has been done in this direction. Cai and Guo (2017) proved that adaptivity
in s is infeasible for statistical inference with random design when n  (s log p)2 in a minimax
sense. However, for standard Gaussian design, Javanmard and Montanari (2014b) proved that the
debiased estimator is asymptotically Gaussian in an average sense if s = O(n/ log p) with s/p,
n/p constant, but they did not provide theoretical results when the covariance of the design is
unknown. Javanmard and Montanari (2015), denoted as [JM15], proved that asymptotic normality
√
for the debiased Lasso holds when s  n/(log p)2 , sj  n/ log p and min{s, sj }  n/ log p under
Gaussian design and other technical conditions, where sj is the number of nonzero elements in j-th
column of the precision matrix of the design. In this paper, we show that the sample size conditions
for the debiased Lasso can be improved by bootstrap if a significant proportion of signals are strong,
for both deterministic and random designs.

1.2

Bootstrap

Bootstrap has been widely studied in high-dimensional models for conducting inference. For the
debiased Lasso procedure, Zhang and Cheng (2017) proposed a Gaussian bootstrap method to
conduct simultaneous inference with non-Gaussian errors. Dezeure et al. (2016) proposed residual,
paired and wild multiplier bootstrap for the debiased Lasso estimators, which demonstrates the
benefits of bootstrap for heteroscedastic errors as well as simultaneous inference. However, the
aforementioned papers do not provide improvement on the sample size conditions.
For fixed number of covariates p, Chatterjee and Lahiri (2011) proposed to apply bootstrap to a
modified Lasso estimator as well as to the Adaptive Lasso estimator (Zou, 2006). In a closely related
paper, Chatterjee and Lahiri (2013) showed the consistency of bootstrap for Adaptive Lasso when
p increases with n under some conditions which guarantee sign consistency. They also proved the
second-order correctness for a studentized pivot with a bias-correction term. It is worth mentioning
that a beta-min condition is required in their theorems as sign consistency is used to prove bootstrap
consistency.
In this paper, we prove that the bias of the debiased Lasso estimator can be further removed by
bootstrap without assuming the beta-min condition. We provide a refined analysis to distinguish
the effects of small and large coefficients and show that bootstrap can remove the bias caused
by strong coefficients. Under deterministic designs, the sample size requirement is reduced to
n  max{s log p, (s̃ log p)2 }, where s̃ is the number of coefficients whose size is no larger than
2

p
C log p/n for some constant C > 0 (Theorem 3.4 in Section 3). One can see that the condition on
the overall sparsity s, s  n/ log p, provides the rate of point estimation. If a majority of signals are
strong, say s̃  s, our sample size condition is weaker than the usual n  (s log p)2 . Comparable
results are also proved for Gaussian designs, which involve the sparsity of the j-th column of the
precision matrix (Theorem 4.3 in Section 4).

1.3

Some other related literatures

In the realm of high-dimensional inference, many other topics have been studied. For bootstrap
theories, Mammen (1993) considered estimating the distribution of linear contrasts and of F-test
statistics when p increases with n. Chernozhukov et al. (2013) and Deng and Zhang (2017) developed
theories for multiplier bootstrap to approximate the maximum of a sum of high-dimensional random
vectors. Belloni et al. (2014) proposed to construct confidence regions for instrumental median
regression estimator and other Z-estimators based on Neyman’s orthogonalization, which is firstorder equivalent to the bias correction. Inference based on selected model has been considered in
many recent papers (Berk et al., 2013; Lockhart et al., 2014; Lee et al., 2016; Tibshirani et al.,
2016). Barber and Candes (2016) considered false discovery rate control via a knockoff filter in
high-dimensional setting.

1.4

Notations

For vectors u and v, let kukq denote the `q norm of u, kuk0 the number of nonzero entries of u,
hv, ui = uT v the inner product. For a set T , let |T | denote the cardinality of T and uT the subvector
of u with components in T . We use ej to refer to the j-th standard basis element, for example,
e1 = (1, 0, . . . , 0). For a matrix A ∈ Rk1 ×k2 , let kAkq denote the `q operator norm of A. Specially,
let kAk∞ = maxj≤k1 kAj,. k1 . Let Λmax (A) and Λmin (A) be the largest and smallest singular values
of A, AT1 ,T2 the submatrix of A consisting of rows in T1 and columns in T2 . For a vector b ∈ Rp ,
let sgn(b) be an element of the sub-differential of the `1 norm of b. Specifically, (sgn(b))j = bj /|bj |
if bj 6= 0 and (sgn(b))j ∈ [−1, 1] if bj = 0. We use an  bn to refer to |an /bn | → 0. The notation
an  bn is defined analogously. Let Φ(x) = P(Z ≤ x), where Z is a standard normal random
variable.
We use v0 , v1 , v2 , c1 , c2 , . . . to denote generic constants which may vary from one appearance to
the other.

1.5

Outline of the paper

The remainder of this paper is organized as follows. In Section 2, we describe the procedure under
consideration and layout the main ideas of the proof. In Section 3 and 4, we prove the bootstrap
consistency for the debiased Lasso and the asymptotic normality of a bias-corrected debiased Lasso
estimator under fixed designs and Gaussian designs, respectively. We illustrate our theoretical
results with simulation experiments in Section 5 and conclude with a discussion in Section 6. Proofs
of the main theorems and lemmas are provided in Section 7.

2

Main contents

In this section, we describe the procedure of bootstrapping the debiased Lasso under consideration
and the main ideas of this paper.

3

2.1

Bootstrapping the debiased Lasso

Consider a linear regression model
yi = xTi β + i ,
where β ∈ Rp is the true unknown parameter and 1 , . . . , n are i.i.d. random variables with mean 0
and variance σ 2 . We assume the true β is sparse in the sense that the number of nonzero entries of β
is relatively small compared with min{n, p}. For simplicity, we also assume that xj ’s are normalized,
s.t. kxj k22 = n, for j = 1, . . . , p.
The Lasso estimator (Tibshirani, 1996) is defined as
β̂ = arg min
b∈Rp

1
ky − Xbk22 + λkbk1 ,
2n

(1)

where λ > 0 is a tuning parameter.
Suppose that we are interested in making inference of a single coordinate βj , j = 1, . . . , p. The
debiased Lasso (Zhang and Zhang, 2014) corrects the Lasso estimator by a term calculated from
residuals. Specifically, it takes the form
(DB)

β̂j

= β̂j +

zjT (y − X β̂)
zjT xj

,

(2)

where zj is an estimate of the least favorable direction (Zhang, 2011). For the construction of zj , it
can be computed either as the residual of another `1 -penalized regression of xj on X−j (Zhang and
Zhang, 2014; Van de Geer et al., 2014) or by a quadratic optimization (Zhang and Zhang, 2014;
Javanmard and Montanari, 2014a). We adopt the first procedure in this paper. Formally,
zj = xj − X−j γ̂−j , with
1
γ̂−j = arg min
kxj − X−j γ−j k22 + λj kγ−j k1 , λj > 0.
γ−j ∈Rp−1 2n

(3)
(4)

While it is also possible to debias other regularized estimators of β, such as Dantzig selector (Candes
and Tao, 2007), SCAD (Fan and Li, 2001) and MCP (Zhang, 2010), we restrict our attention to
bootstrapping the debiased Lasso.
We consider Gaussian bootstrap although the noise i are not necessarily assumed to be normally
distributed. We generate the bootstrapped response vector as
yi∗ = xi β̂ + ˆ∗i , i = 1, . . . , n,

(5)

where xi are unchanged and ˆ∗i are i.i.d. standard Gaussian random variables multiplied by an
estimated standard deviation σ̂. Namely,
ˆ∗i = σ̂ξi , i = 1, . . . , n,

(6)

where ξi , are i.i.d standard normal. For the choice of variance estimator, we use
σ̂ 2 =

1
n − kβ̂k0

ky − X β̂k22

(7)

(Sun and Zhang, 2012; Reid et al., 2016; Zhang and Cheng, 2017; Dezeure et al., 2016). This is the
same proposal of bootstrapping the residuals as in Zhang and Cheng (2017). However, we do not
4

directly use ˆ∗i in (6) to simulate the distribution of the debiased estimator. Instead, we recompute
the debiased Lasso based on (X, y ∗ ) as follows:
(∗,DB)
β̂j

=

β̂j∗

+

zjT (y ∗ − X β̂ ∗ )
zjT xj

,

(8)

where zj is the same as the sample version in (3) and β̂ ∗ is the bootstrap version of the Lasso
estimator computed via (1) with (X, y ∗ ) instead of the original sample.
We construct the confidence interval for βj as


(DB)
(∗,DB)
(DB)
(∗,DB)
β̂j
− q1−α/2 (β̂j
− β̂j ), β̂j
− qα/2 (β̂j
− β̂j ) ,
(9)
where qc (u) is the c-quantile of the distribution of u.
We prove that under proper conditions, the approximation error of the debiased Lasso estimator
(DB)
β̂j
in (2) is dominated by a constant term. We propose to estimate this dominating constant
bias by the median of the bootstrapped approximation errors and construct a double debiased Lasso
(DDB) estimator


(DDB)
(DB)
(∗,DB)
β̂j
= β̂j
− median β̂j
− β̂j ,
(10)
which is asymptotically normal under proper conditions.

2.2

Main ideas

Our analysis is based on a different error decomposition for the debiased Lasso from the one originally
introduced. In Zhang and Zhang (2014), the error of the debiased Lasso is decomposed into two
terms, a noise term and a remainder term:
!
TX
z
zjT 
j
(DB)
β̂j
− βj =
(β̂ − β) .
(11)
− eTj − T
zjT xj
z j xj
| {z }
|
{z
}
Orig.noise

Orig.remainder

This is the starting point of many existing analysis of the debiased Lasso (Van de Geer et al., 2014;
Javanmard and Montanari, 2014a; Dezeure et al., 2016). Typically, the Orig.remainder term is
bounded by OP (sλλj ) through an `∞ -`1 splitting with λj in (4).
Our analysis is motivated by the following observations. Let S and Ŝ be the support of β and
β̂ respectively. It follows from the KKT condition of Lasso (1) that

β̂Ŝ = βŜ +

1 T
X X
n Ŝ Ŝ

−1 



−1
1 T
1 T
X  −λ
X X
sgn(β̂Ŝ ) and β̂Ŝ c = 0,
n Ŝ
n Ŝ Ŝ

assuming that XŜT XŜ /n is invertible. Our idea is to approximate β̂ by an oracle estimator β̂ o in
the analysis, where

−1 


−1
1 T
1 T
1 T
β̂So = βS +
XS XS
XS  − λ
XS XS
sgn(βS ) and β̂So c = 0,
(12)
n
n
n
when XST XS /n is invertible. This estimator β̂ o is oracle as it requires the knowledge of the true
support of β. However, it is different from the oracle least square estimator as the last term in β̂So
is added to mimic the Lasso estimator. In fact, β̂ o = β̂ when the Lasso estimator is sign consistent.
5

Inference based on the oracle estimator β̂ o (12) is relatively easy, because its approximation
error does not involve random support selection. In fact, its approximation error is linear in  with
an unknown intercept. Our idea is that when the difference between the oracle estimator β̂ o and
the Lasso estimator β̂ is small, the approximation error of the debiased Lasso in (11) is dominated
by a bias term associated with this intercept. Therefore, bootstrap can be used to remove this main
bias term. Specifically, we decompose the error of the debiased Lasso in (2) as
!
!
zjT 
zjT X
zjT X
(DB)
T
o
T
β̂j
− βj = T − ej − T
(β̂ − β) − ej − T
(β̂ − β̂ o )
zj x j
z j xj
zj x j
!S 

−1
zjT 
zjT X
XST 
1 T
= T − eTj − T
XS XS
n
n
zj xj
zj x j
|
{zS
}
N oise
! 
!
−1
TX
TX
z
z
1
j
j
+ λ eTj − T
X T XS
sgn(βS ) + eTj − T
(β̂ o − β̂) .
(13)
n S
zj x j
zj x j
S
{z
}
|
{z
} |
Remainder

Bias

Here the N oise term is the sum of the Orig.noise in (11) and a noise term associated with the
oracle estimator β̂ o in (12). The Bias term is from the intercept of the oracle estimator β̂ o in (12),
which is a constant of order OP (sλλj ) (Remark 3.1 in Section 3). The Remainder term arises from
the difference between the oracle estimator β̂ o and the Lasso estimator β̂ in (1). We prove that the
consistency of bootstrap when the Remainder is of order o(n−1/2 ), even if the Bias term is of larger
order than n−1/2 . The error decomposition in (13) will demonstrate benefits over the decomposition
in (11) when the Remainder term in (13) is of smaller order than the Orig.remainder term in (11).
One way to bound the Remainder term in (13) is by considering the event that the selected
support by Lasso is inside the true support and the an `∞ -bound exists for its estimation error:
n
o
Ω0 = Ŝ ⊆ S and kβ̂ − βk∞ ≤ Cn,p λ, Cn,p > 0 .
(14)
Recall that when the Lasso estimator β̂ is sign consistent, β̂ o = β̂ and Remainder in (13) is zero.
Let S̃ be a set of “small” coefficients, such that S̃ = {j : 0 < |βj | ≤ Cn,p λ}. In Ω0 , we can get
sgn(βj ) = sgn(β̂j ), for j ∈ S\S̃. And hence the sign inconsistency only occurs on S̃. Formally,
ksgn(β̂S ) − sgn(βS )k1 ≤ 2|S̃|.

(15)

We show that the Remainder term in (13) is associated with the order of |S̃|. This leads to the
improvement in sample size requirement when |S̃| is of smaller order than |S|.

3

Main results: deterministic design

In this section, we carry out detailed analysis for deterministic designs. We first provide sufficient
conditions for our theorems. For ease of notation, let Σn = X T X/n.
Condition 3.1. X is deterministic with
Λmin (ΣnS,S ) = Cmin > 0 and

6

max |Xi,j | ≤ K0 .

i≤n,j≤p

Condition 3.2.
ΣnS c ,S (ΣnS,S )−1

∞

≤ κ < 1.

Condition 3.3.
(ΣnS,S )−1

∞

≤ K1 < ∞.

Condition 3.4. i , i = 1, . . . , n, are i.i.d. random variables from a distribution with E[1 ] =
0, E[21 ] = σ 2 and E[|1 |4 ] ≤ M0 .
Condition 3.5. For any j ≤ p, kzj k44 = o(kzj k42 ) and kzj k22 /n ≥ K2 > 0.
As K1 is assumed to be a constant in Condition 3.3, the eigenvalue condition in Condition 3.1 is
redundant in the sense that Λmin (ΣnS,S ) ≥ 1/K1 . Note that the eigenvalue condition and Condition
3.3 are only required on a block of the Gram matrix consisting of rows and columns in the true
support. The quantity in Condition 3.2 is called incoherence parameter (Wainwright, 2009). This
condition is equivalent to the uniformity of the strong irrepresentable condition (Zhao and Yu, 2006)
over all sign vectors. Another related condition, the neighborhood stability condition (Meinshausen
and Bühlmann, 2006), has been studied for model selection in Gaussian graphical models. Condition
3.3 is required for establishing an `∞ -bound of estimation error of the Lasso estimator. Condition
3.4 involves only first four moments of  allowing some heavy-tailed distributions. Condition 3.5
contains some regularity conditions on zj , which are verifiable after the calculation of zj .

3.1

Preliminary lemmas

We first prove that event Ω0 in (14) holds true with large probability for deterministic designs.
Lemma 3.1. Suppose that Conditions 3.1 - 3.4 are satisfied and (n, p, s, λ) satisfies that
r
32σ 2
2 log p
16σ
n≥ 2
and λ >
.
2
λ (1 − κ)
1−κ
n
Then it holds that

(16)

r

2 log p
Ŝ ⊆ S and kβ̂S − βS k∞ ≤ K1 λ + 8σ
,
Cmin n
{z
}
|

(17)

g1 (λ)

with probability greater than 1 − 4 exp(−c1 log p) − c2 /n for some c1 , c2 > 0.
Lemma 3.1 is proved in Section 7.1. Lemma 3.1 asserts that the Lasso estimator does not have
false positive selection with large probability under Conditions 3.1 - 3.4. It is known that Condition
3.3 and beta-min condition together imply the selection consistency of the Lasso estimator. However,
we do not impose the beta-min
condition but distinguish the effects of small and large signals. Note
p
that g1 (λ)  λ for λ  log p/n.
Next we show that analogous results of Lemma 3.1 hold for the bootstrap version of the Lasso
estimator β̂ ∗ .
Lemma 3.2. Assume that Conditions 3.1 - 3.4 are satisfied. If (n, p, s, λ) satisfies (16), n  s log p
and
r
p
2 log p
4σ
≤ λ  log p/n,
(18)
1−κ
n
then with probability going to 1,
r
2 log p
∗
∗
Ŝ ⊆ S and kβ̂S − β̂S k∞ ≤ K1 λ + 2σ
.
(19)
Cmin n
|
{z
}
g10 (λ)

7

Lemma 3.2 is proved in Section 7.2. We mention that the condition n  s log p is required for
the consistency of σ̂ 2 (see Lemma A.4 for details). Note that it is Ŝ instead of S that is the true
support under the bootstrap resampling proposal and Ŝ ⊆ S with large probability by Lemma 3.1.
However, (19) is sufficient for the error of the bootstrapped debiased Lasso to approximate the error
decomposition in (13), which can be seen from the next Lemma.
In the following lemma, we consider the error decomposition in (13) and bound the Remainder
term for the debiased Lasso and its bootstrap analogue. Let N oise∗ be the bootstrap version of
N oise, which is
! 
−1 T ∗
zjT ˆ∗
zjT X
XS ˆ
1 T
∗
T
N oise = T − ej − T
XS XS
.
(20)
n
n
zj x j
zj xj
S

Let s̃ be the number of small coefficients, such that

s̃ = j : 0 < |βj | < g1 (λ) + g10 (λ)

,

(21)

for g1 (λ) and g10 (λ) defined in (17) and (19) respectively.
Lemma 3.3 (Bounding the remainder terms). Suppose that Conditions 3.1 - 3.4 hold true, λ 
p
(DB)
(∗,DB)
log p/n satisfies (16) and (18) and n  s log p. For β̂j
and β̂j
defined in (2) and (8)
respectively, we have
!
s̃λλj
(DB)
= o(1),
(22)
P β̂j
− βj − N oise − Bias > 2K1 T
zj xj /n
!
s̃λλ
j
(∗,DB)
P β̂j
− β̂j − N oise∗ − Bias > 2K1 T
= o(1),
(23)
zj xj /n
where N oise and Bias are defined in (13), N oise∗ is defined in (20) and s̃ is defined in (21).
Lemma 3.3 is proved in Section 7.3. The factor zjT xj /n is calculable and can be treated as a
positive constant typically. In fact, this factor is proportional to the standard deviation of N oise
and N oise∗ , so that it will be cancelled in the analysis of the asymptotic normality. Therefore, we
have proved that the Remainder term in (13) is of order OP (s̃λλj ).
p
Remark 3.1. Under Conditions 3.1 - 3.4 and λ  λj  log p/n, we can get a natural upper
bound on Bias in (13):
!


sλλj
s log p
Bias = OP
= OP
= oP (1).
n
(zjT xj /n)Cmin
Note that the order of Bias is not guaranteed to be o(n−1/2 ) under the sample size conditions of
Lemma 3.3. There will be no guarantee of improvement on the sample size requirement if we do not
remove the Bias term.

3.2

Consistency of bootstrap approximation

Inference for βj is based on the following pivotal statistics
Rj =

zjT xj (DB)
zjT xj (∗,DB)
(β̂j
− βj ) and Rj∗ =
(β̂
− β̂j ),
kzj k2
kzj k2 j
8

(24)

where β̂ (DB) and β̂ (∗,DB) are defined in (2) and (8) respectively. We show the consistency of
bootstrap approximation of Rj∗ to Rj as well as the asymptotic normality of a pivot based on the
(DDB)

in (10):

(DDB)

=

double debiased Lasso estimator β̂j

Rj

zjT xj
(DDB)
(β̂j
− βj ).
σ̂kzj k2

(25)

We specify the sample size conditions as following:
n
p
A1 = (n, p, s, s̃, λ, λj ) : (n, p, s, λ) satisfies (16) and (18), λ  λj  log p/n and
o
n  max{s log p, (s̃ log p)2 } for s̃ in (21) .

(26)

As discussed in Section 1, the condition on the overall sparsity recovers the rate of point estimation.
If s̃  s, our sample size condition is weaker than the typical one n  (s log p)2 .
Theorem 3.4. Assume that Conditions 3.1 - 3.5 hold true and (n, p, s, s̃, λ, λj ) ∈ A1 . Then for Rj
and Rj∗ defined in (24), it holds that
sup

P{Rj ≤ qα (Rj∗ )} − α = oP (1),

α∈(0,1)
(DDB)

where qα (Rj∗ ) is the α-quantile of the distribution of Rj∗ . For Rj
sup
α∈(0,1)

(DDB)

P(Rj

defined in (25),

≤ zα ) − α = oP (1).

Theorem 3.4 is proved in Section 7.4. Based on Theorem 3.4, a two-sided 100 × (1 − α)%
confidence interval for βj can be constructed as in (9).
For the double debiased estimator (10), the Biasin (48) is estimated
by the median of the

(∗,DB)
(∗,DB)
distribution of β̂j
− β̂j . In practice, the median β̂j
− β̂j can be approximated by the
sample median of bootstrap realizations.
Remark 3.2. Suppose we are interested in making inference for a linear combination of regression
coefficients ha0 , βi for a0 ∈ Rp . It is not hard to see that Gaussian bootstrap remains consistent
under the conditions of Theorem 3.4 if ka0 k1 /ka0 k2 is bounded.

4

Main results: Gaussian designs

This section includes main results in the case of Gaussian design. The proof follows similar steps
as for deterministic designs. We first describe conditions we impose in our theorems.
Condition 4.1. X has independent Gaussian rows with mean 0 and covariance Σ.
Condition 4.2.
ΣS c ,S Σ−1
S,S
Condition 4.3.

−1/2 2

ΣS,S

∞

∞

≤ κ < 1.

≤ K1 < ∞.

9

Condition 4.4.
Λmin (ΣS,S ) ≥ Cmin , 1/ max(Σ−1 )j,j ≥ C∗ and max Σj,j ≤ C ∗ < ∞.
j≤p

j≤p

Condition 4.5. i , i = 1, . . . , n, are i.i.d from Gaussian distribution with mean 0 and variance σ 2 .
Condition 4.2 - Condition 4.3 are population versions of Condition 3.2 - Condition 3.3. In
Condition 4.4, we require that the largest diagonal element of Σ−1 is upper bounded, in order to
lower bound kzj k22 /n asymptotically. It is also worth mentioning that Condition 4.3 is related to
condition (iii) in [JM15]. Specifically, [JM15] required that
ρ(Σ, C0 s0 ) =

max

T ⊆[p],|T |≤C0 s

Σ−1
T,T

∞

< ρ, for C0 ≥ 33.

This condition is on a set T , which is actually the support of the estimation error of a perturbed
Lasso estimator, while Condition 4.3 is assumed on the true support S.

4.1

Preliminary lemmas

Lemma 4.1. Assume that Conditions 4.1 - 4.5 are satisfied and (n, p, s, λ) satisfies that
r
σ 2 Cmin
8σ
C ∗ log p
2
sλ ≤
and λ ≥
.
2
1−κ
n
Then for
r
g2 (λ) = (1 + Cn )K1 λ + 4σ

log p
with Cn = O
Cmin n



s∨

√

s log p
√
,
n

(27)

(28)

it holds that
Ŝ ⊆ S and kβ̂S − βS k∞ ≤ g2 (λ),

(29)

with probability greater than 1 − c1 /n − 2 exp(−c2 log p) − 2 exp(−c3 n) for some c1 , c2 , c3 > 0.
Lemma 4.1 is proved in Section 7.5. Note that g2 (λ) = o(1) if n  s log p. If s2 ∨ s log p = O(n),
then g2 (λ) = O(λ), which is the same as deterministic design case. Theorem 3 in Wainwright (2009)
considers the same scenario, but their results require s → ∞ and their upper bound on kβ̂ − βk∞
only holds for sign consistency case.
In the next Lemma, we prove a bootstrap analogue of Lemma 4.1.
Lemma 4.2. Assume that Conditions 4.1 - 4.5 hold true. If (n, p, s, λ) satisfies (27), n  s log p
and
r
r
4σ
log p
log p
≤λ
,
(30)
1−κ
n
n
then with probability going to 1,
Ŝ ∗ ⊆ S and kβ̂S∗ − β̂S k∞ ≤ g2 (λ), for g2 (λ) in (28).

(31)

Lemma 4.2 in proved in Section 7.6. Same as the deterministic design case, the condition
n  s log p is required for the consistency of σ̂ 2 .

10

4.2

Consistency of bootstrap approximation

Under Conditions 4.1 - 4.5, we prove the consistency of Gaussian bootstrap under Gaussian designs.
For g2 (λ) defined in (28), define
s̃ = |{j : 0 < |βj | < 2g2 (λ)}| .
We specify the required sample size condition as following:
n
p
A2 = (n, p, s, s̃, sj , λ, λj ) : (n, p, s, λ) satisfies (27) and (30), λ  λj  log p/n and
o
n  max{ss̃ log p, (s̃ log p)2 , sj log p} for s̃ in (32) .

(32)

(33)

Theorem 4.3. Suppose that Conditions 4.1 - 4.5 are satisfied and (n, p, s, s̃, sj , λ, λj ) ∈ A2 . Then
it holds that
sup P{Rj ≤ qα (Rj∗ )} − α = oP (1).
α∈(0,1)
(DDB)

For Rj

defined in (25),
sup
α∈(0,1)

(DDB)

P(Rj

≤ zα ) − α = oP (1).

It can be seen from the proof (Section 7.7) that condition n  ss̃ log p in (33) is used to achieve
desired rates for |Remainder| and its bootstrap analogue, such that k(ΣnS,S )−1 k∞ s̃λ2 = oP (n−1/2 ).
The condition n  sj log p is required to prove that kzj k22 /n is asymptotically bounded away from
zero.
√
In terms of the sparsity requirements, A2 (33) implies that it is sufficient to require s = O( n)
√
√
and s̃ = o( n/ log p). Compared to the typical condition, s = o( n/ log p), our condition allows at
least an extra order of log p. Moreover, if s̃ is constant, our requirement on s is s  n/ log p, which
recovers the rate of point estimation. Comparing with the sparsity condition assumed in [JM15] for
unknown Gaussian design case, our analysis still benefits when s̃ is sufficiently small:
• If the sparsity of the j-th column of precision matrix is much larger than the sparsity of β, i.e.
s̃ ≤ s  sj , [JM15] required n  max{(s log p)2 , sj log p}, which is no better than the rate in
A2 (33) as discussed above. If s̃  s, A2 is weaker than the sparsity conditions assumed in
[JM15].
• If the j-th column of the precision matrix is much sparser, i.e. s  sj , [JM15] required
that n  max{s(log p)2 , (sj log p)2 }. If s̃  log p, then ss̃ log p  s(log p)2 and hence the
sample size condition in A2 is weaker. If s̃  log p, [JM15] required weaker condition on s
but stronger condition on sj .

5

Simulations

In this section, we report the performance of the debiased Lasso with Gaussian bootstrap and other
comparable methods in simulation experiments.
Consider deterministic design case with n = 100, p = 500, Xi ∼ N (0, Ip ) and i ∼ N (0, 1). We
consider a relatively large sparsity level, s = 20, and two levels of true regression coefficients as
following.
11

(i) All the signals are strong: β1 = · · · = β20 = 2.
(ii) A large proportion of signals are strong: β1 = · · · = β5 = 1, β6 = · · · = β20 = 2.
We compare the performance of bootstrapping the debiased Lasso (BS-DB), the debiased Lasso
without bootstrap (DB) and the Adaptive Lasso with residual bootstrap (BS-ADP). For BS-DB,
we generate (1 − α)% confidence interval (CI) according to (9) with 500 bootstrap resamples. We
take λ = λj at the universal level for the Lasso procedures. For DB, we estimate the noise level by
(7) and take λ = λj at the universal level for the Lasso procedures. (1 − α)% confidence intervals
are generated according to
!
kzj k2
kzj k2
(DB)
(DB)
β̂j
+ σ̂zα/2 T , β̂j
+ σ̂z1−α/2 T
.
zj x j
zj xj
For BS-ADP, we consider the pivot defined in (4.2) of Chatterjee and Lahiri (2013), which can
achieve second-order correctness under some conditions. Such estimators also have a bias-correction
term, which can be explicitly calculated assuming sign consistency. The choices of λ1,n and λ2,n are
according to Section 6 of Chatterjee and Lahiri (2013). Each confidence interval is generated with
500 bootstrap resamples.
We construct two-sided 95% confidence intervals using each of the aforementioned methods.
Each setting is replicated with 1000 independent realizations. In the following table, we report
the average coverage probability on S and S c (cov
c S and cov
c S c , respectively) as well as the average
length of CIs on S and S c (`S and `S c , respectively) for identity covariance matrix and equicorrelated
covariance matrix with Σj,j = 1 and Σj,k = 0.2 (j 6= k).
β
(i)

(ii)

Methods
BS-DB
DB
BS-ADP
BS-DB
DB
BS-ADP

cov
cS
0.997
0.940
0.274
0.974
0.939
0.279

Σj,k = 0
cov
c Sc
0.999
0.982
0.950
0.998
0.982
0.951

(j =
6 k)
`S
1.127
0.886
0.181
1.057
0.887
0.195

`S c
0.539
0.885
0.201
0.554
0.886
0.187

cov
cS
0.893
0.627
0.241
0.820
0.649
0.280

Σj,k = 0.2 (j 6= k)
cov
c Sc
`S
`S c
0.997 1.074 0.436
0.934 0.760 0.778
0.945 0.432 0.319
0.987 0.963 0.424
0.925 0.716 0.733
0.943 0.638 0.280

One can see that BS-DB always gives larger coverage probabilities than DB across different
settings. We mention that noise level is overestimated (see (7)). For example, in setting (i) and
(ii) with the identity covariance matrix, the average of σ̂ is 2.240 and 2.244, respectively. The CIs
given by BS-DB are longer than those computed with DB on S, but on S c the CIs given by BS-DB
are shorter than the ones given by DB. On the other hand, BS-ADP exhibits the overconfidence
phenomenon: the average lengths of CIs are small, which results in low coverage probabilities on
S. In the presence of equicorrelation, which is a harder case, BS-DB is significantly better than DB
and BS-ADP in terms of coverage probability.

12

●

1.5

1.6

●

●
●
●
●

●
●

1.25

●

●

●
●

●

1.00

Centers of CIs

●

1.0

●

1.2

●
●

●

●
●

●

0.75
●
●

0.8

0.5

●
●
●
●

●
●
●
●

0.50

●
●
●

●
●
●
●
●
●

●
●

0.4

●
●
●
●

0.0
DB

DDB

Las

DB

●

DDB

0.25

●
●
●
●
●

Las

DB

●
●

2.5

●
●
●
●

DDB

Las

●
●

●

●

2.4

●
●
●

●

Centers of CIs

●
●
●
●

2.0

2.0

●
●
●

2.0

●
●
●

●

●
●
●
●
●

●
●

●
●
●

●
●

1.5

●

●

●
●
●
●

1.6

1.5

●
●
●
●
●
●

●
●
●

●

DB

DDB

●
●
●
●
●
●

1.0

●
●
●
●
●
●

●

DB

DDB

Las

DB

DDB

●

0.2

●
●
●
●

0.4

●
●
●

Las

Las

●
●
●
●

●

●
●
●
●
●

●
●
●
●
●

●

0.0

●
●
●
●

0.0

Centers of CIs

●

0.2

●
●
●

●
●
●
●
●

●

●

−0.2

0.0

−0.2

●

●
●

●

●

●
●
●
●
●
●
●
●

−0.2

●
●

DB

DDB

●

−0.4

−0.4

●
●

●

Las

DB

DDB

Las

DB

DDB

Las

Figure 1: Boxplots of the double debiased Lasso (DDB) (10), the debiased Lasso (DB) (2) and the
Lasso (Las) (1) with the identity covariance matrix in setting (ii). First row consists of estimates
for weak signals: β1 = β2 = β3 = 1. Second row consists of estimates for strong signals: β6 = β7 =
β8 = 2. Third row consists of estimates for zeros: β21 = β22 = β23 = 0. Each Boxplot is based on
1000 independent replications.
Figure 1 demonstrates the bias-correction effects of debiasing and bootstrap across different
levels of signal strengths. Concerning the overall performance, DDB is better than DB in terms of
bias-correction, which is in line with our theoretical results. For j ∈ S, DDB and DB are less biased
than the Lasso estimators. On S c , the Lasso estimates the regression coefficients as zero with a
large probability. Thus, the Boxplot degenerates to a point at zero with a few outliers. Comparing
row-wise, one can see that bootstrap has more significant correction effects on strong signals (second
row) than on weak signals (first row). When true coefficients are zeros, DDB is also less biased than
DB.

13

6

Discussions

We consider the bias-correction effect of bootstrap for statistical inference with debiased Lasso under
proper conditions. Our analysis on the approximation error of debiased Lasso admits sample size
conditions in terms of the number of weak signals. Our results contribute to the inference problem
in the regime s log p  n . (s log p)2 , but also demonstrate the benefits of having strong signals for
the debiased Lasso procedure. We establish the consistency of Gaussian bootstrap and show that
confidence intervals can be constructed based on bootstrap samples.
Besides Gaussian bootstrap, we also considered residual bootstrap, which is robust in the
presence of heteroscedastic errors. However, the proof involves a more technical analysis and may
impair the sample size conditions. To focus on the main idea, this is omitted from the paper. We
also considered the proof techniques in [JM15], which construct a perturbed version of the Lasso
estimator assuming βj is known and utilize its independence of xj . However, these techniques
cannot be directly applied to the bootstrapped debiased Lasso, since the “true” parameters β̂ and
σ̂ under the bootstrap resampling plan are not independent with xj for j ∈ S.

7

Proofs of main lemmas and theorems

To simplify our notations in this section, let ûS = β̂S − βS , û∗S = β̂S∗ − β̂S , WSn = XST /n, WS∗ =
XST ˆ∗ /n and S\j = S\{j}.

7.1

Proof of Lemma 3.1

Proof. Firstly, we use Lemma 1 - Lemma 3 in Wainwright (2009) to prove that (17) holds with large
probablity. Consider a restricted Lasso problem
β̌S = arg min
b∈Rs

1
ky − XS bS k22 + λkbS k1 and β̌S c = 0.
2n

(34)



PS⊥ 
T
−1
XS (XS XS ) sgn(β̌S ) +
.
nλ

(35)

Define Tj as
Tj =

xTj

By Lemma 1 of Wainwright (2009), if ΣnS,S is invertible and |Tj | < 1 for ∀j ∈ S c , then the β̌ is the
unique solution to the Lasso with Ŝ ⊆ S. Note that
maxc |Tj | ≤ kXSTc XS (XST XS )−1 sgn(β̌S )k∞ + maxc
j∈S

j∈S

≤

XSTc XS (XST XS )−1 ∞

xTj PS⊥ 
nλ

xTj PS⊥ 
+ maxc
.
j∈S
nλ
|
{z
}
Q1

We use standard symmetrization techniques to prove that Q1 ≤ (1 − κ)/2 with large probability
(see Lemma A.1 for detailed results). By Condition 3.2 and (76) in Lemma A.1, there exists some
c1 , c2 > 0 such that




κ+1
1−κ
c2
P maxc |Tj | >
≤ P Q1 >
≤ 4 exp (−c1 log p) + ,
j∈S
2
2
n
14

for λ in (16). Together with Condition 3.1, we have Ŝ ⊆ S with probability greater than
4 exp (−c1 log p) + c2 /n. By the KKT condition of the Lasso (1), Ŝ ⊆ S implies that
ûS = (ΣnS,S )−1 WSn − λ(ΣnS,S )−1 sgn(β̂S ).

(36)

Then we have
kûS k∞ = k(ΣnS,S )−1 WSn − λ(ΣnS,S )−1 sgn(β̂S )k∞
≤ k(ΣnS,S )−1 WSn k∞ +λk(ΣnS,S )−1 k∞ .
|
{z
}
Q2

By (77) in Lemma A.1 and Condition 3.3, there exists some c3 , c4 > 0 such that
!
r
2 log p
c4
≤ 4 exp(−c3 log p) + .
P kûS k∞ > K1 λ + 8σ
Cmin n
n

7.2

Proof of Lemma 3.2

Proof. Formally, the bootstrapped Lasso estimator β̂ ∗ is defined via
β̂ ∗ = arg min
b∈Rp

1 ∗
ky − Xbk22 + λkbk1 .
2n

(37)

Define a restricted Lasso problem with observations (XS , y ∗ ):
β̌S∗ = arg min
b∈Rs

1 ∗
ky − XS bS k22 + λkbS k1 and β̌S∗ c = 0.
2n

(38)

Define Tj∗ as
Tj∗

xTj



XS (XST XS )−1 sgn(β̌S∗ )

P ⊥ ˆ∗
+ S
nλ


.

(39)



P(Ŝ ∗ ⊆ S) ≥ P maxc |Tj∗ | < 1, Ŝ ⊆ S
j∈S


∗
= P maxc |Tj | < 1 − P(Ŝ 6⊆ S).

(40)

=

By Condition 3.1 and Lemma A.2,

j∈S

Note that
maxc |Tj∗ | ≤ maxc xTj XS (XST XS )−1 sgn(β̌S∗ )
j∈S

j∈S

+ maxc
1
j∈S

xTj PS⊥ ˆ∗
.
nλ
| {z }
Q∗1,j

By construction (5), Q∗1,j is a Gaussian variable with mean zero and variance no larger than
σ̂ 2 /(nλ2 ), ∀j ∈ S c , conditioning on σ̂ 2 . Thus,




1−κ
1−κ 2
∗
∗
2
P maxc |Q1,j | ≥
≤ P maxc |Q1,j | ≥
|σ̂ ≤ 2σ + P(σ̂ 2 ≥ 2σ 2 )
j∈S
j∈S
2
2


nλ2 (1 − κ)2
≤ 2(p − s) exp −
+ o(1),
16σ 2
15

where the last step is due to the consistency of σ̂ 2 in (7) (see
q Lemma A.4). Condition 3.2 implies
2 log p
4σ
that maxj∈S c kxTj XS (XST XS )−1 sgn(β̌S∗ )k1 ≤ κ. For λ > 1−κ
and some c1 > 0, we have
n


1+κ
∗
< 1 ≥ 1 − 2 exp(−c1 log p) − o(1).
P |Tj | ≤
2
By Lemma 3.1 and (40), P(Ŝ ⊆ S) → 1 and hence
P (Ŝ ∗ ⊆ S) ≥ 1 − 2 exp(−c1 log p) − o(1).
By the KKT condition of the bootstrapped Lasso (37), in the event that {Ŝ ∗ ⊆ S},
û∗S = (ΣnS,S )−1 WS∗ − λ(ΣnS,S )−1 sgn(β̂S∗ ).

(41)

Therefore,
kû∗S k∞ ≤ k(ΣnS,S )−1 WS∗ k∞ + kλ(ΣnS,S )−1 sgn(β̂S∗ )k∞
≤ k(ΣnS,S )−1 WS∗ k∞ + λK1 .

(42)

Again using the Gaussian property of ˆ∗ , there exists some c2 > 0 such that
!
r
log
p
2σ
P k(ΣnS,S )−1 WS∗ k∞ ≥ √
n
Cmin
!
r
2σ
log
p
≤ P k(ΣnS,S )−1 WS∗ k∞ ≥ √
σ̂ 2 ≤ 2σ 2 , Ŝ ∗ ⊆ S + P(σ̂ 2 > 2σ 2 ) + P(Ŝ ∗ 6⊆ S)
n
Cmin
≤ 2 exp(−c2 log p) + o(1).
Together with (42), the proof is completed.

7.3

Proof of Lemma 3.3

Proof. The KKT condition of (4) is
1 T
z X−j
n j

as

≤ λj .

(43)

∞

In the event that (17) holds true, (36) holds true and hence we can rewrite Remainder in (13)
!
zjT X
T
Remainder = λ ej − T
(ΣnS,S )−1 [sgn(β̂S ) − sgn(βS )].
(44)
zj x j
S

Let S̃ be the set of small coefficients, such that S̃ = {j : 0 < |βj | < g1 (λ) + g10 (λ)} for g1 (λ) and
g10 (λ) in (17) and (19) respectively. kûS k∞ ≤ g1 (λ) further implies that for ∀j ∈ S\S̃,
β̂j = βj + ûj > βj − max |ûj | > βj − g1 (λ) > g10 (λ), for βj > g1 (λ) + g10 (λ).
j

β̂j = βj + ûj < βj + max |ûj | < βj + g1 (λ) < −g10 (λ), for βj < −[g1 (λ) + g10 (λ)].
j

16

Therefore, if (17) holds true, then
sgn(βj ) = sgn(β̂j ) and |β̂j | > g 0 (λ) for j ∈ S\S̃.

(45)

The sign inconsistency of the Lasso estimator β̂ only occurs on S̃ and hence
sgn(β̂S ) − sgn(βS )

1

≤ 2s̃.

(46)

By (44), we have
|Remainder| ≤ λ

≤λ
≤

eTj −

zjT XS

(ΣnS,S )−1

zjT xj

zjT XS\j
zjT xj

!
S

sgn(β̂S ) − sgn(βS )
∞

(ΣnS,S )−1

∞

sgn(β̂S ) − sgn(βS )

∞

1

1

2K1 λλj s̃
,
zjT xj /n

where the last step is due to Condition 3.3, (43) and (46). The proof for (22) is completed by the
fact that (17) holds with probability going to 1.
For the bootstrap version, define an oracle Lasso estimator computed with the bootstrap samples.
Formally,
−1
(∗,o)
(∗,o)
β̂S = β̂S + ΣnS,S
(WS∗ − λsgn(βS )) and β̂S c = 0.
(47)
(∗,o)

If Ŝ ⊆ S and Ŝ ∗ ⊆ S, we can plug in β̂S
(∗,DB)

β̂j

− β̂j =
=

zjT ˆ∗
zjT xj
zjT ˆ∗

+

eTj −

zjT X
zjT xj
zjT X

and obtain that

!
(∗,o)

(β̂S

− β̂S ) +

eTj −

!S

zjT X

!

zjT xj

(∗,o)

(β̂S∗ − β̂S

)

S

(ΣnS,S )−1 WS∗ + Bias
zjT xj
{z S
}
N oise∗
!


zjT X
T
+ λ ej − T
(ΣnS,S )−1 sgn(β̂S∗ ) − sgn(βS ) ,
zj x j
S
|
{z
}

zjT xj
|

−

eTj −

(48)

Remainder∗

where N oise∗ is in (20) and Bias is in (13).
In view of (19) and (45) , we have sgn(β̂j∗ ) = sgn(β̂j ) = sgn(βj ) for j ∈ S\S̃. Hence,
ksgn(β̂S∗ ) − sgn(βS )k1 ≤ 2s̃.
Together with (43) and Condition 3.3, it holds that
|Remainder∗ | ≤

2K1 s̃λλj
= oP (1),
zjT xj /n

in the event that {Ŝ ⊆ S, Ŝ ∗ ⊆ S}, which holds with large probability by Lemma 3.1 and 3.2.

17

(49)

7.4

Proof of Theorem 3.4

We simplify the notations for the terms in (13) and (48). Let
bj = Bias in (13), Remj = Remainder in (13), ηj = N oise in (13),
Rem∗j = Remainder∗ in (48), ηj∗ = N oise∗ in (20).

(50)

Proof. Define a version of pivots in (24) which is standardized and bias-removed:
Rjo =

zjT xj
zjT xj
(DB)
(∗,o)
(∗,DB)
(β̂j
− βj − bj ) and Rj
=
(β̂j
− β̂j − bj ).
σkzj k2
σkzj k2
(∗,o)

We first find the limiting distribution for Rjo and Rj
Let ζj be the normalized version of ηj in (50):
ζj =

(51)

.

n
X
zjT xj
ηj =
ζi,j ,
σkzj k2

(52)

i=1




T  /n .
where ζi,j = σkz1j k2 zi,j i − (zjT xj eTj − zjT XS )(ΣnS,S )−1 Xi,S
i
Statement (22) in Lemma 3.3 implies that


√

zjT xj
nK1 s̃λλj
nK1 s̃λλj
Rjo = OP
+
ηj = OP
+ ζj = oP (1) + ζj ,
σkzj k2
σkzj k2
σK2

(53)

where the second step is due to Condition 3.5 and the last step is by our sample size condition.
Note that ζj is a random variable with mean zero and variance s2n , where
s2n = V ar(ζj )
1
=
kzj − (zjT xj eTj − zjT X)S (ΣnS,S )−1 XST /nk22
kzj k22
1
2
=1+
(z T xj eTj − zjT X)S (ΣnS,S )−1 (zjT xj ej − X T zj )S −
z T XS (ΣnS,S )−1 (zjT xj ej − X T zj )S
nkzj k22 j
nkzj k22 j
3
2
=1+
(zjT xj eTj − zjT X)S (ΣnS,S )−1 (zjT xj ej − X T zj )S −
z T xj eTj (ΣnS,S )−1 (zjT xj ej − X T zj )S .
2
nkzj k2
nkzj k22 j
|
{z
} |
{z
}
H1

H2

(54)
Note that H1 in (54) can be bounded by

|H1 | ≤
≤

3 (zjT xj eTj − zjT X)S /n

2
2

(ΣnS,S )−1

2

kzj k22 /n

3skzjT XS\j /nk2∞
K2 Cmin

≤

3sλ2j
,
K2 Cmin

(55)

where the second last step is by Conditions 3.1 and 3.5 and the last step is by (43). Similarly, H2
in (54) can be bounded by
√
sλj
2
T
n
−1
T
|H2 | ≤
zj XS\j /n
(ΣS,S )
xj zj ≤ √
.
(56)
2
2
2
kzj k2
K2 Cmin
18

Thus, for n  s log p, we have
s2n = 1 + o(1).

(57)

Now we check the Lyapunov condition, which is
n
1 X
E[|ζi,j |4 ] = 0.
lim
n→∞ s4
n
i=1

Using Condition 3.4, we can obtain that
n
X

E[ζi,j |4 ] ≤

i=1

n
E[||4 ] X
T
|zi,j − (zjT xj eTj − zjT X)S (ΣnS,S )−1 Xi,S
/n|4
σ 4 kzj k42 i=1

M0
≤ 4
23
σ kzj k42

n
X

4

|zi,j | +

i=1

n
X

!
|(zjT xj eTj

−

T
zjT X)S (ΣnS,S )−1 Xi,S
/n|4

.

(58)

i=1

T /n, i = 1, . . . , n. Then we have
For ease of notation, let ci = (zjT xj eTj − zjT X)S (ΣnS,S )−1 Xi,S

kck22

nsλ2j
kzj k22
H1 ≤
,
=
3
Cmin

max |ci | ≤ s zjT XS\j /n

∞

i∈[n]

(ΣnS,S )−1

max |xi,j | ≤ K1 K0 sλj .

∞ i,j

As a consequence,
n
X

4

|ci | ≤ max |ci |

2

i∈[n]

i=1

n
X
i=1

nK12 K02 s3 λ4j
nsλ2j
=
.
|ci | ≤ (K1 K0 sλj )
Cmin
Cmin
2

2

In view of (58), it holds that
n
M0 23 (nK12 K02 s3 λ4j /Cmin + kzj k44 )
1 X
4
E[ζ
|
]
≤
lim
i,j
n→∞ s4
n→∞
σ 4 kzj k42 (1 − o(1))2
n

lim

i=1

≤ lim

M0 23 K12 K02 s3 λ4j

= 0,
σ 4 K22 Cmin n
q
as long as s3 λ4  n. For s  n/ log p and λj  logn p , it is easy to check that s3 λ4 = O(n/ log p) 
n.
We have proved that
D
ζj /sn −
→ Z, for Z ∼ N (0, 1).
n→∞

Together with (53) and (57), we have
sup P(Rjo ≤ c) − Φ(c) = oP (1).

(59)

c∈R

(∗,o)

For the bootstrap version, consider Rj

defined in (51). By Lemma A.4 and (23) in Lemma

3.3,
(∗,o)
Rj


= OP

nK1 s̃λλj
σkzj k2



zjT xj
+
ηj + oP (1) = OP
σkzj k2
19

√

nK1 s̃λλj
σK2



+ ζj∗ + oP (1) = oP (1) + ζj∗ ,

where
ζj∗ =

zjT xj ∗
η
σkzj k2 j

(60)

is a Gaussian variable with mean zero and variance 1 + oP (1). This implies that
sup P(ζj∗ ≤ c) − Φ(c) = oP (1).

(61)

c∈R

Let F∗ (c) be the cumulative distribution function of ζj∗ , i.e. F∗ (c) = P(ζj∗ ≤ c). For ∀v1 , v2 > 0 and
∀α ∈ (0, 1),


n  

o
(∗,o)
(∗,o)
P qα (Rj ) − zα > v1 ≤ P F∗ qα Rj
> F∗ (zα + v1 )
≤ P {α > F∗ (zα + v1 )}
≤ P {α + v2 > Φ(zα + v1 )} + P {F∗ (zα + v1 ) ≤ Φ(zα + v1 ) − v2 } + o(1)
= P {α + v2 > Φ(zα + v1 )} + o(1),
where the first step is due to the monotonicity of F∗ , the second step is by the definition of quantile
function, and the last step is due to (61). By first taking v2 → 0, we have proved that for ∀α ∈ (0, 1)
and ∀v1 > 0,
n 

o
(∗,o)
P qα Rj
− zα > v1 = o(1).
A matching lower bound can be proved by a completely analogous argument. Thus,


(∗,o)
sup qα Rj
− zα = oP (1).

(62)

α∈(0,1)

To complete our proof, note that by Lemma A.4,
Rj =

σRjo

zjT xj
zjT xj
(∗,o)
∗
+
bj + oP (1) and Rj = σRj
+
bj + oP (1).
kzj k2
kzj k2

Together with (59) and (62), it holds that

sup P Rj ≤ qα (Rj∗ ) − α ≤ sup
α∈(0,1)

α∈(0,1)

≤ sup

(63)

n

o
(∗,o)
P Rjo ≤ qα Rj
−α
P{Rjo ≤ zα } − α + oP (1)

α∈(0,1)

= oP (1).
(DDB)

Next, we prove the asymptotic normality of Rj
(∗,DB)
β̂j

(DDB)

in (25). Note that β̂j

in (10) corrects

with an estimated bias


(∗,DB)
b̂j = median β̂j
− β̂j .

Due to (48), we can easily obtain that


zjT xj
zjT xj
(∗,o)
b̂j =
bj + median Rj
+ oP (1)
σkzj k2
σkzj k2
zjT xj
=
bj + z0.5 + oP (1)
σkzj k2
=

zjT xj
bj + oP (1),
σkzj k2
20

(64)

(DDB)

where the second step is due to (62). By definition of β̂j

(10) and Rj defined in (24),

zjT xj
zjT xj
1
(DDB)
(β̂j
− βj ) = Rj −
b̂j = Rjo + oP (1) = Z + oP (1),
σkzj k2
σ
σkzj k2

(65)

(DDB)

where the last step is due to (59) for Z ∼ N (0, 1). For Rj
defined in (25), (65) and Lemma
A.4 implies that


(DDB)
P Rj
≤ c = P(Z ≤ c) + oP (1) = Φ(c) + oP (1).

7.5

Proof of Lemma 4.1

Proof. (i) Let
c
toj = xj − XS Σ−1
S,S ΣS,j , for j ∈ S .

(66)

For β̌S and Tj defined in (34) and (35) respectively, we can rewrite Tj as
Tj =

(toj )T



XS (XST XS )−1 sgn(β̌S )

|

P ⊥
+ S
nλ

{z



+Σj,S Σ−1
S,S .

}

E1,j

Conditioning on XS and , toj is a Gaussian random variable with mean 0 and variance at most Σj,j .
Thus,
Var(E1,j |XS , ) ≤ Σj,j

(XS (XST XS )−1 sgn(β̌S )

P ⊥
+ S
nλ

2

2


T
T
−1
≤ Σj,j (sgn(β̌S )) (XS XS ) sgn(β̌S ) + kk22 /(nλ)2 .

Define an event

B1 = kk22 /n ≤ 2σ 2 , Λmax ((ΣnS,S )−1 ) ≤

4
Cmin

, k(ΣnS,S )−1 k∞

(67)


≤ (1 + Cn )K1 for Cn in Lemma A.3 (ii) .

B1 implies that
sgn(β̌S )T (XST XS )−1 sgn(β̌S ) ≤ ksgn(β̌S )k22 k(XST XS )−1 k2 ≤

s
4s
Λmax ((ΣnS,S )−1 ) ≤
.
n
nCmin

Thus, by (67) and Condition 4.4, in B1 ,
maxc Var(E1,j ) ≤ C

∗



j∈S

4s
2σ 2
+
nCmin nλ2


.

(68)

Thus, by Lemma A.3 and Condition 4.5,




P maxc |E1,j | > x ≤ P maxc |E1,j | > x, B1 + P(B1c )
j∈S
j∈S
(
)
x2
c1
≤ 2(p − s) exp −
+
+ 2 exp(−c2 log p) + 2 exp(−c3 n),
4s
2σ 2
∗
n
2C ( nCmin + nλ2 )
21

for some constant c1 , c2 , c3 > 0. Let x = (1 − κ)/2 and solve
x2
2C ∗ ( nC4smin +

2σ 2
)
nλ2

≥ 2 log p.

For

r
σ 2 Cmin
8σ
C ∗ log p
sλ ≤
and λ ≥
,
2
1−κ
n
there exists some c1 > 0, such that


c1
1+κ
≤
P maxc |Tj | >
+ 2 exp(−c4 log p) + 2 exp(−c3 n),
j∈S
2
n
2

for some constant c1 , c3 , c4 > 0.
(ii) The second task is to bound kûS k∞ . In the event that {Ŝ ⊆ S},
kûS k∞ ≤ k(ΣnS,S )−1 WSn k∞ + λk(ΣnS,S )−1 sgn(β̂S )k∞
≤ k(ΣnS,S )−1 WSn k∞ + λk(ΣnS,S )−1 k∞ .
{z
} |
{z
}
|
E2

E3

For E2 , conditioning on X, (ΣnS,S )−1 WSn is a Gaussian random vector with mean 0 and variance
(σ 2 /n)(ΣnS,S )−1 . And hence,
P (E2 > x) ≤ P (E2 > x, B1 ) +

P (B1c )

nCmin x2
≤ 2s exp −
8σ 2




+ P (B1c ) .

Lemma A.3 implies that
P (E3 > λ(1 + Cn )K1 ) ≤ 2 exp(−c5 log p),
for some c5 > 0. Using part (i) of the proof, we can obtain that for some c6 , c7 , c8 > 0,
!
r
log p
c6
P kûS k∞ ≤ 4σ
+ λ(1 + Cn )K1 ≥ 1 −
− 2 exp(−c7 n) − 2 exp(−c8 log p).
Cmin n
n

7.6

Proof of Lemma 4.2

Proof. (i) Define an event

B2 = maxc |Tj | < 1 for Tj defined in (35) and Λmax ((ΣnS,S )−1 ) ≤
j∈S

Since B2 implies {Ŝ ⊆ S}, for Tj∗ defined in (39), Lemma A.2 implies that
∗

P(Ŝ ⊆ S) ≥ P



maxc |Tj∗ |
j∈S

22


< 1, B2 .

4
Cmin


.

For toj defined in (66), we have
maxc |Tj∗ |
j∈S


PS⊥ ˆ∗
≤ maxc
+
j∈S
nλ


PS⊥ ˆ∗
T
−1
∗
o T
XS (XS XS ) sgn(β̌S ) +
+ ΣS c ,S Σ−1
≤ maxc (tj )
S,S
j∈S
nλ
|
{z
}
xTj



XS (XST XS )−1 sgn(β̌S∗ )

∞

.

(69)

∗
E1,j

Recall that under the bootstrap resampling plan (5) and (6), yi∗ ∼ N (xi,Ŝ β̂Ŝ , σ̂ 2 ) conditioning on
(X, β̂, Ŝ, σ̂ 2 ).
∗ , we first show that X (X T X )−1 sgn(β̌ ∗ ) is independent of to in (66) ∀j ∈ S c , in the
For E1,j
S
j
S S
S
event of B2 . Note that by Lemma 1 in Wainwright (2009), B2 implies that β̌ in (34) is the unique
solution to the Lasso (1). As a result, β̂ is a function of (XS , ) and Ŝ ⊆ S. Ŝ ⊆ S further implies
that β̌S∗ in (38) is a function of (XS , β̂, ˆ∗ ). Therefore, the following arguments hold true:
B2 ⊆ {β̂ is a function of (XS , ), β̌S∗ in (38) is a function of (XS , β̂, ˆ∗ )}
⊆ {β̂ is a function of (XS , ), σ̂ 2 in (7) is a function of (XS , ), β̌S∗ in (38) is a function of (XS , , σ̂, ξ)}
⊆ {β̂ is a function of (XS , ), σ̂ 2 in (7) is a function of (XS , ), β̌S∗ in (38) is a function of (XS , , ξ)}
⊆ {XS (XST XS )−1 sgn(β̌S∗ ) is a function of (XS , , ξ)}.

(70)

B2 ∩ {σ̂ 2 ≤ 2σ 2 , kξk22 ≤ 2n} implies that
XS (XST XS )−1 sgn(β̌S∗ )

P ⊥ ˆ∗
+ S
nλ

2

≤
2

4s
Cmin n

+

σ̂ 2 kξk22
4s
4σ 2
≤
+
.
n2 λ 2
Cmin n nλ2

Thus,


1−κ
∗
2
2
2
P maxc E1,j ≥
, B2 , σ̂ ≤ 2σ , kξk2 ≤ 2n
j∈S
2


1−κ
∗
≤ P maxc E1,j ≥
, (70) and (71) hold true
j∈S
2
(
)
(1 − κ)2
≤ 2(p − s) exp −
σ2
8C ∗ ( nCsmin + nλ
2)
≤ 2 exp(−c1 log p),
q
log p
4σ
for n  s log p and λ ≥ 1−κ
n .
q

log p
We conclude that for n  s log p and λ >
n ,




1+κ
1−κ
∗
∗
P maxc |Tj | ≤
, B2 ≥ P maxc |E1,j | <
, B2
j∈S
j∈S
2
2


1−κ
∗
= P(B2 ) − P maxc |E1,j | ≥
, B2
j∈S
2


1−κ
∗
≥ P(B2 ) − P maxc |E1,j
|≥
, B2 , σ̂ 2 ≤ 2σ 2 , kξk22 ≤ 2n
j∈S
2


2
2
2
− P σ̂ > 2σ − P kξk2 > 2n
4σ
1−κ

= 1 − o(1).
23

(71)

(ii) Let

B3 = Ŝ ∗ ⊆ S, Λmax ((ΣnS,S )−1 ) ≤

4
Cmin

, k(ΣnS,S )−1 k∞ ≤ K1 (1 + Cn ) for Cn in Lemma A.3 (ii),

σ̂ 2 ≤ 2σ 2 .

(72)

In B3 , (41) holds true and we have
kû∗S k∞ ≤ k(ΣnS,S )−1 WS∗ k∞ + λk(ΣnS,S )−1 sgn(β̂S∗ )k∞
T
n
−1
≤ max σ̂(ΣnS,S )−1
j,S XS ξ/n +λk(ΣS,S ) k∞ .
j∈S
|
{z
}
∗
E2,j

In B3 , for ∀j ∈ S,
n
X

−1 T
T
2
n
2
((ΣnS,S )−1
j,. Xi,S /n) = k(ΣS,S )j,. XS /nk2 ≤

i=1

1
4
Λmax ((ΣnS,S )−1 ) ≤
.
n
nCmin

By the Gaussian property of ξ, in B3 ,


nCmin x2
∗
P max E2,j
> x ≤ 2s exp(−
).
j∈S
16σ 2
B3 is a large probability event due to part (i) of the proof, Lemma A.3 and Lemma A.4. Putting
these pieces together, we have
!
r
log p
∗
+ K1 (1 + Cn )λ ≤ 2 exp(−c2 log p) + o(1) → 0,
P kûS k∞ > 4σ
Cmin n
for some c2 > 0 and λ satisfying (30).

7.7

Proof of Theorem 4.3

Proof. Under Gaussian designs, we still consider error decompositions as in (13) and (48). We use
simplified notations described in (50).
In the event that (29) holds, we can obtain that
!
zjT XS
T
|Remj | ≤ λ ej − T
(ΣnS,S )−1 [sgn(β̂S ) − sgn(βS )]
zj x j
S

≤λ

= OP

zjT XS\j
zjT xj

1

(ΣnS,S )−1

∞

sgn(β̂S ) − sgn(βS )

∞

K1 (1 + Cn )ns̃λλj
zjT xj

1

!
,

where the last step is by (43), Lemma 4.1, Lemma A.3 and the definition of s̃ in (32).
By Lemma 5.3 of Van de Geer et al. (2014), if n  sj log p,
kzj k22 /n = 1/(Σ−1 )j,j + oP (1),
24

(73)

where maxj≤p (Σ−1 )j,j ≤ 1/C∗ by Condition 4.4. Thus, for Rjo defined in (51) and ζj in (52) we
have


nK1 (1 + Cn )s̃λλj
o
+ ζj + oP (1)
Rj = OP
σkzj k2
√

nK1 (1 + Cn )s̃λλj
√
= OP
+ ζj + oP (1)
σ C∗
= oP (1) + ζj ,
(74)
where the last step is due to in A2 ,
√

p
s̃ log p
ss̃ log p
ns̃λλj =
= o(1), ss̃λλj =
= o(1) and s log ps̃λλj =
n
n

r

s log p s̃ log p
= o(1).
n
n

Next we show that for ζj in (74),
sup |P(ζj ≤ c) − Φ(c)| = oP (1).
c∈R

Conditioning on X, ζj is a Gaussian random variable with mean 0 and variance of the form (54).
By (73) and Lemma A.3, we can similarly prove (55) and (56) by replacing K2 with C∗ (1 − oP (1))
√
and replacing Cmin with Cmin /4 + oP (1). Hence, |s2n − 1| = OP ( sλj ) = oP (1). Then we have,
P(ζj ≤ c) = E[P(ζj ≤ c|X)] = E[Φ(c/sn )] = Φ(c) + oP (1).
(∗,o)

in (51) and ζj∗ in (60), Lemma 4.2 implies that
√

nK1 s̃λλj
√
= OP
+ ζj∗ + oP (1) = oP (1) + ζj∗ .
σ C∗

For the bootstrap version Rj
(∗,o)

Rj

(75)

Conditioning on X and , we can similarly prove ζj∗ is a Gaussian random variable with mean
0 and variance 1 + oP (1). Thus,
sup P(ζj∗ ≤ c) − Φ(c) = oP (1).
c∈R

Together with (63), (74), (75) and Lemma A.4,
sup


P Rj ≤ qα (Rj∗ ) − α ≤ sup
α∈(0,1)

α∈(0,1)

≤ sup

n

o
(∗,o)
P Rjo ≤ qα Rj
−α
P{Rjo ≤ zα } − α + oP (1)

α∈(0,1)

= oP (1).
(DDB)

The asymptotic normality of Rj
omitted here.

can be similarly proved as for the fixed design case and is

Acknowledgements
The author would like to thank Professor Cun-Hui Zhang for insightful and constructive discussions
on the technical part of the paper as well as the presentation.
25

References
R. F. Barber and E. J. Candes. A knockoff filter for high-dimensional selective inference. 2016.
preprint, http://arxiv.org/abs/1602.03574.
A. Belloni, V. Chernozhukov, and K. Kato. Uniform post-selection inference for least absolute
deviation regression and other z-estimation problems. Biometrika, 102(1):77–94, 2014.
R. Berk, L. Brown, A. Buja, et al. Valid post-selection inference. The Annals of Statistics, 41(2):
802–837, 2013.
P. Bühlmann and S. Van De Geer. Statistics for high-dimensional data: methods, theory and
applications. Springer Science & Business Media, 2011.
T. T. Cai and Z. Guo. Confidence intervals for high-dimensional linear regression: Minimax rates
and adaptivity. The Annals of Statistics, 45(2):615–646, 2017.
E. Candes and T. Tao. The dantzig selector: Statistical estimation when p is much larger than n.
The Annals of Statistics, pages 2313–2351, 2007.
A. Chatterjee and S. N. Lahiri. Asymptotic properties of the residual bootstrap for lasso estimators.
Proceedings of the American Mathematical Society, 138(12):4497–4509, 2010.
A. Chatterjee and S. N. Lahiri. Bootstrapping lasso estimators. Journal of the American Statistical
Association, 106(494):608–625, 2011.
A. Chatterjee and S. N. Lahiri. Rates of convergence of the adaptive lasso estimators to the oracle
distribution and higher order refinements by the bootstrap. Annals of Statistics, 41(3):1232–1259,
2013.
V. Chernozhukov, D. Chetverikov, and K. Kato. Gaussian approximations and multiplier bootstrap
for maxima of sums of high-dimensional random vectors. The Annals of Statistics, 41(6):2786–
2819, 2013.
V. Chernozhukov, D. Chetverikov, M. Demirer, et al. Double/debiased machine learning for
treatment and structural parameters. The Econometrics Journal, 2017.
H. Deng and C.-H. Zhang. Beyond gaussian approximation: Bootstrap for maxima of sums of
independent random vectors. 2017. preprint, http://arxiv.org/abs/1705.09528.
R. Dezeure, P. Bühlmann, and C.-H. Zhang. High-dimensional simultaneous inference with the
bootstrap. 2016. preprint, http://arxiv.org/abs/1606.03940.
J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its oracle properties.
Journal of the American statistical Association, 96(456):1348–1360, 2001.
E. X. Fang, Y. Ning, and H. Liu. Testing and confidence intervals for high dimensional proportional
hazards models. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2016.
J. Jankova and S. Van De Geer. Confidence intervals for high-dimensional inverse covariance
estimation. Electronic Journal of Statistics, 9(1):1205–1229, 2015.
A. Javanmard and A. Montanari. Confidence intervals and hypothesis testing for high-dimensional
regression. Journal of Machine Learning Research, 15:2869–2909, 2014a.
26

A. Javanmard and A. Montanari. Hypothesis testing in high-dimensional regression under the
gaussian random design model: Asymptotic theory. IEEE Transactions on Information Theory,
60(10):6522–6554, 2014b.
A. Javanmard and A. Montanari. De-biasing the Lasso: Optimal Sample Size for Gaussian Designs.
pages 1–32, 2015. preprint, http://arxiv.org/abs/1508.02757.
K. Knight and W. Fu. Asymptotics for lasso-type estimators. The Annals of Statistics, 28(5):
1356–1378, 2000.
J. D. Lee, D. L. Sun, Y. Sun, et al. Exact post-selection inference, with application to the lasso.
The Annals of Statistics, 44(3):907–927, 2016.
R. Lockhart, J. Taylor, R. J. Tibshirani, et al. A significance test for the lasso. Annals of statistics,
42(2):413, 2014.
E. Mammen. Bootstrap and wild bootstrap for high dimensional linear models. The Aannals of
Statistics, pages 255–285, 1993.
N. Meinshausen and P. Bühlmann. High-dimensional graphs and variable selection with the lasso.
The annals of statistics, pages 1436–1462, 2006.
R. Mitra and C.-H. Zhang. The benefit of group sparsity in group inference with de-biased scaled
group lasso. Electronic Journal of Statistics, 10(2):1829–1873, 2016.
S. Reid, R. Tibshirani, and J. Friedman. A study of error variance estimation in lasso regression.
Statistica Sinica, 26:35–67, 2016.
Z. Ren, T. Sun, C.-H. Zhang, et al. Asymptotic normality and optimalities in estimation of large
gaussian graphical models. The Annals of Statistics, 43(3):991–1026, 2015.
T. Sun and C.-H. Zhang. Scaled sparse linear regression. Biometrika, 99(4):879–898, 2012.
R. Tibshirani. Regression selection and shrinkage via the lasso. Journal of the Royal Statistical
Society B, 58(1):267–288, 1996.
R. J. Tibshirani, J. Taylor, R. Lockhart, et al. Exact post-selection inference for sequential regression
procedures. Journal of the American Statistical Association, 111(514):600–620, 2016.
S. Van de Geer, P. Bühlmann, Y. Ritov, et al. On asymptotically optimal confidence regions and
tests for high-dimensional models. Annals of Statistics, 42(3):1166–1202, 2014.
R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. pages 210–268,
2010. preprint, http://arxiv.org/abs/1011.3027.
M. J. Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using `1 constrained quadratic programming (Lasso). IEEE Transactions on Information Theory, 55(5):
2183–2202, 2009.
C.-H. Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of
statistics, 38(2):894–942, 2010.
C.-H. Zhang. Statistical inference for high-dimensional data. In Very High Dimensional
Semiparametric Models, Mathematisches Forschungsinstitut Oberwolfach, (48), 2011.
27

C.-H. Zhang and S. Zhang. Confidence intervals for low dimensional parameters in high dimensional
linear models. Journal of the Royal Statistical Society. Series B: Statistical Methodology, 76(1):
217–242, 2014.
X. Zhang and G. Cheng. Simultaneous inference for high-dimensional linear models. Journal of the
American Statistical Association, 0(0):1–12, 2017.
P. Zhao and B. Yu. On model selection consistency of Lasso. The Journal of Machine Learning
Research, 7:2541–2563, 2006.
H. Zou. The adaptive lasso and its oracle properties. Journal of the American statistical association,
101(476):1418–1429, 2006.

28

A

Some technical lemmas

Lemma A.1 (Symmetrization). Assume that Conditions 3.1 - 3.4 hold true,
r
2 log p
32σ 2
16σ
.
and n ≥ 2
λ>
1−κ
n
λ (1 − κ)2
Then we have
xTj PS⊥ 
1−κ
P maxc
>
j∈S
nλ
2

!

n
P max (ΣnS,S )−1
j,. WS > 8σ

≤ 4 exp(−c1 log p) +
r

j∈S

2 log p
Cmin n

c2
,
n

!
≤ 4 exp(−c1 log p) +

(76)
c2
,
n

(77)

for some c1 , c2 > 0.
Proof. In this proof, we apply standard symmetrization techniques.
Let
n
xTj PS⊥ 
1 X (xTj PS⊥ )i i
=
,
Q1,j =
nλ
n
λ
i=1

(˜
1 , . . . , ˜n ) be an independent copy of (1 , . . . , n ). Q̃1,j = xTj PS⊥ ˜/(nλ) and ω1 , . . . , ωn be a
Rademacher sequence. Note that

"
#
!2 
n
T P ⊥) 
2
X
2
(xTj PS⊥ )i i
(x
1
j S i i
 = 1 PS⊥ xj σ 2 ≤ σ ≡ C1 .
maxc E
= 0, maxc
E
j∈S
j∈S n
λ
λ
nλ2
λ2
2
i=1

We apply symmetrization inequalities (Problem 14.5 in Bühlmann and Van De Geer (2011)),
which gives for ∀ 0 < η < 1,



 P max c |Q − Q̃ | > (1 − η)t
1,j
1,j
j∈S
P maxc |Q1,j | > t ≤
j∈S
1 − C1 /nη 2 t2


Pn (xTj PS⊥ )i i ωi
1
2P maxj∈S c n i=1
> (1 − η)t/2
λ
≤
.
1 − C1 /nη 2 t2
For n ≥ 2C1 /(η 2 t2 ), we have
!


n
1 X (xTj PS⊥ )i i ωi
P maxc |Q1,j | > t ≤ 4P maxc
> (1 − η)t/2 .
j∈S n
j∈S
λ

(78)

i=1

Conditioning on , by McDiarmid’s inequality, we have

P maxc
j∈S

1
n

n
X
i=1

(xTj PS⊥ )i i ωi
λ

!
> (1 − η)t/2 







X
2((1 − η)t/2)2
≤
exp − P h
i2 . (79)


n
T
⊥


c
j∈S
i=1 2(xj PS )i i /(nλ)

29

Moreover, by Chebyshev’s inequality, ∀j ∈ S c
n h
X

maxc P
j∈S

2(xTj PS⊥ )i i /(nλ)

i=1

i2

!
16kPS⊥ xj k44 E[4i ]
4σ 2
>
t
≤
max
−
j∈S c
nλ2
(nλ)4 t2
≤

16(K0 + K0 κ)2 M0
,
n3 λ4 t2

where the last step is due to
maxc kPS⊥ xj k44 ≤ max
(xTj PS⊥ )2i kPS⊥ xj k22
c
j∈S

j∈S ,i≤n

2

xi,j − xi,S (XST XS )−1 XST xj
≤ n max
j∈S c ,i≤n
2

n
n
−1
≤ n max |xi,j | + max |xi,j |kΣS c ,S (ΣS,S ) k∞
i,j

i,j

2

≤ n(K0 + K0 κ) .
Thus, for any constant C2 ,
P

n h
X

2(xTj PS⊥ )i i /(nλ)

i=1

i2

!
√
4σ 2
C2 (K0 + K0 κ) M0
16
>
+
≤
→ 0.
nλ2
nλ2
nC22

And hence by (78) and (79), for n ≥ 8σ 2 /(λ2 η 2 (1 − κ)2 ),




1−κ
2[(1 − η)(1 − κ)/4]2 nλ2
16
√
P maxc |Q1,j | >
≤ 4(p − s) exp − 2
+
.
j∈S
2
nC22
4σ + C2 (K0 + K0 κ) M0
q
2
2
2 log p
16σ
and n ≥ λ232σ
, we have
Take C2 = (K +K4σκ)√M and η = 1/2. Then for λ > 1−κ
n
(1−κ)2
0
0
0


1−κ
c2
P maxc |Q1,j | >
≤ 4 exp (−c1 log p) + ,
j∈S
2
n
for some c1 , c2 > 0.
P
T
(ii) Now consider Q2,j = ni=1 (ΣnS,S )−1
j,S Xi,S i /n. Previous arguments still applies with
" n
#
X
2  
1
1
)2 2i ≤ max XS (ΣnS,S )−1
max E
(Xi,S (ΣnS,S )−1
E 2i
.,j
S,j
n j∈S
n j∈S
2
i=1

σ2
,
j∈S
Cmin
" n
#
n
2
4
X
M0 X 
−1 T
T
n
max Var
2(ΣnS,S )−1
X

/n
≤
max
2(Σ
)
X
i
S,S j,S i,S
j,S i,S
j∈S n4
j∈S
= max eTj (ΣnS,S )−1 ej σ 2 ≤

i=1

i=1

≤ max
j∈S

≤

n
4
16M0 X 
−1
n
T
k(Σ
)
k
kX
k
1
∞
S,S j,S
i,S
n4

i=1
4
4
16M0 K1 K0
.
n3

Thus,
r
P max |Q2,j | > 8σ
j∈S

2 log p
Cmin n

!

30

≤ 4 exp(−c3 log p) +

c4
.
n

Lemma A.2 (Selection consistency of the bootstrapped Lasso). For β̌ ∗ defined in (38) and Tj∗
defined in (39), if maxj∈S c |Tj∗ | < 1, Ŝ ⊆ S and ΣnS,S is invertible, then β̌ ∗ is the unique solution to
the bootstrapped Lasso and Ŝ ∗ ⊆ S.
Proof. In the event that {Ŝ ⊆ S}, β̂S c = 0. By the KKT condition of β̌S∗ in (38),
ΣnS,S (β̌S∗ − β̂S ) − WS∗ + λsgn(β̌S∗ ) = 0.
If |Tj∗ | < 1 for ∀ j ∈ S c , then there exists sgn(β̌S∗ c ) such that
ΣnS c ,S (β̌S∗ − β̂S ) − WS∗c + λsgn(β̌S∗ c ) = 0.
And hence there exists sgn(β̌ ∗ ) such that β̌ ∗ in (38) is a solution to
Σn (β̌ ∗ − β̂) − W ∗ + λsgn(β̌ ∗ ) = 0,
which is the KKT condition of the bootstrapped Lasso (37). By Lemma 1 in Wainwright (2009), β̌ ∗
is an optimal solution to the bootstrapped Lasso problem (37). Moreover, β̌ ∗ is the unique solution,
since ΣnS,S is invertible and |Tj∗ | < 1 for ∀ j ∈ S c . This implies that Ŝ ∗ ⊆ S.
Lemma A.3. Under Conditions 4.1 - 4.4, we have the following results.
(i) Let c1 > 4, c2 > 0. For n > c1 s, with probability at least 1 − 2 exp(−c2 n) → 1,
Λmax ((ΣnS,S )−1 ) ≤

4
.
Cmin

(80)

√
√
√
√
√
√
(ii) Let cn = ( s ∨ log p)/ n and Cn = 4 scn /(1 − 2cn )2 = O((s ∨ s log p)/ n). With
probability at least 1 − 2 exp(− log p/2),
k(ΣnS,S )−1 k∞ ≤ K1 (1 + Cn ) .

(81)

Proof. Let X̃ = XΣ−1/2 and Σ̃n = X̃ T X̃/n. Then Σ̃n = Ip×p .
By Corollary 5.35 of Vershynin (2010), with probability at least 1 − 2 exp(−x2 /2),
r
r

2

2
s
s
x
x
n
n
1−
−√
+√
≤ Λmin (Σ̃S,S ) ≤ Λmax (Σ̃S,S ) ≤ 1 +
.
(82)
n
n
n
n
√
√
√
√
For x = n/2 − s and n  4s, with probability at least 1 − 2 exp(−( n/2 − s)2 /2) → 1,
Λmin (Σ̃nS,S ) ≥ 1/4.
And hence,
n
Λmax ((Σ̃nS,S )−1 ) = Λ−1
min (Σ̃S,S ) ≤ 4
−1/2

−1/2

Λmax ((ΣnS,S )−1 ) = k(ΣnS,S )−1 k2 ≤ kΣS,S k2 k(Σ̃nS,S )−1 k2 kΣS,S k2 ≤
Moreover,
k(Σ̃nS,S )−1 k∞ ≤ 1 + k(Σ̃nS,S )−1 − Ik∞
√
≤ 1 + sk(Σ̃nS,S )−1 − Ik2
√
≤ 1 + sΛmax ((Σ̃nS,S )−1 ) − I)
√
n
≤ 1 + s(Λ−1
min (Σ̃S,S ) − 1).
31

4
Cmin

.

Taking x =

√

s∨

√

log p in (82), we have with probability 1 − exp(− log p/2),
√
−2

√
s ∨ log p
−1
n
√
−1
Λmin (Σ̃S,S ) − 1 ≤ 1 − 2
n
√
√
√
√
√
4( s ∨ log p)/ n − 4( s ∨ log p)2 /n
=

2
√ √
1 − 2 s∨√nlog p
√
≤ Cn / s.

Putting these arguments together, we have
−1/2

(ΣnS,S )−1

∞

−1/2

≤ ΣS,S (Σ̃nS,S )−1 ΣS,S
≤

−1/2
kΣS,S k2∞

(Σ̃nS,S )−1

∞
∞

= K1 (1 + Cn ).

q

Lemma A.4 (Consistency of variance estimator in (7)). Assume that n  s log p and λ  logn p .
If either (i) Conditions 3.1 - 3.5 hold true, or (ii) Conditions 4.1 - 4.5 hold true, then we have
σ̂ 2 = σ 2 + oP (1).

(83)

Proof. (i) For deterministic designs with  satisfying Condition 3.4, we have
kXST /nk∞ = OP (λ),
By (77) in Lemma A.1, In the event that (17) holds, we have
kûS k22 ≤ 2k(ΣnS,S )−1 WSn k22 + 2λ2 k(ΣnS,S )−1 sgn(β̂S )k22
2λ2
≤ 2sk(ΣnS,S )−1 WSn k2∞ + 2 ksgn(β̂S )k22
Cmin


s log p
= OP
.
n
p
√
Therefore, kûS k1 ≤ skûS k2 = OP (s log p/n) and |T XS ûS | ≤ nkWSn k∞ kûS k1 = OP (s log p), by
a similar as for (77). Moreover, by the KKT condition of the Lasso (1),




s log p
T n
T
n
n
ûS ΣS,S ûS = ûS WS − λsgn(β̂S ) ≤ kûS k1 kWS − λsgn(β̂S )k∞ = OP
.
(84)
n
Note that |Ŝ| ≤ |S|  n. Hence,
σ̂ 2 =

1
n − |Ŝ|
1

ky − X β̂k22


kk22 + kX ûk22 − 2T X û
n − |Ŝ|


1 s log p
= σ 2 + OP
+
+ oP (1)
n
n
=

= σ 2 + oP (1).
32

(85)

(ii) For the Gaussian designs with Gaussian errors (Condition 4.4), we have



x2
T
.
P kXS k∞ > x|XS ≤ s exp −
2nσ 2
In the event that (29) holds,
kûS k22 ≤ 2k(ΣnS,S )−1 WSn k22 + 2λ2 k(ΣnS,S )−1 sgn(β̂S )k22



8
n 2
2
= OP
skWS k∞ + sλ
Cmin


s log p
= OP
.
nCmin
Hence, kûS k1 = OP (sλ). By (84), (85) and (80) in Lemma A.3,


1 s log p
2
2
σ̂ = σ + OP
+
= σ 2 + oP (1).
n
n

33

