I'm reading the original NUTS paper by Hoffman and Gelman, but couldn't fully understand the recursively doubling process.

The following figure is taken from the paper. enter image description here

The NUTS process starts with an initial state $(\theta, r)$ represented by the black circle, where $\theta$ is the target variable we are interested in, and $r$ the auxiliary momentum variable introduced in HMC. At each iteration, the process will randomly decide to do forward leapfrog integration or backward one.

In the illustration shown above, the first iteration is forward evolution, so the state at the light orange circle is obtained by one step of forward leapfrog integration from the state at the black circle.


During the doubling process, we add a state $(\theta', r')$ to the candidate set $\mathcal{C}$ if the state satisfies the condition $u \le exp{(\mathcal{L}(\theta') - \frac{1}{2} r' \cdot r')}$, where $u$ is the slice variable, $\mathcal{L}$ the logarithm of the (posterior) probability density of the target variable.

After the doubling process is terminated, we then randomly sample an element from $\mathcal{C}$.

My question is, why do we only sample one element from $\mathcal{C}$ ? Since all the elements in $\mathcal{C}$ are on the Leapfrog integration path and they all satisfy the criteria (see the paper for the C.1 - C.4 conditions), why can't we add all the elements in $\mathcal{C}$ to the samples?

  • $\begingroup$ My guess is that elements from the same leapfrog integration are too correlated to result in unbiased samples $\endgroup$
    – shouldsee
    Sep 8 '18 at 19:42
  • $\begingroup$ Because the samples are of varying size, which would give more weights to some iterations than to others. Now all simulations can be recycled into a Rao-Blackwell estimate, as recently shown by one of my PhD students. $\endgroup$
    – Xi'an
    Sep 8 '18 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.