labelfont=bf,justification=centering [Pan]PMMediumBlue

# Tamed Langevin Sampling under Weaker Conditions

Iosif Lytrasc,∗,⋄ c Corresponding author.  ∗ Athena/Archimedes Research
Centre, Athens, Greece.  ⋄ The University of Edinburgh, Edinburgh, UK.
<EMAIL_ADDRESS>and  Panayotis Mertikopoulos♯ ♯ Univ. Grenoble Alpes,
CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
<EMAIL_ADDRESS>
###### Abstract.

Motivated by applications to deep learning which often fail standard Lipschitz
smoothness requirements, we examine the problem of sampling from distributions
that are not log-concave and are only weakly dissipative, with log-gradients
allowed to grow superlinearly at infinity. In terms of structure, we only
assume that the target distribution satisfies either a Log-Sobolev or a
Poincare inequality and a local Lipschitz smoothness assumption with modulus
growing possibly polynomially at infinity. This set of assumptions greatly
exceeds the operational limits of the “vanilla” ULA, making sampling from such
distributions a highly involved affair. To account for this, we introduce a
taming scheme which is tailored to the growth and decay properties of the
target distribution, and we provide explicit non-asymptotic guarantees for the
proposed sampler in terms of the KL divergence, total variation, and
Wasserstein distance to the target distribution.

###### Key words and phrases:

Langevin sampling; taming; isoperimetry; Poincaré inequality; log-Sobolev
inequality; weak dissipativity.

###### 2010 Mathematics Subject Classification:

Primary 65C05, 60H10; secondary 68Q32.

##  1\. Introduction

A broad array of modern and emerging machine learning architectures relies on
being able to sample efficiently from a target distribution $\pi$ on
$\mathbb{R}^{d}$, typically expressed in Gibbs form as
$\pi(x)\propto\exp(-u(x))$ for some potential function
$u\colon\mathbb{R}^{d}\to\mathbb{R}$. Under suitable assumptions for $u$, this
distribution arises naturally as the invariant measure of the Langevin
stochastic differential equation

$dX_{t}=-\nabla u(X_{t})\>dt+\sqrt{2}\>dB_{t}$ (LSDE)

where $B_{t}$ is a canonical Wiener process (Brownian motion) in
$\mathbb{R}^{d}$ with unit volatility. Based on this key property of (LSDE),
one of the most – if not _the_ most – widely used algorithmic schemes for
sampling from $\pi$ is the so-called _unadjusted Langevin algorithm_ (ULA),
given in recursive form as

$\theta_{n+1}^{\operatorname{ULA}}=\theta_{n}^{\operatorname{ULA}}-\lambda
h\big{(}\theta_{n}^{\operatorname{ULA}}\big{)}+\sqrt{2\lambda}\xi_{n+1}$ (ULA)

where $\theta_{n}\in\mathbb{R}^{d}$, $n=1,2,\dotsc$, is the algorithm’s state
variable, $\xi_{n}$ is an independent and identically distributed (i.i.d.)
sequence of standard $d$-dimensional random variables with unit covariance,
$\lambda>0$ is a step-size parameter, and $h\coloneqq\nabla u$ denotes the
gradient of $u$. The idea behind (ULA) is that
$\theta_{n}^{\operatorname{ULA}}$ can be seen as an Euler-Maruyama
discretization of (LSDE) so, for sufficiently large $n$ and small enough
$\lambda$, $\theta_{n}^{\operatorname{ULA}}$ will be distributed according to
some approximate version of the invariant measure of (LSDE), which is
precisely the target distribution $\pi$.

This simple idea has generated a vast corpus of literature and techniques for
proving the non-asymptotic convergence rate of (ULA) in different probability
metrics, the most popular ones being the Wasserstein and total variation
distances, as well as the Kullback–Leibler (KL) and/or Rényi divergence. Much
of this literature has focused on the case where the target distribution $\pi$
is log-concave and has Lipschitz continuous log-gradients, corresponding
respectively to convexity and Lipschitz smoothness of the potential $u$; for
some representative recent works, see Dalalyan [12], Durmus & Moulines [13,
14], Barkhagen et al. [5] and references therein.

Beyond these works, especially when the target distribution is multimodal,
there has been significant effort to relax the (strong) convexity requirement
for $u$ by means of a combination of “convexity at infinity” and
“dissipativity” assumptions – that is, convexity outside a compact set, and a
drift coercivity condition of the form $\langle{h(x)},{x}\rangle=\Omega(\lvert
x\rvert^{2})$ for the drift $h=\nabla u$ of (LSDE) respectively, cf. Cheng et
al. [10], Majka et al. [23], Erdogdu et al. [16], as well as a recent thread
of results on the related stochastic gradient Langevin dynamics (SGLD) scheme
by Raginsky et al. [30], Chau et al. [9] and Zhang et al. [34].

At the same time, building on an important insight of Vempala & Wibisono [33],
a parallel thread in the literature has explored at depth the role of
isoperimetric inequalities in establishing the (rapid) convergence of (ULA)
when the potential of $\pi$ is Lipschitz smooth, either via the use of a
_logarithmic Sobolev inequality_ (LSI) in the case of Mou et al. [26] and
Chewi et al. [11], or a _Poincaré inequality_ (PI) in the case of
Balasubramanian et al. [4], and even weaker inequalities in Mousavi-Hosseini
et al. [27] possibly reducing the degree of smoothness to (global) Hölder
continuity of the drift of (LSDE), cf. Nguyen et al. [29] and Erdogdu &
Hosseinzadeh [15],Mousavi-Hosseini et al. [27].

##### Our contributions in the context of related work.

Our paper seeks to bridge these branches of the sampling literature – the
relaxation of global Lipschitz smoothness requirements and the relaxation of
convexity requirements via the use of isoperimetric inequalities – and, in so
doing, to bring together the best of both worlds. Specifically, motivated by
applications to the optimization and sampling of deep learning models (which
are notoriously non-Lipschitz), we seek to answer the following question:

How to sample efficiently in the absence of log-concavity and linear gradient
growth properties? Can one derive bounds in different distances with weaker
assumptions?

This is a difficult setting for sampling because, as has been noted in several
works, both (ULA) and its SGLD variants may be highly unstable in such
scenarios; in particular, when the drift coefficient of (ULA) exhibits
superlinear growth, the Euler-Marauyama scheme – which forms the core
component of (ULA) – diverges in a very strong sense. A key result in this
direction was obtained by Hutzenthaler et al. [17] who showed that the
difference of the exact solution of a stochastic differential equation (SDE)
and its numerical approximation, diverges to infinity in the strong mean
square sense, even at a finite point in time. This negative result has shown
that superlinear growth of the drift coefficient directly results in a blow-up
of the moments of the numerical approximation scheme used to generate samples,
which thus explains the failure of these algorithms.

Providing an efficient work-around to this issue is not easy, and one needs to
explore the roots of (ULA) for a possible answer – specifically, going all the
way back to the initial observation that (ULA) is an Euler-Maruyama numerical
apporximation scheme for the trajectories of (LSDE), and using the theory of
numerical solutions of SDEs to explore a different angle of attack. In this
regard, a technology tailored to solving SDEs with superlinearly growing
drifts first emerged in the works of Hutzenthaler et al. [18] and Sabanis [31,
32], revolving around a technique known as “taming”. The idea of these schemes
is to create an adaptive Euler scheme with a new drift coefficient
$\mu^{\lambda}$ which is a “tamed”, rescaled version of the original drift,
with the step-size of the algorithm appearing in the rescaling factor, and
with the aim of ensuring the following dove-tailing properties:

  1. (P1)

$\mu^{\lambda}$ has at most linear growth, that is,
$\mu^{\lambda}(x)=\operatorname{\mathcal{O}}(\lvert x\rvert)$ for large $x$.

  2. (P2)

$\mu^{\lambda}$ converges pointwise to $\mu$ in the limit $\lambda\to 0$.

This technique has been applied previously in the setting of Langevin-based
sampling in multiple works under strong dissipativity or convexity assumptions
[7; 19], in the stochastic gradient case [21] under a “convexity at infinity”
assumption [28] and, in a concurrent work, under a logarithmic Sobolev
inequality coupled with a $2$-dissipativity assumption [22]. However, even
though it is fairly common for distributions with superlinearly growing log-
gradients to satisfy a logarithmic Sobolev inequality, it is not always
possible obtain a bound that remains well-behaved with respect to the
dimension – and similar limitations also hold for the $2$-dissipativity
condition.

| Convexity | Dissipativity
---|---|---
Brosse et al. [7] |  strongly convex (for $W_{2}$) | $\langle x\mathopen{}|\mathopen{}\nabla u(x)\rangle\geq c\lvert\nabla u(x)\rvert\lvert x\rvert$
Neufeld et al. [28] | convex at infinity |  $(2+r)$-dissipative ($r>0$)
Lytras & Sabanis [22] | LSI |  $2$-dissipative
Current work |  PI \+ WC / LSI |  $1$-dissipative
Table 1. Comparison of convexity and dissipativity assumptions in related works. |  KL Divergence | Total Variation | Wasserstein | Constants
---|---|---|---|---
Brosse et al. [7] | — | $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{2})$ |  $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon)$ 2 [$W_{2}$] | $\exp(\operatorname{\mathcal{O}}(d))$
Neufeld et al. [28] | — | — |  $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{2})$ [$W_{2}$] | $\exp(\operatorname{\mathcal{O}}(d))$
Lytras & Sabanis [22] | $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon)$ | $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{2})$ |  $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{2})$ [$W_{2}$] | $\operatorname{poly}(d)/C_{\operatorname{LSI}}$
Current work(under logarithmic Sobolev inequality (LSI)) | $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon)$ | $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{2})$ |  $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{2})$ [$W_{2}$] | $\operatorname{poly}(d)/C_{\operatorname{LSI}}$
Current work (under Poincaré inequality (PI)) | $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{3})$ | $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{6})$ |  $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{8})$ [$W_{1}$] | $\operatorname{poly}(d)/C_{\operatorname{PI}}$
Table 2. Comparison of convergence rates under different assumptions; factors
that are logarithmic in $1/\varepsilon$ have been absorbed in the tilded
$\tilde{\operatorname{\mathcal{O}}}(\boldsymbol{\cdot})$ notation. The
observed drop relative to the concurrent work of Lytras & Sabanis [22] is due
to the weaker assumptions made in our paper – Poincaré vs. log-Sobolev and
weak dissipativity vs. $2$-dissipativity (or higher), cf. Table 1. The
constants $C_{\operatorname{LSI}}$ and $C_{\operatorname{PI}}$ refer to the
(positive) constants that appear in the log-Sobolev and Poincaré inequalities
respectively.

The main contribution of our paper is to provide a bridge between these two
worlds and bring to the forefront the best properties of both: sampling
efficiently from potentials with locally Lipschitz log-gradients that may grow
polynomially at infinity, with a drift coefficient that is only
$1$-dissipative (instead of $2$-dissipative) and a considerably lighter
Poincaré inequality requirement – as opposed to the more rigid framework
imposed by the use of LSIs. Specifically, we propose two novel algorithmic
schemes, the _weakly dissipative tamed unadjusted Langevin algorithm_ (wd-
TULA) and the _regularized tamed unadjusted Langevin algorithm_ (reg-TULA)
which allow us to simultaneously treat superlinearly growing drift
coefficients for target distributions satisfying a Poincaré inequality, the
former under a weak convexity (WC) requirement, the latter without. For
completeness, we also show that the proposed taming schemes achieve optimal
convergence rates in the presence of stronger LSI conditions.

To position these contributions in the context of related work, Table 1
summarizes our paper’s assumptions relative to the most closely related works
in the literature, and Table 2 provides a side-by-side comparison of the
achieved rates. To the best of our knowledge, the work closest to our own is
the concurrent work of Lytras & Sabanis [22], who provide a tamed algorithmic
scheme achieving an $\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon)$ rate
of convergence to $\pi$ in the KL divergence metric (respectively
$\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{2})$ in terms of the total
variation and Wasserstein $W_{2}$ distance). Due to the relaxation from a
logarithmic Sobolev inequality to a considerably weaker Poincaré inequality,
our rates do not match those of Lytras & Sabanis [22] in the case of the KL
and total variation (TV) metrics – where weakly dissipative tamed unadjusted
Langevin algorithm (wd-TULA) achieves a rate of
$\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{3})$ and
$\tilde{\operatorname{\mathcal{O}}}(1/\varepsilon^{6})$ respectively, cf.
Table 2 (the Wassserstein metrics are otherwise incomparable; see also Theorem
3 for the rates without any WC requirements). This also applies to the
“convexity at infinity” assumption of Neufeld et al. [28], which has been
shown to imply an LSI, and is thus considerably more stringent than the PI
setting of our paper. Importantly, our analysis still carries a polynomial
dependence on the dimensionality of the problem, in contrast to the analysis
of Neufeld et al. [28] where the dependence is exponential. These aspects of
our results are particularly intriguing for future work on the subject, as
they open a hitherto unexplored link between the isoperimetric inequalities,
the role of coercivity in the target distribution in a superlinearly-growing
gradient setting.

##  2\. Setup and blanket assumptions

In this section, we provide the necessary groundwork for stating the proposed
algorithmic schemes and our main results.

###  2.1. Notational conventions

We begin by fixing notation and terminology. Throughout our paper,
$\lvert\boldsymbol{\cdot}\rvert$ denotes the Euclidean norm of a vector,
$\lVert\boldsymbol{\cdot}\rVert$ the spectral norm of matrix; the Frobenius
norm will be denoted by $\lVert\boldsymbol{\cdot}\rVert_{F}$, and the total
variation distance by $\lVert\boldsymbol{\cdot}\rVert_{\mathrm{TV}}$. For a
sufficiently smooth function $f\colon\mathbb{R}^{d}\to\mathbb{R}$, we will
write $\nabla f$, $\nabla^{2}f$ and $\Delta f$ for its gradient, Hessian
matrix, and Laplacian respectively, and $J^{(i)}f$ for its $i$-th order
Jacobian. We also write $\mathcal{H}^{k}$ for the usual Sobolev space.

For any two probability measures $\mu$, $\nu$ on a measurable space $\Omega$
with a $\sigma$-algebra understood from the context, we will write $d\mu/d\nu$
for the Radon-Nikodym derivative of $\mu$ with respect to $\nu$ when $\mu$ is
absolutely continuous relative to $\nu$ ($\mu\ll\nu$). In this case, the
_Kullback–Leibler_ (KL) divergence of $\mu$ with respect to $\nu$ is defined
as

${H}_{\nu}(\mu)=\int_{\Omega}\frac{d\mu}{d\nu}\log\left(\frac{d\mu}{d\nu}\right)d\nu.$
(KL)

We say that $\zeta$ is a _transference plan_ of $\mu$ and $\nu$ if it is a
probability measure on $\mathbb{R}^{d}\times\mathbb{R}^{d}$ (endowed with the
standard Borel algebra) and we have
$\zeta\left(A\times\mathbb{R}^{d}\right)=\mu(A)$ and
$\zeta\left(\mathbb{R}^{d}\times A\right)=\nu(A)$ for every Borel subset $A$
of $\mathbb{R}^{d}$. We denote by $\Pi(\mu,\nu)$ the set of transference plans
of $\mu$ and $\nu$. Furthermore, we say that a couple of
$\mathbb{R}^{d}$-valued random variables $(X,Y)$ is a coupling of $\mu$ and
$\nu$ if there exists $\zeta\in\Pi(\mu,\nu)$ such that $(X,Y)$ is distributed
according to $\zeta$. Finally, for two probability measures $\mu$ and $\nu$ on
$\mathbb{R}^{d}$, the Wasserstein distance of order $p\geq 1$ is defined as

$W_{p}(\mu,\nu)=\left(\inf_{\zeta\in\Pi(\mu,\nu)}\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}\lvert
x-y\rvert^{p}\>d\zeta(x,y)\right)^{1/p}.$ (1)

###  2.2. Blanket assumptions

Throughout what follows, we will write $\pi\coloneqq e^{-u}\big{/}\int e^{-u}$
for the target distribution to be sampled, and $Lf=\Delta f-\Gamma(u,f)$ for
the infinitesimal generator of (LSDE), where $\Gamma(f,g)=\langle\nabla
f\mathopen{}|\mathopen{}\nabla g\rangle$ denotes the carré du champ operator
for $f,g\in\mathcal{H}^{1}$.

We begin by stating our blanket assumptions for (LSDE):

######  Assumption 1.

The drift $h=\nabla u$ of (LSDE) satisfies the following conditions:

  1. (A1)

_Polynomial Lipschitz continuity:_

$\lvert h(x)-h(y)\rvert\leq L^{\prime}(1+\lvert x\rvert+\lvert
y\rvert)^{l^{\prime}}\lvert x-y\rvert$ (PLC)

for some $L^{\prime},l^{\prime}>0$ and for all $x,y\in\mathbb{R}^{d}$

  2. (A2)

_Weak dissipativity:_

$\langle h(x)\mathopen{}|\mathopen{}x\rangle\geq A\lvert x\rvert^{a}-b$ (WD)

for some $a\geq 1$, $A,b>0$ and for all $x\in\mathbb{R}^{d}$.

  3. (A3)

_Polynomial Jacobian growth:_

$\max\\{\lvert h(x)\rvert,\lVert J^{(i)}(h)(x)\rVert\\}\leq L(1+\lvert
x\rvert^{2l})$ (PJG)

for some $L,l>0$ and for all $x\in\mathbb{R}^{d}$.

Of the above, Item (A1) posits that $h$ is locally Lipschitz continuous, with
the modulus of Lipschitz continuity (essentially the largest eigenvalue of the
Hessian of $u$) growing possibly at a polynomial rate at infinity. As such,
Item (A1) allows us to capture a very broad spectrum of applications with
superlinear Hessian growth (especially in the context of deep learning
landscapes that exhibit polynomial growth with a degree equal to the depth of
the underlying network).

Item (A2) is at the core of our analysis, as it enables us to provide moment
bounds that are uniform in time: it is essentially a coercivity assumption,
but with a relaxed exponent relative to the $2$-dissipativity framework of
other works, which can be fairly restrictive if the tails of the target
distribution are thicker than sub-Gaussians. For generality, we treat not only
the case of $1$-dissipative gradients, but all dissipativity exponents $a\geq
1$. In practice, although it is quite possible that $2$\- dissipativity may
hold for a given distribution, $a$-dissipativity for $a<2$ may be much easier
to verify and leverage to produce more favourable constants $A$,$b$.

Finally, Item (A3) is a strictly technnical requirement intended to streamline
our presentation when rigorously differentiating under the integral sign –
that is, exchanging the order of integration and time derivatives – in the use
of a divergence theorem when establishing a differential inequality later in
our paper.

Our next blanket assumption concerns the target distribution $\pi$:

######  Assumption 2.

The target distribution $\pi$ satisfies a _Poincaré inequality_ (PI) of the
form

$\operatorname{Var}_{\pi}(f)\coloneqq\int_{\mathbb{R}^{d}}\left(f-\int_{\mathbb{R}^{d}}f\>d\pi\right)^{2}\>d\pi\leq\frac{1}{C_{\operatorname{PI}}}\int\lvert\nabla
f\rvert^{2}\>d\pi$ (PI)

for some positive constant $C_{\operatorname{PI}}>0$ and all test functions
$f\in\mathcal{H}^{1}(\mathbb{R}^{d})$.

This assumption is weaker than the widely used (but more stringent)
logarithmic Sobolev inequality.

$H_{\pi}(\nu)\coloneqq\int_{\mathbb{R}^{d}}f\log
f\>d\pi\leq\frac{1}{2C_{\operatorname{LSI}}}\int_{\mathbb{R}^{d}}\frac{\Gamma(f,f)}{f}\>d\pi\eqqcolon\frac{1}{2C_{\operatorname{LSI}}}I_{\pi}(\nu),$
(LSI)

for some positive constant $C_{\operatorname{LSI}}>0$ and for every
probability measure $\nu\ll\pi$ with $f\coloneqq d\nu/d\pi$. One should note
that PI can be given as a consequence of the weak dissipativity condition (see
[2]). In the case of diffusion processes, the importance of these inequalities
lies in the fact that (PI) implies exponential ergodicity with respect to the
$\chi^{2}$ divergence, while (LSI) implies exponential ergodicity in relative
entropy. In particular, by the Bakry–Emery theorem [1], (LSI) was established
for strongly convex potentials and is stable under bounded pertrubations,
Lipschitz mappings and convolutions. It also implies Talagrand’s
transporation-cost inequality: if $\mu$ satisfies (LSI), then

$W_{2}(\mu,\nu)\leq\sqrt{\frac{2}{C_{\operatorname{LSI}}}H_{\mu}(\nu)}.$ (2)

By comparison, (PI) is significantly less stringent than (LSI): to begin,
(LSI) implies (PI) with the same constant but, moreover, (PI) has been shown
to hold for dissipative potentials where (LSI) fails, and is also stable under
pertubations, Lipschitz mappings and convolutions. It also implies exponential
moments of some order i.e., $\mathbb{E}_{\mu}e^{q|x|}<\infty$ whenever $\mu$
satisfies (PI).

Our last assumption concerns the convexity characteristics of the potential
$u(x)$ and will be used only in the case where (PI) is the strongest condition
in place.

######  Assumption 3.

$u$ is weakly convex, i.e.,

$\nabla^{2}u(x)\succcurlyeq-KI\quad\text{for some $K>0$ and for all
$x\in\mathbb{R}^{d}$}.$ (WC)

This assumption simply means that the eigenvalues of $\nabla^{2}u(x)$ do not
become arbitrarily negative, and is widely used in the numerical approximation
of SDEs. For our purposes, we will mostly use it in the context of the famous
HWI inequality

$H_{\pi}(\nu)\leq\sqrt{I_{\pi}(\nu)}{W_{2}(\pi,\nu)}+\frac{K}{2}W_{2}^{2}(\pi,\nu)\quad\text{for
all $\pi,\nu\in\mathcal{P}_{2}(\mathbb{R}^{d})$}.$ (HWI)

To provide a glimpse of the analysis to come, we will develop and examine two
novel taming schemes, one non-regularized and one regularized, that are
tailored to the dissipativity profile of the initial potential, and which
cover the following cases:

  1. (1)

When the potential satisfies (LSI).

  2. (2)

For the non-regularized case: when (LSI) fails and the potential satisfies
(PI) along with (WC).

  3. (3)

For the regularized case: when (LSI) fails and the potential only satisfies
(PI).

###  2.3. The failure of the unadjusted Langevin algorithm

Before moving forward with the development of the taming schemes mentioned
above, we conclude this section with a simple – but not simplistic –
$1$-dimensional example that satisfies our range of assumptions, but where the
“vanilla” unadjusted Langevin algorithm fails.

Setting $u(x)=x^{3}/3$ and applying (ULA) with step-size $\lambda$ and initial
condition $X_{0}=\mathcal{N}(0,\frac{4}{\lambda})$, we get

$X_{n+1}=X_{n}-\lambda X_{n}^{2}+\sqrt{2\lambda}\xi_{n+1}$

Then, since $X_{n}$ is independent of ${\xi}_{n+1}$

$\mathbb{E}[X_{n+1}^{2}]=\mathbb{E}\left[X_{n}^{2}(1-\lambda
X_{n})^{2}\right]+2\lambda=\mathbb{E}X_{n}^{2}(1-2\lambda\mathbb{E}X_{n}+\lambda^{2}\mathbb{E}X_{n}^{2})+2\lambda$

using the inequality $1-2x+x^{2}\geq-1+\frac{1}{2}x^{2}$ one obtains

$\mathbb{E}[X_{n+1}^{2}]\geq-\mathbb{E}X_{n}^{2}+\frac{1}{2}\lambda^{2}\mathbb{E}X_{n}^{6}\geq-\mathbb{E}X_{n}^{2}+\frac{\lambda^{2}}{2}\left(\mathbb{E}X_{n}^{2}\right)^{3}+2\lambda$

where the last step was obtain by Jensen’s inequality. Applying for $n=0$ it
is easy to see that

$\mathbb{E}X_{1}^{2}\geq(\mathbb{E}X_{0}^{2})\left(\frac{\lambda^{2}}{2}\mathbb{E}(X_{0}^{2})^{2}-1\right)+2\lambda\geq\mathbb{E}X_{0}^{2}+2\lambda.$

Iterating over $n$ yields

$\mathbb{E}X_{n+1}^{2}\geq\mathbb{E}X_{n}^{2}+2\lambda n.$ (3)

We thus see that the second moment of the algorithm’s iterates diverges as
$n\to\infty$, indicating in this way that (ULA) cannot be used to sample from
the target distribution.

##  3\. Tamed schemes and main results

We now proceed to state our tamed algorithmic schemes and main results.

###  3.1. Taming without regularization

To streamline our presentation and ease the introduction of the various
components of the analysis, we begin with the case where the eigenvalues of
$\nabla^{2}u$ do not become arbitrarily negative, i.e., $u$ satisfies the weak
convexity assumption (WC). In this case, we will consider the _weakly
dissipative tamed unadjusted Langevin algorithm_ that iterates as

$\bar{\theta}_{n+1}^{\lambda}=\bar{\theta}_{n}^{\lambda}-\lambda
h_{\lambda}(\bar{\theta}_{n}^{\lambda})+\sqrt{2\lambda}\xi_{n+1}\quad\text{for
all $n=0,1,\dotsc$}$ (wd-TULA)

where $\theta_{0}$ is initialized randomly according to a Gaussian
distribution $\pi_{0}$,111The Gaussian requirement could be relaxed by
positing that $\lvert\nabla\log\pi_{0}\rvert$ and
$\lVert\nabla^{2}\log\pi_{0}\rVert$ grow at most polynomially, but we will not
need this level of generality. $\xi_{n}$ is an i.i.d. sequence of Gaussian
$d$-dimensional vectors with unit covariance, and the _tamed drift_
$h_{\lambda}$ is given by

$h_{\lambda}(x)=\frac{Ax}{(1+\lvert
x\rvert^{2})^{1-a/2}}+f_{\lambda}(x)\quad\text{with}\quad
f_{\lambda}(x)=\frac{f(x)}{1+\sqrt{\lambda}\lvert x\rvert^{2\ell}}$ (4)

where $f(x)=h(x)-\frac{Ax}{(1+\lvert x\rvert^{2})^{1-a/2}}$ and the various
constants defined as in Assumption 1.

To connect (wd-TULA) with the existing literature on tamed schemes, we note
here that the majority of taming factors are either of the form
$h(x)/[1+(\lambda)^{c}\lvert h(x)\rvert]$ for $c=1$ or $c=1/2$ [7], or of the
form $h(x)/[1+\lambda^{c}|x|^{2l-1}]$ [21]. In this regard, the taming scheme
(4) is more intricate: we first split the original gradient drift into a part
which has at most linear growth, and we then proceed to tame the superlinearly
growing part. The drift coefficient of this scheme has the property that it
grows at most as $|x|^{\frac{a}{2}}$ (so it grows at most linearly) while
inheriting the dissipativity condition of the initial gradient. For more
details, see Lemma A.1. In this regard, when the potential satisfies a
stronger $2$-dissipativity condition, we recover the taming scheme of Lytras &
Sabanis [22].

Our main result for (wd-TULA) may then be stated as follows:

######  Theorem 1.

Suppose that Assumptions 1, 2 and 3 hold and let $\rho_{n}$ denote the
distribution of the $n$-th iterate of (wd-TULA) run with
$\lambda<\lambda_{\max}=\min\\{\frac{1}{4(2AC^{*}+2L+1)^{2}},\frac{1}{\dot{c}_{0}H_{\pi}(\rho_{0})},\frac{2}{\mu^{2}}\\}$
where the constants are given in the proof of Proposition A.2 and Lemmas A.2,
Proposition A.3 .

Then $\rho_{n}$ enjoys the convergence guarantee

$H_{\pi}(\rho_{n})\leq\left(1-\frac{\dot{c}_{0}}{2}\lambda^{3/2}\right)^{n}H_{\pi}(\rho_{0})+\left(1+\frac{4c_{1}}{c_{0}}\right)\sqrt{\lambda}$
(5)

where $c_{1}$ depends polynomially on $d$ and $\dot{c}_{0}$ is an explicit
function of the Poincaré constant $C_{\operatorname{PI}}$ of (PI). In
particular, given a tolerance level $\varepsilon>0$, (wd-TULA) achieves
$H_{\pi}(\rho_{n})\leq\varepsilon$ within
$n\geq\dot{c}_{0}^{-1}(1+c_{1}/\dot{c}_{0})^{3}\log(2/\varepsilon)/\varepsilon^{3}=\tilde{\Theta}(1/\varepsilon^{3})$
if run with step-size
$\lambda\leq\varepsilon^{2}/[4(1+4C_{1}/\dot{c}_{0})^{2}]$.

This theorem ensures that the algorithm converges at a polynomial rate, even
in the absence of (LSI). This is very important in practice as, even if (LSI)
holds, it is usually difficult to derive explicit bounds with nice dependence
on the problem’s defining parameters. More to the point, if (LSI) holds and
$C_{\operatorname{LSI}}$ is known, the proposed algorithm exhibits optimal
convergence rates, achieving in this way the best of both worlds:

######  Theorem 2.

Suppose that Assumption 1 and (LSI) hold. Let $\rho_{n}$ be the distribution
of $n-th$ iterate of the algorithm (wd-TULA). Then, for
$\lambda\leq\lambda_{\max}$, we have

$H_{\pi}(\rho_{n})\leq
e^{-\frac{3}{2}C_{LSI}\lambda(n-1)}H_{\pi}(\rho_{0})+\frac{\hat{C}}{\frac{3}{2}C_{LSI}}\lambda$

where $\hat{C}$ depends polynomially on the dimension with leading term at
most $\mathcal{O}\left(d^{\max\\{2,l^{\prime}+1\\}(2l+1)}\right)$. In
particular, given a tolerance level $\varepsilon>0$, if (wd-TULA) is run with
step-size $\lambda\leq\frac{3\epsilon C_{LSI}}{2\hat{C}}$, for
$n\geq\frac{2\hat{C}}{\epsilon}C_{LSI}^{-1}\log(\frac{2}{\epsilon}H_{\pi}(\rho_{0}))=\tilde{\Theta}(1/\varepsilon)$
iterations, we have $H_{\pi}(\rho_{n})\leq\epsilon.$

Theorems 1 and 2 are our main results for (wd-TULA). The proof of both
theorems is fairly arduous and involves a series of intricate steps, so, to
streamline our presentation and facilitate our comparison with the case where
(WC) is dropped altogether, we proceed directly to the regularized version of
(wd-TULA) and defer the discussion of the proof of the theorem to the next
section.

###  3.2. Regularized taming

We consider now the case where the eigenvalues of $\nabla^{2}u(x)$ become
arbitrarily negative (i.e., Assumption 3 fails altogether). To account for
this negative growth, we are going to regularize the tamed potential by
anchoring it close to the original target. This will require care to ensure
that the new sampling potential satisfies Assumption 3 with a controllable
constant, as well as the corresponding regularity requirements of Assumption
1.

Without further ado, these considerations lead to the _regularized potential_

$u_{r,\lambda}(x)=u(x)+\lambda\lvert x\rvert^{2r+2}$ (6)

where, with a fair degree of hindsight, the exponent $r$ is chosen so that
$r>l/2$ and $r(2+l^{\prime})/[(r+1)(2r-l^{\prime})]<1$ (a moment’s reflection
shows that this is not the empty set).

In view of the above, the _regularized taming_ scheme that we will consider
involves rescaling by the factor $(1+\sqrt{\lambda}\lvert x\rvert^{2r+1})$,
leading to the regularized drift:

$h_{r,\lambda}(x)=\frac{Ax}{(1+|x|^{2})^{1-\frac{a}{2}}}+\frac{\nabla
u_{r,\lambda}(x)-Ax(1+|x|^{2})^{a/2-1}}{1+\sqrt{\lambda}|x|^{2r+1}}.$ (7)

In this way, we obtain the _regularized tamed unadjusted Langevin algorithm_

$\bar{x}_{n+1}^{\lambda}=\bar{x}_{n}^{\lambda}-\lambda
h_{r,\lambda}(\bar{x}_{n}^{\lambda})+\sqrt{2\lambda}\Xi_{n+1}$ (reg-TULA)

where $\Xi_{n}$ is an i.i.d. sequence of Gaussian $d$-dimensional vectors. Our
main result for this regularized sampling scheme may then be stated as
follows:

######  Theorem 3.

Suppose that Assumptions 1 and 2 hold and let $\rho^{\operatorname{reg}}_{n}$
denote the distribution of the $n$-th iterate of (reg-TULA) run with
$\lambda<\lambda_{\max,2}:=\min\\{\lambda_{\max},\frac{ln2}{R_{2}^{2r+2}}\\}$
where $R_{2}$ is given in Lemma A.8. Then $\rho^{\operatorname{reg}}_{n}$
enjoys the convergence guarantee

$H_{\pi}(\rho^{\operatorname{reg}}_{n})\leq\left(1-c\lambda^{1+\frac{1}{r+1}+\frac{l}{2r-l}}\right)^{n-1}H_{{\pi_{\operatorname{reg}}}}(\rho_{0})+(\hat{C}/c)\lambda^{1-\frac{1}{r+1}-\frac{l}{2r-l}}+C_{3}\lambda$
(8)

where $c,C_{3},\hat{C}$ depend polynomially on $d$. In particular, if
$c_{l,r}:=\frac{r(2+l)}{(r+1)(2r-l)}$, then, for
$\lambda<\mathcal{O}\left({\epsilon}^{\frac{1}{1-c_{l,r}}}\right),$ we have

$H_{{\pi_{\operatorname{reg}}}}(\rho^{\operatorname{reg}}_{n})\leq\epsilon\quad\text{after}\quad
n=\Theta\left(\log(1/\epsilon)\cdot\epsilon^{-\frac{1+c_{l,r}}{1-c_{l,r}}}\right)\quad\text{iterations}.$

##  4\. Proof outline and technical innovations

To give an idea of the main ideas and technical innovations required for the
proof of Theorems 1, 2 and 3, we provide below a brief roadmap of our proof
strategy.

The cornerstone of our approach is the derivation of a differential inequality
in the spirit of Vempala & Wibisono [33]. The tricky part here is that the
drift coefficient is not the original gradient but a tamed one, which yields
additional complexity when one tries to prove the exchange of integrals and
derivatives starting from the Fokker-Planck equation. In so doing, we
ultimately obtain a “template inequality” of the form

$\frac{d}{dt}H_{\pi}(\hat{\pi}_{t})\leq-\frac{3}{4}I_{\pi}(\hat{\pi}_{t})+\mathbb{E}|h(\theta_{t})-h_{\lambda}(\theta_{k\lambda})|^{2}$
(9)

where $\hat{\pi}_{t}$ is the continuous-time interpolation of the algorithm.

The first term of the template inequality (9) is connected to the relative
entropy via an isoperimtric inequality, either directly – if (LSI) holds – or
by means of another inequality – under (PI) and (WC). In this last case, the
connection is achieved by establishing a “modified” version of (LSI) as a
consequence of (PI) and (HWI). As for the second term of (9), its contribution
can be controlled by the one-step error of the algorithm (by local
Lipschitzness) and the $L_{2}$ approximation of the tamed scheme to the
original gradient at grid points. A key difficulty here is that these bounds
must be uniform in the number of iterations moment bounds for our algorithm
which is obtained by the careful construction of the tamed coefficient, which
satisfies a dissipativity condition.

This is an important novetlyt of our work, as we are able to achieve a
uniform-in-time exponential moment bound for the algorithm, even in the $1-$
dissipative case (contrary to other works such as [15] where the moments
bounds are not uniform in time or [34] which leverages a “convexity at
infinity” assumption). We achieve this by means of a Herbst argument for
Gaussians (since each iterate is a Gaussian when conditioned to the previous
step), to pass from the conditional expectation of the exponential to the
exponential of the conditional expectation. We then use the contraction
structure (which is provided by the inherited dissipativity of our scheme and
the growth of the tamed drift coefficient as given in Lemma A.1) to create an
induction.

In the absence of _both_ (LSI) _and_ (WC), we employ a similar method to
sample from the regularized potential – for which we prove the equivalent of
(LSI) – and we then proceed to compute the KL divergence of the algorithm’s
iterates relative to the target distribution. The main challenge here is to
show that the regularized potential also satisfies (PI) with a constant that
is explicitly connected to the Poincaré constant of the _original_ target and
is _independent_ of $\lambda$. In general, these are mutually antagonistic
properties, which are ultimately achieved in our case by leveraging the
dissipativity properties of the regularized potential to find a Lyapunov
function $W$ such that $LW\leq-\theta$ for some $\theta>0$ outside of a ball.
By using the inequality for the infinitesimal generator of the Langevin SDE
with drift coeffient the regularized potential, and the fact that, inside said
ball, the regularized measure inherits the Poincaré constant of the original
(as a bounded perturbation thereof), and by employing a variation of a shrewd
argument of Cattiaux et al. [8, Proof of Theorem 2.3], we are finally able to
establish (PI) on the whole space. The conditions of $2$-dissipativity and
weak convexity are then easier to prove, eventually leading to the upgrade of
(PI) to a suitably modified form of (LSI).

A major obstacle in the above strategy is determining the explicit constants
while simultaneously trying to minimize their dependence on the step-size as
much as possible. For example, one can establish a version of (LSI) for the
regularized potential in a more direct manner, by simply using convexity at
infinity, or by a technique similar to Lytras & Sabanis [22, Corollary 5.4].
However, the version of (LSI) obtained in this would involve a catastrophic
exponential dependence on $1/\lambda$, which would thus render it unusable for
deriving finite-time convergence rates. Albeit (significantly) more involved,
our method completely circumvents the exponential dependence, which in turn
enables the polynomial-time convergence rates of the proposed schemes (and
recoups the technical investment described above).

For convenience, we summarize the main steps below, in decreasing order of the
assumptions made.

##### Case 1: Analysis under (LSI).

This case concerns Theorem 2, and the analysis unfolds as follows:

  1. (1)

We prove that the tamed coefficients exhibit linear growth, and inherit the
dissipativity property of the original gradient, cf. Lemma A.1.

  2. (2)

We use the properties of the tamed scheme to derive exponential (and
subsequently polynomial) moments for our algorithm, cf. Lemmas A.2 and A.3.

  3. (3)

We establish a differential template inequality for the relative entropy
between the continuous-time interpolation of the algorithm and target measure,
cf. Corollary 2. This involves a rigorous treatment of the exchange of
derivatives and integrals.

  4. (4)

We bound the remaining terms using the local Lipschitz property of $\nabla u$
and the approximation properties of the tamed scheme.

  5. (5)

We employ (LSI) to conntect the Fisher information term to the relative
entropy, and we backsolve to produce convergence rates in terms of the KL
divergence.

  6. (6)

Using Pinsker’s inequality, we obtain a result for total variation distance
and by Talagrand’s inequality for the $W_{2}$ distance.

##### Case 2: (PI) and (WC).

This case concerns Theorem 1, and the analysis unfolds as follows:

  1. (1)

We employ the same scheme to tame $\nabla u$ and repeat the first steps as in
the proof of Theorem 2.

  2. (2)

Lacking (LSI), our analysis branches out as follows: we use Assumption 3 and
(PI) to produce a different template inequality between the KL divergence and
the Fisher information distance between the continuous-time interpolation of
the algorithm and target measure (Proposition A.2).

  3. (3)

We backsolve the derived differential inequality to produce non-exponential
convergence rates relative to the KL divergence, cf. Propositions A.3 and 6.

  4. (4)

Finally, by using Pinsker’s inequality and the exponential moments of our
alogirthm and the bound in relative entropy, we are able to derive bounds $TV$
and $W_{1}$ distance under (PI), cf. Corollary 3.

##### Case 3: (PI) only.

This case concerns Theorem 3, and the analysis unfolds as follows:

  1. (1)

We introduce a regularized potential to sample from, and we show that it has a
range of desirable properties as described in Lemma A.1.

  2. (2)

We use the same scheme to tame the gradient of the regularized potential and,
through similar arguments, we derive exponential (and polynomial) moments for
(reg-TULA).

  3. (3)

We show that the regularized measure satisfies a version of (PI), cf. Lemma
A.8, and this inequality can be upgraded to a version of (LSI) with manageable
constants (Proposition A.4).

  4. (4)

We branch back to the analysis using (LSI) to sample from the regularized
potential, and we use the relation between the regularized and the original
one to derive the algorithm’s convergence rate, as outlined in Theorem 7.

  5. (5)

Using Pinsker’s and Talagrand’s inequalities, we convert these bounds to $TV$
and $W_{2}$ (Corollary 4).

The details of all the above are provided in full in the paper’s appendix.

##  5\. Numerical Experiments

We proceed by providing some numerical experiments that validate our results.
The focus of our attention will be the invariant measure $\pi$ generated by
the double-well potential $u=(|x|^{2}-1)^{2}$. Since $\nabla u=4x(|x|^{2}-1)$
one easily observes that the potential satisfies our smoothness and
dissipativity assumptions. Since the 1-dissipativity holds one can also deduce
a Poincare inequality for the potential. Finally, it is immediate to see that
the potential satisfies a convexity at infinity assumption, which of course is
way stronger that our weak convexity assumption. For explicit calculations the
interested reader can point to [28]. We perform the experiment for our
algorithm for $10^{6}$ iterations and $10^{5}$ samples for 100 independent
iterations. The dimension is $d=100$ and we start the algorithm from a
constant where every coordinate is zero, but the first coordinate is 200. We
should note that starting from a constant doesn’t contradict our analysis as
we can still perform the analysis of the algorithm starting from the result of
the 1st iteration which is a Gaussian. When one runs ’vanilla’ ULA for
stepsize={0.1, 0.01} all experiments show that the algorithm explodes (the
moments exceed the infinity value of the computer) so the need to use an
alternative becomes apparent. Here we present a boxplot which describes the
the second moment of the first coordinate for different values. The second
moment of each coordinate is given by

$\mathbb{E}\left[X_{i}^{2}\right]=d^{-1}\int_{\mathbb{R}_{+}}r^{2}\nu(r)\mathrm{d}r/\int_{\mathbb{R}_{+}}\nu(r)\mathrm{d}r,\quad\nu(r)=r^{d-1}\exp\left\\{\left(r^{2}/2\right)-\left(r^{4}/4\right)\right\\}$

and is estimated by a random walk of $10^{7}$ samples as
$\mathbb{E}[X_{i}^{2}]=0.104.$ The figure below shows the behaviour of the
algorithm for different stepsizes. One can see that the for stepsize={0.1,
0.01} the error is of order $10^{-1}$ while for stepsize =0.001 the error is
of order $10^{-2}.$

We also present a similar figure for the well-known TULA algorithm devoleped
in [7]. We can see that the TULA algorithm is not as efficient as wd-TULA for
large stepsize as it gives an error of approximately 1.1 but performs better
for stepsize 0.1 (gives error of order $10^{-2}$) and similarly to wdTULA for
$\lambda=0.001.$

Figure 1. Performance of (wd-TULA) compared to TULA (left and right
respectively); lower values are better.

##  Appendix A Preliminary steps and lemmas

###  A.1. Moment bounds for (wd-TULA)

In order to prove the moment bounds for our algorithm, the following
properties of our the tamed coeffient will play a pivotal role.

######  Lemma A.1.

For all $x\in\mathbb{R}^{d}$, we have

$\langle h_{\lambda}(x),x\rangle\geq A_{1}\lvert x\rvert^{a}-B_{1}$ (A.1)

where $A_{1}=A/2$ and $B_{1}=\max\\{A_{1},B\\}$. In addition, we have

$\lvert h_{\lambda}(x)\rvert^{2}\leq 4A^{2}\lvert
x\rvert^{a}+2L^{2}/\lambda+4A^{2}\quad\text{for all $x\in\mathbb{R}^{d}$}.$
(A.2)

###### Proof.

Postponed to the proof section. ∎

######  Lemma A.2.

Let $M:=\left(2(2d+4A^{2}+2L^{2}+A)\right)^{\frac{1}{a}}$ and
$\mu=\frac{AaM^{a}}{16(1+M^{2})^{1-\frac{a}{2}}}.$ Let
$V_{\mu}(x)=e^{\mu(1+|x|^{2})^{\frac{a}{2}}}.$ There holds, for
$\lambda<\min\\{1,\frac{A}{4},\frac{2}{\mu^{2}}\\}$

$\sup_{n}\mathbb{E}V_{\mu}(\bar{\theta}^{\lambda}_{n})\leq C_{\mu}$

where $C_{\mu}\leq\mathcal{O}(e^{\mu d}).$

###### Proof.

Postponed to the Appendix. The main tools used in the proof is the fact that
conditionally on the previous step the algorithm is a Gaussian distribution
and therefore satisfies a Log-Sobolev. We proceed our proof by using the fact
that the function $f(x)=|x|/(1+|x|^{2})$ is 1-Lipschitz and we proceed using
Herbst argument. The dissipativity and growth condition of our scheme enables
to control the key quantity $|x-h_{\lambda}(x)|^{2}$. ∎

######  Lemma A.3.

Let $p\in\mathbb{N}.$ There holds

$\sup_{n}|\bar{\theta}^{\lambda}_{n}|^{2p}\leq C_{p}$

where $C_{p}\leq\mathcal{O}(d^{p})+2p.$

###  A.2. Establishing a key differential inequality regarding KL- divergence

The goal of this Section is to establish a differential inequality that will
be the basis for our analysis. We define the continuous-time interpolation of
our algorithm given as

$\theta_{t}=\theta_{k\lambda}-(t-k\lambda)h_{\lambda}(\theta_{k\lambda})+{\sqrt{2}}(B_{t}-B_{k\lambda}),\quad\forall
t\in[k\lambda,(k+1)\lambda]$ (A.3)

and $\theta_{0}=\bar{\theta_{0}}.$

That way

$\mathcal{L}(\theta_{k\lambda})=\mathcal{L}(\bar{\theta}^{\lambda}_{k})\quad\forall
k\in\mathbb{N}.$

We define the marginal distribution of $\theta_{t}$ as $\hat{\pi}_{t}$. One
notices that, since conditioned on $\theta_{k\lambda}$, $\theta_{t}$ is a
Gaussian its conditional distribution is given by

$\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)=Ce^{-\frac{\sqrt{t-k\lambda}}{2}|x-\mu(t,y)|^{2}}$

where $\mu(t,y)=y-(t-k\lambda)h_{\lambda}(y)$ and $C$ some normalizing
constant. One further notes that, as
$\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)$ can be viewed as a distribution of
a process satisfying a Langevin SDE with constant drift $-h_{\lambda}(y)$ and
initial condition $y$, i.e

$\displaystyle d\hat{\mu}_{t}$
$\displaystyle=-h_{\lambda}(y)dt+\sqrt{2}dB_{t},\quad\forall
t\in(k\lambda,(k+1)\lambda]$ $\displaystyle\hat{\mu}_{k\lambda}$
$\displaystyle=y$

it satisfies the following Fokker-Planck PDE:

$\frac{\partial\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)}{\partial
t}=div\left(\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)h_{\lambda}(y)\right)+\Delta_{x}\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y).$
(A.4)

Based on rigorous work done in the Appendix we are able to prove the analogous
differential in time relative entropy inequality (that originally appeared in
[33] for the vanilla ULA) for our tamed scheme.

######  Proposition A.1.

Let $k\in\mathbb{N}.$ Then, for every $t\in[k\lambda,(k+1)\lambda],$

$\displaystyle\frac{d}{dt}H_{\pi}(\hat{\pi}_{t})$
$\displaystyle=-\int_{\mathbb{R}^{d}}\langle\hat{\pi}_{t}(x)E\left(h_{\lambda}(\theta_{k\lambda})\big{|}\theta_{t}=x\right)+\nabla\hat{\pi}_{t}(x),\nabla\log\hat{\pi}_{t}(x)-\nabla\log\pi\rangle
dx.$

###### Proof.

See Appendix. The idea of the proof is the same as the one in Lytras & Sabanis
[22]. We see that our scheme has nice properties such as $||\nabla
h_{\lambda}||\leq\mathcal{O}(\frac{1}{\sqrt{\lambda}})$ and has polynomially
growing higher derivatives. Working as in Lytras & Sabanis [22] we are able to
produce the following inequality and show that in a small neighbourghood of
$t$

$\hat{\pi}_{t}(x)\leq Ce^{-r|x|^{2}}$

and $|\nabla\log\hat{\pi}_{t}|$ and $||\nabla^{2}\log\hat{\pi}_{t}||$ grow
polynomially in $x$. This enables some change of the integrals and the
derivatives along with application of the divergence theorem. By using Bayes
theorem on the conditional Fokker-Planck equation with the divergence theorem
we produce the following inequality. ∎

######  Theorem 4.

Then, for $\lambda<\lambda_{\max}$ and for every $t\in[k\lambda,(k+1)\lambda]$
,$k\in\mathbb{N},$ there holds

$\frac{d}{dt}H_{\pi}(\hat{\pi}_{t})\leq-\frac{3}{4}I_{\pi}(\hat{\pi}_{t})+\mathbb{E}|h(\theta_{t})-h_{\lambda}(\theta_{k\lambda})|^{2}.$

######  Lemma A.4.

There holds

$\mathbb{E}|\theta_{t}-\theta_{k\lambda}|^{2p}\leq C_{1,p}\lambda^{p}$

The proof follows by using the growth of property of $h_{\lambda}$ and the
uniform in time moment bounds of the algorithm.

######  Lemma A.5.

Then,

$\mathbb{E}|h_{\lambda}(\theta_{k\lambda})-h(\theta_{t})|^{2}\leq
C_{err}\lambda\quad\forall k\in\mathbb{N},$

where $C_{err}$ is given explicitly in the proof and depends at most
polynomially in the dimension.

For this proof we have split the split the difference as follows

$|h(\theta_{t})-h_{\lambda}(\theta_{k\lambda})|^{2}\leq
2|h(\theta_{t})-h(\theta_{k\lambda})|^{2}+2|h(\theta_{k\lambda})-h_{\lambda}(\theta_{k\lambda})|^{2}.$

The first term is bounded using Item (A1) Lemma A.4 and the uniform in time
moment bounds of the algorithm (since
$\mathcal{L}(\theta_{k\lambda})=\mathcal{L}(\bar{\theta}^{\lambda}_{n})$ and
the squared taming error which is of order $\lambda$.
Now we are going to provide an inequality between the relative entropy and the
Fisher information. When LSI is assumed the connection is immediate.

###  A.3. Convergence analysis

####  A.3.1. Convergence under LSI

######  Theorem 5.

Let $\rho_{n}$ be the distribution of $n-th$ iterate of the algorithm (wd-
TULA). Then, for $\lambda\leq\lambda_{max}$,

$H_{\pi}(\rho_{n})\leq
e^{-\frac{3}{2}C_{LSI}\lambda(n-1)}H_{\pi}(\rho_{0})+\frac{\hat{C}}{\frac{3}{2}C_{LSI}}\lambda$

where $\hat{C}$ is given explicitly in the proof and depends polynomially on
the dimension.

Using Talagrand’s inequality one deduces the following result regarding the
convergence in Wasserstein distance.

######  Corollary 1.

There holds,

$W_{2}(\mathcal{L}(\bar{\theta}^{\lambda}_{n}),\pi)\leq\frac{\sqrt{2}}{\sqrt{C_{LSI}}}\left(e^{-\frac{3}{4}(C_{LSI}\lambda(n-1)}H_{\pi}(\rho_{0})+\sqrt{\frac{\beta\hat{C}}{\frac{3}{2}(C_{LSI})}\lambda}\right).$

####  A.3.2. Convergence under PI and weak convexity

When one does not assume any Log-Sobolev inequality other tools are needed to
describe their connection.

######  Proposition A.2.

There exists $\dot{c}_{0}>0$ such that

$H_{\pi}(\hat{\pi}_{t})\leq\frac{1}{\dot{c}_{0}}\sqrt{I_{\pi}(\hat{\pi}_{t})}.$

The relies on a combination of an inequality between the $W_{2}$ distance and
the Fischer information which stems from the Poincare inequality, combined
with the HWI inequality.

######  Corollary 2.

There holds,

$\frac{d}{dt}H_{\pi}(\hat{\pi}_{t})\leq-\dot{c}_{0}{H^{2}_{\pi}}(\hat{\pi}_{t})+C_{err}\lambda\quad\forall
t\in[k\lambda,(k+1)\lambda]$

###### Proof.

Combining Theorem 4, Proposition A.2 and Lemma A.5 yields the result. ∎

######  Proposition A.3.

Let $\rho_{n}$ be the $n$-th iteration of our algorithm. Then, there holds

$H_{\pi}(\rho_{k+1})\leq(H_{\pi}(\rho_{k})^{-1}+\dot{c}_{0}\lambda)^{-1}+2C_{1}\lambda^{2}$

The proof proceeds by using a comparison theorem for ODEs to solve the
differential inequality. By using elementary inequalites we reach a simpler
recurrent condition which we iterate over $n$ to reach the following theorem.

######  Theorem 6.

Suppose that $\lambda$ satisfies the stepsize restrictions given in the moment
bounds. In addition, we assume that $\lambda\leq\frac{1}{4\dot{c}_{0}C_{1}}.$
Then, There holds

$H_{\pi}(\rho_{n})\leq(1-\frac{\dot{c}_{0}}{2}\lambda^{\frac{3}{2}})^{n}H_{\pi}(\rho_{0})+(1+\frac{4C_{1}}{\dot{c}_{0}})\sqrt{\lambda}$

Suppose that $\lambda<\epsilon^{2}/4(1+4\frac{C_{1}}{\dot{c}_{0}})^{2}$ Then,
$H_{\pi}(\rho_{n})\leq\epsilon$ after
$n\geq\mathcal{O}\left(\log(\frac{1}{\epsilon})\frac{1}{\epsilon^{3}}\right)$
iterations.

######  Corollary 3.

Let $\bar{\theta}^{\lambda}_{n}$ be the $n-th$ iterate of the algorithm. Then,
there holds

$\|\mathcal{L}(\bar{\theta}^{\lambda}_{n}),\pi)-\pi\|_{TV}\leq\frac{\sqrt{2}}{2}\left(\sqrt{H_{\pi}(\rho_{0})}(1-\frac{\dot{c}_{0}}{2}\lambda^{\frac{3}{2}})^{\frac{n}{2}}+\sqrt{(1+4\frac{c_{1}}{\dot{c}_{0}})}\lambda^{\frac{1}{4}}\right)$

and

$W_{1}(\mathcal{L}(\bar{\theta}^{\lambda}_{n}),\pi)\leq
C_{W}\left(H_{\pi}(\rho_{n})+{H_{\pi}(\rho_{n})}^{\frac{1}{2}}\right)$

###  A.4. Proving convergence without Assumption 3 using a regularized
potential

In the case where $\mathbf{B}$3 is missing, we are going to sample from a
regularized potential which is close to the original target. The new
regularized potential will inherit the important Local Lipschitzness, growth
and dissipativity properties of the original and it will also satisfy
$\mathbf{B}$3 with constant depending on $\lambda$.

We first state some important properties of the new potential which are
related to the properties of the original target.

####  A.4.1. Properties of the regularized potential

######  Lemma A.6.

For $\lambda\leq 1$, the regularized potential
$u_{\operatorname{reg},\lambda}$ satisfies Item (A1) with constants
independent of $\lambda.$ As a result, the tamed scheme inherits the
$a$-dissipitivity condition, and has at most linear growth.

######  Lemma A.7.

Let $p>1$. There exist, $C_{reg,2p}\leq\mathcal{O}(d^{p})$ such that

$\sup_{n}\mathbb{E}|x^{\lambda}_{n}|^{2p}\leq C_{reg,2p}$

Since the regularized potential satisfies potential satisfies Assumption 1
with different constants independent of $\lambda$ and the tamed scheme
inherits the dissipativity condition, the proof follows in the same way as in
the unregularized case.

######  Lemma A.8.

Let $\lambda\leq\frac{ln2}{2R_{2}^{2r+2}}.$ and $R_{2}\leq\mathcal{O}(d)$. The
measure ${\pi_{\operatorname{reg}}}$ satisfies a Poincare inequality with
constant $C_{P,r}^{-1}$ independent of $\lambda$.

######  Proposition A.4.

The regularized measure satisfies LSI with constant
$C_{LSI}^{-1}\leq\mathcal{O}\left((\frac{1}{\lambda})^{\frac{1}{r+1}+\frac{l^{\prime}}{2r-l^{\prime}}}\right)$

To prove this theorem we use the fact that the regularized measure satisfies a
Poincare inequality. By proving that it also satisfies a 2-dissipativity
condition and has a lower bounded Hessian, by using some classic theorems
depending on Lyapunov functions we show the Poincare inequality can be
upgraded to a Log-Sobolev.

######  Theorem 7.

Let $\rho^{\operatorname{reg}}_{n}$ be the distribution of the $n$-th iterate
of the tamed algorithn with the regularized gradient (reg-TULA). There holds

$H_{\pi}(\rho^{\operatorname{reg}}_{n})\leq
H_{{\pi_{\operatorname{reg}}}}(\rho^{\operatorname{reg}}_{n})+\mathcal{O}(\lambda)\leq
e^{-\dot{c}\lambda(n-1)}H_{{\pi_{\operatorname{reg}}}}(\rho_{0})+\frac{\hat{C}}{\dot{c}}\lambda$

where $\dot{c}=C_{LS}$ given in Lemma A.4 and $\hat{C}$ depends polynomially
on the dimension.

By using the same arguments as in the unregularized case one reaches a
differential inequality. This time we make use of the Log-Sobolev inequality
to get a differential inequality for
$H_{{\pi_{\operatorname{reg}}}}(\rho^{reg}_{n}).$ Then, the proof of the
connection between $H_{\pi}(\rho^{\operatorname{reg}}_{n})$ and
$H_{\pi_{\operatorname{reg}}}(\rho^{\operatorname{reg}}_{n})$ is a simple
application of the definition of the relative entropy and the moments of the
algorithm and the invariant measure.

######  Corollary 4.

Let $c_{l,r}:=\frac{r(2+l)}{(r+1)(2r-l)}$ For
$\lambda<\mathcal{O}\left({\epsilon}^{\frac{1}{1-c_{l,r}}}\right),$ there
holds

$H_{{\pi_{\operatorname{reg}}}}(\rho_{n})\leq\epsilon\quad\text{after}\quad
n\geq\mathcal{O}\left(\log(\frac{1}{\epsilon})(\frac{1}{\epsilon})^{\frac{1+c_{l,r}}{1-c_{l,r}}}\right)\quad\text{iterations}$

and

$||\mathcal{L}(\bar{x}^{\lambda}_{n})-\pi||_{TV}\leq\epsilon\quad
n\geq\mathcal{O}\left(\log(\frac{1}{\epsilon}^{2})(\frac{1}{\epsilon^{2}})^{\frac{1+c_{l,r}}{1-c_{l,r}}}\right)\quad\text{iterations}$

In addition, for
$\lambda\leq\mathcal{O}\left({\epsilon}^{\frac{2+c_{r,l}}{1-c_{l,r}}}\right)$
there holds

$W_{2}(\mathcal{L}(\bar{x}^{\lambda}_{n}),\pi)\leq\epsilon\quad\text{after}\quad
n\geq\mathcal{O}\left(\log(\frac{1}{\epsilon})(\frac{1}{\epsilon})^{(2+c_{r,l})\frac{1+c_{l,r}}{1-c_{l,r}}}\right)\quad\text{iterations}.$

##  Appendix B Proof section

###  B.1. Proof of preliminary statements

###### Proof of Lemma A.1.

It easy to see that if $\langle f(x),x\rangle<0$, then $\langle
f_{\lambda}(x),x\rangle\geq\langle f(x),x\rangle$ which implies that

$\langle h_{\lambda}(x),x\rangle\geq A|x|^{a}-B.$

Suppose that $\langle f(x),x\rangle\geq 0$. Then,

$\langle h_{\lambda}(x),x\rangle\geq
A\frac{|x|^{2}}{(1+|x|^{2})^{1-\frac{a}{2}}}\geq
A|x|^{a}\frac{|x|^{2}}{1+|x|^{2}}$

If $|x|>1$ then

$\langle h_{\lambda}(x),x\rangle\geq\frac{A}{2}|x|^{a}$

and if $|x|<1$

$\langle h_{\lambda}(x),x\rangle\geq\frac{A}{2}|x|^{a}-\frac{A}{2}.$

To prove the second part one notices that

$\displaystyle|h_{\lambda}(x)|^{2}$ $\displaystyle\leq
2(1-\frac{1}{1+\sqrt{\lambda}|x|^{2l}})^{2}A^{2}\frac{|x|^{2}}{(1+|x|^{2})^{2-a}}+2(\frac{h(x)}{1+\sqrt{\lambda}|x|^{2l}})^{2}$
$\displaystyle\leq 2A^{2}(1+|x|^{2})^{a-1}+2\frac{L^{2}}{\lambda}$
$\displaystyle\leq 2A^{2}(1+|x|^{2})^{\frac{a}{2}}+2\frac{L^{2}}{\lambda}$
$\displaystyle\leq 4A^{2}+4A^{2}|x|^{a}+2\frac{L^{2}}{\lambda}$

∎

###  B.2. Moment bounds

###### Proof of Lemma A.2.

The proof starts by noticing that conditioned on $\bar{\theta}^{\lambda}_{n}$,
$\theta^{\lambda}_{n+1}$ is a Gaussian, with covariance matrix
$\frac{\lambda}{2}I_{d}$. Thus conditioned on the previous step since the
function $(1+|x|^{2})^{\frac{1}{2}})$ is 1-Lipschitz by t Proposition 5.5.1 in
Bakry et al. [3] there holds so for $\mu^{2}\leq\frac{2}{\lambda},$

$\displaystyle\mathbb{E}[V_{\mu}(\theta^{\lambda}_{n+1})|\bar{\theta}^{\lambda}_{n}]$
$\displaystyle\leq
e^{\mu^{2}\lambda}e^{\mu\mathbb{E}[(1+|\theta^{\lambda}_{n+1}|^{2})^{\frac{1}{2}}|\bar{\theta}^{\lambda}_{n}]}$
$\displaystyle\leq
e^{\mu^{2}\lambda}e^{\mu\left(1+\mathbb{E}[|\theta^{\lambda}_{n+1}|^{2}|\bar{\theta}^{\lambda}_{n}]\right)^{\frac{1}{2}}}$
$\displaystyle=e^{\mu^{2}\lambda}e^{\mu\left(1+|\bar{\theta}^{\lambda}_{n}-\lambda
h_{\lambda}(\bar{\theta}^{\lambda}_{n})|^{2}+2\lambda d\right)^{\frac{1}{2}}}$

where the penultimate step was obtained by Jensen’s inequality. Since

$\displaystyle|x-\lambda h_{\lambda}(x)|^{2}$
$\displaystyle\leq|x|^{2}-2\lambda\langle
x,h_{\lambda}(x)\rangle+\lambda^{2}|h_{\lambda}(x)|^{2}$ (B.1)
$\displaystyle\leq|x|^{2}+\lambda(4\lambda
A^{2}-A|x|^{a})+\lambda(A+2L^{2})+\lambda^{2}4A^{2}$

Since for $\lambda\leq\max\\{1,\frac{1}{2A}\\},$ and $|x|\geq
M:=\left(2(2d+4A^{2}+2L^{2}+A)\right)^{\frac{1}{a}}$ by (B.1) one deduces

$\displaystyle(1+|x-h_{\lambda}(x)|^{2}+2\lambda d)^{\frac{1}{2}}$
$\displaystyle\leq(1+|x|^{2}-\lambda\frac{A}{4}|x|^{a})^{\frac{1}{2}}$ (B.2)
$\displaystyle=(1+|x|^{2})^{\frac{1}{2}}\left(1-\lambda\frac{A}{4}\frac{|x|^{a}}{(1+|x|^{2})}\right)^{\frac{1}{2}}$
$\displaystyle\leq(1+|x|^{2})^{\frac{1}{2}}\left(1-\frac{Aa}{8}\lambda\frac{|x|^{a}}{(1+|x|^{2})}\right)\quad\text{using}\quad(1-t)^{\frac{1}{2}}\leq
1-\frac{1}{2}t$
$\displaystyle=(1+|x|^{2})^{\frac{1}{2}}-\lambda\frac{A}{8}\frac{|x|^{a}}{(1+|x|^{2})^{1-\frac{1}{2}}}$
$\displaystyle=(1+|x|^{2})^{\frac{1}{2}}-\lambda\frac{A}{8}\frac{|x|^{a}}{(1+|x|^{2})^{\frac{1}{2}}}$
$\displaystyle\leq(1+|x|^{2})^{\frac{1}{2}}-\lambda\frac{AM^{a}}{8(1+M^{2})^{\frac{1}{2}}}$

and the last step was deduced using that the function
$g(x)=\frac{x^{a}}{(1+|x|^{2})^{\frac{1}{2}}}$ is increasing for $a\geq 1$ and
$x\geq 0$ Using (B.2) one deduces that if $|\bar{\theta}^{\lambda}_{n}|\geq
M,$

$e^{\mu\left(1+|\bar{\theta}^{\lambda}_{n}-\lambda
h_{\lambda}(\bar{\theta}^{\lambda}_{n})|^{2}+2\lambda
d\right)^{\frac{1}{2}}}\leq
V_{\mu}(\bar{\theta}^{\lambda}_{n})e^{-\mu^{2}\lambda}$

On the other hand, if $|\bar{\theta}^{\lambda}_{n}|\leq M,$ using the
inequality $(1+z+y)^{\frac{1}{2}}\leq{1+z}^{\frac{1}{2}}+\frac{y}{2}$ one
deduces

$\displaystyle\mu\left(1+|\bar{\theta}^{\lambda}_{n}-\lambda
h_{\lambda}(\bar{\theta}^{\lambda}_{n})|^{2}+2\lambda d\right)^{\frac{1}{2}}$
$\displaystyle=\mu\left({1+|\bar{\theta}^{\lambda}_{n}|^{2}+(2|\bar{\theta}^{\lambda}_{n}||h_{\lambda}(\bar{\theta}^{\lambda}_{n})|+\lambda^{2}|h_{\lambda}(\bar{\theta}^{\lambda}_{n})|^{2}+2\lambda
d)}\right)^{\frac{1}{2}}$ (B.3)
$\displaystyle\leq\mu({1+|\bar{\theta}^{\lambda}_{n}|^{2}})^{\frac{1}{2}}+(\frac{\mu}{2}(2|\bar{\theta}^{\lambda}_{n}|\lambda|h_{\lambda}(\bar{\theta}^{\lambda}_{n})|+\lambda^{2}|h_{\lambda}(\bar{\theta}^{\lambda}_{n})|^{2}+2\lambda
d)^{\frac{1}{2}}$
$\displaystyle\leq\mu({1+|\bar{\theta}^{\lambda}_{n}|^{2}})^{\frac{1}{2}}+\lambda
C_{M}$

where $C_{M}\leq C_{0}+M^{2l+1}+M^{4l+2}+2d$ where $C_{0}$ is an absolute
constant independent of the dimension. As a result, if
$|\bar{\theta}^{\lambda}_{n}|\leq M$

$\displaystyle e^{\mu\left(1+|\bar{\theta}^{\lambda}_{n}-\lambda
h_{\lambda}(\bar{\theta}^{\lambda}_{n})|^{2}+2\lambda d\right)^{\frac{1}{2}}}$
$\displaystyle\leq V_{\mu}(\bar{\theta}^{\lambda}_{n})e^{C_{M}\lambda}$

which leads to

$\displaystyle\mathbb{E}[V_{\mu}(\theta^{\lambda}_{n+1})|\bar{\theta}^{\lambda}_{n}]$
$\displaystyle\leq
V_{\mu}(\bar{\theta}^{\lambda}_{n})e^{(C_{M}+\mu^{2})\lambda}$
$\displaystyle=e^{-\mu^{2}\lambda}V_{\mu}(\bar{\theta}^{\lambda}_{n})+\left(e^{(C_{M}+\mu^{2})\lambda}-e^{-\mu^{2}\lambda}\right)V_{\mu}(\bar{\theta}^{\lambda}_{n})$
$\displaystyle\leq
e^{-\mu^{2}\lambda}V_{\mu}(\bar{\theta}^{\lambda}_{n})+e^{(C_{M}+\mu^{2})\lambda}V_{\mu}(\bar{\theta}^{\lambda}_{n})\left(1-e^{-(2\mu^{2}-C_{M})\lambda}\right)$
$\displaystyle\leq
e^{-\mu^{2}\lambda}V_{\mu}(\bar{\theta}^{\lambda}_{n})+\lambda C$

where the last step was derived from the inequality $1-e^{-t}\leq t.$ Putting
all together one deduces,

$\mathbb{E}V_{\mu}(\bar{\theta}^{\lambda}_{n+1})\leq
e^{-\lambda\mu^{2}n}\mathbb{E}V_{\mu}(\theta_{0})+\bar{C}.$

∎

###### Proof of Lemma A.3.

The proof starts by noticing that the function $g(x)=(ln(x))^{2p}$ is concave
for $x\geq e^{2p}.$ As a result, for $n\in\mathbb{N}$

$\displaystyle\mathbb{E}(\mu|\bar{\theta}^{\lambda}_{n}|+{2p})^{2p}$
$\displaystyle\leq\mathbb{E}g(e^{\mu(1+|\bar{\theta}^{\lambda}_{n}|^{2})^{\frac{1}{2}}+2p})$
$\displaystyle\leq
g(\mathbb{E}e^{\mu(1+|\bar{\theta}^{\lambda}_{n}|^{2})^{\frac{1}{2}}+2p})\quad\text{(Jensen)}$
$\displaystyle\leq
2^{2p-1}(ln\mathbb{E}e^{\mu(1+|\bar{\theta}^{\lambda}_{n}|^{2})^{\frac{1}{2}}}+2p^{2p})$
$\displaystyle\leq 2^{2p-1}(lnC_{\mu}^{2p}+2p^{2p})$

∎

###  B.3. Rigorous proofs of integral and derivative exchange

######  Lemma B.1.

Let $\lambda<\frac{1}{4(2AC^{*}+2L+1)^{2}}$. Then, the following hold: Let
$k\in\mathbb{N}$ and $t\in[k\lambda,(k+1)\lambda]$. Then, there exist $C,r,q$
such that

  * •

$\hat{\pi}_{t}\leq Ce^{-r|x|^{2}}\quad\forall x\in\mathbb{R}^{d}$

  * •

$|\nabla\log\hat{\pi}_{t}(x)|\leq C(1+|x|^{q})\quad\forall x\in\mathbb{R}^{d}$

  * •

$||\nabla^{2}\log\hat{\pi}_{t}(x)|\leq
C^{\prime}(1+|x|^{q^{\prime}})\quad\forall x\in\mathbb{R}^{d}.$

###### Proof.

Let

$\phi(x)=x-(t-k\lambda)h_{\lambda}(x)=x-(t-k\lambda)AR(x)-(t-\kappa\lambda)f_{\lambda}(x)$

where $R(x)=\frac{x}{(1+|x|^{2})^{1-\frac{a}{2}}}$,
$f_{\lambda}=\frac{h(x)-AR(x)}{g_{\lambda}}$ and
$g_{\lambda}=\frac{1}{1+\sqrt{\lambda}|x|^{2l}}$. Since for the derivatives of
$R$ there holds

$||J_{R}||\leq C^{*}$

and for $H:=J_{h}$, $||H||\leq g_{\lambda}L\frac{1}{\sqrt{\lambda}},$

$\displaystyle(t-k\lambda)||AJ_{R}+J_{f_{\lambda}}||$
$\displaystyle\leq\lambda(A||J_{R}(x)||+||(H-AJ_{R})g_{\lambda}+\nabla
g_{\lambda}\otimes(h(x)-AR(x))||$ (B.4)
$\displaystyle\leq\lambda(AC^{*}+(||H||+AC^{*})g_{\lambda}+|\nabla
g_{\lambda}(x)||h(x)-AR(x)|)$
$\displaystyle\leq(2AC^{*}+2L+1)\sqrt{\lambda}\leq\frac{1}{2}.$

Thus,

$\frac{1}{2}I_{d}\leq J_{\phi}\leq\frac{3}{2}I_{d}.$

In addition, using the fact that the high derivatives of $h$ and $R$ have at
most polynomial growth one can easily see that $||J^{(2)}_{\phi}||$ and
$||J^{(3)}_{\phi}||$ have at most polynomial growth. From then, on we proceed
with same arguments as in Lemmas A.5-A.7 in Lytras & Sabanis [22]. ∎

######  Lemma B.1.

$\mathbb{E}\left(\frac{\partial\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|\theta_{k\lambda})}{\partial
t}\right)=\frac{\partial\hat{\pi}_{t}}{\partial t}(x).$

###### Proof.

Analysing the left hand side of the equation one deduces the following:

In a neighbourhood of $t$, for fixed $x$,
$\frac{\partial\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)}{\partial t}$ decays
exponentially with $y$ and since $\hat{\pi}_{k\lambda}(y)\leq Ce^{-r|y|^{2}}$
due to Lemma B.1 one can exchange the derivative with the integral in the
following expression

$\frac{\partial}{\partial
t}\int_{\mathbb{R}^{d}}\hat{\pi}_{k\lambda}(y)\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)dy=\int_{\mathbb{R}^{d}}\hat{\pi}_{k\lambda}(y)\frac{\partial\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)}{\partial
t}dy.$

Noticing that

$\frac{\partial\hat{\pi}_{t}}{\partial t}(x)=\frac{\partial}{\partial
t}\int_{\mathbb{R}^{d}}\hat{\pi}_{k\lambda}(y)\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)dy$

and

$\int_{\mathbb{R}^{d}}\hat{\pi}_{k\lambda}(y)\frac{\partial\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)}{\partial
t}dy=\mathbb{E}\left(\frac{\partial\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|\theta_{k\lambda})}{\partial
t}\right)$

yields the result. ∎

######  Lemma B.2.

$\mathbb{E}\left(div_{x}\left(\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|\theta_{k\lambda})h_{\lambda}(\theta_{k\lambda})\right)\right)=div_{x}\left(\hat{\pi}_{t}(x)\mathbb{E}\left(h_{\lambda}(\theta_{k\lambda})\big{|}\theta_{t}=x\right)\right).$

###### Proof.

Since $\hat{\pi}_{t}$ decays exponentially with $y$ and for fixed $t$, in a
neighbourhood of $x$ $\nabla\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)$ is at
most linear in $y$ and $h_{\lambda}$ has at most linear growth, this enables
the interchange of integral and derivative with respect to $x$ in the
following expression

$\int_{\mathbb{R}^{d}}\hat{\pi}_{k\lambda}(y)div_{x}\left(\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)h_{\lambda}(y)\right)dy=div_{x}\int_{\mathbb{R}^{d}}\hat{\pi}_{k\lambda}(y)\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)h_{\lambda}(y)dy$

Since

$\mathbb{E}\left(div\left(\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|\theta_{k\lambda})h_{\lambda}(\theta_{k\lambda})\right)\right)=\int_{\mathbb{R}^{d}}\hat{\pi}_{k\lambda}(y)div_{x}\left(\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)h_{\lambda}(y)\right)dy$

and due to Bayes theorem

$\displaystyle
div_{x}\int_{\mathbb{R}^{d}}\hat{\pi}_{k\lambda}(y)\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)h_{\lambda}(y)dy$
$\displaystyle=div_{x}\int_{\mathbb{R}^{d}}\hat{\pi}_{t}(x)\hat{\pi}_{\theta_{k\lambda}|\theta_{t}}(y|x)h_{\lambda}(y)dy$
$\displaystyle=div_{x}\left(\hat{\pi}_{t}(x)\mathbb{E}\left(h_{\lambda}(\theta_{k\lambda})\big{|}\theta_{t}=x\right)\right)$

and the result immediately follows. ∎

######  Lemma B.3.

$\mathbb{E}\left(\Delta_{x}\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|\theta_{k\lambda})\right)=\Delta\hat{\pi}_{t}(x).$

###### Proof.

Noting that by definition

$\mathbb{E}\left(\Delta_{x}\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|\theta_{k\lambda})\right)=\int_{\mathbb{R}^{d}}\Delta_{x}(\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y))\hat{\pi}_{k\lambda}(y)dy$

and

$\Delta_{x}\hat{\pi}_{t}(x)=\Delta_{x}\int_{\mathbb{R}^{d}}\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)\hat{\pi}_{k\lambda}(y)dy$

it suffices to prove that

$\int_{\mathbb{R}^{d}}\Delta_{x}(\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y))\hat{\pi}_{k\lambda}(y)dy=\Delta_{x}\int_{\mathbb{R}^{d}}\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)\hat{\pi}_{k\lambda}(y)dy.$

By simple computations for the Gaussian distribution one deduces that
$|\nabla_{x}\log\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)|$,
$\Delta_{x}\log\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)$ have at most linear
growth with respect to $y$ in a neighbourhood of $x$ . Writing

$\Delta_{x}\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)=\left(\Delta_{x}\log\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)+|\nabla_{x}\log\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)|^{2}\right)\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)$

one deduces that in a neighbourhood of $x$, the integrand in the first term is
dominated by a function of the form $C(1+|y|^{2})e^{-c|y|^{2}}.$ Applying the
dominated convergence theorem enables the exchange of the integral and the
Laplacian which completes the proof. ∎

######  Corollary 5.

$\frac{\partial\hat{\pi}_{t}}{\partial
t}(x)=div_{x}\left(\hat{\pi}_{t}(x)\mathbb{E}\left(h_{\lambda}(\theta_{k\lambda})\big{|}\theta_{t}=x\right)\right)+\Delta\hat{\pi}_{t}(x)\quad\forall
t\in[k\lambda,(k+1)\lambda]$

###### Proof.

Taking expectations in (A.4) and combining Lemmas B.1,B.2 and B.3 yields the
result. ∎

######  Lemma B.4.

There exist $C,k,r^{\prime}>0$ indepent of $x$, uniform in a small
neighbourghood of $t$ such that

$div_{x}\left(\hat{\pi}_{t}(x)\mathbb{E}\left(h_{\lambda}(\theta_{k\lambda})\big{|}\theta_{t}=x\right)\right)+\Delta\hat{\pi}_{t}\leq
C(1+|x|^{k})e^{-r^{\prime}|x|^{2}}$

###### Proof.

Writing, due to Bayes’ theorem,

$\displaystyle
div_{x}\left(\hat{\pi}_{t}(x)\mathbb{E}\left(h_{\lambda}(\theta_{k\lambda})\big{|}\theta_{t}=x\right)\right)=\int_{\mathbb{R}^{d}}\hat{\pi}_{k\lambda}(y)div_{x}\left(\hat{\pi}_{t|\mathcal{F}_{k\lambda}}(x|y)h_{\lambda}(y)\right)dy$
$\displaystyle\leq Ce^{-c|x|^{2}+|x|}\int_{\mathbb{R}^{d}}e^{-r|y|^{2}}|y|dy$

for some $C,c,r>0$ where the last step is a result of the Gaussian expression
of the conditional density, the linear growth of $h_{\lambda}$ and the
exponential decay of $\hat{\pi}_{k\lambda}$ given in Lemma B.1.

For the second term, writing

$\Delta\hat{\pi}_{t}=\hat{\pi}_{t}\left(|\nabla\log\hat{\pi}_{t}|^{2}+\Delta\log\hat{\pi}_{t}\right)$

the result follows due to Lemma B.1. ∎

######  Corollary 6.

$\frac{d}{dt}H_{\pi}(\hat{\pi}_{t})=\int_{\mathbb{R}^{d}}\frac{\partial\hat{\pi}_{t}(x)}{\partial
t}(1+\log\hat{\pi}_{t}(x)-\log\pi)dx$

###### Proof.

Noting that $\log\hat{\pi}_{t},\log\pi$ have polynomial growth, due to Lemma
B.4,
$\frac{\partial\hat{\pi}_{t}(x)}{\partial t}(1+\log\hat{\pi}_{t}(x)-\log\pi)$
can be dominated by an $L^{1}$ integrable function over small neighbourhood of
$t$, thus using the dominated convergence theorem one deduces the exchange of
derivative and integration i.e

$\displaystyle\int_{\mathbb{R}^{d}}\frac{\partial\hat{\pi}_{t}(x)}{\partial
t}(1+\log\hat{\pi}_{t}(x)-\log\pi(x))dx$
$\displaystyle=\int_{\mathbb{R}^{d}}\frac{\partial}{\partial
t}\left(\hat{\pi}_{t}(x)\log\frac{\hat{\pi}_{t}(x)}{\pi(x)}\right)dx$
$\displaystyle=\frac{d}{dt}\int_{\mathbb{R}^{d}}\hat{\pi}_{t}(x)\log\frac{\hat{\pi}_{t}(x)}{\pi(x)}dx$
$\displaystyle=\frac{d}{dt}H_{\pi}(\hat{\pi}_{t}).$

∎

###### Proof of Corollary A.1.

Recall that from Lemma 6, there holds

$\frac{d}{dt}H_{\pi}(\hat{\pi}_{t})=\int_{\mathbb{R}^{d}}\frac{\partial\hat{\pi}_{t}(x)}{\partial
t}(1+\log\hat{\pi}_{t}(x)-\log\pi)dx.$ (B.5)

Let

$F_{t}(x)=\hat{\pi}_{t}(x)E\left(h_{\lambda}(\theta_{k\lambda})\big{|}\theta_{t}=x\right)+\nabla\hat{\pi}_{t}(x)$

and

$g_{t}(x)=1+\log\hat{\pi}_{t}-\log\pi.$

Recall from Corollary 5 that

$\frac{\partial\hat{\pi}_{t}}{dt}(x)=div_{x}(F_{t})(x)$

Since $\nabla\hat{\pi}_{t}=\hat{\pi}_{t}\nabla\log\hat{\pi}_{t}$ using the
Lemma B.1,B.4 one deduces that there exists constants $C$, $q$ ,$r$>0
independent of $x$, uniform in a small neighbourhood of $t$, such that

$\max\\{|F_{t}(x)g_{t}(x)|,|div(F_{t})(x)g_{t}(x)|,|\langle F_{t}(x)\nabla
g_{t}(x)\rangle|\\}\leq C(1+|x|^{q})e^{-r|x|^{2}}.$ (B.6)

We drop the dependence of the constants on $t$ since we want to integrate with
respect to $x.$ Let $R>0$ and $v(x)$ the normal unit vector on $\partial
B(0,R)$. Due to (B.6)

$\int_{\partial B(0,R)}\langle g_{t}(x)F_{t}(x),v(x)\rangle dx\leq
R^{d}C(1+|R|^{q})e^{-r|R|^{2}}.$ (B.7)

Since $div(F_{t})g_{t}$, $\langle F_{t},\nabla_{x}g_{t}\rangle$ are integrable
(in view of (B.6)) applying the divergence theorem on $B(0,R)$ there holds

$\int_{B(0,R)}div_{x}(F_{t})(x)g_{t}(x)dx=\int_{\partial B(0,R)}\langle
g_{t}(x)F_{t}(x),v(x)\rangle dx-\int_{B(0,R)}\langle
F_{t}(x)\nabla_{x}g_{t}(x)\rangle dx.$ (B.8)

As a result,

$\displaystyle\int_{\mathbb{R}^{d}}div(F_{t})(x)g_{t}(x)dx$
$\displaystyle=\lim_{R\rightarrow\infty}\int_{B(0,R)}div_{x}(F_{t})(x)g_{t}(x)dx$
$\displaystyle=\lim_{R\rightarrow\infty}\left(\int_{\partial B(0,R)}\langle
g_{t}(x)F_{t}(x),v(x)\rangle dx-\int_{B(0,R)}\langle
F_{t}(x)\nabla_{x}g_{t}(x)\rangle\right)dx$
$\displaystyle=0-\lim_{R\rightarrow\infty}\int_{B(0,R)}\langle
F_{t}(x)\nabla_{x}g_{t}(x)\rangle dx=-\int_{\mathbb{R}^{d}}\langle
F_{t}(x)\nabla_{x}g_{t}(x)\rangle dx.$

∎

###### Proof of theorem 4.

Using Proposition A.1, for all $t\in[k\lambda,(k+1)\lambda],$

$\displaystyle\frac{d}{dt}H_{\pi}(\hat{\pi}_{t})$
$\displaystyle=-\int_{\mathbb{R}^{d}}\langle\hat{\pi}_{t}(x)E\left(h_{\lambda}(\theta_{k\lambda})\big{|}\theta_{t}=x\right)+\nabla\hat{\pi}_{t}(x),\nabla\log\hat{\pi}_{t}(x)-\nabla\log\pi(x)\rangle
dx$ $\displaystyle=-\int_{\mathbb{R}^{d}}\hat{\pi}_{t}(x)\langle
E\left(h_{\lambda}(\theta_{k\lambda})\big{|}\theta_{t}=x\right)+\nabla\log\hat{\pi}_{t}(x),\nabla\log\hat{\pi}_{t}(x)-\nabla\log\pi(x)\rangle
dx$ $\displaystyle=-\int_{\mathbb{R}^{d}}\hat{\pi}_{t}(x)\langle
E\left(h_{\lambda}(\theta_{k\lambda})\big{|}\theta_{t}=x\right)+\nabla\log\pi,\nabla\log\hat{\pi}_{t}(x)-\nabla\log\pi(x)\rangle
dx$
$\displaystyle-\int_{\mathbb{R}^{d}}\hat{\pi}_{t}|\nabla\log\hat{\pi}_{t}(x)-\nabla\log\pi(x)|^{2}dx$
$\displaystyle=-I_{\pi}(\hat{\pi}_{t})-\int_{\mathbb{R}^{d}}\hat{\pi}_{t}(x)\langle
E\left(h_{\lambda}(\theta_{k\lambda})-h(x)\big{|}\theta_{t}=x\right),\nabla\log\hat{\pi}_{t}(x)-\nabla\log\pi(x)\rangle
dx$
$\displaystyle=-I_{\pi}(\hat{\pi}_{t})-\int_{\mathbb{R}^{d}}\hat{\pi}_{t}(x)\langle
E\left(h_{\lambda}(\theta_{k\lambda})-h(\theta_{t}))\big{|}\theta_{t}=x\right),\nabla\log\hat{\pi}_{t}(x)-\nabla\log\pi(x)\rangle
dx$ $\displaystyle\leq-
I_{\pi}(\hat{\pi}_{t})+\int_{\mathbb{R}^{d}}\hat{\pi}_{t}(x)\left|E\left(h_{\lambda}(\theta_{k\lambda})-h(\theta_{t}))\big{|}\theta_{t}=x\right)\right|^{2}dx+\frac{1}{4}I_{\pi}(\hat{\pi}_{t})$
$\displaystyle=-\frac{3}{4}I_{\pi}(\hat{\pi}_{t})+\int_{\mathbb{R}^{d}}\hat{\pi}_{t}(x)\left|\int_{\mathbb{R}^{d}}\hat{\pi}_{\theta_{k\lambda}|\theta_{t}}(y|x)(h_{\lambda}(y)-h(x))dy\right|^{2}dx$
$\displaystyle\leq-\frac{3}{4}I_{\pi}(\hat{\pi}_{t})+\int_{\mathbb{R}^{d}}\hat{\pi}_{t}(x)\int_{\mathbb{R}^{d}}\hat{\pi}_{\theta_{k\lambda}|\theta_{t}}(y|x)\left|h_{\lambda}(y)-h(x)\right|^{2}dydx$
$\displaystyle=-\frac{3}{4}I_{\pi}(\hat{\pi}_{t})+\mathbb{E}|h_{\lambda}(\theta_{k\lambda})-h(\theta_{t})|^{2}$

where the first inequality was obtained using Young inequality and the second
using Jensen’s. ∎

###### Proof of Lemma A.4.

Let $t\in[k\lambda,(k+1)\lambda].$ First of all, one needs to bound the one
step error $\mathbb{E}|\theta_{t}-\theta_{k\lambda}|^{2p}$ for different
values of $p\in\mathbb{N}$.

$\displaystyle\mathbb{E}|\theta_{t}-\theta_{k\lambda}|^{2p}$
$\displaystyle\leq
2^{2p}\lambda^{2p}\mathbb{E}|h_{\lambda}(\theta_{k\lambda})|^{2p}+2^{p}\lambda^{p}\mathbb{E}|Z|^{2p}$
$\displaystyle\leq
2^{p}\lambda^{p}\mathbb{E}\left(4A^{2}|\theta_{k\lambda}|^{a}+4(L^{2}+A^{2})\right)^{p}+2^{p}\lambda^{p}\mathbb{E}|Z|^{2p}$
$\displaystyle\leq\lambda^{p}C_{1,p}$

where $C_{1,p}=\mathcal{O}\left(d^{p(2l+1)}\right),$ which is derived by the
moment bounds of the Gaussian, the fact that
$\mathcal{L}(\theta_{k\lambda})=\mathcal{L}(\bar{\theta}^{\lambda}_{k})$ and
the moment bounds of the algorithm. ∎

###### Proof of Lemma A.5.

For every $x\in\mathbb{R}^{d}$,

$|h_{\lambda}(x)-h(x)|=\left|(h(x)-A\frac{x}{(1+|x|^{2})^{1-\frac{a}{2}}})(1-\frac{1}{1+\sqrt{\lambda}|x|^{2l}})\right|^{2}\leq\lambda\left|(|h(x)|+|x|)|x|^{2l}\right|^{2}$

so

$\mathbb{E}\left|h(\theta_{k\lambda})-h_{\lambda}(\theta_{k\lambda})\right|^{2}\leq\lambda\mathbb{E}\left|\left(|h(\bar{\theta}_{k})|+|\bar{\theta}_{k}|\right)|\bar{\theta}_{k}|\right|^{2}\leq
16\left(L^{2}(\bar{C}_{4l}+1)+\bar{C}_{2l+1}\right)\lambda.$ (B.9)

where the constants are given in Lemma A.3. In addition, using Item (A1) one
deduces that

$\displaystyle\mathbb{E}|h(\theta_{k\lambda})-h(\theta_{t})|^{2}$
$\displaystyle\leq\mathbb{E}(1+|\theta_{k\lambda}+|\theta_{t}|)^{2l^{\prime}}|\theta_{t}-\theta_{k\lambda}|^{2}$
(B.10)
$\displaystyle\leq\sqrt{3^{4l^{\prime}}(1+\mathbb{E}|\theta_{k\lambda}^{4l^{\prime}}+\mathbb{E}|\theta_{k\lambda}-\theta_{t}|^{4l^{\prime}})}\sqrt{\mathbb{E}|\theta_{k\lambda}-\theta_{t}|^{4}}$
$\displaystyle\leq\sqrt{3^{4l^{\prime}}}\sqrt{1+\lambda^{2l^{\prime}}C_{1,2l^{\prime}}+\sup_{n}\mathbb{E}|\bar{\theta}^{\lambda}_{n}|^{4l^{\prime}}}\lambda\sqrt{C_{2,p}}\quad(\text{Lemma
\ref{lemma-onestep} }$
$\displaystyle\leq\sqrt{1+\lambda^{2l^{\prime}}C_{1,2l^{\prime}}+C_{2l^{\prime}}}\lambda\sqrt{C_{2,p}}$

where the last step was derived by Lemma A.3. Combining (B.9) and (B.10),
yields the result. ∎

###### Proof of Theorem 2.

$\displaystyle\frac{d}{dt}H_{\pi}(\hat{\pi}_{t})$
$\displaystyle\leq-\frac{3}{4}I_{\pi}(\hat{\pi}_{t})+\beta\mathbb{E}|h_{\lambda}(\theta_{k\lambda}-h(\theta_{t})|^{2}$
$\displaystyle\leq-\dot{c}H_{\pi}(\hat{\pi}_{t})+2\beta\mathbb{E}|h_{\lambda}(\theta_{k\lambda})-h(\theta_{k\lambda})|^{2}+2\beta\mathbb{E}|h(\theta_{k\lambda})-h(\theta_{t})|^{2}$
$\displaystyle\leq-\dot{c}H_{\pi}(\hat{\pi}_{t})+\beta\hat{C}\lambda$

where $\hat{C}=2C_{onestep}+2C_{tam}$ where the first term has been bounded
using the Log-Sobolev inequality and the rest of the terms using the one-step
error in Lemma A.4 and the taming error in Lemma A.5. Splitting the terms one
obtains

$\displaystyle\left(\frac{d}{dt}H_{\pi}(\hat{\pi}_{t})+\dot{c}H_{\pi}(\hat{\pi}_{t})\right)e^{\dot{c}t}\leq
e^{\dot{c}t}\beta\hat{C}\lambda$

Integrating over $[k\lambda,t]$ yields

$\displaystyle
e^{\dot{c}t}H_{\pi}(\hat{\pi}_{t})-e^{\dot{c}k\lambda}H_{\pi}(\hat{\pi}_{k\lambda})\leq\frac{\beta\hat{C}}{\dot{c}}\lambda(e^{\dot{c}t}-e^{\dot{c}k\lambda})$

which implies

$H_{\pi}(\hat{\pi}_{t})\leq
e^{\dot{c}(k\lambda-t)}H_{\pi}(\hat{\pi}_{k\lambda})+\frac{\beta\hat{C}}{\dot{c}}\lambda(1-e^{\dot{c}(k\lambda-t)}).$
(B.11)

Setting $t=n\lambda$ and $k=(n-1)$ leads to

$H_{\pi}(\hat{\pi}_{n\lambda})\leq
e^{-\dot{c}\lambda}H_{\pi}(\hat{\pi}_{(n-1)\lambda})+\frac{\beta\hat{C}}{\dot{c}}\lambda(1-e^{-\dot{c}\lambda})$

so by iterating over $n$,

$H_{\pi}(\hat{\pi}_{n\lambda})\leq
e^{-\dot{c}\lambda(n-1)}H_{\pi}(\pi_{0})+\frac{\beta\hat{C}}{\dot{c}}\lambda$

which completes the proof. ∎

###### Proof of Lemma A.2.

Let $f=\pi/\hat{\pi}_{t}$ Then,

$\displaystyle\frac{1}{2}\int(\sqrt{\hat{\pi}_{t}}-\sqrt{\pi})^{2}dx$
$\displaystyle\leq\left(1-\mathbb{E}_{\nu}(\sqrt{f})\right)\left(1+\mathbb{E}_{\nu}(\sqrt{f})\right)$
(B.12) $\displaystyle\leq 1-\left(\mathbb{E}_{\nu}(\sqrt{f})\right)^{2}$
$\displaystyle=\mathbb{E}_{\nu}((\sqrt{f})^{2})-\left(\mathbb{E}_{\pi}(\sqrt{f})\right)^{2}$
$\displaystyle=Var_{\pi}(\sqrt{f})$
$\displaystyle\leq\frac{1}{C_{P}}\mathbb{E}_{\pi}|\nabla\sqrt{f}|^{2}$
$\displaystyle\leq\frac{1}{4C_{P}}\mathbb{E}_{\pi}|\nabla f|^{2}/f$
$\displaystyle=\frac{1}{4C_{P}}\int\left(\pi f|\frac{\nabla
f}{f}|^{2}\right)dx$
$\displaystyle=\frac{1}{4C_{p}}\int\left(\hat{\pi}_{t}|-\nabla\log\frac{\hat{\pi}_{t}}{\pi}|^{2}\right)dx$
$\displaystyle=\frac{1}{C_{p}}I_{\pi}(\hat{\pi}_{t}).$

In addition, since both $\hat{\pi}_{t}$ and $\pi$ have finite polynomial
moments, there holds

$\displaystyle W_{2}^{2}(\mathcal{L}(\theta_{t}),\pi)$
$\displaystyle=2\int|x|^{2}|\pi(x)-\hat{\pi}_{t}(x)|dx$ (B.13)
$\displaystyle\leq
2\left(\int|x|^{4}(\sqrt{\pi}+\sqrt{\hat{\pi}_{t}})^{2}dx\right)^{\frac{1}{2}}\left(\int(\sqrt{\hat{\pi}_{t}}-\sqrt{\pi})^{2}dx\right)^{\frac{1}{2}}$
$\displaystyle\leq
4(\sqrt{\mathbb{E}_{\hat{\pi}_{t}}|x|^{4}}+\sqrt{\mathbb{E}_{\pi}|x|^{4}})\sqrt{I_{\pi}(\hat{\pi}_{t})}\quad\text{derived
from \eqref{eq-1}}$ $\displaystyle
32(\sqrt{\sup\mathbb{E}|\bar{\theta}^{\lambda}_{n}|^{4}}+\sqrt{\mathbb{E}|\theta_{t}-\theta_{k\lambda}|^{4}}+\sqrt{\mathbb{E}_{\pi}|x|^{4}})\sqrt{I_{\pi}(\hat{\pi}_{t})}$
$\displaystyle\leq C\sqrt{I_{\pi}(\hat{\pi}_{t})}$

where the last step was derived from Lemmas A.4 and A.3 We are going to use
our assumption to connect the relative entropy to $W_{2}$ distance. Since
Assumption 3 holds and $\pi$ has finite second moments, the HWI can be
applied, so

$\displaystyle H_{\pi}(\hat{\pi}_{t})$
$\displaystyle\leq\sqrt{I_{\pi}(\hat{\pi}_{t})}W_{2}(\mathcal{L}(\theta_{t}),\pi)+\frac{\kappa}{2}W_{2}^{2}(\mathcal{L}(\bar{\theta}^{\lambda}_{n}),\pi)$
(B.14)
$\displaystyle\leq\sqrt{2}(\sqrt{\mathbb{E}_{\pi}}|x|^{2}+\sqrt{\mathbb{E}|\theta_{k\lambda}-\theta_{t}|^{2}}+\sqrt{\mathbb{E}|\bar{\theta}^{\lambda}_{n}|^{2}})\sqrt{I_{\pi}(\hat{\pi}_{t})}+\frac{\kappa}{2}W_{2}^{2}(\mathcal{L}(\bar{\theta}^{\lambda}_{n}),\pi).$

Combining (B.13) with (B.14) yields the result. ∎

###### Proof of Proposition A.3.

Let $\phi(t,x)=-\dot{c}_{0}x^{2}+k_{2}$ where $k_{2}:=2C_{1}\lambda.$ Then,
from Corollary 2 there holds

$\frac{dH_{\pi}(\hat{\pi}_{t})}{dt}<\phi(H_{\pi}(\hat{\pi}_{t}),t).$

Let $\delta<H_{\pi}^{-1}(\rho_{k})/2$ Setting
$g_{\delta}(t)=\left(H_{\pi}(\rho_{k})^{-1}-\delta+\dot{c}_{0}(t-k\lambda)\right)^{-1}+k_{2}(t-k\lambda)$
one deduces

$g_{\delta}^{\prime}(t)=-\dot{c}_{0}\left(H_{\pi}(\rho_{k})^{-1}-\delta+\dot{c}_{0}(t-k\lambda)\right)^{-2}+k_{2}$
(B.15)

Since
$(H_{\pi}^{-1}(\rho_{k})-\delta)^{2}\leq\left(H_{\pi}(\rho_{k})^{-1}-\delta+\dot{c}_{0}(t-k\lambda)\right)^{2}$
one obtains

$g_{\delta}^{\prime}(t)-\phi(g_{\delta}(t),t)\geq
0>\frac{dH_{\pi}(\hat{\pi}_{t})}{dt}-\phi(H_{\pi}(\hat{\pi}_{t}),t)\quad\forall
t\in[k\lambda,(k+1)\lambda]$ (B.16)

Using (B.16) and the fact that
$g_{\delta}(k\lambda)=\left(H_{\pi}(\rho_{k})^{-1}-\delta\right)^{-1}>H_{\pi}(\rho_{k})=H_{\pi}(\hat{\pi}_{k\lambda})$
By comparison theorem for differential inequalities, see McNabb [24], there
holds

$(H_{\pi}(\rho_{k})^{-1}+\dot{c}_{0}\lambda)^{-1}+2C_{1}\lambda^{2}=\lim_{\delta\rightarrow
0^{+}}g_{\delta}((k+1)\lambda)\geq H_{\pi}(\rho_{k+1})$ (B.17)

∎

###### Proof of theorem 6.

We begin the proof by noticing that

$H_{\pi}(\rho_{n})\leq\frac{1}{\dot{c}_{0}\lambda}\quad\forall n.$ (B.18)

This will be done by induction. Since for $\lambda<\lambda_{max},$

$H_{\pi}(\rho_{0})\leq\frac{1}{\dot{c}_{0}\lambda}$

it holds for $n=0.$ Suppose that

$H_{\pi}(\rho_{k})\leq\frac{1}{\dot{c}_{0}\lambda}$ (B.19)

Then

$\displaystyle
H_{\pi}(\rho_{k+1})\leq\frac{1}{\dot{c}_{0}\lambda}\left(\dot{c}_{0}\lambda
H_{\pi}(\rho_{k})(1+\dot{c}_{0}\lambda
H_{\pi}(\rho_{k}))^{-1}\right)+2C_{1}\lambda^{2}$

Since the function $\phi(x)=\frac{x}{1+x}$ is increasing, then
$\phi(\dot{c}_{0}\lambda H_{\pi}(\rho_{k}))<\phi(1)$ so

$H_{\pi}(\rho_{k+1})\leq\frac{1}{2\dot{c}_{0}\lambda}+2C_{1}\lambda^{2}\leq\frac{1}{\dot{c}_{0}\lambda}.$

which proves (B.18) by induction.
We proceed with two cases:
Case 1:
$H_{\pi}(\rho_{k_{0}})\geq\frac{4c_{1}}{\dot{c}_{0}}\sqrt{\lambda}\quad\forall
k_{0}\leq k$:
Making use of (B.18) and the inequality $\frac{1}{x+1}\leq(1-\frac{x}{2})$ for
$x\leq 1$, one obtains

$H_{\pi}(\rho_{k+1})\leq H_{\pi}(\rho_{k})(1-\frac{\dot{c}_{0}}{2}\lambda
H_{\pi}(\rho_{k}))+2C_{1}\lambda^{2}\leq
H_{\pi}(\rho_{k})(1-2C_{1}\lambda^{\frac{3}{2}})+2C_{1}\lambda^{2}$

Summing over $k$ one deduces

$H_{\pi}(\rho_{k})\leq
H_{\pi}(\rho_{0})(1-2C_{1})\lambda^{\frac{3}{2}})^{k}+\sqrt{\lambda}.$ (B.20)

Case 2: There exist $k_{0}\leq k$ such that
$H_{\pi}(k_{0})\leq\sqrt{\frac{4c_{1}}{\dot{c}_{0}}}\sqrt{\lambda}.$ Suppose
that $\frac{4c_{1}}{\dot{c}_{0}}\sqrt{\lambda}\geq
H_{\pi}(\rho_{k_{0}})\geq\frac{1}{2}\frac{4c_{1}}{\dot{c}_{0}}\sqrt{\lambda}.$
Then,

$H_{\pi}(\rho_{k_{0}+1})\leq
H_{\pi}(\rho_{k_{0}})-\frac{\dot{c}_{0}}{2}\lambda
H_{\pi}^{2}(\rho_{k_{0}})+C_{1}\lambda^{2}\leq H_{\pi}(\rho_{k_{0}})$

On the other hand, if
$H_{\pi}(k_{0})\leq\frac{1}{2}\frac{4c_{1}}{\dot{c}_{0}}\sqrt{\lambda}.$ it is
easy to see that
$H_{\pi}(\rho_{k+1})\leq\frac{4c_{1}}{\dot{c}_{0}}\sqrt{\lambda}.$

This implies that

$\exists
k_{0}<k:H_{\pi}(\rho_{k_{0}})\leq\frac{4c_{1}}{\dot{c}_{0}}\sqrt{\lambda}\implies
H_{\pi}(\rho_{k})\leq\frac{4c_{1}}{\dot{c}_{0}}\sqrt{\lambda}$

Combining case 1 and case 2 together yields the result. ∎

###### Proof of Corollary 3.

For the bound in total variation, using Theorem 6 and Pinsker’s inequality
gives the result.
For the bound in $W_{1}$ distance, using Lemma A.2 and Corollary 2.3 in [6],
one deduces that

$C_{W}:=\frac{2}{\mu}(\frac{3}{2}+\log\mathbb{E}e^{\mu|\bar{\theta}^{\lambda}_{n}|})<\infty$

and

$W_{1}(\mathcal{L}(\bar{\theta}^{\lambda}_{n}),\pi)\leq
C_{W}\left(H_{\pi}(\rho_{n})+{H_{\pi}(\rho_{n})}^{\frac{1}{2}}\right).$

Applying the bound on $C_{W}$ in Lemma A.2 and Theorem 6 yields the result. ∎

##  Appendix C Proofs for the convergence of regularized scheme

###  C.1. Properties for the regularized potential

###### Proof of Lemma A.6.

It is easy to see that the function $G(x)=(r+1)|x|^{2r}$ is Locally Lipschitz
since

$J_{G}=(r+1)|x|^{2r}I_{d}+(r+1)rx^{t}x|x|^{2r-2}$

then,

$||J_{G}(x)||\leq(r+1)^{2}|x|^{2r}.$

Using the mean value theorem

$|\lambda G(x)-\lambda
G(y)|\leq\lambda\int_{0}^{1}||J_{G}(tx+(1-t)y|||x-y|dt\leq\lambda(r+1)^{2}(1+|x|+|y|)^{2r}|x-y|.$

As a result,

$|\nabla u_{\operatorname{reg},\lambda}(x)-\nabla
u_{\operatorname{reg},\lambda}(y)|\leq((r+1)^{2}+L)(1+|x|+|y|)^{2r}|x-y|\quad\forall
x,y\in\mathbb{R}^{d}.$

It is also easy to see that the higher derivatives of
$u_{\operatorname{reg},\lambda}$ have polynomial growth less than $2r+1$. With
respect to the dissipativity it is easy to see that

$\langle\nabla u_{\operatorname{reg},\lambda}(x),x\rangle\geq\langle\nabla
u(x),x\rangle,$

so Item (A2) is satisified with the same $A$ and $b$. For the tamed scheme, by
it is definition it easy to see that

$|\nabla u_{r,\lambda}|\leq
A+\sqrt{\lambda}+A|x|^{\frac{a}{2}}+\frac{(L+1)}{\sqrt{\lambda}}.$

∎

###### Proof of Lemma A.8.

The proof starts by noticing that there exists $R_{1}$ depending on $A,B$ of
Item (A2) such that

$\langle\nabla
u_{\operatorname{reg},\lambda}(x),x\rangle\geq\frac{A}{2}|x|\quad\forall|x|\geq
R_{1}.$

In addition, picking a smooth Lyapunov function $W\geq 1$ such

$W=e^{\frac{A}{4}|x|}\quad\forall|x|\geq R_{1},$

one deduces that for generator of the Langevin SDE with drift coeffient the
regularized gradient,

$\displaystyle LW(x)$ $\displaystyle=\Delta W(x)-\langle\nabla W(x),\nabla
u_{\operatorname{reg},\lambda}(x)\leq\frac{A}{4}W\left(\frac{d-1}{|x|}+\frac{A}{4}-\langle\nabla
u_{\operatorname{reg},\lambda}(x),x\rangle\\}\right)$
$\displaystyle\leq\frac{A}{4}W(\frac{d-1}{|x|}+\frac{A}{4}-\frac{A}{4}|x|)$

So there exists $R_{0}\leq\mathcal{O}({d})$ such that

$LW\leq-\theta W\quad\forall|x|\geq R_{2}:=\max\\{R_{0},R_{1}\\}.$

Setting $B=B(0,R_{2})$ and $B_{2}=B(0,R_{2}+2)$. Let a smooth function
$\chi=\psi(|x|)$ (see Lemma B.13 of Li & Erdogdu [20] for the construction)
such that $\chi=0$ on $B$ nad $\chi=1$ on $B_{2}^{c}$ and $|\nabla\chi|\leq
1.$

$\displaystyle\int\frac{-LW}{W}f^{2}d{\pi_{\operatorname{reg}}}$
$\displaystyle=\int\Gamma\left(\frac{f^{2}}{W},W\right)d{\pi_{\operatorname{reg}}}$
(C.1)
$\displaystyle=2\int\frac{f}{W}\Gamma(f,W)d{\pi_{\operatorname{reg}}}-\int\frac{f^{2}}{W^{2}}\Gamma(W,W)d{\pi_{\operatorname{reg}}}$
$\displaystyle=-\int\left|\frac{f}{W}\nabla W-\nabla
f\right|^{2}d{\pi_{\operatorname{reg}}}+\int\Gamma(f,f)d{\pi_{\operatorname{reg}}}$
$\displaystyle\leq\int\Gamma(f,f)d{\pi_{\operatorname{reg}}}$

Writing for a smooth $f$,

$\displaystyle\int f^{2}d{\pi_{\operatorname{reg}}}$
$\displaystyle=\int(f(1-\chi)+f\chi)^{2}d{\pi_{\operatorname{reg}}}$
$\displaystyle\leq 2\int f^{2}(1-\chi)^{2}d{\pi_{\operatorname{reg}}}+2\int
f^{2}\chi^{2}d{\pi_{\operatorname{reg}}}$
$\displaystyle\leq\frac{2}{\theta}\int\frac{-LW}{W}f^{2}(1-\chi)^{2}d{\pi_{\operatorname{reg}}}+2\int_{B_{2}}f^{2}d{\pi_{\operatorname{reg}}}$
$\displaystyle\leq\frac{2}{\theta}\int\Gamma(f(1-\chi),f(1-\chi))d{\pi_{\operatorname{reg}}}+2\int_{B_{2}}f^{2}d{\pi_{\operatorname{reg}}}$

. Since $\Gamma(fg,fg)\leq 2\left(f^{2}\Gamma(g,g)+g^{2}\Gamma(f,f)\right)$,
we get:

$\displaystyle\int f^{2}d{\pi_{\operatorname{reg}}}$
$\displaystyle\leq\frac{4}{\theta}\int\Gamma(f,f)d{\pi_{\operatorname{reg}}}+\frac{4}{\theta}\int
f^{2}\Gamma(\chi,\chi)d{\pi_{\operatorname{reg}}}+2\int_{B_{2}}f^{2}d{\pi_{\operatorname{reg}}}$
(C.2)
$\displaystyle\leq\frac{4}{\theta}\int\Gamma(f,f)d{\pi_{\operatorname{reg}}}+\left(\frac{4}{\theta}+2\right)\int_{B_{2}}f^{2}d{\pi_{\operatorname{reg}}}$

Applying the previous inequality for
$\tilde{f}=f-\int_{B_{2}}fd{\pi_{\operatorname{reg}}}$ and using the fact that

$Var_{{\pi_{\operatorname{reg}}}}(f)\leq\int\tilde{f}^{2}d{\pi_{\operatorname{reg}}}$

yields

$\displaystyle Var_{{\pi_{\operatorname{reg}}}}(f)$
$\displaystyle\leq\int\tilde{f}^{2}d{\pi_{\operatorname{reg}}}\leq\frac{4}{\theta}\int\Gamma(\tilde{f},\tilde{f})d{\pi_{\operatorname{reg}}}+\left(\frac{4}{\theta}+2\right)\int_{B_{2}}\tilde{f}^{2}d{\pi_{\operatorname{reg}}}$
(C.3)
$\displaystyle=\frac{4}{\theta}\int\Gamma(f,f)d{\pi_{\operatorname{reg}}}+\left(\frac{4}{\theta}+2\right)\int_{B_{2}}\tilde{f}^{2}d{\pi_{\operatorname{reg}}}$

When restricted to the ball $B_{2}$ $u_{\operatorname{reg},\lambda}$ is a
bounded petrubation $u$ on the same ball since

$|u(x)-u_{\operatorname{reg},\lambda}(x)|\leq\lambda(R_{2}+2)^{2r+2}\quad\forall
x\in B_{2}.$

Using Hooley-Strook pertubation theorem one deduces that
${\pi_{\operatorname{reg}}}$ satisfies Poincare inequality when resticted to
$B_{2}$ with constant $k_{B_{2}}^{-1}\leq
e^{2\lambda(R_{2}+2)^{2r+2}}C_{P}^{-1}\leq 3C_{P}{-1}.$ Thus,

$\int_{B_{2}}\tilde{f}^{2}d{\pi_{\operatorname{reg}}}\leq
k_{B_{2}}\int\Gamma(f,f)d{\pi_{\operatorname{reg}}}.$

Applying this to (C.3) completes the proof. ∎

######  Lemma C.1.

The function $u$ given by $u_{r,\lambda}(x):=u(x)+\lambda|x|^{2r+2}$ satisfies

$\langle\nabla u_{r,\lambda}(x)-\nabla
u_{r,\lambda}(y),x-y\rangle\geq\left(c_{1}(|x|^{2r}+|y|^{2r})-c_{2}(|x|^{l^{\prime}}+|y|^{l^{\prime}})-c_{3}\right)|x-y|^{2}\quad\forall
x,y\in\mathbb{R}^{d}.$

where $c_{1}:=\lambda(r+1)$, $c_{2}=c_{3}=L$.

The proof follows by using Item (A1) and the fact that the regularized term
$2r$ dominates $l$ for large values. This will yield a lower bound for the
minimum eigenvalue of $\nabla^{2}u_{\operatorname{reg},\lambda}.$

###### Proof.

Let $f(x)=|x|^{2r+2}.$ Then $\nabla f(x)=2(r+1)|x|^{2r}x.$ Writing

$\displaystyle\langle\nabla f(x)-\nabla f(y),x-y\rangle$
$\displaystyle=\langle\nabla f(x),x\rangle+\langle\nabla
f(y),y\rangle-\langle\nabla f(x),y\rangle-\langle\nabla f(y),x\rangle$
$\displaystyle=(2r+2)(|x|^{2r+2}+|y|^{2r+2})-(r+1)(|x|^{2r}+|y|^{2r})2\langle
x,y\rangle$ $\displaystyle=(2r+2)(|x|^{2r+2}+|y|^{2r+2})$
$\displaystyle+(r+1)(|x|^{2r}+|y|^{2r})\left(|x-y|^{2}-|x|^{2}-|y|^{2}\right)$
$\displaystyle=(r+1)\left(|x|^{2r+2}+|y|^{2r+2}-|x|^{2r}|y|^{2}-|y|^{2r}|x|^{2}\right)$
$\displaystyle+(r+1)(|x|^{2r}+|y|^{2r})|x-y|^{2}.$

Since

$\displaystyle|x|^{2r+2}+|y|^{2r+2}-|x|^{2r}|y|^{2r+2}-|y|^{2r}|x|^{2r+2}$
$\displaystyle=|x|^{2}(|x|^{2r}-|y|^{2r})-|y|^{2}(|x|^{2r}-|y|^{2r})$
$\displaystyle=(|x|^{2}-|y|^{2})(|x|^{2r}-|y|^{2r})$ $\displaystyle\geq 0,$

one deduces

$\langle\nabla f(x)-\nabla
f(y),x-y\rangle\geq(r+1)(|x|^{2r}+|y|^{2r})|x-y|^{2}\quad\forall
x,y\in\mathbb{R}^{d}.$ (C.4)

Noting that by the gradient local Lipschitz assumption on $g$, there holds

$\langle\nabla u(x)-\nabla
u(y),x-y\rangle\geq-L(1+|x|^{l}+|y|^{l})|x-y|^{2}\quad\forall
x,y\in\mathbb{R}^{d},$

the result immediately follows. ∎

###### Proof of Proposition A.4.

It is easy to see that the regularized measure satisfies a $2-$ dissipativity
condition with constant $A_{reg}=\lambda^{\frac{1}{r+1}}$ i.e

$\langle\nabla u_{r,\lambda}(x),x\rangle\geq A_{reg}|x|^{2}-(b+1).$ (C.5)

In addition, using Lemma C.1, it is easy to see that when
$|x|,|y|\geq\frac{L}{r+1}(\frac{1}{\lambda})$

$\langle\nabla u_{r,\lambda}(x)-\nabla u_{r,\lambda}(y),x-y\rangle\geq 0$

so one concludes that

$\langle\nabla u_{r,\lambda}(x)-\nabla u_{r,\lambda}(y),x-y\rangle\geq-
K_{\lambda}|x-y|^{2}\quad\forall x,y\in\mathbb{R}^{d}$

which leads to

$\nabla^{2}u_{r,\lambda}(x)\geq-K_{\lambda}I_{d}\quad\forall
x\in\mathbb{R}^{d}.$ (C.6)

Let $W:=e^{\frac{A_{reg}|x|^{2}}{4}}.$ Then, since $\nabla
W=W\frac{A_{reg}}{2}x$ and $\Delta
W\leq(\frac{A_{reg}d}{2}+\frac{A^{2}_{reg}d}{4})W$ one observes that

$LW=\Delta W-\langle\nabla u_{r,\lambda}(x),\nabla
W\rangle=(\frac{A_{reg}d}{2}+\frac{A^{2}_{reg}d}{4}-\frac{A_{reg}}{2}|x|^{2})W$
(C.7)

Since $\pi_{reg}$ also satisfies a Poincare inequality with consant $C_{P,r}$
using Theorem 3.15 in [25], it can be upgraded to a Log-Sobolev inequality
with constant

$\displaystyle\frac{1}{C_{LS}}$ $\displaystyle\leq
2\sqrt{\frac{1}{A_{reg}}\left(\frac{1}{2}+\frac{+\frac{A^{2}_{reg}d}{4}-\frac{A_{reg}}{2}+\frac{A_{reg}}{2}{\pi_{\operatorname{reg}}}\left(|x|^{2}\right)}{C_{P,reg}}\right)}$
(C.8)
$\displaystyle+\frac{K_{\lambda}}{A_{reg}\lambda}+\frac{K_{\lambda}\left(\frac{A_{reg}d}{2}+\frac{A^{2}_{reg}d}{4}+\frac{A_{reg}}{2}{\pi_{\operatorname{reg}}}\left(|x|^{2}\right)\right)+2\frac{A_{reg}}{2}}{C_{P,reg}}$

where ${\pi_{\operatorname{reg}}}(|x|^{2})$ is given by Lemma C.6. ∎

###### Proof of A.7.

The proof is the same, as in the proof of the moment bounds for the
regularized potential, since all we need is the $a-$ dissipativity and the
growth condition which are almost the same. It is done through providing first
exponential moments and then produce polynomial. ∎

######  Lemma C.2.

There holds

$\mathbb{E}|x_{t}-x_{k\lambda}|^{2p}\leq\mathcal{O}(\lambda^{p})$

###### Proof.

The proof follows in the same way is the respective one for the unregulazized
algorithm. ∎

######  Lemma C.3.

There holds

$\mathbb{E}|\nabla
u_{r,\lambda}(x_{k\lambda})-h_{r,\lambda}(x_{k\lambda})|^{2}\leq
C^{reg}_{tam}\lambda$

where $C^{reg}_{tam}\leq\mathcal{O}(d^{4r+2}).$

###### Proof.

Writing

$\displaystyle|\nabla
u_{r,\lambda}(x_{k\lambda})-h_{r,\lambda}(x_{k\lambda})|^{2}$
$\displaystyle\leq
2|h(x_{k\lambda})-h_{\lambda}(x_{k\lambda})|^{2}+2\lambda^{2}\left|(r+1)x_{k\lambda}|x_{k\lambda}|^{2r}(1-\frac{1}{1+\sqrt{\lambda}|x_{k\lambda}|^{2r+1}}\right|^{2}$
$\displaystyle\leq
2|h(x_{k\lambda})-h_{\lambda}(x_{k\lambda})|^{2}+2\lambda^{2}(r+1)^{2}|x_{k\lambda}|^{4r+2}.$

Taking expectations, the first term can be treated as in the proof of Lemma
A.5 with the moment bounds in Lemma A.7. ∎

######  Lemma C.4.

There holds

$\mathbb{E}|\nabla u_{r,\lambda}(x_{t})-\nabla
u_{r,\lambda}(x_{k\lambda}|^{2}\leq C^{reg}_{onestep}\lambda$

###### Proof.

The proof follows in the same way as the respective one for the unregularized
algorithm with the new moment bounds, and setting the Local Lipschitz
constants as in Lemma A.6. ∎

######  Lemma C.5.

Let $x_{t}$ the continuous time interpolation of the algorithm. Then, for
$\lambda<\lambda_{\max}$ and for every $t\in[k\lambda,(k+1)\lambda]$
,$k\in\mathbb{N},$ there holds

$\frac{d}{dt}H_{\pi}(\hat{\pi}_{t}^{reg})\leq-\frac{3}{4}I_{\pi}(\hat{\pi}_{t}^{reg})+\mathbb{E}|\nabla
u_{r,\lambda}(x_{t})-h_{r,\lambda}(x_{k\lambda})|^{2}$

.

###### Proof.

Since the regularized potential has the same key properties as the
unregularized, the interpolation inequality holds with exactly the same
arguments. ∎

######  Lemma C.6.

Let $p\in\mathbb{N}.$ There holds

$\mathbb{E}_{\pi}|x|^{2p}\leq C_{\pi}$

and

$\mathbb{E}_{{\pi_{\operatorname{reg}}}}|x|^{2p}\leq
C_{{\pi_{\operatorname{reg}}}}$

where $C_{{\pi_{\operatorname{reg}}}}$ and $C_{\pi}$ are
$\mathcal{O}(d^{2p}).$

###### Proof.

Using the fact that both measures satisfy the dissipativity condition with
constant $a$ we will proceed with the same arguments. We will show it only for
$\pi$. Since $\pi$ and ${\pi_{\operatorname{reg}}}$ satisfy a Poincare
inequality they have finite polynomial moments of all orders.

$|x|^{2p-1}\langle h(x),x\rangle\geq|x|^{2p-1}(A|x|^{a}-b)\geq
A|x|^{2p}-A-b|x|^{2p-1}.$ (C.9)

Setting $V(x)=|x|^{2p}$ one notices that $\nabla V(x)=2p|x|^{2p-1}x$ and
$\Delta V=(2pd+4(p-1)p)|x|^{2p-2}.$ Since $\pi$ is the invariant measure of
the Langevin SDE with generator

$LV=\Delta V-\langle V,h\rangle,$

there holds

$(2pd+4(p-1)p)\mathbb{E}_{\pi}|x|^{2p-2}=\mathbb{E}_{\pi}\Delta
V(x)=\mathbb{E}_{\pi}\langle V(x),h(x)\rangle\geq
2p\left(A\mathbb{E}_{\pi}|x|^{2p}-A-b\mathbb{E}_{\pi}|x|^{2p-1}\right).$

Iterating over $2p$ yields the result. ∎

###### Proof of Theorem 7.

Setting $\dot{c}=\frac{3}{2}C_{LSI}$ one obtains

$\displaystyle\frac{d}{dt}H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}_{t}^{reg})$
$\displaystyle\leq-\frac{3}{4}I_{{\pi_{\operatorname{reg}}}}(\hat{\pi}_{t}^{reg})+\mathbb{E}|h_{r,\lambda}(x_{k\lambda}-\nabla
u_{r,\lambda}(x_{t})|^{2}$
$\displaystyle\leq-\dot{c}H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}_{t}^{reg})+2\mathbb{E}|h_{r,\lambda}(x_{k\lambda})-\nabla
u_{r,\lambda}(x_{k\lambda})|^{2}+2\mathbb{E}|\nabla
u_{r,\lambda}(x_{k\lambda})-\nabla u_{r,\lambda}(x_{t})|^{2}$
$\displaystyle\leq-\dot{c}H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}_{t}^{reg})+\hat{C}\lambda$

where $\hat{C}$ depends polynomially on the dimension, where the first term
has been bounded using the Log-Sobolev inequality and the rest of the terms
using the one-step error and taming, as in the unregularized case . Splitting
the terms one obtains

$\displaystyle\left(\frac{d}{dt}H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}_{t}^{reg})+\dot{c}H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}_{t}^{reg})\right)e^{\dot{c}t}\leq
e^{\dot{c}t}\hat{C}\lambda$

Integrating over $[k\lambda,t]$ yields

$\displaystyle
e^{\dot{c}t}H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}_{t}^{reg})-e^{\dot{c}k\lambda}H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}^{reg}_{k\lambda})\leq\frac{\hat{C}}{\dot{c}}\lambda(e^{\dot{c}t}-e^{\dot{c}k\lambda})$

which implies

$H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}_{t}^{reg})\leq
e^{\dot{c}(k\lambda-t)}H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}^{reg}_{k\lambda})+\frac{\hat{C}}{\dot{c}}\lambda(1-e^{\dot{c}(k\lambda-t)}).$
(C.10)

Setting $t=n\lambda$ and $k=(n-1)$ leads to

$H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}^{reg}_{n\lambda})\leq
e^{-\dot{c}\lambda}H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}^{reg}_{(n-1)\lambda})+\frac{\hat{C}}{\dot{c}}\lambda(1-e^{-\dot{c}\lambda})$

so by iterating over $n$,

$H_{{\pi_{\operatorname{reg}}}}(\hat{\pi}^{reg}_{n\lambda})\leq
e^{-\dot{c}\lambda(n-1)}H_{{\pi_{\operatorname{reg}}}}(\rho_{0})+\frac{\hat{C}}{\dot{c}}\lambda$

Noticing that

$\displaystyle\int\log\frac{\rho^{\operatorname{reg}}_{n}}{\pi}d\rho^{\operatorname{reg}}_{n}$
$\displaystyle=\int\log\frac{\rho^{\operatorname{reg}}_{n}}{{\pi_{\operatorname{reg}}}}d\rho^{\operatorname{reg}}_{n}+\int\log\frac{{\pi_{\operatorname{reg}}}}{\pi}d\rho^{\operatorname{reg}}_{n}$
$\displaystyle=H_{{\pi_{\operatorname{reg}}}}(\rho^{\operatorname{reg}}_{n})+\int\log\frac{{\pi_{\operatorname{reg}}}}{\pi}d(\rho^{\operatorname{reg}}_{n}-\pi)-H_{\pi_{\operatorname{reg}}}(\pi)$
$\displaystyle\leq
H_{{\pi_{\operatorname{reg}}}}(\rho^{\operatorname{reg}}_{n})+\lambda\mathbb{E}_{\rho^{\operatorname{reg}}_{n}}[|x|^{2r+2}]+\lambda\mathbb{E}_{\pi}[|x|^{2r+2}].$

The result follows by Lemma C.6. ∎

###### Proof of Corollary 4.

Using Pinsker’s inequality and the bound in Theorem 7 one obtains the bound in
total variation. Recall that for the $W_{2}$ distance, since
${\pi_{\operatorname{reg}}}$ satisfies a Log-Sobolev inequality then, it
satisfies a Talagrand inequality with same constant.

$\displaystyle W_{2}(\mathcal{L}(\bar{x}^{\lambda}_{n},\pi)$
$\displaystyle\leq
W_{2}(\mathcal{L}(\bar{x}^{\lambda}_{n},{\pi_{\operatorname{reg}}})+W_{2}(\pi,{\pi_{\operatorname{reg}}})$
$\displaystyle\leq\sqrt{2C_{\operatorname{LSI}}^{-1}(H_{\pi_{\operatorname{reg}}}(\rho^{\operatorname{reg}}_{n})}+2C_{\operatorname{LSI}}^{-1}\sqrt{I_{\pi_{\operatorname{reg}}}(\pi)})$

The first term can be bounded by Theorem 7 while the second term is

$\sqrt{\int|\nabla\log{\pi_{\operatorname{reg}}}(x)-\nabla\log\pi(x)|^{2}d\pi}\leq\lambda\sqrt{\mathbb{E}_{\pi}[|x|^{4r+2}]}.$

Using the bound on the Log Sobolev constant and Lemma C.6 leads to the result.
∎

## Acknowledgments

This research was supported in part by the French National Research Agency
(ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PEIA-0003), the
“Investissements d’avenir” program (ANR-15-IDEX-02), the LabEx PERSYVAL
(ANR-11-LABX-0025-01), MIAI@Grenoble Alpes (ANR-19-P3IA-0003). PM is also a
member of the Archimedes Research Unit, Athena RC, Department of Mathematics,
University of Athens. This research was also supported in part by project MIS
5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the
European Union under the NextGenerationEU Program.

## References

  * Bakry & Émery [2006] Bakry, D. and Émery, M.  Diffusions hypercontractives.  In _Séminaire de Probabilités XIX 1983/84: Proceedings_ , pp. 177–206. Springer, 2006.
  * Bakry et al. [2008] Bakry, D., Barthe, F., Cattiaux, P., and Guillin, A.  A simple proof of the poincaré inequality for a large class of probability measures.  _Electronic Communications in Probability_ , 13:60–66, 2008\.
  * Bakry et al. [2014] Bakry, D., Gentil, I., Ledoux, M., et al.  _Analysis and geometry of Markov diffusion operators_ , volume 103\.  Springer, 2014.
  * Balasubramanian et al. [2022] Balasubramanian, K., Chewi, S., Erdogdu, M. A., Salim, A., and Zhang, S.  Towards a theory of non-log-concave sampling: first-order stationarity guarantees for langevin monte carlo.  In _Conference on Learning Theory_ , pp. 2896–2923. PMLR, 2022\.
  * Barkhagen et al. [2021] Barkhagen, M., Chau, N. H., Moulines, É., Rásonyi, M., Sabanis, S., and Zhang, Y.  On stochastic gradient langevin dynamics with dependent data streams in the logconcave case.  _Bernoulli_ , 27(1):1–33, 2021.
  * Bolley & Villani [2005] Bolley, F. and Villani, C.  Weighted csiszár-kullback-pinsker inequalities and applications to transportation inequalities.  In _Annales de la Faculté des sciences de Toulouse: Mathématiques_ , volume 14, pp. 331–352, 2005.
  * Brosse et al. [2019] Brosse, N., Durmus, A., Moulines, É., and Sabanis, S.  The tamed unadjusted Langevin algorithm.  _Stochastic Processes and their Applications_ , 129(10):3638–3663, 2019.
  * Cattiaux et al. [2013] Cattiaux, P., Guillin, A., and Zitt, P. A.  Poincaré inequalities and hitting times.  In _Annales de l’IHP Probabilités et statistiques_ , volume 49, pp. 95–118, 2013.
  * Chau et al. [2021] Chau, N. H., Moulines, É., Rásonyi, M., Sabanis, S., and Zhang, Y.  On stochastic gradient langevin dynamics with dependent data streams: The fully nonconvex case.  _SIAM Journal on Mathematics of Data Science_ , 3(3):959–986, 2021.
  * Cheng et al. [2018] Cheng, X., Chatterji, N. S., Abbasi-Yadkori, Y., Bartlett, P. L., and Jordan, M. I.  Sharp convergence rates for Langevin dynamics in the nonconvex setting.  _arXiv preprint arXiv:1805.01648_ , 2018.
  * Chewi et al. [2021] Chewi, S., Erdogdu, M. A., Li, M. B., Shen, R., and Zhang, M.  Analysis of langevin monte carlo from poincar$\backslash$’e to log-sobolev.  _arXiv preprint arXiv:2112.12662_ , 2021.
  * Dalalyan [2017] Dalalyan, A. S.  Theoretical guarantees for approximate sampling from smooth and log-concave densities.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 79(3):651–676, 2017.
  * Durmus & Moulines [2017] Durmus, A. and Moulines, E.  Nonasymptotic convergence analysis for the unadjusted Langevin algorithm.  _The Annals of Applied Probability_ , 27(3):1551–1587, 2017.
  * Durmus & Moulines [2019] Durmus, A. and Moulines, E.  High-dimensional Bayesian inference via the unadjusted Langevin algorithm.  _Bernoulli_ , 25(4A):2854–2882, 2019.
  * Erdogdu & Hosseinzadeh [2021] Erdogdu, M. A. and Hosseinzadeh, R.  On the convergence of langevin monte carlo: The interplay between tail growth and smoothness.  In _Conference on Learning Theory_ , pp. 1776–1822. PMLR, 2021\.
  * Erdogdu et al. [2022] Erdogdu, M. A., Hosseinzadeh, R., and Zhang, S.  Convergence of langevin monte carlo in chi-squared and rényi divergence.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 8151–8175. PMLR, 2022.
  * Hutzenthaler et al. [2011] Hutzenthaler, M., Jentzen, A., and Kloeden, P. E.  Strong and weak divergence in finite time of euler’s method for stochastic differential equations with non-globally lipschitz continuous coefficients.  _Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences_ , 467(2130):1563–1576, 2011\.  ISSN 1364-5021.
  * Hutzenthaler et al. [2012] Hutzenthaler, M., Jentzen, A., and Kloeden, P. E.  Strong convergence of an explicit numerical method for sdes with nonglobally lipschitz continuous coefficients.  _Ann. Appl. Probab._ , 22(4):1611–1641, 08 2012\.
  * Johnston et al. [2023] Johnston, T., Lytras, I., and Sabanis, S.  Kinetic langevin mcmc sampling without gradient lipschitz continuity–the strongly convex case.  _arXiv preprint arXiv:2301.08039_ , 2023.
  * Li & Erdogdu [2020] Li, M. B. and Erdogdu, M. A.  Riemannian langevin algorithm for solving semidefinite programs.  _arXiv preprint arXiv:2010.11176_ , 2020.
  * Lovas et al. [2023] Lovas, A., Lytras, I., Rásonyi, M., and Sabanis, S.  Taming neural networks with tusla: Nonconvex learning via adaptive stochastic gradient langevin algorithms.  _SIAM Journal on Mathematics of Data Science_ , 5(2):323–345, 2023.
  * Lytras & Sabanis [2023] Lytras, I. and Sabanis, S.  Taming under isoperimetry.  _arXiv preprint arXiv:2311.09003_ , 2023.
  * Majka et al. [2020] Majka, M. B., Mijatović, A., and Szpruch, Ł.  Nonasymptotic bounds for sampling algorithms without log-concavity.  _The Annals of Applied Probability_ , 30(4):1534–1581, 2020.
  * McNabb [1986] McNabb, A.  Comparison theorems for differential equations.  _Journal of mathematical analysis and applications_ , 119(1-2):417–428, 1986.
  * Menz & Schlichting [2014] Menz, G. and Schlichting, A.  Poincaré and logarithmic sobolev inequalities by decomposition of the energy landscape.  _The Annals of Probability_ , 42(5):1809–1884, 2014.
  * Mou et al. [2022] Mou, W., Flammarion, N., Wainwright, M. J., and Bartlett, P. L.  Improved bounds for discretization of langevin diffusions: Near-optimal rates without convexity.  _Bernoulli_ , 28(3):1577–1601, 2022.
  * Mousavi-Hosseini et al. [2023] Mousavi-Hosseini, A., Farghly, T. K., He, Y., Balasubramanian, K., and Erdogdu, M. A.  Towards a complete analysis of langevin monte carlo: Beyond poincaré inequality.  In _The Thirty Sixth Annual Conference on Learning Theory_ , pp. 1–35. PMLR, 2023.
  * Neufeld et al. [2022] Neufeld, A., En, M. N. C., and Zhang, Y.  Non-asymptotic convergence bounds for modified tamed unadjusted langevin algorithm in non-convex setting.  _arXiv preprint arXiv:2207.02600_ , 2022.
  * Nguyen et al. [2021] Nguyen, D., Dang, X., and Chen, Y.  Unadjusted langevin algorithm for non-convex weakly smooth potentials.  _arXiv preprint arXiv:2101.06369_ , 2021.
  * Raginsky et al. [2017] Raginsky, M., Rakhlin, A., and Telgarsky, M.  Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis.  In _Conference on Learning Theory_ , pp. 1674–1703, 2017.
  * Sabanis [2013] Sabanis, S.  A note on tamed euler approximations.  _Electron. Commun. Probab._ , 18(47):1–10, 2013\.
  * Sabanis [2016] Sabanis, S.  Euler approximations with varying coefficients: the case of superlinearly growing diffusion coefficients.  _Ann. Appl. Probab._ , 26(4):2083–2105, 2016\.
  * Vempala & Wibisono [2019] Vempala, S. and Wibisono, A.  Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices.  _Advances in neural information processing systems_ , 32, 2019.
  * Zhang et al. [2023] Zhang, Y., Akyildiz, Ö. D., Damoulas, T., and Sabanis, S.  Nonasymptotic estimates for stochastic gradient langevin dynamics under local conditions in nonconvex optimization.  _Applied Mathematics & Optimization_, 87(2):25, 2023.

  *[ULA]: unadjusted Langevin algorithm
  *[i.i.d.]: independent and identically distributed
  *[KL]: Kullback–Leibler
  *[SGLD]: stochastic gradient Langevin dynamics
  *[LSI]: logarithmic Sobolev inequality
  *[PI]: Poincaré inequality
  *[SDE]: stochastic differential equation
  *[SDEs]: stochastic differential equation
  *[WC]: weak convexity
  *[LSIs]: logarithmic Sobolev inequality
  *[wd-TULA]: weakly dissipative tamed unadjusted Langevin algorithm
  *[reg-TULA]: regularized tamed unadjusted Langevin algorithm
  *[TV]: total variation