TY - GEN

T1 - On the convergence rate of distributed gradient methods for finite-sum optimization under communication delays

AU - Doan, Thinh T.

AU - Beck, Carolyn L.

AU - Srikant, R.

N1 - Funding Information:
The authors would like to thank the anonymous reviewers for their valuable comments and helpful suggestions. The work is supported by Boeing, ARO Grant W911NF-16-1-0259, and the National Science Foundation under Grant NSF CNS 15-44953 and NeTS 1718203.

PY - 2018/6/12

Y1 - 2018/6/12

N2 - 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 multiple 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.

AB - 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 multiple 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.

UR - http://www.scopus.com/inward/record.url?scp=85050409679&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050409679&partnerID=8YFLogxK

U2 - 10.1145/3219617.3219654

DO - 10.1145/3219617.3219654

M3 - Conference contribution

AN - SCOPUS:85050409679

T3 - SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems

SP - 93

EP - 95

BT - SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems

PB - Association for Computing Machinery, Inc

T2 - 2018 ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2018

Y2 - 18 June 2018 through 22 June 2018

ER -