Mini-batch stochastic gradient descent (SGD) is state of the art in large scale distributed training. The scheme can reach a linear speed-up with respect to the number of workers, but this is rarely seen in practice as the scheme often suffers from large network delays and bandwidth limits. To overcome this communication bottleneck recent works propose to reduce the communication frequency. An algorithm of this type is local SGD that runs SGD independently in parallel on different workers and averages the sequences only once in a while. This scheme shows promising results in practice, but eluded thorough theoretical analysis.
    
 We prove concise convergence rates for local SGD on convex problems and show that it converges at the same rate as mini-batch SGD in terms of number of evaluated gradients, that is, the scheme achieves linear speed-up in the number of workers and mini-batch size. The number of  communication rounds can be reduced up to a factor of T^{1/2}---where T denotes the number of total steps---compared to mini-batch SGD. This also holds for asynchronous implementations.

 Local SGD can also be used for large scale training of deep learning models. The results shown here aim serving as a guideline to further explore the theoretical and practical aspects of local SGD in these applications. Stochastic Gradient Descent (SGD) BID29 consists of iterations of the form DISPLAYFORM0 for iterates (weights) x t , x t+1 ∈ R d , stepsize (learning rate) η t > 0, and stochastic gradient g t ∈ R d with the property E g t = ∇f (x t ), for a loss function f : R d → R. This scheme can easily be parallelized by replacing g t in (1) by an average of stochastic gradients that are independently computed in parallel on separate workers (parallel SGD). This simple scheme has a major drawback: in each iteration the results of the computations on the workers have to be shared with the other workers to compute the next iterate x t+1 . Communication has been reported to be a major bottleneck for many large scale deep learning applications, see e.g. BID32 BID17 . Mini-batch parallel SGD addresses this issue by increasing the compute to communication ratio. Each worker computes a mini-batch of size b ≥ 1 before communication. This scheme is implemented in state-of-the-art distributed deep learning frameworks BID0 BID26 BID31 . Recent work in BID43 BID10 explores various limitations of this approach, as in general it is reported that performance degrades for too large mini-batch sizes BID13 BID18 BID42 .In this work we follow an orthogonal approach, still with the goal to increase the compute to communication ratio: Instead of increasing the mini-batch size, we reduce the communication frequency. Rather than keeping the sequences on different machines in sync, we allow them to evolve locally on each machine, independent from each other, and only average the sequences once in a while (local SGD). Such strategies have been explored widely in the literature, under various names.An extreme instance of this concept is one-shot SGD (McDonald et al., 2009; BID53 where the local sequences are only exchanged once, after the local runs have converged. Zhang et al. (2013 ) show statistical convergence (see also BID33 BID9 BID12 ), but the analysis restricts the algorithm to at most one pass over the data, which is in general not enough for the training error to converge. More practical are schemes that perform more frequent averaging of the parallel sequences, as e.g. BID22 for perceptron training (iterative parameter mixing), see also BID6 , BID48 BID4 BID46 for the training of deep neural networks (model averaging) or in federated learning BID23 .The question of how often communication rounds need to be initiated has eluded a concise theoretical answer so far. Whilst there is practical evidence, the theory does not even resolve the question whether averaging helps when optimizing convex functions. Concretely, whether running local SGD on K workers is K times faster than running just a single instance of SGD on one worker. Theorem 2.2. Let f be L-smooth and µ-strongly convex, DISPLAYFORM0 are generated according to (4) with gap(I T ) ≤ H and for stepsizes η t = 4 µ(a+t) with shift parameter a > max{16κ, H}, for DISPLAYFORM1 DISPLAYFORM2 We were not especially careful to optimize the constants (and the lower order terms) in (5), so we now state the asymptotic result. Corollary 2.3. Letx T be as defined as in Theorem 2.2, for parameter a = max{16κ, H}. Then DISPLAYFORM3 For the last estimate we used E µ x 0 − x ≤ 2G for µ-strongly convex f , as derived in (Rakhlin et al., 2012, Lemma 2) . Remark 2.4 (Mini-batch local SGD). So far, we assumed that each worker only computes a single stochastic gradient. In mini-batch local SGD, each worker computes a mini-batch of size b in each iteration. This reduces the variance by a factor of b, and thus Theorem (2.2) gives the convergence rate of mini-batch local SGD when σ 2 is replaced by DISPLAYFORM4 We now state some consequences of equation FORMULA17 . For the ease of the exposition we omit the dependency on L, µ, σ 2 and G 2 below, but depict the dependency on the local mini-batch size b.Convergence rate. For T large enough and assuming σ > 0, the very first term is dominating in (6) and local SGD converges at rate O(1/(KT b)). That is, local SGD achieves a linear speedup in both, the number of workers K and the mini-batch size b. Global synchronization steps. It needs to hold H = O( T /(Kb)) to get the linear speedup. This yields a reduction of the number of communication rounds by a factor O( T /(Kb)) compared to parallel mini-batch SGD without hurting the convergence rate. Extreme Cases. We have not optimized the result for extreme settings of H, K, L or σ. For instance, we do not recover convergence for the one-shot averaging, i.e. the setting H = T (though convergence for H = o(T ), but at a lower rate). Unknown Time Horizon/Adaptive Communication Frequency BID46 empirically observe that more frequent communication at the beginning of the optimization can help to get faster time-to-accuracy (see also BID16 ). Indeed, when the number of total iterations T is not known beforehand (as it e.g. depends on the target accuracy, cf. (6) and also Section 4 below), then increasing the communication frequency seems to be a good strategy to keep the communication low, why still respecting the constraint H = O( T /(Kb)) for all T . DISPLAYFORM5 . It will be useful to define DISPLAYFORM6 Observex t+1 =x t − η t g t and E g t =ḡ t .Now the proof proceeds as follows: we show (i) that the virtual sequence {x t } t≥0 almost behaves like mini-batch SGD with batch size K (Lemma 3.1 and 3.2), and (ii ) the true iterates {x k t } t≥0,k∈[K] do not deviate much from the virtual sequence FIG6 . These are the main ingredients in the proof. To obtain the rate we exploit a technical lemma from BID35 . Lemma 3.1 . Let {x t } t≥0 and {x t } t≥0 for k ∈ [K] be defined as in (4) and (7) and let f be L-smooth and µ-strongly convex and η t ≤ 1 4L . Then DISPLAYFORM7 Bounding the variance. From equation FORMULA21 it becomes clear that we should derive an upper bound on E g t −ḡ t 2 . We will relate this to the variance σ 2 . DISPLAYFORM8 Bounding the deviation. Further, we need to bound DISPLAYFORM9 For this we impose a condition on I T and an additional condition on the stepsize η t . Lemma 3.3. If gap(I T ) ≤ H and sequence of decreasing positive stepsizes {η t } t≥0 satisfying η t ≤ 2η t+H for all t ≥ 0, then DISPLAYFORM10 where G 2 is a constant such that DISPLAYFORM11 Optimal Averaging. Similar as in BID14 BID34 BID28 we define a suitable averaging scheme for the iterates {x t } t≥0 to get the optimal convergence rate. In contrast to BID14 ) that use linearly increasing weights, we use quadratically increasing weights, as for instance BID34 BID35 . Lemma 3.4 ((Stich et al., 2018) ). Let {a t } t≥0 , a t ≥ 0, {e t } t≥0 , e t ≥ 0 be sequences satisfying DISPLAYFORM12 DISPLAYFORM13 for w t = (a + t) 2 and S T := T −1 DISPLAYFORM14 Proof. This is a reformulation of Lemma 3.3 in BID35 . We prove convergence of synchronous and asynchronous local SGD and are the first to show that local SGD (for nontrivial values of H) attains theoretically linear speedup on strongly convex functions when parallelized among K workers. We show that local SGD saves up to a factor of O(T 1/2 ) in global communication rounds compared to mini-batch SGD, while still converging at the same rate in terms of total stochastic gradient computations.Deriving more concise convergence rates for local SGD could be an interesting future direction that could deepen our understanding of the scheme. For instance one could aim for a more fine grained analysis in terms of bias and variance terms (similar as e.g. in BID7 BID12 ), relaxing the assumptions (here we relied on the bounded gradient assumption), or investigating the data dependence (e.g. by considering data-depentent measures like e.g. gradient diversity BID42 ). There are also no apparent reasons that would limit the extension of the theory to non-convex objective functions; Lemma 3.3 does neither use the smoothness nor the strong convexity assumption, so this can be applied in the non-convex setting as well. We feel that the positive results shown here can motivate and spark further research on non-convex problems. Indeed, very recent work (Zhou & Cong, 2018; BID44 analyzes local SGD for non-convex optimization problems and shows convergence of SGD to a stationary point, though the restrictions on H are stronger than here.
We prove that parallel local SGD achieves linear speedup with much lesser communication than parallel mini-batch SGD. Provides a convergence proof for local SGD, and proves that local SGD can provide the same speedup gains as minibatch, but may be able to communicate significantly less. This paper presents an analysis of local SGD and bounds on how frequent the estimators obtained by running SGD required to be averaged in order to yield linear parallelization speedups. The authors analyze the local SGD algorithm, where $K$ parallel chains of SGD are run, and the iterates are occasionally synchronized across machines by averaging