Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies distributed mean estimation in the $d$-dimensional space where each client can use only $d(1+o(1))$ bits for communication. A crucial assumption is that the server and the $n$ clients can have shared randomness while each client can independently communicate with the server. Under such an assumption, the authors proposed two schemes and demonstrated the efficiency of their new approaches. 
main_review: Several comments are in order.


1) Most parts of the paper read well with concise notations. In particular, I like the way of illustration that always starts with the Alice-Bob example. The proposed algorithms are also conceptually simple and easy to understand. 


2) The authors propose two schemes: One utilizing uniformly random rotation matrices, and the other uses Hadamard transforms. The first scheme (DRIVE) seems computationally inefficient but works for all cases, and the second (DRIVE$^+$) is more efficient and works for scenarios with structural assumptions. 


3) I wonder if the assumption of shared randomness is typical in the literature and practice (e.g., in Federated learning applications). In particular, the server needs to know the randomness of $\textbf{all}$ clients, and uniformly generating rotation matrices seems to require lots of random bits. It will be great if the authors can clarify this point with quantitative statements such as how many random bits are sufficient. 


4) The $\textbf{only}$ approach with a satisfactory theoretical guarantee is DRIVE accompanied by uniformly random rotation matrices (Theorem 5). Here, I do have concerns about the efficiency of the algorithm. 

     - On page 1, the authors mention that approaches via variable-length encoding have high computational costs. I thought that this hinted that the proposed schemes should be much more efficient. 

     However, as Table 1 demonstrates, DRIVE with a uniformly drawn rotation matrix is $1{,}000$ times slower than some existing approaches. 


5) I like the experimental results as they demonstrate that the proposed schemes lead to concrete improvements on standard test datasets. But I felt slightly overwhelmed by the list of highly compressed experiment descriptions, especially given that most relevant details appear in the supplementary. I suggest the authors pick a few experiments to include in the main paper with more information. This change should probably enhance the readability of the submission. 


6) Another comment is about the competing algorithms. It seems that Hadamard + 1-bit SQ and Kashin + 1bit SQ are not designed for the $d(1+o(1))$ setting. I am slightly concerned about the fairness of comparison (e.g., lines 321-322). I wonder if the authors can add comparisons with Hadamard/Kashin + $c$-bit SQ for some $c>1$ as a relaxation since achieving $d(1+o(1))$ may not be crucial in many applications. 


7) I appreciate the authors for being honest and providing a list of limitations of their work at the end of the submission. This part does not seem to mention the computational aspects of the algorithms. I think it might be good to state the time complexities of the proposed algorithms and some existing ones clearly at someplace. 


8) Minor comments: 
    - Is there a reason for normalizing the MSE of mean estimation by the sum of squared norms of the individual vectors (e.g., line 51)? I think it might be natural and more consistent if the normalizing factor is the squared norm of the mean. 
   - Should one increase the spacing between lines 59 and 60?
   - Line 73: Is the word "it" referring to Alice?
   - Page 3: Should Algorithm 1 have a caption? 
   - Line 227: Is there an actual application where 1.17 bits per coordinate is much worse than 1+o(1) bits?
limitations_and_societal_impact: The authors clearly stated the limitations of their work in the second paragraph of the Conclusion section. I do have some additional suggestions about the computational efficiency aspect. In Checklist, the authors indicated that "we do not believe there is an inherit (inherent?) negative societal impact in this work."
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the distributed mean estimation. In this problem, there are n clients,  each of which has a d-dimensional real-valued; the goal is to estimate their mean on the sever side using minimum communication cost. The paper focuses on 1-bit quantization methods, i.e., each client sends one bit per coordinate and d(1+o(1)) bits in total. The algorithms are standard (including the Hadamard transformation based method); the main difference is new scaling factors S. Theoretical analysis on the expectation and variance are provided. Empirical results also show some advantages of the new estimate. 
main_review: Strength:
1. The problem studied is fundamental and well-motivated.
2. Theoretical guarantees are proved.
3. Empirical results show that the new estimate achieve improved MSE among 1-bit quantization methods.

Weakness:
1. All algorithms mostly use existing techniques. The 
2. The analyses are not too difficult.
3. My main concern is that the paper only focus on 1-bit quantization, which I think is somewhat restricted. 1-bit quantization is often suboptimal; multi-level quantization could be much better, see e.g., qsgd [1]. In particular, when the vectors are sparse or skew, the budget for different  coordinates should be different. In particular [2] shows that the total communication cost can be sublinear in d for skew vectors. Moreover, the random rotation operation applied on the original vectors destroys such sparsity/skewness. Such skewness is bad for 1-bit quantization, which is why random rotation is applied to make the vector “flat”. But skewness can actually save communication provably, if multi-level quantization is used. 
4. In the experiments, multi-level quantization QSGD, variable-length coding methods [3], etc. should also be compared. 




[1] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. Qsgd: Communication-efficient sgd via gradient quantization and encoding.\
[2] Z. Huang, Y. WANG, K. Yi, et al. Optimal sparsity-sensitive bounds for distributed mean estimation.\
[3] A. T. Suresh, X. Y. Felix, S. Kumar, and H. B. McMahan. Distributed mean estimation with limited communication.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the problem of communication-efficient distributed mean estimation. This paper proposes a novel algorithm DRIVE which uses as little as almost 1 bit for each coordinate of the vector and estimate the distributed mean with bounded error. The idea is to use a uniform random rotation to minimize the vNMSE. Besides, DRIVE can use structured random rotation to accelerate the compression for high dimensional vectors. The empirical evaluation of DRIVE shows that federated learning with gradients compressed by DRIVE can achieve faster convergence than other compression schemes.
main_review: Overall, the writing of the paper is clean and easy to understand. As a majority of the evaluation is done for federated learning task, it would be better to provide a convergence result for DRIVE+SGD to show the impact of error of distributed mean estimation on the rates. Besides, there is a recent work (Davies et al., 2020) could be an interesting reference.

Davies P, Gurunathan V, Moshrefi N, et al. New Bounds For Distributed Mean Estimation and Variance Reduction[J]. arXiv preprint arXiv:2002.09268, 2020.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of distributed mean estimation under a single bit (per coordinate) communication constraint. It proposes a novel compression scheme based on random rotation and sign quantization. The suggested method is applied to distributed and federated machine learning problems and shows improved results over previously studied quantization methods.
main_review: This work proposes and analyzes a compression method that is based on multiplication by rotation matrix followed by deterministic sign quantization and scaling. To make it scalable and computationally efficient for large dimensions, the authors suggest using structured randomized Hadamard transform, which is not a novel thing on its own. 
The paper is clearly written, but it can benefit from adding a table with a summary of the obtained theoretical results and comparison to previous approaches.

Theorem 5 is a simple consequence of the known fact
$$
\mathrm{E} \left\Vert \frac{1}{n} \sum_{i=1}^n \left(X_i - \mathrm{E}\left[X_i\right]\right) \right\Vert_2^2 = \frac{1}{n^2} \sum_1^n \mathrm{E} \lVert X_i - \mathrm{E}\left[X_i\right] \rVert_2^2,
$$
for any independent random variables $X_i$. This was previously used in many analyzes of distributed optimization methods with compressed (gradient) updates.

 As soon as DRIVE with a structured random rotation cannot be made unbiased, I would like to point out the authors to the fact that distributed/federated optimization methods with biased compressors are not guaranteed to converge in the general case of convex functions and may even diverge exponentially [1]. That is why the Error-Feedback mechanism [2, 3] is required to guarantee the theoretical foundation of the proposed method in the optimization setting. In my opinion, this is the main weak theoretical point of the paper, but it can be fixed without a great effort with additional experiments.

Regarding the experiments. Could you please comment why your experimental results contradict with findings of Caldas et al., which showed a better performance of Kashin representation in comparison to Hadamard transform? I think that more discussion regarding this would be helpful and insightful.
 

**Minor issues/comments:**

I would like to ask the authors to define (in the paper) the term PRNG, which was used on pages 2, 4 in the context of shared randomness.

It seems to me that the paper can benefit from moving some (technical) proofs into Appendix. For instance, the proofs of Theorem 1 and Lemma 1 are pretty simple, and their idea can be expressed in one sentence. This can free the space for a more detailed description of DRIVE$^+$.


[1] Beznosikov A., et al. “On biased compression for distributed learning”. arXiv preprint arXiv:2002.12410, 2020.

[2] Sebastian U. Stich, et al. “Sparsified SGD with memory”. In Advances in Neural Information Processing Systems (NeurIPS), 2018. 

[3] Richtárik P., et al. “EF21: A New, Simpler, Theoretically Better, and Practically Faster Error 
Feedback”. arXiv preprint arXiv:2106.05203, 2021.

[4] Caldas S., et al. “Expanding the Reach of Federated Learning by Reducing Client Resource Requirements”. arXiv preprint arXiv:1812.07210, 2018.
limitations_and_societal_impact: Limitations of the work were mostly addressed. Negative societal impact concerns are not applicable due to the theoretical nature of the paper.
review_title: null

Meta-review: The paper proposes a new 1-bit mean estimation algorithm. While the idea of using random rotation matrices have been explored in this problem, the paper proposes a new elegant algorithm that has better performance both in theory and experiments. The paper is well written and I recommend acceptance.

I am curious to see how this method compares empirically to the variable length encoding presented in Distributed mean estimation with limited communication paper. I encourage authors to add this comparison and incorporate other reviewer comments in the final version.
Decision: Accept (Poster)