Irreversible Monte Carlo algorithms for efficient sampling

Konstantin S. Turitsyn; Michael Chertkov; Marija Vucelja

doi:10.1016/j.physd.2010.10.003

Irreversible Monte Carlo algorithms for efficient sampling

Konstantin S. Turitsyn, Michael Chertkov, Marija Vucelja

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

100 Scopus citations

Abstract

Equilibrium systems evolve according to Detailed Balance (DB). This principle guided the development of Monte Carlo sampling techniques, of which the MetropolisHastings (MH) algorithm is the famous representative. It is also known that DB is sufficient but not necessary. We construct irreversible deformation of a given reversible algorithm capable of dramatic improvement of sampling from known distribution. Our transformation modifies transition rates keeping the structure of transitions intact. To illustrate the general scheme we design an Irreversible version of MetropolisHastings (IMH) and test it on an example of a spin cluster. Standard MH for the model suffers from critical slowdown, while IMH is free from critical slowdown.

Original language	English (US)
Pages (from-to)	410-414
Number of pages	5
Journal	Physica D: Nonlinear Phenomena
Volume	240
Issue number	4-5
DOIs	https://doi.org/10.1016/j.physd.2010.10.003
State	Published - Feb 15 2011
Externally published	Yes

Keywords

MCMC algorithms
Mixing
Monte Carlo methods

ASJC Scopus subject areas

Statistical and Nonlinear Physics
Mathematical Physics
Condensed Matter Physics
Applied Mathematics

Access to Document

10.1016/j.physd.2010.10.003

Cite this

@article{2c119d196f384ba5b2c57e0113f51598,

title = "Irreversible Monte Carlo algorithms for efficient sampling",

abstract = "Equilibrium systems evolve according to Detailed Balance (DB). This principle guided the development of Monte Carlo sampling techniques, of which the MetropolisHastings (MH) algorithm is the famous representative. It is also known that DB is sufficient but not necessary. We construct irreversible deformation of a given reversible algorithm capable of dramatic improvement of sampling from known distribution. Our transformation modifies transition rates keeping the structure of transitions intact. To illustrate the general scheme we design an Irreversible version of MetropolisHastings (IMH) and test it on an example of a spin cluster. Standard MH for the model suffers from critical slowdown, while IMH is free from critical slowdown.",

keywords = "MCMC algorithms, Mixing, Monte Carlo methods",

author = "Turitsyn, {Konstantin S.} and Michael Chertkov and Marija Vucelja",

note = "Funding Information: The authors are grateful to V. Chernyak, F. Krzakala, J. Machta, D. Shah and T. Witten for inspiring discussions and useful remarks. The work at LANL was carried out under the auspices of the National Nuclear Security Administration of the US Department of Energy at Los Alamos National Laboratory under Contract No. DE-AC52-06NA25396 . MC also acknowledges the Weston Visiting Professorship Program supporting his stay at the Weizmann Institute, where part of this work was done. ",

year = "2011",

month = feb,

day = "15",

doi = "10.1016/j.physd.2010.10.003",

language = "English (US)",

volume = "240",

pages = "410--414",

journal = "Physica D: Nonlinear Phenomena",

issn = "0167-2789",

publisher = "Elsevier B.V.",

number = "4-5",

}

TY - JOUR

T1 - Irreversible Monte Carlo algorithms for efficient sampling

AU - Turitsyn, Konstantin S.

AU - Chertkov, Michael

AU - Vucelja, Marija

N1 - Funding Information: The authors are grateful to V. Chernyak, F. Krzakala, J. Machta, D. Shah and T. Witten for inspiring discussions and useful remarks. The work at LANL was carried out under the auspices of the National Nuclear Security Administration of the US Department of Energy at Los Alamos National Laboratory under Contract No. DE-AC52-06NA25396 . MC also acknowledges the Weston Visiting Professorship Program supporting his stay at the Weizmann Institute, where part of this work was done.

PY - 2011/2/15

Y1 - 2011/2/15

N2 - Equilibrium systems evolve according to Detailed Balance (DB). This principle guided the development of Monte Carlo sampling techniques, of which the MetropolisHastings (MH) algorithm is the famous representative. It is also known that DB is sufficient but not necessary. We construct irreversible deformation of a given reversible algorithm capable of dramatic improvement of sampling from known distribution. Our transformation modifies transition rates keeping the structure of transitions intact. To illustrate the general scheme we design an Irreversible version of MetropolisHastings (IMH) and test it on an example of a spin cluster. Standard MH for the model suffers from critical slowdown, while IMH is free from critical slowdown.

AB - Equilibrium systems evolve according to Detailed Balance (DB). This principle guided the development of Monte Carlo sampling techniques, of which the MetropolisHastings (MH) algorithm is the famous representative. It is also known that DB is sufficient but not necessary. We construct irreversible deformation of a given reversible algorithm capable of dramatic improvement of sampling from known distribution. Our transformation modifies transition rates keeping the structure of transitions intact. To illustrate the general scheme we design an Irreversible version of MetropolisHastings (IMH) and test it on an example of a spin cluster. Standard MH for the model suffers from critical slowdown, while IMH is free from critical slowdown.

KW - MCMC algorithms

KW - Mixing

KW - Monte Carlo methods

UR - http://www.scopus.com/inward/record.url?scp=78650923207&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650923207&partnerID=8YFLogxK

U2 - 10.1016/j.physd.2010.10.003

DO - 10.1016/j.physd.2010.10.003

M3 - Article

AN - SCOPUS:78650923207

SN - 0167-2789

VL - 240

SP - 410

EP - 414

JO - Physica D: Nonlinear Phenomena

JF - Physica D: Nonlinear Phenomena

IS - 4-5

ER -

Irreversible Monte Carlo algorithms for efficient sampling

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this