{
  "id": "1707.03663",
  "version": "v1",
  "published": "2017-07-12T12:08:55.000Z",
  "updated": "2017-07-12T12:08:55.000Z",
  "title": "Underdamped Langevin MCMC: A non-asymptotic analysis",
  "authors": [
    "Xiang Cheng",
    "Niladri S. Chatterji",
    "Peter L. Bartlett",
    "Michael I. Jordan"
  ],
  "comment": "20 pages",
  "categories": [
    "stat.ML",
    "cs.LG",
    "stat.CO"
  ],
  "abstract": "We study the underdamped Langevin diffusion when the log of the target distribution is smooth and strongly concave. We present a MCMC algorithm based on its discretization and show that it achieves $\\varepsilon$ error (in 2-Wasserstein distance) in $\\mathcal{O}(\\sqrt{d}/\\varepsilon)$ steps. This is a significant improvement over the best known rate for overdamped Langevin MCMC, which is $\\mathcal{O}(d/\\varepsilon^2)$ steps under the same smoothness/concavity assumptions. The underdamped Langevin MCMC scheme can be viewed as a version of Hamiltonian Monte Carlo (HMC) which has been observed to outperform overdamped Langevin MCMC methods in a number of application areas. We provide quantitative rates that support this empirical wisdom.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-07-12T12:08:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "non-asymptotic analysis",
      "outperform overdamped langevin mcmc methods",
      "underdamped langevin mcmc scheme",
      "hamiltonian monte carlo",
      "underdamped langevin diffusion"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}