Functional inequalities of the Infinite swapping algorithm: theory and applications

Seminar | September 4 | 3:10-4:10 p.m. | 1011 Evans Hall

 Wenpin Tang, Berkeley IEOR

 Department of Statistics

Sampling Gibbs measures at low temperature is a very important task but computationally very challenging. Numeric evidence suggest that the infinite-swapping algorithm (isa) is a promising method. The isa can be seen as an improvement of replica methods which are very popular. We rigorously analyze the ergodic properties of the isa in the low temperature regime deducing Eyring-Kramers formulas for the spectral gap (or Poincaré constant) and the log-Sobolev constant. Our main result shows 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 deviation inequality showing that sampling is also improved by an exponential factor. Furthermore, we analyze simulated annealing for the isa and show that isa is again superior to the over-damped Langevin dynamics. This is joint work with Georg Menz and André Schlichting.

 CA, pitman@berkeley.edu, 510-642-2781