CaltechAUTHORS
  A Caltech Library Service

Optimal tuning of the hybrid Monte Carlo algorithm

Beskos, Alexandros and Pillai, Natesh and Roberts, Gareth and Sanz-Serna, Jesus-Maria and Stuart, Andrew (2013) Optimal tuning of the hybrid Monte Carlo algorithm. Bernoulli, 19 (5A). pp. 1501-1534. ISSN 1350-7265 . https://resolver.caltech.edu/CaltechAUTHORS:20160726-155502558

[img] PDF - Published Version
See Usage Policy.

382Kb
[img] PDF - Submitted Version
See Usage Policy.

459Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160726-155502558

Abstract

We investigate the properties of the hybrid Monte Carlo algorithm (HMC) in high dimensions. HMC develops a Markov chain reversible with respect to a given target distribution Π using separable Hamiltonian dynamics with potential −logΠ−log⁡Π. The additional momentum variables are chosen at random from the Boltzmann distribution, and the continuous-time Hamiltonian dynamics are then discretised using the leapfrog scheme. The induced bias is removed via a Metropolis–Hastings accept/reject rule. In the simplified scenario of independent, identically distributed components, we prove that, to obtain an O(1) acceptance probability as the dimension dd of the state space tends to ∞, the leapfrog step size hh should be scaled as h=l×d^(−1/4). Therefore, in high dimensions, HMC requires O(d^(1/4)) steps to traverse the state space. We also identify analytically the asymptotically optimal acceptance probability, which turns out to be 0.651 (to three decimal places). This value optimally balances the cost of generating a proposal, which decreases as l increases (because fewer steps are required to reach the desired final integration time), against the cost related to the average number of proposals required to obtain acceptance, which increases as l increases.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.3150/12-BEJ414DOIArticle
http://projecteuclid.org/euclid.bj/1383661192#infoPublisherArticle
https://arxiv.org/abs/1001.4460arXivDiscussion Paper
Additional Information:© 2013 ISI/BS. Received February 2011 and revised October 2011. We thank Sebastian Reich for drawing our attention to the paper [18], which sparked our initial interest in the scaling issue for HMC. We also thank Gabriel Stoltz and Robert D. Skeel for stimulating discussions and useful comments. NP gratefully acknowledges the NSF Grant DMS 1107070; JMS gratefully acknowledges the Grant TM2010-18246-C03 by Ministerio de Ciencia e Innovacion, Spain; AS is grateful to EPSRC and ERC for financial support. Part of this work was done when NP was a postdoctoral member of CRiSM, University of Warwick, and visited JMS at University of Valladolid, so we thank both these institutions for their warm hospitality. Finally, we thank two referees for their comments that greatly improved the content and presentation of the paper.
Funders:
Funding AgencyGrant Number
NSFDMS 1107070
Ministerio de Ciencia e Innovacion (MINECO)TM2010-18246-C03
Engineering and Physical Sciences Research Council (EPSRC)UNSPECIFIED
European Research Council (ERC)UNSPECIFIED
Subject Keywords:Hamiltonian dynamics; high dimensions; optimal acceptance probability; leapfrog scheme; squared jumping distance
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Andrew StuartJ106
Issue or Number:5A
Record Number:CaltechAUTHORS:20160726-155502558
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160726-155502558
Official Citation:Beskos, Alexandros; Pillai, Natesh; Roberts, Gareth; Sanz-Serna, Jesus-Maria; Stuart, Andrew. Optimal tuning of the hybrid Monte Carlo algorithm. Bernoulli 19 (2013), no. 5A, 1501--1534. doi:10.3150/12-BEJ414. http://projecteuclid.org/euclid.bj/1383661192.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:69235
Collection:CaltechAUTHORS
Deposited By: Linda Taddeo
Deposited On:26 Jul 2016 23:50
Last Modified:03 Oct 2019 10:20

Repository Staff Only: item control page