Involutive MCMC: a Unifying Framework

Kirill Neklyudov, Max Welling, Evgenii Egorov, Dmitry P. Vetrov

Abstract

Markov Chain Monte Carlo (MCMC) is a computational approach to fundamental problems such as inference, integration, optimization, and simulation. The field has developed a broad spectrum of algorithms, varying in the way they are motivated, the way they are applied and how efficiently they sample. Despite all the differences, many of them share the same core principle, which we unify as the Involutive MCMC (iMCMC) framework. Building upon this, we describe a wide range of MCMC algorithms in terms of iMCMC, and formulate a number of "tricks" which one can use as design principles for developing new MCMC algorithms. Thus, iMCMC provides a unified view of many known MCMC algorithms, which facilitates the derivation of powerful extensions. We demonstrate the latter with two examples where we transform known reversible MCMC algorithms into more efficient irreversible ones.

Introduction

Markov Chain Monte Carlo (MCMC) is the workhorse of Bayesian inference, allowing us to sample from complex, high-dimensional probability distributions. However, the field is fragmented. Dozens of algorithms exist, each with its own complex proof of validity. Furthermore, most traditional MCMC methods are reversible, meaning the chain is just as likely to move from point A to B as from B to A. While easier to analyze, reversible chains often suffer from "random walk behavior," where they slowly diffuse through the space.

Irreversible chains can move much faster and explore more efficiently, but they are notoriously difficult to design and prove correct. This paper introduces Involutive MCMC (iMCMC), a powerful mathematical framework that unifies a vast array of popular MCMC algorithms—from Metropolis-Hastings to Hamiltonian Monte Carlo—under a single umbrella. By framing these algorithms as compositions of "involutions" (functions that are their own inverse), the authors provide a toolkit of design principles to easily build highly efficient samplers.

The iMCMC Framework

The core idea of iMCMC relies on two main components:

  1. Auxiliary Variables: The state space is expanded (e.g., adding "momentum" to "position").
  2. Involutions: A deterministic map $f$ is used such that applying it twice brings you back to the start ($f(f(x)) = x$).

A simple transition kernel—proposing a move using an involution and accepting/rejecting it with a specific ratio—is enough to keep the target distribution invariant. This framework acts as a universal language for the field, encompassing a wide variety of existing methods.

Table 1: A wide range of MCMC algorithms unified under the iMCMC framework.

The authors categorize existing MCMC knowledge into six "Tricks":

  • Tricks 1 & 2 (Mixtures and State-Dependence): Handling mixture distributions and choosing different involutions based on the current state.
  • Tricks 3 & 4 (Flow-Based Integration): Building complex involutions using non-involutive bijections like neural network flows (e.g., NICE).
  • Tricks 5 & 6 (Designing Irreversibility): By composing reversible iMCMC kernels and not resampling auxiliary variables at every step, one creates a "persistent" motion that drives the sampler forward, preventing it from doubling back.

Experimental Evaluation

The authors evaluated their framework on synthetic tasks like MoG2 (a bimodal mixture of Gaussians) and real-world Bayesian Logistic Regression datasets: Australian, German, and Heart. They demonstrated the power of iMCMC by creating irreversible versions of standard algorithms: Irr-MALA (Irreversible Metropolis-Adjusted Langevin Algorithm) and Irr-NICE-MC.

Table 2: Comparison of Effective Sample Size (ESS) and ESS per second across various datasets.

Key Results

  • Efficiency Gains: On the bimodal MoG2 task, the irreversible Irr-MALA achieved an Effective Sample Size (ESS) of 0.027, nearly 4x better than standard MALA (0.007).
  • Flow-Based Superiority: Irr-NICE-MC significantly outperformed its reversible counterpart (A-NICE-MC). On the Heart dataset, it achieved an ESS per second of 324 compared to 241 for the reversible version.
  • Minimal Overhead: The transition from reversible to irreversible provided these gains with negligible computational cost, as shown in the "ESS per second" metrics.

Conclusion

iMCMC provides a unified view of many known MCMC algorithms, facilitating the derivation of powerful extensions. While performance depends on hyperparameters and ergodicity must still be carefully considered, the framework naturally accommodates "learned" samplers and provides a clear path to designing efficient irreversible chains. Future work may explore deep connections to chaotic iterated maps or use these kernels to improve unsupervised learning models.

Summary updated

Abstract

Markov Chain Monte Carlo (MCMC) is a computational approach to fundamental problems such as inference, integration, optimization, and simulation. The field has developed a broad spectrum of algorithms, varying in the way they are motivated, the way they are applied and how efficiently they sample. Despite all the differences, many of them share the same core principle, which we unify as the Involutive MCMC (iMCMC) framework. Building upon this, we describe a wide range of MCMC algorithms in terms of iMCMC, and formulate a number of "tricks" which one can use as design principles for developing new MCMC algorithms. Thus, iMCMC provides a unified view of many known MCMC algorithms, which facilitates the derivation of powerful extensions. We demonstrate the latter with two examples where we transform known reversible MCMC algorithms into more efficient irreversible ones.
BibTeX
@inproceedings{neklyudov2020involutive,
  author = {Kirill Neklyudov and Max Welling and Evgenii Egorov and Dmitry P. Vetrov},
  title = {{Involutive MCMC: a Unifying Framework}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=3Ooma7AsO86},
}
Figure