A stochastic algorithm using one sample point per iteration and diminishing step-sizes (Q1102867)

A stochastic algorithm for finding stationary points of real-valued functions defined on a Euclidean space is analyzed. It is based on the Robbins-Monro stochastic approximation procedure. Gradient evaluations are done by means of Monte Carlo simulations. At each iterate \(x_ i\), one sample point is drawn from an underlying probability space, based on which the gradient is approximated. The descent direction is against the approximation of the gradient, and the stepsize is 1/i. It is shown that, under broad conditions, w.p.1. if the sequence of iterates \(x_ 1,x_ 2,..\). generated by the algorithm is bounded, then all of its accumulation points are stationary.