SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
Authors: Jianyu Wang
Vinayak Tantia
Nicolas Ballas
Michael Rabbat
Venue:  (2020)
Keywords: distributed optimization
decentralized training methods
communication-efficient distributed training with momentum
large-scale parallel SGD

Abstract: Distributed optimization is essential for training large models on large datasets. Multiple approaches have been proposed to reduce the communication overhead in distributed training, such as synchronizing only after performing multiple local SGD steps, and decentralized methods (e.g., using gossip algorithms) to decouple communications among workers. Although these methods run faster than AllReduce-based methods, which use blocking communication before every update, the resulting models may be less accurate after the same number of updates. Inspired by the BMUF method of Chen & Huo (2016), we propose a slow momentum (SlowMo) framework, where workers periodically synchronize and perform a momentum update, after multiple iterations of a base optimization algorithm. Experiments on image classification and machine translation tasks demonstrate that SlowMo consistently yields improvements in optimization and generalization performance relative to the base optimizer, even when the additional overhead is amortized over many updates so that the SlowMo runtime is on par with that of the base optimizer. We provide theoretical convergence guarantees showing that SlowMo converges to a stationary point of smooth non-convex losses. Since BMUF can be expressed through the SlowMo framework, our results also correspond to the first theoretical convergence guarantees for BMUF.

Published as a conference paper at ICLR 2020
SLowMo: IMPROVING COMMUNICATION-FFFIIINN DISTRIBUTED SGD WITH SLOW MOMENTUM
Jianyu Wang"
Department of Electrical and Computer Engineering Carnegie Mellon University Pinsburgh, PA 15213, USA jianyuw16and andrew.wwwww......... cmu. edu
Vinayak Tantia, Nicolas Ballas Michael Rabbat Facebook AT Research Montreal, Canada {tantia, ballasn, mikerabbatJofb.com
ABSTRACT
Distributed optimization is essential for training large models on large datasets. Multiple approaches have been proposed to reduce the communication overhead in distributed training, such as synchronizing only after performing multiple lo- cal SGD steps, and decentralized methods (e.g., using gossip algorithms) to de- couple communications among workers. Although these methods run faster than ALLREDUCE-based methods, which use blocking communication before every update, the resulting models may be less accurate after the same number of up- dates. Inspired by the BMUF method of (hen & Huo (2016), propose slow momentum (SLOW Mo) framework, where workers periodically synchronize and perform momentum update, after multiple iterations of base optimization algo- rithm. Experiments on image classification and machine translation tasks demon- strate that SLOW Mo consistently yields improvements in optimization and gen- eralization performance relative to the base optimizer, even when the additional overhead is amortized over many updates so that the SLOWMe Mo runtime on par with that of the base optimizer. We provide theoretical convergence guarantees showing that SLOWMO converges to a stationary point of smooth non-convex losses. Since BMUF can be expressed through the SL framework, our results also correspond to the first theoretical convergence guarantees for BMUF.
INTRODUCTION
Distributed optimization (Chen et al., 2016 Goyal et al. (2017) is essential for training large models on large datasets (Radford et al.J 2019; Liu et al.] 2019; Mahajan et al., 2018b). Currently, the most widely-used approaches have workers compute small mini-batch gradients locally, in parallel, and then aggregate these using a blocking communication primitive, ALLREDUCE, before taking optimizer step. Communication overhead is major issue limiting the scaling of this approach, since ALLREDUCE must complete before every step and blocking communications are sensitive to stragglers (Dutta et al., 2018; Ferdinand et al. 2019).
Multiple complementary approaches have recently been investigated to reduce or hide communi- cation overhead. Decentralized training (Jiang al. 2017 Lian et al., 2017): 2018 Assran al.) 2019) reduces idling due to blocking and stragglers by employing approximate gradient aggregation (e.g., via gossip distributed averaging). Approaches such Local SGD reduce the frequency of communication by having workers perform multiple updates between each round of communi-
cation (McDonald et al. 2010 McMahan al. 2017 Zhou & Cong 2018 Stich 2019 Yu al.
2019b) It is also possible to combine decentralized algorithms with Local SGD (Wang & Joshi
WWrk performed while doing internship Facehook AT Research.

---

Published as a conference paper at ICLR 2020
2018 Wang et al. 2019). These approaches reduce communication overhead while injecting addi- tional noise into the optimization process. Consequently, although they run faster than large mini- batch methods, the resulting models may not achieve the same quality in terms of training loss or generalization accuracy after the same number of iterations.
Momentum is believed to be critical component for training deep networks, and it has been em- pirically demonstrated to improve both optimization and generalization (Sutskever et al.) 2013)) Yet, there no consensus on how combine momentum with communication efficient training algorithms. Momentum is typically incorporated into such approaches by having workers maintain separate buffers which are not synchronized (Lian al. 2017 2018 Assran et al. 2019; | Koloskoval et al. (019a). However, recent work shows that synchromizing the momentum buffer, using periodic AEL.REDUCR or a decentralized method, leads to improvements in accuracy at the cost of dou- bling the communication overhead (Yu et al. 2019a). In block-wise model update filtering (BMUF) nodes perform multiple local optimization steps between communication rounds (similar to local SGD), and they also maintain momentum buffer that is only updated after each communication round (Chen & Huo 2016). Although is now commonly used for training speech models, there no theoretical convergence guarantees for BMUF, and it has not been widely applied to other tasks (e.g., in computer vision or natural language processing).
Inspired by BMUF, we propose general framework called slow momentum (SLOwMO) to improve the accuracy of communication-efiiienn distributed training methods. S0 runs on top of a base algorithm, which could be local SGD decentralized method such stochastic gradient push (SGP) (Nedić & Olshevsky] 2016) Assran et al. 2019). Periodically, after taking some number of base algorithm steps, workers average their parameters using ALLREDUCE and perform mo- mentum update. We demonstrate empirically that SLowMO consistently improves optimization and generalization performance across a variety of base algorithms on image classification and neural machine translation tasks training ResNets on CIFAR- 10 and ImageNet, and training a transformer on WM 16 En-De. Ultimately, SL.WO MO allows us to reap the speedup and scaling performance of coomunication-effiicee distributed methods without sacrificing as much in accuracy.
We also prove theoretical bounds showing that SLOWMO converges to a stationary point of smooth non-convex functions at rate O(1 //TT) after Tr total inner optimization steps and T SLOWMo updates with worker nodes, for a variety of base optimizers. Thus, SLOWWMO is order-wise no Lookahead optimizer
slower than stochastic gradient descent. BMUF and the (hang et al.) 2019) can be expressed through the SLOwMO framework, and so results also translate to the first theoretical convergence guarantees for both of these methods.
THE SLOW MOMENTUM (SLOWMo) FRAMEWORK
S0.0wMo is a framework intended for solving stochastic optimization problems of the form
Σ (e,,D, WERd
min
(1)
using m worker nodes, where the loss function term E; and samples E, from the distribution D; are available at the ith worker. SLOWMo builds on top of a base optimization algorithm and has nested loop structure shown Algorithm Each worker maintains a local copy of the parameters, 2!!6) at worker i after the kth inner step of the fth outer iteration. We assume that all workers are initialized to the same point C0 and the framework also uses a slow momentum buffer u, which is initialized to un = O; although each worker stores a copy of u, locally, these are always synchronized across all nodes, so we omit the superseript simplify the notation.
Within each outer iteration, workers first take T steps of the base optimizer. The base optimizer could be method which involves no communication. such SGD (with without momentum) or a decentralized algorithm which involves some communication, such as stochastic gradient push
(6) (SGP) (Assran et al. 2019). We denote these updates by . o (, where 71 is the
(f)
base optimizer (fast) learning rate and d(() is the update direction used at worker i. If the base
optimizer is SGD then d (xx St,k)- ). For other base optimizers which may additional
(8) ((0)
2

---

Published as a conference paper at ICLR 2020
Algorithm 1: Slow Momentum
Input: Base optimizer with learning rate Yi Inner loop steps T; Slow learning rate o; Slow momentum factor A; Number of worker nodes m. Initial point 20,0 and initial slow momentum buffer 240 = O.
X4,0
for t E {0, (0......., 1 at worker parallel do Resct/maintain/average base optimizer buffers for k E (0, T - } do
Xt,7
(6) Base optimizer step: 11,4+
(1) 1itk
T steps of base optimizer
end
Exact-Average: 2,, = +/ Σ 2i=1 tt5
Figure Illustration of one outer iteration in the slow momentum framework for m = 3 workers.
Update slow momentum: u4+11 Bu, + 7t
(21.0 24.r)
Update outer iterates: 11+1,0 = Lt,0 - am4441
end
local momentum communication, de represents the full update applied at worker this step.
Specific examples of d d for different base optimizers presented in Table C.1 in Appendix
After the base optimizer steps, the workers calculate the average Ft,r Zt,0 m > Ek
using ALLREDUCE (line 6), and then they perform slow momentum update (lines 7-8),
41+1 = 3r, + (x1.0 xt,r)
(2)
I1+1.0 Z1,0 2014111
Although the workers perform this update locally, in parallel, we again omit superscripts because the values of z4,0- Ft,r, and hence u4+1 and 11+1.0 are always identical across all workers, since they follow the ALLREDUCE in line 6. Note that the difference Ft,0 2t,7 is scaled by in ( make the slow momentum buffer invariant to the fast learning rate %/ which may change through training, e.g., when using a learning rate schedule. The outer update in line 8 uses the product ane of the slow and fast learning rates. We use the distinction between slow and fast because the base optimizer step is applied times for each outer update, but this is not intended to imply that one learning rate is necessarily bigger or smaller than the other. We give specific examples learning rates and other hyperparameters used in the experiments in Section below.
A specific SLOWMo algorithm instance is obtained by specifying the base algorithm and the hyper- parameters a, B, y, and We recover number of existing algorithms in this framework. When the base algorithm is SGD, 7 = 1, a = 1, and B E [0, 1). we recover standard large mini-batch SGD 7 and momentum B. When the base algorithm SGD, 1, 1, and 8 0,
with learning we recover Local SGD (McDonald et al. 20100; Stich 2019 Yu et al. [019b]] Wang & Joshi 2018). When the base algorithm does not involve communication among workers, recover BMUF (Chen & Huo 2016).
and
We also obtain interesting novel distributed algorithms. In particular, the experiments in Section demonstrate that using SLowMo with decentralized base algorithm like SGP and reasonable val- ues of 7 consistently leads to improved optimization and generalization performance over the base method alone, without significant increase in runtime. We also observe empirically that, for fixed number of iterations, SLOW Mo combined with SGP is superior SLOWMMo combined with SGD.
The above are all distributed algorithms. Perhaps surprisingly, SLOWMo also encompasses recently-introdueed non-distributed method: if we have m 1 worker with SGD/Adam as base algorithm, (201)), which also has a nested loop structure. Section provides theoretical convergence guar- antees when using the SLowMo framework to minimize smooth non-convex functions, and thus provides the first theoretical convergence guarantees in the literature for BMUF and Lookahead in this setting.
(0, 1]. B 0, and 0, we recover the Lookahead optimizer of Zhang et al.
3

---

Published as a conference paper at ICLR 2020
3 RELATED WORK
The idea of reducing communication overhead by using ALLREDUCE to synchronize parameters after every т > 0 optimizer steps has been considered at least since the work of McDonald et al. 2010), and has been more recently referred to as Local SGD in the literature. Elastic-average SGI) Zhang et al. 2015) uses a related approach, but with a parameter server rather than ALLREDUCE. Lin et al. 200 8 apply Local SGD for distributed training of deep neural networks and propose post- local SGD, which starts by running ALLREDUCE-SOR SGD for some epochs before switching to Local SGD, to improve generalization the cost of additional communication.
Decentralized methods use approximate distributed averaging over a pecr-to-peet topology. rather than AD..REDUCE. This decouples communication but also injects additional noise in the optimiza- tion process since the models at different workers are no longer precisely synchronized. Lian et al.) (017)) present decentralized parallel SGD (D-PSGD), where each worker sends copy of its model to its peers at every iteration, and show it can be faster than parameter-server and ALLREDUCE methods for training deep neural networks. Lian et al. (018) study an asynchronous extension, AD-PSGD. Assran et al. (019)) study stochastic gradient push (SGP), and propose its asynchronous counterpart overlap SGP (OSGP), which achieve further speedup over D-PSGD and AD-PSGD by using less coupled communication. D-PSGD, AD-PSGI, and SGP all have similar theoretical convergence guarantees for smooth non-convex functions, showing a linear scaling relationship be- tween the number of workers and the number of iterations to reach neighborhood of a first-order stationary point. Although the theory for all three methods only covers the case of SGD updates without momentum, implementations use momentum locally at each worker, and workers only av- erage their model parameters (not momentum buffers). Yu et al.] (2019a) prove that linear scaling holds when workers average their parameters and momentum buffers, although this doubles the communication overhead. We refer to this approach as double-averaging below.
Scaman et al. (2019) establish optimal rates of convergence for decentralized optimization meth- ods in the deterministic, convex setting. RRchards & Rebeschini (2019) provide guarantees on the generalization error of non-parametric least-squares regression trained using decentralized gradient descent, showing that there are regimes where one can achieve linear speedup. Neither of these results apply directly to the setting considered in this paper, which focuses on smooth non-convex stochastic optimization, and extending this line of work to non-convex settings is an interesting direction.
Mahajan et al. (018a) propose an approach to distributed learning of linear classifiers (i.e., convex problems) where, in parallel, workers minimize locally formed approximate loss funetions, and then the resulting minimizers are averaged to determine descent direction. Methods which fit in the SLowMo framework, including Local SGD, BMUF (Chen & Huo 2016), and the serial Lookahead optimizer Zhang et al. 2019), can be seen as related to this approach, where the actual loss function at each worker is used rather than an approximate one, and where the descent direction is used in a momentum update rather than (deterministic) line search method.
Note that various approaches to gradient compression have been proposed to reduce the communica- tion overhead for EDUCR and decentralized learning methods (Alistarh al. [007]] Wen al.) 2007 Bernstein et al. 2019| Karimireddy et al., 2019: Koloskova et al.) 2019b; Vogels et al.) (019). However, is presently not clear what extent compression may be beneficial for methods like BMUF, D-PSGD, SGP, and OSGP, which perform averaging on the model parameters rather than on gradients. Combining SLOWMO with compression techniques is an interesting and important direction for future work.
Finally, although momentum methods are known achieve accelerated rates for deterministic opti- mization, currently the theoretical understanding of the benefits of momentum methods (both serial and parallel) limited (Bottou et al., 2018). Loizou & Richtárik] (2017) show that accelerated convergence rates can be achieved when the objective is a quadratic finite sum (i.e., least squares problem) that satisfies an interpolation condition. [Can et al. (2019) show that accelerated rates can also be achieved in the more general setting of smooth, strongly convex objectives, in regime where the noise level is below an explicit threshold, and where the rate of convergence is measured in terms of the I-Wasserstein metric of the distribution of trajectories produced by the momentum method. In the setting of smooth non non-convex functions, Gitman et al.] (2019) establish stability and asymptotic convergence results for the quasi-hyperbolic momentum method (Ma & Yarats 2019.
4

---

Published as a conference paper at ICLR 2020
which can be viewed interpolating between SGD and stochastic momentum method. Extending these results, which focus on the serial setting, to obtain decentralized momentum methods with guaranteed acceleration, is an important direction for future work.
4 EXPERIMENTAL RESULTS
We evaluate the effectiveness of SLOWMO on three datasets: image classification on CIFAR-I0 and ImageNet, and neural machine translation on WMT 16-EnDe. All experiments use NVIDIA DGX-1 servers as worker nodes. Each server contains 8 NVIDIA V100 GPUs and the servers are internetworked via commodity 10 Gbps Ethernet.
On CIFAR-10 (Krizhevsky et al. 2009). we train ResNet-18 (He et al. 2016) using 32 V100 GPUs, located on 32 different worker nodes. The total mini-batch size 4096, and we train for 200 epochs. The learning rate (rr) linearly increases during the first 5 epochs, following the warm-up strategy in Goyal et al. (0177), and then decays by a factor of 10 at epochs 100, 150, and 175. The (fast) learning rate was tuned separately for each base optimizer. All experiments were run 5 times with different random seeds, and the mean metrics are reported.
On ImageNet (Krizhevsky al. 2012 train a ResNet-50 (He et al., 2016) using 32 worker nodes (i.e., 256 GPUs). The total mini-batch size is 8192, and we train for 90 epochs. The learning rate schedule is identical to (Goyal et al. 2017), i.e., linear warm-up in the first 5 epochs and decay by a factor of 10 at epochs 30, 60 and 80.
On WMT 16-En-De, we train a transformer model (Vaswani et al. 2017) using 8 worker nodes (i.e., 64 GPUs). The model is trained with 200k token batches, and we train for 25 epochs. We follow the experimental setting Ott et al. (2018).
For each task, we consider several baselines: (i) Local SGD /Local Adam, where worker nodes independently run single-node SGD (with Nesterov momentum) or Adam and periodically average model parameters; (ii) stochastic gradient push (SGP), the state-of-the-ar synchronous decentralized training method; and (iii) Overlap -GP (OSGP), an asynchronous version of SGP. For each baseline, we examine its performance with and without SLOwMo. Recall that Local SGD and Local Adam with SLoWMo are equivalent BMUF. Local SGD and Local Adam do not involve communica- tion during the inner loop (base optimizer) updates, while SGP and OSGP involve gossiping with one peer at every step. In addition, we also evaluate the performance of TR-SGD/AR--daan the traditional ALLREDUCE implementation of parallel SGD/Adam. Details of all baseline methods are provided in Appendices A and
In general, the hyperparameters of SLOWMo (slow learning rate slow momentum B, and number of inner loop steps 7) need to be tuned for each base optimizer and task. The results in Table all 1, which found to be consistently the best. For Local SGD (with without SLow Mo), we set = 12, and for all other baseline methods we use т = 48. Using T > 12 for Local SGD resulted in significantly worse loss/accuracy ImageNet and WMT 16 En-De.
Note also that all of our baselines (or base optimizers) leverage local momentum scheme, follow- ing previous works (Assran et al., 2019 Koloskova et al. 2019a). When using these methods with SLOWMO, there are different ways to handle the base algorithm local momentum buffers at the be- ginning of each outer loop (line 2 in Algorithm I zeroing, averaging among workers, or maintain- ing the current local value. Appendix B.eadixxB...oo/// provides an empirical comparison. For the experiments reported here, when using SGD with Nesterov momentum as the base algorithm (CIFAR- and Im- agenet) we zero the base algorithm buffer, and when using Adam as the base algorithm (WMT" 16 En-De) we maintain the current value of the Adam buffers. We also tried to apply S1.WwMo on top of AR-SGD base optimizer, but we did not observe any improvement in that setting.
Optimization and Generalization Performance. Table I shows the best training loss and the validation accuracy/BLEU score for each baseline, with and without SLowMo. Using SLOWMo consistently improves both the optimization and generalization performance across all training tasks and baseline algorithms. Figure 2 presents validation error/osss per epoch to give a sense of conver- gence speed. Observe that SGP with SLOWMo substantially improves convergence, compared to SGP alone. We observe similar phenomenon when comparing the training curves; Appendix B
5

---

Published as a conference paper at ICLR 2020
Table I: Comparisons the original distributed optimization algorithms on various training tasks. The best training loss, validation accuracy (for image classification), and BLEU score (for machine translation) are reported. We fix slow learning rate 1. We set the number of local steps T 12 for CIFARIO. 10. For ImageNet and WMT, we use Local SGD. The slow momentum 3 tuned for each case. It typically ranges from 0.4 to 0.8.
48 for SGP and OSGP and
12 for
Training Loss
Validation Acc./BLEU
Datasets
Baseline
Original
w/ SLOwMO
Original
w/ SLOWMo
Local SGD
0.122
0.006
91.73%
93.20%
OSGP
0.011
0.001
93.17%
93.74%
CIFAR-10
SGP
0.002
0.001
93.90%
94.32%
AR-SGD
0.002
92.66%
Local SGD
1.43
1.21
69.94%
73.24%
OSGP
1.03
0.97
74.96%
75.54%
ImageNet
SGP
1.07
1.00
75.15%
75.73%
AR-SGD
0.96
76.00%
Local Adam
2.520
2.480
26.62
27.14
SGP 2.500
2.447
26.92
27.84
WMT" En-De
AR-Adam
2.468
27.17
Communication Cost. Table 2 shows the average training time per iteration ImageNet and 1M For SGP/OSGP, since the additional communication cost due to averaging in line 6 of Algorithm i amortized over the corresponding base algorithm. For methods like Local SGD or Local Adam, which already compute an average every 7 iterations, using Ml (i.e., using 3 > does increase the amount of communication. In other words, using SLOWM Mo on top of the base algorithm improves training/validation accuracy at a negligible additional communication cost.
48 iterations, SLOWMO maintains nearly the same speed as
Effects of r. The most important parammerreettrr in SLOwMO is the number of base optimizer steps before each SLOwMo update, since it influences both the accuracy and the training time. Figure 3 presents the validation accuracy and average iteration time of SGP-SLoWMe for different values 7 on ImageNet and WMT' 16. can be observed that the validation performance does not monotonically increase or decrease with Instead, there is a best value. On both ImageNet and WMT' we find = to be a good tradeoff between speed and accuracy. Moreover, SLOW pretty robust to the choice of т; even if r 96 for ImageNet and 7 192 for WMT' 16, SGP with SLowMo achieves better validation accuracy/loss than SGP alone.
We further investigate the effect of other hyperparameters (the slow learning rate a, slow momentum 33 as well as the different strategies for handling base algorithm buffers Appendix B
100.
Validation Loss (NLL))
Validation Ervar
SGGP
SCGP
SGP
SCP.SLL.
SGP SLLMM
26
SCPN-2 oMo
Validation
m 60
25
50
75
1000
12.5
150
175
200
20
60
50
2.1
20
Number Fpochs
Number of Epochs
Number of Epochs
(a) CIFAR-10, batch size:4k.
(b) ImageNet, batch size:8k.
(c) WMT16 En-De, batch 200k.
Figure 2: Validation curves for various tasks using SGP the base algorithm. We fix 1, 12 for these three plots. Shaded areas in (a) and (b) show the min-max values across all worker nodes. The corresponding training curves presented in Appendix B.2

---

Published as a conference paper at ICLR 2020
Table Average time per iteration with and without SLOwMo. Recall that r 48 for the SGP and OSGP base optimizer and r 12 for Local SGD/Local Adam. In some cases, with SLowMo was faster than without; we hypothesize that this is due to statistical variations timing and background network traffic.
(a) ImageNet, batch size:8k, 32 nodes.
(b) WMT' En-De, batch size:200k, nodes.
Time//teeations (ms)
Baseline
Time/iterations (ms)
Baseline
Original
w/ SLOWMO
Original
w/ SLOWMo
Local SGD
294
282
Local Adam
503
505
OSGP
271
271
SGP
1225
1279
SGP
304
302
AR-Adam
1648
AR-SGD
420
oG (cz 1,8 0.7)
SGP.SL.MM (ar 1.B 0.5)
2.1255
Time per iteration (ms))
314
75.3
Valludti 10 aecuracy
Time ittration (ms)
1340
2. 10000
312
1320
21175
310
1900
2.050
203
75
1250
306
204
20
40
60
90
100
25
75
100
150
175
200
(a) Effect r on ImageNet.
(b) Effect of WMT" 16.
Figure 3: The effects of in S1.owMo. We use SGP the base algorithm. For ImageNet we plot validation accuracy (higher is better), and for WMT' 16 En-De we plot validation NLL (lower better). Increasing 7 amortizes communication cost over more iterations, so the average time per iteration decreases. We hypothesize that moderate values of r have a regularizing effect, improving loss and accuracy, and when 7 is too large performance is degraded because workers' local models drift too far apart.
Comparison with Double-Averaging Momentum. As mentioned in Section 3, Yu et al. (201 (a) propose an alternative momentum scheme, double-averaging, to improve the convergence of Local SGD and D-PSGD. We empirically compare with S1.oWMo in terms of the validation accuracy and average training time per iteration on ImageNet. When the base algorithm is SGP, double averaging achieves 75.54% validation accuracy and takes 402 ms per iteration on average, while SLOWMO-SGP (r 48) reaches 75. 73% validation accuracy while taking 302 ms per iteration on average. Similarly, when the baseline algorithm Local SGD with t 12, double-averaging reaches 72.04% and takes 405 ms per iteration, while SLOW Mo reaches 73. 73.24% and takes only 282 ms per iteration.
THEORETICAL RESULTS
This section provides convergence guarantee for SL.WWMo and shows that it can achieve linear speedup in terms of number of workers. Let (x) = Re,-D, [F;( [F &i] denote the expected objec-
tive function at worker i, and let fxx = Σm f((x). Our analysis conducted for a constant learning rate Tt = under the following standard assumptions.
Assumption (L-smooth). Each local objective function ft(x)) [V) ff(l)) < L| yll- for all x, Rd and (1.2...., m...
L-smooth, i.e.,
Assumption 2 (Bounded variance). There exists finite positive constant o² such that Eg_DD (xx; ff(()) < for all i (1,2....,m),
In order to generalize the analysis to various base algorithms, we define d., = 1 Emh de as the average descent direction across the m workers and make the following assumption.

---

Published as a conference paper at ICLR 2020
Assumption 3. There exists finite positive constant V such that E I|do, Ei, k x I V, where Et, denotes expectation conditioned on all randomness from stochastic gradients up to the k-th step of t-th outer iteration.
As mentioned in Section the analytic form of dı, depends on the choice base algorithm. Therefore, the value of V also changes. For instance, when the base algorithm is Local-SGD, then
dr Di (. c()). follows that
E I|dEA Rt, (11
m² Σ VF
1
VAG
V.
(4)
The above value (V o² /m) can also be applied to other base algorithms, such D-PSGD, SGP, and OSGP. More details are provided in Appendix [
Our main convergence result is stated next. Proofs of all results this section appear in Appendix D
Theorem (General Result). Suppose all worker nodes start from the same initial point 20,0. and T and T so that 0n T-B = V
the initial slow momentum is uo 0. If we set a, 3, V/
and the total iterations TT satisfies TT z mL? (1 (1+ maxxx max 3r(11 (3(1---a) B-a) ArB 1 13), then under Assumptions
11
7 Ito
3 have that:
[V) _ 2ff(zo.))
fin) + MVL VMOT
E
BIV E. [dd,
Elfect of base optimizer
4m V (T 1)
-1-8 (1-8
SmVL2? g
(5)
TP
TT
(1-
Effect of momentum
where fuy inf fxx).
Consistent with AR-SGD. Recall that AR-SGD is equivalent to taking T 1, a = 1, and B and using SGD with learning rate the base optimizer. In this case, all terms the RHS but the first one vanish, V o² o²/m, and 5 is identical to the well-known rate of O(1/VmIT))) for SGD.
Effeet of the base optimizer. The second term in (5) only depends on the base optimizer. It mea- sures the bias between the full batch gradient V f( and the expected update averaged across all workers E,, x For the base optimizers considered in this paper, this term relates to the discrep- ancies among local models and be easily found in previous distributed optimization literature. In particular, under the same assumptions as Theorem one can show that this term vanishes in a rate of 1/(T>) for D-PSGD, SGP, OSGP and Local-SGD: see Appendix
As an example, we provide the convergence analysis for the extreme case of Local SGD, where there communication between nodes during each inner iteration. Intuitively, using other base algo- rithms should only make this term smaller since they involve more communication than Local SGD, Corollary (Convergence of BMUF, i.e., Local SGD with SL.WMMo). Under the same condi- tions as Theorem [ if the inner algorithm is Local SGD and there exists a positive finite constant such that Σ [V - [x)) < <² then
EI =0 ( ( +
MT (T)
(6)
k=0
Linear speedup. Corollary I shows that when the total number steps Tr sufficiently large: 2 m² the convergence rate will dominated by the first term (L/VVmTT). That is, order to achieve error the algorithm requires times less steps when using times more worker nodes. This also recovers the same rate as AR-SGD.
Extension to single-node case. As mentioned in Section 2 when there is only node and the slow momentum factor is 3 = O, the SLowMo--SO is the Lookahead optimizer. One can directly apply Theorem to this special case and get the following corollary.
8

---

Published as a conference paper at ICLR 2020
Corollary (Convergence of Lookahead). Under the same conditions Theorem optimizer AR-SGD and 5 = 0, then one can obtain the following upper bound:
1 if the inner
2 (f( (()
E
fml) + t
40 LT
-
-
--1
2
T7 t=0 k=
VTT
-T
1
+
(8)
VT
T
6 FASTER SLOWMO: REMOVING THE PERIODIC ALLREDUCE
SLowMo helps improve both the optimization and generalization of communication-efin rithms. When the hase optimizer SGP or OSGP, S1.0WMo also comes at the expense of higher communication cost, since it requires performing exact average every iterations. Although the communication cost can be amortized, here we go one step further and propose SGP-SLOW variant, named SGP-SLOW Www.ooo-ooaarragge where we remove the exact average when we perform the SLOWM Mo update, i.e we skip line 6 in Algorithm I We empirically evaluate this variant on the ImageNet and WMT 16 datasets, using a 1, B 0.6 and T 48.
algo-
Surprisingly, we observe that SGP-SLLO.MoO Mo-veveraee achieves similar performances on Imagenet (75.78%, compared 73% for SGP- (GP-SLOwMo) and only slightly degrades the validation NLL on WM (2.11, compared to 201 while preserving the iteration time of the base algorithm (298 ms per iteration on ImageNet and 1227 ms per iteration on WMTT since this variant does not require additional communication. These results suggest that the slow momentum updates, and not the momentum buffer synchronization, contribute the most to the performance gain of SLOwMo. We leave further investigation of SLowMo-SGP-nnn -eooverrge for future work.
CONCLUDING REMARKS
In this paper, we propose a general momentum framework, SLowMo, for communication-efiie efffccient distributed optimization algorithms. SLOWMO can be built on the top of SGD, well decentral- ized methods, such as SGP and (asynchronous) OSGP. On three different deep learning tasks, we empirically show that SLoWMo consistently improves the optimization and generalization perfor- mance of the corresponding baseline algorithm while maintaining a similar level of communication efficiency. Moreover, we establish convergence guarantee for SLOWMo, showing that it con- verges to a stationary point of smooth and non-convex objective functions. Since BMUF (Chen & Huo 2016) can be expressed through So framework (by setting the base optimizer to Lo- cal SGD or Local Adam), to the best of our knowledge, we provide the first convergence guarantee for BMUF in the literature.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Z. Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effcieentt sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, pp. 1709-174 1720, 2007.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael Rabbat. Stochastic gradient push for distributed deep learning. In International Conference Machine Learning, 2019.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD with majority vote communication efficient and fault tolerant. International Conference on Learn- ing Representations, 2019.
Léon Bottou, Frank F. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
In Local SGD/ acal Adam, exact average is also required every iterations, hence in comparison, using S1.owMo does not increase the amount of communication required.

---

Published as a conference paper at ICLR 2020
Bugra Can, Mert Gürbüzbalaban, and Lingjiong Zhu. Accelerated linear convergence of stochastic momentum methods in Wasserstein distances. arXiv preprint 1xxiv:901.0044., 2019.
Jianmin Chen, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting distributed syn- chronous SGD, In International Conference on Learning Representations Workshop Track, 2016.
Kai Chen and Qiang Huo. Scalable training of deep learning machines by incremental block train- ing with intra-block parallel optimization and blockwise model-update filtering. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5880-5884, 2016.
Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, and Priya Nagpurkar. Slow and stale gradients can win the race: Error-runtime trade-off's in distributed SGD. In International Conference on Artificial Intelligence and Statistics, pp. 803-812, 2018.
Nuwan Ferdinand, Haider Al-Lawati, Stark Draper, and Matthew Nokelby, Anytime minibatch: Exploiting stragglers online distributed optimization. In International Conference on Learning Representations, 2019.
Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the role of momentum in stochastic gradient methods. In Advances in Neural Information Processing Systems, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He, Accurate, large minibatch SGD: Training ImageNet in 1 hour. arXiv preprint
2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Zhanhong Jiang, Aditya Balu, Chinmay Hegde, and Soumik Sarkar. Collaborative deep learning in fixed topology networks. In Advances in Neural Information Processing Systems, pp. 59.5590-5555 5914, 2017.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In International Conference on Machine Learning, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint 1xXVv:197.009356 2019a.
Anastasiaa Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning. 2019b.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Learning multiple layers of features from tiny images. CIFAR-IO (Canadian Institute for Advanced Research), 2009. URL http:/ttt/////t cs. torronto.dd/-kriiz//
html
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, pp. 1097-1105, 2012.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 5330-5340, 2017.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In Proceedings of the 35th International Conference on Machine Learning, pp. 3049-3058, 2018.
10

---

Published as a conference paper at ICLR 2020
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't 't use large mini-batches, use local sgd. arXiv preprint 1rXiv:180..02211 2018.
Yinhan Liu, Myle Out, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized BERT pre- training approach. arXiv preprint arXiv: 1692, 2019.
Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods. arXiv preprint arxiv: 2017.
Jerry Ma and Denis Yarats. Quasi- -uass--hyperbolic momentum and Adam for deep learning. In Interna- tional Conference on Learning Representations, 2019.
Dhruv Mahajan, Nikunj Agrawal, S Sathiya Keerthi, Sundararajan Sellamanickam, and Léon Bot- tou. An efficient distributed learning algorithm based on effective local functional approximations. The Journal of Machine Learning Research, 19(1):2942-299 2978, 2018a.
Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens van der Maaten. Exploring the limits of weakly supervised pretraining. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 181- 196, 2018b.
Ryan McDonald, Keith Hall, and Gideon Mann. Distributed training strategies for the structured perceptron. In Human Language Technologies: The 2010 Annual Conference of the North Amer- ican Chapter of the Association for Computational Linguistics, pp. 456-464. Association for Computational Linguisties, 2010.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicttion-effciennt learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282, 2017.
Angelia Nedić and Alex Olshevsky. Stochastic gradient-push for strongly convex functions time-
varying directed graphs. IEEE Trans. Automatic Control, 61(1):39966-394, 2016.
Myle Ott, Grangier David Edunov, Sergey, and Michael Auli. Scaling neural machine translation. In Conference Machine Translation (WMT), 2018.
Adam Paszke, Soumith Chintala, Ronan Collobert, Koray Kavukeuoglu, Clement Farabet, Samy Bengio, lain Melvin, Jason Weston, and Johnny Mariethoz. Pytorch: Tensors and dynamic neural networks in python with strong gpu acceleration, 2017.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multi-task learners. Open AI tech. report, Feb. 2019.
Dominic Richards and Patrick Rebeschini. Optimal statistical rates for decentralised non-parametric regression with linear speed-up. In Advances in Neural Information Processing Systems, 2019.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal convergence rates for convex distributed optimization in networks. Journal of Machine Learning Research, pp. 1-31,
Sebastian U Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International Conference on Machine Learning, pp. 1139-1147, 2013.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, pp. -998-6008, 2017.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems, 2019.
11

---

Published as a conference paper at ICLR 2020
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of communication-efficin SGD algorithms. arXiv preprint arXiv:1808.07570 2018.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. MATCHA: Speeding up decentralized SGD via matching decomposition sampling. arXiv preprint 2019.
09435,
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. TernGrad: Ternrry gradients reduce communication distributed deep learning. Advances Neural Information Processing Systems, pp. 1509-1519, 2007.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient mentum SGD for distributed non-convex optimization. In International Conference on Machine Learning. 2019a.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019b.
Michael R Zhang, James Lucas, Geoffrey Hinton, and Jimmy Ba. Lookahead optimizer: k steps forward, step back. arXiv preprint
2019.
S. Zhang, A. Choromanska, and Y. LeCun. Deep learning with elastic averaged SGD. In Advances in Neural Information Processing Systems, pp. 685-693, 2015.
Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradi- descent algorithm for nonconvex optimization. International Joint Conference Artificial Intelligence, 2018.
12

---

Published as a conference paper at ICLR 2020
A EXPERIMENT DETAILS
A.1 IMPLEMENTATION DETAILS
All methods implemented in PyTorrc 1.0 (Paszke et al. 2017). and experiments CUDA 9.2, CUDNN 7.3, and NCCL 2.2.13.. The ImageNet experiments build on the example from
https: //github....t/// conp///ptorrd//eeaappeee//agaagp ments build on https:: http:p/s//ggttuus..ooo//o/orrrrr
The WMT 16 En-De experi-
For SGP and OSGP we use the
implementations
gradient_puse
A.2 CIFAR-10
For the CIFAR-10 experiments, we train ResNet-18, the implementation of which avail- able at /tctps://qithie http.b/co///aggggg////ooo//..... farcc-hcfarr/aae htt.//aaarbb////////oo/bboooboba http/matter/mot mmodels///// resnet.pp pyy all base algorithms, we use Nesterov momentum parameter of 0.9 and set the weight decay factor as 10-1 For each base algorithm, we tune the (fast) learning rate from (0.01, 0.025, 0.05, 0.1, 0.15] and linearly scale with the number of workers (i.e., 32). We found that, with a total batch size 4096, the best learning rate for AR-SGD is 0.01, for OSGP/SGP is 0.05, and for Local SGD is 0.025.
When applying Mo to these base algorithms, we fix = 1 and r 12 and tune the value of from (0.4, 0.5, 0.6, 0.7, 0.83. It turns out that for OSGP, SGP, and Local SGD, the best values of are all equal to 0.7. More discussion the effects of and / can be found in Appendix B.3
A.3 IMAGENET
For the ImageNet experiments, we use the same learning-rate, schedule, momentum, and weight decay as those suggested in Goyal al. (2017) for SGD. In particular, we use ResNet50 (He et al. (2016)) and train it for 90 epochs with a reference learning-rate of 0. with respect to a 256 sample batch, and scale this linearly with the batch-size. We decay the learning-rate by factor of 10 epochs 30, 60, 80. We use a Nesterov momentum parameter of 0.9. We use weight decay 10-1
When using SLOWMO, we set the slow learning rate a and explore different numbers of inner steps, E {12, 48} and different slow momentum value 3 E {0.5, 0.6, 0.7} when the base optimizer is SGP/OSGP and / 0.7 when the base optimizer LocalSGD. We also explore larger set of values T E {12, 24, 48, 96} in the ablation experiments.
A.4 WMT16 EN-DE
For the WMT16 En-De experiments, follow the experimental protocol described in Out et al. 2018). All experiments are based on the big transformer model (Vaswani et al. (017]) with 6 blocks in the encoder and decoder networks. For these experiments, the base optimizer used is Adam (Kingma & Ba 2015) with betal 0.9, beta2 = 0.98, and 10-8 and trained for 25 epochs. We use the same learning rate schedule as Ott et al. (2018), iee, the learning rate increases linearly for 4, 000 steps to 10 3, after which it is decayed proportionally to the inverse square root of the number steps. We use label smoothing with weight 0. for the uniform prior distribution.
1 For SLOWMO, we explore {0.5, 1.0) as the slow learning rate We observe that gives better performance and therefore report results for a = unless stated otherwise. We explore different numbers of inner steps, т E {12, 48) and different slow momentum value {0.1, 0.3, 0.5, 0.6, 0.7). We also explore a larger set of 7 values, i.c 5 E {12, 24, 48, 96, 192), in the ablation experiments.
13

---

Published as a conference paper at ICLR 2020
Table B.I: Validation NLL (lower is better) with and without SL on WMT' 16 En-De. We observe that Mo improves the validation NLL of SGP and Local Adam.
Validation NLL
Baseline
Original
w/ SLOWMO
Local Adam
2.179
2.137
SGP
2.137
2.106
AR-Adam
2.108
B ADDITIONAL EMPIRICAL RESULTS
B.I VALIDATION NLL ON WMT' 16 EN-DE
We show the Validation NLL on WMT" 16 En-De in Table B.] corresponding to the experiments in Table I We observe that SLOWMo improves the validation NLL (along with BLEU score) of SGP and Local Adam.
B.2 ADDITIONAL TRAINING CURVES
corresponding to the validation curves in Figure 2 can be observed that SLOwMo substantially improves the convergence speed of SGP.
We present the training loss-versus-epochs curves in Figure B.I
AR-SGD SGPP
Training Loss (NLL)
Triinng Loss
SGP SLUMo
STGP
Training Loss
3,0
StoMo
SCIP
SGP SLMMo
20-1
30
2.0
2
50
35
100
125
150
200
1.0
70
20
Number of Epochs
Number Epochs
Number of Epochs
CIFAR-10, batch size:4k.
(b) ImageNet, batch size:8k.
(c) WMT16 En-De, batch 20ze:
Figure B.1: Training curves for various tasks using SGP the base algorithm. We fix 1, 12 for these three plots. Shaded areas in (a) and (b) show the min-max values across all worker nodes. The corresponding validation curves are presented in Figure 2 Note that the training losses in these three figures are evaluated right after the SLowMO update (i.e., Eq.
B.3 EFFECT OF SLOW LEARNING RATE & AND SLOW MOMENTUM FACTOR B
In this section we evaluate the impact of slow learning rate a and slow momentum 33 hyperameters.
In Figure B.2a we perform parameter sweep over a and 3 on CIFAR-10 10 dataset, using OSGP as the base algorithm of S1.owMo. One can observe that when the value of B is fixed, gives the highest validation accuracy; when the value of a fixed, there best value of f ranging from 0.4 to 0.8.
1 always
We further validate this claim on the WMT' 16-En-De dataset. Figure B.2b shows that a = gives lower validation loss than 0.5 for fixed 3 when using SGP Local Adam the base algorithms. When rumning SLowMo-Adam with 3 > 0.5 and a = 1.0, or with 3 > 0.7 and = 0.5, the validation loss was substantially above observations, we stick to a = and fine-tune 3 for SLowMo methods on all training tasks.
and is not plotted here. Motivated by the
14

---

Published as a conference paper at ICLR 2020
Slow learning rate az
03 0.6 0,4 0.
89.47
88.36
86.54
84.17
80.76
94.5
12, average local buffers
Validation (NLL)
2.275
SCW dem)
90.95
01.62
91.32
90.05
89.04
2,250
SGR
2.225
Local/dum,
92.03
92.50
92.32
91.70
91.17
2.200
LocalAdom, 0=10
-00
92.66
02.63
92.80
92.51
92.08
2.155
92.94
03.32
95.05
95.04
92.87
0.8
0.6
0.4
0.2
Slow momentum
Slow momentum B
(b) Effect of and B on WMT 16 SLOwMM-Adam.
(a) Parameter sweep CIFAR-10 training task using OSGP the base algorithm.
Figure B.2: Impact on slow learning rate and slow momentum / on SLowMo.
B.4 BASE OPTIMIZER MOMENTUM BUFFER STRATEGIES
As described in Section the base optimizer may have some associated buffers. SGD with mo- mentum uses a momentum buffer, and Adam tracks estimates of the first and second moments of the gradient. The slow momentum buffer is updated every 7 steps according to Eq 2 There several strategies that can be used to update the base optimizer buffers at the outer iteration level (line 2 in Algorithm D}. Here, we explore three strategies: 1) reset the base optimizer buffers to zero 2) maintain the base optimizer buffers to their current values; 3) average the base optimizer buffers across workers, which requires additional communications, We evaluate the impact of these strategies on ImageNet and WMT' 16 in Table B.2 and Table B.3
On ImageNet, we observe that the different buffer strategies achieve similar training and validation performance, However, the averaging strategy comes at the cost of higher communication overhead (an additional call ALD.RRDDUCE for each buffer averaged). Based on these results, we choose the reset strategy the default in our experiments.
On WMT' 16, we find that the reset buffer strategy underperforms both the maintain and average approaches. When using Adam base optimizer, reseting the second moment to zeros hurts the optimization performance. This is not surprising since is recognized that warming up the Adam buffer is important. Averaging buffers achieves the best results but comes at significantly higher communication cost. We therefore select the maintain strategy as the default one when using Adam.
Table B.2: Effect of different buffer strategies:
ImageNet, batch size:8k, 32 nodes.
Buffer Strategy
Training Loss
Validation Accuracy
Avg parameters + avg buffers
1.06
75.66%
Avg parameters reset buffers
1.00
75.73%
Avg parameters + maintain buffers
0.98
75.78%
Table B.3: Effect of different buffer strategies; WMT' 16 En-De, batch size:200k, 8 nodes.
Buffer Strategy
Training Loss
Validation Loss
Avg parameters + avg buffers
2.438
2.101
Avg parameters reset buffers
5.093
4.732
Avg parameters + maintain buffers
2.447
2.106
B.5 STANDARD DEVIATIONS ON CIFAR-10
Since experiments for CIFAR-10 were ran for 5 times with different random seeds, here we report the standard deviations the validation accuracy in Table B.4 as complementary Table
15

---

Published as a conference paper at ICLR 2020
Table B.4: Validation Accuracy with and without SLowMo on CIFAR-I0. Using SLowMo con- sistently improves the performance of the base algorithms.
Validation Accuracy
Baseline
Original
w/ SLOWMo
Local SGD
91.73 = .4%
93.20 + -2%
OSGP
98.17 .1%
93.74 + .17%
SGP
93.90 = 13%
94.32 = .21%
AR-SGD
92.66 .66
C BASELINE ALGORITHMS
In this section, we give a detailed description of each baseline algorithms used throughout the paper. provide theoretical justification how incorporate the update rules of D-PSGD, SGP and OSGP into the analysis of SLowMo, and also derive the analytic form of V used in Assumption 3 for each method. A summary of the base optimizer update directions given Table C.I
Table C.1: Examples of update directions used by the base optimizer in SLOwMo, where (() and (1() denote the first-order and second-order momentum buffers respectively and Biocal, 31; $2 are the corresponding local momentum factors. When the local momentum buffers are reset at the (i) 0 and / k when the local momentum buffers I, 2 1, and I tr k. maintained, then h/ h (2 1,
beginning of each inner loop, then h20
(i) 0, 11,0
(i) (i)
Base Optimizer
Update directions
d (and possible additional buffers h() m()) +
h (f)
k+1 = k t.k
(5)
SGD
d, Boocal h
r,++1
(6)
F,
St.ke
(()))
(4)
1 = Biocat
+ Fi t.ki
SGP
t.k
d0
(4)
7t jEENNN (t)))) ((,))) [xr - Ve (3rcal 1.++
1 Σ,
(4)
a
1.k
h h = 3, -3 + (1 (1--3,)V/ (1 (
0 1,6+1 B20 + (1 V2)V
(i)
(i)
(6) (
Adam
h1,++1 h (1)
(1)
h,,41/(1
/ (1- -1)), U+
(1)
2 01-
(1)
d0) = -h (1)
/ 0/441
+
h (7)
k+1 h 3, (0)
ik + (1 (1--3))F(( (0 ()
SGP (Adam)
i k+ /20l1) + (1 (=
(1)
(1)
(6)
= h //.41/00 -81), 6(0)
(6)
22b+1 = 1t.4+1/(1 35)
(1)
1
d
7t
v
t.k 7t
(6)
1 Σ
Ejenan() ((()) (2(1) - 0 + e)]
C.1 SGP AND OSGP
Algorithms 2 and 3 present the pseudo-code of SGP and OSGP (Assran et al. 2019). To be con- sistent with the experimental results of the original paper, also use local Nesterov momentum for each worker node. The communication topology among worker nodes is a time-varying di- rected exponential graph Assran et al. (2019). That if all nodes are ordered sequentially, then, according to their rank (0, I,... m 1), each node periodically communicates with peers that are (m 1). hops away. We let each node only send and receive a single message (i.e. communicate with I peer) at each iteration.
2",2!, 2! ......."" .2.
16

---

Published as a conference paper at ICLR 2020
Algorithm 2: Stochastic Gradient Push with Nesterov Momentum (SGP)
Input: learning rate y, momentum factor 3o: Number of worker nodes m. Initial point æy) =g fgg and (f) 1 for all nodes i E {1, m... .
for & E {0, ...., K } at worker in parallel do
Compute mini batch gradients: (= (()
Update local momentum: K+1 Sohk + V (t) c())
x *+4 = kk - 11
(6) k+1 + (2 :5k )
Send (Pk (1) (6) (1.8) (()) to out-neighbors
(1.5)
4.
(1.5) (5) (6J)
())
Receive (P) = Pk
wk
from in-neighbors
Update model parameters:
(1)
EjENt (6.) (1)
#R41
Update de-biased factors: w #+1 = Ejengato
(6,5) (1)
1 x+4
Update de-biased model parameters: 2(1) =x # /
10 end
Algorithm 3: Overlap Stochastic Gradient Push with Nesterov Momentum (OSGP)
Input: learning rate y; momentum factor Bo: Number of worker nodes m. Initial point zo (i) (1) h and o
20
(6) 1 for all nodes {1, 2,...,m). since last 0.
for i E {0, 1,.., K 1} at worker in parallel do
Compute mini batch gradients: (z (0) (0))
(()))
Update local momentum: h 8 + VF(2 ( (1 (6)
15k
#x+ = k 1B k+1 + VF((2 :5k
(8)
(0) (6)
Non-blocking send (pk (1:0) (0) (3:t)
a ktg.Pk Wk
to out-neighbors
#* 2010) (1)
(8)
We+1 = pb
(i)
if count_sincelans (i.)) (1)
then
(1.1) (1) is received from in-neighbors Block until (pk "x+ toPh
10
count
11
else
count count_since_last count since_sinceelast
13
end
if Receive buffer non-empty then
15
for (p
x:
#
(i)
3
:PE
(5.4)
w.()) in the receive buffer do
(1) x x+41 Pk 244
(b.1) (f)
6+1
(6.)
17
1++1 w
+ Pe
w W44
18
end
19
end
Update de- biased model parameters:
(
(8) 2 /
k++
end
Note that although the implementation of SGP is with Nesterov momentum, the theoretical analysis in Assran et al. (2019) only considers the vanilla case where there is no momentum. Accordingly, the update rule can be written matrix form
X k+1 (Xx -FF((Z: P
(9)
17

---

Published as a conference paper at ICLR 2020
where X (ark ....,, Tk (m)) Rdxm stacks all model parameters different nodes and Zn [2k (1)
(1)
E Rdxm denotes the de-biased parameters. Similarly, we define the stochastic ; ).... (m ; gdxm, Moreover, Ps Rmxm is defined as the mixing matrix which conforms to the underlying communication topology.
2k [m]]
gradient matrix as (
If node is one of the in-neighbors of node i, then pli.)) 0 otherwise plfs)) 0. In particular, matrix Ps column-stochastic.
If we multiply vector 1 1/m on both sides of the update rule (9), we have
m
2k+1 = 23
m7 Σ (2 S
7
(10)
where 2i = Xx //m denotes the average model across all worker nodes. Recall that in SLOW we rewrite the updates of the base algorithm the kth steps of the tth outer iteration as
Lt,k+1
Lt,k ?d
(11)
So comparing (10) and (11), we can conclude that de, E²
As conse- quence, have E,,a/dd,dt E (z(() Since mini-batch gradients are independent, it follows that
()
E |d,, Be x1, =F
V 2, (.2 -
(12)
V P. (. [=((f)))))
(13)
m
V.
(14)
Similarly, for OSGP, one can repeat the above procedure again. But the definition of Xx, Zμ and VF(Zz) will change, in order account for the delayed messages. In this case, we still have the update rule Eq. (10). But æ is no longer the averaged model across all nodes. It also involves delayed model parameters. We refer the interested reader to Assran et al. (2019) for futher details.
C.2 D-PSGD
In the case of decentralized parallel SGD (D-PSGD), proposed in Lian al. (017). the update rule quite similar to SGP. However, the communication topology among worker nodes is an undirected graph. Hence, the mixing matrix Pa doubly-stochastic. Each node will exchange the model parameters with its neighbors. The update rule can be written as
X = (X VF(X Ex)) P
(15)
Again, we have that X = k
I
(m))
E Rdxm stacks all model parameters at different nodes
and ((X))) = |V (x 11 (t)
V (x (1), ((0) E d denotes the stochastic gradient
Sk
matrix. By multiplying vector 1 1/m both sides of (15), have
24+1 36
Va 0 c0
(16)
=bb ydk--
(17)
As result, using the same technique (12)-(14), we have V = o² //m for D-PSGD.
C.3
LOCAL SGD
We further present the code of Local SGD in Algorithm 4 and the pseudo-code of double- averaging momentum scheme in Algorithm 5
18

---

(1) Published as a conference paper at ICLR 2020
Algorithm 4: Local SGD with Nesterov Momentum
Input: learning rate y; momentum factor So: Communication period т; Number of worker nodes
m. Initial point zy and hyp Ofor all nodes i E
for k E 10,1,..... K 1] at worker in parallel do
Compute mini-batch gradients: (f R (9) c(0)
Update local momentum: h Soh + (R (0) (
F 2 k 71 (F
(f)
())
(8)
(1) [()
if l: mod then
ALLREDUCE model parameters: I k+1
1 2リ=1 2+7
else
(1) #R41 *
(6)
end
10
end
Algorithm 5: Local SGD with Double-Averaging Nesterov Momentum (Yu al. 2019a)
Input: learning rate y, momentum factor 3o: Communication period r; Number of worker nodes
m. Initial point (5) and hg (5) Ofor all nodes i E (1,2,...,m))
for & E 10, K 1} worker in parallel do
Compute mini batch gradients: (=x (9) (
Update local momentum: h (4)
= h (1)
(Z (1), (
*
#R+ 3x (A)
(6)
(i)
+ VR. :5k c())
k+
le mod 5 then
ALLREDUCE model parameters:
3 #k+1 = 1 th
(t)
j=1
ALLREDUCE momentum buffers:
h
(4)
1 ق1= #+4
k+1
else
(1)
k+1
x k+t
(6)
h
10
k++
11
end
12
end
D PROOFS
D. EQUIVALENT UPDATES
To begin, recall that de, 1
m Em
(1) d and that the local updates
(8) Ei
7d
(18)
for k: = . 1, followed by an averaging step to obtain Ft,- can write the update rule of the base optimizer as
Em T Therefore, we
Ft.r Ft.0
de
(19)
k=
19

---

Published as a conference paper at ICLR 2020
Combining this with and we have
1,+ = 21,0 0r
de,k a7,8ut
(20)
k=0
0r,0
de, (x1.0 2t-1,00)
(21)
k=0
Let yr.o 21,0 + 1- (21.0 Zt- 11-1,0); Vt. Then by rearranging terms we get
07
31+1,0 = Vr,0
d,
(22)
B
R=0
Now, ler further extend the auxiliary sequence all values of k + as follows:
O27
yt Vt.k
d,
(23)
It is easy show that yt 1,+1,0- In the sequel, will analyze the convergence of sequence {yr,) instead of {
D.2 PRELIMINARIES
In the table below, we list all notations used in this paper.
Table D.1: List of notations.
Global learning rate
Global momentum factor
3
learning rate
?
Outer iteration length
T
Total number of outer iterations
T
Total number of steps
K
Liptschiz constant
Number of worker nodes
Throughout the theoretical analysis, will repeatedly use the following facts:
Fact 1: (a, b) = 1 |||| + 1/2 |b| 1 la bll²:
Fact 2: According to Young's 's Inequality, for any 0, we have
(a. b) = 2a
1
|||| 2
|
(24)
2
Fact 3: ||a b/l² S 2|aa| 2 + bb/l:
Fact 4: Suppose [a,)/_ is set of non- scalars and to Jensen's 's Inequality, we have
Then according
b
2
0
bi
< s
Ci
b
2
(25)
1=1
i=
D.3 GENERAL TREATMENT
Since each local objective fi is L-mmooth, the function f 1 Σm fi is also L-smooth. It follows that
a2-21
[f f(H1.)) < 1
an (Vi()))) (d. +
Et,
[|dr,tl]
(26)
2(1 33)
20

---

Published as a conference paper at ICLR 2020
where I denotes conditional expectation over the randommess in the (t, k)-th iteration, condi- tioned on all past random variables. For the first term on the right hand side:
(Vf(ve.)) V fZ Bd (Vf(Z)))) Bi (d,,) -VVf(y))), [x,,)
VS(U)N) - ( + a [[E,,(
2a
(VI(F)))) (c.x))
(27)
1- a ||Er, xdl
V ((((+,)))1
2a
1
VV [
|
f2(
Ee,
(28)
2
2
L
1
11 22,4
2a
2
1
| (
+
| f(),,) Be,((de,]]]
(29)
2
where 27 comes from Fact 4 (24 and > 0 is constant. For simplicity, we directly set a = 0.5.
Eqn. 28 uses Fact 2 (a. b) ||a| |bll }lla bll². Furthermore, according to the
definition of Yr,u, it can be shown that
1 21,1112
a 1
(1
ydu + vr,0
(30)
1-
1=0
k-1
22n²
a
Σ j=0
d
+ + Iz,all
(31)
B
k-1
2,3
227
a
Σ
d
+ (1-18)2 ||01,, 2..1.112
(32)
3
j=
Substituting (32 into 29
follows that
- (VV((u.)) E., (d.,)) < 2 [
- ||Br, (
+ [V - -E,,(dd,,
2,21. (1 (1-1
2 k-1
Σ di
+
32
1t.0 Ft 21-1.0011
(1 - B)3
1=0
(33)
Moreover, for the second term in (26). we have
Ey,4 ||dr,
| ( wll + Ee [lidek E [dd,((
(34)
Then, plugging 33 and
34p into 26).
(f -f( s
Jeff
|| | VV(()))))1
Joff (1
TothL
|
2
2
2
+
2
E,
||dr - E,, (d,,1,
+
Yeff
E,, [dl
2
2
2
k--1
2
22 T.2
2/ 212
(
Σ
dr,j
+
|| Tt. 10
1
3
(1 - --2
1=0
(35)
21

---

Published as a conference paper at ICLR 2020
where "ett (1 - B). Taking the total expectation,
Elf(yc&+1) f(yrk))
Yell E
V
Yea
(2
E Ee [de,
+
Yeft L
|
Be [c,(cdr,))] [d1,
Vell 2
TR,, x
2
(t.
2 (1-
(1-2211-1
2
E
Σ
d
+
2 2om 1,2
B112,1,0 02-1,011
(1 B)2
j=0
Na(1)
(2(1,
(36)
Summing from h: = 0 = 1, we have
B[f(y--10)) - f(y1,00) -E[f(ye.r) f(yr,o)]
(37)
- -
Yeff
E
V (
Yeff
Yeff
E
T de 1
2
2
2
k=
L LTV
Voff
E
| (x -
N2(1,
Na(1),
2
2
k=0
k=
A=0
(38)
where (t, k), N2 k), and (t()) are defined in dividing both side by total iterations K = TT,
36 Summing from 0 T and
ELS(YT,)) - [(y0,0)) K
Yeff
E (..
Teff (1
-ettl.
ΣΣ
E || [d1
2K
2K
1=
A=
Y LV
Yell
T-1
[ - Ee,x [d1.
2
2K
t= 1mma
T T-1T-1
N2 k)
Na(t).
(39)
K
K
t=
K=U
t=
k=
Now, we going further expand the expressions of the last two terms in (39
D.3.1 BOUNDING N2(1,
Using the fact l|a + b112 < 2 [|]a|| + ||b|12 we have
k-1
2
Σ (d.. - Er, (dho))
+2
Σ
E [d.
(40)
1=0
Σ (dr.s BR, (dr
24:
Σ
|
(dr 11?
(41)
0=
22

---

Published as a conference paper at ICLR 2020
where the last inequality comes from Fact 3. Then, taking the total expectation and summing over the t-th outer iteration,
d1
S2E
di,
Begldr,sl)
+2
E
|
[d.,
(42)
k=0
1-1
E
||des - Br, (c 12
+2
Σ
E
(43)
k= 0 j=0
km
22V Σ k + Σ k Σ
E [ 111
(44)
j=0
=T 1)V + (( - 1)
Σ
E E dd,
(45)
k=
where 43
uses the following fact:
E
Σ ( Begldhs))
Σ E |la. B,g (dh
/=0
Σ E (dd, Beglde.l, du, E,,,(de,))
(46)
j 1m5+1
E ||bb.
k-1
Σ
E (dis - Idesl Eeclch, Be,(dd.)])) (47)
j=0 1=/+1
k-1
Σ B (ides - Ee, Idc,s113]
(48)
1=
As result, we end up with the following
(1 (1-3-10 a)
k2( 22n2 1)
EE ||EE, & ( x1l
(49)
a²
k=0
k2) 1. 12 - 1) (1- 31-3-0) a)2
T
TV +
E || E 111
(50)
a²
t=0 k=
ke(t,k) 52n 7(T 1) (1 (1- 8 a)²
a-)
V T-11-1
E | 11
(51)
K 1=
a²
K
(=0 k=
where K = 77 denotes the total steps.
23

---

Published as a conference paper at ICLR 2020
D.3.2
BOUNDING (t(
From the update rule 2p. and (18). we have
11.0 Zt-
1,01
=0 2
d. 1,6 + 814-1
(52)
Σ
d 1,k + Σ
d + Bu
(53)
k=0
r-1
=
Σ
8
Σ
de,k
(54)
<2a2g²
Σ
Σ
(dg,k
A (d)
21
+ 2022?
Bs, [da,.t
(55)
==0
A=
T2
For the first term Ti, taking the total expectation, we get
T
EE
g
Σ dd. - Eo
(56)
82( 1 1- 5)
(d..t Eg (cs,k(
(57)
A=0
82((-1-1) 1-8
E3
||d,N BB, [do,((=
(58)
k=0
TV
<VV
(1
TV + 32+ + +
82(1-1)) < 1- 82
(59)
=
where 57 and 58
are derived using the same routine according to Fact 4,
46 to
48
Similarly, for the second
term Tg in 55
(-1
H-1
27
E[Tz]
<
Σ
1-
Σ
3
3
Eg dayk
(60)
==0
==0
A==
1-8
(61)
0
4m0
k=
L. [2]
B E
do
(62)
8=0
k=U
24

---

Published as a conference paper at ICLR 2020
Substituting (59) and 662
back into (55) and summing over the t-th outer iteration, we have
4 4 L3
Na(1) S
| da
112
(63)
(1 (1- -32)
(1-
k=0
4K 4k 1. 1,
1. B22
Nt(
E
E 12?
[B
(64)
(1-
(1-3) 1=0
R=
4K 2L
4T
T-27-1
T-1
| xell
8T-1--
B2)
(1-
t=0 k=
8=1+1
(65)
4K 12BTVV
1.
E
||
(66)
(1- (82
-12
0=
4K BBB
2/
T-1
Σ
E
| de 113
(67)
B2)
(1-
47 L2B
12
T-17-1
(a(t)= S
E
E do
E
(68)
(1 (1-
(1 - B)² K
1=0 K=
1= k=
D.3.3 FINAL RESULTS
Plugging 5I and 668) back into
39 one can obtain
Blf o) f(00,0)]
<
Joff
T
I (xt,,))
Veff
C1
T-17-1
Σ
E || =d]
K
2K
2K
t= k=U
1=0 k=0
Yen L.
1 + (T ( (1-8-1)
2
8 I
+
+
2
α
(1 - 32)
T-17-1
Veil
E Vf((,,)) Een(de.
(69)
2K
1=0 k=0
where C1 = 1/2
LoaL - - 1) - B B - /(1 - B)3. When the
constants satisfy
1
Joh 472 1) (1-3- 0)
8 3
2 0,
(70)
2
a²
(1 31-
we have
(lI(())))) - f [30.0)]
T
T-1--1
<
Yeff
E E (
+
Teff
E (2xt,.) - Ex, (d.,((d,,)]'"
K
2k
2K
t= k=0
t= k=0
LV
(1-B-1)
2
87el 82
+ LT
+
(71)
2
(1 32
After rearranging terms, we get
2E 2E(f(2o.o) f(3r,o))
T-1
ΣΣ
E [f(x,,)))) - Ee, [dc,
K
JorK
K
1=0
k=
1=0 k=
(1-3
1
3 -1 1)
2 L82
LLLV
1 1 4ra - 1)
+
(72)
B2
25

---

Published as a conference paper at ICLR 2020
Furthermore, since Yo.o = 20,0 fx (10 bound can be simplified as
20,0 and f(yr,)) 2 fints the above upper
E B( ΣΣ
(f(22))))
-fint)
1
VoHkK
K
1=0
(1 11-3-11 )
2 + L
+ LV
1 1 MeaLLT
1)
(73)
a
g2
If we set Toff v K then
(f(20,)) fint)
T-1
E [|
E ( - -,,
K
VmK
K
1=0 k=0
mLV
4mL 1
( (1- (1-8-1)
2
8mL
+
(74)
Vmk
K
a
K(1 - B3)
Recall the learning rate constraint is
1 y/m VK'
7oL 47 1) (1 - 31-3-a0)
182
L
2 0.
(75)
a²
(1 3)2
When Yett
the constraint can be rewritten as
1
mL?
1) (1 - B -
a)2
mL2
B
m.I²²
+ +
87²
(76)
2
K
a²
K
(1-3)3 K
After rearranging, we have
K
K
3
a)² + 1672
82
21
+ 28 - 218
(1-8)² + 1,
(77)
mL?
mL?
a²
K
88(T - 1) (1 3 ))
B²
12
+ 1672
+
(78)
mL2
a²
(1- 31-
K
21 (8T(T - 1) (1 - 8 a-)2
B2
+ 167
+ 1)
(79)
mL2
a²
(1 (1- 3)2
Furthermore, note that
8T(T 1) (1 11-3-- 31-3-a)
B²
}
1
+ 1672
(1 - 8)2 + $1)
a²
9 - 8 a)
B²
+ 167
8)2 + 1
(80)
a²
3r(11
B a)
4
<v3
1
(81)
a
I g
Therefore, when K > mL2 (I (1+ 3max isfied.
3-(1-8-a
1 11). the condition (79) must be sat- 1-3
1r3
D.4 SPECIAL CASE 1: BLOCKWISE MODEL UPDATE FILTERING (BMUF)
In this case, the inner optimizer is Local-SGD. That is.
m
m
d
(F elf) E,,(d m v((
(82)
m
Since all worker nodes are averaged after every iterations, we have x easy to validate that V a² m//m.
(2) = 2r,0, Vi. Besides, it is
26

---

Published as a conference paper at ICLR 2020
According to previous literature the convergence of Local-SGD (Wang & Joshi 2018 Yu al. 2019a), we can directly get the following upper bound.
T-I K
A
B ((
B
(83)
m (xx.))
(84)
m
R
V (axak)
V v (8)
(85)
k= 21
T-11-1 m
mK ΣΣΣ
E
(86)
i=1
222
622
(87)
1 - 1272
1 12 L272
When yL. < 1. we have 1/(1 - 12
2 3/2. It follows that
E ((V)(()
(88)
K
Substituting (88) into 73 and setting Tー /m/ht K, we have
2L (f(x000)) - fiot) +
amm
3 + 9
E V fl (Zx x1?
K
Vmk
3)
K
t=
k=
1 1 3
#40
1)
B²
S
1
+
(89)
K
82)
K
=0
+ +0
m
(90)
Vmkk
K
D.5 SPECIAL CASE 2: LOOKAHEAD
In this case, the inner optimizer is SGD and m = Thus, we have 3 = -0, L.,, = vf(x())),
and V = 0², Therefore,
E(Vf(E (f( fint) ayK
Lo + 4(1 a2)l-)22223(7 1)0²
(91)
be observed that when 1 or r the above upper bound reduces to the case of vanilla
mini-batch SGD. If we set arL / ///K, then we have
2L (f(2)))) fin) +
4(1 10--0] o 1)o²
| [(),)))
<
(92)
K
VR
a²K K
t= 0=0
1
=0
+
(93)
VK
K
If the total iterations K is sufficiently large, then the first term will dominate the convergence rate.
27


Reviews:
[{"review_id": "rkeNRR7o9r", "reviewer": "AnonReviewer4", "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": "The paper presents a simple momentum scheme which can be applied to distributed and decentralized SGD schemes. The scheme proposes to do a sequence inner/local steps of any optimizer without any momentum, but then only apply momentum on the outer level, after each global synchronization round.\n\nThe paper is clearly written and experiments are well set up.\n\nIn a more general view, I'd encourage the authors to discuss in the paper that momentum can be applied both in the inner and the outer loop. For example both [K19] and [Assran et al. (2019)] have already applied momentum in a similar setting but focusing on the inner level (which would be harder to analyze in theory, but might be a good method in practice).\n\nThe provided theoretical convergence result is valuable as a contribution, even if it does not show benefits of momentum over SGD, but at least it shows a slowdown which is bounded, as in single-machine SGD. The authors have done non-trivial work to extend it to the case of communication and local updates, but I didn't have time to check the entire long proof in the appendix.\n\nThe experimental results are convincing in comparison to the baselines without momentum.\nI would have hoped the authors also add a more clear picture of how the proposed 'outer' momentum would compare to practical 'inner' momentum schemes such as used by [Assran et al. (2019)] and [K19].\n\nThe main question for me is on the significance of the contribution. The benefits of momentum are well known in practice in the single-machine case, and theoretically not well understood. The paper here translates this type of results also to the decentralized case. As momentum is common it is not very surprising that it is also beneficial here. The paper could be strengthened by adding comparisons of different inner/outer momentum variants which are unique to the distributed setting. \n\nMinor comments:\n- At the end of Section 3, it is said that \"Local SGD, ... perform averaging on the model parameters rather than on gradients.\".\nWhile not totally wrong, I think one should say that local SGD can easily do averaging of the model changes/deltas, instead of the models themselves.\n\n- Start of Page 3 and of Section 5: potentially clarify notion of 'descent direction', as with SGD those are not technically descent on the original (local or global) objective, but only on the currently sampled stochastic f_i .\n\nUPDATE AFTER REBUTTAL\nThe discussion and other reviews were helpful, for instance that the paper should still clarify better the fact that the proposed method is just a very minor generalization of BMUF, to some more SGD variants (including decentralized). Nevertheless, reviewers seem to agree that the paper is well-presented in giving a more clear review of such methods, and valuable in improving the theoretical understanding of such distributed momentum methods. I keep the current score.\n\nReferences:\n[K19] Koloskova, Anastasia, et al. \"Decentralized Deep Learning with Arbitrary Communication Compression.\" arXiv preprint arXiv:1907.09356 (2019).", "extra_scores": {"experience_assessment": "I have published one or two 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": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJg5vflkqH", "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": "Paper summary: \nThe paper proposes a general framework to improve the optimization and generalization performance of several communication efficient algorithms, including local SGD, SGP. A convergence analysis is provided for smooth non-convex losses. \n\nScore: Accept. \n\nDetailed comments: \nPros: \n* The paper is written in a clear and well-organized form. The experimental setup description, as well as the ablation study, provide a clear guideline to use this framework in practice. \n* The extensive empirical experiments in this paper justify the effectiveness of the proposed methods. \n\nCons: \n* Providing the convergence analysis is encouraged but more understanding is required. The analysis is quite standard and the convergence rate with extra effect (increasing the upper bound) in Eq.5 cannot explain why it convergences faster and generalizes better (e.g. in Figure 2) than AR-SGD. \n* As one main contribution of this paper is in terms of the theoretical convergence guarantees, the related work should precisely mention the recent progress in this area and (maybe) point out the difference compared to the prior work. \n\nMinor comments: \n1. It is confusing to talk about the \\tau in the main paper and the same \\tau notation in Algorithm 3 (default parameter in OSGP). Are these two factors the same?\n", "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": "H1g7D8tTFS", "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": "The authors verify the effect of BMUF[1], which is called slow momentum in this paper, on computer vision and natural language processing tasks with different kinds of local optimizers.  They also provided the theoretical convergence guarantee of BMUF.\n\nThe literature survey of this paper is quite good and the experimental results are convincing. However, they should modify their claim that \"BMUF is a special case of SlowMomentum\".\nIn classical block momentum version of BMUF, the  update formula is:\nu_{t+1} = \\beta u_{t} + \\alpha (x_{t,0}-x_{t,\\tau})\nx_{t+1,0} = x_{t,0} - u_{t+1}\n\\beta is called block momentum and \\alpha is block learning rate\n\nin this paper, the update formula becomes:\nu_{t+1} = \\beta u_{t} +  (x_{t,0}-x_{t,\\tau})/\\gamma_{t}\nx_{t+1,0} = x_{t,0} - \\alpha\\gamma_{t}u_{t+1}\n\nObviously this two formula are equivalent. BMUF is a general framework, which can work with different kinds of local optimizer. The author should not narrow down the definition of BMUF as BMUF with SGD as local optimizer and \\alpha=1. Actually, \\alpha=1 is used in all experiments of this paper.\n\nIn conclusion, the organization and writing of this paper is satisfactory, the experiments and theoretical proof is valuable for respective researchers. They should clarify that SlowMomentum is same with BMUF with classical block momentum. I will give a weak accept to this paper.\n\n [1] Kai Chen and Qiang Huo. Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5880–5884, 2016.", "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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a new approach, SlowMo, to improve communication-efficient distribution training with SGD. The main method is based on the BMUF approach and relies on workers to periodically synchronize and perform a momentum update. This works well in practice as shown in the empirical results. 

Reviewers had a couple of concerns regarding the significance of the contributions. After the rebuttal period some of their doubts were clarified. Even though they find that the solutions of the paper are an incremental extension of existing work, they believe this is a useful extension. For this reason, I recommend to accept this paper.
Decision: Accept (Poster)