Sharp dimensional analysis of midpoint methods for Langevin sampling

We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target π propto e-V, where 0 prec α Ipreceqnabla2Vpreceqβ I and kappa=β/α. To achieve √α,W2leqslantvarepsilon, we show that deterministic Heun uses at most widetilde O(kappa4/3d1/3varepsilon-2/3) gradient queries, and underdamped exponential midpoint uses widetilde O(kappa5/4d1/4varepsilon-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 d1/3varepsilon-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.