Archive for leapfrog integrator
even faster HMC by learning leapfrog scale offline [online]
Posted in Books, Statistics, University life with tags Hamiltonian Monte Carlo, HMC, leapfrog integrator, No-U-Turn sampler, NUTS, population Monte Carlo, Statistics & Computing, tempering on September 24, 2026 by xi'an
faster HMC by learning
Posted in Books, Kids, Statistics, University life with tags algorithm, conformal Hamiltonian dynamics, eHMC, Hamiltonian Monte Carlo, HMC, leapfrog integrator, mirror descent, No-U-Turn sampler, NUTS, PhD thesis, population Monte Carlo, publication fees, revision, Scholarly Open Access, Shanghai, Springer Nature, Statistics & Computing, tempering, Università Ca' Foscari Venezia on September 23, 2026 by xi'an
Just received the good news that our paper Faster Hamiltonian Monte Carlo by Learning Leapfrog Scale by Wu Changye (吴昌烨), Pierre Pudlo, Julien Stoehr and myself, got accepted in Statistics & Computing! This is great in its own, but further concludes a story that started with Changye’s PhD thesis at Paris Dauphine in 2018, with a revision request from Statistics & Computing that stalled with Changye’s departing for industry in Shanghai and eventually resumed thanks to Julien’s massive investment in coding and improving the learning mechanism. It may also conclude my story with Statistics & Computing, where I am supposed to be the historically most prolific author (?), given the move by Springer to a cash-flow model on 01 January, 2027…
comments from Bob
Posted in Books, pictures, Statistics, University life with tags arXiv, Fisher divergence, Hamiltonian Monte Carlo, HMC, JMLR, leapfrog integrator, local adaptation, MCMC, NUTS, Riemann manifold, U-turn on April 10, 2026 by xi'an
Bob replied to my short post with further items of information that I find worth sharing:
Thanks for the kind post, Christian. It’s amusing to be the subject of one of these posts given how many of them I’ve read about other people. I really appreciate your summaries. And thanks to everyone in the audience for all the great feedback during and after the talk. Here’s a link to my slides.
One of your students or postdocs mentioned an approach that does continuous adaptation on some kind of polynomial schedule that is provably correct, but I didn’t manage to write down the author/reference or the name of the person who recommended it. If you happen to know what that is, I’d be grateful for the reference.
I would also like to follow up on the Robert & Andrieu paper you mention, but I could not find the exact reference on your Google Scholar page. The closest match I can find is:
Controlled MCMC for optimal sampling. 2001. C Andrieu, CP Robert. INSEE.
Section 1.3 is titled “Criteria for local adaptation.” The section cites two things. The first is Haario et al.’s (1999) sliding window approach, for which HMC moves too fast to be useful locally. The second is the multiple try approach of Liu et al. (2000) and the delayed rejection approach Tierny and Mira (1999). We applied delayed rejection to HMC step size adaptation in a couple of papers before developing GIST (Modi, Barnett and Carpenter in Bayesian Analysis; Turok, Modi, and Carpenter in AISTATS); these mirror our second GIST paper and third GIST paper in doing the step size adaptation for a whole trajectory and at each leapfrog step. The GIST approach is easier to understand, easier to describe mathematically, easier to implement, and is more efficient.
The nice part about GIST compared to Riemannian HMC is that we do not need to do any volume adjustments (which must be autodiffed through), which are cubic, and we do not need an implicit integrator, which is incredibly fussy to tune. The tradeoff is the we require reversibility of the adaptation, which I think is going to be tricky with varying curvature. Of course, we can’t afford to compute Hessian matrices in high dimensions, but we could manage Hessian-vector products if we could figure out how to use just those and we could also manage low-rank plus diagonal approximations or sketches as described in the Nutpie paper.
We’ve arXived the Nutpie paper since the talk:
Preconditioning HMC by minimizing Fisher divergence. arXiv. 2026. Seyboldt, Carlsen, and Carpenter.
The WALNUTS paper has been accepted by JMLR, but currently only the arXiv version is available:
The within-orbit adaptive leapfrog no-U-turn sampler. 2026. Nawaf Bou-Rabee, Bob Carpenter, Tore Selland Kleppe, Sifan Liu. 2025 arXiv; 2026 to appear JMLR.
Working with Nawaf and Tore has made all the difference in the world on this—it’s not something I could have done by myself. Sifan’s the one who came up with the nice characterization of NUTS and Nawaf’s done a number of additional things like providing mixing time bounds for NUTS (with Milo Marsden, who’s sadly no longer with us—he’s gone into finance).
Furthermore, you can adjust the U-turn criterion from 180 degrees to whatever you want to control how much of a full orbit you get. Those tend to be even more wasteful of iterations, though—this is what the plot from the expected integration time of NUTS is supposed to show, but it was confusing in the talk.
The approach you took with Wu Chengye to randomize number of leapfrog steps made a deep impression on me. It’s also wasteful in leapfrog steps because any number of steps greater than or less than about 1/4 of an orbit is wasteful either in computation or because it leads to more diffusive sampling. You can see that it is roughly as gradient efficient as NUTS in a 1000-dimensional standard normal. Interestingly, it’s worse than NUTS for parameter estimates and better for squared parameter estimates, which is overall a win. Nawaf has also published on randomized HMC. I think we could turn down NUTS U-turn criterion below 180 degrees to get something similar with NUTS, but I haven’t tried it.
One important property of your randomized approach is that it is much much easier to code efficiently for GPUs than NUTS, because the conditionals in NUTS are hard to execute in SIMD fashion. There’s a very nice introduction to this problem by Sountsov, Carroll, and Hoffman, in their paper “Running Markov Chain Monte Carlo on Modern Hardware and Software,” which is out on arXiv and also going into the next edition of the Handbook of MCMC). The thing to read about how to code NUTS on GPU is Dance, Glaser, Orbanz, and Adams’s paper, “Efficiently Vectorized MCMC on Modern Accelerators,” which is on arXiv and ICML 2025.
You can also randomize step size to vary the integration time and avoid harmonics, e.g.,
Randomized Hamiltonian Monte Carlo. 2017. Bou-Rabee and Sanz-Serna. Annals of Applied Probability.
robustified Hamiltonian
Posted in Books, Statistics, University life with tags Gregynog, Hamiltonian, HMC, leapfrog integrator, non-reversible MCMC, NUTS, randomised HMC, single malt, University of Warwick, Wales on April 1, 2022 by xi'an
In Gregynog, last week, Lionel Riou-Durant (Warwick) presented his recent work with Jure Vogrinc on Metropolis Adjusted Langevin Trajectories, which I had also heard in the Séminaire Parisien de Statistique two weeks ago. Starting with a nice exposition of Hamiltonian Monte Carlo, highlighting its drawbacks. This includes the potentially damaging impact of poorly tuning the integration time. Their proposal is to act upon the velocity in the Hamiltonian through Langevin (positive) damping, which also preserves the stationarity. (And connects with randomised HMC.) One theoretical in the paper is that the Langevin diffusion achieves the fastest mixing rate among randomised HMCs. From a practical perspective, there exists a version of the leapfrog integrator that adapts to this setting and can be implemented as a Metropolis adjustment. (Hence the MALT connection.) An interesting feature is that the process as such is ergodic, which avoids renewal steps (and U-turns). (There are still calibration parameters to adjust, obviously.)
unbiased Hamiltonian Monte Carlo with couplings
Posted in Books, Kids, Statistics, University life with tags Biometrika, discussion paper, Hamiltonian Monte Carlo, leapfrog integrator, maximal coupling, Royal Statistical Society, unbiased MCMC on October 25, 2019 by xi'an
In the June issue of Biometrika, which had been sitting for a few weeks on my desk under my teapot!, Jeremy Heng and Pierre Jacob published a paper on unbiased estimators for Hamiltonian Monte Carlo using couplings. (Disclaimer: I was not involved with the review or editing of this paper.) Which extends to HMC environments the earlier paper of Pierre Jacob, John O’Leary and Yves Atchadé, to be discussed soon at the Royal Statistical Society. The fundamentals are the same, namely that an unbiased estimator can be produced from a converging sequence of estimators and that it can be de facto computed if two Markov chains with the same marginal can be coupled. The issue with Hamiltonians is to figure out how to couple their dynamics. In the Gaussian case, it is relatively easy to see that two chains with the same initial momentum meet periodically. In general, there is contraction within a compact set (Lemma 1). The coupling extends to a time discretisation of the Hamiltonian flow by a leap-frog integrator, still using the same momentum. Which roughly amounts in using the same random numbers in both chains. When defining a relaxed meeting (!) where both chains are within δ of one another, the authors rely on a drift condition (8) that reminds me of the early days of MCMC convergence and seem to imply the existence of a small set “where the target distribution [density] is strongly log-concave”. And which makes me wonder if this small set could be used instead to create renewal events that would in turn ensure both stationarity and unbiasedness without the recourse to a second coupled chain. When compared on a Gaussian example with couplings on Metropolis-Hastings and MALA (Fig. 1), the coupled HMC sees hardly any impact of the dimension of the target (in the average coupling time), with a much lower value. However, I wonder at the relevance of the meeting time as an assessment of efficiency. In the sense that the coupling time is not a convergence time but reflects as well on the initial conditions. I acknowledge that this allows for an averaging over parallel implementations but I remain puzzled by the statement that this leads to “estimators that are consistent in the limit of the number of replicates, rather than in the usual limit of the number of Markov chain iterations”, since a particularly poor initial distribution could on principle lead to a mode of the target being never explored or on the coupling time being ever so rarely too large for the computing abilities at hand.
