Running time of NUTS using Big O notation?

Hi, I am writing up an analysis involving MCMC estimation of a model using Hamiltonian Monte Carlo with the No U-Turn Sampler. I am wondering, is there a description of the theoretical running time of the algorithm using Big O notation somewhere? I’m referring to the running time to conduct a hypothetical draw of a single parameter from its posterior distribution. I can give some insight to the reader regarding the number of parameters my model has, the number of warmup iterations, etc., but I am stuck at the point that I try to explain how long it takes for NUTS itself to do its sampling. The discussion that I have seen online all refers to the number of minutes a particular model takes to run, but I am hoping for a more theoretical description than that.

I recognize that this may be a somewhat naive question because the sampler is non-deterministic – after all, a worst-case running time would be that the algorithm would run forever, with samples improbably getting rejected all the time. But nonetheless, there should still be some notion of theoretical running time for a stochastic algorithm, right?

Thanks very much,


That is a random variable, so they best you would be able to do is perhaps say there is some expected number of leapfrog steps (and thus gradient evaluations and thus flops) on an iteration. It tends to be fairly constant after warmup for most models but not before.

The standard result for expected number of iterations to get an independent draw in Hamiltonian Monte Carlo is \mathcal{O}(N^{5/4}) whereas random-walk Metropolis is \mathcal{O}(N^2).

But there’s a huge invisible constant here for conditioning in the posterior, and it’s based on some approximations.

There’s a discussion on page 29 of Neal’s HMC overview paper:

I can’t recall where this is first proved or the assumptions it’s making on the distributions and don’t have time to unwind this all from the discussion in Neal’s overview. Someone else did this originally, but I don’t see a citation, either, and can’t recall who it was.