Sharp dimensional analysis of midpoint methods for Langevin sampling
TL;DR
The proofs exploit cancellation at stationarity and smoothing using techniques from Malliavin calculus, outperforming previous upper bounds based on standard couplings and shows surprisingly that in high dimensions, deterministic discretizations can outperform their random counterparts.
Abstract
We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target $\pi \propto e^{-V}$, where $0 \prec \alpha I\preceq\nabla^2V\preceq\beta I$ and $\kappa=\beta/\alpha$. To achieve $\sqrt\alpha\,W_2\leqslant\varepsilon$, we show that deterministic Heun uses at most $\widetilde O(\kappa^{4/3}d^{1/3}\varepsilon^{-2/3})$ gradient queries, and underdamped exponential midpoint uses $\widetilde O(\kappa^{5/4}d^{1/4}\varepsilon^{-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 $\varepsilon$ 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}\varepsilon^{-1/3}$ to get an $\varepsilon$-close sample despite starting at a benign initialization. This shows surprisingly that in high dimensions, deterministic discretizations can outperform their random counterparts.
