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, 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]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[2]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[3]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[4]

Chih-Chiang Fang. Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020127

[5]

Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169

[6]

Liqin Qian, Xiwang Cao. Character sums over a non-chain ring and their applications. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020134

[7]

Min Li, Jiahua Zhang, Yifan Xu, Wei Wang. Effects of disruption risk on a supply chain with a risk-averse retailer. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021024

[8]

Wen-Bin Yang, Yan-Ling Li, Jianhua Wu, Hai-Xia Li. Dynamics of a food chain model with ratio-dependent and modified Leslie-Gower functional responses. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 2269-2290. doi: 10.3934/dcdsb.2015.20.2269

[9]

Benrong Zheng, Xianpei Hong. Effects of take-back legislation on pricing and coordination in a closed-loop supply chain. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021035

[10]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

[11]

Ian Schindler, Kyril Tintarev. Mountain pass solutions to semilinear problems with critical nonlinearity. Conference Publications, 2007, 2007 (Special) : 912-919. doi: 10.3934/proc.2007.2007.912

[12]

Valeria Chiado Piat, Sergey S. Nazarov, Andrey Piatnitski. Steklov problems in perforated domains with a coefficient of indefinite sign. Networks & Heterogeneous Media, 2012, 7 (1) : 151-178. doi: 10.3934/nhm.2012.7.151

[13]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446

[14]

M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072

[15]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065

[16]

Samir Adly, Oanh Chau, Mohamed Rochdi. Solvability of a class of thermal dynamical contact problems with subdifferential conditions. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 91-104. doi: 10.3934/naco.2012.2.91

[17]

Elvise Berchio, Filippo Gazzola, Dario Pierotti. Nodal solutions to critical growth elliptic problems under Steklov boundary conditions. Communications on Pure & Applied Analysis, 2009, 8 (2) : 533-557. doi: 10.3934/cpaa.2009.8.533

[18]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002

[19]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[20]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263

 Impact Factor: 

Metrics

  • PDF downloads (19)
  • HTML views (42)
  • Cited by (0)

Other articles
by authors

[Back to Top]