Fast langevin based algorithm for MCMC in high dimensions

Alain Durmus; Gareth O. Roberts; Gilles Vilmart; Konstantinos C. Zygalakis

doi:10.1214/16-AAP1257

Fast langevin based algorithm for MCMC in high dimensions

Alain Durmus, Gareth O. Roberts, Gilles Vilmart, Konstantinos C. Zygalakis

Research output: Contribution to journal › Article › peer-review

Abstract

We introduce new Gaussian proposals to improve the efficiency of the standard Hastings-Metropolis algorithm in Markov chain Monte Carlo (MCMC) methods, used for the sampling from a target distribution in large dimension d. The improved complexity is O(d^1/5) compared to the complexity O(d^1/3) of the standard approach. We prove an asymptotic diffusion limit theorem and show that the relative efficiency of the algorithm can be characterised by its overall acceptance rate (with asymptotical value 0.704), independently of the target distribution. Numerical experiments confirm our theoretical findings.

Original language	English
Pages (from-to)	2195-2237
Number of pages	43
Journal	Annals of Applied Probability
Volume	27
Issue number	4
DOIs	https://doi.org/10.1214/16-AAP1257
Publication status	Published - 1 Aug 2017
Externally published	Yes

Keywords

Diffusion limit
Exponential ergodicity
Markov chain Monte Carlo
Weak convergence

Access to Document

10.1214/16-AAP1257

Cite this

@article{4c01faca94fd492ba16fc652a0e5a96e,

title = "Fast langevin based algorithm for MCMC in high dimensions",

abstract = "We introduce new Gaussian proposals to improve the efficiency of the standard Hastings-Metropolis algorithm in Markov chain Monte Carlo (MCMC) methods, used for the sampling from a target distribution in large dimension d. The improved complexity is O(d1/5) compared to the complexity O(d1/3) of the standard approach. We prove an asymptotic diffusion limit theorem and show that the relative efficiency of the algorithm can be characterised by its overall acceptance rate (with asymptotical value 0.704), independently of the target distribution. Numerical experiments confirm our theoretical findings.",

keywords = "Diffusion limit, Exponential ergodicity, Markov chain Monte Carlo, Weak convergence",

author = "Alain Durmus and Roberts, \{Gareth O.\} and Gilles Vilmart and Zygalakis, \{Konstantinos C.\}",

note = "Publisher Copyright: {\textcopyright} Institute of Mathematical Statistics, 2017.",

year = "2017",

month = aug,

day = "1",

doi = "10.1214/16-AAP1257",

language = "English",

volume = "27",

pages = "2195--2237",

journal = "Annals of Applied Probability",

issn = "1050-5164",

number = "4",

}

TY - JOUR

T1 - Fast langevin based algorithm for MCMC in high dimensions

AU - Durmus, Alain

AU - Roberts, Gareth O.

AU - Vilmart, Gilles

AU - Zygalakis, Konstantinos C.

N1 - Publisher Copyright: © Institute of Mathematical Statistics, 2017.

PY - 2017/8/1

Y1 - 2017/8/1

N2 - We introduce new Gaussian proposals to improve the efficiency of the standard Hastings-Metropolis algorithm in Markov chain Monte Carlo (MCMC) methods, used for the sampling from a target distribution in large dimension d. The improved complexity is O(d1/5) compared to the complexity O(d1/3) of the standard approach. We prove an asymptotic diffusion limit theorem and show that the relative efficiency of the algorithm can be characterised by its overall acceptance rate (with asymptotical value 0.704), independently of the target distribution. Numerical experiments confirm our theoretical findings.

AB - We introduce new Gaussian proposals to improve the efficiency of the standard Hastings-Metropolis algorithm in Markov chain Monte Carlo (MCMC) methods, used for the sampling from a target distribution in large dimension d. The improved complexity is O(d1/5) compared to the complexity O(d1/3) of the standard approach. We prove an asymptotic diffusion limit theorem and show that the relative efficiency of the algorithm can be characterised by its overall acceptance rate (with asymptotical value 0.704), independently of the target distribution. Numerical experiments confirm our theoretical findings.

KW - Diffusion limit

KW - Exponential ergodicity

KW - Markov chain Monte Carlo

KW - Weak convergence

U2 - 10.1214/16-AAP1257

DO - 10.1214/16-AAP1257

M3 - Article

AN - SCOPUS:85028724242

SN - 1050-5164

VL - 27

SP - 2195

EP - 2237

JO - Annals of Applied Probability

JF - Annals of Applied Probability

IS - 4

ER -

Fast langevin based algorithm for MCMC in high dimensions

Abstract

Keywords

Access to Document

Fingerprint

Cite this