# Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2018.

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

- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization](https://mlsanity.com/paper/2208.00779/) (2022)
- [Asynchronous speedup in decentralized optimization](https://mlsanity.com/paper/2106.03585/) (2021)
- [Byzantine-Robust Gossip: Insights from a Dual Approach](https://mlsanity.com/paper/2405.03449/) (2024)
- [Exposing the Vulnerability of Decentralized Learning to Membership Inference Attacks Through the Lens of Graph Mixing](https://mlsanity.com/paper/2412.12837/) (2024)
- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)
- [Distributed Finite-Sum Constrained Optimization subject to Nonlinearity on the Node Dynamics](https://mlsanity.com/paper/2203.14527/) (2022)
- [Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous Decentralized Optimization](https://mlsanity.com/paper/2207.07543/) (2022)
- [An Asynchronous Decentralized Algorithm for Wasserstein Barycenter Problem](https://mlsanity.com/paper/2304.11653/) (2023)
- [On Gossip Algorithms for Machine Learning with Pairwise Objectives](https://mlsanity.com/paper/2603.24128/) (2026)

## Abstract (arXiv)

In this paper, we study the problem of minimizing a sum of smooth and strongly convex functions split over the nodes of a network in a decentralized fashion. We propose the algorithm ESDACD, a decentralized accelerated algorithm that only requires local synchrony. Its rate depends on the condition number kappa of the local functions as well as the network topology and delays. Under mild assumptions on the topology of the graph, ESDACD takes a time O((τmax + Deltamax)√kappa/γln(ε-1)) to reach a precision ε where γ is the spectral gap of the graph, τmax the maximum communication delay and Deltamax the maximum computation time. Therefore, it matches the rate of SSDA, which is optimal when τmax = Omegaleft(Deltamaxright). Applying ESDACD to quadratic local functions leads to an accelerated randomized gossip algorithm of rate O( √θrm gossip/n) where θrm gossip is the rate of the standard randomized gossip. To the best of our knowledge, it is the first asynchronous gossip algorithm with a provably improved rate of convergence of the second moment of the error. We illustrate these results with experiments in idealized settings.