PaperlayerView exact revision on arXiv

Source-linked AI summary

Is Local SGD Better than Minibatch SGD?

Blake Woodworth, Kumar Kshitij Patel, Sebastian U. Stich, Zhen Dai, Brian Bullins, H. Brendan McMahan, Ohad Shamir, Nathan Srebro

arXiv:2002.07839v2cs.LGmath.OCstat.ML

TL;DR

The paper asks whether local SGD is better than minibatch SGD under matched distributed computation and communication, addressing limited theoretical understanding of that comparison. It analyzes quadratic and general convex objectives and finds that local SGD can strictly outperform the baseline, yet can also be worse in certain regimes, motivating methods that combine both approaches.

  • Problem

    Existing convex analyses of local SGD are dominated by minibatch SGD, leaving its comparative performance and optimality under matched distributed resources unresolved.

  • Method

    The paper derives upper and lower bounds for local SGD, compares them with minibatch SGD, and studies quadratic and general convex objectives under a worst-case framework.

  • Results

    Local SGD strictly outperforms minibatch SGD for quadratic objectives, sometimes improves over it for general convex objectives, but has a worse lower bound in another regime.

  • Takeaways & Limitations

    Local SGD is not uniformly optimal, so selecting it requires considering alternatives such as minibatch SGD and methods combining both advantages.

  • Takeaways & Limitations

    The paper’s upper and lower bounds for local SGD are not tight, with the first term differing as K1/3 versus K2/3.

Abstract

from arXiv · show

We study local SGD (also known as parallel SGD and federated averaging), a natural and frequently used stochastic distributed optimization method. Its theoretical foundations are currently lacking and we highlight how all existing error guarantees in the convex setting are dominated by a simple baseline, minibatch SGD. (1) For quadratic objectives we prove that local SGD strictly dominates minibatch SGD and that accelerated local SGD is minimax optimal for quadratics; (2) For general convex objectives we provide the first guarantee that at least sometimes improves over minibatch SGD; (3) We show that indeed local SGD does not dominate minibatch SGD by presenting a lower bound on the performance of local SGD that is worse than the minibatch SGD guarantee.

1 Introduction

The paper examines whether local SGD is theoretically better than minibatch SGD under matched computation and communication, finding that the answer depends on the objective and regime.

  • Setup: Local SGD distributes M workers across R communication rounds, with each worker taking K local SGD steps before iterates are averaged.Each machine computes T = KR stochastic gradients, while the system computes N = KRM gradients over R communication steps.
  • Baseline: Minibatch SGD provides the matched baseline by taking R steps with minibatches of size KM.Each round averages KM stochastic-gradient estimates at the current iterate.
  • Open question: Existing convex analyses of local SGD are strictly dominated by minibatch SGD, leaving unclear whether this reflects weak analyses or genuinely worse performance.The paper frames this as an unresolved comparison under typical supervised-learning noise scaling.
  • Contributions: For quadratic objectives, local SGD is strictly better than minibatch SGD in the worst case, and accelerated local SGD is minimax optimal.This establishes a setting where local SGD’s theoretical advantage is definitive.
  • Contributions: For general convex objectives, local SGD improves over minibatch SGD when M is large and K ≳ R, but can also have higher worst-case error in another regime.The paper supports the lower-bound result with logistic-regression experiments in the predicted problematic regime.
  • Implications: The results caution users against assuming local SGD dominates minibatch SGD and motivate methods combining their advantages.The paper identifies regimes where alternatives to local SGD should be considered.

2 Preliminaries

The paper formalizes distributed stochastic optimization under smooth convex objectives and matched computation, then defines local SGD, minibatch SGD, and comparison baselines for worst-case analysis.

  • Problem class: The problem class contains H-smooth convex or λ-strongly convex objectives with bounded minimizer norm and uniformly bounded stochastic-gradient variance.The analysis covers both general convex and strongly convex functions, while emphasizing the general convex case in the main text.
  • Problem class: Supervised learning supplies a natural setting where the parameter scaling H ≈ σ2 follows from comparable bounds on the loss derivatives.The passage relates both smoothness and gradient variance to the feature norm.
  • Algorithms: Local SGD uses M machines performing K stochastic-gradient steps per communication round for R rounds, whereas minibatch SGD performs R steps using minibatches of size KM.The algorithms are compared under the same computation and communication structure.
  • Baselines: Thumb-twiddling SGD uses minibatches of size M by computing one gradient per machine per round and idling for the remaining K − 1 steps.It is introduced as a deliberately weak baseline for testing whether local SGD can match even this standard.
  • Evaluation criterion: The paper defines worst-case performance over the function class and uses minimax error to assess optimality under the prescribed oracle structure.The graph oracle model formalizes dependencies induced by communication, but existing lower bounds are not known to be tight.
  • Prior guarantees: Prior local-SGD guarantees are strictly dominated by minibatch SGD in the natural scaling H = σ2, while the paper’s bound improves over minibatch without requiring serial-only computation.Earlier improvements occur only in a trivial low-noise regime where serial SGD already beats minibatch SGD.
  • Prior guarantees: Existing analyses rely on varying assumptions, including not-quite-convexity, detailed noise models, or bounded third derivatives, complicating direct comparisons.The paper specializes these results to its common setting and notes that some assumptions are stronger or weaker than its own.
  • Alternative viewpoint: The paper also considers a communication-reduction viewpoint that fixes T = KR local computations per machine and compares against communication after every step.This reframes the question as reducing communication without paying an error cost.

3 Good News: Quadratic Objectives

For quadratic objectives, local versions of linear-update algorithms inherit their serial guarantees with variance reduction, making local SGD strictly better than minibatch SGD and accelerated local-AC-SA minimax optimal.

  • Linear update algorithms: For quadratic objectives, local-A inherits algorithm A’s guarantee while benefiting from variance reduction by a factor of M.The result applies to linear update algorithms, including SGD and AC-SA.
  • Linear update algorithms: The guarantee depends only on the total computation KR, not on K and R individually.This also yields a matching worst-case upper bound for different K and R values with the same product.
  • Linear update algorithms: Averaging the final iterates of M independent executions of A matches the upper bound of T iterations of size-M minibatch-A.This procedure is called one-shot averaging.
  • Boundaries: The theorem does not imply identical performance on each instance when K and R vary with fixed KR.It establishes matching worst-case upper bounds, while stochastic-gradient structure assumptions must remain valid for the local method.
  • Comparison with minibatch SGD: Local-AC-SA is minimax optimal for quadratic objectives.The paper obtains this result by applying the general linear-update theorem to local-SGD and local-AC-SA.
  • Comparison with minibatch SGD: Local-SGD’s quadratic bound is strictly better than minibatch SGD’s because its first term scales as (KR)^-1 instead of R^-1.The advantage remains relative to accelerated minibatch SGD for the corresponding accelerated local-AC-SA bound.

4 More Good News: General Convex Objectives

For general convex objectives, the paper gives the first local-SGD upper bound that is not dominated by minibatch SGD and identifies regimes where local SGD is better. The comparison depends on M, K, and R, and the guarantee does not establish universal dominance.

  • General convex objectives: The paper’s first general-convex analysis yields a local-SGD bound that is not dominated by minibatch SGD.The analysis is claimed to dominate all previous upper bounds.
  • Theorem 2: Theorem 2 uses optimally tuned constant stepsizes for λ = 0 and decaying stepsizes for λ > 0.The result concerns appropriate averages of local-SGD iterates.
  • Proof approach: The analysis models the averaged iterate as approximately following size-M minibatch SGD, with an error term controlled by worker-iterate dispersion.The paper refines this dispersion analysis to improve the resulting bound.
  • Comparison with minibatch SGD: The statistical term has the same minimax scaling for both algorithms in the noise-dominated regime, where M^3K ≲ R and MK ≲ R.That term cannot be improved by any first-order algorithm.
  • Comparison with minibatch SGD: Local SGD’s K^-1 R^-2/3 rate is better than minibatch SGD’s R^-1 when K ≳ R, but worse when K ≲ R.The trade-off reflects noisier local updates versus K times more updates.
  • Comparison with minibatch SGD: Local SGD strictly outperforms minibatch SGD in the worst case in the large-M and large-K regime.The comparison is based on the upper bound from Theorem 2 and minibatch SGD’s guarantee.

5 Bad News: Minibatch SGD Can Outperform Local SGD

For general convex objectives, local SGD is not uniformly competitive with minibatch SGD: a lower-bound construction shows minibatch can be better, especially when K is small relative to R. The gap can be even larger in strongly convex settings, while experiments qualitatively match the theory.

  • Lower bound: A hard-instance construction establishes that local SGD has a performance lower bound for any K ≥2, M, and R ≥1 under any fixed stepsize.The construction uses a function-distribution pair and local SGD initialized at 0.
  • Mechanism: Nonquadratic objectives introduce an additional bias in local SGD that does not depend on M and scales poorly with K and R.The underlying contrast is with quadratic objectives, whose SGD updates are linear.
  • Lower bound: Local SGD can be worse than minibatch SGD in the worst case when K is small relative to R.For larger K, local SGD is better in the worst case according to the stated crossover comparison.
  • Strongly convex case: In strongly convex problems, minibatch SGD’s optimization term scales as exp(−R), whereas local SGD cannot achieve a term better than (KR)−2.The resulting dependence on R is exponentially worse for local SGD, with a worse bound when R ≳ log(K).
  • Empirical evidence: On logistic regression, experiments show local SGD performing worse than minibatch SGD in the small K = 5 regime with optimally tuned stepsizes.The empirical comparison includes thumb-twiddling SGD and follows the qualitative prediction of the lower-bound theorem.

6 Future work

The paper concludes that local SGD is not always competitive or optimal, while its exact worst-case behavior remains unresolved. Future work should seek methods that combine local and minibatch SGD’s advantages and attain optimal guarantees across regimes.

  • Local SGD can sometimes be worse than minibatch SGD and is not optimal, despite the paper’s first analysis showing improvement in a natural setting.
  • The upper and lower bounds for local SGD are not tight, leaving its exact worst-case behavior unresolved.The first term differs in its dependence on K, with the paper conjecturing intermediate behavior.
  • A simple univariate nonquadratic example shows local SGD can remain bounded away from the optimum even with infinitely many machines, while minibatch SGD stays at zero.
  • The empirical study uses 50000 points in R25 and compares optimally tuned local, minibatch, and thumb-twiddling SGD on logistic loss.The labels are generated from an intersection of two halfspaces with boundary-dependent label noise.
  • The paper motivates algorithms that combine local and minibatch SGD and dominate both, including in regimes where local SGD already performs better.
  • One target is an algorithm combining accelerated-gradient optimization over KR steps with an optimal statistical term for general convex objectives.Such a method would match the lower bound of Woodworth et al. for the communication structure.

A Comparisons Between Existing Local SGD Analyses and Minibatch SGD

The paper reconciles prior local-SGD analyses under differing assumptions by converting strongly convex guarantees into comparable convex guarantees. It then uses optimistic interpretations of those bounds to compare them with minibatch SGD.

  • Strongly convex guarantees can be converted into convex guarantees by adding a quadratic regularizer and optimizing over λ > 0.
  • When a guarantee has multiple error terms, the paper separately optimizes each term and sums the resulting bounds.
  • The table uses optimistic interpretations of prior bounds because the goal is to show that existing analyses are dominated by minibatch SGD.

A.1 Stich [23]

The comparison with Stich [23] adjusts for that paper’s stronger and different assumptions, including quasi-convexity, smoothness, and multiplicative noise. The resulting rates are placed alongside minibatch-SGD guarantees under matched variance assumptions.

  • The compared analysis assumes uniformly bounded stochastic gradients, an assumption additional to the paper’s setup.
  • An optimistic bound assumes iterates remain no farther from x∗ than at initialization, although this need not hold.
  • The paper retains a bound from Stich [23] because its purpose is to show that the analysis is deficient.
  • For the non-strongly convex setting, the paper extends the result by optimizing the error and regularization terms separately while ignoring constants.
  • Stich [23] assumes λ⋆-quasi-convexity, H-smoothness, and multiplicative stochastic-gradient noise; the paper compares rates using its uniform variance bound.

A.3 Khaled et al. [13]

Khaled et al.’s cited guarantee can be worse than minibatch SGD, while its apparent exception corresponds to a regime where serial SGD is already better than minibatch SGD.

  • When H = B = σ2 = 1, Khaled et al.’s guarantee is strictly worse than minibatch SGD.
  • For arbitrary H, B, and σ2, the guarantee is worse than minibatch SGD unless the stated parameter regime holds.
  • That exception is trivial because KR serial SGD already achieves lower error than minibatch SGD.
  • In that regime, ignoring M − 1 machines is preferable, and local SGD performs no better than serial SGD.

B Proofs from Section 3

For quadratic objectives, local execution of linear update algorithms inherits the serial algorithm’s behavior with reduced gradient variance. This makes local SGD competitive with minibatch SGD and makes accelerated local SGD minimax optimal.

  • Theorem 1 shows that local-A’s averaged iterate can be analyzed through the linear update algorithm A after variance reduction by M.
  • The averaged local iterates evolve according to A with a lower-variance stochastic gradient, even when the average is not explicitly computed at every step.
  • For any quadratic objective with λ = 0, Corollary 1 provides guarantees for local-SGD and local-AC-SA.
  • Local-AC-SA is minimax optimal for quadratic objectives.
  • The first and second terms of local-AC-SA’s guarantee cannot be improved, including by an algorithm allowed MKR sequential stochastic-gradient calls.

C Proof of Theorem 2

Theorem 2 analyzes local SGD for convex and strongly convex objectives using averaged iterates and tailored stepsizes, while comparing favorably with serial SGD in the stated bounds.

  • The analysis uses averaged local iterates, which may not be computed by the algorithm but are central to the proof.
  • For convex objectives, the proof improves a prior upper bound by controlling the final term more tightly than Stich’s analysis.
  • Local SGD is never worse than KR steps of sequential SGD on one machine, supplying the serial-SGD terms in Theorem 2’s bounds.
  • Convex Case λ = 0: For λ = 0, local SGD uses an optimally tuned constant stepsize and an appropriate average of its iterates.
  • Strongly Convex Case λ > 0: For λ > 0, local SGD uses decreasing stepsizes and an appropriate weighted average under the strongly convex analysis.

D Proofs from Section 5

The Section 5 proofs construct a separable hard instance and analyze its coordinates independently to establish a lower bound for fixed-stepsize local SGD.

  • The hard objective decomposes across three coordinates, so local-SGD dynamics can be analyzed independently on each coordinate.
  • Lemmas 8–10 analyze repeated fixed-stepsize stochastic-gradient updates on g_L, including even and odd iteration counts.
  • The third coordinate is reduced to local SGD on the univariate function g_L with a shifted initialization.
  • The first two coordinates evolve as deterministic gradient descent because their stochastic gradients contain no noise.
  • Theorem 3 concludes that, for any K ≥ 2 and M, R ≥ 1, fixed-stepsize local SGD has a worst-case output lower bound on a constructed objective.
Loading 2002.07839v2…