Iterate averaging with step sizes decreasing slower than O(1/n) converges at an optimal rate¶

Claim · All claims
Evidence · 1 study · theoretical r3 · q2
Currency · newest study 2003 · not yet checked against its sources · not reviewed by a person · overdue for a recheck since 2006: tool and model accuracy changes quickly

Subclaims¶

q2 i? When coefficients go to zero slower than O(1/n), the averaged iterate sequence converges to its limit at an optimal rate, allowing relatively large step sizes with offline averaging handling increased noise. → Harold J. Kushner and G. George Yin 2003

Evidence¶

Harold J. Kushner and G. George Yin 2003¶

Harold J. Kushner and G. George Yin. (2003). Stochastic Approximation and Recursive Algorithms and Applications, Second Edition. Springer-Verlag, New York. https://doi.org/10.1007/b97441

q2 · i? · theoretical · r3

Analytical result reported in the Preface, attributed to Polyak and Juditsky. The monograph notes these results "have since been corroborated by numerous simulations and extended mathematically."

"Polyak and Juditsky showed that, if the coefficients ϵn go to zero “slower” than O(1/n), then the averaged sequence∑n i=1 θi/n converges to its limit at an optimal rate."

Discussion¶

Related Claims¶

• For tracking time-varying systems, the step size is kept strictly away from zero — related
• Many learning algorithms, including neural network training and Q-learning, have recursive forms of the stochastic approximation type — related
• Diminishing step sizes in stochastic approximation induce implicit averaging that eliminates noise effects in the long run — a broader claim this one bears on
• Hyperparameter sweeps reproduce the lesson's claims: γ = 0 never solves the task while ε = 1 still converges — related