Title: Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo,
Abstract: A key task in Bayesian statistics is sampling from distributions that are
only specified up to a partition function (i.e., constant of proportionality).
However, without any assumptions, sampling (even approximately) can be #P-hard,
and few works have provided "beyond worst-case" guarantees for such settings.
For log-concave distributions, classical results going back to Bakry and
Émery (1985) show that natural continuous-time Markov chains called Langevin
diffusions mix in polynomial time. The most salient feature of log-concavity
violated in practice is uni-modality: commonly, the distributions we wish to
sample from are multi-modal. In the presence of multiple deep and
well-separated modes, Langevin diffusion suffers from torpid mixing.
We address this problem by combining Langevin diffusion with simulated
tempering. The result is a Markov chain that mixes more rapidly by
transitioning between different temperatures of the distribution. We analyze
this Markov chain for the canonical multi-modal distribution: a mixture of
gaussians (of equal variance). The algorithm based on our Markov chain provably
samples from distributions that are close to mixtures of gaussians, given
access to the gradient of the log-pdf. For the analysis, we use a spectral
decomposition theorem for graphs (Gharan and Trevisan, 2014) and a Markov chain
decomposition technique (Madras and Randall, 2002).