Ergodicity of the infinite swapping algorithm at low temperature

Georg Menz, André Schlichting, Wenpin Tang and Tianqi Wu

Stochastic Processes and their Applications, 2022, vol. 151, issue C, 519-552

Abstract: Sampling Gibbs measures at low temperatures is an important but computationally challenging task. Numerical evidence suggests that the infinite-swapping algorithm (isa) is a promising method. The isa can be seen as an improvement of the parallel tempering replica method. We rigorously analyze the ergodic properties of the isa in the low temperature regime, deducing asymptotic estimates for the spectral gap (or Poincaré constant), optimal in dimension one, and an estimate for the log-Sobolev constant. Our main results indicate that the effective energy barrier can be reduced drastically using the isa compared to the classical over-damped Langevin dynamics. As a corollary, we derive a concentration inequality showing that sampling is also improved by an exponential factor. Finally, we study simulated annealing for the isa and prove that the isa again outperforms the over-damped Langevin dynamics.

Keywords: Sampling; Low-temperature; Simulated annealing; Infinite swapping; Spectral gap; Eyring–Kramers formula (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S030441492200151X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:151:y:2022:i:c:p:519-552

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2022.06.015

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().