Optimization

Stochastic Approximation

Find the root or minimizer of a function observed only through noisy measurements, the theoretical basis of stochastic gradient methods.

Optimizing under noise

Stochastic approximation addresses problems where you cannot evaluate a function exactly, only observe noisy samples of it. The goal is to find a root or a minimizer despite the noise. It is the mathematical foundation of stochastic gradient descent, reinforcement learning updates, and adaptive signal processing.

The Robbins-Monro algorithm

To find x* where g(x*) = 0 given noisy observations Y = g(x) + noise, Robbins-Monro iterates x_{k+1} = x_k - a_k * Y_k. Under a decreasing step-size schedule with sum a_k = infinity and sum a_k^2 < infinity, the iterates converge to x* almost surely. The first condition ensures the algorithm can travel any distance; the second ensures the noise averages out.

Kiefer-Wolfowitz

When only noisy function values are available (not noisy gradients), the Kiefer-Wolfowitz procedure estimates the gradient by finite differences of noisy evaluations, then takes a Robbins-Monro step. It converges more slowly because the finite-difference gradient estimate is itself noisy and biased, but needs no analytic derivative.

Step-size conditions

sum a_k = infinity: steps must not shrink so fast that progress stalls short of the target.
sum a_k^2 < infinity: steps must shrink fast enough to suppress accumulated noise.
A common schedule is a_k = a0 / k, which satisfies both.

Averaging and modern relevance

Polyak-Ruppert averaging, taking the running average of iterates rather than the last one, achieves the asymptotically optimal convergence rate and is more robust to step-size choice. Stochastic approximation theory explains why SGD works, informs learning-rate schedules, and underpins convergence analysis of temporal-difference learning in reinforcement learning.

python

x = x0
for k in range(1, iters+1):
    y = noisy_gradient(x)        # unbiased estimate of grad
    x = x - (a0/k) * y           # Robbins-Monro step

Stochastic approximation is the theory behind training models from noisy, streaming, or sampled data at scale.