Math @ Duke

Publications [#354091] of Holden Lee
Papers Published
 Ge, R; Lee, H; Risteski, A, Beyond logconcavity: Provable guarantees for sampling multimodal distributions using simulated tempering langevin Monte Carlo,
Advances in Neural Information Processing Systems, vol. 2018December
(January, 2018),
pp. 78477856
(last updated on 2022/01/28)
Abstract: 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 latentvariable generative models. However sampling (even very approximately) can be #Phard. Classical results (going back to [BÉ85]) on sampling focus on logconcave distributions, and show a natural Markov chain called Langevin diffusion mixes in polynomial time. However, all logconcave distributions are unimodal, 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) logconcave distributions of the same shape. In particular, our technique applies to the canonical multimodal distribution: a mixture of gaussians (of equal variance). Our algorithm efficiently samples from these distributions given only access to the gradient of the logpdf. 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

