×

A stochastic approximation algorithm with step-size adaptation. (English) Zbl 1061.62123

Summary: We consider the following stochastic approximation algorithm for searching of the zero point \(x^*\) of a function \[ \varphi: x_{t+1}=x_t-\gamma_t y_t,\;y_t=\varphi(x_t)+\xi_t, \] where \(y_t\) are observations of \(\varphi\) and \(\xi_t\) is the random noise. The step sizes \(\gamma_t\) of the algorithm are random, the increment \(\gamma_{t+ 1}-\gamma_t\) depending on \(\gamma_t\) and on \(y_ty_{t-1}\) in a rather general form. Generally, it is meant that \(\gamma_t\) increases as \(y_ty_{t-1}>0\), and decreases otherwise. It is proved that the algorithm converges to \(x^*\) almost surely. This result generalizes similar results of H. Kesten [Ann. Math. Stat. 29, 41–59 (1958; Zbl 0087.13404)] and A. Plakhov and L. B. Almeida [Modified Kesten algorithm. Preprint (1998)], where \(\gamma_{t+1}-\gamma_t\) is assumed to depend only on \(\gamma_t\) and \(\text{sgn}(y_ty_{t-1})\) and not on the magnitude of \(y_ty_{t-1}\).

MSC:

62L20 Stochastic approximation
65C60 Computational problems in statistics (MSC2010)

Citations:

Zbl 0087.13404
PDFBibTeX XMLCite
Full Text: DOI