The DOI matches its Crossref record; 53 of the 53 references it cites were found in a registry or an index.
Distributed stochastic gradient tracking methods
Open accessAbstract
In this paper, we study the problem of distributed multi-agent optimization over a network, where each agent possesses a local cost function that is smooth and strongly convex. The global objective is to find a common solution that minimizes the average of all cost functions. Assuming agents only have access to unbiased estimates of the gradients of their local cost functions, we consider a distributed stochastic gradient tracking method (DSGT) and a gossip-like stochastic gradient tracking method (GSGT). We show that, in expectation, the iterates generated by each agent are attracted to a neighborhood of the optimal solution, where they accumulate exponentially fast (under a constant stepsize choice). Under DSGT, the limiting (expected) error bounds on the distance of the iterates from the optimal solution decrease with the network size n, which is a comparable performance to a centralized stochastic gradient algorithm. Moreover, we show that when the network is well-connected, GSGT incurs lower communication cost than DSGT while maintaining a similar computational cost. Numerical example further demonstrates the effectiveness of the proposed methods.
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
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
A Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643
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
Boyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874516 · Cited by 2,439
Stochastic Estimation of the Maximum of a Regression Function
Kiefer, J., & Wolfowitz, J. (1952) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729392 · Cited by 2,133
Constrained Consensus and Optimization in Multi-Agent Networks
Nedic, A., Ozdaglar, A., & Parrilo, P. A. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2041686 · Cited by 2,086
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
Robust Stochastic Approximation Approach to Stochastic Programming
Nemirovski, A., Juditsky, A., Lan, G., & Shapiro, A. (2009) · SIAM Journal on Optimization · doi:10.1137/070704277 · Cited by 1,945
Stochastic Approximation and Recursive Algorithms and Applications
(2003) · Stochastic Modelling and Applied Probability · doi:10.1007/b97441 · Cited by 1,838
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
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-citationMulti-fidelity optimization via surrogate modelling
Forrester, A. I. J., Sóbester, A., & Keane, A. J. (2007) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2007.1900 · Cited by 1,018
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
Self-citationKia, S. S., Cortés, J., & Martínez, S. (2015) · Automatica · doi:10.1016/j.automatica.2015.03.001 · Cited by 694
Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
Chen, J., & Sayed, A. H. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2198470 · Cited by 680
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
Sayed, A. H. (2014) · Proceedings of the IEEE · doi:10.1109/jproc.2014.2306253 · Cited by 587
Harnessing 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
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
Rakhlin, A., Shamir, O., & Sridharan, K. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1109.5647 · Cited by 492
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
Lian, X., Zhang, C., Zhang, H., Hsieh, C., Zhang, W., & Liu, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.09056 · Cited by 395
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-citationDesign and Analysis of Simulation Experiments
Kleijnen, J. P. C. (2015) · International Series in Operations Research & Management Science · doi:10.1007/978-3-319-18087-8 · Cited by 355
Distributed Asynchronous Constrained Stochastic Optimization
Srivastava, K., & Nedic, A. (2011) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2011.2118740 · Cited by 350
Design and Analysis of Simulation Experiments
(2008) · International Series in Operations Research & Management Science · doi:10.1007/978-0-387-71813-2 · Cited by 317
1Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed GraphsPreprint
Nedić, A., & Olshevsky, A. (2016) · Cited by 315
Self-citationConvergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization
Bianchi, P., & Jakubowicz, J. (2013) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2012.2209984 · Cited by 245
On the second eigenvalue of random regular graphs
Friedman, J., Kahn, J., & Szemerédi, E. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73063 · Cited by 218
Fast Convergence Rates for Distributed Non-Bayesian Learning
Nedic, A., Olshevsky, A., & Uribe, C. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2690401 · Cited by 212
DLM: Decentralized Linearized Alternating Direction Method of Multipliers
Ling, Q., Shi, W., Wu, G., & Ribeiro, A. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2436358 · Cited by 196
Communication-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
Aybat, N. S., Wang, Z., Lin, T., & Ma, S. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2713046 · Cited by 172
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
On the Learning Behavior of Adaptive Networks—Part I: Transient Analysis
Chen, J., & Sayed, A. H. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2427360 · Cited by 143
An augmented Lagrangian method for distributed optimization
Chatzipanagiotis, N., Dentcheva, D., & Zavlanos, M. M. (2014) · Mathematical Programming · doi:10.1007/s10107-014-0808-7 · Cited by 131
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
Proximal-Gradient Algorithms for Tracking Cascades Over Social Networks
Baingana, B., Mateos, G., & Giannakis, G. B. (2014) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2014.2317284 · Cited by 103
Adaptive Penalty-Based Distributed Stochastic Convex Optimization
Towfic, Z. J., & Sayed, A. H. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2331615 · Cited by 98
Asynchronous 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
Self-citationOn the Learning Behavior of Adaptive Networks—Part II: Performance Analysis
Chen, J., & Sayed, A. H. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2427352 · Cited by 85
Convergence Rates for Distributed Stochastic Optimization Over Random Networks
Jakovetić, D., Bajović, D., Sahu, A. K., & Kar, S. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619228 · Cited by 71
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-citationStochastic Subgradient Algorithms for Strongly Convex Optimization Over Distributed Networks
Sayin, M. O., Vanli, N. D., Kozat, S. S., & Başar, T. (2017) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2017.2713396 · Cited by 57
Cavalcante, R. L. G., & Stańczak, S. (2013) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2013.2246766 · Cited by 54
Cohen, K., Nedić, A., & Srikant, R. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2705559 · Cited by 54
Self-citationDecentralized Consensus Algorithm with Delayed and Stochastic Gradients
Sirb, B., & Ye, X. (2018) · SIAM Journal on Optimization · doi:10.1137/16m1081257 · Cited by 52
A Distributed Algorithm for Convex Constrained Optimization Under Noise
Chatzipanagiotis, N., & Zavlanos, M. M. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2504932 · Cited by 37
A Flocking-Based Approach for Distributed Stochastic Optimization
Pu, S., & García, A. (2017) · Operations Research · doi:10.1287/opre.2017.1666 · Cited by 20
Self-citationSwarming 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
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-citation
Metadata
- Authors
- Pu, S., & Nedić, A.
- Venue
- Mathematical Programming
- Published
- 2020-03-17
- Volume
- 187
- Issue
- 1-2
- Pages
- 409-457
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W3011252985
- Cited by
- 266
- References
- 53
- FWCI
- 15.09
- 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.