Don't Use Large Mini-batches, Use Local SGD
Authors: Tao Lin
Sebastian U. Stich
Kumar Kshitij Patel
Martin Jaggi
Venue:  (2020)

Abstract: Mini-batch stochastic gradient methods (SGD) are state of the art for distributed training of deep neural networks. 
Drastic increases in the mini-batch sizes have lead to key efficiency and scalability gains in recent years. 
However, progress faces a major roadblock, as models trained with large batches often do not generalize well, i.e. they do not show good accuracy on new data.
As a remedy, we propose a \emph{post-local} SGD and show that it significantly improves the generalization performance compared to large-batch training on standard benchmarks while enjoying the same efficiency (time-to-accuracy) and scalability. We further provide an extensive study of the communication efficiency vs. performance trade-offs associated with a host of \emph{local SGD} variants. 


Published as a conference paper at ICLR 2020
DON'T USE LARGE MINI-BATCHES, USE LOCAL SGD
Tao Lin
Sebastian U. Stich EPFL, Switzerland sebastian. sticheepl.
EPFL, Switzerland tao. 1ew.1ineepff.cc
Kumar Kshitij Patel
Martin Jaggi
IIT Kanpur, India kumarkshättipateellegee com
EPFL, Switzerland martin. i www.gjapggggicccoooo. ch
ABSTRACT
Mini-batch stochastic gradient methods (SGD) are state of the art for distributed training of deep neural networks. Drastic increases in the mini-batch sizes have lead to key efficiency and scalability gains in recent years. However, progress faces major roadblock, as models trained with large batches often do not generalize well, i.e. they do not show good accuracy on new data.
As a remedy, we propose post-local SGD and show that it significantly improves the generalization performance compared to large-batch training standard and scalability.
benchmarks while enjoying the same efficiency We further provide extensive study of the communication efficiency performance trade-offss associated with host of local SGD variants.
INTRODUCTION
Fast and efficient training of large scale deep-learning models relies on distributed hardware and on distributed optimization algorithms. For efficient use of system resources, these algorithms crucially must (i) enable parallelization while being communication efficient, and (ii) exhibit good generalization behaviour, i.e. good performance unseen data (test-set). Most machine learning applications currently depend on stochastic gradient descent (SGD) (Robbins & Monro 1985) and in particular its mini-batch variant (Bottou 2010 Dekel al. 2012). However, this algorithm faces generalization difficulties in the regime of very large batch sizes as we will review now.
Mini-batch SGD. For a sum-structured optimization problem where E Bd denotes the parameters of the model and fa: Rd R the loss function of the i-th training example, the
form min N Σ (ww
SGD update for K > workers is given as
K Σ
E EIIIE v)((w)))
((++1 (() 7(0)
K
where Y(s) > 0 denotes the learning rate and Z// S [N] the subset (mini-batch) of training datapoints selected by worker ic (typically selected uniformly at random from the locally available datapoints on worker k). For convenience, we will assume the same batch size B per worker.
Local SGD. Motivated to better balance the available system resources (computation vs. commu- nication), local SGD (a.k.a. local-update SGD, parallel SGD, or federated averaging) has recently attracted increased research interest (Mcdonald et al. 2009 Zinkevich et al.] 22010] McDonald al. 2010 Zhang et al.] 2014 2016 McMahan et al. 2017). In local SGD, each worker k E [K] evolves a local model by performing H sequential SGD updates with mini-batch size B before communication (synchronization by averaging) among the workers. Formally,
w (0+1+1 == w/ 1 "(0)
EETT co+t
(i
wirrn := & ΣK w
(2)
(0+H
where w + denotes the local model on machine & after global synchronization rounds and subsequent h [H] local steps (I& is defined analogously). Mini-batch SGD is special case

---

Published as a conference paper at ICLR 2020
1.50
1.25
AL mineauch docnt L. But
Seb Maa!
Top-7 Treising Accuracy
100
90
Top-1 Test Accuracy
90
1.00
noar 500 34 Ho
0.75
70
85
min-bann 5G0 res huin
560 D.
0.50
60
80
Jin Piu
0.25
lirut 5o0 sf
lrne 900 11.
pussicaal 5GD
para Min (6.1-224)
300
150
200
250
309
Epoch
Epach
Spoch
(a) Training loss.
(b) Training top- accuracy.
(c) Test top-1 accuracy.
accuracy training set
accuracy lest
system performance
Algorition
Joss
lop-1 acc.
lup-1 acc.
parallelism
communicctiin
A]: small mini-butch SGD (K 1, Buc)
0.01
100%
excellent
98%
excellent
x1
pour
A2: large mäni batch SGD (K- 16, BBB)
0.01
100%
encellonr
92%
good
x16
+1
ok
huge mini batch SGD (K 16.5 1Bxx)
0.10
81%
poor
80%
paur
x16
SGD
l7
00.01
95%
92%
good
x16
good
AS: post-local SGD (KC 16, 15- 16)
00.01
90%
exceliout
935%
excellent
X16
:1 (phase 1), 18 18iphase 2)
good
Figure I: Illustration of the generalization gap. Large-batch SGD (A2. blue) matches the training curves of small- batch SGD (AI, green), i.c. has no optimization difficulty (left & middle). However, it does not reach the same test accuracy (right) while the proposed post-local SGD (A5, red) does. Post-local SGD (A5) is defined by starting local SGD from the model obtained by large-batch SGD (A2) at epoch 150. Mini-batch SGD with larger mini-batch size (A.3, yellow) even suffers from optimization issues. Experiments are for ResNet-20 on CIFAR-10
( [Bix== = 128), with fined-tuned learning rate for mini-batch SGD with the warmup scheme in Goyal et al. (2077). The inline table highlights the comparison of system/ggeerralization performance for different algorithms.
if H = 11and and Bis = B. Furthermore, the communication patterns of both algorithms are identical if B Bbc. However, as the updates (eq. (2) are different from the mini-batch updates (eq. D for any H > 1, the generalization behavior (test error) of both algorithms is expected to be different.
Large batch SGD. Recent schemes for scaling training to a large number of workers rely on standard mini-batch SGD ( with very large overall batch sizes (Shallue et al. 2018 You et al. 2018, Goyal et al. 2017). i.e. increasing the global batch size linearly with the number of workers K. However, the batch size interacts differently with the overall system efficiency on one hand, and with generalization performance on the other hand. While larger batch size in general increases throughput, it may negatively affect the final accuracy on both the train- and test-set. Two main scenarios of particular interest can be decoupled as follows:
Scenario 1. The communication restricted setting, where the synchronization time is much higher than the gradient computation time. In this case the batch size of best efficiency is typically large, and is achieved by using partial computation (gradient accumulation) while waiting for communication. We in particular study the interesting case when the mini-batch sizes of both algorithms satisfy the relation B == H Bioe. in this case both algorithms (local SGD and mini- batch SGD) evaluate the same number of stochastic gradients between synchronization steps.
Scenario 2.
The regime of poor generalization of latge-batch SGD, that is the use of very large overall batches (often a significant fraction of the training set size), which is known to cause drastically decreased generalization performance (Chen & Huo 2016 Keskar al., 2017] Hoffer let al. 2017 (Shallue et al.] 2018: Golmant et al.) 2018). If sticking to standard mini-batch SGD and maintaining the level of parallelisation, the batch size B would have to be reduced below the device (locally optimal) capacity in order to alleviate this generalization issue, which however impacts training time"
Main Results. Key aspects of the empirical performance of local SGD compared to mini-batch baselines are illustrated in Figure [ In scenario 1), comparing local SGD with H = 4 (A4) with mini-batch SGD of same effective batch size B = 4 (A3) reveals a stark difference, both in terms of train and test error (local SGD achieves lower training loss and higher test accuracy). This motivates the use of local SGD as an alternative to large-batch training a hypothesis that we confirm in experiments. Further, in scenario 2), mini-batch SGD with smaller batch size B B (A2) is observed to suffer from poor generalization, although the training curve matches the single-
Note that in terms of efficiency on current GPUs, the computation time on device for small batch sizes is constant but scales non-lincarly with B, as shown in Table 7 in Appendix
2

---

Published as a conference paper at ICLR 2020
machine baseline (A1). The generalization gap can thus not be explained an optimization issue alone. Our proposed post-local SGD (A5) (defined by starting local SGD from the model obtained by large-batch SGD (A2) epoch 150) closes this generalization gap with the single-maching bascline (A1) and is also more communication efficient than the mini-batch competitors. In direct comparison, post-local SGD is more communication-efficeenn than mini-batch SGD (while less than local SGD). It achieves better generalization performance than both these algorithms.
Contributions. Our main contributions can thus be summarized as follows:
Trade-offs in Local SGD: We provide the first comprehensive empirically study of the trade-offs in local SGD for deep learning -heii -hen varying the number of workers K, number of local steps H and mini-batte sizes for both scenarios 1) on communication efficiency and 2) on generalization.
We propose post-local SGD, a simple but very efficient training scheme to address the current generalization issue of large-batch training. It allows us to scale the training to much higher number of parallel devices. Large batches trained by post-local SGD enjoy improved communication efficiency, while the same time strongly outperforming most competing small and large batch baselines in terms of accuracy, Our empirical experiments on standard benchmarks show that post-local SGD can reach flatter minima than large-batch SGD on those problems.
Post-local SGD:
2 RELATED WORK
The generalization gap in large-batch training. State-of-the-art distributed deep learning frameworks (Abadi et al. 2016 Paszke et al. 2017; Seide & Agarwal (016) resort to synchronized large-batch SGD training, allowing scaling by adding more computational units and performing data-parallel synchronous SGD with mini-batches divided between devices. Training with large batch size (e.g. batch size 10 on ImageNet) typically degrades the performance both in terms of training and test error (often denoted as generalization gap) (Chen & Huo [016)] [i] 2017 Li et al., 2014, Keskar et al. 2017 Shallue et al. 2018 McCandlish al. 2018 Golmant et al. 2018 Masters & Luschi| 2018). Goyal et al. (0117) argue that the test error degrades because of optimization issues and propose use a "learning rate warm-up" phase with linear scaling of the step-size. You et al.) (2017a) propose Layer-wise Adaptive Rate Scaling (LARS) to scale to larger mini-batch size, but the generalization gap does not vanish. HHofer et al. (2017) argue that the generalization gap can be closed when increasing the number of iterations along with the batch size. However, this diminishes the efficiency gains of parallel training.
Keskar et al. (011)) empirically show that larger batch sizes correlate with sharper minima (Hochreiter & Schmidhuber 1997) found by SGD and that flat minima are preferred for better generalization. This interpretation despite being debated in Dinh et al. (2017) was further developed in Hoffer ct al. (2017); Yao et al. (2018); Izmailov et al. (2018). Neelakantan et al. (2015) propose to add isotropic white noise to the gradients to avoid over-fitting and better optimization. Zhu et al. (019); ; Xing et al. 2018) further analyze "structured" anisotropic noise and highlight the importance of anisotropic noise (over isotropic noise) for improving generalization. The importance of the scale of the noise for non-convex optimization has also been studied in Smith & Le (011)); Chaudhari & Soatto (0018). Wen al. (219)) propose inject noise (sampled from the expensive empirical Fisher matrix) to larce-batch SGD. However, to our best knowledge, none of the prior work (except our lost-local SGD) can provide a computation efficient way to inject noise to achieve as good generalization performance as small-batch SGD, for both of CIFAR and ImageNet experiments.
Local SGD and convergence theory. While mini-batch SGD is very well studied Ziikeevihh et al.. 2010; Dekel et al. 2012) Takač et al., 2013), the theoretical foundations of local SGD variants still developing. Jain et al. (2018) study one-shot averaging
quadratic functions and Bijral ct al. (2016) study local SGD in the setting of a general graph of workers. A main research question is whether local SGD provides linear speedup with respect to the number of workers K, similar to mini-batch SGD. Recent work partially confirms this, under the assumption that H is not too large compared to the total iterations Z'. [ttchh (2019) and Patel & Dieuleveut (2019) show convergence at rate ((TTHBB)))) on strongly convex and smooth objective functions when H = 122) For smooth non-convex objective functions, Zhou & Cong (0018) show a rate of 1/2 (for the decrement of the stochastic gradient), Yu et al. (019 give an improved
3

---

Published as a conference paper at ICLR 2020
when H O(T)/4) For diseussion of more recent theoretical results we refer to (Kairouz et al, 2019). Alistarh et al. (2018) study convergence under adversarial delays. Zhang et al. (2016) empirically study the effect of the averaging frequency on the quality of the solution for some problem cases and observe that more frequent averaging at the beginning of the optimization can help. Similarly, (Bijral al. (2016) argue to average more frequently at the beginning.
result ((H
POST-LOCAL SGD AND HIERARCHICAL LOCAL SGD
In this section we present two novel variants of local SGD. First, we propose post-local SGD reach high generalization accuracy (cf. Section 4.2 beloww, and second, hierarchical SGD designed from a systems perspective aiming at optimal resource adaptivity (computation vs. communication trade-off).
Large-batch Training Alternative for Better Generalization. We propose post- local SGD, variant where local SGD is only started in the second phase of training, after /' initial Step 2 with standard mini-batch SGD. Formally, the update in is performed with a iteration dependent H(t) given as
Post-local SGD:
-
f1,
i', {H, ift t'
(mini-batch SGD) (local SGD)
H(o) =
(post-local SGD)
As the proposed scheme is identical to mini-batch SGD in the first phase (with local batch size B = B,oc), we can leverage previously tuned learning rate warm-up strategics and schedules for large-batch training (Goyal et al. 2017) without additional tuning. Note that only use 'small' local mini-batches of size B Bise in the warm-up phase, and switch to the communication efficient larger effective batches H Buse in the second phase, while also achieving better generalization in experiments (cf. also the discussion in Section (5. We would like to point out that it is crucial to use local SGD in the second phase, as e.g. just resorting to large batch training does achieve worse performance (see e.g. 3rd row in Table 2 beloow.
Hierarchical Local SGD: Optimal Use of Systems Resources in Heterogeneous Systems. Real world systems come with different communication bandwidths on several levels, e.g. with GPUs or other accelerators grouped hierarchically within chip, machine, rack or even the level of entire data-centers. In this scenario, we propose to employ local SGD as an inner loop on each level of the hierarchy, adapted to the corresponding computation vs communication trade-off of that particular level. The resulting scheme, hierarchical local SGD, can offer significant benefits in terms of system adaptivity and performance, as we show with experiments and a discussion in Appendix D
EXPERIMENTAL RESULTS
In this section we systematically evaluate the aforementioned variants of local SGD on deep learning and
tasks. In summary, the main findings presented in Sections 4.1 and below are:
Local SGD, on the one hand, can serve as a communication-effiieen alternative to mini-bateh SGD for different practical purposes (communication restricted Scenario 1). For example in Figure 2(a) (with fixed Bise and K), in terms of 92.48% best test accuracy achieved by our mini-batch SGD implementation for K = 16. practitioners can either choose to achieve reasonable good training quality (91.2%, matching (He et al. 2016al) with a 2.59x x speedup (time-to- come-to--ccuracy in training time (H = =), or achieve slight better test performance (92.57%) with slightly reduced communication efficiency (1.76x x speedup for 2)
Post-local SGD, on the other hand, in addition to overcoming communication restrictions does provide a state-of-the-att remedy for the generalization issue of large-batch training (Scenario 2). Unlike local SGD with large H and K (e.g. H = 16, K = 16) which can encounter optimization issues during initial training (which can impact later generalization performance), we found that post-local SGD elegantly enables an ideal trade-off between optimization and generalization within a fixed
"The switching time t' between the two phases our experiments determined by the first learning rate decay. However could be tuned more generally aiming at capturing the time when trajectory starts to get into the influence basin of a local minimum (Robbins & Monro 1985] Smith et al. 2018 Loshchilov & Hutter 2017 Huang et al. (001aa) 7a). Results in Appendix B.4.2 and empinically evaluate the impact of different I' on optimization and generalization.
4

---

Published as a conference paper at ICLR 2020
training budget (e.g. Table 3 Table 5 Figure 3 and many others in Appendix C.5 and can achieve the same or even better performance than small mini-batch baselines.
Setup. We briefly outline the general experimental setup, and refer to Appendix A for full details.
Datasets. We evaluate all methods on the following two main (standard) tasks: (1) Image classification
for CIFAR- 10/100 (Krizhevsky & Hinton| 2009), and (2) Image classification for ImageNet (Rus
sakovsky et al. 2015). The detailed data augmentation scheme refers to Appendix A
Models. We use ResNer-20 (He et al.) 2016a) with CIFAR-10 as base configuration to understand different properties of lloct SGD. We then empirical evaluate the large-batch training perfor- mance of post-local SGD, for ResNet- DensetNet-40-12 (Huang al.. (017b) and WedeResNNet-
28-10 10-10 Zagoruyko & Komodakis] 2016) on CIFAR-10/100) Finally, we train ResNet-50 (He et al. 201 on ImageNet to investigate the accuracy and scalability of (post-)local SGD training.
Implementation and platform. Our algorithms are implemented in PyTorch (Paszke et al., 2017). with flexible configuration of the machine topology supported by Kubernetes. The cluster consists of Intel Xeon E5-2680 v3 servers and each server has 2 NVIDIA TITAN Xp GPUs. We use the notion a x 1-GPU to denote the topology of the cluster, i.e., a nodes and each with GPUs.
Specific learning schemes for large-batch SGID. We rely on the recently proposed schemes for efficient large batch training (Goyal al., (2177, which are formalized by (i) linearly sealing the learning rate w.r.t. the global mini-batch size; (ii) gradual warm-up of the learning rate from small value. See Appendix A.3 for more details.
Distributed training procedure CIFAR- 10/100. The experiments follow the common mini-batch SGD training scheme for CIFAR (He et al. 2016a by Huang et al. 2017b) and all competing methods access the same total number of data samples (i.e. gradients) regardless of the number of local steps. Training ends when the distributed algorithms have accessed the same number of samples as the single-worker baseline. The data is disjointly partitioned and reshuffled globally every epoch. The learning rate scheme follows (He et 20. 6a Huang et al. (0176). where we drop the initial learning rate by a factor of 10 when the model has accessed 50% and 75% of the total number of training samples. Unless mentioned specifically, the used learning rate is scaled by the global mini-batch size (BK for mini- SGD and B for local SGD) where the initial learning rate is fine-tuned for each model and each task for the single worker. See Appendix A.4 for more details.
4.1 SUPERIOR SCALABILITY OF LOCAL SGD OVER MINI-BATCH SGD
First, we empirically study local SGD training for the communication restricted case (i.e. Scenario 1). As local SGD (with local batch size B needs H times fewer communication rounds than mini- batch SGD (with the same batch size B = Bioe) we expect local SGD to significantly outperform mini-batch SGD terms time-to-aceuracy and scalability and verify this experimentally. We further observe that local SGD shows better generalization performance than mini-batch SGD.
Significantly better scalability when inereasing the number of workers on CIFAR, in terms of tine-to-accuracy. F demonstrates the speedup auce-to-ac for training ResNet-20 for CIFAR-10, 10, with varying number of GPUs K and the number of local steps H, both from 1 to 16.
Table Scaling behavior of local SGD in clock-time for increasing number of work- ers K, for different number of local steps H, for training ResNet-20 Bude 128. The reported speedup (averaged over three runs) is over single GPU training time for reaching the baseline top-1 test accu- racy (91.2% as in (He et al. (216))). We use 8 2-GPU cluster with 10 Gbps network. H recovers mini-hatch SGD.
Spoodup wirt the sccurscy
CIFAR-10 with
workers (9)
Our code is available at httppp://gichu..co///ppp//////// 1
5

---

Published as a conference paper at ICLR 2020
We demonstrate in Figure I that local SGD scales 2x better than its mini-batch SGD counterpart, in terms of time-to to-euucrcy as we increase the number of workers K on a commodity cluster. The local update steps (H) result in strong advantage over the standard large- barge-bach training. Mini-batch SGD fixes the batch size to B = Blx. and while increasing the number workers K gets impacted by the communication bottleneck (section D even as parallelism per device remains unchanged. In this experiment, local SGD on 8 GPUs even achieves a 2x lower time-to-accuracy than mini-batch SGD with 16 GPUs. Moreover, the (near) linear scaling performance for H/ = 8 in Figure | shows that the main prpee-parameter H of local SGD is robust and consistently different from its mini-batch counterpart, when scaling the number of workers.
Effectiveness and scalability of local SGD to even larger datasets (e-g,, ImageNet) and larger clusters. Local SGD presents a competitive alternative to the current large-batdl ImageNet training methods. Figure in Appendix B.3.2 shows that we can efficiently train state-of-the-an ResNet-50
(at least 1.5x x speedup to reach 75% top-1 accuracy) for ImageNet (Goyal et al. 2017 You et al. 2017a) via local SGD on a 16 x 2-GPU cluster.
Local SGD significantly outperforms mini-batch SGD at the same effective batch size and communication ratio. Figure 2 compares local SGD with mini-batch SGD of the same effective batch size, that the same number of gradient computations per communication round as described in Scenario above (Section I.
$2.75
$3.00
7op Test Accuracy
Top-1 Test Accuracy
1 Test Accuracy
12.50
92
90
$2.25
32:00
85
91
11.75
1012
Top-1
H+-4
80
H+g
11.25
90
33.00
16
of war tera 1O0
workerrs (1)
workers (K)
workers
of workers (X)
(a) Top-1 test accuracy of local SGD. H = 1 is mini-batch SGD
(b) Top-1 test accuracy of local SGD (circle) vs. mini-batch SGD (triangle). with same effective batch size B = H B per worker. The points for given K have the same communication cost.
with optimal hyper-parameters.
Training ResNet-20 CIFAR-10 under different K and H, with fixed B 128. All results averaged over three runs and all settings access to the same total number of training samples. We fine-tune the learning rate of mini-batch SGD each setting.
Figure 2:
4.2 (POST)-LOCAL SGD CLOSES THE GENERALIZATION GAP LARGE-BATCH TRAINING
Even though local SGD has demonstrated effective communication efficiency with guaranteed test performance (Scenario 1), we observed in the previous section that it still encounters difficulties when scaling very large mini-batches (Figure 2(a)). though is much less affected than mini-batch SGD (Figure 2.b).. Post-local SGD can address the generalization issue of large batch training (Scenario 2)
as we show now, First, we would like to highlight some key findings Table
Table 2: Test performance (generalization) for local SGD variants and mini- SGD (highlighting selected data from Figure 2 Table and Figure 3) Mini-batch SGD suffers from the generalization gap (and sometimes even from optimization issues due insufficient training) when scaling larger H and K. Same experimental setup as Figure [ (fine-tuned mini-batch SGD baselines). The " denotes the transition the first learning rate decay. The reported results are averaged over three runs.
Algoritim
Top-1 acc.
butch
Algorittu
Top-1 acc.
Mini buch SGD (K 4)
92.6%
KB=512
Mini hatch SGD (K 16)
92.5%
Mini buch SGD (K
89.5%
KB
Mini-hatch
76.3%
16384
Mini butch SGD (K 4)
92.5%
KB = 512 8192
Mini butch SGD (K 16)
92.0%
KHB 2048 -+ 16384
Local
A 4)
92.5%
KHB.
8, 16)
KH. 16381
Post-local SGD (H 16, K
92.7%
K...B. = 512
8192
Rost- SGD (H = 8, K 16)
92.9%%
KH = 2018 -+ 16381

---

Published as a conference paper at ICLR 2020
We now focus the generalization issues (Section I of large-batch SGD, isolating the potential negative impact from the optimization difficulty (e.g. the insufficient training epochs (Shallue et al. the test set. Our evaluation starts from (standard) constant effective mini-batch size of 2048 or 4096 for mini-batch SGI on CIFAR dataset, as in (Keskar et al. 2017
2018)) from the performance
Hoffer et al. 2017 Yao et al. (018).
Post-local SGD generalizes better and faster than mini-batch SGD. Table 3 summarizes the generalization performance of post-local SGD on large batch size (K 16, Bice 128) across different architectures on CIFAR tasks for = 16 and H = =2. Under the same setup, Table 9 in the Appendix C.3 evaluates the speedup of training, while Figure demonstrates the learning curves of mini-bated SGD and post-local SGD, highlighting the generalization difficulty of large-batch SGD. We can witness that post-local SGD achieves at least 1.3x speedup over the whole training procedure compared to the mini-batch SGD counterpart (K = 16, B = 128), while enjoying the significantly improved generalization performance.
Table 3: Top-1 test accuracy of training different CNN models via post-local SGD on K = 16 GPUs with a large global batch size (K Bise = 2048). The reported results are the average of three runs and all settings access the same total number of training samples. We compare small and large mini-batch baselines. The indicates a fine-tuned learning rate, where the tuning procedure refers to Appendix A.4
CIFAR-10
CIFAR-100
Small batch
Large batch
Post-lucal SGD
Pred-local SGD (HI-32)
Small butch
Large butch
Pred-lecal SGD
Post-local SGD (11-22)
baseline +
baseline
(H-16)
buseline JC=2, H-
baseline-
(H-16)
X=2, 128 X B- 128 K 16, Bac- 128 K -6, Hb_ - 128
K H- 128 X 16, Haa 128 K- 16, Bg. 128
RosNet-20
92.63 20,00
92.48 20:17
02.80 10:1
98.02
16:1
68.84 2006
08.17
20:18
60.24
20.00
09.38 1: 00:00
DemsoNet-40-12
94.41 20.14
94.36
20.00
91.43
10012
94.58 10/11
74.85 20114
74.06
20:00
74:45
20.00
75 10005
WidekkesNet-25-10
85.89 =0.10
96.43
+0.57
96.9 96.94 +0.06
90.76 -6.26
79.78
10.16
79.31
-0.28
81.28 +0.13
80. 80.66 +0016
We further demonstrate the generalization performance and the scalability of post-local SGD, for diverse tasks (e.g., Language Modeling), and for even larger global batch sizes (K Bice = 4096 for CIFAR-100 and 4096 and 8192 respectively for ImageNet), in Appendix C.5 For example, Table 11 presents the severe generalization issue (2% drop) of the fine-tuned large-batch SGD training (KB 4096) for above three CNNs on CIFAR-100, and cannot be addressed by increasing the training steps (Table[12. Post-local SGD (K Bise = 4096) with default papee--rrameterss can perfectly close this generalization gap or even better than the fine-tuned small mini-batch baseline For ImageNet training in Figure T6] the post-local SGD outperforms mini-batch SGD baseline for both of K = 4096 (76.18 and 75.87 respectively) and KB= = 8192 (75.65 and 75.64 respectively) with 1.35x x speedup for the post-local SGD training phase.
The effectiveness of post-local SGD training for different H and K. As seen in Figure (aa applying any number of local steps over the case of batgh-batch training (when K Brx = 2048) improves the generalization performance compared to mini-batch SGD. Figure 3(b illustrats that post-local SGD is better than mini-batch SGD in general for different number of workers K (as well as different K B,c)). Thus, post-local SGD presents consistently excellent generalization performance.
Post-local SGD can improve the training efficiency upon other compression techniques. The results in Table 4 illustrate that post-local SGD can be combined with other communication-effican techniques (e.g. the sign-based compression schemes) for further improved communication efficiency and better test generalization performance.
Post-local SGD can improve upon other SOTA optimizers. The benefits of post-local SGD training on ImageNet are even more pronounced for larger batches (c.g. K KBo > 8192) (Goyal et al..
'It is less challenging (e.g. comparing the first and third rows in the right column of Table 2 to train with mini-batch SGD for medium-size, constant effective mini-bate bini-batch size. In our evaluation. the training of the post-local SGD and mini-batch SGD will start from the same effective mini-batch size with the same number of workers K. Even under this relaxed comparison, post-local SGD still significantly outperform mini-hatch SGD.
We omit the comparison with other noise injection methods none of them (Ncelakantan et al. 2015 Wen
2019) can completely address the generalization issue even for CIFAR dataset.

---

Published as a conference paper at ICLR 2020
clacsifiation Acturayy
95.0
02.2
02.8
Clazaiiatttan
$2.8
92.6
92.4
92.4
92.2
may natch with
64
The number local staps (1
of workers (K)
(a) Performance of poct-local SGD for different numbers local steps H on 16 GPUs. l mini-batch SGD and Bise 2048.
(b) Performance of post-local SGD for different numbers of workers for 16 and 32. The local batch size fixed to Blue B = 128 both for local and mini-batch SGD).
Figure 3: Top-1 test accuracy of training ResNet-20 on CIFAR-10. Box-plot figures are derived from runs. Table Top-1 accuracy training ResNet-220 on CIFAR via sign-based compression scheme and post- local SGD (K 2048 and K = 16). = in the table for the simplicity corresponds to the original sign-based algorithm and we fine-tune their hyper-parameters. The reported results are the average of three runs with difterent seeds. The learning rate schedule is fixed for different local update steps (for H 1). For the detailed tuning procedure, training scheme, as well as the pseudo code the used variants, we refer to Appendix C.3.5
CIFAR-19
CIEAR-100 100
11
21
16
17
11 14
11
21
--
stmSGD Bermsiiin et ald 2018 BI sDp3SD Karmarso an 2019
01:61
+6.28
91.77
00.4
92.22
+0.11
92,00
+8.15
67.21
+0.11
67.41
+0.30
68.32
+0.11 00.4
+6.88
08.12
92:45
10.38
92.63
-0.30
92.72
0000
92.76
10.00
08.19
10.10
09.14
60.30
60.00
69.49
10.21
2017, Shallue et al. 2018 Golmant al. 2018 Considering other optimizers, Table below shows
that local SGD can improve upon LARS You et al. 2017a).
Table 5: The Top-1 test accuracy of training ResNet50 ImageNet. We report the performance (w/ w/o post-local SGD) achieved by using SGD with Nesterov Momentum, learning schemes (Goyal et al. 2017). and LARS. We follow the general experimental setup described in Section A.4.2 and use K = 32 and
SGD Momentum LARS SGD Momentum LARS Post-local
Dus 192
76.13
K B.. 16,384
74.52
75.23
DISCUSSION AND INTERPRETATION
Generalization issues of large-batch SGD training are not yet very well understood from theoretical perspective. Hence, a profound theoretical study of the generalization local SGD is beyond the scope of this work but we hope the favorable experimental results will trigger future research this direction. In this section we discuss some related work and we argue that local SGD can be seen as way to inject and control stochastic noise to the whole training procedure.
Connecting Local Updates with Stochastic Noise Injection. be written
The update eq. ( can alternatively
W+++ 1 W; 79: w. 79: + + 9.) ww -99. 76,
where 9, == Σ V (w.)). g, = -gg f((,) and e = 9. 9. For most data-sets the noise can be well approximated by zero-mean Gaussian with variance E(w). The variance matrix E(w), following Hoffer et al. (017)) and Hu et al. 2017), for uniform sampling of mini-hatch indices can be approximated as
(ww) ~ +) K(w) = - +
N V((w)V(((w)))
(4)
'The LARS implementation follows the code Btt.luuboooo//IDIIA//pa for mixed precision and distributed training in Pytorch. LARS uses layer-wise learning rate hased on the ratio between ||w]], and fi llz- thus our post-local SGD be simply integrated without extra modification and parameter synchronization.
8

---

Published as a conference paper at ICLR 2020
2017 Zhu al. 2019) interpret eq. 3 as an Suler-Maruyamme approximation to the continuous time Stochastic Differential Equation
Recent works @Jsttzzbski et al. 2018 Li al. 2017; Mandt et al.
(SDE): dw, = gg + /1 N-B R( w (d)(()) where R( R(w)R(w) = ((w) and ((t) ~ (O, I).
BN
When B < N (in eq. 44)) the learning rate and the batch size only appear in the SDE through the ratio p: y ". Jastrzzbski et al. (2018) argue that thus mainly the ratio controls the stochastic noise and training dynamics, and that P positively correlates with wider minima and better generalization matching with recent experimental successes of ImageNet training (Goyal et al. 2017).
This explanation fails in the large batch regime. When the batch size grows too large, the relative magnitude of the stochastic noise decreases as yB-1 * >(N - B)/ BN,, i.e. is not anymore uniquely describing the training dynamics for large batch size and small dataset size when B & N (Jastzzebski et al.) 2018). This could be a reason why the generalization difficulty of large-batch training remains, as clearly illustrated e.g. in Figure Table Figure 3(b) and as well in (Shallue
et al. 2018 Golmant et al. 2018).
The local update step of local SGD is a natural and computation way inject stll-structured stochastic noise to the SGD training dynamics. By using the same ratio 3 as mini-batee SGD, the main difference of the local SGD training dynamics comes from the stochastic noise e during the local update phase (K' times smaller local mini-batch with H local update steps). The will be approximately sampled with the variance matrix K (ww) instead of [(w)) in mini-batch SGD, causing the stochastic noise determined by K and H to increase. This could be one of the reasons for post-local SGD to generalize as good as mini-batch SGD (small mini-batch size) and leading to flatter minima than large-batch SGD in experiments. Similar positive effects of adding well- well-structured stochastic noise to SGD dynamics on non-convex problems have recently also been observed in (Smith
& Le 2018 Chaudhari & Soatto 2018 Zhu al.. 2019: Xing al. 2018 Wen al. 2019
5.1 POST-LOCAL SGD CONVERGES TO FLATTER MINIMA
Figure 4(a) evaluates the spectrum of the Hessian for different local minima. We observe that large- batch SGD tends to get stuck at locations with high Hessian spectrum while post-local SGD tends to prefer low curvature solutions with better generalization error. Figure (bb) ) linearly interpolates two minima obtained by mini-batch SGD and post-local SGD, and Figure 13 (in the Appendix) visualizes
the sharpness of the model trained by different methods. These results give evidence that post-local SGD converges flatter minima than mini- SGD for training ResNet-20 CIFAR-10.
lnaulDomaint sigenvaake of the Hesstan)
100
2.0 mirk saltch SGD
pasi--ocalla SCD with H-18
Top1 Clessfication Accursty
poss local SGD with Hw2
post- local SCD with Ho
part lncal 502 With 11-44
poet-iocal SCD with 1--61
Inguat entropy)
2.5
past local 5GD with 11-1
poet-loze loc--ooclllll SCD with 120
60
2.0
40
1.5
tuinig
-20
1.0
dashed (ies:
1.5
1.00
200
220
2440
260
280
300
-0.50 -0.25 0.00
0.25 0.50
0.25
1.00
1.25
1.50
Epoch
A
(a) The dominant eigenvalue of the Hessian, for model trained from different schemes. It is evalu- ated on the test dataset per epoch, and only the phase related to the post-local SGD strategy is visualized. Mini-batch SGD or post-local local SGD with small H (c.g.. H H=22 2, 4) have noticeably larger dominant eigenvalue.
(b) 1-d linear interpolation between models post-looaa SGD (A and Wmini-bachh saD (A 1), i.e.
i AWmini-buch SGD + (1 posppottbee SGD. The solid lines correspond to evaluate io on the whole training dataset while the dashed lines are on the test dataset. The model parameters only differ from the post-local SGD phase.
Figure 4: Understanding the generalization ability of post-local SGD for large-batch training (ResNet-20 on CIFAR-10 with BK B = 2048). We use fixed B = Bise = 128 with K = 16 GPUs. The detailed experimental setup as well as more visualization of results are available in Appendix C.4

---

Published as a conference paper at ICLR 2020
6 CONCLUSION
We leverage the idea of local SGD for training in distributed and heterogeneous environments. Ours is the first work to extensively study the trade-off between communication efficiency and generalization performance of local SGD, Our local SGD variant, called post-local SGD, not only outperforms large-batch SGD's generalization performance but also matches that of small-batch SGD, In our experiments post-local SGD converged to flatter minima compared to traditional large-batch SGD, which partially explains its improved generalization performance. We also provide extensive experiments with another variant hierarchical local SGD, showing its adaptivity to available system resources. Overall, local SGD comes off a simpler and more efficient algorithm, replacing complex ad-hoc tricks used for current large-batch SGD training.
ACKNOWLEDGEMENTS
The authors thank the anonymous reviewers and Thijs Vogels for their precious comments and feedback. We acknowledge funding from SNSF grant 200021_175796, as well as a Google Focused Research Award.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Fugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, Matthicu Devin, Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint orXiv:6033 1603.04467, 2016.
Dan Alistarh, Christopher De Sa, and Nikola Konstantinov. The convergence of stochastic gradient descent in asynchronous shared memory. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pp. 178, 2018.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Arizzzdennshelli, and Animashree Anandkumar. signSGD: Com- pressed Optimisation Non-Convex Problems. In ICML- International Conference on Machine Learning. 2018.
Avleen S Bijral, Anand Sarwate, and Nathan Srebro. On data dependence distributed stochastic optimization. arXiv preprint arXiv: 11006600303333 04379,2, 2016.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In COMPSTAT'2010 Prrocceeiiiiisseseeiiiii Proceedings of 19th International Conference on Computational Statistics, pp. 177-187, 2010.
Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference, converges limit cycles for deep networks. In 2018 Information Theary and Applications Workshop (ITA), pp. 1-10. IEEE, 2018.
Kai Chen and Qiang Huo. Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise uoddel- filtering. In Acoustics, Speech and Signal Processing (ICASSP), 2016 IEEE International Conference on, pp. 5880-5884, IEEE, 2016.
Ofer Dekel, Ran Gilad-Bachrade Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 135022):155-20,, 2012.
J. Deng, W. Dong, R. Socher, L.-J. Li. K. Li. and L. Fei-Fei. ImageNet: A large-scale hierarchical image database. In CVPR09, 2009.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In ICML- Proceedings of the 34th International Conference on Machine Learning, pp. 1019-1028, 2017.
Noah Golmant, Nikita Vemuri, Zhewei Yao, Vladimir Feinberg, Amir Gholami, Kai Rothauge, Michael W Mahoney, and Joseph Gonzalez. On the computational inefficiency of large batch sizes for stochastic gradient 2018.
descent. arXiv preprint arXiv:
Ian J Goodfellow. Oriol Vinyals, and Andrew M Saxe. Qualitatively characterizing neural network optimization problems. In ICLR- International Conference Leurning Representations, 2015.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training ImageNet in 1 hour. arXiv preprint arXiv: 026777 2017.
10

---

Published as a conference paper at ICLR 2020
William Gropp, Ewing Lusk, and Anthony Skjellum. Using MPI: portable parallel programming with the message-passing interface, volume 1. MIT press, 1999.
Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European Conference on Computer Vision. pp. 630 645. Springer, 2016b.
Sepp Hochreiter and J Schmidhuber. Flat minima. Neural Computation, 9(1):1-4,, 1997.
Flad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In NIPS Advances Neural Information Processing Systems, pp. 1731-1741, 2017.
Wenqing Hu, Chris Junchi Li, Lei Li, Juan-Guo Liu. the diffusion approximation nonconvex stochastic gradient descent, arXiv preprint 1rXiv:1705.077 2017.
Gao Huang. Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinberger. Deep networks with stochastic depth. In European Conference on Computer Vision, pp. 646-661, Springer, 2016.
Gao Huang, Yixuan Li, Gcoff Pleiss, Zhuang Liu, John E Hopcroft, and Kilian Q Weinberger. Snapshot ensembles: Train 1, get for free. In ICLR International Conference on Learning Representations, 2017a.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinherger. Densely connected convolutional networks. In CVPR Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017b.
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, Andrew Gordon Wilson, Averaging weights leads to wider optima and better generalization. In UAI Conference on Uncertainty in Artificial Intelligence, 2018.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Pranceth Netrapalli, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecification. Journal of Machine Learning Research, 18(223): 1-42, 2018.
Stanislaw Jastrzębski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima SGD. International Conference on Artificial Neural Networks 2018, 2018.
Peter Kairouz, H. Brendan McMahan, and ct. al, including Scbastian U. Stich. Advances and open problems in federated learning, arXiv preprint 1912:v111..44999 2019.
Sai Praneeth Karimireddy, Quentin Rebjack, Sehastian U. Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In ICMI Proceedings of the 36th International Conference on Machine Learning, pp. 3252-3322 1261.261.222 2019.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap sharp minima. In ICLR International Conference on Learning Representations, 2017.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape neural nets. In NewrIPS Advances in Neural Information Processing Systems, pp. 6391-6401, 2018.
Mu Li. Scaling distributed machine learning with system and algorithm co-design. PhD thesis, Intel, 2017.
Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J Smola. Efficient mini-batch training for stochastic optimization. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 661 670. ACM, 2014.
Qianxiao Li, Cheng Tai, et al. Stochastic modified equations and adaptive stochastic gradient algorithms. In ICMI. Proceedings of the 34th International Conference Machine Learning, pp. 2101-21 10, 2017.
11

---

Published as a conference paper at ICLR 2020
Ily Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with restarts. In ICLR International Conference on Learning Representations, 2017.
Stephan Mandt, Matthew Hoffman, and David M Blei. Stochastic gradient descent as approximate hayesian inference. The Journal of Machine Learning Research, 18(1):4873-4077, 2017.
James Martens and Ilya Sutskever. Training deep and recurrent networks with hessian-free optimization. In Newrul networks: Tricks of the trade, pp. 479-535. Springer, 2012.
Dominic Masters and Carlo Luschi. Revisiting small batch training for deep neural networks, arXiv preprint TrXiv:180.007612 2018.
Sam McCandlish, Jared Kaplan, Dario Amodci, and OpenAl Dota Team. An empirical model of large-batch training. arXiv preprint 1812::1812.006 2018.
Ryan Medonald, Mehryar Mohri, Nathan Silherman, Dan Walker, and Gideon S. Mann. Efficient large-scale distributed training of conditional maximum entropy models. In NIPS Advances Neural Information Processing Systems 22, pp. 1231-1239. 2009.
Ryan McDonald, Keith Hall, Gideon Mann. Distributed training strategies for structured perceptron. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, HLT 100 pp. 456-464, Association for Computational Linguistics, 2010.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication- efficient learning of deep networks from decentralized data. In AISTATS Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1273-1282, 2017.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In ICLR- International Conference on Learning Representations, 2017.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing Istm language models. In ICLR International Conference on Learning Representations, 2018.
Arvind Neelakantan, Luke Vilnis, Quoc V Le, llya Sutskever, Lukasz Kaiser, Karol Kurach, and James Martens. Adding gradient noise improves learning for very deep networks. arXiv preprint arXiv: 15..:://1..6600 1.0607, 2015.
Adam Paszke, Sam Gross. Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. 2017.
Kumar Kshitij Patel and Aymeric Dieuleveut. Communication trade-off's for synchronized distributed SGD with large step size. arXiv preprint arXiv: 11355, 2019.
Rolf Rabenseifner. Optimization of collective reduction operations. ICCS International Conference on Computational Science, pp. 1 1-9. Springer, 2004.
Herbert Robbins and Sutton Monro. stochastic approximation method. Herbert Robbins Selected Papers, pp. 102-109. Springer, 1985.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh. Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal Computer Vision, 111(3):21-2252 2015.
Frank Seide and Amit Agarwal. CNTK: Microsoft's open- deep-leaming toolkit. In KDD Proceedings of the 22nd ACM SIGKDD International Conferencee Knowledge Discovery and Data Mining, pp. 2135-2135. ACM, 2016.
Christopher Shallue, Jaehoon Lee, Joe Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George Dahl. Measuring the effects of data parallelism on neural network training. arXiv preprint arXiv:181 1.06600 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR International Conference on Learning Representations. 2015.
Samuel L Smith and Quoc V Le. A bayesian perspective on gencralization and stochastic gradient descent. In ICLR International Conference Learning Representations, 2018.
Samuel I. Smith, Picter-Jan Kindermans, Chris Ying, and Quoe Le. Don't decay the learning rate, increase the batch size. In ICL.R International Conference on Learning Representations, 2018.
12

---

Published as a conference paper at ICLR 2020
Sebastian U Stich. Local SGD converges fast and communicates little. In ICLR International Conference on Learning Representations, 2019.
Martin Takáč, Avleen Bijral, Peter Richtárik, and Nathan Srebro. Mini-batch primal and dual methods for SVMs. In ICML Proceedings of the 30th International Conference on Machine Learning, 2013.
Rajeev Thakur, Rolf Rabenseifner, and William Gropp. Optimization of collective communication operations in MPICH. The International Journal of High Performance Computing Applications. 19(1):49 66, 2005.
Jianyu Wang and Gauri Joshi. Adaptive communication strategies achieve the best error-runtime trade-off in local-update SGD. SyxML. 2019.
Yeming Wen, Kevin Luk, Maxime Gazeau, Guodong Zhang, Harris Chan, and Jimmy Ba. Interplay be- tween optimization and generalization stochastic gradient descent with covariance noise. arXiv preprint arXiv:1902.08234 2019.
Chen Xing, Devansh Arpit, Christos Tsirigotis, and Yoshua Bengio. A walk with SGD. arXiv preprint 1EK2vv8802.087000 2018.
Zhewei Yao, Amir Gholami, Qi Lei, Kurt Keutzer, and Michael W Mahoney. Hessian-based analysis large batch training and robustness to adversaries. In NeurIPS Advances in Neural Information Processing Systems, pp. 4949-49999 2018.
Yang You, Igor Gitman, and Boris Ginsburg. Scaling SGD Batch Size to 32k for ImageNet Training. arXiv preprint 133888,70..08888 6, 2017a.
Yang You, Zhao Zhang, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. ImageNet training in 24 minutes. arXiv preprint (409:/77000011111 2017b.
Yang You, Zhao Zhang. Cho-Jui Hsieh, James Demmel, and Kurt Keutzer. Imagenet training in minutes. In Proceedings of the 47th International Conference on Parallel Processing. ACM, 2018.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD for non-convex optimization with faster convergence and less communication. In AAAI - The Thirty-Thiin Third AAAI Conference on Artificial Intelligence, 2019.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC, 2016.
Jian Zhang, Christopher De Sa, Ioannis Mitliagkas, and Christopher Ré. Parallel SGD: When does averaging help? arXiv preprint (/Xivv660600736:000 2016.
X. Zhang, J. Trmal, D. Povey, and S. Khudanpur. Improving deep neural network acoustic models using generalized maxout networks. In ICASSP 2014 - IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 215-219, 2014.
Fan Zhou and Guojing Cong. On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization. In IJCAI-18- Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pp. 2219-3227, 2018.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: behavior escaping from minima and regularization effects. In ICML- Proceedings of the 36th International Conference on Machine Learning 2019.
Martin Zinkevich, Markus Weimer, Alex Smola, and Lihong Li. Parallelized stochastic gradient descent. NIPS Advances in Neural Information Processing Systems 23, 2010.
13

---

Published as a conference paper at ICLR 2020
Supplementary Material
For easier navigation through the paper and the extensive appendix, we include table of contents.
CONTENTS
Introduction
Related Work
3
Lostl SGD and Hierarchical Local SGD
Experimental Results
Superior Scalability of Local SGD over mini-hatch SGD)
(Post)-Local SGD closes the Generalization Gap of Large-batch Training
6
5
Discussion and Interpretation
8
5.1
Post-local SGD converges flatter minima
6
Conclusion
10
Details Deep Learning Experimental Setup
15
Datasel
15
Models and Model Initialization
15
A.3
I
Large Batch Leaming Schemes
16
A.4
Hyperparameter Choices and Training Procedure, over Different Models/Datann
16
A.4.1
CIFAR-1OCCIARR-100
16
A.4.2
ImageNet
17
A.5
System Performance Evaluation
17
Local SGD Training
18
Formal Definition of the Local SGD Algorithm)
18
2
Numerical Illustration of Local SGD on a Convex Prohlem
18
B.3
More Results on Local SGD Training
19
B.3.1
Training CIFAR- 10 via local SGD
19
B.3.2
Training ImageNet via Local SGD
20
B.3.3
Local SGD Scales Larger Batch Sizes than Minc-batch SGD
.............
B.4
Practical Improvement Possibilities for Standard Local SGD Training
B.4.1
Local SGD with Momentum
B.4.2
Warm-up of the Number of Local SGD Steps
23
Post-local SGD Training
26
The Algorithm of Post-local SGD
26
2
The Effectiveness of Turning Post-local SGD after the First Learning Rate Decay
27
The Speedup of Post-local SGD Training CIFAR
27
14

---

Published as a conference paper at ICLR 2020
Understanding the Generalization Post-local SGD
28
Post-local SGD Training on Diverse Tasks
28
C.3.1
Post-local SGD Training CIFAR for Global Mimi-batcl Size Biue 4096
28
C.5.2
Post-local SGD Training on Language Modeling
29
C,5.3
Post-local SGD Training on ImageNet
31
C.5.4
Post-local SGD VS, Other Noise Injection Methods
31
C.5.5
Post-local SGD with Other Compression Schemes
32
D
Hierarchical Local SGD
35
D.I
The Illustration of Hicrarchical Local SGD
35
D.2
The Algorithm Hierarchical Local SGD
36
D33 Hierarchical Local SGD Training
38
D.3.1 The Performance of Hierarchical Local SGD
38
Communication Schemes
39
Discussion and Future Work
40
A DETAILS ON DEEP LEARNING EXPERIMENTAL SETUP
A. DATASET
We the following tasks.
Image classification for CIFAR-10/100 (Krizhessky & Hinton 2009). Each consists of a training set of 50K and a test of 10K color images of 32 32 pixels, well as 10 and 100 target classes respectively. We adopt the standard data augmentation scheme and preprocessing scheme (He) ct al., (2166a] Huang et al. 2016). For preprocessing, we normalize the data using the channel means and standard deviations.
Image classification for ImageNet (Russakovsky et al. 2013). The ILSVRC 2012 classification dataset consists of 1.28 million images for training, and 50K for validation, with 1K target classes.
We use ImageNet-1k k (Deng et al. 2009) and adopt the same data preprocessing and augmentation scheme as in He al. (201 6a b): Simonyan & Zisserman (2015). The network input image is
224 x 224 pixel random crop from augmented images, with per-pixel mean subtracted.
Language Modeling for WikiText-2 (Merity et al.) (017). WikiText-2 is sourced from curated Wikipedia articles. frequently used for machine translation and language modelling, and features vocabulary of over 30, 000 words. Compared to the preprocessed version of Penn Treebank (PTB), WikiText-2 is over times larger.
A.2 MODELS AND MODEL INITIALIZATION
We use ResNet-20 He et al. 201 with CIFAR- 10 as base configuration to understand different properties of (post))local SGD. We then empirically evaluate the large-batch training performance of post-local SGD, for ResNet-20, DensetNet-40-12 (Huang et al. 201 7b) and WideResNet-28- 10 (Zagoruyko& & Komodakis 2016) on CIFAR-10/10 and for LSTM on WikiText-2 (Merity et al.) 2017). Finally, train 5e (He et al. 2016a) on ImageNet investigate the accuracy and scalability of (post-)local SGD training.
For the weight initialization follow Goyal al. (017), , where adopt the initialization introduced by He et al. (2013) for convolutional layers and initialize fully-connected layers by a zero-mean Gaussian distribution with the standard deviation of 0.01.
Table 6 demonstrates the scaling ratio of our mainly used Neural Network architectures. The scaling ratio You al. 2017b) identifies the ratio between computation and communication, wherein
15

---

Published as a conference paper at ICLR 2020
DNN models, the computation is proportional to the number of floating point operations required for processing an input while the communication is proportional to model size (or the number of parameters). Our local SGD training scheme will show more advantages over models with small "computation and communication scaling ratio".
Table 6: Scaling ratio for different models.
Communication
Computation
CompuiatinnConmmunattion
Model
# parameters
# flops per image
scaling ratio
ResNet-20 (CTFAR-10)
0.27 million
0.041 billion
151.85
ResNet-20 (CIFAR-100)
0.27 million
0.041 billion
151.85
ResNet-50 (ImageNet- Ik)
25.00 million
billion
308.00
DenseNett40-12 (CIFAR-10)
1.06 million
0.28 billion
264.15
DenseNet-40-12 (CIFAR-100)
1.10 million
0.28 billion
254.55
WideResNet-28-10 10 (CIFAR-10)
36.48 million
5.24 billion
143.64
WideResNeet28- (CIFAR-100)
36.54 million
5.24 billion
143.40
A.3 LARGE BATCH LEARNING SCHEMES
The work of Goyal er al. (217)) proposes common configurations to tackle large-batch training for the ImageNet dataset. We specifically refer to their crucial techniques w.r.t. learning rate as "large
batch learning schemes" in our main text. For a precise definition, this is formalized by the following two configurations:
Scaling the learning rate: When the mini-batch size is multiplied by k multiply the learning rate by k.
Learning rate gradual warm-up: We gradually ramp up the learning rate from small to large value. In (our) experiments, with a large mini-batch of size kn, start from a learning rate of rj and increment by constant amount at each iteration such that reaches r knn after 5 epochs. More precisely, the incremental step size for each iteration is calculated from ENTTKMT where N is the number of total training samples, i is the number of computing units and the local mini-batch size.
A.4 HYpERPARAMETER CHOICES AND TRAINING PROCEDURE, OVER DIFFERENT MODELS/DATASETTS
A.4.1 CIFAR-IO/CIFAR 100
The experiments follow the common mini-batch SGD training scheme for CIFAR (He et al. [016 b Huang al.) 2017b) and all competing methods access the same total amount of data samples regardless of the number of local steps. The training procedure is terminated when the distributed algorithms have accessed the same number of samples as standalone worker would access. For example, ResNet-20, DensetNet-40-11 12 and Net 10 would access 300, 300 and 250 epochs respectively. The data is partitioned among the GPUs and reshuffled globally every epoch. The local mini-batches are then sampled among the local data available on each GPU, and its size is fixed to Bise 128.
The learning rate scheme follows works (He et al., 2016a Huang et al. 2017b), where drop the initial learning rate by 10 when the model has accessed 50% and 75% of the total number of training samples. The initial learning rates of ResNet-20, DensetNet-40-11 12 and WideResNet-28.. 10 are fine-tuned on single GPU (which are 0.2, 0.2 and 0.1 respectively). and can be scaled by the global mini-batch size when using large-bate batch learning schemes.
In addition to this, we use a Nesterov momentum 0.9 without dampening, which is applied independently each local model. For all architectures, following He et al. (2016a), we do not
16

---

Published as a conference paper at ICLR 2020
apply weight decay the learnable Batch Normalization (BN) coefficients. The weight decay of ResNet-20, DensetNet-40-12 12 and WideResNeet-8- 10 are le-4, le-4 and 5e-4 respectively. For the BN for distributed training again follow Goyal et al. (017) and compute the BN statistics independently for each worker.
Unless mentioned specifically, local SGD uses the exact same optimization scheme as mini-batch SGD.
The procedure of fine-tuning. There is no optimal learning rate scaling rule for large-batch SGD) across different mini-batch sizes, tasks and architectures, revealed the Figure 8 offShaluue et al. (2018). Our tuning procedure is built on the insight of their Figure 8, where we grid-search the optimal learning rate for each mini-batch size, starting from the linearly scaled learning rate. For example, compared to mini-batch size 128, mini-batch size 2048 with default large-bate batch learning schemes need to linearly scale the learning rate by the factor of 16. In order to find out optimal learning rate, we will evaluate linear-spaced grid of five different factors (i.e.. (15, 15.5, 16, 16.5, 17)). If the best performance was ever at one the extremes of the grid, we would try new grid points so that the best performance contained in the middle of the parameters. Please note that this unbounded grid search-ever though initialized at the linearly scaled learning rate-does also cover other suggested scaling heuristies, for instance square root scaling, and finds the best scaling for each scenario.
Note that in our experiments of large-bates batch SGD, either with the default large-batch learning schemes, or tuning/using the optimal learning rate, always warm-up the learning rate for the first 5 epochs.
A.4.2 IMAGENET
ResNet-50 training is limited to 90 passes over the data in total, and the data is disjointly partitioned and is re-shuffled globally every epoch. All competing methods access the same total number of data samples (i.e. gradients) regardless of the number of local steps. We adopt the large-batch learning schemes as in Goyal al. (2117) below. We linearly scale the learning rate based on 0.1 x Bgloh) where 0.1 and 256 is the base learning rate and mini-batch size (Number of GPUs 250
respectively for standard single GPU training. The local mini-batch size is set to 128. For learning rate scaling, we perform gradual warmup for the first epochs, and decay the scaled learning rate by the factor of 10 when local models have access 30, 60, 80 epochs of training samples respectively.
A.5 SYSTEM PERFORMANCE EVALUATION
Figure 5 investigates the increased latency of transmitting data among CPU cores.
Time of aal-reduce per 00 MB
3.00
0.75
0.50
0.25
0.00
of cores
The data transmission cost (in seconds) of an all-reduce operation for 100 MB, over the different number of cores, using PyTorch's 's built-in MPI all-reduce operation. Each evaluation is the average result of 100 data transmissions Kubernetes cluster. The network bandwidth is 10 Gbps, and we use 48 cores per physical machine.
Figure 5:
Table 7 evaluates the time of running forward and backward with different mini-batch size, for training ResNet20 on CIF We can witness that a larger size we use, the better parallelism GPU have.
17

---

Published as a conference paper at ICLR 2020
Table 7: The system performance of running forward and backward pass single GPU, for training ResNet20
on CIFAR-10. The "Ratio" indicates the Tiale of evalnating ehho samples with spccified mini-hateh size The "Time" is in seconds. Time ovaliating 4006 samples with mini-buich sine 4096
Titan XP
Tesla V100
Mini-Batch Size
Time per iteration (over 100 iterations)
Ratio
Time iteration (over 100 iterations)
Ratio
1.490
0.028
64
0.100
1.284
0.030
4.836
128
0.175
1.124
0.034
2.741
256
0.323
1.037
0.043
1.733
512
0.737
1.183
0.073
1.471
1024
1.469
1.179
0.124
1.249
2048
2.698
1.083
0.212
1.068
4096
4.983
0.397
B LOCAL SGD TRAINING
B. FORMAL DEFINITION OF THE LOCAL SGD ALGORITHM
Algorithm Local SGD
input: the initial model (o)
input: training data with labels Z:
input: mini-batch of size Bus per local model: step size 7), and momentum (optional);
input:
input:
number of synchronization steps T;
input: number local steps H;;
input: number of nodes K.
I: synchronize to have the same initial models w == w(o)
2: for all &: 1.... K do in parallel
3: for ....,, do
h I..... 5: sample mini-batch from L/2) (h-1
6: compute the gradient
gi++h11 Bice Li
V ([
7:
update the local model to
w w004 = (1)+
8:
end for
9:
all-reduce aggregation of the gradients
Ai wio
10: get new global (synchronized) model w((411 1) for all K nodes:
w w/o Koo 1 D Aio
11: end for
12:
end for
B.2 NUMERICAL ILLUSTRATION OF LOCAL SGD ON CONVEX PROBLEM
In addition to our deep learning experiments, we first illustrate the convergence properties of local SGD on small scale convex problem. For this, consider logistic regression the w8a datase
18

---

Published as a conference paper at ICLR 2020
(d 300, 49749). We measure the number of iterations reach the target accuracy c 0.005. For each combination H. Bise and K we determine the best learning rate by extensive grid search (ef. paragraph below for the detailed experimental setup). In order to mitigate extraneous effeets on the measured results, we here measure time in discrete units, that is we count the number of stochastic gradient computations and communication rounds, and assume that communication of the weights is 25x x more expensive than a gradient computation, for ease of illustration.
Figure 6(a) shows that different combinations of the parameters (Bre: H) can impact the convergence time for K 16. Here, local SGD with (16, 16) converges more than 2x faster than for (64, 1) and 3x faster than for (256, 1).
Figure 6(b) depicts the speedup when increasing the number of workers K. Local SGD shows the best speedup for H 16 small number of workers, while the advantage gradually diminishes for very large K.
32
wallscok necurrrry (niuiioe
spoodup cloe TO SCOmaaY
46
36 64 236 3024
35 64
128
Ioral mini-hatch size Bi.
Summber of wurkers
(a) Time (relative to best method) to solve a regu- larized logistic regression problem to target accu- racy 0.005 for K = 16 workers for H 1,2, 8, 16 and local mini-batch size Buc- We sim- ulate the network traffic under the assumption that communication is 25x slower than a stochastic gra- dient computation.
(b) Speedup over the number of workers to solve regularized logistic regression problem to target accuracy
0.005, for Bxc 16 and If 1, 2, 8, 16. We simulate the network traf- fie under the assumption that communication 25 slower than a stochastic gradient computation.
Figure 6: Numerical illustration of local SGD on a convex problem.
Experimental Setup for Convex Experiments For the illustrative experiments here study the convergence of local SGD on the logistic regression problem, f(w) = - log(1 11 + exp(-b;a, w)) + A w|l where a, Rd and b, (-1,+1) are the data samples, and regularization parameter = L/n. For each run, we initialize wo = O₂ and measure the number of stochastic gradient evaluations (and communication rounds) until be best of last iterate and weighted average of the iterates reaches the target accuracy f (w.,) - f < c = 0.005, with f == 0.12644331 76216545. report the best result found with any of the following two
For each configuration (K, H, Bioc), stepsizes: 7t := (32, I+I and 7/+ = 32c. Here e is a parameter that can take the values 2' for i E Z. For each stepsize we determine the best parameter c by a grid search, and consider parameter optimal, if parameters (2-2c, --1c, 2c, 22c) yield worse results (i.e. more iterations reach the target accuracy).
cn
B.3 MORE RESULTS ON LOCAL SGD TRAINING
B.3.1 TRAINING CIFAR-10 10 VIA LOCAL SGD
Better communication efficiency, with guaranteed test accuracy. Figure 7 shows that local SGD is significantly more communication efficient while guaranteeing the accuracy and faster convergence speed. In Figure| 7 the local models use a fixed local mini-bated size B = 128 for all updates. All methods run for the same number of total gradient computations. Mini-batch
19

---

Published as a conference paper at ICLR 2020
Top- Traar Tww.GOAAAAALLI KOLLIN
11.5
Tapek Ten Cesst AcCETNC
81.3
47A
(a) Training accuracy vs. number of (b) Training accuracy training (c) Test accuracy number of global synchronization rounds. time.
epochs.
Training CIFAR-10 with ResNet-20 via local SGD (2 x 1-GPU). The local batch size Bixe is fixed 128, and the number of local steps H is varied from 16. All the experiments under the training configurations.
Figure 7:
SGD-the baseline method for comparison-is special case of local SGD with H 1. with full global model synchronization for each local update. We see that local SGD with H as illustrated in Figure ((a] by design does H times less global model synchronizations, alleviating the communication bottleneck while accessing the same number of samples (see vection[]] The impact of local SGD training upon the total training time is
significant for larger number of local steps H (i.e., Figure 7(b). resulting an at least 3 speed-up when comparing mini-batch H to local SGD with H 16. The final training accuracy remains stable across different H values, and there is no difference or negligible difference in test accuracy (Figure 7(c)).
B.3.2 TRAINING IMAGENET VIA LOCAL SGD
Figure shows the effectiveness of scaling local SGD the challenging ImageNet dataset. We limit ResNet-50 training to 90 passes over the data in total, and use the standard training configurations as mentioned in AppendixAA. A.4.2 A.4.2
Top-1 Tedt Clavsificatin Actuney
30
20
10
Mii-sacch 5G0
Local
10030
20000
30000
40000
50000
60000
Figure 8: The performance of local SGD trained ImageNet-Ik 1k with ResNet-50. We evaluate the model performance test dataset after each complete accessing the whole training samples. We apply large- batch learning schemes (Goyal et al. 2017) to the ImageNet for these two methods. For local SGD, the number of local steps is set to H 8.
Moreover, in our ImageNet experiment, the initial phase local SGD training follows the theoretical assumption mentioned in Subsection and thus gradually warm up the number of local steps from to the desired value H during the first few epochs the training. We found that exponentially increasing the number of local steps from 1 by the factor of (until reaching the expected number of local steps) performs well. For example, our ImageNet training uses 8, so the number of local steps for the first three epochs is 1, 2, respectively.
20

---

Published as a conference paper at ICLR 2020
B.3.3 LOCAL SGD SCALES TO LARGER BATCH SIZES THAN MINI-BATCH SGD
The empirical studies (Shallue al. 2018 Golmant al. 2018 reveal the regime of maximal data parallelism across different tasks and models, where the large-batch training would reach the limit and additional parallelism provides no benefit whatsoever.
reach 2%
23
24
21
global miri-baich sizw
Figure 9: The relationship between steps top-1 test accuracy and batch size, of training ResNec-20 CIFAR-10. The "step" equivalent the number of applying gradients. The global mini-batch size is increased by adding more workers K with fixed Biee 128. Results are averaged over three runs, each with fine-tuned learning rate.
contrary to standard large-batch training, local SGD scales to larger batch size and provides additional parallelism upon the limitation of current large butch training. TigureIshows the example of training ResNet-20 on CIFAR- 10 with = 2. which trains and generalizes better in terms of update steps while with reduced communication cost.
B.4 PRACTICAL IMPROVEMENT POSSIBILITIES FOR STANDARD LOCAL SGD TRAINING
We investigate different aspects of the training to address the quality when scaling local SGD to the extreme case, c.g., hybrid momentum scheme, warming up the local SGD or fine-tuning the learning rate. In this section, we briefly present how these strategies are, and how they work in practice where we train ResNet-20 on CI on 16 GPUs.
B.4.1 LOCAL SGD WITH MOMENTUM
Momentum mini-batch SGD widely used in place of vanilla SGD. The distributed mini-batch SGD with vanilla momentum on K training nodes follows
K
(()) = (M +
((+11) = W(( - (e)
K
where V (1)
Σ E
(((w(()
After H updates of mini-batch SGD, have the following updated I))
H m u
H
K
K
m K
m
W((-H) w(0
+
K
(1+H-1)
Coming back the setting of local SGD, we can apply momentum acceleration on each local model. or global level (Chen & Huo 2016). In the remaining part of this section, we analyze the case of applying local momentum and global momentum. For ease of understanding, we assume the learning rate y is the same throughout the // update steps.
Local SGD with Local Momentum. When applying local momentum on the local SGD, i.c., using independent identical momentum acceleration for each local model and only globally aggregating the
21

---

Published as a conference paper at ICLR 2020
gradients at the time (t) + H, have the following local update scheme
"
k (t)
mu 1)
V (t):
w(y) :1 =win ya)))
where (0)
V)i(w()) Consequently, after local steps.
(0)
H-1
0 Σ
w w(t)-
wii 7
Σ m
Σ
m
V
(0-
7=0
Substituting the above equation into eq.
we have the update
H-1
Σ
((++1) (
7
m
(0+#-1
k-
r=1
T=0
T=U
H-1
K
(!() m K
(0)
K
Comparing the mini-batch SGD with local momentum local SGD after H update steps (H global update steps v.s. H local update steps and global update step), we witness that the main difference of these two update schemes is the difference between Σ m U(t-1) and Σ m' - u/ 1)* where mini-batch SGD holds a global (((-1) while each local model of the local SGD has their own "(: 1)- We will soon see the difference between the global momentum of mini-batch SGD and the local momentum of local SGD.
Local SGD with Global Momentum For global momentum local SGD, i.e., more general variant of block momentum (Chen & Huo 2016). we would like to apply the momentum factor only to the accumulated/yynchnonized gradients:
K
1
1
H-1
Σ
(w/) w w(0+H) = ( +
U(x) = (1-1 7 k=1
K
13
7 k=1
K
(0++
([++) (0(() (() (()) (mmu + Σ [- R-1
Σ
1 K
k (0++))
where w (1+ wit -
(1)+1 w w1 (() Note that for local SGD, we consider summing up the gradients from each local update, i.e. the model difference before and after one global synchronization, and then apply the global momentum to the gradients over workers over previous local update steps.
Obviously, there exists significant difference between mini- batch momentum SGD and global momentum local SGD, at least the term > _ m" is cancelled.
Local SGD with Hybrid Momentum. The following equation tries to combine local momentum with global momentum, showing naive implementation.
First of all, based on the local momentum scheme, after H local update steps,
wh
m
m
(0-H-1)
Together with the result from local momentum with the global momentum, we have
(w)) w w()+H)
u(n (-)111 +
k=1
1
Σ
1
(w
w
w
1 ((+1) (()) - -(2(()
((() ?
())
7 k=
K
(90m -7 (1) Σ
H
m"
K
u
11-1)
H-1
Σ
m
K
m
K
H-+
7=0
k
1
T=0
22

---

Published as a conference paper at ICLR 2020
where 1) is the global momentum memory and 1(r-1) is the local momentum memory for each node k.
Table 8: Evaluate local momentum and global momentum for ResNet-20 on CIFAR-10 data via local SGD training (H case) 5 2-GPU Kubernetes cluster. The local mini-batch size is 128 and base batch size (used for learning rate linear scale). Each local model will access disjoint data partition, using standard learning rate scheme as He et al. 2016a).
local momentum
global momentum
test top-1
0.0
0.0
90.57
0.9
0.0
92.41
0.9
0.1
92.22
92.09
0.9
0.3
92.54
0.9
0.4
92.45
0.9
92.19
0.9
0.6
91.32
0.9
18.76
0.9
0.8
14.35
0.9
0.9
12.21
0.9
0.95
10.11
Local SGD with Momentum in Practice. In practice, it possible combine the local momen- tum with global momentum to further improve the model performance. For example, toy example in Table investigates the impact of different momentum schemes on CIFAR-10 trained with ResNet-20 on a 2-GPU cluster, where some factors of global momentum could further slightly improve the final test accuracy.
However, the theoretical understanding of how local momentum and global momentum contribute to the optimization still remains unclear, which further increase the difficulty tuning local SGD over H, K. An efficient way of using local and global momentum remains future work and in this work, we only consider the local momentum.
B.4.2 WARM-UP OF THE NUMBER OF LOCAL SGD STEPS
We use the term "local step warm-up strategy", to refer to specific variant of post-local SGD. More precisely, instead of the two-phase regime which we presented here the used number of local steps H/ will be gradually increased from to the expected number of local steps H. The warm-up strategies investigated here are "linear". "eeaar""""""ppree" "exponential" and "constant".
Please note that the implemented post-local SGD over the whole text only refers to the training scheme that uses frequent communication (i.e., H 1) before the first learning rate decay and then reduces the communication frequency (i.e., H > 1) after the decay.
This section then investigates the trade-off between stochastic noise and the training stability. Also note that the Figure ((a) in the main text has already presented one aspect of the trade-off. So the exploration below mainly focuses on the other aspects and tries to understand how will the scale of the added stochastic noise impact the training stability. Infact, even the model has been stabilized to region with good quality.
Figure 10 and Figure II investigate the potential improvement through using the local step warm-up strategy for the case of training ResNet-20 on CIFAR- 10. Figure [0 evaluates the warm-up strategies of "linear" and "constant" for different H, while the evaluation of "exponential" warm-up strategy is omitted due to its showing similar performance as "linear" warm-up.
However, none of the investigated strategies show convincing performance. Figure I1 further studies how the period of warm-up impacts the training performance. We can witness that even if we increase the warm-up phase 50 epochs where the training curve of mini-batch SGD becomes stabilized, the
23

---

Published as a conference paper at ICLR 2020
large noise introduced by the local SGD will soon degrade the status of training and lead to potential quality loss, as Figure (aa
93
book
12
(a) Applying local step warm-up strategy to
20
3.
Lestoret steert worm comppetto lind wuriin Tyr mottore seppnck The lindl wormin typentieer
100
203
20
352
200
293
ICC
specto
(b) Applying local step warm-up strategy to 16.
Figure 10: Investigate how local step warm-up strategy impacts the performance of training CIFAR-10 with ResNet-20 via local SGD x 2-GPU). The local batch size Boe fixed to 128. The warmup strategies are "linear" and "constant", and the warm-up period used here is equivalent to the number of local steps H.
24

---

Published as a conference paper at ICLR 2020
line frrat siice verve
HRp--10 ioe seruu
loca Hep--d ine sarmu perie-00
Hap-1
103
coecha
opos1a
(a) Evaluate the impact of "constant" local step warm-up for different period of warm-up phase.
laall pragesi lica stao, peroodde robuus heat prap los stoo verre persoide lost perooiitone
50
200
stapes lisl redeettion
testtpp
2.0
local Hap-o inc Hea samuu perie--5
2.5
sep--
parie-
teid de derert wurma senterr mtp-- vermas
103
(b) Evaluate the impact of "linear" local step warm-up for different period of warm-up phase.
bos stremite lack dhas perooide yra
loca sho seneoe traat pwr.ppeeedddde
batt:pp seC./00
hert chmprtt surme wnnii
stpp- sot wamuu partie-io
look Hap--l ina wammus pano0-30
103
250 303
ooccha
opocss
(c) Evaluate the impact of "exponential" local step warm-up for different period of warm-up phase.
Figure 1I: Investigate different warm-up period of the local step warm-up impacts performance training CIFAR-10 with ResNet-20 via local SGD (8 2-GPU). The local batch size Bye is fixed to 128, and the strategies to warm-up the number of local steps H are "linear", "exponential" and "constant".
25

---

Published as a conference paper at ICLR 2020
C POST-LOCAL SGD TRAINING
C.1 THE ALGORITHM OF POST-LOCAL SGD
Algorithm 2 Post-local SGD
input: the initial model w()
input: training data with labels Z;
input: mini-batch of size Bic local model;
input:
step size 7,, and momentum (optional);
input: number synchronization steps T. the first learning rate decay performed at T":
input: number of eventual local steps H1;;
input: number of nodes K.
I: synchronize to have the same initial models w (()
for all 1,.... do parallel
3: for t = I..... do
4:
if < then
5:
(1)
6:
else
(()) H' end if
8:
9:
for h :== I...., H() do
10:
sample a mini- batch from I ---1 compute the gradient
11:
g Biee Lier
V (u
12:
update the local model to
(0+4 = w(1++h-1 - 1og
13:
end for
14:
all-reduce aggregation of the gradients
A wio w W()
15: get new global (synchronized) model w(( for all K nodes:
w wio
TO0 R D Ai
16:
end for
17:
end for
26

---

Published as a conference paper at ICLR 2020
C.2 THE EFFECTIVENESS OF TURNING ON POST-LOCAL SGD AFTER THE FIRST LEARNING RATE DECAY
In Figure 12 we study the sufficiency as well as the necessity of "injecting" more stochastic noise (i.c., using post-local SGD) into the optimization procedure after performing the first learning rate decay. Otherwise, the delayed noise injection (i.c., starting the post-local SGD only from the second learning rate decay) not only introduces more communication cost but also meets the increased risk of converging to sharper minima.
bum the steer after 150 epechs bar on ove slage after 225 specto
$9.0
Taps: Text Elanoifcatton
92.8
92.4
92.
92.0
The number local steps (H)
Figure 12: The effectiveness and necessary of turning the post-local SGD after the first learning rate decay. The example here trains ResNet-20 on CIFAR-10 on GPUs with Bue = =048.
C.3 THE SPEEDUP OF POST-LOCAL SGD TRAINING ON CIFAR
Table 3 and Table TO evaluate the speedup of mini-batch SGD and post-local SGD, over different CNN models, datasets, and training phases.
Table 9: The Speedup of mini-batch SGD and post-local SGD. over different CNN models and datasets. The GPU and 7 corresponds the training K GPUs. We 16 GPUs in total (with Bice 128) 8 2-GPU cluster with 10 Gbps network bandwidth. The experimental setup the same as Table
speedup evaluated by # where To is the training time of the algorithm
CIFAR- 10
CIFAR-100
H=1
H=16
H=32
H=1
H=16
H=32
ResNet-20
9.45
12.24
13.00
8.75
11.05
11.67
DenseNet-40-12
8.31
10.80
11.37
8.04
10.59
10.85
WideResNeet28-11
5.33
7.94
8.19
5.29
7.83
8.14
Table 10:
Speedup of mini-batch SGD and post-local SGD (only consider the phase of performing post-local SGD) over different CNN models and datasets. The speedup is evaluated by TK where T, is the
La.
training time of the algorithm (corresponding to the second phase) GPU and T: corresponds training on GPUs. We use GPUs total (with Bic 128) on an 8 2-GPU cluster with Ghps network handwidth. The experimental setup is the same as Table
CIFAR-10
CIFAR-100
H=1
H=16
H=32
H=1
H=16
H=32
ResNet-20
9.45
17.33
20.80
8.75
15.00
17.50
DenseNet-40-12
8.31
15.43
18.00
8.04
15.50
16.69
WideRessNet28-11
5.33
15.52
17.66
5.29
15.09
17.69
27

---

Published as a conference paper at ICLR 2020
C.4 UNDERSTANDING THE GENERALIZATION OF POST-LOCAL SGD
The Sharpness Visualization Figure visualizes the sharpness of the minima for training ResNet- 20 on CIFAR-10. 10 different random direction vectors used for the filter normalization (Li al. 2018). to ensure the correctness and consistence the sharp visualization.
100
Top-1 Training Classificaioo Accuracy
Tap-1 Test Clessification Accuracy
30
80
25
Cross-entron moss-ertropy
20
-00
-00
0.8
0.6
0.4
0.2
0.0
0.2
0.4
0.6
0.8
0.8
0.6
044
0.2
0.0
0.2
0.4
0.6
0.8
(a) Training dataset.
(b) Test dataset.
Figure 13: Sharpness visualization of the minima for ResNet-20 trained on CIFAR-10. The training is on top of K 16 GPUs and the local batch size is fixed to Bac 128. The dashed lines are standard mini-batch SGD and the solid lines post-local SGD with H/ 16. The sharpness visualization minima is performed via filter normalization (Li al. 2018). The model perturbed
by a shared random direction d, and evaluated by the whole dataset (training or test respectively). The top-1 test accuracy of mini-batch SGD is 92.25, while that of post-local SGD is 92.61. The sharpness of these two minima is consistent over 10 different random directions.
The spectrum of the Hessian for mini-batch SGD and post-local SGD Figure 14 evvlluate the spectrum of the Hessian for the model trained from mini-batch SGD and post-local SGD with different HI, which again demonstrates the fact that large-batch SGD tends stop at points with high Hessian spectrum while post-local SGD could easily generalize to low curvature solution and with better generalization.
1-d linear interpolation between models The 1-d linear interpolation was first used by Goodfellow et al. (2015) and then widely used to study the "sharpness" and "flatness" different minima in several works (Keskar al.) 2017; Dinh al.) 2017] Li al.] 2018). In Figure [5] the model trained by post-local SGD (W loos-llocal SGD) can generalize to flatter minima than that of mini-batch SGD (Wiini batch SGD), either loca SGD is trained from scratch, resumed from the checkpoint of
WD mini-barch SGD (i.e., the checkpoint is one-epoch ahead of the first learning rate decay so as to share
the common weight structure with w mini-bbtch SGD).
C.5 POST-LOCAL. SGD TRAINING ON DIVERSE TASKS
C.5.1 POST-LOCAL SGD TRAINING ON CIFAR- 100 FOR GLOBAL MINI-BATCH SIZE K B 4096
Table presents the severe quality loss (at around 2%) of the fine-tuned large-batch SGD for training three CNNs CIFAR- Our post-local SGD with default hyper-parameter (i.c., the pyper-parameters from small mini-batch size and via large-batch training schemes) can perfectly better the fine-tuned small mini-batch baselines.
close the generalization gap
We further justify the argument of works (Hoffer et al., 2017: Shallue et al., 2018) in Table where we increase the number of training epochs and train longer (from 300 400 and 500) for ResNet-20 on CIFAR- 100. The results below illustrate that increasing the number of training epochs alleviates the optimization difficulty of large-batch training
28

---

Published as a conference paper at ICLR 2020
loqu/Domant eigenvalus otehe Hocsian)
mil catrr 550
porh local 660 with
nirt-attm
por incal SGi
poulc 500
pous 5022 winn
sou-loca
socal 5cD
the22
2.5
1o (Dommntt eigennakos
2.0
2.0
1.5
1.5
1.0
1.0
1.00
200
220
240
260
200
300
380
200
240
260 200
300
Epoch
Epech
(a) The dominant eigenvalue of the Hessian, which is evaluated on the training datasct per epoch. Only the phase related to the strategy of post-local SGD is visualized. Mini-batch SGD post-local SGD with very much H (e.g.. I1 4) have noticeably larger dominant eigenvalue.
(b) The dominant eigenvalue of the Hessian, which evaluated on the test dataset per epoch. Only the phase related to the strategy of post-local SGD is visualized. Mini-batch SGD or post-local SGD with very much If (e.g., noticeably larger dominant eigenvalue.
2, have
Eigennalae the Hession
Ergenalue the itessian
2-
30-1
20-
pool ocal 5CD with red pash ocal 54B with 0
5GD with hwpd
poo.local 5CD wi Hed hocl 50D Un twwd
pach local wir 120
pom-lcesl 5GD u II
port lecal Sto with 120
10
1D
Eigenvatue
Elgencatue
(c) Top 10 eigenvalues of the Hessian, which is evaluated on the training dataset for the hest model of each training scheme. The top eigenval- of the Hessian of the mini- batch SGD clearly present significant different pattern than the post- local SGD counterpart.
(d) Top 10 eigenvalues the Hessian, which is evaluated on the test dataset for the best model of each training scheme. The top eigenvalues of the Hessian of the mini- bat-hatch SGD clearly present sig- nificant different pattern than the post-local SGD counterpart.
Figure 14: The spectrum of the Hessian ResNet-20 trained on CIFAR-10. The training is on top of K 16 GPUs with K Bue 2048. The spectrum is computed using power iteration (Martens & Sutskever 2012 Yao ct al. 2018) with the relative error of le-4. The top-1 test accuracy of mini-batch SGD is 92.57, while that of post-local SGD ranges from 92.33 to 93.07. Current large-batch SGD tends to stop points with considerably "larger" Hessian spectrum, while large-bate) batch trained with post-local SGD generalizes to solution with low curvature and with better generalization.
Table 11:
Top-1 test accuracy of training different CNN models via post-local SGD K 32 GPUs with a large batch size (B = 1096). The reported results are the average three runs. We include the small and large batch baseline, where the models are trained by mini- SGD with mini-batch size 256 and 4096 respectively. The indicates the ine-ttned learning rate.
CIFAR-100
small batch baseline
large batch baseline
post-local SGD (H=8)
post-local SGD (H=16)
ResNet-20
68.84 +0.06
67.34
+0.34
68.38
+0.48
68.30
+0.30
DenseNett40-12
74.85 40.14
73.00
+-0.4
74.50
+0.34
74.96
+-0.00
2ideResNNet28-110
79.78 10.16
77.82 10.65
79.53
10.45
79.80 10.39
C.5.2 POST-LOCAL SGD TRAINING ON LANGUAGE MODELING
We evaluate the effectiveness of post-local SGD for training the language modeling task on WikiText- 2 through LSTM. We borrowed and adapted the general experimental setup of Merity et al. (2018). where
three-layer LSTM with hidden dimension of size 650. The loss will be averaged over all examples and timesteps. The BPTT length is set to 30. We fine-tune the value of gradient clipping (0.4) and the dropout (0.4) is only applied on the output of L.T.. The local mini-batch size B is
29

---

Published as a conference paper at ICLR 2020
100
Top-2 Classificaion Accuracy
loau/Cross entrrpp)
3-
Top- Classffccatin Accuracy
2-
100
2-
60
logulCrocs enttropy
80
40
40
sold Inee:
9ashed linss te5t
1AX
-3.50 -0.25 0.00
0.25
0.50
0.75
1.00
1.25
1.50
-0.50 -0.25
0.00
0.25
0.50
0.75
1.00
1225
1.50
(a) post-loaal is trained with H 16, where the (b) Wpoot-local is trained with 17 32, where the
training resumes from the checkpoint of Wmin-bachtn training resumes from the checkpoint of Wainisbatch sGiD
which is one-epoch ahead the first learning rate decay. which one-epoch ahead of first learning rate decay.
100
Top-1 Classiication Accuracy
100
Top-1 Classifcatioon Accuracy
antropy antsayy
log Cross-aaaa))))))
80
Cooss
40
20
-0.50
-0.25
0.00
0.25
1.00
-0.50 -0.25
1.00 1.25
1.50
(c) post local SCD trained from scratch with 17 16. (d) pust SGD trained from scratch with 32.
Figure 1-d linear interpolation between models w docn sGi and mini--anch SGD, i.c., w maniiibbac sGi + (1 A) Ppott-caal SGD. for different minima of Res.Net-20 trained on CIFAR-10. The training is on top of
K = 16 GPUs and the local batch size is fixed to Bic 128. The solid lines correspond to evaluate tir on the test dataset. The post-local SGD in Figure [5(a] and ( is trained from the checkpoint of Waistacch sGp before performing the first learning decay, while that Figure [3(e] and Figure [S(d] is trained from scratch. The top-1 accuracy mini-batch SGD 92.25, while that of post-local SGD in Figure [5(a) Figure [5(b] Figure [5(c) and Figure [5(d] are 92.61, 92.35. 93.13 and 93.04 respectively.
the whole training dataset while the dashed lines
Table 12: Top-1 test accuracy of large-batch SGD and post-local SGD, for training ResNet-20 CIFAR-100 with Bis 4096. The reported results are the average three runs. We include the small large batch baseline, where the models are trained by mini-batch SGD with 256 and 4096 respectively. The indicates the fine-tuned learning rate. The learning rate will be decayed by 10 when the distributed algorithm has accesses 50% and 75% of the total number of training samples.
of epochs
small batch baseline
large batch baseline
post-local SGD (H=8)
pest-local (H=16)
300
68.80 88.84 20.06
67.34
#0.31
68.38
+:048
68.30 +:030
400
69.07
67.55
+0.21
69.06
+:0.1
69.05 +0.26
500
69.03 20.10
67.42 10.63
69.02 40.38
68.87 +0.27
64 and we train the model for 120 epochs. The learning rate is again decayed at the phase when the training algorithm has accessed 50% and 75% of the total training samples.
Table 13 below demonstrates the effectiveness of post-local SGD for large-batch training on language modeling task (without extra fine-tuning except our baselines). Note that most of the existing work focuses improving the large-batch training issue for computer vision tasks; and it is non-trivial to scale the training of LSTM for language modeling task due to the presence of different hyper- parameters. Here provide proof of concept result in Table to show that our post-local SGD is able to improve upon standard large-batch baseline. The benefits can be further pronounced if we scale to larger batches (as the case of image classification e.g. in Table 11 and Table 12)
30

---

Published as a conference paper at ICLR 2020
Table 13: The perplexity (lower better) of language modeling task WikiText-2. We K 16 and K K Bixe 1024. The reported results are evaluated validation dataset (average three runs). fine-tune the learning rate for mini-batch SGD baselines.
small batch baseline
large batch baseline
large-batch (H=8)
large-batch (H=16)
86.50 +0.35
86.90 +0.49
86.61 +0.30
86.85 +0.13
C.5.3 POST-LOCAL SGD TRAINING IMAGENET
We evaluate the performance of post-local SGD on the challenging ImageNet training. Again we limit ResNet-50 training to 90 passes over the data in total, and use the standard training configurations as mentioned Appendix A.4.2 The post-local SGD begins when performing the first learning rate decay.
can witness that post-local SGD outperforms mini-batch SGD baseline for both of mini-batch size 4096 (76.18 18 and 75.87 respectively) and 8192 (75.65 and 75.64 respectively).
Clasditcaknn
50
Top. Classfiicaion
acal m5-0-4
locs 1bp-11 _ttp-
10
Epoch
Epoch
(a) The performance of post-local SGD training for ImageNet-Ik with K Bu: 4096, terms epoch-to-acccuaacy
(b) The performance of post-local SGD training for ImageNet-Ik with K Bioe 8192, terms of epoch-to-accuracc.
70
80
Test Clacafication
Top 030
30
3
5000 10000 15003 22000 25000 30000 35000 40203
5000
10000
15:000
20000
[4l
(c) The performance of post-local SGD training for ImageNet-Ik with K Buse 4096, in terms of to-acor-cc.r.cy.
(d) The performance of post-local SGD training for ImageNet-ll with K.c. 8192, in terms of -o-cuury.cc
The performance of post-local SGD training for ImageNet-1k. 1k. We evaluate the model performance dataset after each complete accessing the whole training samples. Note that due the resource limitation main experimental platform the paper, these experiments are on top a 4-GPU (V100) Kubernetes cluster with 10 Gbps network bandwidth.
Figure 16:
C.5.4 POST-LOCAL SGD VS. OTHER NOISE INJECTION METHODS
The role of "nnisee" has been actively studied in SGD for non-convex deep learning, from optimization and generalization aspects. Neelakantan et al. 2015) propose to inject isotropic white noise for better
31

---

Published as a conference paper at ICLR 2020
optimization. Zhu et al. (2019): Xing al. (2018) study the "structured" anisotropic noise and find the importance anisotropic noise in SGD for escaping from minima (over isotropic noise) in terms of generalization, Wen et al. 2019) top of these work and try inject noise (sampled from the expensive empirical Fisher matrix) to large-batch SGD.
However, to best knowledge, none of the prior work can provide computation efficient way to inject noise to achieve as good generalization performance as small-batch SGD. Either it is practically unknown injecting the isotropic noise (Neelakantan al. (0015) can alleviate the issue of large-batch training, or it has been empirically justified (Wen et al. 2019) that injecting anisotropic noise from expensive (diagonal) empirical Fisher matrix fails to recover the same performance as the small mini-batch baselines. In this section, we only evaluate the impact of injecting isotropic noise Neelakantan et al. 2015) for large-batch training, and omit the comparison to Wen al. 2019
The idea Neelakantnn
2015) considers add time-dependent Gaussian noise to the gradient at every training step t: V (0) ((((w()) + +NO0 of), where o follows of := [I r)
We follow the general cypper-parametr" search scheme (as mentioned in Section A.4) and fine-tune the 1) and y in the range of {1e 50-5566,, ,e= 56-b) and (0.5, 1, 1.5, 2, 2.5, 3.0] respectively.
Table 14 below compares the post-local SGD to Neelakantan et al. (015). where the noise injection scheme Neelakantan et al. (2015) cannot address the large-batch training issue and could even deteriorate the generalization performance. Note that we also tried to search the hyper-parameters at around the values reported in Neelakantan et al. (2015) for our oftt-off-hh-art CNNs, but it will directly result in the severe quality loss or even divergence.
Table 14: Top-1 test accuracy of adding isotropic noise for large-batch training. We revisit the case of ResNet-20 in Table 3 (2K for CIFAR-10) and Table (4K for CIFAR- 100), where adding isotropic noise in Neelakantan al. 2015)) cannot address the large-batch training difficulty. The indicates a fine-tuned learning rale.
CIFAR-10, K
2K
CIFAR-100, K B 4K
Neelakantan et al. 20155
92.46
+0.27
67.15 +0.26
banc- SGD)
92.48
+0.17
67.38
+0.34
Post-local SGD
93.02
10.24
68.30
#0.48
Compared to another local SGD variant. Recently, Wang & Joshi (2019) proposed to decrease the number of local update steps H during training. However, their scheme inherited from the convergence analysis for optimization (not the generalization for deep learning), and in principle opposite to our interpolation and proposed strategy (i.e. increasing the local update steps during the training).
Their evaluation (ResNet-50 on CIFAR- for K 4 with B = 128) also does not cover the difficult large batch training scenario (Scenario 2), c.g., H 16, K = 16, Bisc 128. For the same CIFAR- 10 task and K=4 as in Wang & Joshi (2019) our smaller ResNet-20 with local SGD can simply reach a better accuracy with less communication (Figure 2)
C.5.5 POST-LOCAL SGD WITH OTHER COMPRESSION SCHEMES
In this subsection, demonstrate that (post- Mocal SGD can be integrated with other compres- sion techniques for better training efficiency (further reduced communication cost) and improved generalization performance (w.rt. the gradient compression methods).
*On the one hand, it is non non-trivial to re- im-imlmmnnt their method due to the the unavailable code. On the other hand, it known that post-local SGD outperforms their expensive noise injection scheme (Wen al. 2019). based the comparison of their Table 1 and our Table 12
'We directly compare to the reported values of Wang & Joshi 2019 as some missing descriptions and hyperparameters prevented us from reproducing the results ourselves. H in their paper forms decreasing
sequence starting with 10 while our local SGD uses constant H 16 during training.
32

---

Published as a conference paper at ICLR 2020
We use sign-based compression scheme (i.e. signSGD (Bernstein et al., 2018) and EF- signSGD (Karimireddy et al. 2019)) for the demonstration. The pseudo code can be found in Algorithm and Algorithm
Post-local SGD with signSGD. We slightly adapt the original signSGD (Bernstein et al. 2018 to fit in the local SGD framework. The local model will be firstly updated by the sign of the local update directions (e.g. gradients, or gradients with weight decay and momentum acceleration), and then be synchronized to reach the global consensus model for the next local updates.
Note that we can almost recover the signSGD in Bernstein al. (2018) from Algorithm when H' = 1, except that we will average over the sign instead of using the majority vote in Bernstein al. (2018). Table [5] illustrates the trivial generalization performance difference of these two schemes, where the post-local SGD in Aggorithm3is able to significantly improve the generalization performance (as Table 4 with further improved communication efficiency.
Algorithm 3 (Post- Local SGD with the compression scheme in signSGD
input: the initial model w(a E R. training data with labels I: mini-mare batch of size Bise local model; step size 7) and momentum (optional); number of synchronization steps T, and the first learning rate decay performed T'; number of eventual local steps H'; number of nodes K.
I: synchronize to have the same initial models woo = W()
2: for all = 1..... K do parallel
3: for = 1 T do
4: if T' then
(1) =
6:
else
7:
(()) H'
8:
end if
for h ..... (1) do
10:
sample mini batch from It (+)+
11:
compute the gradients ((1) +h-1 Bi (c
1. E Ei
V Vi((w
involve weight
decay and momentum.
12:
update the local model win+ = w(0+h-1 siggign() end for
13:
14:
get model difference A w/)) w//+
compress the model difference: s(o) sign( and pin |
15:
16:
get new global (synchronized) model w((+1) for K nodes: w == wi, + I
17:
end for
18:
end for
Table 15: Top-1 test accuracy of training ResNet-20 on CIFAR (KB,, 2018 and K 16).
CIFAR-10
CIFAR- 100
signSGD (average over signs) signSGD (majority vote over signs)
91.61
+0.28
67.15
+0.10
91.61
+0.26
67.21
+0.11
Post-local SGD with EF-signSGD. We extend the single-worker EF-siggSGD algorithm of Karim- ireddy et al. (2019) (i.e. their Algorithm 1) to multiple-workers case by empirically investigating different algorithmic design choices. Our presented Algorithm EF-signSGD for multiple- can reach similar performance as the mini-batch SGD counterpart (both are after the proper hyper-parameteen tuning and under the same experimental setup).
Training schemes, rithm(3) and EF--iggSGDD in Algorithm The training schemes of the signSGD (Bernstein et al.) 2018) (i.e. the one using majority vote) and the signSGD variant in Algorithm 3 are slightly different from the the experimental setup mentioned in A.44 where only fine-tune the initial learning rate in signSGD and Algorithm 3 (when = 1). The optimal learning rate is searched from the grid (0.005, 0.10, 0.15, 0.20) with the general fine-tuning principle mentioned in A.4 No learning rate
tuning procedure for signSGD, signSGD variant in Algo-
33

---

Published as a conference paper at ICLR 2020
Algorithm 4 (Post- Locol SGD with the compression scheme in EF-signSGD
input:
the initial model w*(o) RR; training data with labels Σ; mini-batch of size Bive per local model; step size y,, momentum m (optional); number synchronization steps and first learning rate decay
is performed at T number of eventual local steps H"; number of nodes K. error-compensated memory
e(o) = 0 _
1: synchronize to have the same initial models w = (())-
2: initialize the local error memory Eju) == E(o)-
3: for all l: ...... K do in parallel
4: for 1 I..... . do
if < T' then
6:
((s)
7:
else
8:
(1)) H' end if
for h== l...., HQy
11:
sample mini-bater batch from I (1)
12:
compute the gradient g giti+h-1 Pie Meezy
Viileo (((
can involve weight
decay and momentum.
13:
update the local model m (()++ m(1+h 110g 1.
14:
end for
get model difference A/o) := w(() w w/0+H + e(t)
|
compress model difference: #/)) = sign(4(in) and p(t)
17:
update local memory: e((+1) = eio) - pioppin)
18:
get new global (synchronized) model w((+1) for all K nodes: wit1)) == w/j
stopto
19:
end for
20:
end for
scaling up warming up is required during the training, and the learning rate will be decayed by 10 when accessing 50% and 75% of the total training samples.
The training schemes of the distributed EF-signSGD in Algorithm 4 in general follow the experimental setup mentioned in A.44 We grid search the optimal initial learning rate for Algorithm 4 (for the case of // 1), and gradually warm up the learning rate from relatively small value (0.1) to this found initial learning rate during the first 5 epochs of the training.
Note that in our experiments, weight decay and Nesterov momentum used for the local model updates, for both of Algorithm Algorithm 4 We empirically found these two techniques can significantly improve the training/test performance under fixed training epoch budget.
34

---

Published as a conference paper at ICLR 2020
D HIERARCHICAL LOCAL SGD
The idea of local SGD can be leveraged to the more general setting of training decentralized and heterogeneous systems, which is an increasingly important application area. Such systems have become common in the industry, e.g. with GPUs other accelerators grouped hierarchically within machines, racks or even at the level of several data-centers. Hierarchical system architectures such as in Figure T7 motivate mobile phones form huge heterogeneous networks, where the benefits of efficient distributed and data-local training of machine learning models promises strong benefits in terms of data privacy.
hierarchical extension of local SGD. Moreover, end-user devices such as
Cleate Serish
Concuct
Pig the Rack surtch
fop of Back Switch
Node 1
Node X
Rack 1
Rack 2
Rack N
CPU
GRU
DU
NiC- 201
Figure Illustration a hierarchical network architecture a cluster data center. While GPUs within each node are linked with fast connections (e.g. NVLink), connections between the servers within and between different racks have much lower bandwidth and latency (via top-of-the-raa switches and cluster switches). The hicrarchy can be extended several layers further and further. Finally, edge switches face the external network even lower bandwidth.
D.1 THE ILLUSTRATION OF HIERARCHICAL LOCAL SGD
Real world systems come with different communication bandwidths on several levels. In this scenario, propose to employ local SGD each level of the hierarchy, adapted to each corresponding computation vs communication trade-off. The resulting scheme, hierarchical local SGD, can offer significant benefits in system adaptivity and performance.
Figure 18: An illustration of hierarchical local SGD, for Bxc 2, using H 3 inner local steps and H²* = outer "block" steps. Local parameter updates are depicted in red, whereas block and global synchronization depicted in purple and black respectively.
As the guiding example, we consider compute clusters which typically allocate a large number of GPUs grouped over several machines, and refer to each group GPU-block. Hierarchical local SGD continuously updates the local models on each GPU for number H local update steps before (fast) synchronization within GPU-block. On the outer level, after H such block update steps,
35

---

Published as a conference paper at ICLR 2020
(slower) global synchronization over all GPU-blocks is performed. Figure 18 and Algorithm 5 how the hicrarchical local SGD works, and the complete procedure is formalized below:
depict
R044+H : = who+0
( (
(11++1+11] wic0+11 R.
Σ (wfeen w(m++++)
wie+nn wien k Σ (witr w(n++H1))
(5)
where w +(t)+ indicates the model after / block update steps and H local update steps, and K, is the number of GPUs on the GPU-block i. The definition of ?[]]] and [(00++0-1 follows a similar scheme.
As the number of devices grows to the thousands (Goyal et al. 2017 You et al. 2017b), the difference between 'within' and 'between' block communication effecincy becomes drastic. Thus, the performance benefits our adaptive scheme compared to flat & large mini-batch SGD will be even more pronounced.
D.2 THE ALGORITHM HIBRARCHICAL LOCAL SGD
36

---

Published as a conference paper at ICLR 2020
Algorithm 5 Hierarchical Local SGD
input: the initial model W[oo
input: training data with labels I;
input: mini-batch of size Buc local model;
input:
step size 7,, and momentum (optional);
input: number synchronization steps I' over nodes:
input: number of local update steps H. and block update steps Hº
input: number of nodes K in total; and nodes K' per GPU-block.
I: synchronize to have the same initial models W[(o) W[(]]
2: for all
...... K do in parallel
= 1.....,7............... do
4: for 1 = L,..,, do
for h == I...,, do 6: sample mini- from I +[+++++--1-- compute the gradient
5:
H
7:
Σ
Buc
8:
update the local model
"in+a+4 == t
Wi0+0+1-1
9:
end for
10:
inner all-reduce aggregation of the gradients
R00 wio00 w(0+4+H-
11:
get new block (synchronized) model w w for K' block nodes:
w/t++++11 == w wis++ M10 K ΣK" ARoH
12:
end for
13:
outer all lll-reduce aggregation the gradients
Aio wion w w
14:
get new global (synchronized) model miu+n for all K nodes:
wi wic+1 wion Moo & Σ Ako
15:
end for
16:
end for
37

---

Published as a conference paper at ICLR 2020
D.3 HIERARCHICAL LOCAL SGD TRAINING
Now we move to our proposed training scheme for distributed heterogeneous systems. In our experimental setup, we try mimic the real world setting where several compute devices such as GPUs are grouped over different servers, and where network bandwidth (e.g. Ethernet) limits the communication of updates of large models. The investigation of hierarchical local SGD again trains ResNet-20 on CIFAR-10 10 and follows the same training procedure as local SGD where we re-formulate below.
The experiments follow the common mini-batch SGD training scheme for CIFAR (He et al. 2016a b) and all competing methods access the same total amount data samples regardless the number of local steps or block steps. More precisely, the training procedure is terminated when the distributed algorithms have accessed the same number of samples as a standalone worker would access in 300 epochs. The data is partitioned among the GPUs and reshuffled globally every epoch. The local mini-batches are then sampled among the local data available on each GPU. The learning rate scheme is the same in He et al. (2016a), where the initial learning rate starts from 0.1 and is divided by 10 when the model has accessed 50% and 75% of the total number of training samples. In addition to this, the momentum parameter set to 0.9 without dampening and applied independently each local model.
D.3.1 THE PERFORMANCE OF HIERARCHICAL LOCAL SGD.
Table 16:
Training CIFAR-10 with ResNet-220 via local SGD on 8 x 2-GPU cluster. The local batch size Buc is fixed to 128 with H7 1, and we scale the number of local steps /f from to 1024. The reported training times the average of three and all the experiments are under the same training configurations for the equivalent 300 epochs, without specific tuming.
H
8
16
32
64
128
256
512
1024
Training Time (minutes)
20.07 13.95 10.48
9.20
8.57
8.32
9.22
9.23
9.50
10.30
10.65
Training time vs. local number of steps. Table 16 shows the performance of local SGD in terms of training time. The communication traffic comes from the global synchronization over 8 nodes, each having 2 GPUs. We can witness that increasing the number of local steps over the "datacenter" scenario cannot infinitely improve the communication performance, or would even reduce the communication benefits brought by large number of local steps. Hierarchical local SGD with inner node synchronization reduces the difficulty of synchronizing over the complex heterogeneous environment, and hence enhances the overall system performance of the synchronization. The benefits are further pronounced when scaling up the cluster size.
125.
1252
350
A5A
KAA
875
815
00
93%
Afrcc
150 A71l
Trme
Time Bo
(a) Training accuracy vs. time. The (b) Training accuracy vs. time. The (c) Training accuracy vs. time. The number of local steps is H 2. number of local steps is H = 2, with number of local steps is H 2, with 1 second delay for each global syn-50 seconds delay for each global syn- chronization.
chronization.
Figure 19: The performance of hierarchical local SGD trained on CIFAR-10 with ResNet-20 (2 x 2-GPU). Each GPU block of the hierarchical local SGD has 2 GPUs, and we have 2 blacks in total. Each figure fixes the number of local steps but varies the number of block steps from 1 to 32, All the experiments are under the same training configurations without specific tuning.
38

---

Published as a conference paper at ICLR 2020
Hierarchical local SGD shows high tolerance to network delays. Even in small-scale exper- iment of two servers and each with two GPUs, hierarchical local SGD shows its ability to significantly reduce the communication cost by increasing the number of block step HD (for fixed H), with trivial performance degradation. Moreover, hierarchical local SGD with a sufficient number of block steps offers strong robustness to network delays. For example, for fixed H 2, by increasing the number of H², i.c. reducing the number of global synchronizations over all models, we obtain a significant gain in training time as in Figure 19(a) The impact of a network of slower communication is further studied in Figure 19(b) where the training is simulated in realistic scenario and each global communication round comes with an additional delay of second. Surprisingly, even for the global synchronization with straggling workers and severe 50 seconds delay per global communication round, Figure 19(c) demonstrates that a large number of block steps (e.g. H = 16) still manages to fully overcome the communication bottleneck with no/trivial performance damage.
Table The performance of training CIEAR-10 with ResNet-20 hierarchical local SGD on a 16-GPU Kubernetes cluster. We simulate three different types of cluster topology. namely 8 nodes with 2 GPUs/node, 4 nodes with GPUs/node, and 2 nodes with 8 GPUs/node. The configuration of hierarchical local SGD satisfies H1 16. All variants either synchronize within each node or over all GPUs, and the communication cost is estimated by only considering H- 16 model updates during the training (the update could come from different level of the synchronizations). The reported results are the average of three runs and all the experiments are under the same training configurations, training for the equivalent of 300 epochs, without specific tuning.
1,
2, H = 8
H 4, H
H 8, H
H = 16,
Hd 16
4
=
H =
# of sync. over nodes # of sync. within node
1
1
15
7
3
0
Test acc. on x 2-GPU
90.02
90.25
89.95
91.41
+0.28
+0.08
+0.19
+0.23
91.18 #0.02
Test acc. on 4 x 4-GPU
91.65
91.26
91.46
91.91
+0.06
+0.17
+0.24
+0.16
Test acc. on x 8-GPU
92.14
92.05
91.94
91.56
10.10
#0.14
10.09
10.18
Hierarchical local SGD offers improved scaling and better test accuracy. Table 17 compares the mini-batch SGD with hierarchical local SGD for fixed product H-H1 = 16 under different network topologies, with the same training procedure. We can observe that for a heterogeneous system with a sufficient block size, hierarchical local SGD with a sufficient number of block update steps can further improve the generalization performance of local SGD training. More precisely, when H- H² fixed, hierarchical local SGD with more frequent inner-node synchronizations (H² > 1) outperforms local SGD (H = 1), while still maintaining the benefits of significantly reduced communication by the inner synchronizations within each node. In summary, as witnessed by Table 17 hierarchical local SGD outperforms both local SGD and bati-batch SGD in terms of training speed as well as model performance, especially for the training across nodes where inter-node connection is slow but intra-node communication is more efficient.
E COMMUNICATION SCHEMES
This section evaluates the communication cost in terms of the number of local steps and block steps, and formalizes the whole communication problem below.
Assume computing devices uniformly distributed over K' servers, where each server has K² devices. The hierarchical local SGD training procedure will access N total samples with local mini-batch size B, with H local steps and 1/ block steps.
The MPI communication scheme (Gropp al. 1999) is introduced for communication cost evaluation. More precisely, we use general all-reduce, e.g., recursive halving and doubling algorithu (Thakur et al. 2005 Rabenseifner 2004), for gradient aggregation among K computation devices. For each all-reduce communication, introduces C log, K communication cost, where C' is the message transmission time plus network latency.
39

---

Published as a conference paper at ICLR 2020
The communication cost under our hierarchical local SGD setting is mainly determined by the number of local steps and block steps. The T H local mini-batch, and it only performs global gradients aggregation of K local models after H² block updates. Thus, the total number of synchronizations among compute devices reduced to
K models within each server synchronize the gradients for every
[ KBB.HH 1, and we can formulate the overall communication cost C as:
N Č KB-H -
N KB-HH 1) C K' l'log I
N K + KB C2 C2log K K²
(6)
where C1 is the single message passing cost for compute devices within the same server, C2 is the cost of that across servers, and obviously C₁ & C2- We can easily witness that the number of block steps 11'h is more deterministic in terms of communication reduction than local step H. Empirical evaluations can be found in Section D.3
Also, note that our hierarchical local SGD is orthogonal to the implementation of gradient aggrega- tion (Goyal al., 2017) optimized for the hardware, but focusing on overcoming the aggregation cost of more general distributed scenarios, and can easily be integrated with any optimized all-reduce implementation.
F DISCUSSION AND FUTURE WORK
Data distribution patterns. In our experiments, the dataset globally shuffled once per epoch and each local worker only accesses a disjoint part of the training data. Removing shuffling altogether, and instead keeping the disjoint data parts completely local during training might be envisioned for extremely large datasets which can not be shared, or also in federated scenario where data locality a must for privacy reasons. This scenario is not covered by the current theoretical understanding of local SGD, but will be interesting to investigate theoretically and practically.
Better learning rate scheduler for local SGD. We have shown in our experiments that local SGD delivers consistent and significant improvements over the state-of-the-an performance of mini-batch SGD. For ImageNet. we simply applied the same configuration of "large-batch learning schemes" by Goyal et al. (017)) However, this set of schemes was specifically developed and tuned for mini-batch SGD only, not for local SGD. For example, scaling the learning rate w.r.t. the global mini-batch size ignores the frequent local updates where each local model only accesses local mini- batches for most of the time. Therefore, it is expected that specifically deriving and tuning learning rate scheduler for local SGD would lead to even more drastic improvements over mini-batch SGD, especially on larger tasks such as ImageNet.
Adaptive local SGD. As local SGD achieves better generalization than current mini-batch SGD approaches, interesting question is if the number of local steps H could be chosen adaptively, i.c. change during the training phase. This could potentially eliminate or at least simplify complex learning rate schedules. Furthermore, recent works (Loshchilov & Hutter 2017 Huang et al. 201 7a) leverage cyclic learning rate schedules either improving the general performance of deep neural network training, or using an ensemble multiple neural networks no additional training cost. Adaptive local SGD could potentially achieve similar goals with reduced training cost.
Hierarchical local SGD design. Hierarchical local SGD provides a simple but efficient training solution for devices over the complex heterogeneous system. However, its performance might be impacted by the cluster topology. For example, the topology of 8 x 2-GPU in Table [7 fails to further improve the performance of local SGD by using more frequent inner node synchronizations. On contrary, sufficiently large size of the GPU block could easily benefit from the block update of hierarchical local SGD, for both communication efficiency and training quality. The design space of hierarchical local SGD for different cluster topologies should be further investigated, c.g., to investigate the two levels of model averaging frequency (within and between blocks) in terms of convergence, and the interplay of different local minima in the case of very large number of local steps. Another interesting line of work, explores heterogenous systems by allowing for different number of local steps different clusters, thus making up for slower machines.
40


Reviews:
[{"review_id": "r1xplIO6YS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a variant of local SGD, post-local SGD, for distributed training of deep neural networks. It targets to mitigate the generalization gap caused by large batch training. The idea is straightforward and easy to understand-- start the training with standard mini-batch SGD and later switch to local SGD. The rationale behind this scheme is that switching to local SGD helps the training converge to flatter minima compared to using large-batch SGD, which correlates with sharper minima, and that helps close the generation gap. Switching to local SGD at the second phase also helps improve communication efficiency by reducing the amortized communication volume. The authors perform empirical studies using ResNet and DenseNet to conclude that post-local SGD outperforms large-batch SGD in terms of generalization performance while also with improved communication efficiency. \n\nStrengths:\n+ The post-local SGD technique is simple yet seems to be useful in practice.\n+ Provide a thorough evaluation of the communication efficiency and generalization performance of local SGD. \n+ Introduce a hierarchical version of post-local SGD to better adapt to the topology of the GPU cluster, which often consists of heterogeneous interconnects.\n\nWeaknesses:\n- The design and experiments are largely empirical without theoretical derivation.\n- It is less clear about the benefit of post-local SGD when applied to ADAM, which is widely used for distributed training of NLP tasks. \n- Scalability improvements over mini-batch SGD are largely done by ignoring other optimization techniques that also reduce the communication volume, such as gradient compression[1], Terngrad[2].\n\nOverall, the post-local SGD proposed by the paper seems to be a promising technique for large-scale distributed training. The motivation and explanation of the work are clear. My major concern is about the generalizability of this work. ResNet50 is not that interesting from a distributed training perspective. It is less clear whether the performance gains are consistent across tasks. The authors are encouraged to report experimental results on distributed training of large LM models.\n\n[1]\"Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training\", Lin et. al., ICLR 2018\n[2]\"Terngrad: Ternary gradients to reduce communication in distributed deep learning\", Wen et. al., NeurIPS 2017", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1gp2D8yqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new distributed computation technique for SGD training of deep neural networks. The proposed method is a modification of the local SGD which updates models distributed to several workers in a parallel way and synchronize the model parameters at every few epochs. The local SGD shows a nice performance but it is not robust against large mini-batch size. The proposed method is called post-local SGD that starts the local SGD after some epochs of standard mini-batch SGD. This modification makes the local SGD robust against the large mini-batch size. The authors conducted thorough experiments to investigate the performance of the proposed method. The experiments reveal that the proposed method gives better performances than the mini-batch SGD and the vanilla local SGD.\n\nPros:\n- As far as I checked, the numerical experiments are strong. They checked several points of view. Several settings of mini-batch sizes and number of workers are compared. For more detailed points, they compared the proposed method for not only the vanilla SGD but also other optimizers such as momentum SGD. Moreover, different choices of timing of starting local SGD (t') are compared. \n- The proposed method is simple and easy to implement.\n\nCons:\n- The local SGD itself is not new and has been already proposed (indeed, the authors are also explaining this point in the paper), and theoretical investigation of local SGD has also been well exploited. This method is just a combination of normal mini-batch SGD and local SGD. In that sense, there are not a so much eye-opening idea in the proposed method.\n- SGLD interpretation is instructive, but it does not explain why the \"post\"-local SGD outperforms the local SGD. We can intuitively guess why post-local SGD is better but it is not a rigorous theory. \n- The post local SGD algorithm has more freedom than existing method, which results in more tuning parameters. There are parameters such as the batch-size before and after switching, the number of workers, the timing of switching and so on. It could be disadvantage of the proposed method.\n\nMinor comment:\n- Please give the precise meaning of the dominant eigenvalue.\n- I think the setting that the data are distributed to all workers is acceptable. It is also an interesting setting from the HPC point of view (on the other hand, it would be less interesting in terms of federated learning).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lcegDaKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a variant of local SGD: post-local SGD, which improves the generalization performance compared to large-batch SGD. This paper also empirically studies the trade-off between communication efficiency and performance. Additionally, this paper proposes hierarchical local SGD. The paper is well-written, the experiments show good performance.\n\nHowever, there are several weakness in this paper:\n\n1. The post-local SGD is a simple extension of local SGD. Roughly speaking, post-local SGD uses fully synchronous SGD to warm up local SGD. The novelty of this algorithm is limited.\n\n2. The main statement that post-local SGD improves the generalization performance, is only supported by empirical results. No theoretical analysis is provided. Thus, the contribution of this paper is limited.\n\n3. In this paper, it is reported that in some experiments, local SGD significantly outperforms mini-batch SGD. As shown in Figure 3, when the number of workers is large enough, mini-batch SGD has extremely bad performance. However, such bad result is potentially caused by a bad choice of learning rates. In this paper, the authors use \"linearly scaling the learning rate w.r.t. the global mini-batch size\". However, some recent papers also suggest using square root scaling instead of linear scaling [1]. I think the mini-batch SGD fails simply because the learning rates are too large. However, the authors claim that the learning rates for mini-batch SGD are fine-tuned (in Figure 3), which makes the empirical results questionable.\n\n\n-----------\nReferences\n\n[1] You, Yang, et al. \"Large batch optimization for deep learning: Training bert in 76 minutes.\" arXiv preprint arXiv:1904.00962 (2019).\n\n===================\nUpdate after author's feedback:\n\nI do not have strong reasons to doubt the empirical results after reading the author's feedback, so I increase the score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a simple modification of local SGD for parallel training, starting with standard SGD and then switching to local SGD. The resulting method provides good results and makes a practical contribution. Please carefully account for reviewer comments in future revisions.
Decision: Accept (Poster)