Testability of high-dimensional linear models with
non-sparse structures

arXiv:1802.09117v1 [math.ST] 26 Feb 2018

Jelena Bradic∗

Jianqing Fan†

Yinchu Zhu‡

February 25, 2018

Abstract
This paper studies hypothesis testing and confidence interval construction in high-dimensional
linear models with possible non-sparse structures. For a given component of the parameter vector, we show that the difficulty of the problem depends on the sparsity of the corresponding row
of the precision matrix of the covariates, not the sparsity of the model itself. We develop new
concepts of uniform and essentially uniform non-testability that allow the study of limitations
of tests across a broad set of alternatives. Uniform non-testability identifies an extensive collection of alternatives such that the power of any test, against any alternative in this group, is
asymptotically at most equal to the nominal size, whereas minimaxity shows the existence of
one particularly “bad” alternative. Implications of the new constructions include new minimax
testability results that in sharp contrast to existing results do not depend on the sparsity of the
model parameters. We identify new tradeoffs between testability and feature correlation. In
particular, we show that in models with weak feature correlations minimax lower bound can be
attained by a confidence interval whose width has the parametric rate regardless of the size of
the model sparsity.

1

Introduction

Statistical inference has widespread significance. In classical statistics, when the underlying parametric model is low-dimensional, tests and confidence intervals are constructed through a form
of a standard error of what is typically an unbiased estimator. In modern statistics, the presence
of high-dimensional observations has necessitated the development of new theory and methods
that could accommodate high-dimensional models, where the number of parameters, p, significantly exceeds the number of observations, n. The cornerstone of such development has been an
assumption on the sparsity of the model parameters that essentially hypothesizes that there exist a
much smaller set of parameters that can explain the data quite well. Indeed, sparsity assumption
of high-dimensional problems has been successfully employed in a variety of statistical problems
such as regression (Fan and Li, 2001; Tibshirani, 1996), classification (Bühlmannn, 2006; Ravikumar et al., 2010), matrix estimation (Bickel and Levina, 2008; Fan et al., 2008; Bunea et al., 2011),
Department of Mathematics, University of California, San Diego. Email: jbradic@ucsd.edu
Department of Operations Research and Financial Engineering, Princeton University. Email: jqfan@princeton.edu
‡
Lundquist College of Business, University of Oregon. Email: yzhu6@uoregon.edu

∗
†

1

graphical models (Meinshausen and Bühlmann, 2006; Wainwright et al., 2007) as well as clustering (Witten and Tibshirani, 2010; Soltanolkotabi et al., 2014). For a long time, it was perceived that
sparsity is necessary for all high-dimensional inference problems (Raskutti et al., 2011; Verzelen,
2012; Fan et al., 2013; Wainwright, 2009; Cai and Guo, 2017; Arias-Castro et al., 2011; Collier et al.,
2017). Recent works of Shah and Bühlmann (2017); Janson et al. (2017); Zhu and Bradic (2017a,b)
establish some examples where sparsity is not necessary to achieve valid inference. In this paper,
we seek to challenge the necessity of model sparsity for the purpose of high-dimensional inference. The fundamental and systematic theory that studies the limitations and tradeoffs between
sparsity and inference has not yet been fully established. This article makes contributions in that
direction, by developing a compeling new detection theory that bridges the gap between low and
high-dimensional statistics.
In this paper, we consider the high-dimensional linear regression, where the dimensionality p
can be much larger than the sample size n,
ε ∼ N (0, σ 2 In )

y = Xβ + ε,

(1)

and where y = (y1 , · · · , yn )> ∈ Rn , X = (X1 , · · · , Xn )> ∈ Rn×p and β ∈ Rp . The covariance matrix
−1
of the design is denoted by Σ = E(Xi X>
i ), whereas its precision matrix is denoted by Ω = Σ .
We denote with k = kβk0 . In this paper, our focus is on the problem of testing individual entries
of β. Without loss of generality, we consider the first entry and denote β = (β, γ > )> ∈ Rp with β
corresponding to the first coordinate of β.
Several quantifications of testing and confidence interval constructions, including Bühlmann
(2013); Nickl and van de Geer (2013); Goeman et al. (2006); Belloni et al. (2014a,b); Zhang and Zhang
(2014); Van de Geer et al. (2014); Javanmard and Montanari (2014) have been proposed. These
methods have shown that confidence intervals of the univariate parameters can be achieved at
√
the expected length of 1/ n, as long as the vector of the remaining model parameters belongs
√
to the set of k-sparse regression vectors with k  n/ log p. Such sparsity requirement recently
raised considerable interest since it appears to be a much stronger condition than that needed for
consistent estimation, which only imposes k  n/ log p; see, e.g., Negahban et al. (2009); Raskutti
et al. (2011); Rigollet and Tsybakov (2011).
√
The natural question is whether the strong condition of k  n/ log p is really needed. The
pioneer works of Cai and Guo (2017) and Javanmard and Montanari (2017) aim to address this
question, where the former, derives the minimax rate for the expected length of confidence intervals
√
assuming k . n/ log p and the latter, in a different context, improves the condition k  n/ log p
to k  n/(log p)2 .
In this paper, we push the limit even further and show that the sparsity condition for k can be
removed entirely; allowing k . p is indeed possible. In other words, the model sparsity is not an
integral part of the problem. To see this, note that β can be represented as a linear combination
of easily estimable quantity, E(Xi yi ), with the weights being the first row of Ω. Leveraging and
exploring the structure of the precision matrix Ω could allow for more general results. When Ω
is known, we show that a simple plug-in estimate achieves the parametric rate for a full range
0 ≤ k ≤ p. However, there are important hurdles that need to be cleared before minimax results
can be directly developed for inference on models that are not necessarily sparse. In fact, a new
theory of the limit of detection – one that does not restrict the growth of k – must be provided first.
2

We propose a novel framework to study the fundamental boundary of the detection rate for β
while allowing k . p. Impossibility results are established under the new concept of (essentially)
uniform non-testability. We state that the null hypothesis is uniformly non-testable against the
alternative if the power of any test of nominal level α against any point in the alternative is at most
α. Such claim is typically much stronger than the minimax results affirming that there exists at
least one point in the alternative against which the test has no power. The new concept allows us to
identify many, and not only one, “bad” alternatives. In particular, uniform non-testability results
imply minimax results and are not driven by only a few “bad” points.
The proposed uniform non-testability results also provide new insights. Under uniform nontestability, testing the null hypothesis against one (arbitrary) point is already impossible for any
test. Since any test that has size control is powerless against every point in the alternative, our work
indicates that the difficulty in these testing problems is quite fundamental. Such understanding
cannot be gained merely from the minimax framework. However, when Ω is unknown and has its
first row sparse enough, we provide a minimax optimal test and a confidence interval for β without
assuming an upper bound on k.
Our impossibility results on detection rates are stated in terms of s, the number of non-zero
entries in the first row of Ω. Thanks to the newly defined optimality criterion, the rate n−1/2 +
sn−1 log p is identified as the fundamental limit of detection for the problem of identifying the null
β = β0 against the alternative β = β0 + h. Namely, for 0 ≤ h ≤ c(n−1/2 + sn−1 log p), we highlight
that the problem above is (essentially) uniformly non-testable for some constant c > 0. Moreover,
we propose a valid test that is also asymptotically powerful against the alternatives for which β =
β0 +c0 (n−1/2 +sn−1 log p) for another constant c0 > 0. Therefore, the rate n−1/2 +sn−1 log p is indeed
a fundamental and optimal boundary of detection for models in which k can be as large as p.
In addition, the new non-testability results shed new light onto the existing literature of adaptivity of testing; here, we are interested in adaptivity with respect to k (see e.g., Javanmard and
Montanari (2017); Collier et al. (2017); Cai and Low (2006b); Laurent and Massart (2000); Verzelen
and Gassiat (2016); Cai and Guo (2017)). A particularly important question is whether it is possible to construct an adaptive confidence interval that has the minimax optimal length. Ideally, an
adaptive confidence interval should have its length automatically adjusted to the actual sparsity of
the unknown regression vector, while maintaining a pre-specified coverage probability. Although
adaptive inference is believed to be unachievable without the knowledge of Ω, we show that such
√
adaptivity can be attained by only requiring s  n/ log p and no assumption is needed on k. If Ω
is known, then we can further remove the assumption on s. In these cases, the proposed inference
procedure automatically achieves the optimal parametric rate for any 0 ≤ k ≤ p. Moreover, we also
consider adaptivity with respect to s since the detection rate is shown to depend on s. We show that
√
adaptivity to s in the region s  n/ log p is impossible in general when no constraint is imposed
on k.
The rest of the paper is organized as follows: After basic notation is introduced, Section 2
presents a precise formulation of the problem and some initial insights. Section 3 establishes two
impossibility results under the lack of sparsity in the first row of Ω. These results provide a lower
bound on the detection rates. Section 4 focuses on the upper bounds and the attainability of lower
bounds. Section 5 discusses connections to the minimax rates of detection and adaptivity of the
confidence intervals. The proofs of all of the results are presented in the Appendix as well as in the

3

Supplementary document.

2

Problem setup

We present in this section the framework for hypothesis in high-dimensional models that are not
necessarily sparse. We begin with the notation that will be used throughout the manuscript.

2.1

Notation

For a matrix X ∈ Rn×p , Xi , (X),j and Xij denote respectively the i-th row, j-th column and (i, j)
entry of the matrix X, Xi,−j denotes the i-th row of X excluding the j-th coordinate, and X−j
denotes the submatrix of X excluding the j-th column. Let [p] = {1, 2, . . . , p}. For a subset J ⊆ [p],
XJ denotes the submatrix of X consisting of columns (X),j with j ∈ J and for a vector x ∈ Rp ,
xJ is the p-dimensional vector that has the same coordinates as x on J and zero coordinates on the
complement J c of J. Let x−J denote the subvector with indices in J c . For a set S, |S| denotes its
cardinality. For a vector x ∈ Rp , supp(x) denotes the support of x and the q norm of x is defined
P
as kxkqq = j∈[p] |xj |q for q ≥ 0, with kxk0 = |supp(x)| and kxk∞ = maxj∈[p] |xj |. For a matrix A
and 1 ≤ q ≤ ∞, kAkq = supkxkq =1 kAkq . For a symmetric matrix A, λmin (A) and λmax (A) denote
respectively the smallest and largest eigenvalue of A. Iq denotes the q × q identity matrix. For two
positive sequences an and bn , an . bn means an ≤ Cbn for a positive constant C independent of
n. Moreover, we use an  bm if bn . an and an . bn . Lastly, an  bn is used to denote that
limn→∞ an /bn = 0. For a ∈ R, let bac denote the largest integer that is at most a.

2.2

High-dimensional linear models that are not necessarily sparse

We shall focus on the high-dimensional linear model (1) with the random design such that Xi ∼
Np (0, Σ), 1 ≤ i ≤ n and are independent of the error ε. Note that both Σ and the noise level σ
are considered as unknown. Since our problem is centered around the construction of confidence
intervals for the univariate parameter β, we re-parametrize model (1) as
y = Zβ + Wγ + ε,

ε ∼ N (0, σ 2 I),

(2)

where β ∈ R, γ ∈ Rp−1 , Z = (Z1 , . . . , Zn )> ∈ Rn and W = (W1 , . . . , Wn )> ∈ Rn×(p−1) . The
distribution of the data is now indexed by the parameter
θ = (β, γ, Σ, σ),
which consists of parameter of interest β, the nuisance parameters γ, the covariance matrix Σ =
n−1 E[X> X] of the random design vector X = (Z, W), and the variance of the noise σ. The observed
data is D = {D1 , . . . , Dn } with i.i.d. triplets Di = (yi , Zi , Wi ), for i = 1, · · · , n. Note that β in (2)
can be represented as
β = Ω1, E(X>
(3)
i yi ),
where Ω1, is the first row of Ω. Since each element of E(X>
i yi ) can be easily estimated at a rootn rate, the estimability of β depends on Ω only through its first row. Hence, it seems prudent to
define a parameter space that includes both the parameters of the model as well as the matrix Ω,
4


e = θ = (β, γ, Σ, σ) : β ∈ R,
Θ

M −1 ≤ λmin (Σ) ≤ λmax (Σ) ≤ M, 0 ≤ σ ≤ M1 , kβk2 ≤ M2 , (4)

where β = (β, γ > )> and M > 1, M1 and M2 are positive constants. Then, whenever Ω is known, a
simple plug-in estimate
βb = Ω1, X> y/n
(5)

achieves the parametric rate without any assumption on k. Namely, we provide the following result.
e defined in (4) we have
Theorem 1. For Θ

(6)

sup Eθ |βb − β|  n−1/2 .
e
θ∈Θ

Theorem 1 identifies that the inference for non-sparse high-dimensional models is possible as
long as the precision matrix is known, i.e., indicates that the ability to decorrelate the features (i.e., to
estimate Ω1, well) is the key to efficient inference in high-dimensional non-sparse models. Observe
that the above result does not restrict allows for p  n; in fact, it does not put any restrictions on
the growth of p or k. We note that when k is smaller than n, Cai and Guo (2017) and Javanmard
and Montanari (2017) also explore the precision matrix structure for valid inference; however, their
procedure do not extend to allow k to be much bigger than n, hence, a novel method is warranted.
To further study lower limits of detection of testing
H0 : β = β0
our focus is on the parameter spaces defined as
Θ=



θ = (β, γ, Σ, σ) : β ∈ R, M −1 ≤ λmin (Σ) ≤ λmax (Σ) ≤ M,



Σ(−1),(−1) = Ip−1 , 0 ≤ σ ≤ M1 , and kβk2 ≤ M2 , (7)
where M > 1 and M1 , M2 > 0 are some universal constants. To study upper limits of detection
e as defined in (4). It is worth pointing that none of the parameter spaces, Θ
e or Θ,
we still analyze Θ
restricts k, the number of non-zero elements in β of the linear model (1), or the `1 norm of β (which
√
can grow at a rate of p). Our work is hence very different from existing minimax studies. We also
define
Θ(s0 , β0 ) = {θ = (β, γ, Σ, σ) ∈ Θ : β = β0 , kΩ1, k0 ≤ s0 }
and

Θ(s0 ) =

[

Θ(s0 , β).

β∈R

The main goal of this paper is to address the following questions:
1. Is it possible to have accurate inference procedure about univariate parameters without requiring the
model parameter β itself to be sparse?
2. Is the accuracy in terms of the detections rates uniform over the parameter space?
5

3

Lower bound

For 0 < α < 1 and a given parameter space Θ1 , the set of tests of nominal level α ∈ (0, 1) regarding
the null hypothesis θ ∈ Θ1 is denoted with


Ψα (Θ1 ) = ψ : D 7→ [0, 1] : sup Eθ ψ ≤ α ,
θ∈Θ1

see, e.g., Lehmann and Romano (2006). Here, we allow for both random and non-random tests; for
a non-random test ψ, notice that Eθ ψ = Pθ (ψ = 1).
Definition 1 (Uniform non-testability). Consider the hypothesis testing problem of H0 : θ ∈ Θ(1) versus
H1 : θ ∈ Θ(2) . We say that Θ(1) is asymptotically uniformly nontestable against Θ(2) at size α ∈ (0, 1) if
lim supn→∞ supθ∈Θ(2) Eθ ψ ≤ α for any test ψ ∈ Ψα (Θ(1) ).
Per Definition 1 there does not exist a test that is better than a simple coin toss. Moreover, since
a simple coin toss is uniformly most powerful asymptotically, the data cannot provide sufficient
statistical evidence to distinguish the null from the alternative hypothesis. In contrast, minimaxtype results state that for any test, there is one “difficult” point in the alternative for which no test
has power; therefore, it is possible that beyond this “difficult” point, there might exist a test that
has good power against all the other points.
To characterize alternative hypothesis we introduce
Θζ,κ (s/2, β0 + hn ) =



θ ∈ Θ(s/2, β0 + a) : 0 ≤ a ≤ hn , kβk2 ≤ ζM2 ,


(ζM )−1 ≤ λmin (Σ) ≤ λmax (Σ) ≤ ζM, κ ≤ σ ≤ ζM1 ,

where hn is a sequence of positive numbers and ζ ∈ (M −1 , 1) and κ ∈ (0, ζM1 ) are constants.
Theorem 2. Suppose that sn−1 log p ≤ 1/4 and 2 ≤ s ≤ pc for some constant c < 1/2. Then we have that
for any β0
lim sup
sup
sup
Eθ ψ = α,
n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s/2,β0 +hn )

where hn = ρsn−1 log p and

ρ = min 4,

2
2 ζ −1 − 1
1/2 − c
2M (1 − ζ)2
,
,
,
15(κ−2 M + 1) M 3 (2M + 1)
2M + 1

p

(1 − ζ 2 )M2 κ2 (1 − ζ 2 )2 M22 M2 1 − ζ 2 κ2 (1 − ζ 2 )M22
√
√
,
,
,
. (8)
64ζ 4 M M12
4ζ 2 M12 M
8ζ M
2 M

Theorem 2 establishes that Θ(s, β0 ) is uniformly non-testable against all points in the alternative
Θζ,κ (s/2, β0 +hn ), i.e. every point in Θζ,κ (s/2, β0 +hn ) is difficult for every test. This result is unique
in its treatment of nuisance parameters γ, which are allowed to be fully dense. In the case of dense
models, the lower bound for detection depends on how sparse Ω1, is: it is impossible to have power
in testing β = β0 against β = β0 + h whenever |h| ≤ ρsn−1 log p. One implication is that when Ω1,
is not sparse enough (i.e., s & n/ log p), a detection of alternatives separated by a constant is not
guaranteed; that is, even deviation of non-vanishing magnitude cannot be detected.
6

The proof of Theorem 2 is formulated in a novel way. Namely, the proof emphasizes that the null
space is large and in a sense too large to control the power of a test for each point in the alternative.
For any point in the alternative hypothesis, we compute the χ2 distance between that alternative
and a large collection of points in the null hypothesis. Whenever this distance is small it would
indicate that the average rejection probability for that particular alternative is close to the average
rejection probability for many of the nulls– therefore indicating lack of power.
Next, we fine-tune the above result in search of a parametric rate of detection. In view of that
fact, we introduce a slightly weaker notion of essentially uniform non-testability.
Definition 2 (Essentially uniform non-testability). Consider the hypothesis testing problem of H0 : θ ∈
Θ(1) versus H1 : θ ∈ Θ(2) . We say that Θ(1) is asymptotically essentially uniformly nontestable against
Θ(2) at size α ∈ (0, 1/2) if lim supn→∞ supθ∈Θ(2) Eθ ψ ≤ 2α for any test ψ ∈ Ψα (Θ(1) ).
Essentially uniform non-testability implies


lim inf α +
inf
inf Pθ (ψ = 0) ≥ 1 − α.
n→∞

ψ∈Ψα (Θ(1) ) θ∈Θ(2)

We note that this statement implies the following claim on the minimax total error probability (a
notion discussed by Ingster et al. (2010))


lim inf α +
inf
sup Pθ (ψ = 0) ≥ 1 − α.
n→∞

We also denote

Θκ (s, β0 + hn ) =



ψ∈Ψα (Θ(1) ) θ∈Θ(2)

θ ∈ Θ(s, β0 + a) : 0 ≤ a ≤ hn , kβk2 ≤ M2 ,
M

−1



≤ λmin (Σ) ≤ λmax (Σ) ≤ M, κ ≤ σ ≤ M1 .

Theorem 3. Suppose that sn−1 log p ≤ 1/4 and 2 ≤ s ≤ pc for some constant c < 1/2. Then for any
constant κ ∈ (0, M1 ], we have that for any β0 ,
lim sup

sup

sup

n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θκ (s,β0 +hn )

Eθ ψ ≤ 2α,

p
where hn = n−1/2 τ and τ = κ M −1 log(1 + α2 ).

This results implies that Θ(s, β0 ) is essentially uniformly non-testable against Θκ (s, β0 +n−1/2 τ ).
This result confirms the intuition that parametric rate is a fundamental boundary for statistical
inference, an insight from the classical results of for example Lehmann and Romano (2006); Van der
Vaart (2000). Let c0 = min{ρ, τ }. Then
Θζ,κ (s/2, β0 + c0 (n−1/2 + sn−1 log p))
Hence, Theorems 2 and 3 imply
lim sup

⊂ Θζ,κ (s/2, β0 + ρsn−1 log p)

sup

sup

n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s/2,β0 +c0 (n−1/2 +sn−1 log p))

\

Θκ (s, β0 + τ n−1/2 ).

Eθ ψ ≤ 2α.

(9)

Therefore, constructing a meaningful test with a detection rate smaller than that of n−1/2 +sn−1 log p
is indeed impossible.
7

4

Upper bound

In this section, we show that the lower limit of detection matches the upper limit of detection. In
e
e 0) = S
e
this section we focus our analysis on the space Θ(s).
Formally, we define Θ(s
β0 ∈R Θ(s0 , β0 )
and
n
o
e 0 , β0 ) = θ = (β, γ, Σ, σ) ∈ Θ
e : β = β0 , kΩ1, k0 ≤ s0 .
Θ(s

We introduce notation that helps with our construction. The constructed method will utilize
a sampling splitting scheme. Let bn = bn/4c. We consider four non-overlapping subsets of the
original sample H1 = {1, ..., bn }, H2 = {bn + 1, ..., 2bn }, H3 = {2bn + 1, ..., 3bn } and H4 = {3bn +
2 and that these
1, ..., 4bn }. Next, we observe that the first row of Ω1, takes the form (1, −π > )/σV
parameters can be interpreted as the regression framework
Z = Wπ + V,

(10)

2 = E(V> V)/n. Moreover, observe that
where the vector V is independent of W with σV

yi = Wi> (πβ + γ) + ηi

(11)

for ηi = βvi +εi . Then, we notice that the parameter of interest, β, can be defined through a moment
condition
2
E[vi yi ] = βσV
.
Therefore, for a suitably chosen estimator π̆ of π, let vbi = Zi − Wi> π̆ denote the estimated residuals
of the model (10) and consider a natural estimator of β arising from the above moment condition
P
vbi yi
b
(12)
β = Pi∈H4 2 .
bi
i∈H4 v

Observe that this estimator is computed on the last fold, H4 of the data.
Next, we discuss the careful choice of the estimator π̆ of π. Denote the (p − 1)-dimensional
vector ξ = E[Wi yi ] = ΣW (πβ+γ). We propose to consider a new estimator that achieves n−1/2 bias
corresponding to large entries of ξ and yet preserves the `1 -norm consistency of typical regularized
estimates. Moreover, we note that large entries of π are not just informed by (10) but by (11) as well.
We utilize (11) to estimate large entries of ξ and then project a de-biased estimator of π onto
those entries. Due to possible overfitting we utilize sample splitting and perform the two tasks
onto separate folds of the data.
To estimate large entries we consider a simple correlation screening procedure that follows
P
model (11) by applying a hard thresholded estimator ξbA defined as ξb = b−1
n
i∈H3 Wi yi , where
n
o
A = 1 ≤ j ≤ p : |ξej | > τn ,
(13)
p
P
τn = 4M b−1
n(log p)(M12 + M22 ) and ξe = b−1
n
n
i∈H1 Wi yi . Notice that the set A is selected on
b
different fold of the data with respect to ξ.
To shrink the bias in estimated large coefficients of π, a naive de-biased estimator can be defined
as
X
b W Wi (Zi − W> π
e=π
b + b−1
Ω
π
i b ),
n
i∈H4

8

b,
where we consider a simple `1 -regularized estimator π
X
b = arg min b−1
π
(Zi − Wi> q)2 + λπ kqk1 ,
n
q∈Rp−1

i∈H2

p
b
with λπ = 24M b−1
n log p. In the above, ΩW is a carefully designed candidate estimate of ΩW =
−1
b
Σ−1
W , that utilizes model (11) while ensuring that ΩW is close to ΣW . We propose the following
estimate
bW =
Ω

arg min

λmax (Q),

(14)

Q∈R(p−1)×(p−1)



Q = Q>



b W Q ξbA
Ip−1 − Σ

∞

≤ λΩ

>
b W QξbA ≤ ηΩ ,
ξbA
QΣ
p
−1
>
3
5
2
b W = b−1 P
for Σ
n
i∈H4 Wi Wi as well as λΩ = 24 bn log pM M2 and ηΩ = 32M M2 . The second
b W.
constraint ensures an upper bound on the “magnitude” of Ω
The key construction that guarantees the theoretical properties for the inference procedure is
the following projected de-biased estimator

(15)

π̆ = arg min kqk1
q∈Rp−1

>
>
e A ≤ ηπ
ξbA
qA − ξbA
π
X
−1
bn
Wi (Zi − Wi> q)
i∈H4

b−1
n

X

i∈H4

(Zi − Wi> q)2 ≥

∞

≤ λπ /4

1
,
2M

p
p
−1/2
4
where ηπ = 6408 b−1
M 2 M2 M log(100/α).
n log pM M2 sλπ + 8bn
e.
Note that the first constraint above ensures that bias of large elements of π̆ matches that of π
The remaining two constraints are mimicking KKT conditions defining the optimality of the vector
π that follows (10): the gradient being close to zero as well as ensuring that the estimation of the
variance of the noise is non-trivial.
The estimator π̆ achieves the desirable bias-variance tradeoff: it has small bias for entries corresponding to “large” elements of ξ and has small variance on other entries.
We propose the following test
n
o
ψ∗ = 1 |βb − β0 | > cn ,
where βb is defined in (12) and

q

M 4M22 M 3 + M12 log(100/α)+
cn = 2M 10b−1/2
n
+ 34M (1 +

M2 )λ2π s

+

2
1608b−1
n M


q
2
2
n(log p)(M1 + M2 )λπ s + 2ηπ . (16)

e
We now show that even on the larger parameter Θ(s)
(compared to Θ(s)), the test ψ∗ is indeed
valid and has the optimal detection rate.
9



Theorem 4. Suppose that p ≥ max 2 1 + 1764M 2 s, 360/α and


n ≥ max 4 + 784 log p, (5067 + 220M 2 ) log(100/α),


4 + 4054 1 + 1764M 2 s log(16ep)

e β0 )), i.e.,
Then ψ∗ ∈ Ψα (Θ(s,

sup

Moreover, cn  sn−1 log p + n−1/2 and

e
θ∈Θ(s,β
0)

inf

e
θ∈Θ(s,β
0 +3cn )

Eθ ψ∗ ≤ α.

Eθ ψ∗ ≥ 1 − α.

Theorem 4 demonstrates that lower bound in (9) is achievable by a test ψ∗ as defined above.
Notice that requirement on n and p in Theorem 4 is mild; the key requirement is s . n/ log p. The
proposed uniform non-testability results indicate the new detection boundary of n−1/2 +sn−1 log p.
Theorem 4 establishes that deviations of magnitude 3cn  n−1/2 + sn−1 log p are uniformly testable
e
over Θ(s),
whereas results in Section 3 imply that even on the smaller Θ(s), deviations smaller than
this rate are (essentially) uniformly non-testable.
√
√
Moreover, the parametric rate can be attained whenever s . n/ log p. The case of n/ log p 
s  n/ log p is more difficult and our proposed test still achieves the optimal rate. Note our test
ψ∗ depends on the knowledge of s. It turns out that the uniform non-testability results in Section 3
imply that such knowledge is required to achive such rate, indicating lack of adaptivity to precision
matrix sparsity.

5

Connections to minimax rates and confidence intervals

In this section we highlight the implication of the obtained results on the minimax theory and
adaptivity.

5.1

Minimax rates

The (essential) uniform non-testability leads to the following minimax lower bound.
Corollary 5. If sn−1 log p ≤ 1/4 and 2 ≤ s ≤ pc for some constant c < 1/2, then there exists a constant
h0 > 0 such that for any β0
lim sup

sup

inf

e
n→∞ ψ∈Ψ (Θ(s,β
θ∈Θ(s,β
e
0 +hn )
α
0 ))

Eθ ψ ≤ 2α,

with hn = h0 (n−1/2 + sn−1 log p).

e β0 + h); it
Observe that Corollary 5 establishes a minimax claim that spans the space of Θ(s,
does not impose Σ(−1,),(−1) = Ip−1 and does not restrict k (the sparsity of β). Therefore, Corollary
5 directly refines the existing results on minimax testing, which routinely assume k . n/ log p; see
Cai and Guo (2017); Robins and Van Der Vaart (2006); Cai and Low (2004, 2006a); Hoffmann and
Nickl (2011); Genovese and Wasserman (2008); Nickl and van de Geer (2013); Cai and Guo (2016).
10

Corollary 5 establishes a lower bound for the minimax detection rate of the null H0 : β = β0 against
the alternative
H1 : β = β0 + h0 (n−1/2 + sn−1 log p)
regardless of the sparsity of the nuisance parameter γ in the regression model (2). As such this
result is the first that derives the lower bound for the detection rate under fairly general model
setting and in particular not requiring a model to be sparse. Theorem 4 entails that sparsity of the
first row of the precision matrix (alone) is sufficient for minimax inference (per Corollary 5), and
the model sparsity is not necessary.
In addition, Corollary 5 underlines the importance of decorrelating features in testing nonsparse high-dimensional models. When s ≥ c0 n/ log p, a direct consequence of Corollary 5 is that
it is impossible to distinguish H0 : β = β0 and H1 : β = β0 + c0 h0 in a minimax sense; in other
words, there is no power even against fixed alternatives. Our results imply that whenever Ω1, is
sparse in that kΩ1, k0 = o(n/ log p), the lower bound for minimax detection rate is of the order
n−1/2 + kΩ1, k0 n−1 log p.

√
However, when Ω1, is ultra sparse in that kΩ1, k0 = o( n/ log p), then this lower bound is the
parametric rate, i.e.
√
1/ n.

5.2

Confidence intervals

The theoretical results in Sections 3 and 4 also imply that the expected length of confidence intervals
√
cannot be adapted to s if s  n/ log p.
We denote by Cα (Θ1 ) the set of all (1 − α) level confidence intervals for β over the parameter
space Θ1 constructed from the observed data D,


Cα (Θ1 ) = [l(D), u(D)] : inf Pθ (l(D) ≤ β ≤ u(D)) ≥ 1 − α .
(17)
θ∈Θ1

The construction in Section 4 yields the following confidence interval
CI ∗ = [βb − cn , βb + cn ],

where cn is defined in (16). Theorem 4 implies that

inf Pθ (β ∈ CI ∗ ) ≥ 1 − α.

e
θ∈Θ(s)

Since |CI ∗ | = 2cn , Theorem 4 states the rate for cn and thus implies the following minimax
upper bound for the expected length of the confidence intervals:
inf

sup Eθ |CI α | . n−1/2 + sn−1 log p.

e
CI α ∈Cα (Θ(s))
e
θ∈Θ(s)

(18)

Since confidence intervals can be used to construct tests, minimax results on tests have implications for the minimax length of confidence intervals.

11

Corollary 6. Suppose that sn−1 log p ≤ 1/4 and 2 ≤ s ≤ pc for some constant c < 1/2. Then for any
α ∈ (0, 1/3), we have
inf
sup Eθ |CI α | & n−1/2 + sn−1 log p.
CI α ∈Cα (Θ(s)) θ∈Θ(s)

See Theorem 1 and Equation (3.14) of Cai and Guo (2017) for quantification of optimal confidence interval width for sparse or moderately sparse models i.e., k . n/ log p. In sharp contrast, we
allow for non-sparse vectors β, i.e., k . p. We observe that the role of the sparsity of the model parameters, as presented therein, is now, in non-sparse models, completely taken over by the sparsity
of the first row of the precision matrix. While they require the model to be sparse or moderately
sparse, we need the first row of the precision matrix to be sparse or moderately sparse.
e
e
Moreover, since Θ(s) ⊂ Θ(s)
and Cα (Θ(s))
⊂ Cα (Θ(s)), we have
sup Eθ |CI α | ≥

inf

e
CI α ∈Cα (Θ(s))
e
θ∈Θ(s)

≥

inf

sup Eθ |CI α |

inf

sup Eθ |CI α |.

e
CI α ∈Cα (Θ(s))
θ∈Θ(s)

CI α ∈Cα (Θ(s)) θ∈Θ(s)

e
Therefore, Corollary 6 still holds if we replace Θ(s) with Θ(s).
Combining this with (18), we obtain
e
the minimax optimal rate for the expected length of confidence intervals over Θ(s) and Θ(s):
inf

sup Eθ |CI α |  n−1/2 + sn−1 log p

inf

sup Eθ |CI α |  n−1/2 + sn−1 log p.

CI α ∈Cα (Θ(s)) θ∈Θ(s)

and
e
CI α ∈Cα (Θ(s))
e
θ∈Θ(s)

In Theorem 4, we have constructed a minimax rate-optimal confidence interval for β in the
case that the sparsity s is assumed to be known. A significant drawback of the construction is
that it requires prior knowledge of s, which is typically unavailable in practice. Is it possible to
construct adaptive confidence intervals that have the guaranteed coverage and automatically adjust
e
the length to s? In other words, does there exist a confidence interval in Cα (Θ(s))
that has expected
−1/2
−1
e 1 ) and any s1  s? One consequence of the
length of the order n
+ s1 n log p over all Θ(s
uniform non-testability result is that such adaptivity is not possible.

Theorem 7. Suppose that sn−1 log p ≤ 1/4 and 2 ≤ s ≤ pc for some constant c < 1/2. Then for any
α ∈ (0, 1/4) and s1 ≤ s/2, we have
inf

sup Eθ |CI α |  n−1/2 + sn−1 log p.

CI α ∈Cα (Θ(s)) θ∈Θ(s1 )

Theorem 7 says that for s1  s, the optimal rate over Θ(s1 ) for all confidence intervals that
do not take into account knowledge of s1 , is larger than that with the knowledge of s1 . Therefore,
Theorem 7 implies that for dense models (k . p), adaptivity with respect to s is in general not
√
possible if Ω1, is in at the least moderately sparse regime ( n/ log p  s . n/ log p).
The situation is very different when we consider the adaptivity with respect to k. From the work
of Cai and Guo (2017), we know that inference in high-dimensional models achieves parametric
√
rate whenever the regression model is sparse enough i.e. whenever k . n/ log(p). Their work,
12

however, does not consider the structure in the precision matrix. Our theory sheds light on their
adaptivity results. From our analysis, we can see that the lack of rate-adaptivity documented in
their paper is due to the fact that their parameter space contains points with non-sparse precision
matrices. By Theorem 4, once we restrict our attention to points with sparse enough precision
matrices, adaptivity in k to the minimax rate emerges in that in this case, the rate is always of the
parametric order, regardless of whether or not the model parameter is sparse. Hence, exploiting the
correlation structure of the features not only allows us to achieve accurate inference of non-sparse
models but also leads to the possibility of adaptivity for inference of sparse models.

6

Discussion

This paper establishes theoretical results for hypothesis testing problems in high-dimensional linear models. Our work pushes the frontier of high-dimensional inference by allowing the model
sparsity to be arbitrary. We derive the optimal detection rates and show that the accuracy of statistical inference without imposing model sparsity depends on the ability to decorrelate the features.
The sparsity of the first row of the precision matrix controls the optimal detection rate; for sparse
enough precision matrices, parametric rate can be achieved. These results also provide additional
insights on the adaptivity of optimal inference.
The theoretical development in this paper has implications far beyond minimax detection rates.
In particular, we show that the detection rate for every point in the alternative is the same and thus
the derived detection rate is uniform over the alternative. Another way of viewing our uniform
non-testability results is that these results indicate that the test from a simple coin toss is a uniformly most powerful test asymptotically. For this reason, the detection rates established in this
paper are driven by fundamental difficulty that cannot be fully described under the usual minimax
framework.
Some important extensions and refinements are left open. Our current results only provide
confidence intervals and testability results regarding univariate parameters; extending our theory
to the setting of global testing and especially multivariate testing seems like a promising avenue for
further work. In addition, for generalized linear models, it is not clear whether the phenomenon
continues to hold, as there is no obvious unbiased oracle estimator. Another challenge is that many
exciting hypothesis testing problems have complex structures and some even non-convex boundaries. A systematic approach to studying such problems would improve and extend the current
scope of inferential theoretical results. In general, work can be done to identify a subset of points
for which attainable and optimal tests can be developed, in turn, paving the way for new inferential
methods.
Supplementary document contains the detailed proofs of all auxiliary lemmas as well as details
of the proofs of results Theorems 1 and 4-7. Below we present proofs of Theorems 2 and 3.

13

A

Proof of Theorem 2

Proof of Theorem 2 has been split into a sequence of smaller results. First we present some notation,
then auxiliary Lemmas 1-6 that are useful in the proof of Theorem 2 and lastly the proof of the result
itself.

A.1

Notations

In the rest of Appendix A, we introduce the following notation. We utilize Lemma 6 below to
pinpoint the structure of the covariance matrices Σ that are of interest to us, i.e., the lower-right
corner is equal to Ip−1 .
Namely, we show that for any point θ = (β, γ, Σ, σ) ∈ Θ, we can write Σ as
!
2
π > π + σV
π>
Σ=
,
π
Ip−1
2 is a suitably chosen constant that is positive. This is
where π is a suitably chosen vector and σV
equivalent to working with the vector π ∈ Rp−1 from the following regression,

Z = Wπ + V
for a vector of residuals V ∈ Rn . Coincidently, σV will be the standard deviation of the residuals
V. Recall that Eθ [W> W]/n = Ip−1 for θ ∈ Θ. We also define a matrix Lθ as follows


Ip−1
0
0


Lθ = L(θ) = 
(19)
π>
σV 0  .
>
(πβ + γ)
βσV σ
From Lemma 6 below we know that the space of correlation matrices is spanned by the collection of Σ’s as described above. Notice that under Pθ , vector (Wi> , Zi , yi )> ∈ Rp+1 has gaussian
distribution N (0, Lθ L>
θ ).
The plan of the proof proceeds as follows. We pick an arbitrary test ψ∗ ∈ Ψα (Θ(s, β0 )) and an
arbitrary point in the alternative
θ∗ = (β∗ , γ∗ , Σ∗ , σε,∗ ) ∈ Θζ,κ (s/2, β0 + hn ),
where hn = ρsn−1 log p and
Σ∗ =

2
π∗> π∗ + σV,∗
π∗>
π∗
Ip−1

!

(20)

.

We then construct points based on θ∗ according to Definition 3 below. Observe that these points
are chosen to be dependent on the alternative. Then we proceed to show that (1) these points are
in the null space Θ(s, β0 ) and (2) the average χ2 -distance between these points and θ∗ is small.
Therefore, the power of ψ∗ against θ∗ is close to the average power against these points. Since these
points are in the null space, the power against them is at most equal to the nominal level. As a
result, the power against θ∗ is also close to the nominal level.
14

In the rest of Appendix A, we denote m = bs/2c and define the set of all m-sparse vectors with
entries taking values in {0, 1} as M, i.e.,

M = δ ∈ {0, 1}p−1 : kδk0 = m
!
p−1
and let N denote the cardinality of M. Clearly, N =
. We list M as M = {δ(1) , ..., δ(N ) },
m
i.e., δ(j) denotes the element j of the set M.
Definition 3. Given θ∗ ∈ Θζ,κ (s/2, β0 + hn ) as in (20), let 0 ≤ d ≤ ρ be such that β∗ = β0 + h with
h = dsn−1 log p. Let r = σV,∗ /σε,∗ > 0. For j ∈ {1, ..., N }, define
θj = (β0 , γ(j) , Σ(j) , σε,0 )
with
β0 = β∗ − h
γ(j) = γ∗ + hπ(j) + r(1 − h)σε,∗
p
σε,0 = σε,∗ 1 − hr2 + h2 r2
!
> π
2
>
π(j)
+
σ
π
(j)
V,0
(j)
Σ(j) =
π(j)
Ip−1
where
√
and σV,0 = σV,∗ 1 − h.

A.2

π(j) = π∗ + σV,∗

p

h/mδ(j)

p
h/mδ(j)

Auxiliary results

Below we present useful auxiliary results.
Lemma 1. For a constant c ∈ (0, 1/2), let the sequence (m, n, p) be such that 1 ≤ m ≤ pc as well as
mn−1 log p ≤ 1/4 as p → ∞. Then for any a ∈ (0, (1 − 2c)/4),
!
!
m
p−m−1
m
X
m−k

−n k
!
1 − kan−1 log p
≤ 1 + o(1).
p
−
1
k=0
m
The next two results are useful for computing χ2 -distance.
Lemma 2. Let gj denote the probability density function of N (0, Σj ) with nonsingular Σj ∈ Rk×k for
j = 0, 1, 2. Suppose that Σj can be decomposed as Σj = Lj L>
j . Then


dPg1
dPg2
1
Eg0
×
=q


 ,
dPg0
dPg0
>−I
det Ik − Q1 Q>
−
I
Q
Q
2 2
k
k
1
where Qj = L−1
0 Lj for j = 1, 2.

15

Lemma 3. Consider the notations in Definition 3. Let Qj = L−1
θ∗ Lθj . Then for any j1 , j2 ∈ {1, ..., N },
i

h

>
Q
−
I
−
I
Q
det Ip+1 − Qj1 Q>
p+1
p+1
j
j2
j1
2
h
i2
>
δ
= 1 − m−1 h[r2 (1 − h)2 + 1]δ(j
.
1 ) (j2 )

With the help of Lemmas 1, 2 and 3, we can provide the next result concerning the distance
between the null and alternative hypothesis.
Lemma 4. Consider θ∗ ∈ Θζ,κ (m, β0 +ρsn−1 log p) as defined in the proof of Theorem 2. Consider {θj }N
j=1
defined in Definition 3. Let ρ be defined as in (8). Then


lim sup Eθ∗ N −1
n→∞

N
X
dPθj
j=1

dPθ∗

2

− 1 = 0.

Note that θj is a function of ρ and γ. Next, we show that the designed points, θj belong to the
the null parameter space.
Lemma 5. Consider θ∗ ∈ Θζ,κ (m, β0 + hn ) with hn = ρsn−1 log p in the proof of Theorem 2. Consider
{θj }N
j=1 defined in Definition 3. Suppose that the conditions in the statement of Theorem 2 hold. Then
{θj : 1 ≤ j ≤ N } ⊂ Θζ,κ (2m, β0 ).
Lastly, the following lemma describes the structure of the covariance matrices.
Lemma 6. !
Consider any a > 0 and b ∈ Rp−1 . Let Σ be a positive definite matrix. If all the eigenvalue of
a b> Σ
are positive, then a > b> Σb.
Σb Σ
!
a b>
are positive, then a > b> b.
In particular, if all the eigenvalues of
b Ip−1
Now, that all of the auxiliary results are established, we are ready to present the main proof.

A.3

Proof of Theorem 2

The proof methodology is novel in that for each possible candidate point in the alternative, we
need to design a sequence of points in the null space and demonstrate that their χ2 -distances to the
candidate point in the alternative will be small therefore limiting the power of the test.
Proof of Theorem 2. Recall that m denotes the largest integer not exceeding s/2, i.e., m = bs/2c.
Fix any η > 0. Recall ρ defined in (8).
Observe that by the properties of the supremum, we can choose ψ∗ ∈ Ψα (Θ(s, β0 )) and
θ∗ = (β∗ , γ∗ , Σ∗ , σε,∗ ) ∈ Θζ,κ (s/2, β0 + hn )
with hn = ρsn−1 log p such that
sup

sup

ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s/2,β0 +hn )

16

Eθ ψ ≤ Eθ∗ ψ∗ + η.

(21)

Since k · k0 can only take values in Z, Θζ,κ (s/2, β0 + hn ) = Θζ,κ (m, β0 + hn ).
By Lemma 6, there exist σV,∗ > 0 and π∗ ∈ Rp−1 such that
!
2
π∗> π∗ + σV,∗
π∗>
Σ∗ =
.
π∗
Ip−1
We construct {θj }N
in the Definition 3.
j=1 as
 dP 
θ
Since Eθj ψ∗ = Eθ∗ ψ∗ dPθj , it follows that
∗

N

−1

N
X
j=1

Eθj ψ∗ − Eθ∗ ψ∗


N 
X
dPθj
Eθ∗ ψ∗
= N
− Eθ∗ ψ∗
dPθ∗
j=1


N
X
dPθj
= Eθ∗ ψ∗ N −1
− 1
dPθ∗
−1

j=1

(i)

≤ Eθ∗ N

(ii)



−1

N
X
dPθj
j=1



≤ Eθ∗ N −1

dPθ∗

−1

N
X
dPθj
j=1

dPθ∗

2 1/2

− 1 

,

where (i) holds by |ψ∗ | ≤ 1 almost surely and (ii) holds by Lyapunov’s inequality.
By Lemma 4 and the above display, we have
lim sup N −1
n→∞

N
X
j=1

Eθj ψ∗ − Eθ∗ ψ∗ = 0.

By Lemma 5, θj ∈ Θζ,κ (2m, β0 ) ⊆ Θ(s, β0 ) for all j ∈ {1, ..., N }. This and the fact that ψ∗ ∈
Ψα (Θ(s, β0 )) imply
N
X
N −1
Eθj ψ∗ ≤ α.
j=1

Hence, lim supn→∞ Eθ∗ ψ∗ ≤ α. By (21), we have
lim sup

sup

sup

n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s/2,β0 +hn )

Eθ ψ ≤ lim sup Eθ∗ ψ∗ + η ≤ α + η.
n→∞

Moreover, since η > 0 is arbitrary, we have
lim sup

sup

sup

n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s/2,β0 +hn )

Eθ ψ ≤ α.

Notice that a random test that rejects the hypothesis at random with probability α has power equal
to α. Since Ψα (Θ(s, β0 )) includes such random tests, the above inequality holds with equality. The
proof is complete.

17

B

Proof of Theorem 3

Proof of Theorem 3. Here we will show that no test can be better than the Likelihood Ratio test.
p
Recall τ = κ M −1 log(1 + α2 ). We choose an arbitrary test
ψ∗∗ ∈ Ψα (Θ(s, β0 ))

and an arbitrary point
θ∗∗ = (β∗∗ , γ∗∗ , Σ∗∗ , σε,∗∗ ) ∈ Θκ (s, β0 + hn )

with hn = τ n−1/2 . Throughout this proof we denote with θ∗∗ the point in the alternative space.
Notice that β∗∗ = β0 + h with 0 ≤ h ≤ hn .
We define
θ0 = (β0 , γ∗∗ , Σ∗∗ , σε,∗∗ ).
Clearly,
θ0 ∈ Θ(s, β0 )

and

Eθ0 ψ∗∗ ≤ α.

thus

Recall the notation Xi = (Zi , Wi> )> ∈ Rp . Let σz2 = Eθ0 Zi2 . By the definition of Θκ (s, β0 ),
(22)

σz2 ≤ λmax (Σ∗∗ ) ≤ M and σε,∗∗ ≥ κ2 .

Then the likelihood of the data under Pθ∗∗ can be written as a product of the likelihood of y
given X and the likelihood of X:
"

n
1
1 X
√
exp − 2
(yi − Zi β∗∗ − Wi> γ∗∗ )2
2σε,∗∗
( 2πσε,∗∗ )n
i=1
"

!#
n

1 X > −1
× p
exp −
Xi Σ∗∗ Xi
2
( det(2πΣ∗∗ ))n
i=1
1

!#

.

!#

.

Similarly, the likelihood of the data under Pθ0 can be written as
"

n
1
1 X
√
exp − 2
(yi − Zi β0 − Wi> γ∗∗ )2
2σε,∗∗
( 2πσε,∗∗ )n
i=1
"

!#
n

1 X > −1
Xi Σ∗∗ Xi
× p
exp −
2
( det(2πΣ∗∗ ))n
i=1
1

Hence, the likelihood ratio can be written as
dPθ∗∗
dPθ0

n
i
1 Xh
>
2
>
2
= exp
(y
−
Z
β
−
W
γ
)
−
(y
−
Z
β
−
W
γ
)
i
i 0
i
i ∗∗
i ∗∗
i ∗∗
2
2σε,∗∗
i=1
!
n
i
h X h
(i)
>
= exp
Zi yi − Zi (β0 + h/2) − Wi γ∗∗ ,
2
σε,∗∗
i=1

18

!
(23)

where (i) follows by β∗∗ = β0 + h. Thus,
dPθ∗∗
|Eθ0 ψ∗∗ − Eθ∗∗ ψ∗∗ | = Eθ0 ψ∗∗ − Eθ0 ψ∗∗
dPθ0


dPθ∗∗
−1
= Eθ0 ψ∗∗
dPθ0
(i)

dPθ∗∗
≤ Eθ0
−1
dPθ0
s



2 s
dPθ∗∗
dPθ∗∗ 2
≤ Eθ0
− 1 = Eθ0
− 1,
dPθ0
dPθ0

where (i) follows by |ψ∗∗ | ≤ 1. By (23), we have
"
!#


n
i
2h X h
dPθ∗∗ 2
= Eθ0 exp
Eθ0
Zi yi − Zi (β0 + h/2) − Wi> γ∗∗
2
dPθ0
σε,∗∗
i=1
!#
"
n
2h X
(i)
Zi [εi − Zi h/2]
= Eθ0 exp
2
σε,∗∗
i=1
!
#)
(
"
n
2h X
Zi [εi − Zi h/2] | Z
= Eθ0 Eθ0 exp
2
σε,∗∗
i=1
(
"
!
#
!)
n
n
2h X
h2 X 2
= Eθ0 Eθ0 exp
Zi εi | Z exp − 2
Zi
2
σε,∗∗
σε,∗∗
i=1

(24)

(25)

i=1

where (i) follows by the fact that under Pθ0 , yi = Zi β0 + Wi> γ∗∗ + εi .
P
Notice that under Pθ0 , ni=1 Zi εi conditional on Z has a Gaussian distribution with mean 0 and
P
2 . Hence, by the moment generating function of Gaussian distribuvariance equal to ni=1 Zi2 σε,∗∗
tions, it follows that
"
!
#
!
n
n
X
2h X
−2 2
Eθ0 exp
Zi εi | Z = exp 2σε,∗∗
h
Zi2 .
2
σε,∗∗
i=1

i=1

Therefore, we can use the above display to continue (25) and obtain
(
"
!
#
!)


n
n
2h X
h2 X 2
dPθ∗∗ 2
= Eθ0 Eθ0 exp
Zi εi | Z exp − 2
Zi
Eθ0
2
dPθ0
σε,∗∗
σε,∗∗
i=1
i=1
(
!
!)
n
n
2
X
X
h
−2 2
h
Zi2 exp − 2
= Eθ0 exp 2σε,∗∗
Zi2
σε,∗∗
i=1
i=1
"
!#
n
X
−2 2
= Eθ0 exp σε,∗∗
h
Zi2
"

= Eθ0 exp
(i)

"

≤ Eθ0 exp

i=1

−2 2
σz2 σε,∗∗
h

n
X

!#

(Zi2 σz−2 )

i=1



!#
n
X

(Zi2 σz−2 )
log(1 + α2 ) n−1
i=1

19

−n/2
= 1 − 2n−1 log(1 + α2 )

(ii)



≤ exp log(1 + α2 ) = 1 + α2 ,

(iii)

p
where (i) follows by 0 ≤ h ≤ hn = τ n−1/2 = n−1/2 κ M −1 log(1 + α2 ) and (22), (ii) follows by the
moment generating function of χ2 (n) (chi-squared distribution with n degrees of freedom) and the
fact that
n
X
Zi2 σz−2
i=1

has a χ2 (n) distribution together with n−1 log(1 + α2 ) < 1/2 (due to α2 < 1/4 and log(1.25) < 1/2)
and (iii) follows by the fact that
(1 − a/n)−n/2 ≤ exp(a/2)
for any n ≥ 1 and a ≥ 0.
Therefore, the above display and (24) imply that
s


√
dPθ∗∗ 2
|Eθ0 ψ∗∗ − Eθ∗∗ ψ∗∗ | ≤ Eθ0
− 1 = α2 = α.
dPθ0

Since Eθ0 ψ∗∗ ≤ α, it follows that Eθ∗∗ ψ∗∗ ≤ 2α. Since ψ∗∗ and θ∗∗ are chosen arbitrarily, the
desired result follows.

C Proof of Theorem 4
Before the main proof we establish a sequence of useful auxiliary results. Then we shall prove
Theorem 4. To simplify notations, we write P instead of Pθ . Note that all the results here hold
e
uniformly over θ ∈ Θ(s)
in finite samples. Therefore, we also omit supθ∈Θ(s)
and inf θ∈Θ(s)
whenever
e
e
possible.

C.1

Auxiliary results

The following result establishes a concentration result regarding the product of two Gaussian random variables that are allowed to be dependent. In particular, the result generalizes concentration
of measure of chi-squared random variables.
Lemma 7. Let {ri,1 }ni=1 and {ri,2 }ni=1 be sequences of i.i.d random variables with N (0, σ12 ) and N (0, σ22 )
distributions, respectively that are not necessarily independent from each other. Then for any t > 0,
!


n
X
t2
P
(ri,1 ri,2 − Eri,1 ri,2 ) ≥ tσ1 σ2 ≤ 2 exp −
.
2(2n + 7t)
i=1

Lemma 8. Let the assumption of Theorem 4 hold. Then,
(1) The population parameter ξ satisfies kξk2 ≤ 2M 2 M2 .
20

(2) The estimator ξb satisfies


q
−1
2
2
b
P kξ − ξk∞ > 2bn M n(log p)(M1 + M2 ) ≤ 2/p.

(3) Similarly,



q
X
−1
−1
2
2
P kξb − bn
Wi yi k∞ > 4bn M n(log p)(M1 + M2 ) ≤ 4/p.
i∈H4

(4) Moreover,



P kξbA k2 ≤ 4M 2 M2 ≥ 1 − 4/p.

(5) The `∞ -norm of estimation error of the thresholded estimator is


q
−1
2
2
b
P kξAc k∞ ≤ 8bn M n(log p)(M1 + M2 ) ≥ 1 − 4/p.

(6) Lastly,

P



b−1
n

X

vi (Wi> (πβ + γ) + εi ))

i∈H4

≤ 10b−1/2
n
(7) and


q

M 4M22 M 3 + M12 log(100/α) ≥ 1 − 0.02α,



X

−1
2
−1
P bn
vi ≥ (2M )
≥ 1 − 2 exp −M −2 bn /44 .
i∈H4

b W.
We now discuss the estimation properties of the proposed regularized estimator Ω

b W with
Lemma 9. Let the assumption of Theorem 4 hold. Then ΩW satisfies the constraint in (14) for Ω
probability at least 1 − 10/p − 2 exp(−bn /18).
The next result establishes a lower bound on the restricted eigenvalue constant
P
> 2
b−1
n
i∈H2 (Wi q)
.
κ(s) =
min
min
kqJ k22
|J|⊂{1,...,p−1},|J|≤s kqJ c k1 ≤3kqJ k1

Lemma 10. Let τ ∈ (0, 1) be an arbitrary constant. Whenever


1 + 36M 2 (1 + τ )2 (1 − τ )−2 s ≤ p − 1,



and bn ≥ 570 1 + 36M 2 (1 + τ )2 (1 − τ )−2 τ −2 s log(12ep/τ ), then


P κ(s) > 0.24(1 − τ )2 M −1 ≥ 1 − 4 exp(−τ 2 bn /570).

The following result establishes finite-sample properties of the Lasso estimator and follows by
standard arguments. We include it here for completeness and clarity.
21

Lemma 11. Let the assumption of Theorem 4 hold. Then,
P (kb
π − πk1 ≤ 267sλπ M ) ≥ 1 − 4 exp (−3bn /3040) − 2/p2
and
P

 X

i∈H4


Wi vi ∞ /bn ≤ λπ /4 ≥ 1 − 2/p2 .

The next two results establish the properties of the proposed regularized estimator π̆.
Lemma 12. Let the assumption of Theorem 4 hold. Then π satisfies the constraints in (15) for π̆ with
probability at least 1 − 14/p − 0.02α − 6 exp (−3bn /3040) − 2 exp(−M −2 bn /44).
Lemma 13. Let the assumption of Theorem 4 hold. Then with probability at least 1 − 14/p − 0.02α −
10 exp (−3bn /3040) − 2 exp(−M −2 bn /44),
kπ̆ − πk1 ≤ 134M λπ s.

C.2

Proof of Theorem 4

Now we are ready to prove Theorem 4.
Proof of Theorem 4. Let δ = π̆ − π. Notice that vbi = vi − Wi> δ. Then
P
b−1
bi (yi − βb
vi )
n
i∈H4 v
βb − β =
−1 P
bn
bi2
i∈H4 v
P
P
>
vi ) b−1
b−1
vi )
n
n
i∈H4 vi (yi − βb
i∈H4 δ Wi (yi − βb
=
−
.
P
P
−1
−1
2
2
bn
bn
bi
bi
i∈H4 v
i∈H4 v
{z
} |
{z
}
|
T1

(26)

T2

We now bound T1 and T2 in two steps. We first make the following observations. Notice that
Lemma 13 implies
P(M1 ) ≥ 1 − 14/p − 0.02α − 10 exp(−3bn /3040) − 2 exp(−M −2 bn /44),
where
M1 = {kπ̆ − πk1 ≤ 134M λπ s} .

Moreover, Lemma 8 implies that P(M2 ) ≥ 1 − 8/p − 0.02α, where


q
X
−1
−1
2
2
b
M2 = ξ − bn
Wi yi ≤ 4bn M n(log p)(M1 + M2 )
\

(
\

i∈H4

∞

kξbAc k∞ ≤ 8b−1
n M
b−1
n

X

i∈H4


q
2
2
n(log p)(M1 + M2 )



vi Wi> (πβ + γ) + εi

)
q

≤ 10b−1/2
M 4M22 M 3 + M12 log(100/α) .
n
22

Finally, Lemma 12 implies that
P(M3 ) ≥ 1 − 14/p − 0.02α − 6 exp(−3bn /3040) − 2 exp(−M −2 bn /44),
where
M3 =

n

>
>
e A ≤ ηπ
ξbA
πA − ξbA
π

\

Define

b−1
n

X

i∈H4

o \

b−1
n

Wi (Zi − Wi> π)

M = M1

\

M2

X

i∈H4

∞

(Zi −

Wi> π̆)2

1
≥
2M


≤ λπ /4 .

\



M3 .

Since bn > n/4 − 1 > n/5 (due to n > 784) and p ≥ 360/α, we have
P (M) ≥ 1 − 36/p − 0.06α − 16 exp (−3bn /3040) − 4 exp(−M −2 bn /44)

> 1 − 0.1α − 0.06α − 16 exp (−3n/15200) − 4 exp(−M −2 n/220)
(i)

(27)

≥ 1 − 0.16α − 16 × 0.01α − 4 × 0.01α > 1 − α

where (i) follows by the assumption of n ≥ 5067 log(100/α) and n ≥ 220M 2 log(100/α).
Since vbi = Zi − Wi> π̆, we have that by definition, on the event M,
b−1
n

X

i∈H4

Step 1: bound T1 .
First observe that

vbi2 ≥

1
.
2M

(28)

yi = Zi β + Wi> γ + εi = Wi> (πβ + γ) + βvi + εi .
Hence, yi − βb
vi = Wi> (πβ + γ) + Wi> δ + εi . Therefore,

X
X 
X
−1
>
−1
b−1
v
(y
−
βb
v
)
=
b
v
W
(πβ
+
γ)
+
ε
vi Wi> δ .
i i
i
i
i + bn
n
n
i
i∈H4

|

i∈H4

{z

T1,1

}

|

i∈H4

By definition, on the event M, we have
q

|T1,1 | ≤ 10b−1/2
M 4M22 M 3 + M12 log(100/α).
n

{z

T1,2

}

Notice that Wi vi = Wi (Zi − Wi> π). Therefore, on the event M,
|T1,2 | ≤ kδk1 b−1
n

X

i∈H4

Wi v i
∞

≤ (134M λπ s) × (λπ /4) < 34M λ2π s.

The above displays and (28) imply that on the event M,


q

−1/2
2
2
2
3
|T1 | ≤ 2M 10bn
M 4M2 M + M1 log(100/α) + 34M λπ s .
23

(29)

Step 2: bound T2 .
First notice that
b−1
n

X

i∈H4

= b−1
n
|

(30)

δ > Wi (yi − βb
vi )

X

X
b + δ > ξb − b−1
δ > (Wi yi − ξ)
δ > Wi vbi β .
n
|{z}
i∈H4
i∈H4
{z
} T2,2 |
{z
}
T2,1

T2,3

On the event M, by Hölder’s inequality, we have
|T2,1 | ≤ kδk1 b−1
n

X

i∈H4

b
(Wi yi − ξ)

∞


q
−1
2
2
≤ (134M λπ s) × 4bn M n(log p)(M1 + M2 )
q
−1
2
= 536bn M
n(log p)(M12 + M22 )λπ s.


(31)

To bound T2,2 , notice that on the event M,
>b
> b c
|T2,2 | = δA
ξ A + δA
c ξA

> b c
e A )> ξbA + (e
≤ (π̆A − π
πA − πA )> ξbA + δA
c ξA
(i)

> b c
≤ ηπ + (e
πA − πA )> ξbA + δA
c ξA

(ii)

> b c
≤ ηπ + ηπ + δA
c ξA

≤ 2ηπ + kδAc k1 kξbAc k∞
≤ 2ηπ + kδk1 kξbAc k∞



q
−1
2
2
≤ 2ηπ + (134M λπ s) × 8bn M n(log p)(M1 + M2 )
q
2
= 2ηπ + 1072b−1
M
n(log p)(M12 + M22 )λπ s,
n
(iii)

(32)

where (i) follows by the constraint (15) and (ii) and (iii) follow by the definition of M.
P
To bound T2,3 , notice on the event M, the constraint in (15) is satisfied by π̆ and thus kb−1
n
i∈H4 Wi (Zi −
>
Wi π̆)k∞ ≤ λπ /4, which is
X
≤ λπ /4.
b−1
Wi vbi
n
i∈H4

∞

Therefore, on the event M,

|T2,3 | ≤ kδk1 b−1
n
(i)

X

i∈H4

Wi vbi

∞

|β|

≤ (134M λπ s) × (λπ /4) × M2 < 34M M2 λ2π s.
24

(33)

where (i) follows by the definition of B and the fact that |β|2 ≤ β 2 + kγk22 = kβk22 ≤ M22 .
In light of (30) and (28), we combine (31), (32) and (33), obtaining that on the event M,


q
2
2 + M 2 )λ s + 2η + 34M M λ2 s .
|T2 | ≤ 2M 1608b−1
M
n(log
p)(M
π
π
2 π
n
2
1

(34)

By (26), (29) and (34), it follows that on the event M,

(35)

|βb − β| ≤ cn .

b 0 | > cn ) = Pθ (|β−β|
b
e β0 ), we have Eθ ψ∗ = Pθ (|β−β
Therefore, by (27), for any θ ∈ Θ(s,
> cn ) ≤ α.
This proves the first part of Theorem 4.
p We now show the second part of Theorem 4. It is straight-forward to see that bn  n, λπ 
n−1 log p and ηπ  sn−1 log p + n−1/2 . Therefore, cn  n−1/2 + sn−1 log p.
e β0 + 3cn ), we have that on the event M,
Moreover, for any θ ∈ Θ(s,
(i)

|βb − β0 | ≥ |β − β0 | − |βb − β| = 3cn − |βb − β| ≥ 2cn > cn ,

e β0 + 3cn ), we have
where (i) follows by (35). Thus, for any θ ∈ Θ(s,
(i)

Eθ ψ∗ = Pθ (|βb − β0 | > cn ) ≥ Pθ (M) ≥ 1 − α,

where (i) holds by (27). This proves the second part of Theorem 4.

D

Proof of Corollary 5

Proof of Corollary 5. Let h0 = min{ρ, τ }, where ρ and τ are defined in Theorems 2 and 3, respectively. Notice that
Θζ,κ (s/2, β0 + h0 (n−1/2 + sn−1 log p))
⊂ Θζ,κ (s/2, β0 + ρsn1 log p)
Thus, Theorems 2 and 3 imply

\

Θκ (s, β0 + τ n−1/2 ).

lim sup

sup

sup

Eθ ψ ≤ 2α.

lim sup

sup

inf

Eθ ψ ≤ 2α.

n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s/2,β0 +h0 (n−1/2 +sn−1 log p))

Hence,
n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s/2,β0 +h0 (n−1/2 +sn−1 log p))

(36)

e β0 )) ⊂ Ψα (Θ(s, β0 )) and Θζ,κ (s/2, β0 + hn ) ⊂
The desired result follows by noticing that Ψα (Θ(s,
−1/2
−1
e
Θ(s, β0 + hn ) with hn = h0 (n
+ sn log p).

25

E

Proof of Corollary 6

Consider a sequence of CI = [l, u] ∈ Cα (Θ(s)) such that
lim sup inf Eθ |CI| = lim sup
n→∞ θ∈Θ(s)

n→∞

inf

CI 0 ∈C

α (Θ(s))

sup Eθ |CI 0 |.

θ∈Θ(s)

Consider the test
ψ = 1{β0 ∈
/ CI}

for testing θ ∈ Θ(s, β0 ). Clearly, ψ ∈ Ψα (Θ(s, β0 )). Consider Θ(s, β0 + hn ) with hn = h0 (n−1/2 +
sn−1 log p) defined in Corollary 5.
Fix any θ ∈ Θ(s, β0 + hn ). We have that β = β0 + h0 with 0 ≤ h0 ≤ hn . Notice that
1 − Eθ ψ = Pθ (β0 ∈ CI)
= Pθ (l ≤ β0 ≤ u)

= Pθ (l ≤ β0 ≤ u and β ∈ CI) + Pθ (l ≤ β0 ≤ u and β ∈
/ CI)

(i)

= Pθ (l ≤ β0 ≤ u and β0 + h0 ∈ CI) + Pθ (l ≤ β0 ≤ u and β ∈
/ CI)

= Pθ (max{l, l − h0 } ≤ β0 ≤ min{u, u − h0 }) + Pθ (l ≤ β0 ≤ u and β ∈
/ CI)
≤ Pθ (max{l, l − h0 } ≤ min{u, u − h0 }) + Pθ (β ∈
/ CI)

≤ Pθ (l ≤ u − h0 ) + α

= Pθ (|CI| ≥ h0 ) + α ≤ Pθ (|CI| ≥ hn ) + α
where (i) follows by β = β0 + h0 . Hence,
inf

θ∈Θ(s,β0 +hn )

Eθ ψ ≥ 1 − α −

sup
θ∈Θ(s,β0 +hn )

Pθ (|CI| ≥ hn ).

By (36) in the proof of Corollary 5, we have that
lim sup

sup

inf

n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θ(s,β0 +hn )

≤ lim sup

sup

≤ lim sup

sup

Eθ ψ

inf

n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θ(s/2,β0 +hn )

inf

Eθ ψ

n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s/2,β0 +hn )

Eθ ψ ≤ 2α.

The above two displays imply
lim inf

sup

n→∞ θ∈Θ(s,β +h)
0

Pθ (|CI| ≥ hn ) ≥ 1 − 3α.

The desired result follows by noticing that
|CI| ≥ |CI|1{|CI| ≥ hn } ≥ hn 1{|CI| ≥ hn }
and thus
sup
θ∈Θ(s,β0 +hn )

Eθ |CI| ≥ hn

sup
θ∈Θ(s,β0 +hn )

26

Pθ (|CI| ≥ hn ).

F

Proof of Theorem 7

Proof of Theorem 7. By Theorem 4, we have
inf

sup

CI∈Cα (Θ(s)) θ∈Cα (Θ(s1 ))



Eθ |CI| = O n−1/2 + sn−1 log p .

Hence, it suffices to show that
lim inf
n→∞

inf CI∈Cα (Θ(s)) supθ∈Cα (Θ(s1 )) Eθ |CI|

> 0.
n−1/2 + sn−1 log p

(37)

We proceed by contradiction. Let hn be defined as in Theorem 2. Fix an arbitrary β0 ∈ R.
Suppose that there exists CI 0 = [l0 , u0 ] ∈ Cα (Θ(s)) such that
sup
θ∈Cα (Θ(s1 ))

Eθ |CI 0 | = e
hn

with lim inf n→∞ (e
hn /hn ) = 0. Define ∆ = α−1e
hn . Consider
ψ0 = 1{β0 ∈
/ CI 0 }

as the test for H0 : β = β0 vs Ha : β = β0 + ∆.
Notice that
sup
θ∈Θ(β0 ,s)

Eθ ψ0 =

sup
θ∈Θ(β0 ,s)

(i)

Pθ (β0 ∈
/ CI 0 ) ≤ α,

where (i) follows by CI 0 ∈ Cα (Θ(s)). Thus, ψ0 ∈ Ψ(Θ(β0 , s)).
Fix an arbitrary θ1 ∈ Θζ,κ (s1 , β0 + ∆). Notice that on the event
\
{β0 + ∆ ∈ CI 0 } {u0 − ∆ < l0 },

we have β0 + ∆ ≤ u0 , which means β0 ≤ u0 − ∆ < l0 and thus β0 ∈
/ CI 0 . Hence,


\
Eθ1 ψ0 = Pθ1 (β0 ∈
/ CI 0 ) ≥ Pθ1 {β0 + ∆ ∈ CI 0 } {u0 − ∆ < l0 }
≥ Pθ1 (β0 + ∆ ∈ CI 0 ) − Pθ1 (u0 − ∆ ≥ l0 )

(i)

≥ 1 − α − Pθ1 (u0 − l0 ≥ ∆)

Eθ1 |u0 − l0 |
∆
e
(iii)
hn
≥ 1−α−
∆

(ii)

≥ 1−α−

(iv)

= 1 − 2α

where (i) follows by CI 0 ∈ Cα (Θ(s)), (ii) follows by Markov’s inequality, (iii) follows by the fact that
θ1 ∈ Θ(β0 + ∆, s1 ) and supθ∈Cα (Θ(s1 )) Eθ |CI 0 | ≤ e
hn and (iv) follows by ∆ = α−1e
hn . Consequently,
we obtain
lim sup
sup
sup
Eθ ψ ≥ 1 − 2α.
n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s1 ,β0 +∆)

27

Since ∆  e
hn = o(hn ) and s1 ≤ s/2, we have that Θζ,κ (s/2, β0 + hn ) contains Θζ,κ (s1 , β0 + ∆)
for large n and thus
lim sup

sup

sup

n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s1 ,β0 +∆)

≤ lim sup

Eθ ψ

sup

sup

n→∞ ψ∈Ψα (Θ(s,β0 )) θ∈Θζ,κ (s/2,β0 +hn )

(i)

Eθ ψ ≤ α,

where (i) follows by Theorem 2. The above two displays imply that α ≥ 1 − 2α. This is not possible
since α < 1/3. Hence, we have arrived at the contradiction.
Therefore, there does not exist CI 0 = [l0 , u0 ] ∈ Cα (Θ(s)) such that supθ∈Cα (Θ(s1 )) Eθ |CI 0 | =
e
O(hn ) with e
hn = o(hn ). Hence,
!
lim inf
n→∞

inf

sup

CI∈Cα (Θ(s)) θ∈Cα (Θ(s1 ))

Similarly using Theorem 3, we can show that
lim inf
n→∞

inf

sup

CI∈Cα (Θ(s)) θ∈Cα (Θ(s1 ))

Eθ |CI| /hn > 0.
!

Eθ |CI| /(n−1/2 ) > 0.

Therefore, we have proved that the claim in (37). The proof is complete.

G

Proof of Theorem 1

Proof of Theorem 1 . To simply notation, we write E instead of Eθ . All the statements hold unie Let βb = Ω1, X> y/n. Then
formly for any θ ∈ Θ.
Notice that

βb − β = Ω1, X> (Zβ + Wγ + ε)/n − β
h
i
= Ω1, X> Z/n − 1 β + Ω1, X> (Wγ + ε)/n.
Σ=

2
γ > ΣW γ + σV
ΣW γ
>
γ ΣW
ΣW

!

−2
2 = E(V> V)/n and V = Z − Wπ. Then
and Ω1, = σV
(1, −π > ), where ΣW = E(W> W)/n, σV
h
i
Ω1, X> Z/n − 1 β + Ω1, X> (Wγ + ε)/n.

= n−1

n h
i
X
−2
−2
(vi Zi σV
− 1) + σV
vi (Wi> γ + εi ) .
i=1

where vi , Zi and Wi> γ denote the i-th entry of V, Z and Wγ, respectively.
Notice that
n
on
−2
−2
(vi Zi σV
− 1) + σV
vi (Wi> γ + εi )
i=1

is an i.i.d sequence of random variables with bounded sub-exponential norms. Therefore,
n h
i2
X
−2
−2
E(βb − β)2 = n−2
(vi Zi σV
− 1) + σV
vi (Wi> γ + εi ) . n−1 .
i=1

The desired result follows by noticing E|βb − β| ≤

q
E(βb − β)2 .

28

H

Proof of auxiliary lemmas used in proving Theorem 2

Proof of Lemma 1. Let

−n
Ak = 1 − kan−1 log p
Notice that for 0 ≤ k ≤ m,

m
k

!

!
p−m−1
m−k
!
.
p−1
m

#
−n
an−1 log p
(m − k)2
1−
1 − kan−1 log p
(k + 1)(p − 2m + k)


an−1 log p
(m − k)2
= −n log 1 −
+
log
1 − kan−1 log p
(k + 1)(p − 2m + k)


−1
(m − k)2
an log p
+
log
≤ −n log 1 −
1 − kan−1 log p
p − 2m + k
2c
(i)

p
≤ −n log 1 − 2an−1 log p + log
p − 2pc
(ii)
2a log p
p2c
≤
+
log
1 − 2an−1 log p
p − 2pc
(iii)
p2c
< 4a log p + log
p − 2pc
4a+2c−1
p
,
= log
1 − 2pc−1

Ak+1
log
= log
Ak

"

(38)

where (i) follows by the fact that

1 − kan−1 log p ≥ 1 − man−1 log p ≥ 1 − a/4 ≥ 1/2,
(ii) follows by the fact that log(1 − x) ≥ x/(x − 1) for any x ∈ (0, 1) and 2an−1 log p ∈ (0, 1) (due to
2an−1 log p ≤ 2a/(4m) ≤ a/2 < 1/2) and (iii) follows by 2an−1 log p < 1/2.
Notice that 4a + 2c − 1 < 0 and c − 1 < 0. Hence, for large p, log(Ak+1 /Ak ) ≤ − log 2 for any
0 ≤ k ≤ m. It follows that for large p,
m
X

Ak = A0 +

k=0

Notice that

A0 =

Hence,

m
X
k=1

p−m−1
m
!
p−1
m

!


1−

=

Ak ≤ A0 + A1

m−1
Y
j=0

m
p−m

m
X
k=1

2−k ≤ A0 + 2A1


m−1
Y
p − 2m + j
m
=
1−
.
p−m+j
p−m+j

m

j=0

≤ A0 ≤
29



m
1−
p

m

(39)

Since m2 /p ≤ p2c−1 → 0, both sides tend to 1 and thus A0 → 1. To bound A1 , notice that (38)
implies
p4a+2c−1
(i)
A1 ≤
A0 = o(A0 ),
c−1
1 − 2p

where (i) follows by 4a + 2c − 1 < 0 and c < 1. Hence, A1 = o(1). In light of (39), the desired result
follows.
Proof of Lemma 2. Notice that
Eg0



dPg1
dPg2
×
dPg0
dPg0



=

Z

Rk

g1 (x)g2 (x)
dx.
g0 (x)

By Lemma 11 in Cai and Guo (2017), we have
Z
g1 (x)g2 (x)
dx
g0 (x)
Rk
1
=q

−1
det Ik − Σ−1
0 [Σ1 − Σ0 ] Σ0 [Σ2 − Σ0 ]

1
=q




> −1 L L> − L L> (L−1 )> L−1 L L> − L L>
det Ik − (L−1
1 1
0 0
2 2
0 0
0
0 ) L0
0
1
=q


 >
>
> Q Q> − I
det Ik − (L−1
1 1
k Q2 Q2 − Ik L0
0 )
1
=q


 >
>
> Q Q> − I
det Ik − (L−1
1 1
k Q2 Q2 − Ik L0
0 )

1
=q


 >
 −1
>
L0
det (L0 )> Ik − Q1 Q>
1 − Ik Q2 Q2 − Ik

1
=q



 −1 

>
det L>
det (L0 )> det Ik − Q1 Q>
1 − Ik Q2 Q2 − Ik
0
1
=q


 .
>−I
det Ik − Q1 Q>
−
I
Q
Q
2
k
k
1
2

Proof of Lemma 3. We first derive some preliminary results and then compute

h
ih
i
>
det Ip+1 − Qj1 Q>
−
I
Q
Q
−
I
.
p+1
j2 j2
p+1
j1
Step 1: First we derive the form of the matrix Qj Q>
j − Ip for 1 ≤ j ≤ N .
By straight-forward computation, we can verify that


Ip−1
0
0
 −1 >

−1
σV,∗
0 .
L−1
θ∗ = −σV,∗ π∗
−1 γ >
−1 σ −1
−σε,∗
−β∗ σε,∗
∗
ε,∗
30

Thus,
Qj = L−1
θ Lθj
∗


Ip−1
0
0
Ip−1
0
0
 −1 >


−1
>
π(j)
σV,0
0 
π∗
σV,∗
0 
= −σV,∗
−1 γ >
−1 σ −1
−σε,∗
−β∗ σε,∗
(π(j) β0 + γ(j) )> β0 σV,0 σε,0
∗
ε,∗


Ip−1
0
0

−1
−1
σV,∗
(π(j) − π∗ )>
σV,∗
σV,0
0 
=



>
−1
−1
−1
σε,∗ γ(j) − γ∗ + (β0 − β∗ )π(j)
−hσε,∗ σV,0 σε,∗ σε,0


Ip−1
0
0
(i) 
−1
>
σV,∗ σV,0
0 
= a2 δ(j)

>
−1
−1
a1 δ(j) −hσε,∗ σV,0 σε,∗ σε,0

for a1 = r(1 − h)
have

p
p
> δ
h/m and a2 = h/m, where (i) follows by Definition 3. Since δ(j)
(j) = m, we

Qj Q>
j − Ip+1



Ip−1
0
0
Ip−1
a2 δ(j)
a1 δ(j)



−1
>
−1
−1 σ
σV,∗
σV,0
0 
σV,∗
σV,0 −hσε,∗
= a2 δ(j)
 0
V,0  − Ip+1
>
−1 σ
−1
−1 σ
a1 δ(j)
−hσε,∗
0
0
σε,∗
V,0 σε,∗ σε,0
ε,0


0
a2 δ(j) a1 δ(j)
(i) 
>
a
δ
0
0 
=  2 (j)
.
>
a1 δ(j)
0
0

where (i) follows by Definition
3 hand the definitions
.

i h of a1 and a2i

Step 2: Compute det Ip+1 − Qj1 Q>
Qj2 Q>
for any j1 , j2 ∈ {1, ..., N }.
j1 − Ip+1
j2 − Ip+1
From Step 1, we have that for any j1 , j2 ∈ {1, ..., M },



>
Ip+1 − Qj1 Q>
−
I
Q
Q
−
I
p+1
j2 j2
p+1
j1



0
a2 δ(j1 ) a1 δ(j1 )
0
a2 δ(j2 ) a1 δ(j2 )


>
>
0
0 
0
0 
= Ip+1 − a2 δ(j
 a2 δ(j2 )
.
1)
>
>
a1 δ(j1 )
0
0
a1 δ(j2 )
0
0


>
Ip−1 − (a21 + a22 )δ(j1 ) δ(j
0
0
)
2


> δ
> δ
0
1 − a22 δ(j
−a1 a2 δ(j
=
.
1 ) (j2 )
1 ) (j2 )
>
2
>
0
−a1 a2 δ(j1 ) δ(j2 ) 1 − a1 δ(j1 ) δ(j2 )
Since this is a block-diagonal matrix, the desired result follows by simple computation
h


i
det Ip+1 − Qj1 Q>
Qj2 Q>
j2 − Ip+1
j1 − Ip+1
!
> δ
> δ


1 − a22 δ(j
−a1 a2 δ(j
2
2
>
1 ) (j2 )
1 ) (j2 )
= det Ip−1 − (a1 + a2 )δ(j1 ) δ(j2 ) det
> δ
> δ
−a1 a2 δ(j
1 − a21 δ(j
1 ) (j2 )
1 ) (j2 )
31

(40)

(i)

h

>
δ
= 1 − (a21 + a22 )δ(j
1 ) (j2 )

i

> δ
> δ
1 − a22 δ(j
−a1 a2 δ(j
1 ) (j2 )
1 ) (j2 )
det
>
2
>
−a1 a2 δ(j1 ) δ(j2 ) 1 − a1 δ(j1 ) δ(j2 )

h
i2
>
= 1 − (a21 + a22 )δ(j
δ
,
1 ) (j2 )

!

where (i) follows by the Sylvester’s determinant identity. The desired result follows by the definitions of a1 and a2 .
Proof of Lemma 4. Recall all the notations in Lemma 3 and ρ defined in (8). Notice that

2
N
X
dPθj
Eθ∗ N −1
− 1
dPθ∗
j=1

=N

−2

N X
N
X

j2 =1 j1 =1

N X
N h
X

(i)

= N −2

j2 =1 j1 =1
(ii)

Eθ∗

= N −1



dPθj1
dPθ∗

×

dPθj2
dPθ∗



−1

>
1 − m−1 h[r2 (1 − h)2 + 1]δ(j
δ
1 ) (j2 )

i−n

−1

N h
i−n
X
>
1 − m−1 h[r2 (1 − h)2 + 1]δ(1)
δ(j)
− 1,
j=1

where (i) follows by Lemmas 2 and 3 (since there are n i.i.d observations, likelihood is a simple
product) and (ii) follows by observing that
N h
i−n
X
>
1 − m−1 h[r2 (1 − h)2 + 1]δ(j
δ
(j
)
)
2
1

j1 =1

> δ
>
does not depend on j2 . To see this, simply notice that {δ(j)
(j2 ) }1≤j≤N is a permutation of {δ(j) δ(1) }1≤j≤N
for any 1 ≤ j2 ≤ N .
For k ∈ {0, 1, ..., m}, let
>
Sk = {j ∈ {1, ..., N } : δ(1)
δ(j) = k}.
!
!
!
m
p−m−1
p−1
. Recall that N =
. It follows that
Notice that the cardinality of Sk is
k
m−k
m
2

N
X
dPθj
− 1
Eθ∗ N −1
dPθ∗
j=1
!
!
m
p−m−1
m
X
m−k

−n k
!
=
− 1.
1 − m−1 h[r2 (1 − h)2 + 1]k
p
−
1
k=0
m

By Lemma 1, it suffices to verify that we can choose a ∈ (0, (1 − 2c)/4) such that m−1 h[r2 (1 −
h)2 + 1] ≤ an−1 log p. We now verify the stronger condition of
m−1 h[r2 (1 − h)2 + 1]
< (1 − 2c)/5.
n−1 log p
32

To this end, we recall h = dsn−1 log p, 0 ≤ d ≤ ρ and s/2 − 1 < m ≤ s/2 from Definition 3. Since
m ≥ 1, we have s/m ≤ (2m + 1)/m ≤ 3. Now we observe that

m−1 dsn−1 log p [r2 (1 − h)2 + 1]
m−1 h[r2 (1 − h)2 + 1]
=
n−1 log p
n−1 log p
≤ m−1 ρs[r2 (1 − h)2 + 1]
(i)

≤ 3ρ[r2 (1 − h)2 + 1]

= 3ρ[r2 (1 − dsn−1 log p)2 + 1]

(ii)

≤ 3ρ[r2 + 1]



≤ 3ρ κ−2 M + 1

(iii)
(iv)

≤ (1/2 − c)/5,

where (i) follows by s/m ≤ 3, (ii) follows by dsn−1 log p ≤ 1 (due to sn−1 log p ≤ 1/4 and 0 ≤ d ≤
√
2
≤ M and σε,∗ ≥ κ) and (v) follows by
ρ ≤ 4), (iii) follows by r ≤ M /κ (since r = σV,∗ /σε,∗ , σV,∗
the definition of ρ. The proof is complete.
Proof of Lemma 5. Recall that from Lemma 6, we can write θ∗ = (β∗ , γ∗ , Σ∗ , σε,∗ ) ∈ Θ using
!
2
π∗> π∗ + σV,∗
π∗>
Σ∗ =
.
π∗
Ip−1
Since θ∗ ∈ Θζ,κ (m, β0 + hn ), we have (1) β∗ = β0 + h with h = dsn−1 log p and 0 ≤ d ≤ ρ and (2)
2
≤ λmax (Σ∗ ). Hence,
λmax (Σ∗ ) ≤ ζM < M . Notice that π∗> π∗ + σV,∗
max {kπ∗ k2 , σV,∗ } ≤

√

M.

Recall r = σV,∗ /σε,∗ . By the definition of Θζ,κ (s, β0 + hn ), we have
√
r ≤ M /κ.
The rest of the proof proceeds in four steps, where we verify that
(1) σε,0 ≤ M1 ,
(2) k(Σ−1
(j) ),1 k0 ≤ 2m and
−1
(3) M ≤ λmin (Σ(j) ) ≤ λmax (Σ(j) ) ≤ M .
(4) β02 + kγ(j) k22 ≤ ζ 2 M22 .
Step 1: Show σε,0 ≤ M1 .
Notice that
σε,0 = σε,∗

p
p
(i)
1 − hr2 + h2 r2 ≤ ζM1 1 − hr2 + h2 r2 ≤ ζM1 < M1 ,

where (i) −hr2 + h2 r2 ≤ 0 (since 0 ≤ h ≤ ρsn−1 log p ≤ ρ/4 ≤ 1).
Step 2: Show k(Σ−1
(j) ),1 k0 ≤ 2m.
33

(41)

(42)

Observe that (Σ−1
(j) ),1 =

1
−π(j)

!

−2
σV,0
and (Σ−1
∗ ),1 =

1
−π∗

!

−2
σV,∗
. Hence,

k(Σ−1
(j) ),1 k0 = kπ(j) k0 + 1
and k(Σ−1
∗ ),1 k0 = kπ∗ k0 + 1. Since
kπ(j) k0 ≤ kπ∗ k0 + kδ(j) k0 = kπ∗ k0 + m
and θ∗ ∈ Θζ,κ (m, β0 + hn ), we have
−1
k(Σ−1
(j) ),1 k0 ≤ k(Σ∗ ),1 k0 + m ≤ 2m.

Step 3: Show M −1 ≤ λmin (Σ(j) ) ≤ λmax (Σ(j) ) ≤ M .
Since 2m ≤ s ≤ 2m + 1 and s ≥ 2, we have m ≥ 1 and

Notice that kδ(j) k2 =

√

2 ≤ s/m ≤ 2 + 1/m ≤ 3.
m and
kπ(j) − π∗ k2 = σV,∗

p
√
h/mkδ(j) k2 = σV,∗ h.

(43)

Let k · kF denote the Frobenius norm and observe that

2

>
2
2
kΣ(j) − Σ∗ k2F = π(j)
π(j) − π∗> π∗ + σV,0
− σV,∗
+ 2kπ(j) − π∗ k22
2

(i)
2
= kπ(j) − π∗ k22 + 2(π(j) − π∗ )> π∗ − hσV,∗
+ 2kπ(j) − π∗ k22

2
(ii)
>
2
= 2(π(j) − π∗ ) π∗ + 2σV,∗
h
2
2
≤ 2kπ(j) − π∗ k2 × kπ∗ k2 + 2σV,∗
h


(iii)
√
2
2
≤ 2σV,∗ hM + 2σV,∗
h
2
(iv)  √
≤ 2 hM + 2M h
(v)

≤ M (2M + 1)ρ/2
(
)

2
(vi)
1
1
2
2
≤ min
− 1 , M (1 − ζ) ,
M2 ζ

2
2
2 h (due to Definition 3), (ii) follows by (43), (iii) follows
where (i) follows by σV,0
− σV,∗
= −σV,∗
by (43), (iv) follows by (41), (v) follows by h ≤ ρ/4 (due to h = dsn−1 log p with 0 ≤ d ≤ ρ and
sn−1 log p ≤ 1/4) and (vi) follows by 0 ≤ d ≤ ρ and the definition
p of ρ in (8).
Let k · k denote the spectral norm of a matrix (i.e., kAk = λmax (A> A)). Notice that

λmin (Σ(j) ) ≥ λmin (Σ∗ ) − kΣ(j) − Σ∗ k
34

and λmax (Σ(j) ) ≤ λmax (Σ∗ ) + kΣ(j) − Σ∗ k. Since kΣ(j) − Σ∗ k ≤ kΣ(j) − Σ∗ kF , the above display
implies that
 


1 1
λmin (Σ(j) ) ≥ λmin (Σ∗ ) − min
− 1 , M (1 − ζ)
M ζ


1 1
≥ λmin (Σ∗ ) −
−1
M ζ
and similarly
λmax (Σ(j) ) ≤ λmax (Σ∗ ) + min



1
M



≤ λmax (Σ∗ ) + M (1 − ζ).



1
− 1 , M (1 − ζ)
ζ

Since (ζM )−1 ≤ λmin (Σ∗ ) ≤ λmax (Σ∗ ) ≤ ζM , we obtain
M −1 ≤ λmin (Σ(j) ) ≤ λmax (Σ(j) ) ≤ M
.
Step 4: Show β02 + kγ(j) k22 ≤ ζ 2 M22 .
Since θ∗ ∈ Θζ,κ (m, β0 + hn ), we have that
(44)

(β0 + h)2 + kγ∗ k22 ≤ ζ 2 M22 .
Therefore, we need to show that
 2
 

β0 + kγ(j) k22 − (β0 + h)2 + kγ∗ k22 ≤ (1 − ζ 2 )M22 .

(45)

Let δγ,j = γ(j) − γ∗ . Notice that
 2
 

β0 + kγ(j) k22 − (β0 + h)2 + kγ∗ k22

= −2(β0 + h)h + h2 + kδγ,j k22 + 2γ∗> δγ,j

≤ 2|β0 + h|h + h2 + kδγ,j k22 + 2kγ∗ k2 · kδγ,j k2

(i)

≤ 2ζM2 h + h2 + kδγ,j k22 + 2ζM2 kδγ,j k2

≤ 2ζM2 hn + h2n + kδγ,j k22 + 2ζM2 kδγ,j k2 ,

(46)

where (i) follows by kγ∗ k2 ≤ ζM2 and |β0 + h| ≤ ζM2 (due to (44)).
By the assumption of sn−1 log p ≤ 1/4, M > 1 and the definition of ρ in (8) we have that
h2n = ρ2 (sn−1 log p)2 ≤ ρ2 /16 ≤

(1 − ζ 2 )M22
< (1 − ζ 2 )M22 /4
64M

(47)

and
2ζM2 hn = 2ζM2 ρsn−1 log p ≤ ζM2 ρ/2
≤
35

(1 − ζ 2 )M22
√
< (1 − ζ 2 )M22 /4. (48)
16 M

By Definition 3, we have

p
√
h/mkδ(j) k2 = hkπ(j) k2 + rσε,∗ h.
√
√
By (41) and (43), kπ(j) k2 ≤ kπ∗ k2 + kπ(j) − π∗ k2 ≤ M + σV,∗ h. Since h ≤ hn = ρsn−1 log p ≤
ρ/4, we have that

p
p
1 √
M + σV,∗ ρ/4 + rσε,∗ ρ/4
kδγ,j k2 ≤ ρ
4
√
(i) 1 
p
p
√
≤ ρ 1 + ρ/4
M + κ−1 M ζM1 ρ/4
4
(ii) 1 √
p
√
≤ ρ M + κ−1 M ζM1 ρ/4,
2
√
where (i) follows by σV,∗ ≤ M (due to (41)), σε,∗ ≤ ζM1 (due to the definition of Θζ,κ (s)) and
√
r ≤ M /κ (due to (42)) and (ii) follows by ρ ≤ 4. By the definition of ρ in (8), we have
√
√
M 2
√
ζ M1 M2 ρ
2ζM2 kδγ,j k2 ≤ ζM2 M ρ +
κ
(1 − ζ 2 )M22 (1 − ζ 2 )M22
(1 − ζ 2 )M22
≤
+
≤
.
(49)
8
8
4
By the elementary inequality of (a + b)2 ≤ 2a2 + 2b2 , we also have

2
p
√
1 √
2
−1
ρ M +κ
kδγ,j k2 ≤
M ζM1 ρ/4
2
1
M
≤ ρ2 M + 2 ζ 2 M12 ρ
2
2κ
(i) (1 − ζ 2 )M 2
(1 − ζ 2 )M22
(1 − ζ 2 )M22
2
≤
+
≤
,
(50)
8
8
4
where (i) follows by the definition of ρ in (8).
In light of (46), we obtain (45) by combining (47), (48), (49) and (50). The proof is complete.
kδγ,j k2 ≤ hkπ(j) k2 + rσε,∗

Proof of Lemma 6. Notice that
!−1
a b> Σ
Σb Σ
=

a−1 + a−2 b> Σ(Σ − a−1 Σbb> Σ)−1 Σb −b> Σ(Σ − a−1 Σbb> Σ)−1
−(Σ − a−1 Σbb> Σ)−1 Σb
(Σ − a−1 Σbb> Σ)−1

!

.

Since all the eigenvalues of the above matrix are positive, the eigenvalues of the blocks on the
diagonal are also positive. This means that the eigenvalues of Σ − a−1 Σbb> Σ are positive. Notice
that
Σ − a−1 Σbb> Σ = Σ1/2 (I − a−1 Σ1/2 bb> Σ1/2 )Σ1/2 .

Since Σ1/2 is positive definite, we have that all the eigenvalues of I − a−1 Σ1/2 bb> Σ1/2 is positive. It
follows that
det(I − a−1 Σ1/2 bb> Σ1/2 ) > 0.
By Sylvester’s determinant identity, we have det(I − a−1 Σ1/2 bb> Σ1/2 ) = 1 − a−1 b> Σb. The desired
result follows.

36

I

Proof of auxiliary lemmas used in proving Theorem 4

Proof of Lemma 7. We first prove the result assuming σ1 = σ2 = 1. Let ri = ri,1 ri,2 . Then for any
m ≥ 3,
(i)
(ii) 1
2
2 m
|ri |m = |ri,1 ri,2 |m ≤ 2−m (ri,1
+ ri,2
) ≤ (|ri,1 |2m + |ri,2 |2m ),
2
2 + r 2 )/2, (ii) follows by the elementary inequality (a + b)m ≤
where (i) follows by |ri,1 ri,2 | ≤ (ri,1
i,2
2m−1 (am + bm ) for a, b ≥ 0 and m ≥ 2. Hence,
n
X
i=1

E|ri |m ≤


n
E|r1,1 |2m + E|r1,2 |2m .
2

2 ∼ χ2 (1). The moment generating function of χ2 distribuSince r1,1 ∼ N (0, 1), we have that r1,1
tions implies
2
E exp(r1,1
/3) = (1 − 2/3)−1 = 3.

Notice that by Taylor’s series,

2
E exp(r1,1
/3) = 1 +

∞
X
3−j E exp(|r1,1 |2j )
j=1

Therefore, for any j ≥ 1,

j!

.

3−j E exp(|r1,1 |2j )
< 3.
j!

Similarly, we can show that for any j ≥ 1,
3−j E exp(|r1,2 |2j )
< 3.
j!
Let ν = 2n. Hence, for m ≥ 6,
n
X
i=1

E|ri |m ≤
≤


n
E|r1,1 |2m + E|r1,2 |2m
2


n m+1
m! m−2
ν7
.
3
m! + 3m+1 m! = n3m+1 m! <
2
2

Since both r1,1 and r1,2 are standard normal, we can easily compute for m = 3, 4, 5


m=3

n
15n
X

n
m
2m
2m
E|ri | ≤
E|r1,1 | + E|r1,2 |
= 105n m = 4

2

i=1
945n m = 5.

Pn
P
m−2 for m ≥ 3. Clearly,
2
Thus, ni=1 E|ri |m ≤ m!
i=1 E(ri ) = n < ν. Therefore, by Corollary
2 ν7
2.11 of Boucheron et al. (2013), we have that for any t > 0,
!


n
X
t2
P
(ri − Eri ) ≥ t ≤ exp −
.
2(2n + 7t)
i=1

37

Similarly, we can show the same result for −ri : for any t > 0,
!


n
X
t2
P −
(ri − Eri ) ≥ t ≤ exp −
.
2(2n + 7t)
i=1

Hence,

P

n
X
i=1

!

(ri − Eri ) ≥ t



t2
≤ 2 exp −
2(2n + 7t)



.

We have proved the result for σ1 = σ2 = 1. In the general case, notice that ri,1 σ1−1 ∼ N (0, 1)
and ri,2 σ2−1 ∼ N (0, 1). Hence, the above display implies
!


n
X

t2
−1 −1
−1 −1
P
.
ri,1 ri,2 σ1 σ2 − Eri,1 ri,2 σ1 σ2
≥ t ≤ 2 exp −
2(2n + 7t)
i=1

The desired result follows.

e
Proof of Lemma 8. By the definition of Θ(s),
we have that β 2 + kγk22 ≤ M22 . Notice that the first row
−2
−2
−2
≤ λmax (Σ−1 ) ≤ M . This
+ σV
. Therefore, M −1 ≤ λmin (Σ−1 ) ≤ kπk22 σV
of Σ−1 is (1, −π > )σV
−1/2
1/2
means that M
≤ σV ≤ M
and kπk2 ≤ M . Since M > 1, it follows that
kξk2 ≤ λmax (ΣW ) (|β| · kπk2 + kγk2 )

≤ M (M2 M + M2 ) = M2 M (M + 1) < 2M 2 M2 .

This proves part (1).
Since EWi yi = ΣW (πβ + γ), we have that for each 1 ≤ j ≤ p − 1,
X
ξbj − ξj = b−1
[Wi,j yi − EWi,j yi ] .
n
i∈H3

Notice that both Wi,j and yi are normal random variables with mean zero. Moreover,
2
EWi,j
≤ λmax (Σ) ≤ M

and
Eyi2 = σ 2 + β > Σβ ≤ σ 2 + λmax (ΣW )kβk22 ≤ M12 + M M22 ,

where we recall β = (β, γ > )> ∈ Rp .
It follows by Lemma 7 that ∀t > 0,



q
2
2
b
P bn |ξj − ξj | > t M (M1 + M M2 ) ≤ 2 exp −

t2
2(2bn + 7t)



.

√
We set t = 2 n log p. Since n/4 − 1 < bn ≤ n/4 and n/ log p ≥ 784 = 282 , the union bound
implies


q
−1
2
2
b
P kξ − ξk∞ > 2bn
n(log p)M (M1 + M M2 )


t2
≤ 2p exp −
2(2bn + 7t)
38



4n log p
√
≤ 2p exp −
2(n/2 + 14 n log p)



!
!
4
p
= 2 exp
1−
log p
1 + 28 n−1 log p



4
log p = 2/p.
≤ 2 exp
1−
1+1
Since M > 1, we have proved part (2).
By the same argument,


q
2 + M 2 ) ≤ 2/p
P kξe − ξk∞ > 2b−1
M
n(log
p)(M
n
2
1

and



P  b−1
n

X

i∈H4

Wi yi − ξ
∞

(51)

(52)


q
> 2b−1
n(log p)(M12 + M22 ) ≤ 2/p.
n M

Part (3) follows.
Now we prove part (4).
p
Denote τ = 2b−1
n(log p)(M12 + M22 ) and the event B = {kξe − ξk∞ ≤ τ }. Notice that
n M
A = {j : |ξej | ≥ 2τ } by the definition in (13). Define Aτ = {j : |ξj | ≥ τ }.
Since |ξj | ≥ |ξej | − |ξej − ξj |, we have that |ξj | ≥ |ξej | − kξe − ξk∞ . Therefore, on the event B,
|ξj | ≥ τ for any j ∈ A. In other words, on the event B, A ⊆ Aτ and thus |A| ≤ |Aτ |. To bound |Aτ |,
notice that τ 2 |Aτ | ≤ kξk22 .
T
Define the event B 0 = {kξb − ξk∞ ≤ τ }. On the event B B 0 ,
kξbA k2 ≤ kξA k2 + kξbA − ξA k2
p
≤ kξk2 + |A|kξbA − ξA k∞
p
≤ kξk2 + |Aτ |kξbA − ξA k∞
q
≤ kξk2 + kξk22 τ −2 τ
= 2kξk2 ≤ 4M 2 M2 .

Part (4) follows because (52) and part (2) imply P(B
To see part (5), notice that for any j ∈ Ac ,

T

B 0 ) ≥ 1 − 4/p.

|ξbj | ≤ kξb − ξk∞ + kξe − ξk∞ + |ξej | ≤ kξb − ξk∞ + kξe − ξk∞ + 2τ.

T
Therefore, on the event B B 0 , |ξbj | ≤ 4τ for any j ∈ Ac . Part (5) follows.
2 )
Now we show part (6). The argument is similar to the proof of part (2). Notice that vi ∼ N (0, σV
and
Wi> (πβ + γ) + εi ∼ N (0, (πβ + γ)> ΣW (πβ + γ) + σ 2 ).
2 ≤ M and
Also notice that σV

(πβ + γ)> ΣW (πβ + γ) + σ 2 ≤ λmax (ΣW )kπβ + γk22 + M12

≤ λmax (ΣW ) (kπk2 · |β| + kγk2 )2 + M12
39

(i)

≤ M (M2 M + M2 )2 + M12 < 4M22 M 3 + M12 ,
where (i) follows by M > 1.
Since Evi [Wi> (πβ + γ) + εi ] = 0, it follows by Lemma 7 that for any t > 0,


q

X 

P
vi Wi> (πβ + γ) + εi > tbn1/2 M 4M22 M 3 + M12 
i∈H4

≤ 2 exp −

t2 bn

1/2

2(2bn + 7tbn )

!

= 2 exp −

t2

−1/2

2(2 + 7tbn

)

!

.

(53)

p
Now we take t = 10 log(100/α). The assumption of (n − 4)/ log p ≥ 784 implies that n > 784.
p
−1/2
Hence, bn > n/4 − 1 > n/5, which means bn
< 5/n. Thus, the assumption of Theorem 4
p
−1/2
implies that n > 500 log(100/α) and thus tbn
≤ 10 5n−1 log(100/α) < 1. The above display
implies


q

X 

P
vi Wi> (πβ + γ) + εi > 10bn1/2 M 4M22 M 3 + M12 log(100/α)
i∈H4



100 log(100/α)
< 2 exp −
2(2 + 7)





50
= 2 exp − log(100/α)
9

< 2 exp (− log(100/α)) = α/50.



This proves part (6).
2 ) and M −1 ≤ σ 2 ≤ M . By an argument
It remains to show part (7). Notice that vi ∼ N (0, σV
V
similar to (53), we have that for any t > 0,




X

t2
P
vi2 − Evi2 > tM  ≤ 2 exp −
.
2(2bn + 7t)
i∈H4

Now we take t = bn /(2M 2 ). Hence,




X
X
1 
1
P b−1
vi2 <
≤ P b−1
(vi2 − Evi2 ) <
− Evi2 
n
n
2M
2M
i∈H4
i∈H4


X
1
1
(vi2 − Evi2 ) <
≤ P b−1
−
n
2M
M
i∈H4


X

1 
≤ P b−1
vi2 − Evi2 >
n
2M
i∈H4


X

= P
vi2 − Evi2 > tM 
i∈H4


≤ 2 exp −

b2n /(4M 4 )
2(2bn + 7bn /(2M 2 ))



40


= 2 exp −

bn /M 4
(16 + 28/M 2 )




< 2 exp −M −2 bn /44 ,

(i)

where (i) follows by 28/M 2 < 28 (since M > 1). The proof is complete.
Proof of Lemma 9. We need to show

X

P  Ip−1 − b−1
Wi Wi> ΩW ξbA
n
i∈H4

and


q
3
> 24 b−1
n log pM M2  < 6/p
∞





X
>
−1
>
5
2
P ξbA ΩW bn
Wi Wi ΩW ξbA ≤ 32M M2 ≤ 2 exp(−bn /18) + 4/p.

(54)

(55)

i∈H4

We prove these two claims in two steps.
Step 1: show (54).
Define qi = Wi Wi> ΩW ξbA and qi,j = Wi,j Wi> ΩW ξbA for 1 ≤ j ≤ p − 1. Let F denote the
σ-algebra generated by {(Wi , yi , Zi )}i∈H1 S H3 . Notice that ξbA is F-measurable and {Wi }i∈H4 is
independent of F due to the sample splitting. Therefore, for i ∈ H4 , conditional on F, Wi,j and
Wi> ΩW ξbA are both Gaussian with mean zero.
2 | F) ≤ λ
Also observe that for i ∈ H4 , E(Wi,j
max (ΣW ) ≤ M and
>
>
E[(Wi> ΩW ξbA )2 | F] ≤ ξbA
ΩW ΣW ΩW ξbA = ξbA
ΩW ξbA
kξbA k22
≤ M kξbA k22 .
≤ λmax (ΩW )kξbA k22 ≤
λmin (ΣW )

Therefore, Lemma 7 implies that for any t > 0,



X
b
P
[qi,j − E(qi,j | F)] > tM kξA k2 | F  ≤ 2 exp −
i∈H4

t2
2(2bn + 7t)



.

Since E(qi | F) = E(Wi Wi> ΩW ξbA | F) = ΣW ΩW ξbA = ξbA , we apply the union bound and
obtain that ∀t > 0,


X

P  b−1
Wi Wi> ΩW − Ip−1 ξbA ∞ > tM kξbA k2 | F 
n


i∈H4

= P  max

1≤j≤p−1


≤ 2p exp −

X

i∈H4



[qi,j − E(qi,j | F)] > tbn M kξbA k2 | F 

t2 b2n
2(2bn + 7tbn )




= 2p exp −

p
By choosing t = 6 b−1
n log p, it follows that



X
−1
>

P
bn
Wi Wi ΩW − Ip−1 ξbA
i∈H4

41

∞

t2 bn
2(2 + 7t)



.


q
b
> 6 b−1
n log pM kξA k2 


≤ 2p exp −


36 log p
p
4 + 14 × 8 b−1
n log p


(i)
36 log p
= 2p−2.6 < 2p−2 ,
≤ 2p exp −
4 + 14 × 6/14

2
where (i) follows
by the fact that

 bn > n/4 − 1 and the assumption (n − 4)/ log p ≥ 784 = 28 . By
Lemma 8, P kξbA k2 ≤ 4M 2 M2 ≥ 1 − 4/p. Therefore, we have



P

Ip−1 − b−1
n

X

i∈H4


Wi Wi> ΩW ξbA

∞

≤ 4/p + 2p−2 < 6/p.


q
3
> 24 b−1
n log pM M2 

We have proved (54).
Step 2: show (55).
> Ω W . For i ∈ H , notice that conditional on F, r is Gaussian with mean zero and
Let ri = ξbA
i
4
i
W
>Ω Σ Ω ξ
b
b
b>
variance ξbA
W W W A = ξA ΩW ξA . It follows by Lemma 7 that




X

t2
2
2
>
b
b


P
ri − E(ri | F) > tξA ΩW ξA | F ≤ 2 exp −
.
2(2bn + 7t)
i∈H4

0 Ω ξ
b
Since E(ri2 | F) = ξbA
W A , we have


X

>
P b−1
ri2 > 1 + bn−1 t ξbA
ΩW ξbA 
n



i∈H4



X

2
2
>
b
b


=P
ri − E(ri | F) > tξA ΩW ξA ≤ 2 exp −
i∈H4

t2
2(2bn + 7t)



.

>Ω ξ
b
b 2
b 2
b 2
b
Notice that ξbA
W A ≤ λmax (ΩW )kξA k2 = kξA k2 /λmax (ΣW ) ≤ M kξA k2 . By Lemma 8, kξA k2 ≤
2
4M M2 with probability at least 1 − 4/p. Therefore, we have that




X
 5 2
t2
−1
2
−1


P bn
ri > 16 1 + bn t M M2 ≤ 2 exp −
+ 4/p.
2(2bn + 7t)
i∈H4

Since b−1
n

P

2
i∈H4 ri

>Ω
−1
= ξbA
W bn

P

i∈H4


Wi Wi> ΩW ξbA , we choose t = bn and obtain (55).

Proof of Lemma 10. We invoke Corollary 18 of Rudelson and Zhou (2013) and Lemma 4.1 of Bickel
et al. (2009).
For any k between 1 and p, we define the sparse eigenvalues
P
> 2
b−1
n
i∈H2 (Wi q)
φmin (k) = min
kqk22
1≤kqk0 ≤k

and

φmax (k) =

max

b−1
n

1≤kqk0 ≤k

42

P

> 2
i∈H2 (Wi q)
.
kqk22

The proof proceeds in two steps. We first verify a sufficient condition for the sparse eigenvalue
condition and then derive the desired result.
p
−1/2
Step 1: Show that rows of ΣW W are isotropic and ψ2 with constant 8/3.
−1/2
Notice that ΣW W is a matrix whose entries are i.i.d N (0, 1). Let r > denote the first row of
−1/2
ΣW W. For any nonzero vector q ∈ Rp−1 , (r > q)2 /kqk22 has a chi-squared distribution with one
degree of freedom. By the moment generating function of chi-squared distributions, we have that
√
for any t > 2kqk2 ,

Thus,

 
−1/2

 > 2
h

i
2kqk22
(r q)
kqk22
> 2 2
= 1−
E exp (r q) /t
= E exp
.
× 2
t
t2
kqk22

n
h

io p
inf t : E exp (r > q)2 /t2
≤ 8/3kqk2 .
p
In other words, r is isotropic and ψ2 with constant 8/3; see Definition 5 of Rudelson and Zhou
(2013).
Step 2: Show the desired result.
By Corollary 18 of Rudelson and Zhou (2013), we have that with probability at least 1−2 exp(−τ 2 bn /570),
(1 − τ )2 M −1 ≤ φmin (k) ≤ φmax (k) ≤ (1 + τ )2 M
if bn ≥ 570τ −2 k log(12ep/τ ). Let m be the smallest integer satisfying m ≥ 36M 2 (1 + τ )2 (1 − τ )−2 s.
This means that if bn ≥ 570τ −2 (s + m) log(12ep/τ ), then P (B) ≥ 1 − 4 exp(−τ 2 bn /570), where
the event B is defined as

B = φmin (s + m) ≥ (1 − τ )2 M −1 and φmax (m) ≤ (1 + τ )2 M .

Notice that on the event B, mφmin (m + s) > c20 sφmax (m) with c0 = 3. By Lemma 4.1(ii) of Bickel
et al. (2009), on the event B
s
!
p
p
sφmax (m)
κ(s) = φmin (m + s) 1 − c0
mφmin (m + s)
r
p
s
= φmin (m + s) − c0
φmax (s)
m
r
s
−1/2
≥ (1 − τ )M
−3×
× (1 + τ )2 M
36M 2 (1 + τ )2 (1 − τ )−2 s
= 0.5(1 − τ )M −1/2 .

The desired result follows.
Proof of Lemma 11. We invoke Theorem 6.1 of Bühlmann and Van De Geer (2011). We first show a
P
concentration result for k i∈H2 Wi vi k∞ .
2 )) with E(W2 ) ≤ λ
For 1 ≤ j ≤ p − 1, Wi,j ∼ N (0, E(Wi,j
max (Σ) ≤ M . Also observe that
i,j
2
2
vi ∼ N (0, σV ) with σV ≤ λmax (Σ) ≤ M . Since E(Wi,j vi ) = 0, it follows by Lemma 7 that ∀t > 0,




X
t2


P
Wi,j vi > tM ≤ 2 exp −
.
2(2bn + 7t)
i∈H2

43

By the union bound, we have

X
P
Wi vi
i∈H2





> tM ≤ 2p exp −
∞

t2
2(2bn + 7t)

√
Taking t = 6 bn log p, we have that


X
p
P
Wi vi ∞ > 6M bn log p ≤ 2p exp −
i∈H2



.

36 log p
p
4 + 14 × 6 b−1
n log p

!



36 log p
≤ 2p exp −
= 2p−2.6 < 2/p2 ,
4+6

(i)

where (i) follows by bn > n/4 − 1 and the assumption (n − 4)/ log p ≥ 784 = 282 . In other words,


X
P 2
Wi vi ∞ /bn ≤ λπ /2 ≥ 1 − 2/p2 .
(56)
i∈H2

By the assumptions of Theorem 4 and bn > n/4 − 1, we can easily verify the assumption of
Lemma 10 with τ = 3/4. Thus, we apply Lemma 10 with τ = 3/4 and obtain the restricted eigenvalue condition

(57)
P κ(s) > 0.015M −1 ≥ 1 − 4 exp (−3bn /3040) ,

where κ(s) is defined in Lemma 10. Notice that due to Hölder’s inequality, κ(s) is smaller than the
compatibility constant in Equation (6.4) of Bühlmann and Van De Geer (2011):
P
> 2
b−1
n
i∈H2 (Wi q)
κ(s) =
min
min
kqJ k22
|J|⊂{1,...,p−1},|J|≤s kqJ c k1 ≤3kqJ k1
P
> 2
b−1
n
i∈H2 (Wi q)
.
≤
min
min
kqJ k21 /s
|J|⊂{1,...,p−1},|J|≤s kqJ c k1 ≤3kqJ k1
By (56) and (57), together with Theorem 6.1 of Bühlmann and Van De Geer (2011), we have that
P (kb
π − πk1 ≤ 267sλπ M ) ≥ 1 − 4 exp (−3bn /3040) − 2/p2 .

This proves the first claim. For the second claim, we simply follow the same argument as in (56)
with H2 replaced by H4 .
Proof of Lemma 12. We need to show that with high probability,

and
b−1
n

>
>
e A ≤ ηπ ,
ξbA
πA − ξbA
π

X

i∈H4

as well as

b−1
n

Wi (Zi − Wi> π)

X

i∈H4

∞

(Zi − Wi> π)2 ≥
44

≤ λπ /4

1
.
2M

(58)

Since Zi − Wi> π = vi , Lemmas 11 and 8 imply that


X
P  b−1
Wi (Zi − Wi> π) ∞ ≤ λπ /4 ≥ 1 − 2/p2 > 1 − 2/p
n

(59)

i∈H4

and



P b−1
n

X

i∈H4

(Zi − Wi> π)2 ≥

It remains to show (58). Notice that

and thus

b W b−1
e − π = Ip−1 − Ω
π
n

>
>
e A − ξbA
ξbA
π
πA


>
b W b−1
= ξbA
Ip−1 − Ω
n

|

X

i∈H4

X

i∈H4

{z
T1



1 
≥ 1 − 2 exp(−M −2 bn /44).
2M


Wi Wi>  (b
π − π) + b−1
n


Wi Wi>  (b
π − π) + b−1
n
}

|

X

i∈H4

X

i∈H4

(60)

b W Wi vi
Ω

>b
ξbA
ΩW Wi vi .

{z
T2

}

We proceed in two steps. We first bound T1 and then T2 .
b W . By Lemma 9,
Let B denote the event that ΩW satisfies the constraint in (14) for Ω
P (B) ≥ 1 − 10/p − 2 exp(−bn /18).

(61)

Step 1: bound T1
b W satisfies the constraint in (14) and therefore,
Notice that on the event B, Ω


X
>
b W b−1
|T1 | ≤ ξbA
Ip−1 − Ω
Wi Wi> 
kb
π − πk1
n
i∈H4

q
3
≤ 24 b−1
π − πk1 ,
n log pM M2 kb

(i)

∞

where (i) follows by the constraint in (14). By the bound in Lemma 11, we have that


q
−1
4
P |T1 | > 6408 bn log pM M2 sλπ and B ≤ 4 exp (−3bn /3040) + 2/p2 .

(62)

Step 2: bound T2
Let F be the σ-algebra generated by {(yi , Wi , Zi )}i∈H1 S H3 and {Wi }i∈H4 . Notice that {vi }i∈H4
is independent of both {Wi }i∈H4 and {(yi , Wi , Zi )}i∈H1 S H3 . Hence, {vi }i∈H4 is independent of F.
>Ω
b W Wi }i∈H is F-measurable. Since {vi }i∈H is i.i.d N (0, σ 2 ),
On the other hand, notice that {ξbA
4
4
V
we have that conditional on F, T2 is Gaussian with mean zero and variance


X
>b
b W ξbA .
ξbA
ΩW b−2
Wi Wi>  Ω
n
i∈H4

45

By the elementary bound of P(|X| > tσ) ≤ 2 exp(−t2 /2) for X ∼ N (0, σ 2 ), we have that for any
t > 0,
v




u
u

u > b  −2 X

2
b W ξbA | F 
P |T2 | > ttξbA
ΩW bn
Wi Wi>  Ω
 ≤ 2 exp −t /2 .
i∈H4

b W satisfies the constraint in (14) and thus
We notice that, on the event B, Ω
X

>b
b W ξbA ≤ 32M 5 M 2 b−1 .
ξbA
ΩW b−2
Wi Wi> Ω
n
2 n
i∈H4

It follows that for any t > 0,


√

2
2M
|
F
≤ 2 exp −t2 /2 .
P |T2 | > 4tb−1/2
M
M
2
n

We take t =

p
2 log(100/α) and obtain


p
2
P |T2 | > 8b−1/2
M
M
M
log(100/α)
and
B
≤ 0.02α.
2
n

(63)

Now we combine (61), (62) and (63), obtaining

P (|T1 | + |T2 | > ηπ ) ≤ 10/p + 2 exp(−bn /18) + 0.02α + 4 exp (−3bn /3040) + 2/p2
< 12/p + 0.02α + 6 exp (−3bn /3040) .

>π
> π = T + T , we have proved that (58) holds with probability at least 1 −
e A − ξbA
Since ξbA
1
2
A
12/p − 0.02α − 6 exp (−3bn /3040). By recalling (59) and (60), we complete the proof.
>
b W = b−1 P
Proof of Lemma 13. Let δ = π̆ − π and Σ
n
i∈H4 Wi Wi . Let J0 = supp(π). Define B to be
the event that π satisfies the constraint in (15) and κ(s) ≥ 0.24(1 − τ )2 M −1 , where κ(s) is defined
in Lemma 10 and τ ∈ (0, 1) is a constant to be determined later.
On the event B, we have that kπ̆k1 ≤ kπk1 , which means kπ + δJ0 k1 + kδJ0c k1 ≤ kπk1 . Hence,
on the event B,
kδJ0c k1 ≤ kδJ0 k1 .
(64)
P
P
−1
b
Also observe that on the event B, kb−1
n
i∈H4 Wi Zi − ΣW πk∞ ≤ λπ /4 and kbn
i∈H4 Wi Zi −
b
ΣW π̆k∞ ≤ λπ /4, which means
b ∞ ≤ λπ /2.
kΣδk

Therefore, on the event B,

b ≤ kδk1 kΣ
b W δk∞ ≤ 0.5λπ kδk1
δ > Σδ

(i)
√
= 0.5λπ (kδJ0 k1 + kδJ0c k1 ) ≤ λπ kδJ0 k1 ≤ λπ skδJ0 k2 ,

where (i) follows by (64).
b via the restricted eigenvalue condition. By (64),
On the other hand, we can lower bound δ > Σδ
we have that on the event B, kδJ0c k1 ≤ kδJ0 k1 ≤ 3kδJ0 k1 . Thus, we have that
b ≥ κ(s)kδJ k2 ≥ 0.24(1 − τ )2 M −1 kδJ k2 .
δ > Σδ
0 2
0 2
46

Now we combine the above two displays and obtain that on the event B,
√
M λπ s
kδJ0 k2 ≤
.
0.24(1 − τ )2
Therefore, (64) implies that on the event B,

√
kδk1 ≤ 2kδJ0 k1 ≤ 2 skδJ0 k2 ≤
Notice that by Lemmas 10 and 12,

2M λπ s
.
0.24(1 − τ )2

P(B) ≥ 1 − 14/p − 0.02α − 6 exp (−3bn /3040)

− 2 exp(−M −2 bn /44) − 4 exp(−τ 2 bn /570).

Hence, the desired result follows by choosing τ = 3/4.

References
Arias-Castro, E., Candès, E. J., and Plan, Y. (2011). Global testing under sparse alternatives: Anova,
multiple comparisons and the higher criticism. The Annals of Statistics, 39(5):2533–2556.
Belloni, A., Chernozhukov, V., and Hansen, C. (2014a). Inference on treatment effects after selection
among high-dimensional controls. The Review of Economic Studies, 81(2):608–650.
Belloni, A., Chernozhukov, V., and Kato, K. (2014b). Uniform post-selection inference for least
absolute deviation regression and other z-estimation problems. Biometrika, 102(1):77–94.
Bickel, P. J. and Levina, E. (2008). Regularized estimation of large covariance matrices. The Annals
of Statistics, pages 199–227.
Bickel, P. J., Ritov, Y., and Tsybakov, A. B. (2009). Simultaneous analysis of lasso and dantzig selector.
The Annals of Statistics, 37(4):1705–1732.
Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration inequalities: A nonasymptotic theory
of independence. Oxford university press.
Bühlmann, P. (2013).
19(4):1212–1242.

Statistical significance in high-dimensional linear models.

Bernoulli,

Bühlmann, P. and Van De Geer, S. (2011). Statistics for high-dimensional data: methods, theory and
applications. Springer Science & Business Media.
Bühlmannn, P. (2006).
34(2):559–583.

Boosting for high-dimensional linear models.

The Annals of Statistics,

Bunea, F., She, Y., and Wegkamp, M. H. (2011). Optimal selection of reduced rank estimators of
high-dimensional matrices. The Annals of Statistics, 39(2):1282–1309.
Cai, T. T. and Guo, Z. (2016). Accuracy assessment for high-dimensional linear regression. arXiv
preprint arXiv:1603.03474.
47

Cai, T. T. and Guo, Z. (2017). Confidence intervals for high-dimensional linear regression: Minimax
rates and adaptivity. The Annals of Statistics, 45(2):615–646.
Cai, T. T. and Low, M. G. (2004). An adaptation theory for nonparametric confidence intervals. The
Annals of Statistics, 32(5):1805–1840.
Cai, T. T. and Low, M. G. (2006a). Adaptive confidence balls. The Annals of Statistics, 34(1):202–228.
Cai, T. T. and Low, M. G. (2006b). Optimal adaptive estimation of a quadratic functional. The Annals
of Statistics, 34(5):2298–2325.
Collier, O., Comminges, L., Tsybakov, A. B., et al. (2017). Minimax estimation of linear and quadratic
functionals on sparsity classes. The Annals of Statistics, 45(3):923–958.
Fan, J., Fan, Y., and Lv, J. (2008). High dimensional covariance matrix estimation using a factor
model. Journal of Econometrics, 147(1):186–197.
Fan, J. and Li, R. (2001). Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 96(456):1348–1360.
Fan, J., Liao, Y., and Mincheva, M. (2013). Large covariance estimation by thresholding principal
orthogonal complements. Journal of the Royal Statistical Society: Series B (Statistical Methodology),
75(4):603–680.
Genovese, C. and Wasserman, L. (2008). Adaptive confidence bands. The Annals of Statistics,
36(2):875–905.
Goeman, J. J., Van De Geer, S. A., and Van Houwelingen, H. C. (2006). Testing against a high
dimensional alternative. Journal of the Royal Statistical Society: Series B (Statistical Methodology),
68(3):477–493.
Hoffmann, M. and Nickl, R. (2011). On adaptive inference and confidence bands. The Annals of
Statistics, 39(5):2383–2409.
Ingster, Y. I., Tsybakov, A. B., and Verzelen, N. (2010). Detection boundary in sparse regression.
Electronic Journal of Statistics, 4:1476–1526.
Janson, L., Barber, R. F., and Candes, E. (2017). Eigenprism: inference for high dimensional signalto-noise ratios. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79(4):1037–
1065.
Javanmard, A. and Montanari, A. (2014). Confidence intervals and hypothesis testing for highdimensional regression. The Journal of Machine Learning Research, 15(1):2869–2909.
Javanmard, A. and Montanari, A. (2017). De-biasing the lasso: Optimal sample size for gaussian
designs. to appear in the Annals of Statistics.
Laurent, B. and Massart, P. (2000). Adaptive estimation of a quadratic functional by model selection.
The Annals of Statistics, 28(5):1302–1338.

48

Lehmann, E. L. and Romano, J. P. (2006). Testing statistical hypotheses. springer.
Meinshausen, N. and Bühlmann, P. (2006). High-dimensional graphs and variable selection with
the lasso. The Annals of Statistics, 34(3):1436–1462.
Negahban, S., Yu, B., Wainwright, M. J., and Ravikumar, P. K. (2009). A unified framework for highdimensional analysis of m-estimators with decomposable regularizers. In Advances in Neural
Information Processing Systems, pages 1348–1356.
Nickl, R. and van de Geer, S. (2013). Confidence sets in sparse regression. The Annals of Statistics,
41(6):2852–2876.
Raskutti, G., Wainwright, M. J., and Yu, B. (2011). Minimax rates of estimation for high-dimensional
linear regression over lq -balls. IEEE transactions on information theory, 57(10):6976–6994.
Ravikumar, P., Wainwright, M. J., and Lafferty, J. D. (2010). High-dimensional ising model selection
using l1 -regularized logistic regression. The Annals of Statistics, 38(3):1287–1319.
Rigollet, P. and Tsybakov, A. (2011). Exponential screening and optimal rates of sparse estimation.
The Annals of Statistics, 39(2):731–771.
Robins, J. and Van Der Vaart, A. (2006). Adaptive nonparametric confidence sets. The Annals of
Statistics, 34(1):229–253.
Rudelson, M. and Zhou, S. (2013). Reconstruction from anisotropic random measurements. IEEE
Transactions on Information Theory, 59(6):3434–3447.
Shah, R. D. and Bühlmann, P. (2017). Goodness-of-fit tests for high dimensional linear models.
Journal of the Royal Statistical Society: Series B (Statistical Methodology).
Soltanolkotabi, M., Elhamifar, E., and Candes, E. J. (2014). Robust subspace clustering. The Annals
of Statistics, 42(2):669–699.
Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical
Society. Series B (Methodological), 58(1):267–288.
Van de Geer, S., Bühlmann, P., Ritov, Y., and Dezeure, R. (2014). On asymptotically optimal confidence regions and tests for high-dimensional models. The Annals of Statistics, 42(3):1166–1202.
Van der Vaart, A. W. (2000). Asymptotic statistics, volume 3. Cambridge university press.
Verzelen, N. (2012). Minimax risks for sparse regressions: Ultra-high dimensional phenomenons.
Electronic Journal of Statistics, 6:38–90.
Verzelen, N. and Gassiat, E. (2016). Adaptive estimation of high-dimensional signal-to-noise ratios.
arXiv preprint arXiv:1602.08006.
Wainwright, M. J. (2009). Information-theoretic limits on sparsity recovery in the high-dimensional
and noisy setting. IEEE Transactions on Information Theory, 55(12):5728–5741.

49

Wainwright, M. J., Lafferty, J. D., and Ravikumar, P. K. (2007). High-dimensional graphical model
selection using l1 -regularized logistic regression. In Advances in neural information processing systems, pages 1465–1472.
Witten, D. M. and Tibshirani, R. (2010). A framework for feature selection in clustering. Journal of
the American Statistical Association, 105(490):713–726.
Zhang, C.-H. and Zhang, S. S. (2014). 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.
Zhu, Y. and Bradic, J. (2017a). Linear hypothesis testing in dense high-dimensional linear models.
Journal of the American Statistical Association, 0(just announced):0–0.
Zhu, Y. and Bradic, J. (2017b). Significance testing in non-sparse high-dimensional linear models.
ArXiv e-prints.

50

