Stochastic Approximation(redirected from Robbins-Monro algorithm)
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 yk of the function R(x) at a point xk contains a random error. The Robbins-Monro procedure is given by the formula xk+ y = × k + a k (y k – α). Under certain conditions on R(x), on the sequence ak approaching zero, and on the character of the random errors, it has been proved that xk → θ 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 xk – 8 has led to the construction of asymptotically optimal stochastic approximation procedures, in which the sequence ak must be chosen independence on the observations.
REFERENCESWasan, 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