Improved Metropolis-Hastings algorithms via landscape modifcation with applications to simulated annealing and the Curie-Weiss model
From MaRDI portal
Publication:6354089
DOI10.1017/APR.2023.35arXiv2011.09680OpenAlexW4386241068MaRDI QIDQ6354089FDOQ6354089
Authors: Michael C. H. Choi 
Publication date: 19 November 2020
Abstract: In this paper, we propose new Metropolis-Hastings and simulated annealing algorithms on finite state space via modifying the energy landscape. The core idea of landscape modification relies on introducing a parameter , in which the landscape is modified once the algorithm is above this threshold parameter. We illustrate the power and benefits of landscape modification by investigating its effect on the classical Curie-Weiss model with Glauber dynamics and external magnetic field in the subcritical regime. This leads to a landscape-modified mean-field equation, and with appropriate choice of the free energy landscape can be transformed from a double-well into a single-well, while the location of the global minimum is preserved on the modified landscape. Consequently, running algorithms on the modified landscape can improve the convergence to the ground-state in the Curie-Weiss model. In the setting of simulated annealing, we demonstrate that landscape modification can yield improved mean tunneling time between global minima, and give convergence guarantee using an improved logarithmic cooling schedule with reduced critical height. Finally, we discuss connections between landscape modification and other acceleration techniques such as Catoni's energy transformation algorithm, preconditioning, importance sampling and quantum annealing. We stress that the technique developed in this paper is applicable to any difference-based discrete optimization algorithm.
Full work available at URL: https://doi.org/10.1017/apr.2023.35
Recommendations
- An improved variant of simulated annealing that converges under fast cooling
- A simple approach to time-inhomogeneous dynamics and applications to (fast) simulated annealing
- Metropolis-Type Annealing Algorithms for Global Optimization in $\mathbb{R}^d $
- The energy transformation method for the Metropolis algorithm compared with simulated annealing
- An adaptive simulated annealing algorithm.
This page was built for publication: Improved Metropolis-Hastings algorithms via landscape modifcation with applications to simulated annealing and the Curie-Weiss model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6354089)
