Involutive MCMC: a Unifying Framework

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

Markov Chain Monte Carlo (MCMC) is the workhorse of Bayesian inference, allowing researchers to sample from complex, high-dimensional probability distributions. However, the field has historically been fragmented. Researchers have developed dozens of specialized algorithms—such as Hamiltonian Monte Carlo (HMC), Gibbs sampling, and Reversible-Jump MCMC—that often seem mathematically distinct.

Furthermore, many traditional MCMC methods are reversible. This means the sampler has no "momentum" and frequently backtracks, leading to slow exploration (or "mixing") of the target distribution.

This paper introduces Involutive MCMC (iMCMC), a mathematical framework that unifies this vast array of algorithms. By framing these disparate methods as deterministic "involutions" acting on an augmented state space, the authors provide a unified language for MCMC and a systematic toolbox to turn slow, reversible algorithms into fast, irreversible ones that efficiently traverse the state space.

The Involutive MCMC Framework

The core innovation of the paper is the Involutive MCMC kernel. Instead of sampling directly from a target distribution $p(x)$, the framework augments the state with an auxiliary variable $v$ (analogous to momentum in physics).

The iMCMC algorithm follows three primary steps:

  1. Augment: Sample an auxiliary variable $v$ from a conditional distribution $p(v|x)$.
  2. Transform: Apply a deterministic function $f(x, v)$ that is an involution. An involution is a function that is its own inverse, meaning applying it twice brings you back to the starting point ($f(f(x,v)) = (x,v)$).
  3. Accept/Reject: Use a generalized Metropolis-Hastings step to decide whether to accept the new state or remain in the current one.
Trajectory of an irreversible MCMC sampler maintaining a persistent direction until a rejection occurs.

Key Insights and "Tricks"

The authors demonstrate that nearly every popular MCMC method is simply a specific choice of an involution $f$ and an auxiliary distribution $p(v|x)$. For example, standard Metropolis-Hastings is just a "swap" involution, while HMC is a "leap-frog" integrator followed by a momentum flip.

To help researchers build complex, novel samplers, the paper outlines several design principles or "Tricks":

  • Smart Auxiliary Spaces: Utilizing mixtures to handle intractable integrals.
  • Smart Deterministic Maps: Leveraging "flows" (like neural networks) or Hamiltonian dynamics as the involution.
  • Smart Compositions (Persistent Direction): Composing multiple reversible kernels to create an irreversible chain. By simply not resetting the auxiliary variable every time, the sampler maintains a "persistent direction." It keeps moving forward until it hits a "wall" (a rejection), at which point it reverses. This prevents the sampler from uselessly doubling back on itself, yielding "irreversibility for free."
  • Neural Network Integration: The framework provides a mathematically rigorous way to plug learnable "normalizing flows" (like NICE) into MCMC, allowing the sampler to learn the geometry of the distribution.

Experimental Results

To validate the framework, the authors created irreversible versions of existing algorithms (Irr-MALA and Irr-NICE-MC) and tested them on several datasets:

  • MoG2: A synthetic mixture of two 2D Gaussian distributions, designed to test the sampler's ability to jump between distinct modes.
  • Bayesian Logistic Regression: Real-world classification tasks using the Australian, German, and Heart datasets from the UCI repository.

Performance was measured using Effective Sample Size (ESS)—a metric indicating how many truly "independent" samples the chain produces—and ESS per second to account for computational overhead.

Effective Sample Size (ESS) and ESS per second across various datasets.

The irreversible modifications consistently outperformed their reversible counterparts across almost all tasks with negligible computational overhead:

  • Mode Hopping: On the bimodal MoG2 task, the irreversible version (Irr-NICE-MC) achieved an ESS of 1.643, nearly double the 0.852 of the original reversible A-NICE-MC version.
  • Efficiency Gains: On the Heart dataset, Irr-NICE-MC proved significantly more efficient, delivering 324 ESS/sec compared to 241 ESS/sec for the standard version.

Limitations and Future Work

While iMCMC provides a powerful unifying theory, it does come with practical considerations. Adding auxiliary variables inherently increases the dimensionality of the state space. If this auxiliary space is poorly chosen, it can lead to higher variance in the estimates. Furthermore, while the framework dictates how to use an involution, it does not automatically identify which involution is optimal for a specific, unknown target distribution.

Looking forward, the authors suggest that this framework could bridge the gap between traditional MCMC and flow-based generative models used in unsupervised learning. This intersection could pave the way for "deterministic samplers" that behave like chaotic dynamical systems, further accelerating the pace of Bayesian inference.

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 algorit...
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