Loss Landscape Dependent Self-Adjusting Learning Rates in Decentralized Stochastic Gradient Descent
Authors: Wei Zhang
Mingrui Liu
Yu Feng
Xiaodong Cui
Brian Kingsbury
David S Kung
Yuhai Tu
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Decentralized Training
Loss Landscape Dependent Noise
Self-Adjusting Learning Rate
Learning Dynamics

Abstract: Distributed Deep Learning (DDL) is essential for large-scale Deep Learning (DL) training. Synchronous Stochastic Gradient Descent (SSGD) 1 is the de facto DDL optimization method. Using a sufficiently large batch size is critical to achieving DDL runtime speedup. In a large batch setting, the learning rate must be increased to compensate for the reduced number of parameter updates. However, a large
learning rate may harm convergence in SSGD and training could easily diverge. Recently, Decentralized Parallel SGD (DPSGD) has been proposed to improve distributed training speed. In this paper, we find that DPSGD not only has a system-wise runtime benefit but also a significant convergence benefit over SSGD in the large batch setting. Based on a detailed analysis of the DPSGD learning dynamics, we find that DPSGD introduces additional landscape-dependent noise that automatically adjusts the effective learning rate to improve convergence. In addition, we theoretically show that this noise smoothes the loss landscape, hence allowing a larger learning rate. This result also implies that DPSGD can make learning rate tuning much easier for tasks that require careful learning rate warmup (e.g, Attention-Based Language Modeling). We conduct extensive studies over 18 state-of-the-art DL models/tasks and demonstrate that DPSGD often converges in cases where SSGD diverges when training is sensitive to large learning rates. Our findings are consistent across three different application domains: Computer Vision (CIFAR10 and ImageNet-1K), Automatic Speech Recognition (SWB300 and SWB2000) and Natural Language Processing (Wikitext-103); three different types of neural network models: Convolutional Neural Networks, Long Short-Term Memory Recurrent Neural Networks and Attention-based Transformer Models; and two optimizers: SGD and Adam.

Loss Landscape Dependent Self-Adjusting Learning
Rates in Decentralized Stochastic Gradient Descent
Anonymous Author(s)
Affiliation
Address
email il
Abstract
Distributed Deep Learning (DDL) is essential for large-scale Deep Learning (DL. training. Synchronous Stochastic Gradient Descent (SSGD) is the de facto DDL optimization method. Using a sufficiently large batch size is critical to achieving DDL runtime speedup. In large batch setting, the learning rate must be increased to compensate for the reduced number of parameter updates. However, large learning rate may harm convergence in SSGD and training can easily diverge. Recently, Decentralized Parallel SGD (DPSGD) has been proposed to improve distributed training speed. In this paper, we find that DPSGD not only has runtime benefit, but also significant convergence benefit over SSGD in the large batch setting. Based on a detailed analysis of DPSGD learning dynamics, we find that DPSGD introduces additional audscape-dependee noise that automatically adjusts the effective learning rate to improve convergence. In addition, we theoretically show that this noise smooths the loss landscape, hence allowing larger learning rate. This result also implies that DPSGD can greatly simplify learning rate tuning for tasks that require careful learning rate warmup (e.g, Attention Based Language Modeling). We conduct extensive studies over 18 state-of-the- DL models/tasks and demonstrate that DPSGD often converges in cases where SSGD diverges when training is sensitive to large learning rates. Our findings are consistent across three different application domains: Computer Vision (CIFAR10 and ImageNet- IK), Automatic Speech Recognition (SWB300 and SWB2000) and Natural Language Processing (Wikitext-100 103); three different types of neural network models: Convo- lutional Neural Networks, Long Short-Tern Memory Recurrent Neural Networks and Attention-based Transformer Models; and two optimizers: SGD and Adam.
2
8
10
11
12
14
16
18
20
21
22
23
Introduction
24
25
Deep Learning (DL) has revolutionized AI across application domains: Computer Vision (CV) [29, 14], Natural Language Processing (NLP) [50], and Automatic Speech Recognition (ASR) [15]. Stochastic Gradient Descent (SGD) the fundamental optimization method used in DL training.
28
27
28 Due to massive computational requirements, Distributed Deep Learning (DDL) is the preferred mechanism to train large scale Deep Learning (DL) tasks.
29
The degree of parallelism in a DDL system is dictated by batch size: the larger the batch size, the more parallelism and higher speedup can be expected. However, large batches require larger learning 32 rate and overall they may negatively affect model accuracy because (1) large batch training usually
30
31
33 converges to sharp minima which do not generalize well [24], and (2) large learning rates may violate
34 the conditions (i.e., the learning rate should be less than the reciprocal of the smoothness parameter)
35 required for convergence in nonconvex optimization theory [11]. Although training longer with large
38 batches can lead to better generalization [18], doing so gives up some or all of the speedup we seek.
In the literature, SSGD is also called "Centralized Synchronized Stochastic Gradient Descent". In this paper. we use these two terms interchangeably.
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

ImageNet 0000, 8S-8192
SWB300 0td-0.01, BS-8192
Wikitext-100 std=0.01, B5-256
100.
55G0
10
Accuracy(3)
Heldour-L Loos
50
0
-0
10
5520-150e
2000-100
150
Fanchs
Ebarhs
Enochs
(a)
I-BN, Ima-
LSTM SWR300,
(c)
GPT2 Wikitest-
geNes, BS8192
BS$192
105, B8256
Figure I: SSGD (red) does not converge when the learning rate needs to be large (e.g., large batch setting or short warmup period). Figure la shows model accuracy (higher is better), while Figure Ib and Figure Ic show heldout loss (lower is better). Injecting Gaussian noise (blue) does not enable SSGD to escape poor local minima. In contrast, DPSGD (green) converges using the same hyper- parameter setup. The detailed task descriptions and training recipes are given in Sections 4.3 and 4.5. BS denotes Batch-Size.
37 Through meticulous hyper-paane parameter design (e.g., learning rate schedules) tailored to each specific
38 task, SSGD-based DDL systems have enabled large batch training and shortened training time for some challenging CV tasks [12, 54] and NLP tasks [55] from weeks to hours or less. However, it is observed that SSGD with large batch size leads to large training loss and inferior model quality for ASR tasks [58], as illustrated in Figure 1b (red curve). Here, found for other types of tasks (e.g.
39
40
42 CV and NLP) and DL models, large batch SSGD has the same problem (Figures la and Ic).
43
Several SSGD variants have been proposed to address large batch training problems: (1) local SGD, i.e., SGD-based algorithms with periodic averaging. where learners conduct global averaging after multiple steps of gradient-based updates [13, 36, 64]: (2) SSGD based algorithm with second- order statistics, including adaptive gradient algorithms [55, 54] and algorithms for exploring the information from the gradient covariance matrix [51]; and (3) SSGD-bass bbbdedded algorithms
44
45
46
smoothed landscape [35, 9]. in which specifically designed loss landscape smoothing algorithms are used. All of these approaches require global synchronization and/or global statistics collection, which makes
48
50 them vulnerable to stragglers.
51 Decentralized algorithms, such as Decentralized Parallel Stochastic Gradient Descent (DPSGD) [33].
52 are surrogates for SSGD in machine learning. Unlike SSGD, where each learner updates its weights
53 by taking a global average of all learners' weights, DPSGD updates each learner's weights by taking
54 a partial average (i.e., across a subset of neighboring learners). In contrast to the existing variants additional calculation and global synchronization. Traditionally 56 DPSGD is a second-choice to SSGD, and is used only when the underlying computational resources less homogeneous (i.e., a high latency network or computational devices rumning at different 58 speeds). Little thought has been given to the question of whether there are any convergence benefits for DPSGD, especially in the large batch setting.
of SSGD, DPSGD requires
59
60 In this paper, we find that DPSGD [33] greatly improves large batch training performance, as illustrated by the green curves in Figure 1. Since DPSGD only uses partial average of neighboring learners' weights, each learner's weights differ from the weights of other learners. The differing weights between learners are an additional source of noise in DPSGD training. The key difference between SSGD, SSGD with Gaussian noise (denoted as "SSGD"" in this paper) and DPSGD is the source of noise during the update, and this noise directly affects performance in deep learning. This naturally motivates us to ask Why does decentralized training outperform synchronous training in the large batch setting? More specifically, we try to understand whether these performance differences are caused by differences in noise. We answer this question from both theoretical and empirical perspectives. Our contributions are:
61
62
63
64
86
68
70
We analyze the dynamics of DDL algorithms, including both SSGD and DPSGD. We show, both theoretically and empirically, that the intrinsic noise in DPSGD automatically adjusts the effective learning rate when the batch size is large to help convergence. Note that the intrinsic noise comes completely for free in the DPSGD algorithm, and we show that it has
71
72
73

---

74
a loss-landsee landscape smoothing effect. Guided by our theoretical results, we also investigate training tasks where careful learning rate warmup schemes are required (e.g., Transformer models) [56, 42, 52] and find that DPSGD can work with much shorter learning rate warmup period thus simplifying syper-parameter tuning.
75
76
77
78
We conduct extensive empirical studies of 18 CV, ASR, and NLP tasks with state-of-the-art CNN, LSTM, and Transformer models. Our experimental results demonstrate that DPSGD consistently outperforms SSGD, across application domains and Neural Network (NN) architectures the large batch setting, without any eyper-paramete tuning. To the best of our knowledge, DPSGD is the only generic algorithm that improve SSGD large batch training and shorten learning rate warmup period for this many models/tasks. Furthermore, unlike other solutions, DPSGD does not require global synchronization.
79
81
83
85
The remainder of this paper is organized as follows. Section 2 details the problem formulation and learning dynamics analysis of SSGD, SSGD", and DPSGD; Section 3 and Section 4 detail the empirical results; Section 5 discusses related work; and Section 6 concludes the paper.
86
87
86
2
Analysis of stochastic learning dynamics in SSGD and DPSGD
89
We first formulate the dynamics of an SGD based learning algorithm with multiple (n >> 1) learners indexed by j = 3...3.... following the same theoretical framework established for single learner [3]. At time (iteration) 1, each learner has its own weight vector wīz (t), and the average weight vector (t) is defined as: W. (t) = n "E (t). Each learner j updates its weight vector according the cross-entropy loss function I, (t) (17) for minibatch (t)(t) that is assigned to it at time f. The size of the local minibatch is B, and the overall batch size for all learners n.B Two multi-learner algorithms, SSGD and DPSGD, are described below.
90
91
92
98
94
95
96 (1) Synchronous Stochastic Gradient Descent (SSGD): the synchronous algorithm, each learner j E [1, nl] starts from the average weight vector Wh and moves along the gradient of its local loss function (t) evaluated at the average weight w.:
wi + W. (t) (VL (W,
(1)
39
where a is the learning rate.
100
(2) Decentralized Parallel SGD (DPSGD): In the DPSGD algorithm [33], each learner computes the gradient at its own local weight (t). The learning dynamics follows:
101
(t + 1) = - aVL (0 (tī)()).
(2)
102
where (t) is the starting weight set to be the average weight of a subset of "neighboring" learners of learner-j, which corresponds to the non-zero entries in the mixing matrix definee [33] (note that Wa,- = WT if all learners are included as neighbors).
103
104
By averaging over all leamners, the learning dynamics for the average weight W,, for both SSGD and DPSGD can be written formally the same way as:
106
N. (1 + 1) = (t) aga,
where Ha = =n =n -E= Tj is the average gradient and T, is the gradient from learner-.. The difference between SSGD and DPSGD the weight at which gj computed: gj = (T),(0) (t)) is
107
108
computed at W., for SSGD; h, = (L (wi (t)) is computed at w7, for DPSGD. The deviation of the weight for learner-j from the average weight is defined as duū, = w W.. It is easy to see that dut (t + +1) = (T,,(() (f) ((ū - (t)], which depends on gradients at different points on the loss landscape.
109
111
112
113
2.1 Understanding DPSGD from the Optimization Perspective
114
The main difference between DPSGD and SSGD that the stochastic gradients are calculated at different weights in DPSGD, while SSGD's 's stochastic gradient is calculated at the same weight. Intuitively, DPSGD explores more space than SSGD, which may help explain the empirical success of DPSGD. We formalize this intuition into the following theorem, which shows that DPSGD is optimizing a smoother landscape than SSGD.
115
116
117
118
This is also called the "gossip matrix" in the literature, e.g.. [27].
3

---

119
Theorem 1. Denote Fi by the filtration generated by all the random variables until the t-th iteration. Suppose n. is large enough that - VINi(t)(ū -. En (L (1.())( S
120
almost surely, and assume 6tū,(t) Fi-1 iid. o(0,021) with i = 1, 1,..., 1. Then from the
121
122
(t- 1)-h iteration to 1-th iteration, SSGD and DPSGD are doing one step of stochastic gradient
descent on two different functions L(T) and L(w)= = Essae [L + (()( Fr-1), respectively.
123
The DPSGD loss (ui)) is smoother than the SSGD loss L(wt) if L(Ø) is Lipschitz continuous.
124
125
Remark: The proof of Theorem can be found in Appendix A. Here, we briefly mention its
126
y/l for any x, y, where I, is the smoothness parameter of f- The landscape of the function ʃ is smoother when I
implications. A function f is defined as 1.-smooth if || (xx) V [y(y)l I 1.11=
127
128
is smaller. Assume T(ii)) is G-LLipschtzz continuous, i.e., [T((wT) [( S Gl|uū - l7| then by using Lemma 2 of [39], we know that the DPSGD landscape L(wi 2G -moooh. According to the convergence theory of SGD and DPSGD for nonconvex functions [11, 33, 12], the largest learning rate one can choose to guarantee convergence is +. For SSGD with the original loss landscape L, I, can be very large (even close to +oo due to the nonsmooth nature of the ReLU activation) while L, of the smoothed loss function L for DPSGD is much smaller. This explains why we can use a larger learning rate in DPSGD as the landscape DPSGD sees has a smaller gradient-Lipschit constant I, than that in SSGD.
129
130
131
132
133
134
135
It is important to note that le of the smoothed loss function L in DPSGD depends on the standard deviation ow of weights from different learners. Since ow depends on the loss landscape and changes with time (see Fig. 2(b)), the smoothing effect in DPSGD is self-adjusting it is strong in the initial stage of training when the loss landscape is rough and becomes weaker as training progresses when the loss landscape becomes smoother. Our theoretical result suggests that this self-adjusting smoothing effect is responsible for DPSGD's convergence with a large learning rate in the large batch
137
138
139
140
141
142
size setting. Next, we elaborate on this insight and verify it in simple network for classification using the MNIST dataset.
143
Note that the Theorem 1 is only one-step analysis. People may be interested in extending the analysis to trajectory-baatt based analysis. We provide a sketch here. If we consider the perturbed objective (w) = E3 [L + 6)). where comes from the intrinsic noise of DPSGD, then we can utilize the descent lemma as shown in [11] to prove that DPSGD can converge to a stationary point of [ww) in polynomial time. However, without the inherent noise of DPSGD, the landscape is rough and that is the reason why SSGD diverges. SSGD may not be able to converge to the stationary point of L(w) (since the large learning rate in large batch setting makes the descent lemma not applicable in this effect in SSGD, so SSGD does not
145
146
147
148
149
150
case) or i(w) (since there is no noise and mondscape-smoothing optimize the smoothed landscape). This is also consistent with our empirical evidence.
151
152
153
2.2
DPSGD Introduces Landseape-Deppendent Self-Adjusting Learning Rate that Helps Convergence
154
155
To understand the implication of the smoothing effect in DPSGD (Theorem 1) for learning dynamics, we define an effective learning rate ag = ago 0/|l@l| by projecting the weight displacement vector
156
157
n = agæ onto the direction of the gradient g = V (w..) of the original loss function L at w..
158
The learning dynamics, Eq. 3, can be rewritten as:
(l + 1) = (I - o.. + 71,
(4)
159
where the "noise" term V/ = -0g. + a.. describes the random weight dynamics in directions orthogonal to g. The noise term has zero mean (m_)μ = 0 and the noise strength is characterized by its variance (t) = ||
160
161
162
The effective learning rate is related to the noise strength: a = -a² 1
which indicates that higher noise strength A leads lower effective learning rate ae. The DPSGD noise
|l/l /
163
ApP is larger than the SSGD noise As by an additional noise term A (2) (> 0) that originates from
164
the difference of local weights (w7,) from their mean (w.):: ADP = As + A (2), Appendix B for

---

details. By expanding A (2) w.I.t. j'üi, we obtain the average A ()) over minibatch ensemble {u}:
186
(A (1))) = a² (1|m
VL (m.)))))
(5)
= Σ
167
where Hu = Vi is the Hessian matrix of the loss function and Civ = =n=" the weight covariance matrix. From Eq. 5 and the dependence of aa on A, it clear that the effective learning rate in DPSGD depends directly on the loss landscape (H) and indirectly via the weight variance, o = Tr(C), which decreases as the loss landscape becomes smooth (see Fig. 2(b)).
owgzdws, is
188
170
171 It is important to stress that the noise 771 in Eq.4 is not an artificially added noise, It is intrinsic to the use of minibatches (random subsampling) in all SGD-based algorithms (including SSGD and DPSGD). The noise is increased in DPSGD due to the weight difference among different learners varies in weight space via its dependence on the loss landscape, as explicitly shown in Eq. 5. However, besides its landscape dependence, SGD noise scales inversely noise in SSGD scales as I/(nB), which is too small to be effective for large batch size nBB A main finding of our paper is that the additional uudscape-dependee
172
173
174
(owi), The noise strength
175
176
with the minibatch size B [3]. With synchronized learners,
noise A (2) in DPSGD can make for the small SSGD noise when n is large and help enhance convergence in the large batch setting.
178
179
180
The landscape dependent smoothing effect in DPSGD (shown in Sec. 2.1) indicates that a₂ in DPSGD reduced at the beginning of training when the landscape is rough. To demonstrate effects of the landscape-dependeer self-adjusting learning rates, we did detailed analysis in numerical experiments used n 5 learners with each learner fully
182
183
using the MNIST dataset. In this experiment, connected network with two hidden layers (50 units per layer) and we used Wæs = T7 for DPSGD.
184
185
We focused on the large batch setting using nB 2000 and a large learning rate a As shown in Fig. 2(a), DPSGD converges to a solution with a low loss (2.1% test error), but SSGD fails to converge.
186
187
(b)
DPSGD
SSGD
S8G1"
10
02
0.5
DPSGD
L
10
10
03
10 2
500
1000
1500
2000
0
500
1000
1500
2000
time:bateh)
(attebattc))
Figure 2: (a) Comparison of different multi-learner algorithms, DPSGD (green), SSGD (red), and SSGD* (blue) for large learning rate 1. The adaptive learning rate allows DPSGD to converge while SSGD fails to converge. A fine-tuned SSGD* also converges but to an inferior solution. (b) The effective learning rate for DPSGD a. (DPSGD) is self-adaptive to the landscape it is reduced in the beginming of training when gradients are large and recovers to ~ a when the gradients are small. The weight variance o? has the opposite landscape-dependence a, and decreases with training time.
188 To understand the convergence in DPSGD, we computed the effective learning rate (a²) and the weight variance (o during training. As shown in Fig. 2(b) (upper panel), the effective learning rate ae is reduced in DPSGD during early training (0 < < 700). This reduction ag is caused by the stronger noise A (2) DPSGD (see Fig. Appendix B), which essential for convergence when gradients are large in the beginning of the training process. In the later stage of the training process
190
191
193
when gradients are smaller, the andscape-dependee DPSGD noise decreases and a. automatically increases back to be x to allow fast convergence. From Eq. 5, the landscape-dependent noise in
5

---

AlexNet
VGG
VGG-BN
bs=256
Baseline
56.31/79.05
69,02/88.66
70.65/89.92
Ir=1x
1=-0.01
Ir=0.1
bs=2048
SSGD
54.29/77.43
67.67/87.91
70.36/89.58
8x
DPSGD
53.71/76.91
67.28/87.55
69.76/89.31
40=4
SSGD
0.10/0.50
0.10/0.50
65.39/86.51
1=16x
DPSGD
52.53/76.01
66.44/87.20
68.86/88.82
bs=8192
SSGD
0.10/0.50
0.10/0.50
0.10/0.50
l==32x
DPSGD
49.01/73.00
65.00/86.11
63.55/85.43
Table 1: ImageNet- Top-1/Top-5 model accuracy (%) comparison for batch size 2048, 4096 and 8192. All experiments are conducted 16 GPUs (leamner)) with batch size per GPU 128, 256 and 512 respectively. Bold text represents the best model accuracy achieved given the specific batch size and learning rate. The batch size 256 baseline is presented for reference. bs stands for batch-size, Ir stands for learning rate. Baseline Ir set to 0.01 for AlexNet and VGG11, 0.1 for the other models. In the large batch setting, we use learning rate warmup and linear scaling as prescribed in [12]. For rough loss landscape like AlexNet and VGG, SSGD diverges when batch size is large whereas DPSGD converges.
195
DPSGD depends on the weight variance. As shown Fig. 2(b) (lower panel), the weight variance of has a time-dependent trend that is opposite to ag; o is large in the beginning of training when the landscape is rough and decreases as training progresses and the landscape becomes smoother.
197
To show the importance of the landscape-dependen weight variance, we used SSGD", which injects 1.i.d. a Gaussian noise with a constant variance to weights in SSGD, i.e., by setting 8vūz ~ NN og) with a constant o-- We found that SSGD" fails to converge for most choices of noise strength oî Only by fine tuning of can SSGD* converge, but to an inferior solution with much higher loss and test error (5.7%) as shown in Fig. 2(a).
199
200
202
Finally, in addition to helping convergence, we found that the landscape-depender noise in DPSGD 203
204
can also help find flat minima with better generalization in the large batch setting (see Appendix for details).
Experimental Methodology
206
207
We implemented SSGD and DPSGD using Py PyTorc, OpenMPI, and NVidia NCCL. We ran exper- iments on a cluster of two 8-V 1000GPU x86 servers. For CV tasks, we evaluated on CIFAR-I0
208
209
(50,000 training samples, 17MBB and ImageNet- IK (1.2 million training samples, 140GB). For
210
ASR tasks, we evaluated on SWB-300 (300 hours training data, 4,000,000 samples, 30GB) and
211
SWB-2000 (2000 hours training data, 30,000,000 samples, 216GB). For the NLP task, we evaluated
on 1oritext-103(100 million tokens, I 180MB). In all, we evaluate 18 state-of-the-art NN models: 15 CNN models, 2 6-layer bi-directional LSTM models, and 16-layer GPT-2 transformer model. We summarize the model sizes and training times in Table 6 of Appendix D. Also refer to Appendix D for hardware configuration, software implementation, dataset and Neural Network (NN) model details.
213
215
Experimental Results
216
217
All the large batch experiments are conducted on GPUs (learners). Batches are evenly distributed among learners, e.g., with sixteen learners, each learner uses local batch size that is one sixteenth the overall batch size. learner randomly picks neighbor with which exchange weights in each DPSGD iteration [59].
218
219
4.1
SSGD and DPSGD Comparison on CV Tasks (CIFAR-10 and ImageNet-1K))
222
On ImageNet- K we test 6 CNN models AlexNet, VGG11, VGGII-BN, ResNet-50, ResNext-50 and DenseNet-161 161. Among them, AlexNet and VGG have rougher loss landscapes and can only work with smaller learning rates, while VGG11-BN ResNet-50, ResNext-50, and DenseNet-161
223
225 have smoother loss landscapes thanks to the use BatchNorm or Residual Connections, and thus work with larger learning rates. We use the same baseline training recipe prescribed in [4]:

---

SWB-300
Figure 3: SSGD diverges when the learning rate warmup period is 75 iterations while DPSGD con- verges with a warmup period as short as 25 itera- tions. (Wikitex1003, GPT-2)
bs2048
bs4096
bs8192
SSGD
1.58
10.37
10.37
DPSGD
1,59
1.60
1.66
SWB 2000
bs2048
bs4096
bs8192
SSGD 1,46
1.46
10.37
Baseline
DPSGD 1.45
1.47
1.47
SSGD (w/ 75 iters)
Table 2: Heldout loss comparison for SSGD and
Validaaiion Loos
DPSGD (w/ 25 iters)
DPSGD, evaluated on SWB-300 and SWB-2000.
There are 32000 classes in this task, held-out loss 10.37 (i.e. In $20000 indicates complete diver- gence. bs stands for batch size.
4
0 50
100 125 Eoochs
150
175
200
227
batch size 256, initial learning rate 0.01 for AlexNet and VGG-11 and 0.1 for the other 4 models, learning rate anneals by 0.1 every 30 epochs, 100 epochs in total. To study the model performance
229 in the large batch setting, we follow the large batch size learning rate schedule prescribed in [12]: learning rate warmup for the first 5 epochs and then learning rate linear scaling w.r.t batch size.
230
231
For example, in the AlexNet batch-size 8192 experiment, the learning rate is gradually warmed-up from 0.01 0.32 in the first epochs, annealed to 0.032 from epoch 31 epoch 60, annealed to
232
233
0.0032 from epoch 61 to epoch 90, and annealed to 0,00032 from epoch 91 to epoch 100. SSGD and
234
DPSGD achieve comparable model accuracy in the large batch setting (see Table 10 in Appendix E.6).
235
Most noticeably, when batch-size increases to 8192, SSGD diverges with AlexNet, VGGII, and
236
VGG11-BN whereas DPSGD converges as shown in Table 1. Figure 9 in Appendix E.6 details the model accuracy progression versus epochs in each setting. Please see our detailed analysis of DPSGD
237
238
vs SSGD on CIFAR-10 10 tasks throughout Appendix E.1 Appendix E.5 where we document the
DPSGD and SSGD comparison and loss landscape visualization (contour 2D projection and Hessian 2D projection), which show that DPSGD usually leads to much flatter optima than SSGD, and thus better generalization in the large batch setting.
240
242
Summary For rough loss landscapes like AlexNet and VGG, DPSGD converges whereas SSGD diverges in the large batch setting.
243
244
4.2
SSGD and DPSGD Comparison on ASR tasks
Unlike CV tasks where CNNs and their residual connection variants are the dominant models, ASR tasks overwhelmingly adopt RNN/S STM models that capture sequence features. Furthermore, Batch- Norm is known not work well in RNN/LSTM tasks [31]. Finally, there over 32,000 different classes with wildy uneven distribution in our ASR tasks due to the Zipfian characteristics of natural language. All in all, ASR tasks present a much more challenging loss landscape than CV tasks to optimize over.
246
248
249
250
For the SWB-300 and SWB-2000 tasks, we follow the same learning rate schedule proposed in [57]: we use learning rate 0.1 for baseline batch size 256, and linearly warmup the learning rate w.r. the baseline batch size for the first 10 epochs before annealing the learning rate by 1 for the remaining
252
v/2 10 epochs. For example, when using a batch size 2048, we linearly warmup the learning rate to 0.8 by the end of the 10th epoch before annealing. Table 2 illustrates heldout loss for SWB-300 and
254
255
256
SWB-2000 In the SWB-300 task, SSGD diverges beyond batch size 2048 and DPSGD converges
257
well until batch size 8192. In the SWB-2000 task, SSGD diverges beyond batch size 4096 and DPSGD converges well until batch size 8192. Figure 10 in Appendix E.7 details the heldout loss progression versus epochs.
258
280
Summary For ASR tasks. SSGD diverges whereas DPSGD converges baseline model accuracy in the large batch setting.
281
262
4.3
Noise-injection and Learning Rate Tuning
In 6 out of 17 studied CV and ASR tasks, large batch setting leads to a complete divergence in 263
SSGD: EfficientNet-BO. AlexNet, VGGIL, VGGII-BN, SWB-300 and SWB-2006 As discussed in
7

---

AlexNet
VGG11
VGGI I-BN
SSGD
0.10/0.50
0.1000.00
0.10/0.50
=3"=32x
DPSGI
49.010/73.00
65.004/86.11
63.546/85.44
SSGD
0.10/0.50
0.10/0.50
70.11/89.47
1r=16x
DPSGD
49.26/73.14
62.046/83.98
69.108/89.C
SSGD
46.40/70.25
45.32/70.61
69.54/89.22
1r=8x
DPSGD
47.78/71.89
56.52/79.92
68, 88.98/88.78 78
SSGD 41.77/66.44
50.20774.83
68.61/88.57
1r=x
DPSGD
42.18/66.96
48.52/73.33
67.98/88.22
Table 3: ImageNet- learning rate tuning for AlexNet VGGI1, VGGI1 with batch-size 8192.
Bold text in each column indicates the best top- 1op-1/to--S. accuracy achieved across different learning rate and optimization method configurations for the corresponding batch size. DPSGD consistently delivers the most accurate models. *The learning rate 1x used here corresponds to batch size 256 baseline learning rate, and we still adopt the same learning rate warmup, scaling and annealing schedule. Thus 32x refers linear learning rate scaling when batch size is 8192. By reducing learning rate to 16x, 8x and 4x, SSGD can escape early traps but still lags behind compared to DPSGD in most cases.
SWB-300
SWB-300
SWB-200
(bs4096)
(bs8192)
(bs 8192)
SSGD
10.37
10.37
10.37
1='=2.6332
DPSGD
1.60
1.66
1.47
SSGD
10.37
10.37
10.37
1r=0.8/.6
DPSGD
1.65
1.73
1.48
SSGD
1.76
10.37
1,51
1r0.8/0.8
DPSGD
1.77
1.80
1.52
SSGD
1.92
2.05
1,58
00-2244.4
DPSGD
1.94
2.00
1.59
Table 4: Decreasing learning rate for SWB-300 and SWB-2000 (bs stands for batch-size). Bold text in each column indicates the best held-out loss achieved across different learning rate and optimization method configurations for the corresponding batch size. DPSGD consistently delivers the most accurate models. *learning rate 1.6 is used for bs4096 and learning rate 3.2 is used for 198192. We still adopt the same learning rate warmup, scaling and annealing schedule (baseline learning rate is 0.1 for batch size 256).
285
Section 2. the intrinsic landscape deppndeen noise in DPSGD effectively helps escape early traps (e.g.- saddle points) and improves training by automatically adjusting the learning rate. In this section, we demonstrate these facts by systematically adding Gaussian noise (the same as the SSGD* algorithm in Section 2) and decreasing the learning rate. We find that SSGD might escape early traps but still results in a much inferior model compared to DPSGD.
286
267
269
270
Noise-injection In Figure 1, we systematically explore Gaussian noise injection with mean 0 and standard deviation (std) ranging from 10 to 0.00001 via binary search (i.e. roughly 20 configurations for each task). We found in the vast majority of the setups, poise-injection cannot escape early traps. In EfficientNet-Bi BO, only when std is set to 0.04, does the model start to converge, but to very low accuracy (test accuracy 22. 15% SSGD vs 91. 13.13% in DPSGD). In the SWB-300 case, when std is 0.01, SSGD shows an early sign of converging for the first 3 epochs before it starts to diverge. the AlexNet, VGGI1, VGG11-BA, BBN, and SWB-2000 cases, we didn't 't find any configuration that can escape early traps. Figure characterizes our best-effort Gaussian noise tuning and its comparison against SSGD and DPSGD. A plausible explanation is that Gaussian noise injection
271
272
273
274
275
276
278
escapes saddle points very slowly, since Gaussian noise is isotropic and the complexity for finding local minima is peneension-depedder [10]. Deep Neural Networks are usually over- over-parameterized (i.c., -ighnsiinnss,,,,,,... so it may take long time to escape local traps. In contrast, the heightened noise in DPSGD is anisotropic [3, 8] and can drive the system to escape in the
280
282
283
right directions.
Learning Rate Tuning setting, we systematically tune down the learning rates. Table and Table compare the model quality trained by SSGD and DPSGD using smaller learning rates in the large batch setting, for ImageNet and
To make stterrise-divergeer SSGD training converge in the large batch
285
8

---

287
ASR tasks. Table 9 in Appendix E.3 illustrates the similar learning rate tuning effort for CIFAR-10 tasks. As we can see, by using a smaller learning rate, SSGD can escape early traps and converge. however it consistently lags behind DPSGD in the large batch setting. Morever, DPSGD does not depend on such an exhaustive learning rate tuning to achieve convergence. DPSGD can simply follow the learning rate warm-up and linear scaling rules [12] whereas SSGD requires much more stringent learning rate tuning. This implies DPSGD practitioners enjoy a much larger degree of freedom when it comes to hyper- hhper-paramett parameter tuning in the large batch setting than the SSGD practitioners.
288
280
292
Summary By systematically introducing mandssape--ndepedeee noise and reducing the learning rate, 295
294
SSGD could escape early traps (e.g., saddle points), but results in much inferior models compared to DPSGD in the large batch setting.
296
4.4
DPSGD and SSGD Runtime Comparison
296
In Appendix F, we detail runtime comparison between DPSGD and SSGD and demonstrate DPSGD consistently runs faster than SSGD. We also compare DPSGD with LAMB[55], state-of-the-ard optimizer specifically designed for synchronous large-batch training, demonstrating that DPSGD can avoid straggler problems in distributed training.
300
302
4.5
SSGD and DPSGD Comparison on NLP tasks (Wikitext-103)
For NLP tasks such as Masked Language Modeling (MLM) [6, 50], careful learning rate warmup scheme needs to be designed so that learning rate grows from 0 to a desired learning rate gradually.
304
305
Too short a warmup period often leads divergence and practitioners need restart training, which wastes huge computational resources[42, 52, 56]. We test our theory by finding the shortest viable
308
307
learning rafe warmup period for SSGD and DPSGD. We use the hyper-parameter settings prescribed
308
in [52], warmup learning rate 0 to 2.5 x 10-4 in the first 64000 samples (i.e., 250 iterations of to zero on top of an Adam optimizer. We then shorten the learning rate warmup period and check convergence. Figure 3 and Table 5 show that SSGD diverges
309
batch size 256) and then
310
311
when the learning rate warmup period is shorter than 100 iterations, while DPSGD converges with a warmup period as short as 25 iterations. Figure Ic shows that injecting independent random noise into
312
313
SSGD (in the same fashion as Section 4.3) does not help SSGD escape early training traps. These experiments corroborate our theory that DPSGD can leverage loss landscape noise to self-adjust the
314
315
learning rate.
Warmup(iters)
250
100
75
50
25
15
SYNC
3.09
3.07
7.26
7.26
7.26
7.26
DPSGD
3.08
3.053
3.06
3.08
3.09
7.26
Table 5: Validation loss comparison when shortening the learning rate warmup period. DPSGD can converge with a much shorter warmup. All experiments are conducted on GPUs (learners). Wikitext- GPT-2 model, 200 epochs training in total.
Related Works
316
317
Please see Appendix G
Conclusion
318
319
In this paper, we find that in the large-batch and large-learning-rate setting, DPSGD yields comparable model accuracy when SSGD converges; moreover, DPSGD converges when SSGD diverges. We then investigate why DPSGD outperforms SSGD for large batch training. Through detailed analysis on small-scale tasks and an extensive empirical study of diverse set of modern DL tasks, we conclude noise, which is strengthened in the DPSGD system, self-adjusts the effective learning rate according to the loss landscape, helping convergence. This self-adjusting learning rate effect is a mere by-product of the inherent Doss-landscape-deeendee dependent-noise of the
320
321
322
323
that the mendscape-dependee
324
325
326
DPSGD training algorithm and requires no additional computation, no additional communication tuning. The theory was originally developed to understand why DPSGD outperforms SSGD in the large batch setting for CV and ASR tasks. The same theory can be also verified in NLP tasks where when carefully designed learning rate warmup scheme is required.
and no additional
328

---

References
330
331
[1] Carlo Baldassi, Christian Borgs, Jennifer T. Chayes, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes. Proceedings of the National Academy of Sciences, 1 113(48):E7655- E7662. 2016.
332
333
334
335
[2]
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgc: Biasing gradient descent into wide valleys, 2016.
337
338
[3] Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks. 2018 Information Theory and Applications Workshop (ITA), Feb 2018.
339
340
341
[4] Soumith Chintala. PyTorch ImageNet Examples, 2020. Available at https//giituab.com/yyoorrh cxample//tee/mastermmaggnnn
342
343
[5] J. Deng, W. Dong, R. Socher, L. Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248 248-255,222 2009.
345
346
[6] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies. Volume I (Long and Short Papers), pages 417 Minneapolis. Minnesota, June 2019, Association for Computational Linguisties.
347
348
349
350
[7] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: I 11008, 2017.
352
88 Yu Feng and Yuhai Tu. The inverse critical for finding flat minima. Proceedings of the National Academy Sciences, 1 11((9), 2021.
relation in stochastic gradient descent is
355
356
[9] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-awarr mini- mization for efficiently improving generalization. ICLR, 2021.
357
358
[10] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online online stochastic gradient for tensor decomposition. In Conference on Learning Theory, pages 797- 842, 2015.
380
361
[1] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
382
363
[12] Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangging Jia, and Kaiming He. Accurate, large minibatch SGD: training imagenet in 1 hour. CoRR, abs/1706.02677, 2017.
364
385
366
[13] Vipul Gupta, Santiago Akle Serrano, and Dennis DeCoste. Stochastic weight averaging in parallel: Large-batch training that generalizes well. ICLR, 2020.
368
[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2015.
389
370
[15] Geoffrey Hinton, Li Deng, Dong Yu, George Dahl, Abdel rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara Sainath, and Brian Kingsbury. Deep neural networks for acoustic modeling in speech recognition. Signal Processing Magazine, 2012.
371
372
373
374
[16] Geoffrey E. Hinton and Drew van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the Sixth Annual Conference on Computational Learning Theory, COLT '93, pages 5-13, New York, NY, USA, 1993. ACM.
376
377
[17] Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1::1442, 1997.
[18] Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap large batch training of neural networks. In Advances in Neural Information Processing Systems, pages 1731-1741, 2017.
379
10

---

381
[19] Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang. Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. CoRR, abs/1704.04861, 2017.
382
384
[20] G. Huang. Z. Liu, L.. Van Der Maaten, and K. Q. Weinberger. Densely connected convolutional
385
networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2261-2269, 2017.
386
387
[21] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. ICML, 2015.
388
389
[22]
Stanistaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint arXiv:171..04233 2017.
391
392
[23]
Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos J Storkey. Finding flatter minima with sgd. In ICLR (Workshop). 2018.
[24] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: 04836, 2016.
395
[25] D. P. Kingma and J. L. Ba. ADAM: method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
398
399
[26] Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? arXiv preprint arXiv: arXiv:182.006/75. 2018.
[27]
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 3478-3488 PMLR, 2019.
402
403
(28) Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Computer Science Department, University of Toronto, Tech. Rep, 144)77 2009.
405
406
[29]
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097-1105, 2012.
408
409
[30]
Sameer Kumar, Victor Bitorff, Dehao Chen, Chiachen Chou, Blake Hechtman, HyoukJoong Lee, Naveen Kumar, Peter Mattson, Shibo Wang, Tao Wang. Yuanzhong Xu, and Zongwei Zhou. Scale MLPerf-0.6 models on Google TPU-v3 Pods. arXiv e-prints, page Xiv: arXiv:1909.00 1909.0976,, September 2019.
410
411
412
413
[31] César Laurent, Gabriel Pereyra, Philémon Brakel, Ying Zhang, and Yoshua Bengio. Batch normalized recurrent neural networks, 2016.
414
415
[32] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 6389-6399. Curran Associates, Inc., 2018.
416
417
418
419
[33] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 5330 5340, 2017.
420
421
422
423
[34] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In JCML, 2018
424
425
[35] Tao Lin, Lingjing Kong, Sebastian Stich, and Martin Jaggi. Extrapolation for large-batch training in deep learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6104. PMLR, 13-18 Jul 2020.
426
427
429
[36] Tao Lin, Sebastian U. Stich, and Martin Jaggi. Don't use large mini-batches, use local SGD.
430
ICIR, 2020.
[37] Kang Liu. Train CIFARIO with PyTorch, 2020. Available at http:///ggiinbbocoomnnggghhhnno cifar.
431
11

---

433
[38]
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. ICLR, 2017.
434
435
[39] Yurii Nesterov and Vladimir Spokoiny, Random gradient- minimization of convex functions. Foundations of Computational Mathematics, 17(2):27-5566 2017.
436
437
[40] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. In Advances in Neural Information Processing Systems, pages 5947-5956, 2017.
438
439
[41] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally-normalizeed margin bounds for neural networks. arXiv preprint arXiv:/707.099: 2017.
440
442
443
[42] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. 2018.
[43] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
446
447
[44] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
[45] Mark Sandler, Andrew G. Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chich Chen. Inverted residuals and linear bottlenecks: Mobile networks for classification, detection and segmentation. CVPR, abs/ 8011 1801.04311,,, 2018.
450
452
[46] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference on Learning Representations, 2015.
453
454
[47] Samuel Smith and Quoe Le. A bayesian perspective on generalization and stochastic gradient descent. arXiv preprint arXiv: 2017.
455
456
[48] Christian Szegedy. Wei Liu, Yangqing Jia, Pierre Sermanet, Scott E. Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. CoRR, abs/1409,48422, 2014.
457
458
459
[49] Mingxing Tan and Quoe V. Le. Efficientnet: Rethinking model scaling for convolutional neural networks. ICML, abs/1905. 1946, 2019.
460
[50] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E. ukasz, Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett, editors. Advances in Neural Information Processing Systems 30, pages 5998-6008. Curran Associates, Inc., 2017.
462
463
484
465
[51] Yeming Wen, Kevin Luk, Maxime Gazeau, Guodong Zhang, Harris Chan, and Jimmy Ba, An empirical study of stochastic gradient descent with structured covariance noise. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3621-3631. PMLR, 26-28 Aug 2020.
486
487
468
489
470
[52] Thomas Wolf. Transfer Learning in Natural Language Processing, 2019. Available at https: heatt//bcooo/uugggggffc/iaaaanno Baaraaaee__taasseeeeeeee leafffer_eeannng_uttee tuttorill.
471
[53] Saining Xie, Ross B. Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. CVPR, abs/161 11111111.0543.. .05431, 2017.
473
474
[54] Yang You, Igor Gitman, and Boris Ginsburg. Scaling SGD batch size to 32k for imagenet training. CoRR, abs/1708.00388. 2017.
[55] Yang You, Jing Li, Jonathan Hseu, Xiaodan Song, James Demmel, and Cho-Jui Hsieh. Reducing BERT pre-training time from days to 76 minutes. CoRR, abs/1904.00962.. 2019.
477
478
[56] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. Opt: Open pre-trained transformer language models, 2022.
480
[57] Wei Zhang, Xiaodong Cui, Ulrich Finkler, Brian Kingsbury, George Saon, David Kung, and Michael Picheny. Distributed deep learning strategies for automatic speech recognition. In ICASSP 2019, May 2019.
483
12

---

485
[58]
Wei Zhang, Xiaodong Cui. Ulrich Finkler, George Saon, Abdullah Kayi, Alper Buyuktosunoglu, Brian Kingsbury, David Kung. and Michael Picheny. A highly efficient distributed deep learning system for automatic speech recognition. In INTERSPEECH 2019, Sept 2019.
486
487
488
[59]
Wei Zhang, Xiaodong Cui, Abdullah Kayi, Mingrui Liu, Ulrich Finkler, Brian Kingsbury, George Saon, Youssef Mroueh, Alper Buyuktosunoglu, Payel Das, David Kung, and Michael Picheny. Improving efficiency in large-scale decentralized distributed training. In (CASSP'2020,
489
480
491
May 2020.
[60]
Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness-awart async-sgd for distributed deep learning. In Proceedings of the Twenty- -riftt-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 2350-2356, 2016.
493
495
[61]
Wei Zhang, Suyog Gupta, and Fei Wang. Model accuracy and runtime tradeoff in distributed deep learning: A systematic study. In IEEE International Conference on Data Mining, 2016.
496
[62]
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. CVPR, abs/1 707.01083, 2018.
498
439
633
Yao Zhang, Andrew M. Saxe, Madhu S. Advani, and Alpha A. Lee. Energy-entropy competition and the effectiveness of stochastic gradient descent in machine learning. Molecular Physics, Jun 2018.
500
501
1 116(11-2):3214-32222
502
[64]
Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradient descent algorithm for nonconvex optimization. In IJCA/-18, pages 3219-3227, 7 2018.
503
Checklist
504
505
1. For all authors...
506
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
507
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
510
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
511
512
2. If you are including theoretical results...
513
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
514
(b) Did you include complete proofs of all theoretical results? [Yes]
515
3. If you ran experiments..
516
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] Not code(proprietary), but enough instructions to reproduce the results.
517
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
520
521
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
522
523
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
524
525
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
526
(a) If your work uses existing assets, did you eite the creators? [Yes]
527
(b) Did you mention the license of the assets? [N/A]
528
(c) Did you include any new assets either in the supplemental material or as a URL?? [No]
529
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [N/A]
530
531
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
532
533
5. If you used crowdsourcing or conducted research with human subjects...
534
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
13

---

536
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
537
538
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "y4joeCH_EIL", "reviewer": "Reviewer_2WDQ", "summary": "This work compares two stochastic gradient descent methods for Distributed Deep Learning (DDL), one is Synchronous Stochastic Gradient Descent (SSGD), and the other is Decentralized Parallel SGD (DPSGD), in a large batch setting. The authors empirically find that DPSGD not only has a runtime benefit but also a significant convergence benefit over SSGD in the large batch setting, which is due to additional landscape-dependent noise brought by DPSGD.\n\nTo understand this phenomenon, the authors perform both theoretical analysis and experimental investigation. They claim that the introduced noise smooths the loss landscape. They also conduct extensive studies over 18 state-of-the-art DL models/tasks and demonstrate that DPSGD often converges in cases where SSGD diverges when training is sensitive to large learning rates.", "questions": "(1) The orthogonal decomposition of noise in Equation (4) is based on the expectation of users. In other words, it only holds when the number of users is very large. However, the experiment shown in Figure 2 only performs with 5 learners. In this case, is the results of the experiment consistent with the theoretical analysis?\n\n\n(2) In Table 1, the best performance comes from when lr=1x, and the performance drops significantly when lr is very large. What are the advantages of a large learning rate?", "limitations": "Even though the authors claim that they describe the limitations of their work. However, I cannot an explicit description. I would like to ask the authors if they can show me where is the limitation during the rebuttal.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n(1) The authors provide a theoretical analysis to compare the smoothness of the two methods.\n\n(2) This work conducts experiments on an adequate number of tasks and datasets.\n\nWeaknesses\n\n(1) The writing of this work has a big problem. The authors put important context including Related Works and DPSGD and SSGD Runtime Comparison in the appendix. \n\nRelated work is almost an indispensable chapter of an article. Besides, whether DPSGD has an advantage in runtime compared to SSGD is also important. Since the authors claim that DPSGD can have an advantage in terms of convergence, it is to be expected whether this advantage can bring about a saving in runtime. Although the conference has body content restrictions, putting very important content in the appendix is ​​a discouraged behavior.\n\n(2) Although this article emphasizes that DPSGD has great benefits, from the perspective of actual performance, the results are not very satisfactory when the learning rate is very large. Therefore, whether a large learning rate brings a great improvement in efficiency will be a very important question, and I don't think the author provide a detailed analysis in the text.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "q5TwjNH5KR", "reviewer": "Reviewer_x6PL", "summary": "The authors propose a comparison between two methods of parallelization of the SGD, namely SSGD and DPSGD. They prove theoretically that the decentralized one (DPSGD) adds a smoothing effect to the naive SSGD, and shows that DPSGD is better than SSGD as the batch size increases.", "questions": "There is a beginning of theoretical analysis of the proposed method though the Hessian of the loss. SSGD and DPSGD provide information about the loss surface, and, intuitively, DPSGD provides richer information. Is it possible to formulate SSGD and DPSGD as second-order methods, where the approximation of the preconditioning matrix (usually the Hessian) is computed in a distributed way? Is this the optimal second-order method with acceleration through distributed computing? Etc.\n\nNote: Fig2b shows an evolution of the learning rate, which appears also when using second-order methods.", "limitations": "The authors have tested an improved version of SSGD against DPSGD, in order to compare them fairly.\n\nThe main unchecked limitations are (as mentioned above):\n * no error margins in the results;\n * lack of reproducibility: the reader lacks information to obtain the same hyperparameters.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThis paper makes a tiny link between some distributed methods and second-order methods. It helps to understand their dynamics. Furthermore, the computation of an \"effective learning rate\" for DPSGD is useful to illustrate the implicit mechanisms of this method.\n\nThe experiments on large datasets, such as ImageNet, are valuable.\n\nAccording to the experiments, DPSGD seems to perform way better than the alternative choices when the batch size increases.\n\n### Control experiments\n\nIt is noticeable that the authors have tested a modification of the SSGD, called ``SSGD*'', in order to test fairly SSGD against DPSGD. \n\n## Weaknesses\n\n### Theory\n\nTheorem 1 contains at least two major issues:\n * The hypothesis: ``$\\| \\frac{1}{n} \\sum\\_{i = 1}^n X\\_i - \\frac{1}{n-1} \\sum\\_{i = 1}^{n - 1} X\\_i \\| \\leq \\epsilon$ almost surely'' is not reasonable when the $X\\_i$ are i.i.d. and without compact support. So, we cannot consider the simple case where the $X\\_i = \\nabla L^{\\mu\\_i(t)}(\\vec{w}\\_i(t))$ are i.i.d. Gaussian random variables.\n * In the proof: it is true that, conditionally to $\\mathcal{F}\\_{t-1}$, the $\\vec{w}\\_{i}(t)$ are independent, but it is false for the $\\delta w\\_i(t)$. \nLet us recall that: $\\delta \\vec{w}\\_{i}(t) = \\vec{w}\\_{a}(t) - \\vec{w}\\_{i}(t) = \\frac{1}{n} \\sum\\_{j = 1}^n \\vec{w}\\_{j}(t) - \\vec{w}\\_{i}(t)$.Thus, all $\\delta \\vec{w}\\_{i}(t)$ are linear combinations of the same set of variables, with only non-zero coefficients. It is thus impossible that two $\\vec{w}\\_{i}(t)$ are independent. Besides, independence has nothing to do with the fact the $\\sum_{i=1}^n \\delta \\vec{w}\\_{i}(t) = 0$... on the contrary, this equation indicates a strong dependence between the terms.\n\nHowever, it is probable that this theorem can be made useful and rigorous. But, anyway, it does not seem to be useful in the presented work. \n\n### Experiments\n\nError margins: there is no mention of any variance or error margin in the results. So, we cannot evaluate the significance of the presented results: if a reported result seems to be better than another, it may be luck... \n\nThe main drawback of the experimental setup is its complexity. In particular, a huge preliminary phase of fine-tuning seems to be necessary, without proposing a reproducible procedure to recover the proposed hyperparameters (which are very numerous). The authors only provide citations of preceding works, where the fine-tuning has already been done. \n\nIt is clear that the authors claim to prove the reliability of DPSGD as the batch size increases; they do not claim to beat the state of the art. So, there is no point of testing architecture trained with highly fine-tuned optimization procedures. A unified and simplified optimization process should have been considered.\n\n### Clarity\n\nThe paper suffers from several writing issues.\n * The \"related works\" section must not be put in appendix. This section is fundamental to draw a line between existing works and actual contributions, and to evaluate fairly the significance of the paper.\n * Using $\\vec{w}_j$, where $j$ is an index standing for an integer, and $\\vec{w}_a$, where $a$ is a simple letter (standing for \"average\"), is confusing. Why not using $\\hat{w}$ instead of $\\vec{w}_a$? Same issue with $\\vec{w}_{s, j}$. Besides, arrows can easily be removed, or replaced by bold text: $\\mathbf{w}_j$ instead of $\\vec{w}_j$.\n * If the authors do not use the general version of DPSGD presented in [33], then the general notation $\\vec{w}_{s, j}$ can be removed.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "coP-CKeBNiq", "reviewer": "Reviewer_ndjb", "summary": "The paper studies two distributed learning algorithm for training large-scale deep learning models.\nThe authors argue that the decentralized parallel stochastic gradient descent (DPSGD) has a series of advantages over the more commonly employed Synchronous SGD (SSGD). They argue that the optimization dynamics of DPSGD injects noise which smooths the optimization landscape and allows for larger learning rates. This is especially beneficial in the large-batch-size setting.\nThe paper contains one main theoretical result concerning the smoothness of the objective function that DPSGD implicitly minimizes. \nSeveral experiments with various tasks and architecture are conducted.", "questions": "*Major*\n- I do not understand why the assumption that $\\delta_i w |\\\\mathcal{F}_{t-1}$ should be Gaussian with zero mean and especially equal (scalar) variance. Why this should make sense? In the appendix the authors call for the central limit theorem, but 1) I do not understand to what it should be applied 2) I think that at least the multidimensional version of the CLT should be considered here. On the contrary, the empirical results with SSGD + Gaussian noise (which show poor performances) seem to suggest that there is a fundamental difference between the noise induced by DPSGD and Gaussian noise. \n- One might hypothesize that the advantage of  DPSGD is that the noise is adaptive (but still Gaussian). To empirically verify this, the authors could run an experiment where the Gaussian noise added to SSGD is scheduled after what the authors find by running DPSGD (e.g. figure 2 b) for the MNIST setting. If the resulting methods performs on par with DPSGD, then I could be more willing to accept the assumption, although questions would remain. \n- Otherwise, I would argue that Th 1. is not useful to understand the advantages of DPSGD. \n\n*Others*\n- From Lemma 2 of Random Gradient-Free Minimization of Convex Functions [39] it would follow that the smoothness coefficient should be $\\frac{\\sqrt{n}}{\\sigma} G$ where $n$ is the dimension of the parameter vector. From where do you obtain $\\frac{2}{\\sigma} G$ that you report in the paper?\n- I do not quite understand how the theoretical result cannot involve the mixing matrix. As the authors note, for a complete mixing matrix DPSGD is equivalent to SSGD; this should be reflected in the statement and formulation of the theorem.\n- In eq. (2) is it intentional that there are 2 sets of weights $w_j$ and $w_{s,j}$? Isn't it that the loss is also computed at $w_{s,j}$? Or does each worker maintain 2 sets of weights?\n\n*Minor*\n- Why only limiting to the cross-entropy loss? \n- I do not understand the reason behind \"self\" of self-adjusting. Why \"self\"? Usually one speaks about adaptive method.\n- Typos: allow [for]; tasks -> models in line 29; inconsistencies between figures and tables and texts (e.g. Fig 1 SSGD-noise vs SSGD* in the text).\n", "limitations": "- Negative societal impacts are not discussed, but I do not see any visible one, so I think missing that discussion is fine for this paper. \n- Limitations of the proposed analysis are not discussed, and should be added, e.g. in relation to the assumptions of the theorem.\n- I do not think it is proper to have one paragraph sketching out very informally a possible result suggesting that other \"people\" (line 144) then can fill the gaps. One might suggest this as a potential interesting future work (briefly and in the conclusions). Or spell out the theorem and include the proof. As it stands, the passage starting at 144 should be removed.", "rating": 3, "confidence": 3, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- The experimental section contains several diverse tasks and architectures, therefore having large coverage\n- The intuitive and empirical arguments in favor of DPSGD are interesting; somewhat helping build up confidence in this algorithm which has other advantages wrt SSGD\n\n**Weaknesses:**\n- I am not quite convinced of the utility of the theoretical results, especially regarding the Gaussian hypothesis (see below in questions)\n- Even factoring this concern out, I believe the theoretical contribution to be very limited as it is basically the application of a know Lemma\n- The presentation is unclear in various passages, including the proof of the theorem; notation is too often overloaded (see eq (3)) making it difficult to understand what is what. This is especially bad in section 2.2: e.g. in equation (4) one might expect the authors to discuss about the DPSGD algorithm, but there is no mention of the gradient $g_j=\\nabla L^{\\mu_j}(w_j)$. Other important quantities such as the total loss are never explicitly defined and the reader is left with the need to self-interpret the paper at various points.\n- The layout of the paper should be revised: the abstract is too long and the related work section cannot be relegated to the appendix. Space can be saved by avoiding repetitions, focusing discussion and removing unnecessary \"summary\" sentences at the end of each experimental section.\n- The claim that DPSGD needs very little to no tuning is exaggerated and not backed up by the experiments. In particular, note that in the NLP experiment DPSGD still needs the learning rate warm-up stage, although shorter. \n- The paper would benefit from a more complete (also formally) introduction of the two algorithms. For instance it is not clear what happens at the end of the optimization with DPSGD. Are the weights averaged over all the worker?\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ODy9dpaI4_Q", "reviewer": "Reviewer_bt9N", "summary": "The paper compares the convergence behavior of two common training schemes for distributed stochastic gradient descent optimization on large batch sizes. In particular, Synchronous Stochastic Gradient Descent (SSGD), where weight updates are computed by synchronizing all distributed learners globally, is being evaluated against Decentralized Parallel Stochastic Gradient Descent (DPSGD), where only a random selection of neighboring distributed learners is used to compute the weight update. The authors observe a much better convergence behavior with DPSGD and explore the hypothesis that this is due to an inherent quality of this training scheme to introduce stabilizing noise in the weight update rule, which automatically scales the learning rate depending on the landscape of the loss function. The paper continues to give a theoretical explanation for this observation and finally provides a very extensive evaluation on various machine learning tasks in a large distributed training environment. The results demonstrate a clear advantage of DPSGD for large batch sizes and a more robust convergence behavior that doesn't require to reduce the learning rates drastically, as it is the case for SSGD.", "questions": "It is not very clear to me why only Gaussian noise has been considered, it appears like the noise simulation could have been designed such that it is more similar to the noise introduced by DPSGD.\n\nline 213: numbers up to twelve (12) should be written as words\n", "limitations": "The authors did not really discuss the limitations of their evaluation, which is unfortunate. As mentioned earlier, especially the simulated noise injection has a lot of room for further considerations. It again appears that this discussion has been omitted due to the page limit. An outlook on potential societal impact is also not provided. Since the important results of this paper mostly benefit groups with very large training resources, some discussion on this topic would have been appropriate. ", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The claim of this paper is very adequately examined. The biggest strength of this paper is clearly the very deep evaluation, taking large CV, NLP and ASR tasks into account. The authors hereby build on top of previously published modern state-of-the-art training recipes with warm-up periods and adaptive gradient optimizers in order to ensure optimal performance. The thorough evaluation and the conclusions drawn from the experiments is convincing and of high significance to the field.\n\nThe scope of this work seems to be a bit too large for this conference. At various points in the paper it is noticeable that the authors were struggling with the page limit. It is particularly unfortunate that the description of related work had to be put into the appendix. One way to reduce the scope of this paper would be to leave out the evaluation of noise-injection, which appears rather limited by sticking to Gaussian noise injection at various points in the training process. While these results somehow support the claims by the authors, that the advantages of DPSGD are related to their inherent noise introduction, it is far from being proven to be the case given that manual noise injection experiments with SSGD contain many heuristics and best effort attempts to simulate the effect of DPSGD. In my opinion this could have been studied in a separate publication.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject