Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper analyzes deterministic and randomized midpoint discretizations for Langevin sampling under bounded Hessian conditions, achieving improved sample complexity bounds. By leveraging stationarity cancellations and Malliavin calculus for smoothing, deterministic Heun and exponential midpoint methods achieve near-optimal query complexities of $\widetilde O(κ^{4/3}d^{1/3}\varepsilon^{-2/3})$ and $\widetilde O(κ^{5/4}d^{1/4}\varepsilon^{-1/2})$ respectively. Crucially, the analysis reveals that deterministic methods can outperform randomized counterparts in high dimensions for achieving $\varepsilon$-close samples from benign initializations.
Deterministic midpoint methods for Langevin sampling can achieve superior sample complexity in high dimensions compared to their randomized counterparts.
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.
MIT CSAIL