Ergodicity of the infinite swapping algorithm at low temperature
From MaRDI portal
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.
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.
Cites work
- scientific article; zbMATH DE number 5071766 (Why is no real title available?)
- scientific article; zbMATH DE number 4048925 (Why is no real title available?)
- scientific article; zbMATH DE number 1489880 (Why is no real title available?)
- scientific article; zbMATH DE number 2117879 (Why is no real title available?)
- scientific article; zbMATH DE number 7415116 (Why is no real title available?)
- scientific article; zbMATH DE number 2208078 (Why is no real title available?)
- A deviation inequality for non-reversible Markov processes
- A large deviations analysis of certain qualitative properties of parallel tempering and infinite swapping algorithms
- Asymptotics of the spectral gap with applications to the theory of simulated annealing
- Bayesian data analysis.
- Diffusions for Global Optimization
- Exit event from a metastable state and Eyring-Kramers law for the overdamped Langevin dynamics
- Exponential convergence of Langevin distributions and their discrete approximations
- Generalisation of the Eyring-Kramers transition rate formula to irreversible diffusion processes
- Hybrid parallel tempering and simulated annealing method
- Hypocoercivity in metastable settings and kinetic simulated annealing
- Hypoelliptic estimates and spectral theory for Fokker-Planck operators and Witten Laplacians
- Infinite Swapping Algorithm for Training Restricted Boltzmann Machines
- Kramers law: validity, derivations and generalisations
- Large deviation principles for Markov processes via phi-Sobolev inequalities
- Log-concave sampling: Metropolis-Hastings algorithms are fast
- Lévy flights, non-local search and simulated annealing
- Metastability in reversible diffusion processes. I: Sharp asymptotics for capacities and exit times
- Metastability in reversible diffusion processes. II: Precise asymptotics for small eigenvalues
- Nonasymptotic convergence analysis for the unadjusted Langevin algorithm
- On the infinite swapping limit for parallel tempering
- Optimization by simulated annealing
- Poincaré and logarithmic Sobolev inequalities by decomposition of the energy landscape
- 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)
- Sharp asymptotics of the first exit point density
- The simulated tempering method in the infinite switch limit with adaptive weight learning
- Theoretical Guarantees for Approximate Sampling from Smooth and Log-Concave Densities
- Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
- Tunnel effect and symmetries for Kramers-Fokker-Planck type operators
- deviation bounds for additive functionals of markov processes
Cited in
(6)- Methodological and computational aspects of parallel tempering methods in the infinite swapping limit
- Tail probability estimates of continuous-time simulated annealing processes
- Convergence of simulated annealing using kinetic Langevin dynamics
- On the infinite swapping limit for parallel tempering
- 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
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)
