去中心化学习研究者终于有了理论最优的随机算法——MG-ADSGD同时加速了条件数和网络拓扑的影响，做分布式优化或联邦学习的团队值得关注这个新基准。
本文提出MG-ADSGD算法，针对强凸优化问题，首次在去中心化随机优化中同时实现加速的κ平方根和网络谱间隙的平方根倒数依赖。该算法结合Nesterov型原始-对偶外推与多轮快速八卦平均，通过将八卦深度与小批量大小耦合，额外通信轮次同时提升共识精度和降低梯度方差。理论分析表明，MG-ADSGD的通信复杂度达到当前最优，包含σ²/(μnε)项和√(κ/(1-β))项，优于现有所有去中心化随机方法。这一突破解决了去中心化随机优化中长期存在的加速难题。
Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization
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 \(\sqrtκ\) and \(1/\sqrt{1-β}\) dependences, no existing stochastic method attains both improvements at once. In this paper, we propose \emph{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. We show that MG-ADSGD achieves the communication complexity \[ \widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right), \] where \(ε\) denotes the target accuracy, \(n\) is the number of nodes, and \(σ^2\) is the gradient variance. To the best of our knowledge, this bound yields the best currently available communication complexity for decentralized stochastic strongly convex optimization, up to logarithmic factors that are independent of $ε$.