Error Compensated Distributed SGD Can Be Accelerated
Authors: Xun Qian
Peter Richtárik
Tong Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: machine learning
error feedback
acceleration
L-Katyusha

Abstract: Gradient compression is a recent and increasingly popular technique for reducing the communication cost in distributed training of large-scale machine learning models. In this work we focus on developing efficient distributed methods that can work for any compressor satisfying a certain contraction property, which includes both unbiased (after appropriate scaling) and biased compressors such as RandK and TopK. Applied naively, gradient compression introduces errors that either slow down convergence or lead to divergence. A popular technique designed to tackle this issue is error compensation/error feedback. Due to the difficulties associated with analyzing biased compressors, it is not known whether gradient compression with error compensation can be combined with acceleration. In this work, we show for the first time that error compensated gradient compression methods can be accelerated. In particular, we propose and study the error compensated loopless Katyusha method, and establish an accelerated linear convergence rate under standard assumptions. We show through numerical experiments that the proposed method converges with substantially fewer communication rounds than previous error compensated algorithms.

Error Compensated Distributed SGD can be Accelerated
Xun Qian' xun. qian@kaust sa
Peter Richtárik Otterriihharikokaaue edu.
Tong Zhang' tongzhangoust. hk
Abstract
Gradient compression is a recent and increasingly popular technique for reducing the communication cost in distributed training of large-scale machine learning models. In this work we focus on developing efficient distributed methods that can work for any compressor satisfying a certain contraction property, which includes both unbiased (after appropriate scaling) and biased compressors such as RandK and TopK. Applied naively, gradient compression introduces errors that either slow down convergence or lead to divergence. A popular technique designed to tackle this issue is error compensation//rror feedback. Due to the difficulties associated with analyzing biased compressors, it is not known whether gradient compression with error compensation can be combined with acceleration. In this work, we show for the first time that error compensated gradient compression methods can be accelerated. In particular, we propose and study the error compensated loopless Katyusha method, and establish an accelerated linear convergence rate under standard assumptions. We show through numerical experiments that the proposed method converges with substantially fewer communication rounds than previous error compensated algorithms.
Introduction
When training very large scale supervised machine learning problems, such as those arising in the context of federated learning (Konččý et al. 2016b] McMahan al., 2017 Konečný et al. 2016a] (see also recent surveys [Li et al. 2019 Kairouz (2019). distributed algorithms are indispensable. In such settings, communication is generally much slower than (local) computation, which makes it the key bottleneck in the design of efficient distributed systems. There are several ways to tackle this issue, including reliance on large mini-batches [Goyal al. [017 You al. [017]. asynchronous learning [Agarwal and Duchi 2011 Lian |001 Recht et al. [011], local updates [M et al.
2017 Stich 2020, Khaled et al.) 2020 [ and Richtárik 2020 Woodworth et al. 2020 and
communication compression (e.g., quantization and sparsification) AAlistrr et al. 2017 Bernstein
ct al. 2018 Mishchenko et al.) 2019 Seide et al. 2014 Wen et al. 2017].
Communication compression. In this work, we focus on the last of these techniques: communication compression. The key idea here is apply a lossy compression transformation/operatoo to the messages before they are communicated so as to save on communication time. While compression reduces the communicated bits in each communication round, it introduces errors, and this generally leads to increase in the number of communication rounds needed to find a solution of any predefined accuracy. Still, compression has been found useful in practice, as the trade-off often seems to prefer compression no compression.
KKin Abdullah University of Science and Technology, Thuwal, Saudi Arabia 1 King Abdullah University Science and Technology, Thuwal, Saudi Arabia; Moscow Institute of Physics and Technology, Dolgoprudny, Russia $ Hoong Kong University of Science and Technology, Hong Kong
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Contractive and unbiased compressors. There are two large families of such compression operators: contraction and unbiased compressors [Beznosikov et al. 2020]. A (possibly) randomized map
Q: Rd I is called contraction compressor if there exists a constant 0 < 8 < 1 such that
E [| Q=))ll - (1 ==]
vr E R
Further, we say that randomized map @ Rd + IR is an unbiased compressor if there exists constant w 2 0 such that
EB [Q(w)] = x and [Q(())] S 1)
Var E IR..
It is well known that (see, e.g., [ezzosikov et al. 2020 after appropriate scaling, any unbiased compressor satisfying (2) becomes a contraction compressor. Indeed, it is easy to verify that for any Q satisfying ( w+1 Q is a contraction compressor satisfying (I) with å = 1/(w+1). Thus we can construct corresponding contraction compressor from any unbiased compressor. However, there are empirically very powerful contractive compressors, such as TopK (Alistarh et al. (2018) (described below), which do not arise this way, and because of this, the class of contractive compressors important in practice. For illustration purposes, we now define two canonical examples of contraction compressors. Let < K d. The Topk compressor defined as
(x))(())))))))))))))) if K, otherwise.
(TopK(z))>()
where π is a permutation of {1, 2, ..., d3 such that ([z)) 2 (1z))<(+1 for i L,..., d 1. The RandK compressor is defined as
(RandK(z)), = (r); if otherwise,
where S' is chosen uniformly from the set of all element subsets of 21, For TopK and RandK compressors, we have ó 2 K/a (Stich et al. 2018). Some frequently used unbiased compressors include random dithering [Alistarh et al. 2017]. random sparsification (Stich et al. 2018), and natural compression [Horváth et al. [019b] For more examples of contraction and unbiased compressors, we refer the reader to Beznosikov et al. 2020].
Related Work. If we assume that the accumulated eтror is bounded, and in the case of unbiased compressors, the convergence rate of error compensated SGD was shown be the same as that of vanilla SGD (Tang et al.) 2018). However, if we only assume bounded second moment of the stochastic gradients, in order to guarantee the boundedness of the accumulated quantization error, some decaying factors need to be involved in general, and error compensated SGD is proved to have some advantage over QSGD Alistarh et al., 2017] some perspective for convex quadratic problems [Wu et al. 2018). On the other hand, for contraction compressors, has the same convergence rate as vanilla SGD [Stich et al. 2018 Stich and Karimireddy 2019 Tang ct al. 2019]. Since SGD only has sublinear convergence rate, these error compensated methods could not get linear convergence rate. If f is non-smooth and tú = O, error compensated SGD was studied in [Karimireddy et al. 2019 in the single node case, and the convergence rate is of order O (1/VBR).
compensated SGD actually
For variance-reduced methods, QSVRG (Alistrrh al. 2017 handles the smooth case ( 0), and VR-DIANA [Horváth et al.) 2019a], ADIANA [Li et al. 2020) handle the composite case (general v). However, the compressors of these algorithms need to be unbiased. Error compensation in VR-DIANA and ADIANA does not need to be used since their method successfully employs variance reduction (of the variance introduced by the compressor) instead. Recently, error compensated method called EC-LSVRG-DIANE strongly convex and smooth case was proposed in [Gorbunov al. 2020), but besides the contraction compressor, the unbiased compressor also needed in the algorithm.
which can achieve nonaccelerated linear convergence for the
Error compensation. While contractive compressors can be more powerful in practice, they are not unbiased, and this leads to severe difficulties the algorithm design space, and poses challenges for theoreticians trying to understand the convergence behavior of distributed algorithms using contractive compressors. Indeed, while there is no issue with the use of contractive compressors in the non-distributed setting (which is of course not interesting from practical point of view) in

---

combination with standard gradient-typ type methods, serious convergence issues arise in the distributed setting. Indeed, classical methods such gradient descent can diverge (even exponentially fast) when the Topk compressor is used to compress uplink gradient information Beznosikov et al. 2020]. Fortunately, this issue can resolved using the error compensation (EC mechanism, which can be traced back to at least[Seide et al. [2014). However, this mechanism remained a heuristic until recently. To highlight the difficulty of analyzing EC, we remark that the first theoretical breakthroughs applied to the single node regime only (Stich et al., [2018] Stich and Karimireddy 2019]. More recently, theoretical progress was made in the crucially important distributed setting as well [Beznosikov et al.
2020 Gorbunov et al. 2020]. However,
still very far in our understanding of optimization
algorithms using contractive compressors.
One of the key open problems in this area-the problem address in this paper in the affirmative- is whether it is possible to design provably accelerated gradient- type methods that work with contractive compressors.
In this paper, we give a confirmed answer by studying error compensation in conjunction with the acceleration mechanism employed in loopless Katyusha (L- (L-Kauyusha) [Kovalev et al. 2020 Qian
al. 2019], which a loopless variant of Katyusha [Allen-Zhu) [2077] The acceleration Katyusha
or I. La-Katyusha is an extension of Nesterov's 's acceleration [Neserrvv 1983 2004] in the stochastic regime. Moreover, Katyusha and L--Katyusha can achieve the optimal iteration complexity among
randomized methods for solving finite-sum strongly convex optimization problems Lan and Zhou
2018
2 Problem Description and Summary of Contributions
We formally describe the distributed optimization problem we solve in Section 2. and then summa- rize our key contributions Section 2.2
2.1
Problem Description
We consider the composite finite-sun sum optimization problem
1 n Σ (z)) + (
min P(x) FER
where f(x) = ΣΣ (x) is an average of n smooth convex functions, distributed over n compute nodes, and vi: Rdd + Ru is proper closed convex function representing possibly nonsmooth regularizer. On each node T, f()) (x) is an average of m smooth convex functions, i.c., m
(() m Σ (x), representing the average loss over the training data stored on this node.
We denote the smoothness constants of functions f. f(r) and f(() using symbols Ly, L and L, respectively These constants are in general related as follows: L mL.
L, < L < nLy,
(4)
While we specifically focus on the case when m 1, our results are also new in the I case, and hence this regime relevant as well. We assume throughout that problem (3) has at least one optimal solution x².
We will optionally use the following additional assumption for the contraction compressor. The assumption is not necessary, but when used, it will lead to better complexity.
Assumption 2.1. [xQ(x)) åx and IE[Q (æ)] = 8, for all x E IR, where 6 and ôn are compres- sion parameters of Q and Q2, respectively.
It is easy to verify that RandK compressor satisfies Assumption 2.1 with 8 = K/d, and w+1 Q, where Q is any unbiased compressor, also satisfies Assumption 2.1 with 8 1/(w+1).
'Eroo compensation is also known under the name error feedback. FFunction f Ed -> R smooth is differentiable, and has L-Lipschitz gradient: ([)))-(())]) Ll| yll for any x, y Ltd. is called the smoothness constant of f.
3

---

2.2 Contributions
We now summarize the main contributions of our work.
Acceleration for error compensation. We develop new communication efficient algorithm (Algorithm[] [ for solving the distributed optimization problem (3) which call Error Compensated Loopless Katyusha (ECLK). ECLK is the first accelerated error compensated method (this is true even in the non-distributed setting), which believe is significant contribution the field.
Iteration complexity. We obtain the first accelerated linear convergence rate for error compensated methods using contraction operators. Let p I (61), where p E (0, 1] is parameter of the method described later and ò the compression parameter of Q1 in Algorithm I (see Assumption 2.1). Then the iteration complexity of ECLK is
((
L
(1-83L Ap
(1-8)L uP8
log
(5)
This is an improvement over the previous best known results for error compensated methods in (Beznosikov al.) 2020 and [Gorbunov al.) 2020), where nonaccelerated linear rates were obtained for the smooth case (*) = 0). Moreover, in oder to obtained linear rate, [Beznosikov et al.
[2020] required the assumption that V (x²) 0 for all and also need full gradients to be computed by nodes. The complexity of EC-LSVRG-DIANA in Goorbnno et al. 2020 is
o (( m ) log
(6)
When the last term in (6) is dominant and the last two terms in (5) are dominant, the complexity of ECLK is better than that of EC-LSVRG-DIANA if O 1 (1-6)6y
If we invoke additional assumptions (Assumption 2.1 on the contraction compressor, the iteration complexity of ECLK is improved to
(
Lr
L ppm
(1-6) up
+
(1-8)z
log !
This is indeed an improvement since L,j S L (see (4), and because of the extra scaling factor of n in the last term. 5 = i.e., no compression is used, we recover the iteration complexity of the accelerated method L-Katyusha [Qian et al. 2019
3 Error compensated L-Katyusha
3.1 Description of the method
In this section describe method: error compensated L- L-Katyusha (see Algorithm []. Roughly speaking, ECLK a combination of L-Katyusha, error feedback, and a learning scheme in VR- DIANA [Hovväth et al. 2019a].
The search direction L- L-Katyusha in the distributed setting (n 2 1) iteration k: is
(w + v o (())
where i7 is sampled uniformly and independently from [m] = {1, 2., m) on the 7-th node for
1 << - S x* is the current iteration, and wx is the current reference point. Whenever & is nonzero
in problem (3). f=(=") is nonzero in general, and so is f (a*) (it could be nonzero even
Vf(x*) 0 the non-regularized case). Thus, compressing the direction
(2*) VJ (7) (w** (w)*)
directly on each node would cause nonzero noise even if t and w converged to the optimal solution x²" On the other hand, since f/(²) is L-smooth, V (T) (I*) V (w*) could be small if a and
w are close enough. For the last term v (w"),, introduce vector he leam it iteratively in

---

similar way in VR-DIANA However, we use contraction compressor rather than an unbiased one. More precisely, we take the update
h h h Q1 QV - h)),,
(8)
where Q1 is a contraction compressor. fi can be initialized by any vector in IR It is possible to interprete the learning procedure (8) as one step of the compressed gradient descent method applied to certain quadratic optimization problem whose unique solution is the vector (f((((")) Now would expect V f (w*) h could converge
k. +00. We substract h from the search
direction in to get
9 -
Vig (w*) + ( h
and will add h back after aggregation.
Next we apply the compression and error feedback techniques, i.e., we compress the vector " on each node get --t = Q o + ef), where Q is contraction compressor and L1 is positive parameter. The accumulated eπror e is updated by the compression error at iteration k. On each node, a scalar u is also maintained, and only uf will be updated. The summation of u for 1 T T n w², and we use u² to control the update frequency of the reference point = Each node sends the two compressed vectors or. (V( nodes. After aggregating g* 1. -
Σ, 9 + +e
hr),, and scalar #k+1 the other gr. we add the average vector h - h after multiplying the stepsize E to get the search direction g + 2.1.. We also use the following standard proximal operator for the update of eh:
prox (x) = arg min (1ll y/l m))())
The reference point w will be updated if -+ 1. It is easy to see that wht will be updated with probability p each iteration. All nodes maintain the same copies of æt wh 3at 2t, g". ht, and u².
We need the following assumptions in this section.
Assumption 3.1. The two compressors Q and Qı in Algorithm Mare contraction compressors with parameters 8 and 61, respectively.
Assumption 3.2. f(() L-smooth, f(7) is L-smooth, is &b is Strongyy convex, where μ.g 2 0, pe 2 0, and == μ4 + p&g > O.
- -smsoooth and py-strongly convex, and
3.2 Convergence analysis: preliminaries
First, we introduce some perturbed vectors which will be used in the convergence analysis. The perturbed vector is usually used in the analysis of eπто compensated methods [Karimireddy et al.)
2019]. In Algorithm I let ex Σ"=1 ck g² ET= Ih and j x= 1+n01 e", 2
ck Itno; k for l: 2 0. Then c+1
-= (ct o g+ e 2. " ghh and from
the optimality condition for the proximal operator, we have
zh+1
x+1 1 h+1
Itno1
1010 l + =k - - 2,1
n
.+1
I+noi
(1+n01)27
1tNo1
1111 + + _ 2 -
now 1
(2+
[10 i
t g
1 hht C. (14901)41
*+1)
I+901
The above relation plays vital role in the convergence analysis, and allows follow the analysis of original L-Katyusha. In particular, we will use zt to construct Lyapunov functions. Next we define some notations which will be used to construct Lyapunov functions. Define 2 Citna/2
We can also use single shared random variable & instead.

---

Algorithm Error Compensated Loopless Katyusha (ECLK)
1: Parameters: stepsize parameters "I
0, L1
0, 01
# 2 0, 01, 02 E (0, 1):
301
22
probability p E (0, 1]
2: Initialization: -0 10
20 w R4. u 0
E
R: &
0
E
R2. h2 E R4.
u - uh; ho =
Σ h
3: for = 0,1,2.... do
4: for r = 1,.... do
5: Sample og uniformly and independently in [m]] on each node
6:
- = V 1
(T) (x*)
- (w*) + V (w*) h = h + Q1 (V (v) h)
(r)
7:
g = Q n
E of + + h
8:
e e + 2 o 5..
/+t1 0 for T 2,..,, n
{1
with probability
9:
"1 k+1 { with probability
1-p
10:
Send S"t Q1 (1(V((((**))
)t),, and u to the other nodes
11:
-1+;,, and wht1 from the other nodes g ET=1 gr. u+t = =Er=1 wht1
Receive gz. Q (
12:
13:
k+1 prox T4 [tnos
(Moooo + = - -
-g"
-2211t)
14:
ght z² + 02(22tt - 2
w k+ = { y² if uf+ =1
15:
w² otherwise
16:
x+1 01 b1 + +gw + (1 - 0l - 022-02nn 02)
17:
h+41 ht + D Qi (V(V))))) (w*) )イ
18:
end for
19:
end for
xr 112 y* == (P(*t) P*), and W* == più
8,
(P(w*) P*) for A: 2 O, where ; = P(x*).
From the update rule of w* in Algorithm 1 it is easy to see that
Ex [x[W++1] === = (1- (1- + 12
(10)
(V) y) be the Bregman divergence and E&[]] denote the expectation conditional on x² y²h 2t wht h wht and of. The following lemma reveals the evolution of the other two terms 2* and yk
for 1: 2 0. Let (=)
=
Lemma 3.3. If C1 > Ls and 01 + 02 S L, then Es
[žkt] + + can be upper bounded by
C 2* + (1 - 01 0z) + pgw* +
L1 + 4) 1| + ( G1 +
E&
[|le [13]
2n
+/2 (02
2L me,)
By By(w* (
x*) 1-0 By (1 xx)).
Because of the compression, we have the additional error terms | || and ||
2 in the evolution To upper bound these ervor terms, we need to analyze the evolution of in the next two lemmas.
of 2* and y* in Lemma 3.3
-r= k and 1 E
((() (w>)
Lemma 3.4. The quantity Es
let+1 1p
is upper bounded by the expression
| + 401-mmn² onL
v (w²) - 11
20 2(1-6) e
(4/ + T.) By(w",at a
2
Lemma 3.5. The quantity
1 Σ" E& E
(w) is upper bounded by the expression
(1 - (-4))2 |n
- v + 4Lp (1 2)) By (, 2²)) + 4Lp (1 b/
22 By a²)).

---

for Under the additional Assumption 2.1 we need to analyze the evolution of ||e* and |/** - VV as well, which can be found in the appendix.
3.3 Convergence analysis: main results
With the above lemmas at hand, we are ready to construct suitable Lyapunov functions which enable us prove linear convergence. First, we construct the Lyapunov function & for the general case.
Let L2 = 61 + 112(1-8)L 28(1-8)L
224(1-6)Ep
1 + 2
and for k: 2 0 define
352
36
828,
$ = 2* y* W
461 Kn
Σ
|e
56(1-8)
11 (w
30
Then we can get the linear convergence of tb the following theorem.
Theorem 3.6. Let Assumption 3.1 and Assumption 3.2 hold. L1 2 m. 3,m) 01 + 202 S 1, and 02
2
3L1'
C2 then we have
k 40. 4 2 0.
E [ I (1 min 14 01 + 02 g. (11-2).88
Assumption 2.1 holds, we define the Lyapunov function ti as follows. Let L3 = 112(1-6)L5
224(1 6)L
308(1-6)L
224(1-6)p
(L, + 26
22 (1+
and for l 2 0 define
352
30n
8-81
o.
2he +++3 y* W 1
461 ||e p +
28 (1-,(1-8)
|et1
by
6mm
5611-601 26
11at v v((w*))1
504(1-81 8'6in
1
(1=)))
Then we can get the linear convergence of 4 in Theorem 3.7
Theorem 3.7. Let Assumption Assumption 3.1 and Assumption 3.2 hold. If 2 max 3pm}. 01 + 20, I 1, and 0g 2 L2. then we have 32,
.(1 9). g: k To. ))
E [ k
min 2 01 02
02 q
v4
From Theorems 3.6 and 3.7 by choosing the parameters appropriately, we can obtain the iteration complexity for ECLK. Theorem 3.8. Let Assumption 3.1 and Assumption 3.2 hold. Let Li max (La, L5 3pm)) O2
Cs and
3 f.,.
min
Exp 02)02)
Lf - f
01
min
otherwise
(i) Let C4 Cz. Then with some q E 12 1), we have 1| < < for L,
k k 0
(
Ls log 1
In particular, if S (61)) then the iteration complexity becomes
k k ((
+
+
L1
L
(1- 8)L
(1-8)4 8)L upō
log
(11)
ppM
ap
(ii) Let Ls = Lz. If Assumption
2.1
holds, then for some q E 12. 1). we have E|y < ev
k O
+ + 1
/
Ca np
log
If S (8))) the iteration complexity becomes
#
k
1/2
+
Li
L
1//
11-8). Ap
(1-8)L upón
log 1
(12)
From Theorem 3.8 it is easy that the optimal for ECLK is ((1)).
7

---

Comparison to ADIANA. ADIANA (Li et al. 2020 is an accelerated and compressed dis- tributed method with any unbiased compressor. The iteration complexity of ADIANA is np l when S w, and o ((
V VV log when n > w.
If we choose Q and Q1 in ECLK to be the contraction compressor w+1 Q where Q is any unbiased compressor, then 8 = 81 w+I and thus the complexity in (12) becomes
((
LI ((W+V
(w+1) Jmm
+ (w 1)
7 +
ww++1)
log 1
porp- == 61- In this case, the dependency of of the iteration complexity of ADIANA is better than that of ECLK. However, the full gradients are computed by all nodes at each iteration in ADIANA, which could be slower than the communication when is very large. Furthermore, the contraction compressor could be more efficient than the unbiased compressor in practice, i.c., for the same level of compression, could be larger than 1/(w+11. This efficiency of the contraction compressor is the motivation to study the error compensated methods, and in numerical experiments, ECLK is comparable ADIANA.
4 Experiments
In this section, we experimentally study the performance error compensated L-Katyusha (ECLK) used with several contraction compressors on the logistic regression problem for binary classification,
log (1 + exp(-w:Afx) + |=111
where {AAs 3 are the training data points. We use Python 3.7 to perform the experiments. We use the datasets a5a, a9a, w6a, w8a, phishing. and mushrooms from the LIBSVM library [Chang and Lin 2011]. The regularization parameter was set to À 10-3, The number of nodes in our experiments is n 20, and the optimal solution obtained by running the uncompressed L-Katyusha for 10 iterations. More experiments can be found in the appendix.
Compressors. We use three contraction compressors: the TopK compressor with K 1, or the compressor on
_ Q, where Q is either the unbiased random dithering compressor with s vd levels AAlistrrh et al. 2017] the natural compressor (Hovváth al. 2019b). For the Top1 compressor, the number of communicated bits for the compressed vector is 64 + log d], and 5 = 1/a. For the random dithering compressor with vd. the number of communicated bits for the compressed vector 2.&d + 64, and w [Alistarh al., 2017)] For the natural compressor, the number of communicated bits for the compressed vector is 12d, and 1/8 Horváth et al.) 2019b].
Parameter setting. In all the experiments, search for the optimal stepsize for all tested algo- rithms. In particular, we use the parameter setting in Theorem (i) for ECLK. From Theorem 3.8 (i), we know that constants. For the tested problem, = x. Q and Q1 are chosen to be the same contraction compressor for ECLK, which implies that 5 81, and the lower bound for ô can be obtained easily for our used compressors. We set I. as r.y., T.th and I 1tth respectively. Then we choose I, = 1. T.P.. I. L- T,th and I, = 1 T and search for the best t in the set {10-* A 0, 1, 2...... }. We set p 5 for EC-LSVRG-DIANS [Gorbunov et al.) 2020). EC-LSVRG-DIAL DIANA requires the use of an additional unbiased compressor; for this make use of random dithering.
values for all parameters if we know values of jr, 6, 81, p, and Lipschitz
ò for ECLK except in Section 4.4 We calculate the theoretical Ly. L, and
4.1 Top1 vs random dithering vs natural compression vs no compression
First, we compare the uncompressed L-Katyusha method with ECLK with three contraction compres- sors: Topl, random dithering, and natural compression; see Figure T ECLK is orders of magnitude better in terms of communication complexity.
4.2 Comparison with EC-LSVRG-DIANA and ECGD
Next, we compare ECLK with EC-LSVRG-DIANA [Gorbunov et al. 2020] and error compensated GD (ECGD) using the Topl, random dithering, and natural compressor. Note that ECGD is special
8

---

Top1
Top1
Tupa
Rardom dithering
Randem dithering
Random dithering
compression
compreees
compression
1811
25 Communicated per noce (1 bis)
10 10 Communiccttd bis per 11 10"
Communccated bits per node (1 bis)
Figure 1: The communication complexity performance of ECLK used with compressors: Topl vs random dithering vs natural compression vs no compression. Datasets: mushrooms, w8a, and a9a.
dthering
compression
BELK
ECASVRG-DAAAA
ECLK
ECLC
FC- SVRG-DIANA
PC+ SVRG-TWAA ECGD
ECCO
25 Communicated bits per roce 11 10" bistt
Communicated bit per node (1 10" bib))
Communictted bits per node 11 10 best
Figure 2: The communication complexity performance of ECGD vs EC-LSVRG-DIANA vs ECLK for Topl, Random dithering, and Natural compression on a9a data set.
case of error compensated SGD [Stich et al. 2018 with m = 1, where the full gradient V f(()((z)) calculated on each node. Figures and 3 show that ECGD can only converge to a neighborhood of the optimal solution, and that ECLK is considerably faster than EC-LSVRG-DIANA.
4.3 Comparison with ADIANA
Let us denote by ECLK-F the special case of ECLK with m = 1, i... the full gradient V f (x+ is calculated each node. We compare ECLK-F with the accelerated variant of DIANA, called ADIANA eLi al.] 2020], for six data sets. For ADIANA we use two unbiased compressors: random dithering and natural compression. Figure A shows that in terms of communication complexity, ECLK-F is comparable to ADIANA, and can be better than ADIANA in some cases.
4.4 Impact of the update frequency of the reference point
Finally, we test the impact of the update frequency of the reference point p for ECLK with Top1 compressor; see Figure 5
We choose five values for pr 6/3, 8, 35, 98, and 1. Figure performance of p = usually better than p = 6/3. As we increase p from p = 6, the performance of ECLK could be improved. However, if p is too large, the performance of ECLK is no better than p = generally.
that the
Top1
Ranstum ingi
Natural compression
LSVRG OVANA
ECLK
BOLK
FOGD
Communcsated bits per node (2 10 bib)
Commanicated bis per noce 11 10" bis)
Communicated bits per node 11 20" bis)
Figure 3: The communication complexity performance of ECGD vs EC-LSVRG-DIANA vs ECLK for Top1, Random dithering, and Natural compression on mushroom ooms data set.

---

BELK
DELKY Top1
DCLIC Topt
ECUKF Random dithering
Random
ECLICE Random dithering
compression
aithering
ADJANA compression
AQUANA compression
comeression
1811
18
1214
25
25
is
12
Communicated node bis)
Communicated (1
Communicatod
phishing
wba
ECLKFF F Top?
ECLK Top]
EOLK Top1
ECLKF Random dithering
ECLKFF Random dithering
ECLIFF Random dithering
ECLK-F Natural compression
377
ECUIF Natura comp compression
ECLIC Natural compression
ARHANI Bardom ditherng
ADHANA Natural compression
377"
AGUAAA Randum dithwing
Natural compression
ARHANA Rancorn dither
ADIANA Natural compression
1811
Communicated
Communicctod
Figure 4: The communication complexity performance of ECLK vs ADIANA for Top1, Random dithering, and Natural compression on mushrooms, w8a, a9a, phishing, w6a, and a5a data sets.
mushrooms
wBa
Trai:
Tac 813
BELK 8/3
p 8
ECUK 6
FCIK
FCIK 35
ECLK 95
ECLK 9
ECLK
FCIK N
Tel!
ECLK o
35
Figure 5: The communication complexity performance of ECLK with the Topl compressor and p E (6/3,6, 36, 96, 1) on the mushrooms, w8a, and data sets.
Acknowledgments and Disclosure of Funding
Xun Qian and Peter Richtárik acknowledge funding by the KAUST Baseline Research Funding Scheme, the Extreme Computing Research Center at KAUST, and administrative support from the Visual Computing Center at KAUST. Tong Zhang acknowledges further funding by GRF 16201320.
10

---

References
A. Agarwal and J. C. Duchi. Distributed delayed stochastic optimization. In Advances in Neural Information Processing Systems (NIPS), pages 873-881, 2011.
D. Alistarh, D. Grubie, J. Li, R. Tomioka, and M. Vojnovic. QSGD: Commumication SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS), pages 1709-1720, 2017.
D. Alistarh, T. Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), pages 5973-5983, 2018.
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research, 18(1):8194 1944444444444,, 2017.
J. Bernstein, Y. X. Wang, K. Azizzadenesheli, and A. Anandkumar. SignSGD: Compressed optimisa- tion for non-convex problems. pages 560-569, 2018.
A. Beznosikov, Horváth, Richtárik, and M. Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002. 12410, 2020.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM
Transactions on Intelligent Systems and Technology (TIST), 2(3):127,, 2011.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging error compensated SGD. In Neural Information Processing Systems (NeurlPS), 2020.
P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Jia, and K. He. Accurate, large minibatch SGD: Training imagenet in hour. arXiv preprint arXiv: (ct::/7776677 2017.
Filip Hanzely and Peter Richtárik. Federated learning of mixture of global and local models. arXiv preprint arXiv:2002.05516 2020.
S. Horváth, D. Kovalev, K. Mishchenko, S. Stich, and P. Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint 150 2019a.
Samuel Horváth, Chen-Ye Yu Ho, L'udovít Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning, arXiv preprint 1905. 2019b.
Peter et al Kairouz. Advances and open problems federated learning. arXiv preprint arXiv:1912.04977 2019,
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. arXiv preprint arXiv:1901.098/0 2019.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In The 23rd International Conference Artificial Intelligence and Statistics (AISTATS), 2020.
Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: distributed machine learning for on-device intelligence. arXiv preprint 11010:1610 2016a.
Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi Multi-Partty Machine Learning Workshop, 2016b.
D. Kovalev, S.I Horváth, and Richtárik. Don't jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Proceedings of the 31st International Conference on Algorithmic Learning Theory (ALT), 2020.
Guanghui I Lan and Yi Zhou. An optimal randomized incremental gradient method. Matheratical programming, 171(1):67-2215, 2018.

---

Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: challenges, methods, and future directions. arXiv preprint arXiv:1908.07875 2019.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
X. Lian, Y. Huang, Y. Li, and J. Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems (NIPS), pages 2737-2745, 2015.
Chenxin Ma, Jakub Konečný, Martin Jaggi, Virginia Smith, Michael Jordan, Peter Richtárik, and Martin Takáč. Distributed optimization with arbitrary local solvers. Optimization Methods and Software, 32(4):813-88) 2017.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. Communication--fficee learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárik. Distributed learning with compressed gradient differences. arXiv preprint 1901v::901.022000 2019.
Yurii Nesterov. A method of solving a convex programming problem with convergence rate O(1/k²). Soviet Mathematics Doklady, 27 376,, 1983.
Yurii Nesterov. Introductory lectures on convex optimization: basic course (Applied Optimization). Kluwer Academic Publishers, 2004.
Xun Qian, Zheng Qu, and Peter Richtárik, L-SVRG and L-Katyusha with arbitrary sampling. arXiv preprint
2019.
B. Recht, C. Re, S. Wright, and F. Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems (NIPS), pages 693-701, 2011.
F. Seide, H. Fu, J. Droppo, G. Li, and D. Yu. 1-bit stochastic gradient descent and its application to data- parallel distributed training of speech DNNs. Fifteenth Annual Conference of the International Speech Communication Association, 2014.
U. Stich and Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv:1909.0533 2019.
S. U. Stich, J. B. Cordonnier, and M. Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NeurIPS), pages 4447-4458, 2018.
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations (ICLR), 2020.
H. Tang, S. Gan, C. Zhang, T. Zhang, and J. Liu. Communication compression for decentralized training. In Advances Neural Information Processing Systems (NeurIPS), pages 7652-7662. 2018.
H. Tang, X. Lian, T. Zhang, and Liu. DoubleSqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 6155-6165, 2019.
W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, and H. Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems (NIPS), pages 1509-1519, 2017.
Blake Woodworth, Kumar Kshitij Patel, Sebastian U. Stich, Zhen Dai, Brian Bullins, H. Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? arXiv preprint arXiv:2002.0788 07839, 2020.
12

---

J. Wu, W. Huang, J. Huang, and T. Zhang. Error compensated quantized SGD and its applications to large-scale distributed optimization. The 35th International Conference on Machine Learning (ICML), pages 5321-5329, 2018.
Y. You, I. Gitman, and B. Ginsburg. Scaling SGD batch size to 32k for imagenet training. arXiv preprint arXiv:1708.038800 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
and (b) Did you describe the limitations of your work? [Yes] We need Assumptions and
3.2 for our results.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump-
tions 2.1 3.1 and 3.2
(b) Did you include complete proofs of all theoretical results? [Yes] We include the complete proofs in the Appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Data sets are from the LIBSVM library. Code and instructions are in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [No] We used a fixed random seed to make sure the numerical
results can be reproduced.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] We run the experiments on a laptop, and we did not count the time. Hence the results independent of the amount of compute and the type of resources.
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We used the LIBSVM library and cited.
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL.? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [No]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "tWyOTdZlWM2", "reviewer": "Reviewer_5Tji", "summary": "The authors consider accelerated training algorithms using gradient compression with error compensation. For this purpose, they incorporated gradient compression and error compensation in the Katyusha algorithm and developed ECKL. The algorithm quantizes both the SG and VR term and keeps track of the quantization error for error compensation in the next iteration.\n\nThe paper analyzed the convergence rate and iteration complexity of ECKL for the smooth convex functions and compared it with variants of DIANA both theoretically and via some simple simulations on logistic regression.", "questions": "", "limitations": "", "rating": 7, "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": "The idea and algorithm developed in the paper is interesting and can be potentially useful in distributed DNN training. However, one shortcoming of the paper is its analysis.The paper only considers the class of smooth convex functions. Although for theoretical analysis, the assumptions in the paper are common and ok, but for the simulations, it would be more interesting to see how the algorithm performs for more complex cost functions, even training a simple DNN on CIFAR10 could have demonstrated the performance of ECKL in more general setting.\n\nMinor:\nFinally, the writing and notations of the paper can be improved. Some notations are used without proper definition, and some parts are missing, e.g.,\n* what is parameter $\\mathcal{L}_1$?\n* Algorithm 1, how $h_\\tau^0$ is initialized?\n* Alg. 1: $u_\\tau^{k+1}$ is always set to 0 for $\\tau=2,\\ldots,n$, and only $u_1^k$ is changing and used. It seems that worker 1 acts as the controller to decide on updating $\\omega^k$. In that sense, defining $u_\\tau^k$ looks redundant and a single shared random variable $u^k$ would be enough.\n\n____________________________\nUPDATE:\nThanks for the answers and clarifications. I updated the my recommendation accordingly. Although not necessary and having simulations on convex problems suffices for the paper, I believe that showing the performance on some non-convex problems can really add to the value of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "ZNTCdvQvAWy", "reviewer": "Reviewer_xkpw", "summary": "This paper proposed an error compensated based Katyusha method for finite-sum convex problems. The proposed method achieves the same asymptotic convergence rate as its full precision accelerated counterpart. Compared to another related work ADIANA, the proposed method can be applied to contractive compressor. ", "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": "The paper is clearly written and theoretically sound. However, I am not clear about the motivation of applying gradient compression to a finite-sum convex problems and what the real convex applications are that require gradient compression. Typically, the application requires gradient compression is the training of large deep neural networks, which is neither finite-sum nor convex. In addition, I have a few questions.\n\n1. Theoretically, how do we select Q and Q_1 that minimizes the bound given a fixed communication budget?\n2. What is the communication collective primitive used in the proposed algorithm? Since most of quantization and sparsification methods are incompatible with allreduce, it seems to me that it is all-to-all broadcast?\n3. Since the proposed method obtains an accelerated rate that has better dependency on condition number, it is good to see the experimental results with varying condition numbers. \n4. The proposed method introduces a number of hyper-parameters. How do we choose them in practice?", "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": {}}, {"review_id": "VBsa2aOsT4a", "reviewer": "Reviewer_ZXqE", "summary": "The paper introduces an error compensation variant of the loopless Katyusha, ECLK. Theoretical convergence analysis is given and accelerated linear convergence rate is obtained using contraction operators. Experimental study of ECLK is given on the logistic regression problem for binary classification.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 applys error compensation to accelerated gradient methods, and introduces error compensated loopless Katyusha method. Convergence analysis is given of ECLK with contraction operators, and compared to ADIANA with unbiased compressor. Experimental results are given for binary classification with ECLK with three contraction compressors, and compared with other methods in literature. \n\nThe paper is clearly written and well organized.\n\n**Update**: Thanks for the authors' response to the reviews. It helps with the clarification after reading the responses to all the reviewers.\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": "2iYfh49rDYm", "reviewer": "Reviewer_iBtS", "summary": "This paper considers communication efficient algorithms for SGD. In this model, there are $n$ total workers and each worker has a local smooth convex loss function $f_i$ on $R^d$. The objective is for a coordinator to find an approximate global minimum for an objective function that represents the average loss across all workers while minimizing communication between the workers and the coordinator. \n\nA common approach is for each worker to compute a sketch on their local batch of gradients that allows the coordinator to recover of the top $k$ gradients in magnitude, ideally improving the rate of convergence. However, the challenge with this approach is that the estimator formed by the coordinator using the sketches sent from the workers may not be an unbiased estimator of the overall gradient, which allows error to accumulate over multiple iterations. This paper introduces provable accelerated gradient-methods, in the sense of Nesterov momentum for contractive compressors, which are a general class of stochastic functions that form estimators of the gradient, including the top $k$ estimator. ", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "It seems the algorithm performs the usual uniform sampling technique to acquire a batch of gradients for each step. The algorithm then applies a contractive compressor in the standard way to improve communication efficiency over naive SGD. To address the bias incurred by the contractive compressor, the algorithm attempts to learn the added bias and subtract the bias incurred from the previous iterate before using a standard proximal operator to update the current iterate.\n\nI believe existing approaches that achieve communication efficient SGD also use this framework to deal with error accumulation and feedback, e.g., FetchSGD [RPU+20] also achieves acceleration though it seems the convergence rate is better in this paper. What is the algorithmic novelty that allows the improved convergence rate? This should perhaps be clarified in the paper. \n\nThough the theoretical contributions of the paper seem very relevant to the machine learning and stochastic optimization communities, I think the exposition of the paper could be greatly improved in general. For example, I think discussion or comparison to related works or techniques are sometimes overlooked [IRU+19, RPU+20] or too brief [KRSJ19]. I also think the current text description does not give enough intuition for the main algorithm. \n\n[KRSJ19] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, Martin Jaggi: Error Feedback Fixes SignSGD and other Gradient Compression Schemes. ICML 2019: 3252-3261\n\n[IRU+19] Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Vladimir Braverman, Ion Stoica, Raman Arora:\nCommunication-efficient Distributed SGD with Sketching. NeurIPS 2019: 13144-13154\n\n[RPU+20] Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, Raman Arora: FetchSGD: Communication-Efficient Federated Learning with Sketching. ICML 2020: 8253-8265", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not think there are any limitations and potential negative societal impact of their work that the authors need to address. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "2NwaHTKpLn", "reviewer": "Reviewer_XZRR", "summary": "This paper presents accelerated methods for communication-efficient learning applications. In particular, a loopless Katyusha strategy is introduced to attain the O(\\sqrt{L/\\mu}) rate for error-compensated methods using stochastic gradient information. These methods are called ECLK. In terms of theoretical iteration complexity and empirical experiments, ECLK is explicitly shown to be more communication efficient and to have a better rate than existing error compensation methods.", "questions": "", "limitations": "", "rating": 7, "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 is clearly written. The simulation results highlight the impact of algorithmic tuning parameters, and the superior performance of ECLK over non-accelerated error-compensated algorithms. However, there are some concerns presented below: \n\n* The authors claim that ECLK performs better than EC-LSVRG-DIAN but worse than ADIANA, in theoretical iteration complexity. However, to compare these complexities, Lyapunov functions associated with these methods are totally different. The Lyapunov function for ECLK is the summation of the Euclidean distance and the function difference, while the Lyapunov function for EC-LSVRG-DIANA and ADIANA is only the function difference. Therefore, comparing the complexities with different Lyapunov functions seems to weaken the authors' claim.\n* Literature review related to this work is in Section F in the supplementary materials. This approach leads to weak discussions of error compensation in the introduction. This literature review in Section F should be included rather in the introduction. \n* This paper lacks the motivation on why Katyusha is used as the acceleration technique, instead of Nesterov's acceleration. It will be better if the authors also include literature review about this technique.\n* One section in numerical experiments highlights that ECLK is comparable to ADIANA that uses non-compensated information for most cases in deterministic settings. This raises the question why the authors instead consider the extension of ADIANA for error-compensated methods. In addition, what happens in stochastic settings? Since Katyusha, unlike Nesterov's acceleration, guarantees the fast rate for the methods to solve stochastic optimization, ECLK may be expected to outperform ADIANA and error-compensated algorithms with Nesterov's acceleration. This will strengthen the authors' contributions. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The contribution of this paper is primarily theoretical. Therefore, limitations and societal impacts are not applicable. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["Discrimination / Bias / Fairness Concerns", "Inadequate Data and Algorithm Evaluation"], "time_spent_reviewing": "4"}, "extra_text": {"ethical_concerns": "Ethical concerns in terms of methodology are addressed by the authors. For instance, python codes are provided for the reviewers to re-run the experiments on the benchmark data where its source was available and properly cited. "}}]

Author rebuttal:

Meta-review: Overall, this paper addresses an important open problem. It is well-written, and solid theoretical results are complemented by distinct advantages in simulation experiments.

Based on my own reading, and the comments of the reviewers, I recommend acceptance. 

There are some weak points that should be improved in the camera ready version.

The abstract and part of the introduction are a little bit misleading, referring to Nesterov’s acceleration (easily mistaken for Nesterov’s accelerated gradient method), while the algorithm later uses Katyusha (another acceleration technique).

The writing is a bit too dense, with little exposition on how the algorithm works and how it is related to previous work. In the response to the reviewers, you claim that this is not an issue and it does not matter if you put material in the main text or the appendix. I disagree. The main text should be complete and accessible to a broader audience than researchers in error-compensated training algorithms. I believe that parts of the related work from the appendix need to be moved into the main text and that you need to expand on how the algorithm works, and how its parameters are selected. In the response to the reviewers, you share such intuition and describe parameter tuning techniques. This knowledge should also make it into the main document.

Finally, I also believe that you can clarify in what environment you perform your experiments. I see the main contribution of this paper as mainly theoretical, but you do talk about “nodes” in your experiments, and “send” and “receive” in your algorithm. To me, it is perfectly fine if you have made the experiments in a Python/Matlab/C++… simulation where send and receive operations are instantaneous and error-free. But you should be clear with this in the paper.
Decision: Accept (Poster)