Improved annealing for sampling from multimodal distributions via landscape modification

Abstract

Given a target distribution $\mu \propto e^{-\mathcal{H}}$ to sample from with Hamiltonian $\mathcal{H}$, in this paper we propose and analyze new Metropolis-Hastings sampling algorithms that target an alternative distribution ${\mu }_{1,\alpha ,c}^f\propto e^{-{\mathcal{H}}_{1,\alpha ,c}^f}$, where ${\mathcal{H}}_{1,\alpha ,c}^f$ is a landscape-modified Hamiltonian which we introduce explicitly. The advantage of the Metropolis dynamics which targets ${\pi }_{1,\alpha ,c}^f$ is that it enjoys reduced critical height described by the threshold parameter $c$, function $f$, and a penalty parameter $\alpha \ge 0$ that controls the state-dependent effect. First, we investigate the case of fixed $\alpha$ and propose a self-normalized estimator that corrects for the bias of sampling and prove asymptotic convergence results and Chernoff-type bound of the proposed estimator. Next, we consider the case of annealing the penalty parameter $\alpha$. We prove strong ergodicity and bounds on the total variation mixing time of the resulting non-homogeneous chain subject to appropriate assumptions on the decay of $\alpha$. We illustrate the proposed algorithms by comparing their mixing times with the original Metropolis dynamics on statistical physics models including the ferromagnetic Ising model on the hypercube or the complete graph and the $q$-state Potts model on the two-dimensional torus. In these cases, the mixing times of the classical Glauber dynamics are at least exponential in the system size as the critical height grows at least linearly with the size, while the proposed annealing algorithm, with appropriate choice of $f$, $c$, and annealing schedule on $\alpha$, mixes rapidly with at most polynomial dependence on the size. The crux of the proof harnesses on the important observation that the reduced critical height can be bounded independently of the size that gives rise to rapid mixing.

arXiv comment25 pages

References in corpus (8)

• MCMC using Hamiltonian dynamics
• General state space Markov chains and MCMC algorithms
• Equi-energy sampler with applications in statistical inference and statistical mechanics
• Accelerating diffusions
• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• Simulated Tempering and Swapping on Mean-Field Models
• An improved variant of simulated annealing that converges under fast cooling
• On the convergence of an improved and adaptive kinetic simulated annealing