Accelerated Stochastic Approximation
Kesten, Harry
Ann. Math. Statist., Tome 29 (1958) no. 4, p. 41-59 / Harvested from Project Euclid
Using a stochastic approximation procedure $\{X_n\}, n = 1, 2, \cdots$, for a value $\theta$, it seems likely that frequent fluctuations in the sign of $(X_n - \theta) - (X_{n - 1} - \theta) = X_n - X_{n - 1}$ indicate that $|X_n - \theta|$ is small, whereas few fluctuations in the sign of $X_n - X_{n - 1}$ indicate that $X_n$ is still far away from $\theta$. In view of this, certain approximation procedures are considered, for which the magnitude of the $n$th step (i.e., $X_{n + 1} - X_n$) depends on the number of changes in sign in $(X_i - X_{i - 1})$ for $i = 2, \cdots, n$. In theorems 2 and 3, $$X_{n + 1} - X_n$$ is of the form $b_nZ_n$, where $Z_n$ is a random variable whose conditional expectation, given $X_1, \cdots, X_n$, has the opposite sign of $X_n - \theta$ and $b_n$ is a positive real number. $b_n$ depends in our processes on the changes in sign of $$X_i - X_{i - 1}(i \leqq n)$$ in such a way that more changes in sign give a smaller $b_n$. Thus the smaller the number of changes in sign before the $n$th step, the larger we make the correction on $X_n$ at the $n$th step. These procedures may accelerate the convergence of $X_n$ to $\theta$, when compared to the usual procedures ([3] and [5]). The result that the considered procedures converge with probability one may be useful for finding optimal procedures. Application to the Robbins-Monro procedure (Theorem 2) seems more interesting than application to the Kiefer-Wolfowitz procedure (Theorem 3).
Publié le : 1958-03-14
Classification: 
@article{1177706705,
     author = {Kesten, Harry},
     title = {Accelerated Stochastic Approximation},
     journal = {Ann. Math. Statist.},
     volume = {29},
     number = {4},
     year = {1958},
     pages = { 41-59},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1177706705}
}
Kesten, Harry. Accelerated Stochastic Approximation. Ann. Math. Statist., Tome 29 (1958) no. 4, pp.  41-59. http://gdmltest.u-ga.fr/item/1177706705/