Push–Pull Gradient Methods for Distributed Optimization in Networks

By Shi Pu, Wei Shi, Jinming Xu, Angelia Nedić. IEEE Transactions on Automatic Control, 2018

415 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/97349817ca8fc96b04ee57cf03de0ab847f145ed

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent (2019, background): “1) has been studied extensively in the literature under various distributed algorithms [43, 25, 26, 19, 15, 16, 39, 11, 35, 23, 45, 34], among which the distributed gradient descent (DGD) method proposed in [25] has drawn the greatest attention.”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, background): “Problem (1) has been studied extensively in the literature undervariousdistributedalgorithms[12]–[23],amongwhichthe distributedgradientdescent(DGD)methodproposedin[13]has drawnthegreatestattention.”
Distributed stochastic gradient tracking methods (2018, background): “Distributed algorithms dealing with problem (1) have been studied extensively in the literature [56,36, 37,28,19,20,52,13,46,34,45].”
Distributed Gradient Methods for Convex Machine Learning Problems in Networks: Distributed Optimization (2020, methodology): “Also, with suitably selected step sizes, both algorithms converge linearly to the solution of the problem ( ) min m f x 1 i n m / when all of the functions f i are strongly convex and have Lip-schitz continuous gradients (see [32] and [33] for details).”