SpreadNUTS -- Moderate Dynamic Extension of Paths for No-U-Turn Sampling
  & Partitioning Visited Regions
Fareed Sheriff
Markov chain Monte Carlo (MCMC) methods have existed for a long time and the
field is well-explored. The purpose of MCMC methods is to approximate a
distribution through repeated sampling; most MCMC algorithms exhibit
asymptotically optimal behavior in that they converge to the true distribution
at the limit. However, what differentiates these algorithms are their practical
convergence guarantees and efficiency. While a sampler may eventually
approximate a distribution well, because it is used in the real world it is
necessary that the point at which the sampler yields a good estimate of the
distribution is reachable in a reasonable amount of time. Similarly, if it is
computationally difficult or intractable to produce good samples from a
distribution for use in estimation, then there is no real-world utility
afforded by the sampler. Thus, most MCMC methods these days focus on improving
efficiency and speeding up convergence. However, many MCMC algorithms suffer
from random walk behavior and often only mitigate such behavior as outright
erasing random walks is difficult. Hamiltonian Monte Carlo (HMC) is a class of
MCMC methods that theoretically exhibit no random walk behavior because of
properties related to Hamiltonian dynamics. This paper introduces modifications
to a specific HMC algorithm known as the no-U-turn sampler (NUTS) that aims to
explore the sample space faster than NUTS, yielding a sampler that has faster
convergence to the true distribution than NUTS.