Linear convergence in optimization over directed graphs with row-stochastic matrices
arXiv:1611.06160
Abstract
This paper considers a distributed optimization problem over a multi-agent network, in which the objective function is a sum of individual cost functions at the agents. We focus on the case when communication between the agents is described by a \emph{directed} graph. Existing distributed optimization algorithms for directed graphs require at least the knowledge of the neighbors' out-degree at each agent (due to the requirement of column-stochastic matrices). In contrast, our algorithm requires no such knowledge. Moreover, the proposed algorithm achieves the best known rate of convergence for this class of problems, for , where is the number of iterations, given that the objective functions are strongly-convex and have Lipschitz-continuous gradients. Numerical experiments are also provided to illustrate the theoretical findings.
arXiv commentarXiv admin note: text overlap with arXiv:1607.04757
References in corpus (9)
- Constrained Consensus
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- By-passing the Kohn-Sham equations with machine learning
- Convex Optimization for Big Data
- DILAND: An Algorithm for Distributed Sensor Localization with Noisy Distance Measurements
- Pure density functional for strong correlations and the thermodynamic limit from machine learning
- On the Linear Convergence of Distributed Optimization over Directed Graphs
- On the Distributed Optimization over Directed Networks
- Distributed Subgradient Projection Algorithm over Directed Graphs