Distributed Nesterov gradient methods over arbitrary graphs

Abstract--In this letter, we introduce a distributed Nesterov method, termed as ABN, 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 (stronglyconnected) 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. I. INTRODUCTION Distributed optimization has recently seen a surge of interest particularly with the emergence of modern signal processing and machine learning applications. A well-studied problem in this domain is finite sum minimization that also has some relevance to empirical risk formulations, i.e., min R is a smooth and convex function available at an agent i. 's depend on data that may be private to each agent and communicating large data is impractical, developing distributed solutions of the above problem have attracted a strong interest.