Department of Mathematical Sciences

Center for Nonlinear Analysis

CNA Home People Seminars Publications Workshops and Conferences CNA Working Groups CNA Comments Form Summer Schools Summer Undergraduate Institute PIRE Cooperation Graduate Topics Courses SIAM Chapter Seminar Positions Contact

Publication 25-CNA-016

Polynomial Complexity Sampling From Multimodal Distributions Using Sequential Monte Carlo

Ruiyu Han
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213
ruiyuh@andrew.cmu.edu

Gautam Iyer
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213
gautam@math.cmu.edu

Dejan Slepčev
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213
slepcev@andrew.cmu.edu

Abstract: We study a sequential Monte Carlo algorithm to sample from the Gibbs measure with a non-convex energy function at a low temperature. We use the practical and popular geometric annealing schedule, and use a Langevin diffusion at each temperature level. The Langevin diffusion only needs to run for a time that is long enough to ensure local mixing within energy valleys, which is much shorter than the time required for global mixing. Our main result shows convergence of Monte Carlo estimators with time complexity that, approximately, scales like the forth power of the inverse temperature, and the square of the inverse allowed error. We also study this algorithm in an illustrative model scenario where more explicit estimates can be given.

Get the paper in its entirety as 25-CNA-016.pdf

« Back to CNA Publications