Improved Finite-Particle Convergence Rates for Stein Variational Gradient Descent

## Abstract

Abstract. We provide finite-particle convergence rates for the Stein Variational Gradient Descent (SVGD) algorithm in the Kernelized Stein Discrepancy ( 𝖪𝖲𝖣 𝖪𝖲𝖣 \mathsf{KSD} ) and Wasserstein-2 metrics. Our key insight is that the time derivative of the relative entropy between the joint density of N 𝑁 N particle locations and the N 𝑁 N -fold product target measure, starting from a regular initial distribution, splits into a dominant ‘negative part’ proportional to N 𝑁 N times the expected 𝖪𝖲𝖣 2 superscript 𝖪𝖲𝖣 2 \mathsf{KSD}^{2} and a smaller ‘positive part’. This observation leads to 𝖪𝖲𝖣 𝖪𝖲𝖣 \mathsf{KSD} rates of order 1 / N 1 𝑁 1/\sqrt{N} , in both continuous and discrete time, providing a near optimal (in the sense of matching the corresponding i.i.d. rates) double exponential improvement over the recent result by Shi and Mackey ( 2024 ) . Under mild assumptions on the kernel and potential, these bounds also grow polynomially in the dimension d 𝑑 d . By adding a bilinear component to the kernel, the above approach is used to further obtain Wasserstein-2 convergence in continuous time. For the case of ‘bilinear + Matérn’ kernels, we derive Wasserstein-2 rates that exhibit a curse-of-dimensionality similar to the i.i.d. setting. We also obtain marginal convergence and long-time propagation of chaos results for the time-averaged particle laws.

## 1. Introduction

Stein Variational Gradient Descent (SVGD) (Liu and Wang, ) is a widely-used deterministic particle-based algorithm for sampling from a target density $\pi\propto\exp(-V)$, where $V:\mathbb{R}^{d}\to\mathbb{R}$ is the potential function. For a given symmetric, positive-definite kernel $\textsf{k}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$, discrete time-step $n\in\mathbb{N}_{0},$ step-size $\eta>0$, and for $1\leq i\leq N$, the SVGD algorithm is given by

$$ $\displaystyle x^{N}_{i}(n+1)=x^{N}_{i}(n)-\frac{\eta}{N}\sum_{j}\left[\textsf{k}(x^{N}_{i}(n),x^{N}_{j}(n))\nabla V(x^{N}_{j}(n))-\nabla_{2}\textsf{k}(x^{N}_{i}(n),x_{j}^{N}(n))\right].$ (1) $$

SVGD provides a compelling alternative to more classical randomized sampling algorithms like Markov Chain Monte Carlo (MCMC) that require additional uncertainty quantification with respect to the algorithmic randomness. It has attracted considerable attention in the machine learning and applied mathematics communities because of its fascinating theoretical properties and broad range of applications (Feng et al., ; Haarnoja et al., ; Lambert et al., ; Liu et al., ; Xu et al., ). Our focus in this work is on deriving rates of convergence of the SVGD algorithm in ([1](#S1.E1)) and the corresponding continuous-time, $N$-particle SVGD dynamics on $\mathbb{R}^{d}$, obtained by letting $\eta\to 0_{+}$, given by

$$ $\displaystyle\dot{x}^{N}_{i}(t)=-\frac{1}{N}\sum_{j}\textsf{k}(x^{N}_{i}(t),x^{N}_{j}(t))\nabla V(x^{N}_{j}(t))+\frac{1}{N}\sum_{j}\nabla_{2}\textsf{k}(x^{N}_{i}(t),x_{j}^{N}(t)),$ (2) $$

with $\dot{x}$ denoting the time derivative and $\nabla_{2}$ represents gradient with respect to the second argument. Throughout the paper, we will implicitly assume the existence of a solution to the above equation and the completeness of the vector field driving the above dynamics in $\left(\mathbb{R}^{d}\right)^{N}$. This is satisfied, for example, under standard continuity and linear growth assumptions on the driving vector field.

Background and past work: The motivation for SVGD originates from the *gradient flow for the relative entropy* on the Wasserstein-2 space of probability measures on $\mathbb{R}^{d}$. More precisely, for a probability measure $\mu$ on $\mathbb{R}^{d}$ possessing a regular enough positive density, the Wasserstein gradient flow is given by the measure-valued trajectory $\mu_{t}$ satisfying the continuity equation

$$ $\partial_{t}\mu_{t}+\nabla\cdot(v_{t}\mu_{t})=0,\quad\mu_{0}=\mu,$ (3) $$

where $v_{t}=-\nabla\log(p_{t}/\pi)$ and $p_{t}$ is the density of $\mu_{t}$. Under suitable conditions, $\mu_{t}$ can be shown to converge (often with quantifiable fast rates) to $\pi$. Unfortunately, this approach is not practically implementable via particle discretization as the associated empirical measure approximating $\mu_{t}$ does not possess a density.

In a very influential paper, Liu and Wang () devised a *projected* gradient descent algorithm by projecting the velocity vector $v_{t}$ along a reproducing kernel Hilbert space (RKHS) associated with a symmetric positive definite kernel k. This leads to a flow analogous to ([3](#S1.E3)) but with $v_{t}=-P_{\mu_{t}}\nabla\log(p_{t}/\pi)$, where the projection $P_{\mu_{t}}$ is given by $P_{\nu}f(x)\coloneqq\int\textsf{k}(x,y)f(y)\nu(\mathsf{d}y)$ for probability measure $\nu$ and function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ for which the integral is well-defined. The key observation of Liu and Wang () was that, by applying integration by parts, one obtains

$$ $-P_{\mu_{t}}\nabla\log(p_{t}/\pi)(x)=\int\left(-k(x,y)\nabla V(y)+\nabla_{2}k(x,y)\right)\mu_{t}(\mathsf{d}y).$ $$

The right hand side is well-defined even when $\mu_{t}$ lacks a density and is hence amenable to particle discretization, which leads to the SVGD equations ([1](#S1.E1)) and ([2](#S1.E2)). See Korba et al. () for a more detailed description of this approach.

With this motivation, the following diagram from Liu et al. () highlights the major goals involved in rigorously analyzing the SVGD dynamics.

$$ ${{\text{Initial particles}\atop\mu^{N}(0)=\frac{1}{N}\sum_{j=1}^{N}\delta_{{x}_{j}(0)}}}$ ${{\text{Evolving particles}\atop\mu^{N}(t)=\frac{1}{N}\sum_{j=1}^{N}\delta_{{x}_{j}(t)}}}$ ${{\text{Equilibrium}\atop\mu^{N}(\infty)=\frac{1}{N}\sum_{j=1}^{N}\delta_{{x}_{j}(\infty)}}}$ ${{\text{Initial density}\atop\mu_{0}}}$ ${{\text{Evolving density}\atop\mu_{t}}}$ ${{\text{Target}\atop\mu_{\infty}=\pi}}$ $\scriptstyle{(c)}$ $\scriptstyle{(b)}$ $\scriptstyle{(e)}$ $\scriptstyle{(d)}$ $\scriptstyle{(a)}$ $$

- (a)
Unified convergence of the empirical measure for $N<\infty$ particles to the continuous target as time $t$ and $N$ jointly grow to infinity;
- (b)
Convergence of mean-field SVGD to the target distribution over time;
- (c)
Convergence of the empirical measure for finite particles to the mean-field distribution at any finite given time $t\in[0,\infty)$;
- (d)
Convergence of finite-particle SVGD to equilibrium over time;
- (e)
Convergence of the empirical measure for finite particles to the continuous target at time $t=\infty$.

Practically speaking, [(a)](#S1.I1.i1) is the ideal outcome that completely defines the algorithmic behavior of SVGD. One approach towards this is to combine either [(b)](#S1.I1.i2) and [(c)](#S1.I1.i3) or [(d)](#S1.I1.i4) and [(e)](#S1.I1.i5) in a quantitative way to yield [(a)](#S1.I1.i1). Regarding [(b)](#S1.I1.i2), Liu () showed the convergence of mean-field SVGD (solution to ([3](#S1.E3)) with $v_{t}=-P_{\mu_{t}}\nabla\log(p_{t}/\pi)$) in Kernelized Stein Discrepancy ($\mathsf{KSD}$, Chwialkowski et al. (); Liu et al. (); Gorham and Mackey ()), which is known to imply weak convergence under appropriate assumptions. Korba et al. (); Chewi et al. (); Salim et al. (); Sun et al. (); Duncan et al. () sharpened the results with weaker conditions or explicit rates. He et al. () extended the above result to the stronger Fisher information metric and Kullback–Leibler divergence based on a regularization technique.
Lu et al. (); Gorham et al. (); Korba et al. () obtained time-dependent mean-field convergence [(c)](#S1.I1.i3) under various assumptions using techniques from partial differential equations and from the literature of ‘propagation of chaos’. In particular, Lu et al. () derived the mean-field PDE ([3](#S1.E3)) for the evolving density that emerges as the mean-field limit of the finite-particle SVGD systems, and showed the well-posedness of the PDE solutions. Carrillo and Skrzeczkowski () established refined stability estimates in comparison to Lu et al. () for the mean-field system when the initial distribution is close to the target distribution in a suitable sense. In particular, they increase the length of the time interval in which mean-field approximation is meaningful from $\approx\log\log N$ to $\approx\sqrt{N}$ for such initial data close to the target.

Shi and Mackey () obtained refined results for [(c)](#S1.I1.i3) and combined them with [(b)](#S1.I1.i2) to get the *first unified convergence* [(a)](#S1.I1.i1) in terms of KSD. However, they have a rather slow rate of order $1/\sqrt{\log\log N}$, resulting from the fact that their bounds for [(c)](#S1.I1.i3) still depend on the time $t$ (sum of step sizes) double-exponentially. Note that studying the convergence [(d)](#S1.I1.i4) and [(e)](#S1.I1.i5), provides another way to characterize the unified convergence [(a)](#S1.I1.i1) for SVGD. Liu et al. () analyzed this strategy for the *Gaussian SVGD* case where the target distribution $\pi$ and initial distribution $\mu$ are both Gaussian and the kernel k is bilinear. In this case, the flow of measures for the mean-field SVGD remains Gaussian for all time and this fact was exploited to obtain detailed rates and ‘uniform-in-time’ propagation of chaos results. Das and Nagaraj () obtained a polynomial convergence rate ($O(N^{-\alpha})$ for some $\alpha>0$) for a related but different algorithm, which they called *SVGD with virtual particles*, by adding more randomness to the dynamics and using stochastic approximation techniques. The recent work of Priser et al. () also studies finite-particle asymptotics, albeit for not the original SVGD iterates (as in ([1](#S1.E1))) but for a modified one where a Langevin-type regularization including a Gaussian noise is added at each step. Hence, they leverage existing techniques for Langevin Monte Carlo to establish their results. However, their techniques are not applicable to the deterministic SVGD system in ([1](#S1.E1)).

Challenges for finite-particle SVGD: In comparison to the numerous works quantifying convergence rates for the mean-field SVGD equation, only Shi and Mackey () and Liu et al. () discussed above have made attempts towards obtaining rates for the finite-particle version of (deterministic) SVGD. This has been perceived as a challenging open problem till date. The tractability of the mean-field SVGD equation comes from the observation that it has a (projected) gradient structure which leads to the following monotonicity property of the KL-divergence:

$$ $\partial_{t}\mathsf{KL}(\mu_{t}||\pi)=-\mathsf{KSD}^{2}(\mu_{t}||\pi),\quad t\geq 0.$ $$

The non-negativity of $\mathsf{KL}$ then leads to bounds on the $\mathsf{KSD}$. For the finite-particle versions ([1](#S1.E1)) and ([2](#S1.E2)), there is no gradient structure to the dynamics, which renders the above approach inapplicable. Moreover, the vector field driving the finite-particle dynamics is not globally Lipschitz and lacks suitable convexity properties. This results in double-exponentially growing bounds in time between the particle empirical distribution and the mean-field limit (see Lu et al. (, Prop. 2.6) and Shi and Mackey (, Thm. 1)). As a consequence, trying to obtain [(a)](#S1.I1.i1) using [(b)](#S1.I1.i2) and [(c)](#S1.I1.i3) in the general (non-Gaussian) setting yields the slow convergence rate $1/\sqrt{\log\log N}$. In Das and Nagaraj (), the authors tried to deliberately bypass this approach in the finite-particle setting, which leads to better rates, but their approach needs an altogether different, albeit related, algorithm with additional randomness driving the dynamics.

Our contribution: A key insight in this paper is to work with the *joint density* of the particle locations, when started from a suitably regular initial distribution, and track the evolution of its relative entropy with respect to the $N$-fold product measure $\pi^{\otimes N}$. It turns out that the time derivative of this relative entropy has a ‘negative part’ that is exactly $N$ times the expected $\mathsf{KSD}^{2}$ of the empirical measure at time $t$ with respect to $\pi$, and a ‘positive part’ that can be separately handled and shown to be small in comparison to the negative part (see ([2](#S2.Ex20))). This gives a novel connection between the joint particle dynamics and the empirical measure evolution. While analyzing the deterministic SVGD, in comparison to Shi and Mackey () which uses [(b)](#S1.I1.i2) and [(c)](#S1.I1.i3) or Liu et al. () which uses [(d)](#S1.I1.i4) and [(e)](#S1.I1.i5), we directly provide convergence rates for [(a)](#S1.I1.i1) using the above strategy.

Our first main result, Theorem [1](#Thmtheorem1), exploits this observation to obtain $O(1/\sqrt{N})$ bounds for the expected $\mathsf{KSD}$ between $\mu_{av}^{N}\coloneqq\frac{1}{N}\int_{0}^{N}\mu^{N}(t)\mathsf{d}t$ and $\pi$ for the continuous-time SVGD dynamics in ([2](#S1.E2)). Analogous bounds for the discrete-time SVGD dynamics in ([1](#S1.E1)) are obtained in Theorem [3](#Thmtheorem3). Together, these results constitute a *double exponential improvement over Shi and Mackey () for the true SVGD algorithm*. As discussed in Remark [2](#Thmremark2), the bounds in Theorem [1](#Thmtheorem1) are *essentially optimal* when compared with the $\mathsf{KSD}$ in the i.i.d. setting, and *grow linearly in $d$* (that is, $\mathsf{KSD}$ is $O(d/\sqrt{N})$) under mild assumptions on the kernel and the potential. Moreover, unlike previous works even for the mean-field SVGD, we do not require any assumptions on the tail behavior (such as sub-Gaussianity) of the target $\pi$ in Theorem [1](#Thmtheorem1). Further, it follows from Gorham and Mackey () that the $\mathsf{KSD}$ bound alone does not even guarantee weak convergence of the particle marginal laws as $N\rightarrow\infty$, unless one establishes tightness of these laws. Our approach gives control on the relative entropy of the joint law in time which, in turn, gives the desired tightness and weak convergence for the time-averaged particle marginal laws $\bar{\mu}^{N}(\mathsf{d}x)\coloneqq\frac{1}{N}\int_{0}^{N}\mathbb{P}(x_{1}(t)\in\mathsf{d}x)\mathsf{d}t$ for exchangeable initial conditions, see Theorem [2](#Thmtheorem2).

The discrete-time SVGD bound in Theorem [3](#Thmtheorem3), although similar in flavor to Theorem [1](#Thmtheorem1), is substantially more involved and requires careful control on the discretization error.
In this result, we incorporate a parameter $\alpha$ that lets us interpolate between exponential tails and Gaussian tails as $\alpha$ varies from 0 0 to $1/2$. This parameter turns out to be crucial in choosing the step-size $\eta$, which is $\approx d^{-(\frac{1+\alpha}{2(1-\alpha)}\vee 1)}N^{-\frac{1+\alpha}{1-\alpha}}$, and the number of iterations required $\approx N^{\frac{2}{1-\alpha}}$, to obtain $\mathsf{KSD}$ bounds which are $O\left(d^{(\frac{3-\alpha}{4(1-\alpha)}\vee 1)}N^{-1/2}\right)$. Unlike the population limit discrete-time SVGD rates previously obtained in Korba et al. (); Salim et al. (), the Hilbert-Schmidt norm of the Jacobian of the transformation associated with each iteration depends non-trivially on the initial configuration and the number of iterations. A key technical ingredient in controlling this is an ‘a priori’ bound on the functional $n\mapsto N^{-1}\sum_{i}V(x^{N}_{i}(n))$ obtained in Lemma [3](#Thmlemma3).

In Section [4](#S4), we obtain *Wasserstein-2 convergence and associated rates*. For this purpose, we heavily rely on the treatise of Kanagawa et al. () which connects $\mathsf{KSD}$ convergence to Wasserstein convergence when the kernel has a bilinear component and a translation invariant component of the form $(x,y)\mapsto\Psi(x-y)$ (see ([13](#S4.E13))). Such kernels are typically unbounded, in contrast with standard boundedness assumptions in most papers on SVGD (a notable exception is Liu et al. ()). In Theorem [4](#Thmtheorem4), under dissipativity and growth assumptions on the potential $V$, we obtain polynomial $\mathsf{KSD}$ convergence rates for SVGD finite-particle dynamics with such kernels, which by Kanagawa et al. () imply Wasserstein convergence. When the translation invariant part of the kernel is of Matérn type, we obtain Wasserstein convergence rates in Theorem [5](#Thmtheorem5) of the form $O(1/N^{\alpha/d})$ (where $\alpha>0$ does not depend on $d$) for the particle SVGD using Theorem [4](#Thmtheorem4) in conjunction with results in Kanagawa et al. (). This is the first work on Wasserstein convergence for non-Gaussian SVGD finite-particle dynamics. Unlike the $\mathsf{KSD}$ bound, the $d$ dependence leads to *curse-of-dimensionality* in the Wasserstein bound, but this is to be expected when compared to Wasserstein bounds for empirical distribution of i.i.d. random variables (Dudley, ; Weed and Bach, ). Finally, we obtain a *long-time propagation of chaos* result in Proposition [1](#Thmproposition1), namely, we show that the time-averaged marginals of the particle locations over the time interval $[0,N]$, started from an exchangeable initial configuration, become asymptotically independent as $N\to\infty$ and essentially produce i.i.d samples from $\pi$. Although the results in Sections [4](#S4) and [5](#S5) are proved for the continuous-time SVGD in ([2](#S1.E2)) to highlight the main ideas, analogous results can also be proved in discrete-time and is deferred to future work.

Notation: Throughout the article, we will often suppress the superscript $N$ for various objects when it is clear from context. Furthermore, underlined vectors (e.g., $\underline{x}$) denote objects in $\left(\mathbb{R}^{d}\right)^{N}$.

## 2. Continuous-time Finite-Particle Convergence Rates in KSD Metric

We first provide rates in the $\mathsf{KSD}$ metric. Let $\mathcal{H}_{0}$ denote the reproducing kernel Hilbert space (RKHS) of real-valued functions associated with the positive definite kernel k (Aronszajn, ). Then $\mathcal{H}\coloneqq\mathcal{H}_{0}\times\dots\times\mathcal{H}_{0}$ inherits a natural RKHS structure comprising $\mathbb{R}^{d}$-valued functions. The *Langevin-Stein operator* (Gorham and Mackey, ) $\mathcal{T}_{\pi}$, associated with $\pi\propto e^{-V}$, acts on differentiable functions $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ by

$$ $\mathcal{T}_{\pi}\phi(x)\coloneqq-\nabla V(x)\cdot\phi(x)+\nabla\cdot\phi(x),\quad x\in\mathbb{R}^{d}.$ $$

The *Kernelized Stein Discrepancy*(^1^11See Barp et al. (, Section 2.2) for additional technical details regarding the well-definedness of $\mathsf{KSD}$.) ($\mathsf{KSD}$) (Chwialkowski et al., ; Gorham and Mackey, ), associated with the kernel k, of a probability measure $P$ on $\mathbb{R}^{d}$ with respect to $\pi$ is defined as

$$ $\mathsf{KSD}(P||\pi)\coloneqq\sup\{\mathbb{E}\left[\mathcal{T}_{\pi}\phi(X)\right]:\ X\sim P,\,\phi\in\mathcal{H},\|\phi\|_{\mathcal{H}}\leq 1\}.$ (4) $$

The definition of $\mathsf{KSD}$ is motivated by *Stein’s identity* which says that, for any sufficiently regular $\phi$, $\mathbb{E}_{X\sim\pi}\left[\mathcal{T}_{\pi}\phi(X)\right]=0$ and thus, the above measures the ‘distance’ of $P$ from $\pi$ via the maximum discrepancy of this expectation from 0 0 when $X\sim P$, as $\phi$ varies over $\mathcal{H}$.

The appeal of $\mathsf{KSD}$ lies in the fact that, unlike most distances on the space of probability measures, $\mathsf{KSD}$ has an explicit tractable expression. The function $\phi^{*}\in\mathcal{H}$ for which the above supremum is attained has a closed form expression $\phi^{*}(x)\propto\mathbb{E}_{Y\sim P}\left[-\textsf{k}(Y,x)\nabla V(Y)+\nabla_{1}\textsf{k}(Y,x)\right]$. Using this, we get the following expression for $\mathsf{KSD}$:

$$ $\displaystyle\mathsf{KSD}^{2}(P||\pi)$ $\displaystyle=\mathbb{E}_{(X,Y)\sim P\otimes P}\left[\nabla V(X)\cdot(\textsf{k}(X,Y)\nabla V(Y))-\nabla V(X)\cdot\nabla_{2}\textsf{k}(X,Y)\right.$ $\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.-\nabla V(Y)\cdot\nabla_{1}\textsf{k}(X,Y)+\nabla_{1}\cdot\nabla_{2}\textsf{k}(X,Y)\right].$ (5) $$

Before proceeding, we introduce the following regularity conditions, and state an existence and regularity result (proved in Appendix [A](#A1)) for the joint particle density.

###### Assumption 1 .

We make the following regularity assumptions.

- (a)
The maps $(x,y)\mapsto\textsf{k}(x,y)$ and $x\mapsto V(x)$ are $\mathcal{C}^{3}$.
- (b)
$\underline{x}^{N}(0)=(x^{N}_{1}(0),\dots,x^{N}_{N}(0))$ has a $C^{1}$ density $p^{N}_{0}$.

###### Lemma 1 .

Consider the SVGD dynamics ([2](#S1.E2)) under Assumption [1](#Thmassumption1). Then the particle locations $(x_{1}(t),\dots,x_{N}(t))$ have a joint density $p^{N}(t,\cdot)$ for every $t\geq 0$, and the map $(t,\underline{z})\mapsto p^{N}(t,\underline{z})$ is $\mathcal{C}^{2}$.

Denote the KL-divergence as

$$ $\displaystyle\mathsf{KL}(p^{N}(t)||\pi^{\otimes N})\coloneqq\int\log\left(\frac{p^{N}(t,\underline{z})}{\pi^{\otimes N}(\underline{z})}\right)p^{N}(t,\underline{z})\mathsf{d}\underline{z}.$ (6) $$

The following theorem furnishes the key bound on the $\mathsf{KSD}$ between the empirical law

$$ $\mu^{N}(t)\coloneqq\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}(t)},\,\qquad t\geq 0,$ $$

and the target distribution $\pi$. Define

$$ $C^{*}(z)\coloneqq\nabla_{2}\textsf{k}(z,z)\cdot\nabla V(z)+\textsf{k}(z,z)\Delta V(z)-\Delta_{2}\textsf{k}(z,z),\quad z\in\mathbb{R}^{d}.$ (7) $$

In the above, $\nabla_{2}\textsf{k}(z,z)\coloneqq\nabla_{2}\textsf{k}(z,\cdot)(z)$ and $\Delta_{2}\textsf{k}(z,z)\coloneqq\Delta_{2}\textsf{k}(z,\cdot)(z)$.

###### Theorem 1 .

Let Assumption [1](#Thmassumption1) hold. Then, we have for every $T>0$,

$$ $\displaystyle\frac{1}{T}\int_{0}^{T}\mathbb{E}[\mathsf{KSD}^{2}(\mu^{N}(t)||\pi)]\mathsf{d}t\leq\frac{\mathsf{KL}(p^{N}(0)||\pi^{\otimes N})}{NT}+\frac{1}{N^{2}T}\int_{0}^{T}\mathbb{E}\left[\sum_{k=1}^{N}C^{*}\left(x_{k}(t)\right)\right]\mathsf{d}t,$ $$

where the expectation is with respect to $p(t)$. In addition, we have that

$$ $\displaystyle\mathsf{KL}(p^{N}(T)||\pi^{\otimes N})\leq\mathsf{KL}(p^{N}(0)||\pi^{\otimes N})+\frac{1}{N}\int_{0}^{T}\mathbb{E}\left[\sum_{k=1}^{N}C^{*}\left(x_{k}(t)\right)\right]\mathsf{d}t.$ $$

Moreover, if $C^{*}\coloneqq\sup_{z\in\mathbb{R}^{d}}C^{*}(z)<\infty$ and $\underset{N\to\infty}{\limsup}~{}\mathsf{KL}(p^{N}(0)||\pi^{\otimes N})/N<\infty$, then

$$ $\displaystyle(\mathbb{E}[\mathsf{KSD}(\mu_{av}^{N}||\pi)])^{2}\leq\frac{1}{N}\int_{0}^{N}\mathbb{E}[\mathsf{KSD}^{2}(\mu^{N}(t)||\pi)]\mathsf{d}t\leq\frac{\sup_{L}\frac{\mathsf{KL}(p^{L}(0)||\pi^{\otimes L})}{L}+C^{*}}{N},$ (8) $$

where $\mu_{av}^{N}(\mathsf{d}x)\coloneqq\frac{1}{N}\int_{0}^{N}\mu^{N}(t,\mathsf{d}x)\mathsf{d}t$.

###### Remark 1 .

The condition $C^{*}<\infty$ holds, for example, when $\textsf{k}(u,v)=\Psi(u-v)$ for a positive-definite $\mathcal{C}^{3}$ function $\Psi:\mathbb{R}^{d}\to\mathbb{R}$ (Bochner, ), and $\sup_{x\in\mathbb{R}^{d}}\Delta V(x)<\infty$. Examples of such kernels include the radial basis kernel (e.g., Gaussian) and a wide class of Matérn kernels. The condition on the potential allows for a large class of non-log-concave densities as well.

###### Remark 2 (Optimality and dimension dependence) .

According to Sriperumbudur (); Hagrass et al. (), we have under mild regularity conditions, that the empirical measure $P_{N}\coloneqq\frac{1}{N}\sum_{i=1}^{N}\delta_{X_{i}}$, where $X_{i}\sim P$, i.i.d., satisfies $\mathbb{E}[\mathsf{KSD}(P_{N}||P)]=O(1/\sqrt{N})$. This points to the fact that our rates in Theorem [1](#Thmtheorem1) are presumably optimal with respect to $N$. While there is no curse-of-dimensionality in the $\mathsf{KSD}$ rates, the dimension factor appears in the numerator of the bound ([8](#S2.E8)). When $\textsf{k}(u,v)=\Psi(u-v)$ as in Remark [1](#Thmremark1) with $\sup_{x\in\mathbb{R}^{d}}\Delta V(x)\leq Cd$ for some dimension independent constant $C$, it can be checked that $C^{*}\leq\Psi(0)Cd-\Delta\Psi(0)$, which gives a linear in $d$ upper bound on $C^{*}$ for a wide range of kernels (including the Gaussian kernel) and potentials. Moreover, as long as mild regularity conditions are assumed about the kernel and the potential function, then according to Vempala and Wibisono (, Lemma 1), the initialization dependent term could be taken to be linear in $d$ when $V$ has Lipschitz gradients. These combine to give an $O(d/\sqrt{N})$ bound on the $\mathsf{KSD}$.

###### Proof of Theorem 1 .

We will abbreviate $\mathsf{H}(t)\coloneqq\mathsf{KL}(p^{N}(t)||\pi^{\otimes N})$. Using the particle dynamics equation ([2](#S1.E2)) and integration by parts, it is easy to verify that $p(t,\underline{z})$ is a weak solution of the following $N$-body Liouville equation (see, for example, Golse et al. (, Pg. 7) and Ambrosio et al. (, Chapter 8)) given by

$$ $\displaystyle\partial_{t}p(t,\underline{z})+\frac{1}{N}\sum_{k,\ell=1}^{N}\text{div}_{z_{k}}(p(t,\underline{z})\Phi(z_{k},z_{\ell}))=0,$ $$

where $\Phi(z,w)\coloneqq-\textsf{k}(z,w)\nabla V(w)+\nabla_{2}\textsf{k}(z,w)$. Recalling ([6](#S2.E6)), and using the density regularity obtained in Lemma [1](#Thmlemma1), we have that

$$ $\displaystyle\mathsf{H}^{\prime}(t)$ $\displaystyle=\int\partial_{t}p(t,\underline{z})\mathsf{d}\underline{z}+\int\log\left(\frac{p(t,\underline{z})}{\pi^{\otimes N}(\underline{z})}\right)\partial_{t}p(t,\underline{z})\mathsf{d}\underline{z}$ $\displaystyle=-\int\frac{1}{N}\sum_{k,\ell}\log\left(\frac{p(t,\underline{z})}{\pi^{\otimes N}(\underline{z})}\right)\text{div}_{z_{k}}(p(t,\underline{z})\Phi(z_{k},z_{\ell}))\mathsf{d}\underline{z}$ $\displaystyle=\frac{1}{N}\sum_{k,\ell}\int\nabla_{z_{k}}\log\left(\frac{p(t,\underline{z})}{\pi^{\otimes N}(\underline{z})}\right)\cdot(p(t,\underline{z})\Phi(z_{k},z_{\ell}))\mathsf{d}\underline{z}$ $\displaystyle=\frac{1}{N}\sum_{k,\ell}\int\nabla_{z_{k}}p(t,\underline{z})\cdot\Phi(z_{k},z_{\ell})\mathsf{d}\underline{z}+\frac{1}{N}\sum_{k,\ell}\int\nabla V(z_{k})\cdot\Phi(z_{k},z_{\ell})p(t,\underline{z})\mathsf{d}\underline{z}$ $\displaystyle=\frac{1}{N}\sum_{k,\ell}\int\left(-\text{div}_{z_{k}}\Phi(z_{k},z_{\ell})+\nabla V(z_{k})\cdot\Phi(z_{k},z_{\ell})\right)p(t,\underline{z})\mathsf{d}\underline{z}.$ $$

Now, observe that

$$ $\displaystyle-\text{div}_{z_{k}}\Phi(z_{k},z_{\ell})$ $\displaystyle=\text{div}_{z_{k}}(\textsf{k}(z_{k},z_{\ell})\nabla V(z_{\ell}))-\text{div}_{z_{k}}(\nabla_{2}\textsf{k}(z_{k},z_{\ell}))$ $\displaystyle=\nabla_{1}\textsf{k}(z_{k},z_{\ell})\cdot\nabla V(z_{\ell})-\nabla_{1}\cdot\nabla_{2}\textsf{k}(z_{k},z_{\ell})$ $\displaystyle\quad+(\nabla_{2}\textsf{k}(z_{k},z_{k})\cdot\nabla V(z_{k})+\textsf{k}(z_{k},z_{\ell})\Delta V(z_{k})-\Delta_{2}\textsf{k}(z_{k},z_{\ell}))\mathbbm{1}_{\{k=\ell\}}.$ $$

Similarly,

$$ $\displaystyle\nabla V(z_{k})\cdot\Phi(z_{k},z_{\ell})=-\nabla V(z_{k})\cdot(\textsf{k}(z_{k},z_{\ell})\nabla V(z_{\ell}))+\nabla V(z_{k})\cdot\nabla_{2}\textsf{k}(z_{k},z_{\ell}).$ $$

Therefore, using the explicit form of $\mathsf{KSD}$ in ([2](#S2.Ex5)), we have

$$ $\displaystyle\sum_{k,\ell}\left(-\text{div}_{z_{k}}\Phi(z_{k},z_{\ell})+\nabla V(z_{k})\cdot\Phi(z_{k},z_{\ell})\right)=-N^{2}\mathsf{KSD}^{2}(\mu(\underline{z})||\pi)+\sum_{k}C^{*}(z_{k}),$ $$

where $\mu(\underline{z})\coloneqq\frac{1}{N}\sum_{i=1}^{N}\delta_{z_{i}}$. Hence, we have

$$ $\displaystyle\mathsf{H}^{\prime}(t)$ $\displaystyle=-N\int\mathsf{KSD}^{2}(\mu(\underline{z})||\pi)p(t,\underline{z})\mathsf{d}\underline{z}+\frac{1}{N}\mathbb{E}\left[\sum_{k}C^{*}\left(x_{k}(t)\right)\right]$ $\displaystyle=-N\mathbb{E}[\mathsf{KSD}^{2}(\mu^{N}(t)||\pi)]+\frac{1}{N}\mathbb{E}\left[\sum_{k}C^{*}\left(x_{k}(t)\right)\right],$ (9) $$

where we recall that $\mu^{N}(t)=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}(t)}$ is the empirical measure. Hence, we have

$$ $\displaystyle\frac{1}{T}\int_{0}^{T}\mathbb{E}[\mathsf{KSD}^{2}(\mu^{N}(t)||\pi)]\mathsf{d}t\leq\frac{\mathsf{H}(0)}{NT}+\frac{1}{N^{2}T}\int_{0}^{T}\mathbb{E}\left[\sum_{k}C^{*}\left(x_{k}(t)\right)\right]\mathsf{d}t,$ $$

which completes the first claim. The entropy bound follows from ([2](#S2.Ex20)).

To prove the final claim, recall
$\mu^{N}_{av}(\mathsf{d}x)\coloneqq\frac{1}{N}\int_{0}^{N}\mu^{N}(t,\mathsf{d}x)\mathsf{d}t$
and note that the map $Q\mapsto\mathsf{KSD}(Q||\pi)$ is convex, which follows immediately from the representation of $\mathsf{KSD}$ given in ([4](#S2.E4)). From this and repeated applications of Jensen’s inequality, we obtain

$$ $\displaystyle\mathbb{E}[\mathsf{KSD}(\mu^{N}_{av}||\pi)]$ $\displaystyle\leq\frac{1}{N}\int_{0}^{N}\mathbb{E}[\mathsf{KSD}(\mu^{N}(t)||\pi)]\mathsf{d}t$ $\displaystyle\leq\frac{1}{N}\int_{0}^{N}\sqrt{\mathbb{E}[\mathsf{KSD}^{2}(\mu^{N}(t)||\pi)]}\mathsf{d}t$ $\displaystyle\leq\left(\frac{1}{N}\int_{0}^{N}\mathbb{E}[\mathsf{KSD}^{2}(\mu^{N}(t)||\pi)]\mathsf{d}t\right)^{1/2}$ $\displaystyle\leq\frac{\left(\sup_{L}\frac{\mathsf{H}(0)}{L}+C^{*}\right)^{\frac{1}{2}}}{\sqrt{N}}.$ $$

This completes the proof of the theorem.
∎

###### Assumption 1 .

###### Lemma 1 .

###### Theorem 1 .

###### Remark 1 .

###### Remark 2 (Optimality and dimension dependence) .

###### Proof of Theorem 1 .

### 2.1. Marginal convergence.

We now address the convergence in law of the time-averaged marginals when the initial particle locations are drawn from an exchangeable law.

###### Theorem 2 .

Suppose Assumption [1](#Thmassumption1) holds, $C^{*}<\infty$ and let $\textsf{k}(u,v)=\Psi(x-y)$, where $\Psi$ is a $\mathcal{C}^{3}$ function with non-vanishing generalized Fourier transform. Suppose also that the law $p_{0}$ of the initial particle locations $(x_{1}(0),\ldots,x_{N}(0))$ is exchangeable for each $N\in\mathbb{N}$ and $\underset{N\to\infty}{\limsup}\frac{1}{N}\mathsf{KL}(p^{N}(0)||\pi^{\otimes N})<\infty$. Define

$$ $\bar{\mu}^{N}(\mathsf{d}x)\coloneqq\frac{1}{N}\int_{0}^{N}\mathbb{P}(x_{1}(t)\in\mathsf{d}x)\mathsf{d}t.$ $$

Then, $\bar{\mu}^{N}\to\pi$, weakly.

###### Proof of Theorem 2 .

We will first show tightness of $\{\bar{\mu}^{N}\}_{N}$. By subadditivity of relative entropy (which follows from Budhiraja and Dupuis (, Lemma 2.4(b) and Theorem 2.6)), we have

$$ $\displaystyle\mathsf{KL}(\mathcal{L}(x_{1}(t))||\pi)\leq\frac{1}{N}\mathsf{KL}(p(t)||\pi^{\otimes N})\leq\frac{\mathsf{KL}(p(0)||\pi^{\otimes N})}{N}+\frac{C^{*}t}{N}.$ $$

Hence, there exists $C>0$ such that $\mathsf{KL}(\mathcal{L}(x_{1}(t))||\pi)\leq C$ for all $t\in[0,N]$, $\forall N\geq 1$. Fix any $\epsilon>0$. Let $\delta>0$ such that $\delta C<\epsilon/2$.
Let $K$ be a compact subset of $\mathbb{R}^{d}$ such that $\delta\log(1+\pi(K^{c})(e^{1/\delta}-1))\leq\epsilon/2$.
By the variational representation of relative entropy (Budhiraja and Dupuis, , Prop. 2.3) and Theorem [1](#Thmtheorem1), we have

$$ $\displaystyle\mathbb{P}(x_{1}(t)\notin K)$ $\displaystyle\leq\delta\left[\log\left(\int e^{\frac{1}{\delta}\mathbbm{1}_{K^{c}}(z)}\pi(\mathsf{d}z)\right)+\mathsf{KL}(\mathcal{L}(x_{1}(t))||\pi)\right]$ $\displaystyle\leq\delta\log(1+\pi(K^{c})(e^{1/\delta}-1))+\delta C<\epsilon$ $$

for all $t\in[0,N]$, $\forall N\geq 1$. In particular, $\{\bar{\mu}^{N}\}_{N}$ is tight. Moreover, we have

$$ $\displaystyle\mathsf{KSD}(\bar{\mu}^{N}||\pi)$ $\displaystyle=\mathsf{KSD}\left(\frac{1}{N}\int_{0}^{N}\mathcal{L}(x_{1}(t))\mathsf{d}t||\pi\right)$ $\displaystyle\leq\frac{1}{N}\int_{0}^{N}\mathsf{KSD}(\mathcal{L}(x_{1}(t))||\pi)\mathsf{d}t\qquad\text{\emph{by the convexity of $\mathsf{KSD}$}}$ $\displaystyle=\frac{1}{N}\int_{0}^{N}\mathsf{KSD}(\mathbb{E}[\mu^{N}(t)]||\pi)\ \ \text{\emph{using exchangeability, where}}\ \mathbb{E}[\mu^{N}(t)](\mathsf{d}x)\coloneqq\mathbb{E}[\mu^{N}(t,\mathsf{d}x)]$ $\displaystyle\leq\frac{1}{N}\int_{0}^{N}\mathbb{E}[\mathsf{KSD}(\mu^{N}(t)]||\pi)]\mathsf{d}t\to 0\qquad\text{\emph{by $\mathsf{KSD}$ convexity and Theorem~{}\ref{thm:KSDrates}}}.$ $$

The result now follows from Gorham and Mackey (, Theorem 7).
∎

###### Theorem 2 .

###### Proof of Theorem 2 .

## 3. Discrete-time Finite-Particle Rates in 𝖪𝖲𝖣 𝖪𝖲𝖣 \mathsf{KSD} metric

In this section, we obtain $\mathsf{KSD}$ rates for the discrete-time SVGD dynamics given by ([1](#S1.E1)). The dynamics can be succinctly represented as

$$ $\displaystyle\underline{x}(n+1)=\underline{x}(n)-\eta\mathbf{T}(\underline{x}(n)),\ n\in\mathbb{N}_{0},$ $$

where $\eta$ is the step-size and $\mathbf{T}=(\mathsf{T}_{1},\ldots,\mathsf{T}_{N})^{\prime}$ with $\mathsf{T}_{i}(\underline{x})=\frac{1}{N}\sum_{j}\left[\textsf{k}(x_{i},x_{j})\nabla V(x_{j})-\nabla_{2}\textsf{k}(x_{i},x_{j})\right]$. In this section, we use $T$ to denote the number of iterations.

Although the idea is once again to track the evolution of the relative entropy of the joint density of particle locations with respect to $\pi^{\otimes N}$, one needs a careful quantification of the discretization error to obtain an equation similar to ([2](#S2.Ex20)).
We will make the following assumptions. All constants appearing in the section will be independent of $d,N$.

###### Assumption 2 .

We make the following regularity assumptions.

- (a)
*Boundedness*: k and all its partial derivatives up to order $2$ are uniformly bounded by $B\in(0,\infty)$.
- (b)
*Growth*: $\inf_{z\in\mathbb{R}^{d}}V(z)>0$ and, for some $A>0$, $\alpha\in[0,1/2]$, $\|\nabla V(x)\|\leq AV(x)^{\alpha}$ for all $x\in\mathbb{R}^{d}$.
- (c)
*Bounded Hessian*: $\sup_{z\in\mathbb{R}^{d}}\|H_{V}(z)\|_{op}=C_{V}<\infty,$ where $H_{V}$ denotes the Hessian of $V$ and $\|\cdot\|_{op}$ denotes the operator norm.
- (d)
Recalling ([7](#S2.E7)), we assume that $\sup_{z\in\mathbb{R}^{d}}\nabla_{2}\textsf{k}(z,z)\cdot\nabla V(z)+\textsf{k}(z,z)\Delta V(z)-\Delta_{2}\textsf{k}(z,z)=c^{*}d$ for some constant $c^{*}>0$.
- (e)
Initial entropy bound: $\mathsf{KL}(p(0)||\pi^{\otimes N})\leq C_{KL}Nd$ for some constant $C_{KL}>0$.

###### Remark 3 .

Conditions (a) and (c) are essentially motivated by the work of Korba et al. (), who in turn are motivated by standard assumptions made in the stochastic optimization literature. The condition (b) in Assumption [2](#Thmassumption2) captures the growth rate of the potential $V$ which plays a crucial role in the step-size selection and number of iterations required (see ([10](#S3.E10)) below) to obtain the convergence rate in Theorem [3](#Thmtheorem3). As $\alpha$ approaches 0 0, $\pi$ approaches the exponential distribution and as $\alpha$ approaches $1/2$, $\pi$ is close to a Gaussian (in tail behavior). Conditions (d) and (e) are explicit refinements of similar conditions required in the continuous-time analysis.

###### Theorem 3 .

Suppose Assumption [2](#Thmassumption2) holds. Let the initial locations $(x_{1}(0),\ldots,x_{N}(0))$ be sampled from

$$ $p_{K}(0)\coloneqq p(0)|\mathcal{S}_{K}\quad\text{where}\quad\mathcal{S}_{K}\coloneqq\Big{\{}\underline{x}\in\left(\mathbb{R}^{d}\right)^{N}:N^{-1}\sum_{i}V(x_{i})\leq K\Big{\}},$ $$

for some $K>0$ satisfying $\int_{\mathcal{S}_{K}}p(0,\underline{z})\mathsf{d}\underline{z}\geq 1/2$, where $p(0)|\mathcal{S}_{K}$ represents the restriction of the density to the set $\mathcal{S}_{K}$. Then there exist positive constants $a,b$ depending only on the constants appearing in Assumption [2](#Thmassumption2) such that with

$$ $\displaystyle\eta=\frac{a}{d^{\frac{1+\alpha}{2(1-\alpha)}}+\sqrt{d}K^{\alpha}+d}N^{-\frac{1+\alpha}{1-\alpha}},\qquad T=\lceil N^{\frac{2}{1-\alpha}}\rceil,$ (10) $$

we have

$$ $\mathbb{E}_{p_{K}(0)}\left[\frac{1}{T}\sum_{n=0}^{T-1}\mathsf{KSD}^{2}\left(\mu^{N}_{n}||\pi\right)\right]\leq\frac{bd\left(d^{\frac{1+\alpha}{2(1-\alpha)}}+\sqrt{d}K^{\alpha}+d\right)}{N}.$ $$

In particular, if $(x_{1}(0),\ldots,x_{N}(0))$ is sampled from $p(0)$, then for any $\epsilon>0$,

$$ $\mathbb{P}\left(\frac{1}{T}\sum_{n=0}^{T-1}\mathsf{KSD}^{2}\left(\mu^{N}_{n}||\pi\right)>\frac{bd\left(d^{\frac{1+\alpha}{2(1-\alpha)}}+\sqrt{d}K^{\alpha}+d\right)}{N\epsilon}\right)\leq\epsilon+\int_{\mathcal{S}_{K}^{c}}p(0,\underline{z})\mathsf{d}\underline{z}.$ $$

###### Remark 4 .

The proof of Theorem [3](#Thmtheorem3) involves an ‘interpolation’ in the spirit of Korba et al. () between the laws of $\underline{x}(n)$ and $\underline{x}(n+1)$ which leads to a Taylor expansion of the relative entropy. The main subtlety in the analysis when dealing with the joint law evolution here comes from the fact that, unlike for the population limit SVGD, the Hilbert-Schmidt norm of the Jacobian of the map $\mathbf{T}(\underline{x})$ at $\underline{x}=\underline{x}(n)$ is not uniformly bounded in $n$ and $\underline{x}(0)$. This requires refined ‘a priori’ bounds on the rate of growth of the path functional $n\mapsto\frac{1}{N}\sum_{i}V(x_{i}(n))$ (see Lemma [3](#Thmlemma3)). As a result, for initial locations in $\mathcal{S}_{K}$ one can fine tune the step-size depending on $N,d,K$ such that the second order term in the Taylor expansion becomes small in comparison to the first term. Moreover, the first order term is shown to have the same form as the continuous-time derivative of the joint relative entropy obtained in the proof of Theorem [1](#Thmtheorem1). This leads to the results in Theorem [3](#Thmtheorem3).

Marginal convergence results, similar to Theorem [2](#Thmtheorem2), in the discrete-time setting can also be deduced from the entropy bounds involved in proving Theorem [3](#Thmtheorem3).

The proof of Theorem [3](#Thmtheorem3) proceeds through the following lemmas. We will assume throughout that Assumption [2](#Thmassumption2) holds.

###### Lemma 2 .

$\|\mathbf{T}(\underline{x})\|^{2}\leq 2A^{2}B^{2}N\left(\frac{1}{N}\sum_{i}V(x_{i})\right)^{2\alpha}+2NB^{2}d,\quad\underline{x}\in\left(\mathbb{R}^{d}\right)^{N}$.

###### Proof of Lemma 2 .

Observe that

$$ $\displaystyle\|\mathbf{T}(\underline{x})\|^{2}$ $\displaystyle=\frac{1}{N^{2}}\sum_{i}\|\sum_{j}(\textsf{k}(x_{i},x_{j})\nabla V(x_{j})-\nabla_{2}\textsf{k}(x_{i},x_{j})\|^{2}$ $\displaystyle\leq\frac{2}{N}\sum_{i,j}\left(\textsf{k}^{2}(x_{i},x_{j})\|\nabla V(x_{j})\|^{2}+\|\nabla_{2}\textsf{k}(x_{i},x_{j})\|^{2}\right)$ $\displaystyle\leq 2A^{2}B^{2}N\left(\frac{1}{N}\sum_{j}V(x_{j})^{2\alpha}\right)+2NB^{2}d$ $\displaystyle\leq 2A^{2}B^{2}N\left(\frac{1}{N}\sum_{j}V(x_{j})\right)^{2\alpha}+2NB^{2}d,$ $$

where the last step follows by Jensen’s inequality noting $\alpha\leq 1/2$.
∎

The following lemma gives a key ‘a priori’ bound on the growth rate of $N^{-1}\sum_{i}V(x_{i}(n))$ in terms of $n$ and $\eta$ and is crucial to the rest of the proof.

###### Lemma 3 .

There exist positive constants $M,D$ depending only on the constants appearing in Assumption [2](#Thmassumption2) such that for $T\geq 1$, $0\leq n\leq T$, $\eta\leq 1\wedge\frac{1}{\sqrt{DT}}$,

$$ $\frac{1}{N}\sum_{i}V(x_{i}(n))\leq M\left(d^{\frac{1}{1-\alpha}}+\frac{1}{N}\sum_{i}V(x_{i}(0))\right)\left[\left(\eta n\right)^{\frac{1}{1-\alpha}}\vee 1\right].$ $$

###### Proof of Lemma 3 .

Note that, using Taylor’s theorem,

$$ $\displaystyle\quad\frac{1}{N}\sum_{i}V(x_{i}(n+1))-\frac{1}{N}\sum_{i}V(x_{i}(n))=\frac{1}{N}\sum_{i}\langle\nabla V(x_{i}(n)),x_{i}(n+1)-x_{i}(n)\rangle$ $\displaystyle\quad+\frac{1}{N}\sum_{i}\int_{0}^{1}(1-s)\langle x_{i}(n+1)-x_{i}(n),H_{V}(x_{i}(n)-s\eta\mathsf{T}_{i}(\underline{x}(n)))(x_{i}(n+1)-x_{i}(n))\rangle ds$ $\displaystyle\leq\frac{1}{N}\sum_{i}\langle\nabla V(x_{i}(n)),x_{i}(n+1)-x_{i}(n)\rangle+\frac{C_{V}\eta^{2}}{2N}\|\mathbf{T}(\underline{x}(n))\|^{2}.$ $$

Now, applying Lemma [2](#Thmlemma2) in the above and writing $D_{1}=A^{2}B^{2}C_{V}$ and $D_{2}=B^{2}C_{V}$, we obtain

$$ $\displaystyle\quad\frac{1}{N}\sum_{i}V(x_{i}(n+1))-\frac{1}{N}\sum_{i}V(x_{i}(n))$ $\displaystyle\leq\frac{1}{N}\sum_{i}\langle\nabla V(x_{i}(n)),x_{i}(n+1)-x_{i}(n)\rangle+D_{1}\eta^{2}\left(\frac{1}{N}\sum_{j}V(x_{j}(n))\right)^{2\alpha}+D_{2}d\eta^{2}$ $\displaystyle=-\frac{\eta}{N^{2}}\sum_{i,j}\langle\nabla V(x_{i}(n)),\textsf{k}(x_{i}(n),x_{j}(n))\nabla V(x_{j}(n))\rangle+\frac{\eta}{N^{2}}\sum_{i,j}\langle\nabla V(x_{i}(n)),\nabla_{2}\textsf{k}(x_{i}(n),x_{j}(n))\rangle$ $\displaystyle\quad+D_{1}\eta^{2}\left(\frac{1}{N}\sum_{j}V(x_{j}(n))\right)^{2\alpha}+D_{2}d\eta^{2}$ $\displaystyle\leq\frac{\eta}{N^{2}}\sum_{i,j}\langle\nabla V(x_{i}(n)),\nabla_{2}\textsf{k}(x_{i}(n),x_{j}(n))\rangle+D_{1}\eta^{2}\left(\frac{1}{N}\sum_{j}V(x_{j}(n))\right)^{2\alpha}+D_{2}d\eta^{2},$ $$

where, in the last step, we used the positive-definiteness of k. Thus, suppressing the dependence on $n$ of the right hand side to avoid cumbersome notation, we obtain

$$ $\displaystyle\quad\frac{1}{N}\sum_{i}V(x_{i}(n+1))-\frac{1}{N}\sum_{i}V(x_{i}(n))$ $\displaystyle\leq\frac{B\sqrt{d}\eta}{N}\sum_{i}\|\nabla V(x_{i})\|+D_{1}\eta^{2}\left(\frac{1}{N}\sum_{j}V(x_{j})\right)^{2\alpha}+D_{2}d\eta^{2}$ $\displaystyle\leq AB\sqrt{d}\eta\left(\frac{1}{N}V(x_{i})\right)^{\alpha}+D_{1}\eta^{2}\left(\frac{1}{N}\sum_{j}V(x_{j})\right)^{2\alpha}+D_{2}d\eta^{2}.$ $$

Thus, writing $f(n)\coloneqq\frac{1}{N}V(x_{i}(n))$ and recalling $\alpha\leq 1/2$, we obtain

$$ $f(n+1)\leq(1+D_{1}\eta^{2})f(n)+AB\sqrt{d}\eta f(n)^{\alpha}+D_{3}d\eta^{2},$ (11) $$

where $D_{3}=D_{1}+D_{2}$. We will now harness the recursive bound ([11](#S3.E11)) to obtain the claimed bound in the lemma. First, we handle the case $0\leq n\leq\lceil 1/\eta\rceil$. Fix $L>0$. Define

$$ $\tau_{L}\coloneqq\sup\{n\geq 0:f(n)\leq L\}\wedge\lceil 1/\eta\rceil.$ $$

Then for $1\leq n\leq\tau_{L}$, ([11](#S3.E11)) gives for $\eta\leq 1$,

$$ $\displaystyle f(n)$ $\displaystyle\leq(1+D_{1}\eta^{2})f(n-1)+AB\sqrt{d}\eta L^{\alpha}+D_{3}d\eta^{2}$ $\displaystyle\leq\sum_{\ell=0}^{n-1}(1+D_{1}\eta^{2})^{\ell}(AB\sqrt{d}\eta L^{\alpha}+D_{3}d\eta^{2})+(1+D_{1}\eta^{2})^{n}f(0)$ $\displaystyle\leq\frac{2}{\eta}(1+D_{1}\eta^{2})^{1/\eta}(AB\sqrt{d}\eta L^{\alpha}+D_{3}d\eta^{2})+(1+D_{1}\eta^{2})^{1+1/\eta}f(0)$ $\displaystyle\leq 2e^{D_{1}}(AB\sqrt{d}L^{\alpha}+D_{3}d)+(1+D_{1})e^{D_{1}}f(0).$ $$

Hence, taking $L=\hat{M}\left(d+f(0)\right)$ for some suitably large $\hat{M}\geq 1$ depending only on the constants appearing in Assumption [2](#Thmassumption2), we conclude from the above bound that $f(\tau_{L})<L$ and hence $\tau_{L}=\lceil 1/\eta\rceil$. Thus,

$$ $f(n)\leq\hat{M}\left(d+f(0)\right)\quad\text{ for all }0\leq n\leq\lceil 1/\eta\rceil.$ $$

Now, we handle the case $1/\eta\leq n\leq T$. We will proceed by induction. Let

$$ $\displaystyle\beta\coloneqq M(d^{\frac{1}{1-\alpha}}+f(0)),\qquad\text{where}\qquad M=\hat{M}\vee[16(1-\alpha)^{2}(AB+D_{3})]^{\frac{1}{1-\alpha}}.$ $$

Take any $\eta\leq 1\wedge\frac{1}{4(1-\alpha)\sqrt{D_{1}T}}$. Then, by the above bound, note that for $n=\lceil 1/\eta\rceil$, $f(n)\leq\beta(n\eta)^{\frac{1}{1-\alpha}}$. Suppose for some $1/\eta\leq n\leq T$, $f(n)\leq\beta(n\eta)^{\frac{1}{1-\alpha}}$. Then, by ([11](#S3.E11)),

$$ $\displaystyle f(n+1)$ $\displaystyle\leq(1+D_{1}\eta^{2})\beta(n\eta)^{\frac{1}{1-\alpha}}+AB\sqrt{d}\eta\beta^{\alpha}(n\eta)^{\frac{\alpha}{1-\alpha}}+D_{3}d\eta^{2}$ $\displaystyle\leq\beta((n+1)\eta)^{\frac{1}{1-\alpha}}\left[(1+D_{1}\eta^{2})\left(\frac{n}{n+1}\right)^{\frac{1}{1-\alpha}}+\frac{AB\sqrt{d}}{\beta^{1-\alpha}n}+\frac{D_{3}d\eta^{\frac{1-2\alpha}{1-\alpha}}}{\beta n^{\frac{1}{1-\alpha}}}\right]$ $\displaystyle\leq\beta((n+1)\eta)^{\frac{1}{1-\alpha}}\left[(1+D_{1}\eta^{2})-\left\{\frac{1}{8(1-\alpha)^{2}n}-\frac{AB\sqrt{d}+D_{3}d}{\beta^{1-\alpha}n}\right\}\right]$ $\displaystyle\leq\beta((n+1)\eta)^{\frac{1}{1-\alpha}}\left[(1+D_{1}\eta^{2})-\left\{\frac{1}{8(1-\alpha)^{2}n}-\frac{AB\sqrt{d}+D_{3}d}{M^{1-\alpha}dn}\right\}\right]$ $\displaystyle\leq\beta((n+1)\eta)^{\frac{1}{1-\alpha}}\left[1+D_{1}\eta^{2}-\frac{1}{16(1-\alpha)^{2}n}\right]$ $\displaystyle\leq\beta((n+1)\eta)^{\frac{1}{1-\alpha}},$ $$

where the fifth inequality uses the choice of $M$ and the last inequality uses the bound on $\eta$. The claimed bound follows by induction.
∎

We will now use Lemma [3](#Thmlemma3) to obtain bounds on $\|\mathbf{T}(\underline{x}(n))\|^{2}$ and the Hilbert-Schmidt norm of the Jacobian matrix $J\mathbf{T}(\underline{x}(n))$.

###### Lemma 4 .

For $T\geq 1$, $0\leq n\leq T$, $\eta\leq 1\wedge\frac{1}{\sqrt{DT}}$, we have

$$ $\displaystyle\|\mathbf{T}(\underline{x}(n))\|^{2}$ $\displaystyle\leq 2A^{2}B^{2}N\left[M^{2\alpha}\left(d^{\frac{1}{1-\alpha}}+\frac{1}{N}\sum_{i}V(x_{i}(0))\right)^{2\alpha}\left[\left(\eta n\right)^{\frac{2\alpha}{1-\alpha}}\vee 1\right]\right]+2NB^{2}d,$ $\displaystyle\|J\mathbf{T}(\underline{x}(n))\|_{HS}^{2}$ $\displaystyle\leq 8A^{2}B^{2}d(N+2)\left[M^{2\alpha}\left(d^{\frac{1}{1-\alpha}}+\frac{1}{N}\sum_{i}V(x_{i}(0))\right)^{2\alpha}\left[\left(\eta n\right)^{\frac{2\alpha}{1-\alpha}}\vee 1\right]\right]$ $\displaystyle\quad+8B^{2}d^{2}(N+3)+8B^{2}dC_{V}^{2}.$ $$

###### Proof of Lemma 4 .

The first bound follows from Lemma [2](#Thmlemma2) and Lemma [3](#Thmlemma3). To prove the second bound, note that

$$ $\|J\mathbf{T}(\underline{x})\|_{HS}^{2}=\sum_{i,j=1}^{N}\sum_{k,l=1}^{d}\|\partial_{jl}\mathsf{T}_{ik}(\underline{x})\|^{2},$ $$

where for $v_{i}\in\mathbb{R}^{d}$, $v_{ik}$ denotes the $k$th coordinate of $v_{i}$ and $\partial_{jl}$ denotes the partial derivative with respect to $x_{jl}$. We will also write for $m=1,2,$ $\partial_{mk}\textsf{k}$ to denote the partial derivative of k with respect to the $k$th coordinate of the $m$th variable. Observe that,

$$ $\displaystyle\partial_{x_{jl}}\mathsf{T}_{ik}(\underline{x})$ $\displaystyle=\frac{1}{N}\sum_{u=1}^{N}\left(\partial_{1l}\textsf{k}(x_{i},x_{u})\partial_{k}V(x_{u})-\partial_{2k}\textsf{k}(x_{i},x_{u})\right)\mathbbm{1}(i=j)$ $\displaystyle\quad+\frac{1}{N}\left(\partial_{2l}\textsf{k}(x_{i},x_{j})\partial_{k}V(x_{j})-\partial_{2k}\textsf{k}(x_{i},x_{j})\right)$ $\displaystyle\quad+\frac{1}{N}\left(\textsf{k}(x_{i},x_{j})\partial_{lk}V(x_{j})-\partial_{2k}\textsf{k}(x_{i},x_{j})\right)$ $\displaystyle\quad+\frac{1}{N}\left(\textsf{k}(x_{i},x_{j})\partial_{k}V(x_{j})-\partial_{2l}\partial_{2k}\textsf{k}(x_{i},x_{j})\right).$ $$

Write $S_{m}(i,j)$ for the $m$th term in the above bound for $m=1,2,3,4$. In a similar manner as the proof of Lemma [2](#Thmlemma2),

$$ $\displaystyle\sum_{ijkl}|S_{1}(i,j)|^{2}$ $\displaystyle\leq\frac{1}{N}\sum_{iukl}\left(\partial_{1l}\textsf{k}(x_{i},x_{u})\partial_{k}V(x_{u})-\partial_{2k}\textsf{k}(x_{i},x_{u})\right)^{2}$ $\displaystyle=\frac{1}{N}\sum_{iul}\left\|\partial_{1l}\textsf{k}(x_{i},x_{u})\nabla V(x_{u})-\nabla_{2}\textsf{k}(x_{i},x_{u})\right\|^{2}$ $\displaystyle\leq 2A^{2}B^{2}dN\left(\frac{1}{N}\sum_{i}V(x_{i})\right)^{2\alpha}+2NB^{2}d^{2}.$ $$

Similarly,

$$ $\displaystyle\sum_{ijkl}|S_{2}(i,j)|^{2}$ $\displaystyle=\frac{1}{N^{2}}\sum_{ijkl}\left(\partial_{2l}\textsf{k}(x_{i},x_{j})\partial_{k}V(x_{j})-\partial_{2k}\textsf{k}(x_{i},x_{j})\right)^{2}$ $\displaystyle\leq\frac{2B^{2}}{N^{2}}\sum_{ij}(d\|\nabla V(x_{j})\|^{2}+d^{2})$ $\displaystyle\leq 2A^{2}B^{2}d\left(\frac{1}{N}\sum_{i}V(x_{i})\right)^{2\alpha}+2B^{2}d^{2}.$ $$

Moreover,

$$ $\displaystyle\sum_{ijkl}|S_{3}(i,j)|^{2}$ $\displaystyle\leq\frac{2B^{2}}{N^{2}}\sum_{ijkl}\left((\partial_{lk}V(x_{j}))^{2}+1\right)$ $\displaystyle\leq 2B^{2}\sup_{z\in\mathbb{R}^{d}}\|H_{V}(z)\|^{2}+2B^{2}d^{2}\leq 2B^{2}dC_{V}^{2}+2B^{2}d^{2}.$ $$

Finally,

$$ $\displaystyle\sum_{ijkl}|S_{4}(i,j)|^{2}$ $\displaystyle\leq\frac{2B^{2}}{N^{2}}\sum_{ijkl}\left((\partial_{k}V(x_{j}))^{2}+1\right)\leq 2A^{2}B^{2}d\left(\frac{1}{N}\sum_{i}V(x_{i})\right)^{2\alpha}+2B^{2}d^{2}.$ $$

Combining the above bounds, we obtain

$$ $\displaystyle\|J\mathbf{T}(\underline{x})\|_{HS}^{2}\leq 4\left[2A^{2}B^{2}d(N+2)\left(\frac{1}{N}\sum_{i}V(x_{i})\right)^{2\alpha}+2B^{2}d^{2}(N+3)+2B^{2}dC_{V}^{2}\right].$ $$

The claimed bound in the lemma now follows from the above and Lemma [3](#Thmlemma3).
∎

Now, we will complete the proof of Theorem [3](#Thmtheorem3).

###### Proof of Theorem 3 .

Fix $K>0$ as in the theorem and sample $(x_{1}(0),\ldots,x_{N}(0))$ from $p_{K}(0)$ supported on $\mathcal{S}_{K}$. Denote the law of $\underline{x}(n)$ by $p_{K}(n)$. As we will work with fixed $0\leq n\leq T$ for the first portion of the proof, we will suppress dependence on $n$. Set $\nu(0)=p_{K}(n)$ and $\nu(\eta)=p_{K}(n+1)$. Interpolate these laws by defining $\nu(t)\coloneqq{\phi_{t}}_{\#}p_{K}(n)$, $t\in[0,\eta]$, where $\phi_{t}(\underline{x})\coloneqq\underline{x}-t\mathbf{T}(\underline{x}),t\in[0,\eta]$. Write $S_{K}=(\operatorname{Id}-\eta\mathbf{T})^{n}\mathcal{S}_{K}$ and $S_{K,t}\coloneqq\phi_{t}(S_{K}),t\in[0,\eta]$.

Set the step-size $\eta$ as

$$ $\displaystyle\eta=\left[\frac{1}{C_{0}}\left(\frac{1}{N^{\frac{1-\alpha}{1+\alpha}}T^{\frac{2\alpha}{1+\alpha}}}\wedge\frac{1}{N}\right)\right]^{1/2}\theta,\quad\text{where}\quad\theta\in[0,1]$ $$

will be appropriately chosen later and $C_{0}\coloneqq 2[24A^{2}B^{2}dM^{2\alpha}(d^{\frac{1}{1-\alpha}}+K)^{2\alpha}+8B^{2}d(C_{V}^{2}+4d)]$. By Lemma [4](#Thmlemma4), this choice of $\eta$ ensures that for any $\underline{x}\in S_{K}$, $t\in[0,\eta]$,

$$ $\|tJ\mathbf{T}(\underline{x})\|_{op}\leq\eta\|J\mathbf{T}(\underline{x})\|_{HS}\leq\frac{\theta}{2}\leq\frac{1}{2}.$ $$

Thus, $J\phi_{t}(\underline{x})$ is invertible for any such $\underline{x},t$ and

$$ $\|(J\phi_{t}(\underline{x}))^{-1}\|_{op}\leq\sum_{k=0}^{\infty}\eta^{k}\|J\mathbf{T}(\underline{x})\|_{HS}^{k}\leq 2.$ $$

In particular, if $\nu(0)$ admits a density, then for any $t\in[0,\eta]$, $\nu(t)$ admits a density given by

$$ $q_{K}(t,\underline{x})=\left(\operatorname{det}(J\phi_{t}(\phi_{t}^{-1}(\underline{x})))\right)^{-1}p_{K}(n,\phi_{t}^{-1}(\underline{x})),\quad\underline{x}\in S_{K,t}$ $$

and $q_{K}(t,\underline{x})=0$ otherwise. Writing $E(t)\coloneqq\mathsf{KL}(q_{K}(t)||\pi^{\otimes N})$, we obtain the following Taylor expansion on the interval $[0,\eta]$ along the lines of Korba et al. ():

$$ $E(\eta)=E(0)+\eta E^{\prime}(0)+\int_{0}^{\eta}(\eta-t)E^{\prime\prime}(t)\mathsf{d}t.$ (12) $$

clearly, $E(0)=\mathsf{KL}(p_{K}(n)||\pi^{\otimes N})$ and $E(\eta)=\mathsf{KL}(p_{K}(n+1)||\pi^{\otimes N})$. Moreover, by computations similar to Korba et al. (), writing $\hat{\nabla}V(\underline{x})=(\nabla V(x_{1}),\ldots,\nabla V(x_{N}))^{\prime}$, we obtain for $t\in[0,\eta]$,

$$ $\displaystyle E^{\prime}(t)$ $\displaystyle=-\int\operatorname{tr}\left((J\phi_{t}(\underline{x}))^{-1}\partial_{t}J\phi_{t}(\underline{x})\right)p_{K}(n,\underline{x})\mathsf{d}\underline{x}+\int\langle\hat{\nabla}V(\phi_{t}(\underline{x})),\partial_{t}\phi_{t}(\underline{x})\rangle p_{K}(n,\underline{x})\mathsf{d}\underline{x}$ $\displaystyle=\int\operatorname{tr}\left((J\phi_{t}(\underline{x}))^{-1}J\mathbf{T}(\underline{x})\right)p_{K}(n,\underline{x})\mathsf{d}\underline{x}-\int\langle\hat{\nabla}V(\phi_{t}(\underline{x})),\mathbf{T}(\underline{x})\rangle p_{K}(n,\underline{x})\mathsf{d}\underline{x}.$ $$

In particular, recalling $\Phi(z,w)\coloneqq-\textsf{k}(z,w)\nabla V(w)+\nabla_{2}\textsf{k}(z,w)$,

$$ $\displaystyle E^{\prime}(0)$ $\displaystyle=\int\left(\text{div}(\mathbf{T}(\underline{x}))-\langle\hat{\nabla}V(\underline{x}),\mathbf{T}(\underline{x})\rangle\right)p_{K}(n,\underline{x})\mathsf{d}\underline{x}$ $\displaystyle=\int\left(-\frac{1}{N}\sum_{i,j}\text{div}_{x_{i}}\Phi(x_{i},x_{j})+\frac{1}{N}\sum_{i,j}\nabla V(x_{i})\Phi(x_{i},x_{j})\right)p_{K}(n,\underline{x})\mathsf{d}\underline{x}$ $\displaystyle\leq-N\mathbb{E}_{p_{K}(0)}\left[\mathsf{KSD}^{2}(\mu^{N}_{n}||\pi)\right]+c^{*}d$ $$

along the same lines as the proof of Theorem [1](#Thmtheorem1). Moreover, note that for $t\in[0,\eta]$,

$$ $E^{\prime\prime}(t)=\psi_{1}(t)+\psi_{2}(t)$ $$

where, using Lemma [4](#Thmlemma4) and our choice of step-size $\eta$,

$$ $\psi_{1}(t)=\mathbb{E}_{\underline{x}\sim p_{K}(n)}\left[\langle\mathbf{T}(\underline{x}),H_{V}(\phi_{t}(\underline{x}))\mathbf{T}(\underline{x})\rangle\right]\leq C_{V}\sup_{\underline{x}\in S_{K}}\|\mathbf{T}(\underline{x})\|^{2}\leq\frac{\theta^{2}}{4\eta^{2}},$ $$

and

$$ $\displaystyle\psi_{2}(t)$ $\displaystyle=\int\|J\mathbf{T}(\underline{x})(J\phi_{t}(\underline{x}))^{-1}\|_{HS}^{2}\,p_{K}(n,\underline{x})\mathsf{d}\underline{x}$ $\displaystyle\leq\sup_{\underline{x}\in S_{K}}\|J\mathbf{T}(\underline{x})\|_{HS}^{2}\|(J\phi_{t}(\underline{x}))^{-1}\|_{op}^{2}\leq 4\sup_{\underline{x}\in S_{K}}\|J\mathbf{T}(\underline{x})\|_{HS}^{2}\leq\frac{\theta^{2}}{\eta^{2}}.$ $$

Combining the above observations, we obtain the following key ‘descent lemma’ for any $0\leq n\leq T$:

$$ $\displaystyle\mathsf{KL}(p_{K}(n+1)||\pi^{\otimes N})\leq\mathsf{KL}(p_{K}(n)||\pi^{\otimes N})-N\eta\mathbb{E}_{p_{K}(0)}\left[\mathsf{KSD}^{2}(\mu^{N}_{n}||\pi)\right]+c^{*}d\eta+\theta^{2}.$ $$

Hence, for $T\geq 2$,

$$ $\displaystyle\mathbb{E}_{p_{K}(0)}\left[\frac{1}{T}\sum_{n=0}^{T-1}\mathsf{KSD}^{2}(\mu^{N}_{n}||\pi)\right]\leq\frac{\mathsf{KL}(p_{K}(0)||\pi^{\otimes N})}{NT\eta}+\frac{c^{*}d}{N}+\frac{\theta^{2}}{N\eta}.$ $$

Routine computations give

$$ $\mathsf{KL}(p_{K}(0)||\pi^{\otimes N})\leq 2\mathsf{KL}(p(0)||\pi^{\otimes N})+\log 2\leq\gamma dN,$ $$

where $\gamma\coloneqq 2C_{KL}+\log 2$.
Using this in the previous display and recalling the choice of $\eta$, we obtain

$$ $\displaystyle\mathbb{E}_{p_{K}(0)}\left[\frac{1}{T}\sum_{n=0}^{T-1}\mathsf{KSD}^{2}(\mu^{N}_{n}||\pi)\right]\leq\gamma d\sqrt{C_{0}}\frac{\sqrt{N^{\frac{1-\alpha}{1+\alpha}}T^{\frac{2\alpha}{1+\alpha}}\vee N}}{T\theta}+\frac{c^{*}d}{N}+\sqrt{C_{0}}\frac{\theta\sqrt{N^{\frac{1-\alpha}{1+\alpha}}T^{\frac{2\alpha}{1+\alpha}}\vee N}}{N}.$ $$

The above expression is ‘approximately’ optimized on taking $T=\lceil N^{\frac{2}{1-\alpha}}\rceil$ and $\theta=\sqrt{N/T}=N^{-\frac{1+\alpha}{2(1-\alpha)}}$, which gives the bound

$$ $\mathbb{E}_{p_{K}(0)}\left[\frac{1}{T}\sum_{n=0}^{T-1}\mathsf{KSD}^{2}(\mu^{N}_{n}||\pi)\right]\leq\frac{(\gamma d+1)\sqrt{C_{0}}+c^{*}d}{N}.$ $$

The theorem follows from the above upon noting that $\sqrt{C_{0}}\leq c\left(d^{\frac{1+\alpha}{2(1-\alpha)}}+\sqrt{d}K^{\alpha}+d\right)$ for some constant $c$ depending only on the constants appearing in Assumption [2](#Thmassumption2).
∎

###### Assumption 2 .

###### Remark 3 .

###### Theorem 3 .

###### Remark 4 .

###### Lemma 2 .

###### Proof of Lemma 2 .

###### Lemma 3 .

###### Proof of Lemma 3 .

###### Lemma 4 .

###### Proof of Lemma 4 .

###### Proof of Theorem 3 .

## 4. Continuous-time Finite-Particle Rates in W 2 subscript 𝑊 2 W_{2} Metric

We now explore convergence rates for the continuous-time SVGD in the $L^{2}$-Wasserstein metric. For $s>0$, let $\mathcal{P}_{s}$ be the set of all Borel measurable probability measures on $\mathbb{R}^{d}$ with finite $s$-moment. For two measures $\mu,\nu\in\mathcal{P}_{s}$, the $L^{s}$-Wasserstein distance (based on the Euclidean distance) is defined as

$$ $\displaystyle\mathsf{W}_{s}(\mu,\nu)\coloneqq\left(\underset{\pi\in\Pi(\mu,\nu)}{\inf}~{}\mathbb{E}_{(X,Y)\sim\pi}\left[\|X-Y\|_{2}^{s}\right]\right)^{1/s},$ $$

where $\Pi(\mu,\nu)$ denotes the set of all possible couplings of the probability measures $\mu$ and $\nu$.

To address $W_{2}$ convergence, we consider the SVGD dynamics in ([2](#S1.E2)) with kernels of the form

$$ $\displaystyle\tilde{\textsf{k}}(u,v)=1+\langle u,v\rangle+\Psi(u-v).$ (13) $$

We further assume that the kernel obtained by $(u,v)\mapsto\Psi(u-v)$ is positive-definite, $\Psi(z)=\Psi(-z)$ for all $z\in\mathbb{R}^{d}$, $\sup_{z\in\mathbb{R}^{d}}\|\nabla\Psi(z)\|<\infty$, $\Psi\in\mathcal{C}^{3}$ and has a non-vanishing and continuous generalized Fourier transform. A classical example of a kernel that satisfies these assumptions is the Matérn kernel. We first state the following dissipativity and growth assumptions from Kanagawa et al. () along with an additional Laplacian growth condition.

###### Assumption 3 .

The following conditions hold:

- (a)
Dissipativity: The potential $V$ satisfies
$-\langle x,\nabla V(x)\rangle\leq-\alpha\|x\|^{2}+\beta_{1}\|x\|+(\beta_{0}-d),$
for some $\alpha>0$ and $\beta_{1},\beta_{0}\geq 0$.
- (b)
Growth: $\|\nabla V(x)\|\leq\lambda_{b}(1+\|x\|)$, for some $\lambda_{b}>0$.
- (c)
$\sup_{z\in\mathbb{R}^{d}}\Delta V(z)<\infty$.

The above assumptions are widely used in the MCMC literature literature and is satisfied in many cases including certain Gaussian mixture models, and allow for some degree of non-log-concavity in $\pi$.

###### Theorem 4 .

Let Assumption [3](#Thmassumption3) hold. Assume that the initialization is such that

$$ $\underset{N\to\infty}{\limsup}\frac{1}{N}\mathsf{KL}(p(0)||\pi^{\otimes N})<\infty.$ $$

Fix any $\eta>0$ and let $M=M(N)\coloneqq\lceil N^{2+\eta}\rceil$. Then, there exists a constant $C_{0}>0$ such that

$$ $\displaystyle\mathbb{E}[\mathsf{KSD}(\mu_{av}^{M}||\pi)]\leq\frac{C_{0}}{N^{1+\eta/2}},~{}~{}\forall N\geq 1\qquad\text{and}\qquad\mathsf{W}_{2}(\mu_{av}^{M},\pi)\stackrel{{\scriptstyle a.s}}{{\to}}0,~{}\text{as}~{}N\to\infty,$ $$

where recall $\mu_{av}^{M}(\mathsf{d}x)\coloneqq\frac{1}{M}\int_{0}^{M}\mu^{M}(t,\mathsf{d}x)\mathsf{d}t$.

The additional bilinear term in ([13](#S4.E13)) is the key to tackling Wasserstein convergence. It gives uniform control in $N,T$ over the second moment of the particle locations in the SVGD dynamics ([2](#S1.E2)), given in the following lemma.

###### Lemma 5 .

Under the same setting of Theorem [4](#Thmtheorem4), we have that

$$ $\displaystyle\limsup_{N\to\infty}~{}\sup_{T\geq 1}~{}\mathbb{E}\left[\frac{1}{T}\int_{0}^{T}\frac{1}{N}\sum_{i=1}^{N}\|x_{i}(t)\|^{2}\mathsf{d}t\right]<\infty.$ $$

This result is proved using Lyapunov function techniques and plays a key role in the proof of Theorem [4](#Thmtheorem4).

###### Proof of Lemma 5 .

For this proof, we will abbreviate $x_{i}(t)$ as $x_{i}$. Note that, using the SVGD equations ([2](#S1.E2)), we have

$$ $\displaystyle\begin{aligned} \frac{\mathsf{d}}{\mathsf{d}t}\left[\frac{1}{N}\sum_{i=1}^{N}V(x_{i})\right]=&-\left\|\frac{1}{N}\sum_{i=1}^{N}\nabla V(x_{i})\right\|^{2}-\frac{1}{N^{2}}\sum_{i,j}\langle x_{i},x_{j}\rangle\langle\nabla V(x_{i}),\nabla V(x_{j})\rangle\\ &+\frac{1}{N}\sum_{i}\langle x_{i},\nabla V(x_{i})\rangle-\frac{1}{N^{2}}\sum_{i,j}\langle\nabla V(x_{i}),\nabla\Psi(x_{i}-x_{j})\rangle\\ &-\underbrace{\frac{1}{N^{2}}\sum_{i,j}\langle\nabla V(x_{i}),\Psi(x_{i}-x_{j})\nabla V(x_{i})\rangle}_{\geq 0}.\end{aligned}$ (14) $$

The non-negativity claim above is a consequence of positive-definiteness of the kernel obtained by $(u,v)\mapsto\Psi(u-v)$. Note that

$$ $\displaystyle\frac{1}{N^{2}}\sum_{i,j}\langle x_{i},x_{j}\rangle\langle\nabla V(x_{i}),\nabla V(x_{j})\rangle$ $\displaystyle=\sum_{\ell,\ell^{\prime}=1}^{d}\left(\frac{1}{N}\sum_{i=1}^{N}x_{i,\ell}(\nabla V(x_{i}))_{\ell^{\prime}}\right)^{2}$ $\displaystyle\geq\sum_{\ell=1}^{d}\left(\frac{1}{N}\sum_{i=1}^{N}x_{i,\ell}(\nabla V(x_{i}))_{\ell}\right)^{2}$ $\displaystyle\geq\frac{1}{d}\left(\frac{1}{N}\sum_{i=1}^{N}\sum_{\ell=1}^{d}x_{i,\ell}(\nabla V(x_{i}))_{\ell}\right)^{2}$ $\displaystyle=\frac{1}{d}\left(\frac{1}{N}\sum_{i=1}^{N}\langle x_{i},\nabla V(x_{i})\rangle\right)^{2},$ $$

where the penultimate step follows by Cauchy-Schwartz inequality. Using the above inequality in ([14](#S4.E14)), we obtain

$$ $\displaystyle\begin{aligned} \frac{\mathsf{d}}{\mathsf{d}t}\left[\frac{1}{N}\sum_{i=1}^{N}V(x_{i})\right]\leq&-\frac{1}{d}\left(\frac{1}{N}\sum_{i=1}^{N}\langle x_{i},\nabla V(x_{i})\rangle\right)^{2}-\left\|\frac{1}{N}\sum_{i=1}^{N}\nabla V(x_{i})\right\|^{2}\\ &+\frac{1}{N}\sum_{i}\langle x_{i},\nabla V(x_{i})\rangle-\frac{1}{N^{2}}\sum_{i,j}\langle\nabla V(x_{i}),\nabla\Psi(x_{i}-x_{j})\rangle.\end{aligned}$ (15) $$

By Assumption [3](#Thmassumption3), there exists $A,\alpha,\beta,\gamma>0$ such that

$$ $\displaystyle\langle x,\nabla V(x)\rangle$ $\displaystyle\geq\alpha\|x\|^{2}~{}~{}~{}\text{for}~{}~{}~{}\|x\|\geq A,$ $\displaystyle\|\nabla V(x)\|$ $\displaystyle\leq\beta\|x\|~{}~{}~{}\text{for}~{}~{}~{}\|x\|\geq A,$ $\displaystyle\|\nabla\Psi\|_{\infty}$ $\displaystyle\leq\gamma.$ $$

Using the above in ([15](#S4.E15)), and defining

$$ $\displaystyle\Gamma(t)\coloneqq\sum_{i}\|x_{i}\|^{2}\mathbbm{1}[\|x_{i}\|\geq A],$ $$

we obtain

$$ $\displaystyle\frac{\mathsf{d}}{\mathsf{d}t}\left[\frac{1}{N}\sum_{i=1}^{N}V(x_{i})\right]\leq$ $\displaystyle-\frac{\alpha^{2}}{d}\left(\Gamma(t)\right)^{2}+\left(\frac{2C\beta}{d}+\beta\right)\Gamma(t)+\beta\gamma\left(\Gamma(t)\right)^{1/2}+C^{\prime},$ $$

where the constants $C,C^{\prime}>0$ are independent of $N$ (but they depend on $A$). Thus, choosing picking a sufficiently large constant $B>0$ (which is independent of $N$), we obtain for a constant $C_{B}>0$ that, for all $T>0$,

$$ $\displaystyle\frac{\alpha^{2}}{2d}\int_{0}^{T}\left(\Gamma(t)\right)^{2}\mathbbm{1}(\Gamma(t)\geq B)\mathsf{d}t$ $\displaystyle\leq\frac{1}{N}\sum_{i}V(x_{i}(0))+C_{B},$ $\displaystyle\int_{0}^{T}\left(\Gamma(t)\right)^{2}\mathbbm{1}(\Gamma(t)<B)\mathsf{d}t$ $\displaystyle\leq B^{2}T.$ $$

Therefore, we obtain for all $T>0$,

$$ $\displaystyle\frac{1}{T}\int_{0}^{T}\frac{1}{N}\sum_{i}\|x_{i}(t)\|^{2}\mathsf{d}t\leq\frac{1}{T}\int_{0}^{T}\left(\Gamma(t)\right)^{2}\mathsf{d}t+A^{2},$ with $\displaystyle\frac{1}{T}\int_{0}^{T}\left(\Gamma(t)\right)^{2}\mathsf{d}t\leq B^{2}+\frac{C_{B}}{T}+\frac{1}{NT}\sum_{i}V(x_{i}(0)).$ $$

Thus, for all $T\geq 1$ and $N\geq 1$ and for a constant $D>0$ (which is independent of $N$),

$$ $\displaystyle\mathbb{E}\left[\frac{1}{T}\int_{0}^{T}\frac{1}{N}\sum_{i=1}^{N}\|x_{i}(t)\|^{2}\right]\leq D+\frac{1}{T}\mathbb{E}\left[\frac{1}{N}\sum_{i}V(x_{i}(0))\right].$ $$

By the variational representation of relative entropy, for $\delta\in(0,1)$,

$$ $\displaystyle\mathbb{E}\left[\frac{1}{N}\sum_{i}V(x_{i}(0))\right]\leq\frac{1}{\delta}\log\left(\int\exp^{\delta V(z)}\pi(\mathsf{d}z)\right)+\frac{1}{N\delta}\mathsf{KL}(p^{N}(0)||\pi^{\otimes N}).$ $$

By Assumption [3](#Thmassumption3), $\pi$ is sub-Gaussian. Hence, we have

$$ $\displaystyle\limsup_{N\to\infty}\mathbb{E}\left[\frac{1}{N}\sum_{i}V(x_{i}(0))\right]<\infty,$ $$

from which, the result follows.
∎

###### Proof of Theorem 4 .

Recall $\mathsf{H}(t)=\mathsf{KL}(p^{N}(t)||\pi^{\otimes N})$. From the general $\mathsf{KSD}$ bound obtained in Theorem [1](#Thmtheorem1), with $\tilde{\textsf{k}}$, we obtain for every $T>0$,

$$ $\displaystyle\frac{1}{T}\int_{0}^{T}\mathbb{E}[\mathsf{KSD}^{2}(\mu^{N}(t)||\pi)]\mathsf{d}t\leq\frac{\mathsf{H}(0)}{NT}+\frac{1}{N^{2}T}\int_{0}^{T}\mathbb{E}\left[\sum_{k=1}^{N}C^{*}\left(x_{k}(t)\right)\right]\mathsf{d}t,$ $$

where $C^{*}(x_{i}(t))$ is as defined in ([7](#S2.E7)) with the kernel $\tilde{\textsf{k}}$. Now note that we can obtain constant $C>0$ such that, for any $z\in\mathbb{R}^{d}$,

$$ $\displaystyle\nabla_{2}\tilde{\textsf{k}}(z,z)\nabla V(z)$ $\displaystyle=\langle z,\nabla V(z)\rangle\leq\|z\|\|\nabla V(z)\|\leq C(1+\|z\|^{2}),$ $\displaystyle\tilde{\textsf{k}}(z,z)\Delta V(z)$ $\displaystyle\leq C(\|z\|^{2}+1+\Psi(0)),$ $\displaystyle-\Delta_{2}\tilde{\textsf{k}}(z,z)$ $\displaystyle=-\Delta\Psi(0).$ $$

Hence, for all $z\in\mathbb{R}^{d}$, we have that $C^{*}(z)\leq C_{1}\|z\|^{2}+C_{2}$, for some constants $C_{1},C_{2}>0$. Therefore, we have for any $t>0$ and $N\geq 1$, that

$$ $\displaystyle\frac{1}{T}\int_{0}^{T}\mathbb{E}[\mathsf{KSD}^{2}(\mu^{N}(t)||\pi)]\mathsf{d}t\leq\frac{\mathsf{H}(0)}{NT}+\frac{C_{1}}{NT}\int_{0}^{T}\mathbb{E}\left[\frac{1}{N}\sum_{k=1}^{N}\mathbb{E}[\|x_{k}(t)\|^{2}]\right]\mathsf{d}t+\frac{C_{2}}{N}.$ $$

Now, using Lemma [5](#Thmlemma5), there exists a constant $C_{4}>0$ such that for any $T\geq 1$ and $N\geq 1$,

$$ $\displaystyle\frac{1}{T}\int_{0}^{T}\mathbb{E}[\mathsf{KSD}^{2}(\mu^{N}(t)||\pi)]\mathsf{d}t\leq\frac{\mathsf{H}(0)}{NT}+\frac{C_{4}}{N}.$ $$

By the convexity of $\mathsf{KSD}$, we have for $N\geq 1$,

$$ $\displaystyle\mathbb{E}[\mathsf{KSD}(\mu_{av}^{M}||\pi)]\leq\frac{C_{0}}{N^{1+\eta/2}}.$ $$

Hence, by Borel–Cantelli lemma, we have that $\mathsf{KSD}(\mu_{av}^{M}||\pi)\stackrel{{\scriptstyle a.s}}{{\to}}0$, as $N\to\infty$. The stated Wasserstein convergence result now follows by Kanagawa et al. (, Thm. 3.1) taking $m=\operatorname{Id},q_{m}=1,q=2,L=L^{(2)}$ and $\Phi=\Psi$.
∎

By the results in Kanagawa et al. (, Section 3.2), we can translate the $\mathsf{KSD}$ bound in Theorem [4](#Thmtheorem4) into a bound in the $\mathsf{W}_{2}$ metric. For computational clarity, we restrict ourselves to the Matérn-family of kernels. Specifically we consider ([13](#S4.E13)) with

$$ $\displaystyle\tilde{\textsf{k}}_{\text{mk}}(u,v)\coloneqq 1+\langle u,v\rangle+\underbrace{\frac{2^{1-(d/2+\nu)}}{\Gamma(d/2+\nu)}\|\Sigma(u-v)\|_{2}^{\nu}K_{-\nu}\bigl{(}\|\Sigma(u-v)\|_{2}\bigr{)}}_{\coloneqq\Psi_{\text{mk}}(u-v)},$ (16) $$

where $\Gamma$ is the Gamma function,
$\Sigma$ a strictly positive definite matrix,
and $K_{-\nu}$ the modified Bessel function of the second kind of order $-\nu$.

To proceed, we also require the following assumption from Kanagawa et al. (), which is motivated by the Langevin diffusion:

$$ $\displaystyle\mathsf{d}Z_{t}=-\nabla V(Z_{t})\mathsf{d}t+\sqrt{2}\mathsf{d}B_{t},$ (17) $$

where $(B_{t})_{t\geq 0}$ is a $d$-dimensional Brownian motion. Note that ([17](#S4.E17)) is the stochastic differential equation equivalent of the Wasserstein gradient flow in ([3](#S1.E3)); see, for example, Jordan et al. (); Bakry et al. () for details. The connection between the two perspectives has in particular proved to be extremely useful for analyzing both Markov Chain Monte Carlo algorithms and particle-based methods.

###### Assumption 4 .

For $s\in\{1,2\}$, let $\rho_{s}:[0,\infty)\to[0,\infty)$ be an upper bounding function for the $L^{s}$-Wasserstein distance in the following sense:

$$ $\displaystyle\mathsf{W}_{s}(\mathcal{L}(Z_{t}^{x}),\mathcal{L}(Z_{t}^{y}))\leq\rho_{s}(t)\|x-y\|_{2},~{}\forall x,y\in\mathbb{R}^{d},t\geq 0,$ (18) $$

where $Z_{t}^{x}$ and $Z_{t}^{x}$ are Langevin diffusion processes in ([17](#S4.E17)) with initializations $Z_{0}=x$ and $Z_{0}=y$. Assume that $\tilde{\rho}(t)\coloneqq\frac{\log\frac{\rho_{1}(t)}{\rho_{1}(0)}-\log\rho_{2}(t)}{\log\frac{\rho_{1}(t)}{\rho_{1}(0)}}$ is uniformly bounded in $t$ and, moreover,

$$ $\displaystyle\int_{0}^{\infty}\rho_{1}(t)\left\{1+\sqrt{\rho_{1}(t)}\,\tilde{\rho}(t)\right\}\mathsf{d}t<\infty.$ $$

###### Remark 5 .

Suppose there exist $U>0$ and $R,L\geq 0$ such that the potential $V$ satisfies

$$ $\frac{\langle\nabla V(x)-\nabla V(y),x-y\rangle}{\|x-y\|_{2}^{2}}\leq\left\{\begin{array}[]{ll}-U&\mbox{if }\|x-y\|_{2}>R,\\ L&\mbox{if }\|x-y\|_{2}\leq R.\end{array}\right.$ (19) $$

Then, by Eberle (, ), there exists $c,c_{1}>0$ such that we can set $\rho_{1}(t)=ce^{-c_{1}t},\ t\geq 0$. Moreover, using ([19](#S4.E19)) and Grönwall’s lemma, we can set $\rho_{2}(t)=e^{Lt},\ t\geq 0$. Consequently, $\tilde{\rho}(t)=\frac{L+c_{1}}{c_{1}}$ and hence Assumption [4](#Thmassumption4) holds.

###### Theorem 5 .

Consider the SVGD updates in ([2](#S1.E2)) with the kernel in  ([16](#S4.E16)). Suppose Assumption [4](#Thmassumption4) and the assumptions made in Theorem [4](#Thmtheorem4) are satisfied. Then, there exists a constant $C(d)>0$ such that for any $\epsilon\in(0,1)$, we have

$$ $\displaystyle\mathbb{P}\left[\mathsf{W}_{2}(\mu_{av}^{M},\pi)\geq C(d)\left(\frac{C_{0}}{\epsilon N^{1+\eta/2}}\right)^{r(d)}\right]\leq\epsilon,\qquad\forall N\geq\left(\frac{C_{0}}{\epsilon}\right)^{\frac{2}{2+\eta}},$ $$

where $C_{0}$ is the same constant from Theorem [4](#Thmtheorem4), $C(d)$ is the constant $C_{P,d}(1)$ from Kanagawa et al. (, Theorem 3.5), and

$$ $\displaystyle r(d)\coloneqq\frac{1}{3(\frac{4d+1}{d})}\cdot\frac{1}{\frac{3d}{2}+\frac{17}{6}+\left[\frac{d+1}{d}+\frac{5}{3}\right]\nu}.$ (20) $$

###### Remark 6 .

Note that $r(d)\approx\frac{1}{18d}$ for la‘rge $d$. Hence, unlike the $\mathsf{KSD}$ rates in Theorem [5](#Thmtheorem5), the $\mathsf{W}_{2}$ rates have a curse-of-dimensionality. However, this is expected, as even in the case of i.i.d. samples, we have a similar curse-of-dimensionality (Dudley, ; Weed and Bach, ).

###### Proof of Theorem 5 .

By Theorem 3.5 in Kanagawa et al. (), we have that

$$ $\displaystyle\mathsf{W}_{2}(\mu_{av}^{M},\pi)\leq C(d)(1\vee\mathsf{KSD}(\mu_{av}^{M}||\pi)^{(1-r(d))})\mathsf{KSD}(\mu_{av}^{M}||\pi)^{r(d)},$ $$

where, from Kanagawa et al. () we have

$$ $\displaystyle r(d)=\frac{1}{3\left(\frac{4d+1}{d}\right)}\frac{1}{1+t_{1}}~{}~{}\text{ where}~{}~{}t_{1}=\frac{3d+1}{2}+\frac{1}{3}+\left[\frac{d+1}{d}+\frac{5}{3}\right]\nu,$ $$

resulting in ([20](#S4.E20)). Define $\mathcal{E}\coloneqq\left\{\mathsf{KSD}(\mu_{av}^{M}||\pi)\leq\frac{C_{0}}{\epsilon N^{1+\eta/2}}\right\}$. By Theorem [4](#Thmtheorem4) and Markov’s inequality, we have that $\mathbb{P}[\mathcal{E}^{c}]\leq\epsilon$. On the event $\mathcal{E}^{c}$, for $N\geq\left(\frac{C_{0}}{\epsilon}\right)^{\frac{2}{2+\eta}}$, we have

$$ $\displaystyle\mathsf{W}_{2}(\mu_{av}^{M},\pi)\leq C(d)\left(\frac{C_{0}}{\epsilon N^{1+\eta/2}}\right)^{r(d)},$ $$

thereby proving the claim.
∎

###### Assumption 3 .

###### Theorem 4 .

###### Lemma 5 .

###### Proof of Lemma 5 .

###### Proof of Theorem 4 .

###### Assumption 4 .

###### Remark 5 .

###### Theorem 5 .

###### Remark 6 .

###### Proof of Theorem 5 .

## 5. Propagation of Chaos

We now exhibit a *long-time propagation of chaos* (POC) for the particle system started from an exchangeable initial configuration and driven by the dynamics ([2](#S1.E2)). More precisely, we show that, under the conditions of Theorem [4](#Thmtheorem4), the time-averaged marginals of particle locations over the time interval $[0,N]$ become asymptotically independent, with distribution $\pi$, as $N\to\infty$.

###### Proposition 1 .

Suppose that the law $p^{N}_{0}$ of the initial particle locations $(x^{N}_{1}(0),\ldots,x^{N}_{N}(0))$ is exchangeable for each $N\in\mathbb{N}$. For $1\leq k\leq N$, define the $k$-dimensional marginal of the time-averaged occupancy measure of particle locations as follows:

$$ $\bar{\mu}^{N}_{k}(\mathsf{d}x_{1},\ldots,\mathsf{d}x_{k})\coloneqq\frac{1}{N}\int_{0}^{N}\mathbb{P}(x^{N}_{1}(t)\in\mathsf{d}x_{1},\ldots,x^{N}_{k}(t)\in\mathsf{d}x_{k})\mathsf{d}t.$ $$

Recall $M=M(N)\coloneqq\lceil N^{2+\eta}\rceil$. Under the same setting as Theorem [4](#Thmtheorem4), we have that, for any fixed $k\in\mathbb{N}$, $\mathsf{W}_{1}(\bar{\mu}^{M}_{k},\pi^{\otimes k})\to 0$, as $N\to\infty$.

###### Remark 7 .

This result should be compared with Shi and Mackey (, Theorem 2) and Lu et al. (, Proposition 2.6) where finite-time POC results are shown: the particle marginal laws at a fixed time become asymptotically independent as $N\to\infty$. However, owing to the lack of Lipschitz property of the vector field driving ([2](#S1.E2)), this POC can only be extended to growing times $t=t_{N}=O(\log\log N)$ when the particle marginal laws are not necessarily close to $\pi$. In contrast, Proposition [1](#Thmproposition1) extends to the time interval $[0,N]$ (hence, long-time POC) and the time-averaged particle trajectories essentially produce i.i.d. samples from $\pi$.

###### Proof of Proposition 1 .

Let $\mathcal{P}(\mathbb{R}^{d})$ denote the space of probability measures on $\mathbb{R}^{d}$, and denote by $\mathcal{P}(\mathcal{P}(\mathbb{R}^{d}))$ the space of probability measures on $\mathcal{P}(\mathbb{R}^{d})$. Let $\mathcal{L}(\mu_{av}^{M})$ denote the law of the random measure $\mu_{av}^{M}$ and $\delta_{\pi}$ denote the Dirac measure at $\pi$ in $\mathcal{P}(\mathcal{P}(\mathbb{R}^{d}))$.

By Lemma [5](#Thmlemma5) and exchangeability,

$$ $\sup_{N\geq 1}\mathbb{E}\left[\int_{\mathbb{R}^{d}}\|x\|^{2}\mu_{av}^{M}(\mathsf{d}x)\right]=\sup_{N\geq 1}\mathbb{E}\left[\int_{\mathbb{R}^{d}}\|x\|^{2}\bar{\mu}^{M}_{1}(\mathsf{d}x)\right]<\infty.$ (21) $$

Moreover, by Assumption [3](#Thmassumption3)(a), $\int_{\mathbb{R}^{d}}\|x\|^{2}\pi(\mathsf{d}x)<\infty$. Hence, by Chaintron and Diez (, Theorem 3.21), we conclude that $\mathsf{W}_{1}(\bar{\mu}^{M}_{k},\pi^{\otimes k})\to 0$ if and only if $\mathcal{W}_{1}\left(\mathcal{L}(\mu_{av}^{M}),\delta_{\pi}\right)\to 0$ as $N\to\infty$, where $\mathcal{W}_{1}$ is the Wasserstein distance on the space $\mathcal{P}(\mathcal{P}(\mathbb{R}^{d}))$ equipped with the distance function $\mathsf{W}_{1}$ as defined in Chaintron and Diez (, Definition 3.5).

Note that $\mathcal{W}_{1}\left(\mathcal{L}(\mu_{av}^{M}),\delta_{\pi}\right)\leq\mathbb{E}\left[\mathsf{W}_{1}(\mu_{av}^{M},\pi)\right]$. By Theorem [4](#Thmtheorem4) and Jensen’s inequality,

$$ $\mathsf{W}_{1}(\mu_{av}^{M},\pi)\stackrel{{\scriptstyle a.s}}{{\to}}0\qquad\text{as}\qquad N\to\infty.$ $$

Moreover, observe that

$$ $\mathsf{W}_{1}^{2}(\mu_{av}^{M},\pi)\leq\mathsf{W}_{2}^{2}(\mu_{av}^{M},\pi)\leq 2\int_{\mathbb{R}^{d}}\|x\|^{2}\mu_{av}^{M}(\mathsf{d}x)+2\int_{\mathbb{R}^{d}}\|x\|^{2}\pi(\mathsf{d}x)$ $$

and hence, by ([21](#S5.E21)) and Assumption [3](#Thmassumption3)(a), $\sup_{N\geq 1}\mathbb{E}\left[\mathsf{W}_{1}^{2}(\mu_{av}^{M},\pi)\right]<\infty$. In particular, $\{\mathsf{W}_{1}(\mu_{av}^{M},\pi):N\geq 1\}$ is uniformly integrable and thus $\mathbb{E}\left[\mathsf{W}_{1}(\mu_{av}^{M},\pi)\right]\to 0$ as $N\to\infty$. The result follows.
∎

###### Proposition 1 .

###### Remark 7 .

###### Proof of Proposition 1 .

## 6. Acknowledgements

KB was supported in part by National Science Foundation (NSF) grant DMS-2413426. SB was supported in part by NSF CAREER award DMS-2141621. We thank Lester Mackey for his insightful comments on an earlier version of this work and for valuable discussions regarding the broader literature on $\mathsf{KSD}$ and SVGD.

## Appendix A Auxiliary Results

###### Proof of Lemma 1 .

Let $F:\left(\mathbb{R}^{d}\right)^{N}\rightarrow\left(\mathbb{R}^{d}\right)^{N}$ be given by

$$ $F_{i}(\underline{z})\coloneqq-\frac{1}{N}\sum_{j}\textsf{k}(z_{i},z_{j})\nabla V(z_{j})+\frac{1}{N}\sum_{j}\nabla_{2}\textsf{k}(z_{i},z_{j}),$ $$

for $1\leq i\leq N$. By Assumption [1](#Thmassumption1), $F$ is a $\mathcal{C}^{2}$ map. Note that the SVGD particle trajectories can be written as $\{\mathbf{x}(t,\underline{x}(0)):t\geq 0\}$, where the flow $\mathbf{x}:[0,\infty)\times\left(\mathbb{R}^{d}\right)^{N}\rightarrow\left(\mathbb{R}^{d}\right)^{N}$ is given by

$$ $\dot{\mathbf{x}}(t,\underline{z})=F(\mathbf{x}(t,\underline{z})),\quad\mathbf{x}(0,\underline{z})=\underline{z},$ $$

with $\dot{\mathbf{x}}$ denoting the time derivative.
By Hartman [, Chapter 5, Cor. 4.1], the map $(t,\underline{z})\mapsto\mathbf{x}(t,\underline{z})$, and consequently, the inverse map $(t,\underline{z})\mapsto\mathbf{x}(t,\cdot)^{-1}(\underline{z})$, are $\mathcal{C}^{2}$ maps on $(0,\infty)\times\left(\mathbb{R}^{d}\right)^{N}$.

A simple change of variable formula gives (see Crippa [, Page 21])

$$ $p(t,\underline{z})=\frac{p_{0}}{\operatorname{det}(\nabla\mathbf{x}(t,\cdot))}\circ\mathbf{x}(t,\cdot)^{-1}(\underline{z}),\quad(t,\underline{z})\in(0,\infty)\times\left(\mathbb{R}^{d}\right)^{N}.$ $$

The existence and regularity of $p(\cdot,\cdot)$ then follows from the above observations.
∎

###### Proof of Lemma 1 .

## Peer Reviews

confidence: 3
contribution: 4
initial_rating: 8
presentation: 3
questions: - In the proof of Theorem 3, the bounds on the magnitude and the Lipschitz-ness of the update operator (Lemmas 3 and 4) grow with $n$ the iteration count. Is there any way to relate those quantities back to the distance between $\mu_n^N$ and $\pi$ instead? Intuitively, this way, the time-discretization error terms could be bounded uniformly for long times...
- Are there any results on the convergence of SVGD in KL divergence (with infinite particles and/or in continuous time)? If yes, do your results allow to improve upon them? If not, would your proof approach allow to get such a result?
- Does SVGD also exhibit long-time propagation of chaos for the "last-iterate" (as opposed to "time-averaged" in Proposition 1) occupancy measure of particle locations?
soundness: 4
strengths: This paper establishes quantitative convergence guarantees for finite-particle (and discrete-time) SVGD, with a much better dependency on problem parameters than the only previous known analysis. This is thus arguably the first satisfactory convergence bound, for an algorithm that has attracted considerable attention from theoreticians. So this paper's achievement is highly significant.

The main novel insight used in this paper is remarkably clean. It is also quite satisfying, in that it allows for an intuitive proof strategy. 

The presentation of the paper is clear, although a bit technical from section 4 onwards.
summary: This work provides a convergence analysis of the Stein Variational Gradient Descent (SVGD) algorithm in its full formulation, i.e., using finitely many particles and in discrete time. Such a quantitative convergence proof was long sought after, ever since the algorithm was first proposed in 2016. (The only previous known result, Shi and Mackey (2024), gave a quite poor convergence rate, and had a much more involved proof.) This paper thus improves upon a long line of work reviewed in the introduction. In particular, the behavior of SVGD in the infinite-particle limit is relatively well-understood, so the main difficulty lies in the finite-particle discretization.

This work's main novel insight is presented in Equation (9) in the proof of Theorem 1, in a continuous-time context: it consists in an identity which cleanly separates the finite-particle error from the infinite-particle behavior of SVGD. The finite-particle error term in this identity can be controlled by making a mild assumption on the kernel and the target distribution (Remark 1). The discrete-time, finite-particle convergence result, Theorem 3, builds upon this insight, as well as on ideas from prior works and on new estimates (Remark 4).

The Theorems 1 and 3 establish convergence in kernelized Stein discrepancy (KSD). They are complemented by convergence results in Wasserstein distance in section 4. A long-time propagation of chaos-type result for SVGD is established in section 5.
weaknesses: Section 5 on propagation of chaos (POC) could benefit from a little bit more motivation: it is not clear why POC would be a desirable property for SVGD.

Possible typos:
- In Assumption 1(b) and Lemma 1, p_0^N needs to be C2 (not C1) for p^N(t,.) to be C2
- in Assumption 2(d), maybe = is meant to be <=
- typos on line 430

---

confidence: 5
contribution: 4
initial_rating: 8
presentation: 3
questions: - *Theorems 1 and 2*. Is it easy to choose an initial distribution, such that $\lim\sup_{N \to \infty} \frac{1}{N} \mathrm{KL}\left(p^{N}(0) \,\big\|\, \pi^{\otimes N}\right) < \infty$? If yes, is there a general scheme for it?
- How easy would it be to replace the averaged KSD error with the 'last iterate' KSD error. In the paper you have this type of results for some time-averaged distributions. But is it possible to avoid averaging completely as in the case of LMC?
soundness: 4
strengths: The SVGD algorithm was well studied in practice for several years already. However, its theoretical understanding was rather limited. As well discussed by the authors, past work only tackled particular (simpler) cases discretization mechanisms of the continuous SVGD, leaving the most interesting case open. That is the finite-particle discrete-time setting. In this setting they solve this problem and obtain polynomial convergence guarantees for different types of metrics, under certain conditions.  
The paper is generally well-written, although certain mathematical details are omitted.
summary: This paper studies the finite-particle SVGD in both discrete and continuous settings. Their results include convergence results in averaged Kernel Stein Discrepancy and Wasserstein distance.
weaknesses: ### General comments

- Some of the conditions in the main results are not easy to verify. See the Questions section. 
- The paper is generally well-written, although certain mathematical details are omitted. 

### Mathematical comments 

- The derivations starting from *line 281* are not well-explained. Why does the first term on the right-hand side vanish on second line? How is the third line derived?
- In order to obtain (17), the term $(\sum_j V(x_j)/N)^{2\alpha}$ is upper bounded  by $\sum_j V(x_j)/N$. This does not seem to be correct, even with the assumption $2\alpha < 1$.
- *line 927*. "Routine computations give...". More details on this part would ease the reading. 

### Notation
- *Theorem 2*  $P(x_1(t) ∈ dx)$ is slightly vague from a mathematical point of view. Perhaps explicitly stating what is meant by this notation, would make the theorem clearer. 
-  $p^N (t,\underline{z})$ is defined in Lemma 1, but later in the paper the notation is changed to $p(t,\underline{z})$. 
- *notation in the proof of theorem 1* To keep notation self-explanatory I would suggest to use the number of particles in the notation for $H(0)$ in the proof of Theorem 2. That is to use $H^N(0)$, as later in the proof of the last claim you use $\sup_L H^L(0)/L$.

### typos

* *line 271* equation equation -> equation.
* *line 291* missing a period at the end of the equation.
* *line 674* Extra square bracket in the equation. 
* *line 747,749* There is a $\sum$ sign missing in the first term of the right side and in the definition of $f(n)$. 
* *page 8* literature literature -> literature

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: * For time-average distribution $\frac{1}{N}\int_0^N\mu^N(t, \mathrm{d}x)\ \mathrm{d}t$, why do you integrate it from $0$ to $N$ instead of from $0$ to $T$? Since $N$ is the number of particle, the time integration range is confusing to me.
* What is $\mathcal{L}$ in Assumption 4?
* The Growth condition in Assumption 2 is essential for Theorem 3. Can you discuss some relation between this condition with some other common conditions in sampling such as log Sobolev inequality, Poincare inequality and Talagrand inequality (which is also used in some previous works on SVGD)? What kind of distributions satisfy Assumption 2?
* Also, it would be helpful to collect all related results and their corresponding assumptions in a table for a clear comparison.
* The smoothness constant in condition (c) could be interesting to the convergence rate. Why don't you include that constant in Thm 3?
* What is the relation between Wasserstein distance and KSD? Since Thm 1 doesn't exhibit any curse of dimension (CoD), it would be interesting to provide some intuition about where the CoD comes from for Wasserstein distance. Is that due to the relation between Wasserstein distance and KSD? I think the convergence in Wasserstein distance is more interesting than KSD to sampling community, and thus there should be more discussion on this result. Does Matern kernel in SVGD show better performance than some bounded kernels (Gaussian RBF) in practice (maybe do some simulation)?
* If we choose $\alpha=1/2$, as remark 3 claims, the distribution will approach Gaussian. According to Thm 3, in order to achieve the averaged $\mathrm{KSD}^2\leq\varepsilon^2$, we need to choose $N\asymp 1/\varepsilon^2$, and thus $T=O(N^4)=O(1/\epsilon^8)$. Is this terrible mixing time comparable to other sampling algorithm for Gaussian targets?

I am happy to raise my score if the authors can answer some of the questions.
soundness: 3
strengths: * In KSD, this paper significantly improves the particle dependence over Shi & Mackey (2024) (which is known to be the previous best result) by considering the evolution of the joint distribution of N particles.
* In Wassertein-2 distance, this is the first convergence rate, albeit showing curse of dimension.
* The discussion on related works is extensive and informative.
summary: This paper performs a new analysis for Stein variational gradient descent (SVGD), achieving double exponential improvement of #particle for the continuous-time and discrete-time convergence rates in Kernel Stein discrepancy (KSD) over the best known previous result. This paper also establishes the convergence in Wasserstein distance using the bilinear Matern kernel and establishes marginal convergence and long-time propagation of chaos results for the time-averaged particle laws.
weaknesses: * Some notations should be further clarified, and there is not a subsection collecting all the notations which makes certain parts not that readable.
* This paper is short of some discussion on assumptions.
* Comparison with previous analysis including assumptions and rates is not that clear.
* The discussion on the convergence in Wasserstein-2 distance is weak.


For more details, see Questions below.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: Theorem 5 is derived for the Matérn-family of kernels (defined by eq. (12)) since it needs Theorem 3.5 in Kanagawa et al. (2022). However, the authors claim in the main text that the restriction to such kernels is only done for "computational clarity." Could the authors add a remark further clarifying if this means that Theorem 5 extends to the broader class of kernels defined in eq. (11)?
soundness: 4
strengths: The paper is extremely well written, and while I have not checked all the proofs in detail, the results appear to be formally correct. The authors also do a good job explaining the literature.

The authors bypass the challenges faced by previous attempts at deriving convergence rates for SVGD in the KSD metric by working with the joint density of particle locations and the N-fold product target measure, exploiting a simple and elegant relationship related to the evolution of their KL divergence.
summary: The paper studies finite-particle convergence rates for the Stein Variational Gradient Descent (SVGD) algorithm in the Kernelized Stein Discrepancy (KSD), deriving results in both continuous and discrete times. It also provides convergence rates for the continuous-time SVGD in the L2-Wasserstein metric for a specific class of kernels.

Minor typo: in line 430, either refer to Assumption 3 in the singular or the conditions in the plural.
weaknesses: A key element in the development is the N-fold product target measure $\pi^{\bigotimes N}$. Although it's definition can arguably be derived from its name, I think it would be nice to formally define it too; pressumably, $\pi^{\bigotimes N}(x_1,\cdots,x_N) := \pi(x_1)\times\cdots\times\pi(x_N)$.

Meta-review: This work provides a convergence analysis of the Stein Variational Gradient Descent (SVGD) algorithm in its full formulation, i.e., using finitely many particles and in discrete time. Such a quantitative convergence proof was long sought after, ever since the algorithm was first proposed in 2016. (The only previous known result, Shi and Mackey (2024), gave a quite poor convergence rate, and had a much more involved proof.) This paper thus improves upon a long line of work reviewed in the introduction. In particular, the behavior of SVGD in the infinite-particle limit is relatively well-understood, so the main difficulty lies in the finite-particle discretization. This work's main novel insight is presented in Equation (9) in the proof of Theorem 1, in a continuous-time context: it consists in an identity which cleanly separates the finite-particle error from the infinite-particle behavior of SVGD. The finite-particle error term in this identity can be controlled by making a mild assumption on the kernel and the target distribution (Remark 1). The discrete-time, finite-particle convergence result, Theorem 3, builds upon this insight, as well as on ideas from prior works and on new estimates (Remark 4). The Theorems 1 and 3 establish convergence in kernelized Stein discrepancy (KSD). They are complemented by convergence results in Wasserstein distance in Section 4. A long-time propagation of chaos-type result for SVGD is established in Section 5.

Some of the key strengths:
- This paper establishes quantitative convergence guarantees for finite-particle (and discrete-time) SVGD, with a much better dependency on problem parameters than the only previous known analysis. This is thus arguably the first satisfactory convergence bound, for an algorithm that has attracted considerable attention from theoreticians. So this paper's achievement is highly significant.
- The main novel insight used in this paper is remarkably clean. It is also quite satisfying, in that it allows for an intuitive proof strategy.
- The presentation of the paper is clear, although a bit technical from Section 4 onwards. The paper is generally well-written, although certain mathematical details are omitted (much of this was fixed during the author-reviewer discussion).
- The SVGD algorithm was well studied in practice for several years already. However, its theoretical understanding was rather limited. As well discussed by the authors, past work only tackled particular (simpler) cases discretization mechanisms of the continuous SVGD, leaving the most interesting case open. That is the finite-particle discrete-time setting. In this setting they solve this problem and obtain polynomial convergence guarantees for different types of metrics, under certain conditions.
- In KSD, this paper significantly improves the particle dependence over Shi & Mackey (2024) (which is known to be the previous best result) by considering the evolution of the joint distribution of N particles.
- In Wassertein-2 distance, this is the first convergence rate, albeit showing curse of dimension.
- The discussion on related works is extensive and informative.


Some of the key weaknesses:
- some typos
- Section 5 on propagation of chaos (POC) could benefit from a little bit more motivation: it was not at first clear why POC would be a desirable property for SVGD. An explanation was added later, during the discussion period.
- Some derivations were skipped - these steps were added in the discussion period.
- Some notation seems to be undefined or hard to trace. Pointers were provided in the discussion period.

---

All reviewers eventually agreed on the score: "8: accept, good paper". The paper is unanimously praised, and as the AC, I agree with their evaluation, and recommend the paper for acceptance.

Decision: Accept (Oral)