An Improved Analysis of Gradient Tracking for Decentralized Machine Learning

1 Introduction

• Data heterogeneity is a central challenge in decentralized training, and prior work shows that D-SGD is affected by non-IID data distributions.GT is described as independent of data heterogeneity and linearly convergent for noiseless, distributed strongly convex problems; the paper asks how it behaves with noise and on non-convex tasks.Source: §1 · pp. 1–2
• The paper develops an improved GT analysis with a new proof technique and uses its results to compare GT with D-SGD and D2.On topologies where D2 applies, the cited recent upper bound coincides with GT’s worst-case complexity, while D2 requires c to be constant.Source: §1 · p. 2
• The analysis improves GT’s dependence on network connectivity, a parameter represented by p in convergence rates.The introduction also says the upper bound improves the last two terms by a factor of c.Source: §1 · p. 2
• In the presence of stochastic noise, GT’s leading convergence-rate term is optimal and matches the unimprovable rate of all-reduce mini-batch SGD.The authors state this is the first derivation of this result in the non-convex setting.Source: §1 · p. 2
• In the non-asymptotic regime, GT’s rate depends on network topology; the authors introduce graph parameters to describe this dependence and verify it numerically.They say this topology dependence helps explain why worst-case behavior is rarely observed in practice.Source: §1 · p. 2

2 Related Work

• Decentralized optimization also includes gossip averaging, ADMM, dual averaging, primal-dual, block-coordinate, and gradient-propagation methods.The section notes that some methods based on gossip averaging work on non-convex problems and can train deep neural networks.Source: §2 · pp. 2–3
• Table 2 presents advances in non-convex GT convergence rates and reports improved dependence on the graph parameter p.The caption compares the paper’s result with existing rates.Source: Table 2 · p. 3
• EXTRA and decentralized primal-dual gradient methods are independent of data heterogeneity and converge linearly in the strongly convex, noiseless setting, but are not designed for non-convex tasks..Source: §2 · p. 3
• D2 and GT tolerate stochastic noise, are agnostic to data heterogeneity, and can be applied to non-convex objectives such as deep-learning training.The passage notes that D2’s applicability to time-varying topologies is unclear and restricts it to constant mixing topologies with a lower bound on the negative eigenvalue.Source: §2 · p. 3
• Prior GT analyses cover time-varying networks, strongly convex and non-convex objectives, stochastic settings, and variance reduction, among other cases.The cited work includes analyses of stochastic strongly convex objectives and stochastic non-convex functions.Source: §2 · p. 3

3 Setup

• Each of n nodes has a local objective, and communication is restricted to graph edges encoded by a mixing matrix W.Local objectives may be stochastic expectations over node-specific data distributions, with access to stochastic gradients.Source: §3 · pp. 3–4

3.1 Notation

• Node vectors are assembled as columns of a matrix, with the average vector replicated across columns.The notation also extends to matrices of local gradients.Source: §3.1 · p. 4

3.2 Algorithm

• Each node updates a model parameter and a tracking variable; the tracker follows the average local gradients and is used instead of a gradient in the model update.The matrix-form description identifies X and Y as the iterate and tracking-variable sequences.Source: §3.2 · p. 4

3.3 Assumptions

• The analysis assumes a symmetric doubly stochastic mixing matrix with p > 0; p relates to the spectral gap, while c ≥ p reflects the most negative eigenvalue.The setup also states smoothness and bounded-noise assumptions, with strong convexity used in some settings; c is constant for many practical graphs.Source: §3.3 · p. 5
• The authors note that c may be as small as p, in which case the strongly convex result does not improve on existing results; for many practical graphs, c is bounded by a constant.Increasing self-weights can ensure c = 1, and no explicit lower bound on c is required as an assumption.Source: §3.3 · p. 5

4.1 Main theorem—GT convergence in the general case

• The general theorem gives GT convergence bounds for non-convex, strongly convex, and general convex settings under the stated assumptions.The strongly convex case adds Assumption 3 with μ > 0; the general convex case uses μ ≥ 0.Source: §4.1 · p. 6
• With stochastic noise, the leading convergence-rate term is graph-parameter independent, matches all-reduce mini-batch SGD estimates, and is stated to be optimal.After a sufficiently long transient, GT achieves linear speedup in the number of workers; the transient depends on p and c, not data dissimilarity.Source: §4.1 · p. 6
• The proof framework permits several assumption relaxations, including different mixing matrices for x and y and local computation steps, though arbitrary time-varying mixing products may be non-symmetric.The text also describes possible relaxations to the bounded-gradient noise assumptions.Source: §4.1 · p. 6

4.2 Faster convergence on consensus functions

• For noise-free consensus functions, Theorem 3 gives an ε-accurate iterate within a stated complexity bound that does not depend on c.The passage identifies this as an improvement over the estimate from Theorem 2 for this special case.Source: §4.2 · p. 7

5.1 Parameter c

• If c is as small as p, Theorem 2 does not improve the existing strongly convex rate; whether c is tight generally remains open.Theorem 3 removes c in special cases.Source: §5.1 · p. 7

5.2 Comparison to prior GT literature

• Tables 1 and 2 compare strongly convex and non-convex GT rates, and the paper reports tightening all prior results.Source: §5.2 · p. 7

5.3 Comparison to other methods.

• GT removes dependence on data heterogeneity ζ, and in the homogeneous case matches D-SGD's rate on many practical graphs when c is constant.The discussion introduces this comparison for the strongly convex case and says analogous observations hold for other cases.Source: §5.3 · p. 7
• When c is bounded by a constant, the GT rate in Theorem 2 matches D2; this condition holds for many practical graphs.D2's rate applies under its stated mixing-matrix condition.Source: §5.3 · p. 7, §5.1 · p. 7

• The proof writes iterates as an average plus a consensus difference, then derives a recursion for the consensus distance.A key lemma enables replacing p with c in the final convergence rate by grouping repeated gradients and estimating their norm.Source: §6 · pp. 8–9
• The iteration matrix J is not contractive, so the proof bounds its powers and adds a provably non-increasing term before unrolling the consensus recursion.The bound uses the mixing parameter p.Source: §6 · pp. 8–9
• Careful tracking-error estimates avoid the data-dissimilarity parameter used in a related proof, while old parameter values become discounted after enough communication rounds.The proof describes this as a crucial difference from the pattern in [16].Source: §6 · p. 8
• The average iterate follows an update nearly identical to mini-batch SGD on a complete graph, supporting an SGD-like analysis of its sequence.The average update follows from GT and the doubly stochastic mixing matrix.Source: §6 · p. 8
• For Theorem 3's special case, the proof analyzes the average and consensus difference and uses diagonalizability of J′ to simplify the argument.Source: §6 · pp. 8–9

• The experiments use quadratic local functions, random normal initialization, and artificial stochastic gradient noise; the analysis measures loss after many steps at fixed γ.The setup also uses a large node count to make the first convergence-rate term smaller than the noise term.Source: §7 · pp. 9–10
• The loss scales linearly in 1/p as p varies, supporting the conclusion that this dependence cannot be further improved in the tested setup.The experiment uses n=300 nodes and varies p by interpolating a uniform-weight ring with a fully connected graph; c is held constant.Source: §7 · p. 10
• For c, the numerical results may suggest a better theoretical dependence, but the authors leave that question for future work.The c experiment uses a ring with n=300 nodes and reduces self-weights to vary c; p and γ are held constant in the figure caption.Source: §7 · p. 10

• The smallest eigenvalue of the mixing matrix strongly affects GT performance, but can often be controlled by choosing sufficiently large node self-weights.Source: §8 · p. 10
• The paper reports complexity bounds that improve over previous GT results and verifies the tightness of the convergence-rate second term numerically.Source: §8 · p. 10
• The proof technique might also support improved analyses of gossip methods with noncontractive mixing matrices, including directed-graph or row- or column-stochastic settings.Source: §8 · p. 10

A Proof of Theorem 3 — Consensus Functions

• The proof decomposes the error into consensus and optimization components.The optimization analysis identifies the average tracking quantity with the average iterate minus the optimum.Source: A Proof of Theorem 3 — Consensus… · p. 15
• For γ > 0, the 2 × 2 matrices are diagonalizable because their eigenvalues are distinct.The argument uses the eigenvalues of the mixing matrix to analyze the associated matrices.Source: A Proof of Theorem 3 — Consensus… · p. 16
• Figure 3 compares the upper bound with the true |λ(M_i)| for γ = 1 − |λ_i|.The bound is visualized for this step-size choice.Source: A Proof of Theorem 3 — Consensus… · p. 16

B Proof of Theorem 2 — General Case

• Theorem 10 gives GT Algorithm 1 constant-stepsize error bounds after T iterations (T > 2) for non-convex and strongly-convex cases; the latter requires Assumption 3 with µ > 0.The guarantee assumes a mixing matrix as in Definition 1 and Assumptions 1, 2, and 4.Source: B Proof of Theorem 2 — General Case · p. 17

B.1 Useful Inequalities

• Auxiliary lemmas bound mixing-matrix eigenvalue expressions and geometric sums using p and c, alongside standard norm inequalities.Source: §B.1 · pp. 17–18

B.2 Convex Cases

• The convex-case proof bounds a consensus recursion by separating stochastic noise and introduces a quantity non-increasing even when k < τ.Source: §B.2 · pp. 18, 19, 22

B.2.1 τ-slow Sequences

• The proof defines τ-slow increasing and decreasing sequences, including constant stepsizes and constant weights that satisfy the respective conditions for any τ.Source: §B.2.1 · p. 24

B.2.2 The Main Recursion

• The main recursion lemma gives a weighted recurrence for sequences with weights that are 64τ-slow increasing.Source: §B.2.2 · p. 25

B.2.3 Combining with the Descent Lemma 6

• The analysis obtains the rates of Theorem 2 for the strongly convex case, similarly to [16, Lemma 15], and for the weakly convex case, similarly to [16, Lemma 16].Source: §B.2.3 · p. 26

B.2.4 Strongly Convex Case

• The strongly-convex case uses a constant stepsize with geometrically increasing weights to bound the recurrence.Source: §B.2.4 · p. 26

B.3 Weakly Convex and Non Convex Cases

• For a = 0, the weakly convex and non-convex recurrence uses a constant stepsize and unit weights.Source: §B.3 · p. 27
• Lemma 26 provides a constant-stepsize tuning for three parameter cases in the weakly convex and non-convex analysis.The proof uses this tuning for its first three terms.Source: §B.3 · p. 27

B.4 Non-convex Case

• Under Theorem 2’s assumptions, Lemma 27 gives a descent bound for averages of Algorithm 1 iterates in the non-convex case [16].The bound uses a constant stepsize subject to a stated upper bound.Source: §B.4 · p. 28
• The non-convex analysis establishes a consensus-distance recursion with absolute constants C1, C2 > 0; its proof follows the convex-case approach, separates stochastic noise, and estimates terms T1 and T2.Source: §B.4 · pp. 28–29
• The proof combines the unrolled recursion with the non-convex descent lemma and uses Lemma 25 to obtain the final rate.The supplied passages do not state the rate’s formula.Source: §B.4 · p. 29

C Experimental Setup and Additional Plots

• The experiments measure f(¯x(t))−f⋆ after many steps with a constant stepsize chosen small enough to avoid divergence.The setup aims to measure the noise-related convergence level, with the other term kept at least an order of magnitude smaller using a fully connected topology.Source: C Experimental Setup and Additional… · p. 30

C.1 Problem Instances

• Setup A uses quadratic local objectives, random normal initialization, and additive Gaussian gradient noise.The noise is added to the gradients as ξ sampled from a Gaussian distribution.Source: §C.1 · p. 30
• Setup B uses quadratic objectives and structured noise aligned with eigenvectors for the smallest and second-largest mixing-matrix eigenvalues.The authors motivate this construction by noting that components in the smallest-eigenvalue eigenspace are amplified most.Source: §C.1 · p. 30

C.2 Graph Topologies and Mixing Matrices

• Interpolating a uniform-weight ring with a fully connected topology yields a mixing matrix whose c remains constant.The interpolation is defined as Wα = αWring + (1 − α)Wcomplete.Source: §C.2 · p. 30
• Reducing the ring's self-weight can make c small, and the experiments report its exact value from the smallest eigenvalue.The smallest eigenvalue is not generally equal to 2w − 1, except when w = 1/3.Source: §C.2 · p. 30

C.3 Additional Plots for Setup A

• With Gaussian noise, the plots show loss scaling compared with 1/p as p varies at fixed c, and compared with 1/c² as c varies at fixed p.The last subfigure varies c while holding p constant.Source: Figure 4 · p. 31

C.4 Additional Plots for Setup B

• With structured noise, the plots show loss scaling compared with 1/p as p varies at fixed c, and compared with 1/c² as c varies at fixed p.The noise variance is σ² = 1.Source: Figure 5 · p. 31
• The Figure 5 findings support the scaling predicted by theory.The reported experiments vary c and p under structured stochastic noise.Source: §C.4 · p. 31, Figure 5 · p. 31
• The plotted findings cannot replace a formal proof, which the authors leave for future work.Source: §C.4 · p. 31