{"id":"arxiv/2610.32422","url":"https://arxiv.org/abs/2610.32422","tags":["math.OC","cs.LG"],"score":0,"title":"On the Limits of Stochastic Push-Pull over Time-Varying Digraphs","domain":"math.OC","source":"arxiv","authors":["Feiming Wang","Yutong He","Sulaiman Alghunaim","Kun Yuan"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-23","reactions":{}}