A linear algorithm for optimization over directed graphs with geometric convergence

Abstract

In this letter, we study distributed optimization, where a network of agents, abstracted as a directed graph, collaborates to minimize the average of locally-known convex functions. Most of the existing approaches over directed graphs are based on push-sum (type) techniques, which use an independent algorithm to asymptotically learn either the left or right eigenvector of the underlying weight matrices. This strategy causes additional computation, communication, and nonlinearity in the algorithm. In contrast, we propose a linear algorithm based on an inexact gradient method and a gradient estimation technique. Under the assumptions that each local function is strongly-convex with Lipschitz-continuous gradients, we show that the proposed algorithm geometrically converges to the global minimizer with a sufficiently small step-size. We present simulations to illustrate the theoretical findings.

References in corpus (3)

• Distributed Basis Pursuit
• ADD-OPT: Accelerated Distributed Directed Optimization
• Cloud K-SVD: A Collaborative Dictionary Learning Algorithm for Big, Distributed Data

Cited by in corpus (18)

• Accelerated Distributed Nesterov Gradient Descent
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• FROST -- Fast row-stochastic optimization with uncoordinated step-sizes
• Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
• AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs
• Distributed Nesterov gradient methods over arbitrary graphs
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Supervised Learning Under Distributed Features
• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• Distributed Online Optimization in Time-Varying Unbalanced Networks without Explicit Subgradients
• Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• A System Theoretical Perspective to Gradient-Tracking Algorithms for Distributed Quadratic Optimization
• Scaling-up Distributed Processing of Data Streams for Machine Learning
• Privacy-Preserving Push-Pull Method for Decentralized Optimization via State Decomposition
• The Barzilai-Borwein Method for Distributed Optimization over Unbalanced Directed Networks
• Automatic Performance Estimation for Decentralized Optimization