An improved convergence analysis for decentralized online stochastic non-convex optimization

II. ASSUMPTIONS AND THE GT-DSGD ALGORITHM

• The online setting gives each node private local data and noisy, unbiased gradient samples with bounded variance, over a balanced directed communication graph.The analysis assumes smooth local objectives; the global objective may additionally satisfy the PL condition, under which every stationary point is a global minimum.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

• For general smooth non-convex objectives, GT-DSGD can achieve network-independent performance matching centralized minibatch SGD when the iteration count is large enough.The paper contrasts this with prior results suggesting GT-DSGD is always network-dependent; under the stated regime, the work also reports a 1/n reduction in stochastic-gradient computations per node for an approximate stationary point.Source: §I · pp. 1–2
• Under the global PL condition, the paper establishes linear convergence up to steady-state error with constant step-sizes and order-optimal global sublinear rates on almost every sample path with stochastic-approximation step-sizes.The path-wise rates generalize prior decentralized stochastic-approximation analyses that were mostly under local convexity assumptions.Source: §I · pp. 1–2

III. MAIN RESULTS

• GT-DSGD replaces local stochastic-gradient descent directions with an auxiliary tracker that tracks a signal mimicking the global gradient.The paper writes the decentralized updates in matrix form and uses λ = ∥W − J∥ to characterize network connectivity.Source: §II · p. 3, §III · p. 3

A. General smooth non-convex functions

• The stationary gap decays as O(1/K) up to a steady-state error; its network-independent terms match centralized minibatch SGD, while network-dependent terms are O(α^2).With an appropriate constant step-size, the finite-horizon bound separates these centralized-comparable terms from the decentralized network effects.Source: A. General smooth non-convex functions · p. 3
• For K ≥ K_nc, GT-DSGD achieves network-independent linear speedup over centralized minibatch SGD, reducing stochastic-gradient computations per node by a factor of 1/n.This requires sufficiently many iterations and the step-size conditions described for Corollary 1.Source: A. General smooth non-convex functions · pp. 3–4
• Compared with DSGD, GT-DSGD is robust to local-global function heterogeneity, but its network-independent transient scales as O((1−λ)^−6) versus O((1−λ)^−4) for DSGD.GT-DSGD also requires two consecutive communication rounds per node per iteration.Source: A. General smooth non-convex functions · p. 4

B. Smooth non-convex functions under PL condition

• Under the PL condition, constant step-sizes yield linear convergence up to steady-state error, with a network-independent term matching centralized minibatch SGD and a network effect controlled by O(α^2).The analysis permits the PL condition on the global objective rather than requiring global strong convexity; with exact gradients, GT-DSGD converges linearly to an optimum.Source: B. Smooth non-convex functions under… · p. 4
• With decaying step-sizes, GT-DSGD has global sublinear convergence on almost every sample path under the PL condition, with polynomial-time decay rates that are order-optimal for general non-degenerate variances.The paper identifies this as the first such path-wise result for online decentralized stochastic optimization under non-convexity.Source: B. Smooth non-convex functions under… · pp. 4–5
• In expectation, GT-DSGD asymptotically achieves a network-independent O(1/k) rate under the PL condition, matching the Ω(1/k) oracle lower bound.After K_PL iterations, the rate matches centralized minibatch SGD up to constant factors; the transient improves condition-number dependence over prior results but is moderately worse in network dependence.Source: B. Smooth non-convex functions under… · p. 5

• The study uses directed exponential and undirected grid graphs with 16 nodes, plus an undirected geometric graph with 100 nodes.The associated second-largest singular values are 0.6, 0.93, and 0.99, respectively.Source: §IV · p. 5, Figure 1 · p. 6
• Two stochastic-gradient setups use randomly selected local samples or gradient noise with zero mean and bounded variance.Source: §IV · p. 5
• Performance is measured by average global function value across nodes, plotted against epochs for sampled-data runs and iterations for noise-based runs.Source: §IV · p. 5
• Experiments cover non-convex logistic regression, neural-network classification, and synthetic functions satisfying the global PL condition.Source: §IV · pp. 5–6
• Logistic-regression plots compare GT-DSGD across graphs with centralized minibatch SGD, while neural-network plots compare GT-DSGD with DSGD under heterogeneous data.Source: Figure 2 · p. 6, Figure 3 · p. 6, §IV · p. 6

A. Non-convex logistic regression for binary classification

• Across the a9a, w8a, and creditcard datasets, GT-DSGD matches centralized minibatch SGD and is graph-independent with an appropriate constant step-size, given enough iterations.The comparison uses directed exponential and grid graphs, each with 16 nodes, and centralized SGD with minibatch size 16.Source: A. Non-convex logistic regression for… · p. 6

B. Neural network for multiclass classification

• With heterogeneous node data, GT-DSGD significantly outperforms DSGD on Fashion-MNIST, CIFAR-10, and STL-10, demonstrating robustness to that setting.The experiment uses a 100-node geometric graph and a neural network with one 64-neuron hidden layer.Source: B. Neural network for multiclass… · p. 7

C. Synthetic functions that satisfy the global PL condition

• With αk = (k + 3)^-1, GT-DSGD matches centralized minibatch SGD across graphs after transient iterations, achieving an asymptotically network-independent O(1/k) rate.With constant step-sizes, it also converges linearly up to a steady-state error; smaller step-sizes reduce that error but slow convergence, and GT-DSGD reaches a smaller error faster than DSGD.Source: C. Synthetic functions that satisfy… · p. 7, Figure 5 · p. 7

V. CONVERGENCE ANALYSIS: THE GENERAL NON-CONVEX CASE

• Mixing contracts disagreement from consensus: ∥Wx − Jx∥ ≤ λ∥x − Jx∥.The tracking state satisfies yk+1 = gk for k ≥ 0.Source: §V · p. 7
• The network mean state moves in the direction of the average local stochastic gradients.The passage also states that the GT-DSGD iterates are square-integrable and have the indicated filtration measurability properties.Source: §V · pp. 7–8
• The next-iteration state-consensus error is bounded above by λ times the squared current state disagreement, plus αkλ times the gradient-tracking disagreement between yk+1 and its consensus projection.∥xk+1 − Jxk+1∥ ≤ λ∥xk − Jxk∥2 + αkλ∥yk+1 − Jyk+1∥.Source: §V · p. 8

A. A descent inequality

• The subsection establishes a key descent inequality characterizing the expected decrease in the value of the global objective function F over each iteration, under Assumptions 1–3 when 0 < αk ≤ 1/(2L).Source: A. A descent inequality · p. 8
• Unlike centralized SGD’s corresponding descent inequality, GT-DSGD’s bound includes an additional network consensus-error term, ∥xk − Jxk∥.The comparison is made with centralized stochastic gradient descent,.Source: A. A descent inequality · p. 8
• To establish convergence, the analysis controls the consensus perturbation jointly with the gradient-tracking error.This is the stated strategy for handling the additional term in the descent inequality.Source: A. A descent inequality · p. 8

B. Bounding the gradient tracking error

• The component terms are bounded using conditional unbiasedness, gradient-noise variance, smoothness, and consensus relations.The argument uses conditional measurability and the consensus bounds from Lemma 2.Source: B. Bounding the gradient tracking error · pp. 8–9
• The cross-term analysis uses the tracking update and mixing-matrix relations, with conditional measurability allowing expectation-based control.The derivation also invokes the mixing contraction and smoothness bounds.Source: B. Bounding the gradient tracking error · pp. 8–9
• Auxiliary bounds from Lemmas 5–7 are combined to obtain an upper bound on the gradient-tracking error.The resulting bound is stated under a step-size restriction involving λ.Source: B. Bounding the gradient tracking error · pp. 9–10

C. LTI dynamics

• The consensus and gradient-tracking process is jointly represented as a linear-time-invariant system built from Lemmas 2 and 8.The section uses this system to characterize the convergence analysis.Source: C. LTI dynamics · p. 10
• The analysis seeks a step-size range ensuring the system matrix has spectral radius below one, using a positive-vector criterion.The cited lemma states that Xx < x for a positive vector x implies ρ(X) < 1.Source: C. LTI dynamics · p. 10
• Lemma 11 bounds accumulated consensus error using accumulated averages of local exact gradients and stochastic-gradient variance, and this bound leads to a convergence result for general smooth non-convex functions.The theorem proof takes expectations of a descent inequality and sums it over iterations.Source: C. LTI dynamics · p. 11

VI. CONVERGENCE ANALYSIS UNDER PL CONDITION: CONSTANT STEP-SIZE

• The PL condition is used to refine the descent inequality and develop general bounds on GT-DSGD iterates.The section states that these bounds support the proof of Theorem 2.Source: §VI · p. 11
• The analysis combines inequalities from Lemmas 2, 14, and 15 into linear dynamics, then determines step-size conditions for the resulting matrix to have spectral radius below one.The proof uses the positive-vector criterion to bound the spectral radius.Source: §VI · p. 12
• Theorem 2 analyzes GT-DSGD with a constant step-size αk = α restricted by the bound α in (30).The proof applies the linear-dynamics and spectral-radius results to derive the theorem’s statements.Source: §VI · p. 12

VII. CONVERGENCE ANALYSIS UNDER PL CONDITION:

• Under appropriate step-sizes, stochastic gradient-tracking errors are uniformly bounded in mean square across iterations.This bound is also used in the following section.Source: §VII · p. 13
• Theorem 3 establishes almost-sure sublinear convergence under the specified stochastic-approximation step-sizes and the PL condition.The proof uses bounded tracking-error results and almost-supermartingale arguments.Source: §VII · pp. 13–14
• Theorem 3 considers step-sizes αk = δ(k + ϕ)^-ϵ, with δ ≥ 1/µ and ϵ in (0.5, 1].The proof constructs weighted processes and uses the Robbins–Siegmund almost-supermartingale convergence theorem.Source: §VII · p. 13

VIII. CONVERGENCE ANALYSIS UNDER PL CONDITION: ASYMPTOTICALLY OPTIMAL RATE IN MEAN

• Theorem 4 and Corollary 2 address the asymptotically optimal expected convergence rate and the transient time to network-independent performance under the PL condition.The section uses the step-size sequence referenced in [1].Source: §VIII · p. 14
• Theorem 4 derives an expected-rate bound by recursively applying an inequality for Ψk, defined using the expected normalized objective gap.The proof develops a non-asymptotic rate under step-size and parameter restrictions.Source: §VIII · pp. 14–15
• Corollary 2 gives conditions on k for the rate to be network-independent, requiring k to exceed a threshold involving K1 and K2.The proof derives a lower bound on k for this regime.Source: §VIII · pp. 15–16

• Under derived conditions, GT-DSGD matches centralized minibatch SGD for both general non-convex objectives and objectives satisfying the PL condition.Source: §IX · p. 16
• The results improve on prior theory, which suggested GT-DSGD was strictly worse than centralized minibatch SGD.Source: §IX · p. 16
• For a family of stochastic approximation step-sizes, GT-DSGD converges globally at a sublinear rate to an optimal solution on almost every sample path when the objective satisfies PL.Source: §IX · p. 16