Wormhole Hamiltonian Monte Carlo

Shiwei Lan, Jeffrey Streets, Babak Shahbaba

Introduction

In Bayesian inference, the ability to sample from complex posterior distributions is fundamental. While Hamiltonian Monte Carlo (HMC) has become a standard tool due to its efficiency in exploring local geometry, it faces a significant challenge: multimodality. In landscapes where high-probability regions (modes) are separated by vast "valleys" of low probability, standard HMC samplers often lack the kinetic energy required to traverse these barriers. Consequently, the sampler becomes trapped in a single mode, leading to biased estimates and incomplete posterior exploration.

Standard HMC samplers often fail to transition between isolated modes, resulting in incomplete exploration of the target distribution.

Methodology: The Wormhole Approach

To overcome the limitations of traditional HMC, we introduce Wormhole Hamiltonian Monte Carlo (WHMC). This algorithm leverages Riemannian geometry to create "shortcuts" between disparate modes, effectively folding the probability landscape.

Geometric Warping and Mirror Worlds

The core innovation of WHMC is the modification of the Riemannian metric $G(\theta)$. By defining a metric that "shortens" the distance along specific paths between modes to near zero, the sampler can transition between them with minimal energy expenditure. To ensure these shortcuts do not interfere with local exploration, WHMC utilizes an auxiliary "mirror" dimension. This allows the sampler to "jump" into a mirror world, travel via a wormhole to a new mode's location, and return to the primary parameter space.

Adaptive Mode Discovery

Unlike many multimodal samplers that require prior knowledge of mode locations, WHMC can discover them on the fly. Using a regeneration technique, the algorithm periodically pauses to explore a "residual energy function"—the target density minus the approximations of already discovered modes. When a new mode is found, a new wormhole is dynamically added to the network.

WHMC constructs a network of paths (left) that warp the geometry to connect modes, enabling the sampler to fully capture the distribution (right).

Experimental Evaluation

The performance of WHMC was evaluated across several benchmarks:

  • 2D Toy Posterior: Used to visualize the jumping behavior and the formation of the wormhole network.
  • High-Dimensional Gaussian Mixtures: Mixtures of 10 Gaussians in up to $D=100$ dimensions, testing the algorithm's robustness against the curse of dimensionality.
  • Sensor Network Localization: A $D=16$ dimensional problem involving inferring sensor locations from noisy distance data, which naturally produces multiple valid geographic configurations.

Key Results and Discussion

WHMC demonstrates superior performance in high-dimensional settings. In the 100-dimensional Gaussian mixture test, WHMC maintained a low Relative Error of Mean (REM), whereas competing methods like Regeneration Darting Monte Carlo (RDMC) failed to transition between modes. Similarly, in the Sensor Network Localization problem, WHMC achieved a significantly lower REM (0.02) compared to RDMC (0.13) within a fixed time budget of 500 seconds.

The adaptive version of the algorithm successfully mapped complex distributions without prior knowledge, proving that the residual energy exploration is an effective strategy for mode discovery.

Conclusion and Future Work

Wormhole Hamiltonian Monte Carlo provides a robust framework for sampling from multimodal distributions by treating geometry as a navigable shortcut. While the current implementation uses a computationally efficient flat base metric ($O(D)$ complexity), future iterations could incorporate the Fisher Information Matrix to better handle complex local curvatures, albeit at a higher computational cost ($O(D^3)$). Further research into non-linear wormhole paths may also enhance the algorithm's ability to navigate more intricate probability manifolds.

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