ASY-SONATA: Achieving Linear Convergence in Distributed Asynchronous Multiagent Optimization
ASY-SONATA: Achieving Linear Convergence in Distributed Asynchronous Multiagent Optimization
复制标题
DOI：
10.1109/allerton.2018.8636055
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Ye Tian;Ying Sun;G. Scutari
中科院分区：
文献类型：
--
作者：
Ye Tian;Ying Sun;G. Scutari
本文研究了静态有向图上的多智能体（凸和非凸）优化问题。我们提出了一个通用的分布式异步算法框架，其中i）代理可以更新他们的本地变量，以及与他们的邻居在任何时候进行通信，没有任何形式的协调;和ii）他们可以执行本地计算使用（可能）延迟，从他们的邻居不同步的信息。延迟不需要为代理所知或遵守任何特定的配置文件，并且也可以是时变的（但有界的）。该算法建立在对异步（从上述意义上讲）具有鲁棒性的跟踪机制之上，其目标是局部估计代理梯度的总和。当应用到强凸函数，我们证明了它收敛于R-线性（几何）率，只要步长是足够小的。证明了当非凸问题和/或递减、不协调步长时，算法的次线性收敛速度。据我们所知，这是第一个分布式算法，证明几何收敛速度在这样一个一般的随机设置。
This papers studies multi-agent (convex and nonconvex) optimization over static digraphs. We propose a general distributed asynchronous algorithmic framework whereby i) agents can update their local variables as well as communicate with their neighbors at any time, without any form of coordination; and ii) they can perform their local computations using (possibly) delayed, out-of-sync information from their neighbors. Delays need not be known to the agents or obey any specific profile, and can also be time-varying (but bounded). The algorithm builds on a tracking mechanism that is robust against asynchrony (in the above sense), whose goal is to estimate locally the sum of agents’ gradients. When applied to strongly convex functions, we prove that it converges at an R-linear (geometric) rate as long as the step-size is sufficiently small. A sublinear convergence rate is proved, when nonconvex problems and/or diminishing, uncoordinated step-sizes are employed. To the best of our knowledge, this is the first distributed algorithm with provable geometric convergence rate in such a general asynchonous setting.