arXiv:1512.07619v3 [stat.ME] 4 Sep 2017

UNIFORMLY VALID POST-REGULARIZATION
CONFIDENCE REGIONS FOR MANY FUNCTIONAL
PARAMETERS IN Z-ESTIMATION FRAMEWORK∗
By Alexandre Belloni† Victor Chernozhukov‡ ,
Denis Chetverikov§ and Ying Wei¶
Duke University† , MIT‡ , UCLA§ , and Columbia University¶
In this paper we develop procedures to construct simultaneous
confidence bands for p̃ potentially infinite-dimensional parameters
after model selection for general moment condition models where p̃
is potentially much larger than the sample size of available data, n.
This allows us to cover settings with functional response data where
each of the p̃ parameters is a function. The procedure is based on
the construction of score functions that satisfy certain orthogonality
condition. The proposed simultaneous confidence bands rely on uniform central limit theorems for high-dimensional vectors (and not on
Donsker arguments as we allow for p̃ ≫ n). To construct the bands,
we employ a multiplier bootstrap procedure which is computationally
efficient as it only involves resampling the estimated score functions
(and does not require resolving the high-dimensional optimization
problems). We formally apply the general theory to inference on regression coefficient process in the distribution regression model with a
logistic link, where two implementations are analyzed in detail. Simulations and an application to real data are provided to help illustrate
the applicability of the results.

1. Introduction. High-dimensional models have become increasingly
popular in the last two decades. Much research has been conducted on estimation of these models. However, inference about parameters in these models is much less understood, although the literature on inference is growing
quickly; see the list of references below. In particular, despite its practical
relevance, there is almost no research on the problem of construction of simultaneous confidence bands on many target parameters in these models
(with two exceptions being [9] and [42]). In this paper we provide a solution
to this problem by constructing simultaneous confidence bands for parameters in a very general framework of moment condition models, allowing for
many functional parameters, where each parameter itself can be an infinitedimensional object, and the number of parameters can be much larger than
∗

First ArXiv version: December 23, 2015. Revised version: September 6, 2017.
Keywords and phrases: inference after model selection, moment condition models with
a continuum of target parameters, Lasso and Post-Lasso with functional response data

1

2

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

the sample size of available data.
As a substantive application, we apply our general results to provide simultaneous confidence bands for parameters in a logistic regression model
with functional response data
(1.1)

EP [Yu | D, X] = Λ(D ′ θu + X ′ βu ), u ∈ U ,

where D = (D1 , . . . , Dp̃ )′ is a p̃-vector of covariates whose effects are of
interest, X = (X1 , . . . , Xp )′ is a p-vector of controls, Λ : R → R is the logistic link function, U = [0, 1] is a set of indices, and for each u ∈ U , Yu =
1{Y 6 (1 − u)y + uȳ} for some constants y 6 ȳ and the response variable Y ,
θu = (θu1 , . . . , θup̃ )′ is a vector of target parameters, and βu = (βu1 , . . . , βup )′
is a vector of nuisance parameters. Here, both p̃ and p are allowed to be
potentially much larger than the sample size n, and we have p̃ functional
target parameters (θuj )u∈U and p functional nuisance parameters (βuj )u∈U .
This example is important because it demonstrates that our methods can
be used for inference about the whole distribution of the response variable
Y given D and X in a high-dimensional setting, and not only about some
particular features of it such as mean or median. This model is called a distribution regression model in [20] and a conditional transformation model in
[23], who argue that the model provides a rich class of models for conditional
distributions, and offers a useful generalization of traditional proportional
hazard models as well as a useful alternative to quantile regression. We
develop inference methods to construct simultaneous confidence bands for
many functional parameters of this model in Section 3. To achieve that our
contributions include to effectively estimate a continuum of high-dimensional
nuisance parameters, allow for approximately sparse models, control sparse
eigenvalues of a continuum of random matrices, and establish the validity
of a multiplier bootstrap for the construction of confidence bands for the
many functional parameters of interest. In particular, these contributions
go much beyond [9] and [42], which consider the special case of many scalar
parameters.
Our general results refer to the problem of estimating the set of parameters (θuj )u∈U ,j∈[p̃] in the moment condition model,
(1.2)

EP [ψuj (W, θuj , ηuj )] = 0,

u ∈ U , j ∈ [p̃],

where W is a random element that takes values in a measurable space
(W, AW ) according to a probability measure P , U ⊂ Rdu and [p̃] := {1, . . . , p̃}
are sets of indices, and for each u ∈ U and j ∈ [p̃], ψuj is a known score
function, θuj is a scalar parameter of interest, and ηuj is a potentially highdimensional (or infinite-dimensional) nuisance parameter. Assuming that a

POST-REGULARIZATION CONFIDENCE REGIONS

3

random sample of size n, (Wi )ni=1 , from the distribution of W is available together with suitable estimators ηbuj of ηuj , we aim to construct simultaneous
confidence bands for (θuj )u∈U ,j∈[p̃] that are valid uniformly over a large class
of probability measures P , say Pn . Specifically, for each u ∈ U and j ∈ [p̃],
we construct an appropriate estimator θ̌uj of θuj along with an estimator of
√
buj , such that
the standard deviation of n(θ̌uj − θuj ), σ
(1.3)



cα σ
buj
cα σ
buj
PP θ̌uj − √ 6 θuj 6 θ̌uj + √ , ∀u ∈ U , j ∈ [p̃] → 1 − α,
n
n

uniformly over P ∈ Pn , where α ∈ (0, 1) and cα is an appropriate critical
value, which we choose to construct using a multiplier bootstrap method.
The left- and the right-hand sides of the inequalities inside the probability
statement (1.3) then can be used as bounds in simultaneous confidence bands
for θuj ’s. In this paper, we are particularly interested in the case when p̃ is
potentially much larger than n and U is an uncountable subset of Rdu , so
that for each j ∈ [p̃], (θuj )u∈U is an infinite-dimensional (that is, functional)
parameter.
In the presence of high-dimensional nuisance parameters, construction of
valid confidence bands is delicate. High-dimensionality requires relying upon
regularization that leads to lack of asymptotic linearization of the estimators
of target parameters since regularized estimators of nuisance parameters
suffer from a substantial bias and this bias spreads into the estimators of
the target parameters. This lack of asymptotic linearization in turn typically
translates into severe distortions in coverage probability of the confidence
bands constructed by traditional techniques that are based on perfect model
selection; see [27], [28], [29], [36]. To deal with this problem, we assume
that the score functions ψuj are constructed to satisfy a near-orthogonality
condition that makes them immune to first-order changes in the value of the
nuisance parameter, namely
 h
i
(1.4)
∂r EP ψuj (W, θuj , ηuj + rη̃})
≈ 0,
u ∈ U , j ∈ [p̃],
r=0

for all η̃ in an appropriate set where ∂r denotes the derivative with respect
to r. We shall often refer to this condition as Neyman orthogonality, since in
low-dimensional parametric settings the orthogonality property originates
in the work of Neyman on the C(α) test in the 50s. In Section 2 below,
we describe a few general methods for constructing the score functions ψuj
obeying the Neyman orthogonality condition.
The Neyman orthogonality condition (1.4) is important because it helps to
make sure that the bias from the estimators of the high-dimensional nuisance

4

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

parameters does not spread into the estimators of the target parameters. In
particular, under (1.4), it follows that
h
i
EP,W ψuj (W, θuj , ηbuj ) ≈ 0, u ∈ U , j ∈ [p̃],

at least up to the first order, where the index W in EP,W [·] means that the
expectation is taken over W only. This makes the estimators of the target
parameters θuj immune to the bias in the estimators ηbuj , which in turn
improves their statistical properties and opens up the possibilities for valid
inference.
As the framework (1.2) covers a broad variety of applications, it is instructive to revisit the logistic regression model with functional response
data (1.1). To construct score functions ψuj that satisfy both the moment
conditions (1.2) and the Neyman orthogonality condition (1.4) in this example, for u ∈ U and j ∈ [p̃], define a (p̃ + p − 1)-vector of additional nuisance
parameters
(1.5)

γuj = arg

min

γ∈Rp̃+p−1

EP [fu2 {Dj − X j γ}2 ],

where
(1.6)

fu2 = fu2 (D, X) = VarP (Yu | D, X).

Then, denoting W = (Y, D, X) and splitting θu into θuj and θu[p̃]\j =
(θu1 , . . . , θuj−1 , θuj+1 , . . . , θu[p̃] )′ , we set
o
n
ψuj (W, θuj , ηuj ) = Yu − Λ(Dj θuj + X j βuj ) (Dj − X j γuj ),
′
where X j = (D[p̃]\j
, X ′ ), D[p̃]\j = (D1 , . . . , Dj−1 , Dj+1 , . . . , Dp̃ )′ , ηuj =

′
(βuj , γuj ), and βuj = (θu[p̃]\j
, βu′ )′ . It is straightforward to see that these score
functions ψuj satisfy the moment conditions (1.2) and to see that they also
satisfy the Neyman orthogonality condition (1.4), observe that

n
o
∂β EP [ψuj (W, θuj , β, γuj )]
n
o
∂γ EP [ψuj (W, θuj , βuj , γ)]

j
β=βu

j
γ=γu

i
h
= −EP fu2 {Dj − X j γuj }(X j )′ = 0,
h
i
= −EP {Yu − Λ(D′ θu + X ′ βu )}(X j )′ = 0,

where the first line holds by definition of fu2 and γuj since VarP (Yu | D, X) =
Λ′ (D ′ θu + X ′ βu ), and the second by (1.1). Because of this orthogonality
condition, we can exploit the moment conditions (1.2) to construct reg√
ular, n-consistent, estimators of θuj even if non-regular, regularized or

POST-REGULARIZATION CONFIDENCE REGIONS

5

post-regularized, estimators of ηuj = (βuj , γuj ) are used to cope with highdimensionality. Using these regular estimators of θuj , we then can construct
valid confidence bands (1.3).
Our general approach to construct simultaneous confidence bands, which
is developed in Section 2, can be described as follows. First, we construct the
moment conditions (1.2) that satisfy the Neyman orthogonality condition
(1.4), and use these moment conditions to construct estimators θ̌uj of θuj for
all u ∈ U and j ∈ [p̃]. Second, under appropriate regularity conditions, we
establish a Bahadur representation for θ̌uj ’s. Third, employing the Bahadur
representation, we are able to derive a suitable Gaussian approximation for
the distribution of θ̌uj ’s. Importantly, the Gaussian approximation is possible
even if both p̃ and the dimension of the index set U , du , are allowed to grow
with n, and p̃ asymptotically remains much larger than n. Finally, from the
Gaussian approximation, we construct simultaneous confidence bands using
a multiplier bootstrap method. Here, the Gaussian and bootstrap approximations are constructed by applying the results on high-dimensional central
limit and bootstrap theorems established in [14], [16], [9], [18], and [10] by
verifying the conditions there.
Although regularity conditions underlying our approach can be verified
for many models defined by moment conditions, for illustration purposes, we
explicitly verify these conditions for the logistic regression model with functional response data (1.1) in Section 3. We also examine the performance
of the proposed procedures in a Monte Carlo simulation study and provide
an example based on real data in Section 5. In addition, in the Supplementary Material, we discuss the construction of simultaneous confidence bands
based on a double-selection estimator. This estimator does not require to
explicitly construct the score functions satisfying the Neyman orthogonality
condition but nonetheless is first-order equivalent to the estimator based on
such functions.
We also develop new results for ℓ1 -penalized M -estimators in Section 4
to handle functional data and criterion functions that depend on nuisance
functions for which only estimates are available (for brevity of the paper,
generic results are deferred to Appendix L of the Supplementary Material,
and Section 4 only contains results that are relevant for the logistic regression
model studied in Section 3). Specifically, we develop a method to select
penalty parameters for these estimators and extend the existing theory to
cover functional data to achieve rates of convergence and sparsity guarantees
that hold uniformly over u ∈ U . The ability to allow both for functional data
and for nuisance functions is crucial in the implementation and in theoretical
analysis of the methods proposed in this paper.

6

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Orthogonality conditions like that in (1.4) have played an important role
in statistics and econometrics. In low-dimensional settings, a similar condition was used by Neyman in [33] and [34] while in semiparametric models
the orthogonality conditions were used in [31], [1], [32], [37] and [30]. In
high-dimensional settings, [5] and [2] were the first to use the orthogonality condition (1.4) in a linear instrumental variables model with many instruments. Related ideas have also been used in the literature to construct
confidence bands in high-dimensional linear models, generalized linear models, and other non-linear models; see [6], [41], [7], [38], [12], [25], [24], [9],
[3], [5], [43], [35], [42]. We contribute to this quickly growing literature by
providing procedures to construct simultaneous confidence bands for many
infinite-dimensional parameters identified by moment conditions.
2. Confidence Regions for Function-Valued Parameters Based
on Moment Conditions.
2.1. Generic Construction of Confidence Regions. In this section, we
state our results under high-level conditions. In the next section, we will
apply these results to construct simultaneous confidence bands for many
infinite-dimensional parameters in the logistic regression model with functional response data.
Recall that we are interested in constructing simultaneous confidence
bands for a set of target parameters (θuj )u∈U ,j∈[p̃] where for each u ∈ U ⊂
Rdu and j ∈ [p̃] = {1, . . . , p̃}, the parameter θuj satisfies the moment
condition (1.2) with ηuj being a potentially high-dimensional (or infinitedimensional) nuisance parameter. Assume that θuj ∈ Θuj , a finite or infinite
interval in R, and that ηuj ∈ Tuj , a convex set in a normed space equipped
with a norm k · ke . We allow U to be a possibly uncountable set of indices,
and p̃ to be potentially large.
We assume that a random sample (Wi )ni=1 from the distribution of W
is available for constructing the confidence bands. We also assume that for
each u ∈ U and j ∈ [p̃], the nuisance parameter ηuj can be estimated by ηbuj
using the same data (Wi )ni=1 . In the next section, we discuss examples where
ηbuj ’s are based on Lasso or Post-Lasso methods (although other modern regularization and post-regularization methods can be applied). Our confidence
bands will be based on the estimators θ̌uj of θuj that are for each u ∈ U and
j ∈ [p̃] defined as approximate ǫn -solutions in Θuj to sample analogs of the
moment conditions (1.2), that is,


(2.1)
sup
En [ψuj (W, θ̌uj , ηbuj )] − inf En [ψuj (W, θ, ηbuj )] 6 ǫn ,
u∈U ,j∈[p̃]

θ∈Θuj

7

POST-REGULARIZATION CONFIDENCE REGIONS

where ǫn = o(δn n−1/2 ) for all n > 1 and some sequence (δn )n>1 of positive
constants converging to zero.
To motivate the construction of the confidence bands based on the estimators θ̌uj , we first study distributional properties of these estimators. To do
that, we will employ the following regularity conditions. Let C0 be a strictly
positive (and finite) constant, and for each u ∈ U and j ∈ [p̃], let Tuj be
some subset of Tuj , whose properties are specified below in assumptions. In
particular, we will choose the sets Tuj so that, on the one hand, their complexity does not grow too fast with n but, on the other hand, for each u ∈ U
and j ∈ [p̃], the estimator ηbuj takes values in Tuj with high probability. As
discussed before, we rely on the following near-orthogonality condition:

Definition 2.1 (Near-orthogonality condition). For each u ∈ U and
j ∈ [p̃], we say that ψuj obeys the near-orthogonality condition with respect
to Tuj ⊂ Tuj if the following conditions hold: The Gateaux derivative map
 h
i
Du,j,r̄ [η − ηuj ] := ∂r EP ψuj (W, θuj , ηuj + r(η − ηuj ))
r=r̄

exists for all r̄ ∈ [0, 1) and η ∈ Tuj and (nearly) vanishes at r̄ = 0, namely,
(2.2)

Du,j,0 [η − ηuj ] 6 C0 δn n−1/2 ,

for all η ∈ Tuj .



At the end of this section, we describe several methods to obtain score
functions ψuj that obey the near-orthogonality condition. Together these
methods cover a wide variety of applications.
Let ω and c0 be some strictly positive (and finite) constants, and let
n0 > 3 be some positive integer. Also, let (B1n )n>1 and (B2n )n>1 be some
sequences of positive constants, possibly growing to infinity, where B1n > 1
for all n > 1. In addition, denote
i
h
√
Sn := EP supu∈U ,j∈[p̃] nEn [ψuj (W, θuj , ηuj )] ,
n
o
(2.3)
Juj := ∂θ EP [ψuj (W, θ, ηuj )]
.
θ=θuj

The quantity Sn measures how rich the process {ψuj (·, θuj , ηuj ) : u ∈ U , j ∈
[p̃]} is. The quantity Juj measures the degree of identifiability of θuj by the
moment condition (1.2). In many applications, it is bounded in absolute
value from above and away from zero. Finally, let Pn be a set of probability
measures P of possible distributions of W on the measurable space (W, AW ).
We collect our main conditions on the score functions ψuj and the true
values of the target parameters θuj in the following assumption.

8

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Assumption 2.1 (Moment condition problem). For all n > n0 , P ∈ Pn ,
u ∈ U , and j ∈ [p̃], the following conditions hold: (i) The true parameter
value θuj obeys (1.2), and Θuj contains a ball of radius C0 n−1/2 Sn log n
centered at θuj . (ii) The map (θ, η) 7→ EP [ψuj (W, θ, η)] is twice continuously
Gateaux-differentiable on Θuj × Tuj . (iii) The score function ψuj obeys the
near-orthogonality condition given in Definition 2.1 for the set Tuj ⊂ Tuj .
(iv) For all θ ∈ Θuj , |EP [ψuj (W, θ, ηuj )]| > 2−1 |Juj (θ − θuj )| ∧ c0 , where Juj
satisfies c0 6 |Juj | 6 C0 . (v) For all r ∈ [0, 1), θ ∈ Θuj , and η ∈ Tuj ,
(a) EP [(ψuj (W, θ, η) − ψuj (W, θuj , ηuj ))2 ] 6 C0 (|θ − θuj | ∨ kη − ηuj ke )ω ,
(b) |∂r EP [ψuj (W, θ, ηuj + r(η − ηuj ))] | 6 B1n kη − ηuj ke ,
(c) |∂r2 EP [ψuj (W, θuj + r(θ − θuj ), ηuj + r(η − ηuj ))]| 6 B2n (|θ − θuj |2 ∨
kη − ηuj k2e ).

Assumption 2.1 is mild and standard in moment condition problems. Assumption 2.1(i) requires θuj to be sufficiently separated from the boundary of
Θuj . Assumption 2.1(ii) requires that the functions (θ, η) 7→ EP [ψuj (W, θ, η)]
are smooth. It is a mild condition because it does not require smoothness of
the functions (θ, η) 7→ ψuj (W, θ, η). Assumption 2.1(iii) is our key condition
and is discussed above. Assumption 2.1(iv) implies sufficient identifiability
of θuj . In particular, it implies that the equation EP [ψuj (W, θ, ηuj )] = 0
has only one solution θ = θuj . If this equation has multiple solutions, Assumption 2.1(iv) implies that the set Θuj is restricted enough so that there
is only one solution in Θuj . Assumption 2.1(v-a) means that the functions
(θ, η) 7→ ψuj (W, θ, η) mapping Θuj ×Tuj into L2 (P ) are Lipschitz-continuous
at (θ, η) = (θuj , ηuj ) with Lipschitz order ω/2. In most applications, we can
set ω = 2. Assumptions 2.1(v-b,v-c) impose smoothness bounds on the functions (θ, η) 7→ EP [ψuj (W, θ, η)].
Next, we state our conditions related to the estimators ηbuj . Let (∆n )n>1
and (τn )n>1 be some sequences of positive constants converging to zero. Also,
let (an )n>1 , (vn )n>1 , and (Kn )n>1 be some sequences of positive constants,
possibly growing to infinity, where an > n ∨ Kn and vn > 1 for all n > 1.
Finally, let q > 2 be some constant.
Assumption 2.2 (Estimation of nuisance parameters). For all n > n0
and P ∈ Pn , the following conditions hold: (i) With probability at least
1 − ∆n , we have ηbuj ∈ Tuj for all u ∈ U and j ∈ [p̃]. (ii) For all u ∈ U ,
j ∈ [p̃], and η ∈ Tuj , kη − ηuj ke 6 τn . (iii) For all u ∈ U and j ∈ [p̃], we
have ηuj ∈ Tuj . (iv) The function class F1 = {ψuj (·, θ, η) : u ∈ U , j ∈ [p̃], θ ∈
Θuj , η ∈ Tuj } is suitably measurable and its uniform entropy numbers obey
(2.4)

sup log N (ǫkF1 kQ,2 , F1 , k · kQ,2 ) 6 vn log(an /ǫ),
Q

for all 0 < ǫ 6 1

POST-REGULARIZATION CONFIDENCE REGIONS

9

where F1 is a measurable envelope for F1 that satisfies kF1 kP,q 6 Kn . (v) For
all f ∈ F1 , we have c0 6 kf kP,2 6 C0 . (vi) The complexity characteristics
an and vn satisfy
(a) (vn log an /n)1/2 6 C0 τn ,
√
(b) (B1n τn +Sn log n/ n)ω/2 (vn log an )1/2 +n−1/2+1/q vn Kn log an 6 C0 δn ,
2 B τ2 6 C δ .
(c) n1/2 B1n
0 n
2n n
Assumption 2.2 provides sufficient conditions for the estimation of the
nuisance parameters (ηuj )u∈U ,j∈[p̃] . Assumption 2.2(i) requires that the set
Tuj is large enough so that ηbuj ∈ Tuj with high probability. Assumptions
2.2(i,ii) together require that the estimator ηbuj converges to ηuj with the
rate τn . This rate should be fast enough so that Assumptions 2.2(vi-b,vi-c)
are satisfied. Assumption 2.2(iv) gives a bound on the complexity of the
set Tuj expressed via uniform entropy numbers, and Assumptions 2.2(via,vi-b) require that the set Tuj is small enough so that its complexity does
not grow too fast. Assumption 2.2(v) requires that the functions (θ, η) 7→
ψuj (W, θ, η) are scaled properly. Suitable measurability of F1 , required in
Assumption 2.2(iv), is a mild condition that is satisfied in most practical
cases; see Appendix A for clarifications. Overall, Assumption 2.2 shows the
trade-off in the choice of the sets Tuj : setting Tuj large, on the one hand,
makes it easy to satisfy Assumption 2.2(i) but, on the other hand, yields
large values of an and vn in Assumption 2.2(iv) making it difficult to satisfy
Assumption 2.2(vi).
We stress that the class F1 does not need to be Donsker because its uniform entropy numbers are allowed to increase with n. This is important
because allowing for non-Donsker classes is necessary to deal with highdimensional nuisance parameters. Note also that our conditions are very
different from the conditions imposed in various settings with nonparametrically estimated nuisance functions; see, e.g., [15], [39], and [26].
In addition, we emphasize that the conditions stated in Assumption 2.2
are sufficient for our results for the general model (1.2) but can often be
relaxed if the structure of the functions ψuj (W, θ, η) is known. For example,
it is possible to relax Assumption 2.2(vi) if the functions ψuj (W, θ, η) are
linear in θ, which happens in the linear regression model with θ being the
coefficient on the covariate of interest; see [7]. Moreover, it is possible to
relax the entropy condition (2.4) of Assumption 2.2 by relying upon sample
splitting, where a part of the data is used to estimate ηuj , and the other
part is used to estimate θuj given an estimate ηbuj of ηuj ; see [2].
The following theorem is our first main result in this paper:

10

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Theorem 2.1 (Uniform Bahadur representation). Under Assumptions
2.1 and 2.2, for an estimator (θ̌uj )u∈U ,j∈[p̃] that obeys (2.1), we have
√

(2.5)

−1
(θ̌uj − θuj ) = Gn ψ̄uj + OP (δn ) in ℓ∞ (U × [p̃])
nσuj

−1 −1
2 :=
uniformly over P ∈ Pn , where ψ̄uj (·) := −σuj
Juj ψuj (·, θuj , ηuj ) and σuj
−2
2 (W, θ , η )].
Juj
EP [ψuj
uj uj

Comment 2.1 (On the proof of Theorem 2.1).
we use the following identity:
(2.6)
(2.7)

√

To prove this theorem,

√
nEP,W [ψuj (W, θ̌uj , ηbuj ) − ψuj (W, θuj , ηuj )] = − nEn [ψuj (W, θuj , ηuj )]
√
+ nEn [ψuj (W, θ̌uj , ηbuj )] + Gn ψuj (W, θuj , ηuj ) − Gn ψuj (W, θ̌uj , ηbuj ).

Here, the term on the right-hand side of (2.6) is the main term on the righthand side of (2.5), up to a normalization (σuj Juj )−1 . Also, we show that the
first term in (2.7) is OP (δn ) since θ̌uj satisfies (2.1). Moreover, using a rather
standard theory of Z-estimators, we show that θ̌uj − θuj = OP (B1n τn ). This
in turn allows us to conclude with the help of empirical process arguments
that the difference of the last two terms in (2.7) is OP (δn ) as well. Thus,
it remains to show that the left-hand side of (2.6) is equal to the left-hand
side of (2.5) up to an approximation error OP (δn ) and up to a normalization
(σuj Juj )−1 . To do so, we use second-order Taylor’s expansion of the function
√
f (r) = nEP,W [ψuj (W, θuj + r(θ̌uj − θuj ), ηuj + r(b
ηuj − ηuj ))]
at r = 1 around r = 0. This gives
√
nEP,W [ψuj (W, θ̌uj , ηbuj ) − ψuj (W, θuj , ηuj )] = f (1) − f (0)
√
√
√
= nJuj (θ̌uj − θuj ) + nDu,j,0 [b
ηuj − ηuj ] + nf ′′ (r̄)/2

√
for some r̄ ∈ (0, 1). Here, nf ′′ (r̄) = OP (δn ) follows from Assumptions
2.1 and 2.2 and the key near-orthogonality condition also allows us to
√
ηuj − ηuj ] = OP (δn ). Without this condition, the term
show that nDu,j,0 [b
√
√
nDu,j,0 [b
ηuj − ηuj ] would give first-order bias and lead to slower-than- n
rate of convergence of the estimator θ̌uj . Finally, again using the empirical process arguments, we can show that all the bounds including the term
OP (δn ) hold uniformly over u ∈ U and j ∈ [p̃].

The uniform Bahadur representation derived in Theorem 2.1 is useful for
the construction of simultaneous confidence bands for (θuj )u∈U ,j∈[p̃] as in
(1.3). For this purpose, we apply new high-dimensional central limit and

11

POST-REGULARIZATION CONFIDENCE REGIONS

bootstrap theorems that have been recently developed in a sequence of papers [14], [16], [9], [18], and [10]. To apply these theorems, we make use of
the following regularity condition.
Let (δ̄n )n>1 be a sequence of positive constants converging to zero. Also,
let (̺n )n>1 , (¯
̺n )n>1 , (An )n>1 , (Ān )n>1 , and (Ln )n>1 be some sequences of
positive constants, possibly growing to infinity, where ̺n > 1, An > n, and
Ān > n for all n > 1. In addition, from now on, we assume that q > 4.
−1 b−1
Denote by ψbuj (·) := −b
σuj
Juj ψuj (·, θ̌uj , ηbuj ) an estimator of ψ̄uj (·), with
Jbuj and σ
buj being suitable estimators of Juj and σuj .

Assumption 2.3 (Additional score regularity). For all n > n0 and P ∈
Pn , the following conditions hold: (i) The function class F0 = {ψ̄uj (·) : u ∈
U , j ∈ [p̃]} is suitably measurable and its uniform entropy numbers obey
sup log N (ǫkF0 kQ,2 , F0 , k · kQ,2 ) 6 ̺n log(An /ǫ),

for all 0 < ǫ 6 1,

Q

where F0 is a measurable envelope for F0 that satisfies kF0 kP,q 6 Ln . (ii) For
all f ∈ F0 and k = 3, 4, we have EP [|f (W )|k ] 6 C0 Lnk−2 . (iii) The function
class Fb0 = {ψ̄uj (·) − ψbuj (·) : u ∈ U , j ∈ [p̃]} satisfies with probability 1 − ∆n :
log N (ǫ, Fb0 , k · kPn ,2 ) 6 ̺¯n log(Ān /ǫ) for all 0 < ǫ 6 1 and kf kPn ,2 6 δ̄n for
all f ∈ Fb0 .

This assumption is technical, and its verification in applications is rather
standard. For the Gaussian approximation result below, we actually only
need the first and the second part of this assumption. The third part will be
needed for establishing validity of the simultaneous confidence bands based
on the multiplier bootstrap procedure.
Next, let (Nuj )u∈U ,j∈[p̃] denote a tight zero-mean Gaussian process indexed by U × [p̃] with covariance operator given by EP [ψ̄uj (W )ψ̄u′ j ′ (W )] for
u, u′ ∈ U and j, j ′ ∈ [p̃]. We have the following corollary of Theorem 2.1,
which is our second main result in this paper.
Corollary 2.1 (Gaussian approximation). Suppose that Assumptions
2.1, 2.2, and 2.3(i,ii) hold. In addition, suppose that the following growth
2/7
conditions are satisfied: δn2 ̺n log An = o(1), Ln ̺n log An = o(n1/7 ), and
2/3
Ln ̺n log An = o(n1/3−2/(3q) ). Then
sup PP
t∈R

sup
u∈U ,j∈[p̃]

√ −1
(θ̌uj − θuj )| 6 t
| nσuj

uniformly over P ∈ Pn .

!

− PP

sup
u∈U ,j∈[p̃]

|Nuj | 6 t

!

= o(1)

12

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Based on Corollary 2.1, we are now able to construct simultaneous confidence bands for θuj ’s as in (1.3). In particular, we will use the Gaussian
multiplier bootstrap method employing the estimates ψbuj of ψ̄uj . To describe
the method, define the process
!
n
X
1
(2.8)
Gb = (Gbuj )u∈U ,j∈[p̃] = √
ξi ψbuj (Wi )
n
i=1

u∈U ,j∈[p̃]

where (ξi )ni=1 are independent standard normal random variables which are
independent from the data (Wi )ni=1 . Then the multiplier bootstrap critical
value cα is defined as the (1 − α) quantile of the conditional distribution
of supu∈U ,j∈[p̃] |Gbuj | given the data (Wi )ni=1 . To prove validity of this critical
value for the construction of simultaneous confidence bands of the form
(1.3), we will impose the following additional assumption. Let (εn )n>1 be a
sequence of positive constants converging to zero.
Assumption 2.4 (Variation estimation).
PP

sup
u∈U ,j∈[p̃]

For all n > n0 and P ∈ Pn ,
!

σ
buj
− 1 > εn
σuj

6 ∆n .

The following corollary establishing validity of the multiplier bootstrap
critical value cα for the simultaneous confidence bands construction is our
third main result in this paper.
Corollary 2.2 (Simultaneous confidence bands). Suppose that Assumptions 2.1 – 2.4 hold. In addition, suppose that the growth conditions of Corollary 2.1 hold. Finally, suppose that εn ̺n log An = o(1), and δ̄n2 ̺¯n ̺n (log Ān ) ·
(log An ) = o(1). Then (1.3) holds uniformly over P ∈ Pn .
2.2. Construction of score functions satisfying the orthogonality condition. Here we discuss several methods for generating orthogonal scores in
a wide variety of settings, including the classical Neyman’s construction. In
what follows, since the argument applies to each u and j, it is convenient to
omit the indices u and j and also to use the subscript 0 to indicate the true
values of the parameters. For simplicity we also focus the discussion on the
exactly orthogonal case. With these simplifications, we can restate the orthogonality condition as follows: we say that the score ψ obeys the Neyman
orthogonality condition with respect to η0 ∈ T if the following conditions
hold: The Gateaux derivative map
 h
i
Dr̄ [η − η0 ] := ∂r EP ψ(W, θ0 , η0 + r(η − η0 )
r=r̄

13

POST-REGULARIZATION CONFIDENCE REGIONS

exists for all r̄ ∈ [0, 1) and η ∈ T and vanishes at r̄ = 0, namely,
Du,j,0 [η − η0 ] = 0,

(2.9)
for all η ∈ T .

1) Orthogonal Scores for Likelihood Problems with Finite-Dimensional
Nuisance Parameters. In likelihood settings with finite-dimensional parameters, the construction of orthogonal equations was proposed by Neyman [33]
who used them in construction of his celebrated C(α)-statistic.1
To describe the construction, suppose that the log-likelihood function
associated to observation W is (θ, β) 7→ ℓ(W, θ, β), where θ ∈ Θ ⊂ Rd is
the target parameter and β ∈ T ⊂ Rp0 is the nuisance parameter. Under
regularity conditions, the true parameter values θ0 and β0 obey
(2.10)

E[∂θ ℓ(W, θ0 , β0 )] = 0,

E[∂β ℓ(W, θ0 , β0 )] = 0.

Now consider the new score function
ψ(W, θ, η) = ∂θ ℓ(W, θ, β) − µ∂β ℓ(W, θ, β),

(2.11)

where the nuisance parameter is
η = (β ′ , vec(µ)′ )′ ∈ T × D ⊂ Rp ,

p = p0 + dp0 ,

µ is the d×p0 orthogonalization parameter matrix whose true value µ0 solves
the equation
−1
Jθβ − µJββ = 0 (i.e., µ0 = Jθβ Jββ
),
and
J=



Jθθ Jθβ
Jβθ Jββ



h
i
= ∂(θ′ ,β ′ ) E ∂(θ′ ,β ′ )′ ℓ(W, θ, β)

θ=θ0 ; β=β0

.

Provided that µ0 is well-defined, we have by (2.10) that
E[ψ(W, θ0 , η0 )] = 0,
1
Note that the C(α)-statistic, or the orthogonal score statistic, had been explicitly used
for testing (and also for setting up estimation) in high-dimensional sparse models in [9] and
in [35], where it is referred to as the decorrelated score statistic. The discussion of Neyman’s
construction here draws on [21]. Note also that our results cover other types of orthogonal
score statistics as well, which allows us to cover much broader classes of models; see for
example the discussion of conditional moment models with infinite-dimensional nuisance
parameters below.

14

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

where η0 = (β0′ , vec(µ0 )′ )′ . Moreover, it is trivial to verify that under standard regularity conditions the score function ψ obeys the near orthogonality
condition (2.2) exactly (i.e., with C0 = 0), i.e.
∂η E[ψ(W, θ0 , η)]

η=η0

= 0.

Note that in this example, µ0 not only creates the necessary orthogonality
but also creates the efficient score for inference on the main parameter θ,
as emphasized by Neyman.
2) Orthogonal Scores for Likelihood Problems with Infinite-Dimensional
Nuisance Parameters. The Neyman’s construction can be extended to semiparametric models, where the nuisance parameter β is a function. In this
case, the original score functions (θ, β) 7→ ∂θ ℓ(W, θ, β) corresponding to the
log-likelihood function (θ, β) 7→ ℓ(W, θ, β) associated to observation W can
be transformed into efficient score functions ψ that obey the exact orthogonality condition (2.9) by projecting the original score functions onto the
orthocomplement of the tangent space induced by the nuisance parameter
β; see Chapter 25 of [39] for a detailed description of this construction. Note
that the projection may create additional nuisance parameters, so that the
new nuisance parameter η could be of larger dimension than β. Other relevant references include [15], [26], [7], and [9]. The approach is related to
Neyman’s construction in the sense that the score ψ arising in this model
is actually the Neyman’s score arising in a one-dimensional least favorable
parametric subfamily; see Chapter 25 of [39] for details.
3) Orthogonal Scores for Conditional Moment Problems with InfiniteDimensional Nuisance Parameters. Next, consider a conditional moment
restrictions framework studied by Chamberlain [13]. To define the framework, let W , X, and Z be random vectors in Rdw , Rdx , and Rdz , respectively, with Z being a sub-vector of X and X being a sub-vector of W , so
that dz 6 dx 6 dw . Also, let θ ∈ Θ ⊂ Rdθ be a finite-dimensional parameter
whose true value θ0 is of interest, and let h : Rdz → Rdh be a vector-valued
functional nuisance parameter, with the true value being h0 : Rdz → Rdh .
The conditional moment restrictions framework assumes that θ0 and h0 satisfy the following equation:
(2.12)

E[m(W, θ0 , h0 (Z)) | X] = 0,

where m : Rdw × Rdθ × Rdh → Rdm is some known function. This framework
is of interest because it covers an extremely rich variety of models, without

15

POST-REGULARIZATION CONFIDENCE REGIONS

having to explicitly rely on the likelihood formulation. For example, it covers
the partial linear model,
(2.13)

Y = Dθ0 + h0 (V ) + U,

E[U | D, V ] = 0,

where Y is a scalar dependent random variable, D is a scalar independent
treatment random variable, V is a vector of control random variables, and
U is a scalar unobservable noise random variable. Indeed, (2.13) implies
(2.12) by setting W = (Y, D, V ′ )′ , X = (D, V ′ )′ , V = Z, and m(W, θ, h) =
Y − Dθ − h.
Here we would like to build a (generalized) score function (θ, η) 7→ ψ(W, θ, η)
for estimating θ0 , the true value of parameter θ, where η is a new nuisance
parameter with true value η0 , that obeys the near orthogonality condition
(2.2). There are many ways to do so but one particularly useful way is the
following. Consider the functional parameters Σ : Rdx → Rdm × Rdm and
ϕ : Rdx → Rdθ × Rdm whose true values are given by
Σ0 (X) = E[m(W, θ0 , h0 (Z))m(W, θ0 , h0 (Z))′ | X]

and
where


′
ϕ0 (X) = A0 (X) − Γ0 (X)G0 (Z)

A0 (X) = ∂θ′ E[m(W, θ, h0 (Z)) | X]

θ=θ0

,

Γ0 (X) = ∂h′ E[m(W, θ0 , h) | X]

h=h0 (Z)

,


−1
G0 (Z) = E[Γ0 (X)′ Σ0 (X)−1 Γ0 (X) | Z]
× E[Γ0 (X)′ Σ0 (X)−1 A0 (X) | Z].

Then set

η = (h, ϕ, Σ)

and η0 = (h0 , ϕ0 , Σ0 ),

and define the score function
ψ(W, θ, η) =

ϕ(X)
“instrument”

Σ(X)−1 m(Z, θ, h(X)) .
weight

residual

It is rather straightforward to verify that under mild regularity conditions,
the score function ψ satisfies the moment condition,
E[ψ(W, θ0 , η0 )] = 0,
and in addition, the orthogonality condition,
∂η E[ψ(W, θ0 , η)]

η=η0

= 0.

Note that this construction gives the efficient score function ψ that yields an
estimator of θ0 achieving the semi-parametric efficiency bound, as calculated
by Chamberlain [13].

16

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

3. Application to Logistic Regression Model with Functional
Response Data. In this section we apply our main results to a logistic
regression model with functional response data described in the Introduction.
3.1. Model. We consider a response variable Y ∈ R that induces a functional response (Yu )u∈U by Yu = 1{Y 6 (1 − u)y + uȳ} for a set of indices
U = [0, 1] and some constants y 6 ȳ. We are interested in the dependence of
this functional response on a p̃-vector of covariates, D = (D1 , . . . , Dp̃ )′ ∈ Rp̃ ,
controlling for a p-vector of additional covariates X = (X1 , . . . , Xp )′ ∈ Rp .
We allow both p̃ and p to be (much) larger than the sample size of available
data, n.
For each u ∈ U , we assume that Yu satisfies the generalized linear model
with the logistic link function
(3.1)

EP [Yu | D, X] = Λ(D ′ θu + X ′ βu ) + ru ,

where θu = (θu1 , . . . , θup̃ )′ is a vector of parameters that are of interest,
βu = (βu1 , . . . , βup )′ is a vector of nuisance parameters, ru = ru (D, X) is an
approximation error, Λ : R → R is the logistic link function defined by
Λ(t) =

exp(t)
,
1 + exp(t)

t ∈ R,

and P ∈ Pn is the distribution of the triple W = (Y, D, X). As in the previous section, we construct simultaneous confidence bands for the parameters
(θuj )u∈U ,j∈[p̃] based on a random sample (Wi )ni=1 = (Yi , Di , Xi )ni=1 from the
distribution of W = (Y, D, X).
3.2. Orthogonal Score Functions. Before setting up score functions that
satisfy both the moment conditions (1.2) and the orthogonality condition
(1.4), observe that “naive” score functions that follow directly from the
model (3.1),
o
n


′
muj (W, θuj , θu[p̃]\j , βu , ru ) = Yu − Λ Dj θ + X j (θu[p̃]\j
, βu′ )′ − ru Dj ,

′
where X j = (D[p̃]\j
, X ′ ), satisfy the moment conditions EP [muj (W, θuj )] = 0
but violate the orthogonality condition (1.4) (with muj replacing ψuj and
ηuj = (θu[p̃]\j , βu , ru )). To satisfy the orthogonality condition (1.4), we proceed using an approach from Section 2.2 as in the Introduction. Specifically,
for each u ∈ U and j ∈ [p̃], define the (p̃+p−1)-vector of additional nuisance

POST-REGULARIZATION CONFIDENCE REGIONS

17

parameters γuj by (1.5) where fu2 = fu2 (D, X) is defined in (1.6). Thus, by
the first order condition of (1.5), the nuisance parameters γuj satisfy
(3.2)

fu Dj = fu X j γuj + vuj ,

EP [fu X j vuj ] = 0.

′
Also, denote βuj = (θu[p̃]\j
, βu′ )′ . Then we set
o

n

ψuj (W, θuj , ηuj ) = Yu − Λ Dj θuj + X j βuj − ru (Dj − X j γuj ),

where the nuisance parameter is ηuj = (ru , βuj , γuj ). As we formally demonstrate in the proof of Theorem 3.1 below, this function satisfies the nearorthogonality condition (1.4).
3.3. Estimation Using Orthogonal Score Functions. Next, we discuss estimation of ηuj ’s and θuj ’s. First, we assume that the approximation error ru = ru (D, X) is asymptotically negligible, so that it can be estimated
by O = O(D, X), the identically zero function of D and X. Second, for
γuj , we consider an estimator γ
euj defined as a post-regularization weighted
least squares estimator corresponding to the problem (1.5). Third, for βuj ,
′
we consider a plug-in estimator βbuj = (θeu[p̃]\j
, βeu′ )′ , where θeu and βeu are
suitable estimators of θu and βu . In particular, we assume that θeu and βeu

are post-regularization maximum likelihood estimators corresponding to the
log-likelihood function (θ, β) 7→ −Mu (W, θ, β) where

Mu (W, θ, β) = − 1{Yu = 1} log Λ(D ′ θ + X ′ β)

(3.3)
+ 1{Yu = 0} log(1 − Λ(D ′ θ + X ′ β)) .

The details of the estimators θeu , βeu , and γ
euj are given in Algorithm 1 below.
The results in this paper can also be easily extended to the case where θeu ,
βeu , and γ
euj are replaced by penalized maximum likelihood estimators θbu and
βbu and penalized weighted least squares estimator b
γuj , respectively.
j
j
Then our estimator of ηuj is ηbuj = (O, βbu , γ
eu ). Substituting this estimator
into the score function ψuj gives
o
n

euj ),
(3.4)
ψuj (W, θuj , ηbuj ) = Yu − Λ Dj θuj + X j βbuj (Dj − X j γ

which, using the sample analog (2.1) of the moment conditions (1.2), gives
the following estimator of θuj :
h
i
(3.5)
θ̌uj ∈ arg inf En ψuj (W, θ, ηbuj ) .
θ∈Θuj

The algorithm is summarized as follows.

18

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Algorithm 1. For each u ∈ U and j ∈ [p̃]:
Step 1. Run post-ℓ1 -penalized logistic estimator (4.2) of Yu on D and X to
compute (θeu , βeu ).
Step 2. Define the weights fbu2 = fbu2 (D, X) = Λ′ (D ′ θeu + X ′ βeu ).
Step 3. Run the post-lasso estimator (4.5) of fbu Dj on fbu X j to compute γ
euj .
Step 4. Compute βbuj = (θe′
, βe′ )′ .
u[p̃]\j

u

Step 5. Solve (3.5) with ψuj (W, θ, ηbuj ) defined in (3.4) to compute θ̌uj .

3.4. Regularity Conditions. Next, we specify our regularity conditions.
For all u ∈ U and j ∈ [p̃], denote Zuj = Dj −X j γuj . Also, denote an = p∨ p̃∨n.
Let q, c1 , and C1 be some strictly positive (and finite) constants where
¯ n )n>1 be some sequences of positive
q > 4. Moreover, let (δn )n>1 and (∆
constants converging to zero. Finally, let (Mn,1 )n>1 and (Mn,2 )n>1 be some
sequences of positive constants, possibly growing to infinity, where Mn,1 > 1
and Mn,2 > 1 for all n.
Assumption 3.1 (Parameters). For all u ∈ U , we have kθu k + kβu k +
maxj∈[p̃] kγuj k 6 C1 and maxj∈[p̃] supθ∈Θuj |θ| 6 C1 . In addition, for all
u1 , u2 ∈ U , we have (kθu2 − θu1 k+ kβu2 − βu1 k) 6 C1 |u2 − u1 |. Finally, for all
u ∈ U and j ∈ [p̃], Θuj contains a ball of radius (log log n)(log an )3/2 /n1/2
centered at θuj .
Assumption 3.2 (Sparsity). There exist s = sn and γ̄uj , u ∈ U and
j ∈ [p̃], such that for all u ∈ U , kβu k0 + kθu k0 + maxj∈[p̃] kγ̄uj k0 6 sn and
−1/2

maxj∈[p̃] (kγ̄uj − γuj k + sn

kγ̄uj − γuj k1 ) 6 C1 (sn log an /n)1/2 .

Assumption 3.3 (Distribution of Y ).
(D, X) is bounded by C1 .

The conditional pdf of Y given

Assumptions 3.1-3.3 are mild and standard in the literature. In particular,
Assumption 3.1 requires the parameter spaces Θuj to be bounded, and also
requires that for each u ∈ U and j ∈ [p̃], the parameter θuj to be sufficiently
separated from the boundaries of the parameter space Θuj . Assumption 3.2
requires approximate sparsity of the model (3.1). Note that in Assumption
3.2, given that γ̄uj ’s exist, we can and will assume without loss of generality
j
for some T ⊂ {1, . . . , p + p̃ − 1} with |T | 6 sn , where T = Tuj
that γ̄uj = γuT
j
is allowed to depend on u and j. Here the (p + p̃ − 1)-vector γuT
is defined
j
j
from γu by keeping all components of γu that are in T and setting all other
components to be zero. Assumption 3.3 can be relaxed at the expense of
more technicalities.

POST-REGULARIZATION CONFIDENCE REGIONS

19

Assumption 3.4 (Covariates). For all u ∈ U , the following inequalities hold: (i) inf kξk=1 EP [fu2 {(D ′ , X ′ )ξ}2 ] > c1 , (ii) minj,k (EP [|fu2 Zuj Xkj |2 ] ∧
EP [|fu2 Dj Xkj |2 ]) > c1 , and (iii) maxj,k EP [|Zuj Xkj |3 ]1/3 log1/2 an 6 δn n1/6 .
In addition, we have that (iv) supkξk=1 EP [{(D ′ , X ′ )ξ}4 ] 6 C1 , (v) Mn,1 >
2 s log a 6 δ n1/2−1/q , (vii) M
EP [supu∈U ,j∈[p̃] |Zuj |2q ]1/(2q) , (vi) Mn,1
n
n
n
n,2 >
1/2
1/2−1/q
2q
1/(2q)
2
, and (ix)
{EP [(kDk∞ ∨kXk∞ ) ]}
, (viii) Mn,2 sn log an 6 δn n
1−3/q
4
2
.
Mn,1 Mn,2 sn 6 δn n
This assumption requires that there is no multicollinearity between covariates in vectors D and X. In addition, it requires that the constants y
and ȳ are chosen so that the probabilities of Y < ȳ and Y > y are both
non-vanishing since otherwise we would have E[fu2 ] = E[VarP (Yu | D, X)]
vanishing either for u = 0 or u = 1 violating Assumption 3.4(i). Intuitively,
sending y and ȳ to the left and to the right tails of the distribution of Y ,
2
respectively, would blow up the variance of the estimators θ̌uj , given by σuj
in Theorem 2.1, and leading eventually to the estimators with slower-than√
n rate of convergence. Although our results could be extended to allow
for the case where y and ȳ are sent to the tails of the distribution of Y
slowly, we skip this extension for the sake of clarity. Moreover, Assumption
3.4 imposes constraints on various moments of covariates. Since these constraints might be difficult to grasp, at the end of this section, in Corollary
3.3, we provide an example for which these constraints simplify into easily
interpretable conditions.
Assumption 3.5 (Approximation error). For all u ∈ U , we have (i)
supkξk=1 EP [ru2 {(D ′ , X ′ )ξ}2 ] 6 C1 EP [ru2 ], (ii) EP [ru2 ] 6 C1 sn log an /n, (iii)
maxj∈[p̃] |EP [ru Zuj ]| 6 δn n−1/2 , and (iv) |ru (D, X)| 6 fu2 (D, X)/4 almost
¯ n , (v) supu∈U ,j∈[p̃] (En [(ru Zuj /fu )2 ]+
surely. In addition, with probability 1− ∆
En [ru2 /fu6 ]) 6 C1 sn log an /n.
This assumption requires the approximation error ru = ru (D, X) to be
sufficiently small. Under Assumption 3.4, the first condition of Assumption
3.5 holds if the approximation error is such that ru2 6 CEP [ru2 ] almost surely
for some constant C.
3.5. Formal Results. Under specified assumptions, our estimators θ̌uj
satisfy the following uniform Bahadur representation theorem.
Theorem 3.1 (Uniform Bahadur representation for logistic model). Suppose that Assumptions 3.1 – 3.5 hold for all P ∈ Pn . In addition, suppose

20

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

that the following growth condition holds: δn2 log an = o(1). Then for the
estimators θ̌uj satisfying (3.5), we have
√ −1
nσuj (θ̌uj − θuj ) = Gn ψ̄uj + OP (δn ) in ℓ∞ (U × [p̃]),
−1 −1
2 :=
uniformly over P ∈ Pn , where ψ̄uj (W ) := −σuj
Juj ψuj (W, θuj , ηuj ), σuj
−2 2
EP [Juj
ψuj (W, θuj , ηuj )], and Juj is defined in (2.3).

This theorem allows us to establish a Gaussian approximation result for
√ −1
the supremum of the process { nσuj
(θ̌uj − θuj ) : u ∈ U , j ∈ [p̃]}:
Corollary 3.1 (Gaussian approximation for logistic model). Suppose
that Assumptions 3.1 – 3.5 hold for all P ∈ Pn . In addition, suppose that
2/7
the following growth conditions hold: δn2 log an = o(1), Mn,1 log an = o(n1/7 ),
2/3

and Mn,1 log an = o(n1/3−2/(3q) ). Then
sup PP
t∈R

sup
u∈U ,j∈[p̃]

√ −1
(θ̌uj − θuj )| 6 t
| nσuj

!

− PP

sup
u∈U ,j∈[p̃]

|Nuj | 6 t

!

= o(1)

uniformly over P ∈ Pn , where (Nuj )u∈U ,j∈[p̃] is a tight zero-mean Gaussian
process indexed by U × [p̃] with the covariance given by EP [ψ̄uj (W )ψ̄u′ j ′ (W )]
for u, u′ ∈ U and j, j ′ ∈ [p̃].
Based on this corollary, we are now able to construct simultaneous confidence bands for the parameters θuj . Observe that
i

h 
Juj = −EP Λ′ Dj θuj + X j βuj Dj (Dj − X j γuj ) , u ∈ U , j ∈ [p̃],

and so it can be estimated by

i
h 
γuj ) ,
Jbuj = −En Λ′ Dj θeuj + X j βbuj Dj (Dj − X j e

u ∈ U , j ∈ [p̃],

2 = E [J −2 ψ 2 (W, θ , η )], and so it can be estimated by
In addition, σuj
uj uj
P uj uj
2
−2 2
σ
buj
= En [Jbuj
ψuj (W, θeuj , ηbuj )],

u ∈ U , j ∈ [p̃],

−1 b−1
Moreover, as in Section 2, define ψbuj (W ) = −b
σuj
Juj ψuj (W, θ̌uj , ηbuj ), and
let cα be the (1−α) quantile of the conditional distribution of supu∈U ,j∈[p̃] |Gbuj |
given the data (Wi )ni=1 where the process Gb = (Gbuj )u∈U ,j∈[p̃] is defined in
(2.8). Then we have

POST-REGULARIZATION CONFIDENCE REGIONS

21

Corollary 3.2 (Uniform confidence bands for logistic model). Suppose
that Assumptions 3.1 – 3.5 hold for all P ∈ Pn . In addition, suppose that
2/7
the following growth conditions hold: δn2 log an = o(1), Mn,1 log an = o(n1/7 ),
2/3

Mn,1 log an = o(n1/3−2/(3q) ), and sn log3 an = o(n). Then (1.3) holds uniformly over P ∈ Pn .
To conclude this section, we provide an example for which conditions of
Corollary 3.2 are easy to interpret. Recall that an = n ∨ p ∨ p̃.
Corollary 3.3 (Uniform confidence bands for logistic regression model
under simple conditions). Suppose that Assumptions 3.1 – 3.3, 3.4(i,ii,iv),
and 3.5(i,ii,iv,v) hold for q > 4 for all P ∈ Pn . In addition, suppose that
{EP [(kDk∞ ∨ kXk∞ )2q ]}1/(2q) 6 C1 and supu∈U ,j∈[p̃] kγuj k1 6 C1 . Moreover, suppose that the following growth conditions hold: log7 an /n = o(1),
s2n log3 an /n1−2/q = o(1), and supu∈U ,j∈[p̃] |EP [ru Zuj ]| = o((n log an )−1/2 ).
Then (1.3) holds uniformly over P ∈ Pn .
Comment 3.1 (Estimation of variance). When constructing the confidence bands based on (1.3), we find in simulations that it is beneficial to
2 of σ 2 by max{b
2 ,Σ
b 2 } where Σ
b 2 = En [fbu2 (D −
replace the estimators σ
buj
σuj
uj
uj
uj
j
j
2
2
X γ
eu ) ] is an alternative consistent estimator of σuj .

Comment 3.2 (Alternative implementations, double selection). We note
that the theory developed here is applicable for different estimators that
construct the new score function with the desired orthogonality condition
implicitly. For example, the double selection idea yields an implementation
of an estimator that is first-order equivalent to the estimator based on the
score function. The algorithm yielding the double selection estimator is as
follows.

Algorithm 2. For each u ∈ U and j ∈ [p̃]:
Step 1′ . Run post-ℓ1 -penalized logistic estimator (4.2) of Yu on D and X to
compute (θeu , βeu ).
Step 2′ . Define the weights fbu2 = fbu2 (D, X) = Λ′ (Di′ θeu + Xi′ βeu ).
buj .
Step 3′ . Run the lasso estimator (4.4) of fbu Dj on fbu X to compute γ

Step 4′ . Run logistic regression of Yu on Dj and all the selected variables in
Steps 1′ and 3′ to compute θ̌uj .

As mentioned by a referee, it is surprising that the double selection procedure has uniform validity. The use of the additional variables selected in Step

22

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

3’, through the first order conditions of the optimization problem, induces
the necessary near-orthogonality condition. We refer to the Supplementary
Material for a more detailed discussion.

Comment 3.3 (Alternative implementations, one-step correction). Another implementation for which the theory developed here applies is to replace Step 5 in Algorithm 1 with a one-step procedure. This relates to the
debiasing procedure proposed in [38] to the case when the set U is a singleton. In this case instead of minimizing the criterion (3.5) in Step 5, the
method makes a full Newton step from the initial estimate,
−1
Step 5′′ . Compute θ̄uj = θbuj − Jbuj
En [ψuj (W, θbuj , ηbuj )].
The theory developed here directly apply to those estimators as well.


Comment 3.4 (Extension to other approximately sparse generalized linear models). Inspecting the proofs of Theorem 3.1 and Corollaries 3.1–3.3
reveals that these results can be extended with minor modifications to cover
other approximately sparse generalized linear models. For example, the results can be extended to cover the model (3.1) where we use the probit link
function instead of the logit link function Λ.

4. ℓ1 -Penalized M-Estimators: Nuisance Functions and Funceuj ,
tional Data. In this section, we define the estimators θeu , βeu , and γ
which were used in the previous section, and study their properties. We
consider the same setting as that in the previous section. The results in this
section rely upon a set of new results for ℓ1 -penalized M -estimators with
functional data presented in Appendix L of the Supplementary Material.
4.1. ℓ1 -Penalized Logistic Regression for Functional Response Data: Asymptotic Properties. Here we consider the generalized linear model with the
logistic link function and functional response data (3.1). As explained in the
previous section, we assume that θeu and βeu are post-regularization maximum likelihood estimators of θu and βu corresponding to the log-likelihood
function Mu (W, θ, β) = Mu (Yu , D, X, θ, β) defined in (3.3). To define these
estimators, let θbu and βbu be ℓ1 -penalized maximum likelihood (logistic regression) estimators


λ b
′
′ ′
(θ
,
β
)
k
(4.1)
(θbu , βbu ) ∈ arg min En [Mu (Yu , D, X, θ, β)] + kΨ
u
1
θ,β
n
b u a diagonal matrix of penalty loadings. We
where λ is a penalty level and Ψ
b u according to Algorithm 3 described below. Uschoose parameters λ and Ψ
ing the ℓ1 -penalized estimators θbu and βbu , we then define post-regularization

POST-REGULARIZATION CONFIDENCE REGIONS

23

estimators θeu and βeu by

(4.2) (θeu , βeu ) ∈ arg min En [Mu (Yu , D, X, θ, β)] : supp(θ, β) ⊆ supp(θbu , βbu ).
θ

We derive the rate of convergence and sparsity properties of θeu and βeu as
well as of θbu and βbu in Theorem 4.1 below. Recall that an = n ∨ p ∨ p̃.

Algorithm 3 (Penalty Level and Loadings for Logistic Regression).
Choose γ ∈ [1/n, 1/ log n] and c > 1 (in practice, we set c = 1.1 and
√
γ = .1/ log n). Define λ = c nΦ−1 (1 − γ/(2(p + p̃)Nn )) with Nn = n.
b u , choose a constant m̄ > 0 as an upper bound on the number
To select Ψ
e = (D ′ , X ′ )′ , m = 0, and initialof loops and proceed as follows: (0) Let X
1
1/2
2
b
e
for k ∈ [p + p̃]. (1) Compute (θbu , βbu ) and (θeu , βeu )
ize luk,0 = 2 {En [Xk ]}
b u = diag({b
e 2 (Yu −
based on Ψ
luk,m , k ∈ [p + p̃]}). (2) Set b
luk,m+1 := {En [X
k
b u and
Λ(D ′ θeu + X ′ βeu ))2 ]}1/2 . (3) If m > m̄, report the current value of Ψ
stop; otherwise set m ← m + 1 and go to step (1).

Theorem 4.1 (Rates and Sparsity for Functional Response under Logistic
Link). Suppose that Assumptions 3.1 – 3.5 hold for all P ∈ Pn . In addition,
bu
suppose that the penalty level λ and the matrices of penalty loadings Ψ
are chosen according to Algorithm 3. Moreover, suppose that the following
growth condition holds: δn2 log an = o(1). Then there exists a constant C̄ such
that uniformly over all P ∈ Pn with probability 1 − o(1),
r


sn log an
,
sup kθbu − θu k + kβbu − βu k 6 C̄
n
u∈U
r


s2n log an
b
b
sup kθu − θu k1 + kβu − βu k1 6 C̄
,
n
u∈U
and the estimators θbu and βbu are uniformly sparse: supu∈U kθbu k0 + kβbu k0 6
C̄sn . Also, uniformly over all P ∈ Pn , with probability 1 − o(1),
r


sn log an
e
e
,
sup kθu − θu k + kβu − βu k 6 C̄
n
u∈U
r


s2n log an
sup kθeu − θu k1 + kβeu − βu k1 6 C̄
.
n
u∈U

4.2. Lasso with Estimated Weights: Asymptotic Properties. Here we consider the weighted linear model (3.2) for u ∈ U and j ∈ [p̃]. Using the parameter γ̄uj appearing in Assumption 3.2, it will be convenient to rewrite

24

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

this model as
(4.3)

fu Dj = fu X j γ̄uj + fu r̄uj + vuj ,

EP [fu X j vuj ] = 0

where r̄uj = X j (γuj − γ̄uj ) is an approximation error, which is asymptotically
negligible under Assumption 3.2. As explained in the previous section, we
assume that e
γuj is a post-regularization weighted least squares estimator of
γuj (or γ̄uj ). To define this estimator, let γ
buj be an ℓ1 -penalized (weighted
Lasso) estimator


λ b
j
2
j 2
1
b
(4.4)
γ
bu ∈ arg min 2 En [fu (Dj − X γ) ] + kΨuj γk1
γ
n
b uj are the associated penalty level and the diagonal mawhere λ and Ψ
trix of penalty loadings specified below in Algorithm 4 and where fbu2 ’s
are estimated weights. As in Algorithm 1 in the previous section, we set
fbu2 = fbu2 (D, X) = Λ′ (D ′ θeu + X ′ βeu ). Using b
γuj , we define a post-regularized
weighted least squares estimator
(4.5)

γ
euj ∈ arg min 12 En [fbu2 (Dj − X j γ)2 ] : supp(γ) ⊆ supp(b
γuj ).
γ

We derive the rate of convergence and sparsity properties of γ
euj as well as of
j
γ
bu in Theorem 4.2 below.

Algorithm 4 (Penalty Level and Loadings for Weighted Lasso). Choose
γ ∈ [1/n, 1/ log n] and c > 1 (in practice, we set c = 1.1 and γ = .1/ log n).
√
b uj ,
Define λ = c nΦ−1 (1 − γ/(2(p + p̃)Nn )) with Nn = pp̃2 n2 . To select Ψ
choose a constant m̄ > 1 as an upper bound on the number of loops and proceed as follows: (0) Set m = 0 and b
lujk,0 = max16i6n kfbui Xij k∞ {En [fbu2 Dj2 ]}1/2 .
b uj = diag({b
(1) Compute γ
buj and γ
euj based on Ψ
lujk,m , k ∈ [p + p̃ − 1]}). (2)
j
j 2 1/2
4
j
2
b
b
Set lujk,m+1 := {En [fu (Dj − X e
γu ) (Xk ) ]} . (3) If m > m̄, report the
j
b
current value of Ψu and stop; otherwise set m ← m + 1 and go to step (1).

Theorem 4.2 (Rates and Sparsity for Lasso with Estimated Weights).
Suppose that Assumptions 3.1 – 3.5 hold for all P ∈ Pn . In addition, suppose
b uj are chothat the penalty level λ and the matrices of penalty loadings Ψ
sen according to Algorithm 4. Moreover, suppose that the following growth
condition holds: δn2 log an = o(1). Then there exists a constant C̄ such that
uniformly over all P ∈ Pn with probability 1 − o(1),
r
r
sn log an
s2n log an
j
j
j
j
, max sup kb
γu − γ̄u k1 6 C̄
,
max sup kb
γu − γ̄u k 6 C̄
n
n
j∈[p̃] u∈U
j∈[p̃] u∈U

POST-REGULARIZATION CONFIDENCE REGIONS

25

and the estimator γ
buj is uniformly sparse, maxj∈[p̃] supu∈U kb
γuj k0 6 C̄sn .
Also, uniformly over all P ∈ Pn , with probability 1 − o(1),
r
r
sn log an
s2n log an
j
j
j
j
, max sup ke
γu − γ̄u k1 6 C̄
.
max sup ke
γu − γ̄u k 6 C̄
n
n
j∈[p̃] u∈U
j∈[p̃] u∈U
5. Monte Carlo Simulations. In this section we provide a simulation
study to investigate the finite sample properties of the proposed estimators
and the associated confidence regions. We report only the performance of the
estimator based on the double selection procedure due to space constraints
and note that it is very similar to the performance of the estimator based
on score functions with near-orthogonality property. We will compare the
proposed procedure with the traditional estimator that refits the model selected by the corresponding ℓ1 -penalized M-estimator (naive post-selection
estimator).
We consider a logistic regression model with functional response data
where the response Yu = 1{y 6 u} for u ∈ U a compact set. We specify two
different designs: (1) a location model, y = x′ β0 + ξ, where ξ is distributed
as a logistic random variable, the first component of x is the intercept and
the other p − 1 components are distributed as N (0, Σ) with Σk,j = |0.5||k−j| ;
(2) a location-shift model, y = {(x′ β0 + ξ)/x′ ϑ0 }3 , where ξ is distributed as
a logistic random variable, xj = |wj | where w is a p-vector distributed as
N (0, Σ) with Σk,j = |0.5||k−j| , and ϑ0 has non-negative components. Such
specification implies that for each u ∈ U
Design 1: θu = u(1, 0, . . . , 0)′ − β0

and Design 2: θu = u1/3 ϑ0 − β0 .

In our simulations we will consider n = 500 and p = 2000. For the location
(i)
model (Design 1) we will consider two different choices for β0 : (i) β0j = 2/j 2
(ii)

for j = 1, . . . , p, and (ii) β0j = (1/2)/{j − 3.5}2 for j > 1 with the intercept
(ii)

coefficient β01 = −10. (These choices ensure maxj>1 |β0j | = 2 and that y is
around zero in Design 2(ii).) We set ϑ0 = 18 (1, 1, 1, 1, 0, 0, . . . , 0, 0, 1, 1, 1, 1)′ .
For Design 1 we have U = [1, 2.5] and for Design 2 we have U = [−.5, .5]. The
results are based on 500 replications (the bootstrap procedure is performed
5000 times for each replication).
We report the (empirical) rejection frequencies for confidence regions with
95% nominal coverage. That is, the fraction of simulations the confidence
regions of a particular method did not cover the true value (thus .05 rejection
frequency is the ideal performance). We report the rejection frequencies for
the proposed estimator and the post-naive selection estimator.

26

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Table 1 presents the performance of the methods when applied to construct a confidence interval for a single parameter (p̃ = 1 and U is a singleton). Since the setting is not symmetric we investigate the performance for
different components. Specifically, we consider {u} × {j} for j = 1, . . . , 5.
In addition, Table 3 in the Supplementary Material contains the results for
j = 6, . . . , 10. First consider the location model (Design 1). The difference
between the performance of the naive estimator for Design 1(i) and 1(ii)
highlights its fragile performance which is highly dependent on the unknown
parameters. We can see from Tables 1 and 3 that in Design 1(i) the Naive
method achieve (pointwise) rejection frequencies between .032 and .162 when
the nominal level is .05. However, in the Design 1(ii) the range goes from
0.018 to 0.904. We also note that it is important to look at the performance
of each component and avoid averaging across components (large j components are essentially not in the model, indeed for j > 50 we obtain rejection
frequencies very close to .05 regardless of the model selection procedure). In
contrast the proposed estimator exhibits a more robust behavior. For Design
1(i) the rejection frequencies are between .028 and .062 while for Design 1(ii)
the rejection frequencies of the proposed estimator were between 0.044 and
0.056.
Table 2 presents the performance for simultaneous confidence bands of the
form {[θ̃uj − cvσ̃uj , θ̃uj + cvσ̃uj ] for u ∈ U × [p̃] where θ̃uj is a point estimate,
σ̃uj is an estimate of the pointwise standard deviation, and cv is a critical
value that accounts for the uniform estimation. For the point estimate we
consider the proposed estimator and the post-naive selection estimator which
have estimates of standard deviation. We consider two critical values: from
the multiplier bootstrap (MB) procedure and the Bonferroni (BF) correction
(which we expect to be conservative). For each of the four different designs
(1(i), 1(ii), 2(i) and 2(ii) described above), we consider four different choices
of U × [p̃]. Table 2 displays rejection frequencies for confidence regions with
95% nominal coverage (and again .05 would be the ideal performance). The
simulation results confirms the differences between the performance of the
methods and overall the proposed procedure is closer to the nominal value of
.05 . The proposed estimator performed within a factor of two to the nominal
value in 10 out of the 16 designs considered (and 13 out 16 within a factor
of three). The post-naive selection estimator performed within a factor of
two only in 3 out of the 16 designs when using the multiplier bootstrap as
critical value (7 out of 16 within a factor of three) and similarly with the
Bonferroni correction as the critical value.

POST-REGULARIZATION CONFIDENCE REGIONS

27

p = 2000, n = 500
Design
Method
1(i)
Proposed
Naive
1(ii)
Proposed
Naive
2(i)
Proposed
Naive
2(ii)
Proposed
Naive

Rejection Frequencies for j ∈ {1, . . . , 5}
j=1 j=2 j=3 j=4
j=5
0.042 0.040 0.062 0.050
0.044
0.100 0.098 0.108 0.108
0.162
0.044 0.040 0.054 0.056
0.056
0.038 0.030 0.070 0.886
0.698
0.046 0.054 0.044 0.052
0.054
0.046 0.050 0.038 0.070
0.054
0.092 0.074 0.034 0.088
0.082
0.034 0.972 0.182 0.312
0.916
Table 1
We report the pointwise rejection frequencies of each method for (pointwise) confidence
intervals for each j ∈ {1, . . . , 5}. For Design 1 we used U = {1} and for Design 2 we
used U = {.5}. The results are based on 500 replications.

p = 2000, n = 500
Design
Method
Proposed
1(i)
Naive (MB)
Naive (BF)
Propose
1(ii)
Naive (MB)
Naive (BF)
Design
Method
Proposed
Naive (MB)
2(i)
Naive (BF)
Proposed
2(ii)
Naive (MB)
Naive (BF)

Uniform over U × [p̃]
[1, 2.5] × {1}
{1} × [10]
[1, 2.5] × [10]
{1} × [1000]
0.054
0.036
0.048
0.040
0.126
0.136
0.172
0.032
0.014
0.124
0.026
0.032
0.270
0.036
0.032
0.142
0.014
0.802
0.934
0.404
0.000
0.802
0.718
0.376
[−.5, .5] × {1} {.5} × [10] [−.5, .5] × [10] {.5} × [1000]
0.364
0.038
0.052
0.062
0.116
0.040
0.022
0.048
0.018
0.038
0.000
0.046
0.140
0.090
0.408
0.084
0.002
0.946
0.996
0.362
0.000
0.946
0.944
0.298
Table 2
We report the rejection frequencies of each method for the (uniform) confidence bands for
U × [p̃]. The proposed estimator computes the critical value based on the multiplier
bootstrap procedure. For the naive post-selection estimator we report the results for two
choices of critical values, one choice based on the multiplier bootstrap (MB), and another
based on Bonferroni (BF) correction. The results are based on 500 replications.

28

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

APPENDIX A: NOTATION
Throughout the paper, the symbols P and E denote probability and expectation operators with respect to a generic probability measure. If we
need to signify the dependence on a probability measure P , we use P as a
subscript in PP and EP . Note also that we use capital letters such as W to
denote random elements and use the corresponding lower case letters such as
w to denote fixed values that these random elements can take. For a positive
integer k, [k] denotes the set {1, . . . , k}.
We denote by Pn the (random) empirical probability measure that assigns
probability n−1 to each Wi ∈ (Wi )ni=1 . En denotes the expectation with
respect to the empirical measure, and Gn = Gn,P denotes the empirical
√
process n(En − EP ), that is,
Gn,P (f ) = Gn,P (f (W )) = n−1/2
EP [f (W )] :=

Z

n
X
{f (Wi ) − EP [f (W )]},
i=1

f (w)dP (w),

indexed by a class of measurable functions F : W → R; see [15, chap. 2.3].
In what follows,R we use k·kP,q to denote the Lq (P ) norm; forPexample, we use
kf (W )kP,q = ( |f (w)|q dP (w))1/q and kf (W )kPn ,q = (n−1 ni=1 |f (Wi )|q )1/q .
For a vector v = (v1 , . . . , vp )′ ∈ Rp , kvk0 denotes the ℓ0 -“norm” of v, that
is, the number of non-zero components of v, kvk1 denotes the ℓ1 -norm of v,
that is, kvk1 =√|v1 | + · · · + |vp |, and kvk denotes the Euclidean norm of v,
that is, kvk = v ′ v.
We say that a class of functions F = {f (·, t) : t ∈ T }, where f : W × T →
R, is suitably measurable if it is an image admissible Suslin class, as defined
in [22], p 186. In particular, F is suitably measurable if f : W × T → R is
measurable and T is a Polish space equipped with its Borel σ-field, see [22],
p 186.
APPENDIX B: PROOFS FOR SECTION 2
In this appendix, we use C to denote a strictly positive constant that is
independent of n and P ∈ Pn . The value of C may change at each appearance. Also, the notation an . bn means that an 6 Cbn for all n and some C.
The notation an & bn means that bn . an . Moreover, the notation an = o(1)
means that there exists a sequence (bn )n>1 of positive numbers such that
(i) |an | 6 bn for all n, (ii) bn is independent of P ∈ Pn for all n, and (iii)
bn → 0 as n → ∞. Finally, the notation an = OP (bn ) means that for all
ǫ > 0, there exists C such that PP (an > Cbn ) 6 1 − ǫ for all n. Using this

POST-REGULARIZATION CONFIDENCE REGIONS

29

notation allows us to avoid repeating “uniformly over P ∈ Pn ” many times
in the proofs of Theorem 2.1 and Corollaries 2.1 and 2.2. Throughout this
appendix, we assume that n > n0 .
Proof of Theorem 2.1. We split the proof into five steps.
Step 1. (Preliminary Rate Result). We claim that with probability 1 −
o(1),
sup |θ̌uj − θuj | . B1n τn .
u∈U ,j∈[p̃]

By definition of θ̌uj , we have for each u ∈ U and j ∈ [p̃],
En [ψuj (W, θ̌uj , ηbuj )] 6 inf

θ∈Θuj

En [ψuj (W, θ, ηbuj )] + ǫn ,

which implies via the triangle inequality that uniformly over u ∈ U and
j ∈ [p̃], with probability 1 − o(1),
EP [ψuj (W, θ, ηuj )]|θ=θ̌uj 6 ǫn + 2I1 + 2I2 . B1n τn , where

(B.1)
I1 :=

En [ψuj (W, θ, ηbuj )] − En [ψuj (W, θ, ηuj )] . B1n τn ,

sup
u∈U ,j∈[p̃],θ∈Θuj

I2 :=

En [ψuj (W, θ, ηuj )] − EP [ψuj (W, θ, ηuj )] . τn .

sup
u∈U ,j∈[p̃],θ∈Θuj

and the bounds on I1 and I2 are derived in Step 2 (note also that ǫn =
o(τn ) by construction of the estimator and Assumption 2.2(vi)). Since by
Assumption 2.1(iv), 2−1 |Juj (θ̌uj − θuj )| ∧ c0 does not exceed the left-hand
side of (B.1), inf u∈U ,j∈[p̃] |Juj | & 1, and by Assumption 2.2(vi), B1n τn = o(1),
we conclude that

−1
B1n τn . B1n τn ,
(B.2)
sup |θ̌uj − θuj | .
inf |Juj |
u∈U ,j∈[p̃]

u∈U ,j∈[p̃]

with probability 1 − o(1) yielding the claim of this step.
Step 2. (Bounds on I1 and I2 ) We claim that with probability 1 − o(1),
I1 . B1n τn and I2 . τn .
To show these relations, observe that with probability 1 − o(1), we have
I1 6 2I1a + I1b and I2 6 I1a , where
I1a :=

sup
u∈U ,j∈[p̃],θ∈Θuj ,η∈Tuj

I1b :=

sup
u∈U ,j∈[p̃],θ∈Θuj ,η∈Tuj

En [ψuj (W, θ, η)] − EP [ψuj (W, θ, η)] ,
EP [ψuj (W, θ, η)] − EP [ψuj (W, θ, ηuj )] .

30

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

To bound I1b , we employ Taylor’s expansion:
h
i
I1b 6
sup
∂r EP ψuj (W, θ, ηuj + r(η − ηuj ))
u∈U ,j∈[p̃],θ∈Θuj ,η∈Tuj ,r∈[0,1)

6 B1n

sup

u∈U ,j∈[p̃],η∈Tuj

kη − ηuj ke 6 B1n τn ,

by Assumptions 2.1(v) and 2.2(ii).
To bound I1a , we apply the maximal inequality of Lemma O.2 to the class
F1 defined in Assumption 2.2 to conclude that with probability 1 − o(1),
p

(B.3)
I1a . n−1/2
vn log an + n−1/2+1/q vn Kn log an .

Here we used: log supQ N (ǫkF1 kQ,2 , F1 , k · kQ,2 ) 6 vn log(an /ǫ) for all 0 <
ǫ 6 1 with kF1 kP,q 6 Kn by Assumption 2.2(iv); supf ∈F1 kf k2P,2 6 C0 by
Assumption 2.2(v); an > n ∨ Kn and vn > 1 by the choice of an and vn .
In turn, the right-hand side of (B.3) is bounded from above by O(τn ) by
Assumption 2.2(vi) since (vn log an /n)1/2 . τn and
n−1/2 n−1/2+1/q vn Kn log an . n−1/2 δn . n−1/2 . τn .
Combining presented bounds gives the claim of this step.
Step 3. (Linearization) Here we prove the claim of the theorem. Fix u ∈ U
and j ∈ [p̃]. By definition of θ̌uj , we have
(B.4)

√
√
√
n En [ψuj (W, θ̌uj , ηbuj )] 6 inf
n En [ψuj (W, θ, ηbuj )] + ǫn n.
θ∈Θuj

Also, for any θ ∈ Θuj and η ∈ Tuj , we have
(B.5)

√
√
nEn [ψuj (W, θ, η)] = nEn [ψuj (W, θuj , ηuj )] − Gn ψuj (W, θuj , ηuj )


√
− n EP [ψuj (W, θuj , ηuj )] − EP [ψuj (W, θ, η)] + Gn ψuj (W, θ, η).

Moreover, by Taylor’s expansion of the function r 7→ EP [ψuj (W, θuj + r(θ −
θuj ), ηuj + r(η − ηuj ))],
(B.6)

EP [ψuj (W, θ, η)] − EP [ψuj (W, θuj , ηuj )] = Juj (θ − θuj ) + Du,j,0 [η − ηuj ]
+ 2−1 ∂r2 EP [W, θuj + r(θ − θuj ), ηuj + r(η − ηuj )]

r=r̄

for some r̄ ∈ (0, 1). Substituting this equality into (B.5), taking θ = θ̌uj and
η = ηbuj , and using (B.4) gives
(B.7)

√
ηuj − ηuj ]
n En [ψuj (W, θuj , ηuj )] + Juj (θ̌uj − θuj ) + Du,j,0 [b
√
√
6 ǫn n + inf
n|En [ψuj (W, θ, ηbuj )]| + |II1 (u, j)| + |II2 (u, j)|,
θ∈Θuj

POST-REGULARIZATION CONFIDENCE REGIONS

where
II1 (u, j) :=

√

31

h
i
n sup ∂r2 EP ψuj (W, θuj + r(θ − θuj ), ηuj + r{η − ηuj }) ,
r∈[0,1)



II2 (u, j) := Gn ψuj (W, θ, η) − ψuj (W, θuj , ηuj )

with θ = θ̌uj and η = ηbuj . It will be shown in Step 4 that


|II1 (u, j)| + |II2 (u, j)| = OP (δn ).
(B.8)
sup
u∈U ,j∈[p̃]

In addition, it will be shown in Step 5 that
√
(B.9)
sup
inf
n|En [ψuj (W, θ, ηbuj )]| = OP (δn ).
u∈U ,j∈[p̃] θ∈Θuj

√
Moreover, ǫn n = o(δn ) by construction of the estimator. Therefore, the exηuj −ηuj ]| = OP (δn n−1/2 )
pression in (B.7) is OP (δn ). Also, supu∈U ,j∈[p̃] |Du,j,0 [b
by the near-orthogonality condition since ηbuj ∈ Tuj for all u ∈ U and
j ∈ [p̃] with probability 1 − o(1) by Assumption 2.2(i). Therefore, Assumption 2.1(iv) gives
√
−1 √
nEn [ψuj (W, θuj , ηuj )] + n(θ̌uj − θuj ) = OP (δn ).
sup Juj
u∈U ,j∈[p̃]

The asserted claim now follows by dividing both parts of the display above
by σuj (under the supremum on the left-hand side) and noting that σuj is
bounded below from zero uniformly over u ∈ U and j ∈ [p̃] by Assumptions
2.2(iii) and 2.2(v).
Step 4. (Bounds on II1 (u, j) and II2 (u, j)). Here we prove (B.8). First,
with probability 1 − o(1),
√
ηuj − ηuj k2e
sup |II1 (u, j)| 6 nB2n sup |θ̌uj − θuj |2 ∨ kb
u∈U ,j∈[p̃]

.

√

u∈U ,j∈[p̃]

2
nB1n
B2n τn2

. δn ,

where the first inequality follows from Assumptions 2.1(v) and 2.2(i), the
second from Step 1 and Assumptions 2.2(ii) and 2.2(vi), and the third from
Assumption 2.2(vi).
Second, we have with probability 1 − o(1) that supu∈U ,j∈[p̃] |II2 (u, j)| .
supf ∈F2 |Gn (f )|, where
n
F2 = ψuj (·, θ, η) − ψuj (·, θuj , ηuj ) :
o
u ∈ U , j ∈ [p̃], η ∈ Tuj , |θ − θuj | 6 CB1n τn

32

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

for sufficiently large constant C. To bound supf ∈F2 |Gn (f )|, we apply Lemma
O.2. Observe that
sup kf k2P,2 6

f ∈F2

sup
u∈U ,j∈[p̃],|θ−θuj |6CB1n τn ,η∈Tuj

sup

6

u∈U ,j∈[p̃],|θ−θuj |6CB1n τn ,η∈Tuj



EP (ψuj (W, θ, η) − ψuj (W, θuj , ηuj ))2

C0 (|θ − θuj | ∨ kη − ηuj ke )ω . (B1n τn )ω ,

where we used Assumption 2.1(v) and Assumption 2.2(ii). Also, observe that
(B1n τn )ω/2 > n−ω/4 by Assumption 2.2(vi) since B1n > 1. Therefore, an
application of Lemma O.2 with an envelope F2 = 2F1 and σ = (CB1n τn )ω/2
for sufficiently large constant C gives with probability 1 − o(1),
p
(B.10)
sup |Gn (f )| . (B1n τn )ω/2 vn log an + n−1/2+1/q vn Kn log an ,
f ∈F2

since supf ∈F2 |f | 6 2 supf ∈F1 |f | 6 2F1 and kF1 kP,q 6 Kn by Assumption
2.2(iv) and
log sup N (ǫkF2 kQ,2 , F2 , k · kQ,2 ) . vn log(an /ǫ),

for all 0 < ǫ 6 1

Q

by Lemma N.1 because F2 ⊂ F1 − F1 for F1 defined in Assumption 2.2(iv).
The claim of this step now follows from an application of Assumption 2.2(vi)
to bound the right-hand side of (B.10).
Step 5. Here we prove (B.9). For all u ∈ U and j ∈ [p̃], let θ̄uj =
√
−1
θuj − Juj
En [ψuj (W, θuj , ηuj )]. Then supu∈U ,j∈[p̃] |θ̄uj − θuj | = OP (Sn / n)
√
since Sn = EP [supu∈U ,j∈[p̃] | nEn [ψuj (Wuj , θuj , ηuj )]|] and Juj is bounded
in absolute value below from zero uniformly over u ∈ U and j ∈ [p̃] by
Assumption 2.1(iv). Therefore, θ̄uj ∈ Θuj for all u ∈ U and j ∈ [p̃] with
probability 1 − o(1) by Assumption 2.1(i). Hence, with the same probability,
for all u ∈ U and j ∈ [p̃],
√
√
n En [ψuj (W, θ, ηbuj )] 6 n En [ψuj (W, θ̄uj , ηbuj )] ,
inf
θ∈Θuj

and so it suffices to show that
√
(B.11)
sup
n En [ψuj (W, θ̄uj , ηbuj )] = OP (δn ).
u∈U ,j∈[p̃]

To prove (B.11), for given u ∈ U and j ∈ [p̃], substitute θ = θ̄uj and η = ηbuj
into (B.5) and use Taylor’s expansion in (B.6). This gives
√
f1 (u, j)| + |II
f2 (u, j)|
n En [ψuj (W, θ̄uj , ηbuj )] 6 |II
√
+ n En [ψuj (W, θuj , ηuj )] + Juj (θ̄uj − θuj ) + Du,j,0 [b
ηuj − ηuj ] ,

POST-REGULARIZATION CONFIDENCE REGIONS

33

f1 (u, j) and II
f2 (u, j) are defined as II1 (u, j) and II2 (u, j) in Step
where II
3 but with θ̌uj replaced by θ̄uj . Then, given that supu∈U ,j∈[p̃] |θ̄uj − θuj | .
√
Sn log n/ n with probability 1 − o(1), the argument in Step 4 shows that


f1 (u, j)| + |II
f2 (u, j)| = OP (δn ).
|II
sup
u∈U ,j∈[p̃]

In addition,

En [ψuj (W, θuj , ηuj )] + Juj (θ̄uj − θuj ) = 0

by the definition of θ̄uj and supu∈U ,j∈[p̃] |Du,j,0 [b
ηuj − ηuj ]| = OP (δn n−1/2 ) by
the near-orthogonality condition. Combining these bounds gives (B.11), so
that the claim of this step follows, and completes the proof of the theorem.


APPENDIX C: REMAINING PROOFS FOR SECTION 2
See Supplementary Material.
APPENDIX D: PROOFS FOR SECTIONS 3 AND 4
See Supplementary Material.
REFERENCES
[1] Andrews, D.W.K. (1994). Asymptotics for semiparametric econometric models via
stochastic equicontinuity. Econometrica, 62(1):43–72.
[2] Belloni, A., Chen, D, Chernozhukov, V., and Hansen, C. (2012). Sparse models and
methods for optimal instruments with an application to eminent domain. Econometrica, 80:2369–2429. arXiv:1010.4345, 2010.
[3] Belloni, A. and Chernozhukov, V. (2011). ℓ1 -penalized quantile regression for high
dimensional sparse models. Annals of Statistics, 39(1):82–130. arXiv:0904.2931, 2009.
[4] Belloni, A. and Chernozhukov, V. (2013). Least squares after model selection in
high-dimensional sparse models. Bernoulli, 19(2):521–547. arXiv:1001.0188, 2009.
[5] Belloni, A., Chernozhukov, V., and Hansen, C. (2010). Lasso methods for gaussian
instrumental variables models. arXiv:1012.1297, 2010.
[6] Belloni, A., Chernozhukov, V., and Hansen, C. (2013). Inference for high-dimensional
sparse econometric models. Advances in Economics and Econometrics. 10th World
Congress of Econometric Society. August 2010, III:245–295. arXiv:1201.0220, 2011.
[7] Belloni, A., Chernozhukov, V., and Hansen, C. (2014). Inference on treatment effects after selection amongst high-dimensional controls. Review of Economic Studies,
81:608–650. arXiv:1201.0224, 2011.
[8] Belloni, A., Chernozhukov, V., and Kato, K. (2013). Valid Post-Selection Inference in High-Dimensional Approximately Sparse Quantile Regression Models.
arXiv:1312.7186, 2013.
[9] Belloni, A., Chernozhukov, V., and Kato, K. (2015). Uniform post selection inference for LAD regression models and other Z-estimators. Biometrika, (102):77–94.
arXiv:1304.0282, 2013.

34

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

[10] Belloni, A., Chernozhukov, V., and Wang, L. (2011). Square-root-lasso: Pivotal
recovery of sparse signals via conic programming. Biometrika, 98(4):791–806.
arXiv:1009.5689, 2010.
[11] Belloni, A., Chernozhukov, V., Fernández-Val, I., and Hansen, C. (2013). Program
evaluation with high-dimensional data. arXiv:1311.2645, 2013.
[12] Belloni, A., Chernozhukov, V., and Wang, L. (2014). Pivotal estimation via squareroot lasso in nonparametric regression. The Annals of Statistics, 42(2):757–788.
arXiv:1105.1475, 2013.
[13] Chamberlain, G. (1992). Efficiency bounds for semiparametric regression. Econometrica, 60:567–596.
[14] Chernozhukov, V., Chetverikov, D., and Kato, K. (2013). Gaussian approximations
and multiplier bootstrap for maxima of sums of high-dimensional random vectors.
The Annals of Statistics, 41(6):2786–2819. arXiv:1212.6906, 2012.
[15] Chernozhukov, V., Chetverikov, D., and Kato, K. (2014). Anti-concentration and
honest, adaptive confidence bands. The Annals of Statistics, 42(5):1787–1818.
arXiv:1303.7152, 2013.
[16] Chernozhukov, V., Chetverikov, D., and Kato, K. (2014). Central limit theorems and
bootstrap in high dimensions. arxiv:1412.3661, 2014.
[17] Chernozhukov, V., Chetverikov, D., and Kato, K. (2014). Gaussian approximation of suprema of empirical processes. The Annals of Statistics, 42(4):1564–1597.
arXiv:1212.6885, 2012.
[18] Chernozhukov, V., Chetverikov, D., and Kato, K. (2015). Comparison and anticoncentration bounds for maxima of gaussian random vectors. Probability Theory
and Related Fields, 162:47–70. arXiv:1301.4807, 2013.
[19] Chernozhukov, V., Chetverikov, D., and Kato, K. (2015). Empirical and multiplier
bootstraps for suprema of empirical processes of increasing complexity, and related
gaussian couplings. arXiv:1502.00352, 2015.
[20] Chernozhukov, V., Fernández-Val, I., and Melly, B. (2013). Inference on counterfactual distributions. Econometrica, 81:2205–2268. arXiv:0904.0951, 2009.
[21] Chernozhukov, V., Hansen, C., and Spindler, M. (2015). Post-selection and postregularization inference in linear models with very many controls and instruments.
Americal Economic Review: Papers and Proceedings, 105:486–490. arXiv:1501.03185,
2015.
[22] Dudley, R. (1999). Uniform central limit theorems, volume 63 of Cambridge Studies
in Advanced Mathematics. Cambridge University Press, Cambridge.
[23] Hothorn, T., Kneib, T., and Bühlmann, P. (2014). Conditional transformation models. J. R. Statist. Soc. B, 76:3–27. arXiv:1201.5786, 2012.
[24] Javanmard, A. and Montanari, A. (2014). Confidence intervals and hypothesis testing for high-dimensional regression. J. Mach. Learn. Res., 15:2869–2909.
arXiv:1306.3171, 2013.
[25] Javanmard, A. and Montanari, A. (2014). Hypothesis testing in high-dimensional
regression under the gaussian random design model: asymptotic theory. IEEE Transactions on Information Theory, 60:6522–6554. arXiv:1301.4240, 2013.
[26] Kosorok, M. (2008). Introduction to Empirical Processes and Semiparametric Inference. Series in Statistics. Springer, Berlin.
[27] Leeb, H. and Pötscher, B. (2008). Can one estimate the unconditional distribution of post-model-selection estimators? Econometric Theory, 24(2):338–376.
arXiv:0704.1584, 2007.
[28] Leeb, H. and Pötscher, B. (2008). Recent developments in model selection and related
areas. Econometric Theory, 24(2):319–322.

POST-REGULARIZATION CONFIDENCE REGIONS

35

[29] Leeb, H. and Pötscher, B. (2008). Sparse estimators and the oracle property, or
the return of Hodges’ estimator. J. Econometrics, 142(1):201–211. arXiv:0704.1466,
2007.
[30] Linton, O. (1996). Edgeworth approximation for MINPIN estimators in semiparametric regression models. Econometric Theory, 12(1):30–60. Cowles Foundation
Discussion Papers (1086), 1994.
[31] Newey, W. (1990). Semiparametric efficiency bounds. Journal of Applied Econometrics, 5(2):99–135.
[32] Newey, W. (1994). The asymptotic variance of semiparametric estimators. Econometrica, 62(6):1349–1382.
[33] Neyman, J. (1959). Optimal asymptotic tests of composite statistical hypotheses.
Probability and Statistics, the Harold Cramer Volume.
[34] Neyman, J. (1979). c(α) tests and their use. Sankhya, 41:1–21.
[35] Ning, Y. and Liu, H. (2014). A general theory of hypothesis tests and confidence
regions for sparse high dimensional models. arXiv:1412.8765, 2014.
[36] Pötscher, B. and Leeb, H. (2009). On the distribution of penalized maximum likelihood estimators: the LASSO, SCAD, and thresholding. J. Multivariate Anal.,
100(9):2065–2082. arXiv:0711.0660, 2009.
[37] Robins, J. and Rotnitzky, A. (1995). Semiparametric efficiency in multivariate regression models with missing data. J. Amer. Statist. Assoc., 90(429):122–129.
[38] 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. arXiv:1303.0518, 2013.
[39] van der Vaart, A. (1998). Asymptotic Statistics. Cambridge University Press.
[40] van der Vaart, A. and Wellner, J. (1996). Weak Convergence and Empirical Processes.
Springer Series in Statistics.
[41] Zhang, C.-H, and Zhang, S. (2014). Confidence intervals for low-dimensional parameters with high-dimensional data. J. R. Statist. Soc. B, 76:217–242. arXiv:1110.2563,
2011.
[42] Zhang, X. and Cheng, G. (2017). Simultaneous inference for high-dimensional linear
models. Journal of the American Statistical Association, 0:1–12. arXiv:1603.01295,
2016.
[43] Zhao, T., Kolar, M., and Liu, H. (2014). A general framework for robust testing and
confidence regions in high-dimensional quantile regression. arXiv:1412.8724, 2014.

0

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Supplement to “Uniformly Valid Post-Regularization
Confidence Regions for Many Functional Parameters in ZEstimation Framework”
APPENDIX E: EMPIRICAL APPLICATION: US PRESIDENTIAL
APPROVAL RATINGS
In this section we illustrate the applicability of the tools proposed in this
work with data on US presidential approval ratings used in [6]. There several economic and political factors that impact presidential approval ratings.
In this illustration, we are interested on the impact of unemployment rates
and on the impact of time in office on the approval rate of a sitting president. However, the impact of such factors might not be homogeneous and
in fact depend on current ratings. For example, a sitting president is likely
to have a fraction of voters who would support him regardless of economic
factors. Thus, a low unemployment rate might not have an effect when approval ratings are low and have a significant effect when approval ratings are
high. This would imply a different effect on different parts of the conditional
distribution of the approval rating.
To study the distributional effect of these factors we use a logistic regression model with functional data as described in Section 3. Letting Y denote
the approval rating, we define Yu = 1{Y 6 u} to be the binary variable that
indicates if the approval rating is below the threshold u ∈ U = [.45, .65]. For
each level of approval rating u ∈ U we estimate the model
E[Yu | Dunemp , Dtime , X] = Λ(θu,unemp Dunemp + θu,time Dtime + X ′ βu ) + ru
where Dunemp denotes the unemployment rate, Dtime the number of months
the president has been in office, ru a (small) approximation error, and X
denotes several additional control variables. In addition to the linear terms
for the variables2 used in [6], we also consider interactions among controls.
Therefore, for each u ∈ U we have a generalized linear model using logistic
link function with 160 variables and 603 observations.
We construct simultaneous confidence bands for both coefficients (p̃ = 2)
uniformly over u ∈ U . Although p < n for every u ∈ U , the full model
(applying logistic regression with all regressors) led to numerical instabilities
and other numerical failures. We proceed to construct (asymptotically) valid
confidence regions based on the double selection procedure for functional
logistic regression.
2

Those include dummy variables for each president, Watergate scandal, causalities in
different wars, political shocks, and other variables, see [6] for a complete description.

1

POST-REGULARIZATION CONFIDENCE REGIONS
Process of Coefficient

0.50

0.55
approval ratings

0.60

0.65

150
50

unemployment
0.45

−50 0

0.05
−0.05

time_in_office

0.15

Process of Coefficient

0.45

0.50

0.55

0.60

0.65

approval ratings

Fig 1. The panels display pointwise (dotted) and uniform (dotdash) confidence bands for
the unemployment coefficient and the time-in-office coefficient. These confidence regions
are set to have 95% coverage and were constructed based on the double selection algorithm.
The critical value for the uniform confidence bands was set to 2.93 based on the multiplier
bootstrap procedure with 5000 repetitions. For both coefficients, the lowest value of the
upper confidence band is smaller than the largest value of the lower confidence band.

Figure 1 displays the estimation results. Specifically, the figure displays
point estimates of each coefficient for every u ∈ U (solid line), pointwise
confidence intervals (dotted line), and uniform confidence bands (dot-dash
lines). Point estimates account for model selection mistakes and are computed based the double selection procedure. For 95% coverage, the pointwise
critical value is taken to be Φ−1 (.975) ≈ 1.96 from the normal approximation and the critical value for uniform confidence bands (uniformly over
both coefficients and over u ∈ U ) was calculated to be 3.003 based on 5000
repetitions of the multiplier bootstrap.
At 95% confidence level, the uniform confidence band rule out “no effect”
over U for both variables. Indeed, the straight line at 0 is not contained in the
uniform confidence bands for either variable. Next consider the process of
the unemployment coefficient. The analysis suggests that the unemployment
rate has an overall negative effect on the approval rate of a sitting president
(as the coefficient is positive increasing the probability to be below a threshold). Regarding time-in-office, the effect also seems to be predominantly
negative. However, the impact is not homogeneous across u ∈ U . Indeed,
the lowest value of the upper confidence band (0.007, u = 0.584) is smaller
than the largest value of the lower confidence band (0.013, u = 0.647), see
the circles in the plot of the process of the time-in-office coefficient. The
impact seems to be greater for the lower and higher values of u ∈ U while
the effect of seems negligible in the range of u ∈ [.575, .625]. In particular,
at 95% level, no effect is ruled out for large values of u.

2

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

APPENDIX F: ADDITIONAL SIMULATION RESULTS
Here, we present additional simulation results discussed in Section 5.
p = 2000, n = 500
Design
Method
1(i)
Proposed
Naive
1(ii)
Proposed
Naive
2(i)
Proposed
Naive
2(ii)
Proposed
Naive

Rejection Frequencies for j ∈ {6, . . . , 10}
j=6 j=7 j=8 j=9
j = 10
0.028 0.044 0.048 0.042
0.036
0.110 0.078 0.072 0.068
0.032
0.052 0.044 0.048 0.054
0.050
0.172 0.062 0.030 0.052
0.018
0.040 0.038 0.052 0.036
0.044
0.040 0.064 0.038 0.038
0.044
0.046 0.068 0.058 0.068
0.070
0.096 0.028 0.018 0.016
0.024
Table 3
We report the pointwise rejection frequencies of each method for (pointwise) confidence
intervals for each j ∈ {6, . . . , 10}. For Design 1 we used U = {1} and for Design 2 we
used U = {.5}. The results are based on 500 replications.

APPENDIX G: REMAINING PROOFS FOR SECTION 2
Proof of Corollary 2.1. To prove the asserted claim, we will apply
Lemma 2.4 in [9]. Denote
Zn =

sup
u∈U ,j∈[p̃]

−1
n1/2 σuj
(θ̌uj − θuj ) .

2/7

Under our assumptions, Ln ̺n log An = o(n1/7 ), and so given that ̺n > 1
2 (W )] = 1,
and An > n, it follows that log Ln . log n. Hence, since EP [ψ̄uj
Assumption 2.3(i) and Corollary 2.2.8 in [15] imply that
"
#
p
p
sup |Nuj | . ̺n log(An Ln ) . ̺n log An .
(G.1)
EP
u∈U ,j∈[p̃]

Further, Theorem 2.1 shows that
Zn −

(G.2)

sup
u∈U ,j∈[p̃]

|Gn ψ̄uj | = OP (δn ),

and Theorem 2.1 in [10], together with Assumptions 2.3(i,ii), shows that one
can construct a version Zen of supu∈U ,j∈[p̃] |Nuj | such that
1/3

(G.3)

sup

u∈U ,j∈[p̃]

en = OP
|Gn ψ̄uj | − Z

Ln ̺n log An
Ln (̺n log An )2/3
+
1/2−1/q
n
n1/6

!

.

3

POST-REGULARIZATION CONFIDENCE REGIONS

Combining (G.2) and (G.3) gives
1/3

(G.4)

|Zn − Zen | = OP

Ln ̺n log An Ln (̺n log An )2/3
+
δn +
n1/2−1/q
n1/6

!

.

Therefore, it follows from Lemma 2.4 in [9] that (G.1) and (G.4) imply
(G.5)

sup PP (Zn 6 t) − PP (Zen 6 t) = o(1)
t∈R

2/7

under our growth conditions δn2 ρn log An = o(1), Ln ρn log An = o(n1/7 ),
2/3
and Ln ρn log An = o(n1/3−2/(3q) ); note that formally their Lemma 2.4 requires Zn to be the supremum of an empirical process but this requirement
is not used in the proof. The asserted claim now follows by substituting the
en .
definitions of Zn and Z


en∗ = supu∈U ,j∈[p̃] |Gbuj |. For all ϑ ∈
Proof of Corollary 2.2. Denote Z
0
(0, 1), let cϑ be the (1 − ϑ) quantile of supu∈U ,j∈[p̃] |Nuj |. We proceed in
several steps.
Step 1. Here we show that c0ϑ satisfies the bound
"
#
p
0
sup |Nuj | + 2 log(1/ϑ)
cϑ 6 EP
u∈U ,j∈[p̃]

2 ] = 1 for all u ∈ U and j ∈ [p̃].
for all ϑ ∈ (0, 1). Indeed, recall that EP [Nuj
Therefore, this bound follows from Borell’s inequality; see Proposition A.2.1
in [15].
Step 2. Here we show that for any ϑ ∈ (0, 1) and β ∈ (0, ϑ),
"
#
.
0
0
sup |Nuj |
cϑ−β − cϑ > cβ EP
u∈U ,j∈[p̃]

2 ] = 1 for all
for some absolute constant c > 0. Indeed, given that EP [Nuj
u ∈ U and j ∈ [p̃], this bound follows from Corollary 2.1 in [8].
Step 3. Here we show that

 q
n
1 X
∗
e
√
Zn − sup
(G.6)
ξi ψ̄uj (Wi ) = OP δ̄n ̺¯n log Ān .
n
u∈U ,j∈[p̃]
i=1

Indeed, the left-hand side of (G.6) is bounded from above by
n

sup
u∈U ,j∈[p̃]

n

1 X b
1 X
√
ξi ψ̄uj (Wi ) = sup
ξi (ψuj (Wi ) − ψ̄uj (Wi )) .
Gbuj − √
n i=1
n i=1
u∈U ,j∈[p̃]

4

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

P
Conditional on (Wi )ni=1 , n−1/2 ni=1 ξi (ψbuj (Wi )−ψ̄uj (Wi )) is zero-mean Gaussian with variance En [(ψbuj (Wi ) − ψ̄uj (Wi ))2 ] 6 δ̄n2 with probability at least
1 − ∆n by Assumption 2.3(iii). Thus, with the same probability,
"
#
q
n
1 X b
n
√
sup
EP
ξi (ψuj (Wi ) − ψ̄uj (Wi )) | (Wi )i=1 . δ̄n ̺¯n log Ān
n
u∈U ,j∈[p̃]
i=1

by Assumption 2.3(iii) and Corollary 2.2.8 in [15]. Since ∆n → 0, (G.6)
follows.
Step 4. Here we construct a version Zen of supu∈U ,j∈[p̃] |Nuj | such that
n

sup

u∈U ,j∈[p̃]

1 X
√
ξi ψ̄uj (Wi ) − Zen = OP
n i=1

1/2

Ln ̺n log An
Ln (̺n log An )3/4
+
n1/2−1/q
n1/4

!

.

Indeed, as was discussed in the proof of Corollary 2.1, we have log Ln . log n
2 (W )] = 1. Therefore, the claim follows from Theorem 2.2 in [10]
and EP [ψ̄uj
i
combined with Assumption 2.3(i,ii).
Step 5. Here we show that there
 exists a sequence of positive constants
(ϑn )n>1 such that ϑn → 0 and PP cα (1 + εn ) > c0α−ϑn → 0. Indeed, Steps
en∗ − Zen | = OP (rn ) where
3 and 4 imply that |Z
rn . δ̄n

q

1/2

Ln ̺n log An Ln (̺n log An )3/4
̺¯n log Ā +
+
.
n1/2−1/q
n1/4

Also, as in the proof of Corollary 2.1, EP [Zen ] . (̺n log An )1/2 . Hence,
rn EP [Zen ] = o(1) under our conditions, and so there exists a sequence of
en ] = o(1). Furpositive constants (χn )n>1 such that χn → ∞ but χn rn EP [Z
∗
1/2
ther, let βn = {PP (|Zen − Zen | > χn rn )} . Observe that βn = o(1) and
 


∗
n
e
e
PP PP |Zn − Zn | > χn rn | (Wi )i=1 > βn 6 βn .

The last display implies that with probability at least 1 − βn , cα 6 c0α−βn +
χn rn . Hence, with the same probability, using the bounds in Steps 1 and 2,
we obtain for some sequence of positive constants (ϑn )n>1 such that ϑn =
o(1),
cα (1 + εn ) 6 (c0α−βn + χn rn )(1 + εn ) 6 c0α−ϑn
since χn rn EP [Zen ] = o(1) and εn (EP [Zen ])2 = o(1) by assumption. The claim
of this step follows.

POST-REGULARIZATION CONFIDENCE REGIONS

5

Step 6. Here we complete the proof. We have


√ −1
sup | nb
PP
σuj (θ̌uj − θuj )| 6 cα
u∈U ,j∈[p̃]


√
−1
(θ̌uj − θuj )| 6 cα σ
buj /σuj , ∀u ∈ U , j ∈ [p̃]
= PP | nσuj


√ −1
sup | nσuj
6 PP
(θ̌uj − θuj )| 6 cα (1 + εn ) + o(1)

6 PP



u∈U ,j∈[p̃]

sup
u∈U ,j∈[p̃]


√ −1
| nσuj
(θ̌uj − θuj )| 6 c0α−ϑn + o(1)

= 1 − α + ϑn + o(1) = 1 − α + o(1),

where the third line follows by Assumption 2.4, the fourth by Step 5, and
the fifth by Corollary 2.1. Similar arguments also give the same bound from
the other side. Therefore,
!
√ −1
sup | nb
(G.7)
PP
σuj (θ̌uj − θuj )| 6 cα = 1 − α + o(1).
u∈U ,j∈[p̃]

This completes the proof.



APPENDIX H: PROOFS FOR SECTION 3
In this appendix, we use c and C to denote strictly positive constants that
depend only on c1 and C1 (but do not depend on n, u, j, or P ∈ Pn ). The
values of c and C may change at each appearance. Also, the notation an . bn
means that an 6 Cbn for all n and some C. The notation an & bn means
that bn . an . Moreover, the notation an = o(1) means that there exists a
sequence (bn )n>1 of positive numbers such that (i) |an | 6 bn for all n, (ii) bn
is independent of P ∈ Pn for all n, and (iii) bn → 0 as n → ∞. Finally, the
notation an = oP (bn ) means that for any C, we have PP (an > Cbn ) = o(1).
Using this notation allows us to avoid repeating “uniformly over P ∈ Pn ”
and “uniformly over u ∈ U and j ∈ [p̃]” many times in the proofs of Theorem
3.1 and Corollaries 3.1 – 3.3.
Proof of Theorem 3.1. Observe that for all u ∈ U and j ∈ [p̃], we
have EP [|Zuj |2 ] . 1 by Assumptions 3.1 and 3.4. We use this fact several
times in the proof without further notice.
For u ∈ U and j ∈ [p̃], define
o
n
Tuj = η = (η (1) , η (2) , η (3) ) : η (1) ∈ ℓ∞ (Rp̃+p ), η (2) ∈ Rp̃−1+p , η (3) ∈ Rp̃−1+p ,

6

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

so that ηuj = (ru , βuj , γuj ) ∈ Tuj , and Tuj is convex. Endow Tuj with a norm
k · ke defined by
q
kηke = EP [η (1) (D, X)2 ] ∨ kη (2) k ∨ kη (3) k, η = (η (1) , η (2) , η (3) ) ∈ Tuj .
Further, recall that an = p ∨ p̃ ∨ n and define τn = C(sn log an /n)1/2 and

n
Tuj = {ηuj } ∪ η = (η (1) , η (2) , η (3) ) ∈ Tuj : η (1) = O, kη (2) k0 ∨ kη (3) k0 6 Csn ,
o
√
kη (2) − βuj k ∨ kη (3) − γuj k 6 τn , kη (3) − γuj k1 6 C sn τn

for sufficiently large C.
First, we verify Assumption 2.1(i). To bound Sn , below we establish the
following inequality:
p
(H.1)
kγuj 2 − γuj 1 k1 . p + p̃|u2 − u1 |.
Recall that

fu2 = fu2 (D, X) = VarP (Yu | D, X) = EP [Yu | D, X](1 − EP [Yu | D, X]),
and so
(H.2)

|fu22 − fu21 | 6 EP [Yu2 | D, X] − EP [Yu1 | D, X] . |u2 − u1 |

by Assumption 3.3. In addition,

(H.3)

h 
2 i
EP fu22 X j (γuj 1 − γuj 2 )
h 

i
= EP fu22 X j (γuj 1 − γuj 2 ) Dj − X j γuj 2 − (Dj − X j γuj 1 )

i
h 
= −EP fu22 X j (γuj 1 − γuj 2 ) (Dj − X j γuj 1 )
h


i
= −EP (fu22 − fu21 ) X j (γuj 1 − γuj 2 ) (Dj − X j γuj 1 )
i
h


= −EP (fu22 − fu21 ) X j (γuj 1 − γuj 2 ) Zuj 1 ,

where the first line follows from adding and subtracting Dj , the second
from the equality EP [fu22 (Dj − X j γuj 2 )X j ] = 0, the third from the equality
EP [fu21 (Dj − X j γuj 1 )X j ] = 0, and the fourth from Dj − X j γuj 1 = Zuj 1 . Now,
by the Cauchy-Schwarz inequality, the expression in (H.3) is bounded in

POST-REGULARIZATION CONFIDENCE REGIONS

7

absolute value by
i1/2
h
2 i
 h
· EP (fu21 − fu22 )2 (Zuj 1 )2
EP X j (γuj 1 − γuj 2 )
i1/2
h
 h 
2 i
. EP fu22 X j (γuj 1 − γuj 2 )
· EP (fu21 − fu22 )2 (Zuj 1 )2
2 i1/2
 h 
,
. |u2 − u1 | EP fu22 X j (γuj 1 − γuj 2 )

where the second line follows from EP [(X j (γuj 1 − γuj 2 ))2 ] . kγuj 1 − γuj 2 k2 .
EP [fu22 (X j (γuj 1 − γuj 2 ))2 ], which holds by Assumption 3.4, and the third line
follows from (H.2). Hence, (EP [fu22 (X j (γuj 1 − γuj 2 ))2 ])1/2 . |u2 − u1 |, and so
 h 
2 i1/2
(H.4)
kγuj 2 − γuj 1 k . EP fu22 X j (γuj 1 − γuj 2 )
. |u2 − u1 |.

Therefore,

kγuj 2 − γuj 1 k1 6

p

p + p̃kγuj 2 − γuj 1 k .

p

p + p̃|u2 − u1 |,

and so (H.1) follows.
Next, let
n
o
G1 = (Y, D, X) 7→ 1{Y 6 uȳ + (1 − u)y} : u ∈ U ,
o
n
G2 = (Y, D, X) 7→ EP [g(Y, D, X) | D, X] : g ∈ G1 ,
n
o
G3,j = (Y, D, X) 7→ Dj − X j γuj : u ∈ U , j ∈ [p̃].

Then the function class Fe = {ψuj (·, θuj , ηuj ) : u ∈ U , j ∈ [p̃]} satisfies
Fe ⊂ (G1 − G2 ) · (∪j∈[p̃] G3j ).

Observe that G1 is a VC-subgraph class with index bounded by C, and so
by Theorem 2.6.7 in [15], its uniform entropy numbers obey
(H.5)

sup log N (ǫkFe1 kQ,2 , G1 , k · kQ,2 ) 6 C log(C/ǫ),

for all 0 < ǫ 6 1,

Q

where Fe1 ≡ 1 is its envelope. In addition, Lemma N.2 implies that the
uniform entropy numbers of G2 obey the same inequalities with the same
envelope Fe1 (but possibly different constant C). Moreover, for any u ∈ U
and j ∈ [p̃], by Assumptions 3.1 and 3.2 and the triangle inequality,
p
p
√
kγuj k1 . kγ̄uj k1 + sn log an /n . sn kγ̄uj k + sn log an /n
p
√
√
. sn kγuj k + sn log an /n . sn ,
(H.6)

8

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

because by Assumption 3.4, sn log an /n = o(1). Therefore, (H.1) and Lemma
N.3 with k = 1 imply that for all j ∈ [p̃], the uniform entropy numbers of
G3,j obey
sup log N (ǫkFe3 kQ,2 , G3,j , k · kQ,2 ) 6 C log(an /ǫ),

for all 0 < ǫ 6 1,

Q

−1
where Fe3 (Y, D, X) = supu∈U ,j∈[p̃] |Zuj |+ Mn,2
(kDk∞ ∨ kXk∞ ) is its envelope,
and so Lemma N.1 gives that the uniform entropy numbers of ∪j∈[p̃] G3,j obey
the same inequalities with the same envelope Fe3 . Hence, Lemma N.1 also
shows that the uniform entropy numbers of Fe obey
e k · kQ,2 ) 6 C log(an /ǫ), for all 0 < ǫ 6 1,
(H.7) sup log N (ǫkFe kQ,2 , F,
Q

−1
where Fe (Y, D, X) = C{supu∈U ,j∈[p̃] |Zuj | + Mn,2
(kDk∞ ∨ kXk∞ )} is its envelope. Now observe that kFekP,q . Mn,1 and that kf kP,2 . 1 uniformly over
f ∈ Fe by Assumption 3.4. Therefore, it follows from Lemma O.2 that
h
i
√
sup
Sn = EP
nEn [ψuj (W, θuj , ηuj )]
u∈U ,j∈[p̃]

(an Mn,1 ) + n−1/2+1/q Mn,1 log(an Mn,1 )
p
. log1/2 (an Mn,1 )(1 + δn ) . log an ,
. log

1/2

where the last two inequalities follow from Assumption 3.4 and the facts
that δn = o(1) and that log Mn,1 . log n, which is another consequence
of Assumption 3.4. Hence, Assumption 3.1 implies that for all u ∈ U and
j ∈ [p̃], Θuj contains a ball of radius C0 n−1/2 Sn log n centered at θuj for all
sufficiently large n for any constant C0 . Therefore, Assumption 2.1(i) holds.
Next, Assumption 2.1(ii) follows from the observation that for all u ∈ U
and j ∈ [p̃], the map (θ, η) 7→ ψuj (W, θ, η) is twice continuously Gateauxdifferentiable on Θuj × Tuj , and so is the map (θ, η) 7→ EP [ψuj (W, θ, η)].
To verify the orthogonality condition in Assumption 2.1(iii), note that for
all u ∈ U , j ∈ [p̃], and η = (η (1) , η (2) , η (3) ) ∈ Tuj with η 6= ηuj , we have
i
h
Du,j,0 [η − ηuj ] = EP ru Zuj − Λ′ (Dj θuj + X j βuj )Zuj X j (η (2) − βuj ) ,

where we used the equality EP [{Yu − Λ(Dj θuj + X j βuj ) − ru }X j ] = 0. In
addition, |EP [ru Zuj ]| 6 δn n−1/2 by Assumption 3.5. Further, recall that
EP [fu2 Zuj X j ] = 0 and observe that
fu2 = fu2 (D, X) = Var(Yu | D, X) = EP [Yu | D, X](1 − EP [Yu | D, X])
= (Λ(D ′ θu + X ′ βu ) + ru )(1 − Λ(D ′ θu + X ′ βu ) − ru )

= Λ′ (D ′ θu + X ′ βu ) + ru − ru2 − 2ru Λ(D ′ θu + X ′ βu ),

9

POST-REGULARIZATION CONFIDENCE REGIONS

where we used the equality Λ′ (t) = Λ(t) − Λ2 (t), which holds for all t ∈ R.
Hence,
h
i
EP Λ′ (Dj θuj + X j βuj )Zuj X j (η (2) − βuj )
h
2 i1/2
i
 h
. EP (ru Zuj )2 · EP X j (η (2) − βuj )

1/2
. EP [ru2 ]
· kη (2) − βuj k . sn log an /n . δn n−1/2 ,

where the second line follows from the Cauchy-Schwarz inequality and the
observations that |ru | 6 1 and that |Λ(t)| 6 1 for all t ∈ R, and the third line
from Assumptions 3.4 and 3.5 (the last inequality holds because s2n log2 an 6
δn2 n by Assumption 3.4). Also, when η = ηuj , we have |Du,j,0 [η − ηuj ]| = 0,
and so Assumption 2.1(iii) holds.
Next, we verify Assumption 2.1(iv). Fix u ∈ U and j ∈ [p̃]. Observe that
i
h
Juj = −EP Λ′ (Dj θuj + X j βuj )Dj Zuj
i
h
i
h
= −EP fu2 Dj Zuj + EP (ru − ru2 − 2ru Λ(D ′ θu + X ′ βu ))Dj Zuj
i
h
i
h
= −EP fu2 |Zuj |2 + EP (ru − ru2 − 2ru Λ(D ′ θu + X ′ βu ))Dj Zuj .
Hence, by Assumptions 3.1, 3.4 and 3.5 and the Cauchy-Schwarz inequality,

1/2
|Juj | > c1 − 4 EP [ru2 ]EP [|Dj Zuj |2 ]
= c1 + o(1),

and also |Juj | . 1 uniformly over u ∈ U and j ∈ [p̃]. In addition,
o
1 n
EP [ψuj (W, θ, ηuj )] = Juj (θ − θuj ) + ∂θ2 EP [ψuj (W, θ, ηuj )]
2

θ=θ̄

(θ − θuj )2

for some θ̄ ∈ Θuj . Moreover, for all θ ∈ Θuj , we have |∂θ2 EP [ψuj (W, θ, ηuj )]| 6
EP [|Dj2 Zuj |] . 1 by Assumptions 3.1 and 3.4 since |Λ′′ (t)| 6 1 for all t ∈ R.
These inequalities together imply Assumption 2.1(iv).
Next, we verify Assumption 2.1(v) with ω = 2 and B1n = B2n = C
for sufficiently large C. Fix u ∈ U , j ∈ [p̃], r ∈ (0, 1], θ ∈ Θuj , and η =
(η (1) , η (2) , η (3) ) ∈ Tuj . We consider the case η 6= ηuj , and the other case is
similar. Denote
I1,1 = 2|X j (η (3) − γuj )| + |ru Zuj |,

I1,2 = Dj (θ − θuj ) + X j (η (2) − βuj ) · |Zuj |.

10

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Then
ψuj (W, θ, η) − ψuj (W, θuj , ηuj ) 6 I1,1 + I1,2 ,
since |Λ′ (t)| 6 1 for all t ∈ R. In addition,
EP [(ru Zuj )2 ] . EP [ru2 ] 6 kη − ηuj k2e ,

EP [(X j (η (3) − γuj ))2 ] . kη (3) − γuj k2 6 kη − ηuj k2e
2 ] . kη − η k2 . Also,
by Assumptions 3.5 and 3.4, respectively. Thus, EP [I1,1
uj e

i
h
i
h
2
EP [I1,2
] 6 EP (Zuj )2 · EP (Dj (θ − θuj ) + X j (η (2) − βuj ))2
i
h
. EP (Dj (θ − θuj ) + X j (η (2) − βuj ))2

. |θ − θuj |2 + kη (2) − βuj k2 . |θ − θuj |2 + kη − ηuj k2e ,

where the first line follows from the Cauchy-Schwarz inequality, the second from EP [(Zuj )2 ] . 1, and the third from Assumption 3.4. Therefore,
Assumption 2.1(v-a) holds.
To verify Assumption 2.1(v-b), observe that under our conditions,
h
i
h
i
∂r EP ψuj (W, θ, ηuj + r(η − ηuj )) = EP ∂r ψuj (W, θ, ηuj + r(η − ηuj )) .
Further, denote

xr = Dj θ + X j βuj + rX j (η (2) − βuj ),

I2,1 = −X j (η (3) − γuj )(Yu − Λ(xr ) − (1 − r)ru ),

I2,2 = ru (Zuj − rX j (η (3) − γuj )),

I2,3 = −Λ′ (xr )(Zuj − rX j (η (3) − γuj ))X j (η (2) − βuj ).
Then ∂r ψuj (W, θ, ηuj + r(η − ηuj )) = I2,1 + I2,2 + I2,3 , and so
h
i
EP ∂r ψuj (W, θ, ηuj + r(η − ηuj )) = EP [I2,1 ] + EP [I2,2 ] + EP [I2,3 ].
Now, observe that

i
h
EP [|I2,1 |] . EP |X j (η (3) − γuj )|
i1/2
 h
. kη − ηuj ke ,
. EP |X j (η (3) − γuj )|2

POST-REGULARIZATION CONFIDENCE REGIONS

11

where the first inequality holds since |ru | 6 1, the second by Jensen’s inequality, and the third by Assumption 3.4. Also, by the Cauchy-Schwarz
inequality,
i1/2
h

. kη − ηuj ke ,
EP [|I2,2 |] 6 EP [ru2 ] · EP (Zuj − rX j (η (3) − γuj ))2

where the second inequality follows from (EP [ru2 ])1/2 6 kη−ηuj ke . Moreover,
since |Λ′ (t)| 6 1 for all t ∈ R, the Cauchy-Schwarz inequality gives
i
 h
EP [|I2,3 |] . EP (Zuj − rX j (η (3) − γuj ))2
i1/2
h
. kη − ηuj ke .
× EP (X j (η (2) − βuj ))2

Therefore, Assumption 2.1(v-b) holds.
To verify Assumption 2.1(v-c), denote

I3,1 = −ru X j (η (3) − γuj ) + Λ′ (xr )X j (η (3) − γuj )X j (η (2) − βuj ),

I3,2 = −ru X j (η (3) − γuj ),

I3,3 = −Λ′′ (xr )(Zuj − rX j (η (3) − γuj ))(X j (η (2) − βuj ))2
+ Λ′ (xr )X j (η (3) − γuj )X j (η (2) − βuj ),

so that ∂r I2,1 = I3,1 , ∂r I2,2 = I3,2 , and ∂r I2,3 = I3,3 . Now, observe that since
|Λ′ (t)| 6 1 for all t ∈ R,
p
EP [|I3,1 |] . EP [ru2 ]kη (3) − γuj k + kη (3) − γuj kkη (2) − βuj k . kη − ηuj k2e

by the Cauchy-Schwarz inequality, the triangle inequality, and Assumptions
3.1 and 3.4. Similarly, EP [|I3,2 |] . kη − ηuj k2e . In addition, since |Λ′′ (t)| 6 1
for all t ∈ R,
EP [|I3,3 |] . kη −

ηuj k2e

i1/2
 h
j (2)
j 4
. kη − ηuj k2e
+ EP (X (η − βu ))

by the arguments used above, the Cauchy-Schwarz inequality, and Assumption 3.4. Also, the terms in EP [∂r2 ψuj (W, θuj + r(θ − θuj ), ηuj + r(η − ηuj ))]
arising from differentiation of θuj + r(θ − θuj ) can be bounded similarly.
Therefore, Assumption 2.1(v-c) holds.
Next, we verify Assumption 2.2(i). Observe that by Theorems 4.1 and
4.2, with probability 1 − o(1),

 p


sup kθeu − θu k + kβeu − βu k . sn log an /n, sup kθeu k0 + kβeu k0 . sn ,
u∈U

u∈U

12

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

sup
u∈U ,j∈[p̃]

ke
γuj − γuj k .

p

sn log an /n, and

sup
u∈U ,j∈[p̃]

ke
γuj k0 . sn .

′
In addition, βbuj = (θeu[p̃]\j
, βeu′ )′ , and so uniformly over u ∈ U and j ∈ [p̃],
with probability 1 − o(1),
p
kβbuj − βuj k . sn log an /n and kβbuj k0 . sn .

Moreover, uniformly over u ∈ U and j ∈ [p̃], with probability 1 − o(1),
p
ke
γuj − γuj k1 6 ke
γuj − γ̄uj k1 + kγ̄uj − γuj k1 . ke
γuj − γ̄uj k1 + sn log an /n
p
p
√
γuj − γ̄uj k + sn log an /n . sn log an /n
. sn ke

by Assumption 3.2 and the triangle and the Cauchy-Schwarz inequalities.
Therefore, Assumption 2.2(i) holds. In addition, Assumption 2.2(ii) holds by
construction of Tuj and since EP [ru2 ] 6 C1 sn log an /n, which in turn follows
from Assumption 3.5. Also, Assumption 2.2(iii) holds by construction of Tuj .
Next, we establish the entropy bound of Assumption 2.2(iv) with vn =
Csn and Kn = CMn,1 for sufficiently large constant C > 0 (recall that
an = p ∨ p̃ ∨ n). Let
n
o
G4 = (Y, D, X) 7→ (D ′ , X ′ )ξ : ξ ∈ Rp̃+p , kξk0 6 Csn , kξk 6 C ,
n
o
G5,j = (Y, D, X) 7→ ξDj + X j βuj : u ∈ U , |ξ| 6 C , j ∈ [p̃],

for sufficiently large C. Moreover, recall that W = (Y, D, X) and let
o
n
F1,1 = W 7→ ψuj (W, θ, η) : u ∈ U , j ∈ [p̃], θ ∈ Θuj , η ∈ Tuj \ ηuj ,
o
n
F1,2 = W 7→ ψuj (W, θ, ηuj ) : u ∈ U , j ∈ [p̃], θ ∈ Θuj .

Then F1 = F1,1 ∪ F1,2 and

F1,1 ⊂ (G1 − Λ(G4 )) · G4 ,

F1,2 ⊂ (G1 − G2 + Λ(∪j∈[p̃] G5,j ) − Λ(∪j∈[p̃] G5,j )) · (∪j∈[p̃] G3,j ),

where G1 , G2 , and G3,j , j ∈ [p̃], are defined above, because ψuj (W, θ, ηuj ) =
{1{Y 6 uȳ + (1 − u)y} − ru − Λ(Dj θ + X j βuj )}Zuj . A bound for the uniform
entropy
 numbers of G1 is established above in (H.5). Also, G4 is a union over
p+p̃
Csn VC-subgraph classes with indices O(sn ), and so is Λ(G4 ). Hence, by
Lemma N.1,
sup log N (ǫkFe1,1 kQ,2 , F1,1 , k · kQ,2 ) 6 Csn log(an /ǫ),
Q

for all 0 < ǫ 6 1,

POST-REGULARIZATION CONFIDENCE REGIONS

13

where
Fe1,1 (W ) =

sup

sup

u∈U ,j∈[p̃] γ∈Rp̃−1+p : kγ−γuj k1 6C √sn τn



2|Dj − X j γ|

is an envelope of F1,1 . Observe that |Dj −X j γ| 6 |Dj −X j γuj |+|X j (γ−γuj )| 6
√
supu∈U ,j∈[p̃] |Zuj | + kXk∞ C sn τn , and so
kFe1,1 kP,q . Mn,1 +

√

sn τn Mn,2 . Mn,1

√
by Assumption 3.4 (observe that sn τn Mn,2 . 1 and Mn,1 > 1).
Next we turn to F1,2 . Bounds for the uniform entropy numbers of G2 and
∪j∈[p̃] G3,j are established above. Consider G5,j for j ∈ [p̃]. Note that for all
u1 , u2 ∈ U ,
p
√
kγuj 2 − γuj 1 k1 . p + p̃|u2 − u1 |, kγuj 1 k1 . sn ,
 p

kβuj 2 − βuj 1 k1 . kθu2 − θu1 k1 + kβu2 − βu1 k1 . p + p̃|u2 − u1 |
by (H.1), (H.6), and Assumption 3.1. Therefore, for all ξ1 , ξ2 ∈ R such that
|ξ1 | 6 C and |ξ2 | 6 C, and all u1 , u2 ∈ U ,
(ξ2 , βuj 2 ) − (ξ1 , βuj 1 )

1

6 |ξ2 − ξ1 | + kβuj 2 − βuj 1 k1
p
. |ξ2 − ξ1 | + p + p̃|u2 − u1 |.

Hence, Lemma N.3 implies that for all j ∈ [p̃], the uniform entropy numbers
of Λ(G5,j ) obey
sup log N (ǫkFe5 kQ,2 , Λ(G5,j ), k · kQ,2 ) 6 C log(an /ǫ),

for all 0 < ǫ 6 1,

Q

−1
where Fe5 (Y, D, X) = 1 + Mn,2
(kDk∞ ∨ kXk∞ ) is its envelope. Hence, by
Lemma N.1,

sup log N (ǫkFe1,2 kQ,2 , F1,2 , k · kQ,2 ) 6 C log(an /ǫ),

for all 0 < ǫ 6 1,

Q

where

−1
Fe1,2 (W ) = C(1 + Mn,2
(kDk∞ ∨ kXk∞ ))


−1
×
sup |Zuj | + Mn,2
(kDk∞ ∨ kXk∞ )
u∈U j∈[p̃]

14

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

is an envelope of F1,2 that satisfies kFe1,2 kP,q . Mn,1 by Assumption 3.4 and
the Cauchy-Schwarz inequality. Applying Lemma N.1 one more time finally
shows that the uniform entropy numbers of F1 obey (2.4) with constants
specified above and with an envelope F1 = Fe1,1 ∨ Fe1,2 satisfying kF1 kP,q .
Mn,1 .
Next, we verify Assumption 2.2(v). Fix u ∈ U , j ∈ [p̃], θ ∈ Θuj , and
η = (η (1) , η (2) , η (3) ) ∈ Tuj . Then
EP [ψuj (W, θ, η)2 ]
2
i

i

h h
= EP EP Yu − Λ Dj θ + X j η (2) − η (1) | D, X (Dj − X j η (3) )2
> EP [fu2 (Dj − X j η (3) )2 ] > c,

where the first inequality follows from the fact that for any random variable
ξ, the function x 7→ E[(ξ − x)2 ] is minimized at x = E[ξ] and in this case
fu2 = Var(Yu | D, X), and the second inequality follows from Assumption
3.4. In addition,
EP [ψuj (W, θ, η)2 ] 6 EP [(Dj − X j η (3) )2 ] . 1
by Assumptions 3.1 and 3.4. Therefore, Assumption 2.2(v) holds.
Finally, we verify Assumption 2.2(vi). The condition (a) holds by construction of τn and vn . To verify the condition (b) observe that
(B1n τn )ω/2 (vn log an )1/2 + n−1/2+1/q vn Kn log an
. n−1/2 sn log an + n−1/2+1/q sn Mn,1 log an . δn
by Assumption 3.4. In addition,
√
√
√
(Sn log n/ n)ω/2 (vn log an )1/2 . sn (log an ) · (log n)/ n . δn ,
since Sn . (log an )1/2 , which is established above, and sn log an 6 δn n1/2−1/q ,
which holds by Assumption 3.4. The condition (b) follows. The condition
(c) holds because
2
n1/2 B1n
B2n τn2 . n−1/2 sn log an . δn

as in the verification of the condition (b). This completes the verification of

Assumptions 2.1 and 2.2 and thus completes the proof of the theorem.

POST-REGULARIZATION CONFIDENCE REGIONS

15

Proof of Corollary 3.1. The asserted claim will follow from Corollary
2.1 as long as we can verify its conditions. Assumptions 2.1 and 2.2 were verified in the proof of Theorem 3.1. Therefore, it suffices to verify Assumption
2.3(i,ii) and the growth conditions of Corollary 2.1.
First, we verify Assumption 2.3(i). Recall the function class
Fe = {ψuj (·, θuj , ηuj ) : u ∈ U , j ∈ [p̃]}

defined in the proof of Theorem 3.1, where it is also proven that its uniform
entropy numbers obey (H.7) with an envelope Fe satisfying kFekP,q . Mn,1 .
Also, note that Assumption 2.1(iv) gives 1 . |Juj | . 1 for all u ∈ U and
2 (W, θ , η )] . 1 for
j ∈ [p̃], and that Assumption 2.2(v) gives 1 . EP [ψuj
uj uj
all u ∈ U and j ∈ [p̃]. Hence,
n
o
e ξ ∈ R, c 6 |ξ| 6 C ,
F0 ⊂ ξ · f : f ∈ F,

and so Lemma N.1 implies that the uniform entropy numbers of F0 obey
(H.8)

sup log N (ǫkF0 kQ,2 , F0 , k · kQ,2 ) 6 C log(an /ǫ),

for all 0 < ǫ 6 1,

Q

where its envelope F0 satisfies kF0 kP,q . Mn,1 . Thus, Assumption 2.3(i)
holds with ̺n = C, An = an = p ∨ p̃ ∨ n, and Ln = CMn,1 .
Next, we verify Assumption 2.3(ii). For k = 3, 4, u ∈ U , and j ∈ [p̃], we
have
i
h
i
h
EP |ψ̄uj (W, θuj , ηuj )|k . EP |Dj − X j γuj |k . 1

by Assumptions 3.1 and 3.4 since |Yu | 6 1, |Λ(t)| 6 1 for all t ∈ R, and
|ru | 6 1. Thus, Assumption 2.3(ii) holds with the same Ln = CMn,1 since
Mn,1 > 1.
Finally, with our choice of An and ̺n , the growth conditions of Corollary
2.1 hold by assumption. This completes the proof.

Proof of Corollary 3.2. The asserted claim will follow from Corollary
2.2 as long as we can verify its conditions. Assumptions 2.1 and 2.2 were
verified in the proof of Theorem 3.1. Assumption 2.3(i,ii) was verified in the
proof of Corollary 3.1. Therefore, it suffices to verify Assumptions 2.3(iii)
and 2.4 and the growth conditions of Corollary 2.2.
We split the proof into six steps. In Steps 1-3, we verify Assumption 2.4.
In Steps 4 and 5, we verify Assumption 2.3(iii). In Step 6, we verify the
growth conditions of Corollary 2.2.
Step 1. Here we show that
Jbuj − Juj = oP (log−1 an )

16

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

uniformly over u ∈ U and j ∈ [p̃]. For θ ∈ R, β ∈ Rp̃−1+p , γ ∈ Rp̃−1+p , and
j ∈ [p̃], define


ψej (W, θ, β, γ) = −Λ′ Dj θ + X j β Dj (Dj − X j γ),
m
e j (θ, β, γ) = EP [ψej (W, θ, β, γ)].

Then Jbuj = En [ψej (W, θeuj , βbuj , γeuj )] and Juj = m
e j (θuj , βuj , γuj ) for all u ∈ U
and j ∈ [p̃]. Therefore, by the triangle inequality,
|Jbuj − Juj | 6 Jbuj − m
e j (θeuj , βbuj , γ
euj ) + m
e j (θeuj , βbuj , γeuj ) − m
e j (θuj , βuj , γuj ) .

Define



n
G6 = (Y, D, X) 7→ −Λ′ Dj θ + X j η (2) Dj (Dj − X j η (3) ) :

o
u ∈ U , j ∈ [p̃], θ ∈ Θuj , η = (η (1) , η (2) , η (3) ) ∈ Tuj \ ηuj .

Then by Assumption 2.2(i), with probability 1 − o(1),

Jbuj − m
e j (θeuj , βbuj , γ
euj ) 6 sup En [f (W )] − EP [f (W )]
f ∈G6

for all u ∈ U and j ∈ [p̃]. In addition, G6 ⊂ −Λ′ (G4 ) · G42 , where the function
class G4 is introduced in the proof of Theorem 3.1. Moreover,


Dj θ + X j η (2) . kDk∞ ∨ kXk∞ kη (2) k1




p
p
. p + p̃ kDk∞ ∨ kXk∞ kη (2) k . p + p̃ kDk∞ ∨ kXk∞

uniformly over u ∈ U , j ∈ [p̃], θ ∈ Θuj , and η = (η (1) , η (2) , η (3) ) = Tuj \
ηuj by Assumptions 3.1. Hence, applying Lemmas N.1 and N.4 with K =
Mn,2 n2/q (p + p̃)1/2 shows that the uniform entropy numbers of G6 obey
sup log N (ǫkF6 kQ,2 , G6 , k · kQ,2 ) 6 Csn log(an /ǫ),

for all 0 < ǫ 6 1

Q

where F6 (W ) = (1 + (kDk∞ ∨ kXk∞ )/(Mn,2 n2/q ))kDk∞ Fe1,1 (W ) is its envelope, and Fe1,1 is defined in the proof of Theorem 3.1. Also, recall that

POST-REGULARIZATION CONFIDENCE REGIONS

17

kFe1,1 kP,q . Mn,1 , which is established in the proof of Theorem 3.1, and so
i4/q
 h
EP max |F6 (Wi )|q/4
16i6n

i4/q
 h
q/4
e
6 EP max |kDi kq/4
∞ F1,1 (Wi )|
16i6n



h

i4/q
(kDi k∞ ∨ kXi k∞ )q/2 e
q/4
|
F
(W
)|
1,1
i
16i6n
(Mn,2 n2/q )q/4
i2/q
h
 h (kDk ∨ kXk )q i
∞
∞
2
2
e1,1 (W )|q/2
. n2/q Mn,1
,
|
F
·
E
. n2/q Mn,1
+ n4/q EP
P
(Mn,2 n2/q )q/2
+ EP

max

where the first line follows from the triangle inequality, and the second from
the Cauchy-Schwarz inequality and Assumption 3.4. In addition, kf kP,2 . 1
for all f ∈ G6 . Hence, Lemma O.2 implies that
r
2 s log a
sn log an Mn,1
n
n
= o(log−1 an )
sup En [f (W )] − EP [f (W )] .
+
1−2/q
n
n
f ∈G6
with probability 1 − o(1) by Assumption 3.4 and the growth condition
sn log3 an /n = o(1).
Next, using the same arguments as those used to verify Assumption 2.1(va) in Theorem 3.1 shows that
m
e j (θeuj , βbuj , γ
euj ) − m
e j (θuj , βuj , γuj ) . kθeuj − θuj k + kβbuj − βuj k + ke
γuj − γuj k

and the right-hand of this inequality is bounded above by (Csn log an /n)1/2
uniformly over u ∈ U and j ∈ [p̃] with probability 1 − o(1), as demostrated
in the proof of Theorem 3.1. In turns, (Csn log an /n)1/2 = o(log−1 an ) by
assumption. Combining presented bounds gives the claim of this step.
Step 2. Here we show that
2
2
En [ψuj
(W, θeuj , ηbuj )] − EP [ψuj
(W, θuj , ηuj )] = oP (log−1 an )

uniformly over u ∈ U and j ∈ [p̃]. The proof of this claim is similar to
that in Step 1, where the main difference is that instead of −Λ′ (·) in the
function class G6 , we set Yu2 − 2Yu Λ(·) + Λ2 (·), with the resulting function
class having the same envelope and its uniform entropy numbers obeying
the same bounds as those derived fo G6 (up to possibly different constants).
Step 3. Here we finish the verification of Assumption 2.4. Observe that
2 (W, θ , η )] . 1 for all u ∈ U and j ∈ [p̃] by
1 . Juj . 1 and 1 . EP [ψuj
uj uj

18

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

2 . 1, and so
Assumptions 2.1(iv) and 2.2(v). Hence, 1 . σuj
2
σ
buj
σ
buj
2
2
−1 6 2 −1 . σ
buj
− σuj
σuj
σuj

−2
−2
2
En [ψuj
(W, θeuj , ηbuj )]
6 Jbuj
− Juj

−2
2
2
En [ψuj
(W, θeuj , ηbuj )] − EP [ψuj
(W, θuj , ηuj )]
+ Juj

2
2
(W, θeuj , ηbuj )] − EP [ψuj
(W, θuj , ηuj )] = oP (log−1 an )
. Jbuj − Juj + En [ψuj

uniformly over u ∈ U and j ∈ [p̃] by Steps 1 and 2. Therefore, Assumption
2.4 holds for some εn and ∆n satisfying εn log an = o(1) and ∆n = o(1).
Step 4. Here we show that the inequality concerning the entropy numbers
of Fb0 in Assumption 2.3(iii) holds with ̺¯n = C, Ān = an = p ∨ p̃ ∨ n, and
∆n = o(1). By construction of ψbuj , the function class {ψbuj (·) : u ∈ U , j ∈ [p̃]}
contains at most np̃ functions (as u varies, new functions appear only as u
crosses one of the observations (Yi )ni=1 ). Also, it follows from (H.8) in the
proof of Corollary 3.1 that the entropy numbers of F0 = {ψ̄uj (·) : u ∈ U , j ∈
[p̃]} obey
N (ǫ, F0 , k · kPn,2 ) 6 C log(an kF0 kPn,2 /ǫ) 6 C log(an /ǫ),

for all 0 < ǫ 6 1,

with probability 1 − o(1). Hence,
log N (ǫ, Fb0 , k · kPn,2 ) 6 C log(an /ǫ),

for all 0 < ǫ 6 1

with probability 1 − o(1). The claim of this step follows.
Step 5. Here we show that the second part of Assumption 2.3(iii), that is,
that with probability 1 − ∆n , we have kf kPn,2 6 δ̄n for all f ∈ Fb0 , holds for
some δ̄n and ∆n satisfying δ̄n = o(log−1 an ) and ∆n = o(1). By the triangle
inequality,
−1 b−1
−1 −1
σ
buj
Juj ψuj (W, θ̌uj , ηbuj ) − σuj
Juj ψuj (W, θuj , ηuj )

6

−1 b−1
|b
σuj
Juj

−

−1 −1
Juj |
σuj

· ψuj (W, θuj , ηuj )

Pn,2

Pn,2

−1 b−1
+σ
buj
Juj ψuj (W, θ̌uj , ηbuj ) − ψuj (W, θuj , ηuj )

Pn,2

.

We bound two terms on the right-hand side of this inequality in turn. To
bound the first term, observe that
−1 −1
−1 b−1
Juj | = oP (log−1 an )
|b
σuj
Juj − σuj

19

POST-REGULARIZATION CONFIDENCE REGIONS

uniformly over u ∈ U and j ∈ [p̃] by Steps 1 and 3 and since 1 . Juj . 1
and 1 . σuj . 1, which is discussed in Step 3. Also, as established in
the proof of Theorem 3.1, the uniform entropy numbers of the function
class Fe = {ψuj (·, θuj , ηuj ) : u ∈ U , j ∈ [p̃]} obey (H.7) with an envelope Fe
satisfying kFekP,q . Mn,1 . Moveover, EP [f 2 (W )] . 1 uniformly over f ∈ Fe
by Assumption 2.2(v). Therefore, Lemma O.3 shows that
h
i
2
sup En [ψuj
(W, θuj , ηuj )]
EP
u∈U ,j∈[p̃]

. 1 + n−1/2+1/q Mn,1

p

log an + n−1/2+1/q Mn,1 log an

2
. 1 + n−1+2/q Mn,1
log an . 1,



where the second inequality follows from Assumption 3.4. Hence,
−1 b−1
−1 −1
|b
σuj
Juj − σuj
Juj | · kψuj (W, θuj , ηuj )kPn,2 = oP (log−1 an )

uniformly over u ∈ U and j ∈ [p̃].
To bound the second term, define

n
G7 = ψuj (·, θ, η) − ψuj (·, θuj , ηuj ) : u ∈ U , j ∈ [p̃], θ ∈ Θuj ,
o
p
|θ − θuj | 6 Csn log an /n, η ∈ Tuj

for sufficiently large constant C > 0 and Tuj appearing in Assumption 2.2.
Then G7 ⊂ F1 − F1 , and so Lemma N.1 together with the bound for the
uniform entropy numbers of F1 established in the proof of Theorem 3.1
imply that the uniform entropy numbers of G7 obey
sup log N (ǫkF kQ,2 , G7 , k · kQ,2 ) 6 Csn log(an /ǫ),

for all 0 < ǫ 6 1,

Q

where F7 is its envelope satisfying kF7 kP,q . Mn,1 . In addition, Assumption
2.2(i) together with Step 1 in the proof of Theorem 2.1 imply that with
probability 1 − o(1),
ψuj (·, θ̌uj , ηbuj ) − ψuj (·, θuj , ηuj ) ∈ G7

for all u ∈ U and j ∈ [p̃] (recall that in the proof of Theorem 3.1, we
set B1n = C and τn = (Csn log an /n)1/2 ). Also, Assumptions 2.1(v-a) and
2.2(ii) show that EP [f 2 (W )] . sn log an /n uniformly over f ∈ G7 . Hence, it

20

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

follows from Lemma O.3 that
i
h
EP sup En [f 2 (W )]
f ∈G7

. sn log an /n + n−1/2+1/q Mn,1

p

sn log an + n−1/2+1/q Mn,1 sn log an

2
. n−1+2/q Mn,1
sn log an = o(log−1 an ).



Hence,
−1 b−1
σ
buj
Juj kψuj (W, θ̌uj , ηbuj ) − ψuj (W, θuj , ηuj )kPn,2 = oP (log−1 an )

uniformly over u ∈ U and j ∈ [p̃] by Assumption 3.4. Combining presented
bounds gives the asserted claim and completes the verification of Assumption
2.3.
Step 6. Recall that the growth conditions of Corollary 2.1 were verified
in the proof of Corollary 3.1, where we set ̺n = C and An = an . The other
growth conditions of Corollary 2.2, εn ̺n log An = o(1) and δ̄n2 ̺¯n ̺n (log Ān ) ·
(log An ) = o(1) hold because we have εn = o(log−1 an ), ̺¯n = C, Ān = an ,
and δ̄n = o(log−1 an ). This completes the proof of the corollary.

Proof of Corollary 3.3. To prove the asserted claim, we will apply Corollary 3.2. Below we will verify Assumptions 3.4(iii,v,vi,vii,viii,ix),
3.5(iii), and the growth conditions of Corollary 3.2.
Set
i1/(2q)
 h
and C̄n := 1 + sup kγuj k1
M̄n = EP (kDk∞ ∨ kXk∞ )2q
u∈U ,j∈[p̃]

so that M̄n 6 C1 and C̄n 6 1+ C1 by assumption. Observe that for all u ∈ U
and j ∈ [p̃],
|Zuj | = |Dj − X j γuj | 6 (kDk∞ ∨ kXk∞ ) · (1 + kγuj k1 ) . C̄n (kDk∞ ∨ kXk∞ )
Then
i1/3

1/3
 h
max EP [|Zuj Xkj |3 ]
. C̄n M̄n2 . 1.
. C̄n EP (kDk∞ ∨ kXk∞ )6
j,k

Therefore, given that log6 an = o(n) by assumption, it follows that Assumption 3.4(iii) holds for some δn satisfying δn2 log an = o(1).
Also,
#!1/(2q)
"
EP

sup

u∈U ,j∈[p̃]

|Zuj |2q

. C̄n M̄n . 1,

POST-REGULARIZATION CONFIDENCE REGIONS

21

and so Assumption 3.4(v) holds with Mn,1 = C for sufficiently large constant
C. In addition, since s2n log3 an = o(n1−2/q ), Assumption 3.4(vi) holds for
some δn satisfying δn2 log an = o(1).
Further, Assumption 3.4(vii) holds with Mn,2 = M̄n by definition of M̄n .
In addition, since s2n log2 an = o(n1−2/q ), Assumption 3.4(viii) holds for some
δn satisfying δn2 log an = o(1). Also, Assumption 3.4(ix) holds for some δn satisfying δn2 log an = o(1) since Mn,2 = M̄n 6 C1 , Mn,1 6 C, sn 6 δn n1/2−1/q ,
and q > 4.
Moreover, since supu∈U ,j∈[p̃] |EP [ru Zuj ]| = o((n log an )−1/2 ), Assumption
3.5(iii) holds for some δn satisfying δn2 log an = o(1). Finally, the growth
2/7
2/3
conditions Mn,1 log an = o(n1/7 ) and Mn,1 log an = o(n1/3−2/(3q) ) hold because Mn,1 . C̄n M̄n . C, log7 an = o(n), and log3 an = o(n1−2/q ).
Thus, there exists δn such that Assumptions 3.4(iii,v,vi,vii,viii,ix) and
3.5(iii) as well as all growth conditions of Corollary 3.2 are satisfied. Since
all other conditions of Corollary 3.2 are assumed, the asserted claim follows

from that in Corollary 3.2.
APPENDIX I: PROOFS FOR SECTION 4
In this appendix, we use C to denote a strictly positive constant that
is independent of n and P ∈ Pn . The value of C may change at each appearance. Also, the notation an . bn means that an 6 Cbn for all n and
some C. The notation an & bn means that bn . an . Moreover, the notation
an = o(1) means that there exists a sequence (bn )n>1 of positive numbers
such that (i) |an | 6 bn for all n, (ii) bn is independent of P ∈ Pn for all
n, and (iii) bn → 0 as n → ∞. Finally, the notation an .P bn means that
for any ǫ > 0, there exists C such that PP (an > Cbn ) 6 ǫ for all n, and
the notation an &P bn means that bn .P an . Using this notation allows us
to avoid repeating “uniformly over P ∈ Pn ” many times in the proofs of
Theorems 4.1 and 4.2.
Proof of Theorem 4.1. In this proof, we will rely upon results in
Appendix L. In particular, the asserted claims will follow from an application
of Lemmas L.1, L.2, and L.3 (with some extra work). To follow the notation
in Appendix L, define Xu = (D ′ , X ′ )′ and wu = fu2 and redefine θu =
(θu′ , βu′ )′ , θbu = (θbu′ , βbu′ )′ , and p = p̃ + p. Also, define au = au (Xu ) as a
solution to the following equation:
(I.1)

Λ(Xu′ θu ) + ru = Λ(Xu′ θu + au ).

22

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Since Λ is increasing, for each value of Xu , au is uniquely defined. Then θu
satisfies (L.1) with



Mu (Yu , Xu , θ, a) = − 1{Yu = 1} log Λ(Xu′ θ + a(Xu ))


+ 1{Yu = 0} log 1 − Λ(Xu′ θ + a(Xu ))

for θ being a vector in Rp and a being a function of Xu . Similarly, θbu satisfies (L.2) where Mu (Yu , Xu , θ) = Mu (Yu , Xu , θ, O) and O = O(Xu ), the
identically zero function of Xu .
To apply Lemmas L.1, L.2, and L.3, we need to verify Assumption L.1.
In addition, one of the conditions in these lemmas is that (L.5) holds with
probability 1 − o(1). Verification of this condition will be done with the help
of Lemma L.4, which in turn relies upon Condition WL. Therefore, below
we also verify this condition.
We first verify Condition WL with ǫn = 1/n and Nn = n. Observe that
since U = [0, 1], we have for any ǫ ∈ (0, 1] that N (ǫ, U , dU ) 6 1/ǫ, and so ǫn
and Nn satisfy the inequality Nn > N (ǫn , U , dU ), which is the first requirement of Condition WL. Further, as in front of Condition WL in Appendix
L, let
Su = ∂θ Mu (Yu , Xu , θ, au )|θ=θu

Λ′ (Xu′ θu + au (Xu )) 
Λ′ (Xu′ θu + au (Xu ))
· Xu
−
1{Y
=
0}
= − 1{Yu = 1}
u
Λ(Xu′ θu + au (Xu ))
1 − Λ(Xu′ θu + au (Xu ))


= − 1{Yu = 1}(1 − Λ(Xu′ θu + au (Xu )) − 1{Yu = 0}(Λ(Xu′ θu + au (Xu )) · Xu


= − Yu − EP [Yu | Xu ] · Xu .

Then |Suk | 6 |Xuk |. In addition, since γ > 1/n, we have
p
p
Φ−1 (1 − γ/(2pNn )) . log(pn) . log an .

Also, since fu 6 1, Assumption 3.4(ii,iii) yields log1/2 an . δn n1/6 . Moreover,
Assumption 3.4(iv) yields (EP [|Suk |3 ])1/3 . 1 uniformly over u ∈ U and
k ∈ [p]. Therefore, Condition WL(i) holds for some ϕn satisfying ϕn . δn .
Assumption 3.4(i,iv) also implies that uniformly over u ∈ U and k ∈ [p],
(I.2)

EP [|Suk |2 ] 6 EP [|Xuk |2 ] . 1 and EP [|Suk |2 ] = EP [|fu Xuk |2 ] & 1,

and so Condition WL(ii) holds for some C and C̄ depending only on the
constants in Assumption 3.4.
To verify Condition WL(iii), we apply Lemma L.5. Observe that Yu =
1{Y 6 (1 − u)y + uȳ} and the class of functions {H(·, u) : u ∈ U } with

POST-REGULARIZATION CONFIDENCE REGIONS

23

H(y, u) = 1{y 6 (1 − u)y + uȳ} is VC-subgraph with index bounded by
some C. Also, Xu does not depend on u, and by Assumption 3.4(iv,vii,viii),
EP [|Xuk |4 ] . 1 uniformly over k ∈ [p] and
1/(2q)
(EP [kXu k2q
. (δn n1/2−1/q )1/2 .
∞ ])

Moreover, by Assumption 3.3, EP [|Yu − Yu′ |4 ] = |u − u′ | uniformly over
u, u′ ∈ U . Therefore, Lemma L.5 with 2q replacing q implies that Condition
WL(iii) holds with ∆n = (log n)−1 and some ϕn satisfying
1/2

δn log an log1/2 an
ϕn .
∨
= o(1),
n1/4
n1/4
where the last assertion follows from log1/2 an . δn n1/6 , established above,
and δn2 log4 an = o(n), which holds by δn2 log an = o(1).
Next we verify Assumption L.1. It is well-known that the function θ 7→
Mu (Yu , Xu , θ) is convex almost surely, which is the first requirement of
Assumption L.1. Further, let us verify Assumption L.1(b). By Condition
WL(iii), which was verified above, we have with probability 1 − o(1) that
2 ]| = o(1) uniformly over u ∈ U and k ∈ [p]. So, it follows from
|(En − EP )[Suk
2 ] = (1 − o(1))E [S 2 ]
(I.2) that with the same probability we have En [Suk
P uk
uniformly over u ∈ U and k ∈ [p], and so Assumption L.1(b) holds for some
b u such
∆n , ℓ, and L satisfying ∆n = o(1), ℓ = 1 − o(1), and L . 1 for any Ψ
that
2 ]6Ψ
b2 . 1
(1 − o(1))EP [Suk
ukk
(I.3)
with probability 1 − o(1) uniformly over u ∈ U and k ∈ [p].

Thus, it suffices to verify (I.3). In the case m̄ = 0, we have by Lemma
2 ] = (1 − o(1))E[X 2 ] with
O.2 and Assumption 3.4(i,iv,vii,viii) that En [Xuk
uk
probability 1 − o(1) uniformly over u ∈ U and k ∈ [p]. Thus, (I.3) holds since
in this case,
b 2 = 1 En [X 2 ] = 1 − o(1) EP [X 2 ] . 1
Ψ
ukk
uk
uk
4
4
2 ] > E[f 2 X 2 ] = E[S 2 ] (recall that f 2 6 1/4) with probability
and 4−1 E[Xuk
u
u uk
uk
1 − o(1) uniformly over u ∈ U and k ∈ [p].
To establish (I.3) for m̄ > 1, we proceed by induction. Assuming that (I.3)
holds when the number of loops in Algorithm 3 is m̄ − 1, we can complete
the proof of the theorem to show that kXu′ (θeu − θu )kPn ,2 . (sn log an /n)1/2
with probability 1 − o(1) uniformly over u ∈ U for m = m̄ − 1. Then for
m = m̄, we have by the triangle inequality that
1/2

2
|b
luk,m − lu0k | 6 En [Xuk
{Λ(Xu′ θu ) + ru − Λ(Xu′ θeu )}2 ]


6 kΛ(Xu′ θu ) − Λ(Xu′ θeu )kPn ,2 + kru kPn,2 · max kXui k∞ .P δn
16i6n

24

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

uniformly over u ∈ U and k ∈ [p] since max16i6n kXui k∞ .P n1/(2q) Mn,2
by Assumption 3.4(vii), kru kPn ,2 .P (sn log an /n)1/2 by Assumption 3.5(v),
n1/(2q) Mn,2 (sn log an /n)1/2 6 δn by Assumption 3.4(viii), and the fact that
2 ). Thus, (I.3)
Λ is 1-Lipschitz (observe that Mn,2 > 1, and so Mn,2 6 Mn,2
holds with the number of loops in Algorithm 3 being m̄. This completes
verification of Assumption L.1(b).
To verify Assumption L.1(a), note that for any δ ∈ Rp ,
{∂θ Mu (Yu , Xu , θu ) − ∂θ Mu (Yu , Xu , θu , au )}′ δ

= {Λ(Xu′ θu ) − Λ(Xu′ θu + au (Xu ))}Xu′ δ = −ru Xu′ δ,

and so
En [∂θ Mu (Yu , Xu , θu ) − ∂θ Mu (Yu , Xu , θu , au )]′ δ
√
√
√
6 kru / wu kPn ,2 k wu Xu′ δkPn ,2 6 Cn k wu Xu′ δkPn ,2
where the first inequality follows from the Cauchy-Schwarz inequality, and
¯ n for some Cn satisfying Cn .
the second holds with probability 1 − ∆
1/2
(sn log an /n)
by Assumption 3.5. Thus, Assumption L.1(a) follows for
¯ n = o(1).
given Cn and ∆n = ∆
To verify Assumption L.1(c), note that Lemma O.2 in [5] imply that for
any u ∈ U , Au ⊂ Rp , and δ ∈ Au ,

En [Mu (Yu , Xu , θu + δ)] − En [Mu (Yu , Xu , θu )] − En [∂θ Mu (Yu , Xu , θu )]′ δ

 √
 
√
√
√
+ 2kau / wu kPn,2 k wu Xu′ δkPn ,2 > k wu Xu′ δk2Pn ,2 ∧ q̄Au k wu Xu′ δkPn ,2 ,

where
(I.4)

q̄Au = inf

δ∈Au

(En [wu |Xu′ δ|2 ])3/2
.
En [wu |Xu′ δ|3 ]

√
Next, we bound kau / wu kPn ,2 . Fix some arbitrary value of Xu . Consider
the case that ru = ru (Xu ) > 0. Then au = au (Xu ) > 0, and so combining
the mean-value theorem and (I.1) shows that for some t ∈ (0, au ),
ru = au Λ′ (Xu′ θu + t).

Now, since the function Λ′ is unimodal,
Λ′ (Xu′ θu + t) > Λ′ (Xu′ θu ) ∧ Λ′ (Xu′ θu + au ).

Further, observe that Λ′ (Xu′ θu + au ) = fu2 and
Λ′ (Xu′ θu ) = Λ(Xu′ θu ) · (1 − Λ(Xu′ θu ))

= (Λ(Xu′ θu ) + ru − ru ) · (1 − Λ(Xu′ θu ) − ru + ru )
= fu2 − ru (1 − Λ(Xu′ θu )) + ru (Λ(Xu′ θu ) + ru )
> fu2 − ru + 2ru Λ(Xu′ θu ) > fu2 − ru .

POST-REGULARIZATION CONFIDENCE REGIONS

25

In addition, by Assumption 3.5, |ru | 6 fu2 /4, so that Λ′ (Xu′ θu ) > 3fu2 /4.
Thus,
|au | 6 4ru /(3fu2 ).

Similarly, the same inequality can be obtained in the case that ru = ru (Xu ) <
0. Conclude that
p
√
kau / wu kPn ,2 . kru /fu3 kPn ,2 . sn log an /n
¯ n uniformly over u ∈ U . Therefore, Assumption
with probability at least 1−∆
¯ n , Cn . (sn log an /n)1/2 and q̄Au
L.1(c) holds for any Au ⊂ Rp with ∆n = ∆
defined in (I.4).
Next, we apply Lemma L.1. We have to verify the condition on q̄Au required in the lemma. To do so, recall that Au = Au,1 ∪ Au,2 where
Au,1 = {δ : kδTc u k1 6 2c̃kδTu k1 },
o
n
b −1 k∞
√
3n ckΨ
u0
Cn k wu Xu′ δkPn ,2 .
Au,2 = δ : kδk1 6
λ ℓc − 1
Then q̄Au defined in (I.4) equals q̄Au,1 ∧ q̄Au,2 where q̄Au,1 and q̄Au,2 are defined
similarly. To bound q̄Au,1 , we have
1/2

1/2

En wu |Xu′ δ|2
En wu |Xu′ δ|2
&P inf
q̄Au,1 > inf
δ∈Au,1 n1/(2q) Mn,2 kδk1
δ∈Au,1 max16i6n kXui k∞ kδk1


1/2
En wu |Xu′ δ|2
κ̄2c̃
> 1/(2q)
> inf
√
√
δ∈Au,1 n1/(2q) Mn,2 (1 + 2c̃) sn kδTu k
n
Mn,2 (1 + 2c̃) sn

uniformly over u ∈ U by Assumption 3.4(viii) and definition of κ̄2c̃ . By
Lemma J.3, sparse eigenvalues of order ℓn sn , for some sequence ℓn → ∞,
are bounded away from zero and from above so that κ̄2c̃ is bounded away
from zero with probability 1 − o(1). Conclude that


1
1
sn log an 1/2
q̄Au,1 &P 1/(2q)
>
&
√
1/2
δn n
n
Mn,2 (1 + 2c̃) sn
δn n1/4
uniformly over u ∈ U where the second inequality holds by Assumption
3.4(viii) and the third by Assumption 3.4(vi) (when we apply Assumption
3.4(vi), we use the fact that Mn,1 & 1, which in turn follows from Assumption
3.4(i)). Next, to bound q̄Au,2 , we have

1/2

1/2
En wu |Xu′ δ|2
En wu |Xu′ δ|2
&P inf
q̄Au,2 > inf
δ∈Au,2 n1/(2q) Mn,2 kδk1
δ∈Au,2 max16i6n kXui k∞ kδk1
b −1 k−1
λ ℓc − 1 kΨ
λ
u0 ∞
>
&P
1/(2q)
1+1/(2q)
3nCn c n
Mn,2
Cn n
Mn,2

26

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

b −1 k∞ . 1 with probability 1 − o(1).
uniformly over u ∈ U since supu∈U kΨ
u0
√ −1
Substituting λ = c nΦ (1 − γ/(2pNn )) and Cn . (sn log an /n)1/2 gives
q̄Au,2 &P

1
1
&
√ > 1/2
n1/(2q) Mn,2 sn
δn n1/4



sn log an
δn n

1/2

uniformly over u ∈ U . Moreover,


L+

1
c



b u0 k∞
kΨ



√
λ sn
sn log an 1/2
+ 6c̃Cn .
nκ̄2c̃
n

b u0 k∞ . 1 with probability 1 − o(1). Hence, since δn = o(1),
since supu∈U kΨ
the condition on q̄Au required in Lemma L.1 is satisfied with probability
1 − o(1). In addition, note that (L.5) holds with probability 1 − o(1) by
Lemma L.4. Therefore, applying Lemma L.1 gives
(I.5)
√
k wu Xu′ (θbu − θu )kPn ,2 . (sn log an /n)1/2 and kθbu − θu k1 . (s2n log an /n)1/2

with probability 1 − o(1) uniformly over u ∈ U .
The second inequality in (I.5) gives the second inequality in the first
asserted claim of the theorem. To transform the first inequality in (I.5) into
the first inequality in the first asserted claim of the theorem (and also to
prove other claims), we apply Lemma L.2. We have to verify (L.6). To do
so, note that
′ b
sup max |Xui
(θu − θu )| .P n1/(2q) Mn,2 kθbu − θu k1

u∈U 16i6n

2
. {n−1+1/q Mn,2
s2n log an }1/2 . δn = o(1)

by Assumption 3.4(vii, viii) and since Mn,2 > 1. Also, note that uniformly
over t and ∆t in R with |∆t| 6 1, we have
et+∆t
et
|et+∆t − et |
−
=
1 + et+∆t 1 + et
(1 + et+∆t )(1 + et )
t
t
∆t
e |e∆t − 1|
e |e − 1|
.
. Λ′ (t)∆t.
=
(1 + et+∆t )(1 + et )
(1 + et )2

|Λ(t + ∆t) − Λ(t)| =
(I.6)

Thus, with probability 1 − o(1),
|[∂θ Mu (Yui , Xui , θbu ) − ∂θ Mu (Yui , Xui , θu )]′ δ|
′ b
′
′
′
′ b
′
= |Λ(Xui
θu ) − Λ(Xui
θu )| · |Xui
δ| . Λ′ (Xui
θu ) · |Xui
(θu − θu )| · |Xui
δ|

27

POST-REGULARIZATION CONFIDENCE REGIONS

uniformly over i = 1, . . . , n and u ∈ U . Also, since |ru | 6 wu /4 by Assumption 3.5 and wu = fu2 6 1,
√
′
2
′
2
2
Λ′ (Xui
θu ) = fui
−rui +2rui Λ(Xui
θu )+rui
6 wui +3|rui |+wui
6 3wui 6 3 wui ;
′ θ ) above in this proof. Therefore, for some
see the expression for Λ′ (Xui
u
constant C,

|En [∂θ Mu (Yu , Xu , θbu ) − ∂θ Mu (Yu , Xu , θu )]′ δ|
√
6 Ck wu X ′ (θbu − θu )kP ,2 kX ′ δkP ,2 6 Ln kX ′ δkP
u

n

u

n

u

n ,2

with probability 1 − o(1) uniformly over u ∈ U for some Ln satisfying Ln .
(sn log an /n)1/2 . Hence, since supu∈U φmax (ℓn sn , u) . 1 with probability 1 −
o(1) for some ℓn → ∞ sufficiently slowly by Lemma J.3, Lemma L.2 implies
that supu∈U kθbu k0 . sn with probability 1−o(1), which is the second asserted
claim of the theorem.
In turn, since supu∈U kθbu k0 . sn with probability 1 − o(1), Lemma J.3
also establishes that
√
√
k wu Xu′ (θbu − θu )kPn ,2 & k wu Xu′ (θbu − θu )kPP ,2 & kθbu − θu k

with probability 1 − o(1) uniformly over u ∈ U , where the inequality follows
from Assumption 3.4(i). Combining these inequalities with (I.5) gives the
first inequality in the first asserted claim of the theorem.
It remains to prove the claim about the estimators θeu . We apply Lemma
L.3. We have to verify the condition (L.7) on q̄Au required in the lemma. To
do so, we first bound q̄Au from below for Au = {δ ∈ Rp : kδk0 6 Cs} where
C is a constant such that sbu + sn 6 Csn with probability 1 − o(1) uniformly
over u ∈ U . We have

1/2

3/2
En wu |Xu′ δ|2
En wu |Xu′ δ|2
> inf
q̄Au = inf
′ δ|3 ]
δ∈Au max kXui k∞ kδk1
δ∈Au En [wu |Xu
16i6n


1/2
p
En wu |Xu′ δ|2
φmin (Csn , u)
log1/4 an
√
> inf
&
&P √
1/2
kδk0 6Csn max kXui k∞ Csn kδk2
sn n1/(2q) Mn,2
δn n1/4
16i6n

uniformly over u ∈ U , where the inequality preceding the last one follows
from Assumption 3.4(vii) and the definition of φmin (Csn , u), and the last
one follows from Assumption 3.4(viii) and the observation that by Lemma
J.3, inf u∈U φmin (Csn , u) is bounded away from zero with probability 1 − o(1)
uniformly over u ∈ U .

28

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Next we bound from above the right-hand side of (L.7). It follows by (L.8)
that uniformly over u ∈ U with probability 1 − o(1),
En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )] . sn log an /n

b u0 k∞ .
since λ/n . (log an /n)1/2 , kθbu −θu k1 . (s2n log an /n)1/2 , and supu∈U kΨ
1/2
1 with probability 1 − o(1). Furthermore, Cn . (sn log an /n)
and
b u0 k∞ kΨ
b −1 En [Su ]k∞ . λ/n
sup kEn [Su ]k∞ 6 sup kΨ
u0

u∈U

u∈U

with probability 1 − o(1) by the choice of λ; see Lemma L.4. Hence, it
follows that the right-hand side of (L.7) is bounded up to a constant by
(sn log an /n)1/2 with probability 1 − o(1) uniformly over u ∈ U . Also, since
s2n log an /n . 1 (see Assumption 3.4(viii) and recall that Mn,2 > 1) and
δn = o(1), the condition (L.7) on q̄Au required in Lemma L.3 holds with
probability 1 − o(1) uniformly over u ∈ U . Hence, Lemma L.3 implies that
√
k wu Xu (θeu − θu )kPn ,2 . (sn log an /n)1/2
with probability 1−o(1) uniformly over u ∈ U . Finally, as in the case of θbu ’s,
√
we also have k wu Xu (θeu − θu )kPn ,2 & kθeu − θu k with probability 1 − o(1)
uniformly over u ∈ U , which gives the last asserted claim and completes the
proof of the theorem.


Proof of Theorem 4.2. The strategy of this proof is similar to that
of Theorem 4.1. In particular, we will rely upon results in Appendix L with
U and p replaced by Ue = U × [p̃] and p̄ = p + p̃ − 1, respectively, where
′
for ũ = (u, j) ∈ Ue, we set Yũ = Dj , Xũ = (X j )′ = (D[p̃]\j
, X ′ )′ , θũ = γ̄uj ,
θbũ = γ
buj , θeũ = γ
euj , aũ = (fu , r̄uj ), r̄ũ = r̄uj = X j (γuj − γ̄uj ), and wũ = fbu2 .
e we have that θũ satisfies (L.1) where
Note that for all ũ ∈ U,
Mũ (Yũ , Xũ , θ, a) = 2−1 f 2 (Dj − X j θ − r)2

for θ being a vector in Rp̄ and a being a pair (f, r) of functions of D and
X. Similarly, θbũ satisfies (L.2) where Mũ (Yũ , Xũ , θ) = Mũ (Yũ , Xũ , θ, (fbu , O))
and O = O(D, X), the identically zero function of D and X.
We first verify Condition WL with
ǫn =

δn2
,
2 ∨ M2 )
n1/2+1/q (p + p̃)1/2 (Mn,1
n,2

Nn = pp̃2 n2 , and the following semi-metric dUe on Ue: for all ũ = (u, j)
and ũ′ = (u′ , j ′ ) in Ue, dUe (ũ, ũ′ ) = |u − u′ | if j = j ′ and dUe (ũ, ũ′ ) = 1

POST-REGULARIZATION CONFIDENCE REGIONS

29

otherwise. Observe that N (ǫ, Ue, dUe ) 6 p̃/ǫ for all ǫ > 0. Also, note that
2 ∨ M 2 6 δ n1/2−1/q by Assumption 3.4(vi,viii), and so
Mn,1
n
n,2
1/ǫn 6 n(p + p̃)1/2 /δn 6 n2 (p + p̃)1/2
since δn > 1/n by Assumption 3.4(i,vii,viii). Thus, ǫn and Nn satisfy the
inequality Nn > N (ǫn , Ue, dUe ), which is the first requirement of Condition
WL.
Next, we verify Condition WL(i). As in front of Condition WL in Appendix L, for ũ = (u, j), let
Sũ = Suj = ∂θ Mũ (Yũ , Xũ , θ, aũ )|θ=θũ
= −fu2 (Dj − X j γuj )(X j )′ = −fu2 Zuj (X j )′ .
p
Then the inequality Φ−1 (1 − t) . log(1/t), which holds uniformly over
t ∈ (0, 1/2), implies that
(EP [|Sũk |3 ])1/3 Φ−1 (1 − γ/2pNn ) . (EP [|Zuj Xkj |3 ])1/3 log1/2 an 6 δn n1/6
uniformly over ũ ∈ Ue and k ∈ [p̄], where the second inequality holds by
Assumption 3.4(iii). Hence, Condition WL(i) holds for some ϕn satisfying
ϕn . δn .
To verify Condition WL(ii), note that by Assumption 3.4(ii), we have
2 ] & 1 and
EP [Sũk
2
] 6 EP [|Zuj Xkj |2 ] 6 EP [|Zuj |4 + |Xkj |4 ] . 1
EP [Sũk

uniformly over ũ = (u, j) ∈ Ue and k ∈ [p̄] by Assumption 3.4(iv).
To verify Condition WL(iii), we use the decomposition
Sũk − Sũ′ k = −(fu2 − fu2′ )Zuj Xkj + fu2′ X j (γuj − γuj ′ )Xkj

e By (H.2) and (H.1) we have
for ũ = (u, j) and ũ′ = (u′ , j) in U.
p
(I.7)
|fu2 − fu2′ | . |u − u′ | and kγuj − γuj ′ k1 . p + p̃|u − u′ |

uniformly over u, u′ ∈ U and j ∈ [p̃]. Therefore, uniformly over ũ = (u, j)
and ũ′ = (u′ , j) in Ue such that |u − u′ | 6 ǫn , we have


p
|Sũk − Sũ′ k | . |Zuj |kX j k∞ + kX j k2∞ p + p̃ · |u − u′ |
 p

(I.8)
. |Zuj |2 + kX j k2∞ · p + p̃ǫn .

30

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Since
EP [

max

j 2
2
sup |Zui
| ] 6 n1/q Mn,1

16i6n,j∈[p̃] u∈U

and
EP [

max

16i6n,j∈[p̃]

2
kXij k2∞ ] 6 n1/q Mn,2

by Assumption 3.4(v,vii), we have by Markov’s inequality that with probability 1 − o(1),
sup
dUe

(ũ,ũ′ )6ǫ

n

max |En [Sũk − Sũ′ k ]| . δn n−1/2 .
k∈[p̄]

In addition, uniformly over ũ, ũ′ ∈ Ue with dUe (ũ, ũ′ ) 6 ǫn and k ∈ [p̄],


1/2 
1/2
2
− Sũ2′ k ]| 6 EP [(Sũk − Sũ′ k )2 ]
|EP [Sũk
· EP [(Sũk + Sũ′ k )2 ]
1/2

2
2
. (Mn,1
+ Mn,2
)(p + p̃)1/2 ǫn
. δn .

Further, let U ǫ denote a minimal ǫn -net for U . Using (I.7) and (I.8), we
obtain that with probability 1 − o(1),
sup

max

u∈U j∈[p̃],k∈[p̄]

2
|(En − EP )[Sujk
]| . sup

max

u∈U ǫ j∈[p̃],k∈[p̄]

2
|(En − EP )[Sujk
]| + δn .

To bound the first term on the right-hand side of this inequality, we apply
Lemma P.1 with Xui and p replaced by Sũi and p̄, respectively, and k = 1,
2 Z j (X j )′ for ũ = (u, j) ∈ U
e and i =
where Sũi = (Sũ1i , . . . , Sũ[p̄]i )′ = −fui
ui
i
1, . . . , n. With


2
2
K = EP max sup max Sujki
16i6n u∈U j∈[p̃],k∈[p̄]
#
"
6 EP

max

sup

16i6n u∈U ,j∈[p̃]

j 2
4
4
+ Mn,2
),
|Zui
| kXij k2∞ . n2/q (Mn,1

which holds by Assumption 3.4(v,vii), the lemma yields
maxǫ

max

u∈U j∈[p̃],k∈[p̄]

2
2
2
+ Mn,2
) log an
(En − EP )[Sujk
] .P n−1/2 n1/q (Mn,1

. δn log1/2 an = o(1)
by Assumption 3.4(vi) and (viii). Thus, Condition WL(iii) holds with some
∆n and ϕn satisfying ∆n = o(1) and ϕn = o(1).

POST-REGULARIZATION CONFIDENCE REGIONS

31

Next, we verify Assumption L.1. The function θ 7→ Mũ (Yũ , Xũ , θ) is convex almost surely, which is the first requirement of Assumption L.1. Further,
to verify Assumption L.1(a), note that


[∂θ Mu (Yu , X, θu ) − ∂θ Mu (Yu , X, θu , au )]′ δ = − fbu2 r̄uj + (fbu2 − fu2 )Zuj · X j δ,

so that by the Cauchy-Schwarz and triangle inequalities, since wu = fbu2 , we
have
|En [∂θ Mu (Yu , X, θu ) − ∂θ Mu (Yu , X, θu , au )]′ δ|
 √

6 kfbu r̄uj kPn ,2 + k(fbu2 − fu2 )Zuj /fbu kPn ,2 · k wu X j δkPn ,2 .

To bound supu∈U ,j∈[p̃] kfbu r̄uj kPn ,2 , note that fbu 6 1, and so Lemma J.1
shows that with probability 1 − o(1),
sup

u∈U ,j∈[p̃]

kfbu r̄uj kPn ,2 6

sup

u∈U ,j∈[p̃]

kr̄uj kPn ,2 . (sn log an /n)1/2 .

Also, by Lemma J.2, with probability 1 − o(1),
(I.9)

sup
u∈U ,j∈[p̃]

k(fbu2 − fu2 )Zuj /fbu kPn ,2 . (sn log an /n)1/2 .

Hence, Assumption L.1(a) holds for some ∆n and Cn satisfying ∆n = o(1)
and Cn . (sn log an /n)1/2 .
To prove Assumption L.1(b), as in Appendix L, for ũ = (u, j) ∈ Ue, let
b ũ0 = Ψ
b uj0 = diag({lũ0k , k ∈ [p̄]}) where lũ0k = luj0k = (En [S 2 ])1/2 ,
Ψ
ũk
k ∈ [p̄]. Note that by Condition WL(ii,iii), which is verified above,
b ũ0k . 1
1.Ψ

with probability 1 − o(1) uniformly over ũ ∈ Ue and k ∈ [p̄]. Now, suppose
that m̄ = 0 (even though Algorithm 4 requires m̄ > 1). Then uniformly over
u ∈ U , j ∈ [p̃], and k ∈ [p̄] with probability 1 − o(1),

1/2 
1/2
b
lujk,0 & En [fbu4 (Dj Xkj )2 ]
& En [fu4 (Dj Xkj )2 ]
&1

2 −f 2 | 6 f 2
where the second inequality follows from the observation that |fbui
ui
ui
with probability 1 − o(1) uniformly over i = 1, . . . , n and u ∈ U (see (J.1) in
the proof of Lemma J.2), and the third from the same derivations as those
used to obtain Condition WL(ii,iii). Also, uniformly over u ∈ U , j ∈ [p̃], and
k ∈ [p̄],
b
lujk,0 6 max kXij k∞ (En [Dj2 ])1/2 .P n1/(2q) Mn,2
16i6n

32

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

by Assumption 3.4(vii) since fbu 6 1. Therefore, Assumption L.1(b) holds
with some ∆n , L, and ℓ satisfying ∆n = o(1), L . n1/(2q) Mn,2 log1/2 an , and
ℓ & 1.
To establish Assumption L.1(b) for m̄ > 1, which is required by Algorithm
4, we proceed by induction. Assuming that Assumption L.1(b) holds with
some ∆n , ℓ, and L satisfying ∆n = o(1), ℓ & 1, and L . n1/(2q) Mn,2 log1/2 an
when the number of loops in Algorithm 4 is m̄−1, we can complete the proof
of the theorem to show that kfbu X j (e
γuj − γ̄uj )kPn ,2 . (L + 1)(sn log an /n)1/2
with probability 1 − o(1) uniformly over u ∈ U and j ∈ [p̃] for m = m̄ − 1.
Thus, by the triangle inequality,
(I.10)

kfbu X j (e
γuj − γuj )kPn ,2 . (L + 1)(s2n log an /n)1/2

with probability 1 − o(1) uniformly over u ∈ U and j ∈ [p̃] since
kfbu X j (γ̄uj − γuj )kPn ,2 6 kX j (γ̄uj − γuj )kPn ,2

6 max kXij k · kγ̄uj − γuj k1
16i6n

.P n1/(2q) Mn,2 (s2n log an /n)1/2
uniformly over u ∈ U and j ∈ [p̃]. Then for m = m̄, we have uniformly over
u ∈ U , j ∈ [p̃], and k ∈ [p̄],
1/2

euj )2 ]
En [fbu4 (Xkj )2 (Dj − X j γ

1/2
− En [fu4 (Xkj )2 (Dj − X j γuj )2 ]

1/2
γuj − γuj ))2 ]
6 En [fbu4 (Xkj )2 (X j (e

1/2
− En [(fbu2 − fu2 )2 (Xkj )2 (Dj − X j γuj )2 ]


. kfbu X j (e
γuj − γuj )kPn ,2 + k(fbu2 − fu2 )Zuj /fbu kPn ,2 · max kX j k∞

|b
lujk,m − luj0k | =

16i6n

1/(2q)

Mn,2 (s2n

.P n
log a2n /n)1/2 n1/(2q) Mn,2
2
= n−1/2+1/q Mn,2
sn log an . δn log1/2 an =

o(1),

where the first inequality follows from the triangle inequality and the observation that (fbu2 − fu2 )2 6 fu4 − fbu4 , the second from fbi 6 1 and fu 6 1, the
third from (I.9) and (I.10), and the last from Assumption 3.4(viii). Thus, for
m̄ > 1, Assumption L.1(b) holds for some ∆n , ℓ, and L satisfying ∆n = o(1),
ℓ & 1, and L . 1.
Further, Assumption L.1(c) holds with ∆n = 0 and q̄Aũ = ∞ for any Aũ

33

POST-REGULARIZATION CONFIDENCE REGIONS

since for any ũ = (u, j) ∈ Ue and δ ∈ Rp̄ , we have

En [Mũ (Yũ , Xũ , θũ + δ)] − En [Mũ (Yũ , Xũ , θũ )]
= −En [fb2 (Dj − X j γ̄ j )X j δ] + 2−1 En [(fbu X j δ)2 ]
u

and

u

√
2−1 En [(fbu X j δ)2 ] > En [fbu (X j δ)2 ] = k wu Xũ′ δkPn ,2

where we used fbu 6 1/2.
We are now ready to apply Lemma L.1. Observe that by Lemma L.4, λ
satisfies (L.5) with probability 1 − o(1). Also, as established in (J.1) in the
2 − f 2 | 6 f 2 /2 with probability 1 − o(1) uniformly
proof of Lemma J.2, |fbui
ui
ui
over i = 1, . . . , n and u ∈ U . Therefore, since Lemma J.3 implies that for
some ℓn satisfying ℓn → ∞,
1.

min

kfu Xũ′ δk2Pn ,2
kδk2

kδk0 6ℓn sn

6

kXũ′ δk2Pn ,2

max

kδk0 6ℓn sn

kδk2

.1

with probability 1 − o(1) uniformly over ũ ∈ Ue, it follows that κ̄2c̃ & 1 with
b ũ0 k∞ . 1 and sup e kΨ
b −1 k∞ .
probability 1 − o(1). In addition, supũ∈Ue kΨ
ũ0
ũ∈U
1 with probability 1 − o(1). Therefore, applying Lemma L.1 gives
(I.11) kfbu X j (b
γuj − γ̄uj )kPn ,2 . (sn log an /n)1/2 and kb
γuj − γ̄uj k1 . (s2n log an /n)1/2

with probability 1 − o(1) uniformly over u ∈ U and j ∈ [p̃].
The second inequality in (I.11) gives the second inequality in the first
asserted claim of the theorem. To transform the first inequality in (I.11)
into the first inequality in the first asserted claim of the theorem (and also
to prove other claims), we apply Lemma L.2. We have to verify (L.6). To do
so, note that for ũ = (u, j) ∈ Ue, we have
|[∂θ Mũ (Yũ , Xũ , θbũ ) − ∂θ Mũ (Yũ , Xũ , θũ )]′ δ| 6 |fbu X j (θbũ − θũ )| · |fbu X j δ|.

Therefore, by the Cauchy-Schwarz inequality and since fbu 6 1,

|En [∂θ Mũ (Yũ , Xũ , θbũ ) − ∂θ Mũ (Yũ , Xũ , θũ )]′ δ|
6 kfbu X j (b
γ j − γ̄ j )kP ,2 kfbu X j δkP ,2 6 Ln kX j δkP
u

u

n

n

n ,2

with probability 1−o(1) uniformly over ũ = (u, j) ∈ Ue for some Ln satisfying
Ln . (sn log an /n)1/2 . Thus, since supũ∈Ue φmax (ℓn sn , ũ) . 1 for some ℓn →
∞ with probability 1 − o(1) by Lemma J.3, it follows from Lemma L.2 that
supu∈U kb
γuj k0 . sn with probability 1 − o(1) uniformly over u ∈ U and
j ∈ [p̃], which is the second asserted claim of the theorem.

34

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

In turn, with probability 1 − o(1), uniformly over u ∈ U and j ∈ [p̃], we
have
kfbu X j (b
γuj − γ̄uj )kPn ,2 & kfu X j (b
γuj − γ̄uj )kPn ,2 & kb
γuj − γ̄uj k.

Combining these inequalities with (I.11) gives the first inequality in the first
asserted claim of the theorem.
It remains to prove the claim about the estimators γ
euj . We apply Lemma
L.3. The condition (L.7) on q̄Aũ required in the lemma holds almost surely
since q̄Aũ = ∞. Also, it follows from (L.8) that uniformly over u ∈ U and
j ∈ [p̃] with probability 1 − o(1),
En [Mũ (Yũ , Xũ , θeũ )] − En [Mũ (Yũ , Xũ , θũ )] . sn log an /n

since λ/n . (log an /n)1/2 , supu∈U ,j∈[p̃] kb
γuj − γ̄uj k1 . (s2n log an /n)1/2 , and
b uj0 k∞ . 1 with probability 1 − o(1). Furthermore, Cn .
supu∈U ,j∈[p̃] kΨ
1/2
(sn log an /n)
and
b ũ0 k∞ kΨ
b −1 En [Sũ ]k∞ . λ/n
sup kEn [Sũ ]k∞ 6 sup kΨ
ũ0

ũ∈Ue

ũ∈Ue

with probability 1 − o(1) by the choice of λ; see Lemma L.4. In addition,
uniformly over ũ ∈ Ue with probability 1 − o(1), we have sbũ + sn . sn and
φmin (Csn , ũ) & 1 for arbitrarily large C. Hence, by Lemma L.3,
√
γuj − γ̄uj )kPn ,2 . (sn log an /n)1/2
k wũ X j (e

with probability 1 − o(1) uniformly over u ∈ U and j ∈ [p̃]. Finally, as in the
√
case of b
γuj ’s, we also have k wũ X j (e
γuj −γ̄uj )kPn ,2 & ke
γuj −γ̄uj k with probability
1− o(1) uniformly over u ∈ U and j ∈ [p̃], which gives the last asserted claim
and completes the proof of the theorem.

APPENDIX J: AUXILIARY LEMMAS FOR PROOFS OF THEOREMS
4.1 AND 4.2
Lemma J.1 (Control of Approximation Error). Suppose that Assumptions 3.1 – 3.5 hold for all P ∈ Pn . Then for r̄uj = X j (γuj − γ̄uj ), we have
with probability 1 − o(1) that
sup
u∈U ,j∈[p̃]

uniformly over P ∈ Pn .

2
En [r̄uj
] . sn log an /n

POST-REGULARIZATION CONFIDENCE REGIONS

35

Lemma J.2 (Control of Estimated Weights and Score). Suppose that
Assumptions 3.1 – 3.5 hold for all P ∈ Pn . Then with probability 1 − o(1),
we have
sup k(fbu2 − fu2 )Zuj /fbu kPn ,2 . (sn log an /n)1/2
u∈U ,j∈[p̃]

uniformly over P ∈ Pn .

Lemma J.3 (Functional Sparse Eigenvalues). Suppose that Assumptions
3.1 – 3.5 hold for all P ∈ Pn . Then for ℓn → ∞ slowly enough, we have
sup

sup

u∈U kδk0 6ℓn sn ,kδk=1

|1 − kfu (D ′ , X ′ )δkPn ,2 /kfu (D ′ , X ′ )δkP,2 | = oP (1) and
sup

kδk0 6ℓn sn ,kδk=1

|1 − k(D ′ , X ′ )δkPn ,2 /k(D ′ , X ′ )δkP,2 | = oP (1)

uniformly over P ∈ Pn .
Proof of Lemma J.1. By Assumption 3.2, supu∈U maxj∈[p̃] kγ̄uj k0 6 sn
and


sup max kγ̄uj − γuj k + s−1/2
kγ̄uj − γuj k1 6 C1 (sn log an /n)1/2 .
n
u∈U j∈[p̃]

Also, by (H.4), we have kγuj − γuj ′ k 6 Lγ |u − u′ | for some constant Lγ uniformly over u, u′ ∈ U . By the triangle inequality,
sup
u∈U ,j∈[p̃]

2
En [r̄uj
]6

sup
u∈U ,j∈[p̃]

2
|(En − EP )[r̄uj
]| +

sup
u∈U ,j∈[p̃]

2
EP [r̄uj
].

Consider the class of functions G = {(D, X) 7→ X j (γuj − γ̄uj ) : u ∈ U , j ∈
j
[p̃]} and Gj,T = {(D, X) 7→ X j (γuj − γuT
) : u ∈ U } for j ∈ [p̃] and T ⊂
[p + p̃ − 1] being a subset of the components of X j with |T | 6 sn . Since
j
γ̄uj = γuT
for some T = Tuj , it follows that G ⊂ ∪j∈[p̃],|T |6sn Gj,T . Also, we
j
have kγuT
− γuj ′ T k 6 kγuj − γuj ′ k for all u, u′ ∈ U , j ∈ [p̃], and T ⊂ [p + p̃ − 1].
Therefore, for fixed j and T , we have
j
(X j (γuT
− γuj ))2 − (X j (γuj ′ T − γuj ′ ))2
j
j
= X j (γuT
− γuj + γuj ′ T − γuj ′ )X j (γuT
− γuj ′ T + γuj ′ − γuj )

j
j
− γuj + γuj ′ T − γuj ′ k1 kγuT
− γuj ′ T + γuj ′ − γuj k1
6 k(D ′ , X ′ )′ k2∞ kγuT

6 8k(D ′ , X ′ )′ k2∞ sup kγuj k1 {p + p̃}1/2 kγuj − γuj ′ k
u∈U


−1 ′
′
6 M Lγ k(D , X ′ )′ k2∞ M |u − u′ |.

36

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

where L′γ = 8 supu∈U ,j∈[p̃] kγuj k1 {p + p̃}1/2 Lγ . an and we will set M = a2n .
Therefore, we have for the envelope G(D, X) = k(D ′ , X ′ )′ k2∞ (M −1 L′γ +
supu∈U ,j∈[p̃] kγ̄uj − γuj k21 ) that for all 0 < ǫ 6 1 and all finitely-discrete probability measures Q,

2
log N (ǫkGkQ,2 , G 2 , k · kQ,2 ) . sn log an + max log ǫkGkQ,2 , Gj,T
, k · kQ,2
j∈[p̃],|T |6s

. sn log an + log N (ǫ/M, U , dU )

. sn log an + log(an /ǫ) . sn log(an /ǫ).

By Lemma O.2, since
. n1/q Mn,2

max G(Di , Xi )

16i6n

′
a−2
n Lγ +

P,2

sup
u∈U ,j∈[p̃]

kγ̄uj − γuj k21

!

. n−1+1/q Mn,2 s2n log an ,
we have with probability 1 − o(1) that
s
4 ]
sn log an supu∈U ,j∈[p̃] EP [r̄uj
2
sup |(En − EP )[r̄uj
]| .
n
u∈U ,j∈[p̃]
sn n−1+1/q Mn,2 s2n log2 an
+
n
r
sn log an
sn log an
sn log an sn log an
.
+ δn
.
,
n
n
n
n

where we used that sn > 1, r̄uj = X j (γuj − γ̄uj ), EP [{(D ′ , X ′ )ξ}4 ] 6 C1 kξk4
by Assumption 3.4(iv), kγ̄uj − γuj k2 6 C12 sn log an /n by Assumption 3.2,
Mn,2 s2n log an 6 δn n1−1/q implied by Assumption 3.4(viii). Finally, the result
2 ] = E [{X j (γ j − γ̄ j )}2 ] . kγ j − γ̄ j k2 . s log a /n by
follows since EP [r̄uj
u
u
u
u
P
n
n
Assumption 3.2.

Proof of Lemma J.2. Recall that fbu2 = fbu2 (D, X) = Λ′ (D ′ θeu + X ′ βeu )
and that by Theorem 4.1, we have
sup(kθeu − θu k + kβeu − βu k) . (sn log an /n)1/2

u∈U

and supu∈U k(θeu′ , βeu′ )′ k0 . sn with probability 1 − o(1). Also,
max |(Di′ , Xi′ ){(θeu′ , βeu′ )′ − (θu′ , βu′ )′ }|

16i6n

6 max k(Di′ , Xi′ )′ k∞ {kθeu − θu k1 + kβeu − βu k1 }
16i6n

.P n1/(2q) Mn,2 (s2n log an /n)1/2 6 δn

POST-REGULARIZATION CONFIDENCE REGIONS

37

by Assumption 3.4(vii, viii) since Mn,2 > 1. Thus, for t̃ui = Di′ θeu + Xi′ βeu and
tui = Di′ θu + Xi′ βu , we have with probability 1 − o(1) that supu∈U ,i∈[n] |t̃ui −
1/2

tui | 6 δn = o(1), and so |Λ(t̃ui ) − Λ(tui )| . Λ′ (tui )|t̃ui − tui | uniformly over
u ∈ U and i = 1, . . . , n as in (I.6). Hence, the inequality |x(1−x)−y(1−y)| 6
|x− y|, which holds for all x, y ∈ [0, 1], implies that with probability 1− o(1),
2
2
2
(J.1) |fbui
− fui
| 6 |Λ(t̃ui ) − Λ(tui ) − rui | . Λ′ (tui )|t̃ui − tui | + |rui | 6 fui
/2

since |ru | 6 fu2 /4 by Assumption 3.5 and
(J.2)

2
2
Λ′ (tui ) = fui
+ 2Λ(tui )rui − rui + rui

2
2
2
2
6 fui
+ 3|rui | + rui
6 fui
+ 4|rui | 6 2fui

by the definition of fu2 and since |ru | 6 1. Therefore, with probability 1−o(1),
k(fbu2 − fu2 )Zuj /fbu kPn ,2 . k(fbu2 − fu2 )Zuj /fu kPn ,2

uniformly over u ∈ U and j ∈ [p̃]. Hence, it suffices to show that with
probability 1 − o(1),
sup
u∈U ,j∈[p̃]

k(fbu2 − fu2 )Zuj /fu kPn ,2 . (sn log an /n)1/2 .

Next, as in (H.1), we have uniformly over u, u′ ∈ U that kγuj − γuj ′ k1 .
(p + p̃)1/2 |u − u′ |, and so, given that Zuj − Zuj ′ = X j (γuj ′ − γuj ), we have by
Assumption 3.4(vii) that
j
max |Zui
− Zuj ′ i | 6 max k(Di′ , Xi′ )′ k∞ kγuj − γuj ′ k1

16i6n

16i6n

.P n1/(2q) Mn,2 (p + p̃)1/2 |u − u′ |.
Moreover, as in (H.2), we have uniformly over u, u′ ∈ U that |fu2 − fu2′ | .
|u − u′ |.
√
Further, observe that for a > 1, the inequality |x| 6 log( a − 1) implies
that
1
1
1
ex
√
>
= −x
>
.
Λ′ (x) =
x
2
x
(1 + e )
e +2+e
2 a
2(1 + e|x| )
Also, by Assumptions 3.1, 3.2, and 3.4(vii),
|tui | 6 k(Di′ , Xi′ )′ k∞ (kθu k1 + kβk1 ) 6 n1/(2q) Mn,2

p

sn log n

with probability 1 − o(1) uniformly over u ∈ U and i = √
1, . . . , n. Thus,
√
applying the inequality above with a−1 = exp(n1/(2q) Mn,2 sn log n) gives
p
2
fui
> Λ′ (tui )/2 & exp(−n1/(2q) Mn,2 sn log n)

38

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

with probability 1 − o(1) uniformly over u ∈ U and i = 1, . . . , n. So,
p
En [fu−2 ] . exp(n1/(2q) Mn,2 sn log n)
with probability 1 − o(1) uniformly over u ∈ U .
In addition, let

−1

p
1+1/q
2
2
1/2
1/(2q)
,
ǫ = ǫn = n
(Mn,1 ∨ Mn,2 )(p + p̃) exp(n
Mn,2 sn log n)

and let U ǫ be an ǫ-net of U with |U ǫ | 6 1/ǫ. For all i = 1, . . . , n, let Ui be
a value of u ∈ R such that Yi = (1 − u)y + uȳ. Note that fbu does not vary
with u on any interval [u, ū] ⊂ U as long as Ui ∈
/ [u, ū] for all i = 1, . . . , n.
Also, since ǫ . n−3 , with probability 1 − o(1), each interval [u − 2ǫ, u + 2ǫ]
with u ∈ U ǫ contains at most one value of Ui ’s by Assumption 3.3. Now,
sup max En [(fbu2 − fu2 )2 (Zuj /fu )2 ] . sup max En [(fbu2 − fu2 )2 (Zuj /fu )2 ]
u∈U j∈[p̃]

+

u∈U ǫ j∈[p̃]

sup

inf

′
ǫ
u∈U ,j∈[p̃] u ∈U

En [(fbu2 − fu2 )2 (Zuj /fu )2 − (fbu2′ − fu2′ )2 (Zuj ′ /fu′ )2 ] ,

and uniformly over j ∈ [p̃] and u, u′ ∈ U such that fbu = fbu′ , we have with
probability 1 − o(1) that
En [(fbu2 − fu2 )2 (Zuj /fu )2 − (fbu2′ − fu2′ )2 (Zuj ′ /fu′ )2 ]
6 En [{(fbu2 − fu2 )2 − (fbu2′ − fu2′ )2 }(Zuj /fu )2 ]

+ En [(fbu2′ − fu2′ )2 {(Zuj /fu )2 − (Zuj ′ /fu′ )2 }]

. En [{(fu2′ − fu2 )(Zuj /fu )2 ] + En [fu4′ {(Zuj /fu )2 − (Zuj ′ /fu′ )2 }]
. |u′ − u|En [(Zuj /fu )2 ] + En [(fu4′ /fu2 )|{Zuj − Zuj ′ }{Zuj + Zuj ′ }|]
+ En [(fu2′ /fu2 )(Zuj ′ )2 (fu2′ − fu2 )]


2
.P |u′ − u| · n1/q Mn,1
+ n1/(2q) Mn,2 (p + p̃)1/2 n1/(2q) Mn,1 · En [fu−2 ].

Thus, by the choice of ǫ, and since with probability 1 − o(1) each interval
[u − 2ǫ, u + 2ǫ] with u ∈ U ǫ contains at most one value of Ui ’s, we have with
probability 1 − o(1) that
sup

En [(fbu2 − fu2 )2 (Zuj /fu )2 − (fbu2′ − fu2′ )2 (Zuj ′ /fu′ )2 ] . sn log an /n.
inf
′
ǫ

u∈U ,j∈[p̃] u ∈U

POST-REGULARIZATION CONFIDENCE REGIONS

39

Further by (J.1) and (J.2), with probability 1 − o(1),
sup
u∈U ǫ ,j∈[p̃]

.

En [(fbu2 − fu2 )2 (Zuj /fu )2 ]

sup

u∈U ǫ ,j∈[p̃]

En [Λ′ (tui )2 |t̃ui − tui |2 (Zuj /fu )2 ] +

. max

sup

j∈[p̃] u∈U ǫ ,kδk0 6Csn ,kδk=1

sup
u∈U ǫ ,j∈[p̃]

En [ru2 (Zuj /fu )2 ]

En [{(D ′ , X ′ )δ}2 (Zuj )2 ]sn log an /n + sn log an /n

for C large enough, where we used that supu∈U En [ru2 (Zuj /fu )2 ] . sn log an /n
with probability 1 − o(1) by Assumption 3.5, and supu∈U (kθeu − θu k + kβeu −
βu k) . (sn log an /n)1/2 and supu∈U (k(θeu′ , βeu′ )′ k0 + k(θu′ , βu′ )′ k0 ) . sn with
probability 1 − o(1). Therefore, since
EP [{(D ′ , X ′ )δ}2 (Zuj )2 ] 6 EP [{(D ′ , X ′ )δ}4 ]1/2 EP [(Zuj )4 ]1/2 . 1,

to establish the statement of the lemma it suffices to show that with probability 1 − o(1),
max
j∈[p̃]

sup
u∈U ǫ ,kδk0 6Csn ,kδk=1

|(En − EP )[{(D ′ , X ′ )δ}2 (Zuj )2 ]| . 1.

To do so, we will apply Lemma P.1 with U replaced by U ǫ × [p̃] and Xu
replaced by Zuj (D ′ , X ′ )′ . We have
 h
K = EP

max

16i6n,u∈U

j
kZui
(D ′ , X ′ )′ k2∞
ǫ

i1/2

i1/q
 h
6 n1/q EP maxǫ kZuj (D ′ , X ′ )′ kq∞
u∈U

1/(2q)
j 2q
6 n1/q EP [k(D ′ , X ′ )′ k2q
6 n1/q Mn,2 Mn,1
∞ ]EP [kZu k∞ ]

by Assumption 3.4(v,vii). Also,
sup

max

ǫ
kδk0 6Csn ,kδk=1 u∈U ,j∈[p̃]

EP [(Zuj (D ′ , X ′ )δ)2 ] . 1

by Assumption 3.4(iv). Then, by Lemma P.1 we have for


log1/2 (p̃|U0ǫ |) + (log sn )(log1/2 n)(log1/2 an )
δ̃n = n−1/2 Ks1/2
n
that

sup

max

ǫ
kδk0 6Csn ,kδk=1 u∈U ,j∈[p̃]

|(En − EP )[(Zuj (D ′ , X ′ )δ)2 ]| .P δ̃n2 + δ̃n .

40

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Now,
2
2
p̃|U ǫ | 6 p̃/ǫ 6 n1+1/q (Mn,1
∨ Mn,2
)(p + p̃)3/2 exp(n1/(2q) Mn,2

so that
log(p̃|U ǫ |) . log an + n1/(2q) Mn,2

p

p

sn log n),

sn log n.

Using Assumption 3.4(vi,viii,ix) and since δn2 log an = o(1), we have
2 M4 s
Mn,1
(Mn,1 ∨ Mn,2 )2 sn log an
n,2 n
1/2
6
δ
log
a
=
o(1)
and
= o(1),
n
n
n1/2−1/q
n1−3/q

and so
1/2

δ̃n .

.

sn n1/q Mn,2 Mn,1 (log sn )(log1/2 n)(log1/2 an )
n1/2
1/2
1/2 1/4
sn n1/q Mn,2 Mn,1 n1/(4q) Mn,2 sn log1/4 n
+
n1/2
 M 2 sn log an 1/2  M 2 sn log an 1/2
n,1
n,2
+

n1/2−1/q
n1/2−1/q
 M 2 sn log n 1/4  M 2 sn 1/4  M 2 M 4 sn 1/4
n,2
n,1 n,2
n,1
n1/2−1/q

n1/2−1/q

n1−3/q

= o(1).

This completes the proof.



Proof of Lemma J.3. Both results follow from Lemma P.1. We provide
a proof only for the first result (the second result is simpler and follows
similarly).
Recall that by Assumption 3.4(i),
inf kfu (D ′ , X ′ )δkP,2 > c1 .

kδk=1

Also, observe that for any x, y ∈ [0, 1], we have
p

x(1 − x) −

p

y(1 − y) 6

p

|x − y|.

Therefore, since fu2 = E[Yu | D, X](1 − E[Yu | D, X]), by Assumption 3.3,
for any u, u′ ∈ U , we have
1/2 
1/2

6 C1 |u′ − u|
.
|fu′ − fu | 6 |E[Yu′ − Yu | D, X]|

POST-REGULARIZATION CONFIDENCE REGIONS

41

Hence, since ℓn → ∞, with probability 1 − o(1) uniformly over u, u′ ∈ U and
δ ∈ Rp+p̃ with kδk = 1 and kδk0 6 ℓn sn , we have
kfu′ (D ′ , X ′ )δkPn ,2 − kfu (D ′ , X ′ )δkPn ,2

6 k(fu′ − fu )(D ′ , X ′ )δkPn ,2 6 kfu′ − fu kPn ,2 max k(Di′ , Xi′ )′ k∞ kδk1
16i6n


1/2
√
√
n1/(2q) Mn,2 ℓn sn
6 kfu′ − fu kPn ,2 n1/(2q) Mn,2 ℓn sn 6 C1 |u′ − u|

by Assumption 3.4(vii). Thus, for
ǫ = ǫn =

c21
,
2 ℓ4 s
C1 n1/(2q) Mn,2
n n

we have with probability 1 − o(1) that
sup
|u−u′ |6ǫ,kδk0 6ℓn sn ,kδk=1

kfu′ (D ′ , X ′ )δkPn ,2 − kfu (D ′ , X ′ )δkPn ,2 6 c1 /ℓn .

Now, let U ǫ be an ǫ-net of U such that |U ǫ | 6 3/ǫ. We will apply Lemma
P.1 with U replaced by U ǫ , k = ℓn sn , and Xu replaced by fu (D ′ , X ′ )′ . Since
0 6 fu 6 1, we have
i1/2
 h
2
k(Di′ , Xi′ )′ k2∞
K = EP max maxǫ fui
16i6n u∈U

i1/2
 h
6 n1/(2q) Mn,2
6 EP max k(Di′ , Xi′ )′ k2∞
16i6n

by Assumption 3.4(vii). Also,
sup

maxǫ EP [fu2 ((D ′ , X ′ )δ)2 ]

kδk0 6ℓn sn ,kδk=1 u∈U

EP [{(D ′ , X ′ )δ}2 ] 6

sup

6

kδk0 6ℓn sn ,kδk=1

p

C1

by Assumption 3.4(iv). Thus, applying Lemma P.1 gives
sup

maxǫ |(En − EP )[fu2 ((D ′ , X ′ )δ)2 ]| .P δ̃n2 + δ̃n

kδk0 6ℓn sn ,kδk=1 u∈U

where
δ̃n = n−1/2+1/(2q) Mn,2
Finally, by Assumption 3.4(viii),

p

ℓn sn (log1/2 an )(log 3/2 n).

2
δ̃n2 = n−1+1/q Mn,2
ℓn sn (log an )(log3 n)

6 n−1/2 ℓn δn (log1/2 an )(log3 n) = o(1)
since ℓn → ∞ slowly enough and log1/2 an . δn n1/6 by Assumption 3.4(ii,iii).
Combining presented bounds gives the asserted claim.


42

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

APPENDIX K: DOUBLE SELECTION METHOD FOR LOGISTIC
REGRESSION WITH FUNCTIONAL RESPONSE
DATA
In this section we discuss in details and provide formal results for the
double selection estimator for logistic regression with functional response
data.
Algorithm 5. (Based on double selection) For each u ∈ U and j ∈ [p̃]:
Step 1’. Run post-ℓ1 -penalized logistic estimator (4.2) of Yu on D and X to
compute (θeu , βeu ).
Step 2’. Define the weights fbu2 = fbu2 (D, X) = Λ′ (Di′ θeu + Xi′ βeu ).
buj .
Step 3’. Run the lasso estimator (4.4) of fbu Dj on fbu X to compute γ
Step 4’. Run logistic regression of Yu on Dj and all the selected variables in
Steps 1’ and 2’
to compute θ̌uj .

The following result establishes the Bahadur representation for the double
selection estimator (analog to Theorem 3.1 for score functions).
Theorem K.1 (Uniform Bahadur representation, double selection). Suppose that Assumptions 3.1 – 3.5 hold for all P ∈ Pn . Then, the estimator
(θ̌uj )u∈U ,j∈[p̃] , based on the double selection, obeys as n → ∞
√
Σ−1
n(θ̌uj − θuj ) = Gn ψ̄uj + OP (δn ) in ℓ∞ (U × [p̃])
uj

uniformly over u ∈ U , where Σ2uj := EP [fu2 (D − X j γuj )2 ]−1 .
Proof of Theorem K.1. The analysis is reduced to the proof of Theγuj ) for which by Theorems
orem 3.1. Let Tbuj = supp(θbu ) ∪ supp(βbu ) ∪ supp(b
4.1 and 4.2 satisfies supu∈U ,j∈[p̃] |Tbuj | . sn with probability 1 − o(1). Therefore Step 3 is a post-selection logistic regression which yields an initial rate
of convergence |θ̌uj − θuj | + kθ̄u[p̃]\j − θu[p̃]\j k + kβ̄u − βu k . (sn log an /n)1/2 .
Moreover, by the first order condition of Step 3 we have
(K.1)

′
En [{Yui − Λ(Dj θ̌uj + D[p̃]\j
θ̄u[p̃]\j + X ′ β̄u )}(Dj , X jb )′ ] = 0
Tuj

so that any linear combination yields zero. Setting the parameters (θeu′ , βeu′ ) =
′
γuj ) = Dj −X j γ
euj , we recover the
(θ̄u[p̃]\j , θ̄u[p̃]\j
, β̄u′ ), and zbuj = (Dj , X jb )(1, −e
Tuj

setting in the proof of Theorem 3.1. The rest of the proof follows similarly.


POST-REGULARIZATION CONFIDENCE REGIONS

43

The double selection procedure benefits from additional variables selected
in Step 2. The (estimated) weights used in the equation ensure that selection
will ensure a near-orthogonality condition that is required to remove first
order bias. In contrast, (naive) Post-ℓ1 -logistic regression does not select such
variables which in turn translates in to first order bias in the estimation of
θuj . We stress that Step 2 is tailored to the estimation of each coefficient θuj
which enables the additional adaptivity.
The double selection achieves orthogonality conditions relative to all selected variables in finite samples. Although first-order equivalent to other
estimator discussed here, this additional orthogonality could potentially lead
to a better finite sample performance. To provide intuition why, consider the
logistic regression case with p̃ = dim(D) = 1 and U = {0} for simplicity. In
this case we have
E[Y |D, X] = Λ(Dθ0 + X ′ β0 ) and let f = Λ′ (Dθ0 + X ′ β0 ).
Letting γ
b be the Lasso estimate of f D on f X we have that the one step
estimator
b
θ̄ = θb − En [(D − X ′ γ
b)2 ]−1 En [{Y − Λ(D θb + X ′ β))}(D
− X ′γ
b)]

is an approximate solution for the moment condition
(K.2)

b
− X ′γ
b)] = 0.
En [{Y − Λ(Dθ + X ′ β)}(D

b Our proposed estimator based on
Indeed, it is one Newton step from θ.
estimated score functions defines θ̌ as an exact solution for (K.2), namely
b
En [{Y − Λ(D θ̌ + X ′ β)}(D
− X ′γ
b)] = 0.

The double selection achieves that implicitly. Indeed, letting Tb = support(β̌)∪
support(b
γ ), the first order condition of running a logistic regression of Y on
D and XTb yields



D
′
=0
(K.3)
En {Y − Λ(D θ̌ + X β̌)}
XTb
where (θ̌, β̌) is the solution of the logistic regression. By multiplying the
vector (1, −b
γ ′ )′ , the relation above implies
En [{Y − Λ(D θ̌ + X ′ β̌)}(D − X ′ γ
b)] = 0.

b ⊂ Tb ensures that β̌ is a good
since support(b
γ ) ⊂ Tb (the condition support(β)
approximation of β0 ). Note that (K.3) provides a more robust orthogonality
condition and does not need to explicitly create the new score functions as
the other two methods.

44

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

APPENDIX L: GENERIC FINITE SAMPLE BOUNDS FOR
ℓ1 -PENALIZED M-ESTIMATORS: NUISANCE
FUNCTIONS AND FUNCTIONAL DATA
In this section, we establish a set of results for ℓ1 -penalized M-estimators
with functional data and high-dimensional parameters. These results are
used in the proofs of Theorems 4.1 and 4.2 and may be of independent
interest.
We start with specifying the setting. Consider a data generating process with a functional response variable (Yu )u∈U and observable covariates
(Xu )u∈U satisfying for each u ∈ U ⊂ Rdu ,
(L.1)

θu ∈ arg minp EP [Mu (Yu , Xu , θ, au )],
θ∈R

where θu is a p-dimensional vector of parameters, au is a nuisance parameter
that captures potential misspecification of the model, and Mu is a known
function. Here for all u ∈ U , Yu is a scalar random variable and Xu is a
pu -dimensional random vector with pu 6 p for some p. We assume that the
solution θu is sparse in the sense that the process (θu )u∈U satisfies
kθu k0 6 s,

for all u ∈ U .

Because the model (L.1) allows for the nuisance parameter au , such sparsity
assumption is very mild and formulation (L.1) encompasses many cases of
interest including approximately sparse models.
Throughout this section, we assume that we have n i.i.d. observations,
{(Yui , Xui )u∈U }ni=1 , from the distribution of (Yu , Xu )u∈U to estimate (θu )u∈U .
In addition, we assume that an estimate b
au of the nuisance parameter au is
available for all u ∈ U . Using the estimate b
au , we use the criterion function
Mu (Yu , Xu , θ) := Mu (Yu , Xu , θ, b
au )

as a proxy for Mu (Yu , Xu , θu , au ). We allow for the case where p is much
larger than n.
Since p is potentially larger n, and the parameters θu are assumed to be
sparse, we consider an ℓ1 -penalized Mu -estimator (Lasso) of θu :


λ b
b
(L.2)
θu ∈ arg min En [Mu (Yu , Xu , θ)] + kΨu θk1
θ
n

b u a diagonal matrix of penalty loadings.
where λ is a penalty level and Ψ
Further, for each u ∈ U , we also consider a post-regularized (Post-Lasso)
estimator of θu :
(L.3)

θeu ∈ arg min En [Mu (Yu , Xu , θ)] : supp(θ) ⊆ Tbu
θ

POST-REGULARIZATION CONFIDENCE REGIONS

45

where Tbu = supp(θbu ).
b u is
We assume that for each u ∈ U , the matrix of penalty loadings Ψ
chosen as an appropriate estimator of the following “ideal” matrix of penalty
b u0 = diag({lu0k , k = 1, . . . , p}), where
loadings: Ψ
i1/2
 h
,
(L.4)
lu0k = En (∂θk Mu (Yu , Xu , θu , au ))2

where ∂θk Mu (Yu , Xu , θu , au ) denotes a sub-gradient of the function θ 7→
Mu (Yu , Xu , θ, au ) with respect to the kth coordinate of θ and evaluated at
b u will be specified below in lemmas. Also, we
θ = θu . The properties of Ψ
assume that the penalty level λ is chosen such that with high probability,
(L.5)

λ
b −1 En [∂θ Mu (Yu , Xu , θu , au )]
> c sup Ψ
u0
n
u∈U

∞

,

where c > 1 is a fixed constant. When U is a singleton, the condition (L.5)
is similar to that in [7], [2], and [4]. When U is a continuum of indices, a
similar condition was previously used in [1] in the context of ℓ1 -penalized
quantile regression.
For u ∈ U , denote Tu = supp(θu ). Let ℓ and L be some constants satisfying
L > ℓ > 1/c. Also, let
c̃ =

Lc + 1
b u0 k∞ kΨ
b −1 k∞ ,
sup kΨ
u0
ℓc − 1 u∈U

where for any diagonal matrix A = diag({ak , k = 1, . . . , p}), we denote
kAk∞ = max16k6p |ak |. Let (∆n )n>1 be a sequence of positive constants converging to zero, and let (Cn )n>1 be a sequence of random variables. Also, let
wu = wu (Xu ) be some weights satisfying 0 6 wu 6 1 almost surely. Finally,
let Au be some random subset of Rp and q̄Au be a random variable possibly
depending on Au , where both Au and q̄Au are specified in the lemmas below.
To state our results in this section, we need the following assumption:
Assumption L.1 (M-Estimation). The function θ 7→ Mu (Yu , Xu , θ) is
convex almost surely, and with probability at least 1 − ∆n , the following
inequalities hold for all u ∈ U :
√
(a) |En [∂θ Mu (Yu , Xu , θu ) − ∂θ Mu (Yu , Xu , θu , au )]′ δ| 6 Cn k wu Xu′ δkPn ,2
for all δ ∈ Rp ;
b u0 6 Ψ
b u 6 LΨ
b u0 ;
(b) ℓΨ
(c) for all δ ∈ Au ,
En [Mu (Yu , Xu , θu + δ)] − En [Mu (Yu , Xu , θu )] − En [∂θ Mu (Yu , Xu , θu )]′ δ
 √
√
√
+ 2Cn k wu Xu′ δkPn ,2 > k wu Xu′ δk2Pn,2 ∧ {q̄Au k wu Xu′ δkPn,2 } .

46

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

In many applications one can take the weights to be wu = wu (Xu ) = 1
but we allow for more general weights since it is useful for our results on the
weighted Lasso with estimated weights. Also, in applications, we typically
have Cn . {n−1 s log(pn)}1/2 . Assumption L.1(a) bounds the impact of esb u are
timating the nuisance functions uniformly over u ∈ U . The loadings Ψ
b
assumed larger (but not too much larger) than the ideal choice Ψu0 defined
in (L.4). This is formalized in Assumption L.1(b). Assumption L.1(c) is an
identification condition that will be imposed for particular choices of Au
and q̄Au . It relates to conditions in the literature derived for the case of a
singleton U and no nuisance functions, see the restricted strong convexity3
used in [13] and the non-linear impact coefficients used in [1] and [3].
Define the restricted eigenvalue
κ̄2c̃ = inf

inf

u∈U δ∈∆2c̃,u

√
k wu Xu′ δkPn ,2 /kδTu k

where ∆2c̃,u = {δ : kδTc u k1 6 2c̃kδTu k1 }. Also, define minimum and maximum
spare eigenvalues
φmin (m, u) =

√
kXu′ δk2Pn ,2
k wu Xu′ δk2Pn ,2
and
φ
(m,
u)
=
max
.
max
16kδk0 6m
kδk2
kδk2
16kδk0 6m
min

The following results establish the rate of convergence and a sparsity bound
for the ℓ1 -penalized estimator θbu defined in (L.2) as well as the rate of
convergence for the post-regularized estimator θeu defined in (L.3).
Lemma L.1.

Suppose that Assumption L.1 holds with

Au = {δ : kδTc u k1 6 2c̃kδTu k1 } ∪ {δ : kδk1 6
√

b −1 k∞
√
3n ckΨ
u0
Cn k wu Xu′ δkPn ,2 }
λ ℓc − 1

b u0 k∞ λ s + 6c̃Cn . In addition, suppose that λ satisfies
and q̄Au > (L + 1c )kΨ
nκ̄2c̃
condition (L.5) with probability 1 − ∆n . Then, with probability at least 1 −
2∆n , we have for all u ∈ U that
√

√
1 b
λ s
′ b
k wu Xu (θu − θu )kPn ,2 6 L +
kΨu0 k∞
+ 6c̃Cn ,
c
nκ̄2c̃
 (1 + 2c̃)√s 3n ckΨ
b −1 k∞ 
u0
b
Cn
+
kθu − θu k1 6
κ̄2c̃
λ ℓc − 1
√


λ s
1 b
kΨu0 k∞
+ 6c̃Cn .
× L+
c
nκ̄2c̃
√
Assumption L.1 (a) and (c) could have been stated with {Cn / s}kδk1 instead of
√
′
Cn k wu Xu δkPn ,2 .
3

47

POST-REGULARIZATION CONFIDENCE REGIONS

Lemma L.2. In addition to conditions of Lemma L.1, suppose that with
probability 1 − ∆n , we have for some random variable Ln and all u ∈ U and
δ ∈ Rp that
(L.6)

{En [∂θ Mu (Yu , Xu , θbu ) − ∂θ Mu (Yu , Xu , θu )]}′ δ 6 Ln kXu′ δkPn ,2 .

Further, for all u ∈ U , let sbu = supp(Tbu ). Then with probability at least
1 − 3∆n , we have for all u ∈ U that
sbu 6 min φmax (m, u)L2u ,
m∈Mu

where Mu = {m ∈ N : m > 2φmax (m, u)L2u } and Lu =
Lemma L.3.
sbu + su } and

{Cn + Ln }.

Suppose that Assumption L.1 holds with Au = {δ : kδk0 6

q̄Au > 2 max

(L.7)

b −1 k∞ n
ckΨ
u0
cℓ−1 λ



1/2
,
En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )]
+
 √sb + s kE [∂ M (Y , X , θ , a )]k

u
u
n θ u u
u u u
∞
p
+ 3Cn .
φmin (b
su + su , u)

Then with probability at least 1 − ∆n , we have for all u ∈ U that

1/2
√
k wu Xu′ (θeu − θu )kPn ,2 6 En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )]
+
√
sbu + su kEn [∂θ Mu (Yu , Xu , θu , au )]k∞
p
+ 3Cn .
+
φmin (b
su + su , u)

In addition, with probability at least 1 − ∆n , we have for all u ∈ U that
(L.8)
λL b
b u0 k∞ .
En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )] 6
kθu − θu k1 sup kΨ
n
u∈U

A key requirement in Lemmas L.1 and L.2 is that λ satisfies (L.5) with
high probability. Therefore, below we provide a choice of λ and a set of
conditions under which the proposed choice of λ satisfies this requirement.
Let dU : U × U → R+ denote a metric on U . Also, let
Su = ∂θ Mu (Yu , Xu , θu , au ),

u ∈ U.

Moreover, let C and C̄ be some strictly positive constants. Finally, (ǫn )n>1 ,
(ϕn )n>1 , and (Nn )n>1 be some sequences of positive constants, where ϕn =
o(1).

48

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Condition WL. The constants ǫn and Nn satisfy the inequality Nn >
N (ǫn , U , dU ) and the following conditions hold:
(i) sup max(EP [|Suk |3 ])1/3 Φ−1 (1 − γ/{2pNn }) 6 ϕn n1/6 ;
u∈U k∈[p]

(ii) C 6 EP [|Suk |2 ] 6 C̄, for all u ∈ U and k ∈ [p];
(iii) with probability at least 1 − ∆n ,
sup
dU

(u,u′ )6ǫ

sup

n

kEn [Su − Su′ ]k∞ 6 ϕn n−1/2 , and
2
2
]| 6 ϕn .
− Su2′ k ]| + |(En − EP )[Suk
max |EP [Suk

dU (u,u′ )6ǫn k∈[p]

Let
(L.9)

√
λ = c′ nΦ−1 (1 − γ/{2pNn }),

where 1 − γ (with γ = γn = o(1)) is a confidence level associated with
the probability of event (L.5), and c′ > c is a slack constant. The following
lemma shows that this choice of λ satisfies (L.5) with high probability under
Condition WL.
Lemma L.4. Suppose that Condition WL holds. In addition, suppose
that λ satisfies (L.9) for some c′ > c and γ = γn ∈ [1/n, 1/ log n]. Then


−1
b
PP λ/n > c sup kΨu0 En [Su ]k∞ > 1 − γ − o(γ) − ∆n .
u∈U

Condition WL(iii) is of high level. Therefore, to conclude this section, we
present a lemma that gives easy to verify conditions that imply Condition
WL(iii).
Lemma L.5. Suppose that for all u ∈ U , Xu = X and Yu = H(Y, u)
where Y is a random variable and {H(·, u) : u ∈ U } is a VC-subgraph class
of functions bounded by one with index CY for some constant CY > 1. In
addition, suppose that for all u ∈ U , we have Su = (Yu − EP [Yu | X]) · X.
2 ] 6
Moreover, suppose that maxk∈[p] EP [Xk4 ] 6 C̄, C 6 supu∈U ,k∈[p] EP [Suk
q 1/q
C̄, and EP [kXk∞ ]
6 Kn , for some constants C, C̄ > 0 and q > 4 and
a sequence of constants (Kn )n>1 . Finally, suppose that EP [|Yu − Yu′ |4 ] 6
Cu |u − u′ |ν for any u, u′ ∈ U and some constants ν and C. Then we have

POST-REGULARIZATION CONFIDENCE REGIONS

49

with probability at least 1 − (log n)−1 that
(L.10)
(L.11)
(L.12)

 log(npK ) 1/2 K log(npK )
n
n
n
+
1+ν/2
1−1/q
′
n
n
dU (u,u )61/n
 log(npK ) 1/2 K 2 log(npK )
n
n
2
+ n 1−2/q
]| .
sup max |(En − EP )[Suk
k∈p
n
n
u∈U
sup

kEn [Su − Su′ ]k∞ .

2
− Su2′ k ]| . dU (u, u′ )ν/4
max |EP [Suk
k∈[p]

up-to constants that depend only on C, C̄, CY , Cu , q, and ν.
APPENDIX M: PROOFS FOR APPENDIX L
Proof of Lemma L.1. For u ∈ U , let δu = θbu − θu and Su,n =
En [∂θ Mu (Yu , Xu , θu , au )]. Throughout the proof, we will assume that the
events (a), (b), and (c) in Assumption L.1 as well as the event (L.5) hold.
These events hold with probability at least 1 − 2∆n . We will show that the
inequalities in the statement of Lemma L.1 hold under these events.
By definition of θbu , we have
En [Mu (Yu , Xu , θbu )] +

Thus,

(M.1)

λ b b
λ b
kΨu θu k1 6 En [Mu (Yu , Xu , θu )] + kΨ
u θu k1 .
n
n

En [Mu (Yu , Xu , θbu )] − En [Mu (Yu , Xu , θu )]
λ b b
λ b
λ b
λ b
kΨu δu,Tu k1 − kΨ
6 kΨ
u θu k1 − kΨu θu k1 6
u δu,Tuc k1
n
n
n
n
λL b
λℓ b
6
kΨu0 δu,Tu k1 − kΨ
u0 δu,Tuc k1 .
n
n

Moreover, by convexity of θ 7→ Mu (Yu , Xu , θ), we have

En [Mu (Yu , Xu , θbu )] − En [Mu (Yu , Xu , θu )]
√
λ1 b
kΨu0 δu k1 − Cn k wu Xu′ δu kPn ,2
(M.2) > En [∂θ Mu (Yu , Xu , θu )]′ δu > −
nc
where the second inequality holds by Assumption L.1(a) and
b −1 Su,n k∞
λ/n > c sup kΨ
u0
u∈U

50

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

since
′
|En [∂θ Mu (Yu , Xu , θu )]′ δu | = |Su,n
δu + {En [∂θ Mu (Yu , Xu , θu )] − Su,n }′ δu |

′
6 |Su,n
δu | + |{En [∂θ Mu (Yu , Xu , θu )] − Su,n }′ δu |
b −1 Su,n k∞ kΨ
b u0 δu k1 + Cn k√wu X ′ δu kPn ,2
6 kΨ
u

u0

√
λ1 b
6
kΨu0 δu k1 + Cn k wu Xu′ δu kPn ,2 .
nc

(M.3)

Combining (M.1) and (M.2), we have
(M.4)

√
λ Lc + 1 b
λ cℓ − 1 b
kΨu0 δu,Tuc k1 6
kΨu0 δu,Tu k1 + Cn k wu Xu′ δu kPn ,2 ,
n c
n c

and for c̃ =

Lc+1
ℓc−1

b u0 k∞ kΨ
b −1 k∞ , we have
supu∈U kΨ
u0

kδu,Tuc k1 6 c̃kδu,Tu k1 +

b −1 k∞
√
n ckΨ
u0
Cn k wu Xu′ δu kPn ,2 .
λ ℓc − 1

Now, suppose that δu 6∈ ∆2c̃,u , namely kδu,Tuc k1 > 2c̃kδu,Tu k1 . Then
2c̃kδu,Tu k1 6 c̃kδu,Tu k1 +
and so
kδu,Tu k1 6
since c̃ > 1. Also,

and so

b −1 k∞
√
n ckΨ
u0
Cn k wu Xu′ δu kPn ,2
λ ℓc − 1

b −1 k∞
√
1
n ckΨ
u0
kδu,Tuc k1 6 kδu,Tuc k1 +
Cn k wu Xu′ δu kPn ,2 ,
2
λ ℓc − 1
kδu,Tuc k1 6

Therefore,
(M.5)

b −1 k∞
√
n ckΨ
u0
Cn k wu Xu′ δu kPn ,2 ,
λ ℓc − 1

kδu k1 6

b −1 k∞
√
2n ckΨ
u0
Cn k wu Xu′ δu kPn ,2 .
λ ℓc − 1

b −1 k∞
√
3n ckΨ
u0
Cn k wu Xu′ δu kPn ,2 =: Iu ,
λ ℓc − 1

as long as δu 6∈ ∆2c̃,u . In addition, if δu ∈ ∆2c̃,u , then
√
√
s √
kδu,Tu k1 6 skδu,Tu k 6
k wu Xu′ δu kPn ,2 =: IIu .
κ̄2c̃

POST-REGULARIZATION CONFIDENCE REGIONS

51

Hence, in both cases, we have
kδu,Tu k1 6 Iu + IIu .

(M.6)

Next, for every u ∈ U , since
Au = ∆2c̃,u ∪ {δ : kδk1 6

b −1 k∞
√
3n ckΨ
u0
Cn k wu Xu′ δkPn ,2 },
λ ℓc − 1

it follows that δu ∈ Au , and we have

√
√
k wu Xu′ δu k2Pn ,2 ∧ q̄Au k wu Xu′ δu kPn ,2
6 En [Mu (Yu , Xu , θbu )] − En [Mu (Yu , Xu , θu )]
√
− En [∂θ Mu (Yu , Xu , θu )]′ δu + 2Cn k wu Xu′ δu kPn ,2

√
1λ b
6 L+
kΨu0 δu,Tu k1 + 3Cn k wu Xu′ δu kPn ,2
c n

√
1λ b
6 L+
kΨu0 k∞ {Iu + IIu } + 3Cn k wu Xu′ δu kPn ,2
c n
√
n
o √
1 b
λ s
6
L+
kΨu0 k∞
+ 6c̃Cn k wu Xu′ δu kPn ,2 ,
c
nκ̄2c̃

where the first inequality follows from Assumption L.1(c), the second from
b u0 δu,Tu k1 6 kΨ
b u0 k∞ kδu,Tu k1
(M.1), (M.3), and ℓ > 1/c, the third from kΨ
and (M.6), and the fourth from definitions of Iu , IIu , and c̃. Thus, as long
as
√

λ s
1 b
kΨu0 k∞
+ 6c̃Cn , for all u ∈ U ,
q̄Au > L +
c
nκ̄2c̃
which is assumed, we have

√

√
1 b
λ s
′
k wu Xu δu kPn ,2 6 L +
kΨu0 k∞
+ 6c̃Cn =: IIIu ,
c
nκ̄2c̃

for all u ∈ U .

This gives the first asserted claim. The second asserted claim follows from
kδu k1 6 1{δu ∈ ∆2c̃,u }kδu k1 + 1{δu ∈
/ ∆2c̃,u }kδu k1
 (1 + 2c̃)√s 3n ckΨ
b −1 k∞ 
u0
Cn IIIu .
+
6 (1 + 2c̃)IIu + Iu 6
κ̄2c̃
λ ℓc − 1

This completes the proof.



52

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Proof of Lemma L.2. For u ∈ U , let Su,n = En [∂θ Mu (Yu , Xu , θu , au )].
Throughout the proof, we will assume that the events (a), (b), and (c) in
Assumption L.1 as well as the events (L.5) and (L.6) hold. These events hold
with probability at least 1 − 3∆n . We will show that the inequalities in the
statement of Lemma L.2 hold under these events.
By definition of θbu , there exists a subgradient ∂θ En [Mu (Yu , Xu , θbu )] of
En [Mu (Yu , Xu , θbu )], such that for every j with |θbuj | > 0,
b
b −1
|(Ψ
u ∂θ En [Mu (Yu , Xu , θu )])j | = λ/n.

Therefore, we have
λp
b
b −1
sbu = k(Ψ
u ∂θ En [Mu (Yu , Xu , θu )])Tbu k
n
b −1 {En [∂θ Mu (Yu , Xu , θu )] − Su,n }) b k
b −1 Su,n ) b k + k(Ψ
6 k(Ψ
u
u
Tu
Tu
b
b −1
+ k(Ψ
u {En [∂θ Mu (Yu , Xu , θu ) − ∂θ Mu (Yu , Xu , θu )]})Tbu k
p
b −1 Ψ
b u0 k∞ kΨ
b −1 En [Su,n ]k∞ sbu
6 kΨ
u
u0
√
b −1 k∞ Cn
+ kΨ
sup
k wu X ′ δkPn ,2
u

6

b −1 k∞
+ kΨ
u

u

kδk=1,kδk0 6b
su

sup

kδk=1,kδk0 6b
su

|{En [∂θ Mu (Yu , Xu , θbu ) − ∂θ Mu (Yu , Xu , θu )]}′ δ|

b −1 k∞
λ p
kΨ
u0
{Cn + Ln }
sup
kXu′ δkPn ,2
sbu +
cℓn
ℓ
kδk=1,kδk0 6b
su

where the first inequality follows from the triangle inequality, the second
from Assumption L.1(a), and the third from Assumption L.1(b) and inequalities (L.5) and (L.6).
Now, recall that Lu =

b −1 k∞
n ckΨ
u0
λ cℓ−1

sup
kδk=1,kδk0 6b
su

{Cn + Ln }. In addition, note that

kXu′ δk2Pn ,2 = φmax (b
su , u).

Thus, we have
(M.7)

sbu 6 φmax (b
su , u)L2u .

Consider any M ∈ Mu = {m ∈ N : m > 2φmax (m, u)L2u }, and suppose that
sbu > M . By the sublinearity of the maximum sparse eigenvalue (Lemma 3
in [2]), for any integer k > 0 and constant ℓ > 1, we have φmax (ℓk, u) 6
⌈ℓ⌉φmax (k, u), where ⌈ℓ⌉ denotes the ceiling of ℓ. Therefore,
su , u)L2u = φmax (M sbu /M, u)L2u
sbu 6 φmax (b
 
sbu
2b
sn
6
φmax (M, u)L2u
φmax (M, u)L2u 6
M
M

POST-REGULARIZATION CONFIDENCE REGIONS

53

since ⌈k⌉ 6 2k for any k > 1. Therefore, we have M 6 2φmax (M, u)L2u which
violates the condition that M ∈ Mu . Therefore, we have sbu 6 M . In turn,
applying (M.7) once more with sbu 6 M we obtain sbu 6 φmax (M, u)L2u . The
result follows by minimizing the bound over M ∈ Mu .

Proof of Lemma L.3. The second asserted claim, inequality (L.8),
follows from the observation that with probability at least 1 − ∆n , for all
u ∈ U , we have that
En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )]
6 En [Mu (Yu , Xu , θbu )] − En [Mu (Yu , Xu , θu )]

λ b
λ b b
λ b
b
kΨu θu k1 − kΨ
u θu k1 6 kθu − θu k1 · sup kΨu k∞
n
n
n
u∈U
λL b
b u0 k∞ ,
kθu − θu k1 · sup kΨ
6
n
u∈U

6

where the first inequality holds by the definition of θeu , the second by the
definition of θbu , the third by the triangle inequality, and the fourth by Assumption L.1(ii).
To prove the first asserted claim, assume that the events (a), (b), and (c)
in Assumption L.1 hold. These events hold with probability at least 1 − ∆n .
We will show that the asserted claim holds under these events.
For u ∈ U , let δ̃u = θeu − θu , Su,n = En [∂θ Mu (Yu , Xu , θu , au )], and t̃u =
√
k wu Xu′ δ̃u kPn ,2 . By the inequality in Assumption L.1(c), we have

t̃2u ∧ q̄Au t̃u 6 En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )]
− En [∂θ Mu (Yu , Xu , θu )]′ δ̃u + 2Cn t̃u
6 En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )]

+ kSu,n k∞ kδ̃u k1 + 3Cn t̃u
6 En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )]
 √sb + s kS k

u
u
u,n ∞
+ t̃u p
+ 3Cn
φmin (b
su + su , u)

where the second inequality holds by calculations as in (M.3), and the third
inequality follows from
√
p
√
sbu + su
kδ̃u k1 6 sbu + su kδ̃u k2 6 p
k wu Xu′ δ̃u kPn ,2 .
φmin (b
su + su , u)

54

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Next, if t̃2u > q̄Au t̃u , then
q̄Au t̃u 6

q̄A
q̄Au
1/2
{En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )]}+ + u t̃u ,
2
2

1/2
so that t̃u 6 {En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )]}+ . On the other
hand, if t̃2u 6 q̄Au t̃u , then

t̃2u

6 {En [Mu (Yu , Xu , θeu )] − En [Mu (Yu , Xu , θu )]} + t̃u

!
√
sbu + su kSu,n k∞
p
+ 3Cn .
φmin (b
su + su )

1/2
{En [Mu (Yu , Xu , θeu )]−En [Mu (Yu , Xu , θu )]}+ +

!
√
sbu + su kSu,n k∞
p
+ 3Cn .
φmin (b
su + su )

Since for positive numbers a, b, c, inequality a2 6 b + ac implies a 6
we have
t̃u 6

√
b + c,

In both cases, the inequality in the asserted claim holds. This completes the
proof.

Proof of Lemma L.4. For brevity of notation, denote ǫ = ǫn . Also, let
An denote the event that the inequalities in Condition WL(iii) hold. Then
PP (An ) > 1 − ∆n . Further, by the triangle inequality,
(M.8)
b −1 En [Su ]k∞ 6 max kΨ
b −1 En [Su ]k∞
sup kΨ
u0
u0
ǫ
u∈U

u∈U

+

sup

u∈U ǫ ,u′ ∈U ,dU (u,u′ )6ǫ

b −1 En [Su ] − Ψ
b −1
kΨ
u0
u′ 0 En [Su′ ]k∞

where U ǫ is a minimal ǫ-net of U so that |U ǫ | 6 Nn .
For each k = 1, . . . , p and u ∈ U ǫ , we apply Lemma O.1 with Zi := Suki ,
′′
µ = 1, and ℓn = c′′ ϕ−1
n , where c is a small enough constant that can be
chosen to depend only on C and C̄. Then Condition WL(i,ii) implies that


γ
n1/6 Mn
−1
06Φ
−1
1−
6
2pNn
ℓn
where Mn = (EP [Z12 ])1/2 /(EP [Z13 ])1/3 , and so applying Lemma O.1, the
union bound, and the inequality |U ǫ | 6 Nn gives


√


| nEn [Suk ]|
γ

PP  sup max q
> Φ−1 1 − 2pN
n
ǫ
2
u∈U k∈[p]
En [Suk ]


γ
6 2pNn ·
(M.9)
· 1 + O(ϕ1/3
n ) 6 γ + o(γ)
2pNn

POST-REGULARIZATION CONFIDENCE REGIONS

55

since ϕn = o(1). Also, observe that
|En [Suk ]|
b −1 En [Su ]k∞ = sup max q
.
maxǫ kΨ
u0
u∈U
2 ]
u∈U ǫ k∈[p]
En [Suk

Therefore, (M.9) implies that with probability at least 1 − γ − o(γ),


γ
−1
−1/2 −1
b
(M.10)
max kΨu0 En [Su ]k∞ 6 n
Φ
1−
u∈U ǫ
2pNn
Further, by the triangle inequality,
sup
u∈U ǫ ,u′ ∈U ,dU (u,u′ )6ǫ

(M.11)

b −1 En [Su ] − Ψ
b −1
kΨ
u0
u′ 0 En [Su′ ]k∞
sup

6

u∈U ǫ ,u′ ∈U ,dU (u,u′ )6ǫ

(M.12)

+

sup

b −1 − Ψ
b −1
b
b −1
k(Ψ
u0
u′ 0 )Ψu0 k∞ kΨu0 En [Su ]k∞

u,u′ ∈U ,dU (u,u′ )6ǫ

b −1
kEn [Su − Su′ ]k∞ kΨ
u′ 0 k∞ .

To control the expression in (M.11), note that by Condition WL(ii), on the
b u0kk is bounded away from zero uniformly over u ∈ U and k ∈ [p].
event An , Ψ
Thus, we have uniformly over u ∈ U and k ∈ [p] that
b −1 − Ψ
b −1
b
b
b ′
b −1
b
b ′
|(Ψ
u0kk
u′ 0kk )Ψu0kk | = |Ψu0kk − Ψu 0kk |Ψu′ 0kk . |Ψu0kk − Ψu 0kk |

(M.13)

on the event An . Moreover, we have
sup
u,u′ ∈U ,d

U

(u,u′ )6ǫ

6
6

2
]}1/2 − {En [Su2′ k ]}1/2
max {En [Suk
k∈[p]


1/2
2
] − En [Su2′ k ]|
max |En [Suk

sup

u,u′ ∈U ,dU (u,u′ )6ǫ k∈[p]

1/2

2
2
− Su2′ k ]|
]| + |EP [Suk
. ϕ1/2
max 2|(En − EP )[Suk
n

sup

u,u′ ∈U ,dU (u,u′ )6ǫ k∈[p]

on the event An . Combining this bound with (M.13) implies that
sup
u,u′ ∈U ,dU (u,u′ )6ǫ

1/2
b −1 − Ψ
b −1
b
k(Ψ
u0
u′ 0 )Ψu0 k∞ . ϕn

on the event An . Also, using standard bounds for the tails of Gaussian
random variables gives


p
γ
−1
. log(2pNn /γ).
Φ
1−
2pNn

56

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Thus, on the intersection of events An and (M.10), we have
sup
u∈U ǫ ,u′ ∈U ,dU (u,u′ )6ǫ

b −1 − Ψ
b −1
b
b −1
k(Ψ
u0
u′ 0 )Ψu0 k∞ kΨu0 En [Su ]k∞

. (ϕn /n)1/2

p
log(pNn /γ).

Finally, on the event An , we have that the expression in (M.12) satisfies
sup
u,u′ ∈U ,dU (u,u′ )6ǫ

−1/2
b −1
.
kEn [Su − Su′ ]k∞ kΨ
u′ 0 k∞ 6 ϕn n

It follows that on the intersection of events An and (M.10), for n large
enough, we have


γ
c′ − c −1
−1
−1
b
b
·Φ
,
1−
sup
kΨu0 En [Su ]− Ψu′ 0 En [Su′ ]k∞ 6
c
2pNn
u∈U ǫ ,u′ ∈U ,dU (u,u′ )6ǫ

where we again used standard tail bounds for the tails of Gaussian random
variables. The asserted claim now follows by recalling the inequality (M.8)
and noting that PP (An ) > 1 − ∆n and that (M.10) holds with probability
at least 1 − γ − o(γ).

Proof of Lemma L.5. For j ∈ [p], let
n
o
n
o
Fj = (Y, X) 7→ Yu Xj : u ∈ U , Fj′ = (Y, X) 7→ Xj EP [Yu | X] : u ∈ U ,
n
o
Gj = (Y, X) 7→ Xj2 ζu2 : u ∈ U

where ζu = Yu − EP [Yu | X]. Note that the function F (Y, X) = kXk∞ is an
envelope both for Fj and for Fj′ for all j ∈ [p̃]. By assumption, F can be
chosen to satisfy kF kP,q 6 Kn .
Because Fj is a product of a VC-subgraph class of functions with index
bounded by CY and a single function, Lemma N.1(1) implies that its uniform
entropy numbers obey
(M.14)

log N (ǫkF kQ,2 , Fj , k · kQ,2 ) . log(e/ǫ),

0 < ǫ 6 1.

Also, Lemma N.2 implies that the uniform entropy numbers of Fj′ obey
log sup N (ǫkF kQ,2 , Fj′ , k · kQ,2 ) 6 log sup N
Q

Q

ǫ

2


kF kQ,2 , Fj , k · kQ,2 ,

0 < ǫ 6 1.

POST-REGULARIZATION CONFIDENCE REGIONS

57

Further, since Gj ⊂ (Fj − Fj′ )2 , G = 4F 2 is an envelope for Gj , and the
uniform entropy numbers of Gj obey for all ǫ ∈ (0, 1],

ǫ
(M.15) log N (ǫkGkQ,2 , Gj , k · kQ,2 ) 6 2 log N k2F kQ,2 , Fj − Fj′ , k · kQ,2
 2ǫ

6 2 log N kF kQ,2 , Fj , k · kQ,2
4

ǫ
+ 2 log N kF kQ,2 , Fj′ , k · kQ,2
4

ǫ
6 4 log sup N kF kQ,2 , Fj , k · kQ,2 ,
8
Q
where the first and the second inequalities follow from Lemma N.1(2), and
the third from the bound on uniform entropy numbers of Fj′ above. Hence,
Lemma N.1(2) implies that the uniform entropy numbers of G = ∪j∈[p]Gj
obey
log N (ǫkGkQ,2 , G, k · kQ,2 ) . log(p/ǫ), 0 < ǫ 6 1,

where G = 4F 2 is its envelope. Therefore, since |Suj | 6 2|Xj | and also
maxj6p EP [Xj4 ] 6 C̄ by assumption, Lemma O.2 implies that with probability at least 1 − (log n)−1 ,
r
log(npKn ) n2/q Kn2
2
sup max |(En − EP )[Suj ]| .
+
log(npKn ),
n
n
u∈U j6p
which gives (L.11).
To verify (L.10), note that
max EP [Xj2 (ζu − ζu′ )2 ]

sup

dU (u,u′ )61/n j∈[p]

sup

6
dU

(u,u′ )61/n

sup

6
dU

(u,u′ )61/n

sup

.
dU

(u,u′ )61/n

max EP [Xj2 (Yu − Yu′ )2 ]
j∈[p]

max{EP [Xj4 ]}1/2 {EP [(Yu − Yu′ )4 ]}1/2
j6p

|u − u′ |ν/2 . n−ν/2 .

Therefore, Lemma O.2 implies that we have with probability at least 1 −
(log n)−1 ,
1
sup
max |Gn (Xj (ζu − ζu′ ))|
kEn [Su − Su′ ]k∞ = √
n dU (u,u′ )61/n j∈p
dU (u,u′ )61/n
r
log(npKn ) n1/q Kn log(npKn )
.
+
,
n
n1+ν/2
sup

58

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

which gives (L.10).
Finally, to verify (L.12) note that uniformly over u, u′ ∈ U and j ∈ [p],
we have
2
|EP [Suj
− Su2′ j ]| = |EP [(Suj − Su′ j )(Suj + Su′ j )]|

1/2 
1/2
2
. EP [(Suj − Su′ j )2 ]
· E[Suj
] + EP [Su2′ j ]
1/2

. EP [Xj2 (Yu − Yu′ )2 ]

1/4 
1/4
. EP [Xj4 ]
· EP [(Yu − Yu′ )4 ]
. dU (u, u′ )ν/4 .

This completes the proof.



APPENDIX N: BOUNDS ON COVERING ENTROPY
Let (Wi )ni=1 be a sequence of independent copies of a random element W
taking values in a measurable space (W, AW ) according to a probability law
P . Let F be a set of suitably measurable functions f : W → R, equipped
with a measurable envelope F : W → R.
Lemma N.1 (Algebra for Covering Entropies).
(1) Let F be a VC subgraph class with a finite VC index k or any other class
whose entropy is bounded above by that of such a VC subgraph class, then
the uniform entropy numbers of F obey
sup log N (ǫkF kQ,2 , F, k · kQ,2 ) . 1 + k log(1/ǫ) ∨ 0
Q

(2) For any measurable classes of functions F and F ′ mapping W to R,
log N (ǫkF + F ′ kQ,2 , F + F ′ , k · kQ,2 )

6 log N 2ǫ kF kQ,2 , F, k · kQ,2 + log N
log N (ǫkF · F ′ kQ,2 , F · F ′ , k · kQ,2 )

6 log N 2ǫ kF kQ,2 , F, k · kQ,2 + log N

N (ǫkF ∨ F ′ kQ,2 , F ∪ F ′ , k · kQ,2 )

′
′
ǫ
2 kF kQ,2 , F , k
′
′
ǫ
2 kF kQ,2 , F , k


6 N (ǫkF kQ,2 , F, k · kQ,2 ) + N ǫkF ′ kQ,2 , F ′ , k · kQ,2 .


· kQ,2 ,

· kQ,2 ,

(3) For any measurable class of functions F and a fixed function f mapping
W to R,
log sup N (ǫk|f | · F kQ,2 , f · F, k · kQ,2 ) 6 log sup N (ǫ/2kF kQ,2 , F, k · kQ,2 )
Q

Q

POST-REGULARIZATION CONFIDENCE REGIONS

59

(4) Given measurable classes Fj and envelopes Fj , j = 1, . . . , k, mapping
W to R, a function φ : Rk → R such that for fj , gj ∈ Fj , |φ(f1 , . . . , fk ) −
P
φ(g1 , . . . , gk )| 6 kj=1 Lj (x)|fj (x) − gj (x)|, Lj (x) > 0, and fixed functions
f¯j ∈ Fj , the class of functions L = {φ(f1 , . . . , fk ) − φ(f¯1 , . . . , f¯k ) : fj ∈
Fj , j = 1, . . . , k} satisfies


k
X
, L, k · kQ,2 
Lj Fj
log sup N ǫ
Q

6

j=1

k
X
j=1

log sup N
Q

Q,2

ǫ
k kFj kQ,2 , Fj , k


· kQ,2 .

Proof. See Lemma L.1 in [5].



Lemma N.2 (Covering Entropy for Classes obtained as Conditional Expectations). Let F denote a class of measurable functions f : W × Y → R
with a measurableR envelope F . For a given f ∈ F, let f¯: W → R be the
function f¯(w) := f (w, y)dµw (y) where µw is a regular conditional probability distributionR over y ∈ Y conditional on w ∈ W. Set F̄ = {f¯: f ∈ F}
and let F̄ (w) := F (w, y)dµw (y) be an envelope for F̄. Then, for r, s > 1,
log sup N (ǫkF̄ kQ,r , F̄, k · kQ,r ) 6 log sup N ((ǫ/4)r kF kQ,s
e ),
e , F, k · kQ,s
Q

e
Q

where Q belongs to the set of finitely-discrete probability measures over W
e belongs to the set of finitely-discrete
such that 0 < kF̄ kQ,r < ∞, and Q
probability measures over W × Y such that 0 < kF kQ,s
e < ∞. In particular,
for every ǫ > 0 and any k > 1,
log sup N (ǫ, F̄ , k · kQ,k ) 6 log sup N (ǫ/2, F, k · kQ,k
e ).
Q

e
Q

Proof. See Lemma L.2 in [5].



Lemma N.3. Consider a mapping ũ 7→ ξũ from Ue = [0, 1]k into Rp and
the class of functions F = {x 7→ M(x′ ξũ ) : ũ ∈ Ue} mapping Rp into R where
M : R → R is L-Lipschitz. Assume that kξũ2 − ξũ1 k1 6 Ckũ2 − ũ1 k for all
ũ1 , ũ2 ∈ Ue for some constant C > 0. Then, for any M > 0 the uniform
entropy numbers of F satisfy
sup log N (ǫkF kQ,2 , F, k · kQ,2 ) 6 k log(3LCM k/ε),

for all 0 < ǫ 6 1,

Q

where F (x) = supũ∈Ue |M(x′ ξũ )| + M −1 kxk∞ , x ∈ Rp , is its envelope.

60

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Proof. Consider any f1 , f2 ∈ F. There exist ũ1 , ũ2 ∈ Ue such that
f1 (x) = M(x′ ξũ1 ) and f2 (x) = M(x′ ξũ2 ) for all x ∈ Rp . Therefore, since M
is L-Lipschitz, we have
|M(x′ ξũ2 ) − M(x′ ξũ1 )| 6 Lkxk∞ kξu2 − ξu1 k1 6 Lkxk∞ Ckũ2 − ũ1 k

6 LCM kũ2 − ũ1 k{M −1 kxk∞ + supũ∈Ue |M(x′ ξũ )|}
6 LCM kũ2 − ũ1 kF (x)

by definition of the envelope F (x) = M −1 kxk∞ + supũ∈Ue |M(x′ ξũ )|. Thus,
for any finitely discrete probability measure Q on Rp ,
kf2 − f1 kQ,2 6 LCM kũ2 − ũ1 k · kF kQ,2 .
√
√
Recall√that since B∞ ⊂ B2 k we have N (B∞ , k · k, ǫ) 6 N (B2 k, k · k, ǫ) 6
follows from√standard volume argu(1 + 2 k/ǫ)k where the last inequality
√
ments. Furthermore, for any ǫ 6 k we have 1 + 2 k/ǫ 6 3k/ǫ. Therefore
log N (ǫkF kQ,2 , F, k · kQ,2 ) 6 k log(3LCM k/ǫ).

Lemma N.4. Let F be a class of functions with an envelope F . Also,
let M : R → R be an L-Lipschitz function bounded in absolute value by a
constant M . Assume that for some positive constants C1 and C2 , the uniform
entropy numbers of F obey
sup log N (ǫkF kQ,2 , F, k · kQ,2 ) 6 C1 log(C2 /ǫ),

for all 0 < ǫ 6 1.

Q

Then for any constant K > 0, the uniform entropy numbers of the class of
functions M(F) = {M(f ) : f ∈ F} obey
sup log N (ǫkFM(F ) kQ,2 , M(F), k·kQ,2 ) 6 C1 log(C2 K/ǫ),

for all 0 < ǫ 6 1,

Q

where FM(F ) = M + LF/K is its envelope.
Proof. The result follows from the observation that for any f ′ , f ′′ ∈ F
and any finitely-discrete probability measure Q,
kM(f ′ ) − M(f ′′ )kQ,2 6 Lkf1 − f2 kQ,2 ,
so that if F can be covered by k balls of radius ǫkF kQ,2 (in the k · kQ,2
norm), then M(F) can be covered by k balls of radius ǫLkF kQ,2 (in the
same norm).


61

POST-REGULARIZATION CONFIDENCE REGIONS

APPENDIX O: SOME PROBABILISTIC INEQUALITIES
Lemma O.1 (Moderate deviations for self-normalized sums, [11]). Let
Z1 ,. . ., P
Zn be independent,
random variables and µ ∈ (0, 1]. Let
Pnzero-mean
2,
2 =
Z
Sn,n = ni=1 Zi , Vn,n
i=1 i
( n
)1/2 ( n
)1/{2+µ}
. 1X
1X
Mn =
E[Zi2 ]
E[|Zi |2+µ ]
>0
n
n
i=1

and 0 < ℓn 6 n

µ
2(2+µ)

i=1

Mn . Then for some absolute constant A,

µ
P(|Sn,n /Vn,n | > x)
Mn
A
− 1 6 2+µ , 0 6 x 6 n 2(2+µ)
− 1.
2(1 − Φ(x))
ℓn
ℓn

Let (Wi )ni=1 be a sequence of independent copies of a random element W
taking values in a measurable space (W, AW ) according to a probability law
P . Let F be a set of suitably measurable functions f : W → R, equipped
with a measurable envelope F : W → R.
Lemma O.2 (Maximal Inequality I, [9]). Work with the setup above.
Suppose that F > supf ∈F |f | is a measurable envelope for F with kF kP,q <
∞ for some q > 2. Let M = maxi6n F (Wi ) and σ 2 > 0 be any positive
constant such that supf ∈F kf k2P,2 6 σ 2 6 kF k2P,2 . Suppose that there exist
constants a > e and v > 1 such that
log sup N (ǫkF kQ,2 , F, k · kQ,2 ) 6 v log(a/ǫ), 0 < ǫ 6 1.
Q

Then
EP [kGn kF ] 6 K

s

vσ 2 log



akF kP,2
σ



vkM kP,2
log
+ √
n



akF kP,2
σ

!

,

where K is an absolute constant. Moreover, for every t > 1, with probability
> 1 − t−q/2 ,
kGn kF 6 (1 + α)EP [kGn kF ]
i
h
√
+ K(q) (σ + n−1/2 kM kP,q ) t + α−1 n−1/2 kM kP,2 t , ∀α > 0,

where K(q) > 0 is a constant depending only on q. In particular, setting
a > n and t = log n, with probability > 1 − c(log n)−1 ,
(O.1)
s

!


vkM kP,q
akF kP,2
akF kP,2
,
+ √
log
kGn kF 6 K(q, c) σ v log
σ
σ
n

62

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

where kM kP,q 6 n1/q kF kP,q and K(q, c) > 0 is a constant depending only
on q and c.
Lemma O.3 (Maximal Inequality II, [9]). Work with the setup above.
Suppose that the conditions of Lemma O.2 are satisfied. Then
i
h
EP kEn [f 2 (W )]kF − sup EP [f 2 (W )]
f ∈F

6



KkM kP,2
√
σ
n

s

v log



akF kP,2
σ





akF kP,2

vkM kP,2 log
σ
√
,
+
n

where K is an absolute constant.
Proof. The proof of the asserted claim coincides one-by-one with that
given for the corresponding inequality in Lemma 2.2 of [9], with the constant
3 replaced everywhere by the constant 2. At the end of the proof, the entropy
integral
Z δ
q
sup 1 + log N (ǫkF kQ,2 , F, k · kQ,2 )dǫ
J(δ) =
0

Q

is bounded by δ(v log(a/δ))1/2 under our condition on the uniform entropy
numbers of F.

APPENDIX P: A BOUND ON SPARSE EIGENVALUES FOR MANY
RANDOM MATRICES
The following lemma is a generalization of the main result in [14] to many
matrices.
Lemma P.1. Let U denote a finite set and (Xui )u∈U , i = 1, . . . , n, be
independent (across i) random vectors such that Xui ∈ Rp with p > 2 and
(E[max16i6n maxu∈U kXui k2∞ ])1/2 6 K. Furthermore, for k > 1, define
√

K k  1/2
δn := √
log |U | + log1/2 p + (log k)(log 1/2 p)(log1/2 n) ,
n
Then

E

"

sup

max En

kθk0 6k,kθk=1 u∈U

. δn2 + δn
up to a universal constant.




(θ Xu ) − E[(θ Xu ) ]
′

sup

kθk0 6k,kθk=1,u∈U

2

p

′

2

En E[(θ ′ Xu )2 ]

#

POST-REGULARIZATION CONFIDENCE REGIONS

63

Proof. For T ⊂ {1, . . . , p}, let BT = {θ ∈ Rp : kθk
P = 1, supp(θ) ⊆ T }.
Also, for T = ∪|T |=k BT × U , let R := sup(θ,u)∈T ( ni=1 (θ ′ Xui )2 )1/2 and
M := max16i6n,u∈U kXui k∞ . By symmetrization inequality, Lemma 6.3 in
[12], we have
"
#
 ′

2
′
2
nE
sup
max En (θ Xu ) − E[(θ Xu ) ]
kθk0 6k,kθk=1 u∈U

" "

6 2E E

sup
(θ,u)∈T

n
X

′

2

εi (θ Xui )

i=1

|X

##

,

where X = (Xui )u∈U ,16i6n and (εi )ni=1 is a sequence of independent Rademacher
random variables that are independent of X. A consequence of Lemma 4.5
in [12] (see equation (4.8)) gives
"
#
"
#
n
n
X
X
′
2
1/2
′
2
E sup
εi (θ Xui ) | X 6 (π/2) E sup
gi (θ Xui ) | X
(θ,u)∈T

(θ,u)∈T

i=1

i=1

where (gi )ni=1 is a sequence of independent standard normal random variables
that are independent of X. In turn, an application of Dudley’s integral gives
#
"
Z diam(T )
n
X
′
2
gi (θ Xui ) | X 6 8
log1/2 N (T , d, ǫ)dǫ
I1 := E sup
(θ,u)∈T

where

0

i=1

n
X
√
diam(T ) 6 2 sup ( (θ ′ Xui )4 )1/2 6 2 kM R
(θ,u)∈T i=1

√
using that |θ ′ Xui | 6 kXui k∞ kθk1 6 M k, and d is the corresponding Gaussian semi-metric. Furthermore, we have
log N (T , d, ǫ) 6 log |U | + max log N (∪|T |=k BT × {u}, d, ǫ),
u∈U

so that
Z
√
1/2
I1 6 16 kM R log |U | + 8

diam(T )
0

max log1/2 N (∪|T |=k BT × {u}, d, ǫ)dǫ.
u∈U

64

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Now, for any (θ, u) and (θ̄, u) in Duk := ∪|T |=k BT × {u}, we have
d((θ, u), (θ̄, u)) =

n
1/2
X
{(θ ′ Xui )2 − (θ̄ ′ Xui )2 }2
i=1

n
1/2
X
max |(θ − θ̄)′ Xui |
{(θ ′ Xui ) + (θ̄ ′ Xui )}2
6
16i6n

i=1

6 2 sup
(θ,u)∈T

n
X
i=1

(θ ′ Xui )2

1/2

max |(θ − θ̄)′ Xui | = 2Rkθ − θ̄kXu

16i6n

where we let kδkXu := max16i6n |δ′ Xui |. This implies that


√
√
N (Duk , d, ǫ) 6 N Duk / k, k · kXu , ǫ/{2 kR} .
√
Therefore, since diam(T ) 6 2 kM R, we have
Z

diam(T )

0

6

Z

max log1/2 N (Duk , d, ǫ)dǫ
u∈U
√
2 kM R

0

√
= 2 kR

Z

√
√
max log1/2 N (Duk / k, k · kXu , ǫ/{2 kR})dǫ
u∈U

M
0

√
max log1/2 N (Duk / k, k · kXu , ǫ)dǫ.
u∈U

√
√
Note that BT / k ⊂ BT1 and Duk / k ⊂ B 1 × {u} where B 1 := {θ ∈
Rp : kθk1 6 1} and BT1 = {θ ∈ B 1 : supp(θ) ⊆ T }. It follows from Lemma
−2
2
3.9 in [14] that N (B 1 , k · kXu , ǫ) 6 (2p)Aǫ M log n for all ǫ > 0 and some
universal constant A. Moreover, as in the discussion after Lemma 3.9 in [14],
we have N (BT1 , k · kXu , ǫ) 6 (1√+ 2M/ǫ)k for all ǫ> 0 and all T ⊂ {1, . . . , p}
with |T | = k, so that N (Duk / k, k · kXu , ǫ) 6 kp (1 + 2M/ǫ)k for all ǫ > 0.

POST-REGULARIZATION CONFIDENCE REGIONS

Therefore,
Z

0

M

65

√
max log1/2 N (Duk / k, k · kXu , ǫ)dǫ
u∈U

√
M/ k

 

p
k
log
6
(1 + 2M/ǫ) dǫ
k
0
Z M


Aǫ−2 M 2 log n
1/2
dǫ
(2p)
log
+
√
Z

1/2

M/ k

√
 
√ Z M/ k
M
1/2 p
log1/2 (1 + 2M/ǫ)dǫ
6 √ log
+ k
k
k
0
Z M
dǫ
+ A1/2 M (log1/2 n)(log1/2 (2p))
√
M/ k ǫ

√ 
6 M log1/2 p + M 1/2 + log1/2 (1 + 2 k)

√ 
+ A1/2 M (log1/2 n)(log1/2 (2p)) log M − log(M/ k)


. M log1/2 p + (log k)(log1/2 n)(log1/2 p)

up to a universal constant where in the third inequality, we used the fact
that integrating by parts gives
√
√
√ Z M/ k
log1/2 (1 + 2M/ǫ)dǫ 6 M (1/2 + log1/2 (1 + 2 k)).
k
0

Collecting the terms, we obtain


√
I1 . kM R log1/2 |U | + log1/2 p + (log k)(log 1/2 n)(log1/2 p) .
Therefore, since K > (E[M 2 ])1/2 , setting
√

K k  1/2
δn = √
log |U | + log1/2 p + (log k)(log1/2 n)(log1/2 p)
n

gives

I2 = E

"

sup

max En

kθk0 6k,kθk=1 u∈U




(θ ′ Xu )2 − E[(θ ′ Xu )2 ]

#

δn E[M R]
√
6 (δn /K)(E[M 2 ])1/2 (E[R2 /n])1/2 6 δn (E[R2 /n])1/2
K n

1/2
sup
En E[(θ ′ Xu )2 ]
. δn I2 +
.
.

kθk0 6k,kθk=1,u∈U

66

BELLONI CHERNOZHUKOV CHETVERIKOV WEI

Thus, because a 6 δn (a + b)1/2 implies a 6 δn2 + δn b1/2 , we have
p
En E[(θ ′ Xu )2 ]
I2 . δn2 + δn
sup
kθk0 6k,kθk=1,u∈U

up to an absolute constant. This completes the proof.



REFERENCES
[1] Belloni, A. and Chernozhukov, V. (2011). ℓ1 -penalized quantile regression for high
dimensional sparse models. Annals of Statistics, 39(1):82–130. ArXiv, 2009.
[2] Belloni, A. and Chernozhukov, V. (2013). Least squares after model selection in
high-dimensional sparse models. Bernoulli, 19(2):521–547. ArXiv, 2009.
[3] Belloni, A., Chernozhukov, V., and Kato, K. (2013). Robust inference in highdimensional approximately sparse quantile regression models. ArXiv, 2013.
[4] Belloni, A., Chernozhukov, V., and Wang, L. (2011). Square-root-lasso: Pivotal recovery of sparse signals via conic programming. Biometrika, 98(4):791–806. Arxiv,
2010.
[5] Belloni, A., Chernozhukov, V., Fernández-Val, I., and Hansen, C. (2013). Program
evaluation with high-dimensional data. ArXiv, 2013.
[6] Berlemann, M., Enkelmann, S., and Kuhlenkasper, T. (2014). Unraveling the relationship between presidential approval and the economy: a multidimensional semiparametric approach. Journal of Applied Econometrics.
[7] Bickel, P., Ritov, Y., and Tsybakov, A. (2009). Simultaneous analysis of Lasso and
Dantzig selector. Annals of Statistics, 37(4):1705–1732. ArXiv, 2008.
[8] Chernozhukov, V., Chetverikov, D., and Kato, K. (2014). Anti-concentration and
honest, adaptive confidence bands. The Annals of Statistics, 42(5):1787–1818. ArXiv,
2013.
[9] Chernozhukov, V., Chetverikov, D., and Kato, K. (2014). Gaussian approximation
of suprema of empirical processes. The Annals of Statistics, 42(4):1564–1597. ArXiv,
2012.
[10] Chernozhukov, V., Chetverikov, D., and Kato, K. (2015). Empirical and multiplier
bootstraps for suprema of empirical processes of increasing complexity, and related
gaussian couplings. ArXiv, 2015.
[11] Jing, B.-Y., Shao, Q.-M., and Wang, Q. (2003). Self-normalized Cramer-type large
deviations for independent random variables. Ann. Probab., 31(4):2167–2215.
[12] Ledoux, M. and Talagrand, M. (1991). Probability in Banach Spaces (Isoperimetry
and processes). Ergebnisse der Mathematik undihrer Grenzgebiete, Springer-Verlag.
[13] Negahban, S., Ravikumar, P., Wainwright, P., and Yu, B. (2012). A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers.
Statistical Science, 27(4):538–557. ArXiv, 2010.
[14] Rudelson, M. and Vershynin, R. (2008). On sparse reconstruction from fourier
and gaussian measurements. Communications on Pure and Applied Mathematics,
61:1025–1045.
[15] van der Vaart, A. and Wellner, J. (1996). Weak Convergence and Empirical Processes.
Springer Series in Statistics.
Fuqua School of Business
Duke University
100 Fuqua Drive
Durham, NC 27708, USA.
E-mail: abn5@duke.edu

Department of Economics and
Operations Research Center, MIT
50 Memorial Drive
Cambridge, MA 02142, USA.
E-mail: vchern@mit.edu

POST-REGULARIZATION CONFIDENCE REGIONS
Department of Economics, UCLA
Bunche Hall, Rm 8283
315 Portola Plaza
Los Angeles, CA 90095, USA.
E-mail: chetverikov@econ.ucla.edu

67

Department of Biostatistics
Columbia University
722 West 168th St, Rm 633
New York, NY 10032, USA.
E-mail: yw2148@cumc.columbia.edu

