Harnessing smoothness to accelerate distributed optimization
The DOI matches its Crossref record; 36 of the 37 references it cites were found in a registry or an index.
Abstract
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. Literature has developed consensus-based distributed (sub)gradient descent (DGD) methods and has shown that they have the same convergence rate O(log t/√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(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
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
“However, none of the papers mentioned in this paragraph provide a theoretical analysis for strongly convex optimization problems over time-varying graphs , which is the goal of this paper.”
From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [52]
In the citing paper
“Finally, we note that reference [52], appearing simultaneously with this work, also proposed a method for distributed optimization based on gradient differences.”
From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [52]
Citations
Cites
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
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 [23], [24].”
BackgroundErdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
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 4×
“, [6], [8]–[13], [16]– [18], [20], [21], that combine a consensus algorithm and a first order optimization algorithm.”
BackgroundMethodInfluentialMatrix Analysis and Applied Linear Algebra
Meyer, C. (2000) · doi:10.1137/1.9780898719512 · Cited by 3,565
Introductory Lectures on Convex Optimization: A Basic Course
Nesterov, Y. E. (2014) · Medical Entomology and Zoology · Cited by 3,557
Matrix analysis and applied linear algebra
(2001) · Choice Reviews Online · doi:10.5860/choice.38-5065 · Cited by 3,300
Parlar, M. (2000) · Interactive Operations Research with Maple · doi:10.1007/978-1-4612-1356-7_5 · Cited by 1,741
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
Convex Optimization: Algorithms and Complexity
Bubeck, S. (2015) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000050 · Cited by 1,001
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
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2010) · Cited by 884
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 [9], directed or random communication graph [10]–[12], linear scaling in network size [13], heterogeneous local constraints [14], [15].”
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
On the Convergence of Decentralized Gradient Descent
Yuan, K., Ling, Q., & Yin, W. (2016) · SIAM Journal on Optimization · doi:10.1137/130943170 · Cited by 633
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
Consensus-based distributed support vector machines
Forero, P. A., Caño, A., & Giannakis, G. B. (2010) · Cited by 364
1Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed GraphsPreprint
Nedić, A., & Olshevsky, A. (2016) · Cited by 316
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 [9], directed or random communication graph [10]–[12], linear scaling in network size [13], heterogeneous local constraints [14], [15].”
BackgroundA fast distributed proximal-gradient method
Chen, A. I., & Ozdaglar, A. (2012) · 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2012.6483273 · Cited by 154
Matei, I., & Baras, J. S. (2011) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2011.2120593 · Cited by 133
On Distributed Optimization in Networked Systems
Johansson, B. (2008) · KTH Publication Database DiVA (KTH Royal Institute of Technology) · Cited by 114
Olshevsky, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.4186 · Cited by 92
Distributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms
Tsitsiklis, J. N., Bertsekas, D. P., & Athans, M. (1984) · 1984 American Control Conference · doi:10.23919/acc.1984.4788427 · Cited by 77
Communication complexity of convex optimization
Tsitsiklis, J. N., & Luo, Z.-Q. (1987) · Journal of Complexity · doi:10.1016/0885-064x(87)90013-6 · Cited by 51
Fast Distributed First-Order Methods
Chen, A. I.-A. (2012) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 49
Convergence analysis of distributed subgradient methods over random networks
Lobel, I., & Ozdaglar, A. (2008) · 2008 46th Annual Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2008.4797579 · Cited by 44
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
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
Research works printed but not linked: 1
- 2012, Logistic Regression
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
“Finally, we note that reference [52], appearing simultaneously with this work, also proposed a method for distributed optimization based on gradient differences.”
MethodHarnessing 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
Self-citationNetwork 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
Li, Z., Shi, W., & Yan, M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2926022 · Cited by 244
A 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
Metadata
- Authors
- Qu, G., & Li, N.
- Affiliations
- Harvard University (US)
- ORCID
- Venue
- 2016 IEEE 55th Conference on Decision and Control (CDC)
- Publisher
- IEEE
- Published
- 2016-12
- Pages
- 159-166
- ISSN
- 0191-2216 (ISSN-L)
- OpenAlex
- W2400034325
- Cited by
- 72
- References
- 37
- Citations by year
- 2025: 4 · 2024: 5 · 2023: 4 · 2022: 7 · 2021: 3 · 2020: 5 · 2019: 10 · 2018: 22 · 2017: 9 · 2016: 3
- FWCI
- 12.53
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE Conference on Decision and Control (CDC) (publishedVersion)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Keywords
- distributed optimization, smoothness, linear convergence, strongly convex functions, gradient estimation, history information, convergence rate, nonsmooth optimization, communication complexity
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.