Stochastic Gradient Tracking over Time-Varying Networks: One-Step Lyapunov Analysis
2026-08-17 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors study how a group of agents can collaboratively solve optimization problems over networks that change over time. They show that even if communication at individual steps is weak or disconnected, the network collectively improves agreement among agents over fixed time windows. By designing a special mathematical tool, they analyze errors in a simplified way and prove that their method achieves similar error rates as centralized methods, with efficiency improving linearly as more agents work together after some initial period.
decentralized optimizationstochastic gradient trackingtime-varying networksdoubly stochastic matricesLyapunov functionstrongly convex objectivesconvex optimizationconsensus algorithmslinear speedupcommunication graphs
Authors
Sulaiman A. Alghunaim
Abstract
We study decentralized stochastic gradient tracking over a time-varying network of $N$ agents under a uniform window-mixing condition. Products of $τ$ consecutive doubly stochastic mixing matrices contract disagreement by a factor $λ<1$, although individual matrices need not contract disagreement strictly and individual communication graphs may be disconnected. We construct a time-varying quadratic norm that turns this window contraction into an exact one-step Lyapunov identity. This leads to coupled one-step recursions for the centroid and disagreement errors, without unrolling the dynamics over communication windows. For smooth strongly convex objectives, the leading stochastic term is $\widetilde{\mathcal O}(1/(NK))$; for smooth convex objectives, it is $\mathcal O(1/\sqrt{NK})$. Both match their centralized mini-batch counterparts and yield linear speedup after a network-dependent transient.