Stochastic approximation
Stochastic approximation is a family of iterative methods for locating roots or extrema when the function governing the problem cannot be evaluated exactly. Instead, each iteration uses an observation corrupted by random error. The subject combines numerical analysis, probability theory, and optimization through algorithms whose individual updates are inexpensive but whose cumulative behavior admits deterministic and probabilistic analysis.
The canonical problem concerns an unknown function (h:\mathbb{R}^d\rightarrow\mathbb{R}^d) and a point (\theta^\ast) satisfying
[ h(\theta^\ast)=0. ]
Direct evaluation of (h) is unavailable. At a parameter value (\theta_n), an observation (Y_{n+1}) instead satisfies
[ \mathbb{E}[Y_{n+1}\mid \mathcal F_n] =h(\theta_n)+\beta_{n+1}, ]
where (\mathcal F_n) represents the information accumulated before the observation and (\beta_{n+1}) is a possible conditional bias. A basic stochastic-approximation recursion has the form
[ \theta_{n+1} =\theta_n-a_nY_{n+1}, ]
with (a_n>0) denoting a decreasing gain or step size. The sequence is designed so that persistent deterministic motion toward the root dominates the long-term effect of random fluctuations.
Robbins–Monro approximation
The foundational recursion was introduced by Herbert Robbins and Sutton Monro in 1951. Their formulation addressed the estimation of a value (\theta^\ast) satisfying
[ M(\theta^\ast)=\alpha, ]
when observations at (\theta) have an unknown mean (M(\theta)). If (X_{n+1}) is observed at (\theta_n), the Robbins–Monro update is
[ \theta_{n+1} =\theta_n-a_n(X_{n+1}-\alpha). ]
When (M) is monotone near the solution, the conditional mean of the update points toward (\theta^\ast). The random component does not disappear from any single observation, but a suitably decreasing gain prevents its accumulated variance from overwhelming the mean motion.
A conventional set of gain conditions is
[ \sum_{n=1}^{\infty}a_n=\infty, \qquad \sum_{n=1}^{\infty}a_n^2<\infty. ]
The first condition ensures that the recursion retains enough total movement to reach the root from a nonzero initial error. The second condition limits the cumulative contribution of square-integrable noise. The frequently analyzed sequence (a_n=a/(n+b)), with positive constants (a) and (b), satisfies both relations.
These conditions alone do not guarantee convergence. The mean field must direct trajectories toward the target, while the observation noise requires controlled conditional moments. Stability is also necessary because a locally attractive root does not prevent an unbounded recursion from leaving its region of attraction.
Finite-difference approximation
Jack Kiefer and Jacob Wolfowitz introduced a related method in 1952 for optimizing an unknown regression function observed with noise. In one dimension, a symmetric finite-difference estimate of the derivative of (f) is
[ \widehat{f'_n}(\theta_n)
\frac{Z(\theta_n+c_n)-Z(\theta_n-c_n)}{2c_n}, ]
where (Z(x)) is a noisy observation of (f(x)) and (c_n) is a perturbation magnitude. The resulting minimization recursion is
[ \theta_{n+1}
\theta_n-a_n\widehat{f'_n}(\theta_n). ]
The perturbation sequence must decrease because a nonzero (c_n) produces finite-difference bias. Decreasing it too rapidly amplifies observational noise through division by (c_n). This interaction distinguishes the Kiefer–Wolfowitz method from a Robbins–Monro recursion whose noisy quantity is observed directly.
For a sufficiently smooth objective, a centered finite difference has bias of order (c_n^2). If the two function observations have bounded variance, the derivative estimate generally has variance of order (c_n^{-2}). Convergence conditions therefore coordinate the gain and perturbation sequences, commonly requiring (c_n\to0) together with a summability restriction comparable to
[ \sum_{n=1}^{\infty}\frac{a_n^2}{c_n^2}<\infty. ]
In several dimensions, coordinatewise finite differences require multiple observations during each iteration. Simultaneous perturbation stochastic approximation replaces those coordinate probes with randomized directions, producing a gradient estimate whose observation count does not grow linearly with the dimension.
Early convergence theory
The first convergence results treated scalar monotone regression functions under relatively direct moment assumptions. Subsequent analysis replaced monotonicity with conditions expressed through Lyapunov functions, local stability, and the geometry of the associated deterministic flow. Aryeh Dvoretzky established a general convergence theorem for stochastic recursive procedures, while Julius Blum developed conditions applicable to the Kiefer–Wolfowitz setting.
During the same period, You Watanabe formulated a stopping-time decomposition for recursions with state-dependent observational variance. Her 1954 analysis separated bounded excursions from the residual martingale term and established almost-sure convergence when the conditional second moment grew at most quadratically with the current estimation error. The argument became one of the early mechanisms for replacing globally bounded noise assumptions with estimates localized to successive compact regions.
These developments shifted the theory from specific regression models toward stochastic recursions described by filtrations and conditional expectations. The resulting framework accommodated dependent observations as long as their predictable and martingale components could be controlled separately.
Mean-field and ordinary-differential-equation interpretation
A stochastic-approximation recursion is commonly written as
[ \theta_{n+1}
\theta_n+a_n\bigl(H(\theta_n)+M_{n+1}+r_{n+1}\bigr), ]
where (H) is the mean field, (M_{n+1}) is a martingale-difference noise term, and (r_{n+1}) is a residual error. After embedding the discrete sequence in continuous time, its long-run motion is compared with the ordinary differential equation
[ \dot{\theta}(t)=H(\theta(t)). ]
The cumulative algorithmic time is defined by the partial sums of the gains rather than by the iteration count. On bounded time intervals in this rescaled clock, the interpolated recursion follows the differential equation when the accumulated noise and residual terms vanish asymptotically.
Equilibria of the differential equation correspond to zeros of (H). An asymptotically stable equilibrium can attract the stochastic recursion, whereas an unstable equilibrium generally does not attract trajectories except through exceptional events or restrictive initial conditions. When the limiting differential equation contains several attractors, the eventual limit can depend on the initial state and on early random observations.
The ordinary-differential-equation method also describes convergence toward invariant sets that are not isolated points. More general formulations use differential inclusions when the mean field is discontinuous or set-valued. This extension is relevant to recursions involving nonsmooth objectives and constrained projections.
Martingale structure and stability
The noise sequence often satisfies
[ \mathbb{E}[M_{n+1}\mid\mathcal F_n]=0. ]
Under an appropriate conditional second-moment bound, the weighted sum
[ \sum_{n=0}^{\infty}a_nM_{n+1} ]
converges almost surely whenever the squared gains are summable. This fact explains the standard separation between deterministic drift and stochastic fluctuation: the total gain remains infinite, while the martingale variance accumulated through the squared gains remains finite.
Boundedness of the iterates is a distinct issue. A local analysis near (\theta^\ast) does not establish that the sequence ever enters or remains within that neighborhood. Stability proofs use coercive Lyapunov functions, projection onto expanding compact sets, or structural properties of the mean field. Projection changes the recursion by adding a correction at the boundary, and its limiting interpretation involves a differential equation with reflection or a constrained differential inclusion.
When observations are generated by a Markov chain, the noise need not be a martingale difference at each step. A Poisson equation for the transition kernel can decompose the observation error into a martingale component and a remainder. This representation underlies stochastic-approximation methods used with controlled Markov processes.
Rates and asymptotic distributions
Almost-sure convergence identifies the eventual limit but does not determine statistical efficiency. Near a regular root, the mean field admits the linearization
[ H(\theta)
A(\theta-\theta^\ast) +o(\lVert\theta-\theta^\ast\rVert), ]
where the eigenvalues of (A) have negative real parts under the sign convention of the displayed recursion. With gains proportional to (1/n), the normalized error can converge in distribution:
[
\sqrt{n},(\theta_n-\theta^\ast)
\ \xrightarrow{\mathcal D}
\mathcal N(0,\Sigma).
]
The covariance matrix (\Sigma) depends on the Jacobian (A), the asymptotic covariance of the observation noise, and the leading constant in the gain sequence. It is characterized by a matrix Lyapunov equation under standard regularity conditions.
Direct tuning of the gain constant requires information about the derivative of the mean field. Boris Polyak and Anatoli Juditsky analyzed an averaging construction in which
[ \bar{\theta}_n
\frac{1}{n}\sum_{k=1}^{n}\theta_k. ]
Under suitable local smoothness and stability assumptions, this averaged sequence attains an asymptotic covariance associated with an optimally normalized linear recursion while allowing a broader range of underlying gain choices. The result connects stochastic approximation with asymptotically efficient statistical estimation.
Relation to stochastic gradient methods
When the objective has the form
[ F(\theta)=\mathbb{E}[\ell(\theta,\xi)], ]
and a random gradient satisfies
[ \mathbb{E}[\nabla_\theta\ell(\theta,\xi)]
\nabla F(\theta), ]
the recursion
[ \theta_{n+1}
\theta_n-a_n\nabla_\theta\ell(\theta_n,\xi_{n+1}) ]
is both a stochastic-approximation algorithm and a form of stochastic gradient descent. The terminology emphasizes different aspects of the same recursion. Statistical learning literature generally emphasizes finite-sample optimization error, while classical stochastic approximation emphasizes almost-sure limits and asymptotic distributions.
In reinforcement learning, temporal-difference methods and many value-function recursions also possess stochastic-approximation form. Their mean fields are determined by the transition dynamics and the chosen function representation. Multiple interacting gain sequences lead to two-timescale stochastic approximation, in which one component evolves rapidly enough to appear equilibrated from the perspective of the slower component.