Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers "instance-optimality" of discrete distribution estimation under communication constraints for interactive schemes where each client receives a single sample from the distribution p. The focus is on the small alphabet regime (d<<n). Upper bounds for $l_2$ error feature the half norm and for $l_1$ error feature the one-third norm. 
main_review: The paper considers a problem of significant interest. This is the first work to consider instance-optimality in communication constrained settings. The writing is clear for most of the part, except the lower bound. It appears as if the authors copy-pasted parts of the lower bound proof in haste since there are symbols such as $S'_{\theta}(X)$ that have not been defined in the main text and there are references to equation numbers (7) and Lemma E.1 that can be found in the appendix. 
Couple of concerns:
1) In the local refinement round, the knowledge of the groups is available at the server after the localization round. It's then not clear how this is available to clients since the knowledge of $\mathcal{J}_i$ is necessary to send the ranking of the symbol it receives. 

2) Line 263 states that symbols with larger $p_j$ have a larger estimation error. It's not clear why this should be the case when one would expect that a higher probability symbol might be seen often and therefore be estimated more accurately. 

Overall, I would have preferred more discussion about the intuition behind the local refinement scheme (for e.g. some explanation for why it works well). It is also worth pointing out in the related works section that most works that analyze the minimax settings focus on the large alphabet regime. 

Some typos: 
1) Pg 7, line 257, is the union an intersection? 
2) Pg 8, line 263 - comma instead of period

limitations_and_societal_impact: I am satisfied with the limitations that have been addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies estimating an unknown discrete distribution over $d$ symbols from its samples observed under $b$-bit communication constraint. The main result states that for a sufficiently large sample size $n$, the optimal $\ell_2$ error is essentially 
$\Theta \left(
\frac{\lVert p \rVert_{1/2}}{n2^b}
\lor
\frac1n
\right)$.
The paper also obtains an upper bound on the $\ell_1$ learning rate without a matching lower bound. 
The optimal interactive scheme first finds a coarse estimate of the underlying distribution with an existing minimax approach, 
then refines the result using this estimate and an independent sample. 
main_review: Pros:
1. The paper is well-written and provides appropriate examples and plots. 
2. I appreciate the authors' efforts to develop the proposed learning scheme that achieves near-optimal performance for every distribution. The idea is also natural enough to lead to a simple algorithm.
3. The results also imply a logarithmic improvement over an existing scheme on $s$-sparse distributions, though under a different setting. 

Cons:
1. It seems that the results, including Theorems 2.1, 2.2., and 2.4, hold only for large sample sizes $n$, e.g., $n\gtrsim d^3$. I wonder if this is the case for practical applications. As per my understanding, these types of distribution learning applications often involve large alphabets. 
2. The minimax lower bound in Theorem 2.4 considers the supremum over distributions $p'$ satisfying $\lVert p' - p\rVert_\infty \le \sqrt{\frac{\lVert p\rVert_{1/2}}{n d 2^{b}}}$. I wonder if the $\ell_{1/2}$-norm values remain close to that of $p$ or not, which is critical to the merits of the lower bound. 
3. The optimality of the results on the $\ell_1$ norm is unclear. From my perspective, $\ell_1$ distance is probably a better measure for distribution learning as it directly relates to classification errors in hypothesis selection. 
4. In line 191, the paper claims that the scheme is minimax optimal over $\mathcal P_{d, s}$. I can see the upper bound, but not a (nearly matching lower bound for $s$-sparse distributions. Note that the prior work [10] considers the problem under the non-interactive setting, which is more restrictive. 
5. Line 193 states that "since $\beta$ is constant," I wonder why this is the case and note that Corollary 3.2 assumes only $\beta\in(0, 1/3)$. Also, Line 204 claims that the results in [10] do not apply to geometric and Zipf distributions. My thought is that these distributions have small "effective support sizes," learnable with a standard minimax algorithm. 

Additional suggestion:
1. It might be better if the authors can shorten the abstract as it has 20 lines of text.
2. It seems reasonable to consider experiments in more practical settings, such as those mentioned in the Introduction. 

 


limitations_and_societal_impact: The authors discussed the limitations of their work and marked N/A for the potential negative societal impact of their work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies distributed estimation of a discrete, $d$-dimensional law $p$ under communication constraints (wherein each client may only send $b$ bits) in a sequential model (wherein clients are ordered, and are aware of messages sent by earlier clients when preparing their message). 

The authors describe what is essentially a two-stage scheme that first obtains a crude estimate of the law using a minimax scheme. This estimate yields a sense of which elements of the law are large, and subsequent communications are designed that provide more samples for such elements, the precise weighting of which depends on the error metric being controlled. As a result, if the number of clients is large enough ($n \gg d^3\log d$ for squared-$\ell_2$ error), the resulting estimate for the squared-$\ell_2$ criterion has error decaying as $\max( \\| p\\|_{1/2}2^{-b} , 1)/n$. Both stages of the scheme use the grouping idea of Han et al [4].

The above scheme is complemented by a lower bound for the $\ell_2$ criterion, which shows that under the same large $n$ condition, a matching lower bound but with a $(1+\delta)/2$ norm instead of the $1/2$ norm, lending a measure of tightness to the achievability analysis. This is derived via a Fisher information technique due to Barnes et al, and a nice construction of a parametric family of discrete laws in which the lowest $d-h$ masses are fixed. Under some auxiliary conditions, the resulting bound depends linearly on $h^2 p_{(h)},$ where $p_{(h)}$ is the $h$th biggest entry of $p$, and this quantity is characterised in terms of the $1/2$ and $(1+\delta)/2$ norms.

Together, these results almost characterise the bit-rate needed by each client to ensure optimal estimation, specifically the $1/2$-Renyi entropy of $p.$ This immediately leads to improved rates for spase, and for highly skewed laws.

main_review: Post Rebuttal: thanks for the clarifications. I think my view basically remains the same.

----


I think the paper discusses a relevant problem, and the proposed scheme and lower bound are quite elegant. Pointwise results are always particularly interesting, and the bound of this paper are novel, and offer a broad insight into distributed estimation. It's particularly nice that these offer direct improvements for cases such as sparsity.

Perhaps the biggest weakness of the analysis is the large error terms, which require a large number of clients to be effective. Equivalently, the results of the paper do not offer improvements on sample complexity of the tasks for a given bitrate. On the whole this is not a deal breaker - I think there may well be regimes where one does have access to a large number of clients, none of which can communicate much (although whether such a situation would admit the sequential model is a little questionable). I think that the paper should discuss this aspect explicitly [*], and contextualise the analysis by describing application domains where such an assumption is reasonable (and ideally also where it is not). In addition, a discussion of whether the authors believe that these terms are an artifact of the analysis or more fundamental would also be useful to the community. 

[*] while the authors are conscientious about stating the bounds completely and acknowleding the requirements on $n$, I think this is not enough.

---

Clarity: The paper is mostly well written, and the approach is well explained. The related work described is, to my knowledge, adequate, and the results are properly contextualised with respect to these (barring a frank discussion of the size of $n$, as I discussed above). I think the paper can benefit from explaining where the particular form of the $n_j$ comes from. This seems not hard to motivate, at least for the $\ell_2$ squared error - using the explanation on line 267, the net error behaves as $\sum p_j/n_j$, and since no client can account for more than $2^b-1$ symbols, there's a sum constraint on the $n_j$, and minimising under it leads to the choice of $n_j \propto \sqrt{p_j}$.

----

A few minor points that need correction:

- Equation (2) is missing a factor of $2$ somewhere (there are only $n/2$ clients).

- The event $\mathcal{E}$ on 257 should be an intersection of each of the $\sqrt{\hat{p_j}}$ being close, not a union. Similarly for $\mathcal{E}_1$ in the appendix. 

- Equation (6) is not quite right - the Binomial tails flatten at the extremes, due to which if $n' p$ is small, then concentration at $\sqrt{\varepsilon_n p}$ as claimed is not right, and instead we have something like (Bernstein's inequality) $\hat{p} \in p \pm \max(\epsilon_n, \sqrt{\varepsilon_n p})$. The argument can be fixed by separately considering the case $p < \varepsilon_n \implies \hat{p} < 2\varepsilon_n $ which directly gives $|\sqrt{p} - \sqrt{\hat{p}}| \le 3\sqrt{\varepsilon_n}.$ Also, for completeness' sake, the usual statement of Hoeffding's inequality is not sensitive to the variance, and something like Bernstein's or Bennet's is needed.

- The proof for $C_\delta = \delta^{2/(1+\delta)} $ in Lemma 6.2 does not quite follow (in fact $\sum_{h \in \mathbb{N}} 1/h^{1 + \delta} > 1/\delta  $). This is not a big deal, since the bound $\sum_{h \in \mathbb{N}} 1/h^{1 + \delta} \le 1 + 1/\delta  $ is true, and this in turn gives $C_\delta = (\delta/(1+\delta) )^{2 / (1 + \delta)},$ which has the same qualitative behaviour for the relevant small $\delta$.


limitations_and_societal_impact: The limitations with respect to $n$ should be discussed more deeply, as described above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the estimation of a discrete distribution P on an alphabet of size d under communication constraints. Each local client holds a single observation from P and transmits no more than b bits to the central server. A two-round interactive scheme is proposed and achieves nearly optimal estimation error. The estimation error depends on the Rényi entropy of P instead of the global parameter d. The minimax lower bound is also derived in this paper. 
main_review: Overall the problem considered is of broad interest and the results in this paper are solid. The fundamental limit on the communication resources in terms of the Rényi entropy is one significant contribution of the current paper. The main concern is on the additional terms of Theorems 2.1 and 2.2 (hidden from the abstract when n is sufficiently large). The quantitative implication is n=poly(d), which appears unrealistic and should be properly justified. With so many clients, the total communication costs are still high. This issue also concerns Theorem 2.4 where the local region scales with n. More issues in Theorem 2.4: the set $\mathcal{P}_d'$ is introduced without context; the term $\delta>0$ is not really arbitrary as $c_\delta$ vanishes with $\delta$, so it should be optimized if possible. 
limitations_and_societal_impact: The limitations are discussed in the paper. The potential negative societal impacts are not available as the paper is mostly on the theoretical aspects.
review_title: null

Meta-review: Based on the reviews and discussion, I am inclined to recommend the acceptance of this paper.  The reviewers generally appreciate the importance of the problem, and the contributions made, particularly studying instance-optimality in a communication-constrained setting.  However, the reviewers do maintain some concerns, some of which are quoted as follows:
- "I still think $n\ge d^3$ is restrictive (also much worse than $d^2$ you mentioned). Even in applications where the number of samples is larger than the domain size, $d^3$ easily blows up. As other quantitative results are available, it is important to include proper discussions such as why you believe the transition happens at $d^3$."
- "I don't agree with "the scaling of our lower can be made arbitrarly close to the upper bound" due to the extra vanishing $c_\delta$. I do appreciate the lower bound $\Vert p\Vert_{1/2} /\log d $ though."
- "Perhaps the biggest weakness of the analysis is the large error terms, which require a large number of clients to be effective. Equivalently, the results of the paper do not offer improvements on sample complexity of the tasks for a given bitrate."
- "the authors claimed that their min-max Lower Bound is stronger because they maximize over a larger domain, not making intuitive sense. For another example, the authors commented that the $\ell_2$ error is equally important as the $\ell_1$ error for assessing discrete distribution learners. I don't think this is the case in the literature, and the $\ell_2$-type results are often much easier to derive. In particular, the authors also admitted that the $\ell_1$ problem remains "open." "

I believe that these are valid concerns, but at the same time, none of them were viewed as strong reasons for rejection, and one reviewer was willing to champion the paper more strongly, hence my recommendation.

In the final version of the paper, I ask that the authors carefully take the above comments *and* all of the reviews into careful consideration.
Decision: Accept (Poster)