Stochastic Approximation of Minima with Improved Asymptotic Speed

Abstract

It is shown that the Keifer-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 Robins-Monro method. The modification consists in making more observations at every step and in utilizing these so as to eliminate the effect of all derivatives $\partial^if/\lbrack\partial x^{(i)}\rbrack^j, j = 3, 5 \cdots, s - 1$. Let $\delta_n$ be the distance from the approximating value to the approximated $\theta$ after $n$ observations have been made. Under similar conditions on $f$ as those used by Dupac (1957), the results is $E\delta_n^2 = O(n^{-s/(s+1)})$. Under weaker conditions it is proved that $\delta_n^2n^{s/(s+1)-\epsilon} \rightarrow 0$ with probability one for every $\epsilon > 0$. Both results are given for the multidimensional case in Theorems 5.1 and 5.3. The modified choice of $Y_n$ in the scheme $X_{n+1} = X_n - a_nY_n$ is described in Lemma 3.1. The proofs are similar to those used by Dupac (1957) and are based on Chung's (1954) lemmas and, in Theorem 5.3, on a modification of one of these lemmas. The result of Theorem 5.3 is new also for the usual Kiefer-Wolfowitz procedure. The main and very simple idea, however, is in Lemma 3.1; it will suggest, to a reader acquainted with Dupac's Theorem 3 and its proof, the consequences elaborated in Theorem 5.1.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 153 citations exist upstream.