MULTI-LEVEL STOCHASTIC APPROXIMATION ALGORITHMS

• 成果类型: Article
• 署名作者: Frikha, Noufel
• 署名单位: Universite Paris Cite
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/15-AAP1109
• 发表日期: 2016
• 页码: 933-985
• 关键词: monte-carlo; CONVERGENCE; rates; time

摘要

This paper studies multi-level stochastic approximation algorithms. Our aim is to extend the scope of the multi-level Monte Carlo method recently introduced by Giles [Oper. Res. 56 (2008) 607-617] to the framework of stochastic optimization by means of stochastic approximation algorithm. We first introduce and study a two-level method, also referred as statistical Romberg stochastic approximation algorithm. Then its extension to a multi-level method is proposed. We prove a central limit theorem for both methods and give optimal parameters. Numerical results confirm the theoretical analysis and show a significant reduction in the initial computational cost.