Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors focuses on communication-efficient algorithms for estimating the entropy of a distribution under privacy constraints. They propose private methods for Shannon, Ginni and Collision entropy that are the most widely used entropy types. The proposed algorithms are implemented for both interactive and non-interactive models. They showed that the estimation algorithms for each entropy satisfy local differential privacy and require minimal communication.

strengths_and_weaknesses: Strengths: To the best of my knowledge, the proposed approach is novel and solves an important problem in a distributed data setting.

Weaknesses: In my opinion, the main problem is the lack of motivation. I couldn't get why private entropy estimation is important. It is not easy to follow the paper at times as a non-expert in the field. Minor issue: why don't you refer to the previously best-known algorithm in line 14?  That could help to people to engage who are working on similar problems and knows the literature well. 
questions: It might be useful to provide some background why Ω(d^2) pair observations to achieve O(d) error is good. Similarly, Ω(d/ε) pair observations are necessary to achieve O(εd) error is an improvement and other similar bounds? Maybe it is clear for people who are working in this field but that makes reading the paper more difficult. 
limitations: Authors mentions in Checklist that there is a gap between upper and lower bounds. First of all I couldn't find the discussion in the main part of the paper and it is not discussed how the gap between the upper and lower bound can be reduced (if possible).
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors study the problem of estimating the entropy of a distribution in a distributed setting. Specifically, samples from a distribution are distributed across machines. The goal is for a central entity to estimate the entropy of the distribution. They consider a number of different communication models - (a) non-interactive model, in which all users simultaneously exchange information with the server during a single round of communication (b) sequentially interactive model, in which the server queries users one at a time, possibly in an adaptive manner. They use the blackboard model of communication where the information sent from a machine to the server is broadcast to all machines for free, i.e. the information is written on a metaphorical blackboard and all machines get to view the blackboard for free. 

Note that entropy estimation can be very trivially accomplished by estimating the distribution itself, but here they ensure that their algorithms are "private" where privacy is defined according to the notion of "local differential privacy".

Their main contributions are: (1) An interactive and private algorithm for estimating the Shannon entropy (2) non-interactive algorithms for estimating the Gini and collision entropy.

My reviewing capacity: I have some previous experience in doing research in distributed statistical estimation. I am comfortable with basic information theory, randomized algorithms, concentration inequalities, basic analysis. I have taken a look at the proofs in moderate detail.


strengths_and_weaknesses: The problem of estimating entropy has been well studied, and this has been studied in distributed settings as well. The paper provides improved algorithms in the settings considered. Other than for Shannon entropy, the authors provide non-interactive algorithms. Obviously it is "better" to provide strong non-interactive algorithms because non-interactive algorithms are trivially interactive with just zero interaction. While related work is well cited, more discussion about the importance of the problem is required. The algorithmic techniques are non-obvious. The analysis uses quite basic information theory and concentration inequalities.
As I said, I haven't perused the proofs in complete details, but the paper seems sound technically. The analysis is rigorously done. Also, the paper is very clearly written.

I am not very convinced about the strength and importance of the results. For example, with Shannon entropy, which really is the most commonly used form of entropy, they assume that the support size of the distribution is constant. If support size is constant, then distribution estimation can be done with O_eps,delta(1) amount of communication, and in turn entropy estimation can be done trivially. While I don't have context of the relevant work, the authors must clearly describe why they can't use techniques for distributed distribution estimation and why new techniques are required. Another issue is the structure assumed in the distribution. There is no motivation provided about why the distributional structure would be something of interest.
Also, I feel that the authors have provided very little motivation about why these problems are important. This is especially important with Gini and collision entropy.

questions: See suggestions for improvement above.
limitations: See comments above.
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 provides a method for computing the Shannon, Gini, and collision
entropy of a distribution in the sequentially-interactive differential 
privacy models.

For Shannon entropy, they approximate the weight of the Chow-Liu tree 
using private l_1 estimation between pairs of variables, combined with the fact
that the l_1 estimation of a distribution can approximate entropy when the 
domain is not too large. Under sequential interaction, they show that a
near-linear number of samples can be taken by estimating the weight of  
a maximum spanning tree. This improves over the work of Chow and Liu.
They also show that their algorithm has optimal dimensionality dependence with a 
lower bound.

They specialize these results to when the dependency graph of the distribution 
is a chain or a star.

Finally, they show how to use hash collisions to estimate Gini and collision
entropy in the non-interactive local DP setting.

strengths_and_weaknesses: + The paper achieves subquadratic sample complexity for the problem of Entropy
  estimation, improving over the Chow-Liu algorithm.

+ The communication overhead is a small constant for both algorithms.

- The lower bounds do not depend on $\alpha$, the privacy parameter, thus they
  are definitely loose when \alpha is small.

- There are no experiments to evaluate the approximation quality. (Edit - they've added some which favorably compare their work)

questions: What do the authors expect for the approximation quality of the entropy estimation algorithm given that the algorithm only considers tree-structured distributions?

Can we make any statement about sample complexity when the privacy parameter $\alpha$ is low?
limitations: The Shannon entropy of the best tree-structured distribution 
is returned, this is an approximation of the true Shannon entropy which is the 
assumption of the Chow-Liu tree. 

(Edit: this seems to be a common assumption, so it’s not a severe limitation.)

This limitation could best be overcome with an experiments section---the
algorithms are straightforward to implement, and one could estimate the quality
of the entropy estimation on a real-example.
review_title: null

Meta-review: metareview: This is a solid paper on private and communication-efficient algorithms to estimate entropy in a distributed setting. The paper presents several algorithmic and theoretical results, including showing that the Chow-Liu algorithm performs much worse when only the entropy is needed and not the entire distribution. One main criticism from reviewers was the lack of motivation, which the authors clarified in the rebuttal. The authors should incorporate and highlight these clarified motivations in the paper. A key criticism from the reviewers is absence of experiments. While the authors provide some token experiments in the rebuttal (which they may include in the camera ready version), I think the paper is strong enough to stand on its theoretical footing. All of the reviewers have recommended acceptance, and I agree with this recommendation.
confidence: Certain
Decision: Accept