Ergodicity of the infinite swapping algorithm at low temperature

DOI10.1016/J.SPA.2022.06.015zbMATH Open1494.37008arXiv1811.10174OpenAlexW2900584796MaRDI QIDQ2157335FDOQ2157335

Authors: André Schlichting, Wenpin Tang, Tianqi Wu, Georg Menz 

Publication date: 27 July 2022

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Abstract: Sampling Gibbs measures at low temperatures is an important task but computationally challenging. Numerical evidence suggests that the infinite-swapping algorithm (isa) is a promising method. The isa can be seen as an improvement of the replica methods. We rigorously analyze the ergodic properties of the isa in the low temperature regime, deducing an Eyring-Kramers formula for the spectral gap (or Poincar'e constant) 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 overdamped Langevin dynamics. As a corollary, we derive a deviation 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 overdamped Langevin dynamics.

Full work available at URL: https://arxiv.org/abs/1811.10174

Recommendations

• A large deviations analysis of certain qualitative properties of parallel tempering and infinite swapping algorithms
• On the infinite swapping limit for parallel tempering
• On the swapping algorithm
• Methodological and computational aspects of parallel tempering methods in the infinite swapping limit
• On swapping and simulated tempering algorithms.

zbMATH Keywords

samplingsimulated annealingspectral gapEyring-Kramers formulainfinite swappinglow-temperature

Mathematics Subject Classification ID

Dynamical aspects of statistical mechanics (37A60) Thermodynamic formalism, variational principles, equilibrium states for dynamical systems (37D35) Classical equilibrium statistical mechanics (general) (82B05) Functional inequalities, including subadditivity, convexity, etc. (39B62)

Cites Work

• Bayesian data analysis.
• Optimization by simulated annealing
• Exponential convergence of Langevin distributions and their discrete approximations
• Title not available (Why is that?)
• Hypoelliptic estimates and spectral theory for Fokker-Planck operators and Witten Laplacians
• Metastability in reversible diffusion processes. I: Sharp asymptotics for capacities and exit times
• Metastability in reversible diffusion processes. II: Precise asymptotics for small eigenvalues
• Kramers law: validity, derivations and generalisations
• Title not available (Why is that?)
• Tunnel effect and symmetries for Kramers-Fokker-Planck type operators
• Title not available (Why is that?)
• Generalisation of the Eyring-Kramers transition rate formula to irreversible diffusion processes
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
• Lévy flights, non-local search and simulated annealing
• On the infinite swapping limit for parallel tempering
• Diffusions for Global Optimization
• Asymptotics of the spectral gap with applications to the theory of simulated annealing
• Title not available (Why is that?)
• Poincaré and logarithmic Sobolev inequalities by decomposition of the energy landscape
• A deviation inequality for non-reversible Markov processes
• deviation bounds for additive functionals of markov processes
• Hybrid parallel tempering and simulated annealing method
• Nonasymptotic convergence analysis for the unadjusted Langevin algorithm
• Theoretical Guarantees for Approximate Sampling from Smooth and Log-Concave Densities
• Large deviation principles for Markov processes via phi-Sobolev inequalities
• Recuit simulé sur \(\mathbb{R}{}^ n\). Étude de l'évolution de l'énergie libre. (Simulated annealing on \(\mathbb{R}{}^ n\). Study of the evolution of free energy)
• Hypocoercivity in metastable settings and kinetic simulated annealing
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• A large deviations analysis of certain qualitative properties of parallel tempering and infinite swapping algorithms
• Sharp asymptotics of the first exit point density
• Exit event from a metastable state and Eyring-Kramers law for the overdamped Langevin dynamics
• Title not available (Why is that?)
• Title not available (Why is that?)
• The simulated tempering method in the infinite switch limit with adaptive weight learning
• Infinite Swapping Algorithm for Training Restricted Boltzmann Machines

Cited In (6)

• Methodological and computational aspects of parallel tempering methods in the infinite swapping limit
• Convergence of simulated annealing using kinetic Langevin dynamics
• A large deviations analysis of certain qualitative properties of parallel tempering and infinite swapping algorithms
• Discrete-time simulated annealing: a convergence analysis via the Eyring-Kramers law
• On the infinite swapping limit for parallel tempering
• Tail probability estimates of continuous-time simulated annealing processes

This page was built for publication: Ergodicity of the infinite swapping algorithm at low temperature

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2157335)