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 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 γ r = γ 0 2 − r , r = 0 , … , R . We first state a quantitative result under general assumptions that guarantees an ε-approximation (in an L 2 -sense) with a cost of the order ε − 2 or ε − 2 | log ε | 3 under less contractive assumptions. We then apply it to overdamped Langevin diffusions with strongly convex potential U : R d → R and obtain an ε-complexity of the order O ( d ε − 2 log 3 ( d ε − 2 ) ) or O ( d ε − 2 ) 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 ) 2 λ ¯ U − 3 d ε − 2 (where λ ¯ U and λ ¯ 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.