A stochastic approximation algorithm with step size adaptation

Plakhov, A.Y.; Cruz, P., (2004) 'A stochastic approximation algorithm with step size adaptation', Journal of Mathematical Science 120(1) pp.964-973 RAE2008

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.

Peer reviewed