On the Limits of Stochastic Push-Pull over Time-Varying Digraphs
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 neff≤ 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/√(neff T)). When p=1, the identity neff=n recovers the usual linear speedup for static digraphs. However, periodic networks can have neff=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.
Related
- Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization
- Goal-Oriented Communication and Control Co-Design via Semantic Push-Pull in Industrial IoT
- On the suboptimality of stochastic MPC with varying constraint horizon
- Elementary ratio and zero limits for varying recurrences
- Stochastic Sequential Feedback Optimization for Wind Farm Control under Time-Varying Inflow
BibTeX
@misc{wang2026limits,
title = {{On the Limits of Stochastic Push-Pull over Time-Varying Digraphs}},
author = {Feiming Wang and Yutong He and Sulaiman Alghunaim and Kun Yuan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32422},
eprint = {2610.32422},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32422},
}
RIS
TY - UNPB
TI - On the Limits of Stochastic Push-Pull over Time-Varying Digraphs
AU - Feiming Wang
AU - Yutong He
AU - Sulaiman Alghunaim
AU - Kun Yuan
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32422
UR - https://arxiv.org/abs/2610.32422
AB - 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_eff≤ 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/√(n_eff T)). When p=1, the identity n_eff=n recovers the usual linear speedup for static digraphs. However, periodic networks can have n_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.
ER -