Stochastic Approximation

Stochastic Approximation 

a method of solving a broad class of problems in statistical estimation. In this method, each successive estimate is obtained in the form of a correction of the preceding estimate, the correction being based solely on new observations. The principal features responsible for the popularity of stochastic approximation in both theoretical and applied work are the method’s nonparametric character (its applicability when the information available on the object of observation is scanty) and its recursive nature (simplicity of recalculation of the estimate when new observation results are obtained). Stochastic approximation is used in many applied problems in control theory, instruction theory, and in problems of engineering, biology, and medicine.

Stochastic approximation was introduced in 1951 by the American statisticians H. Robbins and S. Monro. They set forth a recursion scheme for finding the root of a regression equation—that is, the root α of the equation R(x) = α where each measured value y_k of the function R(x) at a point x_k contains a random error. The Robbins-Monro procedure is given by the formula x_k+ y = × _k + a _k (y _k – α). Under certain conditions on R(x), on the sequence a_k approaching zero, and on the character of the random errors, it has been proved that x_k → θ as k increases.

The method of stochastic approximation was subsequently applied to other problems, such as the finding of the maximum of a regression function and the estimation of the unknown parameters of a distribution on the basis of observations. Investigation of the limiting distribution of the normalized difference x_k – 8 has led to the construction of asymptotically optimal stochastic approximation procedures, in which the sequence a_k must be chosen independence on the observations.

REFERENCES

Wasan, M. Stokhasiicheskaia approksimatsiia. Moscow, 1972. (Translated from English.)
Nevel’son, M. B., and R. Z. Khas’minskii. Stokhasiicheskaia approksimatsiia i rekurrentnoe otsenivanie. Moscow, 1972.

R. Z. KHAS’MINSKII