PaperlayerView exact revision on arXiv

Source-linked AI summary

Minibatch vs Local SGD for Heterogeneous Distributed Learning

Blake Woodworth, Kumar Kshitij Patel, Nathan Srebro

arXiv:2006.04735v5cs.LGmath.OCstat.ML

TL;DR

The paper asks how Local SGD and Minibatch SGD compare when machines optimize different local objectives with intermittent communication. It analyzes both methods, including accelerated minibatch variants and a dual-stepsize framework. It concludes that minibatch methods are robust to heterogeneity, accelerated Minibatch SGD is optimal at high heterogeneity, and Local SGD improves over Minibatch SGD only in a sufficiently near-homogeneous regime.

  • Problem

    The paper examines whether Local SGD offers better guarantees than Minibatch SGD for convex heterogeneous objectives under limited communication.

  • Method

    The paper analyzes Minibatch SGD, Accelerated Minibatch SGD, and Local SGD under heterogeneous distributed stochastic optimization, including a dual-stepsize formulation.

  • Results

    Accelerated Minibatch SGD is optimal under high heterogeneity, while Local SGD improves over Minibatch SGD only in a sufficiently small-heterogeneity, non-homogeneous regime.

  • Takeaways & Limitations

    Minibatch SGD is essentially immune to heterogeneity, whereas Local SGD’s benefits are confined to homogeneous or near-homogeneous settings.

  • Takeaways & Limitations

    The medium-heterogeneity regime remains open: other methods might improve over accelerated or ordinary Minibatch SGD, but Local SGD does not.

Abstract

from arXiv · show

We analyze Local SGD (aka parallel or federated SGD) and Minibatch SGD in the heterogeneous distributed setting, where each machine has access to stochastic gradient estimates for a different, machine-specific, convex objective; the goal is to optimize w.r.t. the average objective; and machines can only communicate intermittently. We argue that, (i) Minibatch SGD (even without acceleration) dominates all existing analysis of Local SGD in this setting, (ii) accelerated Minibatch SGD is optimal when the heterogeneity is high, and (iii) present the first upper bound for Local SGD that improves over Minibatch SGD in a non-homogeneous regime.

1 Introduction

The paper studies intermittent-communication distributed learning with heterogeneous local data, asking whether Local SGD improves over Minibatch SGD and which method is optimal across heterogeneity regimes.

  • Setting: Heterogeneous data and limited communication make consensus learning difficult because local objectives can differ substantially.A model that performs well for one machine’s distribution may perform poorly for others.
  • Methods: Minibatch SGD averages local minibatch gradients into one update using data from all machines, while Local SGD averages independently updated local iterates after communication.Local SGD decouples the number of updates from the number of communications.
  • Open question: Existing analyses had not shown Local SGD improving over Minibatch SGD in heterogeneous settings, and often gave much worse guarantees.The paper frames this as both an analytical question and a method-comparison problem.
  • Findings: High heterogeneity makes Local SGD strictly worse than Minibatch SGD, even without acceleration and regardless of communication frequency.This conclusion follows from the paper’s discussion of heterogeneity-dependent lower bounds.
  • Findings: Local SGD improves over Minibatch SGD when heterogeneity is sufficiently small, providing the first such result for a non-homogeneous setting.The regime is near-homogeneous but not exactly homogeneous.
  • Findings: Accelerated Minibatch SGD is optimal with moderately high or unrestricted heterogeneity, while a medium-heterogeneity regime may require new methods.The paper identifies a regime where Accelerated Minibatch SGD may not be optimal but Local SGD is worse than Minibatch SGD.

2 Setup

The setup distributes stochastic optimization across machines with distinct data distributions and restricts communication, comparing minibatch and local computation under heterogeneity-dependent assumptions.

  • Problem setup: Each machine has its own distribution D_m, and the objective is the average of the local objectives.The setting models data distributed across machines, regions, servers, or devices.
  • Communication model: Each machine computes T stochastic gradients over R communication rounds, processing K = T/R gradients per round.Communication is limited relative to local computation, with all machines communicating at the end of each round.
  • Minibatch SGD: Minibatch SGD computes K gradients at a common iterate on each machine, averages them across machines, and performs R updates using minibatches of size KM.The aggregated gradient uses non-i.i.d. samples from all local distributions.
  • Local SGD: Local SGD performs K local SGD steps from a common starting iterate, then averages the final local iterates to initialize the next round.Unlike Minibatch SGD, machines update their local iterates throughout each communication round.
  • Communication reduction: The communication-reduction viewpoint fixes T local gradient computations while asking how far R can be reduced before accuracy degrades.Better error guarantees in K, M, and R permit fewer communication rounds for a given accuracy.
  • Assumptions: The analysis uses a heterogeneity parameter ζ^2_* that measures disagreement among local gradients at the optimum.The parameter is required by existing Local SGD analyses and is argued to be necessary for Local SGD convergence.
  • Assumptions: The paper considers strongly convex and weakly convex objectives under smoothness, variance, heterogeneity, and initialization or bounded-optimum assumptions.Strongly convex guarantees use λ and initial sub-optimality, whereas weakly convex guarantees use a bound B on the optimum norm.

3 Minibatch SGD and Accelerated Minibatch SGD

Minibatch gradients remain unbiased for the average objective despite heterogeneous data, allowing standard SGD analyses whose guarantees do not depend on heterogeneity.

  • Gradient estimation: Minibatch gradients are unbiased estimates of the gradient of the overall objective, ∇F, despite heterogeneous local objectives.This permits standard analyses for SGD and accelerated SGD.
  • Gradient estimation: The variance of the aggregated gradient decreases with MK and is unaffected by the heterogeneity parameter ζ_*².A corresponding variance-at-the-optimum calculation gives σ_*²/MK.
  • Guarantees: The paper provides separate Minibatch SGD guarantees for convex and strongly convex objectives.The stated results are presented for both weakly convex and strongly convex assumptions.
  • Guarantees: Accelerated Minibatch SGD likewise has guarantees for both convex and strongly convex objectives.Its analysis uses the same heterogeneity-robust minibatch gradient property.
  • Guarantees: Minibatch SGD and Accelerated Minibatch SGD have guarantees independent of ζ_*².The bounds are tight in the homogeneous case, so both methods are essentially immune to arbitrary heterogeneity.

4 Local SGD for heterogeneous data

Existing analyses indicate that heterogeneous Local SGD cannot substantially improve over Minibatch SGD except near homogeneity, while new analysis identifies a limited low-heterogeneity regime where Local SGD does improve.

  • Prior analyses: Previously published heterogeneous Local SGD guarantees are dominated by Koloskova et al.’s analysis, which remains worse than Minibatch SGD in every regime.The comparison is summarized in the convex-guarantee table.
  • Lower bounds: Karimireddy et al.’s lower bound shows that traditional Local SGD has heterogeneity-dependent error, but its scope requires the traditional stepsize choice.The qualification is η_inner = η_outer, equivalently η_g = 1.
  • Lower bounds: For any M, K, and R, four-dimensional objectives yield a fixed-stepsize Local SGD lower bound under both convex and strongly convex assumptions.The strongly convex statement applies for H ≥16λ.
  • Lower bounds: In the convex case, the lower bound closely resembles Koloskova et al.’s upper bound, with remaining gaps in K- and heterogeneity-dependent terms.The comparison focuses on H = B = σ² = 1 to emphasize ζ².
  • Lower bounds: Local SGD can be strictly worse than Minibatch SGD regardless of K, and increasing the duration of local rounds may provide little help under heterogeneity.The lower bound includes an additional 1/(MKR) term beyond the Minibatch baseline.
  • Refined analysis: A refined heterogeneity measure ζ̄² enables a smooth analysis from heterogeneous to homogeneous objectives and supports a new Local SGD guarantee.ζ̄² equals zero exactly when the local objectives agree up to an irrelevant additive constant.
  • Refined analysis: Theorem 3 is the first analysis showing improvement over Minibatch SGD in a heterogeneous regime, specifically when ζ̄² ≲ 1/R in the convex case.At ζ̄ = 0, it recovers the homogeneous result, including improvement when K ≳ R.
  • Scope: The related SCAFFOLD guarantee improves over Minibatch SGD only in a setting with randomly available machines and sufficiently small ζ*, unlike the all-machines setting considered here.This distinction is explicitly noted in the paper’s comparison.

5 Accelerated Minibatch SGD is optimal for highly heterogeneous data

The paper establishes optimality of Accelerated Minibatch SGD at sufficiently high heterogeneity using a lower bound for distributed zero-respecting algorithms. It leaves a medium-heterogeneity regime unresolved, where improvement may be possible but not through Local SGD.

  • Lower bound: Distributed zero-respecting algorithms restrict each machine’s iterate support to coordinates previously activated by gradients observed on that machine.The definition tracks communication timing between machine pairs and limits query supports accordingly.
  • Lower bound: The lower bound applies to any distributed zero-respecting algorithm on constructed convex and strongly convex quadratic objectives.This class includes Minibatch SGD, Accelerated Minibatch SGD, Local SGD, and coordinate descent methods.
  • High heterogeneity: Accelerated Minibatch SGD is optimal when ζ∗ is sufficiently large, including the convex regime ζ∗≥HB and the strongly convex regime up to log factors.The lower-bound comparison identifies high heterogeneity as the regime where accelerated minibatching cannot be improved.
  • Open regime: When ζ∗ is smaller than the high-heterogeneity threshold, the lower bound does not match Accelerated Minibatch SGD, so improvement remains possible.The paper specifically identifies this mismatch as an open question rather than a demonstrated gap.
  • Open regime: The unresolved convex regime is HB/R ≤ ζ∗ ≤ HB, while Local SGD is already ruled out as the improving method there.The paper asks whether new algorithms can improve over Accelerated Minibatch SGD when heterogeneity is bounded but non-negligible.

6 Inner and outer stepsizes

The paper studies a dual-stepsize method that interpolates between Minibatch SGD and Local SGD. With optimal stepsizes, its guarantee is at least as good as either endpoint, although existing analysis does not show a strict improvement from intermediate choices.

  • Method: The unified method takes local SGD steps with an inner stepsize and applies a communication-round update with an outer stepsize.This dual-stepsize formulation was previously presented and analyzed as FedAvg.
  • Interpolation: Setting ηinner = 0 recovers Minibatch SGD with stepsize ηouter, while setting ηinner = ηouter recovers Local SGD.The two established algorithms appear as endpoint choices within the same update family.
  • Guarantee: With optimally chosen stepsizes, the dual-stepsize method is guaranteed to be at least as good as both Minibatch SGD and Local SGD.The bound takes the better of the endpoint guarantees under the weakly convex assumptions.
  • Limitation: Existing analysis does not determine whether choosing 0 ≪ηinner ≪ηouter improves over both endpoint methods.The unresolved question concerns intermediate inner and outer stepsizes rather than the endpoint recoveries.

7 Using a Subset of Machines in Each Round

The paper extends its analysis to rounds using a uniformly random subset of machines, a setting typical in federated learning. Minibatch gradients remain unbiased, with guarantees depending on the participating-machine sample size and heterogeneity parameters.

  • Setting: Using only S ≤ M uniformly sampled machines per round is a heterogeneous federated-learning variant in which not all objective components are observed each round.In the homogeneous case, sampling machines makes no difference because their distributions are identical.
  • Minibatch estimator: Each round’s Minibatch SGD estimator averages SK stochastic gradients from K samples on each of S sampled machines.Sampling is performed uniformly without replacement.
  • Minibatch estimator: The sampled-machine gradient estimator remains unbiased for the overall gradient ∇F(xr), with variance determined by stochastic noise and machine sampling.The stated variance includes both the σ²/(SK) term and a heterogeneity-dependent component.
  • Guarantees: The paper provides convex and strongly convex guarantees for the subset-machine setting.These guarantees are stated separately for the two curvature assumptions.
  • Guarantees: Accelerated Minibatch SGD has analogous guarantees, while the guarantees also apply to Minibatch SGD and the inner/outer stepsize method.The paper notes that these bounds improve over the earlier analysis of the inner/outer variant, while SCAFFOLD can help in some regimes.

8 Discussion

The discussion concludes that Local SGD improves over Minibatch SGD only in homogeneous or near-homogeneous regimes, whereas Accelerated Minibatch SGD is optimal under high heterogeneity. Medium heterogeneity remains open, and the appendix develops the Minibatch SGD analysis supporting these comparisons.

  • Discussion: Nearly all prior analyses failed to show Local SGD improving over Minibatch SGD, with the known improvement confined to the homogeneous setting.The paper frames the heterogeneous case as substantially more difficult.
  • Discussion: The first non-homogeneous improvement for Local SGD occurs when ζ̄² is bounded and less than 1/R, while high heterogeneity ζ∗ > HB makes Accelerated Minibatch SGD optimal.The paper also states that Local SGD benefits lie in homogeneous or near-homogeneous settings unless additional assumptions are imposed.
  • Discussion: The regime R ≪ ζ∗ ≪ HB may permit improvement over accelerated or ordinary Minibatch SGD, but Local SGD cannot provide it.The paper leaves the design of methods for this medium-heterogeneity regime as an open question.
  • Appendix analysis: The resulting Minibatch SGD guarantees are stated separately under convex and strongly convex assumptions.The theorem gives a universal-constant bound for the average of iterates and a weighted-average guarantee in the strongly convex case.
  • Appendix analysis: The appendix derives convergence for the averaged iterate using specified step sizes and averaging weights, with separate schedules for strongly convex and non-strongly-convex cases.The schedules use κ = 8H/λ and a transition index t0 in the strongly convex analysis.

A.2 Accelerated Minibatch SGD for heterogeneous objectives

This section develops accelerated minibatch SGD guarantees for heterogeneous objectives by applying AC-SA to regularized objectives and verifying unbiasedness and variance properties. The resulting guarantees cover weakly convex and strongly convex cases.

  • Setup: Accelerated minibatch SGD analyzes H-smooth, λ-strongly convex objectives using unbiased stochastic gradients with variance bounded by σ2.The framework begins from classical accelerated SGD results and extends them to distributed minibatch gradients.
  • AC-SA: AC-SA maintains intertwined sequences and updates them using prescribed αt and γt step-size parameters over T stochastic-gradient iterations.The algorithm initializes xag_0 at x0, queries gradients at xmd_t, and iterates until T steps are completed.
  • Weakly convex reduction: Regularizing F with λ∥x−x0∥2/2 converts strongly convex guarantees into guarantees for weakly convex objectives.The regularization parameter can be optimized to obtain the weakly convex result.
  • Guarantees: The regularized AC-SA procedure achieves the stated weakly convex rate, while multi-stage AC-SA supplies the corresponding strongly convex guarantee.The section identifies these rates as minimax optimal for weakly convex functions and almost optimal or optimal under strongly convex assumptions.
  • Distributed application: Distributed minibatch gradients remain unbiased for the average objective, with variance obtained by substituting the distributed estimator into the accelerated SGD lemmas.The proof uses independent local iterates and then applies the previously established AC-SA results.

B Proof of Theorem 2

The proof constructs two local stochastic objectives whose average satisfies the required smoothness, convexity, variance, and heterogeneity conditions. A case analysis then establishes a Local SGD lower bound across stepsize regimes.

  • Construction: The lower-bound construction uses two local objectives and Gaussian-noise distributions, extending to M machines by assigning machines to the two objectives.For more than two machines, the resulting lower bound loses at most an (M−1)/M factor.
  • Construction: The constructed functions are H-smooth and λ-strongly convex, while their gradient variance is bounded by σ2.The auxiliary function is designed so the average objective has the required optimization properties and heterogeneity level.
  • Local SGD dynamics: Local SGD initialized at zero is analyzed coordinate-by-coordinate because the four coordinates of the constructed objectives are decoupled.The fourth coordinate provides the relevant dynamics for the lower-bound argument.
  • Lower bound: For any M, K, and R, the construction yields a Local SGD suboptimality lower bound for both convex and strongly convex assumptions.The theorem applies to any fixed stepsize η, under the stated condition H ≥ 16λ.
  • Case analysis: The proof combines three stepsize cases with standard first-order stochastic lower bounds to obtain separate convex and strongly convex conclusions.The cases isolate contributions from stochastic variance and heterogeneity, then combine them into the final bounds.

C Proof of Theorem 3

The proof bounds Local SGD by controlling local-iterate disagreement and then averaging the iterates under convex and strongly convex stepsize schedules. The resulting theorem gives guarantees under an additional heterogeneity condition.

  • Disagreement bounds: The analysis begins with technical lemmas that bound Local SGD’s disagreement between machines under fixed and decreasing stepsizes.The disagreement is controlled using the most recent synchronization time, with at most K−1 local steps between communications.
  • Theorem 3: Theorem 3 gives convex and strongly convex guarantees for the average of Local SGD iterates under additional condition (12).The displayed bound includes stochastic, optimization, and heterogeneity-dependent terms.
  • Convex case: For convex objectives, the proof uses a constant stepsize and bounds the average objective through convexity.The argument combines bounds on optimization error, stochastic noise, and disagreement.
  • Strongly convex case: For strongly convex objectives, the proof uses ηt = 2/[λ(a+t+1)] with a = 20H/λ and weighted averaging.This schedule ensures ηt ≤ 1/(10H) and supports the final weighted-error bound.
  • Limitation: The strongly convex proof may potentially achieve an exp(−KR) first term, but the derived recurrence makes the necessary schedule difficult to determine.This is an explicit limitation of the presented analysis rather than a claimed impossibility result.

D Details of Experiments

The experiments construct MNIST classification tasks with tunable heterogeneity and compare Local SGD, Minibatch SGD, and related guarantees. The theoretical discussion identifies regimes where accelerated minibatch SGD or SCAFFOLD is preferable.

  • Dataset: MNIST is split by digit into ten groups of approximately 6,000 examples, then reduced to 100 dimensions using PCA without other preprocessing.The dataset contains 60,000 training examples, with some discarded to equalize group sizes.
  • Tasks: Twenty-five binary classification tasks are formed by pairing even and odd digits, with even labels +1 and odd labels −1.The tasks are arbitrarily labeled task 1 through task 25.
  • Heterogeneity: Heterogeneity is controlled by mixing p·2n examples from each machine’s task with (1−p)·2n examples sampled from all tasks.The experiment evaluates p from 0.0 through 1.0.
  • Evaluation: Local and Minibatch SGD optimize logistic loss with stepsizes tuned separately for each p, K, and R, reporting the best average loss over four runs.The two methods use different log-scale stepsize grids.
  • Theory comparison: Accelerated Minibatch SGD is optimal for sufficiently high heterogeneity, while the corresponding communication requirement is within a logarithmic factor of the lower bound.The convex threshold is ζ∗ ≥ HB; the strongly convex statement is optimal up to log factors.
  • SCAFFOLD comparison: When all machines participate each round, SCAFFOLD does not improve over Minibatch SGD and adds terms to the guarantees.With only a random subset of machines, SCAFFOLD improves in some regimes but is worse in others, including some strongly convex regimes.
Loading 2006.04735v5…