At Stability's Edge: How to Adjust Hyperparameters to Preserve Minima Selection in Asynchronous Training of Neural Networks?
Authors: Niv Giladi
Mor Shpigel Nacson
Elad Hoffer
Daniel Soudry
Venue:  (2020)
Keywords: implicit bias
stability
neural networks
generalization gap
asynchronous SGD

Abstract: Background: Recent developments have made it possible to accelerate neural networks training significantly using large batch sizes and data parallelism. Training in an asynchronous fashion, where delay occurs, can make training even more scalable. However, asynchronous training has its pitfalls, mainly a degradation in generalization, even after convergence of the algorithm. This gap remains not well understood, as theoretical analysis so far mainly focused on the convergence rate of asynchronous methods.
Contributions: We examine asynchronous training from the perspective of dynamical stability. We find that the degree of delay interacts with the learning rate, to change the set of minima accessible by an asynchronous stochastic gradient descent algorithm. We derive closed-form rules on how the learning rate could be changed, while keeping the accessible set the same. Specifically, for high delay values, we find that the learning rate should be kept inversely proportional to the delay. We then extend this analysis to include momentum. We find momentum should be either turned off, or modified to improve training stability.  We provide empirical experiments to validate our theoretical findings.

Published as a conference paper at ICLR 2020
AT STABILITY'S EDGE: How TO ADJUST HYPER- PARAMETERS TO PRESERVE MINIMA SELECTION IN ASYNCHRONOUS TRAINING OF NEURAL NETWORKS?
Niv Giladi
Mor Shpigel N
Elad Hoffer
Daniel Soudry!
TTchhnion Israel Institute of Technology. Haifa, Israel Habana-Labs, Caesarea, Israel gglladinv, mor. mor. shpigel, elad, hoffer, daniel. soudry ) @gmaal............ com
ABSTRACT
Recent developments have made it possible to accelerate neural net- works training significantly using large batch sizes and data parallelism. Training in an asynchronous fashion, where delay occurs, can make training even more scalable. However, asynchronous training has its pitfalls, mainly degradation in generalization, even after convergence of the algorithm. This gap remains not well understood, theoretical analysis so far mainly focused on the convergence rate of asynchronous methods.
Background:
Contributions: We examine asynchronous training from the perspective of dy- namical stability. We find that the degree of delay interacts with the learning rate, change the set of minima accessible by asynchronous stochastic gradient descent algorithm. We derive closed-form rules on how the learning rate could be changed, while keeping the accessible set the same. Specifically, for high delay values, we find that the learning rate should be kept inversely proportional to the delay. We then extend this analysis to include momentum. We find momentum should be either turned off, or modified to improve training stability. We provide empirical experiments validate our theoretical findings.
INTRODUCTION
Training deep neural networks (DNNs) requires large amounts of computational resources, often using many devices operating over days and weeks. Furthermore, with ever-increasing model size and available data, the amount of compute used was noted to increase exponentially over the past few years (Amodei & Hernandez 2018). Fortunately, the operations made in DNN training are highly suitable for parallelization over many devices. Most commonly, the parallelization is done by parallapaallelimm" in which the data is divided into separate batches which are distributed between different devices during training. By using many devices, with each device highly utilized, one could train on a large number samples without paying in run-time. However, this training is done synchronously, with synchronization between the different devices done on every iteration (SSGGD). With the growth in the number of devices participating in the training, the synchronization becomes a prominent bottleneck.
To overcome the synchronization bottleneck, asynchronous training (A-SGD) has been proposed (Dean al. 2012; Recht al. 2011). The basic idea behind such training is that when device finishes calcul allulatiigg its batch gradients, an update to the DNN parameters is immediately performed, without waiting for other devices. This approach is known as asynchronous centralized training with a parameter server (PS) that updates the parameters (Li) 2014). The main problem in such training is that, since the PS updates the parameters whenever a device communicates with him, the parameters that are being used in other devices calculation are no longer up-to-date. This phenomena is called gradient staleness or delay as we will refer to it, and it causes deterioration generalization performance when using A-SGD.
"Equal contribution

---

Published as a conference paper at ICLR 2020
The generalization deterioration be seen in Fig. Unless the learning rate is significantly decreased, we can see a generalization gap: a deterioration in the generalization of A-SGD (with delay r = 32) from the baseline (S-SGD, full convergence, following many training epochs (2000). Due to the generalization gap demonstrated in the figure, A-SGD with parameter server and large delays is not commonly used despite it is relatively simple to implement and despite its vast potential to accelerate training. Therefore, our main goal in this work is to shed some theoretical light on the generalization gap problem and use to improve A-SGD training.
0) value near the steady state i.c., after are near
2-
0.003
-00.00
1.8
9-0.10
Validation Evoor %
0.020
Validation Eroor %
0.030
1.6
10:
0.050
1.4
1.2-
SGD, 0. 0.5
0.8
10"
10!
10
10
0.01
0.02
0.03
0.04
0.05
Epochs
Leariing Rate
Figure 1: Impact of learning rate and delay on generalization error. Validation error with delay (7 32) and different learning rates 17. We observe that unless we decrease the learning rate (proportionally to 1/T) there a generalization gap from the equivalent large batch training: (left) training curve. (right) validation error as function of learning rate after reaching steady state. Horizontal dashed line is the validation error acquired by the equivalent large batch training (S-SGD, 7 0). Learning rates larger then 0.05 did not converge with (7 32) delay. CNN trained with MNIST. More details section B
Previous theoretical analysis of A-SGD (Liu et al.) 2018 Lian et al., 2016 2015 Dai et al., 2018) Dutta et al. 20188 8 Arjevani et al. 2018) focused analyzing the convergence rate, i.e., the time it takes to reach steady state, and not on the properties of the obtained solution. contrast, our paper focus understanding how the delay affects the selection of the solution we converge to, and changes in this selection can impact generalization.
We tackle these questions from the perspective of dynamical stability. The dynamical stability approach was used in (Nar & Sastry 2018 Wu et al. 2018), to study which minima are accessible under specific choice of optimization algorithm and hyperparameters. In (Nar & Sastry] 2018), the authors analyzed gradient descent (GD) algorithm as a discrete-time nonlinear dynamical system. By analyzing the Lyapunov stability of this system for different minima, they showed a relation between the learning rate choice and the accessible minima set, i.e., the subset of the local optima that GD can converge to. In (Wu et al., 2018). the authors focused on stochastic gradient descent (SGD), defined a criterion to evaluate the stability of specific minimum and used this criterion to show how the learning rate and batch-size play a role in SGD minima selection process.
Here, we use dynamical stability to analyze the dynamics of A-SGD. Using this approach, the main question we try to tackle is:
How do learning rate, delay and momentum interact and affect the minima selection process?
Contributions
We start by modelling A-SGD dynamical system with delay. By analyzing the stability properties of that system, we find:
There exist an inverse linear relation between the delay of A-SGD, and the threshold learning rate i.c., the critical learning rate in which a minimum loses stability.
This implics that in order to keep specific minimum stability we change the delay, need to change the learning rate inversely proportional to the delay.
Momentum has crucial role in determining stability properties for A-SGD, Depending on the specific training algorithm, it can either hurt the stability or improve it. We show how to modify momentum to stabilize A-SGD training.
2

---

Published as a conference paper at ICLR 2020
With theoretical findings, we derive closed form rules when training asynchronously. We suggest to scale the learning rate inversely to the delay in order to reach a better generalization performance. In section 3] we provide experiments is interesting to contrast this simple linear relation with the more complicated picture observed for the scaling of the learning rate with the batch size. Specifically, it has heen observed by [Shallue et al.) (2018) that the optimal learning rate scales differently with the batch size when changing the models and datasets, i.e., there no general "rule of thumb" that applies in all cases.
popular classification tasks to support our theoretical analysis.
A similar scaling rule for the learning rate was proposed before (Zhang et al. 2013), however, there it lacked theoretical basis or demonstration of its effectiveness with large effective batch sizes, i.e. the sum of all the minibatch sizes of all the workers, as we do here.
2 THEORETICAL ANALYSIS
2.1 PRELIMINARIES AND PROBLEM SETUP
Consider the problem of minimizing the empirical loss
N f(x) Σ f((),
(I)
where N is the number of samples, x Rd and Vi = 1, I... N: f. R2 - R twice continuously differentiable function. The update rule for minimizing (x) in eq. Jusing asynchronous stochastic gradient descent (A-SGD) is given by
X = - [/(t
V)V
where v) is the learning rate, n()) is a random selection process of a sample from (1.2.... 2.....NJ N) at iteration i, and is some delay due the asynchronous nature of our training. For simplicity, we focus on a fixed delay r. The extension to stochastic delay is discussed in section 2.2.
Our main goal understanding how different factors such as the gradient staleness and the learning rate affect the minima selection process in neural networks. In other words, we would like to understand how the different hyperparameters interact to divide the minima of the loss to two sets: those we can converge to and those we cannot converge to.
To analyze this we suppose we are vicinity of some minimum point x", which implies fx(*)) O. Given some values of and т, we ask whether or not we can converge to x", using the theory of dynamical stability. As we shall see, the learning rate 17 or delay r are too high, then this minimum loses stability, i.e., A-SGD cannot converge to x" in expectation.
Specifically, we examine the expectation of the linearized dynamics around x". We show in appendix that, to ensure stability, it is sufficient that the following one-dimensional equation is stable:
T++1 It + nart-- 0,
N N Σ fx'",, the sharpness term a Amax (H) as the
where we defined the Hessian
maximal eigenvalue of the Hessian, and JG the projection of the expectation of the perturbation
X, x" on the eigenvector which corresponds to the maximal eigenvalue a. Additionally, we show in appendix A that the characteristic equation of eq. 3 is
2+ 2 + na 0.
2.2 STABILITY ANALYSIS
For given (1) 7), we would like determine if the minimum point x* is asymptotically stable OOpeenheim 1999) in expectation. This will enable us to divide the minima into two sets: those we might converge to since they stable, and those cannot possibly converge (except for measure zero set initialization) since they are unstable. We use the characteristic equation (eq. to define the stability criterion:
3

---

Published as a conference paper at ICLR 2020
Definition (Stability criterion) For given (1, T). we say that the dynamics in eq. 3 Jree stable if all the roots of the corresponding characteristic equation (eq. 4 are inside the unit circle. This condition is equivalent 2t for any initialization.
We would like find conditions when and how can change the hyperparameters (17, 7) to maintain the same stability criterion. This, for example, will enable us to understand how to compensate for the delay introduced by asynchrony using the learning rate. In order to analyze stability we examine the characteristic equation in eq. and ask: when does the maximal root of this polynomial have unit magnitude?
2.2.1
THE INTERACTION BETWEEN LEARNING RATE AND DELAY
Recall the characteristic equation
gT+ oz) 0.
(5)
This polynomial has + 1 roots. In order ensure stability require that the root with the maximal magnitude, i.e., the maximal root, will be inside the unit circle. We want to find the threshold learning rate, i.e., the learning rate in which the maximal root is exactly the unit circle, threshold of stability. In appendix B
the
we show that this requires that
an sin
(6)
4T 2
Using Taylor approximation we get
1 )
1
1 π
ar) 2 4T
(2r 0 an
We observe numerically that the error between the exact solution (eq. and the linear approximation
(eq. 7 is smaller than 0.05 for + 2 1. Additionally, in the appendix Fig. 6 we demonstrate the high accuracy of the analytic approximation of the relation between 1 and т, compared to the numerical evaluation of the value of an
for which the maximal root of eq. is the unit circle.
We can see that maintain stability for given minimum point (or given sharpness value) the learning rate should be kept inversely proportional to the delay. This implies that given some minimum for r 0 and corresponding learning rate n/o for which this minimum stable, we can evaluate the learning rate which will ensure this minimum remain stable for larger delay values. To do this, we first estimate a using eq. 6 amju = 2in (
Implications:
2 a 2. Note that interested in O, while the relation in eq. i only a good approximation for r 2 1. Next, given some delay т, we substitute a into eq. in order to evaluate learning rate value for which the stability of all minima is maintained in
do not use eq. to evaluate since
π
T7/o
7) ~J
(8)
+1)
4(T+
Related empirical results: In section 3.1 we show empirically the existence of stability threshold for different values of delay and compare it with our theoretical threshold.
Stochastic delay: In appendix we extend our theoretical analysis to derive the characteristic equation for A-SGD with stochastic delay, i.c., when 7 is drawn from some discrete distribution. We analyze two cases:
Discrete uniform distribution: unif b).
Gaussian distribution discrete approximation: Vu, Vk I,.., 2μ Pr(r k) = Pr(k - 0.5 < < k + 0.5) where z ~ N(u, 1). In Zhang al. (2015), the authors showed empirically a delay distribution that resembles to Gaussian distribution.
For both cases, we show numerically that the inverse relation between the learning rate r and the expected delay Er still applies.
4

---

Published as a conference paper at ICLR 2020
2.2.2 THE EFFECTS OF MOMENTUM ON STABILITY
The optimization step of A-SGD with momentum is defined as follows:
V++1 = mV - 17 - (x((e-)((X---)
X = X, + V
(9)
where x; the weights, Va and f(n(t)) (Xx) are the velocity and gradients at time t, respectively, m is the momentum parameter, 1) is the step size and is the delay. The constant (1 m) term which multiplies the gradients called "dampening".
In appendix D we extend our theoretical analysis to derive the characteristic equation for A-SGD with momentum. In addition, section D.2. we show numerically that an inverse relation between the learning rate 1 and the delay also applies when using momentum. Particularly,
1. We need to keep the learning rate inversely proportional to the delay.
2. For given delay, larger momentum values require smaller learning rate for stability.
Therefore, the range of stable learning rates decreases when the momentum parameter ('m') increases which can make tuning the learning rate difficult, especially with large delays. These results suggest that, to ensure stability when training with large delay, it is recommended to work without momentum.
Relation to previous results: The conclusion that when using A-SGD with high delay values it's recommended to turn off momentum is consistent with the results of Mitliagkas al. (2017); Liu al. al. (2018). In Liu et al.) (2018), for streaming PCA, the authors showed it is necessary to reduce momentum in order to ensure convergence and acceleration through asynchrony. In Mitliagkas et al. (211)) the authors suggested that asynchrony adds implicit momentum to the training process and therefore it necessary to reduce momentum when working asynchronously.
Next, we discuss new method for introducing momentum into asynchronous training. This method enables asynchronous training where increasing the momentum parameter improves the stability.
Shifted momentum As discussed, training asynchronously is less stable when momentum is used. We propose to utilize momentum in an alternative method, called shifted momentum, for training asynchronously where the momentum benefits the training process and particularly its stability. We observe this method tends to improve the convergence stability compared to training without momentum (or with the original momentum), as is demonstrated in appendix Fig. []] We suggest that instead of exchanging the gradients terms, as in eq. [ we exchange the entire velocity term. This way, each worker calculates the velocity term based in its gradients and momentum buffer. The formulation this method is given the following equation:
Vi+1 mV 77 m) (x(t-=)(X
X Xx Ve+1
or
X++1 X₁ + m (x, xt- (1 m) V V[((e-)((x (x--r)
(10)
In appendix De we show that the characteristic equation of eq. i0
2 T+2 2 r+1 + (n7 (1 m) m) m m0
(11)
where we use the sharpness term a Amax (H) as before.
We would like to characterize how the learning rate, delay and momentum affect minima stability. Thus, for each momentum value, we evaluate numerically the value of 1 for which the maximal root of eq. IT is on the unit circle, i.e., when we are on the threshold of stability. In Fig. 4 [we see that the inverse relation between the learning rate 17 and the delay still applies when using shifted momentum. Moreover, we can see that in contrast to regular momentum, in shifted momentum, a larger momentum value m enables us work with larger step-size. Therefore, increasing the momentum improves the stability.
or
The analysis delayed gradients and velocity might also shed light on the stability of recent asynchronous training approaches. where the workers communicating through weight averaging (Lian et al. 2017; Assran et al. 2019). This method is similar to ours in the sense that each worker holds its momentum buffer. In parallel us, (Hakimi et al. 2019) used a variation of shifted momentum with Nesterov momentum (denoted as Multi-ASGD, and demonstrated empirically its generalization benefits, but without theoretical analysis of this benefit.
Relation to previous results:
5

---

Published as a conference paper at ICLR 2020
0.2
80
0.15
64
60
1/ //poccs
32
16
1/n
0.1
40
0.05
20
0
0
0.05 0.1
0.15
20
40
60
Figure 2: Stability threshold maintained when 7) x 1/T: the left figure we show number of epochs it takes to diverge from a minimum as a function of the learning rate 7). The black circles are the stability thresholds - below which, we do not escape the minimum. In the right figure for cach value of delay we show 1/1 where 7) is the maximal learning rate in which we did not diverge. Due sampling resolution, there might be up 8% deviation from the maximal learning rate found. This deviation is represented in the bars. VGG-11 trained with CTFAR1O.
3 EXPERIMENTS
In this section, we provide experiments to support our theoretical findings. In the following subsec- tions we: (I) demonstrate the relationship between hyperparameters and minima selection, and (2) show our findings can help improve asynchronous training. Details about the experiments and the implementation can be found in appendix E
3.1 How HYPERPARAMETERS AFFECT MINIMA SELECTION
In this section, we demonstrate how the delay and learning rate affect the accessible minima set. We train with fixed learning rate.
Minima stability. To demonstrate how delay and learning rate change the stability of minimum, we start from a model that converged to some minimum and train with different values of delay and learning rate to see if the algorithm leaves that minimum, i.e., the minimum becomes unstable. We do so by training VGG- on CIFARIC 10 for 10,000 epochs until we reach a steady state. This training is done without delay, momentum and weight decay. Next, introduce delay т, change the learning rate, and continue to train the model. Fig. shows the number of epochs it takes to leave the steady state for given delay and learning rate 7). We observe that for certain (T, n) pairs, the algorithm stays in the minimum (below the black circle) while for others it leaves that minimum after some number of epochs (above the black circle). Importantly, we can see in the right panel in Fig. that, as predicted by the theory, the inverse learning rate, 1/n, where is the maximal learning rate in which we did not diverge, scales linearly with the delay T. Additional details are given in appendix F
Generalization with delay. With delay, we need to adjust the hyperparameters in order to maintain the accessible minima set. However, even a certain pair of (T,1) changes the accessible set, is possible that there are still accessible minima that generalize well. We perform experiments to
investigate what type of generalization we can expect from training with different (T.7) pairs. We examine this by training a VGG-11 on CIFAR10 10 with different (T.r)) pairs until we reach steady state (around 6,000 epochs). We use plain SGD without momentum or weight decay. We compare the generalization performance achieved by each pair of learning rate and delay. We repeat the experiment for each pair four times and report mean and standard deviation values. The results presented in Fig. [3] We can empirical stability threshold, i.e., the learning rate in which the error diverge. In addition, we see that the smallest error (with small variance) is obtained at learning rate which is somewhat smaller then the learning rate at the empirical threshold of stability, as expected (LeCun et al. 2012).
linear scaling between the delay values and the learning rate
"oode will he available http:://githii..cmmppeess submi 8 ons/ /ww//ylllllllc.oo delay_staa stabi 111111110 1ity

---

Published as a conference paper at ICLR 2020
7=64
r=32
18
18
Emor %
Envor %
16
16
15
15
0.005
0.01
0.015
0.02
0.01
0.02
0.03
0.04
1=16
r=8
18
18
Ervr %
Emor
16
16
15
15-
0.035
0.04
0.045
0.05
0.055
0.06
0.07
0.08
0.09
0.1
Figure 3: Better generalization obtained near the stability threshold. Validation error Vs. learning rate of VGG-11 trained with CIFARIO for different delay values. Solid lines represent mean validation error. The margins represent one standard deviation. The vertical dashed line the learning rate according eq. The horizontal dashed line is the accuracy obtained with 7=0 (S-SGD).
Shifted momentum stability. In subsection 2.2.2 we introduced shifted momentum a modification
of the standard momentum update, in which increasing the momentum value ('m') improves stability. We validate the stability properties of this method by training fully connected model with MNIST. The model has 3 layers, 1024 neurons in each layer with ReL.U activations. Again, training is done synchronously with a large batch and no weight decay until reaches a steady state. Then, after reaching minimum, We found the maximum learning rate for a given m and T for which training does not diverge, i.c, this maximum learning rate is at the edge of stability. Fig. depicts the empirical results. The value of a Amax H) is estimated at the minimum point using power iteration. Two important results emerge from the graph. First, in order maintain the stability threshold, the learning rate has to be inversely proportional to the delay, as described in subsection 2.2 Second, with increased momentum values, training becomes more stable. Meaning, we can larger learning rates with larger momentum value. This stands in contrast to the analysis of the original momentum: as we show numerically in appendix [D] increasing the momentum value m in the standard momentum algorithm decreases the stability and hence we need to decrease the learning rate as the momentum value grows larger.
continued to train the model, each time with different triplet of (r, 7, m).
3.2 IMPROVING ASYNCHRONOUS TRAINING
So far we focused the steady state behavior of A-SGD, i.c. after many iterations. However, one of the prominent motivations for training asynchronously is to speed-up training. In this subsection, examine whether our findings also relevant for improving the accuracy of models trained asynchronously with little to no excess budget of epochs, compared to equivalent large batch regime. In large batch training. the learning size and the small one. As (Shallue et al. (2018) pointed out, we can expect a different learning rate scaling for different models/datasets. We start with set of models and datasets that follow square root scaling of the learning rate with the batch size (Hoffer et al,, 2017). Recall that our inversely linear scaling rule (i.e., 17 x 1/T) applies to the large batch learning rate. We demonstrate the validity of our inversely linear learning rate scaling by comparing our method with one that does not account for the delay т. The results are presented in Table I We can see that using the small batch regime with delay (ASGD) does not converge at all. With our inversely linear learning rate scaling (+LR), there a small gap from the equivalent large batch. If we also increase the budget of epochs by 30%, optimization regime (+30%) generalizes better than the large batch (LB). Because A-SGD has better run timtimme performance compared to S-SGD (Dutta et al.) 2018 Assran et al.) 2019), such excess in epochs may still result in improved overall wall clock time (this depends on the hardware details).
is scaled function of the ratio between the large batch
7

---

Published as a conference paper at ICLR 2020
50
0
40
0.5
m 0.5
30
1/4n
20
20
10
10
10 20 30
40
50
60
Figure Stability threshold improved when increasing momentum parameter, when using shifted momentum: (left) For different values of momentum m, we examine the relation between 1 and an L for which the maximal roots of eq. i on the unit circle. obtained by numerically evaluating the value of en With shifted momentum, we maintain stability threshold. (right) evaluate empirically the relation depicted the Ieft panel by training, with shifted momentum, a fully connected model with MNIST. The markers are empirically evaluated, and the solid lines are qelincar fit to the markers.
Table 1: Validation accuracy results, SB/L.B represent small and large batch respectively with r = 0. ASGD is asynchronous training with r = 32, +LR stands for ASGD with our linear scaling, and +30% is also with additional 30% epochs budget.
Network
Dataset
SB
LB
ASGD
+LR
+30%
Resnet44 (He al.
2016)
Cifar10
92.87%
90.42%
10.0%
88.57%
91.65%
VGGI1 Simonyan & Zisserman
2014)
Cifar10
89.8%
84.55%
10.0%
61.41%
84.74%
C3 (Keskar et al. 2016)
Cifar100
60.0%
57.89%
1.0%
54.02%
58.94%
WResnellb-4 ( Lagoruyko & Komodakis 2016
Cifar100
76.78%
72.85%
17.8%
70.35%
73.81%
ImageNet. We next experiment with ResNet50 and ImageNet, which is popular benchmark for large batch and asynchronous training because of its complexity and scale, Our focus is asynchronous centralized training with high delay. To the best of our knowledge, the generalization gap is not closed yet in this setting. This is an important setting because of its simplicity and scalability potential. Optimization details can be found in appendix 1
In Fig. we compare three A-SGD optimizations trained with ImageNet. As can be seen in the figure, the generalization gap decreases from 4.33% to 1.69%. just by turning off momentum. This corresponds with our analysis and previous results about the relation between momentum and delay. Shifted momentum similarly improves generalization, our analysis on the beneficial role the momentum parameter has, using shifted momentum. The learning rate is first scaled linearly with the total batch size of all the workers, in Goyal al.) (2017). Our inverse linear scaling with delay cancels this increase, and we get similar learning rate as in regular small batch training. In contrast, when scaled the learning rate with 1/VF, training did not converge at all.
be seen in the right panel. This validates
DISCUSSION
fundamental problem with asynchronous training that seems to cause degrada- tion in generalization, even after training has converged to steady state. Identifying the root of this problem and resolving is essential order to scale parallelism. When approaching this problem, need to address two issues. First, what is the origin of this generalization gap? Second, how can we decrease this generalization gap?
Motivation.
Conclusions. Our work tackles both questions by studying the behaviour of A-SGD and the relation between the delay and the hyperparameters, e.g., the learning rate and momentum. We analyze A-SGD from the theoretical perspective of dynamical stability. We find that a linear connection between the inverse learning rate and delay is necessary in order to keep the set of accessible minima
8

---

Published as a conference paper at ICLR 2020
100
100
100
S-56D
SDGGD A-SGD, m-O
5-86D
A-SCD, m-0.9
80
80
A-SCD +SM, m-0.9
Envo %
Error %
Ervo %
60
60
60
40
40
20
20
20
20
40
60
80
0
40 Epochs
80
20
40
60
80
Epochs
Epochs
Figure 5: ResNet50 ImageNet asynchronous training. The baseline (in blue, S-SGD) is large batch synchronous training. following Goyal et al. (2017), where 1) x batch size. For A AGD, based on our analysis, we additionally change 1 x 1/T (in contrast, 7j x I/vT does not converge at all). Thus, in this case, we get the same learning rate as in a small batch regime. We compare three A-SGD options (in orange): (1) with standard 0; and (3) with shifted momentum. S-SGD validation final error
momentum (2) with momentum value is 23.8%. A-SGD achieves 28.13% when training with standard momentum (left). The error drops 25, 25.49% when turning off momentum (middle). With shifted momentum. error is similar, 25.4% (right). This matches the analysis in section 2.2.2 Solid lines are validation error and dashed lines are train error.
the same. In addition, we find how momentum affects the accessible minima set. Our analysis suggests that, when increasing delay, momentum degrades stability. Therefore, it should be turned off in order to maintain performance, as was previously observed empirically (Mithagkas et al. 2017; Dai et al.) 2018 [iu et al., 2018). However, we observe that momentum can have some benefits in improving convergence stability without delay. To maintain these benefits, we propose to modify momentum into method called shifted momentum. We supply theoretical analysis of A-SGI) with shifted momentum and conclude that, in contrast to regular momentum, this method improves stability when delay is increased. In addition, we supply empirical evidence support these findings. Lastly, we demonstrate, these findings can improve the generalization performance of distributed training algorithms and bring us one step closer to closing the generalization gap.
Future Directions. It interesting to examine how the dynamical stability analysis holds during training. Specifically, what implications can we derive from the analysis, before we reach the steady state (e.g.. minimum of the loss), given a tight epochs budget. Our empirical findings in this case (Fig. [3] suggest that the optimal learning rate chosen for the steady state may remain optimal during the convergence process. This might be because the hyperparameters at the stability threshold are closely related to the hyperparameters that achieve the optimal convergence speed to that minimum. For example, GD it easy to show that V/hreshold = 2/ooptmma- Therefore, both stability and convergence rate may be optimally maintained using similar scaling relations in the hyperparameters. This is an interesting question for future study.
Another interesting question for future study is to understand how the stability conditions change when some synchronization is introduced. Several practical A-SGD methods use synchronization to some extent, e.g. (Assran et al., 2019 Chen et al. 2016). For synchronization methods that reduce the delay in expectation, we can intuitively expect an improvement in dynamical stability, from our analysis of stochastic delay (appendix C However, further analysis of the stability method for each method is required for an exact answer.
Answering these questions may lead to more precise understanding of the trade-off's between S-SGD and the various A-SGD methods.
REFERENCES
Dario Amodei and Danny Hernandez. Ai and compute.
Ittps://qpenai.com www.://pee......coo.o././.ooooma
ai Bi-and--a computet 2018. Accessed: 2019-05-23.
Yossi Arjevani, Ohad Shamir, and Nathan Srebro. Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates. jun 2018.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael Rabbat, Stochastic Gradient Push for Distributed Deep Learning. 2019.

---

Published as a conference paper at ICLR 2020
Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting distributed synchronous sgd. arXiv preprint arXiv: 1604.0098, 2016.
Wei Dai, Yi Zhou, Nanqing Dong, Hao Zhang, and Eric Xing. Toward Understanding the Impact of Staleness in Distributed Machine Learning, sep 2018.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior, Paul Tucker, Ke Yang. and Quoc V Le. Large scale distributed deep networks. Advances in Neural Information Processing Systems, pp. 1223 1231, 2012.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEF Conference on, pp. 248-255. leee, 2009.
Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, and Priya Nagpurkar. Slow and Trade-offs in Distributed SGD. mar 2018.
Stale Gradients Can Win the Race:
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: 706.02677, 2017.
Ido Hakimi, Saar Barkai, Moshe Gabel, and Assaf Schuster. Taming Momentum in a Distributed Asynchronous Environment. 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. NIPS, pp. 1731-1741, 2017.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima. sep 2016.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Yann Lecun, Leon Bottou, Yoshua Bengio, and Patrick Ha. Gradient-Based Learning Applied to Document Recognition. 1 1-tr)::::44: 1-46, 1998.
Yann A LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Roben Müller. Efficient backprop. In Neural networks: Tricks of the trade, pp. 9-48. Springer, 2012.
Mu Li. Scaling Distributed Machine Learning with the Parameter Server. Proceedings of the 2014 International Conference Big Data Science and Computing BigDataScience '14, pp. 1-1, 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, Huan Zhang, Cho-Jui Hsieh, Yijun Huang, and Liu. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first-order. In Advances in Neural Information Processing Systems. pp. 0054-3062, 2016.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. arXiv preprint arXiv: 17l010692.. 2017.
Tianyi Liu, Shiyang Li, Jianping Shi, Enlu Zhou, and Tuo Zhao. Towards understanding acceleration tradeoff between momentum and asynchrony in nonconvex stochastic optimization. In Advances in Neural Information Processing Systems, pp. 3686-3696. 2018.
Ioannis Mitliagkas, Ce Zhang, Stefan Hadjis, and Christopher Re. Asynchrony begets momentum, with an application to deep learning. 54th Anmual Allerton Conference on Communication, Control, and Computing, Allerton 2016, pp. 997-1004, 2017.
10

---

Published as a conference paper at ICLR 2020
Kamil Nar and S Shankar Sastry. Step Size Matters in Deep Learning. In NIPS, 2018.
Alan V Oppenheim. Discrete-time signal processing. Pearson Education India, 1999.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach parallelizing stochastic gradient descent. In Advances in neural information processing systems, pp. 693-701, 2011.
Christopher Shallue, Jaehoon Lee, Joe Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George Dahl. Mcasuring the effects of data parallelism neural network training. arXiv preprint arXiv:1811.03600, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint urXiv::409: 1556, 2014.
Lei Wu, Chao Ma, and Weinan E. How SGD Selects the Global Minima in Over-parameterizee Learning: A Dynamical Stability Perspective. In NIPS, 2018.
Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic momentum methods for deep learning. arXiv preprint arXiv: 1808. 10396, 2018.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv:1605.00) 146, 2016.
Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness aware async-sgd for distributed deep learning, arXiv preprint arXiv: 151100550, 2015.

---

Published as a conference paper at ICLR 2020
Appendix
A STABILITY ANALYSIS FOR EQ- 2
In this section, we would like to analyze the stability of eq. 2 In particular, we would like to examine if given minimum point x" is stable. To analyze this suppose minimum point x", which implies Vx(x*) = O, and ask whether or not we can converge to x" using the theory of dynamical stability. Formally, consider the linearized dynamics around x":
in a vicinity of some
X++1 = Xx 17 ([G((""mTrr)) + VG (x-)) (xt-r - x"))
where we denoted G(x;;m)) Sn, (xx) and changed the notation of the time index in n(() the subscript, i.c., 72z
Examining the expectation of this equation obtain
N
Ex++1 Ext
;(x";t)+
V (x";)) (Exi-r xx)
N
Ex,- 7 (Exi-r x')
where in (1) we used 4k-
1, I,.., N Pr(nt = k) = N and in (2) we used the fact that x" is
minimum point and thus
G( vx(x*) 0 and denoted H
N Σ vG(x":1)
fi(x*)
Using S Ex,- x" variable change we obtain
81+1 = 8, -
(12)
From the Spectral Factorization Theorem we write H = UAUT where U is orthogonal matrix and = diag(a) (l,,..., Un) a diagonal matrix. Substituting this into eq. 12 we obtain:
8 8; UAU St
Multiplying the last equation with U from the left, denoting s, = UT St, and using the fact that U is an orthogonal matrix, i.c., U we get:
5 = 6, 7
Recall that A diag(a) .... aN) ) is diagonal matrix. Therefore, analyzing the dynamics of the last equation is equivalent to analyzing the dynamics of the following N one-dimensional equations:
Vi L....N i1) (i) na,
where si (i) denotes the 7thh component of the vector 8t-
In order to ensure stability of the N-dimensional dynamical system, it's sufficient to require that 5 (1) = (1) na ( where we assume without loss of generality i is the first one that loses stability.
(13)
02 2 ... 2 This is true since the dynamics for
To simplify notations we define x, (1) and the sharpness term a Amax (H), the maximal singular value of H. Using these notations, we can re-write eq. 13 as:
Lt+1 Zt njT,,- + Ie+1 2, ma., 0.
(14)
Since this is linear time invariant difference equation, of order r + 1, its solution is, generically:
c
where o are determined by the initial conditions, and 2, are the roots of the characteristic equation of eq. 14 To find this characteristic equation, substitute xi zt into eq. 14 and obtain
[+1 z' + nazt = 0 + ++ 2 + na =
Note that for xt O, it is required that Vi, | 1.
12

---

Published as a conference paper at ICLR 2020
B FINDING THE CONDITION FOR THE MAXIMAL ROOT OF THE CHARACTERISTIC EQUATION (EQ. TO BE ON THE UNIT CIRCLE
To simplify the notation, we denote am) Recall the characteristic eq. (eq. 5
2 ++ + a 0.
Since we are looking for solution on the unit circle we substitute 2 = e0 into the equation where i is the unit imaginary number and 0 is some angle. We obtain:
c0((++) eT =a=
Using e0 (0) (i) get
cos (#(T + 1)) i ssn (0(T + 1)) (cos (fT) + i (0r)) + = 0
cos (0(r + 1)) cos (0T) sinn (0(T + 1)) sin (0r) = 0
Using trigonometric product-sum identities we obtain
2 sin
0(27+1) 2 sin (g) + a =
(15)
cos
012++1) 2
sin
If sin (2) = O then we get from the first equation a O. This is contradiction since we assume
that O. Thus, sin (2) O. This implies from the second equation in eq. that
cos ((2T + 1)
0(2r + 1)
2 + æk for 0, 1,... 27
2
2
Substituting this result into the first equation in eq. 15 and using >> O obtain that the possible solutions must satisfy
(1
4
a sin
for 0, I....
4T +
Also, since sin (a)) = sin(T - x) we can eliminate symmetric solution and get
(1 + 4k:)
sin
for i: 0, 1,...,
4T +
> 0 monotonically increasing with k. Since the magnitude of the characteristic equation increases with a and we are interested in the maximal root we are looking for the minimal a value. This value corresponds to Thus, the maximal root satisfies:
Note that for h = 0,1,..,, - J:
(1+1k)m
< 2 and thus sin (1+-4k)m 4r+2
4r42
π
sin
4T
C STABILITY ANALYSIS FOR EQ. 2 WITH STOCHASTIC DELAY
We assume that (t)) is drawn from some distribution. this section, we would like to analyze the stability of eq. [ In partieular, we would like to examine if given minimum point x* is stable. To analyze this we suppose we are in a vicinity of some minimum point x", which implies Vf((*) = 0, and ask whether not we can converge to x" using the theory of dynamical stability. Formally, consider the linearized dynamics around x":
X = X; 17 (G(x": [0((x*)meep 74-)()) + VG (x;;)))))))) (x+-7(0) - -x"))
where we denoted G(x;n)) = V V.n, (x,) and changed the notation of the time index in nt) to the subscript, i.e., f4.-
13

---

Published as a conference paper at ICLR 2020
numeric solution analytic approcinaation
20
1/o0
10
10
20
30
Figure is necessary keep the learning rate inversely proportional to the delay to maintain stability. In blue we see the relation between 1. and obtained by numerically evaluating the value any
of 1 for which the maximal root of eq. 5 is on the unit circle. In orange we see the analytic an approximation az 1 (2r + 1). We can see that in order maintain stability for given minimum point, the delay increases need to decrease the learning rate 7) keep 7) inversely proportional to r. In appendix (Fig. [Op we show that with momentum, we also get similar linear relation, only with higher slope.
Examining the expectation of this equation we obtain
N Σ
Ex++1
Ex,-
G(X*:1)
+ N Σ (x(::))
Σ b
Ex Pr(T(t)= =k) -x)-xx) -x))
N i=1
Ex:
H
Σ Pr(((t)= k) (Ext- - xx))
where in (1) we used and Ak = 1, I,..,N N: Pr(n: = k) = N and in (2) we used the fact that x"
is minimum point and thus Σ ((x":1)= = fx(x") = 0 and denoted H vG(x::1)
V fi(x*).
Using S; = Ex, x" variable change we obtain
S;11 5; nH Σ Pr(r(t) k)s
(16)
From the Spectral Factorization Theorem we can write H = UAUT where is an orthogonal matrix and diag(a), (01, (n)) is diagonal matrix. Substituting this into eq. 16 we obtain:
S St nUA Σ Pr(r(()= k) S
Multiplying the last equation with T from the left, denoting s. U st, and using the fact that U an orthogonal matrix, i.c., U U we get:
8 6; n Σ Pr(T(() = k)
Recall that A = (iag((a,, ..., aN) is diagonal matrix. Therefore, analyzing the dynamics of the last equation equivalent to analyzing the dynamics of the following one-dimensional equations:
Vi = 1,..N S
S
1704 Σ Pr(((t) 8)8,-
where (i) denotes the tth component of the vector st-
14

---

Published as a conference paper at ICLR 2020
In order to ensure stability of the N-dimensional dynamical system, it's sufficient require that
S (1) = (1) !lli Pr(T(()) - (1),
(17)
where we assume without loss of generality 2 02 2 ... 2 aN. This true since the dynamics for i is the first one that loses stability.
To simplify notations we define z; = (1) and the sharpness term a = d1 = Amax (H), the maximal
singular value of H. Using these notations, we re-write eq. 13 as:
Σ Pr(r(t) = 1=)== + r++1 - Zz + Pr(T(t) = k)x1= =0 (18)
2++1 Zt
k
&
The characteristic equation of eq. 18 is
2 + Tja
Pr(t(1)= = --)=
(19)
C.I STABILIY ANALYSIS
We would like find conditions when and how can we change the hyperparameters (n, ET) to maintain the same stability criterion (definition D In order to analyze stability we examine the characteristic equation in eq. 18 and ask: when does the maximal root of this polynomial have unit magnitude?
1. I ~ unif(a, b):
2 1 + naa
2
(20)
m
k=
14
12
10
1/ar
10
15
20
25
30
ET
Figure unif(a, 63 where and b an integer in the range [1, 64]. In this case, ET a+b We see the relation between on and Er obtained by numerically evaluating the value of 1 for which the maximal root of eq. 20 on the unit circle. We can see that order to maintain stability for given minimum point, as the delay expectation Er increases need to decrease the learning rate to keep inversely proportional to т.
2. Gaussian distribution discrete approximation: Vy, Vk: 1,.... 2p Pr(r = k) Pr
0.5 < z S k 0.5) where z ~ N(u, 1):
15

---

Published as a conference paper at ICLR 2020
20
15
1/
10
5
10
15
20
25
30
ET
Figure Vj,, Vk = I,.,,, 2/ : Pr(r - k) = Pr(k 0.5 S z S 0.5) where N(u, 1) and j is an integer in the range [1, 30). In this case, Er μu. We see the relation between 1 and Er obtained by numerically evaluating the value
ar
for which the maximal root eq. 19 on the unit circle. We can see that in order to maintain stability for a given minimum point, as the delay expectation Er increases we need decrease the learning rate 77 to keep 77 inversely proportional to
100
Normal Distrioutoon
80
Eror %
60
40
0
40 Epochs
Figure 9; Gaussian distribution of delay. Comparison of ResNet50 trained asynchronously on ImageNet with two types of delay distributions: constant i.e., round robin (orange) and discrete Gaussian distribution (blue). Constant distribution reaches 25.4% validation error while Gaussian distriution reaches similar error of 25.3%.
16

---

Published as a conference paper at ICLR 2020
D THEORETICAL ANALYSIS WITH MOMENTUM
In this section, we repeat the steps of the analysis in section for A-SGD with momentum.
D.1 PRELIMINARIES AND PROBLEM SETUP
Consider the problem of minimizing the empirical loss
f(x) Σ f((x,,
(21)
where N is the number of samples, x E Rd and Vi 1.... N: J Rd + twice continuously
differentiable function. The update rule for minimizing ((x) in eq. 21 using asynchronous stochastic
gradient descent with momentum (A-MSGD) is given by
V++1 mv, 17 m) G(x
X++1 = + Vi+1
or
X++1 X, x,-1) (1 m.) G(x1-rint-))
(22)
where m is the momentum, 17 is the learning rate, Gix;; n4) = V Sn, (xx), n, is random selection process of sample from 2.. NN at iteration f, and some delay due the asynchronous nature of our training.
Our main goal is understanding how different factors such as the gradient staleness т, and hyperpa- rameters such as the momentum m and learning rate affect the minima selection process in neural networks. In other words, we would like to understand how the different hyperparameters interact to divide the global minima of our network to two sets: those converge to.
converge to and those we cannot
To analyze this suppose we in vicinity of minimum point x", which implies fx(")) 0, and ask whether or not we can converge to x" using the theory of dynamical stability. Formally, consider the linearized dynamics around some minimum point x":
X++1 = + m (x: x;-1) 77 (1 (1- m) (G(x"; ;n--r) + VG (x";m+r)) (Xi-r x'))
Examining the first moment of this equation we obtain
1 Σ G(X)))
N
1 N
Ex,+1 = Ex, + m (Ex; Ex,-1) - - m))
VG VG (x";1) (Ext-r -xx)
Ex, m (Ex; Ex.-1) )) - 17 m)) H (Exirr x*),
N
where N Σ G(x";1) # [ = 0 since x a minimum point and H
N Σ VG(x":1)
2 [((x))
Using S; = Ex; x" variable change we obtain
8 = S; + m (St - St-1) - 17 (1 - m) Hs
(23)
From the Spectral Factorization Theorem matrix and = diag(a; (11, .... (n)) a diagonal matrix. Substituting this into eq. 23 we obtain:
write H = UDUT where U is orthogonal
S = St + m (8t st-1) - (1 - m) UAUT St
Multiplying the last equation with UT from the left, denoting s, = UT st, and using the fact that U an orthogonal matrix, i.e., U we get:
s S, m (5+ 5 -n (1 m) A.,
17

---

Published as a conference paper at ICLR 2020
Recall that A diag( (11 .... oN) is diagonal matrix. Therefore, analyzing the dynamics of the last equation is equivalent to analyzing the dynamics of the following N one dimeeniinii equations:
= I....N (t) = še(i) + m (Sc(i) - 17 (1 m) (
where s, (i) denotes the hhh component of the vector St-
In order to ensure stability of the N d-dimensiionll dynamical system, it's sufficient require that m) a1);-
$ (1) (1) (1) 5, 1
(24)
where assume without loss of generality a1 the first one that loses stability.
02 2 oN. This true since the dynamics for
To simplify notations define 2, = (1) and the sharpness term di Amax (H), the maximal singular value of H. Using these notations, we can re-write eq. 24 as:
Fr++ 2t + m (xe xz- (1 m) 0'0i +
1t+1 (m 1) xt m + m) a-t 0. The characteristic equation this difference equation
(25)
(1 + m) x" + m²² 7) (1 m) a 0.
(26)
D.2 STABILITY ANALYSIS
We would like to find conditions on when and how can we change the hyperparameters (m, 77, T) to maintain the same stability criterion (definition [ In order analyze stability we examine the characteristic equation in eq. [6]and ask: when does the maximal root of this polynomial have unit magnitude?
D.2.1 THE INTERACTION BETWEEN LEARNING RATE, DELAY, AND MOMENTUM
For the general case and different values of momentum, evaluate numerically the value of - for ar which the maximal root of the general characteristic equation (eq. 26 is on the unit circle, i.e., when are the threshold of stability. We show the results in Fig. T0 We observe that there is still an inverse relation between the learning rate and delay when using momentum. Specifically, we observe that:
1. We need to decrease the learning rate as the delay increases.
2. The lines becomes more steep for larger values of momentum. This implies that, for a given delay, maintaining stability for larger values of momentum requires smaller learning rate. Therefore, it is casier to maintain stability with m
D.3 SHIFTED MOMENTUM
In this section, repeat the steps of the analysis in section D.I for A-SGD with shifted momentum. The update rule for minimizing f(x) in eq. 21 using asynchronous stochastic gradient descent with shifted momentum is given by
Vt+1 MV 1 (1 m) (x((-r((X(+)))
X++1 X, +
X++1 X2 MV
m) V fn(ttr)
Xx m (X,-, X1-
m) (x(--r
Following the same steps as in section D.I we obtain the following mie-dimensional equation:
E++1 2z (x) Ft- 17 (1 m) aI
++ - 5t + (n(1 m)a m) + 17.7-7-111 = 0.
The last equation characteristic equation is:
++2 +1 + (7(1 - m)a - m)mmmmm= + m = 0.
18

---

Published as a conference paper at ICLR 2020
35
m
0
30
m 0.1
m
25
m 0.9
m 0.99
m 0.999
1fon
20
15
10
10
15
20
30
35
Figure 10: Using (standard) momentum, is still necessary to keep the learning rate inversely proportional to the delay to maintain stability. For different values of momentum m, examine the relation between
and obtained by numerically evaluating the value 1 for which the maximal root of eq- 25 is on the unit circle. Similar to the results with m = O, we can see that maintaining stability requires to keep the learning rate y inversely proportional to the delay
100
100
A- SGD, m=0.9
A- AGDG, m= A-SGD,
A-SGD,
80
A-SGD 4SM, m=0.9
80
A-SGD +SM, m=0.9
Train Enor %
Test, Test, Eroor %
60
60
40
40
20
0
0.
0
100
200
300
400
500
100
200
300
400
500
Epochs
Epochs
Figure 11: Shifted momentum improves stability. ResNer44 trained with CIFAR10 with same pepraaarameters and three training algorithms: A-SGD with momentum (red), A-SGD without momentum (Orange) and A-SGD with shifted momentum (Blue). We observed "spikes" in the training error that appear when training with large batch size or with delay for large number of epochs, without decreasing the learning rate. While momentum negates these "spikes" in large batch training, Shifted momentum improves the convergence stability of the model and negates these "spikes" when training with delay.
E EXPERIMENTS DETAILS
We experimented with a set of popular classification tasks: MNIST (Lecun et al. 1998). CIFAR1O 10, CIFAR100 (Krizheskyy) 2009) and ImageNet (Deng al., 2009). order incorporate delay the experiments, we keep replicas of the model parameters and perform SGD step with different replica at a time according to round robin scheduling. The implementation done with PyTorch framework. Section
C in the appendix shows that constant delay, i.c., round robin, acts similarly in terms of stability to several other delay distributions. In addition, Zhang et al. (2015) shows empirically with realistic distribution that constant delay distribution is good model for delay distribution. Fig. shows empirically that round robin scheduling works a similar way to discrete Gaussian distribtion.
Although stochastic gradient descent with momentum originally introduced with the dampening term, many drop the latter when using momentum SGD. This is true for most DNN frameworks like Caffe, PyTorch, and TensorFlow where the dampening term is set to by default. As Shallue et al.
19

---

Published as a conference paper at ICLR 2020
(2118): Yan al. (0018) pointed out, without dampening, the momentum scales the learning rate that the effective learning rate Ae is equal to / I-m after sufficiently many iterations T (i.e., when T + 20). Because we alter the momentum value in our experiments, we use dampening and scale the learning rate accordingly to keep the effective learning rate the same without dampening.
E.1 IMAGENET OPTIMIZATION DETAILS
Our baseline Goyal et al. (017)) large hatch training. They trained ResNet50 for 90 epochs with a large batch of 8192 samples and reached the same accuracy level of 23.8% the small batch training. They used linear scaling with the batch size (scaling the learning rate by the large batch size divided by the baseline batch size) and a warm-up of the learning rate the first epochs. We use 32 workers, each with minibatch size of 256.
F MINIMA STABILITY EXPERIMENTS
In this section, we provide additional details about the minima stability experiment presented in section 3 As discussed in section 3 we are interested to examine for which pairs of (r, v)) the minima stability remains the same.
In Fig. 12 we show the validation error of such (r, 71) pairs function of epochs. We note that these graphs the same experiment as in Fig. As can be seen, for larger learning rates, it takes less epochs to leave the minimum. It is interesting to see that after leaving the minimum, the A-SGD algorithm converges again to minimum with generalization good as the baseline (at 7 0). This suggests that the minima selection process of A-SGD is affected by the whole optimization path. In other words, suppose start the optimization from minimum with good generalization (since was selected using optimization with r O), and then it becomes unstable due to a change in the values of (1), 7), in this experiment. These results in Fig. 12 suggest typically converge to stable minimum with similar generalization properties, possibly nearby the original minimum. start to train from scratch using the same (17, r) pair which lost stability in our experiment, we typically get generalization gap (as observed in our experiments), which suggests the optimization path might have taken very different path from the start, leading other regions with worse generalization than the original minimum.
In contrast,
G ADDITIONAL EXPERIMENTS
We examine what generalization performance we can expect during training, before reaching minimum. We do so by using the same experiment Fig. We sample the validation error each learning rate at different epochs. Results are presented in Fig. [3] Using our suggested learning rate modification (dividing the baseline large batch learning rate by the delay) gives the near optimal learning rate that can be seen in the figure.
20

---

Published as a conference paper at ICLR 2020
7=64
r=32
100
100
y=0.0
0000
7-0.017
2-0.03
80
7-0.015
80
7=0.0
0044
=00022
60
0.355
60
-=0.026
Enor %
7-0 0125
Enor %
2- 0.025
40
40
20
20
1.01
1.02
1.03
1.04
1.05
1.01
1.02
1.03
1.01
1.05
Epochs
x10
Epochs
y=16
y=8
100
100
-00.08
0.15
y=0.0
0014
80
y=0.06
80
-0.13
gm0.05 0.055
0
Bror %
60
-00.55
y=0.05
Error %
60
9=0.1
0.11
40
40
20
20
1
1.01
1.02
1.03
1.04
1.05
1.01
1.02
1.03
1.04
1.05
Epochs
x10
Epochs
10
Figure 12: Learning rates larger than 0.8/ diverge from the minimum. We show the validation error Vs. epochs for different delay and learning rate values. The baseline learning rate used 0.8 according to large batch training Hoffer et al. (2017). The minimum learning rate for each 7 is the stability threshold.
2
1.8
Validation Error %
1.6
1.4
1.2
800 epochs
500 spochs
200 spochs
100 epochs
0.8
0
0.01
0.02
0.03
0.04
0.05
Learning Rate
Figure 13: Impact of learning rate and delay on generalization error during training. Validation error with delay (T = 32) as function of learning rate at different epochs. The optimal learning rate of 1) 0.01 chosen found in the scan (which matches our proposed learning rate scaling), stays the same throughout the training. This might suggest why it's beneficial to use the optimal hyperparameters for the minimum, even when the algorithm hasn't 't converged to the steady state yet. CNN trained with MNIST, same settings as in Fig
21


Reviews:
[{"review_id": "SyeTfjp3YH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 authors model A-SGD as a dynamical system, where parameters are updated with delayed gradients. The authors analyze the stability of this system, and they first derive that the learning rate must scale linearly with the inverse of the delay around a minimum to remain stable. Using a similar analysis they show that the standard way of incorporating momentum into A-SGD requires small learning rates for high momentum values, and they propose \"shifted momentum,\" which allows for stability under higher momentum values. Experimentally, the authors show that around minima the learning rate needed to retain stability scales linearly with the inverse of the delay, that there appears to be an analogous threshold when training models from scratch, that shifted momentum allows for higher momentum values, and finally that on several datasets A-SGD with an appropriate learning rate is able to generalize at least as well as large batch synchronous training.\n\nThis is a nice paper with a large number of interesting theoretical and experimental results, and I believe it should be accepted. I think there are some largely presentational issues that should be addressed, however:\n\n- I think the authors should attempt to make a stronger case for the practical implications of their analysis: in particular, in the most practical setting (where we don't have a minimum obtained from synchronous training), what does the provided analysis allow us to do? Part of this might involve being more explicit about the results in Table 1: what exactly was the procedure for selecting the learning rates? Is it meaningfully different than just lowering the learning rate?\n\n- Equation (3) is rather obscure without the Appendix, especially since unbolded x hasn't been introduced anywhere. I think the authors should try to convey more of what's going on in this equation in the main text.\n\nMinor: 'looses' should be 'loses' throughout, and it might be good to include a conclusion section. ", "extra_scores": {"experience_assessment": "I have read many 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": "SkgYLuIwjr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 studies how asynchrony affects model training by investigating dynamic stability of minimum points that A-SGD can access. They point out that not all local minimum points are accessible, and asynchrony can affect which minimum points can be accessed, and thus helps to explain why models trained by A-SGD have higher generalization gap. The authors also propose shifted-momentum that utilize momentum for asynchronous training.\n\nOverall, this paper provides nice insights and thorough theoretical analysis. Experiments are carefully designed to validate their results. I think this paper is well written and its novelty is significant.\n\nStrength:\n- Theoretical formulation and analysis in this paper is nice and elegant.\n- Provide theoretical insights of A-SGD with momentum, which is important.\n- Experiments of minima selection are carefully designed. I like the idea to observe trajectories ``leaving minimum''.\n\nSome quick questions:\n- In Fig. 3, we can clearly see a threshold of \\eta. I notice that when \\tau=16 the fluctuation is more significant than other three cases. Can you explain why this appears?\n- In Sec. 3.1, do you consider any kind of learning rate scheduling to change learning rate over epochs, like you did in Sec. 3.2?\n- It would be great to evaluate on more tasks, as it has been shown that some may be more robust than others (Dai et al., 2019).\n\nWei Dai, Yi Zhou, Nanqing Dong, Hao Zhang, and Eric Xing. Toward Understanding the Impact of Staleness in Distributed Machine Learning. In Proc. International Conference on Learning Representations (ICLR), 2019.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxe-k_0Kr", "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": "The authors introduce a theoretical model for delayed gradients in asynchronous training. It is a very nice model and solving the corresponding differential equation allows to study its stability. Authors derive stability bounds for pure SGD (learning rate needs to decrease with delay) and for SGD with momentum, where they introduce a nice momentum formulation that improves stability. These are nice insights and good results and they are validated by experiments. More experiments and practical analysis would be welcome though. Some example questions: would introducing some sychronization help? Is the lower learning rate hurting training speed when measures as wall-clock time to accuracy?\n\nI am very grateful for the authors' response. It would still be good to see more experiments, but I hope this paper gets accepted.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "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_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of training neural networks asynchronously, and the gap in generalization due to different local minima being accessible with different delays. The authors derive a theoretical model for the delayed gradients, which provide prescriptions for setting the learning rate and momentum.

All reviewers agreed that this a nice paper with valuable theoretical and empirical contributions.


Decision: Accept (Spotlight)