A Proximal Gradient Algorithm for Decentralized Composite Optimization
The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
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 · cited 8×
“We have hand-op-timized this parameter and the step sizes for DADMM, DSM, and P-EXTRA.”
MethodInfluentialAn 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 · cited 1×
“The existing algorithms that solve problem (1) include the primal-dual domain methods such as the decentralized alternating direction method of multipliers (DADMM) [16], [21] and the primal domain methods including the distributed sub-gradient method (DSM) [22].”
MethodSelf-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 · cited 1×
“Typical choices of can be found in [23], [28].”
BackgroundConsensus 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 · cited 14×
“9 k 0 100 200 300 400 500 R el a ti v e E rr o r 10-10 10-8 10-6 10-4 10-2 100 DSM, step size ,k = 9:5=k1=2 DADMM, penalty coe/cient c = 0:0038 P-EXTRA, step size , = 46 k 0 100 200 300 400 500 S u cc es si ve D i, er en ce 10-10 10-5 100 105 DSM, step size ,k = 9:5=k1=2 DADMM, penalty coe/cient c = 0:0038 P-EXTRA, st…”
BackgroundMethodInfluential
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
“In particular, the authors of Shi, Ling, Wu, and Yin (2015b) developed a proximal gradient exact first-order algorithm (PG-EXTRA) by using proximal operations ( Parikh & Boyd, 2014 ).”
BackgroundMethodAsynchronous 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 436
“This issue was fixed later by Shi et al. [2015a], Wu et al. [2016] by using the gradients of last two instead of one iterates in each iteration, which was later improved in Li et al. [2017], Shi et al. [2015b] by considering proximal gradients.”
MethodPush–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
“Work in [28], [29] investigates proximal-gradient methods which can tackle (1) with proximal friendly component functions.”
BackgroundSelf-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
An operator splitting approach for distributed generalized Nash equilibria computation
Yi, P., & Pavel, L. (2019) · Automatica · doi:10.1016/j.automatica.2019.01.008 · Cited by 271
“∇xi fi(xi, x−i) with local objective function value observations (taking the simultaneous perturbation stochastic approximation in Spall (1992) as an example), or by utilizing the estimation techniques developed in Salehisadaghiani & Pavel (2016b).”
Li, Z., Shi, W., & Yan, M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2926022 · Cited by 244
“By making a simple modification over PG-EXTRA [1], our proposed algorithm brings a big improvement in the speed and the dependency of convergence over networks.”
BackgroundMethodInfluentialSelf-citationDistributed nonconvex constrained optimization over time-varying digraphs
Scutari, G., & Sun, Y. (2019) · Mathematical Programming · doi:10.1007/s10107-018-01357-w · Cited by 210
Communication Compression for Decentralized Training
Tang, H., Gan, S., Zhang, C., Zhang, T., & Liu, J. (2018) · arXiv · doi:10.48550/arxiv.1803.06443 · Cited by 206
“Two methods [Li et al., 2017, Shi et al., 2015] were proposed to blackuce the steady point error in decentralized gradient descent convex optimization.”
MethodCommunication-efficient algorithms for decentralized and stochastic optimization
Lan, G., Lee, S., & Zhou, Y. (2020) · Mathematical Programming · doi:10.1007/s10107-018-1355-4 · Cited by 187
On Nonconvex Decentralized Gradient Descent
Zeng, J., & Yin, W. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2818081 · Cited by 184
Self-citationAybat, N. S., Wang, Z., Lin, T., & Ma, S. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2713046 · Cited by 172
“In [21], the proximal gradient exact first-order algorithm (PG-EXTRA) is proposed; PG-EXTRA is an extension of the algorithm EXTRA [23] to handle the non-smooth terms { ξ i } i ∈N .”
BackgroundMethodInfluentialD$^2$: Decentralized Training over Decentralized Data
Tang, H., Lian, X., Yan, M., Zhang, C., & Liu, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.07068 · Cited by 159
“Existing decentralized consensus algorithms [Li et al., 2017, Shi et al., 2015b] use a modification of the doubly stochastic matrix such that λ > 0, i.e., choose W = ( ˜ W + I ) /2 where W is a doubly stochastic matrix.”
BackgroundSun, Y., Scutari, G., & Daneshmand, A. (2022) · SIAM Journal on Optimization · doi:10.1137/19m1259973 · Cited by 155
“additive convex nonsmooth term in the objective, [39] proposed PG-EXTRA, which is thus applicable to (P) over undirected graphs, possibly with different local nonsmooth functions.”
BackgroundDecentralized Proximal Gradient Algorithms With Linear Convergence Rates
Alghunaim, S. A., Ryu, E. K., Yuan, K., & Sayed, A. H. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3009363 · Cited by 151
“In the numerical experiment, we test the performance of two wellknown decentralized proximal methods, PG-EXTRA [21] and DLADMM [22], [23].”
BackgroundMethodInfluentialDecentralized Consensus Optimization With Asynchrony and Delays
Wu, T., Yuan, K., Ling, Q., Yin, W., & Sayed, A. H. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2017.2695121 · Cited by 99
“Computing decentralized geometric medians have various interesting applications, see [2] for more detail.”
BackgroundMethodResultInfluentialSelf-citationDecentralized Frank–Wolfe Algorithm for Convex and Nonconvex Problems
Wai, H.-T., Lafond, J., Scaglione, A., & Moulines, É. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2685559 · Cited by 144
“We compare the algorithms of PG-EXTRA [16] (with fixed step size α = 1 /d ), DPG [15] (with step size α t = 1 /t ) and BHT [7].”
InfluentialA Unification and Generalization of Exact Distributed First-Order Methods
Jakovetić, D. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2018.2846183 · Cited by 142
“In particular, Shi et al. (2015) on the one hand and Qu and Li (2017) and Nedic et al. (2016) on the other hand propose two different types of methods that are designed from very different perspectives.”
BackgroundMethodZONE: Zeroth-Order Nonconvex Multiagent Optimization Over Networks
Hajinezhad, D., Hong, M., & Garcia, A. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2896025 · Cited by 137
“Other related algorithms can be found in [9–11].”
BackgroundLi, B., Cen, S., Chen, Y., & Chi, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.05844 · Cited by 134
Salehisadaghiani, F., Shi, W., & Pavel, L. (2019) · Automatica · doi:10.1016/j.automatica.2019.01.012 · Cited by 128
Self-citationDistributed Optimization for Smart Cyber-Physical Networks
Notarstefano, G., Notarnicola, I., & Camisa, A. (2019) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000020 · Cited by 122
Parallel and Distributed Successive Convex Approximation Methods for Big-Data Optimization
Scutari, G., & Sun, Y. (2018) · Lecture notes in mathematics · doi:10.1007/978-3-319-97142-1_3 · Cited by 122
Distributed Mirror Descent for Online Composite Optimization
Yuan, D., Hong, Y., Ho, D. W. C., & Xu, S. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2987379 · Cited by 113
“Different from the aforementioned works that deal only with non-composite objective functions, the authors in [16], [31] considered a decentralized composite optimization problem where the local objective function of every node is composed of a smooth function and a non-smooth regularizer.”
BackgroundMethodInfluentialDistributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
Xu, J., Tian, Y., Sun, Y., & Scutari, G. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3086579 · Cited by 109
“Sublinear rate of O (1 /k ) has been proved for a variety of schemes, including PG-EXTRA [17], D-FBBS [18] and DPGA [19].”
BackgroundForward-Backward-Half Forward Algorithm for Solving Monotone Inclusions
Briceño-Arias, L. M., & Davis, D. (2018) · SIAM Journal on Optimization · doi:10.1137/17m1120099 · Cited by 104
A Push-Pull Gradient Method for Distributed Optimization in Networks
Pu, S., Shi, W., Xu, J., & Nedic, A. (2018) · 2018 IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619047 · Cited by 94
Self-citationImproved Convergence Rates for Distributed Resource Allocation
Nedić, A., Olshevsky, A., & Shi, W. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619322 · Cited by 100
Self-citationWalkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization
Mao, X., Yuan, K., Hu, Y., Gu, Y., Sayed, A. H., & Yin, W. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2983167 · Cited by 90
“This approach includes well-known algorithms such as diffusion [5], [6] and consensus [11], [12], distributed ADMM (D-ADMM) [13]–[15], EXTRA [16], PG-EXTRA [17], DIGing [18], exact diffusion [19], NIDS [20], and beyond.”
MethodInfluentialSelf-citationOn the Influence of Bias-Correction on Distributed Stochastic Optimization
Yuan, K., Alghunaim, S. A., Ying, B., & Sayed, A. H. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3008605 · Cited by 89
“In addition to exact diffusion, there exist some other useful bias-correction methods such as EXTRA [1], [17], DIGing or gradient-tracking methods [3], [18]–[21], Aug-DGM [22], [23] and NIDS [24].”
MethodDecentralized Accelerated Gradient Methods With Increasing Penalty Parameters
Li, H., Fang, C., Yin, W., & Lin, Z. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3018317 · Cited by 88
Self-citationExtraPush for Convex Smooth Decentralized Optimization over Directed Networks
Zeng, J., & Yin, W. (2017) · Journal of Computational Mathematics · doi:10.4208/jcm.1606-m2015-0452 · Cited by 82
“Another line of future research is to generalize ExtraPush to handle the sum of smooth and proximable (possibly nonsmooth) functions as done in [14] to generalize Extra this way.”
BackgroundSelf-citationDistributed stochastic variance reduced gradient methods by sampling extra data with replacement
Lee, J. D., Lin, Q., Ma, T., & Yang, T. (2017) · Journal of Machine Learning Research · Cited by 78
Variance-Reduced Stochastic Learning by Networked Agents Under Random Reshuffling
Yuan, K., Ying, B., Liu, J., & Sayed, A. H. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2872003 · Cited by 67
“We therefore combine SAGA and PG-EXTRA [35] to reach prox-DSA that is able to handle non-smooth proximable regularizations.”
MethodQ-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning
Elgabli, A., Park, J., Bedi, A. S., Issaid, C. B., Bennis, M., & Aggarwal, V. (2021) · IEEE Transactions on Communications · doi:10.1109/tcomm.2020.3026398 · Cited by 51
“In the distributed optimization literature, there are a variety of algorithms that are broadly categorized into primal meth-ods [27]–[30] and primal-dual methods [31]–[33].”
An Optimal Algorithm for Decentralized Finite-Sum Optimization
Hendrikx, H., Bach, F., & Massoulié, L. (2021) · SIAM Journal on Optimization · doi:10.1137/20m134842x · Cited by 77
A Linearly Convergent Proximal Gradient Algorithm for Decentralized OptimizationPreprint
Alghunaim, S. A., Yuan, K., & Sayed, A. H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.07996 · Cited by 76
“PG-EXTRA [23] extends EXTRA [1] to handle non-smooth regularization local terms and it establishes an improved rate o (1 /i ) under the same condition.”
BackgroundHybrid Voltage Control in Distribution Networks Under Limited Communication Rates
Liu, H. J., Shi, W., & Zhu, H. (2018) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2018.2797692 · Cited by 75
“Such use of subgradient and notation have appeared in many recent references including [28], [29].”
BackgroundSelf-citationDistributed Proximal Algorithms for Multiagent Optimization With Coupled Inequality Constraints
Li, X., Feng, G., & Xie, L. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2989282 · Cited by 75
“Distributed proximal gradient algorithms were also developed for tackling composite objective functions in [21], [22].”
Federated Composite OptimizationPreprint
Yuan, H., Zaheer, M., & Reddi, S. J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.08474 · Cited by 75
“2 not only matches the rate by Stich (2019) for smooth, unconstrained FedAvg but also allows for a general non-smooth composite ψ, general Bregman divergence induced by h, and arbitrary norm ‖ · ‖.”
BackgroundRobust and communication-efficient collaborative learning
Reisizadeh, A., Taheri, H., Mokhtari, A., Hassani, H., & Pedarsani, R. (2019) · arXiv · doi:10.48550/arxiv.1907.10595 · Cited by 73
“…descent-type methods (Nedic and Ozdaglar, 2009; Jakovetic et al., 2014; Yuan et al., 2016; Qu and Li, 2017), augmented Lagrangian algorithms (Shi et al., 2015a,b; Mokhtari and Ribeiro, 2016), distributed variants of the alternating direction method of multipliers (ADMM) (Schizas et al.,…”
MethodGlobal Convergence Rate of Proximal Incremental Aggregated Gradient Methods
Vanli, N. D., Gürbüzbalaban, M., & Ozdaglar, A. (2018) · SIAM Journal on Optimization · doi:10.1137/16m1094415 · Cited by 68
“Notable examples include constrained and regularized least squares problems that arise in various machine learning applications [9, 30, 41], distributed optimization problems that arise in wireless sensor network [28, 35] as well as smart grid applications [15, 16] and constrained optimization of separable problems [2…”
BackgroundExtraPush for convex smooth decentralized optimization over directed networks
Zeng, J., & Yin, W. (2015) · arXiv · doi:10.48550/arxiv.1511.02942 · Cited by 65
“Another line of future research is to generalize ExtraPush to handle the sum of smooth and proximable (possibly nonsmooth) functions as done in [14] to generalize Extra this way.”
BackgroundSelf-citationDecentralised federated learning with adaptive partial gradient aggregation
Jiang, J., & Hu, L. (2020) · CAAI Transactions on Intelligence Technology · doi:10.1049/trit.2020.0082 · Cited by 64
“…optimisation methods have been proposed to overcome the challenges in large scale distributed machine learning, such as primal methods [13 – 15] and primal-dual methods [16 – 18], while, in federated learning settings, the communication cost often becomes dominant compared to the…”
MethodA Bregman Splitting Scheme for Distributed Optimization Over Networks
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2805260 · Cited by 62
“For generalization, they extend the algorithm to general convex problems and composite convex problems, yielding PEXTRA and PG-EXTRA, respectively [40].”
BackgroundMethodInfluentialGADMM: Fast and Communication Efficient Framework for Distributed Machine Learning
Elgabli, A., Park, J., Bedi, A. S., Bennis, M., & Aggarwal, V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.00047 · Cited by 42
“…there are a variety of distributed optimization algorithms proposed in the literature, such as primal methods (Jakoveti´c et al., 2014; Nedi´c and Olshevsky, 2014; Nedi´c and Ozdaglar, 2009; Shi et al., 2015) and primal-dual methods (Chang et al., 2014a; Koppel et al., 2017; Bedi et al., 2019).”
MethodDecentralized Dynamic Optimization for Power Network Voltage Control
Liu, H. J., Shi, W., & Zhu, H. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2631886 · Cited by 60
Self-citationRevisiting EXTRA for Smooth Distributed Optimization
Li, H., & Lin, Z. (2020) · SIAM Journal on Optimization · doi:10.1137/18m122902x · Cited by 56
Distributed Stochastic Consensus Optimization With Momentum for Nonconvex Nonsmooth Problems
Wang, Z., Zhang, J., Chang, T., Li, J., & Luo, Z.-Q. T. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3097211 · Cited by 55
“We show that the PPDM algorithm can have a close connection with the PG-EXTRA algorithm in [8].”
BackgroundMethodInfluentialZhu, Y., Wen, G., Yu, W., & Yu, X. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3070398 · Cited by 54
Shen, Z., Mokhtari, A., Zhou, T., Zhao, P., & Qian, H. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.09969 · Cited by 54
“EXTRA (Shi et al., 2015a) improves over DGD by incorporating information from the last two iterates and is shown to converge linearly.”
BackgroundMethodInfluentialMulti-consensus Decentralized Accelerated Gradient DescentPreprint
Ye, H., Luo, L., Zhou, Z., & Zhang, T. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.00797 · Cited by 52
“One class of them is primal-only methods, including decentralized gradient methods (Nedic and Ozdaglar, 2009; Yuan et al., 2016), decentralized accelerated gradient method (Jakoveti ´ c et al., 2014; Qu and Li, 2019) and EXTRA (Shi et al., 2015b; Li et al., 2019; Mokhtari and Ribeiro, 2016).”
BackgroundMethodInfluentialDistributed Optimization With Coupling Constraints
Wu, X., Wang, H., & Lu, J. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3169955 · Cited by 49
“Also, according to [4], each node i manages to locally determine [P ]ij and [P ]ij ∀j ∈ N̄i to satisfy Assumption 1.”
BackgroundMethodInfluentialDistributed Robust Optimization for Networked Agent Systems With Unknown Nonlinearities
Wen, G., Zheng, W. X., & Wan, Y. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3216965 · Cited by 49
“Recent studies on distributed optimization have mainly focused on designing discrete-time algorithms, which can be roughly categorized into the following two classes: algorithms with diminishing step-sizes [9] and algorithms with a fixed step-size [10].”
BackgroundWei, Y., Fang, H., Zeng, X., Chen, J., & Pardalos, P. M. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2936355 · Cited by 48
“[ 17 ] - [ 18 ] proposed several proximal gradient algorithms for solving the distributed optimization problems with nonsmooth local cost functions.”
BackgroundMethodNetworked Signal and Information Processing: Learning by multiagent systems
Vlaski, S., Kar, S., Sayed, A. H., & Moura, J. M. F. (2023) · IEEE Signal Processing Magazine · doi:10.1109/msp.2023.3267896 · Cited by 47
“In this case, noisy and biased gradient estimates obtained from measuring function values using various difference approximations are used in the algorithm design in lieu of exact or unbiased gradients as assumed in the first-order setting — see [38,44] and the references therein for more details.”
MethodDistributed Learning Systems with First-Order Methods
Liu, J., & Zhang, C. (2020) · Foundations and Trends in Databases · doi:10.1561/1900000062 · Cited by 46
“…Li et al. (2019b), Li and Yan (2019), Tang et al. (2018b), Li et al. (2019a), He et al. (2018), Lian et al. (2017), Li and Yan (2017), Simonetto et al. (2017), Colin et al. (2016), Yuan et al. (2016), Shi et al. (2015b), Shi et al. (2015a), Ling and Ribeiro (2013), and Nedić and Ozdaglar (2009).”
Nonsmooth Resource Allocation of Multiagent Systems With Disturbances: A Proximal Approach
Zhu, Y., Wen, G., Yu, W., & Yu, X. (2021) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2021.3068349 · Cited by 43
First-Order Methods for Large-Scale Market Equilibrium ComputationPreprint
Gao, Y., & Kroer, C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.06747 · Cited by 43
AB /Push-Pull method for distributed optimization in time-varying directed networks
Nedić, A., Nguyen, D. T. A., & Nguyen, D. T. (2023) · Optimization methods & software · doi:10.1080/10556788.2023.2261602 · Cited by 42
“Reference [23] investigates decentralized algorithms that take advantage of proximal operations for the non-smooth terms.”
BackgroundAccelerated Gradient Tracking over Time-varying Graphs for Decentralized OptimizationPreprint
Li, H., & Lin, Z. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.02596 · Cited by 42
“Besides gradient tracking, EXTRA is another important family of decentralized optimization algorithms.”
BackgroundInfluentialGraph and Distributed Extensions of the Douglas–Rachford Method
Bredies, K., Chenchene, E., & Naldi, E. (2024) · SIAM Journal on Optimization · doi:10.1137/22m1535097 · Cited by 41
A Sparse Interactive Model for Matrix Completion with Side Information.
Lü, J., Liang, G., Sun, J., & Bi, J. (2016) · PubMed · Cited by 41
Consensus-Based Distributed Optimization Enhanced by Integral Feedback
Wang, X., Mou, S., & Anderson, B. D. O. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3169179 · Cited by 40
“2) To achieve exponential convergence, the proposed result only requires the sum of all objective functions to be strongly convex at the optimum point1; this is a more relaxed condition compared with the existing results that require all agents’ local objective functions to be strongly convex [26]–[31].”
BackgroundMethodResultInfluentialA Canonical Form for First-Order Distributed Optimization Algorithms
Sundararajan, A., Scoy, B. V., & Lessard, L. (2019) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2019.8814838 · Cited by 40
Distributed and Inexact Proximal Gradient Method for Online Convex Optimization
Bastianello, N., & Dall’Anese, E. (2021) · European Control Conference (ECC) · doi:10.23919/ecc54610.2021.9654953 · Cited by 40
“PG-EXTRA [20] undirected sub-linear(ergodic) PG-ExtraPush [24] directed quasi-strongly convex bounded subgr. linear DDPG [25] undirected,asynchronous strongly convex sub-linear (objective conv.)”
BackgroundMethodResultInfluentialSurrogate-based distributed optimisation for expensive black-box functions
Li, Z., Dong, Z., Liang, Z., & Ding, Z. (2020) · Automatica · doi:10.1016/j.automatica.2020.109407 · Cited by 39
Exact Optimal Accelerated Complexity for Fixed-Point IterationsPreprint
Park, J., & Ryu, E. K. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2201.11413 · Cited by 38
“We applied PG-EXTRA, PG-EXTRA combined with OHM, PG-EXTRA with (OC-Halpern), and PG-EXTRA with Restarted OC-Halpern (OS-PPMres0 ), since PG-EXTRA can be understood as a fixed-point iteration (Wu et al., 2018).”
BackgroundMethodInfluentialDecentralized consensus optimization with asynchrony and delays
Wu, T., Yuan, K., Ling, Q. H., Yin, W., & Sayed, A. H. (2016) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2016.7869516 · Cited by 34
“To establish convergence under delays, we cannot follow the existing analysis of PG-EXTRA [2]; instead, motivated by [30], [32], a new non-Euclidean metric is introduced to absorb the delays.”
MethodResultSelf-citationMaros, M., & Jaldén, J. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619626 · Cited by 34
“Dual and primal-dual methods typically converge to the optimal solution using a constant step-size [14], [16], [6], [17], [21], [5].”
MethodResource-Aware Exact Decentralized Optimization Using Event-Triggered Broadcasting
Liu, C., Li, H., & Shi, Y. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3014316 · Cited by 34
“The method in [35] has the same primal-dual structure, as explained in [36].”
BackgroundMethodA Decentralized Proximal Point-type Method for Saddle Point ProblemsPreprint
Liu, W., Mokhtari, A., Ozdaglar, A., Pattathil, S., Shen, Z., & Zheng, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.14380 · Cited by 32
Parallel multi-wavelength calibration algorithm for radio astronomical arrays
Brossard, M., Korso, M. N. E., Pesavento, M., Boyer, R., Larzabal, P., & Wijnholds, S. J. (2017) · Signal Processing · doi:10.1016/j.sigpro.2017.12.014 · Cited by 31
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning
Elgabli, A., Park, J., Bedi, A. S., Bennis, M., & Aggarwal, V. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9054491 · Cited by 31
DISA: A Dual Inexact Splitting Algorithm for Distributed Convex Composite Optimization
Guo, L., Shi, X., Yang, S., & Cao, J. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3301289 · Cited by 31
“Recall several existing distributed primal-dual algorithms such as DPGA [23], PG-EXTRA [24], NIDS [25], and D-iPGM [27].”
MethodLi, Z., Liu, B., & Ding, Z. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3071058 · Cited by 30
“For comparison purposes, we have included two commonly used optimization algorithms: the ADMM [9] and distributed proximal gradient (DPG) [45].”
MethodDistributed decision-coupled constrained optimization via Proximal-Tracking
Falsone, A., & Prandini, M. (2021) · Automatica · doi:10.1016/j.automatica.2021.109938 · Cited by 29
New convergence analysis of a primal-dual algorithm with large stepsizes
Li, Z., & Yan, M. (2021) · Advances in Computational Mathematics · doi:10.1007/s10444-020-09840-9 · Cited by 29
Li, H., Hu, J., Ran, L., Wang, Z., Lü, Q., Du, Z., & Huang, T. (2021) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2021.3072373 · Cited by 28
“Assumption 1 is not uncommon in recent literature [1], [16], [33], [35] and one can see [36, Section 10.2] for detailed discussions about the strongly convex and convex properties.”
BackgroundMethodInfluentialDistributed subgradient method for multi‐agent optimization with quantized communication
Li, J., Chen, G., Wu, Z., & He, X. (2016) · Mathematical Methods in the Applied Sciences · doi:10.1002/mma.4044 · Cited by 28
“When the gradients of local objectives are Lipschitz continuous, the recent algorithm EXTRA proposed in [16,17] showed a better performance of convergence.”
Continuous-time Analysis of Anchor Acceleration
Suh, J., Park, J., & Ryu, E. K. (2023) · neural information processing systems · doi:10.52202/075280-1422 · Cited by 27
Guo, L., Shi, X., Cao, J., & Wang, Z. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3250839 · Cited by 27
“In this subsection, we compare D-iPGM (εk = 0), PGEXTRA [20], and NIDS [21] from the perspective of operator splitting.”
BackgroundMethodInfluentialZhang, J., Liu, H., So, A. M., & Ling, Q. H. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3092347 · Cited by 27
“We also demonstrate the connection between PAD and several dual domain methods, including EXTRA [19], DLM [14], and PG-EXTRA [20].”
MethodInfluentialSelf-citationMaros, M., & Jaldén, J. (2019) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2019.2892055 · Cited by 26
“Doing so we will now establish the conditions over ρ ξ and η for which P-EXTRA is guaranteed to converge according to [13] and the conditions under which generalized ADMM is guaranteed to converge according to [15].”
BackgroundMethodResultInfluentialZhou, X., Ma, Z., Zou, S., Zhang, J., & Guo, Y. (2022) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2022.3201814 · Cited by 26
“Remark: Note that this assumption implies that the corresponding optimization problem is solvable, which is common in the consensus-based distributed optimization literature, such as [32], [33].”
BackgroundDistributed Big-Data Optimization via Blockwise Gradient Tracking
Notarnicola, I., Sun, Y., Scutari, G., & Notarstefano, G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3008713 · Cited by 26
“Primal-based distributed methods that converge to an exact consensual solution using fixed step-sizes are available in the literature; they can be roughly grouped as i) [19], [20]; ii) [21]–[23], iii) [8], [24]–[29]; and iv) [30]–[33].”
MethodA geometrically convergent method for distributed optimization over time-varying graphs
Nedić, A., Olshevsky, A., & Shi, W. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798402 · Cited by 25
“…that work over undirected fixed graphs and usually need a diminishing step size to reach exact convergence; references [16]–[21], [23], [24], [27] concern about primal-dual-like methods which can deploy constant step size and converge quickly and exactly to the solution over undirected…”
BackgroundSelf-citationA Sharp Convergence Rate Analysis for Distributed Accelerated Gradient MethodsPreprint
Li, H., Fang, C., Yin, W., & Lin, Z. (2018) · arXiv (Cornell University) · Cited by 25
Self-citationFlexPD: A Flexible Framework of First-Order Primal-Dual Algorithms for Distributed Optimization
Mansoori, F., & Wei, E. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3083981 · Cited by 24
“The proximal gradient algorithm in [38] extends EXTRA algorithm in [37] to non-smooth settings and its asynchronous version is introduced in [46].”
MethodVariance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning
Zhang, J., Liu, H., So, A. M., & Ling, Q. H. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3240652 · Cited by 24
“This convergence error can be eliminated with local historic information, for example, in exact first-order algorithm (EXTRA) [11], [12], primal-dual methods [13]–[15], exact diffusion [16], [17], and gradient tracking [18]–[20].”
BackgroundSelf-citationHuang, Y., Meng, Z., Sun, J. Q., & Ren, W. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3293521 · Cited by 23
“Inrecentyears,manydiscrete-timeandcontinuous-timedistributed optimizationalgorithmshavebeenproposedin[4],[5],[6],[7],[8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [22], [23], [24], [19], [20], and [21].”
BackgroundDistributed consensus-based multi-agent convex optimization via gradient tracking technique
Li, H., Zhang, H., Wang, Z., Zhu, Y., & Han, Q. (2019) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2019.01.050 · Cited by 23
A Computation-Efficient Decentralized Algorithm for Composite Constrained Optimization
Lü, Q., Liao, X., Li, H., & Huang, T. (2020) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2020.3037837 · Cited by 23
“ByextendingEXTRA[14]todeal with local non-smooth terms, PG-EXTRA is proposed in [31] and an improved convergence is established.”
BackgroundMethodInfluentialPrimal–Dual Fixed Point Algorithms Based on Adapted Metric for Distributed Optimization
Li, H., Zheng, Z., Lü, Q., Wang, Z., Gao, L., Wu, G., Ji, L., & Wang, H. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3110295 · Cited by 23
“Similarly, Li et al. [38] proposed NIDS algorithm by combining EXTRA [31] and proximal operations, which achieved the same convergence as [37] and could employ a larger stepsize.”
BackgroundMethodSelf-citationLANA: An ADMM-like Nash equilibrium seeking algorithm in decentralized environment
Shi, W., & Pavel, L. (2017) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2017.7962967 · Cited by 23
“This proposition has appeared in recent works [27], [28] as the key to provide o ( 1”
BackgroundSelf-citationA Primal-Dual Forward-Backward Splitting Algorithm for Distributed Convex Optimization
Li, H., Su, E., Wang, C., Liu, J., Zheng, Z., Wang, Z., & Xia, D. (2021) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2021.3098831 · Cited by 22
“In [34], the authors employed the composite structure to propose an exact first-order method (PG-EXTRA) and presented well performance.”
MethodYu, Z., Ho, D. W. C., Yuan, D., & Liu, J. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3127278 · Cited by 22
Slavakis, K., & Yamada, I. (2018) · Optimization · doi:10.1080/02331934.2018.1505885 · Cited by 22
“3 Contributions Driven by the similarity between the algorithmic solution of [26, 27] and HSDM, and aiming at solving (1), this study introduces a new member to the HSDM family of algorithms: the Fejér-monotone (FM-)HSDM.”
BackgroundMethodInfluentialLi, H., Fang, C., & Lin, Z. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.10802 · Cited by 22
“Existing decentralized algorithms include the distributed subgradient (gradient) method [11, 12, 13, 14, 15, 16, 17], the fast gradient method [18], the dual averaging method [19], the dual decomposition [20], ADMM [21, 22, 23] and EXTRA [10, 24].”
MethodYan, J., Shi, X., Guo, L., Wan, Y., & Wen, G. (2024) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2024.3407660 · Cited by 21
“In comparison with [18], [21], [22], [23], the selection of step size in DDP-ADMM is more flexible and suitable for parameter settings in a distributed environment.”
BackgroundMethodInfluential
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.