Why Does Decentralized Training Outperform Synchronous Training In The Large Batch Setting?
Authors: Wei Zhang
Mingrui Liu
Yu Feng
Brian Kingsbury
Yuhai Tu
Venue:  (2021)
Keywords: Decentralized
Distributed Deep Learning
Large Batch

Abstract: Distributed Deep Learning (DDL) is essential for large-scale Deep Learning (DL) training. 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 batch size may converge to sharp minima with poor generalization, and a large learning rate may harm convergence. Synchronous Stochastic Gradient Descent (SSGD) is the de facto DDL optimization method. Recently, Decentralized Parallel SGD (DPSGD) has been proven to achieve a similar convergence rate as SGD and to guarantee linear speedup for non-convex optimization problems. While there was anecdotal evidence that DPSGD outperforms SSGD in the large-batch setting, no systematic study has been conducted to explain why this is the case. Based on a detailed analysis of the DPSGD learning dynamics, we find that DPSGD introduces additional landscape-dependent noise, which has two benefits in the large-batch setting: 1) it automatically adjusts the learning rate to improve convergence; 2) it enhances weight space search by escaping local traps (e.g., saddle points) to find flat minima with better generalization. We conduct extensive studies over 12 state-of-the-art DL models/tasks and demonstrate that DPSGD consistently outperforms SSGD in the large batch setting; 
  and DPSGD converges in cases where SSGD diverges for large learning rates. Our findings are consistent across different application domains, Computer Vision and Automatic Speech Recognition, and different neural network models, Convolutional Neural Networks and Long Short-Term Memory Recurrent Neural Networks.

Under review as a conference paper at ICLR 2021
WHY DOES DECENTRALIZED TRAINING OUTPER- FORM SYNCHRONOUS TRAINING IN THE LARGE BATCH SETTING?
Anonymous authors
Paper under double-blind review
ABSTRACT
Distributed Deep Learning (DDL) is essential for large-scale Deep Learning (DL) training. 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, a large batch size may converge to sharp minima with poor generalization, and a large learning rate may harm convergence. Synchronous Stochastic Gradient Descent (SSGD) is the de facto DDL optimization method. Recently, Decentralized Parallel SGD (DPSGD) has been proven to achieve a similar convergence rate as SGD and to guarantee linear speedup for non-convex optimization problems. While there was anecdotal evidence that DPSGD outperforms SSGD in the large-batch setting, no systematic study has been conducted to explain why this is the case. Based on a detailed analysis of the DPSGD learning dynamies, we find that DPSGD introduces additional detesccappedeedeeett noise, which has two benefits in the large-batch setting: 1) it automatically adjusts the learning rate to improve convergence; 2) it enhances weight space search by escaping local traps (c.g., saddle points) to find flat minima with better generalization. We conduct extensive studies over 12 state- of-the-art DL models/tasks and demonstrate that DPSGD consistently outperforms SSGD in the large batch setting; and DPSGD converges in cases where SSGD diverges for large learning rates. Our findings are consistent across different application domains, Computer Vision and Automatic Speech Recognition, and different neural network models, Convolutional Neural Networks and Long Short- Term Memory Recurrent Neural Networks.
INTRODUCTION
Deep Learning (DL.) has revolutionized Al training across application domains: Computer Vision (CV) Krizhevsky et al. 2012 He et al. 2013). Natural Language Processing (NLP) (Vaswani et al. 2012). Stochastic Gradient Descent (SGD) is the fundamental optimization method used in DL training. Due to massive computational requirements, Distributed Deep Learning (DDL) the preferred mechanism to train large scale Deep Learning (DL) tasks. In the early days, Parameter Server (PS) based Asynchronous SGD (ASGD) training was the preferred DDL approach (Dean et al. 2012 Li et al., 2014) as it did not require strict system-wide synchronization. Recently, ASGD has lost popularity due to its unpredictability and often inferior convergence behavior (Zhang et al. 2016b). Practitioners now favor deploying Synchronous SGD (SSGD) on homogeneous High Performance Computing (HPC) systems. The degree of parallelism in a DDL system is dictated by batch size: the larger the batch size, the more parallelism and higher speedup learning rate and overall they may negatively affect model accuracy because 1) large batch training usually converges to sharp minima which do not generalize well (Keskar al. (016) and 2) large learning rates may violate the conditions (i.e., the smoothness parameter) required for convergence in nonconvex optimization theory (Ghadimi & Lan| 2013). Although training longer with large batches could lead to better generalization (Hoffer et al. 2017). doing so gives up some or all of the speedup we seek. Through meticulous hyper-parametes design (e.g., learning rate) tailored to each specific task, SSGD- based DDL systems have enabled large batch training and shortened training time for some challenging CV tasks (Goyal et al. 2017 You et al. 2017) and NLP tasks (You et al., 2019) 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 Zhang et al. 2019b), as illustrated in Figure Ia (red curve). In this paper found for other types of tasks (c.g. CV) and DL models, large batch SSGD has the same problem (Figure Tb and Figure IT). The cause of this problem could be that training gets trapped at saddle points since large batches reduce the magnitude of noise in the
2017.. and Automatic Speech Recognition (ASR) (Hinton
be expected. However, large batches require a larger

---

Under review as a conference paper at ICLR 2021
Senur16 050-2.05
LSTM, SWB300, BS 8192
(b) EfficientNet, CIFAR- 10, BS 8192 (c) SENct-18, CIFAR-10, 10, BS 8192
Figure 1: SSGD (red) does not converge in the large batch setting. Figure la plots the heldout-loss,
the lower the better. Figure Tb and Figure Ic plot the model accuracy, the higher the better. By injecting Gaussian noise, SSGD might escape early traps but result in much worse model (blue) compared to DPSGD (green) in the large batch setting. The detailed task descriptions and training BS stands for Batch-Size.
recipes are described in Section 4.3
stochastic gradient and prevent the algorithm from exploring the whole parameter space. To solve this problem, one may add isotropic noise (e.g.. spherical Gaussian) to help SSGD escape from saddle points (Ge et al. 2015). However, this is not good solution for high-dimensional DL training as shown in the blue curves of Figure [1] One possible reason is that the complexity of escaping a saddle point by adding isotropic noise has a polynomial dependency on the dimension of the parameter space, so adding such noise in a high dimensional space (such deep learning) does not bring significant benefits. In this paper, we have found that Decentralized Parallel SGD (DPSGD) (Lian et al. 2017b) greatly improves large batch training performance, illustrated in the green curves in Figure I Unlike SSGD, where each learner updates its weights by taking global average of all learners' weights, DPSGD updates each learner's s weights by taking a partial average (i.e., across subset of neighboring learners). Therefore, in DPSGD, each learner's ' weights differ from the weights of other learners | source of noise during the update, and this noise directly affects performance in deep learning. This naturally motivates us to study Why decentralized training outperform synchronous training the large batch setting? More specifically, we try to understand whether their performance difference caused by their different noise. We answer these questions from both theoretical and empirical perspectives. Our contributions are:
The key difference among SSGD, SSGD with Gaussian noise and DPSGD the
We analyze the dynamics of DDL. algorithms, including both SSGD and DPSGD. We show, both theoretically and empirically, that the intrinsic noise in DPSGD can 1) reduce the effective learning rate when the gradient is large to help convergence; 2) enhance the search in weight space for flat minima with better generalization.
We conduct extensive empirical studies of 12 CV and ASR tasks with state-of-the. art CNN and LSTM models. Our experimental results demonstrate that DPSGD consistently outperforms SSGD, across application domains and Neural Network (NN) architectures in the large batch setting, without any hyper-parameter funing. To the best of our knowledge, we are unaware of any generic algorithm that can improve SSGD large batch training on this many models/tasks.
The remainder of this paper is organized as follows. Section 2 details the problem formulation and learning dynamics analysis of SSGD, SSGD+Gaussian, and DPSGD; Section and Section detail the empirical results; and Section concludes the paper.
2 ANALYSIS OF STOCHASTIC LEARNING DYNAMICS AND EFFECTS OF NOISE
We first formulate the dynamics of an SGD based learning algorithm with multiple (n 1) learners indexed by j = 1. ...n following the same theoretical framework established for single learner (Chaudhari & Soatto 2018). At each given time (iteration) t, each learner has its own weight vector wi, (1), and the average weight vector w. (t) is defined as: w.(() = n " (1).
'The detailed DPSGD algorithm and its learning dynamics are described in Section 2 We use the terms "SSGD with Gaussian noise" and "SSGD"" interchangeably in this paper.
2

---

Under review as a conference paper at ICLR 2021
Each learner j updates its weight vector according to the eross-entropy loss function [()((( for minibatch (t) that is assigned to it at time t. The size of the local minibatch is B, and the overall batch size for all learners is nB. Two multi-learner algorithms
described below.
(1) Synchronous Stochastic Gradient Descent (SSGD): In the synchronous algorithm, the learner j E [1,n] starts from the average weight vector tia and moves along the gradient of its local loss function (*)(*) evaluated at the average weight wia:
my (t + 1) (t) - (WL (t)),
(1)
where a is the learning rate.
(2) Decentralized Parallel SGD (DPSGD): In the DPSGD algorithm (Lian et al. 2017a). learner computes the gradient at its own local weight Wi, (t). The learning dynamics follows:
(t - - (t) (V (i)(()).
where (t) is the starting weight set be the average weight of a subset of "neighboring" learners of learner-j, which corresponds to the non-zero entries in the mixing matrix defined in (Lian et al. 2017a) (note that W..j = W. if all learners are included neighbors).
By averaging over all learners, the learning dynamics for the average weight wA for both SSGD and DPSGD can be written formally the same way as: V. + = w. (() oga. where Z. f= Fj is the average gradient and Øj is the gradient from learner-j. The difference between SSGD and DPSGD is the weight which Tj is computed: Øj = (Z/((0) (w, is computed W for SSGD; ōj = (1,(0) (1) computed at vł, for DPSGD.
By projecting the weight displacement vector Ant ag onto the direction of the gradient ğ = (((T) of the overall loss function L at War we can write the learning dynamics as:
V.a (L + 1) (l) - a.e + :7.
where ag = aga 0/ an effective learning rate and rj -aga + aeg is the noise term that describes the stochastic weight dynamics in directions orthogonal to The noise term has zero mean (m), = and its strength characterized by its variance (l)) = ||77| 12 A and a, are related by the cquality: 12 + A = a which indicates that a higher noise strength A leads to lower effective learning rate
The noise strength A (and hence a.) is different in SSGD and DPSGD. The DPSGD noise ADP is larger than the SSGD noise As by an additional noise A (2) (> 0) that originates from the difference of local weights (17²) from their mean (w.): Apr As A (2)), see Appendix B for details. By
expanding A (2) w.r.t Aw; = W Wa. we obtain the average A (2) over minibatch ensemble {u}:
(A (2) 11 = a 21lm
Σ -
a
Σ HaaHaaCurr k.l.!'
(4)
where HaI L is the Hessian matrix of the loss function and Cu n n >
Auy,A
the weight covariance matrix. is clear that (2) depends on the loss landscape it is larger in rough landscapes and smaller in flat landscapes.
is important to stress that the noise oj in Eq 3 is not an artificially added noise. It is intrinsic to the use of minibatches (random subsampling) in SGD-based algorithms and is enhanced by the difference among different learners DPSGD. The noise strength A varies in weight space via its dependence the loss landscape, explicitly shown in Eq However, besides its landscape dependence, SGD noise also depends inversely on the minibatch size B (Chaudhari & Soatto 2018). 8). With n synchronized learners, the noise in SSGD scales as 1/(nB), which is too small to be effective for a large batch size n.B. A main finding of our paper is that the additional bundscape-deeendee
noise (2) in DPSGD can make up for the small SSGD noise when nB is large and help enhance convergence and generalization in the large batch setting.
In the following, we investigate the effects of this landscape-dependent noise for SSGD and DPSGD using the MNIST dataset where each learner is fully connected network with two hidden layers (50 units per layer). We focus on the large batch setting using nB = 2000 in the experiments.
3

---

Under review as a conference paper at ICLR 2021
2.1 NOISE IN DPSGD REDUCES EFFECTIVE LEARNING RATE TO HELP CONVERGENCE
First, we study a case with a large learning rate a 1. In this experiment, we used n = 5, and W..y = Vi for DPSGD. As shown in the upper panel of Fig. 2 a), DPSGD converges to solution with low loss (2.1% test error), but SSGD fails to converge. As shown in Fig. a (lower panel), the effective learning rate Ore is reduced in DPSGD during early training (0 S t S 700) while 0e in SSGD remains roughly the same as a. This reduction of ar caused by the stronger noise A in DPSGD is essential for convergence by avoiding overshoots when gradients are large in the beginning of the training process. In the later stage of the training process when gradients are smaller, the landsape-depeender DPSGD noise decreases and Oe increases back to be noise, we introduce a variant of SSGD, SSGD", by injecting Gaussian noise with constant variance weights in SSGD. However, most choices of this injected noise fail to converge. Only by fine tuning the injected noise strength can SSGD* converge, but to an inferior solution with much higher loss and test error (5.7%). The poor performance likely due to the persistent reduction of ag even in the later stage of training (see Fig. 2 aa (lower panel)) since the added Gaussian noise in SSGD* is independent of the loss landscape.
To show the
importance of the landscape-dependes
This insight on reducing learning rate is consistent with nonconvex optimization theory (Ghadimi Lan 2013 Lian et al., 2017b). When we use a larger batch size, stochastic gradient has smaller variance, and nonconvex optimization is able to choose larger learning rate without affecting its convergence. However, the learning rate should be limited by 1/1, where La is the smoothness parameter. In the very large batch setting, the learning rate under the linear scaling rule (Goyal et al. 2017) may indeed exceed this limit (1/lg). Here, we show that these conflicting requirements can be resolved in DPSGD where the enhanced sundsaap--ependder learning rate by reducing a, when the loss landscape is rough with large gradients and restoring to the original large when the landscape is smooth. In Appendix
noise adaptively adjusts the effective
F we consider simple synthetic problem where we show that the larger noise in DPSGD allows the algorithm to escape saddle points in the loss function landscape while the SSGD algorithm gets stuck for a long time.
(a)
(b)
10
10
1222
SSOD
SOOD
L
10-1
10:1
10:1
SSGD
0.5
10-1
0
1000
2000
3000
4000
1000
2000
3000
4000
time
time (batch)
DPSGD
Figure Comparison of different multi-learner algorithms, DPSGD (green), SSGD (red), and SSGD* (blue). (a) For large learning rate 1, the lowered effective learning rate a₂ in DPSGD in the beginning of training allows DPSGD to converge while SSGD fails to converge. SSGD* also converges but to an inferior solution. (b) For a smaller 0.2, DPSGD finds a flatter minimum with a lower test error than SSGD. SSGD* has the worst performance. See text for detailed description.
2.2 NOISE IN DPSGD ENHANCES SEARCH TO FIND FLAT MINIMA WITH BETTER GENERALIZATION
Next, we consider a case with a smaller learning rate a = 0.2. Here we used DPSGD is the average weight of 2 neighbors on each side. In this case, both SSGD and DPSGD can converge to solution, but their learning dynamies are different. As shown Fig. b (upper panel), while the training loss L of SSGD (red) decreases smoothly, the DPSGD training loss (green) fluctuates widely during the time window (1000-3000) when it stays significantly above the SSGD training loss. As shown in Fig. b (lower panel), these large fluctuations in L are caused by the high and increasing noise level in DPSGD. This elevated noise level in DPSGD allows the algorithm to search in wider region in weight space. At around time 3000(batch), the DPSGD loss decreases suddenly and eventually converges to a solution with a similar training loss as SSGD. However, despite their similar final training loss, the DPSGD loss landscape is flatter (contour lines further
and w.. (t) in
4

---

Under review as a conference paper at ICLR 2021
CIFARTO
EfficientNet-Bi
SENet-18 18
VGG-19 19
ResNet-18
DenseNet- 121
MobileNet
Size
11.11 MB
42.95 MB
76.45 MB
42.63 MB
26.54 MB
12.27 MB
Time
2.92 Hr
1.58 Hr
1.08
1.37 Hr
5,48 Hr
1.02 Hr
CIFARIO
SWB300
SWB2000
MobileNerV2
ShuffleNet
GoogleNet
ResNext-29
L.TTM
LSTM
Size
8.76 MB
4.82 MB
23.53 MB
34.82 MB
164.62 MB
164.62 MB
Time
1.96 Hr
2.46 Hr
5.31 Hr
4.55 Hr
26.88 Hr
203.21 Hr
Table I: Evaluated workload model size and training time. Training time is measured when running
on VI00 GPU. CIFAR-I0 10 is trained with batch size 128 for 320 epochs. SWB-300 and SWB-2000 are trained with batch size 128 for 16 epochs.
apart) than SSGD landscape. Remarkably, the DPSGD solution has lower test error (2.3%) than the test error of the SSGD solution (2.6%). We have also tried the SSGD" algorithm, but the performance (3.9% test error) worse than both SSGD and DPSGD.
To understand their different generalization performance, we studied the loss function landscape around the SSGD and DPSGD solutions. The contour plots of the loss function L around the two solutions are shown in the two right panels in Fig. bb). We found that the loss landscape near the DPSGD solution flatter than the landscape near the SSGD solution despite having the same minimum loss. Our observation is consistent with (Keskar et al. 2016) where it was found that SSGD with large batch size converges to a sharp minimum which does not generalize well. Our results are in general agreement with the current consensus that flatter minima have better generalization (Hinton & van Camp 1993; Hochreiter & Schmidhuber, 1997 Baldassi et al. 2016 Chaudhari et al. 2016 Zhang et al. 2018b). It was recently suggested that the landscape-dependees noise in SGD-
algorithms can drive the system towards flat minima (Feng & Tu 2020). However, in the large batch setting, the SSGD noise is too small to effective. The additional landscape-dependent noise A (2) in DPSGD, which also depends inversely on the flatness of the loss function (see Eq. 4. is thus critical for the system to find flatter minima in the large batch setting.
3 EXPERIMENTAL METHODOLOGY
We implemented SSGD and DPSGD using PyTorch, OpenMPI, and NVidia NCCL. We run experi- ments on a cluster of 8-V 8-V 100-GPU x86 servers. For CV tasks, we evaluated on CIFAR-10 1- (50,000 samples, 178MB). For ASR tasks, we evaluate on SWB-300 (300 hours training data, 4,000,000 sam- ples, 30GB) and SWB-2000 (2000 hours training data, 30,000,000 samples, 216GB We evaluate on 12 state-of-the NN models: 10 CNN models and 6-layer bi-directional LSTM models. We summarize the model size and training time in Table T We refer readers to Appendix D for software implementation, hardware configuration, dataset and Neural Network (NN) model details.
4 EXPERIMENTAL RESULTS
All the large batch experiments are conducted on 16 GPUs (learners) not stated otherwise. Batches are evenly distributed among learners, e.g., each learner uses a local batch size of 128, when the overall batch size is 2048. A learner randomly picks a neighbor with which to exchange weights in each iteration Zhang et al. 2020).
4.1 SSGD AND DPSGD COMPARISON ON CV TASKS
For CIFAR- 10 tasks, we use the hyper-parametts setup proposed in Liu 2020): a baseline batch size 128 and learning rate 0.1 for the first 160 epochs, learning rate 0.01 for the next 80 epochs, and learning rate 0.001 for the remaining 80 epochs. Using the same learning rate schedule, we keep increasing the batch size up 8192. Table Saaeerrecce records test accuracy under different batch sizes. Model accuracy consistently deteriorates beyond batch size 1024 because the learning rate is too small for the number of parameter updates.
To improve model accuracy beyond batch size 1024, we apply the linear scaling rule (i.e., linearly
increase learning rate w.r.t batch size) (He al. 2013 Zhang et al., 2019a Goyal et al. 2017: Zhang
et al. 2016b a). We use learning rate 0.1 for batch size 1024, 0.2 for batch size 2048, 0.4 for batch size 4096, and 0.8 for batch size 8192. Table 3 compares SSGD and DPSGD performance running with 16 GPUs (learners). SSGD and DPSGD perform comparably up to batch size 4096. When the batch size increases to 8192, DPSGD outperforms SSGD in all but one case. Most noticeably, SSGD
SSWB-2000 training is more challenging than ImageNet. It takes over 200 hours on I V100 GPU to finish training SWB-2008 SWB-2000 has 32,000 highly unevenly distributed classes whereas ImageNet has 1000 evenly distributed classes.
5

---

Under review as a conference paper at ICLR 2021
Batch Size
128
256
512
1024
2048
4096
8192
EfficientNet-OO
87.51
89.32
91.28
91.92
90.62
88.00
84.85
SENet-18
95.18
94.84
94.83
94.52
93.83
92.94
91.69
VGG-19
93.51
93.78
93.35
93.12
92.64
91.82
87.76
ResNet-18 18
95.44
95.26
95.08
94.59
94.96
92.98
91.24
DenseNet- 121
95.06
95.27
95.42
95.11
94.81
93.09
92.34
MobileNet
89.53
90.96
92.39
92.24
91.22
89.54
86.59
MobileNetV2
90.52
92.93
94.17
94,99
93.71
91.97
89.81
ShuffleNet
90.4
92.27
92.82
93.15
91.94
90.59
87.81
GoogleNet
94.99
95.06
94.97
95.32
94.05
92.78
91.09
ResNext-29
95.35
95.66
95.31
95.42
94.24
93.00
91.06
Table 2: CIFAR-10 accuracy (%) with different batch size. Across runs, learning rate is set as 0.1 for first 160 epochs, 0.01 for the next 80 epochs and 0.001 for the last 80 epochs. Model accuracy consistently deteriorates when batch size is over 1024. Bold text in each row represents the highest accuracy achieved for the corresponding model, e.g., EfficientNet-BO achieves highest accuracy at 91.92% with batch size 1024.
BO
SB-18
VGG
Res-18 95.44
Dense- 121
Mobile
MobileV2
Shuille 90.40
Google 94.99
ResNext-29
bs=128
Baseline
87.51
95.18
93.51
95.06
89.53
90.52
95.35
1=-111
bs=1024
SSGD
91.92
94.52
93.12
94.59
95.11
92.24
94.99
93.15
95.32
95.42
1==0.1
DPSGD
91.69
94.55
93.15
94.98
95.12
92.52
94.36
93.55
95.18
95.72
bs=2048
SSGD
91.69
94.36
92,64
94.96
95.11
91.72
94.24
92.91
94.76
94.19
1r=
DPSGD
91.06
94.70
93.05
94.86
95.32
92.72
94.51
92.89
94,80
95.30
bs=4096
SSGD
91.62
94.28
92.68
94.30
94.72
91.68
94.25
92.67
94.36
93.21
1r0.44
DPSGD
91.23
94.58
92.72
94.78
95.24
92.03
94.12
92.20
94,99
94.32
bs=8192
SSGD
10
10
87.11
92.70
92.79
91.10
93.22
92.09
93.72
92.38
1=0.88
DPSGD
91.13
90.48
90.52
94.34
94.79
91.80
93.09
92.36
93.84
92.55
Table 3: CIFAR- 10 comparison for batch size 2048, 4096 and 8192, with learning rate set as 0.2, 0.4 and 0.8 respectively. All experiments are conducted on 16 GPUs (learners), with batch size per GPU 128, 256 and 512 respectively. Bold texts represent the best model accuracy achieved given the specific batch size and learning rate. When batch size is 8192, DPSGD significantly outperforms SSGD. The batch size 128 baseline is presented for reference. bs stands for batch-size, Ir stands for learning rate.
diverges in EfficientNet-BO and SENet-18 when the batch-size is 8192. Figure 5 in Appendix details model accuracy progression w.r.t epochs in each setting.
To better understand the loss landscape in SSGD and DPSGD training, we visualize the landscape contour 2D projection and Hessian 2D projection, using the same mechanism in (Li al.] 2018). For both plots, we randomly select two N-dim vectors (where N is the number of parameters in each model) and multiply with a scaling factor evenly sampled from -0.1 to 0.1 in a K x K grid to generate K2 perturbations of the trained model. To produce contour plot, we calculate the testing data loss of the perturbed model at each point in the x grid. Figure depicts the 2D contour plot for representative models (at the end of the 320th epoch) in 50 x 50 grid. DPSGD training leads not only to a lower loss but also much more widely spaced contours, indicating a flatter loss landscape and more generalizable solution. For the Hessian plot, we first calculate the maximum eigen value Amax and minimum eigen value Amin of the model's Hessian matrix at each sample point in 4x4 grid. We then calculate the ratio between |Amin| and [Amux]- The lower r is, the more likely it is in a convex region and less likely in saddle region. We then plot the heatmap of this value in this 4x4 grid. The corresponding models are trained the 16-th epoch (i.e. the first 5% training phase) and the corresponding Hessian plot Figure 4 indicates DPSGD is much more effective at avoiding early traps (e.g., saddle points) than SSGD.
Summary DPSGD outperforms SSGD for 9 out of 10 CV tasks in the large batch setting. Moreover, SSGD diverges on the EfficientNet-BB and SENet- 18 tasks. DPSGD is more effective at avoiding early traps (e.g., saddle points) and reaching better solutions than SSGD in the large batch setting.
4.2 SSGD AND DPSGD COMPARISON ON ASR TASKS
For the SWB-300 and SWB-2000 tasks, we follow the same learning rate schedule proposed in learning rate 0.1 for baseline batch size 256, and linearly warmup
/Zhag et al. 2019a):

---

Under review as a conference paper at ICLR 2021
VGG-S
(b) VGG-DP
(c) ResN-S
(d) ResN-DP
(c) DenseN-S (f) DenseN-DP
Figure 3: CIFAR-10 2D contour plot. The more widely spaced contours represent a flatter loss
landscape and more generalizable solution. The distance between each contour line is 0.005 across all the plots. We plot against the model trained at the end of 320th epoch. VGG: VGG-19, ResN: ResNet- 18, DenseN: DenseNet-121, -S: -SSGD, -DP: -DPSGD
(a) VGG-S
(b) VGG-DP
(c) ResN-S
(d) ResN-DP
(c) Dense-8
(f) Dense-DP
Figure 4: CIFAR-IO Hessian heatmap on 4x4 grid. The lower value (i.e. a cooler color) indicates the corresponding point is less likely in saddle. We plotted against the models at the end of the 16th epoch. DPSGD is much more effective at avoiding early traps (e.g.. saddle points) than SSGD. VGG: VGG-19, ResN: ResNet-18, DenseN: 12. -SSGD, -DP: -DPSGD
learning rate w.r. the baseline batch size for the first 10 epochs before annealing learning rate by /2 for the remaining 10 epochs. For example, when using batch size 2048, we linearly warmup the learning rate to 0.8 by the end of the 10th epoch before annealing. Table Biblsttillsttttsss heldout loss for SWB-300 and SWB-2000. In the SWB-300 task, SSGD diverges beyond batch size 2048 and DPSGD converges 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 in Appendix details heldout loss progression w.r.t epochs.
Summary For ASR tasks, SSGD diverges whereas DPSGD converges to baseline model accuracy in the large batch setting.
4.3 COISE-INJECTION AND LEARNING RATE TUNING
In 4 out of 12 studied tasks, a large batch setting leads to a complete divergence in SSGD: EfficientNet- BO, SENet-18. SWB-300 and SWB-2000. As discussed in Section 2 the intrinsic landscape- dependent noise in DPSGD effectively helps escape early traps (e.g., saddle points) and improves training by automatically adjusting 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. find that SSGD might escape early traps but results much inferior model compared to DPSGD.
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, voise-injection cannot escape early traps. In EfficientNet-BO only when std is set to 0.04, does the model start converge, but to a very bad loss (test accuracy 155% in SSGD 91. 11.13% in DPSGD). In SENet- 18, when std is set to 0.01, the model converges to reasonable accuracy (84.86%) but still significantly lags behind its DPSGD counterpart (90.48%). In the SWB-300 case, when std is 0.01, SSGD shows early sign of
SWB-300
SWB-2000
bs2048
bs4096
bs8192
bs2048
bs4096
bs8192
SSGD
1.58
10.37
10.37
1.46
1.46
10.37
DPSGD
1.59
1.60
1.66
1.45
1.47
1.47
Table 4: Heldout loss comparison for SSGD and DPSGD, evaluated SWB-300 and SWB-200 There are 32000 classes in this task, a held-out loss 10.37 (i.e. (m22000) indicates a complete divergence. bs stands for batch size.
7

---

Under review as a conference paper at ICLR 2021
121
Mobole
MobileV2
Shuftl
Google
ResNext
SSGD
10.00
10.00
87.11
92.7
92.79
91.10
93.22
92.09
93.72
92.38
0=8.8
DPSGD
91.13
90.48
90.52
94.34
94.79
91.80
93.09
92.36
93.84
92.55
SSGD
88,61
92.84
91.06
91.98
93.42
91.13
93.11
91.54
92.85
89.70
1=:0.4
DPSGD
89.80
94.00
91.93
93.91
94.32
91.38
93.14
91.68
93.49
92.79
SSGD
88.03
92.41
90,51
92.13
92.98
88,38
91.68
90.14
92.44
91.31
1r=2.2
DPSGD
87.69
93.11
91.59
93.30
94.28
89.18
92.52
90.13
93,41
91.79
Table 5: CIFAR-10 with batch size 8192. By reducing learning rate, SSGD can escape early traps but still lags behind DPSGD. Bold text in each column indicates the best accuracy achieved for that model across different learning rate and optimization method configurations. DPSGD consistently delivers the most accurate models.
SWB-30 300 (bv1096)
SWB-300 (bx8192)
SWB-2000 (bs 8192)
SSGD
10.37
10.37
10.37
1r'=0.1
DPSGD
1.60
1.66
1.47
SSGD
10.37
10.37
10.37
1=00.5
DPSGD
1.65
1.73
1.48
SSGD
1.76
10.37
1.51
1=00025
DPSGD
1.77
1.80
1.52
SSGD
1.92
2.05
1.58
150.12
DPSGD
1.94
2.00
1.59
Table 6: 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. *The learning rate used here corresponds to batch size 256 baseline learning rate, and we still adopt the same learning rate warmup, scaling and annealing schedule. Thus when this learning rate reduces by x, the overall effective learning rate also reduces by z.
converging for the first 3 epochs before it starts to diverge. In the SWB-2000 case, 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 escapes saddle points very slowly, since Gaussian noise is isotropic and the complexity for finding local minima is dimension-dependeen (Ge et al. 2015). Deep Neural Networks over-parameterizer (i.e., high-dimensional), so it may take a long time to escape local traps. In contrast, the heightened landscape-depended noise in DPSGD is anisotropic (Chaudhari & Soatto 2018 Feng & Tu 2020) and can drive the system to escape in the right directions.
usually
Learning Rate Tuning Table[Jand compare model quality (measured in either test accuracy or held-out loss) for different learning rates the large batch size setting, for CV and ASR tasks. By using a smaller learning rate, SSGD can escape early traps, yet it consistently lags behind DPSGD in the large batch setting.
Summary By systematically introducing landscape-independent noise and reducing the learning rate, SSGD could escape early traps (e.g., saddle points), but results in much inferior models compared to DPSGD in the large batch setting.
4.4
END-TO-END RUN-TIME COMPARISON AND ADVICE FOR PRACTITIONERS
Please refer to Appendix
CONCLUSION
In this paper, we investigate why DPSGD outperforms SSGD in the large batch training. Through detailed analysis on small-scale tasks and an extensive empirical study of a diverse set of modern DL tasks, conclude that the landscape-dependent noise, which is strengthened in the DPSGD system, brings two benefits in the large batch setting: (1) It adaptively adjusts the effective learning rate according to the loss landscape, helping convergence. (2) It enhances search in weight space find flat minima with better generalization. Based on our findings, we recommend that DDL practitioners consider DPSGD as an alternative when the batch size must be kept large, e.g., when shorter run time to reach a reasonable solution is desired.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In PMLR, Proceedings of Machine Learning Research, pp. 344-353.
PMLR, 2019.
Carlo Baldassi, Christian Borgs, Jennifer T. Chayes, Alessandro Ingrosso, Carlo Lucibello, Luca Sagli- etti, and Riccardo Zecehina. Unreasonable effectiveness of learning neural networks: From accessi- ble states and robust ensembles to basic algorithmic schemes. Proceedings of the National Academy of Sciences, 11344 2016. ISSN 0027-8424. doi: 10. 1..1077/paa..16881 1608103113 URL
https: /ww. pnas. wttp://.........oooeeo//////////
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. doi: 10.1 10.1109/ita.0011 2010.//ta.1118800222222 URL :ttt:://dt..oi..org/1......
8503224
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys, 2016.
Jeffrey Dean, Greg S. Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V. Le. Mark Z. Mao, Mare' Aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, and Andrew Y. Ng. Large scale distributed deep networks. In NIPS, 2012.
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:1703.11008, 2017.
Yu Feng and Yuhai Tu. How neural networks find generalizable solutions: Self-tuned annealing in deep learning. ArXiv, abs/2001.01678, 2020.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online stochastic gradient for tensor decomposition. Conference on Learning Theory, pp. 797-842, 2015.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4))2341-2366 2013.
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training imagenet in 1 hour. CoRR, abs/1 Ne617706002677 2017. URL http: /ttp:://arxiv ww..or///aa...... awtp///s///// /170 02677
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2015.
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.
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, pp. 5-13, New York, NY, USA, 1993. ACM. ISBN 0-89791-611-5. doi: 10. 10.1145/168304 168306. htRp:ttp://ooi acm. htt.:/oor/.......11.....1 111....11111111111118848000 118.83333.18880.5
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 911:: 1997.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. In Advances in Neural Information Processing Systems, pp. 1731-1741, 2017.
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/ 100404664,, 2017. URL http::://rxi..ooom org/abs/
1704. 04861

---

Under review as a conference paper at ICLR 2021
Jie Hu, Li Shen, and Gang Sun. Squeezz--an-eecitatio networks. CVPR, abs/ abss//79900107, URL pttt:://arxiie org. httggabb///0//00/ 01507
G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger. Densely connected convolutional networks. In 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp- 2261-2269, 2017.
Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint 2017.
Stanislaw Jastrzebski. Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Finding flatter minima with sgd. ICLR (Workshop), 2018.
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 1609v:1609.000
2016.
D. P. Kingma and J. L. Ba. ADAM: method for stochastic optimization. International Conference on Learning Representutions (ICLR), 2015.
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local 00000...611...22 2018.
minima? arXiv preprint
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Computer Science Department, University of Toronto, Tech. Rep, 1(4):7, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
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, art. arXiv:1909.09) 097566,,,9 September 2019.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 6389-6399.
Bengio, H. Wallach, H. Larochelle, K. Grauman, Cesa-
Curran Associates, Inc., 2018 URL 7875 1175-visualizing the- loss- www.scape- www.oo--nnuaa--eeeeeeeee pdf
Mu Li, David G Andersen, Jun Woo Park, Alexander J Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. In 1thh (USENIX) Symposium Operating Systems Design and Implementation ((OSDI) 14), pp. 583-598, 2014.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. In NIPS, 2017a.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 5330-5340, 201 7b.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In /CML, 2018.
Kang Liu. Train CIFARIO with PyTorch, 2020. URL http:::/ggithuub.ccm/uaaaaa citorch-cifaa Available at at /ttt::///itttuu com. wttp://wwww.///yttroocooooo
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general-
ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956,
2017a.
10

---

Under review as a conference paper at ICLR 2021
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564. 2017b.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018. URL URL/attes://ppereriiee
Mark Sandler, Andrew G. Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chii Chieh Chen. Inverted residuals and linear bottlenecks: Mobile networks for classification, detection and seg- mentation. CVPR, abs/1 801.001.000 100381411, 2018. / wttp:/wwww..ggg//////.111. 04381
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference Learning Representations, 2015.
Samuel L Smith and Quoe V Le. bayesian perspective on generalization and stochastic gradient descent. arXiv preprint arXiv: 2017.
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, 4b8/1409.4842, 2014. URL /tRL/tttp://axx...or03 wttpo////g////./..////./ 4842
Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural networks. ICML, abs//995.11994 2019. URL
11946
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, t. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 5998-60000 Curran Associates, Inc., 2017. URL http: -ot.teeetooo---lll-ooo---------- you-need. pdf
//papers nips..n......oo wttpsppppppppppeeeeeeeeeeeeeee ciaapeeesnpss.cc/ppee/////e/
Saining Xie, Ross B. Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual
transformations for deep neural networks. CVPR, abs/161 0E11611111553,,, 2017. URL http:://rxiv
brq/abs/1611. 05431
Yang You, Igor Gitman, and Boris Ginsburg. Scaling SGD batch size to 32k for imagenet training. CoRR, abs/ 03888, 2017. URL httptttp:///xttt wttrxxivorg/aab//1110
03888
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/1 904.00962, 2019. URL http
Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness-aware async-sgd for distributed deep learning. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pp. 2350-2356, 2016a.
Wei Zhang, Suyog Gupta, and Fei Wang. Model accuracy and runtime tradeoff distributed deep learning: A systematic study. In IEFE International Conference Data Mining, 201
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 2019a.
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 Sept 2019b.
system for automatic speech recognition. In INTERSPEECH
Wei Zhang, Xiaodong Cui, Abdullah Kayi, Mingrui Liu, Ulrich Finkler, Brian Kingsbury, George Saon. Youssef Mrouch, Alper Buyuktosunoglu, Payel Das, David Kung, and Michael Picheny. Improving efficiency in large-scale decentralized distributed training. In ICASSP 2020,, May 2020.
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. CVPR, abs/1707.01083 2018a. URL http!
7 Marxiva w/tpxx..org/abs//////////oo wwwaaab///1000000 01083
11

---

Under review as a conference paper at ICLR 2021
Yao Zhang, Andrew M. Saxe, Madhu S. Advani, and Alpha A. Lee. and the effecctivnness of stochastic gradient descent machine learning. Molecular Physics, 116 (21-22)3214-32223 Jun 2018b. ISSN 1362-3028. doi: 10. 10.1080000068896622211 2110:00226687772118888888888 1483535. URL
competition
ht 0tw.110000002899755000 2018. 1885335
12


Reviews:
[{"review_id": "wPUUpaUgqV4", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 claims that decentralized parallel SGD (DPSGD) performs better than synchronous SGD (SSGD) and noisy version of synchronous SGD (SSGD*) in large batch setting. Theoretically, it shows that the noise in DPSGD is landscape-dependent, which may help generalization. Experimental results on CV and ASR tasks show that DPSGD can outperform baselines when batch size is very large. Meanwhile, DPSGD is observed to adaptively adjust the effective learning rate and converge to flatter minima.\n\nAlthough the idea in the paper is insightful, most of the claims are lack of sufficient supports and in-depth discussion. For the theoretical part, Eq(4) only shows the differences of noise between SSGD and DPSGD. The explicit relation between Delta^(2) and generalization is not provided. After reading Eq.(4), I still do not know why Delta^(2) can help generalization. In my mind, Delta_S is also landscape-dependent because the covariance matrix of \\Delta_S aligns well with Hessian in some cases [1][2].\n\nThe explicit relation between decreasing effective learning rate and convergence rate of an optimization algorithm is not provided too. The convergence not only depends on the tendency of the learning rate but its decreasing rate. For an extreme instance, if the effective learning rate decreases rapidly, it is hard to imagine that it will help convergence. \n\nBesides, there are many writing issues in the paper. Please see the details comments below.\n\nDetailed comments:\n\n(1) For a scientific paper, every claim should be objective. There are many subjective claims in this paper. For example, \"Recently, ASGD has lost popularity due to.....\"(in Intro), \"One possible reason is that the complexity of escaping a saddle point.....\"(in Intro), \"The poor performance is likely due to......\"(in Sec2.1), etc. These claims are lack of sufficient supports  and are not convincing.\n\n(2) There are redundant notations which make the paper hard to follow. For example, the \"SSGD+noise\" in Figure 1 and \"SSGD*\" in Figure 2; the subscript of a letter sometimes denotes the learner, sometimes denotes the average or subset average.\n\n(3) Some claims are ambiguous. For example, \"It is clear that \\Delta^(2)\" depends on the loss landscape-it is larger in rough landscapes and smaller in flat landscapes\". What is the measure of the loss landscape and the flatness? Both landscape and flatness are descriptive terms and their measures should be clearly introduced. Why does the noise in SSGD not depend on landscape?\n\n(4) The term \"Multiple learners\" is misleading, especially for SSGD. It is better to name them local workers because they only calculated gradients and SSGD outputs a unified model. \n\n(5) I suggest to use the original format because this version looks too crowded. For example, the space between sections is too small and the paragraphs in the introduction are merged.\n\nIn summary, the current version is not ready to be published.\n\n[1] Wen, et al., An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise\n\n[2] Zhu, et al,. The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Minima and Regularization Effects.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "VgjV5yNNu57", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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 gives some empirical comparison of centralized sgd and decentralized sgd for relatively large batch size. The authors claim that decentralized sgd performs better than centralized version and that this is because the noise introduced by the decentralized version helps escape the local minima.\n\nWhile it is claimed that \"We show, both theoretically and empirically, that the intrinsic noise in DPSGD can...\", it is hardly possible to find any theoretical insight. The theoretical analysis part, Section 2, contains a figure (Figure 2) with an entire subsection (Section 2.2) discussing it, but include no theorem, lemma, or even proposition! There is clearly stated noise comparison between centralized sgd and decentralized sgd and thus it is not clear why one can claim decentralized sgd does better becomes of noise.\n\nSecond, as a paper studying the large batch setting, it is necessary to define what large batch means and how batch size relates to the convergence, none of which is included in the paper. In fact, in the theoretical analysis part (Section 2), batch size does not appear at all. Why is large batch size important, or is decentralized sgd always better than centralized one? The entire Section 2 is far away from understandable.\n\nThe experiment section also fails to justify the claim. The authors compared decentralized and centralized sgd for batch size = 1024, 2048, 4096, 8192. Are those all large batch, or is 1024 small and the other large? From Table 3 I guess it is the former case. But then a nature question is: does decentralized version perform poorly for small batch size? The experiment section  fails to show a \"phase transition\", which cannot support the claim. Furthermore, for vision tasks, evaluation on a single dataset (CIFAR10) is certainly not enough. Same thing for ASR task. Most importantly, there is no empirical evidence supporting the claim that decentralized sgd \" 1) [it] automatically adjusts the learning rate to improve convergence; 2) [it] enhances weight space search by escaping local traps (e.g., saddle points) to find flat minima with better generalization\".  Figure 3 and Figure 4 simply show properties of the neural network and the datasets and has nothing to do with optimization methods. Table 2,3,5,6 only shows final accuracy produced by the optimizers, but say nothing about how the optimizers reach the solutions.\n\nThe paper writing is problematic too. A single section (Section 3) talking about methodology with less than 1/3 page is awkward. Discussing empirical results in the analysis part (Section 2) is misleading. It is also not acceptable to have \"Please refer to Appendix F.\" for a whole subsection (4.4). Many sentences do not make sense. For example,  \"In a large batch setting, the learning rate must be increased to compensate for the reduced number of parameter updates\". Why is number of parameters updates reduced? \"While there was anecdotal evidence that DPSGD outperforms SSGD in the large-batch setting\". What is the evidence? Which paper claims this? There are numerous typos too.\n\nIn short, this paper is sloppy and far away from publishable in its current stage. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "RnQCkJEo8bu", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "#### Summary\nThis paper posits that gossip-based SGD methods for distributed deep learning are more stable, and generalize better, than synchronous SGD in large-batch settings. There is some intuitive discussion, but the hypothesis is mostly validated empirically on MNIST, CIFAR10, and several ASR tasks, for a wide variety of model architectures. I found this hypothesis very interesting, and to be of significant value to the community. I also found the approach sufficiently novel. The empirical evidence was convincing, but was restricted to very small-scale tasks, and so on larger datasets, it is not clear to me what the limiting batch-size is going to be where one observes the behaviour outlined in this work, or whether such a limiting batch-size even exists. The paper was also missing a study on the magnitude of the consensus error $\\Delta^{(2)}$ (via the graph topology) on model performance.\n\nIncluding a study on i) larger datasets and ii) various consensus errors $\\Delta^{(2)}$ via the graph topology, would strengthen the paper, and I would be happy to increase my support for this work.\n\n---\n#### Originality\nMost of the literature in this area has demonstrated that gossip-based methods converge faster (i.e., in wall-clock time), but to possibly higher error solutions. Previous literature has also demonstrated that this gap can be bridged with longer training. By consider extremely large batch-sizes, this work demonstrates that there may be a regime in which gossip-based methods are more stable and generalize better.\n\nThe paper first sets out to intuitively describe this phenomenon by decomposing the noise in the gradient-based updates. The decomposition is provided as the sum of a \"true\" gradient term and an orthogonal component. I quite liked this approach to the decomposition because it then allows the author to describe what they refer to as the effective learning-rate — a quantity that they can empirically measure in practice. While I generally liked this exposition, there is a minor error, which seems inconsequential for the rest of the paper: it is stated that these noise terms $\\eta$ are unbiased, which as far as I understand doesn't appear to be correct. Generally speaking, under unbiased sampling, the noise term $\\eta$ has zero mean if the gradients are evaluated at $w_\\alpha$ (or are linear in their argument), but not if they are evaluated at $w_j$, as in DPSGD; i.e., $E[\\frac{1}{n}\\sum_{j}g_j(w_j)] \\neq E[g(w_a)]$, where the expectation is with respect to the mini-batch sampled across all workers. Though more generally, I also liked the highlighted relationship between the noise strength $\\Delta$ and the effective learning learning rate $\\alpha_\\epsilon$, which does not depend on this (possibly erroneous) zero-mean property.\n\nThe hypothesis is thereafter tested through extensive experiments on MNIST, CIFAR10, and various ASR tasks for a broad range of hyperparameters.  Both the goal of the paper, and the approach taken to address it (i.e., through the reasoning of effective learning rates), are sufficiently novel in my opinion.\n\n---\n#### Quality and Significance\n\nLarge batch deep-learning is of significant interest for parallelizing deep learning workflows. There do exist known limitations for scaling large-batch training, and therefore finding a regime (in the limit of large batches) in which certain methods are not only more efficient, but also more effective, is certainly of value to the community.\n\nI am not familiar with ASR baselines, but the vision baselines look reasonable. I was actually quite surprised by Figure 1. I was not aware of this behaviour for SGD with large batch sizes on CIFAR10. However, I would be interested to see if this observation is particular to CIFAR10 on vision tasks, or whether similar results hold on ImageNet, which is much more stable to large batch-sizes. For example, training on ImageNet with the same batch-size is known to work well. One question I have concerns a subtle point that could explain the results you’re seeing in Fig.1: is the loss (and accuracy) being computed before or after averaging/gossiping the weights? The step-size is scaled according to the batch-size, and your large-batch update is only complete after averaging/gossiping, therefore $w_j$ is a poorly specified set of model weights, and the curves should be evaluated at $w_a$.\n\nMore generally, modulo this important distinction in my opinion, I found the empirical evidence convincing. However, my main concern is that the analysis was only on very small-scale tasks, and so on larger datasets, it is not clear to me what the limiting batch-size is going to be where one observes the behaviour outlined in this work, or whether such a limiting batch-size even exists.\n\nWhat was missing was also a study on the effect of the graph topology. It is stated in the appendix that 16 learners with randomized communication was found to work well, but I think crucial to this discussion is how the consensus error $\\Delta^{(2)}$, which depends on the graph topology, affects this aforementioned behaviour.\n\nAre the observations of the 2D contour and hessian plots consistent across multiple sampled directions? I ask because the parameters are 100-dimensional, and so it may not be the case that the level sets are entirely characterized by these 2 random vectors.\n\n---\n#### Clarity\n\nThe work is clear for the most part. Some minor comments on the exposition\n* The last approximation in equation 4 is not clear to me (e.g., what is the double subscript on the weights), though I agree with the following sentence, that the consensus error is going to be larger in sharper landscapes.\n* Not sure what qualifies as a “generic algorithm” so I would remove the phrase \"To the best of our knowledge, we are unaware of any generic algorithm that can improve SSGD large batch training on this many models/tasks.\"\n* I would temper sharp vs flat minima arguments, since these arguments have been shown to depend on the parameterization of the objective.\n* Decentralized training can be synchronous (e.g., via all-reduce), and so I don’t think the real distinction (i.e., gossip-based vs globally synchronous methods) is well captured in the title or the exposition.\n* The common argument that large batches converge to sharp minima is still a largely experimental idea, and so basing an argument on these principles does not provide convincing evidence (especially since such arguments depend on the parameterization of the objective).\n* How is the complexity of escaping a saddle point computed, and why is it assumed that the models in Figure 1 are stuck in saddle points. Phrases like this should be somewhat tempered, or at least discussed in more detail: “However, this is not a good solution for high-dimensional DL training as shown in the blue curves of Figure 1. One possible reason is that the complexity of escaping a saddle point by adding isotropic noise has a polynomial dependency on the dimension of the parameter space, so adding such noise in a high dimensional space (such as deep learning) does not bring significant benefits\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "CLOdTfGe9ce", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 did comprehensive experimental study on how DPSGD and SSGD converge in different tasks. Some intuition is provided to explain why DPSGD usually performs better than SSGD under large batch settings. Training with large batch size is a very important topic nowadays to speedup deep learning pipelines. In this paper different models, learning rates, and datasets are evaluated. Overall I feel the experiments show a good sign that decentralization is helpful in this case. \n\nIn my opinion the experiments in this paper are valuable, but I would be more happy to see this paper to inspire some solid theoretical studies on exactly why decentralized (and other tricks) can help the large batch training problem (and when they will fail). \n\nSome additional things I would love to see in the revision:\n* comparing with SSGD with \"warmup\" where the learning rate increases from a small value at the beginning of training. This kind of warmup lr schedule has been shown effective in some existing work (for example, Goyal, Priya, et al. \"Accurate, large minibatch sgd: Training imagenet in 1 hour.\" arXiv preprint arXiv:1706.02677 (2017).), and should mitigate that convergence issue mentioned in this paper.\n* code to help other practitioners verify the results\n\nI wanted to give a accept but the formatting of this paper has a lot of room to improve. To list a few:\n* duplicated references in the reference section\n* page 2 footnote 2, the line below equation (2): quote should be fixed\n* sections titles formatting (capital letter or not) should be consistent", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper did experimental studies on how DPSGD and SSGD converge in different tasks. Some concerns were raised regarding the clarity, some unjustified claims, baselines and etc, and partially addressed after the rebuttal and discussions. However, some critical concerns remains. The reviewers agreed that the paper would be more appealing if these concerns can be well addressed.
Decision: Reject