# Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 32 references that are in the map.
- First posted on arXiv 8 Jun 2021.

## Builds on (most cited first, 18 of 18)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Linearly Converging Error Compensated SGD](https://mlsanity.com/paper/2010.12292/) (2020)
- [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Accelerated Distributed Nesterov Gradient Descent](https://mlsanity.com/paper/1705.07176/) (2017)
- [Multi-consensus Decentralized Accelerated Gradient Descent](https://mlsanity.com/paper/2005.00797/) (2020)
- [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)
- [Towards accelerated rates for distributed optimization over time-varying networks](https://mlsanity.com/paper/2009.11069/) (2020)
- [Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters](https://mlsanity.com/paper/1810.01053/) (2018)
- [An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints](https://mlsanity.com/paper/2102.11079/) (2021)
- [PANDA: A Dual Linearly Converging Method for Distributed Optimization over Time-Varying Undirected Graphs](https://mlsanity.com/paper/1803.08328/) (2018)
- [Decentralized and Parallel Primal and Dual Accelerated Methods for Stochastic Convex Programming Problems](https://mlsanity.com/paper/1904.09015/) (2019)

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

- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging](https://mlsanity.com/paper/2206.05091/) (2022)
- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [Optimal Algorithms for Decentralized Stochastic Variational Inequalities](https://mlsanity.com/paper/2202.02771/) (2022)
- [Online Federated Learning via Non-Stationary Detection and Adaptation amidst Concept Drift](https://mlsanity.com/paper/2211.12578/) (2022)
- [DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization](https://mlsanity.com/paper/2208.00779/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [DePRL: Achieving Linear Convergence Speedup in Personalized Decentralized Learning with Shared Representations](https://mlsanity.com/paper/2312.10815/) (2023)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [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)
- [Tight analyses of first-order methods with error feedback](https://mlsanity.com/paper/2506.05271/) (2025)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [Federated Composite Saddle Point Optimization](https://mlsanity.com/paper/2305.15643/) (2023)
- [A Stochastic Approximation Approach for Efficient Decentralized Optimization on Random Networks](https://mlsanity.com/paper/2410.18774/) (2024)
- [Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimization](https://mlsanity.com/paper/2411.15795/) (2024)

## Abstract (arXiv)

We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network whose links are allowed to change in time. We solve two fundamental problems for this task. First, we establish the first lower bounds on the number of decentralized communication rounds and the number of local computations required to find an ε-accurate solution. Second, we design two optimal algorithms that attain these lower bounds: (i) a variant of the recently proposed algorithm ADOM (Kovalev et al., 2021) enhanced via a multi-consensus subroutine, which is optimal in the case when access to the dual gradients is assumed, and (ii) a novel algorithm, called ADOM+, which is optimal in the case when access to the primal gradients is assumed. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.