A Proximal Gradient Algorithm for Decentralized Composite Optimization

Wei Shi, Qing Ling, Gang Wu, and Wotao Yin

Published in IEEE Tran. Signal Processing


This paper proposes a decentralized algorithm for solving a consensus optimization problem defined in a static networked multi-agent system, where the local objective functions have the smooth+nonsmooth composite form. Examples of such problems include decentralized constrained quadratic programming and compressed sensing problems, as well as many regularization problems arising in inverse problems, signal processing, and machine learning, which have decentralized applications. This paper addresses the need for efficient decentralized algorithms that take advantages of proximal operations for the nonsmooth terms.

We propose a proximal gradient exact first-order algorithm (PG-EXTRA) that utilizes the composite structure and has the best known convergence rate. It is a nontrivial extension to the recent algorithm EXTRA. At each iteration, each agent locally computes a gradient of the smooth part of its objective and a proximal map of the nonsmooth part, as well as exchange information with its neighbors. The algorithm is “exact” in the sense that an exact consensus minimizer can be obtained with a fixed step size, whereas most previous methods must use diminishing step sizes. When the smooth part has Lipschitz gradients, PG-EXTRA has an ergodic convergence rate of Oleft(frac{1}{k}right) in terms of the first-order optimality residual. When the smooth part vanishes, PG-EXTRA reduces to P-EXTRA, an algorithm that does not compute the gradients (so no ‘‘G’’ in the name), which has a slightly improved convergence rate at oleft(frac{1}{k}right) in a standard (non-ergodic) sense. Numerical experiments demonstrate effectiveness of PG-EXTRA and validate our convergence results.


W. Shi, Q. Ling, G. Wu, and W. Yin, A Proximal Gradient Algorithm for Decentralized Composite Optimization, IEEE Transactions on Signal Processing, 63(22), 6013-6023, 2015. DOI: 10.1109/TSP.2015.2461520

Preceding paper

W. Shi, Q. Ling, G. Wu, and W. Yin, EXTRA: an Exact First-Order Algorithm for Decentralized Consensus Optimization, SIAM J. Optimization 25(2), 2014.

« Back