Distributed Nesterov gradient methods over arbitrary graphs
This work addresses distributed optimization challenges in networked systems, offering improved convergence for applications like sensor networks or multi-agent learning, though it is incremental with variations for different communication constraints.
The authors tackled the problem of distributed optimization over arbitrary graphs by introducing a distributed Nesterov method that does not require doubly-stochastic weight matrices, achieving acceleration compared to state-of-the-art methods.
In this letter, we introduce a distributed Nesterov method, termed as $\mathcal{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 (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.