# A Note on the Convergence of Mirrored Stein Variational Gradient Descent
under $(L_{0},L_{1})-$Smoothness Condition

Lukang Sun
KAUST
<EMAIL_ADDRESS>King Abdullah University of Science and Technology,
Thuwal, Saudi Arabia Peter Richtárik
KAUST
<EMAIL_ADDRESS>
###### Abstract

In this note, we establish a descent lemma for the population limit Mirrored
Stein Variational Gradient Method (MSVGD). This descent lemma does not rely on
the path information of MSVGD but rather on a simple assumption for the
mirrored distribution $\nabla\Psi_{\\#}\pi\propto\exp(-V)$. Our analysis
demonstrates that MSVGD can be applied to a broader class of constrained
sampling problems with non-smooth $V$. We also investigate the complexity of
the population limit MSVGD in terms of dimension $d$.

###  1 Introduction

The constrained optimization problem

$\min_{\theta\in\Omega}F(\theta),$ (1)

where $\Omega$ is some constrained convex region in ${\mathbb{R}}^{d}$, is of
importance in practice. The above constrained optimization problem can be
solved by constructing a differentiable one to one map
$T:{\mathbb{R}}^{d}\to\Omega$, then by compositing $T$, we get the
unconstrained optimization problem

$\min_{x\in{\mathbb{R}}^{d}}F\circ T(x),$ (2)

which can be solved efficiently by gradient based approaches. One method based
on such kind of transformation is the renowned mirror descent algorithm
Nemirovskij and Yudin (1983):

$\nabla\Psi(\theta_{n+1})=\nabla\Psi(\theta_{n})-\gamma\nabla F(\theta_{n}),$
(3)

where $\Psi(\cdot):\Omega\to{\mathbb{R}}$ is the mirror function,
$\nabla\Psi(\cdot):\Omega\to{\mathbb{R}}^{d}$ is called the mirror map and
$\gamma$ is the step-size. This algorithm is based on the discretization of
the gradient flow of $F\circ\nabla\Psi^{-1}(x)$:

$\frac{d}{dt}x_{t}=-\nabla
F\circ\nabla\Psi^{-1}(x_{t})=-\nabla^{2}\Psi^{-1}(x_{t})\nabla
F(\nabla\Psi^{-1}(x_{t})).$ (4)

Inspired by this, most recently Shi et al. (2021) proposed a variant of Stein
Variational Gradient Descent (SVGD) called Mirrored Stein Variational Gradient
Descent (MSVGD) to solve the constrained sampling problem: to sample points
from distribution $\pi\propto\exp(-F)$ with support on $\Omega$. This method
is equivalent to SVGD applied on the mirrored distribution
$\bar{\pi}=\nabla\Psi_{\\#}\pi$, however it doesn’t require the computation
related to $\bar{\pi}$. In Shi et al. (2021), under the $L$-smoothness
condition of $V$ they showed that MSVGD decreases the KL divergence following
the method from Liu (2017). In this note, inspired by Sun et al. (2022) we
reanalyze MSVGD under a weaker smoothness condition called
$(L_{0},L_{1})$-smoothness originally from Zhang et al. (2019). This condition
allows $V$ to grow like a polynomial with degree larger than 2, so it include
a large class of non-smooth functions into it. One more advantage of our
analysis is that we don’t require the path information of MSVGD like in Shi et
al. (2021), so we can establish a complexity analysis of the population limit
MSVGD in terms of the desired accuracy $\varepsilon$ and dimension $d$.

####  1.1 Related work

A parallel approach to solve the constrained sampling problem is by the
Mirrored Langevin algorithm Hsieh et al. (2018); Ahn and Chewi (2021); Zhang
et al. (2020). The work of Liu and Wang (2016) introduced SVGD as a sampling
method, since then several variants of SVGD have been considered, these
include: random batch method SVGD (RBM-SVGD) Li et al. (2020), matrix kernel
SVGD Wang et al. (2019), Newton version SVGD Detommaso et al. (2018),
Stochastic SVGD Gorham et al. (2020), Mirrored SVGD Shi et al. (2021) etc.
However, most of the theoretical understanding of SVGD is still limited to
continuous time approximation of SVGD or population limit SVGD : Lu et al.
(2019) studied the scaling limit of SVGD in continuous time, Duncan et al.
(2019) studied the geometry related to SVGD, Liu (2017) first built a
convergence result of SVGD in the population limit, Korba et al. (2020)
established a descent lemma for SVGD in population limit in terms of Kullback-
Leibler divergence however their analysis relied on the path information of
SVGD which is unknown beforehand, Salim et al. (2021) provided a clean
analysis based on the work of Korba et al. (2020), they assumed $\pi$
satisfies Talagrand’s $\text{T}_{1}$111see Equation 16 with $p=1$.inequality
then they resolved the problem of relying on path information and got a
complexity bound for SVGD in terms of the desired accuracy $\varepsilon$ and
dimension $d$ which is first shown up in the analysis of SVGD. Sun et al.
(2022) introduced the $(L_{0},L_{1})$-smoothness condition to analyze SVGD and
under a generalized $\text{T}_{p}$ inequality they also got a complexity bound
for SVGD in terms of $\varepsilon$ and $d$.

####  1.2 Contributions

The contributions of this work can be listed in three folds:

  * •

We study the population limit MSVGD under a novel smoothness criterion that
was utilized to analyze SVGD in Sun et al. (2022). This smoothness condition
originally comes from the optimization literature and allows the local
smoothness constant to increase with the gradient norm and so it is strictly
weaker than the original Lipschitz gradient assumption.

  * •

Under this smoothness assumption, we build a descent lemma for population
limit MSVGD. Our result is complete in that we only make assumptions on the
mirrored target distribution $\bar{\pi}$ but not on the path information like
in Shi et al. (2021).

  * •

We provide a complexity bound for the population limit MSVGD under this
smoothness condition.

####  1.3 Paper structure

The paper is organized as follows. Section 2 introduces the background needed
on optimal transport, reproducing kernel Hilbert space (RKHS) and Mirrored
Stein variational gradient descent (MSVGD); Section 3 presents the assumptions
needed in our analysis; Section 4 shows theoretical results on the population
limit MSVGD under assumptions from Section 3; We conclude this work in section
5 and for the missing proofs and explanations, please refer to Appendix
Appendix.

###  2 Preliminaries

####  2.1 Notations

For every
$x=(x_{1},\ldots,x_{d})^{\top},y=(y_{1},\ldots,y_{d})^{\top}\in{\mathbb{R}}^{d}$,
we will denote
$\left\|x\right\|^{p}:=\left(\sum_{i=1}^{d}|x_{i}|^{2}\right)^{\frac{p}{2}},\forall
p\geq 1$, $\left\|x\right\|=\sqrt{\sum_{i=1}^{d}|x_{i}|^{2}}$ and
$\left<x,y\right>=\sum_{i=1}^{d}x_{i}y_{i}$. We will use $\nabla^{2}V(x)$ to
denote the Hessian of potential function
$V(\cdot):{\mathbb{R}}^{d}\to{\mathbb{R}}$ at point $x$ and
$\left\|\nabla^{2}V(x)\right\|_{op}$ to denote the operator norm of matrix
$\nabla^{2}V(x)$. The Jacobian matrix of a vector valued function
$h(\cdot)=(h_{1}(\cdot),\ldots,h_{d}(\cdot))^{\top}$ with each
$h_{i}(\cdot):{\mathbb{R}}^{d}\to{\mathbb{R}}$ is a $d\times d$ matrix defined
as

$Jh(x):=\big{(}{\frac{\partial h_{i}}{\partial
x_{j}}}(x)\big{)}_{i=1,j=1}^{d,d}.$

We will use $\left\|Jh(x)\right\|_{HS}$ to denote the Hilbert-Schmidt norm of
matrix $Jh(x)$, that is

$\left\|Jh(x)\right\|_{HS}=\sqrt{\operatorname{tr}\left(Jh(x)^{\top}Jh(x)\right)}.$

The notations $\Omega$ and $\mathcal{O}$ follow the convention in complexity
analysis, i.e., $f=\Omega(g)$ means $f\gtrsim g$, and $f=\mathcal{O}(g)$ means
$f\lesssim g$. Notations $\tilde{\Omega},\tilde{\mathcal{O}}$ are used in a
similar way, but they don’t take into account the dependence of parameter
except $p,d,\lambda,C_{\bar{\pi},p}$ and $\varepsilon$. ${\rm I}_{d}$ is
denoted as the $d\times d$ identity matrix.

####  2.2 Optimal Transport

Let $\mathcal{X}_{1},\mathcal{X}_{2}$ be two measurable spaces, and denote
${\mathcal{P}}(\mathcal{X}_{1}),{\mathcal{P}}(\mathcal{X}_{2})$ as the sets of
all Borel probability measures on $\mathcal{X}_{1},\mathcal{X}_{2}$
respectively. Given a measurable map $T:\mathcal{X}_{1}\to\mathcal{X}_{2}$ and
$\mu\in\mathcal{P}(\mathcal{X}_{1})$, we denote by
$T_{\\#}\mu\in{\mathcal{P}}(\mathcal{X}_{2})$ the pushforward measure of $\mu$
by $T$, characterized by the transfer lemma
$\int_{\mathcal{X}_{1}}\phi(T(x))d\mu(x)=\int_{\mathcal{X}_{2}}\phi(y)dT_{\\#}\mu(y)$,
for any measurable and bounded function $\phi$ defined on $\mathcal{X}_{2}$.
We denote by ${\mathcal{P}}_{p}({\mathbb{R}}^{d})$ with $p\geq 1$ the set of
Borel measures $\mu$ on ${\mathbb{R}}^{d}$ with finite $p$-th absolute moment,
that is $\int\left\|x\right\|^{p}d\mu(x)<+\infty$. For every
$\mu,\nu\in{\mathcal{P}}_{p}({\mathbb{R}}^{d})$, we denote $\Gamma(\mu,\nu)$
as the set of all the coupling measures between $\mu$ and $\nu$ on
${\mathbb{R}}^{d}\times{\mathbb{R}}^{d}$, that is for any
$\gamma\in\Gamma(\mu,\nu)$, we have
$\mu={T_{1}}_{\\#}\gamma,\nu={T_{2}}_{\\#}\gamma$ with
$T_{1}(x,y)=x,T_{2}(x,y)=y$. The Wasserstein distance $W_{p}$ between $\mu$
and $\nu$ is defined by

$W_{p}(\mu,\nu)=\left(\inf_{\gamma\in\Gamma(\mu,\nu)}\int\left\|x-y\right\|^{p}d\gamma(x,y)\right)^{\frac{1}{p}},$
(5)

we can show that $W_{p}(\cdot,\cdot)$ is a metric on
${\mathcal{P}}_{p}({\mathbb{R}}^{d})$ and so
$\left({\mathcal{P}}_{p}({\mathbb{R}}^{d}),W_{p}\right)$ is a metric space,
see Ambrosio et al. (2005). We define the Kullback-Leibler (KL) divergence of
$\mu$ with respect to $\pi$ as

$\mathop{\mathrm{KL}}\nolimits(\mu\mid\pi):=\begin{cases}\int\log(\frac{\mu}{\pi})(x)d\mu(x)&\text{$\mu$
is abosolutely continuous with respect to $\pi$}\\\
\infty&\text{else}\end{cases}.$ (6)

####  2.3 Mirrored Sein Variational Gradient Descent (MSVGD)

Algorithm 1 Mirrored Sein Variational Gradient Descent Shi et al. (2021)

1:Input: density $p$ on $\Omega$, kernel $k(\cdot,\cdot)$, mirror function
$\Psi$, particles $\left(\theta_{0}^{i}\right)_{i=1}^{N}\subset\Omega$, step
sizes $\gamma$

2:Init: $x_{0}^{i}\leftarrow\nabla\Psi\left(\theta_{0}^{i}\right)$ for
$i\in[N]$

3:for $k=0,1,\cdots,n$ do

4: $x_{k+1}^{i}\leftarrow
x_{k}^{i}+\gamma\frac{1}{N}\sum_{j=1}^{N}k(\theta_{k}^{i},\theta_{k}^{j})\nabla^{2}\Psi(\theta_{k}^{j})^{-1}\nabla_{\theta}\log(\pi)(\theta_{k}^{j})+\nabla_{\theta}\cdot\left(\nabla^{2}\Psi(\theta)^{-1}k(\theta_{k}^{i},\theta)\right)\mid_{\theta=\theta_{k}^{j}}$

5:for $i\in[N]$

6: $\theta_{k+1}^{i}\leftarrow\nabla\Psi^{*}(x_{k+1}^{i})$ for $i\in[N]$

7:end for

8:Return: $\left(\theta_{n+1}^{i}\right)_{i=1}^{N}$.

We First introduce the background on the Reproducing Kernel Hilbert Space
(RKHS). Let ${\mathcal{H}}_{0}$ denote a Reproducing Kernel Hilbert Space
(RKHS) with kernel $k(\cdot,\cdot):\Omega\times\Omega\to{\mathbb{R}}$. For
every $f,g\in{\mathcal{H}}_{0}$, denote the inner product between $f$ and $g$
on ${\mathcal{H}}_{0}$ as $\langle f,g\rangle_{{\mathcal{H}}_{0}}$ and the
norm of $f$ as $\left\|f\right\|_{{\mathcal{H}}_{0}}:=\sqrt{\langle
f,f\rangle_{{\mathcal{H}}_{0}}}$. The most important property on
${\mathcal{H}}_{0}$ is the so called reproducing property: $f(\theta)=\langle
f(\cdot),k(\theta,\cdot)\rangle_{{\mathcal{H}}_{0}},\forall
f\in{\mathcal{H}}_{0}$. The $d$-fold Cartesian product of ${\mathcal{H}}_{0}$
is denoted by ${\mathcal{H}}$, then the inner product on ${\mathcal{H}}$ is
given by
$\left<f,g\right>_{{\mathcal{H}}}:=\sum_{i=1}^{d}\left<f_{i},g_{i}\right>_{{\mathcal{H}}_{0}}$,
here
$f=(f_{1},\ldots,f_{d})^{\top},g=(g_{1},\ldots,g_{d})^{\top}\in{\mathcal{H}}$
(that is each $f_{i},g_{i}\in{\mathcal{H}}_{0}$).

Let $\Omega$ be some closed convex domain in ${\mathbb{R}}^{d}$ and
$\Psi(\cdot):\Omega\to(-\infty,+\infty]$ be some proper, closed and strongly
${{K}}$-convex function defined on $\Omega$. Define
$\Psi^{*}(x):=\sup_{\theta\in\Omega}x^{\top}\theta-\Psi(\theta)$ the convex
conjugate of $\Psi$, we always assume the domain of $\Psi^{*}$ is
${\mathbb{R}}^{d}$. It is well known that $\Psi^{*}$ is convex on
${\mathbb{R}}^{d}$ and the inverse map of $\nabla\Psi$ is $\nabla\Psi^{*}$,
that is $\nabla_{x}\Psi^{*}(x)\mid_{x=\nabla\Psi(\theta)}=\theta$, so it is
easy to verify that
$\left\|\nabla^{2}\Psi^{*}\right\|_{\mathop{\mathrm{op}}\nolimits}=\left\|\nabla^{2}\Psi^{-1}\right\|_{op}\leq\frac{1}{K}$
(see Beck (2017)). One important example in application is
$\Omega=\left\\{\theta\in{\mathbb{R}}^{d}:\sum_{i=1}^{d}\theta_{i}\leq
1,\theta_{i}\geq 0,\forall i\in[d]\right\\}$ and
$\Psi(\theta)=\sum_{i=1}^{d}\theta_{i}\log(\theta_{i})+\left(1-\sum_{i=1}^{d}\theta_{i}\right)\log(1-\sum_{i=1}^{d}\theta_{i})$.
It is easy to verify that $\Psi$ is $1$-strongly convex and
$\operatorname{dom}(\nabla\Psi^{*})={\mathbb{R}}^{d}$.

With the map $\Psi$, we can now turn the constrained sampling problem
$\pi(\theta):=\exp(-F(\theta)),\theta\in\Omega$ into unconstrained sampling
problem $\bar{\pi}(x):=\exp(-V(x)),x\in{\mathbb{R}}^{d}$ with
$\bar{\pi}=\nabla\Psi_{\\#}\pi$. The idea behind the MSVGD is first to sample
point $x\sim\bar{\pi}$ through ordinaly SVGD method, then by map
$\nabla\Psi^{*}$ we get point $\theta=\nabla\Psi^{*}(x)\sim\pi$.

For any $\mu\in{\mathcal{P}}(\Omega)$, we have

$\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\theta)d\mu(\theta)\in{\mathcal{H}},$
(7)

we can now give the definition of the Mirrored Stein Fisher information:

######  Definition 1.

The Mirrored Stein Fisher information of $\mu$ relative to $\pi$ with mirror
map $\Psi$ is given by

$I_{MStein}\left(\mu\mid\pi\right):=\int_{\theta\in\Omega}\int_{\theta^{\prime}\in\Omega}k(\theta,\theta^{\prime})\left<\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\theta),\nabla^{2}\Psi(\theta^{\prime})^{-1}\nabla_{\theta^{\prime}}\log(\frac{\mu}{\pi})(\theta^{\prime})\right>d\mu(\theta)d\mu(\theta^{\prime}).$

On the one hand, when $\Omega={\mathbb{R}}^{d}$ and
$\Psi(\theta)=\frac{\left\|\theta\right\|^{2}}{2}$, this Mirrored Stein Fisher
information will be reduced to Stein Fisher information Duncan et al. (2019);
on the other hand, it can be seen as the Stein Fisher information of
$\nabla\Psi_{\\#}\mu$ relative to $\nabla\Psi_{\\#}\pi$ with kernel
$k(\nabla\Psi^{*}(\cdot),\nabla\Psi^{*}(\cdot))$, see Lemma 1.

######  Lemma 1.

Let $\bar{\mu}:=\nabla\Psi_{\\#}\mu$ and $\bar{\pi}:=\nabla\Psi_{\\#}\pi$,
then we have

$\displaystyle g_{\bar{\mu}}(\cdot)$
$\displaystyle:=P_{\bar{\mu}}\nabla\log(\frac{\bar{\mu}}{\bar{\pi}})(\cdot)=\int_{x\in{\mathbb{R}}^{d}}k(\nabla\Psi^{*}(x),\cdot)\nabla_{x}\log(\frac{\bar{\mu}}{\bar{\pi}})(x)d\bar{\mu}(x)=\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\theta)d\mu(\theta)$
(8)

and

$I_{MStein}\left(\mu\mid\pi\right)=\int_{x\in{\mathbb{R}}^{d}}\int_{y\in{\mathbb{R}}^{d}}k(\nabla\Psi^{*}(x),\nabla\Psi^{*}(y))\left<\nabla_{x}\log(\frac{\bar{\mu}}{\bar{\pi}})(x),\nabla_{y}\log(\frac{\bar{\mu}}{\bar{\pi}})(y)\right>d\bar{\mu}(x)d\bar{\mu}(y)=\left\|g_{\bar{\mu}_{n}}\right\|_{{\mathcal{H}}}^{2}.$
(9)

The form of $g_{\bar{\mu}}(\cdot)$ in the right hand side of (8) is not
attainable in practice, since it require the gradient of
$\log(\frac{\mu}{\pi})$, however with a non-demanding assumption, we have the
following representation of $g_{\bar{\mu}}$.

######  Lemma 2.

Assume for any $\theta^{\prime}\in\Omega$,
$k(\theta,\theta^{\prime})\nabla^{2}\Psi(\theta)^{-1}\mu(\theta)$ vanishes
when $\theta\to\partial\Omega$, then we have

$\displaystyle g_{\bar{\mu}}(\cdot)$
$\displaystyle=\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\theta)d\mu(\theta)$
(10)
$\displaystyle=-\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\pi)(x)d\mu(\theta)-\int_{\theta\in\Omega}\nabla_{\theta}\cdot\left(k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\right)d\mu(\theta).$

When kernel $k(\cdot,\cdot)$ and density of $\mu$ is bounded, this vanishing
condition of $k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\mu(\theta)$ at
boundary $\partial\Omega$ is satisfied by the example
$\Omega=\left\\{\theta\in{\mathbb{R}}^{d}:\sum_{i=1}^{d}\theta_{i}\leq
1,\theta_{i}\geq 0,\forall i\in[d]\right\\}$ and
$\Psi(\theta)=\sum_{i=1}^{d}\theta_{i}\log(\theta_{i})+\left(1-\sum_{i=1}^{d}\theta_{i}\right)\log(1-\sum_{i=1}^{d}\theta_{i})$.

With all the preparation, we can show what we mean by population limit (or
infinite particle regime) MSVGD, that is

$\begin{cases}\bar{\mu}_{n-1}=\nabla\Psi_{\\#}\mu_{n-1}\\\
\bar{\mu}_{n}=\left({\rm I}_{d}-\gamma
g_{\bar{\mu}_{n-1}}\right)_{\\#}\bar{\mu}_{n-1}\\\
\mu_{n}=\nabla\Psi^{*}_{\\#}\bar{\mu}_{n}\end{cases}$ (11)

with $n=1,2,\ldots$ and $\gamma$ the step-size. However to calculate the
integration exactly in $g_{\bar{\mu}_{n-1}}$ is not practical, in general the
integration is replaced by the empirical summation

$\displaystyle g_{\bar{\mu}_{n-1}}(\cdot)$
$\displaystyle=-\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\pi)(x)d\mu(\theta)-\int_{\theta\in\Omega}\nabla_{\theta}\cdot\left(k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\right)d\mu(\theta)$
$\displaystyle\approx\frac{1}{N}\sum_{j=1}^{N}k(\cdot,\theta_{k}^{j})\nabla^{2}\Psi(\theta_{k}^{j})^{-1}\nabla_{\theta}\log(\pi)(\theta_{k}^{j})+\nabla_{\theta}\cdot\left(\nabla^{2}\Psi(\theta)^{-1}k(\cdot,\theta)\right)\mid_{\theta=\theta_{k}^{j}}=:{g}_{\hat{\mu}_{n-1}}(\cdot).$

So the finite particle Mirrored Stein Variational gradient Descent in
Algorithm 1 is equivalent to

$\begin{cases}\hat{\mu}_{n-1}=\nabla\Psi_{\\#}\mu_{n-1}\\\
\hat{\mu}_{n}=\left({\rm I}_{d}-\gamma
g_{\hat{\mu}_{n-1}}\right)_{\\#}\hat{\mu}_{n-1}\\\
\mu_{n}=\nabla\Psi^{*}_{\\#}\hat{\mu}_{n}\end{cases}$ (12)

with $\mu_{0}=\frac{1}{N}\sum_{i=1}^{N}\delta_{\theta_{0}^{i}}$.

###  3 Assumptions

We first state an assumption on the mirror function $\Psi$.

######  Assumption 1.

The mirror function $\Psi(\cdot):\Omega\to(-\infty,+\infty]$ is strongly
${{K}}$-convex and the range of the mirror map $\nabla\Psi$ is
${\mathbb{R}}^{d}$.

Next, we state the standard assumption on the kernel
$k(\cdot,\cdot):\Omega\times\Omega\to{\mathbb{R}}$.

######  Assumption 2.

There exists $B_{1},B_{2}>0$ s.t. for all $\theta\in\Omega$,
$k(\theta,\theta)\leq B_{1}^{2}$ and
$\partial_{\theta_{i}}\partial_{\theta^{\prime}_{j}}k(\theta,\theta^{\prime})\mid_{\theta^{\prime}=\theta}\leq
B_{2}^{2}$, $\forall i\in[d],j\in[d]$.

By reproducing property, this is equivalent to say
$\left<k(\theta,\cdot),k(\theta,\cdot)\right>_{{\mathcal{H}}_{0}}\leq
B_{1}^{2}$ and
$\left<\partial_{\theta_{i}}k(\theta,\cdot),\partial_{\theta_{j}}k(\theta,\cdot)\right>_{{\mathcal{H}}_{0}}\leq
B_{2}^{2}$ for all $\theta\in\Omega$. If $k(\theta,\theta^{\prime})$ is in the
form $f(\theta-\theta^{\prime})$ and $f$ is smooth at point
$0\in{\mathbb{R}}^{d}$, then it satisfies 2. One can also normalize
$k(\theta,\theta^{\prime})$ by $k(\theta/{d},\theta^{\prime}/{d})$ to make
$B_{2}={\mathcal{O}}(\frac{1}{d})$.

Shi et al. (2021) assumed $L$-smoothness of $V$, where $V$ is the potential
function of the mirrored distribution $\bar{\pi}=\exp(-V)$, that is

$\|\nabla^{2}V(x)\|_{op}\leq L,$

where $L>0$ is a bounded constant. Different from the $L$-smoothness
assumption on $V$, We introduce a weaker smoothness assumption called
$(L_{0},L_{1})$-smoothness from Zhang et al. (2019). The assumption reads as
in the following:

######  Assumption 3.

$\exists L_{0},L_{1}\geq 0$ s.t.

$\left\|\nabla^{2}V(x)\right\|_{op}\leq L_{0}+L_{1}\|\nabla V(x)\|,$ (13)

for any $x\in\mathbb{R}^{d}$.

For instance $g(x)=|x|^{2+\delta}$ with $x\in{\mathbb{R}}$ and $\delta>0$
satisfies $(L_{0},L_{1})$-smoothness condition with
$L_{0}=(2+\delta)(1+\delta)^{1+\delta},L_{1}=1$, while it is not a $L$-smooth
function. We also need the a assumption on $\bar{\pi}$.

######  Assumption 4.

There exists $p\geq 1$, $x_{0}\in{\mathbb{R}}^{d}$ and $s>0$ such that

$\int\exp({s\left\|x-x_{0}\right\|^{p}})d\bar{\pi}(x)<+\infty.$

If Assumption 4 holds, then based on results from Bolley and Villani (2005)
(see Lemma 8 in the Appendix), we have

$W_{p}(\mu,{\bar{\pi}})\leqslant
C_{{\bar{\pi}},p}\left[\mathop{\mathrm{KL}}\nolimits(\mu\mid{\bar{\pi}})^{\frac{1}{p}}+\left(\frac{\mathop{\mathrm{KL}}\nolimits(\mu\mid{\bar{\pi}})}{2}\right)^{\frac{1}{2p}}\right],\quad\forall\mu\in{\mathcal{P}}_{p}({\mathbb{R}}^{d}),$
(14)

where

$C_{{\bar{\pi}},p}:=2\inf_{x_{0}\in{\mathbb{R}}^{d},s>0}\left(\frac{1}{s}\left(\frac{3}{2}+\log\int\exp({s\left\|x-x_{0}\right\|^{p}})d{\bar{\pi}}(x)\right)\right)^{\frac{1}{p}}<+\infty.$
(15)

Note constant $C_{{\bar{\pi}},p}$ may depend on dimension, for instance if
${\bar{\pi}}(x)\propto\exp(-\left\|x\right\|^{p})$, we have
$C_{{\bar{\pi}},p}={\mathcal{O}}\left(d^{\frac{1}{p}}\right)$ by simple
calculation. 4 is used to guarantee inequality (14) hold, we can instead
directly assume Talagrand’s $\text{T}_{p}$ inequality.

######  Assumption 5.

For any $\mu\in{\mathcal{P}}_{p}({\mathbb{R}}^{d})$, we have

$W_{p}(\mu,{\bar{\pi}})\leq\sqrt{\frac{2\mathop{\mathrm{KL}}\nolimits(\mu\mid{\bar{\pi}})}{\lambda}}.$
(16)

It is not clear the condition on $\bar{\pi}$ such that $\text{T}_{p}$
inequality holds except for a few cases. When $p=1$, a sufficient and
necessary condition for Equation 16 to be hold is there exists
$x_{0}\in{\mathbb{R}}^{d},s>0$ such that
$\int\exp({s\left\|x-x_{0}\right\|^{2}})d{\bar{\pi}}(x)<+\infty$ (see
(Villani, 2009, Theorem 22.10.)). When $V$ is strongly $K$-convex, then
Equation 16 holds with $p=2,\lambda=K$ (Bakry-Émery criterion, see Bakry and
Émery (1985)), also $\text{T}_{2}$ is preserved under bounded perturbation
(Holley-Strook criterion, see Holley and Stroock (1986) or Steiner
(2021))222these two criterions are used for logarithmic Sobolev inequality
(LSI), since LSI implies $\text{T}_{2}$ with the same constant, they can be
also applied on $\text{T}_{2}$..

To bound the Stein Fisher information along trajectory of MSVGD, we also need
an assumption on the growth rate of $\nabla V$.

######  Assumption 6.

There exists $p\geq 1$ and a constant $C_{p}$ such that

$\big{\|}\nabla V(x)\big{\|}\leq C_{p}\left(\left\|x\right\|^{p}+1\right),$

for any $x\in{\mathbb{R}}^{d}$.

One simple example that satisfies both 4 and 6 is $V(x)=\left\|x\right\|^{p}$.

###  4 Main Theory

The following proposition is close to the descent lemma, however the step-size
$\gamma$ in this proposition depends on the path information. In the
following, we always denote
$\bar{\pi}=\nabla\Psi_{\\#}\pi,\bar{\mu}_{n}=\nabla\Psi_{\\#}\mu_{n},\forall
n=0,1,2,\ldots$.

######  Proposition 1.

Suppose that Assumptions 1, 2 and 3 are satisfied. Let $\alpha>1$ and choose

$\gamma\leq\min\left\\{\frac{(\alpha-1)K}{\alpha
B_{2}dI_{MStein}(\mu_{n}\mid\pi)^{\frac{1}{2}}},\frac{1}{B_{1}I_{MStein}(\mu_{n}\mid\pi)^{\frac{1}{2}}L_{1}},\frac{{{K}}^{2}}{\left(\alpha^{2}B_{2}^{2}d^{2}+{{K}}^{2}(e-1)B_{1}^{2}A_{n}\right)}\right\\},$
(17)

where $A_{n}:=L_{0}+L_{1}\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}[\|\nabla
V(\boldsymbol{X})\|]$. Then

$\mathrm{KL}\left(\mu_{n+1}\mid\pi\right)-\mathrm{KL}\left(\mu_{n}\mid\pi\right)\leq-\frac{\gamma}{2}I_{MStein}(\mu_{n}\mid\pi),$
(18)

In the above proposition, the upper bound for the step-size $\gamma$ depend on
$I_{MStein}(\mu_{n}\mid\pi)^{\frac{1}{2}}$ and $A_{n}$, these values can be
further bounded by $\mathop{\mathrm{KL}}\nolimits(\mu_{n}\mid\pi)$ by the
following two lemmas.

######  Lemma 3.

If Assumptions 1 and 2 are satisfied, then

$I_{MStein}(\mu_{n}\mid\pi)^{\frac{1}{2}}\leq
B_{1}\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla
V(\boldsymbol{X})\|\big{]}+\frac{B_{2}d}{K}$ (19)

for all $n\in\mathbb{N}$.

Let us denote function
$G_{p}(x):=x^{\frac{1}{p}}+\left(\frac{x}{2}\right)^{\frac{1}{2p}}$ in the
following.

######  Lemma 4.

Suppose Assumptions 3, 4 and 6 hold. Then,

$\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}[\|\nabla
V(\boldsymbol{X})\|]\leq
C_{p}\left(C_{\bar{\pi},p}\left(G_{p}(\mathop{\mathrm{KL}}\nolimits({\mu}_{n}\mid{\pi}))+G_{p}(\mathop{\mathrm{KL}}\nolimits({\mu}_{0}\mid{\pi}))\right)+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p},$
(20)

where $C_{p}$ from 6, $C_{\bar{\pi},p}$ from (15).

Now, using Equations 19 and 20 we can give an upper bound for $\gamma$ such
that it satisfies condition (17), then based on Proposition 1 we have the
following descent lemma which only depends on the initial distribution
$\mu_{0},\bar{\mu}_{0}$ and the target distribution $\pi,\bar{\pi}$.

######  Theorem 1 (Descent lemma).

Suppose Assumptions 1, 2, 3, 4, and 6 are satisfied. Also, suppose that the
step-size $\gamma$ satisfies

$\gamma\leq{M}\left(C_{p}\left(2C_{\bar{\pi},p}G_{p}(\mathop{\mathrm{KL}}\nolimits({\mu}_{0}\mid{\pi}))+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right),$
(21)

where
${M}(x):=\min\left\\{\min\left\\{\frac{1}{B_{1}L_{1}},\frac{(\alpha-1){{K}}}{\alpha
B_{2}d}\right\\}\frac{K}{KB_{1}x+B_{2}d},\frac{{{K}}^{2}}{\alpha^{2}B_{2}^{2}d^{2}+{{K}}^{2}B_{1}^{2}(e-1)\left(L_{1}x+L_{0}\right)}\right\\}$,
then the following bound is true:

$\mathrm{KL}\left(\mu_{n+1}\mid\pi\right)-\mathrm{KL}\left(\mu_{n}\mid\pi\right)\leq-\frac{\gamma}{2}I_{MStein}(\mu_{n}\mid\pi).$
(22)

Now, based on the above descent lemma, we can derive the complexity bound for
MSVGD in population limit.

######  Corollary 1 (Convergence).

Suppose Assumptions 1, 2, 3, 4, and 6 are satisfied. Also $\gamma$ satisfies
condition (21) and $B_{2}={\mathcal{O}}(\frac{1}{d})$, then we have

$\frac{1}{n}\sum_{k=0}^{n-1}I_{MStein}\left(\mu_{k}\mid\pi\right)\leq\frac{2\mathop{\mathrm{KL}}\nolimits(\mu_{0}\mid\pi)}{n\gamma}.$
(23)

If $\bar{\pi}(x)=\exp(-V(x))$ and $\bar{\mu}_{0}={\mathcal{N}}(0,{\rm
I}_{d})$, then to have
$\frac{1}{n}\sum_{k=0}^{n-1}I_{MStein}\left(\mu_{k}\mid\pi\right)\leq\varepsilon$,
we need

$n=\tilde{\Omega}\left(\frac{8^{p}C_{\bar{\pi},p}^{p}\Gamma(\frac{p+d+1}{2})^{2}}{(p+1)^{2}\Gamma(\frac{d}{2})^{2}\varepsilon}\right).$
(24)

If $B_{2}={\mathcal{O}}(1)$, we can replace the kernel $k(\cdot,\cdot)$ by
$k(\cdot/d,\cdot/d)$, then it satisfies $B_{2}={\mathcal{O}}(\frac{1}{d})$. By
Stirling formula, we know the dimension dependency of
$\frac{\Gamma(\frac{p+d+1}{2})^{2}}{\Gamma(\frac{d}{2})^{2}}$ is of order
$1+p$, so if $p$ is not big, there should be
$n=\tilde{\Omega}\left(\frac{C_{\bar{\pi},p}^{p}d^{1+p}}{\varepsilon}\right)$.

####  4.1 Better Results under $\text{T}_{p}$ Inequality when $1\leq p\leq 2$

In the next, we assume $\bar{\pi}$ satisfies Talagrand’s $\text{T}_{p}$
inequality (16) instead of 4 and keep the other assumptions the same. When
$p\in[1,2]$, Equation 16 is more preferable in our analysis since
$W_{p}(\bar{\mu},\bar{\pi})={\mathcal{O}}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}\mid\bar{\pi})^{\frac{1}{2}})$
while Equation 14 gives the bigger bound
$W_{p}(\bar{\mu},\bar{\pi})={\mathcal{O}}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}\mid\bar{\pi})^{\frac{1}{p}})$.We
focus on the cases when $p\in[1,2]$ and we give a modified version of Lemma 4,
Theorem 1 and Corollary 1.

######  Lemma 5.

Suppose Assumptions 3, 5 and 6 hold. Then,

$\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}[\|\nabla
V(\boldsymbol{X})\|]\leq
C_{p}\left(\sqrt{\frac{2\mathop{\mathrm{KL}}\nolimits({\mu}_{n}\mid{\pi})}{\lambda}}+\sqrt{\frac{2\mathop{\mathrm{KL}}\nolimits({\mu}_{0}\mid{\pi})}{\lambda}}+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p},$
(25)

where $C_{p}$ from 6.

######  Theorem 2.

Suppose Assumptions 1, 2, 3, and 6 are satisfied. Also, suppose that the step-
size $\gamma$ satisfies

$\gamma\leq{M}\left(C_{p}\left(\sqrt{\frac{2\mathop{\mathrm{KL}}\nolimits({\mu}_{n}\mid{\pi})}{\lambda}}+\sqrt{\frac{2\mathop{\mathrm{KL}}\nolimits({\mu}_{0}\mid{\pi})}{\lambda}}+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right),$
(26)

where
${M}(x):=\min\left\\{\min\left\\{\frac{1}{B_{1}L_{1}},\frac{(\alpha-1){{K}}}{\alpha
B_{2}d}\right\\}\frac{K}{KB_{1}x+B_{2}d},\frac{{{K}}^{2}}{\alpha^{2}B_{2}^{2}d^{2}+{{K}}^{2}B_{1}^{2}(e-1)\left(L_{1}x+L_{0}\right)}\right\\}$,
then the following bound is true:

$\mathrm{KL}\left({\mu}_{n+1}\mid{\pi}\right)-\mathrm{KL}\left({\mu}_{n}\mid{\pi}\right)\leq-\frac{\gamma}{2}I_{MStein}({\mu}_{n}\mid{\pi}).$
(27)

Now, based on the above modified descent lemma, we can derive the complexity
bound for MSVGD in population limit.

######  Corollary 2.

Suppose Assumptions 1, 2, 3,5 and 6 hold. If $\gamma$ satisfies condition (26)
and $B_{2}={\mathcal{O}}(\frac{1}{d})$, then we have

$\frac{1}{n}\sum_{k=0}^{n-1}I_{MStein}\left({\mu}_{k}\mid{\pi}\right)\leq\frac{2\mathop{\mathrm{KL}}\nolimits({\mu}_{0}\mid{\pi})}{n\gamma}.$
(28)

If $\bar{\pi}(x)=\exp(-V(x))$ and $\bar{\mu}_{0}={\mathcal{N}}(0,{\rm
I}_{d})$, then to make
$\frac{1}{n}\sum_{k=0}^{n-1}I_{MStein}\left({\mu}_{k}\mid{\pi}\right)\leq\varepsilon$,
we need

$n=\tilde{\Omega}\left(\frac{d^{\frac{(p+2)(p+1)}{4}}}{\lambda^{\frac{p}{2}}\varepsilon}\right).$
(29)

When $1\leq p\leq 2$, if we assume $\pi$ satisfies Talagrand’s $\text{T}_{p}$
inequality (16) instead of 4, $n$ will have a slightly better dimension
dependency, that is of order $\frac{(p+2)(p+1)}{4}$.

######  Remark 1.

Here we provide a sufficient condition on which
$\lim_{n\to\infty}I_{MStein}(\mu_{n}\mid\pi)$ implies $\mu_{n}\to\pi$ weakly,
this condition can be found in Gorham and Mackey (2017). Since Mirrored Stein
Fisher information depends on the target distribution $\bar{\pi}$, mirror
function $\Psi$ and kernel $k(\cdot,\cdot)$, we need the following two
properties on $\bar{\pi}$ and $k(\nabla\Psi^{*}(\cdot),\nabla\Psi^{*}(\cdot))$
respectively:

  1. 1.

$\bar{\pi}$ is distant dissipative, that is
$\kappa_{0}\triangleq\liminf_{r\rightarrow\infty}\kappa(r)>0$ with

$\kappa(r)=\inf\left\\{2\frac{\langle\nabla V(x)-\nabla
V(y),x-y\rangle}{\|x-y\|^{2}}:\|x-y\|=r\right\\}.$

If $V$ is strongly convex outside a compact set, then $\bar{\pi}$ is distant
dissipative, for instance $V(x)=\left\|x\right\|^{2+\delta}$ with $\delta\geq
0$.

  2. 2.

$k(\nabla\Psi^{*}(\cdot),\nabla\Psi^{*}(\cdot))$ is an inverse multiquadratic
kernel, i.e.,
$k(\nabla\Psi^{*}(x),\nabla\Psi^{*}(y))=\left(c^{2}+\|x-y\|^{2}\right)^{\beta}$
for some $c>0$ and $\beta\in(-1,0)$. It is easy to check that 2 is satisfied.

###  5 Conclusion

We proved a descent lemma for minimizing the $\mathop{\mathrm{KL}}\nolimits$
divergence with the MSVGD algorithm under $(L_{0},L_{1})$-smoothness
condition. Though in this paper we assume $k(\cdot,\cdot)$ is scalar, our
analysis can also be applied on matrix kernel. The result implies
${\mathcal{O}}(1/n)$ convergence under Mirrored Stein Fisher information. The
results in this note match the ones from Sun et al. (2022), this is not
surprising since MSVGD is equivalent to SVGD for target distribution
$\nabla\Psi_{\\#}\pi$. The proved results remain on the theoretical level, the
algorithm we analyzed in the infinite particle regime which is not
implementable on a computer. There is paper analysing the finite particle
regime Shi et al. (2021), however they assumed a $L$-smooth $V$ and their
result is asymptotic. A relevant analysis of the finite particle regime still
lacks certain clarity and is yet to be developed.

### References

  * Ahn and Chewi [2021] Kwangjun Ahn and Sinho Chewi.  Efficient constrained sampling via the mirror-Langevin algorithm.  _Advances in Neural Information Processing Systems_ , 34:28405–28418, 2021.
  * Ambrosio et al. [2005] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré.  _Gradient flows: in metric spaces and in the space of probability measures_.  Springer Science & Business Media, 2005.
  * Bakry and Émery [1985] Dominique Bakry and Michel Émery.  Diffusions hypercontractives.  In _Seminaire de probabilités XIX 1983/84_ , pages 177–206. Springer, 1985.
  * Beck [2017] Amir Beck.  _First-order methods in optimization_.  SIAM, 2017.
  * Bolley and Villani [2005] François Bolley and Cédric Villani.  Weighted Csiszár-Kullback-Pinsker inequalities and applications to transportation inequalities.  In _Annales de la Faculté des sciences de Toulouse: Mathématiques_ , volume 14, pages 331–352, 2005.
  * Detommaso et al. [2018] Gianluca Detommaso, Tiangang Cui, Youssef Marzouk, Alessio Spantini, and Robert Scheichl.  A Stein variational Newton method.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Duncan et al. [2019] Andrew Duncan, Nikolas Nüsken, and Lukasz Szpruch.  On the geometry of Stein variational gradient descent.  _arXiv preprint arXiv:1912.00894_ , 2019.
  * Gorham and Mackey [2017] Jackson Gorham and Lester Mackey.  Measuring sample quality with kernels.  In _International Conference on Machine Learning_ , pages 1292–1301. PMLR, 2017.
  * Gorham et al. [2020] Jackson Gorham, Anant Raj, and Lester Mackey.  Stochastic Stein discrepancies.  _Advances in Neural Information Processing Systems_ , 33:17931–17942, 2020.
  * Holley and Stroock [1986] Richard Holley and Daniel W Stroock.  Logarithmic Sobolev inequalities and stochastic Ising models.  1986\.
  * Hsieh et al. [2018] Ya-Ping Hsieh, Ali Kavis, Paul Rolland, and Volkan Cevher.  Mirrored Langevin dynamics.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Korba et al. [2020] Anna Korba, Adil Salim, Michael Arbel, Giulia Luise, and Arthur Gretton.  A non-asymptotic analysis for Stein variational gradient descent.  _Advances in Neural Information Processing Systems_ , 33:4672–4682, 2020.
  * Li et al. [2020] Lei Li, Yingzhou Li, Jian-Guo Liu, Zibu Liu, and Jianfeng Lu.  A stochastic version of Stein variational gradient descent for efficient sampling.  _Communications in Applied Mathematics and Computational Science_ , 15(1):37–63, 2020.
  * Liu [2017] Qiang Liu.  Stein variational gradient descent as gradient flow.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Liu and Wang [2016] Qiang Liu and Dilin Wang.  Stein variational gradient descent: A general purpose bayesian inference algorithm.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Lu et al. [2019] Jianfeng Lu, Yulong Lu, and James Nolen.  Scaling limit of the stein variational gradient descent: The mean field regime.  _SIAM Journal on Mathematical Analysis_ , 51(2):648–671, 2019.
  * Nemirovskij and Yudin [1983] Arkadij Semenovič Nemirovskij and David Borisovich Yudin.  Problem complexity and method efficiency in optimization.  1983\.
  * Salim et al. [2021] Adil Salim, Lukang Sun, and Peter Richtárik.  Complexity analysis of Stein variational gradient descent under Talagrand’s inequality T1.  _arXiv preprint arXiv:2106.03076_ , 2021.
  * Shi et al. [2021] Jiaxin Shi, Chang Liu, and Lester Mackey.  Sampling with mirrored Stein operators.  _arXiv preprint arXiv:2106.12506_ , 2021.
  * Steiner [2021] Clément Steiner.  A Feynman-Kac approach for logarithmic Sobolev inequalities.  _Electronic Journal of Probability_ , 26:1–19, 2021.
  * Sun et al. [2022] Lukang Sun, Avetik Karagulyan, and Peter Richtarik.  Convergence of Stein variational gradient descent under a weaker smoothness condition.  _arXiv preprint arXiv:2206.00508_ , 2022.
  * Villani [2009] Cédric Villani.  _Optimal transport: old and new_ , volume 338.  Springer, 2009.
  * Wang et al. [2019] Dilin Wang, Ziyang Tang, Chandrajit Bajaj, and Qiang Liu.  Stein variational gradient descent with matrix-valued kernels.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Winkelbauer [2012] Andreas Winkelbauer.  Moments and absolute moments of the normal distribution.  _arXiv preprint arXiv:1209.4340_ , 2012.
  * Zhang et al. [2019] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie.  Why gradient clipping accelerates training: A theoretical justification for adaptivity.  In _International Conference on Learning Representations_ , 2019.
  * Zhang et al. [2020] Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, and Marcelo Pereyra.  Wasserstein control of mirror Langevin Monte Carlo.  In _Conference on Learning Theory_ , pages 3814–3841. PMLR, 2020\.

###### Contents

  1. 1 Introduction
    1. 1.1 Related work
    2. 1.2 Contributions
    3. 1.3 Paper structure
  2. 2 Preliminaries
    1. 2.1 Notations
    2. 2.2 Optimal Transport
    3. 2.3 Mirrored Sein Variational Gradient Descent (MSVGD)
  3. 3 Assumptions
  4. 4 Main Theory
    1. 4.1 Better Results under $\text{T}_{p}$ Inequality when $1\leq p\leq 2$
  5. 5 Conclusion
  6. A Proof of Proposition 1
  7. B  Lemmas
    1. B.1 Proof of Lemmas
  8. C Main Theory
    1. C.1 Complexity Analysis
  9. D The Cases under $\text{T}_{p}$ inequality with $1\leq p\leq 2$

## Appendix

For simplicity, in this appendix we will denote
$k_{\Psi}(\cdot,\cdot):=k(\nabla\Psi^{*}(\cdot),\nabla\Psi^{*}(\cdot))$. Since
$\mathop{\mathrm{KL}}\nolimits(\nabla\Psi_{\\#}\mu\mid\nabla\Psi_{\\#}\pi)=\mathop{\mathrm{KL}}\nolimits(\mu\mid\pi)$
for diffeomorphism $\nabla\Psi$, so it is enough to prove the results using
$\mathop{\mathrm{KL}}\nolimits(\bar{\mu}\mid\bar{\pi})$, where
$\bar{\mu}=\nabla\Psi_{\\#}\mu,\bar{\pi}=\nabla\Psi_{\\#}\pi$.

###  Appendix A Proof of Proposition 1

We follow the proof procedure in Sun et al. [2022]. First due to Lemma 1, we
have
$\left\|g_{\bar{\mu}_{n}}\right\|_{{\mathcal{H}}}^{2}=I_{MStein}(\mu_{n}\mid\pi)$.
For the sake of brevity we will omit the index when referring to
$g_{{\bar{\mu}}_{n}}$ and will write simply $g$. Let us define
$\phi_{t}:=I-tg$ and $\bar{\rho}_{t}:={\phi_{t}}_{\\#}{\bar{\mu}}_{n}$ for
every $t\in[0,\gamma]$. Then, applying Taylor formula to the function

$\varphi(t):=\mathrm{KL}\left(\bar{\rho}_{t}\mid\bar{\pi}\right)$ (30)

we have the following

$\varphi(\gamma)=\varphi(0)+\gamma\varphi^{\prime}(0)+\int_{0}^{\gamma}(\gamma-t)\varphi^{\prime\prime}(t){\rm
d}t.$ (31)

By the definition of the MSVGD iteration, we have that
$\varphi(0)={\mathop{\mathrm{KL}}\nolimits}\left({\bar{\mu}}_{n}\mid\bar{\pi}\right)$
and
$\varphi(\gamma)={\mathop{\mathrm{KL}}\nolimits}\left({\bar{\mu}}_{n+1}\mid\bar{\pi}\right)$.
Let us now compute the term of (31) corresponding to the first order
derivative. In order to do that we show that $\phi_{t}$ is a diffeomorphism.

######  Lemma 6.

Suppose that Assumption 2 holds. Then, for any $x\in{\mathbb{R}}^{d}$ and
$h\in\mathcal{H}$,

$\|Jh(x)\|_{{\rm HS}}\leq\frac{B_{2}d}{{{K}}}\|h\|_{\mathcal{H}}.$

Applying the lemma to the function $g$, we obtain the following:

$\|tJg(x)\|_{op}\leq\|tJg(x)\|_{{\rm HS}}\leq
t\frac{B_{2}d}{{{K}}}\|g\|_{\mathcal{H}}<1.$ (32)

The latter inequality is due to the condition on the step-size $\gamma$
($\gamma\leq\frac{(\alpha-1){{K}}}{\alpha
B_{2}d\left\|g\right\|_{{\mathcal{H}}}}$). The inequality (32) implies that
$\phi_{t}$ is a diffeomorphism. Therefore, $\bar{\rho}_{t}$ admits a density
given by the formula of transformation of probability densities:

$\bar{\rho}_{t}(x)=\left|J\phi_{t}\left(\phi_{t}^{-1}(x)\right)\right|^{-1}{\bar{\mu}}_{n}\left(\phi_{t}^{-1}(x)\right).$

Changing the variable of integration and applying the transfer lemma we get
the following formula for $\varphi(t)$:

$\displaystyle\varphi(t)$
$\displaystyle=\int\log\left(\frac{\bar{\rho}_{t}(y)}{\bar{\pi}(y)}\right)\bar{\rho}_{t}(y){\mathrm{d}}y$
$\displaystyle=\int\log\left(\frac{{\bar{\mu}}_{n}(x)\left|J\phi_{t}(x)\right|^{-1}}{\bar{\pi}\left(\phi_{t}(x)\right)}\right){\bar{\mu}}_{n}(x){\mathrm{d}}x$
$\displaystyle=\int\left[\log\left({\bar{\mu}}_{n}(x)\right)+\log\left(\left|J\phi_{t}(x)\right|^{-1}\right)-\log\left({\bar{\pi}\left(\phi_{t}(x)\right)}\right)\right]{\bar{\mu}}_{n}(x){\mathrm{d}}x.$

Let us then compute the time derivative of $\varphi(t)$. Taking the derivative
inside and applying Jacobi’s formula for matrix determinant differentiation we
obtain the following equality:

$\varphi^{\prime}(t)=-\int\operatorname{tr}\left(J\phi_{t}(x)^{-1}\frac{dJ\phi_{t}(x)}{dt}\right){\bar{\mu}}_{n}(x){\mathrm{d}}x-\int\left\langle\nabla\log\bar{\pi}\left(\phi_{t}(x)\right),\frac{d\phi_{t}(x)}{dt}\right\rangle{\bar{\mu}}_{n}(x){\mathrm{d}}x.$

By definition, $d\phi_{t}/dt=g$. Therefore, we can use the explicit expression
of $\phi_{t}$ to write:

$\varphi^{\prime}(t)=\int\operatorname{tr}\left(J\phi_{t}(x)^{-1}Jg(x)\right){\bar{\mu}}_{n}(x){\mathrm{d}}x+\int\left\langle\nabla
V\left(\phi_{t}(x)\right),g(x)\right\rangle{\bar{\mu}}_{n}(x){\mathrm{d}}x.$

The Jacobian at time $t=0$ is simply equal to the identity matrix since
$\phi_{0}={\rm I}_{d}$. It follows that
$\operatorname{tr}\left(J\phi_{0}(x)^{-1}Jg(x)\right)=$
$\operatorname{tr}(Jg(x))=\operatorname{div}(g)(x)$ by the definition of the
divergence operator. Using integration by parts:

$\displaystyle\varphi^{\prime}(0)$
$\displaystyle=-\int[-\operatorname{div}(g)(x)-\langle\nabla\log\bar{\pi}(x),g(x)\rangle]{\bar{\mu}}_{n}(x){\mathrm{d}}x$
(33)
$\displaystyle=-\int\left\langle\nabla\log\left(\frac{{\bar{\mu}}_{n}}{\bar{\pi}}\right)(x),g(x)\right\rangle{\bar{\mu}}_{n}(x){\mathrm{d}}x$
$\displaystyle=-\left\langle
P_{\bar{\mu}}\nabla\log\left(\frac{{\bar{\mu}}_{n}}{\bar{\pi}}\right)(x),g(x)\right\rangle_{{\mathcal{H}}}$
$\displaystyle=-\|g\|_{{\mathcal{H}}}^{2}.$

Next, we calculate the term of (31) that contains the second derivative.
First,

$\varphi^{\prime\prime}(t)=\int\left[{\operatorname{tr}\left(\left(Jg(x)\left(J\phi_{t}(x)\right)^{-1}\right)^{2}\right)}+\left\langle
g(x),\nabla^{2}V\left(\phi_{t}(x)\right)g(x)\right\rangle\right]{\bar{\mu}}_{n}(x){\mathrm{d}}x.$

From the definition of the function $\phi_{t}$, we know that
$J\phi_{t}(x)=({\rm I}_{d}+tJg)(x)$. Thus, $J\phi_{t}^{-1}$ and $Jg$ commute
and
$\operatorname{tr}\left(\left(Jg(x)\left(J\phi_{t}(x)\right)^{-1}\right)^{2}\right)=\left\|Jg(x)\left(J\phi_{t}(x)\right)^{-1}\right\|_{\rm
HS}^{2}$.

Overall we have the following:

$\varphi^{\prime\prime}(t)=\underbrace{\int\left\|Jg(x)\left(J\phi_{t}(x)\right)^{-1}\right\|_{\rm
HS}^{2}{\bar{\mu}}_{n}(x){\mathrm{d}}x}_{:=\psi_{1}(t)}+\underbrace{\int\left\langle
g(x),H_{V}\left(\phi_{t}(x)\right)g(x)\right\rangle{\bar{\mu}}_{n}(x){\mathrm{d}}x}_{:=\psi_{2}(t)}.$

First, we bound $\psi_{1}(t)$. Cauchy-Schwarz implies that

$\left\|Jg(x)\left(J\phi_{t}(x)\right)^{-1}\right\|_{\rm
HS}^{2}\leq\|Jg(x)\|_{\rm
HS}^{2}\left\|\left(J\phi_{t}(x)\right)^{-1}\right\|_{op}^{2}.$

From Lemma 6, we have $\|Jg(x)\|_{\rm
HS}\leq\frac{B_{2}d}{{{K}}}\|g\|_{{\mathcal{H}}}$. To bound the second term,
let us recall that $\phi_{t}=I-tg$ and that $t\leq\gamma$. Thus, the following
bound is true:

$\displaystyle\left\|\left(J\phi_{t}(x)\right)^{-1}\right\|_{op}$
$\displaystyle=\left\|\big{(}({\rm
I}_{d}-tJg)(x)\big{)}^{-1}\right\|_{op}\leq\sum_{k=0}^{\infty}\|tJg(x)\|_{op}^{k}\leq\sum_{k=0}^{\infty}\|\gamma
Jg(x)\|_{\rm HS}^{k}.$

Recalling (17) and combining it with Lemma 6 we obtain

$\displaystyle\left\|\left(J\phi_{t}(x)\right)^{-1}\right\|_{op}\leq\sum_{k=0}^{\infty}(\gamma\frac{B_{2}d}{{{K}}}\|g\|_{{\mathcal{H}}})^{k}\leq\sum_{k=0}^{\infty}\left(\frac{\alpha-1}{\alpha}\right)^{k}=\alpha.$

Summing up, we have that

$\psi_{1}(t)\leq\frac{\alpha^{2}B_{2}^{2}d^{2}}{{{K}}^{2}}\|g\|_{{\mathcal{H}}}^{2}.$
(34)

Next, we bound $\psi_{2}$. By definition

$\displaystyle\psi_{2}(t)$
$\displaystyle=\mathbb{E}_{\boldsymbol{X}\sim{\bar{\mu}}_{n}}\left[\left\langle
g(\boldsymbol{X}),\nabla^{2}V\left(\phi_{t}(\boldsymbol{X})\right)g(\boldsymbol{X})\right\rangle\right]\leq\mathbb{E}_{\boldsymbol{X}\sim{\bar{\mu}}_{n}}\left[\|\nabla^{2}{V}\left(\phi_{t}(\boldsymbol{X})\right)\|_{op}\|g(\boldsymbol{X})\|_{2}^{2}\right].$

Let us bound the norm of $g(x)$. The reproduction property of the RKHS yields
the following:

$\|g(x)\|_{2}^{2}=\sum_{i=1}^{d}\left\langle
k(x,.),g_{i}\right\rangle_{\mathcal{H}_{0}}^{2}\leq\|k(x,.)\|_{\mathcal{H}_{0}}^{2}\|g\|_{\mathcal{H}}^{2}\leq
B_{1}^{2}\|g\|_{\mathcal{H}}^{2}.$ (35)

Therefore,

$\psi_{2}(t)\leq
B_{1}^{2}\|g\|_{\mathcal{H}}^{2}\mathbb{E}_{\boldsymbol{X}\sim{\bar{\mu}}_{n}}\left[\|\nabla^{2}{V}\left(\phi_{t}(\boldsymbol{X})\right)\|_{op}\right].$
(36)

Let us bound
$\mathbb{E}_{\boldsymbol{X}\sim{\bar{\mu}}_{n}}\left[\|H_{V}\left(\phi_{t}(\boldsymbol{X})\right)\|_{op}\right]$.
3 implies the following inequality:

$\left\|\nabla^{2}V(\phi_{t}(x))\right\|_{op}\leq L_{0}+L_{1}\|\nabla
V(\phi_{t}(x))\|,$

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

To bound the term $\|\nabla V(\phi_{t}(x))\|$, we introduce the following
lemma from Sun et al. [2022] without proof.

######  Lemma 7.

Let $V$ be an $\left(L_{0},L_{1}\right)$-smooth function and $\Delta>0$ be a
constant. For any $x,x^{+}\in\mathbb{R}^{d}$ such that
$\left\|x^{+}-x\right\|\leq\Delta$, we have

$\left\|\nabla
V\left(x^{+}\right)\right\|\leq\frac{L_{0}}{L_{1}}\left(\exp(\Delta
L_{1})-1\right)+\|\nabla V(x)\|\exp(\Delta L_{1}).$

We will apply Lemma 7 to $\phi_{t}(x)$ and $\phi_{0}(x)$. By definition,
$\phi_{t}(x)-\phi_{0}(x)=tg(x)$ and according to inequality (35),

$\|\phi_{t}(x)-\phi_{0}(x)\|\leq tB_{1}\|g\|_{{\mathcal{H}}}.$

Thus, using Lemma 7 for $x=\phi_{0}(x)$, $x^{+}=\phi_{t}(x)$ and
$\Delta=tB_{1}\|g\|_{{\mathcal{H}}}$, we obtain the following:

$\displaystyle\left\|\nabla^{2}V(\phi_{t}(x))\right\|_{op}$ $\displaystyle\leq
L_{0}+L_{1}\left(\frac{L_{0}}{L_{1}}\big{(}\exp(tB_{1}\|g\|_{{\mathcal{H}}}L_{1})-1\big{)}+\left\|\nabla
V\left(\phi_{0}(x)\right)\right\|\exp(tB_{1}\|g\|_{{\mathcal{H}}}L_{1})\right)$
(37) $\displaystyle=\big{(}L_{0}+L_{1}\left\|\nabla
V\left(x\right)\right\|\big{)}\exp(tB_{1}\|g\|_{{\mathcal{H}}}L_{1}),$

where the last equality is due to $\phi_{0}(x)=x$. Combining (36) and (37) we
obtain

$\psi_{2}(t)\leq
B_{1}^{2}\|g\|_{{\mathcal{H}}}^{2}\left(L_{0}+L_{1}\mathbb{E}_{\boldsymbol{X}\sim{\bar{\mu}}_{n}}\big{[}\left\|\nabla
V(\boldsymbol{X})\right\|\big{]}\right)\exp(tB_{1}\|g\|_{{\mathcal{H}}}L_{1}).$

Summing up, the bounds on $\psi_{1}$ and $\psi_{2}$ yield the following
inequality:

$\displaystyle\varphi^{\prime\prime}(t)$
$\displaystyle\leq\|g\|_{{\mathcal{H}}}^{2}\Big{[}\frac{\alpha^{2}B_{2}^{2}d^{2}}{{{K}}^{2}}+B_{1}^{2}\Big{(}L_{0}+L_{1}\mathbb{E}_{\boldsymbol{X}\sim{\bar{\mu}}_{n}}\big{[}\left\|\nabla
V(\boldsymbol{X})\right\|\big{]}\Big{)}\exp(tB_{1}\|g\|_{{\mathcal{H}}}L_{1})\Big{]}$
$\displaystyle=\|g\|_{{\mathcal{H}}}^{2}\Big{[}\frac{\alpha^{2}B_{2}^{2}d^{2}}{{{K}}^{2}}+B_{1}^{2}A_{n}\exp(tB_{1}\|g\|_{{\mathcal{H}}}L_{1})\Big{]},$

recall that by definition
$A_{n}=\big{(}L_{0}+L_{1}\mathbb{E}_{\boldsymbol{X}\sim{\bar{\mu}}_{n}}\big{[}\left\|\nabla
V(\boldsymbol{X})\right\|\big{]}\big{)}$. Use the previous upper bound, we
have

$\displaystyle\int_{0}^{\gamma}(\gamma-t)\varphi^{\prime\prime}(t)dt$
$\displaystyle\leq\|g\|_{{\mathcal{H}}}^{2}\int_{0}^{\gamma}(\gamma-t)\Big{[}\frac{\alpha^{2}B_{2}^{2}d^{2}}{{{K}}^{2}}+B_{1}^{2}A_{n}\exp(tB_{1}\|g\|_{{\mathcal{H}}}L_{1})\Big{]}dt$
$\displaystyle=\frac{\gamma^{2}}{2}\|g\|_{{\mathcal{H}}}^{2}\frac{\alpha^{2}B_{2}^{2}d^{2}}{{{K}}^{2}}+B_{1}^{2}\|g\|_{{\mathcal{H}}}^{2}A_{n}\frac{\exp(\gamma
B_{1}\|g\|_{{\mathcal{H}}}L_{1})-\gamma_{1}B\|g\|_{{\mathcal{H}}}L_{1}-1}{B_{1}^{2}\|g\|^{2}_{{\mathcal{H}}}L_{1}^{2}}.$

One can check that $\exp(t)-t-1\leq(e-1)t^{2}/2$, when $t\in[0,1]$, since
$\gamma B_{1}\|g\|_{{\mathcal{H}}}L_{1}<1$, we deduce that

$\int_{0}^{\gamma}(\gamma-t)\varphi^{\prime\prime}(t)dt\leq\|g\|^{2}_{{\mathcal{H}}}\left(\frac{\gamma^{2}\alpha^{2}B_{2}^{2}d^{2}}{2{{K}}^{2}}+\frac{e-1}{2}B_{1}^{2}A_{n}\gamma^{2}\right),$
(38)

combine with (33), we finally have

$\displaystyle\varphi(\gamma)-\varphi(0)$
$\displaystyle\leq-\gamma\|g\|_{{\mathcal{H}}}^{2}+\gamma^{2}\|g\|^{2}_{{\mathcal{H}}}\left(\frac{\alpha^{2}B_{2}^{2}d^{2}}{2{{K}}^{2}}+\frac{e-1}{2}B_{1}^{2}A_{n}\right)$
$\displaystyle=-\gamma\left(1-\frac{1}{2}\gamma\left(\frac{\alpha^{2}B_{2}^{2}d^{2}}{{{K}}^{2}}+(e-1)B_{1}^{2}A_{n}\right)\right)\|g\|_{{\mathcal{H}}}^{2}$
$\displaystyle\overset{(i)}{\leq}-\frac{\gamma}{2}\|g\|_{{\mathcal{H}}}^{2},$

$(i)$ is since we choose
$\gamma\leq\frac{{{K}}^{2}}{\left(\alpha^{2}B_{2}^{2}d^{2}+{{K}}^{2}(e-1)B_{1}^{2}A_{n}\right)}$.

Finally, by Lemma 1
$\|g\|_{{\mathcal{H}}}^{2}=I_{MStein}({{\mu}}_{n}\mid{\pi})$. This concludes
the proof of the Proposition 1.

######  Remark 2.

One may notice that we did not use the exact formula of $g$ except for (33).
In fact the proposition remains true for a general $g\in{\mathcal{H}}$ with a
slight change. If we skip the last equality in (33) and repeat the other
steps, then we get the following:

$\varphi(\gamma)-\varphi(0)\leq-\gamma\left\langle
P_{\bar{\mu}}\nabla\log\left(\frac{{\bar{\mu}}_{n}}{\bar{\pi}}\right)(x),g(x)\right\rangle_{{\mathcal{H}}}+\frac{\gamma^{2}}{2}\|g\|^{2}_{{\mathcal{H}}}\left(\frac{\alpha^{2}B_{2}^{2}d^{2}}{{{K}}^{2}}+{(e-1)B_{1}^{2}A_{n}}\right).$
(39)

###  Appendix B  Lemmas

The following lemma is from [Bolley and Villani, 2005, Corollary 2.3.].

######  Lemma 8.

Let $\mathcal{X}$ be a measurable space equipped with a measurable distance
$\bf d$, let $p\geqslant 1$ and let $\nu$ be a probability measure on
$\mathcal{X}$. Assume that there exist $x_{0}\in\mathcal{X}$ and $s>0$ such
that $\int\exp({s{\bf d}\left(x_{0},x\right)^{p}})d\nu(x)$ is finite. Then

$\forall\mu\in{\mathcal{P}}(\mathcal{X}),\quad W_{p}(\mu,\nu)\leqslant
C_{\nu,p}\left[\mathop{\mathrm{KL}}\nolimits(\mu\mid\nu)^{\frac{1}{p}}+\left(\frac{\mathop{\mathrm{KL}}\nolimits(\mu\mid\nu)}{2}\right)^{\frac{1}{2p}}\right],$

where

$C_{\nu,p}:=2\inf_{x_{0}\in
X,s>0}\left(\frac{1}{s}\left(\frac{3}{2}+\log\int\exp({s{\bf
d}\left(x_{0},x\right)^{p}})d\nu(x)\right)\right)^{\frac{1}{p}}<+\infty.$ (40)

####  B.1 Proof of Lemmas

###### Proof of Lemma 1.

By the formula of transformation of probability densities, we first have
$\bar{\mu}(x)=\mu(\nabla\Psi^{*}(x))|\det\nabla^{2}\Psi(\nabla\Psi^{*}(x))|^{-1}$
and
$\bar{\pi}(x)=\pi(\nabla\Psi^{*}(x))|\det\nabla^{2}\Psi(\nabla\Psi^{*}(x))|^{-1}$,
so

$\log(\frac{\mu}{\pi})(\theta)=\log(\frac{\bar{\mu}}{\bar{\pi}})(x),$ (41)

where $x=\nabla\Psi(\theta)$. Since
$\mu(\theta)=\left(\nabla\Psi^{*}_{\\#}\bar{\mu}\right)(\theta)$, we have

$\displaystyle\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\theta)d\mu(\theta)$
(42)
$\displaystyle=\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\theta)d\left(\nabla\Psi^{*}_{\\#}\bar{\mu}\right)(\theta)$
$\displaystyle=\int_{x\in{\mathbb{R}}^{d}}k(\nabla\Psi^{*}(x),\cdot)\nabla^{2}\Psi(\nabla\Psi^{*}(x))^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\nabla\Psi^{*}(x))d\bar{\mu}(x)$
$\displaystyle=\int_{x\in{\mathbb{R}}^{d}}k(\nabla\Psi^{*}(x),\cdot)\nabla^{2}\Psi(\nabla\Psi^{*}(x))^{-1}\nabla_{\theta}\log(\frac{\bar{\mu}}{\bar{\pi}})(x)d\bar{\mu}(x)$
$\displaystyle=\int_{x\in{\mathbb{R}}^{d}}k(\nabla\Psi^{*}(x),\cdot)\nabla^{2}\Psi(\nabla\Psi^{*}(x))^{-1}\nabla^{2}\Psi(\nabla\Psi^{*}(x))\nabla_{x}\log(\frac{\bar{\mu}}{\bar{\pi}})(x)d\bar{\mu}(x)$
$\displaystyle=\int_{x\in{\mathbb{R}}^{d}}k(\nabla\Psi^{*}(x),\cdot)\nabla_{x}\log(\frac{\bar{\mu}}{\bar{\pi}})(x)d\bar{\mu}(x).$

Similarly, we have

$\displaystyle\int_{\theta\in\Omega}\int_{\theta^{\prime}\in\Omega}k(\theta,\theta^{\prime})\left<\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\theta),\nabla^{2}\Psi(\theta^{\prime})^{-1}\nabla_{\theta^{\prime}}\log(\frac{\mu}{\pi})(\theta^{\prime})\right>d\mu(\theta)d\mu(\theta^{\prime})$
(43)
$\displaystyle=\int_{\theta\in\Omega}\int_{\theta^{\prime}\in\Omega}k(\theta,\theta^{\prime})\left<\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\theta),\nabla^{2}\Psi(\theta^{\prime})^{-1}\nabla_{\theta^{\prime}}\log(\frac{\mu}{\pi})(\theta^{\prime})\right>d\left(\nabla\Psi^{*}_{\\#}\bar{\mu}\right)(\theta)d\left(\nabla\Psi^{*}_{\\#}\bar{\mu}\right)(\theta^{\prime})$
$\displaystyle=\int_{x\in{\mathbb{R}}^{d}}\int_{y\in{\mathbb{R}}^{d}}k(\nabla\Psi^{*}(x),\nabla\Psi^{*}(y))$
$\displaystyle\qquad\left<\nabla^{2}\Psi(\nabla\Psi^{*}(x))^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\nabla\Psi^{*}(x)),\nabla^{2}\Psi(\nabla\Psi^{*}(y))^{-1}\nabla_{\theta^{\prime}}\log(\frac{\mu}{\pi})(\nabla\Psi^{*}(y))\right>d\bar{\mu}(x)d\bar{\mu}(y)$
$\displaystyle=\int_{x\in{\mathbb{R}}^{d}}\int_{y\in{\mathbb{R}}^{d}}k(\nabla\Psi^{*}(x),\nabla\Psi^{*}(y))\left<\nabla^{2}\Psi(\nabla\Psi^{*}(x))^{-1}\nabla_{\theta}\log(\frac{\bar{\mu}}{\bar{\pi}})(x),\nabla^{2}\Psi(\nabla\Psi^{*}(y))^{-1}\nabla_{\theta^{\prime}}\log(\frac{\bar{\mu}}{\bar{\pi}})(y)\right>d\bar{\mu}(x)d\bar{\mu}(y)$
$\displaystyle=\int_{x\in{\mathbb{R}}^{d}}\int_{y\in{\mathbb{R}}^{d}}k(\nabla\Psi^{*}(x),\nabla\Psi^{*}(y))$
$\displaystyle\qquad\left<\nabla^{2}\Psi(\nabla\Psi^{*}(x))^{-1}\nabla^{2}\Psi(\nabla\Psi^{*}(x))\nabla_{x}\log(\frac{\bar{\mu}}{\bar{\pi}})(x),\nabla^{2}\Psi(\nabla\Psi^{*}(y))^{-1}\nabla^{2}\Psi(\nabla\Psi^{*}(y))\nabla_{y}\log(\frac{\bar{\mu}}{\bar{\pi}})(y)\right>d\bar{\mu}(x)d\bar{\mu}(y)$
$\displaystyle=\int_{x\in{\mathbb{R}}^{d}}\int_{y\in{\mathbb{R}}^{d}}k(\nabla\Psi^{*}(x),\nabla\Psi^{*}(y))\left<\nabla_{x}\log(\frac{\bar{\mu}}{\bar{\pi}})(x),\nabla_{y}\log(\frac{\bar{\mu}}{\bar{\pi}})(y)\right>d\bar{\mu}(x)d\bar{\mu}(y)$
$\displaystyle=\left\|g_{\bar{\mu}}\right\|_{{\mathcal{H}}}^{2},$

where $x=\nabla\Psi(\theta),y=\nabla\Psi(\theta^{\prime})$. ∎

###### Proof of Lemma 2.

The proof is direct.

$\displaystyle\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\frac{\mu}{\pi})(\theta)d\mu(\theta)$
(44)
$\displaystyle=\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\mu)(\theta)\mu(\theta)d\theta-\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\pi)(\theta)\mu(\theta)d\theta$
$\displaystyle=\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\mu(\theta)d\theta-\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\pi)(\theta)\mu(\theta)d\theta$
$\displaystyle\overset{(i)}{=}\int_{\theta\in\Omega}\nabla_{\theta}\cdot\left(k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\right)d\mu(\theta)-\int_{\theta\in\Omega}k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\nabla_{\theta}\log(\pi)(\theta)\mu(\theta)d\theta,$

$(i)$ is due to integration by parts and the assumption that
$k(\theta,\cdot)\nabla^{2}\Psi(\theta)^{-1}\mu(\theta)\to 0$ as
$\theta\to\partial\Omega$. ∎

Before we proceed to prove the left lemmas, we need to do some calculation
first. Let $e_{i}$ be the $i$-th standard basis of ${\mathbb{R}}^{d}$, then

$\displaystyle\langle\partial_{x_{i}}k(\nabla\Psi^{*}(x),\cdot),\partial_{y_{i}}k(\nabla\Psi^{*}(y),\cdot)\rangle_{{\mathcal{H}}_{0}}$
$\displaystyle=\lim_{\epsilon_{1}\to 0}\lim_{\epsilon_{2}\to
0}\langle\frac{k(\nabla\Psi^{*}(x+\epsilon_{1}e_{i}),\cdot)-k(\nabla\Psi(x),\cdot)}{\epsilon_{1}},\frac{k(\nabla\Psi^{*}(y+\epsilon_{2}e_{i}),\cdot)-k(\nabla\Psi^{*}(y),\cdot)}{\epsilon_{2}}\rangle_{{\mathcal{H}}_{0}}$
$\displaystyle=\lim_{\epsilon_{1}\to
0}\frac{1}{\epsilon_{1}}\left\\{\lim_{\epsilon_{2}\to
0}\frac{k(\nabla\Psi^{*}(x+\epsilon_{1}e_{i}),\nabla\Psi^{*}(y+\epsilon_{2}e_{i}))-k(\nabla\Psi^{*}(x+\epsilon_{1}e_{i}),\nabla\Psi^{*}(y))}{\epsilon_{1}\epsilon_{2}}\right.$
$\displaystyle\left.\quad-\lim_{\epsilon_{2}\to
0}\frac{k(\nabla\Psi^{*}(x),\nabla\Psi^{*}(y+\epsilon_{2}e_{i}))-k(\nabla\Psi^{*}(x),\nabla\Psi^{*}(y))}{\epsilon_{1}\epsilon_{2}}\right\\}$
$\displaystyle=\lim_{\epsilon_{1}\to
0}\frac{\sum_{j=1}^{d}\partial_{i}\partial_{j}\Psi^{*}(y)\left(\partial_{\theta^{\prime}_{j}}k(\nabla\Psi^{*}(x+\epsilon_{1}e_{i}),\theta^{\prime})-\partial_{\theta^{\prime}_{j}}k(\nabla\Psi^{*}(x),\theta^{\prime})\right)}{\epsilon_{1}}\mid_{\theta^{\prime}=\nabla\Psi^{*}(y)}$
$\displaystyle=\sum_{j,j^{\prime}}\partial_{i}\partial_{j}\Psi^{*}(x)\partial_{i}\partial_{j^{\prime}}\Psi^{*}(y)\partial_{\theta_{j}}\partial_{\theta^{\prime}_{j^{\prime}}}k(\theta,\theta^{\prime})\mid_{\theta=\nabla\Psi^{*}(x),\theta^{\prime}=\nabla\Psi^{*}(y)},$

set $x=y$ and denote $A(x)=\left(a_{ij}(x)\right)_{i=1,j=1}^{d,d}$ with
$a_{ij}(x):=\sum_{k=1}^{d}\partial_{k}\partial_{i}\Psi^{*}(x)\partial_{k}\partial_{j}\Psi^{*}(x)$.
Since $\Psi^{*}$ is convex, then $\nabla^{2}\Psi^{*}$ is non-negative definite
and so is $A(x)=\nabla^{2}\Psi^{*}(x)\nabla^{2}\Psi^{*}(x)$, and then
$|a_{ij}(x)|\leq\frac{a_{ii}+a_{jj}}{2}$ (since $a_{ii}a_{jj}-a_{ij}^{2}\geq
0$), so we have

$\displaystyle\left\|\nabla k_{\Psi}(x,\cdot)\right\|^{2}_{{\mathcal{H}}}$
$\displaystyle=\sum_{i=1}^{d}\langle\partial_{x_{i}}k(\nabla\Psi^{*}(x),\cdot),\partial_{x_{i}}k(\nabla\Psi^{*}(x),\cdot)\rangle_{{\mathcal{H}}_{0}}$
(45)
$\displaystyle\leq\frac{1}{2}B^{2}\sum_{j,j^{\prime}}\left(a_{jj}(x)+a_{j^{\prime}j^{\prime}}(x)\right)$
$\displaystyle=B^{2}d\operatorname{Tr}(A(x))$
$\displaystyle=B^{2}d\operatorname{Tr}(\nabla^{2}\Psi^{*}(x)\nabla^{2}\Psi^{*}(x))$
$\displaystyle\leq\frac{B^{2}d^{2}}{{{K}}^{2}}.$

###### Proof of Lemma 3.

Denote $\Phi(x):=k_{\Psi}(x,\cdot)\in\mathcal{H}$. Then by definition of the
Mirrored Stein Fisher information and integration bay parts, we have the
following:

$\displaystyle I_{MStein}({\mu}_{n}\mid{\pi})^{\frac{1}{2}}$
$\displaystyle=\left\|\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}(\nabla
V(\boldsymbol{X})\Phi(\boldsymbol{X})-\nabla\Phi(\boldsymbol{X}))\big{]}\right\|_{\mathcal{H}}$
$\displaystyle\leq\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla
V(\boldsymbol{X})\Phi(\boldsymbol{X})-\nabla\Phi(\boldsymbol{X})\big{]}\|_{\mathcal{H}}$
$\displaystyle\leq\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla
V(\boldsymbol{X})\Phi(\boldsymbol{X})\|_{\mathcal{H}}\big{]}+\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla\Phi(\boldsymbol{X})\|_{\mathcal{H}}\big{]}$
$\displaystyle=\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla
V(\boldsymbol{X})\|\|\Phi(\boldsymbol{X})\|_{\mathcal{H}}\big{]}+\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla\Phi(\boldsymbol{X})\|_{\mathcal{H}}\big{]}$
$\displaystyle\leq
B_{1}\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla
V(\boldsymbol{X})\|\big{]}+\frac{B_{2}d}{K}.$

∎

###### Proof of Lemma 4.

$\displaystyle\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}[\left\|\nabla
V(\boldsymbol{X})\right\|]$ $\displaystyle\leq
C_{p}\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}[\left\|\boldsymbol{X}\right\|^{p}]+C_{p}$
(46) $\displaystyle=C_{p}W_{p}^{p}(\bar{\mu}_{n},\delta_{0})+C_{p}$
$\displaystyle\leq
C_{p}\left(W_{p}(\bar{\mu}_{n},\bar{\pi})+W_{p}(\bar{\pi},\bar{\mu}_{0})+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}$
$\displaystyle\leq
C_{p}\left(C_{\bar{\pi},p}\left(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{n}\mid\bar{\pi})^{\frac{1}{p}}+\left(\frac{\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{n}\mid\bar{\pi})}{2}\right)^{\frac{1}{2p}}\right)\right.$
$\displaystyle\left.\quad+C_{\bar{\pi},p}\left(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})^{\frac{1}{p}}+\left(\frac{\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{2}\right)^{\frac{1}{2p}}\right)+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}$
$\displaystyle=C_{p}\left(C_{\bar{\pi},p}\left(G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{n}\mid\bar{\pi}))+G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))\right)+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}.$

∎

###### Proof of Lemma 6.

The proof is based on the reproducing property and Cauchy-Schwarz inequality
in the RKHS space. Indeed,

$\displaystyle\|Jh(x)\|_{\rm HS}^{2}$
$\displaystyle=\sum_{i,j=1}^{d}\left|\frac{\partial h_{i}(x)}{\partial
x_{j}}\right|^{2}$
$\displaystyle=\sum_{i,j=1}^{d}\left\langle\partial_{x_{j}}k_{\Psi}(x,.),h_{i}\right\rangle_{\mathcal{H}_{0}}$
$\displaystyle\leq\sum_{i,j=1}^{d}\left\|\partial_{x_{j}}k_{\Psi}(x,.)\right\|_{\mathcal{H}_{0}}^{2}\left\|h_{i}\right\|_{\mathcal{H}_{0}}^{2}$
$\displaystyle=\|\nabla
k_{\Psi}(x,.)\|_{\mathcal{H}}^{2}\left\|h\right\|_{\mathcal{H}}^{2}$
$\displaystyle\leq\frac{B^{2}d^{2}}{{{K}}^{2}}\left\|h\right\|_{\mathcal{H}}^{2}.$

This concludes the proof. ∎

###  Appendix C Main Theory

###### Proof of Theorem 1.

From Equation 17 and Lemma 3, we have

$\displaystyle\min\left\\{\frac{(\alpha-1){{K}}}{\alpha
B_{2}d\|g_{\bar{\mu}_{n}}\|_{{\mathcal{H}}}},\frac{1}{B_{1}\|g_{\bar{\mu}_{n}}\|_{{\mathcal{H}}}L_{1}},\frac{{{K}}^{2}}{\left(\alpha^{2}B_{2}^{2}d^{2}+{{K}}^{2}(e-1)B_{1}^{2}A_{n}\right)}\right\\}$
(47)
$\displaystyle\geq\min\left\\{\min\left\\{\frac{1}{B_{1}L_{1}},\frac{(\alpha-1){{K}}}{\alpha
B_{2}d}\right\\}\frac{K}{KB_{1}\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla
V(\boldsymbol{X})\|\big{]}+B_{2}d},\frac{{{K}}^{2}}{\alpha^{2}B_{2}^{2}d^{2}+{{K}}^{2}B_{1}^{2}(e-1)\left(L_{1}\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla
V(\boldsymbol{X})\|\big{]}+L_{0}\right)}\right\\}$
$\displaystyle=:{M}\left(\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla
V(\boldsymbol{X})\|\big{]}\right),$

so ${M}\left(\cdot\right)$ is a non-increasing function. By Lemma 4, we
further have

${M}\left(\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}\big{[}\|\nabla
V(\boldsymbol{X})\|\big{]}\right)\geq{M}\left(C_{p}\left(C_{\bar{\pi},p}\left(G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{n}\mid\bar{\pi}))+G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))\right)+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right).$
(48)

From now on, we will use mathematical induction. First,

$\displaystyle\gamma$
$\displaystyle\leq{M}\left(C_{p}\left(2C_{\bar{\pi},p}G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right)$
(49) $\displaystyle\leq\min\left\\{\frac{(\alpha-1){{K}}}{\alpha
B_{2}d\|g_{\bar{\mu}_{n}}\|_{{\mathcal{H}}}},\frac{1}{B_{1}\|g_{\bar{\mu}_{n}}\|_{{\mathcal{H}}}L_{1}},\frac{{{K}}^{2}}{\left(\alpha^{2}B_{2}^{2}d^{2}+{{K}}^{2}(e-1)B_{1}^{2}A_{n}\right)}\right\\},$

so it satisfies the condition of Proposition 1 and we will have
$\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{1}\mid\bar{\pi})\leq\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})$.
Next, suppose for integer $n\geq 1$, we have
$\gamma\leq{M}\left(C_{p}\left(2C_{\bar{\pi},p}G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right)$
satisfying the condition of Proposition 1 for $(\bar{\mu}_{k})_{k=0}^{n}$ (and
so the sequence
$\left(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{k}\mid\bar{\pi})\right)_{k=0}^{n}$
non-increasing), we need to prove
$\gamma\leq{M}\left(C_{p}\left(2C_{\bar{\pi},p}G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right)$
also satisfies the condition of Proposition 1, that is

$\displaystyle\gamma$
$\displaystyle\leq{M}\left(C_{p}\left(C_{\bar{\pi},p}\left(G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{n}\mid\bar{\pi}))+G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))\right)+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right)$
(50) $\displaystyle\leq\min\left\\{\frac{(\alpha-1){{K}}}{\alpha
B_{2}d\|g_{\bar{\mu}_{n}}\|_{{\mathcal{H}}}},\frac{1}{B_{1}\|g_{\bar{\mu}_{n}}\|_{{\mathcal{H}}}L_{1}},\frac{{{K}}^{2}}{\left(\alpha^{2}B_{2}^{2}d^{2}+{{K}}^{2}(e-1)B_{1}^{2}A_{n}\right)}\right\\}$

(50) is due to the non-increasing property of sequence
$\left(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{k}\mid\bar{\pi})\right)_{k=0}^{n}$,

$\displaystyle\gamma$
$\displaystyle\leq{M}\left(C_{p}\left(2C_{\bar{\pi},p}G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right)$
(51)
$\displaystyle\leq{M}\left(C_{p}\left(C_{\bar{\pi},p}\left(G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{1}\mid\bar{\pi}))+G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))\right)+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right)$
$\displaystyle\qquad\vdots$
$\displaystyle\leq{M}\left(C_{p}\left(C_{\bar{\pi},p}\left(G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{n}\mid\bar{\pi}))+G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))\right)+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right)$
$\displaystyle\leq\min\left\\{\frac{(\alpha-1){{K}}}{\alpha
B_{2}d\|g_{\bar{\mu}_{n}}\|_{{\mathcal{H}}}},\frac{1}{B_{1}\|g_{\bar{\mu}_{n}}\|_{{\mathcal{H}}}L_{1}},\frac{{{K}}^{2}}{\left(\alpha^{2}B_{2}^{2}d^{2}+{{K}}^{2}(e-1)B_{1}^{2}A_{n}\right)}\right\\}.$

So by Proposition 1, we have
$\left(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{k}\mid\bar{\pi})\right)_{k=0}^{n+1}$
non-increasing. By mathematical induction, we proved the theorem. ∎

####  C.1 Complexity Analysis

In this section, we denote $\Pi$ as the area of unit radius circle. Assume
$\bar{\mu}_{0}={\mathcal{N}}(0,{\rm I}_{d})$, we need first calculate the
value of
$\int_{x\in{\mathbb{R}}^{d}}\left\|x\right\|^{p+1}\bar{\mu}_{0}(x)dx$.

######  Lemma 9.

Assume $\bar{\mu}_{0}={\mathcal{N}}(0,{\rm I}_{d})$, then for any $p>-d-1$ we
have

$\int_{x\in{\mathbb{R}}^{d}}\left\|x\right\|^{p+1}\bar{\mu}_{0}(x)dx=2^{(p+1)/2}\frac{\Gamma(\frac{p+d+1}{2})}{\Gamma(\frac{d}{2})}.$
(52)

###### Proof.

We integrate this in polar coordinate
$\left(r,\varphi_{1},\ldots,\varphi_{d-1}\right)$.

$\displaystyle\int_{x\in{\mathbb{R}}^{d}}\left\|x\right\|^{p+1}\bar{\mu}_{0}(x)dx$
(53)
$\displaystyle=(2\Pi)^{-d/2}\int_{x\in{\mathbb{R}}^{d}}\left\|x\right\|^{p+1}\exp(-\left\|x\right\|^{2}/2)dx$
$\displaystyle=(2\Pi)^{-d/2}\int_{0}^{\infty}\int_{0}^{\Pi}\cdots\int_{0}^{\Pi}\int_{0}^{2\Pi}r^{p+1}\exp(-r^{2}/2)r^{d-1}\sin^{d-2}\left(\varphi_{1}\right)\sin^{d-3}\left(\varphi_{2}\right)\cdots\sin\left(\varphi_{d-2}\right)drd\varphi_{1}d\varphi_{2}\cdots
d\varphi_{d-1}$
$\displaystyle=(2\Pi)^{-d/2}\frac{\sqrt{2\Pi}}{2}\frac{1}{\sqrt{2\Pi}}\int_{-\infty}^{\infty}r^{p+d}\exp(-r^{2}/2)dr\int_{0}^{\Pi}\cdots\int_{0}^{\Pi}\int_{0}^{2\Pi}\sin^{d-2}\left(\varphi_{1}\right)\sin^{d-3}\left(\varphi_{2}\right)\cdots\sin\left(\varphi_{d-2}\right)d\varphi_{1}d\varphi_{2}\cdots
d\varphi_{d-1}$ $\displaystyle=\frac{(2\Pi)^{-(d-1)/2}}{2}M_{p+d}|S_{d-1}|$
$\displaystyle=\frac{(2\Pi)^{-(d-1)/2}}{2}M_{p+d}\frac{2\Pi^{\frac{d}{2}}}{\Gamma\left(\frac{d}{2}\right)}$
$\displaystyle=\frac{(2\Pi)^{-(d-1)/2}}{2}\frac{2^{(p+d)/2}\Gamma\left(\frac{p+d+1}{2}\right)}{\sqrt{\Pi}}\frac{2\Pi^{\frac{d}{2}}}{\Gamma\left(\frac{d}{2}\right)}$
$\displaystyle=2^{(p+1)/2}\frac{\Gamma(\frac{p+d+1}{2})}{\Gamma(\frac{d}{2})},$

where $|S_{d-1}|$ is the $d-1$-dimensional volume of the sphere $S_{d-1}$,
$M_{p+1}:=\int_{x\in{\mathbb{R}}}|x|^{p+1}\frac{1}{\sqrt{2\Pi}}e^{-\frac{x^{2}}{2}}dx$
and from Winkelbauer [2012], we know the $p+1$-th central absolute moment is
$M_{p+1}=\frac{2^{(p+1)/2}\Gamma(\frac{p+2}{2})}{\sqrt{\Pi}}={\mathcal{O}}(\sqrt{2p}\left(\frac{p}{e}\right)^{\frac{p}{2}})$.
∎

Assume $\bar{\pi}(x)=e^{-V(x)}$, then we have the following lemma.

######  Lemma 10.

Let 6 hold and $\bar{\mu}_{0}={\mathcal{N}}(0,{\rm I}_{d})$, we then have

$\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})\leq\frac{d}{2}\log(\frac{1}{2\Pi
e})+V(0)+\frac{C_{p}}{p+1}\left(2^{(p+1)/2}\frac{\Gamma(\frac{p+d+1}{2})}{\Gamma(\frac{d}{2})}+(p+1)\sqrt{2}\frac{\Gamma(\frac{d+1}{2})}{\Gamma(\frac{d}{2})}\right).$
(54)

###### Proof.

By6, we know

$\big{\|}\nabla V(x)\big{\|}\leq C_{p}\left(\left\|x\right\|^{p}+1\right),$
(55)

so

$\displaystyle V(x)$ $\displaystyle=\int_{0}^{1}\left<\nabla
V(tx),x\right>dt+V(0)$ (56) $\displaystyle\leq\int_{0}^{1}\left\|\nabla
V(tx)\right\|\left\|x\right\|dt+V(0)$
$\displaystyle\leq\int_{0}^{1}C_{p}\left(\left\|tx\right\|^{p}+1\right)\left\|x\right\|dt+V(0)$
$\displaystyle\leq
C_{p}\left(\frac{\left\|x\right\|^{p+1}}{p+1}+\left\|x\right\|\right)+V(0).$

We procced to calculate
$\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})$,

$\displaystyle\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})$
$\displaystyle=\int_{x\in{\mathbb{R}}^{d}}\log(\frac{\bar{\mu}_{0}}{\bar{\pi}})(x)\bar{\mu}_{0}(x)dx$
(57)
$\displaystyle=\int_{x\in{\mathbb{R}}^{d}}\log(\bar{\mu}_{0})(x)\bar{\mu}_{0}(x)dx+\int_{x\in{\mathbb{R}}^{d}}V(x)\bar{\mu}_{0}(x)dx$
$\displaystyle\leq\frac{d}{2}\log(\frac{1}{2\Pi
e})+\int_{x\in{\mathbb{R}}^{d}}\left(C_{p}\left(\frac{\left\|x\right\|^{p+1}}{p+1}+\left\|x\right\|\right)+V(0)\right)\bar{\mu}_{0}(x)dx$
$\displaystyle=\frac{d}{2}\log(\frac{1}{2\Pi
e})+V(0)+\frac{C_{p}}{p+1}\int_{x\in{\mathbb{R}}^{d}}{\left\|x\right\|^{p+1}}+(p+1)\left\|x\right\|\bar{\mu}_{0}(x)dx$
$\displaystyle=\frac{d}{2}\log(\frac{1}{2\Pi
e})+V(0)+\frac{C_{p}}{p+1}\left(2^{(p+1)/2}\frac{\Gamma(\frac{p+d+1}{2})}{\Gamma(\frac{d}{2})}+(p+1)\sqrt{2}\frac{\Gamma(\frac{d+1}{2})}{\Gamma(\frac{d}{2})}\right)$

where we use Lemma 9. ∎

According to Lemma 10, the order of
$\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})$ is

$\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})=\tilde{\mathcal{O}}\left(\frac{2^{(p+1)/2}\Gamma(\frac{p+d+1}{2})}{(p+1)\Gamma(\frac{d}{2})}\right).$
(58)

###### Proof of Corollary 1.

By Theorem 1, we know that

$\frac{1}{n}\sum_{k=0}^{n-1}I_{MStein}\left(\bar{\mu}_{k}\mid\bar{\pi}\right)\leq\frac{2\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{n\gamma},$

we need to estimate the order of
$\frac{\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{\gamma}$.
Firstly, from Lemma 10 we know
$\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})={{\mathcal{O}}}((C_{p}+1)dM_{p})$,
so

$\displaystyle
G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))$
$\displaystyle=\left(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})^{\frac{1}{p}}+\left(\frac{\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{2}\right)^{\frac{1}{2p}}\right)$
(59)
$\displaystyle={{\mathcal{O}}}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})^{\frac{1}{p}}).$

Next, we estimate the order of $\frac{1}{\gamma}$, we have

$\displaystyle\frac{1}{\gamma}$
$\displaystyle=\frac{1}{{M}\left(C_{p}\left(2C_{\bar{\pi},p}G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}\right)}$
(60)
$\displaystyle=\tilde{\mathcal{O}}(\left(2C_{\bar{\pi},p}G_{p}(\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi}))+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p})$
$\displaystyle=\tilde{\mathcal{O}}\left(2C_{\bar{\pi},p}\left(\frac{2^{(p+1)/2}\Gamma(\frac{p+d+1}{2})}{(p+1)\Gamma(\frac{d}{2})}\right)^{\frac{1}{p}}+\left(2^{\frac{p}{2}}\frac{\Gamma(\frac{p+d}{2})}{\Gamma(\frac{d}{2})}\right)^{\frac{1}{p}}\right)^{p}$
$\displaystyle=\tilde{\mathcal{O}}\left(\frac{32^{\frac{p}{2}}C_{\bar{\pi},p}^{p}\Gamma(\frac{p+d+1}{2})}{(p+1)\Gamma(\frac{d}{2})}\right).$

So we finally have

$\frac{\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{\gamma}=\tilde{\mathcal{O}}\left(\frac{8^{p}C_{\bar{\pi},p}^{p}\Gamma(\frac{p+d+1}{2})^{2}}{(p+1)^{2}\Gamma(\frac{d}{2})^{2}}\right),$
(61)

to get
$\frac{2\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{n\gamma}\leq\varepsilon$,
we need
$n\geq\frac{2\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{\gamma\varepsilon}$,
that is

$n=\tilde{\Omega}\left(\frac{8^{p}C_{\bar{\pi},p}^{p}\Gamma(\frac{p+d+1}{2})^{2}}{(p+1)^{2}\Gamma(\frac{d}{2})^{2}\varepsilon}\right).$
(62)

∎

By  the Stirling formula  $\Gamma(z+1)\sim\sqrt{2\Pi
z}\left(\frac{z}{e}\right)^{z}$, we know

$\displaystyle\frac{\Gamma(\frac{p+d+1}{2})^{2}}{\Gamma(\frac{d}{2})^{2}}$
$\displaystyle=\Omega\left(\frac{{\Pi(d+p-1)}\left(\frac{d+p-1}{2e}\right)^{{d+p-1}}}{{\Pi(d-2)}\left(\frac{d-2}{2e}\right)^{{d-2}}}\right)$
(63)
$\displaystyle=\Omega\left(\left(\frac{d+p-1}{d-2}\right)^{d-2}\left(\frac{d+p-1}{2e}\right)^{p+1}\right)$
$\displaystyle=\Omega\left(d^{p+1}\right),\quad\text{where we only consider
the order of $d$},$

so the iteration complexity has dimension dependency of order $p+1$.

###  Appendix D The Cases under $\text{T}_{p}$ inequality with $1\leq p\leq 2$

###### Proof of Lemma 5.

$\displaystyle\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}[\left\|\nabla
V(\boldsymbol{X})\right\|]$ $\displaystyle\leq
C_{p}\mathbb{E}_{\boldsymbol{X}\sim\bar{\mu}_{n}}[\left\|\boldsymbol{X}\right\|^{p}]+C_{p}$
(64) $\displaystyle=C_{p}W_{p}^{p}(\bar{\mu}_{n},\delta_{0})+C_{p}$
$\displaystyle\leq
C_{p}\left(W_{p}(\bar{\mu}_{n},\bar{\pi})+W_{p}(\bar{\pi},\bar{\mu}_{0})+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}$
$\displaystyle\leq
C_{p}\left(\sqrt{\frac{2\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{n}\mid\bar{\pi})}{\lambda}}+\sqrt{\frac{2\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{\lambda}}+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}+C_{p}$

∎

###### Proof of Theorem 2.

The proof is the same as the one for Theorem 1 but with this new bound (25). ∎

###### Proof of Corollary 2.

Similar to the proof of Corollary 1, we need to estimate the order of
$\frac{\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{\gamma}$. By
Equation 58 and  the Stirling formula  $\Gamma(z+1)\sim\sqrt{2\Pi
z}\left(\frac{z}{e}\right)^{z}$, we know

$\displaystyle\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})$
$\displaystyle=\tilde{\mathcal{O}}\left(\frac{\Gamma(\frac{p+d+1}{2})}{\Gamma(\frac{d}{2})}\right)$
(65)
$\displaystyle=\tilde{{\mathcal{O}}}\left(\frac{\sqrt{\Pi(d+p-1)}\left(\frac{d+p-1}{2e}\right)^{\frac{d+p-1}{2}}}{\sqrt{\Pi(d-2)}\left(\frac{d-2}{2e}\right)^{\frac{d-2}{2}}}\right)$
$\displaystyle=\tilde{{\mathcal{O}}}\left(\left(\frac{d+p-1}{d-2}\right)^{\frac{d-2}{2}}\left(\frac{d+p-1}{2e}\right)^{\frac{p+1}{2}}\right)$
$\displaystyle=\tilde{{\mathcal{O}}}\left(d^{\frac{p+1}{2}}\right),$

we also know

$\displaystyle
W_{p}^{p}(\bar{\mu}_{0},\delta_{0})=\int_{x\in{\mathbb{R}}^{d}}\left\|x\right\|^{p}d\bar{\mu}_{0}(x)=2^{\frac{p}{2}}\frac{\Gamma(\frac{p+d}{2})}{\Gamma{\frac{d}{2}}}={\mathcal{O}}\left(d^{\frac{p}{2}}\right).$
(66)

So we have

$\displaystyle\left(2\sqrt{\frac{2\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{\lambda}}+W_{p}(\bar{\mu}_{0},\delta_{0})\right)^{p}$
(67)
$\displaystyle=\tilde{{\mathcal{O}}}\left(\left(\sqrt{\frac{1}{\lambda}}d^{\frac{p+1}{4}}+d^{\frac{1}{2}}\right)^{p}\right)$
$\displaystyle=\tilde{{\mathcal{O}}}\left(\max\left\\{\frac{1}{\lambda^{\frac{p}{2}}}d^{\frac{p(p+1)}{4}},d^{\frac{p}{2}}\right\\}\right)$
$\displaystyle=\tilde{{\mathcal{O}}}\left(\frac{d^{\frac{p(p+1)}{4}}}{\lambda^{\frac{p}{2}}}\right),$

and then

$\displaystyle\frac{\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{\gamma}$
$\displaystyle=\tilde{{\mathcal{O}}}\left(\frac{d^{\frac{p(p+1)}{4}}}{\lambda^{\frac{p}{2}}}d^{\frac{p+1}{2}}\right)$
(68)
$\displaystyle=\tilde{{\mathcal{O}}}\left(\frac{d^{\frac{(p+2)(p+1)}{4}}}{\lambda^{\frac{p}{2}}}\right).$

To get
$\frac{2\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{n\gamma}\leq\varepsilon$,
we need
$n\geq\frac{2\mathop{\mathrm{KL}}\nolimits(\bar{\mu}_{0}\mid\bar{\pi})}{\gamma\varepsilon}$,
that is

$n=\tilde{\Omega}\left(\frac{d^{\frac{(p+2)(p+1)}{4}}}{\lambda^{\frac{p}{2}}\varepsilon}\right).$
(69)

∎