Stochastic push-pull may lose speedup on changing network connections
On the Limits of Stochastic Push-Pull over Time-Varying Digraphs
Machine Learning
Summary
Stochastic Push-Pull is a method that speeds up tasks shared across networked computers. It works well and gets faster as more computers join, but usually only when their connections don’t change. The authors show that when the network’s connections change periodically, this speedup can be much less, meaning the method doesn’t scale as well. They identify a smaller effective number of nodes that truly impact performance and confirm this with experiments.
What this means in practice
- •For distributed system engineers: Design and evaluate decentralized algorithms while accounting for reduced scalability on periodically changing network topologies.
- •For network protocol developers: Adjust synchronization and communication protocols to mitigate performance loss caused by time-varying network connectivity.
Authors
Feiming Wang, Yutong He, Sulaiman Alghunaim, Kun Yuan
Abstract
Stochastic Push-Pull achieves linear speedup with respect to the network size $n$ on static strongly connected digraphs, but whether this speedup persists on time-varying networks remains unclear. In this work, we construct a quadratic decentralized problem on period-two networks showing that stochastic Push-Pull may fail to attain linear speedup over time-varying digraphs. For $p$-periodic networks, we identify an effective node count $n_{\mathrm{eff}}\le n$ that governs the leading stochastic term. Specifically, for smooth nonconvex objectives, we establish convergence upper bounds and matching lower bounds for stochastic Push-Pull with constant stepsizes, both exhibiting the leading-order dependence $Θ(1/\sqrt{n_{\mathrm{eff}} T})$. When $p=1$, the identity $n_{\mathrm{eff}}=n$ recovers the usual linear speedup for static digraphs. However, periodic networks can have $n_{\mathrm{eff}}=o(n)$, demonstrating the loss of linear speedup under temporal variation. Numerical experiments illustrate effective-count scaling and the separation between static and periodic networks, consistent with our theoretical findings.