Maximal Couplings of the Metropolis-Hastings Algorithm

Guanyang Wang, John O’Leary, Pierre Jacob
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:1225-1233, 2021.

Abstract

Couplings play a central role in the analysis of Markov chain Monte Carlo algorithms and appear increasingly often in the algorithms themselves, e.g. in convergence diagnostics, parallelization, and variance reduction techniques. Existing couplings of the Metropolis-Hastings algorithm handle the proposal and acceptance steps separately and fall short of the upper bound on one-step meeting probabilities given by the coupling inequality. This paper introduces maximal couplings which achieve this bound while retaining the practical advantages of current methods. We consider the properties of these couplings and examine their behavior on a selection of numerical examples.

Cite this Paper


BibTeX
@InProceedings{pmlr-v130-wang21d, title = { Maximal Couplings of the Metropolis-Hastings Algorithm }, author = {Wang, Guanyang and O'Leary, John and Jacob, Pierre}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {1225--1233}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/wang21d/wang21d.pdf}, url = {https://proceedings.mlr.press/v130/wang21d.html}, abstract = { Couplings play a central role in the analysis of Markov chain Monte Carlo algorithms and appear increasingly often in the algorithms themselves, e.g. in convergence diagnostics, parallelization, and variance reduction techniques. Existing couplings of the Metropolis-Hastings algorithm handle the proposal and acceptance steps separately and fall short of the upper bound on one-step meeting probabilities given by the coupling inequality. This paper introduces maximal couplings which achieve this bound while retaining the practical advantages of current methods. We consider the properties of these couplings and examine their behavior on a selection of numerical examples. } }
Endnote
%0 Conference Paper %T Maximal Couplings of the Metropolis-Hastings Algorithm %A Guanyang Wang %A John O’Leary %A Pierre Jacob %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-wang21d %I PMLR %P 1225--1233 %U https://proceedings.mlr.press/v130/wang21d.html %V 130 %X Couplings play a central role in the analysis of Markov chain Monte Carlo algorithms and appear increasingly often in the algorithms themselves, e.g. in convergence diagnostics, parallelization, and variance reduction techniques. Existing couplings of the Metropolis-Hastings algorithm handle the proposal and acceptance steps separately and fall short of the upper bound on one-step meeting probabilities given by the coupling inequality. This paper introduces maximal couplings which achieve this bound while retaining the practical advantages of current methods. We consider the properties of these couplings and examine their behavior on a selection of numerical examples.
APA
Wang, G., O’Leary, J. & Jacob, P.. (2021). Maximal Couplings of the Metropolis-Hastings Algorithm . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:1225-1233 Available from https://proceedings.mlr.press/v130/wang21d.html.

Related Material