Gap-Aware Mitigation of Gradient Staleness
Authors: Saar Barkai
Ido Hakimi
Assaf Schuster
Venue:  (2020)
Keywords: distributed
asynchronous
large scale
gradient staleness
staleness penalization
sgd
deep learning
neural networks
optimization

Abstract: Cloud computing is becoming increasingly popular as a platform for distributed training of deep neural networks. Synchronous stochastic gradient descent (SSGD) suffers from substantial slowdowns due to stragglers if the environment is non-dedicated, as is common in cloud computing. Asynchronous SGD (ASGD) methods are immune to these slowdowns but are scarcely used due to gradient staleness, which encumbers the convergence process. Recent techniques have had limited success mitigating the gradient staleness when scaling up to many workers (computing nodes).  In this paper we define the Gap as a measure of gradient staleness and propose Gap-Aware (GA), a novel asynchronous-distributed method that penalizes stale gradients linearly to the Gap and performs well even when scaling to large numbers of workers. Our evaluation on the CIFAR, ImageNet, and WikiText-103 datasets shows that GA outperforms the currently acceptable gradient penalization method, in final test accuracy. We also provide convergence rate proof for GA. Despite prior beliefs, we show that if GA is applied, momentum becomes beneficial in asynchronous environments, even when the number of workers scales up.

Published as a conference paper at ICLR 2020
GAP-AWARE MITIGATION OF GRADIENT STALENESS
Saar Barkaï'
Too Hakimi'
Department of Electrical Engineering
Department of Computer Science
Technion Israel Institute of Technology Haifa, Israel
Technion Israel Institute of Technology
Haifa, Israel
saarbarka i Amgall......... com
idohak im gma com
Assaf Schuster
Department of Computer Science Technion Israel Institute of Technology Haifa, Israel assa techion.ccii i1
ABSTRACT
Cloud computing is becoming increasingly popular platform for distributed training of deep neural networks. Synchronous stochastic gradient descent (SSGD) suffers from substantial slowdowns due to stragglers if the environment is non- dedicated, as common in cloud computing. Asynchronous SGD (ASGD) meth- ods are immune to these slowdowns but scarcely used due to gradient staleness, which encumbers the convergence process. Recent techniques have had limited suc- cess mitigating the gradient staleness when scaling up many workers (computing nodes). In this paper we define the Gap as measure of gradient staleness and propose Gap-Aware (GA), a novel asynchrooouu-distribueeed method that penalizes stale gradients linearly to the Gap and performs well even when scaling to large numbers of workers. Our evaluation on the CIFAR, ImageNet, and WikiText- 103 datasets shows that GA outperforms the currently acceptable gradient penalization method, in final test accuracy. We also provide convergence rate proof for GA. Despite prior belief',, we show that if GA is applied, momentum becomes beneficial in asynchronous environments, even when the number of workers scales up.
INTRODUCTION
The steady growth of deep neural networks over the years has made it impractical to train them from scratch on single worker (i.e., computational device). Distributing the computations workers can drastically reduce the training time. However, due to the sequential nature of the widely used stochastic gradient descent (SGD) method, distributing the process is not an easy task.
several
Synchronous SGD (SSGD) is the most common method used to distribute the learning process across multiple workers. Several recent works (Mikami al.) 2018 Ying et al. 2018 Yamazaki al.) 2019; Goyal et al.] 2017) have shown that SSGD can achieve large speedups while maintaining high accuracy. The major drawback of SSGD is that its speed confined to the slowest worker in every iteration. This shortcoming is magnified in non-dedicated environments such as cloud computing. For this reason, all the above mentioned works were forced to use homogeneous workers in dedicated network, which serves to reduce the variance in the workers' iteration times. Unlike cloud computing, dedicated networks are expensive and therefore not available to most users.
In asynchronous SGD (ASGD), each worker communicates independently of the others, thereby addressing the major drawback of SSGD. ASGD enjoys lincar speedup in terms of the number of workers, even non-dedicated networks. This makes ASGD potentially better alternative to SSGD when using cloud computing. Unfortunately, ASGD also has significant weakness known gradient staleness; the gradients used update the parameter server's (master) parameters
Equal contribution.
An environment of computation nodes who not specifically optimized work together

---

Published as a conference paper at ICLR 2020
often based on older parameters and therefore are inaccurate. Prior works have shown that gradient staleness severely hinders the convergence process by reaching reduced final accuracy (Chen et al. 2016: Cui et al., 2016). Mitliagkas et al. (2016) showed that gradient staleness also induces implicit momentum, thus the momentum coefficient must be decayed when scaling up the number of workers. Most research works measure the gradient staleness of worker according to the delay: the number of master updates since the worker began calculating the stochastic gradient until g is used to update the master. To overcome gradient staleness, Zhang et al. (2015b) proposed Staleness-Aware (SA), which penalizes the step size of stale gradients linearly to their delay. This method was later embraced by other works (Jiang et al. 2017: Hardy et al. 2017 Giladi et al. (2019) and is currently the common method for penalizing stale gradients. Unfortunately, this method suffers from a degradation of the final accuracy, especially when scaling up the number of workers. In Section 4.1 we show that the main reason for this degradation is the over-penalization and under-penalization caused by SA.
SSGD and ASGD rely on hyperparameter tuning for every different number of workers (Shallue et al. 2018) Tuning is extremely time-consuming, thus avoiding it is beneficial, whenever possible.
Our contribution: To mitigate gradient staleness while minimizing the degradation of final accuracy, we define a measure of gradient staleness we refer to as the Gap. The Gap is based on the difference between the parameters used to calculate the gradient and the parameters on which the gradient is applied. We propose a new method called Gap-Aware (GA) that penalizes the step size of stale gradients linearly to their Gap, while eliminating the over-penale wer-penalization or under-penalization of SA. No new hyperparameters
introduced using the GA method.
We show that GA out- SA, especially as the number of workers scales up. We prove that the convergence rate of the GA-ASGD algorithm with a non-convex loss function is consistent with SGD: O
VBK) where K is the total number of steps and B is the batch size.
We show that penalizing the gradient itself rather than the step-size, eliminates under-penand penalizpnaiiza.inn.
Our results suggest that GA can be used without re-tuning the hyperparameters.
As opposed to conclusions by Mitliagkas et al. (2016), we show that applying momentum in an asynchronous environment is advantageous (using GA), even when multiple workers are used. We combine GA with Adam (Kingma & Ba 2015) (Adam-GA), and show that Adam-GA achieves almost two orders of magnitude better perplexity than Adam Adam-SA (which combines Adam with SA) using several workers on the Transformers-Xi model.
Our results establish GA as a superior a preferable alternative to SSGD in non-dedicated networks such as cloud computing, even when scaling to large numbers of workers. To validate our claims, we performed experiments on the CIFAR10, CIFAR 100 (Krizhevsky 2012), ImageNet (Russakovsky et al. 2015). and WikiText- 103 Merity et al. 2016) datasets, using several tfat-oo--the-ane architectures. A version of GA has reached 12% final test accuracy on the ImageNet dataset using 128 simulated asynchronous workers. As far as we know, this is the largest number of asynchronous workers reported to converge on ImageNet.
option to SA and suggest that using GA is
2 RELATED WORK
Eliminating gradient staleness is a challenging task and several papers suggested techniques to reduce its detrimental effects. Zheng et al. (2017) proposed DC-ASGD, which uses a Taylor expansion to mitigate the gradient staleness. EASGD (Zhang et al.) 2015a) uses center force to pull the workers' parameters toward the master's s parameters. Both DC-ASGD and EASGD achieve high accuracy on small numbers of workers, but fall short when trained on large clusters. Chan & Lane 2014) proposed penalizing stale gradients by reducing their size and thus limiting their effect on the learning process. They suggest decaying the learning rate exponentially to the delay; this makes the step size arbitrarily small when the amount of workers grows, virtually ceasing the learning process. As part of their convergence analysis. Dutta et al. (2018) suggest penalizing method that is linear to the norm between the master and worker's 's parameters. However, their method introduces another hyperparameter, which requires additional time to tune. As opposed other methods, GA performs well even when the number of workers is large, without introducing new hyperparameters.
Gupta et al. (2016) well as Aji & Heafield (2019) suggest collecting several gradients before updating the master to reduce the effects of gradient staleness. |Wen et al.) (2017) propose minimizing the size of the gradients to reduce communication times. GA is orthogonal to both of these approaches.
2

---

Published as a conference paper at ICLR 2020
3 BACKGROUND
The goal of an optimization procedure is to minimize f(0), where ff is a smooth, but not necessarily convex, objective function (a.k.a. loss) and the vector 8 IR is the model's parameters:
0. arg min 1(0) B<((((E) dERa
(1)
where & E E is random variable from E. the entire set of training samples E E)0:E) is the stochastic loss function with respect to the training sample indexed by &. SGD is commonly the workhorse behind the optimization of deep neural networks. Denoting 1) the learning rate and as the step number, SGD's iterative update rule is: 0x+1 = 02 7) V ffx)). We denote X as the variable X the 1tth step, where is any variable.
Momentum Momentum (Polyak
1964) is a widely adopted optimization technique due to its
accelerated convergence and oscillation reduction (Sutskever et al. 2013). Instead of simply using the gradient, the momentum iterative update rule uses an exponentially-weigtees moving average of gradients called the update vector: Uk+1 = -Yu V f(x).. The update rule is: 0k+1 02 +
Nesterov's 's Accelerated Gradient (NAG) (Nesterov 1983) a well-used variation of momentum that
has been proven to achieve quadratic speedup in convergence rate compared to SGD.
ASYNCHRONOUS SGD (ASGD)
We consider the commonly used ASGD, which operates with a parameter-server (master), used to keep the model's most up-to-date parameters. Each worker maintains replica of the model's parameters. The workers run in parallel and synchronize with the master independently from each other at the beginning of each batch iteration. We denote ты as the delay at the 1 step. The worker and master algorithms are given by Algorithm and respectively, where B is the batch-size and Sk.b denotes the tth sample in the batch sampled at the htth iteration. Gradient staleness appears when gradient 9% is computed on parameters 0 but applied to different parameters 0z.
Algorithm Momentum-ASGD. worker
Algorithm Momentum-ASGID master
Always do:
For = 1...K do:
Receive parameters 0ą-r, from the master
Receive gradient of from worker i
Get B training samples (L....
Update momentum uh+1 + you + gi
Compute gradient: gi +- Eb=1 b= Send of. to the master
VF (02- S k)
Update master's weights:
Bk+1 + 0₂ 7 Uk+1
Send 02+1 to worker
4.1 STALENESS-AWARE
Zhang al. 2015b) proposed a gradient penalization method called Staleness-Aware (SA). SA aims to reduce the effects of gradient staleness by dividing the step size by its corresponding (Algorithm 3). The worker algorithm remains unchanged. The two ideas behind SA that stale gradients should be penalized to reduce their impact and that gradient staleness scales with r SA successfully mitigates the gradient staleness when N is small. Although commonly used, SA can potentially over- ver-penaliiz as well as under- redaaiee stale gradients as we show below.
We consider the version of momentum without dampening
3

---

Published as a conference paper at ICLR 2020
Algorithm 3 Staleness-Aware: master
Algorithm 4 Gap-Aware: master
Initialize an iteration array: iter [0] N
For k = 1...K do:
For k 1...K do:
Receive gradient g from worker i
Receive gradient ge from worker
Calculate Gap: Gş 10 P0--0 -0
+ 1
Calculate worker i's delay < k iter(i]
Update momentum Uk+1 f- 72k + gk
Update momentum Pk+1 t- Yo +
o gk
Update master 0k+1 f 0k
2a Uk+1
Update master d + 02 V--1
78
Send 1 to worker
Save and send current parameters 8 worker
Save current iteration iter[t] + k
Over-Penalizing Let us assume that at some step after T master updates we get 0g 0 just as the gradient calculated on 0x-7 is applied. This means there is no gradient staleness for the next gradient update since it was computed using the same parameters on which Unfortunately, the delay remains > 0, thereby causing over-penalization when SA is used.
applied.
Additionally, scales linearly with N, which dramatically reduces 1j when is large. Consequently, on large numbers of workers, the convergence rate of SA is sluggish and its accuracy plummets.
Penaliinnn The SA method doesn't 't take into account that when using momentum, the update step also contains past gradients. To emphasize the importance of this issue, let's examine a fictional example: assume that some gradient gk is very stale (Ty is large). Following the SA technique, the update rule is: 0x+1 = 02 lh gradient 9ı is indeed penalized by being multiplied by 1h, which small; thus ge doesn't change the parameters much. We further assume the next iteration is very fast (Tk+1 is small). The next update li++1
TK Uk++1 0g
(yy + gk). This means the stale
will be: 0x+2 = 02+1- 1o411 u + Y9k + 9k+1). The stale gradient Jk is multiplied by 7 7741 which is large (assuming a as 7)++)). Despite the fact that 9s was stale, it still has a significant impact on the learning process. In other words, gs is mnder-penalized.
TC+1
To eliminate this possibility we penalize the stale gradient itself rather than the learning rate. Using this method, the staleness each gradient is accounted for within the update vector v.
GAP-AWARE (GA)
In this section we propose method called Gap-Aware to mitigate over and under- penalization.
5.1 THE GAP A MEASURE OF GRADIENT STALENESS
An intuitive method to measure gradient staleness would be: (
This essentially measures the difference between the stale gradient and the accurate gradient that is computed on the up-to-date parameters. (Of course, V f((0)) ) is never calculated in ASGD algorithms.) Commonly used deep learning is the Lipschitzian gradients assumption:
[ V (v)ll L| vll. Vx, Vy, L
Setting 0k, y P--T into Equation 2 get: |VV (0x) V (0k-z, )ll
L OR- ll-
This implies that ||0A - 0 is a valid (and easily calculated) measure of the gradient staleness. This measure also addresses the delay's 's over-penalization; using the same simple example described will now be zero, correctly measuring the gradient staleness.
in Section 4.1 the term 110, 0z-72
The learning rate y,, commonly decays the training progresses. This decay can be viewed built-in penalization to reduce variance. Following this notion, we suggest reducing the staleness penalization as 77 decays. To accommodate all the attributes above, we define the Gap:
Definition 1. Gk. the Gap at the 4tth step, is defined as the minimal number of updates required to traverse the current distance between the master's 's and worker's 's parameters using the maximal leamning rate and assuming all gradients have an average norm. Gj. E R is defined as:
G = 10 0 ||C
Where C = Em /
(Ox- II] is constant representing the maximal distance the parameters travel in single update, given the gradient's norm is the average gradient norm.
4

---

Published as a conference paper at ICLR 2020
Definition means that dividing li by the Gap produces larger steps than those produced by SA This allows exploring more distant minimas while still mitigating the gradient staleness. Note that E[G²] тą occurs only if all previous Tr updates were in the exact same direction, which rarely happens. Empirically, we found that E[Ga] < 7h (See Appendix C.8).
To mitigate the gradient staleness, while eliminating the over-penalization and under- sedder-pnaaiizaton,, divide the gradients themselves by their respective Gap. We refer to this method as Gap-Aware (GA).
5.2 CONVERGENCE ANALYSIS
In this section we provide the outlines of the convergence analysis. The complete proofs given in Appendix B The GA-ASGD update rule (without momentum) is:
B
0x+1 = 02 7k (
(3)
b=1
The convergence rate is the speed number of steps) at which a convergent sequence approaches its limit. We follow ideas similar to Lian et al. (2015) to show that the upper bound of the convergence rate of GA on non-convex loss function similar that of SGD.
Assumption 1.
We assume the following, commonly-used assumptions, hold:
Unbiased gradient: The stochastic gradient V (0; {) is unbiased:
( Eg V ())
(4)
Bounded variance:
The variance of the stochastic gradient is bounded:
Eg ()(( (0) I o²
v0
(5)
I Lipschitzian gradients: See Equation 2
Independence: All the random variables (ER. l.... KtbkK
1...
are independent.
Bounded age: All delay variables TI....KK are bounded:
max Tk S
(6)
Theorem 1. Assume that Assumption
holds and the learning rate sequence {mc I....
b..k satisfies:
BLT +2B
Th G
Σ
< for all k: 1,.
Gk
We have the following ergodic convergence rate for the iteration of GA-ASGD:
K
2(1(0:)-((01)
B BOBBB
====
Th GE
+ 2BL > Žj=k-7
k-1
"
Lo
Gz
Gk
Gk
Where E[-] denotes taking expectation in terms of all random variables.
To simplify the upper bound in Theorem T observed that setting the learning rate mn such that the expression ne is constant value across all & obtains the following convergence rate: G₁
Corollary 1. Assume that Assumption as follows:
holds and that me are set such that De. is constant for any Gr
f(01) f((0)
Vk [l....,K K.
(9)
G
BLKo²
the maximal delay parameter T satisfies:
4BL(T++ 1)²(f(01) f(8))
K>
(10)
o²
then the outpul of GA satisfies the following ergodic convergence rate:
EIIV (F(0.) -(0))
min kE(1.... [K)
(11)
K
BK
5

---

Published as a conference paper at ICLR 2020
Tost Erao (K6
Train Ener (%)
Gobal
0:06
"oursdar Wio
32
Workers
Workers
Figure 1: Final test and train error for different numbers of asynchronous workers N. The figure shows the average (bold line) and standard deviation (band) of 5 runs on the CIFARIU 10 dataset using the WideResNet model. The black dashed line is the SGD error using a single worker.
Corollary claims that if the total iterations is greater than O(BT)), the convergence rate achieves D(K, which is consistent with the convergence rate of ASGD presented in Lian et al. 2015 and with the convergence rate of SGD.
5.3 GAP-AWARE VERSIONS
We explore three ways to measure Ge:
Global: G3 E IR defined in Definition T
Layer-wise: Every layer is penalized differently and independently. G2 E RP where P is the number of layers the model. We denote 1 as an S-dimensional vector of ones. We denote any vector X is the pdh layer in the vector X.. Every element in G& is calculated per-layer:
G
|0p.p
02 PR-T..PlI/C + 1P
(12)
wirametterwwis:: Every parameter (element in the parameter vector 0) is penalized differently and independently. G₁ Rd where is the number of parameters. We denote - vector X, the absolute value per element of X. Every element in G3 is calculated and applied per-element:
G = 10x Ok O/-
(13)
Where C' Ed is also calculated element-wise. Specifically, C 14
We tested these variations on three different frameworks to determine which technique has the best performance. Figure demonstrates that the parameter-wise method (equation [3) resulted in the best test and train eтror. Since this phenomenon repeats across all frameworks, we henceforth use the parameter-wise method in the Gap-Aware algorithm. We denote O as an element-wise multiplication between vectors and describe the final GA algorithm of the master as Algorithm 4 The worker algorithm remains the same as in Algorithm
EXPERIMENTS
We simulated multiple distributed workers to measure the final test error, train error, and convergence speed of different cluster sizes. To validate that penalizing linearly to the Gap is the factor that leads to better performance, we used the same hyperparameters across all the tested algorithms (see Appendix C.4). These hyperparameters the authors of the respective papers for each framework. We simulated the workers' execution time using gamma--istributed model (Ali al., 2000) (see Appendix C.3), where the execution time for each individual batch was drawn from a gamma distribution. The gamma distribution is well-accepted model for task execution time, which naturally gives rise stragglers. The importance of asynchronous over synchronous training is explained in Appendix D
the tuned for single worker, suggested by
Combining GA with DANA One way to verify whether is better to penalize using the Gap or the delay, is to change the Gap while fixing the delay, and examining the results using GA and SA. Momentum generally increases the norm of the update vector; this in turn, increases the effective step size thus increasing the Gap for given delay. Hakimi al. (2019) introduced DANA, which uses the
A framework is a unique combination dataset and model. See full experiment Appendix
A worker is machine with more accelerators (i.e., GPU), ASGD methods treat each machine with multiple accelerators, all working synchronously locally, as
single worker.

---

Published as a conference paper at ICLR 2020
16:0
NAG-A5GD
45
NAG-A9GO
Test Error (%)
Gap- Aufare
Test Error (%)
15.0
DANA
DANA-EA
Test Error
DANA-SA DANA
DANA
35
DANA
DANA-SA
DANNGG
12.5
30
10.0
25
7.5
121620244 28
40
48
12 16
28 # Workers
40
12 16 24 28
40
# WWorkers
# Workers
(a) CIFARIO ResNet-20
(b) CIFARIO WideResNet
(c) CIFARI00 WideResNet
Final test error for different numbers of asynchronous workers N. Each line in the figure represents the average (bold line) and standard deviation (band) of runs on specific framework. The black dashed line represents the average result of SGD using single worker.
Figure 2:
momentum to estimate the master's parameters at the time of the gradient update, thus decreasing the Gap. The combination of decreasing the Gap using DANA and penalizing stale gradients using GA or SA is casily integrated since both methods are orthogonal. In experiments, we also compared (DANA-SA). We note that
between DANA-Gap-Awand (DANA-GA) and DANA-Staleness-- since DANA decreases the Gap, DANA-GA penalizes much less than DANA-SA (see Appendix C.8
Algorithms Our evaluations consist the following algorithms:
Baseline: Single worker with the same tuned hyperparameters in the respective framework's
paper. See Appendix C.4
ASGD: ASGD (Algorithm) without momentum (r 0).
NAG-ASGD: ASGD with momentum (Algorithm)
2 using a NAG optimizer.
Staleness-Aware SA as described Algorithm 3 using NAG optimizer.
Gap-Aware: Parameter-wise GA (Algorithm 4 as described in Section using a NAG optimizer.
DANA: DANA (Algorithm 6 as described in Appendix C.T]
DANA-SA: DANA-Staleness-Awar (Algorithm{7)
? as described in Appendix C.1
DANA-GA: DANA-Gap-Aware (Algorithm R) as deseribed in Appendix C.1
Adam: Adam (Algorithm 9 as described in Appendix[C.]]
Adam-SA: Adam-Staleness- Aware (Algorithm) 10p as described in Appendix
Adam-GA: Adam-Gap-Award (Algorithm [1] described in Appendix C.1
Our evaluation was extensive on image classification tasks such as CIFARIO, CIFAR 100 (Krizhessyy) 2012), and ImageNet (Russakovsky et al. 2015). It also included language modeling task using the WikFText- 103 corpus (Merity et al. 2016). All datasets and models are detailed Appendix C.2
6.1 EVALUATION ON CIFAR
Gradient Staleness Effects In Figure NAG-ASGD shows how gradient staleness exacerbated by momentum. NAG-ASGD yields high accuracy with few workers, but the test error climbs sharply when more than 16 workers are used. On the other hand, ASGD without momentum performs poorly using few workers. When using many workers, ASGD significantly surpasses NAG-ASGD because of the implicit momentum generated asynchronous training (Mitliagaas al. 2016).
SA & GA Figure 2lalso demonstrates that both staleness penalization methods (GA and SA) out- perform the naive NAG-ASGD. GA results better final test error than SA across all experiments. This empirically proves that GA is the better method for penalizing the gradients. We claim this occurs mainly because SA over- ever-penalizes the gradicnts, thereby making it impossible to reach any distant, good minima when the number of steps limited (for more details Appendix C.8).
DANA Versions Figure 2 shows that DANA potentially diverges when N grows as opposed to DANA-GA and DANA-SA. This shows that DANA benefits from staleness penalization. Furthermore, DANA-GA out-performs all other methods and remains close to the baseline's 's error across all frameworks. The fact that DANA-GA out-performs DANA-SA validates that GA is superior SA.
7

---

Published as a conference paper at ICLR 2020
Table
Test accuracy on different frameworks
N=32. Table 2: Final test perplexity using
Transformer-Xi on WikiText-1033 (Base-
Framework
Tuned ASGD
GA
DANA-GA
line 24.25. Lower is better).
C10
88%
87.9%
91.1%
N
Adam
Adam-SA
Adam-GA
C10 WR
91.6%
92.3%
94.3%
1644.76
1210.8 1129.9
26.48
C100 WR
71.1%
70.6%
74.3%
8
1603.01
28.7
"CI0C100=CIIAAR00000 R=ResNet, WR=
Table 3: ResNet--0 ImageNet final test accuracy (Baseline 75.64%)
N
ASGD
NAG-ASGD
SA
GA
DANA
DANA-SA
DANA-GA
32
70.53%
70.64%
61.73%
70.27%
74.89%
65.66%
75.06%
48
69.05%
66.78%
56.22%
67.75%
73.75%
61.16%
74.23%
64
67.1%
59.81 %
50.79%
64.78%
69.88%
56.98%
74.11 %
128
NaN
NaN
NaN
NaN
NaN
NaN
72.18%
Tuned ASGD To validate that the staleness penalization helps overcome the gradient staleness and improve the results, we tumed the momentum and learning rate ASGD using workers on the frameworks shown in Figure 2 For each framework, we performed grid search of 70 perturbations (See Appendix C.12). Table shows that GA and DANA-GA: using the same hyperparameters as the baseline, provide similar better results than tuning both y and 17, which is highly time-conssu cone-conuuming
According to Mitliagkas et al. (016)), momentum is used, the asynchronous implicit momentum should impede the convergence as N increases. However, GA and DANA-GA. which momentum, generally perform better than the tuned ASGD even when N large. This phenomenon repeats across all frameworks, which suggests that GA, and especially DANA-GA, can mitigate the asynchronous implicit momentum problem. Tuning these methods should further improve the results.
large
The graphs of the train error also show the concepts discussed here regarding the test error and are presented Figure 6, Appendix C.10 The convergence rate analysis appears in Appendix C.11
6.2 IMAGENET EXPERIMENTS
We conducted experiments on the ImageNet dataset using the ResNet-50 model (He et al. 2016). Every asynchronous worker is machine with 8 GPUs, so the 128 workers in experiments simulate total of 1024 GPUs. For reference, Goyal et al. (2017) used 256 GPUs synchronously. The hyperparameters we used are those of the tuned single worker (see Appendix C.4). T that GA out-performe SA due to the high number of workers, which exacerbates the over over-penalizing of SA. Unlike SA, GA out out-performs NAG-ASGD as N increases due to successful staleness mitigation. DANA-GA remains close to the baseline and better than any other method as N increases. DANA -AA reaches 72.18% final test accuracy when using 128 workers, which the most asynchronous workers shown to converge on ImageNet as far as we know.
6.3 NLP EXPPRIMENTS
NLP tasks are usually trained using Adam (Kingma & Ba) 2015). To test SA and GA we implemented a version Adam-SA SA and Adam-GA given by Algorithm 10 and II respectively (Appendix C.I). Transformer-Xi (Dai et al. 2019 is a state-of-the-an model for NLP tasks; however, its sensitivity to gradient staleness is catastrophic (Aji & Heafield 2019). Table 2 shows that GA successfully mitigates the gradient staleness and achieves mear-baseline perplexity while SA results in higher perplexity by almost two orders of magnitude. In this scenario, SA completely fails to mitigate the gradient staleness, proving the superiority of GA. (See hyperparameters in Appendix C.4
8

---

Published as a conference paper at ICLR 2020
7 CONCLUSIONS
The goal of this work is to mitigate gradient staleness, one of the main challenges of ASGD. We argue that penalizing stale gradients linearly to the delay, as done in the widely used SA method, flounders due to over and uuder-penalization and proposed GA, a novel asynchronous distributed technique that mitigates the gradient staleness by penalizing stale gradients linearly to the Gap. We showed that GA surpasses SA across all frameworks, especially in NLP problems or when the number of workers is large. This presents GA superior alternative for staleness penalizing. We further introduced DANA-GA and demonstrated that DANA-GA mitigates gradient staleness better than any of the other methods we compared. Despite prior belief, DANA-GA's superb performance enables the of momentum in asynchronous environments with many workers; it presents a desirable alternative for parallel training with multiple workers, especially non-dedicated environments such cloud computing. In future work, plan to examine what makes GA perform so well in NLP tasks.
We defined the Gap to measure gradient staleness
ACKNOWLEDGEMENT
This work was supported by The Hasso Plattner Institute.
REFERENCES
Alham Fikri Aji and Kenneth Heafield. Making asynchronous stochastic gradient descent work for
transformers. arXiv preprint arXiv: 19Xx::9906.03496 2019.
Shoukat Ali, Howard Jay Siegel, Muthucumaru Maheswaran, Sahra Ali, and Debra Hensgen. Task execution time modeling for heterogeneous computing systems. In Proceedings of the 9th Hetero- geneous Computing Workshop, HCW '00, pp. 185-199, 2000. ISBN 0-7695-0556-2.
William Chan and lan Lane. Distributed asynchronous optimization of convolutional neural networks. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting distributed synchronous sgd. arXiv preprint arXiv: 16040008,, 2016.
Henggang Cui, Hao Zhang, Gregory R Ganger, Phillip B Gibbons, and Eric P Xing. Geeps: Scalable deep learning on distributed gpus with a gpu-specialized parameter server. In Proceedings of the Eleventh European Conference on Computer Systems, pp. 4. ACM, 2016.
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime G. Carbonell, Quoc V. Le, and Ruslan Salakhutdinov. Transformer-x:: Attentive language models beyond a fixed-length context. CoRR, 0ets/9901.22660 2019. URL
/ 901. C2860
Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, and Priya Nagpurkar. Slow and stale gradicnts can win the race: Error-runtime trade-offs in distributed sgd. arXiv preprint arXhv:1803.01113. 2018
Niv Giladi, Mor Shpigel Nacson, Elad Hoffer, and Daniel Soudry. At stability's 's edge: How to adjust hyperparameters to preserve minima selection in asynchronous training of neural networks? arXiv preprint arXiv: 12340, 2019.
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch. Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training imagenet in 1 hour. CoRR, abs/1 706.02677, 2017.
Suyog Gupta, Wei Zhang, and Fei Wang. Model accuracy and runtime tradeoff in distributed deep learning: A systematic study. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 171-180. IEEE, 2016.
Ido Hakimi, Saar Barkai, Moshe Gabel, and Assaf Schuster. Taming momentum in a distributed asynchronous environment. arXiv preprint arXiv: 1612, 2019.

---

Published as a conference paper at ICLR 2020
C. Hardy, E. Le Merrer, and B. Sericola. Distributed deep learning on edge-devices, Feasibility via adaptive compression. In 2017 IEEE 16th International Symposium on Network Computing and Applications (NCA). pp. 1-8, Oct 2017. doi: 10.1109/NCA.2017..1177
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Jiawei Jiang, Bin Cui, Ce Zhang, and Lele Yu. Heterogeneity-awar distributed parameter servers. In Proceedings of the 2017 ACM International Conference on Management of Data, pp. 463-478. ACM, 2017.
Diederik Kingma and Lei Ba. J. ADAM: method for stochastic optimization. In International Conference on Learning Representations, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 05 2012.
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.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. CoRR, abs/1609.07784,, 2016. httll/ttp./aarxlv.oo///bb//////p
07843
Hiroaki Mikami, Hisahiro Suganuma, Pongsakorn U.-Chupala, Yoshiki Tanaka, and Yuichi Kageyama. Imagenet/resnet-500 training in 224 seconds. CoRR, abs/1811 105233, 2018. URLhhttp://axxi
org/abs 05233
Ioannis Mitliagkas, Ce Zhang, Stefan Hadjis, and Christopher Ré. Asynchrony begets momentum, with an application to deep lcarning. In 54th Annual Allerton Conference on Communication, Control, and Computing, pp. 997-1004, 2016.
Yurii Nesterov. A method of solving a convex programming problem with convergence rate o(1/k2). In Soviet Mathematics Doklady, volume 27, pp. 372-376, 1983.
B.T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computa- tional Mathematccs and Mathematical Physics, 4(5): 17, 1964.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael S. Bernstein, Alexander C. Berg, and Fei-Fei Li. ImageNet large scale visual recognition challenge. International Journal of Computer Vision, 115 (3):211-255 2015.
Christopher J. Shallue, Jaehoon Lee, Joseph M. Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George E. Dahl. Measuring the effects of data parallelism on neural network training. CoRR, abs/1811.036000, 2018. http:://////
htargg/bb//11110 03600
llya Sutskever, James Martens, George E. Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In Proceedings of the 30th International Conference on Machine Learning, pp. 1139-1147, 2013.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in neural information processing systems, pp. 1509-1519, 2017.
Masafumi Yamazaki, Akihiko Kasagi, Akihiro Tabuchi, Takumi Honda, Masahiro Miwa, Naoto Fukumoto, Tsuguchika Tabaru, Atsushi Ike, and Kohta Nakashima. Yet another accelerated SGD: resnet-50 training on imagenet in 74.7 seconds. CoRR, abs/1903. 2019. URL
wwwp/bs./////ooooooo//.o//eaaaee http:://rxi: wrw. abs 1903 12650
Chris Ying, Sameer Kumar, Dehao Chen, Tao Wang, and Youlong Cheng. Image classification at supercomputer scale. CoRR, abs/181 1.06992, 2018. 06992
://arxiv....a./a/ wwtp://wrr//////aeaao../..osss/t 1811
10

---

Published as a conference paper at ICLR 2020
Sixin Zhang, Anna Choromanska, and Yann LeCun. Deep learning with elastic averaging SGD. In Advances Neural Information Processing Systems 28: Anmual Conference on Neural Information Processing Systems, pp. 685-693,220 2015a.
Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness-aware async-sgd for distributed deep btattg///axxlv.org/abs//////////
learning. CoRR, 0bs/15111.0955 2015b.
05950
Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu, Zhi-Ming Ma, and Tie- Yan Liu. Asynchronous stochastic gradient descent with delay compensation, 2016.
Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu. Zhiming Ma, and Tic- Van Liu. Asynchronous stochastic gradient descent with delay compensation. In Proceedings of the 34th International Conference on Machine Learning, pp. 4129-4129, 2017.

---

Published as a conference paper at ICLR 2020
A
SOURCE CODE
The source code of -ANw-Gapp-ware provided via: DOWNLOAD
B PROOFS
Proof for Theorem
Proof. From the Lipschitzisan gradient assumption equation 2
have
f(0k+1) f(Ox) -
<Vf((k)), 0x+1 0k) + L
10 - -
n L
V((0k), TM
V F(On- OO- En-rab))
V F
Gk
2G
Bıj
m 2G
(((k));
Σ
Σ
V
(14)
Gk
Taking expectation with respect to εn.. on both sides of equation
14 we have
Eg.,. (f f(0x)
BYTk Gx
vf(ex).
1
Σ
B
B
1 + EeE
(15)
2G
where we use the unbiased stochastic gradient assumption (equation
From the fact that:
(a, b) = (aaal + ||b|1² lla - bll²)
we have
Be,, (f(x+))) -((mm)
<
[[Tf(0))11 +
1
1
B
f(O
2
vf(es)
1 B
Σ
v f((0)Tc)
2G
B
B
1 L + 2G
Egu
VF - Ea t6,
(16)
k
T2
12

---

Published as a conference paper at ICLR 2020
Next estimate the upper bound of T1 and T2. For T2 we have
27
T2 -Ba
V 10 Ek-
b=1
B
B
EE...
+
f ((k-TT))
E
-
+
B
V f(0 ((0k=Tm)) }
+ 2
b=1
B
-Eq,.
VF(00-niSt-n. -ff(a)))--
+
Σ
vf(
b=
1=1
2
13
-
-
+
Σ
V
f0kk
B
= E5s,,
-
6=
+
Σ
VV 7F 77 - VS(Ok-
1sbebsB
B
<Eer.
(5((k- (f(0k-m)))1) +
Σ vf
b=1
<Bo²
(J((k=TT))
(17)
where the fifth equality is due to
B
B
Egc. 6=
-
V f (0
h=
Ega.- (VF(0)-nitttmm))) - vf((k-T())
V ff((k-
6=1
13

---

Published as a conference paper at ICLR 2020
and the last inequality is due to the bounded variance assumption equation 5 and due to:
Ege,,
(((kk=T)))
-Ber.-
Σ
1Bbc
=Bgr..
Σ
VF - B
f(((k=
IEbEU'SB
=0.
(18)
We next turn to 71:
T ((0))) 1
Σ
V f (0 Tm)
B h=1
(0x) - Vf (0 2
<1,2110- - 02 02- 1|?
where the last inequality is from the Lipschitzian gradient assumption (equation 2p follows that
T. <T. 10
01-
0k
1-1
Σ
(0j+1 -8,)
j=
1
=
Σ
n
Σ
F (0 (
G
j Tx
1-
B
=1²
Σ
VF -
Σ
my
Σ
v
(0)-
G
G
j= Tk
b=
j=k-
A-1
B
k-1
B
221²
Σ
VF (0g-r; -5
+
Σ
f
(0
G
G
j=k-Tk
b=1
j=k-Te
b=1
T
T
(19)
14

---

Published as a conference paper at ICLR 2020
where the last inequality uses the fact that ||a + bll? I 2||a|12 + 2|1b11 for any real vectors and b.
Taking the expectation in terms of (f)-r,,-1) E { Tk...., k - }}} for Ta, we have
k-1
B
1
= =B ( bjEfk -b
Σ
7
(((0)=));(()1,)))
G
j=h-T
k-1 Σ
Σ
-
V
(
j=k- Tk
B
Th
+ -j
C.Gy
1-12j"
B
- - (100)));;(0-)))))((((11)))))))))
E 1..- kk.
Σ
Σ V -1000
- Besk-
Σ
Buj G
<Be,
Σ
<B Σ
0²
(20)
G2
j=k-Tk Tx
where the second to last equality is due to the last lines in equation 17 and the third equality is due to
Ee, A-
12526-72
Σ
My Cg
Σ
VF
k+ >22">
B
V ( (y ((0g)
-E 120-1221 12j2k
Mz""
Σ Byr. -y -1(0pr))))
G.
Ey- -
=0.
15

---

Published as a conference paper at ICLR 2020
Taking the expectation in terms of Ey-r,,* for Ta, have
Egg-r,, 15-t k [Ti]
=Bg, (..ii(k-Tu.nkk11
Σ
1
Σ
f
(0)-z))
G3
j-k-Tk
Buj ff (0
=Bg₁ (kk
Gj
B²n Gj
Σ
E -
(21)
j= Tk
where the last inequality uses the fact that N a:ll2 S N NEE N i= ||::] for any real vectors ag and
the bounded age assumption equation 6
We take full expectation on both sides of equation 19 and substitute E[T3] and B[T,]] by their upper bounds, equation 20 and equation 21 respectively:
k-
k-1
B²d G
E < 2T?
B
Σ
0²
T
Σ
E
| |1
(22)
Gj
j=
j=kーTH
Substituting [[[i]] and [E[7]] with their upper bounds equation 22 and equation 17 taking full expectation on both sides in equation [6 we obtain
respectively, and
[fk++ f(0x)
(0mmm1) (7)
Buk
B
B[[[v)(0+)1 +
Σ
V
f(0 (0-
2Gr
Bup
B Σ
G 02
T
B²1 E
||
Gt
G²
j=k-Tk
j=kーT
L
Bo² +E
V f(
2G
Bukk E|| [ +
B2
Bypk
E
2Gk
2G
2Gk
B
B
Σ
a²
B3I..ITT
Σ
|V/00-=)))1
(23)
22
G
Gh
G
j=k-Tk Tk
j=kー
16

---

Published as a conference paper at ICLR 2020
Summarizing the inequality equation 23 from k to k master, we have
K, meaning until the K-th update of the
(f - f(11)
<
B
K
Tk
E
K
BLL
Bilk
E (V
2
Gk
20
2G
km 1
km
Br L
B² L
k-1
+
+
Σ
0²
2G
k=1
j=k-T
K
1TT TJ
k-1
[|b)())-)]1]]
+TL
E
G
03
j=
B
E
(
2
G
k=1
BT
BSMLLT
Th+t
BTp
E
|
2G
Gk
2Gx
Br
B²
Σ
a²
2G
Ge
G
j=k- Th
B
The
E (IVI(()))I*
BTj
B²TLL
0²
2
G
20
Gk
B
lk E (1T)(0))))
B L
B² 1?2
Σ j=k-T
o²
(24)
2
Gk
2G
Gk
where the second to last inequality is due to equation and the last inequality is due equation 6 Note that the global optimization point. By doing a few simple algebraic operations on equation 24 we have:
K
2(S(0)) - ((0))
+
B G
+
mn L2
Gt
kj=k-
-+I-1
of C.
d²
Gk
B
B2b
kmml
k
(25)
This completes the proof.
Proof for Corollary 1
Proof. Combining equation 9 and equation 10
we get
4BL(T 1)2(f(0)) f(0-))
o²
(1(0))- (((0))
4B² + +1²
BLKo2
1
4B* 1)2 n²²
S 2BL(T+1)
(26)
follows from equation
that thth
T
1
ByL B
<
2T +
2(T + 2
2
2
=
1
17

---

Published as a conference paper at ICLR 2020
The last inequality holds since naturally T O. This implies that condition equation in Theorem
satisfied globally. Then we can safely apply equation 8 in Theorem
B(I 2(f(0)) f(0')) + K (Br2 1BB2L+222LLTT 23 0² K
BK
2(1(01) -((0))
+ (1+
BK 2(1 -((0)) +2L0'N
BKп
(f(0r) - L)
(f(01) - 1)
-2V
+ 2
BK
BK
(f(0)) -f(0))
BK
where the third inequality is due to equation 26 and the second to last equality uses equation 9 completes the proof.
This
Proof for equation in Section 4.1
Proof.
Dk+1
Ox+2
Ok41
Uk-2
Tk41
7k+1
0k+1
(yrk+1 + 9k+1)
Tk41
(27)
0c+1
M/++1
(7(70k + 9k) + gx+1)
7k+1
Ox+1
(n + 7yh + gg++1)
Tk+1
C EXPERIMENTAL SETUP
C.1 ALGORITHMS
Algorithms only change the master's algorithm; the complementary worker algorithm is the same as ASGD (Algorithm[] [] The master's scheme is simple FIFO. We consider parameter server optimizations beyond the scope of this paper.
The calculation the coefficient is described in Appendix C.6
We note that in Algorithms and the term 0* is identical to Pg- from the definition of т in Section
Algorithm 5 Staleness-Aue Awaes--Arrrr---ee Gradient: master
Initialize an iteration array: iler = [0] N
For == 1...K do:
Receive gradient of from worker i Calculate worker i's current delay Tk f- k iterli]
Update momentum Uc+1 + YUk + 02
Update master's weights 0k+1 + 01
Uk+1
Send 0x+1 i to worker
Save current iteration iler(i] +- k
18

---

Published as a conference paper at ICLR 2020
Algorithm 6 DANA: master
For = 1...K do:
Receive gradient g from worker i
Update worker's momentum of +- y0² + gj.
Update master's weights 0k+1 t- 02 U
Send estimate 0 Ox+1 71:7 Ej=1 v worker
Algorithm 7 SAANA--Salenes-AAie master
Initialize an iteration array for the workers: iter = [0] * N
For k= 1...K do:
Receive gradient de from worker
Calculate worker i's current delay Tk s- k - iterli]
Update worker's s momentum D² t yo² + li
TE
Update master's weights 0k+1 0g nau
Send estimate 0 = 0x+1 7 2
N
v worker i
jm1
Save current iteration iter[i] +
Algorithm 8 DANA- DANA-GappAware. master
Initialize the given weights for each worker: 6 Po For k 1...K do:
Receive gradient st. from worker i
Calculate Gap: GA 10=-001 + 1d
Update worker's momentum of + --² +
2 g
Gk
Update master's weights 0k+1 +- 02: - 178*
Save and send estimate 6² +- -x-1- mn En
2ن to worker i
The Adam-based algorithm requires slightly more intelligent integration the gradient staleness penalizing methods (such as GA and SA). Penalizing the gradient before calculating the first and second moments doesn't 't affect the update vector since the first and second moments cancel each other out. Therefore, we suggest applying the penalty only on the first moment, thus decreasing the update step's size by the desired amount. Since DANA's integration into the Adam algorithm convoluted and not straight forward, we chose not to implement the combination in this paper.
Algorithm 9 Adam: master
Require: 71... .. step lengths
Require: 31. 32 E [0, 1): exponential decay rates for the moment estimates
Initialize: mg <- 0, Un
For I...K do: Receive gradient gf. from i
Update biased first moment estimate my < 81 (1 Br)
Update biased second moment estimate Uk t 320h + (1 (gtt)
Compute bias-corrected first order moment estimate my + 1-
my
Compute bias-corrected second order moment estimate 0g <- T-
Update master's weights 0k+1 +- 02
me-iig Voxte
Send 0 to worker
19

---

Published as a conference paper at ICLR 2020
Algorithm 10 Adam-Staleness-Awarr master
Require: " step lengths
Require: 31 E [0, 1): exponential decay rates for the moment estimates
Initialize: <- 0. vn f 0
Initialize: iler = [0] * N: an iteration array for the workers
For = I...K do:
Receive gradient gi from worker i
Calculate worker i's current delay т k: iter(i)
Update biased first moment estimate <- m1mx-1 + (1 31)
Update biased second moment estimate Uk 320k 1 + (1 (gt))
Compute bias-corrected first order moment estimate ri + B-
ma.
Compute bias-corrected second order moment estimate Üg x----- I-35
Update master's weights 0k+1 t- 0
Send 0 to worker
Save current iteration iter[t] +-
Algorithm 11 Adam- Adaa--GppAAwar: master
Require: Tt.... ".] step lengths
Require: $1. B2 E [0, 1): exponential decay rates for the moment estimates
Initialize: my <- 0, By
Initialize: 6' = 0o: parameters for every worker
For k 1... do:
Receive gradient of from worker i
Calculate Gap: G₁ 10--0'1 +
Update biased first moment estimate my < -1m4-1 +
1-81 C gh
Gt
Update biased second moment estimate Uk + 320k-1 + (1 32 (gtt²
Compute bias-corrected first order moment estimate vin +- 1- Dr
Compute bias-corrected second order moment estimate 0ū. -- 1-85
Update master's weights 0k+1 0%
Ii mi-ii Vou+e
Send 0x+1 1 to worker
Save worker i's given parameters 6³ <- 0x+1
C.2 DATASETS & MODELS
CIFAR The CIFAR-10 (Krizhevsky) 2012) dataset comprises 60K RGB images partitioned into 50K training images and 10K test images. Each image contains 32x32 RGB pixels and belongs to of 10 equal-sized classes. CIFAR-100 is similar but has 100 classes. Link
ImageNet The ImageNet dataset (Russakovsky et al.) 2015), known ILSVRC2012, consists of RGB images, each labeled as one of 1000 classes. The images are partitioned into 1.28 million training images and 50K validation images; each image is randomly cropped and re-sized to 224x224 (I-crop validation). Link
WikiText-103 The WikiText language modeling dataset is collection of over 100 million tokens extracted from the set of verified Good and Featured articles on Wikipedia. Compared to the preprocessed version of Penn Treebank (PTB), WikiText- 103 is over 110 times larger. The WikiText dataset also features a far larger vocabulary and retains the original case, punctuation, and numbers (Merity et al. 2016). Link
20

---

Published as a conference paper at ICLR 2020
Transformer-XL The Wikilext-102 dataset is trained the Transformer-Xe XL model (Dai al. 2019). The hyperparameters are the ones suggested in the original paper (also see Appendix C.4 and the implementation is taken from their repository. Link
C.3 GAMMA DISTRIBUTION
Ali al. (2000) suggest method called CVB to simulate the run-time of distributive network of computers. The method is based on several definitions:
Definition 2.
Task execution time variables:
Mtask
mean time of tasks
Vtaek variance of tasks
Mmach
mean computation power of machines
V Vmach
variance of computation power of machines
Otask
took
amach
Vmach
G)a,B) is random number generated using a gamma distribution, where a is the shape and 8 is the scale.
For case, all tasks similar and batch size of B. Therefore, the algorithm for deciding the execution-ting of every task on certain machine is reduced to one of the following:
Algorithm 12 Task execution time homogeneous machines
Btask Pluak
Oceask
① G(atask; Brask)
Smach
Orwach for i from to K - 1: time G(amacho Smach)
Algorithm 13 Task execution time heterogeneous machines
Omach Smach amach
for j from to M:
pli] = G(amachr 3mack)
Stask [i] plß
for i from 0 to - 1: time = G(otask: Brask (curr))
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 Algorithms 12 and 13 naturally give rise to stragglers. In the homogeneous algorithm, all workers have same mean execution time but some tasks can still very slow; this generally means that in every epoch different machine will be the slowest. In the heterogeneous algorithm, every machine has different mean execution time throughout the training. We further note that pij] the mean execution time of machine on the average task.
In our experiments, we simulated execution times using the following parameters as suggested by Ali al. 2000): Ptask Mmach B V2 Vaach where B is the batch size, yielding mean execution time of j simulated time units, which is proportionate to B. In the homogeneous setting Vmach = 0.1, whereas in the heterogeneous setting Vmact = 0.6. For both settings, Viask 0.1.
Figure B illluutrrats the differences between the homogeneous and heterogeneous ganma-distributie distribution. Both environments have the same mean (128) but the probability of having iteration that is at
21

---

Published as a conference paper at ICLR 2020
0.03
0.006
0.02
0.01
0.002
0.00
80
100
120
140
160
160
200
260
400
600
800
(a) Homogeneous gamma-distribution
(b) Heterogeneous gamma-distribution
Figure 3: Gamma-distribution in homogeneous and heterogeneous environments. The x-axis the simulated time units the iteration takes while the y-axis is the probability. Both environments have the same mean (128 time units). The red area represents the probability have an iteration which takes more than 1.25x longer than the mean iteration time.
least 1.25x longer than the mean (which means 160 or more) is significantly higher in the heteroge- neous environment (27.9% in heterogeneous environment opposed to 1% in the homogeneous environment).
C.4 HYPERPARAMETERS
Since one of our intentions was to verify that penalizing the gradients linearly the Gap the factor that leads to better final test error and convergence rate, we used the same hyperparameters across all algorithms tested. These hyperparameters are the original hyperparameters respective neural network architecture, which are tuned for single worker.
CIFAR-10 ResNet-20
Initial Learning Rate 77: 0.1
Momentum Coefficient yy 0.9 with NAG
Dampening: (no dampening)
Batch Size B: 128
Weight Decay: 0.0005
Learning Rate Decay: 0.1
Learning Rate Decay Schedule: Epochs and 120
Total Epochs: 160
We note that Krizhevsky (2012) originally suggested 0.0001 as the Weight Decay hyperparameter for this framework. However, when we tuned the Weight Decay on single worker we found that 0.0005 results in the best final test accuracy (92.43% as opposed to 91.63%).
CIFAR-10/100 Wide ResNet 16-4
Initial Learning Rate zy: 0.1
Momentum Coefficient q: 0.9 with NAG
Dampening: 0 (no dampening)
Batch Size B: 128
Weight Decay: 0.0005
Learning Rate Decay: 0.2
Learning Rate Decay Schedule: Epochs 60, 120 and 160
Total Epochs: 200
ImageNet ResNet-50
Initial Learning Rate 7y. 0.1
Momentum Coefficient 7: 0.9 with NAG
Dampening: (no dampening)
Batch Size B: 256
Weight Decay: 0.0001
Learning Rate Decay: 0.1
22

---

Published as a conference paper at ICLR 2020
Learning Rate Decay Schedule: Epochs 30 and 60 Total Epochs: 90
WikiText-103 Transformer-XL
Initial Learning Rate 0.00025
Dropout: 0.1
Dampening: 0 (no dampening)
Batch Size B:
First Moment Coefficient $1: 0.9
Second Moment Coefficient 32: 0.999
10-8
Learning Rate Decay: Cosine from 0.00025 to 0
Gradient Clipping: 0.25
Total Iteration Steps: K = 200000
Learning Rate Warm-Up In the early stages of training, the network changes rapidly, causing error spikes. For all algorithms, follow the gradual warm-up approach (Goyal et al. (017) to initial learning rate by the number workers and ramp
overcome this problem: we divide up linearly until it reaches its original value after 5 epochs. We also momentum correction (Goyal ct al. 2017) in all algorithms to stabilize training when the learning rate changes.
C.5 WEIGHT DECAY
When GA is used with Weight Decay, the gradients contain a weight decay element which also needs to be divided by the Gap part of the gradient.
C.6 C CORFFICIENT
In Definition we explained that we use coefficient C to measure the gap. In Section 5.3 using
the parameter- wise method, C' calculated per-parameter. To calculate C per-paaameter, we used weighted-average in manner similar to the technique used in Adam (Kingma & Ba 2015). The mechanism is described in Algorithm
Algorithm 14 C Coefficient Calculation
Require: Mmaa (usually Mmaz 77)
Require: 31 E [0, 1): exponential decay rates for the moment estimates
Initialize: C' 4- 0d ma +- 0
For k= 1...K do:
Receive gradient o¹ from worker i
Calculate update step Uk+1 YPu + g
Update biased second moment estimate m& + 81m + +1 (1- 31
Compute bias-corrected second order moment estimate myg <- 1-885
Calculate Coefficient C Tmaa (Vir= +
Where is the parameter-we wise method, all operations are executed per-parameter. Throughout our experiments used 31 0.999 and 10-8 as suggested by Kingma & Ba 2015).
23

---

Published as a conference paper at ICLR 2020
C.7
TABLED RESULTS
Table 4: ResNet-20 CIFARIO Final Test Accuracy (Baseline 92.43%)
N
SA
DANA-SA
NAG-ASGD
GA
ASGD
DANA
DANA-GA
91.63:1.116
91.82:1.177
91.4311.37
91.78:t0.13
90.5+0.06
92.13:10.08
92.06:1..24
8
90.63:10.14
90.99
87.6
91.21
90.28
91.97:10.17
92.13:0.14
12
89.73=0.27
90.27
10.0
90.12:+0.29
90.02:+0.31
91.2++028
91.87:0.24
16
88.93=0.37
89.48:00.06
10.0=0.0
89.59=10.39
89.82::.29
89.68:0.41
91.9811015
20
0..2
88.97+0.23
10.0+000
89.03++0228
89.55++0.13
88.06-+0.23
91.62.+0117
24
0..2
88,420.25
10.0=0.0
88.7540.4
89.35
67.72:1.46
91.46110.17
28
06.3
88.0+0.27
10.0=0.0
18.18
88.5+0.12
30.72:19.74
91.4510.11
32
0..5
8..64
10.0++0.0
87.92+00.27
88.3++0.7
27.6++14.7
91.15++0.32
40
83
86.75+0.22
10.0
86.4811.11
86.6110.54
22.82+13.59
90.9410.2
48
80.82:10.46
85.6::0.28
10.0+0.0
85.0:10.66
83.6:10.6
10.0+0.0
90.6810.33
Table 5: WideResNet 16-4 CIFARIO Final Test Accuracy (Baseline 95.17%)
N
SA
DANA-SA
NAG-ASGD
GA
ASGD
DANA
DANA-GA
4
94.41
94.39+0.26
94.81+0.11
94.89+0.16
92.99-+0.15
95.0++0.13
95.08
8
93.3810.16 93.5210.02
92.8310.61
94.32-0.16
92.9110.09
94.6710.06
94.911.16
12
92.46:10.16
92.68+0.21
44.35+28.22
94.02++.1
92.81+00.2
94.27+0.15
94.84+1..1
91.5110.14 16
91.92+0.07
23.36+:26.2
93.72=00008
92.48:10.25
93.56-10.26
94.77-10.19
20
90.62.0.17
91.3740.23
33.41430.31
93.35=0.11
92.28-10.31
92.57:10.35
94.68-10.11
24
90.06+0.16
90.5+0.14
11.62+3.23
92.92+0.03
92.13+0.3
89.93+10.59
94.39+0.11
28
89.3
90.18+0.17
31.91
92.56=0.08
91.610.26
75.32 12.14
94.39-1..2
32
88.740006
89.35:10.16
19.02
92.35=10.22
91.22-1..19
68.13
94.27-10.1
40
87.2
88.23+0.25
10.0=0.0
91.65=0.16
90.53+0.24
28.97=25.07
93.8410.12
48
85.6510.226
86.6410.78
12.26=4.52
90.9710.38
89.5410.31
22.31=11.43
93.6311.13
24

---

Published as a conference paper at ICLR 2020
40
40
40
Worker
24 Workers
30
30
Gep
20
16 Mictters
Worters
Workerss
20
Worken
Workers
Delay
20
10
10
10
50
100
150
200
100
150
200
50
100
150
200
Epoch
Epoch
Epoch
(a) DANA-GA
(b) Gap-Aware
(c) Delay (SA)
Figure 4: Delay and Gap throughout the training process for different number of workers using GA and DANA-GA. The figure shows the average (bold line) and standard deviation (band) of 5 runs for N E [4, 8, 16, 24, 32]. All sub-figures are equally scaled to easily compare between them. GA penalizes the stale gradient much less than SA. DANA-GA penalizes the stale gradicnts even less than GA thanks to its approximation.
Table 6: WideResNet 16-4 CIFAR 100 Final Test Accuracy (Baseline 76.72%)
N
SA
DANA-SA
NAG-ASGD
GA
ASGD
DANA
DANA-GA
4
74.74:10.3
16.19
76.27:1.2
75.64.10.08
72.42:10.31
76.21
75.75.0..11
8
0..14
75.66:00199
7..24
7..3
72.8
7..03:1.0.1
7..64
12
71.6610.23
74.73
69.2910.56
73.8610.3
72.3410:28
75.72:0.27
75.41
16
0..39+0.27
03.76++0.19
6.73
72.82+0.17
71.99+0.3
75.0+-0.26
75.01
20
69.51+0.223
0..3+
37.28+7.21
72.34+0.2
71.63++0.18
73.41+0.4
74.75+00.22
24
68.6610.1
70.540:44
9.67
71.74::0.17
71.1510.34
71.26::0499
74.76-10.16
28
67.48+0.3
6..67+003
6.35+7.41
71.22++0.4
70.58+0.36
68.7+1.25
74.41+0.45
32
65.67=+0.41
63.52+0.77
12.71
70.64
69.91
66.73+1.15
74.33+
40
0..3
66.0610.23
9.5611.11
69.75+0.4
69.25110.48
64.29
73.6110.26
48
58.78=0.57
64.46+0.27
4.24
68.3440.19
67.63:10.43
27.42+
73.33+.023
C.8
DELAY vs. GAP
To better illustrate that the delay is usually bigger than the Gap, we measured both sizes throughout the training process using different workers. The tested framework was CIFAR 100 using WideResNet 16-4. We used the Gap-Aware and DANA-GA algorithms with the same hyperparameters described in Appendix C.4
Figure shows the average Gap and Delay (r) for every epoch throughout the training process. The Gap (Figure 4(b)) is constantly lower than the Delay (Figure 4 especially towards the end of the training where the learning rate small (which decreases the distance between the master's and worker's parameters). This figure illustrates how penalizing according to the Delay, as in Staleness-Aware can easily over-penalize when the number of workers is large.
DANA uses an approximation of the master's parameters at the time of the future update, thus mitigating the staleness of the incoming gradients. This mitigation also reduces the Gap, as shown in Figure 4(a) which reduces the needed penalization when using DANA-GA.
C.9 GAP VERSIONS
We tested three different Gap variations (See Section 5.3 to determine which technique has the best performance. The variations were tested three different frameworks:
CIFAR10 using ResNet-20
CIFAR10 10 using WideResNet 16-4
25

---

Published as a conference paper at ICLR 2020
Toxt Erao (66
Train Ener (%)
Jabal
10.0
16
32
Workers
Workers
Test CIFARIO ResNet-20
(b) Train CIFARIO ResNet-20
Test Emer (%)
Tran Erer (%)
16
32
16
24
32
Workers
# Workers
(c) Test error. CIFARIO0 WideResNet
(d) Train error. CIFARI00 WideResNet
Figure 5: Final and train error for different numbers of workers N. The figure shows the average (bold line) and standard deviation (band) of 5 runs. The black dashed line is the SGD error using single worker.
ASGO
40
AS-D
NAG-ASSD
10.0
NAG-ASCO
NAG-ASOD
Train Emror (%)
Sta eness Aware
Gop
Train Error (%)
Gop Aiatr:
Staleness AWAa
Train Error (%)
30
7.5
DANA
20-
DAVA-GA
5.0
20
2.5
10
4
12 16 20 24
28
32
40
48
8 12:1620 2216202428833
48
12 16 20 24 28 32
40
48
Workers
Workers
Workers
(a) CIFARIO ResNet-20
(b) CIFARIO WideResNet
(c) CIFARIO0 WideResNet
Figure 6: Final train error for different numbers of workers N. The figure shows the average (bold line) and standard deviation (band) of runs on different frameworks.
CIFAR100 using WideResNet 16-4
Each framework was trained on N E [4, 8, 16, 24,32) asynchronous workers. Figure contains the experiments not shown Section and demonstrates that parameter-wise Gap-Aware usually reaches better or similar final enrors. The hyperparameters are the same ones detailed in Appendix C.4 C.4
C.10 CIFAR TRAINING
Figure 6 shows that DANA-GA always remains very close to the zero-error region. This means that, unlike other algorithms, DANA-GA is able to converge on the training set despite the gradient staleness. Figure 6 further demonstrates all of the concepts diseussed in Section 6.
C.11 CONVERGENCE RATE
Figure 7 that the convergence rate GA similar to that of SA. despite using a larger step size. This suggests that GA does not require more steps than SA to reach its (better) minima. DANA-GA's convergence rate remains very close to the baseline, which suggests that doesn't require more steps to converge. This means that DANA-GA reaches a test error similar to the single worker case in the same number of steps, while enjoying asynchronous speedup.
Figure g demonstrates the same ideas discussed in the last paragraph ImageNet using 64 asyn- chronous workers. However, since this case the number workers is much larger, both SA and DANA-SA perform very poorly due the the over- penalization of SA. This helps illustrate that GA is a better staleness mitigation method than SA. DANA-GA remains very close to the baseline despite the large number of workers used, demonstrating the superiority of DANA-GA.
26

---

Published as a conference paper at ICLR 2020
100
80
NAG-ASGD
50-
Test Error (%)
ABED
Staleness
40
DANA
Gap-Awaar
Test Error (%)
80
Test Error
DANA-BA
DANA-SA
30
60
DANA-GA
20
Baoelin
40
20
0
100
150
100
150
200
50
100
150
200
Epoch
Epoch
Epoch
(a) CIFARIO ResNet-20
(b) CIFARIO WideResNet
(c) CIFARI00 WideResNet
Test error throughout the training using 16 workers. The figure shows the average (bold line) and standard deviation (band) of runs on different frameworks.
Figure 7:
100
NAG-ASGD
ASGD
-.. Staleness-Awatt
Test Error (%)
80
Gap-Aware
DANA
DANA-SA
60
Baseline
40
0
20
40
60
80
Epoch
Figure Test error throughout the training using 64 workers on ImageNet. DANA-GA remains close to the baseline. GA surpasses SA and DANA-SA.
C.12 TUNED ASGD
We tuned the learning and momentum of ASGD the CIFAR10 dataset with the ResNet-20 model using 32 workers. Tuning was performed using grid search over 70 perturbations:
17 E [0.001, 0.003, 0.01, 0.1, 0.3, 1]
E 0.9, -088, -05,, -0.55, 0, 0.25, 0.5, 0.8, 0.9,0.95) 0.95]
As suggested by Mitliagaas (2016), we also tested negative values of momentum mitigate the implicit momentum created by the gradient staleness. Figures to 11 the results of the above experiments. The best final test error was given when:
Figure (17 0.03, 0.5)
Figure (1) = 0.3, = 0..)
Figure
(1) 0.3, -0.5)
This shows that the best hyperparameters can vary between frameworks. The best hyperparameters for specific framework also vary across different number of workers all the hyperparameters found in this experiment are different from the best hyperparameters the single worker. Tuning for the best hyperparameters for every different number of workers for each framework significantly increases the training time and is best avoided possible.
DANA-GA surpasses the tuned ASGD in every framework, while DANA performs very poorly using 32 workers. This proves that gradient penalization is very beneficial to overcome gradient staleness and specifically that GA is very successful gradient penalization method.
27

---

Published as a conference paper at ICLR 2020
0.95
83.23
86.4
77.37
10.0
10.0
10.0
10.0
0.9- 79.9
84.66
87.21
62.88
10.0
10.0
10.0
-5
0.8 74.52
83.27
87.31
84.44
10.0
10.0
10.0
Momentum
0.5
63.17
76.62
84.84
88.0
85.28
9.96
10.0
-60
0.25
58.39
70.99
82.86
87.21
87.76
54.3
10.0
0.0
54. 54.25
67.93
81.1
85.93
87.77
82.43
10.0
45
-0.25
50.77
65.92
79.87
85.04
87.7 84.06
10.0
-0.5
48.18
63.14
78.25
84.83
87.44 85.99
10.0
30
-0.8
45.61
61.39
75.36
83.02
87.82 85.87
10.0
-0.9
45.14
60.38
74.59
83.48
87.86
87.44
14.59
15
0.001
0.003
0.01 0.03 0.1
0.3
1.0
Learning Rate
Figure 9: Test Accuracy ASGD using 32 asynchronous workers on CIFAR1O ResNet-20 using different learning rate and momentum coefficients. The best accuracy achieved is 88% (1 = 0.03, 7 0.5). The tuning includes negative values of momentum
-90
0.95
86.8
89.93
89.32 40.84
10.0
10.0
10.0
0.9
84.0
88.54
90.92
88.88
10.0
10.0
10.0
75
0.8
80.43
86.3
89.5 91.42
65.21
10.0
10.0
Momentum
0.5
71.69
82.04
.6.64 90.03 90.86
10.0
10.0
-60
0.25
66.53
78.99
86.02
89.92 90.77
86.47
10.0
0.0
62.23
76.23
84.63
89.12 12 91.07 89.67
10.0
45
-0.25
59.39
73.81
83.55
88.12 91.04 90.28
37.46
-0.5
56.74
71.76
82.62
87.47 91.02 91.55
50.47
33
-0.8
54.25
69.14 14
80.96
87.08 90.0 91.57
57.0
-0.9
53.45
43.45
68.41
81.23
86.94 90.16 90.69
10.0
15
0.001
0.003
0.01
0.03 0'1 0.3
1.0
Learning Rate
Figure 10: Test Accuracy of ASGD using 32 asynchronous workers CIFARIO WideResNet 16-4 using different learning rate and momentum coefficients. The best accuracy achieved 91.57% (n) 0.3,1 7 -0.8). The tuning includes negative values of momentum
C.13 GRADIENT STALENESS NOISE
We notice that in the ImageNet experiments (Table NAG-ASGD remains relatively close the baseline even when the number of workers is large, as opposed to the CIFAR experiments, which NAG-ASGD severely deteriorates N scales up. This phenomenon suggests that there is some
28

---

Published as a conference paper at ICLR 2020
0.95
61.18
68.18
69.56
55.48
1.0
1.0
1.0
0.9
54.34
65.65
69.9
66.63
1.0
1.0
1.0
600
0.8
42.71
60.13
68.18
70.33
65.04
1.0
1.0
0.5
26.41
46.67
63.19
68.59
70.82
66.21
1.0
Momentum
-45
0.25
21.1
38.26
58.79
67.61
70.59
68.35
1.0
0.0
18.4
32.97
55.26
66.48
69.66 70.66
7.08
30
-0.25
16.46
29.25
51.67
64.87
69.79 70.33
19.1
-0.5
15.04
26.38
48.2
63.14
68.99 71.07
65.57
15
-0.8
14.08
23.66
45.51
61.33
69.04
70.99
62.4
-0.9
13.69
22.94
44.09
60.34
68.24
70.82
66.82
0.001
0.003
0.01
0.03
0.1
0.3
1.0
Learning Rate
Figure 11: Test Accuracy of ASGD using 32 asynchronous workers on CIFARIO WideResNet 16-4 using different learning rate and momentum coefficients. The best accuracy achieved is 71.07% (n) 0.3, = 0.5). The tuning includes negative values of momentum
grudient staleness noise that framework can "tolerate" and still perform well. Following this intuition, reasonable that some gradient staleness should allowed go "un-penalized" to avoid limiting the step-size needlessly. This idea explains why SA and GA demonstrated relatively poor results in ImageNet, especially when the number of workers was relatively small. Though we consider this analysis beyond the scope of this work, it is relevant for this paper note that think that the tolerable gradient staleness noise depends on the size of the model and dataset, which suggests that GA can be further improved by correctly analysing the tolerable gradient staleness noise and starting the penalization accordingly. We plan to continue our research in this path as well.
D ASYNCHRONOUS SPEEDUP
Cloud computing is becoming increasingly popular a platform to perform distributed training of deep neural networks. Although synchronous SGD is currently the primary method (Mikami et al.) 2018, Ying al. 2018 Yamazaki et al. 2019 Goyal al. 2017) used to distribute the learning process, it suffers from substantial slowdowns when run in non-dedicated environments such as the cloud. This shortcoming 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 potentially better alternative for cloud computing.
Figure (a) shows the theoretically achievable speedup. based on the detailed gamma- distribbued model, for asynchronous (GA and other ASGD variants) and synchronous algorithms using homoge- neous 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 each iteration until all workers complete their batch. Figure 12(b shows that ASGD-based algorithms (including GA, SA and DANA versions) are up 21% faster than SSGD in homogeneous environments. In heterogeneous environments, ASGD methods can be 6x faster than SSGD. We note that this speedup is 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.
29

---

Published as a conference paper at ICLR 2020
Homogemeuus Speedlup
Hamogeneaus Helerggenets ASG2
Teterogeneets SSGD Speeduu X5GD Speedup
Speedup Ratio
---- Liter Spred.p
Speedup
203
Workers
Warkers
(a) Asyne (ASGD) syne (SSGD) speedups.
(b) ASGD speedup over SSGD. axis is log scale.
Figure 12: Theoretical speedups for any ASGD (such as GA, SA DANA variants) and SSGD algorithms when batch execution times are drawn from gamma distribution. Each lime is an average of 20 runs with 100000 iterations per asynchronous algorithms are more communication efficient. Accounting for the communication overheads should expand the gap between the asynchronous and synchronous training.
Communication overheads not modeled; however,
20.0
ASGD
ASGO
40
ASGD
NAG-A900
NAG-AGGD
NAG-ASGO
17.5
Stadenees-Anne Auntn
Test Error (%)
Gapskoane
15
Gep-frente
Test Error (%
35
15.0
12.5
10
10.0
25
7.5
8
12
16
20
24
28
32
4
8
12
20 Workers
16
24
28
32
8
12
20 Workers
16
24
28
32
Workers
(a) CIFARIO ResNet-20
(b) CIFARIO WideResNet
(c) CIFARIO0 100 WideResNet
Figure 13: Final test error for different numbers of heterogeneous workers N. The figure shows the average (bold line) and standard deviation (band) of runs on different frameworks. The black dashed line represents the average result of SGD using single worker.
D.1 GAP-AWARE OVERHEAD
The Gap-Ave Cap-Aware method requires the master to save the parameters of every worker and adds some simple calculations mentioned in Algorithm and Algorithm 14 These caleulations add commu- nication or computation requirements to the workers and introduce only lightweight overhead to the parameter server compared to vanilla-ASGD. This lightweight overhead is similar the overhead introduced by other ASGD-based methods such as Zheng et al. (2016). The space requirement is not critical since the master is usually implemented in distributed manner, and the parameters stored in the CPU-side memory, which is usually substantially larger than the total parameter size.
and
D.2 HETEROGENEOUS EXPERIMENTS
tested the performance of GA in reference to other algorithms when asynchronous workers are heterogeneous. The setting was very similar to the one mentioned in Section except that it this scenario we used the gamma-dinn gammaadiistibution distribution to model heterogeneous workers (see Appendix C.3).
Figure B demonstrates that GA and DANA-GA superior to the other tested algorithms in hetero- geneous environments as well. When comparing between Figure [3 and Figure 2 it is noticeable that heterogeneous environments reach higher accuracy. This is because in heterogeneous environments some workers are very fast compared to the other ones, thus their gradients are more accurate and arrive more frequently than the slow workers' gradients. Since in cloud computing. the workers can be either heterogeneous or homogeneous, we suggest using DANA-GA to maximize the results.
30


Reviews:
[{"review_id": "Sylx4uze9H", "reviewer": "AnonReviewer2", "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": "This paper studies training large machine learning models in a distributed setup. For such a setup, as the number of workers increases, employing synchronous stochastic gradient descent incurs a significant delay due to the presence of straggling workers. Using asynchronous methods should circumvent the issue of stragglers. However, these asynchronous methods suffer from the stale gradients where by the time a worker sends the gradients to the master server, the model parameters have changed based on the gradients received from other workers. This leads to severe performance degradation in the models trained by using asynchronous methods, especially where the number of workers scales.\n\nThis paper proposes a gap-aware method to reduce the adverse impact of stale gradient on the asynchronous distributed learning. In particular, when the master receives a gradient from a worker, it computes the norm of the difference between the current model parameter and the past model parameter associated with the gradient. The master then computes *gap* value based on this norm and the norm of the average gradient. Before employing the gradient, the master scales the gradient by the computed gap value. The paper establishes the convergence rate for the gap-aware asynchronous method which is similar to the convergence rate of SGD. The paper then performs an extensive experimental evaluation of the proposed method over different datasets and models. The empirical results demonstrate the advantage of the proposed gap-aware method over other baselines.\n\nPros\n\n- The extensive empirical evaluation shows that the proposed method is effective in preventing performance degradation in an asynchronous setup across tasks and models. \n\n- The method outperforms other solutions to combat stale gradient, such as the staleness-aware method by Zhang et al.\n\n- The paper shows that the proposed method can be combined with DANA (Hakimi et al.) and achieves the performance very close to the synchronous setting while realizing the speed up provided by the asynchronous methods.\n\nCons\n\n- It was not clear to the reviewer how the convergence analysis of the proposed method differs from the existing analysis in the literature and if any novel ideas were involved in obtaining the theoretical results presented in the paper.\n\n- The gap-aware method increases the overhead at the master as it needs to store the most recent model parameters sent to each of the workers. This is much higher than the staleness-aware method where the master stores a single scalar for each worker. The paper barely discusses such overheads associated with the proposed method.", "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 carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Hyejd9jotH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a simple idea to mitigate gradient staleness in asynchronized distributed systems. Instead of scaling the staleness as in SA method, the authors propose to scale with the GAP, which is defined as the distance between current parameter and the staled parameter.\n\nThe paper is fairly well written, and the overall idea is interesting and simple in implementation. The authors also derive convergence bounds for the proposed algorithm and provide reasonable experimental results. I have the following comments:\n\n1. I think the theory, at the current stage, is not sufficient. The authors only provide a convergence bound for the proposed method, which does not tell anything about the advantages over other methods such as the ASGD and SA methods. I think a detailed comparison should be conducted. From the current presentation, it seems there is no theoretical advantages of the proposed method over existing methods, which seems to suggest that the empirical advantage might not come from the algorithm itself.\n\nI also notice that comparisons of convergence are illustrated in the appendix. However, it shows all SA and GA have similar convergence rates. This seems to indicate that SA and GA should performed similarly, which is not the case in the experiments.\n\n2. For experimental results, in Figure 2 (and others), how do you get the errors for different workers? I mean, how long do you need to run for each case? You should make sure that all the settings should use the same computational resources for fair comparisons, but this is not described in the text, making the results doubtable.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1lQL-d6YH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces a new variant of asynchronous SGD, GA-ASGD, for distributed training. The goal is to mitigate the gradient staleness issue caused by asynchronously applying gradients to an old version of parameters. Prior work addresses this issue by penalizing the learning step of a worker linearly to its missed updates since getting a replica of parameters. However, that approach does not consider the differences between the old and new versions of parameters, which can cause over-penalization and under-penalization. The main contribution of this paper is to introduce a new way of measuring weight staleness and to explore the idea of penalizing the gradient itself to mitigate the staleness issue. The paper does a good job of discussing how GA can be applied to existing optimizers such as Adam. It performs empirical studies on ImageNet and Transformers-XL to conclude that GA-ASGD outperforms ASGD and the prior staleness aware approach. It also demonstrates the scalability of GA by scaling up to training with 128 asynchronous workers.\n\nStrengths:\n+ Introduced a novel approach to measure the parameter staleness, which helps penalize the gradients instead of the learning step. \n+ The approach seems to be easily applicable without much additional hyperparameter tuning. \n+ Evaluation on both image and NLP tasks demonstrate that GA leads to improvement over prior staleness aware approaches.\n\nWeaknesses:\n- Despite great improvements over prior ASGD based approaches, there is still a quite noticeable accuracy degradation compared to the SGD baseline. \n- The evaluation is done with simulation, and no report of the number of training steps to converge and end-to-end training time, making it difficult to compare the efficiency with SGD based approaches. \n\nOverall, I think this is good work. The idea of defining weights stableness as the minimal number of updates required to traverse the current distance between the master and worker weights seems to be reasonable. The comparison to prior ASGD based approaches are extensive, and the improvements seem decent. The fact that it does not require much or additional hyperparameter tuning also seems neat. \n\nMy major concern comes from results compared to SGD and motivation. The fact that almost all ASGD based workloads, even with the help of GA, cannot get on-par accuracy as the SGD baseline bothers me. In particular, the accuracy drops considerably as the number of asynchronous workers grows (Fig 1. and Fig. 2, and Table 3). For example,  the gap between the accuracy of GA vs. SGD can be as large as 3.46% when there are 128 workers. That gap might be closed with additional hyperparameter tuning, but it is unclear from the current draft and results. In the Transformer-XL example, GA has to limit the number of asynchronous workers to 4 in order to get close to baseline accuracy. It would have been better to show the trade-off between accuracy and performance in comparison with SGD. \n\nOn the other hand, the recent advance of SGD using large-batch training achieves great results on large model training such as BERT [1]. It helps to improve the compute/communication ratio, which seems to mitigate the straggler issue. Given that today's cloud service largely uses homogenous accelerators (TPU/GPU of the same SKU), it is less clear whether it is really beneficial to train with ASGD despite the improvements from GA.\n\nQuestion:\nOne question is about how the batch size should be changed as the number of workers increases. The convergence analysis indicates that by increasing the batch size, the convergence speed of GA-ASGD will decrease. Does that mean the batch size should remain relatively unchanged to avoid negatively impacting the end-to-end training?\n\nIs there any benefit to applying Gap to model parallelism paradigm such as pipeline parallelism?\n\n[1] \"Large Batch Optimization for Deep Learning: Training BERT in 76 minutes\", by You et. al.", "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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a novel approach for measuring gradient staleness and use this measure to penalize stale gradients in an asynchronous stochastic gradient set up. Following previous work, they provide a convergence proof for their approach. Most importantly, they provide extensive evaluations comparing against previous approaches and show impressive gains over previous work.

After the author response, the primary concerns from reviewers is regarding the gap between the proposed method and single worker SGD/synchronous SGD. I feel that the authors have made compelling arguments that ASGD is an important optimization paradigm to consider, so their improvements in narrowing the gap are of interest to the community. There were some concerns about the novelty of the theory, and my impression is that theorem is straightforward to prove based on assumptions and previous work, however, I view the main contribution of the paper as empirical.

This paper is borderline, but I think the impressive empirical results over existing work on ASGD is a worthwhile contribution and others will find it interesting, so I am recommending acceptance.
Decision: Accept (Poster)