Stochastic Approximation


Also found in: Acronyms, Wikipedia.

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 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.

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

References in periodicals archive ?
Ghadimi, "Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: a generic algorithmic framework," Siam Journal on Optimization, vol.
Spall, "Optimal random perturbations for multivariable stochastic approximation using a simultaneous perturbation gradient approximation", IEEE Trans.
Assumption (A2)(iii) on the limit of (n[[gamma].sub.n]) as n goes to infinity is usual in the framework of stochastic approximation algorithms.
Hasminskii, Stochastic Approximation and Recursive Estimation, American Mathematical Society, Providence RI, 1976.
For comparison, the results using the stochastic approximation method (10) are also included.
The algorithms proposed in this article utilize perturbation analysis to carry out the gradient estimation and stochastic approximation to find the optimal number of circulating kanbans for a manufacturing system with general machine breakdown and stochastic demand.
The stochastic approximation method of value assignment assumes that two standards that give the same average signal response when assayed on some specific assay system are functionally equivalent with respect to analyte level.
For model evaluation, they propose and develop performance criteria based on inherence analysis and propose an interactive optimization algorithm based on simultaneous stochastic approximation for improving the performance of learnt human control systems models.
Most of the articles involve stochastic approximations, and only a few uses an alternative approximation of uncertainty, for example, fuzzy logic and robust optimization, among others.
This diagram describes the main crossrelations, the fundamental equivalence principles in the context of stochastic approximations. This exhibits the point where one arrives at the heart of sophisticated numerical approximation theory for stochastic processes.
Our approach is to ask what types of population dynamics are suggested by simple linear, but stochastic approximations. From the perspective of many ecologists, our approach must appear akin to claiming that the earth is flat.
Marceau, "Stochastic approximations of present value functions," Bulletin of the Swiss Association of Actuaries, vol.