The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Push–Pull Gradient Methods for Distributed Optimization in Networks
Open accessAbstract
In this article, 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 new distributed gradient-based methods 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 gradients is pushed to the neighbors, whereas the information about the decision variable is pulled from the neighbors, hence giving the name “push-pull gradient methods.” The methods utilize two different graphs for the information exchange among agents and, as such, unify the algorithms with different types of distributed architecture, including decentralized (peer to peer), centralized (master-slave), and semicentralized (leader-follower) architectures. We show that the proposed algorithms and their many variants converge linearly for strongly convex and smooth objective functions over a network (possibly with unidirectional data links) in both synchronous and asynchronous random-gossip settings. In particular, under the random-gossip setting, “push-pull” is the first class of algorithms for distributed optimization over directed graphs. Moreover, we numerically evaluate our proposed algorithms in both scenarios, and show that they outperform other existing linearly convergent schemes, especially for ill-conditioned problems and networks that are not well balanced.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
Consensus seeking in multiagent systems under dynamically changing interaction topologies
Ren, W., & Beard, R. W. (2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.846556 · Cited by 6,569
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 1×
“References [7], [8], [9] studied time-varying and/or stochastic undirected networks.”
BackgroundBoyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874516 · Cited by 2,439
Gossip-based computation of aggregate information
Kempe, D., Dobra, A., & Gehrke, J. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238221 · Cited by 1,480
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
Self-citationDistributed Optimization Over Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2364096 · Cited by 1,187
Self-citationAchieving 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 · cited 10×
“Unlike the push-sum type protocol used in the previous literature [9], [14], our algorithm uses a row stochastic matrix for the mixing of the decision variables, while it employs a column stochastic matrix for tracking the average gradients.”
BackgroundMethodInfluentialSelf-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-citationHarnessing Smoothness to Accelerate Distributed Optimization
Qu, G., & Li, N. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2017.2698261 · Cited by 565
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization
Nedic, A., Olshevsky, A., & Rabbat, M. G. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2817461 · Cited by 534
Self-citationNEXT: In-Network Nonconvex Optimization
Lorenzo, P. D., & Scutari, G. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2524588 · Cited by 473
Diffusion Adaptation Over Networks
Sayed, A. H. (2014) · Academic Press Library in Signal Processing · doi:10.1016/b978-0-12-411597-2.00009-6 · Cited by 465
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2015) · 2015 54th IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402509 · Cited by 332 · cited 4×
“The structure of Algorithm 1 resembles that of the gradient tracking methods as in [9], [25] with the doubly stochastic matrix being split into a row-stochastic matrix and a column-stochastic matrix.”
MethodInfluentialSelf-citation1Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed GraphsPreprint
Nedić, A., & Olshevsky, A. (2016) · Cited by 315
A Proximal Gradient Algorithm for Decentralized Composite Optimization
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2461520 · Cited by 307
Self-citationPush-Sum Distributed Dual Averaging for convex optimization
Tsianos, K. I., Lawlor, S., & Rabbat, M. G. (2012) · 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426375 · Cited by 304 · cited 1×
“Reference [34] has been the first to propose a push-sum based distributed optimization algorithm for directed graphs.”
BackgroundDistributed stochastic gradient tracking methods
Pu, S., & Nedić, A. (2021) · Mathematical Programming · doi:10.1007/s10107-020-01487-0 · Cited by 266
Self-citationAverage consensus on general strongly connected digraphs
Cai, K., & Ishii, H. (2012) · Automatica · doi:10.1016/j.automatica.2012.08.003 · Cited by 263
ARock: An Algorithmic Framework for Asynchronous Parallel Coordinate Updates
Peng, Z., Xu, Y., Yan, M., & Yin, W. (2016) · SIAM Journal on Scientific Computing · doi:10.1137/15m1024950 · Cited by 247
Li, Z., Shi, W., & Yan, M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2926022 · Cited by 244
Self-citationA Linear Algorithm for Optimization Over Directed Graphs With Geometric Convergence
Xin, R., & Khan, U. A. (2018) · IEEE Control Systems Letters · doi:10.1109/lcsys.2018.2834316 · Cited by 243
Newton-Raphson Consensus for Distributed Convex Optimization
Varagnolo, D., Zanella, F., Cenedese, A., Pillonetto, G., & Schenato, L. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2449811 · Cited by 219
Linear Convergence in Optimization Over Directed Graphs With Row-Stochastic Matrices
Xi, C., Mai, V. S., Xin, R., Abed, E. H., & Khan, U. A. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2797164 · Cited by 215
Convergence of Asynchronous Distributed Gradient Methods Over Stochastic Networks
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2730481 · Cited by 214
Self-citationOptimal algorithms for smooth and strongly convex distributed optimization in networks
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., & Massoulié, L. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.08704 · Cited by 177
DEXTRA: A Fast Algorithm for Optimization Over Directed Graphs
Xi, C., & Khan, U. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2672698 · Cited by 172
A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks
Uribe, C. A., Lee, S., Gasnikov, A. V., & Nedić, A. (2020) · Information Theory and Applications Workshop (ITA) · doi:10.1080/10556788.2020.1750013 · Cited by 151
Geometrically convergent distributed optimization with uncoordinated step-sizes
Nedic, A., Olshevsky, A., Shi, W., & Uribe, C. A. (2017) · 2017 American Control Conference (ACC) · doi:10.23919/acc.2017.7963560 · Cited by 145
Self-citationFROST—Fast row-stochastic optimization with uncoordinated step-sizes
Xin, R., Xi, C., & Khan, U. A. (2019) · EURASIP Journal on Advances in Signal Processing · doi:10.1186/s13634-018-0596-y · Cited by 122
Gossip Algorithms for Convex Consensus Optimization Over Networks
Lu, J., Tang, C. Y., Regier, P. R., & Bow, T. D. (2011) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2160020 · Cited by 115
A Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization
Mokhtari, A., Shi, W., Ling, Q. H., & Ribeiro, A. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2613678 · Cited by 113
Self-citationA Push-Pull Gradient Method for Distributed Optimization in Networks
Pu, S., Shi, W., Xu, J., & Nedić, A. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619047 · Cited by 104
Self-citationAsynchronous Gossip-Based Random Projection Algorithms Over Networks
Lee, S., & Nedić, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2460051 · Cited by 97
Linear Time Average Consensus and Distributed Optimization on Fixed Graphs
Olshevsky, A. (2017) · SIAM Journal on Control and Optimization · doi:10.1137/16m1076629 · Cited by 87
ExtraPush 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
A Distributed Stochastic Gradient Tracking Method
Pu, S., & Nedić, A. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8618708 · Cited by 70
Self-citationExtraPush for convex smooth decentralized optimization over directed networks
Zeng, J., & Yin, W. (2015) · arXiv · doi:10.48550/arxiv.1511.02942 · Cited by 65
Decentralized 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
Swarming for Faster Convergence in Stochastic Optimization
Pu, S., & García, A. (2018) · SIAM Journal on Control and Optimization · doi:10.1137/17m1111085 · Cited by 16
Self-citationMathkar, A. S., & Borkar, V. S. (2016) · SIAM Journal on Control and Optimization · doi:10.1137/140992588 · Cited by 16
Cited by
Distributed stochastic gradient tracking methods
Pu, S., & Nedić, A. (2021) · Mathematical Programming · doi:10.1007/s10107-020-01487-0 · Cited by 266
Self-citationCommunication-efficient distributed learning: An overview
Cao, X., Başar, T., Diggavi, S., Eldar, Y. C., Letaief, K. B., Poor, H. V., & Zhang, J. (2023) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2023.3242710 · Cited by 139
“push-pull algorithm, in [29]), and decentralized optimization over time-varying directed networks (e.”
Background
Metadata
- Authors
- Pu, S., Shi, W., Xu, J., & Nedic, A.
- Venue
- IEEE Transactions on Automatic Control
- Published
- 2021-01
- Volume
- 66
- Issue
- 1
- Pages
- 1-16
- ISSN
- 0018-9286 (ISSN-L)
- 1558-2523
- 2334-3303
- OpenAlex
- W3006548771
- Cited by
- 376
- References
- 42
- FWCI
- 21.22
- Type
- journal article
- Language
- en
- Open access
- green
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.