A stochastic approximation algorithm with step size adaptation

Abstract

We consider the following stochastic approximation algorithm of searching for the zero point x∗ of a function ϕ: xt+1 = xt − γtyt, yt = ϕ(xt) + ξt, where yt are observations of ϕ and ξt is the random noise. The step sizes γt of the algorithm are random, the increment γt+1 − γt depending on γt and on yt yt−1 in a rather general form. Generally, it is meant that γt increases as ytyt−1 > 0, and decreases otherwise. It is proved that the algorithm converges to x∗ almost surely. This result generalizes similar results of Kesten (1958) and Plakhov and Almeida (1998), where γt+1 − γt is assumed to depend only on γt and sgn(ytyt−1) and not on the magnitude of ytyt−1.