提出新型分布式优化算法,显著提升强凸问题的通信效率。
Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization
- 结合Nesterov加速与多轮快速消息传递,动态匹配通信深度与批量大小。
- 通信复杂度达最优阶,同时实现√κ和1/√(1−β)的依赖性优化。
- 适合大规模分布式学习场景,尤其适用于通信受限的网络系统。
去中心化随机优化是网络上大规模学习的基本范式,各节点仅与邻居通信且无需中央协调。对于强凸问题,通信效率主要由条件数κ = L/μ 和网络谱间隙1−β决定。尽管确定性方法可同时实现√κ和1/√(1−β)的加速,但现有随机方法无法兼顾两者。本文提出多轮快速消息传递加速随机梯度下降(MG-ADSGD),将Nesterov型原始-对偶外推与多轮快速消息传递平均相结合。核心思想是将消息传递深度与小批量大小耦合,使额外通信轮次同时提升共识精度并降低梯度方差。我们证明MG-ADSGD的通信复杂度为˜O(σ²/(μnε) log(1/ε) + √(κ/(1−β)) log(1/ε)),其中ε为目标精度,n为节点数,σ²为梯度方差。据我们所知,该界在去中心化随机强凸优化中达到当前最优通信复杂度,仅差对数因子且与ε无关。
原文摘要 · Abstract (English)
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 $ε$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。