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

Thinh T. Doan, Carolyn L. Beck, R. Srikant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationSIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems
PublisherAssociation for Computing Machinery, Inc
Pages93-95
Number of pages3
ISBN (Electronic)9781450358460
DOIs
StatePublished - Jun 12 2018
Event2018 ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2018 - Irvine, United States
Duration: Jun 18 2018Jun 22 2018

Publication series

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

Other

Other2018 ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2018
CountryUnited States
CityIrvine
Period6/18/186/22/18

    Fingerprint

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Computational Theory and Mathematics
  • Software

Cite this

Doan, T. T., Beck, C. L., & Srikant, R. (2018). On the convergence rate of distributed gradient methods for finite-sum optimization under communication delays. In SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems (pp. 93-95). (SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems). Association for Computing Machinery, Inc. https://doi.org/10.1145/3219617.3219654