Overview
Field: Machine Learning Authors: Ming Sun, Kun Yuan Published: 2025-06-11 arXiv: 2506.08635
Summary
Decentralized stochastic optimization is a fundamental paradigm for large-scale learning over networks, where agents communicate only with their neighbors and no central coordinator is required. For strongly convex problems, communication efficiency is mainly determined by the condition number κ = L/μ and the network spectral gap 1-β. Although deterministic decentralized methods can simultaneously achieve accelerated √κ and 1/√{1-β} dependences, no existing stochastic method attains both improvements at once.
This paper proposes Multi-Gossip Accelerated DSGD (MG-ADSGD), a decentralized stochastic algorithm combining Nesterov-type primal-dual extrapolation with multi-round fast gossip averaging. The key idea is to couple the gossip depth with the mini-batch size, so that additional communication rounds simultaneously improve consensus accuracy and reduce gradient variance.
Main Result
The communication complexity of MG-ADSGD is:
Õ(σ²/(μnε) log(1/ε) + √(κ/(1-β)) log(1/ε))
where ε is the target accuracy, n the number of nodes, and σ² the gradient variance. To the authors' knowledge, this is the best communication complexity currently achievable for decentralized stochastic strongly convex optimization (ignoring ε-independent logarithmic factors).
Links
- Paper: https://arxiv.org/abs/2506.08635