Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
A key task in Bayesian machine learning is sampling from distributions that are only specified up to a partition function (i.e., constant of proportionality). One prevalent example of this is sampling posteriors in parametric distributions, such as latent-variable generative models. However sampling (even very approximately) can be #P-hard.
Classical results (going back to [BÉ85]) on sampling focus on log-concave distributions, and show a natural Markov chain called Langevin diffusion mixes in polynomial time. However, all log-concave distributions are uni-modal, while in practice it is very common for the distribution of interest to have multiple modes. In this case, 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 a mixture of (strongly) log-concave distributions of the same shape. In particular, our technique applies to the canonical multi-modal distribution: a mixture of gaussians (of equal variance). Our algorithm efficiently samples from these distributions given only access to the gradient of the log-pdf. To the best of our knowledge, this is the first result that proves fast mixing for multimodal distributions in this setting.
For the analysis, we introduce novel techniques for proving spectral gaps based on decomposing the action of the generator of the diffusion. 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").
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 a mixture of (strongly) log-concave distributions of the same shape. In particular, our technique applies to the canonical multi-modal distribution: a mixture of gaussians (of equal variance). Our algorithm efficiently samples from these distributions given only access to the gradient of the log-pdf. To the best of our knowledge, this is the first result that proves fast mixing for multimodal distributions in this setting.
For the analysis, we introduce novel techniques for proving spectral gaps based on decomposing the action of the generator of the diffusion. 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").
Additional materials for the paper can be found at http://tiny.cc/glr17. Note that the proof and results have been improved and generalized from the precursor at http://www.arxiv.org/abs/1710.02736. See Section ?? for a comparison.
Summary:  This paper considers the problem of sampling from multi-modal distributions. Specifically they are interested in sampling from distributions that are (close to) mixtures of log-concave distributions with the same shape.   The algorithm that they consider for this task is a simulated tempering algorithm which utilizes Langevin dynamics Markov chains at varying temperatures. They show that this algorithm can produce samples close to the desired distribution in polynomial-time.   Quality:  The paper appears to be technically sound, although I have not verified the proofs rigorously.    Clarity:  This submission is easy enough to read, although it is light on details. Since one of the major tools/contributions of the paper is the decomposition theorem in Appendix D, I would have preferred if some statement of this theorem had appeared in the submission itself.   Originality:  This paper appears to present the first provably efficient algorithm for sampling from mixtures of log-concave distributions using only gradient information of the log-pdf.   Moreover, although decomposition theorems have previously been used to analyze Markov chains, the decomposition theorems presented in this paper appear to be novel as well.   Significance:  I think that this is a very interesting theoretical contribution to the study of sampling algorithms. Sampling from multi-modal distributions is an important problem in machine learning, and this paper makes progress in showing that a classical heuristic (simulated tempering) can be applied in this particular setting. Moreover, I think the techniques developed in this paper may be useful to others in this field.  That said, I do not know of any practical situations in which there is a distribution that we want to sample from that (a) is a mixture of log-concave distributions with the same shape and (b) we have only access to the gradient of its log-pdf. I think this submission would be made significantly stronger with a discussion of such situations.   Detailed comments:  - In the last sentence of the abstract, it states “…this is the first result that proves fast mixing for multimodal distributions.” However, since there are many Markov chains that provably sample from multimodal distributions, I think you probably meant something to the effect of “…with only access to the gradient of the log-pdf.”  - In lines 58-59 and 102-104, you discuss the lower bounds presented in Appendix K. I think it is important to clarify that you are talking about algorithms that have only access to the log-pdf and its gradient.