The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo
By Matthew D. Hoffman, Andrew Gelman. 2011
5,283 citations recorded by the source corpus.
Hamiltonian Monte Carlo (HMC) is a Markov chain Monte Carlo (MCMC) algorithm that avoids the random walk behavior and sensitivity to correlated parameters 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 simpler 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 introduce 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. Empirically, NUTS perform at least as efficiently as and sometimes more efficiently than a well tuned standard HMC method, without requiring user intervention or costly tuning runs. We also derive a method for adapting the step size parameter {\epsilon} on the fly based on primal-dual averaging. NUTS can thus be used with no hand-tuning at all. NUTS is also suitable for applications such as BUGS-style automatic inference engines that require efficient "turnkey" sampling algorithms.
Subfields: Artificial Intelligence, Statistics and Probability, Probabilistic & Bayesian Methods
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Sergey Levine
- Mohit Bansal
- Quoc V. Le
- Ruslan Salakhutdinov
- Percy Liang
- Jianfeng Gao
- Eric P. Xing
In Statistics and Probability
- David M. Blei
- Paul-Christian Burkner
- Matthew D. Hoffman
- Andrew Gelman
- Qiang Liu
- Aki Vehtari
- Dustin Tran
- Stephan Mandt
In Probabilistic & Bayesian Methods
- David M. Blei
- Richard E. Turner
- Qiang Liu
- Michalis K. Titsias
- Andrew Gordon Wilson
- Matthew D. Hoffman
- Zoubin Ghahramani
- Dustin Tran
Citations in the corpus
- Composable Effects for Flexible and Accelerated Probabilistic Programming in NumPyro (2019, methodology): “The No-U-Turn Sampler (NUTS) [14] is an extension of the Hamiltonian Monte Carlo (HMC) algorithm [15, 16], which can efficiently sample from high-dimensional continuous probability distributions.”
- Pyro: Deep Universal Probabilistic Programming (2018, methodology): “Pyro implements several generic probabilistic inference algorithms, including the No U-turn Sampler (Hoffman and Gelman (2014)), a variant of Hamiltonian Monte Carlo.”
- Variational Inference: A Review for Statisticians (2016, methodology): “We compare CAVI to an implementation in Stan (Stan Development Team 2015), which uses a Hamiltonian Monte Carlo-based sampler (Hoffman and Gelman 2014).”
- Stochastic Gradient Hamiltonian Monte Carlo (2014, methodology): “Based on the attractive properties of HMC in terms of rapid exploration of the state space, HMC methods have grown in popularity in recent years (Neal, 2010; Hoffman and Gelman, 2011; Wang et al., 2013). ar X iv :1 40 2.”
- A deterministic and computable Bernstein-von Mises theorem (2019, methodology): “This is due to log-concave distributions being strongly concentrated around their posterior distribution (Pereyra [2016]).”
- Assumed Density Filtering Methods for Learning Bayesian Neural Networks (2016, methodology): “We also compute the posterior predictive density using standard backpropagation and the gold standard “ground-truth” density by averaging over 20, 000 samples from the No-U-Turn sampler (Hoffman and Gelman 2014) after a burn-in of 5000.”
- Stochastic Gradient Descent as Approximate Bayesian Inference (2017, methodology): “It uses stochastic gradients which gives it a competitive advantage over NUTS (which uses full gradients) in particular in the early search phase of the sampler.”
- Automatic differentiation in machine learning: a survey (2015, methodology): “For instance, the probabilistic programming language Stan22 implements automatic Bayesian inference based on HMC and the No-U-Turn sampler (NUTS) (Hoffman and Gelman, 2014) and uses reverse mode AD for the calculation of gradients for both HMC and NUTS.”
- Probabilistic programming in Python using PyMC3 (2016, methodology): “It features next-generation Markov chain Monte Carlo (MCMC) sampling algorithms such as the No-U-Turn Sampler (NUTS) (Homan and Gelman, 2014), a self-tuning variant of Hamiltonian Monte Carlo (HMC) (Duane et al., 1987).”
- Importance of Search and Evaluation Strategies in Neural Dialogue Modeling (2018, methodology): “Inference We use no-u-turn (NUTS) sampler (Hoffman and Gelman, 2014) for posterior inference in Pyro (Bingham et al., 2018).”
- Dialogue Natural Language Inference (2018, methodology): “Inference We use Pyro[1] and the no-u-turn sampler (NUTS)[6] for posterior inference.”
- Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm (2016, methodology): “We compared our algorithm with the no-U-turn sampler (NUTS)1 [29] and non-parametric variational inference (NPV)2 [5] on the 8 datasets (N > 500) used in Gershman et al.”