On the Choice of Design in Stochastic Approximation Methods
Fabian, Vaclav
Ann. Math. Statist., Tome 39 (1968) no. 6, p. 457-465 / Harvested from Project Euclid
In a previous paper [Fabian (1967)], we have shown that the Kiefer-Wolfowitz procedure--for functions $f$ sufficiently smooth at $\theta$, the point of minimum--can be modified in such a way as to be almost as speedy as the original Robbins-Monro method. The modification consists of taking more observations at every step and utilizing these (according to a design $d$) so as to eliminate the effect of all derivatives $\partial^jf/\lbrack\partial x^{(i)}\rbrack^j, j = 3, 5, \cdots, s - 1$. Let $\delta_n$ be the distance of the approximating value to the approximated $\theta$ after $n$ observations taken. Under some regularity conditions it was shown that $E\delta^2_n = O(n^{-s/(s + 1)}).$ There are many designs $d$ achieving this speed. For selection of the best one, i.e. the one which minimizes $\lim n^{s/(s + 1)}E\delta^2_n$ we have to derive the dependence of this limit on the design $d$, which is done in Section 4. The best choice of the design $d = \lbrack u, \xi\rbrack$ is that which minimizes the right-hand side of (2.7) below; here $u = \lbrack u_1, u_2, \cdots, u_m\rbrack, \xi = \lbrack\xi_1, \cdots, \xi_m\rbrack$ with $0 < u_1 < u_2 < \cdots < u_m \leqq 1, \xi_i \geqq 0, \sum^m_{i = 1}\xi_i = 1; \xi_i$ indicates how many observations should be taken (roughly speaking) at $u_i$. The vector $v = \lbrack v_1, \cdots, v_m\rbrack$ is determined by $v = \frac{1}{2}U^{-1}e_1 (e_1 = \lbrack 1, 0, \cdots, 0\rbrack, \lbrack\cdots\rbrack$ denotes column vectors), $U^{(ij)} = u^{2i - 1}_j, i, j = 1, \cdots, m$. It seems difficult to minimize (2.7) given $K_0, K_1$. Moreover we usually do not know these constants. So in this paper we solve the question of minimizing the first term $\sum^m_{i = 1}(v^2_i/\xi_i)$ only. The result is formulated in Theorem 5.1.
Publié le : 1968-04-14
Classification: 
@article{1177698409,
     author = {Fabian, Vaclav},
     title = {On the Choice of Design in Stochastic Approximation Methods},
     journal = {Ann. Math. Statist.},
     volume = {39},
     number = {6},
     year = {1968},
     pages = { 457-465},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1177698409}
}
Fabian, Vaclav. On the Choice of Design in Stochastic Approximation Methods. Ann. Math. Statist., Tome 39 (1968) no. 6, pp.  457-465. http://gdmltest.u-ga.fr/item/1177698409/