Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence
cs.LG, math.OC, stat.ML
Submitted: 2026-03-02
Updated: 2026-10-28
Comments: 40 pages, 1 table, ICML2026
Project page: https://chewisinho.github.io/main.pdf
License: http://creativecommons.org/licenses/by/4.0/
The gist: Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions π proportional to e-V, and is often empirically effective in high dimensions.
Terminology
Abstract
Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions π proportional to e-V, and is often empirically effective in high dimensions. However, existing non-asymptotic convergence guarantees for discretized ULD typically scale polynomially with the ambient dimension d, leading to vacuous bounds when d is large. The main known dimension-free result concerns the randomized midpoint discretization in Wasserstein-2 distance (Liu et al.,2023), while dimension-independent guarantees for ULD discretizations in KL divergence have remained open. We close this gap by proving the first dimension-free KL divergence bounds for discretized ULD. Our analysis refines the KL local error framework (Altschuler et al., 2025) to a dimension-free setting and yields bounds that depend on tr(H), where H upper bounds the Hessian of V, rather than on d. As a consequence, we obtain improved iteration complexity for underdamped Langevin Monte Carlo relative to overdamped Langevin methods in regimes where tr(H) much less than d.
Sources
- Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling
- Wasserstein contraction properties for hypoelliptic diffusions
- Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusion
- On the convergence of Hamiltonian Monte Carlo
- The shifted ODE method for underdamped Langevin MCMC
- Sqrt(d) Dimension Dependence of Langevin Monte Carlo
- Score-Based Generative Modeling through Stochastic Differential Equations
- Poisson Midpoint Method for Log Concave Sampling: Beyond the Strong Error Lower Bounds
- Wasserstein Convergence of Critically Damped Langevin Diffusions
- Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited
- Analysis of Langevin midpoint methods using an anticipative Girsanov theorem
- Neural Thompson Sampling
Related papers
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis
- (Mis)generalization of Helpful-Only Fine-tuning