针对随机拓扑下的分布式优化，提出高效通信的随机逼近算法。
A Stochastic Approximation Approach for Efficient Decentralized Optimization on Random Networks
- 基于随机增广拉格朗日法，将拓扑随机性融入优化框架。
- 在T轮迭代内实现O(1/√T)和O(1/T²/³)的收敛精度。
- 适合通信受限、拓扑动态变化的分布式系统应用。
去中心化优化中一个挑战性问题是：在不可靠且带宽受限的通信网络下，如何设计在随机时变拓扑上具有快速收敛性的算法。本文提出一种基于随机逼近的全随机对偶算法（FSPDA）框架。该框架基于新观察：时变拓扑的随机性可被纳入随机增广拉格朗日形式，其期望值在鞍点处与去中心化优化问题的驻点一致。基于FSPDA框架，我们开发了两种支持高效稀疏通信的新算法——FSPDA-SA允许代理根据时变拓扑执行多步本地梯度更新以加速收敛；FSPDA-STORM进一步引入方差缩减步骤以提升样本复杂度。对于光滑（可能非凸）目标函数，在T次迭代内，FSPDA-SA（对应地，FSPDA-STORM）可找到一个O(1/√T)（对应地，O(1/T²/³)）的驻点解。数值实验验证了FSPDA算法的优势。
原文摘要 · Abstract (English)
A challenging problem in decentralized optimization is to develop algorithms with fast convergence on random and time varying topologies under unreliable and bandwidth-constrained communication network. This paper studies a stochastic approximation approach with a Fully Stochastic Primal Dual Algorithm (FSPDA) framework. Our framework relies on a novel observation that randomness in time varying topology can be incorporated in a stochastic augmented Lagrangian formulation, whose expected value admits saddle points that coincide with stationary solutions of the decentralized optimization problem. With the FSPDA framework, we develop two new algorithms supporting efficient sparsified communication on random time varying topologies -- FSPDA-SA allows agents to execute multiple local gradient steps depending on the time varying topology to accelerate convergence, and FSPDA-STORM further incorporates a variance reduction step to improve sample complexity. For problems with smooth (possibly non-convex) objective function, within $T$ iterations, we show that FSPDA-SA (resp. FSPDA-STORM) finds an $\mathcal{O}( 1/\sqrt{T} )$-stationary (resp. $\mathcal{O}( 1/T^{2/3} )$) solution. Numerical experiments show the benefits of the FSPDA algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。