ON ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

arXiv:1608.01364v3 [] 5 Oct 2017

By Rajarshi Mukherjee∗ , Eric Tchetgen Tchetgen† , and James Robins‡
Abstract We provide general adaptive upper bounds for estimating nonparametric functionals based on second order U-statistics arising from finite dimensional approximation of the infinite dimensional
models using projection type kernels. An accompanying general adaptive lower bound tool is provided yielding bounds on chi-square divergence between mixtures of product measures. We then provide
examples of functionals for which the theory produces rate optimally
matching adaptive upper and lower bound.

1. Introduction. Estimation of functionals of data generating distribution has always been
of central interest in statistics. In nonparametric statistics, where data generating distributions are
parametrized by functions in infinite dimensional spaces, there exists a comprehensive literature
addressing such questions. In particular, a large body of research has been devoted to explore
minimax estimation of linear and quadratic functionals in density and white noise models. We
do not attempt to survey the extensive literature in this area. However, the interested reader can
find a comprehensive snapshot of the literature in Hall and Marron (1987), Bickel and Ritov (1988),
Donoho, Liu and MacGibbon (1990), Donoho and Nussbaum (1990), Fan (1991), Kerkyacharian and Picard
(1996), Laurent (1996), Cai and Low (2003), Cai and Low (2004), Cai and Low (2005a), and other
references therein. Although the question of more general nonparametric functionals has received
relatively less attention, some fundamental insights regarding estimation of non-linear integral
functionals in density and white noise models can be found in Ibragimov and Has’ minskii (2013),
Kerkyacharian and Picard (1996), Nemirovski (2000), and references therein.
A general feature of the results obtained while estimating “smooth” nonparametric functionals is
an elbow effect in the rate of estimation based on the smoothness of the underlying function classes.
√
For example while estimating quadratic functionals in a d dimensional density model, n−efficient
estimation can be achieved as soon as Hölder exponent β of the underlying density exceeds d4 ,
4β

whereas the optimal rate of estimation is n− 4β+d (in root mean squared sense) for β < d4 . A similar
elbow in the rate of estimation exists for estimation of non-linear integral functionals as well.
For density model this was demonstrated by Birgé and Massart (1995), Kerkyacharian and Picard
(1996). For signal or white noise model, the problem of general integrated non-linear functionals
√
was studied by Nemirovski (2000), but mostly in the n− regime. However, for more complex
nonparametric models, the approach for constructing minimax optimal procedures for general non√
linear functionals in non− n regimes has been rather case specific. Motivated by this, in recent
times, Robins et al. (2008, 2016), Mukherjee, Newey and Robins (2017) have developed a theory
of inference for nonlinear functionals in parametric, semi-parametric, and non-parametric models
based on higher order influence functions.
Most minimax rate optimal estimators proposed in the literature, however, depend explicitly on
the knowledge of the smoothness indices. Thus, it becomes of interest to understand the question
of adaptive estimation i.e. the construction and analysis of estimators without prior knowledge of
∗

Assistant Professor, Division of Biostatistics, University of California, Berkeley
Professor, Department of Biostatistics, Harvard University
‡
Professor, Department of Biostatistics, Harvard University
AMS 2000 subject classifications: Primary 62G10, 62G20, 62C20
Keywords and phrases: Adaptive Minimax Estimation, Lepski’s Method, Higher Order U-Statistics
†

1

2

the smoothness. The question of adaptation of linear and quadratic functionals has been studied in
detail in the context of density, white noise, and nonparametric additive Gaussian noise regression
models (Low (1992), Efromovich and Low (1994), Efromovich and Low (1996), Tribouley (2000),
Efromovich and Samarov (2000), Klemela and Tsybakov (2001), Laurent and Massart (2000), Cai and Low
(2005b), Cai and Low (2006), Giné and Nickl (2008)). However, adaptive estimation of more general
non-linear functionals in more complex nonparametric models have received much less attention.
This paper is motivated by taking a step in that direction.
In particular, we suppose we observe i.i.d copies of a random vector O = (W; X) ∈ Rm+d with
unknown distribution P on each of n study subjects. The variable X represents a random vector
of baseline covariates such as age, height, weight, etc. Throughout X is assumed to have compact
support and a density with respect to the Lebesgue measure in Rd . The variable W ∈ Rm can be
thought of as a combination of outcome and treatment variables in some of our examples. In the
above set up, we are interested in estimating certain “smooth” functionals φ(P ) in the sense that
under finite dimensional parametric submodels, they admit derivatives which can be represented
as inner products of first order influence functions with score functions (Bickel et al., 1993). For
some classic examples of these functionals, we provide matching upper and lower bounds on the
rate of adaptive minimax estimation over a varying class of smoothness of the underlying functions,
provided the marginal design density of X is sufficiently smooth.
The contributions of this paper are as follows. Extending the theory from density estimation and
Gaussian white noise models, we provide a step towards adaptation theory for non-linear functionals
√
in more complex nonparametric models in the non- n regime. The crux of our arguments relies
on the observation that when the non-adaptive minimax estimators can be written as a sum of
empirical mean type statistics and 2nd −order U-statistics, then one can provide a unified theory
of selecting the “best” data driven estimator using Lepski type arguments (Lepski, 1991, 1992).
Indeed, under certain assumptions on the data generating mechanism P , the non-adaptive minimax
estimators have the desired structure for a large class of problems (Robins et al., 2008). This enables
us to produce a class of examples where a single method helps provide a desired answer. In order
to prove a lower bound for the rate of adaptation, we provide a general tool for bounding the chisquare divergence between two mixtures of suitable product measures. This extends the results in
Birgé and Massart (1995); Robins et al. (2009), where similar results were obtained for the Hellinger
distance. Our results are provided in the low regularity regime, i.e. when it is not possible to
√
achieve n-efficient estimator in an asymptotically minimax sense. This typically happens when the
“average smoothness” of the function classes in consideration is below d4 . Discussions on obtaining
√
a corresponding n-efficient estimator for regularity above d4 is provided in Section 4.
The rest of the paper is organized as follows. In Section 2 we provide the main results of the paper
in a general form. Section 3 is devoted for applications of the main results in specific examples. A
discussion on some issues left unanswered is provided in Section 4. In Section 5 we provide a brief
discussion on some basic wavelet and function space theory and notations, which we use extensively
in our jargon. Finally Section 6 and Appendices A and B are devoted for the proof of the theorems
and collecting useful technical lemmas.
1.1. Notation. For data arising from underlying distribution P we denote by PP and EP the
probability of an event and expectation under P receptively. For any positive integer m ≥ 2d , let
m
j(m)d ≥ m/2d . For a two
j(m) denote the largest integer j such that 2jd ≤ m i.e. j = ⌊ d1 log
log 2 ⌋ and 2
variable function h(O1 , O2 ) let S(h(O1 , O2 )) = 12 [h(O1 , O2 ) + h(O2 , O1 )] be the symmetrization of
h. The results in this paper are mostly asymptotic (in n) in nature and thus requires some standard
asymptotic notations. If an and bn are two sequences of real numbers then an ≫ bn (and an ≪ bn )
implies that an /bn → ∞ (and an /bn → 0) as n → ∞, respectively. Similarly an & bn (and an . bn )

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

3

implies that lim inf an /bn = C for some C ∈ (0, ∞] (and lim sup an /bn = C for some C ∈ [0, ∞)).
Alternatively, an = o(bn ) will also imply an ≪ bn and an = O(bn ) will imply that lim sup an /bn = C
for some C ∈ [0, ∞)). Finally we comment briefly on the various constants appearing throughout
the text and proofs. Given that our primary results concern convergence rates of various estimators,
we will not emphasize the role of constants throughout and rely on fairly generic notation for such
constants. In particular, for any fixed tuple v of real numbers, C(v) will denote a positive real
number which depends on elements of v only. Finally for any linear subspace L ⊆ L2 [0, 1]d , let
Π (h|L) denote the orthogonal projection of h onto L under
R the Lebsegue measure. Also, for a
function defined on [0, 1]d , for 1 ≤ q < ∞ we let khkq : = ( [0,1]d |h(x)|q dx)1/q denote the Lq seminorm of h, khk∞ : = supx∈[0,1]d |h(x)| the L∞ semi-norm of h. We say h ∈ Lq [0, 1]d for q ∈ [1, ∞]
if khkq < ∞. Typical functions arising in this paper will be considered to have memberships in
certain Hölder balls H(β, M ) (see Section 5 for details). This will imply that the functions are
uniformly bounded by a number depending on M . However, to make the dependence of our results
on the uniform upper bound of functions more clear, we will typically assume a bound BU over the
function classes, and for the sake of compactness will avoid the notational dependence of BU on
M.
2. Main Results. We divide the main results of the paper into three main parts. First we
discuss a general recipe for producing a “best” estimator from a sequence of estimators based on
second order U-statistics constructed from compactly supported wavelet based projection kernels
(defined in Section 5). Next we provide a general tool for bounding chi-square divergence between
mixtures of product measures. This serves as a basis of using a version of constrained risk inequality
(Cai and Low, 2011) for producing matching adaptive lower bounds in context of estimation of nonlinear functionals considered in this paper. Finally we provide estimators of design density as well
as regression functions in L∞ norm which adapt over Hölder type smoothness classes (defined in
Section 5).
2.1. Upper Bound.
Consider i.i.d data Oi = (Wi , Xi ) ∼ P , Wi ∈ Rm , Xi ∈ [0, 1]d , i = 1, . . . , n and a real valued functional of interest φ(P ). Given this sample of size n ≥ 1, consider further, a sequence of estimators
{φ̂n,j }j≥1 of φ(P ) defined as follows:
φ̂n,j =

n
X

1
1X
L1 (Oi ) −
S L2l (Oi1 )KVj (Xi1 , Xi2 ) L2r (Oi2 )
n
n(n − 1)
i=1

i1 6=i2

where KVj (Xi1 , Xi2 ) is a resolution 2j wavelet projection kernel defined in Section 5 and L1 , L2l , L2r
are measurable functions such that ∀O one has
max{|L1 (O)|, |L2l (O)|, |L2r (O)|} ≤ B
for a known constant B. Also assume that |g(x)| ≤ B ∀x, g being the marginal density of X with
respect to Lebesgue measure. Such a sequence of estimators can be though about as a bias corrected
version of a usual first order estimator arising from standard first order influence function theory
for “smooth” functionals φ(PP
) (Bickel et al., 1993; Van der Vaart, 2000). In particular, the linear
of
empirical mean type term n1 ni=1 L1 (Oi ) typically

P derives from the classical influence function
1
S
L
(O
)K
(X
,
X
)
L
(O
)
corrects
φ(P ) and the U-statistics quadratic term n(n−1)
i1
Vj
i1
i2
2r
i2
2l
i1 6=i2
for higher order bias terms. While, specific examples in Section 3 will make the structure of these
sequence of estimators more clear, the interested reader will be able to find more detailed theory
in Robins et al. (2008, 2016).

4

The quality of such sequence of estimators will be judged against models for the data generating
mechanism P . To this end, assume P ∈ Pθ where Pθ is a class of data generating distributions
indexed by θ which in turn can vary over an index set Θ. The choices of such a Θ will be clear
from our specific examples in Section 3, and will typically corresponding to smoothness indices
of various infinite dimensional functions parametrizing the data generating mechanisms. Further
assume that there exists positive real values functions f1 and f2 defined on Θ such that the sequence
of estimators {φ̂n,j }j≥1 satisfies the following bounds with known constants C1 > 0 and C2 > 0
whenever n ≤ 2jd ≤ n2 .
Property (A): Bias Bound




f1 (θ)
sup |EP φ̂n,j − φ(P ) | ≤ C1 2−2jd d + n−f2 (θ) .

P ∈Pθ

Property (B): Variance Bound


2
2jd
sup EP φ̂n,j − EP φ̂n,j
≤ C2 2 .
n
P ∈Pθ

Given properties (A) and (B), we employ a Lepski type argument to choose an “optimal” estimator
from the collection of {φ̂n,j }j≥1 ’s. To this end, as in Efromovich and Low (1996), for a given choice
1−

2

of c > 1, let N be the largest integer such that cN −1 ≤ n log log n . Denote k(j) = 2jd , which,
according to the definition in Section 1.1 implies that k(j(m)) ≤ m. For l = 0, . . . , N − 1 let
2

l

βl be the solution of k(jl ) = n 1+4βl /d , where jl = j(cl n) i.e. k(jl ) = 2j(c n)d . Note that,
j(cN−1 n)d

2

n2

≤

cN−1 n
n2

=

1

2

n log log n

k(jN )
n2

=

= o(1). By our choice of discretization, k(j0 ) ≤ k(j1 ) ≤ . . . ≤
β

′

′

k(jN −1 ). Also, there exists constants c1 , c2 such that for all 0 ≤ l ≤ l ≤ N − 1 one has βdl − dl ∈
i
 2  1
h ′
′
1+4βl /d
k(jl )
l −l
n
l −l
,
c
.
For
l
=
0,
.
.
.
,
N
−
1
let
k
(j
)
=
=
and R(k∗ (jl )) =
c1 log
2
∗
l
1
n
log n
log n
(log n) 1+4βl /d

k∗ (jl )
n2

=n

8βl /d
− 1+4β
l /d

1
− 1+4β
l /d

(log n)

′

′

. This implies that for l > l there exists constant c ≥ 0 such that

k∗ (jl )
≥
k∗ (jl′ )



n2
log n

4β ′ /d−4βl /d
l
 (1+4β
/d)(1+4β /d)
l

′

l

′

≥ ec ≥ 1.

Finally letting s∗ (n) be the smallest l such that k∗ (jl ) ≥ n, define
( 
)
2
2 R(k (j ′ )) log n
l:
φ̂
−
φ̂
≤
C
∗
n,j(k
(j
))
n,j(k
(j
))
′
opt
ˆl: = min
∗ l
∗
l
l
′
∀l ≥ l, s∗ ≤ l ≤ N − 1

(2.1)

where Copt is a deterministic constant to be specified later.
With the notations and definitions as above we now have the following theorem which is the
main result in the direction of adaptive upper bound in this paper.
Theorem 2.1. Assume β < d4 . Then there exists a positive C depending on B, C1 , C2 , and
choice of wavelet bases ψ 00,0 , ψ 10,0 (defined in Section 5) such that
sup
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

4β
4β+d

√
 8β

2
log n 4β+d
EP φ̂n,j (k∗ (l̂)) − φ(P ) ≤ C
.
n

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

5

A few remarks are in order regarding the implications of Theorem 2.1. In particular, provided
one has a knowledge of a data generating θ and therefore of f1 (θ) and f2 (θ), one can use the bias
and variance properties to achieve an optimal trade-off and subsequently obtain mean squared error
−

8β

in estimating φ(P ) over P ∈ Pθ which scales as n 8β+d . Theorem 2.1 demonstrates a logarithmic
price payed by the estimator φ̂n,j (k∗ (l̂)) in terms of estimating φ(P ) over a class of data generating
n
o
4β
mechanisms Pθ : f1 (θ) = β, f2 (θ) > 4β+d
, β < d4 . As will be demonstrated in Section 3, the term

4β
f1 (θ) = β usually drives the minimax rate of estimation whereas f2 (θ) > 4β+d
is a regularity
condition which typically will relate to marginal density of covariates in observational studies.
Moreover, in our examples, the range of β < d/4 will be necessary to guarantee the non-existence
√
of n-consistent estimators of φ(P ) over P ∈ Pθ in a minimax sense.
Finally, it therefore remain to be explored whether this logarithmic price payed in Theorem
2.1 is indeed necessary. Using a chi-square divergence inequality developed in the next section
along with a suitable version of constrained risk inequality (see Section B) we shall argue that the
logarithmic price of Theorem 2.1 is indeed necessary for a class of examples naturally arising in
many observational studies.

2.2. Lower Bound.
We provide a bound on the chi-square divergence between two mixture of product measures,
and thereby extending results of Birgé and Massart (1995) and Robins et al. (2009). Since both
Birgé and Massart (1995) and Robins et al. (2009) considered demonstrating bounds on the Hellinger
divergence between mixtures of product measures, they do not automatically provide bounds on
the corresponding chi-square divergences. However, such bounds are essential to explore adaptive
lower bound in a mean squared error sense. To this end, as in Robins et al. (2009), let O1 , . . . , On be
a random sample from a density p with respect to measure µ on a sample space (χ, A). For k ∈ N,
let χ = ∪kj=1 χj be a measurable partition of the sample space. Given a vector λ = (λ1 , . . . , λk ) in
some product measurable space Λ = Λ1 × · · · × Λk let Pλ and Qλ be probability measures on χ
such that
• Pλ (χj ) = Qλ (χj ) = pj for every λ and some (p1 , . . . , pk ) in the k-dimensional simplex.
• The restrictions Pλ and Qλ to χj depends on the j th coordinate λj of λ = (λ1 , . . . , λk ) only.
For pλ and qλ densities of the measures Pλ and Qλ respectively that are jointly measurable
in the
R
parameters
λ
and
the
observations,
and
π
a
probability
measure
on
Λ,
define
p
=
p
dπ(λ)
and
λ
R
qλ = qλ d(π(λ)), and set
Z
(pλ − p)2 dµ
,
a = max sup
j
pλ
pj
λ
χj
Z
(pλ − p)2 dµ
b = max sup
,
j
pλ
pj
λ
χj
Z
p2 dµ
,
c = max sup
e
j
λ
χj pλ pj
Z
(q − p)2 dµ
δ = max sup
.
j
pλ
pj
λ
χj
With the notations and definitions as above we now have the following theorem which is the main
result in the direction of adaptive lower bound of this paper.

6

Theorem 2.2. Suppose that npj (1 ∨ a ∨ b ∨ e
c) ≤ A for all j and for all λ, B ≤ pλ ≤ B for
positive constants A, B, B. Then there exists a C > 0 that depends only on A, B, B, such that, for
any product probability measure π = π1 ⊗ · · · ⊗ πk , one has

Z
Z
2
2
2
χ
Pλ d(π(λ)), Qλ d(π(λ)) ≤ eCn (maxj pj )(b +ab)+Cnδ − 1,
2
R  dν2
where χ2 (ν1 , ν2 ) =
−
1
dν1 is the chi-square divergence between two probability measures
dν1
ν1 and ν2 with ν2 ≪ ν1 .

2.3. L∞ -Adaptive Estimation of Density and Regression Functions.
We provide adaptive estimator of regression function in L∞ using Lepski type arguments (Lepski,
1992). Consider i.i.d data on Oi = (Wi , Xi ) ∼ P for a scalar variable W such that |W | ≤ BU and
EP (W |X) = f (X) almost surely, and X ∈ [0, 1]d has density g such that 0 < BL ≤ g(x) ≤ BU < ∞
for all x ∈ [0, 1]d . Although to be precise, we should put subscripts P to f, g, we omit this since
the context of their use is clear. We assume Hölder type smoothness (defined in Section 5) on
f, g and let P(β, γ) = {P : (f, g) ∈ H(β, M ) × H(γ, M ), |f (x)| ≤ BU , BL ≤ g(x) ≤ BU ∀ x ∈
[0, 1]d } denote classes of data generating mechanisms indexed by the smoothness indices. Then we
have the following theorem, which considers adaptive estimation of f, g in L∞ norm over (β, γ) ∈
(βmin , βmax ) × (γmin , γmax ), for given positive real numbers βmin , βmax , γmin , γmax .
Theorem 2.3. If γmin > βmax , then there exists an fˆ and ĝ depending on M, BL , BU , βmin ,
βmax , γmin , γmax , and choice of wavelet bases ψ 00,0 , ψ 10,0 (defined in Section 5) such that the following
hold for every (β, γ) ∈ (βmin , βmax ) × (γmin , γmax ) with a large enough C > 0 depending possibly on
M, BL , BU , and γmax .


− β
2β+d
n
,
sup EP kfˆ − f k∞ ≤ (C)
log n
P ∈P(β,γ)

− γ
2γ+d
d
n
2γ+d
EP kĝ − gk∞ ≤ (C)
,
log n


1
/ H(β, C) ≤ 2 ,
sup PP fˆ ∈
n
P ∈P(β,γ)
d
2β+d

sup
P ∈P(β,γ)

PP (ĝ ∈
/ H(γ, C)) ≤

1
,
n2

|fˆ(x)| ≤ 2BU and BL /2 ≤ ĝ(x) ≤ 2BU ∀x ∈ [0, 1]d .
Remark 2.4. A close look at the proof of Theorem 2.3, shows that the proof continues to hold
for βmin = 0. Moreover, although we did not keep track of our constants, the purpose of keeping
them in the form above is to show that the multiplicative constants is not arbitrarily big when β is
large.
Theorems of the flavor of Theorem 2.3 is not uncommon in literature (see (Giné and Nickl,
2015, Chapter 8) for details). In particular, results of the kind stating that ĝ ∈ H(γ, C) with high
probability uniformly over P(β, γ) for a suitably large constant C is often very easy to demonstrate.
However, our proof shows that a suitably bounded estimator ĝ, which adapts over smoothness and
satisfies ĝ ∈ H(γ, C) with probability larger than 1 − n1κ uniformly over P(β, γ), for any κ > 0

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

7

and correspondingly large enough C. This result in turn turns out to be crucial for the purpose
of controlling suitable bias terms in our functional estimation problems. Additionally, the results
concerning fˆ are relatively less common in an unknown design density setting. Indeed, adaptive
estimation of regression function with random design over Besov type smoothness classes has been
obtained by model selection type techniques by Baraud (2002) for the case of Gaussian errors. Our
results in contrast hold for any regression model with bounded outcomes and compactly supported
covariates having suitable marginal design density. Before proceeding we note that the results of
this paper can be extended to include the whole class of doubly robust functionals considered
in Robins et al. (2008). However we only provide specific examples here to demonstrate the clear
necessity to pay a sharp poly-logarithmic penalty for adaptation in low regularity regimes.

3. Examples. In this section we discuss applications of Theorem 2.1 and Theorem 2.2 in producing rate optimal adaptive estimators of certain nonparametric functionals commonly arising in
statistical literature. The proof of the results in this section can be found in Mukherjee, Tchetgen Tchetgen and Rob
(2017).
3.1. Average Treatment Effect. In this subsection, we consider estimating the “treatment
effect” of a treatment on an outcome in presence of multi-dimensional confounding variables
(Crump et al., 2009; Robins, Mark and Newey, 1992). To be more specific, we consider a binary
treatment A and response Y and d-dimensional covariate vector X, and let τ be the variance
weighted average treatment effect defined as


V ar(A|X)c(X)
E(cov(Y, A|X))
τ: = E
=
E(V ar(A|X))
E(V ar(A|X))
Above
c(x) = E(Y |A = 1, X = x) − E(Y |A = 0, X = x).

(3.1)

and under the assumption of no unmeasured confounding, c(x) is often referred to as the average
treatment effect among subjects with covariate value X = x. The reason of referring to τ as the
average treatment effect can e further understood by considering semi-parametrically constrained
model
c(x) = φ∗ for all x,

(3.2)

or specifically the model
E(Y |A, X) = φ∗ A + b(X).
It is clear that under (3.2) it turns out that , τ equals φ∗ . Moreover, the inference on τ is closely
related to the estimation E(Cov(Y, A|X)) (Robins et al., 2008). Specifically, point and interval
estimator for τ can be constructed from point and interval estimator of E(Cov(Y, A|X)). To be
more specific, for any fixed τ ∗ ∈ R, one can define Y ∗ (τ ∗ ) = Y − τ ∗ A and consider
φ(τ ∗ ) = E((Y ∗ (τ ∗ ) − E(Y ∗ (τ ∗ )|X))(A − E(A|X))) = E(cov(Y ∗ (τ ∗ ), A|X)).
it is easy to check that τ is the unique solution of φ(τ ∗ ) = 0. Consequently, if we can construct
estimator φ̂(τ ∗ ) of φ(τ ∗ ), then τ̂ satisfying ψ(τ̂ ) = 0 is an estimator of τ with desirable properties. Moreover, (1 − α) confidence set for τ can be constructed as the set of values of τ ∗ for

8

which (1 − α) interval estimator of φ(τ ∗ ) contains the value 0. Finally, since E(Cov(Y, A|X)) =
E(E(Y |X)E(A|X)) − E(AY ), and E(AY ) is estimable easily at a parametric rate, the crucial part
of the problem hinges on the estimation of E(E(Y |X)E(A|X)).
Henceforth, for the rest of the section, we assume that we observe n iid copies of O = (Y, A, X) ∼
P and we want to estimate φ(P ) = EP (CovP (Y, A|X)). We assume that the marginal distribution
of X has a density with respect to Lebesgue measure on Rd that has a compact Rsupport, which we
assume to be [0, 1]d and let g be the marginal density of X (i.e. EP (h(X)) =
h(x)g(x)dx for
[0,1]d

all P -integrable function h), a(X): = EP (A|X), b(X): = EP (Y |X), and c(X) = EP (Y |A = 1, X) −
EP (Y |A = 0, X). Although to be precise, we should put subscripts P to a, b, g, c, we omit this
< d4 , γmax ≥ γ > γmin ≥
since the context of their use is clear. Let Θ: = {θ = (α, β, γ): α+β
2
2(1 + ǫ) max{α, β}} for some fixed ǫ > 0, and let Pθ denote all data generating mechanisms P
satisfying the following conditions for known positive constants M, BL , BU .
(a) max{|Y |, |A|} ≤ BU a.s. P .
(b) a ∈ H(α, M ), b ∈ H(β, M ), and g ∈ H(γ, M ).
(c) 0 < BL < g(x) < BU for all x ∈ [0, 1]d .

Note that we do not put any assumptions on the function c. Indeed for Y and A binary random
variables, the functions a, b, g, c are variation independent. Following our discussion above, we will
discuss adaptive estimation of φ(P ) = EP (covP (Y, A|X)) = EP ((Y − b(X))(A − a(X))) over P ∈ P.
In particular, we summarize our results on upper and lower bounds on the adaptive minimax
estimation of φ(P ) in the following theorem.
Theorem 3.1. Assume (a) − (c) and (α, β, γ) ∈ Θ. Then the following hold for positive C, C ′
depending on M, BL , BU , γmax .
(i) (Upper Bound) There exists an estimator φ̂, depending only on M, BL , BU , γmax such that
 4α+4β
√

2
log n 2α+2β+2d
sup EP φ̂ − φ(P ) ≤ C
.
n
P ∈P(α,β,γ)
(ii) (Lower Bound) Suppose {A, Y } ∈ {0, 1}2 . If one has
 4α+4β
√

2
log n 2α+2β+2d
sup EP φ̂ − φ(P ) ≤ C
,
n
P ∈P(α,β,γ)
for an estimator φ̂ of φ(P ). Then there exists a class of distributions P(α′ ,β ′ ,γ ′ ) such that
′

sup

P ′ ∈P

′ ′ ′
(α ,β ,γ )

′

 4α +4β
√

2
log n 2α′ +2β ′ +2d
′
′
.
EP ′ φ̂ − φ(P ) ≥ C
n

Theorem 3.1 describes the adaptive minimax estimation of the treatment effect functional in
√
n-rate estimation is not possible. By assuming more
low regularity regime ( α+β
2 < d/4) i.e. when
smoothness on the marginal of g (i.e. lager value of γ) it is possible to include the case of α+β
2 ≥ d/4
α+β
α+β
as well. In particular, if the set of (α, β) includes the case 2 > d/4 as well as 2 < d/4, one
√
should be able to obtain adaptive and semi-parametrically efficient n-consistent estimator of
the treatment effect for α+β
2008), the
2 > d/4. Similar to quadratic functionals (Giné and Nickl, √
α+β
=
d/4
will
however
incur
an
additional
logarithmic
penalty
over
usual
case of 2
n-rate of

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

9

convergence. All these extensions can definitely be incorporated in the designing of the Lepski’s
method in Section 2. However, we do not pursue this in this paper and refer to Section 4 for more
discussions on relevant issues. Finally, it is worth noting that if the set of (α, β) only includes the
case α+β
2 > d/4, one can indeed obtain adaptive and even semiparametrically efficient estimation
of the functionals studied here without effectively any assumption on g. The interested reader can
find the details in Mukherjee, Newey and Robins (2017); Robins et al. (2016).
3.2. Mean Response in Missing Data Models. Suppose we have n i.i.d observations on
O = (Y A, A, X) ∼ P , for a response variable Y ∈ R which is conditionally independent of the missingness indicator variable A ∈ {0, 1} given covariate information X. In literature, this assumption
is typically known as the missing at random model (MAR) and under this assumption, our quantity
of interest φ(P ) = EP (Y ) is identifiable as EE (Y |A = 1, X) from the observed data. This model
is a canonical example of a study with missing response variable and to make this assumption
reasonable, the covariates must contain the information on possible dependence between response
and missingness. We referred the interested reader to Tsiatis (2007) for the history of statistical
analysis of MAR and related models.
To the lay down the mathematical formalism for minimax adaptive
R estimation of φ(P ) in
this model, let f be the marginal density of X (i.e. EP (h(X)) =
h(x)f (x)dx for all P [0,1]d

a−1 (X): =

integrable function h),
EP (A|X), and b(X): = EP (Y |A = 1, X) = EP (Y |X), and
g(X) = f (X)/a(X) (with the convention of the value +∞ when dividing by 0). Although to
be precise, we should put subscripts P to a, b, g, we omit this since the context of their use is clear.
< d4 , γmax ≥ γ > γmin ≥ 2(1 + ǫ) max{α, β}} for some fixed ǫ > 0,
Let Θ: = {θ = (α, β, γ): α+β
2
and let Pθ denote all data generating mechanisms P satisfying the following conditions for known
positive constants M, BL , BU .
(a) |Y | ≤ BU .
(b) a ∈ H(α, M ), b ∈ H(β, M ), and g ∈ H(γ, M ).
(c) BL < g(x), a(x) < BU for all x ∈ [0, 1]d .
We then have the following result.
Theorem 3.2. Assume (a) − (c) and (α, β, γ) ∈ Θ. Then the following hold for positive C, C ′
depending on M, BL , BU , γmax .
(i) (Upper Bound) There exists an estimator φ̂, depending only on M, BL , BU , γmax such that
 4α+4β
√

2
log n 2α+2β+2d
sup EP φ̂ − φ(P ) ≤ C
.
n
P ∈P(α,β,γ)
(ii) (Lower Bound) Suppose {A, Y } ∈ {0, 1}2 . If one has
 4α+4β
√

2
log n 2α+2β+2d
,
sup EP φ̂ − φ(P ) ≤ C
n
P ∈P(α,β,γ)
for an estimator φ̂ of φ(P ). Then there exists a class of distributions P(α′ ,β ′ ,γ ′ ) such that
′

sup
P ′ ∈P(α′ ,β ′ ,γ ′ )

′

 4α +4β
√

2
log n 2α′ +2β ′ +2d
′
′
.
EP ′ φ̂ − φ(P ) ≥ C
n

10

Once again, Theorem 3.2 describes the adaptive minimax estimation of the average outcome in
√
n-rate estimation is not
missing at random models in low regularity regime ( α+β
2 < d/4) i.e. when
d
possible. Extensions to include α+β
≥
is
possible
by
similar
Lepski
type
method
with additional
2
4
smoothness assumption on g. However, we do not pursue this in this paper and refer to Section 4
for more discussions on relevant issues.
3.3. Quadratic and Variance Functionals in Regression Models. Consider a observing data which are n i.i.d copies of O = (Y, X) ∼ P and the functional of interest is the expected value of the
 regression of Y on X. Specifically suppose we want to esti from of the
2
mate φ(P ) = EP {EP (Y |X)} . Assume that distribution of X has a density with respect to

Lebesgue measure on Rd that has a compact support, which we assume to be [0, 1]d for sake of
simplicity. Let g be the marginal density of X, and b(X): = EP (Y |X). The class of distributions
Θ: = {P(β, γ): β < d4 , γmax ≥ γ > γmin ≥ 2(1 + ǫ)β} for some fixed ǫ > 0, where by P(β, γ) we
consider all data generating mechanisms P satisfying the following conditions. for known positive
constants M, BL , BU .

(a) max{|Y |} ≤ BU .
(b) b ∈ H(β, M ), and g ∈ H(γ, M ).
(c) 0 < BL < g(x) < BU for all x ∈ [0, 1]d .
Theorem 3.3. Assume (a) − (c) and (β, γ) ∈ Θ. Then the following hold for positive C, C ′
depending on M, BL , BU , γmax .
(i) (Upper Bound) There exists an estimator φ̂, depending only on M, BL , BU , γmax such that
 8β
√

2
log n 4β+d
.
sup EP φ̂ − φ(P ) ≤ C
n
P ∈P(β,γ)
(ii) (Lower Bound) Suppose Y ∈ {0, 1}2 . If one has
√
 8β

2
log n 4β+d
sup EP φ̂ − φ(P ) ≤ C
,
n
P ∈P(β,γ)
′

′

for an estimator φ̂ of φ(P ). Then there exists a class of distributions P(β , γ ) such that
′

 8β′
√

2
4β +d
log
n
′
sup
EP φ̂ − φ(P ) ≥ C ′
.
′
′ ′
n
P ∈P(β ,γ )
Remark 3.4. Although Theorem 3.3 and the discussion before that is made in the context
of estimating a particular quadratic functional in the context of a regression framework, it is
worth noting that the result extends to estimating classical quadratic functionals in density models
(Efromovich and Low, 1996; Giné and Nickl, 2008).
One can also consider in the same set up, the estimation of functionals related to the conditional
variance of Y under such a regression model, which has been studied in detail by Brown and Levine
(2007); Cai and Wang (2008); Fan and Yao (1998); Hall and Carroll (1989); Ruppert et al. (1997).
Whereas, the minimax optimal and adaptive results in Brown and Levine (2007); Cai and Wang
(2008) are in a equi-spaced fixed design setting, one can use an analogue of Theorem 3.3 to demonstrate a rate adaptive estimator and corresponding matching lower bound, with a mean-squared

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

error of the order of
d
4.



√n
log n

−

8β
4β+d

11

for estimating EP (V arP (Y |X)) adaptively over Hölder balls

As noted by Robins et al. (2008), this rate is higher than the rate of estiof regularity β <
mating the conditional variance in mean-squared error for the equispaced design (Cai and Wang,
2008). In a similar vein, one can also obtain similar results for the estimation of conditional
variance under the assumption if homoscedasticity i.e. σ 2 : = V ar (Y |X = x) for all x ∈ [0, 1]d .
In particular, one can once again obtain an estimator with mean-squared error of the order of
− 8β

4β+d
√n
for estimating σ 2 over any Hölder balls of regularity β < d4 . In particular, a canlog n

didate sequence of φ̂n,j ’s for this purpose was constructed in Robins et al. (2008), and in essence
P
1
2
equals φ̂n,j = n(n−1)
i1 6=i2 (Yi1 − Yi2 ) KVj (Xi1 , Xi2 )— whose properties can be analyzed by a
technique similar to the proof of Theorem 3.3. Its however worth noting that, even in this very
easy to state classical problem, matching lower bounds, even in non-adaptive minimax sense is not
available. Therefore, our results related to homoscedastic variance estimation, can be interpreted
from a point of view of selecting a “best” candidate from a collection of estimators.
4. Discussion. In this paper, we have extended the results for adaptive estimation of nonlinear integral functionals from density estimation and Gaussian white noise models, to move towards an adaptive estimators non-linear functionals in more complex nonparametric models. Our
results are provided and are most interesting in the low regularity regime, i.e. when it is not pos√
sible to achieve n-efficient estimator in an asymptotically minimax sense. This typically happens
when the “average smoothness” of the function classes in consideration is below d4 . The reason
for focusing on the low regularity region is two fold. Firstly, this regime corresponds to situations
where adaptation is to smoothness is not possible without paying a logarithmic penalty–making
it an interesting case to study. Secondly, as noted in Robins et al. (2008), the appropriate nonadaptive minimax sequence of estimators of the functionals considered in this paper, which attain
√
n-efficiency rely either on high regularity of the marginal density of the covariates X in our examples or on correcting higher order bias by using U-statistics of degree 3 and higher. Indeed,
under stringent assumptions on the smoothness of the density of X, our results carry through to
√
yield adaptive n-efficient estimators. However, under more relaxed conditions on the density of
X, although we can in principle employ a similar framework of Lepski type idea as implemented
by Theorem 2.1, the mathematical analysis of such a method requires sharp control of tails of
U-statistics of degree 3 and higher. The structure of the higher order U-statistics considered in the
estimators constructed in Robins et al. (2008) makes such an analysis delicate, and we plan to focus
on these issues in a future paper. However, it is worth noting that with the additional knowledge
of smoothness exceeding d4 one can indeed obtain adaptive and even semiparametrically efficient
estimation of the functionals studied here without effectively any assumption on g. The interested
reader can find the details in Mukherjee, Newey and Robins (2017); Robins et al. (2016). Finally,
the results of this paper can be extended to include the whole class of doubly robust functionals
considered in Robins et al. (2008). However we only provide specific examples here to demonstrate
the clear necessity to pay a poly-logarithmic penalty for adaptation in low regularity regimes.
5. Wavelets, Projections, and Hölder Spaces.
We work with certain Besov- Hölder type spaces which we define in terms of moduli of wavelet

coefficients of continuous functions. For d > 1, consider expansions of functions h ∈ L2 [0, 1]d on
an orthonormal basis of compactly supported bounded wavelets of the form
h(x) =

X

k∈Zd

hh, ψ 00,k iψ 00,k (x)

+

∞ X
X

X

l=0 k∈Zd v∈{0,1}d −{0}d

hh, ψ vl,k iψ vl,k (x),

12

where the base functions ψ vl,k are orthogonal for different indices (l, k, v) and are scaled and translated versions of the 2d S-regular base functions ψ v0,0 with S > β, i.e., ψ vl,k (x) = 2ld/2 ψ v0,0 (2l x −

Qd
l
vj
d
d
l
2
k) =
j=1 2 ψ0,0 2 xj − kj for k = (k1 , . . . , kd ) ∈ Z and v = (v1 , . . . , vd ) ∈ {0, 1} with
1
0
= ψ being the scaling function and mother wavelet of regularity S respec= φ and ψ0,0
ψ0,0
tively as defined in one dimensional case. As our choices of wavelets, we will throughout use compactly supported scaling and wavelet functions of Cohen-Daubechies-Vial type with S first null
moments(Cohen, Daubechies and Vial, 1993). In view of the compact support of the wavelets, for
v are non-zero on [0, 1]; let us
each resolution level l and index v, only O(2ld ) base elements ψl,k
denote the corresponding set of indices k by Zl obtaining the representation,
h(x) =

X

k∈ZJ0

hh, ψ 0J0 ,k iψ 0J0 ,k (x) +

∞ X
X

X

l=J0 k∈Zl v∈{0,1}d −{0}d

hh, ψ vl,k iψ vl,k (x),
(5.1)

where J0 = J0 (S) ≥ 1 is such that 2J0 ≥ S (Cohen, Daubechies and Vial, 1993; Giné and Nickl,
2015). Thereafter, let for any h ∈ L2 [0, 1]d , khh, ψ l′ ,· ik2 be the vector L2 norm of the vector


′
hh, ψ vl′ ,k′ i: k ∈ Zl′ , v ∈ {0, 1}d .
We will be working with projections onto subspaces defined by truncating expansions as above
at certain resolution levels. For example letting
n
o
Vj : = span ψ vl,k , J0 ≤ l ≤ j, k ∈ Zl , v ∈ {0, 1}d , j ≥ J0
(5.2)
one immediately has the following orthogonal projection kernel onto Vj as
KVj (x1 , x2 ) =

X

ψ 0J0 ,k (x1 )ψ 0J0 ,k (x2 ) +

k∈ZJ0

j X
X

X

ψ vl,k (x1 )ψ vl,k (x2 ).

l=J0 k∈Zl v∈{0,1}d −{0}

(5.3)

Owing to the MRA property of the wavelet basis, it is easy to see that KVj has the equivalent
representation as
X X
v
v
KVj (x1 , x2 ) =
(x2 ) .
(5.4)
(x1 ) ψjk
ψjk
k∈Zj v∈{0,1}d

Thereafter, using S-regular scaling and wavelet functions of Cohen-Daubechies-Vial type with
S > β let
H(β, M )


J0 (β+ d2 )
:=
khh, ψ 0J0 · ik∞ +
 :2

h ∈ C [0, 1]d
sup



d




2l(β+ 2 ) |hh, ψ vl,k i| ≤ M  ,
d

l≥0,k∈Zd ,v∈{0,1}d −{0}

(5.5)


with C [0, 1]d being the set of all continuous bounded functions on [0, 1]d . It is standard result in
the theory of wavelets that H(β, M ) is related to classical Hölder-Zygmund spaces with equivalent
norms (see (Giné and Nickl, 2015, Chapter 4) for details). For 0 < β < 1 for example, H(β, M )

13

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS


consists of all functions in C [0, 1]d such that kf k∞ +

|f (x1 )−f (x2 )|
sup
≤ C(M ). For nonkx1 −x2 kβ
d
x1 ,x2 ∈[0,1]


integer β > 1, H(β, M ) consists of all functions in C [0, 1]d such that f (⌊β⌋) ∈ C [0, 1]d for any

partial f (⌊β⌋) of order ⌊β⌋ of f and kf k∞ +

sup

x1 ,x2 ∈[0,1]d

|f (⌊β⌋) (x1 )−f (⌊β⌋) (x2 )|
kx1 −x2 kβ−⌊β⌋

≤ C(M ). Therefore, the

functions in H(β, M ) are automatically uniformly bounded by a number depending on the radius
M.
6. Proof of Main Theorems.
Proof of Theorem 2.1.
Proof. In this proof we repeatedly use the fact that for any fixed m ∈ N and a1 , . . . , am real
numbers, one has by Hölder’s Inequality |a1 + . . . , am |p ≤ C(m, p) (|a1 |p + . . . + |am |p ) for p > 1.
Suppose β ∈ (βl+1 , βl ] for some l = 0, . . . , N − 2. Indeed, this l depends on β and n, and therefore,
to be very precise, we should write it as l(β, n). However, for the sake of brevity we omit such
notation. We immediately have the following lemma.
′

For l ≥ l + 2 and Copt large enough depending on C1 , C2 , B, ψ 00,0 , ψ 10,0 ,

Lemma 6.1.

sup
P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d


 C
′
PP ˆl = l ≤ ,
n

where C > 0 is an universal constant.
Proof.
sup
P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d



PP ˆl ≥ l + 2
′

≤

PP

sup
P ∈Pθ :

l

4β
f1 (θ)=β,f2 (θ)>
4β+d

≤

N
X

l′ =l+1

sup
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

∃l > l + 1:
2

2 log nR(k ∗ (j ′ ))
φ̂n,j(k∗ (jl+1 )) − φ̂n,j(k∗ (j ′ )) > Copt
l

q


PP |φ̂n,j(k∗ (jl+1 )) − φ̂n,j(k∗ (j ′ )) | > Copt log nR(k∗ (jl′ ))
l

4β
4β+d

′

For any fixed l + 2 ≤ l ≤ N1 , using that R(k∗ (jl+1 )) ≤ R(k∗ (jl′ )) and




sup
|EP φ̂n,j(k∗ (jl+1 )) − EP φ̂n,j(k∗ (j ′ )) |
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

l

4β
4β+d

≤ Ck∗ (jl+1 )−2βl+1 /d +

n−f2 (θ) ≤ 2C

sup
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

4β
4β+d

p

log nR(k∗ (jl+1 ))

we have that
sup
P ∈Pθ :

4β
f1 (θ)=β,f2 (θ)>
4β+d

!

q


PP |φ̂n,j(k∗ (jl+1 )) − φ̂n,j(k∗ (j ′ )) | > Copt log nR(k∗ (jl′ ))
l

14

≤

sup
P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d

+

sup
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

≤

4β
4β+d

f1 (θ)=β,f2 (θ)>

4β
4β+d

sup
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

4β
4β+d






Copt q
|φ̂n,j(k∗ (jl+1 )) − EP φ̂n,j(k∗ (jl+1 )) | >
log nR(k∗ (jl′ ))
2




p
C
log nR(k∗ (jl′ ))
|φ̂n,j(k∗ (j ′ )) − EP φ̂n,j(k∗ (j ′ )) | > opt
2
l
l

 


PP 
−|EP φ̂n,j(k∗ (jl+1 )) − EP φ̂n,j(k∗ (j ′ )) |


l

PP

sup
P ∈Pθ :

+

PP






Copt p
∗
log nR(k (jl+1 ))
|φ̂n,j(k∗ (jl+1 )) − EP φ̂n,j(k∗ (jl+1 )) | >
2




p
C
∗ (j ′ ))
log
nR(k
|φ̂n,j(k∗ (j ′ )) − EP φ̂n,j(k∗ (j ′ )) | > opt
l 
l
l


 2
PP 
−|EP φ̂n,j(k∗ (jl+1 )) − EP φ̂n,j(k∗ (j ′ )) |


l

Now
sup
P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d

≤





|EP φ̂n,j(k∗ (jl+1 )) − EP φ̂n,j(k∗ (j ′ )) |
l

sup
P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d

≤ 2C1 n
≤ 2C1 n

4β
− 4β+d

4β
− 4β+d



2C1 2−2j(k∗ (jl+1 ))f1 (θ) + n−f2 (θ)


− 4β

4βl+1 +d
4β
n
k∗ (jl+1 ) −2β/d
− 4β+d
dβ
√
≤ 2C1 n
+ 2C1
+ 2C1 2
d
2
log n
− 4β

4βl+1 +d
n
2
+ 2C1 2d /4 √
.
log n


p
C
log nR(k∗ (jl′ )) for Copt chosen large
The last quantity in the above display is smaller than opt
4
enough (depending on C1 and d). This implies that for Copt properly chosen based on the given
parameters,
q


sup
PP |φ̂n,j(k∗ (jl+1 )) − φ̂n,j(k∗ (j ′ )) | > Copt log nR(k∗ (jl′ ))
l

P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d

≤

sup
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

+

f1 (θ)=β,f2 (θ)>

≤

PP



4β
4β+d

sup
P ∈Pθ :

PP



4β
4β+d




Copt p
log nR(k∗ (jl+1 ))
|φ̂n,j(k∗ (jl+1 )) − EP φ̂n,j(k∗ (jl+1 )) | >
2




Copt q
∗
|φ̂n,j(k∗ (j ′ )) − EP φ̂n,j(k∗ (j ′ )) | >
log nR(k (jl′ ))
l
l
4

C
,
n

for an universal constant C. The last inequality can now be obtained by standard Hoeffding’s
decomposition and subsequent application of Lemma B.2 and B.5 to the second and first order
degenerate parts respectively. The control thereafter is standard by our choices of n ≤ 2jd ≤ n2 .
For similar calculations we refer to (Mukherjee and Sen, 2016).

15

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

Returning to the proof of Theorem 2.1 we have

2
EP φ̂n,j (k∗ (j )) − φ(P )
sup
P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d

≤

sup
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

+

f1 (θ)=β,f2 (θ)>


2 

φ̂n,j (k∗ (j )) − φ(P ) I ˆl ≤ l + 1
EP
l̂

4β
4β+d

sup
P ∈Pθ :

l̂


2 

ˆ
EP
φ̂n,j (k∗ (j )) − φ(P ) I l ≥ l + 2
l̂

4β
4β+d

= T1 + T2
Control of T1 . Using the definition of ˆl we have the following string of inequalities.
T1
=

sup
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

≤2

 

2 
EP I ˆl ≤ l + 1 φ̂n,j (k∗ (j )) − φ(P )
l̂

4β
4β+d

sup
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

≤2

 
2 


  φ̂
∗ (j
−
φ̂
∗
n,j(k
))
l+1
n,j (k (jl̂ ))


2
EP  I ˆ
l ≤l+1
 + φ̂

∗
−
φ(P
)
n,j(k (jl+1 ))


4β
4β+d

2
Copt

sup
P ∈Pθ :
f1 (θ)=β,f2 (θ)>

log nR (k (jl+1 )) + 2

4β
4β+d

≤ (4C +



n2
log n

sup

P ∈Pθ :
f1 (θ)=β,f2 (θ)>

2
≤ Copt
log nR (k∗ (jl+1 )) + C

2
Copt
)

∗

4β
4β+d

2j(k∗ (jl+1 ))d
−4j(k∗ (jl+1 ))d βd
+
C2
+
n2

4βl+1 /d
− 1+4β
/d
l+1

c

≤e

′



n2
log n

4β/d
− 1+4β/d


2 
EP φ̂n,j(k∗ (jl+1 )) − φ(P )
sup

2Cn−2f2 (θ)

P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d

.
∗

Above we have used the property of r(β), definition of j(k∗ (l)) to conclude that 2j(k (l))d ≤ k∗ (l),
and also the definition and properties of βl together with the fact that βl+1 ≤ β < βl implies
β/d − βl+1 /d ≤ logc n for some fixed constant c.
Control of T2 .
T2
≤

≤

≤

′

N
X

l =l+2
N
X

l′ =l+2

′

N
X

l =j+2

sup
P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d

sup
P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d

4



C
n



2 
′
EP I(ˆl = l ) φ̂n,j(k∗ (j′ )) − φ(P )

1 
′
PPp lˆ = l

1

sup
P ∈Pθ :
4β
f1 (θ)=β,f2 (θ)>
4β+d

EPq


2q 
φ̂n,j (k∗ (j ′ )) − φ(P )
l

#
 1 " j (k∗ (j ′ ))d
 1
p
8β
l
C p
2
− 4β+d
−4j (k ∗ (j ′ ))β/d
l
+
2
+
n
.
log
n
,
n2
n

16

where the second last inequality above follows from Lemma 6.1, Lemma B.2, and Lemma B.5, and
the last inequality follows from the choice of N . log n. Therefore for p sufficiently close to 1, we
have desired control over T2 .
Proof of Theorem 2.2.
Proof.
We closely follow Rthe proof strategy of Robins et al. (2009). In particular, consider
R
P n : = Pλn dπ(λ) and Qn : = Qnλ dπ(λ) to be distributions of O1 , . . . , On and define probability
Iχ

Iχ

dP

dQ

measures on χj defined by Pj,λj = jpj λ and Qj,λj = jpj λ . Therefore, if pλ and qλ are densities
of Pλ and Qλ respectively with respect to some common dominating measure, then one has

Z
Z
χ2
Pλn dπ(λ), Qnλ dπ(λ)


2

k Q
R Q

I(Oi ∈ χj )qλ (Oi )dπj (λj ) 


 j=1 i
= EP n  k
 −1

R Q Q
I(Oi ∈ χj )pλ (Oi )dπj (λj )
j=1 i




= EP n 

k
Y

j=1

R

R

Q

i:Oi ∈χj

Q

i:Oi ∈χj

qj,λj (Oi )dπj (λj )

pj,λj (Oi )dπj (λj )

2


 − 1.

(6.1)

Define variables I1 , . . . , In such that Ii = j if OI ∈ χj for i = 1, . . . , n, j = 1, . . . , k and
let Nj = |{i: Ii = j}|. Now note that the measure P n arises as the distribution O1 , . . . , On
if this vector is generated in two steps as follows. First one chooses λ ∼ π and then given λ
O1 , . . . , On are generated independent pλ . This implies that given λ, (N1 , . . . , Nk ) is distributed
as Multinomial(Pλ (χ1 ), . . . , Pλ (χk )) = Multinomial(p1 , . . . , pk ) ⇒ (N1 , . . . , Nk ) ⊥ λ ⇒ under P n ,
(N1 , . . . , Nk ) ∼ Multinomial(p1 , . . . , pk ) unconditionally. Similarly, given λ, I1 , . . . , In are independent, and the event Ii = j has probability pj which is again free of λ. This in turn implies that
(I1 , . . . , In ) ⊥ λ under P n . The conditional distribution of O1 , . . . , On given λ and (I1 , . . . , In ) can
also be described as follows. For each partitioning set χj generate Nj variables independently from
Pλ restricted and renormalized to χj , i.e. from the measure Pj,λj . Now we can do so independently across the partitioning sets and attach correct labels {1, . . . , n} which are consistent with
(I1 , . . . , In ). The conditional distribution of O1 , . . . , On under P n given I1 , . . . , In is the mixture of
this distribution relative to the conditional distribution of λ given I1 , . . . , In , which by the virtue of
independence of I1 , . . . , In and λ under P n , was seen to be the unconditional distribution, π. Thus
we can obtain a sample from the conditional distribution under P n of O1 , . . . , On given
I1 , . . . , In
R
by generating for each partitioning set χj a set of Nj variables from the measure Pj,λj dπ(λj ),
independently across the partitioning sets, and next attaching labels consistent with I1 , . . . , In . The
above discussion allows us to write the right hand side of (6.1) as
2


R Q
qj,λj (Oi )dπj (λj )
k
Y



 R i:IQ
i =j
EP n EP n 
 |I1 , . . . , In  − 1

pj,λj (Oi )dπj (λj )
j=1

= EP n

k
Y

j=1

Ii =j

 R Q

qj,λj (Oi )dπj (λj )

2





 i:Ii =j
EP n  R Q
 |I1 , . . . , In  − 1
pj,λj (Oi )dπj (λj )
Ii =j

17

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS



= E

k
Y

j=1

ER

N

Pj,λj dπj (λj )
j

R

R

N

Qj,λj j dπj (λj )
N

Pj,λjj dπj (λj )

2 

 −1

c = maxj supλ
Arguing similar to Lemma 5.2 of Robins et al. (2009), we have with e
c = max{e
c, 1} that


E

k
Y

ER

j=1



≤ E


= E


≤ E

k
Y

j=1

N

Pj,λj dπj (λj )
j





1 + 2 

k
Y


R

N

Qj,λj j dπj (λj )
N

Pj,λjj dπj (λj )


Nj 
X
Nj
r=2

r

p2 dµ
χj p λ p j

and

2 

 −1

br + 2Nj2



Nj − 1 r
a b + 2Nj2 e
cNj −1 δ − 1
r

Nj −1 

X
r=1






(1 + b)Nj − 1 − Nj b + Nj2 (1 + a)Nj −1 − 1 b + 2Nj2 e
cNj −1 δ  − 1

1+2

j=1

k
Y


R

R






(1 + b)Nj − 1 − Nj b + Nj2 (1 + a)Nj −1 − 1 b + 2Nj2 cNj −1 δ  − 1

1+2

j=1

To bound the last quantity in the above display we use Shao (2000) to note that since Nj , j =
1, 
. . . , k is a multinomial
random
vector,
for any
f on the range of Nj ’s,


P

P increasing function
Qk
Qk
k
k
E
≤ exp
j=1 f (Nj ) = E exp
j=1 Nj
j=1 Ef (Nj ) =
j=1 Ef (Nj ). In this context,
noting that



1 + 2 (1 + b)Nj − 1 − Nj b + Nj2 (1 + a)Nj −1 − 1 b + 2Nj2 cNj −1 δ

is an increasing function in each coordinate of Nj (on the range of Nj ) we therefore have by Shao
(2000) that the last display is bounded by
k
Y

E

j=1



1+2




(1 + b)Nj − 1 − Nj b + Nj2 (1 + a)Nj −1 − 1 b + 2Nj2 cNj −1 δ
−1





(1 + bpj )n − 1 − nbpj

n−2
2

+npj (1 + apj )
(1 + napj + npj − pj )b − npj (1 − pj )b − npj b  − 1
=
1+2


j=1
+2δnpj (cpj + 1 − pj )n−2 (cnpj + 1 − pj )
k
Y

≤
≤



k
Y


1 + C (npj b)2 + (npj )2 ab + npj δ

j=1

k 
Y

j=1
Pk

≤e



−1



1 + Cn(max pj ) (npj )b + npj ab + npj δ − 1

j=1

2

j

(Cn(maxj pj )((npj )b2 +npj ab)+npj δ) − 1 = eCn2 (maxj pj )(b2 +ab)+Cnδ − 1

where we have used the fact that n(maxj pj ) (1 ∨ a ∨ b ∨ e
c) ≤ A for a positive constant A along
Pk
with j=1 pj = 1.

18

6.1. Proof of Theorem 2.3.
Proof. Let
jmin d

1


2βmax /d+1
n
⌋,
=⌊
log n

lmin d

1


2γmax /d+1
n
=⌊
⌋,
log n

2

2

jmax d

2

lmax d

2

1


2βmin /d+1
n
=⌊
⌋,
log n
1


2γmin /d+1
n
=⌊
⌋.
log n

Without loss of generality assume that we have data {xi , yi }2n
i=1 . We split it into two equal parts
and use the second part to construct the estimator ĝ of the design density g and us the resulting
ĝ to construct the adaptive estimate of the regression function from the first half of the sample.
Throughout the proof, EP,i [·] will denote the expectation with respect to the ith half of the sample,
with the other half held fixed, under the distribution P . Throughout we choose the regularity of
our wavelet bases to be larger than γmax for the desired approximation and moment properties to
hold. As a result our constants depend on γmax .
P
Define T1 = [jmin , jmax ]∩ N and T2 = [lmin , lmax ]∩ N. For l ∈ T2 , let ĝl (x) = n1 2n
i=n+1 KVl (Xi , x).
Now, let
)
(
r
ld ld
2
ˆ
, ∀l ∈ T2 s.t. l ≥ j .
l = min j ∈ T2 : kĝj − ĝl k∞ ≤ C ∗
n
where C ∗ is a constant (depending on γmax , BU ) that can be determined from the proof hereafter.
Thereafter, consider the estimator ge: = ĝl̂ .
Fix a P : = (f, g) ∈ P(β, γ). To analyze the estimator ge, we begin with standard bias variance
type analysis for the candidate estimators ĝl . First note that for any x ∈ [0, 1]d , using standard
facts about compactly supported wavelet basis having regularity larger than γmax (Härdle et al.,
1998), one has for a constant C1 depending only on q and the wavelet basis used,
γ

|EP (ĝl (x)) − g(x)| = |Π (g|Vl ) (x) − g(x)| ≤ C1 M 2−ld d .

(6.2)

Above we have used the fact that
sup
h∈H(γ,M )

kh − Π(h|Vl )k∞ ≤ C1 M 2−lγ .

(6.3)

Also, by standard arguments about compactly supported wavelet basis having regularity larger
than γmax (Giné and Nickl, 2015), one has for a constant C2 : = C(BU , ψ 00,0 , ψ 10,0 , γmax )
r
2ld ld
.
(6.4)
EP (kĝl (x) − EP (ĝl (x)) k∞ ) ≤ C2
n
Therefore, by (6.2), (6.4), and triangle inequality,
−ld γd

EP,2 kĝl − gk∞ ≤ C1 M 2

r

2ld ld
.
n

r

)

+ C2

Define,
∗

(

−ld γd

l : = min l ∈ T2 : C1 M 2

≤ C2

2ld ld
n

.

19

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

The definition of l∗ implies that for n sufficiently large,
d

2



C1
M
C2



2d
2γ+d



n
log n



d
2γ+d

l∗ d

≤2

d+1

≤2



C1
M
C2



2d
2γ+d



n
log n



d
2γ+d

.

The error analysis of ge can now be carried out as follows.




g − gk∞ I ˆl > l∗
EP,2 ke
g − gk∞ = EP,2 ke
g − gk∞ I ˆl ≤ l∗ + EP,2 ke
: = I + II.

(6.5)

(6.6)

We first control term I as follows.



I = EP,2 ke
g − gk∞ I ˆl ≤ l∗




≤ EP,2 kĝl̂ − ĝl∗ k∞ I ˆl ≤ l∗ + EP,2 kĝl∗ − gk∞ I ˆl ≤ l∗
r ∗
r ∗
l d l∗ d
γ
2
2l d l∗ d
∗
≤ C∗
+ C1 M 2−l d d + C2
n
n
r ∗
 2d 

− γ
l
d
∗
2γ+d
2γ+d
n
2 l d
d+1 C1
∗
.
≤2
M
≤ (C + 2C2 )
n
C2
log n

(6.7)

The control of term II is easier if one has suitable bounds on kĝl − gk∞ . To this end note that, for
any fixed x ∈ [0, 1]d , there exists a constant C3 : = C(ψ 00,0 , ψ 10,0 , γmax )
|ĝl (x)| ≤

n
1XX
n

X

i=1 k∈Zl v∈{0,1}d

v
v
|ψl,k
(Xi )||ψl,k
(x)| ≤ C3 2ld .

This along with the fact that kgk∞ ≤ BU , implies that for n sufficiently large,
kĝl − gk∞ ≤ C3 2ld + BU ≤ 2C3 2ld .
In the above display the last inequality follows since l ≥ lmin ≥
II ≤ C3

lX
max
l=l̂



2ld P ˆl = l .



n
log n



1
2γmax /d+1

. Therefore,
(6.8)



ˆ
We now complete the control over II by suitably bounding P l = l . To this end, note that for any
l > l∗ ,


PP,2 ˆl = l
!
r
ld ld
X
2
≤
PP,2 kĝl − ĝl∗ k∞ > C ∗
n
l>l∗


 
q
∗
ld ld


C
2


∗

X  PP,2 kĝl∗ − E (ĝl∗ ) k∞ > 2
n − kEP,2 (ĝl ) − EP,2 (ĝl ) k∞


q
≤
∗


2ld ld

+PP,2 kĝl − EP,2 (ĝl ) k∞ > C2
l>l∗ 


n

20




q

2ld ld
C∗

∗
∗
∗
)
−
Π
(g|V
)
k
−
kΠ
(g|V
P
)
k
>
−
E
(ĝ
kĝ
∞
∞
l
l
l
l
X  P,2
2
n


q
≤
∗

2ld ld
+P kĝl − EP,2 (ĝl ) k∞ > C2
l>l∗ 

n

 

q ∗
q


2ld ld
2l d l∗ d
C∗


∗
∗

X  PP,2 kĝl − E (ĝl ) k∞ > 2
n − 2C2
n


q
≤
∗


2ld ld

+P kĝl − EP,2 (ĝl ) k∞ > C2
l>l∗ 


n


 
q
∗
ld ld


C
2



X  PP,2 kĝl∗ − E (ĝl∗ ) k∞ > ( 2 − 2C2 )
n


q
≤
∗


2ld ld

+P kĝl − EP,2 (ĝl ) k∞ > C2
l>l∗ 


n
X
2 exp (−Cld),
≤









l>l∗

(6.9)

In the fourth and fifth of the above series of inequalities, we have used (6.3) and the definition of l∗
respectively. The last inequality in the above display holds for a C > 0 depending on BU , ψ 00,0 , ψ 10,0
and the inequality follows from Lemma B.6 provided we choose C ∗ large enough depending on
M, BU , ψ 00,0 , ψ 10,0 , γmax . In particular, this implies that, choosing C ∗ large enough will guarantee
that there exists a η > 3 such that for large enough n, one has for any l > l∗
P(ˆl = l) ≤ n−η .

(6.10)

This along with 6.8 and choice of lmax implies that
II ≤ C3

X

l>l∗

2ld n−η = C3

X 2ld

l>l∗

n

n−η+1 ≤

lmax
log n
≤
.
nη−1
n

(6.11)

Finally combining equations (6.7) and (6.11), we have the existence of an estimator ge depending
on M, BU , and γmax (once we have fixed our choice of father and mother wavelets), such that for
every (β, γ) ∈ [βmin , βmax ] × [γmin , γmax ],
− γ

2γ+d
d
n
,
sup EP ke
g − gk∞ ≤ (C) 2γ+d
log n
P ∈P(β,γ)
with a large enough positive C depending on M, BU , and γmax .
We next show that uniformly over P ∈ P(β, γ), ge belongs to H(γ, C) with probability at least
1 − 1/n2 , for a large enough constant C depending on M, BU , and γmax . Towards this end, note
′
that, for any C > 0 and l > 0, (letting for any h ∈ L2 [0, 1]d , khh, ψ l′ ,· ik2 be the vector L2 norm of


′
the vector hh, ψ vl′ ,k′ i: k ∈ Zl′ , v ∈ {0, 1}d − {0}d . We have,
 ′

d
PP,2 2l (γ+ 2 ) khe
g , ψ l′ ,· ik∞ > C
=

lX
max

l=lmin
∗

=

l
X

l=lmin

 ′

 ′
d
PP,2 2l (γ+ 2 ) khĝl , ψ l′ ,· ik∞ > C, ˆl = l I l ≤ l
 ′
 ′

d
PP,2 2l (γ+ 2 ) khĝl , ψ l′ ,· ik∞ > C, ˆl = l I l ≤ l

21

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS
lX
max

+

l=l∗ +1
∗

l
X

≤

l=lmin

+

lX
max

l=l∗ +1
∗

≤

l
X

l=lmin

 ′

 ′
d
PP,2 2l (γ+ 2 ) khĝl , ψ l′ ,· ik∞ > C, ˆl = l I l ≤ l

 ′
 ′

d
PP,2 2l (γ+ 2 ) khĝl , ψ l′ ,· ik∞ > C I l ≤ l

 ′

PP,2 ˆl = l I l ≤ l

 ′
 X
 ′
d
n−η ,
PP,2 2l (γ+ 2 ) khĝl , ψ l′ ,· ik∞ > C I l ≤ l +

(6.12)

l>l∗

where the last inequality follows from (6.10) for some η > 3 provided C ∗ is chosen large enough
as before. Now,

 ′
d
PP,2 2l (γ+ 2 ) khĝl , ψ l′ ,· ik∞ > C
 ′



d
≤ PP,2 2l (γ+ 2 ) khĝl , ψ l′ ,· i − EP,2 hĝl , ψ l′ ,· i k∞ > C/2
 ′



d
+ PP,2 2l (γ+ 2 ) kEP,2 hĝl , ψ l′ ,· i k∞ > C/2



 ′
d
= PP,2 2l (γ+ 2 ) khĝl , ψ l′ ,· i − EP,2 hĝl , ψ l′ ,· i k∞ > C/2

if C > 2M (by definition 5.5). Therefore, from (6.12), one has for any C > 2M ,

 ′
d
PP,2 2l (γ+ 2 ) khĝ, ψ l′ ,· ik∞ > C
∗

≤
+

l
X

l=lmin
lX
max
l=l∗

 ′


 ′

d
PP,2 2l (γ+ 2 ) khĝl , ψ l′ ,· i − EP,2 hĝl , ψ l′ ,· i k∞ > C/2 I l ≤ l

′

n−3 I l ≤ l .

(6.13)

Considering the first term of the last summand of the above display, we have
∗

l
X

l=lmin

=

 ′


 ′

d
PP,2 2l (γ+ 2 ) khĝl , ψ l′ ,· i − EP,2 hĝl , ψ l′ ,· i k∞ > C/2 I l ≤ l

∗

l
X
X

X

PP,2

l=lmin k∈Zl′ v∈{0,1}d

2n


C/2
1 X  v
> ′
ψl′ ,k (Xi ) − EP,2 ψlv′ ,k (Xi )
d
n
2l (γ+ 2 )
i=n+1

By Bersntein’s Inequality, for any λ > 0,
2n


1 X  v
>λ
ψl′ ,k (Xi ) − EP,2 ψlv′ ,k (Xi )
PP,2
n
i=n+1


2
nλ
 ,
≤ 2 exp − 
v
2
2 σ + kψl′ ,k k∞ λ/3

!

!

′

I l ≤l

22


2

. Indeed, there exists constant C4 depending on
where σ 2 = EP,2 ψlv′ ,k (Xi ) − EP,2 ψlv′ ,k (Xi )
the ψ 00,0 , ψ 10,0 , γmax such that σ 2 ≤ C4 and kψlv′ ,k k∞ ≤ C4 2
∗

′
l d
2

. Therefore,

2n


C/2
1 X  v
ψl′ ,k (Xi ) − EP,2 ψlv′ ,k (Xi )
> ′
PP,2
d
l
n
2 (γ+ 2 )
i=n+1
l=lmin k∈Z ′ v∈{0,1}d
l


′
l∗
′

−2l (γ+ d2 )
2
X
X X
n2
C

exp −
I
l
≤
l
≤2
′
′
d
l d
8C4
1 + C2 2 2 2−l (γ+ 2 )
l=lmin k∈Zl′ v∈{0,1}d
!
′
l∗
′

X
X X
n2−2l γ
C2
=2
exp −
I
l
≤
l
′
′
8C4 2l d + C 2l (d−γ)
d
l
X
X

X

≤2

X X

X

l
X
X

X

′

I l ≤l

2

l=lmin k∈Zl′ v∈{0,1}
l∗

!

C2
n2−2l
exp −
′
8(1 + C2 )C4 2l d
d

l=lmin k∈Z ′ v∈{0,1}
l

′

γ

!

′

I l ≤l

!
∗
′

C2
n2−2l γ (l∗ −l)(d+2γ) ∗
=2
exp −
2
l
d
I
l
≤
l
∗
8(1 + C2 )C4 2l d l∗ d
l=lmin k∈Zl′ v∈{0,1}d
!
l∗
′

X
X X
C 2 C2
∗
(l −l)(d+2γ) ∗
2
l
d
I
l
≤
l
exp − d+3
≤2
2 C1 (1 + C2 )C4
l=lmin k∈Zl′ v∈{0,1}d
!
l∗
′

X X
X
C 2 C2
exp − d+3
≤2
ld
I
l
≤
l
2 C1 (1 + C2 )C4
l=lmin k∈Z ′ v∈{0,1}d
l
!
l∗
′

X
′
C 2 C2
0
1
l d
C(ψ0,0 , ψ0,0 )2 exp − d+3
≤2
ld
I
l
≤
l
2 C1 (1 + C2 )C4
l=lmin
! !
l∗
′

X
C 2 C2
0
1
−
1
ld
I
l
≤
l
C(ψ0,0 , ψ0,0 ) exp −
≤2
2d+3 C1 (1 + C2 )C4
l=lmin
!
!

′
2C
C
2
0
1
,
−
1
l
d
I
l
≤
l
≤ 2lmax C(ψ0,0
, ψ0,0
) exp −
min
max
2d+3 C1 (1 + C2 )C4
∗

(6.14)

C 2 C2
2d+3 C1 (1+ C
)C4
2

≥ 1. Above inequality 6.14 uses the definition of l∗ . Indeed choosing C large


2C
2
enough, one can guarantee, 2d+3 CC (1+
−
1
lmin d ≥ 4 log n. Such a choice of C implies that,
C
)C

if

1

∗

l
X
X

X

l=lmin k∈Z ′ v∈{0,1}d
l

≤

PP,2

2

4

2n


C/2
1 X  v
> ′
ψl′ ,k (Xi ) − EP,2 ψlv′ ,k (Xi )
d
n
2l (γ+ 2 )
i=n+1

!

′

I l ≤l

0 , ψ1 )
C(ψ0,0
′
0,0
I(l ≤ lmax ),
3
n

0 , ψ 1 ) one has
which in turn implies that, for C sufficiently large (depending on M, ψ0,0
0,0

 C(ψ 0 , ψ 1 ) + 1 ′
 ′
d
0,0
0,0
I(l ≤ lmax ).
PP,2 2l (γ+ 2 ) khĝ, ψ l′ ,· ik2 > C ≤
n3

23

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

This along with the logarithmic in n size of lmax implies that for sufficiently large n, uniformly over
P ∈ P(β, γ), e
g belongs to H(γ, C) with probability at least 1 − 1/n2 , for a large enough constant
0 , ψ 1 being fixed by specifying a regularity
C depending on M, BU , and γmax (the choice of ψ0,0
0,0
S > γmax ).
However this ge does not satisfy the desired point-wise bounds. To achieve this let φ be a C ∞
function such that ψ(x)|[BL ,BU ] ≡ x while B2L ≤ ψ(x) ≤ 2BU for all x. Finally, consider the
estimator ĝ(x) = ψ(e
g (x)). We note that |g(x) − ĝ(x)| ≤ |g(x) − e
g(x)|— thus ĝ is adaptive to the
smoothness of the design density. The boundedness of the constructed estimator follows from the
construction. Finally, we wish to show that almost surely, the constructed estimator belongs to the
Hölder space with the same smoothness, possibly of a different radius. This is captured by the next
lemma, proof of which can be completed by following arguments similar to proof of Lemma 3.1 in
Mukherjee and Sen (2016). In particular,
Lemma 6.2. For all h ∈ H(β, M ), ψ(h) ∈ H(β, C(M, β)), where C(M, β) is a universal constant dependent only on M, β and independent of h ∈ H(β, M ).
Now, the construction of fˆ satisfying the desired properties of Theorem 2.3 can be done following
ideas from proof of Theorem 1.1 of Mukherjee and Sen (2016). In particular, construct the estimator
ĝ of the design density g as above from second part of the sample and let for j ∈ T1 , fˆj (x) =
n
1 P Wi
n
ĝ(Xi ) KVj (Xi , x). Now, let
i=1

(

ĵ = min j ∈ T1 : kfˆj − fˆj ′ k∞ ≤ C ∗∗

r

2j ′ d j ′ d
, ∀j ′ ∈ T1 s.t. j ′ ≥ j
n

)

.

where C ∗∗ depends only on the known parameters of the problem and can be determined from the
proof hereafter. Thereafter, consider the estimator fe: = fˆĵ .
Now define
(
)
r
2jd jd
∗
−jd βd
j : = min j ∈ T1 : 2
,
≤
n
Therefore
EP kfe − f k∞ ≤ EP kfˆĵ − f k∞ I(ĵ ≤ j ∗ ) + EP kfˆĵ − f k∞ I(ĵ > j ∗ ).

Thereafter using Lemma B.6 and 6.3 we have
EP kfˆĵ − f k∞ I(ĵ ≤ j ∗ )

≤ EP kfˆĵ − fˆj ∗ k∞ I(ĵ ≤ j ∗ ) + EP kfˆj ∗ − f k∞
r ∗
2j d j ∗ d
∗∗
+ EP,2 kfˆj ∗ − EP,1 (fˆj ∗ )k∞ + EP,2 kEP,1 (fˆj ∗ ) − f k∞
≤C
n
r ∗
2j d j ∗ d
≤ (C ∗∗ + C(BU , BL , ψ 00,0 , ψ 10,0 ))
n
g
+ EP,2 kΠ(f ( − 1)|Vj ∗ )k∞ + kf − Π(f |Vj ∗ )k∞
ĝ
r ∗
2j d j ∗ d
≤ (C ∗∗ + C(BU , BL , ψ 00,0 , ψ 10,0 ))
n

(6.15)

24

+ C(M, ψ 00,0 , ψ 10,0 )2−j

∗β

g
+ EP,2 kΠ(f ( − 1)|Vj ∗ )k∞ .
ĝ
(6.16)

Now, by standard computations involving compactly wavelet bases and property of ĝ
g
g
EP,2 kΠ(f ( − 1)|Vj ∗ )k∞ ≤ C(ψ 00,0 , ψ 10,0 )EP,2 kf ( − 1)k∞
ĝ
ĝ
≤ C(BU , BL , ψ 00,0 , ψ 10,0 )EP,2 kĝ − gk∞
− γ

2γ+d
n
0
1
.
≤ C(BU , BL , M, γmax , ψ 0,0 , ψ 0,0 )
log n

(6.17)

Combining (6.16), (6.17), definition of j ∗ , and the fact that γ > β, we have
EP kfˆĵ − f k∞ I(ĵ ≤ j ∗ ) ≤ C(BU , BL , M, γmax , ψ 00,0 , ψ 10,0 )



n
log n

−

β
2β+d

.

(6.18)

provided C ∗ ∗ is chosen depending only the known parameters of the problem. Now using arguments
similar to those leading to (6.8) we have
X
EP kfˆĵ − f k∞ I(ĵ > j ∗ ) ≤ C(BU , BL , ψ 00,0 , ψ 10,0 )
2jd PP (ĵ = j).
(6.19)
j>j ∗

We now complete the control over II by suitably bounding PP (ĵ = j). To this end, note that for
any j > j ∗ ,
PP (ĵ = j)
X
≤
PP

!
jd jd
2
kfˆj − fˆj ∗ k∞ > C
n
∗
j>j


q
 
   
 
jd jd
∗∗

2
C
ˆ ∗ − EP,1 fˆj k∞ 


 PP,1 kfˆj ∗ − EP,1 fˆj ∗ k∞ > 2

X
n − kEP,1 fj


q
≤
EP,2
 
∗∗


2jd jd


j>j ∗
+PP,1 kfˆj − EP,1 fˆj k∞ > C2


n




q

 



jd jd
∗∗


2
g
g
C

∗
− Π f ĝ |Vj k∞ 
 PP,1 kfˆj ∗ − EP,1 fˆj ∗ k∞ > 2

X
n − kΠ f ĝ |Vj


q
≤
EP,2
.
 
∗∗


2jd jd


j>j ∗
+PP,1 kfˆj − EP,1 fˆj k∞ > C2


n
∗∗

r

Now,



g
Π f |Vj ∗
ĝ





g
− Π f |Vj
ĝ
∗



∞

≤ C(M, ψ 00,0 , ψ 10,0 )2−j β + C(BU , BL , , ψ 00,0 , ψ 10,0 )kĝ − gk∞ .
q ∗
q
2jd jd
2j d j ∗ d
Using the fact that
>
for j > j ∗ , we have using the definition of j ∗ that there
n
n
exists C, C ′ > 0 depending on M, BU , BL , ψ 00,0 , ψ 10,0 such that
PP (ĵ = j)

25

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS








q
 
2jd jd
C ∗∗
ˆ
ˆ
∗
∗
−
C)
P
k
f
−
E
f
k
>
(
P,1
j
P,1
j
∞
X
2
n




q ∗
q
≤
EP,2
 

2jd jd
2j d j ∗ d
C ∗∗
′
ˆ
ˆ

∗
j>j
+ PP,2 kĝ − gk∞ > C
 +PP,1 kfj − EP,1 fj k∞ > 2
n
n









.

(6.20)

Now, provided C ∗∗ > 2C is chosen large enough (depending on BU , BL , ψ 00,0 , ψ 10,0 ) we have there
exists large enough C ′′ (depending on BU , BL , ψ 00,0 , ψ 10,0 ) such that
!
r
∗∗
jd jd
2
C
− C)
PP,1 kfˆj ∗ − EP,1 fˆj ∗ k∞ > (
2
n
!
r
 
C ∗∗ 2jd jd
′′
+ PP,1 kfˆj − EP,1 fˆj k∞ >
≤ 2e−C jd .
2
n




(6.21)

Henceforth, whenever required, C, C ′ , C ′′ will be chosen to be large enough depending on the known
parameters of the problem, which in turn will imply that C ∗∗ can be chosen large enough depending
on the known parameters of the problem as well. First note that, the last term in the above display
can be bounded rather crudely using the following lemma.
Lemma 6.3. Assume γmin > βmax . Then for C ′ , C1 , C2 > 0 (chosen large enough depending on
BU , ψ 00,0 , ψ 10,0 ) one has
sup
P ∈P(β,γ)



PP,2 kĝ − gk∞ > C

′

r

2j ∗ d j ∗ d 
≤ C1 (lmax − lmin )e−C2 lmin d .
n

g ), where ψ(x) is C ∞ function
The proof of Lemma 6.3 can be argued as follows. Indeed, ĝ = ψ(e
which is identically equal to x on [BL , BU ] and has universally bounded first derivative. Therefore,
it is enough to prove Lemma 6.3 for ge instead of ĝ and thereby invoking a simple first order Taylor
series argument along with the fact that ψ(g) ≡ g owing to the bounds on g. The crux of the
argument for proving Lemma 6.3 is that
q by Lemma B.6, any ĝl for l ∈ T2 suitably concentrates
around g in a radius of the order of

2ld ld
n .

The proof of the lemma is therefore very similar to
the proof of adaptivity of ĝ (by dividing into cases where the chosen ˆl is larger and smaller than l∗
respectively and thereafter invoking Lemma B.6) and therefore we omit the details.
Plugging in the result of Lemma 6.3 into (6.20), and thereafter using the facts that γmin > βmax ,
lmax , jmax are both poly logarithmic in nature, along with equations (6.15), and (6.18), (6.19), (6.21)
we have the existence of an estimator fe depending on M, BU , BL , βmin , βmax , γmax , such that for
every (β, γ) ∈ [βmin , βmax ] × [γmin , γmax ],
sup
P ∈P(β,γ)

EP kfe − f k∞ ≤ C



n
log n

−

β
2β+d

,

with a large enough positive constant C depending on M, BU , BL , βmin , γmax , ψ 00,0 , ψ 10,0 .
However this fe does not satisfy the desired point-wise bounds. To achieve this, as before, let φ
be a C ∞ function such that ψ(x)|[BL ,BU ] ≡ x while B2L ≤ ψ(x) ≤ 2BU for all x. Finally, consider
the estimator fˆ(x) = ψ(e
g (x)). We note that |f (x) − fˆ(x)| ≤ |f (x) − fe(x)|— thus fˆ is adaptive to
the smoothness of the design density. The boundedness of the constructed estimator follows from

26

the construction. Finally,the proof of the fact that the constructed estimator belongs to the Hölder
space with the same smoothness, possibly of a different radius follows once again from of Lemma
6.2.
References.
Baraud, Y. (2002). Model selection for regression on a random design. ESAIM: Probability and Statistics 6 127–146.
Bickel, P. J. and Ritov, Y. (1988). Estimating integrated squared density derivatives: sharp best order of convergence estimates. Sankhyā: The Indian Journal of Statistics, Series A 381–393.
Bickel, P. J., Klaassen, C. A., Bickel, P. J., Ritov, Y., Klaassen, J., Wellner, J. A. and Ritov, Y. (1993).
Efficient and adaptive estimation for semiparametric models. Johns Hopkins University Press Baltimore.
Birgé, L. and Massart, P. (1995). Estimation of integral functionals of a density. The Annals of Statistics 11–29.
Brown, L. D. and Levine, M. (2007). Variance estimation in nonparametric regression via the difference sequence
method. The Annals of Statistics 35 2219–2232.
Brown, L. D. and Low, M. G. (1996). A constrained risk inequality with applications to nonparametric functional
estimation. The annals of Statistics 24 2524–2535.
Bull, A. D. and Nickl, R. (2013). Adaptive confidence sets in Lˆ 2. Probability Theory and Related Fields 156
889–919.
Cai, T. T. and Low, M. G. (2003). A note on nonparametric estimation of linear functionals. Annals of statistics
1140–1153.
Cai, T. T. and Low, M. G. (2004). Minimax estimation of linear functionals over nonconvex parameter spaces.
Annals of statistics 552–576.
Cai, T. T. and Low, M. G. (2005a). Nonquadratic estimators of a quadratic functional. The Annals of Statistics
2930–2956.
Cai, T. T. and Low, M. G. (2005b). On adaptive estimation of linear functionals. The Annals of Statistics 33
2311–2343.
Cai, T. T. and Low, M. G. (2006). Optimal adaptive estimation of a quadratic functional. The Annals of Statistics
34 2298–2325.
Cai, T. T. and Low, M. G. (2011). Testing composite hypotheses, Hermite polynomials and optimal estimation of
a nonsmooth functional. The Annals of Statistics 39 1012–1041.
Cai, T. T. and Wang, L. (2008). Adaptive variance function estimation in heteroscedastic nonparametric regression.
The Annals of Statistics 36 2025–2054.
Cohen, A., Daubechies, I. and Vial, P. (1993). Wavelets on the interval and fast wavelet transforms. Applied and
computational harmonic analysis 1 54–81.
Crump, R. K., Hotz, V. J., Imbens, G. W. and Mitnik, O. A. (2009). Dealing with limited overlap in estimation
of average treatment effects. Biometrika asn055.
Donoho, D. L., Liu, R. C. and MacGibbon, B. (1990). Minimax risk over hyperrectangles, and implications. The
Annals of Statistics 1416–1437.
Donoho, D. L. and Nussbaum, M. (1990). Minimax quadratic estimation of a quadratic functional. Journal of
Complexity 6 290–323.
Efromovich, S. and Low, M. G. (1994). Adaptive estimates of linear functionals. Probability theory and related
fields 98 261–275.
Efromovich, S. and Low, M. (1996). On optimal adaptive estimation of a quadratic functional. The Annals of
Statistics 24 1106–1125.
Efromovich, S. and Samarov, A. (2000). Adaptive estimation of the integral of squared regression derivatives.
Scandinavian journal of statistics 27 335–351.
Fan, J. (1991). On the estimation of quadratic functionals. The Annals of Statistics 1273–1294.
Fan, J. and Yao, Q. (1998). Efficient estimation of conditional variance functions in stochastic regression. Biometrika
85 645–660.
Giné, E., Latala, R. and Zinn, J. (2000). Exponential and moment inequalities for U-statistics. In High Dimensional
Probability II 13–38. Springer.
Giné, E. and Nickl, R. (2008). A simple adaptive estimator of the integrated square of a density. Bernoulli 47–61.
Giné, E. and Nickl, R. (2015). Mathematical foundations of infinite-dimensional statistical models. Cambridge
Series in Statistical and Probabilistic Mathematics.
Hall, P. and Carroll, R. (1989). Variance function estimation in regression: the effect of estimating the mean.
Journal of the Royal Statistical Society. Series B (Methodological) 3–14.
Hall, P. and Marron, J. S. (1987). Estimation of integrated squared density derivatives. Statistics & Probability
Letters 6 109–115.

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

27

Härdle, W., Kerkyacharian, G., Tsybakov, A. and Picard, D. (1998). Wavelets, approximation, and statistical
applications. Springer.
Houdré, C. and Reynaud-Bouret, P. (2003). Exponential inequalities, with constants, for U-statistics of order
two. 55–69.
Ibragimov, I. A. and Has’ minskii, R. Z. (2013). Statistical estimation: asymptotic theory 16. Springer Science &
Business Media.
Kerkyacharian, G. and Picard, D. (1996). Estimating nonquadratic functionals of a density using Haar wavelets.
The Annals of Statistics 24 485–507.
Klemela, J. and Tsybakov, A. B. (2001). Sharp adaptive estimation of linear functionals. The Annals of statistics
1567–1600.
Laurent, B. (1996). Efficient estimation of integral functionals of a density. The Annals of Statistics 24 659–681.
Laurent, B. and Massart, P. (2000). Adaptive estimation of a quadratic functional by model selection. Annals of
Statistics 1302–1338.
Lepski, O. (1991). On a problem of adaptive estimation in Gaussian white noise. Theory of Probability & Its Applications 35 454–466.
Lepski, O. V. (1992). On problems of adaptive estimation in white Gaussian noise. Topics in nonparametric estimation 12 87–106.
Low, M. G. (1992). Renormalization and white noise approximation for nonparametric functional estimation problems. The Annals of Statistics 545–554.
Mukherjee, R., Newey, W. K. and Robins, J. M. (2017). Semiparametric Efficient Empirical Higher Order
Influence Function Estimators. arXiv preprint arXiv:1705.07577.
Mukherjee, R. and Sen, S. (2016). Optimal Adaptive Inference in Random Design Binary Regression. Bernoulli
(To Appear).
Mukherjee, R., Tchetgen Tchetgen, E. and Robins, J. (2017). Supplement to “Adpative Estimation of Nonparametric Functionals”.
Nemirovski, A. (2000). Topics in non-parametric. Ecole dEté de Probabilités de Saint-Flour 28 85.
Petrov, V. V. (1995). Limit Theorems of Probability Theory. Sequences of Independent Random Variables, vol. 4
of. Oxford Studies in Probability.
Robins, J. M., Mark, S. D. and Newey, W. K. (1992). Estimating exposure effects by modelling the expectation
of exposure conditional on confounders. Biometrics 479–495.
Robins, J., Li, L., Tchetgen, E. and van der Vaart, A. (2008). Higher order influence functions and minimax
estimation of nonlinear functionals. In Probability and Statistics: Essays in Honor of David A. Freedman 335–421.
Institute of Mathematical Statistics.
Robins, J., Tchetgen, E. T., Li, L. and van der Vaart, A. (2009). Semiparametric minimax rates. Electronic
Journal of Statistics 3 1305–1321.
Robins, J., Li, L., Mukherjee, R., Tchetgen, E. T. and van der Vaart, A. (2016). Higher Order Estimating
Equations for High-dimensional Models. The Annals of Statistics (To Appear).
Ruppert, D., Wand, M. P., Holst, U. and HöSJER, O. (1997). Local polynomial variance-function estimation.
Technometrics 39 262–273.
Shao, Q.-M. (2000). A comparison theorem on moment inequalities between negatively associated and independent
random variables. Journal of Theoretical Probability 13 343–356.
Tribouley, K. (2000). Adaptive estimation of integrated functionals. Mathematical Methods of Statistics 9 19–38.
Tsiatis, A. (2007). Semiparametric theory and missing data. Springer Science & Business Media.
Van der Vaart, A. W. (2000). Asymptotic statistics 3. Cambridge university press.

APPENDIX A: PROOF OF REMAINING THEOREMS
Proof of Theorem 3.1.
Proof.
(i) Proof of Upper Bound
The general scheme of proof involves identifying a non-adaptive minimax estimator of φ(P )
under the knowledge of P ∈ P(α,β,γ) , demonstrating suitable bias and variance properties of this
sequence of estimators, and thereafter invoking Theorem 2.1 to conclude. This routine can be carried out as follows. Without loss of generality assume that we have 3n samples {Yi , Ai , Xi }ni=1 .
Divide the samples in to 3 equal parts (with the lth part being indexed by {(l − 1)n + 1, . . . , ln}

28

for l ∈ {1, 2, 3}), estimate g by ĝ adaptively from the third part (as in Theorem 2.3), and estimate a and b by â and b̂ respectively, adaptively from the second part (as in Theorem 2.3). Let
EP,S denote the expectation while samples with indices in S held fixed, for S ⊂ {1, 2, 3}. A first
order influence function for φ(P ) at P P
is given by (Y − b(X)(A − a(X))) − φ(P ) and a result1
ing first order
estimator for φ(P ) is n ni=1 (Yi − b̂(Xi ))(Ai − â(Xi )). This estimator has a bias
R
d
EP,{2,3}
(b(x) − b̂(x))(a(x) − â(x)) g(x)dx. Indeed for α+β
2 < 2 , this bias turns out to be sub4α+4β

optimal compared to the minimax rate of convergence of n− 2α+2β+d in mean squared loss. The
most intuitive way to proceed is to estimate
R and correct for the bias. If there exists a “dirac-kernel”
K(x1 , x2 ) ∈ L2 [0, 1]d × [0, 1]d such that h(x1 )K(x1 , x2 )dx2 = h(x1 ) almost surely x1 for all h ∈
P
(Ai2 −â(Xi2 ))
(Yi1 −b̂(Xi1 )))
1
√
K(Xi1 , Xi2 ) √
,
L2 [0, 1]d , then one can estimate the bias term by n(n−1)
g(Xi1 )

1≤i1 6=i2 ≤n

g(Xi2 )

provided the marginal density g was known. Indeed there are two concerns with the above suggestion. The first one being the knowledge of g. This can be relatively easy to deal with by plugging in
an suitable estimate ĝ–although there are some subtleties involved (refer to to Section 4 for more on
this). The primary concern though is the non-existence of a “dirac-kernel” of the above sort as an
element of L2 [0, 1]d × L2 [0, 1]d . This necessitates the following modification where one works with
projection kernels on suitable finite dimensional linear subspace L of L2 [0, 1]d which guarantees
existence of such kernels when the domain space is restricted to L. In particular, we work with the
linear subspace Vj (defined in 5) where the choice of j is guided by the balance between the bias
and variance properties of the resulting estimator. In particular, a choice of 2j is guided by the
knowledge of the parameter space P(α,β,γ) . For any j such that n ≤ 2jd ≤ n2 , this implies that our
bias corrected second order estimator of φ(P ) is given by
n

φ̂n,j =

1X
(Yi − b̂(Xi ))(Ai − â(Xi ))
n
i=1

1
−
n(n − 1)

X

S

1≤i1 6=i2 ≤n

(Yi1 − b̂(Xi1 )))
(Ai2 − â(Xi2 ))
p
KVj (Xi1 , Xi2 ) p
ĝ(Xi1 )
ĝ(Xi2 )

!

Note that division by ĝ is permitted by the properties guaranteed by Theorem 2.3. Indeed this
sequence of estimators is in the form of those considered by Theorem 2.1 with
L1 (O) = (Y − b̂(X))(A − â(X)),
L2l (O) =

(Y − b̂(X)))
p
,
ĝ(X)

L2r (O) =

(A − â(X)))
p
,
ĝ(X)

where by Theorem 2.3 max{|L1 (O)|, |L2l (O)|, |L2r (O)|} ≤ C(BL , BU ). Therefore it remains to show
that these sequence φ̂n,j satisfies the bias and variance property (A) and (B) necessary for application of Theorem 2.1.
We first verify the bias property. Utilizing the representation of the first order bias as stated
above, we have


|EP φ̂n,j − φ(P ) |
hR 

i
(b(x) − b̂(x))(a(x) − â(x)) g(x)dx
EP,{2,3}
 

=
(Y1 −b̂(X1 )))
(A2 −â(X2 ))
√
−EP S
KVj (X1 , X2 ) √
ĝ(X1 )

ĝ(X2 )

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

29

(A.1)
Now, using the notation δb(x) = b(x) − b̂(x) and δa(x) = a(x) − â(x), we have
"
#
(Y1 − b̂(X1 )))
(A2 − â(X2 ))
p
EP
KVj (X1 , X2 ) p
ĝ(X1 )
ĝ(X2 )
#
Z Z "
δa(x2 )g(x2 )
δb(x1 )g(x1 )
p
KVj (x1 , x2 ) p
dx1 dx2
= EP,{2,3}
ĝ(x1 )
ĝ(x2 )
#


Z "
δb(x1 )g(x1 )
δag
p
= EP,{2,3}
Π √ |Vj (x1 ) dx1
ĝ
ĝ(x1 )
#
Z "
δb(x1 )g(x1 ) δa(x1 )g(x1 )
p
p
dx1
= EP,{2,3}
ĝ(x1 )
ĝ(x1 )
#


Z "
δb(x1 )g(x1 )
δag ⊥
p
− EP,{2,3}
Π √ |Vj (x1 ) dx1
ĝ
ĝ(x1 )

Z 

= EP,{2,3}
(b(x) − b̂(x))(a(x) − â(x)) g(x)dx


Z 
1
1
2
+ EP,{2,3}
−
dx1
δa(x1 )δb(x1 )g (x1 )
ĝ(x1 ) g(x1 )
#


Z "
δag ⊥
δb(x1 )g(x1 )
p
Π √ |Vj (x1 ) dx1
− EP,{2,3}
ĝ
ĝ(x1 )

Plugging in A.2 into A.1, we get,


|EP φ̂n,j − φ(P ) |

i
Rh
δa(x1 )δb(x1 )g2 (x1 ) ĝ(x1 1 ) − g(x1 1 ) dx1
EP,{2,3}


=
R δb(x1 )g(x1 )  δag ⊥ 
√
√
|V
(x1 ) dx1
−EP,{2,3}
Π
ĝ j

(A.2)

ĝ(x1 )

(A.3)

Now, by repeatedly applying Cauchy-Schwarz Inequality and invoking results in Theorem 2.3, we
have
Z 




1
1
EP,{2,3}
δa(x1 )δb(x1 )g (x1 )
−
dx1
ĝ(x1 ) g(x1 )
 12

Z
g4 (x1 )
2
(ĝ(x1 ) − g(x1 )) dx1
≤ EP,{3}
g(x1 )ĝ(x1 )

1
1 
Z
Z 
4
4
4
4
× EP,{2,3} (â(x1 ) − a(x1 )) dx1
EP,{2,3}
b̂(x1 ) − b(x1 ) dx1
2

1
1 
1 
4 4
BU2 
2 2
4 4
≤
EP,{3} kĝ − gk2
EP,{2,3} kâ − ak4
EP,{2,3} b̂ − b
BL
4
β
γ
α


− 2α+d − 2β+d − 2γ+d
d
d
d
B2
n
≤ U (C) 2γ+d + 2α+d + 2β+d
BL
log n

(A.4)

30

Moreover,
Z "

#


δag ⊥
δb(x1 )g(x1 )
p
EP,{2,3}
Π √ |Vj (x1 ) dx1
ĝ
ĝ(x1 )




Z  
δag ⊥
δbg ⊥
= EP,{2,3}
Π √ |Vj (x1 )Π √ |Vj (x1 ) dx1
ĝ
ĝ
1
" 
" 
#!

 #! 21
2
δag ⊥ 2
δbg ⊥ 2
EP,{2,3} Π √ |Vj
≤ EP,{2,3} Π √ |Vj
ĝ
ĝ
2
2

1 
1
1 2
1 2
≤ C 2−2jβ + 2
,
2−2jα + 2
n
n

(A.5)

where the last line follows for some constant C (depending on M, BU , BL , γmax ) by Theorem 2.3,
definition of (5.5), and noting that kΠ (h|Vj ) k∞ ≤ C(BU ) if khk∞ ≤ BU . Therefore, if n ≤ 2jd ≤ n2
d
along with α+β
2 < 4 , one has combining A.3, A.4, and A.5, that for a constant C (depending on
min
M, BU , BL , γmin , γmax ) and γmin (ǫ): = γ1+ǫ


|EP φ̂n,j − φ(P ) |
"
1 
1 #
− α − β − γ

2α+d
2β+d 2γ+d
2
2
n
1
1
≤C
+ 2−2jβ + 2
2−2jα + 2
log n
n
n
#
"
− α − β − γ
2α+d
2β+d 2γ+d
α+β
3
n
+ 2−2jd 2d + 3n− 2
≤C
log n


γ
(ǫ)
γ
(ǫ)
β
γ
α
β
γ
α
− 2α+d
− 2β+d
− 2γ min(ǫ)+d 2γ min+d(ǫ) − 2γ+d
+ 2β+d
+ 2γ+d
−2jd α+β
2α+d
2d
min
min
≤ 4C n
+2
n
log n


γ
(ǫ)
γ−γmin (ǫ)
α+β
− α − β − min
≤ 4C n 2α+d 2β+d 2γmin (ǫ)+d n− 2γ+d log n + 2−2jd 2d


γ
(ǫ)
ǫγ
β
α
− 2α+d
− 2β+d
− 2γ min(ǫ)+d − (1+ǫ)(2min
−2jd α+β
max
+d)
2d
min
≤ 4C n
log n + 2
n
γmin (ǫ)
β
α
Now, letting θ = (α, β, γ), f1 (θ) = α+β
2 and f2 (θ) = − 2α+d − 2β+d − 2γmin (ǫ)+d we have the bias
property corresponding to Theorem 2.1 holds with the given choice of f1 and f2 and a constant C
2α+2β
depending on M, BU , BL , γmax for {P ∈ Pθ : f1 (θ) = α+β
2 , f2 (θ) > 2α+2β+d }. To proof of the validity
of the variance property corresponding to Theorem 2.1 is easy to derive by standard Hoeffding
decomposition of φ̂n,j followed by applications of moment bounds in Lemmas B.2 and B.5. For
calculations of similar flavor, refer to proof of Theorem 1.3 in Mukherjee and Sen (2016). Note
d
that this is the step where we have used the fact that α+β
2 ≤ 4 , since otherwise the linear term
1
dominates resulting in O( n ) the variance.

sup
P ∈Pθ :

f1 (θ)=τ,f2 (θ)>

4τ
4τ +d

√
 8τ /d

2
log n 1+4τ /d
.
EP φ̂n,j (k∗ (l̂)) − φ(P ) ≤ 8C
n

Noting that for θ ∈ Θ, since γmin > 2(1 + ǫ) max{α, β}, one has automatically, f2 (θ) >
completes the proof of the upper bound.

2α+2β
2α+2β+d ,

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

31

(ii) Proof of Lower Bound
To prove a lower bound matching the upper bound above, note that φ(P ) = EP (covP (Y, A|X)) =
√
EP (AY ) − EP (a(X)b(X)). Indeed, EP (AY ) can be estimated at a n-rate by sample average of Ai Yi . Therefore, it suffices to prove a lower for adaptive estimation of EP (a(X)b(X)).
Let c(X) = EP (Y |A = 1, X) − EP (Y |A = 0, X), which implies owing to the binary nature of
A that EP (Y |A, X) = c(X) (A − a(X)) + b(X). For the purpose of lower bound it is convenient
to parametrize the data generating mechanism by (a, b, c, g), which implies that φ(P ) =
R
a(x)b(x)g(x)dx. With this parametrization, we show that the same lower bound holds in a smaller
class of problems where g ≡ 1 on [0, 1]d . Specifically consider


P = (a, b, c, g):


d
.
Θsub =
<
,
a ∈ H(α, M ), b ∈ H(β, M ), α+β
2
4


g ≡ 1, (a(x), b(x)) ∈ [BL , BU ]2 ∀x ∈ [0, 1]d
The likelihood of O ∼ P for P ∈ Θsub can then be written as

a(X)A (1 − a(X))1−A
× (c(X)(1 − A(X)) + b(X))Y A (1 − c(X)(1 − a(X)) − b(X))(1−Y )A
× (−c(X)a(X) + b(X))Y (1−A) (1 + c(X)a(X) − b(X))(1−Y )(1−A) .

(A.6)

Let for some (α, β, γ) tuple in the original problem Θ, one has
 4α+4β
√

2
log n d+2α+2β
.
sup EP φ̂ − φ(P ) ≤ C
n
P ∈P(α,β,γ)
R
d

let H: [0, 1]d → R be a C ∞ function supported on 0, 21 such that H(x)dx = 0 and
R Now,
H 2 (x)dx = 1 and let for k ∈ N (to be decided later) Ω1 , . . . , Ωk be the translates of the cube
d
1 
k− d 0, 12 that are disjoint and contained in [0, 1]d . Let x1 , . . . , xk denote the bottom left corners
of these cubes.
Assume first that α < β. We set for λ = (λ1 , . . . , λk ) ∈ {−1, +1}k and α ≤ β ′ < β,
aλ (x) =

k


1
1  1  αd X
λj H (x − xj )k d ,
+
2
k
j=1

k
β′


1
1 1 d X
λj H (x − xj )k d ,
bλ (x) = +
2
k
j=1

cλ (x) =

1
2

− bλ (x)
.
1 − aλ (x)

A properly chosen H guarantees aλ ∈ H(α, M ) and bλ ∈ H(β ′ , M ) for all λ. Let




1
n
k
Θ0 = P : P = aλ , , 0, 1 , λ ∈ {−1, +1} ,
2
and
o
n
Θ1 = P n : P = (aλ , bλ , cλ , 1), λ ∈ {−1, +1}k .

32

Finally let Θtest = Θ0 ∪ Θ1 . Let π0 and π1 be uniform priors on Θ0 and Θ1 respectively. It is easy to
 α+β ′
check that by our choice of H, φ(P ) = 41 on Θ0 and φ(P ) = 14 + k1 d for P ∈ Θ1 . Therefore, using
 α+β ′
notation from Lemma B.1, µ1 = 14 , µ2 = 41 + k1 d , and σ1 = σ2 = 0. Since Θ0 ⊆ P (α, β, γ), we
√
 4α+4β
log n d+2α+2β
must have that worst case error of estimation over Θ0 is bounded by C
. Therefore,
n
√
 2α+2β
log n d+2α+2β
. This implies by Lemma B.1,
the π0 average bias over Θ0 is also bounded by C
n
that the π1 average bias over Θ1 (and hence the worst case bias over Θ1 ) is bounded below by
√
√
  α+β ′
 2α+2β
 2α+2β
d
1
log n d+2α+2β
log n d+2α+2β
−C
η,
(A.7)
−C
k
n
n
R
R
where η is the chi-square divergence between the probability measures P n dπ0 (P n ) and P n dπ1 (P n ).
We now bound η using Theorem 2.2.
To put ourselves in the notation of Theorem 2.2, let for λ ∈ {−1, +1}k , Pλ and Qλ be the
probability measures identified from Θ0 and Θ1 respectively.
Therefore, with χj = {0, 1}×{0, 1}×Ωj , we indeed have for all j = 1, . . . , k, Pλ (χj ) = Qλ (χj ) = pj
where there exists a constant c such that pj = kc .

R
R
Letting π be the uniform prior over {−1, +1}k it is immediate that η = χ2
Pλ d(π(λ)), Qλ d(π(λ)) .
It now follows by calculations similar to proof of Theorem 4.1 in Robins et al. (2009), that for a
constant C ′ > 0

χ

2

Z

Now choosing k =

Pλ d(π(λ)),


√ n
c∗ log n

χ



2

Z





2
′
′
− 4β
−4 α+β
′n
d
2d
k
+k
− 1.
Qλ d(π(λ)) ≤ exp C
k

2d
d+2α+2β ′

Z

, we have

Pλ d(π(λ)),

Z


′
Qλ d(π(λ)) ≤ n2C c∗ − 1.
′

2α+2β
2α+2β
Therefore choosing c∗ such that 2C ′ c∗ + 2α+2β
′ +d < 2α+2β+d , we have the desired result by (A.7).
The proof for α > β is similar after changing various quantities to:

aλ (x) =

′
k


1
1  1  αd X
λj H (x − xj )k d ,
+
2
k

j=1

β ≤ α′ < α,

k
β


1
1 1d X
λj H (x − xj )k d ,
bλ (x) = +
2
k
j=1

cλ (X) =

( 12 − aλ (X))bλ (X)
,
aλ (X)(1 − aλ (X))





1
k
n
, bλ , 0, 1 : λ ∈ {−1, +1} ,
Θ0 = P : P =
2

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

33

and
o
n
Θ1 = P n : P = (aλ , bλ , cλ , 1): λ ∈ {−1, +1}k .

For the case of α = β, choose α′ < β and therefore, α′ < β and thereafter work with
aλ (x) =

′
k


1
1  1  αd X
+
λj H (x − xj )k d ,
2
k

j=1

bλ (x) =

k
β


1
1 1d X
λj H (x − xj )k d ,
+
2
k
j=1

cλ (x) =

Θ0 =

1
2

− bλ (x)
.
1 − aλ (x)





1
P n : P = aλ , , 0, 1 : λ ∈ {−1, +1}k ,
2

and
o
n
Θ1 = P n : P = (aλ , bλ , cλ , 1): λ ∈ {−1, +1}k .

This completes the proof of the lower bound.
Proof of Theorem 3.2.
Proof. (i) Proof of Upper Bound

The general scheme of proof is same as that of Theorem 3.2 and involves identifying a nonadaptive minimax estimator of φ(P ) under the knowledge of P ∈ P(α,β,γ) , demonstrating suitable
bias and variance properties of this sequence of estimators, and thereafter invoking Theorem 2.1
to conclude. This routine can be carried out as follows. Without loss of generality assume that we
have 3n samples {Yi Ai , Ai , Xi }ni=1 . Divide the samples in to 3 equal parts (with the lth part being
indexed by {(l − 1)n + 1, . . . , ln} for l ∈ {1, 2, 3}), estimate f by fˆ adaptively from the third part (as
in Theorem 2.3), and estimate E (A|x) and b by E\
(A|x) and b̂(x): = E (Y \
|A = 1, x) respectively,
adaptively from the second part (as in Theorem 2.3). Let EP,S denote the expectation while samples
with indices in S held fixed, for S ⊂
{1, 2, 3}. Note that g(X) = f (X|A = 1)P (A = 1). Therefore,
1 P3n
also estimate P (A = 1) by π̂: = n 2n+1 Ai i.e. the sample average of A’s from the third part of
the sample and fˆ1 is estimated as an estimator of f (X|A = 1) from the third part of our sample
using density estimation technique among observations with A = 1. Finally, our estimate of a
1
and ĝ = fˆ1 π̂ respectively. In the following, we will freely use Theorem
and g are â(x) = \
E(A|x)

2.3, for desired properties of â, b̂, and ĝ. In particular, following the proof of Theorem 2.3, we can
actually assume that our choice of ĝ also satisfies the necessary conditions of boundedness away
from 0 and ∞, as well as membership in H(γ, C) with high probability for a large enough C > 0.
A first order influence function for φ(P ) at P
P is given by Aa(X)(Y − b(X) + b(X) − φ(P ) and a
1
resulting first order
estimator for φ(P ) is n ni=1 Ai a(Xi )(Yi − b̂(Xi )) + b(Xi ). This estimator has
R
d
a bias −EP,{2,3}
(b(x) − b̂(x))(a(x) − â(x)) g(x)dx. Indeed for α+β
2 < 2 , this bias turns out to

34
−

4α+4β

be suboptimal compared to the minimax rate of convergence of n 2α+2β+d in mean squared loss.
Similar to proof of Theorem 3.1 we use a second order bias corrected estimator as follows.
Once again we work with the linear subspace Vj (defined in 5) where the choice of j is guided
by the balance between the bias and variance properties of the resulting estimator. In particular,
a choice of 2j is guided by the knowledge of the parameter space P(α,β,γ) . For any j such that
n ≤ 2jd ≤ n2 , our bias corrected second order estimator of φ(P ) is given by
n

φ̂n,j =

1X
Ai â(Xi )(Yi − b̂(Xi )) + b̂(Xi )
n
i=1

1
+
n(n − 1)

X

S

1≤i1 6=i2 ≤n

(Ai2 â(Xi2 ) − 1)
Ai1 (Yi1 − b̂(Xi1 )))
p
p
KVj (Xi1 , Xi2 )
ĝ(Xi1 )
ĝ(Xi2 )

!

Note that division by ĝ is permitted by the properties guaranteed by Theorem 2.3. Indeed this
sequence of estimators is in the form of those considered by Theorem 2.1 with
L1 (O) = Aâ(X)(Y − b̂(X)) + b̂(X),
L2l (O) = −

A(Y − b̂(X)))
p
,
ĝ(X)

L2r (O) =

(Aâ(X) − 1)
p
,
ĝ(X)

where by Theorem 2.3 max{|L1 (O)|, |L2l (O)|, |L2r (O)|} ≤ C(BL , BU ). Therefore it remains to
show that these sequence φ̂n,j satisfies the bias and variance property (A) and (B) necessary for
application of Theorem 2.1. Using the conditional independence of Y and A given X, one has y
calculations exactly parallel to that in proof of Theorem 3.1, that for a constant C (depending on
M, BU , BL , γmin , γmax ),


|EP φ̂n,j − φ(P ) |


γ
(ǫ)
ǫγ
β
α
α+β
− 2β+d
− 2γ min(ǫ)+d − (1+ǫ)(2min
− 2α+d
−2jd
max +d) log n + 2
2d
min
n
,
≤C n
γmin (ǫ)
β
α
min
where γmin (ǫ): = γ1+ǫ
. Now, letting θ = (α, β, γ), f1 (θ) = α+β
2 and f2 (θ) = − 2α+d − 2β+d − 2γmin (ǫ)+d
we have the bias property corresponding to Theorem 2.1 holds with the given choice of f1 and f2
2α+2β
and a constant C depending on M, BU , BL , γmax for {P ∈ Pθ : f1 (θ) = α+β
2 , f2 (θ) > 2α+2β+d }. To
proof of the validity of the variance property corresponding to Theorem 2.1 is one again easy to
derive by standard Hoeffding decomposition of φ̂n,j followed by applications of moment bounds in
Lemmas B.2 and B.5.

sup
P ∈Pθ :

f1 (θ)=τ,f2 (θ)>

4τ
4τ +d

√
 8τ /d

2
log n 1+4τ /d
.
EP φ̂n,j (k∗ (l̂)) − φ(P ) ≤ 8C
n

Noting that for θ ∈ Θ, since γmin > 2(1 + ǫ) max{α, β}, one has automatically, f2 (θ) >
completes the proof of the upper bound.

2α+2β
2α+2β+d ,

(ii) Proof of Lower Bound
First note that we can parametrize our distributions by the tuple of functions (a, b, g). We show

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

35

that the same lower bound holds in a smaller class of problems where g ≡ 1/2 on [0, 1]d . Specifically
consider


P = (a, b, g):


α+β
d
Θsub =
.
a ∈ H(α, M ), b ∈ H(β, M ), 2 < 4 ,


2
d
g ≡ 1/2, (a(x), b(x)) ∈ [BL , BU ] ∀x ∈ [0, 1]
The observed data likelihood of O ∼ P for P ∈ Θsub can then be written as
(a(X) − 1)1−A bY (X)(1 − b(X))1−Y
Let for some (α, β, γ) tuple in the original problem Θ, one has

A

.

(A.8)

 4α+4β
√

2
log n d+2α+2β
sup EP φ̂ − φ(P ) ≤ C
.
n
P ∈P(α,β,γ)


R
d → R be a C ∞ function supported on 0, 1 d such that
H(x)dx = 0 and
Now,
let
H:
[0,
1]
2
R 2
H (x)dx = 1 and let for k ∈ N (to be decided later) Ω1 , . . . , Ωk be the translates of the cube
d
1 
k− d 0, 12 that are disjoint and contained in [0, 1]d . Let x1 , . . . , xk denote the bottom left corners
of these cubes.
Assume first that α < β. We set for λ = (λ1 , . . . , λk ) ∈ {−1, +1}k and α ≤ β ′ < β,
aλ (x) = 2 +

k
1α X
d

k

j=1



1
λj H (x − xj )k d ,

k
β′


1
1 1 d X
bλ (x) = +
λj H (x − xj )k d .
2
k
j=1

A properly chosen H guarantees aλ ∈ H(α, M ) and bλ ∈ H(β ′ , M ) for all λ. Let
o
n
Θ0 = P n : P = (aλ , 1/2, 1/2) : λ ∈ {−1, +1}k ,

and

o
n
Θ1 = P n : P = (aλ , bλ , 1/2): λ ∈ {−1, +1}k .

Finally let Θtest = Θ0 ∪ Θ1 . Let π0 and π1 be uniform priors on Θ0 and Θ1 respectively. It is
 α+β ′
1
1 1
1
easy to check that by our choice of H, φ(P ) = 2 on Θ0 and φ(P ) = 2 + 2 k d for P ∈ Θ1 .
 α+β ′
Therefore, using notation from Lemma B.1, µ1 = 21 , µ2 = 12 + 21 k1 d , and σ1 = σ2 = 0.
Since Θ0 ⊆ P (α, β, γ), we must have that worst case error of estimation over Θ0 is bounded by
 4α+4β
 2α+2β
√
√
log n d+2α+2β
log n d+2α+2β
C
.
Therefore,
the
π
average
bias
over
Θ
is
also
bounded
by
C
.
0
0
n
n
This implies by Lemma B.1, that the π1 average bias over Θ1 (and hence the worst case bias over
Θ1 ) is bounded below by a constant multiple of
  α+β ′  √
 2α+2β
√
 2α+2β
d
log n d+2α+2β
log n d+2α+2β
1
−
−
η,
k
n
n

(A.9)

36

where
chi-square
between the probability measures
R n η is the
R n divergence
n
n
P dπ0 (P ) and P dπ1 (P ). We now bound η using Theorem 2.2.
To put ourselves in the notation of Theorem 2.2, let for λ ∈ {−1, +1}k , Pλ and Qλ be the
probability measures identified from Θ0 and Θ1 respectively.
Therefore, with χj = {0, 1}×{0, 1}×Ωj , we indeed have for all j = 1, . . . , k, Pλ (χj ) = Qλ (χj ) = pj
where there exists a constant c such that pj = kc .

R
R
Letting π be the uniform prior over {−1, +1}k it is immediate that η = χ2
Pλ d(π(λ)), Qλ d(π(λ)) .
It now follows by calculations similar to proof of Theorem 4.1 in Robins et al. (2009), that for a
constant C ′ > 0
χ

2

Z

Now choosing k =

Pλ d(π(λ)),


√ n
c∗ log n



Z





2
′
α+β ′
− 4β
−4
′n
2d
k d +k
− 1.
Qλ d(π(λ)) ≤ exp C
k

2d
d+2α+2β ′

, we have
Z

Z
′
χ2
Pλ d(π(λ)), Qλ d(π(λ)) ≤ n2C c∗ − 1.
′

2α+2β
2α+2β
Therefore choosing c∗ such that 2C ′ c∗ + 2α+2β
′ +d < 2α+2β+d , we have the desired result by (A.7).
The proof for α > β is similar after changing various quantities to:

aλ (x) = 2 +

k
 1  α′ X
d

k

bλ (x) =

j=1



1
λj H (x − xj )k d ,

β ≤ α′ < α,

k
β


1
1 1d X
λj H (x − xj )k d .
+
2
k
j=1

and

o
n
Θ0 = P n : P = (2, bλ , 1/2) : λ ∈ {−1, +1}k ,
o
n
Θ1 = P n : P = (aλ , bλ , 1/2): λ ∈ {−1, +1}k .

For the case of α = β, choose α′ < β and therefore, α′ < β and thereafter work with
aλ (x) = 2 +

bλ (x) =

k
 1  α′ X
d

k

j=1



1
λj H (x − xj )k d ,

k
β


1
1 1d X
λj H (x − xj )k d
+
2
k
j=1

and

o
n
Θ0 = P n : P = (aλ , 1/2, 1/2) : λ ∈ {−1, +1}k ,
o
n
Θ1 = P n : P = (aλ , bλ , 1/2): λ ∈ {−1, +1}k .

This completes the proof of the lower bound.

37

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

Proof of Theorem 3.3.
Proof. (i) Proof of Upper Bound
Without loss of generality assume that we have 3n samples {Yi , Ai , Xi }ni=1 . Divide the samples in
to 3 equal parts (with the lth part being indexed by {(l − 1)n + 1, . . . , ln} for l ∈ {1, 2, 3}), estimate
g by ĝ adaptively from the third part (as in Theorem 2.3), and estimate b by b̂, adaptively from
the second part (as in Theorem 2.3). Let EP,S denote the expectation while samples with indices
in S held fixed, for S ⊂ {1, 2, 3}. For any j such that n ≤ 2jd ≤ n2 , consider
n

φ̂n,j

1X
(2Yi − b̂(Xi ))b̂(Xi )
=
n
i=1

+

1
n(n − 1)

X

(Yi1 − b̂(Xi1 )))
(Yi2 − b̂(Xi2 ))
p
KVj (Xi1 , Xi2 ) p
ĝ(Xi1 )
ĝ(Xi2 )
1≤i1 6=i2 ≤n

Indeed this sequence of estimators is in the form of those considered by Theorem 2.1 with
L1 (O) = (2Y − b̂(X))b̂(X),
L2l (O) = −

(Y − b̂(X)))
p
,
ĝ(X)

L2r (O) =

(Y − b̂(X)))
p
,
ĝ(X)

where by Theorem 2.3 max{|L1 (O)|, |L2l (O)|, |L2r (O)|} ≤ C(BL , BU ). Therefore it remains to
show that these sequence φ̂n,j satisfies the bias and variance property (A) and (B) necessary for
application of Theorem 2.1. We first verify the bias property. Utilizing the representation of the
first order bias as stated above, we have


|EP φ̂n,j − φ(P ) |

 
2
R
EP,{2,3}
(b(x) − b̂(x) g(x)dx

 
=
(Y2 −b̂(X2 ))
(Y1 −b̂(X1 )))
√
KVj (X1 , X2 ) √
−EP S
ĝ(X1 )

ĝ(X2 )

(A.10)

Now, by calculations similar to proof of Theorem 3.1, one can show that for a constant C (depending
on M, BU , BL , γmin , γmax ),


|EP φ̂n,j − φ(P ) |


γ
(ǫ)
ǫγ
2β
γmin
− 2γ min(ǫ)+d − (1+ǫ)(2min
− 2β+d
−2jd α+β
max
+d)
2d
min
n
, γmin (ǫ): =
≤C n
log n + 2
1+ǫ
2β
min (ǫ)
− 2γγmin
Now, letting θ = (β, γ), f1 (θ) = β and f2 (θ) = − 2β+d
(ǫ)+d , the rest of the proof follows
along the lines of the proof of Theorem 3.1.
(ii) Proof of Lower Bound
The proof of the lower bound is very similar to that of the lower bound proof in Theorem 3.1, after
identifying Y = A almost surely P, and hence is omitted.

38

APPENDIX B: TECHNICAL LEMMAS
B.1. Constrained Risk Inequality. A main tool for producing adaptive lower bound arguments is a general version of constrained risk inequality due to Cai and Low (2011), obtained
as an extension of Brown and Low (1996). For the sake of completeness, begin with a summary
of these results. Suppose Z has distribution Pθ where θ belongs to some parameter space Θ. Let
Q̂ = Q̂(Z) be an estimator of a function Q(θ) based on Z with bias B(θ): = Eθ (Q̂) − Q(θ). Now
suppose that Θ0 and Θ1 form
R a disjoint partition
R of Θ with priors π0 and π1 supported on them
respectively. Also, let µi = Q(θ)dπi and σi2 = (Q(θ) − µi )2 dπi , i = 0, 1 be the mean and variance
of Q(θ) under the two priors π0 and π1 . Letting γi be the marginal density with respect to some
common dominating measure of Z under πi , i = 0, 1, let us denote by Eγ0 (g(Z)) the expectation
of g(Z) with respect to the marginal density of Z under prior π0 and distinguish it from Eθ (g(Z)),
which is the expectation under Pθ . Lastly, denote the chi-square divergence between γ0 and γ1 by

2  12

γ1
χ = Eγ0 γ0 − 1
. Then we have the following result.
Lemma B.1 (Cai and Low (2011)).
Z

B(θ)dπ1 (θ) −

If
Z

R


2
Eθ Q̂(Z) − Q(θ) dπ0 (θ) ≤ ǫ2 , then

B(θ)dπ0 (θ) ≥ |µ1 − µ0 | − (ǫ + σ0 )χ.

Since the maximum risk is always at least as large as the average risk, this immediately yields a
lower bound on the minimax risk.
B.2. Tail and Moment Bounds. The U-statistics appearing in this paper are mostly based
on projection kernels sandwiched between arbitrary bounded functions. This necessitates generalizing the U-statistics bounds obtained in Bull and Nickl (2013) as in Mukherjee and Sen (2016)
.
Lemma B.2. O1 , . . . , On ∼ P are iid random vectors of observations such that Xi ∈ [0, 1]d is
a sub-vector of Oi for each i. There exists constant C: = C(B, BU , J0 ) > 0 such that the following
hold
(i)
P

(B.1)




X
1
R (Oi1 , Oi2 ) − E (R (O1 , O2 )) ≥ t
n(n − 1)
i1 6=i2

2

−Cnt2

≤e

− Ct2

+e

a

1

− Ct
a

+e

2

√

t
√
−C
a

+e

3

,

(ii)


E |

1
n(n − 1)

X

i1 6=i2



2q 

R (Oi1 , Oi2 ) − E (R (O1 , O2 )) |

≤



2jd
C 2
n

q

,


q

2jd
1
2jd
where a1 =
a2 =
+ 1 , a3 = n−1
,
n + n

R(O1 , O2 ) = S L2l (O1 )KVj (X1 , X2 ) L2r (O2 ) with max{|L2l (O)|, |L2r (O)|} ≤ B , almost surely
O, and Xi ∈ [0, 1]d are iid with density g such that g(x) ≤ BU for all x ∈ [0, 1]d .
jd
1
2
n−1 2 ,

1
n−1

q

2jd
n

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

39

Proof. The proof of part (i) can be found in Mukherjee and Sen (2016). However, for the
sake of completeness we provide the proof here again. We do the proof for the special case where
L2l = L2r = L. However, the details of the argument shows that the proof continues to hold to
symmetrized U-statistics as defined here.
The proof hinges on the following tail bound for second order degenerate U-statistics (Giné and Nickl,
2015) is due to Giné, Latala and Zinn (2000) with constants by Houdré and Reynaud-Bouret (2003)
and is crucial for our calculations.
Lemma B.3. Let Un be a degenerate U-statistic of order 2 with kernel R based on an i.i.d.
sample W1 , . . . , Wn . Then there exists a constant C independent of n, such that
X
√
P [|
R(W1 , W2 )| ≥ C(Λ1 u + Λ2 u + Λ3 u3/2 + Λ4 u2 )] ≤ 6 exp(−u),
i6=j

where, we have,
n(n − 1)
E[R2 (W1 , W2 )],
2
Λ2 = n sup{E[R(W1 , W2 )ζ(W1 )ξ(W2 )]: E[ζ 2 (W1 )] ≤ 1, E[ξ 2 (W1 )] ≤ 1},
Λ21 =

1

2
Λ3 = knE[R2 (W1 , ·)k∞
,

Λ4 = kRk∞ .

We use this lemma to establish Lemma B.2. By Hoeffding’s decomposition one has
X
1
R (Oi1 , Oi2 ) − E (R (O1 , O2 ))
n(n − 1)
=
+

2
n

n
X

i1 =1

i1 6=i2

h

EOi1 R (Oi1 , Oi2 ) − ER (Oi1 , Oi2 )

i

X  R (Oi , Oi ) − EO R (Oi , Oi ) 
1
1
2
1
2
i1
−EOi2 R (Oi1 , Oi2 ) + ER (Oi1 , Oi2 )
n(n − 1)

: = T1 + T2

i1 6=i2

P
B.2.1. Analysis of T1 . Noting that T1 = n2 ni1 =1 H(Oi1 ) where H(Oi1 ) = E (R (Oi1 , Oi2 |Oi1 ))−
ER (Oi1 , Oi2 ) we control T1 by standard Hoeffding’s Inequality. First note that,
|H(Oi1 )|
X X h

2 i
v
v
v
|
=|
L (Oi1 ) ψjk
(Xi1 ) E ψjk
(Xi2 ) L (Oi2 ) − E ψjk
(Xi2 ) L (Oi2 )
k∈Zj v∈{0,1}d

≤
+

X

X

k∈Zj v∈{0,1}d

X

X


v
v
|L (Oi1 ) ψjk
(Xi1 ) E ψjk
(Xi2 ) L (Oi2 ) |
v
E ψjk
(Xi2 ) L (Oi2 )

k∈Zj v∈{0,1}d

2

First, by standard compactness argument for the wavelet bases,

v
(X) L(O) | ≤
|E ψjk

Z

d

 jd Y
vl j
(2 xl − kl ) ||g(x)|dx
ψ00
|E (L(O)|X = x) 2 2
l=1

40
jd

≤ C(B, BU , J0 )2− 2 .

(B.2)

Therefore,
X

X

k∈Zj v∈{0,1}d

2
v
E ψjk
(Xi2 ) L (Oi2 )
≤ C(B, BU , J0 )

(B.3)

Also, using the fact that for each fixed x ∈ [0, 1]d , the number indices k ∈ Zj such that x belongs to
v is bounded by a constant depending only on ψ 0 and ψ 1 . Therefore
support of at least one of ψjk
00
00
combining (B.2) and (B.3),
X X

v
v
|L (Oi1 ) ψjk
(Xi1 ) E ψjk
(Xi2 ) L (Oi2 ) |
k∈Zj v∈{0,1}d

jd

jd

≤ C(B, BU , J0 )2− 2 2 2 = C(B, BU , J0 ).

(B.4)

Therefore, by (B.4) and Hoeffding’s Inequality,
2

P (|T1 | ≥ t) ≤ 2e−C(B,BU ,J0 )nt .

(B.5)

B.2.2. Analysis of T2 . Since T2 is a degenerate U-statistics, it’s analysis is based on Lemma
B.3. In particular,
T2 =

X
1
R∗ (Oi1 , Oi2 )
n(n − 1)
i1 6=i2

where
R∗ (Oi1 , Oi2 )

 
 

v (X ) − E ψ v (X ) E (L(O )|X )

X 
L(Oi1 )ψjk
i
i
i
i1
1
1
1

 jk

=
 × L(Oi )ψ v (Xi ) − E ψ v (Xi ) E (L(Oi )|Xi )

2
2
2
2
2
jk
jk
k∈Zj v∈{0,1}d
X

Letting Λi , i = 1, . . . , 4 being the relevant quantities as in Lemma B.3, we have the following
lemma.
Lemma B.4.

There exists a constant C = C(B, BU , J0 ) such that
Λ21 ≤ C

jd
n(n − 1) jd
2 , Λ2 ≤ Cn, Λ23 ≤ Cn2jd , Λ4 ≤ C2 2 .
2

Proof. First we control Λ1 . To this end, note that by simple calculations, using bounds on L, g,
v ’s we have,
and orthonormality of ψjk
Λ21 =



n(n − 1)  ∗
E {R (O1 , O2 )}2 ≤ 3n(n − 1)E R2 (O1 , O2 )
2



= 3n(n − 1)E L2 (O1 ) KV2j (X1 , X2 ) L2 (O2 )
Z Z hX X
i2
4
v
v
≤ 3n(n − 1)B
ψjk
(x1 ) ψjk
(x2 ) g(x1 )g(x2 )dx1 dx2
k∈Zj v∈{0,1}d

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

≤ 3n(n − 1)B 4 BU2
= 3n(n − 1)B 4 BU2

Z Z hX

X

v
v
(x2 )
(x1 ) ψjk
ψjk

k∈Zj v∈{0,1}d

X

X Z

k∈Zj v∈{0,1}d

≤ C(B, BU , J0 )n(n − 1)2jd .

2
v
ψjk
(x1 ) dx2

Z

i2

41

dx1 dx2

2
v
ψjk
(x2 ) dx2

Next we control



Λ2 = n sup E (R∗ (O1 , O2 ) ζ (O1 ) ξ (O2 )) : E ζ 2 (O1 ) ≤ 1, E ξ 2 (O2 ) ≤ 1 .

To this end, we first control


|E L(O1 )KVj (X1 , X2 ) L(O2 )ζ(O1 )ξ(O2 ) |
Z Z
=|
E(L(O1 )ζ(O1 )|X1 = x1 )KVj (x1 , x2 ) E(L(O2 )ξ(O2 )|X2 = x2 )g(x2 )g(x2 )dx1 dx2 |
Z
= | E(L(O)ζ(O)|X = x)Π (E(L(O)ξ(O)|X = x)g(x)|Vj ) g(x)dx|
≤

Z

 1 Z
1
2
2
2
E (L(O)ζ(O)|X = x)g (x)dx
Π (E(L(O)ξ(O)|X = x)g(x)|Vj ) dx
2

2

 1 Z
1
2
2
2
2
2
E(L (O)ζ (O)|X = x)g (x)dx
E(L (O)ξ (O)|X = x)g (x)dx
≤
p
≤ B 2 BU E(ζ 2 (O1 ))E(ξ 2 (O2 )) ≤ B 2 BU
Z

2

2

2

Above we have used Cauchy-Schwartz Inequality, Jensen’s Inequality, and the fact that projections
contract norm. Also,


|E E L(O1 )KVj (X1 , X2 ) L(O2 )|O1 ζ(O1 )ξ(O2 ) |
= |E [L(O1 )Π (E (L(O1 )g(X1 )|X1 ) |Vj ) ζ(O1 )ξ(O2 )] |

= |E [L(O1 )Π (E (L(O1 )g(X1 )|X1 ) |Vj ) ζ(O1 )] ||E(ξ(O2 ))|
Z
≤ | Π(E(L(O)ζ(O)|X = x)g(x)|Vj )Π(E(L(O)|X = x)g(x)|Vj )dx| ≤ B 2 BU ,
where the last step once again uses contraction property of projection, Jensen’s Inequality, and
bounds on L and g. Finally, by Cauchy-Schwartz Inequality and (B.3),



E E L(O1 )KVj (X1 , X2 ) L(O2 ) ζ(O1 )ξ(O2 )
X X

v
≤
E2 L(O)ψjk
(X) ≤ C(B, BU , J0 ).
k∈Zj v∈{0,1}d

i 1
h
2
This completes the proof of Λ2 ≤ C(B, BU , J0 )n. Turning to Λ3 = nkE (R∗ (O1 , ·))2 k∞
we have
that
(R∗ (O1 , o2 ))2
≤ 2 [R(O1 , o2 ) − E(R(O1 , O2 )|O1 )]2 + 2 [E(R(O1 , O2 )|O2 = o2 ) − E (R(O1 , O2 ))]2

Now,
E [R(O1 , o2 ) − E(R(O1 , O2 )|O1 )]2

42



≤ 2E L2 (O1 )KV2j (X1 , x2 ) L2 (o2 )
X X
 2
v
v
(X2 )L(O2 )
+ 2E
(X1 )E ψjk
L(O1 )ψjk
k∈Zj v∈{0,1}d

≤ 2B 4 BU2

X

X

k∈Zj v∈{0,1}d

2
v
(x2 ) + 2E(H 2 (O2 )) ≤ C(B, BU , J0 )2jd .
ψjk

where the last inequality follows from arguments along the line of (B.4). Also, using inequalities
(B.3) and (B.4)
[E(R(O1 , O2 )|O2 = o2 ) − E (R(O1 , O2 ))]2
hX X
 i2


v
v
v
(x2 )L(o2 )
(X1 ) − ψjk
(X1 ) E L(O1 )ψjk
=
E L(O1 )ψjk
k∈Zj v∈{0,1}d

≤ C(B, BU , J0 ).

This completes the proof of controlling Λ3 . Finally, using compactness of the wavelet basis,
X X
v
v
(x2 )| ≤ C(B, BU , J0 )2jd
(x1 )||ψjk
|ψjk
kR(·, ·)k∞ ≤ B 2 sup
x1 ,x2

k∈Zj v∈{0,1}d

Combining this with arguments similar to those leading to (B.4), we have Λ4 ≤ C(B, BU , J0 )2jd .
Therefore, using Lemma B.3 and Lemma B.4 we have
r

C(B, BU , J0 ) √ jd
2jd 3 2jd 2 
P |T2 | ≥
2 t+t+
≤ 6e−t .
t2 +
t
n−1
n
n
3

Finally using 2t 2 ≤ t + t2 we have,
h
i
√
Pf |T2 | > a1 t + a2 t + a3 t2 ≤ 6e−t
(B.6)

q
jd
2jd
U ,J0 )
U ,J0 )
2 2 , a2 = C(B,B
where a1 = C(B,B
n−1
n−1
n +1 ,
q

p
2jd
2jd
U ,J0 )
a3 = C(B,B
h(t) + a2 h(t) + a3 h2 (t) ≤ t, then one
+
.
Now
if
h(t)
is
such
that
a
1
n−1
n
n

has by (B.6),

i
h
p
P [|T2 | ≥ t] ≤ P |T2 | ≥ a1 h(t) + a2 h(t) + a3 h2 (t) ≤ 6e−6h(t) .
√
Indeed, there exists such an h(t) such that h(t) = b1 t2 ∧ b2 t ∧ b3 t where b1 =
C(B,BU ,J0 )
,
a2

and b3 =

C(B,B
√ U ,J0 ) .
a3

C(B,BU ,J0 )
,
a21

b2 =

Therefore, there exists C = C(B, BU , J0 ) such that
2

− Ct2

P [|T2 | ≥ t] ≤ e

a

1

− Ct
a

+e

2

√

t
√
−C
a

+e

3

.

(B.7)

B.2.3. Combining Bounds on T1 and T2 . Applying union bound along with B.5 and B.7 completes the proof of Lemma B.2 part (i).
For the proof of part (ii) note that with the notation of the proof of part (i) we have by Hoeffding
decomposition


X
1
R (Oi1 , Oi2 ) − E (R (O1 , O2 )) |2q  ≤ 2(E|T1 |2q + E|T2 |2q )
E |
n(n − 1)
i1 6=i2

The proof will be completed by individual control of the two moments above.

ADAPTIVE ESTIMATION OF NONPARAMETRIC FUNCTIONALS

43

P
B.2.4. Analysis of E|T1 |2q . Recall that T1 = n2 ni1 =1 H(Oi1 ) where H(Oi1 ) = E (R (Oi1 , Oi2 |Oi1 ))−
ER (Oi1 , Oi2 ) and |H(O)| ≤ C(B, BU , J0 ) almost surely. Therefore by Rosenthal’s Inequality B.5
we have
)q #
( n
 2q "X
n
X
2
E|H(Oi )|2
E|H(Oi )|2q +
E|T1 |2q ≤
n
i=1
i=1

2q
2C(B, BU , J0 )
≤
(n + nq ) ≤ C(B, BU , J0 )q n−q .
n
B.2.5. Analysis of E|T2 |2q . Recall that
h
i
p
P [|T2 | ≥ t] ≤ P |T2 | ≥ a1 h(t) + a2 h(t) + a3 h2 (t) ≤ 6e−6h(t) .

√
where h(t) = b1 t2 ∧ b2 t ∧ b3 t with b1 =

C(B,BU ,J0 )
, b2
a21

=

C(B,BU ,J0 )
,
a2

and b3 =

C(B,BU ,J0 )
√
.
a3

Therefore

Ef (|T2 |2q )
Z ∞
x2q−1 Pf (|T2 | ≥ x)dx
= 2q
0
Z ∞
p
x2q−1 Pf (|T2 | ≥ a1 h(x) + a2 h(x) + a3 h2 (x))dx
≤ 2q
0
Z
∞
x2q−1 e−h(x) dx
≤ 12q
Z0 ∞
√
2
x2q−1 e−{b1 x ∧b2 x∧b3 x} dx
= 12q
0

Z
Z ∞
Z ∞
∞
√
2q−1 −b3 x
2q−1 −b2 x
2q−1 −b1 x2
dx
x
e
x
e
dx +
dx +
x
e
≤ 12q
0
0
0
! 
q
Γ(q) Γ(2q) 2Γ(4q)
2jd
= 12q
≤ C 2
+ 2q +
2bq1
n
b2
b4q
3
for a constant C = C(B, BU , J0 ), by our choices of b1 , b2 , b3 .
Since the estimators arising in this paper also have a linear term, we will need the following
standard Bernstein and Rosenthal type tail and moment bounds (Petrov, 1995).
Lemma B.5. If O1 , . . . , On ∼ P are iid random vectors such that |L(O)| ≤ B almost surely P,
then for q ≥ 2 one has for large enough constants C(B) and C(B, q)
n

P(|

2
1X
(L(Oi ) − E(L(Oi ))) | ≥ t) ≤ 2e−nt /C(B) ,
n

i=1

and
E(|

n
X
i=1

(L(Oi ) − E(L(Oi ))) |q )


#q/2 
" n
n
X
X


E |L(Oi ) − E(L(Oi ))|2
E (|L(Oi ) − E(L(Oi ))|q ) +
≤
i=1

i=1

q
2

≤ C(B, q)n .

44

We will also need the following concentration inequality for linear estimators based on wavelet
projection kernels, proof of which can be done along the lines of proofs of Theorem 5.1.5 and
Theorem 5.1.13 of Giné and Nickl (2015).
Lemma B.6. Consider i.i.d. observations
Oi = (Y, X)i , i = 1, . . . , n where Xi ∈ [0, 1]d with
P
marginal density g. Let m̂(x) = n1 ni=1 L(Oi )KVl (Xi , x), such that max{kgk∞ , kLk∞ } ≤ BU . If
2ld ld
1
0
n ≤ 1, there exists C, C1 , C2 > 0, depending on BU and scaling functions ψ0,0 , ψ0,0 respectively,
such that
r
2ld ld
E(km̂ − E(m̂)k∞ ) ≤ C
,
n
and for any x > 0


p
3
ld
ld
P nkm̂ − E(m̂)k∞ > nE(km̂ − E(m̂)k∞ ) + C1 n2 x + C2 2 x ≤ e−x .
2

