Distributed Training Across the World
Authors: Ligeng Zhu
Yao Lu
Yujun Lin
Song Han
Venue:  (2020)
Keywords: Distributed Training
Bandwidth

Abstract: Traditional synchronous distributed training is performed inside a cluster, since it requires high bandwidth and low latency network (e.g. 25Gb Ethernet or Infini-band). 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 un-der 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 achieves90×speedup over traditional methods without loss of accuracy on ImageNet.

Under review as a conference paper at ICLR 2020
DISTRIBUTED TRAINING ACROSS THE WORLD
Anonymous authors Paper under double-blind review
ABSTRACT
Traditional synchronous distributed training is performed inside cluster since it requires high bandwidth and low latency network (e.g. 25Gb Ethernet or Infini- band). 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 un- der 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 (Furope), Tokyo (Asia), Oregon (North America) and Ohio (North America). Under such challeng- ing settings, DTS achieves 90 speedup over traditional methods without loss of accuracy on ImageNet.
INTRODUCTION
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 reasonable time, distributed training is an important technique and gains increasing attention (Li et al., 2014; Dean et al., 2012; Recht al., 2011; Goyal al., 2017; Jia et al., 2018). To maintain good scalability, a low latency and high bandwidth network is essential for most modern distributed systems. Existing frameworks (Chen al., 2015; Xing et al., 2015; Moritz 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 us.
weeks to converge. In order enable training in
Bandwidth is easy to increase (e.g. stacking hardware) but latency is hard to improve (physical limits). For example, we have two servers located at Shanghai and Boston respectively, even at the speed of light and direct air dis- tance, it still takes 78ms" to send and receive a packet. 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 train- ing. As shown in Fig. 1, traditional distributed training algorithm scales poorly under such large latency.
SSGD O DTTS ASGD
BCD PSGD
FolAvg
0.90
0.68
Scalability
0.45
0.00
100 500
1000
Network Latency (ms)
In many scenarios, the training data involves privacy- sensitive information, such as personal medical his- tory (Jochems et al., 2016: 2017) and keyboard input his- tory (McMahan et al., 2016; Konen et al., 2016; Bonawitz al., 2019), thus cannot be centralized to a data center due to security and legacy concerns (GDPR, 2016). When datasets are distributed across many
Figure 1: DTS maintains a good scala- bility when network latency increases. while the performance of conventional algorithms degrades quickly.
111 725km x 2/(3 x 10"m/s) = 78. 16ms. Information collected from Google Maps.
IIf 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
Inside & cluster
Acroes the world
London
479,000us
Ohio
Oregon
210ms
Tokyo
2,274 sigla
168 159,506x longer
98X Worse
23 kmgm
102ms
Latency
Speed
Network conditions across different continents (Left) and the comparison between connec- tions inside cluster (Right). Different from training inside a data center, long-distance distributed training suffers from high latency, which proposes severe challenge to scale across the world.
Figure 2:
locations across public clouds, private clusters and even edge devices, is impossible to setup 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 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 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 ECD-PSGD (results copied directly from their original paper (Tang et al., 2018a)
We benchmark our DTS under challenging settings: training 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 DDTS 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 20x.
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.
2 RELATED WORK
Distributed Learning becomes ever more important as the sizes of both datasets and models increase. Many studies have been made explore the efficiency, both at the algorithm level (Li al., 2014; Dean et al., 2012; Recht et al., 2011; I; Goyal et al., 2017; Jia et al., 2018) and at the framework level (Chen et al., 2015; Akiba al., 2017: Abadi et al., 2015; Paszke al.. 2017; Sergeev Del Balso, 2018). In most of distributed algorithms, each node performs computation and exchange updates through network. key component to improve scalability is to reduce the communication-too computation 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. One- bit gradient gradient (Seide et al., 2014) achieves 10x 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 &
2

---

Under review as a conference paper at ICLR 2020
Heafield, 2017) and dynamic compression ratio (Chen 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 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 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 coun- tries (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 performed in each update, such as AD-PSGD (Lian et al., 2017) and D2 (Tang et al., 20180 20)8b). 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., 201 20, BUCKWILD! (De Sa et al., 2015) and dist-belief (Dean al., 2012). However, most of them are implemented through parameter server (Dean et al., 2012; Chilimbi al.. 2014; Li al., 2014) and leads 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.
3 APPROACH
To motivate this section, first review the mechanism of synchronous distributed training: 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 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:
y: learning rate.
"(i))) model weights at iteration on worker j.
t: iteration steps that the synchronization bar- rier is delayed.
"(a.y" error compensated weights at iteration i on worker j.
pt iteration steps between temporally sparse update intervals.
(w(a, local gradients at iteration worker j.
M(rg): momentum at iteration on worker j. " error compensated momentum at itera-
Vuray: global averaged gradients at iteration
tion worker j.
3.1 DELAYED UPDATE In modern implementations of vanilla SSGD, the transmission is partially pipelined with back- propogration: Synchronizing gradients th layer can be performed simultancously with back- propagating (n 1)th layer. However, it is not enough cover communication since latency on
3

---

Under review as a conference paper at ICLR 2020
C Computation
Synchroniration Barrier
Locally update
Send gradients to other
T1
T2
T3
T4
T1
T2
T3
T4
(a) Synchronous distributed learning.
T1
T2
T3
T4
Ti
T2
T3
T4
(b) Synchronous distributed learning with delayed update.
T1
T2
T3
T4
3
Ti
T2
T3
T4
(c) Synchronous distributed learning with temporally sparse update.
The visualization of our proposed techniques (Left) and the execution pipeline (Right). Yellow lines and blocks indicate communication, while green ones indicate computation. Delayed update covers communication by computation and requires the same number of synchronization. Temporally sparse reduces the synchronization frequency and improve the amortized latency.
Figure 3:
long-distance connection is usually larger 2 100ms) than propagating a layer 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.
(z I 1ms). To relax
To understand, we start with vanilla SGD: Consider a worker with index j. the weights at timestamp during distributed training are derived via
((n.)) w(n-1.) VW(nn11 w(0
(F(())
(1)
1=0
where (w(n-1) is the averaged gradients calculated by gathering all local gradients (w) In SSGD, the synchronization has to finish before (n 1) forwarding. In delayed update, we delay the barrier to (n + thth iteration and because of the delay, Vw(n-1) 1) is not received at timestamp We local gradients update instead.
((n)) = w(n-1.f) (W(
Meanwhile, stale gradients (u(n-)) arrive. At timestamp f, performed the gradient step using local gradients (w(n-t5). which should be the global averaged Vw(n--) in SSGD. We correct the mismatch caused by replacing Vwin-(.j) with (win-e)- From Eq. 1, it adds compensation term, which the difference of two gradients.
w/n,,) (1(n-15) Y [Winn-5) -7 Vw (..))
local gradicats
etror compensation
W(nn) 7 [winn-) - Vw(n-t,))
Next, consider momentum SGD. With momentum m, the weight timestamp is updated by
U(n.f) m1,))- + (w((s) W(ns) W(n-1.j) ((
(4)
4

---

Under review as a conference paper at ICLR 2020
We rewrite the cumulative form to general form
n
((n,))
((0,i)
7
U(iJ)
[(n
m V w
(n-ij)
im0
n- 1
i=0
(5)
= =m(o)))
m
Vi(k))
(6)
m
V (i.))
i=0
k=
1-1
==
(w())
(((o))
m
1=0
k=0
Then, we can derive the compensated momentum
w((.))) m1,)n-15)) + (.5)) + m' (VW(n-t) - (wi(n-
((n)) + m' (Vw(n-r)- V ((((n)s))
and weights similarly
w((n.)) w((n-15) (((n--1)))
Σ m (Wu(n-1) (W(n-)s))
k=U
(8)
[((n)) - 7 Σ m² (Vw(n-t)- (w(n-15))
In original synchronous stochastic gradient descent (SSGD), every worker receives averaged gradients from at timestamp n. This requires collective operation (e.g. Allreduce) to execute quickly; otherwise, it will slow down the training process. operation is moved from timestamp to + 1. It means as long as the gradients within t x Tompute. the training is not blocked. To put some real numbers, assume we are training ResNet-50 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 1. and show this is as fast as SSGD.
delayed update, the barrier of the collective
transmitted
3.2 TEMPORALLY SPARSE UPDATE
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 f transmissions at the same time. Without 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-dise dist-dieeece connections, the latency varies in 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, update from Eq. 1, which the difference between accumulated gradients. Note the compensation in temporally sparse update only applies when (mod) p) 0.
derive the compensation term for temporally sparse
n-1
w(n)) = w(nn) - 7(
Vi
i=n P
5

---

Under review as a conference paper at ICLR 2020
Bandwidth
Non-computing time
Synchronous SGD
w
Tiriining
T communicate T overlap
Delayed Update (t)
2 w
T Training
max (0. communicate
Toverlap
x T compute
Temporal Sparsity (p)
w (p
Trainnng)
(T communicate
T Tovertap) 3/p x 'T compute)]
Delayed Update (t)
(p
(rining))
maa((, (7 communicate
T overlap
Temporal Sparsity (p)
Table The networking requirements for different training strategies.
For SGD with momentum acceleration, based accumulated gradients is enough compensate both Vi0(n)) and W(n.f)- We need to transmit an extra term to correct the momentum:
k/m)) = -U(n)) +
m
(
m
==n-p P
w(nn)) -W(n,s) 7(
(u(
m Vu(an)
(10)
k=0
im k=0
n-1
(((o)) 7(
m
mink (i(()
Σ
m Vwi(k.))
1m nl km
im km
Let ((i)) Ex=n-p m VVw(k)) Note S(+12) .mS(..)) Vu(++1) and S(n-pt1,)
(w(n-p.5)- the formula can be written as:
k(ns)) U(n,)) (3(n) S((n))
n-1 Σ
n-1
(11)
w (mn)) = w(mn)) - 7(
S(n)
i=n-p P
(=
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 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 every N steps. It does not require any changes to the byper-parameters. We prove the convergence of temporally sparse update Appendix A.2.2 and demonstrate that enjoys the same convergence rate SSGD.
3.3 DELAYED AND TEMPORALLY SPARSE UPDATE
The delayed technique and temporally sparse update can be combined together. The compensation formulas for vanilla SGD is
n-t-
w ((n))) = W(nj) - 7(
Σ
Vw(
Σ
Vu(a.))
(12)
-nn-t-p
i=ー-t-
and for momentum SGD is
((n = U(n.j) + +m' m'nn (Sn-i-S(m-t.)) S(n-t.)))
n n-1-1
n-t-1
(13)
w (n.) ((..)) - ym'(
Σ amn-ttp
S
Σ
S(g)
Emn-t-p
Original ring allreduce transfers 2||w|| packets (Thakur 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
Original
Delay delay-16
delay- delay-20
delay-12
0.9
0.7-
0.6
0.7
1og-1 Aucuniyy
0.5
Scalability
0.4
0.5
orggiaal
0.3
4dlay4
12
0.2
de
0.1-
delay-20
20
60
60
100
120
10
50
100
500
1000
5000
Epecha
Network latency (ms)
(a) The learning curve with different delay steps and scalability under various latency.
Original
temporal surritym4
temponal sparsity
tempural Sparsity-12
tempural sparsity116
temporal spursity-20
0.8
0.7-
0.6-
Ttg-1 Acumayy
0.5
Scalability
0.4-
original
0.3
4pasityy
tempseal spansit
0.2
kompsaal-gomiit-112
lanpseal-ganniy-l
0.1
temp spanity 20
0.0
100
500
Epochs
Network latency (ms)
(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.
4 EXPERIMENT
4.1 EXPERIMENT SETTINGS
We evaluate our DTS 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 vali- dation 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 the initial learning rate 0.0125 for which grows linearly w.r.t number of GPUs. For a fair comparison, the training settings are the same among all experiments.
When performing ablation studies under different latency, we synthesis the network condition using netem'. When training across the world, the limited network is benchmarked using qperf'i We implement DST in Py Torch 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.
4.2 RESULTS OF DELAYED UPDATE
Fig. 4a shows the performance and scalability for delayed update with different latency. We start from delay steps 4 and gradually increase it. The learning curve shows that with our proposed error compensation delayed update demonstrates robust convergence and comparable performance compared vanilla SSGD, even when delay interval is as large as 20.
Inttps://wiki. www.://ooaaaatoooooooaaaaaaaotaa www.oo//nnwww.igggnee.e.....eeee hhttps://1imi die. net net/man/// hmtp///////////ffff/ee
7

---

Under review as a conference paper at ICLR 2020
D-4, T-4 (200ms) SSGD (0ms) ideal
D-20, T- (200m)) SSGD (200ms)
Top- %
16
Original SGD
76.63
D=4, T=4, C=1%
76.15
12
D-8, T=8, C=1 %
76.32
Speedup
D=12, T=8, C=1% %
76.18
D=20, T=12, C=1%
75.81
(a) Delayed updates preserves the accuracy while tolerate a large latency. D. T. C indicate delayed update, temporal sparsity and gradient compression ratio respectively. The results are evaluated on ImageNet dataset.
12
16
Number of servers
(h) Better speedup and scalability with DTS. Measured on servers across the world.
Table 2: DTS demonstrates good scalability and accuracy on world-wite high latency training.
In original SSGD and modern deep learning frameworks, though the transmission is partially pipelined with backpropogration: Synchronizing gradients of nh layer can be performed simultancously with back-propagating (n y layer, it is not enough to fully cover communication since latency on long distance connection is usually larger ( 2 100ms) than propagating a layer (1 (ms). 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.
4.3 RESULTS OF TEMPORALLY SPARSE UPDATE
The connection of real-world network has many bothering issues such unstable latency and conges- tion on routers. Temporally sparse is introduced to amortize these via reducing the synchronization frequency. The results are shown in Fig. 4b(Lefi): 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.
4.4 DISTRIBUTED TRAINING ACROSS THE WORLD
With two powerful techniques, we close to our original target of distributed training across world. To evaluate DTTS, 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. The real latency across the ring allreduce is about 479ms through Ethernet. On V100 GPU, ResNet-50 takes around 300ms forward and backward. Therefore delayed update with steps more than is already enough to tolerate such a network. In terms of latency variance and network congestion, we integrate temporally sparse update alleviate which drastically reduces the bandwidth requirement by / times. However, there is still a bottleneck on bandwidth for coossccnntneett connections (e.g. Tokyo to London). Though theoretically bandwidth achievable by switching to better internet service providers, AWS does not provide such option. As economical alternative, 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 lus latency).
adapt deep
5 CONCLUSION
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 wide range of decentralized learning applications.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg. Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaogiang Zheng. TensorFlow: Large-scale machine learning heterogeneous systems, 2015. URL http: //tensor//noooo flow. ow. www.wworrreo org/ Software available from tensorflow.org.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. arXiv preprint arXiv: 000.170044.0..21 2017.
Takuya Akiba, Keisuke Fukuda, and Shuji Suzuki. ChainerMN: Scalable Distributed Deep Learning Framework, In Proceedings of Workshop on ML Systems The Thirty-firsl Annual Conference on Neural Information Processing Systems (NIPS), 2017. URL http: http:////aaannnn/a/eeeeeee org/
http///ssets//pppppeee hwwppppsssppprrrraeeeeeee htlpppappp______ pd..ff.
Dan Alistarh, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Randomized quantization for communication-oppimaa stochastic gradient descent. arXiv preprini arXiv:1610.02/33 2016.
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.
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research, 18(1):819488244 2017.
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pp. 699-707, 2016.
Alberto Bietti and Julien Mairal. Stochastic optimization with variance reduction for infinite datasets with finite sum structure. In Advances in Neural Information Processing Systems, pp. 1623-1633, 2017.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H Brendan McMahan, al. Towards federated learning at scale: System design. arXiv preprint arXiv: 1etp:::9902.00444 2019.
Chia- Yu Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, and Kailash Gopalakrish- nan. Adacomp: Adaptive residual gradient compression for data-parallel distributed training. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Tianqi Chen, Mu Li, Yutian Li, Min Lin, Naiyan Wang, Minjie Wang, Tianjun Xiao, Bing Xu, Chiyuan Zhang, and Zheng Zhang. Mxnet: A flexible and efficient machine learning library for heterogeneous distributed systems. arXiv preprint arXiv: 2015.
Trishul M Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam: Building an efficient and scalable deep learning training system. In OSDI, volume 14, pp. 571-582, 2014.
Christopher M De Sa. Ce Zhang, Kunle Olukotun, and Christopher Ré. Taming the wild: unified analysis of hogwild-style algorithms. In Advances in neural information processing systems, pp. 2674-2682, 2015.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior, Paul Tucker, Ke Yang, Quoc V Le, et al. Large scale distributed deep networks. In Advances in neural information processing systems, pp. 1223-1231, 2012.
Aaron Defazio and Léon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. arXiv preprint 18/2 2018.

---

Under review as a conference paper at ICLR 2020
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in neural information processing systems, pp. 1646-1654, 2014.
Deng. W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Seagle Hierarchical Image Database. In CVPRO9, 2009.
Roy Frostig, Rong Ge, Sham Kakade, and Aaron Sidford. Competing with the empirical risk minimizer in single pass. In Conference on learning theory, pp. pp. 728-763, 2015.
GDPR. The eu general data protection regulation (gdpr). 2016.
Google. Towards federated learning at scale: System design. 2017. URL https: //i. googleblog wtm.l/ooccocooooooooooooooo//e/e 2017 /4
col.rmioaitclllllatttiiiiiii html.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: 026777 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, In Proceedings of the IEEE conference computer vision and pallern recognition, pp. 770-778, 2016.
Xianyan Jia, Shutao Song. Wei He, Yangzihao Wang, Haidong Rong, Feihu Zhou, Liqiang Xie, Zhenyu Guo, Yuanzhou Yang, Liwei Yu, al. Highly scalable deep learning training system with mixed-precision: Training imagenet in four minutes. arXiv preprinl urXiv:/800) 1205, 2018.
Peng Jiang and Gagan Agrawal. linear speedup analysis of distributed deep learning with sparse and quantized communication. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Ceesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 2525-2536. Curran Associates, Inc., 2018. URL http: ptpppaapppssssss/ nips cc cc/ wc/paper/////eeecceeeeeeeeeeeepe 7519-a- 1al19--a-nnneaaa speedup- analysis- of diw-diiisttiuddddd seeerribuuddddedepepeeeee -aae- wtth-sparre-anddquaat pdf.
Arthur Jochems, Timo M Deist, Johan Van Soest, Michael Eble, Paul Bulens, Philippe Coucke, Wim Dries, Philippe Lambin, and Andre Dekker. Distributed learning: developing predictive model based on data from multiple hospitals without data leaving the hospital-a real life proof of concept. Radiotherapy and Oncology, 121(3):459 467, 2016.
Arthur Jochems, Timo Deist, Issam El Naqa, Mare Kessler, Chuck Mayo, Jackson Reeves, Shruti Jolly, Martha Matuszak, Randall Ten Haken, Johan van Soest, et al. Developing and validating a survival prediction model for nscle patients through distributed learning across 3 countries. International Journal of Radiation Oncology* Biology Physics, 99(2)3444-35, 2017.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315 2013.
Jakub Konen, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. In NIPS Workshop on Private Multi-Party Machine Learning, 2016. URL
http///axxvvv/////////// wwwxiiiorg///. abs/
1610. 05492.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Jason D Lee, Qihang Lin, Tengyu Ma, and Tianbao Yang. Distributed stochastic variance reduced gra- dient methods and a lower bound for communication complexity. arXiv preprint arXivv1507.07595 2015.
Lihua Lei and Michael Jordan. Less than a single pass: Stochastically controlled stochastic gradient method. arXiv preprint arXiv: 012.66699036226 2016.
10

---

Under review as a conference paper at ICLR 2020
Mu Li, David G Andersen, Jun Woo Park, Alexander J Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. In 11th {USENIX] Symposium Operating Systems Design and Implementation ({OSDI) 14), pp. 583-598, 2014.
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.
Xiangru Lian, Wei Zhang, Ce Zhang, and Liu. Asynchronous decentralized parallel stochastic gradient descent. arXiv preprint 1txiv:1710.06952 2017.
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimization. In Advances in neural information processing systems, pp. 3384-3392, 2015.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv preprint arXiv: 2017.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608. 1XXx::6608.0383,, 2016.
Julien Mairal. Incremental anjorization-miniiizzatooo optimization with application to large-scale machine learning. SIAM Journal on Optimization, 25(2): 855, 2015.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication-efficiiie learning of deep networks from decentralized data. arXiv preprint 1rxiv:6602.05622) 2016.
Philipp Moritz, Robert Nishihara, Ion Stoica, and Michael Jordan. Sparknet: Training deep networks in spark. arXiv preprint arXiv:1511.0600 2015.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS-W W, 2017.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in neural information processing systems, pp. 693-701, 2011.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference machine learning, pp. 314-323, 2016.
Felix Sattler, Simon Wiedemann, Klaus-Robers Müller, and Wojeiech Samek. Sparse binary com- pression: Towards distributed deep learning with minimal communication. CoRR, abs/1805.0m 180.00888. 2018. URL
ooro abss / 1805.04 08768.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):83-112, 2017.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Alexander Sergeev and Mike Del Balso. Horovod: fast and easy distributed deep learning in tensorflow. arXiv preprini arXiv: I 8802005799 2018.
Shai Shalev-Shwartz and Tong Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. arXiv preprint arXiv: 1009 2013a.
Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(Feb):567-599, 2013b.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.

---

Under review as a conference paper at ICLR 2020
Nikko Strom. Scalable distributed dnn training using commodity gpu cloud computing. In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
Peng Sun, Wansen Feng, Ruobing Han, Shengen Yan, and Yonggang Wen. Optimizing network performance for distributed dnn training on gpu clusters: Imagenet/alexnet training in 1.5 minutes. arXiv preprint 1rXiv:1902.06855, 2019.
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training. Advances Neural Information Processing Systems, pp. 7652-7662, 2018a.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D2: Decentralized training decentralized data. CoRR, abs/1803.07066 2018b. URL /ttp://wwww.wo./////a/aaaoaaaaaa 07068.
Hanlin Tang, Xiangru Lian, Tong Zhang, and Ji Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pass cror-compensated compression. In International Conference on Machine Learning, 2019.
Rajeev Thakur, Rolf Rabenseifner, and William Gropp. Optimization of collective communication operations in mpich. The International Journal of High Performance Computing Applications, 19 (1):49-66, 2005.
John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions automatic control, (1)) 803-812, 1986.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Tergradd Ternary gradients to reduce communication in distributed deep learning. In Advances in neural information processing systems, pp. 1509-1519, 2017.
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction.
SIAM Journal on Optimization, 24(4):2057-2072 2014.
Eric P Xing, Qirong Ho, Wei Dai, Jin Kyu Kim, Jinliang Wei, Seunghak Lee, Xun Zheng, Pengtao Xie, Abhimanu Kumar, and Yaoliang Yu. Petuum: A new platform for distributed machine learning on big data. IEEE Transactions on Big Data, 1(2):49 07,499-6-4466 2015.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
12

---

Under review as a conference paper at ICLR 2020
A APPENDIX
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-1 7 V (((,,-1) Vf( - -
(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 signif- icantly 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), stream- ing (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 (Alenn-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-ar 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 al., 2019). We consider the following non-convex optimization problem
J min f(w) = ] Σ f(w).
where denotes the number of workers. Moreover. each f, IF, 4)]. In the empirical minimization setting, S corresponds to a mini-batch sampling strategy and fy could again be expressed as a finite sum /, = n Σ Sky. Throughout this paper, we assume the optimization satisfies the following assumptions.
Assumption 1 (L-smooth). Each function fz( is L-moooth, i.c. for all x, E Rd and i E [],
(z) - [z S L| yll-
Assumption 2 (Bounded gradients and variances). There exists positive constant G and such that
Eg, [VE](( < Vw, Vj FV -) (f,()] 0², Vw,
We prove that our algorithms have the convergence rate
O 2J N
O JJN
where J is the number of workers, is iterations and e is staleness in our algorithm (t for delayed steps and d for temporal sparsity). With proper settings, our algorithms fast original SSGD O(I/VJN). The detailed proof follows below.
13

---

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 we and initialize each worker with wo,j wp for j E [1.
2. For iteration 0, 1,
On each local worker j. sample stochastic gradient (w( and update: If n update with standard SGD rule:
((n.)) w((n-1j) (nn1)
o Else:
"(n)) = w(n-11j) - 7( (VWW(n-1.) + VWn-t Ve(n-15)) (15)
where
V Vün-t
(i(n-
j=1
3. Output Vw(n) E w(n.)
Notably, the delayed update formula can rewritten as
(n.j) we
W
Vw((i))
(Delayed)
invariant of
where the first quantity is commonly shared among all the workers and the second term corresponds to local updates.
Let (W(s)) be the sequence generated on the j-th worker according to Delayed Update Algorithm, then for any jo E []
Lemma A.1.
[ - "m 13 S 222222
Proof. From the delayed update formula Delayed, we have,
[1] Vwl
[1
=>²B
Vw(s
Σ
Vwi
j=ml
11
imn-2+1
+E Σ
Vwl 2
imn-t+1
272t
n Σ
E (w 12] +272
( [1
j=
6222
14

---

Under review as a conference paper at ICLR 2020
Theorem A.2. Consider the sequence generated by the Delayed Algorithm. then
N-1
Σ
7N - --, fio²
2 -
Proof. By smoothness of /, we have
Vwin- 1)) + L [W(n))
([((V S R[S(( + (V)(V (
Vw(n)
2
Note that
J
Vi(n) [1 ]
Ww(n-15)
We have
E3 V (w))) - (w(nn1)ll [|
- 1
j
(mmm- 1,5) 12]
= , Σ
(V00 - (//(m(--1)))1 + 2
7 j=1
j=1
72 J
++ 1 Σ
Σ
(Vl((V(()11)))
V (1((,,)11))
1=1
220² +
V (1(
Moreover,
PKVS(Vu(nn)) Vw(n)
(1((n-1)
-V 11))
V (i((--111l
j=1
J
[ (n j
V (f(
j=1
J
2 - 197
Ví (w
-
- } Σ
V Vsz (w (1(n))))))
2
2
1=1
1=1
Applying the lemma, we have
1
(1
=Elll
j (WW(n-1)
V fz (1(
Ell(
[[] [f
12
< J
VW(n-1) - w1n-15)11
-
< 1222
15

---

Under review as a conference paper at ICLR 2020
Thus, combining the above inequalities together with 7 1. yields
Elf (V
B (u(n--))
2 -7 Bill V (2 -
L 2. 200
L
2J 7202.
Rearrange the terms yields
[ - +4 + f702
Telescoping from I,..N yields
N
(E(S(Vm)))) - ([(((W))))) + + + L 1/102
0 VV
N
Corollary A.2.1. When the number of iteration N surpass the number of machines J, let the stepsize
y
LVN" yields
v
2L
4PGJJ
VJN (f(wo) - -f" +
N
1
RJ N
0 VJN
O0
When delayed steps is in reasonable range (1 O(N+J- the first term dominates and delayed update demonstrates the same convergence speed as original SSGD O(I/VIN).
A.2.2 PROOF OF THE CONVERGENCE OF TEMPORALLY SPARSE UPDATE ALGORITHM
Temporally Sparse Update Algorithm
Initialize we and initialize each worker with wo,j wp for E []
2. For iteration n = 0, 1,
On each local worker j, sample a stochastic gradient Vw( 1.) and update:
If (mod d) * O. update with standard (local) SGD rule:
W(n.)) W(n-1.f) VW
o Else:
W(n.)) w(n-1o)) -? - (n)(n +
Vwn Wwnd+kk (w(n-ath.)) (16)
k=n-d
where
V Twp d+k j
W(in-dtkJ)
3. Output Vw(n) = = 3/E/=1 w(n))
16

---

Under review as a conference paper at ICLR 2020
Notably, the temporally sparse update formula can rewritten
di 1
(i(i.))
(TS)
F=U
1
invariant of
where the first quantity is commonly shared among all the workers and the second term corresponds local updates.
Lemma A.3. Lef (wr(s)) be the sequence generated the j-th worker according Temporally Sparse Update Algorithm, then for any jo E []]
Vw W 11 S dr
Proof. From the update of (TS), we have
E
[1]
V [in)
do)
[|]]
=y²B
Vw((s)
V ((doo)
j=1
j=d
+1
==d 2
27
2
(
+
i= +1
in +1
dd²
[2]
+2y2d
Σ
E V (1)))))
J
+=
1+
S42
Theorem A.4. Consider the sequence generated by the Temporally Sparse Update Algorithm, then
N-1
VIIVI(VW)))111 Σ 1=0
&N - (")
J10²
N
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
VJ LVN' yields
7
2T.
JPC
(W(())
(f(wo)
-
VJN
N
d2j N
0
+ 0
VJN
When temporal sparsity is in reasonable range (d < O(N ))), the first term dominates and temporally sparse update demonstrates the same convergence speed as original SSGD O(I//JN).
17


Reviews:
[{"review_id": "rJlp29pRtS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe paper's approach with delayed updates, i.e., delaying gradient updates to other nodes, sends the updates in a later iteration. In this way, very long latencies can be hidden (covered by computation) since the gradient updates can be postponed to an arbitrary iteration (barrier synchronization) in the future. \n\nUnfortunately, delaying the updates opens up for the same problems as asynchronous SGD (ASGD), i.e., slower (none) convergence or staleness problems. These problems are coped with using a compensation factor, that adjusts the momentum and weights accordingly. \n\nA critical aspect of ASGD is to provide convergence guarantees, and DTS is similar in that aspect. However, the paper does not provide any convergence analysis or convergence guarantees. \n\nUsing only one dataset / network to evaluate the approach is too little. In order to show the generality, more benchmarks need to be evaluated.\n\nIn general, I like the paper. It is well written and easy to read. However, the novelty and contribution is relatively low. A lot of work has been done in the HPC and distributed systems communities over decades on how to tolerate latencies, trade-offs between communication and computation, proper synchronization points, etc. The ideas presented in this paper are well-known and extensively applied in those communities. None of that work is referensed or acknowledged in this paper. \n\nThe term \"scalability\" is used as an evaluation metric, but never clearly defined in the paper.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyeMuX_J9H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper tackles the issue of scalability in distributed SGD over a high-latency network.\nAlong with experiments, this paper contributes two ideas: delayed updates and temporally sparse updates.\n\n- strengths: \n\n· Clear-looking overall presentation.\n  Good efforts to explain the network problems (latency, congestion) and how they are tackled by delayed updates and temporally sparse updates.\n\n- weaknesses:\n\n· While the overall presentation looks clean, the paper does not talk about the setting (one parameter server and many workers, only workers, etc).\n  This is arguably basic information, and the readers is left to understand by themselves that the setting consists in many workers without a parameter server.\n\n· There is no theoretical analysis of the soundness of the proposed algorithm.\n  For instance in ASGD (that the authors cite), stale gradients are dampened before being used, which in turn is used to guarantee convergence.\n  In the proposed algorithm, there is no dampening nor apparent limit of the maximum value of t; such a difference with prior art should entail a serious (theoretical) analysis.\n\n· Finally, using SSGD for comparison is not very \"fair\", as communication-efficient algorithms have already been published for quite some time [1, 2, and follow-ups (e.g. searching for \"local sgd\")].\n  At the very least a comparison with ASGD (cited) is necessary, as in a realistic setting latency is indeed a problem but arguably not bandwidth\n  (plus, orthogonal gradient compression techniques do exist, e.g. as in \"Federated Learning: Strategies for Improving Communication Efficiency\").\n\nquestions to the authors: \n\n- Can you clarify the setting?\n\n- Can you give at least an intuition why accepting stale gradient is correct (i.e. does not impede convergence)?\n  There is no theoretical limit on the value of t; can workers take any arbitrary old gradient?\n  So when the training is close to convergence (if it reaches it), i.e., when the norm of the gradients are close to 0,  the algorithm could then use very old gradients (which norms could be orders of magnitude larger) to \"correct the mismatch\" caused by the local training; is this correct?\n  To solve that issue, ASGD introduces a simple dampening mechanism (which is necessary in the convergence proof), which your algorithm does not have.\n\n\nThe related work section focuses on gradient compression techniques (which tackle low bandwidth, not latency) and asynchronous SGD (which is more prone to congestion, with a single parameter server),\nbut seems to overlook that sparse communication techniques already exist (this fact should at least be mentioned).\n\nThe idea of sparse communication for SGD exists since at least 2012 [1, Algorithm 3].\nA first mention of the use of such techniques for \"communication efficiency\" dates from (at least) 2015 [2].\n\n[1] Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao.\n    Optimal distributed online prediction using mini-batches.\n    J. Mach. Learn. Res., 13(1):165–202, January 2012.\n\n[2] Sixin Zhang, Anna E. Choromanska, Yann LeCun.\n    Deep learning with Elastic Averaging SGD.\n    NeurIPS, 2015.\n\n\nI do not see a clear novelty, nor a proof (or even intuitions) that the proposed algorithm is theoretically sound.\nThe comparison with SSGD is arguably unfair, since SSGD is arguably not at all the state-of-the-art in the proposed setting (hence the claimed speedup of x90 can be very misleading).", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJeMe67H5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors provide a technique to compensate for error introduced by stale or infrequent synchronization updates in distributed deep learning.\n\nTheir solution is to use local gradient information to update the model, and once delayed gradient information from other workers arrives, the use it to provide a correction which would give an equivalent result to \"no delay\" synchronization in the case of linear model training.\n\nThe three approaches are:\n1. Delayed update -- use local gradients for immediate update, apply correction when stale averaged update arrives. \n2. Sparse update -- only update once every p iterations, the averaged update includes p steps\n3. Combined -- 1. and 2. combined\n\nAuthors evaluate on ImageNet, showing some improvement, and promise to release their implementation for PyTorch/Horovod. Their technique, combined with a reference implementation in a popular framework stands a good chance of having impact. Given the increase in cloud training workloads, even a small improvement in this setting is significant.\n\nComments:\n- \"scalability\" is never defined. I would recommend defining it, or referencing a paper which defines it. I assume it refers to training throughput divided by ideal training throughput.\n- Evaluation is one on resnet-50. Because it's mostly convolutions, such network has high compute/network ratio and is not frequently bottlenecked by network. A more convincing experiment would rely on lower computation intensity architecture such as Transformer/BERT training.\n- Section 1 states that without their technique, they expect SGD to exhibit 0.008 scalability for 100 servers, compared to 0.72 for their method. However, the number 0.72 was not supported by data, their largest experiment used 16 servers.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a distributed algorithm for training deep nets in clusters with high-latency (i.e. very remote) nodes. While the motivation and clarity are the strengths of the paper, the reviewers have some concerns regarding novelty and insufficient theoretical analysis. 
Decision: Reject