Multilevel Langevin Pathwise Average for Gibbs Approximation

We propose and study a new multilevel method for the numerical approximation of a Gibbs distribution π on ${\mathbb{R}}^d$, based on (overdamped) Langevin diffusions. This method relies on a multilevel occupation measure, that is, on an appropriate combination of R occupation measures of (constant-step) Euler schemes with respective steps ${\gamma }_r={\gamma }_0{2}^{-r},\hspace{0.17em}r=0,\dots ,R$. We first state a quantitative result under general assumptions that guarantees an ε-approximation (in an L²-sense) with a cost of the order ${\epsilon }^{-2}$ or ${\epsilon }^{-2}|\log \epsilon {|}^3$ under less contractive assumptions. We then apply it to overdamped Langevin diffusions with strongly convex potential $U:{\mathbb{R}}^d\to \mathbb{R}$ and obtain an ε-complexity of the order $\mathcal{O}(d{\epsilon }^{-2}{\log }^3(d{\epsilon }^{-2}))$ or $\mathcal{O}(d{\epsilon }^{-2})$ under additional assumptions on U. More precisely, up to universal constants, an appropriate choice of the parameters leads to a cost controlled by ${({\overline{\lambda }}_U\vee 1)}^2{\underset{¯}{\lambda }}_U^{-3}d{\epsilon }^{-2}$ (where ${\overline{\lambda }}_U$ and ${\underset{¯}{\lambda }}_U$ respectively denote the supremum and the infimum of the largest and lowest eigenvalue of $D^{2}U$). We finally complete these theoretical results with some numerical illustrations, including comparisons to other algorithms in Bayesian learning and opening to the non–strongly convex setting.

Funding: The authors are grateful to the SIRIC ILIAD Nantes-Angers program, supported by the French National Cancer Institute [INCA-DGOS-Inserm Grant 12558].