Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper introduces a new, simple yet theoretically and practically effective compression technique: natural compression. Theoretically, the compression technique increases the second moment of the compressed vector by not more than the factor of 9/8. Empirically, the communications savings are substantial, leading to 3-4 times improvement in overall running time. 

Overall, I think the paper is theoretically solid and empirically validated. I tend to acceptance. 

Pros: 
1.  Theoretically grounded and rigorous criterion for compressing the information. The authors also give the theoretical and geometric interpretation why the natural compression technique can reduce communication without sacrificing too much accuracy. 
2. It theoretically demonstrates that the savings in communication due to compression can outweigh the iteration slowdown, which leads to an overall speedup. This is not common in existing compression work. 
3. The simulation considers various distributed learning settings and several standard datasets. It also considers the compatibility of the proposed compression schemes to the current IEEE standard and current programmable network switches. This provides evidence on the practical impact of the proposed compression scheme.  

Cons: 
1.   The literature review seems outdated. Considering various compression techniques (quantization and sparsification) have been proposed during the last two years, more recent work needs to be discussed and compared, e.g.,

Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification and Local Computations, NIPS 2019
Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradients, NIPS 2019
Online Learned Continual Compression with Adaptive Quantization Modules, ICML 2020
Moniqua: Modulo Quantized Communication in Decentralized SGD, ICML 2020 
 
2.  In the simulations, the baselines are lacking. Specifically, the proposed compression techniques only compare with non-compression schemes, which is not sufficient. 

review_title: Natural Compression for Distributed Deep Learning Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposed a new compression scheme called natural dithering, which uses powers of 2 as quantization levels in gradient compression. The variance of the scheme is studied and the compression scheme is tested in neural network training experiments.

Pros:
The proposed compression scheme is easy to implement in practice and the experiment results show it can reduce training time in practice. The study on different aspects of natural dithering is quite comprehensive, including the variance, comparison with standard dithering, and the limit regime when the number of bits goes to infinity (where standard dithering is better).  

Cons:
My main concern is the novelty of this paper. Although discussions in the paper are quite comprehensive, the proposed compression scheme is just changing the uniform quantization levels to powers of 2. The idea is quite trivial and standard especially given the current machine representation of floating-point numbers. 

review_title: A stochastic quantization scheme with log-scale quantization levels

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a novel unbiased bidirectional compressor for vanilla SGD to reduce the communication overhead. Both theoretical and empirical analysis are provided. In overall, the paper is technically sound.

My concerns are mainly about the the significance of the proposed method in practice and the comparison to the previous work:

1. Dist-EF-SGD [1] and SignSGD [2] both achieve nearly 32x bidirectional compression, while natural compression only achieves roughly 8x in the experiments. Although this paper focuses on unbiased compressors and Dist-EF-SGD and SignSGD are biased compressors, the gap in the compression ratio is hard to ignore, which makes it hard to claim that this paper achieves SOTA in practice.

2. For the CIFAR-10 experiments, all the models (the smallest is ResNet50) are heavily over-parameterized, which means that there is huge redundancy in the gradients and models themselves. As a result, it will be easy to converge to small training loss for any compressor. Furthermore, since the experiments lacks comparison to other works (the only baseline with compression is standard dithering), it's hard to justify the importance of the proposed compressor. It will be better if the authors could show results on simpler models such as resnet20.

3. The paper lacks comparison to other methods. I still highly recommend to compare to dist-EF-SGD [1], since it achieves SOTA performance in communication-efficient distributed SGD. For other compressors, I understand that the other unbiased compressors may not have bidirectional compression. However, SignSGD [2] achieves bidirectional 32x compression without error feedback (error feedback improves the convergence of SignSGD, but not neccessary in some cases). Although SignSGD is biased compressor, it satisfies the requirement "vanilla distributed SGD with bidirectional compression" mentioned in Section 4, which makes it a good baseline. However, SignSGD is not compared or cited in this paper.

4. Most of the experiments are relatively small. For the ImageNet experiments in the appendix, no comparison in training time is provided.


References:
[1] Zheng, Shuai, Ziyue Huang, and James Kwok. "Communication-efficient distributed blockwise momentum SGD with error-feedback." Advances in Neural Information Processing Systems. 2019.
[2] Bernstein, Jeremy, et al. "signSGD: Compressed Optimisation for Non-Convex Problems." International Conference on Machine Learning. 2018.
review_title: My concerns are mainly about the the significance of the proposed method in practice and the comparison to the previous work

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a data compression method named natural compression. This method can be implemented very fast and could be added to other compression methods for additional compression. Then this is generalized to natural dithering for a more aggressive compression. In addition, it compares different compression methods for a bidirectional compressed SGD method. 

Strength:

- This compression method is very fast and can be combined with other compression methods. This compression has a small relative variance. It also has advantages in hardware implementation. 

Weakness:

- Except for the compression method, the optimization algorithms discussed in this paper is the standard parallel SGD. There are many advanced optimization algorithms in the literature, and it is more important to see its performance of this compression method on those advanced algorithms. Two examples are DoubleSqueeze (Parallel stochastic gradient descent with double-pass error-compensated compression) and DORE (A Double Residual Compression Algorithm for Efficient Distributed Learning), and both algorithms have bidirectional compression. 
- The compression rate is large comparing to other data compression methods such as p-quantization in the paper (Distributed Learning with Compressed Gradient Differences). Also, the comparison in A.4 may be unfair for the standard dithering. For standard dithering, the variance is bounded, while the variance for natural compression is relatively bounded. Therefore, for large values, the variance of natural compression is larger than standard ones (the same applies to Theorem 2), while small values favor natural compression. In the analysis, the relative variance is applied, so the result does not favor standard ones. It would be more interesting to compare different compression methods in solving various types of machine learning problems with different algorithms. 
- Table 1 may not reflect the speedup in real implementation. As mentioned above, the analysis is based on the relative variation, so it would be interesting to see the comparison in numerical experiments as well. 
- Line 4 in the caption of Table 1. The second sentence is not completed. 
review_title: Recommendation to Reject: Not enough contribution

Meta-review: Three reviewers provided negative reviews and the authors wrote detailed feedback. During the later discussion stages, the reviewers acknowledged that some concerns are alleviated (e.g. R1 raised score from 4 to 5), but two concerns still remain: i) the novelty is less clear to the reviewers; ii) the advantage over existing approaches is not strong enough. I personally think the first concern is somewhat subjective; for the second concern, the authors indeed added a few experiments on "comparison to Top-K, SignSGD, EF-SignSGD, and PowerSGD", but R1 still maintained that the comparison is "not well demonstrated", which I guess is because R1 views the two works mentioned in R1's review as "concurrent or later" while R1 pointed out in the discussion that those two works appear before Oct 2019.  
R2 pointed out that the paper could have shown the advantage in one of two aspects (see below) but did not. 
See the discussions of the three reviewers below.

R1
"The advantage of the proposed compression method over existing approaches is not well demonstrated."
R2:
"To justify the significance of the contribution, I think the paper should show at least 1 of the followings:
When approaching a very high compression ratio, the natural compressor has significantly better testing accuracy compared to the previous work, i.e., the proposed work could push the compression ratio higher than the previous work with nearly no accuracy loss. The authors could use the new compressor alone, or combine it with some other compressors such as top-k, as the authors mentioned in the answers. (However, according to the extra experiments, the testing accuracy is slightly better than top-k, and slightly worse than power-k. None of them makes a significant difference.)
The natural compressors can achieve similar accuracy compared to the previous work with the same compression ratio, but with much less computation overhead. (I think this one may work for this paper, as the authors mentioned in their answers. However, to justify such a contribution, we will need to check the training time compared to EF-SGD with top-k and power-k, which seems not included in the extra experiments.)"
R4: 
"I stand with my point that the novelty is limited."

Overall, I think the paper might have presented an interesting idea, but unfortunately can not be accepted in the current form. 

Decision: Reject