Stochastic approximation: Difference between revisions

Revision as of 23:37, 6 June 2011

Revision as of 23:41, 6 June 2011

Line 6:

==Robbins-Monro algorithm==

The [[Herbert Robbins|Robbins]]-Monro algorithm, introduced in 1951<ref name="rm">A Stochastic Approximation Method, Herbert Robbins and Sutton Monro, ''Annals of Mathematical Statistics'' '''22''', #3 (September 1951), pp. 400–407.</ref>, presented a methodology for solving a root finding problem, where the function is represented as an expected value. Let us assume that we have a function <math>M(x)</math>, and a constant <math>\alpha</math>, such that the equation <math>M(x) = \alpha</math> has a unique root at <math>x=\theta</math>. It is assumed that while we cannot directly observe the function <math>M(x)</math>, we can instead obtain measurements of the random variable <math>N(x)</math> with the property ofwhere <math>\mathbb E[N(x)] = M(x)</math>. The structure of the algorithm is to then generate iterates of the form

::<math>x_{n+1}=x_n+a_n(\alpha-N(x_n))</math>.

Here, <math>a_1, a_2, \dots</math> is a sequence of positive step-sizes. [[Herbert Robbins|Robbins]] and Monro proved <ref name="rm" />^{, Theorem 2} that <math>x_n</math> [[convergence of random variables|converges]] in <math>L^2</math> (and hence also in probability) to <math>x_0\theta</math> provided that:

* <math>N(x)</math> is uniformly bounded,

* <math>M(x)</math> is nondecreasing,

* <math>M'(x_0)</math> exists and is positive, and

* <math>a_n</math> satisfies athe certainfollowing set of bounds, to converge slowly to zero.requirements:

:<math>x_{n+1}=x_n+a_n(\alpha-N(x_n))</math>

The last condition is fulfilled for example by taking <math>a_n=1/n</math>; other series are possible but in order to average out the noise in <math>N(x)</math>, <math>a_n</math> must converge slowly.