Source-linked AI summary
Tighter Theory for Local SGD on Identical and Heterogeneous Data
Ahmed Khaled, Konstantin Mishchenko, Peter Richtárik
TL;DR
Local SGD must distinguish identical from heterogeneous data because averaging locally optimized solutions may not minimize the true objective. The paper analyzes both regimes under weaker assumptions, covering arbitrarily heterogeneous data and improving convergence theory for identical data.
Problem
With dissimilar data, locally running SGD can produce solutions whose average does not minimize the true objective, creating convergence challenges for Local SGD.
Method
The paper analyzes Local SGD separately for identical and heterogeneous data, including an analysis that applies to arbitrarily heterogeneous data without assuming similarity between local data or gradients.
Results
The identical-data analysis provides the fastest known convergence rate under weaker assumptions than prior work, while the heterogeneous-data analysis applies to arbitrarily heterogeneous data.
Takeaways & Limitations
Data heterogeneity is a central difficulty for Local SGD because local solutions may not align with the true objective, whereas identical data enables efficient scalable training.
Takeaways & Limitations
A prior analysis relies on a bounded quantity tied to convergence and uses it to upper-bound H, preventing calculation of communication complexity.
Abstract
from arXiv · showhide
We provide a new analysis of local SGD, removing unnecessary assumptions and elaborating on the difference between two data regimes: identical and heterogeneous. In both cases, we improve the existing theory and provide values of the optimal stepsize and optimal number of local iterations. Our bounds are based on a new notion of variance that is specific to local SGD methods with different data. The tightness of our results is guaranteed by recovering known statements when we plug $H=1$, where $H$ is the number of local steps. The empirical evidence further validates the severe impact of data heterogeneity on the performance of local SGD.
1 Introduction
The paper studies how local SGD can reduce communication while retaining convergence guarantees across identical and heterogeneous data regimes. It argues that heterogeneous data require weaker, more meaningful assumptions than bounded gradient dissimilarity and motivates sharper communication analyses.
- Local SGD and data regimes: Local SGD performs several SGD iterations on each node before averaging, reducing communication compared with minibatch SGD.Its theory has developed separately for identical and heterogeneous data.
- Identical and heterogeneous data: Identical-data analysis seeks faster convergence under weaker assumptions, while heterogeneous-data analysis must account for local objectives that may differ.In the heterogeneous case, local SGD can produce solutions whose average does not minimize the true objective.
- Identical and heterogeneous data: Federated learning operates in a highly non-i.i.d. regime, making arbitrary data heterogeneity central to the analysis of Local SGD.The paper presents an analysis applying to arbitrarily heterogeneous data, whereas previous work assumed similarity between data or local gradients.
- Communication efficiency: The paper asks how many communications are needed to reach accuracy ε and, equivalently, how large the synchronization interval H can be.Communication is emphasized because it can be especially expensive in federated learning.
- Prior theory: Existing theory compares local SGD bounds across convex settings, with the paper claiming superior strongly convex rates under less restrictive assumptions than prior work.The related-work discussion also identifies a gap in understanding Local SGD despite its empirical use.
- Limits of prior assumptions: Prior heterogeneous-data analyses commonly assume bounded dissimilarity, bounded gradient diversity, or bounded local gradients.The paper argues bounded-gradient assumptions can be pathological, less insightful, or vacuous because they constrain both gradients and function differences.
3 Settings and Contributions
The paper analyzes Local SGD under identical and heterogeneous data using smoothness, convexity, and stochastic-gradient assumptions tailored to each regime. It derives improved convergence results for both settings, including arbitrary convex smooth finite-sum problems, and validates the theory experimentally.
- Problem settings: The analysis distinguishes identical data, where nodes estimate the gradient of a shared function, from heterogeneous data, where node m estimates ∇f_m.The paper models these regimes with different stochastic-gradient assumptions and convergence rates.
- Problem settings: Assumption 2 uses bounded stochastic-gradient variance, but it typically fails for finite-sum problems, motivating the paper’s alternative stochastic-gradient model.The alternative assumption requires per-sample losses to share the objective’s smoothness and strong-convexity parameters.
- Contributions: Under identical data and strong convexity, the paper proves an improved Local SGD iteration complexity for ε-accurate squared distance, recovering convergence for H=1 and H=T.For the merely convex case, it also reports an iteration-complexity result for ε-accurate functional suboptimality.
- Contributions: The same ε-dependence holds under the stochastic-gradient model for both strongly convex and merely convex objectives, yielding the first results for arbitrary convex smooth finite-sum problems.This extends the analysis beyond settings previously explored for Local SGD.
- Contributions: For heterogeneous data, Local SGD achieves an ε-accurate functional-suboptimality guarantee under T=Ω(M^3H^4), without restrictive gradient assumptions.The paper characterizes this as the first analysis to capture true data heterogeneity between nodes.
- Experiments: Experiments with logistic regression on multiple datasets investigate how heterogeneity affects Local SGD convergence speed.These experiments are presented as verification of the theoretical results.
4 Convergence Theory
The analysis shows that local SGD matches Minibatch SGD up to synchronization-dependent error terms, with tighter guarantees for identical data and additional heterogeneity dependence for different data. It derives communication-efficient choices of stepsize and local-step interval, while recovering Minibatch SGD when H=1.
- Proof strategy: The proof bounds iterate deviation from the average through a sequence V_t and controls these terms using the synchronization interval H.The recurrence follows SGD up to an error proportional to V_t, which is then bounded individually or over an epoch.
- Identical data: For identical data, local SGD has the same convergence behavior as Minibatch SGD plus an additive error controlled by H.When H=1, the error term vanishes and the ordinary Minibatch SGD rate is recovered.
- Identical data: Choosing H=O(T/M) yields an asymptotic convergence rate with linear speedup in M, while requiring approximately T/H communication steps.The resulting communication complexity is ˜Ω(M), up to constants and logarithmic factors.
- Identical data: Given T steps, the optimal identical-data interval is H=1+⌊T/(κM)⌋, achieving communication complexity ˜Ω(min(T,κM)).Matching Minibatch SGD guarantees requires H=O(T/(κM)) under the stated regime.
- Finite-sum setting: The finite-sum analysis extends the convergence guarantees under Assumption 3, including identical-data strongly convex and convex cases.The paper states that these results apply to arbitrary convex and smooth finite-sum problems and preserve the Minibatch SGD rate up to problem-independent constants and polylogarithmic factors.
- Heterogeneous data: For convex heterogeneous data, convergence includes dependence on σ²_dif, and the synchronization-interval dependence is quadratic rather than linear.The heterogeneity measure can vary substantially with how data are distributed, and matching identical-data convergence requires more frequent communication.
5 Experiments
Experiments evaluate local SGD on logistic regression datasets under identical and heterogeneous data, emphasizing communication cost, local-step count, and convergence behavior. Heterogeneous data can make local methods much faster than synchronized methods when communication is expensive and only imprecise convergence is required.
- Logistic regression experiments used LIBSVM datasets with ℓ2 regularization of order 1/n and MPI on parallel CPU cores.
- Identical Data: Figure 2 reports identical-data results on ‘a9a’ for stepsize 1/L, where every local-iteration setting reached a neighborhood within few communication rounds.The caption attributes this behavior to large stepsizes.
- Heterogeneous Data: Figure 3 compares heterogeneous-data convergence on ‘a5a’ across local-step counts, including fully synchronized gradient descent at one local step.The plots vary communication-round convergence, wall-clock time, and communication cost.
- Identical Data: The identical-data experiments observed convergence to neighborhoods with different radii for stepsizes 1/L and 0.05/L.
- Heterogeneous Data: When communication is significantly more expensive than gradient computation, local methods are much faster for imprecise convergence.
7 Basic Facts and Notation
This section establishes notation for synchronization times, epochs, stochastic gradients, Bregman divergence, and variance decompositions used in the analysis. It also records standard convexity, smoothness, linear-algebra, and expectation facts.
- The section introduces stochastic-gradient notation, including gradients at time t and their expectation.
- An epoch is the sequence of timesteps between two synchronizations, indexed by consecutive synchronization timestamps.
- The proofs use variance decomposition for random vectors and its finite-valued-vector specialization.
- Bregman divergence associated with f is defined as D_f(x,y) = f(x) − f(y) − ⟨∇f(y), x − y⟩.
- The section also invokes Jensen’s inequality, smoothness and convexity propositions, and elementary linear-algebra inequalities.
8 Proofs for Identical data under Assumption 2
These proofs derive identical-data convergence results under Assumption 2 by combining variance bounds, conditional updates, and recursive inequalities. The argument culminates in theorem statements obtained by averaging and iterating the bounds.
- The proof analyzes the averaged iterate and local iterates between synchronization points using conditional expectations.
- Gradient deviations are decomposed into terms involving local deviations, average gradients, and stochastic-gradient variance.
- Smoothness, Jensen’s inequality, and Assumption 2 bound the resulting terms in the one-step recursion.
- The analysis combines lemmas for identical data with gradient-variance bounds and recursively iterates the resulting inequality.
9 Proofs for identical data under Assumption 3
These proofs develop identical-data bounds under Assumption 3 by controlling individual gradient noise, iterate variance, gradient deviations, and epoch-level disagreement. The resulting recursions yield convergence theorems under explicit stepsize conditions.
- The proof strategy begins with individual gradient variance and perturbed-iterate bounds for identical data.
- The iterate variance across nodes is defined relative to the mean, and the noise at the optimum is separately identified.
- The final theorem proofs combine epoch decompositions, double counting, and Jensen’s inequality under additional stepsize constraints.
- A single-iterate optimality-gap analysis requires γ ≤ 1/[4L(1 + 2/M)].
- Average gradient variance reduction and epoch iterate deviation bounds control disagreement over at most H local steps.
10 Proofs for Heterogeneous data
The heterogeneous-data proof develops lemmas controlling local-update variance, distances, and optimality gaps, then combines them into convergence recursions under stepsize restrictions. The analysis also establishes that more local iterations reduce communication rounds needed to reach a solution neighborhood.
- Supporting lemmas: The proof bounds heterogeneous-data local-update terms using strong convexity, smoothness, convexity, Jensen’s inequality, and independence.These bounds control variance, gradient norms, Bregman divergences, and iterate-related terms.
- Supporting lemmas: γ ≤ 1/(4L p(H−1)) is imposed in Lemma 13 to control accumulated local-update effects within synchronization intervals.The argument uses intervals of at most H local steps and bounds t − t_p by H − 1.
- Optimality-gap recursion: The single-recursion lemma contracts the squared distance by (1 − γµ) while adding local-variance, Bregman-divergence, and stochastic-variance terms.For γ ≤ 1/(8L), the proof simplifies the coefficients using 1 − 4γL ≥ 1/2 and 1 + 2γL ≤ 5/4.
- Communication consequence: The final heterogeneous-data analysis concludes that more local iterations require fewer communication rounds to reach a neighborhood of the solution.This communication benefit is stated alongside the proof’s recursive convergence bounds.
11 Extra Experiments
The extra experiments extend the main experimental setting to additional datasets, with Figure 5 covering identical data and Figure 6 covering heterogeneous data.
- Figure 5: Figure 5 reports experiments with identical data.The experiments use the same setting described in the main text but a different dataset.
- Figure 6: Figure 6 reports experiments with heterogeneous data.It uses the same experimental setting as the main text with a different dataset.
- Experimental setup: The additional experiments vary the datasets while retaining the main-text experimental setting.The passage explicitly describes both figures as using the same setting with different datasets.
12 Discussion of Dieuleveut and Patel (2019)
The discussion critiques an earlier identical-data analysis for relying on a bounded iterate-distance quantity that may imply bounded gradients and depend on convergence. It argues that this assumption can make the resulting communication complexity unavailable.
- Prior assumptions: The earlier analysis assumes a Hessian Lipschitz constant and thrice differentiability for general non-quadratic functions.The discussion identifies these conditions in the formulation of the prior result.
- Assumption critique: The quantity G is criticized because assuming it bounded may also imply bounded gradients, weakening the claimed improvement over Stich (2019).The discussion states that the relationship makes the improvement unclear.
- Communication complexity: Because G depends on algorithmic convergence and also bounds H, the prior analysis may use a circular argument and cannot calculate communication complexity.The discussion links G’s definition to the convergence argument and to the local-iteration bound.