🔭 astrophysics

Practical and Scalable Hamiltonian Monte Carlo Without the Metropolis Test

This paper proposes an automatic step size tuning scheme for unadjusted Hamiltonian Monte Carlo that selects a step size to meet a user-specified asymptotic bias tolerance, demonstrating that this approach significantly outperforms adjusted counterparts in high-dimensional problems.

Original authors: Jakob Robnik, Reuben Cohn-Gordon, Uroš Seljak

Published 2026-06-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jakob Robnik, Reuben Cohn-Gordon, Uroš Seljak

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Core Problem: Finding the "Center of Mass" in a Foggy Mountain Range

Imagine you are trying to find the exact center of a massive, foggy mountain range. You don’t have a map, but you have a compass that tells you which way is "downhill" (this is called the gradient). Your goal is to wander around the mountains enough to figure out where the "center of gravity" of the whole range is.

In statistics and machine learning, this is called sampling. We use algorithms to wander around a complex mathematical landscape to calculate averages (expectations).

Two popular ways to do this are Hamiltonian Monte Carlo (HMC) and Langevin Monte Carlo (LMC). Think of these as a hiker with a momentum boost. Instead of just walking step-by-step, the hiker builds up speed, rolling down hills and coasting up others, which allows them to explore the landscape much faster than a slow walker.

The "Safety Check" Bottleneck

Traditionally, these fast hikers use a safety mechanism called the Metropolis-Hastings (MH) test.

The Analogy:
Imagine the hiker takes a big leap. Before accepting that they have actually moved to the new spot, they check their energy levels. If the leap was "too perfect" or violated the laws of physics slightly due to calculation errors, they might reject the move and stay where they were. This ensures the hiker stays exactly on the correct path.

The Problem:
As the mountain range gets bigger (more dimensions/parameters), this safety check becomes incredibly slow.

In a small range, checking your energy is easy.
In a massive range with millions of peaks and valleys, the energy check involves adding up tiny errors from every single dimension.
To keep the error low enough to pass the safety check, the hiker has to take tiny, microscopic steps.
Result: The hiker becomes sluggish. The time it takes to explore the range grows significantly as the range gets bigger. This is a major bottleneck for modern AI and physics problems that have millions of parameters.

The Proposed Solution: Trust the Speed, Control the Drift

The authors propose a radical idea: Throw away the safety check.

They suggest using "Unadjusted" samplers. The hiker just leaps forward without stopping to check if the move is perfectly valid.

The Trade-off:

Pros: The hiker can take bigger steps and move much faster. They don’t get bogged down by the slow safety checks.
Cons: Because they aren’t checking their energy, the hiker will drift slightly off the true path. This creates a small, permanent error called Asymptotic Bias. It’s like walking with a slight limp; you’ll never be perfectly centered, but you’ll be very close.

The Big Question:
How do you know how big a step to take?

If the step is too big, the "limp" (bias) is huge, and your answer is wrong.
If the step is too small, you’re moving too slowly, defeating the purpose of skipping the safety check.

Previously, users had to manually guess the right step size, which was difficult and required expert knowledge. This paper solves that problem.

The "Engine Temperature" Gauge (EEVPD)

The authors discovered a clever way to automatically tune the step size. They found a direct link between the energy error of the leap and the bias (the drift from the true answer).

The Analogy:
Think of the hiker’s leap like a car engine.

The Energy Error is like the engine’s temperature gauge.
The Bias is how much the car is pulling to the left or right.

The paper proves mathematically (for Gaussian distributions) and shows numerically (for other shapes) that if you keep the "engine temperature" (Energy Error Variance Per Dimension, or EEVPD) within a specific range, you guarantee that the "pulling to the side" (Bias) is small enough to be acceptable.

They created an automatic tuning scheme:

The algorithm starts wandering.
It constantly monitors its "engine temperature" (EEVPD).
If the temperature is too high (too much error), it slows down (takes smaller steps).
If the temperature is low, it speeds up (takes bigger steps).
It adjusts itself until it hits a target temperature that ensures the error is negligible compared to the natural randomness of the sampling.

Why This Matters

It’s Automatic: You don’t need to be an expert to tune the step size. The algorithm does it for you ("black-box").
It Scales: In traditional methods, as the problem gets bigger (more dimensions), the hiker gets slower. With this new method, the hiker stays fast regardless of how big the mountain range is.
It’s Faster: In experiments with over 1 million parameters (like in quantum physics simulations), this method was 100 times faster than the standard best-in-class methods (like NUTS).

Summary

The paper introduces a way to make fast, gradient-based sampling algorithms fully automatic and highly scalable by removing the slow "safety check" (Metropolis-Hastings step). Instead, it uses a real-time monitor of energy errors (EEVPD) to automatically adjust the step size, ensuring that the slight inaccuracy introduced by skipping the check is kept under control. This allows computers to solve massive, high-dimensional problems much faster than before.

Technical Summary: Practical and Scalable Hamiltonian Monte Carlo Without the Metropolis Test

Problem Statement
Hamiltonian Monte Carlo (HMC) and underdamped Langevin Monte Carlo (LMC) are state-of-the-art methods for sampling from high-dimensional distributions with differentiable densities. Standard implementations employ a Metropolis–Hastings (MH) acceptance step to correct for the asymptotic bias introduced by numerical integration. However, this adjustment imposes a significant computational penalty in high dimensions. Specifically, the MH acceptance probability depends on the total energy change across all parameters, forcing the step size to scale as $d^{-1/4}$ (where $d$ is the dimensionality) to maintain a fixed acceptance rate. This results in a sampling cost that scales as $d^{1/4}$ , creating a bottleneck for large-scale problems.

Unadjusted samplers (those without the MH step) avoid this dimensional scaling and can operate with constant efficiency relative to dimension. However, they introduce an asymptotic bias in expectation estimates. These methods have seen limited adoption in general-purpose Bayesian inference because they require manual tuning of the integration step size to ensure this bias remains negligible compared to the Monte Carlo variance. There has been a lack of automated, principled schemes for selecting this step size.

Methodology
The authors propose an automatic tuning scheme that selects the step size $\epsilon$ to meet a user-specified tolerance for asymptotic bias. The core insight is establishing a rigorous relationship between the Energy Error Variance Per Dimension (EEVPD) and the asymptotic bias of the sampler.

Metric Definition: The authors define EEVPD as the variance of the one-step energy error $\Delta H$ induced by the numerical integrator, normalized by the dimension $d$ . This quantity is a cheap byproduct of the integration step and can be estimated online.
Theoretical Bounds (Gaussian Case): For Gaussian target distributions, the authors derive closed-form expressions for the stationary distribution of unadjusted HMC and LMC. They prove that the covariance matrix bias $b^2_{\text{cov}}$ and the Wasserstein distance $W_2$ between the target and stationary distributions are upper-bounded by functions of EEVPD. Specifically, $b^2_{\text{cov}} \leq \phi^{-1}(\text{EEVPD})$ for $\text{EEVPD} < 0.397$ .
Extension to Non-Gaussian Targets: Numerical experiments on various non-Gaussian benchmarks (Rosenbrock, Funnel, Brownian motion, etc.) suggest that these Gaussian-derived bounds generally hold as conservative upper bounds for non-Gaussian targets as well.
Automatic Tuning Algorithm: The tuning scheme adaptively varies the step size $\epsilon$ during a warm-up phase to target a specific EEVPD value. This target is derived from a bias-variance tradeoff analysis. For a desired relative Root Mean Squared Error (RMSE) tolerance, the optimal squared bias should be approximately one-fifth of the total mean squared error tolerance. For example, to achieve a 10% relative RMSE, the target EEVPD is set to $3 \times 10^{-4}$ .
Preconditioning and Trajectory Length: The scheme also includes automatic determination of diagonal preconditioning and trajectory length (or momentum decoherence length for LMC), utilizing the faster convergence properties of unadjusted methods for preconditioner estimation.

Key Contributions

Automated Step-Size Selection: A black-box tuning algorithm for unadjusted HMC, LMC, and Microcanonical Langevin Monte Carlo (MCLMC) that requires no manual hyperparameter tuning.
Bias-Energy Error Relationship: Rigorous analytical proofs linking EEVPD to asymptotic bias bounds for Gaussian distributions, and empirical validation for non-Gaussian distributions.
Scalability: Demonstration that unadjusted samplers, when properly tuned, maintain constant computational efficiency regardless of dimensionality, unlike MH-adjusted methods.

Results

Bayesian Benchmarks: On standard Bayesian inference problems (dimensions 36–2429), unadjusted LMC and MCLMC with the proposed tuning consistently outperformed their MH-adjusted counterparts and the No-U-Turn Sampler (NUTS). In many cases, the unadjusted methods required significantly fewer gradient evaluations to achieve a target error (e.g., $b^2_{\text{avg}} < 0.01$ ).
High-Dimensional Physics Models:
- $\phi^4$ Field Theory: In a model with over $10^6$ dimensions, unadjusted MCLMC required only 1,344 gradient calls to converge, compared to 133,266 for NUTS and 39,240 for adjusted MCLMC.
- U(1) Lattice Gauge Theory: In a model with up to 2 million dimensions, unadjusted MCLMC converged in 198 gradient calls, whereas adjusted NUTS, HMC, and MCLMC required 127,875, 17,699, and 15,578 calls, respectively.
Scaling Behavior: Experiments confirmed that the cost of MH-adjusted methods scales as $d^{1/4}$ , while the cost of the proposed unadjusted methods remains constant with increasing dimension.
Accuracy: Marginal posteriors generated by the unadjusted methods were practically indistinguishable from those generated by long NUTS chains, confirming that the discretization bias was successfully suppressed.

Significance and Claims
The paper claims to make unadjusted gradient-based samplers viable as fully automatic, black-box algorithms. By removing the need for manual step-size tuning and demonstrating superior scalability in high dimensions, the authors argue that unadjusted HMC, LMC, and MCLMC should be preferred over adjusted methods like NUTS for high-dimensional applications. The work bridges the gap between the theoretical efficiency of unadjusted samplers and their practical applicability in Bayesian inference and statistical physics. The authors note limitations, specifically identifying the Brownian motion model as a case where the bias bound was less tight than predicted, and recommend diagnostic checks (e.g., comparing chains with different step sizes) to ensure discretization bias remains negligible in practice.