Resonances in reflective Hamiltonian Monte Carlo

This paper investigates the slow mixing and resonant unmixing phenomena in high-dimensional reflective Hamiltonian Monte Carlo with inexact reflections by quantifying distribution non-uniformity via Sinkhorn divergence, revealing critical step-size scaling laws and fluid-like versus discretisation-dominated dynamics in spherical and cubic domains.

The Gist

Imagine you are trying to find the perfect spot to park a car in a massive, multi-dimensional parking garage. You have a fleet of autonomous cars (particles) that need to explore the entire garage to ensure they've seen every corner. This is what a computer algorithm called Reflective Hamiltonian Monte Carlo (RHMC) does: it helps scientists solve complex math problems by "driving" around a defined space to find the best answers.

However, this paper discovers that in very high-dimensional spaces (think of a garage with hundreds of floors and directions at once), these cars get stuck in a weird traffic jam. They don't mix well; instead, they start bouncing around in a synchronized, rhythmic pattern that looks like a dance, but it's actually a disaster for finding the truth.

Here is the breakdown of what's happening, using simple analogies:

1. The Setup: The "Perfect" Parking Garage

The algorithm tries to sample a uniform distribution. Imagine the garage is a giant, empty sphere or a cube. The goal is for the cars to spread out evenly so that every square inch of the floor has exactly one car.

• The Problem: The cars start all bunched up at a single point (like a traffic jam at the entrance).
• The Tool: The cars move in straight lines until they hit a wall. When they hit a wall, they bounce off (reflect).

2. The Glitch: The "Inexact" Bounce

In the real world, if a ball hits a wall, it bounces off at the exact moment it touches the surface. But in this computer simulation, the "walls" are calculated roughly. The car moves forward, realizes it's past the wall, and then bounces back.

• The Analogy: Imagine a game of ping-pong where the paddle is slightly too big. The ball hits the paddle, goes a tiny bit through it, and then gets slapped back. Because the computer calculates the bounce based on where the ball is (outside the wall) rather than where it touched the wall, the physics get slightly weird.

3. The Phenomenon: "Resonance" (The Traffic Jam Dance)

The paper calls the main problem Resonance.

• The Metaphor: Imagine a crowd of people running in a circular track. If they all start at the same spot and run at the same speed, they stay in a tight pack. If they hit a wall and bounce back, they all hit it at the exact same time and bounce back together.
• What happens in the paper: In high dimensions, the cars naturally tend to run along the "edge" of the garage (the boundary) rather than cutting through the middle. Because they all start together and bounce off the walls at the same time, they bunch up into a tight group, travel to the opposite side of the room, bunch up there, and bounce back.
• The Result: Instead of spreading out to fill the room (mixing), they oscillate back and forth like a pendulum. They are "unmixing." This creates a "resonance" where the density of cars spikes in certain areas and vanishes in others, just like a sound wave hitting a wall and echoing.

4. The Two Regimes: Fluid vs. Discrete

The authors found two ways this traffic jam behaves, depending on how fast the cars are driving (the "step size"):

• The Fluid Regime (Slow Cars): If the cars move slowly, they act like a liquid. They flow smoothly, hit the wall, and spread out a bit. But even then, they eventually bunch up again because of the "inexact" bounce.
• The Discretization Regime (Fast Cars): If the cars move too fast, they overshoot the walls by a lot. They get stuck in a "rejection" loop where they try to move, hit the wall, get rejected, and stay in the same spot. In high dimensions, this causes the cars to get trapped in one-dimensional lines (like running up and down a single hallway) and never exploring the rest of the garage.

5. Why This Matters

This isn't just a parking problem. This algorithm is used in Nested Sampling, a technique used by astrophysicists to calculate the probability of the universe having certain properties, or by material scientists to design new drugs.

• The Consequence: Because the cars are dancing in a synchronized loop instead of spreading out, the computer thinks it has found the answer, but it's actually biased. It gives a "negative error," meaning the final result is consistently wrong.
• The Scale: The problem gets worse as the number of dimensions increases. In a 100-dimensional garage, the "critical speed" where the cars start getting stuck is incredibly low. It's like trying to drive a car in a room where the walls are so close together that you can't even turn the steering wheel.

6. The Solution? (Or at least, the Insight)

The paper suggests that the current way we tune these algorithms is broken. We usually check if the cars are hitting the walls "often enough" to think they are working. But this paper shows that even if they are hitting the walls, they might be doing it in a synchronized, useless loop.

• The Fix: We need to stop the cars from dancing in sync. The authors suggest adding a little bit of "noise" (randomness) to their speed at every step. This is like telling the cars, "Hey, speed up a tiny bit, slow down a tiny bit, randomly." This breaks the rhythm, stops the bunching, and forces them to actually explore the whole garage.

Summary

The paper reveals that a popular computer algorithm for solving hard math problems has a hidden flaw: in high-dimensional spaces, the "bouncing" mechanism causes the data points to synchronize and bounce back and forth in a tight group (resonance) instead of spreading out. This makes the algorithm fail to find the true answer. The solution is to introduce more randomness to break the rhythm and force the data to mix properly.

Technical Summary

1. Problem Statement

The paper addresses the poor mixing performance and systematic errors observed in Reflective Hamiltonian Monte Carlo (RHMC), specifically the Galilean Monte Carlo (GMC) variant, when applied to high-dimensional uniform distributions.

• Context: RHMC is widely used in nested sampling and slice sampling for Bayesian inference and materials science. It relies on "inexact reflections" because the exact boundary intersection is often computationally prohibitive or unknown.
• The Issue: In high dimensions ($n \gg 10$), RHMC exhibits a negative systematic error in estimating normalizing constants (model evidence). This is attributed to "poor mixing," where particle ensembles fail to explore the volume uniformly.
• Specific Challenge: Unlike standard MCMC which runs long chains, nested sampling often operates in a "many-short-chains" regime, initializing many parallel chains from a single point (or a small set of "live points"). The paper isolates the mixing problem by studying an ensemble of particles initialized from a Dirac delta distribution (a single point) targeting a uniform distribution.
• Gap: Existing theoretical bounds on mixing time (based on "warmness") are vacuous for Dirac delta initializations (infinite warmness), and the physical mechanism behind the mixing failure in high dimensions was previously unidentified.

2. Methodology

The authors employ a combination of computational experiments, geometric analysis, and spectral analysis to diagnose the mixing dynamics.

• Metric: Sinkhorn Divergence (SD):
  • Instead of standard convergence metrics, the authors use the Sinkhorn Divergence (an entropy-regularized optimal transport cost) to quantify the distance between the particle ensemble's density and the target uniform distribution.
  • An increase in SD indicates "unmixing" (bunching), while a decrease indicates mixing.
• Test Geometries:
  • Unit Sphere ($S^{n-1}$): Represents isotropic distributions (common in linear models and harmonic approximations).
  • Unit Cube ($[-1, 1]^n$): Represents distributions with flat boundaries (common in polytope volume calculations and discrete parameters).
• Dimensionality Reduction (Sphere):
  • The authors prove that for the sphere, the dynamics of any particle trajectory are confined to a 2D plane spanned by the initial position and momentum.
  • They construct a lossless rotation map to project $n$-dimensional trajectories onto a 2D disk, allowing for direct visualization of the density evolution.
• Spectral Analysis:
  • The time-series of the Sinkhorn Divergence is analyzed via Power Spectral Density (PSD) to identify oscillatory modes (resonances) and their frequencies.
• Low-Dimensional Toy Models:
  • The high-dimensional dynamics are mapped to 1D and 2D toy models to reproduce the "bunching" and "unmixing" phenomena, isolating the role of inexact reflections.

3. Key Contributions & Findings

A. Mechanism of Mixing Failure: Resonances and Bunching

The primary discovery is that the mixing failure is caused by resonances arising from the interplay between high-dimensional geometry and inexact reflections.

• Inexact Reflections: In GMC, particles overstep the boundary and reflect based on a normal vector defined outside the volume. This differs from dynamical billiards (exact reflections).
• Order Preservation: Unlike billiards where reflection reverses the order of particles, GMC preserves the order of particles along the normal. If a dispersing wave packet hits a boundary, the inexact reflection causes the particles to converge (focus) rather than diverge.
• Spontaneous Unmixing: This focusing effect causes the particle density to spontaneously "unmix" (form local over-densities) at specific time intervals, creating oscillations in the Sinkhorn Divergence.

B. Two Distinct Dynamical Regimes

The behavior of the particle ensemble transitions between two regimes based on the momentum standard deviation ($\sigma_p$) and dimension ($n$):

1. Fluid-like Regime (Small $\sigma_p$):
   • Particles behave like a shock wave propagating through the volume.
   • In the sphere, the wave reflects between antipodal points.
   • Mixing is dominated by the diffusion of the wavefront.
2. Discretization-Dominated Regime (Large $\sigma_p$):
   • Particles move too fast for the discrete time steps to resolve the boundary correctly.
   • Sphere: Particles get "stuck" on a specific radius (concentration of measure) and oscillate between antipodal points, failing to explore the radial dimension.
   • Cube: Particles are frequently rejected (momentum reversal) rather than reflected, trapping them in 1D subspaces or at their initial positions.

C. Critical Scaling Laws

The paper derives power-law scalings for the critical step size ($\sigma_p$) that separates these regimes:

• Sphere: The critical scale scales as $n^{-1/2}$.
• Cube: The critical scale scales as $n^{-0.986}$ (approximately $n^{-1}$). This is derived from the scaling of the mean chord length in high-dimensional cubes, which decreases rapidly with dimension.
• Implication: As dimension increases, the allowable step size for effective mixing shrinks drastically, explaining why RHMC fails in high dimensions with standard tuning.

D. Frequency Spectrum Analysis

• Sphere: The dominant frequency corresponds to a "supersonic" mode where particles travel along the boundary, reaching antipodal points faster than a straight-line trajectory due to the geometry of the reflection.
• Cube: The spectrum transitions from continuous (fluid-like) to discrete peaks (quasi-periodic) as $\sigma_p$ increases. At high $\sigma_p$, a single dominant frequency ($f = 1/4$ MCS$^{-1}$) emerges, corresponding to particles trapped in 1D oscillations.

E. Critique of Current Tuning Metrics

The authors demonstrate that the standard tuning metric for RHMC—the trajectory-wise acceptance rate—is uninformative regarding mixing.

• A chain can have a high acceptance rate (e.g., 1/2 or 1/3) while being completely stuck in a subspace or exhibiting strong resonances.
• The metric fails to detect "unmixing" or convergence to a subspace, leading practitioners to believe the algorithm is tuned correctly when it is not.

4. Results

• Visual Evidence: In the sphere, the particle density forms a ring that oscillates between the initial point and the antipodal point, leaving the center of the sphere empty (under-density).
• Cube Behavior: In the cube, increasing $\sigma_p$ leads to a sharp increase in rejection rates, trapping particles in 1D lines or at the initial point, causing the Sinkhorn Divergence to plateau at a high value.
• Damping: Adding Gaussian noise to the momentum at every step (similar to Langevin dynamics) damps these resonances but introduces a new trade-off: too much noise increases rejection rates in the cube, slowing mixing further.

5. Significance and Implications

• Theoretical Insight: The paper provides the first rigorous explanation for the "curse of dimensionality" in RHMC, attributing it not just to volume concentration but to discrete-time resonances caused by inexact reflections.
• Practical Impact:
  • Explains the systematic negative bias in nested sampling evidence calculations for high-dimensional problems.
  • Demonstrates that current tuning heuristics (acceptance rates) are insufficient and potentially misleading.
  • Suggests that local preconditioning (coordinate transformations dependent on position) or adaptive noise injection may be necessary to break these resonances.
• Future Directions: The work calls for new tuning metrics based on the short-time dynamics (e.g., monitoring the Sinkhorn Divergence or spectral properties) rather than long-term acceptance rates, and motivates the development of new piecewise-deterministic algorithms that avoid these resonances.

In summary, the paper reveals that high-dimensional RHMC suffers from a fundamental physical instability where the discretization of time and the geometry of the boundary cause particle ensembles to spontaneously bunch and unmix, rendering standard sampling strategies ineffective without specific geometric or algorithmic interventions.