Can somebody explain to me NUTS in english?

Question

My understanding of the algorithm is the following:

No U-Turn Sampler (NUTS) is a Hamiltonian Monte Carlo Method. This means that it is not a Markov Chain method and thus, this algorithm avoids the random walk part, which is often deemed as inefficient and slow to converge.

Instead of doing the random walk, NUTS does jumps of length x. Each jump doubles as the algorithm continues to run. This happens until the trajectory reaches a point where it wants to return to the starting point.

My questions: What is so special about the U-turn? How does doubling the trajectory not skip the optimized point? Is my above description correct?

Answer 1

The no U-turn bit is how proposals are generated. HMC generates a hypothetical physical system: imagine a ball with a certain kinetic energy rolling around a landscape with valleys and hills (the analogy breaks down with more than 2 dimensions) defined by the posterior you want to sample from. Every time you want to take a new MCMC sample, you randomly pick the kinetic energy and start the ball rolling from where you are. You simulate in discrete time steps, and to make sure you explore the parameter space properly you simulate steps in one direction and the twice as many in the other direction, turn around again etc. At some point you want to stop this and a good way of doing that is when you have done a U-turn (i.e. appear to have gone all over the place).

At this point the proposed next step of your Markov Chain gets picked (with certain limitations) from the points you have visited. I.e. that whole simulation of the hypothetical physical system was "just" to get a proposal that then gets accepted (the next MCMC sample is the proposed point) or rejected (the next MCMC sample is the starting point).

The clever thing about it is that proposals are made based on the shape of the posterior and can be at the other end of the distribution. In contrast Metropolis-Hastings makes proposals within a (possibly skewed) ball, Gibbs sampling only moves along one (or at least very few) dimensions at a time.

Answer 2

You're incorrect that HMC is not a Markov Chain method. Per Wikipedia:

In mathematics and physics, the hybrid Monte Carlo algorithm, also known as Hamiltonian Monte Carlo, is a Markov chain Monte Carlo method for obtaining a sequence of random samples from a probability distribution for which direct sampling is difficult. This sequence can be used to approximate the distribution (i.e., to generate a histogram), or to compute an integral (such as an expected value).

For more clarity, read the arXiv paper by Betancourt, which mentions the NUTS terminating criteria:

... identify when a trajectory is long enough to yield sufficient exploration of the neighborhood around the current energy level set. In particular, we want to avoid both integrating too short, in which case we would not take full advantage of the Hamiltonian trajectories, and integrating too long, in which case we waste precious computational resources on exploration that yields only diminishing returns.

Appendix A.3 talks about something like the trajectory doubling you mention:

We can also expand faster by doubling the length of the trajectory at every iteration, yielding a sampled trajectory t ∼ T(t | z) = U T2L with the corresponding sampled state z′ ∼ T(z′ | t). In this case both the old and new trajectory components at every iteration are equivalent to the leaves of perfect, ordered binary trees (Figure 37). This allows us to build the new trajectory components recursively, propagating a sample at each step in the recursion...

and expands on this in A.4, where it talks about a dynamic implementation (section A.3 talks about a static implementation):

Fortunately, the efficient static schemes discussed in Section A.3 can be iterated to achieve a dynamic implementation once we have chosen a criterion for determining when a trajectory has grown long enough to satisfactory explore the corresponding energy level set.

I think the key is that it doesn't do jumps that double, it calculates its next jump using a technique that doubles the proposed jump's length until a criteria is met. At least that's how I understand the paper so far.