Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings

Juan P. Madrigal-Cianci, Fabio Nobile, Raul Tempone

Research output: Contribution to journalArticlepeer-review


In this work, we present, analyze, and implement a class of multilevel Markov chain Monte Carlo (ML-MCMC) algorithms based on independent Metropolis–Hastings proposals for Bayesian inverse problems. In this context, the likelihood function involves solving a complex differential model, which is then approximated on a sequence of increasingly accurate discretizations. The key point of this algorithm is to construct highly coupled Markov chains together with the standard multilevel Monte Carlo argument to obtain a better cost-tolerance complexity than a single-level MCMC algorithm. Our method extends the ideas of Dodwell et al., [SIAM/ASA J. Uncertain. Quantif., 3 (2015), pp. 1075–1108] to a wider range of proposal distributions. We present a thorough convergence analysis of the ML-MCMC method proposed, and show, in particular, that (i) under some mild conditions on the (independent) proposals and the family of posteriors, there exists a unique invariant probability measure for the coupled chains generated by our method, and (ii) that such coupled chains are uniformly ergodic. We also generalize the cost-tolerance theorem of Dodwell et al. to our wider class of ML-MCMC algorithms. Finally, we propose a self-tuning continuation-type ML-MCMC algorithm. The presented method is tested on an array of academic examples, where some of our theoretical results are numerically verified. These numerical experiments evidence how our extended ML-MCMC method is robust when targeting some pathological posteriors, for which some of the previously proposed ML-MCMC algorithms fail.
Original languageEnglish (US)
Pages (from-to)91-138
Number of pages48
JournalSIAM/ASA Journal on Uncertainty Quantification
Issue number1
StatePublished - Mar 3 2023

Bibliographical note

KAUST Repository Item: Exported on 2023-03-06
Acknowledged KAUST grant number(s): OSR-2015-CRG4-258
Acknowledgements: This project was partially funded by the King Abdullah University of Science and Technology through grant OSR-2015-CRG4-2584-01:   ``Advanced Multi-Level sampling techniques for Bayesian Inverse Problems with applications to subsurface." The first and second authors  also acknowledge support from the Swiss Data Science Center(SDSC) through grant P18-09. The third author acknowledges support from  the  Alexander von Humboldt foundation. The authors would like to extend their gratitude to the anonymous reviewers whose comments significantly improved the quality of this manuscript. The authors would also like to thank Dr. Sebastian Krumscheid, Dr. Panagiotis Tsilifis, and Dr. Anamika Pandey for fruitful discussions during the very early stages of this work.


Dive into the research topics of 'Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings'. Together they form a unique fingerprint.

Cite this