Year: 2019

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 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 global momentum compression (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 with no loss of generalization accuracy. GMC can also achieve comparable (sometimes better) performance compared with DGC, with an extra theoretical guarantee.

heading: 1 INTRODUCTION
text: Many machine learning models can be formulated as the following empirical risk minimization problem:
min w∈Rd
F (w) := 1
n n∑ i=1 f(w; ξi), (1)
where w denotes the model parameter, ξi denotes the ith training data, n is the number of training data, and d is the size of the model. For example, let ξi = (ai, yi), where ai denotes the feature of the ith training data and yi denotes the label. Then in logistic regression f(w; ξi) = log(1 + e−yia
T i w) + λ2 ‖w‖ 2, and in SVM f(w; ξi) = max(0, 1 − yiaTi w) + λ2 ‖w‖ 2. Many deep learning
models can also be formulated as (1).
One of the efficient ways to solve (1) is stochastic gradient descent (SGD) (Robbins & Monro, 1951). In each iteration, SGD calculates one stochastic gradient ∇f(w; ξi) and updates w by w← w−η∇f(w; ξi), or updates w with a mini-batch of stochastic gradients. Inspired by momentum and nesterov’s accelerated gradient descent, momentum SGD (MSGD) (Polyak, 1964; Tseng, 1998; Lan, 2012; Kingma & Ba, 2015) has been proposed and widely used in machine learning. In practice, MSGD can achieve better performance than SGD (Krizhevsky et al., 2012; Sutskever et al., 2013). Many machine learning platforms like TensorFlow, PyTorch, 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 calculate a batch of stochastic gradients. DSGD can
be formulated as follows:
wt+1 = wt − ηt p p∑ k=1 gt,k, (2)
where p is the number of workers, gt,k is the stochastic gradient or a mini-batch of stochastic gradients calculated by the kth worker at the tth iteration. DSGD can be implemented on distributed frameworks like parameter server and all-reduce framework. Each worker calculates gt,k 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, gt,k is a high dimensional vector. Due to the latency and limited bandwidth of network, communication 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 dimension vectors from workers, which will lead to communication traffic jam and make the convergence of DSGD slow. Hence, we need to compress gt,k 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 et 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 an 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 to 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 gt,k at each iteration, each worker only sends a subset of coordinates in gt,k, denoted as S(gt,k), to the server or other workers. Here, S(gt,k) 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., gt,k−S(gt,k), and store it in the memory rather than dropping them. The gt,k−S(gt,k) is called memory gradient and will be used to calculate the next update vector gt+1,k. This is intuitively necessary because a subset of coordinates in the stochastic gradient can not reflect the real descent direction and can make errors with higher probability than the original stochastic gradient. This memory gradient based sparse communication strategy has been widely adopted by recent communication compression methods and has achieved better performance than quantization methods and other sparse communication methods without memory gradient. In these memory gradient based sparse communication methods, some are for vanilla SGD (Aji & Heafield, 2017; Alistarh et 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 et al., 2018; Karimireddy et al., 2019; Tang et al., 2019). Very recently, there has appeared one sparse communication method for distributed MSGD (DMSGD), called deep gradient compression (DGC) (Lin et al., 2018), which has achieved better performance than vanilla DSGD with sparse communication in practice. However, the theory about the convergence of DGC is still lack. Furthermore, although DGC uses momentum SGD, the momentum in DGC is calculated by each worker. Hence it is a local momentum without global information.
In this paper, we propose a novel method, called global momentum compression (GMC), for sparse communication in DMSGD which includes DSGD as a special case. The main contributions of this paper are 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 problems. 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, compared with the DMSGD counterpart without sparse communication, 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.

heading: 2 PRELIMINARY
text: In this paper, we use ‖ · ‖ to denote L2 norm, use w∗ to denote the optimal solution of (1), use ∇f(w; I) , 1|I| ∑ ξi∈I ∇f(w; ξi) to denote one stochastic gradient with respect to a mini-batch of samples I such that EI [∇f(w; I)|w] = ∇F (w), use to denote element-wise product, use 1 to denote the vector (1, 1, . . . , 1)T ∈ Rd, use ej to denote the vector (0, . . . , 1, . . . 0)T ∈ Rd with only the jth coordinate being 1, use I to denote an identity matrix. For a vector a, we use a(j) to denote its jth coordinate value. ‖a‖0 denotes the number of non-zero values in a.
Definition 1 (smooth function) Function h(·) is L-smooth (L > 0) if ∀w,w′,
|h(w)− h(w′)−∇h(w′)T (w −w′)| ≤ L 2 ‖w −w′‖2.
Definition 2 (convex function) Function h(·) is convex if ∀w,w′,
|h(w)− h(w′)−∇h(w′)T (w −w′)| ≥ µ 2 ‖w −w′‖2,
where µ ≥ 0. If µ > 0, h(·) is called a µ-strongly convex function.

heading: 2.1 DISTRIBUTED MOMENTUM SGD
text: The widely used momentum SGD (MSGD) (Polyak, 1964) for solving (1) can be written as
gt =βgt−1 + ηt∇f(wt; It), wt+1 =wt − gt,
where β ∈ [0, 1). The gt is the Polyak’s momentum and ∇f(wt; It) is an unbiased estimation of ∇F (wt). Since gt = (wt −wt+1), MSGD can also be written as
wt+1 =wt − ηt(∇f(wt; It) + β
ηt (wt−1 −wt)). (3)
Please note that if β = 0, 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 ∇f(wt; It) + β(wt−1 − wt)/ηt. The update process of w in this way is equivalent to the serial MSGD. We call (wt−1 −wt)/ηt the global momentum, because it captures the global information from all workers.
Another way to implement DMSGD is using local momentum:
gt,k =βgt−1,k + ηtvt,k, k = 1, 2, . . . , p, wt+1 =wt − p∑ k=1 gt,k,
where vt,k is the stochastic gradient calculated by the kth worker and ∑p k=1 vt,k = ∇f(wt; It).
gt−1,k is the local momentum. Since ∑p k=1 gt−1,k = (wt−1 − wt), this DMSGD with local momentum can also be written as 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 on the global momentum. Hence, each worker in DGC cannot capture the global information from its own local momentum, while that in 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.
Algorithm 1 Global Momentum Compression (GMC) on Parameter Server 1: Initialization: p workers, w−1 = w0, β ∈ [0, 1), batch size b; 2: Set g0,k = u0,k = 0, k = 1, . . . , p, 3: for t = 0, 1, 2, ...T − 1 do 4: Workers: 5: for k = 1, 2 . . . , p, each worker parallelly do 6: if t > 0 then 7: Receive wt −wt−1 from the server; 8: Get wt by wt = wt−1 + (wt −wt−1); 9: end if 10: Randomly pick a mini-batch of training data It,k ⊆ Dk with |It,k| = b; 11: gt,k = 1 pb ∑ ξi∈It,k ∇f(wt; ξi)− β pηt
(wt −wt−1); 12: Generate a sparse vector mt,k ∈ {0, 1}d; 13: Send mt,k (gt,k + ut,k) to the server; 14: ut+1,k = (1−mt,k) (gt,k + ut,k); 15: end for 16: Server: 17: wt+1 = wt − ηt ∑p k=1 mt,k (gt,k + ut,k); 18: Send wt+1 −wt to workers; 19: end for

heading: 3 GLOBAL MOMENTUM COMPRESSION
text: Assume we have p workers. Dk denotes the data stored on the kth worker (k = 1, 2, . . . , p) and⋃p k=1Dk = {ξ1, ξ2, . . . , ξn}. Our method Global Momentum Compression (GMC) mainly performs the following operations iteratively:
• Each worker calculates gt,k = 1pb ∑ ξi∈It,k ∇f(w; ξi)− β pηt
(wt−wt−1), where It,k ⊆ Dk and |It,k| = b; • Each worker generates a sparse vector mt,k and sends mt,k (gt,k + ut,k) to the server
or other workers;
• Each worker updates ut+1,k = (1−mt,k) (gt,k + ut,k); • Update parameter wt+1 = wt − ηt ∑p k=1 mt,k (gt,k + ut,k);
Below, we introduce the framework and two essential elements of GMC: memory gradient ut,k and global momentum (wt−1 −wt)/ηt.

heading: 3.1 FRAMEWORK OF GMC
text: GMC can be easily implemented on the all-reduce distributed framework in which each worker sends the sparse vector mt,k (gt,k+ut,k) to all the other workers, then each worker updates wt+1 after receiving the sparse vectors from other workers.
Recently, parameter server (Li et al., 2014a) has been one of the most popular distributed frameworks in machine learning. GMC can also be implemented on parameter server. Although the theories in this paper can be adopted for the all-reduce framework, in this paper we adopt parameter server for illustration. The details of GMC implemented on parameter server are shown in Algorithm 1. The difference between GMC and traditional DSGD on parameter server is that in GMC after updating wt+1, server will send wt+1 −wt, rather than wt+1, to workers. Since mt,k is sparse, wt+1 −wt is sparse as well. Hence, sending wt+1 − wt can reduce the communication cost compared with sending wt. In our experiments, we find that GMC can make ‖wt+1 −wt‖0 ≤ 0.01d with no loss of accuracy when training large scale models. Workers can get wt+1 by wt+1 = wt+(wt+1−wt).
Remark 1 We can also use the sparse communication technique on the server (denoted as GMC∗) to make (wt+1−wt) sparser than that in GMC so that when the server sends wt+1−wt to workers, the communication cost can be further reduced, compared with GMC. The convergence of GMC∗
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.

heading: 3.2 NECESSITY OF MEMORY GRADIENT
text: In GMC, after sending a sparse vector mt,k (gt,k+ut,k) to the server, each worker will remember the coordinates which are not sent and store them in ut+1,k:
ut+1,k = (1−mt,k) (gt,k + ut,k). (4) Hence we call ut,k 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 are not sent. We consider the simple case that β = 0, which means gt,k is a stochastic gradient of F (w) and GMC degenerates to (Aji & Heafield, 2017). Since mt,k is a sparse vector, GMC can be seen as a method achieving sparse communication by combining stochastic coordinate descent (SCD) (Nesterov, 2012) and DSGD. In SCD, each −∇F (w)(j)ej denotes a true descent direction. When we use a stochastic gradient ∇f(w; I) to replace ∇F (w), −∇f(w; I)(j)ej will make errors with high probability, especially when mt,k adopts the strategy that choosing s coordinates with the largest absolute values (denoted as top-s strategy).
For further explaining the importance of memory gradient, we consider the following simple example: let n = p = 2, f(w; ξ1) = (−α, )w, f(w; ξ2) = (α + , γ)w, where w ∈ [−1, 0] × [−1, 0], 0 < < α < γ < α + . f(w; ξ1) is on the first worker and f(w; ξ2) is on the second worker. Then we run GMC with β = 0 to solve minF (w) = 12 (f(w; ξ1) + f(w; ξ2)). The optimal solution is w∗ = (−1,−1)T . We adopt the top-1 strategy for mt,k in this example. If we do not use the memory gradient, which means each worker directly sends mt,k gt,k to the server, then the two workers will send (−α/2, 0)T and ((α + )/2, 0)T respectively to the server. The parameter is updated by w← w−ηt( /2, 0). We observe that w(2) will never be updated. This is due to the pseudo large gradient value which cheats mt,k. Since ∇F (w) = ( /2, (γ + )/2)T , we can see that the second coordinate has the true large gradient value and we should have mainly focused on updating w(2). However, in the two stochastic gradients ∇f(w; ξ1) and ∇f(w; ξ2), the first coordinate has larger absolute value. Hence,∇f(w; ξk) cheats mt,k which leads to the error.
If we use memory gradient, at the beginning, mt,1 = mt,2 = (1, 0)T . After some iterations, mt,1 = (0, 1)
T and mt,2 = (0, 1)T due to the memory gradient. Specifically, let t1, t2 be two integers satisfying α/ ≤ t1 < α/ + 1, (α + )/γ ≤ t2 < (α + )/γ + 1, then it is easy to verify that mct1,1 = (0, 1) T ,mct2,2 = (0, 1) T ,∀c ≥ 1. It implies that if we use the memory gradient, both w(1) and w(2) will be updated. Hence, GMC can make w converge to the optimum (−1,−1)T . Hence, the memory gradient is necessary for sparse communication. It can overcome the disadvantage of combining DSGD and SCD.

heading: 3.3 BENEFIT OF GLOBAL MOMENTUM
text: In GMC, each worker calculates gt,k as
gt,k = 1
pb ∑ ξi∈It,k ∇f(wt; ξi)− β pηt (wt −wt−1). (5)
When β = 0, it degenerates to DSGD with sparse communication, which is also called gradient dropping in (Aji & Heafield, 2017). We use g(GD)t,k to denote this degenerated version with β = 0. We can see that GMC uses the global momentum (wt−1−wt)/ηt. While in DGC (Lin et al., 2018), the g(DGC)t,k is calculated by
g (DGC) t,k =
1
pb ∑ ξi∈It,k ∇f(wt; ξi) + βg(DGC)t−1,k, (6)
which uses the local momentum g(DGC)t−1,k. We use u (DGC) t,k to denote the memory gradient in DGC.
For sparse mt,k, we can find that g (DGC) t,k and u (DGC) t,k only contain the information based on the local data, while gt,k and ut,k can contain the global information due to the global momentum. Hence, global momentum is better than local momentum when using memory gradient for sparse communication. Assume that E[F (wt)] converges to F (w∗), then wt −wt−1 denotes the descent direction with high probability. Since It,k ⊆ Dk, which only contains partial information of the whole training data, the global momentum (wt−1 − wt)/ηt can make compensation for the error between the stochastic gradient and the full gradient. Specifically, if (wt−wt−1)T (−∇F (wt)) ≥ 0, then we get that
gTt,k∇F (wt) =( 1
pb ∑ ξi∈It,k ∇f(wt; ξi)− β pηt (wt −wt−1))T∇F (wt)
≥ 1 pb ∑ ξi∈It,k ∇f(wt; ξi)T∇F (wt)
=(g (GD) t,k ) T∇F (wt).
It implies that gt,k is a better estimation of ∇F (wt) than g(GD)t,k . The experiments in (Lin et al., 2018) also show that (Aji & Heafield, 2017) has some loss of accuracy with ‖mt,k‖0 ≈ 0.001d, while we can set such a sparsity for GMC with no loss of accuracy in practice. Hence, GMC is better than (Aji & Heafield, 2017).
Remark 2 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.

heading: 4 CONVERGENCE OF GMC
text: 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 a diagonal matrix Mt,k ∈ Rd×d such that diag(Mt,k) = mt,k to replace the symbol . Then we obtain
wt+1 =wt − ηt p∑ k=1 Mt,k(gt,k + ut,k), (7)
ut+1,k =(I−Mt,k)(gt,k + ut,k), k = 1, 2, . . . , p. (8) For convenience, we denote ∇f(w; It) = 1pb ∑p k=1 ∑ ξi∈It,k ∇f(wt; ξi), ũt = ∑p k=1 ut,k, g̃t =∑p
k=1 gt,k. By eliminating Mt,k, we obtain
wt+1 =wt − ηt∇f(wt; It) + β(wt −wt−1)− ηtũt + ηtũt+1. (9) We can find that if we do not use the sparse communication technique, then ũt = 0 and (9) is the same as momentum SGD in (3).
First, we give the following lemma:
Lemma 1 Let xt = wt + β1−β (wt −wt−1)− ηt 1−β ũt. Then we have:
xt+1 = xt − ηt
1− β ∇f(wt; It) + ηt − ηt+1 1− β ũt+1. (10)
Equation (10) is similar to the update equation in SGD except the additional term ũt+1. Inspired by this, we only need to prove the convergence of xt and ‖xt − wt‖. To get the convergence results, we further make the following three assumptions:
Assumption 1 (bounded gradient) E‖∇f(wt; ξi)‖2 ≤ G2,∀t.
Assumption 2 (bounded memory) E‖ũt‖2 ≤ U2,∀t.
Assumption 3 (bounded parameter) E‖xt −w∗‖2 ≤ D2,∀t.
Remark 3 Assumption 1 is common in stochastic optimization. Assumption 2 is easy to be guaranteed. We discuss it in Appendix D. Assumption 3 is only for convenience in the analysis for strongly convex and convex cases. We can add one projection operation on Equation (7) to guarantee Assumption 3 (if both wt and ũt are bounded, xt is bounded as well), which can be written as wt+1 = ΠΩ(wt − ηt ∑p k=1 Mt,k(gt,k + ut,k)). The convergence can still be guaranteed if we use the projection operation. More details are put in Appendix E.
For the new variable xt in Lemma 1, the gap between xt and wt has the following property:
Lemma 2 With Assumption 1 and Assumption 2, we get that
• If ηt = η, then
E‖xt −wt‖2 ≤ [ 2β2(2G2 + 2U2)
(1− β)4 +
2U2
(1− β)2 ]η2. (11)
• If ηt = r(t+q)ρ , ρ ∈ [0.5, 1], r > 0, q ≥ 0, then
E‖xt −wt‖2 ≤ [ 2β2(2G2 + 2U2) max{(1− β)A, 2}
(1− β)4 +
2U2
(1− β)2 ]η2t . (12)
where A = maxt0t=0{ η2t+βη 2 t−1+...+β tη20 η2t+1 }, t0 satisfies ( t0+1+qt0+2+q ) 2ρ ≥ 1+β2 .
Lemma 2 implies that E‖xt − wt‖2 ≤ O(η2t ), i.e. the distance between xt and wt is O(ηt). For convenience, below we use the constant Cr,q,ρ,β,η to denote the upper bound of E‖xt − wt‖2/η2t . If r = 0, Cr,q,ρ,β,η denotes the upper bound in (11) and if η = 0, Cr,q,ρ,β,η denotes the upper bound in (12). Then we have the following convergence results:
Theorem 1 (strongly convex case) LetF (·) beL-smooth and µ-strongly convex. With Assumption 1, Assumption 2, Assumption 3, and ηt = 1−βµ(t+1) , m = dT/2e, we obtain
1
m T−1∑ t=T−m E(F (wt)− F (w∗)) ≤ 3A+ 2G
√ C(1−β)/µ,1,1,β,0(1− β)
µT .
where A = max{µ2D2, 2(1− β) √ C(1−β)/µ,1,1,β,0LD + µUD + 2G 2 + 2U2}.
Theorem 2 (convex case) Let F (·) be a convex function. With Assumption 1, Assumption 2, Assumption 3, and ηt = 1−β√t+1 , we obtain
T−1∑ t=0 2√ t+ 1 E(F (wt)− F (w∗)) ≤ ‖w0 −w∗‖2 +A log(T ),
where A = 2(1− β) √ C1−β,1,0.5,β,0G+ 2UD + 2G 2 + 2U2. Since ∑T−1 t=0 1√ t+1 = O( √ T ), Theorem 2 implies that if the objective function is convex, GMC has a convergence rate of O(log(T )/ √ T ).
Theorem 3 (non-convex case) Let F (·) beL-smooth. With Assumption 1, Assumption 2, and ηt = η being a constant, we obtain
1
(1− β)T T−1∑ t=0 E‖∇F (wt)‖2 ≤ F (w0)− F (w∗) Tη +Aη,
where A = LG √ C0,0,1,β,η 1−β + LG2 2(1−β)2 .
By taking η = O(1/ √ T ), it is easy to find that GMC has a convergence rate of O(1/ √ T ), if the objective function is non-convex.

heading: 5 EXPERIMENTS
text: 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 on 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 β is set as 0.9. In our experiments, we consider the communication cost on the server which is the busiest node. It 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 mt,k is sparse, workers send the vectors using the structure of (key, value). The cost of each (key, value) is 2. Server sends wt+1 −wt using this structure as well. Hence, the cost of GMC and DGC is 2( ∑p k=1 ‖mt,k‖0 + p‖wt+1 −wt‖0). We define the communication compression ratio (CR) of GMC and DGC as:
CR = 1
T T+4∑ t=5 1 pd (p‖wt+1 −wt‖0 + p∑ k=1 ‖mt,k‖0).
The CR of DMSGD is 100% (no compression). Here, all numbers have the same unit (float value).

heading: 5.1 CONVEX MODEL
text: 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, mt,k directly adopts top-s strategy with ‖mt,k‖0 = s where s = 0.01d or 0.001d. We use 8 workers for this experiment. The weight decay is 0.0001 and total batch size is 128. The result is shown in Figure 1. We can see that GMC gets similar performance as DGC and DMSGD.

heading: 5.2 NON-CONVEX MODEL
text: For large models, we use the approximate top-s strategy for mt,k: given a vector a, we first randomly choose a subset S ⊂ {1, . . . , d} and |S| is 0.001d ∼ 0.01d. We get the threshold θ such that |{j||a(j)| ≥ θ, j ∈ S}| = 0.001|S|. Then we set mt,k by choosing the indexes in {j||a(j)| ≥ θ, j = 1, 2, . . . , d}. It implies that ‖mt,k‖0 is approximately 0.001d. First, we use the dataset CIFAR-10 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 2 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 can see that GMC also gets the performance as that of DMSGD and is slightly better than DGC. Table 1 shows 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 8 workers with total batch size 256. The weight decay is set as 0.0001. In Figure 3, GMC gets the same
test accuracy as that of DMSGD during the learning process. Table 2 shows that compared with DMSGD, GMC can reduce the communication cost by more than 100 fold with no loss of accuracy and save about 40% of training time. Compared with DGC, GMC achieves slightly better accuracy with comparable communication compress ratio.
0 20 40 60 80
Epoch
Figure 3: Learning process.

heading: 6 CONCLUSION
text: 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.

heading: A USING SPARSE COMMUNICATION ON SERVER
text: If we use the sparse communication technique on the server, the update for wt can be written as:
wt+1 =wt − ηtat [ p∑ k=1 mt,k (gt,k + ut,k) + ∆t], (13)
ut+1,k =(1−mt,k) (gt,k + ut,k), k = 1, 2, . . . , p, (14)
∆t+1 =(1− at) [ p∑ k=1 mt,k (gt,k + ut,k) + ∆t], (15)
where gt,k is the same as that in GMC. We call this method GMC∗. The mt,k and at are generated by the worker and server respectively. The ut,k and ∆t are the memory gradients on the worker and server respectively. We can call ut,k the local memory gradient and ∆t the global memory gradient. Details are presented in Algorithm 2.
Algorithm 2 GMC∗
1: Initialization: p workers, w−1 = w0, β ∈ [0, 1), batch size b; 2: Set g0,k = u0,k = ∆0 = 0, k = 1, . . . , p, 3: for t = 0, 1, 2, ...T − 1 do 4: Workers: 5: for k = 1, 2 . . . , p, each worker parallelly do 6: if t > 0 then 7: Receive wt −wt−1 from the server; 8: Get wt by wt = wt−1 + (wt −wt−1); 9: end if
10: Randomly pick a mini-batch of training data It,k ⊆ Dk with |It,k| = b; 11: gt,k = 1 pb ∑ ξi∈It,k ∇f(wt; ξi)− β pηt
(wt −wt−1); 12: Generate a sparse vector mt,k ∈ {0, 1}d; 13: Send mt,k (gt,k + ut,k) to the server; 14: ut+1,k = (1−mt,k) (gt,k + ut,k); 15: end for 16: Server: 17: Generate a sparse vector at ∈ {0, 1}d; 18: wt+1 = wt − ηtat [ ∑p k=1 mt,k (gt,k + ut,k) + ∆t];
19: ∆t+1 = (1− at) [ ∑p k=1 mt,k (gt,k + ut,k) + ∆t] 20: Send wt+1 −wt to workers; 21: end for
We eliminate mt,k,at and obtain
wt+1 − ηt∆t+1 =wt − ηt[ p∑ k=1 mt,k (gt,k + ut,k) + ∆t]
=wt − ηt[g̃t + ũt − ũt+1 + ∆t] By denoting ht = ũt + ∆t, we obtain
wt+1 − ηtht+1 = wt − ηtht − ηt∇f(wt; It) + β(wt −wt−1) The equation is the same as (9). Hence our convergence analysis is also suitable for GMC∗. In Figure 4, we set at using top-s strategy with ‖at‖0 = s = 0.001d, which implies that wt+1 −wt is nearly as sparse as mt,k. We can see that GMC∗ achieves the same loss as DMSGD. But it is slightly worse than GMC and DMSGD in terms of accuracy.

heading: B OTHER WAYS FOR SPARSE COMMUNICATION
text: It is easy to get one way to combine memory gradient and global momentum that we can put the global momentum wt −wt−1 on the server. We briefly present it in Algorithm 3.
Algorithm 3 for t = 0, 1, 2, ...T − 1 do
Workers: for k = 1, 2 . . . , p, each worker parallelly do gt,k = 1 pb ∑ ξi∈It,k ∇f(wt; ξi);
Generate a sparse vector mt,k ∈ {0, 1}d; Send mt,k (gt,k + ut,k) to the server; ut+1,k = (1−mt,k) (gt,k + ut,k);
end for Server: wt+1 = wt − ηt ∑p k=1 mt,k (gt,k + ut,k) + β(wt −wt−1);
Send wt+1 −wt to workers; end for
Let {wt}, {gt,k}, {ut,k} be the sequences produced by Algorithm 3, then we can get that
wt+1 =wt − ηt p∑ k=1 Mt,k(gt,k + ut,k) + β(wt −wt−1),
ut+1,k =(I−Mt,k)(gt,k + ut,k), k = 1, 2, . . . , p. By eliminating Mt,k, we obtain the same equation as that in (9). Hence our convergence analysis is also suitable for Algorithm 3. The difference from GMC is that the memory gradient ut,k 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 of correcting the update direction. Hence, GMC gets better performance than Algorithm 3. (Lin et al., 2018) also points out that Algorithm 3 has some loss of convergence performance.
Another way is that we put ηt in the memory gradient. We briefly present it in Algorithm 4.
Let {wt}, {gt,k}, {ut,k} be the sequences produced by Algorithm 4, then we can get that
wt+1 =wt − p∑ k=1 Mt,k(gt,k + ut,k)
ut+1,k =(I−Mt,k)(gt,k + ut,k), k = 1, 2, . . . , p. By eliminating Mt,k, we obtain the same equation as that in (9). Hence our convergence analysis is also suitable for Algorithm 3. However, the norm of memory gradient is larger than that of GMC. In particular, let yt,k = ut,k/ηt, then we have
yt+1,k = ηt ηt+1 (I−Mt,k)( 1 pb ∑ ξi∈It,k ∇f(wt; ξi)− β
pηt (wt −wt−1) + yt,k)︸ ︷︷ ︸
the same as the memory gradient of GMC
Algorithm 4 for t = 0, 1, 2, ...T − 1 do
Workers: for k = 1, 2 . . . , p, each worker parallelly do gt,k = ηt pb ∑ ξi∈It,k ∇f(wt; ξi)− β p (wt −wt−1);
Generate a sparse vector mt,k ∈ {0, 1}d; Send mt,k (gt,k + ut,k) to the server; ut+1,k = (1−mt,k) (gt,k + ut,k);
end for Server: wt+1 = wt − ∑p k=1 mt,k (gt,k + ut,k);
Send wt+1 −wt to workers; end for
If ηt is a constant, then Algorithm 4 is the same as GMC. If ηt is non-increasing, then ηt ≥ ηt+1 and
‖yt+1,k‖ ≥‖(I−Mt,k)( 1
pb ∑ ξi∈It,k ∇f(wt; ξi)− β pηt (wt −wt−1) + yt,k)‖.
Figure 5 shows the learning process of ResNet56 on CIFAR10. 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 4 is 10 fold of that in GMC. Hence, GMC is better than Algorithm 4 after training 80 epochs.

heading: C CONVERGENCE PROOFS
text: First, we introduce the Young’s Inequality as follow: ∀a, b
(a+ b)2 ≤ (1 + γ)a2 + (1 + 1 γ )b2,∀γ > 0,
which is used frequently in our proofs.
C.1 PROOF OF LEMMA 1
xt+1 =wt+1 + β
1− β (wt+1 −wt)− ηt+1 1− β ũt+1
= 1
1− β (wt+1 − βwt)− ηt+1 1− β ũt+1
= 1
1− β (wt − ηtũt − ηt∇f(wt; It) + β(wt −wt−1)− βwt + ηtũt+1)− ηt+1 1− β ũt+1
= 1
1− β (wt − βwt−1 − ηtũt − ηt∇f(wt; It) + ηtũt+1)− ηt+1 1− β ũt+1
= 1
1− β (wt − βwt−1 − ηtũt − ηt∇f(wt; It)) + ηt − ηt+1 1− β ũt+1
= 1
1− β (wt − βwt−1)− ηt 1− β ũt − ηt 1− β ∇f(wt; It) + ηt − ηt+1 1− β ũt+1
=xt − ηt
1− β ∇f(wt; It) + ηt − ηt+1 1− β ũt+1.
C.2 PROOF OF LEMMA 2 Since wt+1 −wt = ηt ∑p k=1 Mt,k(gt,k + ut,k), we have ∀γ > 0,
E‖wt+1 −wt‖2 ≤η2tE‖g̃t + ũt‖2
=η2tE‖β(wt−1 −wt)/ηt +∇f(wt; It) + ũt‖2
≤(1 + γ)β2E‖wt −wt−1‖2 + (1 + 1
γ )(2G2 + 2U2)η2t .
Let γ = 1β − 1, we get that
E‖wt+1 −wt‖2 ≤βE‖wt −wt−1‖2 + η2t
1− β (2G2 + 2U2)
≤2G 2 + 2U2
1− β (η2t + βη 2 t−1 + . . .+ β tη20).
If ηt = η, we get that E‖wt −wt−1‖2 ≤ (2G 2+2U2)η2
(1−β)2 . Then we obtain
E‖xt −wt‖2 ≤ 2β2
(1− β)2 E‖wt −wt−1‖2 +
2η2
(1− β)2 U2
≤[ 2β 2(2G2 + 2U2)
(1− β)4 +
2U2
(1− β)2 ]η2.
If ηt = r(t+q)ρ , ρ ∈ [0.5, 1], r > 0, q ≥ 0, let t0 satisfy ( t0+1+q t0+2+q )2ρ ≥ 1+β2 , A = maxt0t=1{ η2t+βη 2 t−1+...+β tη20 η2t+1
}. Then by induction, we get that E‖wt − wt−1‖2 ≤ (2G2+2U2) max{(1−β)A,2}η2t
(1−β)2 . Then we obtain
E‖xt −wt‖2 ≤ 2β2
(1− β)2 E‖wt −wt−1‖2 + 2η2t (1− β)2 U2
≤[ 2β 2(2G2 + 2U2) max{(1− β)A, 2}
(1− β)4 +
2U2
(1− β)2 ]η2t .
C.3 PROOF OF THEOREM 1
According to Lemma 1, we get that
E‖xt+1 −w∗‖2
=E‖xt −w∗‖2 − 2E[ ηt
1− β ∇f(wt; It)− ηt − ηt+1 1− β ũt+1] T (xt −w∗)
+ E‖ ηt 1− β ∇f(wt; It)− ηt − ηt+1 1− β ũt+1‖2
=E‖xt −w∗‖2 − 2E[ ηt
1− β ∇F (wt)− ηt − ηt+1 1− β ũt+1] T (xt −w∗)
+ E‖ ηt 1− β ∇f(wt; It)− ηt − ηt+1 1− β ũt+1‖2
≤E‖xt −w∗‖2 − 2ηt
1− β E∇F (wt)T (xt −w∗) + 2(ηt − ηt+1) 1− β EũTt+1(xt −w∗)
+ E‖ ηt 1− β ∇f(wt; It)− ηt − ηt+1 1− β ũt+1‖2
≤E‖xt −w∗‖2 − 2ηt
1− β E∇F (xt)T (xt −w∗) + 2ηt 1− β E(∇F (xt)−∇F (wt))T (xt −w∗)
+ 2(ηt − ηt+1)
1− β UD + 2G2η2t (1− β)2 + 2(ηt − ηt+1)2 (1− β)2 U2
≤E‖xt −w∗‖2 − 2ηt
1− β EF (xt)T (xt −w∗) + 2η2t 1− β
√ C(1−β)/µ,0,1,β,0LD
+ 2(ηt − ηt+1)
1− β UD + 2G2η2t (1− β)2 + 2(ηt − ηt+1)2 (1− β)2 U2. (16)
Using the strongly convex property, we get that
E‖xt+1 −w∗‖2
≤(1− 2 t )E‖xt −w∗‖2 + 2η2t 1− β
√ C(1−β)/µ,0,1,β,0LD
+ 2(ηt − ηt+1)
1− β UD + 2G2η2t (1− β)2 + 2(ηt − ηt+1)2 (1− β)2 U2
≤(1− 2 t )E‖xt −w∗‖2 + [2(1− β)
√ C(1−β)/µ,0,1,β,0LD + 2µUD + 2G 2 + 2U2] 1
µ2t2 .
Since E‖x1 −w∗‖2 ≤ D2, we get that
E‖xt −w∗‖2 ≤ A
µ2t ,∀t ≥ 1,
where A = max{µ2D2, 2(1−β) √ C(1−β)/µ,0,1,β,0LD+ 2µUD+ 2G
2 + 2U2}. Using (16) again, we get that
2E(F (xt)− F (w∗)) ≤ µt(E‖xt −w∗‖2 − E‖xt+1 −w∗‖2) + A
µt .
By summing up the equation from t = T −m to T − 1, we get that
2 T−1∑ t=T−m E(F (xt)− F (w∗))
≤ T−1∑
t=T−m [µt(E‖xt −w∗‖2 − E‖xt+1 −w∗‖2) +
A µt ]
≤µ(T −m)E‖xT−m −w∗‖2 + T−1∑
t=T−m (µE‖xt −w∗‖2 +
A µt )
≤µ(T −m)E‖xT−m −w∗‖2 + T−1∑
t=T−m
2A
µt
≤A µ + T−1∑ t=T−m 2A µt .
By setting m = dT/2e, we get that ∑T−1 t=T−m 1 t ≤ 1. Then
1
m T−1∑ t=T−m E(F (xt)− F (w∗)) ≤ 3A µT .
Since E[F (xt)− F (wt)] ≥ E∇F (wt)T (xt −wt) ≥ −G √ C(1−β)/µ,0,1,β,0 1−β µt , we get the result
1
m T−1∑ t=T−m E(F (wt)− F (w∗)) ≤ 3A+ 2G
√ C(1−β)/µ,0,1,β,0(1− β)
µT .
C.4 PROOF OF THEOREM 2
Similar to (16), we get that
E‖xt+1 −w∗‖2
=E‖xt −w∗‖2 − 2E[ ηt
1− β ∇f(wt; It)− ηt − ηt+1 1− β ũt+1] T (xt −w∗)
+ E‖ ηt 1− β ∇f(wt; It)− ηt − ηt+1 1− β ũt+1‖2
=E‖xt −w∗‖2 − 2E[ ηt
1− β ∇F (wt)− ηt − ηt+1 1− β ũt+1] T (xt −w∗)
+ E‖ ηt 1− β ∇f(wt; It)− ηt − ηt+1 1− β ũt+1‖2
≤E‖xt −w∗‖2 − 2ηt
1− β E∇F (wt)T (xt −w∗) + 2(ηt − ηt+1) 1− β EũTt+1(xt −w∗)
+ E‖ ηt 1− β ∇f(wt; It)− ηt − ηt+1 1− β ũt+1‖2
≤E‖xt −w∗‖2 − 2ηt
1− β E∇F (wt)T (wt −w∗) + 2ηt 1− β E∇F (wt)T (wt − xt)
+ 2(ηt − ηt+1)
1− β UD + 2G2η2t (1− β)2 + 2(ηt − ηt+1)2 (1− β)2 U2
≤E‖xt −w∗‖2 − 2ηt
1− β E(F (wt)− F (w∗)) + 2η2t 1− β
√ C1−β,1,0.5,β,0G
+ 2(ηt − ηt+1)
1− β UD + 2G2η2t (1− β)2 + 2(ηt − ηt+1)2 (1− β)2 U2. (17)
Since ηt = 1−β√t+1 , we get that
T−1∑ t=0 2√ t+ 1 E(F (wt)− F (w∗)) ≤‖w0 −w∗‖2 + T−1∑ t=0 A t+ 1
≤‖w0 −w∗‖2 +A log(T ), where A = 2(1− β) √ C1−β,1,0.5,β,0G+ 2UD + 2G 2 + 2U2.
C.5 PROOF OF THEOREM 3
Since F (·) is L-smooth, we get that EF (xt+1)
≤EF (xt)− η
1− β E[∇F (xt)T∇f(wt; It)] +
L 2 E‖ η 1− β ∇f(wt; It)‖2
=EF (xt)− η
1− β E[∇F (xt)T∇F (wt)] +
Lη2
2(1− β)2 E‖∇f(wt; It)‖2
≤EF (xt)− η
1− β E[‖∇F (wt)‖2 + (∇F (xt)−∇F (wt))T∇F (wt)] +
LG2η2
2(1− β)2
≤EF (xt)− η
1− β E[‖∇F (wt)‖2 − LG‖xt −wt‖] +
LG2η2
2(1− β)2
≤EF (xt)− η
1− β E‖∇F (wt)‖2 +
LG √ C0,0,1,β,ηη 2
1− β +
LG2η2
2(1− β)2
Summing up the above equation from t = 0 to T − 1, we get that
1
(1− β)T T−1∑ t=0 E‖∇F (wt)‖2 ≤ F (w0)− F (w∗) Tη +Aη,
where A = LG √ C0,0,1,β,η 1−β + LG2 2(1−β)2 .

heading: D MORE DISCUSSION ABOUT ASSUMPTION 2
text: In the convergence theorems, we need E‖ũt‖2 ≤ U2 (Assumption 2). Since ũt = ∑p k=1 ut,k, we only need E‖ut,k‖2 to be bounded which is mainly related to the choice of mt,k. Theoretically, we set one large threshold θ̃ > 0 in advance and we denote θst,k as the s-largest value of {|g (j) t,k+u (j) t,k||j = 1, . . . , d}. Then in each iteration, we can choose the values such that |g(j)t,k + u (j) t,k| ≥ min{θ̃, θst,k}. Then we obtain ‖ut,k‖2 ≤ dθ̃2 and hence E‖ut,k‖2 ≤ dθ̃2. In practice, the large threshold θ̃ is never been used for the choice of mt,k since θst,k θ̃.

heading: E MORE DISCUSSION ABOUT ASSUMPTION 3
text: If we do not use Assumption 3 in the proofs of Theorem 1 and Theorem 2, we can add one projection operation on equation (7), which can be written as
wt+1 = ΠΩ(wt − ηt p∑ k=1 Mt,k(gt,k + ut,k)),
where Ω = {w|‖w‖ ≤ W} and ‖w∗‖ ≤ W2 . Then wt is bounded. Hence, we reasonably assume that ∀t, i, ‖ũt‖ ≤ U , ‖∇f(wt; ξi)‖ ≤ G and we set ηt ≤ η0 ≤ (1−β)W2U . Please note that the U can be irrelevant to Ω according to Appendix D. We still define xt as
xt = wt + β
1− β (wt −wt−1)− ηt 1− β ũt.
Then xt is bounded as well.
To get the convergence results for strongly convex and convex functions, we need to prove two essential inequalities: E‖xt−wt‖2 ≤ O(η2t ) and ‖xt+1−w∗‖2 ≤ ‖xt−w∗− ηt 1−β∇f(wt; It) + ηt−ηt+1 1−β ũt+1‖ 2.
First, we get that ‖wt+1 −wt‖2 ≤ η2t ‖ ∑p k=1 Mt,k(gt,k + ut,k)‖2. According to the definition of Mt,k, we have ∀γ > 0,
‖wt+1 −wt‖2 ≤η2t ‖g̃t + ũt‖2
=η2t ‖β(wt −wt−1)/ηt +∇f(wt; It) + ũt‖2
≤(1 + γ)β2‖wt −wt−1‖2 + (1 + 1
γ )(2G2 + 2U2)η2t .
By setting γ = 1−ββ , we obtain ‖wt+1 −wt‖ 2 ≤ β‖wt −wt−1‖2 + 2G 2+2U2 1−β η 2 t . Then using the proof in Lemma 2, we obtain the first inequality that E‖xt −wt‖2 ≤ O(η2t ). Next, we get the relation between xt+1 and xt. According to the definition of xt, we have
‖xt+1 −w∗‖2 = ‖wt+1 + β
1− β (wt+1 −wt)− ηt+1 1− β ũt+1 −w∗‖2
= 1
(1− β)2 ‖wt+1 − (ηt+1ũt+1 + βwt + (1− β)w∗)‖2.
Since ‖ũt‖ ≤ U uniformly and ‖w∗‖ ≤ W2 , ηt ≤ η0 ≤ (1−β)W 2U , we get that
‖ηt+1ũt+1 + βwt + (1− β)w∗‖ ≤ηt+1U + βW + (1− β) W
2 ≤W.
Then we obtain ηt+1ũt+1 + βwt + (1− β)w∗ ∈ Ω and
‖xt+1 −w∗‖2 ≤ 1
(1− β)2 ‖wt − ηt p∑ k=1 Mt,k(gt,k + ut,k)− (ηt+1ũt+1 + βwt + (1− β)w∗)‖2
= 1
(1− β)2 ‖wt − ηt(g̃t + ũt − ũt+1)− (ηt+1ũt+1 + βwt + (1− β)w∗)‖2
=‖xt −w∗ − ηt
1− β ∇f(wt; It) + ηt − ηt+1 1− β ũt+1‖2.
Then similar to the analysis in Theorem 1 and Theorem 2, we can prove the convergence for strongly convex and convex cases.

Review summaries:
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:

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.