Maximal Couplings of the Metropolis-Hastings Algorithm

Guanyang Wang, John O'Leary, Pierre JacobAISTATS 2021 · OpenReview

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.

Introduction

In Markov chain Monte Carlo (MCMC), "coupling" involves running two distinct Markov chains simultaneously such that they eventually "meet" (reach the same state) and remain together thereafter. This technique is foundational for parallelization, variance reduction, and the creation of unbiased estimators for complex target distributions.

The theoretical gold standard for any coupling is to be maximal, meaning it achieves the highest possible probability of the two chains meeting in a single step, as constrained by the "coupling inequality." Historically, the standard approach for the Metropolis-Hastings (MH) algorithm—the "Status Quo" ($P_{SQ}$)—couples the proposal and acceptance steps independently. While computationally simple, this approach consistently falls short of the theoretical maximum meeting probability. This research introduces implementable maximal couplings that require only the standard information available to an MH algorithm: the ability to evaluate target and proposal densities.

Conceptual Framework: The Coupling Inequality

The core challenge lies in maximizing the overlap between the transition kernels of two chains starting at different points. The coupling inequality states that for any two probability measures, the probability of a meeting is bounded by the total variation distance between them.

Visualizing the overlap and mapping of transition densities in a maximal coupling.

As shown in the figure above, the transition densities $f(x, z)$ and $f(y, z)$ can be decomposed into overlapping (C) and non-overlapping (A, B) regions. A maximal coupling ensures that if a meeting does not occur within the overlapping region C, the chains are mapped to the remaining probability mass in a way that preserves the marginal distributions while maximizing the probability of future meetings.

Proposed Methods

The authors introduce three "implementable" maximal couplings that function as "black-box" solutions for existing MH setups:

  1. $P_{MI}$ (Full-kernel with Independent Residuals): This treats the entire MH transition as a single distribution. It uses a rejection sampling approach to force a meeting. If the first chain's move does not result in a meeting, the second chain's move is sampled independently from a "residual" distribution.
  2. $P_{MR}$ (Full-kernel with Reflection Residuals): Similar to $P_{MI}$, but utilizes a "reflection" technique for residuals. This encourages chains to move toward each other even when they fail to meet, which is critical for maintaining performance in high-dimensional spaces.
  3. $P_C$ (Coupled Transitions from Coupled Proposals): This method uses a clever Bernoulli coupling in the acceptance step to ensure the overall transition is maximal. It is computationally more efficient than the full-kernel versions as it avoids the overhead of rejection sampling loops.
Algorithm 3: Drawing from the maximal coupling $P_{MI}$ using rejection sampling.

Key Insights and Results

The Efficiency of Maximality

The authors demonstrate that coupling the components of an algorithm (proposal then acceptance) is mathematically guaranteed to be less efficient than coupling the whole transition at once. In a 1D Biased Random Walk example, maximal couplings reduced the average meeting time from approximately 75 iterations to 60 iterations.

Scaling and Dimensionality

A significant finding is that maximality alone is insufficient in high dimensions. In a 100-dimensional multivariate normal target study, the independent residual version ($P_{MI}$) saw meeting times explode exponentially. However, the reflection-based version ($P_{MR}$) maintained strong "contraction," keeping the chains close enough to eventually meet. This highlights that how chains fail to meet is as important as the probability that they do meet.

Practical Implementation

The $P_C$ algorithm provides the benefits of maximality without the computational "while-loop" overhead of rejection sampling. This makes it the most viable candidate for integration into existing MCMC software and high-performance computing environments.

Conclusion

By closing the gap between the "Status Quo" and the theoretical coupling inequality, these maximal couplings significantly improve the efficiency of unbiased MCMC estimators. While the "contraction" problem in high dimensions remains sensitive to the geometry of the proposal distribution, the introduction of $P_{MR}$ and $P_C$ provides a robust framework for future developments in non-convex landscapes and non-Markovian couplings.

Summary updated

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.
BibTeX
@inproceedings{wang2021maximal,
  author = {Guanyang Wang and John O'Leary and Pierre Jacob},
  title = {{Maximal Couplings of the Metropolis-Hastings Algorithm}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=86KgUUCfQa},
}

Loading related content...

Figure