Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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)$. 
The 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. 
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. 

The 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. 
Typo in line 246 - should be p_i instead of q_i? 
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.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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). 

The 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. 

The 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. 
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.  

*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. 
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

The 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.


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.

Weaknesses: 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.


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).
2. The discussion about space complexity before Lemma 3.3 does not make sense until the parameters (b_l, r_l, etc.) are defined.
3. What is an intuitive explanation of why the bucketing technique can remove polylog(k) factors?

limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.
2. 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.
3. The claims of the paper are all supported by theoretical results, which is comprehensive and convincing.

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.
2. 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.
3. 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?
4. 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).
review_title: null

Meta-review: metareview: This paper improves the state-of-the-art in estimating the entropy of a discrete distribution under memory constraints. The reviewers agreed that the presented result is elegant and non-trivial and that the ideas are described well. There is some concern that the paper is incremental due to the absence of lower bounds, but the algorithmic contribution is strong enough to merit acceptance to NeurIPS.
confidence: Certain
Decision: Accept