A Proximal Gradient Algorithm for Decentralized Composite OptimizationWei Shi, Qing Ling, Gang Wu, and Wotao Yin
Published in IEEE Tran. Signal Processing
OverviewThis 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
CitationW. 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 paperW. 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 |
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 
in a standard (non-ergodic) sense.
Numerical experiments demonstrate effectiveness of PG-EXTRA and
validate our convergence results.