Stochastic approximation

Summary

Stochastic approximation is a family of iterative methods for finding a root or an extremum of a function observed only with random noise. Each step moves the current guess by a decreasing step size times a noisy measurement. The first methods were the Robbins–Monro algorithm of 1951, for roots, and the Kiefer–Wolfowitz algorithm of 1952, for maxima. Stochastic gradient descent, the workhorse of machine learning, is a stochastic approximation method.