AdaScale SGD: A Scale-Invariant Algorithm for Distributed Training
Authors: Tyler B. Johnson
Pulkit Agrawal
Haijie Gu
Carlos Guestrin
Venue:  (2020)
Keywords: Large-batch SGD
large-scale learning
distributed training

Abstract: When using distributed training to speed up stochastic gradient descent, learning rates must adapt to new scales in order to maintain training effectiveness. Re-tuning these parameters is resource intensive, while fixed scaling rules often degrade model quality. We propose AdaScale SGD, a practical and principled algorithm that is approximately scale invariant. By continually adapting to the gradient’s variance, AdaScale often trains at a wide range of scales with nearly identical results. We describe this invariance formally through AdaScale’s convergence bounds. As the batch size increases, the bounds maintain final objective values, while smoothly transitioning away from linear speed-ups. In empirical comparisons, AdaScale trains well beyond the batch size limits of popular “linear learning rate scaling” rules. This includes large-scale training without model degradation for machine translation, image classification, object detection, and speech recognition tasks. The algorithm introduces negligible computational overhead and no tuning parameters, making AdaScale an attractive choice for large-scale training.


Under review as a conference paper at ICLR 2020
ADASCALE SGD: A SCALE-INVARIANT ALGORITHM FOR DISTRIBUTED TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
When using distributed training to speed up stochastic gradient descent, learn- ing rates must adapt to new scales in order to maintain training effectiveness. Re-tuning these parameters is resource intensive, while fixed scaling rules often degrade model quality. We propose AdaScale SGD, practical and principled al- gorithm that is approximately scale invariant. By continually adapting to the gra- dient's 's variance, AdaScale often trains at wide range of scales with nearly identi- cal results. We describe this invariance formally through AdaScale's convergence bounds. As the batch size increases, the bounds maintain final objective values, while smoothly transitioning away from linear speed-ups. In empirical compar- isons, AdaScale trains well beyond the batch size limits of popular "linear learning rate scaling" rules. This includes large- scale training without model degradation for machine translation, image classification, object detection, and speech recog- nition tasks. The algorithm introduces negligible computational overhead and no tuning parameters, making AdaScale an attractive choice for large-scale training.
INTRODUCTION
Large datasets and large models underlie much of the recent success of machine learning. Training such models is time consuming, however, as stochastic gradient descent algorithms can require days or weeks to train effectively. Thus, procedures that speed up SGD are valuable. Faster training enables consideration of more data and models, which expands the capabilities of machine learning.
To speed up SGD, distributed systems can process thousands of training examples per iteration. But training at large scales also creates a major algorithmic challenge. Specifically, learning rates must adapt to each scale. Without choosing these training parameters carefully, scaled SGD frequently trains low-quality models, producing a waste resources rather than a useful model.
To adapt learning rates, "fixed scaling rules" are standard but unreliable strategies. Goyal et al. (2017) popularized "linear learning rate scaling," which can work well, especially for computer vision tasks (Krizhevsky, 2014; Devarakonda et al., 2017; Jastrzębski et al., 2018; Smith et al., 2018; Lin et al., 2019). For other problems or larger scales, however, linear scaling often fails. This fact is well-known in theory (Yin et al., 2018; Jain al., 2018; Ma et al., 2018) and in practice (Goyal et al.. 2017). Other fixed scaling rules are also undependable. Golmant et al. (2018) test three rules linear, root, and identity-and conclude that each one often degrades model quality. Shallue et al. (2019) compute near-optimal parameters for many tasks and scales, and the results do not align with any fixed rule. To ensure effective training, the authors recommend avoiding such rules and re-tuning parameters for each new scale-aa an inconvenient and resource- inteereveeeeeieeeeeeee solution.
We propose AdaScale SGD. A practical but principled algorithm, AdaScale more reliably scales training by adapting to the gradient's ' variance. Decreased gradient variance is the fundamental im- pact of large batch sizes. Thus, scaling provides little gain if the variance already "small" small scales. In such cases, AdaScale increases the learning rate conservatively, and large-scale training progresses similarly to the small-batch setting. For iterations with "large" gradient variance, Ada- Scale increases the learning rate aggressively, and the per-iteration progress dramatically increases.
AdaScale is approximately scale invariant, a quality that simplifies large-batch training. With no changes to learning rates or other inputs, AdaScale can train many scales with similar results. This leads to two important innovations: (i) AdaScale improves the translation of training configurations between scales, which is useful for scaling up tasks or adapting to dynamic resource availability;

---

Under review as a conference paper at ICLR 2020
AdaScale
Linear scaling
Leaminn rate 1/:
Val. Ace (%6)
94.0
Val. Ace (56)
94.0
0.4
Val. Ace (5)
94.0
0.2
80.0
80.0
70.0
3k
6k
9k
12k
24k
36k
4k
8k
12k
3k
6k
9k
Iteration
itr.
Iteration
Iteration
S=1
S=4
S=8
S=16
S=32
S=64
Figure 1: Motivating results. For cifar10. AdaScale preserves model quality for many scales When plotted in terms scale-invariant iterations, training curves align closely, With AdaScalc, "warm-up" behavior emerges from adapting a simple learning rate schedule (exponential decay) to scale S (learning rate plot cropped show behavior). Mcanwhile, lincar scaling (with warm-up heuristic) degrades model quality as S increases.
and (ii) AdaScale works at scale with simple learning rate schedules, which eliminates the need for "warm-up" heuristics (Goyal et al., 2017). Qualitatively, AdaScale and warm-up have similar effects learning rates, but with AdaScale, this behavior emerges from principled and adaptive mechanism, not hand-tuned parameters.
We provide theoretical results that formalize this approximate scale invariance. Bounds for all scales converge to identical objective values. In contrast, the linear scaling rule requires fewer iterations but compromises model quality and training stability, causing divergence the batch size increases.
We perform large-scale empirical evaluations on five training benchmarks. Tasks include image clas- sification, machine translation, object detection, and speech recognition. The results align well with our theory, as AdaScale systematically preserves model quality across many scales, This includes training ImageNet with batch size 32k and Transformer with 262k max tokens per batch.
To provide context for our description of AdaScale, Figure 1 includes results from a simple scaling experiment using CIFAR- 10 data. These results illustrate the concept of scale invariance, AdaScale's qualitative impact on learning rates, and failure case for the linear scaling rule.
PROBLEM FORMULATION
We focus on quickly computing approximate solutions to the problem
minimizewERs F(w), where F(w) Ex-xx [f(w
(P1)
Here w parameterizes machine learning model, while X denotes distribution over batches of training data. We assume that and f are differentiable and that Ex-x Vw](w,x)) ] = VF(w).
Stochastic gradient descent is a popular algorithm for solving (P1). Let w, denote the model pa- rameters when iteration t begins. During this iteration, SGD samples batch X₃ ~ and computes the gradient ge V fwW. x.). SGD then applies the update w++1 Wt Tgge. Here nh is the learning rate. Given a schedule ir Zzo + R2 SGD defines fi = 1r((). For our experiments in $4, Ir is exponential decay or step decay function. SGD completes training after T iterations.
To speed up training, practitioners often parallelize gradient computation across multiple devices. Algorithm 1 defines scaled SGD algorithm.
scale S, the algorithm samples independent batches during each iteration. After computing the gradient for each batch in parallel, the algorithm applies the mean of these gradients (in place of g:) when updating model parameters.
But scaling training in this way creates a considerable algorithmic challenge. Each new scale re- quires a new learning rate schedule, which is inconvenient and resource intensive to obtain. To help address this challenge, we propose scaled SGD algorithm that is approximately scale invariant.
Definition 1. Let Wr denote the (possibly random) result of a scaled SGD algorithm. Fixing all algorithm inputs except scale the algorithm is scale invariant wT does not depend on S.
A invarianv algorithm makes parallelizing training significantly easier. Such algorithm can scale to any available amount of computational resources, and there is no need for parameter re- tuning, unreliable heuristics, algorithmic expertise from users.
2

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Scaled SGD
Algorithm 2 AdaScale SGD
function Scaled_SGD(S, 1r, X, /, Wo) for t 0, 2, T- do
function AdaScale(S, 1r, TSI, X, wo)
initialize To f 0: 0
g: < compute cateeerrrdddddiiieee f, 1/t < 1r(()
while < Tsi do
gt t compute_ grw.ieetddd..d..... S,
W++1 <
1/.B.
# Compute gain rа [1, (see $3.3):
return WT
+- O (w.
function compute sempute_gradien(w.. S, X, f) in parallel for i = ,,..., do
E (w.)
(8) (umple_batch22)
7h Tr [T]
V W (w..,
Wi+1 f- We 1/
T++1 f- Te + r
return 2i=18 gg!)
return W.
3 ADASCALE SGD ALGORITHM
This section introduces our AdaScale algorithm. As motivation, we first consider the role of gradient variance in SGD. We later provide practical guidance for variance estimation and momentum tuning.
3.1 INTUITION: IDENTITY SCALING, LINEAR SCALING, AND GRADIENT VARIANCE
We now consider two fixed scaling rules, which influence the design of AdaScale. One of these rules identity scaling, which keeps the training configuration constant for all scales:
Definition 2. To apply the identity scaling rule to Algorithm 1, use the same ir and T for all S.
Note that this rule has little practical appeal, since it fails to reduce the number of training iterations. second and more popular strategy is linear learning rate scaling:
Definition 3. To apply the linear learning rate scaling rule to Algorithm 1, use 1r(t) = (-1rs( and T [Tsi/S], where lrş1 and T's denote the learning rate schedule and total steps S 1.
Conceptually, linear scaling treats SGD as perfectly parallelizable algorithm. If true, applying gradients from S batches in parallel achieves the same result doing in sequence.
For special cases of (PI), the identity and linear rules result in male--invariant algorithms. To show this, we first define the variance quantities
E(w) = covx (W, x), VwJ(w, x)) and o d²(w) = = (r(- In words, d'(w) sums the variances of each entry in V Vwf(w, By sampling batches indepen- dently, scaling fundamentally impacts SGD by reducing this variance. Given w, in Algorithm 1, we have cov(g,, B:) = و E(w,) and E [g] (w::.. Here, only the covariance depends on S.
Consider the special case of zero gradient variance. In this case, identity scaling performs ideally: Proposition 1 (Scale-invariant SGD for deterministic gradients). If o²(() 0 for all w E IRd, then applying identity scaling Algorithm results in scale-invariant algorithm.
Although identity scaling does not speed up training, Proposition is critical for framing the impact of large scales. If the gradient variance is "smmall"" then cannot expect large gains from increasing S- a larger scale has little effect on g.. With "large" variance, however, the opposite is true:
Proposition 2 (Scale-invariant SGD for extreme stochasticity). Consider fixed covariance matrix E E s learning rate value ñ E Ryo, and training duration T. For a given v E R>0. assume fwf(w,x) ~ NVVF((W) vE), and apply linear scaling to Algorithm I with (1 vー and Tsi 1/T'. The resulting scaled SGD algorithm is ccale-invariant the limit v + +
In less formal terms, linear scaling leads to scale-invariance in the case of very large gradient vari- ance (as well as small learning rates and many iterations, to compensate for this variance). Since increasing decreases variance, it is natural that scaling yields large speed-ups in this extreme case.
In practice, the gradient's variance is neither ing may perform poorly. Moreover, the gradient's ''s variance does not remain constant throughout training. A scale-invarian algorithm, it seems, must continually adapt the state of training.
nor infinite, and both identity and linear scal-
3

---

Under review as a conference paper at ICLR 2020
3.2 ADASCALE DEFINITION
AdaScale, defined in Algorithm 2, adaptively interpolates between identity and linear scaling, based on the expectation of o (w,). During iteration AdaScale multiplies the learning rate by the "gain ratio" Tr E S]: Th = r lr(( Here is the "scale-invariant iteration," defined as - =0==0 Tv. The idea is that iteration & performs the equivalent of single-batch iterations, and T₁ accumulates this progress. AdaScale concludes when Ti 2 Tst. where Tsi the total scale- invariant iterations. Since []. AdaScale requires at least [Tsi/S] and most T'i iterations.
The identity and linear rules correspond to two special cases of AdaScale. If = for all the algorithm equates SGD with identity scaling. Similarly, if S for all we have linear scaling. Thus, to approximate scale-inaariance, $3.1 suggests setting re = 1 when the gradient's 's variance is small and r, S when this variance large. AdaScale achieves this by defining
ro o² (wi) + VF(()))l
[VF(())
The expectations here are with respect to the distribution of Wt, and we must approximate in practice (see $3.3). This definition of ensures that as increases, [[[w,41 w., V (F(w,)) and B|[[w++1 well") increase multiplicatively by rz. This leads to our scale-invariant bound in $5.
3.3 PRACTICAL CONSIDERATION:
imagenet, S-16
imagenet, S--128
If S = in AdaScale, then Fz = for all iterations. For larger scales, Ft depends on E [[o" (w:)] and IE' [[]/F(())]]]] and a practi- cal implementation must efficiently approximate these values. Fortunately, the per-batch gradi- (1) ents gi ..... g:
16 12
128
Gain ratio
96
64
(5) and aggregated gradient gr are readily available in distributed SGD algo- rithms. This makes approximating rt straight- forward. In particular, we define
0
30k
Iteration
Iteration
Offline evaluation
Online estimate
Figure Gain ratios. Plots compare moving average Ys estimates to values computed offline (using 1000 batches). 'he values align closely. Abrupt changes align with learning rate step changes.
S 0.-- 3-1 ii Ig. (1)
12
|B: T-1
and 2 = |g 1 50.
Here o7 and ii are unbiased estimates of EE [w:)w and [[IV estimation variance, we estimate 7i by plugging in moving averages of and pi. which average oi and jo over prior iterations. Our implementation uses exponential moving average parameter f= max 5/1000, 0}, where the choice of 6, and we provide evidence of this in Appendix C. To initialize, we set +- 1, and for iterations f < (1 0)-1 we define of and ni as the mean of past samples. Before averaging, we clip estimates so that o? 2 10-6 (to prevent division by zero) and if? 2 (to ensure r, S))
To ensure robustness
results no averaging. We find that AdaScale is robust to
To verify these estimators, Figure 2 compares moving average estimates to offline estimates using model checkpoints. These plots also provide examples of gain ratios for practical problems. We note that numerous prior works-for example, (Schaul et al., 2013; Kingma Ba, 2015; McCandlish et al., 2018) have relied similar moving averages estimate gradient moments.
One final practical consideration is the momentum parameter when using AdaScale with momentum-SGD. The performance of momentum-SGD depends less critically p than the learn- ing rate (Shallue et al., 2019). For this reason, we find that AdaScale often performs well if p re- mains constant across scales and iterations. This approach to momentum scaling has also succeeded in prior works involving the linear scaling rule (Goyal et al., 2017; Smith et al., 2018).
4 EMPIRICAL COMPARISONS
We evaluate AdaScale on five practical training benchmarks. We assess scale invariance by compar- ing training curves across scales. We assess impact on training times by comparing total iterations. We consider a variety of tasks, models (He al., 20;6;;;; Amodei et al., 2016: Vaswani et al., 2017: Redmon & Farhadi, 2018), and datasets (Deng et al., 2009; Krizhevsky, 2009; Everingham et al., 2010; Panayotov et al., 2015). Table 1 summarizes our training benchmarks. Due to space limitations, we provide additional implementation details in Appendix B.
4

---

Under review as a conference paper at ICLR 2020
imagenet
Learning rate 1ht
77.0
Val. Acc (%)
77.0
Training loss
5.0
4.0
Val. Ace
68.0
68.0
3.0
39.0
59.0
2.0
1.0
50.0
50.0
1.3
8k
16k
24k
32k
200k
400k
0
200k
400k
8k
16k
24k
32k
Iteration t
S-invariant itcration
S-invariant iteration
Itcration
speech
Learning rate 1/t: Learning rate 1/:
WAcc (%
Val. WAce (%)
80.0
Training loss
.02
70.0
70.0
.01
65.0
65.0
60.0
60.0
15k
20k
60k
80k
20k
40k
60k
15k 20k
Iteration
S-invariant iteration Ti
S-invariant iteration TI
Iteration
transformer
Val BLEU
27.5
BLEU
27.5
Training loss
0.9
0.6
1.7
0.3
20.0
20.0
0
75k
100k
0.5M
1.0M
1.5M
100k
Iteration
S-invariant iteration
T
S-invariant iteration T:
Iteration
yolo
Leaming rate I/|
81.0
Val. mAP (%)
81.0
Training loss
4.5
Val. mAp
72.0
72.0
.11
63.0
63.0
3.0
$4.0
2.5
10k
15k
50k
100K 150K 200k
0
50k 100k 150k 200k
Sk
10k
15k
Iteration f
S-invariant iteration
S-invariant iteration
Iteration
8=1
S=4
S=8
S=16
S=32
S=64
S=128
many scales and benchmarks. AdaScale trains quality models. Training curves align closely in terms of Tr. all cases, n warms up gradually at the start training, even though all ir schedules are simple exponential or step decay functions (which are non- non-increasing in t).
Figure 3: AdaScale training curves.
For each benchmark, decay function for cifar10 0 and speech, and a step decay function otherwise. We use standard ir parameters for imagenet and yolo. Otherwise, imize the validation metric (to our knowledge, there are no standard schedules for solving speech and transf ormer with momentum-SGii SGD). We use momentum p 0.9 except for transformer, in which case we use 0.99 for greater training stability.
simple learning rate schedule. Specifically, Ir is exponential
tuned parameters that approximately max-
Figure (and Figure 1) contains AdaScale training curves for the benchmarks and many scales. Each curve plots the mean of five distributed training runs with varying random seeds. As S in- creases, AdaScale trains for fewer iterations but consistently preserves model quality. Illustrating AdaScale's approximate scale invariance, the training curves align closely when plotted in terms of scale-invarians iterations.
Table
Overview training benchmarks.
Name
Task
Model
Dataset
Metric
cifar10
Image classification
ResNet- 18 (v2)
CIFAR-10
Top-1 accuracy (%)
imagenet
Image classification
ResNet-50 (vl)
ImageNet
Top-1 accuracy (%)
speech
Speech recognition
Deep speech 2
LibriSpeech
Word accuracy (%)
cransformes
Machine translation
Transformer base
WMT-2004
BLEU
yolo
Object detection
YOLOv3
PASCAL VOC
mAP (%)

---

Under review as a conference paper at ICLR 2020
128
Val. Ace (56)
77
Ace (%)
77
Training loss
4.0
Scale S
68
68
3.1
59
59
2.2
VA
1,3
50
50
0 113k 225k
455k
4k
8k
12k
113k 225k
455k
113k 225k
455k
SS-invriiatt iteration
Iteration
S-invariant iteration T
S
S-invariant iteration
8-1
S 321641128
S 128]64132
Figure 4: Elastic AdaScaling. For imagenet, AdaScale is approximately scale invariant, if S changes abruptly 7. 133k, 225k). Unlike AdaScale, LSW degrades model quality this setting (see Table 2). Elastic scaling comparisons consider one random trial; future versions of this work will include five trials.
For S > 1, AdaScale's learning rate increases gradually during initial training, despite the fact that 1r is non-increasing. Unlike warm-up heuristics (Goyal et al., 2017), this behavior emerges naturally from principled algorithm, not hand-tuned user input. Thus, AdaScale provides not only a compelling alternative to warm-up but also plausible explanation for warm-up's success.
For imagenet, also consider elastic scaling. Here, the only change to AdaScale is that S changes abruptly after some iterations. We consider two cases: (i) S increases from to 64 at F; = Tsi / and from 64 128
Tsi/2, /,, and (ii) the scale decreases at the same points, from 128 to 64 to 32. In Figure 4, we include training curves from this setting. AdaScale remains approximately scale invariant, highlighting AdaScale's value for the common scenario of dynamic resource availability.
Table 2: Comparison of final model quality. Shorthand: AS=AdaScale, LSW=Linear scaling rule with warm-up, gray=model quality significantly worse than for S (5 trials, 0.95 significance), N/A=training diverges, #lasaict//=cllatie scaling with increasing/deerrasing scale (sce Figure 4). Linear scaling leads poor model quality as the scale increases, while AdaScale preserves model performance for nearly cases.
Total batch size
Validation metric
Training loss
Total iterations
Task
S
AS
LSW
AS
LSW
AS
LSW
cifar10
1
128
94.1
94.1
0.157
0.157
39.1k
39.1k
8
1.02k
94.1
94.0
0.153
0.161
5.85k
4.88k
16
2.05k
94.1
93.6
0.150
0.163
3.36k
2.44k
32
4.10k
92.8
0.145
0.177
2.08k
1.22k
64
8.19
93.9
76.6
0.140
0.272
1.41k
imagenet
76.4
1.30
1.30
451k
451k
16
4.10k
76.5
76.3
1.26
1.31
33.2k
28.2k
32
8.
76.6
76.1
1.23
1.33
18.7k
14.1k
64
16.4k
76.5
75.6
1.19
1.35
11.2k
7.04k
32.8k
1.14
1.51
7.29k
3.52k
Elastic
various
75.7
1.15
1,36
11.6k
7.04k
Flastic
various
76.6
73.8
1.23
1.46
13.7k
9.68k
speech
1
79.6
79.6
2,03
2.03
84.8k
84.8k
4
128
81.0
80.9
5.21
4.66
22.5k
21.2k
8
256
80.7
80.2
6.74
6.81
12.1k
10.6k
16
512
80.6
N/A
7.33
N/A
6.95k
5.30k
32
1.02k
N/A
8.43
N/A
4.29k
2.65k
transformer
2.05k
27.2
27.2
1.60
1.60
1.55M
1.55M
32.8k
27.4
1.60
1.60
108k
99.0k
32
65.5k
27.3
27.0
1.59
1.61
58.9k
49.5k
64
131k
27.6
26.7
1.59
1.63
33.9k
24.8k
128
262k
27.4
N/A
1.59
N/A
21.4k
12.1k
yolo
1
16
80.2
80.2
2.65
2.65
207k
207k
16
256
81.5
81.4
2.63
2.66
15.9k
12.9k
32
512
81.3
80.5
2.61
2.81
9.27k
6.47k
64
1.02k
81.3
70.1
2.60
4.02
5.75k
3.23k
128
2.05k
81.4
N/A
2.57
N/A
4.07k
1.62k

---

Under review as a conference paper at ICLR 2020
Single batch
AdaScale
LSW
Scaled SGD
5=1, 7339. 1k
S= 16, 331=39.1k
S 3=16,
37.1
S=16, 7=3.28k
10"
10
10
10
10:1
10
10a1
10a1
94.0%
Total 1r decrease
10
10
10
10
93.0%
10
10
10
10a
92.0%
10
10
10
10
91.0%
10
10
10
10
90.0%%
10
10
109
10'
10-1
Initial 1r
Initial 1r
Initial lr
Initial 1r
Figure 5: Scale invariance for many learning rate schedules. Heat maps cover the space of exponential decay ir schedules for cifar10. At scale I6, validation accuracies for AdaScale align closely with results for single-batch training, with the space 94+% schedules growing moderately with AdaScale. With LSW, no schedule achieves 94% accuracy. On the right, direct 1r search at scale 16 produces inferior results AdaScale (here the total iterations, 3.28k, is the average total iterations among 94+% AdaScale trials). Thus, AdaScale induces superior family of schedules for scaled training. The white 'x' indicates the 1r used for Figure 1.
As baseline for all benchmarks, we also evaluate linear scaling with warm-up (LSW). As inputs, LSW takes single-batch schedule 1rşı = Ir and single-batch steps Tşı = Tst. where 1r and Tst are the inputs to AdaScale. Our warm-up implementation closely follows Goyal al. (2017). LSW trains for [T's//S iterations, applying warm-up to the first 5.5% of iterations. During warm-up, the learning rate increases linearly from 1r (0) to S (O).
Table 2 compares results for AdaScale and LSW. LSW consistently trains for fewer steps, but doing so comes at a cost. As S grows larger, LSW consistently degrades model quality and sometimes di- verges. For these divergent cases, we also tested doubling the warm-up duration to 1 % of iterations, and training still diverged. contrast, AdaScale preserves model quality for nearly all cases.
As final comparison, Figure demonstrates AdaScale's performance on cifar10 with many dif- ferent schedules. We consider 13 grid of exponential decay schedules and plot contours of resulting validation accuracy. At scale 16, AdaScale results align with accuracies for single-batch training, illustrating that AdaScale is approximately scale-invariant for many schedules. Moreover, AdaScale convincingly outperforms direct search exponential decay schedules for scaled SGD at 5616. For training at scale, AdaScale provides a more natural learning rate parameterization.
SCALE-INVARIANT CONVERGENCE BOUND
We now present convergence bounds that formalize the approximate scale invariance of AdaScale. The bounds provide identical convergence guarantees for all scales, meaning that in terms of upper bounds on training loss, AdaScale is scale invariant. For comparison, we include an analogous bound for the linear scaling rule. Qualitatively, the bounds agree closely with empirical results.
Let us define F = minw F(w). Our analysis requires a few assumptions that are typical of SGD analysis of non-convex problems (see, for example, (Lei et al., 2017; Yuan al., 2019)):
Assumption He-Polyaak-Lojasiewiic.. For some a: > 0, F(w) F S 2a [F)())] for all w. Assumption (8-smooth). For some 3 > O, ||VF(w) FF( I| S B w w f'll all w, w'.
Assumption (Bounded variance). There exists a V 2 0 such that o² (w) S V for all w.
We emphasize that we do not assume convexity. The PL condition, which is perhaps our strongest assumption, proven to hold for some nonlinear neural networks (Charles Papailiopoulos, 2018).
We consider constant Ir schedules, which result in simple and instructive bounds. To provide context for the AdaScale result, we first present a straightforward bound for single-batch training:
Theorem 1 (Single- SGD bound). Given Assumptions 2, and 17 E (0, 28-1),, consider Algorithm I with S and 1r(() Defining 7 = 1)((2 - 71.3) and A 27 2 we have
E [ (WT)
F*] s - >) [ [F(wo) AA.
The bound describes two important characteristics of the single-batch algorithm. First, the sub- optimality converges in expectation to most A. Second, convergence to A + requires at most

---

Under review as a conference paper at ICLR 2020
iterations. We note similar bounds exist, under stronger variance assumption (Karimi et al., 2016; Reddi et al., 2016; De et al., 2017; Yin et al., 2018).
[Foo((((Wo) 1) (FF) (og((//oo(111 (1-2)-1))
Importantly, our AdaScale bound converges to this same A for all practical values of S:
Theorem 2 (AdaScale bound). Define A as in Theorem 1. Given Assumptions 1, 2. 3. S S y-, and 1j E (0, 2B "), define wr as the result of Algorithm with 1r(t) 17 and scale S. Then [F(ww) (1-7)
E [(F(wr)-
F=] +
This bound for AdaScale is scale invariant, it does not depend S. Like single-batch SGD, the suboptimality converges in expectation to at most A, but AdaScale achieves this for all scales. In addition, AdaScale speeds up training by factor F T T-1 Tt. That is, convergence to A + requires at most [ log((
F)))=*)/log"" log((1 -)] iterations (since Tsi S TT = FT).
As final comparison, we provide an analogous bound for linear scaling, which is not scale invariant: Theorem 3 (Bound for linear scaling rule). Define and A in Theorem 1. Given Assumptions 1, 2, 3, S S 7-' and E (0, 2(53) consider Algorithm I with 1r(()= = St7. We have
(3=Sp)) E (F(wT) - F*] < (1 11-7 (2-
ST
(F(wo)
F=] (211+(22500 ( 2-
A.
2-
Unlike Theorem 2, this bound converges to value that increases with S. In addition, smaller range of learning rates guarantees convergence. In practical terms, this means that linear scaling often leads to worse model quality and greater risk of divergence, especially for large S. These differences appear throughout our empirical comparisons in $4.
Finally, we note both Theorem and Theorem 3 require that S S , For practical problems, ? is small, and we can safely ignore this constraint. Otherwise single batch training would converge quickly, due to Theorem 1, and smaller scales would result in fast training.
6 RELATION TO PRIOR WORK
While linear scaling with warm-up is perhaps the most popular scaling rule, researchers have con- sidered few alternative strategies. "Square root learning rate scaling" (Krizhevsky, 2014: Li et al., 2014; Hoffer et al., 2017: You et al., 2018) multiplies learning rates by the square root of the batch size increase. Across scales, this preserves the covariance of the SGD update. Establishing this in- variant remains poorly justified, however, and often root scaling degrades model quality in practice (Goyal al., 2017: Golmant et al., 2018; Jastrzębski al., 2018). AdaScale adapts learning rates by making 7)2 EE || invariant across scales, which results in our scale-invariant bound from $5. Finally, we might also consider model-specific scaling rules, such as LARS for CNNs (You al., 2017). AdaScale solves the general problem (PI), making AdaScale applicable to many models.
Many prior works have also considered the role of gradient variance in SGD. McCandlish et al. (2018) study the impact of gradient variance on scaling efficiency. These general findings also apply AdaScale, as gradient variance similarly determines AdaScale's efficiency. Much like AdaScale, Johnson & Guestrin (2018) also adapt learning rates to lower amounts of gradient variance-in this case when using SGD with importance sampling. Because the variance reduction is relatively small in this setting, however, distributed training can have far greater impact training times. Lastly, many algorithms also adapt to gradient moments for improved training, given a fixed amount of variance see (Schaul et al., 2013; Kingma & Ba, 2015; Balles & Hennig, 2018), just to name few. AdaScale adapts learning rates across scales, which correspond to different amounts of gradient variance. Perhaps future algorithms will combine approaches in order achieve both goals.
DISCUSSION
SGD is not perfectly parallelizable. Unsurprisingly, the linear scaling rule can fail at large seales. In contrast, AdaScale accepts sublinear speedups in order to better preserve model quality. What do the speed-ups from AdaScale tell us about the scaling efficiency of SGD in general? For many problems, such imagenet with batch size 32.8k, AdaScale establishes lower bounds on SGD's scaling efficiency. An important remaining question is whether AdaScale is optimally efficient, or other practical algorithms achieve similar scale invariance with fewer iterations.
8

---

Under review as a conference paper at ICLR 2020
AdaScale provides useful new parameterization of learning rate schedules for large-batch SGD. We provide a simple 1r schedule, which AdaScale adapts to learning rates for scaled training. From this, warm-up behavior emerges naturally, which produces quality models for many problems and scales. Even in elastic scaling settings, AdaScale adapts successfully to the state of training. Given these appealing qualities, it seems important further study such learning rate schedules.
Based on our empirical results, as well as the algorithm's practicality and theoretical justification, believe that AdaScale is valuable for speeding up training in practice.
REFERENCES
D. Amodei, R. Anubhai, E. Battenberg, C. Case, J. Casper, B. Catanzaro, J. Chen, M. Chrzanowski, A. Coates, G. Diamos, E. Elsen, H. Engel, L. Fan, C. Fougner, T. Han, A. Y. Hannun, B. Jun, P. LeGresley, L. Lin, S. Narang, A. Y. Ng. S. Ozair, R. Prenger, Raiman, S. Satheesh, D. Seeta- pun, S. Sengupta, Y. Wang, Z. Wang, C. Wang, B. Xiao, D. Yogatama, J. Zhan, and Z. Zhu, Deep speech 2: End-to-end speech recognition English and Mandarin. In Proceedings of the 33rd International Conference on Machine Learning, 2016.
L. Balles and P. Hennig. Dissecting Adam: The sign, magnitude and variance of stochastic gradients. In Proceedings of the 35th International Conference Machine Learning. 2018.
Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In Proceedings of the 35th International Conference on Machine Learning, 2018.
S. De, A. Yadav, D. Jacobs, and T. Goldstein. Automated inference with adaptive batches. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In JEEE Conference Computer Vision and Pattern Recognition, 2009.
A. Devarakonda, M. Naumov, and M. Garland. Adabatch: Adaptive batch sizes for training deep neural networks. 1rXiv:1712.02000 1712.02029, 2017.
M. Everingham, I.. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman. The pascal visual object classes (VOC) challenge. International Journal of Computer Vision, 88(2):303-332 2010.
N. Golmant, N. Vemuri, Z. Yao, V. Feinberg, A. Gholami, K. Rothauge, M. W. Mahoney, and J. Gonzalez. On the computational inefficiency of large batch sizes for stochastic gradient descent. 1.ii:1111,,12411 2018
P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He. Accurate, large minibatch SGD: Training ImageNet in one hour. arXiv: 1tXiv:1706.02677, 2017.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 201
K. He, X. Zhang, S. Ren, and J. Sun. Identity mappings in deep residual networks. In European conference on computer vision, 2016b.
E. Hoffer, I. Hubara, and D. Soudry. Train longer, generalize better: Closing the generalization gap in large batch training of neural networks. In Advances in Neural Information Processing Systems 30, 2017.
Jain, S. M. Kakade, R. Kidambi, P. Netrapalli, and A. Sidford. Parallelizing stochastic gradi- ent descent for least squares regression: Mini- Mini-batching, averaging, and model misspecification. Journal of Machince Learning Research, 18(223):1 2018.
S. Jastrzębski, Z. Kenton, D. Arpit, N. Ballas, A. Fischer, Y. Bengio, and A. J. Storkey. Three factors influencing minima in SGD. In Proceedings of the 27th International Conference on Artificial Neural Networks, 2018.
T. B. Johnson and C. Guestrin. Training deep models faster with robust, approximate importance sampling. In Advances in Neural Information Processing Systems 31, 2018.

---

Under review as a conference paper at ICLR 2020
H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal -raaiinggrrientttt meth- ods under the polyak-tojje -ojjskktjj condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2016.
D. Kingma and Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations. 2015.
P. E. Kloeden and E. Platen. Numerical Solution of Stochastic Differential Equations. Springer, 1992.
A. Krizhevsky. Learning multiple layers of features from tiny images, Technical report, 2009.
A. Krizhevsky. One weird trick for parallelizing convolutional neural networks. 1rXiv: 1404.5977, 2014.
L. Lei, C. Ju, J. Chen, and M. Jordan. Nonconvex finite-sum optimization via SCSG methods. In Advances in Neural Information Processing Systems 30, 2017.
M. Li, Zhang, Chen, and A. Smola. Efficient mini-batch training for stochastic optimization. In Proceedings of the 20th ACM SIGKDD Interational Conference on Knowledge Discovery and Data Mining, 2014.
H. Lin, H. Zhang, Y. Ma, T. He, Z. Zhang, S. Zha, and M. Li. Dynamic mini-batch SGD for elastic distributed training: Learning in the limbo of resources. arXiv: 1901. 2019.
Ma, Bassily, and M. Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning. In Proceedings of the 35th International Conference on Machine Learning, 2018.
S. McCandlish, J. Kaplan, D. Amodei, and OpenAl Dota Team. An empirical model of large-batch training. arXiv:1812.0611 2018.
V. Panayotov, G. Chen, D. Povey, and S. Khudanpur. Librispeech: An ASR corpus based on public domain audio books. In IEEE International Conference Acoustics, Speech and Signal Pro- cessing, 2015.
S.J. Reddi, A. Hefny, S. Sra, B. Póczoós, and A. Smola. Stochastic variance reduction for nonconvex optimization. In Proceedings of the 33rd International Conference on Machine Learning, 2016.
Redmon and A. Farhadi. YOLOv3: An incremental improvement. arXiv:1804.02767, 2018.
T. Schaul, S. Zhang, and Y. LeCun. No more pesky learning rates. In Proceedings of the 30th International Conference Machine Learning, 2013.
C. Shallue, J. Lee, J. Antognini, J. Sohl-Dickstein, R. Frostig, and G. E. Dahl. Measuring the effects of data parallelism on neural network training. Journal of Machince Learning Research, 20(1 12):111)149 2019.
S. Smith, Kindermans, C. Ying, and Q. V. Le. Don't decay the learning rate, increase the batch size. In Proceedings of the 6th International Conference Learning Representations, 2018.
A. Vaswani, N. Shazeer, N. Parmar, Uszkoreit, Jones, A. N. Gomez, t.. Kaiser, and Polo- sukhin. Attention is all you need. In Advances in Neural Information Processing Systems 31, 2017.
D. Yin, A. Pananjady, M. Lam, D. Papailiopoulos, K. Ramchandran, and Bartlett. Gradient diver- sity: key ingredient for scalable distributed learning. In Proceedings of the 2 International Conference on Artificial Intelligence and Statistics, 2018.
Y. You, I. Gitman, and B. Ginsburg. Large batch training of convolutional networks. arXiv:1708 03888, 2017.
Y. You, J. Hseu, C. Ying, J. Demmel, K. Keutzer, and C.-J. Hsich. Large-batch training for LSTM and beyond. In NeurlPS Workshop on Systems for MI. and Open Source Software, 2018.
10

---

Under review as a conference paper at ICLR 2020
Z. Yuan, Y. Yan, R. Jin, and T. Yang. Stagewise training accelerates convergence of testing error over sgd. In Advances in Neural Information Processing Systems 32, 2019.
H. Zhang, M. Cisse, N. Dauphin, and D. Lopez-Paz. Mixup: Beyond empirical risk minimization.
In International Conference on Learning Representations, 2018.
Zhang. T. He, H. Zhang. Z. Zhang, J. Xie, and M. Li, Bag of freebies for training object detection neural networks. arXiv: 191::1902.04133 2019.

---

Under review as a conference paper at ICLR 2020
A PROOFS
In this appendix, we prove the results from $5 and $3. We first prove a lemma in $A.1, which we apply the proofs. We prove Theorem 1 in $A.2, Theorem 2 in $A.3, and Theorem in $A.4. We also prove Proposition I in $A.5 and Proposition 2 in $A.6.
A.1 KEY LEMMA
Lemma 1. Given Given Assumptions 1, and 17 E (0,28-)) define 17((2 (3)) and A Consider Algorithm with 1r(t) 1). For all iterations we have
27 3V..
E [[,(w,) F*] (F(w)) F F- Twn) +A.
Proof. We prove this by induction. To simplify notation, let us define F(w) = F(w) F*. For t 0, we have
[[F(wo)] F(wa) - F(wo) IT re?) +A.
Note we are using the convention [[ = 1. For 2 1, assume the inductive hypothesis
t-
B[F(w:-1)] (woo)
II (1 + +A.
Applying Assumption (smoothness) and the update equation w, = -W-1 - 71-1 we have
F(w:) s F(w:-1) (VF(W:))). w. wi-1) + f || wr-1ll 2
= F(w:-1) - (t----))---(((((((---- -)).))) + +
28 |
Taking the expectation with respect to the S random batches from step I, we have
F(w.) w--1] s ((.-1) Ft-
+ L |lB: 1| we-1
Now taking the expectation with respect to the distribution of w,-1, it follows that
E [w:))
< IE [(w
T 17 [ VV + +r2 S [1B
(2)
For the last term, we have
E
E
[g
VF
[ VF(w:-1)) IVF
E
W + 1/F (w:-1)1
B [[02(w--1) (W:-1) + [F
r--1
[[FF + +v)
E
(3)
Combining (3) with (2), we have
E F(w:) < E F(w.-1)
r--17111 - // m ||VF(w: + 28
2
(1- [(w.-1)) +
(4)
In this last step, applied Assumption condition) and plugged in definitions for and A.
12

---

Under review as a conference paper at ICLR 2020
To complete the proof, apply (I):
t-2
(1- +1 + +
B[F(w:)] - (1 - -1-17)
F(wo)
+
t==0
L-1
F(wu)
II - rr7) + A.
#0m0
A.2 PROOF OF THEOREM 1
Theorem (Single-batch SGD bound). Given Assumptions 1, and 1j E (0, 2,3-),, consider
Algorithm I with S and 1r(() 1). Defining 7 = n)a(2 - -133) and A 27 11 PV, we have
[[((T) - F*] = (1 - (F FT] +
Proof. The theorem is special case of Lemma In particular, Algorithm with inputs 1r(() = 7, = and T iterations is equivalent to Algorithm 2 with T't = T and the same scale and learning rate inputs. This follows from the fact that r; = for all iterations of AdaScale when 1. Thus, we can obtain the result by plugging / T into the bound from Lemma 1.
A.3 PROOF OF THEOREM 2
Theorem (AdaScale bound). Define A as in Theorem 1. Given Assumptions 1, 2, 3, S S r and 1 E (0, 23--),, )), define WT as the result of Algorithm 2 with 1r(l) 17 and scale S. Then
E [[F(wT) (1- [F(wo) F*] +
Proof. Let T denote the total iterations for Algorithm 2. Applying Lemma 1, we have
T-1
E (F(..) - F*] (F(wo) - F*)
- r2) +A.
(5)
===0
Now note that for any r 2 1 and x E [0, 1J. we have
rw < - x)".
(6)
This holds because for any 2 and æ E [0, 1]. the function (1 xx=x"" is convex in æ, and - rz is tangent to this function æ Thus,
II (11-re)) S (1-2)2770
Note that this requires 1 rxY 2 0 for all t, which is true because T₁ S Now plugging (7) into (5),
E [F((,) F*] (F(wo) F*)(1 - -5 + A (F(wo) - F*)(1 71 + A.
In the last step, we use the stopping condition of Algorithm 2 (Tst S ΣT-1 rd).
L
A.4 PROOF OF THROREM? 3
Theorem (Bound for linear scaling rule), Define y and A as in Theorem 1. Given Assumptions 1, 3, S S5555= 1 and 17 (0,2(53)- consider Algorithm I with 1r(() St.. We have
E F(((w) - F*] (1 1-7. (2-Sh0)
ST [F(wo) - F=] +
2-m8
A
22-
13

---

Under review as a conference paper at ICLR 2020
Proof. We reduce the theorem to special case of Theorem 1. Define X = (x(1), ..... ,x()), where ( X' for each i [S), and x(1) x(() are jointly independent. Denote by X' the distribution
of &. Also define
8
f(w,x) x)
f(w, xw,
5 1=1
follows that for any w.
Ex | [V/(w, x) - VF(w)] = (0)(w) 5
1
The algorithm described in Theorem 3 is identical running Algorithm with scale 1, batch distri- bution X. loss f. learning rate 1r(()= Sn, and variance upper bound 5. Plugging these values into Theorem 1, we have
B[F(wT) F S (1 Sno Sm13) F*) Sn3V5-1
2x (2 Sm133
T
Sr
2-9n 2-13 (F(wo) - F*] + 2-3
2-n
A
)) 2-
ST
[F(wo)
- F*] +
2-n8
A.
2-5
The last step follows from (6).
A.5 PROOF OF PROPOSITION
Proposition 1 (Scale-invariant SGD for deterministic gradients). If d2(() 0 all w E RRd, then applying identity scaling Algorithm results in scale-invariant algorithm.
Proof. Since the gradient variance is zero, the prrpute_gradient function returns VF(w,)) which does not depend on S. Thus, the algorithm does not depend on S in this case, which im- plies that it is scale-invariant.
A.6 PROOF OF PROPOSITION 2
Proposition 2 (Scale-invariant SGD for extreme stochasticity). Consider fixed covariance matrix Σ $4 learning rate value ij E Rso. and training duration T. For a given v E RR assume W fwf(wxx) ~ N(VF(()) vE), and apply linear scaling to Algorithm I with 1rsi(t) = =v- y11ij i) and Ts vT. The resulting scaled SGD algorithm is scale-invariant in the limit -> +00.
Proof. The scaled SGD algorithm runs for [DT/S] iterations and follows the update rule
W, 5i Siv (w.))
Sn E
Here & is normally distributed with E [&]] O and cov &t) s E. In the limit + +oo, this difference equation converges to stochastic differential equation on the interval [0] (Kloeden & Platen, 1992, Chapter 9):
dw = F(w))dt
where W(t) ~ I).
Since this SDE does not depend on S, the algorithm is scale-invariant in this limit.
B ADDITIONAL DETAILS ON EMPIRICAL COMPARISONS
This appendix provides additional details of our experiment set-up.
14

---

Under review as a conference paper at ICLR 2020
B.1 LEARNING RATE SCHEDULES
We describe the ir schedules for each training benchmark in Table 3. We use two learning rate families: exponential decay and step decay. Using parameters 7/. d. and wi, we define 1r(t) = Mod(t//Ts)) for exponential decay families and 1r(t) = mn 1/t>wi for step decay fam- ilies. Here Tsi denotes the total iterations for scale 5 1. Note that in all cases, schedules and no warm-up.
simple
Table 3: Learning rate schedules for training benchmarks.
Benchmark
Learning rate famliy
17u
d
R0s
cifar10
Exponential decay
0.08
0.0133
N/A
imagenet
Step decay
0.1
0.1
150,240, 300,480, 400,640
speech
Exponential decay
1.4 x10-
0.05
N/A
transformez
Step decay
0.01
0.1
1,440,000
yolo
Step decay
2.5 x10
0.1
160,000, 180,000
For imagenet and yolo, used standard learning rate schedules from (Goyal et al., 2017) and (Zhang et al., 2019). For cifar10, speech, and transformer, we chose learning rate parameters, via hand-tuning, that approximately maximized model quality. This necessary for speech and transformer, since our reference implementations train with the Adam optimizer (Kingma & Ba, 2015), and momentum-SGD requires different learning rate values.
B.2 WARM-UP IMPLEMENTATION
Our warm-up procedure closely follows the strategy of Goyal et al. (2017). We apply warm-up for the first 5.5% of training iterations- denote this number by Ws. During warm-up, the learning rate increases linearly, starting at the initial learning rate for single-batch training and finishing at times this value. After warm-up, Goyal et al. (2017). we modify this scaled schedule so that the total iterations, including warm-up, proportional to S-1 For step-decay schedules, we omit the first Ws iterations after warm-up. For exponential decay schedules, we compress the scaled schedule by Ws iterations, using slightly faster decay.
apply linear scaling the single-batch schedule. Following
B.3 BENCHMARK-SPECITS IMPLEMENTATION DETAILS
Here we describe implementation details that are specific to each benchmark task.
B.3.1 cifar10
We train ResNet-18 (preactivation) models (He al., 2016b), using the standard training data split for CIFAR-10 (Krizhevsky, 2009). We use weight decay 5 x 10 4. For batch normalization, we use parameters momentum 0.995 and scaling parameters. We apply standard data augmentation during training. Specifically, we pad images x and random crop to x 32, and we also apply random horizontal reflections.
x 10-5, and we do train the batch normalization
B.3.2 imagenet
For ImageNet classification (Deng et al., 2009), we train ResNet-50 models (He et al., 201 6a). Our implementation closely follows the implementation 2 convolutions on 3 3 layers. For each block's final batch normalization layer, we initialize the batch norm scaling parameters to (and we initialize to 1 everywhere else). We use weight decay parameter 10 4 Since each GPU processes 128 examples per batch,
Goyal et al. (2017). We use stride-
ghost batch normalization (Hoffer et al., 2017) with ghost batch size 32. We resize imput images to 224x 224 x For data augmentation, we apply random cropping and left-right mirroring during training.
15

---

Under review as a conference paper at ICLR 2020
B.3.3
speech
We use Amodei al. (2016)'s Deep Speech model architecture. The model consists of two 2D convolutional input layers, five bidirectional RNN layers, one fully connected layer, and softmax outputs. Each convolutional layer has 32 filters. The RNN layers use GRU cells with hidden size 800. We apply batch normalization to the inputs of each layer. The batch norm parameters are momentum 0.997 and e = 10 The loss is CTC loss. The inputs to the network are log spectrograms, which we compute using 20ms windows from audio waveforms sampled at 16 kHz. The training data is the t ra in-iinnlll can-cles ean-100 and t tr aeaan-cclean-ie ean 360 partitions of the OpenSI LibriSpeech Corpus, which amounts to 460 hours of recorded speech. We evaluate models the dev-clesd partition.
B.3.4 transformer
We train Transformer base models (Vaswani et al., 2017). We use dynamic batching with at most 256 tokens per example. In Table 2, the "batch size" is the maximum number of tokens processed per iteration. Our implementation closely follows that of Vaswani et al. (2017). Unlike Vaswani et al., we use only the final model for evaluation instead of the average of the last five checkpoints. We train the WMT 2014 English-German dataset and evaluate on the newstest2014 test set.
B.3.5 yolo
We train YOLOv3 models (Redmon Farhadi, 2018). To achieve high mAP scores, we also apply mixup (Zhang et al., 2018) and class label smoothing, following (Zhang et al., 2019). We also use focal loss. We use batch normalization momentum= 0.9 and weight decay = x 10 We resize input images to 416 x 416 (for both training and validation). We report mAP values at IOU threshold 0.5. We use the Pascal VOC 2007 trainval and 2012 trainval datasets for training and the 2007 test set for validation (Everingham et al., 2010). During training, initialize the darknet-53 convolutional layers with weights trained on ImageNet.
B.4 MISCELLANEOUS
In practice, wall time speed-upe also depend on system scaling efficiency. Since most aspects of sys- tem scaling relate orthogonally to the training algorithm, we limit our scope to algorithmic aspects of training.
For Figure 5, one dimension defines initial value 1r(0), and the second dimension specifies total decrease 1r(Tss)) (10) For single-batch training, we use T 39.1 x 10 steps. We run AdaScale and the LW baseline at S = 16, and we compare the final validation accuracies.
C ROBUSTNESS TO AVERAGING PARAMETER
In this appendix, test the robustness of AdaScale to the averaging parameter 0 for estimating gain ratios (see $3.3). When 0, AdaScale does not average estimates of gradient moments. The closer 0 is to 1, the more that AdaScale averages across iterations.
Using the cifar10 benchmark, we compare four values of f at scales $ and S = 32. The case 0 1 5/1000 corresponds to the cifar10 experiment for Figure 1. We average the resulting metrics over five trials. Figure 6 contains the training curves.
We also include final metric values in Table 4.
For the three smaller settings 0, the results align very closely. This suggests that AdaScale is robust the choice of f. When 0 5/10000, that smoothing more significantly biases gain ratio estimates, which leads to more contrasting results.
D ADDITIONAL EMPIRICAL RESULTS
This appendix provides additional empirical results.
16

---

and steps Under review as a conference paper at ICLR 2020
S 8
Train objective
.65
Learning rale
Gain Pt
Acc
.40
4
0.2
2
0.1
80.0
0
2k
4k
2k
4k
6k
4k
6k
2k
4k
6k
Iteration
Iteration
Iteration
Iteration
9
S/10
S/100
S/1000
0
S/10000
S
32
Val. Acc (%)
94.0
Train objective
32
Learning rale
0.9
87.0
Gain
16
80.0
.15
1k
2k
1k
2k
Iteration
Itcration f
Iteration
Iteration
0=
0 5/100
0
S/1000
0
S/10000
Figure 6: AdaScale training curves with varying moving average parameter.
Table 4: AdaScale final metrics with varying moving average parameter.
Final val. accuracy (%)
Final train objective
Total iterations
S
8
1 S/10
94.0
0.153
5.75k
1 - S/100
94.1
0.154
5.78k
S/1000
94.1
0.153
5.85k
1 5/10000
94.1
0.147
6.45k
0
94.0
0.145
2.02k
1 S/100
94.1
0.147
2.03k
1 - S/1000
94.1
0.145
2,08k
1 5/10000
94.1
0.136
2.46k
D. EFFECT OF NUMBER OF STEPS ON LINEAR SCALING WITH WARMUP
As can be seen from empricial results in $4, AdaScale takes more steps than LSW for all scales. In order to understand the contribution of increased step number to the improved performance of Ada- Scale, we compare AdaScale another algorithm called LSW+. LSW+ runs for the same number of steps as AdaScale. It scales the steps axis of the LSW learning rate schedule while keeping the learning rate axis the same. Specifically,
takes single-batch schedule 1rş1 Tsi Tas as inputs, where TAS is the average number of iterations (over five trials) taken by AdaScale. It applys warm-up to the first 5.5% of TAs iterations. During warm-up, the learning rate increases linearly from 1 (0) to S (0):
As can be seen from Table 5, the behavior of I.SW is generally similar to that of L.W. As expected, LSW+ improves upon LSW, but LSW+ still degrades model quality at larger scales for all problems. For speech, transformer, and yolo, LSW+ diverges at the largest scales.
We also note that LSW+ is not practical algorithm, because it requires either (i) first running AdaScale to determine the number iterations; or (ii) tuning the number iterations. The second path is inconvenient in practice. Moreover, it seems for a fair comparison, would also need to consider AdaScale with tuning. Thus, even if LSS++ matched AdaScale, which does not, AdaScale would still be preferable to LSW+.
17

---

Under review as a conference paper at ICLR 2020
transformer. S-16
transformen --128
16
128
Gain ratio Pt
12
96
8
64
4
32
SUK
100%
10k
20k
Iteration t
Iteration
Offfine evaluation
Online estimate
Figure 7: Gain ratios for transformer. Plots compare moving average estimates to values computed
offline (using 1000 batches).
D.2 GAIN RATIO ESTIMATION
Our online gain ratio estimates align closely with offline estimates (computed by averaging over 1000 batches). Figure 7 demonstrates this for the transforme task.
D.3 cifar10 SCALE INVARIANCE CURVES
Figure shows additional plots for the cifar10 task. Notably, training loss curves various scales and full view of the learning rate curves are shown.
Table Comparison AS and LSW+. Shorthand: AS=AdaScale, LSW+=Stretched lincar scaling rule
with warm-up, takes the same number steps as AS gray=model quality significantly worse than for S (5 trials, 0.95 significance), N/A-training diverges
Total hatch size
Validation metric
Training loss
Total iterations
Task
S
AS
LSW+
AS
I.W+
AS
L.W+
cifar10
1
128
94.1
94.1
0.157
0.157
39.1k
39.1k
1,02k
94.1
94.0
0.153
0.145
5.85k
5.85k
16
2.05k
94.1
94.1
0.150
0.136
3.36k
3.36k
32
4.10k
94.1
94.0
0.145
0.128
2.08k
2.08k
64
8.19k
93.9
93.0
0.140
0.128
1.41k
1.41k
imagenet
1
256
76.4
76.4
1.30
1.30
451k
451k
16
4.10k
76.5
76.5
1.26
1.27
33.2k
33.2k
32
8.19k
76.4
1.23
1.24
18.7k
18.7k
64
16.4k
1.19
1.20
11.2k
128
32.8k
76.5
75.5
1.14
1.20
7.29k
7.29k
speech
1
79.6
79.6
2.03
2.03
84.8k
84.8k
4
128
81.0
81.0
5.21
4.22
22.5k
22.5k
8
256
80.7
80.7
6.74
6.61
12.1k
12.1k
16
512
80.6
N/A
7.33
N/A
6.95k
6.95k
32
1.02k
N/A
8.43
N/A
4.29k
4.29k
transformer
2.05k
27.2
27.2
1.60
1.60
1.55M
1.55M
27.4
1.60
1.59
108k
108k
32
65.5k
27.3
27.3
1.59
1.59
58.9k
58.9k
64
131k
27.6
27.1
1.59
1.60
33.9k
33.9k
128
262k
27.4
N/A
1.59
N/A
21.4k
21.4k
yolo
16
80.2
80.2
2.65
2.65
207k
207k
16
256
81.5
81.9
2.63
2.47
15.9k
15.9k
32
512
81.3
81.7
2.61
2.42
9.27k
9.27k
64
1.02k
81.3
80.6
2,60
2.51
5.75k
5.75k
128
2.05k
81.4
N/A
2.57
N/A
4.07k
4.07k
18

---

Under review as a conference paper at ICLR 2020
Learning rate Y/+
Val. Acc (%)
94.0
Val. Ace (%)
94.0
Training loss
0.9
0.6
87.0
87.0
0.3
80.0
115
36k
Iteration
S-invariant iteration fi
S S-invariant iteration Ti
Iteration
8=8
S=16
S=32
S-64
1=128
Figure 8: AdaScale training curves for cifar10. AdaScale trains quality models at various scales.
Learning rate m/
128
Gain ratio
12
64
S-invariant iteration 72
S-invariant iteration TI
S 128
128.64432
S-32
S
Figure 9: Learning rate adaptation for elastic AdaScaling. Gain ratio and learning rate curves for elas- tic scaling scenarios align with the corresponding curves for constant scaling scenarios, despite abrupt scale changes. (at 133k, 225k, dotted lines)
D.4 ELASTIC SCALING
Learning rate and gain ratio curves for the two dynamic scaling scenarios we consider (discussed in $4) align surprisingly well with the corresponding curves for the scenarios where the scale is kept constant throughout the training. This is shown in Figure 9, The abrupt change in scale causes the gain ratio change quickly which in turn leads an almost immediate change in learning rate. This allows the algorithm to quickly adapt to varying scales.
19


Reviews:
[{"review_id": "SyxIwzyRKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents and evaluate an algorithm, AdaScale SGD, to improve the stochastic gradient decent in distributed training. The proposed algorithm claims to be approximately scale-invariant, by adapting to the gradient's variance. The paper is well-written and generally easy to read, although I didn't check all theory in the paper. \n\nThe approach is evaluated using five benchmarks (networks / dataset combinations) from different  domains. The results are promising and seems solid. \n\nThe paper is good and I like it, although I think the novelty and contribution is slightly too low for ICLR. The kind of tweaking and minor optimizations to provide some adaptivity (or similar) in existing and established algorithms and approaches that is presented in this is paper is very important from a practical perspective. However, from a scientific perspective it provides no significant contribution.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this 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": "S1xeppfZcr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors use the PL condition to motivate a formula for learning rate selection. (they bound their loss by a quadratic with fixed curvature alpha, and use this to get learning rate).\n\nTheir analysis very closely mirrors one presented in \"Gradient Diversity\" paper, it uses the same assumptions on the loss. IE compare A.1 in the paper to the B.5 in \"Gradient Diversity\"\n\nGradient Diversity solves for batch size B after which linear learning rate scaling starts to break down, while this paper instead fixes B and solves for learning rate. Two results are comparable, if you take their learning rate formula in section 3.2 (need formula numbers) and solve for B which gives learning rate halfway between B=1 and B=inf, you get the same expression as \"critical batch size\" in equation 5 of gradient diversity paper.\n\nIt's not immediately obvious how to invert formula in Gradient Diversity paper to solve for learning rate, so I would consider their learning rate formula an interesting result.\n\nI also appreciate the breadth of experiments used for evaluation. \n\nThe biggest issue I have with the paper is that I can't tell if it's better of worse than linear learning rate scaling from their experiment section. All of their experiments use more iterations for AS evaluation uses than for LSW evaluation. They demonstrate better training (and test) losses for AS, but because of extra iterations, I can't tell that the improvement in training loss is due to number of iterations, or due to AS scaling.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1lFOBTMKH", "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 novel rule for scaling the learning rate, called the gain ratio, for when the effective batch size (induced by synchronous distributed SGD) is increased. This rule for the gain ratio uses estimates of the trace of the covariance and the norm of the true gradient to determine the appropriate steplength. This results in a method with a R-linear convergence guarantee to a neighborhood that is not dependent on $S$ (which is called scale-invariant). The algorithm additionally tracks the sum of the gain ratios in order to determine the \"effective\" number of iterations taken, and cut the steplength appropriately. \n\nStrengths:\n\nThe gain ratio proposed in this paper is intuitive. I particularly like how the algorithm estimates the mean and variance information in an unbiased manner to determine an appropriate scaling for the steplength. The method is able to attain a R-linear rate of convergence and appears to perform well in practice for a wide variety of applications. The gain ratio is simple to estimate within a distributed framework.\n\nWeaknesses:\n\nI found some of the terms in the paper to be unclear or ill-defined. The original use of the term \"scale\" was unclear to me. Does this refer to the number of nodes in the distributed implementation? What is its relationship to batch size?\n\nI found the definition of scale invariance in this paper to also be unclear on first read. The claim is that the algorithm is scale invariant if its final model does not depend on $S$. What is the \"final model\"? As currently defined, the current analysis does not guarantee that the algorithm will reach the same final model (assuming that $f(w, x) = \\ell(h(w, x), y)$, i.e. a composition of a loss function and model), as the PL condition only ensures that one reaches a global minimum, which may not be unique. In fact, the analysis only guarantees convergence to a neighborhood. The description within the analysis appears to imply that scale-invariance is a property of the algorithm attached to its convergence property. Is this the case?\n\nThe definition of scale invariance is also already used in optimization to mean algorithms that are not modified when the objective is multiplied by a constant or an affine transformation. This adds to the lack of clarity, and I would suggest the authors use a different term for this kind of invariance (batch size invariant, or something like that?).\n\nIs the theoretical comparison between SGD and AdaScale fair? Note that one can prove a stronger convergence result with SGD because one can actually attain a Q-linear rate of convergence to a neighborhood (for a proof, see for example, Bottou, et al. (2018)). In particular, one should have something like (in the paper's notation):\n$$\\mathbb{E}[F(w_T) - F^*] \\leq (1 - \\gamma)^T [F(w_0) - F^*] + \\Delta.$$\nThis means that one can actually guarantee a fixed ratio of decrease in expectation to a neighborhood, whereas AdaScale converges linearly but not with a fixed ratio. \n\nSome other small questions regarding the theory and experiments:\n- Is there a reason why batch normalization was not tried for the CIFAR-10 experiments?\n- Is it possible for $r_{t - 1} \\gamma > 1$?\n- Why was it necessary to estimate $\\sigma^2 (w_t)$ and $\\|\\nabla F(w_t)\\|^2$ by both aggregating at the current iteration and exponential averaging? What happens if exponential averaging is removed?\n- What are the limitations of this method? How large of a batch size can one use with AdaScale before the algorithm breaks down (if at all)?\n\nAdditional Comments:\n\nThe algorithm is quite reminiscient of the steplength prescribed in Bollapragada, et al. (2018), which consider the steplength: \n$$( 1 + \\frac{\\sigma^2(w_t)}{\\|\\nabla F(w_t)\\|^2})^{-1}.$$\nThis gain ratio prescribed in this paper is the ratio between this quantity for two different batch sizes. Is there a clear explanation for why the relationship between these two quantities would arise?\n\nThis method could also be used for determining an appropriate scaling of the steplength in the sequential setting, when a larger batch size is used. Has this been considered?\n\nDespite the concerns regarding the clarity in writing and the rigor in the theory of the paper, I think that the algorithmic idea proposed in this paper is interesting, novel, and practical. Because of the lack of clarity and rigor, I have given this paper a weak reject, but I would be happy to accept the paper if my concerns above were addressed in the final manuscript.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked 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 thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Main summary: Novel rule for scaling learning rate, known as gain ration, for which the effective batch size is increased.

Discussion: 
reviewer 2: main concern is reviewer can't tell if it's better of worse than linear learning rate scaling from their experiment section.
reviewer 3: novlty/contribution is a bit too low for ICLR.
reviewer 1: algorthmic clarity lacking.
Recommendation: all 3 reviewers recommend reject, I agree.
Decision: Reject