Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo

Probability Seminar

Holden Lee (Princeton University)

Thursday, February 14, 2019 -
3:15pm to 4:15pm
119 Physics

A fundamental problem in Bayesian statistics is sampling from distributions that are only specified up to a partition function (constant of proportionality). In particular, we consider the problem of sampling from a distribution given access to the gradient of the log-pdf. For log-concave distributions, classical results due to Bakry and Emery show that natural continuous-time Markov chains called Langevin diffusions mix in polynomial time. But in practice, distributions are often multi-modal and hence non-log-concave, and can take exponential time to mix.

We address this problem by combining Langevin diffusion with simulated tempering. The result is a Markov chain that mixes in polynomial rather than exponential time by transitioning between different temperatures of the distribution. We prove fast mixing for any distribution that is close to a mixture of gaussians of equal variance.

For the analysis, we bound the spectral gap using a novel Markov chain decomposition theorem. Previous approaches rely on decomposing the state space as a partition of sets, while our approach can be thought of as decomposing the stationary measure as a mixture of distributions (a "soft partition").

Based on the paper

Joint work with Rong Ge (Duke) and Andrej Risteski (MIT).

Last updated: 2019/02/20 - 10:25pm