Year: 2020

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, communicationcompression, 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.

heading: 1 INTRODUCTION
text: In this paper, we consider the classic problem of minimizing an empirical risk, defined simply as min x∈Rd ∑ i∈[I] fi(x), (1) where d is the dimension, x ∈ Rd denotes the set of model parameters, [I] is the training set, and fi(x) : Rd → R is the loss on the training sample i ∈ [I]. Stochastic gradient descent (SGD) (Robbins & Monro, 1951) is an extremely popular iterative approach to solving this problem: xk+1 = xk − αk∇fBk(xk), (2) where∇fBk(xk) = 1|Bk| ∑ i∈Bk ∇fi(xk) is the sum of gradients computed over samples, typically selected uniformly and randomly as a minibatch Bk ⊆ [I], and αk is the learning rate at iteration k.

heading: 1.1 BACKGROUND ON DECENTRALIZED DATA-PARALLEL SGD
text: For better or 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 is minibatch SGD (MB-SGD) (Bottou (2012)). In a distributed setting with decentralized workers q ∈ [Q], it follows the iteration
xk+1 = xk − αk 1
Q Q∑ q=1 ∇fBqk , (3)
where Bqk ⊆ [I] is a local minibatch selected by worker q ∈ [Q] at iteration k. This strategy is straightforward to scale in a data-parallel 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 a 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)):
xqj,t+1 = x q j,t − αj,t∇fBqj,t , 0 ≤ t < Kj ; x q j+1,0 =
1
Q ∑ q xqj,Kj , (4)
where xqj,t denotes the local model at worker q ∈ [Q] after j synchronization rounds followed by t local gradient updates and Bqj,t is the local minibatch sampled at the same iteration. Kj denotes the number of local gradient update steps before the jth synchronization. Essentially, workers run SGD without any communication for several local steps, after which they globally average the resulting local models. This method is intuitively easy to scale, since it reduces the frequency of the communication. Recently, a variant called post local SGD (PL-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.
Method Bloc Train Loss Train Acc. Test Loss Test Acc Time (Sec) Quality/ Perf.
MB-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-SGD 128 0.018 99.69 0.245 92.98 1603 Good PL-SGD 1024 0.154 94.69 0.381 87.81 1159 Poor
Bloc , where Bloc = 128, Q is
the number of workers, 2 here, and α0 = 0.1. In PL-SGD, we average the model after each gradient update for first 150 epochs and thereafter averaging frequencyK is set to 16 as in Lin et al. (2020); other HPs are identical to theirs. The listed results are average of 3 runs with different seeds.
with PL-SGD. Clearly, these methods can not tolerate a larger Bloc, though the GPUs can support them. This shortcoming of the existing methods in harnessing 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.
Notice that, here our core target is maximally harnessing the local data-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 a large aggregated global batch size with a relatively small Bloc. For example, refer to the performance of MB-SGD and PL-SGD as listed in Table 1 of Lin et al. (2020). Notice that with 16 GPUs, each with Bloc = 128, thus totaling the minibatch size as 2048, identical to the one with 2 GPUs each with Bloc = 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).

heading: 1.2 LOCALLY-ASYNCHRONOUS PARALLEL SGD
text: Now, consider an implementation scheme as the following:
1. In a decentralized setting of L-SGD, i.e. wherein each worker q ∈ [Q] has a local model xq undergoing local SGD updates as described earlier, multiple local concurrent processes u ∈ Uq share the model xq . Processes u ∈ Uq perform asynchronous concurrent gradient updates locally. 2. The workers average their models whenever any one of them would have had at least Kj local shared updates, where Kj is as that in Equation 4. The averaging is performed asynchronously and in a non-blocking way by the (averaging-) processes aq on behalf of each worker q ∈ [Q].
Essentially, the decentralized workers run shared-memory-based asynchronous SGD locally and periodically synchronize in a totally non-blocking fashion.
More formally, consider Algorithm 1. The model xq on a GPU q ∈ [Q] is shared by the processes p ∈ P q = {{aq}∪Uq} locally. The processes p ∈ P q also maintain a shared counter Sq , initialized to 0. The operation read-and-inc implements an atomic (with lock) read and increment of Sq , whereas, read provides an atomic read. Sq 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 ∈ Uq asynchronously and lock-freely update xq with
gradients computed over a non-blocking, potentially inconsistent, snapshot va,q of xq , essentially going Hogwild! (Recht et al. (2011)), see Algorithm 1a.
1 Initialize s = 0; 2 while s ≤ T do 3 vu,q[i] := xq[i], ∀ 1 ≤ i ≤ d; 4 s := read-and-inc(S); 5 Compute∇fBqs (v
u,q); 6 xq[i] −= αs∇fBqs (v
u,q)[i], ∀ 1 ≤ i ≤ d;
(a) Local asynchronous gradient update by process u ∈ Uq .
1 Initialize scur = spre = |Uq|, j = 0; 2 while scur ≤ T do 3 scur := read(S); Compute j corresponding to scur; 4 if scur − spre ≥ Kj then 5 va,qj [i] := x
q[i], ∀ 1 ≤ i ≤ d; 6 Synchronize across ar , r ∈ [Q] \ {q} to compute
vj := 1 Q ∑ q∈[Q] v a,q j ;
7 Compute ∆vqj = vj − v a,q j ; spre := scur; 8 xq[i] += ∆vqj [i], ∀ 1 ≤ i ≤ d; j = j + 1;
(b) Asynchronous non-blocking in-place averaging.
Algorithm 1: Locally-asynchronous Parallel SGD (LAP-SGD)
The process aq , which performs averaging for the worker q ∈ [Q], concurrently keeps on atomically reading Sq , see Algorithm 1b. As soon as it notices an increment Kj in Sq , i.e. xq got concurrently updated with Kj number of gradients , it takes a non-blocking snapshot v a,q j of x
q and synchronizes with ar of peers r ∈ [Q]/q to compute the average vj of the snapshots. Thereafter, aq adds the difference of the average with the snapshot va,qj to the model x
q without blocking the concurrent asynchronous local gradient updates. We call this method locally-asynchronous 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 describe 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 increasing the size of Bloc but by concurrently computing many minibatch gradients. Evidently, LAP-SGD provides speed-up without losing the quality of optimization in comparison to the baseline.
Recently, Kungurtsev et al. (2019) presented a 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 computation cost by means of restricted backpropagation without necessarily losing on optimization quality. Their method is limited to a centralized sharedmemory setting. Moreover, aiming to establish
convergence under non-smoothness assumption, they ensure write consistency under a model-wide lock. Having designed our asynchronous parallel SGD, it inspires us to adapt the partitioned gradient update strategy to our lock-free decentralized setting.
More specifically, building on LAP-SGD, we consider locally partitioned gradient computation along with asynchronous lock-free updates. Essentially, we partition the model xq to {xqi(u)} for u ∈ Uq , i(u) ∩ i(w) = ∅, ∀u,w ∈ Uq (i.e., non-overlapping block components of the vector x). With that, a partitioned gradient computation
will amount to computing ∇i(u)fBqs (vq,u), the minibatch gradient with respect to the partition xqi(u) at line 5 in Figure 1a. Accordingly, the update step at line 6 in Algorithm 1a transforms to xq[i] −= αs∇fBqs (vq,u)[i], ∀ i ∈ 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-partitionedasynchronous parallel SGD (LPP-SGD) as described below.
1. Processes u ∈ Uq maintain a process-local variable last iter which can take two values PARTITIONED and FULL. Each u ∈ Uq initializes last iter as FULL. 2. While s ≤ Tst, each process u ∈ Uq performs LAP-SGD updates as lines 3 to 6 of Algorithm 1a. 3. If Tst < s ≤ T , each process u ∈ Uq performs
(a) a partitioned gradient computation and update: xq,u[i] −= αs∇fBqs (vu,q)[i], ∀i ∈ i(u) if last iter = FULL, and sets last iter = PARTITIONED. (b) an LAP-SGD update if last iter = PARTITIONED, and sets last iter = FULL.
Essentially, after some initial stabilizing epochs each process u ∈ Uq alternates between a full and a partitioned lock-free asynchronous gradient updates to the model xq . Our experiments showed that Tst = T 10 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.

heading: 2 CONVERGENCE THEORY
text: 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 particular the local stochastic gradient evaluations at delayed lock-free Hogwild!-like parameter vectors. However, there is one significant difference that presents a 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 it is impossible to place a reasonable bound on the accuracy of these gradient evaluations relative to what they “should be” in order to achieve descent.
1 Initialize x̄0 = xq0 for all q; 2 for j = 1, ..., J do 3 for all q do 4 Set xq,j0 = x̄j ; 5 for t = 1, ...,Kj do 6 Let xq,jt = x q,j t−1 −
αj,t,q∇̃(i(j,t,q)f(vq,jt );
7 Let x̄j+1 = 1Q Q∑
q=1
xq,jKj ;
Algorithm 2: Iterations of the view x̄j .
In order to present a convergence rate result, we need to define an anchor point on which we can consider convergence 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 occurs potentially varying with system-dependent conditions, while the averaged iterates are what is important to consider for convergence.
We seek to define the major iteration x̄j 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, x̄j is a theoretical construct, i.e., it may
not exist at any particular GPU’s memory at any moment in time. Let sqj := scur − |Uq| be the current state of the shared counter before the jth synchronization round at the GPU q, then x̄j is defined as xq
sqj + ∆vj where x q sqj is the state of the model for GPU q when va,qj was saved and made available for averaging for “major iteration” j. Thus although de facto averaging could have taken place after a set of local updates in time, these local updates correspond to updates after iteration j conceptually. This makes x̄j properly correspond to the equivalent iterate in Zhou & Cong (2017).
With that, we consider a sequence of major iteration views {x̄j} with associated inter-averaging local iteration quantities Kj and local views {vq,jt } at which an unbiased estimate of the (possibly partitioned) gradient is computed, with 0 ≤ t < Kj as well as the local model in memory {xq,jt }. The partition, which could be the entire vector in general, is denoted by i(j, t, q). As each GPU has its own corresponding annealed stepsize, we denote it in general as αj,t,q 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 gradient, a bounded second moment, gradient Lipschitz continuity, and lower boundedness of f . Assumption 2.1. 1. It holds that ∇̃if(vq,jt ) satisfies, independent of i, E [ ∇̃if(vq,jt ) ] =
∇if(vq,jt ); E [∥∥∥∇̃if(vq,jt )−∇if(vq,jt )∥∥∥2] ≤ σ2; E [∥∥∥∇̃if(vq,jt )∥∥∥2] ≤ G.
2. f is Lipschitz continuously differentiable with constant L and is bounded below by fm.
We must also define some assumptions on the probabilistic model governing the asynchronous computation. As these are fairly technical we defer them to the appendix.
Theorem 2.1. Given assumption 2.1, it holds that, 1 Q ∑J j=1 ∑Q q=1 ∑Kj−1 t=0 [αj,t,qC1 − α2j,t,qC2]E ∥∥∥∇i(j,t,q)f(vq,jt )∥∥∥2 + 1Q ∑J j=1 ∑Q q=1 ∑Kj−1 t=0 [αj,t,qC3 − α2j,t,qC4]E
∥∥∇i(j,t,q)f(x̄j)∥∥2 ≤ f(x̄0)− fm
(5)
where C1, C2, C3, and C4 depend on L, B and probabilistic quantities defining the asynchronous computation (see Appendix. Thus there exists a set of such constants such that if αj,t,q = Θ ( 1√ J ) then Algorithm 2 ergodically converges with the standard O(1/ √ J) rate for nonconvex objectives.
Proof Summary: The proof follows the structure of the ergodic convergence proof of K-step local SGD given in Zhou & Cong (2017), wherein at each round of averaging there are QKj total updates to the model vector associated with the Q GPUs and Kj 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 is 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 vq,jt,i = x q,j s,i for s < 0 (i.e., the stochastic gradients are taken, due to local asynchrony, at model vectors with components which existed in 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 a “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 to have a 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 to 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 is 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 C4.

heading: 3 IMPLEMENTATION DETAILS AND NUMERICAL RESULTS

heading: 3.1 EXPERIMENTAL SET-UP
text: Decentralized training. We evaluate the proposed methods LAP-SGD and LPP-SGD comparing 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-16x8 (Zagoruyko & Komodakis (2016)) for the 10-/100-class image classification tasks on datasets CIFAR-10/CIFAR-100 (Krizhevsky (2009)). We also train RESNET-18 for a 1000-class classification problem on IMAGENET (Russakovsky et 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 a seeded
random permutation based on epoch-order. To this effect we use a shared-counter among concurrent process u ∈ Uq in asynchronous methods. Thus, our data sampling is i.i.d.
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 Intel(R) Xeon(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 cross-GPU/cross-machine communication we use NCCL (NCCL (2020)) primitives provided by Pytorch. MB-SGD is based on DistributedDataParallel 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 a CNN, the autograd package of Pytorch allows a 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.
Locally-asynchronous Implementation. One key requirement of the proposed methods is to support a non-blocking synchronization among GPUs. This is both a 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-processes. The child-processes work as u ∈ Uq, ∀q ∈ [Q] to compute the gradients and update the model. Concurrently, the parent-process, instead of remaining idle as it happens commonly with such concurrency models, acts as the averaging process aq ∈ P q, ∀q ∈ [Q], thereby productively utilizing the entire address space occupied over the GPUs. The parent- and child-processes share the iteration and epoch counters. Notice that, here we are using the process-level concurrency which is out of the purview of the thread-level global interpreter lock (GIL) (Python (2020)) of python multi-threading framework.
Hyperparameters (HPs). Each of the methods use identical momentum (Sutskever et al. (2013)) and weight-decay (Krogh & Hertz (1991)) for a 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 to 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, a grid search (Pontes et al. (2016)) suggested that for LPP-SGD warming up the LR up to 1.25× of the warmed-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 : |Uq|, B : Bloc, 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-benchmark presents the mean of 3 runs unless otherwise mentioned.
Concurrency on GPUs. We allocate the processes on a 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 RESNET20/CIFAR-10 by LAP-SGD on the setting S1.
Asynchronous Averaging Frequency. Following PL-SGD, as a 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 a K < Q in LAP-SGD and LPP-SGD may not necessarily increase the averaging rounds j in aggregation. Intuitively, in a locally-asynchronous setting, along with the nonblocking (barrier-free) synchronization among GPUs, the increment events on the shared-counter S would be “grouped” on the real-time scale if the processes u ∈ Uq do not face delays in scheduling, which we control by allocating an optimal number of processes to maximally utilize the compute
resources. For instance, Table 5 lists the results of 5 random runs of RESNET-20/CIFAR-10 training with B = 128 and U = 6 with different combinations of K and P over S1. This micro-benchmark 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 PL-SGD.
Scalability. Table 6 presents the results of WIDERESNET16x8/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 PL-SGD marginally outperform MB-SGD, (b) interestingly, increasing Bloc 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 ∼12% 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 on the baseline generalization accuracy.
Other CIFAR-10/CIFAR-100 Results. Performance of the proposed methods in comparison to the baselines for other training tasks on CIFAR-10/CIFAR-100 datasets are 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 comprehensively evaluated the proposed methods on CIFAR-10/CIFAR-100, here we present their performance on 1000-classes Imagenet dataset.
0 20 40 60 80 Epochs
(1)
(2)
(3)
(4)
(5)
(6)
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 IMAGENET with BS up to multiple thousands. Other system-dependent constraint that our considered setting faces is that there is hardly any leftover compute resources for us to exploit in the local setting of a worker. Yet, we see for RESNET-18, see Table 10, that LAP-SGD improves on generalization accuracy of the baseline with speed-up.
LR Tuning strategy. It is pertinent to mention that the existing techniques, such as LARS (You et al. (2017)), which provide an adaptive LR tuning strategy for large minibatch settings over a large number of GPUs, wherein each worker locally processes a small minibatch, are insufficient in the case Bloc is increased. For example, see Table 11 which lists the
average performance of 5 runs on the setting S1 for Q = 2 for training RESNET-20/CIFAR-10 using the compared methods combined with LARS with η = 0.001 (You et al. (2017)). We scale the LR proportionately: α0 × B×QBloc , where Bloc = 128, Q is the number of workers, 2 here, and α0 = 0.1. Evidently, LARS did not help MB-SGD and PL-SGD in checking the poor generalization due to larger B.

heading: 3.3 ON THE GENERALIZATION OF THE PROPOSED METHODS
text: Let us comment on a theoretical basis of the remarkable performance in terms of generalization error of our methods. In Lin et al. (2020), the model of SGD algorithms as a form of a Euler-Maruyama discretization of a 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 as 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) 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 a SDE. Let us recall three facts,
1. 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 a mini-batch gradients as 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 of 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 to the i.i.d. noise that appears in a discretized SDE.

heading: 4 RELATED WORK
text: In the previous sections we cited the existing literature wherever applicable, in this section we present a brief overview of closely related works and highlight our novelty. In the shared-memory
setting, HOGWILD! (Recht et al. (2011)) is now the classic approach to implement SGD. However, 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 variants which targeted specific system aspects of a multi-core machine. For example, Buckwild! (Sa et al. (2015)) proposed using restricted precision training on a CPU. Another variant, called HOGWILD!++ (Zhang et al. (2016b)), harnesses the non-uniform-memory-access (NUMA) architecture based multi-core computers. In this method, threads pinned to individual CPUs on a multi-socket mainboard with access to a 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 a ring graph of thread-clusters, further, it is a token based procedure where in each round only two neighbours synchronize, whereas in LAP-SGD it is all-to-all, (b) in HOGWILD!++ each cluster maintains two copies of the model: a locally updating copy and a 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 on a ring of workers eventually “comes back” to itself thereby 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 generalization 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-clusters to concurrent processes on GPUs in LAP-SGD, the latter uses a dedicated process that performs averaging without disturbing the local gradient updates 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.
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 simultaneously averaged when sequential computation for multiple iterations happen locally. They showed by limited experiments that it reduced the communication overhead in a 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 et al. (2019), however, unlike them we do not use locks and our implementation setting is decentralized, thus scalable.

heading: 5 CONCLUSION
text: Picking from where Golmant et al. (2018) concluded referring to their findings: “These results suggest that we should not assume that increasing the batch size for larger datasets will keep training times manageable for all problems. Even though it is a natural form of data parallelism for largescale optimization, alternative forms of parallelism should be explored to utilize all of our data more efficiently”, our work introduces a fresh approach in this direction to addressing the challenge.
In our experiments, we observed that the natural system-generated noise in some cases effectively improved the generalization accuracy, which we could not obtain using the existing methods irrespective of any choice of seed for random sampling. The empirical findings suggest that the proposed variant of distributed SGD has a perfectly appropriate place to 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-parallelism. The asynchronous averaging protocol makes LAP-SGD and LPP-SGD specially attractive to settings with large number of workers.
There are a 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 become 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)).

heading: A APPENDIX A: CONVERGENCE THEORY

heading: A.1 PROBABILISTIC ASSUMPTIONS GOVERNING THE ASYNCHRONOUS COMPUTATION
text: Now let us discuss the formalities of the asynchronous computation. We consider that the presence of local HogWild-like asynchronous computation introduces stochastic delays, i.e., at each stochastic gradient computation, the set of parameters at which the stochastic gradient is evaluated is random, it follows some distribution. Thus, considering that, in the general case,
vq,jt,i ∈ ∪k∈{0,...,j}{x q,k s,i }s∈{0,...,t}
we can now define a probability that this parameter view block is equal to each of these potential historical parameter values. To this end we define It,i,q,js,k as the event that block i in the view for GPU q at major iteration j and minor iteration t is equal to the actual parameter xq,ks,i , and p t,i,q,j s,k is its probability. Now, vq,jt,i could be, e.g., x q,j−1 s,i for some s ∈ {0, ...,Kj−1}, i.e., it could have been evaluated at a parameter before the last averaging took place.
In the nonconvex setting, it would be entirely hopeless to bound ‖xq,j−1s,i − v q,j t,i ‖ in general, in this case we can simply hope that the objective function decrease achieved by iterations with a gradient computed after an 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 xq,j−1,i = x q,j−1 Kj−1−1,i, x q,j −2,i = x q,j−1 Kj−1−2,i, etc., and then pt,i,q,j−1,j correspondingly. We can extend this analogously to delays from before two averaging steps, etc. Note that with this notation, pt,i,q,jl,j is well defined for any l ≤ t, l ∈ Z, of
course as long as |l| ≤ j−1∑ k=0 Kk.
In order to derive an expected decrease in the objective, we need to bound the probability of an increase, which means bounding the probability that the view is older than the previous averaging, which can be bounded by a bound on the probability that a particular read is more than some number τ iterations old. We thus make the following assumptions,
Assumption A.1. It holds that,
1. pt,i,q,jl,j = 0 for l ≤ t−D (Maximum Delay) 2. There exists {pτ}τ∈{1,...,D} such that for all (q, j, t), it holds that P [ ∪iIt,i,q,jl,j ] ≤ pt−τ for
l = t− τ (Uniform Bound for Components’ Delays)
With these, we can make a statement on the error in the view. In particular it holds that, E [∥∥∥vq,jt − xq,jt ∥∥∥ | ∩i ∪l≥0It,i,q,jl,j ] ≤ α2j,t,qB (6) for some B > 0. This bound comes from Section A.B.6 in Nadiradze et al. (2020). Thus, if the view is taken such that all components were read after the last averaging step then we can bound the error as given.

heading: A.2 PROOF OF MAIN CONVERGENCE THEOREM
text: Recall the major iterations x̄j 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 set of values for the parameters. The update to x̄j can be written as,
x̄j+1 = 1
Q Q∑ q=1 x̄j − Kj−1∑ t=0 αj,t,q∇̃i(q,j,t)f(vq,jt )  (7) Where we define, ∇̃if(vq,jt ) as the vector of size n whose i’ith components are the calculated stochastic gradient vector defined at vq,jt , with the rest of the components padded with zeros. We indicate the component chosen i(q, j, t) depends on the GPU and minor and major iteration, allowing for flexibility in the choice of block update (including the entire vector).
We are now ready to prove the convergence Theorem. The structure of the proof will follow Zhou & Cong (2017), who derives the standard sublinear convergence rate for local SGD in a synchronous environment for nonconvex objectives.
We begin with the standard application of the Descent Lemma,
f(x̄j+1)− f(x̄j) ≤ −〈∇f(x̄j), 1Q ∑Q q=1 ∑Kj−1 t=0 αj,t,q∇̃i(j,t,q)f(v q,j t )〉
+L2 ∥∥∥ 1Q∑Qq=1∑Kj−1t=0 αj∇̃i(j,t,q)f(vq,jt )∥∥∥2 (8) Now, since E∇̃i(j,t,q)f(vq,jt ) = ∇i(j,t,q)f(v q,j t ),
−E〈∇f(x̄j), ∇̃i(j,t,q)f(vq,jt )〉 = − 12 ( ‖∇i(j,t,q)f(x̄j)‖2 + E‖∇i(j,t,q)f(vq,jt )‖2 − E‖∇i(j,t,q)f(v q,j t )−∇i(j,t,q)f(x̄j)‖2 ) (9)
We now split the last term by the two cases and use equation 6,
E‖∇i(j,t,q)f(vq,jt )−∇i(j,t,q)f(x̄j)‖2 = E [ ‖∇i(j,t,q)f(vq,jt )−∇i(j,t,q)f(x̄j)‖2| ∩i ∪l≥0I t,i,q,j l,j ] P [ ∩i ∪l≥0 It,i,q,jl,j ] +E [ ‖∇i(j,t,q)f(vq,jt )−∇i(j,t,q)f(x̄j)‖2| ( ∩i ∪l≥0 It,i,q,jl,j )c] P [( ∩i ∪l≥0 It,i,q,jl,j
)c] ≤ α2j,t,qBP [ ∩i ∪l≥0 It,i,q,jl,j
] +2 ( ‖∇i(j,t,q)f(x̄j)‖2 + E‖∇i(j,t,q)f(vq,jt )‖2 ) P [( ∩i ∪l≥0 It,i,q,jl,j
)c] and thus combining with equation 22 we get the overall bound, −E〈∇f(x̄j), ∇̃i(j,t,q)f(vq,jt )〉 ≤ − 12 ( ‖∇i(j,t,q)f(x̄j)‖2 + E‖∇i(j,t,q)f(vq,jt )‖2 − α2j,t,qB ) P [ ∩i ∪l≥0 It,i,q,jl,j
] + 12 ( ‖∇i(j,t,q)f(x̄j)‖2 + E‖∇i(j,t,q)f(vq,jt )‖2 ) P [( ∩i ∪l≥0 It,i,q,jl,j
)c] ≤ − ( ‖∇i(j,t,q)f(x̄j)‖2 + E‖∇i(j,t,q)f(vq,jt )‖2 ) P [ ∩i ∪l≥0 It,i,q,jl,j
] + 12 ( ‖∇i(j,t,q)f(x̄j)‖2 + E‖∇i(j,t,q)f(vk,jt )‖2 ) + α2j,t,qB 2
(10)
It can be seen from this expression that we must have, P [ ∩i ∪l≥0 It,i,q,jl,j ] ≥ 1
2 + δ (11)
for some δ > 0 to achieve descent in a expectation for iteration j for a sufficient small stepsizes. Since we are taking the sum of such iterations, we must have, ultimately,
1 Q ∑Q q=1 ∑Kj−1 t=0 αj,t,q [ P [ ∩i ∪l≥0 It,i,q,jl,j ] − 12 − αj,t,q ( QKj + αj,t,qB 2 )] E‖∇i(j,t,q)f(vq,jt )‖2
+ 1Q ∑Q q=1 ∑Kj−1 t=0 αj,t,q [ P [ ∩i ∪l≥0 It,i,q,jl,j ] − 12 − α2j,t,qB 2 ] E‖∇i(j,t,q)f(x̄j)‖2 ≥ δ̂j
(12) with ∞∑ j=0 δ̂j ≥ f(x̄0) − fm, where recall that fm is a lower bound on f , in order to achieve asymptotic convergence. The standard sublinear SGD convergence rate is recovered with any choice with αj,t,q = Θ ( 1√ J ) and thus ultimately δ̂j = Ω ( 1√ J ) .
Let us now consider the quantity P [ ∩i ∪l≥0 It,i,q,jl,j ] in more detail and study how the nature of the concurrency affects the possibility and rate of convergence. In particular notice that, P [ ∩iIt,i,q,jl,j ] ≤ 1− pt−τ for l ≥ t− τ . In general of course we expect this quantity to increase as l is closer to t. Consider two extreme cases: if there is always only one SG iteration for all processes for all major iterations j, i.e.,Kj ≡ 1, any delay means reading a vector in memory before the last major iteration,
and thus the probability of delay greater than zero must be very small in order to offset the worst possible ascent.
On the other hand, if in general Kj >> τ , then while the first τ minor could be as problematic at a level depending on the probability of the small delay times, for t > τ clearly the vector vq,jt 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 a favorable convergence would occur.
The first is of course standard and obvious. The second presents the interesting finding that if you are running HogWild-type 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. An interesting possibility to consider is if a 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 on in the major iteration.

heading: A.3 CONVERGENCE - SIMPLER CASE
text: 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 i(q, j, t) = [n] and vq,jt,i = x q,j s,i with s ≥ 0 for all v q,j t,i , i.e., at no point are local updates computed at gradients evaluated at model components existing in memory prior to 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 in the nonconvex case.

heading: A.3.1 STRONGLY CONVEX CASE
text: The proof of convergence will be based on Stich (2018), the synchronous case.
The formalism of the argument changes to Algorithm 4. Note that this is functionally the same, and simply the concept of major iterations is dispensed with, except to define Kj .
1 Initialize xq0 for all q for t = 1, ..., T do 2 for all q do 3 Let xqt = x q t−1 − αt,q∇̃f(v q t )
4 if (tMOD ∑J j=1Kj = 0) for some J then
5 Let x̄t+1 = 1Q Q∑ q=1 xqt
The only change in the procedure is that the stochastic gradients are computed as evaluated at a vector vqt , so we shall see how the convergence results contrasts with Stich (2018) for synchronous averaging when computations are performed in this manner.
Let, x̄t = 1 Q ∑Q q=1 x q t ,
gt = 1 Q ∑Q q=1 ∇̃f(x q t ), ḡt = 1 Q ∑Q q=1∇f(x q t ), ĝt = 1 Q ∑Q q=1 ∇̃f(v q t ), g̊t = 1 Q ∑Q q=1∇f(v q t )
We have, as in the proof of Lemma 3.1 Stich (2018) ‖x̄t+1 − x∗‖2 = ‖x̄t − αtĝt − x∗‖2 = ‖x̄t − x∗ − αtg̊t‖2 + α2t ‖ĝt − g̊t‖2
+2αt〈x̄t − x∗ − αtg̊t, g̊t − ĝt〉 (13)
Continuing, ‖x̄t − x∗ − αtg̊t‖2 = ‖x̄t − x∗‖2 + α2t ‖̊gt‖2 − 2αt〈x̄t − x∗, g̊t〉
= ‖x̄t − x∗‖2 + α 2 t
Q ∑Q q=1 ‖∇f(x q t )‖2 − 2αtQ ∑Q q=1〈x̄t − v q t + v q t − x∗,∇f(vt)〉
= ‖x̄t − x∗‖2 + α 2 t
Q ∑Q q=1 ‖∇f(x q t )−∇f(x∗)‖2
− 2αtQ ∑Q q=1〈v q t − x∗,∇f(vt)〉 − 2αtQ ∑Q q=1〈x̄t − v q t ,∇f(vt)〉
Using Young’s inequality and L-smoothness, −2〈x̄t − vqt ,∇f(vt)〉 ≤ 2L‖x̄t − v q t ‖2 + 12L‖∇f(v q t )‖2
= 2L‖x̄t − vqt ‖2 + 12L‖∇f(v q t )−∇f(x∗)‖2 ≤ 2L‖x̄t − vqt ‖2 + (f(v q t )− f∗)
Applying this to the above estimate of ‖x̄t − x∗ − αtg̊t‖2, we get, ‖x̄t − x∗ − αtg̊t‖2 ≤ ‖x̄t − x∗‖2 + 2αtLQ ∑Q q=1 ‖x̄t − v q t ‖2
+ 2αtQ ∑Q q=1 (( αtL− 12 ) (f(vqt )− f∗)− µ 2 ‖v q t − x∗‖2 ) Let αt ≤ 14L so ( αtL− 12 ) ≤ − 14 . By the convexity of 1 4 (f(x)− f(x ∗)) + µ2 ‖x− x ∗‖2,
− 2αtQ ∑Q q=1 ( 1 4 (f(v q t )− f∗) + µ 2 ‖v q t − x∗‖2 ) ≤ − 2αtQ ∑Q q=1 ( 1 4 (f(x q t )− f∗) + µ 2 ‖x q t − x∗‖2
) + αt2Q ∑Q q=1 ( ‖vqt − x q t‖+ 2µ‖v q t − x q t‖2 )
Putting this in equation 13 and taking expectations, we get, E‖x̄t+1 − x∗‖2 ≤ (1− µαt)E‖x̄t − x∗‖2 + α2tE‖̊gt − ĝt‖2
−αt2 E(f(x̄t)− f ∗) + 2αtLQ ∑Q q=1 ‖x̄t − v q t ‖2
+ αt2Q ∑Q q=1 ( ‖vqt − x q t‖+ 2µ‖v q t − x q t‖2 ) (14)
By Assumption 2.1, we have,
E‖̊gt − ĝt‖2 = E‖ 1
Q Q∑ q=1 ( ∇̃f(vqt )−∇f(v q t ) ) ‖2 ≤ σ 2 Q (15)
We have that, ∑Q q=1 ‖v q t − x q t‖ ≤ ∑Q q=1 ‖v q t − x q t‖1
≤ ∑Q q=1 ∑t−1 s=max t−τ,t0 αs‖∇̃f(v q s)‖1
≤ αtQτ √ nG
(16)
and similarly, ∑Q q=1 ‖v q t − x q t‖2 ≤ ∑Q q=1 ∑t−1 s=max t−τ,t0 α 2 s‖∇̃f(vqs)‖2
≤ Qα2t τG2 (17)
Letting index t0 be such that t − t0 ≤ H := max{Kj} when averaging takes place, i.e. x̄t0 = x q t0 for all q, we have, 1 Q ∑Q q=1 E‖x̄t − v q t ‖2
= 1Q ∑Q q=1 E‖v q t − x q t + x q t − xt0 − (x̄t − xt0)‖2
≤ 2Q ∑Q q=1 E [ ‖vqt − x q t‖2 + ‖x q t − xt0 − (x̄t − xt0)‖2 ] ≤ 2Q ∑Q q=1 E‖x q t − xt0‖2 + 2α2t τG2
≤ 2Q ∑Q q=1Hα 2 t0 ∑t−1 s=t0 E‖∇̃f(xqs)‖2 + 2α2t τG2
≤ 2Q ∑Q q=1H 2α2t0G 2 ≤ H2α2t0G 2 + 2α2t τG 2 ≤ 8H2α2tG2 + 2α2t τG2
(18)
where we use E‖X −EX‖2 = E‖X‖2 −‖EX‖2 and equation 17 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‖x̄t+1 − x∗‖2 ≤ (1− µαt)E‖x̄t − x∗‖2 + α2t σ 2
Q
−αt2 E(f(x̄t)− f ∗) + 16α3tLH 2G2 + α2tτ √ nG
2 + 2(µ+ 2L)τα 3 tG 2
Finally, using Lemma 3.4 Stich (2018), we obtain, with a > max{16κ,H} for κ = L/µ, and wt = (a+ t) 2, Ef (
1 QSQ ∑Q q=1 ∑T−1 t=0 wtx q t ) − f∗ ≤ µa 3
2ST ‖x0 − x∗‖2 + 4T (T+2a)µST
( σ2
Q + τ √ nG 2 ) + 256Tµ2ST ( 16LH2G2 + 2(µ+ 2L)τG2
) (19) which simplifies to, using Eµ‖x0 − x∗‖ ≤ 2G,
Ef (
1 QSQ ∑Q q=1 ∑T−1 t=0 wtx q t ) − f∗
= O (
1 µQT + κ+H µQT 2
) σ2 +O ( τ √ n
µT
) G
+O ( τ √ n(κ+H) µT 2 ) G+O ( κH2+τ(µ+2L) µT 2 + κ3+H3 µT 3 ) G2
(20)

heading: A.3.2 NONCONVEX CASE
text: This proof will again follow Zhou & Cong (2017). In this case the step-sizes {α(j, t, q)} are independent of t and q, i.e., they are simple {αj}. Thus,
x̄j+1 = 1
Q Q∑ q=1 x̄j − Kj−1∑ t=0 αj∇̃f(vq,jt )  And thus,
f(x̄j+1)− f(x̄j) ≤ −〈∇f(x̄j), 1Q ∑Q q=1 ∑Kj−1 t=0 αj∇̃f(v q,j t )〉
+L2 ∥∥∥ 1Q∑Qq=1∑Kj−1t=0 αj∇̃f(vq,jt )∥∥∥2 (21) Now, since E∇̃f(vq,αt ) = ∇f(v q,α t ),
−E〈∇f(x̄j), ∇̃f(vq,jt )〉 = − 12 ( ‖∇f(x̄j)‖2 + E‖∇f(vq,jt )‖2 − E‖∇f(v q,j t )−∇f(xj)‖2 ) ≤ − 12 ( ‖∇f(x̄j)‖2 + E‖∇f(vq,jt )‖2 − L2E‖v q,j t − x̄j‖2
) (22) We now continue the proof along the same lines as in Zhou & Cong (2017). In particular, we get
E‖vq,jt − x̃j‖2 ≤ t2α2jσ2 + tα2jE t−1∑ s=0 ‖∇f(vq,js )‖2
Let us define K̄ = maxj{Kj} and K = minj{Kj}.
We now have, −αj ∑Kj−1 t=0 E〈∇f(x̄j), ∇̃f(v q,j t )〉 ≤ − (K+1)αj 2 ( 1− L 2α2jK(K̄−1) 2(K+1) ) ‖∇f(x̃j)‖2
−αj2 ( 1− L 2α2j (K̄+1)(K̄−2) 2 )∑K−1 t=0 E‖∇f(v q,j t )‖2 + L2α3jσ 2(2K̄−1)K(K̄−1) 12
Similarly, it also holds that,
L
2 ∥∥∥∥∥∥ 1Q Kj−1∑ t=0 αj∇̃f(vq,jt ) ∥∥∥∥∥∥ 2 ≤ LK2jα 2 jσ 2 2Q + LKjα 2 j 2 Kj−1∑ t=0 E‖∇f(vq,jt )‖2
And so, finally, Ef(x̄j+1)− f(x̄j) ≤ − (K+1)αj2 ( 1− L 2α2jK̄(K̄−1) 2(K+1) − LαjK̄ K+1) ) ‖∇f(x̃j)‖2
−αj2 ( 1− L 2α2j (K̄+1)(K̄−2) 2 − LαjK̄ )∑Q q=1 ∑Kj−1 t=1 E‖∇f(v q,j t )‖2 + L2α3jσ
2(2K̄−1)K̄(K̄−1) 12 + LK2α2jσ 2 2Q
Now, if/once αj is small enough such that,
1 ≥ L2α2j (K̄ + 1)(K̄ − 2)
2 + LαjK̄
then the second term above disappears, and the result is exactly the same as in Zhou & Cong (2017). Specifically, if 1− δ ≥ L2α2j
E ∑J j=1 αj‖∇f(x̄j)‖2∑J l=1 αj ≤ 2(f(x̃1)−F ∗) (K−1+δ) ∑J j=1 αj
+ ∑J j=1 LK̄α2jM∑J l=1 αl(K−1+δ) ( K̄ Q + L(2K̄−1)(K̄−1)αj 6 )

heading: B APPENDIX B: AN ARGUMENT FOR INCREASED GENERALIZATION ACCURACY FOR LOCAL SGD

heading: B.1 WIDE AND NARROW WELLS
text: In general it has been observed that whether a local minimizer is shallow or 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.e., a local minimizer in the objective landscape, for a constant stepsize variant of SGD by modeling it as an overdamped Langevin-type diffusion process,
dXt = −∇f(Xt)dt+ √
2 dWt In general “flatter” minima have longer escape times than shallow ones, where the escape time is the expectation in the number of iterations (defined as a 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 as 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 a 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 → 0, the escape time from a local minimizer valley satisfies, E[τe] = HeC/ and letting the constant H depend on the type of minimizer, it holds that that Hw > Hn, i.e., this time is longer for a wider valley.
We also have from the same reference, P[τe > sE[τe]] = e−s

heading: B.2 AVERAGING
text: 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 τa 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 it resulting in a randomized initialization within the well, and thus the escape time is a sequence of independent trials of length τa with an initial point in the well, i.e., escaping at time τe means that there areQ ⌈ τe τa ⌉ trials wherein none of the Q sequences escaped within τa, and then one of them escaped in the next set of Q trials.
For ease of calculation, let us assume that τa = 12E[τ w e ] = 2E[τne ], where τwe and τne 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 no averaging takes place, we sum up the probabilities for the wide valley that they all escape after time (i− 1)τ time and, given that they do so, not all of them escape after iτa. E[τwe ] ≤ ∑∞ i=1 P (τ w e > (i− 1)τa)Q(1− P (τwe > τai|τwe > (i− 1)τa)Q)iτa
≤ ∑∞ i=1 ( e− Q(i−1) 2 ( 1− e− Q 2 ) τai )
For the narrow well this is, E[τne ] ≥ ∑∞ i=1 P (τ n e > (i− 1)τa)Q(1− P (τne > τai|τne > (i− 1)τa)Q)(i− 1)τa
≥ ∑∞ i=1 ( e−2Q(i−1) ( 1− e−2Q ) τa(i− 1) ) The difference in the expected escape times satisfies,
E[τwe − τne ] ≤ ∑∞ i=1 [[( e− Q(i−1) 2 ( 1− e− Q 2 )) − ( e−2Q(i−1) ( 1− e−2Q ))] (i− 1)
+ ( e− Q(i−1) 2 ( 1− e− Q 2 ))] τa
Recall that in the case of averaging, if escaping takes place between (i− 1)τa and iτa there were no escapes with less that τa for M processors multiplied by i − 1 times trials, and at least one escape between (i− 1)τa and iτa, i.e., 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[τa,we ] ≤ ∑∞ i=1 ( P[τwe > τa](i−1)Q(1− P[τwe > τa]Mi)τai ) ≤ ∑∞ i=1 e − (i−1)Q2 (1− e− iQ 2 )τai
And now with averaging, the escape time from a narrow valley satisfies, E[τa,ne ] ≥ ∑∞ i=1 ( P[τne > τa](i−1)Q(1− P[τne > τa]Qi)τa(i− 1) ) ≥ ∑∞ i=1 e −2(i−1)Q(1− e−2iQ)τa(i− 1)
With now the difference in the expected escape times satisfies, E[τa,we − τa,ne ] ≤ ∑∞ i=1 [[ e− (i−1)Q 2 (1− e− iQ 2 )
−e−2(i−1)Q(1− e−2iQ) ] (i− 1) + e− (i−1)Q 2 (1− e− iQ 2 ) ] τa
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 a greater difference between the escape times between wider and shallow local minimizers, suggesting that, on average if one were to stop a process 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 procedure, 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 as to how this could be the case.

Review summaries:
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.