A Push-Pull Gradient Method for Distributed Optimization in Networks

Abstract

In this paper, 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 a new distributed gradient-based method 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 decision variable is pushed to the neighbors, while the information about the gradients is pulled from the neighbors (hence giving the name "push-pull gradient method"). The method unifies the algorithms with different types of distributed architecture, including decentralized (peer-to-peer), centralized (master-slave), and semi-centralized (leader-follower) architecture. We show that the algorithm converges linearly for strongly convex and smooth objective functions over a directed static network. In our numerical test, the algorithm performs well even for time-varying directed networks.

arXiv commentAccepted in CDC 2018

References in corpus (9)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• ExtraPush for convex smooth decentralized optimization over directed networks
• On the Linear Convergence of Distributed Optimization over Directed Graphs
• Optimal Algorithms for Distributed Optimization
• Distributed Stochastic Gradient Tracking Methods
• Decentralized Consensus Optimization with Asynchrony and Delays

Cited by in corpus (11)

• Supervised Learning Under Distributed Features
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Distributed Stochastic Gradient Tracking Methods
• Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking
• Distributed Online Convex Optimization with Improved Dynamic Regret
• A Distributed Stochastic Gradient Tracking Method
• Exponential Convergence for Distributed Smooth Optimization Under the Restricted Secant Inequality Condition
• Projected Push-Sum Gradient Descent-Ascent for Convex Optimizationwith Application to Economic Dispatch Problems
• Dynamic Average Diffusion with randomized Coordinate Updates
• Distributed Optimization Over Markovian Switching Random Network
• Nested Distributed Gradient Methods with Stochastic Computation Errors