| Abstract: | We develop a framework that allows the use of the multi-level Monte Carlo (MLMC) methodology (Giles in Acta Numer. 24:259–328, 2015. https://doi.org/10.1017/S096249291500001X) to calculate expectations with respect to the invariant measure of an ergodic SDE. In that context, we study the (over-damped) Langevin equations with a strongly concave potential. We show that when appropriate contracting couplings for the numerical integrators are available, one can obtain a uniform-in-time estimate of the MLMC variance in contrast to the majority of the results in the MLMC literature. As a consequence, a root mean square error of $$mathcal {O}(varepsilon )$$ is achieved with $$mathcal {O}(varepsilon ^{-2})$$ complexity on par with Markov Chain Monte Carlo (MCMC) methods, which, however, can be computationally intensive when applied to large datasets. Finally, we present a multi-level version of the recently introduced stochastic gradient Langevin dynamics method (Welling and Teh, in: Proceedings of the 28th ICML, 2011) built for large datasets applications. We show that this is the first stochastic gradient MCMC method with complexity $$mathcal {O}(varepsilon ^{-2}|log {varepsilon }|^{3})$$, in contrast to the complexity $$mathcal {O}(varepsilon ^{-3})$$ of currently available methods. Numerical experiments confirm our theoretical findings. |
