Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors present a new scheme for compressing gradients for use in distributed training. In addition to the previously proposed techniques of sending the sign of the gradient components along with the scale, and the use of error feedback (each sender tracks the error introduced by quantization, and adjusts future gradient updates using it), the authors also propose to exploit the temporal correlation of gradient values (i.e., over successive steps). They do so by computing the delta between two steps, and then use a hyperparameter $\alpha$ to keep only a fraction of the deltas and that is sent losslessly.

The idea is an interesting (even if a fairly simple one) and leads to a greater than 50% savings.

However, I am confused about a basic issue. From the authors’ own data (Figure 2 and text) and from other research on alignment of per-example gradients (e.g. https://arxiv.org/abs/1901.09491, https://arxiv.org/abs/2008.01217), for the bulk of training, actual temporal correlation between gradients is quite low. So how can delta compression help? 

(As an aside, the correlation is likely to be quite affected by batch size as per the second reference above, so some exploration/data around that would also be useful in the context of this proposal.)

This leads me to believe that the compression benefit they are seeing comes from higher values of $\alpha$, i.e., by throwing away information. So a natural question is: What happens if you simply do lossy compression on gradient signs? You would have to go to 3 values (+1, 0 and -1), and there would likely be some natural sparsity, and $\alpha$ could be used to enhance that. That would appear to be an interesting baseline to see how much benefit comes from the temporal aspect v/s the lossiness induced by $\alpha$. These two appear to be currently confounded. (Related: how does $\alpha$ = 0 look in Figure 1? Pretty bad from a compression point of view presumably. If so, then the benefit really comes from lossiness rather than temporal correlation?)

---

### After Rebuttal

Increasing rating based on the authors' clarifications on the source of the gains. Open to further changes based on further review and discussions with other reviewers
  
review_title: Interesting work but there appears to be a basic problem

final_score: rating: 2: Strong rejection
review_content: 1.	The main problem I have with this paper is that this paper idolizes the paper [distributed EF-SGD by Zheng et al. NeuRIPS 2019]. However, the main result, that is, Theorem 1 in dist-EF-SGD is mathematically problematic or simply wrong. The proof of Theorem 1 as given in [distributed EF-SGD by Zheng et al. NeuRIPS 2019] does not hold good when the learning rate sequence $\eta_t>0$ is decreasing. Therefore, the authors’ claim in the Abstract and several parts of the present paper “We strengthen their analysis to show that the rate of convergence of two-way compression with error- feedback asymptotically is the same as that of SGD” eventually invalid. I suggest the authors please read the distributed-EF-SGD paper carefully, understand it better, write the proofs on their own before making these types of strong claims. Please study [1] and work on your proofs. 
2.	Page 2: “However, Karimireddy et al. (2019) theoretically show that SGD with compression does not converge in general.” This is a very strong statement which I do not agree with. Karimireddy et al. (2019) showed how error feedback can fix the convergence issue of sign-based quantization as in signSGD. Moreover, they showed how any compressor (biased/unbiased) can be converted to a $\delta$-compressor. But that does not mean the authors’ statement in this manuscript is correct. As authors claimed “error feedback-based algorithms circumvent the convergence issues for SGD with compression” is not right. Error feedback is known to work well for sparsification, where a subset of gradient components are sent or for extreme quantization (such as sign-based compressions). However, regular random dithering-based quantization techniques such as QSGD, natural compression, etc. converge just fine without error feedback. Actually, error feedback may degrade their performance. I would like to request the authors to first understand these works in detail before writing these types of strong statements on their paper.  
3.	Another vague statement is: “Therefore, these two classes can be respectively thought of as approaches that reduce the quantity versus the quality of the gradient.” Based on what you claimed this? 
4.	“Sign-based compression schemes such as Scaled-sign, SignSGD and Signum (Bernstein et al., 2018)…” SIGNUM is not a sign-based compressor. It is the momentum version of signSGD, nothing novel. 
5.	You may want to talk about the most relevant and recent work on compression known as SketchML [J.  Jiang,  F.  Fu,  T.  Yang,  and  B.  Cui,  “SketchML:  Accelerating Distributed Machine Learning with Data Sketches,” SIGMOD, 2018] while talking about delta encoding first paragraph in Section 3. This recent paper on gradient compression uses delta encoding. 
6.	I failed to understand the benefit of Generalized dist-EF-SGD algorithm in Section 3? What are the main differences telling me? 
7.	“In our case, while the length of the parameter vector d is well over a million for models of practical interest, the entries of b are not necessarily i.i.d..” Can you make an assumption of the independence of the gradient components? If you make that assumption you may elevate the issue. Also, the assumption is not a strong assumption and generally made for stochastic gradients. Please See [Huffman Coding Based Techniques for Fast Distributed Deep Learning, Gajjala et al., CoNext DistML workshop, 2020]
8.	Uniform upper bound of the stochastic gradients g_i is an obsolete concept. The authors may argue that "The classical theoretical analysis of SGD assumes that the stochastic gradients are uniformly bounded". But one can even strongly argue that this bound is actually $\infty$. Moreover, an even a stronger argument can be made that the above assumption is in contrast with strong convexity. Please see ["SGD and Hogwild! Convergence Without the Bounded Gradients Assumption" by Nguyen et al.] as one of the instances. Please understand there are relaxed assumptions such as Strong growth condition on a stochastic gradient as in Assumption 4 of [2]. 
9.	You said: “Since the communications component in Horovod is designed for a master-less setup, we simulate a master-worker environment in our implementation.” But I was wondering why do you need this? In any case, if you use all-reduce collective for aggregation even for P2P architecture the aggregation will be similar. Please correct me if I am wrong. 
10.	While ImageNet accuracy is similar to why test accuracies of the models on CIFAR-100 and ImageNet-32 are below 60%?
11.	In terms of experimental results, instead of Figure 1, the authors may use relative data-volume vs. test accuracy. Especially, when the accuracy figures are really cluttered. To do proper experiments by using compression techniques, the authors can check a very elaborative work and codebase by [Hang Xu et. al, Compressed Communication for Distributed Deep Learning: Survey and Quantitative Evaluation.] In that case, I would encourage the authors to plot relative data-volume vs. test accuracy similar to Figures 6 and 7 therein. I am sorry but in the present papers, the experiments and their presentations are substandard. 
12.	 Why did not you compare with sign-sgd algorithm? Also, sign-based algorithms are notorious in their convergence. SignSGD uses a special stepsize. So I was wondering what is your step-size schedule? You never mentioned this in your paper. You may did it in the Appendix and I did not check the Appendix. So, please indicate if you did. 


Minor Comments:

1.	These two sentences in my understanding are claiming the same thing? 
“We strengthen their analysis to show that the rate of convergence of two-way compression with error feedback asymptotically is the same as that of SGD. As a corollary, we prove that two-way SignXOR compression with error-feedback achieves the same asymptotic rate of convergence as SGD.”
2.	“Novel approaches such as federated learning…” Why is it novel? Unnecessary hyperbole is not part of technical writing. 
3.	“In this section, we prove that the combination of Algorithm 1 and Algorithm 2 converges, and the convergence rate is asymptotically the same as that of SGD.” Why Algorithm 2 when Algorithm 1 implicitly implies the inclusion of Algorithm 2?
4.	Please correct the typos and please write as it is done in a technical paper, not in a sci-fi novel. 

[1] Communication-Efficient Distributed SGD with Error-Feedback, Revisited, Tran Thi Phuong, Le Trieu Phong, 2020. 
[2] Dutta et al. AAAI 2020, On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learning
review_title: The authors proposed a bidirectional gradient compression scheme called SignXOR for distributed training. 

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes a gradient compression approach to remove the communication bottleneck in distributed stochastic gradient descent. I think the key attributes of their algorithm are as follows:
- It uses error feedback (Stich et al., 2018; Karimireddy et al., 2019) and operates in a parameter server model based on (Zheng et al. 2019)
+ The compressor sends the sign of each gradient coordinate and a scale factor per 'block' of coordinates (like Zheng et al. 2019)
+ The messages are compressed with lossless entropy encoding.
+ Specifically, they send and encode the difference between the current sign vector and the previously transmitted one. This is meant to lower the entropy of the vectors (make the distribution of -1's and 1's less even)
+ Because the distribution of -1's and 1's is still roughly 50/50 after delta-coding, the authors introduce (lossy) noise in the compressor. They randomly flip some instances of 'same sign as before' to 'different sign than before'. This reduces the entropy of the 'difference vector' so it can be compressed more.

I believe the main contributions of the paper are:
- The introduction and evaluation of lossless compression on top of sign-based gradient compression
- A theoretical improvement of the constants in the rates from (Zheng et al. 2019)
- A proof that SignSGD with delta-coding and a bias towards changing signs can still be a $\delta$-compressor, as long as the bias is extremely small (not covering the experiments presented in the paper)

I find the ideas presented in this paper interesting and novel and the experiments well executed. The writing is of good quality, and I find it easy to follow. I do, however, have two concerns:
- The method is said to exploit temporal correlation in the gradients by using delta coding. To me, this seems misleading. The authors show that, without the introduced bias, there is not much gain from delta coding ("In our experiments presented in Section 5.2 we observe that when α = 0, p remains close to but slightly lower than 0.5. This implies low correlation between [..]. Our solution is to make $\alpha > 0$."). With the proposed solution, the method exploits patterns created artificially by lossy compression, rather than temporal correlation in the gradients. Given that p < 0.5, this is actually anti-correlation rather than correlation. The signs are more likely to flip due to previously introduced errors.
- If the delta-coding scheme indeed fails to leverage temporal correlation in the gradients without artificially introducing extra errors, the proposed scheme doesn't really do what it seems to be designed for. This makes it less elegant/complicated. This lack of simplicity could be compensated by convincing experimental results, but it seems that many gradient compression schemes achieve similar results to the proposed scheme at similar compression rates (see Xu et al. https://repository.kaust.edu.sa/bitstream/handle/10754/662495/gradient-compression-survey.pdf) for an overview). I am not convinced by the benefits of the proposed scheme over others.
review_title: Interesting approach to combine sign-based gradient compression with lossless encoding. Not convinced about the 'temporal correlation'.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposed an extension of blockwise scaled sign compressor in Zheng et al. (2019). The proposed method exploits the temporal correlation between two consecutive gradients. The authors show that one can have a higher compression rate by inserting distortion to the compressed gradient. A tighten bound is provided such that the asymptotic rate (including constant) is exactly the same as the full-precision counterpart. The experiments show that the proposed compressor can achieve additional 40%-50% reduction on communication compared to the scaled sign. Overall, the reviewer thinks the idea is interesting. The reviewer has a few comments:

1. The proposed method considers randomly flipping the direction for elements that have the same sign as the averaged gradient in the last step. In this way, the sign is always correct for the elements that have opposite direction from the last gradient. I wonder will the results change if we consider flipping the sign of the elements that have opposite direction?

2. Since alpha has a very small upper bound, it is hard to see any theoretical improvement over scaled sign.

3. Theorem 4.2 does not show that one can achieve a linear speedup, i.e., O(1/\sqrt{nT}) rate.

4. For the distributed training with high speed network, the extra overhead incurred by compression is not trivial and cannot be overlooked. As there is no results against CPU wall clock time, it is not clear if the proposed method is really faster than the scaled sign in terms of elapsed time.

5. Can you show the final test accuracies on ImageNet achieved by each algorithm? It seems that scaled sign has slightly higher accuracy.
review_title: Official Blind Review #1

Meta-review: The paper introduces a new scheme for compressing gradients in distributed learning which is argued to exploit temporal correlation.

The paper received very detailed reviews and generated a lot of discussions (thank you to the reviewers for the amazing job).  Many reviewers acknowledge that this is interesting work, a simple and potentially useful algorithm but pointed out many problems with discussion, theoretical analysis, and experiments (e.g., it was not clear to R4 and R3 that these are temporal correlations which are beneficial rather 'lossiness'). Some of these issues were addressed and the current version is currently much stronger than the initial submission (and stronger than the low average scores suggest). Still, the reviewers do not believe that the paper is ready for publication and I share this sentiment. I would strongly encourage the authors to invest more effort in addressing the reviewers' comments and resubmit the work to one of the upcoming top conferences.
Decision: Reject