arXiv: 1606.00304v3

arXiv:1606.00304v3 [] 22 Jun 2017

EFFICIENT MULTIVARIATE ENTROPY ESTIMATION
VIA K-NEAREST NEIGHBOUR DISTANCES
By Thomas B. Berrett∗,§ , Richard J. Samworth†,§ and Ming
Yuan‡,¶
University of Cambridge§
University of Wisconsin–Madison¶
Many statistical procedures, including goodness-of-fit tests and
methods for independent component analysis, rely critically on the
estimation of the entropy of a distribution. In this paper, we seek
entropy estimators that are efficient and achieve the local asymptotic
minimax lower bound with respect to squared error loss. To this end,
we study weighted averages of the estimators originally proposed by
Kozachenko and Leonenko (1987), based on the k-nearest neighbour
distances of a sample of n independent and identically distributed
random vectors in Rd . A careful choice of weights enables us to obtain an efficient estimator in arbitrary dimensions, given sufficient
smoothness, while the original unweighted estimator is typically only
efficient when d ≤ 3. In addition to the new estimator proposed
and theoretical understanding provided, our results facilitate the construction of asymptotically valid confidence intervals for the entropy
of asymptotically minimal width.

1. Introduction. The concept of entropy plays a central role in information theory, and has found a wide array of uses in other disciplines, including statistics, probability and combinatorics. The (differential) entropy
of a random vector X with density function f is defined as
Z
f (x) log f (x) dx
H = H(X) = H(f ) := −E{log f (X)} = −
X

where X := {x : f (x) > 0}. It represents the average information content of
an observation, and is usually thought of as a measure of unpredictability.
∗

Research supported by a Ph.D. scholarship from the SIMS fund.
Research supported by an EPSRC Early Career Fellowship and a grant from the
Leverhulme Trust.
‡
Research supported by NSF FRG Grant DMS-1265202 and NIH Grant 1U54AI117924-01.
AMS 2000 subject classifications: 62G05, 62G20
Keywords and phrases: efficiency, entropy estimation, Kozachenko–Leonenko estimator,
weighted nearest neighbours
†

1
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

2

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

In statistical contexts, it is often the estimation of entropy that is of primary interest, for instance in goodness-of-fit tests of normality (Vasicek,
1976) or uniformity (Cressie, 1976), tests of independence (Goria et al.,
2005), independent component analysis (Miller and Fisher, 2003) and feature
selection in classification (Kwak and Choi, 2002). See, for example, Beirlant
et al. (1997) and Paninski (2003) for other applications and an overview of
nonparametric techniques, which include methods based on sample spacings
in the univariate case (e.g. El Haje Hussein and Golubev , 2009), histograms
(Hall and Morton, 1993) and kernel density estimates (Paninski and Yajima, 2008; Sricharan, Wei and Hero, 2013), among others. The estimator
of Kozachenko and Leonenko (1987) is particularly attractive as a starting
point, both because it generalises easily to multivariate cases, and because,
since it only relies on the evaluation of kth-nearest neighbour distances, it
is straightforward to compute.
To introduce this estimator, for n ≥ 2, let X1 , . . . , Xn be independent
random vectors with density f on Rd . Write k · k for the Euclidean norm
on Rd , and for i = 1, . . . , n, let X(1),i , . . . , X(n−1),i denote a permutation of
{X1 , . . . , Xn } \ {Xi } such that kX(1),i − Xi k ≤ . . . ≤ kX(n−1),i − Xi k. For
conciseness, we let
ρ(k),i := kX(k),i − Xi k
denote the distance between Xi and the kth nearest neighbour of Xi . The
Kozachenko–Leonenko estimator of the entropy H is given by
 ρd V (n − 1) 
n
1X
(k),i d
,
log
(1)
Ĥn = Ĥn (X1 , . . . , Xn ) :=
n
eΨ(k)
i=1
where Vd := π d/2 /Γ(1 + d/2) denotes the volume of the unit d-dimensional
Euclidean ball and where Ψ denotes the digamma function. In fact, this
is a generalisation of the estimator originally proposed by Kozachenko and
(1987), which was defined for k = 1. For integers k we have Ψ(k) =
Leonenko
Pk−1
−γ + j=1
1/j where γ := 0.577216 . . . is the Euler–Mascheroni constant,
Ψ(k)
so that e
/k → 1 as k → ∞. This estimator can
Pnbe regarded as an
−1
∗
attempt to mimic the ‘oracle’ estimator Hn := −n
i=1 log f (Xi ), based
on a k-nearest neighbour density estimate that relies on the approximation
k
≈ Vd ρd(k),1 f (X1 ).
n−1

It turns out that, when d ≤ 3 and other regularity conditions hold, the
estimator Ĥn in (1) has the same asymptotic behaviour as Hn∗ , in that

d
n1/2 (Ĥn − H) → N 0, Var log f (X1 ) .
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

3

We will see that in such settings, this estimator is asymptotically efficient,
in the sense of, e.g., van der Vaart (1998, p. 367). However, when d ≥
4, a non-trivial bias typically precludes its efficiency. Our main object of
interest, therefore, will be a generalisation of the estimator (1), formed as a
weighted average of Kozachenko–Leonenko estimators for different values of
k, where the weights are chosen to try to cancel the dominant bias
P terms.
More precisely, for a weight vector w = (w1 , . . . , wk )T ∈ Rk with kj=1 wj =
1, we consider the estimator
n

Ĥnw

k

1 XX
wj log ξ(j),i ,
:=
n
i=1 j=1

where ξ(j),i := e−Ψ(j) Vd (n − 1)ρd(j),i . Weighted estimators of this general type
have been considered recently (e.g. Sricharan, Wei and Hero, 2013; Moon et
al., 2016), though our construction of the weights and our analysis is new. In
particular, we show that under stronger smoothness assumptions, and with
a suitable choice of weights, the weighted Kozachenko–Leonenko estimator
is efficient in arbitrary dimensions.
There have been several previous studies of the (unweighted) Kozachenko–
Leonenko estimator, but results on the rate of convergence have until now
confined either to the case k = 1 or (very recently) the case where k is fixed
as n diverges. The original Kozachenko and Leonenko (1987) paper proved
consistency of the estimator under mild conditions in the case k = 1. Tsybakov and Van der Meulen (1996) proved that the mean squared error of a
truncated version of the estimator is O(n−1 ) when k = 1 and d = 1 under a
condition that is almost equivalent to an exponential tail; Biau and Devroye
(2015) showed that the bias vanishes asymptotically while the variance is
O(n−1 ) when k = 1 and f is compactly supported and bounded away from
zero on its support. Very recently, in independent work and under regularity
conditions, Delattre and Fournier (2017) derived the asymptotic normality
of the estimator when k = 1, confirming the suboptimal asymptotic variance in this case. Previous works on the general k case include Singh et al.
(2003), where heuristic arguments were presented to suggest the estimator
is consistent for general d and general fixed k and has variance O(n−1 ) for
d = 1 and general fixed k. Gao, Oh and Viswanath (2016) obtain a mean
squared error bound of O(n−1 ) up to polylogarithmic factors for fixed k
and d ≤ 2, though the only densities which the authors can show satisfy
their tail condition have bounded support. Singh and Póczos (2016) obtain
a similar bound (without the polylogarithmic factors, but explicitly assuming bounded support) for fixed k and d ≤ 4. Mnatsakanov et al. (2008) allow
k to diverge with n, and show that the estimator is consistent for general d.
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

4

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

Plug-in kernel methods are also popular for entropy estimation. Paninski
and Yajima (2008), for example, show that a smaller bandwidth than would
be required for a consistent density estimator can still yield a consistent
entropy estimator. A k-nearest neighbour density estimate can be regarded
as a kernel estimator with a bandwidth that depends both on the data
and on the point at which the estimate is required. Sricharan, Wei and
Hero (2013) obtain the parametric rate of convergence for a plug-in kernel
method, assuming bounded support and at least d derivatives in the interior
of the support.
Importantly, the class of densities considered in our results allows the
support of the density to be unbounded; for instance, it may be the whole
of Rd . Such settings present significant new challenges and lead to different behaviour compared with more commonly-studied situations where the
underlying density is compactly supported and bounded away from zero on
its support. To gain intuition, consider the following second-order Taylor
expansion of H(f ) around a density estimator fˆ:

Z
Z
2 (x)
f
1
dx − 1 .
f (x) log fˆ(x) dx −
H(f ) ≈ −
2 Rd fˆ(x)
Rd
When f is bounded away from zero on its support, one can estimate the
(smaller order) second term on the right-hand side, thereby obtaining efficient estimators of entropy in higher dimensions (Laurent, 1996); however,
when f is not bounded away from zero on its support such procedures are no
longer effective. To the best of our knowledge, therefore, this is the first time
that a nonparametric entropy estimator has been shown to be efficient in
multivariate settings for densities having unbounded support. (We remark
that when d = 1, the histogram estimator of Hall and Morton (1993) is
known to be efficient under fairly strong tail conditions.)
The outline of the rest of the paper is as follows. In Section 2, we give
our main results on the mean squared error and asymptotic normality of
weighted Kozachenko–Leonenko estimators, and discuss confidence interval
construction. These main results arise from asymptotic expansions for the
bias and variance, which are stated in Section 3. Here, we also give examples
to illustrate densities satisfying our conditions, discuss how they may be
weakened, and address the fixed k case. Corresponding lower bounds are
presented in Section 4. Proofs of main results are presented in Section 5
with auxiliary material and detailed bounds for various error terms deferred
to the Appendix, which appears as the supplementary material Berrett,
Samworth and Yuan (2017).
We conclude the introduction with some notation used throughout the paimsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

5

per. For x ∈ Rd and r > 0, let Bx (r) be the closed Euclidean ball of radius r
about x, and let Bx◦ (r) := Bx (r) \ {x} denote the corresponding punctured
ball. We write kAkop and |A| for the operator norm and determinant, respectively, of A ∈ Rd×d , and let kAk denote the vectorised Euclidean norm
of a vector, matrix or array. For a smooth function f : Rd → [0, ∞), we write
f˙(x), f¨(x) and f (m) (x) respectively for the gradient vector of f at x, Hessian
m f (x)
. We also
matrix of f at x and the array with (j1 , . . . , jm )th entry ∂x∂j ...∂x
jm
1
Pd ∂ 2 f
write ∆f (x) := j=1 ∂x2 (x) for its Laplacian, and kf k∞ := supx∈Rd f (x)
j

for its uniform norm.

2. Main results. We begin by introducing the class of densities over
which our results will hold. Let Fd denote the class of all density functions
with respect to Lebesgue measure on Rd . For f ∈ Fd and α > 0, let
Z
kxkα f (x) dx.
µα (f ) :=
Rd

Now let A denote the class of decreasing functions a : (0, ∞) → [1, ∞)
satisfying a(δ) = o(δ−ǫ ) as δ ց 0, for every ǫ > 0. If a ∈ A, β > 0
and f ∈ Fd is m := ⌈β⌉ − 1-times differentiable and x ∈ X , we define
ra (x) := {8d1/2 a(f (x))}−1/(β∧1) and
kf (t) (x)k
,
Mf,a,β (x) := max max
t=1,...,m
f (x)



kf (m) (y) − f (m) (x)k
sup
.
f (x)ky − xkβ−m
y∈Bx◦ (ra (x))

The quantity Mf,a,β (x) measures the smoothness of derivatives of f in
neighbourhoods of x, relative to f (x) itself. Note that these neighbourhoods of x are allowed to become smaller when f (x) is small. Finally, for
Θ := (0, ∞)4 × A, and θ = (α, β, ν, γ, a) ∈ Θ, let


Fd,θ := f ∈ Fd : µα (f ) ≤ ν, kf k∞ ≤ γ, sup Mf,a,β (x) ≤ a(δ) ∀δ > 0 .
x:f (x)≥δ

We note here that Lemma 12 in the online supplement can be used to derive a
nestedness property of the classes with respect to the smoothness parameter,
namely that if θ = (α, β, γ, ν, a) ∈ Θ, β ′ ∈ (0, β) and a′ (δ) = 15d⌈β⌉/2 a(δ),
then Fd,θ ⊆ Fd,θ′ , where θ ′ = (α, β ′ , γ, ν, a′ ) ∈ Θ. In Section 3.2 below, we
discuss the requirements of the class Fd,θ in greater detail, and give several
examples, including Gaussian and multivariate-t densities, which belong to
Fd,θ for suitable θ.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

6

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

We now introduce the class of weights w = (w1 , . . . , wk )T that we consider.
For k ∈ N, let
W (k) :=



w ∈ Rk :

k
X

wj

j=1

k
X

(2)

j=1

Γ(j + 2ℓ/d)
= 0 for ℓ = 1, . . . , ⌊d/4⌋
Γ(j)


wj = 1 and wj = 0 if j ∈
/ {⌊k/d⌋, ⌊2k/d⌋, . . . , k} .

Our main result below shows that for appropriately chosen weight vectors in
W (k) , the normalised risk of the weighted Kozachenko–Leonenko estimator
in a uniform sense to that of the oracle estimator Hn∗ :=
Ĥnw converges
Pn
−1
−n
i=1 log f (Xi ). Theorem 8 in Section 4 shows that this limiting risk
is optimal.
Theorem 1. Fix d ∈ N and θ = (α, β, ν, γ, a) ∈ Θ with α > d and
∗
∗
denote any two deterministic
and k1∗ = k1,n
with β > d/2. Let k0∗ = k0,n
∗
∗
sequences of positive integers with k0 ≤ k1 , with k0∗ / log5 n → ∞ and with
k1∗ = O(nτ1 ) and k1∗ = o(nτ2 ), where




α−d
4β ∗
d
d/4
2α
,
,
,1 −
, τ2 := min 1 −
τ1 < min
5α + 3d
2α
4β ∗ + 3d
1 + ⌊d/4⌋
2β
and β ∗ := β ∧ 1. There exists kd ∈ N, depending only on d, such that for
each k ≥ kd , we can find w = w(k) ∈ W (k) with supk≥kd kw(k) k < ∞. For
such w,

(3)
sup
sup nEf (Ĥnw − Hn∗ )2 → 0
k∈{k0∗ ,...,k1∗ } f ∈Fd,θ

as n → ∞. In particular,
sup

sup nEf {(Ĥnw − H(f ))2 } − V (f ) → 0,

k∈{k0∗ ,...,k1∗ } f ∈Fd,θ

where V (f ) := Varf log f (X1 ) =

R

X

f log2 f − H(f )2 .

We remark that the level of smoothness we require for efficiency in Theorem 1, namely β > d/2 is more than is needed for the two-stage estimator
of Laurent (1996) in the case where f is compactly supported and bounded
away from zero on its support, where β > d/4 suffices. As alluded to in the
introduction, the fact that the function x 7→ −x log x is non-differentiable
at x = 0 means that the entropy functional is no longer smooth when f has
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

7

full support, so the arguments of Laurent (1996) can no longer be applied
and very different behaviour may occur (Lepski, Nemirovski and Spokoiny,
1999; Cai and Low, 2011).
It is also useful, e.g. for the purposes of constructing confidence intervals
for the entropy, to understand the asymptotic normality of the estimator.
To this end, let H denote the class of functions h : R → R with khk∞ ≤ 1
and |h(x) − h(y)| ≤ |x − y| for all x, y ∈ R. For probability measures P, Q
on R, we write
Z
dBL (P, Q) := sup

h∈H

∞

h d(P − Q)

−∞

for the bounded Lipschitz distance between P and Q. Recall that dBL
metrises weak convergence. The asymptotic variance V (f ) can be estimated
analogously to H(f ) by V̂nw := max(Ṽnw , 0), where
n

Ṽnw

k

1 XX
wj log2 ξ(j),i − (Ĥnw )2 .
:=
n
i=1 j=1

Fixing q ∈ (0, 1), this suggests that a natural asymptotic (1 − q)-level confidence interval for H(f ) is given by


In,q := Ĥnw − n−1/2 zq/2 (V̂nw )1/2 , Ĥnw + n−1/2 zq/2 (V̂nw )1/2 ,

where zq is the (1−q)th quantile of the standard normal distribution; see also
Delattre and Fournier (2017). Write L(Z) for the distribution of a random
variable Z.
Theorem 2.
sup

Under the conditions of Theorem 1, we have



sup dBL L n1/2 (Ĥnw − H(f )) , N 0, V (f ) → 0

k∈{k0∗ ,...,k1∗ } f ∈Fd,θ

as n → ∞. Consequently,
sup

sup


sup Pf In,q ∋ H(f ) − (1 − q) → 0.

q∈(0,1) k∈{k0∗ ,...,k1∗ } f ∈Fd,θ

We remark that the choice k = kn = ⌈log6 n⌉ with w = w(k) ∈ W (k)
satisfying supk≥kd kw(k) k < ∞ for the weighted Kozachenko–Leonenko estimator satisfies the conditions for efficiency in Theorem 1 whenever f ∈ Fd,θ
with θ = (α, β, γ, ν, a) ∈ Θ satisfying α > d and β > d/2; knowledge of
the precise values of α and β is not required. Moreover, the uniformity
of the asymptotics in k means that if k̂n = k̂n (X1 , . . . , Xn ) is a datadriven choice of k, the conclusions Theorem 2 remain valid provided that
P(k̂n < k0∗ ) + P(k̂n > k1∗ ) → 0.
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

8

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

3. Bias and variance expansions for Kozachenko–Leonenko estimators.
3.1. Bias. The proof of (3) is derived from separate expansions for the
bias and variance of the weighted Kozachenko–Leonenko estimator, and we
treat the bias in this subsection. To gain intuition, we initially focus for
simplicity of exposition on the unweighted estimator
n

1X
log ξi ,
Ĥn =
n
i=1

where we have written ξi as shorthand for ξ(k),i . For x ∈ Rd and u ∈ [0, ∞),
we introduce the sequence of distribution functions
Fn,x (u) := P(ξi ≤ u|Xi = x) =

n−1
X
j=k


n−1 j
pn,x,u(1 − pn,x,u )n−1−j ,
j

where
pn,x,u :=

Z

f (y) dy

and

rn,u :=

Bx (rn,u )



eΨ(k) u
Vd (n − 1)

1/d

.

Further, for u ∈ [0, ∞), define the limiting (Gamma) distribution function
Fx (u) := exp{−uf (x)eΨ(k) }

∞
X
1
uf (x)eΨ(k)
j!
j=k

j

= e−λx,u

∞
X
λjx,u
j=k

j!

,

where λx,u := uf (x)eΨ(k) . That this is the limit distribution for each fixed k
follows from a Poisson approximation to the Binomial distribution and the
Lebesgue differentiation theorem. We therefore expect that
Z ∞
Z
Z ∞
Z
log u dFx (u) dx
f (x)
log u dFn,x (u) dx ≈
f (x)
E(Ĥn ) =
0
X
0
X
Z ∞
Z
 te−Ψ(k) 
tk−1
log
f (x)
=
e−t
dt dx = H.
f (x)
(k − 1)!
0
X
Although we do not explicitly use this approximation in our asymptotic
analysis of the bias, it motivates much of our development. It also explains
the reason for using eΨ(k) in the definition of ξ(k),i , rather than simply k.
Lemma 3 below gives an expression for the asymptotic bias of the unweighted
Kozachenko–Leonenko estimator.
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

9

Lemma 3. Fix d ∈ N and θ = (α, β, ν, γ, a) ∈ Θ. Let k∗ = kn∗ denote any
deterministic sequence of positive integers with k∗ = O(n1−ǫ ) as n → ∞ for
some ǫ > 0. Then there exist λ1 , . . . , λ⌈β/2⌉−1 ∈ R, depending only on f and
d, such that supf ∈Fd,θ maxl=1,...,⌈β/2⌉−1 |λl | < ∞ and for each ǫ > 0,
sup Ef (Ĥn )−H −

f ∈Fd,θ

⌈β/2⌉−1

X
l=1


 α −ǫ
β 
k α+d
kd
Γ(k + 2l/d)Γ(n)
λl = O max
, β
α
Γ(k)Γ(n + 2l/d)
n α+d −ǫ n d

as n → ∞, uniformly for k ∈ {1, . . . , k ∗ }, where λl = 0 if 2l ≥ dα/(α + d).
When d ≥ 3, α > 2d/(d − 2) and β > 2, we have
Z
1
∆f (x)
λ1 = −
dx,
2/d
2/d
X f (x)
2(d + 2)Vd
which is finite under these assumptions; cf. the second part of Proposition
 9
Γ(n)
= n−2l/d 1+
in Section 5.1. Moreover, since, for each l > 0, we have Γ(n+2l/d)
O(n−1 ) , we deduce from Lemma 3 that in this setting,
sup Ef (Ĥn ) − H +

f ∈Fd,θ

Γ(k + 2/d)
2/d

2(d + 2)Vd

Γ(k)n2/d

Z

X

 k2/d 
∆f (x)
.
dx
=
o
f (x)2/d
n2/d

R
(x)
In particular, when d ≥ 4 and X f∆f
dx 6= 0, the bias of the unweighted
(x)2/d
Kozachenko–Leonenko estimator precludes its efficiency.
On the other hand, Lemma 3 motivates the definition of the class of weight
vectors W (k) in (2), and facilitates the expansion for the bias of the weighted
Kozachenko–Leonenko estimator in Corollary 4 below. In particular, since
2(⌊d/4⌋+1)/d > 1/2, we see that this result provides conditions under which
the bias is o(n−1/2 ) for suitably chosen k. This explains why we let ℓ take
values in the range {1, . . . , ⌊d/4⌋} in (2).
Corollary 4. Assume the conditions of Lemma 3. If w = w(k) ∈ W (k)
for k ≥ kd and supk≥kd kw(k) k < ∞, then for every ǫ > 0,
sup
f ∈Fd,θ

Ef (Ĥnw ) −

2(⌊d/4⌋+1)
β 

 α −ǫ
d
kd
k α+d
k
H(f ) = O max
, 2(⌊d/4⌋+1) , β
,
α
n α+d −ǫ n
d
nd

uniformly for k ∈ {1, . . . , k∗ }.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

10

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

The proof of Lemma 3 is given in Section 5.1, but we present here some
of the main ideas that are particularly relevant for the case d ≥ 3, α >
2d/(d − 2) and β ∈ (2, 4]. First, note that
(4)

∂pn,x,u
dFn,x (u)
= Bk,n−k (pn,x,u )
,
du
∂u

a−1 (1 − s)b−1 denotes the density of a Beta(a, b) ranwhere Ba,b (s) := B−1
a,b s
dom variable at s ∈ (0, 1),R with Ba,b := Γ(a)Γ(b)/Γ(a + b). For x ∈ X
and r > 0, define hx (r) := Bx (r) f (y) dy. Since hx (r) is a continuous, nondecreasing function of r, we can define a left-continuous inverse for s ∈ (0, 1)
by

(5)

h−1
x (s) := inf{r > 0 : hx (r) ≥ s} = inf{r > 0 : hx (r) = s},

so that hx (r) ≥ s if and only if r ≥ h−1
x (s). We use the approximation
d
Vd f (x)h−1
x (s) ≈ s −

s1+2/d ∆f (x)
2/d

2(d + 2)Vd

f (x)1+2/d

for small s > 0, which is formalised in Lemma 10(ii) in Section 5.1. In the
case d ≥ 3, α > 2d/(d − 2) and β ∈ (2, 4], the proof of Lemma 3 can be seen
as justifying the use of the above approximation in the following:
Z ∞
Z
log u dFn,x (u) dx
f (x)
E(Ĥn ) =
0
X


Z 1
Z
d
Vd (n − 1)h−1
x (s)
Bk,n−k (s) ds dx
log
f (x)
=
eΨ(k)
0
X

Z 1 
Z
−2/d 2/d
s ∆f (x)
Vd
(n − 1)s 
f (x)
log Ψ(k)
≈
−
Bk,n−k (s) ds dx
e
f (x)
2(d + 2)f (x)1+2/d
0
X
Z
−2/d
Vd
Γ(k + 2/d)Γ(n)
∆f (x)
dx.
= log(n − 1) − Ψ(n) + H −
2(d + 2)Γ(k)Γ(n + 2/d) X f (x)2/d
Note that log(n − 1) − Ψ(n) = −1/(2n) + o(1/n), which leads to the given
bias expression. The proof in other cases proceeds along similar lines. These
heuristics make clear that the function h−1
x (·) plays a key role in understanding the bias. This function is in general complicated, though some
understanding can be gained from the following uniform density example,
where it can be evaluated explicitly. This leads to an exact expression for
the bias, even though the discontinuities mean that the density does not
belong to F1,θ for any θ ∈ Θ.
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

Example 1.
we have

11

Consider the uniform distribution, U [0, 1]. For x ≤ 1/2,
(
s/2,
if s ≤ 2x
h−1
x (s) =
s − x, if 2x < s ≤ 1.

It therefore follows that
E(Ĥn ) − H = 2

Z

1/2 Z ∞

log u dFn,x (u) dx


Z 1/2 Z 1
2(n − 1)h−1
x (s)
Bk,n−k (s) ds dx
log
=2
eΨ(k)
0
0

Z s/2
Z 1/2
Z 1
n − 1
log s dx ds + log Ψ(k)
log(2(s − x)) dx +
= 2 Bk,n−k (s)
e
s/2
0
0
k
= (log 4 − 1) + log(n − 1) − Ψ(n).
n
0

0

3.2. Discussion of conditions and weakening of conditions. Recall the
definitions of the quantity Mf,a,β (x) and A from Section 2. In addition to
standard moment and boundedness assumptions, the condition f ∈ Fd,θ
requires that
(6)

sup Mf,a,β (x) ≤ a(δ)

for all δ > 0 and some a ∈ A.

x:f (x)≥δ

In this subsection, we explore the condition (6) further, with the aid of
several examples.
The condition (6) is reminiscent of more standard Hölder smoothness assumptions, though we also require that the partial derivatives of the density
vary less where f is small. On the other hand, we also allow the neighbourhoods of x in the definition of Mf,a,β (x) to shrink where f (x) is small.
Roughly speaking, the condition requires that the partial derivatives of the
density decay nearly as fast as the density itself in the tails of the distribution. As a simple stability property, if (6) holds for a density f0 , then it also
holds for any density from the location-scale family:

{fΣ (·) = |Σ|−1/2 f0 Σ−1/2 (·−µ) : µ ∈ Rd , Σ = ΣT ∈ Rd×d positive definite}.
This observation allows us to consider canonical representatives of locationscale families in the examples below.

Proposition 5. For each of the following densities f , and for each
d ∈ N, there exists θ ∈ Θ such that f ∈ Fd,θ :
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

12

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN
2

(i) f (x) = f (x1 , . . . , xd ) = (2π)−d/2 e−kxk /2 , the standard normal density;
d+ρ
(ii) f (x) = f (x1 , . . . , xd ) ∝ (1 + kxk2 /ρ)− 2 , the multivariate-t distribution with ρ > 0 degrees of freedom.
Moreover, the following univariate density f also belongs to F1,θ for suitable
θ ∈ Θ:

1 
.
1
f (x) ∝ exp −
1 − x2 {x∈(−1,1)}

The final part of Proposition 5 is included because it provides an example
of a density f that belongs to F1,θ for suitable θ ∈ Θ, even though there
exist points x0 ∈ R with f (x0 ) = 0.
On the other hand, there are also examples, such as Example 2 below,
where the behaviour of f near a point x0 with f (x0 ) = 0 precludes f belonging to Fd,θ for any θ ∈ Θ. To provide some guarantees in such settings,
we now give a very general condition under which our approach to studying
the bias can be applied.
Proposition 6. Assume that f is bounded, that µα (f ) < ∞ for some
α > 0, and let k∗ be as in Lemma 3. Let an := 3(k + 1) log(n − 1), let

1/d
2an
, and assume further that there exists β > 0 such that
rx := Vd (n−1)f
(x)
the function on X given by

supy∈Bx◦ (rx ) |f (y) − f (x)|/ky − xkβ
if β ≤ 1,
Cn,β (x) :=
β−1
˙
˙
supy∈Bx◦ (rx ) kf (y) − f (x)k/ky − xk
if β > 1,
is real-valued. Suppose that Xn ⊆ X is such that
 a β̃/d C (x)
n,β̃
n
→0
n
−
1
x∈Xn
f (x)1+β̃/d
R
as n → ∞, where β̃ := β ∧ 2. Then writing qn := X c f , we have for every
n
ǫ > 0 that


 β̃/d Z
Cn,β̃ (x)
1
k
1−ǫ
,
dx , qn , qn log n ,
(8) Ef (Ĥn ) − H = O max
n
nβ̃/d Xn f (x)β̃/d

(7)

sup

uniformly for k ∈ {1, . . . , k∗ }.
To aid interpretation of Proposition 6, we first remark that if f ∈ Fd,θ for
some θ = (α, β, γ, ν, a) ∈ Θ, then (7) holds, with Xn := {x ∈ X : f (x) ≥ δn },
/ Fd,θ , we may
where δn is defined in (12) below. On the other hand, if f ∈
still be able to obtain explicit bounds on the terms in (8) on a case-by-case
basis, as in the following example.
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

13

Example 2. For a > 1, consider f (x) = Γ(a)−1 xa−1 e−x 1{x>0} , the
density of the Γ(a, 1) distribution. Then for any τ ∈ (0, 1) small enough, we
may take
  1

k a −τ
n
Xn =
, (1 − τ ) log
n
k
to deduce from Proposition 6 that for every ǫ > 0,
Ef (Ĥn ) − H = o
uniformly for k ∈ {1, . . . , k∗ }.

 k1−ǫ 
,
n1−ǫ

Similar calculations show that the bias is of the same order for Beta(a, b)
distributions with a, b > 1.
3.3. Asymptotic variance and normality. We now study the asymptotic
variance of Kozachenko–Leonenko estimators under the assumption that the
tuning parameter k is diverging with n; the fixed k case is deferred to the
next subsection.
Lemma 7. Let θ = (α, β, γ, ν, a) ∈ Θ with α > d and β > 0. Let
∗ and k ∗ = k ∗ denote any two deterministic sequences of positive
k0∗ = k0,n
1,n
1
integers with k0∗ ≤ k1∗ , with k0∗ / log5 n → ∞ and with k1∗ = O(nτ1 ), where τ1
satisfies the condition in Theorem 1. Then for any w = w(k) ∈ W (k) with
supk≥kd kw(k) k < ∞, we have
sup

k∈{k0∗ ,...,k1∗ }

sup nVarf Ĥnw − V (f ) → 0

f ∈Fd,θ

as n → ∞.
The proof of this lemma is lengthy, and involves many delicate error
bounds, so we outline the main ideas in the unweighted case here. First,
we argue that
Var Ĥn = n−1 Var log ξ1 + (1 − n−1 ) Cov(log ξ1 , log ξ2 )

= n−1 V (f ) + Cov log(ξ1 f (X1 )), log(ξ2 f (X2 )) + o(n−1 ),
p

where we hope to exploit the fact that ξ1 f (X1 ) → 1. The main difficulties
in the argument are caused by the fact that handling the covariance above
requires us to study the joint distribution of (ξ1 , ξ2 ), and this is complicated
by the fact that X2 may be one of the k nearest neighbours of X1 or vice
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

14

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

versa, and more generally, X1 and X2 may have some of their k nearest
neighbours in common. Dealing carefully with the different possible events
requires us to consider separately the cases where f (X1 ) is small and large,
as well as the proximity of X2 to X1 . Finally, however, we can apply a normal
approximation to the relevant multinomial distribution (which requires that
k → ∞) to deduce the result. We remark that under stronger conditions
on k, it should also be possible to derive the same conclusion about the
asymptotic variance of Ĥn while only assuming similar conditions on the
density to those required in Proposition 6, but we do not pursue this here.
3.4. Fixed k. A crucial step in the proof of Lemma 7 is the normal approximation to a certain multinomial distribution (cf. the bound on the term
W4 ). This normal approximation is only valid when k → ∞ as n → ∞. In
this subsection, we present evidence to suggest that, when k is fixed (i.e. not
depending on n), then Kozachenko–Leonenko estimators are inefficient. For
simplicity, we focus on the unweighted version of estimator.
Define the functions
αr (s, t) :=


1
µd B0 (s1/d ) ∩ Br1/d e1 (t1/d ) ,
Vd

where e1 = (1, 0, . . . , 0) is the first element of the standard basis for Rd and
µd denotes Lebesgue measure on Rd . Also define the functions Tk on [0, ∞)3
by
L(r,s,t) I(r,s)−ℓ J(r,t)−ℓ

Tk (r, s, t) := eαr (s,t)

X
ℓ=0

X
i=0

X {s − αr (s, t)}i {t − αr (s, t)}j αℓ (s, t)
r
i!j!ℓ!
j=0

I(r,s) J(r,t)

−

X X s i tj
,
i!j!
i=0

j=0

where L(r, s, t) := k − 1 − 1{r<max(s,t)} , I(r, s) := k − 1 − 1{r<s} , J(r, t) :=
k − 1 − 1{r<t} .
In the case k = 1, this function appears in Delattre and Fournier (2017),
where the authors show that, under certain regularity conditions,
Z
T1 (r, s, t)
dr ds dt − 1 + 2 log 2.
e−s−t
lim n Var Ĥn − V (f ) = Ψ′ (1) +
n→∞
st
3
[0,∞)
More generally, Poisson approximation to the same multinomial distribution
mentioned above, together with analysis similar to the proof of Lemma 7,
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION
d\k
1
2
3
5
10

1
2.14
2.29
2.42
2.61
2.85

2
0.97
1.01
1.03
1.05
1.10

3
0.64
0.64
0.64
0.65
0.68

4
0.48
0.47
0.47
0.47
0.50

15

5
0.39
0.38
0.37
0.37
0.40

Table 1
Asymptotic variance inflation (9) of the Kozachenko–Leonenko estimator for fixed k.

suggests that for (fixed) k ≥ 2,
Z
Tk (r, s, t)
e−s−t
lim n Var Ĥn − V (f ) = Ψ′ (k) +
dr ds dt − 1
n→∞
st
[0,∞)3


−(2k−2) 2k − 2
+2
{Ψ(2k − 1) − Ψ(k) − log 2}
k−1

(9)



k−2
1 X −k−j k + j − 1
2
[1 − (k − j){Ψ(k + j) − log 2 − Ψ(k)}].
+
k−1
j
j=0

Here, the Ψ′ (k) term arises as in (18), the integral term arises from the
Poisson approximation, the −1 arises as in (27), and the remaining terms
come from the fact that X1 can be one of the k nearest neighbours of X2 , or
vice-versa, which induces a singular component into the joint distribution
function Fn,x,y of (ξ1 , ξ2 ) given (X1 , X2 ) = (x, y). It is interesting to observe
that this asymptotic inflation of the variance is distribution-free; in Table 1,
we tabulate numerical values for (9) for a few values of d and k. These agree
with those obtained by Delattre and Fournier (2017) for the case k = 1.
4. Lower bounds. In this section, we address the optimality in a local
asymptotic minimax sense of the limiting normalised risk V (f ) given in
Theorem 1 using ideas of semiparametric efficiency (e.g. van der Vaart, 1998,
Chapter 25). For f ∈ Fd,θ , t ≥ 0 and a Borel measurable function g : Rd →
R, define ft,g : Rd → [0, ∞) by
2c(t)
f (x),
1 + e−2tg(x)
−1
R
2
f (x) dx
. This definition ensures that {ft,g :
where c(t) := Rd 1+e−2tg(x)
t ≥ 0} is differentiable in quadratic mean at t = 0 with score function g (e.g.
van der Vaart, 1998, Example 25.16). We say (H̃n ) is an estimator sequence
if H̃n : (Rd )×n → R is a measurable function for each n ∈ N.

(10)

ft,g (x) :=

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

16

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

Theorem 8. Fix d ∈ N, θ = (α, β, γ, µ, a) ∈ Θ and f ∈ Fd,θ . For λ ∈ R,
let gλ := λ{log f + H(f )}. Then, writing I for the set of finite subsets of R,
we have for any estimator sequence (H̃n ) that
(11)

sup lim inf max nEf
I∈I n→∞

λ∈I

n−1/2 ,gλ



H̃n − H(fn−1/2 ,gλ )

2

≥ V (f ).

Moreover, whenever t|λ| ≤ min(1, {144V (f )}−1/2 ), we have ft,gλ ∈ Fd,θ̃ ,

where θ̃ := α, β, 4γ, 4µ, ã ∈ Θ, and ã ∈ A is defined in (90) in the online
supplement.
The proof of Theorem 8 reveals that, at every f ∈ Fd,θ , the entropy
functional H is differentiable relative to the tangent set {gλ : λ ∈ R} with
efficient influence function
ψ̃f := − log f − H(f ).
This observation, together with Theorem 1, confirms that under the assumptions on θ, w and k in that result, the weighted Kozachenko–Leonenko
estimator Ĥnw is (asymptotically) efficient at f ∈ Fd,θ in the sense that
n1/2 {Ĥnw − H(f )} =

n
1 X

n1/2

ψ̃f (Xi ) + op (1)

i=1

(cf. van der Vaart, 1998, p. 367). Moreover, the second part of Theorem 8
and Theorem 1 imply in particular that, under these same conditions on
θ, w and k, the estimator Ĥnw attains the local asymptotic minimax lower
bound, in the sense that
 w
2
Ĥn − H(fn−1/2 ,gλ )
= V (f ).
sup lim max nEf −1/2
I∈I n→∞ λ∈I

n

,gλ

5. Proofs of main results.
5.1. Auxiliary results and proofs of Lemma 3 and Corollary 4. Throughout the proofs, we write a . b to mean that there exists C > 0, depending
only on d ∈ N and θ ∈ Θ, such that a ≤ Cb. The proof of Lemma 3 relies on
the following two auxiliary results, whose proofs are given in Appendix A.4.
Proposition 9.
Then

Let θ = (α, β, γ, ν, a) ∈ Θ, d ∈ N and τ ∈
Z

a f (x) f (x)τ dx → 0
sup

f ∈Fd,θ

d
α+d , 1



.

{x:f (x)<δ}

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

17

EFFICIENT ENTROPY ESTIMATION

as δ ց 0. Moreover, for every ρ > 0,
Z
ρ
a f (x) f (x)τ < ∞.
sup
f ∈Fd,θ

X

Recall the definition of h−1
x (·) in (5). The first part of Lemma 10 below
provides crude but general bounds; the second gives much sharper bounds
in a more restricted region.
Lemma 10.
(i) Let f ∈ Fd and let α > 0. Then for every s ∈ (0, 1)
and x ∈ Rd ,


1/d
 µ (f ) 1/α
s
α
−1
.
≤ hx (s) ≤ kxk +
Vd kf k∞
1−s

(ii) Fix θ = (α, β, γ, ν, a) ∈ Θ, and let Sn ⊆ (0, 1), Xn ⊆ Rd be such that
Cn := sup sup sup

f ∈Fd,θ s∈Sn x∈Xn

a(f (x))d/(1∧β) s
→ 0.
f (x)

Then there exists n∗ = n∗ (d, θ) ∈ N such that for all n ≥ n∗ , s ∈ Sn ,
x ∈ Xn and f ∈ Fd,θ , we have
d
Vd f (x)h−1
x (s)

−

⌈β/2⌉−1

X

bl (x)s

1+2l/d

l=0

a(f (x))d/(2∧β) s
.s
f (x)


β/d

,

where b0 (x) = 1 and |bl (x)| . a(f (x))l f (x)−2l/d for l ≥ 1. Moreover,
if β > 2, then
b1 (x) = −

∆f (x)
2/d

2(d + 2)Vd

f (x)1+2/d

.

We are now in a position to prove Lemma 3.
Proof of Lemma 3. (i) We initially prove the result in the case d ≥ 3,
α > 2d/(d − 2) and β ∈ (2, 4], where it suffices to show that
Z
Γ(k + 2/d)Γ(n)
∆f (x)
sup Ef (Ĥn ) − H +
dx
2/d
2/d
f ∈Fd,θ
2(d + 2)Vd Γ(k)Γ(n + 2/d) X f (x)

 α −ǫ
β 
k α+d
kd
= O max
, β
α
n α+d −ǫ n d
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

18

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

as n → ∞, uniformly for k ∈ {1, . . . , k ∗ }. Fix f ∈ Fd,θ . Define cn := a(k/(n−
1))1/(1∧β) , let
δn := kcdn log2 (n − 1)/(n − 1)

(12)

and let Xn := {x : f (x) ≥ δn }. Recall that an := 3(k + 1) log(n − 1) and let
ux,s :=

d
Vd (n − 1)h−1
x (s)
.
eΨ(k)

The proof is based on (4) and Lemma 10(ii), which allow us to make the
transformation s = pn,x,u = hx (rn,u ). Writing Ri , i = 1, . . . , 5 for remainder
terms to be bounded at the end of the proof, we can write
Z ∞
Z
f (x)
log u dFn,x (u) dx
E(Ĥn ) =
X
0
Z 1
Z
Bk,n−k (s) log ux,s ds dx + R1
f (x)
=
0

Xn

=

Z

f (x)

Xn

=

Z

f (x)

Xn

Z

Z

an
n−1

Bk,n−k (s) log ux,s ds dx + R1 + R2

0

0

an
n−1

n

log

 (n − 1)s 
eΨ(k) f (x)

3
−2/d 2/d
X
s ∆f (x) o
Vd
Ri
B
(s)
ds
dx
+
k,n−k
2(d + 2)f (x)1+2/d
i=1
 


Z
−2/d
4
X
Bk+2/d,n−k ∆f (x)
V
n−1
f (x) log
Ri
=
dx
+
− Ψ(n) − d
f (x)
2(d + 2)Bk,n−k f (x)1+2/d
Xn
i=1
Z
5
−2/d
X
Γ(k + 2/d)Γ(n)
Vd
∆f (x)
= H +log(n − 1)−Ψ(n) −
Ri .
dx +
2(d + 2)Γ(k)Γ(n + 2/d) Xn f (x)2/d
i=1

−

After multiplying the integrand by an appropriate positive power of δn /f (x),
the first part of Proposition 9 tells us that for every ǫ > 0,
 α −ǫ 
Z
∆f (x)
k α+d
k2/d
sup
dx
=
O
sup
α
2/d
2/d
f ∈Fd,θ Xnc f (x)
n α+d −ǫ
k∈{1,...,k ∗ } n
as n → ∞. Since log(n − 1) − Ψ(n) = O(1/n), it now remains to bound
R1 , . . . , R5 . Henceforth, to save repetition, we adopt without further mention
the convention that whenever an error term inside O(·) or o(·) depends on
k, this error is uniform for k ∈ {1, . . . , k∗ }; thus g(n, k) = h(n, k) + o(1) as
n → ∞ means supk∈{1,...,k∗ } |g(n, k) − h(n, k)| → 0 as n → ∞.
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

19

EFFICIENT ENTROPY ESTIMATION

To bound R1 . By Lemma 10(i), we have Vdα µα (f )d kf kα∞ ≥ αα dd /(α +
Hence

d)α+d .

| log ux,s | ≤ log(n − 1) + |Ψ(k)| − log s + | log kf k∞ | + | log Vd |


d
d
kxk
+ | log µα (f )| − log(1 − s) + d log 1 + 1/α
α
α
µα (f )

 α d

V ν (α + d)α+d
1
≤ log(n − 1) + |Ψ(k)| − log s + max log γ , log d
α
αα dd

 α α

α+d
V γ (α + d)
1
d
d
− log(1 − s)
+ | log Vd | + max log ν , log d
α
d
α
d
α d
α
(13)

1
1

1/d
kxk(α + d) α + d Vd γ 1/d
+ d log 1 +
.
α1/d d1/α
Moreover, for any C0 , C1 ≥ 0, ǫ ∈ (0, α) and ǫ′ ∈ (0, ǫ), we have by Hölder’s
inequality that
Z

f (x) C0 + log(1 + C1 kxk) dx
sup
f ∈Fd,θ

Xnc

α−ǫ′
α+d

≤ δn

sup
f ∈Fd,θ

α−ǫ′
α+d

≤ δn
=o



k

Z

(1 + ν)

α
−ǫ
α+d
α

n α+d −ǫ



X

d+ǫ′ 
f (x) α+d C0 + log(1 + C1 kxk) dx

d+ǫ′
α+d

Z

Rd



C0 + log(1 + C1 kxk)
(1 + kxkα )

d+ǫ′
α−ǫ′

α+d
α−ǫ′

dx

 α−ǫ′
α+d

.

Since |E(log B)| = Ψ(a + b) − Ψ(a) when B ∼ Beta(a, b), we deduce that for
each ǫ > 0,
 α −ǫ 
Z 1
Z
k α+d
Bk,n−k (s) log ux,s ds dx = o
f (x)
R1 =
α
n α+d −ǫ
0
Xnc
as n → ∞, uniformly for f ∈ Fd,θ .
To bound R
 2 . For random variables B1 ∼ Beta(k, n−k) and B2 ∼ Bin n−
1, an /(n − 1) we have that for every ǫ > 0,
(14)



(an − k + 1)2
= o(n−(3−ǫ) ),
P B1 ≥ an /(n − 1) = P(B2 ≤ k − 1) ≤ exp −
2an
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

20

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

where the inequality follows from standard bounds on the left-hand tail
of the binomial distribution (see, e.g. Shorack and Wellner (2009), Equation (6), page 440). Now, for any C
R 1 > 0, we have α log(1 + C1 kxk) ≤
α
(1 + C1 kxk) − 1, so that supf ∈Fd,θ X f (x) log(1 + C1 kxk) dx < ∞. Moreover,
Z 1
Z 1
n−1
−
log(1−s)Bk,n−k (s) ds ≤
Bk,n−k−1 (s) ds = o(n−(3−ǫ) ),
an
n − k − 1 an
n−1

n−1

for every ǫ > 0, by a virtually identical argument to (14). We therefore
deduce from these facts and (13) that for each ǫ > 0,
(15)

R2 =

Z

f (x)

Xn

Z

1
an
n−1

Bk,n−k (s) log ux,s ds dx = o(n−(3−ǫ) ),

which again holds uniformly in f ∈ Fd,θ .
To bound R3 . We can write


Z an  
Z
d
d
n−1
Vd f (x)h−1
Vd f (x)h−1
x (s) − s
x (s)
−
log
f (x)
R3 =
s
s
0
Xn


−2/d 2/d
d
s ∆f (x)
Vd
Vd f (x)h−1
x (s) − s
Bk,n−k (s) ds dx
+
+
s
2(d + 2)f (x)1+2/d
=: R31 + R32 ,
say. Now, note that
sup

sup

sup

sup

k∈{1,...,k ∗ } f ∈Fd,θ s∈(0,an /(n−1)] x∈Xn

a(f (x))d s
6
≤
→ 0.
f (x)
log(n − 1)

It follows by Lemma 10(ii) that there exist a constant C = C(d, θ) > 0 and
n1 = n1 (d, θ) ∈ N such that for n ≥ n1 , k ∈ {1, . . . , k ∗ }, s ≤ an /(n − 1) and
x ∈ Xn ,


d
sa(f (x))d/2 β/d
Vd f (x)h−1
s2/d ∆f (x)
x (s) − s
≤C
,
+
2/d
s
f (x)
2(d + 2)Vd f (x)1+2/d
and


−2/d 2/d
d
s a(f (x))
d1/2 Vd
sa(f (x))d/2 β/d 1
Vd f (x)h−1
x (s) − s
+
C
≤ .
≤
s
f (x)
2
2(d + 2)f (x)2/d
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

21

EFFICIENT ENTROPY ESTIMATION

Thus, for n ≥ n1 and k ∈ {1, . . . , k ∗ }, using the fact that | log(1+z)−z| ≤ z 2
for |z| ≤ 1/2,
−4/d

s4/d a(f (x))2
dVd
f (x)
|R31 | ≤ 2
4(d + 2)2 f (x)4/d
0
Xn



d/2 2β/d
2 sa(f (x))
+C
Bk,n−k (s) ds dx
f (x)
Z
−4/d
dVd
Γ(k + 4/d)Γ(n)
≤
a(f (x))2 f (x)1−4/d dx
2(d + 2)2 Γ(k)Γ(n + 4/d) Xn
Z
2C 2 Γ(k + 2β/d)Γ(n)
+
a(f (x))β f (x)1−2β/d dx.
Γ(k)Γ(n + 2β/d)
Xn
Z 1 

Z

On the other hand, we also have for n ≥ n1 and k ∈ {1, . . . , k ∗ } that

sa(f (x))d/2 β/d
Bk,n−k (s) ds dx
f (x)
0
Xn
Z
CΓ(k + β/d)Γ(n)
≤
a(f (x))β/2 f (x)1−β/d dx.
Γ(k)Γ(n + β/d) Xn

|R32 | ≤ C

Z

f (x)

Z 1

Multiplying each of the integrals by f (x)/δn to an appropriate positive power
if necessary and by the second part of Proposition 9, for every ǫ > 0,


max(|R31 |, |R32 |) = O max



α

k α+d −ǫ
α

n α+d −ǫ

β

,

kd
β

nd



,

uniformly for f ∈ Fd,θ .
To bound R4 . We have


 
−2/d 2/d
Vd
s ∆f (x)
(n − 1)s
f (x)
R4 =
Bk,n−k (s) ds dx.
−
log Ψ(k)
an
e
f (x)
2(d + 2)f (x)1+2/d
Xn
n−1
Z

Z

1

Consider the random variable B1 ∼ Beta(k, n − k). Then, using (14) and the
fact that (n − 1)s/eΨ(k) ≥ 1 for s ≥ an /(n − 1) and n ≥ 3, we conclude that
for every ǫ > 0 and n ≥ 3,

 
  
Z
a(f (x))
an 
n − 1
|R4 | ≤ log Ψ(k) + f (x) | log f (x)| +
dx
P
B
≥
1
2
2
n−1
e
Xn
f (x) d Vdd
= o(n−(3−ǫ) ),
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

22

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

uniformly for fR∈ Fd,θ , where, by Lemma 11(i) in the online supplement, we
have supf ∈Fd,θ Xn f (x)| log f (x)| dx < ∞.
To bound R5 . We use the fact that for f ∈ Fd,θ , x ∈ X and ǫ′ > 0,
 kf k 
∞
| log f (x)| ≤ log kf k∞ + log
f (x)
 d


ν (α + d)α+d
1  γ ǫ′
1
.
+
≤ max log γ , log Vd + log
α
αα dd
ǫ′ f (x)

It follows from the first part of Proposition 9 (having replaced a(δ) with
max{a(δ), | log δ|} if necessary) that for each ǫ > 0,
 α −ǫ 
Z
k α+d
f (x){log(n − 1) − Ψ(n) − log f (x)} dx = o
R5 =
α
n α+d −ǫ
Xnc
uniformly in f ∈ Fd,θ . The claim follows when d ≥ 3, α > 2d/(d − 2) and
β ∈ (2, 4].
We now consider the case where either d ≤ 2 or α ≤ 2d/(d − 2) or
β ∈ (0, 2], for which we need only show that
β 

 α −ǫ
kd
k α+d
.
, β
sup |Ef (Ĥn ) − H| = O max
α
f ∈Fd,θ
n α+d −ǫ n d
The calculation here is very similar, but we approximate log ux,s simply by
(n−1)s 
. Writing R1′ , . . . , R5′ for the modified error terms, we obtain
log eΨ(k)
f (x)
Ef (Ĥn ) = H + log(n − 1) − Ψ(n) +

5
X

Ri′ .

i=1

 α/(α+d)−ǫ
Here, R1′ = R1 = o nk
, and R2′ = R2 = o(n−(3−ǫ) ), for every
ǫ > 0 in both cases. On the other hand,


Z an
Z
d
n−1
Vd f (x)h−1
x (s)
′
log
f (x)
R3 =
Bk,n−k (s) ds dx
s
0
Xn

 α −ǫ

k α+d
kβ/d
= O max
,
α
n α+d −ǫ nβ/d
for every ǫ > 0, by Lemma 10(ii). Similarly, for every ǫ > 0,


Z 1
Z
(n − 1)s
′
log Ψ(k)
Bk,n−k (s) ds dx = o(n−(3−ǫ) ),
f (x)
R4 =
an
e
f
(x)
Xn
n−1
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

23

EFFICIENT ENTROPY ESTIMATION

 α/(α+d)−ǫ
. All of these bounds hold uniformly in
and R5′ = R5 = o nk
f ∈ Fd,θ , so the claim is established for this setting.
Finally, consider now the case d ≥ 3, α > 2d/(d − 2) and β > 4. Again
the calculation is very similar to the earlier cases, with the with the main
difference being that in bounding the error corresponding to R3 , we require
a higher-order Taylor expansion of


d
Vd f (x)h−1
x (s) − s
.
log 1 +
s
This can be done using Lemma 10(ii); we omit the details for brevity.
β′

Proof of Corollary 4. It is convenient to write d′ := ⌊d/4⌋ + 1 and
:= ⌈β/2⌉ − 1. We have

|Ef (Ĥnw )

− H| =

k
X
j=1

≤

k
X
j=1


⌊d/4⌋
X Γ(j + 2l/d)Γ(n) 
λl
wj Ef (log ξ(j),1 ) − H −
Γ(j)Γ(n + 2l/d)
l=1



β′
X
Γ(j + 2l/d)Γ(n)
wj Ef (log ξ(j),1 ) − H −
λl
Γ(j)Γ(n + 2l/d)
l=1

+

k
X

wj

j=1

β′
X

l=d′

Γ(j + 2l/d)Γ(n)
λl
Γ(j)Γ(n + 2l/d)



.

The first term can be bounded, uniformly for f ∈ Fd,θ and k ∈ {1, . . . , k∗ },
using Lemma 3. For the second term, we can use monotonicity properties of
ratios of gamma functions to write
k
X
j=1


β′
β′
k
X
X
X
Γ(k + 2l/d)Γ(n)
Γ(j + 2l/d)Γ(n)
|wj |
λl ≤ ′max ′ |λℓ |
wj
d ≤ℓ≤β
Γ(j)Γ(n + 2l/d)
Γ(k)Γ(n + 2l/d)
′
′
j=1

l=d

l=d

 k2d′ /d 
 Γ(k +
≤ d1/2 kwk β ′ − d′ + 1
|λ
|
=
O
max
,
l
′
Γ(k)Γ(n + 2d′ /d) d′ ≤l≤β ′
n2d /d
2d′ /d)Γ(n)

uniformly for f ∈ Fd,θ . The result follows.

5.2. Proof of Lemma 7. Since this proof is long, we focus here on the
main argument, and defer proofs of bounds on the many error terms to
Appendix A.8.
Proof of Lemma 7. We employ the same notation as in the proof of
Lemma 3, except that we redefine δn so that δn := kcdn log3 (n − 1)/(n − 1).
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

24

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

We write Xn := {x : f (x) ≥ δn } for this newly-defined δn . Similar to the
proof of Lemma 3, all error terms inside O(·) and o(·) that depend on k are
uniform for k ∈ {k0∗ , . . . , k1∗ }, and we now adopt the additional convention
that, where relevant, these error terms are also uniform for f ∈ Fd,θ . By
the nested properties of the classes Fd,θ with respect to the smoothness
parameter β, we may assume without loss of generality that β ∈ (0, 1]. We
first deal with the variance of the unweighted estimator Ĥn , and note that
Var Ĥn = n−1 Var log ξ1 + (1 − n−1 ) Cov(log ξ1 , log ξ2 )


= n−1 Var log ξ1 + (1 − n−1 ) Cov log(ξ1 f (X1 )), log(ξ2 f (X2 ))

(16)
− 2 Cov log(ξ1 f (X1 )), log f (X2 ) .
We claim that for every ǫ > 0,

α

 β/d

k
1
k α+d −ǫ
(17) Var log ξ1 = V (f ) + {1 + o(1)} + O max β/d log n ,
α
k
n
n α+d −ǫ

as n → ∞. The proof of this claim uses similar methods to those in the
proof of Lemma 3. In particular, writing S1 , . . . , S5 for remainder terms to
be bounded later, we have
Z ∞
Z
2
log2 u dFn,x (u) dx
f (x)
E(log ξ1 ) =
0
X
Z 1
Z
Bk,n−k (s) log2 ux,s ds dx + S1
f (x)
=
0

Xn

=

Z

f (x)

Xn

=
=

Z

f (x)

ZXn
Xn

Z

Z

an
n−1

Bk,n−k (s) log2 ux,s ds dx + S1 + S2

0
an
n−1

log

0

2




(n − 1)s
Bk,n−k (s) ds dx + S1 + S2 + S3
eΨ(k) f (x)


f (x) log2 f (x) − 2{log(n − 1) − Ψ(n)} log f (x)
′

′

2

+ Ψ (k) − Ψ (n) + {log(n − 1) − Ψ(n)}
(18)

=

Z

X

f (x) log2 f (x) dx +

5
X
i=1

Si +

1
{1 + o(1)},
k



dx +

4
X

Si

i=1

as n → ∞. In Appendix A.8.1, we show that for every ǫ > 0,
α

 β/d

5
X
k
k α+d −ǫ
|Si | = O max β/d log n ,
(19)
α
n
n α+d −ǫ
i=1
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

25

as n → ∞. Combining (18) with (19) and Lemma 3, we deduce that (17)
holds.
The next step of our proof consists of showing that for every ǫ > 0,
(20)


 − 1 + 2α−ǫ
1 β

k 2 α+d k 2 + d
2+β/d
,
log
n
Cov log(ξ1 f (X1 )), log f (X2 ) = O max
2α−ǫ
β
n1+ d
n α+d

as n → ∞. Define

−
Fn,x
(u) :=

n−2
X
j=k

F̃n,x (u) :=

n−2
X


n−2 j
pn,x,u(1 − pn,x,u )n−2−j ,
j

j=k−1




n−2 j
pn,x,u(1 − pn,x,u )n−2−j ,
j

so that
P(ξ1 ≤ u|X1 = x, X2 = y) =



− (u) if kx − yk > r
Fn,x
n,u
F̃n,x (u) if kx − yk ≤ rn,u .

Writing ũn,x,y := Vd (n − 1)kx − ykd e−Ψ(k) , we therefore have that

Cov log(ξ1 f (X1 )), log f (X2 )
Z ∞
Z

−
log uf (x) d(F̃n,x − Fn,x
)(u) dx dy
f (x)f (y) log f (y)
=
ũn,x,y
X ×X
Z ∞
Z

−
(21)
f (x)
log uf (x) d(Fn,x
− Fn,x )(u) dx.
− H(f )
X

0

To deal with the first term in (21), we make the substitution
(22)

y = yx,z := x +

rn,1
z,
f (x)1/d

and let dn := (24 log n)1/d . Writing T1 , T2 , T3 for remainder terms to be

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

26

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

bounded later, for every ǫ > 0 and for k ≥ 2,
Z ∞
Z
−
log(uf (x)) d(F̃n,x − Fn,x
)(u) dy dx
f (x)f (y) log f (y)
X ×X
ũn,x,y
Z ∞
Z Z
−
d
log(uf (x)) d(F̃n,x − Fn,x
)(u)dzdx+T1
f (yx,z ) log f (yx,z )
= rn,1
d
kzk
f (x)

Xn B0 (dn )

d
= rn,1

Z

Z
f (x) log f (x)

Xn

k−1
=
n−k−1

Z

B0 (dn )

Z

Z
f (x) log f (x)dx

Xn

∞

−
log(uf (x)) d(F̃n,x − Fn,x
)(u)dzdx+T1 +T2

kzkd
f (x)
an
n−1

log

0

 (n−1)s 
 (n−2)s 
ds
B
(s)
1−
k,n−k−1
k−1
eΨ(k)
3
X
Ti
+
i=1

(23)

α
 X

3
H(f )
k α+d −ǫ
−2
=
Ti .
+ O(n ) + o 1+ α −ǫ +
n
n α+d
i=1

In Appendix A.8.2, we show that for every ǫ > 0,
3
X

(24)



|Ti | = O max

i=1



1

2α

k− 2 + α+d −ǫ
2α

n α+d −ǫ

1

,

β

k2+d
β

n1+ d

log

2+β/d

n



as n → ∞. We now deal with the second term in (21). Writing U1 , U2 for
remainder terms to be bounded later, for every ǫ > 0,
Z ∞
Z

−
log uf (x) d(Fn,x
− Fn,x )(u) dx
f (x)
X

0

an
n−1

n (n − 1)s − k o
ds dx + U1
=
log(ux,s f (x))Bk,n−k−1 (s)
n−k−1
Xn
0
Z 1
Z
 (n − 1)s 
n (n − 1)s − k o
f (x) log
=
B
(s)
ds dx + U1 + U2
k,n−k−1
n−k−1
eΨ(k)
0
Xn
Z

Z
f (x)

(25)

α


k α+d −ǫ
1
+ U1 + U2 + o 1+ α −ǫ .
=
n−1
n α+d

In Appendix A.8.3, we show that for every ǫ > 0,
(26)

α

 β/d
k α+d −ǫ
k
k1/2
.
max β/d ,
|U1 | + |U2 | = O
α
n
n
n α+d −ǫ



imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

27

EFFICIENT ENTROPY ESTIMATION

From (21), (23), (24), (25) and (26), we conclude that (20) holds. 
By (16), it remains to consider Cov log(ξ1 f (X1 )), log(ξ2 f (X2 )) . We require some further notation. Let Fn,x,y denote the conditional distribution
1/2 log1/2 n) ∨ 0,
function of (ξ1 , ξ2 ) given X1 = x, X2 = y. Let a−
n := (k − 3k
1/2
1/2 log
n) ∧ (n − 1), and let
a+
n := (k + 3k
vx := inf{u ≥ 0 : (n−1)pn,x,u = a+
n },

lx := inf{u ≥ 0 : (n−1)pn,x,u = a−
n },

so that P{ξ1 ≤ lX1 } = o(n−(9/2−ǫ) ) and P{ξ1 ≥ vX1 } = o(n−(9/2−ǫ) ) for
every ǫ > 0. For pairs (u, v) with u ≤ vx and v ≤ vy , let (M1 , M2 , M3 ) ∼
Multi(n − 2; pn,x,u , pn,y,v , 1 − pn,x,u − pn,y,v ), and write
Gn,x,y (u, v) := P(M1 ≥ k, M2 ≥ k),
so that Fn,x,y (u, v) = Gn,x,y (u, v) for kx − yk > rn,u + rn,v . Write


1 αz
Σ :=
αz 1

with αz := Vd−1 µd B0 (1) ∩ Bz (1) for z ∈ Rd , let ΦΣ (s, t) denote the distribution function of a N2 (0, Σ) random vector at (s, t), and let Φ denote the
standard univariate normal distribution function. Writing Wi for remainder
terms to be bounded later, and writing h(u, v) := log(uf (x)) log(vf (y)) as
shorthand, we have
Cov(log(ξ1 f (X1 )), log(ξ2 f (X2 )))
Z ∞Z ∞
Z
h(u, v) d(Fn,x,y − Fn,x Fn,y )(u, v) dx dy
f (x)f (y)
=
0
0
X ×X
Z
Z
h(u, v) d(Fn,x,y − Fn,x Fn,y )(u, v) dx dy + W1
f (x)f (y)
=
[lx ,vx ]×[ly ,vy ]

X ×X

=

Z

=

Z

f (x)f (y)

Z vxZ

X ×X

d
rn,1
k

Z

B0 (2)

h(u, v) d(Fn,x,y −Gn,x,y )(u, v)dxdy −
[lx ,vx ]×[ly ,vy ]

lx

Xn ×X

=

2

f (x)f (y)

Z

Z

∞
−∞

Z

vy
ly

∞

i=1

1
(Fn,x,y − Gn,x,y )(u, v)
du dv dx dy − +
uv
n
4

{ΦΣ (s, t) − Φ(s)Φ(t)} ds dt dz −

−∞

3
X

Wi

i=1

1 X
Wi
+
n
i=1

(27)
=

1 X
Wi
+
n

  X
4
4
1
1 X
eΨ(k)
Wi = O
Wi .
− +
+
k(n − 1) n
nk
i=1

i=1

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

28

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

The proof in the unweighted case is completed by showing in Appendix A.8.4
that for every ǫ > 0,
4
X

|Wi |

i=1

α−ǫ
2α−ǫ 
3
β
5
3 2β
1
(1+ d ) α−ǫ
log 2 n k 2 + α+d k 2 + d k 2β α+d k 2 + d log n k α+d
= O max
,
,
, 2α−ǫ
α−ǫ ,
α−ǫ
1 ,
2β
β
nk 2 n1+ α+d n1+ d
n1+ d
n1+ α+d
n α+d
as n → ∞.
The proof in the weighted case uses similar arguments; details are deferred
to Appendix A.8.4.





5.3. Proofs of Theorems 1 and 2.
Proof of Theorem 1. Writing jt := ⌊tk/d⌋ for t = 1, . . . , d and d′ :=
⌊d/4⌋ + 1 for convenience, a sufficient condition for W (k) 6= ∅ is that the
′
′
matrix A(k) ∈ Rd ×d with (l, t)th entry
(k)

Alt = Γ(jt )−1 Γ(jt + 2(l − 1)/d)k−2(l−1)/d ,
′

is invertible. This follows because, writing e1 := (1, 0, . . . , 0)T ∈ Rd we can
then define w = w(k) ∈ W (k) by setting
⌊d/4⌋+1

(wjt )t=1

:= (A(k) )−1 e1
′

′

and setting all other entries of w to be zero. Now define A ∈ Rd ×d to have
(l, t)th entry Alt := (t/d)2(l−1)/d . Since x−a Γ(x)−1 Γ(x + a) → 1 as x → ∞
for a ∈ R, we have kA(k) − Ak → 0 as k → ∞. Now, A is a Vandermonde
matrix (depending only on d) and as such has determinant
Y
2/d
2/d
|A| =
d−2/d (t2 − t1 ) > 0.
1≤t1 <t2 ≤d′

Hence, by the continuity of the determinant and eigenvalues of a matrix,
we have that there exists kd > 0 such that, for k ≥ kd , the matrix A(k) is
invertible and
k(A(k) )−1 e1 k ≤ |λmin (A(k) )|−1 ≤ 2|λmin (A)|−1 ,
where λmin (·) denotes the eigenvalue of a matrix with smallest absolute
value. It follows that, for each k ≥ kd , there exists w(k) ∈ W (k) satisfying
supk≥kd kw(k) k < ∞, as required.
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

29

EFFICIENT ENTROPY ESTIMATION

Now, by Corollary 4 and the fact that w ∈ W (k) , we have for ǫ > 0
sufficiently small,
Ef (Ĥnw ) −



H(f ) = O max



α

k α+d −ǫ
α

n α+d −ǫ

,

k

2d′
d

n

2d′
d

β

,

kd
n

β
d



= o(n−1/2 ),

uniformly for f ∈ Fd,θ , under our conditions on k1∗ , α and β. By Lemma 7
we have Var Ĥnw = n−1 V (f ) + o(n−1 ) uniformly for f ∈ Fd,θ . Note that by
Cauchy–Schwarz, very similar arguments to those used at (18) and Lemma 11
in the supplement we have that, for j ∈ supp(w),




 1/2

Covf log ξ(j),1 f (X1 ) , log f (X1 ) ≤ V (f )Ef log2 ξ(j),1 f (X1 )
→0
uniformly for f ∈ Fd,θ . Therefore, also using (20), we have that

Varf (Ĥnw − Hn∗ ) = Varf Ĥnw + 2Covf (Ĥnw , log f (X1 )) + n−1 V (f )
k



2X
= Varf Ĥnw − n−1 V (f ) +
wj Covf log ξ(j),1 f (X1 ) , log f (X1 )
n
j=1

+ 2(1 − n−1 )

k
X
j=1




wj Cov log ξ(j),2 f (X2 ) , log f (X1 ) = o(n−1 )

as n → ∞, uniformly for f ∈ Fd,θ . The conclusion (3) follows on writing

Ef (Ĥnw − Hn∗ )2 = Varf (Ĥnw − Hn∗ ) + (Ef Ĥnw − H(f ))2 ,

and the final conclusion is then immediate.

Proof of Theorem 2. We have



dBL L n1/2 {Ĥnw − H(f )} , L n1/2 {Hn∗ − H(f )}


≤ sup Ef h n1/2 {Ĥnw − H(f )} − h n1/2 {Hn∗ − H(f )}
h∈H

(28)

1/2
 
.
≤ n1/2 Ef |Ĥnw − Hn∗ | ≤ n1/2 Ef (Ĥnw − Hn∗ )2

Now write H∗ for the class of functions
 h : R → R having Lipschitz constant
at most 1, and let Z ∼ N 0, V (f ) . Then by standard properties of the
Wasserstein distance (e.g. Gibbs and Su, 2002, p. 424) and the non-uniform

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

30

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

version of the Berry–Esseen theorem (e.g. Paditz, 1989, Theorem 1),



1/2
∗
dBL L n {Hn − H(f )} , N 0, V (f )

≤ sup Ef h n1/2 {Hn∗ − H(f )} − Eh(Z)
h∈H∗
Z ∞

78β3 (f )
(29)
,
=
Pf n1/2 {Hn∗ − H(f )} ≤ x − P(Z ≤ x) dx ≤ 1/2
n V (f )
−∞
where

β3 (f ) := Ef



log f (X1 ) + H(f )

3

=

Z

f (x)| log f (x) + H(f )|3 dx.
X

We conclude from (28) and (29), together with Theorem 1 and Lemma 11
in the online supplement, that



sup
sup dBL L n1/2 (Ĥnw − H(f )) , N 0, V (f ) → 0
k∈{k0∗ ,...,k1∗ } f ∈Fd,θ

as n → ∞, as required.
For the second part of the theorem, set

ǫn = ǫw
n (d, θ) :=


1/3

supk∈{1,...,k∗ } supf ∈Fd,θ 2Ef {Ṽnw − V (f )}2
inf f ∈Fd,θ V (f )2/3

,

so that ǫn → 0, by Lemmas 11(ii) and 13 in the online supplement. Then,
by two applications of Markov’s inequality, for n large enough that ǫn ≤ 1,
Pf



(V̂nw )1/2
− 1 ≥ ǫn
V 1/2 (f )




Ṽnw
− 1 ≥ ǫn + Pf (Ṽnw ≤ 0)
≤ Pf
V (f )



Ef {Ṽnw − V (f )}2
1
+ 1 ≤ ǫn .
≤
V (f )2
ǫ2n


For n ∈ N and L ≥ 1, define hn,L : R → [0, 1] by

if |x| > zq/2 (1 + ǫn ) + 1/L
 0
L{zq/2 (1 + ǫn ) + 1/L − |x|} if 0 < |x| − zq/2 (1 + ǫn ) ≤ 1/L
hn,L (x) :=

1
if |x| ≤ zq/2 (1 + ǫn ).

Thus hn,L has Lipschitz constant L and hn,L (x) ≥

1{|x|≤zq/2 (1+ǫn )} . Then,

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

31

EFFICIENT ENTROPY ESTIMATION

with Z ∼ N (0, 1),

Pf In,q ∋ H(f )

 1/2

 1/2 w
V (f )
1
n |Ĥn − H(f )|
≤ zq/2 (1 + ǫn ) + Pf
≤
≤ Pf
1 + ǫn
V 1/2 (f )
(V̂nw )1/2

 1/2 w
n {Ĥn − H(f )}
+ ǫn
≤ Ef hn,L
V 1/2 (f )


  1/2 w
n {Ĥn − H(f )}
≤ Ef hn,L (Z) + ǫn + LdBL L
, L(Z)
V 1/2 (f )

≤ P |Z| ≤ zq/2 (1 + ǫn ) + L−1 + ǫn




+ L max (1, V −1/2 (f ) dBL L n1/2 (Ĥnw − H(f )) , N 0, V (f ) .

Since L ≥ 1 was arbitrary, we deduce from the first part of the theorem and
Lemma 11 in the online supplement that
lim sup sup

sup

2
= 0.
L≥1 L(2π)1/2


sup Pf In,q ∋ H(f ) −(1−q) ≤ inf

n→∞ q∈(0,1) k∈{k0∗ ,...,k1∗ } f ∈Fd,θ

The lower bound is obtained by a similar argument, omitted for brevity.
Acknowledgements: We thank the reviewers for constructive feedback
on an earlier draft. The second author is grateful to Sebastian Nowozin for
introducing him to this problem, and to Gérard Biau for helpful discussions.
References.
Beirlant, J., Dudewicz, E. J., Györfi, L., and Van der Meulen, E. C. (1997) Nonparametric
entropy estimation: an overview. Int. J. Math. Stat. Sci., 6, 17–39.
Berrett, T. B., Samworth, R. J. and Yuan, M. (2017) Supplementary material to ‘Efficient
multivariate entropy estimation via k-nearest neighbour distances’. Submitted.
Biau, G. and Devroye, L. (2015) Lectures on the Nearest Neighbor Method. Springer, New
York.
Cai, T. T. and Low, M. G. (2011) Testing composite hypotheses, Hermite polynomials
and optimal estimation of a nonsmooth functional. Ann. Statist., 39, 1012–1041.
Cressie, N. (1976) On the logarithms of high-order spacings. Biometrika, 63, 343–355.
Delattre, S. and Fournier, N. (2017) On the Kozachenko–Leonenko entropy estimator. J.
Statist. Plann. Inf., 185, 69–93.
El Haje Hussein, F. and Golubev, Y. (2009) On entropy estimation by m-spacing method.
J. Math. Sci., 163, 290–309.
Gao, W., Oh, S. and Viswanath, P. (2016) Demystifying fixed k-nearest neighbor information estimators. Available at arXiv:1604.03006.
Gibbs, A. L. and Su, F. E. (2002) On choosing and bounding probability metrics. Int.
Statist. Review, 70, 419–435.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

32

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

Goria, M. N., Leonenko, N. N., Mergel, V. V. and Novi Inverardi, P. L. (2005) A new
class of random vector entropy estimators and its applications in testing statistical
hypotheses. J. Nonparametr. Stat., 17, 277–297.
Hall, P. and Morton, S. C. (1993) On the estimation of entropy. Ann. Inst. Statist. Math.,
45, 69–88.
Ibragimov, I. A. and Khas’minskii, R. Z. (1991) Asymptotically normal families of distributions and efficient estimation. Ann. Statist., 19, 1681–1724.
Kozachenko, L. F. and Leonenko, N. N. (1987) Sample estimate of the entropy of a random
vector. Probl. Inform. Transm., 23, 95–101.
Kwak, N. and Choi, C. (2002) Input feature selection by mutual information based on
Parzen window. IEEE Trans. Pattern Anal. Mach. Intell., 24, 1667–1671.
Laurent, B. (1996) Efficient estimation of integral functionals of a density. Ann. Statist.,
24, 659–681.
Lepski, O., Nemirovski, A. and Spokoiny, V. (1999) On estimation of the Lr norm of a
regression function. Probab. Th. Rel. Fields, 113, 221–253.
Miller, E. G. and Fisher, J. W. (2003) ICA using spacings estimates of entropy. J. Mach.
Learn. Res., 4, 1271–1295.
Mnatsakanov, R. M., Misra, N., Li, S. and Harner, E. J. (2008) Kn -nearest neighbor
estimators of entropy. Math. Methods Statist., 17, 261–277.
Moon, K. R., Sricharan, K., Greenewald, K. and Hero, A. O. (2016) Nonparametric ensemble estimation of distributional functionals. https://arxiv.org/abs/1601.06884v2.
Paditz, L. (1989). On the analytical structure of the constant in the nonuniform version
of the Esseen inequality. Statistics, 20, 453–464.
Paninski, L. (2003) Estimation of entropy and mutual information. Neural Comput., 15,
1191–1253.
Paninski, L. and Yajima, M. (2008) Undersmoothed kernel entropy estimators. IEEE
Trans. Inf. Theory, 54, 4384–4388.
Shorack, G. R. and Wellner, J. A. (2009) Empirical Processes with Applications to Statistics. SIAM.
Singh, H., Misra, N., Hnizdo, V., Fedorowicz, A. and Demchuk, E. (2003) Nearest neighbor
estimates of entropy. Am. J. Math. Manag. Sci., 23, 301–321.
Singh, S. and Póczos, B. (2016) Analysis of k nearest neighbor distances with application
to entropy estimation. NIPS, 29, 1217–1225.
Sricharan, K., Wei, D. and Hero, A. O. (2013) Ensemble estimators for multivariate entropy estimation. IEEE Trans. Inf. Theory, 59, 4374–4388.
Tsybakov, A. B. and Van der Meulen, E. C. (1996) Root-n consistent estimators of entropy
for densities with unbounded support. Scand. J. Stat., 23, 75–83.
van der Vaart, A. W. (1998). Asymptotic Statistics. Cambridge University Press, Cambridge.
Vasicek, O. (1976) A test for normality based on sample entropy. J. Roy. Statist. Soc.,
Ser. B., 38, 54–59.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

arXiv: 1606.00304v3

SUPPLEMENTARY MATERIAL TO ‘EFFICIENT
MULTIVARIATE ENTROPY ESTIMATION VIA
K-NEAREST NEIGHBOUR DISTANCES’
By Thomas B. Berrett, Richard J. Samworth and Ming Yuan
Appendix. This is the supplementary material to Berrett, Samworth
and Yuan (2017), hereafter referred to as the main text.
A.4. Proofs of auxiliary results.

d
Proof of Proposition 9. Fix τ ∈ α+d
, 1 . We first claim that given
any ǫ > 0, there exists Aǫ > 0 such that a(δ) ≤ Aǫ δ−ǫ for all δ ∈ (0, γ]. To
see this, observe that there exists δ0 ∈ (0, γ] such that a(δ) ≤ δ−ǫ for δ ≤ δ0 .
But then

sup δǫ a(δ) ≤ max 1, γ ǫ a(δ0 ) ≤ γ ǫ δ0−ǫ ,
δ∈(0,γ]


d
which establishes the claim, with Aǫ := γ ǫ δ0−ǫ . Now choose ǫ = 13 τ − α+d

2d
d
, 1 . Then, by Hölder’s inequality, and since
and let τ ′ := τ3 + 3(α+d)
∈ α+d
ατ ′ /(1 − τ ′ ) > d,
Z
Z

′
τ
ǫ
f (x)τ dx
a f (x) f (x) dx ≤ Aǫ δ sup
sup
f ∈Fd,θ

f ∈Fd,θ

{x:f (x)<δ}

ǫ

Z

τ′

≤ Aǫ δ (1 + ν)

{x:f (x)<δ}
′

τ
α − 1−τ ′

(1 + kxk )
Rd

dx

1−τ ′

as δ ց 0, as required.

d
and τ ′ :=
For the second part, fix ρ > 0, set ǫ := 12 τ − α+d

d
α+d , 1 . Then, by Hölder’s inequality again,
sup

f ∈Fd,θ

Z

X

ρ
a f (x) f (x)τ dx ≤ Aǫ/ρ sup

f ∈Fd,θ

τ′

≤ Aǫ/ρ (1 + ν)

Z

Z

d
+ 2(α+d)
∈

′

f (x)τ dx

X
′

τ
α − 1−τ ′

(1 + kxk )
Rd

τ
2

→0

dx

1−τ ′

< ∞,

as required.

33
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

34

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

Proof of Lemma 10. (i) The lower bound is immediate from the fact
that hx (r) ≤ Vd kf k∞ r d for any r > 0. For the upper bound, observe that
by Markov’s inequality, for any r > 0,
Z
Z
µα (f )
f (y) dy ≥ 1 −
f (y) dy ≥
.
hx (kxk + r) =
rα
B0 (r)
Bx (kxk+r)

α (f ) 1/α
for s ∈ (0, 1).
The result follows on substituting r = µ1−s
(ii) We first prove this result in the case β ∈ (2, 4], giving the stated form
−β/d
/(d + β), and let y := Ca(f (x))β/2 s{s/f (x)}β/d .
of b1 (·). Let C := 4dVd
Now, by the mean value theorem, we have for r ≤ ra (x) that
hx (r) − Vd r d f (x) −

Vd
dVd
r d+2 ∆f (x) ≤ a(f (x))f (x)
r d+β .
2(d + 2)
2(d + β)

It is convenient to write
sx,y := s −

s1+2/d ∆f (x)
2/d

2(d + 2)Vd

f (x)1+2/d

+ y.

Then, provided sx,y ∈ (0, Vd rad (x)f (x)], we have
hx



1/d

sx,y
{Vd f (x)}1/d



−β/d

−2/d

a(f (x))dVd
Vd
∆f (x)
s1+2/d
−
s1+β/d .
≥ sx,y +
x,y
1+2/d
2(d + 2)f (x)
2(d + β)f (x)β/d x,y
Now, by our hypothesis, we know that

−2/d 2/d
s |∆f (x)| y
Vd
sup sup sup max
,
2(d + 2)f (x)1+2/d s
f ∈Fd,θ s∈Sn x∈Xn
 1/2 −2/d 2/d

Cn
d Vd
β/d
, CCn
≤ max
→0
2(d + 2)


as n → ∞. Hence there exists n1 = n1 (d, θ) ∈ N such that for all n ≥ n1 , all
f ∈ Fd,θ , s ∈ Sn and x ∈ Xn , we have
s1+2/d
1
(s1+2/d
− s1+2/d ) ≥ −
x,y
2(d + 2)
2d




−2/d
a(f (x))s2/d y
d1/2 Vd
+
.
s
2(d + 2)f (x)2/d

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

35

EFFICIENT ENTROPY ESTIMATION

Moreover, there exists n2 = n2 (d, θ) ∈ N such that for all n ≥ n2 , all s ∈ Sn ,
x ∈ Xn and f ∈ Fd,θ we have
|sx,y |1+β/d ≤ 2s1+β/d .
Finally, we can choose n3 = n3 (d, θ) ∈ N such that
max



2/d

(4−β)/d

Cn
4(d +

(4−β)/d
2)Vd

,

2d1/2 Cn
(d +

2/d
β)Vd

2/d

,

d3/2 Cn

2(d + 2)(d +

2/d
β)Vd



≤

d
d+β

and such that Cn ≤ (8d1/2 )−d Vd /2 for n ≥ n3 . It follows that for n ≥
max(n1 , n2 , n3 ) =: n∗ , for f ∈ Fd,θ , s ∈ Sn and for x ∈ Xn , we have that
sx,y ∈ (0, Vd rad (x)f (x)] and
hx



1/d

sx,y
{Vd f (x)}1/d



−s


−2/d
a(f (x))s2/d y
d1/2 Vd
da(f (x))s1+β/d
≥y−
+
−
β
2/d
β
s
2(d + 2)f (x)2/d
2d1/2 Vd f (x)2/d
(d + β)Vdd f (x) d


(4−β)/d
a(f (x))2−β/2
a(f (x))β/2 s1+β/d
s
C−
≥
4/d f (x)
f (x)β/d
4(d + 2)Vd

2/d
−β/d 
dVd
s
Ca(f (x))
−
≥ 0.
−
2/d f (x)
d+β
2d1/2 Vd
a(f (x))s1+2/d



The lower bound is proved by very similar calculations, and the result for
the case β ∈ (2, 4] follows. The general case can be proved using very similar
arguments, and is omitted for brevity.
A.5. Auxiliary results for the proof of Theorem 2. Recall the definition
of V (f ) given in the statement of Theorem 1.
For each d ∈ N and θ ∈ Θ and m ∈ N, we have

Lemma 11.

(i) supf ∈Fd,θ X f (x)| logm f (x)| dx < ∞;
(ii) inf f ∈Fd,θ V (f ) > 0;
R

Proof of Lemma 11. Fix d ∈ N and θ = (α, β, γ, ν, a) ∈ Θ.
(i) For ǫ ∈ (0, 1) and t ∈ (0, 1], we have
log

1
1
≤ t−ǫ .
t
ǫ

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

36

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

α
= 2d. Then, by Hölder’s inequality, for any
, so that α(1−mǫ)
Let ǫ = m(α+2d)
mǫ
f ∈ Fd,θ ,
Z
Z
 kf k 
∞
dx + 2m−1 | logm kf k∞ |
f (x)| logm f (x)| dx ≤ 2m−1
f (x) logm
f
(x)
X
X
Z
2m−1 kf kmǫ
∞
≤
f (x)1−mǫ dx + 2m−1 | logm kf k∞ |
ǫm
X
nZ
omǫ
2m−1 γ mǫ
α − 1−mǫ
1−mǫ
mǫ dx
≤
(1
+
kxk
)
(1
+
ν)
ǫm
X
 α d

α+d 
1
m Vd ν (α + d)
m−1
m
,
+2
max log γ , m log
α
αα dd

where the bound on logm kf k∞ comes from (13) in the main text.
(ii) Now define


1
Ad,θ := max sup |H(f )| , − log inf kf k∞ , 1
f ∈Fd,θ
2
f ∈Fd,θ
and the set Sd,θ := {x ∈ X : e−4Ad,θ ≤ f (x) ≤ e−2Ad,θ }. For f ∈ Fd,θ , x ∈
Sd,θ and y ∈ Bx ({8d1/2 a(e−4Ad,θ )}−1/(β∧1) ) we have by Lemma 12 below
that
|f (y) − f (x)| ≤

(30)

15d1/2
a(e−4Ad,θ )e−2Ad,θ ky − xkβ∧1 .
7

By the continuity of f , there exists x0 ∈ Sd,θ such that f (x0 ) = 12 e−2Ad,θ (1 +
e−2Ad,θ ). Thus, by (30), we have that Bx0 (rd,θ ) ⊆ Sd,θ , where
rd,θ :=
Hence

n 7(1 − e−2Ad,θ ) o1/(β∧1)
1
∧
.
−4A
−4A
d,θ )
d,θ )}1/(β∧1)
30d1/2 a(e
8d1/2 a(e

d
V (f ) = Ef [{log f (X1 ) + H(f )}2 ] ≥ A2d,θ Pf (X1 ∈ Sd,θ ) ≥ A2d,θ e−4Ad,θ Vd rd,θ
,

as required.
The following auxiliary result provides control on deviations of the density
arising from the smoothness condition of our Fd,θ classes.
Lemma 12.
 For θ = (α, β, γ, ν, a) ∈ Θ, m := ⌈β⌉ − 1, f ∈ Fd,θ and
y ∈ Bx ra (x) , we have, for multi-indices t with |t| ≤ m, that

∂f t (y) ∂f t (x)
15d1/2
a
f
(x)
f (x)ky − xkmin(β−|t|,1) .
−
≤
∂xt
∂xt
7

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

37

EFFICIENT ENTROPY ESTIMATION

Proof of Lemma 12. If |t| = m then the result follows immediately
from the definition of Fd,θ . Henceforth, therefore, assume that m ≥ 1 and
|t| ≤ m − 1. Writing |||·|||
 here for the largest absolute entry of an array, we
have for y ∈ Bx ra (x) that
∂f t (z)
∂f t (y) ∂f t (x)
−
≤
ky
−
xk
sup
∇
∂xt
∂xt
∂xt
z∈Bx (ky−xk)

≤ ky − xkkf (|t|+1) (x)k + d1/2 ky − xk

sup

f (|t|+1) (z) − f (|t|+1) (x)

z∈Bx (ky−xk)
m−|t|

≤

X

d(ℓ−1)/2 ky − xkℓ kf (|t|+ℓ) (x)k

ℓ=1

+ dm/2 ky − xkm

sup

f (m) (z) − f (m) (x)

z∈Bx (ky−xk)


≤ a(f (x))f (x)ky − xk
≤

1
+ dm/2 ky − xkβ−1
1/2
1 − d ky − xk

15d1/2
a(f (x))f (x)ky − xk,
7



as required.
Lemma 13.
have that

Under the conditions of Theorem 1 in the main text, we
sup Ef [{Ṽnw − V (f )}2 ] → 0.

sup

k∈{k0∗ ,...,k1∗ } f ∈Fd,θ

Proof of Lemma 13. For w = (w1 , . . . , wk )T ∈ W (k) , write supp(w) :=
{j : wj 6= 0}. Then
|Ef Ṽnw − V (f )|
≤

k
X

wj Ef log2 ξ(j),1 −

j=1

≤ kwk1 max

j∈supp(w)

Z

X

f log2 f + Ef {(Ĥnw )2 } − H(f )2

Ef log2 ξ(j),1 −

Z

X

f log2 f + Varf Ĥnw + |(Ef Ĥnw )2 −H(f )2 |.

Thus, by Theorem 1 in the main text, (18) in the proof of that result and
Lemma 11(i), we have that supk∈{k0∗ ,...,k1∗ } supf ∈Fd,θ |Ef Ṽnw − V (f )| → 0.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

38

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

Now,
Varf Ṽnw ≤

kwk21
n

max Varf log2 ξ(j),1

j∈supp(w)

+ kwk21

(31)

max

j,ℓ∈supp(w)

Covf (log2 ξ(j),1 , log2 ξ(ℓ),2 ) .

1/2 log1/2 n) ∨ 0 and a+ := (j + 3j 1/2 log 1/2 n) ∧ (n − 1).
Let a−
n,j := (j − 3j
n,j
Mimicking arguments in the proof of Theorem 1, for any m ∈ N, j ∈ supp(w)
and ǫ > 0,

Ef logm (ξ(j),1 f (X1 ))


Z ∞
Z
−1
d
m Vd (n − 1)f (x)hx (s)
log
f (x)
=
Bj,n−j (s) ds dx
eΨ(j)
0
X
+


Z an,j
n−1
m (n − 1)s
Bj,n−j (s) ds
= a− log
n,j
eΨ(j)
n−1
α

 β/d

k α+d −ǫ
k
m−1
n,
+ O max β/d log
→ 0,
α
n
n α+d −ǫ

uniformly for j ∈ supp(w), k ∈ {k0∗ , . . . , k1∗ } and f ∈ Fd,θ . Moreover, by
Cauchy–Schwarz, we can now show, for example, that
Ef log4 ξ(j),1 = Ef [{log(ξ(j),1 f (X1 )) − log f (X1 )}4 ] → Ef log4 f (X1 )
uniformly for j ∈ supp(w), k ∈ {k0∗ , . . . , k1∗ } and f ∈ Fd,θ . The result follows
upon noting that we may use a similar approach for the covariance term
in (31) to see that supk∈{k0∗ ,...,k1∗ } supf ∈Fd,θ Var Ṽnw → 0.
A.6. Proof of Proposition 5.
Proof of Proposition 5. In each of the three examples, we provide
θ = (α, β, γ, ν, a) ∈ Θ such that f ∈ Fd,θ . In fact, β > 0 may be chosen
arbitrarily in each case.


(i) We may choose any α > 0, and then set ν = d2α/2−1 Γ α2 + d2 /Γ 1+ d2 .
We may also set γ = (2π)−d/2 . It remains to find a ∈ A such that (6) holds.
2
dr −y 2 /2
for the rth Hermite polynomial, and
Write Hr (y) := (−1)r ey /2 dy
re
note that |Hr (y)| ≤ pr (|y|), where pr is a polynomial of degree r with nonnegative coefficients. Using multi-index notation for partial derivatives, if
t = (t1 , . . . , td ) ∈ {0, 1, . . . , }d with |t| := t1 + . . . + td , we have
d

d

j=1

j=1

Y
Y
∂f t (x)
ptj (kxk) ≤ f (x)q|t| (kxk),
|Htj (xj )| ≤ f (x)
= f (x)
t
∂x
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

39

for some polynomial qr of degree r, with non-negative coefficients. It follows
that if y ∈ Bx◦ (1), then for any β > 0 with m = ⌈β⌉ − 1,
dm/2
∂f t (x) ∂f t (y)
kf (m) (x) − f (m) (y)k
≤
max
−
f (x)ky − xkβ−m
f (x)ky − xkβ−m t:|t|=m ∂xt
∂xt
≤

d(m+1)/2
f (x)

≤ d(m+1)/2

max

sup

t:|t|=m+1 w∈B0 (1)

∂f t (x + w)
∂xt

f (x + w)qm+1 (kx + wk)
f (x)
w∈B0 (1)
sup

≤ d(m+1)/2 ekxk qm+1 (kxk + 1).
Similarly,
kf (r) (x)k
≤ dm/2 max qr (kxk).
r=1,...,m
r=1,...,m
f (x)

 1/2
Write g(δ) := −2 log δ(2π)d/2
and define a ∈ A by setting a(δ) :=
max{1, ã(δ)}, where


m/2
1/2 kxk
ã(δ) := d
sup max max qr (kxk) , d e qm+1 (kxk + 1)
max

r=1,...,m

x:kxk≤g(δ)

m/2

=d

max





 1/2 g(δ)
max qr g(δ) , d e qm+1 g(δ) + 1 .

r=1,...,m

Then supx:f (x)≥δ Mf,a,β (x) ≤ a(δ) and a(δ) = o(δ−ǫ ) for every ǫ > 0, so (6)
holds.
(ii) We may choose any α < ρ, and set


α
d
α/2 Γ ρ−α
α/2−1 Γ 2 + 2 (ρ/2)
2


ν = d2
.
Γ 2ρ
Γ 1 + d2
We may also set γ =



ρ
+ d2
2
Γ(ρ/2)ρα/2 π d/2

Γ

. To verify (6) for suitable a ∈ A, we note

by induction, that if t = (t1 , . . . , td ) ∈ {0, 1, . . . , }d with |t| := t1 + . . . + td ,
then
f (x)q|t| (kxk)
∂f t (x)
,
≤
t
∂x
(1 + kxk2 /ρ)|t|
where qr is a polynomial of degree r with non-negative coefficients. Thus,

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

40

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

similarly to the Gaussian example, for any β > 0 with m = ⌈β⌉ − 1,
kf (m) (x) − f (m) (y)k
f (x)ky − xkβ−m
x∈Rd y∈Bx◦ (1)
sup

sup

≤ d(m+1)/2 sup
x∈Rd

f (x + w)qm+1 (kx + wk)
(1)
=: Ad,m,ρ ,
2 /ρ)m+1
f
(x)(1
+
kxk
w∈B0 (1)
sup

(1)

say, where Ad,m,ρ ∈ [0, ∞). Similarly,
kf (r) (x)k
qr (kxk)
(2)
≤ dm/2 sup max
=: Ad,m,ρ ,
2 /ρ)r
r=1,...,m
r=1,...,m
f
(x)
(1
+
kxk
d
d
x∈R
x∈R
sup max

(2)

say, where Ad,m,ρ ∈ [0, ∞). Now defining a ∈ A to be the constant function
(2)

(1)

a(δ) := max{1, Ad,m,ρ , Ad,m,ρ },
we again have that supx:f (x)≥δ Mf,a,β (x) ≤ a(δ), so (6) holds.
(iii) We may take any α > 0 and ν = 1, γ = 3. To verify (6), fix β > 0,
set m := ⌈β⌉ − 1, and define a ∈ A by

 
2(m+1) 1
a(δ) := Am max 1 , log
,
δ

for some Am ≥ 1 depending only on m. Then, by induction, we find that for
′ > 0 depending only on m, and x ∈ (−1, 1)
some constants A′m , Bm


A′m+1 f (y)
A′r
,
sup
Mf,a,β (x) ≤ max max
r=1,...,m (1 − x2 )2r y:0<|y−x|≤ra (x) (1 − y 2 )2(m+1) f (x)
≤

′

Bm+1
≤ a f (x) ,
2
2(m+1)
(1 − x )

provided Am in the definition of a is chosen sufficiently large. Hence (6)
again holds.
A.7. Proof of Proposition 6.
Proof of Proposition 6. To deal with the integrals over Xnc , we first
observe that by (13) in the main text there exists a constant Cd,f > 0,
depending only on d and f , such that
Z 1
Z
Bk,n−k (s) log ux,s ds dx
f (x)
Xnc

0

(32)

≤ Cd,f

Z

Xnc



f (x) log n + log 1 +

kxk
1/α

µα (f )




dx = O max{qn log n, qn1−ǫ } ,

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

41

EFFICIENT ENTROPY ESTIMATION

for every ǫ > 0. Moreover,
Z
f (x) log f (x) dx = O(qn1−ǫ ),
(33)
Xnc

for every ǫ > 0. Now, a slightly simpler argument than that used in the
proof of Lemma 10(ii) in the main text gives that for r ∈ (0, rx ], we have
|hx (r) − Vd f (x)r d | ≤

dVd
C (x)r d+β̃ .
d + β̃ n,β̃

We deduce, again using a slightly simplified version of the argument in
Lemma 10(ii) in the main text, that there exists n0 ∈ N such that for
an
] and x ∈ Xn , we have
n ≥ n0 , s ∈ [0, n−1
(34)

d
Vd f (x)h−1
x (s)

−s ≤

−β̃/d

2dVd

d + β̃

s1+β̃/d

Cn,β̃ (x)
f (x)1+β̃/d

s
≤ .
2

It follows from (32), (33), (34) and an almost identical argument to that
leading to (15) in the main text that for every n ≥ n0 and ǫ > 0,


Z an
Z
d
n−1
Vd f (x)h−1
x (s)
ds dx
Bk,n−k (s) log
|Ef (Ĥn ) − H| ≤
f (x)
s
0
Xn

+ O max{qn1−ǫ , qn log n, n−1 }
Z an
Z
d
n−1
Vd f (x)h−1
x (s) − s
ds dx
Bk,n−k (s)
f (x)
≤2
s
Xn
0

+ O max{qn1−ǫ , qn log n, n−1 }
Z C (x)
−β̃/d B

4dVd
k+β̃/d,n−k
n,β̃
≤
dx + O max{qn1−ǫ , qn log n, n−1 } ,
β̃/d
Bk,n−k
d + β̃
Xn f (x)
as required.

A.8. Completion of the proof of Lemma 7. To prove Lemma 7, it remains
to bound several error terms arising from arguments that approximate the
variance of the unweighted Kozachenko–Leonenko estimator Ĥn , and then
to show how these arguments may be adapted to yield the desired asyptotic
expansion for Var(Ĥnw ).
A.8.1. Bounds on S1 , . . . , S5 . To bound S1 : By similar methods to those
used to bound R1 in the proof of Lemma 3 in the main text, it is straightforward to show that for every ǫ > 0, we have
 α −ǫ 
Z 1
Z
k α+d
2
.
Bk,n−k (s) log ux,s ds dx = O
f (x)
S1 =
α
n α+d −ǫ
0
Xnc
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

42

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

To bound S2 : For every ǫ > 0, we have that
Z 1
Z
Bk,n−k (s) log2 ux,s ds dx = o(n−(3−ǫ) ),
f (x)
S2 =
an
n−1

Xn

by very similar arguments to those used to bound R2 in the proof of Lemma 3
in the main text.
To bound S3 : We have


(n − 1)s
log2 ux,s − log2 Ψ(k)
e
f (x)





d 
d
Vd f (x)h−1
Vd f (x)h−1
(n − 1)s
x (s)
x (s)
+ log
= 2 log Ψ(k)
log
.
s
s
e
f (x)
It therefore follows from Lemma 10(ii) in the main text that for every ǫ > 0,
S3 =

Z

f (x)
Xn

Z

an
n−1

0


 β/d
k
= O max β/d
n




(n − 1)s
2
2
Bk,n−k (s) log ux,s − log
ds dx
eΨ(k) f (x)
α

k α+d −ǫ
log n ,
.
α
n α+d −ǫ

To bound S4 : A simplified version of the argument used to bound R4 in
Lemma 3 of the main text shows that for every ǫ > 0,


Z 1
Z
(n − 1)s
f (x)
S4 =
Bk,n−k (s) log2 Ψ(k)
ds dx = o(n−(3−ǫ) ).
an
e
f
(x)
Xn
n−1
To bound S5 : Very similar arguments to those used to bound R1 in Lemma 3
in the main text show that for every ǫ > 0,
S5 =

Z

2

f (x) log f (x) dx = O
Xnc



α

k α+d −ǫ
α

n α+d −ǫ



.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

43

EFFICIENT ENTROPY ESTIMATION

A.8.2. Bounds on T1 , T2 and T3 . To bound T1 : Let B ∼ Beta(k − 1, n −
k − 1). By (13) in the main text, for every ǫ > 0,
Z ∞
Z
−
log(uf (x)) d(F̃n,x − Fn,x
)(u) dy dx
T11 :=
f (x)f (y) log f (y)
ũn,x,y
Xnc ×Xnc
Z
n−2
≤
f (x)f (y)| log f (y)|
n − k − 1 Xnc ×Xnc
Z 1
(n − 2)s
log(ux,s f (x)) Bk−1,n−k−1 (s) 1 −
ds dy dx
k−1
0


 
Z
1
(n − 2)B
1
1−
f (x)f (y)| log f (y)| E log + log
.
B
1−B
k−1
Xnc ×Xnc




kxk
(n − 2)B
+ log n + | log f (x)| + log 1 + 1/α
dy dx
E 1−
k−1
µα (f )
 − 1 + 2α −ǫ 
k 2 α+d
,
=o
2α
n α+d −ǫ
where we used the Cauchy–Schwarz inequality and elementary properties of
beta random variables to obtain the final bound.
Now let
an d
Vd (n − 1)h−1
x ( n−1 )
∗
,
un (x) := ux,an /(n−1) =
eΨ(k)
and consider
Z ∞
Z Z
−
T12 :=
log(uf (x)) d(F̃n,x − Fn,x
)(u) dy dx .
f (x)f (y) log f (y)
Xnc

ũn,x,y

Xn

If ũn,x,y ≥ u∗n (x), then by very similar arguments to those used to bound R1
and R2 (cf. (13) and (14) in the main text), together with Cauchy–Schwarz,
Z ∞
−
log(uf (x)) d(F̃n,x − Fn,x
)(u)
ũn,x,y

≤

(35)

.

Z

1

an
n−1

| log(ux,s f (x))|{Bk−1,n−k (s) + Bk,n−k−1 (s)} ds


log n + | log f (x)| + log 1 +
n3−ǫ

kxk

1/α
µα (f )



,

for every ǫ > 0. On the other hand, if ũn,x,y < u∗n (x), then kx − yk <
rn,u∗n (x) + rn,u∗n (y) , where we have added the rn,u∗n (y) term to aid a calculation
later in the proof. Define the sequence

−1
ρn := cn log1/d (n − 1) .
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

44

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

From Lemma 10(ii) in the main text,
sup rn,u∗n(y) = sup

y∈Xn

y∈Xn

h−1
y





 a 
k log n 1/d
k log n 1/d
n
. sup
= o(ρn ).
≤
n−1
nδn
y∈Xn nf (y)

Now suppose that x ∈ Xnc and y ∈ Xn satisfy ky − xk ≤ ρn . Choose n0 ∈ N
large enough that rn,u∗n (y) ≤ ρn /2 for all y ∈ Xn , and that log(n − 1) ≥
max{(3/2)d (8d1/2 )d/β , 12Vd−1 2d } for all n ≥ n0 and k ∈ {k0∗ , . . . , k1∗ }. Then
when β ∈ (0, 1] and n ≥ n0 , using the fact that Bx (ρn /2) ⊆ By (3ρn /2), we
have
Z
f (w) dw ≥ Vd f (y)(ρn /2)d − Vd a(f (y))f (y)(ρn /2)d (3ρn /2)β
Bx (ρn /2)

(36)

an
1
.
≥ Vd f (y)(ρn /2)d {1 − (3cn ρn /2)β } ≥ Vd (ρn /2)d δn ≥
2
n−1

Hence, for all n ≥ n0 , x ∈ Xnc , y ∈ Xn with ky−xk ≤ ρn and k ∈ {k0∗ , . . . , k1∗ },
rn,u∗n(x) + rn,u∗n (y) ≤ ρn .

(37)

On other hand, suppose instead that x ∈ Xnc and ρ∗x := inf y∈Xn ky −xk ≥ ρn .
Since Xn is a closed subset of Rd , we can find y ∗ ∈ Xn such that ky ∗ −xk = ρ∗x ,
and set x̃ := ρρn∗ x + 1 − ρρn∗ y ∗ . Then kx̃ − y ∗ k = ρn , so from (36), we
x
x
have rn,u∗n (x̃) ≤ ρn /2 for n ≥ n0 and k ∈ {k0∗ , . . . , k1∗ }. Since Bx̃ (ρn /2) ⊆
Bx (ρ∗x − ρn /2), we deduce that rn,u∗n (x) ≤ ρ∗x − ρn /2 and
{y ∈ Xn : kx − yk < rn,u∗n (x) + rn,u∗n (y) } = ∅

(38)

for n ≥ n0 and k ∈ {k0∗ , . . . , k1∗ }. But for n ≥ n0 ,
(39)

sup

sup

x∈Xnc y∈Xn :ky−xk≤ρn

1
15d1/2
1
|f (x) − f (y)| ≤
(cn ρn )β < ,
f (y)
7
2

so that if x ∈ Xnc , y ∈ Xn and kx − yk ≤ ρn , then f (y) < 2δn for n ≥ n0 and
k ∈ {k0∗ , . . . , k1∗ }.
It therefore follows from (35), (37), (38), (39) and the argument used to

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

45

EFFICIENT ENTROPY ESTIMATION

bound T11 that for each ǫ > 0 and n ≥ n0 ,
Z Z
f (x)f (y)| log f (y)|1{kx−yk<rn,u∗ (x) +rn,u∗ (y) }
T12 ≤
n
n
Xnc Xn
Z ∞
−
| log(uf (x))| d(F̃n,x − Fn,x
)(u) dy dx + o(n−2 )
0
Z Z
f (x)f (y)| log f (y)|
≤
Xnc y:f (y)<2δn
Z ∞
−
| log(uf (x))| d(F̃n,x − Fn,x
)(u) dy dx + o(n−2 )
=o



k

0
2α
− 12 + α+d
−ǫ 
2α

n α+d −ǫ

.

Finally for T1 , we define
Z Z
T13 :=
 f (x)f (y) log f (y)
rn,1 dn
Xn

Bxc

f (x)1/d

Z

∞

ũn,x,y


−
)(u) dy dx .
log uf (x) d(F̃n,x − Fn,x

By Lemma 10(ii) in the main text, we can find n1 ∈ N such that for n ≥ n1 ,
d
k ∈ {k0∗ , . . . , k1∗ }, x ∈ Xn and s ≤ an /(n − 1), we have Vd f (x)h−1
x (s) ≤ 2s.
rn,1 dn
c
∗
∗
Thus, for n ≥ n1 , k ∈ {k0 , . . . , k1 }, x ∈ Xn and y ∈ Bx ( f (x)1/d ),
ũn,x,y ≥

2an
24 log n
≥
≥ u∗n (x).
f (x)
f (x)eΨ(k)

Thus, from (35), T13 = O(n−2 log n). We conclude that for every ǫ > 0,
|T1 | ≤ T11 + T12 + T13 = o



1

2α

k− 2 + α+d −ǫ
2α

n α+d −ǫ



.

To bound T2 : Fix x ∈ Xn and z ∈ B0 (dn ). Choosing n2 ∈ N large enough
r dn
≤ (8d1/2 )−1/β c−1
that n,1
1/d
n for n ≥ n2 , we have by Lemma 12 that
δn

f (y)
1
−1 ≤

f (x)
2
rn,1 dn

sup
y∈Bx

1/d
δn

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

46

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

for n ≥ n2 , k ∈ {k0∗ , . . . , k1∗ }. Also, for all n ≥ n2 , k ∈ {k0∗ , . . . , k1∗ }, we have
f (yx,z ) log f (yx,z ) − f (x) log f (x)
≤ f (yx,z )| log(f (yx,z )/f (x))| + | log f (x)||f (yx,z ) − f (x)|
≤ a(f (x))f (x)kyx,z − xkβ {| log f (x)| + 4}.
Moreover, by arguments used to bound T11 ,


Z ∞
(n − 2)B
−
log(uf (x)) d(F̃n,x − Fn,x
)(u) . E log(B) 1 −
k−1
kzkd /f (x)



(n − 2)B
kxk
,
E 1−
+ log n + | log f (x)| + log 1 + 1/α
k−1
µα (f )
where B ∼ Beta(k − 1, n − k − 1). It follows that for every ǫ > 0,
Z Z
eΨ(k)
{f (yx,z ) log f (yx,z ) − f (x) log f (x)}
T2 =
Vd (n − 1) Xn B0 (dn )
Z ∞
−
log(uf (x)) d(F̃n,x − Fn,x
)(u) dz dx
kzkd /f (x)

α
−ǫ
α+d

k
k1/2
kβ/d
max
=O
,
log2+β/d n
α
−ǫ
β/d
n
n
n α+d





.

To bound T3 : Note that by Fubini’s theorem,
Z
Z ∞
Z
−
log(uf (x)) d(F̃n,x − Fn,x
)(u) dz dx
f (x) log f (x)
d
B0 (dn )

Xn

= Vd
= Vd

Z

Z

kzk
f (x)

f (x) log f (x)

0

Xn

f (x) log f (x)
Xn

Z

Z

0

∞

−
uf (x) log(uf (x)) d(F̃n,x − Fn,x
)(u) dx

u∗n (x)

−
uf (x) log(uf (x)) d(F̃n,x − Fn,x
)(u) dx

+ O(n−(3−ǫ) ),

for every ǫ > 0, where the order of the error term follows from the same
argument used to obtain (35) and Lemma 10(i). Thus, for every ǫ > 0,
Z an 
Z
n−1
Vd f (x)hx−1 (s)d
k−1
T3 =
f (x) log f (x)
log(ux,s f (x))
n − k − 1 Xn
s
0




(n − 1)s
(n − 2)s
ds dx + O(n−(3−ǫ) )
− log
Bk,n−k−1 (s) 1 −
Ψ(k)
k
−
1
e
 1/2

 α −ǫ
k
kβ/d
k α+d
=O
,
log n .
max
α
n
n α+d −ǫ nβ/d
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

47

A.8.3. Bounds on U1 and U2 . To bound U1 : Using Lemma 10(i) and (13)
in the main text as in our bounds on T11 we have that for every ǫ > 0,
Z u∗n (x)
Z

−
U11 :=
log uf (x) d(Fn,x
− Fn,x )(u) dx
f (x)
Xnc

≤

Z

f (x)

Xnc

0

Z

an
n−1

(n − 1)s − k
ds dx
n−k−1
 1 + α −ǫ 
k 2 α+d
.
=o
α
n1+ α+d −ǫ

| log(ux,s f (x))|Bk,n−k−1 (s)

0

(40)

Moreover, using arguments similar to those used to bound R2 in the proof
of Lemma 3 in the main text, for every ǫ > 0,
Z ∞
Z

−
(41) U12 :=
log uf (x) d(Fn,x
− Fn,x )(u) dx = o(n−(3−ǫ) ).
f (x)
X

u∗n (x)

From (40), and (41), we have for every ǫ > 0 that
 1 + α −ǫ 
k 2 α+d
.
|U1 | ≤ U11 + U12 = o
α
n1+ α+d −ǫ

To bound U2 : By Lemma 10(ii) and letting B ∼ Beta(k + β/d, n − k − 1), we
have that for every ǫ > 0,
Z an
Z
n (n − 1)s − k o
 V f (x)h−1 (s)d 
n−1
d
x
Bk,n−k−1 (s)
ds dx
U21 :=
f (x)
log
s
n−k−1
Xn
0

Z
kβ/d
(n − 1)B − k
. β/d E
a(f (x))f (x)1−β/d dx
n−k−1
n
Xn
α
 β/d
 1/2
−ǫ 
α+d
k
k
k
max β/d ,
=O
.
α
n
n
n α+d −ǫ
Moreover, we can use similar arguments to those used to bound R4 in the
proof of Lemma 3 in the main text to show that for every ǫ > 0,




Z 1
Z
(n − 1)s − k
(n − 1)s
Bk,n−k−1(s)
U22 :=
ds dx
f (x)
log
an
n−k−1
eΨ(k)
Xn
n−1
= o(n−(3−ǫ) ).
We deduce that for every ǫ > 0,
|U2 | ≤ U21 + U22

α

 β/d
k α+d −ǫ
k1/2
k
.
=O
max β/d ,
α
n
n
n α+d −ǫ



imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

48

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

A.8.4. Bounds on W1 , . . . , W4 . To bound W1 : We partition the region
([lx , vx ] × [ly , vy ])c into eight rectangles as follows:



c
[lx , vx ] × [ly , vy ] = [0, lx ) × [0, ly ) ∪ [0, lx ) × [ly , vy ] ∪ [0, lx ) × (vy , ∞)



∪ [lx , vx ] × [0, ly ) ∪ [lx , vx ] × (vy , ∞) ∪ (vx , ∞) × [0, ly )


∪ (vx , ∞) × [ly , vy ] ∪ (vx , ∞) × (vy , ∞) .

Recall our shorthand h(u, v) = log(uf (x)) log(vf (y)). By Lemma 10(i) and
the Cauchy–Schwarz inequality, as well as very similar arguments to those
used to bound R2 in the proof of Lemma 3 in the main text, we can bound
the contributions from each rectangle individually, to obtain that for every
ǫ > 0,
Z
Z
h(u, v) d(Fn,x,y − Fn,x Fn,y )(u, v) dx dy
f (x)f (y)
W1 =
([lx ,vx ]×[ly ,vy ])c

X ×X

= o(n−(9/2−ǫ) ).

To bound W2 : We have
Z
Z
f (x)f (y)
W2 =

lx

X ×X

We write Ba,b,c :=
(42)

vx

Z

vy

h(u, v) d(Gn,x,y − Fn,x Fn,y )(u, v) dx dy +
ly

Γ(a)Γ(b)Γ(c)
Γ(a+b+c) ,

1
.
n

and, for s, t > 0 with s + t < 1, let
sa−1 tb−1 (1 − s − t)c−1
Ba,b,c

Ba,b,c (s, t) :=

denote the density of a Dirichlet(a, b, c) random vector at (s, t). For a, b >
+
−1, writing In := [a−
n /(n − 1), an /(n − 1)], let
Z
(n)
sk+a−1 (1 − s)n−k−1 ds,
Bk+a,n−k :=
In

(n)
Bk+a,n−k (s)

(n)

Bk+a,k+b,n−2k−1
(n)
Bk+a,k+b,n−2k−1 (s, t)

k+a−1

(n)

:= s
Z
:=

(1 − s)n−k−1 /Bk+a,n−k

:= s

t

sk+a−1 tk+b−1 (1 − s − t)n−2k−2 ds dt

In ×In

k+a−1 k+b−1

(n)

(1 − s − t)n−2k−2 /Bk+a,k+b,n−2k−1 .

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

49

EFFICIENT ENTROPY ESTIMATION

Then by the triangle and Pinsker’s inequalities, and Beta tail bounds similar
to those used previously, we have that
Z
Bk+a,k+b,n−2k−1 (s, t) − Bk+a,n−k (s)Bk+b,n−k (t) ds dt
In ×In
(n)
Bk+a,k+b,n−2k−1

(n)

−1 +

(n)

Bk+a,n−k Bk+b,n−k

−1
Bk+a,k+b,n−2k−1
Bk+a,n−k Bk+b,n−k
1/2
 Z

 B(n)
(n)
k+a,k+b,n−2k−1 (s, t)
ds dt
Bk+a,k+b,n−2k−1 (s, t) log (n)
+ 2
(n)
In ×In
Bk+a,n−k (s)Bk+b,n−k (t)
 Z 1 Z 1−t


1/2
Bk+a,k+b,n−2k−1 (s, t)
= 2
Bk+a,k+b,n−2k−1(s, t) log
ds dt
Bk+a,n−k (s)Bk+b,n−k (t)
0
0
≤

+ o(n−2 )



Γ(n + a + b − 1)Γ(n − k)2 
+ (n − 2k − 2)ψ(n − 2k − 1)
Γ(n − 2k − 1)Γ(n + a)Γ(n + b)
− (n − k − 1){ψ(n + b − k − 1) + ψ(n + a − k − 1)}
1/2
+ o(n−2 )
+ nψ(n + a + b − 1)

= 21/2 log



(43)
k
= {1 + o(1)}.
n

As a first step towards bounding W2 note that
Z vx Z vy
Z
h(u, v) d(Gn,x,y − Fn,x Fn,y )(u, v) dx dy
f (x)f (y)
W21 :=
ly
lx
Xn ×Xn
Z
Z
log(ux,s f (x)) log(uy,t f (y))
f (x)f (y)
=
In ×In
Xn ×Xn

Bk,k,n−2k−1(s, t) − Bk,n−k (s)Bk,n−k (t) ds dt dx dy

 

Z
Z
(n − 1)s
(n − 1)t
log
f (x)f (y)
=
log
eΨ(k)
eΨ(k)
In ×In
Xn ×Xn

Bk,k,n−2k−1(s, t) − Bk,n−k (s)Bk,n−k (t) ds dt dx dy + W211

(44)

α


1
k α+d −ǫ
= − + O 1+ α −ǫ + O(n−2 ) + W211 ,
n
n α+d

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

50

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

for every ǫ > 0. But, by Lemma 10(ii) and (43), for every ǫ > 0,



 
Z
Z
d
Vd h−1
(n − 1)t
x (s) f (x)
2 log
|W211 | =
f (x)f (y)
log
s
eΨ(k)
In ×In
Xn ×Xn




d
d
Vd h−1
Vd h−1
y (t) f (y)
x (s) f (x)
+ log
log
s
t

Bk,k,n−2k−1 (s, t) − Bk,n−k (s)Bk,n−k (t) ds dt dx dy


Z
Z
d
Vd h−1
x (s) f (x)
log
≤2
f (x)f (y)
s
In
Xn ×Xn
h
log(n − 1) − Ψ(n − k − 1) + log(1 − s) Bk,n−k−1 (s)
i

− log(n − 1) − Ψ(n) Bk,n−k (s) ds dx dy

(45)

2α


 1+ 2β
k d k1+ α+d −ǫ
,
+ O max
2α
2β
n1+ d n1+ α+d −ǫ
α
 1/2
 β/d

k
k α+d −ǫ
k
=O
max β/d ,
.
α
n
n
n α+d −ǫ

Moreover, by Lemma 10(i) and (ii) and very similar arguments, for every
ǫ > 0,
Z vx Z vy
Z
h(u, v) d(Gn,x,y − Fn,x Fn,y )(u, v) dx dy
f (x)f (y)
W22 :=
Xn ×Xnc



W23
(46)

k

lx

α
1+ α+d
−ǫ



k

ly
α
−ǫ
α+d

kβ/d
1
, β/d , 1/2
n
k



= O 1+ α −ǫ max
α
−ǫ
α+d
α+d
n
n
Z vx Z vy
Z
h(u, v) d(Gn,x,y − Fn,x Fn,y )(u, v) dx dy
f (x)f (y)
:=
Xnc ×Xnc

=O



k

lx

2α
1+ α+d
−ǫ 
2α

n1+ α+d −ǫ

ly

.

Incorporating our restrictions on k, we conclude from (44), (45) and (46)
that for every ǫ > 0,
α
 1/2
 β/d

k
k
1
k α+d −ǫ
+ 2|W22 | + |W23 | = O
max β/d ,
.
|W2 | ≤ W21 +
α
n
n
n
n α+d −ǫ
To bound W3 : We write hu , hv and huv for the partial derivatives of h(u, v)
and write, for example, (hu F )(u, v) = hu (u, v)F (u, v). We find on integrating
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

51

EFFICIENT ENTROPY ESTIMATION

by parts that, writing F = Fn,x,y − Gn,x,y ,
Z vx Z vy
Z
(huv F (u, v)) du dv
(h dF )(u, v) −
ly
lx
[lx ,vx ]×[ly ,vy ]
Z vy
Z vx




(hv F )(lx , v) − (hv F )(vx , v) dv
(hu F )(u, ly ) − (hu F )(u, vy ) du +
=
ly

lx

(47)

+ (hF )(vx , vy ) + (hF )(lx , ly ) − (hF )(vx , ly ) − (hF )(lx , vy ).
Using standard binomial tail bounds as used to bound W1 together with (13)
in the main text we therefore see that for every ǫ > 0,
Z vxZ vy
Z
o
nZ vxZ vy
(huv F )(u, v) du dv dx dy
(h dF )(u, v)−
f (x)f (y)
W31 :=
X ×X

=−
(48)

Z

lx

Z
f (x)f (y)

X ×X

lx

ly
vx

(hu F )(u, vy ) du +
lx

Z

ly
vy



(hv F )(vx , v) dv dx dy
ly

+ o(n−(9/2−ǫ) ).
Now, uniformly for u ∈ [lx , vx ] and (x, y) ∈ X × X and for every ǫ > 0,


n − 2 k−1
F (u, vy ) = 1{kx−yk≤rn,u }
p
(1 − pn,x,u )n−k−1 + o(n−(9/2−ǫ) )
k − 1 n,x,u
Bk,n−k (pn,x,u )
+ o(n−(9/2−ǫ) )
= 1{kx−yk≤rn,u }
n−1
1
≤ 1{kx−yk≤rn,vx }
(49)
{1 + o(1)} + o(n−(9/2−ǫ) ).
(2πk)1/2
By (39) and the arguments leading up to it, we have
(50)

sup

x∈Xnc

sup
y∈Xn ∩Bx (rn,vx +rn,vy )

f (x)
− 1 → 0.
f (y)

We therefore have by (13) in the main text that, for every ǫ > 0,
(51)

Z

Xnc ×X

f (x)f (y)

Z

vx

(hu F )(u, vy ) du dy dx = O
lx



1

2α

k− 2 + α+d −ǫ
2α

n α+d −ǫ



.

Now, using Lemma 10(ii), for x ∈ Xn ,
(52)


max{|lx f (x) − 1|, |vx f (x) − 1|} . a(f (x))

k
nf (x)

β/d

+

log1/2 n
.
k1/2

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

52

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

We also need some control over vf (y). By (39) and the work leading up to
it, for n ≥ max(n0 , 5), x ∈ Xn and ky − xk ≤ rn,vx + rn,vy ,
o
n
15d1/2
(cn ρn )β δn ≥ δn /2 ≥ k/(n − 1).
f (y) ≥ 1 −
7

Thus a(f (y)) ≤ cβn and using (50) we may apply Lemma 10(ii) to the set
Xn′ = Xn ∪ {y : ky − xk ≤ rn,vx + rn,vy for some x ∈ Xn }.
From this and (50), for any x ∈ Xn and y ∈ Bx (rn,vx + rn,vy ),
(53)


max(|ly f (y) − 1|, |vy f (y) − 1|) . a(f (y))

k
nf (x)

β/d

+

log1/2 n
.
k1/2

Using (50) again, we have that a(f (yx,z )) . f (x)−ǫ for each ǫ > 0, uniformly
for x ∈ Xn and kzk ≤ {vx f (x)}1/d + {vy f (x)}1/d . From (49), (52) and (53)
we therefore have that
Z vx
Z
(hu F )(u, vy ) du dy dx
f (x)f (y)
lx
Xn ×X
Z
f (x)f (y)1{kx−yk<rn,vx } | log(vy f (y))| log(vx /lx ) dy dx
. k−1/2
Xn ×X

(54)

1

α

k1/2+2β/d log n k 2 + α+d −ǫ
,
,
= O max
α
n1+2β/d nk1/2 n1+ α+d −ǫ






for every ǫ > 0. By (48), (51) and (54) we therefore have that
(55)

W31

2α

k1/2+2β/d log n k−1/2+ α+d −ǫ
= O max
,
,
2α
n1+2β/d nk1/2
n α+d −ǫ






.

Finally, by (13) in the main text and (50), we have since F = 0 when
kx − yk > rn,u + rn,v that
(56)
W32 :=

Z

f (x)f (y)

Xnc ×X

Z

vx
lx

Z

vy

(huv F )(u, v) du dv dx dy = O

ly



2α

k α+d −ǫ
2α

n α+d −ǫ


.

Combining (55) and (56) we have that
W3 = W31 + W32

2α


 1/2+2β/d
log n k α+d −ǫ
k
.
,
, 2α
= O max
−ǫ
n1+2β/d nk1/2 n α+d

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

53

R
To bound W4 : Let p∩ := Bx (rn,u )∩By (rn,v ) f (y) dy and let (N1 , N2 , N3 , N4 ) ∼
Multi(n − 2, pn,x,u − p∩ , pn,y,v − p∩ , p∩ , 1 − pn,x,u − pn,y,v + p∩ ). Further, let
(1)
Fn,x,y
(u, v) := P(N1 + N3 ≥ k, N2 + N3 ≥ k),

so that
(1)
(Fn,x,y −Fn,x,y
)(u, v) = P(N1 + N3 = k − 1, N2 + N3 ≥ k)1{kx−yk≤rn,u }

+ P(N2 + N3 = k − 1, N1 + N3 ≥ k)1{kx−yk≤rn,v }

+ P(N1 + N3 = k − 1, N2 + N3 = k − 1)1{kx−yk≤rn,u ∧rn,v } .
 k−1
n−k−1 ≤ (2πk)−1/2 {1+o(1)}
Now P(N1 +N3 = k−1) = n−2
k−1 pn,x,u (1−pn,x,u )
and Fn,x,y (u, v) = Gn,x,y (u, v) if kx − yk > rn,u + rn,v , and so, by (52)
and (53), we have that
Z vx Z vy
Z
(Fn,x,y − Gn,x,y )(u, v)
du dv dx dy
f (x)f (y)
uv
ly
lx
Xn ×X
Z vx Z vy
Z
(1)
(Fn,x,y − Gn,x,y )(u, v)
du dv dx dy
f (x)f (y)
=
uv
ly
lx
Xn ×X
1
α



2β
1
log n k 2 + d k 2 + α+d −ǫ
+ O max
(57)
.
,
, 1+ α −ǫ
nk1/2 n1+ 2β
d
n α+d
(1)

We can now approximate Fn,x,y (u, v) by ΦΣ (k1/2 {uf (x) − 1}, k 1/2 {vf (x) −
1}) and Gn,x,y (u, v) by Φ(k1/2 {uf (x) − 1})Φ(k1/2 {vf (x) − 1}). To avoid
repetition, we focus on the former of these terms. To this end, for i =
3, . . . , n, let


Yi :=

so that

1{Xi ∈Bx (rn,u )}
,
1{Xi ∈By (rn,v )}



N1 + N3
. We also define
i=3 Yi = N + N
2
3

Pn




pn,x,u
µ := E(Yi ) =
pn,y,v


pn,x,u(1 − pn,x,u) p∩ − pn,x,u pn,y,v
V := Cov(Yi ) =
,
p∩ − pn,x,u pn,y,v pn,y,v (1 − pn,y,v )

When x ∈ Xn and y ∈ Bx◦ (rn,vx + rn,vy ) we have that, writing ∆ for the
symmetric difference and using (50), P(X1 ∈ Bx (rn,u )∆By (rn,v )) > 0 and
so V is invertible. We may therefore set Zi := V −1/2 (Yi − µ). Then by the
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

54

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

Berry–Esseen bound of Götze (1991), writing C for the set of closed, convex
subsets of R2 and letting Z ∼ N2 (0, I), there exists a universal constant
C2 > 0 such that


n
X
1
C2 E(kZ3 k3 )
Z
∈
C
−
P(Z
∈
C)
(58)
sup P
≤
.
i
(n − 2)1/2 i=3
(n − 2)1/2
C∈C
The distribution of Z3 depends on x, y, u and v, but, recalling the substitution y = yx,z as defined in (22) in the main text, we claim that for x ∈ Xn ,
y = yx,z ∈ Bx (rn,u + rn,v ), u ∈ [lx , vx ] and v ∈ [ly , vy ],
(59)

E(kZ3 k3 ) .

 n 1/2
.
kkzk

To establish this, note that for x ∈ Xn and ky − xk ≤ rn,vx + rn,vy , we have
by (50), (52) and (53) that ky − xk . ( nfk(x) )1/d . Thus, for v ∈ [ly , vy ], and
using Lemma 12, we also have that

(60)

|vf (x) − 1| ≤ max(|vy f (y) − 1|, |ly f (y) − 1|) + vy |f (y) − f (x)|
β/d

log1/2 n
k
.
+
. a(f (x) ∧ f (y))
nf (x)
k1/2

Now, by the definition of lx and vx ,
(61)


3k1/2 log1/2 n
max |pn,x,u − k/(n − 1)| , |pn,y,v − k/(n − 1)| ≤
n−1

for all x, y ∈ X and u ∈ [lx , vx ], v ∈ [ly , vy ]. Next, we bound | n−2
k p∩ − αz | for
x ∈ Xn and y = yx,z with kzk ≤ {vx f (x)}1/d + {vy f (x)}1/d . First suppose
that u ≥ v. We may write
Bx (rn,u )∩By (rn,v ) = {Bx (rn,v )∩By (rn,v )}∪[{Bx (rn,u )\Bx (rn,v )}∩By (rn,v )],
Rx
where this is a disjoint union. Writing Ia,b (x) := 0 Ba,b (s) ds for the regularised incomplete beta function and recalling that µd denotes Lebesgue
measure on Rd , we have



kx − yk2
d
µd Bx (rn,v ) ∩ By (rn,v ) = Vd rn,v I d+1 , 1 1 −
2
2
2
4rn,v


veΨ(k)
kzk2
=
I d+1 1 1 −
n − 1 2 ,2
4{vf (x)}2/d
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

and
αz = I d+1 , 1
2

2



55


kzk2
.
1−
4

Now,


d−1
d
1
(1 − r 2 /4) 2
r2
I d+1 , 1 1 −
≤
.
=
dr 2 2
4
B(d+1)/2,1/2
B(d+1)/2,1/2
Hence by the mean value inequality,

eΨ(k) αz
µd Bx (rn,v ) ∩ By (rn,v ) −
(n − 1)f (x)


eΨ(k) vkzk|1 − {vf (x)}−1/d |
αz
≤
+
|1 − vf (x)| .
n−1
B(d+1)/2,1/2
f (x)
It follows that for all x ∈ Xn , y ∈ Bx (rn,vx + rn,vy ) and v ∈ [ly , vy ],
Z

f (w) dw −
Bx (rn,v )∩By (rn,v )

eΨ(k) αz
n−1


β/d
k
k1/2 log1/2 n
k
+
. a(f (x) ∧ f (y))
n
nf (x)
n

using (60) and Lemma 12. We also have by (61) that
Z
f (w) dw ≤ pn,x,u − pn,x,v
{Bx (rn,u )\Bx (rn,v )}∩By (rn,v )


β/d
k
k
k1/2 log1/2 n
. a(f (x) ∧ f (y))
+
.
n
nf (x)
n

Thus, when x ∈ Xn , y = yx,z ∈ Bx (rn,vx + rn,vy ), u ∈ [lx , vx ], v ∈ [ly , vy ] and
u ≥ v,
(62)


β/d
k
n−2
log1/2 n
.
p∩ − αz . a(f (x) ∧ f (y))
+
k
nf (x)
k1/2

We can prove the same bound when v > u similarly, using (52), (60) and
Lemma 12. We will also require a lower bound on pn,x,u + pn,y,v − 2p∩ in the
region where Bx (rn,u ) ∩ By (rn,v ) 6= ∅, i.e., kzk ≤ {uf (x)}1/d + {vf (x)}1/d .
By the mean value theorem,


2−d/2
2
1/2
, 1 − I d+1 , 1 (1/2)
1 − I d+1 , 1 (1 − δ ) ≥ 2 δ max
2
2
2
2
B(d+1)/2,1/2
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

56

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

for all δ ∈ [0, 1]. Thus, for u ≥ v, with v ∈ [ly , vy ], x ∈ Xn , and y = yx,z with
kzk ≤ 2{vf (x)}1/d , by (60) we have,


µd Bx (rn,u ) ∩ By (rn,v )c ≥ µd Bx (rn,v ) ∩ By (rn,v )c



kkzk
kx − yk2
d
= Vd rn,v 1 − I d+1 , 1 1 −
.
&
2
2
2
4rn,v
nf (x)

d
When kzk > 2{vf (x)}1/d we simply have µd Bx (rn,v ) ∩ By (rn,v )c = Vd rn,v
and the same overall bound
applies. Moreover, the same lower bound for

µd By (rn,v ) ∩ Bx (rn,u )c holds when u < v, u ∈ [lx , vx ], x ∈ Xn , and y =
yx,z ∈ Bx (rn,vx + rn,vy ). We deduce that for all x ∈ Xn , y = yx,z ∈ Bx (rn,vx +
rn,vy ), u ∈ [lx , vx ] and v ∈ [ly , vy ],
(63)

pn,x,u + pn,y,v − 2p∩ ≥ max{pn,x,u − p∩ , pn,y,v − p∩ } &

k
kzk.
n

We are now in a position to bound E(kZ3 k3 ) above for x ∈ Xn , y = yx,z ∈
Bx (rn,vx + rn,vy ), u ∈ [lx , vx ], v ∈ [ly , vy ]. We write

 3

 3
3
−1/2 1 − pn,x,u
−1/2 1 − pn,x,u
E(kZ3 k ) = p∩ V
+ (pn,x,u − p∩ ) V
1 − pn,y,v
−pn,y,v
 3

−pn,x,u
+ (pn,y,v − p∩ ) V −1/2
1 − pn,y,v

 3
−1/2 pn,x,u
+ (1 − pn,x,u − pn,y,v + p∩ ) V
(64)
,
pn,y,v
and bound each of these terms in turn. First,

 3
−1/2 1 − pn,x,u
p∩ V
1 − pn,y,v

(65)

= p∩ |V |−3/2 {(1 − pn,x,u )(1 − pn,y,v )(pn,x,u + pn,y,v − 2p∩ )}3/2
(
)3/2
(1 − pn,x,u)(1 − pn,y,v )
= p∩
(p
−p∩ )(pn,y,v −p∩ )
p∩ − pn,x,upn,y,v + n,x,u
pn,x,u +pn,y,v −2p∩

3/2
pn,x,u + pn,y,v
1
≤ p∩ min
. n1/2 /k1/2 ,
,
|V |
p∩ − pn,x,u pn,y,v

using (61) and (62), and where we derive the final bound from the left hand
side of the minimum if kzk ≥ 1 and the right hand side if kzk < 1. Similarly,
(66)

 3
 n 1/2
−1/2 1 − pn,x,u
3/2
(pn,x,u −p∩ ) V
,
≤ (pn,x,u −p∩ )pn,y,v
|V |−3/2 .
−pn,y,v
kkzk
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

57

where we have used (63) for the final bound. By symmetry, the same bound
holds for the third term on the right-hand side of (64). Finally, very similar
arguments yield
(67)

(1 − pn,x,u − pn,y,v + p∩ ) V −1/2



pn,x,u
pn,y,v



3

. (k/n)3/2 .

Combining (65), (66) and (67) gives (59).
Writing ΦA (·) for the measure associated with the N2 (0, A) distribution
for invertible A, and φA for the corresponding density, we have by Pinsker’s
inequality and a Taylor expansion of the log-determinant function that
Z
φA
2
φA log
2 sup |ΦA (C) − ΦB (C)| ≤
φ
B
C∈C
R2
1
= {log |B| − log |A| + tr(B −1 (A − B))} ≤ kB −1/2 (A − B)B −1/2 k2 ,
2
provided kB −1/2 (A − B)B −1/2 k ≤ 1/2. Hence
sup |ΦA (C) − ΦB (C)| ≤ min{1, 2kB −1/2 (A − B)B −1/2 k}.

C∈C

We now take A = (n − 2)V /k, B = Σ and use the submultiplicativity of
the Frobenius norm along with (61) and (62) and the fact that kΣ−1/2 k =
{(1 + αz )−1 + (1 − αz )−1 }1/2 to deduce that



β/d
log1/2 n
k
1
+
a(f (x)∧ f (y))
(68) sup |ΦA (C)− ΦB (C)| .
kzk
nf (x)
k1/2
C∈C
for x ∈ Xn , y ∈ Bx◦ (rn,vx + rn,vy ), u ∈ [lx , vx ], v ∈ [ly , vy ]. Now let u =
f (x)−1 (1 + k−1/2 s) and v = f (x)−1 (1 + k−1/2 t). By the mean value theorem,
(52) and (60),


 
k
−1/2
ΦΣ k
(n − 2)µ −
− ΦΣ (s, t)
k


(n − 2)pn,x,u − k
(n − 2)pn,y,v − k
1
−s +
−t
≤
(2π)1/2
k1/2
k1/2
β/d

k
1/2
(69)
+ k−1/2 .
. k a(f (x) ∧ f (y))
nf (x)
It follows by (58), (59), (68) and (69) that for x ∈ Xn and y ∈ Bx◦ (rn,vx +

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

58

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

rn,vy ),
sup
u∈[lx ,vx ],v∈[ly ,vy ]

(1)
|Fn,x,y
(u, v) − ΦΣ (s, t)|



β/d 

k
1 
log1/2 n
1/2
+ a(f (x) ∧ (f (y))
k +
.
. min 1, 1/2
nf (x)
kzk
k kzk
Therefore, by (52) and (53), and since f (y) ≥ f (x)/2 for x ∈ Xn , y ∈
Bx (rn,vx + rn,vy ) and n ≥ n0 , we conclude that for each ǫ > 0 and n ≥ n0
Z

Z vxZ

(1)

vy

Fn,x (u, v) − ΦΣ (s, t)
1{kx−yk≤rn,u +rn,v } du dv dy dx
uv
lx ly
Xn ×X

 1/2
β/d 2
Z
k
k
log n
.
+ a(f (x)/2)
f (x)
n Xn
nf (x)
k1/2
Z
(1)
sup
|Fn,x,y
(u, v) − ΦΣ (s, t)| dz dx
x,z
f (x)f (y)

B0 (3) u∈[lx ,vx ],v∈[lyx,z ,vyx,z ]

(70)

=O



1

α

log5/2 n k 2 + α+d −ǫ k−1/2+β/d log n k1/2+2β/d
k
max
,
,
,
α
n
k3/2
nβ/d
n2β/d
n α+d −ǫ




.

By similar (in fact, rather simpler) means we can establish the same bound
for the approximation of Gn,x,y by Φ(k1/2 {uf (x) − 1})Φ(k 1/2 {vf (x) − 1}).
(1)
(2)
To conclude the proof for the unweighted case, we write Xn = Xn ∪ Xn ,
where
d

Xn(1) := {x : f (x) ≥ k 2β δn } ,

d

Xn(2) := {x : δn ≤ f (x) < k 2β δn },

and deal with these two regions separately. We have by Slepian’s inequality
that ΦΣ (s, t) ≥ Φ(s)Φ(t) for all s and t. Hence, recalling that s = sx,u =
k1/2 {uf (x) − 1} and t = tx,v = k1/2 {vf (x) − 1}, by (50), (52) and (60), for
every ǫ > 0,
Z vxZ vy
Z
ΦΣ (s, t) − Φ(s)Φ(t)
1{kx−yk≤rn,u +rn,v } du dv dy dx
f (x)f (y)
(2)
uv
lx ly
Xn ×X
Z
Z
1{kx−yx,z k≤rn,vx +rn,vyx,z }
eΨ(k)
≤
f (yx,z )
Vd (n − 1)k Xn(2) Rd
f (x)2 lx lyx,z
Z ∞Z ∞
{ΦΣ (s, t) − Φ(s)Φ(t)} ds dt dz dx
−∞

(71)

1
.
n

Z

−∞

α
d
) α+d
−ǫ 
 k(1+ 2β
,
αz dz dx = o
f (x)
α
(2)
n1+ α+d −ǫ
B0 (2)
Xn

Z

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

59

EFFICIENT ENTROPY ESTIMATION

R
where to obtain the final error term, we have used the fact that B0 (2) αz dz =
Vd . By (52) and (53) we have, for each ǫ > 0,
Z vxZ vy
Z
ΦΣ (s, t) − Φ(s)Φ(t)
f (x)f (y)
1{kx−yk≤rn,u +rn,v } du dv dy dx
(1)
uv
lx ly
Xn ×X
Z
Z
1{kx−yx,z k≤rn,vx +rn,vyx,z }
eΨ(k)
≤
αz dz dx
f (yx,z )
Vd (n − 1)k Xn(1) Rd
f (x)2 lx lyx,z
α


 1/2
Z
eΨ(k)
log n
kβ/d
k α+d −ǫ
=
, 1+β/d , 1+ α −ǫ
f (x) dx + O max
(n − 1)k Xn(1)
nk1/2
n
n α+d
(72)
α
d

 1/2

log n
eΨ(k)
kβ/d
k(1+ 2β ) α+d −ǫ
+ O max
=
.
,
,
α
(n − 1)k
nk1/2 n1+β/d
n1+ α+d −ǫ
(1)

By Lemma 10(ii) as for (60) we have, for x ∈ Xn , y ∈ Bx (rn,vx + rn,vy ),
(73)
 k β/d
= o(k−1/2 ),
max |vf (x)−1−3k−1/2 log1/2 n| . a(f (x)∧f (y))
nf (x)
v∈{vx ,vy }
with similar bounds holding for lx and ly . A corresponding lower bound of
the same order for the left-hand side of (72) follows from (73) and the fact
that
Z 2√log n Z 2√log n
{ΦΣ (s, t) − Φ(s)Φ(t)} ds dt = αz + O(n−2 )
√
√
−2 log n

−2 log n

uniformly for z ∈ Rd . It now follows from (57), (70), (71) and (72) that for
each ǫ > 0,
3

α−ǫ

(1+

d

) α−ǫ

1

β

log5/2 n k 2 + α+d k3/2+2β/d k 2β α+d k 2 + d log n
,
,
,
W4 = O max
α−ǫ ,
α−ǫ
β
nk1/2
n1+2β/d
n1+ d
n1+ α+d
n1+ α+d






,

as required.
We now turn our attention to the variance of the weighted Kozachenko–
Leonenko estimator Ĥnw . We first claim that
(74)
Var

X
k
j=1

wj log ξ(j),1



=

k
X

wj wl Cov(log ξ(j),1 , log ξ(l),1 ) = V (f ) + o(1).

j,l=1

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

60

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

By (18), (19) and Lemma 3 in the main text, for j such that wj 6= 0,
Var log ξ(j),1 = V (f ) + o(1)
as n → ∞. For l > j, using similar arguments to those used in the proof of
(k)
d −Ψ(k)
Lemma 3 in the main text, and writing ux,s := ux,s = Vd (n−1)h−1
x (s) e
for clarity, we have
E(log ξ(j),1 log ξ(l),1 )
Z 1 Z 1−s
Z
(l)
f (x)
log(u(j)
=
x,s )log(ux,s+t )Bj,l−j,n−l (s, t) dt ds dx
0
X
0
Z 1Z 1−s 
Z
(n − 1)s  (n − 1)(s + t)
log
Bj,l−j,n−l (s, t)dt ds dx+o(1)
log
= f (x)
f (x)eΨ(j)
f (x)eΨ(l)
0 0
X
Z
= f (x) log2 f (x) dx + o(1)
X

as n → ∞, uniformly for 1 ≤ j < l ≤ k1∗ . Now (74) follows on noting that
supk≥kd kwk < ∞.
Next we claim that
(75)

Cov

X
k

wj log ξ(j),1 ,

j=1

k
X

wl log ξ(l),2

l=1



= o(n−1 )

as n → ∞. In view of (20) in the main text and the fact that supk≥kd kwk <
∞, it is sufficient to show that

Cov log(f (X1 )ξ(j),1 ), log(f (X2 )ξ(l),2 ) = o(n−1 )

as n → ∞, whenever wj , wl 6= 0. We suppose without loss of generality here
that j < l, since the j = l case is dealt with in (27). We broadly follow
the same approach used to bound W1 , . . . , W4 , though we require some new
′
denote the conditional distribution function
(similar) notation. Let Fn,x,y
(j)

of (ξ(j),1 , ξ(l),2 ) given X1 = x, X2 = y and let Fn,x denote the conditional
distribution function of ξ(j),1 given X1 = x. Let
(j)
rn,u

:=



ueΨ(j)
Vd (n − 1)

1/d

,

(j)
p(j)
n,x,u := hx (rn,u ).

Recall the definitions of a±
n,j given in the proof of Lemma 13, and let vx,j :=
(j)

(j)

−
inf{u ≥ 0 : (n − 1)pn,x,u = a+
n,j } and lx,j := inf{u ≥ 0 : (n − 1)pn,x,u = an,j }.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

61

EFFICIENT ENTROPY ESTIMATION

For pairs (u, v) with u ≤ vx,j and v ≤ vy,l , let (M1 , M2 , M3 ) ∼ Multi(n −
(j)
(l)
(j)
(l)
2; pn,x,u , pn,y,v , 1 − pn,x,u − pn,y,v ) and write
G′n,x,y (u, v) := P(M1 ≥ j, M2 ≥ l).
Also write
Σ′ :=




1
(j/l)1/2 α′z
,
(j/l)1/2 α′z
1


where α′z := Vd−1 µd B0 (1) ∩ Bz (exp(Ψ(l) − Ψ(j))1/d ) . Writing Wi′ for remainder terms to be bounded later, we have

Cov log(f (X1 )ξ(j),1 ), log(f (X2 )ξ(l),2 )
Z
Z
′
(j) (l)
Fn,y )(u, v) dx dy + W1′
h(u, v) d(Fn,x,y
−Fn,x
f (x)f (y)
=
[ly,l ,vy,l ]×[lx,j ,vx,j ]

X ×X

Z
=

′
h(u, v) d(Fn,x,y
−G′n,x,y )(u, v) dx dy −

[ly,l ,vy,l ]×[lx,j ,vx,j ]

X ×X

Z
=

2

Z
f (x)f (y)

Z
f (x)f (y)

Xn ×X

vy,lZ

Vd−1 eΨ(j)
=
(n − 1)(jl)1/2

Rd

Z

∞
−∞

−

G′n,x,y )(u, v)
uv

lx,j

ly,l

Z

vx,j

′
(Fn,x,y

Z

∞

du dv dx dy −

{ΦΣ′ (s, t) − Φ(s)Φ(t)} ds dt dz −

−∞

(76)
V −1 eΨ(j)
= d
(n − 1)l

Z

Rd

α′z

1 X ′
Wi
+
n

1
+
n
1
+
n

i=1
3
X

Wi′

i=1
4
X

Wi′

i=1

  X
4
4
1
1 X
Wi = O
Wi′
dz − +
+
n
nk
i=1

i=1

as n → ∞. The final equality here follows from the fact that, for Borel
measurable sets K, L ⊆ Rd ,
Z

µd (K + z) ∩ L dz = µd (K)µd (L),
(77)
Rd

so that

R

Rd

α′z dz = Vd eΨ(l)−Ψ(j) .

To bound W1′ : Very similar arguments to those used to bound W1 show
that W1′ = o(n−(9/2−ǫ) ) as n → ∞, for every ǫ > 0.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

62

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

To bound W2′ : Similar to our work used to bound W2 , we may show that
Z

a+
n,j
n−1
a−
n,j
n−1

Z

a+
n,l
n−1
−
a
n,l
n−1

|Bj+a,l+b,n−j−l−1 (s, t)−Bj+a,n−j (s)Bl+b,n−l (t)| dt ds
≤

(jl)1/2
{1 + o(1)}
n

as n → ∞, for fixed a, b > −1. Also,
Z 1Z 1−s 
(n − 1)s  (n − 1)t 
log
log
{Bj,l,n−j−l−1(s, t)−Bj,n−j (s)Bl,n−l (t)}dtds
eΨ(j)
eΨ(l)
0 0
1
= − + O(n−2 )
n
as n → ∞. Using these facts and very similar arguments to those used to
bound W2 we have for every ǫ > 0 that
α
 β/d
 1/2

k α+d −ǫ
k
k
′
max β/d ,
W2 = O
.
α
n
n
n α+d −ǫ
To bound W3′ : Similarly to (47) and the surrounding work, we can show
that for every ǫ > 0,
2α
2β



1
log n k 2 + d k α+d −ǫ
′
.
,
, 2α
W3 = O max
nk1/2 n1+ 2β
d
n α+d −ǫ
(j)

(l)

To bound W4′ : Let (N1 , N2 , N3 , N4 ) ∼ Multi(n − 2; pn,x,u − p∩ , pn,y,v −
R
(j)
(l)
p∩ , p∩ , 1−pn,x,u −pn,y,v +p∩ ), where p∩ := B (r(j) )∩B (r(l) ) f (w) dw. Further,
x n,u
y n,v
let
′ ,(1)
Fn,x,y
:= P(N1 + N3 ≥ j, N2 + N3 ≥ l).
Then, as in (57), we have
Z vx,j Z
Z
f (x)f (y)
Xn ×X

=

Z

Xn ×X

′
− G′n,x,y )(u, v)
(Fn,x,y
du dv dx dy
uv
lx,j
ly,l
′ ,(1)
Z vx,j Z vy,l
(Fn,x,y − G′n,x,y )(u, v)
f (x)f (y)
du dv dx dy
uv
lx,j
ly,l
1
α


2β

1
log n k 2 + d k 2 + α+d −ǫ
,
, 1+ α −ǫ
+ O max
.
nk1/2 n1+ 2β
d
n α+d
vy,l

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

63

EFFICIENT ENTROPY ESTIMATION
′ ,(1)

We can now approximate Fn,x,y (u, v) by ΦΣ′ (j 1/2 {uf (x)−1}, l1/2 {vf (x)−1})
and G′n,x,y (u, v) by Φ(j 1/2 {uf (x) − 1})Φ(l1/2 {vf (x) − 1}). This is rather
similar to the corresponding approximation in the bounds on W4 , so we
only present the main differences. First, let
!
Yi′ :=

1{Xi ∈Bx (rn,u
(j)
)}
.
1{Xi ∈By (rn,v
(l)
)}

We also define
(j)

µ′ := E(Yi′ ) =

pn,x,u
(l)
pn,y,v

!

and
V ′ := Cov(Yi′ ) =

!
(j)
(j)
(j)
(l)
pn,x,u (1 − pn,x,u) p∩ − pn,x,upn,y,v
,
(j)
(l)
(l)
(l)
p∩ − pn,x,u pn,y,v pn,y,v (1 − pn,y,v )

and set Zi′ := V ′−1/2 (Yi′ − µ). Our aim is to provide a bound on p∩ . Since
the function

(r, s) 7→ µd B0 (r 1/d ) ∩ Bz (s1/d ) ,
(j)

(j)

is Lipschitz we have for x ∈ Xn , y = x + f (x)−1/d rn,1 z ∈ Bx (rn,vx,j +
(l)

rn,vy,l ), u ∈ [lx,j , vx,j ] and v ∈ [ly,l , vy,l ] that
(78)

β/d

log1/2 n
k
n−2
′
+
.
a(f
(x)
∧
(f
(y))
p
−
α
,
∩
z
nf (x)
eΨ(j)
k1/2

using similar equations to (52), (53) and (60). From this and similar bounds
to (61), we find that |V ′ | & k2 /n2 and k(V ′ )−1/2 k . (n/k)1/2 . We therefore
have
EkZ3′ k3 ≤ k(V ′ )−1/2 k3 EkY3′ − µ′ k3 . n1/2 /k1/2 ,
which is as in the l = j case except with the factor of kzk−1/2 missing. Note
now that
lim sup sup
n→∞

(j,l):j<l

wj ,wl 6=0

sup

k(Σ′ )−1/2 k < ∞.

z∈B0 (1+e(Ψ(l)−Ψ(j))/d )

Hence, using (78), similar bounds to (61) and the same arguments as leading
up to (68),

β/d
k
log1/2 n
,
(79)
sup |ΦA (C) − ΦB (C)| . a(f (x) ∧ f (y))
+
nf (x)
k1/2
C∈C
imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

64

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

where B := Σ′ and
!
(j)
(j)
(j)
(l)
j −1 pn,x,u(1 − pn,x,u )
j −1/2 l−1/2 (p∩ − pn,x,upn,y,v )
A := (n − 2) −1/2 −1/2
.
(j)
(l)
(l)
(l)
j
l
(p∩ − pn,x,u pn,y,v )
l−1 pn,y,v (1 − pn,y,v )
Now let u := f (x)−1 (1 + j −1/2 s) and v := f (x)−1 (1 + l−1/2 t). Similarly
to (69), we have
Φ Σ′

 (n − 2)p(j)

n,x,u
j 1/2

(l)

− j (n − 2)pn,y,v − l 
,
− ΦΣ′ (s, t)
l1/2

β/d
k
. k1/2 a(f (x) ∧ f (y))
+ k−1/2 .
nf (x)

Similarly to the arguments leading up to (70), it follows that
′ ,(1)

vx,jZ vy,l

Fn,x (u, v)−ΦΣ′ (s, t)
1{kx−yk≤rn,u
(j)
(l) du dv dy dx
+rn,v }
uv
lx,j ly,l
Xn ×X
α
1
 3/2


log n k 2 + α+d −ǫ k−1/2+β/d log n k1/2+2β/d
k
max
,
,
,
,
=O
α
n
k3/2
nβ/d
n2β/d
n α+d −ǫ
Z
f (x)f (y)

Z

where the power on the first logarithmic factor is smaller because of the
absence of the factor of the kzk−1 term in (79). The remainder of the work
required to bound W4′ is very similar to the work done from (71) to (72),
using also (77), so is omitted. We conclude that
W4′

d α−ǫ
α−ǫ
3


β

3
3 2β
1
log 2 n k 2 + α+d k 2 + d k(1+ 2β ) α+d k 2 + d log n
= O max
,
,
.
1
α−ǫ ,
α−ǫ
2β ,
β
nk 2
n1+ d
n1+ α+d n1+ d
n1+ α+d

The equation (76), together the bounds on W1′ , . . . , W4′ just proved, establish
the claim (75). We finally conclude from (74) and (75) that
Var(Ĥnw )

X

k
1
wj log ξ(j),1
= Var
n
j=1




X
k
k
X
1
+ 1−
wl log ξ(l),2
wj log ξ(j),1 ,
Cov
n
j=1

= V (f ) + o(n

−1

l=1

),

as required.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

65

EFFICIENT ENTROPY ESTIMATION

A. Proof of Theorem 8.
Proof of Theorem 8. For the first part of the theorem we aim to apply
Theorem 25.21 of van der Vaart (1998), and follow the notation used there.
With Ṗ := {λ(log f + H(f )) : λ ∈ R} we will first show that the entropy
functional H is differentiable at f relative to the tangent set Ṗ, with efficient
influence function ψ̃f = − log f − H(f ). Following Example 25.16 in van der
Vaart (1998), for g ∈ Ṗ, the paths ft,g defined in (10) of the main text are
differentiable
inR quadratic mean at t = 0 with score function g. Note that
R
2
gf
=
0
and
X
X g f < ∞ for all g ∈ Ṗ. It is convenient to define, for t ≥ 0,
the set At := {x ∈ X : 8t|g(x)| ≤ 1}, on which we may expand e−2tg easily
as a Taylor series. By Hölder’s inequality, for ǫ ∈ (0, 1/2),
Z
Z
2(1−ǫ)
f | log f | ≤ (8t)
f |g|2(1−ǫ) | log f |
c
X
At
oǫ
o1−ǫ nZ
nZ
2
2(1−ǫ)
f | log f |1/ǫ = o(t)
g f
≤ (8t)
X

X

as t ց 0. Moreover,
Z
Z
Z
2
−2tg
g2 f.
(log 2 + 2t|g|)f ≤ 16t (4 log 2 + 1)
f log(1 + e
)≤
Act

Act

X

We also have that
−1

|c(t)

(80)

Z 


2
− 1| =
− 1 − tg f
−2tg
X 1+e
Z
Z
e−2tg − 1 + 2tg + tg(e−2tg − 1)
f
+
(1 + t|g|)f
≤
1 + e−2tg
Act
At
Z
Z
Z
16 2
2
2
2
2
≤ t
g f + 72t
g2 f.
g f ≤ 72t
3
Act
At
X

It follows that
−1

Z

{H(ft,g ) − H(f )} + {log f + H(f )}f g
X
Z
 2c(t) 
o
2c(t) 
2c(t)
1 n
1−
log
log
f
−
+
tg(1
+
log
f
)
f
=
t X
1+e−2tg
1+e−2tg
1+e−2tg
Z
1
f {e−2tg − 1 + 2tg + tg(e−2tg − 1)} log f
≤
t At


2
− 2 log
+ tg(1 + e−2tg ) + o(1)
−2tg
1
+
e
Z
Z
16
g2 f + o(1) → 0.
g2 f | log f | + 22t
≤ t
3 X
X
t

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

66

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN

The conclusion (11) in the main text therefore follows from van der Vaart
(1998, Theorem 25.21).
We now establish the second part
the theorem. First, by our previous
R of
2
bound on c(t) in (80), for 12t < { X g f }−1/2 we have that
kft,g k∞ ≤ 2c(t)kf k∞ ≤

2kf k∞
R
≤ 4kf k∞ ,
1 − 72t2 X g2 f

and µα (ft,g ) ≤ 4µα (f ).
We now study the smoothness properties of ft,g . This requires some involved calculations, because we first need to understand corresponding properties of g. To this end, for an m times differentiable function g : Rd → R,
define


kg(m) (y) − g(m) (x)k
∗
(t)
Mg (x) := max max kg (x)k ,
sup
t=1,...,m
ky − xkβ−m
y∈Bx◦ (ra (x))
and


Dg := max 1,


supx:f (x)≥δ Mg∗ (x)
.
sup
a(δ)m+1
δ∈(0,kf k∞ )

Let Jm denote the set of multisets of elements {1, . . . , d} of cardinality
s
at most m, and for J = {j1 , . . . , js } ∈ Jm , define gJ (x) := Qs∂ g∂x (x).
ℓ
ℓ=1
Moreover, for i ∈ {1, . . . , s}, let Pi (J) denote the set of partitions of J into
i non-empty multisets. As an illustration, if d = 2, then

J3 = ∅, {1}, {2}, {1, 1}, {1, 2}, {2, 1}, {2, 2},
{1, 1, 1},{1, 1, 2},{1, 2, 1},{1, 2, 2},{2, 1, 1},{2, 1, 2},{2, 2, 1},{2, 2, 2} .

Moreover, if J = {1, 1, 2} ∈ J3 , then
n
o


P2 (J) =
{1, 1}, {2} , {1, 2}, {1} , {1, 2}, {1} .

Then, by induction, and writing g∗ := g1 = log f + H(f ), it may be shown
that
card(J)
X (−1)i−1 (i − 1)!
X
∗
gJ (x) =
f P1 . . . f Pi .
fi
i=1

{P1 ,...,Pi }∈Pi (J)

Now, the cardinality of Pi (J) is given by a Stirling’s number of the second
kind:
 
i


1X
i−ℓ i
card Pi (J) =
(−1)
ℓcard(J) =: S card(J), i ,
i!
ℓ
ℓ=0

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

67

say. Thus, if card(J) ≤ m, then
card(J)

(81)

|gJ∗ (x)|

≤

X
i=1


1
(i − 1)!S card(J), i a(f (x))i ≤ mm+1 m!a(f (x))m .
2

Moreover, if ky − xk ≤ ra (x) and m ≥ 1, then
card(J)

|gJ∗ (y) − gJ∗ (x)|

≤

X

|fP1 . . . fPi (y) − fP1 . . . fPi (x)|
f i (y)
{P1 ,...,Pi }∈Pi (J)

|fP1 . . . fPi (x)| f i (y)
+
−1 .
f i (y)
f i (x)
X

(i − 1)!

i=1



Now, by Lemma 12,
f i (y)
f (y)
−1 ≤i
−1
i
f (x)
f (x)



f (y)
−1
1+
f (x)

i−1

≤

 71 i−1 f (y)
i
−1 .
56
f (x)

Moreover, by induction and Lemma 12 again,
o
n 71 i
1/2
−
1
a(f (x))i f i (x)ky − xkβ−m .
|fP1 . . . fPi (y) − fP1 . . . fPi (x)| ≤ 8d
56

We deduce that (even when m = 0),
 71 m
(82) |gJ∗ (y) − gJ∗ (x)| ≤ 8d1/2
m!(m + 1)m+2 a(f (x))m+1 ky − xkβ−m .
41
Comparing (81) and (82), we see that
 71 m
m!(m + 1)m+2 =: D.
(83)
Dg∗ ≤ 8d1/2
41


Now let q(y) := (1 + e−2ty )−1 , so that ft,g (x) = 2c(t)q g(x) f (x). Similar
inductive arguments to those used above yield that when J ∈ Jm with m ≥ 1
and g is m times differentiable,
card(J)

(q ◦ g)J (x) =

X
i=1


q (i) g(x)

X

gP1 . . . gPi (x),

{P1 ,...,Pi }∈Pi (J)

and we now bound the derivatives of q. By induction,
i
X
(−1)i−ℓ
q (y) = (2t)
(i)

i

ℓ=1

(i)

aℓ e−2tℓy
,
(1 + e−2ty )ℓ+1

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

68

T. B. BERRETT, R. J. SAMWORTH AND M. YUAN
(i)

(i)

(i)

(i−1)

where for each i ∈ N, we have a1 = 1, ai = i! and aℓ = ℓ(aℓ
(i)

(i−1)

+ aℓ−1 )

for ℓ ∈ {2, . . . , i − 1}. Since max1≤ℓ≤i aℓ ≤ (2i)i−1 (again by induction), we
deduce that
(1 + e−2ty )|q (i) (y)| ≤ 22i−1 ii ti .

(84)

Writing s := card(J), it follows that
s
X
22i−1 ii ti S(s, i)a(f (x))i(m+1) Dgi
|(q ◦ g)J (x)| ≤ q g(x)
i=1


≤ q g(x) ss+1 22s−1 max(1, t)s Bs a(f (x))s(m+1) Dgs ,

(85)

P
where Bs := si=1 S(s, i) denotes the sth Bell number. We can now apply
the multivariate Leibniz rule, so that for a multi-index ω = (ω1 , . . . , ωd ) with
|ω| ≤ m, and for t ≤ 1 and m ≥ 1,

X ω  ∂ ν q g∗ (x) ∂ ω−ν f (x)
∂ ω ft,g∗ (x)
= 2c(t)
∂xω
∂xν
∂xω−ν
ν
ν:ν≤ω

3m−1

≤2

(86)

∂ω f

2 +m

mm+1 Bm Dgm∗ a(f (x))m
∗ (y)

∂ω f

ft,g∗ (x).

∗ (x)

t,g
t,g
Now, in order to control
− ∂x
, we first note that by (82)
ω
∂xω
and (83), we have for ky − xk ≤ ra (x), i ∈ N, J ∈ Jm with card(J) = s and
{P1 , . . . , Pi } ∈ Pi (J),

|gP∗ 1 . . . gP∗ i (y) − gP∗ 1 . . . gP∗ i (x)| ≤ (2D)i a(f (x))i(m+1) ky − xkβ−m .

(87)

Thus, by (84), (87), the mean value theorem and Lemma 12, for t ≤ 1,
ky − xk ≤ ra (x) and m ≥ 1,
|(q ◦ g∗ )J (y) − (q ◦ g∗ )J (x)|
s
X
X
≤
q (i) (g∗ (x))
i=1

+

s
X

{P1 ,...,Pi }∈Pi (J)

{q (i) (g∗ (y)) − q (i) (g∗ (x))}

i=1

m

{gP∗ 1 . . . gP∗ i (y) − gP∗ 1 . . . gP∗ i (x)}

∗

m2 +m+1

≤ D q(g (x))a(f (x))

X

gP∗ 1 . . . gP∗ i (y)

{P1 ,...,Pi }∈Pi (J)

ky − xkβ−m

Bm 23m+5 d1/2 (m + 1)m+1 (1 + e2tg
×
e2tg∗ (x) + e−2t|g∗ (y)−g∗ (x)|

∗ (x)

)

(88)
2 +m+1

≤ D m q(g∗ (x))a(f (x))m

ky − xkβ−m Bm 23m+5 d1/2 (m + 1)m+1

 56 2t
41

.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

EFFICIENT ENTROPY ESTIMATION

69

Using the multivariate Leibnitz rule again, together with (85), (88) and
Lemma 12, for t ≤ 1, ky − xk ≤ ra (x) and |ω| = m ≥ 1,
∂ ω ft,g∗ (y) ∂ ω ft,g∗ (x)
−
∂xω
∂xω

X ω  ∂ ω−ν f (y) ∂ ν q(g∗ (y)) ∂ ν q(g∗ (x))
≤ 2c(t)
−
ν
∂y ω−ν
∂xν
∂xν
ν:ν≤ω

∂ ν q(g∗ (x)) ∂ ν f (y) ∂ ν f (x)
+
−
∂xν
∂xν
∂xν
2 +m+1

≤ 24m+9 d1/2 Bm (m + 1)m+1 D m a(f (x))m

(89)

2 +m+1

′
=: Cm
D m a(f (x))m

ft,g∗ (x)ky − xkβ−m

ft,g∗ (x)ky − xkβ−m .

R
This also holds in the case m = 0. Now note that if 12t < { X (g∗ )2 f }−1/2
we have
∗
1 + e−2tg (x)
ft,g∗ (x)
f (x) =
ft,g∗ (x) ≥
.
2c(t)
4
Finally, define the function
2 +m+1

′
ã(δ) := dm/2 Cm
D m a(δ/4)m

(90)

.

Then ã ∈ A and from (86) and (89), we have Mft,g∗ ,ã,β (x) ≤ ã(ft,g∗ (x)). We

R
conclude that for t < min 1, {144 g2 f }−1/2 , we have that ft,g∗ ∈ Fd,θ′ ,
where θ ′ = (α, β, 4γ, 4ν, ã) ∈ Θ. The result follows on noting that ft,gλ =
ftλ,g∗ .
References.
Berrett, T. B., Samworth, R. J. and Yuan, M. (2017) Efficient multivariate entropy estimation via k-nearest neighbour distances. Submitted.
Götze, F. (1991) On the rate of convergence in the multivariate CLT. Ann. Prob., 19,
724–739.
van der Vaart, A. W. (1998). Asymptotic Statistics. Cambridge University Press, Cambridge.

imsart-aos ver. 2014/10/16 file: WKLRevArxiv.tex date: June 23, 2017

