Dimension-Free Empirical Entropy Estimation
Year: 2021

Abstract:
We seek an entropy estimator for discrete distributions with fully empirical accuracy bounds. As stated, this goal is infeasible without some prior assumptions on the distribution. We discover that a certain information moment assumption renders the problem feasible. We argue that the moment assumption is natural and, in some sense, minimalistic — weaker than finite support or tail decay conditions. Under the moment assumption, we provide the first finite-sample entropy estimates for infinite alphabets, nearly recovering the known minimax rates. Moreover, we demonstrate that our empirical bounds are significantly sharper than the state-ofthe-art bounds, for various natural distributions and non-trivial sample regimes. Along the way, we give a dimension-free analogue of the Cover-Thomas result on entropy continuity (with respect to total variation distance) for finite alphabets, which may be of independent interest.

heading: 1 Introduction
text: Estimating the entropy of a discrete distribution based on a finite iid sample is a classic problem with theoretical and practical ramifications. Considerable progress has been made in the case of a finite alphabet, and the countably infinite case has also attracted a fair amount of attention in recent years. A less-addressed issue is one of empirical accuracy estimates: data-dependent bounds adaptive to the particular distribution being sampled.
Our point of departure is the simpler (to analyze) problem of estimating a discrete distribution µ in total variation norm ‖·‖TV = 12 ‖·‖1, where the most recent advance was made by Cohen et al. [2020]; see therein for a literature review. If µ is a distribution on N and µ̂n is its empirical realization based on a sample of size n, then Theorem 2.1 of Cohen et al. states that with probability at least 1− δ,
‖µ− µ̂n‖1 ≤ 2√ n
∑
j∈N
√ µ̂n(j) + 6
√ log(2/δ)
2n . (1)
∗A major part of this research was conducted when the author was graduate student at Ben-Gurion University of The Negev, Israel.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
This bound has the advantage of being valid for all distributions on N, without any prior assumptions, and being fully empirical: it yields a risk estimate that is computable based on the observed sample, not depending on any unknown quantities. (Additionally, Cohen et al. argue that (1) is near-optimal in a well-defined sense.) The question we set out to explore in this paper is: What analogues of (1) are possible for discrete entropy estimation?
When µ has support size d < ∞, an answer to our question is readily provided by combining (1) with Cover and Thomas [2006, Theorem 17.3.3], which asserts that, for ‖µ− ν‖1 ≤ 1/2, we have
|H(µ)−H(ν)| ≤ ‖µ− ν‖1 log d
‖µ− ν‖1 , (2)
where H(·) is the entropy functional defined in (3). Indeed, taking µ as in (1) and ν to be µ̂n yields a fully empirical estimate on |H(µ)−H(µ̂n)|. For fixed d <∞, no technique relying on the plug-in estimator can yield minimax rates [Wu and Yang, 2016]. The plug-in is, however, minimax optimal for fixed d <∞ [Paninski, 2003] as well as strongly universally consistent even for d =∞ [Antos and Kontoyiannis, 2001a], and is among the few methods for which explicitly computable finite-sample risk bounds are known.
The thrust of this paper is to replace the restrictive finite-support assumption with considerably more general moment conditions. It is well-known that when estimating the mean of some random variable X , the first-moment assumption E|X| ≤M is not sufficient to yield any finite-sample information.2 Strengthening the assumption to E|X|α ≤ M , for any α > 1, immediately yields finite-sample empirical estimates on ∣∣EX − 1n ∑n i=1Xi
∣∣ via the von Bahr and Esseen [1965] inequality.3 In this sense, a bound on the (1 + ε)th moment is a minimal requirement for empirical mean estimation. However, it is not immediately obvious how to apply this insight to the entropy estimation problem: the corresponding random variable is X = − logµ(I), where I ∼ µ, but rather than being given iid samples of X , we are only given draws of I .
Our contribution. In Theorem 1, we provide a dimension-free analogue of (2), which, combined with (1), allows for empirical accuracy bounds on the plug-in entropy estimator under a minimalistic moment assumption. Moreover, for this rich class of distributions, the plug-in estimator turns out to be asymptotically optimal, as we show in Theorem 4. Our moment assumption is natural and essentially the weakest one that makes any empirical bounds feasible, as we argue in Theorem 3. As we demonstrate in Section 6, the rates provided by our empirical bound compare favorably against the state of the art.

heading: 2 Definitions and notation
text: Our logarithms will always be base e by default. For discrete distributions, there is no loss of generality in taking the domain to be the natural numbers N = {1, 2, 3, . . .}. For k ∈ N, we write [k] := {i ∈ N : i ≤ k}. The set of all probability distributions on N will be denoted by ∆N. For d ∈ N, we write ∆d ⊂ ∆N to denote those µ whose support is contained in [d]. We define the operator (·)↓, which maps any µ ∈ ∆N to its non-increasing rearrangement µ↓. The set of all non-increasing distributions will be denoted by ∆↓N := { µ↓ : µ ∈ ∆N } .
We write R+ := [0,∞). For any ξ : N→ R+ and α ≥ 0, define
H(α)(ξ) := ∑
j∈N:ξ(j)>0 ξ(j) |log ξ(j)|α . (3)
For ξ ∈ RN, denote by |ξ| ∈ RN+ the elementwise application of |·| to ξ. When ξ ∈ ∆N and α = 1, (3) recovers the standard definition of entropy, which we denote by H(ξ) := H(1)(ξ). For general
2Even distinguishing, for X ≥ 0, between EX = 0 and EX = M based on a finite sample is impossible with any degree of confidence. Of course, 1
n ∑n i=1Xi → EX almost surely, by the strong law of large numbers.
3Put Y = X − EX; then E|Y | ≤ 2M . For 1 < α < 2, a sharper version of the Bahr-Esseen inequality [Pinelis, 2015] states that E [∣∣∑n i=1 Yi ∣∣α] ≤ 2n(2M)α, which implies tail bounds via Markov’s inequality. Better rates are available via the median-of-means estimator, see Lugosi and Mendelson [2019].
α > 0, this quantity may be referred to as the αth moment of information. For h ≥ 0, define
∆ (α) N [h] = { µ ∈ ∆N : H(α)(µ) ≤ h }
and also ∆(α)N := ⋃ h≥0 ∆ (α) N [h] and ∆ ↓(α) N [h] := ∆ ↓ N ∩∆ (α) N [h].
For n ∈ N and µ ∈ ∆N, we write X = (X1, . . . , Xn) ∼ µn to mean that the components of the vector X are drawn iid from µ. The empirical measure µ̂n ∈ ∆N induced by the sample X is defined by µ̂n(j) = 1 n ∑ i∈[n] 1[Xi = j]. For any ξ ∈ RN and 0 < p <∞, the `p (pseudo)norm is
defined by ‖ξ‖pp = ∑ j∈N |ξ(j)|p and ‖ξ‖∞ = supj∈N |ξ(j)|.
For α, h > 0, and n ∈ N, define the L1 minimax risk for the αth moment by
R(α)n (h) := inf Ĥ sup µ∈∆(α)N [h] E|Ĥ(X1, . . . , Xn)−H(µ)|, (4)
where the infimum is over all mappings Ĥ : Nn → R+.

heading: 3 Main results
text: Our first result is a dimension-free analogue of (2):
Theorem 1. For all α > 1, H : ∆(α)N → R+ is uniformly continuous under `1. In particular, for all µ,ν ∈ ∆(α)N satisfying ‖µ− ν‖∞ < 1/2, we have
|H(µ)−H(ν)| ≤ ‖µ− ν‖1−1/α1 ( 2αα + H(α)(µ) + H(α)(ν) )1/α
≤ ‖µ− ν‖1−1/α1 ( 2α+ H(α)(µ)1/α + H(α)(ν)1/α ) .
The requirement in Theorem 1 that α > 1 cannot be dispensed with, as the function H : ∆(α)N [h]→ R+ is not continuous under `1 for α = 1 (see Remark following Lemma 5), and, a fortiori, is not uniformly continuous. Thus, there can be no function F : R2+ → R+ satisfying
|H(µ)−H(ν)| ≤ F (‖µ− ν‖1 , h), h > 0,µ,ν ∈ ∆ (1) N [h]
with the additional property that for any two sequences µn,νn ∈ ∆N satisfying εn := ‖µn − νn‖1 → 0, it holds that F (εn, h)→ 0.
Perhaps surprisingly,4 it turns out that H : ∆(α)N [h]→ R+ is uniformly continuous under `p for all α > 1, p ∈ [1,∞]: Theorem 2. There is a function F : R4+ → R+ such that
|H(µ)−H(ν)| ≤ F (‖µ− ν‖p , h, α, p), h > 0, α > 1, p ∈ [1,∞],µ,ν ∈ ∆ (α) N [h]
with the additional property that whenever εn := ‖µn − νn‖p → 0, we have F (εn, h, α, p)→ 0.
Remark. Although Theorem 2 establishes uniform continuity, it gives no hint as to the functional dependence of the modulus of continuity F on α, p, h, and ‖µ− ν‖p. We leave this as a fascinating open problem — even though the practical applications are likely to be limited: it follows from Wyner and Foster [2003] and Theorem 4 that for p = α = 2 and fixed h, F (‖µ− ν‖2 , h, 2, 2) cannot decay at a faster rate than 1/ log(1/ ‖µ− ν‖2). Combining Theorem 1 with (1) yields an empirical (under moment assumptions) bound for the plug-in entropy estimator:
4Since `1 dominates all of the `p norms, continuity of a function under `p trivially implies continuity under `1, but the reverse implication is generally not true.
Corollary 1. For all α > 1, h > 0, δ ∈ (0, 1), n ≥ 2 log 4δ , and µ ∈ ∆ (α) N [h], we have that
|H(µ)−H(µ̂n)| ≤ ( 2αα + h+ H(α)(µ̂n) )1/α
 2 ‖µ̂n‖ 1/2 1/2√
n + 6
√ log (4/δ)
2n
  1−1/α
holds with probability at least 1− δ.
In Section 6, we compare the rates implied by Corollary 1 to the state of the art on various distributions.
Next, we examine the optimality of the plug-in estimate by analyzing the minimax risk, defined in (4). It was known [Silva, 2018, Appendix A] that assuming H(µ) <∞ does not suffice to yield a minimax rate for the L2 risk:
inf Ĥ:Nn→R+ sup µ∈∆(1)N
E ( Ĥ(X1, . . . , Xn)−H(µ) )2 =∞.
This technique yields an analogous result for the L1 risk as well. We strengthen these results in two ways: (i) by lower-bounding the L1 risk (rather than L2, which is never smaller), and (ii) by restricting µ to ∆(1)N [h] and obtaining a finitary, quantitative lower bound: Theorem 3. For α = 1, there is a universal constant C > 0 such that for all h > 1 and n ∈ N, we haveR(1)n (h) ≥ Ch.
Remark. The above result complements — but is not directly comparable to — Antos and Kontoyiannis [2001a, Theorem 4]. Ours gives a quantitative dependence on h but constructs an adversarial distribution for each sample size n; theirs is asymptotic only but a single adversarial distribution suffices for all n.
Remark. Our technique immediately yields a lower bound of Ch2 on the L2 minimax risk.
In contradistinction to the α = 1 case, where no minimax rate exists, we show that the plug-in estimator is minimax for all α > 1:
Theorem 4. The following bounds hold for the L1 minimax risk:
(a) Upper bound: for all h > 0, α > 1,
R(α)n (h) ≤ 1 + log n√
n +
2α−1h
logα−1 n , n ∈ N;
further, this bound is achieved by the plug-in estimate H(µ̂n).
(b) Lower bound: for each α > 0, n ∈ N there is an h > 0 such that
R(α)n (h) ≥ h
4 · 3α logα−1 n .
Open problem. Close the gap in the dependence on α in the upper and lower bounds.

heading: 4 Related work
text: Continuity, convergence, moments of information. Zhang [2007] gave a sharpened version of (2) and Ho and Yeung [2010] presented analogous bounds; Audenaert [2007] proved a non-commutative generalization. Sason [2013, Theorem 5] upper-bounds |H(µ)−H(ν)| in terms of quantities related to ‖µ− ν‖1, where (at most) one of them is allowed to have infinite support. Even though H(·) is not continuous on ∆N, the plug-in estimate H(µ̂n) converges to H(µ) almost surely and in L2 [Antos and Kontoyiannis, 2001a]. Silva [2018] studied a variety of restrictions on distributions over infinite alphabets to derive strong consistency results and rates of convergence. Moments of information were apparently first defined in Golomb [1966].
Entropy estimation. Recent surveys of entropy estimation results may be found in Jiao et al. [2015], Verdú [2019]. The finite-alphabet case is particularly well-understood. For fixed alphabet size d < ∞, the plug-in estimate is asymptotically minimax optimal [Paninski, 2003]. Paninski [2004] non-constructively established the existence of a sublinear (in d) entropy estimator. The optimal dependence on d (at fixed accuracy) was settled by Valiant and Valiant [2011a, 2017] as being Θ(d/ log d).
The Θ(d/ log d) dependence on the alphabet size is also relevant in the so-called high dimensional asymptotic regime, where d grows with n. Here, the plug-in estimate is no longer optimal, and more sophisticated techniques are called for [Valiant and Valiant, 2011a,b, 2017]. The works of Wu and Yang [2016], Jiao et al. [2015], Han et al. [2015], Jiao et al. [2017] characterized the minimax rates for the high-dimensional regime: a small additive error of ε requires Θ(d/ε log d) samples. Building off of these polynomial-approximation based constructions, Acharya et al. [2017] design an additional optimal estimator, this one based on a profile maximum likelihood approach that can also estimate a variety of other important statistics. Fukuchi and Sakuma [2017, 2018] generalize the optimal estimators to estimate any additive functional, recovering in particular the optimal rates for entropy. Acharya et al. [2019] modify these optimal estimators with the added goal of low space complexity.
Finally, there is the infinite-alphabet case. Although here the plug-in estimate is again universally strongly consistent, control of the convergence rate requires some assumption on the sampling distribution — and Antos and Kontoyiannis [2001a] compellingly argue that moment assumptions are natural and minimalistic. Absent any prior assumptions, the L1 (and hence L2) convergence rate of any estimator can be made arbitrarily slow (Theorem 4 ibid.). The present paper proves a variant of this result (see Theorem 3 and the Remark following it). Antos and Kontoyiannis [2001a] further show that even under moment assumptions, there is no polynomial rate of convergence for the plug-in estimate: there is no β > 0 such that its risk decays as O(n−β). Wyner and Foster [2003] showed that the plug-in estimate achieves a rate of O( 1logn ) for bounded second moment, and this is minimax optimal. Brautbar and Samorodnitsky [2007] exhibited a function of the higher moments that can be used in place of alphabet size to give a multiplicative approximation to the entropy.

heading: 5 Proofs

heading: 5.1 Proof of Theorem 1
text: We begin with a subadditivity result for the αth moment of information (which we state for α > 0, even though only the range α > 1 will be needed).
Lemma 1. For α > 0 and µ,ν ∈ ∆(α)N , we have
H(α)(|µ− ν|) ≤ 2αα + H(α)(µ) + H(α)(ν).
Proof. Define h(α) : [0, 1] → R+ by z 7→ z lnα(1/z), where h(α)(0) = 0. The function h(α) is increasing on [0, e−α] and decreasing on [e−α, 1]. The maximum is therefore achieved at z = e−α, and
max z∈[0,1]
h(α)(z) = h(α)(e−α) = e−ααα. (5)
Now decompose H(α):
H(α)(|µ− ν|) = ∑
i:µ(i)∨ν(i)>e−α h(α)(|µ(i)− ν(i)|) +
∑
i:µ(i)∨ν(i)≤e−α h(α)(|µ(i)− ν(i)|).
For the first term, since µ ∈ ∆N, it must be that |{i ∈ N : µ(i) > e−α}| ≤ eα, and similarly for ν. Thus,
∑
i:µ(i)∨ν(i)>e−α h(α)(|µ(i)− ν(i)|) ≤
( ∣∣{i : µ(i) > e−α }∣∣+ ∣∣{i : ν(i) > e−α }∣∣ ) max
z∈[0,1] h(α)(z)
≤ 2eαe−ααα = 2αα.
For the second term, notice that when µ(i) ∨ ν(i) ≤ e−α, the monotonicity of h(α) implies h(α)(|µ(i)− ν(i)|) ≤ h(α)(µ(i) ∨ ν(i)),
and hence ∑
i∈N:µ(i)∨ν(i)≤e−α h(α)(|µ(i)− ν(i)|) ≤
∑
i:∈µ(i)∨ν(i)≤e−α h(α)(µ(i) ∨ ν(i))
≤ ∑
i:∈µ(i)∨ν(i)≤e−α h(α)(µ(i)) + h(α)(ν(i))
≤ H(α)(µ) + H(α)(ν).
Proof of Theorem 1. The concavity argument in the proof of Cover and Thomas [2006, Theorem 17.3.3], immediately implies
|H(µ)−H(ν)| ≤ H(|µ− ν|). Then, via an application of Hölder’s inequality, H(|µ− ν|) = ∑
i∈N |µ(i)− ν(i)| log 1|µ(i)− ν(i)|
= ∑
i∈N |µ(i)− ν(i)|1−1/α · |µ(i)− ν(i)|1/α log 1|µ(i)− ν(i)|
≤ (∑
i∈N
( |µ(i)− ν(i)|1−1/α
)1/(1−1/α) )1−1/α(∑
i∈N
( |µ(i)− ν(i)|1/α log 1|µ(i)− ν(i)|
)α)1/α
= ‖µ− ν‖1−1/α1 H(α)(|µ− ν|)1/α. The claim follows by invoking Lemma 1 and the subadditivity of t 7→ t1/α for t ≥ 0 and α > 1.

heading: 5.2 Proof of Corollary 1
text: For h > 1 and n ∈ N, put an = (1−1/(2n)) ln(1−1/(2n)) and define the support size S = S(h, n) by S = b(1/2n) exp(2n(h + an))c. Consider the distributions µ0 = (1, 0, 0, . . . ) and µn defined by µn(1) = 1− 1/(2n), and
µn(i) = 1
2nS , 2 ≤ i ≤ 1 + S(h, n).
We compute the Kullback-Leibler divergence and entropy:
DKL (µ0||µn) = log 1 1− 1/(2n) ≤ 1 1− 1/(2n) − 1 ≤ 1 n (6)
H(µ0) = 0 ≤ h. For x ≥ 2, always bxc ≥ x/2. Additionally, from 2nan ≥ −1, and 12n exp(2nh − 1) > 2, we obtain that S > (1/4n) exp(2n(h+ an)), hence we also have that h ≥ H(µn) > h− 12n ln 2. Since 1 2x ln 2 ≤ 1/2 on (0,∞) and h > 1, it follows that H(µn) ≥ h2 , whence |H(µ0)−H(µn)| ≥ h/2. To bound the L1 minimax risk (defined in (4)), we invoke Markov’s inequality:
E|Ĥ(X1, . . . , Xn)−H(µ)| ≥ h 4 P ( |Ĥ(X1, . . . , Xn)−H(µ)| > h 4 ) .
It follows via Le Cam’s two point method [Tsybakov, 2008, Section 2.4.2] that
R(1)n (h) ≥ h 4 e−nDKL(µ0||µ) ≥ h 4e ,
where the second inequality stems from (6).

heading: 5.3 Proof of Theorem 4
text: We begin with an auxiliary lemma, of possible independent interest.
Lemma 2. For all µ ∈ ∆N and n ∈ N, we have
H(µ) ≥ EH(µ̂n) ≥ H(µ)− inf 0<ε<1
  ∑
i∈N:µ(i)<ε µ(i) log
1
µ(i) + log
( 1 + 1
εn
)  .
Proof. The first inequality follows from Jensen’s, since H(·) is concave and Eµ̂n = µ. To prove the second inequality, choose ε > 0, put J := {i ∈ N : µ(i) < ε}, and compute
EH(µ̂n) = E
  ∑
i∈N\J µ̂n(i) log
1 µ̂n(i) + ∑ i∈J µ̂n(i) log 1 µ̂n(i)
 
≥ E
  ∑
i∈N\J µ̂n(i) log
1
µ̂n(i) +
(∑
i∈J µ̂n(i)
) log
1∑ i∈J µ̂n(i)
 
=: EH(µ̃n),
where µ̃n is the “collapsed” version of µ̂n, where all of the masses in J have been replaced by a single mass equal to their sum, and the inequality holds because conditioning reduces entropy [Cover and Thomas, 2006, Eq.(2.157)]. We observe that µ̃n has support size at most 1 + 1/ε and invoke Paninski [2003, Proposition 1]:
EH(µ̃n) ≥ H(µ̃)− log ( 1 + 1
εn
) , (7)
where µ̃ is the “collapsed” version of µ. Now
H(µ̃) = H(µ) +
 ∑
i∈j µ(i)
  log 1∑
i∈J µ(i) − ∑ i∈J µ(i) log 1 µ(i)
≥ H(µ)− ∑
i∈J µ(i) log
1
µ(i) ,
which concludes the proof.
The first part of the theorem will follow from the following proposition.
Proposition 1. For α ≥ 1, h > 0, n ∈ N and µ ∈ ∆(α)N [h], we have
E|H(µ)−H(µ̂n)| ≤ log n√ n + inf 0<ε<1
[( log 1
ε
)1−α h+ log ( 1 + 1
εn
)] .
Proof. Since by Lemma 2, |H(µ)− EH(µ̂n)| = H(µ)− EH(µ̂n), it follows from the triangle and Jensen inequalities that
E|H(µ)−H(µ̂n)| ≤ E|H(µ̂n)− EH(µ̂n)|+ H(µ)− EH(µ̂n) ≤ √ Var [H(µ̂n)] + H(µ)− EH(µ̂n)
≤ log n√ n + H(µ)− EH(µ̂n), (8)
where the variance bound is from Antos and Kontoyiannis [2001b, Proposition 1(iv)].
For any ε > 0, Lemma 2 implies
EH(µ̂n) ≥ H(µ)− ∑
i∈N:µ(i)<ε µ(i) log
1
µ(i) − log
( 1 + 1
εn
)
≥ H(µ)− ( log 1
ε
)1−α ∑
i∈N:µ(i)<ε µ(i)
( log 1
µ(i)
)α − log ( 1 + 1
εn
)
≥ H(µ)− ( log 1
ε
)1−α H(α)(µ)− log ( 1 + 1
εn
) , (9)
where the second and third inequalities follow from the obvious relations ∑
i:µ(i)<ε
µ(i) log 1 µ(i) ≤ ( log 1 ε )1−α ∑
i:µ(i)<ε
µ(i) ( log 1
µ(i)
)α ≤ ( log 1
ε
)1−α H(α)(µ).
The claim follows by combining (8) with (9).
Proof of Theorem 4(a). Use the fact thatR(α)n (h) ≤ E|H(µ)−H(µ̂n)|, invoke Proposition 1 with ε = 1√
n and use log(1 + x) ≤ x.
We now prove the second half of the theorem.
Proof of Theorem 4(b). Let α > 0, n ∈ N and define two families of distributions: U1 := { µ1 = Uniform([n 3]) } , U2 := { µ2 = Uniform(A) : A ⊂ [n3], |A| = n2 } .
Let h := 3α logα n and note that U1 ∪ U2 ⊆ ∆(α)N [h]. Let E be the event that X = (X1, . . . , Xn) has no repeating elements, i.e |{X1, X2, . . . , Xn}| = n. Let µ1 ∈ U1,µ2 ∈ U2 and consider the values PX∼µn1 (E) and PX∼µn2 (E). For m ∈ N, define X (m) to be the smallest k such that when uniformly throwing m balls into k buckets, the probability of collision is at least 1/2. Since X (m) is known5 to be at least √m (and hence X (n2) > n) we have a lower bound of 12 on both PX∼µn1 (E) and PX∼µn2 (E). Define µ n 1 |E as the distribution on Nn induced by conditioning the product µn1 on the event E, and define µ n 2 |E analogously. Our key observation is that conditional on E, (i) both are effectively distributions on ordered n-tuples from [n3], and (ii) µn1 is uniform on ([n
3])n whereas µn2 = Uniform(A) is uniform on (A)n, where (J)k := { (x1, . . . , xk) ∈ Jk : | {x1, . . . , xk} | = k } , J ⊂ N, k ∈ N. Then
R(α)n (h) ≥ inf Ĥ sup µ∈U1∪U2 E X∼µn
[ |Ĥ(X)−H(µ)| ]
(a) ≥ inf
Ĥ sup µ∈U1∪U2 E X∼µn|E
[ |Ĥ(X)−H(µ)| ] P
X∼µn (E)
≥ inf Ĥ
1 2 sup µ∈U1∪U2 E X∼µn|E
[ |Ĥ(X)−H(µ)| ]
(b) ≥ inf
Ĥ
1
4
( E
X∼µn1 |E
[ |Ĥ(X)−H(µ1)| ] + sup µ2∈U2 E X∼µn2 |E [ |Ĥ(X)−H(µ2)|
])
(c) ≥ inf
Ĥ
1
4
( E
X∼µn1 |E
[ |Ĥ(X)−H(µ1)| ] + E µ2∼Uniform(U2)
[ E
X∼µn2 |E
[ |Ĥ(X)−H(µ2)|
]])
(d) = inf
Ĥ
1
4
( E
X∼µn1 |E
[ |Ĥ(X)−H(µ1)| ] + E X∼µn1 |E [ |Ĥ(X)−H(µ2)|
])
= inf Ĥ
1
4
( E
X∼µn1 |E
[ |Ĥ(X)−H(µ1)|+ |Ĥ(X)−H(µ2)|
])
(e) ≥ 1
4 |H(µ1)−H(µ2)| =
1 4 log n = 1 4
h
3α logα−1 n ,
5Better bounds exist [Brink, 2012].
where (a) is from the law of total expectation (the complement of E is discarded), (b) and (c) are bounding a supremum by an average, (e) is from the triangle inequality, and (d) is by observing that, by symmetry, the operators Eµ2∼Uniform(U2) [ EX∼µn2 |E [·] ] and EX∼µn1 |E [·] are equivalent. (There is a minor abuse of notation in transitions after (c), since we write µ2 without specifying a particular member of U2. However, µ2 only occurs therein as H(µ2), and this value is identical for all µ2 ∈ U2.)

heading: 6 Rates
text: Our bounds have the crucial characteristic of being empirical (under moment assumptions). When we observe favorable distributions (even without a priori knowledge of the fact), we will benefit from tighter bounds. This entails some cost, and in the worst case our bounds will be sub-optimal. In this section, we illustrate these trade-offs for various natural classes of distributions.
For the class of all finite alphabet distributions, our bound is sub-optimal. The MLE (plug-in estimator) is competitive with the optimal estimator up to logarithmic factors in d, but our bounds on the MLE are loose nearly quadratically in d/n, in the worst case. The convergence of the empirical distribution on a finite alphabet in `1 occurs at rate Θ( √ d/n), whereas the MLE entropy estimator
converges at rate O (√(
d n
)2 + log
2 d n
) , as follows from Wu and Yang [2016, Proposition 1]. So any
approach that upper bounds the entropy risk via `1 (as our Theorem 1 or Section 4 of Ho and Yeung [2010]) will be worst-case suboptimal for this class of distributions.
Nevertheless, for certain classes of distributions our bounds (Theorem 1 and Corollary 1) can significantly outperform the state of the art, for small and moderate-sized samples. To calculate the expected rate of our approach, we apply Hölder’s inequality, as in the proof of Theorem 1:
E|H(µ̂n)−H(µ)| ≤ ( E [ 2αα + H(α)(µ) + H(α)(µ̂n) ])1/α (E‖µ̂n − µ‖1) 1−1/α .
Now, as in the proof of Lemma 1 (recall that h(α)(z) := z lnα(1/z)) ,
EH(α)(µ̂n) = ∑
i∈[d] Eh(α)(µ̂n(i))
≤ eα−1 max z∈[0,e1−α]
h(α)(z) + ∑
i∈[d] µ̂n(i)<e 1−α
Eh(α)(µ̂n(i))
(i) ≤ eα−1 max z∈[0,e1−α] h(α)(z) + H(α)(µ) (ii) ≤ α α e + H(α)(µ),
where (i) follows from Jensen’s inequality and (ii) from (5).
By Berend and Kontorovich [2013, Lemma 6], we have E‖µ̂n − µ‖1 ≤ Λn(µ), where
Λn(µ) := 2 ∑
µ(j)<1/n
µ(j) + 1√ n
∑
µ(j)≥1/n
√ µ(j).
This quantity is always finite and Λn(µ) −→ n→∞ 0 for all µ ∈ ∆N (ibid). Thus, we obtain the bound
E|H(µ̂n)−H(µ)| ≤ ( αα
e + 2αα + 2H(α)(µ)
)1/α Λn(µ) 1−1/α. (10)
Finite support. For distributions with a large support but concentrated mass, the bound in (10) compares favorably to the state of the art, especially for smaller sample sizes. To illustrate this, consider a mixture of two distributions with support sizes d and D: µ′ is uniform over [d], µ′′ is uniform over d+ [D], and µ := pµ′ + (1− p)µ′′, for some p ∈ [0, 1]. The state-of-the-art upper bound for the plug-in estimator can be inferred from Wu and Yang [2016, Appendix D], and has the form
E|H(µ̂n)−H(µ)| ≤WY(d,D, p, n) := d+D
n + min
( C
log(d+D)√ n , log n√ n
)
for some C > 1; notice that it is insensitive to p. For a fair comparison to (10), our estimator’s only a priori knowledge of µ is that its support is of size at most d+D. By Proposition 2, we have maxµ∈∆K H (α)(µ) ≤ max {α, logK}α + (α/e)α. This allows us to optimize over α for each n:
OUR(d,D, p, n) := inf α>1
( αα
e + 2αα + 2 max {α, log(d+D)}α + 2(α/e)α
)1/α Λn(µ) 1−1/α.
Since µ has finite support, the Cover-Thomas inequality (2) also applies to yield an adaptive estimate when combined with (1). As t log(1/t) is concave, the latter has the form E|H(µ̂n)−H(µ)| ≤ E [ ‖µ̂n − µ‖1 log d+D
‖µ̂n − µ‖1
] ≤ Λn(µ) log d+D
Λn(µ) =: CT(d,D, p, n).
The comparisons are plotted in Figure 1 (Left).
Infinite support. In some cases our bound is nearly tight (at least for the plug-in estimate), such as for the family of zeta distributions µq(i) ∼ 1/iq with parameter q > 1. For this family, Antos and Kontoyiannis [2001a, Theorem 7] establish a lower bound of order n 1−q q on E ∣∣H(µ̂n)−H(µq) ∣∣. It is straightforward to verify6 that µq ∈ ∆(α)N for all q, α > 1. Thus, we can optimize our bound in (10) over all α > 1; the results are presented in Figure 1 (Right).
Acknowledgments and Disclosure of Funding
This research was partially supported by the Israel Science Foundation (grant No. 1602/19) and Amazon Research Award. We thank Ioannis Kontoyiannis, Igal Sason, and Sergio Verdú for enlightening conversations.

Review summaries:
The main contribution of the paper is to give a continuity bound on entropy: how far the entropies of two categorical distributions are, based on the L1-distance between these distributions. This bound does not depend on dimension, and is instead expressed in terms of a higher information-moment, which is similar to the expression of entropy, but with the log taken to a power alpha. Let’s call this alpha-entropy (note: not Renyi entropy).  Using high-probability bounds on the L1-distance between empirical and true distributions, this gives a parallel bound on the accuracy of the empirical plug-in entropy estimator. The paper shows that, over the class of bounded alpha-entropy distributions, the plug-in estimator is minimax optimal. For the class of finite-dimensional distributions, the plug-in estimator is not minimax optimal, but the paper also shows that for sub-classes with small alpha-entropy its rate is not that far-off from the optimal rate.

This paper proves an inequality for estimating the entropy by means of plugging in the empirical distribution that depends only empirical quantities, in the setting of iid samples from a discrete alphabet with potentially infinite size. This enables the statistician to certify directly in terms of the sample how well the entropy is estimated by the simple plug-in estimator. The result is proven under a mild moment condition which is known to be essential for consistent estimation, and further the authors show strong lower bounds on the risk when the moment assumption fails to hold. Further, minimax lower bounds are shown for estimating the entropy under this moment assumption that are sharp up to constant factors. In the final section these bounds are compared to pre-existing ones in various settings. 

Entropy estimation is one of the well studied and fundamental problems in the field of Information theory. The main goal of the paper is to study the entropy estimation by replacing the finite-support assumption (earlier works) with moment conditions. Under these moment conditions, the paper presents various interesting results (Theorem 1-4).