View source for Stochastic approximation

A method for solving a class of problems of [[Statistical estimation|statistical estimation]], in which the new value of the estimator is a modification of an existing estimator, based on new information. The first procedure of stochastic approximation was proposed in 1951 by H. Robbins and S. Monro.

Let every measurement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s0900101.png" /> of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s0900102.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s0900103.png" />, at a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s0900104.png" /> contain a random error with mean zero. The Robbins–Monro procedure of stochastic approximation for finding a root of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s0900105.png" /> takes the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s0900106.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s0900107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s0900108.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s0900109.png" /> is, for example, an increasing function, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001010.png" /> increases no faster than a linear function, and if the random errors are independent, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001011.png" /> tends to a root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001012.png" /> of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001013.png" /> with probability 1 and in the quadratic mean (see [[#References|[1]]], [[#References|[2]]]). It is clear from (1) that the process of stochastic approximation is recursive, i.e. a new value of the estimator can be obtained without recourse to the old measurement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001014.png" />, and is convenient in cases where the moment at which the estimator is to be represented is not known in advance. The estimator is formed continuously on the basis of observations relating to a given moment. These characteristics also pertain to stochastic approximation with recursive filters, and explain the popularity of stochastic approximation in theoretical and practical applications. The procedure (1) can be directly generalized to the multi-dimensional case.

Another procedure of stochastic approximation, used in finding a maximum point of a regression function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001015.png" />, is attributed to J. Kiefer and J. Wolfowitz. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001016.png" /> be an observation at the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001017.png" />. The Kiefer–Wolfowitz procedure then takes the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001018.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

It has been proved that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001019.png" /> converges to a maximum point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001020.png" /> of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001021.png" /> if, for example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001022.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001023.png" />, if the regression function and the variance of the random errors do not increase too rapidly when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001024.png" />, and if the conditions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001025.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001026.png" /></td> </tr></table>

are fulfilled. The Kiefer–Wolfowitz procedure of stochastic approximation also permits a multi-dimensional generalization: instead of the right-hand side in (2), an approximate value of the gradient of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001027.png" /> has to be substituted.

Procedures of stochastic approximation can naturally be generalized to a continuous observation process. For example, if an observation process is disturbed by a Gaussian white noise, then the analogue of (1) takes the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001028.png" /></td> </tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001029.png" /></td> </tr></table>

is the differential of the process under observation and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001030.png" /> is a [[Wiener process|Wiener process]]. The conditions of convergence of continuous processes are analogous to those mentioned above for discrete time (see [[#References|[2]]]). The basic instrument for proving the convergence of procedures of stochastic approximation is the theorem on the convergence of non-negative supermartingales (see [[Martingale|Martingale]]).

The limit behaviour for an appropriate normalization of the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001031.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001032.png" /> has been studied. In (1), let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001033.png" /></td> </tr></table>

and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001034.png" /> almost certainly when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001035.png" />. Given certain restrictions, foremost among which are the requirements

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001036.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001037.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001038.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001039.png" />, the asymptotic normality of the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001040.png" /> with parameters 0, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001041.png" /> has been proved. The least variance of the limit distribution is obtained for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001042.png" />. This choice of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001043.png" /> is impossible, since the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001044.png" /> and its derivative are unknown values to be observed. However, in a number of works, adaptive procedures have been constructed in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001045.png" /> depends on the observations and approximates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001046.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001047.png" />. These procedures possess properties that are asymptotically optimal in the sense of the asymptotic variance.

The results of asymptotic normality are also known in the multi-dimensional case. Let all roots of the matrix

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001048.png" /></td> </tr></table>

have negative real parts (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001049.png" /> is the identity matrix), let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001050.png" /></td> </tr></table>

when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001051.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001052.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001053.png" /> almost certainly, and let certain other not too-restrictive conditions be fulfilled. Then the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001054.png" /> is asymptotically normal with mean zero and with covariance matrix

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001055.png" /></td> </tr></table>

The above result for an asymptotically-optimal Robbins–Monro procedure can also be generalized to the multi-dimensional case. It has been proved that the random process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001056.png" /> converges to a Gaussian Markov process in a logarithmic scale. Given certain conditions, the convergence of the moments of the random variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001057.png" /> to the moments of the limit law has been proved.

Stochastic approximation-type procedures are convenient in non-parametric situations, since they can be used when a priori information on the regression function is scarce. However, they are also used in estimating the parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001058.png" /> of the density <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001059.png" /> through independent observations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001060.png" /> with this density. Given certain restrictions, the recursive procedure

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001061.png" /></td> </tr></table>

(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001062.png" /> is the Fisher [[Information matrix|information matrix]] of the density <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001063.png" />) is a consistent and asymptotically-efficient recursive estimator of the parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s090/s090010/s09001064.png" />. The same process is also possible in the case of continuous time.

The behaviour of procedures of stochastic approximation has been studied in the case where the regression function has several zeros (several extremal points), and for different modifications and generalizations of procedures of stochastic approximation.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M.T. Wasan,   "Stochastic approximation" , Cambridge Univ. Press  (1969)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  M.B. Nevel'son,   R.Z. Khas'minskii,   "Stochastic approximation and recursive estimation" , Amer. Math. Soc.  (1976)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  Ya.Z. Tsypkin,   "Adaption and learning in automatic systems" , Acad. Press  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  Ya.Z. Tsypkin,   "Foundations of the theory of learning systems" , Acad. Press  (1973)  (Translated from Russian)</TD></TR></table>



====Comments====
Convergence properties of stochastic approximation and other recursive algorithms have been the subject of much research. One approach is the  "ordinary differential equations"  method ([[#References|[a1]]], [[#References|[a2]]]), which is based on interpreting suitably rescaled versions of (1) and (2) as Euler approximations to the solution of an ordinary or stochastic differential equation. Asymptotic properties of the algorithm can then be related to stability properties of the corresponding ordinary or stochastic differential equation. Methods based on compactness and weak convergence have also been introduced.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H.J. Kushner,   D.S. Clark,   "Stochastic approximation methods for constrained and unconstrained systems" , Springer  (1978)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Ljung,   "Analysis of recursive stochastic algorithms"  ''IEEE Trans. Autom. Control'' , '''AC-22'''  (1977)  pp. 551–575</TD></TR></table>