Dimension-free empirical entropy estimation
Authors: Doron Cohen
Aryeh Kontorovich
Aaron Koolyk
Geoffrey Wolfer
Venue: NeurIPS 2021 Poster (2021)
Keywords: entropy
estimation
dimension-free

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, {\em 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-of-the-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.

Dimension-Free Empirical Entropy Estimation
Doron Cohen
Aryeh Kontorovich
Department Computer Science Ben-Gurion University of the Negev Beer-Sheva, Israel doronvâpost. bgu. ac. il
Department of Computer Science Ben- Ben-Gurion University of the Negev
Beer-Sheva, Israel karyeh&cs ac.
Aaron Koolyk
Geoffrey Wolfer
Department of Computer Science
JSPS International Research Fellow Department of Computer and Information Sciences Tokyo University of Agriculture and Technology Tokyo, Japan geo-wolferem2. tuat. ac.
Hebrew University Jerusalem, Israel koolkkkaallaaall.o...... huji.uii.... ac.il
Abstract
We seek an entropy estimator for discrete distributions with fully empirical accuracy bounds. As stated, this goal is infeasible without some prior assumptions 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, provide the first finite-sample entropy estimates for infinite alphabets, nearly recovering the known minimax rates. Morcover, we demonstrate that our empirical bounds are significantly sharper than the state-of- the-art bounds, for various natural distributions and non-trivial sample regimes. Along the way, we give dimension-fre 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.
Introduction
Estimating the entropy of a discrete distribution based on finite iid sample is classic problem with theoretical and practical ramifications. Considerable progress has been made the case of finite alphabet, and the countably infinite case has also attracted fair amount of attention in recent years. less-addressed issue one empirical accuracy estimates: data-dependent bounds adaptive the particular distribution being sampled.
Our point of departure is the simpler (to analyze) problem of estimating discrete distribution μ in total variation norm II-IlTv = |1-I|,, where the most recent advance was made by Cohen et al. [2020]; see therein for a literature review. If şa is distribution on N and j,, its empirical realization based on sample of size n, then Theorem 2.1 of Cohen et al. states that with probability at least 8,
| P,ll
S
2 Vn jEN
Σ (M, 6
1og(2/8) 2n
(1)
major part of this research was conducted when the author was graduate student Ben-Gurion University of The Negev, Israel.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

This bound has the advantage of being valid for all distributions on N, without any prior assumptions, and being fully empirical: 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 optimoll 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 < co, an answer to our question is readily provided by combining (I) with Cover and Thomas [2006, Theorem 17.3.3,, which asserts that, for | w/1 S 1/2, we have
d
H(p) H(v))
|| //1, log || U11
where H(-) is the entropy functional defined in (3). Indeed, taking μs as in (1) and v to be jt, yields fully empirical estimate on [H(x)) Hl,, For fixed d < oo, 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 < oo [Paninski, 2003] as well as strongly universally consistent even for d = oo [Antos and Kontoyiannis, 2001a], and is among the few methods for which explicitly computable finite-sample 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 < M is not sufficient to yield any finite-sample information." Strengthening the assumption to X| < M, for any > 1, immediately yields finite-sample empirical estimates on EX - 1 E X,| via the von Bahr and Esseen [1965] inequality." 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 apply this insight the entropy estimation problem: the corresponding random variable is X = - log μu (f). where I ~ but rather than being given iid
samples of X, we are only given draws of
Our contribution. In Theorem I, we provide dimension- 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 natural and essentially the weakest one that makes any empirical bounds feasible, we demonstrate in Section 6, the rates provided by our empirical bound compare favorably against the state of the art.
argue in Theorem 3. As
2 Definitions and notation
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, ... For k E N, we write [k] = {i E N: S k). The set of all probability distributions on N will be denoted by Ag. For d LEN, N. we write A C Ag to denote those μ whose support is contained in [d].
We define the operator (-)², which maps any μ AN to its non-increasing rearrangement μtt. The set of all non-increasing distributions will be denoted by A := {u+ p E Aw).
We write R4 == [0, oc). For any & N + R4, and 2 0, define
HE) = Σ
{() blog = JENEEG)
(3)
For E R denote by [4| E R. the elementwise application of |-| to g. When & E Ay and a = 1, (3) recovers the standard definition of entropy, which we denote by H(E) = (g) For general
2 Even distinguishing, for X 2 0, between E.X = and EX = M based on a finite sample is impossible with any degree of confidence. Of course, ""= X, + I.. almost surely, hy the strong law of large numbers. 'Put = X- E.X: then Y < 2M. For 1 < a < 2, a sharper version the SahreEsseen inequality [Pinelis, 2015] states that E |Σ " < 2n(2M) "" which implies tail bounds via Markov's inequality. Better rates are available via the median-on of-means estimator, Lugosi and Mendelson [2019].

---

0, this quantity may be referred to as the oth moment of information. For h 2 0, define
(a)
| AN
H (p) = sh)
and also AN = Un2o A
(a) [K]
and A 4(a) [h] == AN n (0) Ns [t].
For n. E N and la E AN. we write X = (XI,..., X..) ~ le to mean that the components of the vector X drawn iid from μr. The empirical measure ie, As induced by the sample X is defined by f (j) = Eiemn 1[x; = j]. For any & E R and 0 < < co, the lp (pseudo)norm is defined by [|e|[ Ejen EE) and || supjen KE()
For a, h 0, and n E N, define the L, minimax risk for the oth moment by
(h) = inf sup uea [M]
E X,) - H(1),,
(4)
where the infimum over all mappings A: N - R...
3 Main results
Our first result is dimension free analogue of (2):
Theorem 1. For all a > 1, H (a) + IR+ is uniformly continuous under fg In particular, for all
μ, V. E A (a) satisfying || < 1/2, we have
1mx
|| 111 1/aa (2a"+1) +1( (w) 1/a
[H(μ) -H())
<
1 1lll1//0 (2a (H) (1)
The requirement in Theorem that a cannot be dispensed with, as the function H: A [ [M] R+ is not continuous under & for = 1 (see Remark following Lemma 5), and, fortiori, is not uniformly continuous. Thus, there can be no function F: T2? - R2 satisfying
H(u) - H(v) s F(ll= - M))
h> h>0, E (1)
with the additional property that for any sequences May vn l|e, - 2nll, + 0, it holds that F(cn, h) +
AN satisfying en
Perhaps surprisingly. it turns out that H (1) [M] R4 uniformly continuous under Ep for all a > 1, E [,
Theorem 2. There is a function F :R + RS such that
H()+) H())
F(llu~ h, a,,), h 0,0 1,p 1.00a>1,pE A (1)
with the additional property that whenever := I|, Mnll, + 0, we have F(En, h a, p) 0.
Remark. Although Theorem 2 establishes uniform continuity, it gives no hint as the functional dependence of the modulus of continuity F on a. p. h, and | =ll, 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 that for p = a 2 and fixed h, F(l vll, h, 2, 2) cannot decay at faster rate than 1/ //og(1/ || 11l 122))
Combining Theorem 1 with (1) yields empirical (under moment assumptions) bound for the plug-in entropy estimator:
*Since & dominates all of the f, norms, continuity of a function under é, trivially implies continuity under f. but the reverse implication is generally not true.

---

Corollary 1. For all a > 1, 0, E 2og z. and μa E AR [b], we have that
1-1/a
1/a
2 211
log (4/6)
H(w) - H(A)))
<
+ + + (H+)))))))
+ 6
vn
2n
holds with probability al least - 6.
In Section 6, we compare the rates implied by Corollary to the state 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()) oo does not suffice yield minimax rate for the L2 risk:
inf AN +R
sup
E (AI, Xx) -H))) = 0c.
PEAS
This technique yields an analogous result for the Ln risk as well. We strengthen these results in two ways: (i) by lower-bounding the [ risk (rather than Lz, which is never smaller), and (ii) by restricting μ AN [h] and obtaining finitary, quantitative lower bound:
Theorem 3. For a there is universal constant such that for all and n E N, we have R( (h) 2 Ch.
The above result complements - but is not directly comparable to Antos and Kon- toyiannis [2001a, Theorem 4]. Ours gives quantitative dependence on h but constructs adversarial distribution for each sample size nı; theirs asymptotic only but single adversarial distribution suffices for all n.
Remark.
Remark. Our technique immediately yields a lower bound of Ch² on the L2 minimax risk.
In contradistinction the a 1 case, where no minimax rate exists, we show that the plug-in estimator is minimax for all a > 1:
Theorem 4. The following bounds hold for the D, minimax risk:
(a) Upper bound: for all h > 0, 1,
2a-1h 1 1 log.
(h)
E N;
Vn
loga-1 n
further, this bound is achieved by the plug-in estimate H(jr))
(b) Lower bound: for each a >> 0, n E N there is an h > 0 such that
R(O)
2
3. log
Open problem. Close the gap in the dependence in the upper and lower bounds.
Related work
Continuity, convergence, moments 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(z)] 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 Ax, the plug-in estimate H(p.)) converges and Kontoyiannis, 2001a]. Silva (2018) 8] studied 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].
H({s) almost surely and in La [Antos

---

Entropy estimation. Recent surveys of entropy estimation results may be found in Jiao et al. [2015], Verdú [2019]. The ainite-alphabet case particularly well-understood. For fixed alphabet size d' < oc, the plug-in estimate is asympiotically 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 [201 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, 201 la. 2017]. The works of Wu and Yang [2016]. Jiao et al. [2015], Han et al. [2015]. Jiao al. [2017] characterized the minimax rates for the nigh-dimensional regime: small additive enror of requires ( / log d' samples. Building off of these polynomial-approvn -aprmiiiappoooiattiion based constructions, Acharya al. [2017] design an additional optimal estimator, this one based on 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- aalhabee 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 T,1 (and hence T.2) 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 B > 0 such that its risk decays as O(n Wyner and Foster [2003] showed that the plug-in estimate achieves a rate of O log (1 for bounded second moment, and this minimax optimal. Brautbar and Samorodnitsky [2007] exhibited a function of the higher moments that can be used in place of alphabet size to give multiplicative approximation to the entropy.
5 Proofs
5.1 Proof of Theorem
We begin with a subadditivity result for the ath moment of information (which we state for a > 0, even though only the range a will be needed).
Lemma 1. For O and pe, A (a) N
we have
((a (1 u1) s 20 + H(a) + (p).
Proof. Define (=));; [0 + R by 2 + z In lnnnn(1// (1/z), where (0)) = O. The function (a(a) is
increasing on [0, e0, and decreasing on (e- 0, 1]. The maximum is therefore achieved at and
max (2) =h(00 = e a =E
(5)
Now decompose H());
H (1H- - vl)
Σ
ho - v(i))= + Σ (w)(()) v())).
For the first term, since f E An, it must be that i(i E N: (e(i) > c 3 S e², and similarly for v. Thus,
((((i) - -v(i)) I (lfi: m(i) > 6 + 1i: v(1) e ) max (())
2E(0.1]
s 2 e e =
5

---

For the second term, notice that when (u(t) V (1) S ee the monotonicity of (()) implies
h( hh (I (()) - h (0)
and hence
Σ
h h ((((t)
Σ
(m(()))
ten())vu()Se
Σ
s H (n)+ (H)
Proof of Theorem I. The concavity argument in the proof of Cover and Thomas [2006, Theo- rem 17.3.3], immediately implies
H(p) - H(v)
< H(lи - (().
Then, via application of Hölder's inequality,
1 (e(i) v(i)
H(I v1)
Σ (Aii) (x) log
(ui))
|m(i) m(i) 1/0 log uuii v(il
1
s Σ (m(i) -1i) 1/(2-1/a) 1-1/a
1/a
Σ
(u(i) - v(i) log um(i) u(i)
1
w 1/a H (1 w))
The claim follows by invoking Lemma and the subadditivity of +> tl/a for t 2 and a >
5.2 Proof of Corollary
For and n E N, put On = (1 (12))(2m) In(1 101--11 11((n)) and define the support size S(h, n)
by S = (1/2m) exp(2n(h + a..)). Consider the distributions No (1, 0, ...) and μ, defined by p,, = (2n), and
(1) 2nS'
25i
We compute the Kullback-Leibler divergence and entropy:
DEL (Hollew) log 1/(nn)
15 n
(6)
1- 11((2))
H(mr) 0 h.
For x 2 2, always [x] x/2. Additionally, from 2na, 2 11, and exp(2nh 2n obtain that S > (1/4m) exp(2n(h a,,)), hence we also have that H(H,), ) h 2n In 2. Since
2,
DF 2n2 < 1/2 on (0) and > 1, it follows that H(u,,) 2 h whence (H(μ)) - H( 2 h/2.
To bound the L, minimax risk (defined in (4)), invoke Markov's inequality:
h P [ X,,) -H()) 4
EX X,, H(z) 2
4
It follows via Le Cam's 's two point method [Tsybakov, 2008, Section 2.4.2] that
h -n 14) >
h
R >
4
40
where the second inequality stems from (6).

---

5.3 Proof of Theorem 4
We begin with an auxiliary lemma, possible independent interest.
Lemma 2. For all E As and n E N, we have
H(p) 2 EH(ū)) 2 H(p))
inf 0<s<1
Σ
uiii log
1 u(()
log 1+
1 ET1
(iNiuu(i)<s
Proof. The first inequality follows from Jensen's, since H(-) concave and E,, μ.. To prove the second inequality, choose & > O, put J = {i EENN p(i) < $), and compute
((.))
E
Σ iENUJ
Pr (i) log (1)
(in( log (1)
iEJ
E
(i) log (1)
Emn(()) iiJ
log 1
Eies (i)
VENUJ
(H,)
where fi, the "collapsed" version of jr, where all of the masses J have been replaced by single mass equal to their sum, and the inequality holds because conditioning reduces entropy [Cover and Thomas, 2006, (2.1). We observe that ir has support size at most + 1/s and invoke Paninski [2003, Proposition 1]:
1 -
EH( (A,)) 2 H(ī)) - log
(7)
where j is the "collapsed" version of μ.. Now
H(A) = H())+ +
Σ
m(i)
log
Σ
u(i) log
Eies m(i)
(a(1))
iEf
TEj
1
H(H)
Σ
((i) log
p(i)'
which concludes the proof.
The first part of the theorem will follow from the following proposition.
Proposition 1. For 2 1, h > 0, E N and μ A (ai) [h], we have
log n Vn
log _
(1++
(()() H(P,))
inf 0<E<1
h + log
Proof. Since by Lemma 2, [H(μ)) - EH( = H(H) - (H(A,), it follows from the triangle and Jensen inequalities that
EJH(H) - H(
E(H(P,)) - EH( + H(H) EH(A.) Var [H( + H(μz) (H(A,)
log n + H(m) EH (p..))
(8)
where the variance bound is from Antos and Kontoyiannis [2001b, Proposition 1(iv)).

---

For any E > O, Lemma 2 implies
(H(
H(p))
E
(a)) log
log
1+ En
pe(i)
(ENi
H(p)
log
1
E
uiii)
log
-log
(1+
pe(i)
KEN:
<c
1-a
H(p)
log E
H (4)
log
1
En
where the second and third inequalities follow from the obvious relations
Σ
log 1
log
1-a
Σ
mli) log
S
log
=
1
1-a
H(a) (p.)
(1)
The claim follows by combining (8) with (9).
Proof Theorem 4(a). Use the fact that R, (
(h) S (H) H(P,)), invoke Proposition 1 with
E and use log(1 + x) S x.
We now prove the second half of the theorem.
Proof of Theorem 4(b). Let 0, N and define two families of distributions:
U1 = {11 = Uniform([""]) U2 = {112 = Uniform(A) : c [n²], |A|= n²]
Let h == 3 log" and note that 21 Ul2 S A (a)
N [h]. Let E' be the event that X = (X X.) has no repeating elements, ie X2, X, = n. Let μ4 E U1 E U2 and con- sider the values Px~uq uu (E) and Px~uy (E). For m N. define X(m) to be the smallest such that when uniformly throwing m balls into & buckets, the probability of collision is at least 1/2. Since (mm) is known
be least vm (and hence X(n2) n)) have lower bound of 2 on both Px-up (F)) and Px-uy (E). Define 14 as the distribution on N" induced by conditioning the product jur" on the event E, and define μ1] E analogously. Our key obser- vation is that conditional on E, (i) both are effectively distributions
1
ordered n-tuples from [n²), and (ii) of is uniform on ([n²), whereas 2 = Uniform (A) is uniform on (A) where (J)x =
TR) E Jh (= mx =k]
N, E N. Then
(h) 2 inf sup pe X~up"
[I(XX) H(m)
2 inf sup
E [IĀ((X) - H(W)]
P (E) x-
ueiliutz X~
2 inf
sup
E [IA(X) - -H(W)]
2 pelli Ully X X~
inf
E
[
- H(m)))
+ sup My Eu x X~
[in(()) H((2))]
11
X-ui
inf
1
E
[ H(mi)
+
E X~u3IE
[
H((2)]]
A 4
X=
Uniffrrm)())))
inf
E.
[(((X) - H(m))) +
[H((X) H((H2))]
X X~uapi E
X-
1
[i((x) - HHH())))))))))))((()))))))) +|(((()(x))))))))()))(()) H((2))]]
inf
E
A
4
X
1
1
[1(()])
H(mz)) |= 11 logn 1
h
3. log" n- n
Better bounds exist [Brink, 2012].
8

---

where (a) is from the law of total expectation (the complement of E is discarded), (b) and (c) are bounding supremum by an average, (c) is from the triangle inequality, and (d) is by observing that, by symmetry, the operators -pn--onior)(4))) [Ex=+eSEE [-]] and Ex-er H are equivalent. (There is minor abuse notation transitions after (c), since we write μl without specifying a particular member of U/. However, H2 only occurs therein as H( and this value is identical for all 22 E U2.)
6
Rates
Our bounds have the crucial characteristic of being empirical (under moment assumptions). When observe favorable distributions (even without priori knowledge of the fact), 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
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, n. in the worst case. The convergence of the empirical distribution on a finite alphabet in & occurs at rate O ((/d/n). whereas the MIE entropy estimator
2 log2 as follows from Wu and Yang [2016, Proposition 1J. So any approach that upper bounds the entropy risk via & (as our Theorem Section 4 of Ho and Yeung [2010]) will be worst-case suboptimal for this class of distributions.
converges at rate
Nevertheless, for certain classes of distributions our bounds (Theorem 1 and Corollary 1) can significantly outperform the state the art, for small and moderate-sizee samples. To calculate the expected rate of our approach, apply Hölder's inequality, in the proof of Theorem 1:
1/a
E ((,) - H(M) $
E 20 H + H()) (ia))
(Blli,, - -All 12-1/a
Now, as in the proof of Lemma (recall that (z) = 2In" (H(()((A)))
Σ Eh
(a) (i),
ie|4
ea-1
h (2) +
Σ
Eh Eh (f.,
max =E(0.et-a]
A, (i)<e'
a
e
max (()0 + H(a) (1)
+ (H),
xE(0,e1-a]
where (i) follows from Jensen's 's inequality and (it) from (5).
By Berend and Kontorovich [2013, Lemma 6], have Elli,, Hll S An),,, where
An = 2
Σ u(j) + Vn Σ v(()..
mf))1/n
#0)21/n
This quantity is always finite and (n)
0 for all An (ibid). Thus, obtain the bound
a _ - 20 2H())())
1/a
E(H(A - H(4)
An (u)
(10)
Finite support. For distributions with 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 and D: pz is uniform over [d]. u" is uniform over d d [D], and
pla (1 p) for some p [0, 1].
The state-of-ut of tf-thh-ar art upper bound for the plug-in estimator can be inferred from Wu and Yang [2016.
Appendix DJ, and has the form
E H((,)) - H(p)) < (dd = d+ D + min (c log(d + D)
log n /n
vn

---

Compwring our upper bound to the slate of art
Our bound for intiri alphabets dog tlg
pv)] Der eppm lood
P.g.e) Caeve Thrae beard
62
Log boc.dd value
sam.ppl
log somple
Figure Left: comparison of the three bounds for d 10, D 1000. p 0.95. Our bound considerably outperforms Wu and Yang [2016] on small samples, and performs nearly as well as the finite-dimensional Cover-Thomas bound. Right: for our value of g = 2. the log-log plot shows roughly the correct slope of 11/2.
for some C >> 1; notice that it is insensitive to p. For a fair comparison to (10), our estimator's only priori knowledge of μ is that its support is of size at most d + D. By Proposition 2, we have max H()) (m) I max {a, log K} + (a/e)². This allows us to optimize over for each n:
1/a An(1))=1//a
(-- + 2a +2 max {a, D)) +((a/))²)
OUR(d, D,p, n) = inf as1
Since has finite support, the Thomas inequality (2) also applies to yield an adaptive estimate when combined with (1). As t log(t//) concave, the latter has the form
d+I D
S An(u)) log d =:
((,,) H(z) S E || Hll, log
| 1l1
An(H)
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 (,,(1) 1/19 with parameter g 1. For this family, Antos and Kontoyiannis [2001a, Theorem 7] establish lower bound of order n on IE H((,) - H(H,)) is straightforward to verify" that 14 A (a) for all a >> Thus, we can optimize our bound in (10) over all a > 1; the results are presented in Figure 1 (Right).
Acknowledgments and Disclosure of Funding
This research partially supported by the Israel Science Foundation (grant No. 1602/19) and Ama- zon Research Award. We thank loannis Kontoyiannis, Igal Sason, and Sergio Verdú for enlightening conversations.
References
J. Acharya, H. Das, A. Orlitsky, and A. Suresh. A unified maximum likelihood approach for estimating symmetric properties of discrete distributions. In D. Precup and Y. W. Teh, edi- tors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 11-21. PMLR, 06-11 Aug 2017. URL attp://proceeding mlr, press/v700 a0000//caaya html.
Acharya, S. Bhadane, P. Indyk, and Z. Sun. Estimating entropy of distributions constant space. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
'One can, for example, apply Cauchy's condensation test, followed up by the ratio test.
10

---

A. Antos and I. Kontoyiannis. Convergence properties of functional estimates for discrete distributions. Random Structures & Algorithms, (9:3-4)1663-11 193, 2001a.
A. Antos and I. Kontoyiannis. Estimating the entropy of discrete distributions. In JEEE International Symposium Information Theory, pages 45 45, 2001b.
K. M. R. Audenaert. A sharp continuity estimate for the von Neumann entropy. J. Phys. A, 40 URL https:
(28):8127-8136, 2007. ISSN 1751-8113. doi: 10. 10.1088/1551-811144002288 addii.or//00 111000//1177111111///////11
D. Berend and A. Kontorovich. A sharp estimate of the binomial mean absolute deviation with applications. Statistics & Probability Letters, 83(4):1254-1259 2013. ISSN 0167-7152. doi: http://d...orr//000..0oooop.p.12 0.23.. article/pp1/9011171522200022
http:////www..iinciirrtttttt com/ scinnce/
D. Berend, A. Kontorovich, and G. Zagdanski. The expected missing mass under an entropy constraint. Entropy, 19(7):315, 2017. doi: 10.3390ee10070315. URL https://doi. org/10
3390/e19070315.
M. Brautbar and A. Samorodnitsky. Approximating entropy from sublinear samples. In N. Bansal, K. Pruhs, and C. Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, Janmary 7-9, 2007, pages 366-375. SIAM, 2007. URL attpp:/ddt acm org/citation. cfm?id= 1283422.
D. Brink. A (probably) exact solution to the birthday problem. The Ramanujan Journal, 28, 06 2012. doi: 00.1007/s113390011 011-433-19999
D. Cohen, A. Kontorovich, and G. Wolfer. Learning discrete distributions with infinite support. In Neural Information Processing Systems (NIPS), 2020.
M. Cover and A. Thomas. Elements of information theory. Wiley- Inter-interscceece [John Wiley Sons], Hoboken, NJ, second edition, 2006. ISBN 978-0-471-24195.99 0-471-24195-4.
K. Fukuchi and Sakuma. Minimax optimal estimators for additive scalar functionals of discrete distributions. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2103- 2107, 2017.
doi: 10.1 1099//0IT2011 800069000000
K. Fukuchi and Sakuma. Minimax optimal additive functional estimation with discrete distribution: Slow divergence speed case. In 2018 IEEE International Symposiun Information Theory (ISIT), pages 1041-1045, 2018. doi: 10. (090SSTT.2018.83377777
S. Golomb. The information generating function of probability distribution (corresp.). IEEE Transactions on Information Theory, 12(1):75-77, 1966. doi: 10.1 10.1109/TT..196 199617TT.996..1538844
Y. J. Jiao, and T. Weissman. Adaptive estimation of shannon entropy. In 2015 IEEE International Symposium Information T'heory (ISTT), pages 1372-1376. IEEE, 2015.
Y. Hao and A. Orlitsky. Data amplification: Instance-optimal property estimation. H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 Proceedings of Machine Learning Research, pages 4049-4059, PMLR, 13-18 Jul 2020. URL http: /ttp::/ttooeeeeee http:///oooceeee..e//ee/ mlr, press/ sases/vvi99 1a119/hho200 html.
Y. Hao, A. Orlitsky, A. Suresh, and Wu. Data amplification: unified and competitive approach to property estimation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL htt.h: http:/:://///oe//eee/e/eee www.eeiininiiinnnnnsseeeeeee cc/ papppp/r///////eeee 11134436642291144111110aaabbbab2
Paper. pdf.
S.-W. Ho and R. W. Yeung. The interplay between entropy and variational distance. IEEE Transac- tions on Information Theory, 56(12):596-5592, 2010.
J. Jiao, K. Venkat, Y. Han, and Weissman. Minimax estimation of functionals of discrete distribu- tions. IEEE Transactions Information Theory, 61(5):2835-2885 2015.

---

J. Jiao, K. Venkat, Y. Han, and T. Weissman. Maximum likelihood estimation of functionals of discrete distributions. IEEE Transactions on Information Theory, 63(10):6774-6798 2017. doi: 10.1 10.1100971122017773333557
H. Jürgensen and D. E. Matthews. Entropy and higher moments of information. Journal of Universal Computer Science, 16(5):749-79,, 2010.
N. Kusolitsch. Why the theorem of Scheffé should rather called a theorem of Riesz. Period. Math. Hungar., 61(1-2):225 229, 2010. ISSN 0031-5303. doi: 00.1007/s10988-00--3322 URL botps://doo org/10. 100.000000100900 010-0999-8--0-2-----
E. H. Lieb and M. Loss. Analysis, volume 14 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, second edition, 2001. ISBN 0-8218-2783-9, doi: 10.1090/
gsm/014. URL htttps://doi.... wwwgooog/... 1090 0at0//gsmm/////// 014.
P.-S. Loh. Convexity. 2013. URL hww.::tttt://eet httpcttss///wwwaaatee math. cmu. wttp:///pllo..acccca//a////oo//p
convexity-solie soln. sol..ddf.
G. Lugosi and S. Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. Found. Comput. Math., 1965):1145-1199) 2019. doi: 10.10077/110208-0999444222 URL
https://doi. httpp://ddi..or/11...o 100110000/0000 ottp://..110//000000000----00000
P. Massart. The tight constant in the Dyveetayy-ieffe-WWofoviiz inequality. Ann. Probab.,
1863):126--2283, 1990. ISSN 0091-1798.
URL http:://iinnsssjsoso..
owooooiiiiioooooooooooooooooooot sici7sici=
1091-179811990077 38: TTCITD> 1101 00 -ttp:/DD2.....0022-0oiiiii----- Qkrrigin-ii....
L. Paninski. Estimation of entropy and mutual information. Neural computation, 15(6):1111-125)
2003. doi: 10.11662/8999766332227777
L. Paninski. Estimating entropy on m bins given fewer than m samples. IEEE Transactions on Information Theory, (009):2200-2000 2004. doi: 10. 13.11/9...220048333660..
I. Pinelis. Best possible bounds of the Bahr-Esseen type. Annals of Functional Analysis, 6(4):1
29, 2015. doi: 10.15352/afa006-4111 URL /ostps://dol org/ 10. 15352/ af////af//// afo006-4--41- 06-4-1.
I. Sason. Entropy bounds for discrete random variables via maximal coupling. IEEE Trans. Inf. Theory, 191111111877111, 2013. doi: 10. 10.100/771.2011.27555. URL httpss/////oi org/10. 1109/TIT. 20130023222222 2274515.
H. Scheffé. A useful convergence theorem for probability distributions. Ann. Math. Statistics, 18: 434-438, 1947. ISSN 0003-4851. doi: 10.211/aam//117777039. URL https::/ddii.rr/// 1214/ 2oms//177733300
J. F. Silva. Shannon entropy estimation in oo-alphabets from convergence results: studying plug-in estimators. Entropy, 20(6):397, 2018.
A. B. Tsybakov. Introduction to nonparametric estimation. Springer Science & Business Media, 2008.
G. Valiant and P. Valiant. Estimating the unseen: An n/log(n)-sample estimator for entropy and support size. shown optimal via new clts. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC 11 page 685-694, New York, NY, USA, 2011a. Association for Computing Machinery. ISBN 9781450306911. doi: 10.1145/1993666.199333 1993797777661197777 URL
https: //doi. org/10. 10. 1ee./ 1993727.
G. Valiant and P. Valiant. The power of linear estimators. In 20/ IEEE 52nd Annual Symposium on Foundations Computer Science, pages 403-412, 201 doi: 10.1109/FOCS.201..88
G. Valiant and Valiant. Estimating the unseen: Improved estimators for entropy and other properties. J. ACM, 64(6). Oct. 2017. ISSN 0004-5411. doi: 10.1145/3125643, URL https: //doi.org/10 1145/3125643.
Verdú. Empirical estimation of information measures: A literature guide. Entropy, 21(8):720, 2019.
12

---

B. von Bahr and C.-G. Esseen. Inequalities for the rth Absolute Moment of a Sum of Random Variables, I r S 2. The Annals of Mathematicall Statistics, 36(1):299 303, 1965. doi:
URL https: org/ 10. 1214/ http:///mmm/mm////////////
Y. Wu and P. Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory, 67(6):370--3720, 2016.
A. J. Wyner and D. Foster. On the lower limits of entropy estimation. IEEE Transactions on Information Theory, submitted for publication, 2003.
7. Zhang. Estimating mutual information via kolmogorov distance. IEEE Transactions on Information Theory, 53(9):3280-3282, 2007. doi: 10. 10.1109971T.2200999112222
13


Reviews:
[{"review_id": "O1z2IYhj6A", "reviewer": "Reviewer_BrT9", "summary": "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).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The things that I like about the paper:\n1) I think the question considered in this paper is a natural generalization of the existing research. It is a very well motivated question from a theoretical perspective. \n2) The results presented in this paper are quite interesting and almost complete (except for the open problem posed by the authors). \n3)The paper is well structured and does a clear presentation of the results. The authors do a good job in placing their contribution with respect to the earlier work.\n4) This paper does both theoretical understanding and simulations.\n\nFew concerns/suggestions:\n1) As this is the first paper to study the entropy estimation problem under the moment conditions, I would love to see some practical applications. Do authors have any application in mind where the previous estimators were not sufficient? \n2) I would encourage authors to include an overview of techniques section where they describe the techniques that were used to prove the theorems and also comment about their novelty/difficulty. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would urge authors to think about both the potential societal impact and the practical limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "FT8abagMOo0", "reviewer": "Reviewer_2Z7U", "summary": "In this paper, the authors work on bounding the entropy estimate of a discrete variable from the plug-in estimator. The authors rely on their paper last year for density estimation to obtain the entropy estimate. ", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors prove that the plug-in estimator for discrete density described in Cohen et al 2020 can be used to estimate the entropy of that density. The estimate relies on a well-known result from Information theory described in the second edition of Cover and Thomas book (Equation 2). \n\nThe authors also mentioned that:\nFor fixed d < 1, no technique relying on the plug-in estimator can yield minimax rates [Wu and Yang, 2016]. The plug-in is, however, minimax optimal for d = infinity, [Paninski, 2003] and is among the few methods for which explicitly computable finite-sample risk bound are known.\n\nThe authors then say that instead of making an argument about d, they will argue in terms of moments of the distribution to prove that the plug-in estimator achieves minimax rates. \n\nI went over the proofs, and they seem correct to be and I did not thoroughly check them.\n\nIs this sufficient novelty from last year's results? From my perspective, the authors are only adding their results from last year and a minimal change to prove minimax rates. I have the impression that this theoretical paper does not actually provide much insight and adds to the discussion of entropy estimation. Or solves an open question in that field. \n\nI am ok with the paper being presented at the conference. I am just not excited about it.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no need for it", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "DRbFGLAtNFq", "reviewer": "Reviewer_9i5x", "summary": "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).\n\nUsing 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths:\n\n+ Extending the Cover-Thomas continuity bound in this way is beautiful, and can suggest other potential extensions. This is worthwhile sharing with the community. _(originality)_\n\n+ The paper, despite being quite technical, is clearly exposed. The proofs, as far as I can see, are correct and well-explained. _(quality, clarity)_\n\n### Weaknesses:\n\n- The paper makes one key claim which is not fully supported. It’s the idea that the bound is completely empirical and can be used to judge the quality of the plug-in estimator entirely from data. But this is only true under the moment assumption, because a non-empirical quantity still remains in the bound (Corollary 1). Even later in the paper this not-entirely-true claim is reiterated (`line 208`). _(quality)_\n\n- A lot of the significance of the result hinges on how meaningful the new moment condition is, what kind of distribution families it defines, and mainly whether it is a good quantifier of the difficulty of estimating entropy. This is not quite elaborated, with the closest argument in the paper, the lower bound which says that for alpha=1 we can’t get a vanishing minimax risk, answering this only in an extreme case. _(significance)_\n\n### Suggestions:\n\n* Theorem 4(a)’s upper bound form is not obvious from the main bounds. Reading through the proofs elucidates it, but I think the transition should be more front and center in the main body of the paper.\n* I’m not sure if the term on `line 85` is correct.\n* `line 64`, remove one _from_\n* Esoteric words like _finitary_ and _contradistinction_ can be distracting\n\n[Edit: Thank you authors for your detailed response. I am raising my evaluation, and I hope to see some of the discussion in your response in the paper itself!]", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It's hard to connect this work to any clear limitations or negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns in this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "BvmrSbB28_o", "reviewer": "Reviewer_5ypC", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**: This family of results is new to my knowledge. The technique leverages recent empirical bounds on estimating discrete distributions in total variation from Cohen et al [2020] as well as a dimension-free (infinite alphabet) version of a classic inequality of Cover and Thomas. It seems clear that the infinite-alphabet case has not yet been studied from this point of view, and the surrounding literature is well-summarized. Some new interesting open problems are raised as well (understanding the modulus of continuity for Theorem 2 as well as sharpening the constant in the minimax rates of Theorem 4). \n\n**Quality**: Overall the quality of the theoretical results is strong. I have not read the proofs carefully, but the arguments appear to be quite clean and mostly fit inside of the main text. It should be stated in the main text that Theorem 2 is proven in the Appendix. The authors acknowledge that in some cases their bounds are not tight and provide evidence as such in Section 6. Indeed, one expects to lose something in some regimes given the empirical/non-asymptotic nature of these bounds. I found the synthetic evaluation helpful in terms of demonstrating the strength of the bounds derived for small sample sizes as well as applying them to some infinite-alphabet scenarios. It is slightly disappointing though that the derived bounds don't outperform standard Cover-Thomas in Figure 1 Left. It would also be interesting to graph the empirical bound in the zeta distribution example Figure 1 Right.\n\n**Clarity**: The paper is carefully written and well-organized for the most part. All assumptions and theoretical results are clearly stated. My only suggestion is to state explicitly that in Section 6 you are deriving upper bounds that will be compared in Theorem 1. I got a bit confused reading it because the figure is on the previous page. The legend in Figure 1 Left could be improved by including the notation introduced in Section 6 for the various bounds.\n\n**Significance**: This paper provides some state-of-the-art bounds for entropy estimation from a few perspectives in the infinite alphabet case: empirical bounds, minimax rates under moment conditions, and a dimension-free variant of the Cover-Thomas bound. The open problems may attract attention as well.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Minor issues/typos:\n- p1 Lines 31-34. I believe that the discussion in terms of the alphabet size $d$ is mixed up. I thought Paninski [2003] proved that for fixed $d$ that as the sample size $n$ grows large that the plug-in estimator is optimal? And Wu-Yang [2016] considered the case where $d$ is allowed to grow with $n$ using estimators based on polynomial approximates? \n- p4 Line 123: typo: \"was was\"\n- p8 Line 212: Is the MLE the same as the plug-in estimator? If so, I would just stick with the \"plug-in\" terminology; otherwise please define the MLE.\n- p9 Line 216: I think that $O\\left( \\sqrt{ \\frac{d^2}{n} + \\frac{\\log^2 d}{\\sqrt{n}} } \\right)$ should be replaced with $O\\left( \\sqrt{ \\frac{d^2}{n} + \\frac{\\log^2 d}{n} } \\right)$\n- p9 Line 237: replace \"convex\" with \"concave\"", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the fundamental problem of estimating entropy of discrete distributions and analyzes the error of the empirical estimator for this problem. If one relies on L1 continuity a dependence on the domain size d is unavoidable (there will be a log d term). The authors define a new notion of continuity for entropy that provides nice bounds on the estimation error of empirical distributions. The paper is worth publishing. 
Decision: Accept (Poster)