March  2021, 3(1): 27-47. doi: 10.3934/fods.2021004

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

Received  October 2020 Revised  January 2021 Published  February 2021

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.

Citation: Ajay Jasra, Kody J. H. Law, Yaxian Xu. Markov chain simulation for multilevel Monte Carlo. Foundations of Data Science, 2021, 3 (1) : 27-47. doi: 10.3934/fods.2021004
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

A. BeskosA. JasraK. LawR. Tempone and Y. Zhou, Multilevel Sequential Monte Carlo samplers, Stochastic Process. Appl., 127 (2017), 1417-1440.  doi: 10.1016/j.spa.2016.08.004.  Google Scholar

[5]

A. BeskosA. JasraK. LawY. 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.  Google Scholar

[6]

N. Bou-RabeeA. Eberle and R. Zimmer, Coupling and convergence for Hamiltonian Monte Carlo, Ann. Appl. Probab., 30 (2020), 1209-1250.  doi: 10.1214/19-AAP1528.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

P. Del Moral, A. Jasra, K. J. H. Law and Y. Zhou, Multilevel SMC samplers for normalizing constants., TOMACS, 27 (2017), article 20. Google Scholar

[10]

P. Diaconis and D. Freedman, Iterated random functions, SIAM Rev., 41 (1999), 45–76. doi: 10.1137/S0036144598338446.  Google Scholar

[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.  Google Scholar

[12]

M. B. Giles, Multilevel Monte Carlo path simulation, Oper. Res., 56 (2008), 607–617. doi: 10.1287/opre.1070.0496.  Google Scholar

[13]

M. B. Giles, Multilevel Monte Carlo methods, Acta Numer., 24 (2015), 259–328. doi: 10.1017/S096249291500001X.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

S. Heinrich, Multilevel Monte Carlo methods, In Large-Scale Scientific Computing, (eds. S. Margenov, J. Wasniewski & P. Yalamov), Springer: Berlin, 2001. Google Scholar

[17]

J. Heng and P. E. Jacob, Unbiased Hamiltonian Monte Carlo with couplings, Biometrika, 106 (2019), 287-302.  doi: 10.1093/biomet/asy074.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

K. Law, A. Stuart and K. Zygalakis, Data Assimilation, Springer-Verlag, New York, 2015. doi: 10.1007/978-3-319-20325-6.  Google Scholar

[26]

S. Meyn, and R. L. Tweedie, Markov Chains and Stochastic Stability, Second edition, CUP: Cambridge, 2009. doi: 10.1017/CBO9780511626630.  Google Scholar

[27] D. S. OliverA. C. Reynolds and N. Liu, Inverse Theory for Petroleum Reservoir Characterization and History Matching, Cambridge University Press, 2008.   Google Scholar
[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.  Google Scholar

[29]

A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451–559. doi: 10.1017/S0962492910000061.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

A. BeskosA. JasraK. LawR. Tempone and Y. Zhou, Multilevel Sequential Monte Carlo samplers, Stochastic Process. Appl., 127 (2017), 1417-1440.  doi: 10.1016/j.spa.2016.08.004.  Google Scholar

[5]

A. BeskosA. JasraK. LawY. 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.  Google Scholar

[6]

N. Bou-RabeeA. Eberle and R. Zimmer, Coupling and convergence for Hamiltonian Monte Carlo, Ann. Appl. Probab., 30 (2020), 1209-1250.  doi: 10.1214/19-AAP1528.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

P. Del Moral, A. Jasra, K. J. H. Law and Y. Zhou, Multilevel SMC samplers for normalizing constants., TOMACS, 27 (2017), article 20. Google Scholar

[10]

P. Diaconis and D. Freedman, Iterated random functions, SIAM Rev., 41 (1999), 45–76. doi: 10.1137/S0036144598338446.  Google Scholar

[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.  Google Scholar

[12]

M. B. Giles, Multilevel Monte Carlo path simulation, Oper. Res., 56 (2008), 607–617. doi: 10.1287/opre.1070.0496.  Google Scholar

[13]

M. B. Giles, Multilevel Monte Carlo methods, Acta Numer., 24 (2015), 259–328. doi: 10.1017/S096249291500001X.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

S. Heinrich, Multilevel Monte Carlo methods, In Large-Scale Scientific Computing, (eds. S. Margenov, J. Wasniewski & P. Yalamov), Springer: Berlin, 2001. Google Scholar

[17]

J. Heng and P. E. Jacob, Unbiased Hamiltonian Monte Carlo with couplings, Biometrika, 106 (2019), 287-302.  doi: 10.1093/biomet/asy074.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

K. Law, A. Stuart and K. Zygalakis, Data Assimilation, Springer-Verlag, New York, 2015. doi: 10.1007/978-3-319-20325-6.  Google Scholar

[26]

S. Meyn, and R. L. Tweedie, Markov Chains and Stochastic Stability, Second edition, CUP: Cambridge, 2009. doi: 10.1017/CBO9780511626630.  Google Scholar

[27] D. S. OliverA. C. Reynolds and N. Liu, Inverse Theory for Petroleum Reservoir Characterization and History Matching, Cambridge University Press, 2008.   Google Scholar
[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.  Google Scholar

[29]

A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451–559. doi: 10.1017/S0962492910000061.  Google Scholar

Figure 1.  Estimates of the Variance and Bias Rates
Figure 2.  Cost against MSE
[1]

Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems & Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81

[2]

Olli-Pekka Tossavainen, Daniel B. Work. Markov Chain Monte Carlo based inverse modeling of traffic flows using GPS data. Networks & Heterogeneous Media, 2013, 8 (3) : 803-824. doi: 10.3934/nhm.2013.8.803

[3]

Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3881-3903. doi: 10.3934/dcdsb.2018335

[4]

Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic & Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291

[5]

Jiakou Wang, Margaret J. Slattery, Meghan Henty Hoskins, Shile Liang, Cheng Dong, Qiang Du. Monte carlo simulation of heterotypic cell aggregation in nonlinear shear flow. Mathematical Biosciences & Engineering, 2006, 3 (4) : 683-696. doi: 10.3934/mbe.2006.3.683

[6]

Chjan C. Lim, Joseph Nebus, Syed M. Assad. Monte-Carlo and polyhedron-based simulations I: extremal states of the logarithmic N-body problem on a sphere. Discrete & Continuous Dynamical Systems - B, 2003, 3 (3) : 313-342. doi: 10.3934/dcdsb.2003.3.313

[7]

Joseph Nebus. The Dirichlet quotient of point vortex interactions on the surface of the sphere examined by Monte Carlo experiments. Discrete & Continuous Dynamical Systems - B, 2005, 5 (1) : 125-136. doi: 10.3934/dcdsb.2005.5.125

[8]

Mazyar Zahedi-Seresht, Gholam-Reza Jahanshahloo, Josef Jablonsky, Sedighe Asghariniya. A new Monte Carlo based procedure for complete ranking efficient units in DEA models. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 403-416. doi: 10.3934/naco.2017025

[9]

Masoumeh Dashti, Stephen Harris, Andrew Stuart. Besov priors for Bayesian inverse problems. Inverse Problems & Imaging, 2012, 6 (2) : 183-200. doi: 10.3934/ipi.2012.6.183

[10]

Johnathan M. Bardsley. Gaussian Markov random field priors for inverse problems. Inverse Problems & Imaging, 2013, 7 (2) : 397-416. doi: 10.3934/ipi.2013.7.397

[11]

Tan Bui-Thanh, Omar Ghattas. A scalable algorithm for MAP estimators in Bayesian inverse problems with Besov priors. Inverse Problems & Imaging, 2015, 9 (1) : 27-53. doi: 10.3934/ipi.2015.9.27

[12]

Kui Lin, Shuai Lu, Peter Mathé. Oracle-type posterior contraction rates in Bayesian inverse problems. Inverse Problems & Imaging, 2015, 9 (3) : 895-915. doi: 10.3934/ipi.2015.9.895

[13]

Ralf Banisch, Carsten Hartmann. A sparse Markov chain approximation of LQ-type stochastic control problems. Mathematical Control & Related Fields, 2016, 6 (3) : 363-389. doi: 10.3934/mcrf.2016007

[14]

Deng Lu, Maria De Iorio, Ajay Jasra, Gary L. Rosner. Bayesian inference for latent chain graphs. Foundations of Data Science, 2020, 2 (1) : 35-54. doi: 10.3934/fods.2020003

[15]

Junxiong Jia, Jigen Peng, Jinghuai Gao. Posterior contraction for empirical bayesian approach to inverse problems under non-diagonal assumption. Inverse Problems & Imaging, 2021, 15 (2) : 201-228. doi: 10.3934/ipi.2020061

[16]

Tan Bui-Thanh, Quoc P. Nguyen. FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems. Inverse Problems & Imaging, 2016, 10 (4) : 943-975. doi: 10.3934/ipi.2016028

[17]

T. J. Sullivan. Well-posed Bayesian inverse problems and heavy-tailed stable quasi-Banach space priors. Inverse Problems & Imaging, 2017, 11 (5) : 857-874. doi: 10.3934/ipi.2017040

[18]

Didi Lv, Qingping Zhou, Jae Kyu Choi, Jinglai Li, Xiaoqun Zhang. Nonlocal TV-Gaussian prior for Bayesian inverse problems with applications to limited CT reconstruction. Inverse Problems & Imaging, 2020, 14 (1) : 117-132. doi: 10.3934/ipi.2019066

[19]

Ralf Banisch, Carsten Hartmann. Addendum to "A sparse Markov chain approximation of LQ-type stochastic control problems". Mathematical Control & Related Fields, 2017, 7 (4) : 623-623. doi: 10.3934/mcrf.2017023

[20]

Samuel N. Cohen, Lukasz Szpruch. On Markovian solutions to Markov Chain BSDEs. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 257-269. doi: 10.3934/naco.2012.2.257

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]