Delay-Tolerant Local SGD for Efficient Distributed Training
Authors: An Xu
Xiao Yan
Hongchang Gao
Heng Huang
Venue:  (2021)
Keywords: Delay-tolerant
communication-efficient
distributed learning

Abstract: The heavy communication for model synchronization is a major bottleneck for scaling up the distributed deep neural network training to many workers. Moreover, model synchronization can suffer from long delays in scenarios such as federated learning and geo-distributed training. Thus, it is crucial that the distributed training methods are both \textit{delay-tolerant} AND \textit{communication-efficient}. However, existing works cannot simultaneously address the communication delay and bandwidth constraint. To address this important and challenging problem, we propose a novel training framework OLCO\textsubscript{3} to achieve delay tolerance with a low communication budget by using stale information. OLCO\textsubscript{3} introduces novel staleness compensation and compression compensation to combat the influence of staleness and compression error. Theoretical analysis shows that OLCO\textsubscript{3} achieves the same sub-linear convergence rate as the vanilla synchronous stochastic gradient descent (SGD) method. Extensive experiments on deep learning tasks verify the effectiveness of OLCO\textsubscript{3} and its advantages over existing works.

Under review as a conference paper at ICLR 2021
DELAY-TOLERANT LOCAL SGD FOR EFFICIENT DIS- TRIBUTED TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
The heavy communication for model synchronization is a major bottleneck for scaling up the distributed deep neural network training to many workers. More- over, model synchronization can suffer from long delays in scenarios such as fed- erated learning and geo-distributed training. Thus, it is crucial that the distributed training methods are both delay-tole toterrttt AND communication-effiien existing works cannot simultaneously address the communication delay and band- width constraint. To address this important and challenging problem, we propose novel training framework OLCO; to achieve delay tolerance with low com- munication budget by using stale information. OLCO₂ introduces novel staleness compensation and compression compensation to combat the influence of stale- ness and compression error. Theoretical analysis shows that OLCO; achieves the same sub-linear convergence rate as the vanilla synchronous stochastic gradient descent (SGD) method. Extensive experiments on deep learning tasks verify the effectiveness of OLCO, and its advantages over existing works.
However,
INTRODUCTION
Data mata-parallel synchronous SGD is currently the workhorse algorithm for large-scale distributed deep learning tasks with many workers (e.g. GPUs), where each worker calculates the stochastic gradient on local data and synchronizes with the other workers in one training iteration (Goyal et al., 2017] You et al. 2017: Huo al., 2020). However, high communication overheads make inefficient to train large deep neural networks (DNNs) with a large number of workers. Generally speaking, the communication overheads come in two forms: 1) high communication delay due to the unstable network or a large number of communication hops, and 2) large communication budger caused by the large size of the DNN models with limited network bandwidth. Although communication delay is not prominent problem for the data center environment, it can severely degrade training efficiency in practical scenarios, egg. when the workers are geo-distributed or placed under different networks (Ethernet, cellular networks, Wi-Fi, etc.) in federated learning (Konečný et al. 2016).
Existing works to address the communication inefficiency of synchronous SGD can be roughly clas- sified into three categories: 1) pipelining SPi (Li ct al. (018)); 2) gradient compression (Aji
& Heafield 2017 Stich et al. 2018 Alistarh et al. 2018 Yu et al. 2018 Vogels et al. 2019): and 3) periodic averaging (also known Local SGD) (Stich 2019 Lin et al. 2018a). In pipelining, the
model update uses stale information such that the next iteration does not wait for the synchroniza- tion of information in the current iteration update the model. As the synchronization barrier is re- moved, pipelining can overlap computation with communication to achieve delay tolerance. Gradi- ent compression reduces the amount of data transferred in each iteration by condensing the gradient with a compressor C(.). Representative methods include scalar quantization (Alistarh et al. 2017: Wen et al. 2017: Bernstein et al.) 2018), gradient sparsification (Aji & Heafield 2017| [Stich al, Alistalistarh et 2018)) and vector quantization YYu et al. [018)] Vogels et al. 2019). Periodic
2018 Alistarh averaging reduces the frequency of communication by synchronizing the workers every p (larger than 1) itteaaions. Periodic averaging is also shown to be effective for federated learning (McMahan et al. 2017). In summary, exiting works handle the high communication delay with pipelining and gradient compression and periodic averaging to reduce the communication budget. However, all existing methods fail to address both. It is also unclear how the three communication-efficce techniques introduced above can be used jointly without hurting the convergence of SGD.

---

Under review as a conference paper at ICLR 2021
Table 1: Comparison of communication-effiicenn methods for distributed DNN training. The period E 4 is the communication interval for periodic averaging. The staleness E N is the number of communication rounds that the information used in the model update has been outdated for. For all methods in this table, delay tolerance T T= sp.
Overlap Comput. with Comm.
Comm. Compression
p Iterations per Comm. Round
Staleness s Supported
Methods
Gradient Compression
X
1
0
Periodic Averaging (Local SGD)
X
X
> 1
Pipelining (Pipe-SGD)
V
X
CoCoD-SGGD
X
1
OverlapLocaISGD
1
OLCO; (Ours)
V 21
In this paper, we propose a novel framework Overlap Local Computation with Compressed Communication (i.e., OLCO;) to make distributed training both delay-tolerant AND communi- cation efficient by enabling and improving the combination of the above three communication- efficient techniques. In Table T we compare OLCO; with the aforementioned works and two succeeding state-of-the ofrthh-art delay-tolerant methods CoCoD-SGD (Shen et al.) 2019) and OverlapLo- denote the num-
calSGD (Wang et al.) (2020). Under the periodic averaging framework, we ber of local SGD iterations per communication round, and 8 to denote the number of communication rounds that the information used in the model update has been outdated for. Let the computation time of one SGD iteration be T computt then we can pipeline the communication and the computation when the communication delay time is less than sp ' computt. For simplicity, we define the delay tolerance of a method as T sp. Local SGD has to use up-to-date information for the model update 0. 2 T, = sp 0). CoCoD-SGI and OverlapLocalSGGD combine pipelining and periodic averaging by using stale results from last communication round (s = 1. 2 T. sp p). while our OL OI,CO; supports various staleness (s 2 1. 2 1, sp) and all other features in Table The main contributions of this paper are summarized as follows:
We propose the novel OLCO; method, which achieves extreme communication efficiency by addressing both the high communication delay and large communication budget issues.
OLCO, introduces novel staleness compensation and compression compensation techniques. Convergence analysis shows that OI.CO; achieves the same convergence rate as SGD,
Extensive experiments on deep learning tasks show that OLCO; significantly outperforms ex- isting delay-toleram methods in both the communication efficiency and model accuracy.
BACKGROUNDS & RELATED WORKS
SGD and Pipelining. In distributed training, we minimize the global loss function f(-) K Ek fe(-), where fe(-) is the local loss function at worker k E [K]. At iteration t, vanilla synchronous SGD updates the model X, Rd with learning rate Tr via X++1 Tt ΣK (x:(x,; (*)) where (AA) is the stochastic sampling variable and Fx, ((4)) is the corresponding stochastic gradient worker k. Throughout this paper, assume that the stochastic gradient is an unbiased estimator by default, i.e., B,! F, (())) (x,,
Pipe-SGD Li et al. 2018) parallelizes the communication and computation of SGD via pipelin- ing. At iteration f, worker h computes stochastic gradient V (x:; F c(()) current model x, and communicates to get the averaged stochastic gradient + Σk=
1= F cf( (*))). Instead of waiting
the communication finish, Pipe-SGI concurrently updates the current model with stale averaged
V (x (1))) Note that Pipe-SGD is different from asynchronous SGD (Ho et al. 2013 Lian et al. 2015) which computes stochastic gradient ing stale model and does not parallelize the computation and communication of a worker. A problem of Pipe-SGD is that its performance deteriorates severely under high communication delay (large s).
stochastic gradient via X = X; The
(k),
2

---

Under review as a conference paper at ICLR 2021
Pipelining with Periodic Averaging. CoCoD-SGD (Shen et al. 2019) utilizes periodic averaging to reduce the number of communication rounds and parallelizes the local model update and global model averaging by concurrently conducting
K
stp-1
X
and L+D X,
Σ V )..)
(1)
K
k=
which x denotes the local model at worker i as the local models on different workers are no longer consistent in non-communicating iterations. When the operations in Eq. ① finishes, the local model is updated via x+p + X, + x x(x) and < t p. CoCoD-SGD can tolerate delay up to SGD iterations (i.e., one communication round in periodic averaging). OverlapLocaISGD (Wang
(k)
al. 2020 improves CoCoD-SGD by heuristically pulling x back to the X, after the operations
in Eq. via X+pp (1 az) xx)x + ax, where 0 S < 1. The motivation is reduce the inconsistency in the local models across workers. OverlapLocalSGD also develops a momentum variant, which maintains slow momentum buffer for x, following SlowMo (Wang et al. 2019). As both CoCoD-SGi and OverlapL.oaaIGGD communicates the non-compressed local model update, they suffer from a large communication budget in each communication round.
(A)
Gradient Compression. The gradient vector E Rd can be sent with much smaller communica- tion budget by applying a compressor C(.). Specifically, Scalar quantization rounds 32-bit floating- point gradient components to low-precision values of only several bits. One important such algo- rithm is scaled SignSGD (called SignSGD in this paper) (Bernstein et al.) 2018: Karimireddy et al.)
2019) which uses C(v) = ||vil sign(v) to compress v to 1 bit. Gradient sparsification only commu- micates large gradient components. Vector quantization uses a codebook where each code a vector and quantizes the gradient vector as a linear combination of the vector codes. With the local error feedback technique (Seide al., 2014, Lin et al., 2018b Wu et al., 2018: Karimireddy et al. 2019, Zheng et al. 2019), which adds the previous compression error (i.e., C(v)) to current gradient before compression, gradient compression can achieve comparable performance as full-precision training. Local error feedback also works for both one-way compression (compress the communi- cation from worker to sever) (Karimireddy et al.) 2019) and Iwo-way compression (compress the communication between worker and server) (Zheng et al. 2019).
Challenges. Simultancously achieving communication compression with pipelining and periodic averaging requires careful algorithm design because 1) pipelining introduces staleness, and 2) state- of-the-art vector quantization methods usually require an additional round of communication to solve the compressor C(-), which is unfavorable in high communication delay scenarios.
3 THE PROPOSED FRAMEWORK: OLCO3
In this section, we will introduce our new delay-tolcrant and communication-efficcaee training frame- work OLCO, We discuss two variants of OLCO3: OLCO,-TC for two-way compression in master- slave communication mode, and OLCO,-VO -VQ adopting commutative vector quantization for both the master-slave and ring all-reduce communication modes. Note that one-way compression in just special case of OLCO,-TC and we omit it for conciseness. We use "line x" to refer to the x-th line of Algorithm I
The key differences between OLCO3-TC and OLCO, VQ are marked in red color.
3.1 OLCO,-TC FOR TWO-WAY COMPRESSION
Motivation. OL is presented in the green part of Algorithm I for efficient master-slave distributed training. Naively pipelining local computation with compressed communication will break the update rule of momentum SGD for the averaged model x, = Σ (k) leading to non- convergence. Therefore, we consider an auxiliary variable x, ==
(k) -e.
where c is the local compression error at worker k and e; is the compression error at the server. If & can follow the update rule of momentum SGD, then the real trained model x, will gradually approach &, as the training converges because the gradient and errors e,
(k) e + 0.
Pipelining. For non communimuni iterations, we perform the local update following Local SGD (line 4). A communicating iteration takes place every p iterations. To pipeline the communication
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Overlap Local Computation with Compressed Communication (OLCO;) worker E [K]. Green part: OLCO;-TC; Yellow part: OLC Best view in color.
1: Input: period p 2 1, staleness 2 0, number of iterations T, number of workers K, learning
rate fmo 1- and compression scheme C(-).
2: Initialize: Local model x Nu. local error ej
(k) server error ep 0, local momentum
buffer m ( 0, and momentum constant < < 1. Variables with negative subscripts are O.
(A)
3: for 0, 1,1,... ... (A)
do
(k), p + (x; 55
4: mi
=
I/ Momentum Local SGD.
5:
if (++1) mod p then
6:
Maintain or reset the momentum buffer.
7:
((A) = x x
(k)
(k)
+ e (k)
// Compression compensation.
8:
e e.42 = ................................ t-p = A C(A,
(k) [k]
(k)
// Compression.
9:
Invoke the communication thread in parallel which does:
(1) Send c(A(41) to and receive C( ((A(+)) from the server node.
10:
(R) (2) Server: A++1 R Ek= ((A (+1) + eq; ec+1 = et+2 ectp = Ait1
11:
(.).
12:
Block until C(A++1-sp is ready.
13:
X++1 = Xt+1-p - ((A(+1-sp)
14:
(R)
+ X(+1 Σラ = C(A (11
1
(R)
I/ Staleness compensation.
15:
A =x++1-p +1 + e
(k)
(k)
(A)
// Compression compensation.
Invoke the communication sp
16:
in parallel which does:
17:
(1) e = e44 _... etpp (R) C(A,1))
(k)
(k)
// Compression.
(2) Average 1 > ((A
(k)
18:
K
(+1 by ring all-reduce or master-slave communication.
Block until R -k=1 C(A (1-sp)) and (k)) cp is ready.
(K)
X1+1 X(+1-p # Σx= C(A (k)
(+1-sp)
x f- X(+1 Σi=o 141-ip
(k)
(k)
// Staleness compensation.
22:
end if
23:
end for
24:
Output: averaged model Xy - Ek=1
EK
(K)
and computation, we compress the local update 1+1 (line 7) for efficient communication, and at the same time, try to update the model with a stale compressed global update C C(A++1-sp) (line 13) that has been outdated for communication rounds (i.c., the staleness is s). The momentum buffer can be maintained or reset to zero every p iteration (line 6). If the delay tolerance T sp is larger than the actual communication delay, the blocking in line 12 becomes no-op and there will be synchronization barrier. The server compresses the sum of the compressed local updates from all workers (line 11) and sends it back, making OLCO,-TC an efficient two-way compression method.
(k)
Compensation. To make the update of the auxiliary variable & follow momentum SGD, we propose !) compensate staleness with all compressed local updates with staleness [0, s 1] (line 14), which requires no communication and allows less stale local update to affect the local model, and 2) maintain a local error (line 8) and add it to the next local update before compression (line to compensate the compression error. With the two compensation techniques in OLCO,-TC, Lemma shows that the update rule of x, follows momentum SGD with averaged momentum
Σk= m
Lemma 1. For OLCO,-TC, let E, 1 Σ x n1 EK
(k)
K
et
et-sp- then we have X,
k1=1" m (K)
Note that there is a "gradient mismatch" problem as the local momentum m, computed at the local model (k) but used in the update rule of the auxiliary variable (Karimireddy et al. 2019 Xu ct al. 2020). However, our analysis shows that it does not affect the convergence rate. We have also considered OLCO, for one-way compression (i.e,, OCC special case of OLCO,-TC. In
4

---

Under review as a conference paper at ICLR 2021
OLCOs-OC, the compressor at the server side is identity function and the server is 0. For OLCO;-OC, the auxiliary variable x also follows momentum SGD as stated in Lemma
then we have X Xt-1 Lemma 2. For OLCO;-OC, let & = R x R E Th-1
Σk 1k=1 (k) K
We can see that the delay tolerance of both OLCO3-TC and OLCO;-OC are T =s{s 2 1. 2 1).
They have memory overhead of (sdd) for storing information with staleness E 10, 1|. For most compression schemes such as SignSGD, the computation complexity of C(.) is (d)..
3.2 OLCO3-VO FOR COMMUTATIVE VECTOR QUANTIZATION
OLCO3-TC and OLCO0-OC work for compressed communication in the master-slave communi- cation paradigm. In contrast, OLCO,-VQ (the yellow part of Algorithm [ works for both the master-slave and ring all-reduce communication paradigms. Ring all-reduce minimizes communi- cation congestion by shifting from centralized aggregation in master-slave communication (Yu et al. 2018 OLCO, VQQ relies on state-of-the-a tfethheart vector quantization scheme, PowerSGD (Vogels al, 2019 which satisfies commutability for compression, i.e., C(v1) + C(v2) = C(vi + V2). However, directly using PowerSGID breaks the delay tolerance of OL.C33 as its compressor C(-) needs commu- nication and introduces synchronization barriers. Specifically, PowerSGI invokes communication across all workers to compute a transformation matrix, which used to project the local updates to the compressed form.
Pipelining with Communication Deneedeenn Compressor. To make OL delay-tolerant, further propose novel compression compensation technique with the stale local error (line 15). This is contrast to OLCO,-TC and OLCO,-OC, which use immediate compressed results to calculate the up-to-date local error. As this technique removes the dependency on immediate compressed results, we can move the whole compression and averaging process to the communica- tion thread (lines 17 and 18). For staleness compensation, OLCO,-VQ uses all uncompressed local updates with staleness E [0, s--1 instead of compressed local updates in OLCO,-TC. With the two compensation techniques, Lemma 3 shows that for OLCO,-VQ, the auxiliary variable & associated with the stale local error also follows the momentum SGD update rule.
Lemma 3. For OLCO,-VO, l = Ek Tt
(k) 1 Ek e then we have X, K,-1
K
k=1 m (k)
4 THEORETICAL RESULTS
In this section, we provide the convergence results of the OLCO; variants for both SGD and momen- tum SGD maintaining momentum (line 6 of Algorithm 1 with common assumptions. As OLCO3- OC is a special case of -LC we only analyze OLCO,-TC and OLCO.-VQ. The detailed proofs of Theorems 2 and 4 can be found in Appendix D and G respectivey. The de- tailed proofs of Lemma and can be found Appendix
use J. to denote the optimal
loss.
Assumption 1. (L-Lipschitz Smoothness) Both the local (f)(-)) and global (f() EK fu(-)) loss functions are L-smooth, i.e.,
[Vx(x) vf6) S L||x yl12. Vx, E
--|x- -yll2, Vk [K], Vx. Ed Assumption 2. (Local Bounded Variance) The local stochastic gradient V Fx,xx; E) has bounded variance, iee, EE-D, [VFx(x; - (x(x)) < o2 E [K], Vx E Rd. Note that EgnDs (F((x:)) = fx(x).
(x)xx) ff(r))l22 S -
(3)
Assumption 3. (Bounded Variance across Workers) The L2 norm of the difference of the local and global full gradient is bounded, i.e., fx ff(x) < R2 vk [K], vx E Rd. K 0 leads to i.idd data distributions across workers.
Assumption 4. (Bounded Full Gradient) The second moment of the global full gradient is bounded,
i.e. (x) < G2, Vx E Rdd.
Assumption 5. (Karimireddy et al. approximate compressor for 8 <
2019 The compression function C(-) : =Rd + R a 8-
for all v Rdd, [[C(y) - -11 < 8)111113
5

---

Under review as a conference paper at ICLR 2021
4.1 SGD
Theorem 1. For OLCO,-VO VQ with vanilla SGD and under Assumptions 7 2 3
and if the
learning rate rj I 1 76 b then
K
((f(x)) - (-)
9nI.0²
V
E
1/T +
+ +12n) 1)po 1+
(4)
T
K
K
-
k=
14(1
6)
5(1
- 6)
168(1 1 8)
82 (s + 1)p] 36n2 [.2 + 1)20²
+
1/ (5 1)2
82
82
If set the learning rate 7 O(K and the communication interval p OK- + 1)-"), the convergence rate will be O 9)). The O(- rate is the same as syn- chronous SGD and Local SGD, and achieves linear speedup regarding the number of workers K.
Theorem 2. For OLCO,-TC with vanilla SGD and under Assumptions
L 2
and S if the
learning rate 1j I minf 61 91 and let h(6) 1
1 (1 1(2-6) ). then
T T
K K
6(f(xo) -fa) n/T +
OnLo²
K
(5)
12n p (s + 1 + 80)())p) + p2n (3(s + 1)² + 80)( + 960m)'²
If we set the learning rate 7 O(K and the communication interval OKK + 1)- the convergence rate will be O(K カ1). When the data distributions across workers
i..dd (i.e., K 0), if we choose the learning rate 1 = O à 2 and the communication interval p = min - 9 (s + o O(K
(p = o(--kkk for enough large 7) instead, the convergence rate will still be O
Therefore, OLCO,-TC can tackle a larger communication interval p (O(K-rr)) than OLCO3- VQ (s+
+ 1)) in the i.i.d. setting. But they are the same in the non-i.i.d setting.
4.2 MOMENTUM SGD
Theorem 3. For OLCO,-VQ with Momentum SGD and under Assumptions
3
4
if the then
learning rate n < min Vr2L(+t15p' 1 } and let g(H, 5, s,
[-ル}² 60(1
15
K
6(1 (x))) - fc) <
Σ 1=0
+ (1- 11)
(6)
T
K
k=1
4nj" 2
(1 m2) [[4(s + l)y - g(v, ó, 8, 8)))) - (12(s + 1)? + g(u, 8, 8, s, + +lu, 6, p.
Theorem 4. For OLCO,-TC with Momentum SGD and under Assumptions
2
3
4
if the
learning rate rj S min V721(>+1>p' 1/1) and h(()) 1-8 (1 + 1(2-5)
1-p
then
82
Σ E
|1 Σ
1
x 112
(k)
6(1
(f f.)
oond
2,2
9
+ (1 k
+
1021
+ 2(ss + 1)p + 168h(5)p²)
n/f
(1 - 21²
(1
[1=
9
9
+ x2(
p1- + 6(ss + 1)2p² 168h(6)p²)) O2(
+ 168h(8)p")]
(1- n)²
The same convergence rate and communication interval p are achieved in Section 4.1

---

Under review as a conference paper at ICLR 2021
ResNet-110, CIFAR-10
ResNet-50, ImageNet
90
70
Test Accuracy (%)
Test (%)
60
80
50-
70:
5GD
Local
CoCoD-SGD
CoCoD-SGD
30
60
DyerlapLocaISGD
Overlapl.calSGG
OLCOy-OC
OLCO,-OC
50
VL
OLC
10
OLCO2-TC
OLCO,-TC
40
0
50
125 150 Epoch
100
175
200
40
80
100
120
Epoch
ResNet-110, CIFAR-10
ResNet-50, ImageNet
90
70
Test Accuracy (%)
Test Accuracy (%6
60-
80
50
70
40
Local SGD
CoCoD-SGD
CoCoD-SGD
30
60
DverlapLocaISGD
OverlapLocaISGD
OLCOy-OC
20
OLCO;-0C
50
OLC
OLCO;-VO
10:
OLCO3-TC
OLCO;-TC
40
0.0
0.1
0.3 0.4
0.6 0.7
50 Communication Budget (GB)
20
80
Communication Budget (GB)
Figure 1: Training curves using T = 56 and s = 1 for the delay-tolerant methods, and T = 0 and
p 56 for Local SGD, Test accuracy can be found in Appendix A.3 Best viewed in color.
ResNet-110, CIFAR-10
ResNet-110,
Local 5GD
CoCoD SGD
OLDO OC
Local SCID
CoCoD SGD
-L00-00C
Accuracy
93.0
OverapLocaS50
OLCO,-TC
Testing Accuracy
93.0
OverlapLocalSGD
OLCO,-TC
92.5
92.5
92.0
92.0
91.5
91.0
91.0
90.5
90.5
90.0
90.0
100
120
Delay Tolerance T
Staleness
Figure/ 2: Left: Vary delay tolerance T = sp with staleness fixed at s = 1. Local SGD uses the same p the delay-tolerant methods but has T 0. Right: Vary staleness with delay tolerance fixed at T = 56. Results for more configurations s and p can be found Appendix A.4
EXPERIMENTS
We compare the following methods: Local SGD (baseline, NO delay tolerance with 0); 2) Pipe-SGD; 3) CoCoD-SGD; 4) OverlapLocalSGD with hyperparameters following Wang et al. (2020) ; 5) OLCO, OC with SignSGD compression; 6) OLCO,-VO with PowerSGID compressoin; 7) OLCO, TC with SignSGD compression. The momentum buffer is maintained (line of Algo- rithm D by default. We do not report the results Pipe-SGD as does not converge for the large delay tolerance T we experimented. We train R 10 (He et al. 2016) with 8 workers for the CIFAR-10 (Krizhevsky et al. 2009) image classification task, and report the mean and standard deviation of the test accuracy over 3 runs in both the i.i.d. and non-i.i.d setting. We also train ResNet-50 with 16 workers for the ImageNet (Russakovsky et al. 2013) image classification task. More detailed descriptions of the experiment configurations be found in Appendix A.1

---

Under review as a conference paper at ICLR 2021
Table 2: Non-i... test accuracy (%) of ResNet- 110 on CIFAR-10. T
56 for the delay-tolerant methods, and T 0 and p 56 for Local SGD, Training curves can be found in Appendix A.2
Method
Delay Tolerance T Compression Ratio
ResNet110
Local SGD
89.93 = 0.08
Pipe-SGD
56
Diverges
CoCoD-SGD
56
87.73 + 0.25
OverlapLocaISGD
56
88.97 + 0.19
OLCO,-OC
+ 1/32
89.75 + 0.21
OL,
56
0.0973
89.31 + 0.08
OL.CO,-TC
56
1/32
89.73 + 0.25
Delay Tolerance with Lower Communication Budget. The training curves of ResNet-110 on CIFAR-10 and ResNet-50 on ImageNet are shown in Figure We use because CoCoD-SGID and OverlapLocaISGD do not support > 2. Compared with other delay-tolerant methods, the communication budget the OLCO; variants is significantly smaller due to compressed commu- nication. OLCO, is also robust communication delay with a large T = sp. Therefore, OLCO, features extreme communication efficiency with compressed communication, delay tolerance, and low communication frequency due periodic averaging.
The two plots the first row of Figure D show that OLCO;-OC and OLCO3-TC outperforms other delay-tolerant methods and comparable Local SGD regarding the model accuracy. The performance of OLCO,-VQ is similar to CoCoD-SGD but inferior to Over- lapLocaISGD. However, in the non-i.i.d. results reported in Table all OLCO3 variants outperform existing delay-tolerant methods in accuracy. This is in line with the theoretical results in Theorems 123 and which show that OLCO, TC can tackle larger p than OLCO, VQ in the i.i.d. setting but the two methods are similar in the non-i.idd setting. In the non-i.i.d setting, all OLCO, variants perform very close to Local SGD, On average, OL.CO,-C and OLCO0,TC improve the test aceu- racy of CoCoD-SGI and Overlapl.ocalSGGD LocalSGD by 2.0% and 0.8%, respectively. OL,CO, improves CoCoD-SGD and OverlapLocalSGGD by 1.6% and 0.4%. These results empirically confirm that the staleness compensation and compression compensation techniques in OLCO; are effective.
Better Model Performance.
Varying Delay Tolerance. We vary the delay tolerance T with staleness fixed = in the left plot of Figure The goal is to check the robustness of OLCO, to the different period p. The results show that OLCO,-OC and OLCO,-TC always outperform other delay-toleram, methods, and have more comparable performance to Local SGD. Note that both the OLCO;-OC and OLCO3- TC provide a significantly smaller communication budget according to Figure I OLCCO, also outperforms CoCoD-SGD with much smaller communication budget.
Varying Staleness. We vary the staleness s of OLCO; in the right plot of Figure under fixed delay tolerance T. Local SGD only supports
0 with no delay tolerance, and CoCoD-SGD and Over- lapLocaISGD only support = 1, so there is only one result for them in the figure. When increasing the staleness beyond 2 for OLCO,, the deterioration of the model performance is very small, es- pecially for OLCO,-VQ. This suggests that the staleness compensation techniques in OLCO, are effective. The performance peaks at s because an appropriate staleness may introduce some noise that helps generalization. In comparison, we cannot tune staleness for better performance in CoCoD-SGD and OverlapLocalSGD.
CONCLUSION
In this work, we proposed a new OLCO; framework to achieve extreme communication efficiency with high delay tolerance and low communication budget in distributed training. OLCO; uses novel staleness compensation and compression compensation techniques. and the theoretical results show that it converges fast vanilla synchronous SGD. Experimental results show that OLCO; significantly outperforms existing delay-tolerant methods in terms of the communication budget and model performance.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alham Fikri Aji and Kenneth Heafiel. Sparse communication for distributed gradient descent. arXiv preprint (XXx:1704.0002... 2017.
Dan Alistarh, Demjan Grubic, Jerry Li. Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-efficii sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, pp. 5973-5983, 2018.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, vol- ume 80 of Proceedings of Machine Learning Research, pp. 560-569, Stockholmsmässan, Stock- holm Sweden, 10-15 Jul 2018. PMLR. URL http: htt.http:: ngg.. http:/rrccceiiinnn...rrrrrreeeee w.t.rsssrres.//
bernstein1 ntml
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint (tlv:/706.266600 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and patlern recognition, pp. 770-778, 2016.
Qirong Ho, James Cipar, Henggang Cui, Seunghak Lee, Jin Kyu Kim, Phillip B Gibbons, Garth A Gibson, Greg Ganger, and Eric P Xing. More effective distributed ml via stale synchronous parallel parameter server. Advances in neural information processing systems, pp. 1223-1231, 2013.
Zhouyuan Huo, Bin Gu, and Heng Huang. Large batch training does not need warmup. arXiv preprint arXiv:2002.01576 2020.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. International Conference on Machine Learning. pp. 3252-3261 2019.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492. 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Youjie Li, Mingchao Yu, Songze Li, Salman Avestimehr, Nam Sung Kim, and Alexander Schwing. Pipe-sgd: A decentralized pipelined sgd framework for distributed deep net training. In Advances in Neural Information Processing Systems, pp. 8045-8056, 2018.
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 2737-2745 2015.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches. use local sgd. arXiv preprint arXiv:1808 07217, 2018a
Yujun Lin, Song Han, Huizi Mao, Yu Wang. and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference on Learning Representations, 2018b. URL /tttt:::///peeevieee net/ feee/forrnee worumorriiiooooo SKhOHMwOR
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:/608 0039833. 2016.

---

Under review as a conference paper at ICLR 2021
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273 1282. PMLR, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems, pp. 8024-8035, 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):21122555) 252, 2015. doi: 10.1007/s1 1263-015-08816..
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-pan aatalparallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Shuheng Shen, Linli Xu, Jingchang Liu, Xianfeng Liang, and Yifei Cheng. Faster distributed deep net training: Computation and communication decoupled stochastic gradient descent. arXiv preprint arXiv: 12043, 2019.
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Confer- ence on Learning Representations, 2019. URL htttp::
font/forrmmidd
S1g2JnRcFX
Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In 2018.
Advances in Neural Information Processing Systems, pp.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems, pp. 14259-14268, 2019.
Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving
communication-efficent distributed sgd with slow momentum. arXiv preprint 1rrXiv:/90000000 2019.
Jianyu Wang, Hao Liang, and Gauri Joshi. Overlap local-sgd: An algorithmic approach hide communication delays in distributed sgd. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8871-8875. IEEE, 2020.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temggad:: Terary gradients to reduce communication in distributed deep learning. In Advances in neural information processing systems, pp. 1509-1519, 2017.
Jaxiann Wu, Weidong Huang. Junzhou Huang, and Tong Zhang. Error compensated quantized sgd and its applications to large-scale distributed optimization. arXiv preprint arXiv:1806.0805: 2018
An Xu, Zhouyuan Huo, and Heng Huang. Training faster with compressed gradient. arXiv preprint 2xXiv:0008.0582. 2020.
Yang You, Igor Gitman, and Boris Ginsburg. Scaling sgd batch size to 32k for imagenet training. arXiv preprint arXiv: 170.00088,88 6, 2017.
Mingchao Yu, Zhifeng Lin, Krishna Naraa, Songze Li, Youjie Li, Nam Sung Kim. Alexan- der Schwing, Murali Annavaram, and Salman Avestimehr. Gradiveq: Vector quantization for handwidth-effiiien gradient aggregation in distributed cnn training. In Advances in Neural Infor- mation Processing Systems, pp. 5123-5133, 2018
Shuai Zheng, Ziyue Huang, and James Kwok. Communication-cfficn distributed blockwise mo- mentum sgd with error-feedbcck. In Advances in Neural Information Processing Systems, pp. 11446-11456, 2019.
10

---

Under review as a conference paper at ICLR 2021
A ADDITIONAL EXPERIMENTAL RESULTS
A.1 EXPERIMENTAL SETTING
All experiments are implemented with PyTorch (Paszke et al., 2019) and run on a cluster Nvidia Tesla P40 GPUs. Each node is connected by 40Gbps Ethernet and equipped with 4 GPUs.
CIFAR. We train the ResNet- 11 10 (He et al. 2016 model with 8 workers on CIFAR- (Krizhevsky
al. 2009) image classification task. We report the mean and standard deviation metrics over
runs. The base learning rate 0.4 and the total batch size is 512. The momentum constant is 0.9
and the weight decay 1 10-4. The model trained for 200 epochs with a learning rate decay of 0.1 at epoch 100 and 150. We linearly warm up the learning rate from 0.05 to 0.4 the beginning epochs. For OLCO3 with staleness E (2, 4,8), staleness. The rank of PowerSGD is 4. Random cropping, random flipping, and standardization are applied as data augmentation techniques. We also train ResNet-56 explore more combinations of and p in Appendix A.4 with the same other settings.
the base learning rate to 0.2 due increased
ImageNet. We train the ResNet-50 model with 16 workers on ImageNet (Russakovsky et al. 2015) image classification tasks. The model is trained for 120 epochs with a cosine learning rate schedul- ing (Loshchilov & Hutter 2016). The base learning rate is 0.4 and the total batch size is 2048. The momentum constant is 0.9 and the weight decay is 10-1 We linearly warm up the learning rate from 0.025 to 0.4 in the beginning 5 epochs. The rank PowerSGD is 50. Random cropping, applied as data augmentation techniques.
random flipping, and standardization
The Non-i.i.d Setting. Similar to (Wang et al. 2020), we randomly choose fraction a of the whole data, sort the data by the class, and evenly assign them to all workers in order. For the rest fraction (1 a) of the whole data, we randomly and evenly distribute them to all workers F). When 0 1 is large, the data distribution across workers is non-i.i.d and highly skewed. When = 0, becomes i.d. data distribution across workers. In our non-i.id. experiments, we choose
0.8.
Fraction=a. Sorted by class. Evenly divided to K workers.
Fraction=1-a Randomly mixed and evenly divided to K workers.
Class 1
Class 2
Class
Worker
Worker
Worker
Worker
Figure 3: Non-L.i. data partition across workers. Best viewed in color.
11

---

Under review as a conference paper at ICLR 2021
A.2
TRAINING CURVE
ResNet-110, CIFAR-10
ResNet-50, ImageNet
2.00
SGD
5.0
1.75
CoCoD-SGD
CoCaDSSED
OvertapLocaISGD
1.50
1.25
OLCO3-OC
OveriapLocalSGG
4.0
OLCD,-CC
OLCO,-VO
Training
OLC
3.5
OLCOy-TC
1.00
OLCOy-TC
0.75
2.5
0.50
2.0
0.25
1.5
0.00
1.0
Epoch
Epech
ResNet-110, CIFAR-10
5.5
ResNet-50, ImageNet
Local SGD
Local
5.0
CoCoD-SGD
CoCoD-SGD
4.5
Dverlapl ocalSGD
OLCOy-OC
OveriapLocaISGD
raining Los
4.0
OLCO,,VQ
OLCOy-OC
Training
OLCO,-VQ
3.5
OLCDy-TC
OLCOy TC
3.0
2.5
2.0
1.5
0.0
0.1
0,2
0.3
0.4
0.5
0.6
0.7
10
30
40
50
60
70
80
Communication Budget (GB)
Communication Budget (GB)
Figure 4: Training curves using T 56 and 1 for the delay-tolerant methods, and T 0 and
p = 56 for Local SGD. Best viewed in color.
ResNet-110,
ResNet-110, CIFAR-10
90
CoCoD-SGD
OverlapLocaISGD
Training Loss
OLCOg-OC
Test Accuracy
OLCO,-VQ
70
Local
OLCO;-TC
CoCoD-SGD
óveriapi.ocalGG
OLCO,-OC
50
OLCO,-VQ
OLCOy-TC
25
50
75
100
125
150
175 200
25
50
75
100
125
150
175 200
Epoch
Epoch
ResNet-110, CIFAR-10
ResNet-110, CIFAR-10
1.2
Local SGD
1.0-
CoCoD-SGD
DverlapLocaISGD
Test Accuracy (%6)
80
Training Loss
OLCO,-OC
0.8
OLCO,-VO
Local
0.6
OLCO,-TC
CoCoD-SGD
60
OverlapLocaISGD
0.4
OLCO,-OC
0.2
OLCO,-VO
OLCO;-TC
0.0
40
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.0
0.1
0.2
0.3
0.4
0.5
0.5
0.7
Communication Budget (GB)
Communication Budget (GB)
Figure 5: Non-i.i.d training curves using T = 56 and for the delay-tolerant methods, and
= 0 and p = 56 for Local SGD. Best viewed in color.
12

---

Under review as a conference paper at ICLR 2021
A.3 TEST ACCURACY
Table 3:
Test accuracy (%) of ResNet-110 on CIFAR-10 and ResNet-50 on ImageNet using 7 = 56 for the delay-tolerant methods, and T 0 and p 56 for Local SGD, CR stands for compression ratio. For each method, the first row denotes maintaining momentum and the second row denotes resetting momentum (line 6).
Method
Delay Tolerance T
CR
Re
CR
ResNet-50
92.67 = 0.18
74.68
Local SGD
92.68 + 0.21
74.76
91.07 = 0.14
70.52
CoCoD-SGD
90.84 + 0.06
70.27
91.78 = 0.21
72.71
OverlapLLcalISGD
91,45 = 0.14
72.87
92.16 = 0.10
73,36
OLCCO,-C
1/32
+ 1/32
92.48 0.12
73.40
91.31 = 0.08
70.38
VL,
0.0973
0.1633
91.05 0.21
70.32
92.15 0.11
73.49
OLCO,-TC
56
1/32
1/32
92.31 0.10
73.47
A.4 HYPERPARAMETERS & p
Again, Figure 6 empirically confirms the theoretical results in Theorems TC can handle a larger period p than OLCO, and that this gap increases with the staleness in the i.i.d. setting. Note that in the right plot of Figure 2 the gap between OLCO, TC and OLCO,-VO does not increase with 8 because the period p decreasing (the delay tolerance = sp is fixed).
and that OLCO,-
94.0
ResNet-56, CIFAR-10
94.0
ResNet-56, CIFAR-10
94.0
0600, Jn-3
OLCO
Local
oLco,
93.5
Sccu
OLC0) vg 5-31
93.5
Cacub 300
OLCO, 2-21
93.5
tucap.scD
OLCO
93.0
OLCOUTC 20
83.0
OLCOUTC
30-20
83.0
Dverta
OLCO (e-4)
92.5
92.5
92.5
$2.0
90.5
96.5
90.5
90.0
40
60
80
100
120
90.0
20
40
60
80
100
120
90.0
20
40
60
80
100
120
Delay Tolerance
Delay Tolerance
Delay Tolerance
Figure 6: Vary delay tolerance T for ResNet-56 on CIFAR-IO. We set p of Local SGD equivalent to T of other delay-tolerant methods. Left: = 1 for the OLCO; variants. Middle: s = 2 for the OLCO; variants. Right: for the OLCO; variants.
Table Test accuracy (%) Figure selecting the best configurations & and p for the OLCO; variants. We set of Local SGD equivalent to T of other delay-tolerant methods.
Method
T
16
T
128
Local SGD
93.19 0.24
92.98 0.19
92.68 + 0.15
92.25 + 0.24
91.98 0.19
CoCoD-SGD
92.56 0.08
92.10 + 0.23
90.74 - 0.14
90.63 + 0.18
90.40 + 0.11
Overlap
92.89 0.11
92.56 + 0.17
92.22 + 0.14
91.36 + 0.23
90.81 + 0.24
OL.CO,-OC
93.13 0.02
92.76 + 0.22
92.21 + 0.06
92.00 + 0.10
92.02 + 0.07
OLCO,-VQ
92.73 0.12
92.11 + 0.23
91.85 + 0.12
91.30 + 0.17
90.58 + 0.21
OLCCO,TCC
93.09 0.12
92.68 + 0.21
92.61 + 0.16
92,27 +
91.74 + 0.22
13

---

Under review as a conference paper at ICLR 2021
B ASSUMPTIONS
Assumption 1. (L-Lipschitz Smoothness) Both the local (fx(.)) and global (f(+) - Σ fa(-)) loss functions are L-smooth, i.e.,
VV ff(()22 - L|| y112, Vx, R
(8)
[V)xxx Sx())]l2 L|Ix ylle, wk [K], Vx, RR. Assumption 2. (Local Bounded Variance) The local stochastic gradient V (x; has bounded variance, Le.,
BR (VF)(x)) f o², Ak [], E
(10)
Note that Be-D, (x; -V(((t))
Assumption 3. (Bounded Variance across Workers) The L2 norm of the difference of the local and global full gradient bounded, i.e..
[V V x², vk E [K], Vx R
(11)
where K = 0 leads to i.idd. data distributions across workers.
Assumption 4. (Bounded Full Gradient) The second moment of the global full gradient is bounded, ie.,
| S G2, Vx E IR...
(12)
Assumption 5. (6-approximate compressor) The compression function C(-) Rdd IR is 5- approximate compressor for < for all v E RR,,
[[C(r) r13 - (1 1r
(13)
C BASIC LEMMAS
Lemma 1. For OLCO,-TC, let Kr == 1 K
K Xt
(k)
K
Ek=1
K
el
-p- then we have
Th-
(N)
i 8
m
(14)
K
Proof. For t = np where n some integer,
Rnp
K
1
(k)
K
(nn-s)p
Xnp
K
1
C(A
(k)
(n-1)p
K
(k)
e(n- s)p
k=1
im0
K s-1
K
=x(n X(n-1pp
((A(n)))p)
C(A
(k)
(1-1)p
K
1
(k)
np
C(n-slp
k=1
k=1
K
K
K
K
1)p
C(A
(n- -
C(A((n
K
C(A
(1-
(k)
K
(k)
C(n- s)p
1=0
k=
1=0
k=
(K)
1
(k) 1
C(A
(k)
(((D(n-s))) -((n-s)p
(n-1)p
K
(k)
K
13p
K
np
(in-s)p11
1=1
k=
K
ap-1
1 K
(k)
1
Σ
(k)
(k)
(k)
K
(n 1)p
K
1 m
m+1++
7+1
K
e e(n-s)p-1
Xnp-1 1
Tap 1
km
(=(1-1) 1)p
km
(15)
14

---

Under review as a conference paper at ICLR 2021
For t + np,
K
K
K
K
P/-11
x
K
K
sp
K
K
1
-p-
1
x,-1
K
m
k=1
1=1
k=1
k=1
A= 1
(16)
Lemma 2. For OL, let = K Ex=
Xx
(K)
1
Ex=
(k),
then we have
K
(8)
8 x
m;
(17)
K
Proof. For t = np where n is some integer,
K
K
K
5-1
K
Knp
K
(k) np
K
ap
Xnp
K
C(A
(2)
(m-1)p/
K
(k)
k=1
k=1
K
X(n-1)p
K
1
C(A
(6)
()-
K
1
C(A
(K)
1)p
K
hp
(k)
1= ==
A=
K
K
s-1
C(A (1)
(n- 1-1)p) ))
1
C(A
(k)
1
ΣΣ
c(
(k)
1pp
K
()-s)pp
K
nn n 1pp
up
i=0
1=0
K
K
K
C(A!))
(K))
(k)
K
(n-1)p
1)p
K
K
up
k=1
k=1
K
1
(k)
(R)
K
(n- 1)p
K
k=1
K
ap-
(6)
1
K
(k)
K
(n-1)) 1)p
K
17 m
T+1
K
-pp1
k=1
k= (=(n-1)p 1)p
k=1
K
Xap-1
7np-1 m mp
K
k=
(18)
For # np,
K
K
K
8,
(k)
X
1
(k)
8,
Th-
m
(k)
(19)
K
K
K
K
k=1
k=1
1=1
k=1
Lemma 3. For OLCO,-VO letă;
Ek
(k)
1 K
Lk=1 ot- then have
(K)
K
11-1
(k)
=
=
m
(20)
K
k=
15

---

Under review as a conference paper at ICLR 2021
Proof. For t np where is some integer,
K
Kny
K
(k) pp
KL
1
(n-e)p
Xnp
K
(n-1)p
(k)
K
(k)
(n- -}p
k=1
K
K s-1
K
X(n-11p
1)p
K
C(A
(k)
s)p/
K
1
(a- 3p
(k)
K
(k)
s)p
k=1
1=0
k=
K
K
K
K
(B)
(K)
C(A
(R)
(A)
())
K
13p
K
s)p
K
(n-1)p
K
(n
1=
1=1
k= 1=0
k=
K
K
1
(k)
1
(K)
1 K
K
(n-
1/p
(n-1- -1p
K
(n
+)p
(n 1)p
1=
i=0
K
K
(k)
K
(n-
K
np
k=1
K
ap-1
K
(k)
1
(k)
KL
(n
1)p
K
7/ 7+1
K
epp 1- sp
(= 1)p
k=
K
Xap-1
K
map
m
up
(k)
k=1
(21)
For L F npp,
K
K
K
K
1
(k)
1
(K)
1
(k)
(k)
(k)
X
Xx-1
m
K
K
sp
K
K
sp
K
km
km
km
k
(22)
D PROOF OF THEOREM 1
Lemma 4. For OLCO,-VQ with vanilla SGD and under Assumptions 2 3
and the local error
satisfies
12(1 - 5)
Elle 12 <
p2
(o² + xx² + G
(23)
82
Proof. First we have
(h)
112 < (x (k) (k) (()))
(x, (xx(x()))) 33// - \ + /3 (xxx (0111
< 302 + 3x2 + +02
(24)
Let S. = -T111.
E Elee, (x) 112 = 1Elle 12 = EIICIA (8)
1
S (1 - A
S.p-1
= (1- - B1l Σ
Fx 1/ +
c (S. (S.-a-1)2 1)p 12
(k)
1'= D)p
Sip-1
<11- - 6)(1 + p) c ((S. 12 + (1 + 5) +
1 Σ
1
V e( )
p
t'= (=(5-11)p 1)p
< (1- 1)( + (K)
1 3(1 + 0)
) 2 + 2 + G2).
(25)
16

---

Under review as a conference paper at ICLR 2021
Therefore,
1-1-11 1-1
El Elle (k) 1 3 6)(1 2 G
Σ (1-+)(1+/))
(26)
3(1 2) ))
$ 1 1- (1 6)(1 + (0² + +
Let p 2(1-5) such that 1 1+ p =
8
2-6 s 3. then Elle 1B = 12(1-6) 2 (0² + +x2
Lemma 5. For OLCO,-VQ with vanilla SGD and under Assumptions 1 2 and the learning
rate 1) S 1)p+ we have
T-IK-1
Σ
E x1 10
KT
1=0 k=1
< (s + (1+
12(1 12(1-5) 5)
(s
+)1)) 11 +
4(1 5)
(27)
82
82
36(1- - 8)
+ 8²
Proof. Let Sy = 1.
k
K
K
B
x
(2)
12
El
Σ
Fr (xp
(K)
(8)
(
K k=1
K
K
k=1
W=1
2=0
S'=S.p
8-1
[-1
K
(6)
V (1)
(k))
(Sc-))p
--epl
1=0
V=
1
El1
NF
(x
(6) (1))
K
K
1'=(S.-8pp 8)p
K
(K)
(5 R- 1)p 12rl
(K)
K
SS i-s- 13p
27
K
E|
Σ
V
V V (x of
K
K
#=1
(==
(8, 5)p
t' t= -ip
K
E
K
K
sp
K
S 1)p
18- 1pp
#=1
F=1
1=0
(28)
17

---

Under review as a conference paper at ICLR 2021
The first term is bounded by
2/²2
K
E
Σ
(x
E 1
K
K
k=1
k/ (= +Ip
(==(S.->pp
2/2
K
Σ
1-1
1
K
+ -V
E
R
k=
('=(S:
SSp
M=1
21
K
1-1
K
Bl|
(x
K k=
K
(= 8)P
k==l
21/ K
K
E|
-
K
K
k= (=11 S)p
k=1
21 2 K
K
K k=
K
(=
k==l
27 K
- 013
(k) (1)) (x)) (xx(x,1)))
K
k=
21
K
1 K
Σ (
Σ
fx V 1
K
K
11 =)pp
< <217(s 1)po0 + 2n7 (s + l)p
Σ
ΣE1
Bl|
1 K
+
+ [V/[(x(+011 >BB,
K
P=t (s+1p=)
(29)
where the third inequality follows
E
11 Σx=
ax
ax12 = E
1 Σ a 1 Σk ||ax||2. and
K
K
E
V
VAA
K
K
k=1
==1
3
VllVV (k)
+ - -V/0
SKr f |13
K
K
$
B|
x 10
Σ
(Z.) (x 013
k=1
2
K
E - x 1 + 3k2
K
(30)
18

---

Under review as a conference paper at ICLR 2021
The second term is bounded by
K
2
E
(2)
(e)
1/
K
K
Sp
K
(St (8--1-8-11 1)p
(S 1-------1 1)p
km
1m0
0
2(1 + 8)
K
(k))
122 +
2(1 + !
K
E1I
8-1
5m
K
(S
18--8)pl1
K
K
13
k=1
M=1
1=0
2(1 + 8)
K
2(1 + 1)
K
Elle
12 +
K
s)p
K
A=1
R=1
1=0
2(1 + +)
Blle (k)
112
2(1 + s) K
K
E
e
(2)
K
(S. +)p
(S. f- 1)p
2(s 1)
K
24(1
8)
E Elle (S. 1----5)1
11
(s + 1)2p"' +
K
82
1=
(31)
where the last inequality follows Lemma term, we have
Combine the bounds of the first term and the second
K
E B
12)11 11
K
k=1
6L K
2n - 1)po² + 2 11p
B
x 10 +3x²)
1'z-
k=1
24(1 - 5) +
(s 12
+ x² + 22)
82
12(1- 8)
4(1 4(1-0) 8)
24(1 6)
< 2)) + 1)po0 (1 +
(s + 1)p) + 61) 1)303 21
12 + 1)?232
8²
82
8²
[-1
K
12n2 L 1)p
Σ
1
Σ
E x 12.
(=+1p
(32)
Sum the above inequality from 1 = t t = T 1 and divide it by T,
T-1K K-1
Σ Σ B|
x
(k)
KT
t= k=1
12(1 - 6)
4(1 4(1 4(1-6), 8)
24(1 - 6)
< 2nn2(s 1)po (1
(s + 1)p) + 1
82 +
82 2s
82
T- K-1
12n) L2 1)
1 KT
Σ
Σ
E| x 13
t=0
(33)
Therefore,
T-1K 1-1-1
E E||x x 1
KT
t= 1=1
2x + 1)p0 01 (1 + 12(1-5)
(s + 1)p)
- +
24(1-51 6²
+ G)2
(2 1)2p2
(34)
19

---

Under review as a conference paper at ICLR 2021
If we choose 17 6L(s+1)p*
K-1K-1
Blix 12
B
KT
1=0 1=1
6) 12(1 12(1-6)
4(1 6)
36(1
6)
31 1
(1+
82 (s + 1)p) + 9n
(s + 1) G²
82
8²
(35)
Theorem 1. For OLCO,-VQ with vanilla SGD and under Assumptions 1 2
and
if the
learning rate 1j S min 1)p(s-1)p' 91, ). then
1
T
1 k F
9nLo² 6(f(xo) - fc)
+ +12n) 12n + 1)p0 (1 + 14(1 - 6)
11
(s + 1)p)
T t=0
K 1=1
T/
K
82
5(1 - 8)
168(1 (1 - 8) 2 88 1)
3,7 1)3p2 2
+
82
82
(36)
Proof. According to Assumption D
L
E, (8 f(x.) < E. (V 8c+1 xx) + - EE, ||,|||1111 - X:112
K
Laj² 2
K
= (VS(())))
Σ V
FFll
; of
k=1
(37)
For the first term,
K
K - (V)(3))
((V)())),
= -IV> -
Σ (V
km
$ 2
1 | [V 11
1 K
Σ (V (b) -
(38)
k=1
W 1 1
L
Σ
K
|| - x
12
2K
k=1
where the first equality follows that v((,,)) = E fix fice)) For the second term,
K
Edll
F
(x,
)
K
k=
K
K
E.ll
(x ((())) v
(1) +
V (x (K) - +/
K
1 K
$3F,
(VP
(1)
(d.)) VSA + 31 -
K
3
3
Σ
x
( 11 + 3 3/
K
K
(39)
Combine them and we have
2 (1-3)()((\(())1 + nL2
1 K
3
(x(x++1) - -((x)) <
2
2
(1 + 3.
K
Σ
x
(8)
12
+
2K
k=
(40)
20

---

Under review as a conference paper at ICLR 2021
If we choose 9
21y2² 1 K
3rj 2n Lo²
" V
+
Σ
[
X
12
1
+
(41)
3
3 K
2K
k=
Then for the averaged parameters
1 R
E xi
K
lIV[( 1
s 211
1
(0))
+
K
k
2L K
1
x 211.11
K
Σ
s-sp
2 +
2
z
K
1t-pp
11 + 2 V / (xx)11
k=1
(), - Baf(R(+
OnLO²
41
10 +
(1)
21.² K
Σ
|
7
K
K
K
(42)
Take total expectation, sum from L= 0 to = T 1, and rearrange,
K
f(
1
(8)
12
K
k=1
(Ro) [x((x]]
21 T-1
41 T-1 K
Σ
E|
(R)
1
Σ
B1|a: 1
1/T
K
KT
KT
t= k=1
k=1
((en) - -ES(XT)]
9nLo²
24(1 - 8)
+
+
11 2 G2)
11T
K
82
(43)
+ 12 + 1) + 12(1
8)
4(1 8) 52
(s+ + 1)p) + 3 1.2 1)3p222(1 +
82
144(1 (((1-))) 8) 11?? + G)2
82
(xo) - fa)
OnLo²
+ +12n L' + 1)po (1 14(1 - 8)
(s + 1)p)
1/T
K
82
5(1 5(1-5)
168(1 8)
+ 367) 222 1s
11 22 1))pp²
82
8²
where the second inequality follows Lemma 4 and 5
E PROOF OF THEOREM 2
Lemma 6. For OLCO,-TC with vanilla SGD and under Assumptions 2 3 and 5
the local error
satisfies
12(1 - 5)
Elle (1)
1
82 (02 + +
(44)
Proof.
Same as the proof of Lemma
4
except that
(S; is replaced with (k) (s.-1)p
(k)
Lemma 7. For OLCO,-TC with vanilla SGD and under Assumptions 2 3 satisfies
and 5 the server error
96(2 -)
8)
E El <
202 + + G9)
(45)
84
21

---

Under review as a conference paper at ICLR 2021
Proof.
Let Ss -1
K E
K
K
1 K
K
c(4
s. 1
- 2E
K
C
Sep
(2)
K
Σ
A
Sap
12
+ 2E
K k=
1=1
k=
2 K
E
BIC
(k)
(3)
2
2
Σ
E1|
1
(8)
(46)
K k=1
3pp)
2
K
k=1
2(2
5)
EI
K
Following the proof of Lemma 4 we have TE|
E
A 1.pp13 - 11 P1p 2 Pop
2(1+2)
Therefore,
K
Elle, 3 = Elles.pl1 112 S (1
B]
1
C(
(k) S.p/
+ +1s111b111 2
K
K
<(1-))(1+ + p 1E
C(A
11 + (1 - 6) + p)EB
K k=1
Sip
22(2 - 8)(1 ()
2
1
E A
(1) S.p
3 + (1 6) p)
p K k=
3(1+ )
22 6) 51 1
p022 + 12 + 69) + + 1) 12
0 1 (1 5)(5))111) + p)
6(2 6) () ) 10² + +x² 2 G
[ (1 6) + 2)
(47)
Letp = 8) such that 1 1+] p 8
2-5 s 8 e
then Elle
(k)
1
S
06(2-5)(1-6)
96
(2) + + +2).
Lemma 8. For OLCO, with vanilla SGD and under Assumptions
22 and5 if the learning
rate 1) S 6L(++Ipp and let h(0)- 1 + 4(2-6) we have
T K-
1 Blje, x x
1
< 3 3n12202' (s + 72h(0)p) + 9n'"'² ((s 1)² + 24h()) - 2166
(s
KT
(48)
Proof.
Let St = 11
K
K
1-1
t-1
B|i - (2) 11
B1
Σ (-
Σ C(A
(8--))))
(8)
Σ Fv ((2
K k=1
K k=1
M=1
S=
C(A (k)
Σ
(k))
11
(5p
K
e;
sp
==
(49)
where
s-1
8-1
1-1
1s--ipp-1
Σ
c
(6)
(p)- =
(k)
(St - 1)p
(8+ 1)m
(k)
Σl
Σ
V (1), ((())
+
+0(5.
2(S--i-1))
(8)
1)p
((8 ((8--1pp 13p
(k)
1=0
1=0
1=0 ('=(St- 1)p
(S
Σ
Fx
(k), (k)
15
+ (k)
((s
(k)
1=0
(S
(50)
22

---

Under review as a conference paper at ICLR 2021
Therefore
K
E
X
x
(
K
K
1
E1
Σ
F
E
1 (x, ((0)))
K k=1
150
k= (S +)p
(=
K
1 K
S.p
(K)
(k)
[ +)p
es.
(K)
K
(R)
e sp l12
(51)
k'
K
2n
|
(X
(X
K
== 1'=1'=(S.-0)) +)p
0'
K
K
+
K
2
BII
(Se-s)
(S--s)p
S
(k)
cs. (S.->))
where the first term can be bounded following Eqs.
29 30 The second term satisfies
K
K
2
1
K
E
K
S.
s)p
+
(S.-9)p
((:
k=1
k'=1
K
K
K
6
E1
(k")
(K)
Blle
(k)
12
6
E
es.
K
SS s)p
(S s)p
K
Sip
K
(52)
K
K
K
[ (S:- 11
Blle
(k)
E
6
E
K
K
S.p
K
1=
8
4(2 - 8)
- 82
+
144p211
(a² + 2
82
where the last inequality follows Lemmas 6 and two inequalities and we have
7
Let h()) 1 (1+ 4(2-5))
80
Combine the above
K
E EX
12)13 12
K
k=1
6L
2/72(s - 1)po² + 2177(s 1)p
Σ Bl 1-x 12 3R²) + 1446(0)p'72 + +2
K
e- (s+ 1)p
po - 1 1 (2h(6)p) + 6172pp x2 ((s + 1) + 24h())) + 144h
22 + 1)p Σ
Σ El|x: 13
1== (0+1)p
(53)
Following Eqs. 33 34 35
ΣΣ E|J 10 < 317pp'' (s 1+ 72h(0)p) + + 13 ((s + 1)² + 24h(()) 2166
(54)
23

---

Under review as a conference paper at ICLR 2021
Theorem 2. For OLCO,-TC with vanilla SGD and under Assumptions
1
2
3
and
if the
learning rate lj S min 1T) 07. and let h(6)
1/ + 1(2-8)
then
1 6(f(xo) f+)
- 1=
1/T +
K
(55)
+ 12n (s + 1+ 80h())p) 12n' p2n'ppnn (3(s + 1)² + S0h( 960n)'p
Proof. Following the proof of Theorem
we have the same inequality as Eq. (41
2n
K
3nd Lo
(x - f(x)) < 3
[
Σ
18
(k)
11
+
(56)
3
K
2K
k=
(k)
Then for the averaged parameters
2k=1 xx
K
1
1 19 112 S V
IVA
ff
+
K
K
S
2
+ ec
12 + ((x
k=1
2L
K
4L2
||| ep 1/ + 2 ff 1x
K
K
k=1
(x.)
Ee (8++1))
InLo
4L k
4L
4L2
+
Σ k=1
x
1
110
(k)
1/ +
|| sp 1
K
K
K
(57)
Take total expectation, sum from = 0 to = T 1, and rearrange,
ΣΣ E
K
11
(z)) - EE((x))
Ln
21, T-1 K
412 T
B
E E 2
nTT
K
KT
KT t=
1= k=1
2 T-1 K
KT Σ Σ
E X
10
(l)())) - Ex(r
9nLo²
4(1
32(2 8) 5)
+ 12n po (s + 1+ +277) +
p +
p)
1/I
K
82
64
+ 120"" (3(s + 1) + 72h(()) + 4(1-6)
32(2 - 8) 8)
+
82
84
G2072'2 4(1 4(1-6)
32
8) 8)
82
84
6( (.))
9n
1/T +
K
+ 11172ppp po² (s 1 80h())p)+ + 127 (3(s= + 1)² + +0h( + 960n
(58)
where the second inequality follows Lemmas 6 and g
F PROOF OF THEOREM 3
We first define two virtual variables z and p. satisfying
(Xr - x), t21 1
P 0. t= 0
(59)
24

---

Under review as a conference paper at ICLR 2021
and
2: = X1 + Pt.
(60)
Then the update rule of 2, satisfies
/ (Rt+1 xx)
74+1 24-
(x++1
xx)
+
(x. x
1 p
K
1
(R)
1
(k)
1
(k)
K
1 μ K k=1
4+1
K
m
k=
k=
K
(61)
1
(R) m [+1
Jum; (K))
(1
11)
K
k=1
K
17
fx
(
(1- K)
which exists for OLCO; OLCO, VQ and OLCO,-TC.
Lemma 9. For OLCC03 with Momentum SGD, we have
3 + R² + G2)
E
(k) 12
(62)
(1 11)
Proof.
(3)
E
Fx
)13
P 1 2
f==0
P==
3(0² 2 + n² + G
<
(1 - 12)
0==0
(63)
Lemma 10. For OLCO3 with Momentum SGD, we have
ElIp. 12 3p312 (o² + 1c2 + G2) - (1)
(64)
Proof.
112
122r2 E
K
11 12212
K
E E| = (1 - =12 Elix: x1-1
m
12) 1 =
E 10
(1 - n1)
K
(1 - 22)2K
k=
kmm
(02 + + G2)
(1-1)4
(65)
Lemma 11. For OLCO,-VQ with Momentum SGD and under Assumptions 2 error satisfies
3
4
and 5
the local
12(1 - 6) 10 xx= G
Elle( _ <
(1 (1-1)2223)110
(66)
Proof.
Let St = 1..1.
E
e
(k) 1/ = E. 112
(k)
E C S.p)
(k) (k) (k)
S.p 12 < (1- 4 (K)
s.p
Srp-1 1
= (1 - 5|
m (5,
(k)
(5.- 1
(67)
('= lip
1 37222(02 + x²2 + G2)
< (1 - 5)(1+ + p) (S.-0-1)p1
12 + (1 8) +
(1- 11²2
p
25

---

Under review as a conference paper at ICLR 2021
Therefore,
Elle; 12 11 S 3(1 3 5)(1 + ) / (0² + R2 + G2)
1
1-1
[1- (1-5)(1+p)) + P)]"
(1-
1=0
(68)
3(1- - (1 + 2) (02 + 122 + G2)
1- (1 p) (1 11)
Let p 2ा
6 such that 1 1+ 1 قي 2. then EBle,
111 113 S 12(1-8)
1 G2).
Lemma 12. For OLCO,-VQ with Momentum SGD and under Assumptions 1 2
3
and 5
if the
learning rate 1) S
1-14 we have
v721(s+1)p 1)p
T
K
Bait x 1 S
0n
3
+ ++++ 1s+1)p+
+
12(1 - (s + 1)²p²
KT
(1 10)
n1)
82
t= k=1
12
1
+ (s 1)3p²
+ 4(1 - 5) 1)
12
1
4(1 0) + 1)²p²
+ (1 n1)2
(1 (1-1²² 11)2
82
(1 n1)
n1)2
82
(69)
Proof. Let S: = -/111
K
K
K Σ
s-1
Bliza
(2)
(g - (K)
(k)
S.p x; (7)
K
K k=1
K
k=1
k==1
1m0
K
(k)
(k)
(k)
1
Σ
Sxp
X
(8p
K
1=0
K
K
1-1- (S. Σ
!-1-!
Σ
VV (x 15 (K))
Σ 1*)
K
E
K
7
(S s)p
k=
1=1
T=0
|= +)p
1-1-(S, (S.
6-1-1 Σ k²)
(nm
(K)
Σ
V
(9)
(5 s/p
1= 8)p
K
(K")
(3))
SS si-i-s-lj 13p 1
(k)
+
9p
K
(5 1p-----11 1p
3r/²
K
1-1-(Si-opp
(k)
E
K
K
(S:-Spp
(S--a)p
k=
P=1
31
2
K
K
H-1-
Σ
El1 K
V 15p
1
V FA
(x i50
n 1|
K
A=1
1=1
('=(S,
0=0
P= s)p
K
K
+
K
3
E
K
1
e ap
K
(S,
(S-1-811)p
(S. 18--1-9-110 1)p
(k)
11
1=1
k=1
K= 1=0
1=0
(70)
The first term
37p²
K
K
1-1- (Sp
(k)
1-1-(S--5)
1
K
K
s)p
SS s)p
k/
7=0
312
K
2
K
m
x)p
1-1 (S.-a)p
11
<
[1
377
11
2
K
K
m
(k)
(S. +1p 11 <
917 + x2 + G2)
(1-
k=1
T=0
(71)
26

---

Under review as a conference paper at ICLR 2021
where the last inequality follows Lemma 9
Following Eq.
29
the second term can be bounded by
3r7
K
K
1-1-t
t-1-t'
Σ
V
:4
Σ #
2
K
K
7=0
t= (S
37/²
E
Vfx (x 1)) - (VF ( Vxa(x
Σー
KL
k=
(Se s)p
k'
+ 31 2
K
8-1-1
B||
Σ
Σ 10
K k=1
1'=(S,
31/ 2
K
(-1
V ( - (x
$ (1 - -2)K
s)p
3n/2
K
1 K
+ (1 (1- -1)K
(t - (S: - ss)p)
Σ km ('=(S
Bl1
Σ
fx - V
K
3/ (s + +)po²
31 + 1)p
6 K
E Bliz - x 112 + 3x²).
(1 (1- 11) (1 - u22
K
t' (++1)p
(72)
where the last inequality follows Eq. (30
Combine the bounds of the first and second term with
Lemma and Eq. 33
K K
Bliz: x/ 12
9r72( (0²
2 + x2 + G2)
3n + 1)po²
31 + 1)p (1 (1- 11)
6L K K
E
x +x22)
(1 - 11)4
(1 11)2
1= 1--- 1tp
1=1
3(s + 1)
K
Elle -ipp 112
K
k= 1=
(o² + x2 + )2)
3s + 1)po²
917² + 1)?pp>>
36(1 - (s + 1))pp(02 + x² + G2)
+
(1 p1)1
(1 n1)²
(1-1)
(2)2)
L2 + 1)p
Σ
1
E El x/0
(1- -1)
K
(-=-((++1) D)p
(73)
Sum the above inequality from t = t t = T - and divide it by T.
T-1 K
Σ
Eliz
x,
(K) 10
3n
3
+ (s + 1)p +
12(1 - ({s-)((s+)))))))) + 1)?p?
KT
(1 - 42² (I 11)
82
(=0 k=1
9n72n2
1
+ (s + 1)2p² + 4(1 6) 1)?p?
G2
1
4(1 8) + 1)?p?
+
+
+
(1 1)) (1 - 11
82
(1 - n2
(1 - (1-1))
82
L2 + +1
T-1 K
Bliz - x 12
2
KT
1=1
(74)
27

---

Under review as a conference paper at ICLR 2021
If we choose 17 -
1-#
vT2L(++1pp'
K
Bliz 13 (1-
4nj²0²
3
+ (s + 1)p + 12(1 - -d)(s + 1)22²
KT
8²
t= k=1
+ (1- 11} (1 [1] + + 1)322
121
1
+ 4(1 +1+1))+22+
() 1)3p²
12
1
4(1 (ss 1)21p²
+
+
8²
(1 12)
(1 - 11)
5²
(75)
Theorem 3. For OLCO,-VQ with Momentum SGD and under Assumptions 7 1-p
3
and 5 2
if the then
learning rate 1) S min
1- } and let g(p, 5, s,
15
<72L(=+1>''
9t.
[1-1}²
1 K
6(1 (11-))1 (f(xo) - f.)
9Ln0²
F(
)13
+ (1 1)
T t=0
K
r/
1=1
4nf L22
(,,,8,s,))) [[A(s + 1)p + g(u, s, s))o + (12(s + 1)3p² + g, + 1(M, 8, - G
(1 (1-w)²
(76)
Proof. Following the proof of Theorem I
and the update rule Eq. 61.. we have a similar inequality
as Eq. 41 by choosing 7 S :t=:
B (*++1)
fZz)
$ 1
"
(- 1
+ 2K
12
Σ
(k) [23 +
Lup
302
+
312 K
7 x ( 12
+ 31 (z+)))
2
2(1 - 11)2
K
K
k=1
k=1
17
(1
3L1
|| (Z) 112 +
L'n
(1 + 3Lm
K
1
X1
(k)
1 +
3L1R0²
2(1 (111) 11)
1 p
2(1 - u)l
2(1 2(1 ~k)K
k=1
17
[/ +
24L²
12
x
(k) 1
3L7202
3(1 - pt)
3(1
K) k=1
2(1 - 11)2
(77)
Then for the averaged parameters
(k) x
k=
K
11
S 2
Σ
(8)
v(x))2 22
K
K
k=1
k=1
K
s 21.71
1
C-
(k)
2/
(78)
K
K
s 4
Σ
(k)
12 + 4L 12.11 - 22
K
sp
kml
Therefore
K Σ
6(1 w)(f(z)) - f(er))
2ouT2
4L T-1
V (8)
E
113 5
+
Σ
Σ
E
14)
T
KL
n/T
(1 p)K
KT
k=1
t= k=1
4L2 T-1
K
4L T-1
+
Σ
E
Σ E
1
T 1=0
T
1=1
6(1 (xx)
9Tmo2
n/T
(1 (1-N)K
41222
(1 (1-1 [[A(s + 1)p+ glu, 8,,,p))o² + (12(8 + 1)32² + +g(u,,,,,))) + 50,,5, 5, &P))
11)2
(79)
28

---

Under review as a conference paper at ICLR 2021
60(1- 80(1-8)x++1)) (x+1))pp
where the last inequality follows Lemmas 10 and and g(u, 8,
[1-1)²
8
G PROOF OF THEOREM
Lemma 13. For OL.CO,TTC with Momentum SGD and under Assumptions error satisfies
4 and 5
the local
12(1 12(1-5) Pn + + G²).
E 1 -
(80)
(1 10202
Proof. Same as the proof of Lemma 11 except that (S--s-1)p is replaced with (R)
(k)
(S,-1)p
Lemma 14. For OLCO,-TC with vanilla SGD and under Assumptions 2 and the server error satisfies
96(2 96(2-8)(1-0) (0² 2
E Elee112 S
(81)
(1 - -1)228
Proof. Let St 1.1. 3(1+2) p0n""0"+*x++ [-(1-)[[[+p) (1-1²)²
Following the proof of Lemma Therefore,
we have A
(k)
Sip
K
Elee [ 2 2010--)11-- (1)(- + 1 1
Σ
B
E
(k) S.p
1 + (1 - 6) + E| [ss_))1
0 K
k=1
22 - (1 - 6)(1 + 2 (1 8)(1 +
3(1 + :)
102 + + x2 G2)
+ -5)(1 + +) es)
(1-1)²
6(2 10-8)- 6) - 5) + )
- (1 - (1 + p) - 11 P 17 (02 + t +2),
(82)
2-5 7 Let p 2(1-5) then Ellee (+) 113 < Elle, ( < (1-A)8" (0² x2 + G
where the first inequality follows the proof of Lemma
5 such that 1+ p
96(2-5)(1-5)
Lemma 15. For OLCO3-TC with Momentum SGD and under Assumptions 1-p
and if the
learning rate 1) S
have
V12L(s+1)p
T-1 K
01 ( (1 p1)2
3
Bli
1 5
+ (s 16+11 1)p 72h(6)p²)
KT
11)2
1=0 k=1
(83)
3
Gr
3
+3(s 1)3p² + -2h(6))²²
+ +72h(6)p²),
(1- 11)
(1 11-11)
(1- μ12 (1 (1-11)2
112
where h(6) 52
1-6
(1 + 4(2-61)
Proof. Let St = 1
K Σ
El x (k)
E
C(A
(k')
(k')
x(())))
K
K
-1p)
(84)
(- Σ
#-1
C(A
(k)
(8.
)pp
Sx
(k')
x;
(k)
K
1
Σ
K
e
(k)
e
ep 112
k=1
29

---

Under review as a conference paper at ICLR 2021
where
C
(k)
(Sc -1pp
+
+XS.pp
(1)
Xi
(8))
A
(k)
(St -i)
-1p 1
(k)
SXS.p
(k) (k))
i=0
p-1
(St (S-=1)=-1
(St (S1-1)p-11 1-t1
Σ
1)p
r+|
VF (k)
1²" +
(9, 1--pp
(k)
()p
(k)
7=0
f-1 1-1-8ip
1-1-1 Σ Ra
(R)
(K)
m
Stp
T=0
S==Spp
8-1-(S,-
(S--8)
Σ
1-1-6
(SL
(k)
1 r++
VV (x) ((0)
Σ
# +
(5.
(k) (1)
-5ppp
T=0
0
(85)
Therefore,
K
K
K
t-1 (S:-6 Σ
(-1- (S, (8)
K 1=1
Bliz
(2)
K k=1
K
m
(2)
(S--))
1 +++
7m (k)
SS:
Σ
/ +++1
k==1
T=0
T=0
K
1-1-1
4-1
1-1-6 Σ
17 F (xg
(K),
Σ 1²
Σ
V
(xp
(1)
K
(S
(==(S,=)pp
T=0
K
(Sp
(k'
(sp
(k)
+es.p + e
Sep
(k)
sp12
===1
37/
K
E
m (A)
3
K
K
5. (Sc-s)p +
(k)
+ spl
(1 - K
(St s)p
K
(8 S8-s)p s>p
k=1
k
3/7²
K
K
1---
1-1
1-1-6
+
Fl
Σ
(
Σ
1 112
k==1' (S
ss)p
P=
(86)
where the first term is bounded following Lemma 9 and the third term is bounded following Eq. The second term
72
K
3
(k)
(k)
K
E
(S (S--s)p
s)p
(S.
+
sp
K
K E
K
S
E
4)p 11 +
E E|le(s
(87)
K
(S
K
Sep
K
k=1
k=1
1=1
8
4(2 4(2-6),
8)
(1 28 (1+
21622 11 (0² + 2 + G
82
Combine these bounds.
1
K
(4) 11 5 9n + 122 + 62)
1-8
(1+ 4(2- 4(2-5)
Σ Eliza
2166p' 0
K
(1- 11)4
(1 - 282
8²
A3m
3/72 + +1)po²
3772 + +1pp
2L K
E Z
x 1 + 3x²²)
(1 (1-1u) -11)
(1 n1)
K k=1
M/ 1s
1. + 11p
Σ
1
K
Elize - xx x
E
[1)
K
(==1(o+1)p
km
(88)
30

---

Under review as a conference paper at ICLR 2021
Sum the above inequality from to t T - 1, divide it by T, and choose 17 1
1-#
v12L(++1pp'
T-1 K
311²0²
Z
X
12
(2)
(1 - nn² (1- 11)2 + + + 31)p+72(()pp)
KT
1=0 k=1
(89)
3
+3(s + 1)²p² + 72h(0)p²) + Gr
3
+ (1 u)²
+ =22h(0)p²).
(1 w1=
(1- n1)²
(1 - 12²
Theorem 4. For OLCO,-TC with Momentum SGD and under Assumptions L 2
and if the
learning rate 1j I min
1-p
'z and let h(6) = 1-6
82 (1 + 412-5)
5² ) then
V12L(*+1pp'
1
Σ
x
(k)
012
K
1=
6(1 (xxo))
S.)
9Lm
6,2
9
(1- (1-14k - +
(1 - nu) [02{
+ 2(s + 1)p + 168h(5)p²)
n
(1 [1=
9
9
+ R²(
+ +6(s + 1)²p² + 168h(8)p²) 02(
+ 118h())p²)).
(1- 11) p1)
(1 n1)
(90)
Proof. Following the proof of Theorem 3
(Z++()+))= - -1(+)) S 1
+
24L2
Σ
K
|
11 +
2(1 k (91)
3La²0²
3(1 11)
3(1 - n1)
k=1
1 K
K
|V8( K Σ
) 12 S 2
1
Σ
(k)
(1 + +
x
K
k=
K
S 2T??|
||
1
(k)
+ et- sp - -P.13 + 2 V f2) |1
(92)
K
k=1
K
< 6
1
(k)
112 + 6L et- 12 + 6 p. 12 + f(2))l
K
k=1
Therefore
K
6(1 ())l(Z))) - f(zr)]
9Lno²
4L T T-1 K
T
E
(8) |13 <
Eliz
x 1
1/I'
(1 - 1)K
KT t= k=
1=1
69
T-1
K
6L T-1 T
6 T-1
E
E e sp
E 1
T
sp
T
0=0
1=1
1=0
6(1 (xx)
f()
9L
6ry² L
+ (1 K)
(1 n)) 1021
2(s + 1)p 168h
T
(1
n1)a
9
9
+ x2(
+ 6(s + 1) + 168h()))?) + G2
+ 168h(5))²)) ()))))
(1
22)2
(1 11)2
(93)
where the last inequality follows Lemmas 10 and 15
31


Reviews:
[{"review_id": "ubgXw8cWvf", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review: This paper studies distributed training of neural networks. The major obstacles in distributed training are communication costs and communication delays. In the literature there exists different methods which attempt to overcome these two issues but, as far as the authors claim, none of the existing algorithms succeeds in dealing with both these aspects at the same time. The authors propose a novel distributed method OLCO_3 which is designed to address both communication costs and communication delays. In particular, the authors propose two variants of the method: OLCO_3 TC which comprises pipelining and compensation, and OLCO_3 VQ which comprises pipelining with communication-dependent compressor. Both the versions of OLCO_3 are analyzed from a theoretical perspective: under some assumptions the authors conduct a theoretical analysis of the convergence of the proposed schemes. Finally, the method in its two variants is benchmarked and compared with state-of-the-art distributed algorithms. \n\n\n+ The authors makes a comprehensive review of the literature and the major techniques used in distributed training of NNs. \n\n+ The authors are focusing on two really critical aspects of distributed training: communication costs and delays. These two aspects represent the bottleneck of distributed training and contributes in these directions would be of great impact.  \n\n \nConcerns: \n\n- The paper is not well-written. In addition to some typos, the style is confused and therefore the paper results hard to read. The content is not clearly explained and presented. Overall the paper requires some re-writing and polishing.\n\n \n- The theoretical results are not commented enough and the derived bounds do require some extra explanation and contextualization.\n\n\n- Since the OLCO_3 method is motivated by the authors in terms of communication and delays efficiency, the theoretical analysis should also maybe account more for these two aspects and underline the major advantages with respect to the state-of-the-art methods in terms of communication costs and delays handling.\n \n\n- Regarding the benchmark section, only test metrics are shown but test metrics are not directly related to the convergence but rather with the generalization properties, while the theoretical results focus on the convergence. \n\n---------------------------------------------------------------------------------------------------------------------------------------------------", "extra_scores": {}, "extra_text": {}}, {"review_id": "XqkxGFgVSeF", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers delay-tolerant and communication-efficient in distributed training and proposes a training framework OLCO3 with local update steps, staleness compensation, and compression compensation. The proposed OLCO3 can be generalized to OLCO3-TC & OLCO3-OC (master-slave case), and OLCO3-VQ (both master-salve and all-reduce case).\n\n### pros.\n* the paper is well-written; the arguments are supported by both empirical and theoretical results.\n* the convergence analyses are provided for OLCO3-VQ and OLCO3-TC, for both SGD and momentum SGD.\n* in numerical results, both iid and non-iid cases are considered.\n\n### cons.\n* missing compression compensation baseline. the paper considers local update, staleness compensation, and compression compensation, but in the empirical results, only local SGD and some delay tolerance methods are considered. it is suggested to also include the results from the powerSGD and the signSGD, thus the readers can identify the source of quality loss.\n* different compression operators are used for different OLCO3 variants. I noticed that in the evaluation part, the paper considers  OLCO3-OC with signSGD, OLCO3-VQ with powerSGD, and OLCO3-TC with signSGD. it is encouraged to justify such a design choice.\n* unclear practical impact. even though it is intuitive to design a training system that has local update steps, staleness compensation, and compression compensation, its practical impact is still unclear to me (due to the trade-off between test accuracy and system performance). it is encouraged to include (e.g. a simulated) results to illustrate the potential trade-off (e.g. time-to-accuracy) on different distributed training scenarios (e.g. differ in latency, bandwidth, local computation capability).\n* the ideas like local update steps, staleness compensation, and compression compensation, have been well developed in the distributed machine learning community. though I do acknowledge the efforts of formulating/combining these ideas into a unified framework, the significance (novelty) of the paper might still have some limitations (as the proof seems quite standard to me). I would like to encourage authors to provide comprehensive empirical results to justify the pros and cons of the proposed scheme, as well as some practical guidelines.", "extra_scores": {}, "extra_text": {}}, {"review_id": "5u9L-cafLA8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method, called OLCO3, to reduce the communication cost in distributed learning. Experiments on real datasets are used for evaluation. The paper is well written. \n\nThe main idea of OLCO3 is to combine many existing communication reduction methods, including pipelining, gradient compression and periodic averaging. There does exist some novelty in OLCO3, but the novelty is not high. Furthermore, there has appeared one similar paper[A] which combines sparsification, quantization and local SGD into the same framework for communication reduction. But this paper does not cite [A], and empirical comparison with [A] is also not provided. \n\nAnother shortcoming of OLCO3 is that the computation-communication overlapping technique will introduce an extra memory cost of O(sd), which might be unacceptable for large deep models with a huge d when s is relatively large. \n\nFor experiments, the convincingness can be improved if test accuracy/training error vs. wall-clock time is also provided. \n  \n[A]. Basu, Debraj, et al. \"Qsparse-local-SGD: Distributed SGD with quantization, sparsification and local computations.\" Advances in Neural Information Processing Systems. 2019.\n\n\n------------------------\nAfter discussion:\n\nThe authors do not provide rebuttal. Hence, I keep the original opinion to give this paper a weak reject.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4agwuSfFuW", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "--- Summary\n\nThis paper proposes OLCO3, a new delay-tolerant SGD communication scheme and training framework for distributed deep neural network training. OLCO3 combines the existing ideas of Stale synchronous Parallel, batching the communication of doing multiple iterations, and gradient compression to achieve more communication efficiency. OLCO3 also uses staleness compensation and compression compensation techniques to improve model convergence under high stateness. Theoretical analysis shows that OLCO3 converges under SGD and momentum SGD. The evaluation was done with ResNet models on Cifar-10 and ImageNet datasets. Under a high staleness delay tolerance 56, OLCO3 achieves better convergence and has lower communication traffic than the baseline methods.\n\n\n--- Strengths\n\n- The paper is clearly written and has theoretical grounds.\n\n\n--- Major issues \n\nMy major issue with this paper is its novelty and experimental setups.\n\n- OLCO3 simply applies three existing delay-tolerant SGD techniques together. I agree that sometimes it needs special designs to combine multiple techniques and that successfully combining them could be an important contribution, but I am not sure it is the case for this work. For example, [Cui et al., 2014], used Stale synchronous Parallel and batched the communication for multiple iterations. [Lin et al., 2018] used gradient compression, and they also accumulated all the compression residuals and added them together with the gradients of the next iteration. So OLCO3's communication scheme and compression compensation techniques are not really novel.\n\n* [Cui et al., 2014] Exploiting bounded staleness to speed up big data analytics. USENIX ATC 2014.\n* [Lin et al., 2018] Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training. ICLR 2018.\n\n- The experiments in this paper used a delay tolerance of 56, which I think is too high for ResNet training. A delay tolerance of 56 means the workers will only communicate every 56 iterations when s=1, or they will have to tolerate 56 iterations of stale data when p=1. The ResNet-50 model has less than 25 million model parameters, and when represented in float32, they are only 100 MB in size. The sizes of the gradients are the same as the model parameters, so they are also 100 MB. I don't think it makes a lot of sense to delay the communication of just 100 MB of data for 56 iterations, especially when there are only two or four 4-GPU machines connected with 40 Gbps Ethernet. Showing that OLCO3 outperforms the other methods under this unrealistic delay tolerance is not very meaningful. The paper mentions that the high delay tolerance could be useful to federated learning, but federated learning is not very common right now, and the paper's experiments are not performed on a federated learning setup either.\n\n- The evaluation also did not measure the wall-clock training time. So it is not clear to me 1) how using the more stale gradient updates speeds up the training and 2) how much computational overhead the gradient compression incurs. I suggest the authors compare the wall-clock training time of their system with the wall-clock training time of synchronous SGD using the state-of-the-art distributed training frameworks.\n\n\n--- Other comments\n\n- Section 2, second paragraph, \"Note that Pipe-SGD is different from asynchronous SGD (Ho et al., 2013; Lian et al., 2015) which computes stochastic gradient using stale model and does not parallelize the computation and communication of a worker.\"\nThis statement is not correct. The State Synchronous Parallel parameter server proposed by [Ho et al., 2013] and [Cui et al., 2014] actually pipelines the communication with computation. Also, whether the communication is pipelined with the computation or not is orthogonal to the communication scheme. For example, the communication can be pipelined with the computation even for synchronous SGD because the model parameter updates from the training backward pass come out layer by layer, and the parameter server systems usually send out the computed parameter updates of the upper layers before the updates of the lower layers are computed.\n\n- Section 5, experimental setup.\nWhy was ResNet-50 model used for the ImageNet dataset but a larger ResNet-110 model was used for the much smaller Cifar-10 dataset?\n\n- Figure 1.\nPlease explain whether the communication budget is the total budget over all workers or the per-worker budget. The graph shows that Cifar-10 only has less than 1 GB of communication traffic even for the baseline synchronous SGD model. If that's the case, it is arguable whether it is indeed useful to do gradient compression when the total traffic for the whole training is only 1 GB.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: No discussion or answers to concerns are offered by the authors.
Given this, the current consensus remains the same as the initial review status, and AC's meta-review cannot provide any additional information.

This leads to rejection
Decision: Reject