Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networks
Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networks
复制标题
DOI：
--
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Jinming Xu;Ye Tian;Ying Sun;G. Scutari
中科院分区：
文献类型：
--
作者：
Jinming Xu;Ye Tian;Ying Sun;G. Scutari
本文提出了一种新的家庭的原始对偶为基础的分布式算法，光滑，凸，多智能体优化网络，只使用梯度信息和八卦通信。该算法还可以在计算和通信上采用加速。我们提供了一个统一的分析，他们的收敛速度，测量的Bregman距离相关的鞍点改造的分布式优化问题。当采用加速时，速率被证明是最佳的，在这个意义上，它匹配（根据建议的度量）现有的复杂性下限的分布式算法适用于这样一类问题，只使用梯度信息和八卦通信。分布式最小二乘回归问题的初步数值结果表明，该算法相比现有的分布式计划毫不逊色。
This paper proposes a novel family of primal-dual-based distributed algorithms for smooth, convex, multi-agent optimization over networks that uses only gradient information and gossip communications. The algorithms can also employ acceleration on the computation and communications. We provide a unified analysis of their convergence rate, measured in terms of the Bregman distance associated to the saddle point reformation of the distributed optimization problem. When acceleration is employed, the rate is shown to be optimal, in the sense that it matches (under the proposed metric) existing complexity lower bounds of distributed algorithms applicable to such a class of problem and using only gradient information and gossip communications. Preliminary numerical results on distributed least-square regression problems show that the proposed algorithm compares favorably on existing distributed schemes.