Shadow Manifold Hamiltonian Monte Carlo

Christopher van der Heide, Fred Roosta, Liam Hodgkinson, Dirk KroeseAISTATS 2021 · OpenReview

Presented at AISTATS 2021, Shadow Manifold Hamiltonian Monte Carlo (SMHMC) is a novel sampling algorithm designed to navigate complex, high-dimensional probability distributions more efficiently than previous state-of-the-art methods. By combining the geometric adaptability of Riemannian Manifold HMC with the numerical stability of "shadow" Hamiltonian methods, SMHMC offers a robust solution for Bayesian inference in challenging topological spaces.

The Challenge: Geometry and Stability

Hamiltonian Monte Carlo (HMC) is a cornerstone of modern Bayesian inference, yet it faces two significant hurdles when dealing with complex models:

  1. Complex Geometry: Standard HMC assumes a "flat" Euclidean space. When target distributions exhibit sharp ridges or varying scales—such as the classic "banana" or "funnel" shapes—HMC becomes highly inefficient. While Riemannian Manifold HMC (RMHMC) addresses this by adapting to local curvature, it relies on implicit numerical integrators (like the generalized leapfrog) that are computationally demanding and sensitive to numerical error.
  2. The Step-Size Trade-off: To maintain high acceptance rates, practitioners typically must use very small integration steps. Larger steps introduce numerical errors that cause the sampler to reject moves, leading to wasted computation and poor exploration.

Previous "Shadow HMC" methods mitigated the step-size issue for standard HMC by targeting a modified ("shadow") energy that the numerical integrator preserves more accurately. However, prior to this work, no shadow Hamiltonian had been derived for the non-separable integrators required for manifold-aware sampling.

The SMHMC Approach

The authors bridge this gap by deriving a fourth-order shadow Hamiltonian ($H^{[4]}$) specifically for the generalized leapfrog integrator. This derivation is particularly delicate because the non-separable nature of Riemannian systems requires accounting for mixed partial derivatives of the Hamiltonian.

Comparison of numerical error and acceptance probability between RMHMC and SMHMC over 2000 iterations.

The SMHMC algorithm functions by:

  • Targeting the Shadow Density: The sampler targets a modified energy that the integrator follows more closely, allowing for larger step sizes without sacrificing stability.
  • Correcting Bias: It uses Importance Sampling to reweight samples, ensuring the final estimates reflect the true target distribution rather than the shadow approximation.
  • Maintaining Validity: A Partial Momentum Refreshment step is employed to ensure the Markov chain remains valid and explores the space effectively.

To facilitate the complex calculations involved, the authors released shadowtorch, a PyTorch implementation that leverages automatic differentiation for higher-order derivatives.

Key Results and Performance

SMHMC was evaluated against standard HMC, RMHMC, and Modified HMC (MMHMC) across several benchmarks, including synthetic pathological densities and real-world Bayesian logistic regression tasks (e.g., Australian Credit, Sonar datasets).

Near-Perfect Acceptance

In logistic regression tests, SMHMC consistently achieved acceptance rates between 96% and 99%. In contrast, RMHMC often saw its acceptance rates dip into the 80s for the same step sizes. This stability allows SMHMC to maintain high performance even when the integration steps are relatively large.

Robust Exploration of "Neal’s Funnel"

Neal’s Funnel is a notorious benchmark where standard HMC often fails to explore the narrow "neck" of the distribution. SMHMC demonstrated superior exploration and a higher Effective Sample Size (ESS) per second compared to both HMC and RMHMC.

Sampling results on Neal’s Funnel (30D). SMHMC and RMHMC show significantly better exploration of the narrow neck compared to standard HMC.

Conclusion and Future Directions

The "aha moment" of SMHMC is the realization that numerical integration error does not need to be eliminated; it simply needs to be accounted for. By targeting the energy that the integrator actually conserves, SMHMC achieves a synergy where RMHMC provides the map (where to go based on geometry) and the shadow Hamiltonian provides the vehicle (how to get there stably).

While SMHMC is more computationally expensive per step due to the need for Hessians and mixed partials ($O(d^3)$ complexity), its gains in efficiency and robustness often outweigh these costs. Future work may extend this framework to even more exotic topological spaces, such as Stiefel manifolds or spheres, which are increasingly relevant in modern machine learning.

Summary updated

BibTeX
@inproceedings{heide2021shadow,
  author = {Christopher van der Heide and Fred Roosta and Liam Hodgkinson and Dirk Kroese},
  title = {{Shadow Manifold Hamiltonian Monte Carlo}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=6J1A3L--PGC},
}
Figure