On the Linear Convergence of Two Decentralized Algorithms
On the Linear Convergence of Two Decentralized Algorithms
复制标题
两种去中心化算法的线性收敛性
DOI：
10.1007/s10957-021-01833-y
复制
发表时间：
2021
影响因子：
1.9
通讯作者：
Yan, Ming
中科院分区：
文献类型：
--
作者：
Li, Yao;Yan, Ming
分散算法解决了连接网络上的多代理问题，其中信息只能与可访问的邻居交换。虽然目前存在多种分散优化算法，但分散算法与集中式算法在收敛条件和收敛速度上仍然存在差距。在本文中，我们通过考虑两种分散算法：EXTRA和NIDS来填补一些空白。它们都与强凸目标函数线性收敛。我们将回答两个问题。它们的步长最优上界是什么？去中心化算法对线性收敛函数的要求比中心化算法高吗？更具体地说，我们放宽了两种算法线性收敛的必要条件。对于EXTRA，我们证明了步长与集中式算法相当。对于NIDS，其步长上界与集中式步长上界完全相同。此外，我们还放宽了对目标函数和混合矩阵的要求。给出了两种算法在最弱条件下的线性收敛结果。
Decentralized algorithms solve multi-agent problems over a connected network, where the information can only be exchanged with the accessible neighbors. Though there exist several decentralized optimization algorithms, there are still gaps in convergence conditions and rates between decentralized and centralized algorithms. In this paper, we fill some gaps by considering two decentralized algorithms: EXTRA and NIDS. They both converge linearly with strongly convex objective functions. We will answer two questions regarding them. What are the optimal upper bounds for their stepsizes? Do decentralized algorithms require more properties on the functions for linear convergence than centralized ones? More specifically, we relax the required conditions for linear convergence of both algorithms. For EXTRA, we show that the stepsize is comparable to that of centralized algorithms. For NIDS, the upper bound of the stepsize is shown to be exactly the same as the centralized ones. In addition, we relax the requirement for the objective functions and the mixing matrices. We provide the linear convergence results for both algorithms under the weakest conditions.