Abstract
We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target $π\propto e^{-V}$, where $0 \prec αI\preceq\nabla^2V\preceqβI$ and $κ=β/α$. To achieve $\sqrtα\,W_2\leqslant\varepsilon$, we show that deterministic Heun uses at most $\widetilde O(κ^{4/3}d^{1/3}\varepsilon^{-2/3})$ gradient queries, and underdamped exponential midpoint uses $\widetilde O(κ^{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.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Chen, F., Chewi, S., Lu, J., & Zhang, M. S. (2026). Sharp dimensional analysis of midpoint methods for Langevin sampling. https://omanscience.com/en/articles/sharp-dimensional-analysis-of-midpoint-methods-for-langevin-sampling
MLA 9
Chen, Fan, et al. "Sharp dimensional analysis of midpoint methods for Langevin sampling." https://omanscience.com/en/articles/sharp-dimensional-analysis-of-midpoint-methods-for-langevin-sampling.
Chicago (author–date)
Chen, Fan, Sinho Chewi, Jianfeng Lu, and Matthew S. Zhang. 2026. "Sharp dimensional analysis of midpoint methods for Langevin sampling." https://omanscience.com/en/articles/sharp-dimensional-analysis-of-midpoint-methods-for-langevin-sampling.
Harvard
Chen, F., Chewi, S., Lu, J. and Zhang, M. S. (2026) 'Sharp dimensional analysis of midpoint methods for Langevin sampling', Available at: https://omanscience.com/en/articles/sharp-dimensional-analysis-of-midpoint-methods-for-langevin-sampling.
Vancouver
Chen F, Chewi S, Lu J, Zhang MS. Sharp dimensional analysis of midpoint methods for Langevin sampling. https://omanscience.com/en/articles/sharp-dimensional-analysis-of-midpoint-methods-for-langevin-sampling
IEEE
F. Chen, S. Chewi, J. Lu, and M. S. Zhang, "Sharp dimensional analysis of midpoint methods for Langevin sampling," https://omanscience.com/en/articles/sharp-dimensional-analysis-of-midpoint-methods-for-langevin-sampling.