Push–Pull Gradient Methods for Distributed Optimization in Networks

TLDR

The paper addresses distributed convex optimization over a network, aiming to minimize the sum of agents’ convex cost functions while respecting the network’s connectivity constraints. It introduces push‑pull gradient algorithms in which each node keeps estimates of the optimal variable and the average gradient, pushing gradient information and pulling variable estimates across two distinct communication graphs to accommodate decentralized, centralized, and leader‑follower architectures. The methods achieve linear convergence for strongly convex smooth problems on directed graphs, including synchronous and random‑gossip settings, and outperform existing linearly convergent schemes on ill‑conditioned and unbalanced networks.

Abstract

In this article, we focus on solving a distributed convex optimization problem in a network, where each agent has its own convex cost function and the goal is to minimize the sum of the agents' cost functions while obeying the network connectivity structure. In order to minimize the sum of the cost functions, we consider new distributed gradient-based methods where each node maintains two estimates, namely an estimate of the optimal decision variable and an estimate of the gradient for the average of the agents' objective functions. From the viewpoint of an agent, the information about the gradients is pushed to the neighbors, whereas the information about the decision variable is pulled from the neighbors, hence giving the name "push-pull gradient methods." The methods utilize two different graphs for the information exchange among agents and, as such, unify the algorithms with different types of distributed architecture, including decentralized (peer to peer), centralized (master-slave), and semicentralized (leader-follower) architectures. We show that the proposed algorithms and their many variants converge linearly for strongly convex and smooth objective functions over a network (possibly with unidirectional data links) in both synchronous and asynchronous random-gossip settings. In particular, under the random-gossip setting, "push-pull" is the first class of algorithms for distributed optimization over directed graphs. Moreover, we numerically evaluate our proposed algorithms in both scenarios, and show that they outperform other existing linearly convergent schemes, especially for ill-conditioned problems and networks that are not well balanced.