# Towards accelerated rates for distributed optimization over time-varying networks

arXiv: https://arxiv.org/abs/2009.11069 · HTML: https://mlsanity.com/paper/2009.11069/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2020.

## Built on by (most cited first, 10 of 10)

- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks](https://mlsanity.com/paper/2106.04469/) (2021)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks](https://mlsanity.com/paper/2102.09234/) (2021)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks](https://mlsanity.com/paper/2211.00533/) (2022)
- [Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks](https://mlsanity.com/paper/2405.18031/) (2024)
- [On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality](https://mlsanity.com/paper/2310.00419/) (2023)
- [Distributed Optimization via Energy Conservation Laws in Dilated Coordinates](https://mlsanity.com/paper/2409.19279/) (2024)
- [Near-Optimal Decentralized Stochastic Convex Optimization over Networks](https://mlsanity.com/paper/2606.04757/) (2026)

## Abstract (arXiv)

We study the problem of decentralized optimization over time-varying networks with strongly convex smooth cost functions. In our approach, nodes run a multi-step gossip procedure after making each gradient update, thus ensuring approximate consensus at each iteration, while the outer loop is based on accelerated Nesterov scheme. The algorithm achieves precision varepsilon > 0 in O(√kappagchilog2(1/varepsilon)) communication steps and O(√kappaglog(1/varepsilon)) gradient computations at each node, where kappag is the global function number and chi characterizes connectivity of the communication network. In the case of a static network, chi = 1/γ where γ denotes the normalized spectral gap of communication matrix W. The complexity bound includes kappag, which can be significantly better than the worst-case condition number among the nodes.