Search papers, labs, and topics across Lattice.
This paper investigates decentralized stochastic gradient tracking in time-varying networks, establishing a framework under a uniform window-mixing condition that allows for effective disagreement reduction among agents. By employing a time-varying quadratic norm, the authors derive a one-step Lyapunov identity that facilitates the analysis of centroid and disagreement errors without needing to unroll the dynamics over communication windows. The results show that for smooth strongly convex objectives, the stochastic error term is $\widetilde{\mathcal O}(1/(NK))$, matching centralized mini-batch performance and achieving linear speedup after an initial transient phase.
Achieving linear speedup in decentralized stochastic optimization without unrolling dynamics could revolutionize how we approach distributed learning in dynamic environments.
We study decentralized stochastic gradient tracking over a time-varying network of $N$ agents under a uniform window-mixing condition. Products of $\tau$ consecutive doubly stochastic mixing matrices contract disagreement by a factor $\lambda<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.
