Stochastic approximation

Stochastic approximation methods are a family of iterative stochastic optimization algorithms that attempt to find zeroes or extrema of functions which cannot be computed directly, but only estimated via noisy observations. Mathematically, this refers to solving:

${\displaystyle \min _{x\in \Theta }\;f(x)=\mathbb {E} [F(x,\xi )]}$

where the objective is to find the parameter ${\displaystyle x\in \Theta }$, which minimizes the above function for some unknown random variable, ${\displaystyle \xi }$. It is assumed that while the ___domain ${\displaystyle \Theta \subset \mathbb {R} ^{d}}$ is known, where ${\displaystyle d}$ is the dimension of the parameter ${\displaystyle x}$, ${\displaystyle f(x)}$ cannot be computed exactly, but instead approximated via simulation.

The first, and prototypical, algorithms of this kind were the Robbins-Monro and Kiefer-Wolfowitz algorithms.

Robbins-Monro algorithm

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

${\displaystyle x_{n+1}=x_{n}+a_{n}(\alpha -N(x_{n}))}$ .

Here, ${\displaystyle a_{1},a_{2},\dots }$  is a sequence of positive step-sizes. Robbins and Monro proved ^{[1], Theorem 2} that ${\displaystyle x_{n}}$  converges in ${\displaystyle L^{2}}$  (and hence also in probability) to ${\displaystyle \theta }$  provided that:

• ${\displaystyle N(x)}$  is uniformly bounded,
• ${\displaystyle M(x)}$  is nondecreasing,
• ${\displaystyle M'(x_{0})}$  exists and is positive, and
• ${\displaystyle a_{n}}$  satisfies the following requirements:

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

The last condition is fulfilled for example by taking ${\displaystyle a_{n}=1/n}$ ; other series are possible but in order to average out the noise in ${\displaystyle N(x)}$ , ${\displaystyle a_{n}}$  must converge slowly.

Kiefer-Wolfowitz algorithm

In the Kiefer-Wolfowitz algorithm^[2], introduced a year after the Robbins-Monro algorithm, one wishes to find the maximum, ${\displaystyle x_{0}}$ , of the unknown ${\displaystyle M(x)}$  and constructs a sequence ${\displaystyle x_{1},x_{2},\dots }$  such that

${\displaystyle x_{n+1}=x_{n}+a_{n}{\frac {N(x_{n}+c_{n})-N(x_{n}-c_{n})}{c_{n}}}}$ .

Here, ${\displaystyle a_{1},a_{2},\dots }$  is a sequence of positive step sizes which serve the same function as in the Robbins-Monro algorithm, and ${\displaystyle c_{1},c_{2},\dots }$  is a sequence of positive step sizes which are used to estimate, via finite differences, the derivative of ${\displaystyle M}$ . Kiefer and Wolfowitz showed that, if ${\displaystyle a_{n}}$  and ${\displaystyle c_{n}}$  satisfy various bounds (fulfilled by taking ${\displaystyle a_{n}=1/n}$ , ${\displaystyle c_{n}=(1/n)^{1/3}}$ ), and ${\displaystyle M(x)}$  and ${\displaystyle N(x)}$  satisfy some technical conditions, then the sequence ${\displaystyle x_{n}}$  converges in probability to ${\displaystyle x_{0}}$ .

Subsequent developments

An extensive theoretical literature has grown up around these algorithms, concerning conditions for convergence, rates of convergence, multivariate and other generalizations, proper choice of step size, possible noise models, and so on.^[3][4] These methods are also applied in control theory, in which case the unknown function which we wish to optimize or find the zero of may vary in time. In this case, the step size ${\displaystyle a_{n}}$  should not converge to zero but should be chosen so as to track the function.^{[3], 2nd ed., chapter 3}

C. Johan Masreliez and R. Douglas Martin were the first to use stochastic approximation in 1975 when dealing with robust estimation.^[5]

See also

• Stochastic gradient descent
• Stochastic optimization
• Simultaneous perturbation stochastic approximation

References

1. A Stochastic Approximation Method, Herbert Robbins and Sutton Monro, Annals of Mathematical Statistics 22, #3 (September 1951), pp. 400–407.
2. Stochastic Estimation of the Maximum of a Regression Function, J. Kiefer and J. Wolfowitz, Annals of Mathematical Statistics 23, #3 (September 1952), pp. 462–466.
3. Stochastic Approximation Algorithms and Applications, Harold J. Kushner and G. George Yin, New York: Springer-Verlag, 1997. ISBN 038794916X; 2nd ed., titled Stochastic Approximation and Recursive Algorithms and Applications, 2003, ISBN 0387008942.
4. Stochastic Approximation and Recursive Estimation, Mikhail Borisovich Nevel'son and Rafail Zalmanovich Has'minskiĭ, translated by Israel Program for Scientific Translations and B. Silver, Providence, RI: American Mathematical Society, 1973, 1976. ISBN 0821815970.
5. R.D. Martin & C.J. Masreliez, Robust estimation via stochastic approximation. IEEE Trans. Inform. Theory, 21(pp.263—271) (1975).