Metastability is a formidable challenge to Markov chain Monte Carlo methods. In this paper we present methods for algorithm design to meet this challenge. The design problem we consider is temperature selection for the infinite swapping scheme, which is the limit of the widely used parallel tempering scheme obtained when the swap rate tends to infinity. We use a recently developed tool for the analysis of the empirical measure of a small noise diffusion to transform the variance reduction problem into an explicit optimization problem. Our first analysis of the optimization problem is in the setting of a double-well model, and it shows that the optimal selection of temperature ratios is a geometric sequence except possibly the highest temperature. In the same setting we identify two different sources of variance reduction and show how their competition determines the optimal highest temperature. In the general multiwell setting we prove that the same geometric sequence of temperature ratios as in the two-well case is always nearly optimal, with a performance gap that decays geometrically in the number of temperatures.

The aim of this paper is to develop tractable large deviation approximations for the empirical measure of a small noise diffusion. The starting point is the Freidlin–Wentzell theory, which shows how to approximate via a large deviation principle the invariant distribution of such a diffusion. The rate function of the invariant measure is formulated in terms of quasipotentials, quantities that measure the difficulty of a transition from the neighborhood of one metastable set to another. The theory provides an intuitive and useful approximation for the invariant measure, and along the way many useful related results (e.g., transition rates between metastable states) are also developed. With the specific goal of design of Monte Carlo schemes in mind, we prove large deviation limits for integrals with respect to the empirical measure, where the process is considered over a time interval whose length grows as the noise decreases to zero. In particular, we show how the first and second moments of these integrals can be expressed in terms of quasipotentials. When the dynamics of the process depend on parameters, these approximations can be used for algorithm design, and applications of this sort will appear elsewhere. The use of a small noise limit is well motivated, since in this limit good sampling of the state space becomes most challenging. The proof exploits a regenerative structure, and a number of new techniques are needed to turn large deviation estimates over a regenerative cycle into estimates for the empirical measure and its moments. 

We introduce and study the basic properties of two ergodic stochastic control problems associated with the quasistationary distribution (QSD) of a diffusion process X relative to a bounded domain. The two problems are in some sense dual, with one defined in terms of the generator associated with X and the other in terms of its adjoint. Besides proving wellposedness of the associated Hamilton-Jacobi- Bellman equations, we describe how they can be used to characterize important properties of the QSD. Of particular note is that the QSD itself can be identified, up to normalization, in terms of the cost potential of the control problem associated with the adjoint.

Large deviations for stochastic approximations is a well-studied field that yields convergence properties for many useful algorithms in statistics, machine learning and statistical physics. In this article, we prove, under certain assumptions, a large deviation principle for a stochastic approximation with state-dependent Markovian noise and with decreasing step size. Common algorithms that satisfy these conditions include stochastic gradient descent, persistent contrastive divergence and the Wang-Landau algorithm. The proof is based don't he weak convergence approach to the theory of large deviations and uses a representation formula to rewrite the problem into a stochastic control problem. The resulting rate function is an action potential over a local rate function that is the Fenchel-Legendre transform of a limiting Hamiltonian.