Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks

Darina Dvinskikh, Anton Novitskii, Demyan Yarmoshik, Alexander Rogozin, Vladislav Matyukhin, Alexander Gasnikov

arXivarxiv/2609.33824Sep 27, 2026math.OCscore 0

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\|\leqβ$, WAVE reaches $ε$-consensus in $O((\sqrtχ+\min\lbraceβχ^2,χ\rbrace)\ln(e/ε))$ communication rounds. This rate matches the fixed-network $\sqrtχ$ dependence when $β=O(χ^{-3/2})$ and smoothly interpolates across the full…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.33824
curl -X POST /api/v1/records/arxiv/2609.33824/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.33824/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'