# Accelerating Decentralized Optimization via Overlapping Local Steps

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 33 references that are in the map.
- First posted on arXiv 4 Jan 2026.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [A Survey on Distributed Machine Learning](https://mlsanity.com/paper/1912.09789/) (2019)
- [Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/1802.09941/) (2018)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms](https://mlsanity.com/paper/1808.07576/) (2018)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [Decentralized Gradient Tracking with Local Steps](https://mlsanity.com/paper/2301.01313/) (2023)
- [Communication-Efficient Federated Learning with Compensated Overlap-FedAvg](https://mlsanity.com/paper/2012.06706/) (2020)
- [Local Exact-Diffusion for Decentralized Optimization and Learning](https://mlsanity.com/paper/2302.00620/) (2023)
- [On the Performance of Gradient Tracking with Local Updates](https://mlsanity.com/paper/2210.04757/) (2022)
- [CO2: Efficient Distributed Training with Full Communication-Computation Overlap](https://mlsanity.com/paper/2401.16265/) (2024)
- [Eager Updates For Overlapped Communication and Computation in DiLoCo](https://mlsanity.com/paper/2502.12996/) (2025)
- [Overlap Local-SGD: An Algorithmic Approach to Hide Communication Delays in Distributed SGD](https://mlsanity.com/paper/2002.09539/) (2020)
- [Faster Distributed Deep Net Training: Computation and Communication Decoupled Stochastic Gradient Descent](https://mlsanity.com/paper/1906.12043/) (2019)
- [From promise to practice: realizing high-performance decentralized training](https://mlsanity.com/paper/2410.11998/) (2024)
- [How Clustering Affects the Convergence of Decentralized Optimization over Networks: A Monte-Carlo-based Approach](https://mlsanity.com/paper/2407.01460/) (2024)
- [Momentum-based Distributed Resource Scheduling Optimization Subject to Sector-Bound Nonlinearity and Latency](https://mlsanity.com/paper/2503.06167/) (2025)
- [Momentum-based Accelerated Algorithm for Distributed Optimization under Sector-Bound Nonlinearity](https://mlsanity.com/paper/2506.22855/) (2025)

## Abstract (arXiv)

Decentralized optimization has emerged as a critical paradigm for distributed learning, enabling scalable training while preserving data privacy through peer-to-peer collaboration. However, existing methods often suffer from communication bottlenecks due to frequent synchronization between nodes. We present Overlapping Local Decentralized SGD (OLDSGD), a novel approach to accelerate decentralized training by computation-communication overlapping, significantly reducing network idle time. With a deliberately designed update, OLDSGD preserves the same average update as Local SGD while avoiding communication-induced stalls. Theoretically, we establish non-asymptotic convergence rates for smooth non-convex objectives, showing that OLDSGD retains the same iteration complexity as standard Local Decentralized SGD while improving per-iteration runtime. Empirical results demonstrate OLDSGD's consistent improvements in wall-clock time convergence under different levels of communication delays. With minimal modifications to existing frameworks, OLDSGD offers a practical solution for faster decentralized learning without sacrificing theoretical guarantees.