NIPS 2011 Big Learning - Algorithms, Systems, & Tools Workshop: No-U-Turn Sampler...

Big Learning Workshop: Algorithms, Systems, and Tools for Learning at Scale at NIPS 2011 Invited Talk: The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo by Matt Hoffman Matt Hoffman is a postdoc working with Prof. Andrew Gelman at Columbia University. His did his Ph.D. at Princeton University in Computer Science working in the Sound Lab with Prof. Perry Cook and Prof. David Blei. Matt's research focuses on developing efficient Bayesian inference algorithms and on Bayesian modeling of audio, audio feature extraction, music information retrieval, and the application of music information retrieval and modeling techniques to musical synthesis. Abstract: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo Hamiltonian Monte Carlo (HMC) is a Markov Chain Monte Carlo (MCMC) algorithm that avoids the random walk behavior and sensitivity to correlations that plague many MCMC methods by taking a series of steps informed by first-order gradient information. These features allow it to converge to high-dimensional target distributions much more quickly than popular methods such as random walk Metropolis or Gibbs sampling. However, HMC's performance is highly sensitive to two user-specified parameters: a step size $\epsilon$ and a desired number of steps $L$. In particular, if $L$ is too small then the algorithm exhibits undesirable random walk behavior, while if $L$ is too large the algorithm wastes computation. We present the No-U-Turn Sampler (NUTS), an extension to HMC that eliminates the need to set a number of steps $L$. NUTS uses a recursive algorithm to build a set of likely candidate points that spans a wide swath of the target distribution, stopping automatically when it starts to double back and retrace its steps. NUTS is able to achieve similar performance to a well tuned standard HMC method, without requiring user intervention or costly tuning runs. NUTS can thus be used in applications such as BUGS-style automatic inference engines that require efficient "turnkey'' sampling algorithms.