Local SGD Meets Asynchrony
Authors: Bapi Chatterjee
Vyacheslav Kungurtsev
Dan Alistarh
Venue:  (2021)
Keywords: SGD
Data-parallel
Asynchronous
Optimization
Non-convex
Deep Neural Network

Abstract: Distributed variants of stochastic gradient descent (SGD) are central to training deep neural networks on massive datasets. 
Several scalable versions of data-parallel  SGD have been developed, leveraging asynchrony, communication-compression, and local gradient steps. Current research seeks a balance between distributed scalability--seeking to minimize the amount of synchronization needed--and generalization performance--seeking to achieve the same or better accuracy relative to the sequential baseline. However, a key issue in this regime is largely unaddressed: if ``local" data-parallelism is aggressively applied to better utilize the computing resources available with workers, generalization performance of the trained model degrades. 

In this paper, we present a method to improve the "local scalability" of decentralized SGD. In particular, we propose two key techniques: (a) shared-memory based asynchronous gradient updates at decentralized workers keeping the local minibatch size small, and (b) an asynchronous non-blocking in-place averaging overlapping the local updates, thus essentially utilizing all compute resources at all times without the need for large minibatches. Empirically, the additional noise introduced in the procedure proves to be a boon for better generalization. On the theoretical side, we show that this method guarantees ergodic convergence for non-convex objectives, and achieves the classic sublinear rate under standard assumptions. 
On the practical side, we show that it improves upon the performance of local SGD and related schemes, without compromising accuracy. 

Under review as a conference paper at ICLR 2021
LOCAL SGD MEETS ASYNCHRONY
ABSTRACT
Distributed variants of stochastic gradient descent (SGD) central to train- ing deep neural networks on massive datasets. Several scalable versions of data-paralles SGD have been developed, leveraging asynchrony. communication- compression, and local gradient steps. Current research seeks a balance be- tween distributed seelabbliityssekkinng to minimize the amount of synchronization needed-and generalization performance-sedde seeking to achieve the same or better ac- curacy relative to the sequential baseline. However, a key issue this regime is largely unaddressed: if "local" data-parallelism is aggressively applied to bet- ter utilize the computing resources available with workers, generalization perfor- mance of the trained model degrades.
In this paper, present method improve the "local scalability" of decen- tralized SGD. In particular, we propose two key techniques: (a) shared-memory based asynchronous gradient updates decentralized workers keeping the local minibatch size small, and (b) an asynchronous non-blocking in-place averaging overlapping the local updates, thus essentially utilizing all compute resources all times without the need for large minibatches. Empirically. the additional noise introduced in the procedure proves to be boon for better generalization. On the theoretical side, we show that this method guarantees ergodic convergence for non-convex objectives, and achieves the classic sublinear rate under standard as- sumptions. On the practical side, we show that it improves upon the performance of local SGD and related schemes, without compromising accuracy.
INTRODUCTION
In this paper, we consider the classic problem of minimizing empirical risk, defined simply min
Σ [i(x),
PER
XE
where d is the dimension, x E Rdd denotes the set of model parameters, [T] the training set, and f((x) Rd + R is the loss the training sample i E [4]. Stochastic gradient descent (SGD) (Rob- bins & Monro, 1951) is an extremely popular iterative approach to solving this problem:
Zk+1 23 ag V fB, (zx).
(2)
where VB = [मa ΣiE, Vi((z)) is the sum of gradients computed over samples, typically selected uniformly and randomly as a minibatch Bg [T]. and aj the learning rate iteration k.
1.1 BACKGROUND ON DECENTRALIZED DATA-PARALLE SGD
For better worse, SGD and its variants currently represent the computational backbone for many large-scale optimization tasks, most notably the training of deep neural networks (DNNs). Arguably the most popular SGD variant minibatch SGD (MB-SGD) (Bottou (2012)). In a distributed setting with decentralized workers g E [Q], it follows the iteration
Tk+1 Tx O%
Ving.
where B% S [2] local minibatch selected by worker g [Q] iteration k. This strategy is straightforward to scale in a Mata-paralle way, as each worker can process a subset of the samples in parallel, and the model is then updated by the average of the workers' gradient computations. For convenience, we assume the same batch size per worker. This approach has achieved tremendous popularity recently, and there has been significant interest in running training with increasingly large batch sizes aggregated over large number of GPUs, e.g. Goyal et al. (2017).
An alternative approach is parallel or local SGD (L-SGD) (Zinkevich et al. (2010); Zhang et al. (2016c); Lin et al. (2020)):
2//0411 = =9, - a'j,t Vfg,, 05t t Ky; 2/+1.0
Σ
2
(4)
Q
j,Ky'
9

---

Under review as a conference paper at ICLR 2021
where dz,, denotes the local model at worker E [Q] after j synchronization rounds followed by L local gradient updates and B¹,, is the local minibatch sampled at the same iteration. K, denotes the number of local gradient update steps before the jth synchronization. Essentially, workers run SGI) without any communication for several local steps, after which they globally average the resulting local models. This method is intuitively easy scale, since it reduces the frequency of the commu- nication. Recently, variant called post local SGD (PI.-SGD) (Lin et al. (2020)), was introduced to address the issue of loss in generalization performance of L-SGD, wherein the averaging frequency during the initial phase of training is high and is reduced later when optimization stabilizes.
Although very popular in practice, these two approaches suffer from the same limitation: their generalization accuracy decreases for larger local batch sizes, as would be ap- propriate to fully utilize the computation power offered by the workers. We illus- trate this in Table 1: examine the results of training RESNET-20 (He et al. (2016)) over CIFAR- 10 (Krizhevsky (2009)) with MB- SGD and PL-SGD over a workstation packing two Nvidia GeForce RTX 2080 Ti GPUs (a current standard). We observe that as the lo- cal batch size Bloe grows, the throughput im- proves significantly, however, the optimiza- tion results degrade sharply, more glaringly with PL-SGD. Clearly, these methods can not tolerate a larger Bl though the GPUs can support them. This shortcoming of the existing methods in hamnsssng the growing data- parallelism is also identified via empirical studies (Golmant et al. (2018); Shallue et al. (2019)) existing in literature. To our knowledge no effective remedy (yet) exists to address this challenge.
Method
Bloc
Train| Loss
Train
Test Loss
Test Acc
Timel (Sec)
Quality/ Perf.
Acc.
Ma-sGD
128
0.016
99.75
0.234
92.95
1754
Baseline
MB-SGD
1024
0.023
99.51
0.293
91.38
1201
OK
PL.-SD
128
0.018
99.69
0.245
92.98
1603
Good
PL-SOD
1024
0.154
94.69
0.381
87.81|
1159
Poor
Table 1: RESNET--UUCIEAR- training for 300 epochs on GPLss.
workers i.c. [B)) = Bloe: Vig E [Q]. k 2 0 for MB-SGD and [1]],l Bloe: Vi E i. 2 0 for Pr-s The L.R is warmed up for the first 5 epoccss to scale from do to on x Pios
Throughout the training the local BS is kept constant
22 XQ where Proe 128, Q is the number of workers, here, and Cip 0.1. PL-SGD, we average the model after each gradient update for lirst 150 epachs and thereafter averag- ing frequency K is sot to 16 as in Lin et al. (2020); other HPs are identical results are average runs with different seeds.
theirs. The
Notice that, here our core target is maximally harnessing the local data- pata-parallelism and therefore the larger local batch size, as against the existing trend in the literature wherein large number of GPUs are deployed to have large aggregated global batch size with a relatively small Bioe. For example, refer to the performance of MB-SGD and PL-SGD as listed in Table of Lin et al. (2020). Notice that with 16 GPUs, each with Bloe 128, thus totaling the minibatch size as 2048, identical to the one with 2 GPUs each with Bt 1024 as above, with exactly the same LR scaling and warmup strategy, both MB-SGD and PL-SGD do not face generalization degradation. However, unfortunately, such an implementation setting would incur excessive wastage of available data-parallel compute resources on each of the GPUs. Indeed, the existing specific techniques such as LARS (You et al. (2017)) to address the issue of poor generalization for global large batch training are insufficient for the larger local minibatch size; we empirically describe it in Section 3 (Table 11).
1.2 LOCALLY-ASYNCHRONE
PARALLEL SGD
Now, consider an implementation scheme as the following:
1. In a decentralized setting of L-SGD, i.c. wherein each worker q [Q] has a local model z undergoing local SGD updates as described carlier, multiple local concurrent processes u E U share the model x². Processes u E U perform asynchronous concurrent gradient updates locally.
2. The workers average their models whenever any one of them would have had at least K2 local shared updates, where K, is as that in Equation 4. The averaging is performed asynchronously and in a non-blocking way by the (averuging-) processes a on behalf of each worker y E [Q].
Essentially, the decentralized workers run haaaeddmemory-baaeee. asynchronous SGD locally and pe- riodically synchronize in a totally non-blocking fashion.
More formally, consider Algorithm 1. The model x on a GPU E [Q] is shared by the processes p E p4 = (UU) locally. The processes p E Pa also maintain a shared counter Sa, initialized to O. The operation read-and-ing Sa, whereas, read provides an atomic read. S" essentially enables ordering the shared gradient updates. In turn, this order streamlines the synchronization among workers, thereby determines the averaging rounds j. The (updater) processes u E U9 asynchronously and lock-freely update xº with
implements an atomic (with lock) read and increment of
2

---

Under review as a conference paper at ICLR 2021
gradients computed over non-blocking, potentially inconsistent, snapshot 6-14 of x², essentially going Hogwild! (Recht et al. (2011)), see Algorithm la.
1 Initialize Scur Spre 109,j = 0;
Initialize s = 0:
2 while Beur S T do
while < T do
8our == (ead Compute j corresponding to Bours
0 == p.l.i.issi s : read-and-inc(())
if Seur Spre: K2 then
0 == x [.] Viiissss d:
Compute V Vgg (1
Synchronize across a".r E [Q] {4) to compute
I1 Vsp (v "00 [b]]
1/ Ege Q 599 Compute Auy = Gj 10 Spre == Scuri
visisd;
1
+= A A [1.. j= j+
(a) Local asynchronous gradient update by process u Uº
(b) Asynchronous non-blocking in-place averaging.
Algorithm 1: Locally-
Parallel SGD (LAP-SGD)
The process a", which performs averaging for the worker E [Q], concurrently keeps on atomically reading 8", see Algorithm 1b. As soon it notices an increment K, in S i.e. 2n got concurrently updated with Kj number of gradients it takes non-blocking snapshot 0.9 of x and synchro- nizes with a" of peers r E [Q]/q to compute the average Ty of the snapshots. Thereafter, a adds the difference of the average with the snapshot v..4 to the model z without blocking the concur- rent asynchronous local gradient updates. We call this method locally-asynchrooous parallel SGD (LAP-SGD). This method closely resembles Hogwild++ (Zhang et al. (2016a)), which targets the heterogeneous NUMA based multi-core machines, though there are key differences which we de- scribe in Section 4. Results of the same training task as before by LAP-SGD is given in Table 2. The distinction of this implementation is that it harnesses the compute power of the GPUs not by increas- ing the size of Bioe but by concurrently computing many minibatch gradients. Evidently, LAP-SGD PGD provides speed-up without losing the quality of optimization in comparison to the baseline.
Recently, Kungurtsev et al. (2019) presented shared-memory based method wherein they showed that partitioned gradient updates for some iterations during the course of training over a shared model can reasonably save on total compu- tation cost by means of restricted backpropagation without necessarily losing on optimization quality. Their method is limited to a centralized shared- memory setting. Moreover, aiming to establish convergence under non-smoothness assumption, they ensure write consistency under model-widd lock. Having designed our asynchronous parallel SGD, it inspires us to adapt the partitioned gradient update strategy to our lock-free decentralized setting.
[0%]
Biod
Train
Train
Test
Test
Time (See)
Quality/ Port.
Loss
Acc.
Loss
Acc
128
0.012
99.83
0.270
92.92
1304
Excellent
128
0.023
99.51
0.266
92.91
1281
Excellent
0.010
99.90
0.280
92.93
1219
Excellent
Table 2:
REsNET-20/CrFA training for 300 epachs on GPUs by LAP-SGD. The warned similar PL-SOD. We follow the same averaging schedule and other HP's as those of PL- sGD, The listed
are average runs.
More specifically, building on LAP-SGD, we consider locally partitioned gradient computation along with asynchronous lock-free updates. Es- sentially, we partition the model x to {a {a% for
[09]
Bioc
Train Loss
Train Acc.
Test Loss
Test
Time (Sec)
Quality/
Acc
Perf.
0.019
99.62
0.270
92.98
1153
Excellent
128
0.021
99.58
0.262
92.84
1085
Excellent
256
0.019
99.65
0.267
92.95
1047
Excellent
E U9, i(u) n i(w) = 0, Vu, w E U9 (i.e., non-overlapping block components of the vector
Table 3: LPP-SOD performance. Other details are identical to
rr) With that, a partitioned gradient computation those in Table 2.
will amount to computing Vuw)JB (19.",, the minibatch gradient with respect to the partition
g (i))) at line in Figure la. Accordingly, the update step at line 6 in Algorithm la transforms to 2º] - a. V Vng (b), V i(u). It is to be noted that we do not use write lock for iterations at any stage. Having devised a partitioned update scheme, we propose locally partiii-- asynchronous parallel SGD (LPP-SGD) described below.
1. Processes u E U maintain a process-local variable last_iter which can take two values PARTITIONED and FULL. Each U initializes last_ited as FULL.
2. While s < Te,. each process u E U performs LAP-SGD updates as lines 3 to of Algorithm la.
3. If < s < T, each process u E 899 performs
3

---

Under review as a conference paper at ICLR 2021
(a) partitioned gradient computation and update: 2- [t] Last_iter= = FULL, and sets last_iter PARTITIONED.
0, f (o (1d) Vi E i(u) if
(b) an LAP-SGD update if last iter= PARTITIONED, and sets last iter FULL.
Essentially, after some initial stabilizing epochs each process u E U9 alternates between a full and a partitioned lock-free asynchronous gradient updates the model x Our experiments showed that Tat = To was almost always sufficient to obtain a competitive optimization result. The results of a sample implementation of LPP-SGD are available in Table 3. It is clear that LPP-SGD handsomely speeds up the computation and provides equally competitive optimization results.
CONVERGENCE THEORY
At a naive first glance, studying the convergence properties of locally asynchronous SGD would be an incremental to existing analyses for local SGD, e.g. Stich (2018); Zhou & Cong (2017), in partic- ular the local stochastic gradient evaluations at delayed lock-free Hogwild!-like parameter vectors. However, there is one significant difference that presents theoretical challenge: sometimes the vectors used for gradient computation or components thereof, have been read from the local shared memory before the last averaging across GPUs had taken place. Especially in the nonconvex case, a priori is impossible to place a reasonable bound on the accuracy of these gradient evaluations relative to what they "should be" in order achieve descent.
In order to present a convergence rate result, we need to define anchor point which we can consider conver- gence to some approximate stationary point in expectation. This is not trivial as both local iterations and averaging is performed asynchronously across different GPUs at distinct moments in time, with the time at which each iteration oc- curs potentially varying with system-dependent conditions, while the averaged iterates are what is important to consider for convergence.
Initialize 2n 2 for all q;
for j I.... J do
for all do
Set 2 = F5; for 1 1,.., Kj do
Let xt x-11 Ojiig V (
We seek to define the major iteration T. as consistent with the analysis presented for the convergence of local SGD in the nonconvex setting in Zhou & Cong (2017). In this case, with asynchrony, 3y is theoretical construct, i.e., it may not exist at any particular GPU's memory at any moment in time. Let s) == Scar current state of the shared counter before the jth synchronization round at the GPU q. then ãy is defined as x²; + Au, where z²g is the state of the model for GPU q when of was saved and made available for averaging for "major iteration" j. Thus although de facto averaging could have taken place after set of local updates in time, these local updates correspond to updates after iteration conceptually. This makes ž; properly correspond to the equivalent iterate in Zhou & Cong (2017).
Let KK²
Algorithm 2: Iterations of the view Zy.
|89| be the
With that, we consider sequence of major iteration views {.,} with associated inter-averaging local iteration quantities Kj and local views {x(²) at which unbiased estimate of the (possibly partitioned) gradient is computed, with 0 S L < K; as well as the local model in memory (x²" ). The partition, which could be the entire vector in general, is denoted by i(j, g). As each GPU has its own corresponding annealed stepsize, we denote it in general as ag.t.g as well.
We state the formal mathematical algorithm as Algorithm 2. Note that this is the same procedure as the practical "what the processor actually does" Algorithm 1, however, with the redefined terms in order to obtain a precise mathematical sequence well-defined for analysis.
We make the following standard assumptions on unbiased bounded variance for the stochastic gra- dient, bounded second moment, gradient Lipschitz continuity, and lower boundedness of f. Assumption 2.1. 1. It holds that (ef())")) satisfies, independent of i. E [+.f(1]6)] =
0²: ( <G.
Val(oz"); E
ff is Lipschitz continuously differentiable with constant L and is bounded below by fm
We must also define some assumptions the probabilistic model governing the asynchronous com- putation. As these are fairly technical we defer them to the appendix.
4

---

Under review as a conference paper at ICLR 2021
Theorem 2.1. Given assumption 2.1, it holds that, b E.- E CagaagCi 25 C2 ( a (1ggt) |
Ca | aa {
(5)
f
where C₁ C2. C3, and C4 depend on L, B and probubilistic quantities defining the asynchronous
computation (see Appendix. Thus there exists of such constants such that if a'aj... θ
(+))
then Algorithm ergodically converges with the standard J(1/VJ) rate for nonconvex objectives.
Proof Summary: The proof follows the structure of the ergodic convergence proof of K-step local SGD given Zhou Cong (2017), wherein each round of averaging there are QK₃ total updates to the model vector associated with the Q GPUs and K minor iterations.
Insofar as these updates are close (stochastically as an unbiased estimate, and based on the local models not having changed too much) to the globally synchronized model vector at the last averaging step, there an expected amount of descent achieved due to the sum of these steps. This is balanced with the amount of possible error in this estimate based on how far the model vector had moved.
In cases wherein v/,:/ = _ for s < 0 (i.e., the stochastic gradients are taken, due to local asyn- chrony, at model vectors with components which existed memory before the last averaging step), we simply bound the worst-case increase in the objective.
To balance these two cases, the analysis takes an approach, inspired partially by the analysis given in Cartis & Scheinberg (2018) of separating these as "good" and "bad" iterates, with "good" iterates corresponding to views read after the last model was stored for averaging, with some associated guaranteed descent in expectation, and "bad" iterates those read beforehand.
By considering the stochastic process governing the amount of asynchrony as being governed by probabilistic laws, we can characterize the probability of "good" and "bad" iterate and ultimately seek to balance the total expected descent from one, and worst possible ascent in the other, as a function of these probabilities.
Remark 2.1. [Speedup due to concurrent updates] Consider the case of classical vanilla local SGD, in which there is complete symmetry in the number of local gradient computations between averaging steps and block sizes across the processors. In this case, for every major iteration there are Q gradient norms on the left hand side, and at the same time it is divided by Q. Thus local SGD as a parallel method does not exhibit classical speedup, rather it can be considered as an approach of using parallelism have more robust and stable method of performing gradient updates with multiple batches computed in parallel. However, due to the idle time that exists between the slowest and fastest processors, it will exhibit negative speedup, relative to the fastest processor. With the approach given in this paper, this negative speedup is corrected for in that this potential idleness is filled with additional stochastic gradient computations by the fastest process. Alternatively, one can also consider this as exhibiting positive speedup relative to the slowest process, whereas standard local SGD has zero speedup relative the slowest process. Above and beyond this, we can consider that as more processes introduces additional latency and delay, which has a mixed effect: on the one hand, we expect that gradient norms at delayed iterates to be larger as the process converging, thus by having more delayed gradients on the left hand side, convergence is faster, and on the other hand, such error in the degree to which the gradient decreases the objective, would specifically increase the constants C2 and CA.
IMPLEMENTATION DETAILS AND NUMERICAL RESULTS 3.1 EXPERIMENTAL SET-UP
Decentralized training. We evaluate the proposed methods LAP-SGD and LPP-SGD compar- ing them against existing MB-SGD and PL-SGD schemes, using CNN models RESNET-20 (He et al. (2016),, SQUEEZENET (Iandola et al. (2017)), and WIDERESNET-I6XS (Zagoruyko & Ko- modakis (2016)) for the 10-/100-class image classification tasks datasets CIFAR- CEFFAR-1/CIIAN 10/CIFAR- 100 (Krizhevsky (2009)). We also train RESNET-18 for a 1000-class classification problem on IMA- GENET (Russakovsky al. (2015)) dataset. We keep the sample processing budget identical across the methods. We use the typical approach of partitioning the sample indices among the workers that can access the entire training set; the partition indices are reshuffled every epoch following seeded
5

---

Under review as a conference paper at ICLR 2021
random permutation based on epoch-order. To this effect process u E U in asynchronous methods. Thus, our data sampling is i..dd
shared-counter among concurrent
Platform specification. Our experiments are based on a set of Nvidia GeForce RTX 2080 Ti GPUs (Nvidia (2020)) (referred to as GPUs henceforth) with 11 GB on-device memory. We use the following specific settings: (a) S1: a workstation with two GPUs and an Intel(R) Xeon(R) E5-1650 v4 CPU running @ 3.60 GHz with 12 logical cores, (b) S2: a workstation with four GPUs and two (ntel(R) (R) E5-2640 v4 CPUs running @ 2.40 GHz totaling 40 logical cores, and (c) S3: two S2 workstations connected with a 100 GB/s infiniband link. The key enabler of our implementation methodology are multiple independent client connection between a CPU and a GPU. Starting from early 2018 with release of Volta architecture, Nvidia's technology Multi-process Service (MPS) efficiently support this. For more technical specifications please refer to their doc-pages MPS (2020).
Implementation framework. We used open-source Pytorch 1.5 (Paszke et al. (2017)) library for our implementations. For Pross-GUU/rross-maaee
communication we use NCCL (NCCL (2020))
primitives provided by Pytorch. MB-SGD is based on DistributedDar wtt.aaaaaaraalleee Paralell Pytorch module. PL-SGD implementation is derived from author's code (LocalSGD (2020)) and adapted to our setting. Having generated the computation graph of the loss function of CNN, the autograd package of Pytorch allows user to specify the leaf tensors with respect to which gradients are needed. We used this functionality in implementing partitioned gradient computation in LPP-SGD.
bacally-asynchronouu Implementation. One key requirement of the proposed methods is to sup- port non-blocking synchronization among GPUs. This is both challenge and an opportunity. To specify, we use a process on each GPU, working as a parent, to initialize the CNN model and share it among spawned child hhild-processes. The child-processes work as E U9, Vg E [Q] to compute the gradients and update the model. Concurrently, the parent-process, instead of re- maining idle as it happens commonly with such concurrency models, acts as the averaging process a E P9, Vq E [Q], thereby productively utilizing the entire address space occupied over the GPUs. The parent- and thild-processer share the iteration and epoch counters. Notice that, here we are us- ing the process-level concurrency which is out of the purview of the thread-level global interpreter lock (GIL) (Python (2020) of python multi multi-threading framework.
Hyperparameters (HPs). Each of the methods use identical momentum (Sutskever et al. (2013)) and weight-decay (Krogh& & Hertz (1991)) for given CNN/dataset case; we rely on their previously used values (Lin et al. (2020)). The learning rate (LR) schedule for MB-SGD and PL-SGD are identical Lin et al. (2020). For the proposed methods we used cosine annealing schedule without any intermediate restart (Loshchilov & Hutter (2017)). Following the well-accepted practice, we warm up the LR for the first 5 epochs starting from the baseline value used over a single worker training. In some cases, grid search (Pontes et al. (2016)) suggested that for LPP-SGD warming up the LR up to 1.25 of the warmed-up up LR of LAP-SGD for the given case, improves the results.
3.2 EXPERIMENTAL RESULTS
In the following discussion we use these abbreviated notations: U U0% B : Bioc. Tr.L.: Training Loss, Tr.A.: Training Accuracy, Te.L.: Test Loss, Te.A.: Test Accuracy, and T: Time in Seconds. The asynchronous methods have inherent randomization due to process scheduling by the operation system. Therefore, each micro-benchman benchmark presents the mean of runs unless otherwise mentioned.
U|
TtA.
Te.A.
128
99.62
92.81
1304
6
128
99.85
92.92
1266
8
128
99.62
92.64
1259
4
256
99.72
92.83
1219
6
256
99.90
92.24
1166
Table
4:
LAP-SOD perfor-
Concurrency GPUs. We allocate the processes on GPU up to the availability of the on-device memory. However, once the data-parallel compute resources get saturated, allocating more processes degrades the performance. For example, see Table 4 which lists the average performance of 5 runs for different combinations of U and B for training RESNET- 20/CIFAR- 10 by LAP-SGD on the setting S1.
mance.
Asynchronous Averaging Frequency. Following PL-SGD, as general rule, for the first half of the training, call it up until P epochs, we set the averaging frequency K = 1. However, notice that, unlike PL-SGD, setting K < Q in LAP-SGD and LPP-SGD may not necessarily increase the averaging rounds j in aggregation. Intuitively, in a asynchoosy setting, along with the non- blocking (barrier-free) synchronization among GPUs, the increment events on the shared-counte S would be "grouped" on the real-time scale the processes u E U do not face delays in scheduling, which control by allocating an optimal number of processes to maximally utilize the compute

---

Under review as a conference paper at ICLR 2021
resources. For instance, Table 5 lists the results of random runs of RESNET-20/C with B = 128 and = 6 with different combinations of K and P over S1. This becro-bbncchark indicates that the overall latency and the final optimization result of our method may remain robust under small changes in K, which it may not be the case with PI.SGD.
training
Scalability. Table 6 presents the results of WIDERESNET- 16X8/CIFAR-10 training in the three system settings that we consider. We observe that in each setting the relative speed-up of different methods are approximately consistent. In particular, we note the following: (a) reduced communication cost helps PI.-SGD marginally outperform MB-SGD, (b) interestingly, increasing Bioe from 128 to 512 does not improve the latency by more than ~4%; this non-linear scalability of data-parallelism was also observed by Lin et al. (2020). (c) each of the methods scale by more than 2x as the implementation is moved to S2, which has 40 CPU cores, from S1 which has 12 CPU cores, furthermore, this scalability is approximately 2x with respect to performance on S3 in comparison to S2, this shows that for each of the methods we utilize available compute resources maximally, (d) in each setting LAP-SGD achieves ~30% better throughput compared to MB-SGD standard batch, (e) in each setting LPP-SGD outperforms LAP-SGD by ~ 122 making it the fastest method, (f) the training and test accuracy of local large minibatch is poor, and (g) the methods LAP-SGD and LPP-SGD consistently improve the bascline generalization accuracy.
K
P
TrA.
Te.A.
T
150
99.76
93.01
1266
4
150
99.85
92.78
1263
93.08
1262
8
0
99.78
92.83
1263
150
99.90
93.16
1261
Table 5:
LAP-SOD perfor-
munce.
R265
8298
7500
Tra (e)
Law-son
Pl-sGi
5000
4002
5784
Mi- (8-128)
PL-ssio (BH512)
2500
1007
2714
1962
1375
7116
2006
2105
1977
(3
(2)
(3)
(4)
(5)
(5)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(19)
Method
Q
TrA.
Te.A.
T
||
Q
TrA.
Te.A.
T
Q
Tr..
Te....
T
LAP-SGO
(1)
2
100.0
94.92
6368
(7)
4
100.0
94,91
3092
(13)
8
100.0
94.69)
1562
LPP-SGD
(2)
99.97
94.89
5551
(8)
99.96
94.87
2724
(14)
99.99
93.78
1377
MB-SGD-128
(3)
100.0
93.9%
8265
(9)
100.0
94,22
4045
(15)
100.0
93.83
2116
MB-SGD-55 5G2-512
(4)
2
95.68
88.42
7920
(10)
99.87
89.46
3913
(16)
8
87.54
73.97
2076
PL-SCD-12X
99.99
8293
(11)
4022
(17)
99.98
94.18
PGD-511512
(6) 2
95.34
88.33
7829
(12)
98.52
84.45
3784
(18)
8
89.19
81.80
1977
Table 6: WIDERESNET-IGSSCCIAA. 10 training in the settings $1: Q = S2: Q = 4, and and Q 8. MB-
CCD-128 indicates MB-SGD method with Bi.. 128 and similarly for others. For LAP-SGD, spawned
concurrent processes on each GPU: 4. whereas for LPP-SGD U 3 concurrent processes were spawned.
Method
U]
Tr..
Tc...
Tr...
Te.A.|
Method
B
Tr...
Te.I.]
Tr..
Te.A.
LAP-SGD
128
0.295
1.191
92.23
69.43
1285
MB-SGD
1024
0.464
1.212
86.46
67.04
1244
LAP-SGD
128
0.299
1.198
92.15
69.78
MB-SGD
128
0.360
69.73
1754
LPP-SGD
128
6
0.404
1.173
83.69
69.47
1085
PL-SGD
1024
0.373
1.152
89.48
67.97
1198
L.P-SCiD
0.378
1.161
89.50
69.75
1154
PI-son
0.379
1.099
89.29
69.67
Table 7: Performance of RESNET-20 on CIFAR-100 over the setting S1.
Method
B
U|
TrL.
Te.L.
Tr..
Te.A|
T
Method
B
U
TrL.
Te.L_
Tr..
Te.A.
T
LAP-SGD
64
4
0.007
1.341
99.98
75.97
1564
MB-SGD
512
0.034
1.918
99.64
63.74
2076
Lre-sGD
64
0.008
1.554
99.97
75.42
1376
PL-SOD
128
0.020
1.354
99.81
72.38
2108
MB-SGD
128
0.007
1.348
99.97
73.29
2115
PL-SGD
512
0.393
1.758
88.91
60.47
1976
Table 8: Performance of WIDERESNET 16x8 on CIFAR- 100 over the setting S3.
Method
B
U|
Tr..
Te.L.
TrA.|
Tc...|
T' ||
Method
B
Tr..
Te...
TrA.
Te...|
LAP-SGD
128
0.004
0.385
99.95
92.48
1251
MB-SGD
128
0.005
0.294
99.93
92.41
2245
LPP-SGD
256
3
0.007
0.355
99.89
92.55
1027
PL-sGD
1024
0.005
0.329
99.93
91.99
1202
MB sGD
1024
0.003
0.325
99.97
91.50
1580
PL. SGD
128
0.006
0.283
99.91
92.51
1843
Table 9: Performance of SQUEEZENET on CIFAR-10 10 over the setting S1.
Other C1FAR-10/CIFAR-1
Results. Performance of the proposed methods in comparison to datasets
the baselines for other training tasks on
available in Tables 7, 8, and 9. In each case we use K = 16 in LAP-SGD, LPP-SGD, and PL-SGD after 50% of total sample processing budget. As an overview, the relative latency of the methods are as seen in Table 6, whereas in each case LAP-SGD and LPP-SGD recovers or improves the baseline training results.
Imagenet Training Results. Having comprchensively evaluated the proposed methods on CIFAR- MARR--0//FFAR-II1 here we present their performance 1000-classes Imagenet dataset.
7

---

Under review as a conference paper at ICLR 2021
Method
U
TrL.
TrA.
Tc...
Te.A.
T
(1)
1.319
68.97
1.215
Acc01
(2)
LPP-SGD
32
4
1.397
68.31
1.257
69.91
24066
40
-(1 (4)
(3)
MB-sGD
128
1.237
70.63
1.220
70.07
26772
(2) (-())
(4)
MB-sGD
1.339
68.53
1.231
70.13
30706
20
- (3) (6)
(5)
PL.-SD
128
1.256
70.22
1.223
70.02
25850
(6)
PL-SGD
1.350
68.32
1.236
70.02
31468
10
Eoochs
60
80
Table 10: RESNET- ISEMAGEETT Training results.
Figure 2: Top-1 Test Accurcy.
Notice that for this training task, with 8 commodity GPUs at our disposal we are very much in the small minibatch setting. Plethora of existing work in the literature efficiently train a RESNET on IM- AGENET with BS up to multiple thousands. Other ristem-depender setting faces is that there hardly any leftover compute resources for us to exploit in the local setting of a worker. Yet, accuracy of the baseline with speed-up.
constraint that our considered
for RESNET-18, see Table 10, that LAP-SGD improves generalization
LR Tuning strategy. It is pertinent to mention that the ex- isting techniques, such as LARS (You et al. (2017)), which provide an adaptive LR tuning strategy for large minibatch set- tings over a large number of GPUs, wherein each worker lo- cally processes a small minibatch, are insufficient in the case Bloe increased. For example, see Table which lists the average performance of 5 runs on the setting S1 for Q 2 for training DESNET--0/CCFARR -00
Method
TrA.
Tc...
Ma-SOD
1024
1324
PL-SGD
1
1024
93.67
84.69
1304
LAP-SGD
4
256
99.87
92.90
1232
LPP-SGD
4
256
99.59
92.83
1071
Table 11: LARS performance.
using the compared methods combined with LARS with 1) = 0.001 (You et al. (2017)). We scale the LR proportionately: og Bise"
BxQ where Bloe = 128, Q is the number of workers, here, and ao = 0.1. Evidently, LARS did not help MB-SGD and PL-SGD in checking the poor generalization due to larger B.
3.3 ON THE GENERALIZATION OF THE PROPOSED METHODS
Let us comment on a theoretical basis of the remarkable performance in terms of generalization error of our methods. Lin et al. (2020), the model SGD algorithms as a form of a Euler- Maruaa-a discretization of Stochastic Differential Equation (SDE) presents the perspective that the batch-size can correspond to the inverse of the injected noise. Whereas distributed SGD combined stochastic gradients such effectively results in an SGD step with a larger batch-size, local SGD, by averaging models rather than gradients, maintains the noise associated with the local small-batch gradients. Given the well-established benefits of greater noise in improving generalization accuracy (e.g. Smith & Le (2018) 8) and others), this presents a heuristic argument as to why local SGD tends to generalize better than distributed SGD. In the Appendix we present an additional argument for why local SGD generalizes well.
However, we see that our particular variation with asynchronous local updates and asynchronous averaging seems to provide additional generalization accuracy above and beyond local SGD, We provide the following explanation as to why this could be the case, again from the perspective of noise as it would appear in SDE. Let us recall three facts,
The noise appearing as a discretization of the Brownian motion term in the diffusion SDE, and, correspondingly the injected noise studied as a driver for increased generalization in previous works on neural network training is i.i.d.,
2. Clearly, the covariances of mini-batch gradients statistical estimates of the gradient at x and x' are going to be more similar when x and x' are closer together,
3. (see Section 2) A challenging property from the perspective of convergence analysis with locally asynchronous updates is gradients taken at models taken at snapshots before a previous all-to-all averaging step, and thus far from the current model in memory.
Thus, effectively, the presence these "highly asynchronous" stochastic gradients, while being potentially problematic from the convergence perspective, effectively brings the analogy of greater injected noise for local SGD over distributed data-parallel closer to accuracy by inducing greater probabilistic independence, i.e., the injected noise, for these updates, is far close the i.i.d. noise that appears in a discretized SDE.
RELATED WORK
In the previous sections we cited the existing literature wherever applicable, in this section we present brief overview of closely related works and highlight our novelty. In the shared-memory
8

---

Under review as a conference paper at ICLR 2021
setting, HOGWILD! (Recht et al. (2011)) is now the classic approach to implement SGD. How- ever, it remains applicable to a centralized setting of a single worker and therefore is not known to have been practically utilized for large scale DNN training. Its success led to designs of vari- ants which targeted specific system aspects of a multi-core machine. For example, Buckwild! (Sa et al. (2015)) proposed using restricted precision training on CPU. Another variant, called HOG- WILD!++ (Zhang et al. (2016b)), harnesses the non-uniform- wwwiiooo--mmmor--eeee memory-access (NUMA) architecture based multi-core computers. In this method, threads pinned to individual CPUs on multi-socket mainboard with access to common main memory, form clusters.
In principle, the proposed LAP-SGD can be seen as deriving from HOGWILD!++, However, there are important differences: (a) at the structural level, the averaging in HOGWILD!++ is binary on ring graph of thread-clusters, further, it is token based procedure where in each round only two neigh- bours synchronize, whereas in LAP-SGD it is all-to-all, (b) in HOGWIID!++ each cluster maintains two copies of the model: a locally updating copy and buffer copy to store the last synchronized view of the model, whereby each cluster essentially passes the "update" in the local model since the last synchronization to its neighbour, however, this approach has a drawback as identified by the authors: the update that is passed leading to divergence, to overcome this problem they decay the sent out update; as against this, LAP-SGD uses no buffer and does not track updates as such, averaging the model with each peer, similar to L-SGD, helps each of the peers to adjust their optimization dynamics, (c) it is not known if the token based model averaging of HOGWILD!++ is sufficient for training DNNs where gener- alization is the core point of concern, in place of that we observed that our asynchronous averaging provides an effective protocol of synchronization and often results in improving the generalization, (d) comparing the HOGWILD!++ thread-clusted to concurrent processes on GPUs in LAP- the latter uses a dedicated process that performs averaging without disturbing the local gradient up- dates thereby maximally reducing the communication overhead, (e) finally, the convergence theory of LAP-SGD guarantees its efficacy for DNN training, which we demonstrated experimentally, by contrast, HOGWILD!++ does not have any convergence guarantee.
ring of workers eventually "comes back" to itself thereby
Recently, Wang et al. (2020) proposed Overlap-local-SGD, wherein they suggested to keep a model copy at each worker, very similar to HOGWILD!++, which is simultancously averaged when quential computation for multiple iterations happen locally. They showed by limited experiments that it reduced the communication overhead in non-iid training case based on CIFAR- 10, however, not much is known about its performance in general cases. The asynchronous partitioned gradient update of LPP-SGD derives from Kungurtsev al. (2019), however, unlike them we do not use locks and our implementation setting is decentralized, thus scalable.
CONCLUSION Picking from where Golmant et al. (2018) 8) concluded referring to their findings: "These results suggest that we should not assume that increasing the batch sitchsizeeor larger datasets will keep training times manageable for all problems. Even though it is natural form of data parallelism for large- scale optimization, alternative forms of parallelism efficiently". ,, our work introduces a fresh approach in this direction to addressing the challenge.
should be explored to utilize all of our data more
In our experiments, we observed that the natural gystem-generatee noise in some cases effectively improved the generalization accuracy, which we could not obtain using the existing methods ir- respective of any choice of seed for random sampling. The empirical findings suggest that the proposed variant of distributed SGD has a perfectly appropriate place fit in the horizon of efficient optimization methods for training deep neural networks. As a general guideline for the applicability of our approach, we would suggest the following: monitor the resource consumption of a GPU that trains a CNN, if there is any sign that the consumption was less than 100%, try out LAP-SGD and LPP-SGD instead of arduously, and at times unsuccessfully, tuning the hyperparameters in order to harness the data- pata-pprallellim. The asynchronous averaging protocol makes LAP-SGD and LPP-SGD specially attractive to settings with large number of workers.
There are plethora of small scale model and dataset combinations, where the critical batch size- after which the returns in terms of convergence per wall-clock time diminish-is small relative to existing system capabilities (Golmant et al. (2018)). To such cases LAP-SGD and LPP-SGD be- come readily useful. Yet, exploring the efficiency of LAP-SGD and LPP-SGD to train at massive scales, where hundreds of GPUs enable training IMAGENET in minutes (Ying et al. (2018)), is an ideal future goal. We also plan to extend the proposed methods to combine with communication optimization approaches such as QSGD (Alistarh et al. (2017)).

---

Under review as a conference paper at ICLR 2021
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and M. Vojnovic. Qsgd: Communication efficient sgd via gradient quantization and encoding, NIPS, 2017.
Nils Berglund. Kramers' law: Validity, derivations and generalisations. arXiv preprint
arXiv: /06.5799, 2011.
Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pp. 421-
436. Springer, 2012.
Coralia Cartis and Katya Scheinberg. Global convergence rate analysis of unconstrained optimiza- tion methods based on probabilistic models. Mathematical Programming, 169(2):337-37) 2018.
Xiaowu Dai and Yuhua Zhu. Towards theoretical understanding of large batch training stochastic gradient descent. arXiv preprint arXiv: 2018.
Noah Golmant, Nikita Vemuri, Zhewei Yao, Vladimir Feinberg, A. Gholami, Kai Rothauge, M. Ma- honey, and Joseph F. Gonzalez. On the computational inefficiency of large batch sizes for stochas- tic gradient descent. ArXiv, abs/1811.1221
2018.
Priya Goyal, Dollár, Ross B. Girshick, P. Noordhuis, L. Wesolowski, Aapo Kyrola, Andrew Tul- loch, Y. Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. ArXiv, abs/1706. 02677, 2017.
Kaiming He, Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Forrest N. landola, Matthew W. Moskewicz, K. Ashraf, Song Han, W. Dally, and K. Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and ilmb model size. ArXiv, abs/1602.00336.. 2017.
Nitish Shirish Keskar, Jorge Nocedal, Ping Tak Peter Tang. Dheevatsa Mudigere, and Mikhail Smelyanskiy. On large-batch training for deep learning: Generalization gap and sharp minima. In 5th International Conference on Learning Representations, ICLR 2017, 2019.
A. Krizhevsky. Learning multiple layers of features from tiny images. 2009.
A. Krogh and J. Hertz. A simple weight decay can improve generalization. NIPS, 1991.
V. Kungurtsev, Malcolm Egan, Bapi Chatterjee, and Dan Alistarh. Asynchronous stochastic subgra- dient methods for general nonsmooth nonconvex optimization. arXiv: Optimization and Control, 2019.
Tao Lin, S. Stich, and M. Jaggi. Don't use large mini-batches, use local sgd. ArXiv, abs/ htts/1808.02.17, 2020.
LocalSGD. http:pss/gggttab..mo//e////////a
Code. 2020.
I. Loshchilov and F. Hutter. Sgdr: Stochastic gradient descent with warm restarts. In ICLR, 2017.
Nvidia MPS. http:://oo....ddda.ccc/////////p
2020.
Giorgi Nadiradze, Ilia Markov, Bapi Chatterjee, Vyacheslav Kungurtsev, and Dan Alistarh. Elas- tic consistency: A general consistency model for distributed stochastic gradient descent. arXiv preprint arXiv:2001.05918 2020.
NCCL. http:///w...cscoacccccceec/e///s
2020.
Nvidia.
https: http::://wwww..iii http://wwww.aaac.caao/aaat/t/ttp rtx rtx-2080-t.// 2020.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
10

---

Under review as a conference paper at ICLR 2021
F. J. Pontes, Gabriela da F. de Amorim, P. Balestrassi, A. P. Paiva, and J. R. Ferreira. Design of experiments and focused grid search for neural network parameter optimization. Neurocomputingg 186:22-34, 2016.
Python.
https://docs: wrttoocsspphhooooroooo pyt.hon.org///goossarrr. htmll
tern--gloall-nnteppett------ 2020.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in neural information processing systems, pp. 693-701, 2011.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 4000407, 1951.
Olga Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Zhiheng Huang, A. Karpathy, A. Khosla, M. Bernstein, A. Berg, and Li Fei-Fei. Imagenet large scale visual recognition chal- lenge. International Journal Computer Vision, 115:211-233 1--22, 2015.
C. D. Sa, Ce Zhang, K. Olukotun, and C. Ré. Taming the wild: A unified analysis hogwild-style algorithms. Advances in neural information processing systems, 28:2656 2664, 2015.
Christopher J. Shallue, Jaehoon Lee, J. Antognini, Jascha Sohl-Dickstein, Roy Frostig, and G. Dahl. Measuring the effects of data parallelism neural network training. J. Mach. Learn. Res., 20: 112:1-112:49, 2019.
Samuel L Smith and Quoe Le. A bayesian perspective on generalization and stochastic gradient descent. In International Conference on Learning Representations, 2018.
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.09767. 2018.
llya Sutskever, J. Martens, G. Dahl, and Geoffrey E. Hinton. On the importance of initialization and momentum in deep learning. In JCML, 2013.
Jianyu Wang, Hao Liang, and G. Joshi. Overlap local-sgd: An algorithmic approach to hide com- munication delays in distributed sgd. ICASSP 2020 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8871-8875, 2020.
Chris Ying, S. Kumar, Dehao Chen, T. Wang, and Youlong Cheng. Image classification at super- computer scale. ArXiv, abs/18 0A1118811.69992 2018.
Yang You, Igor Gitman, and B. Ginsburg. Large batch training of convolutional networks. arXiv: Computer Vision and Pattern Recognition, 2017.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. ArXiv, abs/1605.07144, 2016.
Huan Zhang, Cho-Jui Hsieh, and V. Akella. Hogwild++; A new mechanism for decentralized asynchronous stochastic gradient descent. 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 629-638, 2016a.
Huan Zhang, Cho-Jui Hsieh, and Venkatesh Akella. Hogwild++: A new mechanism for decentral- ized asynchronous stochastic gradient descent. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 629-638. IEEE, 2016b.
Jian Zhang, C. D. Sa, loannis Mitliagkas, and C. Ré. Parallel sgd: When does averaging help? ArXiv, abs/16066 603667.65, 201
Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradi- ent descent algorithm for nonconvex optimization, arXiv preprint arXiv: 700.01012, 2017.
Martin Zinkevich, M. Weimer, Alex Smola, and L. Li. Parallelized stochastic gradient descent. In NIPS, 2010.
11

---

Under review as a conference paper at ICLR 2021
A
APPENDIX A: CONVERGENCE THEORY
A.1 PROBABILISTIC ASSUMPTIONS GOVERNING THE ASYNCHRONOUS COMPUTATION
Now let us discuss the formalities of the asynchronous computation. We consider that the pres- ence of local Hog Wild--kkk asynchronous computation introduces stochastic delays, i.e., at each stochastic gradient computation, the set of parameters at which the stochastic gradient is evaluated random, follows some distribution. Thus, considering that, the general case.
u/. (0.......)) (---f (
now define probability that this parameter view block is equal to each of these potential historical parameter values. To this end define 1f.i-.- the event that block in the view for GPU at major iteration j and minor iteration t is equal to the actual parameter 2 and prke is its probability. Now, u/, could be, e.g., 2- for some & E evaluated parameter before the last averaging took place.
K)-1), }. i.e., it could have been
In the nonconvex setting, it would be entirely hopeless to bound || 12 in general, in this case we can simply hope that the objective function decrease achieved by iterations with a gradient computed after averaging step outweighs the worst-case increase that takes place before it. In order to perform such an analysis, we will need bound the probability that this worst case occurs. In order to facilitate the notation for this scenario, let us define x' = x 4.f-1 Ki-i x² = = - etc., and then (.i. correspondingly. We can extend this analogously to delays from before two 1,i0 is well defined for any S 1, Z, of averaging steps, etc. Note that with this notation, PL.
course as long as
K
In order to derive expected decrease in the objective, we need to bound the probability of an increase, which means bounding the probability that the view older than the previous averaging. which can be bounded by bound on the probability that a particular read is more than some number T iterations old. We thus make the following assumptions,
Assumption A.1. It holds that,
1..... 0 St D (Maximum Delay)
Pí.j
2. There exists {pr (pr)re(.....D) such that for all (q,j,t), it holds that F [u.tt S Pt-r for
1= (Uniform Bound for Components' Delays)
With these, we make a statement the error in the view. In particular it holds that,
E of - x nn Ur2ol [.999] S L
(6)
for some > 0. This bound comes from Section A.B.6 in Nadiradze et al. (2020). Thus, the view is taken such that all components read after the last averaging step then bound the error as given.
A.2 PROOF OF MAIN CONVERGENCE THEOREM
Recall the major iterations žÿ is defined as the value of the parameters after an averaging step has taken place, which is of course well-defined as every GPU will have the same of values for the parameters. The update to Tj can be written as,
1 Q
K,-1
-
Σ
V ((
3
2
-
ajii
t=
Where we define, ()()) as the vector of size whose i'ith components are the calculated stochastic gradient vector defined uit. with the rest of the components padded with zeros. We indicate the component chosen i(q. t) depends on the GPU and minor and major iteration, allowing for flexibility in the choice of block update (including the entire vector).
12

---

Under review as a conference paper at ICLR 2021
We ready prove the convergence Theorem. The structure of the proof will follow Zhou & Cong (2017), who derives the standard sublinear convergence rate for local SGD synchronous environment for nonconvex objectives.
We begin with the standard application of the Descent Lemma,
= - Eno agen ((of 1 En a, ((11 Now, since EV ((a ((t
(8)
-E [VV)( f(f ))
= ( V -
(
We now split the last term by the two cases and use equation 6,
E ( f(3))
E
V [ V (it (fty)] U12o 1 P ni U1o Thiad 41 11900)
(1. ViGin) fa,)) (nt U1zo
" ( Upzo 1 }
+E
$ ag BP
7i U1o0 [[
| ( ( [2,) 112 + E (f )12) P [nr U12o 175h0))
+2
and thus combining with equation 22 we get the overall bound.
-Z(,)(z)), f(
S - +
0g B
P
p[n, U1zo U120 4,
phigd
+ f(
(v 112
P (nn U1zo
(10)
(IIV
(1) 112)
PP
n
U120 Tiy
KJ )2 + \ ( vo. (v.
It can be seen from this expression that we must have,
12i.a 1 +
P n. Ul2o 1, for some d > to achieve descent in expectation for iteration j for sufficient small stepsizes.
(11)
Since we are taking the sum of such iterations, we must have, ultimately,
Dk, 1 0 O'ia. IP ni Uroo
K, -1
ajiin (QK;
V
+ E q=
1.09 Ik- ajao [P [n Lij
a E
(f
6,
(12)
with Σ 6, 2 (Tx) - Sm, where recall that fm is lower bound on in order to achieve asymp-
7=
totic convergence. The standard sublinear SGD convergence rate is recovered with any choice with aj.t. = θ and thus ultimately 8, = -
Let us now consider the quantity [n Utso ung3 a in more detail and study how the nature of the concurrency affects the possibility and rate of convergence.
In particular notice that,
Ta < - Pt-r
for 1 > / In general of course expect this quantity increase as is closer
Consider two extreme cases: if there is always only one SG iteration for all processes for all major iterations j. i... K₃- L, any delay means reading vector in memory before the last major iteration,
13

---

Under review as a conference paper at ICLR 2021
and thus the probability of delay greater than must be very small in order to offset the worst possible ascent.
On the other hand, if in general K, >> 7, then while the first minor could be problematic
level depending on the probability of the small delay times, for t > clearly the vector ug satisfies equation 6.
Thus we can sum up our conclusions in the following statements:
1. Overall, the higher the mean, variance, and thickness of the tails of the delay, the more problematic convergence would be,
2. The larger the quantity of local iterations each GPU performs in between averaging, the more likely favorable convergence would occur.
The first is of course standard and obvious. The second presents the interesting finding that if you running Hog SG iterations on local shared memory, performing local SGD with a larger gap in time between averaging results in more robust performance for local SGD.
This suggests a certain fundamental harmony between asynchronous concurrency and local SGD, more "aggressive" locality, in the sense of doing more local updates between averaging, coincides with expected performance gains and robustness of more "aggressive" asynchrony and concurrency, in the sense of delays in the computations associated with local processes.
In addition, to contrast the convergence in regards to the block size, clearly the larger the block the faster the overall convergence, since the norms of the gradient vectors appear. interesting possi- bility to consider is if process can roughly estimate or predict when averaging could be triggered, robustness could be gained by attempting to do block updates right after an expected averaging step, and full parameter vector updates later in the major iteration.
A.3 CONVERGENCE SIMPLER CASE
In reference to the classic local SGD theory in particular Stich (2018) for the strongly convex case and Zhou & Cong (2017) for the nonconvex case, we consider the simpler scenario wherein j(q.j.t) [n] and u = xr 9-9 with s 2 0 for all o i.e., at no point are local updates computed gradients evaluated model components existing memory prior the last averaging step. We shall see the local asynchrony introduces a mild adjustment in the constants in the strongly convex case, relative to the classic result, and results in no change whatsoever the nonconvex case.
a,
A.3.1 STRONGLY CONVEX CASE
The proof of convergence will be based on Stich (2018), the synchronous case.
The formalism of the argument changes Algorithm 4. Note that this is functionally the same, and simply the concept of major iterations is dispensed with, except to define Kj.
Initialize 29 for all g for t. = 1,.... T do for all q
Let = -/-1 01.9 VS(1))
(tMD Σソ=1 K
0) for some J then
Q
Let Grt = 0
Σ
z
9=1
The only change in the procedure is that the stochastic gradients computed evaluated at vector uf. so we shall see how the convergence results contrasts with Stich (2018) for synchronous averaging when computations performed in this manner.
14

---

Under review as a conference paper at ICLR 2021
Let,
31 1 Σ
8=
Q Σ X
2
()()))
9: Q > 11
Vf(z?),
9: Σ
& Vf(())
9: Q E 2 vf(())
We have, as in the proof of Lemma 3.1 Stich (2018)
|1 x=1 = Jt 0tgt 1=2 = | 1
x² osgell + +ff - -gell
(13)
+2a (3x xx' arrr Gc- gt)
Continuing,
|| x² -a 212 ||x x² 1| + at 11 - 20 (3. x², 99))
= -1a - x² 22 + a
Q ΣØ=
- 20, E (ō+ 2/ + 1 x², vf((e)
18g x² x=11 + q - [V/ - Vf(x>)]] )|2
201 29 (0) x x'v\\(())) - 201 >g 1 (Tt 0/1 V f(()))
Using Young's 's inequality and I-ssmoothness,
-2 - 0/ ( 2 - 2/ 1/ 1 vf
27
21 R. - + [V(())) (V())) - f=(i))|
2L - + fr)
Applying this to the above estimate of || x² - angell., we get,
| x² -ggel 2 < |6: - =1 2n.1. Σ |, 0/11
Q
+
20c
2 - (arL 2) (S(of) 1*) |al1 xx 112)
Let 04 S 1 so (arL
- 1) 5 4. By the convexity of [f((x)) - f(x))( + $1 - 112.
2a:
~g=1 (d(f())) - f*)
111 =²
Q
< 201
Q Σ q=1
- f*) - ~ - x² 133)
+20 9= (10g - = + 2u||i - x 12)
Putting this in equation 13 and taking expectations, we get,
E| Pr41
x=1 < (1 μa, |3 3, xx 112 + + 9. 9 12
- (f) f*) 20,
Q Σ || uf 112
(14)
2/ ΣΦ (1128 - x
l1
+ 20lli8
- x3(13)
By Assumption 2.1, we have,
Q
(f(Co) - vf(13)) 1 0²
E 9. = E
(15)
Q
We have that,
E 1106 x < 9=1 ||0 - 11
I === 11-1 E. 1-7 a, (
(16)
I an aTQ VoQTV/GG
and similarly,
0 |1 x
S 0 m==
E. a ((
=-
(17)
S QQ2TG²
15

---

Under review as a conference paper at ICLR 2021
Letting index to be such that t to H max(Kj) when averaging takes place, ie. Fto 2%
for all g, we have,
E
2/12
4
E 2i + / Tto
(Tt - Tto r+o)ll
-=1
<
E [1o] - 2/ + | Ito (3x 2t,) )1²]]
1-
2
E 2-==1
Elja 12 + GG2
(18)
Q
5 2g Hai E. / (x1)]l 2apTTG
S 2mm1 11 G2 al G G22
S 88 a2 + T0
where we use E||X 2 = E | - || || and equation to go from the third to the fourth
line.
Finally, putting equation 15, equation 18, equation 16 and equation 17 into equation 14 we get that,
E T++1 x= < (1 - p(a) ) b4 x x=1 o 20
-a. - + 16a
2 / + + + 2L)
+ 2
Finally, using Lemma 3.4 Stich (2018), we obtain, with a > max(16k, H) for x. = L//s and Wy = (a + t)3
Ef
Σ e
ErD wax! f
QSa
q=1
I na²
|
- x 1|2 + 4T(T+2a) (0) + =vTG))
(19)
25f
USt
2
+ 3T
206T
(16L + 2(μ + +22
which simplifies to, using E2/11120 200 - x² I 2G,
E
9= Σ :=
T- waxz - f
qBq
0 aQT + NQT
0² +0
Tvn
G
(20)
nT
+0
[v((x+HH) MT²
H|
G+0
KH
+
(x+2L)
+H
G2
NT
NT
A.3.2 NONCONVEX CASE
This proof will again follow Zhou & Cong (2017). In this case the step-sizes (ari: L, 4)) are inde- pendent of and ie., they are simple {a,}. Thus,
K,-1
Fz+1 =
J Σ
aj ((1g))
And thus,
[(t++)) - < < 1=
Σkj
aj 0)0
(21)
+ 10 Ex ag (((."))
K2
Now, since EVf(o8a) -f(of'
-E(V)((E,) ()
= + < (1 2 -
vf(2))11
(22)
-2,11
We now continue the proof along the same lines in Zhou & Cong (2017). In particular, we get
Ellog - - < 22330² + ta |V
Let us define K max and K min; {K)).
16

---

Under review as a conference paper at ICLR 2021
We now have, Σ 00
E B(V((T)) {)(0))) 5
[K+1)a;
K 1 [+)))
1. 1k (1(
Ei=o K-1
E|
f(el )|2 + 122030" (2R (1)))((-)))
Similarly, it also holds that,
K,-1 ag ((0
LK30302
LK
K
Σ 2 Q t=o
2Q
2
And so, finally,
Ef( f(z,)( S (K+1)ay
(1-
L2a L2a3R(R-1)
La,
/f
2(K+1)
K+1)
9 1
-LasK)
E Ei=l E (
2
LKZ0302
2Q
Now, if/once ay is small enough such that,
L2a3( 1)(
12
+ LaaK
2
then the second term above disappears, and the result is exactly the same as Zhou & Cong (2017)-
Specifically, if - 2 a.
EΣ a, [(,
2(f(E))-F")
Ei (K-1+8) D5-1
+ + Eie (K
LRa
L(2K
1) (- 1)0g
?
6
B APPENDIX B: AN ARGUMENT FOR INCREASED GENERALIZATION ACCURACY FOR LOCAL SGD
B.I WIDE AND NARROW WELLS
In general it has been observed that whether local minimizer is shallow deep, or how "flat" it is, seems to affect its generalization properties Keskar et al. (2019). Motivated by investigating the impact of batch size on generalization Dai & Zhu (2018) analyzed the generalization properties of SGD by considering the escape time from a "well", i.c., a local minimizer in the objective landscape, for a constant stepsize variant of SGD by modeling as an overdamped Langevin-type diffusion process,
dx, = - + 2edW,
In general "flatter" minima have longer escape times than shallow ones, where the escape time is the expectation in the number of iterations (detined as continuous parameter in this sense) until the iterates leave the well to explore the rest of the objective landscape. Any procedure that increases the escape time for flatter minima compared to shallower ones should, in theory, result in better generalization properties, as it is more likely then that the procedure will return an iterate that is in shallow minimizer upon termination.
Denote with indexes w for a "wide" valley local minimizer and n for a "narrow" value, which also corresponds to smaller and larger minimal Hessian eigenvalues, respectively.
The work Berglund (2011) discusses the ultimately classical result that as c - 0, the escape time from local minimizer valley satisfies,
E[re] C/e
and letting the constant H depend on the type of minimizer, it holds that that H., > Hn, i.c., this time is longer for wider valley.
We also have from the same reference.
Plre > sE -
17

---

Under review as a conference paper at ICLR 2021
B.2 AVERAGING
We now contrast two procedures and compare the difference in their escape times for shallow and wider local minimizers. One is the standard SGD, and in one we perform averaging every Ta time. In each case there are Q processors, in the first case running independent instances of SGD, and in the other averaging their iterates. We model averaging probabilistically as resulting in randomized initialization within the well, and thus the escape time is a sequence of independent trials of length
To with an initial point in the well, i.c., escaping at time Te means that there are Q
I= trials wherein none of the Q sequences escaped within Ta and then one of them escaped in the next set of Q trials.
For ease of calculation, let us assume that Ta = = = 2 where Te" and T are the calculated single process escape time from a wide and shallow well, respectively.
If any one of the local runs escapes, then there is nothing that can be said about the averaged point, so a lack of escape is indicated by the case for which all trajectories, while periodically averaged, stay within the local minimizer value.
Now consider that if averaging takes place, sum up the probabilities for the wide valley that they all escape after time 00
(i - 1)T time and, given that they do so, not all of them escape after it,
B B[Te"
S E
P(Te" w
(i 1)Ta) (1 (1- P(TT" > TallTe" > (i - 1)Ta) P)iaa
1=
26-11 1)
Ta?
1=
For the narrow well this is,
13 [
P(T > ITTa) (1 - P(Te" > TailTe" > (i 1) 1)5a
i= (0-0 (1 c 22)
Ta e22))
1))
The difference in the expected escape times satisfies,
E -el < i=l
00
-4-1) (1- (1-E-8)
(e 2Q( (1 (1-e -2-2 (i- 1)
(1-e-9)]] Ta
Recall that in the case of averaging, if escaping takes place between (i 1)Te and iTo there were no escapes with less that Ta for M processors multiplied by i - 1 times trials, and at least one escape between (i 1)T, and iT., i.c., not all did not escape between these two times.
The expected first escape time for any trajectory among Q from a wide valley, thus, is, E|ra.0]
< > (P(T"
Ta] ((-1) (1 P| > Ta] (
(1 e )ra
And now with averaging, the escape time from a narrow valley satisfies,
E(ra.") 2 Die (P(T"
> T.. (1 - P|7"" > ra Tal (rali -1))
1))
> Di e 2 - e
-2Q
2iQ )Ta 1)
With now the difference in the expected escape times satisfies,
Elra.0
< > 20 i=1
"-11 (1 (1- - 88
E (1 - E 219]] (i (i-11 + e- 11-10 (1 e- =-) To
It is clear from the expressions then that the upper bound for the difference is larger in the case of averaging. This implies that averaging results in greater difference between the escape times between wider and shallow local minimizers, suggesting that, on average if one were stop pro- cess of training and use the resulting iterate as the estimate for the parameters, this iterate would more likely come from a flatter local minimizer if it was generated with a periodic averaging pro- cedure, relative to standard SGD. Thus it should be expected, at least by this argument that better generalization is more likely with periodic averaging.
Note that since they are both upper bounds, this isn't a formal proof that in all cases the escape times are more favorable for generalization in the case of averaging, but a guide as to the mathematical intuition to how this could be the case.
18


Reviews:
[{"review_id": "vEzURI1vdb4", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a method to address the \"local scalability\" problem in decentralized SGD. The authors study existing data parallel approaches and building upon the limitations, they propose two approaches - a synchronous and asynchronous non-blocking methods which aim to utilize compute resources optimally and avoid using large batch sizes.\n\nI have a few comments:\n- In the introduction, the paper mentions problems of finite-sum minimization form but it is missing the regularizer terms. Is this intended? It is much more common to see finite-sum minimization optimization with l1/l2 regularizers to control model complexity. I am bit surprised if the authors did not consider this.\n\n- Degradation in accuracy upon increasing batch sizes is a popular problem and there has been lot of important work in this work (e.g. LARS [1], LAMB [2] to mention just a few). I don't see what the advantages of the proposed method are in comparison to these approaches which approach the problem differently but end up ultimately solving the large-batch accuracy issues. Can the authors comment this? on whether they investigated this empirically?\n\n- From what I see, the proposed method does not \"intelligently sample\" the data points based on some structure/theoretical observation/heuristics etc. Correct me if I mis-understood. If so, how does proposed approach compare with other methods which aim to construct mini-batches or sub-sets of data on local workers more intelligently? such as [3] or [4]. I feel these related works also can extend to distributed decentralized SGD well.\n\n- The scale of datasets is not large enough for distributed method. I would like to see experiments on datasets with larger # of data points, classes than what is currently presented.\n\n- Did the authors perform any experiments on dense vs sparse datasets to see how the methods perform? The non-uniform distribution of data on various workers in my opinion can affect the optimization a lot and it would be good to see the authors comment on this.\n\n- Table 2 is not convincing to me.\n   (a) What if we go larger than 256 batch size? How does the accuracy look like in that case?\n   (b) The gains are only marginal and don't seem significant. Did the authors perform any statistical significance tests or multiple random trials? If so, what was the variance of this experiment?\n\n- The paper obtains a convergence rate of 1/\\sqrt{T} based on what I understand? I am curious if the authors could comment on what assumptions need to be changed or what fundamentally stops the method from achieving a linear rate?\n\n- Organization of paper can be improved. Minor: equation numbers are missing. The Quality/Perf column in Table 1 is confusing - what to quantify \"ok\", \"good\", \"poor\"?\n\nI feel the paper does not meet the technical bar for an ICLR paper due to incomplete related work, unconvincing experiments. Proposed approaches do not seem very novel to me.\n\n\n[1] https://arxiv.org/pdf/1708.03888.pdf\n\n[2] https://arxiv.org/pdf/1904.00962.pdf\n\n[3] https://negative-dependence-in-ml-workshop.lids.mit.edu/wp-content/uploads/sites/29/2019/06/SMDL_ICML_2019_ND_Workshop.pdf\n\n[4] https://arxiv.org/pdf/1704.06731.pdf", "extra_scores": {}, "extra_text": {}}, {"review_id": "W-C5didaIv9", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper  proposes a class of  asynchronous local SGD by combining the local SGD with shared-memory based asynchronous gradient updates. Moreover, it proves that the proposed methods guarantee ergodic convergence for non-convex objectives, and achieves the classic sub-linear rate under standard assumptions. Some experimental results verify the efficiency of the proposed methods.  Unfortunately, I do not find Appendix of the paper, so I can not judge the contribution of this paper.  I hope the authors to upload the supplementary materials.  \nIn addition, because there are too many notations in this paper, it is easy to be confused. I hope the authors will introduce these notations in a table for readers.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1z4SokANabG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors argue that the mini-batch method and local SGD method suffers generalization performance degradation for large local mini-batch size. An asynchronous method is proposed to improve the generalization performance. A sublinear convergence rate is provided for the non-convex objective. As there are some missing definitions and little explanation of the proposed method, the reviewer finds the paper hard to read.\n\n1. The comparison shown in table 1 is problematic. When the local batch size is increased from 128 to 1024, the learning rate also needs to be scaled accordingly. It is not surprising that we observe performance issue if we do not increase the learning rate. This makes the motivation of the proposed algorithm questionable.\n\n2. It is not clear to the reviewer about the intuition of why local asynchrony can mitigate the generalization issue. In particular, compared to local SGD, the asynchrony introduces additional staleness, which can hinder the convergence.\n\n3. What are the definitions of a^q and U^q? These two symbols are used in many places in the paper. But there are no definitions of them. And, what is s_j^q in Algorithm 1b?\n\n4. What is the motivation of having the process alternate between a full and a partitioned lock-free asynchronous gradient updates to the model $x^q$? It seems to the reviewer that you are switching between SGD and block coordinate descent. This can reduce computational complexity but worsen the convergence at the same time.\n\n5. Theorem 2.1 does not show any improvement by using more workers.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I think this paper has more positives than the reviews might indicate. And I do not share all the reviewers' concerns about the content of the paper. I think that there are a few concerns, though, that still suggest this paper should not be accepted as it is, when taken in conjunction with the concerns brought up by the reviewers.

On the positive side:

 - Asynchronous methods often give significant improvements, and the throughput benefits can even be seen here in Table 6.
 - The experiments are detailed with a lot of results comparing against many alternatives, including for ImageNet.

On the negative side:

 - The biggest concern I have with this paper is the scale of the experiments. This is supposedly about "distributed" SGD, but the largest-scale experiment was run on only two workstations, and many experiments were run in the S1 and S2 settings which don't seem to be distributed at all (run on a single workstation). That is, there's a mismatch between the scale at which these experiments were run and the scale at which people want to run distributed deep learning.
 - The theory seems to be only an incremental change to the standard local-SGD theory. The paper says "At a naive first glance, studying the convergence properties of locally asynchronous SGD would be an incremental to existing analyses for local SGD" but then it does not satisfactorily explain _why_ the approach is _not_ incremental. Not enough is done in the paper to explain why the analysis is not just a trivial combination of the local SGD with the standard approach to make an algorithmic analysis asynchronous. (Or, if the theoretical result _is_ incremental, the paper should make less of a big deal out of it.)
 - The description of the algorithm in Section 1.2 is confusing. I think it would benefit from being more concrete.

The paper should also compare against the paper "Asynchronous Decentralized Parallel Stochastic Gradient Descent" (Lian et al, 2017). It is actually not clear to me whether the method proposed here is a subset (or superset) of the method described in that paper, but they seem _very_ similar.
Decision: Reject