On the Linear Convergence of Distributed Optimization over Directed Graphs

Abstract

This paper develops a fast distributed algorithm, termed \emph{DEXTRA}, to solve the optimization problem when~$n$ agents reach agreement and collaboratively minimize the sum of their local objective functions over the network, where the communication between the agents is described by a~\emph{directed} graph. Existing algorithms solve the problem restricted to directed graphs with convergence rates of $O(\ln k/\sqrt{k})$ for general convex objective functions and $O(\ln k/k)$ when the objective functions are strongly-convex, where~$k$ is the number of iterations. We show that, with the appropriate step-size, DEXTRA converges at a linear rate $O({\tau }^k)$ for $0<\tau <1$, given that the objective functions are restricted strongly-convex. The implementation of DEXTRA requires each agent to know its local out-degree. Simulation examples further illustrate our findings.

References in corpus (6)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Convex Optimization for Big Data
• ExtraPush for convex smooth decentralized optimization over directed networks
• On the Convergence of Decentralized Gradient Descent
• On the Distributed Optimization over Directed Networks
• Distributed Subgradient Projection Algorithm over Directed Graphs

Cited by in corpus (10)

• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• ExtraPush for convex smooth decentralized optimization over directed networks
• A Push-Pull Gradient Method for Distributed Optimization in Networks
• Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
• Private Learning on Networks: Part II
• Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis
• Distributed Subgradient Projection Algorithm over Directed Graphs
• Linear convergence in optimization over directed graphs with row-stochastic matrices
• On linear convergence of two decentralized algorithms
• A Fast Proximal Gradient Algorithm for Decentralized Composite Optimization over Directed Networks