The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
A Proximal Gradient Algorithm for Decentralized Composite Optimization
Abstract
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 exchanges 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 O(1/k) in terms of the first-order optimality residual. When the smooth part vanishes, PG-EXTRA reduces to P-EXTRA, an algorithm without the gradients (so no “G” in the name), which has a slightly improved convergence rate at o(1/k) in a standard (non-ergodic) sense. Numerical experiments demonstrate effectiveness of PG-EXTRA and validate our convergence results.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“EXTRA converges at an o (1 /k ) rate when the objective function in (1) is convex, and it has a Q-linear rate when the objective function is strongly convex.”
From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [61]
Citations
Cites
Distributed Subgradient Methods for Multi-Agent Optimization
Nedic, A., & Ozdaglar, A. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.2009515 · Cited by 3,719
An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination
Cao, Y., Yu, W., Ren, W., & Chen, G. (2013) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2012.2219061 · Cited by 2,399
Distributed asynchronous deterministic and stochastic gradient optimization algorithms
Tsitsiklis, J., Bertsekas, D., & Athans, M. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104412 · Cited by 1,967
Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms
Bullo, F., Cortés, J., & Martínez, S. (2009) · Princeton University Press eBooks · doi:10.1515/9781400831470 · Cited by 1,509
PROBLEMS IN DECENTRALIZED DECISION MAKING AND COMPUTATION
Τσιτσικλής, Ι. (2014) · doi:10.12681/eadd/3778 · Cited by 1,278
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015) · SIAM Journal on Optimization · doi:10.1137/14096668x · Cited by 1,261 · cited 4×
“When the possibly-nondifferentiable term , we have in (2a) and (2b) and thus (4) In (3a) and (3b), we have and thus (5) The updates (4) and (5) are known as EXTRA, a recent algo-rithm for decentralized differentiable optimization [23].”
InfluentialSelf-citationOn the Linear Convergence of the ADMM in Decentralized Consensus Optimization
Shi, W., Ling, Q., Yuan, K., Wu, G., & Yin, W. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2304432 · Cited by 820
Self-citationDistributed Stochastic Subgradient Projection Algorithms for Convex Optimization
Sundhar Ram, S., Nedić, A., & Veeravalli, V. V. (2010) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-010-9737-7 · Cited by 814
Fastest Mixing Markov Chain on a Graph
Boyd, S., Diaconis, P., & Xiao, L. (2004) · SIAM Review · doi:10.1137/s0036144503423264 · Cited by 744
Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
Schizas, I. D., Ribeiro, A., & Giannakis, G. B. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2007.906734 · Cited by 685
Adaptation, Learning, and Optimization over Networks
Sayed, A. H. (2014) · Foundations and Trends in Machine Learning · doi:10.1561/2200000051 · Cited by 667
Distributed Sparse Linear Regression
Mateos, G., Bazerque, J. A., & Giannakis, G. B. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2055862 · Cited by 550
Distributed Robust Power System State Estimation
Kekatos, V., & Giannakis, G. B. (2013) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2012.2219629 · Cited by 521
Breakdown Points of Affine Equivariant Estimators of Multivariate Location and Covariance Matrices
Lopuhaa, H. P., & Rousseeuw, P. J. (1991) · The Annals of Statistics · doi:10.1214/aos/1176347978 · Cited by 446
Multi-Agent Distributed Optimization via Inexact Consensus ADMM
Chang, T.-H., Hong, M., & Wang, X. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2367458 · Cited by 444
Adaptation, Learning, and Optimization over Networks
Sayed, A. (2014) · now publishers, Inc. eBooks · doi:10.1561/9781601988515 · Cited by 415
Consensus-based distributed support vector machines
Forero, P. A., Caño, A., & Giannakis, G. B. (2010) · Cited by 364
Distributed Compressive Sensing
Baron, D., Duarte, M. F., Wakin, M. B., Sarvotham, S., & Baraniuk, R. G. (2009) · doi:10.21236/ada521228 · Cited by 346
Monitoring and Optimization for Power Grids: A Signal Processing Perspective
Giannakis, G. B., Kekatos, V., Gatsis, N., et al. (2012) · Cited by 264
Distributed Autonomous Online Learning: Regrets and Intrinsic Privacy-Preserving Properties
Yan, F., Sundaram, S., Vishwanathan, S. V. N., & Qi, Y. (2013) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2012.191 · Cited by 263
Monitoring and Optimization for Power Grids: A Signal Processing Perspective
Giannakis, G. B., Kekatos, V., Gatsis, N., Kim, S.-J., Zhu, H., & Wollenberg, B. F. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2013.2245726 · Cited by 235
Multirobot Active Target Tracking With Combinations of Relative Observations
Zhou, K., & Roumeliotis, S. I. (2011) · IEEE Transactions on Robotics · doi:10.1109/tro.2011.2114734 · Cited by 219
Distributed Random Projection Algorithm for Convex Optimization
Lee, S., & Nedic, A. (2013) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2013.2247023 · Cited by 184
Decentralized Sparse Signal Recovery for Compressive Sleeping Wireless Sensor Networks
Ling, Q., & Tian, Z. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2047721 · Cited by 173
Self-citationConsensus-based distributed linear support vector machines
Forero, P. A., Cano, A., & Giannakis, G. B. (2010) · Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks · doi:10.1145/1791212.1791218 · Cited by 171
A new method for a class of linear variational inequalities
He, B. (1994) · Mathematical Programming · doi:10.1007/bf01581141 · Cited by 162 · cited 1×
“solution follows from the standard analysis for contraction methods; see, for example, Theorem 3 in [29].”
MethodOn Distributed Optimization in Networked Systems
Johansson, B. (2008) · KTH Publication Database DiVA (KTH Royal Institute of Technology) · Cited by 114
Scalable and Robust Bayesian Inference via the Median Posterior
Minsker, S., Srivastava, S., Lin, L., & Dunson, D. B. (2014) · Cited by 75
Distributed iterative thresholding for ℓ0/ℓ1-regularized linear inverse problems
Ravazzi, C., Fosson, S. M., & Magli, E. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2403263 · Cited by 51
Fast Distributed First-Order Methods
Chen, A. I.-A. (2012) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 49
A scalable distributed algorithm for shape transformation in multi-robot systems
Ravichandran, R., Gordon, G. J., & Goldstein, S. C. (2007) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2007.4399631 · Cited by 30
Set intersection problems: supporting hyperplanes and quadratic programming
Pang, C. H. J. (2014) · Mathematical Programming · doi:10.1007/s10107-014-0759-z · Cited by 20
Distributed soft thresholding for sparse signal recovery
Ravazzi, C., Fosson, S. M., & Magli, E. (2013) · Globecom · doi:10.1109/glocom.2013.6831603 · Cited by 18
A stochastic primal-dual algorithm for distributed asynchronous composite optimization
Bianchi, P., Hachem, W., & Iutzeler, F. (2014) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2014.7032215 · Cited by 14
Convergence rate analysis of several splitting schemes
Davis, D., & Yin, W. (2014) · arXiv · doi:10.48550/arxiv.1406.4834 · Cited by 13
Self-citationA proximal gradient algorithm for decentralized nondifferentiable optimization
Shi, W., Ling, Q. H., Wu, G., & Yin, W. (2015) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2015.7178514 · Cited by 10
Self-citation
Research works printed but not linked: 3
- davis, 2014, ?Convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions ?
- deng, 2013, ?Parallel multi-block ADMM with convergence ?
- 2011, Foundations of Location Analysis
Cited by
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Nedić, A., Olshevsky, A., & Shi, W. (2017) · SIAM Journal on Optimization · doi:10.1137/16m1084316 · Cited by 1,069
Self-citationA survey of distributed optimization
Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., & Johansson, K. H. (2019) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2019.05.006 · Cited by 913
Asynchronous Decentralized Parallel Stochastic Gradient DescentPreprint
Lian, X., Zhang, W., Zhang, C., & Liu, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.06952 · Cited by 443
Push–Pull Gradient Methods for Distributed Optimization in Networks
Pu, S., Shi, W., Xu, J., & Nedic, A. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2972824 · Cited by 376
Self-citationDistributed Optimization for Control
Nedić, A., & Liu, J. (2018) · Annual Review of Control, Robotics, and Autonomous Systems · doi:10.1146/annurev-control-060117-105131 · Cited by 302
Metadata
- Authors
- Shi, W., Ling, Q., Wu, G., & Yin, W.
- Affiliations
- University of Science and Technology of China (CN)
- University of California, Los Angeles (US)
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2015-11
- Volume
- 63
- Issue
- 22
- Pages
- 6013-6023
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W1627780903
- Cited by
- 307
- References
- 36
- Citations by year
- 2026: 17 · 2025: 30 · 2024: 31 · 2023: 28 · 2022: 36 · 2021: 35 · 2020: 41 · 2019: 27 · 2018: 28 · 2017: 19 · 2016: 15
- FWCI
- 23.64
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Signal Processing (publishedVersion)
- Funders
- National Natural Science Foundation of China (61004137, 61573331)
- National Science Foundation (DMS-1317602)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Keywords
- distributed optimization, consensus optimization, multi-agent systems, proximal gradient method, composite objective function, nonsmooth optimization, fixed step size, ergodic convergence rate, compressed sensing, regularization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.