FROST -- Fast row-stochastic optimization with uncoordinated step-sizes

Abstract

In this paper, we discuss distributed optimization over directed graphs, where doubly-stochastic weights cannot be constructed. Most of the existing algorithms overcome this issue by applying push-sum consensus, which utilizes column-stochastic weights. The formulation of column-stochastic weights requires each agent to know (at least) its out-degree, which may be impractical in e.g., broadcast-based communication protocols. In contrast, we describe FROST (Fast Row-stochastic-Optimization with uncoordinated STep-sizes), an optimization algorithm applicable to directed graphs that does not require the knowledge of out-degrees; the implementation of which is straightforward as each agent locally assigns weights to the incoming information and locally chooses a suitable step-size. We show that FROST converges linearly to the optimal solution for smooth and strongly-convex functions given that the largest step-size is positive and sufficiently small.

arXiv commentSubmitted for journal publication, currently under review

References in corpus (8)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Harnessing Smoothness to Accelerate Distributed Optimization
• D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
• A linear algorithm for optimization over directed graphs with geometric convergence
• Sparse Distributed Learning Based on Diffusion Adaptation
• ADD-OPT: Accelerated Distributed Directed Optimization
• Cloud K-SVD: A Collaborative Dictionary Learning Algorithm for Big, Distributed Data
• AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs

Cited by in corpus (4)

• A Review of the Family of Artificial Fish Swarm Algorithms: Recent Advances and Applications
• Distributed Nesterov gradient methods over arbitrary graphs
• The Barzilai-Borwein Method for Distributed Optimization over Unbalanced Directed Networks
• Scalable Distributed Optimization of Multi-Dimensional Functions Despite Byzantine Adversaries