The DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Incremental Stochastic Subgradient Algorithms for Convex Optimization
Open accessAbstract
This paper studies the effect of stochastic errors on two constrained incremental subgradient algorithms. The incremental subgradient algorithms are viewed as decentralized network optimization algorithms as applied to minimize a sum of functions, when each component function is known only to a particular agent of a distributed network. First, the standard cyclic incremental subgradient algorithm is studied. In this, the agents form a ring structure and pass the iterate in a cycle. When there are stochastic errors in the subgradient evaluations, sufficient conditions on the moments of the stochastic errors are obtained that guarantee almost sure convergence when a diminishing step-size is used. In addition, almost sure bounds on the algorithm's performance with a constant step-size are also obtained. Next, the Markov randomized incremental subgradient method is studied. This is a noncyclic version of the incremental algorithm where the sequence of computing agents is modeled as a time nonhomogeneous Markov chain. Such a model is appropriate for mobile networks, as the network topology changes across time in these networks. Convergence results and error bounds for the Markov randomized method in the presence of stochastic errors for diminishing and constant step-sizes are obtained.
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
A Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643
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
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
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
On Distributed Averaging Algorithms and Quantization Effects
Nedic, A., Olshevsky, A., Ozdaglar, A., & Tsitsiklis, J. N. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2009.2031203 · Cited by 557
Cited by
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
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
“Some earlier methods include distributed incremental (sub)gradient methods [37–39, 54 ] and incremental incremental proximal methods [ 3 , 68] , while a more recent Some distributed methods exist that do not (explicitly) use dual variables but can still converge to an exact consensual solution…”
MethodSelf-citationDistributed 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
“The effects of stochastic errors on these algorithms have been investigated in [3,9,14,17,23,24,27].”
BackgroundMethodResultInfluentialSelf-citationZero-Gradient-Sum Algorithms for Distributed Convex Optimization: The Continuous-Time Case
Lu, J., & Tang, C. Y. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2012.2184199 · Cited by 403
Distributed Alternating Direction Method of Multipliers
Wei, E., & Ozdaglar, A. (2012) · 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6425904 · Cited by 389
Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey
Bertsekas, D. P. (2011) · Optimization for Machine Learning · doi:10.7551/mitpress/8996.003.0006 · Cited by 381
Distributed Continuous-Time Convex Optimization With Time-Varying Cost Functions
Rahili, S., & Ren, W. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2593899 · Cited by 343
Asynchronous Broadcast-Based Convex Optimization Over a Network
Nedic, A. (2011) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2079650 · Cited by 310
Incremental proximal methods for large scale convex optimization
Bertsekas, D. P. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0472-0 · Cited by 303
Reaching an Optimal Consensus: Dynamical Systems That Compute Intersections of Convex Sets
Shi, G., Johansson, K. H., & Hong, Y. (2013) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2012.2215261 · Cited by 288
On Analog Gradient Descent Learning Over Multiple Access Fading Channels
Sery, T., & Cohen, K. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2989580 · 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
“One strand focuses on reaching consensus on a particular scalar value or computing exact averages of the initial values of the agents, as natural models of cooperative behavior in networked-systems (for deterministic models, see [28], [14],[20], [9], [21], and [22]; for randomized models, where the randomness may be d…”
BackgroundA new class of distributed optimization algorithms: Application to regression of distributed data
Sundhar Ram, S., Nedić, A., & Veeravalli, V. V. (2012) · Optimization Methods and Software · doi:10.1080/10556788.2010.511669 · Cited by 123
Self-citationDistributed 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
Self-citationLü, Q., & Li, H. (2016) · arXiv · doi:10.48550/arxiv.1611.00990 · Cited by 54
Metadata
- Authors
- Ram, S. S., Nedić, A., & Veeravalli, V. V.
- Venue
- SIAM Journal on Optimization
- Published
- 2009-01
- Volume
- 20
- Issue
- 2
- Pages
- 691-717
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W1973754217
- Cited by
- 239
- References
- 5
- FWCI
- 26.57
- 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.