Underdamped Langevin MCMC with third order convergence
Maximilian Scott [email protected], Dáire O’Kane [email protected], Andraž Jelinčič [email protected], James Foster [email protected], UK · 2025
Read Underdamped Langevin MCMC with third order convergence by Maximilian Scott [email protected], Dáire O’Kane [email protected], Andraž Jelinčič [email protected], James Foster [email protected], UK (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-16485.txt.
Introduction
Maximilian Scott and co-authors propose a new sampling method for a physics-based diffusion process and prove it reaches third-order accuracy, in a 2025 paper. Sampling methods of this family draw samples from a target distribution by simulating a damped motion. How many steps they need for a set error depends on how smooth the target is.
Under standard smoothness conditions, their method matches the step counts of popular rivals. With one extra smoothness condition, a bounded third derivative, the needed steps drop sharply with the error target. The authors call it the first gradient-only method of its kind with third-order convergence. Tests on real data sets for a Bayesian task held up well.
Catalog record
| CREATOR | Maximilian Scott [email protected], Dáire O’Kane [email protected], Andraž Jelinčič [email protected], James Foster [email protected], UK |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 197 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-16485
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Underdamped Langevin MCMC with third order convergence Maximilian Scott [email protected], Dáire O’Kane [email protected], Andraž Jelinčič [email protected], James Foster [email protected], UK 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 d -dimensional target distribution p ( x ) ∝ e − f ( x ) p(x)\propto e^{-f(x)} is strongly log-concave and has varying degrees of smoothness. Precisely, under the assumptions that the gradient and Hessian of f f are Lipschitz continuous, our algorithm achieves a 2-Wasserstein error of ε \varepsilon in 𝒪 ( d / ε ) \mathcal{O}\big(\sqrt{d\hskip 0.7113pt}/\varepsilon\hskip 0.7113pt\big) and 𝒪 ( d / ε ) \mathcal{O}\big(\sqrt{d\hskip 0.7113pt}/\sqrt{\varepsilon}\hskip 0.7113pt\big) 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 f is Lipschitz continuous, then our algorithm achieves a 2-Wasserstein error of ε \varepsilon in 𝒪 ( d / ε 1 3 ) \mathcal{O}\big(\sqrt{d\hskip 0.7113pt}/\varepsilon^{\frac{1}{3}}\hskip 0.7113pt\big) 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). Maximilian Scott, Dáire O’Kane, Andraž Jelinčič and James Foster † † heading: 23 2025 1- 1/21; Revised 5/22 9/22 21-0000 † † shortheadings: Underdamped Langevin MCMC with third order convergence / Scott, O’Kane, Jelinčič and Foster † † firstpage: 1 † † editor: My editor keywords Langevin dynamics, Markov Chain Monte Carlo, High order convergence 1 Introduction In a variety of applications ranging from statistical inference ( Ma et al. 2015 ; Mandt et al. 2017 ; Durmus and Moulines 2019 ) to molecular dynamics ( Pastor et al. 1988 ; Pastor 1994 ; Allen and Tildesley 2017 ) , we are often interested in sampling from a target distribution p(x)\propto e^{-f(x)}, (1) where x\in\mathbb{R}^{d} and f:\mathbb{R}^{d}\to\mathbb{R} denotes a scalar potential. In practice, we typically only know this target distribution up to a normalisation constant – which becomes challenging to compute when the dimension d is large. So instead, we can generate samples by constructing and simulating a Markov chain whose marginal distribution becomes close to the target ( 1 ). This methodology for sampling from p is known as Markov Chain Monte Carlo (or MCMC). In this paper, we consider MCMC algorithms obtained by simulating the underdamped Langevin diffusion (ULD), given by the following stochastic differential equation (SDE): \displaystyle\begin{split}dx_{t}&=v_{t}\,dt,\\[2.0pt] dv_{t}&=-\gamma v_{t}\,dt-u\nabla f(x_{t})\,dt+\sqrt{2\gamma u}\,dW_{t}\hskip 0.7113pt,\end{split} (2) where x,v\in\mathbb{R}^{d} represent the position and momentum of a particle, \gamma>0 denotes a friction coefficient, u>0 and W is a d -dimensional Brownian motion. Under mild assumptions on the scalar potential f , it is known that the SDE ( 2 ) admits a unique strong solution which is ergodic with respect to the Gibbs measure with Hamiltonian H(x,v)=f(x)+\frac{1}{2u}\|v\|^{2} ( Pavliotis 2014 , Proposition 6.1) . In other words, ULD has a stationary measure \pi on \mathbb{R}^{2d} with density proportional to \exp(-H(x,v)) . Therefore, the distribution of x_{t} will converge to the target distribution ( 1 ) and thus simulating ULD will allows us to generate samples. In general, the SDE ( 2 ) which governs ULD does not admit a closed-form solution, and so it is necessary to develop appropriate numerical methods for approximating these samples. A variety of approximations have previously been proposed for ULD. Some noteworthy examples include the unadjusted and Metropolis-adjusted OBABO schemes ( Bussi and Parrinello 2006 ; Monmarché 2021 ; Song and Tan 2021 ; Riou-Durand and Vogrinc 2022 ) , the UBU method ( Álamo and Sanz-Serna 2019 ; Sanz-Serna and Zygalakis 2021 ) , the ALUM methods ( Hu et al. 2021 ) , the randomised midpoint method ( Shen and Lee 2019 ) , the BAOAB method ( Leimkuhler et al. 2016 ) and a Strang splitting ( Buckwar et al. 2019 ) . In addition, there exist a variety of methods for improving the accuracy and robustness of underdamped Langevin MCMC algorithms. These include introducing a preconditioning matrix ( Goodman and Weare 2010 ; Leimkuhler et al. 2018 ; AlRachid et al. 2018 ) , using adaptive step sizes ( Foster and Jelinčič 2024 ; Leroy et al. 2024 ; Leimkuhler et al. 2025 ) or using unbiased estimators based on Multilevel Monte Carlo techniques ( Chada et al. 2024 ) . In this paper we introduce a new practical method for approximating underdamped Langevin dynamics called QUICSORT 1 1 1 QU adrature I nspired and C ontractive S hifted O DE with R unge-Kutta T hree , which is constructed using a piecewise linear discretisation of the underlying Brownian motion. This approach builds upon the Shifted ODE introduced by Foster et al. 2021 with the behaviour that, given certain convexity and smoothness assumptions on f , it yields third order convergence guarantees that hold for all n\geq 0 . Definition 1 (QUICSORT) . Let \{t_{n}\}_{n\geq 0} be a sequence of times with t_{0}=0 , t_{n+1}>t_{n} and h_{n}=t_{n+1}-t_{n} . We construct a numerical solution \{(X_{n},V_{n})\}_{n\geq 0} for the SDE ( 2 ) by choosing some initial (X_{0},V_{0})\sim\pi_{0} and, for each n\geq 0 , defining (X_{n+1},V_{n+1}) as follows: \displaystyle V^{(1)}_{n} \displaystyle:=V_{n}+\sigma(H_{n}+6K_{n}), \displaystyle X^{(1)}_{n} \displaystyle:=X_{n}+\frac{1-e^{-\lambda_{-}\gamma h_{n}}}{\gamma}V^{(1)}_{n}+\frac{e^{-\lambda_{-}\gamma h_{n}}+\lambda_{-}\gamma h_{n}-1}{\gamma^{2}h_{n}}\hskip 0.7113ptC_{n}\hskip 0.7113pt, \displaystyle X^{(2)}_{n} \displaystyle:=X_{n}+\frac{1-e^{-\lambda_{+}\gamma h_{n}}}{\gamma}V^{(1)}_{n}-\frac{1-e^{-\frac{1}{3}\gamma h_{n}}}{\gamma}u\nabla f(X^{(1)}_{n})h_{n}+\frac{e^{-\lambda_{+}\gamma h_{n}}+\lambda_{+}\gamma h_{n}-1}{\gamma^{2}h_{n}}\hskip 0.7113ptC_{n}\hskip 0.7113pt, \displaystyle V^{(2)}_{n} \displaystyle:=e^{-\gamma h_{n}}V^{(1)}_{n}-\frac{1}{2}e^{-\lambda_{+}\gamma h_{n}}u\nabla f(X^{(1)}_{n})h_{n}-\frac{1}{2}e^{-\lambda_{-}\gamma h_{n}}u\nabla f(X^{(2)}_{n})h_{n}+\frac{1-e^{-\gamma h_{n}}}{\gamma h_{n}}\hskip 0.7113ptC_{n}\hskip 0.7113pt, \displaystyle X_{n+1} \displaystyle:=X_{n}-\frac{1-e^{-\lambda_{+}\gamma h_{n}}}{2\gamma}u\nabla f(X^{(1)}_{n})h_{n}-\frac{1-e^{-\lambda_{-}\gamma h_{n}}}{2\gamma}u\nabla f(X^{(2)}_{n})h_{n} (3) \displaystyle\hskip 32.72066pt+\frac{1-e^{-\gamma h_{n}}}{\gamma}V^{(1)}_{n}+\frac{e^{-\gamma h_{n}}+\gamma h_{n}-1}{\gamma^{2}h_{n}}\hskip 0.7113ptC_{n}\hskip 0.7113pt, \displaystyle V_{n+1} \displaystyle:=V^{(2)}_{n}-\sigma(H_{n}-6K_{n}). where \sigma=\sqrt{2\gamma u} , \lambda_{+}=\frac{3+\sqrt{3}}{6} , \lambda_{-}=\frac{3-\sqrt{3}}{6} and C_{n}=\sigma(W_{n}-12K_{n}) . The vectors \{W_{n}\}_{n\geq 0} , \{H_{n}\}_{n\geq 0} and \{K_{n}\}_{n\geq 0} are independent and Gaussian distributed with W_{n}\sim\mathcal{N}\left(0,h_{n}I_{d}\right) , H_{n}\sim\mathcal{N}\left(0,\frac{1}{12}h_{n}I_{d}\right) and K_{n}\sim\mathcal{N}\left(0,\frac{1}{720}h_{n}I_{d}\right) for all n\geq 0 . These random vectors can be viewed as the first three coefficients in a polynomial expansion of the Brownian motion W (see Foster et al. 2020 ). In the recent literature, it has become standard practice to understand a method’s efficacy through a non-asymptotic error analysis. More precisely, by finding an upper bound for the 2-Wasserstein distance between the target distribution ( 1 ) and the distribution of X_{n} , the position variable at the n -th iteration, we can establish a mixing rate for the different numerical methods. Quantitatively, we compare the number of steps n required to reach an error of W_{2}(X_{n}\hskip 0.7113pt,e^{-f})\leq\varepsilon . The main theoretical contribution of this paper is that we show that the QUICSORT method achieves a 2-Wasserstein error of \varepsilon in \mathcal{O}(\sqrt{d}\epsilon^{-\frac{1}{3}}) steps under certain smoothness and strong convexity assumption on f . Our central result is as follows: Theorem 2 (QUICSORT non-asymptotic convergence) . Let \{(X_{n},V_{n})\}_{n\geq 0} denote the QUICSORT approximation ( 1 ) where 0<h\leq 1 is fixed. Suppose that the potential f is three time differentiable, strongly convex and its gradient, Hessian and third derivative are all Lipschitz continuous. Then there exists constants \beta,C>0 (not depending on d and h ) such that for n\geq 0 , the 2-Wasserstein distance between the law of