Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence

Shiyuan Zhang; Qiwei Di; Xuheng Li; Quanquan Gu

cs.LGMar 2, 2026

Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence

Authors: Shiyuan Zhang, Qiwei Di, Xuheng Li, Quanquan Gu

Organizations: Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Abstract

Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions $π\propto 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 $\mathrm{tr}(\mathbf{H})$ , where $\mathbf{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 $\mathrm{tr}(\mathbf{H})\ll d$ .

Figures & tables

Dynamics	Discretization	Metric	Strongly convex	General convex	Dim.-free?	Reference
	LMC	$W_{2}$	$\mathcal{O}(\kappa^{3}\beta^{-1}d/\epsilon^{2})$	–	✗	Dalalyan (2017b)
	LMC	KL	$\mathcal{O}(\kappa^{2}d/\epsilon^{2})$	$\mathcal{O}(\beta^{2}dW^{4}/\epsilon^{6})$	✗	Cheng and Bartlett (2018)
	LMC	KL	$\mathcal{O}(\kappa^{2}\beta^{-1}d/\epsilon^{2})$	$\mathcal{O}\big(\beta dW^{2}/\epsilon^{4}\big)$	✗	Durmus et al. (2019)
OLD	LMC	KL	$\mathcal{O}(\kappa^{2}d/\epsilon^{2})$	$\mathcal{O}\big(\beta^{2}dW^{4}/\epsilon^{6}\big)$	✗	Altschuler and Chewi (2024b)
	RMD	KL	$\mathcal{O}(\kappa{d}^{1/2}/\epsilon)$	$\mathcal{O}\big(\beta^{4/3}d^{1/3}W^{8/3}/\epsilon^{10/3}\big)$	✗	Altschuler and Chewi (2024b)
	PLMC	$W_{2}$	$\mathcal{O}(\kappa^{4/3}\beta^{-1/3}d^{2/3}/\epsilon^{2/3})$	–	✗	Srinivasan and Nagaraj (2025)

Table 1: We summarize the sample complexity results from the most important prior works for various discretization methods applied to overdamped Langevin dynamics (OLD) and underdamped Langevin dynamics (ULD). The comparisons include the underlying dynamics (OLD or ULD), the discretization scheme, the metric used to measure convergence, the problem setting, and whether the bound is dimension-free. Throughout the table, LMC denotes Langevin Monte Carlo, i.e., the Euler-Maruyama discretization of OLD, while ULMC denotes the corresponding discretization of ULD. RMD refers to variants of the randomized midpoint method introduced in Shen and Lee (2019) . PLMC denotes the Poisson midpoint method proposed in Srinivasan and Nagaraj (2025) , which achieves improved convergence rates in Wasserstein distance. For Composite, Freund et al. (2022) assume that the potential function

V

admits a decomposition and interpret overdamped Langevin dynamics as a composite optimization problem. Regarding the parameters, in the

\alpha

-strongly convex setting, let

\kappa=\beta/\alpha

be the condition number,

d

be the ambient dimension, and

\mathbf{H}

be an upper bound of the Hessian matrix

\nabla^{2}V

. For uniformity of presentation, we replace any explicit dependence on

\alpha

in the bounds by

\beta/\kappa

. In the general convex setting, let

W

denote the Wasserstein distance between the initial distribution and the target distribution. In all results, we hide the logarithmic factors and omit the

\widetilde{O}

notation for simplicity.

Explore similar work

Dimension-Uniform Discretization Analysis of Preconditioned Annealed Langevin Dynamics for Multimodal Gaussian Mixtures
May 15, 2026Lorenzo Baldassari, Josselin Garnier, Knut Solna +1Langevin Dynamics Diffusion Sampling
University of Basel · Ecole Polytechnique, IP Paris · University of California Irvine +1
Sharp dimensional analysis of midpoint methods for Langevin sampling
Oct 5, 2026Fan Chen, Sinho Chewi, Jianfeng Lu +1Markov Chain Monte Carlo Stochastic Differential Equations
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. · Department of Statistics and Data Science, Yale University. · Department of Mathematics, Duke University. +1
Improved Analysis for Hessian-free High-resolution Monte Carlo Sampling
Aug 25, 2026Wujun Lv, Xiaoyu Wang, Yingli Wang +1Markov Chain Monte Carlo Langevin Dynamics
School of Mathematics and Statistics, Donghua University, Shanghai, People’s Republic of China · Hong Kong University of Science and Technology (Guangzhou), Guangzhou, Guangdong Province, People’s Republic of China · School of Mathematical Sciences, Fudan University, Shanghai, People’s Republic of China +1

May 15, 2026J/K move · Enter open · S save

Dimension-Uniform Discretization Analysis of Preconditioned Annealed Langevin Dynamics for Multimodal Gaussian Mixtures

Lorenzo Baldassari, Josselin Garnier, Knut Solna, Maarten V. de Hoop

University of Basel · Ecole Polytechnique, IP Paris · University of California Irvine+1

Langevin Dynamics Diffusion Sampling

Open paper AskPDF arXiv

Obtaining stable diffusion-based samplers in high- and infinite-dimensional settings is challenging because errors can accumulate across high-frequency coordinates and make the dynamics unstable under refinement of the finite-dimensional approximation of the underlying function-space problem. Discretization is a typical source of such errors, and preconditioning with a suitable spectral decay is one way to control their accumulation. In this paper, we study this problem for preconditioned annealed Langevin dynamics (ALD) applied to Gaussian mixtures. We first show that Euler-Maruyama (EM) discretization, by treating the stiff linear part of the annealed score with a forward Euler step, imposes a stability constraint coupling the preconditioner with the annealed covariance scale. Together with the conditions ensuring dimension-uniform control of the annealed dynamics, this constraint forces the initial smoothed law to remain uniformly close to the target across dimensions. We then consider an exponential-integrator scheme that integrates the stiff linear part of the annealed score exactly. Under explicit spectral summability conditions coupling the smoothing covariance, the component covariance spectra, and the preconditioner, we prove a dimension-uniform Kullback-Leibler (KL) bound for this scheme. This bound can be made arbitrarily small, uniformly in dimension, by allowing enough time for annealing and then refining the time mesh accordingly. Importantly, these conditions allow regimes in which the KL divergence between the target and the initial smoothed law diverges with dimension, showing that the restrictions imposed by EM are scheme-dependent rather than intrinsic to ALD.

Abstract

Explore similar work

Dimension-Uniform Discretization Analysis of Preconditioned Annealed Langevin Dynamics for Multimodal Gaussian Mixtures

Sharp dimensional analysis of midpoint methods for Langevin sampling

Improved Analysis for Hessian-free High-resolution Monte Carlo Sampling