# Near-Optimal Decentralized Stochastic Convex Optimization over Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 31 references that are in the map.
- First posted on arXiv 3 Jun 2026.

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

- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [Byzantine-Robust Decentralized Learning via ClippedGossip](https://mlsanity.com/paper/2202.01545/) (2022)
- [Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model](https://mlsanity.com/paper/2305.12387/) (2023)
- [ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks](https://mlsanity.com/paper/2102.09234/) (2021)
- [Towards accelerated rates for distributed optimization over time-varying networks](https://mlsanity.com/paper/2009.11069/) (2020)
- [Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networks](https://mlsanity.com/paper/1910.10666/) (2019)
- [Optimal Distributed Optimization on Slowly Time-Varying Graphs](https://mlsanity.com/paper/1805.06045/) (2018)
- [Enhancing Parallelism in Decentralized Stochastic Convex Optimization](https://mlsanity.com/paper/2506.00961/) (2025)

## Abstract (arXiv)

We study decentralized stochastic smooth convex optimization, where M workers minimize an average objective using local stochastic gradients and neighbor-only communication over a fixed gossip network. A central question in this setting is to determine the largest number of workers that can be used under a total budget of N gradient samples while still preserving the centralized O(1/√ N) statistical rate. We introduce an accelerated decentralized method that preserves this rate for up to smashMlesssim √ρ,N3/4 workers, where ρ is the spectral gap of the gossip network, improving the best prior maximal scaling of smashMlesssim ρ√ N. The method is based on a one-step-delayed stochastic acceleration scheme that enables workers to interleave minibatching with accelerated gossip while controlling residual disagreement, and its guarantee depends only logarithmically on the optimum-local heterogeneity. We also establish a matching lower bound for linear-span decentralized first-order methods, showing that the method is optimal up to logarithmic factors.