Publication 26-CNA-007

Convergence of Langevin AIS for Multimodal Distributions

Akshat Agarwal
Princeton University
Princeton NJ 08544
akshat.agarwal@princeton.edu

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

Aidan Jameson
University of Utah
Salt Lake City, UT 84112
u0680511@utah.edu

Seungjae Son
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA, 15213
seungjas@andrew.cmu.edu

Wyatt Wimmer
Brigham Young University
Provo, UT 84602
wyattwimmer@gmail.com

Abstract: We study convergence rates of the annealed importance sampling algorithm (Neal ’01) combined with Langevin Monte Carlo when the target is a multimodal Gibbs measure. The main result shows that for a fixed error threshold, the time complexity is quadratic in the inverse temperature. We identify a simple and useful quantity that controls the sampling error for AIS in a general setting, and then bound this quantity in our setting using spectral estimates. We also study an autonormalized version and obtain bounds for the time complexity in terms of the inverse temperature.

Get the paper in its entirety as  26-CNA-007.pdf

---

«   Back to CNA Publications