Stochastic Approximation of Minima with Improved Asymptotic Speed

It is shown that the Keifer-Wolfowitz procedure--for functions f sufficiently smooth at θ, 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 ∂ⁱf/∂ x⁽ⁱ⁾ʲ, j = 3, 5 ⋯, s - 1. Let δₙ be the distance from the approximating value to the approximated θ after n observations have been made. Under similar conditions on f as those used by Dupac (1957), the results is Eδₙ² = O(n-s/(s+1)). Under weaker conditions it is proved that δₙ²ns/(s+1)-ε → 0 with probability one for every ε > 0. Both results are given for the multidimensional case in Theorems 5.1 and 5.3. The modified choice of Yₙ in the scheme Xₙ₊₁ = Xₙ - aₙYₙ 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.