Wormhole Hamiltonian Monte Carlo

Shiwei Lan, Jeffrey Streets, Babak Shahbaba

Abstract

In machine learning and statistics, probabilistic inference involving multimodal distributions is quite difficult. This is especially true in high dimensional problems, where most existing algorithms cannot easily move from one mode to another. To address this issue, we propose a novel Bayesian inference approach based on Markov Chain Monte Carlo. Our method can effectively sample from multimodal distributions, especially when the dimension is high and the modes are isolated. To this end, it exploits and modifies the Riemannian geometric properties of the target distribution to create wormholes connecting modes in order to facilitate moving between them. Further, our proposed method uses the regeneration technique in order to adapt the algorithm by identifying new modes and updating the network of wormholes without affecting the stationary distribution. To find new modes, as opposed to rediscovering those previously identified, we employ a novel mode searching algorithm that explores a residual energy function obtained by subtracting an approximate Gaussian mixture density (based on previously discovered modes) from the target density function.

Introduction

Sampling from complex, multimodal distributions is a fundamental challenge in Bayesian inference. While Hamiltonian Monte Carlo (HMC) is highly effective at exploring local probability landscapes by simulating Hamiltonian dynamics, it frequently becomes trapped in local modes. When high-probability regions are separated by vast "valleys" of low probability, a standard HMC sampler rarely gains the energy required to traverse these barriers, leading to poor mixing and biased estimates.

Wormhole Hamiltonian Monte Carlo (WHMC) addresses this by modifying the geometry of the state space. By creating "wormholes" that connect distant modes, the algorithm allows the sampler to tunnel through high-energy barriers that would otherwise be impassable.

The Wormhole Approach

The core innovation of WHMC is the modification of the underlying Riemannian metric to "shorten" the distance between isolated modes.

  1. The Wormhole Metric: In HMC, the mass matrix (Riemannian metric) $G$ determines the sampler's movement. WHMC defines a new metric, $G_W$, that drastically reduces the effective distance along a straight line connecting two modes. Within this "wormhole tube," the sampler perceives the modes as being adjacent.
  2. External Vector Fields: To ensure the sampler traverses the wormhole efficiently, an external vector field is added to "push" the particle along the wormhole's axis.
  3. Auxiliary Dimensions: To prevent wormholes from distorting the natural physics of the target distribution, the authors introduce an extra dimension ($D+1$). This creates a "mirror world" where the wormholes reside, allowing the sampler to jump into the mirror world, travel through a wormhole, and emerge in a different mode in the original space.
Comparison of HMC and WHMC on a bimodal distribution. Standard HMC (left) remains trapped in a single mode, while WHMC (right) successfully explores both.

Adaptive Mode Discovery

WHMC does not require prior knowledge of mode locations. Instead, it employs an adaptive discovery system based on the regeneration technique. This allows the algorithm to periodically pause and search for new modes without violating the stationary distribution requirements of MCMC.

To avoid rediscovering known modes, the algorithm explores a residual energy function. By subtracting an approximate Gaussian mixture density (representing previously discovered modes) from the target density, the sampler can focus its search on unexplored regions of the probability landscape. As new modes are found, the network of wormholes is updated dynamically.

Wormhole network (left) and resulting samples (right) in a complex multimodal landscape. The dashed lines represent the connections facilitating transitions between isolated modes.

Experimental Validation

The authors evaluated WHMC on several challenging benchmarks, including high-dimensional Gaussian mixtures (up to $D=100$) and Sensor Network Localization ($D=16$).

  • Scalability: In 100-dimensional tests, WHMC demonstrated significantly lower Relative Error of Mean (REM) compared to state-of-the-art competitors like Regeneration Darting Monte Carlo (RDMC). While RDMC's performance degraded with dimensionality, WHMC remained robust.
  • Exploration: In the Sensor Network Localization task—notorious for geometric ambiguities and multiple modes—WHMC successfully identified all posterior modes, whereas competing methods frequently missed modes entirely.

Conclusion

WHMC represents a significant advancement in multimodal sampling. By leveraging Riemannian geometry to create shortcuts between modes and employing an adaptive discovery mechanism, it overcomes the "waiting time" problem that plagues traditional MCMC in high dimensions. While it introduces additional hyperparameters and computational overhead for Jacobian calculations, the gains in mixing efficiency and exploration accuracy make it a powerful tool for complex Bayesian inference tasks.

Summary updated

Abstract

In machine learning and statistics, probabilistic inference involving multimodal distributions is quite difficult. This is especially true in high dimensional problems, where most existing algorithms cannot easily move from one mode to another. To address this issue, we propose a novel Bayesian inference approach based on Markov Chain Monte Carlo. Our method can effectively sample from multimodal distributions, especially when the dimension is high and the modes are isolated. To this end, it exploits and modifies the Riemannian geometric properties of the target distribution to create \emph{wormholes} connecting modes in order to facilitate moving between them. Further, our proposed method uses the regeneration technique in order to adapt the algorithm by identifying new modes and updating the network of wormholes without affecting the stationary distribution. To find new modes, as opposed to rediscovering those previously identified, we employ a novel mode searching algorithm that explores a \emph{residual energy} function obtained by subtracting an approximate Gaussian mixture density (based on previously discovered modes) from the target density function.
BibTeX
@inproceedings{lan2014wormhole,
  author = {Shiwei Lan and Jeffrey Streets and Babak Shahbaba},
  title = {{Wormhole Hamiltonian Monte Carlo}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9006},
}
Figure