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) (dd((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 [Tagg 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-compenstted 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 0 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 Σ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 a 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² 0002))
(.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 iSngla 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
Momannuum SCD (Sigge Concersalior Mumemmm (imorooppeovvs)
STOWN riigle Conseradionn
STORM
70
ICT Sagg Co Comsmattion
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 EroorCompenstedX'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 data-paralls 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": "esK1N_SG9fK", "reviewer": "Reviewer_LLeQ", "summary": "This paper introduces a new method for error compensation in distributed optimization algorithms, specifically compressed gradient descent-based (CGD) algorithms, with the ultimate goal of reducing communication cost. Compared to existing error compensation approaches, the proposed method, termed ErrorCompensatedX, utilizes the error from the previous two steps of compressed gradient descent to improve it’s convergence rate. Despite some promising theoretical results, the numerical experiments seem inadequate, and below average exposition makes parts of the paper difficult to fully comprehend.", "questions": "", "limitations": "", "rating": 6, "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": "While the idea presented seems promising and some theoretical results are provided, this paper does not clearly indicate whether the proposed scheme reduces communication cost. Exposition is suboptimal and quite dense in places, and as such makes judging the paper on its’ merits and identifying novelties difficult.\n\nSome further comments are below:\n1. Since this paper concerns communication efficient optimization, one would expect to see theoretical and empirical results regarding communication complexity, communication rounds and number of communicated bits. The empirical results presented in Sec. 5 focus only on training loss and testing accuracy versus the number of training epochs. \n2. Is $\\xi^{(i)}$ in Eq. (1) different from $\\xi_t$ in Eq. (2)?\n3. Is $\\alpha_t$ a positive scalar, or can it take any value?\n4. Some additional intuition regarding the role of $\\mathbf{e}_t$ in the equations after line 103, could facilitate better understanding of the proposed method. Also, how  does this equation describe a low-pass filter? \n5. In the beginning of Section 3.2 it is mentioned that $\\mathscr{A}$ is transferred from worker nodes to the server, however the ensuing equations do not involve the workers. The note in line 126 that the discussion focused on the one worker case should be mentioned earlier, ideally in the beginning of the subsection.\n6. The difference between $\\mathbf{\\delta}_s$ between the second and third equations in Sec. 3.2 can be confusing.\n7. The innovation of ErrorCompensatedX compared to regular Error Compensation should be made more explicit in Sec. 3.2.\n8. In line 122 it is mentioned that when $\\alpha = 1$, the last term disappears. However, if $\\alpha = 1$ all terms except $\\mathbf{x}_0$ seem to disappear. \n9. In line 133 it is mentioned that \"using just the compression error from the last step is not good enough\". Not good enough with respect to what criterion? Also, where is this analysis shown?\n10. In Assumption 2, the same inequality is written twice. \n11. What does the learning rate in Sec. 5 refer to?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Discussion regarding limitations of the proposed method seems lacking. \n\nPaper is mainly theoretical and societal impact depends on how the practitioner would deploy the proposed method. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Z9vsAyLdV-A", "reviewer": "Reviewer_HwbF", "summary": "In this paper, the authors present ErrorCompensatedX, which compensates the compression error using the information from the previous 2 steps instead of 1 for distributed SGD with variance reduction. Theoretical analysis is provided. Empirical results show that the proposed algorithm outperforms the baseline with single compensation.\n", "questions": "", "limitations": "", "rating": 7, "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": "The paper is well-written. A novel method for improving the error compensation in variance-reduced SGD is proposed. Furthermore, a general theoretical analysis framework is provided for the proposed method. The experiment results also show good performance compared to the baseline. Overall, I think this is a good paper and I tend to accept it.\nI have the following questions/concerns:\n1. Compared to single compensation, how much extra computation and memory is cost by ErrorCompensatedX?\n2. According to line 184-186, if alpha=1 (SGD case), single compensation and ErrorCompensatedX share the same error bound. Does that mean that in SGD case, single compensation is equivalent to ErrorCompensatedX? No matter if this is correct or not, could you give more explanation about such a special case?\n3. I would recommend adding some more experiments. It could be either larger experiments like CIFAR-100/ImageNet, or applications other than CV, like NLP. Although I don’t think this is a big issue, using multiple datasets/applications in the experiments will be very helpful in showing the good performance of the proposed method.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. In some cases, such as momentum SGD, it seems that ErrorCompensatedX does not outperform single compensation.\n2. Only 1 compressor (1-bit compressor) is tested in the experiments. Different compressors may have different behaviors. I also recommend to try top-k and random-k compressors.\n3. Communication reduction is mostly for reducing the overall time for distributed training. However, no training time is provided in the experiments.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "V59RAYeZRKC", "reviewer": "Reviewer_7b4p", "summary": "This paper proposes an extension to the error compensation framework to reduce communication burden in distributed systems. The idea is to use previous two (instead of one) accumulated compression errors in the history together with low-pass filter update. The extension is applied for variance reduced methods and is analyzed for non-convex smooth objectives. The work provides general framework to analyze such methods, it shows that asymptotic convergence of such methods is the same as without compression and error compensation. Two numerical experiments are included with linear regression and neural networks to illustrate effectiveness of the proposed extension.", "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": "1. It is mentioned in the abstract (lines 8,9) that your analysis standard Error Compansation (EC) does not fully compensate the compression error. Where this statement is justified in your theory ?\n\n2. Then, you propose ErrorCompansatedX (ECX), which presumably compensate the compression error fully and achieves the same rate as without compression. But the same claim about the rate is true for EC methods (see [1,4,5]).\n\n3. Are the statements on reducing half (line 19) or 3% (line 24) of the communication volume without degrading the speed of convergence accurate ? Are they theoretical results for general training or numerical results on some datasets ?\n\n4. Are the references of Momentum SGD in line 28 and STORM in line 29 accurate ? For example, STORM method is not from (Cutkosky & Mehta, 2020).\n\n5. In the introduction (lines 32-34), it is claimed that *the best* compression method for Variance Reduced (VR) methods is found and it is the proposed ECX. Where exactly do you prove that it is the best one ? If so, it is the best one in what sense ?\n\n6. The first point of contribution (lines 36-38) claims that ECX admits *faster convergence rate* compared to previous methods. However, section 4 (lines 145-146) says it gives the same (asymptotic) rate as uncompressed methods; something that previous methods also achieved (see [1,4,5]).\n\n7. Line 38 mentions that ECX fully compensates all error history. What does this mean ? If you are referring the fact that ECX uses previous two errors, then what about using previous three or more error terms. If this statement is empirical and is based on some experiments (e.g., Figure 1), it should made more precise.\n\n8. The second point of contribution (lines 39-44) decomposes the rate into the terms affected by compression and terms that will remain even with full precision training. I think this is typical for most of the compressed algorithms. Minor: equation (2) in line 44 is defined much later after line 90.\n\n9. Lines 73-78 are confusing. Why you highlight linear rate from (Mishchenko et al., 2019; Liu et al., 2020) and (Horva´th et al., 2019) in strongly convex setup, when you consider non-convex objectives only and all those three papers also include some theory for non-convex optimization (which is not mentioned there) ?\n\n10. EC update rule described after line 99 is not exactly accurate because of the step-size $\\gamma$ (it should be inside the compression operator; see e.g. equation (8) of (Stich et al., 2018b) ).\n\n11. Related to the claim made in line 106, see [3,6,7].\n\n12. Is the dependence of $\\epsilon$ in the rate of Corollary 4 accurate ? It is in the denominator, meaning that less compression leads to worse upper bound. Also, the same leading term is achieved by Doublesqueeze method for non-convex losses.\n\n13. In the section for experiments it is mentioned about four implementations, but plots contain three. Assumption two contains the same expression twice.\n\n14. At least 10 references do not have journal/conference names (if not published then usually arXiv version is being referenced).\n\nOut of curiosity, why the method is called ErrorCompansatedX ?\n\n--------------------------- \n\n\nWhat can be done to improve the paper ?\n\nI1. It is claimed that the paper provides general theoretical analysis framework for error compensated and variance reduced methods. One can use that framework to design a new method, which would outperform current VR methods both theoretically and numerically in some (at least one) settings. \n\nI2. By describing the improved behavior of some method, it is important to identify and highlight the aspect/compenent of the method which actually makes the improvement. For instance, the proposed Algorithm 1 adds two components on top of EC framework: low-pass filter and second previous compression error. Which component contributes to faster convergence in Figures 1 and 2 ? Are both of them needed ? Do we actually need second previous error, since as it was mentioned in lines 101-102, low-pass filter can be helpful for stabilizing the training and further improving the training speed.\n\n\nI3. Avoid over-claimed or conflicting statements (see points 3,5,6 above)\n\nI4. Fix the references and inaccuracies when citing prior work (see points 9,10,11,14)\n\n--------------------------- \n\n\n[1] Hanlin Tang, Xiangru Lian, Chen Yu, Tong Zhang, Ji Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression. ICML 2019.\n\n[2] Horva´th, S., Kovalev, D., Mishchenko, K., Stich, S., & Richtarik, P.. Stochastic distributed learning with gradient quantization and variance reduction. arXiv 1904.05115, 2019.\n\n[3] Xun Qian, Hanze Dong, Peter Richtarik, Tong Zhang. Error Compensated Loopless SVRG for Distributed Optimization. OPT2020: 12th Annual Workshop on Optimization for Machine Learning, 2020.\n\n[4] Sebastian U. Stich, Sai Praneeth Karimireddy. The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Updates. Journal of Machine Learning ResearchJMLR 21(237), 1–36, 2020.\n\n[5] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, Martin Jaggi. Error Feedback Fixes SignSGD and other Gradient Compression Schemes, ICML 2019.\n\n[6] Xun Qian, Peter Richtarik and Tong Zhang. Error Compensated Distributed SGD Can Be Accelerated, arXiv 2010.00091, 2020.\n\n[7] Xun Qian, Hanze Dong, Peter Richtarik, Tong Zhang. Error Compensated Proximal SGD and RDA. OPT2020: 12th Annual Workshop on Optimization for Machine Learning, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It might be a good idea to write a small section on limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7+7"}, "extra_text": {}}, {"review_id": "LWBWUQqOvX3", "reviewer": "Reviewer_56o9", "summary": "The paper proposes and analyse a generic error compensated scheme for variance reduced optimization algorithm in a distributed setting.", "questions": "", "limitations": "", "rating": 7, "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": "The paper is well-written and pleasing to read. It is not excessively original, but the analysis is generic to several variance-reduced algorithms and very nicely carried out with a good balance between quantitative results and qualitative explanation. The contribution is also well-motivated with respect to previous work. The numerical experiments are also nicely presented without being excessively striking. It is the most appreciable paper in my batch of seven NeuRIPS papers this year.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: I agree with the reviewers that this paper is well-written and has a nice analysis of several variance-reduced algorithms, balancing quantitative results and qualitative explanations. But I also agree with the reviewers that the exposition and notation could be improved, the effect of the low-pass filter could be better explained, and more extensive experiments could be carried out (especially for STORM, which has the best practical performance improvements, and for data sets where other values of alpha and beta are optimal). The reviewers give a large number of minor suggestions that can help you to significantly improve the paper.

I recommend that the paper should be accepted.
Decision: Accept (Poster)