ErrorCompensatedX: error compensation for variance reduced algorithms
Authors: Hanlin Tang
Yao Li
Ji Liu
Ming Yan
Venue: NeurIPS 2021 Poster (2021)
Keywords: distributed learning
communication compression

Abstract: Communication cost is one major bottleneck for the scalability for distributed learning. One approach to reduce the communication cost is to compress the gradient during communication. However, directly compressing the gradient decelerates the convergence speed, and the resulting algorithm may diverge for biased compression. Recent work addressed this problem for stochastic gradient descent by adding back the compression error from the previous step. This idea was further extended to one class of variance reduced algorithms, where the variance of the stochastic gradient is reduced by taking a moving average over all history gradients. However, our analysis shows that just adding the previous step's compression error, as done in existing work, does not fully compensate the compression error. So, we propose ErrorCompensateX, which uses the compression error from the previous two steps. We show that ErrorCompensateX can achieve the same asymptotic convergence rate with the training without compression. Moreover, we  provide a unified theoretical analysis framework for this class of variance reduced algorithms, with or without error compensation. 

ErrorCompensatedX: error compensation for variance reduced algorithms
Hanlin Tang
Yao Li Department of Mathematics Michigan State University liyao6Emsu. edu
Department of Computer Science
University of Rochester
Mangh11994@gmaal com com
Ji Liu
Ming Yan Department of Computational Mathematics, Science and Technology: Department of Mathematics Michigan State University my myan@msu.. edu
Kuaishou Technology
ji. 1iu. uwisc@gmail.com
Abstract
Communication cost is one major bottleneck for the scalability for distributed learning. One approach to reduce the communication cost is to compress the gradient during communication. However, directly compressing the gradient decel- erates the convergence speed, and the resulting algorithm may diverge for biased compression. Recent work addressed this problem for stochastic gradient descent by adding back the compression error from the previous step. This idea was further extended to one class of variance reduced algorithms, where the variance of the stochastic gradient reduced by taking a moving average over all history gradients. However, our analysis shows that just adding the previous step's 's compression error, as done existing work, does not fully compensate the compression error. So, we propose ErrorCompensia
which uses the compression eπrr from the previous two steps. We show that ErrorCompensatedXX can achieve the same asymptotic convergence rate with the training without compression. Moreover, we provide unified theoretical analysis framework for this class of variance reduced algorithms, with without error compensation.
Introduction
Data compression reduces the communication volume and alleviates the communication overhead in distributed learning. E.g., Alistarr et al. (2017) compress the gradient being communicated using quantization and find that reducing half of the communication size does not degrade the convergence speed. However, the convergence speed would be slower we further reduce the communication size, and it requires the compression to be unbiased (Alistarh et al.] 2017 Tang et al., 2019). Alternatively, recent work (Stich et al., 2018a) Sa) shows that compression with error compensation, which adds back the compression error the next round of compression, using only 3% of the original communication volume does not degrade the convergence speed, and works for both biased and unbiased compression operators.
Despite the promising performance of error compensation on stochastic gradient descent (SGD), SGD admits slow convergence speed if the stochastic gradient has large variance. Variance reduction techniques, such as Momentum SGD (Zhang et al. 2015). ROOT-SGD (Li et al., 2020), STORM (Cutkosky & Mehta 2020), and IGT (Arnol et al. 2019). developed, and they admit increased convergence speeds either theoretically or empirically. We found that directly applying
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

error compensation to those variance reduced algorithms is not optimal, and their convergence speeds degrade. So a natural question arises: what the best compression method for variance reduced algorithms? In this paper, we answer this question and propose ErrorCompensateeXX, a general method for error compensation, and show that admits faster convergence speeds than previous error compensation methods. The contributions of this paper can be summarized as follows:
We propose novel error compensation algorithm for variance reduced algorithms and SGD. Our algorithm admits a faster convergence rate compared to previous methods (Zheng et al. 2019a Stich et al. 2018b) by fully compensating all error history.
We provide a general theoretical analysis framework to analyze error compensated algo- rithms. More specifically, we decompose the convergence rate into the sum of two terms
T
vf(x))]
2 Runcompressed + Re:
where Runcompressed depends only on the convergence rate of the original algorithm without compression and R2 is depends only on the magnitude of the compression error It means that we can easily attain the convergence rate for any compressed algorithm in the form of To the best of our knowledge, this is the first general result for error compensation.
2 Related Works
Variance Reduced Optimization. When the variance of the stochastic gradient is large, training using SGD becomes unstable, and it usually renders a slow convergence speed. Many studies try to reduce the variance of the stochastic gradient. For example, Momentum SGD (Zhang et al., 2015) takes moving average over all previous stochastic gradients. However, its expected momentum does not equal to the full gradient. Recent studies take one step further by applying bias correction the momentum. One approach is to compute the gradient at æ, and Ø;-1 using the same data sample & (Huang et al. 2020; Yuan et al. 2020 Li et al.) 2020), while another direction is to compute the gradient at the extrapolated point of æ, and - (Amold et al. 2019 Cutkosky & Mehta 2020). When the number of data samples is finite, some approaches compute the full gradient once in a while memorize the latest stochastic gradient of each data sample and use its average to approximate the full gradient; examples include SVRG (Johnson & Zhang 2013), SAGA (Defazio et al. 20144) and SARAH (Nguyen et al. 2017).
Communication Efficient Optimization. One major bottleneck of distributed learning is the communication cost. Methods, such as data compression. decentralized training, local SGD, and federated learning, were proposed to reduce the communication cost. Data compression is an important approach that can be combined with other approaches. and it critical for communication networks with limited bandwidth. It was firstly proposed in [Seide et al.] (2014), where authors proposed 1-bit SGD, which uses one bit to represent each element the gradient but still achieves almost the same convergence speed with the uncompressed one. In (Stich et al. (2018b), authors proposed general algorithm for error compensated compression MEM-SGD with theoretical analysis. They found that MEM-SGD has the same asymptotic convergence rate with uncompressed SGD, and more importantly, robust to both biased and unbiased compression operators. This method can be combined with decentralized training (Vogels et al.) 2020), local SGD (Xie et al.) 2020), and accelerated algorithms (Gorbunov et al., (2020). Due to its promising efficiency, error compensation has been applied into many related area (Zheng et al.
2019b Phuong & Phong 2020 Yu et al. 2019 Shi et al. 2019 [vkin et al. 2019; Sun et al. 2019 Basu et al. 2019: Vogels et al. 2019) to reduce the communication cost.
Another direction to minimize the side-effect of compression is to compress the difference between the current gradient and momentum. Previous work (Mishchenko et al.) 2019 Liu et al., (020) proved that this strategy achieves linear convergence when the loss function is strongly convex. However, the linear convergence requires either the full deterministic gradient, or using SVRG (Horváth et al. 2019) to control the variance when for finite sum the loss function. Therefore how they perform with general variance reduced stochastic algorithms is still open problem.

---

3
Algorithm Design
3.1
Background
The underlying problem we consider can be posed as the following distributed optimization problem:
1 ni Σ Betn (xx;(())
min f(x)
(m)
where is the number of workers, D; is the local data distribution for worker (in other words, do not assume that all nodes can access the same data set), and F (()) is the local loss function of model æ given data (()) for worker i.
One widely used method for solving ① is SGD, which updates the model using 2++1 2t - '9t, where Vy is the model at the t-th iteration, y is the learning rate and g: is the averaged stochastic gradients. However, SGD suffers from the problem of large stochastic gradient variance, and many variance reduced algorithms are developed. our paper, we focus on the following variance reduced algorithms: Momentum SGD, STROM, ROOT-SGI"] and IGT, because they all construct the estimator using a moving average of previous stochastic gradients, which can be summarized as
V = V:-1
0 + and (z);; Le+1 = = 7/8
where is the gradient estimator, sf (x/; ) is variable that depends on the history models æ, (for all 8 S f) and data sample &s, and a; is a scalar. Notice that & (a and a; are designed differently for different algorithms. We list the different choices of those parameters for each algorithm in Table 1
O22
// (xcri Et)
SGD
1
V V (
Momentum SGD
Q
V FF(x;
STORM
a D1
(V (e) (1 as V (((
ROOT-SGD
1/t
(Zxe (VF( (1 a. F 11)1;
IGT a
VF
Øt + 1-a1 (xt - - 1):1);
Table 1: Different choices of (a,, a (xtg Er)) for each variance reduced algorithm.
Recent work suggests that instead of compressing the gradient directly (Alistarh al. 2017). using error compensation (Stich et al.] 2018b) could potentially improve the convergence speed. The idea of error compensation quite straightforward: adding back the compression error from the previous step to compensate the side-effect of compression. Denoting Cu as the compressing operator, the updating rule of this method follows
#+++ 2t 7Cu + 8,-1), 5, = + 8, Ca [gt + 8,-1),
where ò is the compression error at the t-th step. Moreover, recent works (Chen al., 2020 Wu eet al., 2018) find that adding low-pass filter to the history compression error could be hel helpful for stabilizing the training and further improving the training speed. Their updating rule can be summarized
-11 - 3)e,-1+ + 68,-1, 01+1 = = CC (g: + te],
d; g: + e, Cw [gt + ez].
where 3 is hyper-parameter the low-pass filter.
Notice that even eтror compensated compression has been proved to be very powerful for accelerating the compressed training, was only studied for SGD, which is special case of (2) when a. For the case where a₁ 1, previous work (Zheng et al. [2019a] Zhao et al., 2019 Wang et al., 2020
adapted the same idea from Stich et al. (2018b), which directly compresses the gradient estimator
'STORM (for non-convex loss function) and ROOT-SGD (strongly-convex loss function) use the same updating rule except a, = 1/T3 STORM and a; = 1/T for ROOT-SGD. Here denotes the randomness of the compression operator.

---

Vt with the compression error from the previous step being compensated (we refer this method as Single Compensation). However, we find that when a, very small (O (1/T) for ROOT-SGD and
O ( for STORM, where T is the total training iterations), Single Compensation would be much slower than the uncompressed one, as shown in Figure
10"
STORM
10
M7 sensales)
TORM drrorGannssnne
10
10
norm
Grad nor
10-1
10
10a
2
0
10
15
5 10 15
Steps
x10
x10
(a)
(b)
Figure 1: Convergence speed comparison on linear regression for STORM and IGT with different compression techniques. The x-axis is the training step number, and the y-axis is the norm of the full gradient. The batch size equals a, 1/t, and ct al. (2019). Single Compensation means only compensate the compression error from the last step, and we can that it admits much slower convergence speed than the uncompressed one when og is very small. However, our proposed ErrorCompensatedxX has a similar convergence rate as the uncompressed one.
1-bit compression described in Tang
3.2 Proposed ErrorCompensatedXX
In this section, we provide the intuition behind our proposed method ErrorCompensatedX. For simplicity, we consider the general update in (2) with ar = Let 1- 0, then the uncompressed algorithm has the update
TT ΣΣ a(1 a)) (x,; 1=
Note a (x.; {.) is transferred from worker nodes to the server (here we aggregate the data from all workers). If the compression is applied on a (x. Es), then we have the update
a(1 a) (d(((EE)))) 5.)
ET =D0
7
1=0 0=0
=0o Σ
a(1 - a) + Σ (1- a) -)-- Σ
Note that the sequence {x.)T is different from that of the uncompressed one. Here d, is the compression error, and the compressed data af <xxx; - 8, transferred to the server. With error compensation and additional 8_1 O. we have
OT 20 7 Σ Σ
a(1 (d + 8.-1 - 5.) -.))
t= a=0
T-1
=0o
(w)
Σ ==0
a(1 -11-5 55
t=0 ==0
Here ò, is the compression error that occurs while compressing e (m.; {.) + 8, When a the last term disappears, and the standard SGD case has been analyzed in Tang et al. 2019); Stich et al.

---

(018a). In this paper. we focus on the case where the last term does not disappear, i.e., a E (0, 1).
Given ò
6-2 O. when using ErrorComennateedX, we have
Σ
(1-a) - 8 8.)
TT 30
1= 5=0
T-1
Σ
all-a) + Σ
=00
Notice that the discussion above, we make an implicit assumption that there is only one worker in the training. For the of multiple workers, adapt the strategy proposed by [Tag al.) (2019), which uses a "arameter-Serve communication prototype and applies error compensation for both rounds of worker-server communication.
For changing at,, the updating rule of ErrorCompensaeeXX with a low-pass filter follows
(t-1 (2 a1)d;-1 0t-2 21-2111 (1-0r)01-2) A, ===d == Ee) + te,
(1 -111-))e-11+ +
aq
a2
2t -11- -1
2141 = 21 -/00
Here E; is the compression error being passed after the low-pass filter and 3 is the hyper-parameter of the low-pass filter. Our analysis indicates that for general case with 0 Or 1, using just the compression error from the last step is not good enough, especially when O₁ is very small. In this case, ErrorCompensatedXX admits much faster convergence speed than Single Compensation and could achieve the same asymptotic speed with the uncompressed onc. We assume a Parameter-Servee communication prototype for the parallel implementation of FrrorCComensateeXX, and the detailed algorithm description can be find in Algorithm
Algorithm ErrorCompensateuX for general of (x; {)
1: Input: Initialize Øg. learning rate 7, loss-pass filter parameter B, initial error on workers 5/ 0, initial error on the server 8-1 d, 0, scheduler of {a, "0=)""--- and number
of total iterations T. The initial gradient estimator vo V F (wo: <!") with total batch-size Bo.
initial compression error buffer e 0 and eo O.
2: for = 1,2,-.. ... . do
3: On worker i:
e -(1 -))
4: Pass the worker compression error into the low-pass filter:
B
-- (2 a2)0 --_ a.)
Compute the error-compensated local gradient estimator: A = of (zz: (z): + +el
5:
Compress A (o) into C.
[ and update the local worker error (6) + A -Cw [1]0]
6:
Send C, A to the parameter server.
7:
8:
On parameter server:
9:
Pass the server compression error into the low-pass filter: e = (1 - 1-1-11
B
0--1 (2 a 0x-2
10:
Average all gradient estimator received from workers: A, = 1 Σ Cu
A
+ te
Compress A, into C. [A,] and update the server error 8, A, C. A
12:
Send C., [A.] to workers
13:
On worker it
14:
Update the gradient estimator v, (1 0x)0.11 + CrCo [A.). Update the model x++1 = 2, Yu-
15:
16: end for
17: Output: Ør
5

---

Throughout this paper and its supplementary document, we let f = ming f()) be the optimal objective value. addition, we let || || denote the l norm of vectors, and S means "less than or equal to up to constant factor".
4 Theoretical Analysis
In this section, we first summarize the general updating rule for each algorithm w/o error compen- sation. Then we will present a general theorem that essential for getting the convergence rate of each algorithm. At last, we will see that by using ErrorCompensatedX, we could achieve the same asymptotic convergence rate with training without communication compression using both biased and unbiased compression.
All error compensation algorithms mentioned so far can be summarized into the formulation of
e, =(1 8) 3 (1 -0,,0-1--2,,0-)) 02,
0, - (1-00) + a ( Ee) - 62 + 72, 1e+1 = 22 --0--
(5)
Here (1-ar)us 0-) + ar ( originates from the original uncompressed algorithm. Other terms that depends the compression error 8, indicates the influence of compression (see our supplementary material for more details about the parameter setting for different compression algorithms.)
4.1 Convergence Rate of General Algorithms
In this section, we decompose the convergence rate of ErrorCompensatedX into two parts: Runcompressed that only depends on the original algorithm without compression, and R. which only depends on the way of error compensation.
Instead of investigating x; directly, we introduce an auxiliary sequence { which defined as
Ur (1 at u-) + a,d (ari a; = f.-1 Yu
and set dtg Mig U4g By for initialization. Below properties and is very helpful for the analysis of the convergence rate for {x,}.
going to that (æ,) admits some nice
For Lr, there seems to be no compression error, but still compute the gradient estimator using æ instead it directly. Therefore we also define
ûs = (xo: {o) = (æo: Eo), û, = =1 -1- (1-a:) + (Etri Et).
In this case, in the view of [ it basically updates the model following
úr = (1 az ú + aq of (#ee Et), o = - 7ú;
( út)
compression bins
Therefore } essentially using the same uncompressed gradient estimator sf ( Ee) for con- structing the gradient estimator ún except that when it updates the model, it will use ú, plus compression bias term 7(1, it).
Now we present the key theorem that concludes the convergence rate of any algorithm (for non-convex loss function) that updates the model according (4) and (5). Before we introduce the final theorem, we first make some commonly used assumptions:
Assumption 1. We assume f > -o and make the following assumptions:
1. Lipsehitzian gradient: f(-) and F(::E) are assumed to be with L-smooth, which means
[[VF(z;;) - FF(y: SLF || vll. Va, y. E,
- x vll.
Vx, y,
2. Bounded variance: The variance of the stochastic gradient bounded
Eg VV((;)(0) f(x))| <o² Vx.i.

---

Theorem 1. For algorithus that follow the updating rule 44 and (5)
under Assumption we have
B[))(=)) = (x0) - -J²)
T-1
641 of
+
21
T
7 +
A
TB| Balaa $2.1?
T
1=
1=
where A is defined as with in defined in and L is the Lipschitz constant of a/ ();E), i.e.
A A -uel?- -(1 1-LL))E((ull I8 f
[x; (y;; E)_l S /ha yا1 y.
Here A,, which depends only on the original uncompressed algorithm, indicates the bias of con- structing the gradient estimator using uncompressed </ Ex), hence 16([(=))-f") >7
- Er A is
usually the convergence rate of the original algorithm without compression.
In order to get a clear vision about the influence the compression error under different error compensation methods, the theorem below we are going to give an upper bound of Σ Ella lel for different error compensation methods.
Assumption 2. The magnitude of the compression error are assumed to be bounded by a constant e:
En 10.000
En 10:00
2. Vt,i
Theorem 2. For algorithms that follow the updating rule 4 and
5
under Assumption 2 setting
8 1, The = 1/, 72, = f/2, CL = C₁ and 022t = C22 we have
Dt 21
1/1
(1 (1 a) o+) 83 12 Σ
(1- (1 -0) 8.
8=0
=0
C222
(1 (1 a)* -)) 8..
==0
More specifically, we have
Σt= Bllaa: d;. 12 < 22122
No Compensation:
at;
Single Compensation: ET TE Fr - 1 < 722
ErrorCompensatedx: E B|| - 1 < 022
4.2
Convergence Rate for Different Gradient Estimators
In this section, we apply Theorem to get the specific convergence rate of EnrorCompensatedX for Momentum SGD, STORM, and IGT.
4.2.1 SGD and Momentum SGD
Since SGD is a special case of Momentum SGD when setting = 1, the following theorem includes both SGD and Momentum SGD.
Theorem 3. Setting sf (x:; {t) VF(wE if I 12. under Assumptions and
2 have
T-1 17yL
A. S
3n
t=
This leads to the corollary below:

---

Corollary 4. For ErrorCompensatedd., under Assumptions 7 and 2 To
setting ai (0,
(21;; = (F Ee) and 7 = min
we have
12L
a
[
+
Vn
(cT)
af
The leading term admits the order of O (1/VnT) which is the same as uncompressed training.
4.2.2 STOchastic Recursive Momentum (STORM)
Theorem 5. Setting sf {x)
1.
(V F E,) - aallaaa)F(m---ee6 if S at and 2
8(L" +2, under Assumptions
and
have
T-1
200 TT
A S
naBo
t=0
This leads us to the corollary below:
Corollary 6. For
ErrorCompensttex, under Assumptions
and
setting
min 4L T ETT
O2 81.y22
Bo
c and
of (
n
(VF(at; Ee) - (1 ai v
we have
T-1
(((x)))
+
nT
n77
T
The leading term admits the order of O (1/(TT)&) which is the same as uncompressed training
Yuan et al. 2020).
4.2.3 Implicit Gradient Transport (IGT)
For IGT, we need to make some extra assumptions (as listed below) for theoretical analysis. Assumption 3. The Hessian f-) is p-Lipschitz continuous, i.e., for every x, y Rd
f(x) v f(y)l S p| yll- Yx, y.
The magnitude of the stochastic gradient is upper bounded, i.e.. F( {) - (y: < A Vx, y.
Now we are ready to present the result of IGT: Theorem 7. Setting st (x):t))
VF
Ct 1-a1 (x, a1-1):E1). if s 2r. under Assump- ar
tions] 7 and we have
T-1 Σ
2T
d²
PAT
A
anBo
at
t=
This leads to the corollary below:
Corollary For ErvorCompensatedx, under Assumptions L
and
by setting y =
min 2L
n² 0077))
(.77
a (== and Bu = we have
T-1
2
1 T
Σ
B [
1.74
TT
The leading term admits the order of 0(1 Q(1((T)))) which is even worse than that of Momentum SGD. A sharper rate of IGT for general non-convex loss function is still open problem.

---

5 Numerical Experiments
In this section, we train ResNet-50 (He et al. 2016) on CIFAR1O, which consists of 50000 training images and 10000 testing images, each has 10 labels. We run the experiments on eight workers, each having a 1080Ti GPU. The batch size on each worker 16 and the total batch size is 128. For each choice of s/ (ari Er), we evaluate four implementations: 1) Original algorithm without compression. 2) No compensation, which compresses the data directly without the previous information. 3) Single compensation, which compresses the gradient estimator with compression error from the last step added. 4) Corpeeompens..ee..
We use the 1-bit compression in Tang et al. (2019), which leads to an overall 96% of communication volume reduction. We find that for both STORM and IGT, setting a; - T-cot- where co is constant and f is the training step count, would make the training faster. We grid search the best learning rate from {0.5. 0.1, 0.001} and cy from 1, 0.05, 0.001), and find that the best learning rate is 0.01 with co = 0.05 for both original STORM and IGT. So we use this configuration for the other three implementations. For Momentum, usually we will not set a to be too small, therefore we only set a, = 0.1, and the best learning rate is 0.1 after the same grid search. We set 3 0.3 for the low-pass filter in all cases.
Nomentum 5c3 (Singla Compenabbor) Momerbum Fimoaanmeaatt
Nomertum 503
10-
ST DRM STORN iSigla Companation) STORN (Ftrrrappeemmn
20"
KST
FST rggg Compenacion)
Training Lows
Training Loos
1ST (erattmmeeeeee
120
40
302
Epochs
Epochs
Epochs
(a) Training loss (Momentum SGD)
(b) Training loss (STORM)
(c) Training loss (IGT)
:00
100
100
Texting Aucuracy
8
Testing Arcuracy
50
8
8
a 8
80
3
Momeemum 563
Momaenuum SCD (Sigge Concersalior Mumemmm (imorooppeovvs)
STOWN riigle Conseradionn
STORM
70
ICT Sagg Co Comsmattion
S78SN (frnrrapeee
IGT 3f pemeermmp 1opes)
6)
40
100
20
50
100
20
197
Epochs
Epochs
(d) Testing accuracy (Momentum SGD)
(e) Testing accuracy (STORM)
(f) Testing accuracy (IGT)
Figure 2: Epoch-wise convergence comparison ResNet-50 for Momenum SGD (left column), STORM (middle column), and IGT (right column) with different communication implementations. We do not include the result of no compensation because it diverges after a few steps of training.
As illustrated in Figure 2 for both STORM and IGT, ErrorCompensatedx achieves almost the same convergence speed with the original algorithm, while Single Compensation fails to achieve this. We find that with increasing magnitude of co. this gap of convergence speed would increase, which further validate our claim that ErrorCompensatede Momentum SGD, all the three implementations (except compression without error compensation) achieves similar convergence speed. This is because a, 0.1 is comparably large.
is more essential when a gets small. For
6 Conclusion and Remarks
In this paper, we address an important problem for communication efficient distributed training: how to fully compensate the compression error for variance reduced optimization algorithms. In our paper, we consider a more general class of optimization algorithms (including SGD and Momentum SGD), and we propose a novel method: ErrorCompensatedX,, which utilize the compression error from the last two steps, in order to fully compensate the history compression error while previous method fails to do. From the theoretical perspective, we provide unified theoretical analysis framework that gives intuitive evaluation for the side-effect of the compression, and shows that

---

LtrorCompensateee admits the same asymptotic convergence rate with each of the original algorithm. Numerical experiments are implemented show EroorCoppenstedX's convergence and its better performance comparing to other implementations.
Acknowledgments
Yao Li and Ming Yan are partially supported by the NSF grant DMS-2012439 and a Facebook Faculty Research Award.
References
Alistarh, D., Grubic, D., Li, J., Tomioka, R., & Vojnovic, M. (2017). Qsgd: Communication-efficentt sgd via gradient quantization and encoding. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan. & R. Garnett (Eds.), Advances in Neural Information Processing Systems, volume 30 (pp. 1709-1720).: Curran Associates, Inc.
Arnold, S. M. R., Manzagol, P.-A., Babanezhad, R., Mitliagkas, I,, Roux, N. L. (2019). Reducing the variance in online optimization by transporting past gradients.
Basu, D., Data, D., Karakus, C., & Diggavi, S. (2019). Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Bue Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 14695 14796). Curran Associates, Inc.
Chen, C.-Y., Ni, J., Lu, S., Cui, X., Chen, P.-Y.. Sun, X., Wang, N., Venkataramani, S., Srinivasan, V. V., Zhang, W., & Gopalakrishnan, K. (2020). Scalecom: Scalable sparsified gradient compression for communication--fficiee. distributed training. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, & H. Lin (Eds.), Advances in Neural Information Processing Systems, volume 33 (pp. 13551- 13563): Curran Associates, Inc.
Cutkosky, A. Mchta, H. (2020). Momentum improves normalized SGD. In D. III & A. Singh (Eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research (pp. :268)) PMLR.
Defazio, A., Bach, F., & Lacoste-Julient S. (2014). Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems, volume 27 (pp. 1646-1654). Curran Associates, Inc.
Gorbunov, E., Kovalev, D., Makarenko, D., & Richtárik, P. (2020). Linearly converging error compensated sgd.
He, K., Zhang, X., Ren, S., & Sun, (2016). Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (pp. 770-778).
Horváth, S., Kovalev, D., Mishchenko, K., Stich, S., & Richtárik, P. (2019). Stochastic distributed learning with gradient quantization and variance reduction.
Huang. F., Tao, L.. & Chen, (2020). Accelerated stochastic gradient-free and projection-free methods. In H. D. III & A. Singh (Eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research (pp. 4530).: PMLR.
Ivkin, N., Rothchild, D., Ullah, E., braverman, V., Stoica, I., & Arora, R. (2019), Communication efficient distributed sgd with sketching. In H. Wallach, Larochelle, A. Beygelzimer, F. d Alché- Buc, F. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 13144 13154), Curran Associates, Inc.
Johnson, R. Zhang, T. (2013). Accelerating stochastic gradient descent using predictive variance reduction. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, & K. Q. Weinberger (Eds.), Advances Neural Information Processing Systems, volume 26 (pp. 315-323): Curran Associates, Inc.
10

---

Li, J., Mou, W., Wainwright, M. J., & Jordan, M. I. (2020). Root-sgd: Sharp nonasymptoties and asymptotic efficiency in a single algorithm.
Liu, x., Li, Y., Tang. J., & Yan, M. (2020). A double residual compression algorithm for efficient distributed learning. In S. Chiappa & R. Calandra (Eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research (pp. 133-143).: PMLR.
Mishchenko, K., Gorbunov, E., Takac, M., & Richtarik, P. (2019). Distributed learning with compressed gradient differences.
Nguyen, L. M., Liu, J.. Scheinberg, K., & Takac, M. (2017). Sarah: A novel method for machine learning problems using stochastic recursive gradient. In D. Precup & Y. W. Teh (Eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research (pp. 2613-2621). International Convention Centre, Sydney, Australia: PMLR.
Phuong, T. T. & Phong, L. T. (2020). Distributed sgd with flexible gradient compression. IEEE Access, 8, 64707-64717.
Seide, F,, Fu, H., Droppo. J., Li, G., & Yu, D. (2014). 1-bit stochastic gradient descent and application to parallel distributed training speech dnns. Interspeech 2014.
Shi, S., Wang, Q., Zhao, K., Tang, Z., Wang, Y., Huang, X., & Chu, X. (2019). A distributed synchronous sgd algorithm with global top-k sparsification for low bandwidth networks. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS) (pp. 2238-2247).
Stich, S. U., Cordonnier, J.-B., & Jaggi, M. (2018a). Sparsified sgd with memory. In S. Bengio, H.
Wallach, H. Larochelle, K. Grauman, N. ResaaBiancchi, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 31 (pp. 4447 (458). Curran Associates, Inc.
Stich, S. U., Cordonnier, J.-B., & Jaggi, M. (2018b). Sparsified sgd with memory. In Advances in Neural Information Processing Systems (pp. 4447-4458).
Sun, J., Chen, T., Giannakis, G., & Yang, Z. (2019). Communication-effiiene. distributed learning via lazily aggregated quantized gradients. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché- Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 3370-3380). Curran Associates, Inc.
Tang, H., Yu, C., Lian, X., Zhang, T., & Liu, J. (2019). Doublesqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression. In International Conference on Machine Learning (pp. 6155 6165).: PMLR.
Vogels, T., Karimireddy, S. P., & Jaggi, M. (2019). Powersgd: Practical low-rank gradient compression for distributed optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buce E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 14259- 14268).. Curran Associates, Inc.
Vogels, T., Karimireddy, P., & Jaggi, M. (2020). Powergossip: Practical low-rank communication compression in decentralized deep learning.
Wang, J., Tantia, V., Ballas, N., & Rabbat, M. (2020). Slowmo: distributed sgd with slow momentum. In International Conference on Learning Representations.
Improving communication-cfficinnt
Wu, J., Huang, W. Huang, J., & Zhang, T. (2018). Error compensated quantized SGD and its applications to large- scale distributed optimization. CoRR, abs/1886.0800.
Xie, C., Zheng, S., Koyejo, O., Gupta, I., Li, M., & Lin, H. (2020). Cser: Communication- sgd with error reset.
Yu, Y., Wu, J., Huang, L. (2019). Double quantization for communication-efficennt distributed optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, & R. Garnett (Fds.),, Advances Neural Information Processing Systems (pp. 1438-44499 Curran Associates, Inc.

---

Yuan, H., Lian, X., Liu. J., & Zhou, Y. (2020). Stochastic recursive momentum for policy gradient methods.
Zhang, S., Choromanska, A., & LeCun, Y. (2015). Deep learning with elastic averaging sgd.
Zhao, S.-Y., Gao, H., Li, W.-J (2019). On the convergence of memory-baset distributed sgd.
Zheng, S., Huang, Z., & Kwok, J. (2019a). Commanication-efficenn distributed blockwise momentum sgd with error-feedhack. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buu Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems, volume 32 (pp. 1 11450- 11460).: Curran Associates, Inc.
Zheng. S., Huang, Z., & Kwok, J. (2019b). Communication- effficiennneiiinnnteeeee distributed blockwise momentum sgd with ferob.kee In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buee E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 11450-11460). Curran Associates, Inc.
12


Reviews:
[{"review_id": "zqpEhr2ebo", "reviewer": "Reviewer_dVax", "summary": "The paper proposed ErrorCompensatedX, that uses compression error from the previous two steps for variance reduced algorithms and SGD. The paper provided a theoretical analysis framework to analyze error compensated algorithms, and shows that ErrorCompensatedX admits the same asymptotic convergence rate for SGD, Momentum SGD, STORM, and IGT. Numerical experiments are performed with ResNet50 on CIFAR10.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "As stated in the paper most error compensation algorithms use compression error from the previous one step. The paper proposed an error compensation algorithm using compression error from the previous two steps as in equation (3) for variance reduced algorithms. The Algorithm 1 assumes a Parameter-Server communication protocol following Tang et al. and the update rule utilizes the low-pass filter by Chen et al. properly cited.\n\nThrough theoretical analysis the paper presents convergence rate for momentum SGD, STORM, IGT, same as the original algorithm. Numerical results are not very sound to me, with only experiments of ResNet50 on CIFAR10. Do ErrorCompensationX outperform Single Compensation with other datasets like ImageNet or other models or other compression method?\n\nThe paper is clearly written and well organized.\n\nCommunication is a bottleneck for scalability of distributed learning. It is important to properly address it and extend beyond SGD.\n\n**Update**:\nThanks for the authors' response to the reviews. I didn't see full answer to my questions. Hopefully they would be addressed in the revised version.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper addressed the limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "al55runLm4", "reviewer": "Reviewer_UoCD", "summary": "The paper presents a modification to the error feedback mechanism for compression of communication in distributed optimization to handle momentum-like terms. The paper presents theoretical analyses of existing momentum-like algorithms coupled with compression based on their modifications and experimental results confirming their results.\n", "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": "Improvements to compressed distributed optimization are likely to be of interest to the community. The submission identifies a problem, the compression of momentum based methods, that is likely to impact practical implementations of distributed training and seems to not have been adressed in the literature so far. \n\nHowever, the current submission suffers from major issues in its treatment of previous work and in the clarity of the assumptions and theoretical results. I cannot recommend acceptance in its current state. My main issues are as follow, with more detailled below;\n- The focus and motivation on \"variance-reduced methods\" seems inappropriate when considering (Polyak or Nesterov) momentum, and there are bibliographic issues throughout the paper.\n- The discussion of related work on variance-reduced compressed distributed optimization is lacking, making the comparative statements of the contributions of the paper inappropriate\n- The theoretical results do not match the results of the original non-compressed algorithms and rely on strong assumptions that previous work did not require.   \n\t- For example, STORM requires a growing batch size $\\propto T^{1/3}$ (Corollary 6), which defeat the purpose of its variance-reduced gradient estimator.\n\t- The assumption (2) that the compression error is uniformly bounded by a constant,  $\\mathbb{E}_\\omega[\\Vert \\Delta_t - C_\\omega[\\Delta_t]\\Vert^2] \\leq \\frac{1}{2}\\epsilon^2$, is unrealistic. It does not hold for the 1-bit compression considered in this work or  other common compression schemes (top-K, random-K). The typical assumption, used in previous, is that the error is multiplicative ($\\mathbb{E}_\\omega[\\Vert \\Delta_t - C_\\omega[\\Delta_t]\\Vert^2] \\leq c \\Vert\\Delta_t\\Vert^2$ for some $c < 1$, see e.g. Definition 2.1 in Stich et al. (2018) or Eq. (8) in Gorbunov et al. (2020))\n\n- The algorithms are analyzed as estimators with some specified error in finite time (where the step-size is constant and depends on the number of iterations) rather than optimization algorithms (with a decreasing step-size) where the convergence rate implies that running the algorithm for longer improves the guarantee.\n\n---\n\n### Detailled comments\n\n\n**Related work and bibliographic issues:**\n\nThe related work and emphasis on variance reduction for the motivation of the work is confusing, as it groups methods from very different settings. The inclusion of (Polyak or Nesterov) momentum is especially confusing at those methods are designed for acceleration in the deterministic setting, not variance reduction, which is bound to confuse readers. It seems that, instead of variance reduction, the submission could be motivated in terms of momentum, with variance-reduced methods using momentum as an application.\n\nBut given the emphasis on variance reduction, the introduction should take greater care to distinguish between algorithms that are typically thought of as variance reduction (SAGA, SVRG and their more recent variants) and the more recent momentum-based variants of ROOT-SGD and STORM. Variants based on SVRG have already been adapted to the compressed setting, starting from Alistarh et al. (2017), and subsequent work in this area should be acknowledged more directly and compared against in the discussion of the proposed method and its results. \n\nThe motivation for the proposed method could be made stronger by discussing the benefits of the STORM/ROOT-SGD over SAG or SVRG-type methods. Given that the setting is distributed optimization, where each machine only holds a subset of the data, periodic computation of the full-gradient on each machine does not seem to be a major issue.\n\nAdditionally, the claimed contribution that \"Our algorithm admits a faster convergence rate compared to previous methods (Zheng et al., 2019a; Stich et al., 2018b) by fully compensating all error history.\" (l36-38, p2) needs to be qualified to a specific setting and the required assumptions, and include a discussion of existing variance-reduced methods.\n\nI would suggest that for future submissions the authors proofread the bibliography and make sure that the citations in text point to the correct paper, as I found the following mistakes\n- The submission cites Gorbunov et al. (2020, \"Linearly Converging Error Compensated SGD\") as an example of accelerated algorithm (l69, p2), but this paper does not use acceleration. There are works on acceleratiion in this setting, for example that of Qian et al. (2020) and Li et al. (2020).\n- I assume that the citation for STORM, Cutkosky and Mehta (2020), \"Momentum Improves Normalized SGD\", was meant to be Cutkosky and Orabona (2019)?\n- The citation for Momentum SGD, Zhang et al. (2015), \"Deep learning with elastic averaging SGD\", EAMSGD (Elastic Avg. Momentum SGD) does not discuss variance-reduction as a benefit and is instead based on Nesterov acceleration, although the description of Momentum SGD in the current submission (e.g. in Table 1) is that of Heavy Ball/Polyak momentum.\n- There are also minor issues with some bibliography entries that \n\t- are duplicated (Stich et al. 2018a and 2018b, Zheng et al. 2019a and 2019b)\n\t- do not contain publication venue (Arnold et al. 2019, Gorbunov et al. 2020, Horváth et al. 2019, Mischenko et al. 2019, Vogels et al. 2020, Yuan et al. 2020, Zhang et al.  2015, Zhao et al. 2019)\n\t- cite the arXiv version instead of the published work (Wu et al. 2018 at ICML)\n\t\n**Clarity of the contributions:**\n\nAt a high level, the presentation for the \"double\" compensation in Section 3.2 is unclear. A presentation for the first (few) iterations, rather than the entire run ($t=0,\\ldots,T$) and highlighting the failure of \"single\" compensation might flow better. But If I understood the method correctly, the main issue it seems to address is as follow: for methods based on a moving average momentum-term (rather than variance reduction), compressing and applying error feedback on the gradient is insufficient as it does not correct the momentum term appropriately. Given this, it is unclear to me why the method is cast as a as \"double compensation\" depending on the previous two timesteps, as in Eq. (3), rather than simply applying error feedback on the momentum term. For example,  \n\n> $v_t = (1-\\alpha) v_{t-1} + \\alpha A(x_t)$  \n> sending $C_{\\omega_t}(v_t + e_t)$  \n> $e_{t+1} = v_t - C_{\\omega_t}(v_t + e_t)$  \n\nIf this more naïve approach does not work, a comparison and discussion of why it fails and why the \"double compensation\" is necessary would be a valuable addition to understand the contribution of the paper. \n\n**Theory**\n\nMy major issues with the theory are the strength of the assumptions (Assumption 2), which were not needed in previous work, and the resulting dependence of the hyperparameters on the problem-specific constants which do not match the uncompressed algorithms. For all results, a comparison to the original algorithms would be helpful.\n\nFor example, Theorem 5 and Corollary 6 show a dependence between the batch-size $B_0$ and the total number of iterations $T$. Such a dependence can make any algorithms \"variance-reduced\", and does not match the existing theory for STORM. \n\nSimilarly, the dependence on a (constant) step-size and the total number of iteration did not appear in the original analysis, which instead used decreasing step-sizes. As the submission points out, having the parameters depend (on some power of) $1/T$ is too small and should be decreased over time instead.\n\n\n**Minor comments:**\n\n- Theorem 5: requires $\\gamma \\leq \\frac{1}{4L} \\text{ and } \\alpha \\geq 8(L^2+L_F^2)\\gamma^2/n$. Assuming for simplicity that $\\gamma$ is maximal ($\\gamma = \\frac{1}{4L}$) and $n=1$, $\\alpha \\geq \\frac{1}{2}(1 + \\frac{L_F^2}{L^2})$. As $L$ is the smoothness constant of $f_i$ and $L_F$ the smoothness constant of the individual components $F$ of $f_i$, $L_F \\geq L$ and $\\alpha \\geq 1$. This runs counter to the assumption that $\\alpha$ is a convex combination parameter $\\in (0,1)$ (l124, p5).\n\tCorollary 6 also does not follow from Theorem 5 as the specified $\\alpha = 8L^2\\gamma^2/n$ falls outside of the range allowed for Thm 5. My guess is that the step-size should instead depend on the smoothness constant of the stochastic functions ($\\propto 1/L_F$ instead of $\\propto 1/L$)?\n- Please be careful when discussing the dependence of the step-size on the current iteration $t$ or the total number of iterations $T$. For example, Figure 1 mentions that $\\alpha_t = 1/t$ but the text before it is \"However, we find that when $\\alpha_t$ is very small ($O(1/T)$ for ROOT-SGD and $O(1/T^{2/3})$ for STORM, where $T$ is the total training iterations)\" (l110-111, p4)\n\tIs it $1/T$ or $1/t$? Using $\\alpha$ instead of $\\alpha_t$ when $\\alpha_t$ is kept constant could help avoid confusion.\n- Assumption 1, bounded variance: the current assumption reads\n\n\t$\\mathbb{E}_{\\zeta^{(i)} \\sim D_i}[\\Vert \\nabla F(x, \\zeta^{(i)}) - \\nabla f(x) \\Vert^2] \\leq \\sigma^2, \\forall x,i$\n\n\tI assume it should instead read as ($f_i$ instead of $f$)\n\t\n\t$\\mathbb{E}_{\\zeta^{(i)} \\sim D_i}[\\Vert \\nabla F(x, \\zeta^{(i)}) - \\nabla f_i(x) \\Vert^2] \\leq \\sigma^2, \\forall x,i$\n\n\tIf not, then the assumption that $\\mathbb{E}_{\\zeta^{(i)} \\sim D_i}[F(x, \\zeta^{(i)})] = f(x)$ should be explicitly stated as it is very strong (and counter to the description of Section 3, \"we do not assume that all nodes can access the same data set\"). Which one is actually  used in the proofs is unclear, as t\n- Assumption 1 writes that \"$f(\\cdot)$ and $F(\\cdot,\\zeta)$ are assumed to be $L$-smooth\" but $f$ is $L$-smooth while $F$ is $L_F$ smooth.\n- Theorem 1 depends on the additional assumption that the step-size $\\gamma$ is smaller than $1/L$ (l429, p18) and needs to be added to the theorem statement.\n- Denoting $C_\\omega$; \"Here $\\omega$ denotes the randomness of the compression operator\" (Footnote 2, p3)  \n\tAs I understood it, omega is the random seed used in the compression operator such, in the equation between l99 and l100, the same compression is applied to the term added to $x_t$ and $\\delta_t$. Adding a subscript, $\\omega_t$, or using an intermediate variable $q = C_\\omega(...)$ to update $x_t$ and $\\delta_t$ would make that clearer. The current notation, for example in Algorithm 1, implies that all instances the compression operator $C_\\omega$ use the same random seed and is deterministic.\n- Adding references to table 1 would help\n- The \"total batch-size $B_0$\" variable in algorithm 1 seems unused.\n- typo: l89 STROM (STORM)\n\n\n---\n\n**References:**\n- Xun Qian, Peter Richtárik, Tong Zhang: \"Error Compensated Distributed SGD can be Accelerated\".   \n\tOPT2020: 12th Annual Workshop on Optimization for Machine Learning\n- Zhize Li, Dmitry Kovalev, Xun Qian, Peter Richtárik: \"Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization\" ICML 2020.\n- Ashok Cutkosky, Francesco Orabona: \"Momentum-Based Variance Reduction in Non-Convex SGD\", NeurIPS 2019\n\n\n\n---\n\n**Update**\n\nI thank the autors for their response. Some of my concerns have been adressed and I increased my score. For a revision, I would the authors focus on the following points:\n- The potential applications of the method are not well discussed. The paper considers stochastic, non-finite sum problems in a distributed setting where communication is the bottleneck, but does not provide real examples that are not adressed by previous work but fall in the scope of the proposed method.\n- The motivation of the key contribution, the proposed modification to compression using compression buffers, needs better exposition. It is unclear, for example, how it would compare to a naïve solution of compressing a momentum-like buffer, and why the two buffers are necessary. Similarly, due to strength of Assumption 2 and the use of an increasing batch size, the comparison of the proposed method to previous work is muddled. While those may be standard techniques to simplify the proof and/or achieve better convergence rates, their inclusion makes it difficult for the reader to understand the key contribution of the submission.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "14"}, "extra_text": {}}, {"review_id": "TKyat3XFdcg", "reviewer": "Reviewer_2AUC", "summary": "This paper proposes ErrorCompensatedX, a method of adding low-pass filters to error compensation method on a type of variance reduced algorithms. A framework of proving convergence is given on some example algorithms (e.g. Momentum SGD, STORM, IGT) and experiment of Resnet-50 on CIFAR10 is conducted for comparing the convergence of algorithms.", "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": "Strength\n==\nError compensation is an important technique for communication compressed model training. In practice, it is true that sometimes (especially at the beginning of training), an ill-conditioned compensation scheme would make the training unstable, especially when we are using cheap compressors such as biased 1-bit quantizer. Having said this, the motivation and the topic of this paper is good and important to the community.\n\nWeakness\n==\nTo begin with, it's not clear what challenge Algorithm 1 is trying to solve, or what settings will Algo 1 be applicable to. Specifically, ErrorCompensatedX requires at least three additional buffers for communication, i.e. $\\delta_{t-1},\\delta_{t}, e_{t-1}$, which are of model size. This very much limits the deployment of the algorithm. The reason we need communication compression is model/gradient being high-dimensional -- does it really worth using 3X additional memory just for low-precision communication? Consider the case of BERT or GPT-2, these additional buffers would take ~GBytes memory and would affect scaling the mini-batch on a modern GPU. If GBytes of memory is needed for all the compressors, why can't we use more bits (more than 1-bit) instead? \n\nAside from applicability, how ErrorCompensatedX contributes in terms of theory is also unclear. In the theoretical analysis, a general method of decomposing a convergence rate into uncompressed and compressed parts is given. This is somewhat confusing as it seems to be the standard method to prove the convergence of any compressed optimization algorithm, please correct me if I'm wrong. Besides, obtaining the same $O(1/\\sqrt{nT})$ rate compared to the uncompressed algorithms is not surprising, as the sample complexity is always the leading term. To the best of my knowledge, I haven't seen any compression-based algorithm breaking this term. The main design seems to be the application of low-pass filters in several algorithms, but how is it different from (Chen et al., 2020; Wu et al., 2018)?\n\nSome technical issues:\n\ni) Why ErrorCompensatedX can only be used on the algorithms specified in Table 1? If the main idea is to compensate the entire history, why can't other optimizers like Adam use it?\n\nii) The assumption on the compressor (i.e. Assumption 2) seems strong, will the algorithm still converge under the following more general assumption:\n\n$\\mathbb{E}||\\mathcal{C}_\\omega(x)-x||^2 \\leq \\omega||x||^2 + \\epsilon^2$,\n\nlike the analysis in (https://arxiv.org/pdf/1907.09356.pdf)?\n\n**Update**\n\nI thanks the authors for clarifying the concerns on the proof and technical achievements. These adequately addressed my concerns so I increase the score slightly to reflect that. On the other hand, I'm still on the fence about the first concern, i.e., the practical usage of the algorithm. I agree with the authors that communication is the bottleneck in many distributed training problems. But I think it would be more convincing if time-wise results are shown in the paper to support the claim that trading 3X memory with bandwidth would be beneficial.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No significant limitations are shown.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "GBqE86gfPI", "reviewer": "Reviewer_Qn5b", "summary": "In contrast to the existing works that only use the compression error from the last step to correct the gradient, this paper proposed to use the compression errors from the previous two steps. The paper assumes that the compression is applied to gradient before getting accumulated to momentum. Under certain conditions, the theoretical analysis shows that the proposed method achieves better bound than only using the compression error from the last iteration.", "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": "This paper proposed a general framework for analyzing different gradient estimators. The theoretical analysis is sound and convincing. The writing needs some improvement to better explain the proposed idea and how we derive its formulation. But I have one major question for the authors.\n\nZheng, S., Huang, Z., & Kwok, J. (2019a) applies compression to momentum instead of gradient estimator, while this paper does it in an opposite way and assumes that the compression is applied to gradient estimator instead of momentum. I am curious how do the theoretical results of the proposed method compare to theirs? From Theorem 2, we can see that the bound is the same with alpha=1 for single compensation and ErrorCompensatedX. So it is interesting to know if the bound can also be improved if we apply compression directly to momentum.\n\nIn addition, how do we derive the equation equation below line 125 from the equation below line 121? I cannot find any explanation. And, how do we obtain the equation (3) from the equation equation below line 125? Why there are extra coefficient \\alpha_{t-1}/\\alpha_t and \\alpha_{t-2}/\\alpha_{t-1}?\n\nThe experiment is not strong. But I appreciate the theoretical contributions, so I still advocate for acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a novel error feedback mechanism to handle momentum-like terms (most notably, SGD with momentum and STORM). The paper presents theoretical analyses of existing momentum-like algorithms coupled with compression based on their modifications and experimental results confirming their results.

The reviewer commended the new direction and find the results of interest to the community. The reviewers also find, as a minor issue, that the assumptions used in the analysis are a bit strong and, more crucially, the experiments do not yet clearly demonstrate practical usability.

The reviewers find that there is currently not enough motivation presented that would justify the 'need' of two momentum buffers. In the particular in the presence of earlier work that successfully (though mostly empirically) applied compression to momentum SGD with a single buffer [such as the cited (Zheng, S., Huang, Z., & Kwok, J. (2019a). Communication-efficient distributed blockwise momentum sgd with error-feedback) and (Vogels, T., Karimireddy, S. P., & Jaggi, M. (2019). Powersgd: Practical low-rank gradient compression for distributed optimization.)] the reviewers find that the key differences should be highlighted better. 
Additionally, I also find it strange that the paper sets off with the question 'what is the best compression method for variance reduced algorithms?', yet optimality of the proposed scheme is not discussed. 

The reviewers provided detailed and well-justified feedback and the authors are encouraged to take their comments into account in the revision. In particular, since the application of error feedback to STROM appears to be a novel direction, we are confident that this work will attract interest in the community after repositioning and recalibration.
Decision: Accept (Poster)