Winfried Barta (George Washington University)

Title: Forgetting the Starting Distribution in Interacting Tempering

Abstract: Simulating multimodal probability distributions on high dimensional spaces can be a difficult problem. Many practical algorithms use local move Markov chains that can easily get "stuck" in one of the modes of the distribution. Tempering is a well-known strategy to try to overcome this problem. However, for some "difficult" distributions like the (ferromagnetic, mean-field) Potts model, even parallel and serial tempering algorithms are known to mix exponentially slowly. Interacting tempering (Fort et al. 2011) is a non-Markovian process that tries to improve on parallel or serial tempering algorithms. As a first step towards a quantitative and non-asymptotic analysis of its convergence behavior, we prove that under (easy to verify) assumptions on the distribution of interest, the interacting tempering process rapidly forgets its starting state. The result applies, among others, to exponential random graph models, the Ising and Potts models (in mean field or on a bounded degree graph), as well as (Edwards-Anderson) Ising spin glasses. We also exhibit an example of a target distribution for which the interacting tempering process forgets its starting state in order n log(n) steps, but takes order exp(n) steps to converge to its limiting distribution, where n is the dimension of the state space.