Contractive kinetic Langevin samplers beyond global Lipschitz continuity

Iosif Lytras, Panayotis Mertikopoulos · 2025

Read Contractive kinetic Langevin samplers beyond global Lipschitz continuity by Iosif Lytras, Panayotis Mertikopoulos (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-2509-12031.txt.

Introduction

Sampling from lumpy probability distributions whose gradients grow faster than linearly defeats ordinary Langevin algorithms, and Iosif Lytras with one co-author tame the problem in 2025. Their setting is kinetic, or underdamped, Langevin dynamics for log-concave targets.

A carefully built taming scheme reins in the superlinear growth, yielding two new discretizations of the kinetic Langevin equation. Both turn out to be contractive, meaning two copies of the sampler pull toward each other, and both satisfy a log-Sobolev inequality, a strong mixing guarantee. From those properties the authors derive non-asymptotic bounds, in the 2-Wasserstein distance, between what each algorithm actually produces and the target distribution it aims for.

Catalog record

CREATORIosif Lytras, Panayotis Mertikopoulos
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-12031

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Contractive kinetic Langevin samplers beyond global Lipschitz continuity Iosif Lytras, Panayotis Mertikopoulos Abstract In this paper, we examine the problem of sampling from log-concave distributions with (possibly) superlinear gradient growth under kinetic (underdamped) Langevin algorithms. Using a carefully tailored taming scheme, we propose two novel discretizations of the kinetic Langevin SDE, and we show that they are both contractive and satisfy a log-Sobolev inequality. Building on this, we establish a series of non-asymptotic bounds in 2 2 -Wasserstein distance between the law reached by each algorithm and the underlying target measure. 1 Introduction Consider the problem of sampling from a distribution of the form \pi\propto\exp(-u) where the potential function u\colon\mathbb{R}^{d}\to\mathbb{R} is known but the normalizing constant isn’t. This problem has a wide range of applications in, among others, machine learning, Bayesian inference, physics, and computer science, but the high dimensionality of the sampling space and the geometry of the potential function can make the design of efficient samplers a highly challenging endeavor. A promising way to overcome (at least partially) the difficulties that arise in this setting is by simulating the associated overdamped Langevin SDE \displaystyle\mathrm{d}L_{t} \displaystyle=-\nabla u\left(L_{t}\right)\mathrm{d}t+\sqrt{\frac{2}{\beta}}\mathrm{\penalty\ d}B_{t},\quad t\geq 0 \displaystyle L_{0} \displaystyle=\theta_{0} and exploiting the fact that this SDE admits the target measure \exp(-\beta u) as its unique invariant measure. Inspired by this observation Langevin-based algorithms have become a popular choice for sampling from distributions in high dimensional spaces. There has been a lot of work in providing non-asymptotic results for Unadjusted Langevin algorithm (ULA) under various assumptions such as Lipschitz continuity of \nabla u and convexity of u . Under the assumption of convexity and gradient Lispchitz continuity important results are obtained in Dalalyan 2017 ; Durmus and Moulines 2017 ; Durmus and Moulines 2019 ; Sabanis and Zhang 2019 ; Barkhagen et al. 2021 , while in the non-convex case, under convexity at infinity or dissipativity assumptions, one may consult Cheng et al. 2018a Majka et al. 2020 , Erdogdu et al. 2022 for ULA while for the Stochastic Gradient variant (SGLD) important works are Raginsky et al. 2017 , Chau et al. 2021 , Zhang et al. 2023b . More recently, starting with the work of Vempala and Wibisono 2019 important estimates have been obtained under the assumption that the target measure \pi satisfies an isoperimetric inequality and the gradient of u satisfies a global Lipschitz continuity, ( Mou et al. 2022 , Balasubramanian et al. 2022 ). The latter assumption has also been relaxed to a weakly smooth assumption (with the gradient still satisfying a linear growth property), see Nguyen et al. 2021 and Erdogdu and Hosseinzadeh 2021 . Recent advances on sampling has led to a connection with optimization ( Vempala and Wibisono 2019 , Chewi and Stromme 2024 ) where overdamped Langevin dynamics can be seen as an analogous to gradient descent. It is therefore natural to explore momentum-like algorithms ( nes 1983 ) for possible improvements. An example of such a method is the discretization of the underdamped/kinetic Langevin SDE given as \displaystyle dV_{t} \displaystyle=\left(-\gamma V_{t}-\nabla u(\theta_{t})\right)dt+\sqrt{2\gamma}dB_{t} (1) \displaystyle d\theta_{t} \displaystyle=V_{t} where \gamma>0 is the friction coefficient and B_{t} is a d -dimensional Brownian motion. Similarly to the overdamped Langevin SDE, the discretization of this diffusion can be used as both an MCMC sampler and non-convex optimizer ( Gao et al. 2021 ) since under appropriate conditions, the Markov process \left\{\left(\tilde{\theta}_{t},\tilde{V}_{t}\right)\right\}_{t\geq 0} has a unique invariant measure given by {\Pi}(\mathrm{d}\theta,\mathrm{d}v)\propto\exp\left(-\left(\frac{1}{2}|v|^{2}+u(\theta)\right)\right)\mathrm{d}\theta\mathrm{d}v. (2) Consequently, the marginal distribution of ( 2 ) in \theta is precisely the target measure \pi . This means that sampling from ( 2 ) in the extended space and then keeping the samples in the \theta space defines a valid sampler for the density \pi . The underdamped Langevin MCMC has shown improved convergence rates in the case of convex and gradient Lipschitz smooth potential u , e.g see Cheng et al. 2018b , Dalalyan and Riou-Durand 2020 , Monmarché 2021 Altschuler and Chewi 2024 . In the non-convex setting important work has been done in Akyildiz and Sabanis 2020 , Gao et al. 2018 , Chau and Rasonyi 2019 , Ma et al. 2021 , Zhang et al. 2023a , while there has been a lot of effort in analyzing the contractive behaviour of these algorithms ( Monmarché 2021 , Leimkuhler et al. 2024 ). All these works assume that the gradient of the potential u grows at most linearly. The current article aims to extend the landscape and allow for super-linear gradient growth aiming to answer the following questions: • Can we create contractive numerical schemes based on the underdamped Langevin SDE, when the gradient grows superlinearly? • What are the convergence rates of these schemes? The current article manages to answer these questions sufficiently by providing novel insights for the contraction rates of modified ULMC in this ill-conditioned scenario, but also provide state of the art convergence results. Our contributions can be summarized as follows: 1. Monotonicity-preserving taming scheme. We introduce a novel drift regularization h_{\lambda} which is both globally Lipschitz and strongly monotone, while converging to the true gradient \nabla u as the stepsize \lambda\rightarrow 0 . This construction extends taming approaches in the sampling literature and provides new technical tools for handling super-linear gradients in kinetic Langevin dynamics. 2. Contractivity of underdamped discretizations. Using a weighted Euclidean norm, we prove that both the tamed stochastic exponential scheme and the tamed OBABO scheme are contractive in an almost sure sense. This establishes, for the first time, explicit contraction rates for underdamped numerical schemes beyond the globally Lipschitz regime. 3. Log Sobolev inequality of the underdamped discretizations. We are able to prove that our discretizations satisfy uniform in the number of iterations Log-Soboelv inequalities. Establishing show the concentration properties of the algorithms and could possibly have other implications for the use of these algorithms in fields such as differential privacy. 4. Non-asymptotic convergence guarantees. We derive quantitative bounds in the 2 -Wasserstein distance between the law of the algorithms and the target distribution. Our results yield iteration complexity O\left(\frac{\log(1/\varepsilon)}{\varepsilon^{2.5}}\right) to reach an \varepsilon -approximation, which improves upon existing bounds for tamed exponential Euler methods and is new for spitting methods in this regime. 2 Preliminaries 2.1 Blanket assumptions Let h:=\nabla u . The following assumptions will be in force throughout the article. Assumption 1 . (strong convexity). There exists an m>0 such that \langle h(x)-h(y),x-y\rangle\geq 2m|x-y|^{2}\quad x,y\in\mathbb{R}^{d}. Assumption 2 . (Local Lipschitz continuity). There exist l>0 and L>0 such that |h(x)-h(y)|\leq L(1+|x|+|y|)^{l}|x-y|\quad x,y\in\mathbb{R}^{d}. Assumption 3 . There holds \mathbb{E}|\theta_{0}|^{2k}+\mathbb{E}|V_{0}|^{2k}<\infty\quad\forall k\in\mathbb{N}. 2.2 Discretizations of the Kinetic Langevin SDE with general drift coefficient We consider numerical schemes for the kinetic (underdamped) Langevin SDE \displaystyle dV_{t} \displaystyle=-\gamma V_{t}\,dt-\nabla u(\theta_{t})\,dt+\sqrt{2\gamma}dB_{t}, (3) \displaystyle d\theta_{t} \displaystyle=V_{t}\,dt, where \gamma>0 is the friction coefficient and B_{t} is a d -dimensional Brownian motion. In the standard case, the drif coeficient is b=-\nabla u . In our setting, we will introduce two schemes with modified drifts b=h_{\lambda} depending on the step size \lambda , which is carefully designed to handle super-linear growth of the gradient. 2.2.1 Stochastic exponential scheme In this section we propose a modified version of the stochastic exponential scheme, an algorithm which was first developed in Cheng et al. 2018b and analysed in

Read the complete text