A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Anastasia Koloskova; Nicolas Loizou; Sadra Boreiri; Martin Jaggi; Sebastian U. Stich

Source-linked AI summary

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, Sebastian U. Stich

arXiv:2003.10422v3Mar 23, 2020cs.LGcs.DCmath.OCstat.ML

TL;DR

Decentralized SGD faces communication, changing-topology, and data-heterogeneity challenges. This paper unifies convergence analysis across decentralized SGD variants and derives rates that include linear convergence in overparametrized settings.

Problem
Decentralized SGD requires theoretical understanding under high communication cost, time-varying topologies, and data heterogeneity.
Method
The paper develops a unified convergence framework covering local SGD, synchronous updates, and pairwise gossip with adaptive network topology.
Results
The analysis provides tight convergence rates, improves convex and strongly-convex local-SGD rates, and proves linear convergence for overparametrized problems.
Takeaways & Limitations
The rates depend on the ratio p/τ, while high-noise optimization achieves linear speedup in the number of workers without dependence on τ or p.
Takeaways & Limitations
The dissimilarity parameter ζ̄^2 cannot generally be removed, and decentralized SGD without additional modifications cannot converge linearly.

Abstract

from arXiv · show

Decentralized stochastic optimization methods have gained a lot of attention recently, mainly because of their cheap per iteration cost, data locality, and their communication-efficiency. In this paper we introduce a unified convergence analysis that covers a large variety of decentralized SGD methods which so far have required different intuitions, have different applications, and which have been developed separately in various communities. Our algorithmic framework covers local SGD updates and synchronous and pairwise gossip updates on adaptive network topology. We derive universal convergence rates for smooth (convex and non-convex) problems and the rates interpolate between the heterogeneous (non-identically distributed data) and iid-data settings, recovering linear convergence rates in many special cases, for instance for over-parametrized models. Our proofs rely on weak assumptions (typically improving over prior work in several aspects) and recover (and improve) the best known complexity results for a host of important scenarios, such as for instance coorperative SGD and federated averaging (local SGD).

1. Introduction

The paper develops a unified convergence analysis for decentralized SGD variants that previously required separate treatments. Its framework covers local updates and diverse gossip schemes, yielding tight rates under weak assumptions across heterogeneous and iid settings.

Decentralized SGD methods face high communication costs, time-varying topologies, and heterogeneous data, motivating a unified theoretical analysis.
The analysis provides tight convergence rates for a large family of decentralized SGD variants and improves or recovers prior results under more general or weaker assumptions.
The framework covers local updates, synchronous and pairwise gossip, and time-varying or randomly sampled mixing distributions.
The results cover both heterogeneous and iid local SGD settings, with improved convex rates and best known non-convex rates under weaker assumptions.
Lower bounds confirm tightness on strongly convex functions, while experiments verify the theoretical behavior and the effects of noise and data diversity.

2. Related Work

Related work spans decentralized consensus, stochastic gradient methods, federated learning, client drift under heterogeneous data, and communication-reduction techniques. The paper focuses on local updates rather than gradient compression.

Decentralized optimization includes gossip protocols, gradient methods combined with averaging, and structure-specific approaches such as ADMM and primal-dual methods.
Decentralized stochastic gradient methods have attracted attention, including implementations for fully decentralized networks and federated learning's star-shaped topology.
Heterogeneous data can induce client drift because each node moves toward its local minimizer, which may differ substantially from the global minimizer.
Communication-reduction research includes gradient compression and local updates; this work focuses on local steps, which are practical but theoretically challenging.

3. Setup

The setup distributes stochastic component functions across nodes without restricting their data distributions, and imposes smoothness with additional convexity when needed. Noise and function diversity are characterized through local assumptions around the optimum or globally for non-convex analysis.

The distributed stochastic optimization problem assigns stochastic component functions and their data distributions to n nodes, including empirical risk minimization as a special case.
The formulation recovers deterministic distributed optimization when each node's empirical distribution contains one element.
No assumptions are imposed on local data distributions, allowing local minimizers to be far from the global minimizer in heterogeneous settings.
All theoretical results assume smoothness, while some results additionally assume µ-convexity or strong convexity.
For convex analysis, noise and function diversity are measured at the optimum, where the noise level is denoted ¯σ2 and function diversity by ¯ζ2.
The non-convex assumption allows noise and diversity bounds to grow with the gradient norm rather than requiring a uniform variance bound everywhere.
The notation tracks node iterates and their averages, while mixing matrices may be sampled from time-varying distributions and can include identity matrices representing no communication.

4. Decentralized (Gossip) SGD

The framework performs local stochastic gradient updates followed by decentralized gossip averaging, with mixing matrices that may vary across iterations or be sampled from changing distributions. Its convergence analysis uses an expected consensus condition over blocks of mixing steps rather than requiring every individual step to contract.

Generalized decentralized SGD: Each iteration combines local stochastic gradient updates with a consensus operation that averages neighboring workers’ values.Communications occur only between connected nodes, and the mixing matrix encodes both network structure and averaging weights.
Generalized decentralized SGD: Mixing matrices may change over iterations and may be sampled from time-varying distributions, including no-communication choices such as the identity matrix.The framework therefore supports adaptive communication patterns rather than a fixed topology alone.
Mixing matrices: The analysis assumes symmetric, doubly stochastic mixing matrices, which preserve the network-wide average while promoting consensus.The expected mixing behavior is described through the spectrum of the random mixing process and the distance to the row-wise average.
Expected consensus rate: Consensus need only improve in expectation over each block of τ consecutive mixing steps, not at every individual realization.This is the paper’s novel expected consensus-rate assumption.
Expected consensus rate: The blockwise assumption avoids requiring strong connectivity after every τ steps and can yield tighter bounds, although symmetry makes the setting less general than some prior work.A single randomly sampled edge can produce expected progress, whereas connectivity guarantees may require Ω(n) pairwise communications.
Pairwise gossip: For pairwise randomized gossip, the mixing parameter is p = ρ(G)/|E|, linking convergence behavior to the graph’s algebraic connectivity and edge count.The parameter p is also related to graph mixing time and diameter.

5. Examples Covered in the Framework

The framework recovers centralized and decentralized SGD and extends to sparse gossip, local updates, randomized mixing, and changing topologies. It therefore unifies several previously separate decentralized optimization algorithms under one analysis.

Constant mixing: A constant fully connected mixing matrix recovers centralized mini-batch SGD, while an arbitrary connected constant matrix recovers decentralized SGD.These appear as the simplest constant-topology instances of the general algorithm.
Sparse gossip: Sparse-topology variants include MATCHA, pairwise randomized gossip, repeated pairwise gossip, randomized subgraph gossip, and clique gossip.These methods reduce communication by selecting edges or subgraphs rather than averaging over the complete network.
Local updates: Loopless local decentralized SGD mimics local SGD by applying a fixed mixing matrix only probabilistically, with its mixing parameter reduced by a factor of τ.The loopless formulation avoids explicitly handling local steps in the analysis.
Local updates: The framework covers alternating decentralized SGD and local SGD, including complete-graph averaging every τ iterations with local steps between averaging rounds.It also allows decentralized local SGD with arbitrary or randomly sampled mixing matrices.
Changing topology: The framework supports nonperiodic time-varying graphs whenever every τ-step composition satisfies the expected consensus assumption.This extends beyond algorithms with fixed or periodic communication structures.

6. Convergence Result

The paper derives convergence guarantees for a broad family of decentralized SGD schemes under heterogeneous data, stochastic noise, local updates, and changing communication. The rates clarify when convergence is linear, how stochasticity and worker dissimilarity affect optimization, and how communication parameters enter the bounds.

General convergence results: Theorem 2 provides iteration-complexity bounds for non-convex, convex, and strongly-convex decentralized SGD schemes under the stated assumptions.The framework covers the convergence results for schemes fitting Algorithm 1, with target accuracy ϵ reached using a suitable constant stepsize.
Strongly-convex case: Strongly convex convergence decreases exponentially fast, with dependence on L/(µp) and communication interval τ.The τ dependence cannot generally be improved, although acceleration may improve the dependence on L/(µp).
Stochastic terms: When stochastic noise satisfies ¯σ2 > 0, the dominant term gives linear speedup in the number of workers n and is independent of τ, p, and ¯ζ2.For T = Ω(τn/p), the second variance-dependent term is dominated by the first.
Optimization terms: With ¯σ2 = 0 but ¯ζ2 > 0, decentralized SGD converges only sublinearly, and the dependence on dissimilarity cannot generally be removed.Theorem 3 establishes this necessity for strongly convex and smooth objectives with non-fully-connected constant mixing.
Communication dependence: The rates depend on the ratio p/τ rather than on p or τ separately, while fully connected mixing recovers the mini-batch SGD rate.For p = 1, the second term is multiplied by (1 − p), removing that contribution and recovering the mini-batch case.
Special cases: Overparametrized settings with ¯σ2 = ¯ζ2 = 0 admit linear convergence for decentralized SGD, similarly to mini-batch SGD.The paper states that the corresponding rate is optimal up to acceleration.

7. Special Cases: Highlights

The framework covers local SGD and related decentralized variants, recovering or improving convergence results across convex, non-convex, iid, and non-iid settings.

Framework scope: The analysis supports additional variants and combinations beyond the examples studied, enabling flexible scheme design for future applications.The paper leaves trade-offs among these approaches for future work.
Local SGD: Local SGD improves previous convex rates and recovers the best known non-convex rates under a more general analysis.These rates remain dominated by large-batch SGD and do not match iid lower bounds.
Decentralized SGD: The non-convex results recover prior best rates in both iid and specific non-iid settings, while also covering convex and deterministic cases.The iid case is characterized by zero function dissimilarity.
Decentralized SGD: The framework improves the best known strongly convex decentralized SGD rates and recovers the best known non-convex rates.The cited comparison concerns decentralized SGD results.

8. Experiments

Experiments vary noise, function similarity, and topology to test whether observed strongly convex convergence matches the theory's predicted dependencies.

Setup: The experiments use least-squares objectives whose function similarity is controlled by ¯ζ2 and whose stochastic noise is controlled by added Gaussian gradient noise.The study uses ring, two-dimensional torus, and fully connected topologies with tuned stepsizes.
Results: In the high-noise regime, topology and function similarity do not affect iteration counts because the noise-dependent term dominates.The same experiments observe linear rates when both noise and function dissimilarity vanish.
Results: Increasing ¯ζ2 by a factor of 10 increases iterations by approximately a factor of 10 for fixed topology.This behavior follows the corresponding dissimilarity-dependent term in the convergence rate.
Results: The iteration-count difference between torus and ring topologies scales approximately linearly with their mixing-parameter ratio.The paper relates this scaling to Θ(n).

9. Extensions

The paper extends its framework through matrix-form decentralized SGD, recursive convergence analysis, and flexible step-size and weighting conditions.

Future extensions: The framework can be extended with gradient compression or overlapping communication, but those techniques are not analyzed here.The paper identifies both as directions for additional distributed-training speedups.
Algorithmic extension: Matrix notation expresses each iteration as stochastic gradient updates followed by gossip averaging with a sampled mixing matrix.The matrix formulation is given as Algorithm 2.
Proof strategy: The proof bounds optimization progress and consensus distance, then combines their recursions to derive Theorem 2's rates.Separate lemmas handle convex, weakly convex, and non-convex cases.
Convex analysis: For convex cases, the analysis tracks average-iterate distance and function suboptimality under assumptions on smoothness, convexity, noise, and mixing.The resulting recursion uses parameters tied to curvature, variance, and network behavior.
Non-convex analysis: For non-convex objectives, the analysis tracks average function suboptimality and gradient norms while controlling consensus error.The non-convex lemmas use a constant-step-size condition involving smoothness and problem parameters.
Tuning conditions: The framework permits slow-changing step sizes and weights, with explicit examples including constant step sizes and constant weights.These sequence conditions support the recursive proof machinery.

A.4. Improved rate when τ = 1 (recovering mini-batch SGD convergence results)

When τ = 1, the consensus analysis yields an improved rate whose middle term is multiplied by (1 −p), recovering mini-batch SGD for fully connected graphs.

Improved rate: When τ = 1, the improved analysis multiplies the middle convergence term by (1 −p).The improvement applies to strongly convex, weakly convex, and non-convex cases.
Mini-batch recovery: For p = 1, corresponding to a fully connected graph, the improved rate recovers the mini-batch SGD convergence rate.The improvement arises because both iterates and stochastic gradients are averaged in the one-step update.
Proof ingredients: The mixing matrices preserve the average of the iterates, which supports the average-iterate descent analysis.This property is used in both convex and non-convex proofs.
Proof ingredients: The proof combines descent and consensus recursions under smoothness, convexity where required, noise, and mixing assumptions.The convex proof requires both fi and Fi to be convex, while the non-convex proof uses separate smoothness and noise conditions.
Consensus analysis: Consensus recursions distinguish times after a completed τ-step block from intermediate times within that block.Separate lemmas handle both regimes in convex and non-convex analyses.
Recursion framework: A generic recursion lemma combines consensus and optimization sequences using slowly varying step sizes and weights.The resulting conditions include explicit bounds on the step size.

Term

The numerical experiment verifies that decentralized SGD’s strongly convex noiseless convergence rate is not linear under nonzero heterogeneity and closely follows the theoretical bounds. Results compare iteration scaling on a ring and a 2-d torus.

Convergence behavior: The noiseless strongly convex convergence is not linear when the heterogeneity measure ¯ζ2 is positive.Theorem 2’s upper bound and Theorem 3’s lower bound indicate this behavior, which the numerical experiment tests.
Experimental setup: Figure 3 plots target accuracy ϵ through 1/√ϵ on the x-axis against iterations to convergence Tϵ on the y-axis.The stepsize is tuned separately for each target accuracy to minimize the required iterations.
Experimental results: Both the ring and 2-d torus results form approximately straight lines, as predicted for the strongly convex case.The experiment uses ¯σ2 = 0, ¯ζ2 = 10, n = 25, and d = 10.
Network comparison: 13.13 is the observed ratio of fitted slopes, matching the 13.142 ratio of the torus and ring spectral gaps.The slopes are 30.2 and 2.3, while the corresponding mixing parameters are 0.276 and 0.021.