Taming Momentum in a Distributed Asynchronous Environment
Ido Hakimi Saar Barkai Moshe Gabel Assaf Schuster
cs.LG cs.DC stat.ML


[
Taming Momentum in a Distributed Asynchronous Environment














equal*


Ido Hakimiequal,tech
Saar Barkaiequal,tech
Moshe Gabelto
Assaf Schustertech


toDepartment of Computer and Mathematical Sciences, University of Toronto Scarborough, Toronto, Canada
techDepartment of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel

Ido Hakimiidohakimi@gmail.com
Saar Barkaisaarbarkai@gmail.com
Moshe Gabelmgabel@cs.toronto.edu
Assaf Schusterassaf@cs.technion.ac.il




Distributed, Asynchronous

0.3in


Although distributed computing can significantly reduce the training time of deep neural networks, scaling the training process while maintaining high efficiency and final accuracy is challenging. Distributed asynchronous training enjoys near-linear speedup, but asynchrony causes gradient staleness - the main difficulty in scaling stochastic gradient descent to large clusters. Momentum, which is often used to accelerate convergence and escape local minima, exacerbates the gradient staleness, thereby hindering convergence. We propose DANA: a novel technique for asynchronous distributed SGD with momentum that mitigates gradient staleness by computing the gradient on an estimated future position of the model's parameters. Thereby, we show for the first time that momentum can be fully incorporated in asynchronous training with almost no ramifications to final accuracy. Our evaluation on the CIFAR and ImageNet datasets shows that DANA outperforms existing methods, in both final accuracy and convergence speed while scaling up to a total batch size of 16K on 64 asynchronous workers.

]










 



§ INTRODUCTION


Modern deep neural networks are comprised of millions of parameters, which require massive amounts of data and long training time <cit.>. The steady growth of neural networks over the years has made it impractical to train them from scratch on a single worker (computational device). Distributing the computations over several workers can drastically reduce the training time <cit.>. Unfortunately, stochastic gradient descent (SGD), which is typically used to train these networks, is an inherently sequential algorithm. Thus, it is difficult to train deep neural networks on multiple workers, especially when trying to maintain fast convergence and high final test accuracy <cit.>.


Synchronous SGD (SSGD) is a straightforward method to distribute the training process across multiple workers: each worker computes the gradient over its own separate mini-batches, which are then aggregated to update a single model. Because SSGD relies on synchronizations to coordinate the workers, its progress is limited by the slowest worker.


Asynchronous SGD (ASGD) addresses the drawbacks of SSGD by eliminating synchronization between the workers, allowing it to scale almost linearly. However, eliminating the synchronizations induces gradient staleness: gradients were computed on parameters that are older than the parameter server's current parameters. Gradient staleness is one of the main difficulties in scaling ASGD, since it worsens as the number of workers grows <cit.>. Due to gradient staleness, ASGD suffers from slow convergence and reduced final accuracy <cit.>. In fact, ASGD might not converge at all if the number of workers is too large.


Momentum <cit.> has been demonstrated to accelerate SGD convergence and reduce oscillation <cit.>. Momentum is crucial for high accuracy and is typically used for training deep neural networks <cit.>. However, when paired with ASGD, momentum exacerbates the gradient staleness <cit.>, to the point that it diverges when trained on large clusters.

Our contribution:  We propose DANA: a novel technique for asynchronous distributed SGD with momentum. By adapting Nesterov's Accelerated Gradient to a distributed setting, DANA computes the gradient on an estimated future position of the model's parameters, thereby mitigating the gradient staleness. As a result, DANA efficiently scales to large clusters, despite using momentum, while maintaining high accuracy and fast convergence. We show for the first time that momentum can be fully incorporated in asynchronous training with almost no ramifications to final accuracy. We evaluate DANA in simulations as well as in two real-world settings: private dedicated compute clusters and cloud data-centers. DANA consistently outperformed other ASGD methods, in both final accuracy and convergence speed while scaling up to a total batch size of 16K on 64 asynchronous workers. 



§ BACKGROUND


The goal of SGD is to find the global minimum of J(θ) where J is the objective function (i.e., loss) and the vector θ∈ R^k is the model's parameters from dimensional k. x_t denotes the value of some variable x at iteration t. ξ∈Ξ denotes a random variable from Ξ, the indices of the entire set of training samples Ξ = {1, ⋯, M}. J(θ; ξ) is the stochastic loss function with respect to the training sample indexed by ξ. The SGD iterative update rule is the following:

    g_t = ∇ J(θ_t; ξ)    ;   θ_t+1=θ_t-η g_t

Where η is the learning rate. We also denote ∇ J(θ) as the full-batch gradient at point θ:
∇ J(θ) = 1/M∑_i=1^M∇ J(θ; i).



  
Momentum
<cit.> proposed momentum, which has been demonstrated to accelerate SGD convergence and reduce oscillation <cit.>. Momentum can be described as a heavy ball that rolls downhill while accumulating speed on its way towards the minima. The gathered inertia accelerates and smoothes the descent, which helps dampen oscillations and overcome narrow valleys, small humps and local minima <cit.>. Mathematically, the momentum update rule (without dampening) is simply an exponentially-weighted moving average of gradients that adds a fraction of the previous momentum vector v_t-1 to the current momentum vector v_t.

    g_t = ∇ J(θ_t; ξ)      ;    
        v_t=γ v_t-1+g_t
    θ_t+1   =θ_t-η v_t

The momentum coefficient γ in <Ref> controls the portion of the past gradients that is added to the current momentum vector v_t. When successive gradients have a similar direction, momentum results in larger steps (higher speed), yielding up to quadratic speedup in the convergence rate for SGD <cit.>.



  
Nesterov
In the analogy of the heavy ball rolling downhill, a higher speed may cause the heavy ball to overshoot the bottom of the valley (the minima), if it does not slow down in time. <cit.> proposed Nesterov's Accelerated Gradient (NAG), which allows the ball to slow down in advance. NAG approximates θ̂_t, the future value of θ_t, based on the previous momentum vector v_t:

    θ̂_t = θ_t-ηγ v_t-1   ;     
        g_t = ∇ J(θ̂_t; ξ) 
    
        v_t=γ v_t-1+g_t   ;     θ_t+1=θ_t-η v_t

NAG computes the gradient using the parameters' estimated future value θ̂ instead of their current value θ. Thus, NAG slows the heavy ball down near the minima so it doesn't overshoot the goal and climb back up the hill. We refer to this attribute as look-ahead, since it allows peeking at the future position of θ. The gradient g_t is computed based on the approximated future parameters θ̂_t and applied to the original parameters θ_t via v_t.

    θ_t+1-θ̂_t   = θ_t-η v_t+1 - θ_t+ηγ v_t 
       = ηγ v_t - η (γ v_t+g_t) 
        = -η g_t

<Ref> shows that the difference between the updated parameters θ_t+1 and the approximated future position θ̂_t is only affected by the newly computed gradient g_t, and not by v_t. Therefore, NAG can accurately compute the gradient even when the momentum vector v_t is large.



§ GRADIENT STALENESS



In this work we consider the common implementation of distributed ASGD that uses a parameter server (also referred to as master), which is commonly used in large-scale distributed settings <cit.>. <Ref> illustrates the ASGD training process and the origin of gradient staleness <cit.>. In ASGD training, each worker pulls the up-to-date parameters θ_t from the master and computes a gradient of a single sample (<Ref>). Once the computations finish, the worker sends the gradient g_t to the master. The master (<Ref>) then applies the gradient g_t to its current set of parameters θ_t+τ, where τ is the lag. The variable x for worker i is denoted as x^i (for the master, i=0). The lag τ of gradient g_t^i is defined as the number of updates the master received from other workers while worker i was computing g_t^i.

 

In other words, gradient g_t^i is stale if it was computed on parameters θ_t but applied to θ_t+τ. This gradient staleness is a major obstacle when scaling ASGD: the lag τ increases as the number of workers N grows <cit.>, decreasing gradient accuracy and ultimately reducing the accuracy of the trained model. As a result, ASGD suffers from slow convergence and reduced final accuracy. In fact, ASGD may not converge at all if the number of workers is too large <cit.>.



  
From Lag to Gap
Previous works analyze ASGD staleness using the lag τ <cit.>. We argue that τ fails to accurately reflect the effects of the staleness. Instead, we measure the gradient staleness with the recently introduced gap <cit.>. We denote Δ_t+τ = θ_t+τ - θ_t as the difference between the master and worker parameters, and define the gap as:

    ( Δ_t+τ ) = (Δ_t+τ)= ‖Δ_t+τ‖_2/√(k)

Where k is the number of parameters. When Δ_t+τ = 0, the gradient is computed on the same parameters to which it will be applied. This is the case for sequential and synchronous methods such as SGD and SSGD. However, in asynchronous algorithms more workers result in an increased lag τ and thus a larger gap. <Ref> illustrates that in ASGD adding more worker increases the gap. 

Next, we show that the gap is directly correlated with gradient accuracy. A common assumption is that the gradient of J is an L-Lipschitz continuous function:

    ∇ J(x) - ∇ J(y)_2 ≤ Lx-y_2   , x, y ∈ℝ^k

Setting x=θ_t+τ, y=θ_t into <Ref>, we get that the inaccuracy of the stale gradient (with respect to the gradient on θ_t+τ) is bounded by the gap:

    ∇ J(θ_t+τ) - ∇ J(θ_t)_2    ≤  Lθ_t+τ-θ_t_2 
    
           =L·√(k)·(Δ_t+τ)

<Ref> shows that a smaller gap implies that the stale gradient is more accurate. Conversely, a larger gap means a larger upper bound on the inaccuracy of the stale gradient. The advantage of measuring the staleness using the gap instead of the lag can be illustrated by a simple extreme example of a worker with a lag of τ=2 at time step t+τ. If the two previous updates are in exactly opposite directions and are of the same magnitude, the worker will compute the gradient on the same parameters as the master θ_t+τ=θ_t. Therefore, the gradient will be accurately computed ∇ J(θ_t+τ) = ∇ J(θ_t), as if the lag were zero. However, the lag remains the same (τ=2), while the gap adjusts according to the two updates and is indeed equal to zero.





  
The Effect of Momentum
While momentum and NAG improve the convergence rate and accuracy of SGD, they make it more difficult to scale to additional asynchronous workers. To simplify the analysis, we henceforth assume that all workers have equal computation power. This assumption can be relieved by monitoring the rate of each worker's updates and weighting them accordingly. We denote by prev(i, t) the last iteration in which worker i sent a gradient to the master before time t. For ASGD and NAG-ASGD[NAG-ASGD is <Ref>, where the optimizer uses the aforementioned NAG method (<Ref>)], [Δ_t+τ ] is the sum of the gradients and the sum of the momentum vectors, respectively:

    [Δ^ASGD_t+τ]    = -η∑_i=1^Ng^i_prev(i,t+τ)
    [Δ^NAG-ASGD_t+τ]    = -η∑_i=1^Nv_prev(i,t+τ)

<Ref> demonstrates empirically that the gap of NAG-ASGD is considerably larger than that of ASGD due to momentum[This is quite intuitive since generally the momentum vector is larger than the gradient.], even though the lag τ in both algorithms is exactly the same.



 §.§ Parameter Prediction
 
The gap arises from the fact that we can not access the future parameters θ_t+τ. <cit.> proposed Linear Weight Prediction (LWP) to estimate future parameters:

    θ_t+τ≈θ̂^LWP_t ≜θ^0_t-τη v_t-1

To reduce the gap, LWP approximate the master's future parameters θ_t+τ in τ update steps. In other words, LWP scales the NAG estimation according to the number of times v_t-1 is used throughout the next τ updates. The worker then computes its gradient on θ̂^LWP_t instead of θ^0_t. LWP is frequently used in asynchronous model parallel pipelines <cit.> to reduce the staleness in the backpropagation; during the forward pass LWP estimates the parameters of the backwards pass. <Ref> describes the LWP master algorithm.

However, in large-scale asynchronous settings LWP is not beneficial because as τ increases, the effect of v_t-1 on reaching θ_t+τ diminishes. <Ref> shows that despite LWP parameter estimation θ̂^LWP_t, its gap is still large and only slightly lower than NAG-ASGD.

DANA-Zero, detailed in the next section, maintains a small gap throughout training, despite using momentum. The small gap enables DANA-Zero to compute more accurate gradients, as given by <Ref>, and therefore achieve fast convergence and high final accuracy.



§ DANA


DANA (Distributed Adaptive NAG ASGD) is a distributed asynchronous technique that achieves state-of-the-art accuracy and fast convergence, even when trained with momentum on large clusters. DANA is designed to reduce the gap by computing the gradient g_t on parameters that approximate the master's future position θ_t+τ using a similar look-ahead to that of NAG. Thus, for the same lag, DANA benefits from a reduced gap, as shown by <Ref>, and therefore suffers less from gradient staleness.



 §.§ The DANA-Zero Update Rule
 
To rectify the problem of LWP we propose to maintain at the master a separate momentum vector v^i for each worker i; these vectors are updated exclusively with the corresponding worker's gradients g^i using the same update rule as in vanilla SGD with momentum (<Ref>). We refer to this method as Multi-ASGD (<Ref>). 

To complete our adaptation of NAG to the distributed case, we propose to perform the look-ahead using the most recent momentum vectors of all of the workers. We name this method DANA-Zero. Instead of sending the master's current parameters θ^0_t, DANA-Zero sends θ̂^DANA_t, the estimated future position of the master's parameters after the next N updates, one for each worker:

    v_t^i    ≜γ v_prev(i,t-1)^i+g_t^i 
    θ̂^DANA_t    ≜θ^0_t-ηγ∑_i=1^Nv^i_prev(i, t-1)


<Ref> shows the DANA-Zero master algorithm. Unlike ASGD (<Ref>), the master now sends back to the worker a future prediction of the parameters θ̂ = θ^0-ηγ∑_j=1^Nv^j instead of the current parameters θ^0. This future prediction is what allows DANA-Zero to decrease the gap and therefore compute accurate gradients. The worker remains the same as in ASGD (<Ref>). <Ref> shows that DANA-Zero accurately estimates the future parameters θ_t+τ and therefore decreases its gap. 

<Ref> proves that [Δ^DANA_t+τ] = [Δ^ASGD_t+τ ] in an asynchronous environment of N equal computational powered workers:

    [Δ^DANA_t+τ] =    [θ_t+τ ] -  [θ̂_t  ] 
    =_<Ref>   θ_t - η∑_i=1^N(v^i_prev(i, t+τ)) 
       -  (θ_t - ηγ∑_i=1^Nv^i_prev(i,t-1) )
    =_<Ref>   θ_t - η∑_i=1^N(γ v^i_prev(i,t-1) + g^i_prev(i,t+τ))
       -  (θ_t - ηγ∑_i=1^Nv^i_prev(i,t-1) )
    
        
        =    -η∑_i=1^Ng^i_prev(i,t+τ)=_<Ref> [Δ^ASGD_t+τ ]

<Ref> shows that despite using momentum, DANA-Zero has a similar gap to that of ASGD. <Ref> demonstrates this empirically: DANA-Zero maintains a small gap throughout the training process. We note that, due to momentum, DANA-Zero converges faster than ASGD, resulting in smaller gradients, and therefore a smaller gap. For more details and an empirical validation see <Ref>.

We note that computing the full summation ∑_i=1^Nv^i_prev(i, t-1) in DANA-Zero can be done in 𝒪(k), instead of 𝒪(k · N) by maintaining v^0 = ∑_i=1^Nv^i_prev(i, t-1) and updating it using v^0_t = v^0_t - v^i_prev(i, t-1) + v^i_t. For further details please see <Ref>.



  
DANA-Zero Equivalence to Nesterov
When running with one worker (N=1) DANA-Zero reduces to a single NAG optimizer. This can be shown by merging the worker and master (<Ref>) into a single algorithm: since at all times θ^1_t=θ^0_t-ηγ v_t-1, the resulting algorithm trains one set of parameters θ, which is exactly the NAG update rule. <Ref> shows the combined algorithm, equivalent to the standard NAG optimizer.



 §.§ Optimizing DANA


In DANA-Zero, the master maintains a momentum vector for every worker, and must also compute θ̂^DANA at each iteration. This adds a small computation and memory overhead to the master. DANA-Slim, a variation of DANA-Zero, obtains the same look-ahead as DANA-Zero but without any computation or memory overhead. Thus, DANA-Slim maintains the same gradient staleness mitigation as DANA-Zero.



  
Bengio-NAG
<cit.> proposed a variation of NAG that simplifies the implementation and reduces computation cost. Known as Bengio-NAG, it defines a new variable Θ to stand for θ after the momentum update:

    Θ_t ≜θ_t -ηγ v_t-1

Substituting θ_t with Θ_t in the NAG update rule, using <Ref>, yields the Bengio-NAG update rule:

    θ_t+1   =θ_t-η v_t
    
        Θ_t+1+ηγ v_t   =Θ_t+ηγ v_t-1-η v_t
    Θ_t+1   = Θ_t-η(γ v_t+∇ J(Θ_t; ξ))

<Ref> shows the Bengio-NAG update rule, where the gradient is both computed on and applied to Θ, rather than computed on θ̂ but applied to θ. Hence, an implementation of Bengio-NAG needs to store only one set of parameters Θ in memory and doesn't require computing θ̂.



  
The DANA-Slim Update Rule
In creating DANA-Slim, we optimized DANA-Zero by leveraging the Bengio-NAG approach. We re-define Θ_t as θ_t after applying the momentum update from all future workers. Therefore, Θ_t+1 is Θ_t after the current worker's update:

    Θ_t    ≜θ_t -ηγ∑_j=1^Nv^j_prev(j,t-1)
    Θ_t+1   = θ_t+1 -ηγ(v^i_t+∑_j  iv^j_prev(j, t-1))

DANA-Slim eliminates both the computational and memory overhead at the master by substituting θ_t with Θ_t.

    θ_t+1   =θ_t-η v^i_t
       ⇓  <Ref>
    Θ_t+1   + ηγ(v^i_t+∑_j  i^N v^j_prev(j,t-1))
       =Θ_t+ηγ∑_j=1^Nv^j_prev(j,t-1)-η v^i_t
    Θ_t+1   =Θ_t+ηγ (v^i_prev(i,t-1)- (1+1/γ )· v^i_t ) 
       ⇓  <Ref>
    Θ_t+1   =Θ_t-η(γ v^i_t+∇ J(Θ_prev(i,t); ξ))

<Ref> shows that DANA-Slim benefits from the same gradient staleness mitigation as DANA-Zero up to a parameter switch. In DANA-Slim the master sends its current parameters Θ_t instead of computing the future parameters θ̂. Therefore, the master doesn't need to maintain the momentum vectors of all the workers.

<Ref> describes the worker algorithm of DANA-Slim. DANA-Slim only changes the worker algorithm, while using the same master algorithm as ASGD[Although <Ref> receives g_t while <Ref> sends v_t, there is no inconsistency since v_t, g_t ∈ℝ^k.] (<Ref>). Hence, it completely eliminates the overhead at the master and enjoys the same linear speedup scaling capabilities of ASGD. DANA-Slim is equivalent to DANA-Zero in all other aspects and provides the same gradient staleness mitigation.




 §.§ Delay Compensation
 
<cit.> proposed Delay Compensated ASGD (DC-ASGD), which tackles the problem of stale gradients by adjusting the gradient with a second-order Taylor expansion. Due to the high computation and space complexity of the Hessian matrix, they propose a cheap yet effective Hessian approximator, which is solely based on previous gradients. We denote by ⊙ a matrix element-wise multiplication. 

    g_t = ∇ J(θ_t; ξ)    ;   ĝ_t    = g_t + λ g_t ⊙ g_t ⊙ (θ_t+τ - θ_t) 
    θ_t+τ+1   = θ_t+τ-ηĝ_t

<Ref> describes DC-ASGD. The delay compensation term, λ g_t ⊙ g_t ⊙ (θ_t+τ - θ_t), adjusts the gradient g_t as if it were computed on θ_t+τ instead of θ_t; thus, mitigating the gradient staleness. However, DC-ASGD adds a memory overhead to the master since it now stores the previously sent parameters for each worker.

A Taylor expansion is more accurate when the source θ_t is in close vicinity to the approximation point θ_t+τ (a small gap). Momentum increases the gap, thus reducing the effectiveness of DC-ASGD. DANA-Zero ensures that the gap is kept small throughout training, even when using momentum; this amplifies the effectiveness of the delay compensation. The combined method, referred to as DANA with Delay Compensation (DANA-DC), is described in <Ref>.



§ EXPERIMENTS
 
In this section, we present our evaluations and insights regarding DANA. In <Ref> we focus on accuracy rather than communication overheads, and therefore we simulate multiple distributed workers[A single worker may be more than a single GPU. DANA, like all ASGD algorithms, treats each machine with multiple GPUs as a single worker. For example, DANA can run on 32 workers with 8 GPUs each (256 GPUs in total), where each worker performs SSGD internally, which is transparent to the ASGD algorithm.] and measure the final test error and convergence speed of different cluster sizes. In <Ref> we show the importance of decreasing the gap in asynchronous environments and point to the high correlation between small gap and high final test accuracy. Finally, in <Ref> we present real-world distributed asynchronous results that are trained in two settings: dedicated private compute cluster and public cloud data-center (Google cloud). We show that DANA trains over 25% faster than an optimized SSGD algorithm while maintaining high final test accuracy and fast convergence.




  
Simulation We simulate the workers' execution time using a gamma-distributed model <cit.>, where the execution time for each individual batch is drawn from a gamma distribution. The gamma distribution is a well-accepted model for task execution time that naturally gives rise to stragglers. We use the formulation proposed by <cit.> and set V=0.1 and μ=B*V^2, where B is the batch size, yielding a mean execution time of B simulated time units (additional details in <Ref>). <Ref> visualizes the distribution of workers' batch execution time. As expected, stragglers appear much more frequently in the heterogeneous environment than in the homogeneous environment.

Since one of our main goals in these experiments is to verify that decreasing the gap leads to a better final test error and convergence rate, we use the same hyperparameters across all algorithms. These are the original hyperparameters suggested by the authors of each neural network architecture's respective paper, tuned for a single worker (for additional details please see <Ref>). This eases the scaling to more workers since it doesn't require re-tuning the hyperparameters when increasing the cluster size.



  
Algorithms Our goal is to produce a scalable method that works well with momentum and therefore all evaluated algorithms use momentum (as does the baseline). Our evaluations consist of the following algorithms:

	
  * Baseline: Single worker with the same tuned hyperparameters as in the respective neural network's paper. This baseline does not suffer from gradient staleness, thus it is ideal in terms of final accuracy and convergence speed.
	
  * NAG-ASGD: Asynchronous SGD, which uses a single NAG optimizer for all workers.
	
  * Multi-ASGD: Asynchronous SGD, which maintains a separate NAG optimizer for each worker.
	
  * DC-ASGD: Delay compensation asynchronous SGD, as described in <Ref>, for which we set γ=0.95 as suggested by <cit.>.
	
  * YellowFin: An algorithm proposed by <cit.>, that automatically tunes the momentum γ and learning rate η throughout the training process. We used the asynchronous variation of YellowFin, named Closed-Loop, and set the hyperparameters η = 1e-4 and γ = 0.0 as suggested by <cit.>.
	
  * LWP: Linear Weight Prediction, described in <Ref>.
	
  * DANA-Slim: A variation of DANA-Zero, which eliminates the overhead, as described in <Ref>.
	
  * DANA-DC: A combination of DANA-Zero with DC-ASGD, as described in <Ref>, for which we set λ = 2, as suggested by <cit.>. 




 §.§ Evaluation on the CIFAR Datasets
 

We evaluate DANA with the ResNet-20 <cit.> and Wide ResNet 16-4 <cit.> architectures on the CIFAR-10 and CIFAR-100 datasets <cit.>. In the CIFAR experiments, bold lines show the mean over five different runs with random seeds, while transparent bands show the standard deviation. The baseline is the mean of five different runs with a single worker.

<Ref> shows that the final test error of both DANA-Slim and DANA-DC is lower than all the other algorithms for any number of workers, especially for large numbers of workers. Both variations of DANA exhibit a very small standard deviations, which points to the high stability DANA provides, even for large numbers of workers. The final accuracies of all the CIFAR experiments are listed in <Ref>.

NAG-ASGD demonstrates how gradient staleness is exacerbated by momentum. NAG-ASGD yields good accuracy with few workers, but fails to converge when trained with more than 16 workers. LWP scales better than NAG-ASGD but falls short of Multi-ASGD. Multi-ASGD serves as an ablation study: its poor scalability demonstrates that it is not sufficient to simply maintain a momentum vector for every worker. Hence, DANA (<Ref>) is also required to achieve fast convergence and low test error.

<Ref> shows the mean and standard deviation of the test error throughout the training of the different algorithms when trained on eight workers. This figure demonstrates the significantly better convergence rate of DANA-DC. It is usually similar to the baseline or even faster and outperforms all the other algorithms. It is noteworthy that DANA-DC's convergence rate surpasses that of DANA-Slim; however, DANA-DC incurs an overhead and both algorithms usually reach a similar final test error, as seen in <Ref>.


When attempting to utilize different computational resources <cit.>, workers may have considerably different computational power from one another. This heterogeneous environment creates high variance in batch execution times, as shown in <Ref>. Therefore, in heterogeneous environments, asynchronous algorithms have a distinct speedup advantage over synchronous algorithms which are slowed down by the slowest worker if not addressed <cit.>. <Ref> shows that even in heterogeneous environments, DANA achieves high final accuracy on large clusters of workers. For additional details about the heterogeneous experiments please see <Ref>.



 §.§ Evaluation on the ImageNet Dataset



<Ref> shows experiments where we evaluate DANA with ResNet-50 <cit.> on the ImageNet dataset <cit.>. In this experiment, every asynchronous worker is a machine with 8 GPUs, so the 64-worker experiment simulates a total of 512 GPUs with a total batch size of 16K.
<Ref> compares final test errors on different cluster sizes and shows that the scalability in terms of final accuracy of DANA-Slim and DANA-DC is much greater than all the other algorithms. <Ref> shows that both variations of DANA significantly outperform all the other algorithms in both convergence speed and final accuracy when trained on 32 asynchronous workers. <Ref> lists the final test accuracies on ImageNet.



 §.§ The Importance of the Gap
 
Although all algorithms share the same average lag (for a given number of workers), the algorithms that achieve a lower average gap (<Ref>) also demonstrate low final error (<Ref>) and fast convergence rate (<Ref>). Ergo, we conclude that the gap is more informative than the lag when battling gradient staleness and that gap reduction is paramount to asynchronous training. We note that the average gap of both DANA-Zero and DANA-DC is an order of magnitude smaller than that of NAG-ASGD and LWP, as shown in <Ref>. Further details of our analysis on the gap are discussed in <Ref>.



 §.§ Evaluation on a Private Compute Cluster
 
While this work focuses on improving the accuracy of ASGD, we also measured acceleration in training time. We conduct our experiments on a system with 8 Nvidia 2080ti GPUs that each have 11GB and base our code on PyTorch <cit.>. We use an efficient implementation for synchronous training[<https://github.com/pytorch/examples/tree/master/imagenet>] (DistibutedDataParallel known as SSGD) based on the Ring-AllReduce communication algorithm that is implemented by Nvidia's NCCL collective communication package. Furthermore, in SSGD, we overlap its computations with communications to accelerate the training by over 15% <cit.>.




<Ref> shows our asynchronous training setup. Each worker is executed on a different process with a dedicated GPU. The shared parameters are stored and updated on the shared memory similar to Hogwild <cit.>. The communications between the GPU and shared memory are transferred via pinned memory for fast parallel data transfer.

<Ref> presents results when training the ResNet-50 architecture on ImageNet with different total batch sizes where every asynchronous worker is a single GPU. For total batch sizes that are larger than 256 (batch size of 32 per GPU) we use gradient accumulation <cit.> to reduce memory footprint as well as reduce the synchronization frequency and communication overhead. Therefore, larger total batch sizes result in higher communication efficiency and shorter training times. <Ref> compares the final test error on different total batch sizes. Multi-ASGD quickly drops in final accuracy when scaling the total batch size. DANA-Slim, on the other hand, not only scales well but in some cases even surpasses the final accuracy of SSGD. <Ref> shows that DANA-Slim converges faster than both Multi-ASGD and SSGD. DANA-Slim trains 25% faster than SSGD while achieving similar final accuracy. <Ref> lists the  final accuracies, training time, and the speedup over a single GPU. DANA-Slim achieves perfect linear scaling while maintaining final accuracy similar to the baseline.



 §.§ Evaluation on a Public Cloud Data-center
 
We evaluate the scalability of DANA-Slim on a public cloud data-center (Google cloud) with a single parameter server and one Nvidia Tesla V100 GPU per machine. Our cross-machine communications are based on CUDA-Aware MPI (OpenMPI) with a 10Gb Ethernet NIC per machine. <Ref> shows that DANA-Slim successfully scales up to 20 workers in agreement with the simulations of <Ref> with high speedup and low final test error (less than 1% higher than the baseline). We consider parameter server optimizations to be beyond the scope of this paper and detail popular parameter server optimization techniques that are orthogonal and compatible with DANA in <Ref>.




§ RELATED WORK


Asynchronous training causes gradient staleness, which hinders the convergence. Several approaches <cit.> proposed to mitigate gradient staleness by tuning the learning rate with regard to the lag τ. These approaches are designed for SGD without momentum and therefore do not address the massive gap that momentum generates. <cit.> show that asynchronous training induces implicit momentum. Thus, the momentum coefficient γ must be decayed when scaling up the cluster size. By decreasing the gap caused by momentum, we show that fast convergence and high final test accuracy is possible in an asynchronous environment with DANA, even when γ is relatively high.

Other approaches for mitigating gradient staleness include DC-ASGD <cit.>, which uses a Taylor expansion to reduce the gradient staleness. YellowFin <cit.> is an SGD based algorithm that automatically tunes the momentum coefficient γ and learning rate η throughout the training process. Both YellowFin and DC-ASGD achieve high accuracy on small clusters, but fall short when trained on large clusters (<Ref>) due to the massive negative effects of the gradient staleness. Communication-efficient asynchronous algorithms, such as Elastic Averaging SGD (EASGD) by <cit.>, can reduce communication overhead. EASGD is an asynchronous algorithm that uses a center force to pull the workers' parameters towards the master's parameters. This allows each worker to train asynchronously and synchronize with the master once every few iterations. Not only are these approaches compatible with (and indeed orthogonal to) DANA, we show that DANA can amplify the effectiveness of the other approaches, as demonstrated with DANA-DC (<Ref>).



§ CONCLUSION

In this paper we tackle gradient staleness, one of the main difficulties in scaling SGD to large clusters in an asynchronous environment. We introduce DANA: a novel asynchronous distributed technique that mitigates gradient staleness by computing the gradient on an estimated future position of the model's parameters. Despite using momentum, DANA efficiently scales to large clusters while maintaining high final accuracy and fast convergence. Thereby, we showed for the first time that momentum can be fully incorporated in asynchronous training with almost no ramifications to final accuracy. We performed an extensive set of evaluations on simulations, private compute clusters, and public cloud data-centers. Throughout our evaluations, DANA consistently outperformed all the other algorithms in both final test error and convergence rate. For future work, we plan on adapting DANA to newer optimizers, such as Nadam <cit.>, and to more recent asynchronous algorithms, in particular EASGD and YellowFin. 



§ ACKNOWLEDGEMENT

The work on this paper was supported by the Israeli Ministry of Science, Technology, and Space and by The Hasso Plattner Institute.








mlsys2020











§ EXPERIMENTAL SETUP



 §.§ Algorithms


<Ref> only change the master's algorithm; the complementary worker algorithm is the same as ASGD (<Ref>). The master's scheme is a simple FIFO. We consider parameter server optimizations to be beyond the scope of this paper.





 §.§ Efficient computation in DANA-Zero
 
Computing the full summation ∑_i=1^Nv^i_prev(i, t-1) of the future position of the master's parameters can be computationally expensive since its computational cost scales up with the number of workers. In practice, DANA-Zero doesn't compute the full summation for every worker that requires the future position of the masters parameters. Instead, DANA-Zero maintains v^0, which is equivalent to the summation of all current momentum vectors at step t. After an update from worker i, DANA-Zero subtracts the worker's previous momentum vector v^i_prev(i, t-1) from v^0_t and adds the worker's updated momentum vector v^i_t to v^0_t. Thus, after each worker update, v^0_t is updated by v^0_t = v^0_t - v^i_prev(i, t-1) + v^i_t. Hence, the computation cost of the summation reduces from 𝒪(k · N) to 𝒪(k); this is the same cost as computing the traditional NAG look-ahead, which isn't affected by the number of workers N.



 §.§ Datasets



  
CIFAR The CIFAR-10 <cit.> dataset comprises of 60K RGB images partitioned into 50K training images and 10K test images. Each image contains 32x32 RGB pixels and belongs to 1 of 10 equal-sized classes. CIFAR-100 is similar but contains 100 classes. https://www.cs.toronto.edu/ kriz/cifar.htmlLink.


  
ImageNet The ImageNet dataset <cit.>, known as ILSVRC2012, consists of RGB images, each labeled as 1 of 1000 classes. Images are partitioned into 1.28 million training images and 50K validation images. Each image is randomly cropped and re-sized to 224x224 (1-crop validation). http://www.image-net.org/Link.



 §.§ Gamma Distribution


<cit.> suggest a method called CVB to simulate the run-time of a distributive network of computers. The method is based on several definitions:
Task execution time variables:

    
  * μ_task - mean time of tasks
    
  * V_task - variance of tasks
    
  * μ_mach - mean computation power of machines
    
  * V_mach - variance of computation power of machines
    
  * α_task = 1/V_task^2
    
  * α_mach = 1/V_mach^2

G(α, β) is a random number generated using a gamma distribution, where α is the shape and β is the scale.

For our case, all tasks are similar and run on a batch size of B. Therefore, the algorithm for deciding the execution-time of every task on a certain machine is reduced to one of the following:


where K is the total amount of tasks of all the machines combined (the total number of batch iterations), M is the total number of machines (workers), and curr is the machine currently about to run.

We note that <Ref> naturally give rise to stragglers. In the homogeneous algorithm, all workers have the same mean execution time but some tasks can still be very slow; this generally means that in every epoch a different machine will be the slowest. In the heterogeneous algorithm, every machine has a different mean execution time throughout the training. We further note that p[j] is the mean execution time of machine j on the average task. 

In our experiments, we simulated execution times using the following parameters as suggested by <cit.>: μ_task = μ_mach = B· V_mach^2, where B is the batch size, yielding a mean execution time of μ simulated time units, which is proportionate to B. In the homogeneous setting V_mach = 0.1, whereas in the heterogeneous setting V_mach = 0.6. For both settings, V_task = 0.1.

<Ref> illustrates the differences between the homogeneous and heterogeneous gamma-distribution. Both environments have the same mean (128) but the probability of having an iteration that is at least 1.25x longer than the mean (which means 160 or more) is significantly higher in the heterogeneous environment (27.9% in heterogeneous environment as opposed to 1% in the homogeneous environment).



 §.§ Hyperparameters


To verify that decreasing the gap leads to a better final test error and convergence rate, especially when scaling to more workers, we used the same hyperparameters across all the tested algorithms. These hyperparameters are the original hyperparameters of the respective neural network architecture, which are tuned for a single worker. 



  
CIFAR-10 ResNet-20

    
  * Initial learning rate η: 0.1
    
  * Momentum coefficient γ: 0.9 with NAG
    
  * Dampening: 0 (no dampening)
    
  * Batch size B: 128
    
  * Weight decay: 1e-4
    
  * Learning rate decay: 0.1
    
  * Learning rate decay schedule: epochs 80 and 120
    
  * Total epochs: 160




  
CIFAR-10/100 Wide ResNet 16-4

    
  * Initial learning rate η: 0.1
    
  * Momentum coefficient γ: 0.9 with NAG
    
  * Dampening: 0 (no dampening)
    
  * Batch size B: 128
    
  * Weight decay: 5e-4
    
  * Learning rate decay: 0.2
    
  * Learning rate decay schedule: epochs 60, 120 and 160
    
  * Total epochs: 200




  
ImageNet ResNet-50

    
  * Initial learning rate η: 0.1
    
  * Momentum coefficient γ: 0.9 with NAG
    
  * Dampening: 0 (no dampening)
    
  * Batch size B: 256
    
  * Weight decay: 1e-4
    
  * Learning rate decay: 0.1
    
  * Learning rate decay schedule: epochs 30 and 60
    
  * Total epochs: 90




  
Learning Rate Warm-Up In the early stages of training, the network generally changes rapidly, causing error spikes. For all algorithms, we followed the gradual warm-up approach proposed by <cit.> to overcome this problem. We divided the initial learning rate by the number of workers N and ramped it up linearly until it reached its original value after five epochs. We also used momentum correction <cit.> in all algorithms to stabilize training when the learning rate changes.



§ ADDITIONAL RESULTS



 §.§ CIFAR Final Accuracies


DANA-DC starts to show signs of divergence when it reaches  32. However, when we tuned the learning rate η, DANA-DC reached a significantly lower test error than that shown in <Ref>. More precisely, when trained on 32 workers with η = 0.025, DANA-DC reached a test error of only 2.5% higher than the baseline on both CIFAR10 scenarios and 4.5% higher than the baseline on CIFAR100.









 §.§ ImageNet Final Accuracies




<Ref> lists the final test accuracy of the different algorithms when training the ResNet-50 architecture <cit.> on ImageNet. DANA consistently outperforms all the other algorithms.



 §.§ Normalized Gap





As shown in <Ref>, the gap of DANA-Zero is smaller than that of ASGD, despite <Ref>. This is because DANA-Zero uses momentum, which accelerates the convergence and leads to smaller gradients. To make a more accurate comparison between the gaps of different algorithms, we define the normalized gap as ^*(Δ_t+τ)=(Δ_t+τ)/g_t.
<Ref> shows that the normalized gap of ASGD is roughly similar to that of DANA-Zero, empirically confirming <Ref>. This suggests that DANA-Zero's future position approximation is close to optimal, even when training with stragglers.



§ ASYNCHRONOUS SPEEDUP





 §.§ CIFAR-10 Distributed Experiments



DANA-Slim successfully scales up to 20 workers (similarly to the simulations) with high speedup and low final test error (less than 1% higher than the baseline). Above 20 workers, the master becomes a bottleneck. This is consistent with the literature on ASGD <cit.>. To overcome this bottleneck, existing parameter server optimization techniques can be used, such as sharding <cit.>, synchronization frequency reduction <cit.>, network utilization improvements <cit.>, communication compression <cit.>, and overlapping communications with computations <cit.>. We note that DANA is compatible with these optimizations. The speedup superiority of ASGD methods compared to SSGD methods is discussed in <Ref>. 

<Ref> shows the speedup and final test error when running DANA-Slim on the Google Cloud Platform with a single parameter server (master) and one Nvidia Tesla V100 GPU per machine, when training ResNet-20 on the CIFAR-10 dataset. It shows speedup of up to 16× when training with N=24 workers. As before, its final test error remains close to the baseline for up to N=24 workers.



Cloud computing is becoming increasingly popular as a platform to perform distributed training of deep neural networks <cit.>. Although synchronous SGD is currently the primary method <cit.> used to distribute the learning process, it suffers from substantial slowdowns when run in non-dedicated environments such as the cloud. This shortcoming is magnified in heterogeneous environments and non-dedicated networks. ASGD addresses the SSGD drawback and enjoys linear speedup in terms of the number of workers in both heterogeneous and homogeneous environments even in non-dedicated networks. This makes ASGD a potentially better alternative for cloud computing. 

<Ref> shows the theoretically achievable speedup, based on the detailed gamma-distributed model, for asynchronous (GA and other ASGD variants) and synchronous algorithms using homogeneous and heterogeneous workers. The asynchronous algorithms can achieve linear speedup while the synchronous algorithm (SSGD) falls short as we increase the number of workers. This occurs because SSGD must wait in each iteration until all workers complete their batch. <Ref> shows that ASGD-based algorithms (including GA, SA and DANA versions) are up to 21% faster than SSGD in homogeneous environments. In heterogeneous environments, ASGD methods can be 6x faster than SSGD. We note that this speedup is an underestimate, since our simulation includes only batch execution times. It does not model the execution time of barriers, all-gather operations, and other overheads which usually increase communication time, especially in SSGD.



§ HETEROGENEOUS ENVIRONMENT



In our experiments, the algorithms scale better in the heterogeneous environment <Ref> than in the homogeneous environment (<Ref>). The reason is that stragglers naturally have less impact on the training process. We will demonstrate this with a simplistic example. Consider an asynchronous environment with only N=2 workers, where one worker is significantly faster than the other. The fast worker will run as in sequential SGD, since its gap and lag will mostly be zero. Conversely, the slow workers will have minimal impact and therefore its stale gradients wouldn't harm the convergence process.

This suggests that high accuracy can be attained more easily in asynchronous heterogeneous environments than in homogeneous environments. <Ref> show that even in a heterogeneous environment, DANA-DC converges the fastest and achieves the highest final accuracy. The final accuracies are listed in <Ref> below.




























