Paper Overview
Research area: Machine Learning Authors: Ming Sun, Kun Yuan Published: 2025-06-11 arXiv: 2506.08635
Abstract
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.
In this paper, the authors propose Multi-Gossip Accelerated DSGD (MG-ADSGD), a decentralized stochastic algorithm that combines 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
MG-ADSGD achieves a communication complexity of
Õ(σ²/(μnε)·log(1/ε) + √(κ/(1-β))·log(1/ε))
where ε is the target accuracy, n is the number of nodes, and σ² is the gradient variance. To the authors' knowledge, this is the best communication complexity currently attainable for decentralized stochastic strongly convex optimization (ignoring ε-independent log factors).
*Source: arXiv preprint 2506.08635*