Title: DISTRIBUTED TRAINING ACROSS THE WORLD

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. * 11, 725km × 2/(3 × 10 8 m/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 .

1. 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 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. 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 involves privacysensitive information, such as personal medical history (Jochems et al., 2016; 2017) and keyboard input history (McMahan et al., 2016; 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

Under review as a conference paper at ICLR 2020 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. 

2. RELATED WORK:

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 & 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 Tang et al., 2018b) . None of them has been evaluated on large learning tasks yet.

D 2 (

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.

3. APPROACH:

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 barrier 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 iteration 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.

3.1. DELAYED UPDATE:

In modern implementations of vanilla SSGD, the transmission is partially pipelined with backpropogration: Synchronizing gradients of n th layer can be performed simultaneously with backpropagating (n -1) th layer. However, it is not enough to cover communication since latency on 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

EQUATION

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.

EQUATION

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.

EQUATION

Next, we consider momentum SGD. With momentum m, the weight at timestamp n is updated by

EQUATION

Under review as a conference paper at ICLR 2020

We rewrite the cumulative form to general form

u (n,j) = n i=0 m i ∇w (n-i,j) = n i=0

m n-i ∇w (i,j)

(5)

EQUATION

Then, we can derive the compensated momentum

EQUATION

and weights similarly

EQUATION

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 × T compute , 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.

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 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.

EQUATION

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 m n-i ∇w (i) - n-1 i=n-p m n-i ∇w (i,j) ) w (n,j) = w (n,j) -γ( n-1 i=n-p n-1-i k=0 m k ∇w (i) - n-1 i=n-p n-1-i k=0 m k ∇w (i,j) ) = w (n,j) -γ( n-1 i=n-p i k=n-p m i-k ∇w (k) - n-1 i=n-p i k=n-p m i-k ∇w (k,j) ) (10) Let S (i,j) = i k=n-p m 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:

EQUATION

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.

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

EQUATION

and for momentum SGD is

EQUATION

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 

4. EXPERIMENT 4.1 EXPERIMENT SETTINGS:

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, the limited network is benchmarked 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.

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.

Under review as a conference paper at ICLR 2020 Table 2 : DTS demonstrates good scalability and accuracy on world-wide high latency training.

In original SSGD and modern deep learning frameworks, though the transmission is partially pipelined with backpropogration: Synchronizing gradients of n th 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.

4.3. RESULTS OF TEMPORALLY SPARSE UPDATE:

The connection of real-world network has many bothering issues such as unstable latency and congestion on routers. Temporally sparse is introduced to amortize these 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.

4.4. DISTRIBUTED TRAINING ACROSS THE WORLD:

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) 

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 wide range of decentralized applications.

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

EQUATION

)

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 f j (w),

where J denotes the number of workers. Moreover, each

f j = E ζj [F j (w, ζ j )].

In the empirical minimization setting, ζ j corresponds to a mini-batch sampling strategy and f j could again be expressed as a finite sum f j = 1 Kj f kj . Throughout this paper, we assume the optimization satisfies the following assumptions. Assumption 1 (L-smooth). Each function f j (x) is L-smooth, i.e. for all x, y ∈ R d and i ∈ [1, J],

||∇f j (x) -∇f j (y)|| ≤ L||x -y||.

Assumption 2 (Bounded gradients and variances). There exists a positive constant G and σ such that

E ζj ||∇F j (w; ζ i )|| 2 ≤ G 2 , ∀w, ∀j E ζj ||∇F j (w; ζ j ) -∇f j (w)|| 2 ≤ σ 2 , ∀w, ∀j

We prove that our algorithms have the convergence rate

O( 1 √ JN ) + O( c 2 J 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 

w (n,j) = w (n-1,j) -γ∇w (n-1,j)

• Else:

EQUATION

where

∇w n-t = 1 J J j=1 ∇w (n-t,j) 3. Output ∇w (n) = 1 J J j=1 w (n,j)

Notably, the delayed update formula can rewritten as

EQUATION

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 j

0 ∈ [1, J] E ∇w (n) -w (n,j0) 2 ≤ 4γ 2 t 2 G 2

Proof. From the delayed update formula Delayed, we have,

E ∇w (n) -w (n,j0) 2 = γ 2 E    1 J J j=1 n-1 i=n-t+1 ∇w (i,j) - n-1 i=n-t+1 ∇w (i,j0) 2    ≤ 2γ 2 E    1 J 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γ 2 t J J j=1 n-1 i=n-t+1 E ∇w (i,j) 2 + 2γ 2 t n-1 i=n-t+1 E ∇w (i,j0) 2 ≤ 4γ 2 t 2 G 2 .

Under review as a conference paper at ICLR 2020 Theorem A.2. Consider the sequence generated by the Delayed Algorithm, then

1 N -1 n=0 E[ ∇f (∇w (n) ) 2 ] ≤ 2 γN (f (w 0 ) -f * ) + 4γ 2 t 2 G 2 L 2 + 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 ] = γ 2 E[ 1 J J j=1 ∇w (n-1,j) 2 ] = γ 2 E[ 1 J J j=1 (∇w (n-1,j) -∇f j (w (n-1,j) ) 2 ] + γ 2 E[ 1 J J j=1 ∇f j (w (n-1,j) ) 2 ] = γ 2 J 2 J j=1 E[ (∇w (n-1,j) -∇f j (w (n-1,j) ) 2 ] + γ 2 E[ 1 J J j=1 ∇f j (w (n-1,j) ) 2 ] ≤ γ 2 σ 2 J + γ 2 E[ 1 J J j=1 ∇f j (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 ∇f j (w (n-1,j) ] = - γ 2 E[ ∇f (∇w (n-1) ) 2 ] + γ 2 E[ ∇f (∇w (n-1) ) - 1 J J j=1 ∇f j (w (n-1,j) 2 ] - γ 2 E[ 1 J J j=1 ∇f j (w (n-1,j) ) 2 ]

Applying the lemma, we have

E[ ∇f (∇w (n-1) ) - 1 J J j=1 ∇f j (w (n-1,j) 2 ] = E[ 1 J J j=1

(∇f j (∇w (n-1) ) -∇f j (w (n-1,j)

) 2 ] ≤ 1 J J j=1

E[ (∇f j (∇w (n-1) ) -∇f j (w (n-1,j)

) 2 ] ≤ L 2 J J j=1 ∇w (n-1) -w (n-1,j) 2 ≤ 4γ 2 L 2 t 2 G 2 .

Under review as a conference paper at ICLR 2020 Thus, combining the above inequalities together with γ ≤ 1 L yields

E[f (∇w (n) )] -(∇w (n-1) )] ≤ γL 2 -γ 2 E[ 1 J J j=1 ∇f j (w (n-1,j) ) 2 ] - γ 2 E[ ∇f (∇w (n-1) ) 2 ] + 2γ 3 L 2 t 2 G 2 + L 2J γ 2 σ 2 ≤ - γ 2 E[ ∇f (∇w (n-1) ) 2 ] + 2γ 3 L 2 t 2 G 2 + 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γ 2 L 2 t 2 G 2 + 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γ 2 L 2 t 2 G 2 + 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 (w 0 ) -f * + σ 2 ) + 4t 2 G 2 J N . = O( 1 √ JN ) + O( t 2 J 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 w 0 and initialize each worker with w 0,j = w 0 for j ∈ [1, J]. ∇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 j 0 ∈ [1, J]

E ∇w (n) -w (n,j0) 2 ≤ 4γ 2 d 2 G 2

Proof. From the update of (TS), we have

E ∇w (n) -w (n,j0) 2 = γ 2 E    1 J J j=1 n-1 i=d n d +1 ∇w (i,j) - n-1 i=d n d +1 ∇w (i,j0) 2    ≤ 2γ 2 E    1 J J j=1 n-1 i=d n d +1 ∇w (i,j) 2    + E   n-1 i=d n d +1 ∇w (i,j0) 2   ≤ 2γ 2 d J J j=1 n-1 i=d n d +1 E ∇w (i,j) 2 + 2γ 2 d n-1 i=d n d +1 E ∇w (i,j0) 2 ≤ 4γ 2 d 2 G 2 .

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 (w 0 ) -f * ) + 4γ 2 d 2 G 2 L 2 + 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 (w 0 ) -f * + σ 2 ) + 4d 2 G 2 J N . = O( 1 √ JN ) + O( d 2 J 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 ).

:

‡ https://wiki.linuxfoundation.org/networking/netem § https://linux.die.net/man/1/qperf

Figures and Tables:

Figure 1: DTS maintains a good scalability when network latency increases, while the performance of conventional algorithms degrades quickly.

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.

to other (c) Synchronous distributed learning with temporally sparse update.

Figure 3: 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.

The learning curve with different temporal sparsity and scalability under various latency.

Figure 4: Compare the top-1 accuracy and scalability on ImageNet training.

(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. cards, batch size 32-1-1

Better speedup and scalability with DTS. Measured on servers across the world.

For iteration n = 0, 1, • • • On each local worker j, sample a stochastic gradient ∇w (n-1,j) and update:• If n (mod d) = 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) + ∇w n-d+k -∇w (n-d+k,j) )] (16)where∇w n-d+k = 1 J J j=1 ∇w (n-d+k,j) 3. Output ∇w (n) = 1 J 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) = w 0 -γ



Table content: <table><tr><td/><td/><td/><td>Ohio</td><td>140</td></tr><tr><td/><td/><td/><td>California</td><td>35ms</td><td>23M</td></tr><tr><td/><td/><td colspan="2">Inside a cluster</td><td>Across the world</td><td>63Mbps</td></tr><tr><td/><td/><td/><td>479,000</td><td>µs</td></tr><tr><td/><td/><td/><td>2,274</td><td>img/s</td></tr><tr><td/><td/><td colspan="2">159,666x longer</td><td>98x worse</td></tr><tr><td/><td/><td/><td>23</td><td>img/s</td></tr><tr><td/><td/><td>3</td><td>µs</td></tr><tr><td/><td/><td colspan="2">Latency</td><td>Speed</td></tr><tr><td>Latency</td><td>Scalability</td><td/></tr><tr><td>Across the world</td><td>3</td><td>2274</td></tr><tr><td>Inside a cluster</td><td>479000</td><td>23.32</td></tr></table>

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.

Table content: <table/>

communicate -T overlap -t × T compute ) Temporal Sparsity (p) 4||w||/(p × T training ) (T communicate -T overlap )/p Delayed Update (t) + Temporal Sparsity (p) 4||w||/(p × T training ) max(0, (T communicate -T overlap -t × T compute ))/p The networking requirements for different training strategies.

Table content: <table><tr><td/><td>Bandwidth</td><td>Non-computing time</td></tr><tr><td>Synchronous SGD</td><td>2||w||/T training</td><td>T communicate -T overlap</td></tr><tr><td>Delayed Update (t)</td><td>2||w||/T training</td><td>max(0, T</td></tr></table>

The learning curve with different delay steps and scalability under various latency.

Table content: <table><tr><td>-1</td></tr></table>



Table content: <table><tr><td>-1</td></tr></table>



Table content: <table><tr><td/><td/><td/><td/><td/><td>-1</td><td/><td/><td/><td/><td/></tr><tr><td colspan="2">L2 regularization</td><td>Accuracy Loss w/</td><td>L1 regularization</td><td colspan="2">L1 regularization</td><td colspan="2">L2 regularization</td><td colspan="2">L2 regularization</td><td/></tr><tr><td>w/o retrain</td><td/><td>o Retrain [L2 reg.]</td><td>w/o retrain</td><td>w/ retrain</td><td/><td>w/ retrain</td><td/><td colspan="2">w/ iterative prune</td><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td>and retrain</td><td/><td/></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0.875</td><td>0.0006</td></tr><tr><td>0.46</td><td>0.3351</td><td>-0.0002</td><td>0.3351</td><td>0</td><td>0.3351</td><td>0.000139</td><td>0.3351</td><td colspan="2">0 0.888888888888889</td><td>0.0003</td></tr><tr><td>0.72</td><td>0.4991</td><td>-0.0011</td><td>0.4991</td><td>-0.0008</td><td colspan="2">0.4991 0.0000389999999999002</td><td>0.4991</td><td>0.0004</td><td>0.9</td><td>-0.0008</td></tr><tr><td>1.05</td><td>0.6657</td><td>-0.0092</td><td>0.6657</td><td>-0.0027</td><td colspan="2">0.6657 -0.00126100000000007</td><td>0.6657</td><td colspan="2">0.0018 0.916666666666667</td><td>-0.0033</td></tr><tr><td>1.27</td><td>0.7494</td><td>-0.0216</td><td>0.7494</td><td>-0.0064</td><td colspan="2">0.7494 -0.00216100000000008</td><td>0.7494</td><td colspan="2">0.0015 0.928571428571429</td><td>-0.006</td></tr><tr><td>1.44</td><td>0.8</td><td>-0.0407</td><td>0.8</td><td>-0.0125</td><td>0.8</td><td>-0.0035</td><td>0.8</td><td>0.0003</td><td>0.9375</td><td>-0.0104</td></tr><tr><td>1.58</td><td>0.8335</td><td>-0.0739</td><td>0.8335</td><td>-0.021</td><td>0.8335</td><td>-0.0057</td><td>0.8335</td><td>-0.0017</td><td>0.94705</td><td>-0.0199</td></tr><tr><td>1.7</td><td>0.8569</td><td>-0.119</td><td>0.8569</td><td>-0.0298</td><td colspan="2">0.8569 -0.00806099999999998</td><td colspan="2">0.8569 -0.00458100000000006</td><td>0.95736</td><td>-0.042</td></tr><tr><td>1.81</td><td>0.8749</td><td>-0.1875</td><td>0.8749</td><td>-0.0443</td><td>0.8749</td><td>-0.010661</td><td colspan="2">0.8749 -0.0081810000000001</td><td>0.963</td><td>-0.06</td></tr><tr><td>2.0</td><td>0.899</td><td>-0.3617</td><td>0.899</td><td>-0.0896</td><td>0.899</td><td>-0.018</td><td>0.899</td><td>-0.0158</td><td/><td/></tr><tr><td>2.27</td><td>0.9299</td><td>-0.6365</td><td>0.9299</td><td>-0.3292</td><td>0.9299</td><td>-0.0413</td><td>0.9299</td><td>-0.0388</td><td/><td/></tr><tr><td>2.78</td><td>0.95</td><td>-0.7916</td><td>0.95</td><td>-0.7552</td><td>0.95</td><td>-0.115561</td><td>0.95</td><td>-0.088381</td><td/><td/></tr></table>

Peer review (iclr2020):
This paper tackles the issue of scalability in distributed SGD over a high-latency network. Along with experiments, this paper contributes two ideas: delayed updates and temporally sparse updates. - strengths: · Clear-looking overall presentation. Good efforts to explain the network problems (latency, congestion) and how they are tackled by delayed updates and temporally sparse updates. - weaknesses: · While the overall presentation looks clean, the paper does not talk about the setting (one parameter server and many workers, only workers, etc). 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. · There is no theoretical analysis of the soundness of the proposed algorithm. For instance in ASGD (that the authors cite), stale gradients are dampened before being used, which in turn is used to guarantee convergence. 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. · 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*)]. 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 (plus, orthogonal gradient compression techniques do exist, e.g. as in *Federated Learning: Strategies for Improving Communication Efficiency*). questions to the authors: - Can you clarify the setting? - Can you give at least an intuition why accepting stale gradient is correct (i.e. does not impede convergence)? There is no theoretical limit on the value of t; can workers take any arbitrary old gradient? 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? To solve that issue, ASGD introduces a simple dampening mechanism (which is necessary in the convergence proof), which your algorithm does not have. The 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), but seems to overlook that sparse communication techniques already exist (this fact should at least be mentioned). The idea of sparse communication for SGD exists since at least 2012 [1, Algorithm 3]. A first mention of the use of such techniques for *communication efficiency* dates from (at least) 2015 [2]. [1] Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. J. Mach. Learn. Res., 13(1):165–202, January 2012. [2] Sixin Zhang, Anna E. Choromanska, Yann LeCun. Deep learning with Elastic Averaging SGD. NeurIPS, 2015. I do not see a clear novelty, nor a proof (or even intuitions) that the proposed algorithm is theoretically sound. The 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).