Annealed Underdamped Langevin Dynamics

Source abstract

In sampling, different flavours of annealing, tempering, or other successive approximation approaches are widely used and studied. In this work we investigate annealed underdamped Langevin sampling for logconcave distributions of the form $π(x) \propto e^{-Ψ(x)}$ for a potential $Ψ:\mathbb{R}^d \rightarrow \mathbb{R}$. That is, we assume access to the score of a general approximating family of distributions $(π_τ)_{τ\in [0,1]}$ with $π_0=π$. This family is used in a time-inhomogeneous underdamped Langevin process with moving target $π_{τ(t)}$ and an appropriate annealing schedule $t\mapsto τ(t)$ such that $τ(t)\downarrow 0$ as $t\to T$ for some $T>0$. While the degeneracy of the Brownian motion prohibits conventional Girsanov arguments, we are able to circumvent this issue by relying on an appropriately designed auxiliary process. To the best of our knowledge these are the first (quantitative) results for sampling using time-inhomogeneous underdamped Langevin dynamics. Moreover, we obtain an iteration complexity of $\mathcal{O}(ε^{-2})$ in total variation distance in comparison to $\mathcal{O}(ε^{-6})$ for annealed overdamped Langevin sampling. While we currently assume convexity, our proof strategies are amenable to generalization for non-logconcave targets and enable for several future research directions.