arXiv:1605.07249v2 [math.ST] 4 Apr 2017

A Massive Data Framework for
M-Estimators with Cubic-Rate
Chengchun Shi, Wenbin Lu and Rui Song∗
Department of Statistics, North Carolina State University
April 6, 2017

Abstract
The divide and conquer method is a common strategy for handling massive data.
In this article, we study the divide and conquer method for cubic-rate estimators
under the massive data framework. We develop a general theory for establishing
the asymptotic distribution of the aggregated M-estimators using a simple average.
Under certain condition on the growing rate of the number of subgroups, the resulting
aggregated estimators are shown to have faster convergence rate and asymptotic
normal distribution, which are more tractable in both computation and inference than
the original M-estimators based on pooled data. Our theory applies to a wide class
of M-estimators with cube root convergence rate, including the location estimator,
maximum score estimator and value search estimator. Empirical performance via
simulations also validate our theoretical findings.

Keywords: Cubic rate asymptotics; divide and conquer; M-estimators; massive data.

The authors gratefully acknowledge please remember to list all relevant funding sources in the unblinded
version
∗

1

1

Introduction

In a world of explosively large data, effective estimation procedures are needed to deal
with the computational challenge arisen from analysis of massive data. The divide and
conquer method is a commonly used approach for handling massive data, which divides
data into several groups and aggregate all subgroup estimators by a simple average to
lessen the computational burden. A number of problems have been studied for the divide
and conquer method, including variable selection (Chen and Xie, 2014), nonparametric
regression (Zhang et al., 2013; Zhao et al., 2016) and bootstrap inference (Kleiner et al.,
2014), to mention a few. Most papers establish that the aggregated estimators achieve
the oracle result, in the sense that they possess the same nonasymptotic error bounds or
limiting distributions as the pooled estimators, which are obtained by fitting all the data
in a single model. This implies that the divide and conquer scheme can not only maintain
efficiency, but also obtain a feasible solution for analyzing massive data.
In addition to the computational advantages for handling massive data, the divide and
conquer method, somewhat surprisingly, can lead to aggregated estimators with improved
efficiency over pooled estimators with slower than the usual n1/2 convergence rate. There
is a wide class of M-estimators with n1/3 convergence rate. For example, Chernoff (1964)
studied a cubic-rate estimator for estimating the mode. It was shown therein that the
estimator converges in distribution to the argmax of a Brownian motion minus a quadratic
drift. Kim and Pollard (1990) systematically studied a class of cubic-rate M-estimators and
established their limiting distributions as the argmax of a general Gaussian process minus a
quadratic form. These results were extended to a more general class of M-estimators using
modern empirical process results (van der Vaart and Wellner, 1996; Kosorok, 2008). In this
paper, we mainly focus on M-estimators with cubic-rate and develop a unified inference
framework for the aggregated estimators obtained by the divide and conquer method. Our
theory states that the aggregated estimators can achieve a faster convergence rate than the
pooled estimators and have asymptotic normal distributions when the number of groups
diverges at a proper rate as the sample size of each group grows. This enables a simple
way for estimating the covariance matrix of the aggregated estimators.
When establishing the asymptotic properties of the aggregated estimators, a major technical challenge is to quantify the accumulated bias. Different from estimators with standard
n1/2 convergence rate, M-estimators with n1/3 convergence rate generally do not have a nice
linearization representation and the magnitude of the associated biases is difficult to quantify. In literature, a few works have been developed for studying the mean of the argmax
of a simple one-dimensional Brownian motion process plus a deterministic function (see for
example, Daniels and Skyrme, 1985; Cator and Groeneboom, 2006; Pimentel, 2014). In
particular, Groeneboom et al. (1999) provided a coupling inequality for the inverse process of the Grenander estimator based on Komlos-Major-Tusnady (KMT) approximation
(Komlós et al., 1975). However, it remains unclear and can be challenging to extend their
technique under a more general setting. On one hand, the KMT approximation requires
the underlying class of functions to be uniformly bounded (see for example, Rio, 1994;
Koltchinskii, 1994). This assumption is violated in some applications for M-estimators, for
2

example the value search estimator described in Section 3. On the other hand, their coupling inequality relies heavily on the properties of the argmax of a Brownian motion process
with a parabolic drift (Groeneboom, 1989), and is not applicable to cubic-rate estimators
that converge to the argmax of a more general Gaussian process minus a quadratic form.
Here, we propose a novel approach to derive a nonasymptotic error bound for the bias of
aggregated M-estimators.
A key innovation in our analysis is to introduce a linear perturbation in the empirical
objective function. In that way, we transform the problem of quantifying the bias into
comparison of the expected supremum of the empirical objective function and that of
its limiting Gaussian process. To bound the difference of these expected suprema, we
adopt similar techniques that have been recently studied by Chernozhukov et al. (2013)
and Chernozhukov et al. (2014). Specifically, they compared a function of the maximum
for sum of mean-zero Gaussian random vectors with that of multivariate mean-zero random
vectors with the same covariance function, and provided an associated coupling inequality.
We improve their arguments by providing more accurate approximation results (Lemma
6.3) for the identity function of maximums as needed in our applications.
Another major contribution of this paper is to provide a tail inequality for cubic-rate Mestimators (Theorem 5.1). This helps us to construct a truncated estimator with bounded
second moment, which is essential to apply Lindberg’s central limit theorem for establishing
the normality of the aggregated estimator. Under some additional tail assumptions on the
underlying empirical process, our results can be viewed as a generalization of empirical
process theories that establish consistency and n1/3 convergence rate for the M-estimators.
Based on the results, we show that the asymptotic variance of the aggregated estimator
can be consistently estimated by the sample variance of individual M-estimators in each
group, which largely simplifies the inference procedure for M-estimators.
The rest of the paper is organized as follows. We describe the divide and conquer
method for M-estimators and state the major central limit theorem (Theorem 2.1) in Section 2. Three examples for the location estimator, maximum score estimator and value
search estimator are presented in Section 3 to illustrate the application of Theorem 2.1.
Simulation studies are conducted in Section 4 to demonstrate the empirical performance
of the aggregated estimators. Section 5 studies a tail inequality and Section 6 provides
the analysis of bias of M-estimators that are needed to prove Theorem 2.1, followed by a
Discussion Section. All the technical proofs are provided in the Appendix.

2

Method

The divide and conquer scheme for M-estimators is described as follows. In the first step,
the data are randomly divided into several groups. For the jth group, consider the following
M-estimator
θ̂

(j)

=

arg max P(j)
nj m(·, θ)
θ∈Θ

nj
1 X
(j)
m(Xi , θ),
≡ arg max
θ∈Θ nj
i=1

3

j = 1, . . . , S,

(j)

(j)

where (X1 , . . . , Xnj ) denote the data for the jth group, nj is the number of observations
in the jth group, S is the number of groups, m(·, ·) is the objective function and θ is a
d-dimensional vector of parameters that belong to a compact parameter space Θ. In the
second step, the aggregated estimator θ̂0 is obtained as a simple average of all subgroup
estimators, i.e.
S
1 X (j)
θ̂0 =
θ̂ .
S j=1

(1)

(j)

We assume that all the Xi ’s are independent and identically distributed across i and j.
In addition, for notational simplicity and without loss of generality, we assume equal allocation among S groups, i.e. n1 = · · · = nS = n. Here, we only consider M-estimation with
non-smooth functions m(·, θ) of θ, and the resulting M-estimators θ̂(j) ’s have a convergence
rate of Op (n−1/3 ). Such cubic-rate M-estimators have been widely studied in the literature,
for example, the location estimator and maximum score estimator as demonstrated in the
next section. The limiting distributions of these estimators have also been established using
empirical process arguments (cf. Kim and Pollard, 1990; van der Vaart and Wellner, 1996).
To be specific, let θ0 denote the unique maximizer of E{m(·, θ)}, and assume θ0 ∈ Θ. Then,
ĥ(j) ≡ n1/3 (θ̂(j) − θ0 ) converges in distribution to h0 = arg maxh Z(h), where
1
Z(h) = G(h) − hT V h,
2

(2)

for some mean-zero Gaussian process G and positive definite matrix V = ∂ 2 E{m(·, θ)}/∂θθT |θ=θ0 .
The main goal of this paper is to establish the convergence rate and asymptotic normality of θ̂0 under suitable conditions for S and n, even though each θ̂(j) does not have a
tractable limiting distribution. The dimension d is assumed to be fixed, while the number
of groups S → ∞ as n → ∞. Let || · ||2 denote the Euclidean norm for vectors or induced
matrix L2 norm for matrices. We first introduce some conditions.
(A1.) There exists a small neighborhood Nδ = {θ : ||θ − θ0 ||2 ≤ δ} in which Em{(·, θ)}
is twice continuously differentiable with the Hessian matrix −V (θ), where V (θ) is positive
definite in Nδ . Moreover, assume E{m(·, θ0 )} > supθ∈Nδc E{m(·, θ)}.
(A2.) For any θ1 , θ2 ∈ Nδ , we have E{|m(·, θ1 ) − m(·, θ2 )|2 } = O(||θ1 − θ2 ||2 ).
(A3.) There exists some envelope function M(·) ≥ |m(·, θ)| for any θ, and ω = ||M(·)||ψ1 <
∞, where || · ||ψp denotes the Orzlic norm of a random variable.
(A4.) The envelope function MR (·) ≡ supθ {|m(·, θ)| : ||θ − θ0 ||2 ≤ R} satisfies EMR2 =
O(R) when R ≤ δ.
(A5.) The set of functions {m(·, θ)|θ ∈ Θ} has Vapnik-Chervonenkis (VC) index 1 ≤ v <
∞.
(A6.) For any θ ∈ Nδ , ||V (θ) − V ||2 = O(||θ − θ0 ||2 ), where V = V (θ0 ).
(A7.) Let L(·) denote the variance process of G(·) satisfying L(h) > 0 whenever h 6= 0. (i)
The function L(·) is symmetric and continuous, and has the rescaling property: L(kh) =
4

kL(h) for k > 0. (ii) For any h1 , h2 ∈ Rd satisfying ||h1 ||2 ≤ n1/3 δ and ||h2 ||2 ≤ n1/3 δ, we
have



(||h1 || + ||h2 ||)2
2
1/3
−1/3
−1/3
.
L(h1 − h2 ) − n E m(·, θ0 + n
h1 ) − m(·, θ0 + n
h2 )
=O
n1/3

Theorem 2.1 Under Conditions (A1)-(A7), if S = o(n1/6 / log4/3 n) and S → ∞ as n →
∞, we have
√

d

Sn1/3 (θ̂0 − θ0 ) → N(0, A),

(3)

for some positive definite matrix A.
Remark 2.1 Theorem 2.1 suggests that θ̂0 converges at a rate of Op (S −1/2 n−1/3 ). In contrast, the original M-estimator obtained based on pooled data has a convergence rate of
Op (S −1/3 n−1/3 ). This implies that we can gain efficiency by adopting the split and conquer
scheme for cubic-rate M-estimators. Such result is interesting as most aggregated estimators in the divide and conquer literature share the same convergence rates as the original
estimators based on pooled data.
Remark 2.2 The constraints on S suggest that the number of group cannot diverge too
fast. A main reason as we showed in the proof of Theorem 2.1 is that if S grows too fast,
the asymptotic normality of θ̂0 will fail due to accumulation of bias in the aggregation of
subgroup estimators. Given a data of size N, we can take S ≈ N l , n = N/S ≈ N 1−l with
l < 1/7 to fulfill this requirement.
Remark 2.3 Conditions A1 - A5 and A7 (i) are similar to those in Kim and Pollard
(1990) and are used to establish the cubic-rate convergence of the M-estimator in each
group. Conditions A6 and A7 (ii) are used to establish the normality of the aggregated
estimator. In particular, Condition A7 (ii) implies that the Gaussian process G(·) has
stationary increments, i.e. E[{G(h1 ) − G(h2 )}2 ] = L(h1 − h2 ) for any h1 , h2 ∈ Rd , which
is used to control the bias of the aggregated estimator.
In the rest of this section, we give a sketch for the proof of Theorem 2.1. The details of
the proof are given in Sections 5 and 6. By the definitions of θ̂0 and ĥ(j) , it is equivalent to
show
S
1 X (j) d
√
ĥ → N(0, A).
S j=1

(4)

When S diverges, intuitively, (4) follows by a direct application of Lindberg’s central
limit theorem for triangular arrays (cf. Theorem 11.1.1, Athreya and Lahiri, 2006). However, a few challenges remain. First, the estimator ĥ(j) may not possess finite second moment. Analogous to Kolmogorov’s 3-series theorem (cf. Theorem 8.3.5, Athreya and Lahiri,
5

2006), we handle this by first definingPh̃(j) , whichPis a truncated version of ĥ(j) with
||h̃(j) ||2 ≤ δn for some δn > 0, such that j ĥ(j) and j h̃(j) are tail equivalent, i.e.


lim Pr 
k


\ S(n)
X

n≥k



S(n)

ĥ(j) =

j=1

X
j=1



(j) 
h̃
= 1.


Using Borel-Cantelli lemma, it suffices to show


S(n)
S(n)
X
X
X
Pr 
ĥ(j) =
h̃(j)  < ∞.
n

j=1

(5)

j=1

Now it remains to show

S
S
o √
1 X n (j)
1 X (j)
d
√
h̃ = √
h̃ − E(h̃(j) ) + SEh̃(j) → N(0, A).
S j=1
S j=1

The second challenge is to control the accumulated bias in the aggregated estimator, i.e.
showing
√
SE(h̃(j) ) → 0.
(6)
Finally, it remains to show that the second moment of h̃(j) satisfies
E(aT h̃(j) )2 → aT Aa,

(7)

for any a ∈ Rd . Then, Theorem 2.1 holds when (5), (6) and (7) are established. Section 5
is devoted to verifying (5) and (7), while Section 6 is devoted to proving (6).

3

Applications

In this section, we illustrate our main theorem (Theorem 2.1) with three applications
including simple one-dimensional location estimator (Example 3.1) and more complicated
multi-dimensional estimators with some constraints, such as maximum score estimator
(Example 3.2) and value-search estimator (Example 3.3).

3.1

Location estimator
(j)

Let Xi (i = 1, . . . , n; j = 1, . . . , S) be i.i.d. random variables on the real line, with a
continuous density p. In each subgroup j, consider the location estimator
n

θ̂

(j)

1X
I(θ − 1 ≤ Xi ≤ θ + 1).
= arg max
θ∈R n
i=1
6

It was shown in Example 3.2.13 of van der Vaart and Wellner (1996) and Example
6.1 of Kim and Pollard (1990) that each θ̂(j) has a cubic-rate convergence. We assume
that Pr(X ∈ [θ − 1, θ + 1]) has a unique maximizer at θ0 . When the derivative of p
exists and is continuous, p′ (θ0 − 1) − p′ (θ0 + 1) > 0 implies that the second derivative
of Pr(X ∈ [θ − 1, θ + 1]) is negative for all θ within some small neighbor Nδ around θ0 .
Therefore, Condition (A2) holds, since
E|I(θ1 − 1 ≤ X ≤ θ1 + 1) − I(θ2 − 1 ≤ X ≤ θ2 + 1)|2
= Pr(θ1 − 1 ≤ X ≤ θ2 − 1) + Pr(θ1 + 1 ≤ X ≤ θ2 + 1)
≤ sup {p′ (θ − 1) + p′ (θ + 1)}|θ1 − θ2 |,
θ∈Nδ

for θ1 ≤ θ2 and |θ1 −θ2 | < 0.5. Moreover, if we further assume that p has continuous second
derivative in the neighborhood Nδ , Condition (A6) is satisfied.
The class of functions {|I(θ − 1 ≤ X ≤ θ + 1)| : θ ∈ Θ} is bounded by 1 and belongs to
VC class. In addition, we have
sup |I(θ − 1 ≤ X ≤ θ + 1) − I(θ0 − 1 ≤ X ≤ θ0 + 1)|

|θ−θ0 |<ǫ

≤ I(θ0 − 1 − ǫ ≤ X ≤ θ0 − 1 + ǫ) + I(θ0 + 1 − ǫ ≤ X ≤ θ0 + 1 + ǫ),
√
for small ǫ. The L2 (P ) norm of the function on the second line is O( ǫ). Hence, Conditions
(A4) and (A5) hold.
Next, we claim that Condition (A7) holds for function L(h) ≡ 2p(θ0 + 1)|h|, or equivalently {p(θ0 − 1) + p(θ0 + 1)}|h|, since p(θ0 − 1) = p(θ0 + 1). Obviously, L(·) is symmetric
and satisfies the rescaling property. For any h1 , h2 such that max(|h1 |, |h2 |) ≤ n1/3 δ, we
define θ1 = θ0 + n−1/3 h1 ∈ Nδ and θ2 = θ0 + n−1/3 h2 ∈ Nδ . Let [a, b] denote the indicator
function I(a ≤ X ≤ b). Assume h1 ≤ h2 . We have

n1/3 E |[θ1 − 1, θ1 + 1] − [θ2 − 1, θ2 + 1]|2 = n1/3 E[θ1 − 1, θ2 − 1] + n1/3 E[θ1 + 1, θ2 + 1]
Z θ2 −1
Z θ2 +1
1/3
1/3
= n
p(θ)dθ + n
p(θ)dθ = {p(θ0 + 1) + p(θ0 − 1)}(h2 − h1 ) + R,
θ1 −1

θ1 +1

where the remainder term R is bounded by
sup (|p(θ − 1) − p(θ0 − 1)| + |p(θ + 1) − p(θ0 + 1)|) (h2 − h1 )

θ1 ≤θ≤θ2

≤ sup 4n−1/3 |p′ (θ)|(h2 − h1 ) max(|h1 |, |h2 |) ≤ sup 4n−1/3 |p′ (θ)|(|h1 | + |h2 |)2 ,
θ∈Nδ

θ∈Nδ

using a first order Taylor expansion. The case when h1 > h2 can be similarly discussed.
Therefore, Condition (A7) holds. Theorem 2.1 then follows.

3.2

Maximum score estimator
(j)

(j) T

(j)

(j)

Consider the regression model Yi = Xi β0 + ei , , j = 1, · · · , S, where Xi is a d(j)
(j) (j)
dimensional vector of covariates and ei is the random error. Assume that (Xi , ei )’s are
7

i.i.d. copies of (X, e). The maximum score estimator is defined as
β̂

(j)

= arg max

||β||2 =1

n
X
i=1

(j)

{I(Yi

(j) T

≥ 0, Xi

(j)

β ≥ 0) + I(Yi

(j) T

< 0, Xi

β < 0)},

where the constraint ||β||2 = 1 is to guarantee the uniqueness of the maximizer.
Assume ||β0|| = 1, otherwise we can define β ⋆ = β0 /||β0 ||2 and establish the asymptotic
distribution of β̂0 − β ⋆ instead. It was shown in Example 6.4 of Kim and Pollard (1990)
that β̂ (j) has a cubic-rate convergence, when (i) median(e|X) = 0; (ii) X has a bounded,
continuously differentiable density p; and (iii) the angular component of X has a bounded
continuous density with respect to the surface measure on Sd−1 , which corresponds to the
unit sphere in Rd .
Theorem 2.1 is not directly applicable to this example since Assumption (A1) is violated.
The Hessian matrix
(j)

V =−

∂ 2 E{I(Yi

(j) T

≥ 0, Xi

(j) T

(j)

β ≥ 0) + I(Yi
∂ββ T

< 0, Xi

β < 0)}

|β0

is not positive definite. One possible solution is to use the arguments from the constrained
M-estimator literature (e.g. Geyer, 1994) to approximate the set ||β||2 = 1 by a hyperplane (β − β0 )T β = 0, and obtain a version of Theorem 2.1 for the constrained cubic-rate
M-estimators. We adopt an alternative approach here, and consider a simple reparameterization to make Theorem 2.1 applicable.
By Gram-Schmidt orthogonalization, we can obtain an orthogonal matrix [β0 , U0 ] with
U0 being a Rd×(d−1) matrix subject to the constraint U0T β0 = 0. Define
q
(8)
β(θ) = 1 − ||θ||22β0 + U0 θ,
for all θ ∈ Rd−1 and ||θ||2 ≤ 1. Take Θ to be the unit ball B2d−1 in Rd−1 . Define
θ̂(j) = arg max
θ∈Θ

n
X
i=1

(j)

[I(Yi

(j) T

≥ 0, Xi

(j)

β(θ) ≥ 0) + I(Yi

(j) T

< 0, Xi

β(θ) < 0)].

Note that under the assumption median(e|X) = 0, we have θ0 = 0.
Let m(y, x, β) = I(y ≥ 0, xT β ≥ 0) + I(y < 0, xT β < 0). Define
κ(x) = E{I(e + X T β0 ≥ 0) − I(e + X T β0 < 0)|X = x}.
It is shown in Kim and Pollard (1990) that
∂E{m(·, ·, β)}
T
−2
T
= ||β||−2
2 β β0 (I + ||β||2 ββ )
∂β

Z

κ(Tβ x)p(Tβ x)dσ,

xT β0 =0

where
T
T
−1
T
Tβ = (I − ||β||−2
2 ββ )(I − β0 β0 ) + ||β||2 ββ0 ,

8

(9)

and σ is the surface measure on the line xT β0 = 0.
Note that ∂β(θ)/∂θ has finite derivatives for all orders as long as ||θ||2 < 1. Assume that κ and p have twice continuous derivatives. This together with (9) implies that
E{m(·, ·, β(θ))} has third continuous derivative as a function of θ in a small neighborhood
Nδ (δ < 1) around 0. This verifies (A6). Moreover, for any θ1 , θ2 ∈ Nδ with ||θ1 − θ2 ||2 ≤ ǫ,
we have
2
q
q
2
2
2
2
1 − ||θ1 ||2 − 1 − ||θ2 ||2
||β(θ1) − β(θ2 )||2 = ||θ1 − θ2 ||2 +
2

(1 − ||θ1 ||22 − 1 + ||θ2 ||22 )
2||θ1 − θ2 ||22
= ||θ1 − θ2 ||22 + p
.
≤
2
p
1 − δ2
2
2
1 − ||θ1 ||2 + 1 − ||θ2 ||2

(10)

Kim and Pollard (1990) showed that E{|m(·, ·, β1) − m(·, ·, β2)|} = O(||β1 − β2 ||2 ) near β0 .
This together with (10) implies
E{|m(·, ·, β(θ1)) − m(·, ·, β(θ2))|2 } ≤ 2E{|m(·, ·, β(θ1)) − m(·, ·, β(θ2))|} = O(||θ1 − θ2 ||2 ).
Therefore, (A2) is satisfied and (A3) trivially holds since |m| ≤ 1.
It was also shown in Kim and Pollard (1990) that the envelope Mǫ of the class of
functions {m(·, ·, β) − m(·, ·, β0) : ||β − β0 ||2 ≤ ǫ} satisfies EMǫ2 = O(ǫ). Using (10), we can
show that the envelope M̃ǫ of the class of functions {m(·, ·, β(θ)) − m(·, ·, β0 ) : ||θ||2 ≤ ǫ}
also satisfies EM̃ǫ2 = O(ǫ). Thus, (A4) is satisfied. Moreover, since the class of functions
m(·, ·, β) over all β belongs to the VC class, so does the class of function m(·, ·, β(θ)). This
verifies (A5).
Finally, we establish (A7). For any θ1 , θ2 ∈ Nδ , define h1 = n1/3 θ1 and h2 = n1/3 θ2 . We
have
o
n
2
1/3
1/3
1/3
n E m(Y, X, β(h1 /n )) − m(Y, X, β(h2 /n ))

= n1/3 E I(X T β(h1 /n1/3 ) ≥ 0) − I(X T β(h2 /n1/3 ) ≥ 0) I(Y ≥ 0)

+ n1/3 E I(X T β(h1 /n1/3 ) < 0) − I(X T β(h2 /n1/3 ) < 0) I(Y < 0)

(11)
= n1/3 E I(X T β(h1 /n1/3 ) ≥ 0) − I(X T β(h2 /n1/3 ) ≥ 0) .

We write X as rβ0 + z with z orthogonal to β0 . Equation (11) can be written as
  s


 s
2
2


h1
h2
h1
T
T
 − I r 1 − h2
 .(12)
+
z
+
z
U
U
≥
0
≥
0
n1/3 E I r 1 −


n1/3 2
n1/3
n1/3 2
n1/3
Define ω = n1/3 r. Equation (12) can be expressed as
Z Z

 ω
I(−z T Uh1 (1 − n−2/3 ||h1 ||22 )−1/2 > ω ≥ −z T Uh2 (1 − n−2/3 ||h2 ||22 )−1/2 )p 1/3 , z dωdz.
n
9

Assume that p(r, z) is differentiable with respect to r and |∂p(r, z)/∂r| ≤ q(z) for some
function q. Then, (12) is equal to
Z
|z T U{h1 (1 − n−2/3 ||h1 ||22)−1/2 − h2 (1 − n−2/3 ||h2 ||22 )−1/2 }|p(0, z)dz + R1
Z
=
|z T U(h1 − h2 )|p(0, z)dz + R1 + R2 ,

where the remainders |R1 | and |R2 | are bounded by
Z
|R1 | ≤ n−1/3 {(z T Uh1 )2 + (z T Uh2 )2 }q(z)dz = O(n−1/3 {||h1 ||22 + ||h2 ||22}),
and

−2/3

||h1 ||22 )−1/2

−2/3

||h2 ||22 )−1/2

|R2 | ≤ |(1 − n

− 1|

Z

Z

|z T Uh1 |p(0, z)dz

− 1| |z T Uh2 |p(0, z)dz
Z
−1/3
≤ n
(||h1 ||2 + ||h2 ||) (|z T Uh1 | + |z T Uh2 |)p(0, z)dz = O(n−1/3 {||h1 ||22 + ||h2 ||22 }),
+ |(1 − n

under suitable moment assumptions on functions p(0, z) and q(z). This verifies (A7).
An application of Theorem 2.1 implies
S
1 X 1/3 (j) d
√
n θ̂ → N(0, A),
S j=1

for some positive definite matrix A ∈ R(d−1)×(d−1) . Hence

S
1 X 1/3 (j) d
√
n U θ̂ → N(0, UAU T ).
S j=1

(13)

By the definition of θ̂(j) and β̂ (j) , we have
q
S
S
1 X 1/3 (j)
1 X 1/3
(j)
√
n (β̂ − β0 − U θ̂ ) ≤ √
n | 1 − ||θ̂(j) ||22 − 1|
S j=1
S j=1
≤

S
n1/3 X (j) 2
1 X 1/3 |1 − ||θ̂(j) ||22 − 1|
√
≤ √
n q
||θ̂ ||2 .
S j=1
S
2
(j)
j
| 1 − ||θ̂ || + 1|
2

√
With probability at least 1−S/n → 1, the last expression is equal to O( Sn1/3 n−2/3 log2/3 n) =
o(1), which is implied by the tail inequality for θ̂(j) established in Theorem 5.1. Combining
this together with (13), we have
S
1 X 1/3 (j)
d
√
n (β̂ − β0 ) → N(0, UAU T ).
S j=1

10

3.3

Value search estimator

The value search estimator was introduced by Zhang et al. (2012) for estimating the optimal
(j)
(j)
(j)
(j)
treatment regime. The data can be summarized as i.i.d. triples {Oi = (Xi , Ai , Yi ), i =
(j)
(j)
1, . . . , n; j = 1, . . . , S}, where Xi ∈ Rd denote patient’s baseline covariates, Ai is the
(j)
treatment received by the patient taking the value 0 or 1, and Yi is the response, the
larger the better by convention. Consider the following model
(j)

Yi

(j)

(j)

(j)

(j)

= µ(Xi ) + Ai C(Xi ) + ei ,

(14)
(j)

where µ(·) is the baseline mean function, C(·) is the contrast function, and ei is the
(j)
(j)
(j)
random error with E{ei |Ai , Xi } = 0. The optimal treatment regime is defined in
(j)⋆
(j)⋆
the potential outcome framework. Specifically, let Yi (0) and Yi (1) be the potential
outcomes that would be observed if the patient received treatment 0 or 1, accordingly. For
(j)
a treatment regime d that maps Xi to {0, 1}, define the potential outcome
(j)⋆

Yi

(j)

(j)⋆

(d) = d(Xi )Yi

(j)

(j)⋆

(1) + {1 − d(Xi )}Yi

(0).

The optimal regime dopt is defined as the rule that maximizes the expected potential out(j)⋆
come, i.e, the value function, E{Yi (d)}. Under the stable unit treatment value assumption (SUTVA) and no unmeasured confounders assumption (Splawa-Neyman, 1990), the
optimal treatment regime under model (14) is given by dopt (x) = I{C(x) > 0}.
The true contrast function C(·) can be complex. As suggested by Zhang et al. (2012),
in practice we can find the restricted optimal regimen within a class of decision rules,
such as linear treatment decision rules d(x, β) = I(β1 + x1 β2 + · · · + xd βd+1 > 0) indexed
by β ∈ Rd+1 , where the subscript k denotes the kth element in the vector. Let β ⋆ =
(j)⋆
(j)
arg maxβ V (β), where V (β) = E{Yi (d(Xi , β))}. To make β ⋆ identifiable, we assume
⋆
)T . The restricted optimal treatment regime is given by
β1⋆ = −1. Define θ⋆ = (β2⋆ , · · · , βd+1
(j)⋆ ˜
(j)
d˜opt (x, θ⋆ ) = I(xT θ⋆ > 1) and the value function is defined by V (θ) = E{Yi (d(X
i , θ))}
˜ θ) = I(xT θ > 1). Zhang et al. (2012) proposed an inverse propensity score
with d(x,
weighted estimator of the value function V (θ) and the associated value search estimator by
maximizing the estimated value function. Specifically, for each group j, the value search
estimator is defined as
θ̂(j) = arg max
θ∈Θ

(j)

n ˜
(j)
(j)
(j)
˜ (j)
1 X d(X
i , θ)Ai + {1 − d(Xi , θ)}(1 − Ai ) (j)
Yi ,
(j) (j)
(j)
(j)
n i=1
πi Ai + (1 − πi )(1 − Ai )

(j)

(j)

where πi = Pr(Ai = 1|Xi ) is the propensity score and known in a randomized study.
(j)
Here, for illustration purpose, we assume that πi ’s are known.
(j)
(j) ˜
(j)
Define m(Oi , θ) = ξi d(X
i , θ), where
(j)

(j)

(j)

ξi

=

Ai

(j)

C(Xi ) +
(j)

πi

(j)

Ai − πi
(j)

(j)

πi (1 − πi )
11

n
o
(j)
(j)
µ(Xi ) + ei
.

(j)

(j)

With some algebra, we can show that θ̂(j) also maximizes Pn m(·, θ), where Pn is the
empirical measure for data in group j. Unlike the previous two examples, here the function
(j)
m is not bounded. To fulfill (A3), we need ||ξi ||ψ1 < ∞. This holds when 0 < γ1 <
(j)
(j)
(j)
πi < γ2 < 1 for some constants γ1 and γ2 , ||C(Xi )||ψ1 < ∞, ||µ(Xi )||ψ1 < ∞ and
(j)
||ei ||ψ1 < ∞.
To show (A1) and (A6), we evaluate the integral
Z
˜ θ)} = E{C(X)d̃(X, θ)} =
Γ(θ) = E{ξ d(X,
C(x)p(x)dx,
(15)
xT θ>1

(j)

where p(x) is the density function of Xi . Consider the transformation
T
−2
⋆ T
Tθ = (I − ||θ||−2
2 θθ ) + ||θ||2 θ(θ ) ,

which maps the region {xT θ⋆ > 1} onto {xT θ > 1}, and {xT θ⋆ = 1} onto {xT θ = 1}. We
exclude the trivial case with θ⋆ = 0. The above definition is meaningful when θ is taken
over a small neighborhood Nδ of θ⋆ . We assume that functions p and C are continuously
differentiable. Note that
∂Tθ x
θxT
2θθT (xT θ − xT θ⋆ )
{θT x − (θ⋆ )T x}
I
−
+
.
=−
∂θ
||θ||22
||θ||22
||θ||42
Using some differential geometry arguments similarly as in Section 5 of Kim and Pollard
(1990), we can show that the integral (15) can be represented as


Z
{θT x − (θ⋆ )T x} T ∂C(x)
θT x − (θ⋆ )T x ∂C(x)p(x)
1 T ∂C(x)p(x)
dx,
x+
θ−
θ
θ
Γ(θ) =
−
||θ||22
∂x
||θ||42
∂x
||θ||22
∂x
xT θ ⋆ >1
which is thrice differentiable under certain conditions on C(x), p(x) and their derivatives.
To show (A7), we assume that the conditional density p(x|y) of X given Y = 1 − X T θ⋆
exists and is continuously differentiable with respect to y. Similarly assume that the density
q(y) of Y exists and is continuously differentiable. Let g(X) = E(ξ 2 |X). For any h1 , h2 ∈
Rd , we have
o
n
2
1/3
2
T ⋆
−1/3 T
T ⋆
−1/3 T
n E ξ I(X θ + n
X h1 > 1) − I(X θ + n
X h2 > 1)
Z
= n1/3 g(x) I(n−1/3 xT h1 > y) − I(n−1/3 xT h2 > y) p(x|y)q(y)dxdy.
Let y = n−1/3 z. The last expression in the above equation can be written as
Z
g(x) I(xT h1 > z) − I(xT h2 > z) p(x|0)q(0)dxdz + R
Z
=
g(x)|xT (h1 − h2 )|p(x|0)q(0)dx + R,
12

with the remainder term
Z
R = g(x) I(xT h1 > z) − I(xT h2 > z) {p(x|n−1/3 z)q(n−1/3 z) − p(x|0)q(0)}dxdz,
which is O(n−1/3 (||h1 ||22 + ||h2 ||22 )) under certain conditions on q(x) and p(x|·). Conditions
(A2) and (A4) can be similarly verified. Since the class of functions {g(x)I(xT θ > 1) : θ ∈
Rd } has finite VC index, Condition (A5) also holds. Theorem 2.1 then follows.

4

Numerical studies

In this section, we examine the numerical performance of the aggregated M-estimator for
the three examples studied in the previous section and compare it with the M-estimator
based on pooled data, denoted as the pooled estimator.

4.1

Location estimator

The data Xj (j = 1, . . . , N) were independently generated from the standard normal distribution. The true parameter θ0 that maximizes E{I(θ − 1 ≤ Xj ≤ θ + 1)} was set to be
0. Let θ̃0 and θ̂0 denote the pooled estimator and the aggregated estimator, respectively.
To obtain θ̂0 , we randomly divided the data into S blocks with equal size n = N/S.
We took N = 2i for i = 12, 14, 16, 18, 20, and S = 2j for j = 3, . . . , 7. For each
combination of N and S, we estimated the standard error of θ̂0 by
c θ̂0 ) = √1
SE(
S

(

2
1 X  (l)
θ̂ − θ̂0
S − 1 l=1
S

)1/2

,

where θ̂(l) denotes the M-estimator for the lth group. For each scenario, we conducted 1000
simulation replications and report the bias and sample standard deviation (denoted as SD)
of estimators θ̃0 and θ̂0 , and estimated standard error and coverage probability (denoted
as CP) of Wald-type 95% confidence interval for θ̂0 in Table 1.
Based on the results, it can be seen that the aggregated estimator θ̂0 has much smaller
standard deviation than the pooled estimator θ̃0 , indicating the efficiency gain by the
divide and conquer scheme as shown in our theory. In addition, the bias of θ̂0 generally
becomes bigger and the standard deviation of θ̂0 generally becomes smaller when S and N
increase, and the normal approximation becomes more accurate when S increases. This
demonstrates the bias-variance trade off for aggregated estimators. With properly chosen
S, the estimated standard error of θ̂0 is close to its standard deviation and the coverage
probability is close to the nominal level.
Table 1: Bias and standard deviation (SD) for θ̃0 and θ̂0 , and estimated standard error and
coverage probabilities (CP) of Wald-type 95% confidence intervals for θ̂0 .

13

θ̃0
S=
N = 212

N = 214

N = 216

N = 218

N = 220

4.2

23

S=

24

θ̂0
S = 25

S = 26

S = 27

Bias
SD
d
SE
CP

−0.0017
0.0549
NA
NA

−0.0022
0.0397
0.0377
0.913

−0.0036
0.0350
0.0349
0.932

−0.0070
0.0339
0.0314
0.919

−0.0162
0.0297
0.0288
0.901

−0.0116
0.0496
0.0415
0.831

Bias
SD
d
SE
CP

−0.0032
0.0359
NA
NA

−0.0016
0.0248
0.0239
0.912

0.0003
0.0222
0.0218
0.922

−0.0015
0.0196
0.0197
0.953

−0.0045
0.0180
0.0175
0.940

−0.0073
0.0157
0.0159
0.924

Bias
SD
d
SE
CP

−0.0008
0.0216
NA
NA

−0.0002
0.0164
0.0151
0.900

−0.0004
0.0141
0.0138
0.939

−3.7 × 10−5
0.0129
0.0123
0.932

−0.0010
0.0111
0.0111
0.939

−0.0012
0.0097
0.0099
0.946

Bias
SD
d
SE
CP

−0.0003
0.0141
NA
NA

−0.0005
0.0101
0.0094
0.899

−0.0006
0.0089
0.0086
0.924

−0.0004
0.0078
0.0078
0.940

−0.0002
0.0070
0.0070
0.945

7.5 × 10−5
0.0064
0.0062
0.943

Bias
SD
d
SE
CP

4.8 × 10−5
0.0087
NA
NA

−9.7 × 10−5
0.0062
0.0060
0.920

6.0 × 10−5
0.0055
0.0055
0.940

0.0003
0.0049
0.0049
0.942

−0.0001
0.0046
0.0044
0.935

−4.3 × 10−5
0.0041
0.0040
0.936

Maximum score estimator

Consider the model Yi = 1.5Xi1 − 1.5Xi2 + 0.5ei , i = 1, · · · , N, where Xi1 , Xi2 and ei were
generated independently from the standard normal. Hence, θ0 = (θ1 , θ2 )T = (1.5, −1.5)T .
Let θ̃0 = (θ̃1 , θ̃2 )T denote the pooled estimator and θ̂0 = (θ̂1 , θ̂2 )T the aggregated estimator.
We set N = 218 , 220 , 222 and S = 24 , . . . , 27 . Table 2 reports the results based on 1000
replications. The findings are very similar to those for the location estimator in the previous
example.
d for θ̃1 , θ̃2 and θ̂1 , θ̂2 , and coverage
Table 2: Bias, standard deviation (SD), standard error (SE)
probabilities of CI for θ̂1 , θ̂2 .

14

θ̃1

N = 218

N = 220

N = 222

N = 218

N = 220

N = 222

4.3

S = 24

S = 25

θ̂1

S = 26

S = 27

Bias
SD
d
SE
CP

−1.3 × 10−5
0.0049
NA
NA

4.6 × 10−4
0.0030
0.0030
0.932

0.0011
0.0027
0.0027
0.922

0.0023
0.0025
0.0024
0.812

0.0040
0.0020
0.0020
0.467

−8.1 × 10−6
0.0032
NA
NA

7.7 × 10−5
0.0020
0.0019
0.925

1.9 × 10−4
0.0017
0.0017
0.941

4.4 × 10−4
0.0014
0.0015
0.945

0.0013
0.0014
0.0014
0.836

Bias
SD
d
SE
CP

−8.8 × 10−8
0.0021
NA
NA

−2.4 × 10−5
0.0012
0.0012
0.942

1.0 × 10−5
0.0011
0.0011
0.947

1.6 × 10−4
9.6 × 10−4
9.6 × 10−4
0.937

2.2 × 10−4
8.6 × 10−4
8.5 × 10−4
0.940

Bias
SD
d
SE
CP

2.0 × 10−5
0.0049
NA
NA

6.7 × 10−4
0.0030
0.0030
0.930

0.0014
0.0027
0.0027
0.908

0.0028
0.0025
0.0024
0.764

0.0048
0.0020
0.0020
0.322

6.4 × 10−6
0.0032
NA
NA

1.6 × 10−4
0.0020
0.0019
0.928

3.2 × 10−4
0.0017
0.0017
0.940

6.5 × 10−4
0.0015
0.0015
0.936

0.0016
0.0014
0.0014
0.786

Bias
SD
d
SE
CP

5.1 × 10−6
0.0021
NA
NA

1.0 × 10−5
0.0012
0.0012
0.941

6.4 × 10−5
0.0011
0.0011
0.942

2.5 × 10−4
9.6 × 10−4
9.6 × 10−4
0.932

3.5 × 10−4
8.6 × 10−4
8.5 × 10−4
0.932

Bias
SD
d
SE
CP

Bias
SD
d
SE
CP

θ̃2

θ̂2

Value search estimator

Consider the model Yi = 1 + Ai (2Xi − 1) + ei , i = 1, · · · , N, where Xi ∼ N(0, 1), ei ∼
N(0, 0.25), and Pr(Aj = 1) = 0.5. Under this model assumption, the optimal treatment
rule takes the form,
dopt (x) = I(2x > 1),
and hence β ⋆ = 2.
We conducted eight scenarios where S = 32, 64, and N = 224 , 225 , 226 and 227 . Due
to the large sample size and limited computer memory, it is extremely slow to calculate
the pooled estimators. Therefore, we only estimated the aggregated estimator θ̂0 . Simulation results based on 1000 replications are reported in Table 3. Except for the case with
15

S = 26 and N = 224 (where the bias is relatively large), the aggregated estimates have
relatively small bias; the estimated standard errors are close to the standard deviations of
the estimates; and the coverage probability is close to the nominal level.
d for θ̂0 , and coverage probabilities
Table 3: Bias, standard deviation (SD), standard error (SE)
of CI for θ̂0 .

N = 224

N = 225

5

Bias
SD
d
SE
CP
Bias
SD
d
SE
CP

S = 25

S = 26

0.0031
0.0087
0.0091
0.940

0.0087
0.0086
0.0086
0.840

−1.1 × 10−4
0.0068
0.0070
0.954

0.0031
0.0063
0.0064
0.921

N = 226

N = 227

Bias
SD
d
SE
CP
Bias
SD
d
SE
CP

S = 25

S = 26

−0.0013
0.0057
0.0055
0.929

2.2 × 10−4
0.0049
0.0050
0.939

−0.0015
0.0043
0.0039
0.932

−0.0014
0.0041
0.0044
0.926

Tail inequality for ĥ(j)

In this section, we establish tail inequalities for θ̂(j) and ĥ(j) , which are used to construct
h̃(j) , a truncated version of ĥ(j) with tail equivalence.
Theorem 5.1 Under Conditions (A1)-(A5), for sufficiently large n, there exists some constant C0 , such that
Pr(θ̂(j) ∈
/ Nδ ) ≤ 4 exp(−C0 n).

(16)

Moreover, for sufficiently large n, there exist some constants C1 , C2 > 0 and N0 ≥ 2, such
that
Pr(||ĥ(j) ||2 ≥ x|θ̂(j) ∈ Nδ ) ≤ C2 exp(−C1 x3 ),

(17)

for any N0 ≤ x ≤ n1/3 δ.
Remark 5.1 (16) and (17) can be viewed as generalization of the consistency and rate of
convergence results established for cube root estimators (cf. Corollary 4.2 in Kim and Pollard,
1990). The tail probability of ||ĥ(j) ||2 is obtained based on the subexponential tail Assumption (A3) for m(·, θ).
We represent ĥ(j) as

2/3
ĥ(j) = arg max Mn,j (h) ≡ arg max n1/6 G(j)
E(mh ) ,
n (mh ) + n
h∈Hn

h∈Hn

16

(j)

(j)

where Hn = {h ∈ Rd : n−1/3 h + θ0 ∈ Θ}, Gn = n1/2 (Pn − E) and mh (·) = m(·, θ0 +
n−1/3 h) − m(·, θ0 ). Similarly define
 1/6 (j)
n Gn (mh ) + n2/3 E(mh ) ,
h̃(j) = arg max Mn,j (h) = arg max
h∈Hn ∩Hδn

h∈Hn ∩Hδn

where Hδn = {h : ||h||2 ≤ δn }. By its definition, we have ||h̃(j)||2 ≤ δn . The following
Corollaries are immediate applications of Theorem 5.1.

Corollary 5.1 Under Conditions (A1)-(A5), for sufficiently large n, there exist some constants N0 ≥ 2, C4 and C5 , such that
Pr(||h̃(j) ||2 > x) ≤ C5 exp(−C4 x3 ),

∀x ≥ N0 .

(18)

The proof is straightforward by noting that for any x ≤ n1/3 δ,
Pr(||h̃(j) ||2 > x) ≤ Pr(||h̃(j) ||2 > x|θ̂(j) ∈ Nδ )Pr(θ̂(j) ∈ Nδ ) + Pr(θ̂(j) ∈
/ Nδ )
3
3
≤ C2 exp(−C1 x ) + 4 exp(−C0 n) ≤ C5 exp(−C4 x ).
Remark 5.2 Corollary 5.1 suggests that h̃(j) has finite moments of all orders. For any
a ∈ Rd and positive integer k, this implies that the sequence of random variables |aT h̃(j) |k
are uniformly integrable. This result is useful in establishing the convergence for moments
of h̃(j) (see Corollary 5.3).
1/3

1/3
Corollary 5.2 Under Conditions (A1)-(A5), taking δn = max(31/3 , 31/3 /C1 ) logP
n where
S
(j)
(j)
3
C1 is defined in Theorem 5.1, then h̃ and ĥ are tail equivalent. If S = o(n ), j=1 h̃(j)
P
and Sj=1 ĥ(j) are also tail equivalent.

Tail equivalence of h̃(j) and ĥ(j) follows by




 C
2
Pr h̃(j) 6= ĥ(j) = Pr ||ĥ(j) ||2 > δn ≤ 3 + 4 exp(−C0 n),
n

(19)

where the last inequality is implied by Theorem 5.1. The second assertion follows by an
application of Bonferroni’s inequality.
1/3
Corollary 5.2 proves (5). From now on, we take δn = max(31/3 , 31/3 /C1 ) log1/3 n. By
d
(19), Slutsky’s Theorem implies h̃(j) → h0 . Applying Skorohod’s representation Theorem
(cf. Section 9.4 in Athreya and Lahiri, 2006), we have that there exist random vectors
d
d
h̃(j)⋆ = h̃(j) and h⋆0 = h0 such that h̃(j)⋆ → h⋆0 , almost surely. This together with the
uniform integrability of ||h̃(j) ||k2 gives the following Corollary.
Corollary 5.3 Under Conditions (A1)-(A5), for any a ∈ Rd and integer k ≥ 1, we have
E{(aT h̃(j) )k } → E{(aT h0 )k } as n → ∞.
17

Remark 5.3 Taking k = 2, it proves (7). Moreover, Corollary 5.3 suggests a simple
scheme for estimating the covariance matrix A ≡ cov(h0 ) given in (3). For any vector a,
by law of large numbers, we obtain
S
1 X T (j) 2
a.s.
(a h̃ ) − E{(aT h̃(1) )2 } → 0.
S j=1

This togetherPwith tail equivalence between h̃(j) and ĥ(j) , and E{(aT h̃(1) )2 } → E{(aT h0 )2 }
implies that j (aT ĥ(j) )2 /S converges to aT Aa.

6

Analysis of the bias

In this section, we control the accumulated bias in the aggregated estimator as in (6). Our
method is inspired by the work of Pimentel (2014), which bounds the expectation of the
argmax of a stochastic process by the difference of the expected suprema of the stochastic
processes with and without a linear perturbation. To illustrate our idea, we first consider
a trivial case by analyzing the bias E(h0 ).

6.1

Stochastic process with a linear perturbation

Recall h0 = arg maxh∈Rd Z(h), where Z(h) = G(h) − 1/2hT V h. Under Condition (A7), the
covariance function Ω(h1 , h2 ) of G is equal to {L(h1 ) + L(h2 ) − L(h1 − h2 )}/2. Symmetry
d
d
of L(·) implies G(·) = G(−·) and Z(·) = Z(−·). Hence,
E(h0 ) = E{arg max Z(h)} =

1
[E{arg max Z(h)} + E{arg max Z(−h)}] = 0.
2

Here we provide an alternative but superfluous proof for this trivial case. Define the
stochastic process with a linear perturbation
Z ε,a (h) = Z(h) + εaT h,
for any ε ∈ R and a ∈ Rd . We have
εaT h0 + sup Z(h) ≤ sup Z ε,a (h).
h

h

Therefore, for any ε > 0,
1
a h0 ≤
ε
T

and
1
a h0 ≥
−ε
T



ε,a
sup Z (h) − sup Z(h) ,

(20)



(21)

h

sup Z
h

h

−ε,a



(h) − sup Z(h) .
h

18

It follows from (20) and (21) that


1
T
ε,a
−ε,a
|E(a h0 )| ≤ max |E{sup Z (h)} − E{sup Z(h)}|, |E{sup Z
(h)} − E{sup Z(h)|} .(22)
ε
h
h
h
h
In the next Lemma we show that the right-hand side of (22) is of the order O(ε) for any
a ∈ Rd with ||a||2 = 1. Taking ε → 0, we obtain E(aT h0 ) = 0, which implies E(h0 ) = 0.
Lemma 6.1 Let X(h) = B(h) − hT W h/2, where B(h) is a mean zero process with stationary increments and W is a positive definite matrix. Assume E{suph∈Rd X ε,a(h)} < ∞,
where X ε,a (h) = X(h) + εaT h. Then, we have
sup E{ sup X ε,a (h)} − E{ sup X(h)} = O(ε2).
h∈Rd

||a||2 =1

h∈Rd

As a result, we have E{arg maxh X(h)} = 0.
Remark 6.1 Lemma 6.1 can be viewed as a generalization of Theorem 4 in Pimentel
(2014). Here we only require the underlying process to have stationary increments. In
addition, we allow the underlying process to be indexed by multi-dimensional parameters.
The proof of Lemma 6.1 relies on the stationary increments property of B, which implies
d

sup X ε,a (h) = sup X(h) + B(εW −1 a) + ε2 aT W −1 a/2.
h

h

In the following lemma, we prove the finiteness of E{suph Z ε,a (h)}.
Lemma 6.2 Under Conditions (A1) - (A7), there exist some positive constants C6 , C7 , C8
and K0 such that


ε,a
sup
Pr sup Z (h) > x ≤ C6 exp(−C7 x2 ) + C8 exp(−x),
||a||2 =1,|ε|≤1

h

for any x ≥ K0 . As a result, for any integer m > 0, we have


ε,a
m
sup sup E {sup Z (h)} < ∞.
||a||2 =1 |ε|≤1

h

Remark 6.2 Lemma 6.2 shows that not only suph Z ε,a (h) possesses finite moments of all
orders, but also has a subexponential tail. This is quite surprising since the supremum is
taken on Rd . This result is due to the rescaling property of L(·).

19

6.2

Nonasymptotic bound for the bias

We now establish the order of |E(aT h̃(j) )|. Define the following process with a linear drift
εn ,a
Mn,j
(h) = Mn,j (h) + εn aT h,
εn ,a
(h)} <
for some sequence εn . By Condition (A3), it is immediate to see E{suph∈Hn ∩Hδn Mn,j
∞ for any εn and a. Similar to (20), (21) and (22), we can show

√

√

| SE(aT h̃)| ≤

S

εn

|E{

max |E{

sup
h∈Hn ∩Hδn

sup
h∈Hn ∩Hδn

−εn ,a
Mn,j
(h)}

εn ,a
Mn,j
(h)} − E{

− E{

sup

sup

Mn,j (h)}|,

h∈Hn ∩Hδn

!

Mn,j (h)}| ,

h∈Hn ∩Hδn

(23)

for any positive sequence εn .
εn ,a
Since Mn,j (h) converges weakly to Z(h), the expected supremum of Mn,j (h) and Mn,j
(h)
ε,a
should be close to those of Z(h) and Z (h), respectively. Define
∆n =

sup
|εn |≤1,||a||2 =1

|E{

sup
h∈Hn ∩Hδn

εn ,a
Mn,j
(h)} − E{ sup Z εn ,a (h)}|.

(24)

h∈Rd

It follows from (22) that
√

T

(j)

| SE(a h̃ )| ≤ 2

√

S

√

S



max |E{ sup Z εn ,a (h)} − E{ sup Z(h)}|,
h∈Rd
h∈Rd

|E{ sup Z −εn ,a (h)} − E{ sup Z(h)}| .
εn

∆n +

εn

h∈Rd

(25)

h∈Rd

√
The second term in (25) is O( Sεn ) by Lemma 6.1. The first term in (25) represents
the approximation error of the expected supremum √
of Gaussian processes, whose order
will√be studied in the next section. If we take εn = ∆n , the right-hand side of (25) is
O( S∆n ). This suggests that the asymptotic normality (3) holds as long as S = o(∆−1
n ).
Intuitively, this implies that the number of slices S cannot diverge too fast, otherwise the
bias will accumulate.

6.3

Bound for the approximation error ∆n

To establish an upper bound for ∆n , we adopt the techniques in Chernozhukov et al. (2013)
and Chernozhukov et al. (2014). Specifically, they established the nonasymptotic bound
for the following difference (see P.1590 in Chernozhukov et al., 2014 or Theorem 2.1 in
Chernozhukov et al, 2013):
p

p

j=1

j=1

E{g(max Sn,j )} − E{g(max Tn,j )} ,
20

P
where g is a smooth function with third order derivatives, Sn,jP= ni=1 Xi,j for some mean
zero random vectors Xi = (Xi,1 , · · · , Xi,p )T ∈ Rp , and Tn,j = ni=1 Yi,j for some mean zero
Gaussian vectors Yi = (Yi,1 , · · · , Yi,p )T ∈ Rp with the same covariance matrix as Xi .
Here, we improve the result in two ways. First, it’s not necessary to assume Xi and Yi
to be mean zero. The same conclusion holds as long as EXi = EYi = µi for any µi < ∞.
Second, we improve the result by taking g to be the identity function as needed in our
application. We summarize our result in the following lemma.
Lemma 6.3 Let X1 , · · · , Xn be independent random vectors in Rp with finite
Pn fourth abT
solute moments.
P Define E(Xi ) = µi = (µi1 , · · · , µip ) , Z = max1≤j≤p i=1 Xij and
Z̃ = max1≤j≤p Yij , where Yi = (Yi,1 , · · · , Yi,p)T is distributed as N{µi , E(Xi XiT )}. Then,
we have for any β > 0,
|EZ − EZ̃| ≤ 2β −1 log p + Cβ{B1 + β(B2 + B3 B4 ) + β 2 (B5 + B6 )},
where C is a constant independent of µ1 , · · · , µn ,
(
)
n
X
X̃ij X̃ik − nE(X̃ij X̃ik )| ,
B1 = E max |
1≤j,k≤p

B2 = E

(

i=1
n
X

max |

1≤j,k,l≤p

B3 = max E
j,k

(

i=1

max |

1≤l≤p

)

X̃ij X̃ik X̃il − nE(X̃ij X̃ik X̃il )| ,

n
X
i=1

)

E(X̃ij X̃ik )X̃il | ,

B4 = E


1
) ,
B5 = nE max |X̃1j | I( max |X̃1j | >
1≤j≤p
1≤j≤p
2β


max

1≤j≤p

n
X
i=1

|X̃ij |4

!

,

4

X̃ij = Xij − µij and X̃i = Xi − µi , j = 1, · · · , p, i = 1, · · · , n.
Lemma 6.4 Under Conditions (A1)-(A7), we have ∆n = O(n−1/6 log4/3 n) for sufficiently
large n.
This completes the proof of Theorem 2.1.
Finally, we would like to point out that our method of analyzing bias is not specific to
cubic-rate M-estimators. In fact, as long as the limiting Gaussian process of a M-estimator
has stationary increments, the bias of the aggregated estimator can be similarly bounded
using our method.

7

Discussion

In this paper, we provide a unified inference framework for aggregated M-estimators with
cubic rates obtained by the divide and conquer method. Our results demonstrate that the
21

aggregated estimators have faster convergence rate than the original M-estimators based on
pooled data and achieve the asymptotic normality when the number of groups S does not
grow too fast with respect to n, the sample size of each group. It remains an open question
whether the rate S = o(n1/6 / log4/3 n) is optimal in general, but the rate can be improved
for some special cases. For example, consider the location estimator described in Section
3. Using the KMT approximation (Komlós et al., 1975) for a stochastic process indexed
by one-dimensional parameter, it can be shown that the difference between the expected
(j)
supremum of Pn (mh ) and the corresponding limiting Gaussian process is O(n−1/3 log n).
However, our theorem states that this difference is of the order O(n−1/6 log4/3 n) in a general
setting. In addition, we have not discussed on how to choose S in practice. One possible
way is to treat S as a tuning parameter and use some cross-validation criteria to determine
S. This is an interesting topic that needs further investigation.

References
Adamczak, R. (2008). A tail inequality for suprema of unbounded empirical processes with
applications to Markov chains. Electron. J. Probab. 13, no. 34, 1000–1034.
Athreya, K. B. and S. N. Lahiri (2006). Measure theory and probability theory. Springer
Texts in Statistics. Springer, New York.
Cator, E. and P. Groeneboom (2006). Second class particles and cube root asymptotics for
Hammersley’s process. Ann. Probab. 34 (4), 1273–1295.
Chen, X. and M.-g. Xie (2014). A split-and-conquer approach for analysis of extraordinarily
large data. Statist. Sinica 24 (4), 1655–1684.
Chernoff, H. (1964). Estimation of the mode. Ann. Inst. Statist. Math. 16, 31–41.
Chernozhukov, V., D. Chetverikov, and K. Kato (2013). Gaussian approximations and
multiplier bootstrap for maxima of sums of high-dimensional random vectors. Ann.
Statist. 41 (6), 2786–2819.
Chernozhukov, V., D. Chetverikov, and K. Kato (2014). Gaussian approximation of
suprema of empirical processes. Ann. Statist. 42 (4), 1564–1597.
Chernozhukov, V., D. Chetverikov, and K. Kato (2015). Comparison and anti-concentration
bounds for maxima of Gaussian random vectors. Probab. Theory Related Fields 162 (1-2),
47–70.
Daniels, H. E. and T. H. R. Skyrme (1985). The maximum of a random walk whose mean
path has a maximum. Adv. in Appl. Probab. 17 (1), 85–99.
Geyer, C. J. (1994). On the asymptotics of constrained M-estimation. Ann. Statist. 22 (4),
1993–2010.
22

Groeneboom, P. (1989). Brownian motion with a parabolic drift and Airy functions. Probab.
Theory Related Fields 81 (1), 79–109.
Groeneboom, P., G. Hooghiemstra, and H. P. Lopuhaä (1999). Asymptotic normality of
the L1 error of the Grenander estimator. Ann. Statist. 27 (4), 1316–1347.
Kim, J. and D. Pollard (1990). Cube root asymptotics. Ann. Statist. 18 (1), 191–219.
Kleiner, A., A. Talwalkar, P. Sarkar, and M. I. Jordan (2014). A scalable bootstrap for
massive data. J. R. Stat. Soc. Ser. B. Stat. Methodol. 76 (4), 795–816.
Koltchinskii, V. I. (1994). Komlos-Major-Tusnady approximation for the general empirical
process and Haar expansions of classes of functions. J. Theoret. Probab. 7 (1), 73–118.
Komlós, J., P. Major, and G. Tusnády (1975). An approximation of partial sums of independent RV’s and the sample DF. I. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 32,
111–131.
Kosorok, M. R. (2008). Introduction to empirical processes and semiparametric inference.
Springer Series in Statistics. Springer, New York.
Marcus, M. B. and J. Rosen (2006). Markov processes, Gaussian processes, and local times,
Volume 100 of Cambridge Studies in Advanced Mathematics. Cambridge University Press,
Cambridge.
Pimentel, L. P. R. (2014). On the location of the maximum of a continuous stochastic
process. J. Appl. Probab. 51 (1), 152–161.
Rio, E. (1994). Local invariance principles and their application to density estimation.
Probab. Theory Related Fields 98 (1), 21–45.
Splawa-Neyman, J. (1990). On the application of probability theory to agricultural experiments. Essay on principles. Section 9. Statist. Sci. 5 (4), 465–472.
van der Vaart, A. W. and J. A. Wellner (1996). Weak convergence and empirical processes.
Springer Series in Statistics. Springer-Verlag, New York. With applications to statistics.
Zhang, B., A. A. Tsiatis, E. B. Laber, and M. Davidian (2012). A robust method for
estimating optimal treatment regimes. Biometrics 68 (4), 1010–1018.
Zhang, Y., J. Duchi, and M. Wainwright (2013). Divide and conquer kernel ridge regression.
In Conference on Learning Theory, pp. 592–617.
Zhao, T., G. Cheng, and H. Liu (2016). A partially linear framework for massive heterogeneous data. Ann. Statist. To apper.
Zhou, S. (2009). Restricted eigenvalue conditions on subgaussian random matrices. arXiv:
0912.4045 .
23

A

Proofs for major results

For notational and conceptual simplicity of the proof, without loss of generality, we avoid
discussing of the measurability issue, by assuming that the parameter space Θ is countable,
and that Θδ = Nδ ∩ Θ is dense in Nδ . Consider the location estimator, for example, we can
take Θ = Q where Q denotes the set of rationals. Under this assumption, the condition
θ0 ∈ Θ seems somewhat strong. Therefore, we assume θ0 ∈ Θ̄ instead, where Θ̄ denotes
the closure of Θ, and impose an additional assumption:
(j)
(j)
(A8.) Pr(supθ∈Θ Pn m(·, θ) ≥ Pn m(·, θ0 )) = 1 for all j = 1, . . . , S.
Take the location estimator as an example. Let Θ = Q, observe that
(j)
sup P(j)
n [θ − 1, θ + 1] ≤ Pn [θ0 − 1, θ0 + 1],
θ∈Q

(j)

(j)

only when some Xi = θ0 ± 1. However, this happens with probability 0, since Xi has
a density function. Assumption (A8) therefore holds. We can similarly verify (A8) for the
maximum score and value search estimator. For simplicity, in the proofs below, we assume
θ0 ∈ Θ and hence (A8) is not needed.
Define the empirical process
Vn(j) (θ) = G(j)
n {m(·, θ) − m(·, θ0 )}.
To prove Theorem 5.1, we need the following two Lemmas.
Lemma A.1 Under Conditions (A4) and (A5), we have
√
E{||Vn(j) (θ)||Θ } ≤ c1 vω,
for some constant c1 .
Lemma A.2 Under Conditions (A4), (A5) and (A6), there exists some constant c3 > 0,
such that
√
E{||Vn(j) (θ)||Θ∩Sk,n } ≤ c3 n−1/6 k.
Definitions of ω and v are given in (A3) and (A5), respectively. We define k and Sk,n
in the proof of Theorem 5.1. The proofs of Lemmas 1 and 2 are given in Appendix B.

A.1

Proof for Theorem 5.1

√
√ (j)
(j)
We first prove (16). Since Vn (θ) + nE{m(·, θ) − m(·, θ0 )} = nPn {m(·, θ) − m(·, θ0 )},
under the event θ̂(j) ∈
/ Nδ , we have




√
√
sup Vn(j) (θ) + nE{m(·, θ) − m(·, θ0 )} ≥ sup Vn(j) (θ) + nE{m(·, θ) − m(·, θ0 )} .(26)
θ∈Θ∩Nδc

θ∈Θ

24

Since θ0 ∈ Θ, we have



√
sup Vn(j) (θ) + nE{m(·, θ) − m(·, θ0 )} ≥ 0.

(27)

θ∈Θ

Combining (26) and (27) together, we have
Pr(θ̂(j) ∈
/ Nδ ) ≤ Pr
≤ Pr

sup

θ∈Θ∩Nδc

sup Vn(j) (θ) ≥

θ∈Θ∩Nδc

inf



θ∈Θ∩Nδc

Vn(j) (θ) +

√

√



nE{m(·, θ) − m(·, θ0 )} ≥ 0

nE{m(·, θ0 ) − m(·, θ)}

!

= Pr

!

(28)

sup Vn(j) (θ) ≥

θ∈Θ∩Nδc

√

!

nη ,

where η = E{m(·, θ0 )} − supθ∈N
/ δ E{m(·, θ)} is positive under Condition (A1).
Under Condition (A4), we have ω ≡ ||M(·)||ψ1 < ∞. It follows from Lemma C.5 that
for all t ≥ 0,

 √ 



nt
t2
3
(j)
(j)
,
(29)
Pr ||Vn (θ)||Θ ≥ E||Vn (θ)||Θ + t ≤ exp − 2 + 3 exp −
2
3σ
c0 ω
for some constant c0 > 0, and
σ 2 = ||E{m(·, θ) − m(·, θ0 )}2 ||Θ ≤ 4E{M 2 (·)} ≤ 8ω 2.

(30)

The last inequality in (30) follows by Lemma C.3. By Lemma A.1, we have, for sufficiently
√
√
√
(j)
(j)
large n, E{||Vn (θ)||Θ } ≤ nη/3. Taking t0 = nη/2, the event supθ∈Θ∩Nδc Vn (θ) ≥ nη
is contained in the event
3
||Vn(j) (θ)||Θ ≥ E{||Vn(j) (θ)||Θ } + t0 .
2
Hence, it follows by (28), (29) and (30) that




nη 2
nη
(j)
Pr(θ̂ ∈
/ Nδ ) ≤ exp −
≤ 4 exp(−C0 n),
+ 3 exp −
96ω 2
2c0 ω
where C0 = min(η 2 /96ω 2, η/2c0ω).
It remains to show (17). For any positive integer k ≤ n−1/3 δ, let Sk,n denote the shell
{θ : (k −1) < n−1/3 ||θ −θ0 ||2 ≤ k}. Let K be the smallest integer such that K ≤ n−1/3 δ + 1.
For any integer J > 0, the event {||θ̂(j) −θ0 ||2 > Jn1/3 } conditional on θ̂(j) ∈ Nδ is contained
in the event {θ̂(j) ∈ ∪J<k≤K Sk,n }. Similar to (26), (27) and (28), we have
X
Pr(θ̂(j) ∈ Sk,n )
(31)
Pr(||θ̂(j) − θ0 ||2 ≥ n−1/3 J|θ̂(j) ∈ Nδ ) ≤
J<k≤K

≤

X

J<k≤K

Pr

sup
θ∈Θ∩Sk,n

Vn(j) (θ) ≥

inf

θ∈Θ∩Sk,n

25

√

nE{m(·, θ0 ) − m(·, θ)}

!

By the second order Taylor expansion, we have
1
E{m(·, θ0 )} − E{m(·, θ)} = (θ0 − θ)T V (θ⋆ )(θ0 − θ),
2

(32)

for some θ⋆ joining the line segment between θ0 and θ. Under Condition (A1), we have for
any θ⋆ ∈ Nδ , λmin{V (θ⋆ )} > 0. Since E{m(·, θ)} is twice continuously differentiable, this
suggests c2 ≡ inf θ⋆ ∈Nδ λmin {V (θ⋆ )} > 0. Note that θ ∈ Nδ implies θ⋆ ∈ Nδ . Together with
(32), we have
√
√
nc2
c2 (k − 1)2
inf
||θ0 − θ||22 ≥
.
nE{m(·, θ0 ) − m(·, θ)} ≥ inf
θ∈Θ∩Sk,n
θ∈Sk,n
2
2n1/6
Combining this with (31), we obtain
Pr(n1/3 ||θ̂(j) − θ0 ||2 ≥ J|θ̂(j)

X

c2 (k − 1)2
Pr
sup Vn(j) (θ) ≥
∈ Nδ ) ≤
2n1/6
θ∈Θ∩Sk,n
J<k≤K

!

.

(33)

To bound the right-hand side of (33), we apply the same strategy. We first provide an
(j)
upper bound for E{||Vn (θ)||Θ∩Sk,n }, and then apply the concentration inequality for the
(j)
empirical process ||Vn (θ)||Θ∩Sk,n . Let N0 denote the smallest integer greater than 1 such
√
√
that c2 (N0 − 1)2 ≥ 8c3 N0 . For any k ≥ N0 , we have c2 (k − 1)2 ≥ 8c3 k. By Lemma A.2,
we have
c2 (k − 1)2
c2 k 2
c2 (k − 1)2
(j)
(j)
≥
2E||V
(θ)||
+
≥
2E||V
(θ)||
+
.
Θ∩S
Θ∩S
n
n
k,n
k,n
2n1/6
4n1/6
16n1/6
Therefore, for all integer k ≥ N0 , we have
Pr

sup
θ∈Θ∩Sk,n

≤ Pr

sup
θ∈Θ∩Sk,n

Vn(j) (θ) ≥

c2 (k − 1)
2n1/6

2

!

|Vn(j) (θ)| − 2E||Vn(j) (θ)||Θ∩Sk,n ≥

2

c2 k
16n1/6

!

.

By Lemma C.5, the probability on the right-hand side of the inequality is bounded above
by
!


c4 k 4
c5 n1/3 k 2
exp − 1/3 2
,
(34)
+ 3 exp −
n σn,k
ω
2
2
where c4 and c5 are some constants, and σn,k
= ||E{m(·, θ) −m(·, θ0 )}2 ||Θ∩Sn,k . Since σn,k
≤
−1/3
c6 n
k for some constant c6 > 0 by Condition (A2), setting C1 = min[c4 /c6 , c5 /{ω(1+δ)}],
the right-hand side of (34) is bounded above by

exp(−C1 k 3 ) + 3 exp(−C1 n1/3 k 2 (1 + δ)) ≤ 4 exp(−C1 k 3 ),
26

since n−1/3 k ≤ (δ + 1). Thus, the right-hand side of (33) is bounded above by
X
X
exp(−C1 (J + 1)2 k)
4 exp(−C1 k 3 ) ≤ 4
k>J

k>J


4 exp(−C1 (J + 1) )
3
≤
C
exp
−C
(J
+
1)
,
2
1
1 − exp(−C1 (J + 1)2 )
3

≤

where C2 = 4/{1 − exp(−C1 )}.
From the above discussions, we have for any x ≥ N0 ,

Pr(n1/3 ||θ̂(j) − θ0 ||2 ≥ x|θ̂(j) ∈ Nδ ) ≤ Pr(n1/3 ||θ̂(j) − θ0 ||2 ≥ [x]|θ̂(j) ∈ Nδ )
≤ C2 exp{−C1 ([x] + 1)} ≤ C2 exp(−C1 x),
where [x] denotes the biggest integer that is smaller or equal to x. This completes the
proof.

A.2

Proof for Lemma 6.1

Note that
1
E{ sup X ε,a (h)} = E sup {B(h) + εaT h − hT W h}
2
h∈Rd
h∈Rd


1
1
−1 T
−1
= E sup {B(h) − (h − εW a) W (h − εW a)} + ε2 aT W −1 a
2
4
h∈Rd
1
1
= E[ sup {B(h + εW −1 a) − hT W h}] + ε2 aT W −1a.
2
4
h∈Rd

(35)

By Condition (A7), the process B̃(h) ≡ B(h + εW −1 a) − B(εW −1a) has the same
distribution as B(h). Therefore, (35) is equal to
1
1
E[ sup {B̃(h) − hT W h}] + E{B(εW −1a)} + ε2 aT W −1 a
2
4
h∈Rd
1
1
1
= E[ sup {B(h) − hT W h}] + ε2 aT W −1 a = E{ sup X(h)} + ε2 aT W −1 a.
2
4
4
h∈Rd
h∈Rd
The result therefore follows by the positive definiteness of W .

A.3

Proof for Lemma 6.4

To prove Lemma 6.4, we need the following Lemma. The definitions of B1 , · · · , B6 are
given latter. The proof of Lemma A.3 is given in Appendix B.

27

Lemma A.3 Assume β = O(nt ) for some 0 < t < 1/3. Then, for sufficiently large n,
p
B1 = O(n−1/3 log7/6 n log N) + O(n−5/12 log3/4 N),
p
B2 = O(n−2/3 log13/6 n log N ) + O(n−3/4 log3/4 N),
p
B3 = O(n−1/6 log N ), B4 = O(n−1/3 log1/3 n),
p
B5 = O(n−5/6 log N ) + O(n−2/3 log7/3 n), B6 = O(1/n).

Proof : We take an ǫ-net {h1 , . . . , hN } of the metric space (Hδn , ||·||2) with N = N(ǫ, Hδn , ||·
||2 ). For notational simplicity, let ε = εn . We have
∆n ≤ |E{

sup
h∈Hn ∩Hδn

ε,a
Mn,j
(h)} − E{

sup
h∈Hn ∩Hδn

N

N

k=1

k=1

Z ε,a (h)}| + |E{

ε,a
≤ |E{max Mn,j
(hk )} − E{max Z ε,a (hk )}| + E{

+ E{

sup
h1 ,h2 ∈Hn ∩Hδn
||h1 −h2 ||2 ≤ǫ

|Z ε,a(h1 ) − Z ε,a(h2 )|} + |E{

sup
h∈Hn ∩Hδn

sup
h1 ,h2 ∈Hn ∩Hδn
||h1 −h2 ||2 ≤ǫ
ε,a

sup

h∈Hn ∩Hδn

Z

Z ε,a (h)} − E{ sup Z ε,a (h)}|
h∈Rd

ε,a
ε,a
|Mn,j
(h1 ) − Mn,j
(h2 )|}

(h)} − E{ sup Z ε,a (h)}|
h∈Hn

∆

+ |E{ sup Z ε,a (h)} − E{ sup Z ε,a (h)}| = η1 + η2 + η3 + η4 + η5 .
h∈Hn

h∈Rd

It suffices to bound η1 , η2 , η3 , η4 and η5 .
ε,a
Analysis of η1 : We first approximate Mn,j
(h) by a Gaussian process Znε,a(h) with the same
ε,a
ε,a
mean µn (h) and covariance function Ωn (h1 , h2 ) as Mn,j
(h), and give an upper bound for
∆

N

N

k=1

i=1

ε,a
I1 = |E{max Mn,j
(hk )} − E{max Znε,a (hk )}|.

Next, for the Gaussian process Z ε,a (h) with mean µε,a (·) = limn µεn ,a (·) and covariance
function Ω = limn Ωn , we give an upper bound for
∆

N

N

k=1

k=1

I2 = |E{max Znε,a (hk )} − E{max Z ε,a (hk )}|.
By its definition, we have η1 ≤ I1 + I2 .
By Lemma 6.3, we have
I1 ≤ 2β −1 log N + Cβ[B1 + β(B2 + B3 B4 ) + β 2 (B5 + B6 )],

28

(36)

where the constant C is independent of a and ε, and
"
#
n
X
1
(j)
(j)
(j)
(j)
mhk (Xi )mhl (Xi ) − nEmhk (X1 )mhl (X1 )| ,
B1 = 2/3 E max |
1≤k,l≤N
n
i=1
#
"
n
X
1
(j)
(j)
(j)
(j)
(j)
(j)
B2 = E
max |
mhk (Xi )mhl (Xi )mhs (Xi ) − nEmhk (X1 )mhl (X1 )mhs (X1 )| ,
1≤k,l,s≤N
n
i=1
"
#
n
X
1
1
(j)
(j)
(j)
mhk (Xi )| , B4 = 2/3 max |Emhk (X1 )mhl (X1 )|,
B3 = 1/3 E max |
1≤k≤N
1≤l,k≤N
n
n
i=1
"
#


n
X
1
n1/3
1
(j) 4
(j)
(j) 4
B5 = 4/3 E max
) .
|mhk (Xi )| , B6 = 1/3 E max |mhk (X1 )| I(max |mhk (X1 )| >
1≤k≤N
k
k
n
n
2β
i=1
Taking β = O(n1/6 log−1/3 n), it follows by (36) and Lemma A.3 that
I1 = O(n−1/6 log1/3 n(log N + log n)) + O(n−1/4 log3/2 n log3/4 N).

(37)

Next, we bound I2 . A second order Taylor expansion gives
1 T
T
µε,a
n (h) = εa h − h V (θ0 + uh)h,
2

(38)

for some 0 < u < n−1/3 . For all h ∈ Hδn , it follows by Condition (A6) that
|hT V (θ0 + uh)h − hT V h| ≤ ||V (θ0 + uh) − V (θ0 )||2 ||h||22 = O(n−1/3 log n).
This together with (38) implies
sup
|ε|≤1,||a||2 =1

ε,a
−1/3
|µε,a
log n).
n (h) − µ (h)| = O(n

(39)

Consider the Gaussian process Z̃nε,a (h) indexed by h ∈ Rd with mean µε,a (h) and cod
ε,a
variance Ωn (·, ·). Since Z̃nε,a(h) = Znε,a(h) − µε,a
n (h) + µ (h), we have
ε,a
E{max Z̃nε,a(hk )} = E[max{Znε,a (hk ) − µε,a
n (hk ) + µ (hk )}].
k

k

Thus, by (39),
|E{max Z̃nε,a (hk )} − E{max Znε,a (hk )}| = O(n−1/3 log n).
k

k

(40)

Define Ω(h, h̃) = L(h) + L(h̃) − L(h̃ − h). By Condition (A7), we have that for all 1 ≤
j, k ≤ N,
!
log2/3 n
.
(41)
max |Ω(hj , hk ) − Ωn (hj , hk )| = O
j,k
n1/3
29

Note that (Z̃nε,a(h1 ), . . . , Z̃nε,a(hp ))T and (Z ε,a (h1 ), . . . , Z ε,a (hp ))T are Gaussian random
vectors with the same mean µε,a (h) and covariance (Ωn (hj , hk ))jk and (Ω(hj , hk ))jk , respectively. It follows by (41) and Lemma C.8 that for any β̃ > 0,
!
2/3
log
n
|E{max Z̃nε,a (hk )} − E{max Z ε,a(hk )}| ≤ 2β̃ −1 log N + O β̃ 1/3
.
k
k
n
Taking β̃ = n1/6 log1/6 n, we obtain
|E{max Z̃nε,a (hk )} − E{max Z ε,a(hk )}| = O(n−1/6 log−1/6 n log N + n−1/6 log5/6 n).
k

k

For sufficiently large n, this together with (40) implies
I2 = O(n−1/6 log−1/6 n log N + n−1/6 log5/6 n).

(42)

Combining (37) with (42), we have for sufficiently large n,
η1 = O(n−1/6 log1/3 n(log N + log n)) + O(n−1/3 log3/2 n log3/4 N).

(43)

Analysis of η2 : We decompose η2 as
η2 ≤ E{

sup
h1 ,h2 ∈Hn ∩Hδn
||h1 −h2 ||2 ≤ǫ

|M̃n,j (h1 ) − M̃n,j (h2 )|} +

sup
h1 ,h2 ∈Hn ∩Hδn
||h1 −h2 ||2 ≤ǫ

ε,a
|µε,a
n (h1 ) − µn (h2 )|,

ε,a
where M̃n,j (h) is the centered process Mn,j
(h) − µε,a
n (h), and is independent of ε and a. For
any h1 , h2 ∈ Hδn with ||h1 − h2 ||2 ≤ ǫ, a first order Taylor expansion gives
p
p
|E(mh1 ) − E(mh2 )| = n1/6 E{m(·, θ0 + n−1/3 log nh1 ) − m(·, θ0 + n−1/3 log nh2 )}

≤ n−1/6 log1/3 n sup
θ∈Θ

∂Em(·, θ)
∂θ

ǫ.

2

Under Condition (A1), |ε| ≤ 1 and ||a||2 ≤ 1, we have
sup
h1 ,h2 ∈Hδn
||h1 −h2 ||2 ≤ǫ

ε,a
−1/6
|µε,a
log1/3 nǫ) + |εaT (h1 − h2 )| = O(ǫ).
n (h1 ) − µn (h2 )| = O(n

By some standard symmetrization arguments and Condition (A2), we have
(j)

(j)

E[{mh1 (X1 ) − E(mh1 ) − mh2 (X2 ) + E(mh2 )}2 ]
(j)

(j)

(j)

(j)

≤ E[{mh1 (X1 ) − mh1 (X2 ) − mh2 (X2 ) + mh2 (X2 )}]2
≤ 4E{(mh1 − mh2 )2 } ≤ c̄ǫ,
for some constant c̄ > 0. Define the metric
(j)

(j)

d2h (h1 , h2 ) = E[{mh1 (X1 ) − E(mh1 ) − mh2 (X2 ) + E(mh2 )}2 ].
30

(44)

We have
E{

sup
h1 ,h2 ∈Hn ∩Hδn
||h1 −h2 ||2 ≤ǫ

|M̃n,j (h1 ) − M̃n,j (h2 )|} ≤ E{

sup
h1 ,h2 ∈Hn ∩Hδn
√
dh (h1 ,h2 )≤ c̄ǫ

|M̃n,j (h1 ) − M̃n,j (h2 )|}.

(45)

Moreover, by Lemma C.7, it can be shown that the right-hand side of (45) is bounded
above by
p
(46)
O( ǫv log n) + O(vκ1/4 n−1/4 log3/4 n) + O(v ω̃n−3/8 log7/8 n),

where

κ=

sup
h1 ,h2 ∈Hδn

E(mh1 − mh2 − Emh1 + Emh2 )4 ≤ 2||E(mh − Emh )4 ||Hδn ≤ 32||Em4h ||Hδn
(j)

(j)

(j)

≤ 32n2/3 ||4EM 2 (X1 ){m(X1 , θ0 + n−1/3 h) − m(X1 , θ0 )}2 ||Hδn ,

(47)

and ω̃ = ||mh ||ψ1 ≤ 2n1/6 ω. Decomposing the right-hand side of (47) as
128n2/3 sup E[M 2 I(M ≤ ω log n){m(·, θ0 + n−1/3 h) − m(·, θ0 )}2 ]

(48)

h∈Hδn

+ 512n2/3 sup E{M 4 I(M > ω log n)}.

(49)

h∈Hδn

Under Condition (A3), the term (48) can be bounded above by
128n2/3 ω 2 log2 n sup E[m(·, θ0 + n−1/3 h) − m(·, θ0 )]2 = O(ω 2n1/3 log7/3 n),
h∈Hδn

and the term (49) is O(ω 4n−1/3 ) by Lemma C.4. This implies
κ = O(ω 2n1/3 log7/3 n) + O(ω 4n−1/3 ).
Combining this together with (46) gives
E{

sup
h1 ,h2 ∈Hδn
||h1 −h2 ||2 ≤ǫ

p
|M̃n,j (h1 ) − M̃n,j (h2 )|} = O( ǫv log n) + O(n−1/6 log4/3 n).

This together with (44) implies
p
p
η2 = O( ǫv log n) + O(n−1/6 log4/3 n) + O(n−1/6 log nǫ).

(50)

Analysis of η3 : Note that G(h) = Z ε,a (h) − µε,a (h) with µε,a(h) = εaT h − 21 hT V h. Similar
to η2 , we have
η3 ≤ E{ sup |G(h1 ) − G(h2 )|} +
h1 ,h2 ∈Hǫ

31

sup |µε,a(h1 ) − µε,a(h2 )|.

h1 ,h2 ∈Hǫ

For sufficiently large n, we can show
sup

sup

|ε|≤1,||a||2≤1 ||h1 −h2 ||2 ≤ǫ

|µε,a(h1 ) − µε,a (h2 )| = O(ǫ).

In addition, we have
E[{G(h1 ) − G(h2 )}2 ] = L(h1 − h2 ) ≤ ||h1 − h2 ||2

sup

L(α),

α∈Rd ,||α||2 =1

where the last inequality follows by the rescaling property of L in Condition (A7). Define
C̄ = supα∈Rd ,||α||2=1 L(α). As L(·) is continuous, we have C̄ < ∞. This suggests that the
process
G(h) is subgaussian (see Definition C.2) with respect to the metric eh (h1 , h2 ) =
p
C̄||h1 − h2 ||2 . Thus, by Corollary 2.2.8 in van der Vaart and Wellner (1996), we have
∆

I3 = E{

sup

√
eh (h1 ,h2 )≤ C̄ǫ

|G(h1 ) − G(h2 )|} ≤ K

Z

0

√
C̄ǫ

p
log D(t, Hδn , eh )dt,

(51)

where K is a positive constant and D(ε, Hδn , d) stands for the packing number, i.e, the
maximum number of ǫ-separated points in Hδn . By the relation between the packing
number and covering number, we obtain
I3 ≤ K

Z

√
0

C̄ǫ

p

log N(t/2, Hδn , eh )dt.

Let 2T̄ be the diameter of Hδn under || · ||2 norm. For any t > 0, it follows by the
definition of eh that


 2

 2

t
t
t
d
N
, Hδn , eh = N
, Hδn , || · ||2 = N
, B , || · ||2 ,
(52)
2
4C̄
4C̄ T̄ 2
where B2d is the unit L2 ball in Rd . By Lemma C.1, the last covering number in (52) is
smaller than (1 + 4C̄ T̄ /t2 )d . Hence we have

Z √C̄ǫ s 
√
4C̄ T̄
(53)
log 1 + 2 dt.
I3 ≤ dK
t
0
We decompose the right-hand side of (53) as I4 + I5 , where

Z √C̄ǫ s 
q
√
4C̄ T̄
dK
log 1 + 2 I(t ≤ C̄ T̄ /n)dt,
I4 =
t
0
s
√


Z C̄ǫ
q
√
4C̄ T̄
dK
log 1 + 2 I(t > C̄ T̄ /n)dt.
I5 =
t
0
32

p
Letting t̃ = t C̄ T̄ /n, we have
r
r



Z 1s 
Z 1s
4n
1
4
dC̄ T̄
dC̄ T̄
log 1 + 2 dt̃ = K
log n + log
dt̃
I4 ≤ K
+
n
n
n t̃2
t̃
0
0
!
r
r
r

Z 1s 
dC̄ T̄ log n
dC̄ T̄
dT̄ log n
4
≤ K
,
(54)
+K
log 1 + 2 dt̃ = O
n
n
n
t̃
0

√
√
√
where the first inequality in (54) is due
p to that log a + log b ≤ log a + log b for all
a, b > 0. As for I5 , note that when t > C̄ T̄ /n, log(1 + 4C̄ T̄ /t2 ) ≤ log(1 + 4n) ≤ log(8n),
and therefore for sufficiently large n,
p
p
p
I5 ≤ dC̄ǫK log(8n) = O( dǫ log n).
Combining this with (54), we obtain
!
r
p
dT̄ log n
I3 = O
+ O( dǫ log n),
n
and hence
r

p
p
η3 = O(n−1/6 log nǫ) + O( dǫ log n) + O

dT̄ log n
n

!

.

(55)

Analysis of η4 : Define ĥε,a = arg maxh∈Hn Z ε,a (h). On the set ĥε,a ∈ Hδn , we have
Z ε,a (h) = sup Z ε,a (h),

sup

h∈Hn

h∈Hn ∩Hδn

and hence
E{

sup
h∈Hn ∩Hδn

Z ε,a (h)} − E{ sup Z ε,a (h)} = E
h∈Hn

By Cauchy-Swartz inequality, we have
"
η42 ≤ E {


sup

h∈Hn ∩Hδn

(

sup

h∈Hn ∩Hδn

Z ε,a (h) − sup Z ε,a (h) I(ĥε,a ∈ Hδcn ) .
h∈Hn

#

Z ε,a (h) − sup Z ε,a (h)}2 Pr(ĥε,a ∈ Hδcn )


h∈Hn

≤ E { sup Z ε,a (h)}2 Pr(ĥε,a ∈ Hδcn ),
h∈Hn

)

(56)

where the last inequality is due to 0 ≤ suph∈Hn Z ε,a (h)−suph∈Hn ∩Hδn Z ε,a (h) ≤ suph∈Hn Z ε,a(h).

2
By Lemma 6.2, E[ suph∈Hn Z ε,a (h) ] = O(1). Therefore it suffices to bound Pr(ĥε,a ∈
Hδcn ).
33

∆

Since Z ε,a (0) = 0, the event {ĥε,a ∈ Hδcn } is contained in A = {suph∈Hn ∩Hδc Z ε,a(h) ≥
n
0}. Define






1
2 2
Ak =
sup
G(h) ≥ c̄(k − 1) T̄ − k T̄ ,


2
h∈Hn


(k−1)T̄ <||h||2≤k T̄

where c̄ = λmin (V ). It is immediate to see that




∞

[
ε,a
Z (h) ≥ 0
A⊆
sup


h∈Hn

k=2 
(k−1)T̄ <||h||2≤k T̄




∞
∞
 [

[
1 T
T
Ak ,
h V h − εa h ⊆
G(h) ≥
inf
⊆
sup
h∈Hn


2
h∈Hn

k=2
k=2 
(k−1)T̄ <||h||2≤k T̄
(k−1)T̄ <||h||2 ≤k T̄

since |ε| ≤ 1 and ||a||2 = 1.
√
Let Hk,T̄ denote the shell (k − 1)T̄ < ||h||2 ≤ k T̄ . Note that T̄ = c0 log n for some
constant c0 . For sufficiently large n and k ≥ 2, we have k T̄ ≤ c̄(k − 1)2 T̄ 2 /4. Therefore
!
∞
∞
X
X
1
2 2
Pr
sup G(h) ≥ c̄(k − 1) T̄ .
Pr(Ak ) ≤
Pr(A) ≤
(57)
4
h∈Hn ∩Hk,T̄
k=2
k=2
Under Condition (A7), the covariance function of G has the following rescaling property:
d √
Ω(kh1 , kh2 ) = kΩ(h1 , h2 ) for any k > 0. This suggests G(k·) = kG(·) for k > 0.
Therefore,
)
)
(
(
2 3/2
c̄(k
−
1)
T̄
1
√
, (58)
sup
G(h) ≥
Pr
sup G(h) ≥ c̄(k − 1)2 T̄ 2 ≤ Pr
√
4
4 k
h∈Hn ∩Hk,T̄
h∈Hn / k T̄ ∩B d
2

√
√
where Hn / k T̄ = {h/ k T̄ : h ∈ Hn }. Similar to (51), (52) and (53), we have
!
r
√ Z 1
4
E{ sup G(h)} = O
d
log(1 + 2 )dt = O(1).
t
0
h∈B2d

(59)

Moreover, Condition (A7) suggests
σ 2 = sup E{G(h)2 } = sup L(h) = O(1).
h∈B2d

(60)

h∈B2d

This together with (59) implies for sufficiently large n,
c̄(k − 1)3/2 T̄ 3/2
c̄(k − 1)3/2 T̄ 3/2
σ
σ
c̄(k − 1)2 T̄ 3/2
√
− E{ sup G(h)} − √ ≥
.
− E{ sup G(h)} − √ ≥
6
12
2π
2π
4 k
h∈B2d
h∈B2d
34

By Lemma C.2, the probability on the right-hand side of (58) is thus bounded above
by
"

σ
c̄(k − 1)3/2 T̄ 3/2
√
G(h)
≥
E{
sup
G(h)}
+
+
Pr
sup
√
12
2π
h∈B2d
h∈Hn / k T̄ ∩B2d

#


≪ exp −(k − 1)T̄ 2 /c0 ,

for sufficiently large n. Combining this with (57) implies
X

Pr(A) ≤
exp −(k − 1)T̄ 2 /c0 ≤ 2 exp(−T̄ 2 /c0 ) = 2/n,
k=2

and hence η4 = O(n−1/2 ).
Analysis of η5 : Take H0 to be a countable subset dense in Rd , and 0 ∈ H0 . Observe that


ε,a
ε,a
ε,a
ε,a
η5 = E{ sup Z (h)} − E{ sup Z (h)} = E{ sup Z (h)} − E{ sup Z (h)}
h∈H0
h∈Hn
h∈Rd
h∈Rd


+
E{ sup Z ε,a (h)} − E{ sup Z ε,a(h)} = I6 + I7 ,
h∈H0

h∈Hn

it suffices to provide upper bounds for I6 and I7 . We first claim for any |ε| ≤ 1, ||a||2 ≤ 1,
I6 = 0. Define Hk = {h : ||h||2 ≤ k} for positive integer k. Assume for any k > 0, the
following holds:
E{ sup

Z ε,a (h)} = E{ sup Z ε,a (h)}.

(61)

h∈Hk

h∈H0 ∩Hk

Then, obviously we have for all k > 0,
E{ sup
h∈H0 ∩Hk

Z ε,a (h)} ≥ E{ sup Z ε,a (h)}.

(62)

h∈Hk

Since Z ε,a (0) = 0, we have suph∈H0 ∩Hk Z ε,a (h) ≥ 0, suph∈Hk Z ε,a (h) ≥ 0 for all k. It follows
by the monotone convergence theorem that
lim E{ sup
k

Z ε,a (h)} = E{ sup Z ε,a (h)},

h∈H0 ∩Hk

lim E{ sup Z ε,a(h)} = E{ sup Z ε,a (h)}.
k

h∈H0

h∈Hk

h∈Rd

These together with (62) implies
E{ sup Z ε,a (h)} = lim E{ sup
h∈H0

k

h∈H0 ∩Hk

Z ε,a (h)} ≥ lim E{ sup Z ε,a(h)} = E{ sup Z ε,a (h)}. (63)
k

h∈Hk

h∈Rd

On the other hand, we have
E{ sup Z ε,a(h)} ≤ E{ sup Z ε,a(h)}.
h∈H0

h∈Rd

Assertion I6 = 0 therefore follows by (63) and (64).
35

(64)

p
p
It remains to show (61). Recall that eh (h1 , h2 ) = C̄||h
−
h
||
≥
E[G(h1 ) − G(h2 )]2 .
1
2
2
p
2
For any k > 0, the diameter Tk of Hk under the metric EG (·) is finite. Similar to (59),
fo any k > 0, we can deduce
Z Tk 
Z Tk
1/2
p
log N(Hk , EG2 (·), t)
(log N(Hk , eh , t))1/2 dt < ∞.
(65)
dt <
0

0

By Theorem 6.1.2 in Marcus and Rosen (2006), (65) suggests there exists another version
G′ of G which is uniformly continuous on Hk . Since H0 ∩ Hk is dense in Hk , we obtain




1 T
1 T
′
T
′
T
(66)
G (h) + εa h − h V h = sup G (h) + εa h − h V h ,
sup
2
2
h∈Hk
h∈H0 ∩Hk

and therefore E suph∈Hn0 ∩Hk Z ε,a(h) = E suph∈H̃n ∩Hk Z ε,a (h). This completes the proof of
(61).
It remains to bound I7 . Define Hn1/3 δ = {h : ||h||2 ≤ n1/3 δ}. Since Θδ is dense in Nδ ,
we have Hn1/3 δ ∩ Hn is dense in Hn1/3 δ . Similar to (61), we can show
Z ε,a (h)} = E{

E{ sup
h∈Hn1/3 δ

Z ε,a(h)}.

sup
h∈Hn1/3 δ ∩Hn

Therefore, we have
I7 ≤ E{ sup Z ε,a (h)} − E{
h∈H0

≤ E{ sup Z

ε,a

h∈H0

(h)} − E{

sup
h∈Hn ∩Hn1/3 δ

sup

Z ε,a(h)} = E{ sup Z ε,a (h)} − E{ sup
h∈H0

Z

ε,a

Z ε,a(h)}

h∈Hn1/3 δ

(h)}.

(67)

h∈Hn1/3 δ ∩H0

Using similar arguments for showing η4 = O(n−1/2 ), we have for sufficiently large n,
E{

sup
h∈Hn1/3 δ ∩H0

Z ε,a(h)} ≥ E{ sup Z ε,a (h)} − O(n−1/2 ).

(68)

h∈H0

Combining (67) and (68) together, we obtain I7 ≤ O(n−1/2 ). Therefore, η5 = O(n−1/2 ).
So far, we have shown

η1 + η2 + η3 + η4 + η5 = O(n−1/6 log1/3 n(log n + log N))
p
+O(n−1/3 log3/2 n log3/4 N) + O( ǫv log n) + O(n−1/6 log4/3 n)
!
r
p
p
d
T̄
log
n
+O(n−1/6 log nǫ) + O( dǫ log n) + O
+ O(n−1/2 ).
n
Taking ǫ = 1/n, it follows by Lemma C.1 that the covering number N ≤ (1 + 2n)d ≪ (4n)d .
This implies ∆n = O(n−1/6 log4/3 n). The proof is therefore completed.

36

A.4

Proof for Lemma 6.2

Define Hk−1,k = {h : k − 1 < ||h||2 ≤ k} and Hk = {h : ||h||2 ≤ k}. It follows by Fatou’s
lemma that for any x > 0,




ε,a
ε,a
(69)
Pr sup Z (h) > x ≤ inf lim Pr sup Z (h) > x .
k

h∈Rd

h∈Hk

Note that
sup Z

ε,a

(h) =

Pr



sup Z

ε,a

h∈Hk

sup Z ε,a(h).

j=1 h∈Hj−1,j

h∈Hk

Therefore

k
X

(
)
 X
k
ε,a
Pr
sup Z (h) > x .
(h) > x ≤

Combining (69) and (70) together, it suffices to show
(
)
∞
X
Pr
sup Z ε,a (h) > x < C6 exp(−C7 x2 ) + C8 exp(−C9 x),
j=1

(70)

h∈Hj−1,j

j=1

(71)

h∈Hj−1,j

for some constants C6 , C7 , C8 and C9 > 0.
Define c̄ = λmin(V ). Since |ε| ≤ 1 and ||a||2 = 1, we have
sup Z ε,a (h) ≤

h∈Hj−1,j

1
sup G(h) − c̄(j − 1)2 + j.
2
h∈Hj−1,j

By the rescaling property of G, the left-hand side of (71) is bounded above by
(
)
∞
X
p
1
2
Pr
j sup G(h) − c̄(j − 1) + j > x ,
2
h∈B2d
j=1

(72)

where B2d is the unit L2 ball in Rd . It follows by (59) and (60) that E{suph∈B2d G(h)} = O(1)
√
and σ 2 = suph∈B2d E{G2 (h)} = O(1). Define L = E{suph∈B2d G(h)} + σ/ 2π. There exists
√
some integer J0 ≥ 1 such that for j ≥ J0 , c̄(j − 1)2 ≥ 4j + jL. For all j ≥ J0 and x > 0,
we have
(
)
)
(
p
p
x
1
Pr
j sup G(h) − c̄(j − 1)2 + j > x ≤ Pr sup G(h) − L > j + √
. (73)
2
j
h∈B2d
h∈B2d
Take B0 to be a countable subset dense in B2d . Similar to (66), we can show
!
Pr

sup G(h) = sup G(h)

h∈B2d

h∈B0

37

= 1.

(74)

It follows by Lemma C.2, (73) and (74) that
)
(


∞
∞
X
X
p
p
1
1
2
2
Pr
j sup G(h) − c̄(j − 1) + j > x ≤
j sup G(h) − c̄(j − 1) + j > x
Pr
2
2
d
h∈B0
h∈B
2
j=J0
j=J0
 √
 X

√ 
∞
X
p
( j + x/ j)2
1
x
√ exp −
≤
Pr sup G(h) − L > j + √
≤
2σ 2
j
2π
h∈B0
j=J0
j=J0


 x
X 1
j
√ exp − 2 exp − 2 = C8 exp(−C9 x),
≤
(75)
σ
2σ
2π
j=J
0

√
J0 L.
for some constants C8 , C9 > 0. On the
other
hand,
when
j
≤
J
,
define
K
=
2J
+
2
0
0
0
√
For any x ≥ K0 , we have x − J0 − J0 L ≥ x/2. Hence,
)
(
(
)
p
x
1
j sup G(h) − c̄(j − 1)2 + j > x ≤ Pr sup G(h) − L > √
Pr
,
2
2 J0
h∈B2d
h∈B2d
for j ≤ J0 and x ≥ K0 . Therefore, it follows by Lemma C.2 and (74) that
)
(


J0
X
p
x2
1
J0
2
j sup G(h) − c̄(j − 1) + j > x ≤ √ exp −
.
Pr
2
8J0 σ 2
2π
h∈B2d
j=1

(76)

√
Letting C6 = J0 / 2π and C7 = 1/(8J0σ 2 ), the proof is completed by (75) and (76).

A.5

Proof for Lemma 6.3

P
P
P
Define µ̄ = ni=1 µi /n = (µ̄1 , . . . , P
µ̄p )T , X̃ = i Xi − nµ̄ and Ỹ = i Yi − nµ̄. Moreover,
define function Fβ (x) = β −1 log{ j exp(βxj + β µ̄j )} : Rp → R, which approximate the
maximum by a smooth function. The approximation error can be bounded by


max |Z − Fβ (X̃)|, |Z̃ − Fβ (Ỹ )| ≤ β −1 log p.
This implies

h
n
oi
|EZ − EZ̃| ≤ E max |Z − Fβ (X̃)|, |Z̃ − Fβ (Ỹ )| + |E{Fβ (X̃)} − E{Fβ (Ỹ )}|
≤ 2β −1 log p + |E{Fβ (X̃)} − E{Fβ (Ỹ )}|.

Hence it suffices to provide an upper bound for |E{Fβ (X̃)} − E{Fβ (Ỹ )}|. Here, we adopt
Stein’s method. For i = 1, . . . , n, let X̃i′ = (X̃i1 , . . . , X̃ip )T be an independent copy of
X̃i ≡ Xi − µi , i = 1, · · · , n. In addition, let I be a uniform random variable on {1, . . . , n},
independent of all other variables. Let X̃ ′ = X̃ − X̃I + X̃I′ and
Z 1
√
√
1
E{Fβ ( tx + 1 − tỸ ) − Fβ (Ỹ )}dt.
h(x) =
0 2t
38

Note that h has derivatives of all orders. Using similar arguments in proof of Lemma 4.2
in Chernozhukov et al. (2014), we can show
|E{Fβ (X̃)} − E{Fβ (Ỹ )}| ≤ C0 βB1 + nE(R),
for some constant C0 > 0, and
R = h(X̃ ′ ) − h(X̃) −

X
j

(X̃ ′ − X̃)T ∆h(X̃) −

1X ′
(X̃ − X̃)T Hessh(X̃)(X̃ ′ − X̃),
2 j,k

where ∆h denotes the gradient of h and Hessh denotes the Hessian matrix. It remains to
bound E(R). By a fourth-order Taylor expansion, we obtain
( n
)
p
1X X
|E(R)| ≤ E
∆ij ∆ik ∆il ∂j ∂k ∂l h(X̃)
6 i=1
j,k,l=1
( n
)
p
1X X
∆ 1
+ E
∆ij ∆ik ∆il ∆im (1 − U)3 ∂j ∂k ∂l ∂m h(X̃ + U∆i ) = (ζ1 + ζ2 ),
6 i=1
6
j,k,l,m=1

where ∆i = (∆i1 , . . . , ∆ip )T = X̃i′ − X̃i , U ∼ U(0, 1) independent of all other variables and
∂j denotes the partial derivative with respect to xj .
Next, we show the following results:
p
X

|∂j ∂k Fβ (x)| ≤ 2β,

(77)

|∂j ∂k ∂l Fβ (x)| ≤ 6β 2 ,

(78)

j,k=1
p

X

j,k,l=1
p

X

j,k,l,m=1

|∂j ∂k ∂l ∂m Fβ (x)| ≤ 26β 3.

(79)

Moreover, let Ujklm (x) = sup{|∂j ∂k ∂l ∂m Fβ (x + y)| : y ∈ Rp , |yj | ≤ β −1 , 1 ≤ ∀j ≤ p}. Then
there exists some constant C0 > 0 such that
p
X

j,k,l,m=1

|Ujklm(x)| ≤ C0 β 3 .

(80)

The proof is similar to that of Lemma 4.3 in Chernozhukov et al. (2014). We only show
(79) and (80) here. Define πj (x) = exp{β(xj +µj )}/[1+exp{β(xj +µj )}]. We can represent
∂j ∂k ∂l ∂m Fβ (x) = β 3 qjklm(x), where
qjklm(x) = πj δjk δjl δjm − πj πm δjk δjl − πj πl δjk (δjm + δlm ) − πj πk (δjl + δkl )(δjm + δkm )
+ 2πj πk πm (δjl + δkl ) + 2πj πm πl δjk + 2πj πk πl (δlm + δjm + δkm ) − 6πj πk πm πl .
39

P
P
Note that πj (x) ≥ 0 and j πj (x) = 1. A direct calculation shows j,k,l,m |qjklm (x)| ≤ 26.
This implies (79). For any y with |yj | ≤ β −1 , 1 ≤ j ≤ p, we have πj (x + y) ≤ e2 πj (x),
which proves (80).
In addition, we have
′
′
E{(X̃ij′ − X̃ij )(X̃ik
− X̃ik )(X̃il′ − X̃il )|X̃ n } = E(X̃ij′ X̃ik
X̃il′ ) − X̃ij X̃ik X̃il

′
′
− E(X̃ij′ X̃ik
)X̃il − E(X̃ij′ X̃il′ )X̃ik − E(X̃ik
X̃il′ )X̃ij = Wjkl − X̃ij X̃ik X̃il

− Φjk X̃il − Φjl X̃ik − Φkl X̃ij ,

(81)

where Wjkl = E(X̃ij X̃ik X̃il ) and Φjk = E(X̃ij X̃ik ). It follows by (81) that ζ1 is bounded by
)#
" (
XX
∆ij ∆ik ∆il ∂j ∂k ∂l h(X̃)|X̃ n
ζ1 = E E
i

≤

E{

XX
j,k,l

i

j,k,l

(X̃ij X̃ik X̃il − Wjkl )∂j ∂k ∂l h(X̃)} + 3 E{

XX
j,k,l

.
Φjk X̃il ∂j ∂k ∂l h(X̃)} (82)

i

By (78), the first term in (82) is bounded by
)
(
X
X
∂j ∂k ∂l h(X̃) ≤ 6β 2 B2 .
E max
(X̃ij X̃ik X̃il − Wjkl )

(83)

Similarly, we can bound the second term in (82) by
)
(
n
X
X
max E max
∂j ∂k ∂l h(X̃) ≤ 6β 2 B3 .
Φjk X̃il

(84)

j,k,l

i

j,k

j,k,l

l

i=1

j,k,l

Combining (83) and (84) together, we obtain
ζ1 ≤ 6β 2 B2 + 18β 2B3 .

(85)

Define χi = I(max1≤j≤p |∆ij | ≤ β −1 ) and χci = 1 − χi . Decompose ζ2 as
)
( n
p
X X
∆ij ∆ik ∆il ∆im (1 − U)3 ∂j ∂k ∂l ∂m h(X̃ + U∆i )χi
E
i=1 j,k,l,m=1

+ E

( n
p
X X

i=1 j,k,l,m=1

∆ij ∆ik ∆il ∆im (1 − U)3 ∂j ∂k ∂l ∂m h(X̃ + U∆i )χci

)

(86)
.

(87)

It follows by the definition of χi and (80) that (86) is smaller than
(
)
X
X
E
max(χi |∂j ∂k ∂l ∂m h(X̃ + U∆i )|) max
|∆ij ∆ik ∆il ∆im |
j,k,l

≤ 26β 3E

i

max

j,k,l,m

j,k,l,m

X
i

|∆ij ∆ik ∆il ∆im |

!

i

≤ 26β 3 E max
j

40

X
i

|∆4ij |

!

≤ 316β 3 E max
j

X
i

!

|X̃ij4 | .

By (79), we can show that (87) is bounded by
(
)
X
X
c
E max |∆ij ∆ik ∆il ∆im χi |
|∂j ∂k ∂l ∂m h(X̃ + U∆i )|
j,k,l,m

i

≤ 26β

3

nE(χc1

j,k,l,m

max ∆41j )
j

3

≤ 316β nE(χc1 max |X̃ij4 |) ≤ 316β 3 nB5 ,
j

where the last inequality follows by Chebyshev’s association inequalities (see Lemma 4.4,
Chernozhukov et al., 2014). This implies ζ2 ≤ 316β 3(B4 + B5 ). Together with (85), the
proof is completed.

B
B.1

Proofs for Lemmas in Section A
Proof for Lemma A.1

Consider the set of functions {m(·, θ) − m(·, θ0 ) : θ ∈ Rd }. Under Condition (A4) and (A5),
an application of Lemma C.6 suggests
q
(j)
(j)
E||Vn (θ)||Θ ≤ c̄ EM 2 (Xi ),
(j)

2
for some constant
√ c̄ > 0. On the other hand, it follows by Lemma C.3 that EM (Xi ) ≤
2
2ω . Take c1 = 2c̄, the assertion therefore follows.

B.2

Proof for Lemma A.2

Consider the set of functions Mk = {m(·, θ) − m(·, θ0 ) : θ ∈ Θ0 ∩ Sk,n }. By Assumption
(A4), the envelope function of Mk is bounded by Mkn−1/3 . Hence, it follows by Lemma C.6
and Assumptions (A4), (A5) and (A6) that
√
E||Vn(j) (θ)||Θ∩Sn,k ≤ c3 kn−1/3 ,
for some constant c3 > 0. This completes the proof.

B.3

Proof for Lemma A.3

We omit the superscript (j) on Xi for notational convenience. Using symmetrization lemma
(see Lemma 2.3.1 in van der Vaart and Wellner, 1996), we obtain
#
"
n
X
−2/3
mhk (Xi )mhl (Xi )εi | ,
(88)
B1 ≤ n
E max |
1≤k,l≤N

i=1

41

where εi are i.i.d Rademacher random variables. Note that for any random variable Y , we
have E|Y | ≤ ||Y ||ψ1 ≤ ||Y ||ψ2 / log 2, the right-hand side of (88) is majorized by
−2/3

n

−1

(log 2) E|| max |

≤ n−2/3 (log 2)−1

1≤k,l≤N

n
X
i=1

mhk (Xi )mhl (Xi )εi |||ψ2|X

(89)

X
p
2 log N max E||
mhk (Xi )mhl (Xi )εi ||ψ2 |X
k,l

i

p
≤ n−2/3 (log 2)−1 12 log NE max
k,l

sX

m2hk (Xi )m2hl (Xi ),

i

where the Orlicz norms || · ||ψ2 |X are taken over ε1 , . . . , εn with X1 , . . . , Xn fixed, the last
inequality is due to Lemma 2.2.10 in van der Vaart and Wellner (1996).
Using the same arguments, we can similarly show
E max
k,l

X
i

m2hk (Xi )m2hl (Xi ) − nEm2hk (Xi )m2hl (Xi )

p
≤ (log 2)−1 12 log N E max
k,l

s
X

(90)

m4hk (Xi )m4hl (Xi )

i

s
X
p
p
−1
12 log N E
≤ (log 2)
M 8 (Xi ) = O( n log N),
i

where the last inequality follows by Lemma C.3. On the other hand, for any k, l, it follows
by Assumption (A4) that
Em2hk (Xi )m2hl (Xi ) ≤ EM 2 (Xi )m2hl (Xi )
(91)
2
2
2
2
≤ EM (Xi )mhl (Xi )I(|M(Xi )| > 2ω log n) + EM (Xi )mhl (Xi )I(|M(Xi )| ≤ 2ω log n)
1
≤ EM 4 (Xi )I(|M(Xi )| > 2ω log n) + 4ω 2 log2 nEm2hl (Xi ) = O( ) + O(δn log2 n),
n
where the last inequality follows by Lemma C.4 and Assumption (A3). This together with
(90) implies
X
p
E max
m2hk (Xi )m2hl (Xi ) = O( n log N) + O(n2/3 log7/3 n).
(92)
k,l

i

Combining this (92) with (88) and (89) gives
p
B1 = O(n−1/3 log7/6 n log N) + O(n−5/12 log3/4 N).
√
Similarly, we can show B2 = O(n−2/3 log13/6 n log N ) + O(n−3/4 log3/4 N).

42

As for B3 , similar to (89), we can deduce
−1/3

B3 ≤ n

(log 2)

−1

p

12 log N E max
k

sX

m2hk (Xi )

i

s
X
p
p
−1/3
−1
≤ n
(log 2)
12 log N E
M 2 (Xi ) = O(n−1/6 log N ).
i

Under Assumption (A3), an application of Cauchy-Swartz inequality gives
q
B4 ≤ Em2hk (Xi )Em2hl (Xi ) = O(δn ) = O(n−1/3 log1/3 n).

√
Using similar arguments in (90) and (91), we have B5 = O(n−5/6 log N)+O(n−2/3 log7/3 n).
Under Assumption (A4), B6 is bounded above by
B6 ≤ n−1/3 EM 4 (Xi )I(|M(Xi )| >

n1/3
).
2β

(93)

If β = O(nt ) for some 0 < t < 1/3, for sufficiently large n, we have n1/3 /(2β) ≫ 2ω log n,
and we can deduce the right-hand side of (93) is O(1/n) by Lemma C.4. Therefore B6 =
O(1/n).

C

Technical lemmas and definitions

Definition C.1 For any random variable Y , define the Orlicz norm ||Y ||ψp as


 p
|Y |
∆
≤2 .
||Y ||ψp = inf E exp
C>0
Cp
Definition C.2 A stochastic process Xt is called sub-Gaussian with respect to the semimetric if for any s, t ∈ T , and x > 0, we have


x2
.
Pr(|Xs − Xt | > x) ≤ 2 exp − 2
2d (s, t)
Lemma C.1 Given d ≥ 1, and ε > 0, we have
N(ε, B2d , ||


d
2
· ||2 ) ≤ 1 +
,
ε

where B2d is the unit ball in Rd , and || · ||2 the Euclidean metric.
Proof: See Lemma B.3 in Zhou (2009).
43

Lemma C.2 Let {Xt : t ∈ T } be a real-valued mean-zero Gaussian process. Assume T is
a countable set and σ = supz∈T (EXz2 )1/2 < ∞. Then for any t > 0, we have


exp(−t2 /2)
σ
√
.
(94)
Pr sup Xz > E sup Xz + √ + σt ≤
2π
2πt
z∈T
z∈T
Proof: Theorem 5.4.3 and Corollary 5.4.5 in Marcus and Rosen (2006) implies LHS of
(94) is bounded by 1 − Φ(t) where Φ stands for the normal cdf. The assertion follows by
noting that
 2
Z ∞
exp(−t2 /2)
1
x
x
√
≤
1 − Φ(t) ≤ √
exp −
.
2
2π t t
2πt
Lemma C.3 For any random variable X, if ||X||ψ1 < ∞, for any integer p ≥ 2, we have
E|X|p ≤ p!||X||pψ1 .

Proof: Denote ω = ||X||ψ1 , it follows by Taylor expansion that


E|X|p
|X|
≥1+
,
2 ≥ E exp
ω
p!
the assertion therefore follows.
Lemma C.4 Assume ||X||ψ1 < ω, then for any integer k ≥ 0, and x > 1, we have
p
E|X|k I(|X| > ωx) ≤ 2 (2k)!ω k exp(−x).
Proof: It follows by Markov’s inequality that
Pr(|X| > ωx) ≤ E

exp(|X|/ω)
≤ 2 exp(−x).
exp(x)

(95)

On the other hand, it follows by Lemma C.3 that
E|X|2k ≤ (2k)!ω 2k .

(96)
p
Using Cauchy-Swartz inequality, we get E|X|k I(|X| > ωx) ≤ E|X|2k Pr(|X| > ωx),
and the assertion follows by (95) and (96).
Lemma C.5 Let X1 , . . . , Xn be i.i.d random variables with values in a measurable space
(S, B), and let F be a countable class of measurable functions f : S → R. Assume Ef (Xi ) =
0 for all f , and ω = || supf ∈F |f (Xi )|||ψ1 < ∞. Then for all 0 < η < 1 and δ > 0, there
exists some constant C = C(η, δ) such that for all t ≥ 0,
!
n
n
X
X
f (Xi )||F + t
f (Xi )| ≥ (1 + η)E||
Pr sup |
f ∈F

 i=1 2

i=1 
t
t
≤ exp −
,
+ 3 exp −
2
2(1 + δ)nσ
Cω

where σ 2 = supf ∈F Ef 2 (Xi ).
44

Proof: See Theorem 4 in Adamczak (2008).
Lemma C.6 Consider the same setup as in Lemma C.5, suppose there exists some constant K and v ≥ 1 such that supQ N(ε||F ||Q,2, F , L2 (Q)) ≤ (K/ε)v , 0 ≤ ∀ε ≤ 1, where
the supremum is taken over all discrete
measure Q such that 0 < QF 2 < ∞, L2 (Q) the
R
2
norm on F defined as ||f ||Q,2 = ( |f | dQ)1/2 , and F the envelope function F = supf ∈F |f |.
Then, there exists some constant C > 0, such that
E sup
f ∈F

n
X
i=1

√
f (Xi ) ≤ C nEF 2 .

Proof: See Theorem 2.14.1 in van der Vaart and Wellner (1996).
Lemma C.7 Consider the same setup as in Lemma C.6. Assume n ≥ 4, then
X
p
1/4
log3/4 n) + O(ωvn1/8 log7/8 n),
E||
f (Xi )||Fǫ = O(ǫ vn log n) + O(vκ1/4
ǫ n
i

where κǫ = ||Ef 4 ||Fǫ , Fǫ = {f1 − f2 : f1 , f2 ∈ F , E|f1 − f2 |2 ≤ ǫ2 }.
Proof: Using symmetrization inequality (see Lemma 2.3.1 in van der Vaart and Wellner,
1996), we have
n

1 X
1 X
f (Xi )||Fǫ ≤ E|| √
E|| √
εi f (Xi )||Fǫ .
n i
n i=1

(97)

Using similar arguments in the proof of Theorem 2.5.2 in van der Vaart and Wellner
(1996), the right-hand side of (97) can be further bounded from above by
Z δn /||F ||n
q
(98)
sup log N(ε||F ||Q,2, F , L2(Q))dε||F ||n,
Ec0
Q

0

for some constant c0 > 0, where
n

δn2

1 X 2
= ||
f (Xi )||Fǫ ,
n i=1

and

||F ||2n

=

n
X

F 2 (Xi ).

i=1

Under the entropy assumption, the right-hand side of (97) is majorized by
Z δn /||F ||n s  
√
K
dε||F ||n.
vE
log
ε
0
We decompose (99) as
Z 1/n s  
Z δn /||F ||n s  
√
√
K
K
∆
vE
log
dε||F ||n + vE
log
dε||F ||n = Eζ1 + Eζ2 .
ε
ε
1/n
0
45

(99)

Consider ζ1 , we have
 
Z 1s
Z 1/n s  
√
1
K
K
dε||F ||2 =
dε′||F ||n ,
ζ1 ≤ v
log
log n + log
′
ε
n
ε
0
0

(100)

where the
by a change of variable ε′ = nε. Note that for any a, b ≥ 0,
√
√last equality
√ follows
we have a + b ≤ a + b and hence the right-hand side of (100) is bounded from above
by
√
Z s  
K
log n
c̄ log n
1 1
log
dε||F ||n ≤
||F ||n +
||F ||n,
n
n 0
ε
n
for some constant c̄, since log n ≥ log 3 ≥ 1. This together with (100) and Cauchy-Swartz
inequality implies


ω log n
c̄ log n p 2
c̄ log n
EF (X1 ) = O
,
(101)
Eζ1 ≤
E||F ||n ≤
n
n
n
since E|F 2| ≤ 2||F ||ψ1 = 2ω 2 by Lemma C.4. Denote a ∨ b = max(a, b), since log(K/ε) is
decreasing as function of ε, ζ2 is majorized by
√
ζ2 ≤ v

Z

(δn /||F ||n )∨(1/n)
1/n

p

log(Kn)dε||F ||n ≤

p
v log(Kn)δn ,

(102)

the last inequality holds since a ∨ b − b ≤ a for a, b > 0. It suffices to give an upper bound
for Eδn2 , since
p
p
Eζ2 ≤ v log(Kn) Eδn2 ,
(103)

by (102) and Cauchy-Swartz inequality.
We further decompose Eδn2 as

Eδn2 ≤ E||Pn f 2 − Ef 2 ||Fǫ + ||Ef 2 ||Fǫ .

(104)

The second term is smaller than or equal to ǫ2 by definition. Using similar arguments
in the proof of Theorem 2.4.3 in van der Vaart and Wellner (1996), the first term can be
bounded by
r
p
6p
(105)
||Pn f 4 ||Fǫ .
4ε||F ||2n + E 1 + log N(ε||2F ||2n, Fǫ , L1 (Pn ))
n
For any f1 , f2 ∈ Fǫ , we have

Pn |f12 − f22 | ≤ Pn |f1 − f2 |4F ≤ 4||F ||n
46

p
Pn |f1 − f2 |2 .

The covering number N(ε||2F ||2n, Fǫ2 , L1 (Pn )) is thus bounded by


ε||F ||n
2
2
2
, F , L2 (Pn ) ,
N(ε||2F ||n, Fǫ , L1 (Pn )) ≤ N(ε||F ||n , Fǫ, L2 (Pn )) ≤ N
2

(106)

where Fǫ2 = {(f1 − f2 )2 : f1 , f2 ∈ Fǫ }.
Under the entropy assumption, we can further bound the right-hand side of (106) by
(2K/ε)2v . Take ε = K/n, note that 2K/ε ≤ 2n ≤ n2 when n ≥ 3, and v ≥ 1, (105) is
bounded by
r
r
2
p
6
+
24v
log
n
30v log n p
4K
8Kω
E||F ||2n +
E ||Pn f 4 ||Fǫ ≤
+
E ||Pn f 4 ||Fǫ . (107)
n
n
n
n
Similarly, we can show E||Pn f 4 ||Fǫ is bounded by
r
p
12||Pnf 8 ||F
κǫ + 16εE||F ||n ||F 3||n + E 1 + log N(16ε||F ||n||F 3 ||n , Fǫ4 , L1 (Pn ))
, (108)
n
for any ε > 0, where Fǫ4 = {(f1 − f2 )4 : f1 , f2 ∈ Fǫ }, κǫ = ||Ef 4 ||Fǫ . Besides, we have
N(16ε||F ||n||F 3 ||n , Fǫ4 , L1 (Pn )) ≤ N(4ε||F ||n, Fǫ , L2 (Pn )) ≤ N 2 (2ε||F ||n, F , L2 (Pn )) ,

since

Pn |f14 − f24 | ≤ Pn |f1 − f2 |4|F 3| ≤ Pn ||f1 − f2 ||n ||4F 3||n .

An application of Cauchy-Swartz inequality and Lemma C.3 implies
p
√
p
E ||Pn f 8 ||F ≤ E Pn F 8 ≤ EF 8 = O(ω 4).

Take ε = K/n in (108), E||Pn f 4 ||Fǫ is bounded by
!
!
r
r


v log n 4
v log n 4
E||F ||n ||F 3||n
+O
= κǫ + O
ω
ω .
κǫ + O
n
n
n

Combining this together with (104), (105) and (107) implies
!
r


κ
v
log
n
ǫ
3/4
2
2
2 3/4 −3/4
Eδn ≤ ǫ + O
+O ω v n
log n .
n

The assertion therefore follows together with (103).

Lemma C.8 Let X = (X1 , . . . , Xp )T and Y = (Y1 , . . . , Yp )T be Gaussian random vectors
X
with mean µX = µY = µ for some µ ∈ Rp and covariance matrices ΣX = (σjk
)j,k and
Y
Y
T
p
Σ = (σjk )j,k , respectively. Then for every β > 0 and µ = (µ1 , . . . , µp ) ∈ R , we have
E max Xj − E max Yj ≤ 2β −1 log p + β∆,
1≤j≤p

1≤j≤p

X
Y
where ∆ = maxj,k |σjk
− σjk
|.

Proof: The proof is similar to that of Theorem 1 in Chernozhukov et al. (2015). We note
that in Chernozhukov et al. (2015)’s paper they require µ = 0. However, such assumption
is redundant and the above error bound holds uniformly for all µ ∈ Rp .
47

