Informed Proposals for Local MCMC in Discrete Spaces

Abstract

There is a lack of methodological results to design efficient Markov chain Monte Carlo ( MCMC) algorithms for statistical models with discrete-valued high-dimensional parameters. Motivated by this consideration, we propose a simple framework for the design of informed MCMC proposals (i.e., Metropolis–Hastings proposal distributions that appropriately incorporate local information about the target) which is naturally applicable to discrete spaces. Using Peskun-type comparisons of Markov kernels, we explicitly characterize the class of asymptotically optimal proposal distributions under this framework, which we refer to as locally balanced proposals. The resulting algorithms are straightforward to implement in discrete spaces and provide orders of magnitude improvements in efficiency compared to alternative MCMC schemes, including discrete versions of Hamiltonian Monte Carlo. Simulations are performed with both simulated and real datasets, including a detailed application to Bayesian record linkage. A direct connection with gradient-based MCMC suggests that locally balanced proposals can be seen as a natural way to extend the latter to discrete spaces. Supplementary materials for this article are available online.

Keywords:

• Bayesian discrete models
• Bayesian record linkage
• Informed Metropolis–Hastings schemes
• Markov chain Monte Carlo
• Peskun ordering

Supplementary Material

A - Proofs: contains proofs of Theorems 1-6 and Proposition 1. (pdf)

B - Details on simulations: additional details and results for the discussion in Section 4.2, the simulation studies in Section 6 and the Bayesian record linkage application in Section 7. (pdf)

C - Code: R code to reproduce the simulation studies in Section 6. (zip)

Acknowledgments

The author is grateful to Samuel Livingstone, Omiros Papaspiliopoulos and Gareth Roberts for stimulating discussions, and thanks the Editor, Associate Editor and referees for useful and constructive comments.

Additional information

Funding

This work was supported in part by an Engineering and Physical Sciences Research Council (EPSRC) Doctoral Prize fellowship and by the European Research Council (ERC) through StG “N-BNP” 306406.