Global Momentum Compression for Sparse Communication in Distributed SGD
Authors: Shen-Yi Zhao
Yin-Peng Xie
Hao Gao
Wu-Jun Li
Venue:  (2020)
Keywords: Distributed momentum SGD
Communication compression

Abstract: With the rapid growth of data, distributed stochastic gradient descent~(DSGD) has been widely used for solving large-scale machine learning problems. Due to the latency and limited bandwidth of network, communication has become the bottleneck of DSGD when we need to train large scale models, like deep neural networks. Communication compression with sparsified gradient, abbreviated as \emph{sparse communication}, has been widely used for reducing communication cost in DSGD. Recently, there has appeared one method, called deep gradient compression~(DGC), to combine memory gradient and momentum SGD for sparse communication. DGC has achieved promising performance in practice. However, the theory about the convergence of DGC is lack. In this paper, we propose a novel method, called \emph{\underline{g}}lobal \emph{\underline{m}}omentum \emph{\underline{c}}ompression~(GMC), for sparse communication in DSGD. GMC also combines memory gradient and momentum SGD. But different from DGC which adopts local momentum, GMC adopts global momentum. We theoretically prove the convergence rate of GMC for both convex and non-convex problems. To the best of our knowledge, this is the first work that proves the convergence of distributed momentum SGD~(DMSGD) with sparse communication and memory gradient. Empirical results show that, compared with the DMSGD counterpart without sparse communication, GMC can reduce the communication cost by approximately 100 fold without loss of generalization accuracy. GMC can also achieve comparable~(sometimes better) performance compared with DGC, with an extra theoretical guarantee.

Under review as a conference paper at ICLR 2020
GLOBAL MOMENTUM COMPRESSION FOR SPARSE COMMUNICATION IN DISTRIBUTED SGD
Anonymous authors Paper under double-blind review
ABSTRACT
With the rapid growth of data, distributed stochastic gradient descent (DSGD) has been widely used for solving large-scale machine learning problems. Due the latency and limited bandwidth of network, communication has become the bottleneck of DSGD when we need to train large scale models, like deep neural networks. Communication compression with sparsified gradient, abbreviated as sparse communication, has been widely used for reducing communication cost in DSGD. Recently, there has appeared one method, called deep gradient com- pression (DGC), to combine memory gradient and momentum SGD for sparse communication. DGC has achieved promising performance in practice. However, the theory about the convergence DGC is lack. In this paper, we propose a novel method, called global momentum compression (GMC), for sparse commu- nication in DSGD. GMC also combines memory gradient and momentum SGD. But different from DGC which adopts local momentum, GMC adopts global mo- mentum. We theoretically prove the convergence rate of GMC for both convex and non-convex problems. To the best of our knowledge, this is the first work that proves the convergence of distributed momentum SGD (DMSGD) with sparse communication and memory gradient. Empirical results show that, compared with the DMSGD counterpart without sparse communication, GMC can reduce the communication cost by approximately 100 fold with no loss of generaliza- tion accuracy. GMC can also achieve comparable (sometimes better) performance compared with DGC, with an extra theoretical guarantee.
INTRODUCTION
Many machine learning models can be formulated as the following empirical risk minimization problem:
min F(w) ;= 1 Σ E(w
wERdd
where w denotes the model parameter, &, denotes the ith training data, n is the number of training data, and is the size of the model. For example, let & = (a,, y:), where a; denotes feature
of the vth training data and Ye denotes the label. Then in logistic regression f(w; = log(1 +
evvaa" w) + À // and in SVM f(w; E,) max(0, y.a w) + À [|] Many deep learning models can also be formulated as
One of the efficient ways to solve [ is stochastic gradient descent (SGD) (Robbins Monro 1951.. In each iteration, SGD calculates one stochastic gradient V {i) and updates by w w w- v (W(;;; {,), or updates w with a mini-batch of stochastic gradients. Inspired by momentum and nesterov's 's accelerated gradient descent, momentum SGD (MSGD) (Polyak (Teeng 1998 Lan
2012 Kingma Ba 2015) has been proposed and widely used machine learning. In practice,
MSGD can achieve better performance than SGD (Krizhevsky al. 2012 Sutskever et al. 2013). Many machine learning platforms like TensorFlow, PoTchh, and MXNet adopt MSGD as one of the optimization methods.
With the rapid growth of data, distributed SGD (DSGD) (Dekel et al. 2012 Li et al. 2014b) has attracted much attention since it can parallelly caleulate batch of stochastie gradients. DSGD can

---

Under review as a conference paper at ICLR 2020
be formulated as follows:
?t
W++1 Wt
gt,
where p is the number of workers, &t. is the stochastic gradient mini-batch of stochastic gra- dients calculated by the kth worker at the /th iteration. DSGD can be implemented on distributed frameworks like parameter server and all-reduce framework. Each worker calculates gr, and sends it to the server or other workers for updating w. Recently. more and more large models, such as deep learning models, are used in machine learning to improve the generalization ability. In large models, ge, is high dimensional vector. Due to the latency and limited bandwidth of network, commu- nication cost has become the bottleneck of traditional DSGD or distributed MSGD (DMSGD). For example, when we implement DSGD on parameter server, the server needs to receive p high dimen- sion vectors from workers, which will lead to communication traffic jam and make the convergence of DSGD slow. Hence, we need to compress gr, to reduce the communication cost.
Recently, researchers have proposed two main categories of communication compression techniques for reducing communication cost in DSGD and DMSGD. The first category is quantization (Wen al. 2017 Alistarh et al. 2017 Jiang & Agrawal 2018). In machine learning problems, 32-bit float number is typically adopted for representation. Quantization methods quantize the value (gradient or parameter) representation from 32 bits to some low bit-width like 8 bits or 4 bits. Since the quantized gradients in most methods are unbiased estimation of the original ones, the convergence rate of these methods has the same order of magnitude as that of DSGD, but slower due to the extra quantization variance. It is easy find that the communication cost can be reduced by 31 fold in the ideal case. In practice, at least 4 bits should be adopted for representation in most cases to keep original accuracy. In these cases, the communication cost is reduced by 7 fold.
The other category is based on sparsified gradient, which is called sparse communication. In sparse communication, after calculating the update vector gr. at each iteration, each worker only sends a subset of coordinates in gr.k. denoted as S(gr,)), to the server or other workers. Here, S(g,,s is a sparse vector and hence it can reduce the communication cost. In recent works (Aji & Heafield, 2017 Lin et al., 2018), each worker will typically remember those values which are not sent to the server, i.e., & S(gr,)) ). and store in the memory rather than dropping them. The gr, - S(g..) is called memory gradient and will be used to calculate the next update vector gt+1,k. This is intu- itively necessary because a subset of coordinates the stochastic gradient can not reflect the real descent direction and can make errors with higher probability than the original stochastic gradi- ent. This memory gradient based sparse communication strategy has been widely adopted by recent communication compression methods and has achieved better performance than quantization meth- ods and other sparse communication methods without memory gradient. In these memory gradient based sparse communication methods, some are for vanilla SGD AAji Heafield 2017: Alistarh ct al. 2018 Stich et al., 2018; Karimireddy et al., 2019 Tang et al.. 2019). The convergence rate of vanilla SGD with sparse communication has been proved in (Alistarh et al. 2018 Stich al.) 2018
Karimireddy et al. 2019: Tang et al. 2019). Very recently, there has appeared one sparse commu- nication method for distributed MSGD (DMSGD), called deep gradient compression (DGC) (Lin al., 22118), which has achieved better performance than vanilla DSGD with sparse communication in practice. However, the theory about the convergence of DGC still lack. Furthermore, although DGC uses momentum SGD, the momentum in DGC is calculated by each worker. Hence it is local momentum without global information.
In this paper, we propose novel method, called global momentum compression (GMC), for sparse communication DMSGD which includes DSGD as a special case. The main contributions of this paper summarized as follows:
GMC combines memory gradient and momentum SGD to achieve sparse communication in DMSGD (DSGD). But different from DGC which adopts local momentum, GMC adopts global momentum.
We theoretically prove the convergence rate of GMC for both convex and non-convex prob- lems. To the best of our knowledge, this is the first work that proves the convergence of DMSGD with sparse communication and memory gradient.
2

---

Under review as a conference paper at ICLR 2020
Empirical results show that, compared with the DMSGD counterpart without sparse com- munication, GMC can reduce the communication cost by approximately 100 fold with no loss of generalization accuracy.
GMC can also achieve comparable (sometimes better) performance with comparable com- munication compression ratio, with an extra theoretical guarantee.
PRELIMINARY
In this paper, we use || to denote L2 norm, use w' to denote the optimal solution of (1. use f[(w:I) [ ExEz V ff(w:)) to denote stochastic gradient with respect to mini-batch of samples I such that E /[ I)
(Ww), use @ denote element-wist wise product, use 1 to denote the vector (1, ..... 1)² Rd use ej to denote the vector (O,..., ..... 1,............ 0)² E Rd with only a to denote
the jth coordinate being 1, use I denote identity matrix. For vector a, its jth coordinate value. ||aloo denotes the number of non-zero values in a.
Definition (smooth function) Function h(.) is L-smooth (L 0) if Vw, w',
L
1h(w) h(w')((w)))) Vh(ww) (w w 1 ww w'l?
Definition 2 (convexfuncttinn Function h(.)) is convex if V/w, w',
[h(w) h(w') Vh(w') w セリ w w/1
where μ 2 1f h(-) is called je-strongly convex finction..
2.1 DISTRIBUTED MOMENTUM SGD
The widely used momentum SGD (MSGD) (Polyak) 1964) for solving [ can be written as
g: =8 1 + V Iww
W++1 =. gr
where 3 (0. The gi is the Polyak's momentum and V (w(; is unbiased estimation of F(,,)) Since g: = (w; W,+1), MSGD can also be written as
Wi+1 W 7/ (V + V)
(Wi-1 w:)).
(3)
Please note that B MSGD degenerates to SGD.
One simple way to implement distributed MSGD (DMSGD) is that each worker parallelly calculates some stochastic gradients and then the stochastic gradients of all workers are aggregated to get ff(W;;; + 3 ([w.-1 w.)/n- The update process of w in this way is equivalent to the serial MSGD. We call (w,-1 w.)/n, the global momentum, because it captures the global information from all workers.
Another way to implement DMSGD using local momentum:
gi, =Bg; + JcV., k 1,2,...,P.
W++1
Bik.
where Ve.k the stochastic gradient calculated by the ktth worker and Eb VL. = Vf(w;; gc-1,k is the local momentum. Since Σh= g:-1.k (W,-1- Wt). this DMSGD with local mo- mentum can also be written the formulation in (3). Hence, the global momentum contains all information of the local momentums. We will find that DGC (Lin et al.) 2018 is mainly based on the local momentum while GMC is mainly based the global momentum. Hence, each worker in DGC cannot capture the global information from its own local momentum, while that GMC can capture the global information from the global momentum even if sparse communication is adopted. In the later section, we will see that global momentum is better than local momentum when using memory gradient for sparse communication.
3

---

Under review as a conference paper at ICLR 2020
Algorithm Global Momentum Compression (GMC) on Parameter Server
1: Initialization: p workers, W-1 Wo. 3 [0, 1), batch size b;
2: Set go,A 4g 0 ,,...,P,
3: for t 00 1, 2.. do
4: Workers:
5: for k = ,,2...,P.. each worker parallelly do
6: if then
7: Receive w, W,-1 from the server;
8: Get w. by W, W + (w, Wi-1); end if
9:
Randomly pick mini-batch of training data Ie,:: S Dr. with [[,,
11:
Sr. = Le,EI,, Vf(we;
(w: wi-1);
12:
Generate sparse vector me, E 10,
13:
Send m @ (gi. + u) to the server,
U1+1k
m @ (gr u.,)):
15:
end for
Server:
17: Wi+1
E k= m O (gr, + uc W; to workers;
18: Send Wt+1
19:
end for
3 GLOBAL MOMENTUM COMPRESSION
Assume have workers. Dy denotes the data stored on the kth worker (k: 1, ... Uh DE (2.. Our method Global Momentum Compression (GMC) mainly per- forms the following operations iteratively:
1........ p and
Each worker calculates gr, pb EgeEt, V.(w:
pi (w. (e--w-1). where It,k S Dr
and [Z,a| b;
Each worker generates a sparse vector m and sends m,, ④ (gi. + (z.k) to the server other workers;
Each worker updates U4+1, (1 m(,k) (gr, u.,k);
Update parameter We+1 W: 1)t Ei=1 m (gr u.,:);
Below, we introduce the framework and two essential elements of GMC: memory gradient u,, and global momentum (W:-1- w.)/nt.
3.1 FRAMEWORK OF GMC
GMC can be easily implemented on the all-reduce distributed framework in which each worker sends the sparse vector m, @ (g,, à + u, to all the other workers, then each worker updates W after receiving the sparse vectors from other workers.
Recently, parameter server (Li et al. 2014a) has been one of the most popular distributed frameworks machine learning. GMC can also implemented on parameter server. Although the theories in this paper can be adopted for the all-reduce framework, in this paper adopt parameter server for illustration. The details of GMC implemented on parameter server are shown in Algorithm| [ The difference between GMC and traditional DSGD on parameter server is that in GMC after updating Wi+1, server will send Wt+1 Wt, rather than W++1, to workers. Since m,,k is sparse, Wt+1 W; sparse as well. Hence, sending Wx+1 w, can reduce the communication sending w.. In our experiments, we find that GMC can make |Wr+1 wello < 0.01d with no loss of accuracy when training large scale models. Workers can get W by W w, (W141-
compared with
Remark We can also use the sparse communication technique the server (denoted GMC") to make (W++1- - w,) sparser than that in GMC so that when the server sends W -w, to workers, the communication cost be further reduced, compared with GMC. The convergence of GMC
4

---

Under review as a conference paper at ICLR 2020
can also be theoretically proved. But in practice, GMC will be slightly worse than GMC in terms of accuracy. Due to the space limitation, we move both theory and experiments about GMC* to Appendix A
3.2 NECESSITY OF MEMORY GRADIENT
In GMC, after sending a sparse vector M,, @ (gr. + ur,x) to the server, each worker will remember the coordinates which are not sent and store them in U,+1
1,+ (1 m.,k) @ (gr, + U,,k))
(4)
Hence we call & the memory gradient, which is important for the convergence guarantee of GMC. Here, we give an intuitive explanation about why GMC needs to remember the coordinate values which not sent. We consider the simple case that
0, which means gr, is stochastic gradient of F(w) and GMC degenerates to (Aji & Heafield 2017). Since mi, is a sparse vector, GMC can be seen method achieving sparse communication by combining stochastic coordinate descent (SCD) (Nesterov) 2012) and DSGD. In SCD, each FF(() denotes true descent direction. When we use stochastic gradient V f (w; replace VF(w), (Vf(w; Z) e, will make errors with high probability, especially when m,,k adopts the strategy that choosing coordi- nates with the largest absolute values (denoted as top-s strategy).
For further explaining the importance of memory gradient. we consider the following simple ex- ample: let n = p 2, f(w: [-,,0], 0 < < a < < a + f(w: (1) is on the first worker and f(w; is on the second
(-a, e)w, (w: (2) (a e, 7,7),, where
[-1,0] x
worker. Then we rum GMC with B == solve min F(w)= = (f(:;; f( f(w; The optimal
solution is w = (-1,-11) We adopt the top-1 strategy for m2,s in this example.
If we do not use the memory gradient, which means each worker directly sends m @ gr. to the server, then the two workers will send (-a/2, 0)2 and ((a + e)/2, 0)² respectively to the server. The parameter is updated by w <- w-nn (e /2. 0). We observe that (2) will never be updated. This due to the pscudo large gradient value which cheats my,k- Since VF(w) = (c/2, (7 + e)/2)², can that the second coordinate has the true large gradient value and we should have mainly focused on updating (2). However, in the two stochastic gradients V ff(w; {i) and ff(w; E2), the first coordinate has larger absolute value. Hence, V [ Ex) cheats M2 which leads to the error.
If we use memory gradient, at the beginning, m = m (1, After some iterations, m (0, 1) and m, (0, 1)" due the memory gradient. Specifically, let f be two integers satisfying a/c < t < a/c + 1. (a c)/r/ < tz < (a c)/7 + 1, then it is easy to verify that m = (0, 1)", Met2,2 (0, 1)", Vc 2 1. It implies that we use the memory gradient, both (1) and (2) will updated. Hence, GMC can make w converge to the optimum (-1,-1)2
Hence, the memory gradient is necessary for sparse communication. It can overcome the disadvan- tage of combining DSGD and SCD.
3.3 BENEFIT OF GLOBAL MOMENTUM
In GMC, each worker calculates gr.k
B (w, pTp
gi.k
Σ Vf(w;:))) E.ET,
w,-1).
(5)
pb
When B = 0, it degenerates to DSGD with sparse communication, which is also called gradient
dropping in (Aji & Heafield 2017). We use gi to denote this degenerated version with 8 0. We can see that GMC uses the global momentum (w,-1- 10-1-Wi -w,)/n. While in DGC (Lin al. 2018
(DGC) is calculated by the gi,k
(DGCC gr.
Σ Vf(we()) + ( S,
(6)
pb
which uses the local momentum
gi-1,
(DGC)
We use u
(DGC) denote the memory gradient in DGC.
5

---

Under review as a conference paper at ICLR 2020
(DOC) only contain the information based the (boc) and urkk For sparse Mr,k. we can find that Bi.k local data, while Br, and 44 contain the global information due the global momentum. Hence, global momentum is better than local momentum when using memory gradient for sparse communication. Assume that (w;) converges to F(w"), then w; w,-1 denotes the descent direction with high probability. Since I, C Dx. which only contains partial information of the whole training data, the global momentum (WN-1 wr)/m, /ft can make compensation for the error between the stochastic gradient and the full gradient. Specifically, if (We (VV then we get that
2 0,
B (wc w(-))) pi
gi,k VF(W))
=(
E Vf(WniE))
pb EiEIe,k
Vf(wiiE)
pb E
= = ) VTW)).:)
implies that gi,k better estimation of (F((,) than gi,k The experiments in (Lin et al, 2018) also show that (Aji & Heafield (017)) has some loss of accuracy with ||m llo as 0.001d, while set such sparsity for GMC with no loss of accuracy in practice. Hence, GMC is better than (Aji & Heafield, 2017)
Remark There are some other ways to combine global momentum and memory gradient. For example, we can put the global momentum on the server. However, these ways lead to some loss of performance, More discussions are put in Appendix B
CONVERGENCE OF GMC
In this section, we prove the convergence rate of GMC for both convex and non-convex problems. The detailed proofs are put in Appendix C We define diagonal matrix M, E Rdxd such that diag(Me,k) m to replace the symbol C. Then we obtain
Wi41 =
M. + ur,)),
(7)
k=1
U++1A =(I ().MM.))(..k + u.,k), = 1,2,...,P
(8)
For convenience, we denote [)( = pb Ei=l EqeIIa VS(((: ún = Eh=1 Ur 8:
Ek Bt,-- By eliminating Mr,k- obtain
W++1 =W - 7/ ((w + 8(w, - wt-1) - ūu + 7-4.11
(9)
We can find that if we do not use the sparse communication technique, then ú, = 0 and 9 is the same as momentum SGD in (3).
First, we give the following lemma:
3 Lemma Let Wr + T-B (we W:-1) T-3 ü. Then we have;
Mt v IZW
+ no 71+1
X++1
1- Ú
(10)
Equation 10) is similar to the update equation in SGD except the additional term ú,+1- Inspired by this, we only need prove the convergence of x, and ||x; well. To get the convergence results, we further make the following three assumptions:
Assumption (bounded gradient) E V / S G2, VL.
Assumption (bounded memory) B ú 2| U2, Vt.
Assumption (bounded parameter) El|x, 1/ D2 VL.

---

Under review as a conference paper at ICLR 2020
Remark 3 Assumption is common in stochastic optinization. Assumption 2 is easy to be guar- anteed. We discuss it in Appendix [ Assumption is only for convenience in the analysis for strongly convex and convex cases. We can add one projection operation on Equation 7 to guaran- tee Assumption rif both W, and ú, are bounded, X is bounded as well), which can be written as Wt+1 [Tg(w: w. ?) > Mr, (gr, u.) The convergence can still be guaranteed if the projection operation. More details are put in Appendix E
For the new variable x; in Lemmal the gap between X; and we has the following property:
Lemma 2 With Assumption 1 and Assumption 2
get that
mh = 17. then
X, w. s $ 91-
222 + 2U2
20
(1 - 9)2 (1- 1
(11)
nf (1tp):: E [0.5, 1|,r,, 0, 2 0, then
28 + 20 max (1-)
2U
Bl|x: - well? <
Wh.
(12)
3)
(1 - 1--
where A = max 1=0 ( +nm 4.3 }. to satisfies (a+2+4
2p
2
14.8
2
Lemma 2 implies that E||x; w S O i.c. the distance between X and w. is O For convenience, below we use the constant Cr..p.l. denote the upper bound of E||x; - w. 1/ll2/12
r = O, Cr.q..99.n denotes the upper bound in (TT) and if = 0, Cr.g.p... denotes the upper bound Then we have the following convergence results:
12
Theorem
(strongly convex case) Let F(-) be L-smooth and p-strongly convex. With Assumption 1 Assumption
Assumption
and T) "(t+1)' m [T/2]], we obtain
1
B(F(wL) - F(w")) 3A4 + 2G 2 CC- (01-0//a11.88011 Tm
171
where A m D2, 2(1 B) C + μUD + 2G 282).
Theorem
(convex case) Let F(-) be a convex function. With Assumption and Ttt = 1-8
Assumption 2 As-
sumption
V we obtain
T
2
E(F(w:) F((")() $ |Wo - 1² + A Alog(T),
Vt Vt+1
0=
where 1 2(1 B) C1B.11005,..0. + D + 2G + 2
Since Σ 1 = O(VT), Theorem implies that if the objective function convex, GMC has vナ+T
a convergence rate of Ollo(())/VT)
Theorem (non-convex case) Let F()) be L-smooth. With Assumption) 7 being constant, we obtain
Assumption 2 and π) =
1
F(wo) - F(w") + An,
E
V FVF((:
(1 B)T
T'
where A
LG LG Co.0
LG 2(--))
1-3
By taking 7 = O(IVTT), it is easy to find that GMC has a convergence rate of O(1/VT), the objective function non-convex.

---

Under review as a conference paper at ICLR 2020
5 EXPERIMENTS
We conduct experiments on a PyTorch based parameter server framework with one server and eight workers. Each worker has access to one TITAN Xp GPU. We compare GMC with distributed momentum SGD (DMSGD) and DGC. In the experiments of (Lin et al. 2018), DGC gets far better performance both accuracy and communication compression ratio than quantization methods. Hence, we do not compare with quantization methods in this paper. We use warm-up strategy (run DMSGD 5 epochs) for both GMC and DGC. The momentum factor masking trick is used in DGC. The 3 is set as 0.9. In our experiments, we consider the communication cost on the server which the busiest node. includes receiving vectors from the p workers and sending one vector to the p workers. So the cost of DMSGD is 2pd. In GMC and DGC, since m is sparse, workers send the vectors using the structure of (key, value). The cost of each (key, value)
2. Server sends
W++1 using this structure as well. Hence, the cost of GMC and DGC is 2(2 kmm ||m,,&ll llo + pl| W|+1 - -wllo). We define the communication compression ratio (CR) of GMC and DGC as:
T+4 Σ E= pd
1
CR
(pll -weloo +
|mc,ello..
T
A=
The CR of DMSGD is 100% (no compression). Here, all numbers have the same unit (float value).
5.1 CONVEX MODEL.
We use the dataset MNIST and the model logistic regression (LR) to evaluate GMC on convex problems. Since the sizes of dataset and model are small, m, directly adopts top-s strategy with |mm,ello- = where s = 0.01d or 0.001d. We use 8 workers for this experiment. The weight decay 0.0001 and total batch size is 128. The result is shown in Figure [ We can see that GMC gets similar performance DGC and DMSGD.
0.30
DGC, --8.idd
92.8
133
+0.001
DMSGD
5432
=0.014
DGC, +-8.1d
GMC, -00.001
DGC, 8.0004
424
GMC, ro00
02b
90.
GMC, s0000d
Epock
Epech
Figure 1: Comparison on convex model. The CRs DGC with s = 0.01d and 0.001d are 7.87% and 0. 0.797% respectively. The CRs of GMC with = 0.01d and 0.001d are 8.0% and 0.797% respectively.
5.2 NON-CONVEX MODEL
For large models, we use the approximate top-s strategy for m given a vector a, we first randomly choose subset S C {1...., d} and |S] is 0.001d 0.01d. We get the threshold such that | > 0,j E SH = 0.001|SS) Then we set m,, by choosing the indexes in (il(a(5 > 0, 1,2, d). It implies that ||m,, llo is approximately 0.001d.
First, we use the dataset CIFAR-IO and three popular deep models (AlexNet, ResNet20, ResNet56) to evaluate GMC on non-convex problems. We use both 4 and 8 workers with the total batch size 128. The weight decay is set as 0.0001. Figure shows the learning process about training loss and test accuracy of the three methods. We can find that GMC and DGC have the same performance as that of DMSGD on ResNet20 and ResNet56. Compared to the two residual networks, AlexNet has more parameters. We see that GMC also gets the performance as that of DMSGD and is slightly better than DGC, Table [ the finial training results of the three methods. Compared with DMSGD, GMC can reduce the communication cost by more than 100 fold with no loss of accuracy. This is far better than those quantization methods. Furthermore, GMC achieves slightly better accuracy with comparable communication compression ratio, compared with DGC.
We also evaluate GMC on larger dataset ImageNet and larger model ResNet18. We use workers with total batch size 256. The weight decay is set 0.0001. In Figure 3 GMC gets the same
8

---

Under review as a conference paper at ICLR 2020
AlrSNzt 407Ptx
Abshe 412Pts
Atrelis EPPI
RCPEI
DMSGD
DMSGD
DGC
DGC
1.35
GMC
GMC
THEt ACRRPAC
8.75
IMSGD
DMNGD
DGC
DGC
025
035
131
kpach
Speck
1.15
HedNetoo 4GP
RoNeoR GPPU
ReNNaa & GPU:
RoNota, EGPU
DASGD
1.4
DMSGD
1.35
DGC
THe ANNERY
GMC
81.8
GMC
1.40
DMSGD
DGC
DOC
0.5
0.60
0.8
Fpach
Fpech
Speck
1.75
1.75
DGC
DGC
GMC
Ted MOURO
1.00
DMSGD
DMSGD GMC
0:5
GMC
38
60
193
126
140
18) 138 180 160
106 133
141
140
20
68
30
100
139
141
160
Figure 2: Learning process of using different non-convex models and workers on CIFAR10.
AlexNet
ResNer20
ResNet56
GPU
Method
Accuracy
CR
Accuracy
CR
Accuracy
CR
DMSGD
75.76%
100%
91.93%
100%
93.23%
100%
4
DGC 75.67%
0.48%
91.35%
0.37%
93.08%
0.47%
GMC
76.10%
0.48%
91.97%
0.36%
93.23%
0.46%
DMSGD 76.08%
100%
91.79%
100%
93.47%
100%
8
DGC
75.42%
0.87%
91.80%
0.66%
93.26%
0.84%
GMC
76.19%
0.85%
91.98%
0.64%
93.43%
0.81%
Table 1: Experimental results CIFARIO.
test accuracy as that DMSGD during the learning process. Table 2 shows that compared with DMSGD, GMC can reduce the communication cost by more than 100 fold with loss of accuracy and save about 40% of training time. Compared with DGC, GMC achieves slightly better accuracy with comparable communication compress ratio.
ImageNet, GPEs
Method
Time (second/epoch)
Accuracy
CR
Accuracy
DMSGD
2536
69.79%
100%
50
DGC 1496
69.57%
0.84%
GMC
1495
69.88%
0.82%
DMSGD
DGC
GMC
Table 2: Experimental results on ImageNet.
28
40
60
$0
Epach
Figure 3: Learning process.
CONCLUSION
In this paper, we propose a novel method, called global momentum compression (GMC), for sparse communication in DMSGD (DSGD). To the best of our knowledge, this is the first work that proves the convergence of DMSGD with sparse communication and memory gradient. Empirical results show that GMC can achieve state-of-the-art performance.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pp- 440-445, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD:
communication--ffiiien SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1707-1718, 2017.
Dan Alistarh, Torsten Hoefter, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, pp. 5977-5987, 2018.
Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13:165-203 2012.
Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances Neural Information Processing Systems, pp. 2530- 2541, 2018.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In Proceedings of the 36th International Conference on Machine Learning, pp. 3252-3261, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, 2015.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, pp. 1106-1114, 2012.
Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Program- ming, 133(1-2):365-397 2012.
Mu Li. David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. In Proceedings of the 11th Symposium Operating Systems Design and Implementation, pp. 583-598, 2014a.
Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J. Smola. Efficient mini-batch training for stochastic optimization. In Proceedings of the 20th International Conference on Knowledge Dis- covery and Data Mining, pp. 661 2014b.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In Proceedings of the 6th International Conference on Learning Representations, 2018
Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems.
SIAM Journal on Optimization, 22(2):341-36,, 2012
Boris Polyak. Some methods speeding up the convergence of iteration methods. Ussr Computa- tional Mathematics and Mathematical Physics, 4:1-17, 12 1964.
Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22:400-407, 1951.
Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems, pp. 4452-4463, 2018.
Ilya Sutskever, James Martens, George E. Dahl, and Geoffrey E. Hinton. On the importance of ini- tialization and momentum in deep learning. In Proceedings of the 30th International Conference Machine Learning, pp. 1 1149,1147, 2013.
10

---

Under review as a conference paper at ICLR 2020
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pase caable-psssaae cror-compensated compression. In Proceedings of the 36th International Conference Machine Learning, pp. 6155-6165, 2019.
Paul Tseng. An incremental gradient(-projection) method with momentum term and adaptive step- size rule. SIAM Journal on Optimization, 8(2):506-531, 1998.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients reduce communication distributed deep learning. Advances in Neural Information Processing Systems, pp. 1508-1518, 2017.

---

Under review as a conference paper at ICLR 2020
A USING SPARSE COMMUNICATION ON SERVER
we use the sparse communication technique on the server, the update for wy can be written as:
We+1 = - -/ O
m @ (gr, ue + Ad),
(13)
Up-1, =(1 m @ gg. u. ..P.....P..
(14)
A++1 =(1 ax)
Σ m O (gr, u.A)) Ae),
(15)
where gr, is the same that in GMC. We call this method GMC The me, and a are generated by the worker and server respectively. The u,,k and A, are the memory gradients on the worker and server respectively. We can call u the local memory gradient and D, the global memory gradient. Details are presented in Algorithm
Algorithm GMC
1: Initialization: p workers, W-I = Wo, 8 E [0, 1), batch size b;
2: Set go.k Ug. Ag k ......p.
3: for tr = 0, T.. do
4: Workers:
5: for 6==1, 1,2....., each worker parallelly do
6: if then
7:
Receive Wi-1 from the server;
8:
Get w, by w. = W,-1 + (w, - w.-1); end if
9:
10:
Randomly pick a mini-batch of training data IG, S Dr with [T,
11:
gr,6 E Vf(w;;;)) pm
8 (w: wr-1);
12:
Generate sparse vector my E {0,
13:
Send m C (gi, + k),k) to the server;
14:
U,+1, =0 m.,k) @ (gi + u.,)):
15:
end for
16:
Server:
Generate sparse vector a {0, 1jd.
18:
WL+1 W, 1,a, @ 1= m @ (g. + u.,)) + Ad]:
19:
A++1 = (1 a,) @ D my @ (gi, + u.,)) + A.]
20:
Send Wx+1 W: workers;
21:
end for
We eliminate m a, and obtain
p
Wi+1 - 17p A111 =W; - mp
mi O (gr, + = + Ar]
A=1
=W ng 18:10 ū ú+t1 + Ar]
By denoting h; ûr + A,, we obtain
W 7), h, W. n, 1/: Vf(w,; + 3(w, w:-1)
The equation is the same as 9 Hence our convergence analysis also suitable for GMC In
Figure 4 we set using top-s strategy with ||a, l = 0.001d, which implies that W nearly as sparse as MyA.- We can see that GMC* achieves the same loss as DMSGD. But slightly worse than GMC and DMSGD in terms of accuracy.
B OTHER WAYS FOR SPARSE COMMUNICATION
is easy to get one way to combine memory gradient and global momentum that we can put the global momentum W. Wi-1 on the server. We briefly present it in Algorithm
12

---

Under review as a conference paper at ICLR 2020
ResNer20, GPUs
ResNet20, GPUs
1.75
DMSGD
1.50
GMC
80
Test Accuracy.
Train Loss
GMC
1.00
70
0.75
60
DMSGD
0.50
GMC
50
0.25
GMC
0.00
40
20
Epoch
Epoch
Figure 4: Comparing GMC* with GMC and DMSGD.
Algorithm 3
for i 0, 1,,,, 2..2...TT do
Workers:
for = 1, 1.2...,,2 ,. each worker parallelly do
gi, ph Eg.EI., &.)
Generate a sparse vector m E {0, 13d, Send m, (gi, + Ur the server; U141, = (1 m @ (gi,k + u.A);
end for
Server:
We+1 - 4/ E m (gr + ue,k) + B(w, wt-1):
Send W,+1 W, to workers;
end for
Let [w:). {. { be the sequences produced by Algorithm 3 then can get that
Wi-1 Th
Σ
M (gi, + ur + 3(w, wr-1),
k=1
U =(1 M,,.) u,,,), 1,2.
By eliminating M. we obtain the same equation as that in (9). Hence our convergence analysis also suitable for Algorithm 3 The difference from GMC that the memory gradient u, in Algorithm 3 only remembers the dropped stochastic gradient. After receiving sparse update vectors from workers, server updates parameter using the global momentum. Compared with GMC, the disadvantage is that its memory gradient does not contain the momentum information which can play the role correcting the update direction. Hence, GMC gets better performance than Algorithm (Lin et al. 2018) also points out that Algorithm 3 has some loss of convergence performance.
Another way is that we put f/ in the memory gradient. We briefly present Algorithm Let {w:), (g {uL,} } be the sequences produced by Algorithm 4 then get that
P
Wx41 =W Mr + Uz,k)
ULFLA = M.a) ue,k), 1,2,,......
By eliminating M.R, obtain the equation that in (9). Hence convergence analysis is also suitable for Algorithm 3. However, the norm memory gradient is larger than that of GMC. In partieular, let yr,k u, T/, then we have
B -(. wt-1) + yt.k)
LL+LA
(I M. x) pb
Σ Vf(We()))
M++1
pip.
E.EZ,A
the same the memory gradient of GMC
13

---

Under review as a conference paper at ICLR 2020
Algorithm 4
fort 0, 1, ...T 1 do
Workers:
for 1.2..., ps each worker parallelly do l1t Σg,EI,, Vf((w;
gr, pb
(w: w:-1);
Generate sparse vector m E {0, 1)d;
Send m2,& @ (gi, + Ur to the server;
1141, = m) @ (gi, + ue,k);
end for
Server:
W++1 = W. - Ei= m @ (gr, + u,,);;
Send Wc+1 W, to workers;
end for
77 is constant, then Algorithm Iis the same as GMC. If m7 is non-increasing, then T) 2 7/+11 and
L Σ
8 (w: w:-1) + y.,e)ll pip
11 211(I - M,,,) pb E:EI.
Vf(wn&))
Figure shows the learning process of ResNet56 on CIFARIO. In the first 80 epochs, GMC and Algorithm 4 are almost the same and both of them are better than Algorithm 3 At the step of scaling
step size by factor 0.1, the norm of memory gradient (yt,k) in Algorithm iis 10 fold of that in GMC. Hence, GMC better than Algorithm 4 after training 80 epochs.
ResNe156, GPUs
ResNet56. GPUs
1.75
1.50
Algorithm3
90
AMM Marrr
Algorithm4
1.25
Accuracy
80
Train Loss
GMC
1.00
70
0.75
600
Algorithm3
0.50
50
Algorithm4
0.25
GMC
0.00
20
140 160
Epoch
Epech
Figure 5: Comparison with Algorithm 3 and Algorithm
C CONVERGENCE PROOFS
First, we introduce the Young's 's Inequality as follow: Va, b
(a b)2 < (1+ + (1 102 Ay > 0.
1
which is used frequently in proofs.
14

---

Under review as a conference paper at ICLR 2020
C.I
PROOF OF LEMMA ]
1 (Wi+1 wz) 76+1 u
B
X++1 W
1-3 -3
1
WW++1 (w()
1 i1+1
1
B
B
(W, - 1 - 1/6 V ([( Ww:: Ix) + B(w, - WI- - Bw, + 7.
71+11
u
1
B
1 - B
1
(Wr - n, T7. Vf( In) + mm 1 u
1
B
1
(We - Bw,- - 7u - 1/6 V/(w,; I,)) + 71 1/141 üc+1
B
1 -
1/2 ùn 1 U
vf(we: Ie) + 1/ 17t i1+1
(W:- Bw(-1)
- 3
1 3
? Vf(Wa:))
1): 1/6+1
u1+1-
1
1 8
C.2 PROOF OF LEMMA
Since Wi+1
We = 7e8 El=1 ML,A(rr. + u(,)), we have by > 0,
B||w1+11 wrll
sn Ee + u.
- 1 3(we-1 w.)/ (V((w: Ix) + url?
<(1 +7)88 - - (1 7 12G2 + mn
Let 7 3 - 1, we get that
v/ (2G² + 2U2) 1- 3
B B||w -
</Bl| w. -
w
20 + 222
(n1 B ... + 31m)).
1 - 3
y) = v, we get that Bl|w;; - w,-1 1 (2G² +2G yn? (1-3)²
Then we obtain
2,32
2T72
E - - - -11- 3)2 El B|(W - -wi-11? + (1- B)2
U2
<1 -
2,3 (2G2 + 222)
21
+ (1 B)2 11?
(1-3)-
?) =
(+ P E
r
[0.5, 11,
0, g 2 0. let to satisfy (6-11-9200 2 Then by induction, we get that E [w, wc-1 2 Then we obtain
1+9
2
A = m
+m
+.. n0 }.
(2G' +20")
max (1-3)*
(1-3)3 E El 2 2n U²
2,32
E E well?
(1 -3)-
2.32 + 2U max (
A3
2U
(1- g/3 mn
8)
15

---

Under review as a conference paper at ICLR 2020
C.3 PROOF OF THEOREM 1
According to Lemma
we get that
E X w=11
E X w 11 -
7
1h. M Vi(W[:
ú [++1)((xx) (xt: - w")
1 1 B
- B
+ E|| B
(.(we: Iz)
7/-1
u 1?
-B|[x
w w11 21F
V.(..) 1
Tc++ ue+1 [xx - w*)
E||
8 Vf(we: IT) 9/-11 ü++1l 11
21p
2(1 17111)
<B X w w111 1 -
EVF(Ww)) w +
1 1 E (x, - -w")
+ El|
v.(wwr:
Iz) 1
-1--1
91-1 uz+11 11
2m
217 B(VF(x) VF(w:)) wi)
SE|X
w' w'11
EVF(xx)
ww)+ + 1
1
2(1 1111)
2G 111
2(1: 112112
UD
U
1-3 -3
(1 - -3)²
(1 -32
2n EF (x1)² (xx))(((--))))) - (xw) + 1 3
21/
SE x1 w'1l2
CCL-B//001.00D
1
2(m
1111)
2G 111
2(m: 1/11))
UD
U²
(16)
1 1-B 3
(1 3)2 (1 B)2
Using the strongly convex property, we get that
E X(+1
w²11
2n
<(1 ]B||x
X1 [||xx-wWi 21
1- 3 V CL-BB)/011B.0DD
2(th .1(+1) UD
2G
2(t 11(41)² U
1- B
(1 3)-
(1- B)²
5(1 [[|x Xt- - 2 [2(1 3) Cc /00 2 20 + 2U2
11213
Since E||x| w011 < D we get that
A
E|
w
<
Vt 1,
4226"
where A= max{p222,2(1 ( 2G + 2U2). Using 16 again,
get that
Elxx+11 - w A
(F(:)( - F(w")) S pt|lx w01
jut"
16

---

Under review as a conference paper at ICLR 2020
By summing up the equation from t t= T - to T 1, we get that
B(F(x;) - F(w"))
t=T-m m
T-1
A
[nl(B|ix -B - w*1l3) +
jet
t=T-m
SM(T - m)BB|xr-m- - w
-
Σ
(n |x: - w
jut
t= m
2A
SP(T - B) w
Σ
jut
2A
/
jet
T=T-m
By setting m [T/2], we get that -t=T-m I 1. Then
1
Σ
B(F(x,) - F(w")) S 34
TT
Since [xF(x,) - F(w:)] (VF -x)
1-8
ut, we get the result
B(F(w.)= F(w")) S 3A+ 3A+2G /11
nT
T=
C.4 PROOF OF THEOREM 2
Similar to T6), we get that
E Bl|xx++1 w²11
=E|[x; w 112 2
1he
V.((w;
1t 17+1
u++1] 10 (xx - w*)
1 1- 3
1-3 B
+ E|| T)
Vf(W,; IT)
71 T)++1
i1+1l12
1 - B
1 1 B
=B||x; w 1|2 2m
17
(F(w.)
17t 17++1
ú [xxe= ww)
1- 3
1- B
+ E|| 1 VS(w.; Ix)
M
112
1 B
21tt
2(1h: (7(-1)
<B|[x; - w 112
EV F(W.)) - w*) +
(x: - w*) |
1 -
1 1- B
111 Me+1 11+1l1
+ EI| I B
1- B
2m
27,
<FI[x; w011
EV EVF(W,))T(M w*)+
EVF(W:) xx)
I 3
1- 3
+ 2(1:: m+11)
2/
2(m -1++)
UD
+
U²
(1-
(1
8)3
2m
2n
<EI|x, w11
B(F(w:)) F(w"))
V
CC--B.10.5...0G
1 3
1 3
2(1 - 11+1)
UD 2G
2(1 11++) )
+
22
(17)
1-3
(1-3)
(1 (1-3)²
17

---

Under review as a conference paper at ICLR 2020
Since 7)
1-8 vIFI
we get that
T-1
Σ
vt+1 B(F(w:) F(w")) <| - ww'12 + Σ t+1
<|/wo- - w'11 + A (Tg(
where A = = - 11--83/C--B11...0 2UD 2G + 2U2
C.5
PROOF OF THEOREM 3
Since F(.) is L-smooth, get that
EF(x++)
L
<XF( 1- E [VFF(x)"V//(VV)
BI| V V[(w: (w.: 2.
Ln²
=EF(xx)
1 E F[VF(X X VF(w:)] + 2(1 8)3
E V wr I2]l
LG
<EF(x,) 1 E[| (w. (VF(x,) - VF(w,)) [W(w,)) VFF(..) +
2(1- B)²
LG
<EF(x)) 1 E[| V(::)( LG||x well 2(1 9)2
<EF(X)) 1- E V/) LG "0.02,19..11 1 B
1G2112
2(1 - B)2
Summing up the above equation from L= t T 1, we get that
1
F(wo) F(w*)
E (E::))
+ An,
(1 B)T
Tn
t=0
where A
LG Co..1...p
+
LG 2(1-372
1-8
D MORE DISCUSSION ABOUT ASSUMPTION 2
In the convergence theorems, we need E 0 < U (Assumption 2) Since ú, Eb Ue we only need E||u,,,,] 2 to be bounded which is mainly related to the choice of my,k- Theoretically, we set one large threshold 0 in advance and we denote 07,, the s-largest value of (1g +u
1,.... d}. Then in each iteration, can choose the values such that ( 2 z min 0 Then we obtain | 2| < d0² and hence E "r S. d02. In practice, the large threshold 0 is never been used for the choice of m,, since Of.R << Ó.
MORE DISCUSSION ABOUT ASSUMPTION 3 E
If we do not use Assumption in the proofs of Theorem T Tand Theorem 2 we can add one projection operation on equation (7). which can be written as
We+1 = No(w: 1/t Σ
+ u.,)),
k=1
where Ω = [w|l w|| < W) and || S
W
2- Then w, is bounded. Hence, we reasonably assume
that Vt, ||ū||| < U, [ { < G and we 77 < no S (1-81W
20 Please note that the U can
be irrelevant to ft according to Appendix D We still define x,
B
w,
w,
W.-1)
1 ú
1 3
18

---

Under review as a conference paper at ICLR 2020
Then X2 is bounded as well.
To get the convergence results for strongly convex and convex functions, we need to prove two essential inequalities: [X|x w. O(n) and | -w I |x - 3 V +
N1 - I-B 11.1
First, we get that [| - 1.,1- S n/! Ei (BA u.,a According the definition of Mr we have byy > 0,
|| -
Σ/ |l: + ú
=1111<< We wi-1)/ Vf( In) + utll
11 + (1 + 1
< + +> w: - w
(2G² + )
By setting = 1-8 we obtain || - will - w, - w 2 + 2G 2 Then using the
1-3
proof in Lemma 2 obtain the first inequality that E||x; w. =
Next, we get the relation between X++1 and xt. According to the definition of x,, we have
B 1 (We41 Wz) Mh+1 3 u w*11
||x+1 w"1l We+1
8)- ||2+11 -11+1u041 + Bw, + (1 - 1-5)w")
Since ||ū,|| S U uniformly and ||w*|| S 2 " S 7/0 S
(1-8)W 20
we get that
W
M4410+11 + Bw,, + (1 -1-3) -3ww"l 1m++1U + 3W + (1
3) 2
S W.
Then we obtain 7 uz+1 + Bw, + (1 - 3)w* E and
P
[|x++1 - w 22
[: n Σ
Mg, + ur,c)) - (ne+ u.41 + Bw, + (1 - 3ww"))""
(1 3)
1=1
1
|w, (g + ū, ü++1) (M4410+1 + Bw, (1 3)w*)11
(1 - B)2
| w
1/t
V[(W;;;)) + "t - 1/+1
1- B 11
1
Then similar the analysis in Theorem and Theorem convex and convex cases.
can prove the convergence for strongly
19


Reviews:
[{"review_id": "HJgWOKP0YH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The author propose a method called global momentum compression for sparse communication setting. The contributtions can be summarized into 3 parts: switching DGC setting from local momentum to global momentumm, theortical proof of the convergence, empirical results showing performance. \n\nHowever there have several issues:\n\t1. No significant contribution. Although they theoretically prove a new version of DGC, it's just a minor modification and no significant performance improvement as shown from their empirical results.\n\t2. In the experiment session, as shown in the results,  their method seems more stable during training but there achieves minor improvement in terms of the test accurarcy. Second, they only compare with DGC and it's counterpart baseline. It's better to include more related algorithms for comparison (like quantization methond: QSGD or signSGD).\n\t3. Comparing with DGC, there is no improvement in saving communication as shown in their results. Since GMC only changes DGC setting from local momentum to global momentum, no modification is involved in the compression part of DGC. \n\nOverall, I appreciate the authors for their theoretical contribution for DGC and well written paper. However, it would be great to show a better improvement and include more related methods for comparison. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HJg4VKwbKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Gradient sparsification is an important technique to reduce the communication overhead in distributed training. In this paper, the authors proposed a training method called global momentum compression (GMC) for distributed momentum SGD with sparse gradient. Following existing gradient sparsification techniques such DGC, GMC is also built up on the memory gradient approach; the major distinction between GMC and existing techniques is that GMC keeps track of global gradient to maintain the memory gradient, while the existing technique keeps track of worker-local gradients for memory gradient. The primary contributions in the paper are as the following:\n\n1. The authors propose GMC, a training method for distributed momentum SGD with sparse gradient communication. It uses global gradient (but still achieve sparse communication) to maintain the gradient memory while existing approaches such as DGC use worker-local gradient to do so.\n\n2. The authors prove the convergence rate of GMC for 1. strongly convex and smooth functions 2. convex functions and 3. Non-convex Lipschitz smooth functions. This is the first work on proving the convergence rate of distributed momentum SGD using sparse communication techniques based on memory gradient.\n\n3. Empirically, the authors show that GMC can empirically attain the same model accuracy as conventional distributed momentum SGD with ~100x reduction in communication overhead. It can also match the performance of DGC at the same communication compression rate.\n\nI think in general the ideas and efforts of the authors in proving the convergence rate of distributed momentum SGD with *gradient sparsification* is interesting and important. However, I have the some questions and concerns on validating the claims in the paper. I currently give weak reject but I am happy to raise the score if the authors can clarify or improve in their rebuttal / future drafts. The primary questions and concerns (critical to the rating) are:\n\n1. One important claimed advantage of GMC over existing method is that it uses global gradient for memory gradient, while existing methods such as DGC uses local-work gradient to do so. But I did not find convincing support of this advantage in the paper: Empirically, in the experiment results, I don't think GMC demonstrate better performance than DGC in a statistical meaningful way; instead they are basically demonstrating matching performance. Theoretically, I am not sure if only the global gradient enables the proof of convergence rate while the worker-local gradient cannot. My preliminary feeling is that by bounding the gradient variance, it should also be possible to prove a rate for DGC using worker-local gradient; this is because the difference between the global gradient and the local gradient might be bounded via the gradient variance.\n\n2. In the experiments, the authors focus on momentum SGD for image classification tasks. To better support the versatility and efficacy of GMC, it would be interesting to include some experiments for other domains (e.g. using the STOA transformer style models for NLP tasks). In these models, momentum-like components are also used in the optimizer (e.g. Adam for fairseq for machine translations), it will be interesting to see if the efficacy of GMC also empirically transfer to these settings.\n\nMinor questions (influencing the rating in a secondary way) \n\n1. Regarding the assumptions in the paper, I think assumption 2 need some validation / support to show that it is a proper one. My preliminary feeling is that assumption 2 is intuitive as the sparsification procedures only zero out small values so that the error introduced in the gradient is small and bounded. But it should be more convincing to empirically show the magnitude of u comparing to the magnitude of gradient g in Equ. 8. \n\n2. I notice that the experiments uses conventional momentum SGD for a few epochs as warm up, is there any specific reasoning on using this warmup approach instead of the sparsity level warmup as used in DGC?\n\n3. In the experiments, GMC does not use the factor masking trick while DGC uses. If it is for demonstrating the benefits of global gradient for gradient memory, I think it is more proper to also include the results of DGC without factor masking? In this way, this question can be directly answered in an ablation study way by eliminating the possible contribution of using/not using factor masking. \n\n\nNITS to improve the paper (not related to the rating):\n\n1. The last contribution bullet forgets to mention that it is about comparing to DGC.\n\n2. In algorithm 1, it is clearer to mention how the mask m is generated (e.g. based on magnitude).\n\n3. In the second paragraph in section 3.2, the vector inner product is not properly written between coefficients and w.\n\n4. Above theorem 1, in the text, the condition for the discussion on the two cases are confusing.\n\n5. In the definition of CR in the first paragraph of section 5, why the summation starts from 5. The text describes as warm up with 5 *epochs* while in the equation it is saying warm up with 4 *steps*.\n\n\n\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1gmm0BAKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a scheme for incorporating compressed (sparsified) gradients with momentum in distributed SGD. The approach differs from others in the literature, comes with theoretical guarantees, and improved performance. The results are correct, and the experiments illustrate that the proposed approach can make a difference (albeit, modest) in the quality of the resulting model.\n\nThe main point I find dissatisfying about the theoretical results of the paper are the use of Assumption 2. The memory vector is a parameter of the algorithm. I realize that one can enforce this with a projection, as argued in the paragraph rationalizing this assumption. However, that specific case isn't analyzed and it isn't clear how incorporating that projection would affect the accuracy, since it would essentially be countering the effect of error feedback.\n\nI also find Assumption 3 to be strange. In the convex setting, one can typically show that this follows from Assumption 1 alone under the additional assumption of a suitably small step size. In the non-convex setting it isn't clear what this means, since w^* is not well defined (if there are multiple global minimizers).\n\nAssumption 1 is also strong. Typically one assumes that the stochastic gradients are unbiased, and either that the expected gradient is Lipschitz continuous (in the smooth case), or the expected gradient is bounded (in the non-smooth case). Assuming that the stochastic gradients are uniformly bounded essentially implies that the noise vanishes when the gradient gets large. \n\nCan you provide examples of functions/problems satisfying these assumptions? Even an example as simple as the case where $F$ is a finite sum of quadratic functions, and one randomly samples one of the terms in the finite sum to compute the gradient (i.e., using SGD to solve a large linear least squares problem) doesn't appear to satisfy Assumption 1.\n\nOverall the results are potentially interesting. I would have given a higher rating if the assumptions didn't appear to be so strong, and if the experimental results demonstrated a more substantial difference with DGC.\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The author propose a method called global momentum compression for sparse communication setting, and provided some theoretical results on the convergence rate. The convergence result is interesting, but the underlying assumptions used in the analysis appear very strong. Moreover, the proposed algorithm has limited novelty as it is only a minor modification. Another main concern is that the proposed algorithm shows little performance improvement in the experiments. Moreover, more related algorithms should be included in the experimental comparison.
Decision: Reject