Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2009 | public
Book Section - Chapter

Computational Complexity of Metropolis-Hastings Methods in High Dimensions


This article contains an overview of the literature concerning the computational complexity of Metropolis-Hastings based MCMC methods for sampling probability measures on ℝ^d, when the dimension d is large. The material is structured in three parts addressing, in turn, the following questions: (i) what are sensible assumptions to make on the family of probability measures indexed by d? (ii) what is known concerning computational complexity for Metropolis-Hastings methods applied to these families? (iii) what remains open in this area?

Additional Information

© 2009 Springer-Verlag Berlin Heidelberg. This article describes work overviewed in the second author's plenary lecture at MCQMC08, held in Montreal in July 2008. The authors are grateful to the organizers of this conference for the opportunity to present this material in lectured and written form. The authors are also indebted to all coauthors on papers listed in the bibliography, as well as to Jeff Rosenthal, for helpful discussions relating to the material in this paper. They are grateful to the European Research Council, the Engineering and Physical Sciences Research Council (UK) and the Office of Naval Research (USA) for funding all of their coauthored research referenced in the bibliography.

Additional details

August 20, 2023
March 5, 2024