Optimization over directed graphs: Linear convergence rate

Chenguang Xi, Usman A. KhanICASSP 2017 · OpenReview

Abstract

This paper considers distributed multi-agents optimization problems where agents collaborate to minimize the sum of locally known convex functions. We focus on the case when the communication between agents is described by a directed graph. The proposed algorithm achieves the best known rate of convergence for this class of problems, O(μk) for 0 <; μ <; 1, given that the objective functions are strongly-convex, where k is the number of iterations. Moreover, it provides a wider and more realistic range of step-size compared with existing methods.
BibTeX
@inproceedings{xi2017optimization,
  author = {Chenguang Xi and Usman A. Khan},
  title = {{Optimization over directed graphs: Linear convergence rate}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2017},
  url = {https://openreview.net/forum?id=iGGwGzu0E2},
}

Loading related content...

Figure