{ "id": "ep7jfez6b9", "slug": "stochastic-approximation", "title": "Stochastic approximation", "updated": "2026-10-15", "topic_path": [ { "id": "physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical" }, { "id": "physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math" }, { "id": "physical.math.statistics", "label": "Statistics and probability", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.statistics" }, { "id": "physical.math.statistics.stats_statistical_inference", "label": "Statistical inference, estimation, sampling, and testing", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.statistics.stats_statistical_inference" } ], "geo": [ { "id": "geo.nongeo.t1946.physical.math.statistics.stats_statistical_inference", "label": "Non-geographic · 1946 to 2000: Statistical inference, estimation, sampling, and testing", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.statistics.stats_statistical_inference", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical" }, { "id": "geo.nongeo.t1946.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math" }, { "id": "geo.nongeo.t1946.physical.math.statistics", "label": "Statistics and probability", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.statistics" }, { "id": "geo.nongeo.t1946.physical.math.statistics.stats_statistical_inference", "label": "Statistical inference, estimation, sampling, and testing", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.statistics.stats_statistical_inference" } ] } ], "excerpt": "Stochastic approximation is a family of iterative algorithms that find the root of an unknown function from noisy observations, introduced by Robbins and Monro in 1951.", "snippet": "Stochastic approximation is a family of iterative algorithms that find the root of an unknown function from noisy observations, introduced by Robbins and Monro in 1951.", "node": "physical.math.statistics.stats_statistical_inference", "markdown": "# Stochastic approximation\n\nStochastic approximation is a family of iterative algorithms that estimate the root of an unknown function, or the optimum of an objective, from a sequence of noisy random observations. [Herbert Robbins](https://www.edgepedia.org/herbert-robbins) and Sutton Monro framed the root-finding version in 1951 as finding the solution \\( x = \\theta \\), where \\( M(x) \\) is an unknown mean response observable only with random error.[1](https://doi.org/10.1214/aoms/1177729586) Setting the target function to the gradient turns the recursion into stochastic gradient descent, the update behind a large share of modern machine learning training.[2](https://bactra.org/notebooks/stochastic-approximation.html) • [3](https://people.eecs.berkeley.edu/~brecht/opt4ml_book/O4MD_05_SGM.pdf)\n\n| Key fact | Detail |\n|---|---|\n| Problem solved | Root of an unknown regression function, or the maximum of one, from noisy observations[1](https://doi.org/10.1214/aoms/1177729586) • [4](https://doi.org/10.1214/aoms/1177729392) |\n| Core update | \\( x_{n+1} = x_n + a_n(Y_n(x_n) - \\alpha) \\)[5](https://encyclopediaofmath.org/wiki/Stochastic_approximation) |\n| Step-size conditions | \\( \\sum a_n = \\infty \\) and \\( \\sum a_n^2 < \\infty \\)[6](https://par.nsf.gov/servlets/purl/10304143) |\n| Convergence sense | With probability 1 and in quadratic mean, under monotonicity, linear growth, and independent errors[5](https://encyclopediaofmath.org/wiki/Stochastic_approximation) |\n| Optimal rate | \\( O(1/\\sqrt{k}) \\) is optimal for plain stochastic oracles; strong convexity yields \\( O(1/k) \\)[7](https://www.math.univ-toulouse.fr/~epauwels/M2RI/session6.pdf) |\n| SGD relation | Stochastic gradient descent is the special case \\( h = -\\nabla f \\)[8](https://www.math.univ-toulouse.fr/%7Egfort/Slides/IMSIMB24.pdf) |\n| Main proof tools | Non-negative supermartingale convergence and the ODE method[5](https://encyclopediaofmath.org/wiki/Stochastic_approximation) • [9](https://wires.onlinelibrary.wiley.com/doi/10.1002/wics.57) |\n\n## How it works\n\nThe Robbins–Monro recursion updates the current estimate with a noisy observation scaled by a small positive gain: \\( X_{n+1} = X_n + a_n(Y_n(X_n) - \\alpha) \\).[5](https://encyclopediaofmath.org/wiki/Stochastic_approximation) In the general form used in modern analyses, \\( X_{k+1} = X_k + \\alpha_k(h(X_k) + M_{k+1}) \\), where \\( h \\) is the mean field whose root is sought and \\( (M_k) \\) is a martingale-difference noise sequence with zero conditional mean and bounded conditional second moment.[7](https://www.math.univ-toulouse.fr/~epauwels/M2RI/session6.pdf) The two step-size conditions divide the work: \\( \\sum a_n^2 < \\infty \\) makes the accumulated noise converge in \\( L_2 \\) and almost surely, while \\( \\sum a_n = \\infty \\) ensures the bias vanishes.[6](https://par.nsf.gov/servlets/purl/10304143) Under these conditions, with \\( R(x) \\) increasing and growing at most linearly and independent errors, \\( X_n \\) converges to the root with probability 1 and in quadratic mean.[5](https://encyclopediaofmath.org/wiki/Stochastic_approximation) The 1951 proof itself established \\( \\mathbb{E}(x_n - \\theta)^2 \\to 0 \\), i.e., convergence in quadratic mean and hence in probability; Blum (1954) later used martingale theory to prove almost-sure convergence under weaker conditions.[1](https://doi.org/10.1214/aoms/1177729586) • [6](https://par.nsf.gov/servlets/purl/10304143) Normalized iterates are asymptotically Gaussian, with a least limit variance attained at a gain \\( a_0 = -[R'(x_0)]^{-1} \\) that is unattainable in practice because \\( R \\) is unknown; adaptive procedures approximate it.[5](https://encyclopediaofmath.org/wiki/Stochastic_approximation) Convergence is proved either through the theorem on convergence of non-negative [supermartingales](https://www.edgepedia.org/supermartingale) or, for general noise, through the ODE method, in which the interpolated algorithm tracks solutions of an ordinary differential equation.[5](https://encyclopediaofmath.org/wiki/Stochastic_approximation) • [9](https://wires.onlinelibrary.wiley.com/doi/10.1002/wics.57) The stochastic gradient method iterates \\( x_{k+1} = x_k - \\alpha_k g(x_k, \\xi_k) \\) with \\( \\mathbb{E}_{\\xi}[g(x, \\xi)] = \\nabla f(x) \\), an unbiased gradient estimate; Bottou, Curtis, and Nocedal attribute the approach to the 1951 Robbins–Monro work.[3](https://people.eecs.berkeley.edu/~brecht/opt4ml_book/O4MD_05_SGM.pdf) In SA terms it is exactly the case \\( h = -\\nabla f \\).[8](https://www.math.univ-toulouse.fr/%7Egfort/Slides/IMSIMB24.pdf) • [2](https://bactra.org/notebooks/stochastic-approximation.html) The limiting ODE is the gradient flow \\( \\dot{x}(t) = -\\nabla f(x(t)) \\), and iterates converge almost surely to the set of critical points, treating maxima and [saddle points](https://www.edgepedia.org/saddle-point) as unstable equilibria.[10](https://www.professeurs.polymtl.ca/jerome.le-ny/teaching/DP_fall09/notes/lec11_SA.pdf)\n\n## How it is done\n\nA practitioner chooses the mean field \\( h \\), a stochastic oracle returning \\( h(x) \\) plus noise, and a step-size schedule. For schedules of the form \\( \\gamma_n = C \\cdot n^{-\\alpha} \\), convergence in quadratic mean requires \\( \\alpha \\in (0,1) \\); at \\( \\alpha = 1 \\) convergence holds only when \\( C \\) is large enough, and \\( \\alpha > 1 \\) makes the steps too small for the error bound to vanish.[11](https://www.di.ens.fr/%7efbach/orsay2016/lecture3.pdf) With \\( \\gamma = C/n \\), asymptotic normality requires \\( 2C \\cdot \\lambda_{\\min}(A) > 1 \\), where \\( A \\) is the differential of \\( h \\) at the root; too small a \\( C \\) gives no convergence and too large a \\( C \\) gives large variance.[11](https://www.di.ens.fr/%7efbach/orsay2016/lecture3.pdf) Constant step sizes do not converge in the stochastic setting, so diminishing stepsizes or epoch schemes with reduction by a factor typically between 0.8 and 0.9 are used.[3](https://people.eecs.berkeley.edu/~brecht/opt4ml_book/O4MD_05_SGM.pdf) With \\( \\eta_t = \\eta_0/t \\), the RMSE around the true solution is proportional to \\( \\eta_0 \\) and can be made arbitrarily small.[2](https://bactra.org/notebooks/stochastic-approximation.html) Averaging the iterates is often added on top of a longer-step-size run. The original \\( \\alpha_k = 1/(k+1) \\) makes the iterate a running average of all samples.[3](https://people.eecs.berkeley.edu/~brecht/opt4ml_book/O4MD_05_SGM.pdf) For convex, Lipschitz objectives, \\( O(1/\\sqrt{k}) \\) rates are optimal for optimization with stochastic oracles; strong convexity yields \\( O(1/k) \\), and variance reduction gives linear rates for finite sums.[7](https://www.math.univ-toulouse.fr/~epauwels/M2RI/session6.pdf) Without strong convexity, plain SGD with \\( \\gamma_n = C \\cdot n^{-\\alpha} \\) reaches at best \\( O(n^{-1/3}) \\), short of the minimax \\( O(n^{-1/2}) \\), while Polyak–Ruppert averaging with \\( \\alpha > 1/2 \\) improves the rate to \\( O(n^{-\\alpha}) \\).[12](https://papers.nips.cc/paper/2011/file/40008b9a5380fcacce3976bf7c08af5b-Paper.pdf)\n\n## Origin\n\nThe method was reported by Herbert Robbins and Sutton Monro in \"A Stochastic Approximation Method,\" The Annals of Mathematical Statistics, 1951.[1](https://doi.org/10.1214/aoms/1177729586) J. Kiefer and J. Wolfowitz published the stochastic-optimum version, \"Stochastic Estimation of the Maximum of a Regression Function,\" in the same journal in 1952 (volume 23, issue 3, pages 462–466).[4](https://doi.org/10.1214/aoms/1177729392) Blum (1954) proved almost-sure convergence via martingales, and the early lineage also includes Wolfowitz (1952) and Dvoretzky (1956).[6](https://par.nsf.gov/servlets/purl/10304143) • [8](https://www.math.univ-toulouse.fr/%7Egfort/Slides/IMSIMB24.pdf) Ljung's 1977 paper \"Analysis of recursive stochastic algorithms\" introduced the ODE method for analyzing such recursions in IEEE Transactions on Automatic Control.[13](https://doi.org/10.1109/tac.1977.1101561) Later landmarks are Polyak and Juditsky's averaging paper (1992),[14](https://doi.org/10.1137/0330046) Kushner and Yang's optimal-rate extension (1993),[15](https://doi.org/10.1137/0331047) Borkar's two-time-scale scheme (1997),[16](https://doi.org/10.1016/s0167-6911%2897%2990015-3) and Spall's simultaneous-perturbation method (2000).[17](https://doi.org/10.1109/tac.2000.880982)\n\n## Variants\n\nThe Kiefer–Wolfowitz procedure estimates the gradient by a finite difference, \\( X_{n+1} - X_n = a_n[Y_n(X_n + C_n) - Y_n(X_n - C_n)]/(2C_n) \\), with conditions \\( \\sum a_n \\cdot C_n < \\infty \\), \\( \\sum a_n^2/C_n^2 < \\infty \\), \\( C_n \\to 0 \\), and \\( \\sum C_n = \\infty \\).[5](https://encyclopediaofmath.org/wiki/Stochastic_approximation) It needs \\( 2d \\) function evaluations per iteration in dimension \\( d \\) (or \\( d+1 \\) with one-sided differences); Spall's SPSA reduces this to two evaluations by perturbing all coordinates simultaneously with random \\( \\pm 1 \\) entries.[10](https://www.professeurs.polymtl.ca/jerome.le-ny/teaching/DP_fall09/notes/lec11_SA.pdf) • [18](https://www.jhuapl.edu/spsa/Comp_Stat_handbook_2nd-edition_Spall.pdf) Polyak and Juditsky's 1992 algorithm averages the trajectories and achieves the highest possible convergence rate for classical optimization and identification problems;[14](https://doi.org/10.1137/0330046) Kushner and Yang showed the optimal rate is generic whenever classical asymptotic normality holds.[15](https://doi.org/10.1137/0331047) Two-time-scale SA runs coupled recursions, so the faster iterates see the slower ones as quasi-static and the analysis reduces to singularly perturbed ODEs.[16](https://doi.org/10.1016/s0167-6911%2897%2990015-3) In the dynamical-systems view, interpolated iterates are asymptotic pseudotrajectories of the limiting ODE, with zero probability of converging to repelling sets such as linearly unstable equilibria and periodic orbits.[19](https://numdam.org/item/SPS_1999__33__1_0.pdf) The incremental gradient method, also known as the perceptron or back-propagation, is a common finite-sum variant, and the SGM with constant stepsize \\( \\alpha_k \\equiv 1 \\) is the randomized [Kaczmarz method](https://www.edgepedia.org/kaczmarz-method), which attains linear convergence.[3](https://people.eecs.berkeley.edu/~brecht/opt4ml_book/O4MD_05_SGM.pdf)\n\n## Applications\n\nRobbins and Monro's own application was recursive estimation of a quantile, such as the median lethal dose in bioassay, from binary response data, with an estimator that is distribution-free.[1](https://doi.org/10.1214/aoms/1177729586) In reinforcement learning, TD(0) is a stochastic approximation,[8](https://www.math.univ-toulouse.fr/%7Egfort/Slides/IMSIMB24.pdf) [Q-learning](https://www.edgepedia.org/q-learning) was published by Watkins and Dayan in Machine Learning in 1992,[20](https://doi.org/10.1007/bf00992698) and Borkar and Meyn gave the first proofs that asynchronous adaptive critic and Q-learning algorithms converge for the average-cost optimal control problem.[21](https://faculty.eng.ufl.edu/meyn/wp-content/uploads/sites/671/archive/spm_files/Papers_pdf/ode.pdf) Variance-reduction oracles extend to general SA, with applications to stochastic EM (SAEM) and online EM.[8](https://www.math.univ-toulouse.fr/%7Egfort/Slides/IMSIMB24.pdf) Benaim's survey lists signal processing, adaptive control, neural networks, and game theory among the fields where the theory is applied,[19](https://numdam.org/item/SPS_1999__33__1_0.pdf) and the SGD instance accounts for much of today's large-scale machine learning computation.[2](https://bactra.org/notebooks/stochastic-approximation.html)\n\n## Limitations and alternatives\n\nStep-size choice is the main practical sensitivity: with \\( \\gamma = C/n \\), convergence fails when \\( 2C \\cdot \\lambda_{\\min}(A) \\le 1 \\).[11](https://www.di.ens.fr/%7efbach/orsay2016/lecture3.pdf) Borkar and Meyn's criterion ties stability of the algorithm to asymptotic stability of the origin for a scaled limiting ODE, which in turn implies convergence.[21](https://faculty.eng.ufl.edu/meyn/wp-content/uploads/sites/671/archive/spm_files/Papers_pdf/ode.pdf) With a fixed step size \\( \\alpha \\) there is no convergence of the iterates, but \\( \\limsup \\mathbb{E}\\|\\theta_n - \\theta^*\\|^2 = O(\\alpha) \\), and averaged fixed-step estimates converge to \\( \\theta^* + \\alpha \\cdot \\bar{u}^* + O(\\alpha^2) \\), a bias of order \\( O(\\alpha) \\), so vanishing-gain algorithms are preferable in reinforcement-learning applications.[22](https://arxiv.org/html/2309.02944) [Multiplicative noise](https://www.edgepedia.org/multiplicative-noise) can produce heavy-tailed stationary distributions with power-law tails \\( P(\\|W\\| > t) = \\Omega(t^{-\\alpha}) \\), even from light-tailed data and light-tailed additive noise, and averaging under multiplicative noise yields a tail heavier than any sub-[Weibull distribution](https://www.edgepedia.org/weibull-distribution).[23](https://ar5iv.labs.arxiv.org/html/2006.06293) Adaptive optimizers such as momentum and Adam incorporate geometric decay that can prevent heavy-tailed fluctuations, potentially limiting exploration while exploiting nearby optima.[23](https://ar5iv.labs.arxiv.org/html/2006.06293) Non-convexity is less damaging than intuition suggests: the iterates have zero probability of converging to repelling sets, including linearly unstable equilibria and periodic orbits.[19](https://numdam.org/item/SPS_1999__33__1_0.pdf) Against deterministic methods, finite-difference SA needs \\( 2p \\) loss measurements per gradient in dimension \\( p \\), SPSA needs two, and adaptive SPSA concurrently estimates the Hessian, producing a stochastic analog of the Newton–Raphson algorithm with near-optimal convergence rate.[18](https://www.jhuapl.edu/spsa/Comp_Stat_handbook_2nd-edition_Spall.pdf)\n\n## References\n\n1. [Herbert Robbins, Sutton Monro (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics.](https://doi.org/10.1214/aoms/1177729586)\n2. [Stochastic Approximation Algorithms (Including Stochastic Gradient Descent), Cosma Shalizi's notebook](https://bactra.org/notebooks/stochastic-approximation.html)\n3. [The Stochastic Gradient Method (Chapter 5, Optimization Methods for ML, Bottou, Curtis & Nocedal)](https://people.eecs.berkeley.edu/~brecht/opt4ml_book/O4MD_05_SGM.pdf)\n4. [J. Kiefer, J. Wolfowitz (1952). Stochastic Estimation of the Maximum of a Regression Function. The Annals of Mathematical Statistics.](https://doi.org/10.1214/aoms/1177729392)\n5. [Stochastic approximation, Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/Stochastic_approximation)\n6. [Historical review of stochastic approximation (Lai, NSF PAR deposited review)](https://par.nsf.gov/servlets/purl/10304143)\n7. [Chapter 6: Stochastic approximation for large sums (lecture notes, E. Pauwels, Université de Toulouse)](https://www.math.univ-toulouse.fr/~epauwels/M2RI/session6.pdf)\n8. [Stochastic Approximation: Finite-time analyses and Variance Reduction (Fort, seminar slides, Nov 2024)](https://www.math.univ-toulouse.fr/%7Egfort/Slides/IMSIMB24.pdf)\n9. [Stochastic approximation: a survey (Kushner, WIREs Computational Statistics, 2009)](https://wires.onlinelibrary.wiley.com/doi/10.1002/wics.57)\n10. [Introduction to Stochastic Approximation Algorithms (J. Le Ny, Polytechnique Montréal lecture notes)](https://www.professeurs.polymtl.ca/jerome.le-ny/teaching/DP_fall09/notes/lec11_SA.pdf)\n11. [Lecture 3: Robbins–Monro algorithm (F. Bach, ENS/Orsay 2016)](https://www.di.ens.fr/%7efbach/orsay2016/lecture3.pdf)\n12. [Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning (Bach & Moulines, NIPS 2011)](https://papers.nips.cc/paper/2011/file/40008b9a5380fcacce3976bf7c08af5b-Paper.pdf)\n13. [L. Ljung (1977). Analysis of recursive stochastic algorithms. IEEE Transactions on Automatic Control.](https://doi.org/10.1109/tac.1977.1101561)\n14. [B. T. Polyak, A. B. Juditsky (1992). Acceleration of Stochastic Approximation by Averaging. SIAM Journal on Control and Optimization.](https://doi.org/10.1137/0330046)\n15. [Harold J. Kushner, Jichuan Yang (1993). Stochastic Approximation with Averaging of the Iterates: Optimal Asymptotic Rate of Convergence for General Processes. SIAM Journal on Control and Optimization.](https://doi.org/10.1137/0331047)\n16. [Stochastic approximation with two time scales (Systems & Control Letters, 1997)](https://doi.org/10.1016/s0167-6911%2897%2990015-3)\n17. [J.C. Spall (2000). Adaptive stochastic approximation by the simultaneous perturbation method. IEEE Transactions on Automatic Control.](https://doi.org/10.1109/tac.2000.880982)\n18. [Stochastic Optimization (Spall, Computational Statistics handbook chapter)](https://www.jhuapl.edu/spsa/Comp_Stat_handbook_2nd-edition_Spall.pdf)\n19. [Dynamics of stochastic approximation algorithms (Benaim, Séminaire de Probabilités 33)](https://numdam.org/item/SPS_1999__33__1_0.pdf)\n20. [Christopher J. C. H. Watkins, Peter Dayan (1992). Q-learning. Machine Learning.](https://doi.org/10.1007/bf00992698)\n21. [Stochastic Approximation and Reinforcement Learning (Borkar & Meyn, SIAM J. Control Optim.)](https://faculty.eng.ufl.edu/meyn/wp-content/uploads/sites/671/archive/spm_files/Papers_pdf/ode.pdf)\n22. [The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning (arXiv)](https://arxiv.org/html/2309.02944)\n23. [Multiplicative noise and heavy tails in stochastic optimization](https://ar5iv.labs.arxiv.org/html/2006.06293)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Statistics and probability › Statistical inference, estimation, sampling, and testing*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Oct 15, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://people.eecs.berkeley.edu/~brecht/opt4ml_book/O4MD_05_SGM.pdf" ], "url": "https://www.edgepedia.org/stochastic-approximation", "markdown_url": "https://www.edgepedia.org/stochastic-approximation.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Stochastic approximation\", Edgepedia (EdgeChat), https://www.edgepedia.org/stochastic-approximation. Edgepedia Community License 1.0.", "credit_md": "\"[Stochastic approximation](https://www.edgepedia.org/stochastic-approximation)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/stochastic-approximation](https://www.edgepedia.org/stochastic-approximation). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Stochastic approximation\", Edgepedia (EdgeChat), https://www.edgepedia.org/stochastic-approximation. Edgepedia Community License 1.0.", "speakable": "Stochastic approximation is a family of iterative algorithms that find the root of an unknown function from noisy observations, introduced by Robbins and Monro in 1951." }