Sharp dimensional analysis of midpoint methods for Langevin sampling

arXiv:2610.06308v1 Announce Type: cross Abstract: We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target pi propto e^{-V}, where 0 prec alpha Ipreceqnabla^2Vpreceqeta I and kappa=eta/alpha. To achieve sqrtalpha,W_2leqslantarepsilon, we show that deterministic Heun uses at most widetilde O(kappa^{4/3}d^{1/3}arepsilon^{-2/3}) gradient queries, and underdamped exponential midpoint uses widetilde O(kappa^{5/4}d^{1/4}arepsilon^{-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 arepsilon 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}arepsilon^{-1/3} to get an arepsilon-close sample despite starting at a benign initialization. This shows surprisingly that in high dimensions, deterministic discretizations can outperform their random counterparts.

Source: arXiv cs.LG | 2026-10-06

Related