This post is from Bob
This one’s a big deal.
Bou-Rabee, Nawaf. 2026. Persistence Pays: Square-root condition-number dependence for Metropolis-adjusted kinetic Langevin Monte Carlo with a non-reversibly updated accept/reject uniform. arXiv 2610.35781.
Abstract: We prove accelerated mixing for a Metropolis-adjusted kinetic Langevin sampler: the OBABO splitting with friction 2 * sqrt(m), adjusted with Neal’s non-reversibly updated uniform, which is redrawn after every epoch of E steps. For targets exp(−U) on ℝ^d with m * I ⪯ ∇^2 U ⪯ L * I and an L_H-Lipschitz Hessian, started from a Gaussian at an approximate minimizer, the chain reaches total variation accuracy ε after Õ(sqrt(κ * d) + sqrt(L_H) * (d/m)^0.75) gradient evaluations, where κ=L/m and Õ hides logarithmic factors. The sqrt(κ) term is necessary, already on Gaussian targets. The proof discretizes Lu’s entropic hypocoercivity by means of an entropy inequality for free transport, so that the relative entropy of the unadjusted chain decays at a rate of order sqrt(m) up to a discretization bias. With the non-reversibly updated uniform, the leading energy errors of velocity Verlet telescope along a path. A coupling argument combines the two. On Bayesian logistic regression posteriors for two standard data sets, which satisfy these assumptions, the gradient cost of the chain with the non-reversibly updated uniform grows roughly like the square root of the condition number at the posterior mode, and that of standard adjusted OBABO roughly like its 3/4 power.
Note the square-root in the condition-number dependence. This is the tightest result we know for a discrete-step, adjusted sampler (i.e., one we can implement as a black-box). The full set of concavity and Lipschitz assumptions are in the abstract above (strongly log concave, Lipschitz in the Hessian). For what it’s worth, Claude (5.5 medium effort) concurs that nobody has proved a result this tight in condition number before.
The scales here get confusing, pardon my pun, so let’s establish some intuition from simple cases (skip this paragraph and the next if you know condition numbers). Suppose we have a multivariate normal distribution. The Hessian (matrix of second partial derivatives) of the negative log density is constant around the density and equal to the inverse of the covariance matrix. In general (i.e., not just for normals) for a point that is log concave (i.e., the Hessian is positive definite), the condition number is the ratio of the largest eigenvalue of that Hessian to the smallest eigenvalue. To simplify even further, suppose the covariance is diagonal, so that Sigma[m,m] represents the variance of variable m and all the off diagonal entries are zero (i.e., zero correlation). In that case, the eigenvalues are just the Sigma[m,m] and the condition number is just the ratio of the largest eigenvalue to the smallest eigenvalue. The problem for sampling with algorithms like random-walk Metropolis, Langevin, or Hamiltonian Monte Carlo, is that their run time is multiplied by the condition number. For a standard normal, where Sigma[m,m] is 1 for every m, the condition number is 1, and that’s the fastest we can get, because condition numbers are >= 1 by construction. That’s why we try to precondition our target posteriors with mass matrixes to make them (or their gradients in the case of Nutpie) look more normal (e.g., with non-centered parameterizations).
Why is posterior exploration time proportional to the condition number? It’s because we have to set the step size to accommodate the direction of highest curvature, then we have to take a number of steps traverse the scale of the direction of lowest curvature. For all of these samplers, traversing a distance takes quadratic time. So the algorithm is quadratic in the ratio of scales, which makes it linear in the condition number.
This is why reducing the condition number is so appealing. Sparse NUTS, from Cole Monnahan, works exceptionally well for mixed-effects models by preconditioning with a sparse Hessian located at the max marginal likelihood estimate (e.g., the estimate produced by lme4 or TMB). Note to Stan devs: We should adapt this for brms through TMB—it’s too model specific for Stan and we don’t have the linear algebra tools we need built into C++.
Why is this paper such a breakthrough? The assumptions on which the guarantee is based are standard in theoretical work, namely that the density must be strictly log concave with Lipschitz-bounded Hessians. Bou-Rabee establishes that generalized Hamiltonian Monte Carlo with one step (aka “kinetic Langevin”) has run time that grows only with the square root of the condition number! This kinetic or generalized part of the algorithm refers to the way momentum is refreshed. Rather than fully refreshing momentum, a new momentum is taken and averaged with the existing momentum at a fixed mixing rate (which could presumably be randomized, but not made dependent on state). The bottom line is that run time for a fixed level of accuracy grows with the ratio of scales (i.e., the square root of the condition) rather than the ratio of squared scales (i.e., the condition number). And unlike something like NUTS or WALNUTS, swapping in a new acceptance probability sequence couldn’t be much easier to implement.
Why is this a big deal? The main obstacle to Stan’s sampling, as I’ve just realized while building Walnuts and Walnutpie and evaluating on a ton of real-world models, is that the condition number remains high in most posteriordb models and models Andrew’s suggested, even after diagonal preconditioning with a mass matrix using either the NUTS or Nutpie divergence target. A ratio of scales as low as 10 will cause a 100-fold slowdown in sampling. That is, if I sample normal(0, diag_matrix([1, 10]’)) in Stan, it’s 100 times slower than if I sample normal(0, diag_matrix[1, 1]). The low-rank and diagonal approach from Nutpie helps here where it’s stable, but so far I haven’t found it to be as stable as the diagonal preconditioned in my evaluations.
The algorithm that Bou-Rabee analyzed was introduced by Radford Neal in the following paper, which I thought I had discussed here before, but can’t find any trace.
Neal, Radford. 2020. Non-reversibly updating a uniform [0,1] value for Metropolis accept/reject decisions. arXiv 2001.11950.
This paper is typical of Neal’s paper, introducing a very simple idea with a profound effect that’s explained so that a beginner can understand it and code it. We used it as a reference for my work with Gilad Turok and Chirag Modi (and also Alex Barnett) on delayed rejection generalized HMC, which I’ve blogged as Multiscale generalized HMC with delayed rejection.
I’m still a bit confused about how the regular condition number works compared to the one Langmore et al. generated for normal targets in HMC, which I blogged about as Condition numbers for HMC and the funnel. Nawaf told me before that Langmore’s work was only for normals, but it still seems relevant.
I better get busy adding this algorithm to Walnutpie. I’d planned to do it at some future date, but it looks like this is probably the sampler we should be using everywhere. Stay tuned for more evaluation.
Quote from the blog post: “The algorithm that Bou-Rabee analyzed was introduced by Radford Neal in the following paper, which I thought I had discussed here before, but can’t find any trace.”
If I am not mistaken the paper is mentioned in a post by Mr. Carpenter on this blog. This might explain things as well: the paper has been mentioned on this blog here before, but the author of the blog post was Mr. Carpenter and not you:
https://statmodeling.stat.columbia.edu/2024/04/24/gist-gibbs-self-tuning-for-hmc/
“This might explain things as well: the paper has been mentioned on this blog here before, but the author of the blog post was Mr. Carpenter and not you:”
My bad, the current post is also written by Mr. Carpenter. This is the second time this multiple authors on this blog here makes me mess something up. Anyway, hopefully the link to the older post might help here.
I’ll take responsibility here. I should always write “This post is from Bob” up top because otherwise people assume they’re all from Andrew. I edited to clarify.
Thanks for finding the old reference. I couldn’t find where else I had talked about it.
P.S. I prefer “Bob.” So much so that Andrew and I used to get a lot of mail around Stan that opened with “Dear Professor Gelman and Bob:” :-).
Even though I almost always start AND END each of my posts with “This post is by Phil”, or some variant of that, it is fairly frequent for at least some commenters to give Andrew the credit or blame. Still, one may as well try.
Interesting…my experience is with deterministic linear algebra, where algorithm runtime depends on condition number in similar ways and for similar reasons. I did not know this translated over to stochastic algorithms as well.
Unrelatedly, “OBABO” reminded me of this meme: https://knowyourmeme.com/photos/46177-unitinu-uniti%D0%B8u
Bob (and Nawaf):
This is interesting, and it reminds me that when I first heard of Hamiltonian Monte Carlo many years ago, I thought it was just an algorithm that did a Metropolis-corrected version of a Hamiltonian path. (I didn’t understand the geometry well enough to understand that this would not work because it wouldn’t go up and down the potential-energy ladder). Then I learned that HMC does an approximate Hamiltonian path at each iteration, but the iterations are started independently. Which always seemed wrong, but I supposed that the idea was that you’d get the Hamiltonian dynamics from the steps in each iteration. And, indeed, in many problems HMC (or variants such as Nuts) work just fine, with effective sample sizes that are close to the number of iterations. But it’s appealing to see that this new algorithm has dependence from one iteration to the next. I never would’ve guessed the bit about the condition number; it’s just good to see that some of the intuition applies here.
This also makes me wonder whether it would make sense to be working with some locally adaptive version of expected squared jumped distance.
Bob, thank you for such a generous post. Few people know this area as well as you do, so it’s especially meaningful. And thanks, Andrew, for the comment.
The dependence from one iteration to the next is indeed what helps here. Kinetic Langevin keeps the momentum and refreshes it a little at every step, much like momentum methods in optimization. As Bob explains, what had stood in the way were the rejections: to keep the target invariant, each rejection has to reverse the momentum, which sends the chain back the way it came. Neal’s non-reversible uniform avoids these reversals by keeping rejections rare over long stretches, and that turned out to be crucial for the proof.
On your last point, we’re working on exactly that: tuning on the fly how much momentum carries over from one step to the next (the friction). Expected squared jumped distance seems like a natural quantity to optimize locally.
Fo I understand correctly that the dynamics is start at state S, with a position and velocity… take one time step to S2, then update the velocity by adding a random perturbation and repeat?
Thats literally a variant on this algorithm I proposed in 2017 yes ?
https://discourse.mc-stan.org/t/momentum-diffusion-hmc/1526
Specifically partway down that post I have
q[i+1] = q[i] + dt p[i]
p[i+1] = p[i] + dt F(q[i]) + dp[i]
q is position, p is momentum/velocity, and F is the – gradient of the potential (ie. the force)
dp is then the partial renewal of the momentum at each time step by a random perturbation in momentum
Horowitz developed the generalized HMC algorithm that does partial momentum refresh in 1991:
https://cds.cern.ch/record/222436/files/199110129.pdf
Nobody could ever get it to work because you have to flip momentum on rejects. So you need to take very small step sizes to make directed progress, but that then requires a lot of steps and you’re back to exponential decay in acceptance.
Neal took Horowitz’s algorithm and swapped out the i.i.d. uniform(0, 1) draws for acceptance, coupled them into the Markov chain, then added a sawtooth pattern (non-reversible) update. That clusters the low values for long sequences of acceptances, allowing it to reliably make directed progress.
cool, I will have to look into those papers tomorrow. thanks for the high level overview.
I was initially confused by the time to total variation accuracy epsilon not depending on epsilon (!), but I see from the actual paper that the O-tilde notation suppresses a log(1/epsilon) multiplier
I had never seen seen the Õ notation before and had to look it up :-). I’m not even sure if people use it to simplify notation or because they don’t actually know the form of the polylog terms. It does make me curious about what happens when ε >= 1 and log(1 / ε) <= 0?