arXiv:1712.07801v1 [math.ST] 21 Dec 2017

Density Estimation with Contaminated Data:
Minimax Rates and Theory of Adaptation
Haoyang Liu and Chao Gao
University of Chicago
December 22, 2017

Abstract
This paper studies density estimation under pointwise loss in the setting of contamination model. The goal is to estimate f (x0 ) at some x0 ∈ R with i.i.d. observations,
X1 , . . . , Xn ∼ (1 − )f + g,
where g stands for a contamination distribution. In the context of multiple testing,
this can be interpreted as estimating the null density at a point. We carefully study the
effect of contamination on estimation through the following model indices: contamination
proportion , smoothness of target density β0 , smoothness of contamination density β1 ,
and level of contamination m at the point to be estimated, i.e. g(x0 ) ≤ m. It is shown
that the minimax rate with respect to the squared error loss is of order
2β1

2β0

2

[n− 2β0 +1 ] ∨ [2 (1 ∧ m)2 ] ∨ [n− 2β1 +1  2β1 +1 ],
which characterizes the exact influence of contamination on the difficulty of the problem. We then establish the minimal cost of adaptation to contamination proportion, to
smoothness and to both of the numbers. It is shown that some small price needs to be
paid for adaptation in any of the three cases. Variations of Lepski’s method are considered
to achieve optimal adaptation.
The problem is also studied when there is no smoothness assumption on the contamination distribution. This setting that allows for an arbitrary contamination distribution
is recognized as Huber’s -contamination model. The minimax rate is shown to be
2β0

2β0

[n− 2β0 +1 ] ∨ [ β0 +1 ].
The adaptation theory is also different from the smooth contamination case. While
adaptation to either contamination proportion or smoothness only costs a logarithmic
factor, adaptation to both numbers is proved to be impossible.
Keywords: minimax rate, nonparametric functional estimation, adaptive estimation,
contamination model, robust statistics, Lepski’s method, null distribution.

1

1

Introduction

Nonparametric density estimation is a well-studied classical topic [21, 8, 23]. In this paper,
we consider a modern twist of the problem. Our goal is to estimate f (x0 ) at some x0 ∈ R
with i.i.d. observations
X1 , ..., Xn ∼ (1 − )f + g.
(1)
For each i = 1, ..., n, the observation Xi is sampled from f with probability 1 − , and
with probability , it is sampled from a contamination distribution g. The presence of contamination makes the estimation problem much harder. In terms of expectation, there are
n contaminated points mixed with other good observations, which requires an estimation
procedure to be robust.
When there is no constraint on the contamination distribution g, the data generating
process (1) is also recognized as Huber’s -contamination model [13, 14]. Recent work on
nonparametric estimation in such a setting includes [6, 12], and the influence of contamination
on minimax rates is investigated by [7, 6]. In the literature of large-scale multiple testing,
the problem is equivalent to estimating the null distribution with the contamination of an
alternative distribution [11]. Optimal rates of estimating the null density f with structural
assumptions on the alternative g are investigated by [15, 3].
In this paper, we consider estimating f (x0 ) of a density function f that has a Hölder
smoothness β0 . Both cases of structured and arbitrary contamination are studied. In the
first case, the contamination distribution g is assumed to be a density function that has a
Hölder smoothness β1 , and the contamination level at the point x0 is assumed to satisfy
g(x0 ) ≤ m. We show that the minimax rate of estimating f (x0 ) with respect to the squared
error loss is of order
2β0
2β1
2
−
−
[n 2β0 +1 ] ∨ [2 (1 ∧ m)2 ] ∨ [n 2β1 +1  2β1 +1 ].
(2)
The minimax rate involves three terms, and the influence of contamination on estimation
−

2β0

is precisely characterized. The first term n 2β0 +1 corresponds to the classical minimax rate
of nonparametric estimation when there is no contamination. The second term 2 (1 ∧ m)2
is determined by contamination on x0 . It depends on both the contamination proportion
−

2β1

2

 and the contamination level m. The last term n 2β1 +1  2β1 +1 is caused by contamination
on the neighborhood of x0 , which is present even if the contamination level m is zero. We
also investigate Huber’s -contamination model, where the contamination distribution g is
arbitrary. The minimax rate for this case is
[n

2β0
0 +1

− 2β

2β0

] ∨ [ β0 +1 ].

(3)

Compared with (2), the rate (3) is easier to understand in terms of the influence of the
contamination. It is interesting to note that even though β0 is the smoothness index of f ,
it still appears on the second term in (3). Thus, when the contamination is arbitrary, its
influence on estimation is also determined by the smoothness of the target density.
We also thoroughly investigate the theory of adaptation in both settings of contamination models. Depending on specific settings, various adaptation costs are necessary. For the
2

contamination model with structured contamination, when the contamination proportion is
unknown, an optimal adaptive procedure can achieve the rate (2) with 2 (1 ∧ m)2 replaced
by 2 . When the smoothness is unknown, an optimal adaptive procedure can achieve the
rate (2) with n replaced by n/ log n. Similarly, for the contamination model with arbitrary
contamination, the rate (3) can be achieved up to a logarithmic factor when either  or β0
is unknown. On the other hand, however, when both the contamination proportion and
the smoothness are unknown, the adaptation theories are completely different for the two
contamination models. For structured contamination, the adaptation cost is just the combination of the cost of unknown contamination proportion and that of unknown smoothness.
In contrast, for arbitrary contamination, we show that adaptation is simply impossible when
both  and β0 are unknown.
The theory of adaptation in nonparametric functional estimation without contamination
is well studied in the literature. It is shown by [1, 17, 5] that a logarithmic factor must be paid
for estimating a point of a density function when smoothness is not known. Adaptation costs
of estimating other nonparametric functionals have been investigated in [18, 22, 16, 2, 4].
Compared with the results in the literature, the presence of contamination brings extra
complication to the problem of adaptation. It is remarkable that the adaptation cost depends
very sensitively on each specific setting and contamination model. The new phenomena
revealed in our paper for adaptation with contamination have not been discovered before.
The rest of the paper is organized as follows. The contamination model with structured
contamination is studied in Section 2 and Section 3. Results of minimax rates and costs of
adaptation are given in Section 2 and Section 3, respectively. The corresponding theory of
contamination model with arbitrary contamination is investigated in Section 4. In Section
5, we discuss extensions of our results to multivariate density estimation and a consistent
procedure in the hardest scenario where adaptation is impossible. All proofs are given in
Section 6.
We close this section by introducing notations that will be used later. For a, b ∈ R, let
a∨b = max(a, b) and a∧b = min(a, b). For an integer m, [m] denotes the set {1, 2, ..., m}. For
a positive real number x, dxe is the smallest integer no smaller than x and bxc is the largest
integer no larger than x. For two positive sequences {an } and {bn }, we write an . bn or
an = O(bn ) if an ≤ Cbn for all n with some consntant C > 0 independent of n. The notation
an  bn means we have both an . bn and bn . an . Given a set S, |S| denotes its cardinality,
and 1S is the associated indicator function. We use P and E to denote generic probability and
expectation whose distribution is determined from the context. The notation E(X : S) stands
for E(X 1S ). The class of infinitely differentiable functions on R is denoted by C ∞ (R). For two
R 2
probability measures P and Q, the chi-squared divergence is defined as χ2 (P, Q) = dP
dQ − 1,
and the total variation distance is defined as TV(P, Q) = supB |P(B) − Q(B)|. Throughout
the paper, C, c and their variants denote generic constants that do not depend on n. Their
values may change from line to line.

3

2

Minimax Rates with Structured Contamination

2.1

Results and Implications

Consider i.i.d. observations X1 , ..., Xn ∼ (1 − )f + g. Our goal is to estimate f at a given
point. Without loss of generality, we aim to estimate f (0). Note that for every i ∈ [n],
we have Xi ∼ f with probability 1 −  and Xi ∼ g with probability . Thus, there are
approximately n observations that are not related to the density function f , and we refer to
these data points as contamination.
To study the fundamental limit of estimating f with contaminated data, we need to
specify appropriate regularity conditions on both f and g. We first define the Hölder class
by
(
)
Σ(β, L) =

f : R → R f (bβc) (x1 ) − f (bβc) (x2 ) ≤ L|x1 − x2 |β−bβc for any x1 , x2 ∈ R .

Here, β stands for the smoothness parameter, and L stands for the radius of the function
space. The Hölder class of density functions is defined as
(
)
Z
P(β, L) =

f : R → [0, ∞) f ∈ Σ(β, L),

f =1 .

Finally, we define the class of mixtures in the form of (1 − )f + g by
n
o
M(, β0 , β1 , L0 , L1 , m) = (1 − )f + g f ∈ P(β0 , L0 ), g ∈ P(β1 , L1 ), g(0) ≤ m .
This class is indexed by several numbers. In addition to the contamination proportion ,
the pair of numbers (β0 , L0 ) are the regularity parameters of the density function f that we
want to estimate, and the pair (β1 , L1 ) controls the regularity of the contamination density g.
Moreover, we use m to denote the contamination level at 0, the point that we are interested
in estimation. Among the six numbers, we allow  and m to depend on the sample size
n, but the numbers β0 , β1 , L0 , L1 are all assumed to be constants that do not depend on n
throughout the paper. We also assume  ≤ 1/2 in the paper.
The minimax risk we study is defined as
R(, β0 , β1 , L0 , L1 , m) = inf

sup


2
EX1 ,...,Xn ∼p fb(0) − f (0) ,

fb(0) p(,f,g)∈M(,β0 ,β1 ,L0 ,L1 ,m)

where the notation p(, f, g) is used to denote the density (1 − ) + g. Later in the paper,
we will shorthand EX1 ,...,Xn ∼p by Epn . We expect that the minimax risk becomes smaller if
 gets smaller or n is larger. Besides the role of  and n, there are several other factors that
affect the difficulty of this estimation problem.
• The smoothness of f : From classical density estimation theory, we know the smoother
f is, the easier it is to estimate f (0).
4

• The level of g(0): Intuitively, the smaller g(0) is, the smaller its influence is on f (0),
and thus the easier the problem is.
• The smoothness of g: Intuitively, the smoother g is, the less the contamination effect
can spread, and thus the easier it is to account for the effect of g in the contamination
model.
Now we present the following theorem of minimax rate, that justifies our intuition above.
Theorem 2.1. Under the setting above, we have
R(, β0 , β1 , L0 , L1 , m)  [n

2β0
0 +1

− 2β

] ∨ [2 (1 ∧ m)2 ] ∨ [n

2β1
1 +1

− 2β

2

 2β1 +1 ].

(4)

In other words, R(, β0 , β1 , L0 , L1 , m) can be upper and lower bounded by the right hand side
of (4) up to a constant that only depends on β0 , β1 , L0 , L1 .
Theorem 2.1 completely characterizes the difficulty of estimating f (0) with contaminated
data. The three terms in the rate (4) have different but very clear meanings. The first term
−

2β0

n 2β0 +1 is the classical minimax rate of estimating a smooth function at a given point without
contamination. The second term 2 (1 ∧ m)2 is proportional to the squared contamination
proportion . It is also determined by the level of the contamination density g at the point 0.
−

2β1

2

The last term n 2β1 +1  2β1 +1 is perhaps the most interesting. Here the effect of  is powered
by an exponent depending on β1 , and it stands for the interaction between the contamination
proportion and the contamination smoothness. The fact that it does not depend on m implies
that we have to pay this price with contaminated data even if g(0) = 0.
To further understand the implications of Theorem 2.1, we present the following illustrative special cases of the minimax rate (4). First, when  = 0, we get
R(0, β0 , β1 , L0 , L1 , m)  n

2β0
0 +1

− 2β

.

This is simply the classical minimax rate of estimating f (0) without contamination.
Next, to understand the role of m, we consider two extreme cases of m = 0 and m = ∞.
From (4), we have
R(, β0 , β1 , L0 , L1 , 0)  [n

2β0
0 +1

− 2β

] ∨ [n

and
R(, β0 , β1 , L0 , L1 , ∞)  [n

2β0
0 +1

− 2β

2β1
1 +1

− 2β

2

 2β1 +1 ],

] ∨ 2 .

The case of m = 0 is particularly interesting. It implies g(0) = 0, and one may expect that
the contamination would2βhave no influence on the minimax rate. This intuition is not true
2
1
−
because of the term n 2β1 +1  2β1 +1 . Since nonparametric estimation of f (0) also depends on
the values of the density function at a neighborhood of 0, the contamination from g can still
have an effect on the neighborhood of 0 despite that g(0) = 0. A smaller value of β1 allows
a greater perturbation by g on the neighborhood of 0. When m = ∞, the minimax rate has
5

−

2β0

a simple form of [n 2β0 +1 ] ∨ 2 . The influence on the minimax rate from contamination is
always 2 , regardless of the smoothness β1 .
Finally, we consider the cases of β1 = 0 and β1 = ∞. In fact, the Hölder class Σ(β, L)
with β1 = ∞ is not well defined, but the discussion below still holds for a sufficiently large
constant β1 . From (4), we have
R(, β0 , 0, L0 , L1 , m)  [n
and
R(, β0 , ∞, L0 , L1 , m)  [n

2β0
0 +1

− 2β

2β0
0 +1

− 2β

] ∨ 2 ,

] ∨ [2 (1 ∧ m)2 ].

The influence of the contamination takes the forms of 2 and 2 (1 ∧ m)2 for the two extreme
cases. This immediately implies that for any values of , β0 , β1 , L0 , L1 , m, we have
[n

2β0
0 +1

− 2β

] ∨ [2 (1 ∧ m)2 ] . R(, β0 , β1 , L0 , L1 , m) . [n

2β0
0 +1

− 2β

] ∨ 2 .

In other words, the influence of contamination on the minimax rate is sandwiched between
m2 2 and 2 .

2.2

Upper Bounds

The minimax rate (4) can be achieved by a simple kernel density estimator that takes the
form
 
n
X
Xi
1
1
b
K
.
(5)
fh (0) =
n(1 − )
h
h
i=1

This estimator is slightly different from the classical kernel density estimator because it is
1
normalized by n(1−)
instead of n1 . The knowledge of the contamination proportion  is very
critical to achieve the minimax rate (4). Later, we will show in Section 3.2 that the minimax
rate (4) cannot be achieved if  is not known.
We introduce the following class of kernel functions.
(
Z
Z
Kl (L) =
K:R→R
K = 1, xj K(x)dx = 0 for all j ∈ [l],
Z
kKk∞ ∨

2

Z

K ∨

)
l

|x| |K(x)|dx ≤ L .

The class Kl (L) collects all bounded and squared integrable kernel functions of order l. The
number L > 0 is assumed to be a constant throughout the paper. We refer to [8] for examples
of kernel functions in the class Kl (L).
1

−
Theorem 2.2. For the estimator fb(0) = fbh (0) with some K ∈ Kbβ0 ∨β1 c (L) and h = n 2β0 +1 ∧

n

− 2β 1+1 − 2β 2+1
1



1

, we have

sup


2
2β0
2β1
2
−
−
Epn fb(0) − f (0) . [n 2β0 +1 ] ∨ [2 (1 ∧ m)2 ] ∨ [n 2β1 +1  2β1 +1 ].

p(,f,g)∈M(,β0 ,β1 ,L0 ,L1 ,m)

6

Theorem 2.2 reveals an interesting choice of the bandwidth
h=n

− 2β 1+1
0

∧n

− 2β 1+1 − 2β 2+1
1



−

1

1

.

Compared with the optimal bandwidth of order n 2β0 +1 in classical nonparametric function
estimation, the h in a robust estimation setting is always smaller. This implies that the kernel
density estimator uses less information from the data. Intuitively, this conservative strategy
makes sense because some of the observations are contaminated. It is easy to check that h is
a non-increasing function of the contamination proportion .
The error bound in Theorem 2.2 can be found through a classical bias-variance tradeoff
argument. We can decompose the difference fb(0) − f (0) as




b
b
b
(f (0) − Ef (0)) + Ef (0) − f (0) −
g(0) +
g(0).
(6)
1−
1−
Here, the first term is the stochastic error. The second term gives the approximation error
of the kernel convolution. The last term is caused by the contamination at 0. Direct analysis
of the three terms gives the bound

2
1
E fb(0) − f (0) .
+ (h2β0 + 2 h2β1 ) + 2 (m ∧ 1)2 .
(7)
nh
−

1

−

1

−

2

Now with the choice h = n 2β0 +1 ∧ n 2β1 +1  2β1 +1 , we obtain the error bound in Theorem
2.2. For detailed derivation, see the proof of Theorem 2.2 in Section 6.1.

2.3

Lower Bounds

In this section, we study the lower bound part of the minimax rate (4). We first state a
theorem
Theorem 2.3. We have
R(, β0 , β1 , L0 , L1 , m) & [n
−

2β0
0 +1

− 2β

] ∨ [2 (1 ∧ m)2 ] ∨ [n

2β1
1 +1

− 2β

2

 2β1 +1 ].

2β0

The first term n 2β0 +1 is the classical minimax lower bound for nonparametric estimation.
We only show how to derive the second and the third terms in the lower bound. Two specific
functions are used as building blocks for our construction, and their definitions and properties
are summarized in the following two lemmas.
−

Lemma 2.1. Let l(x) = e

1
1−x2

1{|x|≤1} . Define

a(x) =
The constant c0 is chosen so that
following properties:

R

(
c0 l(x + 1),
c0 l(x − 1),

−2 ≤ x ≤ 0,
0 ≤ x ≤ 2.

a = 1 and thus a is a density function. It satisfies the

7

1. a is an even density function compactly supported on [−2, 2].
2. a(0) = 0.
3. For any constants β, L > 0, there exists a constant c > 0, such that ca(cx) ∈ P(β, L) ∩
C ∞ (R).
4. For any small constant c > 0, a is uniformly lower bounded by a positive constant on
[−1, −c] ∪ [c, 1], and it is uniformly upper bounded by a positive constant on R.
−

Lemma 2.2. Let l(x) = e

1
1−x2

1{|x|≤1} . Define

b(x) =




−l (4x + 3) ,
l(2x),


−l (4x − 3) ,

−1 ≤ x ≤ − 12 ,
|x| ≤ 21 ,
1
2

≤ x ≤ 1.

It satisfies the following properties:
1. b is an even function compactly supported on [−1, 1].
2. For any β, L > 0, there exists a constant c > 0 such that cb ∈ Σ(β, L) ∩ C ∞ (R).
3. b is uniformly lower bounded by a positive constant on [− 14 , 14 ], and |b| is uniformly
upper bounded by a positive constant on R.
R
4. b = 0.
In order to show R(, β0 , β1 , L0 , L1 , m) & 2 (1 ∧ m)2 , we consider the following four
functions,
f (x) = f0 (x),

(m ∧ 1)b(x),
1−
g(x) = c2 a(c2 x) + c1 (m ∧ 1)b(x),

fe(x) = f0 (x) + c1

ge(x) = c2 a(c2 x).
Here, the constants c1 , c2 are chosen so that the constructed functions f, fe, g, ge are welldefined densities in the desired parameter spaces. It is easy to check that with the above
construction,
(1 − )f + g = (1 − )fe + e
g.
This implies that with the presence of contamination, an estimator fb(0) cannot distinguish
between the two data generating processes (1 − )f + g and (1 − )fe+ e
g . As a consequence,
2
2
2
e
an error of order |f (0) − f (0)|   (1 ∧ m) cannot be avoided.

8

Figure 1: An illustration of the construction of g.

The derivation of the lower bound R(, β0 , β1 , L0 , L1 , m) & n
cate. Consider the following four functions,

2β1
1 +1

− 2β

2

 2β1 +1 is more intri-

f (x) = f0 (x),





x
2(x − c4 )

2(x + c4 )
β0
β0
β0
−h l
c2 h l
−h l
,
1−
h
h
h





 
x
2(x − c4 )
2(x + c4 )
x
β0
β0
β0
β1
e
g(x) = c1 a(c1 x)+c2 h l
−h l
−h l
−c3 h b
,
e
h
h
h
h

fe(x) = f0 (x) +

ge(x) = c1 a(c1 x).
Recall that the definitions of the functions l, a, b are given in Lemma 2.1 and Lemma 2.2.
Again, the constants c1 , c2 , c3 , c4 are chosen properly so that the constructed functions are
well-defined densities in the desired function classes. We note that the function g is defined as a perturbation of ge with two levels of perturbation.
 first level of perturbation
 The

x
x
β
β
e
0
1
h l h has a bandwidth h, while the second one −h b e has a bandwidth e
h. These
h
β
β
two numbers are related by h 0  e
h 1 , which leads to ge(0) = g(0) = 0. In other words,
the constructed contamination density functions g and ge both take value 0 at 0, and the
e
effect on estimating
the values of g and ge in a neighborhood of 0.
 f (0)and f (0) is through

2(x−c4 )
2(x+c4 )
β
β
0
0
The term −h l
−h l
is included in both fe and g only to ensure that
h
h
R
R
fe = g = 1. An illustration of this construction with a two-level perturbation is given by
Figure 1. The colors of the plot correspond to those in the formula.
With the above construction, it is not hard to check that
 
x
β1
e
e
p(, f, g) − p(, f , ge) = −c3 h b
.
e
h
In order that an estimator cannot distinguish between the two densities p(, f, g) = (1−)f +g
and p(, fe, ge) = (1 − )fe + e
g , a sufficient condition is χ2 p(, fe, ge), p(, f, g) . n−1 (see
− 1
Lemma 6.1), which leads to the choice of e
h at the order e
h  n2 2β1 +1 . As a consequence,
9

an error of order

2

2β1

−
|f (0) − fe(0)|2  2 h2β0  2e
h2β1   2β1 +1 n 2β1 +1

cannot be avoided. Recall that the relation hβ0  e
hβ1 is given by the construction. A rigorous
proof of Theorem 2.3 will be given in Section 6.2.

3

Adaptation Theory with Structured Contamination

3.1

Summary of Results

To achieve the minimax rate in Theorem 2.1, the kernel density estimator (5) requires the
knowledge of contamination proportion  and smoothness (β0 , β1 ). In this section, we discuss
adaptive procedures to estimate f (0) without knowing these numbers. However, adaptation
to  or to (β0 , β1 ) is not free, and one can only achieve slower rates than the minimax rate
(4). The adaptation cost varies for each different scenario. A summary of our results is listed
below.
• When the contamination proportion is unknown, the best rate that can be achieved is
n

2β0
0 +1

− 2β

∨ 2 .

• When the smoothness parameters are unknown, the best possible rate is





− 2β0

− 2β1
2β0 +1
2β1 +1
2
 2

n
n

 ∨  (1 ∧ m)2 ∨ 
 2β1 +1  .
log n
log n
• When both the contamination proportion and the smoothness are unknown, the optimal
rate becomes

− 2β0
2β0 +1
n
∨ 2 .
log n
Compared with the minimax rate (4), the ignorance of the contamination proportion implies
that m is replaced by 1 in the rate, while the ignorance of the smoothness implies that n is
replaced by n/ log n in the rate.

3.2

Unknown Contamination Proportion

1
The kernel density estimator (5) depends on  in two ways: the normalization through n(1−)
and the optimal choice of bandwidth h. Without the knowledge of , we consider the following
estimator
 
n
1X1
Xi
b
fh (0) =
K
.
(8)
n
h
h
i=1

The first difference between (8) and (5) is the normalization. When  is not given, we can
only use n1 in (8). Moreover, the choice of h in (8) cannot depend on .
10

Theorem 3.1. For the estimator fb(0) = fbh (0) with some K ∈ Kbβ0 ∨β1 c (L) and h = n
we have

2
2β0
−
sup
Epn fb(0) − f (0) . n 2β0 +1 ∨ 2 .

− 2β 1+1
0

,

p(,f,g)∈M(,β0 ,β1 ,L0 ,L1 ,m)
1

−
With the choice h = n 2β0 +1 , fbh becomes the classical nonparametric density estimator.
The contamination results in an extra 2 in the rate compared with the classical nonparametric minimax rate, regardless of the values of m and β1 . Note that in the current setting,
the error fbh (0) − f (0) has the following decomposition,

(fbh (0) − Efbh (0)) + (Efbh (0) − (1 − )f (0) − g(0)) + (g(0) − f (0)).

(9)

The difference between (6) and (9) is resulted from different normalizations in (5) and (8).
Some standard calculation gives the bound
E(fbh (0) − f (0))2 .

1
∨ h2β0 ∨ 2 ,
nh
−

1

which implies the optimal choice of bandwidth h = n 2β0 +1 , and thus the rate in Theorem
3.1. A detailed proof is given in Section 6.1.
In view of the form of the minimax rate (4), the rate given by Theorem 3.1 can be obtained
by replacing the 2 (1 ∧ m)2 in (4) with 2 . In other words, without the knowledge of , one
cannot achieve the rate 2 (1∧m)2 with any estimator. The necessity of increasing the optimal
rate from 2 (1 ∧ m)2 to 2 is given by the following theorem.
Theorem 3.2. Consider two models M(, β0 , β1 , L0 , L1 , m) and M(e
, β0 , β1 , L0 , L1 , m) with
different contamination proportions. For any estimator fb(0) that satisfies
sup


2
Epn fb(0) − f (0) ≤ Ce
2 ,

p(,f,g)∈M(e
,β0 ,β1 ,L0 ,L1 ,m)

for some constant C > 0, there must exist another constant C 0 > 0, such that for  ≥ C 0e
,
we have

2
sup
Epn fb(0) − f (0) & 2 .
p(,f,g)∈M(,β0 ,β1 ,L0 ,L1 ,m)

Theorem 3.2 shows that it is impossible to achieve a rate that is faster than 2 even
over only two different contamination proportions. The proof of Theorem 3.2 relies on the
following construction,
f = f0 ,
g = c1 a(c1 x),
−e

1−
f0 +
c1 a(c1 x),
fe =
1−e

1−e

ge = c1 a(c1 x).
11

With an appropriate choice of the constant c1 > 0, we have (1−)f +g ∈ M(, β0 , β1 , L0 , L1 , m)
and (1 − e
)fe + e
ge ∈ M(e
, β0 , β1 , L0 , L1 , m). Moreover, it is easy to check that
(1 − )f + g = (1 − e
)fe + e
ge.
In other words, a model with contamination proportion  can also be written with a mixture
that uses a different e
. Unless the contamination proportion is specified, one cannot tell the
difference between (1 − )f + g and (1 − e
)fe + e
ge. This leads to a lower bound of the error,
2
2
e
which is of order |f (0) − f (0)|   . A rigorous proof of Theorem 3.2 that uses a constrained
risk inequality in [1] is given in Section 6.3.

3.3

Unknown Smoothness

In this section, we consider the case that the smoothness numbers are unknown, but the
contamination proportion is given. In view of the kernel density estimator (5) that achieves
1
because of the knowledge of
the minimax rate, we can still use the normalization by n(1−)
, but the bandwidth h needs to be picked in a data-driven way. For a given h, define
 
n
X
1
Xi
1
b
fh (0) =
K
.
n(1 − )
h
h
i=1

With a discrete set H and some constant c1 > 0, Lepski’s method [18, 19, 20] selects a
data-driven bandwidth through the following procedure,
(
)
r
log
n
b
h = max h ∈ H : |fbh (0) − fbl (0)| ≤ c1
, ∀l ≤ h, l ∈ H .
(10)
nl
If the set that is maximized over is empty, we will use the convention b
h = n1 . The estimator
fbbh (0) that uses a data-driven bandwidth enjoys the following guarantee.
Theorem 3.3. Consider the adaptive kernel density estimator fb(0) = fbbh (0) with the band
1
and c1
width defined by (10). In (10), we set H = 1, 21 , · · · , 21m such that 21m ≤ n1 < 2m−1
to be a sufficiently large constant. The kernel K is selected from Kl (L) with a large constant
l ≥ bβ0 ∨ β1 c. Then, we have

2
sup
Epn fb(0) − f (0)
p(,f,g)∈M(,β0 ,β1 ,L0 ,L1 ,m)






− 2β0
− 2β1

2β0 +1
2β1 +1
2
 2

n
n
 ∨  (1 ∧ m)2 ∨ 
. 
 2β1 +1  .
log n
log n
Lepski’s method is known to be adaptive over various nonparametric classes, and it can
achieve minimax rates up to a logarithmic factor without knowing the smoothness parameter
[17]. Theorem 3.3 shows that this is also the case with contaminated observations. With an
1
adaptive kernel density estimator normalized by n(1−)
, the minimax rate (4) is achieved up
to a logarithmic factor in Theorem 3.3.
12

The comparison between the rate given by Theorem 3.3 and the minimax rate (4) reveals
− 2β0

2β0 +1
two differences. The first adaptation cost is characterized by logn n
, compared with
n


2β0
0 +1

− 2β

n
log n

−

in (4). Previous work in adaptive nonparametric estimation [1, 17, 2] implies that
2β0
2β0 +1

cannot be improved by a procedure that is adaptive to the smoothness. The

− 2β1
2β1
2
2
2β1 +1
−
n
second adaptation cost is given by log n
 2β1 +1 , compared with n 2β1 +1  2β1 +1 in (4).

− 2β1
2
2β1 +1
In the next theorem, we show that the rate logn n
 2β1 +1 cannot be improved without
the knowledge of the smoothness numbers.
e0 , L
e 1 , m) with
Theorem 3.4. Consider two models M(, β0 , β1 , L0 , L1 , m) and M(, βe0 , βe1 , L
different smoothness numbers. We assume that β0 ≥ β1 and n2 ≥ (log n)2 . For any estimator fb(0) that satisfies

− 2β1
2
2
e +1
2β
n
1
b
f (0) − f (0) ≤ C
 2βe1 +1 ,
log n
e

sup


Epn

e 0 ,L
e 1 ,m)
p(,f,g)∈M(,βe0 ,βe1 ,L

for some constant C > 0, we must have
sup



Epn fb(0) − f (0)

p(,f,g)∈M(,β0 ,β1 ,L0 ,L1 ,m)

2


&

n
log n

−

2β1
2β1 +1

2

 2β1 +1 ,

for (β0 , β1 , L0 , L1 ) such that β0 ≤ βe0 and β1 < βe1 .
Similar to the statement of Theorem 3.2, Theorem 3.4 shows that it is impossible to
− 2β1

2
2β1 +1
n
achieve a rate that is faster than log n
 2β1 +1 across two function classes with different
smoothness numbers. We remark that the assumptions β0 ≥ β1 and n2 ≥ (log n)2 in

− 2β1
− 2β0

2
2β1 +1
2β0 +1
Theorem 3.4 are necessary conditions for logn n
 2β1 +1 to dominate logn n
.
2β

− 0
2β0 +1
Without these two conditions, logn n
is the larger term between the two, and the

− 2β0
2β0 +1
lower bound of logn n
is already in the literature.

− 2β0

− 2β1
2
2β0 +1
2β1 +1
n
n
With the lower bound of log n
in the literature and log n
 2β1 +1 in Theorem 3.4, we know that the rate in Theorem 3.3 achieved by Lepski’s method cannot be
improved unless smoothness is given.

3.4

Unknown Contamination Proportion and Unknown Smoothness

When both the contamination proportion and the smoothness are unknown, we consider
Lepski’s method with a kernel density estimator normalized by n1 . Define
 
n
1X1
Xi
fbh (0) =
K
.
n
h
h
i=1

13

Then, a data-driven bandwidth b
h is selected according to (10). Again, if the set that is
maximized over is empty in (10), we will use the convention b
h = n1 . Note that this is a
fully data-driven estimator that is adaptive to both the contamination proportion and the
smoothness.
Theorem 3.5. Consider the adaptive kernel density estimator fb(0) = fbbh (0) with the band
1
and c1
width defined by (10). In (10), we set H = 1, 21 , · · · , 21m such that 21m ≤ n1 < 2m−1
to be a sufficiently large constant. The kernel K is selected from Kl (L) with a large constant
l ≥ bβ0 ∨ β1 c. Then, we have


sup

Epn

p(,f,g)∈M(,β0 ,β1 ,L0 ,L1 ,m)

0
2  n − 2β2β0 +1
b
f (0) − f (0) .
∨ 2 .
log n

Compared with the minimax rate in Theorem 2.1, the rate in Theorem 3.5 can be understood as n and 2 (1 ∧ m)2 in (4) replaced by n/ log n and 2 . In view of the results in both

− 2β0
2β0 +1
∨ 2 in Theorem 3.5 cannot be improved
Section 3.2 and Section 3.3, the rate logn n
by any procedure that is adaptive to both the contamination proportion and the smoothness.

4
4.1

Results for Arbitrary Contamination
Minimax Rates

In this section, we study a contamination model without any structural assumption on the
contamination distribution. In other words, we have i.i.d. observations generated from
(1 − )Pf + G, where Pf is a distribution on R that has a density function f , and G is an
arbitrary contamination distribution. This leads to the following model space
n
o
M(, β0 , L0 ) = (1 − )Pf + G f ∈ P(β0 , L0 ) and G is an arbitrary distribution .
This model is often referred to as Huber’s -contamination model [13, 14]. Nonparametric
function estimation under Huber’s -contamination model has recently been studied by [6, 12]
for global loss functions. In this paper, our focus is on the estimation of f (0) and the
corresponding minimax risk is defined by
R(, β0 , L0 ) = inf


2
Epn fb(0) − f (0) .

sup

fb(0) p(,f,g)∈M(,β0 ,L0 )

In contrast to the minimax rate studied in Section 2.1, we only have one parameter  that
indexes the influence of the contamination for R(, β0 , L0 ).
Theorem 4.1. Under the setting above, we have
R(, β0 , L0 )  [n

2β0
0 +1

− 2β

14

2β0

] ∨ [ β0 +1 ].

(11)

−

2β0

The minimax rate given by Theorem 4.1 only involves two terms. The first term n 2β0 +1
is the classical minimax rate for nonparametric estimation without any contamination. The
2β0

second term  β0 +1 characterizes the influence of contamination. It is interesting to see that
−

2β0

2β0

the smoothness index of f appears on both n 2β0 +1 and  β0 +1 . A larger value of β0 implies
a less influence of the contamination. This is in contrast to the rate of R(, β0 , β1 , L0 , L1 , m)
in Theorem 2.1.
β +1
− 0
The phase transition boundary of R(, β0 , L0 ) occurs at  = n 2β0 +1 . Below this level, we
have R(, β0 , L0 )  n

2β0
0 +1

− 2β

, and the contamination has no influence on the classical minimax
2β0

β +1

− 2β0 +1

rate. When  is above n 0 , the rate becomes  β0 +1 , dominated by the contamination of
data. Since we have about n contaminated observations in expectation, an optimal procedure
can achieve the classical minimax rate n

2β0
0 +1

− 2β

β0

with at most n ≤ n 2β0 +1 contaminated data

β0

points. Note that the number n 2β0 +1 is an increasing function of β0 .
Again, the minimax rate is achieved by the kernel density estimator fbh (0) =

Pn



Xi
1
i=1 h K
h
1
the normalization n(1−)
.
order , and 2 is always
1
n

Note that even with the knowledge of , we do not need to use
This is because the difference between (1 − )f (0) and f (0) is of
2β0
dominated by  β0 +1 in the minimax rate. The error fbh (0) − f (0) can be decomposed as
(fbh (0) − Efbh (0)) + (Eh fb(0) − f (0)). Then, a direct analysis shows that the risk can be
bounded by three terms,

2
1
2
E fbh (0) − f (0) .
∨ h2β0 ∨ 2 ,
(12)
nh
h
−

1

1

which leads to the optimal choice of bandwidth h = n 2β0 +1 ∨  β0 +1 , and the minimax rate
is achieved. The choice of optimal bandwidth reveals why greater smoothness implies less
influence of the contamination. For a larger β0 , the bandwidth h becomes smaller. Then
the kernel density estimator will use less contaminated observations because of the narrower
bandwidth.
The lower bound part of Theorem 4.1 can be viewed as an application of Theorem 5.1 in
[7]. A general lower bound for Huber’s -contamination model in [7] reveals a critical quantity
called modulus of continuity, defined as
n
o
ω() = sup |f (0) − fe(0)|2 : TV(Pf , Pfe) ≤ /(1 − ), f, fe ∈ P(β0 , L0 ) .
The definition of modulus of continuity goes back to [9, 10], and its relation to Huber’s contamination model is characterized in [7]. In the current setting, it can be shown that
2β0

ω()   β0 +1 , which leads to the lower bound part of Theorem 4.1. In Section 6.5, we will
give an alternative self-contained proof of the lower bound.

4.2

Adaptation to Contamination Proportion or Smoothness

The key to adaptation to either contamination proportion or smoothness
is the risk decom 
P
position (12) of the kernel density estimator fbh (0) = n1 ni=1 h1 K Xhi . We write (12) as the
15



.

sum of two terms. That is,
1
2
∨ h2β0 ∨ 2 
nh
h



2
1
+
h2 nh



+ h2β0 .

(13)

2

1
The first term h 2 + nh
is a decreasing function of h with a possibly unknown , while the
2β
0
second term h
is an increasing function of h with a possibly unknown β0 . If we know  but
2
1
do not know β0 , then we can use Lespki’s method with h 2 + nh
as an estimate of the error.
On the other hand, if we know β0 but do not know , we can then use a reverse version of
Lepski’s method with h2β0 as an estimate of the error.
Here, we want to emphasize that whether the contamination proportion  is known or not
is more than a matter of normalization. As a comparison, recall the risk decomposition for a
kernel density estimator with structured contamination in (7). There, both h2β0 and 2 h2β1
are increasing functions of h. This implies that simultaneous adaptation to both  and h is
possible through Lepski’s method, and whether  is given or not only affects the normalization
of the kernel density estimator, which is not the case for arbitrary contamination because of
(13).
Inspired by (13), we consider fbbh (0) with a data-driven bandwidth b
h. When  is known
but β0 is unknown, we use
(
!
)
r
log
n

b
h = max h ∈ H : |fbh (0) − fbl (0)| ≤ c1
+
, ∀l ≤ h, l ∈ H .
(14)
nl
l

If the set that is maximized over is empty, we take b
h = n1 . When β0 is known but  is
unknown, we use
(
)
b
h = min h ∈ H : |fbh (0) − fbl (0)| ≤ c1 lβ0 , ∀l ≥ h, l ∈ H .
(15)
If the set that is minimized over is empty, we take b
h = 1.
Theorem 4.2. Consider the adaptive kernel density estimator fb(0) = fbbh (0) with the band
width b
h given by (14) or (15). In either case, we set H = 1, 12 , · · · , 21m such that 21m ≤ n1 <
1
and c1 to be a sufficiently large constant. The kernel K is selected from Kl (L) with a
2m−1
large constant l ≥ bβ0 c. Then, we have
sup


Epn

fb(0) − f (0)

p(,f,g)∈M(,β0 ,L0 )

2


.

log n
n



2β0
2β0 +1

2β0

∨  β0 +1 .

With one of  and β0 given, Theorem 4.2 guarantees adaptive estimation with the rate
 2β0
2β0
log n 2β0 +1
∨  β0 +1 . Compared with the minimax rate in Theorem 4.1, we have an extra
n
logarithmic factor due to the ignorance of either  or β0 . This logarithmic factor cannot be
removed by any adaptive procedure in view of the results of [1, 17, 2].


16

4.3

Adaptation to Both Contamination Proportion and Smoothness?

When both contamination proportion and smoothness are unknown, the adaptation theory
with arbitrary contamination is completely different from the case with structured contamination. Since there is no constraint on the contamination distribution, a model with (, β0 )
can also be written as a different model with (e
, βe0 ). As a consequence, we can prove the
following lower bound.
e 0 , there exists a constant c > 0, such that for
Theorem 4.3. For any constants β0 , L0 , βe0 , L
given any estimator fb(0), one of the following lower bounds must be true,
e

2
2β
0
Epn fb(0) − f (0) ≥ c βe0 +1 ,

sup
p(,f,g)∈M(,β0 ,L0 )

e

2
2β
0
Epn fb(0) − f (0) ≥ c βe0 +1 .

sup
e0 )
p(0,f,g)∈M(0,βe0 ,L

Theorem 4.3 says that in order for any estimator to adapt to two classes with different
e 0 ), it is
contamination proportions and smoothness indices, say M(, β0 , L0 ) and M(0, βe0 , L
e
2β
0

impossible to achieve a rate that is better than  βe0 +1 across both classes. The form of the
e
2β
0
e +1
β
0

has a profound implication. Note that it is a function of both , the
lower bound 
contamination proportion of the first class M(, β0 , L0 ), and βe0 , the smoothness index of the
e 0 ). Therefore, an adaptive estimation rate that is a function of an
second class M(0, βe0 , L
individual class is impossible!
To be specific, we call an estimator fb(0) rate-adaptive if there exists two positive functions
r1 (·) and r2 (·), such that

2
sup
Epn fb(0) − f (0) . n−r1 (β0 ) ∨ r2 (β0 ) ,
(16)
p(,f,g)∈M(,β0 ,L0 )

uniformly over a collection of pairs (, β0 ). For example, when the contamination distribution
is restricted to those with density functions that are Hölder smooth, it is shown in Theorem
0
3.5 that adaptive estimation is possible with some r1 (β0 ) < 2β2β0 +1
and r2 (β0 ) = 2. When
the contamination distribution is arbitrary, Theorem 4.2 shows that adaptive estimation is
0
0
possible over (, β0 ) if either  or β0 is fixed with some r1 (β0 ) < 2β2β0 +1
and r2 (β0 ) = β2β
.
0 +1
In contrast, when both  and β0 are allowed to vary, rate adaptation over a collection of
(, β0 ) is impossible for any positive functions r1 (·) and r2 (·). To see why this implication
r (β )

− r1 (β0 )

can be derived from Theorem 4.3, we consider an  in the range  = o(1) and  > n
n

e )
r (β
− e 1 e0
2β0 /(β0 +1)

. Then, (16) implies

2
Epn fb(0) − f (0) . r2 (β0 ) ,

sup
p(,f,g)∈M(,β0 ,L0 )

sup


2
e
Epn fb(0) − f (0) . n−r1 (β0 ) .

e0 )
p(0,f,g)∈M(0,βe0 ,L

17

2

0

∨

We choose a small βe0 so that

2βe0
βe0 +1

< r2 (β0 ). We then have

e
2β
0 
e
n−r1 (β0 ) + r2 (β0 ) = o  βe0 +1 ,

which contradicts the lower bound given in Theorem 4.3.
In conclusion, when the contamination is arbitrary, the theory of adaptation to both
contamination proportion and smoothness is qualitatively different from adaptation to only
one of them. In comparison, when the contamination is structured, that difference is just
quantitative according to the results in Section 3. Therefore, in order to achieve sensible
error rates adaptively in a robust density estimation context, we need to either assume a
given contamination proportion, a given smoothness index, or a structured contamination
distribution.

5

Discussion

5.1

Extensions to Multivariate Settings

The results in the paper can all be extended to robust multivariate density estimation. We
define a d-dimensional isotropic Hölder class as follows,
)
(
Σd (β, L) =

f : Rd → R max |∇l f (x1 ) − ∇l f (x2 )| ≤ Lkx1 − x2 kβ−bβc for any x1 , x2 ∈ Rd

,

l∈I(β)

where we use I(β) to denote the set of multi-indices {l = (l1 , ..., ld ) l1 + · · · + ld = bβc}. The
class of density functions is defined as
(
)
Z
Pd (β, L) =

f : Rd → [0, ∞) f ∈ Σd (β, L),

f =1 .

Note that the dimension d is assumed to be a constant. Then, the two contamination models
considered in the paper are extended as
n
o
Md (, β0 , β1 , L0 , L1 , m) = (1 − )f + g f ∈ Pd (β0 , L0 ), g ∈ Pd (β1 , L1 ), g(0) ≤ m ,
and
n
o
Md (, β0 , L0 ) = (1 − )Pf + G f ∈ Pd (β0 , L0 ) and G is an arbitrary distribution .
Similarly, we can define the corresponding minimax rates Rd (, β0 , β1 , L0 , L1 , m) and Rd (, β0 , L0 ).
Theorem 5.1. For the two contamination models on Rd , we have
Rd (, β0 , β1 , L0 , L1 , m)  [n

2β0
0 +d

− 2β

] ∨ [2 (1 ∧ m)2 ] ∨ [n

and
Rd (, β0 , L0 )  [n

2β0
0 +d

− 2β

18

2β0

] ∨ [ β0 +d ].

2β1
1 +d

− 2β

2d

 2β1 +d ],

The extra factor of dimension d makes the interpretation of results even more interesting.
−

β0 +d

For example, the phase transition boundary of Rd (, β0 , L0 ) now occurs at  = n 2β0 +d . This
implies that the influence of contamination becomes more severe as the dimension grows. In
contrast, the minimax rate of Rd (, β0 , β1 , L0 , L1 , m) leads to a completely different interpretation. For example, when m ≥ 1, we have
Rd (, β0 , β1 , L0 , L1 , m)  n

2β0
0 +d

− 2β

∨ 2 .

The second term 2 does not change with the dimension d, and the phase transition boundary
−

2β0

−

β0

between n 2β0 +d and 2 is at  = n 2β0 +d , which increases with respect to d. This suggests
that the influence of contamination becomes less severe as d grows. In short, the contamination influence on density estimation can be drastically different in a multivariate setting,
depending on whether the contamination distribution is structured or arbitrary.
Besides the minimax rates, the adaptation results in Section 3 and Section 4 can all be
easily extended to multivariate settings. Similar adaptation costs can be derived as in the
one-dimensional situation.

5.2

Consistency in the Hardest Scenario

When there is no constraint on the contamination distribution, adaptation is impossible
over both contamination proportion and smoothness in the sense of (16). One may wonder
whether there is still anything to do in such a scenario with almost nothing is assumed. In
this section, we show that consistency is still possible under this hardest scenario.
Before introducing the procedure, we remark that achieving consistency without knowing
 and β0 is a non-trivial problem due to the risk decomposition (12) for a kernel density
estimator. According to (12), a choice of bandwidth that leads to consistency must satisfy
nh → ∞, h → 0 and h/ → ∞. Note that the first and the second requirements can
be satisfied easily with a choice of h that does not depend on any model parameter. For
example, one can choose h = n−1/2 . However, the third requirement h/ → ∞ is problematic
without the knowledge of . For any choice of h → 0, there is an adversarial  to make
h/ → ∞ fail.
Despite the above difficulty, we show that a data-driven bandwidth leads to consistency
e
if we know that the smoothness
 β0 has a lower bound β0 . We consider a kernel density
P
n
X
estimator fbh (0) = n1 i=1 h1 K hi . Then, we choose h by the reverse version of Lepskis’
method that is similar to (15). We define b
h by
(

)
βe0

b
h = min h ∈ H : |fbh (0) − fbl (0)| ≤ c1 l , ∀l ≥ h, l ∈ H .

(17)

Again, we use the convention that if the set that is minimized over is empty, we take b
h = 1.
Theorem 5.2. Consider the kernel density estimator fb(0) = fbbh (0) with the bandwidth b
h given
 1
1
1
1
1
by (17). We set H = 1, 2 , · · · , 2m such that 2m ≤ n < 2m−1 and c1 to be a sufficiently
19

large constant. The kernel K is selected from Kl (L) with a large constant l ≥ bβ0 c. Then, as
n → ∞ and  → 0. we have

2
sup
Epn fb(0) − f (0) → 0,
p(,f,g)∈M(,β0 ,L0 )

if β0 ≥ βe0 .
Note that the requirements n → ∞ and  → 0 are necessary conditions of consistency
given the minimax rate (11). The procedure does not require knowledge of  or β0 , and thus
consistency can be achieved without knowing  and β0 even if adaptation is impossible. The
procedure (17) uses a conservative βe0 in the reverse version of Lepski’s method, and can be
viewed as an extension of (15) that uses the true smoothness index β0 .

6

Proofs

6.1

Proofs of Theorem 2.2 and Theorem 3.1

Proof of Theorem 2.2. Decompose the error as

b
b
b
f (0) − f (0) = (f (0) − Ef (0)) + Efb(0) − f (0) −




g(0) +
g(0),
1−
1−

where the first term is the stochastic error, the second term stands for bias, and the third
term is the misspecification error caused by contamination.
For the variance term, we have
 
P
n
Xi
1
K
i=1 h
Var( h1 K( X
h
2
h ))
b
b
=
E(f (0) − Ef (0)) = Var 
,
n(1 − )
n(1 − )2
where

Var

1
K
h



X
h



Z
≤

1 2 x
1
K
((1 − )f (x) + g(x))dx .
2
h
h
h

Z

1 2 x
1
K
dx . .
h
h
h

This gives the variance bound
E(fb(0) − Efb(0))2 .

1
.
nh

(18)

For the bias term we have
Z
Z
1 x
1 x

Efb(0) =
K
f (x)dx +
K
g(x)dx.
h
h
1−
h
h

R
Since f ∈ P(β0 , L0 ) and g ∈ P(β1 , L1 ), we have | h1 K hx (f (x) − f (0))dx| . hβ0 and

R
| h1 K hx (g(x) − g(0))dx| . hβ1 . See [23, Chapter 1.2] for an explicit bias calculation.
Adding up the two bias bounds, we get
Efb(0) − f (0) −


g(0) . hβ0 + hβ1 .
1−
20

(19)

For the last term, it is easy to see that

2

g(0) . 2 (m ∧ 1)2 ,
1−

(20)

since g(0) ≤ m by the assumption and g(0) . 1 by the fact that g ∈ P(β1 , L1 ).
With the relation E(A1 +A2 +A3 )2 . EA21 +EA22 +EA23 and the three bounds in (18), (19)
and (20), we conclude the proof by the specific choice of h = n

− 2β 1+1
0

∧n

− 2β 1+1 − 2β 2+1
1



1

.

Proof of Theorem 3.1. The error decomposes as
fb(0) − f (0) = (fb(0) − Efb(0)) + (Efb(0) − (1 − )f (0) − g(0)) + (g(0) − f (0)).
1
for the variance
Using the same argument that leads to (18), we have E(fb(0) − Efb(0))2 . nh
b
term. The bias term (Ef (0) − (1 − )f (0) − g(0)) can be further decomposed as
Z
Z
1 x
1 x
(1 − )
K
(f (x) − f (0))dx + 
K
(g(x) − g(0))dx.
h
h
h
h

Therefore, the same argument that leads to (19) also gives the bound
|Efb(0) − (1 − )f (0) − g(0)| . hβ0 + hβ1 .
For the last term, we have |g(0) − f (0)| . . Combining the three bounds above, we have

2
1
E fb(0) − f (0) .
+ h2β0 + 2 .
nh
Choose h = n

6.2

− 2β 1+1
0

, and the proof is complete.

Proof of Theorem 2.3

The proof of Theorem 2.3 mainly relies on Le Cam’s two-point argument. The method is
summarized by the following lemma.
Lemma 6.1. Consider two distributions Pθ0 and Pθ1 whose parameters of interest are separated by ∆ = |Tθ0 − Tθ1 |. Assume χ2 (Pθ0 , Pθ1 ) ≤ α. Then, we have

2 1
b
inf sup Eθ T − Tθ ≥ e−α ∆2 .
8
Tb θ∈{θ0 ,θ1 }
We refer the readers to [24] and [23, Chapter 2.3] for rigorous proofs. In the setting of
Theorem 2.3, we need to find two pairs of density functions (f, g) and (fe, ge) that satisfy
f, fe ∈ P(β0 , L0 ), g, ge ∈ P(β1 , L1 ) and g(0) ∨ ge(0) ≤ m. Since we are working with i.i.d.
observations, it is sufficient to show that


χ2 p(, fe, ge), p(, f, g) . n−1 .
Then, Lemma 6.1 implies R(, β0 , β1 , L0 , L1 , m) & |f (0) − fe(0)|2 .
The lower bound of Theorem 2.3 contains three terms. We thus split the proof into three
parts, and then combine the three arguments in the end.
21

Lemma 6.2. We have
R(, β0 , β1 , L0 , L1 , m) & n

2β0
0 +1

− 2β

.

Proof. The proof uses a similar argument in [23, Chapter 2.5]. Since we are dealing with a
setting with contamination, we still give a proof to be self contained. We define the following
four functions,
g(x) = ge(x) = c1 a(c1 x),
f (x) = f0 (x),
x
fe(x) = f0 (x) + c2 hβ0 b
.
h
Here, we take f0 as the density function of some normal distribution with mean zero so that
f0 ∈ P(β0 , L0 /2). The functions a(x) and b(x) are given by Lemma 2.1 and Lemma 2.2.
We first verify that for appropriate choices of c1 , c2 and h ≤ 1, the constructed functions are
well-defined densities in the desired parameter spaces.
• We have f ∈ P(β0 , L0 ) by construction. Since h ≤ 1, b(x/h) is compactly supported
on an area where f0 is lower bounded by some positive constant. Thus, with a c2 > 0
R
that is sufficiently small, fe is nonnegative. The fact fe = 1 can be derived from the
property of b in Lemma 2.2. Hence, fe ∈ P(β0 , L0 ) when c2 is small enough.
• With a sufficiently small c1 > 0, we have g, ge ∈ P(β1 , L1 ).
• By a(0) = 0 according to Lemma 2.1, we get |g(0)| ∨ |e
g (0)| ≤ m.
We use the notation p = (1 − )f + g and q = (1 − )fe + e
g . Note that p can be lower
bounded by a positive constant on the interval [−1, 1] according to its definition. Moreover,
we have
x
,
p(x) − q(x) = −(1 − )c2 hβ0 b
h

and the support of b hx is [−h, h] ⊂ [−1, 1]. This leads to the bound
2

Z

1

χ (q, p) =
−1

(p − q)2
.
p

Z

2

(p − q)  h

In order that nχ2 (q, p) . 1, we can choose h = n

2β0

− 2β 1+1
0

Z

b2

x

 h2β0 +1 .

. This leads to

β0

−
|f (0) − fe(0)|  n 2β0 +1 .

Use Lemma 6.1, and the proof is complete.
Lemma 6.3. We have
R(, β0 , β1 , L0 , L1 , m) & 2 (1 ∧ m)2 .
22

h

Proof. By [23], for any p ∈ P(β, L), there exists a constant pmax such that supx |p(x)| ≤ pmax .
Therefore, it is sufficient to consider m that is bounded by some constant, say m ≤ 1.
Consider the following four functions,
f (x) = f0 (x),

mb(x),
1−
g(x) = c2 a(c2 x) + c1 mb(x),

fe(x) = f0 (x) + c1

ge(x) = c2 a(c2 x).
Here, we take f0 as the density function of some normal distribution with mean zero so
that f0 ∈ P(β0 , L0 /2). The functions a(x) and b(x) are given by Lemma 2.1 and Lemma
2.2. With appropriate choices of the constants c1 , c2 > 0, f, fe, g, ge are well-defined density
functions that belong to the desired function classes.
• By Lemma 2.1, We have f0 ∈ P(β0 , L0 /2) ⊂ P(β0 , L0 ) by construction. Since f0
is strictly positive on [−1, 1] and b is compactly supported on [−1, 1], we have fe ∈
P(β0 , L0 ) for some sufficiently small constant c1 > 0 according to the properties of b
listed in Lemma 2.2.
• By definition of a, we have ge ∈ P(β1 , L1 /2) for some sufficiently small c2 > 0 according
to Lemma 2.1. Since b(x) only takes negative values when c2 a(c2 x) is lower bounded
by a positive constant, g is nonnegative and g ∈ P(β1 , L1 ) when c1 is small enough.
• We also have |g(0)| ∨ |e
g (0)| ≤ m for a sufficiently small c1 because a(0) = 0 and |b(0)|
is bounded by a constant according to Lemma 2.1 and Lemma 2.2.
In summary, we have
(1 − )f + g, (1 − )fe + e
g ∈ M(, β0 , β1 , L0 , L1 , m).
Moreover, according to our construction, we have
(1 − )f + g = (1 − )fe + e
g,
and
|f (0) − fe(0)| = c1


m|b(0)| & m,
1−

where we have used |b(0)| & 1 by Lemma 2.2. Finally, using Lemma 6.1, we obtain the
desired lower bound result.
Lemma 6.4. Assume β1 ≤ β0 and n2 ≥ 1. Then, we have
R(, β0 , β1 , L0 , L1 , m) & n

23

2β1
1 +1

− 2β

2

 2β1 +1 .

Proof. Consider the following four functions,
f (x) = f0 (x),





x

2(x + c4 )
2(x − c4 )
hβ0 l
− hβ0 l
,
− hβ0 l
1−
h
h
h




 

x
2(x + c4 )
x
2(x − c4 )
β0
β0
β1
β0
e
g(x) = c1 a(c1 x) + c2 h l
−h l
− c3 h b
,
−h l
e
h
h
h
h

fe(x) = f0 (x) + c2

ge(x) = c1 a(c1 x).
Since the proof relies on perturbing a density at a point where it is 0, the verification of
nonnegativity is more delicate, which motivates another tuning constant controlling the center
of the negative part of the perturbation. Here, we take f0 as the density function of some
normal distribution with mean zero so that f0 ∈ P(β0 , L0 /2). The functions a(x) and b(x) are
given by Lemma 2.1 and Lemma 2.2. The numbers h and e
h are chosen so that the following
equation is satisfied:
c2 hβ0 l(0) = c3e
hβ1 b(0).
(21)
Now, we verify that with appropriate choices of constants c1 , c2 , c3 , c4 , the constructed functions belong to the parameter spaces.
• The functions f and ge are automatically density functions by definition. Note that

4)
we can choose a small constant c4 so that the negative perturbation −hβ0 l 2(x−c
−
h


4)
hβ0 l 2(x+c
has a support in a region where both f0 and c1 a(c1 x) are bounded beh
low by a positive constant. This immediately implies that fe(x)≥ 0 for all x with a
sufficiently small constant c2 . Similarly, the support of −c3e
h, e
h], which
hβ1 b x is [−e
e
h

is contained in a region where c1 a(c1 x) is bounded below by a positive constant for a
sufficiently small e
h. Therefore, g(x) ≥ 0 for all x with a sufficiently small constant c3 .
R
R
We also note that fe = g = 1 according to the definitions.
• When c1 , c2 , c3 are chosen small enough, we have f, fe ∈ Σ(β0 , L0 ) and g, ge ∈ Σ(β1 , L1 ).
Here g ∈ Σ(β1 , L1 ) is a consequence of the assumption that β1 ≤ β0 .
• Finally, we have l(2c4 /h) = l(−2c4 /h) = 0 for a sufficiently small h. This implies
g(0) = ge(0) = 0 because of (21). Therefore, |g(0) ∨ ge(0)| ≤ m.
In summary, we have
(1 − )f + g, (1 − )fe + e
g ∈ M(, β0 , β1 , L0 , L1 , m).
Besides the properties listed above, we also note that both f and g can be bounded from
below by some positive constant on the interval [−1, 1], if the constants c2 , c3 are sufficiently
small. This implies that the density (1 − )f + g is lower bounded by some positive constant
on the interval [−1, 1].

24

Now, according to the above construction, for p = (1 − )f + g and q = (1 − )fe+ e
g , we
have
 
x
β1
e
.
p(x) − q(x) = −c3 h b
e
h
 
Given that the support of b ex is within [−e
h, e
h] ⊂ [−1, 1] with a sufficiently small e
h, we
h
have
 
Z
Z
Z 1
x
(p − q)2
 2e
h2β1 +1 .
. (p − q)2  2e
h2β1 b2
χ2 (q, p) =
e
p
h
−1

− 1
In order that nχ2 (q, p) . 1, it is sufficient to choose e
h  n2 2β1 +1 . The condition n2 ≥ 1
implies that e
h can be picked sufficiently small. Moreover, with the relation (21), we have
|f (0) − fe(0)| = c2

β
1

− 1
hβ0 l(0)  hβ0  e
hβ1   2β1 +1 n 2β1 +1 .
1−

Finally, using Lemma 6.1, we obtain the desired lower bound result.
We combine the results of Lemma 6.2, Lemma 6.3 and Lemma 6.4.
Proof of Theorem 2.3. In order that the third term n
it is necessary that 2 ≥ n
we have

2β1 −2β0
2β0 +1

2β1
1 +1

− 2β

2

 2β1 +1 dominates the other two,

. This implies both β1 ≤ β0 and n2 ≥ 1. By Lemma 6.4,

R(, β0 , β1 , L0 , L1 , m) & n

2β1
1 +1

− 2β

2

 2β1 +1 .

When the first or the second term dominate, we use Lemma 6.2 and Lemma 6.3, and obtain
R(, β0 , β1 , L0 , L1 , m) & [n

2β0
0 +1

− 2β

] ∨ [2 (1 ∧ m)2 ].

Hence, the proof is complete.

6.3

Proofs of Theorem 3.2 and Theorem 3.4

The proofs of both theorems rely on the following constrained risk inequality by [1].
Lemma 6.5. Consider two distributions Pθ0 and Pθ1 whose parameters of interest are separated by ∆ = |Tθ0 − Tθ1 |. For any estimator Tb, assume
Eθ0 (Tb − Tθ0 )2 ≤ δ 2 .
Then, whenver δI ≤ ∆, we have
Eθ1 (Tb − Tθ1 )2 ≥ (∆ − δI)2 ,
r
where I =

R

dPθ2
1
dPθ0 .

25

Proof of Theorem 3.2. We consider the following four functions,
f = f0 ,
g = c1 a(c1 x),
1−
−e

fe =
f0 +
c1 a(c1 x),
1−e

1−e

ge = c1 a(c1 x).
Here, we take f0 as the density function of some normal distribution with mean zero so that
f0 ∈ P(β0 , L0 /2). The function a(·) is given by Lemma 2.1. The constant c1 is sufficiently
small so that c1 a(c1 x) belongs to both P(β0 , L0 /2) and P(β1 , L1 /2). Now it is easy to check
that f, fe ∈ P(β0 , L0 ), g, ge ∈ P(β1 , L1 ) and g(0) ∨ ge(0) = 0 ≤ m, so that the constructed
functions are well-defined densities in the parameter spaces.
It is easy to check that
(1 − )f + g = (1 − e
)fe + e
ge.
R 2
This implies q /p = 1 for p = (1 − )f + g and q = (1 − e
)fe + e
ge. We also have
−e

f (0).
f (0) − fe(0) =
1−e


2
According to Lemma 6.5, suppose there is an estimator fb(0) that satisfies Epn fb(0) − f (0) ≤
Ce
2 , we must have
Eqn (fb(0) − fe(0))2 ≥



2
−e

f (0) − C 1/2e
 .
1−e


Therefore, there exists a constant C 0 > 0, such that for  ≥ C 0e
, Eqn (fb(0) − fe(0))2 & 2 , and
the proof is complete.
Proof of Theorem 3.4. We construct the following four functions
fe(x) = f0 (x),





x
2(x − c4 )
2(x + c4 )

β0
β0
β0
f (x) = f0 (x) − c2
h l
−h l
−h l
,
1−
h
h
h
ge(x) = c1 a(c1 x),





 
x
2(x + c4 )
x
2(x − c4 )
β0
β0
β0
β1
e
g(x) = c1 a(c1 x) + c2 h l
−h l
−h l
− c3 h b
.
e
h
h
h
h
The construction is similar to that in the proof of Lemma 6.4. The difference is that the
perturbation is now put on both f and g. Here, we take f0 as the density function of some
normal distribution with mean zero so that f0 ∈ P(β0 , L0 /2). The functions a(x) and b(x) are
given by Lemma 2.1 and Lemma 2.2. The numbers h and e
h are chosen so that the following
equation is satisfied:
c2 hβ0 l(0) = c3e
hβ1 b(0).
(22)
26

Similar to the argument used in Lemma 6.4, it is not hard to check that with appropriate
e 0 ), ge ∈ P(βe1 , L
e 1 ), f ∈ P(β0 , L0 ) and
choices of the constants c1 , c2 , c3 , we have fe ∈ P(βe0 , L
g ∈ P(β1 , L1 ), given that βe0 ≥ β0 ≥ β1 and βe1 > β1 . The numbers h and e
h are both required
to be sufficiently small. We also have g(0) = ge(0) = 0 according to the definition with an
appropriate choice of c4 . Then, the constructed functions are well-defined densities in the
parameter spaces.
With the notation p = (1 − )f + g and q = (1 − )fe + e
g , we check the quantities in
Lemma 6.5. Note that
 
x
β1
e
|p(x) − q(x)| = c3 h b
.
e
h
 
With a similar argument in the proof of Lemma 6.4, the function b ex is supported within
h
[−e
h, e
h] ⊂ [−1, 1], and p(x) is lower bounded by some constant uniformly over x ∈ [−1, 1].
This implies,

n


Z 2  n2
Z
Z


(q − p)2 2
C1 n
q
2
= 1+
≤ exp
(p − q) ≤ exp C10 n2e
h2β1 +1 .
I=
p
p
2
Moreover, we also have
∆ = |f (0) − fe(0)| = c2


hβ0 l(0),
1−

and
δ=C


n2
log n

1/2



n
log n

−

e
β
1
e +1
2β
1

1

 2βe1 +1 .

c

In order that I ≤
for some sufficiently small constant c > 0, we can choose e
h 
1
 2 −
2β1 +1
n
, which is always possible with the condition n2 ≥ (log n)2 . According to
log n
− β1

1
2β1 +1
the relation (22), we have ∆   2β1 +1 logn n
. Plugging these quantities into the
constrained risk inequality in Lemma 6.5 and using β1 < βe1 , we get the desired lower bound.

6.4

Proofs of Theorem 3.3 and Theorem 3.5

The proofs of the two theorems are similar. Thus, we give a detailed proof of Theorem 3.5
first, and then sketch the proof of Theorem 3.3.
Proof of Theorem 3.5. For every bandwidth h, the error decomposes as
fbh (0) − f (0) = (fbh (0) − Efbh (0)) + (Efbh (0) − (1 − )f (0) − g(0)) + (g(0) − f (0)),

(23)

where the three terms correspond to a stochastic part that depends on h, a deterministic
part that depends on h, and a deterministic part that does not depend on h. With the same
argument in the proof of Theorem 3.1, we have
E(fb(0) − Efb(0))2 .
27

1
,
nh

|Efb(0) − (1 − )f (0) − g(0)| . hβ0 + hβ1 ,
and
|g(0) − f (0)| . .
Define the oracle bandwidth h∗ to be the largest h ∈ H such that
r
log n
hβ0 + hβ1 ≤ c
,
nh
where the constant c > 0 will be determined later. Then it is easy to see that h∗ satisfies
r
r
log n
log n
0
β0
β1
c
≤ h∗ + h∗ ≤ c
,
(24)
nh∗
nh∗
for some constant c0 that only depends on c.
We proceed to prove that b
h ≥ h∗ with high probability. By the definition of b
h, we have
!
r
log n
P(b
h < h∗ ) ≤ P ∃l ≤ h∗ and l ∈ H s.t. |fbh∗ (0) − fbl (0)| > c1
nl
!
r
X
log n
≤
P |fbh∗ (0) − fbl (0)| > c1
.
nl
l≤h∗ ,l∈H


q
n
We derive a bound for P |fbh∗ (0) − fbl (0)| > c1 log
for each l ≤ h∗ and l ∈ H. Due to
nl
the error decomposition (23), we have:
|fbh∗ (0) − fbl (0)| ≤ C(hβ∗ 0 + hβ∗ 1 ) + |fbh∗ (0) − Efbh∗ (0)| + |fbl (0) − Efbl (0)|,
for some constant C > 0. By (24), the bias term can be controlled as
r
r
log n
c1 log n
β0
β1
C(h∗ + h∗ ) ≤ C × c
≤
,
nh∗
2
nl
for a sufficiently small c > 0. Thus, we have
c1
P(b
h < h∗ ) ≤
P |fbh∗ (0) − Efbh∗ (0)| + |fbl (0) − Efbl (0)| ≥
2
l≤h∗ ,l∈H
!
r
X
c1 log n
b
b
≤
P |fh∗ (0) − Efh∗ (0)| ≥
4
nh∗
l≤h∗ ,l∈H
!
r
X
c
log
n
1
+
P |fbl (0) − Efbl (0)| ≥
.
4
nl
X

l≤h∗ ,l∈H

For any l ≤ h∗ and l ∈ H, we use Bernstein’s inequality, and get


P |fbl (0) − Efbl (0)| ≥ t
n

1 X −1
≤ P
l K(Xi /l) − El−1 K(X/l) ≥ t
n
i=1


nt2 /2
≤ 2 exp − 2
,
σ + M t/3
28

!

r

log n
nl

!

where we choose t =

c1
4

q

log n
nl ,

and σ 2 and M have bounds

σ 2 ≤ El−2 K 2 (X/l) . l−1 and M . l−1 .
This implies the bound
c1
P |fbl (0) − Efbl (0)| ≥
4

r

log n
nl

!

≤ 2 exp −C 0 log n ,

(25)

where the constant C 0 > 0 can be arbitrarily large given a sufficiently large c1 > 0. For
example, we set a large enough c1 > 0 so that C 0 = 3. This gives
P(b
h < h∗ ) ≤ 4|H|n−3 . n−3 log n.
Now, on the event {b
h ≥ h∗ }, the risk decomposes as
|fbbh (0) − f (0)| ≤ |fbbh (0) − fbh∗ (0)| + |fbh∗ (0) − f (0)|.
Due to the definition of b
h, the first term satisfies
r
|fbbh (0) − fbh∗ (0)| ≤ c1

log n
.
nh∗

(26)

For the second term, the error decomposition and the relation (24) implies
E|fbh∗ (0) − f (0)|2 .

log n
+ 2 .
nh∗

Therefore, we have
E(fbbh (0) − f (0))2
≤ E((fbbh (0) − f (0))2 : b
h ≥ h∗ ) + E((fbbh (0) − f (0))2 : b
h < h∗ )


≤ 2E((fbbh (0) − fbh∗ (0))2 : b
h ≥ h∗ ) + 2E((fbh∗ (0) − f (0))2 : b
h ≥ h∗ ) + O n2 P(b
h < h∗ )
log n
log n
+ 2 +
nh∗
n

 2β0
log n 2β0 +1
.
+ 2 .
n
.

The last inequality above is by realizing that h∗ 
proof is complete.



n
log n

−

1
2β0 +1

from the relation (24). The

Proof of Theorem 3.3. The proof for Theorem 3.3 follows the same argument as that of Theorem 3.5. The only difference lies in the normalization, which leads to the error decomposition




b
b
b
b
g(0) +
g(0).
fh (0) − f (0) = (fh (0) − Efh (0)) + Efh (0) − f (0) −
1−
1−
The rest of the details are the same and is omitted.
29

6.5

Proof of Theorem 4.1

We split the proof into upper and lower bounds. We first prove the following upper bound.
1

−
Theorem 6.1. For the estimator fb(0) = fbh (0) with some K ∈ Kbβ0 c (L) and h = n 2β0 +1 ∨
1

 β0 +1 , we have

2
2β0
2β0
−
Epn fb(0) − f (0) . [n 2β0 +1 ] ∨ [ β0 +1 ].

sup
p(,f,g)∈M(,β0 ,L0 )

Proof. Decompose the error as
fbh (0) − f (0) = (fbh (0) − Efbh (0)) + (Eh fb(0) − f (0)),
where the first term is the stochastic error and the second term is the bias. For the first term,
we have

 
1
X
1
K
,
E(fbh (0) − Efbh (0))2 = Var
n
h
h
and

Var

1
K
h



X
h



Z

Z
1 2 x
1 2 x
≤ (1 − )
K
f
(x)dx
+

K
dG(x)
h2
h
h2
h
Z
Z
1
1 2 x

.
K
dx + 2 dG(x)
h
h
h
h
1

.
+ .
h h2

Therefore, we have

1
+
.
E(fbh (0) − Efbh (0))2 .
nh nh2

(27)

For the bias term, we have
Z
Efbh (0) − f (0) = (1 − )
where the first term has bound
Z

1 x
(f (x) − f (0))dx + 
K
h
h

Z

1 x
dG(x) − f (0),
K
h
h

1 x
K
(f (x) − f (0))dx . hβ0 ,
h
h

by [23, Chapter 1.2], and the next two terms can be bounded as
Z
Z
1 x



K
dG(x) − f (0) .
dG(x) + f (0) . .
h
h
h
h
Therefore, we have
|Efbh (0) − f (0)| . hβ0 +
Combine the two bounds (27) and (28), choose h = n
the proof.
30


.
h

− 2β 1+1
0

(28)
1

∨  β0 +1 , and then we complete

Now we state the lower bound.
Theorem 6.2. We have
R(, β0 , L0 ) & [n

2β0
0 +1

− 2β

2β0

] ∨ [ β0 +1 ].

Before proving this theorem, we need the following lemma.
Lemma 6.6. A function d(x) can be written as the difference of two density functions if and
only if
Z
Z
d = 0 and
|d| ≤ 2.
Proof. The “only if” part is obvious. Now assume the two conditions hold, and then for any
density function f , we have the following decomposition for d,


  

 
Z
Z
1
1
d = d+ + 1 −
|d| f − d− + 1 −
|d| f ,
2
2
where d+ and d− are the positive and negative parts of the function. The first condition
R
R
R
implies d+ = d− = 21 |d|. Thus,
  Z 

 

Z
Z
Z 
1
1
|d| f =
d− + 1 −
|d| f = 1.
d+ + 1 −
2
2

R
R 
The second condition guarantees that both d+ + 1 − 12 |d| f and d− + 1 − 12 |d| f are
nonnegative. Thus, the proof is complete.
−

2β0

Proof of Theorem 6.2. For the lower bound of the first term n 2β0 +1 , see the proof of Lemma
6.2. We give a proof for the second term. Consider the following two functions
f = f0 ,
x
fe = f0 + chβ0 b
.
h
Here, we take f0 as the density function of some normal distribution with mean zero so that
f0 ∈ P(β0 , L0 /2). The function b is defined in Lemma 2.2. The constant c is chosen small
enough so that f ∈ P(β0 , L0 ). In order that there exist g and ge so that
(1 − )f + g = (1 − )fe + e
g,
it suffices to verify the existence of densities g and ge such that

1− e
1 −  β0  x 
g(x) − ge(x) =
f (x) − f (x) = c
h b
.


h
By Lemma 6.6, it further suffices to verify the condition
Z
x
1−
c
hβ0 b
dx ≤ 2,

h
1

and this is guaranteed by taking some h   β0 +1 . Now we have g and ge such that (1−)f +g =
(1 − )fe + e
g holds. Moreover,
β0

|f (0) − fe(0)| = chβ0 b(0)   β0 +1 .
Apply Lemma 6.1, and the proof is complete.
31

6.6

Proofs of Theorem 4.2 and Theorem 5.2

We first prove Theorem 5.2. Then, the proof of Theorem 4.2 will be sketched using arguments
in the proofs of Theorem 3.5 and Theorem 5.2.
Proof of Theorem 5.2. We consider observations X1 , ..., Xn . We assume that X1 , ..., Xa are
generated from the density f with some integer a, and the remaining observations Xa+1 , ..., Xn
are generated from contamination. The number a follows Binomial(n, 1 − ). This is without
loss of generality, because the definition of fb does not depend on the order of the data
X1 , ..., Xn . Apply Bernstein’s inequality, and we get




n−a
3
P
≥ 2 ≤ exp − n .
n
8
n
n−a
−3
From now on, we assume that  ≥ 8 log
n , so that n ≤ 2 with probability at least 1 − n .
8 log n
The case  < n will be considered in the end of the proof. Moreover, the following

analysis conditions on the event n−a
n ≤ 2 , and we use P̄ and Ē to denote probability and
expectation conditioning on the random variable a.
We start by the following error decomposition,

fbh (0) − f (0) =

a

1 X −1
h K(Xi /h) − EX∼f h−1 K(X/h)
n
i=1

a
+ EX∼f h−1 K(X/h) − f (0)
n
n
1 X −1
n−a
+
h K(Xi /h) −
f (0).
n
n
i=a+1

With similar arguments used in the proof of Theorem 2.2, we have

Ē

a

1 X −1
h K(Xi /h) − EX∼f h−1 K(X/h)
n
i=1

!2
.

1
,
nh

and
EX∼f h−1 K(X/h) − f (0) . hβ0 .
Moreover,

n−a
n

≤ 2 implies that
n
1 X −1

h K(Xi /h) . ,
n
h
i=a+1

and n−a
n f (0) . . These bounds motivate us to define an oracle bandwidth h∗ that is the
smallest h ∈ H such that
r

log n
e
+
≤ hβ0 .
h
nh

32

Then it is obvious that h∗ satisfies
e
chβ∗ 0


+
≤
h∗

r

log n
e
≤ hβ∗ 0 ,
nh∗

(29)

with some constant c > 0. Now we prove that b
h ≤ h∗ holds with high probability. According
b
to the definition of h, we have


e
P̄(b
h > h∗ ) ≤ P̄ ∃l ≥ h∗ and l ∈ H s.t. |fbh∗ (0) − fbl (0)| ≥ c1 lβ0


X
e
P̄ |fbh∗ (0) − fbl (0)| ≥ c1 lβ0 .
≤
l≥h∗ ,l∈H

By the risk decomposition, for l ≥ h∗ and l ∈ H, the difference |fbh∗ (0) − fbl (0)| is bounded as
|fbh∗ (0) − fbl (0)| ≤

a

1 X −1
h∗ K(Xi /h∗ ) − EX∼f h−1
∗ K(X/h∗ )
n
i=1

a

1 X −1
l K(Xi /l) − EX∼f l−1 K(X/l)
+
n
i=1



β0
+C
+l
,
h∗

for some constant C > 0. According to (29) and the condition βe0 ≤ β0 , we have



 c
c1 e

e
e
1 e
β0
+l
≤ C hβ∗ 0 + lβ0 ≤ hβ∗ 0 + lβ0 ,
C
h∗
4
4
where the last inequality holds for a sufficiently large c1 . Thus, we have the bound

X
c1 e
c1 e 
P̄(b
h > h∗ ) ≤
P̄ |fbh∗ (0) − fbl (0)| ≥ lβ0 + hβ∗ 0
2
2
l≥h∗ ,l∈H

!
a

1 X −1
c
e
1
≤
P̄
h∗ K(Xi /h∗ ) − EX∼f h−1
hβ0
∗ K(X/h∗ ) ≥
n
4 ∗
i=1
l≥h∗ ,l∈H
!
a
X

c
1 X −1
e
1
+
P̄
l K(Xi /l) − EX∼f l−1 K(X/l) ≥ lβ0
n
4
i=1
l≥h∗ ,l∈H
!
r
a
X

1 X −1
c1 log n
−1
≤
h∗ K(Xi /h∗ ) − EX∼f h∗ K(X/h∗ ) ≥
P̄
n
4
nh∗
i=1
l≥h∗ ,l∈H
!
r
a
X

c1 log n
1 X −1
−1
+
P̄
l K(Xi /l) − EX∼f l K(X/l) ≥
,
n
4
nl
X

l≥h∗ ,l∈H

i=1

where the last inequality is by (29) and the observation that
r
r
log n
log n
βe0
βe0
≥
.
l ≥ h∗ ≥
nh∗
nl
33

Use Bernstein’s inequality in a similar way that derives (25), we obtain the bound
!
r
a

1 X −1
c1 log n
−1
≤ 2n−3 ,
P̄
l K(Xi /l) − EX∼f l K(X/l) ≥
n
4
nl
i=1

when the constant c1 is chosen to be sufficiently large. Then, we have
P̄(b
h > h∗ ) . n−3 log n.
On the event b
h ≤ h∗ , the error decomposes as
|fbbh (0) − f (0)| ≤ |fbbh (0) − fbh∗ (0)| + |fbh∗ (0) − f (0)|.
Due to definition of b
h, the first term is bounded as
e
|fbbh (0) − fbh∗ (0)| ≤ c1 hβ∗ 0 .

The second term uses the oracle bandwidth h∗ . Then, we have
Ē(fbbh (0) − f (0))2 ≤ Ē((fbbh (0) − f (0))2 : b
h ≤ h∗ ) + Ē((fbbh (0) − f (0))2 : b
h > h∗ )
2
2
h > h∗ )
h ≤ h∗ ) + n2 P̄(b
h ≤ h∗ ) + Ē((fbh (0) − f (0)) : b
. Ē((fbb (0) − fbh (0)) : b
∗

∗

h

2

1
+ h∗2β0 + 2 + n−1 log n
nh∗
h∗

 2βe0
e
2β
0
log n 2β0 +1
.
∨  β0 +1 ,
n

. h2∗β0 +
e

where we have used (29) in the last inequality. Integrating over the random variable a, we
have




n
−
a
n
−
a
2
2
2
E(fbbh (0) − f (0)) ≤ E (fbbh (0) − f (0)) :
< 2 + E (fbbh (0) − f (0)) :
≥ 2
n
n

 2βe0


e
2β
0
log n 2β0 +1
n−a
2
β
+1
0
∨
.
+n P
≥ 2
n
n

 2βe0
e
2β
0
log n 2β0 +1
(30)
.
∨  β0 +1 .
n
n
Finally, we consider the situation when  < 8 log
n . In this case, for any contamination
distribution g, there is another ge such that


8 log n
8 log n
(1 − )f + g = 1 −
f+
ge.
n
n

See [7] for a rigorous argument of the above equality. Then, we can equivalently analyze the
n
risk with contamination proportion 8 log
n . This leads to the error bound


log n
n



e
2β
0
2β0 +1


∨

log n
n



e
2β
0
β0 +1




log n
n



e
2β
0
2β0 +1




Hence, we let n → ∞ and  → 0, and the proof is complete.
34

log n
n



e
2β
0
2β0 +1

e
2β
0

∨  β0 +1 .

(31)

Proof of Theorem 4.2. For the estimator that uses (15), the result is a special case of Theorem
5.2 by letting βe0 = β0 in view of the bounds (30) and (31). For the estimator that uses (14),
the result follows the same argument as the proof of Theorem 3.5 .

6.7

Proof of Theorem 4.3

We use φ(·) to denote the density of N (0, 1). Then, define
f (x) =c1 φ(c1 x),
c2 x

c2

!

φ
,
1
1
 βe0 +1
 βe0 +1
fe(x) =(1 − )f (x) + g(x),
g(x) =

ge(x) =φ(x).
e 0 /2).
With a constant c1 that is sufficiently small, we can guarantee that f ∈ P(β0 , L0 )∩P(βe0 , L
Since
!
e
β
0
c
x
2
e
,
g(x) = c2  β0 +1 φ
1
 βe0 +1
e 0 /2) when c2 is small enough, which then implies fe ∈ P(βe0 , L
e 0 ). Now
we have g ∈ Σ(βe0 , L
we note that
(1 − )f + g = (1 − 0)fe + 0e
g,
and
e
β
0

fe(0) − f (0) = |f (0) − g(0)|   βe0 +1 ,
we obtain that for any estimator fb(0),
"
# "

2
sup
Epn fb(0) − f (0)
∨
p(,f,g)∈M(,β0 ,L0 )

sup


Epn

#
e
2
2β
0
fb(0) − f (0)
&  βe0 +1 ,

e0 )
p(0,f,g)∈M(0,βe0 ,L

by applying Lemma 6.1.

6.8

Proof of Theorem 5.1

The proofs are exactly the same as in the one-dimensional case. For the lower bounds, we
only need to replace the mollifier function l(x) by its multivariate
  extension ld (x) = l(kxk).
P
n
1
1
The upper bounds are achieved by fbh (0) = n(1−) i=1 hd Kd Xhi , where the bandwidth is
−

1

−

1

−

2

−

1

1

h = n 2β0 +d ∧ n 2β0 +d  2β0 +d for structured contamination and is h = n 2β0 +d ∨  β0 +d for
arbitrary contamination. We can use a product kernel for Kd . See [8, Chapter 12] for details.

Acknowledgement
The research of CG is supported in part by NSF grant DMS-1712957.
35

References
[1] Lawrence D Brown and Mark G Low. A constrained risk inequality with applications to
nonparametric functional estimation. The Annals of Statistics, 24(6):2524–2535, 1996.
[2] T Tony Cai. Rates of convergence and adaptation over besov spaces under pointwise
risk. Statistica Sinica, 13:881–902, 2003.
[3] T Tony Cai and Jiashun Jin. Optimal rates of convergence for estimating the null density
and proportion of nonnull effects in large-scale multiple testing. The Annals of Statistics,
38(1):100–145, 2010.
[4] T Tony Cai and Mark G Low. On adaptive estimation of linear functionals. The Annals
of Statistics, 33(5):2311–2343, 2005.
[5] T Tony Cai and Mark G Low. Optimal adaptive estimation of a quadratic functional.
The Annals of Statistics, 34(5):2298–2325, 2006.
[6] Mengjie Chen, Chao Gao, and Zhao Ren. A general decision theory for hubers contamination model. Electronic Journal of Statistics, 10(2):3752–3774, 2016.
[7] Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance matrix estimation under
hubers contamination model. The Annals of Statistics (to appear), 2017.
[8] L Devroye and G Lugosi. Combinatorial methods in density estimation, 2001.
[9] David L Donoho. Statistical estimation and optimal recovery. The Annals of Statistics,
22(1):238–270, 1994.
[10] David L Donoho and Richard C Liu. Geometrizing rates of convergence, iii. The Annals
of Statistics, 19(2):668–701, 1991.
[11] Bradley Efron. Large-scale simultaneous hypothesis testing: the choice of a null hypothesis. Journal of the American Statistical Association, 99(465):96–104, 2004.
[12] Chao Gao. Robust regression via mutivariate regression depth.
arXiv:1702.04656, 2017.

arXiv preprint

[13] Peter J Huber. Robust estimation of a location parameter. The Annals of Mathematical
Statistics, 35(1):73–101, 1964.
[14] Peter J Huber. A robust version of the probability ratio test. The Annals of Mathematical
Statistics, 36(6):1753–1758, 1965.
[15] Jiashun Jin and T Tony Cai. Estimating the null and the proportion of nonnull effects
in large-scale multiple comparisons. Journal of the American Statistical Association, 102
(478):495–506, 2007.

36

[16] Iain M Johnstone. Chi-square oracle inequalities. Lecture Notes-Monograph Series, pages
399–418, 2001.
[17] OV Lepski and VG Spokoiny. Optimal pointwise adaptive methods in nonparametric
estimation. The Annals of Statistics, 25(6):2512–2546, 1997.
[18] OV Lepskii. On a problem of adaptive estimation in gaussian white noise. Theory of
Probability & Its Applications, 35(3):454–466, 1991.
[19] OV Lepskii. Asymptotically minimax adaptive estimation. i: Upper bounds. optimally
adaptive estimates. Theory of Probability & Its Applications, 36(4):682–697, 1992.
[20] OV Lepskii. Asymptotically minimax adaptive estimation. ii. schemes without optimal
adaptation: Adaptive estimators. Theory of Probability & Its Applications, 37(3):433–
448, 1993.
[21] Bernard W Silverman. Density estimation for statistics and data analysis, volume 26.
CRC press, 1986.
[22] Karine Tribouley. Adaptive estimation of integrated functionals. Mathematical Methods
of Statistics, 9(1):19–38, 2000.
[23] Alexandre B Tsybakov. Introduction to nonparametric estimation, volume 11. Springer,
2009.
[24] Bin Yu. Assouad, fano, and le cam. Festschrift for Lucien Le Cam, 423:435, 1997.

37

