Near-Optimal Decentralized Stochastic Convex Optimization over Networks
Abstract
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 smashM≲ √ρ N3/4 workers, where ρ is the spectral gap of the gossip network, improving the best prior maximal scaling of smashM≲ ρ√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.
Related
- Resilient Decentralized Preconditioned Stochastic Proximal Optimization with Gradient Sketching over Time-Varying Networks
- Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization
- Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization
- Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
- Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks
BibTeX
@misc{kluger2026nearoptimal,
title = {{Near-Optimal Decentralized Stochastic Convex Optimization over Networks}},
author = {Nitai Kluger and Amit Attia and Tomer Koren},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2606.04757},
eprint = {2606.04757},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.04757},
}
RIS
TY - UNPB
TI - Near-Optimal Decentralized Stochastic Convex Optimization over Networks
AU - Nitai Kluger
AU - Amit Attia
AU - Tomer Koren
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2606.04757
UR - https://arxiv.org/abs/2606.04757
AB - 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 smashM≲ √ρ N^3/4 workers, where ρ is the spectral gap of the gossip network, improving the best prior maximal scaling of smashM≲ ρ√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.
ER -