Compressing gradients in distributed SGD by exploiting their temporal correlation
Authors: Tharindu Adikari
Stark Draper
Venue:  (2021)
Keywords: distributed optimization
gradient compression
error-feedback

Abstract: We propose SignXOR, a novel compression scheme that exploits temporal correlation of gradients for the purpose of gradient compression. Sign-based schemes such as Scaled-sign and SignSGD (Bernstein et al., 2018; Karimireddy et al., 2019) compress gradients by storing only the sign of gradient entries. These methods, however, ignore temporal correlations between gradients. The equality or non-equality of signs of gradients in two consecutive iterations can be represented by a binary vector, which can be further compressed depending on its entropy. By implementing a rate-distortion encoder we increase the temporal correlation of gradients, lowering entropy and improving compression. We achieve theoretical convergence of SignXOR by employing the two-way error-feedback approach introduced by Zheng et al. (2019). Zheng et al. (2019) show that two-way compression with error-feedback achieves the same asymptotic convergence rate as SGD, although convergence is slower by a constant factor. We strengthen their analysis to show that the rate of convergence of two-way compression with errorfeedback 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. We numerically evaluate our proposed method on the CIFAR-100 and ImageNet datasets and show that SignXOR requires less than 50% of communication traffic compared to sending sign of gradients. To the best of our knowledge we are the first to present a gradient compression scheme that exploits temporal correlation of gradients.

Under review as a conference paper at ICLR 2021
COMPRESSING GRADIENTS IN DISTRIBUTED SGD BY EXPLOITING THEIR TEMPORAL CORRELATION
Anonymous authors Paper under double-blind review
ABSTRACT
We propose SignXOR, a novel compression scheme that exploits temporal corre- lation of gradients for the purpose of gradient compression. Sign-based schemes such Scaled-sign and SignSGD (Bemsttei et al. 2018 Karimireddy et al.) 2019) compress gradients by storing only the sign of gradient entries. These meth- ods, however, ignore temporal correlations between gradients. The equality or non-equality of signs of gradients in two consecutive iterations can be represented by a binary vector, which can be further compressed depending on its entropy. By implementing rate-distortion encoder we increase the temporal correlation of gradients, lowering entropy and improving compression. We achieve theoreti- cal convergence of SignXOR by employing the two-way error-feedback approach introduced by Zheng et al. (201)). Zheng et al. (2019) show that two-way com- pression with error-feedback achieves the same asymptotic convergence rate SGD, although convergence is slower by constant factor. We strengthen their analysis show that the rate convergence of two-way compression with error- feedback asymptotically is the same as that of SGD. As corollary we prove that two-way SignXOR compression with error-feedhack achieves the same asymp- totic rate of convergence as SGD. We numerically evaluate our proposed method on the CIFAR-I00 and ImageNet datasets and show that SignXOR requires less than 50% of communication traffic compared to sending sign of gradients. To the best our knowledge we are the first to present a gradient compression scheme that exploits temporal correlation of gradients.
INTRODUCTION
Distributed optimization has become the norm for training machine learning models on large datasets. With the need train bigger models on ever-growing datasets, scalability of distributed optimization has become key focus in the research community. While an obvious solution to growing dataset size is to increase the number of workers, the communication among workers has proven to be bottleneck. For popular benchmark models such AlexNet, ResNet and BERT the communication can account for a significant portion of the overall training time (Alistarh et al.) 2017 Seide et al.) 2014 Lin et al. 2018). The BERT ("Bidirectional Encoder Representing from Transformers") " architecture for language models (Devlin et al.] 2018) comprises about 340 mil- lion parameters. If 32-bit Noating-point representation is used one gradient update from worker amounts to communicating around 1.3GB (340 x 10th parameters x 32 bits per parameter x 2 2-33 gi- gabytes per bit x 1.3GB). Frequently communicating such large payloads can easily overwhelm the network resulting in prolonged training times. In addition, large payloads may increase other forms of costs in distributed optimization. Novel approaches such as federated learning employ mobile devices as worker nodes. Exchanging information with mobile devices is heavily constrained due to communication bandwidth and budget limitations. Therefore, communication remains an important bottleneck in distributed optimization and reducing communication is of utmost importance.
Gradient compression alleviates the communication bottleneck. The idea is to apply a compression scheme gradients before sending them over the network. There has been an increasing amount of literature on gradient compression within the last few years (Seide et al.
2014:
Aji Heafield
2017 Alistarh et al.) 2017 Wen et al. 2017 Wangni et al.) 2018 Wu et al. 2018 Lin et al. 2018
Wang et al.] 2018). Such compression schemes have been demonstrated to work well with dis-
tributed stochastic gradient descent (SGD) and its variants. However, SGD with arbitrary compres-

---

Under review as a conference paper at ICLR 2021
sion schemes may not converge. Karimireddy al. 2019 give one example of non-convergence. The recently proposed freobrfeedbcck based algorithms (Stich et al. 2018 Karimireddy et al. 2019) circumvent the convergence issue. frror-feedback methods accumulate the compression error and feed it back to the input of the compression scheme so that the error gets transmitted over subsequent iterations. The dist-EF-SGD algorithm proposed by ZZheng et al. (2019) applies aroo-feedback to two-way compression, in which both worker-to-masee to-metter and master-to master-to-worket communications are compressed. Theoretical guarantees provided by dist-EF-SGD are valid for all compression schemes that fall under the definition of "a-approx compressors' also referred to as ó-compressors. The authors prove that errorfeedbbcc with way compression asymptotically achieves the ((1/VT) convergence rate of SGD. However, the analysis by Zheng et al. (2019) suggests that dist-EF-SGI converges slower than SGD by a constant factor.
Our contributions in this paper are as follows. We propose SignXOR, a novel compression scheme that exploits temporal correlation of gradients. We prove that SignXOR is 5-compressor, and we provide convergence guarantees for SignXOR by employing dist-Er-SGD. We strengthen the convergence bound by Zheng et al.] (2019) to show that dist-EF-SGD asympiotically converges at the same O(I/VT) rate SGD. Consequently, we show that the proposed method asymptoti- cally achieves the SGD convergence rate. We empirically validate the proposed method on CIFAR- 100 and ImageNet datasets and demonstrate that the ratio between total communication budgets of SignXOR and Scaled-sign is less than 50%.
Notation:
For RR x[j]] denotes the jth entry of x, ||æ||a denotes the f1-norm, and ||>||| denotes the f2-nomm. For vector inputs sgn(.) function outputs the sign of the input element-wise. The index set (1, [1,...,n} is denoted by [n], and denotes elementwise multiplication.
RELATED WORK
The most common gradient compression schemes can be categorized into those based on sparsifica- tion and those based on quantization. The methods based on sparsification such as Top-k, Rand-k (Stich al.) 2018 Lin et al., 2018) and Spectral-ATOMM (Wang et al., 2018) preserve only the most significant gradient elements, effectively reducing the quantity of information carrying gradi- ent components. On the other hand, the methods based on quantization such as QSGD (Alistarh) eet al. 2017], TemGGad (Wen et al. 2017) and SignSGD (Bernstein et al.) (2018) reduce the overall floating-port pointttpppnntttto precision of the gradient. Therefore, these two classes of methods can be respectively thought of as approaches that reduce the quantity versus the quality of the gradient. One can think of this in analogy to image compression. For example, JPEG image compression that is based on discrete cosine transform determines both which transform coefficients to store (the quantity) and at what level of resolution to store those coefficients (the quality).
Sign-based compression schemes such as Scaled-sign. SignSGD and Signum (Bernstein et al. 2018) sit at the far end of quantization- levels, +1 and -1. For example, the compressing function of Scaled-sign takes in vector and the decompressing function outputs the vector (||=]l//d) sgn(x). This means that the com- pressed representation needs to store only the sign of each entry x15]. along with the scaling constant ||a]///d /d. In practice one can avoid the 'zero' output of sgn by mapping it to +1 or -1. This allows the two outcomes +1 and -1 be represented using one bit per entry, making the size of the com- pressed representation d + 32 bits in total (assuming 32-bit single-precision representation of the scaling constant). As per Shannon's 's source coding theorem (MacKay 2003 p. 81), the sequence of +1 and -1 can be further compressed without any information loss if the probability of encounter- ing +1 different from that for 1. However, in our experiments on Scaled-sign compression we observe that both outputs are equally likely across all iterations.
algorithms. Such schemes quantize real values to only two
Rd,
Any lossy gradient compression scheme introduces noise, also known as distortion, in addition to the measurement noise that is already present in the stochastic gradients computed by the workers. It is reasonable to expect the additional compression error hurts the convergence rate of the algorithm. However, it has been empirically observed that significan cant compression ratios can be achieved before observing any impact on convergence (Seide et al. 2014, Alistarh et al., (017). One can achieve even greater compression while keeping the convergence rate nearly the same by employing error- feedback (Stich et al.] 2018) Karimireddy et al., 2019 Zheng et al.) 2019)). Algorithms based on error-feedback accumulate the compression error in past iterations and add it to the input of the
2

---

Under review as a conference paper at ICLR 2021
compressing function. This allows all of the gradient information to get transmitted over sequence of iterations, albeit with a delay. For smooth functions the gradient does not change considerably, therefore, the delay does not significantly impact the rate of convergence.
The dist-EF-SGD algorithm proposed by Zheng et al. (019)) is based on error-feedback and of- fers two-way compression under the master-worker topology. The dist-EF-SGD algorithm provides convergence guarantees for 5-compressors. An operator C' Rd - Rd is a d-compressor for all Rd if |[C(x) - z1|²² < (1 6) ||= for some E (0, 1]. The ō is measure of the distortion due to applying C. A good compressor will have ō close to 1 and a large compression ratio. One can show that Scaled-sign is a --approximate compressor. The Scaled-sign compression scheme with dist-EF-SGD offers convergence guarantees under standard assumptions even though Scaled-sign without feror-feedback may not converge (Karimireddy et al., 2019). Zheng et al. (2019) generalize the dist-EF-SGD algorithm to include blockwise compression, in which the gradient is partitioned into blocks that are compressed separately. A natural partitioning method is to consider as blocks the elements of deep neural network such as tensors, matrices and vectors. Blockwise compression allows better exploitation of redundancy that may be present only within a block.
Zheng et al. (2019) empirically demonstrate that Scaled-sign with dist-EF-SGD achieves almost the same performance of SGD with respect to training loss and test accuracy. This indicates that allow more distortion in the compression before observing significant impact on training performance. The proposed SignXOR compression is based on allowing additional distortion in the interest of achieving higher compression ratio.
3 PROPOSED ALGORITHM: SIGNXOR
Our proposal is motivated by the concept of delta encoding. Delta encoding refers to techniques that store data as the difference between successive samples, rather than directly storing the samples themselves (Smith et al. 1997). One often encounters delta encoding in applications such as integer compression and video compression. For example, it is more space efficient to store the first-order differences of a digitized audio signal than to store the values of the original signal. First-order dif- ferences have smaller magnitudes compared to the original sequence and, therefore, the differences can be represented by a comparatively smaller number of bits. A similar approach is used in the inter-picture prediction method in high efficiency video coding (HEVC) (Sze et al. 2014). Inter- picture prediction makes use of temporal correlations across video frames encoding the differences between frames. This requires less storage compared to storing each video frame. Jiang et al. (2018) employ delta encoding in a more related application to distributed optimization. At the core of their algorithm, delta encoding is employed to compress increasing sequence of integers.
Our SignXOR algorithm applies delta encoding to represent temporal changes in the gradient. In essence, SignXOR maintains a binary vector that indicates whether the sign of gradient entry is equal (or not equal) to the sign of the corresponding entry in the previous gradient. The equality (or non-equality) can be represented by a binary 1 (or 0). This procedure resembles the binary XOR operation, hence the name SignXOR. We employ generalized version of original dist-EF-SGD by Zheng et al. (2019) (the original dist-EF-SGD is specified in Algorithm 2 therein) to provide conver- gence guarantees for the proposed compression scheme. The generalization is to make dist-EF--SGD compatible with SignXOR. We outline the proposed method in Algorithm I and Algorithm 2
Generalized dist-EF-SGD: Algorithm | presents generalized dist-EF-SGD for setup with mas- ter and n workers. The three main differences between the generalized and original dist-EF-SGD versions are as follows. First, Algorithm I delegates compression and decompression tasks to two separate functions encode and decode. Second, Algorithm maintains a vector 9, at all nodes in- cluding the master. The vector 9₁ is the average gradient all workers used to update the parameter vector Wp. in the last iteration. Third, the encode and decode functions each take the last gradient Ig the second argument. This is in contrast to the original dist-EF-SGD algorithm in which com- pression is based only on the gradient in the current iteration. Since there are no differences related to compression performance between the original and generalized dist-EF-SGD algorithms, they encompass the same theoretical guarantees.
The compressing function encode takes in two inputs and outputs Gj. This output is the actual payload sent master over the communication channel. In addition to g the ith worker also
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Generalized dist-EF-SGID compatible with SignXOR
input : imitial parameter vector Wgi step sizes (70....,,7. 7r-11
initialize: let O be the all-zeros vector of dimension d;
let Do E IRd vector with entries sampled uniformly from [-1, on ith worker store 9o 6j to 0 set parameter vector wp on master store 9u set Eg to 0
for E {O...., T 1} do ith worker
compute 9% g + 1ej where g is the stochastic gradient at w
nh
compute g = encode ( Ix.) and g = decode (9h. 9a.
5
send G. to master and update error c = me (6 g%
receive 92 from master and compute Jk+1 = decode (9 9s.
7
update parameter vector Wx+1 = W 7k9K+1
on master
receive G and compute T3 decode(Gi Ix) for all i [n]]
compute O 1
n Eieln 9k da ck
compute 95 = encode (āx. 9x) and 92-1 de
11
12
broadcast 9r to all workers and update EK+1 = m7K (0 Ixt1):
computes 0% which is what the master will obtain by decompressing G The vector Dj is used to update < the compression error fed back in the next iteration. The master collects 9 from all workers and decompresses each to obtain z. All workers receive the master broadcast 9 and input it, along with Ig. to the decode function to decompress and obtain ØR+1- Note that in the kth iteration all nodes use the same 9д vector as the second argument in the encode and decode functions.
The encode and decode functions corresponding to SignXOR compression scheme are specified in Algorithm For the ease of explanation consider the specific case when the master compresses 9R to obtain Gg. and the workers decompress G₁. to obtain 9x+1 as approximation to 9k.
Algorithm 2: SignXOR compression and decompression
input: hyperparameter 0 <
/ <1:
function encode(x e Rd y E Rd:);
compute the fraction of +1's in sgn(r);
compute q, the fraction of elements in x such that sgn (x([]) sgn(yli))
initialize binary vector E {0, 1] to all-zeros:
for all j [d]. if sgn(>[5]) sgn(yli)) set bij] with probability 1 compute p. the fraction of I's in b;
6
compress b with a lossless scheme and compute scalar /
output G = (a, compressed representation of b):
function decode(G = {a E R, compressed representation of a vector b E {0, (0.1)"). Ry); expand and decompress G obtain and b; output sgn(y) @ (2h 1);
"
We consider the case when master calls encode with arguments x = 9r and y - Note that the scalars and are not used anywhere in Algorithm 2 These scalars help us describe the algorithm and also become useful our theoretical analysis. The output of encode function is random when * 0, and deterministic when
Compressing function:
O. Let first consider = 0, in which = sgn(,, (g (i)). This implies that p is the fraction of entries in
case b[j] = and only if Øg and D% that have the same signs. This is measure of the (positive negative) correlation between
4

---

Under review as a conference paper at ICLR 2021
the two vectors. The core idea in the proposed compression scheme is to compress the binary vector b using a lossless compression scheme. Shamnon's 's source coding theorem (MacKay 2003 p. 81) states that d i..d. random variables each with entropy Hp)) -p log, p - p) logg p) can be compressed into approximately (H) bits with negligible risk of information loss, as d + cc. In our case, while the length of the parameter vector d is well over million for models of practical interest, the entries of are not necessarily i.idd. However, we demonstrate in Section | that there exist readily available lossless compression algorithms that can compress 6 to very close (p) bits, the Shannon limit. Note that binary entropy H (p) is symmetric around 0.5, and satisfies S (p) I 1 with (0.5) = When p = 0.5 the size of the compressed representation gets close to d, which is same that offered by Scaled-sign. Further compression of b is only possible p is away from 0.5. In our experiments presented in Section 5.2 we observe that when a = 0. p remain close to but slightly lower than 0.5. This implies low correlation between 9J and Jg- We remedy this issue by making a > O. Next we explain how making a > 0 yiclds compression gains and, at the same time, induces correlation between 9r and 9x.
First, note that increasing a introduces distortion to 6, driving p away from 0.5 and towards O. A lower p decreases the entropy of b, yielding a higher compression ratio realized with the lossless compressor. Since we start with a p slightly less than 0.5, if we were to drive towards we would first increase (p) before starting to incur compression gains. For this reason, we design the encoder to push towards zero. In summary, increasing a offers rate savings in the current iteration by adding distortion the current gradient.
Second, we explain how added distortion induces correlation between 9% and 9x- Note that is a measure of correlation between the two vectors (gg and sgn( measured prior adding distortion using a. We emphasize that q does not depend on the errors introduced in the current iter- ation. Rather, q depends on a only through the past iterations. In the experimental results presented in Section 5.2 we observe that increasing a also decreases q. This means that in given iteration the inputs to the encoder are already correlated. Therefore, the b vector that encodes equality (or non- equality) of sgg( and sgn(0;) can be compressed even without adding distortion in the current iteration. The underlying mechanism that causes this temporal correlation in our encoder is error- feedback. Recall that the idea behind error-feedback is to keep track of the compression error in the last iteration and add it back to the input of the encoder in the current iteration (with correction for the step size). Specifically, 9. includes the compression error incurred in 9y- This feedback system induces the temporal relation between the two vectors that we see through q. In summary, our com- pression mechanism interacts with the error-feedback mechanism to increase temporal correlation which we then exploit to realize further compressive gains.
The suggested upper bound for a ensures theoretical convergence of the SignXOR algorithm. We show in Section 5 that in practice a can be increased considerably more than the suggested upper bound before seeing an impact on the training performance.
Let us now consider the case when a worker calls decode with arguments g=9, 9. and y = T.- The first argument G3 contains the scalar a and the compressed representation of binary vector b, which can be recovered exactly as compression of b is lossless. Noting that b computed with 0s as the second argument to the encode function, the output of the decoder is obtained by inverting the sign of I,] whenever b[j] is 0, and by scaling the result by a. One can compactly express the output of this operation as a sgn (7x) C (2b- - 1).
Decompressing function:
Remarks: Note that we can recover the Scaled-sign compression scheme by setting = 0 in Algorithm 2 In comparison to SignXOR, the compressed representation of Scaled-sign stores the sign of each entry in 9r. and the scaling constant a l10g l We demonstrate in Section 5.2 that r, the fraction of +1's in sgn(ûx),, is upproximately 0.5 across all iterations. This means that cannot compress further the sequence of signs, and the encoded representation of Scaled-sign requires at least d bits. Algorithm T can be easily extended to accommodate blockwise compression as was explained by Zheng al. (2019). In blockwise compression the gradient 9, is partitioned into blocks, and the blocks are processed separately using encode and decode functions. In our numerical experiments we employ the blockwise extension of Algorithm |
4 THEORETICAL GUARANTEES
5

---

Under review as a conference paper at ICLR 2021
In this section summarize theoretical results on Algorithm I and Algorithm 2 First, prove that the SignXOR compression scheme presented in Algorithm 2 is a 6-compressor. Second, show that for any 8-compressor the generalized dist-EF-SGD scheme in Algorithm converges at the same (1/VTT) rate as SGD. Putting these two together yields the desired result.
SignXOR is 6-compressor: We consider the general form of encode and decode functions, i.e., with inputs (z. for encode, and with inputs (G.y) for decode. Let us define the operator C بلتا| and the binary vector is such that _ + Rd where (x) = a sgn(z) o (2b 1) with a = d
6 = 1 with probability - if sgn x)) sgu(y), and b = 0 otherwise. Note that a and b have the same meaning as in Algorithm?? 2 The operator C (a:) is representative of decode (enoodeenc,ee(;; y), y), therefore, C% (z) is the SignXOR compressor. Since C is randomized operator, show that is a 6-compressor in expectation as stated in Theorem
Theorem 1. There exist a E (0, 1] such that [B) - x0|?] s (1 - -]][|=11 for all y E R if
1 1 (1-V1-1
Although the suggested upper bound for a is extremely small for large d, we demonstrate in Section 3 that in practice a can be set quite close to Next we discuss the convergence rate of dist-EF-SGD for an arbitrary 8-compressor.
The proof is provided in Appendix A.
Convergence rate of dist-EF-SGD: Zheng et al. (2019) compare the convergence rates of dist-EF- SGD and vanilla SGD in their Corollary 1. As authors note, although the convergence rates of the two algorithms are same in O notation, the former is slower by a constant factor. The differences between the bounds for dist-EF-SGD and vanilla SGD in Corollary 1 are as follows. In both cases, for large T the dominant terms are those with VT in denominator. The ratio between the dominant terms corresponding to dist-EF-SGD and vanilla SGD is 1.5, suggesting that the former always slower than the latter by factor of 1.5. In our Theorem 2 we strengthen the bound for dist-EF- SGD so that the dominant terms in the two algorithms are the same. This means that dist-EF- SGD achieves same convergence rate vanilla SGD in the limit as T - oc. Our proof is for an arbitrary 8 5-compressor that is not necessarily SignXOR. To this end we consider Algorithm ! and define C(xx) decode(encode((; y). v). We assume that C' is a 5-compressor for all y e R² i.c. []I[C(x) - x1 ==|2] < 0|[[= 1| for some ò E (0, 1]. We setup the optimization problem next.
Let F Rd I be a function that is lower bounded by F. and has a gradient VF. We con- sider distributed optimization setup with master and n workers. For some '', E Rd the ith worker calculates the stochastic gradient of at wxk- We assume that gj. is an unbiased estimate of F(w,),, and that of. has bounded variance. Specifically, we assume that g satisfies the two prop- erties EEgg |w,] F(W,,) and Elll (F(w))]] S o². We also assume that F is L-Lipschitz smooth, and that the gradient of bounded. The latter implies that B[[lg[ S G2 for some sealar G. The master and workers generate sequence (wo...., Wpp as per Algorithm I Convergence results of this system is summarized in Theorem
1 (1 27/7). the convergence of Theorem 2. For given wo and step size schedule Th TVT the system outlined in Algorithm 7 after iterations is given by
2L(F(wg) - F,,) o²
E
min
VF VF(W))1?
2V
2L(F(w,) FF)) + 8(1-8)G2
(1+
+ (+). (I)
62
O
2T3/1 - T1/1
We defer the proof of Theorem 2 to Section A.2 in the Appendix. In comparison, the bound for SGD has only the first term in []. Note that the last two terms in ( converge to zero faster than the first term. This means that dist-EF-SGD asymptotically achieves the same convergence rate as SGD. Since SignXOR is a 6-compressor we conclude that the proposed algorithm converges asymptotically the same rate SGD.

---

Under review as a conference paper at ICLR 2021
Table
Details of experiments and summary of findings.
Dataset
Model
Parameters
Workers
Batch size
Bx/Bs Bs
CIFAR- 100
ResNet-18 18
12,596,388
4
32
42%
ImageNet-32 ImageNet
WRN-28-2 ResNet-50
1,595,320
64
43%
25,583,592
16
16
47%
NUMERICAL EXPERIMENTS
We perform multi-GPU experiments on three datasets: CIFAR-100, ImageNet-32 and ImageNet. The ImageNet-32 dataset (Chrabaszez et al. 2017) is a down-sampled version of the ImageNet dataset which the images of size 32 x 32 pixels. All other properties such as the number of images and the number of classes are the same as the original ImageNet dataset. We experiment with ImageNet-32
alternative to ImageNet due the latter's heavy consumption of hardware resources. The additional experiments presented in Section 5.2 are performed with ImageNet-32. We train a wide residual network classifier (Zagoruyko Komodakis 2016) of depth 28 and width 2 (WRN-28-2) 2) using the ImageNet-32 dataset. The CIFAR-IOV and ImageNet datasets are used to train the ResNet-18 and ResNet-50 (He al., 2016) models respectively. all cases the dataset is partitioned to equal sizes and distributed among the workers.
We implement all algorithms using the TensorFlow and Horovod (Sergeev & Balso 2018) packages. Since the communications component in Horovod is designed for master-less setup, we simulate a master-worts worker environment in our implementation. We choose to use the Lempel-Ziv Caapel-Ziv-Markeee chain algorithm (LZMA) the lossless scheme that compresses the binary vector b. The LZMA compression scheme a member of the Lempel-Ziv family of compression algorithms (MacKay, 2003 p. 119.. While there exist other compression schemes in which for large the compression ratio converge to H (p) much faster than the Lempel-Ziv algorithms, in our experiments we employ I.ZMA as its implementation is readily available in Python. We refer the reader to Appendix Sec- tion for an comparison of H(p) and the compression ratio of 1 1.ZMA. In our implementation the encode and decode functions not tuned achieve best computational performance. We, there- fore, do not compare or plot measurements with respect to time. In our experimental setup, a single machine hosts four workers and each worker runs on a dedicated Tesla P100 16GB GPU.
We compare the performance of SignXOR to SGD and dist-EF-SGD with Scaled-sign compression. For Scaled-sign we use the original dist-EF-SGI scheme as the freo-ffedback mechanism. For SignXOR we use the generalized dist Eist-EF-SGG outlined in Algorithm [] Note that there are no compression performance related differences between the original and the generalized versions of dist-EF-SGID. In both cases we use blockwise compression, in which the gradients corresponding to tensors, matrices and vectors are compressed and decompressed separately. Training is started with learning rate of 0.1, and the learning rate is multiplied iteratively by 0.1 at certain epochs. These epochs are multiples 8, 10 and 5 for the experiments involving the CIFAR-100, ImageNet- 32, and ImageNet datasets, respectively. We use regularizer scaled by 10-3 in CIFAR- 100 experiments, and by 10 in the other experiments. Table I summarizes some additional details of the experiments. Batch size is per worker.
weight regularizer in all experiments. The
We define the following measurement to help us interpret our experimental results. Recall that in Algorithm g and 93 are the payloads that workers send and receive. Let 8 and sf denote the number of bits required store G3 and G in bits. Over T iterations with SignXOR, each worker bits. In contrast, if Scaled-sign average sends and receives a total of Bx 1/2 -T- Σie()) (s} +
compression is used each worker communicates bits in each iteration. making the total number of bits sent and received by each worker Bs 2Td. Therefore, Bx/ Bs is the ratio between the total bit usage of each algorithm. We tune the hyperparameter a in Algorithm [ so that SignXOR achieves the same test accuracy Scaled-sign within the same number of epochs.

---

Under review as a conference paper at ICLR 2021
10
SGD
7
SGD
SGD
Scaled--ign
Scalod-sigu
Scaled-sigu
10
SigXXOR 0.7.7
6-
SigXXOR ==7
8
SigXXOR 0.6
Loss
Sig
a-8.88
SignXOR 0-8.8
SignXOR
SigxXOR
a=0.9
SinXOOR 0.9
SignXOR a=0
SignXOR 0.95
4-
3
0.6
0.6
0.8
Test nccuracy
0.6
0.4
0.4
0.2
0.2
0.0
0.0
0.5
usage lby/ss
0.3
0.2
0.1
0.1
0.1
12
18
0
18
24
Epoch
Epoch
Epoch
Figure 1: The three columns present experimental results for CIFAR-100 100 (left), ImageNet-32 (mid- dle), ImageNet (right). In each case the three rows present plots of training loss (top), test accuracy (middle) and Bx/ Bs (bottom). The test accuracy plots indicate top-1 test accuracy for CIFAR-100, and top-5 for the other two. We run SignXOR experiments for multiple a values.
5.1
MAIN RESULTS
Figure presents results from multiple rums of the experiment with different values for a. For the CIFAR- (00 dataset, the SignXOR test accuracy plot corresponding
0.7 closely follows test accuracy of Scaled-sign and SGD. The same observation is true for plots corresponding to a = 0.7 and a 0.6 ImageNet-32 and ImageNet experiments respectively. For these choices of a, the plots of Bx/Bs indicate that in each case SignXOR achieves the top test accuracy with less than 50% of communication required by Scaled-sign. The last column in I Bx/ Bs that SignXOR achieves while attaining the same test accuracy as Scaled-sign by the end of training. Figure| also indicates that we can make a slightly larger than the choices listed in Table to achieve even smaller Bx/Bs with some reduction in the test accuracy. For example, the ImageNet-32 experiment corresponding to a = 0.9 achieves within 0.3 test accuracy Scaled- sign, but only using 12% of the communications usage of Scaled-sign.
the lowest
5.2 DETAILS OF SIGNXOR RESULTS
Figure presents the evolution of and in Algorithm| 2 for experiments related to ImageNet- 32 dataset. The left-sub figure in Figure demonstratss that r. the fraction of +1's in sgn(),) is approximately 0.5 across all iterations. Consequently, the sequence of signs in sgn((;) cannot be further compressed. Note that this observation is true for a. Since a sign compression, we conclude that the output of Scaled-sign cannot be further compressed using lossless compression scheme. The middle-sub figure in Figure F plots q, the fraction entries in 9μ such that sgu(ů, [i]) (g)( Note that remains close to 0.5 when = 0, and goes down as a increases. Recall that q is computed prior to adding distortion using a. This implies that the naturally present correlation between the two vectors sgn( and sgn(Ø,). i.e. temporal correlation, increases with a. The right-sub figure includes plots of p. the fraction of 1 in Note that as per Alg Algorithm 2 we have the relationship Ely) q(1 ax).
recovers the Scaled-
8

---

Under review as a conference paper at ICLR 2021
0.5
0.1
imm 0.2
d- 0.9
0=095
0.0
0.0
0.0
18
24
12 Epoch
12
18
24
Epach
Epoch
Figure 2: Evolution of r, and in Algorithm 2 for experiments conducted using the ImageNet32 dataset. Values collected when the master calls the encode function with arguments 9p and y Js- The peaks at epochs 10 and 20 are due to the drop in the learning rate at these epochs.
CONCLUSIONS AND FUTURE WORK
In this paper propose SignXOR, novel compression algorithm that exploits the temporal cor- relation consecutive gradients in SGD. The proposed algorithm builds off Scaled-sign (Bernstein) et al.) 2018, Karimireddy al., 2019) and dist-EF-SGID (Zheng al., 2019). The SignXOR algo- rithm combines amplitude quantization with the exploitation of temporal correlation. We accomplish this in two stages. The first employs Scaled-sign which quantizes gradient entries into two levels, and the second compresses by exploiting temporal correlation of quantized gradients. it interesting investigate how the second stage can be improved to accommodate more elaborate compression mechanisms beyond a two-level quantizer, such as QSGD (Alistarh et al. (017), Top-k (Stich et al., 2018 [in et al. 2018) and Spectral-ATOMO (Wang et al. 2018). Also, we conjecture that one must be able to compress better by jointly considering the two stages. This way, one can exploit in the second stage some of the information embedded in the gradient that may have been removed in the first stage. We leave these two tasks as future work.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. arXiv preprint arXiv:/044. 0,021, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd:
Communication-effiiinn sgd via gradient quantization and encoding. Advances in Neural Inf. Proc. Sys., pp. 1709-1720, 2017.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Avizzadenesheli, and Anima Anandkumar. signsgd: Compressed optimisation for non-convex problems. July 2018.
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprint 17X7iv:/00..00 08819, 2017.
Jacob Devlin, Ming- Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:8810008805, Oct 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Jiawei Jiang, Fangcheng Fu, Tong Yang, and Bin Cui. Sketchml: Accelerating distributed machine learning with data sketches. In Proc. Int. Conf. on Management of Data, pp. 1269-1284, May 2018.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. Int. Conf. Machine Learning, Jan 2019.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In Int. Conf. Learning Repre- sentations, Vancouver, May 2018
David JC MacKay. Information theory, inference and learning algorithms. Cambridge university press, 2003.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application data-parallel distributed training of speech dnns. In Conf. Int. Speech Comm. Association, Singapore, September 2014.
Alexander Sergeev and Mike Del Balso. Horovod: fast and easy distributed deep learning in Ten- sorFlow. arXiv preprint / 2018.
Steven W Smith et al. The scientist and engineer's guide digital signal processing. 1997.
Sebastian U Stich, Jean- Can-tBatiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Advances in Neural Inf. Proc. Sys., pp. 4447 2018.
V. Sze, M. Budagavi, and G.J. Sullivan. High Efficiency Video Coding (HEVC): Algorithms and Architectures. Springer International Publishing, 2014.
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication-effiiiee learning via atomic sparsification. In Advances in Neural Inf. Proc. Sys., pp. 9850-9861, 2018.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication efficient distributed optimization. In Advances in Neural Information Processing Systems, pp- 1399-1309, 2018.
Wei Wen, Cong Xu, Feng Yan, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication distributed deep learning. In Advances in neural information processing systems, pp. 1509-1519, 2017.
10

---

Under review as a conference paper at ICLR 2021
Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang. Error compensated quantized sgd and its applications to large-scale distributed optimization. Int. Conf. Machine Learning, June 2018.
Sergey Zagoruyko and Nikos Komodakis. 1rXiv:1605.07146 2016.
Wide
residual networks.
arXiv preprint
Shuai Zheng, Ziyue Huang, and James Kwok. Communication-effiienn distributed blockwise mo- mentum sgd with error-feedback. In Advances Neural Inf. Proc. Sys., pp. 11 11446- 1456, 2019.

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 PROOF OF THEOREM 1
Proof. We have
(x) - x = @ (2h 1) =|
| (2h 1) sgn(()) (2))))) xr
I a sg y @ (25 1) - (ag(())) + + [(a))( x||,
where the last step follows from the subadditivity of fo-norm. Squaring both sides and taking the expectation with respect to the randomness in C yields
(x) - 2 ==12| - E ||sgu| (y) (26 - 1) sgn()))l [[a((())) - xx|²
2B(a [gnaalsgng(1 ()) (26 1) sgn(x)]]]]l sgn(x) x1|
(2)
Next we bound each term in In the following we use the property ||>||| < | S vdll=II which shows that || is both lower and upper bounded by ||>||| within a constant factor.
For the second term in 2 we have
||>||| d
- -r| |2
la sgn(2) z112
sgn(x))
||-|||
|10|| sgu(x), xr ||
sg)(x)
|>>1
2 ||0|||
|sgn
(z)]
(sgn(x),23 x) ||=112
d2
which can be simplified and upper bounded as
||a (gn((r) - x1|2 ||ح| d
|
| d
| d
2 + ||:| = |
S
|| 2-
s||=||
for s = (1 2). The first equality is obtained by noting that [[s) = d and (sgn(r), = ||>|| The inequality is due to ||=||| S ||0:|]1- Note that agg((x)) is the Scaled-sign compressor, which 2 -aapproximate compressor since < 1.
For the first term in we have
E B|a"||sga (sgn()) @ (2b - 1) sgn(x))l=1 = a² D E ((sgn((y))))222 - -1) sgn sgn()())) (3)
= 4dga
< 4q0||=/12
where as defined in Algorithm Recall that is the fraction of elements x such that sgn(>[5]) sgn(y]))). The last step is obtained by noting that a²d || < || The sec- ond equality is obtained with the following reasoning. The d elements in summation can be split into three sets. In the first set we have d(1 - 4) elements satisfying sgn()())) # sgn(v(i)) which will cause bij] 0 and syn() (2b]] - 1) sgn(>())) 0. The rest of the dg elements satisfy sgn(>()]) = sgn(yi (y(]) and can be further divided into two sets. Out of these dg elements, in ex- pectation 1
1) sgn(xi>)) = 0. Such elements make up the second set. The third set consists of the rest the elements. Specifically, out of the dq. we have in expectation
fraction have b = again making sgn(vlj])
fraction with b 0. For the elements in this third set we have sgn( (on())))())))))))))))))))))))) (2b[j] - 1) * sgn(xi))) This gives us (sgn(yl))) 1) sgn(x(zl)) = 4 due to the sign mismatch.
12

---

Under review as a conference paper at ICLR 2021
For the last term in 2 we have
1/27
E[a||sgn(() @ (2b 1) sgn(2))l] aB Σ
(sgn (g(())))))2 -1 sgm (z(())
1/2
[((sgn sgn(<<)i))
V 44ga ||=||-
The first inequality is obtained by applying Jensen's inequality to the concave square root function, and the second inequality follows from B
Now we substitute the bounds for all terms in (2) to get
C[ - x x=1²]= < (4ga + 8 + 2v 4 & (V4a + 11)
In the last step remove the dependency
g it is function of æ. The inequality is obtained
by noting that y s 1 for all and y. Finally, letting (v4a + Vz)² 1 - 5 we find the conditions for a so that 0 < 8 S Note that å trivially satisfies
< for all a 2 The lower bound of
5 is satisfied 0 < - (v4a + /8)² which yields the bound < 1 (1 2 This concludes the proof.
A.2 PROOF OF THEOREM 2
We start with the proof of Theorem by Zheng et al. (2019) provided in their Appendix C. In the following analysis adhere the same notation m Theorem make the comparison casier.
The following equivalencies hold their and our notation: k. T) Ti- Ie wp = n,
& M-- Cg, and Ct, __ f
Proof. At the end of the first half of the proof on page 14 (Zheng et al. 2019), for p > 0, authors obtain
B[ & F(t.) - 1)t (1 Li7 + +
Lnjo²
1.2
M
E +
Et
2
2M
2p
M
Let us define \ 1/p and
By taking total expectation and then applying Lemma
2x
6 by Zheng et al. (2019) with μ = 0 we get
Lti: 2
LNão²
[[F(a++)] S B[F( - 7/e
c
E
|VF(2))]
2M
+ non-1112 8(1 -
82
82
Taking telescoping summation T iterations and rearranging the terms give
< F(zo) F. +
La -T- np
(XL3(1-0)G" (1
E
min T-1
[VF(2)))
2M
Σt- "/t (c- Lau
where we have asserted that [[F(i))] = F(oo) and that E[F(iT) 2 F.. Next we pick the step size schedule T) LVT and rearrange terms get
21 (F(zo) F.) +
22
ScA(1-8)G (1+ 8z)
E
min VF(20)1
M
5²
(4)
2VT -
2T VT
13

---

Under review as a conference paper at ICLR 2021
In comparison to 4
the analogous bound for SGD is
min [VF(==))) 2L(F(zo) F.) + M
E
(5)
2VT
For large T', the second term in vanishes at a faster rate than the first term. However, we cannot make a direct comparison between (5) and the first term 4 when c² 1. Setting an arbitrarily large value for À gives c² x 1, but we pay penalty with large cA in second term in 44) The solution make c asymptotically converge
by carefully choosing a that grows with T. This way + 1 and the first term in (4) becomes directly comparable to (5). We also want the cA in the second term of small enough so that it vanishes faster than the first term
Let À = T for some > O. We solve for by expanding cA and 2 in (4) We have =
T 2. We take the following approach to expand 2.2 For IR and positive integer r, from the negative binomial series we have
prtp-
(1-2)
sp.
p
p=0
For r = 2 and ||| < 1 we can write
(1 =)-² = 1 2% +32 + 4z + ... < 1 21+2)+
Since 2X
< 1, we can write
27
1 2
<I+x <1+x" 20
2X
Substituting the result back in and rearranging terms gives
2L(F(wg) - FF)) o²
E
min [V+())))
M
2VT -
+T OT 2L(F - F.)
2VT-1 -
T 1
8(1 -8)G2
1 82
(6)
2) 2T - T
82
(L(F(w)) - -F.) + o
M
TvT 1
+ T
+ T + 0 (
We would like to pick an that makes all terms in the last go zero in the same asymptotic rate. The third term requires < 1. For 0 < s < 1 the first and the third terms are the slowest to go gives = 1. One can substitute
to zero, therefore, they determine Setting -s 1 = in (6) to obtain
2L(F(Wg) - F.) + o²
min [V
2vT -1
2L(F(ug) -F.)+ + 8(1-8i02
(1 1
(
+
273/4- -1/4
where we have incorporated two O (+) into one. Changing the notation to our original yields the result in []. concluding the proof.
A.3 PERFORMANCE OF LZMA COMPRESSION
Figure 3 compares the compression ratio of LZMA algorithm with the theoretical lower bound. We generate a binary sequence of length 107 by sampling from the Berouuli distribution with proba- bility p. compress the sequence using LZMA, and plot the compression ratio versus p. The entropy H is a lower bound for the compression rate.
14

---

Under review as a conference paper at ICLR 2021
10-
LZMA
0.8
Entropy
0.0
0.7
Probubility (p)
Figure 3: Compression performance of the LZMA algorithm random binary sequence.
A.4 IMPACT OF BATCH SIZE ON TEMPORAL CORRELATION
The stochastic gradient workers compute is noisy. This is because workers use only a small mini- batch out of large dataset. We expect the gradient to be less noisy when the size of the mini- batch larger, and we expect less noisy gradients to be more (positively) correlated across time. First, note that as per Algorithm| []] O7 is the sum of the stochastic gradient and the compression error in the last iteration. Second, as noted in Algorithm 2 is the fraction of entries such that (g]( sg]( Although 93 and 9μ not stochastic gradients themselves, we expect their correlation (measured with q) to be impacted by the minibatch size. As is central to our pro- posed compression scheme, we explore numerically how changes with the minibatch size. Recall that we first observed y in the central sub-figure in Figure To this end we rerun the ImageNet32- SignXOR experiments described in Section 5.1 for different minibatch sizes, and for two values of o.. Jammmerizeeee the new results plotted versus the step. The first and second rows corre- spond experiments with 0 and a 0.7 respectively. Training is started with learning rate of 10-4, and the learning rate is multiplied iteratively by 0.1 at certain epochs when the loss starts to plateau. These epochs are multiples of 10, 15, 30 and 35 for the experiments with batch sizes 16, 32, 64, 128 respectively.
We observe that for large minibatch sizes the loss decreases faster. This is because the gradients are less noisy for large minibatches. We also observe that a larger minibatch result in larger q- The reason for this observation is that, as stochastic gradient gets less noisy, the stochastic gradients within 9. and 0R get more (positively) correlated (recall that 9; is the sum of the stochastic gradient and the compression error). This results in an increment of q, the fraction of components in 9, and Is that share the sign. We also observe in Figure 4 that this increment is minimal. For 0.7 only observe a maximum difference around 0.005 between the two g plots corresponding to batch sizes 16 and 128. In summary, q is less responsive to the changes of the batch size.
15

---

Under review as a conference paper at ICLR 2021
16
32
0.46
64
Loss
0.44
0.42
2
Step
Step
le5
0.21
16
32
0.20
64
Loss
0.19
0.18
0.17
Step
le5
Step
1c5
Figure 4: Assessing the impact of batch size 9 in SignXOR. The results from four different minibatch sizes are presented as indicated in the legends. The first and second rows correspond to experiments with and = 0.7 respectively.
SGD
9
Scaled-sign
SignXOR == 0.6
SignXOR 0.7
Test accuracy
of MA 7o9
SignXOR a= 0.8
7
Loss
0.4
6
5
4
3
4
8 Epoch
12
0
12
Epoch
Figure 5: This figure is same as the first two sub-figures in the third column Figure except that the æ-axis runs for larger number of epochs.
16


Reviews:
[{"review_id": "Wsz6baVzku4", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe idea is an interesting (even if a fairly simple one) and leads to a greater than 50% savings.\n\nHowever, 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? \n\n(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.)\n\nThis 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?)\n\n---\n\n### After Rebuttal\n\nIncreasing 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\n  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "SWhue6RMEjr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1.\tThe 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. \n2.\tPage 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.  \n3.\tAnother 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? \n4.\t“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. \n5.\tYou 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. \n6.\tI failed to understand the benefit of Generalized dist-EF-SGD algorithm in Section 3? What are the main differences telling me? \n7.\t“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]\n8.\tUniform 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]. \n9.\tYou 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. \n10.\tWhile ImageNet accuracy is similar to why test accuracies of the models on CIFAR-100 and ImageNet-32 are below 60%?\n11.\tIn 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. \n12.\t 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. \n\n\nMinor Comments:\n\n1.\tThese two sentences in my understanding are claiming the same thing? \n“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.”\n2.\t“Novel approaches such as federated learning…” Why is it novel? Unnecessary hyperbole is not part of technical writing. \n3.\t“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?\n4.\tPlease correct the typos and please write as it is done in a technical paper, not in a sci-fi novel. \n\n[1] Communication-Efficient Distributed SGD with Error-Feedback, Revisited, Tran Thi Phuong, Le Trieu Phong, 2020. \n[2] Dutta et al. AAAI 2020, On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learning", "extra_scores": {}, "extra_text": {}}, {"review_id": "5TDJGRCc2qz", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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:\n- 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)\n+ The compressor sends the sign of each gradient coordinate and a scale factor per 'block' of coordinates (like Zheng et al. 2019)\n+ The messages are compressed with lossless entropy encoding.\n+ 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)\n+ 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.\n\nI believe the main contributions of the paper are:\n- The introduction and evaluation of lossless compression on top of sign-based gradient compression\n- A theoretical improvement of the constants in the rates from (Zheng et al. 2019)\n- 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)\n\nI 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:\n- 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.\n- 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-suSt4gLtKa", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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:\n\n1. 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?\n\n2. Since alpha has a very small upper bound, it is hard to see any theoretical improvement over scaled sign.\n\n3. Theorem 4.2 does not show that one can achieve a linear speedup, i.e., O(1/\\sqrt{nT}) rate.\n\n4. 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.\n\n5. Can you show the final test accuracies on ImageNet achieved by each algorithm? It seems that scaled sign has slightly higher accuracy.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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