Multilevel Langevin Pathwise Average for Gibbs Approximation

We propose and study a new multilevel method for the numerical approximation of a Gibbs distribution π on Rᵈ, based on (overdamped) Langevin diffusions. This method inspired by {mainPPlangevin} and {giles_szpruch_invariant} relies on a multilevel occupation measure, $i.e.$ on an appropriate combination of R occupation measures of (constant-step) Euler schemes with respective steps γᵣ = γ₀ 2⁻ʳ, r=0,…,R. We first state a quantitative result under general assumptions which guarantees an ε-approximation (in a L²-sense) with a cost of the order ε⁻² or ε⁻²|log ε|³ under less contractive assumptions. We then apply it to overdamped Langevin diffusions with strongly convex potential U:Rᵈ and obtain an ε-complexity of the order O(dε⁻²log³(dε⁻²)) or O(dε⁻²) under additional assumptions on U. More precisely, up to universal constants, an appropriate choice of the parameters leads to a cost controlled by (λ̄U 1)²λU⁻³ dε⁻² (where λ̄U and λU respectively denote the supremum and the infimum of the largest and lowest eigenvalue of D²U). We finally complete these theoretical results with some numerical illustrations including comparisons to other algorithms in Bayesian learning and opening to non strongly convex setting.