On the Convergence Rate of Distributed Gradient Methods for Finite-Sum Optimization under Communication Delays
On the Convergence Rate of Distributed Gradient Methods for Finite-Sum Optimization under Communication Delays
复制标题
DOI：
10.1145/3154496
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Thinh T. Doan;Carolyn L. Beck;R. Srikant
中科院分区：
文献类型：
--
作者：
Thinh T. Doan;Carolyn L. Beck;R. Srikant
受机器学习和统计学应用的启发，我们研究了处理器网络上的分布式优化问题，其目标是优化由局部函数和组成的全局目标。在这些问题中，由于数据集的规模很大，数据和计算必须分布在处理器上，从而需要分布式算法。在本文中，我们考虑一个流行的分布式基于梯度的共识算法，它只需要本地计算和通信。在这方面的一个重要问题是分析这种算法的收敛速度在分布式系统中不可避免的通信延迟的存在。我们证明了收敛的基于梯度的共识算法中存在的统一，但可能任意大，处理器之间的通信延迟。此外，我们得到的收敛速度的算法作为网络的大小，拓扑结构和处理器间的通信延迟的函数的上界。
Motivated by applications in machine learning and statistics, we study distributed optimization problems over a network of processors, where the goal is to optimize a global objective composed of a sum of local functions. In these problems, due to the large scale of the data sets, the data and computation must be distributed over processors resulting in the need for distributed algorithms. In this paper, we consider a popular distributed gradient-based consensus algorithm, which only requires local computation and communication. An important problem in this area is to analyze the convergence rate of such algorithms in the presence of communication delays that are inevitable in distributed systems. We prove the convergence of the gradient-based consensus algorithm in the presence of uniform, but possibly arbitrarily large, communication delays between the processors. Moreover, we obtain an upper bound on the rate of convergence of the algorithm as a function of the network size, topology, and the inter-processor communication delays.