Sharp dimensional analysis of midpoint methods for Langevin sampling
Abstract
We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target π∝ e−V, where 0 ≺ αI⪯∇2V⪯βI and κ=β/α. To achieve √α W2leqslantε, we show that deterministic Heun uses at most Õ(κ4/3d1/3ε−2/3) gradient queries, and underdamped exponential midpoint uses Õ(κ5/4d1/4ε−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 ε 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/3ε−1/3 to get an ε-close sample despite starting at a benign initialization. This shows surprisingly that in high dimensions, deterministic discretizations can outperform their random counterparts.
Related
- Wasserstein Bounds for Euler and Randomized Midpoint Langevin Sampling with Noisy Gradients
- Nonlinear Assimilation via Score-Based Sequential Langevin Sampling
- Neural Actor--Critic Learning with Minimax Critics and Reflected Langevin Sampling
- Kinetic Langevin Meets Split Gibbs: Accelerated Posterior Sampling for Imaging Inverse Problems with Diffusion Priors
- Diffusion Removes Langevin's Conditioning Dependence: A Sharp Gaussian Analysis
BibTeX
@misc{chen2026sharp,
title = {{Sharp dimensional analysis of midpoint methods for Langevin sampling}},
author = {Fan Chen and Sinho Chewi and Jianfeng Lu and Matthew S. Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06308},
eprint = {2610.06308},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06308},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp dimensional analysis of midpoint methods for Langevin sampling
AU - Fan Chen
AU - Sinho Chewi
AU - Jianfeng Lu
AU - Matthew S. Zhang
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06308
UR - https://arxiv.org/abs/2610.06308
AB - We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target π∝ e^−V, where 0 ≺ αI⪯∇^2V⪯βI and κ=β/α. To achieve √α W_2leqslantε, we show that deterministic Heun uses at most Õ(κ^4/3d^1/3ε^−2/3) gradient queries, and underdamped exponential midpoint uses Õ(κ^5/4d^1/4ε^−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 ε 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ε^−1/3 to get an ε-close sample despite starting at a benign initialization. This shows surprisingly that in high dimensions, deterministic discretizations can outperform their random counterparts.
ER -