On the Convergence Rate of Distributed Gradient Methods for Finite-Sum Optimization under Communication Delays
Authors:
Open Access
- 19 December 2017
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 1 (2) , 1-27
Abstract
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.Keywords
All Related Versions
Funding Information
- Boeing
- ARO (ARO Grant W911NF-16-1-0259)
- NSF (NSF Grant NeTS 1718203)
- National Science Foundation (NSF CNS 15-44953)
This publication has 16 references indexed in Scilit:
- Distributed Finite-Time Average Consensus in Digraphs in the Presence of Time DelaysIEEE Transactions on Control of Network Systems, 2015
- EXTRA: An Exact First-Order Algorithm for Decentralized Consensus OptimizationSIAM Journal on Optimization, 2015
- Distributed Optimization Over Time-Varying Directed GraphsIEEE Transactions on Automatic Control, 2014
- Scaling Distributed Machine Learning with the Parameter Server2014
- Understanding Machine Learning2014
- On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers2013
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network ScalingIEEE Transactions on Automatic Control, 2011
- Constrained Consensus and Optimization in Multi-Agent NetworksIEEE Transactions on Automatic Control, 2010
- Convergence rate for consensus with delaysJournal of Global Optimization, 2008