Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes two new sparsification methods for the distributed mean estimation problem. One of the proposed strategies, Rand-k-Spatial, uses the spatial correlation of different nodes to have an unbiased estimator. The other strategy, Rand-k-Temporal, uses the temporal correlation of local vectors at consecutive iterations to fill the sparsified elements without an extra computation or storage cost at the resource-constrained nodes. The authors show that both methods outperform Random-k and Top-k sparsification methods empirically.
main_review: Overall, I liked the methodology and enjoyed reading the paper. Although the proposed methods might seem incremental upon Random-k, the way authors get use of temporal and spatial correlations to improve Random-k is neat and theoretically sound. I also agree with the authors that the approach is applicable to other sparsification methods as well. Here, I list some more specific comments and questions:

- The paper refers to top-k and random-k frequently and compares the methods' strengths and weaknesses. However, I think they miss a strategy, rTop-k [1], that combines these two methods and enjoys both top-k's and random-k's benefits. 

- Although the concept of spatial correlations is not new, temporal correlations have recently started getting attraction. And I like the way how authors benefit from temporal correlations. 

- It is interesting that the authors were able to outperform top-k with the modified version of random-k. The discussion on rand-k-temporal and error feedback seems important to me given that many sparsification methods do not perform well without error feedback, hence they suffer from high storage costs at the nodes.

- Do the authors have an explanation as to why rand-k-spatial does not perform well in logistic regression experiments in Figures 5(c,f)? Is this because the data is non-IID for that experiment? Then, does that mean that rand-k-spatial does not work well with non-IID data? If so, then the proposed method is not very useful for practical federated learning settings. Can the authors clarify if I am missing something here?

[1] Barnes, Leighton Pate, et al. "rTop-k: A statistical estimation approach to distributed SGD." IEEE Journal on Selected Areas in Information Theory 1.3 (2020): 897-907.
limitations_and_societal_impact: The authors do not mention limitations or the potential negative societal impact of their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the problem of distributed "Mean Estimation". Authors provide new insight for the sparsified approach and propose a new method that exploits the data correlation. They show that theoretically, their proposed approach for the special cases of random K outperforms the available technique. Finally, theoretical findings are supported by experiments.
main_review: Positive aspects: 

- I think the paper is well-written and it is easy to follow.
- There is some novelty in the way authors try to use the correlation in the data to increase the sparsity of transmitted vectors.
- Experiments look reasonable. 

Downsides:

- While Theorem 2 provides some theoretical insight regarding the connection between data correlation and optimal sparsification scheme, I think the result in the distributed setting is not useful as it depends on the cross product of the date which is not available at the server. So, It is difficult to consider this result as remarkable.

- My major concern about this paper is the additional storage cost required at the server. In essence, the server is iteratively is trying to reconstruct the data at the devices, which has three major issues when it comes to applications such as Federated Learning as pointed out by authors. First, in FL setting there could be a huge number of devices, therefore storing a vector associated with each device could be impractical and also this brings us to the second point that if the server can store as many as vectors why do we need to do this process distributedly. In other words, given this extra storage at the server, devices can send their data and the server can easily take the average. Third (and least importantly), roughly speaking as vectors $b_i$ represents the data point at the server, this could be considered as the violation of data privacy by the server, especially in Federated Learning.  
limitations_and_societal_impact: See above comments!
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the distributed mean estimation problem. In this problem, each node holds a d-dimensional vector and the goal is to compute the mean of all vectors.
The communication cost is the resource to be optimized. The authors propose to exploit spatial and temporal correlations in real world data sets to improve the MSE.
To do so, a new estimate is proposed and analyzed.
main_review: 
Weakness:
1. My main concern is about the estimate (4). The authors claim without proof that it is unbiased. However, it seems that the authors implicitly assume that $M_j$
is independent of $h_{ij}$. But $M_j$ has non-trivial correlation with $h_{ij}$'s. The same problem happens in the proof of Theorem 1. In the proof, the authors use the law of
total expectation, but for different values of $M_j$, the conditional expectation of $h_{ij}$ are all claimed to be the same, which seems incorrect to me. So the authors should provide
an explanation on this issue in the rebuttal.

2. The second concern is that the estimate (4) is only for the case when all coordinates are sampled with the same probability. However, the uniform sampling scheme often has much worse MSE than schemes using sampling probabilities that depend on the value of each coordinate, e.g., [1].

3. The motivation to utilize spatial and temporal correlations is valid, however the solution proposed is quite simple (if not straightforward). 
So I think the technical depth of the paper is below the bar of NeurIPS.

References
[1] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. Qsgd: Communication-efficient sgd via gradient quantization and encoding
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposed new estimator that leverages spatial and temporal correlations between vectors in randomized k-sparsified mean estimation procedures. 
main_review: This paper proposed new estimator that leverages spatial and temporal correlations between vectors in randomized k-sparsified mean estimation procedures. The presentation is easy to follow, and the ideas are clearly described. The intuition behind the new estimator that utilizes the spatial and temporal correlations is sound under the distriubted learning senario, and the proposed estimator is very simple to understand and implement. Theoretical analysis are presented which clearly show under the strong spatial and temporal correlation cases, the new estimator significantly improves the standard randomized k-sparsified estimator.  Empiricla studies on various datasets and models demonstrated that the proposed technique is a simple and effective way to improve the communication efficiency in distributed learning.
limitations_and_societal_impact: N.A.
review_title: null

Meta-review: This paper studies communication efficient estimators for the distributed mean estimation problem. The paper presents two methods that exploit either spatial or temporal correlations of the data, with the goal to improve communication efficiency. The MSE of the two estimators is studied analytically, and numerical benchmarks demonstrate that the proposed techniques can improve the communication efficiency in distributed learning.

The reviewers spotted a few inaccuracies in the proofs, but following the author's response they believe that these issues can be addressed in the final version.

On the one hand, the reviewers emphasized the simplicity of the method, but on the other hand, they found the contribution to be 
slightly incremental. At the end, the good experimental results were the deciding factor in the discussion.

The reviewers believe that this work inspire future work (including attempts to address current limitations regarding practicality in distributed settings) and will be of interest to the community.

The authors are strongly encouraged to take the reviewer's feedback into account when preparing the final version, including the already proposed changes, and perhaps also to include a discussion on lower bounds from an information-theoretic perspective (as guides for follow-up work).
Decision: Accept (Poster)