Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks
Abstract
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 χ bounds the network condition number and successive communication operators satisfy |Lk+1−Lk|≤β, WAVE reaches ε-consensus in O((√χ+min{βχ2,χ})ln(e/ε)) communication rounds. This rate matches the fixed-network √χ dependence when β=O(χ−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 τ rounds apart, WAVE reaches ε-consensus in O((√χ+χ/τ)ln(e/ε)) communication rounds. Finally, we use WAVE as the consensus step in an accelerated decentralized optimization method for α-smooth convex local objectives with a μ-strongly convex average. For sufficiently slow network variation, every agent obtains an ε-solution to the global optimization problem after Õ(√(α/μ) √χ) communication rounds, matching the fixed-network dependence.
Related
- Resilient Decentralized Preconditioned Stochastic Proximal Optimization with Gradient Sketching over Time-Varying Networks
- Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization
- Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization
- Near-Optimal Decentralized Stochastic Convex Optimization over Networks
- Group Distributionally Robust Optimization over Decentralized Networks
BibTeX
@misc{dvinskikh2026accelerated,
title = {{Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks}},
author = {Darina Dvinskikh and Anton Novitskii and Demyan Yarmoshik and Alexander Rogozin and Vladislav Matyukhin and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33824},
eprint = {2609.33824},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33824},
}
RIS
TY - UNPB
TI - Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks
AU - Darina Dvinskikh
AU - Anton Novitskii
AU - Demyan Yarmoshik
AU - Alexander Rogozin
AU - Vladislav Matyukhin
AU - Alexander Gasnikov
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33824
UR - https://arxiv.org/abs/2609.33824
AB - 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 χ bounds the network condition number and successive communication operators satisfy |L_k+1−L_k|≤β, WAVE reaches ε-consensus in O((√χ+min{βχ^2,χ})ln(e/ε)) communication rounds. This rate matches the fixed-network √χ dependence when β=O(χ^−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 τ rounds apart, WAVE reaches ε-consensus in O((√χ+χ/τ)ln(e/ε)) communication rounds. Finally, we use WAVE as the consensus step in an accelerated decentralized optimization method for α-smooth convex local objectives with a μ-strongly convex average. For sufficiently slow network variation, every agent obtains an ε-solution to the global optimization problem after Õ(√(α/μ) √χ) communication rounds, matching the fixed-network dependence.
ER -