Distributed Nesterov gradient methods over arbitrary graphs

Abstract

In this letter, we introduce a distributed Nesterov method, termed as $\mathcal{A}\mathcal{B}\mathcal{N}$, that does not require doubly-stochastic weight matrices. Instead, the implementation is based on a simultaneous application of both row- and column-stochastic weights that makes this method applicable to arbitrary (strongly-connected) graphs. Since constructing column-stochastic weights needs additional information (the number of outgoing neighbors at each agent), not available in certain communication protocols, we derive a variation, termed as FROZEN, that only requires row-stochastic weights but at the expense of additional iterations for eigenvector learning. We numerically study these algorithms for various objective functions and network parameters and show that the proposed distributed Nesterov methods achieve acceleration compared to the current state-of-the-art methods for distributed optimization.

References in corpus (6)

• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• Harnessing Smoothness to Accelerate Distributed Optimization
• A linear algorithm for optimization over directed graphs with geometric convergence
• Distributed Random Projection Algorithm for Convex Optimization
• ADD-OPT: Accelerated Distributed Directed Optimization
• FROST -- Fast row-stochastic optimization with uncoordinated step-sizes

Cited by in corpus (1)

• Automated algorithm design for convex optimization problems with linear equality constraints