Estimation of Entropy in Constant Space with Improved Sample Complexity
Authors: Maryam Aliakbarpour
Andrew McGregor
Jelani Nelson
Erik Waingarten
Venue: NeurIPS 2022 Accept (2022)
Keywords: Sample complexity
Data streams
Shannon Entropy

Abstract: Recent work of Acharya et al.~(NeurIPS 2019) showed how to estimate the entropy of a distribution $\mathcal D$ over an alphabet of size $k$ up to $\pm\epsilon$ additive error by streaming over $(k/\epsilon^3) \cdot \text{polylog}(1/\epsilon)$ i.i.d.\ samples and using only $O(1)$ words of memory. In this work, we give a new constant memory scheme that reduces the sample complexity to $(k/\epsilon^2)\cdot \text{polylog}(1/\epsilon)$. We conjecture that this is optimal up to $\text{polylog}(1/\epsilon)$ factors.

Estimation of Entropy in Constant Space with Improved Sample Complexity
Maryam Aliakbarpour"
Andrew McGregor
Jelani Nelson
Erik Waingarten 8
Abstract
Recent work of Acharya et al. (NeurIPS 2019) showed how to estimate the entropy distribution over an alphabet of size up to additive error by streaming over (k/e²) polylog(1) (1/6 /e) i.i.d. samples and using only O(1) words of memory. In this work, we give new constant memory scheme that reduces the sample complexity to (k/e²) polylog(1/e). We conjecture that this is optimal up polylog(1/e) factors.
Introduction
In the field of streaming algorithms, algorithm makes one pass (or few passes) over database while using memory sublinear the data it sees to then answer queries along the way or at the data stream's 's end. Researchers have developed various algorithms, such problems for over four decades [MP80, MG82, AMS99). For the vast majority of research in the field, the database is assumed to be fixed, and algorithms are then analyzed through the lens of worst case analysis.
well as memory lower bounds, for
In this work, we look to further develop the relationship between streaming algorithms and statistics, specifically studying statistical inference through low-memory streaming algorithms. this setup, rather than processing worst-case instance of some fixed database, our input is instead distribution D, and our algorithm processes ii.d. samples from with the goal of inferring its properties. Natural questions then arise, such understanding the tradcoffs between sample complexity, memory, accuracy, and confidence, or even understanding whether a low-memory algorithm exists at all for particular inference problem even if we allow the streaming algorithm draw unlimited number of samples. Work on streaming algorithms for statistical inference problems began in [GM07], which studied nonparameteric distribution learning, followed by the work of [CLM10], studying low-memory streaming algorithms for use in robust statistics and distribution property testing. Interest in the area later exploded off after work of [SVWI66 66,, which explicitly raised the question of whether low memory might place fundamental limits on learning rates, with flurry of works proving such limitations in response [CMVWI6 16. MM17, KRT17, Raz17, GRTI8, SSV19, GRT19, 19, GKR20, GKLR21], starting with work of [Raz19] on memory/sample tradeoff lower bounds for learning parities (D generates (xr (w, (u) for uniform in the hypercube with w unknown parameter, and the goal is to Iearn w).
In this work, following [ABIS19], foeus specifically the problem of estimating the entropy of an unknown distribution D over (1....,k) using a low-memory streaming algorithm over i.i.d.
Boston University Northeastern University, Supported by NSF awards CNS-2120667, CNS-2120603, CCF 1934846, and BU's Hariri Institute Computing; maryam.. alikbarourr@gaaillll com.
University of Massachusetts Amherst, mcgregorècs. umass. edass.edu. Supported by NSF awards CCF.
1934846, CCF-1908849, and CCF-1637536.
!UC Berkeley, einileeebbereeee eeerrreeeeeeeuu.u....... edu. Supported by NSF award CCF-1951384 1384, ONR grant N00014-18- 1 1-2562, ONR DORECG award
and Google Faculty Research Award. $ Stanfoor University, eawêcs... cols..collue columbia.c edu. Part of this work is supported by the National Science Foundation under Award no. 2002201 and Moses Charikar's Simons Investigator Award,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

samples. It is known that to estimate the entropy up to e additive error with large constant success probability, without memory constraints the optimal sample complexity
k log 2 2 })
1 = + max
log(k/c)
[VV17, VVII, 1V WY16]. Prior work by [BDKR05] also shows that a sublinear number of samples is possible for multiplicative approximation of entropy for distributions whose entropy is sufficiently large. The known optimal algorithms from prior work, however, must remember all samples and hence use ((x) words of memory". The algorithm of [ABIS19] uses only Q(1) words of memory, though at the cost of requiring an increased sample complexity of k Ö(1/e")o, In this work, our goal is to address the question: to what extent was the worsening of sample complexity in previous work necessary to achieve constant memory?
Our Contribution. We show that using ((1) words of memory", it is possible to obtain a sample complexity of k- Ó(1/e²), which is an improvement over the previous memory memory-efficient sample complexity bound which had cubic dependence on 1/c. The starting point of our algorithm revisits a simple estimator proposed by [ABIS19]. Their simple estimator uses O(k log" log"( (k/e))e²) samples to estimate the entropy in constant space. Our novel contribution is modification which estimates a bias incurred by the estimator; this change allows us to use only Olk log" l log" (1/e)/c²) samples. With the simple estimator with improved sampled complexity in hand, we show how an "interval-based algorithm, similar the one in [ABIS19], improves the dependence on is k ((1/e))
We remark that there has been other work on estimating entropy in the data streaming model [BG06, CCM10, HNO08, KNW 10, JW19], but those works are qualitatively different from our own current work and that of [ABIS19]. Specifically, they take the worst case point of view, where the stream items are not drawn i.i.d. from distribution, but rather the stream itself is viewed as a worst-case input and the goal is to estimate its empirical entropy. In that model, O(1) memory algorithms for the additive estimation to entropy provably do not exist, there is known memory lower bound of 2(1/2) bits [JW19].
Overview of Approach. We start by describing the basic algorithm of [ABIS19]. Their basic estimator takes a single random sample i ~ D, followed by N more i.i.d. samples. Then, they define N₂ to be the number of these N samples equal i. The estimate f. == N N₂/N is an unbiased estimator of of the probability ps of i according to D, and for large N, (1g()))))) is reasonable [[oog(1/p)
estimator for the entropy H (D) independent estimates. There is an additional technical detail, that P. may be zero (if N₂ is zero), which is fixed via oonessmoohhing trick of actually setting :=
of D. One can then average many such
:= (N, + 1)/N (which introduces an acceptably small amount of additional bias when N is sufficiently large).
Our improvement begins with the observation that log(1//2) is an unbiased estimator for H. We first propose similar but different estimator to the previous simple estimator. We also begin by taking a random sample ~ D; however, rather than letting N. be sampled from the binomial distribution Bin(N, we sample a negative binomial random variable X, which is the number of additional draws to see exactly more times (f is a parameter of the algorithm). Henceforth we let NB p) denote such negative binomial random variable, where the underlying Bernoulli experiment has success probability p. Then E[x] t/ps, and we will use log( X /t) as reasonable estimate of log(1/po) /p)). This estimator is also biased, but we can correct for this bias using a few more
samples.
Specifically, let Y = Xpa/t and consider the degree-r Taylor expansion of our estimate log( /t) and the ideal quantity log (1/p). As it will turn out, the expectation of the degree-r Taylor expansion of log( X /t) log(1 1 l/p;) log Y is a degree-r polynomial in pt. By drawing r additional samples,
As in prior work, we "word". or "machine word". to denote unit of memory that can hold θ (log(k/e)) bits. Essentially, machine word large enough to hold the name an item the alphabet, as well as the value of c.
"We use Ö(f) to denote a function which is O(f poly(log f))
" "More precisely, we provide a uniform algorithm which given any kt, e generates program with source code of size O(log log(1/e)) words, and that fixed program can then process any stream in ((1) words of working memory.
2

---

we may design an estimator for this polynomial, and subtract it from log(X (o(().). Correcting some of the bias in this way gives us our improved estimate for log(1/Pt). Our analysis of this scheme shows that a sample complexity of (k/e²) polylog(k/e) suffices. We then describe and analyze an improved algorithm in Section 3, which achieves (k/e²) polylog(1 (1/e) sample complexity by additionally incorporating a "bucketing" scheme, similar to one proposed in [ABIS19]. The idea is to partition the possibilities for values of X into disjoint intervals 11- y== [b be) for =
L and optimized choices of the breakpoints by, then estimate both Pr[X E Lr] and the conditional contributions to entropy conditioned on X E 1e for each l. By estimating separately for each I,, one can show that the conditional variance is reduced to obtain an overall smaller sample complexity of (k//²)- polylog(1 (1/e), 1/e), a strict improvement over that of [ABIS19]; details are in Section 3.
Lower bounds: Diakonikolas et al. [9GKR19] show lower bounds for mempry tradcoff's for testing uniformity of distributions. They construct a distribution p over [2k] such that for every i [k), the probabilities of the elements 2i and 2i 1 are (1 + /2k( and (1 /2)/(2)) while the order is picked randomly. They show that any streaming algorithm that uses m bits of memory, n samples, and can distinguish p from the uniform distribution over [2k] with high constant probability requires: (i) m n S2( { ), and (ii) if n S k0.9 and m 2 n²2 /k009 m n 52 A logg It is not hard to see that the entropy of the difference between uniform distribution and p (e). While this trade-off indicates a more general relation between the memory usage and samples, only () applies to constant memory algorithms (since (ii) requires n S ko.9). With word being log(k/c) bits, (i) leads to lower bound of (c/o//llol(/))) samples (the same as with unbounded memory). This leaves open whether the sample complexity for (-wo-word algorithms is ((kk/c) or (2k//²)) We speculate the latter, and we discuss our conjecture in Section 4.
A Simple Algorithm and Analysis
Let & E N, and D be unknown distribution supported on [k:. For any i E [k]. we denote the probability that E [k] is sampled by D as ps. The goal is to design a low-space streaming algorithm which receives independent samples from D and outputs estimate to the entropy:
HD)) def
k
pi log
(2) (-)- ps
-
E
log
( Pi
where logarithms above and throughout this paper are base-2, unless otherwise stated.
2.1 An Estimator for log(1/pt)
As mentioned in Section 1, similarly to [ABIS19] the algorithm aims to estimate (D) by taking sample i ~ D and estimating log(1/p;). Then, averaging these estimates will give an estimator for (D) (albeit with a super-linear dependence on k, which we fix in Section 3). We describe the estimator in Figure 1.
There are three main steps in the analysis. In the first, we show that the estimator has small bias. The
second is showing that the above estimator has low variance. Finally, we show that the estimator may be computed with few bits. In Figure 1, we set r O(log (1/)) and obtain an estimator whose bias is at most e and variance is at most Olog² k). It then follows that repeating the estimate of log(1 /p)) for Ollog" k/e²) i.i.d. chosen i ~ 'D gives the desired estimate with probability at least 2/3. These parameter settings establish the following theorem:
(logg ([flog(11/c) (1/c)) to
Theorem 1. There exists a single-pass data stream algorithm using O(1) words of working memory that processes a stream of Olke log² k log" (1/e)) i.i.d. samples from an unknown distribution DD on [k] and returns an additive approximation of H (D) with probability 2/3.
The space complexity in the theorem above follows since computing the estimator just requires maintaining integers in the sets [k),, [t]. and [r], as well as computing low-degree polynomial. To compute the average of multiple estimators in small space it suffices to compute the sum of the estimates where each estimator is computed in series. The sample complexity bound (given the specified parameters) in the above theorem follows directly from the sample complexity of LogEstimator. By virtue of the fact our estimators are based on negative binomial distributions (X
3

---

Subroutine LogEstimator(D,i)
Input: Sample access to distribution D supported on [A:], an index i E [k]] where p; + 0. Output: number r E I22,, which our bias estimate.
We draw enough samples from D so that i is sampled exactly times, and E N denote the number of samples taken.
2. For r E N, let f: R IR denote the degree-r Taylor expansion of log centered at 1, and h2 : [o, 1] + I be the degree-r polynomial satisfying
2 (
he(p) = Ez-
Finally, 9: [0. 1]" R is the linear function with g(p, .. p²)) - additional independent samples from D, and for j E [r]. we let B, be the indicator random variable that the first j samples were all Note that {Bz} can be encoded using single counter requiring log r bits.
hp)p). We take
3. We return
X log (x)
(B..B., B,)
Figure I: Description of the estimator for log(1/p:)
in Figure the number of Bernoulli trials until t successes), this in turn follows directly from the expectation of negative binomial distributions:
Fact 2.1 (Expected Sample Complexity of LogEstimator). Suppose we draw D and execute LogEstimator(P. i). Then, the expected sample complexity is
k
Σ
Ps r Pi
lk.
Although the number of samples we draw a random variable that only bounded in expectation, note that it implies the existence of a good algorithm that always has bounded sample complexity: namely, we can simply terminate the algorithm early and output Fail if it draws a large constant factor times more samples than we expect, which happens with low probability by Markov's inequality.
Before moving on to the showing the properties of the estimator, we verify that he(p) is degree-r polynomial.
Lemma 2.2. For any N, let f: R denote the degree-r Taylor expansion of log(2) centered at 1. Then, for any p > O and t E N,
f ((22 (2:0]
Z
he(p) = EZ-ND(t.))
a polynomial of degree at most r.
Proof. Recall that the random variable Z NB(1, is the number of independent trials from Ber(p) distribution before one sees successes. Furthermore, f is the degree-r Taylor expansion of log 2 centered and
1)
f(x) In(2)
12"
By lincarity of expectation, it suffices show that for every (I,...,7), Ez (Zp/t 1y is degree-j polynomial in p. Note that Z is sum of t independent Gco(p) random variables, so by expanding ( E G:p 1)s and applying linearity of expectation once more, it suffices show that
8
EG-CGo(L) [G.P]]] = =p'EG-God
[G'] p
Σ
p(1 k1

---

is degree-j polynomial in We note that this latter term, Eg GO] may be expressed as p (1 p). where (-- is the polylogarithm function (see [Wei]). (i_,(1 rational function, where the denominator is exactly př+1, which cancels the p²+ term In addition, the numerator of Li- p) is degree-j polynomial in p, which gives the desired polynomial representation.
p) happens to be
Finally, will be useful for the variance calculation to show that the correction term is always bounded, which show here.
Lemma 2.3. There exists a universal constant c > 0 such that, for any r, L E N, if we let g: [0.1]" be the linear function where g(p, : he(p), then g(b) E [-c, cl for all b {0,1)"
Proof. Recall g: -0. R is the linear function where p(p.p² p'..pp....... ...... p') hr (p). Hence, in order to show that y: {0, + IR is bounded, it suffices to show that the sum-of-magnitudes of the + coefficients of h4 is bounded. Since we have
[1(210]
Z .
(-1) EZ-NB(e.))
(p) EZ-NB((,))
(2(2)
i
(Zp/t ut 1)'} is degree-i polynomial in and the bound (3) implies that, for each i E {I.....r} } these polynomials are at most (O v)) in magnitude. Furthermore, since these are degree-i polynomials bounded in [0, 1], we conclude are at most (O(i/VE)) In
Notice that in Lemma 2.2, we showed that each Ez
(by Lemma 4.1 [Shel3]), that the coefficients in Ez (Zp/t 1)']
particular, we have that the coefficients of hp(p) are at most
Σ (Ou/v)) S Σ (OGIv))'= O(1/VT)
because r/vl can be made an arbitrarily small constant. To show that y: {0, 1}" + R. is bounded, we add the magnitudes of the coefficients, which is O(r/vB) O(1) when O(log and 1 t O=Oool"((1/e))
2.2 Bounding Bias of Estimator
Lemma 2.4. Lei D be any distribution and consider any i [k]. for E (0, 1), we instantiate LogEstimator| (D, with = O(log(1/e)) and Ologg 2 (1/c)), which produces the random variable then E[n] log S.
The remainder of the section constitutes the proof of Lemma 2.4, which will follow from sequence of claims.
Claim 2.5. an execution of LogEstimaooo let and n be defined as in Line and Line of Figure 1, and let Y X pe/l. Then,
E[n] log ()) Ex[h(Y)).
where h(2)) is the error in the degree-r Taylor expansion log
Lemma 2.6. For any E (0, letting r @(log(1/e) and = (llo2((1e)), we have that for p. 0, Exx](())]] S.
5

---

Proof. Whenever E (0, 2), we may write (2) as its Taylor expansion centered at 1. In particular, we have
hn()|| = log(2) f(=)
(-1)et(2=-1)
1)
(-1)et)
-1
(2(2)
In(2) 1=1
e
(-
In(2) bmr+1
(z 1)" 0c
(2 - 1)e
1 2
(= 1)e
1
Σ 1-1
(1)
ln(2)
r r+ l
In(2)
r+
First, consider the case that E (1, 2). Then, we may re-write (1) as
(z - 1)e
1a 1
In(2)
r+7
1
(z (2-18 1)2e-1
+ 28 - (z 11) 1)
T + 28
1
(2)
(2(2)
r + 28
Whenever (1,2), then every term in the right-most summation of (2) is positive; indeed, (z - 1)2(-1/(r + 2f) > 0 because 2 > 1, and (r + 20) + 28 - 1) > while (z (2-1) 1) < 1. In particular, for z E 2). we may upper bound the right-most summation in (2) by upper bounding each term. For every 8 E N, we may upper bound each term
(2 (2-1) 1)26-1
r + 26
(2 1)2c-1
2
(z (2)
<
(z (z-1) 1)
r + 28
26
28
266-1
(2 1)28-1
(2
1)26
2 1
2
Plugging this upper bound into each term of (2), we have that x E (1,2) satisfies
[2 - 1)28-1
(2 - 1)26
[h(2)] < |2- 11"
(n(2)
28
28
20 (2)
(2- 1)e²
|a 1
= 1/2 11"| 1 log z/.
We now consider E (0, 1). Here, every term in the might-most summation in (1), (-1)(221))/- (), is positive. So upper bound
(2- - 1)e
| =|= ==2-11 11"
---
1)
In(2) t=1
+ f
1
(2 1)c 11e.
12 1
In(2)
1z 1 log =|.
The final case occurs when 2 2 2, and we may no longer use the series representation. However, in this case, we have
Σ 2 11--11
1
[b(2)) S + < log =|
log z + +r|z 11
E=1
In all cases, we have
(Ex))]] s Ex[[((Y)]] s 0()) Ex Y 11+23
+ +e/2+ Ex[1 11/10) log(1/Y)),

---

thus suffices to design an algorithm to estimate (4). Our approach to use a bucketing scheme. At a high level, we partition the range of X into I. intervals: I, l,...., .., Tt. expectation of log(X X/U /t) in each interval separately. Then, we take the weighted average of these where we used the fact that Y > 0 and r (log(1/)e) to say (9/10)" < <//2. In order to bound the above two quantities, we use the fact that the random variable Y is subgamma random variable and thus has good concentration around its mean (which is for the case of Y), giving the desired inequality.
Definition 2.7 (Subgamma Random Variable). For a, B E IR a random variable with expectation is (a, B)-subgammaa for all X E R with [*] < B/
2²
4 (A) def In E ((2-H)
2(1 - A|B1)*
It is not hard to verify (see Section B) that the random variable Y is centered at 1, and that there are constants a, 3 E 12z0 so Y is (ax/ /1.B8/0)-sugaamma Then, by taking the Taylor expansion of B[cA(Y-1)], have that for any [^] t/B, and any N,
Ex
- (X
jl X
exp
a²>2
S
a'j! t/2
e
(3)
2t(1 A8/t))
by picking À = vt/a, which is less than t/3 for large enough t. Letting j = r 1 and setting
t= O(r", get the desired bound of o(e/r). ). In order to bound Ex[ 0 { 1/10} log(l/Y)) we compute explicitly, and recall that X 2 t, so that the above event is satisfied only if p; S 1/10.
11 I < 1/110/
Ex(1 (Y < 1/100 log(1/))) < Ex
Y
=
t/ 1/(0p)))
Σ t=t
p5(1 -p;) et 1-1
-p)
t. S t
max
(ell - 1) 1-1
1-1
pf
Ep,
10p,
(e)pp)
1-2
pi - exp(-2(()).
max 10 (E(p.)((10p))
t-1
3
Improving Sample Complexity via Bucketing
In this section, focus estimating the expected value of log /t) with error most Our goal here is to remove the poly k) dependencies in the sample complexity of estimation. In particular, prove the following theorem, which improves on the dependence of l in Theorem 1.
Theorem 2. There exists single-pass data stream algorithm using O(1) words of working memory that processes stream of O(k log (l/ee()))/////a/ (1/e)/e²) i.i.d. samples from unknown distribution 'D on [k] and returns an additive e approximation of (D) with probability at least 2/3.
Given the work done in Section 2, it will suffice estimate the quantity H (we give the explicit reduction in Lemma 3.1 shortly):
H = E B.-DD.X-N(B.,)) (X/t)),
(4)
where is set to (1oee() such that we can then apply the correction term of Section 2. Recall that the randomness in the above expectation is taken over the random choice of ~ D, and X is negative binomial random variable drawn from (B pt). First, we show that it suffices to estimate (4) in order to estimate the entropy, given tools from Section 2.
Lemma 3.1. Consider a fixed distribution D. and for e > O suppose Á E R is such that |H A S
Then, there exists a O(1) word streaming algorithm which given H and using an additional (llo((/ee)ee)) independent samples from DD outputs an estimate the entropy Df up error 12e with probability at least 0.9.
We compute the conditional
conditional expectations, where the weights are determined by the probability of the intervals.
7

---

Unbounded X:
As specified above, the random variable X is a mixture of negative binomial random variables, so X may be unbounded. addition, we had sampled i D where pj was very small, X's value will tend to be very large. It will be convenient to introduce parameter X max E N and consider the random variable X' == mmiin( x m.x). Let H denotes the expected value of X':
H = = [log(X X' x'/t)]
For the rest of the section, we will seek to approximate H, and the fact that this is a good estimate for H follows from the following lemma.
Lemma 3.2. Let D, and let X and be a negative binomial random variable from (B pi). Let X' be the bounded version of X: X' = min(X Xmax). Let t E N and e E (0, If we set
X Xmax= = (k/())2))), then
H-H -E,, log X /t) - log X x1/sssc sc.
Comparison to related work: It is worth noting that the proofs in this section are inspired by the work of [ABIS19]. The authors used a similar bucketing technique to estimate entropy. While the structure of our proof is similar, there are subtle differences between our work and what they did. First, we are focusing on estimating different quantities. In particular, we work with an unbounded random variable while their estimator is bounded. Moreover, they have two-step bucketing system where they draw a sample i and two estimates for p;: they use one estimate for detecting which bucket falls into and the second one to estimate entropy in that bucket. One of the complications of this approach is that the second estimator may fall into a different bucket; Thus, they have to "clip" the second estimator make sure it is close the bucket of the first estimator. We have circumvented these hurdles by using the same estimate for detecting which bucket we are in and estimating log( X/ /t) in that bucket.
The algorithm:
We write it in terms of conditional expectation in the intervals.
X' E le] BEWD,
[log(X'/() (Lg | 1X
1
q
Let qe denote the probability of X' being in Le, and Hy denote the conditional expectation in Le. Our algorithm estimate qe and Hę for each interval to find estimate for H. Below we give brief description of our algorithm, and the pseudocode can be found in Algorithm 1.
Below, we define by = t < bj <... < by = Xmax to be L + parameters (which we will set shortly) that denote the boundary points of the intervals:
I b,b)
I 1],
1. =
1br.1r.-1, (br.-1,br.) br.)
For each interval It, we draw rt samples from D. namely i...... b,, ~ D. For each éz. we start drawing samples from D in the process of drawing negative binomial random variable X; ~ NB(1, Pk,); ); then, we will set X', min(X,, "i,xxmac max)) Furthermore, we will only consider x 's that fall in It, which means that we can stop early we already know X; will be too large. In particular, if we draw by samples and have not observed instances of ēj. we can already conclude X is not in Iç and stop sampling. Among these rt samples f let o₁ denote the number of X 's that fall into 4g We estimate the weight of each bucket by q ce/re. Te. For the last bucket, we set qr in a way that the sum of the weight is one:
Ci rt
Vjj I...., L
dr f Σ बr.
Also, we compute an average of log (x//t) of such X''s and denote it by Ae:
Å H - 1(x E Te) log( (1))
L.
In these definitions, we take A = log(br/t) if cf = 0 and for the sake of analysis A. = Hy Ca 0 for i < L; note that the value of A, will be multiplied by 0 in this case and hence we may define A, arbitrarily. Our estimate for H is the weighted sum of A.. i.c., A = -/ 9e Ar
8

---

Algorithm 1 Estimating E[log X /t] via Bucketing
1: procedure LOGESTIMATOR(&; 6, sample access to D)
2:
Ā +-0 for L = 1,2..... do
3:
4:
Ce 50 H 5
5:
for rg times do
6:
Draw i D
7:
Draw by samples from D but terminate early if occurrences of are observed.
8:
X number of samples drawn
9:
H. + H. + (//)))/)))))))/)) 1(X E lr} and es + ci + 1fx E 1r}
10:
Define
Hi/ce
if > 0 if 0, l < L if c l =
ce/rre
if < L
فe +-
and H.
He log(br./t)
1 -i=1 q if f = L
b Note that if cr = and < I,, the definition of H is just for analysis since in that case
q. = O and the output does not depend on A.-
11:
H - fl + +
Lemma 3.3. Define Error Et
-t=1 Qe H. mmax and (re E N: : E [T.]], we have
Et=r ae
He. For any setting of bo ... br.
qi log (al (bL/be-1)
qe log" (bz /b-
E[Error? 2
6
rt
rt +
Proof of Lemma 3.3.
We start by rewriting Error follows:
F.
1.
Error
(āe 9o) H. Σ
91
A - He)
1=1
L-1
1-1
L-1
(â: qe) He+
1
---oo
qe 1+
Σ
H + Σ
He
Hi)
1=1
8=1
t=1
Σ (āe ( (At (H)
Σ
q8 [H He)
(5)
Using the fact that pe is an unbiased estimator for qe and that for é S 1, H an unbiased estimator of He even when conditioned specific value of qe, we have
ve # l' [ - E (qe ge) (A AL) (Âe- qe. (A (o-AAL) #1)]
and
ve E E [. Ho) (A - Hr. ] = =0.
Hence,
27
E E[Error]]
< 2 E
Σ (â: 4r) (H (B.-Hi.)
+ E
Σ 2e H Hi)
2 E
Σ (ā: qr)²
h-1
(H. [H H..)
+ 2 E
s H Hi) 2
L-1
< 2
Σ
Var[qe] (log(bl/be-)
+ Σ
E
(He-
-H)) =He $1
(6)
6m1

---

Recall q is the average of ra Bernoulli random variables, each set to with probability qe. Hence,
Varl = qe(1 ge)
(7)
Tt +
To bound the expectation of (He H2)² recall the definition of He: g: take sample i ~ D, then X ~ (B(t, p4) to check whether X' E Ig; so, we increment C and use log(X' /t) as an estimate for He. Crucially, if we condition any non-zero value of cz. H, is unbiased estimator given by averaging e, values, all of which are bounded in the interval (oog(bei/t)) log(be/t)) If ct = 0. the estimator sets H, to log(bs/(). In particular, since for all non-zero positive integers, 1/c < 2/(c+1) 1), we may write
(e Hi) 21
(log(be/() (og(bb-i10 1/0
Pricee = =0] -log" Obe (be/be-1) + 2
Ce +
S qe(( q0) r. (be (b//bb-l) + 2E.
log (be/beel))
Cr +
1
2
log" (be/be-1)
log2(ee/ (be/be-1)
1 1+
ge(1 + +r))
3
log (be/be-))
(8)
qe(re +
where the second last inequality used that g(1 q)" - 11((r (r/r++1) 1) for any q E [0. 1] and that since
Ce is distributed as Bin(ge,re), we have E,, [(c + 1)-1] S 1/(ge(re + +1). The proof of this last inequality appears as Lemma 6 in [ABIS19], which reproduce below for convenience:
(in.Bi(
Σ
()
g/(1 (1-9) 2)
(1-1)--
Σ (0-10 I=
I+c
1+1
1+1
1=0
1 (1 9)"
q(r +
q(r 11)
Substituting Eq. 7 and Eq. 8 into Eq. gives the lemma.
We consider the following setting of parameters, where we let L loog k," such that have bu t. and
Vee (I....,, L 1), def
th
by def th and let re der 80 80 (oog2(bz//)) (be/
(log (5) k)3
fairly straightforward to show that Algorithm uses constant number of words. Note that re (similarly b,'s 's can be computed from rt-1, so we do not need to calculate and store all the r rz's beforehand. Also, to compute ÂL, we do not need all the qe's. We only need to keep a running sum of :: Thus, we only need constant number of words of memory. We analyze correctness simply by bounding the variance. Namely, the remainder of the section will be devoted to proving the following lemma, which will imply that our estimator will be within te of A with constant probability.
Lemma 3.4. The expected sample complexity of the algorithm is Okk log (ogee//)))))// (1/e)/e²) and returns an =0(e) approximation with probability 0.9.
Conclusions
We presented algorithm for returning additive approximation of the Shannon entropy of distribution over [k:]. The algorithm required O log' (1/e)) i.i.d. samples from the unknown distribution and a constant number of words of memory. In terms of the e dependence, this improves over the state-of-the-arr [ABIS 19] by factor L/E in the sample complexity. More generally, expect that the technique used, that of correcting the bias via low-degree polynomials will be useful in the context of the other inference problems in the data stream setting. The main open problem is determining whether the sample complexity of our result is optimal. We conjecture that this is the case, up to the poly(log(1//))) (1/c)) factors. See Section D for a discussion of this conjecture.
'Recall that log" is the number of iterated logarithms (base 2) before the result less than equal to 1.
10

---

References
[ABIS19]
Jayadev Acharya, Sourbh Bhadane. Piotr Indyk, and Ziteng Sun. Estimating entropy of distributions in constant space. In Proceedings of the 32nd Annual Conference on Neural Information Processing (NeurIPS), pages 5163-5174, 2019.
[AMS99] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1): 58(1):13371477, 1999.
[BDKR05]
Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld. The complexity of approximating the entropy. SIAM J. Comput., 35(1)) 2005.
[BG06]
Lakshminath Bhuvanagiri and Sumit Ganguly. Estimating entropy over data streams. In Algorithms ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings, pages 148-159, 2006.
[CCM10] Amit Chakrabarti, Graham Cormode, and Andrew McGregor. A near-optimal algorithm for estimating the entropy of a stream. ACM Trans. Algorithms, 6(3):51:1-51:21, 2010.
[CLM10] Steve Chien, Katrina Ligett, and Andrew McGregor. Space-efficient estimation of robust statistics and distribution testing. In Proceedings of the 1tt Annual Conference Innovations in Computer Science (ICS), pages 251 251-265, 2010.
[CMVW16] Michael S. Crouch, Andrew McGregor, Gregory Valiant, and David P. Woodruff. Sample complexity vs. space complexity. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithmms ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of L/PIcs, pages 32:1-32:15. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2016.
Stochastic streams:
[DGKR19] Ilias Diakonikolas, Themis Gouleakis, Daniel M Kane, and Sankeerth Rao. Communi- cation and memory efficient testing of discrete distributions. In Conference Learning Theory, pages 1070-1 106. PMLR, 2019.
[GKLR21] Sumegha Garg, Pravesh K. Kothari, Pengda Liu, and Ran Raz. Memory-sample lower bounds for learning parity with noise. Proceedings the 25th International Workshop Randomization and Computation (RANDOM), pages 60:1-60:19, 2021.
[GKR20]
Sumegha Garg, Pravesh K. Kothari, and Ran Raz. Time-space tradcoff's for distinguish- ing distributions and applications to security of goldreich's 's PRG. In Proceedings of the 24th International Workshop on Randomization and Computation (RANDOM), pages 21:1-21:18, 2020.
[GM07]
Sudipto Guha and Andrew McGregor. Space-efficient sampling. In Proceedings the 11th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 171-178, 2007.
[GRTI8]
Sumegha Garg, Ran Raz, and Avishay Tal. Extractor- time-space lower bounds for learning. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 990-1002, 2018
[GRT19]
Sumegha Garg, Ran Raz, and Avishay Tal. Time-space lower bounds for two- wooppass learning. In Proceedings of the 34th Computational Complexity Conference (CCC), pages 22:1 12:339, 2019.
[HNO08] Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. Sketching and streaming entropy via approximation theory. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (IEEE), pages 489-498, 2008
[JVWW15] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of functionals of discrete distributions. IEEE Trans. Inf. Theory, 61(5):2835-288) 2015.
[JW19] Rajesh Jayaram and David Woodruff. Towards optimal moment estimation in streaming and distributed models. In Dimitris Achlioptas and László A. Végh, editors, Approximation. Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, volume 145 of L.Pless, pages 29:1 29:1-29:21. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2019.
11

---

[KNWI0]
Daniel M. Kane, Jelani Nelson, and David P. Woodruff. On the exact space complexity of sketching and streaming small norms. In Proceedings of the Twenty- Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, page 1161-1178, USA, 2010. Society for Industrial and Applied Mathematics.
[KRT17]
Gillat Kol, Ran Raz, and Avishay Tal. Time-space hardness of learning sparse parities. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1067-1080, 2017.
[MG82]
Jayadev Misra and David Gries. Finding repeated elements. Sci. Comput, Program.. 2(2):143-152, 1982.
[MM17]
Dana Moshkovitz and Michal Moshkovitz. Mixing implies lower bounds for space bounded learning. In Proceedings of the 30th Conference on Learning Theory (COLT), pages 1516-1566, 2017.
[MP80]
Ian Munro and Mike Paterson. Selection and sorting with limited storage. Theor. Comput, Sci., 12:315-323, 1980.
[Raz17]
Ran Raz. A time-space lower bound for a large class of learning problems. In Proceed- ings of the 58th IEEE Annual Symposium Foundations of Computer Science (FOCS), pages 732-742, 2017.
[Raz19]
Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning. J. ACM, 66(1):3:1-3:18 18, 2019.
[She13]
Alexander A. Sherstov. Making polynomials robust to noise. Theory Comput., 9:593- 615, 2013.
[SSV19]
Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Memory-sample tradeoffs for linear regression with small error. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 890-901, 2019.
[SVW16] Jacob Steinhardt, Gregory Valiant, and Stefan Wager. Memory, communication, and statistical queries. In Proceedings of the 29th Conference on Learning Theory (COLT), pages 1490-1516, 2016.
[VV11]
Gregory Valiant and Paul Valiant. The power of linear estimators. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 403-412, 2011.
[VV17]
Gregory Valiant and Paul Valiant. Estimating the unseen: Improved estimators for entropy and other properties. J. ACM, 64(6):37:1337:41, 2017.
[Wei]
Erie W. Weisstein. Polylogarithm. from accessed Feb. 9 2022.
Wolfram Web resource. Last
[WY16]
Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Trans. Inf. Theory, 370))3370- 2016.
12

---

Checklist
1. For all authors...
1.1 Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
1.2 Did you describe the limitations of your work? [N/A] The model assumes that the
stream consists of fid samples. This is discussed in the introduction.
1.3 Did you discuss any potential negative societal impacts of your work? [Yes]
1.4 Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
2.1 Did you state the full set of assumptions of all theoretical results? [Yes]
2.2 Did you include complete proofs of all theoretical results? [Yes] Proofs not included in the body of the paper are included the supplementary material/appennixx
3. If you ran experiments...
3.1 Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
3.2 Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
3.3 Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
3.4 Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
4.1 your work uses existing assets, did you eite the creators? [N/A]
4.2 Did you mention the license of the assets? [N/A]
4.3 Did you include any new assets either in the supplemental material or as a URL? [N/A]
4.4 Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
4.5 Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
5.1 Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
5.2 Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
5.3 Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "zKztM8zKBee", "reviewer": "Reviewer_JqRg", "summary": "This paper considers entropy estimation of an unknown discrete distribution of alphabet size $k$ under memory constraints, specifically constant number of \"words\". Previous work proposed an algorithm whose sample complexity is $\\tilde{O}(k/\\epsilon^3)$. This work improves the sample complexity to $\\tilde{O}(k/\\epsilon^2)$. \nThe entropy of a discrete distribution can be interpreted as the expectation of $\\log(1/p(X))$. Therefore, the crux of the algorithm is in averaging over multiple instances an estimate of $\\log(1/p(X))$. The key innovation in this work is a low-bias, low memory algorithm to estimate $\\log(1/p(X))$. Instead of using a plug-in estimate as previous work, this paper samples a negative binomial random variable to see an element $i$ exactly $t$ times. Although this is an unbounded random variable, the crux of the improvement lies in noticing that in expectation, the number of samples is approximately $k$ for this step. Using a few more samples, the Taylor series approximation of $\\log(1/p(X))$ can be computed and the bias is in turn the error of the Taylor series approximation. Instead of averaging these estimates, the paper considers a method of bucketing similar to previous work. ", "questions": "Included in the previous section. ", "limitations": "Perhaps the main limitation is lack of a matching lower bound. However, the authors have adequately addressed this difficulty in the appendix. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Statistical estimation/learning under memory constraints has started recently receiving attention. While the few existing algorithms in the specific area of distribution learning/property estimation under memory constraints are relatively straightforward, their analysis is not. The paper provides an algorithm that improves the sample complexity of estimating entropy using constant number of words. The main idea behind the improvement is crisp. The presentation is quite clear and the paper is well written. \n\nThe lack of a matching lower bound is a weakness but the authors have adequately addressed that in the appendix. One suggestion is to cite the following paper (https://arxiv.org/pdf/1907.05816.pdf, Theorem 7) that provides an improved lower bound in the streaming model for additive entropy estimation, compared to CCM10. \nTypo in line 246 - should be p_i instead of q_i? ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "oneZ_S_Ozkb", "reviewer": "Reviewer_43yP", "summary": "This paper investigates the entropy estimation problem under O(1) words of memory restriction, improving the current state-of-the art sampling complexity O(k polylog(1/ε)/ε^3) by a factor of 1/ε, where k is the alphabet size. The proposed algorithm inherits the framework of previous works, i.e. firstly take a random sample id, and use the number of samples equal to i to estimate p_i. Instead of sampling from binomial distributions, the new algorithm samples negative binomial variables to make the bias able to be estimated, and then adopt a Taylor expansion to correct the bias. Finally by incorporating a bucketing strategy, the reliance of sampling complexity on k is reduced, yielding a strict improvement compared with the previous work.", "questions": "The sample complexity is only bounded in expectation due to the property of negative binomial, which implies that the practical complexity may severely exceed the expected one with small probability.", "limitations": "1. The authors assume that r is far less than sqrt(t) in line 148. But they then states that r = O(log(1/ε)) and t = O(log^2(1/ε)) in line 149, which imply r ≈ sqrt(t). It seems inconsistent with the previous assumption.\n2. The proof of Lemma 2.6 seems flawed, since when z > 2 the Taylor expansion of log(z) centered at 1 does not even converge.\n3. Some other polynomial expansions e.g. Chebyshev series, are proven to outperform Taylor expansion. Is it possible to further improve the complexity by using Chebyshev series?\n4. The organization of the paper could be further improved.  Some conclusions (e.g. eq (2), line 177) are referenced before their first appearance (e.g. eq (2), line 144).\n", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The idea of using negative binomial variables instead to improve sampling complexity is interesting, and to my knowledge it is original.\n2. The idea of using Taylor expansion to estimate the bias is also impressive. This is the main contribution of this paper, which substantially improves the sampling complexity.\n3. The claims of the paper are all supported by theoretical results, which is comprehensive and convincing.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AstPb9V_FKK", "reviewer": "Reviewer_LvWV", "summary": "This paper considers estimating the entropy of an unknown distribution over an alphabet of size $k$ from independent samples. The model they consider is the *sample streaming model* where independent samples are streamed from the source of a distribution. The resources of interest are (a) memory used  and (b) number of samples required. This model has gained some interest recently as it captures a realistic situation where the data from a source distribution might be streaming in high velocity and estimations has to be done with limited memory without storing all the data. From a model point-of-view, the task is close to designing streaming algorithms over randomized streams (as oppose to worst-case streams). \n\nThe paper that precedes, and most relevant to, the current work is the one due to Acharya, Bhadane, Indyk, and Sun (appeared in NeurIPS 2019) where they first consider entropy estimation problem in the sample streaming model.  They designed a O(1) word algorithm with sample complexity $O({k\\over \\varepsilon^3}\\cdot {\\rm polylog}(1/\\varepsilon))$ that estimates the entropy of an unknown distribution over an alphabet of size $k$ within an additive error $\\varepsilon$.  Here a word of memory is $O(\\log k + \\log {1\\over \\varepsilon})$ bits of memory. \n\nThe main contribution of the present paper is a new algorithm for the entropy estimation problem in the sample streaming model with $O(1)$ word memory and $O({k\\over \\varepsilon^2}\\cdot {\\rm polylog}(1/\\varepsilon))$ samples. Thus the sample complexity is improved by ${1\\over \\varepsilon}$ factor while the memory remains $O(1)$. The proof follows the structure of ABIS19 paper. But there are some crucial differences including that their basic estimator is different.  The paper conjectures that this bound is optimal up to ${\\rm polylog}({1\\over \\varepsilon})$ factors if the memory needs to be constant. ", "questions": " Without a lower bound result, the feel of the paper is incremental.  Is any lower bound better than the one for the unlimited memory model ($\\Omega({k\\over \\varepsilon \\log k} + {\\log^2 k \\over \\varepsilon^2})$) known? I cannot gauge the difficulty of this problem: but any concrete step towards a better lower bound on sample complexity for entropy estimation while maintaining $O(1)$ memory will make the paper substantially stronger. ", "limitations": "I do not see a discussion of the limitations and potential negative societal impact of the work in the paper. However, this may not be relevant for this paper which is theoretical in nature. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:* The model and the problem considered are significant. The paper makes a concrete contribution by improving the sample complexity from prior paper which appeared in NeurIPS. The techniques seem to be  fairly deep and cleaver.  \n\n*Weaknesses:* The paper seems incremental. There is just one result. While it is clean, the contribution may not be of  interest to a wider NeurIPS audience as it is mainly technical. The conceptual contribution is weak. The conjecture is very nice. The authors provide some discussion of how to prove a lower bound in the appendix, but there is no formal lower bound proof  given for substantiating the conjecture other than the upper bound. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9RS8yzL5ynJ", "reviewer": "Reviewer_kziV", "summary": "This paper considers the problem of estimating the entropy of a distribution D over a finite set [k], given access to a stream of i.i.d. samples from D. It is shown that k/eps^2*polylog(1/\\eps) samples suffice for an algorithm with constant words of memory to estimate the entropy within an eps additive error. This improves the previous best sample complexity by a factor of 1/eps. The authors also conjectured that the bound is optimal for constant space algorithms, up to polylog(1/\\eps) factors.\n\nThe main idea of the paper is to write H(D)=E[log(1/p_i)] where i is drawn from D, and to estimate log(1/p_i) for each i. The estimator used in this paper works by empirically estimating a negative binomial random variable X with mean t/p_i, which is the number of samples before seeing exactly t copies of i, and using log(X/t) as a reasonable estimate. The authors further observed that this estimator is biased (i.e., E[log(X/t)] is not equal to log(1/p_i)), and due to Taylor expansion the bias can be written as a polynomial in p_i plus a small remainder. Since the power p_i^r is equal to the probability that first r samples are all copies of i, the bias can thus be estimated to a high precision in constant space. To get rid of the polylog(k) factors, the authors further employed a bucketing technique, which comes down to estimating conditional expectations of log(X/t) given X belongs to some interval I, and the probabilities that X belongs to I.\n\n", "questions": "1. Expression (1) at the bottom of page 5 needs more explanation. The first inequality is non-trivial since there are negative terms in the summation. The last inequality, which I believe should be true, can fit in some extra steps of calculation. In fact, I think Taylor series with remainders can probably simplify the proof here (although I didn't check).\n2. The discussion about space complexity before Lemma 3.3 does not make sense until the parameters (b_l, r_l, etc.) are defined.\n3. What is an intuitive explanation of why the bucketing technique can remove polylog(k) factors?\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The main improving idea is simple yet novel and non-trivial. The previous best bound is achieved by estimating p_i in a straightforward way and arguing that the bias E[log(1/^p_i)]-E[log(1/p_i)] is small. This paper takes a different approach by identifying a relevant negative binomial random variable from the sample stream. Interestingly, the bias of this new estimator is a polynomial in p_i, which is easily approximated. The overall flow of the paper is smooth.\n\nWeaknesses: It would be nice if the paper provides some applications of entropy estimation, especially in the context of streaming with constant memory constraint. Some places require more explanations. See below for specific questions.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept