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

^*Corresponding author for this work

School of Mathematics

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(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.

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 - 31 Aug 2017

Keywords / Materials (for Non-textual outputs)

Weak convergence
Markov chain Monte Carlo
diffusion limit
exponential ergodicity
METROPOLIS-HASTINGS ALGORITHMS
TRANSIENT PHASE
CONVERGENCE
APPROXIMATIONS
DIFFUSIONS
EQUATIONS

Access to Document

10.1214/16-AAP1257

1507.02166v2Accepted author manuscript, 565 KB
1507.02166Accepted author manuscript, 570 KB

Cite this

@article{2d5447f6dae74c75ab7584fe6b3f3d76,

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 = "Weak convergence, Markov chain Monte Carlo, diffusion limit, exponential ergodicity, METROPOLIS-HASTINGS ALGORITHMS, TRANSIENT PHASE, CONVERGENCE, APPROXIMATIONS, DIFFUSIONS, EQUATIONS",

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

year = "2017",

month = aug,

day = "31",

doi = "10.1214/16-AAP1257",

language = "English",

volume = "27",

pages = "2195--2237",

journal = "Annals of Applied Probability",

issn = "1050-5164",

publisher = "Institute of Mathematical Statistics",

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.

PY - 2017/8/31

Y1 - 2017/8/31

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 - Weak convergence

KW - Markov chain Monte Carlo

KW - diffusion limit

KW - exponential ergodicity

KW - METROPOLIS-HASTINGS ALGORITHMS

KW - TRANSIENT PHASE

KW - CONVERGENCE

KW - APPROXIMATIONS

KW - DIFFUSIONS

KW - EQUATIONS

U2 - 10.1214/16-AAP1257

DO - 10.1214/16-AAP1257

M3 - Article

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 / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this