# NUTS vs HMC

**URL:** <https://discourse.mc-stan.org/t/nuts-vs-hmc/16453>\
**Category:** Algorithms\
**Created:** [July 8, 2020, 4:04pm UTC](https://discourse.mc-stan.org/t/nuts-vs-hmc/16453 "2020-07-08T16:04:54Z")\
**Posts on this page:** 1\
**Showing post:** 4

<div class="post-metadata">

**Author:** ![betanalpha](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/betanalpha/32/4_2.png) [@betanalpha](https://discourse.mc-stan.org/u/betanalpha)\
**Post date:** [July 9, 2020, 2:27am UTC](https://discourse.mc-stan.org/t/nuts-vs-hmc/16453/4 "2020-07-09T02:27:55Z")

</div>

> [@ma850](#):
>
> I understand HMC and its shortcomings that led to NUTS. However, I do not understand a few things about NUTS:

First let’s clear up the terminology.

“Hamiltonian Monte Carlo” is a technique for designing algorithms that utilize numerical Hamiltonian trajectories.

The original implementation of Hamiltonian Monte Carlo was “Hybrid Monte Carlo” which used static integration times (fixed number of steps) to construct a Metropolis proposal; this algorithm is also unfortunately commonly referred to as “Hamiltonian Monte Carlo” which only confused everything.

The “No-U-Turn Sampler” was the first practical implementation of _dynamic_ Hamiltonian Monte Carlo which utilizes adaptive integration times, where the number of leapfrog steps can vary. In particular the No-U-Turn sampler is _not_ a Metropolis algorithm. The implementation also included specific adaptation algorithms for the sampler configurations that remained fixed, namely the integrator step size and the inverse Euclidean metric that defines the kinetic energy.

“Exhaustive Hamiltonian Monte Carlo”, or “XHMC”, is another dynamic Hamiltonian Monte Carlo algorithm that utilizes a different criterion for determining how long the numerical Hamiltonian trajectories should grow at each iteration.

Currently Stan uses an advanced dynamic Hamiltonian Monte Carlo algorithm that is _not_ the No-U-Turn sampler. Just about every element of the algorithm has been improved based on theoretical guidance supported by empirical studies.

Because the current algorithm has been in continuous development over the past few years I never branded it with a new name, which has unfortunately caused confusion due to the common presumption that Stan simply implements the original No-U-Turn sampler. Long story short there was a decision to rename the algorithm at one point but governmental issues prevented that from moving forwards.

> [@ma850](#):
>
> Why does NUTS need to go both forward and backwards in time to figure out if there is a u-turn

Hamiltonian Monte Carlo methods need to correct correct for the error introduced by the numerical integrator which requires careful statistical methods.

Hybrid Monte Carlo, for example, uses a Metropolis correction to select between the initial point and the final point, but in order for that to work the numerical Hamiltonian trajectory has to be modified into an _involution_ by flipping the momenta of the final state.

Dynamic Hamiltonian Monte Carlo methods typically use more sophisticated corrections. Really the best way to think about these corrections is via a two step sequence – sample an entire numerical trajectory from the set of numerical trajectories that include the initial point, and then sample a point from that sampled trajectory using the right weights. Randomly integrating backwards and forwards is just a clever way of sampling from the set of numerical trajectories that include the initial point.

> [@ma850](#):
>
> Is the momentum vector r sampled at each substep or do we have only one r for each NUTS ‘big’ step

Each iteration of dynamic Hamiltonian Monte Carlo first samples a momenta, then builds a trajectory, then samples a point from that trajectory. Within an iteration momenta are influenced only by the deterministic Hamiltonian dynamics.

> [@ma850](#):
>
> Stan’s version of NUTS chooses the final parameter value based on multinominal sampling with a bias towards later substeps. How does this relate to the target acceptance probability?

Because Stan’s dynamic Hamiltonian Monte Carlo algorithm, which again is not the No-U-Turn sampler, is not a Metropolis algorithm there is no acceptance probability.

Stan does include an _acceptance statistic_ which is a sort of proxy of an average Metropolis acceptance to guide the step size adaptation.

> [@ma850](#):
>
> Are the substeps that are considered in multinomial sampling only the 2nd, 4th, 8th etc. or is every substep considered?

All of the points in the numerical Hamiltonian trajectory are considered.

> [@ma850](#):
>
> I have read various sources on this, however, they all are either too technical or do not go in detail.

The challenge is that the mathematics of Hamiltonian Monte Carlo are fundamentally difficult, so it’s nearly impossible to provide principled motivation for each step without going into a decent amount of detail. For example my review [https://arxiv.org/abs/1701.02434](https://arxiv.org/abs/1701.02434) is my best attempt at going only into detail relevant for practical implementations, and even that has plenty of technical detail.

---

_[View the full topic](https://discourse.mc-stan.org/t/nuts-vs-hmc/16453)._