Stochastic approximation

Stochastic approximation methods are a family of iterative methods typically used for root-finding problems or for optimization problems. The recursive update rules of stochastic approximation methods can be used, among other things, for solving linear systems when the collected data is corrupted by noise, or for approximating extreme values of functions which cannot be computed directly, but only estimated via noisy observations.

In a nutshell, stochastic approximation algorithms deal with a function of the form ${\textstyle f(\theta )=\operatorname {E} _{\xi }[F(\theta ,\xi )]}$ which is the expected value of a function depending on a random variable ${\textstyle \xi }$. The goal is to recover properties of such a function ${\textstyle f}$ without evaluating it directly. Instead, stochastic approximation algorithms use random samples of ${\textstyle F(\theta ,\xi )}$ to efficiently approximate properties of ${\textstyle f}$ such as zeros or extrema.

Recently, stochastic approximations have found extensive applications in the fields of statistics and machine learning, especially in settings with big data. These applications range from stochastic optimization methods and algorithms, to online forms of the EM algorithm, reinforcement learning via temporal differences, and deep learning, and others. Stochastic approximation algorithms have also been used in the social sciences to describe collective dynamics: fictitious play in learning theory and consensus algorithms can be studied using their theory.

The earliest, and prototypical, algorithms of this kind are the Robbins–Monro and Kiefer–Wolfowitz algorithms introduced respectively in 1951 and 1952.

The Robbins–Monro algorithm, introduced in 1951 by Herbert Robbins and Sutton Monro, presented a methodology for solving a root finding problem, where the function is represented as an expected value. Assume that we have a function ${\textstyle M(\theta )}$, and a constant ${\textstyle \alpha }$, such that the equation ${\textstyle M(\theta )=\alpha }$ has a unique root at ${\textstyle \theta ^{*}.}$ It is assumed that while we cannot directly observe the function ${\textstyle M(\theta ),}$ we can instead obtain measurements of the random variable ${\textstyle N(\theta )}$ where ${\textstyle \operatorname {E} [N(\theta )]=M(\theta )}$. The structure of the algorithm is to then generate iterates of the form:

$${\displaystyle \theta _{n+1}=\theta _{n}-a_{n}(N(\theta _{n})-\alpha )}$$

Here, ${\displaystyle a_{1},a_{2},\dots }$ is a sequence of positive step sizes. Robbins and Monro proved^{, Theorem 2} that ${\displaystyle \theta _{n}}$ converges in ${\displaystyle L^{2}}$ (and hence also in probability) to ${\displaystyle \theta ^{*}}$, and Blum later proved the convergence is actually with probability one, provided that:

$${\displaystyle \qquad \sum _{n=0}^{\infty }a_{n}=\infty \quad {\mbox{ and }}\quad \sum _{n=0}^{\infty }a_{n}^{2}<\infty \quad }$$ A particular sequence of steps which satisfy these conditions, and was suggested by Robbins–Monro, have the form: ${\textstyle a_{n}=a/n}$, for ${\textstyle a>0}$. Other series, such as ${\displaystyle a_{n}={\frac {1}{n\ln n}},{\frac {1}{n\ln n\ln \ln n}},\dots }$ are possible but in order to average out the noise in ${\textstyle N(\theta )}$, the above condition must be met.