On Stochastic Approximation

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