arXiv:1510.08986v2 [] 23 Jun 2016

A Unified Theory of Confidence Regions and Testing for
High Dimensional Estimating Equations
Matey Neykov∗

Yang Ning∗

Jun S. Liu†

Han Liu∗

Abstract
We propose a new inferential framework for constructing confidence regions and
testing hypotheses in statistical models specified by a system of high dimensional estimating equations. We construct an influence function by projecting the fitted estimating equations to a sparse direction obtained by solving a large-scale linear program.
Our main theoretical contribution is to establish a unified Z-estimation theory of confidence regions for high dimensional problems. Different from existing methods, all of
which require the specification of the likelihood or pseudo-likelihood, our framework
is likelihood-free. As a result, our approach provides valid inference for a broad class
of high dimensional constrained estimating equation problems, which are not covered
by existing methods. Such examples include, noisy compressed sensing, instrumental variable regression, undirected graphical models, discriminant analysis and vector
autoregressive models. We present detailed theoretical results for all these examples.
Finally, we conduct thorough numerical simulations, and a real dataset analysis to back
up the developed theoretical results.

Keywords: Post-regularization inference, Estimating equations, Confidence regions, Hypothesis tests, Dantzig selector, Instrumental variables, Graphical models, Discriminant
analysis, Vector autoregressive models.

1

Introduction

Let us observe a sample of n, q-dimensional random vectors {Zi }ni=1 . Denote with Z the
n × q data matrix obtained by stacking all the vectors Zi . Let t(Z, β) : Rn×q × Rd 7→ Rd
be an estimating equation (Godambe, 1991) for a d-dimensional unknown parameter β, and
∗

Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ
08544; e-mail: {mneykov,yning,hanliu}@princeton.edu
†
Department of Statistics, Harvard University, Cambridge, MA 02138, USA; e-mail:
jliu@stat.harvard.edu

1

further let Et (β) = limn→∞ Et(Z, β) denote the limiting expected value of the estimating
equation t(Z, β) as n → ∞. As an example given n i.i.d. observations Zi and an equation
P
h, this reduces to the classical Z-estimation setup t(Z, β) = n−1 ni=1 h(Zi , β) and Et (β) =
Eh(Z, β). For the purpose of parameter estimation, it is usually assumed that the estimating
equation is unbiased in the sense that the true value β ∗ is the unique solution to Et (β) = 0.
When the dimension d is fixed and much smaller than the sample size n, inference on
β ∗ can be obtained by solving the estimating equation t(Z, β) = 0, and the asymptotic
properties follow from the classical Z-estimation theory (Van der Vaart, 2000). However,
when d > n, directly solving t(Z, β) = 0 is an ill-posed problem. To avoid this problem, a
popular approach is to impose the sparsity assumption on β ∗ , which motivates constrained
Z-estimators in the following generic form (Cai et al., 2014):
βb = argmin kβk1 , subject to kt(Z, β)k∞ ≤ λ,

(1.1)

where λ is a regularization parameter.
Assume that we can partition β as (θ, γ T )T , where θ is a univariate parameter of interest
bγ
b T )T and
and γ is a (d − 1)-dimensional nuisance parameter. Similarly, we denote βb = (θ,
β ∗ = (θ∗ , γ ∗T )T . The goal of this paper is to develop a general estimating equation based
framework to obtain valid confidence regions for θ∗ under the regime that d is much larger
than n. The proposed framework has a large number of applications. For instance, given a
convex and smooth loss function (or negative log-likelihood) ` : Rq ×Rd 7→ R, with i.i.d. data
Zi , the inference on β can be conducted based on the estimating equation (or score function)
P
i ,β)
. Hence, inference on many high dimensional problems with
t(Z, β) = n−1 ni=1 ∂`(Z
∂β
specifications of the loss function or the likelihood can be addressed through our framework.
More importantly, the estimating equation method has an advantage over likelihood methods
in that it usually only requires the specification of a few moment conditions rather than the
entire probability distribution (Godambe, 1991). To see the advantage of our framework, we
consider the following examples, which are naturally handled by estimating equations.

1.1

Examples

Linear Regression via Dantzig Selector (Candes and Tao, 2007). Assume that
a linear model (also referred to as noisy compressed sensing) is specified by the following
moment condition E(Y | X) = X T β ∗ . Let X ∈ Rn×d be the design matrix stacking the i.i.d.
covariates {Xi }ni=1 and Y ∈ Rn be the response vector with independent entries Yi . Given
the moment condition, we can easily construct the estimating equation as t((Y , X), β) =
n−1 XT (Xβ −Y ) and Et (β) = Et((Y , X), β). In addition, Et (β) has the true value β ∗ as its
unique root, provided that the second moment matrix ΣX := n−1 EXT X is positive definite.
In the high dimensional setting, Candes and Tao (2007) estimated β by the following Dantzig
selector,
βb = argmin kβk1 , such that kn−1 XT (Xβ − Y )k∞ ≤ λ.
2

Instrumental Variables Regression (IVR). Similarly to the previous example, consider
the linear model Y = X T β ∗ + ε. In many economic applications, it is not always reasonable
to believe that the error and the design variables are uncorrelated, i.e., E[Xε] = 0, which
is a key condition ensuring the unbiasedness of the estimating equation and consequently
b In such cases one may use a set of instrumental
the consistency of the Dantzig selector β.
d
variables W ∈ R which are correlated with X but satisfy E[W ε] = 0 and E[ε2 | W ] = σ 2 .
Let X, W ∈ Rn×d be the design matrix and instrumental variable matrix stacking the i.i.d.
covariates {Xi }ni=1 and instrumental variables {Wi }ni=1 respectively, and Y ∈ Rn be the
response vector with independent entries Yi . Using the instrumental variables, one can
construct unbiased estimating equations t((Y , X, W), β) = n−1 WT (Xβ − Y ) and Et (β) =
Et((Y , X, W), β). In addition, Et (β) has β ∗ as its unique root, provided that the second
moment matrix ΣW X := n−1 EWT X is of full rank. Inspired by Gautier and Tsybakov
b
(2011), we consider the following estimator β:
βb = argmin kβk1 , such that kn−1 WT (Xβ − Y )k∞ ≤ λ.
Graphical Models via CLIME/SKEPTIC (Cai et al., 2011; Liu et al., 2012b). Let
X1 , ..., Xn be i.i.d. copies of X ∈ Rd with E(X) = 0 and Cov(X) = ΣX . It is well known
that in the case when X are Gaussian, the precision matrix Ω∗ = (ΣX )−1 induces a graph,
encoding conditional independencies of the variables X. More generally, this observation
can be extended to transelliptical distributions (Liu et al., 2012b).
P
Let Σn = n−1 i=1 Xi⊗2 be the sample covariance of X1 , ..., Xn . Based on the second
moment condition ΣX Ω∗ = Id , Cai et al. (2011) proposed the CLIME estimator of Ω∗ :
b = argmin kΩk1 , subject to kΣn Ω − Id kmax ≤ λ.
Ω

(1.2)

In this case we have t(X, Ω) = Σn Ω − Id , and Et (Ω) = ΣX Ω − Id . Under the more
general setting of transelliptical graphical models, Liu et al. (2012b) substituted the sample
covariance Σn with a non-parametric estimate based on Kendall’s tau (see Remark 1). Doing
so breaks down the i.i.d. decomposition of the estimating equation described above, but
continues to belong to our formulation (1.1).
Discriminant Analysis (Cai and Liu, 2011). Let X and Y be d-dimensional random
vectors, coming from two populations with different means µ1 = E(X), µ2 = E(Y ), and a
common covariance matrix Σ = Cov(X) = Cov(Y ). Given some training samples, we are
interested in classifying a new observation O into population 1 or population 2. It is well
known (e.g. see Mardia et al. (1979) Theorem 11.2.1) that, under certain conditions, the
Bayes classification rule takes the form:
ψ(O) = I((O − µ)T Ωδ > 0),
where I(·) is an indicator function, µ = (µ1 +µ2 )/2, δ = (µ1 −µ2 ) and Ω = Σ−1 . Specifically,
the observation O is classified into population 1 if and only if ψ(O) = 1.
3

To implement ψ(O) in practice, one has to estimate the unknown parameters µ1 , µ2 and
Ω. Assume we observe n1 and n2 training samples from population 1 and population 2
denoted by X1 , . . . , Xn1 ∈ Rd and Y1 , . . . , Yn2 ∈ Rd . We assume that
Xi = µ1 + Ui , i = 1, . . . , n1 ,

and Yi = µ2 + Ui+n1 , i = 1, . . . , n2 ,

(1.3)

where Ui are i.i.d. copies of U = (U1 , . . . , Ud )T , which satisfies E(U ) = 0 and Cov(U ) =
P 1
P 2
Xi and Ȳ = n12 ni=1
Yi , and the sample
Σ. Define the sample means as X̄ = n11 ni=1
P
P
n1
n2
⊗2
⊗2
bX = 1
bY = 1
covariances as Σ
and Σ
i=1 (Xi − X̄)
i=1 (Yi − Ȳ ) . Furthermore let
n1
n2
b n = n1 Σ
b X + n2 Σ
b Y be the weighted average of Σ
b X and Σ
bY .
Σ
n
n
b −1 , since
In the high dimensional setting with d  n, we cannot directly estimate Ω by Σ
n
the sample covariance is not invertible. Noting that the classification rule solely depends
on β ∗ = Ωδ, Cai and Liu (2011) proposed a direct approach to estimate β ∗ , rather than
estimating Ω and δ separately. Their estimated classification rule is as follows:
b
ψ(O)
= I((O − (X̄ + Ȳ )/2)T βb > 0), where
b n β − (X̄ − Ȳ )k∞ ≤ λ.
βb = argmin kβk1 , subject to kΣ

(1.4)

Clearly the latter formulation constitutes a high dimensional estimating equation as in (1.1),
1
2
b n β − (X̄ − Ȳ ) and Et (β) = Σβ − (µ1 − µ2 ).
with t(({Xi }ni=1
, {Yi }ni=1
), β) = Σ
Vector Autoregressive Models (Han et al., 2014). Let {Xt }∞
t=−∞ be a stationary
d
sequence of mean 0 random vectors in R with covariance matrix Σ. The sequence {Xt }∞
t=−∞
is said to follow a lag-1 autoregressive model if
Xt = AT Xt−1 + Wt ,

t ∈ Z := {..., −1, 0, 1, ....},

where A is a d × d transition matrix, and the noise vectors Wt are i.i.d. with Wt ∼
N (0, Ψ) and independent of the history {Xs }s<t . Under the additional assumption that
det(Id − AT z) 6= 0 for all z ∈ C with |z| ≤ 1, it can be shown that Ψ can be selected so
that the process is stationary, i.e. for all t: Xt ∼ N (0, Σ). Let Σi := Cov(X0 , Xi ), where
Σ0 := Σ. A simple calculation under the lag-1 autoregressive model leads to the following
Yule-Walker Equation: Σi := Σ0 Ai , for any i ∈ N. A special case of the above equation
with i = 1 yields that:
A = Σ−1
(1.5)
0 Σ1 .
Assume that the data (X1 , ..., XT ) follow the lag-1 autoregressive model. By the equation
(1.5), Han et al. (2014) proposed the following estimator of A in the high dimensional setting:
X
b = argmin
A
|Mjk |, subject to kS0 M − S1 kmax ≤ λ,
(1.6)
M∈Rd×d 1≤j,k≤d

P
PT −1
1
T
where λ > 0 is a tunning parameter, S0 = 1/T Tt=1 Xt⊗2 and S1 = T −1
t=1 Xt Xt+1 are
estimators of Σ0 and Σ1 respectively, and T is the number of observations. In this case we
have that t({Xt }Tt=1 , M) = S0 M − S1 , and Et (M) = Σ0 M − Σ1 .
4

1.2

Related Methods

Having explored a few examples falling into the estimating equation framework (1.1), we
move on to outline some related works on high dimensional inference. Recently, significant
progress has been made towards understanding the post-regularization inference for the
LASSO estimator in the linear and generalized linear models. For instance, Lockhart et al.
(2014); Taylor et al. (2014); Lee et al. (2013) suggested conditional tests based on covariates
which have been selected by the LASSO. We stress the fact that this type of tests are of
fundamentally different nature compared to our work. Another important class of methods is
based on the bias correction of L1 or nonconvex regularized estimators. In particular, Belloni
et al. (2012, 2013); Zhang and Zhang (2014); Javanmard and Montanari (2013); van de Geer
et al. (2014) proposed a double selection estimator, low dimension projection estimator,
debiasing and desparsifying correction methods, respectively, for constructing confidence
intervals in high dimensional models with the L1 penalty. Recently, Ning and Liu (2014b,a)
proposed a decorrelated score test in a likelihood based framework. The difference between
our method and this class of methods will be discussed in more details in the next section.
A different score related approach is considered by Voorman et al. (2014), which is testing
a null hypothesis depending on the tuning parameter, and hence differs from our work. For
the nonconvex penalty, under the oracle properties, the asymptotic normality property of
the estimators is established by Fan and Lv (2011), which requires strong conditions, such
as the minimal signal condition. In contrast, our work does not rely on oracle properties or
variable selection consistency. P-values and confidence intervals based on sample splitting
and subsampling are suggested by Meinshausen et al. (2009); Meinshausen and Bühlmann
(2010); Shah and Samworth (2013); Wasserman and Roeder (2009). However, the sample
splitting procedures may lead to certain efficiency loss. In a recent paper by Lu et al. (2015),
the authors developed a new inferential method based on a variational inequality technique
for the LASSO procedure which provably produces valid confidence regions. In contrast to
our work their method needs the dimension d to be fixed, and it may not be applicable to
the inference problem based on the formulation (1.1).

1.3

Contributions

Our first contribution is to propose a new procedure for high dimensional inference in the
estimating equation framework. In order to construct confidence regions, our method is to
project the general estimating equation onto a certain sparse direction, which can be easily
estimated by solving a large-scale linear program. Thus, the proposed inferential procedure
is a general methodology and can be directly applied to many inference problems, including
all aforementioned examples. Although some of the works discussed in Section 1.2 also used
a projection idea, our method is different from previous works in that it directly targets the
influence function of the estimating equation. For instance, in Ning and Liu (2014b,a),
P
the decorrelated score function is defined as n−1 ni=1 [∂`(Zi , β)/∂θ − wT ∂`(Zi , β)/∂γ],
5

where `(Zi , β) is the log-likelihood for data Zi , and wT ∂`(Zi , β)/∂γ is the sparse projection of the θ-score function ∂`(Zi , β)/∂θ to the (d − 1)-dimensional nuisance score space
span{∂`(Zi , β)/∂γ}. While the score functions can be treated as a special case of estimating
equation, such a construction cannot be directly extended to general estimating equations.
The reason is that it remains unclear how to disentangle the estimating equation for the parameter of interest and the nuisance estimating equation space, and therefore the projection
conducted by Ning and Liu (2014b,a) is not well defined. To address this challenge, motivated from the classical influence function representation, we propose a different projection
approach, which directly estimates the influence function of the equation.
Our second contribution is to establish a unified Z-estimation theory of confidence intervals. In particular, we construct a Z-estimator θe that is consistent and asymptotically normal, and its asymptotic variance can be consistently estimated. Furthermore, the pointwise
asymptotic normality results can be strengthened by showing that θe is uniformly asymptotically normal for β ∗ belonging to a certain parameter space (deferred to the Supplementary
Material). Moreover, owing to the flexibility of the estimating equations framework, we are
able to push the theory through for non i.i.d. data, relaxing the assumptions made in most
existing work. In terms of relative efficiency, when the estimating equation corresponds to
the score function, our estimator θe is semiparametrically efficient. The theoretical properties
of hypothesis tests have also been established, but for space limitations the proofs will be
omitted and can be provided by the authors upon request.
Our third contribution is to apply the proposed framework to establish theoretical results for the previous motivating examples including the noisy compressed sensing with
moment condition, instrumental variable regression, graphical models, transelliptical graphical models, linear discriminant analysis and vector autoregressive models. To the best of
our knowledge, many of the aforementioned problems (e.g. instrumental variables regression,
linear discriminant analysis and vector autoregressive models) have not been equipped with
any inferential procedures.
Finally, we further emphasize the difference between our method and the class of methods
based on the bias correction of regularized estimators. Compared to these methods in Zhang
and Zhang (2014); Javanmard and Montanari (2013); van de Geer et al. (2014); Ning and
Liu (2014a), our framework has the following three advantages. First, all of the above propositions rely on the existence of a likelihood, or more generally a loss function. In contrast,
our framework directly handles the estimating equations and is likelihood-free, enabling us
to perform inference in many examples (e.g., the motivating examples discussed in Section
1.1) where the likelihood or the loss function is unavailable or difficult to formulate. For
instance in the instrumental variable regression it is not clear how to devise a loss function,
while the problem naturally falls into the realm of estimating equations. This leads to different methodological development from the previous work, which will be explained later in
details. Second, some of the existing work such as Zhang and Zhang (2014); Javanmard and
Montanari (2013); van de Geer et al. (2014) is only tailored for the linear and generalized

6

linear models. In contrast, our framework covers much broader class of statistical models
specified by estimating equations, such as linear discriminant analysis and vector autoregressive models whose inferential properties have not been studied before. Third, our framework
can handle dependent data, which is more flexible than these existing works all of which
require the data to be independent.

1.4

Organization of the Paper

The paper is organized as follows. In Section 2, we propose our generic inferential procedure for high dimensional estimating equations, and layout the foundations of the general
theoretical framework. In Section 3, we apply the general theory to study the motivating examples including the Dantzig Selector, instrumental variables regression, graphical models,
discriminant analysis and autoregressive models. Numerical studies and a real data analysis
are presented in Section 4, and a discussion is provided in Section 5.

1.5

Notation

The following notations are used throughout the paper. For a vector v = (v1 , . . . , vd )T ∈ Rd ,
P
let kvkq = ( di=1 viq )1/q , 1 ≤ q < ∞, kvk0 = |supp(v)|, where supp(v) = {j : vj 6= 0}, and
|A| denotes the cardinality of a set A. Furthermore let kvk∞ = maxi |vi | and v⊗2 = vvT .
For a matrix M denote with M∗j and Mj∗ the j th column and row of M correspondingly.
Moreover, let kMkmax = maxij |Mij |, kMkp = maxkvkp =1 kMvkp for p ≥ 1. If M is positive
semidefinite let λmax (M) and λmin (M) denote the largest and smallest eigenvalues correspondingly. For a set S ⊂ {1, . . . d} let vS = {vj : j ∈ S} and S c be the complement of
S. We denote with φ, Φ, Φ the pdf, cdf and tail probability of a standard normal random
variable correspondingly. Furthermore, we will use
to denote weak convergence.
For a random variable X, we define its ψ` norm for any ` ≥ 1 as:
kXkψ` = sup p−1/` (E|X|p )1/p .

(1.7)

p≥1

In the present paper we mainly use the ψ1 and ψ2 norms. Random variables with bounded
ψ1 and ψ2 norms are called sub-exponential and sub-Gaussian correspondingly (Vershynin,
2010) . It can be shown that a random variable is sub-exponential if there exists a constant
K1 > 0 such that P(|X| > t) ≤ exp(1 − t/K1 ) for all t ≥ 0. Similarly, a random variable is
sub-Gaussian, if there exists a K2 > 0 such that P(|X| > t) ≤ exp(1 − t2 /K22 ) for all t ≥ 0.
Finally, for two sequences of positive numbers {an } and {bn } we will write an  bn if there
exist positive constants c, C > 0 such that lim supn an /bn ≤ C and lim inf n an /bn ≥ c.

7

2

High Dimensional Estimating Equations

In this section we present the intuition behind the construction of our projection, and formulate the main results of our theory. Recall that β = (θ, γ T )T ∈ Rd , where θ is a univariate
parameter of interest and γ is a (d − 1)-dimensional nuisance parameter. We are interested
in constructing a confidence interval for θ. In fact our results can be extended in a simple
manner to cases with θ being a finite and fixed-dimensional vector, but we do not pursue
this development in the present manuscript. Throughout the paper, we assume without loss
of generality that θ is the first component of β.
In the conventional framework, where the dimension d is fixed and less than the sample
size n, one can estimate the d-dimensional parameter β by the Z-estimator, which is the
root (assumed to exist) of the following system of d equations (Godambe, 1991),
t(Z, β) = 0.

(2.1)

Under certain regularity conditions, the Z-estimator is consistent, and one has the following
b where βb = (θ,
bγ
b T )T is the solution to (2.1)
influence function expansion of the parameter θ,
(Newey and McFadden, 1994; Van der Vaart, 2000):
√
√
∗
n(θb − θ∗ ) = − n[ET (β ∗ )]−1
(2.2)
1∗ t(Z, β ) + op (1).
In the preceding display, we assume ET (β) := limn→∞ ET(Z, β) is invertible, where T(Z, β) :=
∂
t(Z, β). It is noteworthy to observe that in contrast to the Hessian matrix of the log∂β
likelihood (or more generally any smooth loss function), the Jacobian matrix T(Z, β) need
not be symmetric in general (refer to the IVR model for an example). Under further conditions, the right hand side of (2.2) converges to a normal distribution, hence guaranteeing
b
the asymptotic normality of the estimator θ.
In the case when d > n, the estimating equation (2.1) is ill-posed as one has more
parameters than samples, resulting in multiple solutions for β. To deal with such situations,
under the sparsity assumption on β ∗ , we solve the constrained optimization program (1.1).
b and θb in particular,
Due to the constraint in (1.1), the limiting distribution of the estimator β,
becomes intractable as expansion (2.2) is no longer valid. Hence, instead of focusing on the
left hand side of (2.2), in order to construct a theoretically tractable estimator of θ we consider
a direct approach by estimating the influence function on the right hand side. Emulating
expression (2.2), we propose the following projected estimating equation along the direction
b,
v
b
bT t(Z, β),
S(β)
=v
b is defined as the solution to the optimization problem:
where v
b = argmin kvk1 such that
v

b − e1
vT T(Z, β)

∞

≤ λ0 .

(2.3)

In (2.3) λ0 is an additional tuning parameter, and e1 is a d-dimensional row vector (1, 0, . . . , 0),
bT is a natural
where the position of 1 corresponds to that of θ among β. It is easily seen that v
8

estimator of v∗T := [ET (β ∗ )]−1
1∗ in the high dimensional setting, which is an essential term in
b
the right hand of (2.2). Thus, S(β)
can be viewed as an estimate of the influence function
for estimating θ in high dimensions. To better understand our method, consider the linear
model example. In this case, we have
b
bT XT (Xβ − Y ),
S(β)
= n−1 v
where
b = argmin kvk1 , such that kvT Σn − e1 k∞ ≤ λ0 .
v
b corresponds to the first column of the CLIME estimator for the inverse
We can see that v
covariance matrix of Xi .
b does not depend on knowing which is the
We emphasize that the construction of v
estimating equation for θ and which is the nuisance estimating equation space, and thus
the projection is different from the decorrelated score method in Ning and Liu (2014a). In
fact, the lack of a valid loss (or likelihood) function corresponding to the general estimating
equations is the main difficulty for applying the existing likelihood based inference methods.
bγ
b T )T . By plugging in the estimator γ
b , we obtain the projected
Recall that βb = (θ,
b γ
b ) for the parameter of interest θ. Similar to the classical estimating
estimating equation S(θ,
e which is the root of S(θ,
b γ
b) =
equation approach, we propose to estimate θ by a Z-estimator θ,
0. In the following section we lay out the foundations of a unified theory guaranteeing that
the estimator θe is asymptotically normal.

2.1

A General Theoretical Framework

In this section we provide generic sufficient conditions which guarantee the existence and
e which is the root of S(θ,
b γ
b ) = 0. Due to space limitations, we
asymptotic normality of θ,
only present results on the confidence intervals, and the results on uniformly valid confidence
intervals are deferred to the Supplementary Material. The results and proofs on hypothesis
testing can be obtained from the authors upon request.
We assume that t(Z, β) is twice differentiable in β. Recall that we further require β ∗
to be the unique solution to Et (β) = 0, where Et (β) = limn→∞ Et(Z, β). For any β we let
S(β) := v∗T t(Z, β), where v∗T := [ET (β ∗ )]−1
1∗ . Let Pβ be the probability measure under the
parameter β. We use the shorthand notation P∗ = Pβ∗ , to indicate the measure under the
true parameter β ∗ . For any vector β = (θ, γ T )T , we use the following shorthand notation
βθ̌ = (θ̌, γ T )T to indicate that θ is replaced by θ̌. Before we proceed to define our abstract
assumptions and present the results, we first motivate them and give an informal description
below.
2.1.1

Motivation and Informal Description

Throughout this section we build our theory based on the premisses that the estimators βb
b can be shown to be L1 consistent, i.e. kβb − β ∗ k1 = op (1) and kb
and v
v − v∗ k1 = op (1).
9

This is expected to hold for estimators solving programs (1.1) and (2.3) owing to the fact
that both programs aim to minimize the L1 norm of the parameters. The L1 consistency
(see (2.8)) is central in what follows. Under this presumption, the key idea in our theory is
b γ
b βbθ ) about the
b ) = S(
the successful control of the deviations of the “plug-in” equation S(θ,
b βbθ ) =
equation S(θ, γ ∗ ) = S(βθ∗ ) (recall S(βθ∗ ) := v∗T t(Z, βθ∗ )), i.e. we aim to establish S(
∗
S(βθ ) + op (1). By the mean value theorem
b βbθ ) = S(β ∗ ) + v
bT T(Z, βeν )(βbθ − βθ∗ ) + (b
S(
v − v∗ )T t(Z, βθ∗ ),
θ

(2.4)

where βeν is a point on the line segment joining βbθ with βθ∗ . Owing to the L1 consistency
b (2.4) can indeed be rewritten in the form S(
b βbθ ) = S(β ∗ ) + op (1), provided
b and β,
of v
θ
that kb
vT T(Z, βeν )k∞ = Op (1) and kt(Z, βθ∗ )k∞ = Op (1). A sufficient and also sensible
condition for these bounds, is to desire kt(Z, βθ∗ ) − Et (βθ∗ )k∞ = op (1), and kb
vT T(Z, βeν ) −
v∗T ET (βθ∗ )k∞ = op (1), where Et (βθ∗ ) and ET (βθ∗ ) are the limiting expected values of t(Z, βθ∗ )
bT T(Z, βeν ), respectively. It is therefore rational to believe that the latter L∞ -norms
and v
√
converge to 0; see Assumption 1. Furthermore, to show n consistency of the equations one
needs to require an additional scaling condition on the latter convergence rates; see (2.11).
2.1.2

Main Results

We now formalize our intuition above by requiring the following assumption.
Assumption 1 (Concentration). There exists a neighborhood Nθ∗ of θ∗ , such that for all
θ ∈ Nθ∗ :
lim P∗ (kt(Z, βθ∗ ) − Et (βθ∗ )k∞ ≤ r1 (n, θ)) = 1,

(2.5)

lim P (|v t(Z, βθ∗ ) − v∗T Et (βθ∗ )| ≤ r2 (n, θ)) = 1,


∗
T
∗T
∗
e
lim P
sup kb
v T(Z, βν ) − v ET (βθ )k∞ ≤ r3 (n, θ) = 1,

(2.6)

n→∞
∗
∗T

n→∞

n→∞

(2.7)

ν∈[0,1]

where βeν = ν βbθ +(1−ν)βθ∗ , supθ∈Nθ∗ max(r1 (n, θ), r2 (n, θ), r3 (n, θ)) = o(1), and the following
condition holds:
sup kEt (βθ∗ )k∞ < ∞,

θ∈Nθ∗

sup kv∗T [ET (βθ∗ )]−1 k∞ < ∞,

θ∈Nθ∗

where [A]−1 represents a submatrix of A with the 1st column removed.
Condition (2.5) means that the equation t(Z, βθ∗ ) concentrates on its limiting value Et (βθ∗ )
for any θ in a small neighborhood of θ∗ . Similarly, condition (2.6) implies that the projection
of the estimating equation on v∗ also concentrates on its limiting value locally around θ∗ ,
and is automatically implied by (2.5) when kv∗ k1 = O(1). Finally, condition (2.7) means
b concentrates on its limiting value
that the projection of the Jacobian matrix T(Z, βeν ) on v
∗T
∗
∗
v ET (βθ ) in a neighborhood of θ . These conditions are mild, and can be validated for all
examples we consider.
10

b satisfy
Assumption 2 (L1 Consistency). Let the estimators βb and v
lim P∗ (kβb − β ∗ k1 ≤ r4 (n)) = 1,

lim P∗ (kb
v − v∗ k1 ≤ r5 (n)) = 1,

n→∞

n→∞

(2.8)

where max(r4 (n), r5 (n)) = o(1).
As mentioned previously, (2.8) is expected to hold due to the formulations of (1.1) and
(2.3). In particular, (2.8) has been verified for all examples we consider. Assumptions 1 and
2 suffice to show the following consistency result.
b βbθ ) be continuous with a single
Theorem 1 (Consistency). Let the (stochastic) map θ 7→ S(
root θe or non-decreasing. Furthermore, suppose that for any  > 0,
v∗T [Et (βθ∗∗ − )]v∗T [Et (βθ∗∗ + )] < 0.

(2.9)

Under Assumptions 1 and 2 we have that
lim P∗ (|θe − θ∗ | > ) = 0.

n→∞

Condition (2.9) implies that the scalars v∗T [Et (βθ∗∗ − )] and v∗T [Et (βθ∗∗ + )] have opposite
signs for all  > 0, which in turn guarantees that θ∗ is a unique root of the map v∗T [Et (βθ∗ )].
b βbθ ) is unbiased. The condition (2.9) holds for
Hence under (2.9) the population equation S(
numerous examples and is also commonly used in the classical asymptotic theory; see Section
5 of Van der Vaart (2000). In fact, the conclusion of Theorem 1 remains valid if one solves
b βbe) = op (1). To establish the asymptotic
the equation approximately in the sense that S(
θ
e we require the following assumptions.
normality of θ,
Assumption 3 (CLT). Assume that for σ 2 = v∗T Σv∗ , it holds that
σ −1 n1/2 S(β ∗ )

N (0, 1),

where Σ = limn→∞ n Cov t(Z, β ∗ ), and assume that σ 2 ≥ C > 0 for some constant C.
Assumption 3 ensures that the right hand side of expansion (2.4) converges to a normal
distribution when scaled appropriately. This CLT condition is mild, and can typically be
verified via Lyapunov or Lindeberg conditions in cases when t(Z, β) can be decomposed into
a sum of i.i.d. observations. For some types of dependent data, Assumption 3 holds by
applying the martingale central limit theorem (e.g. autoregressive models). Thus, one of the
advantages of our framework is that we can handle dependent data, which are not covered
by the existing methods. We show such an example in Section 3.4.
Assumption 4 (Bounded Jacobian Derivative). Suppose there exists a constant γ > 0 such
that:

∂ 
vT
T(Z, (θ, γ T )T ) ∗1 ≤ ψ(Z),
(2.10)
∂θ
for any v and β satisfying kv − v∗ k1 < γ and kβ − β ∗ k1 < γ, where ψ : Rn×q 7→ R is an
integrable function with E∗ ψ(Z) < ∞.
11

∂
Inequality (2.10) is a technical condition ensuring that vT ∂θ
[T(Z, β)]∗1 is bounded by
an integrable function in a small neighborhood and hence does not behave too erratically,
so that the dominated convergence theorem can be applied. This is a standard condition,
which is also assumed in Theorem 5.41 of Van der Vaart (2000) to establish the asymptotic
normality of Z-estimator in the classical low dimensional regime. It is easily seen that this
condition is mild and holds for linear estimating equations.

Assumption 5 (Scaling). Assume the convergence rates in Assumptions 1 and 2 satisfy
n1/2 (r4 (n)r3 (n, θ∗ ) + r5 (n)r1 (n, θ∗ )) = o(1).

(2.11)

Assumption (2.11) ensures that the small terms on the right hand side of (2.4) continue to
√
be negligible, even after normalizing by n. This assumption requires that the consistency
and concentration rates in (2.8) and Assumption 1 are sufficiently sharp if one hopes to
e This condition can be verified in all of our examples.
establish the asymptotic normality of θ.
We are now in a position to state the main result of this section.
Theorem 2 (Asymptotic Normality). Assume the conditions from Theorem 1 and Assumptions 3, 4 and 5 hold. If σ
b2 is a consistent estimator of σ 2 , then for any t ∈ R, we have:
1/2
bn ≤ t) − Φ(t)| = 0, where U
bn = n (θe − θ∗ ).
lim |P∗ (U
n→∞
σ
b

Some generic sufficient conditions for the consistency of σ
b are shown in Proposition 2
in Section B.1 of the Supplementary Material. In our examples, we will develop consistent
estimates of the variance σ 2 case by case. Given a consistent estimator σ
b2 , Theorem 2 implies
that we can construct a (1 − α)% confidence interval of θ∗ in the following way


√
√ 
lim P∗ θ∗ ∈ θe − Φ−1 (1 − α/2)b
σ / n, θe + Φ−1 (1 − α/2)b
σ / n = 1 − α.
(2.12)
n→∞

We conclude this section by noting a property of our estimator θe in cases when the
P
estimating equation comes from a log-likelihood, i.e. t(Z, β) = n−1 ni=1 h(Zi , β) with
∂
h(Zi , β) being the gradient of the log-likelihood for Zi . Denote H(Z, β) = ∂β
h(Z, β).
∗
∗
∗T
According to the information identity −EH(Z, β ) = Cov h(Z, β ), we have v Σv∗ =
(Σ−1 )11 . In this case, the Z-estimator θe is efficient (Van der Vaart, 2000), because the
variance (Σ−1 )11 coincides with the inverse of the information bound for θ.

3

Implications of the General Theoretical Framework

In this section, we apply the general theory of Section 2.1 to the motivating examples we
listed in the introduction.

12

3.1

Linear model and Instrumental Variables Regression

In this section we consider the linear model via Dantzig Selector and the instrumental variables regression. As seen in the introduction, the instrumental variables regression can be
viewed as a generalization of the linear regression, by substituting W ≡ X. For simplicity,
we only present the results for the linear regression and defer the development of the inference
theory for instrumental variables regression to Appendix C of Supplementary Material.
Recall that β := (θ, γ), and let Σn = n−1 XT X be the empirical estimator of ΣX . Our
goal is to construct confidence intervals for the parameter θ. In the linear regression case,
b
we can easily show that S(β)
reduces to
b
bT XT (Xβ − Y ),
S(β)
= n−1 v
where
b = argmin kvk1 , subject to kvT Σn − e1 k∞ ≤ λ0 ,
v

(3.1)

T
is an estimator of v∗ = Σ−1
X e1 . We impose the following assumption.

Assumption 6. Assume that the error ε := Y − X T β ∗ and the predictor X are both
coordinate-wise sub-Gaussian, i.e.,
kεkψ2 := K < ∞,

kXj kψ2 := KX < ∞,

sup
j∈{1,...,d}

for some fixed constants K, KX > 0. Furthermore assume that the variance Var(ε) ≥ Cε > 0,
the random variables ε and X are independent, and the second moment matrix ΣX satisfies
λmin (ΣX ) ≥ δ > 0, where δ is some fixed constant.
bn = ∆
b −1 n1/2 (θe − θ∗ ), where θe is
To construct confidence intervals for θ, we consider U
b γ
b ) = 0, and
defined as the solution to S(θ,
b := v
b T Σn v
bn−1
∆

n
X

b 2,
(Yi − XiT β)

(3.2)

i=1

is an estimator of the asymptotic variance ∆ := v∗T ΣX v∗ Var(ε). In high dimensional
models, it is often reasonable to assume that the vectors v∗ and β ∗ are sparse. Let s and sv
denote the sparsity of β ∗ and v∗ correspondingly, i.e., kβ ∗ k0 = s and kv∗ k0 = sv . The next
bn in linear models.
corollary of the general Theorem 2 shows the asymptotic normality of U
To simplify the presentation of our result we will assume that kv∗ k1 is bounded, although
this is not needed in our proofs.
Corollary 1. Assume that Condition 6 holds, and
p
√
log d/n = o(1).
max(sv , s) log d/ n = o(1),
p
p
bn satisfies for any t ∈ R:
Then with λ  log d/n and λ0  log d/n, U
bn ≤ t) − Φ(t))| = 0.
lim |P∗ (U

n→∞

13

The proof of Corollary 1 can be found in Appendix F of the Supplementary Material.
The conditions in Corollary 1 agree with the existing conditions in Zhang and Zhang (2014);
van de Geer et al. (2014). In fact, under the additional assumption s3v /n = o(1), we can show
bn is uniformly asymptotically normal; see Remark 4 of the Supplementary Material.
that U
Finally, we comment that a similar asymptotic normality result under the instrumental
variables regression is shown in Corollary 5 of the Supplementary Material.

3.2

Graphical Models

We begin with introducing several assumptions which we need throughout the development.
First let ΣX satisfy λmin (ΣX ) ≥ δ > 0, where δ is some fixed constant. Similarly to Section
3.1 we assume that X is coordinate-wise sub-Gaussian, i.e.,
KX := max kXj kψ2 < ∞,

(3.3)

j∈{1,...,d}

for some fixed constant KX > 0. Our goal is to construct confidence intervals for a component
of Ω∗ , where Ω∗ = (ΣX )−1 . Without loss of generality, we focus on the parameter Ω∗1m for
some m ∈ {1, . . . , d}. When X are coming from a Gaussian distribution, the confidence
intervals for Ω∗1m provide uncertainty assessment on whether X1 is independent of Xm given
the rest of the variables.
There are a number of recent works considering the inferential problems for Gaussian
graphical models (Jankova and van de Geer, 2014; Chen et al., 2015; Ren et al., 2015; Liu,
2013) and Gaussian copula graphical models (Gu et al., 2015; Barber and Kolar, 2015).
Our framework differs from these existing procedures in the following two aspects. First,
our method is based on the estimating equations rather than the likelihood and (node-wise)
pseudo-likelihood. Second, we only require each component of X is sub-Gaussian, whereas
the majority of the existing methods require the data to be sampled from Gaussian or
Gaussian copula distributions.
Let β ∗ := Ω∗∗m , be the mth column of Ω∗ . Then, the CLIME estimator of β ∗ given by
(1.2) reduces to
βb = argmin kβk1 , subject to kΣn β − eTm k∞ ≤ λ,
where eTm is a unit column vector with 1 in the mth position and 0 otherwise. Phrasing
this problem in the terminology of Section 2.1, we can construct d estimating equations:
t(X, β) = Σn β − eTm . Let us decompose the vector β as β := (θ, γ T )T . Then the projected
estimating equation for θ is given by
b
bT (Σn β − eTm ),
S(β)
=v
where
b = argmin kvk1 , such that kvT Σn − e1 k∞ ≤ λ0 .
v
14

(3.4)

∗
b
b is an estimate of v∗ := (ΣX )−1
Here v
∗1 = Ω∗1 . Notice that, due to the symmetry of β and
0
b, if we take λ = λ , it suffices to simply solve the CLIME optimization (1.2) once in order
v
b as βb = Ω
b ∗m and v
b ∗1 . This pleasant consequence for CLIME shows
b β),
b=Ω
to evaluate S(
that in this special case the number of tuning parameters in the generic procedure described
in Section 2 can be reduced to 1, and hence the computation is simplified.
b γ
b ) = 0 has the following closed form expression:
The solution θe to the equation S(θ,

bT (Σn βb − eTm )
v
.
θe = θb −
bT Σn,∗1
v

(3.5)

e we impose the following assumption.
To establish the asymptotic normality of θ,
Assumption 7. There exists a constant αmin > 0 such that:
∆ ≥ αmin kβ ∗ k22 kv∗ k22 , where ∆ = Var(v∗T X ⊗2 β ∗ ).
We note that Assumption 7 is natural. For example when X ∼ N (0, ΣX ), Isserlis’
theorem yields that for any two vectors ξ and θ,
Var(ξ T X ⊗2 θ) = (ξ T ΣX ξ)(θ T ΣX θ) + (ξ T ΣX θ)2 ≥ λ2min (ΣX )kξk22 kθk22 ,
which clearly implies Assumption 7, if λ2min (ΣX ) is lower bounded by a constant.
Denote kβ ∗ k0 = s and kv∗ k0 = sv . To simplify the presentation of our result we will
assume that kv∗ k1 and kβ ∗ k1 are bounded quantities, although this is not needed in our
bn = ∆
b −1/2 n−1/2 (θe − θ∗ ),
proofs. The following corollary yields the asymptotic normality of U
P
n
⊗2
T
2
−1
b is an estimator of ∆.
b := n
v (Xi − Σn )β)
where ∆
i=1 (b
Corollary 2. Let Assumption 7 and (3.3) hold. Furthermore, assume that
max(s2v , s2 ) log d log(nd)/n = o(1),

∃ k > 2 : (sv s)k /nk−1 = o(1),

(3.6)

and p
Var((v∗T X ⊗2 β ∗ )2 ) p
= o(n), E(v∗T X ⊗2 β ∗ )2 = O(1). Let the tuning parameters be
0
λ  log d/n and λ  log d/n. Then for all t ∈ R:
bn ≤ t) − Φ(t)| = 0.
lim |P∗ (U

n→∞

The proof of Corollary 2 can be found in Appendix H.1 of the Supplementary Material.
In addition, we provide a stronger result on uniform confidence intervals for θ in Corollary
8 of the Supplementary Material. Once again, the first part of condition (3.6) agrees with
Ren et al. (2015); Liu (2013). In addition, when the data are known to be Gaussian one
e := vb1 βbm + vbm βb1 of ∆, which can also be shown to be
could use the alternative estimator ∆
p
consistent under the assumption max(sv , s) log d/n = o(1). The second part of condition
(3.6) is mild, since it is only slightly stronger than n−1 sv s = o(1). Unlike Jankova and van de
Geer (2014), we do not assume irrepresentable conditions.
15

Remark 1. (Transelliptical Graphical Models) Our estimating equation based methods for
constructing confidence intervals can be extended to transelliptical graphical models (Liu
et al., 2012b). The key idea is to replace the same covariance matrix Σn in (1.2) and (3.4)
by
(

π
sin
τ
b
, j 6= k;
jk
τ
2
Sbjk
=
1,
j = k,
where
τbjk =

X
2
sign ((Xij − Xi0 j )(Xik − Xi0 k )) .
n(n − 1) 1≤i<i0 ≤n

Similar to Corollary 2, the asymptotic normality of the estimator θe is established. The
details are shown in Appendix D of the Supplementary Material.

3.3

Sparse Linear Discriminant Analysis

In this section, we consider an application of the general theory to the sparse linear discriminant analysis problem. The consistency and rates of convergence of the classification rule
b
ψ(O)
(1.4) have been established by Cai and Liu (2011) in the high dimensional setting.
In the following, we apply the theory of Section 2.1 to construct confidence intervals for θ,
where θ is the first component of β, i.e., β = (θ, γ). Note that if θ = 0, then it implies that
the first feature of O is not needed in the Bayes rule ψ(O). Hence, our procedure can be
used to assess whether a certain feature is significant in the classification.
By the identity β ∗ = Ωδ, we can construct the d-dimensional estimating equations
b n β − (X̄ − Ȳ ). Then the projected estimating equation for θ is given by
t((X, Y), β) = Σ
b n β − (X̄ − Ȳ )),
b
bT (Σ
S(β)
=v
where
b n − e 1 k ∞ ≤ λ0 ,
b = argmin kvk1 , such that kvT Σ
v
b γ
b ) = 0 gives us the Z-estimator
is an estimator of v∗ = (Σ−1 )∗1 . Solving the equation S(θ,
e
e
θ. To establish the asymptotic normality of θ, we impose the following assumption.
Assumption 8. Assume that U satisfies the following moment assumption:
Var(v∗T U ⊗2 β ∗ ) ≥ Vmin kv∗ k22 kβ ∗ k22 ,
where Vmin is a positive constant. In addition let KU = maxj∈{1,...,d} kUj kψ2 < ∞.
As seen in the comments on Assumption 7, we can similarly show that Assumption 8
holds if U ∼ N (0, Σ) and λ2min (Σ) is lower bounded by a positive constant. We define V1 :=
Var(v∗T U ⊗2 β ∗ + α−1 v∗T U ), V2 := Var(v∗T U ⊗2 β ∗ − (1 − α)−1 v∗T U ), where nn1 = α + o(1)
for some 0 < α < 1. Denote
∆ := αV1 + (1 − α)V2 ,
16

(3.7)

bn := ∆
b −1/2 n1/2 (θe−θ∗ ), where ∆
b is some consistent estimator of ∆. The explicit form of
and U
b is complicated, and we defer its expression to Appendix I of the Supplementary Material.
∆
Denote kβ ∗ k0 = s and kv∗ k0 = sv . Once again for simplicity of the presentation we assume
that kv∗ k1 and kβ ∗ k1 are bounded. We obtain the following asymptotic normality result.
Corollary 3. Assume that λmin (Σ) > δ for some constant δ > 0, and let Assumption 8
hold. If
√
(3.8)
max(sv , s) log d/ n = o(1), ∃ k > 2 : (sv s)k /nk−1 = o(1),
p
p
holds and λ  log d/n and λ0  log d/n, then for each t ∈ R:
bn < t) − Φ(t)| = 0.
lim |P∗ (U

n→∞

The second part of (3.8) is similar to that in Corollary 2, which is used to establish the
Lyapunov’s condition for central limit theorem. The proof of Corollary 3 can be found in
Appendix I of the Supplementary Material.

3.4

Stationary Vector Autoregressive Models

In this section we develop inferential methods for the lag-1 vector autoregressive models
considered in the introduction. Let β ∗ = A∗m be the mth column of A. If one is only
interested in estimating β ∗ , instead of solving the whole problem one can only solve the
corresponding subproblem:
βb = argmin kβk1 , subject to kS0 β − S1,∗m k∞ ≤ λ.

(3.9)

β∈Rd

Han et al. (2014) showed that procedure (1.6) consistently estimates A under certain
sparsity assumptions. In the following, we apply our method to construct confidence intervals
for θ, where θ is the first component of β, i.e., β = (θ, γ T )T . By the equation (1.5), we can
construct the d-dimensional estimating equations t(X, β) = S0 β−S1,∗m . Then the projected
estimating equation for θ is given by
b
bT (S0 β − S1,∗m ),
S(β)
=v
where
b = min kvk1 , subject to kvT S0 − e1 k∞ ≤ λ0 ,
v
v∈Rd

e
b b ) = 0. Note that in
is an estimator of v∗T = (Σ−1
0 )1∗ . Define θ to be the solution to S(θ, γ
this framework the estimating equation t(X, β) = S0 β − S1,∗m decomposes into a sum of
dependent random variables. To handle this challenge, our main technical tool is the martingale central limit theorem and concentration inequalities for dependent random variables.

17

e we define the following classes of matrices:
To establish the asymptotic normality of θ,


d×d
M(s) := M ∈ R
: max kM∗j k0 ≤ s, kMk1 ≤ M, kMk2 ≤ 1 −  ,
1≤j≤d

L := M ∈ Rd×d : kM−1 k1 ≤ M, kMk2 ≤ M ,
where M and 1 >  > 0 are some fixed constants. In the following, we can show that
T 1/2 (θe − θ∗ ) converges weakly to N (0, ∆), where
∆ := Ψmm v∗T Σ0 v∗ .

(3.10)

b v T S0 v
b = (S0,mm − βbT S0 β)(b
b) be an estimator of the asymptotic variance ∆, and define
Let ∆
−1/2 1/2 e
∗
b
b
Un := ∆
T (θ − θ ). We have the following asymptotic normality result.
Corollary
4. Let Σ0 ∈ L,pA ∈ M(s), minj Ψjj ≥ C > 0 and kv∗ k0 =√
sv . Then there exist
p
0
λ  log d/T and λ  log d/T such that if max(sv , s) log d = o( T ), we have for all
t ∈ R:
bn ≤ t) − Φ(t)| → 0.
lim |P∗ (U
T →∞

Similarly to Han et al. (2014), we assume that the matrix A belongs to M(s), for the
estimation purpose. The proof of Corollary 4 is given in Appendix J of the Supplementary
material. In this section, we only discussed the lag-1 autoregressive model. As mentioned in
Han et al. (2014), lag-p models can be accommodated in the current lag-1 model framework.
Thus, similar methods can be applied to construct confidence intervals under the lag-p model.

4

Numerical Results

In this section we present numerical results to support our theoretical claims. Numerical
studies on hypothesis testing are available from the authors upon request.

4.1

Linear Model

In this section, we compare our estimating equation (EE) based procedure with two existing
methods: the desparsity (van de Geer et al., 2014) and the debias (Javanmard and Montanari,
2013) methods in linear models. Note that in their methods the LASSO estimator is used
as an initial estimator.
Our simulation setup is as follows. We first generate n = 150 observations X ∼
N (0, ΣX ), where ΣX is a Toeplitz matrix with ΣX,ij = ρ|i−j| , i, j = 1, . . . , d. We consider three scenarios for the correlation parameter ρ = 0.25, 0.4, 0.6 and three possible values of the dimension d = 100, 200, 500. We generate β ∗ under two settings. In the first
setting, β ∗ is held fixed, i.e., β ∗ = (1, 1, 1, 0, . . . , 0)T , and in the second setting we take
β ∗ = (U1 , U2 , U3 , 0, . . . , 0)T , where Ui follows a uniform distribution on the interval [0, 2] for
18

i = 1, 2, 3. The former setting is labeled as “Dirac” and the latter as “Uniform” in Table 4.1
below. Both settings have three nonzero values, i.e., kβ ∗ k0 = 3. The outcome is generated
by Y = X T β ∗ + ε, where ε ∼ N (0, 1). The simulations are repeated 500 times. The tuning
parameter
λ is selected by a 10-fold cross validation. The parameter λ0 is manually set to
p
1
log d/n. We discover that the result is robust with respect to the choice of λ0 . Based on
2
the selected λ and λ0 , we construct the confidence intervals for the first component of β.
Table 4.1: The empirical coverage probability of 95% confidence intervals constructed by our
estimating equation (EE) based method, desparsity and debias methods under the linear
model. The average length of confidence intervals is shown in parenthesis.
Uniform
method
ρ = 0.25
ρ = 0.4
ρ = 0.6
EE
0.94 (0.3) 0.95 (0.4) 0.95 (0.4)
100 desparisty 0.96 (0.4) 0.96 (0.4) 0.95 (0.4)
debias
0.95 (0.3) 0.95 (0.4) 0.94 (0.4)
EE
0.95 (0.3) 0.96 (0.4) 0.95 (0.5)
200 desparisty 0.94 (0.3) 0.95 (0.4) 0.95 (0.4)
debias
0.95 (0.4) 0.95 (0.4) 0.95 (0.4)
EE
0.96 (0.4) 0.96 (0.4) 0.95 (0.4)
500 desparisty 0.96 (0.4) 0.95 (0.4) 0.95 (0.4)
debias
0.95 (0.4) 0.95 (0.4) 0.94 (0.5)
d

ρ = 0.25
0.95 (0.3)
0.96 (0.4)
0.95 (0.4)
0.95 (0.4)
0.95 (0.4)
0.96 (0.4)
0.95 (0.4)
0.96 (0.4)
0.95 (0.5)

Dirac
ρ = 0.4
0.96 (0.4)
0.95 (0.4)
0.94 (0.4)
0.94 (0.4)
0.96 (0.4)
0.96 (0.4)
0.96 (0.4)
0.96 (0.5)
0.95 (0.5)

ρ = 0.6
0.95 (0.4)
0.94 (0.4)
0.95 (0.4)
0.95 (0.5)
0.96 (0.5)
0.95 (0.5)
0.95 (0.4)
0.96 (0.5)
0.94 (0.5)

In Table 4.1, we summarize the empirical coverage probability of 95% confidence intervals
and their average lengths of our estimating equation (EE) based method, desparsity and
debias methods. We find that the empirical coverage probability of our method is very close
to the desired nominal level. In particular, our method tends to have shorter confidence
intervals than the existing two methods, when the dimension is large (e.g. d = 500).

4.2

Graphical Models

In this section we compare our estimating equation (EE) based procedure to the desparsity
method proposed by Jankova and van de Geer (2014) based on the graphical LASSO. We
consider two scenarios. In the first scenario, our data generating process is similar to Jankova
and van de Geer (2014). Specifically, we consider a tridiagonal precision matrix Ω with
Ωii = 1, i = 1, . . . , d and Ωi,i+1 = Ωi+1,i = ρ ∈ {0.3, 0.4} for i = 1, . . . , d − 1. Then we
generate data from the Gaussian graphical model X ∼ N (0, Ω−1 ). We have three settings
for d = 60, 70, 80, and we fix the sample size at n = 250, which is comparable to Jankova
and van de Geer (2014). In the second scenario, we generate data from the transelliptical
19

graphical model. Specifically, the latent generalized concentration matrix Ω is generated
in the same way as in the previous scenario, and then is normalized so that Σ = Ω−1 ,
satisfies diag(Σ) = 1. Next, a normally distributed random vector Z is generated through
Z ∼ N (0, Σ), and is transformed to a new random vector X = (X1 , ..., Xd ), where
X j = qR

f (Zj )

,

f 2 (t)φ (t) dt

and f (t) := sign(t)|t|α is a symmetric power transformation with α = 5 and φ(t) is the pdf
of a standard normal distribution. Then X follows from the transelliptical graphical model
with the latent generalized concentration matrix Ω. Similarly, we consider d = 60, 70, 80,
and fix the sample size at n = 250. The
p simulations are repeated 500 times. The tuning
0
parameters λ = λ are set equal to 0.5 log d/n. In the following, we construct confidence
intervals for the parameter Ω12 .
Table 4.2: The empirical coverage probability of 95% confidence intervals constructed by
our estimating equation (EE) based method and the desparsity method under the Gaussian graphical model and transelliptical graphical model. The average length of confidence
intervals is shown in parenthesis.
Gaussian
Transelliptical
d
method
ρ = 0.3
ρ = 0.4
ρ = 0.3
ρ = 0.4
EE
0.95 (0.3) 0.94 (0.2) 0.93 (0.3) 0.94 (0.3)
60
desparsity 0.95 (0.3) 0.95 (0.3) 0.80 (0.3) 0.44 (0.3)
EE
0.95 (0.3) 0.94 (0.2) 0.92 (0.3) 0.94 (0.3)
70
desparsity 0.95 (0.3) 0.96 (0.3) 0.74 (0.3) 0.47 (0.3)
EE
0.95 (0.3) 0.95 (0.2) 0.93 (0.3) 0.94 (0.4)
80
desparsity 0.94 (0.3) 0.94 (0.3) 0.70 (0.3) 0.44 (0.3)

In Table 4.2, we present the empirical coverage probability of 95% confidence intervals
and their average lengths of our estimating equation (EE) based method, and the desparsity
method. As expected, under the Gaussian graphical model, the confidence intervals of both
methods have accurate empirical coverage probability and similar lengths. However, the
desparsity method which imposes the Gaussian assumption shows significant under-coverage
for the transelliptical graphical model. In contrast, the proposed method preserves the
nominal coverage probability, which demonstrates the numerical advantage of our method.

4.3

Real Data Analysis

In this section, we construct confidence regions for the gene network from the atlas of gene
expression in the mouse aging project dataset (Zahn et al., 2007). The same dataset has
20

been previously analyzed in Ning and Liu (2013), where the authors focus on a subset of
d = 37 genes belonging to the mouse vascular endothelial growth factor signaling pathway
in 8 tissues. The number of replicates within each tissue is n = 40.
Our analysis proceeds conditionally on each of the 8 tissue types – Adrenal (A), Cerebrum
(C), Hippocampus (H), Kidney (K), Lung (L), Muscle (M), Spinal (S), Thymus (T). Namely,
for each type of tissue, we construct the confidence intervals of each edges in the gene network
by using our method and the procedure proposed by Jankova and van de Geer (2014). In
particular, our inference is based on the approach developed in Section 3.2 with the sample
covariance matrix replaced by the rank covariance matrix defined in Remark 1; see also
section D in the Supplementary Material for details. The tuning parameter λ is determined
by the 5-fold cross-validation, under the Gaussian likelihood function,
for a grid of values in
p
the interval [0.3, 0.8], which is selected based on the fact that log d/n ≈ 0.3. The tuning
parameter λ0 is set to be the same as λ. The tuning parameter in Jankova and van de Geer
(2014) is selected by the same cross-validation method.
To perform the comparison we consider 2 sets of genes which have been shown to be
associated by biologists. The first set of genes – Pla2g6, Ptk2 and Plcg2, comes from the
group of PLC-γ genes in the PKC-dependent pathway, and is crucial for ERK phosphorylation and proliferation (Holmes et al., 2007). The second set of genes is comprised of Mapk13,
Mapk14 and Mapkapk2, which are related to the migration of endothelial cells. Instead of
plotting confidence intervals for all the edges in the gene network, in Figure 4.1 we only
plot confidence intervals for the 3 edges connecting genes Pla2g6, Ptk2 and Plcg2, and genes
Mapk13, Mapk14 and Mapkapk2, within each of the 8 tissues. As we see from the plot, while
most of the point estimates of our method and Jankova and van de Geer (2014) are close,
their variances differ drastically. The main reason is that in this dataset the gene expression
values are highly non-Gaussian; see Ning and Liu (2013) for demonstration. Thus, the inference procedure based on the Gaussian assumption (Jankova and van de Geer, 2014) seems
to provide inaccurate results with very wide confidence intervals. In contrast, the proposed
method which relaxes the Gaussian assumption, produces confidence intervals with shorter
length. In fact, most of the 95% confidence intervals by the proposed method do not cover 0,
which concludes that these genes are statistically dependent. This result is consistent with
the biological findings that genes Pla2g6, Ptk2 and Plcg2, and genes Mapk13, Mapk14 and
Mapkapk2 are associated.

5

Discussion

In this paper we propose a generic procedure to construct confidence intervals for Z-estimators
in a high dimensional setting. We establish a general theoretical framework, and illustrate
it with several important applications including linear models, instrumental variables regression, graphical models, classification and time series models. Our framework has better
numerical performance than previously suggested algorithms, and has the advantage of hav21

Ptk2 ↔ Plcg2

●

●

●

●
●
●

●

●
●

●
●
●

C

H

K L M
Tissues

S

T

●

●

●

●

●

●
●

●

●

●

−1.5

A

●

●
●

●

A

C

K L M
Tissues

S

●

●
●

●

●

●
●
●

●
●

●

●
●
●
●

●
●

●

●

●

●
●

●

●

●
●
●

A

C

H

K L M
Tissues

S

T

●

●
●

●

●

●

●

●

●

●

●

C

H

K L M
Tissues

S

T

Mapk14 ↔ Mapkapk2

●
●
●

●

●
●

●

●
●

●
●
●

●

●
●

●

−0.6

−0.6

●

Confidence Regions
−0.2
0.2

●

●

−1.0

Confidence Regions
−0.6
−0.2
0.2

●

●

●

●

●

A

Mapkapk2 ↔ Mapk13

●

●

T

0.6

Mapk13 ↔ Mapk14

H

Confidence Regions
−0.4
0.0 0.2 0.4

●

●
●
●

Confidence Regions
−0.2
0.2 0.4 0.6

●

Confidence Regions
−1.0
−0.5
0.0

0.6

Plcg2 ↔ Pla2g6

●

−1.0

Confidence Regions
−0.5
0.0
0.5

Pla2g6 ↔ Ptk2

A

C

H

K L M
Tissues

S

T

A

C

H

K L M
Tissues

S

T

Figure 4.1: 95% confidence intervals for the edges among the two sets of genes – Plcg2,
Pla2g6, and Pla2g6 (first row) and Mapk13, Mapk14 and Mapkapk2 (second row), within
each of 8 tissues indicated by their first letter. The confidence intervals based on our EE
method are displayed in solid lines, while the intervals of Jankova and van de Geer (2014)
are displayed in dashed lines.
ing a broader scope. In particular, it covers many applications (e.g. instrumental variables
regression, linear discriminant analysis and vector autoregressive models) for which the inferential procedure is previously unexplored.
Additionally our results can be easily extended to cases with multi-dimensional parameters of interest. We would like to mention that unlike approaches such as the ones developed
by Nickl et al. (2013), our methodology cannot be immediately extended to find a global
honest confidence region for the entire parameter β. It is an interesting problem to explore
whether we can carry over certain results in the framework of honest confidence regions for
β under the linear regression considered by Nickl et al. (2013), to the general estimating
equations that we consider. We leave this question for future investigation.

22

References
Adamczak, R. and Wolff, P. (2015). Concentration inequalities for non-lipschitz functions with bounded derivatives of higher order. Probability Theory and Related Fields 162
531–586.
Barber, R. F. and Kolar, M. (2015). Rocket: Robust confidence intervals via kendall’s
tau for transelliptical graphical models. arXiv preprint arXiv:1502.07641 .
Belloni, A., Chen, D., Chernozhukov, V. and Hansen, C. (2012). Sparse models and
methods for optimal instruments with an application to eminent domain. Econometrica
80 2369–2429.
Belloni, A., Chernozhukov, V. and Wei, Y. (2013). Honest confidence regions for
logistic regression with a large number of controls. arXiv preprint arXiv:1304.3969 .
Bickel, P. J., Ritov, Y. and Tsybakov, A. B. (2009). Simultaneous analysis of lasso
and dantzig selector. The Annals of Statistics 1705–1732.
Cai, T. and Liu, W. (2011). A direct estimation approach to sparse linear discriminant
analysis. Journal of the American Statistical Association 106 1566–1577.
Cai, T., Liu, W. and Luo, X. (2011). A constrained l1 minimization approach to sparse
precision matrix estimation. Journal of the American Statistical Association 106 594–607.
Cai, T. T., Liang, T. and Rakhlin, A. (2014). Geometrizing local rates of convergence
for linear inverse problems. arXiv preprint arXiv:1404.4408 .
Candes, E. and Tao, T. (2007). The dantzig selector: Statistical estimation when p is
much larger than n. The Annals of Statistics 2313–2351.
Chen, M., Ren, Z., Zhao, H. and Zhou, H. (2015). Asymptotically normal and efficient estimation of covariate-adjusted gaussian graphical model. Journal of the American
Statistical Association .
Fan, J. and Lv, J. (2011). Nonconcave penalized likelihood with np-dimensionality. Information Theory, IEEE Transactions on 57 5467–5484.
Fang, K.-T., Kotz, S. and Ng, K. W. (1990). Symmetric multivariate and related
distributions. Chapman and Hall.
Gautier, E. and Tsybakov, A. (2011). High-dimensional instrumental variables regression and confidence sets. arXiv preprint arXiv:1105.2454 .
Godambe, V. P. (1991). Estimating functions. Clarendon Press Oxford.
Gu, Q., Cao, Y., Ning, Y. and Liu, H. (2015). Local and global inference for high
dimensional gaussian copula graphical models. arXiv preprint arXiv:1502.02347 .
Hall, P. and Heyde, C. C. (1980). Martingale limit theory and its application. Academic
press New York.
Han, F., Lu, H. and Liu, H. (2014). A direct estimation of high dimensional a direct estimation of high dimensional stationary vector autoregressions. arXiv preprint
arXiv:1307.0293v3 .
Hoeffding, W. (1948). A class of statistics with asymptotically normal distribution. The
23

Annals of Mathematical Statistics 293–325.
Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables.
Journal of the American statistical association 58 13–30.
Holmes, K., Roberts, O. L., Thomas, A. M. and Cross, M. J. (2007). Vascular
endothelial growth factor receptor-2: structure, function, intracellular signalling and therapeutic inhibition. Cellular signalling 19 2003–2012.
Jankova, J. and van de Geer, S. (2014). Confidence intervals for high-dimensional
inverse covariance estimation. arXiv preprint arXiv:1403.6752 .
Javanmard, A. and Montanari, A. (2013). Confidence intervals and hypothesis testing
for high-dimensional regression. arXiv preprint arXiv:1306.3171 .
Lee, J. D., Sun, D. L., Sun, Y. and Taylor, J. E. (2013). Exact inference after model
selection via the lasso. arXiv preprint arXiv:1311.6238 .
Liu, H., Han, F., Yuan, M., Lafferty, J., Wasserman, L. et al. (2012a). Highdimensional semiparametric gaussian copula graphical models. The Annals of Statistics
40 2293–2326.
Liu, H., Han, F. and Zhang, C.-h. (2012b). Transelliptical graphical models. In Advances
in Neural Information Processing Systems.
Liu, W. (2013). Gaussian graphical model estimation with false discovery rate control. The
Annals of Statistics 41 2948–2978.
Lockhart, R., Taylor, J., Tibshirani, R. J., Tibshirani, R. et al. (2014). A
significance test for the lasso. The Annals of Statistics 42 413–468.
Lu, S., Liu, Y., Yin, L. and Zhang, K. (2015). Confidence intervals and regions for the
lasso using stochastic variational inequality techniques in optimization. Technical Report.
Mardia, K. V., Kent, J. T. and Bibby, J. M. (1979). Multivariate analysis. Academic
press.
Meinshausen, N. and Bühlmann, P. (2010). Stability selection. Journal of the Royal
Statistical Society: Series B (Statistical Methodology) 72 417–473.
Meinshausen, N., Meier, L. and Bühlmann, P. (2009). P-values for high-dimensional
regression. Journal of the American Statistical Association 104.
Newey, W. K. and McFadden, D. (1994). Large sample estimation and hypothesis
testing. Handbook of econometrics 4 2111–2245.
Nickl, R., van de Geer, S. et al. (2013). Confidence sets in sparse regression. The
Annals of Statistics 41 2852–2876.
Ning, Y. and Liu, H. (2013). High-dimensional semiparametric bigraphical models.
Biometrika 100 655–670.
Ning, Y. and Liu, H. (2014a). A general theory of hypothesis tests and confidence regions
for sparse high dimensional models. arXiv preprint arXiv:1412.8765 .
Ning, Y. and Liu, H. (2014b). Sparc: Optimal estimation and asymptotic inference under
semiparametric sparsity. arXiv preprint arXiv:1412.2295 .

24

Ren, Z., Sun, T., Zhang, C.-H., Zhou, H. H. et al. (2015). Asymptotic normality and
optimalities in estimation of large gaussian graphical models. The Annals of Statistics 43
991–1026.
Shah, R. D. and Samworth, R. J. (2013). Variable selection with error control: another
look at stability selection. Journal of the Royal Statistical Society: Series B (Statistical
Methodology) 75 55–80.
Taylor, J., Lockhart, R., Tibshirani, R. J. and Tibshirani, R. (2014). Post-selection
adaptive inference for least angle regression and the lasso. arXiv preprint arXiv:1401.3889.
van de Geer, S., Bühlmann, P. and Ritov, Y. (2014). On asymptotically optimal
confidence regions and tests for high-dimensional models. The Annals of Statistics 42
1166–1202.
Van der Vaart, A. W. (2000). Asymptotic statistics, vol. 3. Cambridge university press.
Vershynin, R. (2010). Introduction to the non-asymptotic analysis of random matrices.
arXiv preprint arXiv:1011.3027 .
Voorman, A., Shojaie, A. and Witten, D. (2014). Inference in high dimensions with
the penalized score test. arXiv preprint arXiv:1401.2678 .
Wasserman, L. and Roeder, K. (2009). High dimensional variable selection. Annals of
statistics 37 2178.
Zahn, J. M., Poosala, S., Owen, A. B., Ingram, D. K., Lustig, A., Carter, A.,
Weeraratna, A. T., Taub, D. D., Gorospe, M., Mazan-Mamczarz, K. et al.
(2007). Agemap: a gene expression database for aging in mice. PLoS Genet 3 e201.
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 217–242.

25

Supplement: A Unified Theory of Confidence
Regions and Testing for High Dimensional
Estimating Equations
Matey Neykov∗

A

Yang Ning∗

Jun S. Liu†

Han Liu∗

Theory on Uniformly Valid Confidence Intervals

b γ
b ) = 0 can be
In section 2.1, we showed that if β ∗ is fixed, the solution to the equation S(θ,
used to construct asymptotically valid confidence regions for the parameter θ. In this Section
we prove a stronger result which guarantees that the confidence interval is valid uniformly
over the following parameter space:
Ω = {β ∗ : kβ ∗ k0 ≤ s∗ }.
We restrict our attention to Ω since we need the parameter β ∗ to be sufficiently sparse
in order for us to consistently estimate it. In the following, we introduce some assumptions
guaranteeing uniform convergence.
Assumption 9 (Uniform Consistent Estimation).
lim sup Pβ (kβb − βk1 ≤ r1 (n)) = 1,

lim sup Pβ (kb
v − vk1 ≤ r2 (n)) = 1,

n→∞ β∈Ω

n→∞ β∈Ω

where r1 (n), r2 (n) = o(1).
∗

Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ
08544; e-mail: {mneykov,yning,hanliu}@princeton.edu
†
Department of Statistics, Harvard University, Cambridge, MA 02138, USA; e-mail:
jliu@stat.harvard.edu

26

Assumption 10. Assume that there exists an η > 0 such that:
lim inf inf Pβ (kt(Z, βθ̌ ) − Et (βθ̌ )k∞ ≤ r3 (n)) = 1,

(A.1)

lim inf inf Pβ (|vT t(Z, βθ̌ ) − vT Et (βθ̌ )| ≤ r4 (n)) = 1,


T
T
e
v T(Z, βν ) − v ET (βθ̌ )k∞ ≤ r5 (n) = 1,
lim inf inf Pβ sup kb

(A.2)

n→∞ β∈Ω θ̌∈Nθ
n→∞ β∈Ω θ̌∈Nθ

n→∞ β∈Ω θ̌∈Nθ

(A.3)

ν∈[0,1]

where Nθ = (θ − η, θ + η) and max(r3 (n), r4 (n), r5 (n)) = o(1), βeν = ν βbθ̌ + (1 − ν)βθ̌ . We
also assume
sup sup kEt (βθ̌ )k∞ < ∞,

β∈Ω θ̌∈Nθ

sup sup kvT [ET (βθ̌ )]−1 k∞ < ∞.

β∈Ω θ̌∈Nθ

e which is a uniform analogue
We next prove the uniform consistency of the Z-estimator θ,
of Theorem 1.
b βb ) is continuous with a single
Proposition 1. Assume that the (stochastic) map θ̌ 7→ S(
θ̌
root or nondecreasing. In addition, assume that vT Et (βθ− ) × vT Et (βθ+ ) < 0 for any  > 0.
Under conditions 9 and 10 we have that for any  > 0: supβ∈Ω Pβ (|θe − θ| > ) = o(1).
Assumption 11 (Uniform CLT). For σ 2 = vT Σv we have:
lim sup sup |Pβ (σ −1 n1/2 S(β) ≤ t) − Φ(t)| = 0,

n→∞ β∈Ω t∈R

(A.4)

where Σ = limn→∞ n Cov t(Z, β), and it is assumed that inf β∈Ω σ 2 ≥ C > 0.
Assumption 12. Assume that there exists a γ > 0 such that:
sup

sup

v̌T

β∈Ω max(kv̌−vk1 ,kβ̌−βk1 )<γ


∂ 
T(Z, β̌) ∗1 ≤ ψ(Z),
∂θ

(A.5)

where ψ is an integrable function such that supβ∈Ω Eψ(Z) < ∞.
Assumption 13 (Uniform Consistency of Variance). Assume there exists an estimator σ
b2
of σ 2 , such that limn→∞ inf β∈Ω Pβ (|b
σ 2 − σ 2 | ≤ r6 (n)) = 1, where r6 (n) = o(1).
In Section B.2 we provide sufficient conditions to obtain σ
b satisfying Assumption 13.
Finally, we present a uniform weak convergence result for the Z-estimator which strengthens
Theorem 2. Its proof can be found in Appendix E.
Theorem 3. Under Assumptions 9 – 13, the assumptions in Proposition 1 and n1/2 (r1 (n)r5 (n)+
bn ≤ t) − Φ(t)| = 0, where U
bn =
r2 (n)r3 (n)) = o(1), we have limn→∞ supβ∈Ω supt∈R |Pβ (U
1/2
n
(θe − θ).
σ
b
27

Remark 2. Notice that Theorem 3 immediately implies that
bn | ≤ t) − Φ(t) + Φ(−t)| = 0.
lim sup sup |Pβ (|U

n→∞ β∈Ω t∈R+

The latter can be equivalently expressed as
√
√
lim sup sup |Pβ (θ ∈ (θe − σ
bt/ n, θe + σ
bt/ n)) − Φ(t) + Φ(−t)| = 0,
n→∞ β∈Ω t∈R+

√
√
bt/ n) is uniformly valid over the
which implies that the confidence region (θe − σ
bt/ n, θe + σ
parameter space β ∈ Ω provided that the assumptions we discussed in this section hold.

B

Sufficient Conditions for Variance Consistency

In this brief Section we present sufficient conditions for having consistent variance estimators.

B.1

Consistent Estimators of the Variance

We now provide generic sufficient conditions for constructing a consistent estimate of the
b be a consistent estimator of Cov t(Z, β). In the case when t(Z, β) =
variance. Let Σ
Pn
Pn
1
−1
b ⊗2
b
n
i=1 h(Zi , β) one can use Σ := n
i=1 h(Zi , β) . We consider the “plugin” estimator:
b v of σ 2 . Define: U
bn = σ
bn
bT Σb
σ
b2 = v
b−1 n1/2 (θe − θ∗ ). We are interested in showing that U
converges weakly to a standard normal distribution. To this end we define the following
assumption:
Assumption 14 (Variance Consistency). Assume that the following holds:
b − Σkmax ≤ r7 (n)) = 1,
lim P∗ (kΣ

n→∞

where r7 (n) = o(1).
Proposition 2. Assume the same assumptions as in Proposition 2 plus Assumption 14.
Let furthermore kΣkmax = O(1), kv∗T Σk∞ r2 (n) = o(1) and kv∗ k21 r7 (n) = o(1), then for any
t ∈ R we have:
bn ≤ t) − Φ(t))| = 0.
lim |P∗ (U
n→∞

The proof of Proposition 2 can be found in Section E.

B.2

Uniformly Consistent Estimators of the Variance

Assumption 15 (Plugin Variance Consistency). Assume that the following holds:
b − Σkmax ≤ r8 (n)) = 1,
lim inf Pβ (kΣ

n→∞ β∈Ω

where r8 (n) = o(1).
28

We then have the following:
Proposition 3. Assume that
sup kΣkmax = O(1),

sup kvT Σk∞ r2 (n) = o(1),

β∈Ω

β∈Ω

sup kvk21 r8 (n) = o(1),

β∈Ω

b satisfies Assumption 15. Then σ
b v satisfies Assumption 13.
bT Σb
and Σ
b2 = v
The proof of this proposition is omitted as it follows easily from the proof of Proposition
2 and Lemma 2 in the Appendix.

C

Confidence Intervals for Instrumental Variables Regression

Recall that β := (θ, γ T )T , and let Σn = n−1 [X; W]T [X; W] be the empirical estimator of
Σ = E(X T , W T )T (X T , W T ). Conformally we decompose the matrices Σn and Σ into four
blocks corresponding to ordered pairings of X and W indicated by subscripting with the
pair, e.g. ΣW X,n and ΣW X correspond to n−1 WT X and EW X T resectively. Our goal is to
b
construct confidence intervals for the parameter θ. It is easy to show that S(β)
reduces to
b
bT WT (Xβ − Y ),
S(β)
= n−1 v
where
b = argmin kvk1 , subject to kvT ΣW X,n − e1 k∞ ≤ λ0 ,
v

(C.1)

T
is an estimator of v∗ = Σ−1
W X e1 . We impose the following assumption.

Assumption 16. Let the error ε := Y − X T β ∗ , the predictors X and instruments W be
coordinate-wise sub-Gaussian, i.e.,
kεkψ2 := K < ∞,

sup

max(kXj kψ2 , kWj kψ2 ) := KW X < ∞,

j∈{1,...,d}

for some fixed constants K, KW X > 0 and Var(ε) ≥ Cε > 0. Furthermore, assume
λmin (ΣW X ΣXW ) ≥ δ 2 > 0, where δ is some fixed constant. Additionally recall that
E[ε2 |Z] = σ 2 , E[Zε] = 0.
Assumption 17. We impose the following assumptions on the covariance Σ. Assume:
−1
kΣ−1
XW ΣW W ΣW X kmax ≤ Dmax ,

inf
CSΣW X (s, 1)
√
s∈{1,...,d},s log d< nω

≥ κ∗ > 0,

for some sufficiently large Dmax > 0, ω > 0 is a sufficiently small fixed constant, and the
quantity CSΣW X (s, 1) is defined in Definition G.1.
29

Assumption 16 is mild and ensures that the random variables ε, X, W are not heavytailed, the matrix ΣW X is invertible, the instrumental variables W are uncorrelated with ε,
and that ε is homoscedastic given the instrumental variables. Assumption 17 is a technical
assumption. The first condition ensures that the random variable v∗T W has a finite second
moment, i.e. E(v∗T W )2 ≤ Dmax < ∞. The second condition implies that the matrix ΣW X
is “coordinate-wise sensitive” with respect to the L1 norm. Such a condition is first proposed
by Gautier and Tsybakov (2011), and can be viewed as an extension of the commonly used
restricted eigenvalue (RE) condition. It is not hard to show that this condition holds (for
all s ∈ {1, . . . , d}) if for example λmin (ΣXW + ΣW X ) ≥ 4κ∗ , where the inequality is in the
sense of eigenvalues comparison.
bn = ∆
b −1 n1/2 (θe − θ∗ ), where θe is
To construct confidence intervals for θ, we consider U
b γ
b ) = 0, and
defined as the solution to S(θ,
b := n−1
∆

n
X
b 2,
((b
vT Wi )(Yi − XiT β))

(C.2)

i=1

is an estimator of the asymptotic variance ∆ := Var[v∗T W ε]. As in the linear model we
will assume that v∗ and β ∗ are sparse. Let s and sv denote the sparsity of β ∗ and v∗
correspondingly, i.e., kβ ∗ k0 = s and kv∗ k0 = sv . The next corollary of the general Theorem
bn in instrumental variable regressions. To simplify the
2 shows the asymptotic normality of U
presentation of our result we will assume that kv∗ k1 is bounded, although this is not needed
in our proofs.
Corollary 5. Assume that condition 16 and 17 hold, and
p
√
log d/n = o(1).
max(sv , s) log d/ n = o(1),
Then with λ 

p
p
bn satisfies for any t ∈ R:
log d/n and λ0  log d/n, U
bn ≤ t) − Φ(t))| = 0.
lim |P∗ (U

n→∞

The proof of Corollary 5 can be found in Appendix G. The conditions in Corollary 5
agree with the existing conditions in Zhang and Zhang (2014); van de Geer et al. (2014) for
the simple linear model. In fact, under the additional assumption s3v /n = o(1), we can show
bn is uniformly asymptotically normal; see Remark 8.
that U

D

Confidence Intervals for Transelliptical Models

In this subsection we consider the transelliptical graphical models (TGM), proposed by Liu
et al. (2012b). We recall several definitions before we proceed.

30

Definition D.1 (Elliptical distribution Fang et al. (1990)). Let µ ∈ Rd and Σ ∈ Rd×d . We
say that the d-dimesnional vector X has an elliptical distribution, and we denote it with
d
X ∼ ECd (µ, Σ, ξ) if X = µ + ξAU , where U is a random vector uniformly distributed on
the unit sphere in Rq , ξ ≥ 0 is a scalar random variable independent of U , A ∈ Rd×q is a
deterministic matrix such that AAT = Σ.
Definition D.2 (Transelliptical distribution Liu et al. (2012b)). We call the continuous
random vector X = (X1 , . . . , Xd )T transelliptically distributed, and we denote it with X ∼
T Ed (Σ, ξ; f1 , . . . , fd ), if there exists a set of monotone univariate functions f1 , . . . , fd and a
non-negative random variable ξ, with P(ξ = 0) = 0, such that:
(f1 (X1 ), . . . , fd (Xd ))T ∼ ECd (0, Σ, ξ),
where Σ is symmetric with diag(Σ) = 1 and Σ > 0 in a positive-definite sense. Here Σ is
called the “latent generalized correlation matrix”.
The graphical structure in TGMs can then be defined through the notion of the “latent
generalized concentration matrix” — Ω = Σ−1 , i.e. an edge is present between two variables
Xj , Xk if and only if Ωjk 6= 0. To construct an estimate of Ω, Liu et al. (2012b) suggested
estimating the correlation matrix Σ first. This can be done by using a non-parametric
estimate of the correlation such as Kendall’s tau, and transforming it back, to obtain an
estimate of Σ.
bτ
Assume that X1 , . . . , Xn are i.i.d. copies of X. Recall the definitions of τbjk and S
jk

given in Remark 1. Note that it is clear from the definition of τbjk , that it is an unbiased
estimator of:
τjk = P((Yj − Yj0 )(Yk − Yk0 ) > 0) − P((Yj − Yj0 )(Yk − Yk0 ) < 0),

bτ consistently estimates
where Y , Y 0 ∼ X are i.i.d. random variables. It can be seen that S
jk
∗
−1
Σ (see e.g. (Liu et al., 2012a)). Let Ω = Σ . The TGM estimator with CLIME is given
by:
b = argmin kΩk1 , such that kS
bτ Ω − Id kmax ≤ λ.
Ω
To derive confidence intervals for the parameter Ω∗1m , we can apply a similar approach to
the graphical models. Denote with β = Ω∗m . Then the CLIME with TGM reduces to
bτ β − eT k∞ ≤ λ.
βb = argmin kβk1 , such that kS
m
bτ β − eT ), where
b
b T (S
According to our formulation of the test statistic we have S(β)
=v
m
bτ − e1 k∞ ≤ λ0 .
b = argmin kvk1 , such that kvT S
v

(D.1)

b γ
b ) = 0, has a closed form expression in this example, and it
The solution θe to equation S(θ,
is given below:
bτ βb − eT )
bT (S
v
m
θe = θb −
.
τ
T
b
b S
v
∗1
31

(D.2)

Next we argue that θe can be used to construct confidence intervals for the parameter θ. We
note that the estimating equation in the TGM with CLIME is not a sum of i.i.d. statistics,
due to the U -statistic structure of S τ as compared to estimating equations we considered
in our previous examples. Nevertheless, the assumptions in Section 2 are general enough
 Yto
π
handle such a case. Let Θ be a d × d random matrix with entries Θjk := π cos 2 τjk τjk ,
where:
Y
τjk
= [P((Yj − Yj0 )(Yk − Yk0 ) > 0|Y ) − P((Yj − Yj0 )(Yk − Yk0 ) < 0|Y ) − τjk ],
Y
with Y , Y 0 are i.i.d. copies of X (and all τjk
being a random variable depending on Y ).
Define

∆ := Var(v∗T Θβ ∗ ).

(D.3)

Assumption 18. Let X satisfy the following distributional assumption — there exists
αmin > 0 such that ∆ ≥ αmin kv∗ k22 kβ ∗ k22 .
Remark 3. As in the CLIME case, we can show that the condition Var(v∗T Θβ ∗ ) ≥
αmin kv∗ k22 kβ ∗ k22 is equivalent to Var(v∗T Θβ ∗ ) ≥ Vmin , assuming that the matrix Σ ≥ δ > 0.
b an estimate for ∆. To this end define the following matrices
Next, we proceed to define ∆
b i:
—Θ


1 X
i
b i := π cos π τbjk τbi .
τbjk
:=
sign ((Xij − Xi0 j )(Xik − Xi0 k )) − τbjk , Θ
jk
jk
n − 1 i0 6=i
2
T bib 2
b i is symmetric by definition. Define the estimator ∆
b := n−1 Pn (b
Note that Θ
jk
i=1 v Θ β) .
We have the following:

Corollary 6. Assume the data follow from the transelliptical graphical models and Assumption 18 holds. Furthermore, assume that the smallest eigenvalue of the correlation matrix
satisfies λmin (Σ) ≥ δ > 0 is bounded away from 0, and diag(Σ) = 1. Let kβ ∗ k0 = s and
b is a consistent estimate of ∆. Under the following additional assumptions
kv∗ k0 = sv and ∆
p
max(sv , s)kv∗ k1 kβ ∗ k1 log d/n1/2 = o(1), kv∗ k21 kβ ∗ k21 max(sv , s) log d/n = o(1), (D.4)
∃ k > 2 : (sv s)k /nk−1 = o(1),

(D.5)

p
p
bn =
we can take λ  kβ ∗ k1 log d/n and λ0  kv∗ k1 log d/n so that the statistic U
−1/2
1/2
b
bn ≤ t) − Φ(t)| = 0.
∆
n (θe − θ) satisfies for all t: limn→∞ |P(U
Similarly, we can show the following result regarding uniformly valid confidence intervals.
Before that we define a class of correlation matrices, in analogy to the CLIME case:
e s) = {Σ : Σ = ΣT , 0 < δ ≤ λmin (Σ), diag(Σ) = 1, kΣ−1 k1 ≤ L, max kΣ−1 k0 ≤ s},
S(L,
∗i
i

32

e s). Assume furthermore that X
Corollary 7. Let X ∼ T Ed (µ, Σ, ξ) with Σ ∈ S(L,
satisfies Assumption 18, and
p
s3 n−1/2 = o(1), sL2 log(d)n−1/2 = o(1), sL4 log d/n = o(1).
(D.6)
bn ≤ t) − Φ(t)| = 0.
Then we have limn→∞ supΣ∈S(L,s)
supt |Pβ (U
e

E

Proofs of the General Theory

b
bT t(Z, β). We start by deriving an asymptotic
Recall that S(β) := v∗T t(Z, β), and S(β)
:= v
b βbθ∗ ).
expansion of the projected estimating equation S(
Lemma 1. Suppose Assumptions (2.8), 1 and
n1/2 (r4 (n)r3 (n, θ∗ ) + r5 (n)r1 (n, θ∗ )) = o(1),

(E.1)

hold. Then we have the following asymptotic expansion:
b βbθ∗ ) = n1/2 S(β ∗ ) + op (1).
n1/2 S(
Proof of Lemma 1. Let for brevity r1 (n) = supθ∈Nθ∗ r1 (n, θ) and r3 (n) = supθ∈Nθ∗ r3 (n, θ).
We start by showing that for all θ ∈ Nθ∗ :
b βbθ ) = S(β ∗ ) + op (1) = v∗T [Et (β ∗ )] + op (1).
S(
θ
θ

(E.2)

This fact will be used in the proof of Theorem 1. By the mean value theorem we have:
b βbθ ) = v∗T t(Z, βθ∗ ) + v
bT T(Z, βeν )(βbθ − βθ∗ ) + (b
S(
v − v∗ )T t(Z, βθ∗ )
|
{z
} |
{z
}
I1

I2

Next we control I1 :
|I1 | ≤ k[b
vT T(Z, βeν )]−1 k∞ kβbθ − βθ∗ k1 ≤ Op (r3 (n) + kv∗T [ET (βθ∗ )]−1 k∞ )Op (r4 (n))
{z
}
|

(E.3)

O(1)

where by [·]−1 we mean discarding the first entry (corresponding to θ) of the vector. We
proceed to bound I2 :
|I2 | ≤ kb
v − v∗ k1 kt(Z, βθ∗ )k∞ = Op (r5 (n))Op (r1 (n) + kEt (βθ∗ )k∞ ).
| {z }

(E.4)

O(1)

This combined with (2.6) concludes the our initial statement. For the influence function
expansion stated in Lemma 1 observe that Et (βθ∗∗ ) = 0 and v∗T [ET (βθ∗∗ )]−1 = 0 and hence
using (E.1) we can modify bounds (E.3) and (E.4) to:
n1/2 (|I1 | + |I2 |) ≤ n1/2 Op (r4 (n)r3 (n, θ∗ ) + r5 (n)r1 (n, θ∗ )) = op (1),
and we are done.
33

b βbθ ) is continuous and has a unique 0.
Proof of Theorem 1. First assume that the map θ 7→ S(
∗
∗
Take  > 0 so that both θ − , θ +  ∈ Nθ∗ . Without loss of generality let v∗T Et (βθ∗ − ) < 0
b βbθ ), and the fact
and v∗T Et (βθ∗ + ) > 0 for all  > 0. Note that by the continuity of θ 7→ S(
b βbθ∗ − ) < 0, S(
b βbθ∗ + ) > 0) ≤ P∗ (θ∗ −  < θe < θ∗ + ). Now by
that θe is the unique root P∗ (S(
(E.2) from Lemma 1 we have that the left hand side converges to 1 and this concludes the
proof in the first case. The same argument goes through in the second case.
1/2
Proof of Theorem 2. Let Un = √vn∗T Σv∗ (θe − θ∗ ). It suffices to show that the statement holds
bn is a corollary after an application of Slutsky’s theorem. By
for Un , as the statement for U

the mean value theorem:
1 T ∂
b βbe) = S(
b βbθ∗ ) + v
b
bT [T(Z, βbθ∗ )]∗1 (θe − θ∗ ) + v
[T(Z, βeν )]∗1 (θe − θ∗ )2 ,
(E.5)
S(
θ
2 ∂θ
b and βeν are
where βeν = ν βbθe + (1 − ν)βbθ∗ for some ν ∈ [0, 1]. By (2.10) and the fact that v
consistent (by (2.8) and Theorem 1) we have that:
1 T ∂
b
v
[T(Z, βeν )]∗1 (θe − θ∗ )2 ≤ (θe − θ∗ )2 Op (1) = |θe − θ∗ |op (1).
2 ∂θ
1/2
b βbθ∗ ) = Op (1), and more
Observe that by Lemma 1 and Assumption 3 we have √vn∗T Σv∗ S(
1/2
b βbθ∗ )
precisely √ n
S(
N (0, 1). Next by Assumption 1,

v∗T Σv∗

n1/2 |θb − θ∗ |(|b
vT [T(Z, βbθ∗ )]∗1 | +op (1)) = Op (1),
{z
}
|
1+op (1)

and hence we conclude that θb − θ∗ = Op (n−1/2 ). Thus by Assumption 1 and Sltusky’s:
b βbθ∗ )
n1/2 (θe − θ∗ )
n1/2 S(
√
= −√
+ op (1)
v∗T Σv∗
bT [T(Z, βbθ∗ )]∗1
v∗T Σv∗ v
which concludes the proof.

N (0, 1),

Proof of Proposition 1. We start by showing that for all  > 0:


T
b
b
sup sup Pβ |S(βθ̌ ) − v Et (βθ̌ )| >  = o(1).
β∈Ω θ̌∈Nθ

We have:


b βb ) − vT Et (β )| > 
sup sup Pβ |S(
θ̌
θ̌

β∈Ω θ̌∈Nθ


≤ sup sup Pβ
β∈Ω θ̌∈Nθ




v t(Z, βθ̌ ) − v Et (βθ̌ ) >
3
T

T




b [T(Z, βeν )]−1 kβbθ̌ − βθ̌ k1 >
+ sup sup Pβ sup v
3
β∈Ω θ̌∈Nθ
ν∈[0,1]
∞



+ sup sup Pβ kb
v − vk1 kt(Z, βθ̌ )k∞ >
,
3
β∈Ω θ̌∈Nθ
T

34



(E.6)

where βeν = ν βbθ̌ + (1 − ν)βθ̌ . By Assumptions 9 and 10 it follows that the RHS is o(1), as
b βb ) are continuous. To shorten the
we claimed. First let us assume that the maps θ̌ 7→ S(
θ̌
notation in the remaining of the proof we will use use the following notation: If A, B are
random variables we write P(A ≷ c1 , B ≶ c2 ) := P((A > c1 ∩ B < c2 ) ∪ (A < c1 ∩ B > c2 )).
b βbθ− ) ≶ 0, S(
b βbθ+ ) ≷ 0) ≤ inf β∈Ω Pβ (θ −  <
Then following inequality holds inf β∈Ω Pβ (S(
θe < θ + ). Next for small enough  > 0 such that θ ±  ∈ Nθ , we have:
inf Pβ (vT Et (βθ− ) ≶ 0, vT Et (βθ+ ) ≷ 0)

β∈Ω

b βbθ− ) ≷ 2vT Et (βθ− ), S(
b βbθ+ ) ≶ 2vT Et (βθ+ ))
− sup Pβ (S(
β∈Ω

b βbθ− ) ≶ 0, S(
b βbθ+ ) ≷ 0).
≤ inf Pβ (S(
β∈Ω

The LHS goes to 1 by (E.6), and hence the proof is complete in this case. In the case when
b βb ) are non-decreasing, exactly the same argument goes through.
θ̌ 7→ S(
θ̌
Lemma 2. Let Xn (r) and ξn (r) be two sequences of random variables, depending on a
parameter r ∈ R. Suppose that limn supr∈R supt |Pr (Xn (r) ≤ t) − F (t)| = 0 where F is
a continuous cdf, and limn inf r∈R Pr (|1 − ξn (r)| ≤ τ (n)) = 1 for τ (n) = o(1). Assume in
addition that F is Lipschitz, i.e. there exist κ > 0, such that for any t, s ∈ R : |F (t)−F (s)| ≤
κ|t − s|. Then we have:


Xn (r)
lim sup sup Pr
≤ t − F (t) = 0.
n r∈R t
ξn (r)
Proof of Lemma 2. The proof follows by a direct calculation, and we omit the details.
Lemma 3. Under Assumptions 9 — 12, we have:


b βbθ ) − S(β) ≤ r1 (n)r5 (n) + r2 (n)r3 (n) = 1.
lim inf Pβ S(
n→∞ β∈Ω

(E.7)

If in addition n1/2 (r1 (n)r5 (n) + r2 (n)r3 (n)) = o(1), we have:
b βbθ ) ≤ t) − Φ(t)| = 0.
lim sup sup |Pβ (σ −1 n1/2 S(

n→∞ β∈Ω

(E.8)

t

Proof of Lemma 3. Let Giβ be the event inside the probability measures in assumptions 9
— 12 corresponding to the rate ri (n) for i = 1, . . . , 5. It is clear that inf β∈Ω Pβ (G β ) ≥
P
1 − 5i=1 supβ∈Ω Pβ [(Giβ )c ] → 1. Next, the proof of (E.7) can be done through the same
argument as in the proof of Theorem 1, but using the uniform convergence assumptions.
Note that the bounds (E.3) and (E.4) continue to hold on the event G β = G1β ∩ . . . ∩ G5β .
Hence by Assumptions 9 and 10 the proof of (E.7) is complete.

35

Next we show (E.8). Let κ(n) = n1/2 C −1/2 (r1 (n)r5 (n) + r2 (n)r3 (n)), where we recall the
definition of C: inf β∈Ω vT Σv ≥ C > 0. Then we have:
b βbθ ) ≤ t) ≤ Pβ (σ −1 n1/2 S(
b βbθ ) ≤ t, G β ) + Pβ ((G β )c )
Pβ (σ −1 n1/2 S(
≤ Pβ (σ −1 n1/2 S(β) ≤ t + κ(n)) + Pβ ((G β )c ).
The above implies the following inequality:
b βbθ ) ≤ t) − Φ(t)
Pβ (σ −1 n1/2 S(
≤ Pβ (σ −1 n1/2 S(β) ≤ t + κ(n)) − Φ(t + κ(n)) + (Φ(t + κ(n)) − Φ(t)) + Pβ ((G β )c )
κ(n)
≤ Pβ (σ −1 n1/2 S(β) ≤ t + κ(n)) − Φ(t + κ(n)) + √ + Pβ ((G β )c ),
2π
where we took into account the fact that Φ is Lipschitz with constant ≤ √12π . Now using
Assumption 11, the fact that κ(n) = o(1) and Pβ ((G β )c ) = o(1) we conclude that:
b βbθ ) ≤ t) − Φ(t) ≤ 0.
lim sup sup sup Pβ (σ −1 n1/2 S(
n→∞

β∈Ω

t

With a similar argument one can show the converse, namely:
b βbθ ) ≤ t) − Φ(t) ≥ 0.
lim inf inf inf Pβ (σ −1 n1/2 S(
n→∞ β∈Ω t

This concludes the proof of (E.8).
Proof of Theorem 3. By Assumption 13, we have:





r6 (n)
r6 (n)
−1
inf Pβ 1 − σ
bσ
≤
≥ Pβ |b
≥ inf Pβ |b
σ − σ| ≤ √
σ 2 − σ 2 | ≤ r6 (n)
β
β
C
C
= 1 − o(1),
(E.9)
where recall that inf β∈Ω vT Σv ≥ C > 0. The last expression implies that: Next define:


σ
bσ −1 T ∂
−1
T
e
b
b [T(Z, βθ )]∗1 , ηn (β, ν) =
v
[T(Z, βeν )]∗1 (θe − θ),
ζn (β) = σ
bσ
v
2
∂θ
where βeν = ν βbθe + (1 − ν)βbθ and let ξn (β, ν) = ζn (β) + ηn (β, ν).
We will show that
lim inf inf Pβ (|1 − ξn (β, ν)| ≤ τ (n)) = 1,

(E.10)

n β∈Ω ν∈[0,1]

for some τ (n) = o(1), or equivalently — for every  > 0 : supβ∈Ω supν∈[0,1] Pβ (|1 − ξn (β, ν)| >
) = o(1). We proceed with the following:
sup sup Pβ (|1 − ξn (β, ν)| > ) ≤ sup Pβ (|1 − ζn (β)| > /2) + sup sup Pβ (|ηn (β, ν)| > /2) .
β∈Ω ν∈[0,1]
β∈Ω
{z
} |
|
{z
}

β∈Ω ν∈[0,1]

I1

36

I2

First we tackle I1 . We have:
bT [T(Z, βeθ )]∗1 | > /8),
I1 ≤ sup Pβ (|1 − σ
bσ −1 | > /4) + sup Pβ (|b
σ σ −1 | > 2) + sup Pβ (|1 − v
β∈Ω

β∈Ω

β∈Ω

and all of the terms on the RHS are o(1) due to (E.9) and Assumption 12 respectively.
Next we handle I2 term. Let E = supβ∈Ω Eβ ψ(Z), where the function ψ is defined in
Assumption 12. Fix an α > 0, and proceed as:
I2 ≤ sup Pβ (|b
σ σ −1 | ≥ 2) + sup Pβ (|θe − θ∗ | > E −1 α/2) + sup Pβ (ψ(Z) ≥ α−1 E) ≤ o(1) + α,
β∈Ω

β∈Ω

β∈Ω

where the last inequality follows from (E.9), Proposition 1 and Markov’s inequality. Taking
the limit n → ∞ shows that limn supβ∈Ω supν∈[0,1] Pβ (|ηn (β, ν)| > /2) ≤ α. Taking α → 0
shows (E.10). Next observe that by (E.5) we have the following identity:
b βbθ )
n1/2 S(
n1/2 (θe − θ)
=−
.
σ
b
σξn (β, ν)

(E.11)

Now combining the fact that (E.10) with our results from Lemmas 2 and 3 in addition to
(E.11) completes the proof.
Proof of Proposition 2. Note that the only thing left to show is the consistency of the plugin
b v for v∗T Σv∗ , with the rest of the argument following from Theorem 2 and
bT Σb
estimate v
Slutsky’s theorem. By the triangle inequality we have:
b v − v∗T Σv∗ | ≤ kb
b v − v∗ )k∞ +2 kv∗T Σk
b ∞ kb
b − Σkmax
|b
vT Σb
vT − v∗ k1 kΣ(b
v − v∗ k1 + kv∗ k21 kΣ
|
{z
}
|
{z
} |
{z
}
I1

I2

I3

Next we control |I1 | ≤ Op (r2 (n)2 r7 (n) + kΣkmax r22 (n)) = op (1). Next
|I2 | ≤ 2Op (kv∗ k1 r2 (n)r7 (n) + kv∗T Σk∞ r2 (n)) = op (1).
Finally, for I3 we have |I3 | ≤ kv∗ k21 Op (r7 (n)) = op (1).

F

Proofs for the Dantzig Selector

We recall the definition of restricted eigenvalue (RE) assumption (Bickel et al., 2009).
Definition F.1 (RE). We say that the symmetric positive semi-definite matrix Mk×k possesses the restricted eigenvalue property if:

 T
u Mu
d
REM (s, ξ) =
min
min
: u ∈ R \ {0}, kuS c k1 ≤ ξkuS k1 > 0.
S⊂{1,...,k},|S|≤s
kuS k22
37

Definition F.2. Denote with X the n × d matrix whose rows are the XiT vectors stacked
together. Let Y be the an n × 1 vector stacking the observations Yi for i = 1, . . . , n and let
ε = Y − Xβ ∗ .
Proof of Corollary 1. We will prove this result by validating all of the assumptions required
of the general Theorem
Assumption
(2.8), observe that from Lemma

 p7, we have

 2. Regarding
p
∗
∗
∗
b
bk1 = Op kv k1 sv log d/n and by Lemma 9 — kβ − βk1 = Op s log d/n .
that kv − v
Assumption 1 can be verified as follows. To see (2.5), fix a |θ − θ∗ | < , for some  > 0.
Next by the triangle inequality:
Σn βθ∗ − n−1 XT Y − ΣX (βθ∗ − β ∗ )

≤ kn−1 XT εk∞ + kΣn,∗1 − ΣX,∗1 k∞ .
∞

p
The two terms on the RHS are Op ( log d/n), by the proof of Lemma 8 (see F.6) and
Lemma 5.p The same logic shows that |v∗T Σn βθ∗ − n−1 v∗T XT Y − v∗T ΣX,∗1 (θ − θ∗ )| =
Op (kv∗ k1 log d/n), which implies
p (2.6). Since the Hessian T in (2.7) is free of β we are allowed to set r3 (n) = λ0  kv∗ k1 log d/n = o(1) (by Lemma 7). Finally the two expectations
in Assumption 1, are bounded as we see below:
2
kΣX (βθ∗ − β ∗ )k∞ ≤ kΣX,∗1 k∞  ≤ 2KX
,

kv∗T ΣX,−1 k∞ = 0.

By adding up the following two identities:

  p

p
√
nOp kv∗ k1 log d/n Op s log d/n = op (1),

 p

p
√
√ 
nOp kv∗ k1 sv log d/n Op
log d/n = Op kv∗ k1 sv log d/ n = op (1),
we get that (2.11) is also valid in this case.
To verify the consistency of θe we check the assumptions in Theorem 1. Clearly the
map θ 7→ v∗T ΣX (βθ∗ − β ∗ ) = (θ − θ∗ ) has a unique 0 when θ = θ∗ . Moreover, the map
bT (Σn βbθ − n−1 XT Y ) is continuous as it is linear. In addition, it has a unique zero
θ 7→ v
bT Σn,∗1 = 0. However note that |b
except in cases when v
vT Σn,∗1 − 1| ≤ λ0 by (3.1), and hence
for small enough values of λ0 a unique zero will always exist.
Assumption 3 is verified in Lemma 4. We move on to show (2.10). Clearly (2.10) is trivial
b is a consistent estimate of
as its LHS ≡ 0 in this case. Finally Proposition 4 checks that ∆
∆. This completes the proof.
Remark 4. In fact, under the additional assumption s3v /n = o(1), the proof of Corollary 1
implies that the uniform types of assumptions in Section A are satisfied, and hence under
the same assumptions as in Corollary 1, we have:
bn ≤ t) − Φ(t))| = 0.
lim sup sup |Pβ (U

n→∞ kβk ≤s t∈R
0

38

By Remark 2 the above equality readily translates from estimator uniform consistency to confidence region uniform consistency. It is noteworthy to mention that the space of uniformity is
Ω = {β : kβk0 ≤ s}, provided that the conditions of Corollary 1 hold, which includes
p that the
√
∗
∗
∗ 2
covariates X satisfy sv = kv k0 and max(sv , s)kv k1 log d/ n = o(1), kv k1 log d/n =
o(1).
−2
Remark 5. Note here that it is implied that λ0 = o(1) and hence since kv∗ k1 ≥ 2KX
it
follows that λ = o(1) as well.
√
√
Remark 6. Observe that kv∗ k1 ≤ sv kv∗ k2 ≤ sv δ. This yields sufficient conditions by
√
substituting kv∗ k1 with sv . Moreover, under the assumption that v∗T X is sub-Gaussian,
we can further relax the requirements on sparsity sv dimension d and number of observations
n.
√
Lemma 4. Assume that condition 6 holds and max(sv , s)kv∗ k1 log d/ n = o(1). Then
∆−1/2 n1/2 S(β ∗ )
N (0, 1).

Proof of Lemma 4. To show the weak convergence we verify Lyapunov’s condition for the
−2 Pn
4
∗T
T ∗
CLT. We need to show that n∆2
converges to 0. Note that
i=1 E v Xi (Xi β − Yi )
we have ∆2 ≥ λmin (ΣX )kv∗ k42 Var(ε)2 = O(1)kv∗ k42 . Therefore it suffices to consider the
following expression:
n
n−2 X
E v∗T Xi (XiT β ∗ − Yi )
kv∗ k42 i=1

4

≤n

−2

n
X

E k(Xi εi )Sv k42 ≤ n−1 s2v M,

(F.1)

i=1

where M = 28 (KKX )4 , and the last inequality holding from Lemma 12. Using the fact that
√
−2
kv∗ k1 ≥ 2KX
as seen in Remark 5, we have that max(sv , s)kv∗ k1 log d/ n = o(1) implies
s2v /n = o(1) and completes the proof.
Remark 7. Using the Berry-Esseen theorem for non-identical random variables in combination with Lemma 12 we can further show:

 1/2
n
∗
∗
sup P √ S(β ) ≤ t − Φ(t) ≤ CBE (6KKX )3 n−1/2 sv3/2 = o(1),
t
∆
where M and CBE are absolute constants.
Proposition 4. Under Assumption 6, and the following additional assumption
b →p ∆.
o(1), we have that ∆

kv∗ k21

q

log d
n

=

Proof of Proposition 4. We show that each of the two sums is corresponding to its population
counterpart, and then the proof follows upon an application of Slutsky’s theorem. We start

39

with the first term:
n

n

1X T
1X T
(b
v Xi )2 − v∗T ΣX v∗ ≤
[(b
v Xi )2 − (v∗T Xi )2 ] + | v∗T Σn v∗ − v∗T ΣX v∗ |,
|
{z
}
n i=1
n i=1
I2
|
{z
}
I1

∗

bk∞ + kΣn v∗ k∞ ).
|I1 | ≤ kb
v − v k1 (kΣn v


p
bk1 = Op kv∗ k1 sv log d/n , and by definition
We know from Lemma 7, that kv∗ − v
bk∞ ≤ 1 + λ0 . In the proof of Lemma 7 we also show that
kΣn v


p
∗
∗
kΣn v k∞ = 1 + Op kv k1 log d/n ,
p
a large enough
upon appropriately choosing
λ0  kv∗ k1 log

 d/n, with

 proportionality
p
p
= op (1) we have
constant. Thus since Op kv∗ k1 sv log d/n 2 + Op kv∗ k1 log d/n
∗ 2
shown |I1 | = op (1). We
p next tackle |I2 | ≤ kv k1 kΣn − ΣX kmax . Lemma 5 gives us that
kΣn − ΣX
pkmax = Op ( log d/n), and thus because of our extra assumption we have |I2 | =
∗ 2
Op (kv k1 log d/n) = op (1).
Now we turn to the second part of the proof:
n

1X
b 2 − Var(ε)
(Yi − XiT β)
n i=1
n

n

n

X
1X 2
1X
b 2− 1
(Yi − XiT β)
(Yi − XiT β ∗ )2 +
ε − Var(ε) .
≤
n i=1
n i=1
n i=1 i
{z
}
{z
}
|
|
I3

I4

The term I4 is clearly op (1) because of the LLN (εi are centered and have finite variance as
sub-Gaussian random variables). Thus we are left to deal with I3 :
n

1
2X T b
|I3 | ≤ kX(βb − β ∗ )k22 +
|Xi (β − β ∗ )||εi |
n
n i=1
v
u n
uX
1
2
∗ 2
∗
b
b
≤ kX(β − β )k2 + kX(β − β )k2 t
ε2i ,
n
n
i=1
where Xn×d is a matrix, with rows XiT stacked together.
in Lemma 9 gives us that
q (F.8)
P
n
s
log
d
1
1
∗
2
kX(βb − β )k2 = Op ( n ) = op (1), and since by LLN n i=1 ε2i = Op (1), we have |I3 | =
n
op (1), which shows the consistency of the second estimator and concludes the proof.
2

Lemma 5. We have that with probability at least 1 − 2d2−c̄AX :
p
2
log d/n.
kΣn − ΣX kmax ≤ 4AX KX
40

Note. The constant c̄ is a universal constant independent of the X distribution, KX
is as
p defined in the main text, and AX > 0 is an arbitrarily chosen constant satisfying
AX log d/n ≤ 1.
Proof of Lemma 5. First we note that the elements of the matrix – X ⊗2 are sub-exponential
random variables. This fact can be seen since by Cauchy-Schwartz, one can easily obtain
that:
2
.
kXi Xj kψ1 ≤ 2kXi kψ2 kXj kψ2 ≤ 2KX

(F.2)

2
Next by the triangle inequality it is clear that kXi Xj − EXi Xj kψ1 ≤ 4KX
. The proof is
completed by applying a standard Bernstein tail bound (see Proposition 5.16 in Vershynin
(2010) e.g.).

Lemma 6. Assume the same conditions
assume further that the minip as in Lemma 5, and
λmin (ΣX )
mum eigenvalue λmin (ΣX ) > 0 and s log d/n ≤ (1 − κ) (1+ξ)2 4AX K 2 , where 0 < κ < 1. We
X
then have that Σn satisfies the RE property with REΣn (s, ξ) ≥ κ REΣX (s, ξ) ≥ κλmin (ΣX ) >
2
0 with probability at least 1 − 2d2−c̄AX .
Proof of Lemma 6. The proof follows a standard argument so omit the details.
Definition F.3. For a fixed 0 < κ < 1, let REκ (s, ξ) = κ REΣX (s, ξ).
p
λmin (ΣX )
Lemma 7. Assume that — λmin (ΣX ) > δ > 0, sv log d/n ≤ (1 − κ) (1+1)
2 4A K 2 , where
X X
p
0s
0
∗
2
∗
v
0 < κ < 1 and λ ≥ kv k1 4AX KX log d/n. Then we have that kb
v − v k1 ≤ RE8λ
with
κ (sv ,1)
2

probability at least 1 − 2d2−c̄AX . Additionally we have:
kb
vSvc − vS∗ vc k1 ≤ kb
vSv − vS∗ v k1 .

(F.3)

Proof of Lemma 7. The proof follows a standard argument so omit the details.
p
Lemma 8. Assume the same conditions as in Lemma
5
and
that
log d/n ≤ C for some
q
constant C. Let S = supp(β ∗ ), and let λ = AK logn d . Then, with probability at least
1−

cA2
2(1+2CAX )K 2
X

2

1−ed
−2d2−c̄AX (where c is a universal constant independent of the distribution
of ε, K = kεkψ2 , and the other constants are defined in Lemma 5) we have:
kβbS c − βS∗ c k1 ≤ kβbS − βS∗ k1 ,
b
Σn (β ∗ − β)

41

∞

≤ 2λ.

and:

(F.4)

(F.5)

Proof of Lemma 8. Note that by a Hoeffding’s type of inequality for sub-Gaussian random
variables (see Proposition 5.10 (Vershynin, 2010)) and the union bound, we have:




cnt2
1 T
X ε
≥ t X ≤ ed exp − 2
,
(F.6)
P
n
K kΣn kmax
∞
where c is a universal constant. The remainder of the proof follows by standard arguments
so we omit the details.
Lemma 9. Assume the same conditions as in Lemmas 5, 6 (with ξ = 1), and 8,qso that Σn
satisfies the RE assumption with REκ (s, 1) with high probability. Set λ = AK logn d , as in
1−

Lemma 8. Then with probability at least 1 − ed

cA2
2(1+2CAX )K 2
X

2

− 2d2−c̄AX we have:

p
8AK
s log d/n,
REκ (s, 1)
16A2 K 2
s log d.
kX(βb − β ∗ )k22 ≤
REκ (s, 1)

kβb − β ∗ k1 ≤

(F.7)
(F.8)

Proof of Lemma 9. The proof follows by standard arguments and we omit the details.
Lemma 10. Let {Xi }ni=1 are identical (not necessarily independent), d-dimensional subGaussian vectors with max1≤i≤n,1≤j≤d kXij kψ2 = K. Then we have:
max kXi⊗2 kmax = Op (log(nd)).

i=1,...,n

Proof of Lemma 10. The proof follows after an application of a Bernstein type of of tail
bound (Vershynin, 2010, see e.g.) and we omit the details.
Lemma 11. Let Xi , i = 1 . . . k are sub-exponential with kXi kψ` ≤ U , for some ` ≥ 1 and
denote by X the vector with entries Xi . Then for any p, q ≥ 1 we have:
1/(qp)
EkXkpq ≤ [E[kXkpq
≤ (pq)p/` U p k p/q
q ]]

Proof of Lemma 11. We apply Jensen’s followed by Minkowski’s inequality to obtain the
following:
1/(qp)
[E[kXkpq ]]1/p ≤ [E[kXkpq
≤ [k(E(Xi )pq )1/q ]1/p ≤ (pq)1/` U k 1/p ,
q ]]

where the last inequality follows by the definition of ψ` norm. Raising this inequality to the
power of p finishes the proof.
Lemma 12. Let R ⊂ {1, . . . , d} with |R| = r. Then we have the following:
Ek(Xε)R k42 ≤ r2 28 (KKX )4 .
p
p
Proof of Lemma 12. Simply observe that Ek(Xε)R k42 ≤
E|ε|8 Ek(X)R k82 , and apply
Lemma 11 for ψ2 .
42

G

Proofs for IVR

Definition G.1 (CS). For the (not necessarily symmetric) matrix Mk×k we define its
coordinate-wise sensitivity with respect to the L1 norm by:

CSM (s, ξ) =
min
min skMuk∞ : u ∈ Rd \ {0}, kuS c k1 ≤ ξkuS k1 , kuS k1 = 1 > 0.
S⊂{1,...,k},|S|≤s

This definition is inspired by Gautier and Tsybakov (2011).
Definition G.2. Denote with X and W the n×d matrices whose rows are the XiT and WiT
vectors stacked together respectively. Let Y be the an n × 1 vector stacking the observations
Yi for i = 1, . . . , n and let ε = Y − Xβ ∗ .
Proof of Corollary 5. The proof is the same as the proof of Corollary 1 upon usages of the
Lemmas developed in this section. We omit the details.
Remark 8. In fact, the proof of Corollary 5 implies that the uniform types of assumptions
in Section A are satisfied, and hence under the same assumptions as in Corollary 5, we have:
bn ≤ t) − Φ(t))| = 0.
lim sup sup |Pβ (U

n→∞ kβk ≤s t∈R
0

√
Lemma 13. Assume that condition 6 holds and max(sv , s)(kv∗ k1 ∨ 1) log d/ n = o(1).
Then:
∆−1/2 n1/2 S(β ∗ )
N (0, 1).
Proof of Lemma 13. The proof is the same as that of Lemma 4 after using the Lemmas
developed below. We omit the details.
Remark 9. Using the Berry-Esseen theorem for non-identical random variables in combination with Lemma 12 we can further show:

 1/2
n
∗
∗
sup P √ S(β ) ≤ t − Φ(t) ≤ CBE (6KKW X )3 n−1/2 s3/2
v = o(1),
t
∆
where M and CBE are absolute constants.
Proposition 5. Under assumption 6, and the following additional assumption:
p
kv∗ k21 log d/n = o(1),
b →p ∆.
we have that ∆

43

Proof of Proposition 5. By the triangle inequality, for any two vectors a and b we have
|kak2 − kbk2 | ≤ ka − bk2 . Making multiple usages of this inequality one realizes that it
suffices to show:
n

−1

n
X

∗

b T Xi )2 = op (1), n−1
b) Wi ) ((β − β)
((v − v
T

2

∗

n
X

b T Xi )2 = op (1),
(v∗T Wi )2 ((β ∗ − β)

i=1

i=1

n−1

n
X

b)T Wi )2 ε2i = op (1), n−1
((v∗ − v

i=1

n
X

(v∗T Wi )2 ε2i − E(v∗T Wi )2 ε2i = op (1),

i=1

and E(v∗T Wi )2 ε2i < ∞. We show these convergences in turn. For the first term we have:
−1

n

n
X
b 2 Op (log(nd)2 ) = op (1),
b T Xi )2 ≤ kv∗ − v
b)T Wi )2 ((β ∗ − β)
bk21 kβ ∗ − βk
((v∗ − v
1
i=1

with high probability, where use used Lemma 10 and Lemmas 18 and 16. For the second
term:
−1

n

n
X

∗T

b T Xi )2 ≤ kβ ∗ − βk
b 2 max kXi k2 n−1
(v Wi ) ((β − β)
1
∞
2

∗

i=1,...,n

i=1

≤ Op

(v∗T Wi )2

i=1

 s2 log d log(nd) 
n

n
X

n
X
−1
n
(v∗T Wi )2 ,
i=1

with high probability. By Lemma 14 we have:
−1

n

n
X
X
(v∗T Wi )2 ≤ kv∗ k21 kn−1
Wi⊗2 − ΣW W kmax + v∗T ΣW W v∗ = Op (1),
|
{z
}
i=1
i=1
≤D
max
}
|
√{z
Op (

log d/n)

which combined with the bound in the previous display completes the proof for the second
term. The third term bound follows upon noticing:
−1

n

n
 s2 log d log(nd) 
X
X
b)T Wi )2 ε2i ≤ kb
Op (1)
((v∗ − v
v − v∗ k21 max kWi k2∞ n−1
ε2i ≤ Op
n
| {z }
i=1
Op (1)

= op (1).
Moving to the last term we have:
n−1

n
X

(v∗T Wi )2 ε2i − E(v∗T Wi )2 ε2i ≤ kv∗ k21 kn−1

i=1

n
X
i=1

44

⊗2 2
ε − ΣW W ,Sv Sv σ 2 k∞ ,
Wi,S
v i

where Sv = supp(v∗ ). The final concentration is handled in Lemma 19. Applying this lemma
in conjunction with the union bound gives us the existence of a constant CKW X depending
on K and KW X such that:
p
n
k
X
k/n + k 2 /n]k
⊗2 2
2
2 CKW X [
−1
Wi,Sv εi − ΣW W ,Sv Sv σ k∞ ≥ t) ≤ sv
P(kn
,
tk
i=1
for all k ∈ N. Selecting t = 2e4 CKW X

q

log d
,
n

k = dmin(log d, (n log d)1/4 )e brings the above

bound of the order O(s2v exp(−4dmin(log d, (n log d)1/4 )e)) = o(1), and shows that:
r
n

X
log d 
(v∗T Wi )2 ε2i − E(v∗T Wi )2 ε2i ≤ O kv∗ k21
n−1
= o(1).
n
i=1
We conclude the proof with noticing that E[E[(v∗T Wi )2 ε2i |W ]] = σ 2 E[v∗T Wi⊗2 v∗ ] < ∞.
2

Lemma 14. We have that with probability at least 1 − 2d2−c̄AX :
n

1X
([WiT , XiT ]T )⊗2 − Σ
n i=1

2
= kΣn − Σkmax ≤ 4AW X KW
X

p

log d/n.

max

Note. The constant c̄ is a universal constant independent of the X and W distributions,
KW Xpis as defined in the main text, and AW X > 0 is an arbitrarily chosen constant satisfying
AW X log d/n ≤ 1.
Proof of Lemma 14. Proof is follows by the same argument as in Lemma 5, so we omit the
details.
Lemma 15. Assume the same conditions as in Lemma 14, and assume further
p that the
matrix ΣW X satisfies CSΣW X (s, ξ) > κ∗ and that s is sufficiently small so that s log d/n ≤
∗
(1 − κ) (1+ξ)4AκW X K 2 , where 0 < κ < 1. We then have that ΣW X,n satisfies the CS property
WX

2

with CSΣW X,n (s, ξ) ≥ κ CSΣW X (s, ξ) > 0 with probability at least 1 − 2d2−c̄AW X .
Proof of Lemma 15. This proof is simply using Definition G.1 and Lemma 14.
Definition G.3. For a fixed 0 < κ < 1, let CSκ (s, ξ) = κ CSΣW X (s, ξ).
Lemma 16. Assume that CSΣW X (sv , 1) ≥ κ∗ > 0, and that further sv is small enough
q so
p
log d
κ∗
2
that sv log d/n ≤ (1−κ) (1+1)4AW X K 2 , where 0 < κ < 1 and λ0 ≥ kv∗ k1 4AW X KW
.
X
n
WX

Then we have that kb
v − v ∗ k1 ≤

8λ0 sv
CSΣW X (sv ,1)

2

with probability at least 1 − 2d2−c̄AW X .

45

Proof of Lemma 16. Using a standard argument and Lemma 14 we can show that with
2
probability at least 1 − 2d2−2c̄AW X , v∗ satisfies (C.1) and consequently
n

1X
(b
v − v∗ )T Wi XiT
n i=1

n

∞

1X T
b Wi XiT − e1
≤
v
n i=1

n

1 X ∗T
+
v Wi XiT − e1
n
∞
i=1

≤ 2λ0 .
∞

(G.1)
Let Sv = supp(v∗ ), with sv = |Sv |. Using the formulation of program (C.1) it is not
hard to show that:
vSv − vS∗ v k1 .
kb
vSvc − vS∗ vc k1 ≤ kb

(G.2)

By Lemma 15, ΣW X,n satisfies the CS assumption under our conditions and hence
kb
vSv − vS∗ v k1 CSΣW X (sv , 1)
≤ kΣW X,n (b
v − v∗ )k∞
sv

by (G.1)

≤

2λ0

Hence by (G.2) we conclude kb
v − v∗ k1 ≤ 4sv λ0 / CSΣW X (sv , 1), which is what we wanted to
show.
p
Lemma 17. Assume the same conditions as in Lemma
14
and
that
log d/n ≤ C for some
q
constant C. Let S = supp(β ∗ ), and let λ = AK logn d . Then, with probability at least
1 − 2d1−(cA

2 )/(4K 2
XX )

(where c is a universal constant Lemma 14) we have:
kβbS c − βS∗ c k1 ≤ kβbS − βS∗ k1 ,

(G.3)

and:
b
ΣW X,n (β ∗ − β)

∞

≤ 2λ.

(G.4)

Proof of Lemma 17. Note that by a Bernstein type of inequality for sub-exponential random
variables (see Proposition 5.16 (Vershynin, 2010)) and the union bound, we have:

P

1 T
W ε
n




≥ t ≤ 2d exp −c min
∞


nt2
nt
,
,
2
4K 2 KW
X 2KKW X

(G.5)

where c is a universal constant, and we used the fact that maxi∈{1,...,d} kεWi kψ1 ≤ 2KKZX .
Set t =
Provided that A ≤ 2KW X the above probability bounds gives us that the event
 λ.
2
2
1
E :=
WT ε ∞ ≤ λ holds with probability at least 1 − 2d1−(cA )/(4KXX ) .
n
Note that when E holds, the true parameter satisfies the Dantzig selector constraint and
thus we can obtain (G.3) in the same manner as in Lemma 16. Using the triangle inequality
on E shows (G.4).
46

Lemma 18. Assume the same conditions in Lemmas 14, 15 (with ξ = 1), and 17, so
q that
ΣW X,n satisfies the CS assumption with CSκ (s, 1) with high probability. Set λ = AK logn d ,
as in Lemma 17. Then with probability at least 1 − 2d1−(cA
kβb − β ∗ k1 ≤

2 )/(4K 2
XX )

we have:

4AK p
s log d/n.
CSκ (s, 1)

(G.6)

Proof. Recall from Lemma 17, that on the event E we have that (G.3) and (G.4) hold, and
furthermore n1 WT W = ΣW X,n satisfies the CS condition. Thus on the event E, we have:
kβbS − βS∗ k1 CSκ (s, 1)
b ∞ ≤ 2λ.
≤ kΣW X,n (β ∗ − β)k
s
To get (G.6), note that by (G.3) we have: kβb − β ∗ k1 ≤ 2kβbS − βS∗ k1 ≤
done.

4AKλs
,
CSκ (s,1)

and we are

Lemma 19. Let {Xi }ni=1 be an i.i.d. collection of sub-Gaussian random variables satisfying
kXi kψ2 ≤ K. Then we have:
p
n

 K
X
e k [ k/n + k 2 /n]k
4
−1
4
4
,
P |n
Xi − EXi | ≥ t ≤
k
t
i=1
e 4 depending solely on K.
for any k ∈ N and some fixed constant K
Proof. We make usage of Theorem 1.4 of Adamczak and Wolff (2015), which provides a convenient concentration bound for higher moments of sub-Gaussian random variables.
Using
p
Pn
4 k 1/k
4
−1
e
≤ K4 [ k/n + k 2 /n],
this result it is not hard to check that: [E|n
i=1 Xi − EXi | ]
e 4 is a constant depending solely on K. Consequently, applying Markov’s inequality
where K
we obtain the final conclusion.

H
H.1

Proofs for Graphical Models
Proofs for Graphical Models with CLIME

Proof of Corollary 2. Before we proceed with the proof note that we are guaranteed to have
−1
2 −1
2 −1
kv∗ k1 ≥ (Σ−1
≥ (2KX
) > 0, and similarly kβ ∗ k1 ≥ (2KX
) > 0. Hence,
X )11 ≥ (ΣX,11 )
∗
∗
∗
∗
max(sv kv k1 , skβ k1 )kv k1 kβ k1 log d log(nd)/n = o(1) implies that
√
max(sv , s)kv∗ k1 kβ ∗ k1 log d/ n = o(1).
We show this result by verifying the conditions of Section
To see Assumption
(2.8),
 2.1.p

∗
∗
∗
b
we can use Lemma 7 to argue that kβ − β k1 = Op kβ k1 s log d/n , kb
v − v k1 =


p
Op kv∗ k1 sv log d/n provided that λ and λ0 are large enough.
47

Next we check Assumption 1. To see (2.5), fix a |θ − θ∗ | < , for some  > 0. By the
triangle inequality:
kΣn βθ∗ − ΣX βθ∗ k∞ ≤ kΣn − ΣX kmax (kβk∗1 + ).


p
∗
The RHS is Op kβk1 log d/n , by Lemma 5. The same logic shows that v∗T Σn βθ∗ −


p
v∗T ΣX βθ∗ = Op (kβ ∗ k1 + )kv∗ k1 log d/n , which implies (2.6). Since the Hessian T in
p
(2.7) is free of β we are allowed to set r3 (n) = λ0  kv∗ k1 log d/n = o(1) (by Lemma 7).
Finally the two expectations in Assumption 1, are bounded as we see below:
2
kΣX βθ∗ − eTm k∞ = kΣX (βθ∗ − β ∗ )k∞ ≤ kΣX,∗1 k∞  ≤ 2KX
,

kv∗T ΣX,−1 k∞ = 0.

By adding up the following two identities:

 

p
p
√
nOp kv∗ k1 log d/n Op kβ ∗ k1 s log d/n = op (1),

 

p
p
√
∗
∗
nOp kv k1 sv log d/n Op kβ k1 log d/n = op (1),
we get that (2.11) is also valid in this case after a usage of (3.6).
To verify the consistency of θe we check the assumptions in Theorem 1. Clearly the
map v∗T ΣX (βθ∗ − β ∗ ) = (θ − θ∗ ) has a unique 0 when θ = θ∗ . Moreover, the map θ 7→
bT (Σn βbθ − eTm ) is continuous as it is linear. In addition, it has a unique zero except in cases
v
bT Σn,∗1 = 0. However note that |b
when v
vT Σn,∗1 − 1| ≤ λ0 by (3.4), and hence for small
0
enough values of λ there will exist a unique zero.
Assumption 3 is verified in Lemma 20. Observe that (2.10) is trivial as its LHS ≡ 0 in
b is consistent for ∆ is verified in Lemma 21.
this case. Finally, the fact that ∆
Next, we proceed to formulate a uniform weak convergence result. To this end, for fixed
M > δ > 0, define the following parameter space of covariance matrices:
S(L, s) = {Σ : Σ = ΣT , 0 < δ ≤ λmin (Σ), kΣkmax ≤ M, kΣ−1 k1 ≤ L, max kΣ−1
∗j k0 ≤ s}.
j=1,...,d

We have the following result in terms of uniform convergence:
Corollary 8. Let (3.3) holds, and Cov(X) = ΣX ∈ S(L, s). Let Ω = (ΣX )−1 and denote
β = Ω∗m , and v = Ω∗1 . Assume there exist two constants Vmin and Vmax such that:
Var(vT X ⊗2 β) ≥ Vmin > 0,

E(vT X ⊗2 β)4 ≤ Vmax < ∞.

(H.1)

√
s3 / n = o(1),

(H.2)

Then under the following conditions:
sL3 log(d) log(nd)/n = o(1),

bn ≤ t) − Φ(t)| = 0.
we have limn→∞ supΣX ∈S(L,s) supt∈R |Pβ (U
48

The conditions in this Corollary are essentially the same as those in Corollary 2. Condition E(vT X ⊗2 β)4 ≤ Vmax ensures E(vT X ⊗2 β)2 < ∞ and Var((vT X ⊗2 β)2 ) = o(n). The
only other difference is that the second condition in (H.2) is stronger than the counterpart
in Corollary 2. We need this condition to apply the Berry-Esseen theorem to control the
normal approximation error uniformly.
Lemma 20. Under the assumptions of Corollary 2 we have that: ∆−1/2 n1/2 S(β ∗ )

N (0, 1).

Proof of Lemma 20. Similarly to Lemma 4 we will verify Lyapunov’s condition for the CLT.
It suffices to bound the quantity for some k > 2:
n
X

n−k/2

k/2
kv∗ kk2 kβ ∗ kk2 αmin i=1

k

E v∗T Xi⊗2 β ∗ − v∗T ΣX β ∗ ,

where we used assumption Assumption 7. By Cauchy-Schwartz we can bound the above
P
k
expression by following (up to a constant factor): n−k/2 ni=1 E (Xi⊗2 − ΣX )Sv ,S F , where
by subscripting the matrix we mean setting all elements not in the supports of v∗ or β ∗ (Sv ,
and S correspondigly) to 0, and k · kF is the Frobenius norm of the matrix. Finally using
Lemma 22 we conclude that we can control the expression above by n−k/2+1 (sv s)k/2 (8kKX )k ,
and hence the conclusion follows.
Remark 10. Using the Berry-Esseen theorem for non-identical random variables in combination with the bound we derived above, we can further show:

sup P∗ ∆−1/2 n1/2 S(β ∗ ) ≤ t − Φ(t) ≤ CBE n−1/2 (24KX )3 (sv s)3/2 = o(1),
t

where CBE is an absolute constant.
Lemma 21. Under the assumptions from Corollary 2, we have that the plugin estimator
P
b →
∆
∆.
⊗2 b 2
T
b 2 . Similarly to the analysis
b = 1 Pn (b
vT Σn β)
Proof of Lemma 21. Note that ∆
i=1 v Xi β) −(b
n
bT Σn βb is consistent for v∗T ΣX β ∗ under
of the first term in Proposition 4 one can show that v
P
b 2 − E(v∗T X ⊗2 β ∗ )2 | =
our assumptions. Hence it suffices to show that | n1 ni=1 (b
vT Xi⊗2 β)
X

n
−1
op (1). We start by arguing that n
(b
vT Xi⊗2 βb − v∗T Xi⊗2 β ∗ )2 , is asymptotically neglii=1

|

{z

}

I

gible.
I

1/2

1/2 
1/2

n
n
X
X
⊗2 b
⊗2 ∗ 2
−1
T
∗ 2
−1
∗ T
≤ n
(b
v Xi (β − β ))
+ n
((b
v − v ) Xi β )
.
i=1

|

i=1

{z
I1

}
49

|

{z
I2

}

We first handle I12 = (βb − β ∗ )T n−1

n
X

bv
bT Xi⊗2 (βb − β ∗ ). Using Lemma 10, we can
Xi⊗2 v

i=1

|

{z

}

M

bound M in the following way:
kMkmax ≤

max kXi⊗2 kmax n−1

n
X

b v k∞ .
bT Xi⊗2 v
b ≤ Op (log(nd))kb
v
vk1 kΣb

(H.3)

i=1

b vk∞ ≤ (1 + λ0 ). Hence:
b we have: kΣb
By the definition of v
kMkmax ≤ Op (log(nd))(kv∗ k1 + kb
v − v∗ k1 )(1 + λ0 ) = Op (log(nd))kv∗ k1 ,
p
p
v − v∗ k1 = Op (kv∗ k1 sv log d/n) which are
where we used that λ0  kv∗ k1 log d/n and kb
quantities going to 0 under our assumptions. Thus:

I12 ≤ kβb − β ∗ k21 kv∗ k1 Op (log(nd)) = Op kv∗ k1 kβ ∗ k21 s2 log d/n log(nd) = op (1),
By a similar argument we can show that I2 is of similar order. Putting everything together
we conclude:

I = Op max(s2v kv∗ k1 , s2 kβ ∗ k1 )kv∗ k1 kβ ∗ k1 log d log(nd)/n = op (1).
(H.4)
P
Next, we argue that n−1 ni=1 (v∗T Xi⊗2 β ∗ )2 − E(v∗T X ⊗2 β ∗ )2 is small. Recall that we
are assuming Var((v∗T X ⊗2 β ∗ )2 ) = o(n). A usage of Chebyshev’s inequality shows that
P
n−1 ni=1 (v∗T Xi⊗2 β ∗ )2 − E(v∗T X ⊗2 β ∗ )2 = op (1). Finally note that by the triangle inequality the following two inequalities hold:

1/2 
1/2
n
n
X
X
⊗2 b 2
⊗2 ∗ 2
−1
T
−1
∗T
n
(b
v Xi β)
≤ n
(v Xi β )
+ I 1/2 ,
i=1



i=1

1/2 
1/2
n
n
X
X
⊗2 ∗ 2
⊗2 b 2
−1
∗T
−1
T
n
(v Xi β )
≤ n
(b
v Xi β)
+ I 1/2 .
i=1

Observe that n
proof.

Pn
−1

i=1 (v

i=1
∗T

Xi⊗2 β ∗ )2 = E(v∗T X ⊗2 β ∗ )2 + op (1) = Op (1). This completes the

Proof of Corollary 8. To prove this corollary note that all bounds we showed in the proof
of Corollary 2 hold uniformly in the parameter set S(L, s). Note that as both v and β are
columns of Ω we have that kvk0 , kβk0 ≤ s, kvk1 , kβk1 ≤ L and M −1 ≤ kvk2 , kβk2 ≤ δ −1 .
These conditions in conjunction with the assumptions of the present result, can be seen to
imply the conditions from Section A and this completes the proof.
Lemma 22. Let Rv , R ⊂ {1, . . . , d} with |Rv | = rv , |R| = r. Then we have the following
k
2 k
E k(X ⊗2 − Σ)Rv ,R kF ≤ (rv r)k/2 (8kKX
) .
2
Proof. Apply (F.2) to get kXi Xj kψ1 ≤ 2KX
. Combined with the triangle inequality it gives
2
us kXi Xj − σij kψ1 ≤ 4KX . Next simply use Lemma 11 for ψ1 to complete the proof.

50

H.2

Proofs for Transelliptical Graphical Models

In the transelliptical case the lemmas from the CLIME case are no longer applicable, as the
estimator of Σ is constructed in a completely different manner. Furthermore, the vector X
is coming from a nonparanormal family and need not be sub-Gaussian. Fortunately, Liu
et al. (2012a) provide a concentration result which we state below:
Theorem 4 (Liu 2012). For any n > 1 with probability at least 1 − 1/d, we have
p
bτ − Σkmax ≤ 2.45π log d/n.
kS

(H.5)

While this theorem is defined within the framework of nonparanormal models, the proof
doesn’t utilize the fact that the family is nonparanormal, and thus extends to the transelliptical case. As we can see from the theorem, the rate of Kendall’s tau estimate (H.5), is no
different than the one using the sample covariance matrix, provided in Lemma 5.
Proof of Corollary 6. The proof of this result is the same as Corollary 2, except we use Σ
bτ in place of Σn , Lemma 25 in place of Lemma 7 and Theorem 4 in place
in place of ΣX , S
of Lemma 5. The only different step is the verification of Assumption 3 which we provide in
Lemma 23. We omit the rest of the details.
Lemma 23. Under the assumptions of Corollary 6 we have that ∆−1/2 n1/2 S(β ∗ )
where ∆ is defined as in (D.3).

N (0, 1),

Proof of Lemma 23. Note that by the mean value theorem we have the following representation:

 π 



  π
X
∗ ∗
bτ β ∗ − eT = n1/2 v∗T S
bτ − Σ β ∗ = n1/2
n1/2 v∗T S
−
sin
τjk
v
β
sin
τ
b
jk
m
j k
2
2
j∈S ,k∈S
v

j6=k

= n1/2

X



vj∗ βk∗ cos τjk

j∈Sv ,k∈S
j6=k

n1/2
−
2

X
j∈Sv ,k∈S
j6=k

vj∗ βk∗

π π
2

2

(b
τjk − τjk )

2
π  π
sin τejk
(b
τjk − τjk ) ,
2
2


where τeij is a number between τbij and τij . We will first deal with the first term in the sum
above. Since this term is a linear combination of second order (dependent) U -statistics, we
will make usage of Háejk’s projection method. A similar approach was used in the celebrated
paper of Hoeffding (1948). To this end we define the following notations:
0

ii
τjk
= sign ((Xij − Xi0 j )(Xik − Xi0 k )) − τjk ,
1 X ii0 |i
i
τ ,
τjk
=
n − 1 i0 6=i jk

51

ii0 |i

0

ii
τjk = E[τjk
|Xi ],
0

0

ii0 |i

ii0 |i0

ii
ii
= τjk
− τjk − τjk ,
wjk

2
n

In terms of these notations we therefore have τbjk − τjk =
This gives us the following identity:
n

X

1/2

vj∗ βk∗

j∈Sv ,k∈S
j6=k

Pn

i
i=1 τjk

+

2
n(n−1)

P

0

1≤i<i0 ≤n

ii
wjk
.

n
 πX
X
π π
∗ ∗
−1/2
i
cos τjk
vj βk cos τjk
(b
τjk − τjk ) = πn
τjk
2 2
2
i=1
j∈S ,k∈S



v

j6=k

{z
}
I1
 π X
X
π
ii0
+ 1/2
vj∗ βk∗ cos τjk
wjk
.
n (n − 1) j∈S ,k∈S
2 1≤i<i0 ≤n
|

v

j6=k

|

{z

}

I2

We first deal with I1 which can clearly be represented as a sum of iid mean 0 terms, by
verifying Lyapunov’s condition for the CLT. I1 can be rewritten as:
I1 = n−1/2

n
X

 π
i
τjk
vj∗ βk∗ π cos τjk
.
2
,k∈S

X

(H.6)

i=1 j∈Sv
j6=k

|

{z

}

Mi

Construct the matrix Θi ∈ Rd×d given entrywise by
 π
Θijk = π cos τjk
τ i , hence Θijj = 0.
2 jk

(H.7)

We can then rewrite Mi = v∗T Θi β ∗ = vS∗Tv ΘiSv ,S βS∗ . Calculating the variance of Mi gives
Var(Mi ) = E(v∗T Θi β ∗ )2 ≥ αmin kv∗ k22 kβ ∗ k22 , where the inequality follows by assumption.
We proceed to verify Lyapunov’s condition for some k > 2 (where we ignore the constant
αmin > 0):
n
n
X
X
(sv s)k/2 (2π)k
n−k/2
k
−k/2
i
k
E|M
|
≤
n
= o(1),
EkΘ
k
≤
i
Sv ,S F
nk/2−1
kv∗ kk2 kβ ∗ kk2 i=1
i=1

where the first inequality follows from Cauchy-Schwartz, and to see the second one notice
that each element of Θi is bounded |Θijk | ≤ 2π, and hence kΘiSv ,S kkF ≤ (sv s)k/2 (2π)k . This
implies that I1
N (0, ∆), with ∆ = E(v∗T Θi β ∗ )2 .
Next we deal with the second term I2 , which is mean 0, by showing that its (standardized) variance goes to 0 asymptotically. Before we compute its variance we make several
preliminary calculations:
0

0

0

0

0

rr0 |r

ii rr
ii rr
ii
τls
wls ) = E(τjk
τls ) − E(τjk
E(wjk
ii0 |i

rr0 |r0

+ E(τjk τls

ii0 |i0

0

rr0 |r0

) − E(τjk τlsrr ) + E(τjk τls

ii0 |i0

rr0 |r

ii
) − E(τjk
τls
rr0

ii0 |i

) − E(τjk τls ) + E(τjk τls

52

ii0 |i rr0 |r

0

ii0 |i0

rr0 |r0

) + E(τjk τls

).

)

In the expression above we have taken j 6= k, l 6= s, r 6= i 6= i0 6= r 6= r0 6= i. Notice now
ii0
rr0
that all elements above are independent and since E(wjk
) = E(wls
) = 0, we conclude that
ii0 rr0
0
E(wjk wls ) = 0. Following, the same logic, for j 6= k, l 6= s, i 6= i 6= r0 6= i:
0

0

0

0

0

ir0 |i

ii0 |i

ii0 |i ir0 |i

0

ii
ii ir
ii ir
τls ) − E(τjk τlsir ) + E(τjk τls )
τls ) − E(τjk
wls ) = E(τjk
E(wjk

where all the rest terms are 0, by the same argument as in the first case. Using iterated
expectation by conditioning on Xi it can be easily seen that all terms become equal to —
ii0 |i ir0 |i
ii0 ir0
E(τjk τjk ), and we can conclude that E(wjk
wls ) = 0. Since EI2 = 0, we have:
Var(I2 )
E(I22 )
≤
Var(Mi )
αmin kv∗ k22 kβ ∗ k22
2


=

≤

π2
αmin kv∗ k22 kβ ∗ k22 n(n − 1)2

X
1≤i<i0 ≤n

2
2  P
 P
∗
∗
36
k∈S |βk |
j∈Sv |vj |

π 2 n2

n(n − 1)2 αmin kv∗ k22 kβ ∗ k22

 π  0
ii 
wjk
vj∗ βk∗ cos τjk

2
,k∈S

 X
E

j∈Sv
j6=k

≤

π 2 18sv s
= o(1),
(n − 1)αmin
0

0

ii0 |i

ii0 |i0

ii
ii
where in the next to last inequality we used the trivial bound |wjk
| ≤ |τjk
|+|τjk |+|τjk | ≤ 6.
Var(I2 )
=
Thus the term Var(Mi ) = o(1) and therefore, Chebyshev’s inequality gives us that √ I2
Var(Mi )

op (1).
Finally we deal with the standardized version of the last term:
n1/2
Var(v∗T Θβ ∗ ) 2
1

p

 π  π
2
vj∗ βk∗ sin τejk
(b
τjk − τjk ) .
2
2
,k∈S

X

(H.8)

j∈Sv
j6=k

As we mentioned previously it’s clear that τbjk is a U -statistic, and its kernel is a bounded
function (between −1 and 1). Furthermore, we have that Eb
τjk = τjk . Thus, we can apply
Hoeffding’s inequality for U -statistics (see Hoeffding (1963) equation (5.7)), to obtain that:


nt2
2
.
(H.9)
P(sup |b
τjk − τjk | > t) ≤ 2d exp −
4
jk
p
It follows that selecting t = 9 log d/n suffices to keep the probability going to 0. Notice
that the (H.8) can be controlled by:
√

√
n1/2 π 2 sv s
sv s log d
∗
∗
2
kv k2 kβ k2 sup(b
τjk − τjk ) = Op
= op (1).
8θmin kv∗ k2 kβ ∗ k2
n1/2
jk
The last equation is implied by our assumption. This concludes the proof.
53

Remark 11. Using the Berry-Esseen theorem for non-identical
random variables we can

strengthen weak convergence statement to supt P∗ √I1∆ ≤ t − Φ(t) ≤ CBE n−1/2 (sv s)3/2 =
o(1), where CBE is an absolute constant. Note that we decomposed our test into
and hence this statement is valid more generally for Corollary 6.

√I1
∆

+ op (1),

b →p ∆.
Proposition 6. Under the same assumptions as in Corollary 6, we have that ∆
Proof of Proposition 6. Before
we go to the main proof, recall the definition of Θi (H.7),

π
i
i
. Note that in fact EΘi = 0, since Eτjk
= 0, and thus
where Θijk = π cos τjk 2 τjk
P
∗T
i ∗
∗T
i ∗ 2
b i = 0.
Var(v Θ β ) = E(v Θ β ) . Similarly one can note the simple identity: n1 ni=1 Θ
P
b 2 is consistent for E(v∗T Θi β ∗ )2 .
b i β)
Thus we will in fact focus on showing that n1 ni=1 (b
vT Θ
Consider the following decomposition:
n

n

n

X
1 X T bib 2
1 X T bib 2
b 2] + 1
b 2 − (v∗T Θ
b i β)
b i β)
b i β ∗ )2 ] .
(b
v Θ β) =
[(b
v Θ β) − (v∗T Θ
[(v∗T Θ
n i=1
n i=1
n i=1
|
{z
} |
{z
}
I1

I2

Below we show that I1 is asymptotically negligible. We have:
n

1 X b i b bT b i
b 2 (2π)2 ,
|I1 | = (b
v−v )
Θ β β Θ (b
v + v∗ )T ≤ kb
v − v∗ k1 kb
v + v∗ k1 kβk
1
n i=1
∗ T

b i kmax ≤ 2π. Thus by Lemma 25
where we made use of kΘ


p
|I1 | = Op kv∗ k21 kβ ∗ k21 sv log d/n = op (1),


kv∗ k21 kβ ∗ k21 s


p
log d/n = op (1). Next, we

by assumption. Similarly we obtain |I2 | = Op
P
b i β ∗ )2 − (v∗T Θi β ∗ )2 ]. Before we bound
inspect the following difference I3 = n1 ni=1 [(v∗T Θ
this term recall that we have the following useful inequality kΘi kmax ≤ 2π. Thus:
b i − Θi kmax .
|I3 | ≤ kv∗ k21 kβ ∗ k21 4π max kΘ
i=1,...,n

(H.10)

b i − Θi kmax we will use some concentration inequalities.
To bound the difference maxi=1,...,n kΘ


First, since cos is Lipschitz with constant 1 — cos π2 τbjk − cos π2 τjk ≤ π2 |b
τjk − τjk |, we
have:
π 
π 
π 
i
i
i
i
i
b
|Θjk − Θjk | ≤ π cos
τbjk − cos
τjk |b
τjk | + π cos
τjk |b
τjk
− τjk
|
2
2
2
i
i
≤ π 2 |b
τjk − τjk | + π|b
τjk
− τjk
|.

54

i
where we used the simple observation that |b
τjk
| ≤ 2. Next we have:
i
i
|b
τjk
− τjk
| ≤ |b
τjk − τjk |
X
1
+
sign ((Xij − Xi0 j )(Xik − Xi0 k )) − E [sign ((Xij − Xi0 j )(Xik − Xi0 k )) |Xi ]
n − 1 i0 6=i
|
{z
}
i
θjk
|
{z
}
i
θbjk

This gives us:
i
i
b ijk − Θijk | ≤ (π 2 + π)|b
|.
− θjk
τjk − τjk | + π|θbjk
|Θ

(H.11)

i
are iid conditional on Xi , and they are in the set {−1, 1}
Next, note since the terms in θbjk
by Hoeffding’s inequality, integrating Xi out and the union bound we obtain:


2
(n
−
1)t
i
i
2
.
P(max |θbjk − θjk | > t) ≤ 2nd exp −
i,j,k
2
p
This implies that selecting t = 4 log(nd)/n, would keep the probability converging
to 0.
p
b i −Θi kmax = Op
Combining this result with (H.9) and (H.11) gives us maxi kΘ
log(nd)/n .

p
log(nd)/n = op (1), which follows since
Hence using (H.10), we get |I3 | = kv∗ k21 kβ ∗ k21 Op
p
p
kv∗ k21 kβ ∗ k21 max(sv , s) log d/n = o(1), implies kv∗ k21 kβ ∗ k21 log(nd)/n = o(1). To see the
last implication it is sufficient to observe that kv∗ k1 ≥ Ω11 ≥ 1, kβ ∗ k1 ≥ Ωmm ≥ 1. Finally
P
we assess the difference n1 ni=1 (v∗T Θi β ∗ )2 − E(v∗T Θi β ∗ )2 . By Markov’s inequality in much
the same way as in the last part of the proof of Proposition 21, we can show that the expression above is op (1) if Var((v∗T Θβ ∗ )2 ) = o(n). Since the elements of Θpare bounded by
2π we have |v∗T Θβ ∗ | ≤ kv∗ k1 kβ ∗ k1 2π. Hence since kv∗ k21 kβ ∗ k21 max(sv , s) log d/n = o(1),
implies kv∗ k41 kβ ∗ k41 = o(n) the proof is complete.

Proof of Corollary 7. Similarly to the proof of Corollary 8 we simply need to note that our
conditions imply the conditions required by Corollary 6 and also note that the bounds in
the proofs hold uniformly.
p
Lemma 24. Assume that the minimum eigenvalue λmin (Σ) > 0 and s log d/n ≤ (1 −
λmin (ΣX )
bτ satisfies the RE property with
κ) (1+ξ)
We then have that S
2 2.45π , where 0 < κ < 1.
RESbτ (s, ξ) ≥ κλmin (Σ) with probability at least 1 − 1/d.
Proof of Lemma 24. Proof is the same as in Lemma 6, but we use Theorem 4 instead of
Lemma 5. We omit the details.
Definition H.1. Define REκ (s, ξ) := κ REΣ (s, ξ) ≥ κλmin (Σ).

55

p
λmin (Σ)
Lemma 25. Assume that — λmin (Σ) > 0, sv log d/n ≤ (1 − κ) (1+1)
2 2.45π , where 0 < κ < 1
p
0
sv
and λ0 ≥ kv∗ k1 2.45π log d/n. Then we have that kb
v − v∗ k1 ≤ RE8λ
with probability at
κ (sv ,1)
least 1 − 1/d.
Proof of Lemma 25. Proof is the same as in Lemma 7, but we use Theorem 4 instead of
Lemma 5 and we use Lemma 24 instead of Lemma 6. We omit the details.

I

Proofs for the Linear Discriminant Analysis

0
(kβ ∗ k22 kv∗ k22 + kvk22 ).
Lemma 26. Under Assumption 8 we have that αV1 + (1 − α)V2 ≥ Vmin

Proof of Lemma 26. The proof follows by an elementary calculation so we omit the details.
Remark 12. This also shows that ∆ ≥ δ(α−1 +(1−α)−1 )kv∗ k22 ≥ δ(α−1 +(1−α)−1 )4KU−4 >
0.
Proof of Corollary 3. We verify the conditions of Section
2.1. To see Assumption
(2.8), we


p
v − v ∗ k1 =
can use Lemmas 30 and 31 to get kβb − β ∗ k1 = Op (kβ ∗ k1 ∨ 1)s log d/n , kb


p
Op kv∗ k1 sv log d/n provided that λ and λ0 are large enough, and we used the fact that
n1  n2 .
Next we check Assumption 1. To see (2.5), fix a |θ − θ∗ | < , for some  > 0. By the
triangle inequality:
b n −Σkmax (kβ ∗ k1 +)+kX̄ −µ1 k∞ +kȲ −µ2 k∞ .
≤ kΣ

b n β ∗ −Σβ ∗ +(X̄ − Ȳ )−µ1 +µ2
Σ
θ
θ
∞



p
∗
The RHS is Op (kβ k1 ∨ 1) log d/n , by Lemma 28 and bound (I.3). The same logic
p
shows that r2 (n)  kv∗ k1 (kβ ∗ k1 ∨ 1) log d/n, which implies
p (2.6). Since the Hessian T in
0
∗
(2.7) is free of β we are allowed to set r3 (n) = λ  kv k1 log d/n = o(1) (by Lemma 31).
Finally the two expectations in Assumption 1, are bounded as we see below:
kΣβθ∗ − Σβ ∗ k∞ = kΣ(βθ∗ − β ∗ )k∞ ≤ kΣ∗1 k∞  ≤ 2KU2 ,

kv∗T Σ−1 k∞ = 0.

By adding up the following two identities:

 

p
p
√
nOp kv∗ k1 log d/n Op (kβ ∗ k1 ∨ 1)s log d/n = op (1),


 
p
p
√
∗
∗
nOp kv k1 sv log d/n Op (kβ k ∨ 1) log d/n = op (1),
we get that (2.11) is also valid in this case by assumption.
56

To verify the consistency of θe we check the assumptions in Theorem 1. Clearly the
map v∗T Σ(βθ∗ − β ∗ ) = (θ − θ∗ ) has a unique 0 when θ = θ∗ . Moreover, the map θ 7→
bT (Σn βbθ − (X̄ − Ȳ )) is continuous as it is linear. In addition, it has a unique zero except
v
bT Σn,∗1 = 0. However note that |b
in cases when v
vT Σn,∗1 − 1| ≤ λ0 by (3.4), and hence for
small enough values of λ0 there will exist a unique zero.
Next we verify Assumption 3 in Lemma 27. Finally we move on to show (2.10). Observe
that (2.10) is trivial as its LHS ≡ 0 in this case.
√
Lemma 27. Under the conditions of Corollary 3 we have the following ∆−1/2 nS(β ∗ )
N (0, 1), where ∆ is defined as in (3.7).
Proof of Lemma 27. We stat by defining the following quantity:
#
"n
n2
1
X
X
1
⊗2
⊗2
en =
.
(Yi − µ2 )
Σ
(Xi − µ1 ) +
n i=1
i=1

(I.1)

b n β ∗ − (X̄ − Ȳ )) = n1/2 v∗T (Σ
e n β ∗ − (X̄ − Ȳ )) +n1/2 v∗T (Σ
bn − Σ
e n )β ∗ .
We have n1/2 v∗T (Σ
|
{z
}
|
{z
}
I1

I2

We proceed with showing that the term I2 is small:

bn − Σ
e n kmax = kv∗ k1 kβ ∗ k1 Op log d/n1/2 = op (1),
|I2 | ≤ n1/2 kv∗ k1 kβ ∗ k1 kΣ
where we used (I.4) from Lemma 28 (and made usage of the fact that n1  n2 ). Next we
take a closer look at the term I1 :
e n β ∗ − (µ1 − µ2 )) + n1/2 v∗T (X̄ − µ1 − Ȳ + µ2 )
I1 = n1/2 v∗T (Σ

 
n 
X
n
n
⊗2 ∗
1/2 ∗T 1
Ui β − (µ1 − µ2 ) +
I(i ≤ n1 ) − I(i > n1 ) Ui .
=n v
n i=1
n1
n2
Next, by n1 /n + op (1) = α, it is clear that:
−1/2 ∗T

I1 = n

v

+ n−1/2 v∗T

n1
X

Ui⊗2 β ∗ − (µ1 − µ2 ) + α−1 Ui

i=1
n
X



Ui⊗2 β ∗ − (µ1 − µ2 ) − (1 − α)−1 Ui



i=n1 +1




n1
n
X
X
n
n
−1
−1
−1/2
∗T
+
−α
n
v Ui +
− (1 − α)
n−1/2
v∗T Ui ,
n1
n2
i=1
i=n1 +1
|
{z
}|
{z
}|
{z
} |
{z
}


op (1)

op (1)

Op (1)

Op (1)

where we implicitly used Chebyshev’s inequality and the fact that Var(v∗T U ) ≤ 2v∗T Σv∗ ≤
2δ −1 . Next we verify Lyapunov’s condition. The sum of variances of the terms above equals:
0
n1 V1 + n2 V2 = n(αV1 + (1 − α)V2 )(1 + o(1)) ≥ nVmin
(kβ ∗ k22 kv∗ k22 + kv∗ k22 )(1 + o(1)),

57

by Lemma 26. Without loss of generality let’s assume that α−1 > (1 − α)−1 . It follows then
from Lemma 32, that for any k > 2:
E v∗T Ui⊗2 β ∗ − v∗T (µ1 − µ2 ) + α−1 v∗T Ui

k

≤ kv∗ kk2 (C1 (sv s)k/2 kβ ∗ kk2 + C2 α−k sk/2
v ),

and similarly:
E v∗T Ui⊗2 β ∗ − v∗T (µ1 − µ2 ) − (1 − α)−1 v∗T Ui

k

≤ kv∗ kk2 (C1 (sv s)k/2 kβ ∗ kk2 + C2 α−k sk/2
v ),

where C1 and C2 are some absolute constants depending on k (see the Lemma for details).
Therefore we conclude that the sum in Lyapunov’s condition, is bounded by:
−k

α
C1 kβ ∗ kk2 + Cs2k/2
(sv s)k/2
= o(1).
0
)k/2 (kβ ∗ k22 + 1)k/2
(1 + o(1))nk/2−1 (Vmin
|
{z
}
O(1)

This completes the proof.
Remark 13. We propose the following consistent estimator of ∆, and prove its consistency
in Proposition 7.
2
n1 
n1 
n
2 1 X
2
X
1 X  T
1
n
T
T
⊗2
⊗2 b
b
b
b (Xi − X̄) +
b (Xi − X̄) β +
b (Yi − Ȳ ) β
v
v
v
∆ :=
n i=1
n i=1 n1
n i=n +1
1
2

n
1 X
n T
b (Yi − Ȳ ) − (b
+
v
vT (X̄ − Ȳ ))2 .
n i=n +1 n2
1

Proposition 7. Under the same conditions as in Corollary 3, max(kµ1 k∞ , kµ2 k∞ ) = O(1),
and the following additional assumptions:
p
max(λ0 sv , λs)kv∗ k1 kβ ∗ k1 log(nd) = o(1), Var((v∗T U )2 ) = o(n), Var(v∗T U ⊗2 β ∗ ) = o(n),
E(v∗T U ⊗2 β ∗ )2 = O(1),
b →p ∆.
we have that ∆
Proof of Proposition 7. Note that ∆ can be decomposed as:
∆ =αE(v∗T U ⊗2 β ∗ )2 + α−1 E(v∗T U )2 + (1 − α)E(v∗T U ⊗2 β ∗ )2
+ (1 − α)−1 E(v∗T U )2 − (v∗T (µ1 − µ2 ))2 .
We start from the last term:
(b
vT (X̄ − Ȳ ))2 = [(b
vT (X̄ − Ȳ ))2 − (v∗T (X̄ − Ȳ ))2 ] + (v∗T (X̄ − Ȳ ))2 .
|
{z
} |
{z
} |
{z
}
I

I1

58

I2

Wehave |I1 | ≤ kb
v − v∗ k1 kb
v + v∗ k1 k(X̄ − Ȳ )⊗2 kmax . Using Lemma 31, we know kb
v − v∗ k1 =
p
Op kv∗ k1 sv log d/n . We can apply the concentration inequality (I.3) provided in Lemma
p

⊗2
2
log d/n , where we used
28 to claim that k(X̄ − Ȳ ) kmax ≤ kµ1 −µ2 k∞ +kµ1 −µ2 k∞ Op
the triangle inequality kX̄ − Ȳ k∞ ≤ kX̄ − µ1 k∞+ kȲ − µ2 k∞ + kµ
1 − µ2 k∞ . Finally due to
p
our assumptions we have |I1 | = kµ1 − µ2 k2∞ Op kv∗ k21 sv log d/n = op (1). Next we tackle
I2 = (v∗T (X̄ − Ȳ ))2 − (v∗T (µ1 − µ2 ))2 + (v∗T (µ1 − µ2 ))2 . In a similar fashion to before,
|
{z
} |
{z
}
I21
I22 

p
log d/n kµ1 − µ2 k∞ = op (1). Thus
applying inequality (I.3), we can get |I21 | ≤ kv∗ k21 Op
we have shown I = (v∗T (µ1 − µ2 ))2 + op (1). To this end define the following shorthand
notations:
n

1
2
1X
vT (Xi − X̄)⊗2 β ,
IX (v, β) =
n i=1

n

2
2
1X
IY (v, β) =
vT (Yi − Ȳ )⊗2 β
n i=1

b + IY (b
b is consistent for E(v∗ U ⊗2 β ∗ )2 . We begin with
Next we show that IX (b
v, β)
v, β)
the following bound:
n1 
n2 
2 1 X
2
1X
∗ T
⊗2 b
(b
v − v ) (Xi − X̄) β +
(b
v − v∗ )T (Yi − Ȳ )⊗2 βb
n i=1
n i=1

b ∞ kβk
b 1,
b n βk
≤ kb
v − v∗ k21 M kΣ

where M = max maxi=1,...,n1 k(Xi − X̄)⊗2 kmax , maxi=1,...,n2 k(Yi − Ȳ )⊗2 kmax . Note that
the random variables Xi − X̄ and Yi − Ȳ are in fact mean 0 sub-Gaussian variables since
e.g. kXi − X̄kψ2 ≤ kXi − µ1 kψ2 + kX̄ − µ1 kψ2 ≤ 2KU . Thus an application of Lemma 10,
and the fact that n1  n2  n, gives us that M = O(log(nd)). Furthermore we have:
b ∞ ≤ λ + kX̄ − µ1 k∞ + kȲ − µ2 k∞ + kµ1 − µ2 k∞ = Op (1),
b n βk
kΣ
by application of (I.3), and the way we select λ. Putting the last several inequalities together
with Lemma 30, Lemma 31 and the triangle inequality, we obtain:
q
q
p
p
b + IY (b
b − IX (v∗ , β)
b + IY (v∗ , β)|
b ≤ kvk1 kβk1 sv log(nd) log d/nOp (1).
v, β)
v, β)
| IX (b
Applying the same technique we can further show that in fact:
q
p
b + IY (b
b − IX (v∗ , β ∗ ) + IY (v∗ , β ∗ )| = op (1).
| IX (b
v, β)
v, β)
We proceed to show that IX (v∗ , β ∗ ) + IY (v∗ , β ∗ ) is consistent for E(v∗ U ⊗2 β ∗ )2 and since
b + IY (b
b is consistent
E(v∗ U ⊗2 β ∗ )2 = O(1), the latter inequality also shows that IX (b
v, β)
v, β)

59

f := maxi=1,...,n kU ⊗2 kmax . For exactly the
for E(v∗ U ⊗2 β ∗ )2 . Define the following notation M
i
f
same reasons as for M we have M = Op (log(nd)). Next we consider the difference:
∗

∗

∗

∗

−1

|IX (v , β ) + IY (v , β ) − n

n
X

v∗T Ui⊗2 β ∗

2

|

i=1
n

n

1
2
1X
1X
∗T
T ∗
|v (Xi − X̄)||(Xi − X̄) β | +
|v∗T (Yi − Ȳ )||(Yi − Ȳ )T β ∗ |
≤ kv k1 kβ k1 V
n i=1
n i=1
!
n
1 X ∗T
+
|v Ui ||UiT β ∗ | ,
n i=1

∗

∗


⊗2
where V = max maxi=1,...,n1 k(Xi − X̄)⊗2 − Ui⊗2 kmax , maxi=1,...,n2 k(Yi − Ȳ )⊗2 − Ui+n
k
.
1 max
2
2
Note that by the simple inequality |ab| ≤ (a + b )/2, we have, that the expression in the
brackets is bounded by:
bn + Σ
e n )v∗ /2 + β ∗T (Σ
bn + Σ
e n )β ∗ /2.
≤ v∗T (Σ
p

b n v∗ ≤ kv∗ k1 kv∗T Σ
b n k∞ = kv∗ k1 + kv∗ k2 Op
We have that v∗T Σ
log
d/n
. Similarly since
1
p


bn − Σ
e n kmax = Op log d we have that v∗T Σ
e n v∗ ≤ kv∗ k1 + kv∗ k2 Op
by (I.4) kΣ
log
d/n
.
1
n

p
b n β ∗ ≤ kβ ∗ k1 kµ1 −µ2 k∞ +kβ ∗ k1 (kβ ∗ k1 ∨1)Op
log d/n ,
Similarly one can show that β ∗T Σ
e n β ∗ . We next inspect V :
and a similar inequality for β ∗T Σ
max k(Xi − X̄)⊗2 − Ui⊗2 kmax ≤ max 2kXi k∞ kX̄ − µ1 k∞

i=1,...,n1

i=1,...,n1

+ kX̄ − µ1 k∞ (kX̄ − µ1 k∞ + 2kµ1 k∞ ),
and we can similarly bound the
p other term in V . Note that in Lemma 10 we showed
and as we argue in (I.3), we have kX̄ − µ1 k∞ =
that maxi=1,...,n
1 kXi k∞ = Op ( log(nd)),
p
p
p
Op
log d/n , and thus V = Op
log d/n ( log(nd) + kµ1 k∞ + kµ2 k∞ ). Hence under
our assumptions, we have:
|IX (v∗ , β ∗ ) + IY (v∗ , β ∗ ) − n−1

n
X

v∗T Ui⊗2 β ∗

2

| = op (1).

i=1

Finally we finish this part upon noting that
∗T

Pn
1
i=1
n
⊗2 ∗ 2

v∗T Ui⊗2 β ∗

2

− E v∗T Ui⊗2 β ∗

2

=

op (1), and that under the assumption Var((v U β ) ) = o(n) by Chebyshev’s inequality.
2
P 1
bT (Xi − X̄) , and show it’s consisNext we turn our attention to the term nn1 n11 ni=1
v
tent for α−1 E(v∗T Ui )2 . First note that since nn1 = α−1 + o( n1 ), and we will show the rest of
the expression is Op (1), we will just focus on the average term. We first show the following

60

difference is small:
n1
2
2
1 X
b X (b
bT (Xi − X̄) − v∗T (Xi − X̄) ] = | (b
[ v
v + v ∗ )T |
v − v ∗ )T Σ
n1 i=1

b X kmax .
≤ kb
v − v∗ k1 (kb
v − v∗ k1 + 2kv∗ k1 )kΣ
b
Using the same
 as in the proof of Lemma 28, one can show that
p kΣX kmax ≤
ptechnique
log d/n . By Lemma 31 we have kb
v − v∗ k1 = kv∗ k1 sv Op
log d/n , and
kΣkmax + Op
hence:
n1
p

2
2
1 X
T
∗T
∗ 2
b (Xi − X̄) − v (Xi − X̄) ] ≤ kv k1 sv Op
[ v
log d/n = op (1),
n1 i=1
by assumption. Next we control:
n1
n1
2
2
1 X
1 X
∗T
∗T
∗T
[ v (Xi − X̄) − v Ui ] = v (µ1 − X̄)
(2Xi − X̄ − µ1 )v∗
n1 i=1
n1 i=1


log d
∗ 2
2
∗ 2
= op (1).
≤ kv k1 kµ1 − X̄k∞ = kv k1 Op
n

Thus after using Chebyshev’s inequality upon observing that Var((v∗T U )2 ) = o(n), we have
2
P 2
bT (Yi − Ȳ ) is
v
shown the desired consistency. Similarly we can also show that nn2 n12 ni=1
consistent for (α − 1)−1 E(v∗T Ui )2 . This concludes the proof.
b n − Σkmax ≤ e
Lemma 28. The following inequality holds kΣ
tU (d, n) + t2U (d, n), with prob2−e
cA2U
1−cA2U
ability at least 1 − 2d
− 2ed
, where:
p
p
tU (d, n) = AU KU log d/ min(n1 , n2 ); e
tU (d, n) = 4AU KU2 log d/n.
(I.2)
and AU > 0 is an arbitrary positive constant, c̄ and c are absolute contents independent of
the distribution of U , and KU is as defined in the main section of the text.
Proof of Lemma 28. We start by showing a concentration bound on kX̄ − µ1 k∞ and kȲ −
µ2 k∞ . By proposition 5.10 in Vershynin (2010) and the union bound, we have:


cn1 t2
P(kX̄ − µ1 k∞ > t) ≤ ed exp − 2
.
(I.3)
KU
p
A similar inequality holds for kȲ − µ2 k∞ . Select tU (d, n) = AU KU log d/ min(n1 , n2 ),
b n − Σkmax ≤
where AU > 0 is some large constant. The triangle inequality yields kΣ
bn − Σ
e n kmax + kΣ
e n − Σkmax , where Σ
e n is defined as in (I.1). Next, we have that:
kΣ
bn − Σ
e n kmax ≤ n1 k(X̄ − µ1 )⊗2 kmax + n2 k(Ȳ − µ2 )⊗2 kmax
kΣ
n
n
n1
n2
2
≤ (kX̄ − µ1 k∞ ) + (kȲ − µ2 k∞ )2 ≤ t2U (d, n).
(I.4)
n
n
61

where the last inequality holds with high probability. Note that by Lemma 5 we have:
p
e n − Σkmax ≤ 4AU K 2 log d/n =: e
kΣ
tU (d, n),
U
2

with probability at least 1 − 2d2−c̄AU . Adding the last two inequalities completes the proof.
Lemma 29. Assume the same conditions as in Lemma 28, and assume further that the
min (Σ)
minimum eigenvalue λmin (Σ) > 0 and s(e
tU (d, n)+t2U (d, n)) ≤ (1−κ) λ(1+ξ)
2 , where 0 < κ < 1.
b n satisfies the RE property with RE b (s, ξ) ≥ κλmin (Σ) with probability
We then have that Σ
2

Σn

2

at least 1 − 2d2−c̄AU − 2ed1−cAU .
Remark 14. In fact this event happens on the same event as in Lemma 28.
Proof of Lemma 29. The proof follows the proof of Lemma 6, but uses Lemma 28 instead of
Lemma 5, hence we omit it.
min (Σ)
Lemma 30. Assume that — λmin (Σ) > 0, s(e
tU (d, n) + t2U (d, n)) ≤ (1 − κ) λ(1+ξ)
2 , where

0 < κ < 1 and λ ≥ e
tU (d, n) + t2U (d, n) kβ ∗ k1 + 2tU (d, n). Then we have that kβb − β ∗ k1 ≤

8λs
RE(s,1)

2

2

with probability at least 1 − 2d2−c̄AU − 2ed1−cAU . (see (I.2) for definition of tU and

e
tU )
Remark 15. In fact this event happens on the same event as in Lemma 28.
Proof of Lemma 30. We start by showing the true parameter Ωδ = β ∗ satisfies the sparse
b n β ∗ −(X̄ − Ȳ )k∞ ≤ λ with probability at least 1−2d2−c̄A2U −2ed1−cA2U .
LDA constraint — kΣ
We have that:
b n − Σkmax kβ ∗ k1
b n β ∗ − (X̄ − Ȳ )k∞ ≤ kΣβ ∗ − (µ1 − µ2 )k∞ +kΣ
kΣ
{z
}
|
0

+ kX̄ − µ1 k∞ + kȲ − µ2 k∞ .
Collecting the bounds we derived in Lemma 28 we get:

b n β ∗ − (X̄ − Ȳ )k∞ ≤ e
kΣ
tU (d, n) + t2U (d, n) kβ ∗ k1 + 2tU (d, n).

The last inequality implies that if we select λ ≥ e
tU (d, n) + t2U (d, n) kβ ∗ k1 + 2tU (d, n), it
2
2
will follow that β ∗ satisfies the constraint with probability at least 1 − 2d2−cAU − 2ed1−cAU .
The rest of the proof is identical to the proof of Lemma 7 but instead of using Lemma 6
we use Lemma 29. Thus we omit the proof.
min (Σ)
Lemma 31. Assume that — λmin (Σ) > 0, sv (e
tU (d, n) + t2U (d, n)) ≤ (1 − κ) λ(1+ξ)
2 , where
0
0
∗
2
∗
0 < κ < 1 and λ ≥ kv k1 (e
tU (d, n) + tU (d, n)). Then we have that kb
v − v k1 ≤ 8λ sv

REκ (sv ,1)

2
2
with probability at least 1 − 2d2−c̄AU − 2ed1−cAU . (see (I.2) for definition of tU and e
tU )

62

Remark 16. In fact this event happens on the same event as in Lemma 28.
Proof of Lemma 31. The proof is identical to the one of Lemma 7 but instead of using
Lemma 6 we use Lemma 29, and we use Lemma 28 instead of using Lemma 5. We omit the
proof.
Lemma 32. We have the following inequality:
√
E|v∗T U ⊗2 β ∗ −v∗T (µ1 −µ2 )+cv∗T U |k ≤ 2k−1 kv∗ kk2 (kβ ∗ kk2 (sv s)k/2 (8kKU2 )k +|c|k sk/2
(
kKU )k ).
v
Proof of Lemma 32. The argument follows applying standard inequalities, and the details
are omitted.

J

Proofs for Vector Autoregressive Models

Define the following quantities which will be used throughout. Let:
Kd (Σ0 , A) :=

32kΣ0 k2 maxj (Σ0,jj )
,
minj (Σ0,jj )(1 − kAk2 )

e d (Σ0 , A) := Kd (Σ0 , A)(2M + 3).
K

We set
e d (Σ0 , A)
λ := K


p
Kd (Σ0 , A) −1 p
λ :=
6 log d/T + 2 1/T .
kΣ0 k1
2

p
log d/T ,

0

(J.1)

Lemma
33. Assume that Σ0 ∈ L, A ∈ M(s), minj Ψjj ≥ C > 0 and max(sv , s) log d =
√
o( T ). Then the following relationships hold:
√
0
T max(sv , s)kΣ−1
λ = o(1), λ0 = o(1),
0 k1 λ λ = o(1),
∆ ≥ C 0 > 0,

kv∗ k21
β ∗T Σ0 β ∗
λ0
= o(T ),
= o(1),
Ψmm
v∗T Σ0 v∗ kΣ−1
0 k1

where C 0 is some positive constant.
Proof of Lemma 33. Clearly,
since M = O(1), kΣ−1
0 k1 = O(1), Kd (Σ0 , A) = O(1) and
√
follows that λ = o(1), λ0 = o(1), λ0 M = o(1) and in addimax(s
√v , s) log d = o( −1T ), it
tion T max(sv , s)kΣ0 k1 λ0 λ = o(1).
−1
−1
By the inequality (Σ−1
≥ kΣ0 k−1
0 )jj Σ0,jj ≥ 1 it follows that (Σ0 )0,jj ≥ (maxj Σ0,jj )
2 ≥
−1
M −1 . Hence ∆ = Ψmm v∗T Σ0 v∗ ≥ Ψmm minjj Σ−1
≥
CM
>
0.
0,jj
β ∗T Σ0 β ∗
Next, to show that Ψmm = o(T ), it suffices to see that β ∗T Σ0 β ∗ = O(1). To this end
note that |β ∗T Σ0 β ∗ | ≤ kΣ1,∗k k∞ kAk1 ≤ kΣ1,∗k k∞ M . Next since Ψ = Σ0 − Σ1 , we have
kΣ1,∗k k∞ ≤ maxj Σ0,jj − minj Ψjj ≤ kΣ0 k2 , which shows that |β ∗T Σ0 β ∗ | = O(1).
0
kv∗ k2
Finally we check v∗T Σ01v∗ kΣλ−1 k = o(1). Note that kv∗ k1 ≤ kΣ−1
0 k1 , and also that
0

1

v∗T Σ0 v∗ ≥ minj Σ0,jj ≥ minj Ψjj ≥ C, hence it suffices to show that kv∗ k1 λ0 = o(1). How0
ever, evidently kv∗ k1 ≤ kΣ−1
0 k1 = O(1) and λ = o(1), which shows what we wanted.
63

Next we summarize several results by Han et al. (2014), which we use in the later development.
Theorem 5 (Theorem 4.1. Han et al. (2014)). Suppose that (Xt )Tt=1 from a lag 1 vector
b
autoregressive process (Xt )∞
t=−∞ . Assume that A ∈ M(s). Let A be the optimizer of (1.6)
with the tunning parameter:
p
e d (Σ0 , A) log d/T .
λ=K
b − Ak1 ≤
For T ≥ 6 log d + 1 and d ≥ 8, we have, with probability at least 1 − 14d−1 : kA
4skΣ−1
0 k1 λ. In fact on the same event (see Lemmas A.1. and A.2. (Han et al., 2014)), we
have:
p

p
6 log d/T + 2 1/T ,
kS0 − Σ0 kmax ≤ Kd (Σ0 , A)/2
p

kS1 − Σ1 kmax ≤ Kd (Σ0 , A)
3 log d/T + 2/T .
Proof of Corollary 4. We verify the conditions of Section 2.1. To see Assumption (2.8),
note that by Theorem 5 we have kβb − β ∗ k1 ≤ 4skΣ−1
v − v∗ k1 =
0 k1 λ. Next we inspect kb
−1
Op (sv kΣ0 k1 λ0 ) according to Lemma 35. Next we check Assumption 1. To see (2.5), fix a
|θ − θ∗ | < , for some  > 0. By the triangle inequality:
kS0 βθ∗ − Σ0 βθ∗ − S1,∗m + Σ1,∗m k∞ ≤ kS0 β ∗ − S1,∗m k∞ + kS0,∗1 − Σ0,∗1 k∞ 
The RHS is Op (λ), by Theorem 5 and by the fact that kS0 β ∗ −S1,∗m k∞ ≤ λ with probability
at least 1 − 14d−1 , as is seen from the proof of Theorem 5 (see Han et al. (2014) for details).
The same logic shows that r2 (n)  kv∗ k1 λ, which implies (2.6). Since the Hessian T in
(2.7) is free of β we are allowed to set r3 (n) = λ0 = o(1). Finally the two expectations in
Assumption 1, are bounded as we see below:
kΣ0 βθ∗ − Σ0 β ∗ k∞ ≤ kΣ0,∗1 k∞  = Σ0,11 ,
By adding up the following two identities:
√
0
T Op (4skΣ−1
0 k1 λ)Op (λ ) = op (1),

√

kv∗T Σ0,−1 k∞ = 0.

0
T Op (sv kΣ−1
0 k1 λ )Op (λ) = op (1),

we get that (2.11) is also valid in this case by assumption.
To verify the consistency of θe we check the assumptions in Theorem 1. Clearly the map
∗T
bT (Σ0 βbθ −S1 )
v Σ0 (βθ∗ −β ∗ ) = (θ−θ∗ ) has a unique 0 when θ = θ∗ . Moreover, the map θ 7→ v
bT Σ0,∗1 = 0.
is continuous as it is linear. In addition, it has a unique zero except in cases when v
However note that |b
vT Σ0,∗1 − 1| ≤ λ0 by (3.4), and hence for small enough values of λ0 there
will exist a unique zero.
b is consistent for
Next we verify Assumption 3 in Lemma 34. In addition the fact that ∆
∆ is checked in Proposition 8. Finally we move on to show (2.10). Observe that (2.10) is
trivial as its LHS ≡ 0 in this case.
64

Lemma 34. Under the conditions of Corollary 4, we have that:
∆−1/2 T 1/2 S(β ∗ ) = ∆−1/2 T 1/2 v∗T (S0 β ∗ − S1 )

N (0, 1),

where the definition of ∆ is given in (3.10).
Proof of Lemma 34. First, construct the sequence ξ1 = 0, ξt+1 =

T eT
v∗T Xt⊗2 β ∗ −v∗T Xt Xt+1
m

√

(T −1)∆

t√= 1, . . . , T − 1. We start by showing that the difference between the sequence
T −1v∗T (S0 β ∗ −S1,∗m )
√
is asymptotically negligible. We have:
∆
T
X
t=1

PT

t=1 ξt

for
and

√
√
T
T − 1v∗T (S0 β ∗ − S1,∗m )
( T − 1T )−1 X ∗T ⊗2 ∗ v∗T XT⊗2 β ∗
√
√
√ .
ξt −
v Xt β − √
=
∆
∆
T −1 ∆
t=1
{z
}
{z
} |
|
I2

I1

By Lemma 35, kv∗T S0 − e1 k∞ ≤ λ0 with probability not smaller than 1 − 14d−1 . Thus we
have:
λ0 kβ ∗ k1 + |β1∗ |
λ0 M + |β1∗ |
√
√ = o(1),
|I1 | ≤ √
≤√
T −1 ∆
T −1 ∆
with probability at least 1 − 14d−1 , where we used the fact that |β1∗ | = O(1).
Next observe that EI2 = 0, and using Isserlis’ theorem and Cauchy-Schwartz we have:
 ∗T

1
β Σ0 β ∗
(v∗T Σ0 β ∗ )2
2 β ∗T Σ0 β ∗
Var(I2 ) =
+ ∗T
≤
= o(1).
T −1
Ψmm
v Σ0 v∗ Ψmm
T − 1 Ψmm
√ ∗T
P
∗
and hence I2 = op (1). The last shows that, Tt=1 ξt − T v (S√0 β∆ −S1,∗m ) = op (1), provided that
PT
T
t=1 ξt = Op (1), which we show next. Observe that the sequence (ξt )t=1 forms a martingale
difference sequence with respect to the filtration Ft = σ(X1 , . . . , Xt ) for t = 1, . . . , T , as we
clearly have E[ξt |Ft−1 ] = 0. Furthermore a simple calculation yields that for t ≥ 2 we have
∗T
)2
E[ξt2 |Ft−1 ] = (T(v−1)vX∗Tt−1
. Thus:
Σ0 v∗
T
X
t=1

E[ξt2 |Ft−1 ] − 1 =

T −1
X
 ⊗2
 ∗
v∗T
X
−
Σ
v
0
t
(T − 1)v∗T Σ0 v∗ t=1
T −1

kv∗ k21
1 X ⊗2
≤ ∗T
[X − Σ0 ]
v Σ0 v∗ T − 1 t=1 t
|
{z

.
max

I

Using Theorem 5, it is evident that I ≤ Kd (Σ0 , A)/2
−1

q

6 log d
T −1

+2

q

1
T −1

}


with probability

at least 1 − 14d , and hence the above quantity converges to 0 in probability.
P
Having noted these facts, we want to show that Tt=1 ξt converges weakly to a N (0, 1)
with the help of a version of the martingale central limit theorem (MCLT) (Hall and Heyde,
65

1980). Next we show the Lindeberg condition for the MCLT. For t ≥ 2 and a fixed δ > 0 we
have:
(v∗T Xt−1 )2 E[Z 2 1(|Z| > δC)]
E[ξt2 1(|ξt | ≥ δ)|Ft−1 ] =
,
(T − 1)v∗T Σ0 v∗
o− 21
n ∗T
)2
. Using the properties of the truncated
where Z ∼ N (0, 1) and C = (T(v−1)vX∗Tt−1
Σ0 v ∗
standard normal distribution we have that E[Z 2 |Z > c] = 1 +

φ(c)
c,
Φ(c)

and hence



φ(c)
E[Z 1(|Z| > c)] = 2Φ(c) 1 +
c = 2Φ(c) + 2φ(c)c ≤ 2φ(c)(c−1 + c),
Φ(c)
2

where the last inequality follows from a standard tail bound for the normal distribution.
Now notice that by the union bound and a standard bound on the normal cdf we have
P( max |v∗T Xt | > u) ≤ 2T exp(−u2 /(2v∗T Σ0 v∗ )).
t=1,...,T

p
p
Selecting u = 2 log(T )v∗T Σ0 v∗ gives maxt |v∗T Xt | ≤ 2 log(T )v∗T Σ0 v∗ with probability
at least 1 − T2 . Hence on this event we have:
E[ξt2 1(|ξt | ≥ δ)|Ft−1 ] ≤

e
e −1 + δ C)
e
8 log T φ(δ C)((δ
C)
,
(T − 1)

q
T −1
e
where C =
, and we used the fact that the function φ(x)(x−1 + x) is decreasing.
4 log T
Summing up over t yields:
T
X

e
e −1 + δ C)
e → 0.
E[ξt2 1(|ξt | ≥ δ)|Ft−1 ] ≤ 8 log T φ(δ C)((δ
C)

t=1

This shows that the Lindeberg condition holds with probability 1. Hence by the MCLT we
P
N (0, 1).
can claim Tt=1 ξt
b →p ∆.
Proposition 8. Under the assumptions of Corollary 4 we have ∆
b mm = S0,mm − βbT S0 βb is
Proof of Proposition 8. We begin with showing the consistency of Ψ
consistent for Ψmm . First note that Ψ = Σ0 − AT Σ0 A, and thus Ψmm = Σ0,mm − β ∗T Σ0 β ∗ .
Then we have:
b + |β ∗T (S0 βb − Σ0 β ∗ )|.
b mm − Ψmm | ≤ |S0,mm − Σ0,mm | + |(βb − β ∗ )T S0 β|
|Ψ
Fitstly, by Theorem 5, we have with probability at least 1 − 14d−1 :
|S0,mm −Σ0,mm | ≤ kS0 −Σ0 kmax


p
Kd (Σ0 , A) p
−1
≤
6 log d/T + 2 1/T = λ0 kΣ−1
0 k1 = o(1).
2
66

Secondly:
b ≤ kβb − β ∗ k1 (kS0 β ∗ k∞ + kS0 βb − S0 β ∗ k∞ )
|(βb − β ∗ )T S0 β|
≤ kβb − β ∗ k1 (kS0 kmax kβ ∗ k1 + kS0 βb − S1,∗m k∞ + kS0 β ∗ − S1,∗m k∞ ).
On the event of Theorem 5 we further have:
kβ − β ∗ k1 kS0 kmax kβ ∗ k1 ≤ 4skΣ−1
0 k1 λ[kΣ0 kmax + kS0 − Σ0 kmax ]M = o(1).
Furthermore within the proof of Theorem 5, it can be seen that on the event of interest we
have kS0 β ∗ − S1,∗m k∞ ≤ λ, and hence:
kβb − β ∗ k1 (kS0 βb − S1,∗m k∞ + kS0 β ∗ − S1,∗m k∞ ) ≤ 2λkβb − β ∗ k1 = op (1).
Lastly,
|β ∗T (S0 βb − Σ0 β ∗ )| ≤ |β ∗T S0 (βb − β ∗ )| + |β ∗T (S0 − Σ0 )β ∗ |
≤ kβ ∗ k1 2λ + kβ ∗ k1 [kS0 β ∗ − S1,∗m kmax + kS1,∗m − Σ1,∗m kmax ]

p
3 log d/T + 2/T = o(1),
≤ M 3λ + M Kd (Σ0 , A)
where the last two inequalities hold on the event of Theorem 5, and we used the fact that
kβ ∗ k1 ≤ M since A ∈ M(s).
b T S0 v
b →p v∗T Σ0 v∗ . Similarly to before we have:
Next, we show that v
b − v∗ Σ0 v∗ | ≤ |(b
b| + |v∗T (S0 v
b − Σ0 v∗ )|
|b
vT S0 v
v − v∗ )T S0 v
For the firs termt we have:
0 2
b| ≤ kb
|(b
v − v∗ )S0 v
v − v∗ k1 kb
vT S0 − e1 k∞ + |e1 (b
v − v∗ )| ≤ 4sv kΣ−1
v − v∗ k∞
0 k1 (λ ) + kb
0 2
−1
0
≤ 4sv kΣ−1
0 k1 (λ ) + kΣ0 k1 2λ = o(1),

with the last two inequalities following from Lemma 35 and holding on the event from
Theorem 5. Recall that e is a unit row vector.
Finally, for the second term we have:
0
b − Σ0 v∗ )| ≤ kv∗ k1 λ0 ≤ kΣ−1
|v∗T (S0 v
0 k1 λ = o(1),

and this concludes the proof.
Lemma 35. Assume the assumptions in Theorem 5. Let
λ0 = kΣ−1
0 k1


p
Kd (Σ0 , A) p
6 log d/T + 2 1/T .
2

0
Then on the same event as in Theorem 5, we have kb
v − v∗ k1 ≤ 4sv kΣ−1
0 k1 λ .

67

b optiProof of Lemma 35. We first start by showing that v∗ satisfies the constraint in the v
mization problem with high probability. According to Theorem 5, we have with probability
not smaller than 1 − 14d−1 :
kv∗T S0 − e1 k∞ = kv∗T (S0 − Σ0 )k∞ ≤ kv∗ k1 kS0 − Σ0 kmax

p
Kd (Σ0 , A) p
6 log d/T + 2 1/T ≤ λ0 .
≤ kv∗ k1
2
This implies that kb
vk1 ≤ kv∗ k1 ≤ kΣ−1
0 k1 , and hence similarly to (F.3) in Lemma 7 in the
Supplementary Material we can conclude:
kb
vSvc − vS∗ vc k1 ≤ kb
vSv − vS∗ v k1

(J.2)

Next we control kb
v − v∗ k∞ . We have:
−1
kb
v − v∗ k∞ = k(b
vT Σ0 − e1 )Σ−1
vT S0 − e1 k∞ + kb
vk1 kS0 − Σ0 kmax )
0 k∞ ≤ kΣ0 k1 (kb
0
≤ kΣ−1
0 k1 2λ .

Combining the last bound with (J.2), we get:
0
kb
v − v∗ k1 ≤ 4sv kΣ−1
0 k1 λ ,

which is what we wanted to show.

68

