Content deleted Content added
Spacepotato (talk | contribs) They're stochastic optimization algorithms. |
Spacepotato (talk | contribs) Grammar; Kiefer-Wolfowitz paper uses c_n, not 2c_n. |
||
Line 8:
Here, <math>a_1,a_2,\dots</math> is a sequence of positive step sizes. Robbins and Monro proved that, if <math>N(x)</math> is uniformly bounded, <math>M(x)</math> is nondecreasing, <math>M'(x_0)</math> exists and is positive, and if <math>a_n</math> satisfies a set of bounds (fulfilled if one takes <math>a_n=1/n</math>), then <math>x_n</math> converges in <math>L_2</math> (and hence also in probability) to <math>x_0</math>.<ref name="rm" /><sup>, Theorem 2</sup>. In general, the <math>a_n's</math> need not equal <math>1/n</math>. However, to ensure convergence, they should converge to zero, and in order to average out the noise in <math>N(x)</math>, they should converge slowly.
== Kiefer-Wolfowitz algorithm ==
In the Kiefer-Wolfowitz algorithm <ref>Stochastic Estimation of the Maximum of a Regression Function, [[Jack Kiefer (mathematician)|J. Kiefer]] and J. Wolfowitz, ''Annals of Mathematical Statistics'' '''23''', #3 (September 1952), pp. 462–466.</ref>, introduced a year after the Robbins-Monro algorithm , one wishes to find the maximum, <math>x_0</math>, of the unknown <math>M(x)</math>
and constructs a sequence <math>x_1,x_2,\dots</math> such that
::<math>x_{n+1}=x_n+a_n\frac{N(x_n+c_n)-N(x_n-c_n)}{
Here, <math>a_1,a_2,\dots</math> is a sequence of positive step sizes which serve the same function as in the Robbins-Monro algorithm, and <math>c_1,c_2\dots</math> is a sequence of positive step sizes which are used to estimate, via finite differences, the derivative of <math>M</math>. [[Jack Kiefer (mathematician)|Kiefer]] and Wolfowitz showed that, if <math>a_n</math> and <math>c_n</math> satisfy various bounds (fulfilled by taking <math>a_n=1/n</math>, <math>c_n=(1/n)^{1/3}</math>), and <math>M(x)</math> and <math>N(x)</math> satisfy some technical conditions, then the sequence <math>x_n</math> converges in probability to <math>x_0</math>.
| |||