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\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.

Statistics Theory (math.ST); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Numerical Analysis (math.NA)

arXiv:2610.06308 [math.ST]

(or arXiv:2610.06308v1 [math.ST] for this version)

https://doi.org/10.48550/arXiv.2610.06308 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.