提出新框架统一分析去中心化梯度下降,收敛性更清晰易懂。
Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework
- 用压缩映射与均值海森定理分析算法动态与最终精度分离
- 在无噪和有噪场景下均获得紧致收敛界
- 适合想理解去中心化优化原理的研究者
去中心化梯度下降(DGD)及其变体扩散算法是去中心化机器学习、分布式推断与多智能体协同中的核心方法。本文提出一种新颖的理论框架,用于分析具有强凸光滑目标函数、任意无向拓扑下的DGD与扩散算法,结合压缩映射与均值海森定理(MHT)。该方法在无噪声和有噪声条件下均获得紧致收敛界。尽管定性结果与已有文献相似,但本方法通过压缩映射与MHT将算法动态(收敛到不动点的速度)与渐近性质(不动点距离全局最优的距离)解耦,实现直观且易于理解的分析。扩展涵盖多轮本地梯度更新、时变步长、噪声梯度(随机DGD与扩散)、通信噪声及随机拓扑。
原文摘要 · Abstract (English)
The decentralized gradient descent (DGD) algorithm, and its sibling, diffusion, are workhorses in decentralized machine learning, distributed inference and estimation, and multi-agent coordination. We propose a novel, principled framework for the analysis of DGD and diffusion for strongly convex, smooth objectives, and arbitrary undirected topologies, using contraction mappings coupled with a result called the mean Hessian theorem (MHT). The use of these tools yields tight convergence bounds, both in the noise-free and noisy regimes. While these bounds are qualitatively similar to results found in the literature, our approach using contractions together with the MHT decouples the algorithm dynamics (how quickly the algorithm converges to its fixed point) from its asymptotic convergence properties (how far the fixed point is from the global optimum). This yields a simple, intuitive analysis that is accessible to a broader audience. Extensions are provided to multiple local gradient updates, time-varying step sizes, noisy gradients (stochastic DGD and diffusion), communication noise, and random topologies.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。