  This paper studies multi-level stochastic approximation algorithms. Our aim
is to extend the scope of the multilevel Monte Carlo method recently introduced
by Giles (Giles 2008) 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 multi-level is proposed. We prove a central
limit theorem for both methods and describe the possible optimal choices of
step size sequence. Numerical results confirm the theoretical analysis and show
a significant reduction in the initial computational cost.
