The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Harnessing Smoothness to Accelerate Distributed Optimization
Open accessAbstract
There has been a growing effort in studying the distributed optimization problem over a network. The objective is to optimize a global function formed by a sum of local functions, using only local computation and communication. The literature has developed consensus-based distributed (sub)gradient descent (DGD) methods and has shown that they have the same convergence rate$O(\frac{\log t}{\sqrt{t}})$as the centralized (sub)gradient methods (CGD), when the function is convex but possibly nonsmooth. However, when the function is convex and smooth, under the framework of DGD, it is unclear how to harness the smoothness to obtain a faster convergence rate comparable to CGD's convergence rate. In this paper, we propose a distributed algorithm that, despite using the same amount of communication per iteration as DGD, can effectively harnesses the function smoothness and converge to the optimum with a rate of$O(\frac{1}{t})$. If the objective function is further strongly convex, our algorithm has a linear convergence rate. Both rates match the convergence rate of CGD. The key step in our algorithm is a novel gradient estimation scheme that uses history information to achieve fast and accurate estimation of the average gradient. To motivate the necessity of history information, we also show that it is impossible for a class of distributed algorithms like DGD to achieve a linear convergence rate without using history information even if the objective function is strongly convex and smooth.
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
Consensus and Cooperation in Networked Multi-Agent Systems
Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2006.887293 · Cited by 10,522 · cited 1×
“2The selection of the consensus weights is an intensely studied problem (see [35] and [36]).”
BackgroundErdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
Horn, R. A., & Johnson, C. R. (2012) · doi:10.1017/cbo9781139020411 · Cited by 4,642
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
Expander graphs and their applications
Hoory, S., Linial, N., & Wigderson, A. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01126-8 · Cited by 1,723
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
Distributed 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
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2161027 · Cited by 947
Distributed 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 · cited 1×
“Extensions of these work have been proposed that deal with various realistic conditions, such as stochastic subgradient errors [10], directed or random communication graphs [11]–[13], linear scaling in network size [14], and heterogeneous local constraints [15], [16].”
BackgroundOn Distributed Convex Optimization Under Inequality and Equality Constraints
Zhu, M., & Martinez, S. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2167817 · Cited by 759
Convergence Speed in Distributed Consensus and Averaging
Olshevsky, A., & Tsitsiklis, J. N. (2009) · SIAM Journal on Control and Optimization · doi:10.1137/060678324 · Cited by 692
On the Convergence of Decentralized Gradient Descent
Yuan, K., Ling, Q., & Yin, W. (2013) · arXiv · doi:10.48550/arxiv.1310.7063 · Cited by 635
Fast Distributed Gradient Methods
Jakovetic, D., Xavier, J., & Moura, J. M. F. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2298712 · Cited by 624
Distributed Spectrum Sensing for Cognitive Radio Networks by Exploiting Sparsity
Bazerque, J. A., & Giannakis, G. B. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2038417 · Cited by 510
NEXT: 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
First-order methods of smooth convex optimization with inexact oracle
Devolder, O., Glineur, F., & Nesterov, Y. (2014) · Mathematical Programming · doi:10.1007/s10107-013-0677-5 · Cited by 422
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
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
Nedić, A., & Olshevsky, A. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2529285 · Cited by 181
Consensus-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
Distributed multi-agent optimization with state-dependent communication
Lobel, I., Ozdaglar, A., & Feijer, D. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0467-x · Cited by 162 · cited 1×
“Extensions of these work have been proposed that deal with various realistic conditions, such as stochastic subgradient errors [10], directed or random communication graphs [11]–[13], linear scaling in network size [14], and heterogeneous local constraints [15], [16].”
BackgroundGeometrically 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
Matei, I., & Baras, J. S. (2011) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2011.2120593 · Cited by 133
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
Generating random regular graphs
Kim, J. H., & Vu, V. H. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780576 · Cited by 98
Harnessing smoothness to accelerate distributed optimization
Qu, G., & Li, N. (2016) · 2016 IEEE 55th Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798263 · Cited by 72
Self-citationCommunication complexity of convex optimization
Tsitsiklis, J. N., & Luo, Z.-Q. T. (1987) · Journal of Complexity · doi:10.1016/0885-064x(87)90013-6 · Cited by 52
Convergence analysis of distributed subgradient methods over random networks
Lobel, I., & Ozdaglar, A. (2008) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2008.4797579 · Cited by 46
Distributed nonconvex optimization over networks
Lorenzo, P. D., & Scutari, G. (2015) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camsap.2015.7383778 · Cited by 40
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2014) · arXiv · doi:10.48550/arxiv.1406.2075 · Cited by 38
Achieving Geometric Convergence for Distributed Optimization over Time-Varying GraphsPreprint
Nedić, A., Olshevsky, A., & Shi, W. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1607.03218 · Cited by 31
Accelerated Distributed Nesterov Gradient Descent for smooth and strongly convex functions
Qu, G., & Li, N. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852231 · Cited by 28
Self-citation
Cited by
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms
Zhang, K., Yang, Z., & Başar, T. (2021) · Studies in Systems, Decision and Control · doi:10.1007/978-3-030-60990-0_12 · Cited by 1,264
A 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
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
Distributed stochastic gradient tracking methods
Pu, S., & Nedić, A. (2021) · Mathematical Programming · doi:10.1007/s10107-020-01487-0 · Cited by 266
Xin, R., Kar, S., & Khan, U. A. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2974267 · Cited by 114
Metadata
- Authors
- Qu, G., & Li, N.
- Venue
- IEEE Transactions on Control of Network Systems
- Published
- 2018-09
- Volume
- 5
- Issue
- 3
- Pages
- 1245-1260
- ISSN
- 2325-5870 (ISSN-L)
- 2372-2533
- OpenAlex
- W2763533254
- Cited by
- 565
- References
- 32
- FWCI
- 22.93
- 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.