# Unadjusted Langevin algorithm for non-convex weakly smooth potentials

Dao<EMAIL_ADDRESS>[ Xin
<EMAIL_ADDRESS>[ Yixin<EMAIL_ADDRESS>[
Department of Mathematics, University of Mississippi.  Department of
Mathematics, University of Mississippi.  Department of Computer Science,
University of Mississippi.  University of Mississippi

(2020)

###### Abstract

Discretization of continuous-time diffusion processes is a widely recognized
method for sampling. However, the canonical Euler Maruyama discretization of
the Langevin diffusion process, referred as Unadjusted Langevin Algorithm
(ULA), studied mostly in the context of smooth (gradient Lipschitz) and
strongly log-concave densities, is a considerable hindrance for its deployment
in many sciences, including statistics and machine learning. In this paper, we
establish several theoretical contributions to the literature on such sampling
methods for non-convex distributions. Particularly, we introduce a new mixture
weakly smooth condition, under which we prove that ULA will converge with
additional log-Sobolev inequality. We also show that ULA for smoothing
potential will converge in $L_{2}$-Wasserstein distance. Moreover, using
convexification of nonconvex domain [24] in combination with regularization,
we establish the convergence in Kullback-Leibler (KL) divergence with the
number of iterations to reach $\epsilon$-neighborhood of a target distribution
in only polynomial dependence on the dimension. We relax the conditions of
[31] and prove convergence guarantees under isoperimetry, and non-strongly
convex at infinity.

Langevin Monte Carlo,

non-convex sampling,

Kullback-Leibler divergence,

regularization,

weakly smooth,

###### keywords:

[class=MSC]

††volume: 0††issue: 0

2010.00000

, and

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Assumptions on the potential $U$
    2. 2.2 Smoothing using $p$-generalized Gaussian smoothing
  3. 3 Convergence in KL divergence along ULA under LSI
    1. 3.1 Recall KL divergence along Langevin dynamics
    2. 3.2 Main result: KL divergence along Unadjusted Langevin Algorithm
    3. 3.3 Sampling via smoothing potential
  4. 4 Extended result
    1. 4.1 ULA convergence under $\gamma-$Poincaré inequality, $\alpha$-mixture weakly smooth and $2-$dissipativity
    2. 4.2 ULA convergence under non-strongly convex outside the ball, $\alpha$-mixture weakly smooth and $2-$dissipativity
  5. 5 Conclusion
  6. A Measure definitions and isoperimetry
  7. B Proofs of $p$-generalized Gaussian smoothing
    1. B.1 Proof of $\alpha$-mixture weakly smooth property
    2. B.2 Proof of $p$-generalized Gaussian smoothing properties
  8. C Proofs under LSI
    1. C.1 Proof of Lemma 3.2
    2. C.2 Proof of Lemma 3.2
    3. C.3 Proof of Lemma 3.1
    4. C.4 Proof of Theorem 3.1
  9. D Proof of sampling via smoothing potential
    1. D.1 Proof of Lemma 3.3
    2. D.2 Proof of Lemma 3.2
    3. D.3 Proof of Lemma 3.4
  10. E Convexification of non-convex domain
    1. E.1 Proof of Lemma 4.1
    2. E.2 Proof of Lemma 4.2
    3. E.3 Proof of lemma 4.3
    4. E.4 Proof of lemma 4.1
    5. E.5 Proof of lemma 4.1
    6. E.6 Proof of Lemma 5
  11. F Proof of additional lemmas

##  1 Introduction

Over the last decade, Bayesian inference has become one of the most prevalent
inferring instruments for a variety of disciplines, including the
computational statistics and statistical learning [30]. In general, Bayesian
inference seeks to generate samples of the posterior distribution of the form:

$\rho(\mathrm{x})=\mathrm{e}^{-U(x)}/\int_{R^{d}}\mathrm{e}^{-U(y)}\mathrm{d}y,$
(1.1)

where the function $U(\mathrm{x})$, also known as the potential function, is
often convex. The most conventional approaches, random walks Metropolis
Hasting [30], often struggle to select a proper proposal distribution for
sampling. As a result, it has been proposed to consider continuous dynamics
which inherently leaves the objective distribution $\rho$ invariant. Probably
one of the most well-known example of these continuous dynamic applications is
the over-damped Langevin diffusion [10] associated with $U$,

$\displaystyle dX_{t}=-\nabla U(X_{t})dt+\sqrt{2}dB_{t},$ (1.2)

where $B_{t}$ is a $d$-dimensional Brownian motion and its Euler-Maruyama
discretization hinges on the following update rule:

$\mathrm{x}_{k+1}=\mathrm{x}_{k}-\eta_{k}\nabla
U(\mathrm{x}_{k})+\sqrt{2\eta}\xi_{k},$ (1.3)

where $(\eta_{k})_{k\geq 1}$ is a sequence of step sizes, which can be kept
constant or decreasing to $0$, and $\xi_{k}\sim{N}(0,\ I_{d})$ ($I_{d}$
denotes identity matrix dimension $d$), are independent Gaussian random
vectors. It can be seen that Euler-Maruyama discretization, also known as
Langevin Monte Carlo (LMC) algorithm, does not involve knowledge of $U$, but
gradient of $U$ instead, which makes it ideally applicable where we typically
only know $U$ up to a normalizing constant. Owing to its simplicity,
efficiency, and well understood properties, there are various applications
using LMC [33, 9, 28, 34, 23]. Much of the theory of convergence of sampling
used to focus on asymptotic convergence, failing to provide a detailed study
of dimension dependence. Recently, there is a surge of interests in non-
asymptotic rates of convergence, which include dimension dependence,
especially polynomial dependence on the dimension of target distribution; see,
e.g., [8, 10, 12, 15, 3, 14, 7, 22, 25, 26]. However, there is a critical gap
in the theory of discretization of an underlying stochastic differential
equation (SDE) to the broad spectrum of applications in statistical inference.
In particular, the application of techniques from SDEs traditionally requires
$U(\mathrm{x})$ to have Lipschitz-continuous gradients. This requirement
prohibits many typical utilizations [13]. [6] has recently established an
original approach to deal with weakly smooth (possibly non-smooth) potential
problems through smoothing. Their technique rests on results obtained from the
optimization community, perturbing a gradient evaluating point by a Gaussian.
However, [6] analyzes over-damped Langevin diffusion in the contexts of convex
potential functions while many applications involve sampling in high
dimensional spaces have non convex settings. In another research, [16]
proposes a very beautiful result using tail growth for weakly smooth and
weakly dissipative potentials. By using degenerated convex and modified log
Sobolev inequality, they prove that LMC gets $\epsilon$-neighborhood of a
target distribution in KL divergence with the convergence rate of
$\tilde{O}(d^{\frac{1}{\alpha}+\frac{1+\alpha}{\alpha}(\frac{2}{\beta}-\mathrm{1}_{\\{\beta\neq
1\\}})}\epsilon^{\frac{-1}{\alpha}})$ where $\alpha$ and $\beta$ are degrees
of weakly smooth and dissipative defined in the next section.

Unfortunately, (weakly) smooth conditions typically can not cover a mixture of
distributions with different tail growth behaviors, which prohibit a large
range of applications. Therefore, we first introduce an $\alpha$-mixture
weakly smooth condition to overcome the limitation of the current weakly
smooth condition. Under our novel condition and log-Sobolev inequality, we
will recover the ULA convergence results [31]. In addition, we also show that
ULA for smoothing potential will converge in $L_{2}$-Wasserstein distance.
Since log-Sobolev inequality is preserved under bounded perturbation, we will
extend the results based on convexification of a non-convex domain [24]. Our
contributions can be outlined as follows.

First, for a potential function $U$, which satisfies an $\alpha$-mixture
weakly smooth, and $\gamma$-log Sobolev inequality, we prove that ULA achieves
the convergence rate of

$\tilde{O}\left(d^{\frac{1}{\alpha}}\gamma^{\frac{-1}{\alpha}}\epsilon^{\frac{-1}{\alpha}}\right)$
(1.4)

in KL-divergence.

Second, our convergence results also cover sampling from non-convex
potentials, satisfying $\alpha$-mixture weakly smooth, $2$-dissipative and
$\gamma$-Poincaré or $\gamma$-Talagrand with convergence rate in KL divergence
of

$\tilde{O}\left(d^{\frac{2}{\alpha}+1}\gamma^{\left(\frac{-1}{\alpha}-1\right)}\epsilon^{\frac{-1}{\alpha}}\right).$
(1.5)

Third, we further investigate the case of $\alpha$-mixture weakly smooth,
$2$-dissipative and non strongly convex outside the ball of radius $R$ and
obtain the convergence rate of

$\tilde{O}\left(d^{1+\frac{2}{\alpha}}\gamma^{\left(\frac{-1}{\alpha}-1\right)}e^{5\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4\max\left\\{L_{i}\right\\}R^{1+\alpha}\right)\left(\frac{1}{\alpha}+1\right)}\epsilon^{\frac{-1}{\alpha}}\right).$
(1.6)

Finally, our convergence results remain valid under finite perturbations,
indicating that it is applicable to an even larger class of potentials. Last
but not least, convergence in KL divergence implies convergence in total
variation and in $L_{2}$-Wasserstein metrics based on Pinsker inequalities,
which in turn gives convergence rates of
$O(\cdot\epsilon^{\frac{-2}{\alpha})}$ and
$O(\cdot\epsilon^{\frac{-2\beta}{\alpha}}d^{\frac{2}{\alpha}})$ in place of
$O(\cdot\epsilon^{\frac{-1}{\alpha})}$ in each case above, respectively for
total variation and $L_{2}$-Wasserstein metrics.

The rest of the paper is organized as follows. Section 2 sets out the
notation, definition and smoothing properties necessary to give our main
results in section 3. Section 4 extends the convexification of non convex
domain of [24] for strongly convex outside the ball to non-strongly convex
outside the ball, and employs this outcome in combination with regularization
to obtain convergence in KL divergence for potentials which satisfy log
Sobolev, Talagrand, Poincaré inequalities, or non-strongly convex at infinity
while Section 5 presents our conclusions.

##  2 Preliminaries

This section provides the notational conventions, assumptions, and some
auxiliary results used in this paper. We let $\left|s\right|$, for a real
number $s\in\mathbb{R}$, denote its absolute value and use $\left\langle\ ,\
\right\rangle$ to specify inner products. We use $\|x\|_{p}$ to denote the
$p$-norm of a vector $x\in\mathbb{R}^{d}$ and throughout the paper, we drop
the subscript and just write
$\|x\|\stackrel{{\scriptstyle\triangle}}{{=}}\|x\|_{2}$ whenever $p=2$. For a
function $U$ :$\mathbb{R}^{d}\rightarrow\mathbb{R}$, which is twice
differentiable, we use $\nabla U(x)$ and $\nabla^{2}U(x)$ to denote
correspondingly the gradient and the Hessian of $U$ with respect to $x$. We
use $A\succeq B$ if $A-B$ is a positive semi-definite matrix. We use big-oh
notation $O$ in the following sense that if $f(x)={\displaystyle O(g(x))}$
implies $\lim_{x\rightarrow\infty}\sup\frac{f(x)}{g(x)}<\infty$ and
$\tilde{O}$ suppresses the logarithmic factors.

###  2.1 Assumptions on the potential $U$

The objective of this paper is to sample from a distribution
$\pi\propto\exp(-U(x))$, where $x\in\mathbb{R}^{d}$. While sampling from the
exact distribution $\pi(x)$ is generally computationally demanding, it is
largely adequate to sample from an approximated distribution $\tilde{\pi}(x)$
which is in the vicinity of $\pi(x)$ by some distances. In this paper, we
suppose some of the following conditions hold:

######  Assumption 2.1.

($\alpha$-mixture weakly smooth) There exist
$0<\alpha=\alpha_{1}<...<\alpha_{N}\leq 1$, $i=1,..,N$ $0<L_{i}<\infty$ so
that $\forall x,\ y\in\mathbb{R}^{d}$, we obtain $\left\|\nabla U(x)-\nabla
U(y)\right\|\leq\sum_{i=1}^{N}L_{i}\left\|x-y\right\|^{\alpha_{i}}$ where
$\nabla U(x)$ represents an arbitrary sub-gradient of $U$ at $x$.

######  Assumption 2.2.

($\left(\alpha,\ell\right)-$weakly smooth) There exist $0\leq\ell$,
$0<L<\infty$ and $\alpha\in[0,1]$ so that $\forall x,\ y\in\mathbb{R}^{d}$, we
obtain

$\left\|\nabla U(x)-\nabla U(y)\right\|\leq
L\left(1+\left\|x-y\right\|^{\ell}\right)\left\|x-y\right\|^{\alpha},$

where $\nabla U(x)$ represents an arbitrary sub-gradient of $U$ at $x$.

######  Assumption 2.3.

($\left(\mu,\theta\right)$-degenerated convex outside the ball) There exists
some $\mu>0,$ $1\geq\theta\geq 0$ so that for every $\left\|x\right\|\geq R,$
the potential function $U(x)$ satisfies $\nabla^{2}U(x)\succeq
m\left(\left\|x\right\|\right)I_{d}$ where
$m\left(r\right)=\mu\left(1+r^{2}\right)^{-\frac{\theta}{2}}.$

######  Assumption 2.4.

($\beta-$dissipativity). There exists $\beta\geq 1$, $a$, $b>0$ such that
$\forall x\in\mathbb{R}^{d}$, $\left\langle\nabla U(x),x\right\rangle\geq
a\left\|x\right\|^{\beta}-b.$

######  Assumption 2.5.

($LSI\left(\gamma\right)$) There exists some $\gamma>0,$ so that for all
probability distribution $p\left(x\right)$ absolutely continuous $w.r.t.\
\pi\left(x\right)$, $H({\displaystyle p|\pi)\leq\frac{1}{2\gamma}I(p|\pi)}.$

######  Assumption 2.6.

($PI\left(\gamma\right)$) There exists some $\gamma>0,$ so that for all smooth
function $g\colon\mathbb{R}^{d}\to\mathbb{R}$,
$Var_{\pi}(g)\leq\frac{1}{\gamma}E_{\pi}\left[\left\|\nabla
g\right\|^{2}\right]$ where $Var_{\pi}(g)=E_{\pi}[g^{2}]-E_{\pi}[g]^{2}$ is
the variance of $g$ under $\pi$.

######  Assumption 2.7.

(non-strongly convex outside the ball) For every $\left\|x\right\|\geq R$, the
potential function $U(x)$ is positive semi-definite, that is for every
$y\in\mathbb{R}^{d}$, ${\displaystyle\left\langle y,\nabla^{2}U(x)\
y\right\rangle\geq 0}.$

######  Assumption 2.8.

The function $U(x)$ has stationary point at zero $\nabla U(0)=0.$

######  Remark 2.1.

Assumption 2.8 is imposed without loss of generality. Condition 2.1 often
holds for a mixture of distribution with different tail growth behaviors. It
is straightforward to generalize condition 2.1 from the mixture of two
distribution with the same constant $L$, so we will consider condition 2.2 to
simplify the proof while optimize the convergence rate. Condition 2.2 is an
extension of $\alpha$-weakly smooth or $\alpha-$Holder continuity of the
(sub)gradients of $U$ (that is when $\ell=0$, we recover normal
$\alpha$-weakly smooth).

###  2.2 Smoothing using $p$-generalized Gaussian smoothing

A feature that follows straightforwardly from Assumption 2.1 is that for
$\forall x,\ y\in\mathrm{\mathbb{R}}^{d}$:

######  Lemma 2.1.

If potential $U:\mathbb{R}^{d}\rightarrow\mathbb{R}$ satisfies an
$\alpha$-mixture weakly smooth for some
$0<\alpha=\alpha_{1}<...<\alpha_{N}\leq 1$, $i=1,..,N$ $0<L_{i}<\infty$, then:

$U(y)\leq U(x)+\left\langle\nabla U(x),\
y-x\right\rangle+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\|y-x\|^{1+\alpha_{i}}.$
(2.1)

In particular, if the potential $U:\mathbb{R}^{d}\rightarrow\mathbb{R}$
satisfies $\left(\alpha,\ell\right)-$weakly smooth for some $\alpha+\ell\leq
1$ and $\alpha\in(0,1]$, then:

$U(y)\leq U(x)+\left\langle\nabla U(x),\
y-x\right\rangle+\frac{L}{1+\alpha}\|y-x\|^{1+\alpha}+\frac{L}{1+\ell+\alpha}\|y-x\|^{1+\ell+\alpha}.$
(2.2)

###### Proof.

See Appendix B.1 ∎

Here, to deal with the heavy tail behavior of some distributions in the
mixture, we use $p$-generalized Gaussian smoothing. Particularly, for $\mu\geq
0$, $p$-generalized Gaussian smoothing $U_{\mu}$ of $U$ is defined as:

$U_{\mu}(y):=\mathrm{E}_{\xi}[U(y+\mu\xi)]=\frac{1}{\kappa}\int_{\mathbb{R}^{d}}U(y+\mu\xi)e^{-\left\|\xi\right\|_{p}^{p}/p}d\xi,$

where
$\kappa\stackrel{{{}_{def}}}{{=}}\int_{\mathbb{R}^{d}}e^{-\left\|\xi\right\|_{p}^{p}/p}d\xi=\frac{2^{d}\Gamma^{d}(\frac{1}{p})}{p^{d-\frac{d}{p}}}$
and $\xi\sim N_{p}(0,I_{d\times d})$ (the $p$-generalized Gaussian
distribution). The rationale for taking into account the $p$-generalized
Gaussian smoothing $U_{\mu}$ rather than $U$ is that it typically benefits
from superior smoothness properties. In particular, $U_{\mu}$ is smooth albeit
$U$ is not. In addition, $p$-generalized Gaussian smoothing is more
generalized than Gaussian smoothing in the sense that it contains all normal
distribution when $p=2$ and all Laplace distribution when $p=1$. This family
of distributions allows for tails that are either heavier or lighter than
normal and in the limit as well as containing all the continuous uniform
distribution. More importantly, we prove that a smoothing potential
$U_{\mu}(x)$ is actually smooth (gradient Lipschitz). This property is novel
and potentially useful in the optimization or sampling process, especially
when the potential exhibits some sort of weakly smooth behaviors. Here to
simplify the proof, we consider $p\in\mathbb{R}^{+},$ $2\geq p\geq 1$ and some
primary features of $U_{\mu}$ based on adapting those results of [27].

######  Lemma 2.2.

If potential $U:\mathbb{R}^{d}\rightarrow\mathbb{R}$ satisfies an
$\alpha$-mixture weakly smooth for some
$0<\alpha=\alpha_{1}<...<\alpha_{N}\leq 1$, $i=1,..,N$ $0<L_{i}<\infty$, then:

(i) $\forall x\in\mathbb{R}^{d}$ :
$\left|U_{\mu}(x)-U(x)\right|{\displaystyle\leq\sum_{i}L_{i}\mu^{1+\alpha_{i}}d^{\frac{1+\alpha_{i}}{p}},}$

(ii) $\forall x\in\mathbb{R}^{d}$: ${\displaystyle\left\|\nabla
U_{\mu}(x)-\nabla
U(x)\right\|\leq\sum_{i}L_{i}\mu^{\alpha_{i}}d^{\frac{3}{p}}},$

(iii) $\forall x,\ y\in\mathbb{R}^{d}$: ${\displaystyle\left\|\nabla
U_{\mu}(y)-\nabla
U_{\mu}(x)\right\|\leq\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2}{p}}\left\|y-x\right\|.}$

In particular, if the potential $U:\mathbb{R}^{d}\rightarrow\mathbb{R}$
satisfies $\left(\alpha,\ell\right)-$weakly smooth for some $\alpha+\ell\leq
1$ and $\alpha\in[0,1]$, then:

(i) $\forall x\in\mathbb{R}^{d}$ :
$\left|U_{\mu}(x)-U(x)\right|{\displaystyle\leq
2L\mu^{1+\ell+\alpha}d^{\frac{1+\ell+\alpha}{p}},}$

(ii) $\forall x\in\mathbb{R}^{d}$: ${\displaystyle\left\|\nabla
U_{\mu}(x)-\nabla U(x)\right\|\leq L\mu^{\alpha}d^{1+\frac{1}{p}}},$

(iii) $\forall x,\ y\in\mathbb{R}^{d}$: ${\displaystyle\left\|\nabla
U_{\mu}(y)-\nabla
U_{\mu}(x)\right\|\leq\frac{L}{\mu^{1-\alpha}}d^{\frac{2}{p}}\left\|y-x\right\|.}$

###### Proof.

See Appendix B.2 ∎

##  3 Convergence in KL divergence along ULA under LSI

In this section we review the definition of KL divergence and the convergence
of KL divergence along the Langevin dynamics in continuous time under log-
Sobolev inequality. We then derive our main result for ULA algorithm under
LSI.

###  3.1 Recall KL divergence along Langevin dynamics

Let $p,\pi$ be probability density functions with respect to the Lebesgue
measure on $\mathbb{R}^{d}$. KL divergence of $p$ with respect to $\pi$ is
defined as

${\displaystyle
H(p|\pi)\stackrel{{\scriptstyle\triangle}}{{=}}\int_{\mathbb{R}^{d}}\log\frac{p(x)}{\pi(x)}\pi(x)dx.}$
(3.1)

By definition, KL divergence can be considered as a measure of asymmetric
“distance” of a probability distribution $p$ from a base distribution $\pi$.
$H(p|\pi)$ is always nonnegative and equals zero only when $p$ equals $\pi$ in
distribution. KL divergence is a rather strong measure of distance, which
upper bounds a variety of distance measures. We provide the definition of
other measures in Appendix A. In general, convergence in KL divergence implies
convergence in total variation by Csiszar-Kullback-Pinsker inequality. In
addition, under log-Sobolev inequality with constant $\gamma$, KL divergence
also controls the quadratic Wasserstein $W_{2}$ distance by
$\mathcal{W}_{2}(p,\ \pi)^{2}\leq\frac{2}{\gamma}H(p|\pi).$

The Langevin dynamics for target distribution $\pi=e^{-U}$ is a continuous-
time stochastic process $(X_{t})_{t\geq 0}$ in $\mathbb{R}^{d}$ that
progresses following the stochastic differential equation:

$\displaystyle dX_{t}=-\nabla U(X_{t})\,dt+\sqrt{2}\,dW_{t}$ (3.2)

where $(W_{t})_{t\geq 0}$ is the standard Brownian motion in $\mathbb{R}^{d}$.

If $(X_{t})_{t\geq 0}$ updates following the Langevin dynamics (3.2), then
their probability density function $(p_{t})_{t\geq 0}$ will satisfy the
following the Fokker-Planck equation:

$\displaystyle\frac{\partial p_{t}}{t}\,=\,\nabla\cdot(p_{t}\nabla U)+\Delta
p_{t}\,=\,\nabla\cdot\left(p_{t}\nabla\log\frac{p_{t}}{\pi}\right).$ (3.3)

Here $\nabla\cdot$ is the divergence and $\Delta$ is the Laplacian operator.
In general, by evolving along the Langevin dynamics, a distribution will get
closer to its target distribution $\pi$. From [31] Lemma 1, we have

$\displaystyle\frac{d}{dt}(H(p_{t}|\pi))=-\mathbb{E}_{\pi}\left\|\nabla\log\frac{p_{t}}{\pi}\right\|^{2}.$
(3.4)

Since $\mathbb{E}_{\pi}\left\|\nabla\log\frac{p_{t}}{\pi}\right\|^{2}\geq 0$,
the identity (3.4) exhibits that KL divergence with respect to $\pi$ is
diminishing along the Langevin dynamics, thus the distribution $p_{t}$
actually converges to $\pi$. When $\pi$ fulfills log-Sobolev inequality (LSI),
[31] Lemma 2 shows that

$\displaystyle H(p_{t}|\pi)\leq e^{-2\gamma t}H(p_{0}|\pi).$ (3.5)

Hence, KL divergence converges exponentially fast along the Langevin dynamics.
Log-Sobolev inequality can be thought as a relaxation of logconcavity in
continuous time. LSI was originally initiated by [17] for the scenario of
Gaussian measure, characterizes concentration of measure and sub-Gaussian tail
property, to name a few. [2] broadened it to strongly log-concave measure,
where $\pi$ enjoys LSI with constant $\gamma$ whenever $-\log\pi$ is
$\gamma$-strongly convex. However, LSI is more general than strongly log-
concave condition since it is preserved under bounded perturbation [18],
Lipschitz mapping, tensorization, among others. Therefore, we will study the
KL convergence under log-Sobolev inequality.

###  3.2 Main result: KL divergence along Unadjusted Langevin Algorithm

In general, a practical algorithm often needs to be discretized [20] but the
discretization algorithms are often more complicated and require more
assumptions. In this section, we investigate the behavior of KL divergence
along the Unadjusted Langevin Algorithm (ULA) in discrete time. In order to
sample from a target distribution $\pi=e^{-U}$ in $\mathbb{R}^{d}$, the
updating rule for the discretized ULA algorithm with step size $\eta>0$ is
defined as

$\displaystyle x_{k+1}=x_{k}-\eta\nabla U(x_{k})+\sqrt{2\eta}\,z_{k}$ (3.6)

where $z_{k}\sim N(0,I)$ is an independent standard Gaussian random variable
in $\mathbb{R}^{d}$. As $x_{k}$ is updated following ULA, let $p_{k}$
represent its probability distribution. It is known that ULA converges to a
biased limiting distribution $\pi_{\eta}\neq\pi$ for any fixed $\eta>0$. Thus,
$H(p_{k}|\pi)$ does not converge to $0$ along ULA, as it has an asymptotic
bias $H(\pi_{\eta}|\pi)>0$. When the true target distribution $\pi$ complies
with an $\alpha$-mixture weakly smoothness and LSI, we can prove convergence
in KL divergence along ULA. A key observation is that ULA algorithm will
converge uniformly in time if the discretization error between the ULA output
in one iteration and the Langevin dynamics is bounded. This technique has been
used in many papers, [31, 8]. Our proof structure is similar to that of [31],
whose analysis needs stronger assumptions.

Let $x_{k+1}\sim p_{k+1}$ be the output of one step of ULA (3.6) from
$x_{k}\sim p_{k}$, we have

######  Lemma 3.1.

Suppose $\pi$ is $\gamma-$log-Sobolev, $\alpha$-mixture weakly smooth,
$\max\left\\{L_{i}\right\\}=L\geq 1$. If
$0<\eta\leq\left(\frac{\gamma}{9N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}$
and then along each step of ULA (3.6),

$\displaystyle H(p_{k+1}|\pi)\leq
e^{-\gamma\eta}H(p_{k}|\pi)+2\eta^{\alpha+1}D_{3},$ (3.7)

where

$D_{3}=\sum_{i}10N^{3}L^{6}+16NL^{4}+8N^{2}L^{4}d^{\frac{3}{p}}+4NL^{2}d.$
(3.8)

In particular, if$\pi$ is $\gamma$-log-Sobolev,
$\left(\alpha,\ell\right)$-weakly smooth with $0<\alpha+\ell\leq 1$. If
$0<\eta\leq\left(\frac{\gamma}{2L^{1+\alpha}}\right)^{\frac{1}{\alpha}}$, then
along each step of ULA (3.6),

$\displaystyle H(p_{k+1}|\pi)\leq
e^{-\gamma\eta}H(p_{k}|\pi)+2\eta^{\alpha+1}D_{3}^{\prime},$ (3.9)

where
$D_{3}^{\prime}=16L^{2+2\alpha+2\ell}+4L^{2+2\alpha}d^{\frac{3-\alpha}{1+\alpha}\left(\alpha+\ell\right)}+4L^{2}d^{\alpha+\ell}$.

###### Proof.

See Appendix C.3. ∎

By using this component, we obtain the following theorem.

######  Theorem 3.1.

Suppose $\pi$ is $\gamma-$log-Sobolev, $\alpha$-mixture weakly
smooth,$\max\left\\{L_{i}\right\\}=L\geq 1$, and for any $x_{0}\sim p_{0}$
with $H(p_{0}|\pi)=C_{0}<\infty$, the iterates $x_{k}\sim p_{k}$ of LMC with
step size $\eta\leq
1\wedge\frac{1}{4\gamma}\wedge\left(\frac{\gamma}{9N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}$satisfies

$\displaystyle H(p_{k}|\pi)\leq e^{-\gamma\eta
k}H(p_{0}|\pi)+\frac{8\eta^{\alpha}D_{3}}{3\gamma},$ (3.10)

Then, for any $\epsilon>0$, to achieve $H(p_{k}|\pi)<\epsilon$, it suffices to
run ULA with step size $\eta\leq
1\wedge\frac{1}{4\gamma}\wedge\left(\frac{\gamma}{9N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}\wedge\left(\frac{3\epsilon\gamma}{16D_{3}}\right)^{\frac{1}{\alpha}}$for
$k\geq\frac{1}{\gamma\eta}\log\frac{2H\left(p_{0}|\pi\right)}{\epsilon}$
iterations.

###### Proof.

See Appendix C.4. ∎

If we initialize with a Gaussian distribution $p_{0}=N(0,\frac{1}{L}I)$, we
have the following lemma.

######  Lemma 3.2.

Suppose $\pi=e^{-U}$ is $\alpha$-mixture weakly smooth. Let
$p_{0}=N(0,\frac{1}{L}I)$. Then $H(p_{0}|\pi)\leq
U(0)-\frac{d}{2}\log\frac{2\Pi
e}{L}+\sum_{i}\frac{L}{1+\alpha_{i}}\left(\frac{d}{L}\right)^{\frac{1+\alpha_{i}}{2}}=O(d).$

###### Proof.

See Appendix C.1. ∎

Therefore, Theorem 3.1 states that to achieve $H(p_{k}|\pi)\leq\epsilon$, ULA
has iteration complexity
$\tilde{O}\left(\frac{d^{\frac{3-\alpha}{1+\alpha}}}{\epsilon^{\frac{1}{\alpha}}\gamma^{\frac{1}{\alpha}+1}}\right).$
By Pinsker’s inequality, we have
$TV\left(p_{k}|\pi\right)\leq\sqrt{\frac{H(p_{k}|\pi)}{2}}$ which implies that
to get $TV\left(p_{k}|\pi\right)\leq\epsilon$, it is enough to obtain
$H(p_{k}|\pi)\leq 2\epsilon^{2}$. This bound indicates that the number of
iteration to reach $\epsilon$ accuracy for total variation is
$\tilde{O}\left(d^{\frac{3-\alpha}{1+\alpha}}\gamma^{\frac{-1}{\alpha}-1}\epsilon^{\frac{-2}{\alpha}}\right)$.
On the other hand, from Talagrand inequality, which comes from log-Sobolev
inequality, we know that $W_{2}^{2}(p_{k},\ \pi)\leq H\left(p_{k}|\pi\right)$,
by replacing this in the bound above, we obtain the number of iteration for
$L_{2}$-Wasserstein distance is
$\tilde{O}\left(d^{\frac{3-\alpha}{1+\alpha}}\gamma^{\frac{-1}{\alpha}-1}\epsilon^{\frac{-2}{\alpha}}\right)$.

###  3.3 Sampling via smoothing potential

Inspired by the approach of [6], we study the convergence of the discrete-time
process for the smoothing potential that have the following form:

$U_{\mu}(x):=\mathrm{\mathbb{E}}_{\xi}[U(y+\mu\xi)].$ (3.11)

Observe from Lemma 2.2 that $U(\cdot)$ is $\alpha$-mixture weakly smooth but
$U_{\mu}(x)$ is smooth. Recall that ULA in terms of the smoothing potential
$U_{\mu}$ can be specified as:

$x_{k+1}=x_{k}-\eta\nabla U_{\mu}(x_{k})+\sqrt{2\eta}\varsigma_{k},$ (3.12)

where $\varsigma_{k}\sim N(0,\ I_{d\times d})$ are independent Gaussian random
vectors. In general, we do not have access to an oracle of $\nabla
U_{\mu}(x)$, so rather than working with $\nabla U_{\mu}(x)$ as specified by
Eq. 3.12, we need to use an estimate of the gradient:

$\displaystyle g_{\mu}(x)=\nabla U(x+\mu\xi)$ (3.13)

where $\xi\sim N_{p}(0,I_{d})$. Based on the above estimate of the gradient,
we obtain the following result.

######  Lemma 3.3.

For any $x_{k}\in\mathbb{R}^{d}$, $g_{\mu}(x_{k},\zeta_{k})=\nabla
U_{\mu}(x_{k})+\zeta_{k}$ is an unbiased estimator of $\nabla U_{\mu}$ such
that

$\displaystyle\mathrm{Var}\left[g_{\mu}(x_{k},\zeta_{k})\right]\leq
4N^{2}L^{2}\mu^{2\alpha}d^{\frac{2\alpha}{p}}.$

###### Proof.

See Appendix D.1. ∎

Let the distribution of the $k^{th}$ iterate $x_{k}$ be represented by
$\pi_{\mu,k}$, and let $\pi_{\mu}\propto\exp(-U_{\mu})$ be the distribution
with $U_{\mu}$ as the potential. First, we prove that the $p$-generalized
Gaussian smoothing does not alter the objective distribution substantially in
term of the Wasserstein distance, by bounding $W_{2}(\pi,\pi_{\mu})$.

######  Lemma 3.4.

Assume that $\pi\propto\exp(-\pi)$ and $\pi_{\mu}\propto\exp(-U_{\mu})$ and
$\pi$ has a bounded second moment, that is
$\int\left\|x\right\|^{2}\pi(x)dx=E_{2}<\infty$. We deduce the following
bounds

$W_{2}^{2}(\pi,\ \pi_{\mu})\leq 8.24NL\mu^{1+\alpha}d^{\frac{2}{p}}E_{2}.$

for any $\mu\leq 0.05$.

###### Proof.

See Appendix D.3. ∎

We then derive a result on mixing times of Langevin diffusion with stochastic
estimated gradients under log-Sobolev inequality condition, which enables us
to bound $W_{2}(\pi_{\mu,k},\pi_{\mu})$. Our main outcome is stated in the
subsequent theorem.

######  Theorem 3.2.

Suppose $\pi_{\mu}$ is $\gamma_{1}-$log-Sobolev, $\alpha$-mixture weakly
smooth, with $\max\left\\{L_{i}\right\\}=L\geq 1$ and
$\int\left\|x\right\|^{2}\pi(x)dx=E_{2}<\infty$ and for any $x_{0}\sim p_{0}$
with $H(p_{0}|\pi)=C_{0}<\infty$, the iterates $x_{k}\sim p_{k}$ of ULA with
step size

$\eta\leq\min\left\\{1,\frac{1}{4\gamma},\left(\frac{\gamma_{1}}{13N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}\right\\}$
(3.14)

satisfies

$\displaystyle W_{2}(\pi_{\mu,K},\pi)\leq e^{-\frac{\gamma_{1}}{2}\eta
k}\sqrt{H(p_{0}|\pi_{\mu})}+\sqrt{\frac{8\eta^{\alpha}D_{4}}{3\gamma_{1}}}+3\sqrt{NLE_{2}}d^{\frac{1}{p}}\eta^{\frac{\alpha}{2}},$

where
$D_{4}=\sum_{i}10N^{3}L^{6}+16NL^{4}+8N^{2}L^{4}d^{\frac{3}{p}}+4NL^{2}d+8N^{2}L^{2}d^{\frac{2\alpha}{p}}$.

Then, for any $\epsilon>0$, to achieve $W_{2}(\pi_{\mu,K},\pi)<\epsilon$, it
suffices to run ULA with step size $\eta\leq
1\wedge\frac{1}{4\gamma_{1}}\wedge\left(\frac{\gamma}{13N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}\wedge\left(\frac{\epsilon\gamma_{1}}{6\sqrt{D_{4}}}\right)^{\frac{2}{\alpha}}\wedge\left(\frac{\epsilon}{9\sqrt{NLE_{2}}d^{\frac{1}{p}}}\right)^{\frac{2}{\alpha}}$for
$k\geq\frac{2}{\gamma_{1}\eta}\log\frac{3\sqrt{H\left(p_{0}|\pi\right)\gamma_{1}}}{\epsilon}$
iterations.

###### Proof.

See Appendix D.2. ∎

##  4 Extended result

Since log-Sobolev inequalities are preserved under bounded perturbations by
[18]’s theorem, we provide our extended results through convexification of
non-convex domain [24, 35]. Convexification of non-convex domain is an
original approach proposed by [24, 35], developed and apply to strongly convex
outside a compact set by [35]. We would like to emphasize that it is non
trivial to apply their results in our case since the requirement of strong
convexity. Before starting our extension, we need an additional lemma, taken
from [24, 35], for our proof.

######  Lemma 4.1.

[[24] Lemma 2]. Let us define $\Omega=\mathbb{R}^{d}\backslash\mathbb{B}(0,R)$
where $\mathbb{B}(0,R)$ is the open ball of radius $R$ centered at $0$, and
define $V\left(x\right)=\inf\left\\{\sum_{i}\lambda_{i}U(\ x_{i})\right\\}$
where the infimum is running over all possible convex combination of points
$x_{i}$ (that is $\lambda_{i}\geq 0$, $\sum_{i}\lambda_{i}=1$ and
$\sum_{i}\lambda_{i}x_{i}=x$). Then for $\forall\ x\in\mathbb{B}(0,R)$, $V(\
x)$ can be represented as a convex combination of $U\left(x_{j}\right)$ such
that $\left\|x_{j}\right\|=R,$ that is
$V\left(x\right)=\inf\left\\{\sum_{j}\lambda_{j}U(\ x_{j})\right\\}$ where
$\lambda_{j}\geq 0$, $\sum_{j}\lambda_{j}=1$ and $\sum_{j}\lambda_{j}x_{j}=x$
and $\left\|x_{j}\right\|=R.$ Then,
$\inf_{\left\|\bar{x}\right\|=R}U(\bar{x})\leq V(\
x)\leq\sup_{\left\|\bar{x}\right\|=R}U(\bar{x}).$

###### Proof.

See Appendix E.1. ∎

Adapted techniques from [24] for non-strongly convex and $\alpha$-mixture
weakly smooth potentials, we derive a tighter bound for the difference between
constructed convex potential and the original one in the following lemma.

######  Lemma 4.2.

For $U$ satisfying $\alpha$-mixture weakly smooth and
$\left(\mu,\theta\right)$-degenerated convex outside the ball radius $R$,
there exists $\hat{U}\in C^{1}(\mathbb{R}^{d})$ with a Hessian that exists
everywhere on $\mathbb{R}^{d}$, and $\hat{U}$ is
$\left(\left(1-\theta\right)\frac{\mu}{2},\theta\right)$-degenerated convex on
$\mathbb{R}^{d}$ (that is
$\nabla^{2}\hat{U}(x)\succeq\left(1-\theta\right)\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}I_{d}$),
such that

$\displaystyle\sup\left(\hat{U}(\ x)-U(\ x)\right)$
$\displaystyle-\inf\left(\hat{U}(\ x)-U(\
x)\right)\leq\sum_{i}L_{i}R^{1+\alpha_{i}}+\frac{4\mu}{\left(2-\theta\right)}\
R^{2-\theta}.$ (4.1)

###### Proof.

See Appendix E.2. ∎

######  Remark 4.1.

This result can be applied to potential with degenerated convex outside the
ball. Setting $\mu=0$ implies a result for potential with non-strongly convex
outside the ball, while setting $\theta=0$ implies a result for potential with
strongly convex outside the ball. The constant could be improved by a factor
of $2$ if we take $\epsilon$ defined in the proof to be arbitrarily small.

###  4.1 ULA convergence under $\gamma-$Poincaré inequality, $\alpha$-mixture
weakly smooth and $2-$dissipativity

In general, $PI$ is weaker than $LSI$. In order to apply the previous results
of log Sobolev inequalities, we will also need $2-$dissipativity assumption.
First, using convexification of non-convex domain result above, we have the
following lemma for bounded perturbation.

######  Lemma 4.3.

For $U$ satisfying $\gamma-$Poincaré, $\alpha$-mixture weakly smooth, there
exists $\breve{U}\in C^{1}(\mathbb{R}^{d})$ with a Hessian that exists
everywhere on $\mathbb{R}^{d}$, and $\breve{U}$ is log-Sobolev on
$\mathbb{R}^{d}$ such that

$\sup\left(\breve{U}(\ x)-U(\ x)\right)-\inf\left(\breve{U}(\ x)-U(\
x)\right)\leq 2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}.$
(4.2)

###### Proof.

See Appendix E.3. ∎

Using bounded perturbation theorem, this result implies $\pi$ satisfies a log-
Sobolev inequality, which in turn give us the following result.

######  Theorem 4.1.

Suppose $\pi$ is $\gamma-$Poincaré, $\alpha$-mixture weakly smooth with
$\alpha_{N}=1$ and $2-$dissipativity (i.e.$\left\langle\nabla
U(x),x\right\rangle\geq a\left\|x\right\|^{2}-b$) for some $a,b>0$, and for
any $x_{0}\sim p_{0}$ with $H(p_{0}|\pi)=C_{0}<\infty$, the iterates
$x_{k}\sim p_{k}$ of ULA with step size $\eta\leq
1\wedge\frac{1}{4\gamma_{3}}\wedge\left(\frac{\gamma_{3}}{16L^{1+\alpha}}\right)^{\frac{1}{\alpha}}$satisfies

$\displaystyle H(p_{k}|\pi)\leq e^{-\gamma_{3}\eta
k}H(p_{0}|\pi)+\frac{8\eta^{\alpha}D_{3}}{3\gamma_{3}},$ (4.3)

where $D_{3}$ is defined as in equation (3.8) and

$\displaystyle M_{2}$
$\displaystyle=\int\left\|x\right\|^{2}e^{-\breve{U}(x)}dx=O(d)$ (4.4)
$\displaystyle\zeta$
$\displaystyle=\sqrt{2\left[\frac{2\left(b+\left(L+\frac{\lambda_{0}}{2}\right)R^{2}+aR^{2}+d\right)}{a}+M_{2}\right]\frac{e^{4\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)}}{\gamma}}$
(4.5) $\displaystyle A$ $\displaystyle=(1-\frac{L}{2})\frac{8}{a^{2}}+\zeta,$
(4.6) $\displaystyle B$
$\displaystyle=2\left[\frac{2\left(\left(b+4\left(L+\frac{\lambda_{0}}{4}\right)R^{2}+aR^{2}\right)+d\right)}{a}+M_{2}\right](1-\frac{L}{2}+\frac{1}{\zeta}),$
(4.7) $\displaystyle\gamma_{3}$ $\displaystyle=\frac{2\gamma
e^{-\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)}}{[A\gamma+(B+2)e^{4\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)})]}.$

Then, for any $\epsilon>0$, to achieve $H(p_{k}|\pi)<\epsilon$, it suffices to
run ULA with step size $\eta\leq
1\wedge\frac{1}{4\gamma_{3}}\wedge\left(\frac{\gamma_{3}}{16L^{1+\alpha}}\right)^{\frac{1}{\alpha}}\wedge\left(\frac{3\epsilon\gamma_{3}}{16D_{3}}\right)^{\frac{1}{\alpha}}$for
$k\geq\frac{1}{\gamma_{3}\eta}\log\frac{2H\left(p_{0}|\pi\right)}{\epsilon}$
iterations.

###### Proof.

See Appendix E.5. ∎

From Theorem 4.1, LMC can achieve $H(p_{k}|\pi)\leq\epsilon$, with iteration
complexity of
$\tilde{O}\left(\frac{d^{\frac{1}{\alpha}}}{\epsilon^{\frac{1}{\alpha}}\gamma_{3}^{\frac{1}{\alpha}+1}}\right)$
where

$\displaystyle\gamma_{3}$ $\displaystyle=O\left(\frac{1}{d\gamma
e^{5\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)}}\right)$

so the number of iteration needed is

$\tilde{O}\left(\frac{d^{\frac{2}{\alpha}+1}e^{5\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)\left(\frac{1}{\alpha}+1\right)}}{\gamma_{3}^{\left(\frac{1}{\alpha}+1\right)}\epsilon^{\frac{1}{\alpha}}}\right).$

Similar as before, from Pinsker’s inequality, the number of iteration to reach
$\epsilon$ accuracy for total variation is

$\tilde{O}\left(\frac{d^{\frac{2}{\alpha}+1}e^{5\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)\left(\frac{1}{\alpha}+1\right)}}{\gamma_{3}^{\left(\frac{1}{\alpha}+1\right)}\epsilon^{\frac{2}{\alpha}}}\right).$
(4.8)

To have ${W}_{\alpha}(p_{k},\ \pi)\leq\epsilon$, it is sufficient to choose
$\mathrm{H}(p_{k}|\pi)=\tilde{O}\left(\epsilon^{4}d^{-2}\right)$, which in
turn implies the number of iteration for ${W}_{\alpha}(p_{k},\
\pi)\leq\epsilon$ is

$\tilde{O}\left(\frac{d^{\frac{4}{\alpha}+1}e^{5\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)\left(\frac{1}{\alpha}+1\right)}}{\gamma_{3}^{\left(\frac{1}{\alpha}+1\right)}\epsilon^{\frac{4}{\alpha}}}\right).$
(4.9)

###  4.2 ULA convergence under non-strongly convex outside the ball,
$\alpha$-mixture weakly smooth and $2-$dissipativity

Using convexification of non-convex domain result above, we obtain the
following lemma.

######  Lemma 4.4.

Suppose $\pi$ is non-strongly convex outside the ball of radius $R$,
$\alpha$-mixture weakly smooth with $\alpha_{N}=1$ and $2-$dissipativity
(i.e.$\left\langle\nabla U(x),x\right\rangle\geq a\left\|x\right\|^{2}-b$) for
some $a,b>0$, there exists $\breve{U}\in C^{1}(\mathbb{R}^{d})$ with a Hessian
that exists everywhere on $\mathbb{R}^{d}$, and $\breve{U}$ is convex on
$\mathbb{R}^{d}$ such that

$\sup\left(\breve{U}(\ x)-U(\ x)\right)-\inf\left(\breve{U}(\ x)-U(\
x)\right)\leq 2\sum_{i}L_{i}R^{1+\alpha_{i}}.$ (4.10)

###### Proof.

It comes directly from Lemma 4.2. ∎

Based on result in previous section, we get the following result.

######  Theorem 4.2.

Suppose $\pi$ is non-strongly convex outside the ball $\mathbb{B}(0,R)$,
$\alpha$-mixture weakly smooth with $\alpha_{N}=1$ and $2-$dissipativity
(i.e.$\left\langle\nabla U(x),x\right\rangle\geq a\left\|x\right\|^{2}-b$) for
some $a,b>0$, and for any $x_{0}\sim p_{0}$ with $H(p_{0}|\pi)=C_{0}<\infty$,
the iterates $x_{k}\sim p_{k}$ of LMC with step size $\eta\leq
1\wedge\frac{1}{4\gamma_{3}}\wedge\left(\frac{\gamma_{3}}{16L^{1+\alpha}}\right)^{\frac{1}{\alpha}}$satisfies

$\displaystyle H(p_{k}|\pi)\leq e^{-\gamma_{3}\eta
k}H(p_{0}|\pi)+\frac{8\eta^{\alpha}D_{3}}{3\gamma_{3}},$ (4.11)

where $D_{3}$ is defined as in equation (3.8) and for some universal constant
$K$,

$\displaystyle M_{2}$
$\displaystyle=\int\left\|x\right\|^{2}e^{-\breve{U}(x)}dx=O(d)$ (4.12)
$\displaystyle\zeta$
$\displaystyle=K\sqrt{64d\left[\frac{2\left(b+\left(L+\frac{\lambda_{0}}{2}\right)R^{2}+aR^{2}+d\right)}{a}+M_{2}\right]\left(\frac{a+b+2aR^{2}+3}{ae^{-4\left(4L_{N}R^{2}+4LR^{1+\alpha}\right)}}\right)}$
(4.13) $\displaystyle A$ $\displaystyle=(1-\frac{L}{2})\frac{8}{a^{2}}+\zeta,$
(4.14) $\displaystyle B$
$\displaystyle=2\left[\frac{2\left(\left(b+4\left(L+\frac{\lambda_{0}}{4}\right)R^{2}+aR^{2}\right)+d\right)}{a}+M_{2}\right](1-\frac{L}{2}+\frac{1}{\zeta}),$
(4.15) $\displaystyle\gamma_{3}$
$\displaystyle=\frac{2e^{-\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)}}{A+(B+2)32K^{2}d\left(\frac{a+b+2aR^{2}+3}{a}\right)e^{4\left(4L_{N}R^{2}+4LR^{1+\alpha}\right)}}=\frac{1}{O(d)}.$

Then, for any $\epsilon>0$, to achieve $H(p_{k}|\pi)<\epsilon$, it suffices to
run ULA with step size $\eta\leq
1\wedge\frac{1}{4\gamma_{3}}\wedge\left(\frac{\gamma_{3}}{16L^{1+\alpha}}\right)^{\frac{1}{\alpha}}\wedge\left(\frac{3\epsilon\gamma_{3}}{16D_{3}}\right)^{\frac{1}{\alpha}}$for
$k\geq\frac{1}{\gamma_{3}\eta}\log\frac{2H\left(p_{0}|\pi\right)}{\epsilon}$
iterations.

###### Proof.

See Appendix E.5 . ∎

##  5 Conclusion

In this article, we derive polynomial-dimension theoretical assurances of
unadjusted LMC algorithm for a family of potentials that are $\alpha$-mixture
weakly smooth and isoperimetric (i.e. log Sobolev, Poincaré, and Talagrand).
In addition, we also investigate the family of potential which is non-strongly
convex outside the ball and $2$-dissipative. The analysis we proposed is an
extension of the recently published paper [31] in combination with the
convexification of non-convex domain [24]. There are a number of valuable
potential directions which one can explore, among them we speculate some here.
It is potential to broaden our results to apply underdamped LMC or higher
order LMC to these class of potential while the computational complexity
remains polynomial dependence on $d$. Another fascinating question is whether
it is feasible to sampling from distributions with non-smooth and totally non-
convex structure and integrate into derivative-free LMC algorithm.

##  Appendix A Measure definitions and isoperimetry

Let $p,\pi$ be probability distributions on $\mathbb{R}^{d}$ with full support
and smooth densities, define the Kullback-Leibler (KL) divergence of $p$ with
respect to $\pi$ as

$H(p|\pi)\stackrel{{\scriptstyle\triangle}}{{=}}\int_{{R}^{d}}p(x)\log\frac{p(x)}{\pi(x)}\,dx.$
(A.1)

Likewise, we denote the entropy of $p$ with

${\displaystyle\mathrm{H}(p)\stackrel{{\scriptstyle\triangle}}{{=}}-\int
p(x)\log p(x)dx}$ (A.2)

and for $\mathcal{B}(\mathbb{R}^{d})$ denotes the Borel $\sigma$-field of
$\mathbb{R}^{d}$, define the relative Fisher information and total variation
metrics correspondingly as

${\displaystyle\mathrm{I}(p|\pi)\stackrel{{\scriptstyle\triangle}}{{=}}\int_{\mathbb{R}^{d}}p(x)\|\nabla\log\frac{p(x)}{\pi(x)}\|^{2}dx},$
(A.3) ${\displaystyle TV(p,{\displaystyle\
\pi)\stackrel{{\scriptstyle\triangle}}{{=}}\sup_{A\in\mathcal{B}(\mathbb{R}^{d})}|\int_{A}p(x)dx-\int_{A}\pi(x)dx|}.}$
(A.4)

Furthermore, we define a transference plan $\zeta$, a distribution on
$(\mathbb{R}^{d}\times\mathbb{R}^{d},\
\mathcal{B}(\mathbb{R}^{d}\times\mathbb{R}^{d}))$ (where
$\mathcal{B}(\mathbb{R}^{d}\times\mathbb{R}^{d})$ is the Borel $\sigma$-field
of ($\mathbb{R}^{d}\times\mathbb{R}^{d}$)) so that
$\zeta(A\times\mathbb{R}^{d})=p(A)$ and $\zeta(\mathbb{R}^{d}\times A)=\pi(A)$
for any $A\in\mathcal{B}(\mathbb{R}^{d})$. Let $\Gamma(P,\ Q)$ designate the
set of all such transference plans. Then for $\beta>0$, the
$L_{\beta}$-Wasserstein distance is formulated as:

$W_{\beta}(p,\pi)\stackrel{{\scriptstyle\triangle}}{{=}}\left(\inf_{\zeta\in\Gamma(P,Q)}\int_{x,y\in\mathbb{R}^{d}}\|x-y\|^{\beta}\mathrm{d}\zeta(x,\
y)\right)^{1/\beta}.$ (A.5)

Note that although KL divergence is an asymmetric measure of distance between
probability distributions, it is the preferred measure of distance here since
it also implies total variation distance via Pinsker’s inequality. In
addition, KL divergence also governs the quadratic Wasserstein $W_{2}$
distance under log-Sobolev, Talagrand, and Poincaré inequalities defined
below.

######  Definition A.1.

The probability distribution $p$ satisfies a logarithmic Sobolev inequality
with constant $\gamma>0$ (in short: $LSI(\gamma)$) if for all probability
distribution $p$ absolutely continuous $w.r.t.\ \pi$,

$H({\displaystyle p|\pi)\leq\frac{1}{2\gamma}I(p|\pi)}.$ (A.6)

######  Definition A.2.

The probability distribution $p$ satisfies a Talagrand inequality with
constant $\gamma>0$ (in short: $T(\gamma)$) if for all probability
distribution $p$, absolutely continuous $w.r.t.\ \pi$, with finite moments of
order 2,

$W_{2}(p,\ \pi)\leq\sqrt{\frac{2H(p|\pi)}{\gamma}}.$ (A.7)

######  Definition A.3.

The probability distribution $p$ satisfies a Poincaré inequality with constant
$\gamma>0$ (in short: $PI(\gamma)$) if for all smooth function
$g\colon\mathbb{R}^{d}\to\mathbb{R}$,

$Var_{p}(g)\leq\frac{1}{\gamma}E_{p}[\|\nabla g\|^{2}],$ (A.8)

where $Var_{p}(g)=E_{p}[g^{2}]-E_{p}[g]^{2}$ is the variance of $g$ under $p$.

##  Appendix B Proofs of $p$-generalized Gaussian smoothing

###  B.1 Proof of $\alpha$-mixture weakly smooth property

######  Lemma B.1.

If potential $U:\mathbb{R}^{d}\rightarrow\mathbb{R}$ satisfies
$\alpha$-mixture weakly smooth then:

$U(y)\leq U(x)+\left\langle\nabla U(x),\
y-x\right\rangle+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\|y-x\|^{1+\alpha_{i}}.$

In particular, if potential $U:\mathbb{R}^{d}\rightarrow\mathbb{R}$ satisfies
$\left(\alpha,\ell\right)-$weakly smooth for some $\alpha+\ell\leq 1$ and
$\alpha\in[0,1]$, then:

$U(y)\leq U(x)+\left\langle\nabla U(x),\
y-x\right\rangle+\frac{L}{1+\alpha}\|y-x\|^{1+\alpha}+\frac{L}{1+\ell+\alpha}\|y-x\|^{1+\ell+\alpha}.$

###### Proof.

We have

$\displaystyle\left|U(x)-U(y)-\langle\nabla U(y),x-y\rangle\right|$
$\displaystyle=$ $\displaystyle\Big{|}\int_{0}^{1}\langle\nabla
U(y+t(x-y)),x-y\rangle\text{d}t-\langle\nabla U(y),x-y\rangle\Big{|}$
$\displaystyle=$ $\displaystyle\Big{|}\int_{0}^{1}\langle\nabla
U(y+t(x-y))-\nabla U(y),x-y\rangle\text{d}t\Big{|}.$ $\displaystyle\leq$
$\displaystyle\int_{0}^{1}\|\nabla U(y+t(x-y))-\nabla U(y)\|\|x-y\|\text{d}t$
$\displaystyle\leq$
$\displaystyle\int_{0}^{1}\sum_{i}L_{i}t^{\alpha_{i}}\|x-y\|^{\alpha_{i}}\|x-y\|\text{d}t$
$\displaystyle=$
$\displaystyle\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\|x-y\|^{1+\alpha_{i}},$

where the first line comes from Taylor expansion, the third line follows from
Cauchy-Schwarz inequality and the fourth line is due to Assumption 2.1. This
gives us the desired result. By replacing Assumption 2.1 with Assumption 2.2,
we immediately get

$U(y)\leq U(x)+\left\langle\nabla U(x),\
y-x\right\rangle+\frac{L}{1+\alpha}\|y-x\|^{1+\alpha}+\frac{L}{1+\ell+\alpha}\|y-x\|^{1+\ell+\alpha}.$

∎

###  B.2 Proof of $p$-generalized Gaussian smoothing properties

######  Lemma B.2.

If potential $U:\mathbb{R}^{d}\rightarrow\mathbb{R}$ satisfies
$\alpha$-mixture weakly smooth then:

(i) $\forall x\in\mathbb{R}^{d}$ :
$\left|U_{\mu}(x)-U(x)\right|{\displaystyle\leq\sum_{i}L_{i}\mu^{1+\alpha_{i}}d^{\frac{1+\alpha_{i}}{p}},}$

(ii) $\forall x\in\mathbb{R}^{d}$: ${\displaystyle\left\|\nabla
U_{\mu}(x)-\nabla
U(x)\right\|\leq\sum_{i}L_{i}\mu^{\alpha_{i}}d^{\frac{3}{p}}},$

(iii) $\forall x,\ y\in\mathbb{R}^{d}$: ${\displaystyle\left\|\nabla
U_{\mu}(y)-\nabla
U_{\mu}(x)\right\|\leq\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2}{p}}\left\|y-x\right\|.}$

In particular, if the potential $U:\mathbb{R}^{d}\rightarrow\mathbb{R}$
satisfies $\left(\alpha,\ell\right)-$weakly smooth for some $\alpha+\ell\leq
1$ and $\alpha\in[0,1]$, then:

(i) $\forall x\in\mathbb{R}^{d}$ :
$\left|U_{\mu}(x)-U(x)\right|{\displaystyle\leq
2L\mu^{1+\ell+\alpha}d^{\frac{1+\ell+\alpha}{p}},}$

(ii) $\forall x\in\mathbb{R}^{d}$: ${\displaystyle\left\|\nabla
U_{\mu}(x)-\nabla U(x)\right\|\leq 2L\mu^{\alpha}d^{\frac{3}{p}}},$

(iii) $\forall x,\ y\in\mathbb{R}^{d}$: ${\displaystyle\left\|\nabla
U_{\mu}(y)-\nabla
U_{\mu}(x)\right\|\leq\frac{L}{\mu^{1-\alpha}}d^{\frac{2}{p}}\left\|y-x\right\|.}$

###### Proof.

(i). Since $U_{\mu}(x)=\mathrm{\mathbb{E}}_{\xi}[U(x+\mu\xi)]$,
$U(x)=\mathrm{\mathbb{E}}_{\xi}[U(x)]$ and
$\mathbb{E}_{\xi}\mu\left\langle\nabla U(x),\ \xi\right\rangle=0$, we have

$U_{\mu}(x)-U(x)=\mathbb{E}_{\xi}\left[U(x+\mu\xi)-U(x)-\mu\left\langle\nabla
U(x),\ \xi\right\rangle\right].$

By the definition of the density of $p$-generalized Gaussian distribution [1],
we also have:

$U_{\mu}(x)-U(x)=\frac{1}{\kappa}\int_{\mathbb{R}^{d}}[U(x+\mu\xi)-U(x)-\mu\left\langle\nabla
U(x),\ \xi\right\rangle]e^{-\left\|\xi\right\|_{p}^{p}/p}d\xi.$

Applying Eq. 2.2 and previous inequality:

$\displaystyle|U_{\mu}(x)-U(x)|$
$\displaystyle=\left|\frac{1}{\kappa}\int_{\mathbb{R}^{d}}\left[U(x+\mu\xi)-U(x)-\mu\left\langle\nabla
U(x),\ \xi\right\rangle\right]e^{-\left\|\xi\right\|_{p}^{p}/p}d\xi\right|$
$\displaystyle\leq\sum_{i}\frac{L_{i}}{\kappa(1+\alpha_{i})}\mu^{1+\alpha_{i}}\int_{\mathbb{R}^{d}}\left\|\xi\right\|^{(1+\alpha_{i})}e^{-\left\|\xi\right\|_{p}^{p}/p}d\xi$
$\displaystyle=\sum_{i}\frac{L_{i}\mu^{1+\alpha_{i}}}{(1+\alpha_{i})}E\left[\left\|\xi\right\|^{(1+\alpha_{i})}\right].$

If $p\leq 2$ then $\left\|\xi\right\|\leq\left\|\xi\right\|_{p}$ and we get

$\displaystyle|U_{\mu}(x)-U(x)|$
$\displaystyle\leq\sum_{i}\frac{L_{i}\mu^{1+\alpha_{i}}}{(1+\alpha_{i})}E\left[\left\|\xi\right\|^{(1+\alpha_{i})}\right]$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}\sum_{i}\frac{L_{i}\mu^{1+\alpha_{i}}}{(1+\alpha_{i})}\mathbb{E}\left[\left\|\xi\right\|_{p}^{2}\right]^{\frac{1+\alpha_{i}}{2}}$
$\displaystyle\stackrel{{{}_{2}}}{{\leq}}\sum_{i}\frac{L_{i}\mu^{1+\alpha_{i}}}{(1+\alpha_{i})}\left(\left(d+1\right)^{\frac{2}{p}}\right)^{\frac{1+\alpha_{i}}{2}}$
$\displaystyle\leq\sum_{i}\frac{L_{i}\mu^{1+\alpha_{i}}}{(1+\alpha_{i})}d^{\frac{1+\alpha_{i}}{p}}$
$\displaystyle\leq\sum_{i}\frac{L_{i}\mu^{1+\alpha_{i}}}{(1+\alpha_{i})}d^{\frac{2}{p}}$

where step $1$ follows from Jensen inequality and $0\leq\alpha\leq 1$, step
$2$ is from Lemma F.16 below in which if $\xi\sim N_{p}\left(0,I_{d}\right)$
then $d^{\left\lfloor\frac{n}{p}\right\rfloor}\leq
E(\left\|\xi\right\|_{p}^{n})\leq\left[d+\frac{n}{2}\right]^{\frac{n}{p}}$where$\left\lfloor
x\right\rfloor$ denotes the largest integer less than or equal to $x$, and the
last step is by simplification when $d$ is large enough and $\mu$ is small
enough. By replacing Assumption 2.1 with Assumption 2.2, for $\mu$ is small
enough, we immediately get

$\left|U_{\mu}(x)-U(x)\right|{\displaystyle\leq
2L\mu^{1+\ell+\alpha}d^{\frac{1+\ell+\alpha}{p}}.}$

(ii). We adapt the technique of [27] to $p$-generalized Gaussian smoothing.
Let $y=x+\mu\xi$, then $U_{\mu}(x)$ is rewritten in another form as

$\displaystyle U_{\mu}(x)$
$\displaystyle=\mathrm{\mathbb{E}}_{\xi}[U(x+\mu\xi)]$
$\displaystyle=\frac{1}{\kappa\mu}\int_{\mathbb{R}^{d}}U(y)e^{-\frac{1}{p\mu^{p}}\left\|y-x\right\|_{p}^{p}}dy.$

Now taking the gradient with respect to $x$ of $U_{\mu}(x)$ gives

$\nabla_{x}U_{\mu}(x)=\frac{1}{\kappa\mu}\nabla_{x}\int_{\mathbb{R}^{d}}U(y)e^{-\frac{1}{p\mu^{p}}\left\|y-x\right\|_{p}^{p}}dy.$

By Fubini Theorem with some regularity (i.e. $\mathbb{E}|U(y)|<\infty$), we
can exchange the gradient and integral and get

$\displaystyle\nabla_{x}U_{\mu}(x)$
$\displaystyle=\frac{1}{\kappa\mu}\int_{\mathbb{R}^{d}}\nabla_{x}\left(U(y)e^{-\frac{1}{p\mu^{p}}\left\|y-x\right\|_{p}^{p}}\right)dy$
$\displaystyle=\frac{1}{\kappa\mu}\int_{\mathbb{R}^{d}}U(y)\nabla_{x}\left(e^{-\frac{1}{p\mu^{p}}\left\|y-x\right\|_{p}^{p}}\right)dy$
$\displaystyle=\frac{1}{\kappa\mu}\int_{\mathbb{R}^{d}}U(y)e^{-\frac{1}{p\mu^{p}}\left\|y-x\right\|_{p}^{p}}\frac{-1}{\mu^{p}}\left\|y-x\right\|_{p}^{p}\nabla_{x}(\left\|y-x\right\|_{p})dy$
$\displaystyle=\frac{1}{\kappa\mu}\int_{\mathbb{R}^{d}}U(y)e^{-\frac{1}{p\mu^{p}}\left\|y-x\right\|_{p}^{p}}\frac{1}{\mu^{p}}(y-x)\circ\left|y-x\right|^{p-2}dy.$

where $\circ$ stands for the Hadamard product and $\left|\cdot\right|$ is used
for absolute value of each component of the vector $y-x$. Therefore, by
changing variable back to $\xi$, we deduce

$\displaystyle\nabla_{x}U_{\mu}(x)$
$\displaystyle=\frac{1}{\kappa}\int_{\mathbb{R}^{d}}U(x+\mu\xi)e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\frac{1}{\mu}\xi\circ\left|\xi\right|^{p-2}d\xi$
$\displaystyle=\mathbb{E}_{\xi}\left[\frac{U(x+\mu\xi)\xi\circ\left|\xi\right|^{p-2}}{\mu}\right].$

In addition, if $\xi\sim N_{p}(0,I_{d})$,
$\mathbb{E}\left(\xi\right)=\frac{1}{\kappa}\int\xi
e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi=0$ and then
$\nabla_{\xi}\mathbb{E}\left(\xi\right)=0$. Since $\xi
e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}$ is bounded, we can exchange the
gradient and the integral and get

$\displaystyle\nabla_{\xi}\frac{1}{\kappa}\int\xi
e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi$
$\displaystyle=\frac{1}{\kappa}\int\nabla_{\xi}\left(\xi
e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\right)d\xi$ $\displaystyle 0$
$\displaystyle=\frac{1}{\kappa}\int
e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi+\frac{1}{\kappa}\int\xi\nabla_{\xi}\left(e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\right)d\xi$
$\displaystyle 0$
$\displaystyle=1-\frac{1}{\kappa}\int\xi\mathrm{e}^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\left\|\xi\right\|_{p}^{p-1}\nabla_{\xi}\left(\left\|\xi\right\|_{p}\right)d\xi$
$\displaystyle 0$
$\displaystyle=1-\frac{1}{\kappa}\int\xi\cdot\xi\circ\left|\xi\right|^{p-2}e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi,$

which implies

$\frac{1}{\kappa}\int\xi\cdot\xi\circ\left|\xi\right|^{p-2}e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi=1.$
(B.1)

On the other hand, we also have $\frac{1}{\kappa}\int
e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi=1$ so $\nabla_{\xi}\int
e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi=0.$ By exchange the gradient
and the integral and we also get

$\displaystyle 0$ $\displaystyle=\nabla_{\xi}\int
e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi$
$\displaystyle=\int\nabla_{\xi}e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi$
$\displaystyle=\int\nabla_{\xi}\left(e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\right)d\xi$
$\displaystyle=-\int
e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\xi\circ\left|\xi\right|^{p-2}d\xi$

which implies that

$\mathbb{E}_{\xi}\left[\xi\circ\left|\xi\right|^{p-2}\right]=0.$ (B.2)

From B.1 and B.2, we obtain

$\displaystyle\left\|\nabla U_{\mu}(x)-\nabla U(x)\right\|$
$\displaystyle=\left\|\frac{1}{\kappa}\int_{\mathbb{R}^{d}}\left[\frac{U(x+\mu\xi)-U(x)}{\mu}-\left\langle\nabla
U(x),\xi\right\rangle\right]\xi\circ\left|\xi\right|^{p-2}e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi\right\|$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}\frac{1}{\kappa\mu}\int_{\mathbb{R}^{d}}\left|U(x+\mu\xi)-U(x)-\mu\left\langle\nabla
U(x),\xi\right\rangle\right|e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\left\|\xi\circ\left|\xi\right|^{p-2}\right\|d\xi$
$\displaystyle\stackrel{{{}_{2}}}{{\leq}}\sum_{i}\frac{L_{i}\mu^{\alpha_{i}}}{\kappa\left(1+\alpha_{i}\right)}\int_{\mathbb{R}^{d}}\left\|\xi\right\|^{\alpha_{i}+1}e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\left\|\xi\circ\left|\xi\right|^{p-2}\right\|d\xi$
$\displaystyle=\sum_{i}\frac{L_{i}\mu^{\alpha_{i}}}{\kappa\left(1+\alpha_{i}\right)}\int_{\mathbb{R}^{d}}\left\|\xi\right\|^{\alpha_{i}+1}e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\left\|\xi^{p-1}\right\|d\xi,$

where step $1$ follows from Jensen inequality, step $2$ is due to 2.2 and the
last step follows from component-wise operation of norm. If $p\leq 2$, by
using generalized Holder inequality, $\left\|\xi^{p-1}\right\|$ can be bounded
as follow:

$\displaystyle\left\|\xi^{p-1}\right\|$
$\displaystyle\leq\left\|\xi^{p-1}\right\|_{p}$
$\displaystyle=\left\|\xi^{p-1}\cdot 1_{d}\right\|_{p}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\left\|\xi\right\|_{p}^{p-1}\left\|1_{d}\right\|_{p}^{2-p}$
$\displaystyle=\left\|\xi\right\|_{p}^{p-1}d^{\frac{2-p}{p}}.$ (B.3)

As a result, if $1\leq p\leq 2$ we have

$\displaystyle\left\|\nabla U_{\mu}(x)-\nabla U(x)\right\|$
$\displaystyle\leq\sum_{i}\frac{L_{i}\mu^{\alpha_{i}}}{\kappa\left(1+\alpha_{i}\right)}\int_{\mathbb{R}^{d}}\left\|\xi\right\|^{\alpha_{i}+1}\left\|\xi\right\|_{p}^{p-1}e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}\sum_{i}\frac{L_{i}\mu^{\alpha_{i}}}{\left(1+\alpha_{i}\right)}d^{\frac{2-p}{p}}\mathbb{E}\left[\left\|\xi\right\|_{p}^{p+\alpha_{i}}\right]$
$\displaystyle\stackrel{{{}_{2}}}{{\leq}}\sum_{i}\frac{L_{i}\mu^{\alpha_{i}}}{\left(1+\alpha_{i}\right)}d^{\frac{2-p}{p}}\mathbb{E}\left[\left\|\xi\right\|_{p}^{2p}\right]^{\frac{p+\alpha}{2p}}$
$\displaystyle\stackrel{{{}_{3}}}{{\leq}}\sum_{i}\frac{L_{i}\mu^{\alpha_{i}}}{\left(1+\alpha_{i}\right)}d^{\frac{2-p}{p}}\left(d+p\right)^{\frac{p+\alpha}{p}}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\sum_{i}L_{i}\mu^{\alpha_{i}}d^{\frac{3}{p}}$

where step $1$ is from $\left\|\xi\right\|\leq\left\|\xi\right\|_{p}$, step
$2$ follows from Jensen inequality and $\alpha\leq p$, step $3$ is due to 2.2
and in the last two steps we have used simplification for large enough $d$ and
small enough $\mu$. By replacing Assumption 2.1 with Assumption 2.2, for $\mu$
is small enough, we immediately get

$\left\|\nabla U_{\mu}(x)-\nabla U(x)\right\|\leq
2L\mu^{\alpha}d^{\frac{3}{p}}.$

iii) In this case, using Eqs. 2.2 and B.2, we get:

$\nabla
U_{\mu}(x)=\frac{1}{\kappa}\int_{\mathbb{R}^{d}}\left[\frac{U(x+\mu\xi)-U(x)}{\mu}\right]\xi\circ\left|\xi\right|^{p-2}e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}d\xi.$

Let $V(x)=U(x+\mu\xi)-U(x)$, from above equation, we obtain

$\displaystyle\left\|\nabla U_{\mu}(y)-\nabla U_{\mu}(x)\right\|$
$\displaystyle=\left\|\frac{1}{\mu\kappa}\int_{\mathbb{R}^{d}}\left(V(y)-V(x)\right)e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\xi\circ\left|\xi\right|^{p-2}d\xi\right\|$
$\displaystyle=\left\|\frac{1}{\mu\kappa}\int_{\mathbb{R}^{d}}\int_{0}^{1}\left\langle\nabla
V\left(ty+\left(1-t\right)x\right),y-x\right\rangle
dt\,e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\xi\circ\left|\xi\right|^{p-2}d\xi\right\|$
$\displaystyle=\left\|\frac{1}{\mu\kappa}\int_{\mathbb{R}^{d}}\int_{0}^{1}\left\langle\nabla
U\left(ty+\left(1-t\right)x+\mu\xi\right)-\nabla
U\left(ty+\left(1-t\right)x\right),y-x\right\rangle
dt\,e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\xi\circ\left|\xi\right|^{p-2}d\xi\right\|$
$\displaystyle\leq\frac{1}{\mu\kappa}\int_{\mathbb{R}^{d}}\int_{0}^{1}\left\|\nabla
U\left(ty+\left(1-t\right)x+\mu\xi\right)-\nabla
U\left(ty+\left(1-t\right)x\right)\right\|\left\|y-x\right\|dt\,e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\left\|\xi\circ\left|\xi\right|^{p-2}\right\|d\xi$
$\displaystyle\leq\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}\kappa}\int_{\mathbb{R}^{d}}\left\|\xi\right\|^{\alpha_{i}}\left\|y-x\right\|\,e^{-\frac{1}{p}\left\|\xi\right\|_{p}^{p}}\left\|\xi^{p-1}\right\|d\xi.$

Since $p\leq 2$ we have

$\displaystyle\left\|\nabla U_{\mu}(y)-\nabla U_{\mu}(x)\right\|$
$\displaystyle\leq\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2-p}{p}}\mathbb{E}\left(\left\|\xi\right\|_{p}^{p-1+\alpha}\right)\left\|y-x\right\|$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2-p}{p}}\mathbb{E}\left(\left\|\xi\right\|_{p}^{p}\right)^{\frac{p-1+\alpha}{p}}\left\|y-x\right\|$
$\displaystyle\stackrel{{{}_{2}}}{{\leq}}\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2-p}{p}}\left(d+\frac{p}{2}\right)^{\frac{p-1+\alpha}{p}}\left\|y-x\right\|$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2}{p}}\left\|y-x\right\|,$

where step $1$ follows from Jensen inequality and $\alpha_{i}\leq 1$, step $2$
is due to 2.2 and in the last two step is because of simplification for large
enough $d$ and small enough $\mu$. By replacing Assumption 2.1 with Assumption
2.2, for $\mu$ is small enough, we immediately get

$\left\|\nabla U_{\mu}(y)-\nabla
U_{\mu}(x)\right\|\leq\frac{L}{\mu^{1-\alpha}}d^{\frac{2}{p}}\left\|y-x\right\|.$

∎

##  Appendix C Proofs under LSI

###  C.1 Proof of Lemma 3.2

######  Lemma C.1.

Suppose $\pi=e^{-U}$ satisfies $\alpha$-mixture weakly smooth. Let
$p_{0}=N(0,\frac{1}{L}I)$. Then $H(p_{0}|\pi)\leq
U(0)-\frac{d}{2}\log\frac{2\Pi
e}{L}+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\left(\frac{d}{L}\right)^{\frac{1+\alpha_{i}}{2}}=O(d).$

###### Proof.

Since $U$ is mixture weakly smooth, for all $x\in\mathbb{R}^{d}$ we have

$\displaystyle U(x)$ $\displaystyle\leq U(0)+\langle\nabla
U(0),x\rangle+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\|x\|^{1+\alpha_{i}}$
$\displaystyle=U(0)+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\|x\|^{1+\alpha_{i}}.$

Let $X\sim\rho=N(0,\frac{1}{L}I)$. Then

$\displaystyle\mathbb{E}_{\rho}[U(X)]$ $\displaystyle\leq
U(0)+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\mathbb{E}_{\rho}\left(\|x\|^{1+\alpha_{i}}\right)$
$\displaystyle\leq
U(0)+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\mathbb{E}_{\rho}\left(\|x\|^{2}\right)^{\frac{1+\alpha_{i}}{2}}$
$\displaystyle\leq
U(0)+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\left(\frac{d}{L}\right)^{\frac{1+\alpha_{i}}{2}}.$

Recall the entropy of $\rho$ is
$H(\rho)=-\mathbb{E}_{\rho}[\log\rho(X)]=\frac{d}{2}\log\frac{2\Pi e}{L}$.
Therefore, the KL divergence is

$\displaystyle\mathbb{E}(\rho|\pi)$
$\displaystyle=\int\rho\left(\log\rho+U\right)dx$
$\displaystyle=-H(\rho)+\mathbb{E}_{\rho}[U]$ $\displaystyle\leq
U(0)-\frac{d}{2}\log\frac{2\Pi
e}{L}+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\left(\frac{d}{L}\right)^{\frac{1+\alpha_{i}}{2}}$
$\displaystyle=O(d).$

This is the desired result. ∎

###  C.2 Proof of Lemma 3.2

######  Lemma C.2.

Assume $\pi=e^{-U(x)}$ is $\alpha$-mixture weakly smooth. Then

$\mathbb{E}_{\pi}\left[\left\|\nabla U(x)\right\|^{2}\right]\leq
2\left(\sum_{i}L_{i}\right)^{2}d^{\frac{3}{p}},$

In particular, if $\pi=e^{-U(x)}$ is $\left(\alpha,\ell\right)$-weakly smooth.
Then

$\mathbb{E}_{\pi}\left[\left\|\nabla U(x)\right\|^{2\alpha}\right]\leq
L^{2\alpha}d^{\frac{3-\alpha}{1+\alpha}\alpha},$

$\mathbb{E}_{\pi}\left[\left\|\nabla U(x)\right\|^{2\ell+2\alpha}\right]\leq
L^{2\left(\ell+\alpha\right)}d^{\frac{3-\alpha}{1+\alpha}\left(\ell+\alpha\right)},$

for $d$ sufficiently large.

###### Proof.

Since $\pi$ is stationary distribution, we have

$\frac{d}{dt}\mathbb{E}_{\pi}\left[U_{\mu}\left(x\right)\right]=\int\left(\left(\triangle
U_{\mu}\left(x\right)\right)-\left\langle\nabla U\left(x\right),\nabla
U_{\mu}\left(x\right)\right\rangle\right)\pi\left(x\right)dx=0.$

So

$\displaystyle\mathbb{E}_{\pi}\left\langle\nabla U\left(x\right),\nabla
U_{\mu}\left(x\right)\right\rangle$
$\displaystyle=\mathbb{E}_{\pi}\left(\triangle U_{\mu}\left(x\right)\right)$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2}{p}},$

where the last step comes from Lemma 2.2that $\nabla U_{\mu}\left(x\right)$ is
$\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2}{p}}$-Lipschitz,
$\nabla^{2}U_{\mu}\left(x\right)\preceq\left(\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2}{p}}\right)\,I$.
In addition,

$\displaystyle\mathbb{E}_{\pi}\left\langle\nabla U\left(x\right),\nabla
U_{\mu}\left(x\right)\right\rangle$
$\displaystyle=\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2}\right]+\mathbb{E}_{\pi}\left\langle\nabla
U\left(x\right),\nabla U_{\mu}\left(x\right)-\nabla
U\left(x\right)\right\rangle$
$\displaystyle\stackrel{{{}_{1}}}{{\geq}}\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2}\right]-\mathbb{E}_{\pi}\left\|\nabla
U\left(x\right)\right\|\left\|\nabla U_{\mu}\left(x\right)-\nabla
U\left(x\right)\right\|$
$\displaystyle\stackrel{{\scriptstyle}}{{\geq}}\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2}\right]-\sqrt{\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2}\right]}\sum_{i}L_{i}\mu^{\alpha_{i}}d^{\frac{3}{p}},$

where step $1$ follows from Young inequality and the last step comes from
Cauchy inequality and Lemma 2.2 . From quadratic inequality

$\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2}\right]-\sqrt{\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2}\right]}\sum_{i}L_{i}\mu^{\alpha_{i}}d^{\frac{3}{p}}\leq\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2}{p}}$

and since $\sqrt{\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2}\right]}\geq 0$ we obtain

$\displaystyle\sqrt{\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2}\right]}$
$\displaystyle\leq\frac{1}{2}\left[\sqrt{\left(\sum_{i}L_{i}\mu^{\alpha_{i}}\right)^{2}d^{\frac{6}{p}}+4\sum_{i}\frac{L_{i}}{\mu^{1-\alpha_{i}}}d^{\frac{2}{p}}}+\sum_{i}L_{i}\mu^{\alpha_{i}}d^{\frac{3}{p}}\right].$

Simply choose $\mu=1,$ we get

$\displaystyle\mathbb{E}_{\pi}\left[\left\|\nabla U(x)\right\|^{2}\right]$
$\displaystyle\leq\frac{1}{4}\left[\sqrt{\left(\sum_{i}L_{i}\right)^{2}d^{\frac{6}{p}}+4\left(\sum_{i}L_{i}\right)d^{\frac{2}{p}}}+\sum_{i}L_{i}d^{\frac{3}{p}}\right]^{2}$
$\displaystyle\leq 2\left(\sum_{i}L_{i}\right)^{2}d^{\frac{3}{p}},$

for large enough $d.$ If we replace Assumption 2.1 by Assumption 2.2, we can
choose $p=2$ and $\mu=\frac{1}{d^{\frac{2}{1+\alpha}}}$, we deduce

$\displaystyle\mathbb{E}_{\pi}\left[\left\|\nabla U(x)\right\|^{2}\right]$
$\displaystyle\leq\frac{1}{4}\left[\sqrt{L^{2}\mu^{2\alpha}d^{\frac{6}{p}}+4\frac{Ld^{\frac{2}{p}}}{\mu^{1-\alpha}}}+L\mu^{\alpha}d^{\frac{3}{p}}\right]^{2}$
$\displaystyle\leq L^{2}d^{\frac{3-\alpha}{1+\alpha}},$

for $d$ large enough as desired. Since $\alpha\leq 1$, $x\rightarrow
x^{\alpha}$ is concave function. By Jensen inequality

$\displaystyle\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2\alpha}\right]$
$\displaystyle\leq\left(\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2}\right]\right)^{\alpha}$ $\displaystyle\leq
L^{2\alpha}d^{\frac{3-\alpha}{1+\alpha}\alpha}.$

Similarly, $\ell+\alpha\leq 1,$by Jensen inequality we also have

$\displaystyle\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2\ell+2\alpha}\right]$
$\displaystyle\leq\left(\mathbb{E}_{\pi}\left[\left\|\nabla
U(x)\right\|^{2}\right]\right)^{\ell+\alpha}$ $\displaystyle\leq
L^{2\left(\ell+\alpha\right)}d^{\frac{3-\alpha}{1+\alpha}\left(\ell+\alpha\right)},$

as desired.

∎

###  C.3 Proof of Lemma 3.1

######  Lemma C.3.

Suppose $\pi$ is $\gamma-$log-Sobolev, $\alpha$-mixture weakly smooth with
$\max\left\\{L_{i}\right\\}=L\geq 1$. If
$0<\eta\leq\left(\frac{\gamma}{9N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}$
, then along each step of ULA (3.6),

$\displaystyle H(p_{k+1}|\pi)\leq
e^{-\gamma\eta}H(p_{k}|\pi)+2\eta^{\alpha+1}D_{3},$ (C.1)

where
$D_{3}=\sum_{i}10N^{3}L^{6}+16NL^{4}+8N^{2}L^{4}d^{\frac{3}{p}}+4NL^{2}d$.

In particular, if$\pi$ is $\gamma-$log-Sobolev,
$\left(\alpha,\ell\right)-$weakly smooth with $0<\alpha+\ell\leq 1$. If
$0<\eta\leq\left(\frac{\gamma}{2L^{1+\alpha}}\right)^{\frac{1}{\alpha}}$, then
along each step of ULA (3.6),

$\displaystyle H(p_{k+1}|\pi)\leq
e^{-\gamma\eta}H(p_{k}|\pi)+2\eta^{\alpha+1}D_{3}^{\prime},$ (C.2)

where
$D_{3}^{\prime}=16L^{2+2\alpha+2\ell}+4L^{2+2\alpha}d^{\frac{3-\alpha}{1+\alpha}\left(\alpha+\ell\right)}+4L^{2}d^{\alpha+\ell}$.

###### Proof.

We adapt the proof of [31]. First, recall that the discretization of the LMC
is

$x_{k,t}\stackrel{{\scriptstyle}}{{=}}x_{k}-t\nabla
U(x_{k})+\sqrt{2t}\,z_{k}$,

where $z_{k}\sim N(0,I)$ is independent of $x_{k}$. Let $x_{k}\sim p_{k}$ and
$x^{\ast}\sim\pi$ with an optimal coupling $(x_{k},x^{\ast})$ so that
$\mathbb{E}[\|x_{k}-x^{\ast}\|^{2}]=W_{2}(p_{k},\pi)^{2}$. Let
$D_{1i}=8NL_{i}^{2+2\alpha_{i}}\left(\left(\sum_{j}L_{i}\right)^{2}+1\right)+16L_{i}^{2+2\alpha_{i}}+8L_{i}^{2}\left(\sum_{i}L_{i}\right)^{2}d^{\frac{3}{p}}+4L_{i}^{2}d^{\alpha_{i}}$,
we deduce

$\displaystyle L_{i}^{2}E_{p_{k}}\left[\left\|-t\nabla
U(x_{k})+\sqrt{2t}z_{k}\right\|^{2\alpha_{i}}\right]$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}2L_{i}^{2}t^{2\alpha_{i}}\mathbb{E}_{p_{k}}\left[\left\|\nabla
U(x_{k})\right\|^{2\alpha_{i}}\right]+4L_{i}^{2}t^{\alpha_{i}}\mathbb{E}_{p_{k}}\left[\left\|z_{k}\right\|^{2\alpha_{i}}\right]$
$\displaystyle\stackrel{{{}_{2}}}{{\leq}}2L_{i}^{2}t^{2\alpha_{i}}\mathbb{E}_{p_{k}}\left[\left\|\nabla
U(x_{k})\right\|^{2\alpha_{i}}\right]+4L_{i}^{2}t^{\alpha_{i}}\mathbb{E}_{p_{k}}\left[\left\|z_{k}\right\|^{2}\right]^{\alpha_{i}}$
$\displaystyle\stackrel{{{}_{3}}}{{\leq}}4L_{i}^{2}t^{2\alpha_{i}}\mathbb{E}\left[\left\|\nabla
U(x_{k})-\nabla U(x^{*})\right\|^{2\alpha_{i}}+\left\|\nabla
U(x^{*})\right\|^{2\alpha_{i}}\right]+4L_{i}^{2}t^{\alpha_{i}}d^{\alpha_{i}}$
$\displaystyle\stackrel{{{}_{4}}}{{\leq}}4L_{i}^{2}t^{2\alpha_{i}}\mathrm{\mathbb{E}}\left(\sum_{i}L_{i}\left\|x_{k}-x^{*}\right\|^{\alpha_{i}}\right)^{2\alpha_{i}}+4L_{i}^{2}t^{2\alpha_{i}}\mathbb{E}\left\|\nabla
U(x^{*})\right\|^{2\alpha_{i}}+4L_{i}^{2}t^{\alpha_{i}}d^{\alpha_{i}}$
$\displaystyle\leq
8L_{i}^{2+2\alpha_{i}}t^{2\alpha_{i}}N\sum_{j}L_{i}^{2\alpha_{i}}\mathrm{\mathbb{E}}\left[\left\|x_{k}-x^{*}\right\|^{2\alpha_{j}\alpha_{i}}\right]+4L_{i}^{2}t^{2\alpha}\mathbb{E}\left\|\nabla
U(x^{*})\right\|^{2}$
$\displaystyle+4L_{i}^{2}t^{2\alpha}+4L_{i}^{2}t^{\alpha}d^{\alpha}$
$\displaystyle\stackrel{{{}_{5}}}{{\leq}}8NL_{i}^{2+2\alpha_{i}}t^{2\alpha_{i}}\left(\left(\sum_{j}L_{i}\right)^{2}+1\right)\mathrm{\mathbb{E}}\left[1+\left\|x_{k}-x^{*}\right\|^{2}\right]+4L_{i}^{2}t^{2\alpha}\mathbb{E}\left\|\nabla
U(x^{*})\right\|^{2}$
$\displaystyle+4L_{i}^{2}t^{2\alpha}+4L_{i}^{2}t^{\alpha}d^{\alpha}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}8NL_{i}^{2+2\alpha_{i}}\eta^{2\alpha}\left(\left(\sum_{j}L_{i}\right)^{2}+1\right)\mathrm{\mathbb{E}}\left[\left\|x_{k}-x^{*}\right\|^{2}\right]$
$\displaystyle+\left(8NL_{i}^{2+2\alpha_{i}}\left(\left(\sum_{j}L_{i}\right)^{2}+1\right)+16L_{i}^{2+2\alpha_{i}}+8L_{i}^{2}\left(\sum_{i}L_{i}\right)^{2}d^{\frac{3}{p}}+4L_{i}^{2}d^{\alpha_{i}}\right)\eta^{\alpha_{i}}$
$\displaystyle\leq\frac{16N}{\gamma}\left(\left(\sum_{j}L_{i}\right)^{2}+1\right)L^{2+2\alpha_{i}}\eta^{2\alpha_{i}}H(p_{k}|\pi)+D_{1i}\eta^{\alpha_{i}},$
(C.3)

where step $1$ follows from Lemma F.13 in Appendix F, step $2$ is from
$\alpha\leq 1$ and Jensen’s inequality, step $3$ comes from normal
distribution, and step $4$ follows our Assumption 2.2, and in step $5$ we have
used $\alpha_{i}\leq 1$ and the last step is due to Talagrand inequality which
comes from log-Sobolev inequality and Lemma F.16 in Appendix F below.
Similarly, we get

$\displaystyle\mathrm{\mathbb{E}}_{p_{kt}}\left\|\nabla U(x_{k})-\nabla
U(x_{k,t})\right\|^{2}$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}\sum_{i}L_{i}^{2}\mathrm{\mathbb{E}}_{p_{kt}}\left\|\tilde{x}_{k,t}-x_{k}\right\|^{2\alpha_{i}}$
$\displaystyle=\sum_{i}L_{i}^{2}\mathrm{\mathbb{E}}_{p_{k}}\left\|-t\nabla
U(x_{k})+\sqrt{2t}z_{k}\right\|^{2\alpha_{i}}$
$\displaystyle\stackrel{{{}_{2}}}{{\leq}}\sum_{i}\frac{16N}{\gamma}\left(\left(\sum_{j}L_{i}\right)^{2}+1\right)L^{2+2\alpha_{i}}\eta^{2\alpha_{i}}H(p_{k}|\pi)+\left(\sum_{i}D_{1i}\eta^{\alpha_{i}}\right)$
$\displaystyle\stackrel{{{}_{3}}}{{\leq}}\frac{20N^{3}}{\gamma}L^{6}\eta^{2\alpha}H(p_{k}|\pi)+D_{3}\eta^{\alpha}$
(C.4)

where step $1$ follows from Assumption 2.2, step $2$ comes from similar
reasoning as equation (C.3), and the last step comes from
$\eta\leq\frac{1}{L}$ and $\eta\leq 1$ and definition of $D_{3}$. Therefore,
from [31] Lemma 3, the time derivative of KL divergence along LMC is bounded
by

$\displaystyle\frac{d}{dt}H\left(p_{k,t}|\pi\right)$
$\displaystyle\leq-\frac{3}{4}I\left(p_{k,t}|\pi\right)+\mathbb{E}_{p_{kt}}\left[\left\|\nabla
U(x_{k,t})-\nabla U(x_{k})\right\|^{2}\right]$
$\displaystyle\leq-\frac{3}{4}I(p_{k}|\pi)+\frac{20N^{3}}{\gamma}L^{6}\eta^{2\alpha}H(p_{k}|\pi)+D_{3}\eta^{\alpha}$
$\displaystyle\leq-\mathrm{\frac{3\gamma}{2}}H(p_{k,t}|\pi)+\frac{20N^{3}}{\gamma}L^{6}\eta^{2\alpha}H(p_{k}|\pi)+D_{3}\eta^{\alpha},$

where in the last inequality we have used the definition A.1 of LSI
inequality. Multiplying both sides by $e^{\frac{3\gamma}{2}t}$, and
integrating both sides from $t=0$ to $t=\eta$ we obtain

$\displaystyle e^{\frac{3\gamma}{2}\eta}H(p_{k+1}|\pi)-H(p_{k}|\pi)$
$\displaystyle\leq
2\left(\frac{e^{\frac{3\gamma}{2}\eta}-1}{3\gamma}\right)\left(\frac{20N^{3}}{\gamma}L^{6}\eta^{2\alpha}H(p_{k}|\pi)+D_{3}\eta^{\alpha}\right)$
(C.5) $\displaystyle\leq
2\eta\left(\frac{20N^{3}}{\gamma}L^{6}\eta^{2\alpha}H(p_{k}|\pi)+D_{3}\eta^{\alpha}\right)$
(C.6)

where the last line holds by $e^{c}\leq 1+2c$ for
$0<c=\frac{3\gamma}{2}\eta<1$. Rearranging the term of the above inequality
and using the facts that $1+\eta^{1+2\alpha}\frac{40N^{3}}{\gamma}L^{6}\leq
1+\frac{\gamma\eta}{2}\leq e^{\frac{\gamma\eta}{2}}$ when
$\eta\leq\left(\frac{\gamma}{9N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}$
and $e^{-\frac{3\gamma}{2}\eta}\leq 1$ leads to

$\displaystyle H(p_{k+1}|\pi)$ $\displaystyle\leq
e^{-\frac{3\gamma}{2}\eta}\left(1+\eta^{1+2\alpha}\frac{40N^{3}}{\gamma}L^{6}\right)H(p_{k}|\pi)+2\eta^{\alpha+1}D_{3}$
$\displaystyle\leq e^{-\gamma\eta}H(p_{k}|\pi)+2\eta^{\alpha+1}D_{3}.$ (C.7)

as desired. ∎

###  C.4 Proof of Theorem 3.1

######  Theorem C.1.

Suppose $\pi$ is $\gamma-$log-Sobolev, $\alpha$-mixture weakly smooth with
$\max\left\\{L_{i}\right\\}=L\geq 1$, and for any $x_{0}\sim p_{0}$ with
$H(p_{0}|\pi)=C_{0}<\infty$, the iterates $x_{k}\sim p_{k}$ of ULA with step
size

$\eta\leq\min\left\\{1,\frac{1}{4\gamma},\left(\frac{\gamma}{9N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}\right\\}$
(C.8)

satisfies

$\displaystyle H(p_{k}|\pi)\leq e^{-\frac{3\gamma}{2}\eta
k}H(p_{0}|\pi)+2\eta^{\alpha+1}D_{3},$ (C.9)

where
$D_{3}=\sum_{i}10N^{3}L^{6}+16NL^{4}+8N^{2}L^{4}d^{\frac{3}{p}}+4NL^{2}d$.
Then, for any $\epsilon>0$, to achieve $H(p_{k}|\pi)<\epsilon$, it suffices to
run LMC with step size

$\eta\leq\min\left\\{1,\frac{1}{4\gamma},\left(\frac{\gamma}{9N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}},\left(\frac{3\epsilon\gamma}{16D_{3}}\right)^{\frac{1}{\alpha}}\right\\}$
(C.10)

for $k\geq\frac{1}{\gamma\eta}\log\frac{2H\left(p_{0}|\pi\right)}{\epsilon}$
iterations.

###### Proof.

Applying inequality C.9 recursively, and using the inequality
$1-e^{-c}\geq\frac{3}{4}c$ for $0<c=\gamma\eta\leq\frac{1}{4}$ we obtain

$\displaystyle H(p_{k}|\pi)$ $\displaystyle\leq\,e^{-\gamma\eta
k}H(p_{0}|\pi)+\frac{2\eta^{\alpha+1}D_{3}}{1-e^{-\gamma\eta}}$
$\displaystyle\leq\,e^{-\gamma\eta
k}H(p_{0}|\pi)+\frac{2\eta^{\alpha+1}D_{3}}{\frac{3}{4}\gamma\eta}$
$\displaystyle\leq\,e^{-\gamma\eta
k}H(p_{0}|\pi)+\frac{8\eta^{\alpha}D_{3}}{3\gamma}.$ (C.11)

Note that last inequality holds if we choose $\eta$ such that it satisfies

$\eta\leq\min\left\\{1,\frac{1}{4\gamma},\left(\frac{\gamma}{9N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}\right\\}.$

Given $\epsilon>0$, if we further assume
$\eta\leq\left(\frac{3\epsilon\gamma}{16D_{3}}\right)^{\frac{1}{\alpha}}$,
then the above implies $H(p_{k}|\pi)\leq e^{-\gamma\eta
k}H(p_{0}|\pi)+\frac{\epsilon}{2}.$ This means for
$k\geq\frac{1}{\gamma\eta}\log\frac{2H\left(p_{0}|\pi\right)}{\epsilon},$ we
have $H(p_{k}|\pi)\leq\frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon$, as
desired. ∎

##  Appendix D Proof of sampling via smoothing potential

###  D.1 Proof of Lemma 3.3

######  Lemma D.1.

For any $x_{k}\in\mathbb{R}^{d}$, then $g_{\mu}(x_{k},\zeta_{k})=\nabla
U_{\mu}(x_{k})+\zeta_{k}$ is an unbiased estimator of $\nabla U_{\mu}$ such
that

$\displaystyle\mathrm{Var}\left[g_{\mu}(x_{k},\zeta_{k})\right]$
$\displaystyle\leq 4N^{2}L^{2}\mu^{2\alpha}d^{\frac{2\alpha}{p}}.$

###### Proof.

Recall that by definition of $U_{\mu}$, we have $\nabla
U_{\mu}(x)=\mathrm{\mathrm{\mathbb{E}}}_{\zeta}[U(x+\mu\mathrm{\zeta})]$,
where $\mathrm{\zeta}\sim N_{p}(0,I_{d\times d})$, and is independent of
$\zeta_{1}$. Clearly,
$\mathrm{E}_{\mathrm{\mathrm{\zeta_{1}}}}[g(x,\mathrm{\zeta_{1}})]=\nabla
U_{\mu}(x)$. We now proceed to bound the variance of $g(x,\zeta_{1})$. We
have:

$\displaystyle\mathrm{\mathbb{E}}_{\mathrm{\zeta_{1}}}[\|\nabla
U_{\mu}(x)-g(x,\zeta_{1})\|_{2}^{2}]$
$\displaystyle\leq\mathrm{\mathbb{E}}_{\zeta_{1}}[\|\mathrm{E}_{\zeta}[U(x+\mu\mathrm{\zeta})]-\nabla
U(x+\mu\mathrm{\zeta_{1}})\|^{2}]\text{ }$
$\displaystyle\leq\mathrm{\mathbb{E}}_{\zeta_{1},\mathrm{\zeta}}[\|\nabla
U(x+\mu\mathrm{\zeta})-\nabla U(x+\mu\mathrm{\zeta_{1}})\|^{2}].$
$\displaystyle\leq
N\sum_{i}L_{i}^{2}\mathrm{\mathbb{E}}_{\mathrm{\zeta_{1}},\mathrm{\zeta}}[\|\mu(\mathrm{\zeta}-\mathrm{\zeta_{1}})\|^{2\alpha_{i}}$
$\displaystyle\leq
N\sum_{i}L_{i}^{2}\mu^{2\alpha_{i}}\mathrm{\mathbb{E}}_{\zeta_{1},\mathrm{\zeta}}[\|\mathrm{\zeta}-\mathrm{\zeta_{1}}\|^{2\alpha_{i}}]$
$\displaystyle\leq
2N\sum_{i}L_{i}^{2}\mu^{2\alpha_{i}}\left(\mathrm{\mathbb{E}}\left[\|\mathrm{\zeta}\|^{2\alpha_{i}}\right]+\mathrm{\mathbb{E}}\left[\|\mathrm{\zeta_{1}}\|^{2\alpha_{i}}\right]\right)$
$\displaystyle\leq
2N\sum_{i}L_{i}^{2}\mu^{2\alpha_{i}}\left(\left(\mathrm{\mathbb{E}}\left[\|\mathrm{\zeta}\|^{2}\right]\right)^{\alpha_{i}}+\left(\mathrm{\mathbb{E}}\left[\|\zeta_{1}\|^{2}\right]\right)^{\alpha_{i}}\right)$
$\displaystyle\leq
4N\sum_{i}L_{i}^{2}\mu^{2\alpha_{i}}d^{\frac{2\alpha_{i}}{p}}$
$\displaystyle\leq 4N^{2}L^{2}\mu^{2\alpha}d^{\frac{2\alpha}{p}},$

as claimed. ∎

###  D.2 Proof of Lemma 3.2

Before proving Theorem 3.2, we need an additional lemma.

######  Lemma D.2.

[[31] modified Lemma 3] Suppose $x_{k,t}$ is the interpolation of the
discretized process (1.2). Let $p_{k,t}$, $p_{kt}$ and $p_{kt\zeta}$ denote
its distribution, the joint distribution of $x_{k,t}$ and $x_{k}$ and the
joint distribution of $x_{k,t}$, $x_{k}$ and $\zeta$ respectively. Here
$g(x_{k},\zeta)$ is an estimate of $\nabla U(x_{k})$ with noise $\zeta$ such
that $E_{\zeta}g(x_{k},\zeta)=\nabla U(x_{k})$. Then

${\displaystyle\frac{d}{dt}H\left(p_{k,t}|\pi_{\mu}\right)\leq-\frac{3}{4}I\left(p_{k,t}|\pi_{\mu}\right)+\mathbb{E}_{p_{kt\zeta}}\left[\left\|\nabla
U(x_{k,t})-g(x_{k},\zeta)\right\|^{2}\right]}.$ (D.1)

###### Proof.

The steps follow exactly as in Lemma 3 and we provide the proof here for
completeness. For each $t>0$, let $p_{k\zeta|t}(x_{k},\zeta)$ denote the
distributions of $x_{k}$ and $\zeta$ conditioned on $x_{k,t}$ and
$p_{t|k\zeta}(x_{k,t})$ denote the distributions of $x_{k,t}$ conditioned on
$x_{k}$ and $\zeta$. Following Fokker-Planck equation, we have

$\frac{\partial p_{t|k\zeta}(x_{k,t})}{\partial
t}=\nabla\cdot\left(p_{t|k\zeta}(x_{k,t})g(x_{k},\zeta)\right)+\triangle
p_{t|k\zeta}(x_{k,t}),$ (D.2)

which integrating with respect to $x_{k}$ and $\zeta$ achieves

$\displaystyle\frac{\partial p_{k,t}(x)}{\partial t}$
$\displaystyle=\int\int\frac{\partial p_{t|k\zeta}(x)}{\partial
t}p_{k\zeta}(x_{k},\zeta)dx_{k}d\zeta$
$\displaystyle=\int\int\left(\nabla\cdot\left(p_{t|k\zeta}(x_{k,t})g(x_{k},\zeta)\right)+\triangle
p_{t|k\zeta}(x_{k,t})\right)dx_{k}d\zeta$
$\displaystyle=\int\int\left(\nabla\cdot\left(p_{t|k\zeta}(x_{k,t})g(x_{k},\zeta)\right)\right)+\triangle
p_{k,t}(x)$ $\displaystyle=\nabla\cdot(p_{k,t}(x)\int\int
p_{k\zeta|t}(x_{k})g(x_{k},\zeta)dx_{k}d\zeta)+\triangle p_{k,t}(x)$ (D.3)
$\displaystyle=\nabla\cdot\
(p_{k,t}(x)\mathrm{\mathbb{E}}_{p_{k\zeta|t}}[g(x_{k},\zeta)|x_{k,t}=x])+\triangle
p_{k,t}(x).$ (D.4)

Combining with $\int p_{t}\frac{\partial}{\partial
t}\log\frac{p_{t}}{\pi_{\mu}}\,dx=\int\frac{\partial p_{t}}{\partial
t}\,dx=\frac{d}{dt}\int p_{t}\,dx=0$, we get the following inequality for time
derivative of KL-divergence.

$\displaystyle\frac{d}{dt}H\left(p_{k,t}|\pi_{\mu}\right)$
$\displaystyle=\frac{d}{dt}\int
p_{k,t}(x)\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)dx$
$\displaystyle=\int\frac{\partial p_{k,t}}{\partial
t}(x)\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)dx$
$\displaystyle=\int\left[\nabla\cdot\left(p_{k,t}(x)\mathrm{\mathbb{E}}_{p_{k\zeta|t}}[g(x_{k},\zeta)|x_{k,t}=x]\right)\right]\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)dx$
$\displaystyle+\int\left[\triangle
p_{k,t}(x)\right]\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)dx$
$\displaystyle\stackrel{{\scriptstyle\left(i\right)}}{{=}}\int\left[\nabla\cdot\left(p_{k,t}(x)\mathrm{\mathbb{E}}_{p_{k\zeta|t}}[g(x_{k},\zeta)|x_{k,t}=x]\right)\right]\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)dx$
$\displaystyle+\int\left[\nabla\cdot\left(\nabla\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)-\nabla
U(x)\right)\right]\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)dx$
$\displaystyle\stackrel{{\scriptstyle\left(ii\right)}}{{=}}-\int
p_{k,t}(x)\left\langle\mathrm{\mathbb{E}}_{p_{k\zeta|t}}[g(x_{k},\zeta)|x_{k,t}=x],\
\nabla\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)\right\rangle dx$
$\displaystyle-\int
p_{k,t}(x)\left\langle\nabla\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)-\nabla
U(x),\ \nabla\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)\right\rangle dx$
$\displaystyle=-I\left(p_{k,t}|\pi_{\mu}\right)$ $\displaystyle+\int
p_{k,t}(x)\left\langle\nabla
U(x)-\mathrm{\mathbb{E}}_{p_{k\zeta|t}}[g(x_{k},\zeta)|x_{k,t}=x],\
{\displaystyle\nabla\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)}\right\rangle
dx$
$\displaystyle=-I\left(p_{k,t}|\pi_{\mu}\right)+\mathrm{\mathbb{E}}_{p_{kt\zeta}}\left\langle\nabla
U(x_{k,t})-g(x_{k},\zeta),\
{\displaystyle\nabla\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)}\right\rangle$
$\displaystyle\stackrel{{\scriptstyle\left(iii\right)}}{{\leq}}-I\left(p_{k,t}|\pi_{\mu}\right)$
$\displaystyle+\mathrm{E}_{p_{kt\zeta}}\left\|\nabla
U(x_{k,t})-g(x_{k},\zeta)\right\|^{2}+\frac{1}{4}\mathrm{\mathbb{E}}_{p_{k,t}}\left\|\nabla\log\left(\frac{p_{k,t}(x)}{\pi_{\mu}(x)}\right)\right\|^{2}$
$\displaystyle=-\frac{3}{4}I\left(p_{k,t}|\pi_{\mu}\right)+\mathrm{\mathbb{E}}_{p_{kt\zeta}}\left\|\nabla
U(x_{k,t})-g(x_{k},\zeta)\right\|^{2}$ (D.5)

in which equality $\left(i\right)$ is follows from $\triangle
p_{k,t}=\nabla\cdot(\nabla p_{k,t})$, equality $\left(ii\right)$ follows from
the divergence theorem, inequality $\left(iii\right)$ follows from
$\left\langle u,\
v\right\rangle{\displaystyle\leq\|u\|^{2}+\frac{1}{4}\|v\|^{2}}$, and in the
last step, the expectation is taken with respect to both $x_{k}$ ,$x_{k,t}$
and $\zeta.$ ∎

We now ready to state and prove Theorem 3.2.

######  Theorem D.1.

Suppose $\pi_{\mu}$ is $\gamma_{1}-$log-Sobolev, $\alpha$-mixture weakly
smooth, $L=1\vee\max\left\\{L_{i}\right\\}$, and for any $x_{0}\sim p_{0}$
with $H(p_{0}|\pi)=C_{0}<\infty$, the iterates $x_{k}\sim p_{k}$ of ULA with
step size

$\eta\leq\min\left\\{1,\frac{1}{4\gamma},\left(\frac{\gamma_{1}}{13N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}\right\\}$
(D.6)

satisfies

$\displaystyle H(p_{k}|\pi_{\mu})\leq e^{-\frac{3\gamma_{1}}{2}\eta
k}H(p_{0}|\pi_{\mu})+2\eta^{\alpha+1}D_{4},$ (D.7)

where
$D_{4}=\sum_{i}10N^{3}L^{6}+16NL^{4}+8N^{2}L^{4}d^{\frac{3}{p}}+4NL^{2}d+8N^{2}L^{2}d^{\frac{2\alpha}{p}}$.
Then, for any $\epsilon>0$, to achieve $H(p_{k}|\pi)<\epsilon$, it suffices to
run LMC with step size

$\eta\leq\min\left\\{1,\frac{1}{4\gamma_{1}},\left(\frac{\gamma_{1}}{13N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}},\left(\frac{3\epsilon\gamma_{1}}{16D_{4}}\right)^{\frac{1}{\alpha}}\right\\}$
(D.8)

for
$k\geq\frac{2}{\gamma_{1}\eta}\log\frac{3H\left(p_{0}|\pi_{\mu}\right)}{\epsilon}$
iterations.

###### Proof.

We adapt the proof of [31]. First, recall that the discretization of the ULA
is

$x_{k,t}\stackrel{{\scriptstyle}}{{=}}x_{k}-\eta
g(x_{k},\zeta)+\sqrt{2\eta}\,z_{k}$,

where $z_{k}\sim N(0,I)$ is independent of $x_{k}$. Let $x_{k}\sim p_{k}$ and
$x^{\ast}\sim\pi$ with an optimal coupling $(x_{k},x^{\ast})$ so that
$\mathbb{E}[\|x_{k}-x^{\ast}\|^{2}]=W_{2}(p_{\mu,k},\pi_{\mu})^{2}$. Choosing
$\mu=\sqrt{\eta}$, we have

$\displaystyle\mathrm{\mathbb{E}}_{p_{kt\zeta}}\left\|\nabla
U(x_{k,t})-g(x_{k},\zeta)\right\|^{2}$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}2\left[\mathrm{\mathbb{E}}_{p_{kt\zeta}}\left\|\nabla
U(x_{k,t})-\nabla U(x_{k})\right\|^{2}+\left\|\nabla
U(x_{k})-g(x_{k},\zeta)\right\|^{2}\right]$
$\displaystyle\stackrel{{{}_{2}}}{{\leq}}\frac{40N^{3}}{\gamma_{1}}L^{6}\eta^{2\alpha}H(p_{k}|\pi_{\mu})+D_{3}\eta^{\alpha}+8N^{2}L^{2}\mu^{2\alpha}d^{\frac{2\alpha}{p}}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\frac{40N^{3}}{\gamma_{1}}L^{6}\eta^{2\alpha}H(p_{k}|\pi_{\mu})+D_{4}\eta^{\alpha},$

where step 1 follows from Young inequality and Assumption 2, step $2$ comes
from equation (C.4) , and the last step comes from $\eta\leq\frac{1}{L}$ and
$\eta\leq 1$ and the definition of $D_{4}$. Therefore, from Lemma 3.2, the
time derivative of KL divergence along LMC is bounded by

$\displaystyle\frac{d}{dt}H\left(p_{k,t}|\pi_{\mu}\right)$
$\displaystyle\leq-\frac{3}{4}I(p_{k,t}|\pi_{\mu})+\frac{40N^{3}}{\gamma_{1}}L^{6}\eta^{2\alpha}H(p_{k}|\pi_{\mu})+D_{4}\eta^{\alpha}$
$\displaystyle\leq-\mathrm{\frac{3\gamma_{1}}{2}}H(p_{k,t}|\pi_{\mu})+\frac{40N^{3}}{\gamma_{1}}L^{6}\eta^{2\alpha}H(p_{k}|\pi_{\mu})+D_{4}\eta^{\alpha},$
(D.9)

where in the last inequality we have used the definition A.1 of LSI
inequality. Multiplying both sides by $e^{\frac{3\gamma_{1}}{2}t}$, and
integrating both sides from $t=0$ to $t=\eta$ we obtain

$\displaystyle
e^{\frac{3\gamma}{2}\eta}H(p_{k+1}|\pi_{\mu})-H(p_{k}|\pi_{\mu})$
$\displaystyle\leq
2\left(\frac{e^{\frac{3\gamma_{1}}{2}\eta}-1}{3\gamma_{1}}\right)\left(\frac{40N^{3}}{\gamma_{1}}L^{6}\eta^{2\alpha}H(p_{k}|\pi_{\mu})+D_{4}\eta^{\alpha}\right)$
$\displaystyle\leq
2\eta\left(\frac{40N^{3}}{\gamma_{1}}L^{6}\eta^{2\alpha}H(p_{k}|\pi)+D_{4}\eta^{\alpha}\right)$
(D.10)

where the last line holds by $e^{c}\leq 1+2c$ for
$0<c=\frac{3\gamma_{1}}{2}\eta<1$. Rearranging the term of the above
inequality and using the facts that
$1+\eta^{1+2\alpha}\frac{80N^{3}}{\gamma_{1}}L^{6}\leq
1+\frac{\gamma_{1}\eta}{2}\leq e^{\frac{\gamma_{1}\eta}{2}}$ when
$\eta\leq\left(\frac{\gamma_{1}}{13N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}$
and $e^{-\frac{3\gamma_{1}}{2}\eta}\leq 1$ leads to

$\displaystyle H(p_{k+1}|\pi_{\mu})$ $\displaystyle\leq
e^{-\frac{3\gamma_{1}}{2}\eta}\left(1+\eta^{1+2\alpha}\frac{80N^{3}}{\gamma_{1}}L^{6}\right)H(p_{k}|\pi_{\mu})+2\eta^{\alpha+1}D_{4}$
$\displaystyle\leq
e^{-\gamma_{1}\eta}H(p_{k}|\pi_{\mu})+2\eta^{\alpha+1}D_{3}.$ (D.11)

Applying this inequality recursively, and using the inequality
$1-e^{-c}\geq\frac{3}{4}c$ for $0<c=\gamma_{1}\eta\leq\frac{1}{4}$ we obtain

$\displaystyle H(p_{k}|\pi_{\mu})$ $\displaystyle\leq\,e^{-\gamma_{1}\eta
k}H(p_{0}|\pi_{\mu})+\frac{2\eta^{\alpha+1}D_{4}}{1-e^{-\gamma_{1}\eta}}$
$\displaystyle\leq\,e^{-\gamma_{1}\eta
k}H(p_{0}|\pi_{\mu})+\frac{2\eta^{\alpha+1}D_{4}}{\frac{3}{4}\gamma_{1}\eta}$
$\displaystyle\leq\,e^{-\gamma_{1}\eta
k}H(p_{0}|\pi_{\mu})+\frac{8\eta^{\alpha}D_{4}}{3\gamma_{1}}.$ (D.12)

Note that last inequality holds if we choose $\eta$ such that it satisfies

$\eta\leq\min\left\\{1,\frac{1}{4\gamma_{1}},\left(\frac{\gamma_{1}}{13N^{\frac{3}{2}}L^{3}}\right)^{\frac{1}{\alpha}}\right\\}.$

From Lemma 3.4, by choosing $\mu=\sqrt{\eta}$ small enough so that
$W_{2}(\pi,\ \pi_{\mu})\leq
3\sqrt{NLE_{2}}\eta^{\frac{\alpha}{2}}d^{\frac{1}{p}}$. Since $\pi$ satisfies
log-Sobolev inequality, by triangle inequality we also get

$\displaystyle W_{2}(p_{\mu k},\ \pi)$ $\displaystyle\leq W_{2}(p_{\mu k},\
\pi_{\mu})+W_{2}(\pi,\ \pi_{\mu})$
$\displaystyle\leq\sqrt{\frac{2}{\gamma}H(p_{\mu k},\pi_{\mu})}+W_{2}(\pi,\
\pi_{\mu})$
$\displaystyle\leq\frac{1}{\sqrt{\gamma_{1}}}e^{-\frac{\gamma_{1}}{2}\eta
k}\sqrt{H(p_{0}|\pi_{\mu})}+\frac{2}{\gamma_{1}}\eta^{\frac{\alpha}{2}}\sqrt{D_{4}}+3\sqrt{NLE_{2}}\eta^{\frac{\alpha}{2}}d^{\frac{1}{p}}.$

Given $\epsilon>0$, if we further assume
$\eta\leq\left(\frac{\epsilon\gamma_{1}}{6\sqrt{D_{4}}}\right)^{\frac{2}{\alpha}}\wedge\left(\frac{\epsilon}{9\sqrt{NLE_{2}}d^{\frac{1}{p}}}\right)^{\frac{2}{\alpha}}$,
then the above inequality implies
$H(p_{k}|\pi_{\mu})\leq\frac{1}{\sqrt{\gamma_{1}}}e^{-\frac{\gamma_{1}}{2}\eta
k}\sqrt{H(p_{0}|\pi_{\mu})}+\frac{2\epsilon}{3}.$ This means for
$k\geq\frac{2}{\gamma_{1}\eta}\log\frac{3\sqrt{H\left(p_{0}|\pi_{\mu}\right)\gamma_{1}}}{\epsilon},$
we have $H(p_{k}|\pi)\leq\frac{\epsilon}{3}+\frac{2\epsilon}{3}=\epsilon$, as
desired. ∎

###  D.3 Proof of Lemma 3.4

######  Lemma D.3.

Assume that $\pi\propto\exp(-\pi)$ and $\pi_{\mu}\propto\exp(-U_{\mu})$ and
$\pi$ has a bounded second moment, that is
$\int\left\|x\right\|^{2}\pi(x)dx=E_{2}<\infty$. We deduce the following
bounds

$W_{2}^{2}(\pi,\ \pi_{\mu})\leq 8.24NL\mu^{1+\alpha}d^{\frac{2}{p}}E_{2}.$

for any $\mu\leq 0.05$.

###### Proof.

This proof adapts the technique of the proof of [11]’s Proposition 1\. Without
loss of generality we may assume that
${\displaystyle\int_{\mathbb{R}^{p}}\exp(-U(x))dx=1}$. We first give upper and
lower bounds to the normalizing constant of $\pi_{\mu}$, that is

$\displaystyle c_{\mu}$
$\displaystyle\stackrel{{{}_{\triangle}}}{{=}}\int_{\mathbb{R}^{d}}\pi(x)e^{-\left(U_{\mu}(x)-U(x)\right)}dx.$
$\displaystyle=\mathbb{E}_{\pi}\left(e^{-\left(U_{\mu}(x)-U(x)\right)}\right)$

The constant $c_{\mu}$ is an expectation of
$e^{-\left(U_{\mu}(x)-U(x)\right)}$ with respect to the density $\pi$ so it
can be trivially upper bounded by $e^{M}$ and lower bounded by $e^{-M}$ where
$\left|U_{\mu}(x)-U(x)\right|\leq\sum_{i}L_{i}\mu^{1+\alpha_{i}}d^{\frac{2}{p}}=M$.
Now we control the distance between densities $\pi$ and $\pi_{\mu}$ at any
fixed $x\in\mathbb{R}^{d}$:

$\displaystyle\left|\pi(x)-\pi_{\mu}(x)\right|$
$\displaystyle=\pi(x)\left|1-\frac{e^{-\left(U_{\mu}(x)-U(x)\right)}}{c_{\mu}}\right|$
$\displaystyle\leq\pi(x)\left\\{\left(1-\frac{e^{-\left(U_{\mu}(x)-U(x)\right)}}{e^{M}}\right)+e^{-\left(U_{\mu}(x)-U(x)\right)}\left(\frac{1}{c_{\mu}}-\frac{1}{e^{M}}\right)\right\\}$
$\displaystyle\leq\pi(x)\left(1-e^{-2M}+e^{2M}-1\right)$
$\displaystyle\leq\pi(x)\left(2M+e^{2M}-1\right).$

The first inequality is from triangle inequality of absolute value, second
inequality is trivial while the last inequality follows from $1-e^{-x}\leq x$
for any $x\geq 0$. To bound $W_{2}$, we use an inequality from [32](Theorem
6.15, page 115):

$W_{2}^{2}(\pi,\ \pi_{\mu})\leq
2\int_{\mathbb{R}^{d}}\|x\|_{2}^{2}\left|\pi(x)-\pi_{\mu}(x)\right|dx.$

Combining this with the bound on $\left|\pi(x)-\pi_{\mu}(x)\right|$ shown
above, we have

$\displaystyle W_{2}^{2}(\pi,\ \pi_{\mu})$ $\displaystyle\leq
2\int_{\mathbb{R}^{d}}\|x\|_{2}^{2}\pi(x)\left(2M+e^{2M}-1\right)dx$
$\displaystyle\leq 2\left(2M+e^{2M}-1\right)E_{\pi}\left[\|x\|^{2}\right]$
$\displaystyle\leq 2\left(2M+e^{2M}-1\right)E_{2}$ $\displaystyle\leq
8.24\sum_{i}L_{i}\mu^{1+\alpha_{i}}d^{\frac{2}{p}}E_{2}$ $\displaystyle\leq
8.24NL\mu^{1+\alpha}d^{\frac{2}{p}}E_{2},$

where in the last inequality $M<0.05$ ensures that $e^{2M}-1\leq 2.12M$. This
gives the desired result.

∎

##  Appendix E Convexification of non-convex domain

###  E.1 Proof of Lemma 4.1

######  Lemma E.1.

For function $V$ defined as

$V(\ x)=\inf_{\begin{subarray}{c}\\{\ x_{i}\\}\subset\Omega,\\\
\left\\{\lambda_{i}\big{|}\sum_{i}\lambda_{i}=1\right\\}\\\
\text{s.t.},\sum_{i}\lambda_{i}\ x_{i}=\
x\end{subarray}}\left\\{\sum_{i=1}^{l}\lambda_{i}U(\ x_{i})\right\\},$ (E.1)

$\forall\ x\in\mathbb{B}(0,R)$, $\inf_{\left\|x\right\|=R}U(x)\leq V(\
x)\leq\sup_{\left\|x\right\|=R}U(x)$.

###### Proof.

First, by definition of $V$ inside $\mathbb{B}(0,R)$, we show that for any
linear combination of the form $\sum_{i}\lambda_{i}U(\ x_{i})$
where$\sum_{i}\lambda_{i}=1,$ we can find another representation
$\sum_{j}\lambda_{j}U(\ x_{j})$ where $\sum_{j}\lambda_{j}=1$ and
$\left\|x_{j}\right\|=R$ such that $\sum_{j}\lambda_{j}U(\
x_{j})\leq\sum_{i}\lambda_{i}U(\ x_{i})$. This follows straightforwardly as
follows.

For any $\ x_{j}\in\\{\ x_{i}\\}$, such that $\left\|\bar{x}_{j}\right\|>R$,
there exists a new convex combination $\\{\
x_{i}\\}\bigcup\\{\bar{x}_{j}\\}\setminus\\{\ x_{j}\\}$ with
$\left\|\bar{x}_{j}\right\|=R$, such that $\sum_{i}\lambda_{i}U(\
x_{i})\geq\tilde{\lambda}_{j}U(\bar{x}_{j})+\sum_{i\neq
j}\tilde{\lambda}_{i}U(\ x_{i})$. In this case, we choose $\bar{x}_{j}$ where
$\left\|\bar{x}_{j}\right\|=R$, such that:

$\displaystyle\bar{x}_{j}$
$\displaystyle=\dfrac{1-\bar{\lambda}_{j}}{1-\lambda_{j}}\
x+\dfrac{\bar{\lambda}_{j}-\lambda_{j}}{1-\lambda_{j}}\
x_{j},\>\lambda_{j}<\bar{\lambda}_{j}<1,$ $\displaystyle=\bar{\lambda}_{j}\
x_{j}+\left(\dfrac{1-\bar{\lambda}_{j}}{1-\lambda_{j}}\right)\left(\sum_{i\neq
j}\lambda_{i}\ x_{i}\right).$ (E.2)

Since $U$ is convex on $\Omega$,

$U(\bar{x}_{j})\leq\bar{\lambda}_{j}U(\
x_{j})+\left(\dfrac{1-\bar{\lambda}_{j}}{1-\lambda_{j}}\right)\left(\sum_{i\neq
j}\lambda_{i}U(\ x_{i})\right).$ (E.3)

On the other hand,$x$ can be represented as a convex combination of $\\{\
x_{i}\\}\bigcup\\{\bar{x}_{j}\\}\setminus\\{\ x_{j}\\}$:

$\
x=\dfrac{\lambda_{j}}{\bar{\lambda}_{j}}\bar{x}_{j}+\left(1-\dfrac{\lambda_{j}}{\bar{\lambda}_{j}}\dfrac{1-\bar{\lambda}_{j}}{1-\lambda_{j}}\right)\left(\sum_{i\neq
j}\lambda_{i}\ x_{i}\right)=\tilde{\lambda}_{j}\bar{x}_{j}+\sum_{i\neq
j}\tilde{\lambda}_{i}\ x_{i},$ (E.4)

and that

$\displaystyle\sum_{i}\lambda_{i}U(\ x_{i})$
$\displaystyle\geq\dfrac{\lambda_{j}}{\bar{\lambda}_{j}}U(\bar{x}_{j})+\left(1-\dfrac{\lambda_{j}}{\bar{\lambda}_{j}}\dfrac{1-\bar{\lambda}_{j}}{1-\lambda_{j}}\right)\left(\sum_{i\neq
j}\lambda_{i}U(\ x_{i})\right)$
$\displaystyle=\tilde{\lambda}_{j}U(\bar{x}_{j})+\sum_{i\neq
j}\tilde{\lambda}_{i}U(\ x_{i}).$ (E.5)

As a result, $V(\ x)$ can be represented as

$V(\ x)=\inf_{\begin{subarray}{c}\\{\ x_{j}\\}\subset\Omega,\\\
\left\\{\lambda_{j}\big{|}\sum_{j}\lambda_{j}=1\right\\}\\\
\text{s.t.},\sum_{j}\lambda_{j}\ x_{j}=\
x,\,\left\|x_{i}\right\|=R\end{subarray}}\left\\{\sum_{j}\lambda_{j}U(\
x_{j})\right\\}.$ (E.6)

By the representation of $V$ inside $\mathbb{B}(0,R)$, we obtain
$\inf_{\left\|\bar{x}\right\|=R}U(\bar{x})\leq V(\
x)\leq\sup_{\left\|\bar{x}\right\|=R}U(\bar{x}).$ ∎

###  E.2 Proof of Lemma 4.2

######  Lemma E.2.

For $U$ satisfying $\alpha$-mixture weakly smooth and
$\left(\mu,\theta\right)$-degenerated convex outside the ball radius $R$,
there exists $\hat{U}\in C^{1}(\mathbb{R}^{d})$ with a Hessian that exists
everywhere on $\mathbb{R}^{d}$, and $\hat{U}$ is
$\left(\left(1-\theta\right)\frac{\mu}{2},\theta\right)$-degenerated convex on
$\mathbb{R}^{d}$ (that is
$\nabla^{2}\hat{U}(x)\succeq\left(1-\theta\right)\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}I_{d}$),
such that

$\displaystyle\sup\left(\hat{U}(\ x)-U(\ x)\right)$
$\displaystyle-\inf\left(\hat{U}(\ x)-U(\
x)\right)\leq\sum_{i}L_{i}R^{1+\alpha_{i}}+\frac{4\mu}{\left(2-\theta\right)}\
R^{2-\theta}.$ (E.7)

###### Proof.

Following closely to [24]’s approach, let $g(\
x)=\frac{\mu}{2\left(2-\theta\right)}\
\left(1+\left\|x\right\|^{2}\right)^{1-\frac{\theta}{2}}$ for $0\leq\theta<1$.
The gradient of $g\left(x\right)$ is $\nabla g(\
x)=\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}x$ and
the Hessian of $g\left(x\right)$ is

$\displaystyle\nabla^{2}g(\ x)$
$\displaystyle=\frac{\mu}{2}\left[\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}I_{d}-\theta\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}-1}xx^{T}\right]$
$\displaystyle\preceq\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}I_{d}.$
(E.8)

On the other hand, we also have

$\displaystyle\nabla^{2}g(\ x)$
$\displaystyle=\frac{\mu}{2}\left[\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}I_{d}-\theta\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}-1}xx^{T}\right]$
$\displaystyle=\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}-1}\left[I_{d}+I_{d}\left\|x\right\|^{2}-\theta\left\|x\right\|^{2}\frac{xx^{T}}{\left\|x\right\|^{2}}\right]$
$\displaystyle=\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}-1}\left[I_{d}+I_{d}\left(1-\theta\right)\left\|x\right\|^{2}+\theta\left\|x\right\|^{2}\left(I_{d}-\frac{xx^{T}}{\left\|x\right\|^{2}}\right)\right]$
$\displaystyle\succeq\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}-1}\left(\left(1-\theta\right)\left\|x\right\|^{2}+1\right)I_{d}$
$\displaystyle\succeq\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}-1}\left(\left(1-\theta\right)\left(\left\|x\right\|^{2}+1\right)\right)I_{d}$
$\displaystyle\succeq\left(1-\theta\right)\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}I_{d}.$
(E.9)

We adapt [35] by denoting
$\tilde{U}\left(x\right)=U\left(x\right)-g\left(x\right).$ Since
$U\left(x\right)$ is $\left(\mu,\theta\right)$-degenerated convex outside the
ball, we deduce for every $\left\|x\right\|\geq R,$

$\displaystyle\nabla^{2}\tilde{U}\left(x\right)$
$\displaystyle=\nabla^{2}U\left(x\right)-\nabla^{2}g\left(x\right)$
$\displaystyle\succeq\mu\left(1+\left\|x\right\|{}^{2}\right)^{-\frac{\theta}{2}}I_{d}-\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}I_{d}$
$\displaystyle\succeq\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}I_{d},$
(E.10)

which implies that $\tilde{U}\left(x\right)$ is
$\left(\frac{\mu}{2},\theta\right)$-degenerated convex outside the ball. Now,
we construct $\hat{U}(\ x)$ so that it is twice differentiable, degenerated
convex on all $\mathbb{R}^{d}$ and differs from $U(\ x)$ less than
$4LR^{1+\alpha}+4LR^{1+\ell+\alpha}+\frac{4\mu}{\left(2-\theta\right)}\
R^{2-\theta}$. Based on the same construction of [24], we first define the
function $V$ as the convex extension [35] of $\tilde{U}$ from domain
$\Omega=R^{d}\setminus\mathbb{B}\left(0,R\right)$ to its convex hull
$\Omega^{co}$, $V\left(x\right)=\inf\left\\{\sum_{i}\lambda_{i}\tilde{U}(\
x_{i})\right\\}$ for every $x\in\mathbb{R}^{d}.$ Since $\tilde{U}(\ x)$ is
convex in $\Omega$, $V(\ x)=\tilde{U}(\ x)$ for $\ x\in\Omega$. By Lemma 4.1,
$V(\ x)$ is convex on the entire domain $R^{d}$ and $V(\ x)$ can be
represented as

$V(\ x)=\inf_{\begin{subarray}{c}\\{\ x_{j}\\}\subset\Omega,\\\
\left\\{\lambda_{j}\big{|}\sum_{j}\lambda_{j}=1\right\\}\\\
\text{s.t.},\sum_{j}\lambda_{j}\ x_{j}=\
x,\mathrm{and}\left\|x_{i}\right\|=R\end{subarray}}\left\\{\sum_{j}\lambda_{j}\tilde{U}(\
x_{j})\right\\}.$ (E.11)

Therefore, $\forall\ x\in\mathbb{B}(0,R)$,
$\inf_{\left\|\bar{x}\right\|=R}\tilde{U}(\bar{x})\leq V(\
x)\leq\sup_{\left\|\bar{x}\right\|=R}\tilde{U}(\bar{x})$. Next we construct
$\tilde{V}(\ x)$ to be a smoothing of $V$ on
$\mathbb{B}\left(0,R+\epsilon\right)$. Consider the function
$\varphi{\displaystyle(x)}$ of a variable $x$ in $\mathbb{R}^{d}$ defined by

${\displaystyle\varphi(x)=\begin{cases}Ce^{-1/(1-\left\|x\right\|^{2})}&\text{
if }\left\|x\right\|<1\\\ 0&\text{ if }\left\|x\right\|\geq 1\end{cases}}$
(E.12)

where the numerical constant $C$ ensures normalization. Let
${\displaystyle\varphi_{\delta}(x)=\delta^{-d}\varphi(\delta^{-1}x)}$ be a
smooth function supported on the ball $\mathbb{B}(0,\delta)$. Define

$\displaystyle\tilde{V}(\ x)$ $\displaystyle=\int V(\ y)\varphi_{\delta}(\
x-y)dy$ $\displaystyle=\int V(\ x-y)\varphi_{\delta}(y)dy$
$\displaystyle=E_{y}\left[V(x-y)\right].$ (E.13)

The third equality implies that for any $x$ and $z\in\mathbb{R}^{d}$,

$\displaystyle\left\langle\nabla\tilde{V}(\ x)-\nabla\tilde{V}(\
z),x-z\right\rangle$ $\displaystyle=\left\langle\nabla
E_{y}\left[V(x-y)\right]-\nabla E_{y}\left[V(z-y)\right],x-z\right\rangle$
$\displaystyle\stackrel{{{}_{1}}}{{=}}\left\langle E_{y}\left[\nabla
V(x-y)\right]-E_{y}\left[\nabla V(z-y)\right],x-z\right\rangle$
$\displaystyle=\left\langle E_{y}\left[\nabla V(x-y)-\nabla
V(z-y)\right],x-z\right\rangle$ $\displaystyle=E_{y}\left\langle\nabla
V(x-y)-\nabla V(z-y),x-z\right\rangle$ $\displaystyle\geq 0,$ (E.14)

where step $1$ follows from exchangeability of gradient and integral and the
last line is because of convexity of $V$, which indicates $\tilde{V}$ is a
smooth and convex function on $R^{d}.$ Also, note that the definition of
$\tilde{V}$ implies that $\forall\left\|x\right\|<R+\epsilon$,

$\inf_{\left\|\bar{x}\right\|<R+\epsilon+\delta}V(\bar{x})\leq\tilde{V}(\
x)\leq\sup_{\left\|\bar{x}\right\|<R+\epsilon+\delta}V(\bar{x}).$ (E.15)

And by Lemma 4.1, for $\quad\forall\left\|\bar{x}\right\|<R+\epsilon$

$\displaystyle\inf_{\bar{x}\in\mathbb{B}\left(0,R+\epsilon+\delta\right)\setminus\mathbb{B}(0,R)}\tilde{U}(\bar{x})\leq\tilde{V}(\
x)\leq\sup_{\bar{x}\in\mathbb{B}\left(0,R+\epsilon+\delta\right)\setminus\mathbb{B}(0,R)}\tilde{U}(\bar{x}).$
(E.16)

Finally, we construct the auxiliary function:

$\displaystyle\hat{U}(\
x)-g\left(x\right)=\left\\{\begin{array}[]{l}\tilde{U}(\ x),\
\left\|x\right\|\geq R+2\epsilon\\\ \alpha(\ x)\tilde{U}(\ x)+(1-\alpha(\
x))\tilde{V}(\ x),\ R+\epsilon<\left\|x\right\|<R+2\epsilon\\\ \tilde{V}(\
x),\ \left\|x\right\|\leq R+\epsilon\end{array}\right.$ (E.20)

where $\alpha(\
x)=\dfrac{1}{2}\cos\left(\pi\dfrac{\left\|x\right\|^{2}}{\epsilon\left(2R+3\epsilon\right)^{2}}-\frac{\left(R+\epsilon\right)^{2}}{\epsilon\left(2R+3\epsilon\right)^{2}}\pi\right)+\dfrac{1}{2}$.
Here we know that $\tilde{U}(\ x)$ is convex and smooth in
$\mathbb{R}^{d}\setminus\mathbb{B}\left(0,R\right)$; $\tilde{V}(\ x)$ is also
convex and smooth in
$\mathbb{R}^{d}\setminus\mathbb{B}\left(0,R+\epsilon\right)$. Hence for
$R+\epsilon<\left\|x\right\|<R+2\epsilon$,

$\displaystyle\nabla^{2}\left(\hat{U}(\ x)-g\left(x\right)\right)$
$\displaystyle=\nabla^{2}\tilde{U}(\ x)+\nabla^{2}\left((1-\alpha(\
x))(\tilde{V}(\ x)-\tilde{U}(\ x))\right)$ $\displaystyle=\alpha(\
x)\nabla^{2}\tilde{U}(\ x)+(1-\alpha(\ x))\nabla^{2}\tilde{V}(\ x)$
$\displaystyle-\nabla^{2}\alpha(\ x)\left(\tilde{V}(\ x)-\tilde{U}(\
x)\right)-2\nabla\alpha(\ x)\left(\nabla\tilde{V}(\ x)-\nabla\tilde{U}(\
x)\right)^{T}$ $\displaystyle\succeq-\nabla^{2}\alpha(\ x)\left(\tilde{V}(\
x)-\tilde{U}(\ x)\right)-2\nabla\alpha(\ x)\left(\nabla\tilde{V}(\
x)-\nabla\tilde{U}(\ x)\right)^{T}.$ (E.21)

Note that for $R+\epsilon<\left\|x\right\|<R+2\epsilon$, we have

$\displaystyle\left\|\nabla g(\ x)-\nabla g(\ x-y)\right\|$
$\displaystyle=\left\|\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}x-\frac{\mu}{2}\left(1+\left\|x-y\right\|^{2}\right)^{-\frac{\theta}{2}}\left(x-y\right)\right\|$
(E.22)
$\displaystyle\leq\left\|\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}x-\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}\left(x-y\right)\right\|$
$\displaystyle+\left\|\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}\left(x-y\right)-\frac{\mu}{2}\left(1+\left\|x-y\right\|^{2}\right)^{-\frac{\theta}{2}}\left(x-y\right)\right\|$
$\displaystyle\leq\frac{\mu}{2}\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}\left\|y\right\|+\frac{\mu}{2}\left|\left(1+\left\|x\right\|^{2}\right)^{-\frac{\theta}{2}}-\left(1+\left\|x-y\right\|^{2}\right)^{-\frac{\theta}{2}}\right|\left\|x-y\right\|$
$\displaystyle\leq\frac{\mu}{2}\left(1+\left(R+\epsilon\right){}^{2}\right)^{-\frac{\theta}{2}}\delta+\frac{\mu}{2}\frac{\left|\left(1+\left\|x\right\|^{2}\right)^{\frac{\theta}{2}}-\left(1+\left\|x-y\right\|^{2}\right)^{\frac{\theta}{2}}\right|}{\left(1+\left\|x\right\|^{2}\right)^{\frac{\theta}{2}}\left(1+\left\|x-y\right\|^{2}\right)^{\frac{\theta}{2}}}\left\|\left(x-y\right)\right\|$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}\frac{\mu}{2}\left(1+\left(R+\epsilon\right){}^{2}\right)^{-\frac{\theta}{2}}\delta+\frac{\mu}{2}\frac{\left|\left(1+\left\|x\right\|^{2}\right)-\left(1+\left\|x-y\right\|^{2}\right)\right|}{\left(1+\left\|x\right\|^{2}\right)^{\frac{\theta}{2}}\left(1+\left\|x-y\right\|^{2}\right)^{\frac{\theta}{2}}}\left\|\left(x-y\right)\right\|$
$\displaystyle\leq\frac{\mu}{2}\left(1+\left(R+\epsilon\right){}^{2}\right)^{-\frac{\theta}{2}}\delta+\frac{\mu}{2}\frac{\left|\left(\left\|x\right\|-\left\|x-y\right\|\right)\left(\left\|x\right\|+\left\|x-y\right\|\right)\right|}{\left(1+\left\|x\right\|^{2}\right)^{\frac{\theta}{2}}\left(1+\left\|x-y\right\|^{2}\right)^{\frac{\theta}{2}}}\left\|\left(x-y\right)\right\|$
$\displaystyle\stackrel{{{}_{2}}}{{\leq}}\frac{\mu}{2}\left(1+\left(R+\epsilon\right){}^{2}\right)^{-\frac{\theta}{2}}\delta+\frac{\mu}{2}\frac{\left\|y\right\|\left(\left\|x\right\|+\left\|x-y\right\|\right)}{\left(1+\left\|x\right\|^{2}\right)^{\frac{\theta}{2}}\left(1+\left\|x-y\right\|^{2}\right)^{\frac{\theta}{2}}}\left\|\left(x-y\right)\right\|$
$\displaystyle\leq\frac{\mu}{2}\left(1+\left(R+\epsilon\right){}^{2}\right)^{-\frac{\theta}{2}}\delta+\frac{\mu}{2}\frac{2\left(R+2\epsilon+\delta\right)^{2}\delta}{\left(1+\left(R+\epsilon\right)^{2}\right)^{\frac{\theta}{2}}\left(1+\left(R+\epsilon-\delta\right)^{2}\right)^{\frac{\theta}{2}}},$
(E.23)

where $1$ follows from Lemma F.15, while $2$ is due to triangle inequality. As
a result, we get

$\displaystyle\left\|\nabla\tilde{V}(\ x)-\nabla\tilde{U}(\ x)\right\|$
$\displaystyle=\int\left\|\nabla\tilde{U}(\ x-\ y)-\nabla\tilde{U}(\
x)\right\|\varphi_{\delta}(\ y)dy$
$\displaystyle\leq\sum_{i}L_{i}\delta^{\alpha_{i}}+\left\|\nabla g(\ x)-\nabla
g(\ x-y)\right\|$ $\displaystyle\leq
NL\delta^{\alpha}+\frac{\mu}{2}\left(1+\left(R+\epsilon\right){}^{2}\right)^{-\frac{\theta}{2}}\delta$
(E.24)
$\displaystyle+\frac{\mu}{2}\frac{2\left(R+\epsilon-\delta\right)^{2}\delta}{\left(1+\left(R+\epsilon\right)^{2}\right)^{\frac{\theta}{2}}\left(1+\left(R+\epsilon-\delta\right)^{2}\right)^{\frac{\theta}{2}}}.$
(E.25)

On the other hand, we also acquire

$\displaystyle|\tilde{U}(\mathrm{x})-\tilde{U}(x-\mathrm{y})|$
$\displaystyle\leq\mathrm{\max}\left\\{\left\langle\nabla
U(\mathrm{x-y}),\mathrm{y}\right\rangle,\left\langle\nabla
U(\mathrm{x}),\mathrm{-y}\right\rangle\right\\}$
$\displaystyle+\sum_{i}\frac{L}{1+\alpha_{i}}\|\mathrm{y}\|^{\alpha_{i}+1}+\left|g\left(x\right)-g\left(x-y\right)\right|$
$\displaystyle\mathrm{\leq\max}\left\\{\left\langle\nabla
U(\mathrm{x-y}),\mathrm{y}\right\rangle,\left\langle\nabla
U(\mathrm{x}),\mathrm{-y}\right\rangle\right\\}+\sum_{i}\frac{L}{1+\alpha_{i}}\|\mathrm{y}\|^{\alpha_{i}+1}$
$\displaystyle+\left|\frac{\mu}{2\left(2-\theta\right)}\
\left(1+\left\|x\right\|^{2}\right)^{1-\frac{\theta}{2}}-\frac{\mu}{2\left(2-\theta\right)}\
\left(1+\left\|x-y\right\|^{2}\right)^{1-\frac{\theta}{2}}\right|$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}\mathrm{\max}\left\\{\sum_{i}L_{i}\left\|\mathrm{x-y}\right\|^{\alpha_{i}}\left\|y\right\|,\sum_{i}L_{i}\left\|\mathrm{x}\right\|^{\alpha_{i}}\left\|y\right\|\right\\}$
$\displaystyle+\sum_{i}\frac{L}{1+\alpha_{i}}\|\mathrm{y}\|^{\alpha_{i}+1}+\frac{\mu}{2\left(2-\theta\right)}\left|\left(1+\left\|x\right\|^{2}\right)-\left(1+\left\|x-y\right\|^{2}\right)\right|$
(E.26) $\displaystyle\leq
L\left\|y\right\|\mathrm{\max}\left\\{\sum_{i}L_{i}\left\|\mathrm{x-y}\right\|^{\alpha_{i}},\sum_{i}L_{i}\left\|\mathrm{x}\right\|^{\alpha_{i}}\right\\}$
$\displaystyle+\sum_{i}\frac{L}{1+\alpha_{i}}\|\mathrm{y}\|^{\alpha_{i}+1}+\frac{\mu}{2\left(2-\theta\right)}\left|\left(\left\|x\right\|-\left\|x-y\right\|\right)\left(\left\|x\right\|+\left\|x-y\right\|\right)\right|$
(E.27) $\displaystyle\leq
L\left\|y\right\|\mathrm{\max}\left\\{\sum_{i}L_{i}\left\|\mathrm{x-y}\right\|^{\alpha_{i}},\sum_{i}L_{i}\left\|\mathrm{x}\right\|^{\alpha_{i}}\right\\}+$
(E.28)
$\displaystyle+\sum_{i}\frac{L}{1+\alpha_{i}}\|\mathrm{y}\|^{\alpha_{i}+1}+\frac{\mu}{2\left(2-\theta\right)}\left(\left\|x\right\|+\left\|x-y\right\|\right)\left\|y\right\|,$
(E.29)

where $1$ follows again from Lemma F.15 and the last inequality is because of
triangle inequality. Hence for $R+\epsilon<\left\|x\right\|<R+2\epsilon$,
$\left\|y\right\|\leq\delta$,

$\displaystyle\tilde{V}(\ x)-\tilde{U}(\ x)$
$\displaystyle=\int\left(\tilde{U}(\ x-\ y)-\tilde{U}(\
x)\right)\varphi_{\delta}(\ y)d\ y$ $\displaystyle\leq
L\left\|y\right\|\mathrm{\max}\left\\{\sum_{i}L_{i}\left\|\mathrm{x-y}\right\|^{\alpha_{i}},\sum_{i}L_{i}\left\|\mathrm{x}\right\|^{\alpha_{i}}\right\\}+$
$\displaystyle+\sum_{i}\frac{L}{1+\alpha_{i}}\|\mathrm{y}\|^{\alpha_{i}+1}+\frac{\mu}{2\left(2-\theta\right)}\left(\left\|x\right\|+\left\|x-y\right\|\right)\left\|y\right\|$
$\displaystyle\leq
L\delta\left[\sum_{i}L_{i}\left(R+2\epsilon+\delta\right)^{\alpha_{i}}\right]+$
$\displaystyle+\sum_{i}\frac{L}{1+\alpha_{i}}\delta^{\alpha_{i}+1}+\frac{\mu}{\left(2-\theta\right)}\left(R+2\epsilon+\delta\right)\delta$

Therefore, when $R+\epsilon<\left\|x\right\|<R+2\epsilon$,

$\displaystyle\nabla^{2}\left(\hat{U}(\ x)-g\left(x\right)\right)$
$\displaystyle\succeq-\frac{\left(R+\epsilon\right)^{2}\pi\left(L\delta\left[\sum_{i}L_{i}\left(R+2\epsilon+\delta\right)^{\alpha_{i}}\right]\right)}{\epsilon\left(2R+3\epsilon\right)}I_{d}$
$\displaystyle-\frac{\left(R+\epsilon\right)^{2}\pi\left(+\sum_{i}\frac{L}{1+\alpha_{i}}\delta^{\alpha_{i}+1}+\frac{\mu}{\left(2-\theta\right)}\left(R+2\epsilon+\delta\right)\delta\right)}{\epsilon\left(2R+3\epsilon\right)}I_{d}$
$\displaystyle-\frac{\left(R+\epsilon\right)^{4}\pi^{2}\left(NL\delta^{\alpha}+\frac{\mu}{2}\left(1+\left(R+\epsilon\right){}^{2}\right)^{-\frac{\theta}{2}}\delta\right)}{\epsilon^{2}\left(2R+3\epsilon\right)}I_{d}$
$\displaystyle-\frac{\left(R+\epsilon\right)^{4}\pi^{2}\left(\frac{\mu}{2}\frac{2\left(R+\epsilon-\delta\right)^{2}\delta}{\left(1+\left(R+\epsilon\right)^{2}\right)^{\frac{\theta}{2}}\left(1+\left(R+\epsilon-\delta\right)^{2}\right)^{\frac{\theta}{2}}}\right)}{\epsilon^{2}\left(2R+3\epsilon\right)}I_{d}.$
(E.30)

Taking the limit when $\delta\rightarrow 0^{+}$, we obtain that for
$R+\epsilon<\left\|x\right\|<R+2\epsilon$, $\nabla^{2}\left(\hat{U}(\
x)-g\left(x\right)\right)$ is positive semi-definite; hence it is positive
semi-definite on the entire $R^{d}$, or $\hat{U}(\ x)-g\left(x\right)$ is
convex on $\mathbb{R}^{d}$. From (E.16), we know that for
$R+\epsilon<\left\|x\right\|<R+2\epsilon$,

$\displaystyle\inf_{\bar{x}\in\mathbb{B}\left(0,R+2\epsilon\right)\setminus\mathbb{B}(0,R)}\tilde{U}(\bar{x})$
$\displaystyle\leq\hat{U}(\
x)-g\left(x\right)\leq\sup_{\bar{x}\in\mathbb{B}\left(0,R+2\epsilon\right)\setminus\mathbb{B}(0,R)}\tilde{U}(\bar{x}).$
(E.31)

Therefore,

$\displaystyle\sup\left(\hat{U}(\ x)-U(\ x)\right)-\inf\left(\hat{U}(\ x)-U(\
x)\right)$ $\displaystyle=\sup\left(\hat{U}(\ x)-g\left(x\right)-\tilde{U}(\
x)\right)-\inf\left(\hat{U}(\ x)-g\left(x\right)-\tilde{U}(\ x)\right)$ (E.32)
$\displaystyle\leq
2\left(\sup_{\bar{x}\in\mathbb{B}\left(0,R+2\epsilon\right)\setminus\mathbb{B}(0,R)}\tilde{U}(\bar{x})-\inf_{\bar{x}\in\mathbb{B}\left(0,R+2\epsilon\right)\setminus\mathbb{B}(0,R)}\tilde{U}(\bar{x})\right)$
$\displaystyle\leq
2\left(\sup_{\bar{x}\in\mathbb{B}\left(0,R+2\epsilon\right)}\tilde{U}(\bar{x})-\inf_{\bar{x}\in\mathbb{B}\left(0,R+2\epsilon\right)}\tilde{U}(\bar{x})\right).$
(E.33)

Since $U$ is $\left(\alpha,\ell\right)$-weakly smooth and $\nabla U(0)=0$, we
deduce

$\displaystyle\left|U(\ x)-U(0)\right|$ $\displaystyle=\left|U(\ x)-U(0)-\
\left\langle x,\nabla U(0)\right\rangle\right|$
$\displaystyle\leq\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\left\|x\right\|^{1+\alpha_{i}}$
$\displaystyle\leq\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\left(R+2\epsilon\right)^{1+\alpha_{i}}$
$\displaystyle\leq\sum_{i}L_{i}R^{1+\alpha_{i}}$ (E.34)

and

$\displaystyle\left|g(\ x)\right|$
$\displaystyle=\left|\frac{\mu}{2\left(2-\theta\right)}\
\left(1+\left\|x\right\|^{2}\right)^{1-\frac{\theta}{2}}\right|$
$\displaystyle\leq\frac{\mu}{2\left(2-\theta\right)}\
\left(1+\left(R+2\epsilon\right)^{2}\right)^{1-\frac{\theta}{2}}$
$\displaystyle\leq\frac{\mu}{\left(2-\theta\right)}\ R^{2-\theta}.$ (E.35)

So for $\forall\left\|x\right\|\leq\left(R+2\epsilon\right)$, $\epsilon$ is
sufficiently small,

$\displaystyle\sup_{\bar{x}\in\mathbb{B}\left(R+2\epsilon\right)}\tilde{U}(\bar{x})-\inf_{\bar{x}\in\mathbb{B}\left(R+2\epsilon\right)}$
$\displaystyle\tilde{U}(\bar{x})\leq\sum_{i}L_{i}R^{1+\alpha_{i}}+\frac{2\mu}{\left(2-\theta\right)}\
R^{2-\theta}.$

As a result, we get

$\displaystyle\sup\left(\hat{U}(\ x)-U(\ x)\right)-\inf$
$\displaystyle\left(\hat{U}(\ x)-U(\ x)\right)\leq
2\sum_{i}L_{i}R^{1+\alpha_{i}}+\frac{4\mu}{\left(2-\theta\right)}\
R^{2-\theta}.$

∎

######  Remark E.1.

When $\theta=0,$ the $\left(\mu,\theta\right)$-degenerated convex outside the
ball is equivalent to the $\mu$-strongly convex outside the ball, we achieve a
result for strongly convex outside the ball similar to [24] but for
$\left(\alpha,\ell\right)$-weakly smooth instead of smooth. The constant could
be improved by a factor of $2$ if we take $\epsilon$ to be arbitrarily small.

###  E.3 Proof of lemma 4.3

######  Lemma E.3.

For $U$ satisfying $\gamma-$Poincaré, $\alpha$-mixture weakly smooth with
$\alpha_{N}=1$ and $2-$dissipative, there exists $\breve{U}\in
C^{1}(\mathbb{R}^{d})$ with a Hessian that exists everywhere on $R^{d}$, and
$\breve{U}$ is log-Sobolev on $\mathbb{R}^{d}$ such that

$\sup\left(\breve{U}(\ x)-U(\ x)\right)-\inf\left(\breve{U}(\ x)-U(\
x)\right)\leq 2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}.$
(E.36)

###### Proof.

First, given $R>0,$ let
$\overline{U}(\mathrm{x}):=U(\mathrm{x})+\frac{L_{N}+\lambda_{0}}{2}\left\|x\right\|^{2}$
for $\lambda_{0}=\frac{2L}{R^{1-\alpha}}$, we obtain the following property

$\displaystyle\left\langle\nabla\overline{U}(\mathrm{x})-\nabla\overline{U}(\mathrm{y}),x-y\right\rangle$
$\displaystyle=\left\langle\nabla\left(U(\mathrm{x})+\frac{L_{N}+\lambda_{0}}{2}\left\|x\right\|^{2}\right)-\nabla\left(U(\mathrm{y})+\frac{L_{N}+\lambda_{0}}{2}\left\|y\right\|^{2}\right),x-y\right\rangle$
(E.37) $\displaystyle=\left\langle\nabla U(\mathrm{x})-\nabla
U(\mathrm{y})+(L_{N}+\lambda_{0})\left(x-y\right),x-y\right\rangle$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\geq}}-\sum_{i<N}L_{i}\left\|x-y\right\|^{1+\alpha}+\lambda_{0}\left\|x-y\right\|^{2}$
$\displaystyle\geq\frac{\lambda_{0}}{2}\left\|x-y\right\|^{2}\,for\,\left\|x-y\right\|\geq\left(\frac{NL}{\lambda_{0}}\right)^{\frac{1}{1-\alpha_{1}}}=R,$
(E.38)

where $(i)$ follows from Assumption 2.2. This implies that
$\overline{U}(\mathrm{x})$ is $\lambda_{0}-$ strongly convex outside the ball
$B_{R}=\left\\{x:\left\|x\right\|\leq R\right\\}$. Though
$\overline{U}(\mathrm{x})$ behaves differently than Lemma 4.2 assumptions,
with some additional verifications, we still can apply Lemma 4.2 to derive the
result. We sketch the proof as follows. There exists $\hat{U}\in
C^{1}(\mathbb{R}^{d})$ with a Hessian that exists everywhere on $R^{d}$,

$\displaystyle\hat{U}(\
x)-\frac{\lambda_{0}}{4}\left\|x\right\|^{2}=\left\\{\begin{array}[]{l}\tilde{\overline{U}}(\
x),\ \left\|x\right\|\geq R+2\epsilon\\\ \alpha(\ x)\tilde{\overline{U}}(\
x)+(1-\alpha(\ x))\tilde{V}(\ x),\ R+\epsilon<\left\|x\right\|<R+2\epsilon\\\
\tilde{V}(\ x),\ \left\|x\right\|\leq R+\epsilon\end{array}\right.$ (E.42)

where $\alpha(\ x)$ is defined as before. Both $\tilde{\overline{U}}(\ x)$ and
$\tilde{V}(\ x)$ are convex and smooth in
$\mathbb{R}^{d}\setminus\mathbb{B}\left(0,R\right)$ and for
$R+\epsilon<\left\|x\right\|<R+2\epsilon$, $\left\|y\right\|\leq\delta$,

$\displaystyle\nabla^{2}\left(\hat{U}(\
x)-\frac{\lambda_{0}}{4}\left\|x\right\|^{2}\right)$
$\displaystyle\succeq-\nabla^{2}\alpha(\ x)\left(\tilde{V}(\
x)-\tilde{\overline{U}}(\ x)\right)-2\nabla\alpha(\ x)\left(\nabla\tilde{V}(\
x)-\nabla\tilde{\overline{U}}(\ x)\right)^{T}.$ (E.43)

In this case, we have

$\displaystyle\left\|\nabla\tilde{V}(\ x)-\nabla\tilde{\overline{U}}(\
x)\right\|$ $\displaystyle=\left\|\nabla\int\left(\overline{U}(\ x-\
y)-\overline{U}(\ x)\right)\varphi_{\delta}(\ y)dy\right\|$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}\left\|\nabla\int\left(U(\ x-\ y)-U(\
x)\right)\varphi_{\delta}(\ y)dy\right\|$
$\displaystyle+\lambda_{0}\int\left\|y\right\|\varphi_{\delta}(\ y)dy$
$\displaystyle\leq\left\|\int\left(\nabla U(\ x-\ y)-\nabla U(\
x)\right)\varphi_{\delta}(\ y)dy\right\|+\lambda_{0}\delta$
$\displaystyle\leq\sum_{i}L_{i}\delta^{\alpha_{1}}+\lambda_{0}\delta,$ (E.44)

where $1$ holds by triangle inequality and the last line is because of
$\left(\alpha,\ell\right)-$weakly smooth assumption, while

$\displaystyle\left|\tilde{\overline{U}}(\mathrm{x})-\tilde{\overline{U}}(x-\mathrm{y})\right|$
$\displaystyle\stackrel{{{}_{1}}}{{\leq}}\left|\overline{U}(\mathrm{x})-\overline{U}(x-\mathrm{y})\right|+\left|\frac{L+\lambda_{0}}{2}\left\|x\right\|^{2}-\frac{L+\lambda_{0}}{2}\left\|x-y\right\|^{2}\right|$
$\displaystyle\stackrel{{{}_{2}}}{{\leq}}\left\\{\left\langle\nabla
U(\mathrm{x-y}),\mathrm{y}\right\rangle\vee\left\langle\nabla
U(\mathrm{x}),\mathrm{-y}\right\rangle\right\\}+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\left\|y\right\|^{\alpha_{i}+1}$
$\displaystyle+\frac{L_{N}+\lambda_{0}}{2}\left|\left\|x\right\|^{2}-\left\|x-y\right\|^{2}\right|$
(E.45) $\displaystyle\mathrm{\leq}\left\\{\left\langle\nabla
U(\mathrm{x-y}),\mathrm{y}\right\rangle\vee\left\langle\nabla
U(\mathrm{x}),\mathrm{-y}\right\rangle\right\\}+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\left\|y\right\|^{\alpha_{i}+1}$
$\displaystyle+\frac{L_{N}+\lambda_{0}}{2}\left(\left\|x\right\|-\left\|x-y\right\|\right)\left(\left\|x\right\|+\left\|x-y\right\|\right)$
(E.46)
$\displaystyle\leq\left\\{\left(\sum_{i}L_{i}\left\|\mathrm{x-y}\right\|^{\alpha_{i}}\right)\left\|y\right\|\vee\left(\sum_{i}L_{i}\left\|\mathrm{x}\right\|^{\alpha_{i}}\right)\left\|y\right\|\right\\}$
$\displaystyle+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\left\|y\right\|^{\alpha_{i}+1}+\frac{L_{N}+\lambda_{0}}{2}\left\|y\right\|\mathrm{\max}\left\\{\left\|\mathrm{x-y}\right\|,\left\|\mathrm{x}\right\|\right\\}$
(E.47)
$\displaystyle\leq\sum_{i}L_{i}\left(R+2\epsilon+\delta\right)^{\alpha_{i}}\delta$
(E.48)
$\displaystyle+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\delta^{\alpha_{i}+1}+\frac{L_{N}+\lambda_{0}}{2}\left(R+2\epsilon+\delta\right)\delta,$
(E.49)

where $1$ is due to triangle inequality, $2$ follows from Assumption 1, and
the last line holds by plugging in all the limits. Taking the limit when
$\delta\rightarrow 0^{+},$ and for sufficiently small $\epsilon$, we obtain
$\hat{U}(\ x)-\frac{\lambda_{0}}{4}\left\|x\right\|^{2}$ is convex on all
$\mathbb{R}^{d}$ or $\hat{U}(\ x)$ is $\frac{\lambda_{0}}{2}$\- strongly
convex. By definition of $\overline{U}$, for
$R+\epsilon<\left\|x\right\|<R+2\epsilon$ we obtain

$\displaystyle\left|\overline{U}(\ x)-\overline{U}(0)\right|$
$\displaystyle\leq\left|U(\ x)-U(0)-\ \left\langle x,\nabla
U(0)\right\rangle\right|+\frac{L_{N}+\lambda_{0}}{2}\left\|x\right\|^{2}$
$\displaystyle\leq+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\left\|x\right\|^{\alpha_{i}+1}+\frac{L_{N}+\lambda_{0}}{2}\left\|x\right\|^{2}$
$\displaystyle\leq+\sum_{i}\frac{L_{i}}{1+\alpha_{i}}\left(R+2\epsilon+\delta\right)^{\alpha_{i}+1}+\frac{L_{N}+\lambda_{0}}{2}\left(R+2\epsilon+\delta\right)^{2}$
$\displaystyle\leq\sum_{i}L_{i}R^{1+\alpha_{i}}+\left(L_{N}+\lambda_{0}\right)R^{2}.$
(E.50)

As a result, from Lemma 4.2 we deduce

$\displaystyle\sup\left(\hat{U}(\ x)-\overline{U}(\ x)\right)$
$\displaystyle-\inf\left(\hat{U}(\ x)-\overline{U}(\ x)\right)\leq
2\sum_{i}L_{i}R^{1+\alpha_{i}}+2\left(L_{N}+\lambda_{0}\right)R^{2}.$ (E.51)

Let
$\breve{U}\left(x\right)=\hat{U}\left(x\right)-\left(\frac{L_{N}}{2}+\frac{\lambda_{0}}{4}\right)\left\|x\right\|^{2}$
then for $\left\|x\right\|>R+2\epsilon+\delta$,
$\hat{U}\left(x\right)=\overline{U}\left(x\right)$ so
$\breve{U}\left(x\right)=U\left(x\right)$. For $\left\|x\right\|\leq
R+2\epsilon+\delta$, we have

$\displaystyle\sup\left(\breve{U}(x)-U(x)\right)-\inf\left(\breve{U}(\
x)-U(x)\right)$
$\displaystyle\leq\sup\left(\hat{U}(x)+\frac{L_{N}+\lambda_{0}}{2}\left\|x\right\|^{2}-\overline{U}(x)\right)-\inf\left(\hat{U}(x)+\frac{L_{N}+\lambda_{0}}{2}\left\|x\right\|^{2}-\overline{U}(x)\right)$
$\displaystyle\leq\sup\left(\hat{U}(x)-\overline{U}(x)\right)-\inf\left(\hat{U}(x)-\overline{U}(x)\right)+\left(L_{N}+\lambda_{0}\right)\left(R+2\epsilon+\delta\right)^{2}$
$\displaystyle\leq
2\sum_{i}L_{i}R^{1+\alpha_{i}}+2\left(L_{N}+\lambda_{0}\right)R^{2}+2\left(L_{N}+\lambda_{0}\right)R^{2}.$
$\displaystyle\leq 2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}.$
(E.52)

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

$\sup\left(\breve{U}(x)-U(x)\right)-\inf\left(\breve{U}(\ x)-U(x)\right)\leq
2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}.$

Since $U(x)$ is $PI(\gamma)$, and using [21]’s Lemma 1.2 we have, $\breve{U}(\
x)$ is Poincaré with constant

$\gamma_{1}=\gamma
e^{-4\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)}.$

On the other hand, we know that
$\nabla^{2}\breve{U}\left(x\right)=\nabla^{2}\hat{U}\left(x\right)-\left(L_{N}+\frac{\lambda_{0}}{2}\right)I\succeq-
LI$ for since $\hat{U}\left(x\right)$ is $\frac{\lambda_{0}}{2}-$strongly
convex, which implies that $\nabla^{2}\breve{U}\left(x\right)$ is lower
bounded by $-LI$. In addition, for $\left\|x\right\|>R+2\epsilon+\delta$ from
$2-$dissipative assumption, we have for some $a,$
$b>0,\left\langle\nabla\breve{U}(\mathrm{x}),x\right\rangle\geq
a\left\|x\right\|^{2}-b$, while for $\left\|x\right\|\leq R+2\epsilon+\delta$

$\displaystyle\left\langle\nabla\breve{U}\left(x\right),x\right\rangle$
$\displaystyle\geq\left\langle-\nabla\left(\left(\frac{L_{N}}{2}+\frac{\lambda_{0}}{4}\right)\left\|x\right\|^{2}\right),x\right\rangle$
$\displaystyle\geq-\left(L_{N}+\frac{\lambda_{0}}{2}\right)\left\|x\right\|^{2}$
$\displaystyle\geq-\left(L_{N}+\frac{\lambda_{0}}{2}\right)R^{2}.$
$\displaystyle\geq
a\left\|x\right\|^{2}-\left(L_{N}+\frac{\lambda_{0}}{2}\right)R^{2}-aR^{2}.$

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

$\left\langle\nabla\breve{U}(\mathrm{x}),x\right\rangle\geq
a\left\|x\right\|^{2}-\left(b+\left(L_{N}+\frac{\lambda_{0}}{2}\right)R^{2}+aR^{2}\right).$

We choose $W=e^{a_{1}\left\|x\right\|^{2}}$ and $V=a_{1}\left\|x\right\|^{2}$
with $0<a_{1}=\frac{a}{4}$. One sees that $W$ satisfies Lyapunov inequality

$\displaystyle\mathcal{L}W$
$\displaystyle=\left(2a_{1}d+4a_{1}^{2}\left\|x\right\|^{2}-2a_{1}\left\langle\nabla
U(\mathrm{x}),x\right\rangle\right)W$
$\displaystyle\leq\left(2a_{1}d+4a_{1}^{2}\left\|x\right\|^{2}-2a_{1}a\left\|x\right\|^{2}+2a_{1}\left(b+\left(L_{N}+\frac{\lambda_{0}}{2}\right)R^{2}+aR^{2}\right)\right)W$
$\displaystyle\leq\left(-\frac{a^{2}}{2}\left\|x\right\|^{2}+\frac{a}{2}\left(b+\left(L_{N}+\frac{\lambda_{0}}{2}\right)R^{2}+aR^{2}+d\right)\right)W.$
(E.53)

By [5]’s Theorem 1.9, $\breve{U}\left(x\right)$ satisfies a defective log
Sobolev. In addition, by Rothaus’ lemma, a defective log-Sobolev inequality
together with the $PI(\gamma_{1})$ implies the log-Sobolev inequality with the
log Sobolev constant is
$\gamma_{2}=\frac{2}{[A+(B+2)\frac{1}{\gamma_{{}_{1}}})]}$ where

$\displaystyle A$ $\displaystyle=(1-\frac{L}{2})\frac{8}{a^{2}}+\zeta,$ (E.54)
$\displaystyle B$
$\displaystyle=2\left[\frac{2\left(\left(b+4\left(L_{N}+\frac{\lambda_{0}}{4}\right)R^{2}+aR^{2}\right)+d\right)}{a}+M_{2}\right](1-\frac{L}{2}+\frac{1}{\zeta}).$
(E.55)

where $M_{2}=\int\left\|x\right\|^{2}e^{-\breve{U}(x)}dx$. But it is well
known from Lemma 10 that $M_{2}=O(d)$, so the log-Sobolev constant is just
$O(d)$. This concludes the proof. ∎

###  E.4 Proof of lemma 4.1

######  Theorem E.1.

Suppose $\pi$ is $\gamma-$Poincaré, $\alpha$-mixture weakly smooth with
$\alpha_{N}=1$ and $2-$dissipativity (i.e.$\left\langle\nabla
U(x),x\right\rangle\geq a\left\|x\right\|^{2}-b$) for some $a,b>0$, and for
any $x_{0}\sim p_{0}$ with $H(p_{0}|\pi)=C_{0}<\infty$, the iterates
$x_{k}\sim p_{k}$ of LMC with step size $\eta\leq
1\wedge\frac{1}{4\gamma_{3}}\wedge\left(\frac{\gamma_{3}}{16L^{1+\alpha}}\right)^{\frac{1}{\alpha}}$satisfies

$\displaystyle H(p_{k}|\pi)\leq e^{-\gamma_{3}\epsilon
k}H(p_{0}|\pi)+\frac{8\eta^{\alpha}D_{3}}{3\gamma_{3}},$ (E.56)

where $D_{3}$ is defined as in equation (3.8) and

$\displaystyle M_{2}$
$\displaystyle=\int\left\|x\right\|^{2}e^{-\breve{U}(x)}dx=O(d)$ (E.57)
$\displaystyle\zeta$
$\displaystyle=\sqrt{2\left[\frac{2\left(b+\left(L+\frac{\lambda_{0}}{2}\right)R^{2}+aR^{2}+d\right)}{a}+M_{2}\right]\frac{e^{4\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)}}{\gamma}}$
(E.58) $\displaystyle A$ $\displaystyle=(1-\frac{L}{2})\frac{8}{a^{2}}+\zeta,$
(E.59) $\displaystyle B$
$\displaystyle=2\left[\frac{2\left(\left(b+4\left(L+\frac{\lambda_{0}}{4}\right)R^{2}+aR^{2}\right)+d\right)}{a}+M_{2}\right](1-\frac{L}{2}+\frac{1}{\zeta}),$
(E.60) $\displaystyle\gamma_{3}$ $\displaystyle=\frac{2\gamma
e^{-\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)}}{A\gamma+(B+2)e^{4\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)}}.$

Then, for any $\epsilon>0$, to achieve $H(p_{k}|\pi)<\epsilon$, it suffices to
run ULA with step size $\eta\leq
1\wedge\frac{1}{4\gamma_{3}}\wedge\left(\frac{\gamma_{3}}{16L^{1+\alpha}}\right)^{\frac{1}{\alpha}}\wedge\left(\frac{3\epsilon\gamma_{3}}{16D_{3}}\right)^{\frac{1}{\alpha}}$for
$k\geq\frac{1}{\gamma_{3}\eta}\log\frac{2H\left(p_{0}|\pi\right)}{\epsilon}$
iterations.

###### Proof.

From Lemma E.36 , we can optimize over $\zeta$ and get

$\zeta=\sqrt{2\left[\frac{2\left(b+\left(L+\frac{\lambda_{0}}{2}\right)R^{2}+aR^{2}+d\right)}{a}+M_{2}\right]\frac{1}{\gamma_{1}}}.$

By using Holley Stroock perturbation theorem [18], we have $U(x)$ is log-
Sobolev on $\mathbb{R}^{d}$ with constant

$\gamma_{3}=\frac{2\gamma
e^{-\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)}}{[A\gamma+(B+2)e^{4\left(2\sum_{i}L_{i}R^{1+\alpha_{i}}+4L_{N}R^{2}+4LR^{1+\alpha}\right)})]}.$

Applying theorem 3.1, we get the desired result.∎

###  E.5 Proof of lemma 4.1

######  Lemma E.4.

If $U$ satisfies Assumption 2.4, then

$U(x)\geq\frac{a}{2\beta}\|x\|^{\beta}+U(0)-\sum_{i}\frac{L_{i}}{\alpha_{i}+1}R^{\alpha_{i}+1}-b.$
(E.61)

###### Proof.

Using the technique of [16], let
$R=\left(\frac{2b}{a}\right)^{\frac{1}{\beta}}$, we lower bound
$U\left(x\right)$ when $\left\|x\right\|\leq R$,

$\displaystyle U(x)$ $\displaystyle=U(0)+\int_{0}^{1}\left\langle\nabla
U(tx),\ x\right\rangle dt$ $\displaystyle\geq U(0)-\int_{0}^{1}\left\|\nabla
U(tx)\right\|\left\|x\right\|dt$ $\displaystyle\geq
U(0)-\sum_{i}L_{i}\left\|x\right\|^{\alpha_{i}+1}\int_{0}^{1}t^{\alpha_{i}}dt$
$\displaystyle\geq
U(0)-\sum_{i}\frac{L_{i}}{\alpha_{i}+1}\left\|x\right\|^{\alpha_{i}+1}$
$\displaystyle\geq U(0)-\sum_{i}\frac{L_{i}}{\alpha_{i}+1}R^{\alpha_{i}+1}$
(E.62)

For $\left\|x\right\|>R$, we can lower bound $U$ as follows.

$\displaystyle U(x)$
$\displaystyle=U(0)+\int_{0}^{\frac{R}{\|x\|}}\left\langle\nabla U(tx),\
x\right\rangle dt+\int_{\frac{R}{\|x\|}}^{1}\left\langle\nabla U(tx),\
x\right\rangle dt$ $\displaystyle\geq
U(0)-\int_{0}^{\frac{R}{\left\|x\right\|}}\left\|\nabla
U(tx)\right\|\left\|x\right\|dt+\int_{\frac{R}{\left\|x\right\|}}^{1}\frac{1}{t}\left\langle\nabla
U(tx),\ tx\right\rangle dt$ $\displaystyle\geq
U(0)-\left\|x\right\|\int_{0}^{\frac{R}{\left\|x\right\|}}\sum_{i}L_{i}\left\|tx\right\|^{\alpha_{i}}dt+\int_{\frac{R}{\left\|x\right\|}}^{1}\frac{1}{t}\left(a\left\|tx\right\|^{\beta}-b\right)dt$
$\displaystyle\stackrel{{{}_{1}}}{{\geq}}U(0)-\sum_{i}L_{i}\left\|x\right\|^{\alpha_{i}+1}\int_{0}^{\frac{R}{\left\|x\right\|}}t^{\alpha_{i}}dt\
+\frac{1}{2}\int_{\frac{R}{\left\|x\right\|}}^{1}\frac{1}{t}a\left\|tx\right\|^{\beta}dt$
$\displaystyle\stackrel{{{}_{2}}}{{\geq}}U(0)-\sum_{i}\frac{L_{i}}{\alpha_{i}+1}\left\|x\right\|^{\alpha_{i}+1}\frac{R^{\alpha_{i}+1}}{\left\|x\right\|^{\alpha_{i}+1}}+\frac{a}{2}\left\|x\right\|^{\beta}\int_{\frac{R}{\left\|x\right\|}}^{1}t^{\beta-1}dt$
$\displaystyle\geq
U(0)-\sum_{i}\frac{L_{i}}{\alpha_{i}+1}R^{\alpha_{i}+1}+\frac{a}{2\beta}\left\|x\right\|^{\beta}\left(1-\frac{R^{\beta}}{\left\|x\right\|^{\beta}}\right)$
$\displaystyle\geq\frac{a}{2\beta}\left\|x\right\|^{\beta}+U(0)-\sum_{i}\frac{L_{i}}{\alpha_{i}+1}R^{\alpha_{i}+1}-b,$
(E.63)

where $1$ follows from Assumption 2.4 and $2$ uses the fact that if
$t{\displaystyle\geq\frac{R}{\left\|x\right\|}}$ then ${\displaystyle
a\left\|tx\right\|^{\beta}-b\geq\frac{a}{2}\left\|tx\right\|^{\beta}}.$ Now,
since for $\left\|x\right\|\leq R$,
$\frac{a}{2\beta}\left\|x\right\|^{\beta}\leq b$, we combine the inequality
for $\left\|x\right\|\leq R$ and get

$U(x)\geq\frac{a}{2\beta}\left\|x\right\|^{\beta}+U(0)-\sum_{i}\frac{L_{i}}{\alpha_{i}+1}R^{\alpha_{i}+1}-b.$
(E.64)

∎

###  E.6 Proof of Lemma 5

######  Lemma E.5.

Assume that $U$ satisfies Assumption 2.4, then for $\pi=e^{-U}$ and any
distribution $\rho$, we have

$\frac{4\beta}{a}\left[\mathrm{H}(\rho|\pi)+\tilde{d}+\tilde{\mu}\right]\geq\mathrm{E}_{\rho}\left[\left\|x\right\|{}^{\beta}\right],$
(E.65)

where

$\displaystyle\tilde{\mu}$
$\displaystyle=\frac{1}{2}\log(\frac{2}{\beta})+\sum_{i}\frac{L_{i}}{\alpha_{i}+1}\left(\frac{2b}{a}\right)^{\frac{\alpha_{i}+1}{\beta}}+b+|U(0)|,$
(E.66) $\displaystyle\tilde{d}$
$\displaystyle=\frac{d}{\beta}\left[\frac{\beta}{2}log\left(\pi\right)+\log\left(\frac{4\beta}{a}\right)+(1-\frac{\beta}{2})\log(\frac{d}{2e})\right].$
(E.67)

###### Proof.

Let $q(x)=e^{\frac{a}{4\beta}\left\|x\right\|{}^{\beta}-U(x)}$ and $C_{q}=\int
e^{\frac{a}{4\beta}\left\|x\right\|{}^{\beta}-U(x)}dx$. First, we need to
bound $\log C_{q}$. Using Lemma E.4, we have

$\displaystyle U(x)$
$\displaystyle\geq\frac{a}{2\beta}\left\|x\right\|^{\beta}+U(0)-\sum_{i}\frac{L_{i}}{\alpha_{i}+1}\left(\frac{2b}{a}\right)^{\frac{\alpha_{i}+1}{\beta}}-b.$
(E.68)

Regrouping the terms and integrating both sides gives

$\displaystyle\int e^{\frac{a}{4\beta}\left\|x\right\|{}^{\beta}-U(x)}dx\leq
e^{-U(0)+\sum_{i}\frac{L_{i}}{\alpha_{i}+1}\left(\frac{2b}{a}\right)^{\frac{\alpha_{i}+1}{\beta}}+b}\int
e^{-\frac{a}{4\beta}\left\|x\right\|{}^{\beta}}dx$