arXiv:1706.02410v1 [] 7 Jun 2017

A SHARP MULTIPLIER INEQUALITY WITH
APPLICATIONS TO HEAVY-TAILED REGRESSION
PROBLEMS
QIYANG HAN AND JON A. WELLNER

Abstract. We develop a sharp multiplier
Pinequality used to study the
size of the multiplier empirical process ( n
i=1 ξi f (Xi ))f ∈F , where ξi ’s
and F are multipliers and an indexing
function
class respectively. We
Pn
show that in general the size of E
i=1 ξi f (Xi ) F is determined jointly
by the growth rate of the corresponding empirical process, and the size
of the maxima of the multipliers.
The new inequality sheds light on the long-standing open question
concerning the rate behavior of classical empirical risk minimization procedures in the regression setting with heavy-tailed errors. In particular,
the convergence rate of the least squares estimator in a general nonparametric regression model, with usual entropy conditions on the function classes, is shown to be no worse than the maximum of the optimal
Gaussian regression rate and the noise level of the errors. Furthermore,
this rate cannot be improved in general. We also give an application to
the sparse linear regression model where both design and errors can be
heavy-tailed.

1. Introduction
1.1. The questions and motivation. In this paper we are interested in
the multiplier empirical process
(1.1)

n
X

ξi f (Xi )

i=1

indexed by a class F of measurable functions f : X → R. Here the real
valued multipliers ξ1 , . . . , ξn are independent of X -valued random variables
X1 , . . . , Xn . We do not impose any apriori structural assumptions on ξi ’s,
e.g. ξi can be arbitrarily correlated with each other. Neither do we impose
any structural assumptions on F.
The first question we address is the following.
Date: June 9, 2017.
2010 Mathematics Subject Classification. 60E15, 62G05.
Key words and phrases. multiplier empirical process, multiplier inequality, empirical
risk minimization, nonparametric regression, sparse linear regression, heavy-tailed errors.
Supported in part by NSF Grant DMS-1104832, DMS-1566514 and NI-AID grant R01
AI029168.
1

2

Q. HAN AND J. A. WELLNER

Question 1. Under what moment conditions on the ξi ’s can we assert that,
the multiplier empirical process (1.1) has roughly the same size as the empirical process counterpart for (nearly) all function classes F in a nonasymptotic manner?
Question 1 has been well understood in the asymptotic regime where
ξ1 , . . . , ξn are i.i.d. and F and X are fixed: the central limit theorem (CLT)
for the multiplier empirical process holds if and only if a CLT holds for the
empirical process, given the moment condition kξ1 k2,1 < ∞ (see Section 1.3
for notation), see [36] or Section 2.9 of [68].
Much less work has addressed non-asymptotic aspects concerning (1.1).
In deriving CLTs for the multiplier empirical process, a multiplier inequality relating the modulus of continuity of the multiplier empirical process
with that of the original empirical process is used, see [26, 27], or Lemma
2.9.1 of [68]. This inequality typically suffers from a huge loss in terms of
rates of convergence in the finite sample setting, see Section 5.1. In a recent
work of [49], (1.1) is studied using a multiscale truncated analogue of Talagrand’s γ2 functional only assuming weak moments on the ξi ’s. However,
the bound obtained in [49] does not take into account the Poisson (small
sample) behavior of the empirical process and hence reveals some difficulties in handling general function classes whose element-wise L2 size is much
smaller than its L∞ size, see Section 5.2.
The motivation for studying Question 1 arises from applications in statistical theory. In the empirical risk minimization (ERM) literature, one of
the long-standing fundamental questions is the following.
Question 2. What is the convergence rate of the nonparametric least squares
estimator(LSE) over a general regression function class with the presence
of heavy-tailed errors?
The nonparametric LSE is of fundamental importance in both statistical
theory and application, and serves as the building block for a large class
of more complicated penalized/aggregated estimators. By now, calculation
of rates of convergence for the LSE under light-tailed errors has been wellunderstood: we only need to evaluate the size of a localized Rademacher
or Gaussian process, e.g. [6, 7, 8, 30, 31, 43, 63, 65, 68]. This corresponds
to taking ξ1 , . . . , ξn to be i.i.d. Rademacher or Gaussian random variables
in (1.1). A precise understanding of Question 1 for general multipliers ξi ’s
would naturally lead to improved understanding towards Question 2.
Under heavy-tailed assumptions, one line of research [34, 45, 46, 47] asserts rate-optimality of related ERM procedures using least squares criteria, under a key structural assumption on the function class–namely Lsubgaussian or a small-ball condition. This shows that there are function
classes over which the LSE performs well under heavy-tailed errors. This
approach presents, to some degree, a best-case analysis in the sense that
the assumptions can fail for many other commonly used function classes
including (i) VC-subgraph classes, (ii) shape-restricted classes, (iii) smooth

MULTIPLIER INEQUALITIES

3

classes; see Section 5.2. Another line of research [3, 10, 11, 14, 15, 20, 28,
29, 38, 39, 40, 50] proposes alternative procedures with guaranteed optimal
rates of convergence in heavy-tailed problems (and some with subgaussian
performance), showing that there are good estimators other than the LSE
for general function classes under heavy-tailed errors. To date, it seems
that neither of the approaches gives a definite answer to the fundamental
Question 2.
1.2. Our contribution. 1 We attempt to make progress on the difficulties
2 by developing
mentioned above. We start addressing Question 1 in SectionP
a sharp multiplier inequality characterizing the size of E k ni=1 ξi f (Xi )kF .
Very informally,
E

n
X

ξi f (Xi )

i=1

F



≈ max ‘growth rate’ of k 7→ E

k
X
i=1

εi f (Xi )
F


, E max |ξi | .
1≤i≤n

In particular, the size of the multiplier empirical process is determined not
only by the size of the corresponding empirical process, but also by the
moments of the multipliers. Technically, we establish upper bounds in Theorems 1 and 2 for structureless multipliers ξi ’s and indexing function classes
F. A matching lower bound, established in Theorem 3, shows that the
moment barrier revealed by the multipliers in the size of the multiplier empirical process, is unimprovable without additional structural assumptions
on F.
As indicated before, a clear understanding of the size of the multiplier empirical process is crucial in addressing Question 2. Using our new multiplier
inequality, we show (see Theorem 4) that if the errors have finite Lp,1 (p ≥ 1)
moments, and the underlying function class is uniformly bounded with an
entropy of order ε−α for some α ∈ (0, 2), the rate of convergence for the LSE
in L2 metric is no worse than


1
1
1
OP n− 2+α ∨ n− 2 + 2p .
Furthermore, this rate is in general unimprovable (see Theorem 5). This
rate offers the first quantitative answer to the fundamental Question 2 for
a general regression function class, and shows a clear tradeoff between the
complexity of the function class and the heaviness of the tail of the errors.
We note that the uniform boundedness assumption of the function class is
more of a cliché of the localization property of the estimator : all that we
need is stochastic boundedness of the LSE.
1For notation see Section 1.3.

4

Q. HAN AND J. A. WELLNER

For least squares estimation in non-parametric regression models, we have
restricted our attention to Donsker classes. Such a situation changes drastically in the sparse linear regression model, where the empirical process part
of the Lasso problem is non-Donsker in the sense that its supremum over
the function class in question becomes unbounded as the problem dimension
grows. We suggest a new proof method that combines our new multiplier
inequality with Gaussian approximation techniques to quantify the growth
of the empirical process when both the design matrix and the errors can
be heavy-tailed. The new technique allows us to prove rate-optimality of
the Lasso estimator under a wide range of distributional assumptions on the
design and the errors.
The approach we adopt here, per se, can be viewed as a ‘worst-case’
analysis for the size of the multiplier empirical process, and the rate behavior
of the least squares estimator in the presence of heavy-tailed errors. Such
a view point naturally complements the ‘best-case’ analysis conducted in
[34, 45, 46, 47, 48]. We hope future contributions will go further in the
different directions suggested by both approaches.
1.3. Notation. For a real-valued random variable ξ and 1 ≤ p < ∞, let
1/p
kξkp := E |ξ|p
denote the ordinary p-norm. The Lp,1 norm for a random
variable ξ is defined by
Z ∞
P(|ξ| > t)1/p dt.
kξkp,1 :=
0

It is well known that Lp+ε ⊂ Lp,1 ⊂ Lp holds for any underlying probability
measure, and hence a finite Lp,1 condition requires slightly more than a p-th
moment, but no more than any p + ε moment, see Chapter 10 of [37].
For a real-valued measurable function f defined on (X , A, P ), kf kLp (P ) ≡
kf kP,p ≡ P |f |p )1/p denotes the usual Lp -norm under P , and kf k∞ ≡
supx∈X |f (x)|. f is said to be P -centered if P f = 0. Lp (g, B) denotes the
Lp (P )-ball centered at g with radius B. For simplicity we write Lp (B) ≡
Lp (0, B). To avoid unnecessary measurability digressions, we will assume
that F is countable throughout the article. As usual, for any φ : F → R,
we write kφ(f )kF for supf ∈F |φ(f )|.
Throughout the article ε1 , . . . , εn will be i.i.d. Rademacher random variables independent of all other random variables. Cx will denote a generic
constant that depends only on x, whose numeric value may change from
line to line unless otherwise specified. a .x b and a &x b mean a ≤ Cx b
and a ≥ Cx b respectively, and a ≍x b means a .x b and a &x b [a . b
means a ≤ Cb for some absolute constant C]. For two real numbers a, b,
a ∨ b ≡ max{a, b} and a ∧ b ≡ min{a, b}.
1.4. Organization. Section 2 is devoted to the new multiplier inequality,
while Sections 3-4 are devoted to applications of the multiplier inequalities
to nonparametric and sparse linear regression models, respectively. We make

MULTIPLIER INEQUALITIES

5

some further remarks and comparisons in Section 5. Most detailed proofs
are relegated to Sections 6-7.
2. The multiplier inequality
2.1. Upper bound. We first state the assumptions.
Assumption A. Suppose that ξ1 , . . . , ξn are independent of the random variables X1 , . . . , Xn , and either of the following conditions holds:
(A1) X1 , . . . , Xn are i.i.d. with law P on (X , A), and F is P -centered.
(A2) X1 , . . . , Xn are permutation invariant, and ξ1 , . . . , ξn are independent mean-zero random variables.
Theorem 1. Grant Assumption A. Let F1 ⊃ · · · ⊃ Fn be a non-increasing
sequence of function classes. Assume further that there exist non-decreasing
concave functions {ψn } : R≥0 → R≥0 with ψn (0) = 0 such that
k
X

E

(2.1)

εi f (Xi )

i=1

Fk

holds for all 1 ≤ k ≤ n. Then
E

(2.2)

n
X

ξi f (Xi )

i=1

where Γξn (t) ≡

1
n

Fn

Pn

≤4



|ξi | > t .

i=1 P

Z

∞
0

≤ ψn (k)


ψn nΓξn (t) dt,

The formulation of Theorem 1 requires non-increasing {Fk }. This is suitable for studying the size of the multiplier empirical process indexed by
function classes with a shrinking L2 size. It is also possible to use Theorem
1 for the case F1 = · · · = Fn ; see Section 4 for an application to the sparse
linear regression model.
The key ingredient in the proof of Theorem 1 is the following, which may
be of independent interest.
Proposition 1. Grant Assumption A. For any function class F,
" n
n
k
X
X
X
(2.3)
ξi f (Xi )
≤E
E
εi f (Xi )
( η(k) − η(k+1) )E
i=1

F

k=1

i=1

F

#

where η(1) ≥ · · · ≥ η(n) ≥ η(n+1) ≡ 0 are the reversed order statistics for
(i) (under (A1)) {2 |ξi |}ni=1 , (ii) (under (A2)) {|ξi − ξi′ |}ni=1 with {ξi′ } being
an independent copy of {ξi }.
In the simplest case where ξi ’s are uniformly bounded, (2.3) implies that
the multipliers can be ‘replaced’ by Rademachers. This is the content of
the classical contraction principle (see Section 3.1.4 of [24]). In the general
case for unbounded multipliers, (2.3) suggests that the size of the empirical
Pk
process E
needs to be adjusted with some measure for the
i=1 εi f (Xi )
F

6

Q. HAN AND J. A. WELLNER

heaviness of the tails of the ξi ’s. Hence Proposition 1 can also be viewed
as an interpolation inequality from the contraction principle for bounded
multipliers to unbounded multipliers. We note that in the simple case for
i.i.d. multipliers, an inequality in the spirit of (2.3) has implicitly been used
in [27], see also page 177-178 of [68].
A canonical example in applications is the following.
Theorem 2. Consider the same assumptions as in Theorem 1. Assume for
simplicity that ξi ’s have the same marginal distributions. Suppose that for
some γ ≥ 1, and some constant κ0 > 0,
E

(2.4)

k
X
i=1

εi f (Xi )
Fk

≤ κ0 · k1/γ

holds for all 1 ≤ k ≤ n. Then for any p ≥ 1 such that kξ1 kp,1 < ∞,
E

n
X
i=1

ξi f (Xi )
Fn

≤ 4κ0 · nmax{1/γ,1/p} kξ1 kmin{γ,p},1 .

Proof. First consider
ψn (t) ≡ κ0 t1/γ in Theorem
Pn γ ≤ p. In this case, letting
1/γ
1, we see that E k i=1 ξi f (Xi )kFn ≤ 4κ0 · n kξ1 kγ,1 . On the other hand,
P
if γ > p, we can take ψn (t) ≡ κ0 t1/p to conclude that E k ni=1 ξi f (Xi )kFn ≤
4κ0 · n1/p kξ1 kp,1 . Note that γ ≥ 1 ensures the concavity of ψn .

Theorem 2 says that the upper bound for the multiplier empirical process
has two components: one part comes from the growth rate of the empirical process; another part comes from the moment barrier of the multipliers ξi ’s. Note that the growth rate n1/p corresponds to the worst size of
E max1≤i≤n |ξi | under a p-th moment condition on ξi ’s.
Remark 1. Choosing γ ≥ 2 in Theorem 2 corresponds to the bounded
Donsker regime2 for the empirical process. In this case we only need kξ1 k2,1 <
∞ to ensure the multiplier empirical process to be also bounded Donsker.
This moment condition is generally unimprovable in view of [35]. On the
other hand, such a choice of γ can fail due to: (i) failure of integrability
of the envelope functions of the classes {Fk }, or (ii) failure of the classes
{Fk } to be bounded Donsker. (i) is related to the classical MarcinkiewiczZygmund strong laws of large numbers and the generalizations of those to
empirical measures, see [2, 41, 44]. For (ii), some examples in this regard
can be found in [57], see also Proposition 17.3.7 of [55].
Remark 2. An important assumption we make in Theorems 1 and 2 is the
independence of the multipliers (ξ1 , . . . , ξn ) and the samples (X1 , . . . , Xn ).
We conjecture that the independence assumption cannot be removed based
on a result of [1]: there is no universal multiplier moment for the CLT.
2F is said to be bounded Donsker if sup
n∈N E supf ∈F

√1
n

Pn

i=1

εi f (Xi ) < ∞.

MULTIPLIER INEQUALITIES

7

Remark 3. Although Theorems 1 and 2 are formulated in a non-asymptotic
fashion, they can also be used to examine asymptotic equicontinuity of the
multiplier empirical process; see Section 5.1 for more details.
Remark 4. One particular case for application of Theorems 1 and 2 is the
following. Let δ1 ≥ . . . ≥ δn ≥ 0 be a sequence of non-increasing nonnegative real numbers, and F be an arbitrary function class. Let Fk ≡
F(δk ) ≡ {f ∈ F : P f 2 < δk2 } be the ‘local’ set of F with L2 -radius at most
δk . An important choice in statistical applications for δk is given by
(2.5)

E

k
X

. kδk2 .

εi f (Xi )

i=1

F (δk )

As will be seen in Section 3, the above choice {δk } corresponds to the rate
of convergence for the LSE in a general nonparametric regression model. In
this case Theorems 1 and 2 yield that
(2.6)

E

n
X

. nδn2

ξi f (Xi )

i=1

given sufficient moments of the ξi ’s.

F (δn )

Theorems 1 and 2 only concern the first moment of the suprema of the
multiplier empirical process. For higher moments, we may use the following
Hoffmann-Jørgensen-Talagrand type inequality relating the q-th moment
estimate with the first moment estimate in some independent cases.
Lemma 1 (Proposition 3.1 of [23]). Suppose X1 , . . . , Xn are i.i.d. with law
P and ξ1 , . . . , ξn are i.i.d. with kξ1 k2 < ∞. Let F be a P -centered, countable
class of class of functions such that supf ∈F P f 2 ≤ σ 2 . Then for any q ≥ 1,
!q
q

n
n
X
X
q
ξi f (Xi )
ξi f (Xi ) ≤ K
E sup
E sup
f ∈F i=1

f ∈F i=1

+q

q/2


√
q
q
q
q
( n kξ1 k2 σ) + q E max |ξi | sup |f (Xi )| .

Here K > 0 is a universal constant.

1≤i≤n

f ∈F

2.2. Lower bound. Theorems 1 and 2 do not require any structural assumptions on the function class F. [49] showed that for a ‘L-subgaussian’
class, a 2 + ε moment on i.i.d. ξi ’s suffices to conclude that the multiplier
empirical process behaves like the canonical Gaussian process (see Section
5.2 for more details). One may therefore wonder if the moment barrier for
the multipliers in Theorem 2 is due to an artifact of the proof. Below in
Theorem 3 we show that this barrier is intrinsic for general classes F.

Theorem 3. Let X = [0, 1]d and P be a probability measure on X with
Lebesgue density bounded away from 0 and ∞. Let ξ1 , . . . , ξn be i.i.d. random variables such that E max1≤i≤n |ξi | ≥ κ0 n1/p for some p > 1 and some

8

Q. HAN AND J. A. WELLNER

p
complexity of function class dominates=n1/γ

2

moment barrier dominates=n1/p
2

α=

2
γ−1

Figure 1. Tradeoff between the complexity of the function
class and the moment of the multipliers in the size of the
multiplier empirical process. The critical curve (purple): p =
1 + 2/α.
constant κ0 independent of ξ1 . Then for any γ > 2, there exists a sequence
of function classes F1 ⊃ · · · ⊃ Fn all defined on X such that for n large
enough,
E

k
X

εi f (Xi )

i=1

Fk

≤ κ1 · k1/γ ,

holds for all 1 ≤ k ≤ n, and that
E

n
X
i=1

ξi f (Xi )
Fn

max{1/γ,1/p}
≥ κ−1
.
1 n

Here κ1 is a constant depending on κ0 , γ and P .
Remark 5. The condition on ξi ’s will be satisfied, e.g. if the ξi ’s are i.i.d.
with the tail condition P(|ξi | > t) ≥ κ′0 /(1 + tp ) for t > 0.
Combined with Theorem 2, it is seen that the growth rate nmax{1/γ,1/p}
of the multiplier empirical process cannot be improved in general. This
suggests an interesting phase transition phenomenon (cf. Figure 1): if the
complexity of the function class dominates the effect of the tail of the multipliers, then the multiplier empirical process essentially behaves as the empirical process counterpart; otherwise the size of the maxima of the multipliers
governs the growth of the multiplier empirical process in general.
3. Nonparametric regression: least squares estimation
In this section, we consider the nonparametric regression model:
(3.1)

Yi = f0 (Xi ) + ξi ,

i = 1, . . . , n

MULTIPLIER INEQUALITIES

9

where f0 ∈ F, X1 , . . . , Xn are i.i.d. random variables from P , and ξ1 , . . . , ξn
are mean-zero errors. Let fˆn be any least squares estimator (LSE) over F:
n
2
1X
Yi − f (Xi ) .
fˆn ∈ arg min
f ∈F n
i=1

We assume without loss of generality that fˆn is well-defined.
As discussed in the Introduction, there seems to be no satisfactory solution addressing the question, as to when the LSE performs ‘well’ or ‘badly’
under substantially weaker moment assumptions on the errors for a general
function class. Our theorem below tries to shed some light on this problem
in the realm where the function class F satisfies entropy conditions.
Let (F, k·k) be a subset of the normed space of real functions f : X →
R. Let N (ε, F, k·k) be the ε-covering number, and N[ ] (ε, F, k·k) be the
ε-bracketing number; see page 83 of [68] for more details.
Assumption B. Suppose that F ⊂ L∞ (1) satisfies either of the following
conditions: there exists some α ∈ (0, 2) such that for any ε ∈ (0, 1),


(F1) supQ log N ε kF kL2 (Q) , F, L2 (Q) . ε−α .

(F2) log N[ ] (ε, F, L2 (P )) . ε−α .
Here the supremum in (F1) is taken over all finitely discrete probability
measures Q, and F denotes the envelope function for F.

Theorem 4. Suppose that ξ1 , . . . , ξn are mean-zero errors independent of
X1 , . . . , Xn with the same marginal distributions, and kξ1 kp,1 < ∞ for some
p ≥ 1. Further suppose that F is a P -centered function class such that
F − f0 ⊂ L∞ (1) satisfies Assumption B with some α ∈ (0, 2). Then


1
−1+ 1
= OP n− 2+α ∨ n 2 2p .
fˆn − f0
(3.2)
L2 (P )

If ξi ’s are i.i.d. F need not be P -centered. Furthermore, if ξi ’s are i.i.d.
and p ≥ 2, then (3.2) holds in expectation.
The proof relies on the following reduction scheme.
Proposition 2. Suppose that ξ1 , . . . , ξn are mean-zero random variables
independent of X1 , . . . , Xn , and F − f0 ⊂ L∞ (1). Further assume that
n

(3.3)

E

sup
f ∈F :kf −f0 kL

2 (P )

≤δ

and

1 X
√
ξi (f − f0 )(Xi ) . φn (δ),
n
i=1
n

(3.4)

E

sup
f ∈F :kf −f0 kL

2 (P )

≤δ

1 X
√
εi (f − f0 )(Xi ) . φn (δ).
n
i=1

=
hold for some φn such that δ 7→ φn (δ)/δ is non-increasing. Then fˆn − f0
L2 (P )
√ 2
OP (δn ) holds for any δn such that φn (δn ) ≤ nδn . Furthermore, if ξ1 , . . . , ξn

10

Q. HAN AND J. A. WELLNER

are i.i.d. mean-zero with kξ1 kp < ∞ for some p ≥ 2, then E fˆn − f0
1
1
√
O(δn2 ) for any δn ≥ n− 2 + 2p such that φn (δn ) ≤ nδn2 .

2
L2 (P )

=

The remaining task in the proof of Theorem 4 is a calculation of the
modulus of continuity of the (multiplier) empirical process involved in (3.3)
and (3.4) using Theorem 1 and local maximal inequalities for the empirical
process (see Proposition 5).
Remark 6. Some remarks on the assumptions on F.
(1) Assumption B requires F to be a Donsker class. Although the proof
applies to non-Donsker function classes with α ≥ 2, the first term in
(3.2) becomes sub-optimal in general, see [8].
(2) F is assumed to be P -centered to allow errors with arbitrary dependence structure. It is known from [69] (see Theorem 1, page 638)
that for a centered function class, the minimax risk of estimating
a regression function under arbitrary errors with second moments
uniformly bounded, is no worse than that for i.i.d. Gaussian errors.
If the errors are i.i.d., then F need not be P -centered.
(3) The uniform boundedness assumption on F includes many classical
examples, cf. Section 9.3 of [65]. In fact, this is more of a localiza= OP (1).
tion property for the estimator : all that we need is fˆn
∞
Proving stochastic boundedness of the LSE usually serves as the first
step in deriving a rate of convergence and this may require casespecific techniques. For instance, for isotonic regression on [0, 1],
stochastic boundedness follows easily from the min-max representation of [53] if kf0 k∞ < ∞.

At this point, (3.2) only serves as an upper bound for the convergence
1
rates of the LSE. Since the rate n− 2+α corresponds to the optimal rate in
the Gaussian regression case [70], it is natural to conjecture that this rate
−1+ 1
cannot be improved. On the other hand, the ‘noise’ rate n 2 2p is due to
the reduction scheme Proposition 2, which relates the convergence rate of
the LSE to the size of the multiplier empirical process involved. It seems
natural to wonder if this noise rate is a proof artifact due to the deficiency
in Proposition 2.
Theorem 5. Let X = [0, 1]d and P be a probability measure on X with
Lebesgue density bounded away from 0 and ∞. Suppose that ξ1 , . . . , ξn are
i.i.d. mean-zero random variables with kξ1 kp,1 < ∞ for some p ≥ 2.
(1) For each α ∈ (0, 2), there exists a function class F and some f0 ∈ F
such that F − f0 satisfies Assumption B, and that for p ≥ 1 + 2/α,
there exists some least squares estimator fn∗ over F satisfying
1

E kfn∗ − f0 kL2 (P ) ≥ ρ · n− 2+α .

Here ρ > 0 is a (small) constant independent of n.

MULTIPLIER INEQUALITIES

11

p
1

Gaussian rate =n− 2+α

2

1

1

noise rate=n− 2 + 2p
2

α

Figure 2. Tradeoff between the complexity of the function
class and the noise level of the errors in the convergence rates
for the LSE. The critical curve (purple): p = 1 + 2/α.
(2) There exists a function class F ≡ Fn contained in a fixed uniformly
bounded VC-subgraph function
√ class, and some f0 ∈ F such that
the following holds: suppose log n ≤ p ≤ (log n)1−δ for some δ ∈
(0, 1/2). Then there exists some law for the error ξ1 with kξ1 kp,1 .
log n, such that for n large enough, there exists some least squares
estimator fn∗ over Fn satisfying
1

1

E kfn∗ − f0 kL2 (P ) ≥ ρ′ · n− 2 + 2p (log n)−2 .

Here ρ′ > 0 is a (small) constant independent of n.
The first claim of the above theorem justifies the heuristic conjecture
that the convergence rate for the LSE with heavy-tailed errors, should be
no better than the optimal rate in the Gaussian regression setting. Although
here we give an existence statement, the proof is constructive: in fact we
use (essentially) the Hölder class. Other function classes are also possible if
we can handle the Poisson (small-sample) domain of the empirical process
indexed by these classes. The second claim asserts that there is a ‘simple’
problem (=VC-subgraph class) for which the noise level dominates the risk
for the least squares estimator.
Remark 7. It is easy to derive from Proposition 2 that, considering the
size of kξ1 kp,1 , the rate for LSE in (2) of the above theorem is no worse
1/2

1

1

1

1

than kξ1 kp,1 n− 2 + 2p . n− 2 + 2p (log n)1/2 . Hence we miss at most a polylogarithmic factor in the lower
√ bound in (2) of Theorem 5. We suspect that
the moment condition p ≥ log n is a proof artifact. It would be interesting
to further investigate if this condition can be removed.
1

−1+

1

Theorem 5 implies that the rate OP (n− 2+α ∨ n 2 2p ) obtained in Theorem 4 cannot be improved in general. This translates the tradeoff in the
size of the multiplier empirical process between the complexity of the function class and the heaviness of the tail of the errors (multipliers) into the
convergence rate of the LSE (cf. Figure 2):

12

Q. HAN AND J. A. WELLNER

(1) If p ≥ 1 + 2/α, then fˆn − f0

L2 (P )



1
= OP n− 2+α . In this case, the

noise level is ‘small’ compared with the complexity of the function
class so that the LSE achieves the optimal rate as in the case for
i.i.d. Gaussian errors (see [70]).
 1 1
− +
= OP n 2 2p . In this case,
(2) If p < 1 + 2/α, then fˆn − f0
L2 (P )

the noise is so heavy-tailed that the worst-case rate of convergence
of the LSE is governed by this noise barrier.
If p → ∞, i.e. the errors become increasingly light-tailed, then the optimal
rate in the Gaussian regression case (3.2) will eventually dominate. On the
other hand, if p = 2, i.e. there are only (essentially) second moments for the
errors, then (3.2) will be OP (n−1/4 ), which is the boundary rate for Donsker
and non-Donsker classes, cf. Figure 2.
4. Sparse linear regression: Lasso revisited
In this section we consider the sparse linear regression model:
(4.1)

Y = Xθ0 + ξ

where X ∈ Rn×d is a (random) design matrix and ξ = (ξ1 , . . . , ξn ) is a meanzero noise vector independent of X. When the true signal θ0 is sparse, one
popular estimator is the Lasso [60]:


1
2
kY − Xθk2 + λ kθk1 .
(4.2)
θ̂(λ) ≡ arg min
θ∈Rd n
The lasso estimator has been thoroughly studied in a vast amount of literature; we only refer the readers to the monograph [12] for a comprehensive
overview.
Our main interest here will be the following question: under what moment
conditions on the distributions of X and ξ can the lasso estimator enjoy
the optimal rate of convergence? In particular, neither X nor ξ need be
light tailed apriori, and ξ1 , . . . , ξn need not be independent from each other.
Previous works guaranteeing rate-optimality of the Lasso estimator typically
assume that both X and ξ are sub-gaussian, see [12, 51, 64], or at least X
is sub-gaussian, see [34]. The problem is challenging as we move out of
the sub-gaussian realm since, as we will see, the level of unboundedness of
the underlying empirical process depends on both the tail of X and ξ and
the parameters (d, n). This requires a different analysis compared with the
Donsker indexing function classes in Section 3.
Before stating the result, we need some notion of the compatibility condition: For any L > 0 and S ⊂ {1, . . . , d}, define


p
1
φ(L, S) = |S| min √ kXθS − XθS c k2 : kθS k1 = 1, kθS c k1 ≤ L .
n
Here for any θ = (θi ) ∈ Rd , θS ≡ (θi 1i∈S ) and θS c ≡ (θi 1i∈S
/ ). Let B0 (s) be
the set of s-sparse vectors in Rd , i.e. θ ∈ B0 (s) if and only if |{i : θi 6= 0}| ≤ s.

MULTIPLIER INEQUALITIES

13

Further let Σ = EΣ̂ where Σ̂ = X ⊤ X/n is the sample covariance matrix,
and σ d = σmin (Σ) and σ̄d = σmax (Σ) be the smallest and largest singular
value of the population covariance matrix, respectively. d = dn and s = sn
can either stay bounded or blow up to infinity in asymptotic statements.
Theorem 6. Let X be a design matrix with i.i.d. mean-zero rows, and
0 < lim inf σ d ≤ lim sup σ̄d < ∞. Suppose that
min φ(3, S) ≥ c0
(4.3)
|S|≤s

holds for some c0 > 0 with probability tending to 1 as n → ∞, and that for
some 1/4 ≤ α ≤ 1/2,

log d · M4 (X) ∨ log2 d
(4.4)
lim sup
< ∞,
n2−4α
n→∞
p
where M4 (X) ≡ E max1≤j≤d |X1j |4 . Then for θ̂ L ≡ θ̂(2L kξn k1/α,1 log d/n),
(4.5)


16L2 kξn k21/α,1 s log d
2
1
L
·
lim lim sup sup Pθ0
= 0.
X(θ̂ − θ0 ) >
L→∞ n→∞ θ0 ∈B0 (s)
n
n
2
c20
R∞
P
Here kξn k1/α,1 ≡ 0 Γξn (t)α dt, where Γξn (t) = n1 ni=1 P(|ξi | > t) is defined in Theorem 1.
p
The rate s log d/n in the above theorem is well-known to be (nearly)
minimax optimal for prediction in the sparse linear regression model. The
quantity kξn k1/α,1 should be thought as the ‘noise level’ of the regression
problem. For instance, if ξi ’s are i.i.d, and α = 1/2, then kξn k1/α,1 = kξ1 k2,1 .
Although in Theorem 6 we only consider prediction error, estimation error
L
θ̂ − θ0 can be obtained using completely similar arguments by noting
1
that Lemma 2 below also holds for estimation error.
As an illustration of the scope of Theorem 6, we consider some different
scaling regimes for the parameter space (d, n, s). For simplicity of discussion
we assume that the errors ξ1 , . . . , ξn have the same marginal distributions
and the design matrix X has i.i.d. entries such that X1,1 has a Lebesgue
density bounded away from ∞ and kX1,1 k2,P = 1.
Example 1. Consider the scaling regime d/n → λ ∈ (0, 1). We claim that
kX11 kP,4+ε ∨ kξk4,1 < ∞ for some ε > 0 guarantees the validity of (4.5).
First, (4.3) holds under the finite fourth moment condition, see [5]. Second,
(4.4) holds under the assumed moment conditions. Note that a fourth moment condition on X11 is necessary: if kX11 kP,4 = ∞, then lim sup σ̄d = ∞
a.s., see [4]. This appears to be a new result; [39] considered a different
‘tournament’ Lasso estimator with best tradeoff between confidence statement and convergence rate under heavy-tailed designs and errors.
Example 2. If the entries of X have sub-exponential tails, then Theorem
E of [33] showed that (4.3) holds with probability tending to 1 as n → ∞

14

Q. HAN AND J. A. WELLNER

under (s log d ∨ log3 d)/n → 0. Condition (4.4) is satisfied if kξk2+ε < ∞ up
to a mild dimension constraint d ≤ exp(ncε ) for some constant cε > 0. This
seems to be a new result; the recent result of [56] considered the similar tail
condition on X along with a sub-exponential tail for the errors ξi ’s, while
their rates are not optimal.
Example 3. If the entries of X have sub-gaussian tails, then (4.3) holds
with probability tending to 1 under the scaling s log d/n → 0 (see [52, 54]).
Condition (4.4) is satisfied if kξk2+ε < ∞, which recovers a recent result of
[34] in the case where X and ξ are independent, up to a mild dimension
′
constraint d ≤ exp(ncε ) for some constant c′ε > 0.
Now we prove Theorem 6. The following reduction is well-known.
Lemma 2 (Theorem 6.1 of [12]). On the event
(
)
r
n
2X
log d
EL ≡ max
ξi Xij ≤ L
,
(4.6)
1≤j≤d n
n
i=1
p
with tuning parameter λ ≡ 2L log d/n, it holds that
1
X(θ̂ L − θ0 )
n

2
2

≤

s0 log d
16L2
·
2
φ (3, S0 )
n

where S0 = {i : (θ0 )i 6= 0} and s0 = |S0 |.
The difficulty involved here is that both X and ξ can be heavy tailed.
By Theorem 1, to account for the effect of ξi ’s, we only need to track the
Pk
size of E max1≤j≤d
i=1 εi Xij at each scale k ≤ n. The empirical process
√
(normalized by k) is unbounded as d → ∞ and hence requires a different
analysis from that given in Section 3.
Lemma 3. Let X1 , . . . , Xn be i.i.d. random vectors in Rd with covariance
matrix Σ. If supd σmax (Σ) < ∞, then for all k, d ∈ N,
E max

1≤j≤d

k
X
i=1

1/4
+ (k log d)1/2 .
εi Xij . k log3 d · M4 (X) ∨ log2 d

The proof of the lemma is inspired by the recent work [17] who considered
Gaussian approximation of the maxima of high-dimensional random vectors
by exploiting second moment information for the Xi ’s. We modified their
method by taking into account the third moment information of Xi ’s induced
by the symmetric Rademacher εi ’s; such a modification proves useful in
identifying certain sharp moment conditions considered in the examples (in
particular Example 1). See Section 7.1 for a detailed proof.
Proof of Theorem 6. By Lemma 2 and the assumption on the compatibility condition (4.3), we see that with the choice for tuning parameter λ ≡

MULTIPLIER INEQUALITIES

2L kξn k1/α,1

15

p

log d/n, the left side of (4.5) can be bounded by
!
2 kξ k2
16L
2
n
s
log
d
1
1/α,1
+ o(1)
·
P θ0
X(θ̂ L − θ0 ) >
n
φ2 (3, S0 )
n
2
r


n
log d
2X
ξi Xij > L kξn k1/α,1
+ o(1).
≤ P max
1≤j≤d n
n

(4.7)

i=1

By Lemma 3, we can apply Theorem 1 with F1 = · · · = Fn ≡ {πj : Rd →
R, j = 1, . . . , d} where πj (x) = xj for any x = (xl )dl=1 ∈ Rd , and


p
1/4
ψn (k) ≡ C kα log3 d · M4 ∨ log2 d
+ k1/2 log d
for some 1/4 ≤ α ≤ 1/2 to conclude that
E max

1≤j≤d

n
X

ξi Xij . n

i=1

α

1/4
log d · M4 ∨ log d
3

2

+n

p
1/2

log d

Z

Z

∞

0

∞
0

Γξn (t)α dt

Γξn (t)1/2 dt



p
1/4
. nα log3 d · M4 ∨ log2 d
+ n1/2 log d kξn k1/α,1 .

By Markov’s inequality, (4.7) can be further bounded (up to constants) by
1/4

1 log d · (M4 ∨ log2 d)
+ o(1).
∨1
L
n2−4α

The claim of Theorem 6 therefore follows from the assumption (4.4).



5. Further remarks
5.1. Comparison of Theorem 1 with the multiplier inequality in
[68]. In this section we compare the multiplier inequality in Theorem 1
with the one in Section 2.9 of [68], which originates from [26, 27]: for i.i.d.
mean-zero ξi ’s and i.i.d. Xi ’s, and for any 1 ≤ n0 ≤ n,
n

(5.1)

1 X
ξi f (Xi )
E √
n
i=1

F

. (n0 − 1)E kf (X1 )kF

E max1≤i≤n |ξi |
√
n

k
1 X
εi f (Xi )
+ kξ1 k2,1 max E √
n0 ≤k≤n
k i=1

.
F

5.1.1. Asymptotic setting. The primary application of (5.1) rests in studying
asymptotic equicontinuity of the multiplier empirical process in the following
sense. Suppose that F is Donsker, then by theP
integrability of the empirical
n
3
−1/2
process (see Lemma 2.3.11 of [68]) , E n
i=1 εi f (Xi ) Fδ → 0 as n →
∞ followed by δ → 0. Now apply (5.1) via n → ∞, n0 → ∞ followed by
3Here F ≡ {f − g : f, g ∈ F, kf − gk
δ
L2 (P ) ≤ δ}.

16

Q. HAN AND J. A. WELLNER

P
δ → 0 we see that E n−1/2 ni=1 ξi f (Xi ) F → 0 as n → ∞ followed by
δ P

δ → 0 if kξ1 k2,1 < ∞. This shows that √1n ni=1 ξi f (Xi ) f ∈F satisfies a
CLT in ℓ∞ (F) if F is Donkser and the ξi ’s are i.i.d. with kξ1 k2,1 < ∞. The
moment condition is known to be unimprovable in general [35].
Our new multiplier inequality, Theorem 1, can also be used to study
asymptotic equicontinuity of the multiplier empirical process with the help
of the following lemma.
Lemma 4. Fix 0 ≤ γ ≤ 1 and a concave function ϕ : R≥0 → R≥0 such that
ϕ(x) → ∞ as x → ∞. Let {an } ⊂ R≥0 be such that an → 0 as n → ∞, and
ψ : R≥0 → R≥0 be the least concave majorant of {(n, an ϕ(n))}∞
n=0 . Then
ψ(t)/ϕ(t) → 0 as t → ∞.
P
Take any sequence δn → 0 and let an ≡ E n−1/2 ni=1 εi f (Xi ) F . By
δn
Lemma 4, the least concave majorant function ψ : R≥0 → R≥0 of the map
n 7→ an n1/2 (n ≥ 0) satisfies ψ(t)/t1/2 → 0 as t → ∞. Now an application of
Theorem 1 and the dominated convergence theorem shows that
Z ∞
n
ψ(nP(|ξ1 | > t)) p
1 X
p
· P(|ξ1 | > t) dt → 0
ξi f (Xi )
≤4
E √
n
nP(|ξ1 | > t)
0
i=1
as n → ∞.

Fδn

5.1.2. Non-asymptotic setting. The major drawback of (5.1) is that it is
not sharp in a non-asymptotic setting. For an illustration, let ξ1 , . . . , ξn be
i.i.d. multipliers with kξ1 kp,1 < ∞(p ≥ 3), Xi ’s be i.i.d. samples uniformly
distributed on [0, 1], and F be a uniformly bounded function class on [0, 1]
satisfying Assumption B with α ≡ 1. For example, F can be the class
of uniformly Lipschitz functions on [0, 1], or uniformly bounded monotonic
functions on [0, 1]. We apply (5.1) with F(n−1/3 ) (note that n−1/3 is the
usual local radius for 1-smooth problems) and local maximal inequalities for
the empirical process (Proposition 5) to see that
(5.2)


n
1 X
− 71 12 − p1
−1/6
−1/2+1/p
.
. inf (n0 − 1)n
+ n0
≍n
ξi f (Xi )
E √
1≤n0 ≤n
n
−1/3
i=1

F (n

)

On the other hand, Theorem 2 gives the sharp rate (recall p ≥ 3):
n

1 X
E √
ξi f (Xi )
n
i=1

. n−1/6 .
F (n−1/3 )

It is easily seen that the bound (5.2) calculated from (5.1) is far from optimal
even if p is very large.
5.2. Connections with Mendelson’s work.

MULTIPLIER INEQUALITIES

17

5.2.1. On the ‘L-subgaussian’ and ‘small-ball’ conditions. In a series of papers by Mendelson and his coauthors [32, 34, 38, 39, 45, 46], ERM procedures
from various perspectives are studied under ‘L-subgaussian’, ‘small-ball’ conditions and their variants.
Definition 1. A function class F
(1) is ‘L-subgaussian’ with respect to P if and only if for any f, g ∈
F, kf − gkψ2 (P ) ≤ L kf − gkL2 (P ) where k·kψ2 (P ) denotes the Orlicz
2

norm under P with ψ2 (x) = ex − 1.
(2) satisfies a small-ball condition with respect to P if and only if there
exists some constant κ > 0, ε ∈ (0, 1] such that for every f, g ∈
F ∪ {0},

P |f (X) − g(X)| ≥ κ kf − gkL2 (P ) ≥ ε.

These notions are especially well-suited for function classes with a certain moment equivalence property. In particular, F being sub-gaussian is
√
equivalent to kf kLp (P ) . p kf kL2 (P ) for all p ≥ 2. If there exists some
p > 2 such that the above inequality is true for all f ∈ F, then F satisfies
a small-ball condition4. A canonical example for such function classes is
given by F ≡ {fa (x) = x⊤ a : a ∈ Rp }, and P an isotropic and sub-gaussian
measure on Rp (see Definition 1.2 of [34]). On the other hand, we will see
below that such notions represent, in a certain sense, ‘best-case’ function
classes in statistical applications.
Proposition 3. The following function classes do not satisfy a small-ball
condition (and hence are not sub-gaussian) under the uniform law P on
[0, 1].
(1) The class of indicator functions on [0, 1]:
F = {1[a,b] : 0 ≤ a ≤ b ≤ 1}.

(2) The class of uniformly bounded monotonic/convex functions on [0, 1].
(3) The class of uniformly Lipschitz functions/C α functions with uniformly bounded derivatives on [0, 1].
These examples show that the best-case ‘small-ball’ or ‘sub-gaussian’ condition does not cover (i) VC-subgraph classes (ii) shape-restricted classes
(iii) smooth classes, and hence the theories developed in a series of work of
[34, 38, 39, 45, 46, 47] cannot be directly applied for these frequently used
function classes.
5.2.2. Connections with [49]. [49] studied the multiplier empirical process
(1.1) via a multiscale truncated analogue of Talagrand’s γ2 functional. We
briefly describe the machinery. For a random variable Z, and p ≥ 1, define

kZk(p) := sup1≤q≤p

kZkLq
√ .
q

This norm measures in a sense the ‘sub-gaussian’

4Hence the moment equivalence condition in [38, 39] is stronger than a small-ball

condition.

18

Q. HAN AND J. A. WELLNER

behavior of Z up to the p-th moment. The key quantity used in [49] is the
following: for a function class F, a given u ≥ 1 and s0 ≥ 0,


X
2s/2 kf − πs f k(u2 2s ) + 2s0 /2 sup kπs0 f k(u2 2s0 ) 
Λ̃s0 ,u (F) ≡ inf  sup
f ∈F

f ∈F s≥s
0

where the infimum is taken over all admissible5 sequences {Fs }s≥0 and πs f
is the nearest point in Fs of f with respect to the (u2 2s ) norm. s0 is the
‘starting level’ of the chain. A standard generic chaining argument shows
that for any function class F, with probability at least 1−c0 exp(−u2 2s0 /c0 ),
sup |Gn f | ≤ c1 uΛ̃s0 ,u (F)

(5.3)

f ∈F

√
holds for some absolute constants c0 , c1 ≥ 1. Here Gn ≡ n(Pn − P ).
One main conclusion in [49] is to obtain a bound analogous to (5.3) for the
multiplier empirical process with i.i.d. multipliers ξi ’s admitting 2 + ε moments, cf. Theorem 1.9 in [49]. Such a result is easy to see for L-subgaussian
classes: if F is subgaussian, then Λ̃s0 ,u (F) . γ2 (F, ψ2 ) . γ2 (F, L2 ) 6. Hence
E supf ∈F |Gn f | . γ2 (F, L2 ). Applying the classical multiplier inequality
(5.1) with n0 = 1 we see that for i.i.d. mean-zero multipliers ξ1 , . . . , ξn
independent of samples X1 , . . . , Xn ,
n
1 X
ξi f (Xi ) . kξ1 k2,1 max E sup |Gk (f )|
E sup √
1≤k≤n f ∈F
n
f ∈F
i=1

. kξ1 k2,1 γ2 (F, L2 ) . kξ1 k2,1 E sup |Gf |
f ∈F

where {Gf }f ∈F is the centered Gaussian process indexed by F with covariance structure endowed by the L2 inner product. Here the last inequality
follows from Majorizing Measure Theorem [59]. This recovers Corollary
1.10 of [49] (with a slightly better moment condition on ξi ’s at the cost of a
weaker probability statement).
A basic question for Mendelson’s approach described above, is the sharpness of (5.3).
Proposition 4. Fix any ε > 0, and u ≥ 1, s0 ≥ 0. There exists an integer
n0 ∈ N such that for all n ≥ n0 , we can find a function class F such that
sup |Gn f | ≤ ε · c1 uΛ̃s0 ,u (F)

(5.4)

f ∈F

with probability at least 1 − (c0 + 1) exp(−u2 2s0 /c0 ). The constants c0 , c1 are
taken from (5.3) and its probability estimate.
Compared with (5.4), we see that (5.3) can be arbitrarily loose for some
function class if n is large enough. The major problem here is that the bound
(5.3) is independent of n and hence does not take into account of the Poisson
5A sequence {F } ⊂ F is admissible if |F | = 1 and |F | ≤ 22s .
s
0
s
6For deﬁnition of γ (F, ·), see [59].
2

MULTIPLIER INEQUALITIES

19

(small-sample) behavior of the empirical process. In fact, as n → ∞, the
size of supf ∈F |Gn f | →d supf ∈F |GP f |7 is governed by the Gaussian (largesample) behavior of the empirical process, i.e. the L2 size supf ∈F kf kL2 (P ) ;
while for n = 1 (or small), the quantity supf ∈F |G1 f | is governed by the
Poisson behavior of the empirical process, i.e. the L∞ size of the function
class. Such a discrepancy is actually the key to our construction in the proof
of Proposition 4. In fact any function class with this discrepancy can be
used for the construction. In this sense Proposition 4 shows some difficulties
of the approach of [49] in dealing with function classes whose element-wise
L2 size is much smaller than its L∞ size.
6. Proofs for the main results
6.1. Preliminaries. Let
J(δ, F, L2 ) ≡

(6.1)

Z

δ

sup
0

Q

q

1 + log N (ε kF kQ,2 , F, L2 (Q)) dε

denote the uniform entropy integral, where the supremum is taken over all
discrete probability measures, and
Z δq
(6.2)
1 + log N[ ] (ε, F, k·k) dε
J[ ] (δ, F, k·k) ≡
0

denote the bracketing entropy integral. The following local maximal inequalities for the empirical process play a key role throughout the proof.

Proposition 5. Suppose that F ⊂ L∞ (1), and X1 , . . . , Xn ’s are i.i.d. random variables with law P . Then with F(δ) ≡ {f ∈ F : P f 2 < δ2 },
(1) If the uniform entropy integral (6.1) converges, then


n
X
√
J(δ, F, L2 )
εi f (Xi )
. nJ(δ, F, L2 ) 1 + √ 2
kF kP,2 .
(6.3) E
nδ kF kP,2
i=1

F (δ)

(2) If the bracketing entropy integral (6.2) converges, then


n
X
J[ ] (δ, F, L2 (P ))
√
√ 2
.
. nJ[ ] (δ, F, L2 (P )) 1 +
εi f (Xi )
(6.4) E
nδ
i=1

F (δ)

Proof. (6.3) follows from [67]; see also Section 3 of [22]. (6.4) follows from

Lemma 3.4.2 of [68].
We will primarily work with F ≡ 1 in the above inequalities. A twosided estimate for the empirical process will be important for proving lower
bounds in Theorems 3 and 5. The following definition is taken from [22],
page 1167.
7G

P

is the canonical P -Brownian bridge process.

20

Q. HAN AND J. A. WELLNER

Definition 2. A function class F is α-full (0 < α < 2) if and only if there
exists some constant K1 , K2 > 1 such that both

log N ε kF kL2 (Pn ) , F, L2 (Pn ) ≤ K1 ε−α ,
a.s.
for all ε > 0, n ∈ N, and


log N σ kF kL2 (P ) /K2 , F, L2 (P ) ≥ K2−1 σ −α

hold. Here σ 2 ≡ supf ∈F P f 2 , F denotes the envelope function for F, and
Pn is the empirical measure for i.i.d. samples X1 , . . . , Xn with law P .
The following lemma, giving a sharp two-sized control for the empirical
process under the α-full assumption, is proved in Theorem 3.4 of [22].
Lemma 5. Suppose that F ⊂ L∞ (1) is α-full with σ 2 ≡ supf ∈F P f 2 . If

α/2
√
kF kL (P )
2
&α 1, then there exists some constant
nσ 2 &α 1 and nσ
σ
K > 0 depending only on α, K1 , K2 such that


n
X
kF kL2 (P ) α/2
−1 √
εi f (Xi )
≤E
K
nσ
σ
i=1

√

F

≤ K nσ



kF kL2 (P )
σ

α/2

.

Note that the right side of the inequality can also be derived from (6.3)
(taking supremum over all finitely discrete probability measures only serves
to get rid of the random entropy induced by L2 (Pn ) norm therein).
The following lemma guarantees the existence of a particular type of α-full
class that serves as the basis of the construction in the proof of Theorems 3
and 5.
Lemma 6. Let X , P be as in Theorem 3. Then for each α > 0, there
exists some function class F defined on X which is α-full and contains G ≡
{1[a,b]×[0,1]d−1 : 0 ≤ a ≤ b ≤ 1}.
Proof. Without loss of generality we assume P is uniform on X ≡ [0, 1]d .
1/α
Take F1 = C1 ([0, 1]) to be a 1/α-Hölder class on [0, 1] (see Section 2.7 of
[68]), and define F ≡ {f (x1 , . . . , xd ) := f1 (x1 ) : f1 ∈ F1 }. Let F̃ ≡ F ∪ G.
For any discrete probability measure Q on X = [0, 1]d ,
N (ε, F̃ , L2 (Q)) ≤ N (ε, F, L2 (Q)) + N (ε, G, L2 (Q))

≤ N (ε, F, L∞ ([0, 1]d )) + sup N (ε, G, L2 (Q)),
Q

where the last inequality follows from the fact that any ε-cover of F in L∞
metric on [0, 1]d induces an ε-cover on the function class F under any L2 (Q)
on X . Now by Theorem 2.7.1 of [68] and the fact that G is a bounded
VC-subgraph function class (see Section 2.6 of [68]), we have the following
entropy estimate:
(6.5)

sup log N (ε, F̃ , L2 (Q)) . ε−α .
Q

MULTIPLIER INEQUALITIES

21

where the supremum is taken over all discrete probability measures supported on X . On the other hand, note that
1/α

N (ε, F ∩ L2 (σ; P ), L2 (P )) = N (ε, C1

([0, 1]) ∩ L2 (σ), L2 ([0, 1])).

For ε ≡ cσ for some small c > 0, the latter is bounded from below by
a constant multiple of exp(c′ σ −α ) for another constant c′ > 0, due to the
classical work of [13, 61] in the context of more general Besov spaces. The
1/α
1/α
connection here is C1 ([0, 1]) = B∞,∞ (1) (in the usual notation for Besov
space, see Proposition 4.3.23 of [24]). See also [62], page 103-106 for an
explicit construction for a (local) minimax lower bound in L2 metric for the
Hölder class (which is essentially the same problem), where a set of testing
functions {fi : i ≤ M } is constructed such that M ≥ 2m/8 , kfj − fk kL2 &
m−1/α and kfj kL2 . m−1/α . Hence we see that
log N (cσ, F̃ ∩ L2 (σ; P ), L2 (P )) & σ −α .

(6.6)

The claim follows by combining (6.5) and (6.6).



6.2. Proof of Theorem 1.
Proof of Proposition 1. We will omit F in the proof. We first consider the
condition (A1). Note that for (X1′ , . . . , Xn′ ) being an independent copy of
(X1 , . . . , Xn ), we have
E

n
X

ξi f (Xi ) = Eξ,X

n
X
i=1

i=1

ξi f (Xi ) −

EX ′ f (Xi′ )



≤E

n
X
i=1


ξi f (Xi ) − f (Xi′ ) .

Here in the first equality we used the centeredness assumption on the function class F in (A1). Now conditional
on ξ, for fixed ε1 , . . . , εn , the map
Pn
′
(X1 , . . . , Xn , X1′ , . . . , Xn′ ) 7→
ξ
ε
is a permutation
i=1 i i f (Xi ) − f (Xi )
of the original map (without εi ’s). Since (X1 , . . . , Xn , X1′ , . . . , Xn′ ) is the
coordinate projection of a product measure, it follows by taking expectation
over ε1 , . . . , εn that
(6.7)
n
n
X
X


EX,X ′
ξi εi f (Xi ) − f (Xi′ ) .
ξi f (Xi ) − f (Xi′ ) = Eε,X,X ′
i=1

i=1

This entails that
(6.8)
n
n
n
X
X
X
|ξi | εi f (Xi )
|ξi | sgn(ξi )εi f (Xi ) = 2E
ξi f (Xi ) ≤ 2Eξ,ε,X
E
i=1

i=1

i=1

where the equality follows since the random vector (sgn(ξ1 )ε1 , . . . , sgn(ξn )εn )
has the same distribution as that of (ε1 , . . . , εn ) and is independent of
ξ1 , . . . , ξn . We will simply write |ξi | without the absolute value in the sequel

22

Q. HAN AND J. A. WELLNER

for notational convenience. Let π be a permutation over {1, . . . , n} such
that ξi = ξ(π(i)) . Then the right hand side of (6.8) equals
(6.9)
n
n
X
X
(by relabelling)
ξ(i) επ−1 (i) f (Xπ−1 (i) )
ξ(π(i)) εi f (Xi ) = E
E
i=1

i=1

n
X

=E

ξ(i) εi f (Xi )

i=1

P

(by invariance of (PX ⊗ Pε )n ).

Now write ξ(i) = k≥i (ξ(k) − ξ(k+1) ) where ξ(n+1) ≡ 0. The above display
can be rewritten as
(6.10)
n
n
k
n X
X
X
X
εi f (Xi ) .
(ξ(k) − ξ(k+1) )
(ξ(k) − ξ(k+1) )εi f (Xi ) = E
E
i=1 k=i

i=1

k=1

The claim under (A1) follows by combining (6.8)-(6.10). For (A2), let ξi′ ’s
be an independent copy of ξi ’s. Then the analogy of (6.8) becomes
E

n
X

ξi f (Xi ) = E

i=1

=E

n
n
X
X
(ξi − ξi′ )f (Xi )
(ξi − Eξi′ )f (Xi ) ≤ E
i=1
n
X
i=1

εi ξi − ξi′ f (Xi ) = E

i=1
n
X
i=1

εi |ηi | f (Xi )

where ηi ≡ ξi − ξi′ . The claim for (A2) follows by repeating the arguments
in (6.9) and (6.10).

Proof of Theorem 1. First consider (A1). Using Proposition 1 we see that,


n
n
k
X
X
X
.
ξi f (Xi )
≤ 2E  ( ξ(k) − ξ(k+1) )E
εi f (Xi )
(6.11) E
i=1

i=1

k=1

Fn

Fn

By monotonicity of the function classes {Fk }, for any 1 ≤ k ≤ n,
(6.12)

E

k
X

εi f (Xi )

i=1

Fn

≤E

k
X
i=1

εi f (Xi )
Fk

≤ ψn (k).

Collecting (6.11)-(6.12), we see that
" n
#
n
n Z |ξ(k) |
X
X
X
≤ 2E
ξi f (Xi )
( ξ(k) − ξ(k+1) )ψn (k) = 2E
ψn (k) dt
E
i=1
k=1
k=1 |ξ(k+1) |
Fn
Z ∞
Z ∞

ψn nΓξn (t) dt
ψn (|{i : |ξi | ≥ t}|) dt ≤ 2
≤ 2E
0

0

where the last inequality follows from Fubini’s theorem and Jensen’s inequality, completing the proof for the upper bound for (A1). For (A2), mimicing

MULTIPLIER INEQUALITIES

the above proof, we have
Z ∞
n
X
≤
ψn
ξi f (Xi )
E
i=1

0

Fn

≤

Z

∞

=

Z

∞

ψn

0

ψn

0

n
X

P(

i=1

n
X

ξi − ξi′

!

≥ t)

23

dt
!

P(|ξi | ≥ t/2) + P( ξi′ ≥ t/2)

i=1
n
X

2

i=1

!

P(|ξi | ≥ t/2)

dt = 2

Z

∞
0

dt


ψn 2nΓξn (t) dt.

The proof of the claim for (A2) is complete by noting that ψn (2x) ≤ 2ψn (x)
due to the concavity of ψn and ψn (0) = 0.


6.3. Proof of Theorem 3. We first outline the proof strategy. The proof
contains two main steps:
(1) First we show that the size of the multiplier empirical process always
majorizes the corresponding empirical process (Lemma 7), whose
size from below can be obtained, if entropy control both from above
and below is possible. We construct some function class F̃ with this
property for each level γ > 2, yielding the lower bound n1/γ .
(2) The second step aims at a lower bound n1/p . The ideaPis to add to F̃
some ‘least favorable functions’ G such that E supf ∈G | ni=1 ξi f (Xi )| ≈
E max1≤i≤cn |ξi | & n1/p for some constant c > 0 independent of n.
In order to maintain the upper entropy estimate in the first step, G
needs to be chosen ‘small’ enough.
Lemma 7. Suppose that ξ1 , . . . , ξn are i.i.d. random variables independent
of i.i.d. X1 , . . . , Xn . Then
kξ1 k1 E

n
X
i=1

εi f (Xi )
F

≤ 2E

n
X
i=1

ξi f (Xi )

.
F

Proof. Let X1′ , . . . , Xn′ be independent copies of X1 , . . . , Xn . Then the left
hand side of the above display can be bounded by
(6.13)
n
n
X
X
′
εi |ξi | (f (Xi ) − f (Xi′ )) .
εi (f (Xi ) − f (Xi )) ≤ E
kξ1 k1 E
i=1

i=1

Using arguments similar to (6.8), the |ξi |’s in the above display can be
replaced by ξi ’s. The Rademacher εi ’s can be deleted using arguments in
(6.7), thereby completing the proof by further using triangle inequality. 
Lemma 8. Let X1 , . . . , Xn be i.i.d. random variables distributed on [0, 1]d
with a probability law P admitting a Lebesgue density bounded away from
∞. Let {Ii }ni=1 be a partition of [0, 1]d such that Ii ∩ Ij = ∅ for i 6= j and

24

Q. HAN AND J. A. WELLNER

∪ni=1 Ii = [0, 1]d , and L−1 n−1 ≤ |Ii | ≤ Ln−1 for some absolute value L > 0.
Then there exists some τ ≡ τL,P ∈ (0, 1) such that for n large enough,
P (X1 , . . . , Xn lie in at most τ n intervals among {Ii }ni=1 ) ≤ 0.5n .

Proof. Note that the event in question equals
∪|I|=τ n {X1 , . . . , Xn ∈ ∪i∈I Ii } .
With K ≡ supx∈[0,1]d |(dP/dλ)(x)|, the above display implies that the probability in question can be bounded by
 
in
h e τ
n
n
· τ LK .
τ n · Ln−1 · K ≤ exp (τ n log(e/τ )) · (τ LK)n =
τ
τn

τ
Since τe · τ → 0 as τ → 0, it suffices to choose τ > 0 small enough.

Now we are in position to prove Theorem 3.

Proof of Theorem 3. As in the proof outline, the proof will proceed in two
steps. The first step aims at establishing a lower bound for the multiplier
empirical process on the order of n1/γ .
Let α = 2/(γ − 1), and F̃ be an α-full class on X in Lemma 6. Further
let δk = k−1/(2+α) and F̃k ≡ F̃ (δk ) = {f ∈ F̃ : P f 2 < δk2 }. Then it follows
from Lemma 5 that there exists some constant K > 0,
k
X

K −1 kα/(2+α) ≤ E

εi f (Xi )

i=1

F̃k

≤ Kkα/(2+α) .

P
Lemma 7 now guarantees that E k ni=1 ξi f (Xi )kF̃n can be bounded from
below by a constant multiple of nα/(2+α) = n1/γ where the constant depends
on kξ1 k1 . This completes the first step of the proof.
In the second step, we aim at establishing a lower bound of order n1/p . To
this end, let {Ij }nj=1 be a partition of X such that L−1 n−1 ≤ |Ij | ≤ Ln−1 .
On the other hand, let fj ≡ 1Ij ∈ F̃n for 1 ≤ j ≤ n (increase δn by constant
factors if necessary), and En denote the event that X1 , . . . , Xn lie in N ≥ τ n
sets among {Ij }nj=1 . Then Lemma 8 entails that P(En ) ≥ 1 − 0.5n ≥ 1/2 for
n large enough. Furthermore, let Ij ≡ {i : Xi ∈ Ij } and pick any Xι(j) ∈ Ij .
Note that Ij ’s are disjoint, and hence conditionally on X we have
E max |ξj | ≤ E max ξι(j)
1≤j≤τ n

(by i.i.d. assumption on ξi ’s)

1≤j≤N

≤ E max ξι(j) + E
1≤j≤N

≤ E max

1≤j≤N

X

i∈Ij

ξi

X

ξi

(Ij ’s are disjoint and Eξi = 0)

i∈Ij \ι(j)

(by Jensen’s inequality).

MULTIPLIER INEQUALITIES

25

Then
n
X

E

ξi f (Xi )

i=1

F̃n



≥ E max

1≤j≤n



n
X



ξi fj (Xi )

i=1



= EX Eξ max

≥ EX Eξ max |ξj | 1En ≥
1≤j≤τ n



1≤j≤N

1
Eξ max |ξj |
2 1≤j≤τ n

X

i∈Ij



ξi 1En 

for n large enough. Now the second step follows from the assumption, and
hence completing the proof.

6.4. Proof of Theorem 4. We first prove Proposition 2.
Proof of Proposition 2. Let
Mn f =

n

n

i=1

i=1

1X
2X
(f − f0 )(Xi )ξi −
(f − f0 )2 (Xi ), M f = −P (f − f0 )2 .
n
n

Here we used the fact that Eξi = 0 and the independence assumption between {ξi } and {Xi }. Then it is easy to see that
n

2X
(f − f0 )(Xi )ξi + (Pn − P )(f − f0 )2 .
|Mn f − Mn f0 − (M f − M f0 )| ≤
n
i=1

The first claim follows by standard symmetrization and contraction principle
for the empirical process indexed by a uniformly bounded function class,
followed by an application of Theorem 3.2.5 of [68].
Now assume that ξ1 , . . . , ξn are i.i.d. mean-zero errors with kξ1 kp < ∞
for some p ≥ 2. Fix t ≥ 1. For j ∈ N, let Fj ≡ {f ∈ F : 2j−1 tδn <
kf − f0 kL2 (P ) ≤ 2j tδn }. Then by a standard peeling argument, we have
!

 X
≥ tδn ≤
P fˆn − f0
P sup (Mn (f ) − Mn (f0 )) ≥ 0 .
L2 (P )

j≥1

f ∈Fj

Each probability term in the above display can be further bounded by
!
P

sup (Mn (f ) − Mn (f0 ) − (M f − M f0 )) ≥ 22j−2 t2 δn2

f ∈Fj



≤ P


n
X
√
1
√
ξi f (Xi ) ≥ 22j−4 t2 nδn2 
n

sup

f ∈F −f0 :kf kL

2 (P )



+ P

≤2j tδn

i=1

sup

f ∈F −f0 :kf kL

2 (P )

≤2j tδn


n
X
√
1
√
εi f 2 (Xi ) ≥ 22j−3 t2 nδn2  .
n
i=1

26

Q. HAN AND J. A. WELLNER

By contraction principle and moment inequality for the empirical process
(Lemma 1), we have

2
2


E


sup

f ∈F −f0 :
kf kL (P ) ≤2j tδn
2

n


1 X
√
ξi f (Xi ) 
∨ E


n

sup

f ∈F −f0 :
kf kL (P ) ≤2j tδn

i=1

2

n

1 X
√
εi f 2 (Xi ) 

n
i=1


2
. φn (2j tδn ) + (1 ∨ kξ1 k2 )2 22j t2 δn2 + (1 ∨ kξ1 kp )2 n−1+2/p .

In the above calculation we used the fact that E max1≤i≤n |ξi |2 ≤ kξ1 k2p n2/p
under kξ1 kp < ∞. By Chebyshev’s inequality,
"
#


X  φn (2j tδn ) 2
1
1
ˆ
√
∨ 2j 2 2 ∨ 4j 4 2−2/p 4 .
≥ tδn ≤ Cξ
P fn − f0
2 t nδn 2 t n
22j t2 nδn2
L2 (P )
δn
j≥1

−1+

1

Under the assumption that δn ≥ n 2 2p , and noting that φn (2j tδn ) ≤
2j tφn (δn ) by the assumption that δ 7→ φn (δ)/δ is non-increasing, the right
side of the above display can be further bounded up to a constant by
X  φn (δn ) 2
1
1
√ 2
+ 2 . 2
j
2 t nδn
t
t
j≥1

for t ≥ 1. The expectation bound follows by integrating the tail estimate.

The following lemma calculates an upper bound for the multiplier empirical process at the target rate in Theorem 4.

Lemma 9. Suppose that Assumption A holds with i.i.d. X1 , . . . , Xn ’s with
law P , and F ⊂ L∞ (1) satisfies Assumption B with α ∈ (0, 2). Further
assume for simplicity that ξi ’s have the same marginal distributions with
1
−1+ 1
kξ1 kp,1 < ∞. Then with δn ≡ n− 2+α ∨ n 2 2p , we have
E

n
X

sup

2
P f 2 ≤ρ2 δn
i=1

1−α/2

≤ K̄α (ρ

ξi f (Xi ) ∨ E

∨ρ

−α

sup

n
X

2
P f 2 ≤ρ2 δn
i=1

εi f (Xi )

( α

n 2+α 1 ∨ kξ1 k1+2/α,1 ,
)
1

n p 1 ∨ kξ1 kp,1 ,

p ≥ 1 + 2/α,

1 ≤ p < 1 + 2/α.

1

Proof. If p ≥ 1 + 2/α, then δn = n− 2+α . By local maximal inequalities for
empirical processes (see Proposition 5), we have
!
k
X
√
(ρδk )1−α/2
1−α/2
1∨ √
εi f (Xi ) ≤ C k(ρδk )
E sup
k(ρδk )2
P f 2 ≤ρ2 δk2 i=1
(6.14)
α
≤ Ck 2+α ρ1−α/2 (1 ∨ ρ−(1+α/2) )
α

≤ C(ρ1−α/2 ∨ ρ−α ) · k 2+α .

MULTIPLIER INEQUALITIES

27

Applying Theorem 2 we see that
E

sup

n
X

2
P f 2 ≤ρ2 δn
i=1


α
ξi f (Xi ) ≤ C(ρ1−α/2 ∨ ρ−α ) · n 2+α 1 ∨ kξ1 k1+2/α,1 .
1

1

If p < 1 + 2/α, then δn = n− 2 + 2p . In this case,
(6.15)
!
k
1−α/2
X
√
(ρδ
)
k
E sup
εi f (Xi ) ≤ C k(ρδk )1−α/2 1 ∨ √
2
2
2
2
k(ρδ
P f ≤ρ δk i=1
k)




1 1
1 α p−1
1
+α
· p−1
1−α/2
−(1+α/2) 2 − p + 2 · p
2 p
2
p
≤ Cρ
·k
1+ρ
k
1

≤ C(ρ1−α/2 ∨ ρ−α )k p

where the last inequality follows from p1 > α2 · p−1
p by the assumed relationship
between p and α. Now apply Theorem 2 we have
sup

E

n
X

2
P f 2 ≤ρ2 δn
i=1

as desired.

1

ξi f (Xi ) ≤ C(ρ1−α/2 ∨ ρ−α ) · n p (kξ1 kp,1 ∨ 1)


Proof of Theorem 4. The claim follows immediately from Lemma 9 by noting that the rate δn chosen therein corresponds to the condition (3.3) in
Proposition 2, along with Proposition 5 handling (3.4).

6.5. Proof of Theorem 5.
6.5.1. The strategy. The proof of Theorem 5 is technically rather involved;
here we give a brief outline. There are mainly two steps:
(1) We first show that (see Lemma 10): the risk of some LSE corresponds to the extreme value δn∗ of the map
(6.16) δ 7→ Fn (δ) ≡

sup
f ∈F −f0

:P f 2 ≤δ2

(Pn − P )(2ξf − f 2 ) − δ2 ≡ En (δ) − δ2 .

This step is similar in spirit to [16, 66] (e.g. Theorem 1.1 of [16];
Lemma 3.1 of [66]); we will deal with the fact that the LSE may not
be unique, and the map does not enjoy good geometric properties
such as convexity in [16], or uniqueness of the extreme value of the
map (6.16) as in [66].
(2) Step 1 reduces the problem of finding δn∗ to that of finding δ1 < δ2
such that En (δ1 ) < Fn (δ2 ) [This means, Fn (δ) < Fn (δ2 ) for δ ≤ δ1 ,
implying that the extreme value δn∗ ≥ δ1 ]. Hence our task will be
to find δ1 , δ2 with matching order such that En (δ1 ) is smaller than
Fn (δ2 ) up to a constant order under a specific function class. The
construction of such an underlying regression function is inspired
by the one used in Theorem 3. The main technical job involves (i)
developing a problem-specific approach to derive an upper bound

28

Q. HAN AND J. A. WELLNER

for En (ρδ1 ) for small ρ > 0 (corresponding to the Poisson (smallsample) domain of the empirical process where general tools fail),
(ii) using a Paley-Zygmund moment argument to produce a sharp
lower bound for Fn (δ2 ) and (iii) handling the delicate fact that the
Lp,1 norm is slightly stronger than the Lp norm.
6.5.2. The reduction scheme.
Lemma 10. Fix ε > 0. Let δn∗ ≡ inf{δ∗ ≥ 0 : Fn (δ∗ ) ≥ supδ∈[0,∞) Fn (δ)−ε}.
Then there exists a 2ε-approximate LSE fn∗ such that
kfn∗ − f0 k2L2 (P ) ≥ (δn∗ )2 − ε.
Proof. Without loss of generality we assume f0 = 0. Let fn∗ be such that
δ02 ≡ P (fn∗ )2 ≤ (δn∗ )2 and En (δn∗ ) ≤ (Pn − P )(2ξfn∗ − (fn∗ )2 ) + ε. Note that
for any f ∈ F,
(Pn − P )(2ξf − f 2 ) − P f 2 ≤ Fn (kf kL2 (P ) ) ≤ Fn (δn∗ ) + ε
= En (δn∗ ) − (δn∗ )2 + ε

≤ (Pn − P )(2ξfn∗ − (fn∗ )2 ) − P (fn∗ )2 + 2ε,

where in the last inequality we used the definition of fn∗ and the fact that
(δn∗ )2 ≥ P (fn∗ )2 . This implies that for any f ∈ F,
kY − f k2n = Pn ξ 2 − Pn (2ξf − f 2 )

≥ Pn ξ 2 − Pn (2ξfn∗ − (fn∗ )2 ) − 2ε = kY − fn∗ k2n − 2ε.

Hence fn∗ is a 2ε-approximate LSE. The claim follows if we can show δ02 ≥
(δn∗ )2 − ε. This is valid: if (δn∗ )2 > δ02 + ε, then
Fn (δ0 ) ≥ (Pn − P )(2ξfn∗ − (fn∗ )2 ) − δ02

≥ En (δn∗ ) − ε − δ02 = Fn (δn∗ ) − ε + ((δn∗ )2 − δ02 ) > Fn (δn∗ ),

a contradiction to the definition of δn∗ by noting that δ0 ≤ δn∗ .



Since ε > 0 in Lemma 10 can be arbitrarily small, in the following analysis
we will assume without loss of generality that ε = 0.
The following simple observation summarizes the strategy for finding a
lower bound on the rate of some least squares estimator.
Proposition 6. Suppose that 0 < δ1 < δ2 are such that En (δ1 ) < Fn (δ2 ).
Then there exists a LSE fn∗ such that kfn∗ − f0 kL2 (P ) ≥ δ1 .
Proof. The condition implies that Fn (δ) = En (δ) − δ2 ≤ En (δ) ≤ En (δ1 ) <
Fn (δ2 ) for any δ ≤ δ1 and hence a maximizer δn∗ of the map δ 7→ Fn (δ)
cannot lie in [0, δ1 ], i.e. δn∗ ≥ δ1 . The claim now follows by Lemma 10. 
In the next few subsections, we first prove claim (1) of Theorem 5. The
proof of claim (2) follows the similar proof strategy as that of claim (1); the
details will be delayed until the last subsection.

MULTIPLIER INEQUALITIES

29

6.5.3. Upper bound. The regression function class F we consider will be the
Hölder class constructed in Lemma 6 with X = [0, 1]d , and f0 ≡ 0. We
first handle the upper bound part of the problem. Lemma 9 is awkward in
this regard because general tools (Proposition 5) cannot handle the Poisson
(small-sample) domain of the empirical process, and hence the resulting
bound is insensitive with respect to small ρ > 0. The following lemma
remedies this for our special function class F.

Lemma 11. Suppose that X = [0, 1]d and P is a probability distribution on
X with Lebesgue density bounded away from 0 and ∞. Suppose ξi ’s are i.i.d.
mean-zero and kξ1 kp,1 < ∞. Suppose p ≥ 1 + 2/α. Then for any ρ ∈ (0, 1),
if
n ≥ min{n ≥ 3 : ρ2 ≥ log n(n−α/(2+α) )},

(6.17)

1

then with δn ≡ n− 2+α we have,
E

sup

n
X

2
f ∈F :P f 2 ≤ρ2 δn
i=1

2ξi f (Xi ) − f 2 (Xi ) + P f 2



α

≤ K̄P,α ρ1−α/2 n 2+α (1 ∨ kξ1 kp,1 ).

Note that in the above lemma we may choose ρ small as long as the sample
size condition (6.17) is satisfied. The key idea of the proof is to compare
supf ∈F :P f 2 <σ2 Pn f 2 with σ 2 directly for (nearly) the whole range of σ 2
including the Poisson (small-sample) domain by exploiting the geometry of
F. To this end we need the following.
Lemma 12. Let X1 , . . . , Xn be i.i.d. P on [0, 1] where P has Lebesgue
density bounded away from 0 and ∞. Set γn = κP log n/n where κP ≥ 1
is a constant large enough depending only on P . Let Ij ≡ [(j − 1)γn , jγn )
for j = 1, . . . , n/(κP log n) ≡ N . Then for some cP > 0, nP large enough
depending on P , if n ≥ nP , with probability at least 1 − 2n−2 , all intervals
{Ij } contain at least one and at most cP log n samples.
Proof. Without loss of generality we assume that P is uniform on [0, 1].
The general case where P has Lebesgue density bounded away from 0 and
∞ follows from minor modification. Let E1 (E2 ) be the event that all intervals
{Ij } contain at least one sample(at most c log n samples). Then for κP = 6,
P (E1c ) = P (∪1≤j≤N {Ij contains no samples})


κP log n n
≤ N e−κP log n ≤ n−5 .
≤N · 1−
n
On the other hand,
!
n
X
c
P(E2 ) = P max
1Ij (Xi ) > c log n
1≤j≤N

≤

N
X
j=1

P

i=1

n
X
i=1

1Ij (Xi ) − γn



!

> (c − 6) log n .

30

Q. HAN AND J. A. WELLNER

Now P
we use Bernstein inequality
following form (cf. (2.10) of [9]): for
P in the
2 where |Z | ≤ b for all 1 ≤ i ≤ n, we
S = ni=1 (Zi − EZi ), v = ni=1 EZ
i
 i
2

t
. We apply this with Zi ≡ 1Ij (Xi ) and
have P(S > t) ≤ exp − 2(v+bt/3)
Pn
hence γn = EZi and v = i=1 γn = 6 log n, b = 1, to see that right side of
the above display can be further bounded by


N
X
(c − 6)2 log2 n
exp −
≤ N e−3 log n ≤ n−2
2(6 log n + (c − 6) log n/3)
j=1

by choosing c = 13. Combining two cases we have completed the proof. 

We also need Dudley’s entropy integral bound, recorded below for the
convenience of the reader.
Lemma 13 ([21]). Let (Xt )t∈T be a centered separable Gaussian process,
and kt − sk2 := E(Xt − Xs )2 . Then
Z diam(T ) q
log N (ε, T, k·k) dε.
E sup Xt ≤ C
t∈T

0

Here C is a universal constant.

Proof of Lemma 11. By the contraction principle, we only need to handle
E

sup

n
X

2
P f 2 ≤ρ2 δn
i=1

ξi f (Xi ) ,

E

sup

n
X

2
P f 2 ≤ρ2 δn
i=1

εi f (Xi ) .

Let F be the Hölder class constructed in Lemma 6. We first claim that on
an event En with probability at least 1 − 2n−2 , for any f ∈ F,


log n
2
2
.
(6.18)
Pn f ≤ cP P f +
n

To see this, we only need to consider the first dimension by definition of F.
By Lemma 12, we see that on an event En with probability at least 1 − 2n−2 ,
n
N
N
1X 2
1X X 2
1X
f (Xi ) =
f (Xi ) ≤
cP log n · max f 2 (Xi ).
Xi ∈Ij
n
n
n
i=1

j=1 Xi ∈Ij

j=1

Here N = n/(κP log n) is the number of intervals {Ij }. The trick now is
to observe that since f is at least 1/2-Hölder, we have maxXi ∈Ij f (Xi ) ≤
√
minx∈Ij f (x) + γn , where γn = κP log n/n is the length for each interval
Ij . Hence on the same event as above, the right side of the above display
can be further bounded by

N
N 
2cP log n
2cP X
2cP log n X
2
γn min f 2 (x) +
min f (x) + γn =
x∈Ij
x∈Ij
n
κP
n
j=1
j=1
Z
2cP log n
2cP 1 2
f (x) dx +
,
≤
κP 0
n

MULTIPLIER INEQUALITIES

31

where the inequality follows from the definition of Riemann integral. The
claim (6.18) is thus proven by noting that the intergal in the above display
is equivalent to P f 2 up to a constant depending on P only. Now using
Dudley’s entropy integral (see Lemma 13) and (6.18), we have for the choice
p
1
σn = ρ(n− 2+α ) ≥ log n/n [the inequality holds when n ≥ min{n ≥ 3 :
ρ2 ≥ log n(n−α/(2+α) )}],
n

1 X
√
εi f (Xi )
n

sup

E

2
f ∈F :P f 2 ≤σn

i=1

Z 2√supf ∈F Pn f 2 p

≤ CE
0
Z √
2

2 +log n/n)
cP (σn

.

0

Since

√

ρ2
2
n 2+α



ε−α/2 dε + J(∞, F, L2 )P(Enc ) .P,α σn1−α/2 + n−2 .

α
1 1 2−α
√
= ρ1−α/2 n 2 − 2 2+α = ρ1−α/2 n 2+α and n · n−2 ≤ n−1 ≤
α
≤ ρ2 ≤ ρ1−α/2 n 2+α , in this case Theorem 2 along with the

1−α/2

nσn

(log n)2

log N (ε, F, L2 (Pn )) dε

assumption p ≥ 1 + 2/α yields that
sup

E

n
X

2
f ∈F :P f 2 ≤σn
i=1

α

α

ξi f (Xi ) .P,α ρ1−α/2 n 2+α kξ1 k1+2/α,1 ≤ ρ1−α/2 n 2+α kξ1 kp,1 .

The proof is complete.



6.5.4. Lower bound. Next we turn to the lower bound part of the problem.
We will first consider a lower bound in expectation, then a Paley-Zygmund
type argument translates the claim from in expectation to in probability.
Lemma 14. Let X = [0, 1]d , and P be a probability measure on X with
Lebesgue density bounded away from 0 and ∞. Let ξ1 , . . . , ξn be i.i.d. meanzero random variables such that kξ1 k1 > 0, and F be the Hölder class con1

structed in Lemma 6. Then with δn ≡ n− 2+α , if kξ1 k1 > Kα,P and ϑ ≥ 1
for some Kα,P > 0 depending only on α, P ,
E

sup

n
X

2
P f 2 ≤ϑ2 δn
i=1

2ξi f (Xi ) − f 2 (Xi ) + P f 2



α

≥ K P,α kξ1 k1 ϑ1−α/2 · n 2+α .

Proof. By Lemmas 5 and 7, and the α-fullness of F̃ , we have
E

sup

n
X

2
P f 2 ≤ϑ2 δn
i=1

ξi f (Xi ) ≥

n
X
α
1
εi f (Xi ) ≥ C1 kξ1 k1 ϑ1−α/2 n 2+α .
kξ1 k1 E sup
2
2
P f 2 ≤ϑ2 δn
i=1

32

Q. HAN AND J. A. WELLNER

On the other hand, during the proof of Lemma 9 (see (6.14)) we see that
α
Pk
2
1−α/2 ∨1)·n 2+α . By de-symmetrization,
E supP f 2 ≤ϑ2 δ2
i=1 εi f (Xi ) ≤ C2 (ϑ
k

sup

E

k
X

P f 2 ≤ϑ2 δk2 i=1

α

(f 2 (Xi ) − P f 2 ) ≤ 2C2 (ϑ1−α/2 ∨ 1) · n 2+α .

Here C1 , C2 are constants depending on α, P only. Now for kξ1 k1 ≥ 2C2 /C1 ,
since ϑ ≥ 1, by the triangle inequality we see that
E

sup

n
X

2
P f 2 ≤ϑ2 δn
i=1

as desired.

2ξi f (Xi ) − f 2 (Xi ) + P f 2



α

≥ C1 kξ1 k1 ϑ1−α/2 n 2+α ,


The following Paley-Zygmund lower bound is standard.
Lemma 15 (Paley-Zygmund). Let Z be any non-negative random variable.
q′

(1−ε)EZ
, where q, q ′ ∈ (1, ∞) are
Then for any ε > 0, P(Z > εEZ) ≥ (EZ
q )1/q
conjugate indices: 1/q + 1/q ′ = 1.

Now we turn the lower bound in expectation in Lemma 14 to a probability
bound by a Paley-Zygmund argument.
Lemma 16. Consider
as in Lemma 14 with p ≥ 2, and let
Pn the same setup
2 (X ) + P f 2 . Suppose p ≥ 1 + 2/α. If
Z = supP f 2 ≤ϑ2 δn2
2ξ
f
(X
)
−
f
i
i
i
i=1
kξ1 kp < ∞, kξ1 k1 > Kα , ϑ ≥ 1 and 1 < q ≤ p. Then


α
1
−1/(q−1)
1−α/2
2+α
·n
≥ 2−q/(q−1) L̄α,ξ,ϑ,q,P > 0.
P Z ≥ K P,α kξ1 k1 ϑ
2
The constant in the probability estimate is defined in (6.19) below.
α

Proof. Lemma 14 entails that EZ ≥ K P,α kξ1 k1 ϑ1−α/2 · n 2+α . By the moment inequality Lemma 1, if ξi ’s have finite p-th moments, and q ≤ p,
(6.19)


√
EZ q
1 ∨ E max1≤i≤n |ξi |q
( n(kξ1 k2 ∨ 1)ϑδn )q
≤ Cq 1 +
+
(EZ)q
(EZ)q
(EZ)q

−q
≤ Cq 1 + 2 K P,α kξ1 k1 ∧ 1



q
− qα
− qα
× ϑαq/2 (kξ1 k2 ∨ 1)q n 2(2+α) ∨ ϑq(α/2−1) kξ1 kqp n p 2+α
i
h
−q αq/2
ϑ
(kξ1 kp ∨ 1)q ≡ L̄α,ξ,ϑ,q,P .
≤ Cq 1 + 2 K P,α kξ1 k1 ∧ 1

In the second inequality we used kmaxi |ξi |kq ≤ kmaxi |ξi |kp ≤ n1/p kξ1 kp ,
and the third inequality follows by noting ϑ ≥ 1 and the assumption p ≥
1 + 2/α. The proof is complete.


MULTIPLIER INEQUALITIES

33

6.5.5. Putting the pieces together.
Proposition 7. Suppose kξ1 kp,1 < ∞ for p ≥ max{2, 1 + 2/α}. If kξ1 k1 >
Kα,P for some (large) constant Kα,P > 0, then for n large enough, there
exist constants ρξ,α,P < ϑξ,α,P such that on an event with positive probability
p1 = p1 (α, ξ, P ) > 0 independent of n,




1
1
Fn ϑξ,α,P · n− 2+α > En ρξ,α,P · n− 2+α .

Proof. Lemma 11 and Markov’s inequality entail that for any ρ > 0, if
n ≥ min{n ≥ 3 : ρ2 ≥ log n(n−α/(2+α) )}, then on an event with probability
at least 1 − 1/M ,
(6.20)

α

nEn (ρδn ) ≤ M C̄ξ,α,P · ρ1−α/2 n 2+α .

We will choose ρ, M later on. On the other hand, apply Lemma 16 with
2
q = 2 (since p ≥ 2) and ϑ = (K P,α kξ1 k1 /4) 2+α (we may increase kξ1 k1 to
ensure ϑ ≥ 1 if necessary) we see that on an event with probability at least
2p1 ≡ 2p1 (α, ξ, P ), we have
α
α
1
nFn (ϑδn ) ≥ K P,α kξ1 k1 ϑ1−α/2 · n 2+α − ϑ2 n 2+α
2
(6.21)
α
α
1
≥ K P,α kξ1 k1 ϑ1−α/2 · n 2+α ≡ C ξ,α,P · n 2+α .
4
First we choose M = 1/p1 so that with probability at least p1 , (6.20) and
2
(6.21) hold simultaneously. Then we choose ρ = min{(p1 C ξ,α,P /2C̄ξ,α,P ) 2−α , ϑ/2}
to conclude Fn (ϑδn ) > En (ρδn ) with probability at least p1 .

Now we have completed the program outlined in Proposition 6.
Proof of Theorem 5: claim (1). Recall that the regression function class is
taken from Lemma 6 with f0 ≡ 0. Combining the proof outline Proposition
6, with Proposition 7, we see that there exists an event with probability at
least p1 = p1 (α, ξ, P ) > 0, on which at least one least squares estimator fn∗
1
over F satisfying kfn∗ − f0 kL2 (P ) ≥ ρ · n− 2+α , where ρ > 0 is a (small) constant independent of n. The claim now follows by bounding the expectation
from below on this event.

6.5.6. Proof of the remaining claim. In this subsection we prove the second
claim of Theorem 5. Without loss of generality, we only consider d = 1, and
the probability measure P is assumed to be uniform for simplicity. To this
end, let F̃ ≡ F̃n ≡ {1[a,b] : a, b ∈ [0, 1] ∩ Q, b − a ≥ δn2 } ∪ {0} and f0 = 0,
′
where δn = ρn−1/2+1/2p with 1p − p1′ = ε for some numeric constants ε, ρ > 0
to be specified later.
In the current case En (δ) = 0 for δ < δn and hence our goal is to give a
lower bound for Fn (δn ). We mimic the proof strategy of the first claim of
Theorem 5 by (i) giving a lower bound for the multiplier empirical process
in expectation, and then (ii) using the Paley-Zygmund moment argument

34

Q. HAN AND J. A. WELLNER

to translate the lower bound in probability. The arguments are somewhat
delicate due to the fact that the Lp,1 norm is stronger than the Lp norm.
P
For notational simplicity, let Z ≡ supf ∈F̃n :P f 2 ≤δ2 | ni=1 ξi f (Xi )|, and Z̃ ≡
n
Pn
2
2
supf ∈F̃n :P f 2 ≤δ2
i=1 2ξi f (Xi ) − f (Xi ) + P f .
n

Lemma 17. Suppose ρ ≤ (64/e3 )1/6 and ξ1 , . . . , ξn are i.i.d. mean-zero
random variables. Then for n ≥ 2, we have EZ ≥ 21 E max1≤j≤4−1 n1−1/p′ |ξj | .

Proof. Let Ij ≡ [(j − 1)δn2 , jδn2 ] ⊂ [0, 1] for j = 1, . . . , N where N = δn−2 ≤
ρ−2 n. Note that for any c ∈ (0, 1),

P X1 , . . . , Xn lie in at most cN intervals among {Ij }N
j=1

= P ∪|I|=cN {X1 , . . . , Xn ∈ ∪i∈I Ii }
 
−2
N n
≤
c ≤ ecN log(e/c)−n log(1/c) ≤ e(cρ log(e/c)−log(1/c))n .
cN

By choosing c = ρ2 /4, the exponent in the above display can be further
bounded by 41 log(e/c) − log(1/c) = 41 log(c3 e) = 14 log(eρ6 /64) ≤ − 12 where
the last inequality follows by the assumption that ρ ≤ (64/e3 )1/6 . Hence we
conclude that on an event E with probability at least 1 − 0.61n , the samples
X1 , . . . , Xn must occupy at least ρ2 N/4 many intervals among {Ij }N
j=1 . This
implies that
EZ = E

sup

n
X

2
f ∈F̃n :P f 2 ≤δn
i=1

ξi f (Xi ) ≥ E max

1≤j≤N

X

i∈Ij

ξi 1Ij (Xi ) 1E ≥

1
E max |ξj |
2 1≤j≤ρ2 N/4

where we used the same arguments as in the proof of Theorem 3. The claim
′

now follows by noting ρ2 N/4 = ρ2 δn−2 /4 = n1−1/p /4.
Lemma 18. Suppose that ξ1 , . . . , ξn are i.i.d. symmetric random variables
′
with P(|ξ1 | > t) = 1/(1 + |t|p ). Further suppose that ρ ≤ (64/e3 )1/6 ,
−1/2 ∨ 3 ≤ p ≤ log n/ log log n and n ≥ min{n ≥ 2 : δ = ρn−1/2+1/2p′ ≥
εp
n
log n/n}. Then there exists some absolute constant C1 > 0, and for any
C2 > 0, there exists some constant C3 = C3 (C2 ) > 0 such that


p
2
1 1/p′ −1/(p′ )2
1/2p′
P Z̃ ≥ n
− C3 n
log n ≥ C1 (εp′ ) ∧ 1 n−4ε − e−C2 log n .
16
We need some auxiliary results before the proof of Lemma 18.

Lemma 19. Suppose that ξ1 , . . . , ξn are i.i.d. symmetric random variables
with p(t) ≡ P(|ξ1 | > t) = 1/(1 + |t|p ). Then for any 1 ≤ q < p, and n ≥ 2,


1/q 
p + q 1/q 1/p
1 1/p
q
n .
n ≤ E max |ξi | ≤ E max |ξi |
≤
1≤i≤n
1≤i≤n
4
p−q

We need the following exact characterization concerning the size of maxima of a sequence of independent random variables due to [25], see also
Corollary 1.4.2 of [19].

MULTIPLIER INEQUALITIES

35

Lemma 20. Let ξ1 , . . . , ξn be a sequence of independent non-negative random variables suchP
that kξi kr < ∞ for all 1 ≤ i ≤ n. For λ > 0, set
δ0 (λ) ≡ inf {t > 0 : ni=1 P(ξi > t) ≤ λ}. Then
n

n

i=1

i=1

1 X r
1 X r
Eξi 1ξi >δ0 ≤ E max ξir ≤
Eξi 1ξi >δ0 .
1≤i≤n
1+λ
1∧λ

Proof of Lemma 19. For λ ≡ 1 in Lemma 20, δ0 = inf{t > 0 : np(t) ≤ 1} =
(n − 1)1/p . Lemma 20 now yields that for q < p,
E max |ξi |q ≤ nE |ξ1 |q 1|ξ1 |>δ0
1≤i≤n

Z
= n P(|ξ1 | > δ0 )
nδ0q
+ qn
1 + δ0p

0
∞

δ0

q−1

qu

du +

Z

∞
δ0

q−1

qu

P(|ξ1 | > u) du

1
du
p−q+1
u
δ0
q
n
p + q q/p
= (n − 1)q/p +
(n − 1)q/p ≤
n
p−qn−1
p−q

≤

Z



since n ≥ 2. For a lower bound for E max1≤i≤n |ξi |, we proceed similarly as
above by using 1 + up ≤ 2up on [δ0 , ∞) for n ≥ 2:


Z ∞
1
δ0
(n − 1)1/p
1
n
+
du
=
≥ n1/p .
E max |ξi | ≥
p
p
1≤i≤n
2 1 + δ0
2
4
δ0 2u
This completes the proof.



We also need Talagrand’s concentration inequality [58] for the empirical
process in the form given by [42], recorded as follows.
Lemma 21. Let F be a countable class of real-valued measurable functions
such that supf ∈F kf k∞ ≤ b. Then
!
√
x
≤ e−x ,
P sup |Gn f | ≥ 2E sup |Gn f | + 8σ 2 x + 34.5b √
n
f ∈F
f ∈F
√
where σ 2 ≡ supf ∈F VarP f , and Gn ≡ n(Pn − P ).
Proof of Lemma 18. The proof is divided into two steps. In the first step,
we handle Z, i.e. the multiplier empirical process part. In the second step
we handle the residual term, i.e. the purely empirical process part.
(Step 1) We first claim that there exists some absolute constant C1 > 0
such that


2
1 1/p′ −1/(p′ )2
n
≥ C1 (εp′ ) ∧ 1 n−4ε .
(6.22)
P Z≥
32

Let G be the class of indicators functions 1[a,b] with 0 ≤ a ≤ b ≤ 1. Then
p
since δn ≥ log n/n, by local maximal inequalities for the empirical process

36

Q. HAN AND J. A. WELLNER

(Proposition 5),
(6.23)

E

sup

n
X

2
g∈G:P g 2 ≤δn
i=1

εi g(Xi ) .

p
√
′p
nδn log(1/δn ) . n1/2p log n

where in the last inequality we used ρ .√1. Applying Theorem
1 and noting
√
′
1/p , we see
that p ≤ log n/ log log n implying n1/2p log n ≤ n1/2p log n ≤
Pn
n
that for some absolute constant C > 0, EZ ≤ E supg∈G:P g2 ≤δn2 | i=1 ξi g(Xi )| ≤
Cn1/p kξ1 kp,1 . By the moment inequality Lemma 1, we have for any q ≥ 1,


√
q
q
q
q
EZ ≤ Cq (EZ) + ( n kξ1 k2 δn ) + E max |ξi |
1≤i≤n


′
≤ Cq′ nq/p kξ1 kqp,1 + nq/2p kξ1 kq2 + E max |ξi |q
1≤i≤n


q
′
q/p
q
≤ 2Cq n (kξ1 kp,1 ∨ kξ1 k2 ) + E max |ξi | .
1≤i≤n

Now using the Paley-Zygmund inequality (Lemma 15) and Lemma 17, we
see that
q ′



EZ
1
′
P Z > EZ ≥ 2−q
2
(EZ q )1/q
!q ′
E
max
−1 n1−1/p′ |ξj |
1≤j≤4
≥ Cq′′
.
n1/p (kξ1 kp,1 ∨ kξ1 k2 ) + (E max1≤i≤n |ξi |q )1/q
By Lemma 19, the above display can be further estimated from below by
!q ′
′
′ 2
n1/p −1/(p )
′′′
Cq
n1/p (kξ1 kp,1 ∨ kξ1 k2 ) + [(p′ + q)/(p′ − q)]1/q n1/p′
!2
1/p′ −1/(p′ )2
n
(choose q = q ′ = 2)
≥ C′
′
n1/p (kξ1 kp,1 ∨ kξ1 k2 ) + n1/p
2 − 2 + 2 − 2
2
≥ C ′′ (εp′ ) ∧ 1 n p p′ (p′ )2 ≥ C ′′ (εp′ ) ∧ 1 n−4ε

where in the last line we use the following facts: (i) p1 − p1′ = ε, (ii) p′ ≥ p ≥
ε−1/2 and (iii)
Z ∞
Z ∞
1
1/p
dt
kξ1 kp,1 =
P(|ξ1 | > t)
dt =
(1 + tp′ )1/p
0
0
Z ∞
dt
1
1
≍1+
= 1 + ′,
′ /p = 1 +
′
p
p /p − 1
εp
t
1
1
≍ 1.
kξ1 k2 ≤ kξ1 k2,1 ≍ 1 + ′
(p /2) − 1

MULTIPLIER INEQUALITIES

37

The proof of (6.22) is complete by noting that
1 −1/p′ 1/p′ −1/(p′ )2
1
−1 1/p′ −1/(p′ )2
.
≥
16
n
|ξ
|
≥
n
max
4
EZ ≥ E
j
2 1≤j≤4−1 n1−1/p′
8
(Step 2) We next claim that for any C2 > 0, there exists some absolute
constant C3 > 0 such that
(6.24)
!
n
X
p
1/2p′
2
2
(f (Xi ) − P f ) ≤ C3 n
P
sup
log n ≥ 1 − e−C2 log n .
2
f ∈F̃n :P f 2 ≤δn
i=1

Note that by contraction principle and (6.23),
E

sup

n
X
(f 2 (Xi ) − P f 2 ) . E

2
f ∈F̃n :P f 2 ≤δn
i=1

n
X

sup

2
g∈G:P g 2 ≤δn
i=1

εi g(Xi ) . n1/2p

′

p

log n.

The claim (6.24) now follows from the above display combined with Talagrand’s concentration inequality (Lemma 21) applied with x = C2 log n.
Now the claimed inequality in the lemma follows by considering the event
that is the intersection of the events indicated in (6.22) and (6.24).

Now we are in a good position to prove the second claim of Theorem 5.
′ 2

n
Proof of Theorem 5: claim (2). Suppose that n1/(p ) ≤ 2, p′ < 2 log(64Clog
3 )+log log n
and ρ = 1/8. Then
′p
1 1/p′ −1/(p′ )2
n
− C3 n1/2p log n − nδn2
16 

p
p
1
1 1/p′
1/2p′
2
1/2p′
1/p′
=
log
n
≥
log n > 0.
−
C
n
−
ρ
n
−
C
n
n
3
3
′
2
64
16n1/(p )
o n
o
n
′√
1 1/p′ −1/(p′ )2
− C3 n1/2p log n ⊂ Z̃ − nδn2 > 0 ⊂ {Fn (δn ) > En (δn /2)},
n
Since Z̃ ≥ 16
it follows from Lemma 18 that
2
P(En ) ≡ P (Fn (δn ) > En (δn /2)) ≥ C1 (εp′ ) ∧ 1 n−4ε − e−C2 log n ,
′

provided further ε ≥ 1/p2 , p ≥ 3, n ≥ 2 and n1/p ≥ 64 log n. Equivalently,
p
log n
ε ≥ 1/p2 , p ≥ 3, n ≥ 2,
.
log2 n ≤ p′ ≤
log(64 log n) + 2 log(64C3 )

Furthermore, since p′ = p/(1 − pε) ≤ 2p if ε ≤ 1/2p, it suffices to require


p
log n
2
64C32
1−δ
1/p ≤ ε ≤ 1/2p, n ≥ nδ ∨ e
,
,
log2 n ≤ p ≤ (log n)
≤
2 log(64 log n)
where nδ ≡ min{n ≥ 2 : (log n)δ ≥ 2 log(64 log n)}. Hence for n in the
indicated range (i.e. large enough depending on δ, C3 ), we have
P(En ) ≥ C1 (log n)−2 n−4ε − e−C2 log n ≥ C(log n)−2 n−4ε ,

38

Q. HAN AND J. A. WELLNER

where the first inequality follows from εp′ ≥ εp ≥ 1/p ≥ 1/ log n, and
the second inequality follows for n large enough by choosing C2 = 3 since
n−4ε ≥ n−2 . By Proposition 6,
E kfn∗ − f0 kL2 (P ) ≥ E kfn∗ − f0 kL2 (P ) 1En

δn
· C(log n)−2 n−4ε ≥ C ′ n−1/2+1/2p−4.5ε (log n)−2 .
2
For any 1/(1 − δ) < a < 2 so that p = (log n)1/a , we may choose ε = p−a .
The claim then follows by noting n−ε = n−1/ log n = e−1 , and kξ1 kp,1 ≍
1 + (εp)−1 = 1 + (log n)1−1/a . log n.

≥

7. Remaining proofs
7.1. Proof of Lemma 3. We need some auxiliary lemmas before the proof
of Lemma 3.

Pd
Lemma 22. Let Fβ : Rd → R be defined by Fβ (x) = β −1 log
exp(βxi ) .
i=1
P
Then supx∈Rd dj,k,l,m=1 |∂jklm Fβ (x)| ≤ 25β 3 .
P
Proof. Let πj (x) = ∂j Fβ (x) = exp(βxj )/ di=1 exp(βxi ) and δij = 1i=j .
Then it is easy to verify that (see Lemma 4.3 of [18])
∂jk Fβ = ∂j (πk ) = β(δjk πj − πj πk ),


∂jkl Fβ = β 2 δjk δjl πl − δjk πj πl + 2πj πk πl − (δjl + δkl )πk πl .

Further taking derivative with respect to xm , we have


∂jklmFβ = β 2 δjk δjl ∂m (πl ) − δjk ∂m (πj πl ) + 2∂m (πj πk πl ) − (δjl + δkl )∂m (πk πl )


= β 2 (I) − (II) + 2(III) − (IV ) ,



where (I) = βδjk δjl δlm πl − πl πm , (II) = βδjk (δjm + δlm )πj πl − 2πj πl πm ,
(III)
 = β (δjm + δkm + δlm )πj πk πl − 3πj πk πl πm , and (IV ) = β(δjl +
δkl ) (δ
Pjm + δkm )πj πk − 2πj πk πm . Now summing over j, k, l, m by noting
that j πj = 1 yields the claim.

Proof of Lemma 3. In the proof we write k ≡ n to line up with the notation
used in [17]. Slightly abusing the notation, we use simply Xi ’s to denote
εi Xi ’s. Let Y1 , . . . , Yn be centered i.i.d. Gaussian random vectors in Rd such
that EY1 Y1⊤ = EX1 X1⊤ . We first claim that it suffices to prove that,


4
4
3 −1
(7.1) |EFβ (X) − Fβ (Y )| . β n E max |X1j | ∨ |Y1j |
≡ β 3 n−1 M̄4 ,
1≤j≤d

Pn
d
d
Y =
i=1 Yi ∈ R , and Fβ : R → R is

Pd
defined by Fβ (x)
i=1 exp(βxi ) . Once (7.1) is proved, we use
the inequality 0 ≤ Fβ (x) − max1≤j≤d xj ≤ β −1 log d to obtain that
where X =

√1
n

Pn

Rd ,

i=1 Xi ∈
= β −1 log

n

√1
n

n

1 X
1 X
E max √
Xij − E max √
Yij
1≤j≤d
1≤j≤d
n
n
i=1

i=1

. β 3 n−1 M̄4 + β −1 log d.

MULTIPLIER INEQUALITIES

39

1/4
and
The conclusion of Lemma 3 follows by taking β = n log d/M̄4
controlling the size of the Gaussian maxima.
The proof of (7.1) proceeds in similar lines as in Lemma I.1 of [17] by
a fourth moment argument instead of a√third moment
one P
used therein.
√
n
We provide details below. Let Z(t) = tX + 1 − tY =
i=1 Z
√i (t) be
the Slepian’s interpolation between X and Y , where Zi (t) = √1n ( tXi +
√
1 − tYi ). Let Z (i) (t) = Z(t) − Zi (t). Then,
(7.2)
EFβ (X) − EFβ (Y ) = EFβ (Z(1)) − EFβ (Z(0))
Z 1X
Z 1
d
n X
h
i
d
E ∂j Fβ (Z(t))Żij (t) dt
EFβ (Z(t)) dt =
=
0 i=1 j=1
0 dt


1
where Żij (t) = 2√1 n √1t Xij − √1−t
Yij . Now using Taylor expansion for
∂j Fβ (·) at Z (i) (t), we have
(7.3)
X
∂j Fβ (Z(t)) = ∂j Fβ (Z (i) (t)) +
∂jk Fβ (Z (i) (t))Zik (t)
k

+

X

(i)

∂jkl Fβ (Z (t))Zik (t)Zil (t)

k,l

+

XZ

1

∂jklm Fβ (Z (i) (t) + τ Zi (t))Zik (t)Zil (t)Zim (t) dτ.

k,l,m 0

Hence (7.2) can be split into four terms according to (7.3). Now the key
observation here is that Z (i) (t) is independent of Zi· , Żi· . Since EŻij (t) = 0,
the contribution of the first order term in (7.3) vanishes. Similar observation holds for the second and third order terms. For the second order
term, we only need to verify EŻij (t)Zik (t) = 0; this follows from the construction
of Y that matches
second moments of X: EŻij (t)Zik (t) =

 √ the √

1
1
1
1
√ Xij − √
(EXij Xik − EYij Yik ) =
tXik + 1 − tYik = 2n
Y
2n E
1−t ij
t
0. For the third order term,
EŻij (t)Zik (t)Zil (t)


 √

√
√
√
1
1
1
= 3/2 E √ Xij − √
tXik + 1 − tYik
tXil + 1 − tYil
Yij
2n
1−t
t
√

√
3/2 −1
= (2n )
tEXij Xik Xil − 1 − tEYij Yik Yil .

Cross terms in the calculation of the last line in the above display all vanish
by the independence and centeredness of X and Y . The first term of the
above display is 0 since (recall Xi stands for εi Xi throughout the proof)
Eε3i Xij Xik Xil = Eε3i · EXij Xik Xil = 0 by the independence between the
Rademacher εi and Xi . The second term is also zero by a similar argument:
since Yi =d εi Yi for a Rademacher random variable εi independent of Yi ,

40

Q. HAN AND J. A. WELLNER

EYij Yik Yil = Eε3i · EYij Yik Yil = 0. Hence the only non-trivial contribution of
(7.3) in (7.2) is the fourth order term:
(7.4)
|EFβ (X) − Fβ (Y )|
Z 1Z 1
d
n
X
X
E ∂jklmFβ (Z (i) (t) + τ Zi (t))Żij (t)Zik (t)Zil (t)Zim (t) dτ dt
≤
≤

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

0

n Z
X

d
X

i=1

0

1Z 1

E

0



∂jklmFβ (Z (i) (t) + τ Zi (t))

j,k,l,m=1

×
≤ 25β

3

n Z
X
i=1

max

1≤k,l,m≤d

Żij (t)Zik (t)Zil (t)Zim (t)

1

E
0

max

1≤j,k,l,m≤d



dτ dt

Żij (t)Zik (t)Zil (t)Zim (t) dt

where the last inequality follows from the dimension free property of the
third derivatives of soft max function Fβ (Lemma 22). Now the claim (7.1)
follows by noting that

 
3/4
4 1/4
4
E max
E max |Zij |
Żij (t)Zik (t)Zil (t)Zim (t) ≤ E max Żij
1≤j≤d
1≤j,k,l,m≤d
1≤j≤d



1
1
4
4
−2
√
√
E max |X1j | ∨ |Y1j |
∨
.n
1≤j≤d
1−t
t


R1
1
dt < ∞ converges.

and the fact that the integral 0 √1t ∨ √1−t
7.2. Proof of Proposition 3.

Proof of Proposition 3. We will construct a sequence of {fn } ⊂ F such that
for any κ > 0,
(7.5)

P(|fn | ≥ κ kfn kL2 (P ) ) → 0,

which implies that the small-ball condition fails. √
For (1), let fn ≡ 1[0,1/n] . Then kfn kL2 (P ) = 1/ n, and hence for any
κ > 0,
√
P(|fn | ≥ κ kfn kL2 (P ) ) = P(|fn (X)| ≥ κ/ n) = P(X ∈ [0, 1/n]) = 1/n → 0,
thereby verifying (7.5).
Next consider
√ (2). We let fn (x) ≡ (1/n − x)+ . Then it is easy to see that
kfn kL2 (P ) = 1/ 3n3 . Hence for any κ > 0,
P(|fn | ≥ κ kfn kL2 (P ) ) ≤ P(|fn (X)| ≥ 0) = 1/n → 0,
thereby verifying (7.5). (3) follows from the same construction as in (2)
by replacing fn therein with smooth versions. This can be done, e.g., by
2
choosing fn (x) ≡ φ(x − 1/n) where φ(x) = e−1/x 1x≤0 [since the derivatives
of φ is uniformly bounded on [−1, 0]].


MULTIPLIER INEQUALITIES

41

7.3. Proof of Proposition 4.
Proof of Proposition 4. Consider F = {1[a,b] : 0 ≤ a ≤ b ≤ 1, b − a ≤
δ2 , a, b ∈ Q}. It is easy to see that supf ∈F (δ) |G1 f | ≥ 1 − δ2 . On the other
hand, by the local maximal inequality for the empirical process (see Proposiclass (seeSection 2.6 of [68]), we
tion 5) and the fact that F is a VC-subgraph

√
p
log(1/δ)
have E supf ∈F (δ) |Gn f | . δ log(1/δ) 1 + √nδ
. Talagrand’s concen-

tration inequality (Lemma 21) then implies that with probability exceeding
1 − exp(−u2 2s0 ),
!
p
p
√
log(1/δ)
34.5u2 2s0
√
√
sup |Gn f | ≤ Cδ log(1/δ) 1 +
+ 8u2s0 /2 δ +
.
nδ
n
f ∈F (δ)

p
Note that for δ ≥ log n/n and n ≥ 3, the right side of the above display
can be further bounded from above up to an absolute constant by
p
p
p
δ log(1/δ) + u2s0 /2 δ + u2 2s0 δ log(1/δ) . u2 2s0 δ log(1/δ).

Nowpwe choose n0 ≡ n0 (ε, u, s0 ) so large such that for any n ≥ n0 , if
δ ≡ log n/n, then on an event with probability exceeding 1− exp(−u2 2s0 ),
p
sup |Gn f | ≤ C ′ u2 2s0 δ log(1/δ) < ε(1 − δ2 ) ≤ ε sup |G1 f | .
f ∈F (δ)

f ∈F (δ)

The claim now follows from (5.3) applied for n = 1.



7.4. Proof of Lemma 4.
Proof of Lemma 4. Without loss of generality we assume that an ≤ 1 for
all n = 0, 1, . . .. For any ε ∈ (0, 1), since an vanishes asymptotically, there
exists some Nε for which an ≤ ε as long as n ≥ Nε . Consider
(
ϕ(t),
t ≤ Nε ;
ψε (t) ≡
(1 − ε)ϕ(Nε ) + εϕ(t), t > Nε .
Then it is easy to verify that ψε is a concave function and majorizes n 7→
an ϕ(n) [since ψε (n) ≥ εϕ(n) ≥ an ϕ(n) for n ≥ Nε and ψε (n) = ϕ(n) ≥
an ϕ(n) for n < Nε by the assumption that an ≤ 1]. Hence by definition of
ψ, it follows that lim supt→∞ ψ(t)/ϕ(t) ≤ limt→∞ ψε (t)/ϕ(t) = ε. The claim
now follows by taking ε → 0.

Acknowledgements
The authors would like to thank Vladimir Koltchinskii and Richard Samworth for helpful comments and references on an earlier version of the paper.

42

Q. HAN AND J. A. WELLNER

References
[1] K. S. Alexander. The non-existence of a universal multiplier moment for the central
limit theorem. In Probability in Banach Spaces V, pages 15–16. Springer, 1985.
[2] N. T. Andersen, E. Giné, and J. Zinn. The central limit theorem for empirical processes under local conditions: the case of Radon inﬁnitely divisible limits without
Gaussian component. Trans. Amer. Math. Soc., 308(2):603–635, 1988.
[3] J.-Y. Audibert and O. Catoni. Robust linear least squares regression. Ann. Statist.,
39(5):2766–2794, 2011.
[4] Z. D. Bai, J. W. Silverstein, and Y. Q. Yin. A note on the largest eigenvalue of
a large-dimensional sample covariance matrix. J. Multivariate Anal., 26(2):166–168,
1988.
[5] Z. D. Bai and Y. Q. Yin. Limit of the smallest eigenvalue of a large-dimensional
sample covariance matrix. Ann. Probab., 21(3):1275–1294, 1993.
[6] P. L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. Ann.
Statist., 33(4):1497–1537, 2005.
[7] P. L. Bartlett and S. Mendelson. Empirical minimization. Probab. Theory Related
Fields, 135(3):311–334, 2006.
[8] L. Birgé and P. Massart. Rates of convergence for minimum contrast estimators.
Probab. Theory Related Fields, 97(1-2):113–150, 1993.
[9] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities. Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence, With a foreword
by Michel Ledoux.
[10] C. Brownlees, E. Joly, and G. Lugosi. Empirical risk minimization for heavy-tailed
losses. Ann. Statist., 43(6):2507–2536, 2015.
[11] S. Bubeck, N. Cesa-Bianchi, and G. Lugosi. Bandits with heavy tail. IEEE Trans.
Inform. Theory, 59(11):7711–7717, 2013.
[12] P. Bühlmann and S. van de Geer. Statistics for high-dimensional data. Springer Series
in Statistics. Springer, Heidelberg, 2011. Methods, theory and applications.
[13] B. Carl. Entropy numbers of embedding maps between Besov spaces with an application to eigenvalue problems. Proc. Roy. Soc. Edinburgh Sect. A, 90(1-2):63–70,
1981.
[14] O. Catoni. Challenging the empirical mean and empirical variance: a deviation study.
Ann. Inst. Henri Poincaré Probab. Stat., 48(4):1148–1185, 2012.
[15] O. Catoni. Pac-bayesian bounds for the gram matrix and least squares regression
with a random design. arXiv preprint arXiv:1603.05229, 2016.
[16] S. Chatterjee. A new perspective on least squares under convex constraint. Ann.
Statist., 42(6):2340–2381, 2014.
[17] V. Chernozhukov, D. Chetverikov, and K. Kato. Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors. Ann. Statist.,
41(6):2786–2819, 2013.
[18] V. Chernozhukov, D. Chetverikov, and K. Kato. Gaussian approximation of suprema
of empirical processes. Ann. Statist., 42(4):1564–1597, 2014.
[19] V. H. de la Peña and E. Giné. Decoupling. Probability and its Applications (New
York). Springer-Verlag, New York, 1999. From dependence to independence, Randomly stopped processes. U -statistics and processes. Martingales and beyond.
[20] L. Devroye, M. Lerasle, G. Lugosi, and R. I. Oliveira. Sub-Gaussian mean estimators.
Ann. Statist., 44(6):2695–2725, 2016.
[21] R. M. Dudley. The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. J. Functional Analysis, 1:290–330, 1967.
[22] E. Giné and V. Koltchinskii. Concentration inequalities and asymptotic results for
ratio type empirical processes. Ann. Probab., 34(3):1143–1216, 2006.

MULTIPLIER INEQUALITIES

43

[23] E. Giné, R. Latala, and J. Zinn. Exponential and moment inequalities for U -statistics.
In High dimensional probability, II (Seattle, WA, 1999), volume 47 of Progr. Probab.,
pages 13–38. Birkhäuser Boston, Boston, MA, 2000.
[24] E. Giné and R. Nickl. Mathematical foundations of infinite-dimensional statistical
models, volume 40. Cambridge University Press, 2015.
[25] E. Giné and J. Zinn. Central limit theorems and weak laws of large numbers in certain
Banach spaces. Z. Wahrsch. Verw. Gebiete, 62(3):323–354, 1983.
[26] E. Giné and J. Zinn. Some limit theorems for empirical processes. Ann. Probab.,
12(4):929–998, 1984. With discussion.
[27] E. Giné and J. Zinn. Lectures on the central limit theorem for empirical processes.
In Probability and Banach spaces (Zaragoza, 1985), volume 1221 of Lecture Notes in
Math., pages 50–113. Springer, Berlin, 1986.
[28] D. Hsu and S. Sabato. Loss minimization and parameter estimation with heavy tails.
J. Mach. Learn. Res., 17:Paper No. 18, 40, 2016.
[29] E. Joly, G. Lugosi, and R. I. Oliveira. On the estimation of the mean of a random
vector. Electron. J. Stat., 11(1):440–451, 2017.
[30] V. Koltchinskii. Local Rademacher complexities and oracle inequalities in risk minimization. Ann. Statist., 34(6):2593–2656, 2006.
[31] V. Koltchinskii and D. Panchenko. Rademacher processes and bounding the risk of
function learning. In High dimensional probability, II (Seattle, WA, 1999), volume 47
of Progr. Probab., pages 443–457. Birkhäuser Boston, Boston, MA, 2000.
[32] G. Lecué and S. Mendelson. Learning subgaussian classes: Upper and minimax
bounds. arXiv preprint arXiv:1305.4825, 2013.
[33] G. Lecué and S. Mendelson. Sparse recovery under weak moment assumptions. arXiv
preprint arXiv:1401.2188, 2014.
[34] G. Lecué and S. Mendelson. Regularization and the small-ball method i: sparse recovery. arXiv preprint arXiv:1601.05584, 2016.
[35] M. Ledoux and M. Talagrand. Conditions d’intégrabilité pour les multiplicateurs dans
le TLC banachique. Ann. Probab., 14(3):916–921, 1986.
[36] M. Ledoux and M. Talagrand. Un critère sur les petites boules dans le théorème limite
central. Probab. Theory Related Fields, 77(1):29–47, 1988.
[37] M. Ledoux and M. Talagrand. Probability in Banach Spaces. Classics in Mathematics.
Springer-Verlag, Berlin, 2011. Isoperimetry and processes, Reprint of the 1991 edition.
[38] G. Lugosi and S. Mendelson. Risk minimization by median-of-means tournaments.
arXiv preprint arXiv:1608.00757, 2016.
[39] G. Lugosi and S. Mendelson. Regularization, sparse recovery, and median-of-means
tournaments. arXiv preprint arXiv:1701.04112, 2017.
[40] G. Lugosi and S. Mendelson. Sub-gaussian estimators of the mean of a random vector.
arXiv preprint arXiv:1702.00482, 2017.
[41] D. M. Mason. The asymptotic distribution of weighted empirical distribution functions. Stochastic Process. Appl., 15(1):99–109, 1983.
[42] P. Massart. About the constants in Talagrand’s concentration inequalities for empirical processes. Ann. Probab., 28(2):863–884, 2000.
[43] P. Massart and E. Nédélec. Risk bounds for statistical learning. Ann. Statist.,
34(5):2326–2366, 2006.
[44] P. Massart and E. Rio. A uniform Marcinkiewicz-Zygmund strong law of large numbers for empirical processes. In Asymptotic methods in probability and statistics (Ottawa, ON, 1997), pages 199–211. North-Holland, Amsterdam, 1998.
[45] S. Mendelson. Learning without concentration. J. ACM, 62(3):Art. 21, 25, 2015.
[46] S. Mendelson. ‘local’ vs. ‘global’ parameters–breaking the gaussian complexity barrier.
arXiv preprint arXiv:1504.02191, 2015.
[47] S. Mendelson. On aggregation for heavy-tailed classes. arXiv preprint
arXiv:1502.07097, 2015.

44

Q. HAN AND J. A. WELLNER

[48] S. Mendelson. On multiplier processes under weak moment assumptions. arXiv
preprint arXiv:1601.06523, 2016.
[49] S. Mendelson. Upper bounds on product and multiplier empirical processes. Stochastic
Process. Appl., 126(12):3652–3680, 2016.
[50] S. Minsker. Geometric median and robust estimation in Banach spaces. Bernoulli,
21(4):2308–2335, 2015.
[51] R. Nickl and S. van de Geer. Conﬁdence sets in sparse regression. Ann. Statist.,
41(6):2852–2876, 2013.
[52] G. Raskutti, M. J. Wainwright, and B. Yu. Restricted eigenvalue properties for correlated Gaussian designs. J. Mach. Learn. Res., 11:2241–2259, 2010.
[53] T. Robertson, F. T. Wright, and R. L. Dykstra. Order restricted statistical inference.
Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Ltd., Chichester, 1988.
[54] M. Rudelson and S. Zhou. Reconstruction from anisotropic random measurements.
IEEE Trans. Inform. Theory, 59(6):3434–3447, 2013.
[55] G. R. Shorack and J. A. Wellner. Empirical processes with applications to statistics,
volume 59 of Classics in Applied Mathematics. Society for Industrial and Applied
Mathematics (SIAM), Philadelphia, PA, 2009.
[56] V. Sivakumar, A. Banerjee, and P. K. Ravikumar. Beyond sub-gaussian measurements: High-dimensional structured estimation with sub-exponential designs. In Advances in neural information processing systems, pages 2206–2214, 2015.
[57] V. Strassen and R. M. Dudley. The central limit theorem and ε-entropy. In Probability
and Information Theory (Proc. Internat. Sympos., McMaster Univ., Hamilton, Ont.,
1968), pages 224–231. Springer, Berlin, 1969.
[58] M. Talagrand. New concentration inequalities in product spaces. Invent. Math.,
126(3):505–563, 1996.
[59] M. Talagrand. Upper and lower bounds for stochastic processes, volume 60 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys
in Mathematics. Springer, Heidelberg, 2014. Modern methods and classical problems.
[60] R. Tibshirani. Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc.
Ser. B, 58(1):267–288, 1996.
[61] H. Tribel′. Interpolation properties of ε-entropy and of diameters. Geometric characteristics of the imbedding of function spaces of Sobolev-Besov type. Mat. Sb. (N.S.),
98(140)(1 (9)):27–41, 157, 1975.
[62] A. B. Tsybakov. Introduction to nonparametric estimation. Springer Series in Statistics. Springer, New York, 2009. Revised and extended from the 2004 French original,
Translated by Vladimir Zaiats.
[63] S. van de Geer. Estimating a regression function. Ann. Statist., 18(2):907–924, 1990.
[64] S. van de Geer, P. Bühlmann, Y. Ritov, and R. Dezeure. On asymptotically optimal
conﬁdence regions and tests for high-dimensional models. Ann. Statist., 42(3):1166–
1202, 2014.
[65] S. A. van de Geer. Applications of Empirical Process Theory, volume 6 of Cambridge
Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2000.
[66] S. A. van de Geer and M. Wainwright. On concentration for (regularized) empirical
risk minimization. arXiv preprint arXiv:1512.00677, 2015.
[67] A. van der Vaart and J. A. Wellner. A local maximal inequality under uniform entropy.
Electron. J. Stat., 5:192–203, 2011.
[68] A. W. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes.
Springer Series in Statistics. Springer-Verlag, New York, 1996.
[69] Y. Yang. Nonparametric regression with dependent errors. Bernoulli, 7(4):633–655,
2001.

MULTIPLIER INEQUALITIES

45

[70] Y. Yang and A. Barron. Information-theoretic determination of minimax rates of
convergence. Ann. Statist., 27(5):1564–1599, 1999.
(Q. Han) Department of Statistics, Box 354322, University of Washington,
Seattle, WA 98195-4322, USA.
E-mail address: royhan@uw.edu
(J. A. Wellner) Department of Statistics, Box 354322, University of Washington, Seattle, WA 98195-4322, USA.
E-mail address: jaw@stat.washington.edu

