Markov chain simulation for multilevel Monte Carlo

Ajay Jasra; Kody J. H. Law; Yaxian Xu

doi:10.3934/fods.2021004

Article Contents

2021, Volume 3, Issue 1: 27-47. Doi: 10.3934/fods.2021004

This issue Previous Article The rankability of weighted data from pairwise comparisons Next Article A topological approach to spectral clustering

Markov chain simulation for multilevel Monte Carlo

1.
Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal, 23955, KSA
2.
Department of Mathematics, University of Manchester, Manchester, M13 9PL, UK
3.
Department of Statistics and Applied Probability, National University of Singapore, Singapore, 117546, SG

^* Corresponding author
^* Corresponding author

Received: October 2020

Revised: January 2021

Early access: February 2021

Published: March 2021

Abstract / Introduction Full Text(HTML) Figure(2) Related Papers Cited by

Abstract

This paper considers a new approach to using Markov chain Monte Carlo (MCMC) in contexts where one may adopt multilevel (ML) Monte Carlo. The underlying problem is to approximate expectations w.r.t. an underlying probability measure that is associated to a continuum problem, such as a continuous-time stochastic process. It is then assumed that the associated probability measure can only be used (e.g. sampled) under a discretized approximation. In such scenarios, it is known that to achieve a target error, the computational effort can be reduced when using MLMC relative to i.i.d. sampling from the most accurate discretized probability. The ideas rely upon introducing hierarchies of the discretizations where less accurate approximations cost less to compute, and using an appropriate collapsing sum expression for the target expectation. If a suitable coupling of the probability measures in the hierarchy is achieved, then a reduction in cost is possible. This article focused on the case where exact sampling from such coupling is not possible. We show that one can construct suitably coupled MCMC kernels when given only access to MCMC kernels which are invariant with respect to each discretized probability measure. We prove, under verifiable assumptions, that this coupled MCMC approach in a ML context can reduce the cost to achieve a given error, relative to exact sampling. Our approach is illustrated on a numerical example.

Keywords:

Mathematics Subject Classification: Primary: 62C10, 65C05.

Citation:

Full Text(HTML)

Figure 1. Estimates of the Variance and Bias Rates

Download: Full-size image PowerPoint slide

Figure 2. Cost against MSE

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	S. Agapiou, J. M. Bardsley, O. Papaspiliopoulos and A. M. Stuart, Analysis of the Gibbs sampler for hierarchical inverse problems, SIAM/ASA J. Uncertain. Quantif., 2 (2014), 514–544. doi: 10.1137/130944229.
[2]	S. Agapiou, G. O. Roberts and S. J. Vollmer, Unbiased Monte Carlo: Posterior estimation for intractable/infinite-dimensional models, Bernoulli, 24 (2018), 1726–1786. doi: 10.3150/16-BEJ911.
[3]	C. Andrieu, A. Jasra, A. Doucet and P. Del Moral, On non-linear Markov chain Monte Carlo, Bernoulli, 17 (2011), 987–1014. doi: 10.3150/10-BEJ307.
[4]	A. Beskos, A. Jasra, K. Law, R. Tempone and Y. Zhou, Multilevel Sequential Monte Carlo samplers, Stochastic Process. Appl., 127 (2017), 1417-1440. doi: 10.1016/j.spa.2016.08.004.
[5]	A. Beskos, A. Jasra, K. Law, Y. Marzouk and Y. Zhou, Multilevel Sequential Monte Carlo samplers with dimension independent likelihood informed proposals, SIAM/ASA J. Uncertain. Quantif., 6 (2018), 762-786. doi: 10.1137/17M1120993.
[6]	N. Bou-Rabee, A. Eberle and R. Zimmer, Coupling and convergence for Hamiltonian Monte Carlo, Ann. Appl. Probab., 30 (2020), 1209-1250. doi: 10.1214/19-AAP1528.
[7]	A. Bouchard-Côté, S. J. Vollmer and A. Doucet, The bouncy particle sampler: A non-reversible rejection-free Markov chain Monte Carlo method, J. Amer. Statist. Assoc., 113 (2018), 855-867. doi: 10.1080/01621459.2017.1294075.
[8]	S. Chen, J. Dick and A. B. Owen, Consistency of Markov chain quasi-Monte Carlo on continuous state spaces, Ann. Statist., 39 (2011), 673–701. doi: 10.1214/10-AOS831.
[9]	P. Del Moral, A. Jasra, K. J. H. Law and Y. Zhou, Multilevel SMC samplers for normalizing constants., TOMACS, 27 (2017), article 20.
[10]	P. Diaconis and D. Freedman, Iterated random functions, SIAM Rev., 41 (1999), 45–76. doi: 10.1137/S0036144598338446.
[11]	T. J. Dodwell, C. Ketelsen, R. Scheichl and A. L. Teckentrup, A hierarchical multilevel Markov chain Monte Carlo algorithm with applications to uncertainty quantification in subsurface flow, SIAM/ASA J. Uncer. Quant., 3 (2015), 1075–1108. doi: 10.1137/130915005.
[12]	M. B. Giles, Multilevel Monte Carlo path simulation, Oper. Res., 56 (2008), 607–617. doi: 10.1287/opre.1070.0496.
[13]	M. B. Giles, Multilevel Monte Carlo methods, Acta Numer., 24 (2015), 259–328. doi: 10.1017/S096249291500001X.
[14]	P. W. Glynn and S. P. Meyn, A Lyapunov bound for solutions of the Poisson equation, Ann. Probab., 24 (1996), 916–931. doi: 10.1214/aop/1039639370.
[15]	A.-L. Haji-Ali, F. Nobile and R. Tempone, Multi-index Monte Carlo: When sparsity meets sampling, Numer. Math., 132 (2016), 767–806. doi: 10.1007/s00211-015-0734-5.
[16]	S. Heinrich, Multilevel Monte Carlo methods, In Large-Scale Scientific Computing, (eds. S. Margenov, J. Wasniewski & P. Yalamov), Springer: Berlin, 2001.
[17]	J. Heng and P. E. Jacob, Unbiased Hamiltonian Monte Carlo with couplings, Biometrika, 106 (2019), 287-302. doi: 10.1093/biomet/asy074.
[18]	V. H. Hoang, K. J. H. Law, and A. M. Stuart, Determining white noise forcing from Eulerian observations in the Navier-stokes equation, Stoch. Partial Differ. Equ. Anal. Comput., 2 (2014), 233–261. doi: 10.1007/s40072-014-0028-4.
[19]	V. H. Hoang, C. Schwab and A. M. Stuart, Complexity analysis of accelerated MCMC methods for Bayesian inversion, Inverse Problems, 29 (2013), 085010, 37 pp. doi: 10.1088/0266-5611/29/8/085010.
[20]	S. F. Jarner and R. L. Tweedie, Locally contracting iterated functions and stability of Markov chains, J. Appl. Probab., 38 (2001), 494–507. doi: 10.1239/jap/996986758.
[21]	A. Jasra, K. Kamatani, K. J. H. Law and Y. Zhou, Multilevel particle filters, SIAM J. Numer. Anal., 55 (2017), 3068–3096. doi: 10.1137/17M1111553.
[22]	A. Jasra, K. Kamatani, K. Law and Y. Zhou, Bayesian static parameter estimation for partially observed diffusions via multilevel Monte Carlo, SIAM J. Sci. Comp., 40 (2018), A887–A902. doi: 10.1137/17M1112595.
[23]	A. Jasra, K. Kamatani, K. J. H. Law and Y. Zhou, A multi-index markov Chain Monte Carlo method, Int. J. Uncertain. Quantif., 8 (2018), 61–73. doi: 10.1615/Int.J.UncertaintyQuantification.2018021551.
[24]	A. Jasra, K. Law and C. Suciu, Advanced multilevel Monte Carlo methods, Int. Stat. Rev., 88 (2020), 548–579. doi: 10.1111/insr.12365.
[25]	K. Law, A. Stuart and K. Zygalakis, Data Assimilation, Springer-Verlag, New York, 2015. doi: 10.1007/978-3-319-20325-6.
[26]	S. Meyn, and R. L. Tweedie, Markov Chains and Stochastic Stability, Second edition, CUP: Cambridge, 2009. doi: 10.1017/CBO9780511626630.
[27]	D. S. Oliver, A. C. Reynolds and N. Liu, Inverse Theory for Petroleum Reservoir Characterization and History Matching, Cambridge University Press, 2008.
[28]	C.-H. Rhee and P. W. Glynn, Unbiased estimation with square root convergence for SDE models, Oper. Res., 63 (2015), 1026–1043. doi: 10.1287/opre.2015.1404.
[29]	A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451–559. doi: 10.1017/S0962492910000061.