Stochastic approximation

From Wikipedia, the free encyclopedia

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. The first, and prototypical, algorithms of this kind were the Robbins-Monro and Kiefer-Wolfowitz algorithms.

In the Robbins-Monro algorithm, introduced in 1951^[1], one has a function M(x) for which one wishes to find the value of x, x₀, satisfying M(x₀)=α. However, what is observable is not M(x), but rather a random variable N(x) such that E(N(x)|x)=M(x). The algorithm is then to construct a sequence x₁, x₂, ... which satisfies

x_i+1=x_i+a_i(α-N(x_i)).

Here, a₁, a₂, ... is a sequence of positive step sizes. Robbins and Monro proved that, if N(x) is uniformly bounded, M(x) is nondecreasing, M'(x₀) exists and is positive, and if a_i satisfies a set of bounds (fulfilled if one takes a_i=1/i), then x_i converges in L² (and hence also in probability) to x₀.^{[1], Theorem 2}. In general, the a_i's need not equal 1/i. However, to ensure convergence, they should converge to zero, and in order to average out the noise in N(x), they should converge slowly.

In the similar Kiefer-Wolfowitz algorithm, introduced a year later^[2], one wishes to find the maximum, x₀, of the unknown M(x) and constructs a sequence x₁, x₂, ... such that

x_i+1=x_i+(a_i/c_i)(N(x_i+c_i)-N(x_i-c_i)).

Here, a₁, a₂, ... is a sequence of positive step sizes which serve the same function as in the Robbins-Monro algorithm, and c₁, c₂, ... is a sequence of positive step sizes which are used to estimate, via finite differences, the derivative of M. Kiefer and Wolfowitz showed that, if a_i and c_i satisfy various bounds (fulfilled by taking a_i=1/i, c_i=1/i^1/3), and M(x) and N(x) satisfy some technical conditions, then the sequence x_i converges in probability to x₀.

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 a_i should not converge to zero but should be chosen so as to track the function.^{[3], 2nd ed., chapter 3}

[edit] See also

• Stochastic gradient descent
• Stochastic optimization

[edit] References

1. ^ ^{a b} 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. ^ ^{a b} 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.