A Stochastic Approximation Method
Open accessAbstract
Let $M(x)$ denote the expected value at level $x$ of the response to a certain experiment. $M(x)$ is assumed to be a monotone function of $x$ but is unknown to the experimenter, and it is desired to find the solution $x = \theta$ of the equation $M(x) = \alpha$, where $\alpha$ is a given constant. We give a method for making successive experiments at levels $x_1,x_2,\cdots$ in such a way that $x_n$ will tend to $\theta$ in probability.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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?
The stochastic approximation term should scale as the convergence rate of stochastic first order methods, lower-bounded by 1/D^{1/2}.
“the third term should scale as the convergence rate of these methods, which is lower-bounded by 1 𝐷 1 2 (Robbins and Monro, 1951) (and may attain the bound).”
From Training Compute-Optimal Large Language Models (2022) · cites this paper as Robbins and Monro, 1951
The Summary (p. 1) and Convergence theorems (pp. 2–5) establish convergence of a stochastic approximation procedure, but the readable passages do not give a 1/√D lower bound for the convergence rate of stochastic first-order methods. I searched for the rate, lower bound, and efficiency; several formulas in our copy are undecoded, so the claimed bound cannot be verified from it. (LLM, conf=0.72)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cited by
Sorted by citations
Kohonen, T. (1990) · Proceedings of the IEEE · doi:10.1109/5.58325 · Cited by 8,414 · see citing works
ADADELTA: An Adaptive Learning Rate Method
Zeiler, M. D. (2012) · arXiv · doi:10.48550/arxiv.1212.5701 · Cited by 5,322 · see citing works
Knowledge Graph Embedding: A Survey of Approaches and Applications
Wang, Q., Mao, Z., Wang, B., & Guo, L. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2754499 · Cited by 2,654 · see citing works
Practical Recommendations for Gradient-Based Training of Deep Architectures
Bengio, Y. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-35289-8_26 · Cited by 2,259 · see citing works
Deformable medical image registration: a survey
Sotiras, A., Davatzikos, C., & Paragios, N. (2013) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2013.2265603 · Cited by 1,587 · see citing works
Recent advances in deep learning for object detection
Wu, X., Sahoo, D., & Hoi, S. C. H. (2020) · Neurocomputing · doi:10.1016/j.neucom.2020.01.085 · Cited by 1,047 · see citing works
Bordes, A., Glorot, X., Weston, J., & Bengio, Y. (2014) · Machine Learning · doi:10.1007/s10994-013-5363-6 · Cited by 675 · see citing works
DeepPoseKit, a software toolkit for fast and robust animal pose estimation using deep learning
Graving, J. M., Chae, D., Naik, H., Li, L., Koger, B., Costelloe, B. R., & Couzin, I. D. (2019) · eLife · doi:10.7554/elife.47994 · Cited by 547 · see citing works
Stochastic Gradient Descent on Riemannian Manifolds
Bonnabel, S. (2013) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2013.2254619 · Cited by 540 · see citing works
Automatic differentiation variational inference
Kucukelbir, A., Tran, D., Ranganath, R., Gelman, A., & Blei, D. M. (2016) · arXiv · doi:10.48550/arxiv.1603.00788 · Cited by 515 · see citing works
Ganju, K., Wang, Q., Yang, W., Gunter, C. A., & Borisov, N. (2018) · Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3243734.3243834 · Cited by 475 · see citing works
An optimal method for stochastic composite optimization
Lan, G. (2012) · Mathematical Programming · doi:10.1007/s10107-010-0434-y · Cited by 427 · see citing works
Fast iterative alignment of pose graphs with poor initial estimates
Olson, E., Leonard, J., & Teller, S. (2006) · Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006. · doi:10.1109/robot.2006.1642040 · Cited by 427 · see citing works
Value iteration and adaptive dynamic programming for data-driven adaptive optimal control design
Bian, T., & Jiang, Z.-P. (2016) · Automatica · doi:10.1016/j.automatica.2016.05.003 · Cited by 348 · see citing works
Non-stationary stochastic optimization
Besbes, O., Gur, Y., & Zeevi, A. (2015) · Operations Research · doi:10.1287/opre.2015.1408 · Cited by 337 · see citing works
Model inversion attacks against collaborative inference
He, Z., Zhang, T., & Lee, R. B. (2019) · Proceedings of the 35th Annual Computer Security Applications Conference · doi:10.1145/3359789.3359824 · Cited by 313 · see citing works
Grounding cognitive control in associative learning
Abrahamse, E., Braem, S., Notebaert, W., & Verguts, T. (2016) · Psychological Bulletin · doi:10.1037/bul0000047 · Cited by 276 · see citing works
Qsparse-local-SGD: Distributed SGD with quantization, sparsification, and local computations
Basu, D., Data, D., Karakus, C., & Diggavi, S. N. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.2985917 · Cited by 256 · see citing works
The dopaminergic midbrain encodes the expected certainty about desired outcomes
Schwartenbeck, P., FitzGerald, T. H. B., Mathys, C., Dolan, R., & Friston, K. (2015) · Cerebral Cortex · doi:10.1093/cercor/bhu159 · Cited by 219 · see citing works
Papadimitroulas, P., Brocki, L., Christopher Chung, N., Marchadour, W., Vermet, F., Gaubert, L., Eleftheriadis, V., Plachouris, D., Visvikis, D., Kagadis, G. C., et al. (2021) · Physica Medica · doi:10.1016/j.ejmp.2021.03.009 · Cited by 226 · see citing works
Privacy Risks of General-Purpose Language Models
Pan, X., Zhang, M., Ji, S., & Yang, M. (2020) · 2020 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp40000.2020.00095 · Cited by 188 · see citing works
Training Compute-Optimal Large Language Models
Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E., Casas, D. D. L., Hendricks, L. A., Welbl, J., Clark, A., et al. (2022) · Advances in Neural Information Processing Systems 35 · doi:10.52202/068431-2176 · Cited by 932 · see citing works
“Finally, given that it corresponds to early stopping in stochastic first order methods, the third term should scale as the convergence rate of these methods, which is lower-bounded by 1 𝐷 1 / 2 (Robbins and Monro, 1951) (and may attain the bound).”
A Reinforcement Learning Model to Assess Market Power Under Auction-Based Energy Pricing
Nanduri, V., & Das, T. K. (2007) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2006.888977 · Cited by 168 · see citing works
A Survey on an Emerging Area: Deep Learning for Smart City Data
Chen, Q., Wang, W., Wu, F., De, S., Wang, R., Zhang, B., & Huang, X. (2019) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2019.2907718 · Cited by 167 · see citing works
An analog VLSI recurrent neural network learning a continuous-time trajectory
Cauwenberghs, G. (1996) · IEEE Transactions on Neural Networks · doi:10.1109/72.485671 · Cited by 127 · see citing works
Stochastic collapsed variational Bayesian inference for latent Dirichlet allocation
Foulds, J., Boyles, L., DuBois, C., Smyth, P., & Welling, M. (2013) · Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2487575.2487697 · Cited by 126 · see citing works
Personalized Transformer for Explainable Recommendation
Li, L., Zhang, Y., & Chen, L. (2021) · Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers) · doi:10.18653/v1/2021.acl-long.383 · Cited by 124 · see citing works
Flexible mobility on-demand: an environmental scan
Liyanage, S., Dia, H., Abduljabbar, R., & Bagloee, S. (2019) · Sustainability · doi:10.3390/su11051262 · Cited by 111 · see citing works
The Shape Boltzmann Machine: A strong model of object shape
Eslami, S. M. A., Heess, N., & Winn, J. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247702 · Cited by 61 · see citing works
Learning to denoise astronomical images with U-nets
Vojtekova, A., Lieu, M., Valtchanov, I., Altieri, B., Old, L., Chen, Q., & Hroch, F. (2021) · Monthly Notices of the Royal Astronomical Society · doi:10.1093/mnras/staa3567 · Cited by 63 · see citing works
Taming unbalanced training workloads in deep learning with partial collective operations
Li, S., Ben-Nun, T., Girolamo, S. D., Alistarh, D., & Hoefler, T. (2020) · Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/3332466.3374528 · Cited by 57 · see citing works
Very Deep Convolutional Neural Networks for Morphologic Classification of Erythrocytes
Durant, T. J. S., Olson, E. M., Schulz, W. L., & Torres, R. (2017) · Clinical Chemistry · doi:10.1373/clinchem.2017.276345 · Cited by 49 · see citing works
Chu, Y., & Hahn, J. (2008) · AIChE Journal · doi:10.1002/aic.11562 · Cited by 41 · see citing works
Yang, J., Wang, L., Phadke, N. A., Wickner, P. G., Mancini, C. M., Blumenthal, K. G., & Zhou, L. (2020) · JAMA Network Open · doi:10.1001/jamanetworkopen.2020.22836 · Cited by 42 · see citing works
Learning Weight Uncertainty with Stochastic Gradient MCMC for Shape Classification
Li, C., Stevens, A., Chen, C., Pu, Y., Gan, Z., & Carin, L. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.611 · Cited by 39 · see citing works
Slow and Stale Gradients Can Win the Race
Dutta, S., Wang, J., & Joshi, G. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3103770 · Cited by 40 · see citing works
Domingos, L. C. F., Santos, P. E., Skelton, P. S. M., Brinkworth, R. S. A., & Sammut, K. (2022) · IEEE Access · doi:10.1109/access.2022.3220265 · Cited by 37 · see citing works
Online Non-Negative Convolutive Pattern Learning for Speech Signals
Wang, D., Vipperla, R., Evans, N., & Zheng, T. F. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2222381 · Cited by 25 · see citing works
TextGrad: Automatic "Differentiation" via Text
Yuksekgonul, M., Bianchi, F., Boen, J., Liu, S., Huang, Z., Guestrin, C., & Zou, J. (2024) · arXiv · doi:10.48550/arxiv.2406.07496 · Cited by 12 · see citing works
aSGD: Stochastic Gradient Descent with Adaptive Batch Size for Every Parameter
Shi, H., Yang, N., Tang, H., & Yang, X. (2022) · Mathematics · doi:10.3390/math10060863 · Cited by 11 · see citing works
Considering Race a Problem of Transfer Learning
Khan, A., & Mahmoud, M. (2019) · 2019 IEEE Winter Applications of Computer Vision Workshops (WACVW) · doi:10.1109/wacvw.2019.00022 · Cited by 12 · see citing works
Incorporating Gradients to Rules: Toward Online, Adaptive Provenance-Based Intrusion Detection
Li, Z., Wang, L., Wang, Z., Shen, X., Xu, H., Chen, Y., & Ji, S. (2026) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2025.3611461 · Cited by 2 · see citing works
A Simple and Interactive Transformer for Fine-Grained Emotion Detection
Sui, D., Li, B., Yang, H., Chen, Y., Liu, K., Chu, D., & Zhao, J. (2025) · IEEE Transactions on Audio, Speech and Language Processing · doi:10.1109/taslp.2024.3487418 · Cited by 2 · see citing works
- Authors
- Robbins, H., & Monro, S.
- Venue
- The Annals of Mathematical Statistics
- Publisher
- Institute of Mathematical Statistics
- Published
- 1951-09
- Volume
- 22
- Issue
- 3
- Pages
- 400-407
- ISSN
- 0003-4851 (ISSN-L)
- OpenAlex
- W1994616650
- Cited by
- 9,643
- References
- 0
- Citations by year
- 2026: 474 · 2025: 650 · 2024: 726 · 2023: 726 · 2022: 644 · 2021: 859 · 2020: 821 · 2019: 683 · 2018: 407 · 2017: 259 · 2016: 279 · 2015: 262 · 2014: 272 · 2013: 191 · 2012: 195
- FWCI
- 8.44
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- The Annals of Mathematical Statistics (publishedVersion)
- Project Euclid (Cornell University) (submittedVersion)
- Topics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Simulation Techniques and Applications
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Social Sciences › Decision Sciences › Management Science and Operations Research › Optimal Experimental Design Methods
- Keywords
- stochastic approximation, root finding, monotone functions, expected value, sequential experiments, convergence in probability, optimal experiment design
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
