Submitted to the Annals of Statistics

arXiv:1601.00815v4 [math.ST] 12 Oct 2017

SEMI-PARAMETRIC EFFICIENCY BOUNDS FOR
HIGH-DIMENSIONAL MODELS
By Jana Janková and Sara van de Geer
ETH Zürich
Asymptotic lower bounds for estimation play a fundamental role
in assessing the quality of statistical procedures. In this paper we
propose a framework for obtaining semi-parametric efficiency bounds
for sparse high-dimensional models, where the dimension of the parameter is larger than the sample size. We adopt a semi-parametric
point of view: we concentrate on one dimensional functions of a highdimensional parameter. We follow two different approaches to reach
the lower bounds: asymptotic Cramér-Rao bounds and Le Cam’s type
of analysis. Both these approaches allow us to define a class of asymptotically unbiased or “regular” estimators for which a lower bound is
derived. Consequently, we show that certain estimators obtained by
de-sparsifying (or de-biasing) an ℓ1 -penalized M-estimator are asymptotically unbiased and achieve the lower bound on the variance: thus
in this sense they are asymptotically efficient. The paper discusses in
detail the linear regression model and the Gaussian graphical model.

1. Introduction. Following the development of numerous methods for
high-dimensional estimation, more recently the need for statistical inference has emerged. A number of papers have since studied the problem and
proposed constructions of estimators which are asymptotically normally distributed and hence lead to inference. These results naturally give rise to the
question of their optimality. This motivates us to study the question whether
we can establish asymptotic efficiency bounds in high-dimensional models
and whether we can construct an estimator achieving these bounds.
To introduce the setting, suppose that we observe a sample X (1) , . . . , X (n)
which is distributed according to a probability distribution Pβ that depends
on an unknown high-dimensional parameter β ∈ B ⊂ Rp . The dimension p of
the parameter can be much larger than the sample size n. A major structural
assumption we consider in this paper is sparsity in the high-dimensional parameter. In these sparse high-dimensional settings, a common approach to
estimation is based on regularized M-estimators, where the regularization is
in terms of the ℓ1 -penalty. This approach has been studied extensively, and
MSC 2010 subject classifications: Primary 62J07; secondary 62F12
Keywords and phrases: Asymptotic efficiency, high-dimensional, sparsity, Lasso, linear
regression, graphical models, Cramér-Rao bound, Le Cam’s Lemma

1

2

J. JANKOVÁ AND S. VAN DE GEER

under several settings, it produces near-oracle estimators of β under certain sparsity conditions (and some further conditions). However, the oracle
properties of the regularized estimators come at a price: the regularization
introduces bias by shrinking the estimated coefficients towards zero. Hence,
the regularized approach does not easily yield estimators which are asymptotically normally distributed. This makes it difficult to establish results for
statistical inference.
Several streams of work have emerged that studied “post-regularization
inference”, which focused on construction of methodology for inference, with
some preliminary use of regularized estimators. This was mostly considered
for estimation of low-dimensional parameters of the high-dimensional vector.
One stream of work concentrates on “de-sparsifying” or “de-biasing” procedures, which were studied for the linear model (Zhang and Zhang (2014),
van de Geer et al. (2014), Javanmard and Montanari (2014a), Javanmard
and Montanari (2014a), Javanmard and Montanari (2014b), Javanmard and
Montanari (2015)), for generalized linear models (van de Geer et al. (2014))
and some special cases of non-linear models, such as undirected graphical
models (Janková and van de Geer (2014), Janková and van de Geer (2016a)).
This approach uses the ℓ1 -regularized M-estimator as an initial estimator
and implements a bias correction step which may be interpreted as one iteration using the Newton-Raphson method. Another stream of work studies
the use of orthogonalizing conditions to define a new post-regularization estimator; this approach was considered for general models under high-level
conditions in Chernozhukov, Hansen and Spindler (2015). Further examples
of high-dimensional inference include the works Ren et al. (2015), Gao, Ma
and Zhou (2014) or data splitting methods (Meinshausen and Yu (2009)).
The work in essence shows an important result: an asymptotically normal
estimator for low-dimensional parameters can be constructed in several of
the common models.
Further key questions that were studied concern optimality properties
of these de-sparsified estimators. In particular, what are lower bounds on
the rate of convergence in the supremum norm? These questions have been
investigated for the linear regression with random design (Cai and Guo
(2015)) and for Gaussian graphical models (Ren et al. (2015)) and other
special cases of non-linear models (Gao, Ma and Zhou (2014)). The results
in these settings reveal several important findings, which we discuss for the
linear regression and graphical models. The minimax rates for estimation
of single elements (of the vector of regression coefficients or the precision

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

3

matrix) are shown to satisfy
(1)

√
inf sup Eβ |T (X (1) , . . . , X (n) ) − βi | ≥ C(1/ n + s log p/n),
T β∈B

for some constant C > 0, where βi ∈ R is a single regression coefficient
or a single entry in a precision matrix and the unknown sparsity s is the
number of non-zero entries in the regression vector or, in the case of Gaussian graphical models, in rows of a precision matrix. The infimum in (1) is
taken over all estimators T . The statement (1) further requires some mild
regularity conditions (see Cai and Guo (2015), Ren et al. (2015)). Naturally,
(1) implies that the parametric rate is optimal: it cannot be improved in
order. On the other hand, if there is insufficient sparsity, in particular when
the sparsity s satisfies s ≫ n/ log p, the minimax lower bounds diverge. This
is no surprise as the oracle inequalities for certain M-estimators have only
been shown under the condition s = o(n/ log p). In the intermediate spar√
sity regime when n/ log p ≤ s < n/ log p, the parametric rate cannot be
achieved.
√
As for the upper bounds, the parametric rate 1/ n can be achieved for
estimation of single entries. This basically follows directly from the asymptotic normality of the de-sparsified estimators, if sparsity of β is of small
√
order n/ log p. This sparsity condition is stronger than the condition necessary for oracle inequalities (s = o(n/ log p)). However, as we discuss in
√
Section 8.6, the sparsity condition s = o( n/ log p) is essentially necessary
for asymptotically normal estimation. To summarize the findings, the analysis of the minimax rates revealed that under sufficient sparsity of small
√
√
order n/ log p, the parametric rate of order 1/ n is optimal, and the desparsified estimator achieves it (in the above mentioned cases).
In this paper, we attempt to answer further questions that arise concerning the optimality of asymptotically normal estimators in high-dimensional
settings. The analysis on minimax rates does not address an important question. The derived lower bound (1) does not reveal any explicit lower bounds
on the (asymptotic) variance. The question of efficiency in the spirit of the famous Cramér-Rao result thus remains open in the high-dimensional setting.
This motivates us to pose the following questions. Can we establish lower
bounds on the variance, similar to the Cramér-Rao bounds in the (semi)parametric setting, also in the high-dimensional setting? And if yes, can we
construct an estimator that achieves these bounds? We give an affirmative
answer to these questions.
2. Our contributions. Asymptotic efficiency of estimators was thoroughly studied in the traditional settings; we refer the reader to the books

4

J. JANKOVÁ AND S. VAN DE GEER

van der Vaart (2000), Bickel et al. (1993) and the references therein. These
results are however developed for fixed models which do not change with n,
and hence they cannot be applied to high-dimensional settings where the
dimension of the parameter may grow with the sample size.
In this paper we develop a framework for establishing asymptotic efficiency of estimators in high-dimensional models changing with n. We concentrate on two approaches towards deriving the lower efficiency bounds:
asymptotic Cramér-Rao bounds and Le Cam’s approach.
Firstly, we develop an asymptotic version of a semi-parametric CramérRao lower bound for sparse high-dimensional linear and graphical models. To
this end, we propose a strong asymptotic unbiasedness assumption. Loosely
speaking, this unbiasedness assumption measures the rate at which the bias
√
vanishes in shrinking neighbourhoods of the true distribution of “size” 1/ n.
We consider the linear model and the Gaussian graphical model and for each
of them, we establish lower bounds on the variance of any asymptotically
unbiased estimator. The proposed framework might be applicable to other
high-dimensional models in a similar spirit.
Consequently, for linear regression and Gaussian graphical models, we
show that the de-sparsified estimator is an asymptotically unbiased estimator and is asymptotically efficient, i.e. it reaches the derived lower bound.
Thus, compared to previous results, which only showed asymptotic normality or minimaxity (up to order in n) of the de-sparsified estimator, we show
that it is in terms of variance the best among all asymptotically unbiased
estimators: thus in this sense asymptotically efficient.
In the second approach, we extend some of the classical results of Le Cam
on local asymptotic normality to the high-dimensional setting. The result
underlies a likelihood expansion analysis and involves a careful adjustment
of Le Cam’s arguments to the high-dimensional setting. The result obtained
gives us the limiting distribution of an asymptotically linear estimator under
a small perturbation of the parameter. We next show for the linear model
that the de-sparsified estimator is regular: it converges locally uniformly
to the limiting normal distribution with zero mean, and among all regular
estimators it has the smallest asymptotic variance.
The two approaches above are strongly related, but one does not clearly
dominate the other. A more detailed comparison is discussed in Section 11.
As a by-product of our analysis, we establish new oracle results for the
Lasso. Typical analysis considers oracle inequalities for the prediction error
and the ℓ1 -error which hold with high-probability. We strengthen these oracle inequalities by showing that they also hold for the mean ℓ1 -error and
for higher orders of this error. These oracle inequalities are needed to claim

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

5

strong asymptotic unbiasedness of the de-sparsified estimators.
3. Relation to prior work. As pointed out in Section 2, the traditional results as in, for instance, van der Vaart (2000) or Bickel et al. (1993),
are not directly applicable to the high-dimensional setting. We extend the
traditional approach to semi-parametric efficiency to the context of highdimensional models which requires adjustment of the arguments to a model
changing with n and the sparsity of the model is required to keep remainders in approximate expansions under control. Our main results show that
the lower bounds for high-dimensional models are analogous to those for
parametric models, however, a new message for high-dimensional models is
that to obtain the parametric lower bound, we require that the “worst possible sub-direction” is sparse. Without this condition, we are unable to claim
asymptotic efficiency of the de-sparsified Lasso estimator.
Regarding the upper bounds, to construct asymptotically efficient estimators, our work follows the methodology from the works van de Geer et al.
(2014) and Janková and van de Geer (2016a), where de-sparsified Lasso
estimators are proposed for the linear regression and for undirected graphical models. We borrow these constructions with some small adjustments.
However, the upper bounds derived for the de-sparsified estimators in the
mentioned papers are not sufficient for the present analysis: we need to show
a stronger oracle bound which holds in expectation. Moreover, we extend
the results for estimation of single entries as considered in van de Geer et al.
(2014) and Janková and van de Geer (2016a) to linear functionals.
Asymptotic efficiency of estimators in high-dimensional settings changing with n was first considered in the paper van de Geer et al. (2014).
The paper provides a formulation of asymptotic efficiency of entries of the
de-biased lasso. The approach is based on embedding the high-dimensional
model into a fixed (i.e. not changing with n) infinite-dimensional model, for
which semi-parametric efficiency bounds are available (see van der Vaart
(2000)). However, such an embedding requires a very special model structure. In the present paper, we do not use an embedding but instead directly
develop the theory for models changing with n.
4. Organization of the paper. The particular sections of the paper
are divided as follows. In Section 7 we state preliminary results on oracle
inequalities for the mean ℓ1 -error of the Lasso estimator. In Section 6 we
propose a strong asymptotic unbiasedness assumption. Section 8 gives lower
and upper bounds on the variance of asymptotically unbiased estimators
in the linear model, considering random design in Section 8.3 and fixed
design in Section 8.4. In Section 9 we derive lower and upper bounds on

6

J. JANKOVÁ AND S. VAN DE GEER

the variance of asymptotically unbiased estimators in Gaussian graphical
models. Section 10 contains an extension of Le Cam’s lemma to the highdimensional setting, which is applicable to general non-linear models. Section
11 summarizes the results, conclusions and some open questions. Finally, the
proofs are contained in the supplemental article Janková and van de Geer
(2016b).
5. Notation.
a vector x = (x1 , . . . , xp ) ∈ Rp we denote its ℓp norm
Pp For
p 1/p
by kxkp := ( i=1 xi )
for p ≥ 1. We further let kxk∞ := maxi=1,...,p |xi |
and kxk0 = |{i : i ∈ {1, . . . , p}, xi 6= 0}|. For a vector x ∈ Rn we denote kxk2n := kxk22 /n (with some abuse of notation). By ei we denote a pdimensional vector of zeros with a one at position i. For a matrix A ∈ Rm×n ,
we denote its (i, j)-th entry by Aij , i = 1, . . . , m, j = 1, . . .P
, n. Further, we let
kAk∞ := maxi=1,...,m,j=1,...,n |Aij |, |||A|||1 := maxi=1,...,m nj=1 |Aij | and we
let kAkF denote the Frobenius norm of A. We denote its j-th column by Aj .
By Λmin (A) and Λmax (A) we denote the minimum and maximum eigenvalue
of a symmetric matrix A, respectively. We use tr(A) to denote the trace of
the matrix A. We recall here that for symmetric matrices A, B ∈ Rp×p it
holds that vec(A)T vec(B) = tr(AB), where vec(A) is the vectorized version
of a matrix A obtained by stacking columns of A on each other.
For real sequences fn , gn , we write fn = O(gn ) or fn . gn if |fn | ≤ C|gn |
for some C > 0 independent of n for all n. We write fn ≍ gn if both fn =
O(gn ) and 1/fn = O(1/gn ) hold. Finally, fn = o(gn ) if limn→∞ fn /gn = 0.
For a sequence of random variables Xn , we write Xn = OP (fn ) if Xn /fn
is bounded in probability. We write Xn = oP (1) if Xn converges to zero in
probability. We use
to denote the convergence in distribution. By 1T we
denote the indicator function of the set T. The identity matrix is denoted
by I.
6. Asymptotic unbiasedness. This section defines the concept of strong asymptotic unbiasedness that will be needed for the linear and graphical
model. We turn to the linear model in the next section. Consider a probability distribution Pβ on some observation space X , where the parameter β
lies is a p-dimensional parameter space B ⊂ Rp . We consider the parameter
set
(2)

B(dn ) := {β ∈ B : kβk0 ≤ dn , kβk2 ≤ C},

where C > 0 is some universal constant and dn is a known sequence that
will be specified later. We further define an ℓ2 -neighbourhood of a point
β ∈ B(dn ) as follows
(3)

B(β, ε) := {β̃ ∈ B(dn ) : kβ̃ − βk2 ≤ ε}.

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

7

We remark that all the parameter vectors appearing in this paper are sequences depending on n. In general we omit the index n, except for situations
where omitting the index could lead to confusion.
Let g : B → R and let the parameter of interest be g(β). Our goal is
to derive an asymptotic lower bound for the variance of an estimator Tn of
g(β), which is in some sense asymptotically unbiased. To this end, we define
strong asymptotic unbiasedness as follows.
Definition 1. Let mn be a sequence such that n = o(mn ). We say
that Tn is a strongly asymptotically unbiased estimator of g(β) at β0 (in a
neighbourhood of sizec) with a rate mn if it holds that varβ0 (Tn ) = O(1/n)
c
and for every β ∈ B β0 , √m
n

lim

n→∞

√

it holds

mn (Eβ Tn − g(β)) = 0.

The motivation for Definition 1 comes from the asymptotic unbiasedness
assumption for semi-parametric models, which is assumed to hold in a small
neighborhood of β0 . Definition 1 implies that the mean squared error of the
considered estimator must be of order 1/n.
7. Strong oracle inequalities for the Lasso. We present new results
on oracle inequalities for the Lasso estimator in linear regression which will
be needed in subsequent sections, but can also be of independent interest.
Typical high-dimensional analysis derives oracle inequalities for the Lasso
which hold with high probability (see Bühlmann and van de Geer (2011) for
an overview of such results). The paper Bellec and Tsybakov (2016) derives
bounds on the expectation of the prediction error. Here we derive oracle
inequalities for the ℓ1 -estimation error that hold in expectation.
Consider the linear model
(4)

Y = Xβ0 + ǫ,

where X is the n × p design matrix with independent rows X (i) , i = 1, . . . , n,
Y is the n × 1 vector of observations and ǫ = (ǫ1 , . . . , ǫn )T ∈ Rn is the
(unobservable) error. The error satisfies Eǫ = 0 and its components ǫi are
independent for i = 1, . . . , n. Moreover, the error ǫ and the design matrix
X are independent. We further denote the Gram matrix by Σ̂ := X T X/n.
The vector β0 = (β10 , . . . , βp0 ) ∈ Rp is unknown. The unknown number of
non-zero entries of β0 is denoted by s := kβ0 k0 and is called the sparsity of
β0 .

8

J. JANKOVÁ AND S. VAN DE GEER

The Lasso estimator with a tuning parameter λ > 0 is defined as follows:
(5)

β̂ := arg minp kY − Xβk2n + 2λkβk1 .
β∈R

The known results on oracle inequalities for the Lasso (5) give high-probability bounds for the prediction error and the ℓ1 -error (or under some conditions,
for the
p ℓq -error for 1 ≤ q ≤ 2). In particular, for the tuning parameter
λ ≍ log p/n and under further conditions that may be found in Bühlmann
and van de Geer (2011), it holds
kX(β̂ − β0 )k2n + λkβ̂ − β0 k1 = OP (sλ2 ).
Bellec and Tsybakov (2016) show analogous results for the expected prediction error EkX(β̂ − β0 )kn for the case of fixed design. We show such
results may be obtained for the expected ℓ1 -error, under almost identical
conditions. In particular, Theorem 1 presented below implies that the mean
ℓ1 -error, Eβ0 kβ̂ − β0 k1 , is up to a logarithmic factor of the same order as the
√
oracle error Eβ0 kβora − β0 k1 = O(s/ n), where βora is the oracle maximum
likelihood estimator (i.e. a maximum likelihood estimator applied with the
knowledge of true non-zero entries of β0 ). Theorem 1 actually shows a more
general result since it considers also higher-order errors, namely the k-th
order error Eβ0 kβ̂ − β0 kk1 for any fixed k ∈ {1, 2, . . . }.
We consider the situation when the errors ǫi are independent and subGaussian (with a universal constant) and the design X has independent
sub-Gaussian rows (with a universal constant). To this end, we recall a subGaussianity assumption on random variables and vectors (see Section 14 in
Bühlmann and van de Geer (2011)).
Definition 2. We say that a random vector Z ∈ Rm has sub-Gaussian
entries with constants K, K2 > 0 if
2

2

EeZj /K ≤ K2 ,

j = 1, . . . , m.

We say that a random vector Z ∈ Rm is sub-Gaussian with constants
K, K2 > 0 if for all α ∈ Rm such that kαk2 = 1 it holds that
T Z)2 /K 2

Ee(α

≤ K2 .

In our further analysis, we typically require that the sub-Gaussianity condition as in Definition 2 is satisfied with universal constants K, K2 > 0. A
prime example of a sub-Gaussian random vector with a universal constant
is a Gaussian random vector with zero mean and covariance matrix Σ0 that
satisfies Λmax (Σ0 ) = O(1). We formulate the conditions on the error and the
design in the following.

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

9

(A1) Assume the linear model (4), where the errors ǫi are independent subGaussian random variables with universal constants and with Eǫi = 0.
(A2) Assume that X is a random n × p matrix independent of ǫ with independent rows X (i) , i = 1, . . . , n, with mean zero and with sub-Gaussian
entries with universal constants. We let Σ0 := EΣ̂ and suppose that
1/Λmin (Σ0 ) = O(1).
(A2*) Assume that X is a random n×p matrix independent of ǫ with independent sub-Gaussian rows X (i) , i = 1, . . . , n, with universal constants,
with mean zero. We let Σ0 := EΣ̂ and suppose that 1/Λmin (Σ0 ) =
O(1).
Under conditions (A2) or (A2*) we denote the inverse covariance matrix
0
by Θ0 := Σ−1
0 and by Θj we denote its j-th column (j = 1, . . . , p).
Theorem 1. Suppose
p that conditions (A1), (A2) are satisfied. Suppose
that kβ0 k2 = O(1), s log p/n = o(1) and let k ∈ {1, 2, . . . } be fixed.
Consider
p the Lasso estimator β̂ defined in (5) with a tuning parameter
λ ≥ cτ log p/n, where c > 0 is a sufficiently large universal constant and
√
τ > 1 satisfies τ 2 > 2k log(( sλ2 )−1 )/ log p. Then there exists a universal
constant C1 such that
(Eβ0 kβ̂ − β0 kk1 )1/k ≤ C1 sλ.
Taking k = 1, under the conditions of Theorem 1 we obtain
Eβ0 kβ̂ − β0 k1 ≤ C1 sλ.
Theorem 1 can also be easily extended to fixed design, under a compatibility condition (see Section 13) on the Gram matrix Σ̂, which substitutes
the condition Λmin (Σ0 ) ≥ L > 0, and under the condition kΣ̂k∞ = O(1).
We comment on the conditions (A1), (A2) and kβ0 k2 = O(1),
kβ0 k0 =
p
p
o( n/ log p) assumed in Theorem 1. Condition kβ0 k0 = o( n/ log p) together with conditions (A1), (A2) was used to apply the high-probability
oracle results for Lasso as in Bühlmann and van de Geer (2011) to the
case of random design. Condition kβ0 k2 = O(1) can be justified under an
assumption on the boundedness of the “signal-to-noise ratio”. The “signalto-noise ratio” is defined as the ratio of the
Pn variance of the
Pnsignal (observations) and the variance of the
noise,
i.e.
var
(Y
)/
β0 i
i=1
i=1 var(ǫi ) = 1 +
1 Pn
2
T
2
β0 Σ0 β0 /σǫ , where σǫ := n i=1 var(ǫi ). Hence, under upper-boundedness
of 1/Λmin (Σ0 ), the signal-to-noise ratio is up to a constant lower-bounded
by kβ0 k22 /σǫ2 . If we assume that the signal-to-noise ratio remains bounded

10

J. JANKOVÁ AND S. VAN DE GEER

and the variance of the noise σǫ2 is bounded (as implied by condition (A1)),
then the ℓ2 -norm of β0 must also remain bounded.
Finally, the condition τ 2 > 2k log((sλ2 )−1 )/ log p only guarantees
that
p
we choose sufficiently large regularization parameter λ ≥ cτ log p/n by
choosing τ large enough compared
p to the order k of the error that we want
√
to control. If p ≥ n and λ = cτ log p/n, the condition reduces to τ ≥ C k
for some constant C > 0. Then clearly, this condition means that the higher
order of error we want to control, the stronger regularization must be chosen.
8. The de-sparsified Lasso.
8.1. Methodology. As an initial estimator, we consider the Lasso estimator (5). The Lasso estimator is well-understood in terms of prediction
and estimation error bounds, and was shown minimax optimal in terms
of the prediction error and ℓ1 -error. However, due to the inclusion of the
ℓ1 -penalty, the estimator is biased and its limiting distribution can accumulate a positive mass at zero (Knight and Fu (2000)). In view of statistical
inference, a de-sparsified or de-biased version of the Lasso was then considered (see Zhang and Zhang (2014), van de Geer et al. (2014), Javanmard
and Montanari (2014a), Javanmard and Montanari (2014a), Javanmard and
Montanari (2014b), Javanmard and Montanari (2015)), which was shown to
be asymptotically normal for estimation of βj0 .
To construct the de-biased estimator, we further need to construct a surrogate inverse of Σ̂, or in other words we need to construct an estimator
of the inverse covariance matrix Θ0 = Σ−1
0 . We define Θ̂j as an estimate
of the column Θ0j obtained by solving the following program, that will be
referred to as nodewise regression (see van de Geer et al. (2014)). Recall
that X is the design matrix with rows X (i) , i = 1, . . . , n. The columns of the
design matrix X will be denoted by Xj , j = 1, . . . , p, and by X−j we denote
the n × (p − 1) matrix obtained by removing the j-th column from X. For
j = 1, . . . , p, we let
(6)

γ̂j := arg min kXj − X−j γk2n + 2λj kγk1 ,
γ∈Rp−1

τ̂j2 := kXj − X−j γ̂j k2n + λj kγ̂j k1 ,
and we denote the j-th column of the nodewise Lasso estimator by
Θ̂j := (−γ̂j,1 , . . . , −γ̂j,j−1 , 1, −γ̂j,j+1 , . . . , −γ̂j,p )T /τ̂j2 ,
p
where λj ≍ log p/n for j = 1, . . . , p, uniformly in j. We denote the nodewise Lasso estimator by Θ̂ := (Θ̂1 , . . . , Θ̂p ). The necessary Karush-Kuhn(7)

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

11

Tucker conditions corresponding to the nodewise regression (obtained by replacing derivatives by sub-differentials) imply the condition kΣ̂Θ̂j − ej k∞ =
OP (λj /τ̂j2 ) (see van de Geer et al. (2014)), which will be needed later. We
now define the de-sparsified Lasso introduced in van de Geer et al. (2014),
(8)

b̂ := β̂ + Θ̂T X T (Y − X β̂)/n,

and we let b̂j denote its j-th entry. The motivation for the definition (8)
comes from updating the initial Lasso estimator β̂ by removing the bias due
to the ℓ1 -penalty. We briefly summarize the main results on b̂ as derived in
van de Geer et al. (2014). The estimator b̂j can be shown to be asymptotically
√
linear with a remainder term of small order 1/ n, in particular, under the
conditions (A1), (A2*) and
√
√
s = o( n/ log p), max sj = o( n/ log p)
j=1,...,p

it holds
b̂ − β0 = Θ0 X T ǫ/n + ∆,
√
√
where sj := kΘ0j k0 and k∆k∞ = oP (1/ n). Thus, after normalization by n
and by the (estimated) standard deviation, asymptotic normality of entries
of b̂ with zero mean and unit variance follows by the central limit theorem.
We now investigate the question of “regularity” and asymptotic efficiency
of this estimator.
We first show that the de-sparsified estimator b̂j satisfies the strong asymptotic unbiasedness condition from Definition 1 in Section 6. We then show
that b̂j achieves the lower bound on the variance of any strongly asymptotically unbiased estimator. Thus in this sense the de-sparsified estimator is
asymptotically efficient. In Section 8.3 we investigate the case of a random
Gaussian design matrix and in Section 8.4 the case of a fixed design matrix.
8.2. Strong asymptotic unbiasedness of the de-sparsified Lasso. We consider estimation of linear functionals g(β) = ξ T β, where ξ ∈ Rp is a known
vector. We define an estimator of g(β) = ξ T β as a linear combination ξ of
the de-sparsified estimator b̂. This yields
(9)

b̂ξ := ξ T b̂ = ξ T β̂ + ξ T Θ̂X T (Y − X β̂)/n.

Then we have the following lemma, which shows strong asymptotic unbiasedness of b̂ξ for estimation of ξ T β.
Lemma 1. Suppose that conditions (A1), (A2*) are satisfied, β0 ∈ B(dn )
√
where dn = o ( n/log p), maxj sj ≤ dn , kξk1 = O(1) and kΣ0 k∞ = O(1).

12

J. JANKOVÁ AND S. VAN DE GEER

Let b̂ξ be the estimator defined in p
(9) with tuning parameters of the Lasso
and nodewise regression λ ≍ λj ≍ log p/n uniformly in j = 1, . . . , p. Then
b̂ξ is a strongly asymptotically unbiased estimator of ξ T β at β0 .
8.3. Main results for random design. We derive lower bounds for the
variance of a strongly asymptotically unbiased estimator. We consider the
following conditions on the error distribution and the design matrix X.
(B1) Assume the linear model (4) with ǫ ∼ N (0, I).
(B2) Assume that X is a random n × p matrix independent of ǫ with independent rows X (i) ∼ N (0, Σ0 ) for i = 1, . . . , n. Suppose that the
inverse covariance matrix Θ0 := Σ−1
0 exists, 1/Λmin (Σ0 ) = O(1) and
kΣ0 k∞ = O(1).
Theorem 2. Suppose that conditions (B1), (B2) are satisfied. Suppose
that Tn is a strongly asymptotically unbiased estimator of g(β) at β0 ∈
√
p
T
B(d
n ) with a rate mn . Let h ∈ R satisfy h Σ0 h = 1 and β0 + h/ mn ∈
c
for a sufficiently large universal constant c. Assume moreover
B β0 , √m
n
that for some ġ(β0 ) ∈ Rp it holds

(10)

√

√
mn (g(β0 + h/ mn ) − g(β0 )) = hT ġ(β0 ) + o(1).

Then
nvarβ0 (Tn ) ≥ [hT ġ(β0 )]2 − o(1).
Theorem 2 yields a lower bound [hT ġ(β0 )]2 − o(1) on the variance of
an estimator which is a strongly asymptotically unbiased estimator in a
√
direction h, such that β0 +h/ mn remains within the model. By maximizing
[hT ġ(β0 )]2 over all feasible h, we obtain the following corollary.


p
c
,
Corollary 1. If β0 + Θ0 ġ(β0 )/ ġ(β0 )T Θ0 ġ(β0 )mn ∈ B β0 , √m
n
then the lower bound from Theorem 2 is maximized at the value
q
h0 := Θ0 ġ(β0 )/ ġ(β0 )T Θ0 ġ(β0 ),

and under the conditions of Theorem 2, we get and under the conditions of
Theorem 2, we get
nvarβ0 (Tn ) ≥ ġ(β0 )T Θ0 ġ(β0 ) − o(1).

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

Definition 3.
call

13

Let g be differentiable at β0 with derivative ġ(β0 ). We
c0 := Θ0 ġ(β0 )/ġ(β0 )T Θ0 ġ(β0 )

the worst possible sub-direction for estimating g(β0 ).
The motivation for the terminology worst possible sub-direction in Definition 3 is given by Corollary 1. The normalization by ġ(β0 )T Θ0 ġ(β0 ) is
arbitrary but natural from a projetion theory point of view.
As a special case, consider estimation of g(β) = βj for some fixed value
of j ∈ {1, . . . , p}. Then ġ(β) = ej , the j-th unit vector in Rp . Clearly,
Θ0 ġ(β0 ) = Θ0 ej = Θ0j and g(β0 )T Θ0 ġ(β0 ) = eTj Θ0 ej = Θ0jj , where Θ0j
is the j-th column of Θ0 and Θ0jj is its j-th diagonal element. It follows
that c0j = Θ0j /Θ0jj is the worst possible sub-direction for estimating βj . If


p
c
0
0
√
β0 + Θj / Θ11 mn ∈ B β0 , mn , then Corollary 1 implies the lower bound
varβ0 (Tn ) ≥ Θ0jj /n + o(1/n).

Remark 1. To establish the lower bound, it is crucial that the worst
possible sub-direction lies within the model. For illustration, consider the
situation with the parameter of interest being g(β) = β1 . When Θ01 is not
sufficiently
sparse, we are not allowed to take the global maximizer h =
p
Θ01 / Θ011 in the maximum and the lower bound might thus become smaller.
In that case, the lower bound is given via a sparse approximation of the (nonsparse) precision matrix. For a set M ⊂ {1, . . . , p} and a vector v ∈ Rp , we
denote vM as a p-dimensional vector with entries not in M set to zero. Then
we may write
√
√ max
β0 +h/ mn ∈B(β0 ,c/ mn )

≥

max

M ⊂{1,...,p}:
|M |=dn −kβ0 k0

hT e1
hT Σ0 h
max
p

h∈R :khM k2 ≤c,
0 +h /√m k ≤C
kβM
n 2
M

[hTM e1 ]2
.
hTM Σ0 hM

0 + h/√m k ≤ C, then
But if h := (Σ0M,M )−1 e1 satisfies khk2 ≤ c and kβM
n 2
the lower bound is

max

M ⊂{1,...,p}:|M |=dn−kβ0 k0

(Σ0M,M )−1
11 − o(1),

where Σ0M,M is the reduction of Σ0 obtained by keeping only columns and
rows belonging to the set M. If Θ01 has sparsity dn − kβ0 k0 , then this lower

14

J. JANKOVÁ AND S. VAN DE GEER

0
bound coincides with (Σ0 )−1
11 − o(1) as before. If Θ1 is not sufficiently sparse,
then the lower bound is given via a sparse approximation of the precision
matrix. Finally, as will be seen in the following sections, without assuming
the sparsity condition on the worst possible sub-direction, we would not be
able to conclude asymptotic efficiency of the de-sparsified Lasso estimator.

Finally we show that the de-sparsified estimator b̂j achieves the lower
bound on the variance. Thus the de-sparsified estimator is strongly asymptotically unbiased and has the smallest variance among all strongly asymptotically unbiased estimators. We assume Gaussianity of the error and the
design matrix, as the lower bounds have only been derived for this case.
Theorem 3. Suppose that conditions (B1), (B2) are satisfied, β0 ∈
√
B(dn ) with dn = o ( n/log p) and maxj sj ≤ dn . Assume that kξk1 = O(1).
Let b̂ξ be the estimator defined in (9)pwith tuning parameters of the Lasso
and nodewise regression λ ≍ λj ≍ log p/n, uniformly in j = 1, . . . , p.
Then b̂ξ is a strongly asymptotically unbiased estimator of ξ T β at β0 . Let T
be any strongly asymptotically unbiased estimator of ξ T β at β0 and assume
√
that β0 + Θ0 ξ/(ξ T Θ0 ξn)1/2 ∈ B(β0 , c/ n). Then it holds
varβ0 (T ) ≥

ξ T Θ0 ξ + o(1)
,
n

varβ0 (b̂ξ ) =

ξ T Θ0 ξ + o(1)
.
n

To obtain the result of Theorem 3, we assumed that β0 +Θ0 ξ/(ξ T Θ0 ξn)1/2
√
∈ B(β0 , c/ n), which guarantees that the worst possible sub-direction stays
within the model. Further we assumed that the sparsity in β0 satisfies
√
s = o( n/ log p) and that the sparsity in the rows of Θ0 is of small order
√
n/ log p. Thus, to be able to claim asymptotic efficiency of the de-sparsified
Lasso, we not only require sparsity in β0 , but also sufficient sparsity in the
precision matrix. Note that the sparsity condition on β0 is almost a necessary
condition as discussed in Section 8.6 below.
8.4. Main results for fixed design. In this section, we assume that the
design matrix X is fixed (non-random). Recall that Σ̂ = X T X/n is the
Gram matrix. The following theorem is an analogy of Theorem 2 for fixed
design.
Theorem 4. Let X be a fixed n × p matrix and suppose that condition
√
(B1) is satisfied. Let h ∈ Rp be such that hT Σ̂h = O(1) and β0 + h/ mn ∈
√
B(β0 , c/ mn ). Suppose that Tn is a strongly asymptotically unbiased estimator of g(β) at β0 in the direction h with rate mn . Assume moreover that

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

15

for some ġ(β0 ) ∈ Rp it holds that
(11)

√

√
mn (g(β0 + h/ mn ) − g(β0 )) = hT ġ(β0 ) + o(1).

Then
nvarβ0 (Tn ) ≥ [hT ġ(β0 )]2 − o(1).
For fixed design, the matrix Σ̂ is not invertible, and thus we cannot use the
reasoning as in Section 8.3. We can however try to remedy this by proposing an approximate worst possible sub-direction. To this end, we may use
an estimator Θ̂, which acts as a surrogate inverse of Σ̂ in a certain sense.
Such an estimate can be obtained in the same way as for the random design, using the nodewise regression (7). The necessary Karush-Kuhn-Tucker
conditions of the nodewise regression (obtained by replacing derivatives by
sub-differentials) again imply the condition kΣ̂Θ̂j − ej k∞ = OP (λj /τ̂j2 ). The
de-sparsified estimator can then be defined in the same way as for the random design, as in equation (8).
We consider estimation of g(β0 ) := βj0 , although one could further consider estimation of linear functionals, similarly as for the random design.
Strong asymptotic unbiasedness of b̂j for estimation of βj then follows similarly as in Lemma 1 (with g(β) = βj ) for all β ∈ B(dn ), under dn =
√
o ( n/log p), if the compatibility condition is satisfied for Σ̂ with a universal constant and kΣ̂k∞ = O(1). For the definition of the compatibility
condition, see Definition 4 in Section 13 of the supplemental article Janková
and van de Geer (2016b). We formulate the asymptotic efficiency of b̂j for
g(β) := βj in the following theorem.
Theorem 5. Assume that condition (B1) is satisfied and β0 ∈ B(dn )
√
with dn = o ( n/log p). Let j ∈ {1, . . . , p} and
p let Θ̂j be obtained using
the nodewise regression as in (7) with λj ≍ log p/n. Suppose that β0 +
√
Θ̂j /(Θ̂jj n)1/2 ∈ B(β0 , c/ n), kΘ̂j k2 = O(1), the compatibility condition is
satisfied for Σ̂ with a universalpconstant and kΣ̂k∞ = O(1). Then b̂j defined
in (8) using Θ̂j and with λ ≍ log p/n is a strongly asymptotically unbiased
estimator of βj at β0 and for any strongly asymptotically unbiased estimator
T of βj at β0 it holds
Θ̂jj + o(1)
Θ̂jj + o(1)
, varβ0 (b̂j ) =
.
n
n
q
The condition β0 + Θ̂j / Θ̂jj n ∈ B(dn ) implies that kΘ̂j k0 = O(dn ). To this
end, we refer to Lemma 12 in Section 14 of the supplemental article Janková
varβ0 (T ) ≥

16

J. JANKOVÁ AND S. VAN DE GEER

and van de Geer (2016b), which shows that sparsity in Θ̂j constructed using nodewise regression is guaranteed under random design. The condition
kΘ̂j k2 = O(1) replaces the eigenvalue condition we needed in the case of
random design.
8.5. Le Cam’s bounds. In this section, we provide an alternative approach, which makes another choice in the formulation of asymptotic efficiency. This approach is based on Le Cam’s arguments (see e.g. van der
Vaart (2000)) rather than the Cramér-Rao bounds, and it allows us to show
that the convergence of the de-sparsified estimator to the limiting normal
distribution with smallest possible variance is locally uniform in the underlying unknown parameter, and the asymptotic variance of the de-sparsified
estimator is smallest among the class of asymptotically linear estimators.
Furthermore, the result identifies the asymptotic bias of asymptotically linear estimators. A detailed comparison of the two approaches for deriving
the lower bounds is deferred to Section 11.
We consider the setting from Section 8.3, where the design matrix X is
random with the parameter of interest being g(β) = βj .
Theorem 6. Assume that conditions (B1), (B2) are satisfied, β0 ∈
√
B(dn ) with dn = o( n/ log p), kΘ0j k0 ≤ dn and Λmax (Σ0 ) = O(1). Assume
p
tuning
parameters
λ
≍
λ
≍
log p/n. Then
that b̂j is defined in (8) with
j

for every β̃n ∈ B β0 , √cn

it holds

√

n(b̂j − β̃n )
(Θ0jj )1/2

β̃n

N (0, 1).

Let Tn be an asymptotically linear estimator with an influence function lβ0 :
n

(12)

Tn −

βj0

1X
lβ0 (X (i) , Y (i) ) + oPβ0 (n−1/2 ),
=
n
i=1

where Elβ0 (X (i) , Y (i) ) = 0 and var(lβ0 (X (i) , Y (i) )) =: Vβ0 < ∞. Assume that
for all h ∈ Rp and i = 1, . . . , n it holds
(13)

Elβ0 (X (i) , Y (i) )ǫi hT X (i) − hj = o(1).

Then
Vβ0 ≥ Θ0jj + o(1).

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

17

8.6. Discussion of the conditions. We briefly discuss the conditions assumed to obtain the above results. To establish asymptotic efficiency of the
de-sparsified estimator, we considered conditions analogous to the conditions
assumed in van de Geer et al. (2014). These include a sparsity condition on
√
the parameter β0 of order o( n/ log p), conditions on the covariance matrix
Λmin (Σ0 ) = O(1), kΣ0 k∞ = O(1), sparsity of the precision matrix and a
Gaussianity assumption on the rows on the precision matrix. Unlike in van
de Geer et al. (2014), we assume Gaussianity of the design matrix and the
error; this condition was needed to derive the lower bounds. In addition to
the conditions from van de Geer et al. (2014), we also assume boundedness
of ℓ2 -norm of β0 , which follows if the signal to noise ratio is bounded as argued in Section 7. Condition (13) from Theorem 6 is a variant of asymptotic
unbiasedness which is known to be satisfied in many traditional settings
(see e.g. van der Vaart (2000)). The condition is discussed in more detail in
Section 10 below.
√
Our analysis requires the sparsity condition s = o( n/ log p). This condition is essentially necessary in the linear regression setting for construction
of an asymptotically normal estimator, as argued in the following. First ob√
serve that if the (slightly weaker) condition s = O( n/ log p) is not satisfied,
then there cannot exist an estimator Tn of βj ∈ R and a sequence σn = O(1)
such that
√
n(Tn − βj0 )/σn
N (0, 1).
(14)
Suppose that there exists an estimator Tn that satisfies (14). Then necessar√
ily n(Tn − βj0 )/σn = OP (1). By similar reasoning as in Ren et al. (2015),
we have under the conditions assumed the minimax rates for E|Tn − βj0 | of
√
p
order √1n + s log
n . But then necessarily s log p/n = O(1/ n), which gives
√
s = O( n/ log p). This is only slightly weaker than the condition we require,
√
s = o( n/ log p).
Furthermore, for simplicity of presentation, we assumed that the variance
of the noise is fixed at σǫ = 1. In general, we can include the parameter σǫ
as an unknown parameter in the model, and by orthogonality of the score
corresponding to this parameter and the score corresponding to β, we can
easily extend the arguments. The noise variance will then appear in both
lower and upper bounds.
9. Gaussian graphical models. In this part, we consider efficient estimation of edge weights in undirected Gaussian graphical models. Gaussian
graphical models have become a popular tool for representing dependencies within large sets of variables and have found application in areas such

18

J. JANKOVÁ AND S. VAN DE GEER

as neuroscience, biology and climate data analysis. In particular, Gaussian
graphical models encode conditional dependencies between variables (nodes
in the graph) by including an edge between two variables if and only if
they are not independent given all the other variables. This corresponds to
the problem of estimation of the precision matrix of a multivariate normal
distribution, which we now introduce.
(C1) Assume that the n × p matrix X has independent rows X (i) , i =
1, . . . , n which are Np (0, Σ0 )−distributed.

Denote the precision matrix by Θ0 := Σ−1
0 , where the inverse of Σ0 is asp×p
sumed to exist. The matrix Θ0 ∈ R
is unknown, but we assume bounds
on its row-sparsity (column-sparsity) sj := kΘ0j k0 , where Θ0j is the j-th
column of the precision matrix.
9.1. Methodology. There have been several methods proposed for estimation of the precision matrix in the high-dimensional setting when p ≫ n
(see Friedman, Hastie and Tibshirani (2008), Meinshausen and Bühlmann
(2006)). These methods are based on regularization techniques and lead to
estimators that are biased. De-biasing was then studied similarly as in the
linear regression, and it was shown that de-biasing leads to estimators which
are asymptotically normal. For our further analysis, we consider the desparsified nodewise Lasso estimator proposed in Janková and van de Geer
(2016a). We show that this estimator is strongly asymptotically unbiased
and reaches the lower bound on the variance derived in the previous section.
To introduce the methodology, consider again the nodewise Lasso estimator Θ̂ = (Θ̂1 , . . . , Θ̂p ) defined in (7). Define the de-sparsified nodewise Lasso
(see Janková and van de Geer (2016a))
(15)

T̂ := Θ̂ + Θ̂T − Θ̂Σ̂Θ̂.

Furthermore, we write T̂ij := Θ̂ij + Θ̂ji − Θ̂Ti Σ̂Θ̂j for i, j = 1, . . . , p. The
method and its asymptotic properties were studied in Janková and van de
Geer (2016a). The estimator Θ̂j can be shown to be asymptotically linear
√
with a remainder term of small order 1/ n, in particular, under condition
√
(C1) and under maxj=1,...,p sj = o( n/ log p) it holds
T̂ − Θ0 = −ΘT0 (Σ̂ − Σ0 )Θ0 + ∆,
√
√
where k∆k∞ = oP (1/ n). Thus, after normalization by n and by the
(estimated) standard deviation, it follows that it is asymptotically standard
normal and minimax optimal (see Ren et al. (2015), Janková and van de
Geer (2016a)). We investigate the question of “regularity” and asymptotic
efficiency of the proposed estimator.

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

19

9.2. Strong asymptotic unbiasedness of the de-sparsified nodewise Lasso.
Suppose that the parameter Θ ranges over a parameter space T ⊂ Rp×p . We
then define the parameter set
G(d1 , . . . , dp ) := {Θ ∈ T : Θ = ΘT , kΘj k0 ≤ C1 dj , j = 1, . . . , p,

1/Λmin (Θ) ≤ C2 , Λmax (Θ) ≤ C3 },

for some universal constants C1 , C2 , C3 > 0. We also need to readjust the
definition of a neighbourhood from (3); hence in this section we let
B(Θ, ǫ) := {Θ̃ ∈ G(d1 , . . . , dp ) : kΘ̃ − ΘkF ≤ ǫ}.
The following lemma shows that T̂ij is strongly asymptotically unbiased for
estimation of Θ0ij .
Lemma 2. Let i, j ∈ {1, . . . , p}, assume that condition (C1) is satisfied
√
and Θ0 ∈ G(d1 , . . . , dp ) with max(di , dj ) = o ( n/log p). Let T̂ij be defined
columns of the nodewise Lasso
in (15), where Θ̂i , Θ̂j are the i-th and j-th p
estimator with tuning parameters λi ≍ λj ≍ log p/n. Then T̂ij is a strongly
asymptotically unbiased estimator for Θ0ij .
9.3. Main results. We first derive an asymptotic lower bound for the
variance of Tn when Tn is strongly asymptotically unbiased. We restrict
our attention to estimation of linear functionals of the precision matrix Θ0 ,
h(Θ0 ) = tr(ΨΘ0 ), where Ψ ∈ Rp×p is a known matrix. We shall consider the
case when Ψ is of rank one, say Ψ = ξ1 ξ2T for some vectors ξ1 , ξ2 ∈ Rp . This
corresponds to estimation of g(Θ0 ) = ξ1T Θ0 ξ2 , where ξ1 , ξ2 ∈ Rp are known
vectors.
Contrary to previous sections, the high-dimensional parameter is a matrix,
therefore instead of a vector direction h we shall write the capital letter H
to denote a matrix direction in Rp×p .
Theorem 7. Assume condition (C1), assume that Θ0 ∈ G(d1 , . . . , dp )
√
√
√
where maxj=1,...,p dj = o ( n/log p) and Θ0 + H/ n ∈ B(Θ0 , c/ n). Suppose that Tn is a strongly asymptotically unbiased estimator of g(Θ) = ξ1T Θξ2
at Θ0 ∈ G(d1 , . . . , dp ) in the direction H := Θ0 (ξ1 ξ2T + ξ2 ξ1T )Θ0 /σ, where
σ 2 := ξ1T Θ0 ξ1 ξ2T Θ0 ξ2 + (ξ1T Θ0 ξ2 )2 .
Then it holds
varΘ0 (Tn ) ≥

σ 2 − o(1)
.
n

20

J. JANKOVÁ AND S. VAN DE GEER

As a corollary, consider estimation of g(Θ0 ) = Θ0ij for some fixed (i, j) ∈
{1, . . . , p}2 . Then the worst sub-direction is given by H := (Θ0i (Θ0j )T +
Θ0j (Θ0i )T )/σ where σ 2 := (Θ0ij )2 +Θ0ii Θ0jj and the corresponding lower bound
is ((Θ0ij )2 + Θ0ii Θ0jj )/n + o(1/n).
We now show that the de-sparsified estimator T̂ij reaches the lower bound
on the variance for the parameter of interest g(Θ0 ) = Θ0ij .
Theorem 8. Suppose that condition (C1) holds, Θ0 ∈ G(d1 , . . . , dp )
√
√
√
where max(di , dj ) = o ( n/log p). Suppose that Θ0 + H/ n ∈ B(Θ0 , c/ n)
for H := (Θ0i (Θ0j )T + Θ0j (Θ0i )T )/σ. Let T̂ij be defined in (15), where Θ̂i , Θ̂j
are the i-th and j-th columns
of the nodewise Lasso estimator with tuning
p
parameters λi ≍ λj ≍ log p/n. Then T̂ij is a strongly asymptotically unbiased estimator of Θij at Θ0 and for any strongly asymptotically unbiased
estimator T of Θij at Θ0 it holds
Θ0ii Θ0jj + (Θ0ij )2 + o(1)
Θ0ii Θ0jj + (Θ0ij )2 + o(1)
, varΘ0 (T̂ij ) =
.
n
n
√
√
The condition Θ0 +H/ n ∈ B(Θ0 , c/ n) for H = (Θ0i (Θ0j )T +Θ0j (Θ0i )T )/σ
ensures that perturbation of Θ0 along the worst possible sub-direction H
lies within the model. This also implies that kHk k0 ≤ 2C1 dk , k = 1, . . . , p,
which in turn implies that necessarily kΘ0i k0 = O(dk ), kΘ0j k0 = O(dk ) for
k = 1, . . . , p. Note that we only require sparsity in the i-th and j-th column of the precision matrix. Furthermore, we must have kHkF ≤ c. This is
satisfied under the eigenvalue conditions noting that kHk2F = tr(H T H) and
kΘ0k k2 = O(1) for k = i, j.
varΘ0 (T ) ≥

9.4. Discussion of the conditions. We comment on the conditions used to
obtain the above results. The conditions under which we show asymptotic
efficiency only include eigenvalue conditions on the true precision matrix,
sparsity conditions on columns/rows of the precision matrix and Gaussianity
of the observations X (i) , i = 1, . . . , n. These conditions are almost identical
to conditions in van de Geer et al. (2014) and Janková and van de Geer
(2016a), with the exception of Gaussianity which was used for deriving the
lower bounds. In particular, the condition on row sparsity required is the
√
same as for the linear model: s = o( n/ log p). In view of the results on
minimax rates for estimation of elements of precision matrices (which are
√
derived in Ren et al. (2015)), the condition s = o( n/ log p) is necessary for
asymptotically normal estimation, which follows by similar reasoning as for
the linear regression.

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

21

10. Le Cam’s bounds for general models. In this section, we provide an extension to general non-linear models and a general parameter of
interest. This is achieved via adjustment of Le Cam’s arguments on asymptotic efficiency to the high-dimensional setting. Let X (1) , . . . , X (n) be i.i.d.
with distribution Pβn,0 : βn,0 ∈ B where B is an open convex subset of Rp .
We consider the parameter set
B(dn ) := {β ∈ B : kβk0 ≤ C1 dn , kβk2 ≤ C2 },
where C1 , C2 = O(1) and dn is a known sequence that will be specified
later. Suppose that the parameter of interest is g(βn,0 ) for some function g :
B → R. Assume that for an estimator Tn of g(βn,0 ), we can show asymptotic
linearity: there exists a real-valued function lβn,0 on X (an influence function)
and some sequence βn,0 such that
n

Tn − g(βn,0 ) =

1X
lβn,0 (X (i) ) + oPβn,0 (n−1/2 ),
n
i=1

where Pβn,0 lβn,0 = 0 and the variance Vβn,0 := Pβn,0 lβ2 n,0 < ∞. Under the
conditions of the central limit theorem, the asymptotic linearity implies that
√
1/2 βn,0
n(Tn − g(βn,0 ))/Vβn,0
N (0, 1).
(16)
For asymptotically linear estimators, we thus have the “asymptotic variance”
Vβn,0 = Pβn,0 lβ2 n,0 . We shall need some conditions on the differentiability of g
and the score function. Furthermore, we shall need a Lindeberg’s condition
related to the influence and score function. Assume that Pβ is dominated
by some σ-finite measure for all β in the parameter space and denote the
corresponding probability densities by pβ . We denote the log-likelihood by
∂ℓβ (x)
ℓβ (x) := log pβ (x) and the score function by sβ (x) := ∂β
for all x ∈ X .
(D1) (Differentiability of g) Suppose that for a given β̃n ∈ B(βn,0 , √cn ) it
holds
√
n(g(β̃n ) − g(βn,0 )) = hT ġ(βn,0 ) + o(1),
√
where h = n(β̃n − βn,0 ).
(D2) (Differentiability of the score) Suppose that the score function β 7→ sβ
is twice differentiable and the second derivative satisfies ks̈β k∞ ≤ L
for some universal constant L > 0 and for all β ∈ B(dn ). Let Iβn,0 :=
Pβn,0 sβn,0 sTβn,0 and assume that Λmax (Iβn,0 ) = O(1), 1/Λmin (Iβn,0 ) =
O(1) and
n

(17)

1X
ṡβn,0 + Iβn,0 k∞ = OP (λ),
k
n
i=1

22

J. JANKOVÁ AND S. VAN DE GEER

for some λ > 0. Suppose that dn = o(max{1/λ, n1/3 }).
(D3) (Lindeberg’s condition) Denote fβn,0 (x) := lβn,0 (x) + hT sβn,0 (x) for
x ∈ Rp . Suppose that for all ǫ > 0
(18)

lim Pβn,0 fβ2n,0 1|fβ

n→∞

n,0

√
|>ǫ n

= 0,

and assume that Vβn,0 := Pβn,0 lβ2 n,0 = O(1) and 1/Vβn,0 = O(1).
Condition (D1) is a differentiability condition on g; an analogous condition is
assumed in the first approach through Cramér-Rao bounds. Condition (D2)
is a differentiability condition on the score, which is used to obtain a Taylor
expansion
of the likelihood. Furthermore, the condition (17) guarantees that
P
− n1 ni=1 ṡβn,0 (X (i) ) is a good estimator of the Fisher information in suprep
mum norm. This can be verified e.g. for linear regression with λ ≍ log p/n.
Condition (D2) further assumes the sparsity dn = o(max{1/λ, n1/3 }), which
guarantees that the likelihood ratio expansion approximately holds. Finally,
condition (D3) is a Lindeberg’s condition which is needed to conclude asymptotic normality of certain quantities, since in Theorem 9 below we do not
require any distributional assumption. This condition can be verified for
particular models.
Theorem 9. Let g : B → R and suppose that for some fixed sequence
βn,0 ∈ B(dn ) it holds
n

(19)

1X
lβn,0 (X (i) ) + oPβn,0 (n−1/2 ),
Tn − g(βn,0 ) =
n
i=1

where Pβn,0 lβn,0 = 0. For some fixed constant c > 0, let β̃n ∈ B(βn,0 , √cn )
√
and denote h := n(β̃n − βn,0 ). Suppose that conditions (D1), (D2) and
(D3) are satisfied. Then it holds
√
n(Tn − g(βn,0 + √hn )) − (Pβn,0 (lβn,0 hT sβn,0 ) − hT ġ(βn,0 )) βn,0 + √hn
N (0, 1).
1/2
Vβn,0
The result of Theorem 9 contains a bias term Pβn,0 (lβn,0 hT sβn,0 )−hT ġ(βn,0 )
which depends on h. Now consider that the bias term in the result of the
theorem above vanishes, i.e. that the following condition on the score function sβn,0 and the function lβn,0 is satisfied: for every h ∈ Rp it holds that
(20)

Pβn,0 (lβn,0 hT sβn,0 ) − hT ġ(βn,0 ) = o(1).

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

23

The condition (20) is a variant of asymptotic unbiasedness which is known
to be satisfied in many traditional settings. If condition (20) is satisfied, then
the Cauchy-Schwarz inequality implies
1/2

(hT ġ(βn,0 ))2 ≤ Vβn,0 hT Iβn,0 h + o(Vβn,0 (hT Iβn,0 h)1/2 ).
Hence this implies a lower bound on the asymptotic variance Vβn,0 of an
asymptotically linear estimator as follows
(21)

1/2

Vβn,0 ≥ (hT ġ(βn,0 ))2 /hT Iβn,0 h + o(Vβn,0 /(hT Iβn,0 h)1/2 ).

Assuming that the inverse of Iβn,0 exists, the right-hand side of (21) is
√
√
maximized at h = Iβ−1
ġ(βn,0 ), provided that βn,0 + h/ n ∈ B(βn,0 , c/ n).
n,0
Hence we obtain the following lower bound on the asymptotic variance
1/2

ġ(βn,0 ))1/2 ).
ġ(βn,0 ) + o(Vβn,0 (ġ(βn,0 )T Iβ−1
Vβn,0 ≥ ġ(βn,0 )T Iβ−1
n,0
n,0
We summarize this simple claim in the lemma below.
Lemma 3. Let Tn satisfy (19) with Vβn,0 = O(1), 1/Λmin (Iβn,0 ) = O(1)
and for every h ∈ Rp it holds that

Pβn,0 (lβn,0 hT sβn,0 ) − hT ġ(βn,0 ) = o(1),
√
√
ġ(βn,0 )/ n ∈ B(βn,0 , c/ n), it holds that
then if βn,0 + Iβ−1
n,0
(22)

ġ(βn,0 ) + o(1).
Vβn,0 ≥ ġ(βn,0 )T Iβ−1
n,0
Theorem 9 in conjunction with Lemma 3 gives the result summarized in
Corollary 2 below.
Corollary 2. Suppose that conditions of Theorem 9 and the condition
√
√
ġ(βn,0 )/ n ∈ B(βn,0 , c/ n). Then
(22) are satisfied and that βn,0 + Iβ−1
n,0
(23)

√

√
1/2
n(Tn − g(βn,0 + h/ n))/Vβn,0

√
βn,0 +h/ n

N (0, 1),

where
Vβn,0 ≥ ġ(βn,0 )T Iβ−1
ġ(βn,0 ) + o(1).
n,0
The corollary implies that asymptotic efficiency is attained by an estimator which is asymptotically linear with an influence function lβ = ġ(β)T Iβ−1 sβ ,
provided that it satisfies the condition (22).
We have already shown how these results can be applied to the linear
regression setting in Section 8.5. We remark that the result of Theorem 9
is not directly applicable to Gaussian graphical models, where the unknown
√
parameter has overall sparsity ps, where s = o( n/ log p).

24

J. JANKOVÁ AND S. VAN DE GEER

Remark 2. The sparsity condition dn = o(n1/3 ) arises when considering Taylor expansion of the log-likelihood for general models. Hence, when
there is some special structure in the log-likelihood function, weaker sparsity
conditions might be possible. For instance, for linear regression setting, the
Hessian of the log-likelihood does not depend on the unknown parameter β0 ,
hence in that case by inspection of the likelihood
p expansion in the proof of
Theorem 9, we see that the condition dn = o( n/ log p) is sufficient.

11. Conclusions. In this paper we have proposed a framework for
studying asymptotic efficiency in high-dimensional models. We adopted a
semi-parametric point of view: we concentrated on one dimensional functions of a high-dimensional parameter for which the lower bounds were
derived. The semi-parametric efficiency bounds we obtained correspond to
the efficiency bounds for parametric models. However, the treatment for
high-dimensional models required more elaborate analysis due to the models changing with n and assumed sparsity of the model.
We further considered construction of estimators attaining the lower bounds. We showed that indeed construction of asymptotically efficient estimator is possible: a de-sparsified estimator in linear regression and Gaussian
graphical models is asymptotically efficient for estimation of certain simple
functionals. Our analysis identified the theoretical conditions on the parameter sparsity and further conditions on the model under which asymptotic
efficiency may be shown.
Comparison of the two approaches. The analysis was done in two ways:
in the spirit of asymptotic Cramér-Rao bounds and Le Cam’s bounds (van
der Vaart (2000)). These are strongly related: both define a restricted set of
estimators which are in some sense asymptotically unbiased and claim lower
bounds for any estimator in this class.
However, the two lines of work are not directly comparable as they are
different results under different assumptions. Le Cam’s bounds give a lower
bound on asymptotic variance, while the Cramér-Rao bounds give a bound
on the variance of an estimator. We formulated Le Cam’s approach for a
general sparse model, while the Cramér-Rao bounds were only considered
for the linear regression and Gaussian graphical models. Apart from this, the
main results arising from the two approaches also present some differences
in the assumptions. For the Le Cam’s-type results, we assumed a stronger
sparsity condition of order dn = o(n1/3 / log p) because of the Taylor expansion of the likelihood. However, for the linear regression setting, the sparsity
√
condition can be improved to dn = o( n/ log p), which is the same as in the
Cramér-Rao bounds. For Gaussian graphical models, Le Cam’s approach

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

25

as formulated in this paper cannot be directly used, unlike the approach
through the Cramér-Rao bounds.
Extensions. Our results on upper bounds are presented for the case when
the parameter of interest is a single entry of the high-dimensional parameter or a linear combination with e.g. bounded ℓ1 -norm. It is interesting to
note some relations to literature on minimax rates. One question is whether
asymptotic efficiency can be attained e.g. for estimation of linear functionals in linear regression when the linear combination ξ is sparse. Our results
needed that kξk1 remains bounded. Some recent works on high-dimensional
models further consider estimation of more complicated, non-sparse functionals (in linear regression Cai and Guo (2015), for Gaussian sequence
models Collier, Comminges and Tsybakov (2015)). These resultsPare however of a different nature. Consider for instance estimation of pi=1 βi in
high-dimensional linear regression. In this case, the parametric rate cannot
be achieved (Cai and Guo (2015)) and thus it remains unclear what can be
said about “asymptotic efficiency”.
Furthermore, we have treated the case of a one-dimensional parameter of
interest, though the analysis might be extended to settings when the parameter of interest is higher-dimensional (of a fixed dimension). Finally, our
analysis considered particular examples of de-sparsified estimators, however,
other estimators which are in some sense equivalent to these de-sparsified
estimators are applicable.
SUPPLEMENTARY MATERIAL
Supplement to “Semi-parametric efficiency bounds for highdimensional models”
(doi: 10.1214/00-AOASXXXXSUPP; .pdf). The supplementary material contains proofs.
References.
Bellec, P. C. and Tsybakov, A. B. (2016). Bounds on the prediction error of penalized
least squares estimators with convex penalty. ArXiv: 1609.06675.
Bickel, P. J., Klaassen, C. A., Ritov, Y. and Wellner, J. A. (1993). Efficient and
adaptive estimation for semiparametric models. Springer.
Bühlmann, P. and van de Geer, S. (2011). Statistics for High-Dimensional Data.
Springer.
Cai, T. and Guo, Z. (2015). Confidence Intervals for High-Dimensional Linear Regression:
Minimax Rates and Adaptivity. ArXiv: 1506.05539.
Chernozhukov, V., Hansen, C. and Spindler, M. (2015). Valid Post-Selection and
Post-Regularization Inference: An Elementary, General Approach. Annual Review of
Economics.

26

J. JANKOVÁ AND S. VAN DE GEER

Collier, O., Comminges, L. and Tsybakov, A. B. (2015). Minimax estimation of linear
and quadratic functionals on sparsity classes. ArXiv: 1502.00665.
Friedman, J., Hastie, T. and Tibshirani, R. (2008). Sparse inverse covariance estimation with the graphical lasso. Biostatistics 9 432–441.
Gao, C., Ma, Z. and Zhou, H. H. (2014). Sparse CCA: Adaptive Estimation and Computational Barriers. ArXiv: 1409.8565.
Janková, J. and van de Geer, S. (2014). Confidence intervals for high-dimensional
inverse covariance estimation. Electronic Journal of Statistics 9 1205 –1229.
Janková, J. and van de Geer, S. (2016a). Honest confidence regions and optimality for
high-dimensional precision matrix estimation. TEST.
Janková, J. and van de Geer, S. (2016b). Supplement to “Semi-parametric efficiency
bounds for high-dimensional models”.
Javanmard, A. and Montanari, A. (2014a). Confidence intervals and hypothesis testing
for high-dimensional regression. The Journal of Machine Learning Research 15 2869–
2909.
Javanmard, A. and Montanari, A. (2014b). Hypothesis Testing in High-Dimensional
Regression under the Gaussian Random Design Model: Asymptotic Theory. IEEE
Trans. on Inform. Theory 60 6522 – 6554.
Javanmard, A. and Montanari, A. (2015). De-biasing the lasso: Optimal sample size
for gaussian designs. Arxiv: 1508.02757.
Knight, K. and Fu, W. (2000). Asymptotics for lasso-type estimators. Annals of Statistics 28 1356–1378.
Meinshausen, N. and Bühlmann, P. (2006). High-dimensional graphs and variable selection with the Lasso. Annals of Statistics 34 1436–1462.
Meinshausen, N. and Yu, B. (2009). Lasso-type recovery of sparse representations for
high-dimensional data. Annals of statistics 37 246–270.
Ren, Z., Sun, T., Zhang, C. H. and Zhou, H. H. (2015). Asymptotic normality and
optimalities in estimation of large Gaussian graphical model. Annals of Statistics 43
991–1026.
van de Geer, S., Bühlmann, P., Ritov, Y. and Dezeure, R. (2014). On asymptotically
optimal confidence regions and tests for high-dimensional models. Annals of Statistics
42 1166-1202.
van der Vaart, A. (2000). Asymptotic Statistics. Cambridge University Press.
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 76 217-242.
Seminar für Statistik
ETH Zürich
Rämistrasse 101
8092 Zürich
Switzerland
E-mail: jankova@stat.math.ethz.ch
E-mail: geer@stat.math.ethz.ch

SUPPLEMENT TO “SEMI-PARAMETRIC EFFICIENCY
BOUNDS FOR HIGH-DIMENSIONAL MODELS”
By Jana Janková and Sara van de Geer
This supplement contains the proofs. Section 12 summarizes some
preliminary material on concentration of measure. Section 13 contains the proofs of Section 7: Strong oracle inequalities for the Lasso.
Section 14 contains strong oracle inequalities for the nodewise Lasso.
Section 15 contains proofs for Section 8. Section 16 contains proofs
for Section 9: Gaussian graphical models. In Section 17 we give the
proofs for Section 10: Le Cam’s bounds for general models. Proofs for
Section 14 are deferred to Appendix A and some technical lemmas
are deferred to Appendices B and C.

12. Concentration inequalities for sub-exponential random variables. In this preliminary section, we recall some results on concentration
results for sub-exponential random variables (for the definition of a subexponential random variable, see Section 14.2.1 in Bühlmann and van de
Geer (2011)). Lemma 4 below is a version of Lemma 14.13 in Bühlmann
and van de Geer (2011).
Lemma 4. Let Z1 , . . . , Zn be independent random variables with values
in some (measurable) space Z and γ1 , . . . , γp be real-valued functions on Z
satisfying, for j = 1, . . . , p,
Eγj (Zi ) = 0, Ee|γj (Zi )|/K ≤ M1 , ∀i = 1, . . . , n,
where M1 > 0 is a universal constant and K > 0.
Then there exists a universal constant M2 such that for all t > 0 we have
with probability at least 1 − e−nt that
r
n
√
1X
2 log(2p) M2 K log(2p)
+
.
γj (Zi ) ≤ M2 Kt + 2t +
max
j=1,...,p n
n
n
i=1

The following lemma is a version of Corollary 14.1 in Bühlmann and van de
Geer (2011).

1

2

J. JANKOVÁ AND S. VAN DE GEER

Lemma 5.
it holds

Assume the conditions of Lemma 4. Then for all m = 1, 2, . . .

!
n
1X
m
E max |
γj (Zi )|
j=1,...,p n
i=1
!m
r
2 log(2p + em−1 − p) M2 K log(2p + em−1 − p)
+
,
≤
n
n
where M2 > 0 is a universal constant.
13. Proofs for Section 7: Strong oracle inequalities for the Lasso.
In this section we prove the oracle inequality for the Lasso as stated in
Theorem 1. We need the following preliminary Lemmas 6, 7 and 8. Lemma
6 below gives sufficient conditions under which the compatibility condition
is satisfied. Lemma 7 is a concentration result for sub-Gaussian random
variables as in Section 14 in Bühlmann and van de Geer (2011). Lemma 8 is
a version of Theorem 6.1 in Bühlmann and van de Geer (2011). Recall that
we denote Σ̂ := X T X/n and Σ0 := EX T X/n. We recall the definition of
the compatibility condition (see Section 6.13 in Bühlmann and van de Geer
(2011)). Let S := {i : βi 6= 0} and let s = |S|. We denote by βS the vector
obtained from the vector β ∈ Rp by replacing entries corresponding to the
indices in S by zeros.
Definition 4. We say that a matrix Σ0 satisfies the compatibility condition with a constant φ if

 T
sβ Σ0 β
c
: kβS k1 ≤ 3kβS k1 > 0.
φ := min
kβS k21
Lemma 6 (Corollary 6.8 in Bühlmann and van de Geer (2011)). Suppose
that Λmin (Σ0 ) ≥ L for a universal constant L > 0. Then Σ0 satisfies the
compatibility condition with the constant L. Further suppose that sλ = o(1).
Then on the set kΣ̂ − Σ0 k∞ ≤ λ, for all n sufficiently large, Σ̂ satisfies the
compatibility condition with the constant L/2.
Lemma 7. Suppose that ǫi , i = 1, . . . , n are sub-Gaussian random variables with a universal constant K1 and that X (i) , i = 1, . . . , n are independent random vectors with sub-Gaussian entries, with a universal constant K2 . Suppose that ǫi and X (i) are independent for i = 1, . . . , n and
log p/n = o(1). Then there exists a constant c1 such that for all τ > 1
!
r
log(2p)
2
≤ (2p)−τ .
P kǫT Xk∞ /n ≥ c1 τ
n

3

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

Proof. We apply Lemma 4 with γj (Zi ) = ǫi Xij for i = 1, . . . , n and
j = 1, . . . , p. Then Eǫi Xij = EXij E(ǫi |Xij ) = 0, where we used independence
of ǫi and X (i) . By sub-Gaussianity of ǫi and Xij and by the Cauchy-Schwarz
inequality it follows
Ee|ǫi Xij |/ max{K1 ,K2} ≤ Ee|ǫi |

2 /(2 max{K

≤ (Ee|ǫi |

2 / max{K

2
2
2
1 ,K2 } )+|Xij | /(2 max{K1 ,K2 } )

2
1 ,K2 }

)1/2 (Ee|Xij |

2 / max{K

2
1 ,K2 }

)1/2

= O(1).

Consequently, by Lemma 4 and since log p/n = o(1), there exists a constant
c1 such that for all τ > 1
!
r
n
2
log(2p)
1X
ǫi Xij ≥ c1 τ
≤ (2p)−τ .
P
max
j=1,...,p n
n
i=1

Finally, we give an oracle inequality for the Lasso. The proof may be found
in Bühlmann and van de Geer (2011).
Lemma 8 (a version of Theorem 6.1 in Bühlmann and van de Geer
(2011)). Consider the Lasso estimator β̂ defined in (5) with a tuning parameter λ ≥ 2λ0 . Suppose that sλ = o(1) and that Λmin (Σ0 ) ≥ L for some
universal constant L > 0. Then on the set
T := {kǫT Xk∞ /n ≤ λ0 , kΣ̂ − Σ0 k∞ ≤ λ0 }
it holds
kβ̂ − β0 k1 ≤ 16λs/L.
We are now ready to prove Theorem 1.
Proof of Theorem 1. First we summarize the oracle inequality for
thep
Lasso which holds with high probability. Let T1 := {kǫT Xk∞ /n ≤
τ c1 log p/n} for some τ > 1 and for some suitable constant c1 > 0. By
2
Lemma 7, for the complementary
set T1c it holds that Pβ0 (T1c ) ≤ (2p)−τ .
p
Let T2 := {kΣ̂−Σ0 k∞ ≤ τ c1 log p/n}. Then by Lemma 4, taking γi,j (X (k) )
= eTi (X (k) (X (k) )T − Σ0 )ej for k = 1, . . . , n and i, j = 1, . . . , p, it follows
2
c
−τ 2
that Pβ0 (T2c ) ≤ (2p)−τ . Denote T :=
pT1 ∩ T2 ; then Pβ0 (T ) ≤ 2(2p) .
By Lemma 8, when λ ≥ 2λ0 := 2τ c1 log p/n, on the set T it holds that
kβ̂ − β0 k1 ≤ 16λs/L.

4

J. JANKOVÁ AND S. VAN DE GEER

We now proceed to show that the oracle inequality for the Lasso holds also
in expectation. The definition of β̂ gives
kY − X β̂k2n + λkβ̂k1 ≤ kǫk2n + λkβ0 k1 .
Consequently,
kβ̂k1 ≤ kǫk2n /λ + kβ0 k1 .
Then, and by the triangle inequality
kβ̂ − β0 k1 ≤ kβ̂k1 + kβ0 k1 ≤ kǫk2n /λ + 2kβ0 k1 ,
and thus for any k ∈ {1, 2, . . . }
Eβ0 kβ̂ − β0 kk1 ≤ Eβ0 (kǫk2n /λ + 2kβ0 k1 )k .
Then by the inequality |x + y|k ≤ 2k−1 (|x|k + |y|k ), k ≥ 1, it follows


Eβ0 (kǫk2n /λ + 2kβ0 k1 )k ≤ Eβ0 2k−1 (kǫk2n /λ)k + (2kβ0 k1 )k

By assumption, the random variables ǫ1 , . .P
. , ǫn are sub-Gaussian with universal constants. This also implies that n1 ni=1 var(ǫi 2 ) = O(1). Hence by
Lemma 5 applied with γj (Zi ) := ǫi − var(ǫi ) (j = 1, i = 1, . . . , n) we have
n

Eβ0 (kǫk2n )k

1X
var(ǫi 2 ))k ) = O(1).
= O((
n
i=1

Next observe that by assumption we have kβ0 k2 = O(1) and hence
√
kβ0 kk1 ≤ ( skβ0 k2 )k ≤ O(sk/2 ).
We can thus conclude that


Eβ0 (kǫk2n /λ + 2kβ0 k1 )k ≤ 2k−1 Eβ0 (kǫk2n /λ)k + Eβ0 (2kβ0 k1 )k
≤ O(sk/2 λ−k ).

Hence we obtain a rough bound
(Eβ0 kβ̂ − β0 kk1 )1/k = O(s1/2 λ−1 ).
On the set T we have the oracle bound kβ̂ − β0 k1 = O(sλ) and thus on
the set T , kβ̂ − β0 kk1 = O(sk λk ). Otherwise (so also on the set T c ) we have
the rough bound Eβ0 kβ̂ − β0 kk1 = O(sk/2 λ−k ). Denote by 1A the indicator

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

5

function of a set A. Then it follows using the bounds holding on T and T c
and by the Cauchy-Schwarz inequality
Eβ0 kβ̂ − β0 kk1 = Eβ0 kβ̂ − β0 kk1 1T + Eβ0 kβ̂ − β0 kk1 1T c
q
p
k k
Eβ0 1T c
≤ O(s λ ) + Eβ0 kβ̂ − β0 k2k
1
q
√
= O(sk λk ) + O( sk λ−2k ) Pβ0 (T c )
√
2
≤ O(sk λk ) + O(sk/2 λ−k ) 2(2p)−τ /2
= O(sk λk ),

where we used the assumption τ 2 ≥

√
2k log( sλ2 )
log p

O(sk/2 λ−k )p−τ

2 /2

which implies

= O(sk λk ).

Hence we conclude that there exists a constant C1 such that
(24)

(Eβ0 kβ̂ − β0 kk1 )1/k = C1 sλ.

14. Strong oracle inequalities for the nodewise Lasso. In this
section, we derive a strong oracle inequality for the nodewise regression
estimator Θ̂ of the inverse covariance matrix Θ0 defined in (7). These results
will be needed to show strong asymptotic unbiasedness and upper bounds on
the variance of the de-sparsified Lasso. The proofs may be found in Appendix
A. We require a sparsity condition on the inverse covariance matrix of the
covariates. To this end, denote the sparsity of the j-th row/column of the
matrix Θ0 by sj , i.e.
sj = kΘ0j k0 .
First we remark that the paper van de Geer et al. (2014) shows that under
conditions (A1), (A2*) and sj = o(n/ log p) it holds kΘ̂j −Θ0j k1 = OP (sj λj ).
We aim to show a stronger claim, EkΘ̂j − Θ0j k1 = O(sj λj ). This is a more
difficult task than for the linear regression, since one has to make sure that
the estimate of one over the noise level, 1/τ̂j2 , does not blow up in expectation. Moreover, for further results we shall need not only the result for
each j = 1, . . . , p but actually for the maximum over j = 1, . . . , p, that is,
an oracle bound for E maxj=1,...,p kΘ̂j − Θ0j kk1 , where k ∈ {1, 2, . . . }.
We introduce further notation; we let
γj0 := arg min EkXj − X−j γk2n
γ∈Rp−1

6

J. JANKOVÁ AND S. VAN DE GEER

and
τj2 := EkXj − X−j γ0 k2n .

The following lemma is similar to Theorem 1 for the mean ℓ1 -error of the
Lasso, however, we consider the p Lasso estimators obtained from the nodewise regression and derive an upper bound on the maximum mean ℓ1 -error,
where the maximum is taken over the p estimators.
(A2*) is satisfied, let k ∈ {1, 2, . . . }
Lemma 9. Assume that condition p
be fixed and assume that maxj=1,...,p sj log p/n = o(1),
p j = 1, . . . , p. Let γ̂j
be defined as in (6) with tuning parameters λj = c log p/n, j = 1, . . . , p,
for some sufficiently large constant c > 0. Then it holds that
[E max kγ̂j − γj0 kk1 ]1/k = O( max sj λj ).
j=1,...,p

j=1,...,p

The following lemma shows that the noise estimator τ̂j2 is a near-oracle
estimator of τj2 = 1/Θ0jj , and 1/τ̂j2 is a near-oracle estimator of 1/τj2 .
Lemma 10.p Assume that condition (A2*) is satisfied, kΣ0 k∞ = O(1),
maxj=1,...,p sj log p/n = o(1) and let k ∈ {1, 2, . . . } be fixed.
p Let γ̂j , j =
1, . . . , p be defined as in (6) with tuning parameters λj = c log p/n, j =
1, . . . , p, for some sufficiently large constant c > 0. Then the following statements hold
√
1) [E maxj=1,...,p |τ̂j2 − τj2 |k ]1/k = O(maxj=1,...,p sj λj ),
√
2) [E maxj=1,...,p | τ̂12 − τ12 |k ]1/k = O(maxj=1,...,p sj λj ).
j

j

Combination of the results in Lemmas 9 and 10 gives the following result
for the mean ℓ1 -error of the nodewise regression estimator Θ̂ defined in (7).
Lemma 11.p Assume that condition (A2*) is satisfied, kΣ0 k∞ = O(1),
maxj=1,...,p sj log p/n = o(1) and let k ∈ {1, 2, . . . } be fixed.
p Then for
Θ̂j , j = 1, . . . , p defined in (7) with tuning parameters λj = c log p/n, j =
1, . . . , p, for some sufficiently large constant c > 0, it holds
[E max kΘ̂j − Θ0j kk1 ]1/k = O( max sj λj ).
j=1,...,p

j=1,...,p

We note that the statements of Lemmas 9, 10, 11 would also hold for single
estimators for some fixed j (without taking the maximum over j). Then
the bounds would only depend on the tuning parameter for that particular
estimator and on the sparsity sj . We also give the following lemma for on
the sparsity in the nodewise Lasso estimator. It shows that under certain
conditions, the estimator γ̂j has sparsity of order sj with high probability.

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

7

p
Lemma 12. Assume that condition (A2*) is satisfied, maxj sj log p/n =
o(1), Λp
max (Σ0 ) = O(1). Let γ̂j be defined as in (6) with a tuning parameter
λj = c log p/n for some sufficiently large constant c > 0. Then it holds
that
kγ̂j k0 = OP (sj ).
15. Proofs for Section 8.2: The de-sparsified Lasso.
15.1. Proofs for Section 8.2: Strong asymptotic unbiasedness of the desparsified Lasso.
Proof of Lemma 1. For the de-sparsified estimator b̂ξ we have by simple algebra the equality
b̂ξ − ξ T β0 = ξ T Θ̂X T ǫ/n + ξ T (Σ̂Θ̂ − I)T (β̂ − β0 ).
Consider any β0 ∈ B(dn ). First note that
Eβ0 ξ T Θ̂T X T ǫ/n = EEβ0 (ξ T Θ̂T X T ǫ/n|X) = Eξ T Θ̂T X T Eβ0 (ǫ|X)/n = 0.
We then have by the definition of b̂ξ , by the Hölder’s inequality and the
Cauchy-Schwarz inequality
Eβ0 (b̂ξ − ξ T β0 ) = Eβ0 ξ T Θ̂X T ǫ/n +Eβ0 ξ T (Σ̂Θ̂ − I)T (β̂ − β0 )
{z
}
|
=0

≤ Eβ0 kξk1 kΣ̂Θ̂ − Ik∞ kβ̂ − β0 k1

≤ kξk1 (Eβ0 kΣ̂Θ̂ − Ik2∞ )1/2 (Eβ0 kβ̂ − β0 k21 )1/2 .

By the Karush-Kuhn-Tucker conditions for γ̂j , j = 1, . . . , p (see van de Geer
et al. (2014)), we have
kΣ̂Θ̂ − Ik∞ ≤ max λj /τ̂j2 .
j=1,...,p

By Lemma 10 from Section 14 it follows that
(EkΣ̂Θ̂ − Ik2∞ )1/2 ≤ max λj (Eβ0 max 1/(τ̂j2 )2 )1/2 = O( max λj ).
j=1,...,p

j=1,...,p

j=1,...,p

Next we apply Theorem 1. Conditions kβ0 k0 ≤ dn , kβ0 k2 = O(1), (A1),
√
(A2*) and sparsity dn = o( n/ log p) imply that conditions of Theorem 1 are
satisfied. Hence (Eβ0 kβ̂ − β0 k21 )1/2 = O(sλ). Hence, and since kξk1 = O(1),
and using the last display we obtain that
√
Eβ0 (b̂ξ − ξ T β0 ) = O(sλ max λj ) = o(1/ n),
j=1,...,p

8

J. JANKOVÁ AND S. VAN DE GEER

√
where we used the sparsity condition s ≤ dn = o( n/ log p). Thus we have
√
shown n(Eβ0 (b̂ξ − ξ T β0 )) = o(1). But then there
q exists δn → 0 such that
p
√
n/δn (Eβ0 (b̂ξ − ξ T β0 )) = o(1) (take e.g. δn :=
n(Eβ0 (b̂ξ − ξ T β0 ))) and

hence the estimator b̂ξ is strongly asymptotically unbiased with a rate mn :=
n/δn .

15.2. Proofs for Section 8.3: Main results for random design. Before
proving the statement of Theorem 2, we need auxiliary Lemmas 13, 14 and
15. Throughout this section, we denote by φ the probability density function
of a standard normal random variable.
Lemma 13.

Let Z ∼ N (0, 1). Then for all t ∈ R
h
i2
2
tZ−t2 /2
E e
− 1 − tZ = et − 1 − t2 .

Moreover, for 2t2 < 1 we have

2Z2

Eet

=√

1
.
1 − 2t2

Proof of Lemma 13. By direct calculation
i2
h
2
2
2
E etZ−t /2 = Ee2tZ−t = et ,
2 /2

EetZ−t

and

2 /2

EZetZ−t

=1

2 /2

= tEetZ−t

= t.

The first result of the lemma follows immediately. The second result is also
easily found by standard calculations:
Z
Z
p
1
t2 z 2
t2 Z 2
= e φ(z)dz = φ(z 1 − 2t2 )dz = √
Ee
.
1 − 2t2
Lemma 14. Suppose that u ∈ Rp satisfies 2uT Σ0 u < 1. Let Z = (X, Y ),
where Y = Xβ + ǫ, ǫ ∼ N (0, I) independent of X, and X ∼ N (0, Σ0 ).
Denote the corresponding probability density of Z by pβ and let sβ0 (Z) :=
X T ǫ. Then it holds

2
pβ0 +u (Z) − pβ0 (Z)
T
Eβ0
− sβ0 (Z) u = (1 − 2uT Σ0 u)−n/2 − 1 − nuT Σ0 u.
pβ0 (Z)

9

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

Proof of Lemma 14. Denote the density of Y given X by pβ0 (·|X), i.e.
for y = (y1 , . . . , yn )
pβ0 (y|X) :=

n
Y
i=1

φ(yi − (X (i) )T β0 ) =

1
T
e−(y−Xβ0 ) (y−Xβ0 )/2 ,
(2π)n/2

where φ is the standard normal density.
Given X, the random variable ǫT Xu is N (0, nuT Σ̂u)-distributed. It follows
therefore from the first result of Lemma 13 with t2 = nuT Σ̂u that
"
2 #
pβ0 +u (Y − Xu|X) − pβ0 (Y |X)
T
− sβ0 (Z) u |X
Eβ0
pβ0 (Y |X)
= Eenu

T Σ̂u

− 1 − nuT Σ̂u.

Since (X (i) )T u ∼ N (0, uT Σ0 u) for i = 1, . . . , n, we have by the second result
of Lemma 13
1
(i) T
2
Eβ0 e((X ) u) = p
.
1 − 2uT Σ0 u
Hence
Eβ0 [enu

T Σ̂u

− 1 − nuT Σ̂u] = (1 − 2uT Σ0 u)−n/2 − 1 − nuT Σ0 u,

from which the result follows.
Lemma 15.

Suppose that nuT Σ0 u = o(1). Then

(1 − 2uT Σ0 u)−n/2 − 1 − nuT Σ0 u = o(nuT Σ0 u).
Proof. Since nuT Σ0 u = o(1), we can use the following Taylor expansions
of log and exp
(1 − 2uT Σ0 u)−n/2 = e−n log(1−2u

TΣ

0 u)/2

= enh

TΣ

0 u+o(nh

TΣ

0 u)

= 1 + nhT Σ0 h + o(nhT Σ0 h).

Hence
(1 − 2uT Σ0 u)−n/2 − 1 − nuT Σ0 u = o(nuT Σ0 u).
Proof of Theorem 2. By assumption (10) on the differentiability of
√
g and by strong asymptotic unbiasedness of Tn at β0 and β0 + h/ mn , it
follows
√
√
hT ġ(β0 ) =
mn (g(β0 + h/ mn ) − g(β0 )) + o(1)


√
=
mn Eβ0 +h/√mn Tn (Z) − Eβ0 Tn (Z) + o(1),

10

J. JANKOVÁ AND S. VAN DE GEER

where Z := (X, Y ). We denote probability density corresponding to Z by
pβ , i.e.
T
1
e−(Y −Xβ0 ) (Y −Xβ0 )/2 .
pβ0 (X, Y ) :=
n/2
(2π)
Let sβ0 (Z) := X T ǫ. We may rewrite the expressions to obtain


√
mn Eβ0 +h/√mn Tn (Z) − Eβ0 Tn (Z) + o(1)
Z
√
= mn Tn (z)(pβ0 +h/√mn (z) − pβ0 (z))dz

pβ0 +h/√mn (Z) − pβ0 (Z)
√
pβ0 (Z)/ mn


pβ0 +h/√mn (Z) − pβ0 (Z)
T
= Eβ0 Tn (Z)
− sβ0 (Z) h
√
pβ0 (Z)/ mn

= Eβ0 Tn (Z)

+ Eβ0 Tn (Z)sβ0 (Z)T h

= Eβ0 (Tn (Z) − g(β0 )) ×


pβ0 +h/√mn (Z) − pβ0 (Z)
T
− sβ0 (Z) h
√
pβ0 (Z)/ mn

+ Eβ0 Tn (Z)sβ0 (Z)T h,
R
R
where we used that Eβ0 sβ0 (Z) = 0, pβ0 (z)dz = 1 and pβ0 +h/√mn (z)dz =
1. Since the variance of Tn is O(1/n) by the definition of strong asymptotic
unbiasedness, then
Eβ0 (Tn (Z) − g(β0 ))2 = var(Tn (Z)) + [Eβ0 (Tn (Z) − g(β0 ))]2
= O(1/n) + o(1/n) = O(1/n).

√
By Lemmas 14 and 15 with u := h/ mn and since hT Σ0 h = 1,
Eβ0



pβ0 +h/√mn (Z) − pβ0 (Z)
√
− sβ0 (Z)T h/ mn
pβ0 (Z)

2

= o(n/mn hT Σ0 h)
= o(n/mn ).

Hence, multiplying by mn
Eβ0



2
pβ0 +h/√mn (Z) − pβ0 (Z)
− sβ0 (Z)T h = o(n).
√
pβ0 (Z)/ mn

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

11

Consequently, and by the Cauchy-Schwarz inequality, we have the upper
bound


pβ0 +h/√mn (Z) − pβ0 (Z)
T
− sβ0 (Z) h
Eβ0 (Tn (Z) − g(β0 ))
√
pβ0 (Z)/ mn
s
2

q
pβ0 +h/√mn (Z) − pβ0 (Z)
T
2
≤
− sβ0 (Z) h
Eβ0 (Tn (Z) − g(β0 )) E
√
pβ0 (Z)/ mn
√  √
= O 1/ n o( n) = o(1).

Next observe that by the triangle inequality we have

|hT ġ(β0 )| − |covβ0 (Tn , ǫT Xh)| ≤ |hT ġ(β0 ) − covβ0 (Tn , ǫT Xh)| = o(1),
and hence and by the Cauchy-Schwarz inequality it follows
|hT ġ(β0 )| ≤ |covβ0 (Tn , ǫT Xh)| + o(1)
q
q
≤
varβ0 (Tn ) varβ0 (ǫT Xh) + o(1).
q
√
≤
varβ0 (Tn ) n + o(1),

where we used that varβ0 (X T ǫ) = nΣ0 and hT Σ0 h = 1. By the strong
asymptotic unbiasedness assumption on Tn , we have varβ0 (Tn ) = O(1/n)
and thus taking squares of both sides of the last inequality we obtain
√ q
|hT ġ(β0 )|2 ≤ nvarβ0 (Tn ) + 2 n varβ0 (Tn )o(1) + o(1) ≤ nvarβ0 (Tn ) + o(1).
Proof of Theorem 3. To obtain
p the lower bound on the variance, we
apply Theorem 2 with h := Θ0 ξ/ ξ T Θ0 ξ (note that for g(β) = ξ T β, the
condition on g is satisfied). Then by direct calculation, we see that the
condition hT Σ0 h = 1 is satisfied for this choice of h. Moreover, since β0 +
√
√
√
h/ n ∈ B(β0 , c/ n) by assumption, then it implies that also β0 +h/ mn ∈
√
B(β0 , c/ mn ). Thus by Theorem 2 follows the lower bound varβ0 (T ) ≥
ξ T Θ0 ξ+o(1)
, for any strongly
n
β0 with the rate mn .

asymptotically unbiased estimator T of ξ T β0 at

Next we turn to proving the upper bound. By assumptions of this theorem,
the conditions of Lemma 1 are also satisfied and thus Lemma 1 implies that
b̂ξ is strongly asymptotically unbiased at β0 . It remains to calculate the
variance of b̂ξ . Consider the following decomposition
b̂ξ − ξ T β0 = ξ T Θ0 X T ǫ/n + ξ T (Θ̂ − Θ0 )T X T ǫ/n + ξ T (Σ̂Θ̂ − I)T (β̂ − β0 ).

12

J. JANKOVÁ AND S. VAN DE GEER

Then one can show using the Cauchy-Schwarz inequality that
(25) varβ0 (b̂ξ ) = varβ0 (ξ T Θ0 X T ǫ/n) + varβ0 (ξ T (Θ̂ − Θ0 )T X T ǫ/n)
{z
} |
{z
}
|
r1

r2

T

T

+ varβ0 (ξ (Σ̂Θ̂ − I) (β̂ − β0 ))
|
{z
}
r3

+

1/2 1/2
O(r1 r2

1/2 1/2

+ r1 r3

1/2 1/2

+ r2 r3 ).

First note that as in the proof of Lemma 1, we have Eξ T Θ0 X T ǫ/n = 0 and
hence
r1 = varβ0 (ξ T Θ0 X T ǫ/n) = Eβ0 (E[(ξ T Θ0 X T ǫ/n)2 |X])

= Eβ0 (Θ0 ξ)T X T X/nΘ0 ξ) = ξ T Θ0 ξ/n.

For a random variable U, we have var(U ) ≤ EU 2 and hence by Hölder’s
inequality and the Cauchy-Schwarz inequality
r2 = varβ0 (ξ T (Θ̂ − Θ0 )T X T ǫ/n)
≤ Eβ0 (ξ T (Θ̂ − Θ0 )T X T ǫ/n)2
2

≤ kξk21 Eβ0 Θ̂ − Θ0 kX T ǫ/nk2∞
1


4 1/2
1/2
Eβ0 kX T ǫ/nk4∞
≤ kξk21 Eβ0 Θ̂ − Θ0

= O( max

j=1,...,p

1
2 2
λj sj log p/n)

= o(1/n),

where we used the result of Lemma 11 and applied Lemma 4. For the remainder r3 we have
r3 ≤ Eβ0 (ξ T (Σ̂Θ̂ − I)T (β̂ − β0 ))2

≤ kξk21 Eβ0 kΣ̂Θ̂ − Ik2∞ kβ̂ − β0 k21
1/2
1/2 

Eβ0 kβ̂ − β0 k41
≤ kξk21 Eβ0 kΣ̂Θ̂ − Ik4∞
= O( max λ2j s2 λ2 ) = o(1/n),
j=1,...,p

where we used Lemma 10 and Theorem 1.
Thus using the above calculations and using (25) we conclude that
varβ0 (b̂ξ ) = ξ T Θ0 ξ/n + o(1/n).

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

13

15.3. Proofs for Section 8.4: Main results for fixed design.
Proof of Theorem 4. The proof follows the same lines as the proof of
Theorem 2. The only difference is that we need to check the condition
2

pβ0 +h/√mn (Z) − pβ0 (Z)
T
− sβ0 (Z) h = o(n),
Eβ0
√
pβ0 (Z)/ mn
for fixed design, where pβ0 , Z and sβ0 are defined identically as in the proof of
√
Theorem 2. We denote u := h/ mn . Analogously as in the proof of Lemma
14 in Section 15.2, we obtain
2
 T
1 T
T
T T
= eu X Xu − 1 − uT X T Xu
Eβ0 e−ǫ Xu+ 2 u X Xu − 1 − ǫT Xu
= o(uT X T Xu) = o(nuT Σ̂u).

Then by the assumption hT Σ̂h = O(1) we obtain
o(nuT Σ̂u) = o(nhT Σ̂h/mn ) = o(hT Σ̂hn/mn ) = o(n/mn ).
√
Hence plugging in u = h/ mn and multiplying by mn we obtain
Eβ0



2
pβ0 +h/√mn (Z) − pβ0 (Z)
T
− sβ0 (Z) h = o(n).
√
pβ0 (Z)/ mn

Proof of Theorem 5. The lower bound follows by Theorem 4 (note
thatqg(β) = βj and thus the condition on g is satisfied) applied with h :=
Θ̂j / Θ̂jj . We only need to check that hT Σ̂h = O(1). By the assumption
q
β0 + Θ̂j / Θ̂jj n ∈ B(dn ) we obtain that sj := kΘ̂j k0 ≤ dn . Then
hT Σ̂h = Θ̂Tj Σ̂Θ̂j /Θ̂jj

(26)

≤ kΘ̂Tj k1 kΣ̂Θ̂j − ej k∞ /Θ̂jj + Θ̂Tj ej /Θ̂jj
√

≤ O
sj kΣ̂Θ̂j τ̂j2 − τ̂j2 k∞ + 1,

√
≤ O sj λj /τ̂j2 + 1 = o(1) + 1,

where we used the KKT condition for γ̂j , 1/τ̂j2 = Θ̂jj ≤ kΘ̂j k2 = O(1) and
√
sj ≤ dn = o( n/ log p). This yields the lower bound Θ̂jj + o(1).
Next we turn to proving the upper bound. Strong asymptotic unbiasedness of b̂j follows similarly as in Lemma 1 under the assumptions β0 ∈ B(dn ),

14

J. JANKOVÁ AND S. VAN DE GEER

√
satisfies the compatibility condition with a universal
dn = o ( n/log p), if Σ̂q
√
constant and β0 + Θ̂j / Θ̂jj n ∈ B(β0 , c/ n).
For the variance of
b̂j − βj0 = (Θ̂j )T X T ǫ/n + (Σ̂Θ̂j − ej )T (β̂ − β0 ),
we get (using that |Θ̂Tj Σ̂Θ̂j /Θ̂jj − 1| = o(1) as derived in (26))
varβ0 (b̂j ) = Θ̂Tj Σ̂Θ̂j /n + O(EkΣ̂Θ̂j − ej k2∞ kβ̂ − β0 k21 )

= Θ̂Tj Σ̂Θ̂j /n + O(kΣ̂Θ̂j − ej k2∞ Eβ0 kβ̂ − β0 k21 )

= Θ̂Tj Σ̂Θ̂j /n + O(λ2j /(τ̂j2 )2 s2 λ2 )

= Θ̂jj /n + o(1/n),

where we used 1/τ̂j2 = Θ̂jj ≤ kΘ̂j k2 = O(1).
15.4. Proofs for Section 8.5: Le Cam’s bounds.
Proof of Theorem 6. We apply Theorem 9 from Section 10. In this
setting, we have asymptotic linearity of the de-sparsified Lasso (see van
de Geer et al. (2014)) with the influence function lβ0 (Xi , Yi ) = (Θ0j )T Xi ǫi ,
where Θ0j is the j-th column of the precision matrix. We first show the bias
condition (22) is satisfied with the influence function lβ . By direct calculation, for any h ∈ Rp we have
Pβ0 (lβ0 hT sβ0 ) − hT ej

= (Θ0j )T EX1 ǫ21 X1T h − hj

= (Θ0j )T EX1 X1T E(ǫ21 |X1 )h − hj = 0.

Therefore in this case the bias condition holds. Hence we can conclude by
Theorem 9 that the de-sparsified estimator
b̂j = β̂j + Θ̂Tj X T (Y − X β̂)/n
satisfies for every β̃n ∈ B(β0 , √cn )
√

n(b̂j − β̃n )
(Θ0jj )1/2

β̃n

N (0, 1).

In addition, no asymptotically linear estimator satisfying the condition (22)
(here condition (13)) can have smaller asymptotic variance than Θ0jj as follows by the lower bound on the asymptotic variance in Lemma 3 in Section
10, i.e.
Vβ0 ≥ ġ(β0 )T Iβ−1
ġ(β0 ) + o(1) = Θ0jj + o(1).
0

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

15

16. Proofs for Section 9: Gaussian graphical models.
16.1. Proofs for Section 9.2: Strong asymptotic unbiasedness of the desparsified nodewise Lasso.
Proof of Lemma 2. By the Karush-Kuhn-Tucker conditions corresponding to the nodewise Lasso estimator, we have kΣ̂Θ̂i − ei k∞ = O(λi /τ̂i2 ).
Hence, and applying a version of Lemma 11 without the maximum over
j = 1, . . . , p, we obtain
EΘ0 (T̂ij − Θ0ij ) = EΘ0 (Θ0i )T (Σ̂ − Σ0 )Θ0j +EΘ0 (Θ̂i − Θ0i )T (Σ̂Θ0j − ej )
|
{z
}
=0

+ EΘ0 (Σ̂Θ̂i − ei )T (Θ̂j − Θ0j )

≤ (EΘ0 kΘ̂i − Θ0i k21 )1/2 (EΘ0 kΣ̂Θ0j − ej k2∞ )1/2

+ (EΘ0 kΣ̂Θ̂i − ei k2∞ )1/2 (EΘ0 kΘ̂j − Θ0j k21 )1/2

≤ O(si λi λj (EΘ0 1/(τ̂j2 )2 )1/2 ) + O(sj λi λj (EΘ0 1/(τ̂i2 )2 )1/2 )
√
= o(1/ n).

16.2. Proofs for Section 9.3: Main results. In this section we will give
the proof of Theorems 7 and 8. In the proof of Theorem 7, we use Lemma
20 which is stated and proved in Appendix B.
Proof of Theorem 7. The proof is similar to the proof of Theorem 2.
By strong asymptotic unbiasedness of Tn at Θ0 in the direction H, it follows

√
√
ξ1T Hξ2 =
mn ξ1T (Θ0 + H/ mn )ξ2 − ξ1T Θ0 ξ2


√
mn EΘ0 +H/√mn Tn (X) − EΘ0 Tn (X) + o(1)
=
Let sΘ0 (X) := −n(Σ̂ − Σ0 )/2. Denoting the probability density correspond-

16

J. JANKOVÁ AND S. VAN DE GEER

ing to X by pΘ , we may further rewrite the expressions to obtain


√
mn EΘ0 +H/√mn Tn (X) − EΘ0 Tn (X)
Z
√
= mn Tn (x)(pΘ0 +H/√mn (x) − pΘ0 (x))dz

pΘ0 +H/√mn (X) − pΘ0 (X)
mn EΘ0 Tn (X)
pΘ0 (X)


√
pΘ0 +H/ mn (X) − pΘ0 (X)
T
= EΘ0 Tn (X)
− vec(H) vec(sΘ0 (X))
√
pΘ0 (X)/ mn

=

√

+ EΘ0 Tn (X)vec(H)T vec(sΘ0 (X))

= EΘ0 (Tn (X) − ξ1T Θ0 ξ2 ) ×


pΘ0 +H/√mn (X) − pΘ0 (X)
T
− vec(H) vec(sΘ0 (X))
×
√
pΘ0 (X)/ mn
+ EΘ0 Tn (X)vec(H)T vec(sΘ0 (X)),

R
where
in
the
last
equality
we
used
that
E
s
(X)
=
0,
pΘ0 (x)dx = 1 and
Θ
Θ
0
0
R
√
pΘ0 +H/ mn (x)dx = 1. Since the variance of Tn is O(1/n) by the definition
of strong asymptotic unbiasedness, then

2
EΘ0 (Tn (X) − ξ1T Θ0 ξ2 ))2 = varΘ0 (Tn (X)) + EΘ0 (Tn (X) − ξ1T Θ0 ξ2 )
= O(1/n) + o(1/n) = O(1/n).

We need to use Lemma 20 in Appendix B to conclude that the remainder is
small. Lemma 20 implies
E



pΘ0 +H/√mn (X)
√
− 1 − vec(H)T vec(sΘ0 (X))/ mn
pΘ0 (X)

2

= o(δn ).

Consequently, and by the Cauchy-Schwarz inequality, we have the upper
bound


pΘ0 +H/√mn (X) − pΘ0 (X)
T
−
vec(H)
vec(s
(X))
EΘ0 (Tn (X) − ξ1T Θ0 ξ2 )
√
Θ0
pΘ0 (X)/ mn
q

EΘ0 (Tn (X) − ξ1T Θ0 ξ2 )2 ×
s

2
pΘ0 +H/√mn (X) − pΘ0 (X)
T
× E Θ0
− vec(H) vec(sΘ0 (X))
√
pΘ0 (X)/ mn
√  √
= O 1/ n o( n) = o(1).
≤

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

17

Thus we have
ξ1T Hξ2 = EΘ0 Tn (X)vec(H)T vec(sΘ0 (X)) + o(1).
Hence, because
|ξ1T Hξ2 | − |cov(Tn , vec(H)T vec(sΘ0 (X)))|

≤ |ξ1T Hξ2 − cov(Tn , vec(H)T vec(sΘ0 (X)))|

= o(1)

it follows using the Cauchy-Schwarz inequality that
|ξ1T Hξ2 | = |covΘ0 (Tn , tr(−n(Σ̂ − Σ0 )H/2))| + o(1)
q
p
varΘ0 (Tn ) varΘ0 (−ntr((Σ̂ − Σ0 )H/2)) + o(1).
≤

Now we have

varΘ0 (tr(n(Σ̂ − Σ0 )H/2)) = varΘ0 (ntr(Σ̂H/2))

= varΘ0 (ξ1T Θ0 X T XΘ0 ξ2 )/σ 2
= nvarΘ0 (ξ1T Θ0 X (1) (X (1) )T Θ0 ξ2 )/σ 2
= n(ξ1T Θ0 ξ1 ξ2T Θ0 ξ2 + (ξ1T Θ0 ξ2 )2 )/σ 2
= n.

Hence we conclude
|ξ1T Hξ2 | ≤

√ p
n varΘ0 (Tn ) + o(1).

Plugging in H = Θ0 (ξ1 ξ2T + ξ2 ξ1T )Θ0 /σ we obtain

|ξ1T Hξ2 |2 = (ξ1T Θ0 ξ1 ξ2T Θ0 ξ2 + (ξ1T Θ0 ξ2 )2 )2 /σ 2 = σ 2 .
By the strong asymptotic unbiasedness assumption on Tn , we have varΘ0 (Tn )
= O(1/n) and thus taking squares of both sides of the last inequality we
obtain
ξ1T Θ0 ξ1 ξ2T Θ0 ξ2 + (ξ1T Θ0 ξ2 )2
√ p
≤ nvarΘ0 (Tn ) + 2 n varΘ0 (Tn )o(1) + o(1)
≤ nvarΘ0 (Tn ) + o(1).

18

J. JANKOVÁ AND S. VAN DE GEER

Proof of Theorem 8. To obtain the lower bound on the variance, we
apply Theorem 7 with H := (Θ0i (Θ0j )T + Θ0j (Θ0i )T )/σ. Then by direct calculation, see that the condition tr(H T Σ0 H) = O(1) is satisfied for this choice
√
√
of H. Moreover, Θ0 + H/ n ∈ B(Θ0 , c/ n) by assumption, but then also
√
√
Θ0 +H/ mn ∈ B(Θ0 , c/ mn ). Hence by Theorem 7 follows the lower bound
T

varΘ0 (T ) ≥ ξ Θ0nξ+o(1) .
Next T̂ij is strongly asymptotically unbiased at Θ0 in every direction H such
√
that Θ0 + H/ n ∈ G(d1 , . . . , dp ), which follows by Lemma 2.
It remains to calculate the variance of T̂ij . First we have that

1
varΘ0 ((Θ0i )T X1 X1T Θ0j ) = (Θ0ii Θ0jj + (Θ0ij )2 )/n.
n
By basic calculations, it follows that

varΘ0 ((Θ0i )T (Σ̂ − Σ0 )Θ0j ) =

varΘ0 (T̂ij ) = (Θ0ii Θ0jj + (Θ0ij )2 )/n + O(EΘ0 ((Σ̂Θ0i − ei )T (Θ̂j − Θ0j ))2 )
+ O(EΘ0 ((Θ̂i − Θ0i )T (Σ̂Θ̂j − ej ))2 )

= (Θ0ii Θ0jj + (Θ0ij )2 )/n + O(EΘ0 kΣ̂Θ0i − ei k2∞ kΘ̂j − Θ0j k21 )
+ O(EΘ0 kΘ̂i − Θ0i k21 kΣ̂Θ̂j − ej k21 ).

= (Θ0ii Θ0jj + (Θ0ij )2 )/n

+O((EΘ0 kΣ̂Θ0i − ei k4∞ )1/2 (EΘ0 kΘ̂j − Θ0j k41 )1/2 )

+ O((EΘ0 kΘ̂i − Θ0i k41 )1/2 (EΘ0 kΣ̂Θ̂j − ej k41 )1/2 )

= (Θ0ii Θ0jj + (Θ0ij )2 )/n + O(λ2i s2j λ2j (EΘ0 1/(τ̂i2 )2 )1/2 )
+ O(s2i λ2i λ2j (EΘ0 1/(τ̂j2 )2 )1/2

= (Θ0ii Θ0jj + (Θ0ij )2 )/n + o(1/n).

17. Proofs for Section 10: Le Cam’s bounds for general models.
In this section we give the proof of Theorem 9, for which we need Lemma 16
below. Some technical results (contained in Lemmas 21 and 23) are stated
and proved in Appendix C.
Lemma 16. Assume the conditions of Theorem 9. Suppose that Zn
Z,
where Z is a random vector with values in R2 . Let Xn = ψ(Zn ) and Un =
ψ(Z), where

 


 √
−v12
x1
1/ v11 0
1/2
V
+
.
x 7→ ψ(x1 , x2 ) =
0
1
−v22 /2
x2
Then the following statements hold.

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

19

1. For any function f : R2 → R which is bounded and continuous it holds
that
lim Ef (Xn ) − Ef (Un ) = 0.
n→∞

2. Let f be any bounded and continuous function f : R → R. Suppose
that
lim lim E min(0, M − eUn,2 ) = 0.
M →∞ n→∞

Then it holds that
lim Ef (Xn,1 )eXn,2 − Ef (Un,1 )eUn,2 = 0.

n→∞

Proof of Lemma 16. We first prove the first statement. Let ǫ > 0 and
let f : R2 → R be continuous and bounded.
The map ψ is linear, i.e. ψ(x) = Ax + b for some A ∈ R2×2 and b ∈ R2 (A, b
depending on n). Denote
 √

1/ v11 0
D :=
0
1
Observe that for any x ∈ R2
kAxk22 = xT AT Ax = xT DV Dx ≤ Λmax (DV D)xT x.
By Lemma 22 we have that Λmax (DV D) = O(1) and kbk2 = O(1). Therefore, when kxk2 = O(1), then
(27)

kAx + bk2 = O(1).

Take a compact rectangle R ⊂ R2 not depending on n and such that P (Z 6∈
R) < ǫ.
Divide the rectangle R into a finite number of non-overlapping rectangles
of diameter at most δ/L1/2 , where L is a universal constant such that L ≥
Λmax (DV D). By construction, the number of these rectangles, denote it N ,
does not depend on n. So we have R = ∪N
j=1 Rj , where each Rj is a rectangle
of diameter at most δ/L1/2 .
For all x, y ∈ Rj it holds that kx − yk2 ≤ δ/L1/2 and thus
(28)

kψ(x) − ψ(y)k2 = kA(x − y)k2 ≤ L1/2 kx − yk2 ≤ δ.

Note that by (27), there exists a compact set S not depending on n such
that ψ(R) ⊂ S for all n. The continuous function f is uniformly continuous
on the compact set S. Hence for the ǫ there exists a δ > 0 such that for all

20

J. JANKOVÁ AND S. VAN DE GEER

z, v ∈ S it holds that if kz − vk2 < δ then |f (z) − f (v)| < ǫ. But then since
for all x, y ∈ Rj we have that ψ(x), ψ(y) ∈ S, we obtain by (28) and the
absolute continuity of f that
|f (ψ(x)) − f (ψ(y))| < ǫ
P
for all n. Take a point xj from each set Rj and define fǫ = N
j=1 f (ψ(xj ))1Rj .
Then |f (ψ(x)) − fǫ (x)| < ǫ for all x ∈ R (and all n) and hence if f takes
values in [−K, K], we have the following upper bounds
(29)

|Ef (ψ(Z)) − Efǫ (Z)| ≤ ǫ + 2KP (Z 6∈ R),

(30)

|Ef (ψ(Zn )) − Efǫ (Zn )| ≤ ǫ + 2KP (Zn 6∈ R),

(31)

|Efǫ (Zn ) − Efǫ (Z)| ≤

Since Zn

N
X
j=1

|P (Zn ∈ Rj ) − P (Z ∈ Rj )||f (ψ(xj ))|.

Z, for all j = 1, . . . , N it holds
|P (Zn ∈ Rj ) − P (Z ∈ Rj )| → 0.

Similarly,
|P (Z 6∈ R) − P (Zn 6∈ R)| = |P (Z ∈ R) − P (Zn ∈ R)| → 0.
Finally, by construction we have P (Z 6∈ R) < ǫ. We thus conclude that
the upper bounds (29), (30) and (31) can be made smaller than Cǫ for n
sufficiently large. The claim follows by combining the three upper bounds.
Next we prove the second statement. Denote g(x1 , x2 ) = f (x1 )ex2 . We
write g = g+ − g− , where g+ = max{g, 0} is the positive part and g− :=
max{−g, 0} is the negative part. We first prove for the positive part g+ that
lim Eg+ (Xn ) − Eg + (Un ) = 0.

(32)

n→∞

This will be achieved by first showing that
lim inf Ef + (Xn )eXn,2 − Ef + (Un )eUn,2 ≥ 0
n→∞

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

21

and secondly showing that
lim sup Ef + (Xn )eXn,2 − Ef + (Un )eUn,2 ≤ 0.
n→∞

Then combining the two gives (32).
First we prove that lim inf n→∞ Ef + (Xn )eXn,2 −Ef + (Un )eUn,2 ≥ 0. For every
M , since g+ is non-negative, it holds that f + (x)ex2 ≥ f + (x)(ex2 ∧M ), where
the symbol ∧ denotes the minimum. Hence
Ef + (Xn )eXn,2 − Ef + (Un )eUn,2

≥ Ef + (Xn )(eXn,2 ∧ M ) − Ef + (Un )eUn,2

= [Ef + (Xn )(eXn,2 ∧ M ) − Ef + (Un )(eUn,2 ∧ M )]
+ [Ef + (Un )(eUn,2 ∧ M ) − Ef + (Un )eUn,2 ]

We have f + (x)(ex2 ∧ M ) − f +(x)ex2 = f + (x) min(0, M − ex2 ). Taking limes
inferior of both sides, it follows that
lim inf Ef + (Xn )eXn,2 − Ef + (Un )eUn,2
n→∞

≥ lim inf [Ef + (Xn )(eXn,2 ∧ M ) − Ef + (Un )(eUn,2 ∧ M )]
n→∞

+ lim inf −Ef + (Un ) min(0, M − eUn,2 ).
n→∞

For every fixed M , the function x 7→ f + (x)(ex2 ∧ M ) is bounded and continuous. We may thus apply the first result of the lemma to conclude
lim inf Ef + (Xn )(eXn,2 ∧ M ) − Ef + (Un )(eUn,2 ∧ M ) = 0.
n→∞

Therefore, we have
lim inf Ef + (Xn )eXn,2 − Ef + (Un )eUn,2

(33)

n→∞

≥ lim inf −Ef +(Un ) min(0, M − eUn,2 ).
n→∞

Next since |f + | ≤ K we have
| − Ef +(Un ) min(0, M − eUn,2 )| ≤ KE min(0, M − eUn,2 ).
Then the assumption
lim lim E min(0, M − eUn,2 ) = 0

m→∞ n→∞

22

J. JANKOVÁ AND S. VAN DE GEER

implies that also
lim lim inf −Ef +(Un ) min(0, M − eUn,2 )

m→∞

n

= − lim lim sup Ef + (Un ) min(0, M − eUn,2 ) = 0,
m→∞

n

so we conclude that
lim inf Ef + (Xn )eXn,2 − Ef + (Un )eUn,2 ≥ 0.

(34)

n→∞

Now we prove
lim sup Ef + (Xn )eXn,2 − Ef + (Un )eUn,2 ≤ 0.
n→∞

Similarly as before, since K − f + ≥ 0 (K is an upper bound on f ), we have
that
lim inf E(K − f + (Xn,1 ))eXn,2 − E(K − f + (Un,1 ))eUn,2
n→∞

≥ lim inf E(K − f + (Xn,1 ))(eXn,2 ∧ M ) − E(K − f + (Un,1 ))(eUn,2 ∧ M )
n→∞

(35) + lim inf E(K − f + (Un,1 ))(eUn,2 ∧ M ) − E(K − f + (Un,1 ))eUn,2 .
n→∞

By the the first part of the lemma, we have that for every fixed M it holds
lim inf E(K − f + (Xn,1 ))(eXn,2 ∧ M ) − E(K − f + (Un,1 ))(eUn,2 ∧ M ) = 0,
n

since the function (x1 , x2 ) 7→ (K − f + (x1 ))(ex2 ∧ M ) is bounded and continuous.
For the term in (35), we have since |K − f + | ≤ 2K
| − E(K − f + (Un,1 )) min(0, M − eUn,2 )| ≤ 2KEeUn,2 min(0, M − eUn,2 ).
Hence by the assumption limm→∞ limn→∞ E min(0, M − eUn,2 ) = 0, we have
that
lim inf −E(K − f + (Un,1 )) min(0, M − eUn,2 ) = 0.
n→∞

Thus we conclude that
lim inf E(K − f + (Xn,1 ))eXn,2 − E(K − f + (Un,1 ))eUn,2 ≥ 0.
n→∞

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

23

Now note that
lim inf E(K − f + (Xn,1 ))eXn,2 − E(K − f + (Un,1 ))eUn,2
n→∞

= lim inf −Ef + (Xn,1 )eXn,2 + Ef + (Un,1 )eUn,2
n

= − lim sup Ef + (Xn,1 )eXn,2 − Ef + (Un,1 )eUn,2 .
n

So in conclusion we have shown that
lim sup Ef + (Xn,1 )eXn,2 − Ef + (Un,1 )eUn,2
n

≤ 0 ≤ lim inf Ef + (Xn,1 )eXn,2 − Ef + (Un,1 )eUn,2 .
n

This proves (32).
The same procedure can be used for the negative part f − (since f − is also
bounded and positive) to show that
lim Ef − (Xn,1 )eXn,2 − Ef − (Un,1 )eUn,2 = 0.

n→∞

We then conclude that
lim Ef (Xn,1 )eXn,2 − Ef (Un,1 )eUn,2

n→∞

≤ lim |Ef + (Xn,1 )eXn,2 − Ef + (Un,1 )eUn,2 |
n→∞

+ lim |Ef − (Xn,1 )eXn,2 − Ef − (Un,1 )eUn,2 |
n→∞

= 0.

Proof of Theorem 9. We denote ℓβ (x) := log pβ (x) and
Λn :=

n
X
i=1

ℓβn,0 +h/√n (X (i) ) − ℓβn,0 (X (i) ).

Further for 0 ≤ t ≤ 1 denote g(t) := ℓ((1 − t)β + tβ0 ). Then by a two-term
Taylor expansion of g we have
1
g(1) − g(0) = ġ(0) + g̈(t̃),
2
where 0 ≤ t̃ ≤ 1. Rewriting this from the definition of g gives
1
ℓβ − ℓβ0 = ℓβ0 (β − β0 ) + (β − β0 )T ℓ̈β̃ (β − β0 ),
2

24

J. JANKOVÁ AND S. VAN DE GEER

√
where β̃ := (1 − t̃)β + t̃β0 . Applying the above with β̃ := βn,0 + h/ n and
β0 := βn,0 we obtain
n
n
X
1
1 T1X
(i) T
√ ℓ̇βn,0 (X ) h + h
ℓ̈β̃ (X (i) )h,
Λn :=
n
2 n
i=1

i=1

√
√
where β̃ := (1 − t̃)(βn,0 + h/ n) + t̃βn,0 = βn,0 + (1 − t̃)h/ n. We can then
write the decomposition of Λn as follows
n

n

i=1
n
X

i=1
n
X

1 1X
1 X T
√
ℓ̈β̃ (X (i) )h
h ℓ̇βn,0 (X (i) ) + hT
n
2 n

Λn =

1
√
n

=

i=1

1
+ hT
2
|

(36)

hT ℓ̇βn,0 (X (i) ) +

1 T1
h
2
n
|

i=1

(ℓ̈β̃ (X (i) ) − ℓ̈βn,0 (X (i) ))h
{z

rem1

!
n
1X
(i)
ℓ̈βn,0 (X ) + I(βn,0 ) h
n
i=1
{z
}

}

rem2

1
− hT I(βn,0 )h.
2

We will now show that the remainders rem1 , rem2 converge in probability
√
to zero. First observe that since βn,0 + h/ n ∈ B(βn,0 , √cn ), this implies
that khk2 ≤ c and khk0 ≤ 2s. Combining these two properties yields khk1 ≤
√
√
2sc = O( s).
Regarding the first remainder we have for each j, k = 1, . . . , p
n
n
1X
1 X ...
(ℓ̈β̃ (X (i) ) − ℓ̈βn,0 (X (i) ))j,k =
( ℓ β̄ (X (i) )T (β̃ − βn,0 ))j,k ,
n
n
i=1

i=1

...
where β̄ = (1 − t)β̃ + tβn,0 . By assumption k ℓ β̄ k∞ ≤ L and hence using
Hölder’s inequality
n

n

1 X ...
1X
(i)
ℓ̈β̃ (X (i) ) − ℓ̈βn,0 (X (i) )k∞ ≤ k
k
ℓ β̄ (X )k∞ kβ̃ − βn,0 k1
n
n
i=1
i=1
p
√
≤ Lk(1 − t̃)h/ nk1 = O( s/n).

Thus using Hölder’s inequality, for the first remainder we get

n
√
1X
(ℓ̈β̃ (X (i) ) − ℓ̈βn,0 (X (i) ))h| ≤ O(s3/2 / n) = o(1).
|h
n
T

i=1

25

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

For the second remainder we have using assumption k n1
I(βn,0 )k∞ = OP (λ) that
n

khT (

Pn

i=1 ℓ̈βn,0 (X

(i) )

+

n

1X
1X
ṡβn,0 (X (i) ) + I(βn,0 ))hk∞ ≤ khk21 k
ṡβn,0 (X (i) ) + Iβn,0 k∞
n
n
i=1

i=1

= OP (sλ) = oP (1).

Hence collecting the results, from the decomposition of Λn we have
n

Λn =

(37)

1 X T
1
√
h ℓ̇βn,0 (X (i) ) − hT I(βn,0 )h + oP (1).
2
n
i=1

We introduce the following notation. Let


Vβn,0
Pβn,0 (lβn,0 hT sβn,0 )
V :=
Pβn,0 (lβn,0 hT sβn,0 )
hT I(βn,0 )h
Furthermore, we denote the entries of the matrix V by vij , i, j = 1, 2.
The condition (D3) implies that for any fixed a ∈ R2 it holds for all ǫ > 0
lim E(aT V −1/2 (lβn,0 (X (i) ), hT sβn,0 (X (i) ))T )2 ×

n→∞

×1|aT V −1/2 (l

βn,0 (X

(i) ),hT s

βn,0 (X

(i) ))T |>ǫ

√
naT a

= 0,

where we used that kV k∞ = O(1), which follows by Lemma 22. By the
Lindeberg’s central limit theorem we thus have by condition (38) for any
a ∈ R2 that
√

1
naT a

n
X

aT V −1/2 (lβn,0 (X (i) ), hT sβn,0 (X (i) ))T

i=1

N (0, 1).

Hence, using the likelihood expansion (37) and by the asymptotic linearity
(19), we conclude that
√
1
aT V −1/2 ( n(Tn − g(βn,0 )), Λn + hT I(βn,0 )h)
2

aT Z, where Z ∼ N (0, I2 ).

Then by the Wold device we have
 √

βn,0
n(Tn − g(βn,0 ))
−1/2
Zn := V
N2 (0, I) ∼ Z.
1 T
Λn + 2 h I(βn,0 )h

26

J. JANKOVÁ AND S. VAN DE GEER

Now let f : R → R be bounded and continuous. We may rewrite
√

n(Tn − g(βn,0 )) − v12
√
Eβn,0 +h/ n f
√
v11
√

n(Tn − g(βn,0 )) − v12
= Eβn,0 f
eΛn
√
v11
= Eβn,0 f (Xn,1 )eXn,2 ,

where Xn := (Xn,1 , Xn,2 ) = ψ(Zn ) for the function ψ given by
 √



1/ v11 0
−v12
1/2
T
ψ(x1 , x2 ) =
V (x1 , x2 ) +
.
0
1
−v22 /2
Similarly, define Un as follows
Un := (Un,1 , Un,2 ) = ψ(Z)


 √

−v12
1/ v11 0
V 1/2 N (0, I2 ) +
∼
0
1
−v22 /2
!!
!
√v12
1
− √vv1211
v11
.
= N
,
v
√ 12
v
− v222
22
v11
Since we know that Zn
Z, we hope that in some sense Xn = ψ(Zn ) is
close to Un = ψ(Z). Note that the function ψ depends on n, so we cannot
directly apply the Portmanteau Lemma.
We aim to apply Lemma 16 with Xn = ψ(Zn ) and Un = ψ(Z) defined above
and with the function g(x1 , x2 ) = f (x1 )ex2 . By Lemma 23, we have that
lim lim E| min(0, M − eUn,2 )| = 0.

M →∞ n→∞

Hence we get by the second part of Lemma 16
lim Eg(Xn ) − Eg(Un ) = 0.

n→∞

Next we calculate Eg(Un ). We have
Un,2

Eβn,0 g(Un ) = Ef (Un,1 )e

=

Z

R2

f (u1 ) eu2 fUn (u1 , u2 )du,

where fY denotes the density of a random variable Y. We use Lemma 21 to
obtain that fUn (u)eu2 = fY (u), where
!!


√v12
1
0
v11
.
Y ∼N
,
√v12
v
v22 /2
22
v11

27

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

Hence
Eβn,0 g(Un ) =

Z

R2

f (u1 ) fY (u1 , u2 )du = Ef (Y1 ),

where Y ∼ N (0, 1). Hence for any bounded continuous function f we have
shown
√

n(Tn − g(βn,0 )) − v12
√
− Ef (Y )| = 0.
lim |Eβn,0 +h/ n f
√
n→∞
v11
By the Portmanteau Lemma (note that Y in the above display does not
depend on n), we thus have
√
√
n(Tn − g(βn,0 )) − v12 βn,0 +h/ n
N (0, 1).
√
v11
Therefore, by the differentiability assumption (D1) on g, we get
√
√
n(Tn − g(βn,0 + h/ n)) + hT ġ(βn,0 ) − Pβn,0 lβn,0 hT sβn,0 βn,0 +h/√n
Vβn,0 1/2

N (0, 1).

APPENDIX A: PROOFS FOR SECTION 14
Before proving Lemmas 9, 10, 11 and 12 we first recall a version of Theorem
2.4 from van de Geer et al. (2014). We denote ηj := Xj −X−j γj0 , j = 1, . . . , p.
Theorem 10 (a version of Theorem 2.4 in van de Geer et al. (2014)).
Suppose that conditions (A2*) are satisfied and assume that sj log p/n =
o(1). Consider the p
nodewise regression estimator Θ̂j and the corresponding
2
τ̂j with λj = λ ≥ τ log p/n for j = 1, . . . , p. Then for τ > 1, on the set
p
T
Tj := {kX−j
ηj k∞ /n ≤ cτ log p/n,
p
kΣ̂−j,−j − Σ0−j,−j k∞ ≤ cτ log p/n,
p
|ηjT ηj /n − τj2 | ≤ cτ log p/n},
(where c is some sufficiently large constant), we have the following claims
for j = 1, . . . , p,
q
p
kγ̂j − γj0 k1 ≤ Cτ sj log p/n, |τ̂j2 − τj2 | ≤ Cτ sj log p/n,
p
kΘ̂j − Θ0j k1 ≤ Cτ sj log p/n,
for some constant Cτ > 0. Moreover, for some constant c1 > 0 we have
2

P (Tjc ) ≤ c1 (2p)−τ .

28

J. JANKOVÁ AND S. VAN DE GEER

Proof of Lemma 9. The proof of this lemma is essentially the same
as the proof of Theorem 1, but we need to make adjustments to obtain an
oracle bound for the expectation of the maximum of ℓ1 -errors of p Lasso
estimators, i.e. we show an oracle bound for
(E max kγ̂j − γj kk1 )1/k .
j=1,...,p

First we summarize the oracle inequality for the nodewise regression which
holds with high probability. Let ηj := Xj − X−j γj0 for j = 1, . . . , p, then ηj is
a sub-Gaussian random vector with a universal constant, since Λmax (Θ0 ) =
1/Λmin (Σ0 ) = O(1). Under 1/Λmin (Σ0 ) = O(1), one can check that for
some universal constant L > 0, it holds Λmin (Σ0−j,−j ) ≥ L. Let Tj be as
in Theorem 10. Then on T := ∩pj=1 Tj it holds maxj=1,...,p kγ̂j − γj0 k1 ≤
16λj maxj=1,...,p sj /L.
We now proceed to show that the oracle inequality for the Lasso holds also
in expectation. We follows the steps of the proof of Theorem 1 to get


E max (kǫj k2n /λj + 2kγj0 k1 )k ≤ E max 2k−1 (kǫj k2n /λj )k + (2kγj0 k1 )k
j=1,...,p

j=1,...,p

By Lemma 5 we have

E max (kǫj k2n )k = O(1).
j=1,...,p

Next observe that by assumption on the eigenvalues of Θ0 , we have kγj0 k2 =
O(1) and hence
kγj0 kk1 ≤ ( max

j=1,...,p

√

k/2

sj kγj0 k2 )k ≤ O( max sj ).
j=1,...,p

Further steps again follow the steps of the proof of Theorem 1. Thus we
obtain
E max kγ̂j − γj0 kk1 = O( max skj λkj ),
j=1,...,p

j=1,...,p

where we chose τ sufficiently large (this is possible since k is fixed) so that
k/2

−τ
max sj λ−k
j p

j=1,...,p

2 /2

= O( max skj λkj ).
j=1,...,p

Hence we conclude that
(38)

(E max kγ̂j − γj0 kk1 )1/k = O( max sj λj ).
j=1,...,p

j=1,...,p

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

29

Proof of Lemma 10. Before proving statements 1) and 2) of the lemma,
we first prove that E maxj=1,...,p 1/(τ̂j2 )k = O(1). Throughout the proof, we
use the notation
Γ̂j := (−γ̂j,1 , . . . , −γ̂j,j−1 , 1, −γ̂j,j+1 , . . . , −γ̂j,p ).
Proof of E maxj=1,...,p 1/(τ̂j2 )k = O(1):
We first show the rough bound E maxj=1,...,p
that for each j = 1, . . . , p it holds for t ≥ 0

1
(τ̂j2 )k

= O(pnk/2 ). First observe

P (τ̂j2 ≤ t) = P (Γ̂Tj Σ̂Γ̂j + λj kγ̂j k1 ≤ t)

≤ P (Γ̂Tj Σ̂Γ̂j ≤ t ∧ λj kγ̂j k1 ≤ t)

Using the following lower bound
Γ̂Tj Σ̂Γ̂j = Σ̂jj − 2Σ̂Tj,−j γ̂j + γ̂jT Σ̂−j,−j γ̂j

≥ Σ̂jj − 2|Σ̂Tj,−j γ̂j | + γ̂jT Σ̂−j,−j γ̂j

≥ Σ̂jj − 2kΣ̂j,−j k∞ kγ̂j k1 + γ̂jT Σ̂−j,−j γ̂j

≥ Σ̂jj − 2Σ̂jj t/λj

= Σ̂jj (1 − 2t/λj ),

we obtain that
P (Γ̂Tj Σ̂Γ̂j ≤ t ∧ λj kγ̂j k1 ≤ t) ≤ P (Σ̂jj (1 − 2t/λj ) ≤ t ∧ λj kγ̂j k1 ≤ t)
≤ P (Σ̂jj (1 − 2t/λj ) ≤ t).

Next we use concentration results for Σ̂jj around its mean under the subGaussianity assumption on X. For t ≤ λj /4 it holds that 1 − 2t/λj ≥ 1/2
and thus


P (Σ̂jj (1 − 2t/λj ) ≤ t) = P Σ̂jj − Σ0jj ≤ 2t − Σ0jj .

For 0 < t < λj /4 and n sufficiently large it holds that 2t − Σ0jj < 0 (by the
minimal eigenvalue condition on Σ0 ) and thus


P (Σ̂jj (1 − 2t/λj ) ≤ t) = P Σ̂jj − Σ0jj ≤ 2t − Σ0jj


≤ P |Σ̂jj − Σ0jj | ≥ |2t − Σ0jj |
√
0
≤ e−c(Σjj −2t) n/ log pn ,

30

J. JANKOVÁ AND S. VAN DE GEER

for some constant c > 0. Hence collecting the above inequalities, we have so
far shown that for any 0 < t < λj /4 and n sufficiently large it holds
√
0
(39)
P (τ̂j2 ≤ t) ≤ e−c(Σjj −2t) n/ log p .
Then by rewriting the expectation as an integral
Z ∞
1
P ( max 1/(τ̂j2 )k > x)dx
=
E max
j=1,...,p
j=1,...,p (τ̂j2 )k
0
Z ∞
max pP (1/(τ̂j2 )k > x)dx
=
0 j=1,...,p
Z 1
max P (1/(τ̂j2 )k > x)dx
= p
0 j=1,...,p
Z (λj /4)−k

+ p

1

+ p

Z

∞

(λj /4)

max P (1/(τ̂j2 )k > x)dx

j=1,...,p

max P (1/(τ̂j2 )k > x)dx

−k

≤ p + p(λj /4)

j=1,...,p

−k

+p

Z

∞
(λj /4)−k

|

Next we calculate an upper bound on ii.
Z ∞
Z
2 k
ii =
P (1/(τ̂j ) > x)dx =
(λj /4)−k

=

P (1/(τ̂j2 )k > x)dx
{z
ii

∞

(λj /4)−k
Z ∞
(λj /4)

}

P (1/τ̂j2 > x1/k )dx
P (τ̂j2 < x−1 )dx

−1

Now we can use the bound (39) since x−1 ≤ λj /4. Using the bound and by
standard calculations, we obtain
Z ∞
Z ∞
√
0
2
−1
e−c(Σ11 −2/x) n/ log pn dx = o(1).
P (τ̂j < x )dx ≤
(λj /4)−1

(λj /4)−1

Hence we obtain the rough bound


1
−k
= O(pnk/2 /(log p)k/2 ).
=
O
p
(λ
/4)
E max
j
j=1,...,p (τ̂j2 )k

Define, for τ > 1 and j = 1, . . . , p, the sets

T
Tj := {kX−j
ηj k∞ /n ≤ cτ

p

log p/n,
p
kΣ̂−j,−j − Σ0−j,−j k∞ ≤ cτ log p/n,
p
kηjT ηj /n − τj2 k∞ ≤ cτ log p/n},

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

31

(where c is some sufficiently large constant). Then by Theorem 10, on T =
∩pj=1 Tj we have maxj=1,...,p 1/(τ̂j2 )k ≤ Cτ for some constant Cτ > 0. But
then and by the Cauchy-Schwarz inequality
E max

j=1,...,p

1
(τ̂j2 )k

1
1
1T + E max
1T c
j=1,...,p (τ̂j2 )k
(τ̂j2 )k
q
p
2
≤ O(1) + O(pnk/2 ) 2p(2p)−τ /2 = O(1),

= E max

j=1,...,p

where we chose τ sufficiently large.

Proof of part 1) First we show that E(τ̂j2 )k = O(1). We have
τ̂j2 = kXj − X−j γ̂j k2n + λj kγ̂j k1
= Γ̂Tj Σ̂Γ̂j /n + λj kγ̂j k1

≤ kΓ̂j k21 kΣ̂k∞ + λj kγ̂j k1 .
Hence by basic calculations
ik
kΓ̂j k21 kΣ̂k∞ + λj kγ̂j k1
j=1,...,p
i
h
≤ 2k−1 E max (kΓ̂j k21 kΣ̂k∞ )k + (λj kγ̂j k1 )k .

E max (τ̂j2 )k ≤ E max
j=1,...,p

h

j=1,...,p

We have
E max kγ̂j kk1 ≤ E max (kγ̂j − γj0 k1 + kγj0 k1 )k
j=1,...,p

j=1,...,p

≤ E max 2k−1 (kγ̂j − γj0 kk1 + kγj0 kk1 )
j=1,...,p
k/2

= O(sj ).
Hence
E max (τ̂j2 )k ≤ E max
j=1,...,p

j=1,...,p

= O(s2k
j ).

h

kΓ̂j k21 kΣ̂k∞ + λj kγ̂j k1

ik

Hence, by Theorem 10, on T we have that maxj=1,...,p τ̂j2 = O(1), hence it
follows
E max (τ̂j2 )k = E max (τ̂j2 )k 1T + E max (τ̂j2 )k 1T c = O(1).
j=1,...,p

j=1,...,p

j=1,...,p

32

J. JANKOVÁ AND S. VAN DE GEER

We have under 1/Λmin (Θ0 ) = O(1) that τj2 = 1/Θ0jj = O(1) and hence
E max |τ̂j2 − τj2 |k = O(E max (τ̂j2 )k + (τj2 )k ) = O(1).
j=1,...,p

j=1,...,p

We can then apply the same procedure as before to get
E max |τ̂j2 − τj2 |k = E max |τ̂j2 − τj2 |k 1T + E max |τ̂j2 − τj2 |k 1T c
j=1,...,p
j=1,...,p
j=1,...,p
√
= O( max sj λj ).
j=1,...,p

Proof of part 2) First we have
E max

j=1,...,p

≤ E max

1
1
− 2
2
τ̂j
τj

k

|τ̂j2 − τj2 |k

(τ̂j2 )k (τj2 )k
r
r
≤ max 1/(τj2 )k E max |τ̂j2 − τj2 |2k E max 1/(τ̂j2 )2k .
j=1,...,p

j=1,...,p

j=1,...,p

j=1,...,p

Using that E maxj=1,...,p 1/(τ̂j2 )2k = O(1) and Part 1), we obtain the claim.
Proof of Lemma 11. For some τ > 0 and each j = 1, . . . , p define the
sets
p
T
Tj := {kX−j
ηj k∞ /n ≤ cτ log p/n,
p
kΣ̂−j,−j − Σ0−j,−j k∞ ≤ cτ log p/n,
p
kηjT ηj /n − τj2 k∞ ≤ cτ log p/n},

By Theorem 10, when λj ≥ cτ
∩pi=1 Tj that

p

log p/n uniformly in j, we have on the set

max kΘ̂j − Θ0j k1 ≤ Cτ max sj λj ,

j=1,...,p

j=1,...,p

max |τ̂j2 − τj2 | ≤ Cτ max

j=1,...,p

j=1,...,p

√

s j λj ,

for some Cτ > 0. Next we rewrite
E max kΘ̂j − Θ0j kk1 = E max kΘ̂j − Θ0j kk1 1T + E max kΘ̂j − Θ0j kk1 1T c .
j=1,...,p

j=1,...,p

j=1,...,p

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

33

Then
E max kΘ̂j − Θ0j kk1
j=1,...,p

k
kγ̂j − γj0 k1 /τ̂j2 + kγj0 k1 |1/τ̂j2 − 1/τj2 |
j=1,...,p
i
h
≤ E max 2k−1 (kγ̂j − γj0 k1 /τ̂j2 )k + (kγj0 k1 |1/τ̂j2 − 1/τj2 |)k
≤ E max



j=1,...,p

= O((sj λj )k ),

where in the last display we used Lemmas 9 and 10.
Proof of Lemma 12. Let ηj := Xj − X−j γj0 . The Karush-Kuhn-Tucker
corresponding to the optimization problem (6) give
T
Σ̂−j,−j γ̂j + λj Ẑj = X−j
ηj /n,

where Ẑj,i = sign(γ̂j,i ) if γ̂j,i 6= 0 and Ẑj,i ∈ [−1, 1] otherwise, for i = 1, . . . , p.
Rearranging them, we obtain
T
Σ0−j,−j (γ̂j − γj0 ) + λj Ẑj = X−j
ηj /n + (Σ0−j,−j − Σ̂−j,−j )(γ̂j − γj0 ).

(40)
Firstly,

kΣ0−j,−j (γ̂j − γj0 )k22 ≤ Λmax (Σ0−j,−j )kX−j (γ̂j − γj0 )k2n

+ Λmax (Σ0−j,−j )kγ̂j − γj0 k21 kΣ̂ − Σ0 k∞ .

Secondly,
k(Σ0−j,−j − Σ̂−j,−j )(γ̂j − γj0 )k∞ ≤ kΣ0−j,−j − Σ̂−j,−j k∞ kγ̂j − γj0 k1 .
Denote ŝj := kγ̂j k0 . On the set
T
Tj := {kX−j
ηj /nk∞ ≤ λ0 , k(Σ0−j,−j − Σ̂−j,−j )(γ̂j − γj0 )k∞ ≤ λ0 },

we have
T
kλj Ẑj + X−j
ηj /n + (Σ0−j,−j − Σ̂−j,−j )(γ̂j − γj0 )k22

=

p
X
i=1

|λj Ẑj,i + XiT ηj + eTi (Σ0−j,−j − Σ̂−j,−j )(γ̂j − γj0 )|2

≥ (λj − 2λ0 )2 ŝ.

34

J. JANKOVÁ AND S. VAN DE GEER

Combining the above observations, we obtain
Λmax (Σ0−j,−j )kX−j (γ̂j − γj0 )k2n + Λmax (Σ0−j,−j )kγ̂j − γj0 k21 kΣ̂ − Σ0 k∞

≥ kΣ0−j,−j (γ̂j − γj0 )k22

T
= k − λẐj + X−j
ηj /n + (Σ0−j,−j − Σ̂−j,−j )(γ̂j − γj0 )k22

≥ (λj − 2λ0 )2 ŝ.
Hence on the set T ,

Λmax (Σ0−j,−j )kX−j (γ̂j − γj0 )k2n + Λmax (Σ0−j,−j )kγ̂j − γj0 k21 kΣ̂ − Σ0 k∞
.
(λj − 2λ0 )2
p
Finally, taking λ0 := c log p/n for some c > 0 sufficiently large and taking
λ ≥ 3λ0 and under the assumption Λmax (Σ0 ) = O(1), we obtain
ŝj ≤

ŝj = OP (sj ).

APPENDIX B: ADDITIONAL PROOFS FOR SECTION 16
In this section we give Lemma 20 and its proof, but we need the following
auxiliary Lemmas 17, 18, 19.
Lemma 17. Let x ∼ N (0p , Σ0 ) and let Θ0 = Σ−1
0 . Then for any t ∈ R
p×p
and A ∈ R
such that Θ0 − 2tA is symmetric and positive definite it holds

1/2
det(Θ0 )
txT Ax
.
E Θ0 e
=
det(Θ0 − 2tA)
Proof of Lemma 17. By direct calculation, we obtain
Z
det(Θ0 )1/2 − 1 xT Θ0 x txT Ax
txT Ax
E Θ0 e
=
e
dx
e 2
(2π)p/2
Rp
Z
det(Θ0 )1/2 − 1 xT (Θ0 −2tA)x
e 2
=
dx
(2π)p/2
Rp
Z
det(Θ0 )1/2 det(Θ0 − 2tA)1/2 − 1 xT (Θ0 −2tA)x
e 2
=
dx
(2π)p/2 det(Θ0 − 2tA)1/2
Rp
=

det(Θ0 )1/2
.
det(Θ0 − 2tA)1/2

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

35

√
Lemma 18. Suppose that Θ0 + H/ mn is a symmetric positive definite
matrix. Let pΘ0 be the joint density of the random sample x1 , . . . , xn , where
each xi is an N (0, Θ−1
0 )-distributed random vector. Then it holds
2

pΘ0 +H/√mn (x)
√
− 1 − ntr((Σ̂ − Σ0 )H/ mn )
E Θ0
pΘ0 (x)

n/2
√
n
X
det(Θ0 + H/ mn )n
det(Θ0 )
=
var(xTi Hxi )
−
1
+
det(Θ0 )n
det(Θ0 + 2H)
i=1

−2ntr[((Θ0 + H)−1 − Σ0 )H].

Proof of Lemma 18. The density is given by
det(Θ0 )n/2 − 1 Pni=1 xT Θ0 xi
i
e 2
(2π)np/2
√
For simplicity of notation, denote U := H/ mn . Then we have
pΘ0 (x1 , . . . , xn ) =

1

Pn

pΘ0 +U (x)
det(Θ0 + U )n/2 e− 2
−1 =
pΘ0 (x)
det(Θ0 )n/2

i=1

xT
i U xi

−1

The score function is given by sΘ0 (x) = n(Σ̂ − Σ0 )/2. Let
Z := vec(U )T vec(sΘ0 (x)) = tr(n(Σ̂ − Σ0 )U ) =

n
X
i=1

xTi U xi − ntr(Σ0 U ).

First observe that
n
n
X
X
T
var(xTi U xi ).
xi U xi ) =
EΘ0 Z = var(
2

i=1

i=1

We have
E Θ0



= E Θ0
=

pΘ0 +U (x)
−1−Z
pΘ0 (x)

2

1

Pn

det(Θ0 + U )n/2 e− 2
det(Θ0 )n/2

i=1

xT
i U xi

−1−Z

!2

P
det(Θ0 + U )n
T
− n
2
i=1 xi U xi + 1 + E
E
e
Θ
Θ0 Z +
0
n
det(Θ0 )

−2

P
T
det(Θ0 + U )n/2
− 12 n
i=1 xi U xi + 2E
E
e
Θ0 Z
Θ
0
n/2
det(Θ0 )

−2

P
det(Θ0 + U )n/2
T
− 12 n
i=1 xi U xi .
E
Ze
Θ
0
n/2
det(Θ0 )

36

J. JANKOVÁ AND S. VAN DE GEER

Using Lemma 17, since Θ0 + U/2 is a symmetric positive definite matrix, we
obtain
2

n/2

det(Θ0 + U )n
det(Θ0 )
pΘ0 +U (x)
=
+1
−1−Z
E Θ0
pΘ0 (x)
det(Θ0 )n
det(Θ0 + 2U )
n
X
varΘ0 (xTi U xi )
+
i=1

det(Θ0 + U )n/2
−2
det(Θ0 )n/2



det(Θ0 )
det(Θ0 + U )

n/2

P
det(Θ0 + U )n/2
T
− 12 n
i=1 xi U xi
E
Ze
Θ
0
n/2
det(Θ0 )

n/2
det(Θ0 + U )n
det(Θ0 )
=
−1
det(Θ0 )n
det(Θ0 + 2U )
n
X
varΘ0 (xTi U xi )
+

−2

i=1

−2
|

1 Pn
T
det(Θ0 + U )n/2
EΘ0 Ze− 2 i=1 xi U xi .
n/2
det(Θ0 )
{z
}

i

Next we calculate i. We have again by Lemma 17
tZ

E Θ0 e

−ntr(Σ0 U )t

=e

t

E Θ0 e

Pn

i=1

xT
i U xi

−ntr(Σ0 U )t

=e



det(Θ0 )
det(Θ0 − 2tU )

n/2

.

Since etZ ≤ eZ for t < 0 and EΘ0 eZ < ∞, we can interchange differentiation
and integration below to obtain
EΘ0 ZetZ = EΘ0 (etZ )′ = (EΘ0 etZ )′ .
Hence
EΘ0 ZetZ

= (EΘ0 etZ )′
−ntr(Σ0 U )t

det(Θ0 )
det(Θ0 − 2tU )

n/2

×


n tr((Θ0 − 2tU )−1 U ) − tr(Σ0 U )

= e
(41)



Finally, taking t = −1/2 in (41), we obtain

i = − 2ntr[((Θ0 + U )−1 − Σ0 )U ].

37

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

Hence
E Θ0



pΘ0 +U (x)
−1−Z
pΘ0 (x)

2

=


n/2
det(Θ0 + U )n
det(Θ0 )
−1
det(Θ0 )n
det(Θ0 + 2U )
n
X
varΘ0 (xTi U xi )
+
i=1

− 2ntr[((Θ0 + U )−1 − Σ0 )U ]

This finishes the proof.

Lemma 19.

Let 0 < δ = δn → 0 and let a, b = O(1). Then

n
aδ
1+ √ √
− 1 = O(δ).
√
n(b δ + n)

Proof of Lemma 19.


n

aδ
n log 1+ √ √δa √
n(b
δ+
n)
−1 = e
1+ √ √
−1
√
n(b δ + n)
n

= e
Next
√

h

√



aδ
√
√ +o
n(b δ+ n)

√

aδ
√
√
n(b δ+ n)

i

−1

anδ
√
√ = O(δ).
n(b δ + n)

Hence, and using that ex − 1 = o(x) for x → 0, we obtain
n

e

h

√



aδ
√
√ +o
n(b δ+ n)

aδ
√
√
√
n(b δ+ n)

i

− 1 = O(δ).

Lemma 20. Let pΘ0 be the joint density of the random sample X1 , . . . , Xn ,
T
where each Xi is an N (0, Θ−1
0 )-distributed random vector. Let H := Θ0 (ξ1 ξ2
T
+ξ2 ξ1 )Θ0 /σ. Then
E Θ0



pΘ0 +H/√mn (x)
√
− 1 − tr(sΘ0 (X)H)/ mn
pΘ0 (x)

2

= O(δn ).

38

J. JANKOVÁ AND S. VAN DE GEER

Proof of Lemma 20. We apply Lemma 18 with
H := Θ0 (ξ1 ξ2T + ξ2 ξ1T )Θ0 /σ,
where σ 2 := ξ1T Θ0 ξ1 ξ2T Θ0 ξ2 + (ξ1T Θ0 ξ2 )2 . To apply Lemma 18, we need
√
to show that Θ0 + H/ mn is a symmetric, positive definite matrix (for
n sufficiently large). This can be seen as follows. First note that H :=
Θ0 (ξ1 ξ2T + ξ2 ξ1T )Θ0 /σ is symmetric and Θ0 is symmetric and hence the symmetry of the sum follows. Next we look at positive definiteness.
For any u ∈ Rp we have by the Cauchy-Schwarz inequality

Thus

uT Hu = uT Θ0 (ξ1 ξ2T + ξ2 ξ1T )Θ0 u/σ
q
q
≤ 2 ξ1T Θ0 ξ1 uT Θ0 u ξ2T Θ0 ξ2 uT Θ0 u/σ ≤ Λmax (Θ)uT u.
√
√
uT Θ0 u + uT Hu/ mn ≥ uT Θ0 u − O(Λmax (Θ0 )uT u)/ mn
√
≥ [Λmin (Θ0 ) − O(1)/ mn ] uT u.

√
This shows that the matrix Θ0 +H/ mn is positive definite for n sufficiently
large. But then we can apply Lemma 18 which gives

2
√
pΘ0 +U (x)
− 1 − tr(sΘ0 (X)H)/ mn
E Θ0
pΘ0 (x)

n/2
det(Θ0 )
det(Θ0 + U )n
−1
=
det(Θ0 )n
det(Θ0 + 2U )
{z
}
|
i

+

n
X

|i=1

varΘ0 (xTi U xi )
{z

}

ii

− 2n tr[((Θ0 + U )−1 − Σ0 )U ] .
|
{z
}
iii

Now we calculate the terms i, ii, iii.
1.) Calculation of i.

First we calculate i. Observe that since H is of rank 2 it follows
√
√
i = det(Θ0 + H/ mn ) = det[Θ0 + Θ0 (ξ1 ξ2T + ξ2 ξ1T )Θ0 /(2σ mn )]
√
= (1 + ξ1T Θ0 ξ2 /(2σ mn ))2 det(Θ0 ).

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

39

And hence

n/2
√
det(Θ0 + H/ mn )n
det(Θ0 )
√
det(Θ0 )n
det(Θ0 + 2H/ mn )
n

√
(1 + ξ1T Θ0 ξ2 /(2σ mn ))2
=
√
(1 + ξ1T Θ0 ξ2 /(σ mn ))
2.) Calculation of ii.
The following property holds: if Y ∼ N2 (0, S), then it holds
2
var(Y1 Y2 ) = S11 S22 + S12
.

Further observe that since Θ0 xi ∼ N (0, Θ0 ) we obtain
√
varΘ0 (xTi Hxi / mn ) = varΘ0 (ξ1T Θ0 xi xTi Θ0 ξ2T )/(σ 2 mn )
= (ξ1T Θ0 ξ1 ξ2T Θ0 ξ2 + (ξ1T Θ0 ξ2 )2 )/(σ 2 mn ) = 1/mn .
Thus
ii = n/mn .
3.) Calculation of iii.
Finally, by inversion of a sum of a matrix with another matrix of rank 2, we
get (we omit the calculations)


√
√
1
−1
iii = tr[((Θ0 + H/ mn ) − Σ0 )H/ mn ] = O
.
mn
By Lemma 18 and the above calculations of i, ii, iii it then follows
2

pΘ0 +H/√mn (x)
√
E Θ0
− 1 − tr(sΘ0 (X)H)/ mn
pΘ0 (x)
n

(ξ1T Θ0 ξ2 )2 /(4σ 2 mn )
−1
= 1+
1 + 2ξ1T Θ0 ξ2 /(σmn )
|
{z
}
I


n
n
+
−O
.
mn
mn
For the first term, by Lemma 19 we have that I = O(δn ). Hence we conclude
that

2
pΘ0 +H/√mn (x)
√
− 1 − tr(sΘ0 (X)H)/ mn
E Θ0
pΘ0 (x)


n
= O(δn ).
= O(δn ) + O
mn

40

J. JANKOVÁ AND S. VAN DE GEER

APPENDIX C: ADDITIONAL PROOFS FOR SECTION 17
In this section, we give Lemmas 21, 23.
Lemma 21.

Let Z ∈ R2 be N (µ, Σ)-distributed, where




µ1
σ11 σ12
µ=
,Σ =
.
µ2
σ12 σ22

Suppose that µ2 = −σ22 /2. Let Y ∈ R2 be N (µ + a, Σ)-distributed, with


σ12
.
a=
σ22
Let φZ be the density of Z and φY be the density of Y. Then we have the
following equality for all z = (z1 , z2 ) ∈ R2 :
φZ (z)ez2 = φY (z).

Proof of Lemma 21. The density of Z is
φZ (z) =
It holds that

1
2π

p

det(Σ)

1

T Σ−1 (z−µ)

e− 2 (z−µ)

.

Σ−1 a = (0, 1)T .

Then
1
1
1
(z−µ)T Σ−1 (z−µ) = (z−µ−a)T Σ−1 (z−µ−a)+aT Σ−1 (z−µ)− aT Σ−1 a.
2
2
2
We also have
1
1
1
aT Σ−1 (z − µ) − aT Σ−1 a = (0, 1)T (z − µ) − (0, 1)T a = z2 − µ2 − σ22 = z2 .
2
2
2

Lemma 22.

Let µ and Σ be defined as follows
!
!
√v12
1
− √vv1211
v11
.
,
Σ=
µ=
√v12
v22
− v222
v11

Suppose that Vβ = O(1), 1/Vβ = O(1) and Λmax (Iβ ) = O(1). (The relationship between these quantities and the vij ’s is given in the proof of Theorem
9). Then
kµk22 = O(1) and Λmax (Σ) = O(1).

EFFICIENCY BOUNDS FOR HIGH-DIMENSIONAL MODELS

41

Proof. First observe that
2
v12
= (Eβ lβ hT sβ )2 ≤ Eβ lβ2 Eβ (hT sβ )2

= Vβ hEβ sβ sTβ h ≤ Vβ Λmax (Eβ sβ sTβ )hT h.

Then by assumption Λmax (Eβ sβ sTβ ) = O(1), Vβ = O(1) and since hT h =
O(1), we have that (Eβ lβ hT sβ )2 = O(1). Also observe that v22 = hT Iβ h ≤
Λmax (Iβ )hT h = O(1) by assumption Λmax (Iβ ) = O(1).
Then, and by 1/Vβ = O(1), it follows that
2
2
/v11 + v22
/4 = (Pβ lβ hT sβ )2 /Vβ + (hT Iβ h)2 /4 = O(1).
kµk22 = v12

We proceed to check that the eigenvalues of Σ are bounded. We have
√
1 + v22 ± D
λ1,2 =
,
2
2 /v ) = (1−v )2 +4v 2 /v . Clearly, D ≥ 0,
where D = (1+v22 )2 −4(v22 −v12
11
22
12 11
and as above, one sees that D = O(1). Hence also Λmax (Σ) = O(1).

Lemma 23.

Suppose that
− √vv1211
− v222

Un ∼ N

!

,

1
√v12
v11

√v12
v11

v22

!!

.

Suppose that Vβ = O(1), 1/Vβ = O(1), Λmax (Iβ ) = O(1) and h ∈ Θ. (The
relationship between these quantities and the vij ’s is given in the proof of
Theorem 9).
Then it holds that
lim lim E min(0, M − eUn,2 ) = 0.

M →∞ n→∞

Proof of Lemma 23. We have
Z ∞Z ∞
E min(0, M − eUn,2 ) =
min(0, M − ex2 )φUn (x)dx
−∞
Z−∞
∞ Z ∞
=
M − ex2 φUn (x)dx
−∞

log M

= M P (Un,2 > log M ) − P (Yn,2 > log K),

where we applied Lemma 21 and denoted


1
0
Y ∼N
,
v12
√
v22 /2
v11

√v12
v11

v22

!!

.

42

J. JANKOVÁ AND S. VAN DE GEER

Thus we have

2 /2

P (Yn,2 > log M ) ≤ e−(log M )

,

and
√
√
P (Un,2 > log M ) = P (Un,2 + v12 / v11 > log M + v12 / v11 )
√

≤ e−(log M +v12 /

v11 )2 /2

.

Now observe that
2
v12
= (Eβ lβ hT sβ )2 ≤ Eβ lβ2 Eβ (hT sβ )2

= Vβ hEβ sβ sTβ h ≤ Vβ Λmax (Eβ sβ sTβ )hT h.

Then by assumption Λmax (Eβ sβ sTβ ) = O(1), Vβ = O(1) and since hT h =
O(1), we have that (Elβ hT sβ )2 = O(1). Hence v12 = O(1). We also have by
√
the assumption 1/Vβ = O(1) that 1/ v11 = O(1). Hence we can conclude
√
that v12 / v11 ≤ L for some constant L > 0. Now without loss of generality,
√
choose M such that log M > 2L. Then we have log M +v12 / v11 ≥ log M/2.
Thus we obtain
E min(0, M − eUn,2 ) = M P (Un,2 > log M ) − P (Yn,2 > log K)
√

≤ M e−(log M +v12 /
2 /8

≤ M e−(log M )

v11 )2 /2

2 /2

+ e−(log M )
2 /2

+ e−(log M )

.

Finally, taking the limits we obtain
2 /2

lim lim E min(0, M −eUn,2 ) ≤ lim lim M e−(log M )

M →∞ n→∞

M →∞ n→∞

2 /8

+e−(log M )

= 0.

