ON STOCHASTIC APPROXIMATION

Abstract

Stochastic approximation is concerned with schemes converging to some sought value when, due to the stochastic nature of the problem, the observations involve errors. The interesting schemes are those which are self-correcting, that is, in which a mistake always tends to be wiped out in the limit, and in which the convergence to the desired value is of some specified nature, for example, it is mean-square convergence. The typical example of such a scheme is the original one of Robbins-Monro [7] for approximating, under suitable conditions, the point where a regression function assumes a given value. Robbins and Monro have proved mean-square convergence to the root; Wolfowitz [8] showed that under weaker assumptions there is still convergence in probability to the root; and Blum [11 demonstrated that, under still weaker assumptions, there is not only convergence in probability but even convergence with probability 1. Kiefer and Wolfowitz [6] have devised a method for approximating the point where the maximum of a regression function occurs. They proved that under suitable conditions there is convergence in probability and Blum [1] has weakened somewhat the conditions and strengthened the conclusion to convergence with probability 1. The two schemes mentioned above are rather specific. We shall deal with a vastly more general situation. The underlying idea is to think of the random element as noise superimposed on a convergent deterministic scheme. The Robbins-Monro and KieferWolfowitz procedures, under conditions weaker than any previously considered, are included as very special cases and, despite this generality, the conclusion is stronger since our results assert that the convergence is both in mean-square and with probability 1. The main results are stated in section 2 and their proof follows in sections 3 and 4. Various generalizations are given in section 5, while section 6 furnishes an instructive counterexample. The Robbins-Monro and Kiefer-Wolfowitz procedures are treated in section 7. Because of the generality of our results the proofs in sections 3 and 4 have to overcome a number of technical difficulties and are somewhat involved. A special case of considerable scope where the technical difficulties disappear is discussed in section 8. This section is essentially self-contained and includes an extremely simple complete proof of the mean-square convergence result in the special case, which illustrates the underlying idea of our method. In section 8 we also find the best (unique minimax in a nonasymptotic sense) way of choosing the an in a special case of the Robbins-Monro scheme [they are of the form c/(n + c')]. The concluding section 9 contains some remarks on extensions to nonreal random variables and other topics. Since the primary object of this paper is to give the general approach, no attempt has been made to study any specific procedures except the well-known Robbins-Monro and Kiefer-Wolfowitz schemes which serve as imustrations.