The DOI matches its Crossref record; 45 of the 45 references it cites were found in a registry or an index.
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization
Open accessAbstract
We consider a distributed multi-agent network system where the goal is to minimize a sum of convex objective functions of the agents subject to a common convex constraint set. Each agent maintains an iterate sequence and communicates the iterates to its neighbors. Then, each agent combines weighted averages of the received iterates with its own iterate, and adjusts the iterate by using subgradient information (known with stochastic errors) of its own function and by projecting onto the constraint set.The goal of this paper is to explore the effects of stochastic subgradient errors on the convergence of the algorithm. We first consider the behavior of the algorithm in mean, and then the convergence with probability 1 and in mean square. We consider general stochastic errors that have uniformly bounded second moments and obtain bounds on the limiting performance of the algorithm in mean for diminishing and non-diminishing stepsizes. When the means of the errors diminish, we prove that there is mean consensus between the agents and mean convergence to the optimum function value for diminishing stepsizes. When the mean errors diminish sufficiently fast, we strengthen the results to consensus and convergence of the iterates to an optimal solution with probability 1 and in mean square.
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
“Specifically, it is standard for a distributed subgradient method to converge at the rate of O (ln t/ √ t ) with the constant depending on the subgradient-norm upper bounds L i and the initial conditions x i (0) [25], [5].”
From Distributed Optimization Over Time-Varying Directed Graphs (2015) · cites this paper as [25]
In the citing paper
“Finally, we note that previous research [18], [25], [5] has studied the case when the matrices A ( t ) in (3) are doubly stochastic, which occurs when the directed graph sequence { G ( t ) } is regular. In this case, our polynomial bounds match the previously known results.”
From Distributed Optimization Over Time-Varying Directed Graphs (2015) · cites this paper as [25]
Citations
Cites
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Coordination of groups of mobile autonomous agents using nearest neighbor rules
Jadbabaie, A., Lin, J., & Morse, A. S. (2003) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2003.812781 · Cited by 8,339
PE, & Billingsley, P. (1996) · Journal of the American Statistical Association · doi:10.2307/2291440 · Cited by 6,481
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×
“In the distributed subgradient algorithms of [19, 20], each agent maintains an iterate sequence and communicates the iterates to its neighbors.”
BackgroundMethodInfluentialSelf-citationConvex Analysis and Optimization
Bertsekas, D. P., Nedić, A., & Ozdaglar, A. (2003) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 2,148
Self-citationConstrained 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
Self-citationDistributed 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
(1989) · Choice Reviews Online · doi:10.5860/choice.26-5109 · Cited by 1,755
Hawkes, J., & Billingsley, P. (1987) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2982048 · Cited by 1,631
PROBLEMS IN DECENTRALIZED DECISION MAKING AND COMPUTATION
Τσιτσικλής, Ι. (2014) · doi:10.12681/eadd/3778 · Cited by 1,278
Distributed average consensus with least-mean-square deviation
Xiao, L., Boyd, S., & Kim, S.-J. (2007) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2006.08.010 · Cited by 1,107
Distributed optimization in sensor networks
Rabbat, M., & Nowak, R. (2004) · Proceedings of the 3rd international symposium on Information processing in sensor networks · doi:10.1145/984622.984626 · Cited by 901 · cited 1×
“A number of problems that arise in the context of peer to peer networks can be posed as the constrained minimization of a sum of convex functions, where each component function is known only to one agent in the network [1–13].”
BackgroundHandbook of applied optimization
(2002) · Choice Reviews Online · doi:10.5860/choice.40-1593 · Cited by 867 · cited 1×
“A number of problems that arise in the context of peer to peer networks can be posed as the constrained minimization of a sum of convex functions, where each component function is known only to one agent in the network [1–13].”
BackgroundConvergence 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 · cited 1×
“The work in this paper is also related at a much broader level to the distributed consensus algorithms [7, 20–29].”
ResultKar, S., & Moura, J. M. F. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.2007111 · Cited by 691
Numerical Techniques for Stochastic Optimization
(1988) · Springer Series in Computational Mathematics · doi:10.1007/978-3-642-61370-8 · Cited by 632
Incremental Subgradient Methods for Nondifferentiable Optimization
Nedic, A., & Bertsekas, D. P. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623499362111 · Cited by 589
Self-citationConvex Optimization in Signal Processing and Communications
(2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511804458 · Cited by 554
Gradient Convergence in Gradient methods with Errors
Bertsekas, D. P., & Tsitsiklis, J. N. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497331063 · Cited by 437 · cited 2×
“In an incremental algorithm, there is a single iterate sequence and only one agent updates the iterate at a given time.”
MethodHandbook of Global Optimization
(2002) · Nonconvex Optimization and Its Applications · doi:10.1007/978-1-4757-5362-2 · Cited by 412
Quantized incremental algorithms for distributed optimization
Rabbat, M. G., & Nowak, R. D. (2005) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2005.843546 · Cited by 408
A Convergent Incremental Gradient Method with a Constant Step Size
Blatt, D., Hero, A. O., & Gauchman, H. (2007) · SIAM Journal on Optimization · doi:10.1137/040615961 · Cited by 306
stochastic quasigradient methods and their application to system optimization†
Ermoliev, Y. (1983) · Stochastics · doi:10.1080/17442508308833246 · Cited by 280
Incremental Stochastic Subgradient Algorithms for Convex Optimization
Ram, S. S., Nedić, A., & Veeravalli, V. V. (2009) · SIAM Journal on Optimization · doi:10.1137/080726380 · Cited by 239 · cited 10×
“The effects of stochastic errors on these algorithms have been investigated in [3,9,14,17,23,24,27].”
BackgroundMethodResultInfluentialSelf-citationConvergence Rate of Incremental Subgradient Algorithms
Nedić, A., & Bertsekas, D. (2001) · Applied Optimization · doi:10.1007/978-1-4757-6594-6_11 · Cited by 190
Self-citationApproximate distributed Kalman filtering in sensor networks with quantifiable performance
Spanos, D. P., Olfati‐Saber, R., & Murray, R. M. (2005) · doi:10.5555/1147685.1147711 · Cited by 190
Cooperative distributed multi-agent optimization
Nedić, A., & Ozdaglar, A. (2009) · Convex Optimization in Signal Processing and Communications · doi:10.1017/cbo9780511804458.011 · Cited by 185
Self-citationDistributed subgradient methods and quantization effects
Nedic, A., Olshevsky, A., Ozdaglar, A., & Tsitsiklis, J. N. (2008) · 2008 47th IEEE Conference on Decision and Control · doi:10.1109/cdc.2008.4738860 · Cited by 185
Self-citationConvergence of Approximate and Incremental Subgradient Methods for Convex Optimization
Kiwiel, K. C. (2004) · SIAM Journal on Optimization · doi:10.1137/s1052623400376366 · Cited by 182
Stochastic Programming Methods
Ermoliev, Y. M. (1976) · IIASA PURE (International Institute of Applied Systems Analysis) · Cited by 147
Approximate distributed kalman filtering in sensor networks with quantifiable performance
Spanos, D. P., Olfati‐Saber, R., & Murray, R. M. (2005) · ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN) · doi:10.1109/ipsn.2005.1440912 · Cited by 145 · cited 1×
“The work in this paper is also related at a much broader level to the distributed consensus algorithms [7, 20–29].”
ResultRao, R. V. (2015) · Springer eBooks · doi:10.1007/978-3-319-22732-0_1 · Cited by 101
Distributed Non-Autonomous Power Control through Distributed Convex Optimization
Ram, S. S., Veeravalli, V. V., & Nedic, A. (2009) · IEEE INFOCOM 2009 · doi:10.1109/infcom.2009.5062275 · Cited by 99 · cited 2×
“We refer the reader to [24, 25] for wireless network applications that can be cast in this framework.”
BackgroundSelf-citationOn Distributed Optimization in Networked Systems
Johansson, B. (2008) · Cited by 97
A simple peer-to-peer algorithm for distributed optimization in sensor networks
Johansson, B., Rabi, M., & Johansson, M. (2007) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2007.4434888 · Cited by 97
On the rate of convergence of distributed subgradient methods for multi-agent optimization
Nedić, A. (2007) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2007.4434693 · Cited by 89
Self-citationError Stability Properties of Generalized Gradient-Type Algorithms
Solodov, M. V., & Завриев, С. К. (1998) · Journal of Optimization Theory and Applications · doi:10.1023/a:1022680114518 · Cited by 88
Stochastic approximation for consensus seeking: Mean square and almost sure convergence
Huang, M., & Manton, J. H. (2007) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2007.4434630 · Cited by 79 · cited 1×
“The effect of random errors on consensus algorithms have been investigated in [10, 13, 15, 33].”
BackgroundGaivoronski, A. A. (1994) · Optimization methods & software · doi:10.1080/10556789408805582 · Cited by 78 · cited 1×
“The eects of stochastic errors on these algorithms have been investigated in [3, 9 , 14, 17,23,24,27].”
MethodThe effect of deterministic noise in subgradient methods
Nedić, A., & Bertsekas, D. P. (2009) · Mathematical Programming · doi:10.1007/s10107-008-0262-5 · Cited by 68
Self-citationStochastic Incremental Gradient Descent for Estimation in Sensor Networks
Ram, S. S., Nedić, A., & Veeravalli, V. V. (2007) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2007.4487280 · Cited by 66
Self-citationConvergence 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
Varatkar, G. V., Narayanan, S., Shanbhag, N. R., & Jones, D. L. (2007) · International Symposium on System-on-Chip · doi:10.1109/issoc.2007.4427447 · Cited by 25 · cited 1×
“[34]. In a distributed network on a single chip, for the chip to be fault tolerant, it is desirable to perform the processing in a distributed manner to account for the statistical process variations [32]. We consider constrained minimization of a sum of convex functions, where each component function is known partial…”
BackgroundConvergence Speed in Distributed Consensus and ControlPreprint
Olshevsky, A., & Tsitsiklis, J. N. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0612682 · Cited by 9
Cited by
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
“1) has additional constraints that force x into a bounded set, which also leads to bounded (sub)gradients and a Hessian, projected first-order algorithms are applicable [27, 37].”
BackgroundDistributed 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
“Specifically, it is standard for a distributed subgradient method to converge at the rate of O(ln t/ √ t) with the constant depending on the subgradientnorm upper bounds Li and the initial conditions xi(0) [5], [24].”
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
“To handle a more general (possibly time-varying) networks, distributed subgradient algorithm was proposed in [47], while its stochastic variant was studied in [56] and its asynchronous variant in [36] with provable convergence rates.”
BackgroundSelf-citationDual 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
“Our final set of experiments compares the distributed dual averaging method (DDA) that we present to the Markov incremental gradient descent (MIGD) method [11] and the distributed projected gradient method [10].”
InfluentialLian, X., Zhang, C., Zhang, H., Hsieh, C., Zhang, W., & Liu, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.09056 · Cited by 395
“…and Nedic, 2011, Sundhar Ram et al., 2010] or implicitly indicate that decentralized algorithms were much worse than centralized algorithms in terms of computational complexity and total communication complexity [Aybat et al., 2015, Lan et al., 2017, Ram et al., 2010, Zhang and Kwok, 2014].”
BackgroundMethodInfluential
Metadata
- Authors
- Sundhar Ram, S., Nedić, A., & Veeravalli, V. V.
- Affiliations
- University of Illinois Urbana-Champaign (US)
- Corresponding author
- Nedić, A.
- ORCID
- Veeravalli, V. V.
- Venue
- Journal of Optimization Theory and Applications
- Published
- 2010-07-22
- Volume
- 147
- Issue
- 3
- Pages
- 516-545
- ISSN
- 0022-3239 (ISSN-L)
- 1573-2878
- OpenAlex
- W2066332749
- Cited by
- 814
- References
- 45
- Citations by year
- 2026: 17 · 2025: 43 · 2024: 55 · 2023: 43 · 2022: 48 · 2021: 54 · 2020: 78 · 2019: 64 · 2018: 74 · 2017: 58 · 2016: 60 · 2015: 57 · 2014: 42 · 2013: 44 · 2012: 35
- FWCI
- 51.94
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Journal of Optimization Theory and Applications (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- RePEc: Research Papers in Economics (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Keywords
- distributed optimization, multi-agent systems, projection onto convex sets, consensus, mean square convergence, almost sure convergence, convex optimization
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.