arXiv:1312.7186v4 [] 23 Jun 2016

Valid Post-Selection Inference in
High-Dimensional Approximately Sparse
Quantile Regression Models
Alexandre Belloni
The Fuqua School of Business, Duke University
and
Victor Chernozhukov
Department of Economics, Massachusetts Institute of Technology
and
Kengo Kato
Graduate School of Economics, University of Tokyo
June 24, 2016
Abstract
This work proposes new inference methods for a regression coefficient of interest in
a (heterogeneous) quantile regression model. We consider a high-dimensional model
where the number of regressors potentially exceeds the sample size but a subset
of them suffice to construct a reasonable approximation to the conditional quantile
function. The proposed methods are (explicitly or implicitly) based on orthogonal
score functions that protect against moderate model selection mistakes, which are
often inevitable in the approximately sparse model considered in the present paper.
We establish the uniform validity of the proposed confidence regions for the quantile
regression coefficient. Importantly, these methods directly apply to more than one
variable and a continuum of quantile indices. In addition, the performance of the
proposed methods is illustrated through Monte-Carlo experiments and an empirical
example, dealing with risk factors in childhood malnutrition.

Keywords: quantile regression, confidence regions post model selection, orthogonal score
functions
1

1

Introduction

Many applications of interest require the measurement of the distributional impact of a
policy (or treatment) on the relevant outcome variable. Quantile treatment effects have
emerged as an important concept for measuring such distributional impacts (see, e.g.,
[30, 22]). In this work we focus on the quantile treatment effect ατ on a policy/treatment
variable d of an outcome of interest y in the (heteroskedastic) partially linear model:
τ -quantile(y | z, d) = dατ + gτ (z),
where gτ is the (unknown) confounding function of the other covariates z which can be
well approximated by a linear combination of p technical controls. Large p arises due to
the existence of many features (as in genomic studies and econometric applications) and/or
the use of basis expansions in non-parametric approximations. When p is comparable or
larger than the sample size n, this brings forth the need to perform model selection or
regularization.
We propose methods to construct estimates and confidence regions for the coefficient
of interest ατ based upon robust post-selection procedures. We establish the (uniform)
validity of the proposed methods in a non-parametric setting. Model selection in those
settings generically leads to a moderate mistake and traditional arguments based on perfect
model selection do not apply. Therefore, the proposed methods are developed to be robust
to such model selection mistakes. Furthermore, they are directly applicable to construction
of simultaneous confidence bands when d is multivariate and a continuum of quantile indices
is of interest.
Broadly speaking the main obstacle to construct confidence regions with (asymptotically) correct coverage is the estimation of the confounding function gτ that is (generically)
non-regular because of the high-dimensionality. To overcome this difficulty we construct
2

(explicitly or implicitly) an orthogonal score function which leads to a moment condition
that is immune to first-order mistakes in the estimation of the confounding function gτ .
The construction is based on preliminary estimation of the confounding function and properly partialling out the confounding factors z from the policy/treatment variable d. The
former can be achieved via ℓ1 -penalized quantile regression [2, 19] or post-selection quantile
regression based on ℓ1 -penalized quantile regression [2]. The latter is carried out by heteroscedastic post-Lasso [35, 1] applied to a density-weighted equation. Then we propose two
estimators for ατ based on: (i) a moment condition based on an orthogonal score function;
(ii) a density-weighted quantile regression with all the variables selected in the previous
steps. The latter method is reminiscent of the “post-double selection” method proposed
in [5, 6]. Explicitly or implicitly the last step estimates ατ by minimizing a Neyman-type
score statistic [31].1
Under mild moment conditions and approximate sparsity assumptions, we establish
that the estimator α̌τ , as defined by either method (see Algorithms 2.1 and 2.2 below), is
root-n consistent and asymptotically normal,
√
σn−1 n(α̌τ − ατ )
where

N(0, 1),

(1.1)

denotes convergence in distribution; in addition the estimator α̌τ admits a (piv-

otal) linear representation. Hence the confidence region defined by
√
Cξ,n := {α ∈ R : |α − α̌τ | 6 σ
bn Φ−1 (1 − ξ/2)/ n}

(1.2)

has asymptotic coverage probability of 1 − ξ provided that the estimate σ
bn2 is consistent

for σn2 , namely, σ
bn2 /σn2 = 1 + oP (1). In addition, we establish that a Neyman-type score
1

We mostly focus on selection as a means of regularization, but certainly other regularizations (e.g. the

use of ℓ1 -penalized fits per se) are possible, although they perform no better than the methods we focus

on.

3

statistic Ln (α) is asymptotically distributed as the chi-squared distribution with one degree
of freedom when evaluated at the true value α = ατ , namely,
χ2 (1),

nLn (ατ )

(1.3)

which in turn allows the construction of another confidence region:
Iξ,n := {α ∈ Aτ : nLn (α) 6 (1 − ξ)-quantile of χ2 (1)},

(1.4)

which has asymptotic coverage probability of 1 − ξ. These convergence results hold under
array asymptotics, permitting the data-generating process P = Pn to change with n, which
implies that these convergence results hold uniformly over large classes of data-generating
processes. In particular, our results do not require separation of regression coefficients away
from zero (the so-called “beta-min” conditions) for their validity. Importantly, we discuss
how the procedures naturally allow for construction of simultaneous confidence bands for
many parameters based on a (pivotal) linear representation of the proposed estimator.
Several recent papers study the problem of constructing confidence regions after model
selection while allowing p ≫ n. In the case of linear mean regression, [5] proposes a
double selection inference in a parametric setting with homoscedastic Gaussian errors; [6]
studies a double selection procedure in a non-parametric setting with heteroscedastic errors;
[40] and [37] propose methods based on ℓ1 -penalized estimation combined with “one-step”
correction in parametric models. Going beyond mean regression models, [37] provides high
level conditions for the one-step estimator applied to smooth generalized linear problems,
[7] analyzes confidence regions for a parametric homoscedastic LAD regression model under
primitive conditions based on the instrumental LAD regression, and [9] provides two postselection procedures to build confidence regions for the logistic regression. None of the
aforementioned papers deal with the problem of the present paper.
4

Although related in spirit with our previous work [6, 7, 9], new tools and major departures from the previous works are required. First is the need to accommodate the
non-differentiability of the loss function (which translates into discontinuity of the score
function) and the non-parametric setting. In particular, we establish new finite sample
bounds for the prediction norm on the estimation error of ℓ1 -penalized quantile regression
in nonparametric models that extend results of [2, 19]. Perhaps more importantly, the use
of post-selection methods in order to reduce bias and improve finite sample performance
requires sparsity of the estimates. Although sharp sparsity bounds for ℓ1 -penalized methods are available for smooth loss functions, those are not available for quantile regression
precisely due to the lack of differentiability. This led us to developing sparse estimates with
provable guarantees by suitable truncation while preserving the good rates of convergence
despite of possible additional model selection mistakes. To handle heteroscedsaticity, which
is a common feature in many applications, consistent estimation of the conditional density
is necessary whose analysis is new in high-dimensions. Those estimates are used as weights
in the weighted Lasso estimation for the auxiliary regression ((2.7) below). In addition,
we develop new finite sample bounds for Lasso with estimated weights as the zero mean
condition is not assumed to hold for each observation but rather to the average across all
observations. Because the estimation of the conditional density function is at a slower rate,
it affects penalty choices, rates of convergence, and sparsity of the Lasso estimates.
This work and some of the papers cited above achieve an important uniformity guarantee with respect to the (unknown) values of the parameters. These uniform properties
translate into more reliable finite sample performance of the proposed inference procedures
because they are robust with respect to (unavoidable) model selection mistakes. There
is now substantial theoretical and empirical evidence on the potential poor finite sample
performance of inference methods that rely on perfect model selection when applied to
5

models without separation from zero of the coefficients (i.e., small coefficients). Most of
the criticism of these procedures are consequence of negative results established in [27],
[29], and the references therein.
Notation. We work with triangular array data {ωi,n : i = 1, . . . , n; n = 1, 2, 3, . . . }
where for each n, {ωn,i ; i = 1, . . . , n} is defined on the probability space (Ω, S, Pn ). Each

′
′
ωi,n = (yi,n
, zi,n
, d′i,n )′ is a vector which are i.n.i.d., that is, independent across i but not

necessarily identically distributed. Hence all parameters that characterize the distribution
of {ωi,n : i = 1, . . . , n} are implicitly indexed by Pn and thus by n. We omit this dependence
P
from the notation for the sake of simplicity. We use En to abbreviate the notation n−1 ni=1 ;
P
for example, En [f ] := En [f (ωi )] := n−1 ni=1 f (ωi ). We also use the following notation:
P
Ē[f ] := E [En [f ]] = E [En [f (ωi )]] = n−1 ni=1 E[f (ωi )]. The ℓ2 -norm is denoted by k · k; the

ℓ0 -“norm” k · k0 denotes the number of non-zero components of a vector; and the ℓ∞ -norm

k · k∞ denotes the maximal absolute value in the components of a vector. Given a vector
δ ∈ Rp and a set of indices T ⊂ {1, . . . , p}, we denote by δT ∈ Rp the vector in which

δT j = δj if j ∈ T and δT j = 0 if j ∈
/ T.

2

Setting

For a quantile index τ ∈ (0, 1), we consider a partially linear conditional quantile model
yi = di ατ + gτ (zi ) + ǫi , τ -quantile(ǫi | di , zi ) = 0, i = 1, . . . , n,

(2.5)

where yi is the outcome variable, di is the policy/treatment variable, and confounding
factors are represented by the variables zi which impact the equation through an unknown
function gτ . We shall use a large number p of technical controls xi = X(zi ) to achieve an

6

accurate approximation to the function gτ in (2.5) which takes the form:
gτ (zi ) = x′i βτ + rτ i , i = 1, . . . , n,

(2.6)

where rτ i denotes an approximation error. We view βτ and rτ as nuisance parameters while
the main parameter of interest is ατ which describes the impact of the treatment on the
conditional quantile (i.e., quantile treatment effect).
In order to perform robust inference with respect to model selection mistakes, we construct a moment condition based on a score function that satisfies an additional orthogonality property that makes them immune to first-order changes in the value of the nuisance
parameter. Letting fi = fǫi (0 | di , zi ) denote the conditional density at 0 of the disturbance
term ǫi in (2.5), the construction of the orthogonal moment condition is based on the linear
projection of the regressor of interest di weighted by fi on the xi variables weighted by fi
fi di = fi x′i θ0τ + vi ,

i = 1, . . . , n, Ē[fi xi vi ] = 0,

(2.7)

where θ0τ ∈ arg min Ē[fi2 (di − x′i θ)2 ]. The orthogonal score function ψi (α) := (1{yi 6
di α + x′i βτ + rτ } − τ )vi leads to a moment condition to estimate ατ ,
E[(1{yi 6 di ατ + x′i βτ + rτ i } − τ )vi ] = 0,

(2.8)

and satisfies the following orthogonality condition with respect to first-order changes in the
value of the nuisance parameters βτ and θ0τ :
∂β Ē[(1{yi 6 di ατ + x′i β + rτ i } − τ )fi (di − x′i θ0τ )]
∂θ Ē[(1{yi 6 di ατ + x′i βτ + rτ i } − τ )fi (di − x′i θ)]

β=βτ

θ=θ0τ

= 0, and
= 0.

(2.9)

In order to handle the high-dimensional setting, we assume that βτ and θ0τ are approximately sparse, namely, it is possible to choose sparse vector βτ and θτ such that:
kθτ k0 6 s, kβτ k0 6 s, Ē[(x′i θ0τ − x′i θτ )2 ] . s/n and Ē[(g(zi ) − x′i βτ )2 ] . s/n.
7

(2.10)

The latter equation requires that it is possible to choose the sparsity index s so that the
mean squared approximation error is of no larger order than the variance of the oracle
estimator for estimating the coefficients in the approximation. See [13] for a detailed
discussion of this notion of approximate sparsity.

2.1

Methods

The methodology based on the orthogonal score function (2.8) can be used for construction of many different estimators that have the same first-order asymptotic properties but
potentially different finite sample behaviors. In the main part of the paper we present two
such procedures in detail (the discussion on additional variants can be found in Subsection
1.1 of the Supplementary Appendix). Our procedures use ℓ1 -penalized quantile regression
and ℓ1 -penalized weighted least squares as intermediate steps (we collect the recommended
choices of the user-chosen parameters in Remark 2.1 below). The first procedure stated in
Algorithm 2.1 is based on the explicit construction of the orthogonal score function.
Algorithm 2.1 (Orthogonal score function.)
Step 1. Compute (b
ατ , βbτ ) from ℓ1 -penalized quantile regression of y on d and x.
Step 2. Compute (e
ατ , βeτ ) from quantile regression of y on d and {xj : |βbτ j | > λτ /{En [x2 ]}1/2 }.
ij

Step 3. Estimate the conditional density fb via (2.15) or (2.16).
Step 4. Compute θeτ from the post-Lasso estimator of fbd on fbx.
Step 5. Construct the score function ψbi (α) = (τ − 1{yi 6 di α + x′ βeτ })fbi (di − x′ θeτ ).
i

i

Step 6. For Ln (α) = |En [ψbi (α)]|2 /En [ψbi2 (α)], set β̌τ = βeτ and α̌τOS ∈ arg minα∈Aτ Ln (α).

Step 6 of Algorithm 2.1 solves the empirical analog of (2.8). We will show validity of the

confidence regions for ατ defined in (1.2) and (1.4). We note that the truncation in Step
2 for the solution of the penalized quantile regression (provably) induces a sparse solution
8

with the same rate of convergence as the original estimator. This is required because the
post-selection methods exhibit better finite sample behaviors in our simulations.
The second algorithm is based on selecting relevant variables from equations (2.5) and
(2.7), and running a weighted quantile regression.
Algorithm 2.2 (Weighted Double Selection.)
Step 1. Compute (b
ατ , βbτ ) from ℓ1 -penalized quantile regression of y on d and x.
Step 2. Estimate the conditional density fb via (2.15) or (2.16).

Step 3. Compute θbτ from the Lasso estimator of fbd on fbx.
Step 4. Compute (α̌τDS , β̌τ ) from quantile regression of fby on fbd and {fbxj : j ∈ supp(θbτ )}∪
{fbxj : |βbτ j | > λτ /{En [x2 ]}1/2 }.
ij

Although the orthogonal score function is not explicitly constructed in Algorithm 2.2,

inspection of the proof reveals that an orthogonal score function is constructed implicitly
via the optimality conditions of the weighted quantile regression in Step 4.
Comment 2.1 (Choices of User-Chosen Parameters) For γ = 0.05/n, we set the
penalty levels for the heteroscedastic Lasso and the ℓ1 -penalized quantile regression as
p
√
λ := 1.1 n2Φ−1 (1 − γ/2p) and λτ := 1.1 nτ (1 − τ )Φ−1 (1 − γ/2p).
(2.11)

bτ = diag[Γ
bτ jj , j = 1, . . . , p] is a diagonal matrix defined by the folThe penalty loading Γ
lowing procedure: (1) Compute the post-Lasso estimator θe0 based on λ and initial values
τ

bτ jj = max16i6n kfbi xi k∞ {En [fb2 d2 ]}1/2 . (2) Compute the residuals b
Γ
vi = fbi (di − x′i θeτ0 ) and
i i
update

bτ jj =
Γ

q

En [fbi2 x2ij b
vi2 ], j = 1, . . . , p.

(2.12)

In Algorithm 2.1 we have used the following parameter space for α:
Aτ = {α ∈ R : |α − α
eτ | 6 10{En [d2i ]}−1/2 / log n}.
9

(2.13)

Comment 2.2 (Estimating Standard Errors) There are different possible choices of
estimators for σn :
i
h
−1
2
2
σ
b1n
:= τ (1 − τ ) (En [e
vi2 ]) , σ
b2n
:= τ (1 − τ ) {En [fbi2 (di , x′iŤ )′ (di , x′iŤ )]}−1 ,
11

−2
2
′
2 2
b
σ
b3n := En [fi di e
vi ]
En [(1{yi 6 di α̌τ + xi β̌τ } − τ ) vei ],

(2.14)

where Ť = supp(β̌τ ) ∪ supp(θbτ ) is the set of controls used in the double selection quantile

regression. Although all three estimates are consistent under similar regularities conditions,
their finite sample behaviors might differ. Based on the small-sample performance in computational experiments, we recommend the use of σ
b3n for the orthogonal score estimator
and σ
b2n for the double selection estimator.

2.2

Estimation of Conditional Density Function

The implementation of the algorithms in Section 2.1 requires an estimate of the conditional
density function fi which is typically unknown under heteroscedasticity. Following [22], we
shall use the observation that 1/fi = ∂Q(τ | di , zi )/∂τ to estimate fi where Q(· | di , zi )

b | zi , di ) denote an
denotes the conditional quantile function of the outcome. Let Q(u
estimate of the conditional u-quantile function Q(u | zi , di ), based on either ℓ1 -penalized

quantile regression or an associated post-selection method, and let h = hn → 0 denote a
bandwidth parameter. Then an estimator of fi can be constructed as
fbi =

2h
b + h | zi , di ) − Q(τ
b − h | zi , di )
Q(τ

.

(2.15)

When the conditional quantile function is three times continuously differentiable, this estimator is based on the first order partial difference of the estimated conditional quantile
function, and so it has the bias of order h2 . Under additional smoothness assumptions, an

10

estimator that has a bias of order h4 is given by
fbi =

h
3 b
4 {Q(τ

b − h | zi , di )} −
+ h | zi , di ) − Q(τ

1 b
12 {Q(τ

b − 2h | zi , di )}
+ 2h | zi , di ) − Q(τ

. (2.16)

Comment 2.3 (Implementation of the estimates fbi ) There are several possible choices
of tuning parameters to construct the estimates fbi . In particular the bandwidth choices set
in the R package ‘quantreg’ from [23] exhibits good empirical behavior. In our theoretical
analysis we coordinate the bandwidth choice with the choice of the penalty level of the density weighted Lasso. In Subsection 1.4 of the Supplementary Appendix we discuss in more
detail the requirements associated with different choices for penalty level λ and bandwidth
h. Together with the recommendations made in Remark 2.1, we suggest to construct fbi as

in (2.15) with bandwidth h := min{n−1/6 , τ (1 − τ )/2}.

3

Theoretical Analysis

3.1

Regularity Conditions

In this section we provide regularity conditions that are sufficient for validity of the main
estimation and inference results. In what follows, let c, C, and q be given (fixed) constants
with c > 0, C > 1 and q > 4, and let ℓn ↑ ∞, δn ↓ 0, and ∆n ↓ 0 be given sequences of
positive constants. We assume that the following condition holds for the data generating
process P = Pn for each n.
Condition AS(P). (i) Let {(yi , di , xi = X(zi )) : i = 1, . . . , n} be independent random
vectors that obey the model described in (2.5) and (2.7) with kθ0τ k + kβτ k + |ατ | 6 C. (ii)

2
There exists s > 1 and vectors βτ and θτ such that x′i θ0τ = x′i θτ + rθτ i , kθτ k0 6 s, Ē[rθτ
i] 6

11

Cs/n, kθ0τ − θτ k1 6 s

p

log(pn)/n, and gτ (zi ) = x′i βτ + rτ i , kβτ k0 6 s, Ē[rτ2i ] 6 Cs/n.

(iii) The conditional distribution function of ǫi is absolutely continuous with continuously
differentiable density fǫ |d ,z (· | di , zi ) such that 0 < f 6 fi 6 sup fǫ |d ,z (t | di , zi ) 6 f¯ 6 C
i

and

supt |fǫ′i |di ,zi (t

i

t

i

i

i

i

| di , zi )| 6 f¯′ 6 C.

Condition AS(i) imposes the setting discussed in Section 2 in which the error term ǫi has
zero conditional τ -quantile. The approximate sparsity on the high-dimensional parameters
is stated in Condition AS(ii). Condition AS(iii) is a standard assumption on the conditional
density function in the quantile regression literature (see [22]) and the instrumental quantile
regression literature (see [15]). Next we summarize the moment conditions we impose.
Condition M(P). (i) We have Ē[{(di , x′i )ξ}2 ] > ckξk2 and Ē[{(di , x′i )ξ}4] 6 Ckξk4
for all ξ ∈ Rp+1 , c 6 min16j6p Ē[|fi xij vi − E[fi xij vi ]|2 ]1/2 6 max16j6p Ē[|fi xij vi |3 ]1/3 6 C.

(ii) The approximation error satisfies |Ē[fi vi rτ i ]| 6 δn n−1/2 and Ē[(x′i ξ)2rτ2i ] 6 Ckξk2Ē[rτ2i ]

for all ξ ∈ Rp . (iii) Suppose that Kq = E[max16i6n k(di , vi , x′i )′ kq∞ ]1/q is finite and satisfies
(Kq2 s2 + s3 ) log3 (pn) 6 nδn and Kq4 s log(pn) log3 n 6 δn n.

Condition M(i) imposes moment conditions on the variables. Condition M(ii) imposes
requirements on the approximation error. Condition M(iii) imposes growth conditions on s,
p, and n. In particular these conditions imply that the population eigenvalues of the design
matrix are bounded away from zero and from above. They ensure that sparse eigenvalues
and restricted eigenvalues are well behaved which are used in the analysis of penalized
estimators and sparsity properties needed for the post-selection estimator.
Comment 3.1 (Handling Approximately Sparse Models) To handle approximately
sparse models to represent gτ in (2.6), we assume a near orthogonality between rτ and f v,
namely Ē[fi vi rτ i ] = o(n−1/2 ). This condition is automatically satisfied if the orthogonality
condition in (2.7) can be strengthen to E[fi vi | zi ] = 0. However, it can be satisfied under
weaker conditions as discussed in Subsection 1.2 of the Supplementary Appendix.
12

Our last set of conditions pertains to the estimation of the conditional density function
(fi )ni=1 which has a non-trivial impact on the analysis. We denote by U the finite set of
quantile indices used in the estimation of the conditional density. Under mild regularity
conditions the estimators (2.15) and (2.16) achieve
!
X
1
b + u | di , zi ) − Q(τ
b − u | di , zi )| ,
fbi − fi = O hk̄ +
|Q(τ
h u∈U

(3.17)

where k̄ = 2 for (2.15) and k̄ = 4 for (2.16). Condition D summarizes sufficient conditions
to account for the impact of density estimation via (post-selection) ℓ1 -penalized quantile
regression estimators.
Condition D. For u ∈ U, assume that u-quantile(yi | zi , di ) = di αu + x′i βu + rui ,

2
fui = fyi |di ,zi (di αu + x′i βu + rui | zi , di ) > c where Ē[rui
] 6 δn n−1/2 and |rui | 6 δn h for all
 k̄ 2
nh
+
,
i = 1, . . . , n, and the vector βu satisfies kβu k0 6 s. (ii) For seθτ = s + ns log(n∨p)
h2 λ2
λ
p
√
suppose hk̄ seθτ log(pn) 6 δn , h−2 Kq2 s log(pn) 6 δn n, λKq2 s 6 δn n, h−2 se
sθτ log(pn) 6
p
2
3
sθτ log(pn) 6 δn n, and Kq2 seθτ log (pn) log (n) 6 δn n.
δn n, λ se

Condition D(i) imposes the approximately sparse assumption for the u-conditional

quantile function for quantile indices u in a neighborhood of the quantile index τ . Condition D(ii) provides growth conditions relating s, p, n, h and λ. Subsection 1.4 in the
Supplementary Appendix discusses specific choices of penalty level λ and of bandwidth h

together with the implied conditions on the triple (s, p, n). In particular they imply that
sparse eigenvalues of order seθτ are well behaved.

3.2

Main results

In this section we state our theoretical results. We establish the first order equivalence of
the proposed estimators. We construct the estimators as defined as in Algorithm 2.1 and
13

bτ as in (2.12), and Aτ as in (2.13). The choices of λ
2.2 with parameters λτ as in (2.11), Γ

and h satisfy Condition D.

Theorem 1 Let {Pn } be a sequence of data-generating processes. Assume that conditions
AS(P), M(P) and D(P) are satisfied with P = Pn for each n. Then the orthogonal score
estimator α̌τOS based on Algorithm 2.1 and the double selection estimator α̌τDS based on Al√
gorithm 2.2 are first order equivalent, n(α̌τOS − α̌τDS ) = oP (1). Moreover, either estimator
satisfies

√
σn−1 n(α̌τ − ατ ) = Un (τ ) + oP (1)

where σn2 = τ (1 − τ )Ē[vi2 ]−1

and Un (τ )

N(0, 1),
P
and Un (τ ) := τ (1 − τ ){Ē[vi2 ]}−1/2 n−1/2 ni=1 (τ − 1{Ui 6 τ })vi ,

and U1 , . . . , Un are i.i.d. uniform random variables on (0, 1) independent from v1 , . . . , vn .
Furthermore,
nLn (ατ ) = U2n (τ ) + oP (1) and U2n (τ )

χ2 (1).

The result continues to apply if σn2 is replaced by any of the estimators in (2.14), namely,
σ
bkn /σn = 1 + oP (1) for k = 1, 2, 3.

The asymptotically correct coverage of the confidence regions Cξ,n and Iξ,n as defined

in (1.2) and (1.4) follows immediately. Theorem 1 relies on post model selection estimators
which in turn rely on achieving sparse estimates βbτ and θbτ . The sparsity of θbτ is derived in

Section 2.2 in the Supplemental Appendix under the recommended penalty choices. The
sparsity of βbτ is not guaranteed under the recommended choices of penalty level λτ which

leads to sharp rates. We bypass that by truncating small components to zero (as in Step
2 of Algorithm 2.1) which (provably) preserves the same rate of convergence and ensures
the sparsity.
In addition to the asymptotic normality, Theorem 1 establishes that the rescaled esti√
mation error σn−1 n(α̌τ − ατ ) is approximately equal to the process Un (τ ), which is pivotal
14

conditional on v1 , . . . , vn . Such a property is very useful since it is easy to simulate Un (τ )
conditional on v1 , . . . , vn . Thus this representation provides us with another procedure to
construct confidence intervals without relying on asymptotic normality which are useful for
the construction of simultaneous confidence bands; see Section 3.3.
Importantly, the results in Theorem 1 allow for the data generating process to depend on
the sample size n and have no requirements on the separation from zero of the coefficients.
In particular these results allow for sequences of data generating processes for which perfect
model selection is not possible. In turn this translates into uniformity properties over a
large class of data generating processes. Next we formalize these uniform properties. We let
Pn denote the collection of distributions P for the data {(yi , di , zi′ )′ }ni=1 such that Conditions
AS, M and D are satisfied for given n. This is the collection of all approximately sparse
models where the above sparsity conditions, moment conditions, and growth conditions are
satisfied. Note that the uniformity results for the approximately sparse and heteroscedastic
case are new even under fixed p asymptotics.
Corollary 1 (Uniform Validity of Confidence Regions) Let Pn be the collection of

all distributions of {(yi , di , zi′ )′ }ni=1 for which Conditions AS, M, and D are satisfied for
given n > 1. Then the confidence regions Cξ,n and Iξ,n defined based on either the orthogonal
score estimator or by the double selection estimator are asymptotically uniformly valid
lim sup |P(ατ ∈ Cξ,n ) − (1 − ξ)| = 0

n→∞ P∈Pn

3.3

and

lim sup |P(ατ ∈ Iξ,n ) − (1 − ξ)| = 0.

n→∞ P∈Pn

Simultaneous Inference over τ and Many Coefficients

In some applications we are interested on building confidence intervals that are simultaneously valid for many coefficients as well as for a range of quantile indices τ ∈ T ⊂ (0, 1) a
15

fixed compact set. The proposed methods directly extend to the case of d ∈ RK and τ ∈ T
τ -quantile(y | z, d) =

K
X

dj ατ j + g̃τ (z).

j=1

Indeed, for each τ ∈ T and each k = 1, . . . , K, estimates can be obtained by applying the
methods to the model (2.5) as
τ -quantile(y | z, d) = dk ατ k + gτ (z) where gτ (z) := g̃τ (z) +

X

d j ατ j .

j6=k

For each τ ∈ T , Step 1 and the conditional density function fi , i = 1, . . . , n, are the same for
all k = 1, . . . , K. However, Steps 2 and 3 adapt to each quantile index and each coefficient
of interest. The uniform validity of ℓ1 -penalized methods for a continuum of problems
(indexed by T in our case) has been established for quantile regression in [2] and for least
squares in [10]. The conclusions of Theorem 1 are uniformly valid over k = 1, . . . , K and
τ ∈ T (in the ℓ∞ -norm).
Simultaneous confidence bands are constructed by defining the following critical value




∗
n
c (1 − ξ) = inf t : P
sup
|Un (τ, k)| 6 t | {di , zi }i=1 > 1 − ξ ,
τ ∈T ,k=1,...,K

where the random variable Un (τ, k) is pivotal conditional on the data, namely,
n
{τ (1 − τ )Ē[vτ2ki ]}−1/2 X
√
Un (τ, k) :=
(τ − 1{Ui 6 τ })vτ ki ,
n
i=1

where Ui are i.i.d. uniform random variables on (0, 1) independent from {di , zi }ni=1 , and

vτ ki is the error term in the decomposition (2.7) for the pair (τ, k). Therefore c∗ (1 − ξ)
can be estimated since estimates of vτ ki and σnτ k , τ ∈ T and k = 1, . . . , K, are available.
Uniform confidence bands can be defined as
√
√
[α̌τ k − σnτ k c∗ (1 − ξ)/ n, α̌τ k + σnτ k c∗ (1 − ξ)/ n] for τ ∈ T , k = 1, . . . , K.
16

4

Empirical Performance

4.1

Monte-Carlo Experiments

Next we provide a simulation study to assess the finite sample performance of the proposed
estimators and confidence regions. We focus our discussion on the double selection estimator as defined in Algorithm 2.2 which exhibits a better performance. We consider the
median regression case (τ = 1/2) under the following data generating process:
y = dατ + x′ (cy ν0 ) + ǫ,
d = x′ (cd ν0 ) + ṽ,

ǫ ∼ N(0, {2 − µ + µd2 }/2),

ṽ ∼ N(0, 1),

(4.18)
(4.19)

where ατ = 1/2, θ0j = 1/j 2 , j = 1, . . . , p, x = (1, z ′ )′ consists of an intercept and covariates
z ∼ N(0, Σ), and the errors ǫ and ṽ are independent. The dimension p of the covariates
x is 300, and the sample size n is 250. The regressors are correlated with Σij = ρ|i−j| and
p
ρ = 0.5. In this case, fi = 1/{ π(2 − µ + µd2 )} so that the coefficient µ ∈ {0, 1} makes

the conditional density function of ǫ homoscedastic if µ = 0 and heteroscedastic if µ = 1.
The coefficients cy and cd are used to control the R2 in the equations: y −dατ = x′ (cy ν0 ) + ǫ
and d = x′ (cd ν0 ) + ṽ ; we denote the values of R2 in each equation by Ry2 and Rd2 . We

consider values (Ry2 , Rd2 ) in the set {0, .1, .2, . . . , .9} × {0, .1, .2, . . . , .9}. Therefore we have
100 different designs and perform 500 Monte-Carlo repetitions for each design. For each
repetition we draw new vectors xi ’s and errors ǫi ’s and ṽi ’s.
We perform estimation of fi ’s via (2.15) even in the homoscedastic case (µ = 0), since
we do not want to rely on whether the assumption of homoscedasticity is valid or not. We
use σ
b2n as the standard error estimate for the post double selection estimator based on

Algorithm 2.2. As a benchmark we consider the standard (naive) post-selection procedure

that applies ℓ1 -penalized median regression of y on d and x to select a subset of covariates
17

that have predictive power for y, and then runs median regression of y on d and the
selected covariates, omitting the covariates that were not selected. We report the rejection
frequency of the confidence intervals with the nominal coverage probability of 95%. Ideally
we should see the rejection rate of 5%, the nominal level, regardless of the underlying
generating process P ∈ Pn . This is the so called uniformity property or honesty property
of the confidence regions (see, e.g., [33], [32], and [28]).
In the homoscedastic case, reported on the left column of Figure 1, we have the empirical rejection probabilities for the naive post-selection procedure on the first row. These
empirical rejection probabilities deviate strongly away from the nominal level of 5%, demonstrating the striking lack of robustness of this standard method. This is perhaps expected
due to the Monte-Carlo design having regression coefficients not well separated from zero
(that is, the “beta min” condition does not hold here). In sharp contrast, we see that the
proposed procedure performs substantially better, yielding empirical rejection probabilities
close to the desired nominal level of 5%. In the right column of Figure 1 we report the
results for the heteroscedastic case (µ = 1). Here too we see the striking lack of robustness
of the naive post-selection procedure. We also see that the confidence region based on
the post-double selection method significantly outperforms the standard method, yielding
empirical rejection probabilities close to the nominal level of 5%.

4.2

Inference on Risk Factors in Childhood Malnutrition

The purpose of this section is to examine practical usefulness of the new methods and
contrast them with the standard post-selection inference (that assumes perfect selection).
We will assess statistical significance of socio-economic and biological factors on children’s malnutrition, providing a methodological follow up on the previous studies done by
[17] and [21]. The measure of malnutrition is represented by the child’s height, which will
18

Naive Post Selection (C0.05,n) rp(0.05)

Naive Post Selection (C0.05,n) rp(0.05)

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0

0
0.8

0.8
0.6

0.8

0.6
0.4
0.2

0.6
0.4

Ry2

Rd2

0.2
0

Rd2

0.8
0.6

0.4
0

0.4
0.2

Double Selection (C0.05,n) rp(0.05)

0.2
0

0

Ry2

Double Selection (C0.05,n) rp(0.05)

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0

0
0.8

0.8
0.6

0.8

0.6
0.4
0.2

Rd2

0.8
0.6

0.6

0.4

0.4

Ry2

Rd2

0.2
0

0

0.4
0.2

0.2
0

0

Ry2

Figure 1: The left column is the homoscedastic design (µ = 0), and the right column is the heteroscedastic
design. We the figure displays the rejection probabilities of the following confidence regions with nominal
coverage of 95%: (a) naive selection procedure (1st row), and (b) C0.05,n based on the post double selection
estimator (2nd row). The ideal rejection probability should be 5%, so ideally we should be seeing a flat
surface with height 5%.

be our response variable y. The socio-economic and biological factors will be our regressors
x, which we shall describe in more detail below. We shall estimate the conditional first
decile function of the child’s height given the factors (that is, we set τ = .1). We would
like to perform inference on the size of the impact of the various factors on the conditional
decile of the child’s height. The problem has material significance, so it is important to
conduct statistical inference for this problem responsibly.
19

The data comes originally from the Demographic and Health Surveys (DHS) conducted
regularly in more than 75 countries; we employ the same selected sample of 37,649 as
in Koenker (2012). All children in the sample are between the ages of 0 and 5. The
response variable y is the child’s height in centimeters. The regressors x include child’s
age, breast feeding in months, mothers body-mass index (BMI), mother’s age, mother’s
education, father’s education, number of living children in the family, and a large number
of categorical variables, with each category coded as binary (zero or one): child’s gender
(male or female), twin status (single or twin), the birth order (first, second, third, fourth,
or fifth), the mother’s employment status (employed or unemployed), mother’s religion
(Hindu, Muslim, Christian, Sikh, or other), mother’s residence (urban or rural), family’s
wealth (poorest, poorer, middle, richer, richest), electricity (yes or no), radio (yes or no),
television (yes or no), bicycle (yes or no), motorcycle (yes or no), and car (yes or no).
Although the number of covariates (p = 30) is substantial, the sample size (n = 37, 649)
is much larger than the number of covariates. Therefore, the dataset is very interesting
from a methodological point of view, since it gives us an opportunity to compare various
methods for performing inference to an “ideal” benchmark of standard inference based on
the standard quantile regression estimator without any model selection. This was proven
theoretically in [18] and in [4] under the p → ∞, p3 /n → 0 regime. This is also the general
option recommended by [22] and [27] in the fixed p regime. Note that this “ideal” option
does not apply in practice when p is relatively large; however it certainly applies in the
present example.
We will compare the “ideal” option with two procedures. First the standard postselection inference method. This method performs standard inference on the post-model
selection estimator, “assuming” that the model selection had worked perfectly. Second the
double selection estimator defined as in Algorithm 2.2. (The orthogonal score estimator
20

performs similarly so it is omitted due to space constrains.) The proposed methods do not
assume perfect selection, but rather build a protection against (moderate) model selection
mistakes.
We now will compare our proposal to the “ideal” benchmark and to the standard postselection method. We report the empirical results in Table 4.2. The first column reports
results for the ideal option, reporting the estimates and standard errors enclosed in brackets.
The second column reports results for the standard post-selection method, specifically
the point estimates resulting from the post-penalized quantile regression, reporting the
standard errors as if there had been no model selection. The last column report the results
for the double selection estimator (point estimate and standard error). Note that the
Algorithm 2.2 is applied sequentially to each of the variables. Similarly, in order to provide
estimates and confidence intervals for all variables using the naive approach, if the covariate
was not selected by the ℓ1 -penalized quantile regression, it was included in the post-model
selection quantile regression for that variable.

What we see is very interesting. First of all, let us compare the “ideal” option (column
1) and the naive post-selection (column 2). The Lasso selection method removes 16 out
of 30 variables, many of which are highly significant, as judged by the “ideal” option. (To
judge significance we use normal approximations and critical value of 3, which allows us
to maintain 5% significance level after testing up to 50 hypotheses). In particular, we
see that the following highly significant variables were dropped by Lasso: mother’s BMI,
mother’s age, twin status, birth orders one and two, and indicator of the other religion.
The standard post-model selection inference then makes the assumption that these are
true zeros, which leads us to misleading conclusions about these effects. The standard
21

Variable
cage
mbmi
breastfeeding
mage
medu
edupartner
deadchildren
csexfemale
ctwintwin
cbirthorder2
cbirthorder3
cbirthorder4
cbirthorder5
munemployed
motorcycleyes

quantile
regression
0.6456
(0.0030)
0.0603
(0.0159)
0.0691
(0.0036)
0.0684
(0.0090)
0.1590
(0.0136)
0.0175
(0.0125)
-0.0680
(0.1124)
-1.4625
(0.0948)
-1.7259
(0.3741)
-0.7256
(0.1073)
-1.2367
(0.1315)
-1.7455
(0.2244)
-2.4014
(0.1639)
0.0409
(0.1025)
0.6104
(0.1783)

Naive post
selection
0.6458
(0.0027)
0.0663
(0.0139)
0.0689
(0.0038)
0.0454
(0.0147)
0.1870
(0.0145)
0.0460
(0.0148)
-0.2121
(0.0978)
-1.5084
(0.0897)
-1.8683
(0.2295)
-0.2230
(0.0983)
-0.5751
(0.1423)
-0.7910
(0.1938)
-1.1747
(0.1686)
0.0077
(0.1077)
0.5883
(0.1334)

Table 1: Empirical Results
Double
Selection α̌τ
0.6449
(0.0032)
0.0582
(0.0173)
0.0700
(0.0044)
0.0685
(0.0126)
0.1566
(0.0154)
0.0348
(0.0143)
-0.1546
(0.1121)
-1.5299
(0.1019)
-1.9248
(0.7375)
-0.6818
(0.1337)
-1.1326
(0.1719)
-1.5819
(0.2193)
-2.3041
(0.2564)
0.0379
(0.1124)
0.5154
(0.1625)

Variable
mreligionhindu
mreligionmuslim
mreligionother
mreligionsikh
mresidencerural
wealthpoorer
wealthmiddle
wealthricher
wealthrichest
electricityyes
radioyes
televisionyes
refrigeratoryes
bicycleyes
caryes

quantile
regression
-0.4351
(0.2232)
-0.3736
(0.2417)
-1.1448
(0.3296)
-0.5575
(0.2969)
0.1545
(0.0994)
0.2732
(0.1761)
0.8699
(0.1719)
1.3254
(0.2244)
2.0238
(0.2596)
0.3866
(0.1581)
-0.0385
(0.1218)
-0.1633
(0.1191)
0.1544
(0.1774)
0.1438
(0.1048)
0.2741
(0.2058)

Naive post
selection
-0.2423
(0.1080)
0.0294
(0.1438)
-0.6977
(0.3219)
0.3692
(0.1897)
0.1085
(0.1363)
-0.1946
(0.1231)
0.9197
(0.2236)
0.5754
(0.1408)
1.2967
(0.2263)
0.7555
(0.1398)
0.1363
(0.1214)
-0.0774
(0.1234)
0.2451
(0.2081)
0.1314
(0.1016)
0.5805
(0.2378)

Double
Selection α̌τ
-0.5680
(0.1771)
-0.5119
(0.2176)
-1.1539
(0.3577)
-0.3408
(0.3889)
0.1678
(0.1311)
0.2648
(0.1877)
0.9173
(0.2158)
1.4040
(0.2505)
2.1133
(0.3318)
0.4582
(0.1577)
0.0640
(0.1207)
-0.0880
(0.1386)
0.2001
(0.1891)
0.1438
(0.1121)
0.5470
(0.2896)

post-selection inference then proceeds to judge the significance of other variables, in some
cases deviating sharply and significantly from the “ideal” benchmark. For example, there
is a sharp disagreement on magnitudes of the impact of the birth order variables and the
wealth variables (for “richer” and “richest” categories). Overall, for the naive post-selection,
8 out of 30 coefficients were more than 3 standard errors away from the coefficients of the
“ideal” option.
We now proceed to comparing our proposed options to the “ideal” option. We see approximate agreement in terms of magnitude, signs of coefficients, and in standard errors. In
few instances, for example, for the car ownership regressor, the disagreements in magnitude
may appear large, but they become insignificant once we account for the standard errors.
The main conclusion from our study is that the standard/naive post-selection inference
can give misleading results, confirming our expectations and confirming predictions of [27].
22

Moreover, the proposed inference procedure is able to deliver inference of high quality,
which is very much in agreement with the “ideal” benchmark.

SUPPLEMENTARY MATERIAL
Supplementary Material. The supplemental appendix contains the proofs, additional
discussions (variants, approximately sparse assumption) and technical results. (pdf)

References
[1] A. Belloni, D. Chen, V. Chernozhukov, and C. Hansen. Sparse models and methods for optimal instruments with an application to eminent domain. Econometrica,
80(6):2369–2430, November 2012.
[2] A. Belloni and V. Chernozhukov. ℓ1 -penalized quantile regression for high dimensional
sparse models. Ann. Statist., 39(1):82–130, 2011.
[3] A. Belloni and V. Chernozhukov.

Least squares after model selection in high-

dimensional sparse models. Bernoulli, 19(2):521–547, 2013.
[4] A. Belloni, V. Chernozhukov, and I. Fernandez-Val. Conditional quantile processes
based on series or many regressors. arXiv:1105.6154, may 2011.
[5] A. Belloni, V. Chernozhukov, and C. Hansen. Inference for high-dimensional sparse
econometric models. Advances in Economics and Econometrics: The 2010 World
Congress of the Econometric Society, 3:245–295, 2013.
[6] A. Belloni, V. Chernozhukov, and C. Hansen. Inference on treatment effects after
selection amongst high-dimensional controls. Rev. Econ. Stud., 81:608–650, 2014.
23

[7] A. Belloni, V. Chernozhukov, and K. Kato. Uniform post model selection inference
for LAD regression models. accepted at Biometrika, 2014.
[8] A. Belloni, V. Chernozhukov, and L. Wang. Square-root-lasso: Pivotal recovery of
sparse signals via conic programming. Biometrika, 98(4):791–806, 2011.
[9] A. Belloni, V. Chernozhukov, and Y. Wei. Honest confidence regions for logistic
regression with a large number of controls. ArXiv:1304.3969, 2013.
[10] Alexandre Belloni, Victor Chernozhukov, Iván Fernández-Val, and Chris Hansen. Program evaluation with high-dimensional data. arXiv preprint arXiv:1311.2645, 2013.
[11] Alexandre Belloni, Victor Chernozhukov, and Lie Wang. Pivotal estimation via squareroot lasso in nonparametric regression. The Annals of Statistics, 42(2):757–788, 2014.
[12] P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of lasso and Dantzig
selector. Ann. Statist., 37(4):1705–1732, 2009.
[13] X. Chen. Large sample sieve estimatin of semi-nonparametric models. Handbook of
Econometrics, 6:5559–5632, 2007.
[14] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Gaussian approximation
of suprema of empirical processes. arXiv preprint arXiv:1212.6885, 2012.
[15] Victor Chernozhukov and Christian Hansen. Instrumental variable quantile regression:
A robust inference approach. J. Econometrics, 142:379–398, 2008.
[16] Victor H. de la Peña, Tze Leung Lai, and Qi-Man Shao. Self-normalized Processes:
Limit Theory and Statistical Applications. Springer, New York, 2009.

24

[17] N. Fenske, T. Kneib, and T. Hothorn. Identifying risk factors for severe childhoold
malnutrition by boosting additive quantile regression. Journal of the Statistical Association, 106:494–510, 2011.
[18] Xuming He and Qi-Man Shao. On parameters of increasing dimensions. J. Multivariate
Anal., 73(1):120–135, 2000.
[19] K. Kato.

Group Lasso for high dimensional sparse quantile regression models.

arXiv:1103.1458, 2011.
[20] K. Knight. Limiting distributions for L1 regression estimators under general conditions. The Annals of Statistics, 26:755–770, 1998.
[21] R. Koenker. Additive models for quantile regression: Model selection and confidence
bandaids. Brazilian Journal of Probability and Statistics, 25(3):239–262, 2011.
[22] Roger Koenker. Quantile Regression. Cambridge University Press, Cambridge, 2005.
[23] Roger Koenker. quantreg: Quantile regression. r package version 5.24. R Foundation for Statistical Computing: Vienna) Available at: http://CRAN. R-project.
org/package= quantreg, 2016.
[24] Michael R. Kosorok. Introduction to Empirical Processes and Semiparametric Inference. Springer, New York, 2008.
[25] M. Ledoux and M. Talagrand. Probability in Banach Spaces (Isoperimetry and processes). Ergebnisse der Mathematik undihrer Grenzgebiete, Springer-Verlag, 1991.
[26] Sokbae Lee. Efficient semiparametric estimation of a partially linear quantile regression
model. Econometric Theory, 19:1–31, 2003.
25

[27] Hannes Leeb and Benedikt M. Pötscher. Model selection and inference: facts and
fiction. Econometric Theory, 21:21–59, 2005.
[28] Hannes Leeb and Benedikt M. Pötscher. Can one estimate the conditional distribution
of post-model-selection estimator? The Annals of Statistics, 34(5):2554–2591, 2006.
[29] Hannes Leeb and Benedikt M. Pötscher. Sparse estimators and the oracle property,
or the return of Hodges’ estimator. J. Econometrics, 142(1):201–211, 2008.
[30] E. L. Lehmann. Theory of Point Estimation. New York: Wiley, 1983.
[31] J. Neyman. C(α) tests and their use. Sankhya, 41:1–21, 1979.
[32] Joseph P. Romano and Azeem M. Shaikh. On the uniform asymptotic validity of
subsampling and the bootstrap. Ann. Statist., 40(6):2798–2822, 2012.
[33] Joseph P. Romano and Michael Wolf. Control of generalized error rates in multiple
testing. Ann. Statist., 35(4):1378–1408, 2007.
[34] Mark Rudelson and Roman Vershynin. On sparse reconstruction from fourier and
gaussian measurements. Communications on Pure and Applied Mathematics, 61:1025–
1045, 2008.
[35] R. J. Tibshirani. Regression shrinkage and selection via the Lasso. J. R. Statist. Soc.
B, 58:267–288, 1996.
[36] A. Tsybakov. Introduction to nonparametric estimation. Springer, 2008.
[37] Sara van de Geer, Peter Bühlmann, Ya’acov Ritov, and Ruben Dezeure. On asymptotically optimal confidence regions and tests for high-dimensional models. Annals of
Statistics, 42:1166–1202, 2014.
26

[38] A. W. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes:
With Applications to Statistics. Springer-Verlag, New York, 1996.
[39] Aad W. van der Vaart and Jon A. Wellner. Empirical process indexed by estimated
functions. IMS Lecture Notes-Monograph Series, 55:234–252, 2007.
[40] Cun-Hui Zhang and Stephanie S. Zhang. Confidence intervals for low-dimensional
parameters with high-dimensional data. J. R. Statist. Soc. B, 76:217–242, 2014.

27

Supplementary Appendix for
“Valid Post-Selection Inference in
High-dimensional Approximately Sparse
Quantile Regression Models”
The supplemental appendix contains the proofs of the main results, additional
discussions and technical results. Section 1 collects the notation. Section 2
has additional discussions on variants of the proposed methods, assumptions
of approximately sparse functions, minimax efficiency, and the choices of bandwidth and penalty parameters and their implications for the growth of s, p
and n. Section 3 provides new results for ℓ1 -penalized quantile regression with
approximation errors, Lasso with estimated weights under (weaker) aggregated
zero mean condition, and for the solution of the zero of the moment condition
associated with the orthogonal score function. The proof of the main result of
the main text is provided in Section 4. Section 5 collects auxiliary technical
inequalities used in the proofs, Section 6 provides the proofs and technical lemmas for ℓ1 -quantile regression. Section 7 provides proofs and technical lemmas
for Lasso with estimated weights. Section 8 provides the proof for the orthogonal moment condition estimation problem. Finally Section 9 provided rates of
convergence for the estimates of the conditional density function.

Notation
In what follows, we work with triangular array data {ωi,n : i = 1, . . . , n; n = 1, 2, 3, . . . }
where for each n, {ωi,n ; i = 1, . . . , n} is defined on the probability space (Ω, S, Pn ). Each
1

′
′
ωi,n = (yi,n
, zi,n
, d′i,n )′ is a vector which are i.n.i.d., that is, independent across i but not

necessarily identically distributed. Hence all parameters that characterize the distribution
of {ωi,n : i = 1, . . . , n} are implicitly indexed by Pn and thus by n. We omit this dependence
P
from the notation for the sake of simplicity. We use En to abbreviate the notation n−1 ni=1 ;
P
for example, En [f ] := En [f (ωi )] := n−1 ni=1 f (ωi ). We also use the following notation:
P
Ē[f ] := E [En [f ]] = E [En [f (ωi )]] = n−1 ni=1 E[f (ωi )]. The ℓ2 -norm is denoted by k · k;

the ℓ0 -“norm” k · k0 denotes the number of non-zero components of a vector; and the ℓ∞ norm k · k∞ denotes the maximal absolute value in the components of a vector. Given
a vector δ ∈ Rp , and a set of indices T ⊂ {1, . . . , p}, we denote by δT ∈ Rp the vector

in which δT j = δj if j ∈ T , δT j = 0 if j ∈
/ T . We also denote by δ (k) the vector with k

non-zero components corresponding to k of the largest components of δ in absolute value.
We use the notation (a)+ = max{a, 0}, a ∨ b = max{a, b}, and a ∧ b = min{a, b}. We
also use the notation a . b to denote a 6 cb for some constant c > 0 that does not
depend on n; and a .P b to denote a = OP (b). For an event E, we say that E wp →
1 when E occurs with probability approaching one as n grows. Given a p-vector b, we
denote support(b) = {j ∈ {1, ..., p} : bj 6= 0}. We also use ρτ (t) = t(τ − 1{t 6 0}) and
ϕτ (t1 , t2 ) = (τ − 1{t1 6 t2 }).
Define the minimal and maximal m-sparse eigenvalues of a symmetric positive semidefinite matrix M as
φmin(m)[M] :=

δ ′ Mδ
δ ′ Mδ
and
φ
(m)[M]
:=
max
.
max
16kδk0 6m kδk2
16kδk0 6m kδk2
min

(0.20)

For notational convenience we write x̃i = (di , x′i )′ , φmin (m) := φmin(m)[En [x̃i x̃′i ]], and
φmax (m) := φmax (m)[En [x̃i x̃′i ]].

2

1
1.1

Additional Discussions
Variants of the Proposed Algorithms

There are several different ways to implement the sequence of steps underlying the two
procedures outlined in Algorithms 2.1 and 2.2. The estimation of the control function
gτ can be done through other regularization methods like ℓ1 -penalized quantile regression
instead of the post-ℓ1 -penalized quantile regression. The estimation of the error term v
in Step 2 can be carried out with Dantzig selector, square-root Lasso or the associated
post-selection method could be used instead of Lasso or post-Lasso. Solving for the zero
of the moment condition induced by the orthogonal score function can be substituted
by a one-step correction from the ℓ1 -penalized quantile regression estimator α
bτ , namely,
vi ].
α̌τ = α
bτ + (En [b
v 2 ])−1 En [(τ − 1{yi 6 α
bτ di + x′ βbτ })b
i

i

Other variants can be constructing alternative orthogonal score functions. This can
be achieved by changing the weights in the equation (2.7) to alternative weights, say f˜i ,
that lead to different errors terms ṽ that satisfies E[f˜xṽ] = 0. Then the orthogonal score
function is constructed as ψi (α) = (τ − 1{yi 6 di α + gτ (zi )})ṽi (f˜i /fi ). It turns out that
the choice f˜i = fi minimizes the asymptotic variance of the estimator of ατ based upon

the empirical analog of (2.8), among all the score functions satisfying (2.9). An example is
to set f˜i = 1 which would lead to ṽi = di − E[di | zi ]. Although such choice leads to a less
efficient estimator, the estimation of E[di | zi ] and fi can be carried out separably which
can lead to weaker regularity conditions.

3

1.2

Handling Approximately Sparse Functions

As discussed in Remark 3.1, in order to handle approximately sparse models to represent
gτ in (2.6) an approximate orthogonality condition is assumed, namely
Ē[fi vi rτ i ] = o(n−1/2 ).

(1.21)

In the literature such a condition has been (implicitly) used before. For example, (1.21)
holds if the function gτ is an exactly sparse linear combination of the covariates so that
all the approximation errors are exactly zero, namely, rτ i = 0, i = 1, . . . , n. An alternative
assumption in the literature that implies (1.21) is to have E[fi di | zi ] = fi {x′i θτ + rθτ i },
where θτ is sparse and rθτ i is suitably small, which implies orthogonality to all functions of
zi since we have E[fi vi | zi ] = 0.
The high-dimensional setting makes the condition (1.21) less restrictive as p grows. Our
discussion is based on the assumption that the function gτ belongs to a well behaved class
of functions. For example, when gτ belongs to a Sobolev space S(α, L) for some α > 1
and L > 0 with respect to the basis {xj = Pj (z), j > 1}. As in [36], a Sobolev space of
P
functions consists of functions g(z) = ∞
j=1 θj Pj (z) whose Fourier coefficients θ satisfy
o
n
P∞ 2α 2
P∞
2
.
θ ∈ Θ(α, L) = θ ∈ ℓ2 (N) :
j
θ
6
L
|θ
|
<
∞,
j
j=1
j=1 j

More generally, we can consider functions in a p-Rearranged Sobolev space RS(α, p, L)
which allow permutations in the first p components as in [11]. Formally, the class of
P
functions g(z) = ∞
j=1 θj Pj (z) such that


∞


X
∃ permutation Υ of {1, . . . , p} :
θ ∈ ΘR (α, p, L) = θ ∈ ℓ2 (N) :
|θj | < ∞, Pp
.
P

j 2α θ2 6 L2 
j 2α θ2 + ∞
j=1

j=1

Υ(j)

j=p+1

j

It follows that S(α, L) ⊂ RS(α, p, L) and p-Rearranged Sobolev space reduces substantially
the dependence on the ordering of the basis.
4

Under mild conditions, it was shown in [11] that for functions in RS(α, p, L) the rate-

optimal choice for the size of the support of the oracle model obeys s . n1/[2α+1] . It follows
that
Ē[rτ2 ]1/2 = Ē[{

P

. n−α/{1+2α} .
√
However, this bound cannot guarantee converge to zero faster than n-rate to potentially
j>s θ(j) P(j) (zi )}

2 1/2

]

imply (1.21). Fortunately, to establish relation (1.21) one can exploit orthogonality with
respect all p components of xi . Indeed we have
P
P
|Ē[fi vi rτ i ]| = |Ē[fi vi { pj=s+1 θj Pj (zi ) + j>p+1 θj Pj (zi )]|
P
P
= | j>p+1 Ē[fi vi θj Pj (zi )]| 6 j>p+1 |θj |{Ē[fi2 vi2 ]E[Pj2 (zi )]}1/2
P
P
6 {Ē[fi2 vi2 ] maxj>p+1 E[Pj2 (zi )]}1/2 ( j>p+1 |θj |2 j 2α )1/2 ( j>p+1 j −2α )1/2
= O(p−α+1/2 ).

Therefore, condition (1.21) holds if n = o(p2α−1 ), in particular, for any α > 1, n = o(p)
suffices.

1.3

Minimax Efficiency

In this section we make some connections to the (local) minimax efficiency analysis from
the semiparametric efficiency analysis. In this section for the sake of exposition we assume
that (yi , xi , di )ni=1 are i.i.d., sparse models, rθτ i = rτ i = 0, i = 1, . . . , n, and the median case
(τ = .5). [26] derives an efficient score function for the partially linear median regression
model:
Si = 2ϕτ (yi , di ατ + x′i βτ )fi [di − m∗τ (z)],
where m∗τ (xi ) is given by
m∗τ (xi ) =

E[fi2 di |xi ]
.
E[fi2 |xi ]
5

Using the assumption m∗τ (xi ) = x′i θτ∗ , where kθτ∗ k0 6 s ≪ n is sparse, we have that
Si = 2ϕτ (yi , di ατ + x′i βτ )vi∗ ,
where vi∗ = fi di − fi m∗τ (xi ) would correspond to vi in (2.7). It follows that the estimator

based on vi∗ is actually efficient in the minimax sense (see Theorem 18.4 in [24]), and
inference about ατ based on this estimator provides best minimax power against local
alternatives (see Theorem 18.12 in [24]).
The claim above is formal as long as, given a law Qn , the least favorable submodels are
permitted as deviations that lie within the overall model. Specifically, given a law Qn , we
shall need to allow for a certain neighborhood Qδn of Qn such that Qn ∈ Qδn ⊂ Qn , where the
overall model Qn is defined similarly as before, except now permitting heteroscedasticity
(or we can keep homoscedasticity fi = fǫ to maintain formality). To allow for this we
consider a collection of models indexed by a parameter t = (t1 , t2 ):
yi = di (ατ + t1 ) + x′i (βτ + t2 θτ∗ ) + ǫi ,
fi di = fi x′i θτ∗ + vi∗ , E[fi vi∗ |xi ] = 0,

ktk 6 δ,

(1.22)
(1.23)

where kβτ k0 ∨ kθτ∗ k0 6 s/2 and conditions as in Section 2 hold. The case with t = 0

generates the model Qn ; by varying t within δ-ball, we generate models Qδn , containing

the least favorable deviations. By [26], the efficient score for the model given above is Si ,
so we cannot have a better regular estimator than the estimator whose influence function
is J −1 Si , where J = E[Si2 ]. Since our model Qn contains Qδn , all the formal conclusions
about (local minimax) optimality of our estimators hold from theorems cited above (using
subsequence arguments to handle models changing with n). Our estimators are regular,
√
since under Qtn with t = (O(1/ n), o(1)), their first order asymptotics do not change, as
a consequence of Theorems in Section 2. (Though our theorems actually prove more than
this.)
6

1.4

Choice of Bandwidth h and Penalty Level λ

The proof of Theorem 1 provides a detailed analysis for generic choice of bandwidth h and
the penalty level λ in Step 2 under Condition D. Here we discuss two particular choices for
λ, for γ = 0.05/n
√
√
(i) λ = h−1 nΦ−1 (1 − γ/2p) and (ii) λ = 1.1 n2Φ−1 (1 − γ/2p).
The choice (i) for λ leads to a sparser estimators by adjusting to the slower rate of convergence of fbi , see (3.17). The choice (ii) for λ corresponds to the (standard) choice of penalty
level in the literature for Lasso. Indeed, we have the following sparsity guarantees for the

θ̃τ under each choice
(i) e
sθτ . s + nh2k̄+2 / log(pn) and (ii) seθτ . h−2 s + nh2k̄ / log(pn).

In addition to the requirements in Condition M, (Kq2 s2 + s3 ) log3 (pn) 6 δn n and
Kq4 s log(pn) log3 n 6 δn n, which are independent of λ and h, we have that Condition
D simplifies to
√
h2k̄+1 n 6 δn ,

h−2 Kq4 s log(pn) 6 δn n,

(i)

h2k̄ s log(pn) 6 δn ,

(ii)

h−2 s2 log2 (pn) 6 δn n, h2k̄+2 Kq2 log(pn) log3 n 6 δn
√
h2k̄−2 s log(pn) 6 δn , h2k̄ n 6 δn , (h−2 log(pn) log3 n + Kq2 )Kq2 s log(pn) 6 δn n,
{h−2 + log(pn)}h−2 s2 log(pn) 6 δn n, h2k̄ Kq2 log(pn) log3 n 6 δn

For example, using the choice of fbi as in (2.16) so that k̄ = 4, we have that the following
choice growth conditions suffice for the conditions above:
(i)

Kq3 s3 log3 (pn) 6 δn n, Kq3 6 n1/3 and h = n−1/6

(ii)

(s + Kx3 )s3 log3 (pn) 6 δn n, Kq3 6 n1/3 , and h = n−1/8

7

2

Analysis of the Estimators

This section contains the main tools used in establishing the main inferential results. The
high-level conditions here are intended to be applicable in a variety of settings and they
are implied by the regularities conditions provided in the previous sections. The results
provided here are of independent interest (e.g. properties of Lasso under estimated weights).
We establish the inferential results (1.1) and (1.3) in Section 2.3 under high level conditions.
To verify these high-level conditions we need rates of convergence for the estimated residuals
v and the estimated confounding function b
b
gτ (z) = x′ βbτ which are established in sections 2.2

and 2.1 respectively. The main design condition relies on the restricted eigenvalue proposed
in [12], namely for x̃i = [di , x′i ]′

κc =

inf

kδT c k1 6ckδT k1

kx̃′i δk2,n /kδT k

(2.24)

where c = (c + 1)/(c − 1) for the slack constant c > 1, see [12]. When c is bounded, it is
well known that κc is bounded away from zero provided sparse eigenvalues of order larger
than s are well behaved, see [12].

2.1

ℓ1 -Penalized Quantile Regression

In this section for a quantile index u ∈ (0, 1), we consider the equation
ỹi = x̃′i ηu + rui + ǫi , u-quantile of (ǫi | x̃i , rui ) = 0

(2.25)

where we observe {(ỹi , x̃i ) : i = 1, . . . , n}, which are independent across i. To estimate ηu
we consider the ℓ1 -penalized u-quantile regression estimate
ηbu ∈ arg min En [ρu (ỹi − x̃′i η)] +
η

8

λu
kηk1 .
n

and the associated post-model selection estimates. That is, given an estimator η̄uj
ηeu ∈ arg min { En [ρu (ỹi − x̃′i η)] : ηj = 0 if η̄uj = 0} .
η

(2.26)

We will be typically concerned with ηbu , thresholded versions of the ℓ1 -penalized quantile
µ
regression, defined as ηbuj
= ηbuj 1{|b
ηuj | > µ/En [x̃2ij ]1/2 }.

As established in [2] for sparse models and in [19] for approximately sparse models,

under the event that

λu
> ckEn [(u − 1{ỹi 6 x̃′i ηu + rui })x̃i ]k∞
n

(2.27)

the estimator above achieves good theoretical guarantees under mild design conditions.
Although ηu is unknown, we can set λu so that the event in (2.27) holds with high probability. In particular, the pivotal rule proposed in [2] and generalized in [19] proposes to set
λu := cnΛu (1 − γ | x̃) for c > 1 where
Λu (1 − γ | x̃, ru ) = (1 − γ) − quantile of kEn [(u − 1{Ui 6 u})x̃i ]k∞

(2.28)

where Ui ∼ U(0, 1) are independent random variables conditional on x̃i , i = 1, . . . , n. This
quantity can be easily approximated via simulations. Below we summarize the high level
conditions we require.
Condition PQR. Let Tu = supp(ηu ) and normalize En [x̃2ij ] = 1, j = 1, . . . , p. Assume
p
that for some s > 1, kηu k0 6 s, krui k2,n 6 C s log(p)/n. Further, the conditional

distribution function of ǫi is absolutely continuous with continuously differentiable density
fǫ (· | x̃i , rui ) such that 0 < f 6 fi 6 sup fǫ |x̃ ,r (t | x̃i , rui ) 6 f¯, sup |f ′
(t | x̃i , rui )| <
t

i

i

f¯′ for fixed constants f , f¯ and f¯′ .

ui

t

ǫi |x̃i ,rui

Condition PQR is implied by Condition AS. The conditions on the approximation error
and near orthogonality conditions follows from choosing a model ηu that optimally balance
9

the bias/variance trade-off. The assumption on the conditional density is standard in the
quantile regression literature even with fixed p case developed in [22] or the case of p
increasing slower than n studied in [4].
Next we present bounds on the prediction norm of the ℓ1 -penalized quantile regression
estimator.
Lemma 1 (Estimation Error of ℓ1 -Penalized Quantile Regression) Under Condition
PQR, setting λu > cnΛu (1 − γ | x̃), we have with probability 1 − 4γ for n large enough
r
√
λu s
1
s log(p/γ)
′
kx̃i (b
ηu − ηu )k2,n . N :=
+
nκ2c
κ2c
n
and ηbu − ηu ∈ Au := ∆2c ∪ {v : kx̃′i vk2,n = N, kvk1 6 8Ccs log(p/γ)/λu }, provided that
sup

δ̄∈Au

En [|rui ||x̃′i δ̄|2 ]
En [|x̃′i δ̄|3 ]
→ 0.
+
N
sup
′ 2 3/2
En [|x̃′i δ̄|2 ]
δ̄∈Au En [|x̃i δ̄| ]

Lemma 1 establishes the rate of convergence in the prediction norm for the ℓ1 -penalized
quantile regression estimator. Exact constants are derived in the proof. The extra growth
p
condition required for identification is mild. For instance we typically have λu ∼ n log(np)
and for many designs of interest we have

inf kx̃′i δk32,n /En [|x̃′i δ|3 ]

δ∈∆c

bounded away from zero (see [2]). For more general designs we have
kx̃′i δk32,n
kx̃′i δk2,n
1
>
inf
>
inf
δ∈Au kδk1 maxi6n kx̃i k∞
δ∈Au En [|x̃′i δ|3 ]
maxi6n kx̃i k∞



κ
λu N
√ 2c
∧
s(1 + c) 8Ccs log(p/γ)



.

Lemma 2 (Estimation Error of Post-ℓ1 -Penalized Quantile Regression) Assume Condition PQR holds, and that the Post-ℓ1 -penalized quantile regression is based on an arbitrary
10

b > En [ρu (ỹi − x̃′ ηbu )] − En [ρu (ỹi − x̃′ ηu ))]
vector ηbu . Let r̄u > krui k2,n , sbu > |supp(b
ηu )| and Q
i
i
hold with probability 1−γ. Then we have for n large enough, with probability 1−γ −ε−o(1)
s
su + s) log(p/ε)
e := (b
b1/2
kx̃′i (e
ηu − ηu )k2,n . N
+ f¯r̄u + Q
nφmin (b
su + s)

provided that

En [|x̃′i δ̄|3 ]
En [|rui ||x̃′i δ̄|2 ]
e sup
+
N
→ 0.
′ 2 3/2
En [|x̃′i δ̄|2 ]
kδ̄k0 6b
su +s En [|x̃i δ̄| ]
kδ̄k0 6b
su +s
sup

Lemma 2 provides the rate of convergence in the prediction norm for the post model
selection estimator despite of possible imperfect model selection. In the current nonparametric setting it is unlikely for the coefficients to exhibit a large separation from zero. The
rates rely on the overall quality of the selected model by ℓ1 -penalized quantile regression
and the overall number of components sbu . Once again the extra growth condition required

for identification is mild. For more general designs we have

2.2

p
kx̃′i δk32,n
φmin(b
su + s)
kx̃′i δk2,n
√
inf
.
>
inf
>
′
kδk0 6b
su +s En [|x̃i δ|3 ]
kδk0 6b
su +s kδk1 maxi6n kx̃i k∞
sbu + s maxi6n kx̃i k∞

Lasso with Estimated Weights

In this section we consider the equation
fi di = fi x′i θτ + fi rθτ i + vi , i = 1, . . . , Ē[fi vi xi ] = 0

(2.29)

where we observe {(di , zi , xi = X(zi )) : i = 1, . . . , n}, which are independent across i.
We do not observe {fi = fτ (di , zi )}n directly and only estimates {fbi }n are available.
i=1

i=1

Importantly, we only require that Ē[fi vi xi ] = 0 and not E[fi xi vi ] = 0 for every i = 1, . . . , n.
Also, we have that Tθτ = supp(θτ ) is unknown but a sparsity condition holds, namely
|Tθτ | 6 s. To estimate θθτ and vi , we compute

λ b
θbτ ∈ arg min En [fbi2 (di − x′i θ)2 ] + kΓ
bi = fbi (di − x′i θbτ ), i = 1, . . . , n, (2.30)
τ θk1 and set v
θ
n
11

bτ are the associated penalty level and loadings specified below. A difficulty
where λ and Γ
is to account for the impact of estimated weights fbi while also only using Ē[fi vi xi ] = 0.

We will establish bounds on the penalty parameter λ so that with high probability the

following regularization event occurs
λ
b−1 En [fi xi vi ]k∞ .
> 2ckΓ
τ
n

(2.31)

As discussed in [12, 3, 8], the event above allows to exploit the restricted set condition
vi defined
kθbτ T c k1 6 c̃kθbτ T − θτ k1 for some c̃ > 1. Thus rates of convergence for θbτ and b
θτ

θτ

on (2.30) can be established based on the restricted eigenvalue κc̃ defined in (2.24) with
x̃i = xi .

However, the estimation error in the estimate fbi of fi could slow the rates of convergence.
The following are sufficient high-level conditions. In what follows c, c̄, C, f , f¯ are strictly
positive constants independent of n.
Condition WL. For the model (2.29) suppose that:
(i) for s > 1 we have kθτ k0 6 s, Φ−1 (1 − γ/2p) 6 δn n1/6 ,
(ii) f 6 fi 6 f¯, c 6 min{Ē[|fi xij vi − E[fi xij vi ]|2 ]}1/2 6 max{Ē[|fi xij vi |3 ]}1/3 6 C,
j6p

j6p

2
2
(iii) with probability 1 − ∆n we have En [fbi2 rθτ
i ] 6 cr ,

max|(En − Ē)[fi2 x2ij vi2 ]| + |(En − Ē)[{fi xij vi − E[fi xij vi ]}2 ]| 6 δn ,
j6p




(fbi2 −fi2 )2 2
(fbi2 −fi2 )2 2
2
2
2
2
b
vi + E n
max En [(fi − fi ) xij vi ] 6 δn , En
b2 2 vi 6 cf .
f2
j6p

i

fi fi

bτ 0 6 Γ
b τ 6 uΓ
bτ 0 , for Γ
bτ 0jj = {En [fb2 x2 v 2 ]}1/2 , 1 − δn 6 ℓ 6 u 6 C with prob 1 − ∆n .
(iv) ℓΓ
i ij i

Comment 2.1 Condition WL(i) is a standard condition on the approximation error that

yields the optimal bias variance trade-off (see [3]) and imposes a growth restriction on p
relative to n, in particular log p = o(n1/3 ). Condition WL(ii) imposes conditions on the
conditional density function and mild moment conditions which are standard in quantile
12

regression models even with fixed dimensions, see [22]. Condition WL(iii) requires highlevel rates of convergence for the estimate fbi . Several primitive moment conditions imply

first requirement in Condition WL(iii). These conditions allow the use of self-normalized
moderate deviation theory to control heteroscedastic non-Gaussian errors similarly to [1]
where there are no estimated weights. Condition WL(iv) corresponds to the asymptotically
bτ in (2.12).
valid penalty loading in [1] which is satisfied by the proposed choice Γ

Next we present results on the performance of the estimators generated by Lasso with
estimated weights. In what follows, b
κc is defined with fbi xi instead of x̃i in (2.24) so that

κc > κc mini6n fbi .
b

Lemma 3 (Rates of Convergence for Lasso) Under Condition WL and setting λ >
√
2c′ nΦ−1 (1 − γ/2p) for c′ > c > 1, we have for n large enough with probability 1 − γ − o(1)

√ 
s
1
λ
′
u+
kfbi xi (θbτ − θτ )k2,n 6 2{cf + cr } +
nb
κc̃
c
 


√
b−1k∞ n
s{c
1
1
2ckΓ
λs
+
c
}
f
r
τ0
+ 1+
u+
+
{cf + cr }2
kθbτ − θτ k1 6 2
κ2c̃
b
nb
κc̃ κ
c
2c̃
ℓc − 1 λ
b2c̃
b−1
b
where c̃ = kΓ
τ 0 k∞ kΓτ 0 k∞ (uc + 1)/(ℓc − 1)

Lemma 3 above establishes the rate of convergence for Lasso with estimated weights.

This automatically leads to bounds on the estimated residuals b
vi obtained with Lasso

through the identity

vi
vi − vi = (fbi − fi ) + fbi x′i (θτ − θbτ ) + fbi rθτ i .
b
fi

(2.32)

The Post-Lasso estimator applies the least squares estimator to the model selected by the
Lasso estimator (2.30),
n
o
En [fbi2 (di − x′i θ)2 ] : θj = 0, if θbτ j = 0 , set ṽi = fbi (di − x′i θeτ ).
θeτ ∈ arg minp
θ∈R

13

It aims to remove the bias towards zero induced by the ℓ1 -penalty function which is used to
select components. Sparsity properties of the Lasso estimator θbτ under estimated weights

follows similarly to the standard Lasso analysis derived in [1]. By combining such sparsity

properties and the rates in the prediction norm we can establish rates for the post-model selection estimator under estimated weights. The following result summarizes the properties
of the Post-Lasso estimator.
Lemma 4 (Model Selection Properties of Lasso and Properties of Post-Lasso)
2

2

Suppose that Condition WL holds, and κ′ 6 φmin ({s + nλ2 {c2f + c2r }}/δn ) 6 φmax ({s + nλ2 {c2f +

c2r }}/δn ) 6 κ′′ for some positive and bounded constants κ′ , κ′′ . Then the data-dependent
√
model Tbθτ selected by the Lasso estimator with λ > 2c′ nΦ−1 (1 − γ/2p) for c′ > c > 1,
satisfies with probability 1 − γ − o(1):

kθeτ k0 = |Tbθτ | . s +

n2 2
{c + c2r }
λ2 f

(2.33)

Moreover, the corresponding Post-Lasso estimator obeys with probability 1 − γ − o(1)
s
√
|Tbθτ | log(p ∨ n) λ s
′ e
kxi (θτ − θτ )k2,n .P cf + cr +
.
+
n
nκc

2.3

Moment Condition based on Orthogonal Score Function

Next we turn to analyze the estimator α̌τ obtained based on the orthogonal moment condition. In this section we assume that
Ln (α̌τ ) 6 min Ln (α) + δn n−1 .
α∈Aτ

This setting is related to the instrumental quantile regression method proposed in [15].
However, in this application we need to account for the estimation of the noise v that acts
14

as the instrument which is known in the setting in [15]. Condition IQR below suffices to
make the impact of the estimation of instruments negligible to the first order asymptotics
of the estimator α̌τ . Primitive conditions that imply Condition IQR are provided and
discussed in the main text.
Let {(yi , di , zi ) : i = 1, . . . , n} be independent observations satisfying
yi = di ατ + gτ (zi ) + ǫi ,

τ -quantile(ǫi | di , zi ) = 0,

fi di = fi x′i θ0τ + vi ,

Ē[fi xi vi ] = 0.

(2.34)

Letting D × Z denote the domain of the random variables (d, z), for h̃ = (g̃, ι̃), where g̃ is
a function of variable z, and the instrument ι̃ is a function that maps (d, x) 7→ ι̃(d, z) we
write
ψα̃,h̃ (yi , di , zi ) = ψα̃,g̃,ι̃ (yi , di , zi ) = (τ − 1{yi 6 g̃(zi ) + di α})ι̃(di , zi )
= (τ − 1{yi 6 g̃i + di α})ι̃i .
We denote h0 = (gτ , ι0 ) where ι0i := vi = fi (di − x′i θ0τ ). For some sequences δn → 0 and
∆n → 0, we let F denote a set of functions such that each element h̃ = (g̃, ι̃) ∈ F satisfies
Ē[(1 + |ι0i | + |ι̃i − ι0i |)(gτ i − g̃i )2 ] 6 δn n−1/2 , Ē[(ι̃i − ι0i )2 ] 6 δn ,
Ē[|gτ i − g̃i ||ι̃i − ι0i |] 6 δn n−1/2 , |Ē[fi ι0i {g̃i − gτ i }]| 6 δn n−1/2 ,

(2.35)

and with probability 1 − ∆n we have
sup
2 ,h̃∈F
|α−ατ |6δn



(En − Ē) ψα,h̃ (yi , di , zi ) − ψα,h0 (yi , di , zi ) 6 δn n−1/2

We assume that the estimated functions b
g and b
ι satisfy the following condition.

(2.36)

Condition IQR. Let {(yi , di , zi ) : i = 1, . . . , n} be random variables independent across

i satisfying (2.34). Suppose that there are positive constants 0 < c 6 C < ∞ such that:
(i) fyi |di ,zi (y | di , zi ) 6 f¯, fy′ i |di ,zi (y | di , zi ) 6 f¯′ ; c 6 |Ē[fi di ι0i ]|, and Ē[ι40i ] + Ē[d4i ] 6 C;
15

(ii) {α : |α − ατ | 6 n−1/2 /δn } ⊂ Aτ , where Aτ is a (possibly random) compact interval;
(iii) with probability at least 1 − ∆n the estimated functions b
h = (b
g, b
ι) ∈ F and
|α̌τ − ατ | 6 δn

and

En [ψα̌τ ,bh (yi , di , zi )]| 6 δn n−1/2

(2.37)

(iv) with probability at least 1 − ∆n , the estimated functions b
h = (b
g, b
ι) satisfy
kb
ιi − ι0i k2,n 6 δn and k1{|ǫi | 6 |di (ατ − α̌τ ) + gτ i − b
gi |}k2,n 6 δn2 .

Lemma 5 Under Condition IQR(i,ii,iii) we have
√
σ̄n−1 n(α̌τ − ατ ) = Un (τ ) + oP (1), Un (τ )

N(0, 1)

where σ̄n2 = Ē[fi di ι0i ]−1 Ē[τ (1 − τ )ι20i ]Ē[fi di ι0i ]−1 and
√
Un (τ ) = {Ē[ψα2 τ ,h0 (yi , di , zi )]}−1/2 nEn [ψατ ,h0 (yi , di , zi )].
Moreover, IQR(iv) also holds we have
nLn (ατ ) = Un (τ )2 + oP (1), Un (τ )2

χ2 (1)

and the variance estimator is consistent, namely
En [fbi dib
ιi ]−1 En [(τ − 1{yi 6 b
gi + di α̌τ })2b
ι2i ]En [fbi dib
ιi ]−1 →P Ē[fi di ι0i ]−1 Ē[τ (1 − τ )ι20i ]Ē[fi di ι0i ]−1 .

3

Proofs for Section 3 of Main Text (Main Result)

Proof. (Proof of Theorem 1) The first-order equivalence between the two estimators
follows from establishing the same linear representation for each estimator. In Part 1 of
16

the proof we consider the orthogonal score estimator. In Part 2 we consider the double
selection estimator.
Part 1. Orthogonal score estimator. We will verify Condition IQR and the result follows
by Lemma 5 applied with ι0i = vi = fi (di − x′i θ0τ ) and noting that 1{yi 6 di ατ + gτ (zi )} =
1{Ui 6 τ } for some uniform (0, 1) random variable (independent of {di , zi }) by the definition
of the conditional quantile function.
Condition IQR(i) requires conditions on the probability density function that are assumed in Condition AS(iii). The fourth moment conditions are implied by Condition M(i)
using ξ = (1, 0′)′ and ξ = (1, −θ′ )′ , since Ē[v 4 ] 6 f¯4 Ē[{(di , x′ )ξ}4] 6 C ′ (1 + kθ0τ k)4 , and
0τ

i

i

kθ0τ k 6 C assumed in Condition AS(i). Finally, by relation (2.7), namely E[fi xi vi ] = 0,

′ ′ 2
we have Ē[fi di vi ] = Ē[vi2 ] > f Ē[(di − x′i θ0τ )2 ] > cf k(1, θ0τ
) k by Condition AS(iii) and

Condition M(i).
Next we will construct the estimate for the orthogonal score function which are based
on post-ℓ1 -penalized quantile regression and post-Lasso with estimated conditional density
function. We will show that with probability 1 − o(1) the estimated nuisance parameters
belong to F.

To establish the rates of convergence for βeτ , the post-ℓ1 -penalized quantile regression
based on the thresholded estimator βbτλτ , we proceed to provide rates of convergence for
the ℓ1 -penalized quantile regression estimator βbτ . We will apply Lemma 1 with γ = 1/n.
Condition PQR holds by Condition AS with probability 1 − o(1) using Markov inequality

and Ē[rτ2i ] 6 s/n.

Since population eigenvalues are bounded above and bounded away from zero by Condition M(i), by Lemma 8 (where δ̄n → 0 under Kq2 Cs log2 (1 + Cs) log(pn) log n = o(n)),
we have that sparse eigenvalues of order ℓn s are bounded away from zero and from above
with probability 1 − o(1) for some slowly increasing function ℓn . In turn, the restricted
17

eigenvalue κ2c is also bounded away from zero for bounded c and n sufficiently large. Since
p
p
λτ . n log(p ∨ n), we will take N = C s log(n ∨ p)/n in Lemma 1. To establish the
side conditions note that
sup
δ∈Aτ

En [|x̃′i δ|3 ]
kx̃′i δk32,n

6 sup
δ∈Aτ

maxi6n kx̃i k∞ kδk1
kx̃′i δk2,n

which implies that N sup
δ∈Aτ

En [|x̃′i δ|3 ]
kx̃′i δk32,n

6 maxkx̃i k∞
i6n

√

s(1+2c)
κ2c

∨

8Ccs log(pn)
λu N



.P Kq

p

s log(pn).

→ 0 with probability 1−o(1) under Kq2 s2 log2 (p∨n) 6 δn n.

Moreover, the second part of the side condition
sup
δ∈Aτ

En [|rτ i | |x̃′i δ|2 ]
kx̃′i δk22,n

En [|rτ i | |x̃′i δ|] maxi6n kx̃i k∞ kδk1
kr k
max
kx̃i k∞ kδk1
6 sup τ i 2,n kx̃′ i6n
δk
kx̃′i δk22,n
2,n
i
δ∈Aτ
δ∈Aτ

√
8Ccs log(pn)
s(1+2c)
∨
maxi6n kx̃i k∞ krτ i k2,n
κ2c
λu N

6 sup
6

.P

q

s log(pn)
Kq
n

p

s log(pn).

Under Kq2 s2 log2 (p∨n) 6 δn n, the side condition holds with probability 1−o(1). Therefore,
p
p
by Lemma 1 we have kx̃′ βbτ − βτ k2,n . s log(pn)/n and kβbτ − βτ k1 . s log(pn)/n with
i

probability 1 − o(1).

With the same probability, by Lemma 6 with µ = λτ /n, since φmax (Cs) is uniformly
bounded with probability 1 − o(1), we have that the thresholded estimator βbτµ satisfies the
p
following bounds with probability 1 − o(1): kβbτµ − βτ k1 . s log(pn)/n, kβbτµ k0 . s and
p
kx̃′ (βbµ − βτ )k2,n . s log(pn)/n. We use the support of βbµ as to construct the refitted
i

τ

τ

estimator βeτ .

b = Cs log(pn)/n.
We will apply Lemma 2. By Lemma 12 and the rate of βbτµ , we can take Q

Since sparse eigenvalues of order Cs are bounded away from zero, we will use Ñ =
p
p
C s log(pn)/n and ε = 1/n. Therefore, kx′i (βeτ − βτ )k2,n . s log(np)/n with probability 1 − o(1) provided the side conditions of the lemma hold. To verify the side conditions

18

note that
e sup
N

kδk0 6Cs

En [|x̃′i δ|3 ]
kx̃′i δk32,n

e sup
6N

kδk0 6Cs

e sup
6N

kδk0 6Cs

sup
kδk0 6Cs

En [|rτ i | |x̃′i δ|2 ]
kx̃′i δk22,n

maxi6n kx̃i k∞ kδk1
kx̃′i δk2,n

√
maxi6n kx̃i k∞ Cskδk

√

φmin (Cs)kδk

.P

q

√
s log(pn)
Kq s
n

1
6 krτ i k2,n maxi6n kx̃i k∞ sup kx̃kδk
′ δk
i 2,n
kδk0 6Cs
q
q
p
s log(pn)
Cs
K
s log(pn)
6 krτ i k2,n maxi6n kx̃i k∞ φmin (Cs) .P
q
n

and the side condition holds with probability 1 − o(1) under Kq2 s log2 (p ∨ n) 6 δn n.

Next we proceed to construct the estimator for vi . Note that by the same arguments
above, under Condition D, we have the same rates of convergence for the post-selection
(after truncation) estimators (e
αu , βeu ), u ∈ U, kβeu k0 . C and k(e
αu , βeu ) − (e
αu , βeu )k .
p
s log(pn)/n, to estimate the conditional density function via (2.15) or (2.16). Thus with
probability 1 − o(1)

kfi − fbi k2,n

1
.
h

r

s log(n ∨ p)
+ hk̄ and max |fbi − fi | . δn
i6n
n

(3.38)

where k̄ depends on the estimator. (See relation (3.41) below.) Note that the last relation
implies that maxi6n fbi 6 2f¯ is automatically satisfied with probability 1 − o(1) for n large

enough. Let U denote the (finite) set of quantile indices used in the calculation of fbi .
p
Next we verify Condition WL to invoke Lemmas 3 and 4 with cr = C s log(pn)/n


p
k̄
and cf = C {1/h} s log(n ∨ p)/n + h . The sparsity condition in Condition WL(i) is
implied by Condition AS(ii) and Φ−1 (1 −γ/2p) 6 δn n1/6 is implied by log(1/γ) . log(p ∨n)

and log3 p 6 δn n from Condition M(iii). Condition WL(ii) follows from the assumption on
the density function in Condition AS(iii) and the moment conditions in Condition M(i).
The first requirement in Condition WL(iii) holds with c2r . s log(pn)/n since
2
2
b
¯
En [fbi2 rθτ
i ] 6 max fi En [rθτ i ] . f s log(pn)/n
i6n

19

from maxi6n fbi 6 C holding with probability 1 − o(1), and Markov’s inequality under
2
Ē[rθτ
i ] 6 Cs/n by Condition AS(ii).

The second requirement, maxj6p |(En − Ē)[fi2 x2ij vi2 ]|+|(En − Ē)[{fi xij vi −E[fi xij vi ]}2 ]| 6

δn with probability 1−o(1), is implied by Lemma 8 with k = 1 and K = {E[maxi6n kfi xi vi k2∞ ]}1/2 6
f¯{E[maxi6n k(xi , vi )k4 ]}1/2 6 f¯K 2 , under K 4 log(pn) log n 6 δn n.
∞

q

q

The third requirement of Condition WL(iii) follows from uniform consistency in (3.38)
and the second part of Condition WL(ii) since

bi − fi |2 
|
f
2
2
2
2
2
2
2
2
2
max En [(fbi − fi ) xij vi ] 6 max
max(En − Ē)[fi xij vi ] + max Ē[fi xij vi ] . δn
j6p
i6n
j6p
j6p
fi2

with probability 1−o(1) by (3.38), the second requirement, and the bounded fourth moment

assumption in Condition M(i).
To show the fourth part of Condition WL(iii), because both fbi and fi are bounded away

from zero and from above with probability 1 − o(1), uniformly over u ∈ U (the finite set of
quantile indices used to estimate the density), and fb2 − f 2 = (fbi − fi )(fbi + fi ), it follows
i

i

that with probability 1 − o(1)

En [(fbi2 − fi2 )2 vi2 /fi2 ] + En [(fbi2 − fi2 )2 vi2 /{fbi2 fi2 }] . En [(fbi − fi )2 vi2 /fi2 ].

Next let δu = (e
αu − αu , βeu′ − βu′ )′ where the estimators satisfy Condition D. We have that

with probability 1 − o(1)

En [(fbi − fi )2 vi2 /fi2 ] . h2k̄ En [vi2 ] + h−2

X

2
En [vi2 (x̃′i δu )2 + vi2 rui
].

u∈U

The following relations hold for all u ∈ U

2
2
2
En [vi2 rui
] .P Ē[vi2 rui
] 6 f¯Ē[(di − x′i θ0τ )2 rui
] . s/n

En [vi2 (x̃′i δu )2 ] = Ē[(x′i δu )2 vi2 ] + (En − Ē)[vi2 (x′i δu )2 ]

6 Ckδu k2 + kδu k2 supkδk0 6kδu k0 ,kδk=1 |(En − Ē)[{vi x̃′i δ}2 ]|
20

(3.39)

where we have kδu k .

p

s log(n ∨ p)/n and kδu k0 . s with with probability 1 − o(1). Then

we apply Lemma 8 with Xi = vi x̃i . Thus, we can take K = {E[maxi6n kXi k2∞ ]}1/2 6

{E[maxi6n k(vi , x̃′i )k4∞ ]}1/2 6 Kq2 , and Ē[(δ ′ Xi )2 ] 6 Ē[vi2 (x̃′i δ)2 ] 6 Ckδk2 by the fourth

moment assumption in Condition M(i) and kθ0τ k 6 C. Therefore,
sup
kδk0 6Cs,kδk=1

(En − Ē)



{vi x̃′i δ}2



.P



Kq2 s log3 n log(p∨n)
n

+

q

Kq2 s log3 n log(p∨n)
n



Under Kq4 s log3 n log(p ∨ n) 6 δn n, with probability 1 − o(1) we have
c2f .

s log(n ∨ p)
+ h2k̄ .
h2 n

Condition WL(iv) pertains to the penalty loadings which are estimated iteratively. In
the first iteration we have that the loadings are constant across components as ̟ :=
maxi6n fbi maxi6n kxi k∞ {En [fbi2 d2i ]}2 . Thus the solution of the optimization problem is the
e defined as λ̃ := λ̟/ maxj6p {En [fb2 x2 v 2 ]}1/2 and
same if we use penalty parameters λ̃ and Γ
i

ejj =
Γ

ij i

maxj6p{En [fbi2 x2ij vi2 ]}1/2 .

b0τ jj 6 Γ
e jj 6 C Γ
b0τ jj for some bounded
By construction Γ
b0τ jj are bounded away from zero and from above with
C with probability 1 − o(1) as Γ

e and λ̃ . λ maxi6n kxi k∞ , by
probability 1 − o(1). Since Condition WL holds for (λ̃, Γ),

Lemma 3 we have with probability 1 − o(1)
r
√
s log(n ∨ p)
λ s maxi6n kxi k∞
1
k̄
′ b
+h +
kxi (θτ − θτ )k2,n .
h
n
n
The iterative choice of of penalty loadings satisfies

|En [fbi2 x2ij vi2 ]1/2 − En [fbi2 x2ij vbi2 ]1/2 | 6 maxi6n fbi kxi k∞ |En [{fi2 (di − x′i θ0τ ) − fbi (di − x′i θbτ )}2 ]1/2 |
6 maxi6n fbi kxi k∞ En [(fbi − fi )2 v 2 /f 2 ]1/2
i

i

+ maxi6n fbi kxi k∞ En [fbi2 {x′i (θbτ − θ0τ )}2 ]1/2
q
√
λKq2 s
Kq
k̄
.P h s log(n∨p)
+
+
K
h
q
n
n

uniformly in j 6 p. Thus the iterated penalty loadings are uniformly consistent with
probability 1 − o(1) and also satisfy Condition WL(iv) under h−2 Kq2 s log(pn) 6 δn n and
21

Kq4 s log(pn) 6 δn n. Therefore, in the subsequent iterations, by Lemma 3 and Lemma 4 we
have that the post-Lasso estimator satisfies with probability 1 − o(1)
kθeτ k0

kx′i (θeτ − θτ )k2,n

n2 {c2f + c2r }
ns log(n ∨ p)
.
+
s
.
s
e
:=
s
+
+
θτ
λ2
h2 λ2
r
√
λ s
1 s log(n ∨ p)
k̄
+h +
.
h
n
n

nhk̄
λ

!2

and

where we used that φmax (e
sθτ /δn ) 6 C implied by Condition D and Lemma 8, and that
p
p
p
√ −1
λ > nΦ (1 − γ/2p) ∼ n log(pn) so that seθτ log(pn)/n . (1/h) s log(pn)/n + hk̄ .
Next we construct a class of functions that satisfies the conditions required for F that

is used in Lemma 5. Define the following class of functions.
p

√

sθτ }
s log(pn)/n + hk̄ + λ n s }, kθk0 6 Ce
p
G = {x′i β : kβk0 6 Cs, kβ − βτ k 6 C s log(pn)/n}
p
J = {f˜i 6 2f¯ : kη̃u k0 6 Cs, kη̃u − ηu k 6 C s log(pn)/n, u ∈ U}

M = {x′i θ : kθ − θτ 0 k 6 C{ h1

(3.40)

˜
where f˜i = f (di , zi , {η̃u : u ∈ U}), f˜i = f (di , zi , {η̃˜u : u ∈ U}) ∈ J are functions that satisfy
|f˜i − fi | 6

4f¯ X ′
4f¯ X ′
|x̃i (ηu − η̃u ) + rui | + 4f¯hk̄ and |f˜i − f˜˜i | 6
|x̃ (η̃u − η˜˜u )|
h u∈U
h u∈U i

(3.41)

In particualr, taking f˜i := fbi ∧ 2f¯ where fbi is defined in (2.15) or (2.16). (Due to uniform
consistency (3.38) the minimum with 2f¯ is not binding for n large.) Therefore we have
Ē[(f˜i − fi )2 ] . h2k̄ + (1/h2 )

X
u∈U

2
Ē[|x̃′i (ηu − η̃u )|2 ] + Ē[rui
] . h2k̄ + h−2 s log(pn)/n. (3.42)

We define the function class F as
F = {(g̃, ṽ := f˜(d − m̃)) : g̃ ∈ G, m̃ ∈ M, f˜ ∈ J }
22

The rates of convergence and sparsity guarantees for βeτ and θeτ , and Condition D implies
that the estimates of the nuisance parameters b
gi := x′ βeτ and b
vi = fbi (di − x′ θeτ ) belongs to
i

i

the proposed F with probability 1 − o(1).

We will proceed to verify relations (2.35) and (2.36) hold under Condition AS, M and

D. We begin with (2.35). We have
Ē[|g̃i − gτ i |2 ] 6 2Ē[{x′i (β̃ − βτ )}2 ] + 2Ē[rτ2i ] . s log(pn)/n . δn n−1/2

Ē[|ṽi ||g̃i − gτ i |2 ] 6 2Ē[|ṽi ||x′i (β̃ − βτ )|2 ] + 2Ē[|ṽi |rτ2i ]

6 2{Ē[ṽi2 {x′i (β̃ − βτ )}2 ]Ē[{x′i (β̃ − βτ )}2 ]}1/2 + 2{Ē[ṽi2 rτ2i ]Ē[rτ2i ]}1/2
. {s log(pn)/n}1/2 f¯{Ē[(d − x′ θ̃)2 {x′ (β̃ − βτ )}2 ] + Ē[(d − x′ θ̃)2 r 2 ]}1/2
i

i

i

τi

. s log(pn)/n . δn n−1/2 .

since k(1, −θ)k 6 C and fi ∨ f˜i 6 2f¯, Ē[(x̃′i ξ)4] 6 Ckξk4, Ē[(x̃′i ξ)2 rτ2i ] 6 Ckξk2Ē[rτ2i ] and

Ē[rτ2i ] . s/n which hold by Conditions AS and M. Similarly we have

Ē[|ṽi − vi |{g̃i − gτ i }2 ] 6 Ē[|f˜i − fi ||di − x′i θτ 0 |{g̃i − gτ i }2 ] + Ē[f˜i |x′i (θ̃ − θτ 0 )|{g̃i − gτ i }2 ]
. s log(pn)/n . δn n−1/2 .

as |f˜i − fi | 6 2f¯. Moreover we have that
Ē[(ṽi − vi )2 ] 6 2Ē[(f˜i − fi )2 (di − xi θτ 0 )2 + f˜i2 {x′i (θ̃ − θτ 0 )}2 ]
6 4f¯Ē[(f˜i − fi )2 ]1/2 Ē[(di − x′i θτ 0 )4 ]1/2 + 2f¯2 Ē[{x′i (θ̃ − θτ 0 )}2 ]
p
√
. h1 s log(pn)/n + hk̄ + λ s/n . δn

√
under (3.42), h−2 s log(pn) 6 δn2 n, h 6 δn , and λ s 6 δn n. The next relation follows from
Ē[|ṽi − vi ||g̃i − gτ i |] 6 Ē[|f˜i − fi ||di − x′i θτ 0 ||g̃i − gτ i |] + Ē[f˜i |x′i (θ̃ − θτ 0 )||g̃i − gτ i |]
6 Ē[|f˜i − fi |2 ]1/2 Ē[|di − x′ θτ 0 |2 |g̃i − gτ i |2 ]1/2
i

+f¯Ē[|x′i (θ̃

2 1/2

Ē[|g̃i − gτ i |2 ]1/2
p
. {s log(pn)/n}1/2 { h1 s log(pn)/n + hk̄ } . δn n−1/2 .
− θτ 0 )| ]

23

under h−2 s2 log2 (pn) 6 δn2 n and hk̄

p

s log(pn) 6 δn .

Finally, since |Ē[fi vi rτ i ]| 6 δn n−1/2 from Condition M and Ē[fi vi xi ] = 0 from (2.7), we
have
|Ē[fi vi {g̃i − gτ i }]| 6 |Ē[fi vi x′i (β̃ − βτ )]| + |Ē[fi vi rτ i ]| 6 δn n−1/2 .
Next we verify relation (2.36). By triangle inequality we have
sup
2 ,h̃∈F
|α−ατ |6δn

6

(En − Ē)[(τ − 1{yi 6 di α + g̃i })ṽi − (τ − 1{yi 6 di α + gτ i })vi ]
sup

2 ,h̃∈F
|α−ατ |6δn

(En − Ē)[(1{yi 6 di α + gτ i } − 1{yi 6 di α + g̃i })vi ]

(3.43)

+ sup|α−ατ |6δn2 ,h̃∈F (En − Ē)[(τ − 1{yi 6 di α + g̃i })(ṽi − vi )]
Consider the first term of the right hand side in (3.43). Note that F1 := {(1{yi 6 di α +
gτ i } − 1{yi 6 di α + g̃i })vi : g̃ ∈ G, |α − ατ | 6 δn2 } ⊂ F1a − F1b where F1a := 1{yi 6

di α + gτ i }vi : |α − ατ | 6 δn2 } is the product of a VC class of dimension 1 with the random

variable v, and F1b := {1{yi 6 di α + g̃i }vi : g̃ ∈ G, |α − ατ | 6 δn2 } is the product of v

p
with the union of Cs
VC classes of dimension Cs. Therefore, its entropy number satisfies
′

N(ǫkF1 kQ,2, F1 , k · kQ,2) 6 (A/ǫ)C s where we can take the envelope F1 (y, d, x) = 2|v|. Since

for any function m ∈ F1 we have
Ē[m2 ] = Ē[(1{yi 6 di α + gτ i } − 1{yi 6 di α + g̃i })2 vi2 ]
6 f¯Ē[|gτ i − g̃i |v 2 ] 6 Ē[|gτ i − g̃i |]1/2 Ē[v 4 ] . {s log(pn)/n}1/2 ,
i

i

from the conditional density function being uniformly bounded and the bounded fourth
moment assumption in Condition M(i), by Lemma 9 with σ := C{s log(pn)/n}1/4 , a = pn,
kF1 kP,2 = Ē[vi2 ]1/2 6 C, and kMkP,2 6 Kq we have with probability 1 − o(1)
sup |(En − Ē)[m]| .

m∈F1

{s log(pn)/n}1/4 p
s log(pn) + n−1 sKq log(pn) . δn n−1/2
n1/2

under s3 log3 (pn) 6 δn4 n and Kq2 s2 log2 (pn) 6 δn2 n.
24

Next consider the second term of the right hand side in (3.43). Note that F2 :=

{(τ − 1{yi 6 di α + g̃i })(ṽi − vi ) : (g̃, ṽ) ∈ F, |α − ατ | 6 δn2 } ⊆ F2a · F2b where F2a :=

p
{(τ − 1{yi 6 di α + g̃i }) : g̃ ∈ G} is a constant minus the union of Cs
VC classes of
dimension Cs, and F2b := {ṽi − vi : (g̃, ṽ) ∈ F }. Note that standard entropy calculations
yield
N(ǫkF2a F2b kQ,2 , F2, k · kQ,2) 6 N( 2ǫ kF2a kQ,2, F2a , k · kQ,2) N( 2ǫ kF2b kQ,2, F2b , k · kQ,2 )
Furthermore, since ṽi − vi = (f˜i − fi )vi /fi + f˜i x′i (θτ 0 − θ̃), we have
′
′′
F2b ⊂ F2b
+ F2b
:= (J − {fi }) · {vi /fi } + J · ({x′i θτ 0 } − M)
′
′′
and F2 ⊂ F2a · F2b
+ F2a · F2b
. By (3.41), a covering for J can be constructed based on
p
a covering for Bu := {η̃u : kη̃u k0 6 Cs, kη̃u − ηu k 6 C s log(pn)/n} which is the union of

p
sparse balls of dimension Cs. It follows that for the envelope FJ := 2f¯ ∨ K −1 kx̃i k∞ ,
q

Cs

we have

N(ǫkFJ kQ,2 , J , k · kQ,2) 6
For any m ∈ F2a ·

′
F2b

we have

Ē[m2 ] 6 Ē[(f˜i − fi )2 vi2 /fi2] . h−2
. h−2 s log(pn)/n + h2k̄ .

P

u∈U

Y

u∈U

N



ǫh/4f¯
√
, Bu , k
|U |Kq 2Cs

·k



2
Ē[{|x̃′i (η̃u − ηu )|2 + rui
}vi2 /fi2 ] + h2k̄ Ē[vi2 /fi2 ]

p
Therefore, by Lemma 9 with σ := h1 s log(pn)/n + hk̄ , a = pn, kF2′ kP,2 = k(2f¯ ∨
Kq−1 kx̃i k∞ )vi /fi kP,2 6 (1 + 2f¯)Kq , and kMkP,2 6 (1 + 2f¯)Kq we have with probability
1 − o(1)

p
s log(pn)/n + hk̄ p
sup |(En − Ē)(m)| .
s log(pn) + n−1 sKq log(pn) . δn n−1/2
1/2
′
n
m∈F2a ·F2b
1
h

under h−2 s2 log2 (pn) 6 δn2 n, hk̄

p
s log(pn) 6 δn and Kq2 s2 log2 (pn) 6 δn2 n.
25

p
Ce
sθτ

Moreover, M is the union of

′′
m ∈ F2a · F2b
we have



VC subgraph of dimension Ce
sθτ , and for any

Ē[m2 ] 6 Ē[f˜i2 |x′i (θτ 0 − θ̃)|2 ] 6 4f¯Ē[|x′i (θτ 0 − θ̃)|2 ] . h−2 s log(pn)/n + h2k̄ + (λ/n)2 s.
p
√
Therefore, by Lemma 9 with σ := C{ h1 s log(pn)/n+ hk̄ + λ s/n}, a = pnKq s, kF2′′ kP,2 =
k(2f¯ ∨ K −1 kx̃i k∞ )kxi k∞ kP,2 6 (1 + 2f¯)Kq , and kMkP,2 6 (1 + 2f¯)Kq we have with probaq

bility 1 − o(1)
sup
′′
m∈F2a ·F2b

|(En − Ē)(m)| .

1
h

q

s log(pn)
n

+ hk̄ +

n1/2

√
λ s
n p

under the conditions h−2 se
sθτ log2 (pn) 6 δn2 n, hk̄

seθτ log(pn)+n−1 seθτ Kq log(pn) . δn n−1/2

p
p
seθτ log(pn) 6 δn , λ se
sθτ log(pn) 6 δn n

and Kq2 se2θτ log2 (pn) 6 δn2 n assumed in Condition D.

Next we verify the second part of Condition IQR(iii), namely (2.37). Note that since
p
Aτ ⊂ {α : |α − ατ | 6 C/ log n + |e
ατ − ατ | 6 C s log(pn)/n}, α̌τ ∈ Aτ and s log(pn) 6 δn2 n

implies the required consistency |α̌τ − ατ | 6 δn . To show the other relation in (2.37),
equivalent to with probability 1 − o(1)
|En [ψα̌τ ,bh (yi , di , zi )]| 6 δn1/2 n−1/2 ,
note that for any α ∈ Aτ (since it implies |α − ατ | 6 δn ) and b
h ∈ F, we have with
probability 1 − o(1)

|En [ψα,bh (yi , di , zi )]| . |En [ψατ ,h0 (yi , di , zi )] + Ē[fi di vi ](α − ατ )|
+O(δn |α − ατ |Ē[d2i |vi |] + δn n−1/2 )

from relations (7.64) with α instead of α̌τ , (7.68), (7.69), and (7.71). Letting α∗ =
1/2

ατ − {Ē[fi di vi ]}−1 En [ψατ ,h0 (yi , di , zi )], we have |En [ψα∗ ,bh (yi , di , zi )]| = O(δn n−1/2 ) with
26

probability 1 − o(1) since |α∗ − ατ | .P n−1/2 . Thus, with probability 1 − o(1)
{ En [ψα̌τ ,bh (yi , di , zi )] }2
En [b
vi2 ]

6 Ln (α̌τ ) 6

min { En [ψα,bh (yi , di , zi )] }2

α∈Aτ

τ 2 (1

−

τ )2 En [b
vi2 ]

. δn n−1

as En [b
vi2 ] is bounded away from zero with probability 1 − o(1).

Next we verify Condition IQR(iv). The first condition follows from the uniform consisp
tency of fbi and maxi6n kxi k∞ kθ̃τ − θ0τ k1 .P Kq s log(pn)/n → 0 under K 2 s2 log2 (pn) 6
q

δn n. The second condition in IQR(iv) also follows since

k1{|ǫi | 6 |di (ατ − α̌τ ) + gτ i − b
gi |}k22,n 6 En [1{|ǫi | 6 |di (ατ − α̌τ )| + |x′i (βeτ − βτ )| + |rτ i |}]
6 En [1{|ǫi | 6 3|di (ατ − α̌τ )|}]

+En [1{|ǫi | 6 3|x′i (βeτ − βτ )|}] + En [1{|ǫi | 6 3|rτ i |}]
p
.P f¯Kq s log(pn)/n

which implies the result under Kq2 s2 log(pn) 6 δn n.

The consistency of σ
b1n follows from kb
vi − vi k2,n →P 0 and the moment conditions.

2
The consistency of σ
b3,n follow from Lemma 5. Next we show the consistency of σ
b2n
=
{En [fˇi2 (di , x′iŤ )′ (di , x′iŤ )]}−1
11 . Because fi > f , sparse eigenvalues of size ℓn s are bounded
away from zero and from above with probability 1 − ∆n , and maxi6n |fbi − fi | = oP (1) by

Condition D, we have

′ ′
′
−1
2
{En [fbi2 (di , x′iŤ )′ (di , x′iŤ )]}−1
11 = {En [fi (di , xiŤ ) (di , xiŤ )]}11 + oP (1).

So that σ
b2n − σ̃2n →P 0 for

2
2 2
2
′
2
′
−1
2
−1
σ̃2n
= {En [fi2 (di , x′iŤ )′ (di , x′iŤ )]}−1
11 = {En [fi di ]−En [fi di xiŤ ]{En [fi xiŤ xiŤ ]} En [fi xiŤ di ]} .

Next define θ̌τ [Ť ] = {En [fi2 xiŤ x′iŤ ]}−1 En [fi2 xiŤ di ] which is the least squares estimator of
regressing fi di on fi xiŤ . Let θ̌τ denote the associated p-dimensional vector. By definition
27

fi x′i θτ = fi di − fi rθτ − vi , so that
−2
σ̃2n
= En [fi2 d2i ] − En [fi2 di x′i θ̌τ ]

= En [fi2 d2i ] − En [fi di fi x′i θτ ] − En [fi di fi x′i (θ̌τ − θτ )]

= En [fi di vi ] − En [fi di fi rθτ i ] − En [fi di fi x′i (θ̌τ − θτ )]

= En [vi2 ] + En [vi {fi di − vi }] − En [fi di fi rθτ i ] − En [fi di fi x′i (θ̌ − θ0 )]

We have that |En [vi {fi di − vi }]| = |En [fi vi x′i θ0τ ]| = oP (δn ) since
Ē[(vi fi x′i θ0τ )2 ] 6 f¯2 {Ē[vi4 ]Ē[(x′i θ0τ )4 ]}1/2 6 C
and Ē[fi vi x′i θ0τ ] = 0. Moreover, En [fi di fi rθτ i ] 6 f¯i2 kdi k2,n krθτ i k2,n = oP (δn ), |En [fi di fi x′i (θ̌−
θτ )]| 6 kdi k2,n kfi x′i (θ̌τ − θτ )k2,n = oP (δn ) since |Ť | . seθτ + s with probability 1 − o(1) and
supp(θbτ ) ⊂ Ť .

Part 2. Proof of the Double Selection. The analysis of θbτ and βbτ are identical to the
corresponding analysis for Part 1. Let Tbτ∗ denote the set of variables used in the last step,
namely Tb∗ = supp(βbλτ ) ∪ supp(θbτ ) where βbλτ denotes the thresholded estimator. Using the
τ

τ

τ

same arguments as in Part 1, we have with probability 1 − o(1)
ns log p
|Tbτ∗ | . sb∗τ = s + 2 2 +
h λ

nhk̄
λ

!2

.

Next we establish preliminary rates for η̌τ := (α̌τ , β̌τ′ )′ that solves
η̌τ ∈ arg min En [fbi ρτ (yi − (di , x′iTb∗ )η)]
η

τ

(3.44)

where fbi = fbi (di , xi ) > 0 is a positive function of (di , zi ). We will apply Lemma 2 as the
problem above is a (post-selection) refitted quantile regression for (ỹi , x̃i ) = (fbi yi , fbi (di , x′ )′ ).
i

28

Indeed, conditional on {di , zi }ni=1 , quantile moment condition holds as
E[(τ − 1{fbi yi 6 fbi di ατ + fbi x′i βτ + fbi rτ i })fbi xi ] = E[(τ − 1{yi 6 di ατ + x′i βτ + rτ i })fbi xi ]
= Ē[(τ − Fy |d ,z (di ατ + x′ βτ + rτ i ))fbi xi ]
i

i

i

i

= 0.

Since maxi6n fbi ∧ fbi−1 . 1 with probability 1 − o(1), the required side conditions of Lemma
p
2 hold as in Part 1. We can take r̄τ = C s log(pn)/n with probability 1 − o(1). Finally, to
b let ητ = (ατ , β ′ )′ and ηbτ = (b
provide the bound Q,
ατ , βbλτ ′ )′ which are Cs-sparse vectors.
τ

τ

By definition supp(βbτ ) ⊂ Tbτ∗ so that

En [fbi {ρτ (yi −(di , x′i )η̌τ )−ρτ (yi −(di , x′i )ητ )}] 6 En [fbi {ρτ (yi −(di , x′i )b
ητ )−ρτ (yi −(di , x′i )ητ )}]
By Lemma 12 we have with probability 1 − o(1)

b := C
En [fbi {ρτ (yi − (di , x′i )b
ητ ) − ρτ (yi − (di , x′i )ητ )}] 6 Q

Thus, with probability 1 − o(1), Lemma 2 implies
s
Since s 6

s∗τ
b

and

kfbi (di , x′i )(η̌τ − ητ )k2,n .

1/φmin(Cs + Cb
s∗τ )

s log(pn)
.
n

(s + b
s∗τ ) log(pn)
nφmin(Cs + Cb
s∗τ )

′

6 C by Condition D we have kη̌τ − ητ k .

q

sb∗τ log p
.
n

Next we construct an orthogonal score function based on the solution of the weighted
quantile regression (3.44). By the first order condition for (α̌τ , β̌τ ) in (3.44) we have for
si ∈ ∂ρτ (yi − di α̌τ − x′i β̌τ ) that
En

"



di
si fbi
xiTbτ∗

#

= 0.

By taking linear combination of the selected covariates via (1, −θeτ ) and defining b
vi =
vi . Since si = τ − 1{yi 6
fbi (di − x′iTb∗ θeτ ) we have ψα,bh (yi , di , zi ) = (τ − 1{yi 6 di α + x′i β̌τ })b
τ

29

di α̌τ + x′i β̌τ } if yi 6= di α̌τ + x′i β̌τ ,
|En [ψα̌τ ,bh (yi , di , zi )]| 6 |En [si vbi ]| + En [1{yi = di α̌τ + x′i β̌τ }|b
vi |]

6 En [1{yi = di α̌τ + x′i β̌τ }|b
vi − vi |] + En [1{yi = di α̌τ + x′i β̌τ }|vi |].

Since sb∗τ := |Tbτ∗| . seθτ with probability 1 − o(1), and yi has no point mass, yi = di α̌τ + x′i β̌τ

for at most Ce
sθτ indices in {1, . . . , n}. Therefore, we have with probability 1 − o(1)
En [1{yi = di α̌τ + x′i β̌τ }|vi |] 6 n−1 Ce
sθτ max |vi | .P n−1 seθτ Kq δn−1/6 . δn1/3 n−1/2 .
i6n

under Kq2 e
s2θτ 6 δn n. Moreover,
En [1{yi = di α̌τ +

x′i β̌τ }|b
vi

with probability 1 − o(1) under

− vi |] 6
p

q

(1 + |Tbτ∗ |)/nkb
vi − vi k2,n . δn n−1/2

(3.45)

(3.46)

sb∗τ kb
vi − vi k2,n 6 δn holding with probability 1 − o(1).

Therefore, the orthogonal score function implicitly created by the double selection estimator
α̌τ approximately minimizes

|En [(τ − 1{yi 6 di α + x′i β̌τ })b
vi ]|2
e
,
Ln (α) =
En [{(τ − 1{yi 6 di α + x′i β̌τ })2 b
vi2 ]

en (α̌τ ) . δn1/3 n−1 with probability 1 − o(1) by (3.45) and (3.46). Thus
and we have L

the conditions of Lemma 5 hold and the double selection estimator has the stated linear
representation.


4

Auxiliary Inequalities

In this section we collect auxiliary inequalities that we use in our analysis.

30

Lemma 6 Consider ηbu and ηu where kηu k0 6 s. Denote by ηbuµ the vector obtained by

µ
thresholding ηbu as follows ηbuj
= ηbuj 1{|b
ηuj | > µ/En [x̃2ij ]1/2 }. We have that

kb
ηuµ − ηu k1 6 kb
ηu − ηu k1 + sµ/ minj6p En [x̃2ij ]1/2

|supp(b
η µ )| 6 s + kb
ηu − ηu k1 maxj6p En [x̃2ij ]1/2 /µ
n
√
p
kx̃′i (b
ηuµ − ηu )k2,n 6 kx̃′i (b
ηu − ηu )k2,n + φmax (s) minj6p2 Ensµ[x̃2 ]1/2 +
ij

kb
ηu −ηu k1
√
s

where φmax (m) = sup16kθk0 6m kx̃′i θk22,n /kθk2 .

o

Proof. (Proof of Lemma 6) Let Tu = supp(ηu ). The first relation follows from the
triangle inequality
ηuλ )Tuc k1
kb
ηuλ − ηu k1 = k(b
ηuλ − ηu )Tu k1 + k(b

ηuλ )Tuc k1
ηu − ηu )Tu k1 + k(b
6 k(b
ηuλ − ηbu )Tu k1 + k(b

ηu )Tuc k1
6 µs/ minj6p En [x̃2ij ]1/2 + k(b
ηu − ηu )Tu k1 + k(b
= µs/ minj6p En [x̃2ij ]1/2 + kb
ηu − ηu k1

To show the second result note that
kb
ηu − ηu k1 > {|supp(b
ηuµ )| − s}µ/ max En [x̃2ij ]1/2 .
j6p

ηu − ηu k1 maxj6p En [x̃2ij ]1/2 /µ which yields the result.
Therefore, we have |supp(b
ηuλ )| − s 6 kb
To show the third bound, we start using the triangle inequality
kx̃′i (b
ηuµ − ηu )k2,n 6 kx̃′i (b
ηuµ − ηbu )k2,n + kx̃′i (b
ηu − ηu )k2,n .

Without loss of generality assume that order the components is so that |(b
ηuµ − ηbu )j | is

decreasing. Let T1 be the set of s indices corresponding to the largest values of |(b
ηuµ − ηbu )j |.
Similarly define Tk as the set of s indices corresponding to the largest values of |(b
ηuµ − ηbu )j |
31

k−1
outside ∪m=1
Tm . Therefore, ηbuµ − ηbu =

of the components, k(b
ηuµ − ηbu )Tk k2,̟
P⌈p/s⌉

P⌈p/s⌉

(b
ηuµ − ηbu )Tk . Moreover, given the monotonicity
√
6 k(b
ηuµ − ηbu )Tk−1 k1 / s. Then, we have
k=1

(b
ηuµ − ηbu )Tk k2,n
P
6 kx̃′i (b
ηuµ − ηbu )T1 k2,n + k>2 kx̃′i (b
ηuµ − ηbu )Tk k2,n
p
p
P
ηuµ − ηbu )T1 k + φmax (s) k>2 k(b
ηuµ − ηbu )Tk k
6 φmax (s)k(b
p
p
P
√
√
ηuµ − ηbu )Tk k1 / s
6 φmax (s)µ s/ minj6p En [x̃2ij ]1/2 + φmax (s) k>1 k(b
p
p
√
√
= φmax (s)µ s/ minj6p En [x̃2ij ]1/2 + φmax (s)kb
ηuµ − ηbu k1 / s
p
√
√
6 φmax (s){2 sµ/ minj6p En [x̃2ij ]1/2 + 2kb
ηu − ηu k1 / s}

kx̃′i (b
ηuµ − ηbu )k2,n = kx̃′i

k=1

where the last inequality follows from the first result and the triangle inequality.

The following result follows from Theorem 7.4 of [16] and the union bound.

Lemma 7 (Moderate Deviation Inequality for Maximum of a Vector) Suppose that
Pn
i=1 Uij
,
Sj = qP
n
2
U
i=1 ij

where Uij are independent variables across i with mean zero. We have that




A
−1
P max |Sj | > Φ (1 − γ/2p) 6 γ 1 + 3 ,
16j6p
ℓn
where A is an absolute constant, provided that for ℓn > 0
n1/6
0 6 Φ (1 − γ/(2p)) 6
min M[Uj ] − 1,
ℓn 16j6p
−1

M[Uj ] :=

Pn

Lemma 8 Let Xi , i = 1, . . . , n, be independent random vectors in Rp . Let
 √

p
p
√
δ̄n := 2 C̄K k log(1 + k) log(p ∨ n) log n / n,
32



2 1/2
i=1 EUij
 .
Pn
1
3 1/3
i=1 E|Uij |
n
1
n

where K > {E[max16i6n kXi k2∞ ]}1/2 and C̄ is a universal constant. Then we have
"
#
q
 ′

2
′
2
2
E
sup
En (α Xi ) − E[(α Xi ) ]
6 δ̄n + δ̄n
sup
Ē[(α′ Xi )2 ].
kαk0 6k,kαk=1

kαk0 6k,kαk=1

Proof. It follows from Theorem 3.6 of [34], see [6] for details. 
We will also use the following result of [14].
Lemma 9 (Maximal Inequality) 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 [sup |Gn (f )|] 6 K
f ∈F

s

vσ 2 log



akF kP,2
σ



vkMkP,2
+ √
log
n



akF kP,2
σ

!

,

where K is an absolute constant. Moreover, for every t > 1, with probability > 1 − t−q/2 ,
h
i
√
−1/2
−1 −1/2
sup |Gn (f )| 6 (1+α)EP [sup |Gn (f )|]+K(q) (σ+n
kMkP,q ) t+α n
kMkP,2 t ,
f ∈F

f ∈F

∀α > 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 ,
s

!


vkMkP,q
akF kP,2
akF kP,2
+ √
,
sup |Gn (f )| 6 K(q, c) σ v log
log
σ
n
σ
f ∈F

(4.47)

where kMkP,q 6 n1/q kF kP,q and K(q, c) > 0 is a constant depending only on q and c.
33

5

Proofs for Section 2.1 of Supplementary Material

Proof. (Proof of Lemma 1) Let δ = ηbu − ηu and define

b
R(η)
= En [ρu (ỹi − x̃′i η)]−En [ρu (ỹi − x̃′i ηu −rui )]−En [(u−1{ỹi 6 x̃′i ηu +rui })(x̃′i η− x̃′i ηu −rui )].

b
b u )] 6 f¯krui k2 /2 and with probability at least 1 − γ,
By Lemma 11, R(η)
> 0, Ē[R(η
2,n
p
2
¯
b
R(ηu ) 6 R̄γ := 4 max{f krui k , krui k2,n log(8/γ)/n} 6 4Cs log(p/γ)/n from Condition
2,n

PQR. By definition of ηbu we have

b ηu ) − R(η
b u ) + En [(u − 1{ỹi 6 x̃′ ηu + rui })x̃′ ]δ = En [ρu (ỹi − x̃′ ηbu )] − En [ρu (ỹi − x̃′ ηu )]
R(b
i
i
i
i
6

Let N =

q

8cR̄γ /f +

10
f



f¯krui k2,n +

√
3cλu s
nκ2c

+

λu
kηu k1
n

−

λu
kb
ηu k1 .
n

√

8(1+2c) s log(16p/γ)
√
nκ2c

+

(5.48)


√
√
8c nR̄γ log(16p/γ)
λu {s log(p/γ)/n}1/2

denote the upper bound in the rate of convergence. Note that N > {s log(p/γ)/n}1/2 .

Suppose that the result is violated, so that kx̃′i δk2,n > N. Then by convexity of the
objective function in (2.26), there is also a vector δ̃ such that kx̃′i δ̃k2,n = N, and
En [ρu (ỹi − x̃′i (δ̃ + ηu ))] − En [ρu (ỹi − x̃′i ηu )] 6

λu
kηu k1
n

−

λu
kδ̃
n

+ ηu k1 .

(5.49)

Next we will show that with high probability such δ̃ cannot exist implying that kx̃′i δk2,n 6
N.
By the choice of λu > cΛu (1 − γ | x̃) the event Ω1 := { λnu > ckEn [(u − 1{ỹi 6
b1 (ηu ) 6 R̄γ }
x̃′ ηu + rui })x̃i ]k∞ } occurs with probability at least 1 − γ. The event Ω2 := {R
i

b
also holds with probability at least 1 − γ. Under Ω1 ∩ Ω2 , and since R(η)
> 0, we have
b u) −
−R(η

λu
kδ̃k1
cn

b u + δ̃) − R(η
b u ) + En [(u − 1{ỹi 6 x̃′ ηu + rui })x̃′ ]δ̃
6 R(η
i
i
= En [ρu (ỹi − x̃′i (δ̃ + ηu ))] − En [ρu (ỹi − x̃′i ηu )]

6

λu
kηu k1
n

−

λu
kδ̃
n

+ ηu k1
34

(5.50)

so that for c = (c + 1)/(c − 1)
kδ̃Tuc k1 6 ckδ̃Tu k1 +

nc
b u ).
R(η
λu (c − 1)

To establish that δ̃ ∈ Au := ∆2c ∪ {v : kx̃′i vk2,n = N, kvk1 6 2cnR̄γ /λu } we consider two
cases. If kδ̃Tuc k1 > 2ckδ̃Tu k1 we have

1
nc
b u)
R(η
kδ̃Tuc k1 6
2
λu (c − 1)

and consequentially

kδ̃k1 6 {1 + 1/(2c)}kδ̃Tuc k1 6
Otherwise kδ̃Tuc k1 6 2ckδ̃Tu k1 , and we have

2nc b
R(ηu ).
λu

√
kδ̃k1 6 (1 + 2c)kδ̃Tu k1 6 (1 + 2c) skx̃′i δ̃k2,n /κ2c .

Thus with probability 1 − 2γ, δ̃ ∈ Au .

Therefore, under Ω1 ∩ Ω2 , from (5.49), applying Lemma 13 (part (1) and (3) to cover

δ̃ ∈ Au ), for kx̃′i δ̃k2,n = N with probability at least 1 − 4γ we have

Ē[ρu (ỹi − x̃′i (δ̃ + ηu ))] − Ē[ρu (ỹi − x̃′i ηu )]
n
o
√
kx̃′ δ̃k
8cnR̄γ p
s
log(16p/γ)
+
6 λnu kδ̃k1 + i√n2,n 8(1+2c)
κ2c
λu N


n
o√
√
√
log(16p/γ)
8cnR̄γ
8(1+2c) s
3cλu s
′
√
6 2cR̄γ + kx̃i δ̃k2,n nκ2c +
+ λu N
κ2c
n

√
where we used the bound for kδ̃k1 6 (1 + 2c) skx̃′i δ̃k2,n /κ2c +
Using Lemma 10, since by assumption supδ̄∈Au

En [|rui ||x̃′i δ̄|2 ]
En [|x̃′i δ̄|2 ]

2nc
R̄γ .
λu

→ 0, we have

Ē[ρu (ỹi − x̃′i (ηu + δ̃)) − ρu (ỹi − x̃′i ηu )] > −f¯krui k2,n kx̃′i δ̃k2,n +

f kx̃′i δ̃k22,n
∧ q̄Au f kx̃′i δ̃k2,n
4

Note that N < 4q̄Au for n sufficiently large by the assumed side condition, so that the
minimum on the right hand side is achieved for the quadratic part. Therefore we have
f kx̃′i δ̃k22,n
6 2cR̄γ +kx̃′i δ̃k2,n
4

)
p
p
√
√
s
log(16p/γ)
n
R̄
log(16p/γ)
8(1
+
2c)
8c
3cλ
s
γ
u
√
f¯krui k2,n +
+
+
nκ2c
nκ2c
λu N

(

35

which implies that
kx̃′i δ̃k2,n 6

q

8cR̄γ /f

+ f8 f¯krui k2,n +

√
3cλu s
nκ2c

+

√

8(1+2c) s log(16p/γ)
√
nκ2c

+


√
√
8c nR̄γ log(16p/γ)
λu N

which violates the assumed condition that kx̃′i δ̃k2,n = N since N > {s log(p/γ)/n}1/2 . 
Proof. (Proof of Lemma 2) Let δbu = ηbu − ηu . By optimality of ηeu in (2.26) we have

with probability 1 − γ

b
En [ρu (ỹi − x̃′i ηeu )] − En [ρu (ỹi − x̃′i ηu )] 6 En [ρu (ỹi − x̃′i ηbu )] − En [ρu (ỹi − x̃′i ηu )] 6 Q.

(5.51)

b1/2 denote the upper bound in the rate of convergence where
Let N = 2f¯r̄u + Aε,n + 2Q

ηu − ηu )k2,n > N.
Aε,n is defined below. Suppose that the result is violated, so that kx̃′i (e
Then by convexity of the objective function in (2.26), there is also a vector δeu such that
kx̃′i δeu k2,n = N, kδeu k0 = ke
ηu − ηu k0 6 sbu + s and

b
En [ρu (ỹi − x̃′i (ηu + δeu ))] − En [ρu (ỹi − x̃′i ηu )] 6 Q.

(5.52)

Next we will show that with high probability such δeu cannot exist implying that kx̃′i (e
ηu −
ηu )k2,n 6 N with high probability.

By Lemma 13, with probability at least 1 − ε, we have
s
′
′
e
|(En − Ē)[ρu (ỹi − x̃i (ηu + δu )) − ρu (ỹi − x̃i ηu )]|
(b
su + s) log(16p/ε)
68
=: Aε,n . (5.53)
′e
nφmin (b
su + s)
kx̃i δu k2,n

Thus combining relations (5.51) and (5.53), we have

b
Ē[ρu (ỹi − x̃′i (ηu + δeu ))] − Ē[ρu (ỹi − x̃′i ηu )] 6 kx̃′i δeu k2,n Aε,n + Q

with probability at least 1 − ε. Invoking the sparse identifiability relation of Lemma 10,
E [|r | |x̃′ θ|2 ]

with the same probability, since supkδk0 6bsu +s nEnui[|x̃′ θ|2i ] → 0 by assumption,
i



b
(f kx̃′i δeu k22,n /4) ∧ qesbu f kx̃′i δeu k2,n 6 kx̃′i δeu k2,n f¯krui k2,n + Aε,n + Q.
36

where qesbu :=

f 3/2
2f¯′

inf kδk0 6bsu +s

kx̃′i θk32,n
.
En [|x̃′i θ|3 ]

Under the assumed growth condition, we have N < 4e
qsbu for n sufficiently large and the

minimum is achieved in the quadratic part. Therefore, for n sufficiently large, we have
b1/2 < N
kx̃′i δeu k2,n 6 f¯krui k2,n + Aε,n + 2Q

Thus with probability at least 1 − ε − γ − o(1) we have kx̃′i δeu k2,n < N which contradicts

its definition. Therefore, kx̃′i (e
ηu − ηu )k2,n 6 N with probability at least 1 − γ − ε − o(1). 

5.1

Technical Lemmas for Quantile Regression

Lemma 10 For a subset A ⊂ Rp let

3/2


q̄A = (1/2) · (f 3/2 /f¯′ ) · inf En |x̃′i δ|2
/En |x̃′i δ|3
δ∈A

and assume that for all δ ∈ A

Then, we have
Ē[ρu (ỹi −

x̃′i (ηu



Ē |rui | · |x̃′i δ|2 6 (f /[4f¯′ ])Ē[|x̃′i δ|2 ].

+ δ))] − Ē[ρu (ỹi −

x̃′i ηu )]

f kx̃′i δk22,n 
>
∧ q̄A f kx̃′i δk2,n − f¯krui k2,n kx̃′i δk2,n .
4

Proof. (Proof of Lemma 10) Let T = supp(ηu ), Qu (η) := Ē[ρu (ỹi − x̃′i η)], Ju =
1/2

(1/2)En [fi x̃i x̃′i ] and define kδku = kJu δk. The proof proceeds in steps.

Step 1. (Minoration). Define the maximal radius over which the criterion function can
be minorated by a quadratic function


1
′
2
¯
rA = sup r : Qu (ηu + δ) − Qu (ηu ) + f krui k2,n kx̃i δk2,n > kδku , ∀δ ∈ A, kδku 6 r .
2
r
37

Step 2 below shows that rA > q̄A . By construction of rA and the convexity of Qu (·) and
k · ku ,
Qu (ηu + δ) − Qu (ηu ) + f¯krui k2,n kx̃′i δk2,n >
n
o
kδk2u
kδku
′
¯
> 2 ∧ rA · inf δ̃∈A,kδ̃ku >rAQu (ηu + δ̃) − Qu (ηu ) + f krui k2,n kx̃i δ̃k2,n
o
n
2
2
2
u rA
> kδk2 u ∧ {q̄A kδku } .
> kδk2 u ∧ kδk
rA 4

Step 2. (rA > q̄A ) Let Fỹ|x̃ denote the conditional distribution of ỹ given x̃. From [20],
for any two scalars w and v we have that
ρu (w − v) − ρu (w) = −v(u − 1{w 6 0}) +

Z

0

v

(1{w 6 z} − 1{w 6 0})dz.

(5.54)

We will use (5.54) with w = ỹi − x̃′i ηu and v = x̃′i δ. Using the law of iterated expectations
and mean value expansion, we obtain for t̃x̃i ,t ∈ [0, t]
Qu (ηu + δ) − Qu (ηu ) + f¯krui k2,n kx̃′i δk2,n >

Qu (ηu + δ) − Qu (ηu ) + Ē [(u − 1{ỹi 6 x̃′i ηu })x̃′i δ] =
hR ′
i
x̃i δ
′
′
= Ē 0 Fỹi |x̃i (x̃i ηu + t) − Fỹi |x̃i (x̃i ηu )dt
hR ′
i
2
x̃ δ
= Ē 0 i tfỹi |x̃i (x̃′i ηu ) + t2 fỹ′ i |x̃i (x̃′i ηu + t̃x̃,t )dt
hR ′
i
x̃ δ
> kδk2u − 61 f¯′ Ē[|x̃′i δ|3 ] − Ē 0 i t[fỹi |x̃i (x̃′i ηu ) − fỹi |x̃i (gui )]dt

(5.55)

> 21 kδk2u + 14 f Ē[|x̃′i δ|2 ] − 61 f¯′ Ē[|x̃′i δ|3 ] − (f¯′ /2)Ē [|x̃′i ηu − gui | · |x̃′i δ|2 ] .
where the first inequality follows noting that Fỹi |x̃i (x̃′i ηu + rui ) = u and |Fỹi |x̃i (x̃′i ηu + rui ) −
Fỹ |x̃ (x̃′ ηu )| 6 f¯|rui |.
i

i

i

Moreover, by assumption we have
Ē [|x̃′i ηu − gui | · |x̃′i δ|2 ] = Ē [|rui | · |x̃′i δ|2 ]
6 (f /8)(2/f¯′)Ē[|x̃′ δ|2 ]
i

38

(5.56)

Note that for any δ such that kδku 6 q̄A we have kδku 6 q̄A 6 (1/2) · (f 3/2 /f¯′ ) ·
3/2
Ē [|x̃′i δ|2 ] /Ē [|x̃′i δ|3 ], it follows that (1/6)f¯′Ē[|x̃′i δ|3 ] 6 (1/8)f Ē[|x̃′i δ|2 ]. Combining this
with (5.56) we have


1
1
f Ē[|x̃′i δ|2 ] − f¯′ Ē[|x̃′i δ|3 ] − (f¯′ /2)Ē |x̃′i ηu − gui | · |x̃′i δ|2 > 0.
4
6

(5.57)

Combining (5.55) and (5.57) we have rA > q̄A . 

b u )] 6 f¯krui k2 /2, R(η
b u ) > 0 and
Lemma 11 Under Condition PQR we have Ē[R(η
2,n
p
b u ) > 4 max{f¯krui k2 , krui k2,n log(8/γ)/n}) 6 γ.
P (R(η
2,n

b u ) > 0 by convexity of ρu . Let ǫui =
Proof. (Proof of Lemma 11) We have that R(η
R
b u ) = −En [rui 1 1{ǫui 6 −trui }−1{ǫui 6 0} dt > 0.
ỹi − x̃′ ηu −rui . By Knight’s identity, R(η
i

0

b u )] = En [rui
Ē[R(η
6

R1

0
R1
En [rui 0

Fyi |x̃i (x̃′i ηu + (1 − t)rui ) − Fyi |x̃i (x̃′i ηu + rui ) dt]
f¯trui dt] 6 f¯krui k2 /2.
2,n

b u ) 6 2f¯krui k2 ) > 1/2 by Markov’s inequality.
Therefore P (R(η
2,n
R1
b u ) = En [rui zui ]. We have
Define zui := − 0 1{ǫui 6 −trui } − 1{ǫui 6 0} dt, so that R(η
P (En [rui zui ] 6 2f¯krui k2 ) > 1/2 so that for t > 4f¯krui k2 we have by Lemma 2.3.7 in [39]
2,n

2,n

1
P (|En [rui zui ]| > t) 6 2P (|En [rui zui ǫi ]| > t/4)
2

Since the rui zui ǫi is a symmetric random variable and |zui | 6 1, by Theorem 2.15 in [16]
we have
q
q
√
√
2
2 2
P ( n|En [rui zui ǫi ]| > t̄ En [rui
]) 6 P ( n|En [rui zui ǫi ]| > t̄ En [rui
zui ]) 6 2 exp(−t̄2 /2) 6 γ/8

for t̄ >

p

2 log(8/γ). Setting t = 4 max{f¯krui k22,n , krui k2,n

p

log(8/γ)/n} we have

P (En [rui zui ] > t) 6 4P (En [rui zui ǫi ] > t/4) 6 γ.


39

Lemma 12 Under Condition PQR, conditionally on {x̃i , i = 1, . . . , n}, for kb
ηu k0 6 k,
N 6 kx̃′i (b
ηu − ηu )k2,n 6 N̄ , we have with probability 1 − γ

En [ρu (ỹi −x̃′i ηbu )]−En [ρu (ỹi −x̃′i ηu )] 6

kx̃′i (b
ηu − ηu )k2,n
√
n


v
u
√
N̄
u (k + s) log(16p{1 + 3 n log( )}/γ) 

t
N
4+4


φmin (k + s)






+f¯kx̃′i (b
ηu − ηu )k22,n + f¯krui k2,n kx̃′i (b
ηu − ηu )k2,n .

Proof. (Proof of Lemma 12) By triangle inequality we have
En [ρu (ỹi − x̃′i ηbu ) − ρu (ỹi − x̃′i ηu )] 6 |(En − Ē)[ρu (ỹi − x̃′i ηbu )ρu (ỹi − x̃′i ηu )]|
+|Ē[ρu (ỹi − x̃′i ηbu ) − ρu (ỹi − x̃′i ηu )]|.

The first term is bounded by Lemma 13. The second term is bounded using the identity
(5.54) with w = ỹi − x̃′i ηu and v = x̃′i δ similarly to the argument in (5.55). Using the law
of iterated expectations and mean value expansion, we obtain for t̃x̃i ,t ∈ [0, t]
Qu (ηu + δ) − Qu (ηu ) − f¯krui k2,n kx̃′i δk2,n 6

Qu (ηu + δ) − Qu (ηu ) + Ē [(u − 1{ỹi 6 x̃′i ηu })x̃′i δ] =
hR ′
i
x̃i δ
′
′
= Ē 0 Fỹi |x̃i (x̃i ηu + t) − Fỹi |x̃i (x̃i ηu )dt

and noting that
"Z ′
#
"Z
x̃i δ
En
Fỹi |x̃i (x̃′i ηu + t) − Fỹi |x̃i (x̃′i ηu )dt 6 f¯En
0

0

x̃′i δ

(5.58)

#

tdt 6 f¯kx̃′i δk22,n .


Lemma 13 Let wi (b) = ρu (ỹi − x̃′i ηu −b)−ρu (ỹi − x̃′i ηu ). Then, conditional on {x̃1 , . . . , x̃n },
w e have with probability 1 − γ that for vectors in the restricted set
q
√
N̄


′
s log(16p{1 + 3 n log( N
)}/γ)
4(1
+
c)
wi (x̃i δ)
sup
Gn
6
4
+
kx̃′i δk2,n
κc
δ ∈ ∆c ,

N 6 kx̃′i δk2,n 6 N̄

40

Similarly, for sparse vectors
sup

Gn

1 6 kδk0 6 k,



wi (x̃′i δ)
kx̃′i δk2,n



6 4+4

s

√
k log(16p{1 + 3 n log(N̄ /N)}/γ)
φmin (k)

N 6 kx̃′i δk2,n 6 N̄

Similarly, for ℓ1 -bounded vectors


q
√
wi (x̃′i δ)
R1
Gn
sup
6
4
+
4
log(16p{1
+
3
n log(N̄/N )}/γ)
kx̃′i δk2,n
N
kδk1 6 R1 ,

N 6 kx̃′i δk2,n 6 N̄

Proof. (Proof of Lemma 13) Let wi (b) = ρu (ỹi − x̃′i ηu − b) − ρu (ỹi − x̃′i ηu ) 6 |b|. Note
that wi (b) − wi (a) 6 |b − a|.

For any δ ∈ Rp , since ρu is 1-Lipschitz, we have
 

w (x̃′ δ)
var Gn kx̃i′ δki2,n
6
i

En [{wi (x̃′i δ)}2 ]
kx̃′i δk22,n

6

En [|x̃′i δ|2 ]
kx̃′i δk22,n

6 1.

Then, by Lemma 2.3.7 in [38] (Symmetrization for Probabilities) we have for any M > 1








2
wi (x̃′i δ)
wi (x̃′i δ)
o
>M 6
> M/4
P sup Gn
P sup Gn
kx̃′i δk2,n
1 − M −2
kx̃′i δk2,n
δ∈∆c
δ∈∆c
where Gon is the symmetrized process.
Consider Ft = {δ ∈ ∆c : kx̃′i δk2,n = t}. We will consider the families of Ft for t ∈ [N, N̄].
For any δ ∈ Ft , t 6 t̃ we have



′
wi (x̃′i δ(t̃/t))
wi (x̃′i δ)
o
o wi (x̃i δ)
−
−
G
6
Gn
n
t
t
t̃

wi (x̃′i δ(t̃/t))
t

1
t



+


Gon



wi (x̃′i δ(t̃/t))
t

−

wi (x̃′i δ(t̃/t))
t̃

Gon wi (x̃′i δ) − wi (x̃′i δ[t̃/t]) + Gon wi (x̃′i δ(t̃/t))
 ′ 
√
√
|x̃ δ| |t−t̃|
nEn (|x̃′i δ|) t̃t 1t − 1t̃
6 nEn ti
+
t
 ′ 
√
√
|x̃ δ|
t−t̃
= 2 nEn ti
6 2 n t−t t̃ .
t
=

41



·

1
t



−

1
t̃

√
Let T be a ε-net {N =: t1 , t2 , . . . , tK := N̄ } of [N , N̄] such that |tk − tk+1 |/tk 6 1/[2 n].
√
Note that we can achieve that with |T | 6 3 n log(N̄/N ).
Therefore we have




wi (x̃′i δ)
wi (x̃′i δ)
o
o
6 1 + sup
sup
Gn
=: 1 + Ao .
sup Gn
′
′
kx̃
δk
t
t∈T δ∈∆c ,kx̃i δk2,n =t
δ∈∆c
2,n
i
P (Ao > K) 6 minψ>0 exp(−ψK)E[exp(ψAo )]


2
6 8p|T | minψ>0 exp(−ψK) exp 8ψ 2 s(1+c)
κ2
c

6 8p|T | exp(−K

2

2
/[16 s(1+c)
])
κ2c

2

where we set ψ = K/[16 s(1+c)
] and bounded
κ2
c

o

E [exp (ψA )] 6(1)
6(2)
6(3)
6(4)
6(5)
6(6)

!#
wi (x̃′i δ)
2|T | sup E exp ψ
sup
t
t∈T
δ∈∆c ,kx̃′i δk2,n =t
"
 ′ !#
x̃i δ
2|T | sup E exp 2ψ
sup
Gon
t
t∈T
δ∈∆c ,kx̃′i δk2,n =t
#
!#
"
"
kδk1
max |Gon (x̃ij )|
2|T | sup E exp 2ψ
sup
2
j6p
′
t
t∈T
δ∈∆c ,kx̃i δk2,n =t


 √
s(1 + c)
max |Gon (x̃ij )|
2|T |E exp 4ψ
κ

 c √ j6p

s(1 + c) o
4p|T | max E exp 4ψ
Gn (x̃ij )
j6p
κc


s(1 + c)2
8p|T | exp 8ψ 2
κ2c
"

Gon



where (1) follows by exp(maxi∈I |zi |) 6 2|I| maxi∈I exp(zi ), (2) by contraction principle
√
(Theorem 4.12 [25]), (3) |Gon (x̃′i δ)| 6 kδk1 kGon (x̃i )k∞ , (4) s(1 + c)kx̃′i δk2,n /kδk1 > κc , (6)
En [x2ij ] = 1 and exp(z) + exp(−z) 6 2 exp(z 2 /2).

The second result follows similarly by noting that
√
√
kδk1
kkx̃′i δk2,n
k
p
=p
.
sup
6
sup
t
φmin(k)
φmin(k)
16kδk0 6k,kx̃′i δk2,n =t
16kδk0 6k,kx̃′i δk2,n =t t
42

The third result follows similarly by noting that for ant t ∈ [N , N̄]
kδk1
R1
.
6
t
N
kδk1 6R1 ,kx̃′i δk2,n =t
sup



6

Proofs for Section 2.2 of Supplementary Material

Lemma 14 (Choice of λ) Suppose Condition WL holds, let c′ > c > 1, γ 6 1/n1/3 , and
√
λ > 2c′ nΦ−1 (1 − γ/2p). Then for n > n0 (δn , c′ , c) large enough
b−1 En [fi xi vi ]k∞ ) > 1 − γ{1 + o(1)} + 4∆n .
P (λ/n > 2ckΓ
τ0

bτ 0jj =
Proof. (Proof of Lemma 14) Since Γ
with probability at least 1 − ∆n we have

bτ 0jj − Γτ 0jj | 6 max
max |Γ
j6p

j6p

q

En [fbi2 x2ij vi2 ] and Γτ 0jj =

q

En [fi2 x2ij vi2 ],

q
En [(fbi − fi )2 x2ij vi2 ] 6 δn1/2

by Condition WL(iii). Further, Condition WL implies that Γτ 0jj is bounded away from
b−1 Γτ 0 k∞ →P 1, so
zero and from above uniformly in j = 1, . . . , p and n. Thus we have kΓ
τ0
p
−1
4
b Γτ 0 k∞ 6 c′ /c with probability 1 − ∆n for n > n0 (δn , c′ , c, Γτ 0 ). By the triangle
that kΓ
τ0
inequality

b−1 En [fi xi vi ]k∞ 6 kΓ
b−1 Γτ 0 k∞ kΓ−1 En [fi xi vi ]k∞
kΓ
τ0
τ0
τ0

(6.59)

Next we will apply Lemma 7 which is based on self-normalized moderate deviation
theory. Define Uij = fi xij vi −E[fi xij vi ] which is zero mean by construction and En [fi xij vi ] =

En [Uij ] since Ē[fi xij vi ] = 0. Moreover, we have minj6p Ē[Uij2 ] > c by Condition WL(ii) and

maxj6p Ē[|Uij |3 ] . maxj6p Ē[|fi xij vi |3 ] 6 C since Uij is demeaned and the last bound from
by Condition WL(ii). Using that by Condition WL(iii), with probability 1 − ∆n we have
43

maxj6p |(En − Ē)[Uij2 ]| 6 δn and by Condition WL(ii) minj6p Ē[Uij2 ] > c, we have that
q
q
p
4
2
′
En [Uij ] 6 c /c En [fi2 x2ij vi2 ] with probability 1 − ∆n for n sufficiently large. Therefore,
q
−1
c 4 c′ √
−1
b
P (λ/n > 2ckΓτ 0 En [fi xi vi ]k∞ ) > P (Φ (1 − γ/2p) > c′ c nkΓ−1
τ 0 En [fi xi vi ]k∞ ) − ∆n


q
√
nEn [fi xij vi ]
c 4 c′
−1
√
= P Φ (1 − γ/2p) > c′ c maxj6p
En [fi2 x2ij vi2 ]


q
√
nEn [Uij ]
c 2 c′
−1
> P Φ (1 − γ/2p) > c′ c maxj6p √
− 2∆n
2]
En [Uij


√
nE [U ]
> P Φ−1 (1 − γ/2p) > maxj6p √ n 2ij
− 2∆n
En [Uij ]

> 1 − 2pΦ(Φ−1 (1 − γ/2p))(1 + o(1)) − 2∆n

> 1 − γ{1 + o(1)} − 2∆n
where the last relation by Condition WL. 
Proof. (Proof of Lemma 3) Let δb = θbτ − θτ . By definition of θbτ we have

b 2 ] − 2En [fb2 (di − x′ θτ )xi ]′ δb = En [fb2 (di − x′ θbτ )2 ] − En [fb2 (di − x′ θτ )2 ]
En [fbi2 (x′i δ)
i
i
i
i
i
i
bτ θτ k1 − λ kΓ
bτ θbτ k1
6 λ kΓ
n

n

bτ δbT c k1
− nλ kΓ
θτ
λ
λ
bτ 0 δbT k1 − ℓkΓ
bτ 0 δbT c k1
6 n ukΓ
θτ
n
θτ

6

λ b b
kΓτ δTθτ k1
n

(6.60)

2
Therefore, using that c2f > En [(fbi2 − fi2 )2 vi2 /{fbi2 fi2 }] and c2r > En [fb2 rθτ
i ], we have

b 2 ] 6 2En [(fb2 − f 2 )vi xi /fi ]′ δb + 2En [fb2 rθτ i xi ]′ δb + 2(Γ
b
b −1 En [fi vi xi ])′ (Γ
b τ 0 δ)
En [fbi2 (x′i δ)
i
i
i
0
b τ 0 δbT k1 − λ ℓkΓ
b τ 0 δbT c k1
+ nλ ukΓ
θτ
n
θτ

b 2 ]}1/2 + 2kΓ
b 1
b −1 En [f 2 (di − x′ θτ )xi ]k∞ kΓ
b τ 0 δk
6 2{cf + cr }{En [fbi2 (x′i δ)
0
i
i

b τ 0 δbT k1 − λ ℓkΓ
b τ 0 δbT c k1
+ nλ ukΓ
θτ
n
θτ

b 2 ]}1/2 +
6 2{cf + cr }{En [fbi2 (x′i δ)

b 2 ]}1/2 +
6 2{cf + cr }{En [fbi2 (x′i δ)

44

λ
λ b b c
λ b b
b b
cn kΓτ 0 δk1 + n ukΓτ 0 δTθτ k1 − n ℓkΓτ 0 δTθτ k1


λ
1
λ
1
b b
b b c
n u + c kΓτ 0 δTθτ k1 − n ℓ − c kΓτ 0 δTθτ k1

(6.61)

Let c̃ =
that

cu+1 b
b−1
k Γτ 0 k ∞ k Γ
τ 0 k∞ .
cℓ−1

If δb 6∈ ∆c̃ we have u +

1
c



bτ 0 δbT k1 6 ℓ −
kΓ
θτ

b 2 ]}1/2 6 2{cf + cr }.
{En [fbi2 (x′i δ)

Otherwise assume δb ∈ ∆c̃ . In this case (6.61) yields

b 2 ] 6 2{cf + cr }{En [fb2 (x′ δ)
b 2 ]}1/2 +
En [fbi2 (x′i δ)
i
i

which implies

b 2 ]}1/2 +
6 2{cf + cr }{En [fbi2 (x′i δ)

λ
n
λ
n

u+
u+



1
c



bτ 0 δbT c k1 so
kΓ
θτ



1
λ
1
b b
b b c
c kΓτ 0 δTθτ k1 − n ℓ − c kΓτ 0 δTθτ k1

1 √
b 2 ]}1/2 /b
s{En [fbi2 (x′i δ)
κc̃
c


√ 
1
λ s
u+
6 2{cf + cr } +
nb
κc̃
c
To establish the ℓ1 -bound, first assume that δb ∈ ∆2c̃ . In that case


√
√
λs
1
s{c
+
c
}
f
r
2
′
2
1/2
b 1 6 (1 + 2c̃)kδbT k1 6 s{En [fb (x δ)
b ]} /b
+
.
u+
kδk
κ2c̃ 6 2
i
i
θτ
κ
b2c̃
nb
κc̃ b
c
κ2c̃


bτ 0 δbT k1 6 1 · ℓ − 1 kΓ
bτ 0 δbT c k1 so
Otherwise note that δb 6∈ ∆2c̃ implies that u + 1c kΓ
θτ
2
c
θτ
b 2 ]}1/2
{En [fbi2 (x′i δ)

that (6.61) gives




1
1λ
2 ′ b 2 1/2
2 ′ b 2 1/2
b
b
b
b
c
6 {cf +cr }2 .
2{cf + cr } − {En [fi (xi δ) ]}
kΓτ 0 δTθτ k1 6 {En [fi (xi δ) ]}
· ℓ−
2n
c

Therefore






b−1 k∞ n
1
1
2ckΓ
1
τ0
−1
b 1 6 1+
b k∞ kΓ
bτ 0 δbT c k1 6 1 +
c k1 6
1+
kδbTθτ
kΓ
{cf +cr }2
kδk
τ0
θτ
2c̃
2c̃
2c̃
ℓc − 1 λ


b−1 k∞ are uniformly bounded
Proof. (Proof of Lemma 4) Note that kfbk2∞ and kΓ
0

with probability going to one. Under the assumption on the design, for M defined in
Lemma 18 we have that minm∈M φmax (m ∧ n) is uniformly bounded. Thus by Lemma 18
with probability 1 − γ − o(1) we have

2
n{cf + cr } √
sm .
b
+ s .
λ
The bound then follows from Lemma 15. 
45

6.1

Technical Results for Post-Lasso with Estimated Weights

Lemma 15 (Performance of the Post-Lasso) Under Conditions WL, let Tbθτ denote
the support selected by θbτ , and θeτ be the Post-Lasso estimator based on Tbθτ . Then we have
for sbθτ = |Tbθτ |, with probability 1 − o(1)
s
√ √
φ
(b
s
)
sbθτ log p
c
max
θτ
f
′
′
kfbi (xi θτ + rθτ i − xi θeτ )k2,n .
+p
φmin(b
sθτ ) mini6n fbi
n φmin(b
sθτ ) mini6n fbi
′
b ′
+ min
b kfi (x θτ + rθτ i − x θ)k2,n
supp(θ)⊆Tθτ

i

i

bτ 0 6 Γ
b τ 6 uΓ
bτ 0 with u > 1 > ℓ > 1/c in
Moreover, if in addition λ satisfies (2.31), and ℓΓ

the first stage for Lasso, then we have with probability 1 − γ − o(1)


√
p
1
λ s
′
′
b
min kfi (xi θτ + rθτ i − xi θ)k2,n 6 3{cf + cr } + u +
+ 3f¯C s/n.
c nκc̃ mini6n fbi
supp(θ)⊆Tbθτ

Proof. (Proof of Lemma 15) Let F = diag(f ), Fb = diag(fb), X = [x1 ; . . . ; xn ]′ , mτ =

Xθτ + rθτ , and for a set of indices S ⊂ {1, . . . , p} we define the projection matrix on the
columns associated with the indices in S as PS = F X[S](F X[S]′F X[S])−1 F X[S]′ and PbS =

FbX[S](X[S]′ Fb′ FbX[S])−1 FbX[S]′ . Since fi di = fi mτ i +vi we have that fbi di = fbi mτ i +vi fbi /fi

and we have

Fbmτ − FbX θeτ = (I − PbTbθτ )Fbmτ − PbTbθτ FbF −1 v

where I is the identity operator. Therefore

(6.62)
kFbmτ − FbX θeτ k 6 k(I − PbTbθτ )Fbmτ k + kPbTbθτ FbF −1 vk.
p
√
Since kFbX[Tbθτ ]/ n(X[Tbθτ ]′ Fb′ FbX[Tbθτ ]/n)−1 k 6 kFb−1 k∞ 1/φmin(b
sθτ ), the last term in
(6.62) satisfies

p
√
kPbTbθτ FbF −1 vk 6 kFb −1k∞ 1/φmin(b
sθτ ) kX[Tbθτ ]′ Fb2 F −1 v/ nk
n
p
√
√ o
′ b2
2
−1
′
−1
b
b
b
sθτ ) kX[Tθτ ] {F − F }F v/ nk + kX[Tθτ ] F v/ nk
6 kF k∞ 1/φmin(b
n
o
p
√
√
√
sθτ ) kX[Tbθτ ]′ {Fb 2 − F 2 }F −1v/ nk + sbθτ kX ′ F v/ nk∞ .
6 kFb −1k∞ 1/φmin(b
46

Condition WL(iii) implies that
√
kX[Tbθτ ]′ {Fb2 −F 2 }F −1v/ nk 6

sup
kαk0 6b
sθτ ,kαk61

√
√ p
|α′X[Tbθτ ]′ {Fb 2 −F 2 }F −1 v/ n| 6 n φmax (b
sθτ )cf .

Under Condition WL(iv), by Lemma 14 we have with probability 1 − o(1)
′

√

kX F v/ nk∞ .P

p

log(pn) max

16j6p

Moreover, Condition WL(iv) also implies max16j6p

q

En [fi2 x2ij vi2 ].

q
En [fi2 x2ij vi2 ] . 1 with probability 1 −

o(1) since max16j6p |(En −Ē)[fi2 x2ij vi2 ]| 6 δn with probability 1−∆n , and max16j6p Ē[fi2 x2ij vi2 ] 6

max16j6p {Ē[fi3 x3ij vi3 ]}2/3 . 1.

The last statement follows from noting that the Lasso solution provides an upper bound
to the approximation of the best model based on Tbθτ , and the application of Lemma 3.

Lemma 16 (Empirical pre-sparsity for Lasso) Let Tbθτ denote the support selected by
b−1 fi xi vi ]k∞ , and ℓΓ
bτ 0 6 Γ
bτ 6
the Lasso estimator, sbθτ = |Tbθτ |, assume λ/n > ckEn [Γ
τ0

bτ 0 with u > 1 > ℓ > 1/c. Then, for c0 = (uc + 1)/(ℓc − 1) and c̃ = (uc + 1)/(ℓc −
uΓ
b τ 0 k∞ kΓ
b−1 k∞ we have
1)kΓ
τ0
#
"
√ b
p
p
sk
Γ
k
n{c
+
c
}
τ0 ∞
f
r
b−1 k∞ c0
.
+
sbθτ 6 2 φmax (b
sθτ )(1 + 3kfbk∞ )kΓ
0
λ
κc̃ mini6n fbi

Proof. (Proof of Lemma 16) Let Fb = diag(fb), Rθτ = (rθτ 1 , . . . , rθτ n )′ , and X =
[x1 ; . . . ; xn ]′ . We have from the optimality conditions that the Lasso estimator θbτ satis-

fies

b−1 fb2 xi (di − x′ θbτ )] = sign(θbτ j )λ/n for each j ∈ Tbθτ .
2En [Γ
i
i
j

47

b−1 Γ
b0 k∞ 6 1/ℓ, we have
Therefore, noting that kΓ
p

b −1 X ′ Fb2 (D − X θbτ )) b k
sbθτ λ = 2k(Γ
Tθτ

b −1 X ′ Fb2 Rθτ ) b k
b −1 X ′ (Fb2 − F 2 )F −1 V ) b k + 2k(Γ
b −1 X ′ F V ) b k + 2k(Γ
6 2k(Γ
Tθτ
Tθτ
Tθτ

b −1 X ′ Fb2 X(θτ − θbτ )) b k
+2k(Γ
Tθτ
p
p
−1 b
−1 ′ ′
b
b
b −1 k∞ {cf + kFbk∞ cr } +
6 sbθτ kΓ Γ0 k∞ kΓτ 0 X F V k∞ + 2n φmax (b
sθτ )kΓ
p
b −1 k∞ kfbi x′i (θbτ − θτ )k2,n ,
sθτ )kFbk∞ kΓ
2n φmax (b
p
b −1 k∞
p
kΓ
0
b −1 X ′ F V k∞ + 2n φmax (b
(cf + kFbk∞ cr + kFbk∞ kfbi x′i (θbτ − θτ )k2,n ),
6 sbθτ (1/ℓ) nkΓ
s
)
θτ
τ0
ℓ

where we used that

k(X ′ Fb2 (θτ − θbτ ))Tbθτ k

6 supkδk0 6bsθτ ,kδk61 |δ ′ X ′ Fb2 X(θτ − θbτ )| 6 supkδk0 6bsθτ ,kδk61 kδ ′ X ′ Fb′ kkFbX(θτ − θbτ )k
p
6 supkδk 6bs ,kδk61 {δ ′ X ′ Fb 2 Xδ}1/2 kFbX(θτ − θbτ )k 6 n φmax (b
sθτ )kfbi k∞ kfbi x′ (θτ − θbτ )k2,n ,
0

i

θτ

k(X ′ (Fb2 − F 2 )F −1 V )Tbθτ k 6 supkδk0 6bsθτ ,kδk61 |δ ′ X ′ (Fb2 − F 2 )F −1 V |
p
6 supkδk 6bs ,kδk61 kXδk k(Fb 2 − F 2 )F −1 V k 6 n φmax (b
sθτ )cf
0

θτ

b−1 X ′ F V k∞ , and by Lemma 3, kfbi x′ (θbτ −θτ )k2,n 6 2{cf +cr }+ u +
Since λ/c > kΓ
τ0
i

we have

1
c



√ b
λ skΓ
τ 0 k∞
nκc̃ mini6n fbi

h
p
 √ Γbτ 0 k∞ i
b −1 k
kΓ
nc
sθτ ) 0 ℓ ∞ λf (1 + 2kFbk∞ ) + ncλr 3kFbk∞ + kFbk∞ u + 1c κ sk
2 φmax (b
p
b
c̃ mini6n fi

.
sbθτ 6
1
1 − cℓ
The result follows by noting that (u + [1/c])/(1 − 1/[ℓc]) = c0 ℓ by definition of c0 . 

Lemma 17 (Sub-linearity of maximal sparse eigenvalues) Let M be a semi-definite
positive matrix. For any integer k > 0 and constant ℓ > 1 we have φmax (⌈ℓk⌉)(M) 6
⌈ℓ⌉φmax (k)(M).
48

Lemma 18 (Sparsity for Estimated Lasso under data-driven penalty) Consider the
b−1 fi xi vi ]k∞ . Consider
Lasso estimator θbτ , let sbθτ = |Tbθτ |, and assume that λ/n > ckEn [Γ
τ0

the set

M=
Then,





b−1 k2 c2
m ∈ N : m > 8φmax (m)(1 + 3kfbk∞ )2 kΓ
0
∞ 0

"

#2 
√ b
skΓτ 0 k∞ 
n{cf + cr }
+
.
λ
κc̃ mini6n fbi 

#2
√ b
sk
n{c
+
c
}
Γ
k
f
r
τ0 ∞
b−1 k2 c2
.
+
sbθτ 6 4 min φmax (m) (1 + 3kfbk∞ )2 kΓ
0
∞ 0
m∈M
λ
κc̃ mini6n fbi
i
h
√ b
n{cf +cr }
skΓτ 0 k∞
b−1
.
Proof. (Proof of Lemma 18) Let Ln = 2(1 + 3kfbk∞ )kΓ
k
c
+
∞ 0
0
λ
κ min
fb


"



c̃

i6n

i

Rewriting the conclusion in Lemma 16 we have

sθτ 6 φmax (b
b
sθτ )L2n .

(6.63)

Consider any M ∈ M, and suppose b
sθτ > M. Therefore by the sublinearity of the maxi-

mum sparse eigenvalue (see Lemma 17)
 
sθτ
b
sbθτ 6
φmax (M)L2n .
M
Thus, since ⌈k⌉ 6 2k for any k > 1 we have

M 6 2φmax (M)L2n
which violates the condition that M ∈ M. Therefore, we have sbθτ 6 M.
In turn, applying (6.63) once more with sbθτ 6 M we obtain
sbθτ 6 φmax (M)L2n .

The result follows by minimizing the bound over M ∈ M. 
49

7

Proofs for Section 2.3 of Supplementary Material

In this section we denote the nuisance parameters as h̃ = (g̃, ι̃), where g̃ is a function of
variable z ∈ Z, and ι̃ is a function on (d, z) 7→ ι̃(d, z). We define the score with (α̃, h̃) as
ψα̃,h̃ (yi , di , zi ) = (τ − 1{yi 6 g̃(zi ) + di α̃})ι̃(di , xi ).
For notational convenience we write ι̃i = ι̃(di , zi ) and g̃i = g̃(zi ), h0 = (gτ , ι0 ) and b
h = (b
g, b
ι).

For a fixed α̃ ∈ R, g̃ : Z → R, and ι̃ : D × Z → R we define
Γ(α̃, h̃) := Ē[ψα,h (yi , di , zi )]

α=α̃,h=h̃

The partial derivative of Γ with respect to α at (α̃, h̃) is denoted by Γα (α̃, h̃) and the
directional derivative with respect to [b
h − h0 ] at (α̃, h̃) is denote as
Γ(α̃, h̃ + t[b
h − h0 ]) − Γ(α̃, h̃)
.
t→0
t

Γh (α̃, h̃)[b
h − h0 ] = lim

Proof. (Proof of Lemma 5) The asymptotic normality results is established in Steps
1-4 which assume Condition IQR(i-iii). The additional results (derived on Steps 5 and 6)
also assumed Condition IQR(iv).
Step 1. (Normality result) We have the following identity
En [ψα̌τ ,bh (yi , di , zi )] = En [ψατ ,h0 (yi , di , zi )] + En [ψα̌τ ,bh (yi , di , zi ) − ψατ ,h0 (yi , di , zi )]
= En [ψατ ,h0 (yi , di , zi )] + Γ(α̌τ , b
h)
| {z }

(7.64)

(I)

+n
|

−1/2

Gn (ψα̌τ ,bh − ψα̌τ ,h0 ) + n
{z
} |
(II)

−1/2

Gn (ψα̌τ ,h0 − ψατ ,h0 )
{z
}
(III)

By the second relation in (2.37), Condition IQR(iii), the left hand side of the display above
satisfies we have |En [ψα̌τ ,bh (yi , di , zi )]| . δn n−1/2 with probability at least 1 − ∆n . Since
50

b
h ∈ F with probability at least 1 − ∆n by Condition IQR(iii), with the same probability
we have |(II)| . δn n−1/2 .

We now proceed to bound term (III). By Condition IQR(iii) we have with probability
at least 1 − ∆n that |α̌τ − ατ | 6 δn . Observe that
(ψα,h0 − ψατ ,h0 )(yi , di , zi ) = (1{yi 6 gτ i + di ατ } − 1{yi 6 gτi + di α})ι0i
= (1{ǫi 6 0} − 1{ǫi 6 di (α − ατ )})ι0i ,
so that |(ψα,h0 − ψατ ,h0 )(yi , di , zi )| 6 1{|ǫi | 6 δn |di |}|ι0i | whenever |α − ατ | 6 δn . Since the
class of functions {(y, d, z) 7→ (ψα,h0 −ψατ ,h0 )(y, d, z) : |α−ατ | 6 δn } is a VC subgraph class
with VC index bounded by some constant independent of n, using (a version of) Theorem
2.14.1 in [38], we have
sup
|α−ατ |6δn

|Gn (ψα,h0 − ψατ ,h0 )| .P (Ē[1{|ǫi | 6 δn |di |}ι20i ])1/2 .P δn1/2 .
1/3

This implies that |III| . δn n−1/2 with probability 1 − o(1).

1/2

Therefore we have 0 = En [ψατ ,h0 (yi , di , zi )] + (II) + OP (δn n−1/2 ) + OP (δn )|α̌τ − ατ |.

Step 2 below establishes that (II) = −Ē[fi di ι0i ](α̌τ − ατ )| + OP (δn n−1/2 + δn |α̌τ − ατ |).
Combining these relations we have
Ē[fi di ι0i ](α̌τ − ατ ) = En [ψατ ,h0 (yi , di , zi )] + OP (δn1/2 n−1/2 ) + OP (δn )|α̌τ − ατ |.

(7.65)

√
Note that Un (τ ) = {Ē[ψα2 τ ,h0 (yi , di , zi )]}−1/2 nEn [ψατ ,h0 (yi , di , zi )] and Ē[ψα2 τ ,h0 (yi , di , zi )] =

τ (1−τ )Ē[ι20i ] so that the first representation result follows from (7.65). Since Ē[ψατ ,h0 (yi , di , zi )] =
0 and Ē[ι30i ] 6 C, by the Lyapunov CLT we have
√
and Un (τ )

nEn [ψατ ,h0 (yi , di , zi )] =

√

nEn [ψατ ,h0 (yi , di , zi )]

N(0, Ē[τ (1 − τ )ι20i ])

N(0, 1) follows by noting that |Ē[fi di ι0i ]| > c > 0.
51

Step 2.(Bounding Γ(α, b
h) for |α − ατ | 6 δn ) For any (fixed function) b
h ∈ F, we have

Γ(α, b
h) = Γ(α, h0) + Γ(α, b
h) − Γ(α, h0 )
= Γ(α, h0) + {Γ(α, b
h) − Γ(α, h0 ) − Γh (α, h0 )[b
h − h0 ]} + Γh (α, h0 )[b
h − h0 ].

(7.66)

Because Γ(ατ , h0 ) = 0, by Taylor expansion there is some α̃ ∈ [ατ , α] such that

Γ(α, h0) = Γ(ατ , h0 ) + Γα (α̃, h0 )(α − ατ ) = {Γα (ατ , h0 ) + ηn } (α − ατ )
where |ηn | 6 δn Ē[|d2i ι0i |] 6 δn C by relation (7.73) in Step 4.
Combining the argument above with relations (7.68), (7.69) and (7.71) in Step 3 below
we have
Γ(α, b
h) = Γh (ατ , h0 )[b
h − h0 ] + Γ(ατ , h0 ) + {Γα (ατ , h0 )
+O(δn Ē[|d2i ι0i |])}(α − ατ ) + O(δn n−1/2 )

(7.67)

= Γα (ατ , h0 )(α − ατ ) + O(δn |α − ατ |Ē[|d2i ι0i |] + δn n−1/2 )

Step 3. (Relations for Γh ) The directional derivative Γh with respect the direction b
h − h0

at a point h̃ = (g̃, z̃) is given by

Γh (α, h̃)[b
h − h0 ] = −Ē[fǫi |di ,zi (di (α − ατ ) + g̃i − gτ i )ι̃0i {b
gi − gτ i }]
+Ē[(τ − 1{yi 6 g̃i + di α}){b
ιi − ι0i }]

Note that when Γh is evaluated at (ατ , h0 ) we have with probability 1 − ∆n
|Γh (ατ , h0 )[b
h − h0 ]| = | − Ē[fi ι0i {b
gi − gτ i }]| 6 δn n−1/2

(7.68)

by b
h ∈ F with probability at least 1 − ∆n , and by P (yi 6 gτ i + di ατ | di , zi ) = τ . The
52

expression for Γh also leads to the following bound
Γh (α, h0 )[b
h − h0 ] − Γh (ατ , h0 )[b
h − h0 ] =

= |Ē[{fǫi |di ,zi (0) − fǫi|di ,zi (di (α − ατ ))}ι0i {b
gi − gτ i }]
+Ē[{Fi (0) − Fi (di (α − ατ ))}{b
ιi − ι0i }]|
6 Ē[|α − ατ | f¯′ |di ι0i | |b
gi − gτ i |] + Ē[f¯|(α − ατ )di | |b
ιi − ι0i |]
6 f¯′ |α − ατ |{Ē[|b
gi − gτ i |2 ] Ē[ι2 d2 ]}1/2 + f¯|α − ατ |{Ē[(b
ιi − ι0i )2 ]Ē[d2 ]}1/2
0i i

(7.69)

i

.P |α − ατ |δn
The second directional derivative Γhh at h̃ = (g̃, ι̃) with respect to the direction b
h − h0 ,
provided b
h ∈ F, can be bounded by
Γhh (α, h̃)[b
h − h0 , b
h − h0 ]

g i − g τ i }2 ]
= −Ē[fǫ′i |di ,zi (di (α − ατ ) + g̃i − gτ i )ι̃i {b

+2En [fǫi |di ,zi (di (α − ατ ) + g̃i − gτ i ){b
gi − gτ i }{b
ιi − ι0i }]
6 f¯′ Ē[|ι0i |{b
gi − gτ i }2 ] + f¯′ Ē[|b
ιi − ι0i |{b
g i − g τ i }2 ]
+2f¯Ē[|b
gi − gτ i || |b
ιi − ι0i |]

6 δn n−1/2

(7.70)
since h̃ ∈ [h0 , b
h], |ι̃(di , zi )| 6 |ι0 (di , zi )| + |b
ι(di , zi ) − ι0 (di , zi )|, and the last bound follows
from b
h ∈ F.
Therefore, provided that b
h ∈ F , we have
h
i
Γ(α, b
h) − Γ(α, h0 ) − Γh (α, h0 ) b
h − h0
6 sup

h̃∈[h0 ,b
h]
−1/2

. δn n

h
i
Γhh (α, h̃) b
h − h0 , b
h − h0

(7.71)

.

Step 4. (Relations for Γα ) By definition of Γ, its derivative with respect to α at (α, h̃) is
Γα (α, h̃) = −Ē[fǫi |di ,zi (di (α − ατ ) + g̃i − gτ i )di ι̃i ].
53

Therefore, evaluating Γα (α, h̃) at α = ατ and h̃ = h0 , since for fǫi |di ,zi (0) = fi we have
Γα (ατ , h0 ) = −Ē[fi di ι0i ].

(7.72)

Moreover, Γα also satisfies
|Γα (α, h0 ) − Γα (ατ , h0 )| = Ē[fǫi |di ,zi (di (α − ατ ) | di , zi )ι0i di ] − Ē[fi ι0i di ]
6 |α − ατ |f¯′ Ē[|d2 ι0i |]
i

(7.73)

6 |α − ατ |f¯′ {Ē[d4i ]Ē[ι20i ]}1/2 6 C ′ |α − ατ |

since Ē[d4i ] ∨ Ē[ιP 0i4 ] 6 C and f¯′ < C by Condition IQR(i).
Step 5. (Estimation of Variance) First note that
|En [fbi dib
ιi ] − Ē[fi di ι0i ]|
= |En [fbi dib
ιi ] − En [fi di ι0i ]| + |En [fi di ι0i ] − Ē[fi di ι0i ]|

6 |En [(fbi − fi )dib
ιi ]| + |En [fi di (b
ιi − ι0i )]| + |En [fi di ι0i ] − Ē[fi di ι0i ]|
6 |En [(fbi − fi )di (b
ιi − ι0i )]| + |En [(fbi − fi )di ι0i ]|
+kfi di k2,n kb
ιi − ι0i k2,n + | En [fi di ι0i ] − Ē[fi di ι0i ]|
.P k(fbi − fi )di k2,n kb
ιi − ι0i k2,n + kfbi − fi k2,n kdi ι0i k2,n

(7.74)

+kfi di k2,n kb
ιi − ι0i k2,n + |En [fi di ι0i ] − Ē[fi di ι0i ]|
.P δn

because fi , fbi 6 C, Ē[d4i ] 6 C, Ē[ι40i ] 6 C by Condition IQR(i) and Condition IQR(iv).

54

Next we proceed to control the other term of the variance. We have
| kψα̌τ ,bh (yi , di , zi )k2,n − kψατ ,h0 (yi , di , zi )k2,n | 6 kψα̌τ ,bh (yi , di , zi ) − ψατ ,h0 (yi , di , zi )k2,n
6 kψα̌τ ,bh (yi , di , zi ) − (τ − 1{yi 6 di α̌τ + g̃i })ι0i k2,n
+k(τ − 1{yi 6 di α̌τ + g̃i })ι0i − ψατ ,h0 (yi , di , zi )k2,n
6 kb
ιi − ι0i k2,n + k(1{yi 6 di ατ + gτ i } − 1{yi 6 di α̌τ + g̃i })ι0i k2,n
1/2

1/2

6 kb
ιi − ι0i k2,n + kι20i k2,n k1{|ǫi | 6 |di (ατ − α̌τ ) + gτ i − g̃i |}k2,n
.P δn

(7.75)
by IQR(ii) and IQR(iv). Also, |En [ψα2 τ ,h0 (yi , di , zi )] − Ē[ψα2 τ ,h0 (yi , di , zi )]| .P δn by independence and bounded moment conditions in Condition IQR(ii).
Step 6. (Main Step for χ2 ) Note that the denominator of Ln (ατ ) was analyzed in
relation (7.75) of Step 5. Next consider the numerator of Ln (ατ ). Since Γ(ατ , h0 ) =
Ē[ψατ ,h0 (yi , di , zi )] = 0 we have
En [ψατ ,bh (yi , di , zi )] = (En −Ē)[ψατ ,bh (yi , di , zi )−ψατ ,h0 (yi , di , zi )]+Γ(ατ , b
h)+En [ψατ ,h0 (yi , di , zi )].

By b
h ∈ F with probability 1 − ∆n and (7.67) with α = ατ , it follows that with the same

probability

|(En − Ē)[ψατ ,bh (yi , di , zi ) − ψατ ,h0 (yi , di , zi )]| 6 δn n−1/2 and |Γ(ατ , b
h)| . δn n−1/2 .

The identity nA2n = nBn2 + n(An − Bn )2 + 2nBn (An − Bn ) for An = En [ψατ ,bh (yi , di , xi )] and

Bn = En [ψατ ,h0 (yi , di , xi )] .P {τ (1 − τ )Ē[ι20i ]}1/2 n−1/2 yields
nLn (ατ ) =

n|En [ψατ ,bh (yi , di , zi )]|2
En [ψα2

b (yi , di , zi )]

τ ,h

=

n|En [ψατ ,h0 (yi , di , zi )]|2 + OP (δn )
n|En [ψατ ,h0 (yi , di , zi )]|2
=
+ OP (δn )
Ē[τ (1 − τ )ι20i ] + OP (δn )
Ē[τ (1 − τ )ι20i ]
55

since τ (1 − τ )Ē[ι20i ] is bounded away from zero because C 6 |Ē[fi di ι0i ]| = |Ē[vi ι0i ]| 6

{Ē[vi2 ]Ē[ι20i ]}1/2 and Ē[vi2 ] is bounded above uniformly. Therefore, the result then follows
√
since nEn [ψατ ,h0 (yi , di , zi )]
N(0, τ (1 − τ )Ē[ι20i ]).


8

Rates of convergence for fb

b | x̃) = x̃′ ηbu for u = τ − h, τ + h. Using a Taylor expansion for the conditional
Let Q(u
quantile function Q(· | x̃), assuming that sup|τ̃ −τ |6h |Q′′′ (τ̃ | x̃)| 6 C we have

|Q(τ + h | x̃) − x̃′ ηbτ +h | + |Q(τ − h | x̃) − x̃′ ηbτ −h |
′
′
b
+ Ch2 .
|Q (τ | x̃) − Q (τ | x̃)| 6
h
b′ (τ | x̃i ) which
In turn, to estimate fi , the conditional density at Q(τ | x̃), we set fbi = 1/Q
leads to

b′ (τ | x̃i ) − Q′ (τ | x̃i )|
|Q
b ′ (τ | x̃i ) − Q′ (τ | x̃i )|.
= (fbi fi ) · |Q
|fi − fbi | =
′
′
b
Q (τ | x̃i )Q (τ | x̃i )

(8.76)

Lemma 19 (Bound Rates for Density Estimator) Let x̃ = (d, x), suppose that c 6
fi 6 C, sup f ′ (ǫ | x̃i ) 6 f¯′ 6 C, i = 1, . . . , n, uniformly in n. Assume further that with
ǫ

ǫi |x̃i

probability 1 − ∆n we have for u = τ − h, τ + h that
r
r
C
s
log(p
∨
n)
s2 log(p ∨ n)
C
kx̃′i (b
ηu − ηu ) + rui k2,n 6
, kb
ηu − ηu k1 6 2
κc
n
κc
n
r
C s log(p ∨ n)
.
and |b
ηu1 − ηu1 | 6
κc
n
p
p
Then if sup |Q′′′ (τ̃ | x̃)| 6 C, maxkxi k∞ s2 log(p ∨ n) + maxi6n |di | s log(p ∨ n) 6
i6n
√ |τ̃ −τ |6h
2
δn hκc n and max krui k∞ 6 hδn we have
u=τ +h,τ −h

kfi − fbi k2,n

1
.P
hκc

r

s log(n ∨ p)
+ h2 , and
n

56

krui k∞ maxi6n kxi k∞
max |fi − fbi | .P max
+
i6n
u=τ +h,τ −h
h
hκ2c
r
maxi6n |di |∞ s log(n ∨ p)
+
+ h2 .
hκc
n

r

s2 log(n ∨ p)
n

Proof. Letting (δαu ; δβu ) = ηu − ηbu and x̃i = (di , x′i )′ we have that

x̃′ (η
−b
η
)+r
−x̃′ (η
−b
η
)−r
|fbi − fi | 6 |fi fbi i τ +h τ +h τ +h,i2h i τ −h τ −h τ −h,i | + Ch2
= h−1 (fi fbi )|x′i δβτ +h + di δατ +h + rτ +h,i − x′i δβτ −h − di δατ −h − rτ −h,i }| + Ch2

6 h−1 (fi fbi ) Kx kητ +h k1 + Kx kητ −h k1 + |di | · |δατ +h | + |di | · |δατ −h |

+|rτ +h,i − rτ −h,i |} + Ch2 .

The result follows because for sequences dn → 0, cn → 0 we have |fbi − fi | 6 |fbi fi |cn + dn
implies that fbi (1 − fi cn ) 6 fi + dn . Since fi is bounded, fi cn → 0 which implies that fbi is
bounded. Therefore, |fbi − fi | . cn + dn . We take dn = Ch2 → 0 and

cn = h−1 Kx kητ +h k1 + Kx kητ −h k1 + |di | · |δατ +h | + |di | · |δατ −h | + |rτ +h,i − rτ −h,i | →P 0

by the growth condition.
Moreover, we have
k(fbi − fi )/fi k2,n .

kfbi x̃′i (b
ητ +h − ητ +h ) + fbi rτ +h,i k2,n + kfbi x̃′i (b
ητ −h − ητ −h ) + fbi rτ +h,i k2,n
+ Ch2 .
h

By the previous result fbi is uniformly bounded from above with high probability. Thus,

the result follows by the assumed prediction norm rate kx̃′i (b
ηu − ηu ) + rui k2,n .


57

Optimal IV (C0.05,n) rp(0.05)

0.5
0.4
0.3
0.2
0.1
0
0.8

0.8
0.6

0.6
0.4

0.4
0.2

Rd2

0.2
0

0

Ry2

Optimal IV (I0.05,n) rp(0.05)

0.5
0.4
0.3
0.2
0.1
0
0.8

0.8
0.6

0.6
0.4

0.4
0.2

Rd2

0.2
0

0

Ry2

Optimal IV (C0.05,n) rp(0.05)

0.5
0.4
0.3
0.2
0.1
0
0.8

0.8
0.6

0.6
0.4

0.4
0.2

Rd2

0.2
0

0

Ry2

Optimal IV (I0.05,n) rp(0.05)

0.5
0.4
0.3
0.2
0.1
0
0.8

0.8
0.6

0.6
0.4

0.4
0.2

Rd2

0.2
0

0

Ry2

