Year: 2019

Abstract:
Traditional synchronous distributed training is performed inside a cluster since it requires high bandwidth and low latency network (e.g. 25Gb Ethernet or Infiniband). However, in many application scenarios, training data are often distributed across many geographic locations, where physical distance is long and latency is high. Traditional synchronous distributed training cannot scale well under such limited network conditions. In this work, we aim to scale distributed learning under high-latency network. To achieve this, we propose Delayed and Temporally Sparse (DTS) update that enables synchronous training to tolerate extreme network conditions without compromising accuracy. We benchmark our algorithms on servers deployed across three continents in the world: London (Europe), Tokyo (Asia), Oregon (North America) and Ohio (North America). Under such challenging settings, DTS achieves 90× speedup over traditional methods without loss of accuracy on ImageNet.

text: Traditional synchronous distributed training is performed inside a cluster since it requires high bandwidth and low latency network (e.g. 25Gb Ethernet or Infiniband). However, in many application scenarios, training data are often distributed across many geographic locations, where physical distance is long and latency is high. Traditional synchronous distributed training cannot scale well under such limited network conditions. In this work, we aim to scale distributed learning under high-latency network. To achieve this, we propose Delayed and Temporally Sparse (DTS) update that enables synchronous training to tolerate extreme network conditions without compromising accuracy. We benchmark our algorithms on servers deployed across three continents in the world: London (Europe), Tokyo (Asia), Oregon (North America) and Ohio (North America). Under such challenging settings, DTS achieves 90× speedup over traditional methods without loss of accuracy on ImageNet.

heading: 1 INTRODUCTION
text: Deep neural networks have demonstrated much success in solving large-scale machine learning problems (Krizhevsky et al., 2012; Simonyan & Zisserman, 2014; He et al., 2016). However, training deep neural networks may take days or even weeks to converge. In order to enable training in a reasonable time, distributed training is an important technique and gains increasing attention (Li et al., 2014; Dean et al., 2012; Recht et al., 2011; Goyal et al., 2017; Jia et al., 2018). To maintain a good scalability, a low latency and high bandwidth network is essential for most modern distributed systems. Existing frameworks (Chen et al., 2015; Xing et al., 2015; Moritz et al., 2015; Abadi et al., 2015; Akiba et al., 2017; Paszke et al., 2017; Sergeev & Del Balso, 2018) all require high-end network infrastructure such as 25Gbps Ethernet or Infiniband where bandwidth is as large as 10 to 100 Gbps and latency is as small as 1 us.
16x4 = 64 cards, batch size 32
latency(ms) speed SSGD DTS ECD-PSGD ASGD FedAvg 0 151 0.79 0.7935 0.7994
1 141 0.73 0.7907 0.7829
5 130 0.68 0.7878 0.7677
10 119 0.62 0.7816 0.7607 50 62.2 0.32 0.7866 0.70 0.68 0.7441 100 34.2 0.18 0.7853 0.7370 500 7.46 0.04 0.7812 0.5179 1000 3.73 0.02 0.7721 0.3764
16x4 = 64 cards, batch size 32-1
latency(ms) spee SSGD DTS ECD-PSGD 0 151 0.79 0.7935
1 141 0.73 0.7907 5 130 0.68 0.7878 10 119 0.62 0.7816 50 62.2 0.32 0.7866 0.70 100 34.2 0.18 0.7853 500 7.46 0.04 0.7812 1000 3.73 0.02 0.7721
Sc al
ab ili
ty
0.00
0.23
0.45
0.68
0.90
Network Latency (ms) 0 1 5 10 50 100 500 1000
SSGD
Bandwidth is easy to increase (e.g. stacking hardware) but latency is hard to improve (physical limits). For example, if we have two servers located at Shanghai and Boston respectively, even at the speed of light and direct air distance, it still takes 78ms∗ to send and receive a packet. In real world scenario, the latency can be only worse (around 700ms) because indirect routing between internet service providers (ISP) and queuing delay in switches. Such high latency cause severe scalability† issue for distributed training. As shown in Fig. 1, traditional distributed training algorithm scales poorly under such large latency.
In many scenarios, the training data involv s privacysensitive infor ation, such as personal medical history (Jochems et al., 2016; 2017) and keyboard input history (McMahan et al., 2 16; Konen et al., 2016; Bonawitz et al., 2019), thus cannot be centralized to a data center
due to security and legacy concerns (GDPR, 2016). When datasets are distributed across many
∗11, 725km × 2/(3× 108m/s) = 78.16ms. Information collected from Google Maps. †If a system can achieve M times speedup on N machines, the scalability is defined as M/N .
Under review as a conference paper at ICLR 2020
Latency Bandwidth Scalability
Inside 3 25600 819.2 Across 158750 29 8.192
London
TokyoOregon Ohio
102ms
210ms 97ms
70ms
Table 1-1 Latency Scalability
Across the world 3 2274 Inside a cluster 479000 23.32
Latency Speed
23
479,000
2,274
3
Inside a cluster Across the world
159,666x longer 98x worse
µs
µs
img/s
img/s
Figure 2: Network conditions across different continents (Left) and the comparison between connections inside a cluster (Right). Different from training inside a data center, long-distance distributed training suffers from high latency, which proposes a severe challenge to scale across the world.
locations across public clouds, private clusters and even edge devices, it is impossible to setup a low
latency network under long-distance connections and thereby hurts the scalability of training.
In this work, we enable scalable distributed training across different geographical locations with long distance and high latency network connection. We propose Delayed Update to tolerate latency by putting off the synchronization barrier to a later iteration; we also propose Temporally Sparse Update to amortize the latency and alleviate congestion by reducing the synchronization frequency. To ensure no loss of accuracy, we design a novel error compensation to overcome the staleness for both vanilla and momentum SGD. We focus on the widely adopted synchronous update using data parallelism. As shown in Fig. 1, DTS can maintain high scalability even when latency is as high as 1000ms. This result is also better than existing state of art technologies such as ECD-PSGD (results copied directly from their original paper (Tang et al., 2018a))
We benchmark our DTS under a challenging settings: training a deep neural network on four AWS P3 instances located in different continents of the world (Fig. 2). The measured latency is as large as 277ms (compared to internal latency 2us). In this case, the naive distributed synchronous SGD (SSGD) can only achieve a poor scalability of 0.008. It means in this setting, distributed training with 100 servers is even slower than single machine (0.8 v.s. 1.0). Meanwhile DTS achieves scalability of 0.72 without compromising the accuracy. In conclusion, our contributions are listed below:
• We propose delayed update to tolerate the latency and temporally sparse update to amortize the latency. While preserving the accuracy, delayed update tolerates up to 6 seconds latency and temporally sparse update reduced the traffic congestion by 20×. • We theoretically justify the convergence rate of our proposed algorithms. We show that both
algorithms can be as fast original SGD while scaling well under high latency. • With servers and data distributed in four different countries across the world, we can train
ResNet-50 on ImageNet with scalability. To our best knowledge, DTS is the first work that can achieve scalable synchronous distributed training under such high latency.

heading: 2 RELATED WORK
text: Distributed Learning becomes ever more important as the sizes of both datasets and models increase. Many studies have been made to explore the efficiency, both at the algorithm level (Li et al., 2014; Dean et al., 2012; Recht et al., 2011; Goyal et al., 2017; Jia et al., 2018) and at the framework level (Chen et al., 2015; Akiba et al., 2017; Abadi et al., 2015; Paszke et al., 2017; Sergeev & Del Balso, 2018). In most of distributed algorithms, each node performs computation and exchange updates through network. A key component to improve scalability is to reduce the communication-tocomputation ratio. The communication cost is determined by latency and bandwidth. Conventional studies focus on reducing bandwidth requirements as the latency of internal traffic is usually low.
Gradient quantization / compression has been proposed to reduce the data to be transferred. Onebit gradient gradient (Seide et al., 2014) achieves 10× speedup using 20 GPUs on text-to-speech task. QSGD (Alistarh et al., 2016) and Terngrad (Wen et al., 2017) further improves the trade-off between accuracy and gradient precision. But the theoretical limit of the quantization cannot go beyond 32. To overcome the limitation, gradient sparsification using predefined static threshold (Strom, 2015; Aji &
Under review as a conference paper at ICLR 2020
Heafield, 2017) and dynamic compression ratio (Chen et al., 2018) demonstrate that 99% gradients can be pruned with negligible degradation on model performance. (Sattler et al., 2018) combines both quantization and compression to push the ratio to a new level. DGC (Lin et al., 2017) and DoubleSequeeze (Tang et al., 2019) explore how to compensate the error to preserve the accuracy better. The convergence of quantization and compression is also discussed in (Tang et al., 2019; Jiang & Agrawal, 2018; Alistarh et al., 2018). However, latency remains an issue, especially when servers are not in the same physical location.
Learning on decentralized data has become increasingly popular recently as the growing awareness of data privacy (GDPR, 2016). For example, Federated Learning (Google, 2017) aim to jointly train a model without centralizing the data and have been used to train models for medical treatments across multiple hospitals (Jochems et al., 2016), analyze patient survival situations from various countries (Jochems et al., 2017) and build predictive keyboards to improve typing experience (McMahan et al., 2016; Google, 2017; Bonawitz et al., 2019). However, existing federated learning works do not scale well under high latency network. An orthogonal exploration is Decentralized Training where only partial synchronization is performed in each update, such as AD-PSGD (Lian et al., 2017) and D2 (Tang et al., 2018b). None of them has been evaluated on large learning tasks yet.
Asynchronous SGD (ASGD) is derived from (Tsitsiklis et al., 1986) and has advantages in unstable latency and fault tolerance. Different from synchronous SGD (SSGD), ASGD relaxes synchronization by allowing training on inconsistent models and powers many successful applications such as HOGWILD! (Recht et al., 2011), BUCKWILD! (De Sa et al., 2015) and dist-belief (Dean et al., 2012). However, most of them are implemented through parameter server (Dean et al., 2012; Chilimbi et al., 2014; Li et al., 2014) and leads to problems like communication congestion and resource congestion when scaling up. Moreover, training on inconsistent models leads to different behaviors compared to training on a single device. Though there are studies discussing the convergences (Recht et al., 2011; De Sa et al., 2015) and showing that ASGD converges as good as SSGD (Lian et al., 2015), synchronous SGD (SSGD) is usually preferred in practice (Goyal et al., 2017; Sun et al., 2019) because it has consistent behaviors when increasing the number of machines and therefore is easy to develop and deploy.

heading: 3 APPROACH
text: To motivate this section, we first review the mechanism of synchronous distributed training: at each step, each node will first compute gradients locally, then they wait for the collective operation to transmit gradients to each other to calculate the average. They use the averaged gradient to update the weight and continue to the next step. As shown in right of Fig. 3a, when the communication increases , the whole training process would be drastically slowed down.
To address the problem, our proposed algorithm contains two parts: delayed update (Fig. 3b) and temporally sparse update (Fig. 3c). With the delayed update, instead of waiting for average gradients to come back, it puts off the synchronization barrier to steps later to tolerate the latency. With the temporally sparse update, the synchronization frequency is reduced to amortize latency.
Throughout the paper, we use the following notions:
• γ: learning rate. • t: iteration steps that the synchronization bar-
rier is delayed. • p: iteration steps between temporally sparse
update intervals. • u(i,j): momentum at iteration i on worker j. • u′(i,j): error compensated momentum at itera-
tion i on worker j.
• w(i,j): model weights at iteration i on worker j.
• w′(i,j): error compensated weights at iteration i on worker j.
• ∇w(i,j): local gradients at iteration i on worker j.
• ∇w(i): global averaged gradients at iteration i.

heading: 3.1 DELAYED UPDATE
text: In modern implementations of vanilla SSGD, the transmission is partially pipelined with backpropogration: Synchronizing gradients of nth layer can be performed simultaneously with backpropagating (n − 1)th layer. However, it is not enough to cover communication since latency on
Under review as a conference paper at ICLR 2020
Environment Agent Channel Pruning Policy gradient Deep-Q Network Actor Critic Actions: sparsity for each layer Observations / Reward: accuracy, FLOPs…
Hardware Latency Xxx xxx
1 1
2 2
3 3
4 4 1 2 3 4
Environment Agent Channel Pruning Policy gradient Deep-Q Network Actor Critic Actions: sparsity for each layer Observations / Reward: accuracy, FLOPs…
Hardware Latency Xxx xxx
1 1
2 2
3 3
4 4 1 2 3 4
Environment Agent Cha el Pruning Policy gradient Deep-Q Network Actor Critic Actions: sparsity for each layer Observations / Reward: accuracy, FLOPs…
Hardware Latency Xxx xxx
1 2 3 4 1 2 3 4
long-distance connection is usually larger ( ≥ 100ms) than propagating a layer ( ≈ 11ms). To relax the limitation, we design delayed update to put off the the synchronization barrier by n steps as shown in Fig. 3b. To ensure minimal loss on accuracy, we modify the gradient update formula with error compensations.
To understand, we start with vanilla SGD: Consider a worker with index j, the weights at timestamp n during distributed training are derived via
w(n,j) = w(n−1,j) − γ∇w(n−1) = w(0,j) − γ n−1∑ i=0 ∇w(i) (1)
where ∇w(n−1) is the averaged gradients calculated by gathering all local gradients ∇w(n−1,j). In SSGD, the synchronization has to finish before (n+ 1)th forwarding. In delayed update, we delay the barrier to (n+ t)th iteration and because of the delay, ∇w(n−1) is not received at timestamp n. We use local gradients to update instead.
w(n,j) = w(n−1,j) − γ∇w(n−1,j) (2)
Meanwhile, stale gradients ∇w(n−t) arrive. At timestamp n − t, we performed the gradient step using local gradients∇w(n−t,j), which should be the global averaged∇w(n−t) in SSGD. We correct the mismatch caused by replacing ∇w(n−t,j) with ∇w(n−t). From Eq. 1, it adds a compensation term, which is the difference of two gradients.
w′(n,j) = w(n−1,j) − γ∇w(n−1,j)︸ ︷︷ ︸ local gradients −γ(∇w(n−t) −∇w(n−t,j)︸ ︷︷ ︸ error compensation )
= w(n,j) − γ(∇w(n−t) −∇w(n−t,j)) (3)
Next, we consider momentum SGD. With momentum m, the weight at timestamp n is updated by
u(n,j) = mu(n−1,j) +∇w(n,j) w(n,j) = w(n−1,j) − γu(n−1,j) (4)
Under review as a conference paper at ICLR 2020
We rewrite the cumulative form to general form
u(n,j) = n∑ i=0 mi∇w(n−i,j)
= n∑ i=0 mn−i∇w(i,j)
(5)
w(n,j) = w(0,j) − γ n−1∑ i=0 u(i,j)
= w(0,j) − γ n−1∑ i=0 i∑ k=0 mi−k∇w(k,j)
= w(0,j) − γ n−1∑ i=0 n−1−i∑ k=0 mk∇w(i,j)
(6)
Then, we can derive the compensated momentum
u′(n,j) = mu(n−1,j) +∇w(n−1,j) +m t(∇w(n−t) −∇w(n−t,j))
= u(n,j) +m t(∇w(n−t) −∇w(n−t,j))
(7)
and weights similarly
w′(n,j) = w(n−1,j) − γu(n−1,j) − γ t−1∑ k=0 mk(∇w(n−t) −∇w(n−t,j))
= w(n,j) − γ t−1∑ k=0 mk(∇w(n−t) −∇w(n−t,j))
(8)
In original synchronous stochastic gradient descent (SSGD), every worker receives averaged gradients from n− 1 at timestamp n. This requires collective operation (e.g. Allreduce) to execute quickly; otherwise, it will slow down the training process. In delayed update, the barrier of the collective operation is moved from timestamp n to n+ t− 1. It means as long as the gradients are transmitted within t× Tcompute, the training is not blocked. To put some real numbers, assume we are training ResNet-50 on Nvidia Tesla V100, each step takes around 300ms. If we delay the update by 20 steps, even with latency as large as 6 seconds, the communication still can be fully covered by computations. We attach the proof of convergence in Appendix A.2.1 and show this is as fast as SSGD.

heading: 3.2 TEMPORALLY SPARSE UPDATE
text: Delayed update provides a good solution to tolerate latency. However, there still remains two issues and network congestion is the first one. In the original SSGD, only one transmission is performed during one iteration. But when using delayed update, there can be up to t transmissions at the same time. Without a special hacking to low-level network driver, gradients sent earlier may arrive later, which is not what we want. The second one is latency variance. In real world network, especially for those long-distance connections, the latency varies in a large range. Even though the average latency is small, some accidentally high latency can slow the system.
To address, we adapt temporally sparse update to reduce the communication frequency and design corresponding error compensation to guarantee the accuracy. As demonstrated in Fig. 3c, temporally sparse update only synchronizes for every p steps. For those steps where synchronization is not performed, each worker updates its model with local gradients. For those steps where synchronization is performed, each worker calculates error compensations based averaged information. As a result, the networking congestion is alleviated and the networking latency is amortized across multiple local update steps.
For vanilla SGD, like the delayed update, we can derive the compensation term for temporally sparse update from Eq. 1, which is the difference between accumulated gradients. Note the compensation in temporally sparse update only applies when n (mod p) ≡ 0.
w′(n,j) = w(n,j) − γ( n−1∑ i=n−p ∇w(i) − n−1∑ i=n−p ∇w(i,j)) (9)
Under review as a conference paper at ICLR 2020
For SGD with momentum acceleration, based on accumulated gradients is not enough to compensate both∇w(n,j) and u(n,j). We need to transmit an extra term to correct the momentum:
u′(n,j) = u(n,j) + ( n−1∑ i=n−p mn−i∇w(i) − n−1∑ i=n−p mn−i∇w(i,j)) w′(n,j) = w(n,j) − γ( n−1∑ i=n−p n−1−i∑ k=0 mk∇w(i) − n−1∑ i=n−p n−1−i∑ k=0 mk∇w(i,j))
= w(n,j) − γ( n−1∑ i=n−p i∑ k=n−p mi−k∇w(k) − n−1∑ i=n−p i∑ k=n−p mi−k∇w(k,j))
(10)
Let S(i,j) = ∑i k=n−pm
i−k∇w(k,j). Note S(i+1,j) = mS(i,j) + ∇w(i+1,j) and S(n−p+1,j) = ∇w(n−p,j), the formula can be written as:
u′(n,j) = u(n,j) + (S(n) − S(n,j))
w′(n,j) = w(n,j) − γ( n−1∑ i=n−p S(i) − n−1∑ i=n−p S(i,j)) (11)
Note temporally sparse update is different from gradient accumulation (forward and backward N times, accumulate the gradients and optimizer steps only 1 time). Gradient accumulation is equivalent to increasing the batch size and requires to adjust learning rate and the parameters of batch normalization to ensure smooth convergence. Temporally sparsity updates model every iteration and compensate error every N steps. It does not require any changes to the hyper-parameters. We prove the convergence of temporally sparse update in Appendix A.2.2 and demonstrate that it enjoys the same convergence rate as SSGD.

heading: 3.3 DELAYED AND TEMPORALLY SPARSE UPDATE
text: The delayed technique and temporally sparse update can be combined together. The compensation formulas for vanilla SGD is
w′(n,j) = w(n,j) − γ( n−t−1∑ i=n−t−p ∇w(i) − n−t−1∑ i=n−t−p ∇w(i,j)) (12)
and for momentum SGD is
u′(n,j) = u(n,j) +m t(Sn−t − S(n−t,j))
w′(n,j) = w(n,j) − γm t( n−t−1∑ i=n−t−p Si − n−t−1∑ i=n−t−p S(i,j)) (13)
Original ring allreduce transfers 2||w|| packets (Thakur et al., 2005). Though temporally sparse update doubles data transferred, the temporal sparsity t is always larger than 2. As a consequence, combing two methods can further improve scalability under challenging networking ( Tab. 1).
Under review as a conference paper at ICLR 2020
D, T, D + T Training curve
| Scalability v.s. latency (same machine)
| Scalability v.s. machine (same latency)
16x4 = 64 cards, batch size 32 latency(ms ) speed Original delay=4 delay=8 delay=12 delay=16 delay=20 0 151 0.79 0.7981 0.7935 0.7935 0.7978 0.7935 1 141 0.73 0.7917 0.7907 0.7907 0.7907 0.7907 5 130 0.68 0.7878 0.7892 0.7892 0.7892 0.7878
10 119 0.62 0.7815 0.7816 0.7816 0.7816 0.7816
50 62.2 0.32 0.7793 0.7866 0.7866 0.7866 0.7866
100 34.2 0.18 0.7726 0.7853 0.7853 0.7853 0.7853
500 7.46 0.04 0.73 0.7812 0.7812 0.7812 0.7812
1000 3.73 0.02 0.53 0.7321 0.7790 0.7789 0.7721
5000 1 0.01 0.03 0.45 0.4510 0.5355 0.7321
Sc al
ab ili
ty
0.0
0.2
0.5
0.7
0.9
Network latency (ms) 0 1 5 10 50 100 500 1000 5000
Original delay=8 delay=12 delay=20
16x4 = 64 cards, batch size 32-1
latency(ms) original Temporal Sparsity=4 Temporal=8 Temporal=12 Temporal=16 Temporal=20
0 0.7994 0.8053 0.8399 0.8319 0.8639
1 0.7829 0.8054 0.8277 0.8310 0.8523
5 0.7677 0.8090 0.8216 0.8194 0.8436
10 0.7607 0.7994 0.8085 0.8183 0.8328
15 0.7573 0.7895 0.8120 0.8168 0.8286
20 0.7529 0.7876 0.8112 0.8172 0.8263
25 0.7533 0.7826 0.8108 0.8063 0.8261
50 0.7441 0.7820 0.8081 0.8085 0.8189
100 0.7370 0.7806 0.7841 0.8072 0.8127
150 0.6883 0.7561 0.7750 0.8026 0.8129
200 0.6729 0.7330 0.7739 0.7966 0.8043
Sc al
ab ili
ty
0
0.225
0.45
0.675
0.9
Network Latency (ms) 0 1000 2000 3000 4000 5000 6000
Temporal=8 Temporal=12 Temporal Sparsity=4 Temporal=16 Temporal=20
0
0.2
0.4 0.6 0.8
latency=1000ms-1 Nodes ideal L=0 d=4, t=4 delay=8, temporal= delay=12, t=8 delay=20, t=12 4 4 7 8 8 8 8
8 8 14 15 15 16 16
16 16 27 30 30 31 31
32 32 55 58 59 61 63
64 64 110 91 116 121 123
latency=1000ms-1-1
Nodes Nodes D=4, T=4 (200ms) D=20, T=12 (200ms) SSGD (0ms) SSGD (200ms) Ideal
0 0 0 0 0
4 1 0.8 0.8 0.8 1 1
8 2 1.5 1.5 1.6 0.016 2
16 4 3 3 3.1 0.030 4
32 8 5.8 5.9 6.1 0.066 8
64 16 9.1 11.6 12.1 0.128 16
Sc al
ab ili
ty
0
4
8
12
16
Number of servers
0 4 8 12 16
D=4, T=4 (200ms) D=20, T=12 (200ms) SSGD (0ms) SSGD (200ms) Ideal
16x4 = 64 cards, batch size 32-1-1
latency(ms) Original Temporal Sparsity=4 Temporal Sparsity=8 Temporal Sparsity=12 Temporal Sparsity=16 Temporal Sparsity=20
0 0.79 0.7994 0.8053 0.8399 0.8319 0.8639
1 0.76 0.7829 0.8054 0.8277 0.8310 0.8523
5 0.68 0.7677 0.8090 0.8216 0.8194 0.8436
10 0.62 0.7607 0.7994 0.8085 0.8183 0.8328
50 0.32 0.7441 0.7820 0.8081 0.8085 0.8189
100 0.18 0.7370 0.7806 0.7841 0.8072 0.8127
500 0.04 0.5179 0.6460 0.7135 0.7333 0.7529
1000 0.02 0.3764 0.5132 0.5959 0.6364 0.6581
5000 0.01 0.111 0.2123 0.2656 0.3143 0.3604
Table 2 with load balance balanced without load balance unbalanced 0.9 6.24667472793229 0.9 5.53935234827364 0.85 5.23536863440588 0.85 4.56400742115028 0.8 4.41746119970927 0.8 3.73158046807281 0.7 3.15048025613661 0.7 2.71773154115264 0.6 2.42040902382458 0.6 2.15947329919532 0.5 1.95871011772735 0.5 1.79981186635543
0.4 1.64360026725208 0.4 1.54608167357505 0.3 1.41571093846344 0.3 1.36450079239303 0.2 1.28799022663243 0.2 1.28212446485078
0 1.00005807538185 0 1.00005807538185
Table 2-1
L2 regularization w/o retrain Accuracy Loss w/ o Retrain [L2 reg.] L1 regularization w/o retrain
L1 regularization w/ retrain
L2 regularization w/ retrain
L2 regularization w/ iterative prune and retrain
0 0 0 0 0 0 0 0 0 0.875 0.0006 0.46 0.3351 -0.0002 0.3351 0 0.3351 0.000139 0.3351 0 0.888888888888889 0.0003 0.72 0.4991 -0.0011 0.4991 -0.0008 0.4991 0.0000389999999999002 0.4991 0.0004 0.9 -0.0008 1.05 0.6657 -0.0092 0.6657 -0.0027 0.6657 -0.00126100000000007 0.6657 0.0018 0.916666666666667 -0.0033 1.27 0.7494 -0.0216 0.7494 -0.0064 0.7494 -0.00216100000000008 0.7494 0.0015 0.928571428571429 -0.006 1.44 0.8 -0.0407 0.8 -0.0125 0.8 -0.0035 0.8 0.0003 0.9375 -0.0104 1.58 0.8335 -0.0739 0.8335 -0.021 0.8335 -0.0057 0.8335 -0.0017 0.94705 -0.0199 1.7 0.8569 -0.119 0.8569 -0.0298 0.8569 -0.00806099999999998 0.8569 -0.00458100000000006 0.95736 -0.042
1.81 0.8749 -0.1875 0.8749 -0.0443 0.8749 -0.010661 0.8749 -0.0081810000000001 0.963 -0.06
2.0 0.899 -0.3617 0.899 -0.0896 0.899 -0.018 0.899 -0.0158
2.27 0.9299 -0.6365 0.9299 -0.3292 0.9299 -0.0413 0.9299 -0.0388
2.78 0.95 -0.7916 0.95 -0.7552 0.95 -0.115561 0.95 -0.088381
A cc
ur ac
y Lo
ss -4.5% -4.0% -3.5% -3.0% -2.5% -2.0% -1.5% -1.0% -0.5% 0.0% 0.5%
Parametes Pruned Away
40% 50% 60% 70% 80% 90% 100%
L2 regularization w/o retrain L1 regularization w/o retrain L1 regularization w/ retrain L2 regularization w/ retrain L2 regularization w/ iterative prune and retrain
Sc al
ab ili
ty
0.0
0.2
0.5
0.7
0.9
Network latency (ms) 0 1 5 10 50 100 500 1000 5000
Original Temporal Sparsity=4 Temporal Sparsity=8 Temporal Sparsity=12 Temporal Sparsity=16 Temporal Sparsity=20
Delay=4 delay=16
(a) The learning curve with different delay steps and scalability under various latency.
r , t i l t ( ) ri i l l l l l l . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . .
Sc al
ab ili
ty
.
.
.
.
.
t r l t ( )
ri i l delay=4 l l l l
16x4 = 64 cards, batch size 32-1
latency(ms) original Temporal Sparsity=4 Temporal=8 Temporal=12 Temporal=16 Temporal=20
0 0.7994 0.8053 0.8399 0.8319 0.8639
1 0.7829 0.8054 0.8277 0.8310 0.8523
5 0.7677 0.8090 0.8216 0.8194 0.8436
10 0.7607 0.7994 0.8085 0.8183 0.8328
15 0.7573 0.7895 0.8120 0.8168 0.8286
20 0.7529 0.7876 0.8112 0.8172 0.8263
25 0.7533 0.7826 0.8108 0.8063 0.8261
50 0.7441 0.7820 0.8081 0.8085 0.8189
100 0.7370 0.7806 0.7841 0.8072 0.8127
150 0.6883 0.7561 0.7750 0.8026 0.8129
200 0.6729 0.7330 0.7739 0.7966 0.8043
Sc al
ab ili
ty
0
0.225
0.45
0.675
0.9
et ork atency ( s) 0 1000 2000 3000 4000 5000 6000
Te poral=8 Te poral=12 Te poral Sparsity=4 Te poral=16 Te poral=20
.
. . .
l t i l , t l , t r l l , t l , t
latency 1000 s-1-1
odes odes =4, T=4 (200 s) =20, T=12 (200 s) SS (0 s) SSGD (200 s) Ideal
0 0 0 0 0
4 1 0.8 0.8 0.8 1 1
8 2 1.5 1.5 1.6 0.016 2
16 4 3 3 3.1 0.030 4
32 8 5.8 5.9 6.1 0.066 8
64 16 9.1 11.6 12.1 0.128 16
Sc al
ab ili
ty
er f ser ers
, ( s) , ( s) ( s) ( s)
I eal
16x4 = 64 cards, batch size 32-1-1
latency( s) Original Te poral Sparsity=4 Te poral Sparsity=8 Te poral Sparsity=12 Te poral Sparsity=16 Te poral Sparsity=20
0 0.79 0.7994 0.8053 0.8399 0.8319 0.8639
1 0.76 0.7829 0.8054 0.8277 0.8310 0.8523
5 0.68 0.7677 0.8090 0.8216 0.8194 0.8436
10 0.62 0.7607 0.7994 0.8085 0.8183 0.8328
50 0.32 0.7441 0.7820 0.8081 0.8085 0.8189
100 0.18 0.7370 0.7806 0.7841 0.8072 0.8127
500 0.04 0.5179 0.6460 0.7135 0.7333 0.7529
1000 0.02 0.3764 0.5132 0.5959 0.6364 0.6581
5000 0.01 0.111 0.2123 0.2656 0.3143 0.3604
l it l l l it t l l
l . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . .
. .
Table 2-1
L2 regularization w/o retrain Accuracy Loss w/ o Retrain [L2 reg.] L1 regularization w/o retrain
L1 regularization w/ retrain
L2 regularization w/ retrain
L2 regularization w/ iterative prune and retrain
0 0 0 0 0 0 0 0 0 0.875 0.0006 0.46 0.3351 -0.0002 0.3351 0 0.3351 0.000139 0.3351 0 0.888888888888889 0.0003 0.72 0.4991 -0.0011 0.4991 -0.0008 0.4991 0.0000389999999999002 0.4991 0.0004 0.9 -0.0008 1.05 0.6657 -0.0092 0.6657 -0.0027 0.6657 -0.00126100000000007 0.6657 0.0018 0.916666666666667 -0.0033 1.27 0.7494 -0.0216 0.7494 -0.0064 0.7494 -0.00216100000000008 0.7494 0.0015 0.928571428571429 -0.006 1.44 0.8 -0.0407 0.8 -0.0125 0.8 -0.0035 0.8 0.0003 0.9375 -0.0104 1.58 0.8335 -0.0739 0.8335 -0.021 0.8335 -0.0057 0.8335 -0.0017 0.94705 -0.0199 1.7 0.8569 -0.119 0.8569 -0.0298 0.8569 -0.00806099999999998 0.8569 -0.00458100000000006 0.95736 -0.042
1.81 0.8749 -0.1875 0.8749 -0.0443 0.8749 -0.010661 0.8749 -0.0081810000000001 0.963 -0.06
2.0 0.899 -0.3617 0.899 -0.0896 0.899 -0.018 0.899 -0.0158
2.27 0.9299 -0.6365 0.9299 -0.3292 0.9299 -0.0413 0.9299 -0.0388
2.78 0.95 -0.7916 0.95 -0.7552 0.95 -0.115561 0.95 -0.088381
A cc
ur ac
y Lo
ss
- . - . - . - . - . - . - .
.
.
.
.
r t r
r l ri ti / r tr i r l ri ti / r tr i r l ri ti / r tr i r l ri ti / r tr i r l ri ti / it r ti r r tr i
Sc al
ab ili
ty
.
.
.
.
.
et r late c ( s) 0 1 5 10 50 100 500 1000 5000
temporal sparsity=4 temporal sparsity=16
temporal sparsity=8 temporal sparsity=20 ri i al temporal Sparsity=12
(b) The learning curve with different temporal sparsity and scalability under various latency. Figure 4: Compare the top-1 accuracy and scalability on ImageNet training.

heading: 4 EXPERIMENT

heading: 4.1 EXPERIMENT SETTINGS
text: We evaluate our DTS on image classification task. We studies ResNet-50 (He et al., 2016) on ImageNet (Deng et al., 2009). ImageNet contains 1.2 million training images and 50,000 validation images in 1000 classes. We train ImageNet model with momentum SGD using warmup strategy (Goyal et al., 2017) and cosine anneal learning rate decay (Loshchilov & Hutter, 2016) with 120 epochs. Standard data augmentations random crop and flip are adapted. We set the initial learning rate 0.0125 for which grows linearly w.r.t number of GPUs. For a fair comparison, the training settings are set the same among all experiments.
When performing ablation studies under different latency, we synthesis the network condition using netem‡. When training across the world, th limited network is benchma ked using qperf §. We implement DST in PyTorch framework (Paszke et al., 2017) and adapt Horovod (Sergeev & Del Balso, 2018) as the distributed training backend. To make results reproducible, we conduct our experiment on 16 standard Amazon p.large EC2 instances with eight Nvidia Tesla V100 on each and will release the codebase when less anonymous.

heading: 4.2 RESULTS OF DELAYED UPDATE
text: Under review as a conference paper at ICLR 2020
D, T, D + T Training curve
| Scalability v.s. latency (same machine) | Scalability v.s. machine (same latency)
16x4 = 64 cards, batch size 32 latency(ms ) speed Original delay=4 delay=8 delay=12 delay=16 delay=20 0 151 0.79 0.7981 0.7935 0.7935 0.7978 0.7935 1 141 0.73 0.7917 0.7907 0.7907 0.7907 0.7907 5 130 0.68 0.7878 0.7892 0.7892 0.7892 0.7878 10 119 0.62 0.7815 0.7816 0.7816 0.7816 0.7816 50 62.2 0.32 0.7793 0.7866 0.7866 0.7866 0.7866 100 34.2 0.18 0.7726 0.7853 0.7853 0.7853 0.7853 500 7.46 0.04 0.73 0.7812 0.7812 0.7812 0.7812 1000 3.73 0.02 0.53 0.7321 0.7790 0.7789 0.7721 5000 1 0.01 0.03 0.45 0.4510 0.5355 0.7321
Sc al
ab ili ty
0.0
0.2
0.5 0.7 0.9
Network latency (ms) 0 1 5 10 50 100 500 1000 5000
Original delay=4 delay=8 delay=12 delay=16 delay=20
0 0.7994 0.8053 0.8399 0.8319 0.8639
1 0.7829 0.8054 0.8277 0.8310 0.8523
5 0.7677 0.8090 0.8216 0.8194 0.8436
10 0.7607 0.7994 0.8085 0.8183 0.8328
15 0.7573 0.7895 0.8120 0.8168 0.8286
20 0.7529 0.7876 0.8112 0.8172 0.8263
25 0.7533 0.7826 0.8108 0.8063 0.8261
50 0.7441 0.7820 0.8081 0.8085 0.8189
100 0.7370 0.7806 0.7841 0.8072 0.8127
150 0.6883 0.7561 0.7750 0.8026 0.8129
200 0.6729 0.7330 0.7739 0.7966 0.8043
250 0.6371 0.7261 0.7769 0.7588 0.7924
500 0.5179 0.6460 0.7135 0.7333 0.7529
1000 0.3764 0.5132 0.5959 0.6364 0.6581
1500 0.2905 0.4330 0.5049 0.5711 0.6157
2000 0.2390 0.3696 0.4607 0.5115 0.5548
2500 0.2011 0.3234 0.4080 0.4610 0.5098
5000 0.111 0.2123 0.2656 0.3143 0.3604
Sc al
ab ili
ty
0
0.225
0.45
0.675
Network Latency (ms) 0 1000 2000 3000 4000 5000 6000
0 0.2 0.4 0.6 0.8
latency=1000ms-1 Nodes ideal L=0 d=4, t=4 delay=8, temporal= delay=12, t=8 delay=20, t=12 4 4 7 8 8 8 8 8 8 14 15 15 16 16 16 16 27 30 30 31 31 32 32 55 58 59 61 63 64 64 110 91 116 121 123
1 0.76 0.7829 0.8054 0.8277 0.8310 0.8523
5 0.68 0.7677 0.8090 0.8216 0.8194 0.8436
10 0.62 0.7607 0.7994 0.8085 0.8183 0.8328
50 0.32 0.7441 0.7820 0.8081 0.8085 0.8189
100 0.18 0.7370 0.7806 0.7841 0.8072 0.8127
500 0.04 0.5179 0.6460 0.7135 0.7333 0.7529
1000 0.02 0.3764 0.5132 0.5959 0.6364 0.6581
5000 0.01 0.111 0.2123 0.2656 0.3143 0.3604
Table 2 with load balance balanced without load balance unbalanced 0.9 6.24667472793229 0.9 5.53935234827364 0.85 5.23536863440588 0.85 4.56400742115028 0.8 4.41746119970927 0.8 3.73158046807281 0.7 3.15048025613661 0.7 2.71773154115264 0.6 2.42040902382458 0.6 2.15947329919532 0.5 1.95871011772735 0.5 1.79981186635543 0.4 1.64360026725208 0.4 1.54608167357505 0.3 1.41571093846344 0.3 1.36450079239303 0.2 1.28799022663243 0.2 1.28212446485078 0 1.00005807538185 0 1.00005807538185
L2 regularization w/o retrain Accuracy Loss w/ o Retrain [L2 reg.] L1 regularization w/o retrain
L1 regularization w/ retrain
L2 regularization w/ retrain
L2 regularization w/ iterative prune and retrain
0 0 0 0 0 0 0 0 0 0.875 0.0006 0.46 0.3351 -0.0002 0.3351 0 0.3351 0.000139 0.3351 0 0.888888888888889 0.0003 0.72 0.4991 -0.0011 0.4991 -0.0008 0.4991 0.0000389999999999002 0.4991 0.0004 0.9 -0.0008 1.05 0.6657 -0.0092 0.6657 -0.0027 0.6657 -0.00126100000000007 0.6657 0.0018 0.916666666666667 -0.0033 1.27 0.7494 -0.0216 0.7494 -0.0064 0.7494 -0.00216100000000008 0.7494 0.0015 0.928571428571429 -0.006 1.44 0.8 -0.0407 0.8 -0.0125 0.8 -0.0035 0.8 0.0003 0.9375 -0.0104 1.58 0.8335 -0.0739 0.8335 -0.021 0.8335 -0.0057 0.8335 -0.0017 0.94705 -0.0199 1.7 0.8569 -0.119 0.8569 -0.0298 0.8569 -0.00806099999999998 0.8569 -0.00458100000000006 0.95736 -0.042 1.81 0.8749 -0.1875 0.8749 -0.0443 0.8749 -0.010661 0.8749 -0.0081810000000001 0.963 -0.06 2.0 0.899 -0.3617 0.899 -0.0896 0.899 -0.018 0.899 -0.0158 2.27 0.9299 -0.6365 0.9299 -0.3292 0.9299 -0.0413 0.9299 -0.0388 2.78 0.95 -0.7916 0.95 -0.7552 0.95 -0.115561 0.95 -0.088381
A cc
ur ac
y Lo ss -4.5% -4.0% -3.5% -3.0% -2.5% -2.0% -1.5% -1.0% -0.5% 0.0% 0.5%
Parametes Pruned Away
40% 50% 60% 70% 80% 90% 100%
L2 regularization w/o retrain L1 regularization w/o retrain L1 regularization w/ retrain L2 regularization w/ retrain L2 regularization w/ iterative prune and retrain
In original SSGD and modern deep learning frameworks, though the transmission is partially pipelined with backpropogration: Synchronizing gradients of nth layer can be performed simultaneously with back-propagating (n− 1)th layer, it is not enough to fully cover communication since latency on long distance connection is usually larger ( ≥ 100ms) than propagating a layer (11ms). By delaying the synchronization, delayed update provides much more spare time for transmission and thus scales better. As shown in Fig. 4a, the larger the delayed interval is, the better tolerance towards latency. The scalability keeps stable until maximum tolerance is exceeded.

heading: 4.3 RESULTS OF TEMPORALLY SPARSE UPDATE
text: The connection of real-world network has many bothering issues such as unstable latency and congestion on routers. Temporally sparse is introduced to amortize thes via reducing the synchronization frequency. The results are shown in Fig. 4b(Left): we start with temporal sparsity 4 and increase to 20. With proposed compensation, the temporally sparse update has a negligible loss on accuracy. Fig. 4(Right) exhibits how temporally sparse training scales under different network latency. The scalability degrades slower than because temporally sparse update amortizes the latency.

heading: 4.4 DISTRIBUTED TRAINING ACROSS THE WORLD
text: With two powerful techniques, we are close to our original target of distributed training across world. To evaluate DTS, we deploy located at four different locations across the world: Tokyo(Japan), London (U.K), Oregon (U.S.A) and Ohio(U.S.A). The latency information is shown in Fig.2. The real latency across the ring allreduce is about 479ms through Ethernet. On V100 GPU, ResNet-50 takes around 300ms to forward and backward. Therefore delayed update with steps more than 4 is already enough to tolerate such a network. In terms of latency variance and network congestion, we integrate temporally sparse update to alleviate which drastically reduces the bandwidth requirement by t times. However, there is still a bottleneck on bandwidth for cross-continent connections (e.g. Tokyo to London). Though theoretically bandwidth is achievable by switching to better internet service providers, AWS does not provide such an option. As an economical alternative, we adapt deep gradient compression (Lin et al., 2017) to work through. As shown in Tab. 2a, DTS has little effect on training accuracy. Meanwhile, DTS demonstrates strong scalability (0.72) under high latency (200ms between workers) and this performance is close to what conventional algorithms achieved inside a data center (speedup ratio 0.78 and 1us latency).

heading: 5 CONCLUSION
text: In this paper, we propose two novel delayed update and temporally sparse update methods to scale synchronous distributed training on servers located at different continents across the world. We demonstrate that delayed synchronization and temporally sparse update are both accuracy preserving while tolerate poor network conditions. We believe that our work will open future avenues for a wide range of decentralized learning applications.
Under review as a conference paper at ICLR 2020

heading: A APPENDIX
text: A.1 CONNECTION TO VARIANCE REDUCTION APPROACH
A lot of recent work has been devoted to the study of variance reduction techniques in convex optimization, including (Johnson & Zhang, 2013; Shalev-Shwartz & Zhang, 2013b; Xiao & Zhang, 2014; Schmidt et al., 2017; Defazio et al., 2014; Mairal, 2015). The vanilla SVRG algorithm has the update
wn = wn−1 − η [ ∇fi(wn−1) +∇f(w̃)−∇fi(w̃) ] , (14)
where w̃ is a snapshot reference point updated every constant iteration. These methods are able to achieve linear convergence rates for smooth strongly-convex optimization problems, which significantly improve the sub-linear rate of vanilla SGD. Extension to multiple setting are investigated, including acceleration (Shalev-Shwartz & Zhang, 2013a; Lin et al., 2015; Allen-Zhu, 2017), streaming (Frostig et al., 2015; Lei & Jordan, 2016), synchronous distributed setting (Lee et al., 2015), data augmentation (Bietti & Mairal, 2017). Extension of variance reduction approaches to general non-convex problems has also been studied in (Allen-Zhu & Hazan, 2016; Reddi et al., 2016). Despite these theoretical progress, variance reduction technique does not appear to be helpful for training deep neural network (Defazio & Bottou, 2018).
Our proposed method could be viewed as a delayed variant of SVRG in the decentralized setting. The update (15) in our method mimic the update of vanilla SVRG (14), with the difference that the average gradient is obtained across machine base on local parameters. This variance reduction technique empirically stabilized the asynchronous gradients and handle the staleness, which is able to achieve state-of-the-art performance in modern deep learning setting. Moreover, we obtain close linear speed up with respect to the number of machine, which is the essential goal of distributed optimization.
A.2 THEORETICAL JUSTIFICATION
Our proof closely follows the analysis in (Yu et al., 2019). We consider the following non-convex optimization problem
min w f(w) =
1
J J∑ j=1 fj(w),
where J denotes the number of workers. Moreover, each fj = Eζj [Fj(w, ζj)]. In the empirical minimization setting, ζj corresponds to a mini-batch sampling strategy and fj could again be expressed as a finite sum fj = 1Kj ∑ fkj . Throughout this paper, we assume the optimization satisfies the following assumptions. Assumption 1 (L-smooth). Each function fj(x) is L-smooth, i.e. for all x, y ∈ Rd and i ∈ [1, J ],
||∇fj(x)−∇fj(y)|| ≤ L||x− y||.
Assumption 2 (Bounded gradients and variances). There exists a positive constant G and σ such that
Eζj ||∇Fj(w; ζi)||2 ≤ G2,∀w,∀j Eζj ||∇Fj(w; ζj)−∇fj(w)||2 ≤ σ2,∀w,∀j
We prove that our algorithms have the convergence rate
O( 1√ JN ) +O( c2J N )
where J is the number of workers, N is iterations and c is staleness in our algorithm (t for delayed steps and d for temporal sparsity). With proper settings, our algorithms are as fast as original SSGD O(1/ √ JN). The detailed proof follows below.
Under review as a conference paper at ICLR 2020
A.2.1 PROOF OF THE CONVERGENCE OF DELAYED UPDATE ALGORITHM
Delayed Update Algorithm
1. Initialize w0 and initialize each worker with w0,j = w0 for j ∈ [1, J ].
2. For iteration n = 0, 1, · · ·
On each local worker j, sample a stochastic gradient∇w(n−1,j) and update: ◦ If n < t, update with standard SGD rule:
w(n,j) = w(n−1,j) − γ∇w(n−1,j) ◦ Else:
w(n,j) = w(n−1,j) − γ(∇w(n−1,j) +∇wn−t −∇w(n−t,j)) (15)
where
∇wn−t = 1
J J∑ j=1 ∇w(n−t,j)
3. Output∇w(n) = 1J ∑J j=1 w(n,j)
Notably, the delayed update formula can rewritten as
w(n,j) = w0 − γ n−t∑ i=0
∇wi︸ ︷︷ ︸ invariant of j
−γ n−1∑
i=n−t+1 ∇w(i,j), (Delayed)
where the first quantity is commonly shared among all the workers and the second term corresponds to local updates.
Lemma A.1. Let (w(i,j)) be the sequence generated on the j-th worker according to Delayed Update Algorithm, then for any j0 ∈ [1, J ]
E [ ‖∇w(n) − w(n,j0)‖ 2 ] ≤ 4γ2t2G2
Proof. From the delayed update formula Delayed, we have, E [ ‖∇w(n) − w(n,j0)‖ 2 ]
= γ2E  ∥∥∥∥∥∥ 1J J∑ j=1 n−1∑ i=n−t+1 ∇w(i,j) − n−1∑ i=n−t+1 ∇w(i,j0) ∥∥∥∥∥∥ 2 
≤ 2γ2E  ∥∥∥∥∥∥ 1J J∑ j=1 n−1∑ i=n−t+1 ∇w(i,j) ∥∥∥∥∥∥ 2 + E[‖ n−1∑ i=n−t+1 ∇w(i,j0)‖ 2 ]
≤ 2γ 2t
J J∑ j=1 n−1∑ i=n−t+1 E [∥∥∇w(i,j)∥∥2]+ 2γ2t n−1∑ i=n−t+1 E [ ‖∇w(i,j0)‖ 2 ]
≤ 4γ2t2G2.
Under review as a conference paper at ICLR 2020
Theorem A.2. Consider the sequence generated by the Delayed Algorithm, then
1
N N−1∑ n=0 E[‖∇f(∇w(n))‖2] ≤ 2 γN (f(w0)− f∗) + 4γ2t2G2L2 + L J γσ2.
Proof. By smoothness of f , we have
E[f(∇w(n))] ≤ E[f(∇w(n−1))+ 〈∇f(∇w(n−1)),∇w(n)−∇w(n−1)〉+ L
2 ‖∇w(n)−∇w(n−1)‖2]
Note that
∇w(n) = ∇w(n−1) − γ
J J∑ j=1 ∇w(n−1,j).
We have
E[‖∇w(n) −∇w(n−1)‖2]
= γ2E[‖ 1 J J∑ j=1 ∇w(n−1,j)‖2]
= γ2E[‖ 1 J J∑ j=1 (∇w(n−1,j) −∇fj(w(n−1,j))‖2] + γ2E[‖ 1 J J∑ j=1 ∇fj(w(n−1,j))‖2]
= γ2
J2 J∑ j=1 E[‖(∇w(n−1,j) −∇fj(w(n−1,j))‖2] + γ2E[‖ 1 J J∑ j=1 ∇fj(w(n−1,j))‖2]
≤ γ 2σ2 J + γ2E[‖ 1 J J∑ j=1 ∇fj(w(n−1,j))‖2].
Moreover,
E[〈∇f(∇w(n−1)),∇w(n) −∇w(n−1)]
= − γE[〈∇f(∇w(n−1)), 1
J J∑ j=1 ∇w(n−1,j)]
= − γE[〈∇f(∇w(n−1)), 1
J J∑ j=1 ∇fj(w(n−1,j)]
= − γ 2 E[‖∇f(∇w(n−1))‖2] + γ 2 E[‖∇f(∇w(n−1))− 1 J J∑ j=1 ∇fj(w(n−1,j)‖2]− γ 2 E[‖ 1 J J∑ j=1 ∇fj(w(n−1,j))‖2]
Applying the lemma, we have
E[‖∇f(∇w(n−1))− 1
J J∑ j=1 ∇fj(w(n−1,j)‖2]
=E[‖ 1 J J∑ j=1 (∇fj(∇w(n−1))−∇fj(w(n−1,j))‖2]
≤ 1 J J∑ j=1 E[‖(∇fj(∇w(n−1))−∇fj(w(n−1,j))‖2]
≤ L 2
J J∑ j=1 ‖∇w(n−1) − w(n−1,j)‖2
≤ 4γ2L2t2G2.
Under review as a conference paper at ICLR 2020
Thus, combining the above inequalities together with γ ≤ 1L yields
E[f(∇w(n))]− E[f(∇w(n−1))]
≤ γL 2 − γ 2 E[‖ 1 J J∑ j=1 ∇fj(w(n−1,j))‖2]− γ 2 E[‖∇f(∇w(n−1))‖2] + 2γ3L2t2G2 + L 2J γ2σ2
≤ − γ 2 E[‖∇f(∇w(n−1))‖2] + 2γ3L2t2G2 + L 2J γ2σ2.
Rearrange the terms yields
E[‖∇f(∇w(n−1))‖2] ≤ 2
γ (E[f(∇w(n−1))]− E[f(∇w(n))]) + 4γ2L2t2G2 +
L J γσ2
Telescoping from n = 1, ..N yields
1
N N∑ n=1 E[‖∇f(∇w(n−1))‖2] ≤ 2 γ (E[f(∇w(0))]− E[f(∇w(n))]) + 4γ2L2t2G2 + L J γσ2
Corollary A.2.1. When the number of iteration N surpass the number of machines J , let the stepsize γ = √ J
L √ N , yields
1
N N−1∑ n=0 E[‖∇f(∇w(n))‖2] ≤ 2L√ JN (f(w0)− f∗ + σ2) + 4t2G2J N .
= O( 1√ JN ) +O( t2J N )
When delayed steps is in a reasonable range (t < O(N 1 4 J− 3 4 )), the first term dominates and delayed update demonstrates the same convergence speed as original SSGD O(1/ √ JN).
A.2.2 PROOF OF THE CONVERGENCE OF TEMPORALLY SPARSE UPDATE ALGORITHM
Temporally Sparse Update Algorithm
1. Initialize w0 and initialize each worker with w0,j = w0 for j ∈ [1, J ].
2. For iteration n = 0, 1, · · ·
On each local worker j, sample a stochastic gradient∇w(n−1,j) and update: ◦ If n (mod d) 6= 0, update with standard (local) SGD rule:
w(n,j) = w(n−1,j) − γ∇w(n−1,j) ◦ Else:
w(n,j) = w(n−1,j)−γ[∇w(n−1,j)+ n−1∑
k=n−d
(∇wn−d+k−∇w(n−d+k,j))] (16)
where
∇wn−d+k = 1
J J∑ j=1 ∇w(n−d+k,j)
3. Output∇w(n) = 1J ∑J j=1 w(n,j)
Under review as a conference paper at ICLR 2020
Notably, the temporally sparse update formula can rewritten as
w(n,j) = w0 − γ dbnd c∑ i=0
∇wi︸ ︷︷ ︸ invariant of j
−γ n−1∑
i=dbnd c+1
∇w(i,j), (TS)
where the first quantity is commonly shared among all the workers and the second term corresponds to local updates. Lemma A.3. Let (w(i,j)) be the sequence generated on the j-th worker according to Temporally Sparse Update Algorithm, then for any j0 ∈ [1, J ]
E [ ‖∇w(n) − w(n,j0)‖ 2 ] ≤ 4γ2d2G2
Proof. From the update of (TS), we have E [ ‖∇w(n) − w(n,j0)‖ 2 ]
= γ2E  ∥∥∥∥∥∥ 1J J∑ j=1 n−1∑ i=dbnd c+1 ∇w(i,j) − n−1∑ i=dbnd c+1 ∇w(i,j0) ∥∥∥∥∥∥ 2 
≤ 2γ2E  ∥∥∥∥∥∥ 1J J∑ j=1 n−1∑ i=dbnd c+1 ∇w(i,j) ∥∥∥∥∥∥ 2 + E ‖ n−1∑ i=dbnd c+1 ∇w(i,j0)‖ 2  ≤ 2γ 2d
J J∑ j=1 n−1∑ i=dbnd c+1 E [∥∥∇w(i,j)∥∥2]+ 2γ2d n−1∑ i=dbnd c+1 E [ ‖∇w(i,j0)‖ 2 ]
≤ 4γ2d2G2.
Theorem A.4. Consider the sequence generated by the Temporally Sparse Update Algorithm, then
1
N N−1∑ n=0 E[‖∇f(∇w(n))‖2] ≤ 2 γN (f(w0)− f∗) + 4γ2d2G2L2 + L J γσ2.
Proof. Based on Lemma A.3, the proof follows the exact same schema as the Delayed Update Algorithm, which we omit here.
Corollary A.4.1. When the number of iteration N surpass the number of machines J , let the stepsize γ = √ J
L √ N , yields
1
N N−1∑ n=0 E[‖∇f(∇w(n))‖2] ≤ 2L√ JN (f(w0)− f∗ + σ2) + 4d2G2J N .
= O( 1√ JN ) +O( d2J N )
When temporal sparsity is in a reasonable range (d < O(N 1 4 J− 3 4 )), the first term dominates and temporally sparse update demonstrates the same convergence speed as original SSGD O(1/ √ JN).

Review summaries:
The paper presents an approach - Delayed and Temporally Sparse Update (DTS) - to do distributed training on nodes that are very distant from each other in terms of latency. The approach relies on delayed updates to tolerate latencies and temporally sparse updates to reduce traffic. The approach is implemented in a synchronous stochastic gradient decent (SGD) scheme.