Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Contribution:
1. The paper proposed a new unbiased vector quantizer constructed from Voronoi quantization (which quantized a vector to its nearest neighbor in the codebook) and random codebook generation. 
2. Theoretical properties of the quantization scheme are studied, including relative variance and asymptotic growth of relative variance w.r.t dimension and size of codebook.
3. The proposed quantization achieved superior performance compared with a few baseline methods on training neural nets.

main_review: Overall I think the paper is well-written and has a solid discussion on the theoretical properties of the proposed quantization scheme. But the experiments section can be improved.
Advantages:

1. Thorough analysis is given to relative variance and the asymptotic growth rate of it with the increase of dimension/size of codebook. 
2. The proposed quantization is unbiased and has a lower error compared with HSQ methods (the main basline quantizers) both in theory and in experiments.

Disadvantages:

1.The comparison of different quantizers is only done well on training VGG on CIFAR-10. Similar comparison should be done on more dataset and/or network architectures. 
2. For the ResNet on Imagenet experiment, only the performance of the proposed quantization method is reported and the accuracy is below 70%, though with a higher compression rate than QSGD, the accuracy lower than that of QSGD (which is around 75% in the original paper).

-----------------------------------------after rebuttal--------------------------------

Thanks for the detailed feedback and the new experiments. I encourage the authors to strengthen the experiments on imagenet but the current version looks good to me. I will keep my score.
  

 
limitations_and_societal_impact: I missed the discussions on the limitations of the work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a new unbiased gradient (vector) quantization method for communication efficient distributed optimization. 
The authors establish bounds on expected quantization error and give convergence guarantees in convex optimization settings.
main_review: There has been considerable interest in techniques for communication compression in distributed optimization. This is motivated by increase in size of datasets and models as well as new paradigms like Federated learning. Thus, the topic that the paper considers is important and of wide interest.

The paper proposes a new vector quantization method which is as follows: the method first samples a random codebook from some appropriate probability distribution. Then a vector is mapped to its nearest point in the codebook (hence the term voronoi quantization). 
The paper deals with design of unbiased methods, however the aforementioned point has a directional bias. Therefore, finally, an appropriate scaling is done for debiasing. Hence, what is communicated is the index of the point in the codebook as well as the scaling factor.
The paper is mostly well-written. The authors present a thorough theoretical and empirical analysis. 

**Biased vs unbiased:**: The authors motivate the design of unbiased methods by the fact that with unbiased compression, there is a benefit from averaging due to variance reduction. 
There is a typo in the equation after line 96: the second term should be $K^{-1}E\Vert \text{Comp}_1(x) - E[\text{Comp}_1(x)]\Vert^2$.
The authors say that to correct the directional bias, theyneed to compute the quantity $r_M^p$, which is intractable, but can be approximated by Monte-carlo methods. This approximation error therefore contributes to a (small?) bias in the gradient estimation, hence the method is not *fully* unbiased.

**Empirical comparison with biased compression methods**:
The empirical results support the proposed method over other unbiased methods. However, I wonder how does it perform compared to biased compression methods, like top $k$?


**Improvement over scalar quantization?** The authors prove upper bounds on expected quantization error (Theorem 2). However, it seems to me that in order to get constant error, we need to set $M$ such such $\log M \approx d\log{d}$. Hence the communication size is $O(d\log d)$. Scalar quantization methods instead, for constant accuracy communicate $O(d)$ bits. Am I misunderstanding something here?

**DoStoVoQ: Impact of parameter $L$**: The only change in the second algorithm ``DoStoVoQ" is that it partitions the gradient vector into $L$ buckets and vector quantizes each. However, in the quantization error guarantee, there is no dependence on $L$? Why is it so? If there is indeed no dependence, why do we care about this algorithm at all?

**What if we repeat codebooks?** 
In the method presented, a new codebook is sampled i.i.d. everytime a new vector is compressed. What is the issue if we repeat the same codebook, say among all workers, in an iteration? 

**Convergence guarantee**: In line 316, the authors mention the convergence rate of DoStoVoQ-VR-DIANA (a variant in the appendix), however there is no mention of the the convergence rate of DoSToVoQ, the method in the main paper.

**Return communication compression?**:
In the algorithm, only the communication from workers to master is compressed. There is no mention of communication of updated model back to the workers. 
Do the authors propose to compress the return communication too, or not? If yes, do the convergence guarantee still apply?
limitations_and_societal_impact: No direct societal impact
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new unbiased compression operator based on Voronoi vector quantization. Its theoretical properties are analyzed and the variance bound is proved. Then it is applied in the Federated Learning setting and compared to the previously proposed compressors.
main_review: Overall this is good work on vector quantization, which seems to be the first one to prove the applicability of this approach for such large models as deep neural networks. It presents a sound theoretical analysis and may give rise to further exciting research based on the proposed idea. This is mainly why I think it may deserve publication at the conference.

The submission is clearly written and well organized, though I believe it can benefit from moving some technical details on pages 4-5 to the Appendix. 

My main concerns/requests are to explicitly and carefully say about the memory requirements and computational complexity of the proposed compression method and highlight the differences to the previous approaches. I would like the authors to measure the average time of the suggested technique required for compression and decompression. It is an important aspect, which in some cases limits the applicability of the compressors in the distributed learning [1, 2]. In addition, it is not compatible with All-Reduce, which significantly worsens the efficiency for the distributed training.

Besides, there is almost no experimental study of DoStoVoQ’s performance with respect to its algorithm parameters $L, M, P$. So, I hope that the current paper will be complemented with such results.

Minor issues/comments:

It seems that the authors missed a recent line of recent [3, 4] on compressors based on Kashin representation or Hadamard transform combined with stochastic quantization and the follow-up relevant papers.

[1] Xu H., et al. “Compressed communication for distributed deep learning: Survey and quantitative evaluation”. [Technical report](https://repository.kaust.edu.sa/handle/10754/662495), 2020.

[2] Agarwal S., et al. “On the Utility of Gradient Compression in Distributed Training Systems”. arXiv preprint arXiv:2103.00543, 2021.

[3] Caldas S., et al. “Expanding the Reach of Federated Learning by Reducing Client Resource Requirements”. arXiv preprint arXiv:1812.07210, 2018.

[4] Safaryan M., et al. “Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor”. Information and Inference: A Journal of the IMA (2021).

[5] Saha R., et al. “Distributed Learning and Democratic Embeddings: Polynomial-Time Source Coding Schemes Can Achieve Minimax Lower Bounds for Distributed Gradient Descent under Communication Constraints”. arXiv preprint arXiv:2103.07578, 2021.
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

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper presents DoStoVoQ, a vector quantization method based on Voronoi quantization. It is claimed that the compression method is designed specifically for federated learning applications. Both theoretical analysis and empirical results are provided to show the effectiveness of DoStoVoQ.
main_review: Pros:
1. The paper is well-written and the idea is easy to follow. Improving the communication efficiency of federated learning is a promising research direction. 
2. The scales of the experiments are large enough to provide valid evidence on the performance of DoStoVoQ. 

Cons:
The major concern is that by looking at the results, I am not sufficiently convinced that DoStoVoQ works well in practice, e.g., it leads to 2.5% accuracy loss on ImageNet (line 376), which is not acceptable in practice. In my view, the latest communication efficiency method achieves almost the same final accuracy and does not require compressing the gradient [1] (though DoStoVoQ has the potential to achieve higher compression rates). Maybe one way to improve DoStoVoQ is to adopt the error feedback scheme, but more experiments are required to be done.

Other concerns are elaborated below:
1. It is claimed that DoStoVoQ is for FL. But both of the formulation and experiment settings are about normal distributed SGD. How to make DoStoVoQ compatible with FedAvg/FedProx [2-3]? How does DoStoVoQ perform under data heterogeneity? 

2. Vector quantization is not new in communication efficient distributed training. How does DoStoVoQ compare to [4]? 

3. In some sense, DoStoVoQ is similar to the low-rank based compression methods, e.g., PowerSGD, GradiVeQ and Atomo [5-7]. How does DoStoVoQ compare to them? 

4. As mentioned above, how to make DoStoVoQ compatible with error feedback? Intuitively, it should be easy to achieve. 

5. In the experiments, only compression rates are reported. Please also report the end-to-end wall clock time. 

Minor comments:
Missing references [6-7].

[1] https://arxiv.org/abs/2103.03936

[2] https://arxiv.org/pdf/1602.05629.pdf

[3] https://arxiv.org/abs/1812.06127

[4] https://arxiv.org/abs/1911.07971

[5] https://arxiv.org/abs/1905.13727

[6] https://arxiv.org/pdf/1811.03617.pdf

[7] https://arxiv.org/abs/1806.04090


=========== Post rebuttal ==============
After carefully reading the authors' response, part of my concerns is addressed. Thus, I increase my overall evaluation score from 4 to 5. However, I still have the concern on the real speedup that the proposed method can achieve. Please refer to my comments below.
====================================
limitations_and_societal_impact: My major suggestions are summarized in the “Cons” of “Main review”. Please take a close look at it. Overall, the proposed method can be improved to attain better results on real-world large-scale ML tasks.
review_title: null

Meta-review: The paper proposes a new way to quantize SGD updates, and provides theoretical analysis and empirical validation in distributed settings (but not it seems in Federated settings where multiple updates happen at clients). The paper has several interesting contributions, but also needs a better comparison with the literature and connection to the FL setting (if that is what it is targeted for). I would encourage a resubmission to a subsequent venue with these fixes.
Decision: Reject