为去中心化优化设计统一加速框架,提升收敛速度与适用范围。
DCatalyst: A Unified Accelerated Framework for Decentralized Optimization
- 采用不精确估计序列的动量加速机制,融合任意去中心化算法
- 在多种场景下实现通信与计算复杂度最优(对数因子内)
- 首次将加速能力扩展至此前无高效解法的问题类别,适合分布式学习研究者
我们研究无中心服务器的网络化代理间的去中心化优化问题,目标是最小化 $f+r$,其中 $f$ 表示各代理局部损失的平均(强)凸函数,$r$ 是凸的扩展值函数。本文提出 DCatalyst,一个统一的黑箱加速框架,将 Nesterov 加速融入去中心化优化算法。其核心为一种不精确、动量加速的近端方法(外层循环),可无缝集成任意选定的去中心化算法(内层循环)。我们证明,DCatalyst 在多种去中心化算法和问题实例中均达到最优通信与计算复杂度(对数因子内)。尤其重要的是,它将加速能力拓展至此前缺乏高效解法的问题类别,显著提升了去中心化方法的有效性。技术上,该框架引入了 { extit{不精确估计序列}}——一种针对去中心化复合损失最小化的新型 Nesterov 估计序列扩展,能有效处理共识误差与代理子问题的不精确解,这是现有模型未覆盖的挑战。
原文摘要 · Abstract (English)
We study decentralized optimization over a network of agents, modeled as graphs, with no central server. The goal is to minimize $f+r$, where $f$ represents a (strongly) convex function averaging the local agents' losses, and $r$ is a convex, extended-value function. We introduce DCatalyst, a unified black-box framework that integrates Nesterov acceleration into decentralized optimization algorithms. %, enhancing their performance. At its core, DCatalyst operates as an \textit{inexact}, \textit{momentum-accelerated} proximal method (forming the outer loop) that seamlessly incorporates any selected decentralized algorithm (as the inner loop). We demonstrate that DCatalyst achieves optimal communication and computational complexity (up to log-factors) across various decentralized algorithms and problem instances. Notably, it extends acceleration capabilities to problem classes previously lacking accelerated solution methods, thereby broadening the effectiveness of decentralized methods. On the technical side, our framework introduce the {\it inexact estimating sequences}--a novel extension of the well-known Nesterov's estimating sequences, tailored for the minimization of composite losses in decentralized settings. This method adeptly handles consensus errors and inexact solutions of agents' subproblems, challenges not addressed by existing models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。