Analysis and Design of First-Order Distributed Optimization Algorithms Over Time-Varying Graphs
Analysis and Design of First-Order Distributed Optimization Algorithms Over Time-Varying Graphs
复制标题
DOI：
10.1109/tcns.2020.2988009
复制
发表时间：
2019-07
影响因子：
4.2
通讯作者：
Akhil Sundararajan;Bryan Van Scoy;Laurent Lessard
中科院分区：
文献类型：
--
作者：
Akhil Sundararajan;Bryan Van Scoy;Laurent Lessard
本文主要研究时变图上分布式一阶优化算法的分析与设计。这种算法的目标是优化全局函数，该全局函数是仅使用局部计算和通信的局部函数的平均值。已经提出了几种不同的算法，实现线性收敛到全局最优的局部函数是强凸的。我们提供了一个统一的分析，产生的最坏情况下的线性收敛速度的函数的条件数的本地功能，图的频谱间隙，和算法的参数。该框架需要解决一个小的半定程序，其大小是固定的，它不依赖于本地功能的数量或其域的尺寸。其结果是一种计算效率高的分布式算法分析方法，可以快速比较，选择和调整算法。最后，我们提出了一个新的算法，我们称之为SVL，这是很容易实现的，并实现了更快的最坏情况下的收敛速度比所有其他已知的算法。
This work concerns the analysis and design of distributed first-order optimization algorithms over time-varying graphs. The goal of such algorithms is to optimize a global function that is the average of local functions using only local computations and communications. Several different algorithms have been proposed that achieve linear convergence to the global optimum when the local functions are strongly convex. We provide a unified analysis that yields the worst-case linear convergence rate as a function of the condition number of the local functions, the spectral gap of the graph, and the parameters of the algorithm. The framework requires solving a small semidefinite program whose size is fixed; it does not depend on the number of local functions or the dimension of their domain. The result is a computationally efficient method for distributed algorithm analysis that enables the rapid comparison, selection, and tuning of algorithms. Finally, we propose a new algorithm, which we call SVL, that is easily implementable and achieves a faster worst-case convergence rate than all other known algorithms.