Black-box unadjusted Hamiltonian Monte Carlo

Jakob Robnik, Reuben Cohn-Gordon, Uroš Seljak · 2024

Read Black-box unadjusted Hamiltonian Monte Carlo by Jakob Robnik, Reuben Cohn-Gordon, Uroš Seljak (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-08876.txt.

Introduction

Jakob Robnik, Reuben Cohn-Gordon, and Uroš Seljak make a fast sampling method practical by removing its guesswork, in a 2024 paper. The head title calls it practical and scalable Hamiltonian Monte Carlo without the usual acceptance test. That test removes the small bias caused by rough numerical steps, but it also slows mixing and raises noise.

Skipping the test trades a little bias for much lower variance, yet few used the shortcut because picking the step size was an art. The authors tie the size of energy errors to the bias, then tune the step automatically to meet a bias limit the user sets. On hard test problems, including one with over a million parameters, the tuned shortcut beat the standard method clearly.

Catalog record

CREATORJakob Robnik, Reuben Cohn-Gordon, Uroš Seljak
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-08876

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Black-box unadjusted Hamiltonian Monte Carlo Jakob Robnik, Reuben Cohn-Gordon, Uroš Seljak Abstract Hamiltonian Monte Carlo and underdamped Langevin Monte Carlo are state-of-the-art methods for taking samples from high-dimensional distributions with a differentiable density function. To generate samples, they numerically integrate Hamiltonian or Langevin dynamics. This numerical integration introduces an asymptotic bias in Monte Carlo estimators of expectation values, which can be eliminated by adjusting the dynamics with a Metropolis-Hastings (MH) proposal step. Alternatively, one can trade bias for variance by avoiding MH, and select an integration step size that ensures sufficiently small asymptotic bias, relative to the variance inherent in a finite set of samples. Such unadjusted methods often significantly outperform their adjusted counterparts in high-dimensional problems where sampling would otherwise be prohibitively expensive, yet are rarely used in statistical applications due to the absence of an automated way of choosing a step size. We propose just such an automatic tuning scheme that takes a user-provided asymptotic bias tolerance and selects a step size that ensures it. The key to the method is a relationship we establish between the energy error in the integration and asymptotic bias. For Gaussians, we show that this procedure rigorously bounds the asymptotic bias. We then numerically show that the procedure works beyond Gaussians, on typical Bayesian problems. To demonstrate the practicality of the proposed scheme, we provide a comprehensive comparison of adjusted and unadjusted samplers, showing that with our tuning scheme, the unadjusted methods achieve close to optimal performance and significantly and consistently outperform their adjusted counterparts. 1 Introduction Sampling offers a way to compute expectation values \mathbb{E}_{p}[f]=\int p(\boldsymbol{x})f(\boldsymbol{x})d\boldsymbol{x} , where f(\boldsymbol{x}) is some function of parameters \boldsymbol{x}\in\mathbb{R}^{d} and p(\boldsymbol{x})=e^{-\mathcal{L}(\boldsymbol{x})}/Z is a given probability density, with a possibly unknown normalization constant Z=\int e^{-\mathcal{L}(\boldsymbol{x})}dx . This is a key tool across a variety of disciplines, from economics and social science ( Gelman et al. 2013 ) , to high energy physics ( Duane et al. 1987a ) , computational chemistry Leimkuhler and Matthews 2015b , statistical physics ( Leimkuhler and Matthews 2015a ) , and machine learning ( Neal 2012 ) . Often a gradient \nabla\mathcal{L}(\boldsymbol{x}) is available, either analytically, or via automatic differentiation ( Griewank and Walther 2008 ; Margossian 2019 ) , as is often the case in Bayesian statistics ( Štrumbelj et al. 2024 ; Carpenter et al. 2017 ) , machine learning ( Baydin et al. 2018 ) , lattice quantum problems ( Gattringer and Lang 2010 ) , and cosmology ( Campagne et al. 2023 ; Ruiz-Zapatero et al. 2024 ; Horowitz and Lukic 2025 ) . Markov Chain Monte Carlo (MCMC) ( Metropolis et al. 1953 ) is a commonly employed class of sampling methods in which a Markov chain \{\boldsymbol{x}_{i}\}_{i=1}^{n} is designed such that its stationary distribution is \tilde{p}(\boldsymbol{x}) and the expectation value \mathbb{E}_{p}[f] can be approximated by the time average over the chain \bar{f}=\frac{1}{n}\sum_{i=1}^{n}f(\boldsymbol{x}_{i}) . When a (smooth) gradient is available, Hamiltonian Monte Carlo (HMC) ( Duane et al. 1987b ; Neal et al. 2011a ; Betancourt 2017 ) and underdamped Langevin Monte Carlo ( Horowitz 1991 ; Leimkuhler and Matthews 2015a ) are the gold standard algorithms for generating Markov chain transitions. Despite their success ( Štrumbelj et al. 2024 ) , MCMC often presents a computational bottleneck ( Gattringer and Lang 2010 ; Leimkuhler and Matthews 2015a ; Simon-Onfroy et al. 2025 ) , especially in the high-dimensional applications, forcing the practitioners to resort to more approximate methods, such as Laplace approximation ( Millea and Seljak 2022 ) or an ensemble Kalman filter ( Houtekamer and Mitchell 2005 ; Houtekamer and Zhang 2016 ) . Bias-variance tradeoff Figure 1: Graphical representation of the bias decomposition from Equation ( 2 ). Both adjusted and unadjusted methods have initialization bias, which typically decays exponentially fast for HMC-like algorithms ( Margossian and Gelman 2024 ) (with a rate denoted by c in the Figure). Both methods also have the variance associated with the finite number of samples taken. It decays inversely proportionally to the number of samples t , with a proportionality constant that is determined by the autocorrelation time. Unadjusted methods also have asymptotic bias which depends strongly on the step size \epsilon , for the example from Appendix C , as \mathcal{O}(\epsilon^{4}) . To understand the challenge faced by MCMC, consider the root mean squared error (RMSE) of the Monte Carlo estimator: \mathrm{RMSE}[\bar{f}]=\mathbb{E}_{MC}[(\bar{f}-\mathbb{E}_{p}[f])^{2}]^{1/2}, (1) where \mathbb{E}_{MC}[\cdot] denotes the expectation with respect to the Monte Carlo randomness. We will sometimes also refer to the relative RMSE, which we define as \mathrm{RMSE}[\bar{f}]/\mathbb{E}_{p}[f] . The RMSE can be decomposed as \mathrm{RMSE}[\bar{f}]^{2}=\mathrm{Bias}[\bar{f}]^{2}+\mathrm{Var}[\bar{f}], (2) where \mathrm{Bias}[\bar{f}]=\mathbb{E}_{MC}[\bar{f}-\mathbb{E}_{p}[f]] and the variance \mathrm{Var}[\bar{f}]=\mathbb{E}_{MC}[(\bar{f}-\mathbb{E}_{MC}[\bar{f}])^{2}] . The bias term arises either from the chain not yet reaching its stationary state and being influenced by its initial position (initialization bias), or because the stationary distribution of the chain \tilde{p}(\boldsymbol{x}) does not equal the target distribution p(\boldsymbol{x}) (asymptotic bias). Initialization bias is an important issue ( Margossian et al. 2024 ) , but we will not study it here, noting that for long enough chains it can be eliminated by discarding initial samples ( Margossian and Gelman 2024 ) . The variance term comes from the finite chain length and the correlation between the samples. This decomposition is illustrated in Figure 1 . One of the main practical goals in designing MCMC methods is to obtain a desired RMSE at the lowest possible computational budget. This amounts to balancing the cost of generating samples, correlations between the samples, and the asymptotic bias. For example, the use of Metropolis-Hastings adjustment ( Chib and Greenberg 1995 ) ensures that a chain satisfies detailed balance, so that the asymptotic bias vanishes, but for finite-length chains does not remove the variance. Noting that chains are finite in practice, one could negotiate the tradeoff differently and reduce the variance at the cost of introducing some bias. This possibility is the focus of the present work. Figure 2: Sampling cost scaling with the dimensionality for product targets. Cost is measured by the number of gradient calls needed to achieve low error. MH adjusted methods are shown in dashed lines, and unadjusted methods are shown in solid lines. Step size for the unadjusted schemes is selected by the scheme proposed in this paper. d^{1/4} power law grey lines are shown in the background. A Standard Gaussian target is shown on the left ( D=1 ), and a product of banana-shaped Rosenbrock distributions ( D=2 ) on the right. In both cases, the cost of the MH adjusted methods scales as d^{1/4} , while the cost of the unadjusted method remains constant with dimension. Illustrative example The shortcoming of performing MH is the scaling with the dimension that it implies for the sampler. To develop an intuition, we consider a simple problem, where the target is a product of K independent D -dimensional distributions q : p(\boldsymbol{x})=\prod_{i=1}^{K}q(x_{iD},x_{iD+1}\ldots x_{iD+D-1}), where D is a small number. Suppose we are interested in the expectation value of a function of only one of those parameters, such as f(\boldsymbol{x})=x_{1}^{2} . We will measure the performance as the number of evaluations of \nabla p(\boldsymbol{x}) (which is typically the bottleneck of computation and thus a proxy for the wall-clock time) that the sampler

Read the complete text