2025/08/22 by Scott, Maximilian, O'Kane, Dáire, Jelinčič, Andraž +1
#60J22 #60L90 #62F15 #65C30 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Probability (math.PR) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2508.16485
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).