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: The paper considers the estimation of d-dimensional distributions in a decentralized setting. Agents collaborate by sending messages to a central server, but their messages are limited to k bits and $2^k << d$. This setting was already studied by several authors, but the originality here is to allow sparse heterogeneity among agents.

The assumption is that there are $T$ distinct  but unknown d-dimensional distributions, and each agent is associated with one of the $T$ distributions. The set of agents is therefore partitioned into $T$ classes and, as far as I understand, the classes are known to the central server. Each class is characterized by a (small) set of components that have a distribution specific to it. All agents have exactly n samples drawn from their distribution. They send n messages. The ith message is a binary hash of the ith sample of length $k$.

The approach is the following. After receiving all messages, the server first performs a robust estimation of each component of the distributions, considering all the messages sent by all agents. Then it estimates for each cluster the components that are specific to a cluster and replace the global estimate by an estimate computed with the messages received by all agents in the same cluster.

The main results state that this 2 steps procedure is an upper and a lower bound on the estimation error (the l2 norm of the difference of the estimation and the true distribution) for each class. The upper bound contains a term that can be $T$ times smaller because of the collaboration across classes (possible for the estimation of the non-specific components). Another term depends on the sparsity value s rather than the dimension d for the specific components.

While the proof can be a bit technical, the result is not surprising. The proof has essentially to control the weight of the errors due to the decoding of the hash functions in the restricted communication setting.


strengths_and_weaknesses: 
# Strengths
- The setting is interesting and extends known results
- There are original contributions in the proof
- some experiments give an empirical evaluation of the proposed algorithm

# Weaknesses
1. The statement of the main theorems are not clear enough in the main text
2. I also recommend clarifications in the exposition of the setting
3. I have not understood the approach used in the lower bound



questions: 1. In the main text the authors use the notation $n = \Omega(2^b ln(n))$ which is clearly false (in the common acceptation of this asymptotic notation $\Omega$, the Landau notation). In the appendix, it is written that $n$ should be larger than $2^{b+6} ln(n)$. It should be written like that in the main text.

   But more importantly, the proof itself in appendix C1 starts considering  two cases that also misuse the Landau notation (Using $O$ and $\Omega$).

2. The setting should be more precise about the central server's knowledge of the problem and the agents. In particular, is the central server able to identify the cluster membership of the clients, the value of $T$, of $s$,...?

3. In the lower bound part, two extreme cases are considered (homogeneous and s/2-sparse) and I don't understand why the lower bound can be expressed as the sum of these two cases (and not for instance the max of the two...)  

limitations: As explained above, the setting should be more precise about the central server's knowledge because it induces some limitations.
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: The paper proposes a federated algorithm for efficiently estimating local data distributions with hashed messages to reduce communication costs, provided that there exists a central/global distribution such that the local ones differ from the global one in a number of bins/entries much smaller than the support size. The approach relies on a robust estimate of the global mass of an entry and it is shown to be minimax optimal wrt the estimation error of the local distributions when using the median estimator. The key intuition behind the approach is that the entries that vary the less between users are probably those that are homogeneous.
An empirical analysis both on synthetic and real datasets illustrate in which settings the method improves on global and local baselines, in particular when the communication budget b is sufficiently large. 
strengths_and_weaknesses: The paper is well written. I cannot judge the novelty of the results as I am not familiar with the literature on distributed learning of discrete distributions.

I have a few minor comments on the presentation:
1. In the introduction, a good motivation is given for federated learning but not for learning data distributions in this context. It would be interesting to report some practical examples where it is more useful to estimate the local data distributions instead of local predictors, as the former has probably a higher privacy cost than the latter. Providing a stronger motivation would allow to better asses the impact of the contributions.
2. It should be made clear from the beginning that only the problem of learning discrete distributions is tackled in the current work.
3. When citing the works on federated multi-task learning, the following seminal work should be cited as well:
- Smith, Virginia, et al. "Federated multi-task learning." Advances in neural information processing systems 30 (2017).

Specific remarks and typos:
1. line 28: Is performance drop observed in terms of time convergence or accuracy?
2. line 79: What is it meant by shared randomness here?
3. line 189: $n = \Omega()$ -> $\alpha = \Omega()$?
4. line 243: rest -> remaining
5. line 269: What is it meant as prior in this context?
6. line 304: sparsity -> sparse heterogeneity
7. Figure 2: Why does the error of the proposed approach with the median estimator improve between s = 200 and s = 300?
questions: 1. Why does the encoding function $W^{t, j}$ depend also on the data point? In which cases is this function not given per user?
2. How difficult would it be to extend the current results to continuous distributions?
limitations: The principal limitation of the work is in not considering privacy of the studied system. Even if it is out of the scope of the paper, it would be helpful to mention possible tools when working with sensitive data.
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 proposed a new method for collaborative learning of categorical distribution when the data between users are heterogenous but only sparsely different in a few entries. The methods are composed of two steps: 1. collaborative learning of centralized hashed distribution by robust estimation over multiple agents; 2. fine tuning for each user, which is executed through threshold plus projection. The theoretical part of the paper shows the methods work well when there are lots of users and the difference are sparse. Futher, it states the median-based method is minimax optimal
strengths_and_weaknesses: Originality: The idea of the methods and the problem setting don't sound very novel to me. But the proof and theoretical part look 

Quality: The proof is mainly built upon the classical statistical framework, which looks solid to me.

Clarity:  From motivation to setup, from algorithm description to theoretical analysis, from notation to experiment setting, the paper is written in a good shape so that I think the readers can quickly grasp the core idea and technique.

Significance: I felt the scope of usage and problem setting are more or less limited. But I am conservative on this opinion since I may miss some important applications in practice.
questions: 1. In theorem 1, how to interpret the notation $n=\Omega(2^b \ln(n))$ that has variable $n$ at both sides? $\tilde{O}(\cdot)$ there hide logarithmic factors with respect to which variables (should be datapoints $n$)? how to choose $\alpha$ in practice?

2. The proposed algorithm seems to be one-shot, i.e. processing all data at once. While in the reviewer's experience, the learning scenario is more common to be iterative or online style. That is the users or agents may continuously send one or multiple data to the central server. Is it worth to modify the algorithm to be caple of accepting the stream data or just iteratively updating the style? Or can authors provide more application cases when this batch-style processing is preferred?

3. In the proof of proposition 2, it states that ".., it holds for $q=1, 2, \mathbb{E}\\|x-x^\star\\|^q_q$ = ...". The first line of proof wrote 
"$\mathbb{E}\\|x-x^\star\\|^q_q = \sum_{k\in[d]} \mathbb{E} [|{\rm Proj}(...) - {\rm Proj}(...)|^q]$", i.e., expanding to each entry. Why does it hold for $q=2$ case?

limitations: N/A
review_title: null

Meta-review: metareview: With 4, 7, and 7, the paper got a wide range of scores. The reviewer who assigned score 4 did not identify any clear flaws in the paper, and did not engage with the authors or other reviewers. Hence I put less weight on the lower review and recommend accepting the paper.
confidence: Certain
Decision: Accept