Microcanonical Hamiltonian Monte Carlo

This paper introduces Microcanonical Hamiltonian Monte Carlo (MCHMC) and its continuous variant MCLMC, which utilize fixed-energy dynamics and specialized momentum bounces to achieve superior scalability and performance compared to standard HMC methods like NUTS.

The Gist

Imagine you are trying to find the most valuable spots in a vast, foggy landscape. This landscape represents a complex problem where some areas are "rich" with answers (high probability) and others are empty. Your goal is to map out the rich areas accurately without getting lost or wasting time in the empty zones.

In the world of data science and statistics, this is called sampling. The paper introduces a new, highly efficient way to do this called Microcanonical Hamiltonian Monte Carlo (MCHMC) and its cousin, MCLMC.

Here is the simple breakdown of how it works, using everyday analogies:

1. The Old Way: The Hiker with a Backpack (Standard HMC)

Imagine a hiker (the standard algorithm, known as HMC) trying to map this landscape.

• How they move: The hiker carries a heavy backpack (momentum) that helps them glide over hills and valleys.
• The problem: The hiker's energy changes constantly. Sometimes they have a full backpack, sometimes they are light. To keep moving effectively, they have to stop occasionally, throw away their current backpack, and grab a brand new one with a random weight. This is called "resampling."
• The issue: If the landscape is tricky (like a long, narrow canyon or a multi-peaked mountain range), the hiker might get stuck in a loop, circling the same spot forever, or they might move too slowly through the rich areas.

2. The New Way: The Billiard Ball (MCHMC)

The authors propose a different approach. Instead of a hiker who changes their backpack weight, imagine a billiard ball rolling on a table.

• Constant Energy: The ball never gains or loses energy. It rolls at a constant speed determined by the "terrain" (the math of the problem). If the terrain is "rich" (high probability), the ball slows down to look around. If the terrain is "poor" (low probability), it speeds up to get through quickly.
• The Problem with the Billiard Ball: If the table is perfectly smooth and shaped like a circle, the ball might just bounce around in a perfect, predictable loop forever, never visiting the whole table. It gets "stuck" in a pattern.
• The Solution (The Bounce): To fix this, the authors add a rule: occasionally, the ball hits an invisible wall and bounces off in a completely random new direction, but it keeps the same speed. This "billiard bounce" ensures the ball eventually visits every corner of the table.

3. The Smooth Version: The Drifting Leaf (MCLMC)

The authors also created a smoother version called MCLMC.

• Instead of waiting for a big, sudden bounce, imagine the ball is actually a leaf floating on a river.
• At every tiny step, the current gently nudges the leaf slightly off its course, but not enough to stop it. It's a continuous, gentle "wobble" rather than a hard crash.
• This allows the leaf to explore the river very efficiently, mixing its path constantly without ever stopping.

Why is this better?

The paper claims these new methods are like super-fast explorers compared to the old hiker:

• Speed: They can solve difficult problems (like finding patterns in high-dimensional data) up to 10 to 100 times faster than the current best methods.
• No Tuning: Usually, these algorithms require a human to spend a lot of time "tuning" the settings (like adjusting the size of the steps or how often to bounce). The authors created a smart, automatic system that figures out the perfect settings instantly, like a car with self-driving cruise control that adjusts to the road automatically.
• Handling Tricky Shapes: They are particularly good at navigating "ill-conditioned" landscapes—think of a long, thin banana shape or a funnel where the path gets very narrow. The old methods often get stuck here, but the new methods glide right through.

The "Secret Sauce": The Map vs. The Terrain

The paper explains that these methods work by changing how they view the map.

• In the old method, the hiker tries to walk on the actual shape of the land.
• In the new method, the algorithm "warps" the map. It stretches the empty, low-probability areas and shrinks the high-probability areas. This makes the "rich" spots look like flat, easy-to-walk plains, allowing the ball to spend more time there naturally, without needing to stop and think.

Summary

The paper introduces a new way to explore complex data landscapes. Instead of a hiker who constantly changes their gear, they use a ball that rolls with constant energy but occasionally bounces in random directions (or gently wobbles). This ensures they cover the whole map quickly and efficiently, automatically adjusting their speed to the terrain, making them much faster and more reliable than previous methods for solving complex statistical puzzles.

Technical Summary

Technical Summary: Microcanonical Hamiltonian Monte Carlo

Problem Statement

Sampling from high-dimensional probability distributions $p(x) = e^{-L(x)}/Z$ is a fundamental challenge in fields ranging from Bayesian inference to statistical physics. Standard Hamiltonian Monte Carlo (HMC) methods sample from a canonical ensemble where the system energy fluctuates, requiring occasional stochastic momentum resampling to ensure ergodicity. However, HMC can suffer from slow convergence and high autocorrelation, particularly in ill-conditioned or high-dimensional problems.

Recent deterministic approaches, such as the Energy Sampling Hamiltonian (ESH) proposed by Ver Steeg and Galstyan (2021), attempt to sample from a fixed-energy (microcanonical) surface without momentum resampling. While deterministic methods theoretically offer lower noise and faster convergence, the authors demonstrate that ESH is generally not ergodic. Specifically, running multiple independent chains with deterministic ESH dynamics does not guarantee convergence to the true target distribution, as the system can become trapped in non-ergodic subsets of the energy surface.

Methodology

The paper introduces Microcanonical Hamiltonian Monte Carlo (MCHMC), a class of models that strictly conserve energy while sampling. The core idea is to tune the Hamiltonian function $H(x, \Pi)$ such that the marginal distribution of the uniform distribution on the constant-energy surface over the momentum variables yields the desired target distribution $p(x)$.

1. Hamiltonian Tuning

The authors derive a family of Hamiltonians where the kinetic term $T(\Pi)$ depends on the momentum magnitude $|\Pi|$ via a continuous index $q$. By solving the marginalization condition, they determine the potential energy $V(x)$ required to match the target density.

• Variable Mass Hamiltonian ($q=0$): This choice leads to a Hamiltonian equivalent to a particle with position-dependent mass $m(x) \propto p(x)^{-2/d}$. In this formulation, the particle moves slower in high-density regions and faster in low-density regions. This is the primary focus of the paper.
• Standard Kinetic Energy ($q=2$): Corresponds to $H = \frac{1}{2}|\Pi|^2 + V(x)$, where the potential is tuned differently.
• Relativistic Hamiltonian: A non-separable option, though less analyzed due to integrator complexity.

2. Ensuring Ergodicity: Momentum Decoherence

The authors identify that deterministic evolution on a fixed energy surface is insufficient for ergodicity. They propose two stochastic mechanisms to break momentum correlations while conserving energy:

• MCHMC (Billiard-like Bounces): The momentum direction is randomly reoriented (isotropically) at discrete intervals, while the momentum magnitude (and thus energy) is preserved. This acts as an energy-conserving analog to the momentum resampling in standard HMC.
• Microcanonical Langevin-like Monte Carlo (MCLMC): Instead of discrete bounces, the momentum direction is partially refreshed at every step. This introduces non-Gaussian noise, creating an underdamped Langevin-like dynamics that preserves energy.

3. Hyperparameter Tuning

A significant contribution is the development of an efficient, largely automatic tuning scheme for the two key hyperparameters: the integration step size $\epsilon$ and the momentum decoherence scale $L$ (or bounce frequency).

• Step Size ($\epsilon$): Tuned by monitoring the variance of energy fluctuations ($Var[E]$). The authors find that a target $Var[E]/d \approx 0.001$ (or a conservative $0.0003$) ensures low bias without instability.
• Decoherence Scale ($L$): Tuned by relating $L$ to the size of the "typical set" of the distribution. For Gaussian targets, $L \propto \sqrt{d}$. For non-Gaussian targets, an initial estimate based on effective variance is refined using autocorrelation analysis to determine the effective sample size.

4. Geometric Interpretation

The paper provides a geometric perspective, showing that MCHMC dynamics are equivalent to geodesic motion on a Riemannian manifold with a conformally flat metric $g_{ij}(x) \propto p(x)^{2/d} \delta_{ij}$. The "bounces" are interpreted as necessary interventions to ensure ergodicity on this manifold, particularly in regions where curvature might not naturally induce sufficient mixing.

Key Results

The authors evaluate MCHMC and MCLMC against NUTS (the state-of-the-art HMC variant) and unadjusted HMC on several benchmark problems:

1. Ill-conditioned Gaussians: MCLMC outperforms NUTS by more than an order of magnitude (factor of 10+) for condition numbers $\kappa=100$, with the advantage increasing for higher $\kappa$.
2. Bi-modal Distributions: MCHMC achieves a 6–10x improvement in Effective Sample Size (ESS) over NUTS.
3. Rosenbrock Function: MCHMC shows a 4x improvement over NUTS. The $q=2$ Hamiltonian performs significantly worse than the $q=0$ (variable mass) choice.
4. Neal's Funnel & Stochastic Volatility: MCHMC improves ESS by factors of 11 to 23 over NUTS.
5. Cauchy Distribution: For heavy-tailed distributions where second moments diverge, MCLMC converges significantly faster than NUTS, producing over 600 effective samples in $10^6$ gradient calls compared to NUTS's slow convergence.

Crucially, the paper demonstrates that algorithms without momentum decoherence (pure ESH or "no bounce" MCHMC) fail to converge on these benchmarks, confirming the necessity of the proposed stochastic interventions.

Significance and Claims

The paper claims that MCHMC and MCLMC offer a robust alternative to canonical HMC by leveraging energy-conserving dynamics. Key significance points include:

• Ergodicity: The authors prove that deterministic microcanonical sampling is insufficient and that energy-conserving momentum bounces are essential for ergodicity, resolving a limitation of previous deterministic approaches like ESH.
• Efficiency: The proposed methods exhibit favorable scaling with condition number and dimensionality, often outperforming NUTS by orders of magnitude on standard benchmarks.
• Tuning: The development of a "tuning-free" (or low-cost tuning) scheme based on energy fluctuation monitoring and typical set scaling makes these methods practical for real-world applications without extensive manual hyperparameter search.
• Bias Control: Unlike standard HMC which relies on Metropolis adjustments to correct bias, MCHMC controls bias through step size selection (keeping energy fluctuations small), a strategy common in Molecular Dynamics but less emphasized in Bayesian inference.

The authors conclude that while the class of Hamiltonian models is broad, the geometric interpretation of sampling as geodesic motion on a conformally flat manifold provides a powerful framework for understanding and extending these methods. They note that their automatic tuning scheme is close to optimal across a wide range of targets, though more sophisticated methods (e.g., ChEES) could potentially offer further improvements at higher computational cost.