Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks

We study average consensus over slowly time-varying networks and its application to decentralized optimization. We introduce WAVE, a windowed Chebyshev method that limits the accumulated effect of network variation by restarting the recurrence after finite windows. If $\chi$ bounds the network condition number and successive communication operators satisfy $\Vert L_{k+1}-L_k\Vert \le \beta$, WAVE reaches $ϵ$-consensus in $O((\sqrt{\chi }+\min \{\beta {\chi }^2,\chi \})\ln (e/ϵ))$ communication rounds. This rate matches the fixed-network $\sqrt{\chi }$ dependence when $\beta =O({\chi }^{-3/2})$ and smoothly interpolates across the full range of network variation. For piecewise-constant networks where each change is detected when it occurs and consecutive changes are at least $\tau$ rounds apart, WAVE reaches $ϵ$-consensus in $O((\sqrt{\chi }+\chi /\tau )\ln (e/ϵ))$ communication rounds. Finally, we use WAVE as the consensus step in an accelerated decentralized optimization method for $\alpha$-smooth convex local objectives with a $\mu$-strongly convex average. For sufficiently slow network variation, every agent obtains an $ϵ$-solution to the global optimization problem after $\tilde{O}(\sqrt{\alpha /\mu }\sqrt{\chi })$ communication rounds, matching the fixed-network dependence.