PaperlayerView exact revision on arXiv

Source-linked AI summary

Local SGD Converges Fast and Communicates Little

Sebastian U. Stich

arXiv:1805.09767v3math.OCcs.DCcs.LG

TL;DR

Communication is a major bottleneck in large-scale distributed training, while the frequency of communication rounds in local SGD lacked a concise theoretical answer. The paper analyzes local SGD, in which workers run SGD independently and periodically synchronize, and shows linear speedup in workers and mini-batch size without hurting convergence.

  • Problem

    Communication bottlenecks affect large-scale deep learning, and theory had not given a concise answer about how often local SGD should synchronize or whether averaging yields linear speedup.

  • Method

    Local SGD runs SGD independently across workers and synchronizes their sequences periodically, with synchronization frequency ranging from every iteration to only at the end.

  • Results

    Local SGD converges at rate O(1/(KTb)), achieving linear speedup in the number of workers K and mini-batch size b.

  • Takeaways & Limitations

    Reducing communication frequency can lower communication rounds compared with parallel mini-batch SGD without hurting the convergence rate.

  • Takeaways & Limitations

    The analysis does not recover convergence for one-shot averaging with H = T, although convergence holds for H = o(T) at a lower rate.

Abstract

from arXiv · show

Mini-batch stochastic gradient descent (SGD) is state of the art in large scale distributed training. The scheme can reach a linear speedup 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 speedup 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.

1 Introduction

Local SGD reduces communication by letting workers evolve independently and averaging only periodically, addressing communication bottlenecks in distributed SGD. The paper provides a convergence analysis showing linear computational speedup while substantially reducing communication relative to mini-batch SGD.

  • Motivation: Communication is a major bottleneck in large-scale distributed training, despite parallel SGD’s potential for linear speedup.Mini-batch SGD increases the compute-to-communication ratio, but performance can degrade when mini-batches become too large.
  • Local SGD: Local SGD increases the compute-to-communication ratio by allowing workers to evolve independently and averaging their sequences only periodically.With synchronization every iteration, local SGD becomes mini-batch SGD; with synchronization only at the end, it becomes one-shot averaging.
  • Research gap: The paper addresses whether averaging local sequences can provide a K-fold speedup on convex optimization problems.Prior theory had not established whether local SGD on K workers was K times faster than a single-worker SGD instance.
  • Contributions: The analysis shows that frequent synchronization of K local sequences increases the convergence rate by a factor of K.This establishes linear speedup in computation and makes local SGD as efficient as parallel mini-batch SGD computationally.
  • Contributions: H = O(T/(Kb)) permits reducing communication rounds without hampering asymptotic convergence.The paper compares increasing mini-batch size b with increasing communication interval H as ways to improve the compute-to-communication ratio, while noting H cannot be arbitrarily large.
  • Scope: The guarantees cover convex problems, while convergence is not established for the non-convex setting.The authors present the convex results as motivation for further investigation in applications such as deep learning.

2 Local SGD

Local SGD runs K parallel stochastic-gradient sequences and synchronizes them only at selected indices, interpolating between mini-batch SGD and one-shot averaging. Under smooth, strongly convex assumptions, it achieves linear speedup while allowing substantially fewer communication rounds, though the stated analysis does not cover one-shot averaging or non-convex objectives.

  • Algorithm: Local SGD generates K parallel iterate sequences and averages them at synchronization indices separated by a bounded gap.Synchronizing every iteration recovers parallel mini-batch SGD, while synchronizing only at the end gives one-shot averaging.
  • Variance reduction: Averaging K stochastic gradients reduces the variance by a factor of K, yielding the linear-speedup rationale for parallel SGD and local SGD.The local-SGD analysis seeks to show that workers evolving sufficiently close together retain this variance reduction.
  • Convergence analysis: Under L-smooth and µ-strongly convex assumptions, the theorem uses stepsizes with shift a > max{16κ, H} and a synchronization gap at most H.The result uses weighted averaged iterates and explicitly tracks bias and variance terms.
  • Convergence rate: O(1/(KTb)) is the asymptotic convergence rate of mini-batch local SGD, giving linear speedup in both workers K and mini-batch size b.Using mini-batches of size b reduces variance by a factor of b.
  • Communication: O(T/(Kb)) is the communication-round reduction factor compared with parallel mini-batch SGD without hurting the convergence rate.The communication interval must satisfy the corresponding order constraint to preserve linear speedup.
  • Limitations: The analysis does not recover convergence for one-shot averaging H = T, although it covers H = o(T) at a lower rate.The authors also state that convergence guarantees for the non-convex setting are not yet provided.

3 Proof Outline

The proof introduces a virtual averaged sequence and shows that it behaves like mini-batch SGD while local iterates remain close to it. Variance, deviation, and weighted-averaging lemmas combine to establish the convergence result.

  • Perturbed iterate analysis: The analysis introduces a virtual sequence that need not be computed explicitly and coincides with local iterates at synchronization times.It equals every local sequence when synchronization occurs at every step.
  • Perturbed iterate analysis: The virtual sequence almost behaves like mini-batch SGD with batch size K.The proof establishes this through separate lemmas for the virtual sequence and the stochastic gradients.
  • Bounding the variance: Bounding gradient variance relates the deviation between stochastic and averaged gradients to the variance term σ2.The argument imposes conditions on synchronization indices and the stepsize.
  • Bounding the deviation: A separate deviation bound controls how far the true local iterates move from the virtual sequence.This is the second main ingredient after establishing mini-batch-like behavior.
  • Optimal Averaging: Quadratically increasing weights are used to average iterates and obtain the optimal convergence rate.The resulting rate follows by combining the technical averaging lemma with the preceding bounds.

4 Numerical Illustration

The numerical section evaluates wall-clock speedup by combining gradient-computation and communication costs, then illustrates theoretical and measured behavior under a communication-cost ratio of ρ = 25.

  • Speedup: Wall-clock time combines TK gradient computations with communication across T/H rounds, where each round exchanges 2(K −1) vectors.The communication-to-gradient cost ratio ρ is at least 1 and can be 10–100 or larger on slow networks.
  • Theoretical: The theoretical speedup compares local SGD on K machines with SGD on one machine using the derived communication-cost model.The analysis examines how worker count, communication interval H, target accuracy, and ρ affect scaling.
  • Theoretical: For ϵ = 0, the largest H values give the best theoretical speedup, while for few epochs the optimal H changes with K.When the time horizon is unknown, the discussion points to adaptively increasing H over time.
  • Experimental: The experiment measures iterations to reach target accuracy on logistic regression using the w8a dataset with d = 300 and n = 49749.It tests last-iterate and several averaging choices, including quadratic weighting, under ρ = 25.
  • Conclusion: For smaller T, the O(1/K) dependency appears significantly in experiments and must be considered when deploying on massively parallel systems.The conclusion contrasts this with the less severe theoretical restriction on H as T approaches infinity.

5 Asynchronous Local SGD

Asynchronous local SGD lets workers evolve and synchronize at different times through server-side reads and atomic updates. Its convergence rate matches synchronous local SGD under the stated assumptions.

  • Asynchronous Local SGD: Asynchronous local SGD allows local sequences to operate without synchronization and supports load balancing for heterogeneous workers.Slower workers can compute less between synchronizations, while faster workers can compute more.
  • Asynchronous Local SGD: Each worker evolves its own sequence and uses a worker-specific set of synchronization indices that need not match other workers.The construction tracks local sequences and their synchronization events separately.
  • Asynchronous Local SGD: A worker reads the aggregated variable as it exists when the read occurs, including updates already written at that time.The notation records the worker, initiating read, and contributing local sequences.
  • Asynchronous Local SGD: Atomic aggregation and server reads implement asynchronous updates without overwriting previously written updates.The schematic algorithm tracks each worker's last-read iteration.
  • Convergence result: Under the theorem's stepsize and shift conditions, asynchronous local SGD converges at the same rate as synchronous local SGD.The theorem applies to K parallel sequences and bounds the resulting convergence rate.

6 Conclusion

The paper establishes linear speedup for local SGD on strongly convex functions while reducing communication rounds. It also identifies bounded-gradient assumptions and non-convex analysis as important boundaries for further work.

  • Conclusion: Local SGD attains theoretically linear speedup on strongly convex functions when parallelized among K workers.The result applies for nontrivial synchronization intervals H.
  • Conclusion: O(T^1/2) fewer global communication rounds are possible than with mini-batch SGD while preserving the same rate in total stochastic gradient computations.This is the paper's central computation-versus-communication result.
  • Limitations and future work: The analysis relies on a bounded-gradient assumption and leaves more concise rates and broader data-dependent analyses for future work.The discussion also identifies non-convex objectives as a direction for extending the theory.

A Missing Proofs for Synchronized Local SGD

The synchronized local SGD analysis proves convergence by decomposing the averaged iterate error and bounding variance, disagreement, and optimization terms under convexity and stepsize assumptions.

  • Conclusion: The proof concludes by substituting the derived estimates into the main recursion and taking expectations.The appendix contains the corresponding recursive algebra and upper-bound calculations.
  • Proof strategy: The proof starts from the averaged-iterate update and expands its squared distance to the optimum.The expansion introduces the local gradient average as a comparison term.
  • Proof strategy: Strong convexity controls the optimization term in the distance recursion.The argument explicitly invokes μ-strong convexity.
  • Proof strategy: Young’s inequality bounds the final cross term by separate squared-norm contributions.The proof uses 2⟨a,b⟩ ≤ γ∥a∥2 + γ^-1∥b∥2 for γ > 0.
  • Proof strategy: Convexity converts an average of function gaps and squared distances into corresponding quantities for the averaged iterate.The argument applies this relation under nonnegative coefficients and ηt ≤ 1/(4L).
  • Supporting bounds: The remaining lemmas bound stochastic variance and the deviation of local iterates from the averaged sequence.These bounds support the final convergence recursion after expectations are taken.

B Missing Proof for Asynchronous Local SGD

The asynchronous local SGD proof adapts the synchronized analysis through a virtual sequence and a refined bound on local-sequence deviation under bounded delays.

  • Proof strategy: The asynchronous proof follows the synchronized proof and introduces a virtual sequence for analysis.The virtual sequence aggregates updates that may be written at different times.
  • Assumptions: The analysis assumes every worker has written its updates when the algorithm terminates, while noting this assumption could be relaxed.The assumption is used to simplify the proof notation.
  • Core bound: A refined lemma bounds how far local sequences can deviate from the virtual average.This deviation bound is identified as a main ingredient of the asynchronous analysis.
  • Delay handling: The asynchronous argument tracks delayed writes using intervals based on the delay parameters τ and H.The proof defines [s] for negative s and selects indices within H steps of the current time.
  • Conclusion: After the delayed-sequence estimates are established, the proof of Theorem 5.1 follows immediately.The final step invokes the preceding lemma and completes the asynchronous convergence argument.

C.1 Synchronous Local SGD

The synchronous local SGD section notes that the theorem guarantees convergence for a weighted average of iterates, with practical procedures for tracking it and balancing heterogeneous workloads.

  • Convergence output: Theorem 5 does not prove convergence of the individual iterate sequences, only of a weighted average of all iterates.The authors note that the last iterate may nevertheless be sufficient in practice.
  • Convergence output: The weighted average can be tracked online with an auxiliary sequence instead of storing all intermediate iterates.Table 1 gives recursive formulas for the required averages.
  • Implementation: Synchronous local SGD workers can maintain the running averages locally using recursive formulas.This preserves the weighted-average procedure without requiring storage of the full history.
  • Implementation: A faster worker can compute updates for a lagging worker’s sequence, enabling load balancing in heterogeneous settings.This flexibility is unavailable in the synchronous model because communications must occur in sync.
  • Implementation: In the illustrated two-worker example, each worker performs H local steps before writing updates to the aggregate, with τ ≤ 3H.The bound describes the delay produced by the load-balancing procedure.

D Details on Experiments

The experiments measure local SGD speedup on a regularized logistic-regression problem across worker counts, local-step parameters, mini-batch sizes, target accuracies, and stepsizes.

  • Experimental setup: The empirical study examines speedup on a regularized logistic-regression objective using the w8a dataset with d = 300 and n = 49749.The regularization parameter is set to λ = 1/n.
  • Reproducibility: The experiments can reproduce synchronous averaging results by simulating local SGD with virtual workers.This is possible because the averaging steps are deterministic apart from stochastic-gradient randomness.
  • Evaluation: The experiments evaluate weighted averages because the convergence theorem concerns a special weighted sum rather than the last iterate or uniform average.The precise recursive averaging formulas are provided in Table 1.
  • Evaluation: For each configuration, the best result is selected across two stepsize families and a grid search over parameter c.The grid search treats c as optimal when nearby tested values perform worse.
  • Speedup results: Additional results report measured speedup for mini-batch sizes b = 1 and b = 16 across different worker counts K and parameters H.Figures 4 and 5 provide these configurations.
Loading 1805.09767v3…