Abstract
In this paper, we propose a new numerical method for the underdamped Langevin diffusion (ULD) and present a non-asymptotic analysis of its sampling error in the 2-Wasserstein distance when the d-dimensional target distribution p(x) ∝ e −f(x) is strongly log-concave and has varying degrees of smoothness. Precisely, under the assumptions that the gradient and Hessian of f are Lipschitz continuous, our algorithm achieves a 2-Wasserstein error of ε in O √d/ε and O√d/√ε steps respectively. Therefore, our algorithm has a similar complexity as other popular Langevin MCMC algorithms under matching assumptions.
However, if we additionally assume that the third derivative of f is Lipschitz continuous, then our algorithm achieves a 2-Wasserstein error of ε in O √d/ε 1 3
steps. To the best of our knowledge, this is the first gradient-only method for ULD with third order convergence.
To support our theory, we perform Bayesian logistic regression across a range of real-world datasets, where our algorithm achieves competitive performance compared to an existing underdamped Langevin MCMC algorithm and the popular No U-Turn Sampler (NUTS).
However, if we additionally assume that the third derivative of f is Lipschitz continuous, then our algorithm achieves a 2-Wasserstein error of ε in O √d/ε 1 3
steps. To the best of our knowledge, this is the first gradient-only method for ULD with third order convergence.
To support our theory, we perform Bayesian logistic regression across a range of real-world datasets, where our algorithm achieves competitive performance compared to an existing underdamped Langevin MCMC algorithm and the popular No U-Turn Sampler (NUTS).
| Original language | English |
|---|---|
| Pages (from-to) | 1-63 |
| Number of pages | 63 |
| Journal | Journal of Machine Learning Research |
| Volume | 27 |
| Issue number | 126 |
| Publication status | Published - 6 Jul 2026 |
Funding
We greatly appreciate the support from the Department of Mathematical Sciences at the University of Bath, the Maths4DL programme under EPSRC grant EP/V026259/1 and the Alan Turing Institute. AJ thanks the UK National Cyber Security Centre for funding his research and Extropic for funding his work implementing high order SDE solvers in Diffrax.
| Funders |
|---|
| Engineering and Physical Sciences Research Council |
Keywords
- Langevin dynamics
- Markov Chain Monte Carlo
- High order convergence
Fingerprint
Dive into the research topics of 'Underdamped Langevin MCMC with third order convergence'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS