Sharp dimensional analysis of midpoint methods for Langevin sampling

Abstract

We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target $\pi \propto e^{-V}$, where $0\prec \alpha I⪯{\nabla }^{2}V⪯\beta I$ and $\kappa =\beta /\alpha$. To achieve $\sqrt{\alpha }{W}_2⩽\epsilon$, we show that deterministic Heun uses at most $\tilde{O}({\kappa }^{4/3}{d}^{1/3}{\epsilon }^{-2/3})$ gradient queries, and underdamped exponential midpoint uses $\tilde{O}({\kappa }^{5/4}{d}^{1/4}{\epsilon }^{-1/2})$. The proofs exploit cancellation at stationarity and smoothing using techniques from Malliavin calculus, outperforming previous upper bounds based on standard couplings. At bounded condition number, a lower bound matches the $d$ and $\epsilon$ powers of both deterministic methods. To contrast, for the randomized midpoint methods and Poisson midpoint with at least two grid points (both overdamped and underdamped variants), a simple Gaussian calculation yields a lower bound $d^{1/3}{\epsilon }^{-1/3}$ to get an $\epsilon$-close sample despite starting at a benign initialization. This shows surprisingly that in high dimensions, deterministic discretizations can outperform their random counterparts.