Details

Autor(en) / Beteiligte

• KUSHNER, H. J
• YANG, J

Titel

Stochastic approximation with averaging of the iterates: optimal asymptotic rate of convergence for general processes

Ist Teil von

• SIAM journal on control and optimization, 1993-07, Vol.31 (4), p.1045-1062

Ort / Verlag

Philadelphia, PA: Society for Industrial and Applied Mathematics

Erscheinungsjahr

1993

Beschreibungen/Notizen

• Consider the stochastic approximation algorithm \[X_{n + 1} = X_n + a_n g(X_n ,\xi _n ).\] In an important paper, Polyak and Juditsky [SIAM J. Control Optim., 30 (1992), pp. 838-855] showed that (loosely speaking) if the coefficients $a_n $ go to zero slower than $O({1 / n})$, then the averaged sequence $\sum\nolimits_{i = 1}^n {{{X_i } / n}} $ converged to its limit, at an optimum rate, for any coefficient sequence. The conditions were rather special, and direct constructions were used. Here a rather simple proof is given that results of this type are generic to stochastic approximation, and essentially hold any time that the classical asymptotic normality of the normalized and centered iterates holds. Considerable intuitive insight is provided into the procedure. Simulations have well borne out the importance of the method.