{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,19]],"date-time":"2026-08-19T18:33:41Z","timestamp":1787164421954,"version":"3.56.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,9,10]],"date-time":"2019-09-10T00:00:00Z","timestamp":1568073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,9,10]],"date-time":"2019-09-10T00:00:00Z","timestamp":1568073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P003818\/1"],"award-info":[{"award-number":["EP\/P003818\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Stat Comput"],"published-print":{"date-parts":[[2020,5]]},"abstract":"Abstract<\/jats:title>\n \n We develop a framework that allows the use of the multi-level Monte Carlo (MLMC) methodology (Giles in Acta Numer. 24:259\u2013328, 2015.\n 10.1017\/S096249291500001X<\/jats:ext-link>\n ) 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\n \n \n $$\\mathcal {O}(\\varepsilon )$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is achieved with\n \n \n $$\\mathcal {O}(\\varepsilon ^{-2})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u03b5<\/mml:mi>\n \n -<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n 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\n \n \n $$\\mathcal {O}(\\varepsilon ^{-2}|\\log {\\varepsilon }|^{3})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u03b5<\/mml:mi>\n \n -<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n |<\/mml:mo>\n log<\/mml:mo>\n \u03b5<\/mml:mi>\n \n |<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , in contrast to the complexity\n \n \n $$\\mathcal {O}(\\varepsilon ^{-3})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u03b5<\/mml:mi>\n \n -<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of currently available methods. Numerical experiments confirm our theoretical findings.\n <\/jats:p>","DOI":"10.1007\/s11222-019-09890-0","type":"journal-article","created":{"date-parts":[[2019,9,10]],"date-time":"2019-09-10T06:04:00Z","timestamp":1568095440000},"page":"507-524","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Multi-level Monte Carlo methods for the approximation of invariant measures of stochastic differential equations"],"prefix":"10.1007","volume":"30","author":[{"given":"Michael B.","family":"Giles","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mateusz B.","family":"Majka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lukasz","family":"Szpruch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian J.","family":"Vollmer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3860-9167","authenticated-orcid":false,"given":"Konstantinos C.","family":"Zygalakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,9,10]]},"reference":[{"issue":"4","key":"9890_CR1","doi-asserted-by":"publisher","first-page":"1600","DOI":"10.1137\/130935616","volume":"52","author":"A Abdulle","year":"2014","unstructured":"Abdulle, A., Vilmart, G., Zygalakis, K.C.: High order numerical approximation of the invariant measure of ergodic SDEs. SIAM J. Numer. Anal. 52(4), 1600\u20131622 (2014). \nhttps:\/\/doi.org\/10.1137\/130935616","journal-title":"SIAM J. Numer. Anal."},{"issue":"3","key":"9890_CR2","doi-asserted-by":"publisher","first-page":"1726","DOI":"10.3150\/16-BEJ911","volume":"24","author":"S Agapiou","year":"2018","unstructured":"Agapiou, S., Roberts, G.O., Vollmer, S.J.: Unbiased Monte Carlo: posterior estimation for intractable\/infinite-dimensional models. Bernoulli 24(3), 1726\u20131786 (2018). \nhttps:\/\/doi.org\/10.3150\/16-BEJ911","journal-title":"Bernoulli"},{"issue":"4","key":"9890_CR3","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1214\/aoap\/1177004598","volume":"5","author":"D Duffie","year":"1995","unstructured":"Duffie, D., Glynn, P.: Efficient Monte Carlo simulation of security prices. Ann. Appl. Probab. 5(4), 897\u2013905 (1995)","journal-title":"Ann. Appl. Probab."},{"key":"9890_CR4","unstructured":"Durmus, A., Moulines, E.: High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm (2016). arXiv e-prints \narXiv:1605.01559"},{"key":"9890_CR5","unstructured":"Fang, W., Giles, M.B.: Adaptive Euler\u2013Maruyama method for SDEs with non-globally Lipschitz drift: Part I, finite time interval (2016). arXiv preprint \narXiv:1609.08101"},{"key":"9890_CR6","unstructured":"Fang, W., Giles, M.B.: Adaptive Euler-Maruyama method for SDEs with non-globally Lipschitz drift: Part II, infinite time interval (2017). arXiv preprint \narXiv:1703.06743"},{"issue":"1","key":"9890_CR7","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.jmaa.2018.12.032","volume":"476","author":"W Fang","year":"2019","unstructured":"Fang, W., Giles, M.B.: Multilevel Monte Carlo method for ergodic SDEs without contractivity. J. Math. Anal. Appl. 476(1), 149\u2013176 (2019). \nhttps:\/\/doi.org\/10.1016\/j.jmaa.2018.12.032","journal-title":"J. Math. Anal. Appl."},{"key":"9890_CR8","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1017\/S096249291500001X","volume":"24","author":"MB Giles","year":"2015","unstructured":"Giles, M.B.: Multilevel Monte Carlo methods. Acta Numer. 24, 259\u2013328 (2015). \nhttps:\/\/doi.org\/10.1017\/S096249291500001X","journal-title":"Acta Numer."},{"issue":"4","key":"9890_CR9","doi-asserted-by":"publisher","first-page":"1585","DOI":"10.1214\/13-AAP957","volume":"24","author":"MB Giles","year":"2014","unstructured":"Giles, M.B., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without L\u00e9vy area simulation. Ann. Appl. Probab. 24(4), 1585\u20131620 (2014). \nhttps:\/\/doi.org\/10.1214\/13-AAP957","journal-title":"Ann. Appl. Probab."},{"issue":"A","key":"9890_CR10","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1239\/jap\/1417528487","volume":"51","author":"Peter W. Glynn","year":"2014","unstructured":"Glynn, P.W., Rhee, C.H.: Exact estimation for Markov chain equilibrium expectations. J. Appl. Probab. 51, 377\u2013389 (2014). \nhttps:\/\/doi.org\/10.1239\/jap\/1417528487\n\n (Celebrating 50 Years of The Applied Probability Trust)","journal-title":"Journal of Applied Probability"},{"issue":"1\u20132","key":"9890_CR11","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s00440-009-0250-6","volume":"149","author":"M Hairer","year":"2011","unstructured":"Hairer, M., Mattingly, J.C., Scheutzow, M.: Asymptotic coupling and a general form of Harris\u2019 theorem with applications to stochastic delay equations. Probab. Theory Relat. Fields 149(1\u20132), 223\u2013259 (2011). \nhttps:\/\/doi.org\/10.1007\/s00440-009-0250-6","journal-title":"Probab. Theory Relat. Fields"},{"key":"9890_CR12","unstructured":"Has\u2019minski\u012d, R.Z.: Stochastic Stability of Differential Equations, Monographs and Textbooks on Mechanics of Solids and Fluids: Mechanics and Analysis, vol\/ 7. Sijthoff & Noordhoff, Alphen aan den Rijn\u2014Germantown, Md., translated from the Russian by D. Louvish (1980)"},{"issue":"1","key":"9890_CR13","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","volume":"57","author":"WK Hastings","year":"1970","unstructured":"Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1), 97\u2013109 (1970). \nhttps:\/\/doi.org\/10.1093\/biomet\/57.1.97","journal-title":"Biometrika"},{"issue":"1112","key":"9890_CR14","doi-asserted-by":"publisher","first-page":"v+99","DOI":"10.1090\/memo\/1112","volume":"236","author":"M Hutzenthaler","year":"2015","unstructured":"Hutzenthaler, M., Jentzen, A.: Numerical approximations of stochastic differential equations with non-globally Lipschitz continuous coefficients. Mem. Am. Math. Soc. 236(1112), v+99 (2015). \nhttps:\/\/doi.org\/10.1090\/memo\/1112","journal-title":"Mem. Am. Math. Soc."},{"issue":"2130","key":"9890_CR15","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1098\/rspa.2010.0348","volume":"467","author":"M Hutzenthaler","year":"2011","unstructured":"Hutzenthaler, M., Jentzen, A., Kloeden, P.E.: Strong and weak divergence in finite time of Euler\u2019s method for stochastic differential equations with non-globally Lipschitz continuous coefficients. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 467(2130), 1563\u20131576 (2011). \nhttps:\/\/doi.org\/10.1098\/rspa.2010.0348","journal-title":"Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci."},{"issue":"311","key":"9890_CR16","doi-asserted-by":"publisher","first-page":"1353","DOI":"10.1090\/mcom\/3146","volume":"87","author":"M Hutzenthaler","year":"2018","unstructured":"Hutzenthaler, M., Jentzen, A., Wang, X.: Exponential integrability properties of numerical approximation processes for nonlinear stochastic differential equations. Math. Comput. 87(311), 1353\u20131413 (2018). \nhttps:\/\/doi.org\/10.1090\/mcom\/3146","journal-title":"Math. Comput."},{"issue":"4","key":"9890_CR17","doi-asserted-by":"publisher","first-page":"2681","DOI":"10.1214\/105051605000000511","volume":"15","author":"A Kebaier","year":"2005","unstructured":"Kebaier, A.: Statistical Romberg extrapolation: a new variance reduction method and applications to option pricing. Ann. Appl. Probab. 15(4), 2681\u20132705 (2005). \nhttps:\/\/doi.org\/10.1214\/105051605000000511","journal-title":"Ann. Appl. Probab."},{"key":"9890_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12616-5","volume-title":"Numerical Solution of Stochastic Differential Equations","author":"P Kloeden","year":"1992","unstructured":"Kloeden, P., Platen, E.: Numerical Solution of Stochastic Differential Equations. Springer, Berlin (1992)"},{"key":"9890_CR19","unstructured":"Krylov, N.V.: Controlled Diffusion Processes, Stochastic Modelling and Applied Probability, vol. 14. Springer, Berlin (2009) (translated from the 1977 Russian original by A. B. Aries, Reprint of the 1980 edition)"},{"issue":"3","key":"9890_CR20","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1142\/S0219493703000838","volume":"8","author":"D Lamberton","year":"2002","unstructured":"Lamberton, D., Pag\u00e8s, G.: Recursive computation of the invariant distribution of a diffusion. Bernoulli 8(3), 367\u2013405 (2002). \nhttps:\/\/doi.org\/10.1142\/S0219493703000838","journal-title":"Bernoulli"},{"key":"9890_CR21","unstructured":"Majka, M.B., Mijatovi\u0107, A., Szpruch, L.: Non-asymptotic bounds for sampling algorithms without log-concavity (2018). arXiv e-prints \narXiv:1808.07105"},{"key":"9890_CR22","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.cam.2012.08.015","volume":"238","author":"X Mao","year":"2013","unstructured":"Mao, X., Szpruch, L.: Strong convergence and stability of implicit numerical methods for stochastic differential equations with non-globally Lipschitz continuous coefficients. J. Comput. Appl. Math. 238, 14\u201328 (2013a). \nhttps:\/\/doi.org\/10.1016\/j.cam.2012.08.015","journal-title":"J. Comput. Appl. Math."},{"issue":"1","key":"9890_CR23","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1080\/17442508.2011.651213","volume":"85","author":"X Mao","year":"2013","unstructured":"Mao, X., Szpruch, L.: Strong convergence rates for backward Euler-Maruyama method for non-linear dissipative-type stochastic differential equations with super-linear diffusion coefficients. Stochastics 85(1), 144\u2013171 (2013b). \nhttps:\/\/doi.org\/10.1080\/17442508.2011.651213","journal-title":"Stochastics"},{"issue":"2","key":"9890_CR24","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-4149(02)00150-3","volume":"101","author":"JC Mattingly","year":"2002","unstructured":"Mattingly, J.C., Stuart, A.M., Higham, D.J.: Ergodicity for SDEs and approximations: locally Lipschitz vector fields and degenerate noise. Stoch. Process Appl. 101(2), 185\u2013232 (2002). \nhttps:\/\/doi.org\/10.1016\/S0304-4149(02)00150-3","journal-title":"Stoch. Process Appl."},{"key":"9890_CR25","unstructured":"Nagapetyan, T., Duncan, A.B., Hasenclever, L., Vollmer, S.J., Szpruch, L., Zygalakis, K.: The True Cost of Stochastic Gradient Langevin Dynamics (2017). arXiv e-prints \narXiv:1706.02692"},{"key":"9890_CR26","unstructured":"Rhee, C.H., Glynn, P.W.: A new approach to unbiased estimation for SDE\u2019s. In: Proceedings of the Winter Simulation Conference, Winter Simulation Conference, WSC\u201912, pp. 17:1\u201317:7 (2012). \nhttp:\/\/dl.acm.org\/citation.cfm?id=2429759.2429780"},{"issue":"5","key":"9890_CR27","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1287\/opre.2015.1404","volume":"63","author":"CH Rhee","year":"2015","unstructured":"Rhee, C.H., Glynn, P.W.: Unbiased estimation with square root convergence for SDE models. Oper. Res. 63(5), 1026\u20131043 (2015). \nhttps:\/\/doi.org\/10.1287\/opre.2015.1404","journal-title":"Oper. Res."},{"issue":"4","key":"9890_CR28","doi-asserted-by":"publisher","first-page":"341","DOI":"10.2307\/3318418","volume":"2","author":"GO Roberts","year":"1996","unstructured":"Roberts, G.O., Tweedie, R.L.: Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli 2(4), 341\u2013363 (1996). \nhttps:\/\/doi.org\/10.2307\/3318418","journal-title":"Bernoulli"},{"issue":"4","key":"9890_CR29","doi-asserted-by":"publisher","first-page":"1120","DOI":"10.1137\/S0036142998337235","volume":"37","author":"T Shardlow","year":"2000","unstructured":"Shardlow, T., Stuart, A.M.: A perturbation theory for ergodic Markov chains and application to numerical approximations. SIAM J. Numer. Anal. 37(4), 1120\u20131137 (2000). \nhttps:\/\/doi.org\/10.1137\/S0036142998337235","journal-title":"SIAM J. Numer. Anal."},{"issue":"310","key":"9890_CR30","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1090\/mcom\/3219","volume":"87","author":"L Szpruch","year":"2018","unstructured":"Szpruch, L., Zhang, X.: $$V$$-integrability, asymptotic stability and comparison property of explicit numerical schemes for non-linear SDEs. Math. Comput. 87(310), 755\u2013783 (2018). \nhttps:\/\/doi.org\/10.1090\/mcom\/3219","journal-title":"Math. Comput."},{"issue":"2","key":"9890_CR31","first-page":"163","volume":"8","author":"D Talay","year":"2002","unstructured":"Talay, D.: Stochastic Hamiltonian systems: exponential convergence to the invariant measure, and discretization by the implicit Euler scheme. Markov Process Relat. Fields 8(2), 163\u2013198 (2002)","journal-title":"Markov Process Relat. Fields"},{"issue":"4","key":"9890_CR32","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1080\/07362999008809220","volume":"8","author":"D Talay","year":"1990","unstructured":"Talay, D., Tubaro, L.: Expansion of the global error for numerical schemes solving stochastic differential equations. Stoch. Anal. Appl. 8(4), 483\u2013509 (1990). \nhttps:\/\/doi.org\/10.1080\/07362999008809220","journal-title":"Stoch. Anal. Appl."},{"key":"9890_CR33","unstructured":"Teh, Y.W., Thiery, A.H., Vollmer, S.J.: Consistency and fluctuations for stochastic gradient Langevin dynamics. J. Mach. Learn. Res. 17, Paper No. 7, 33 (2016)"},{"key":"9890_CR34","unstructured":"Vollmer, S.J., Zygalakis, K.C., Teh, Y.W.: Exploration of the (non-)asymptotic bias and variance of stochastic gradient Langevin dynamics. J. Mach. Learn. Res. 17, Paper No. 159, 45 (2016)"},{"key":"9890_CR35","unstructured":"Welling, M., Teh, Y.W.: Bayesian learning via stochastic gradient Langevin dynamics. In: Proceedings of the 28th ICML (2011)"},{"issue":"1","key":"9890_CR36","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1137\/090762336","volume":"33","author":"KC Zygalakis","year":"2011","unstructured":"Zygalakis, K.C.: On the existence and the applications of modified equations for stochastic differential equations. SIAM J. Sci. Comput. 33(1), 102\u2013130 (2011). \nhttps:\/\/doi.org\/10.1137\/090762336","journal-title":"SIAM J. Sci. Comput."}],"container-title":["Statistics and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-019-09890-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11222-019-09890-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-019-09890-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T06:29:06Z","timestamp":1599719346000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11222-019-09890-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,10]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["9890"],"URL":"https:\/\/doi.org\/10.1007\/s11222-019-09890-0","relation":{},"ISSN":["0960-3174","1573-1375"],"issn-type":[{"value":"0960-3174","type":"print"},{"value":"1573-1375","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,10]]},"assertion":[{"value":"18 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}