View article

Sampling Gibbs measures at low temperatures is an important but computationally challenging task. Numerical evidence suggests that the infinite-swapping algorithm (isa) is a promising method. The isa can be seen as an improvement of the parallel tempering replica method. We rigorously analyze the ergodic properties of the isa in the low temperature regime, deducing asymptotic estimates for the spectral gap (or Poincaré constant), optimal in dimension one, 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 over-damped Langevin dynamics. As a corollary, we derive a concentration 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 over-damped Langevin dynamics.