A Finite-Particle Convergence Rate for Stein Variational Gradient Descent
Authors: Jiaxin Shi
Lester Mackey
Venue: NeurIPS 2023 poster (2023)
Keywords: Stein Variational Gradient Descent
SVGD
variational inference
sampling
optimization
Stein's method
TL;DR: We provide the first finite-particle convergence rate for Stein variational gradient descent (SVGD).

Abstract: We provide the first finite-particle convergence rate for Stein variational gradient descent (SVGD), a popular algorithm for approximating a probability distribution with a collection of particles. Specifically, whenever the target distribution is sub-Gaussian with a Lipschitz score, SVGD with $n$ particles and an appropriate step size sequence drives the kernel Stein discrepancy to zero at an order ${1/}{\sqrt{\log\log n}}$ rate. We suspect that the dependence on $n$ can be improved, and we hope that our explicit, non-asymptotic proof strategy will serve as a template for future refinements.

A Finite-Particle Convergence Rate for Stein Variational Gradient Descent
Jiaxin Shi" Stanford University Stanford, CA 94305 taxins@stanford edu
Lester Mackey
Microsoft Research New England Cambridge, MA 02474 1mackey@miccrooof com
Abstract
We provide the first finite-particle convergence rate for Stein variational gradient descent (SVGD), popular algorithm for approximating a probability distribution with collection of particles. Specifically, whenever the target distribution is sub- Gaussian with a Lipschitz score, SVGD with n particles and an appropriate step size sequence drives the kernel Stein discrepancy to zero at order 1/ /log log rate. We suspect that the dependence on n can be improved, and we hope that explicit, non-asymptotic proof strategy will serve template for future refinements.
Introduction
Stein variational gradient descent ISVGD, 18] is an algorithm for approximating a target probability distribution P on IRd with a collection of n particles. Given an initial particle approximation 4D = - -.=1 6r, with locations 2ạ E Rd, SVGD (Algorithm 1) iteratively evolves the particle locations to provide more faithful approximation of the target P by performing optimization in the space of probability measures. SVGD has demonstrated encouraging results for a wide variety of inferential tasks, including approximate inference [18, 28, 27], generative modeling [26, 13], and reinforcement learning [1 21].
Despite the popularity of SVGD, relatively little is known about its approximation quality. A first analysis by Liu [17, Thm. 3.3] showed that continuous SVGD-that is, Algorithm initialized with a continuous distribution 14 in place of the discrete particle approximation n² converges to P in kernel Stein discrepancy IKSD, 4, 19, 9]. KSD convergence also known to imply weak convergence [9, 3, 12, 1] and Wasserstein convergence [14] under various conditions on the target P and the SVGD kernel k. Follow-up work by Korba et al. [15]. Salim et [22], Sun et al. [24] sharpened the result of Liu with path-independent constants, weaker smoothness conditions, and explicit rates of convergence. addition, Dunean et al. [6] analyzed the continuous-ting limit of continuous SVGD provide conditions for exponential convergence. However, each of these analyses applies only to continuous SVGD and not to the finite- particle algorithm used in practice.
To bridge this gap. Liu [17, Thm. 3.2] showed that n-particle SVGD converges continuous SVGD hounded-Lipschitt distance but only under boundedness assumptions violated by most applications of SVGD. To provide a more broadly applicable proof of convergence, Gorham et al. [10, Thm. 7] showed that n-particle SVGD converges to continuous SVGD I-Wasserstein distance under assumptions commonly satisfied in SVGD applications. However, both convergence results asymptotic, providing neither explicit error bounds nor rates of convergence. Korba et al. [15, Prop. 7] explicitly bounded the expected squared Wasserstein distance between n-particle and continuous SVGD but only under the assumption of bounded V log p. an assumption that rules out all strongly
Part of this work was done at Microsoft Research New England.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Algorithm 1 r--particle Stein Variational Gradient Descent [18]: SVGD
Input: Target P with density p, kernel k, step sizes (c,)e20, particle approximation Pa 1 = 62., rounds r do
for s = 0,
24 + 2, 6, En= K(2 x.) V log p(z,) + VV Z, for = I,...,n.
Output: Updated approximation p 2. Ei= 6z; of the target P
Algorithm 2 Generic Stein Variational Gradient Descent [18]: SVGD(Ho,
Input: Target with density p, kernel k, step sizes (te)s20. approximating measure Po: rounds r for s 0, 0..... r 1 do
Let Ma+1 be the distribution of X t f k(z, X logp(z) + V for X pa.
Output: Updated approximation Hr of the target P
log concave or dissipative distributions and all distributions for which the KSD is currently known to control weak convergence [9, 3, 12, 1]. In addition, Korba et al. [15] do not provide a unified bound for the convergence of n-particle SVGD to P and ultimately conclude that "the convergence rate for SVGD using [4ğ] ] remains an open problem." " The same open problem was underscored in the later work of Salim et al. [22], who write "an important and difficult open problem in the analysis of SVGD is to characterize its complexity with a finite number of particles."
In this work, we derive the first unified convergence bound for fnite-partich SVGD to its target. To achieve this, we first bound the 1-Wasserstein discretization error between finite- mnite-particle and continuous SVGD under assumptions commonly satisfied in SVGD applications and compatible with KSD weak convergence control (see Theorem 1). We next bound KSD in terms of 1-Wasserstein distance and SVGD moment growth to explicitly control KSD discretization error in Theorem 2. Finally, Theorem 3 combines our results with the established KSD analysis of continuous SVGD to arrive at an explicit KSD error bound for n-particle SVGD.
2 Notation and Assumptions
Throughout, we fix a nonnegative step size sequence (cs)s20. target distribution P in the set Pi of probability measures on dRd with integrable first moments, and a reproducing kernel k-a symmetric positive definite function mapping IR x Rd to R-with reproducing kernel Hilbert space (RKHS) H and product RKHS Hd A X 1=11 H [2]. We will use the terms "kernel" and "reproducing kernel" interchangeably. For all μr, v E PI, we [j,,, be the set of all couplings of μ and v, i... joint probability distributions y over P1 X P1 with μ and v as marginal distributions of the first and second variable respectively. We further let μ @ // denote the independent coupling, the distribution of (X, 2) when X and Z are drawn independently from μ and v respectively. With this notation in place we define the 1-Wasserstein distance between μl, v E P, Wi (p.z) & inf inf Exx, II x1 and introduce the shorthand mm... E |ll x= 1]1 for each x² E Rdd mp.P - Exx,2)=0oP[|A - Z1l)). and Mp.P - EX [||X 2 (1 We further define the Kullback-Leibler (KL) divergence as KL(μ(Iv) & Eo,l 4e)] when μ is absolutely continuous with respect to y (denoted by < v) and as oo otherwise.
Our analysis will make use of the following assumptions on the SVGD kernel and target distribution.
Assumption 1 (Lipsehitz, mean-zero score function). The target distribution P E P, has dif- ferentiable density with an L-Lipschitz score function sp & V logp. i.e.. [[,, - sp(y)ll2 S
L| - 2ll2 for all x, E Rdd Moreover, Epls,] = 0 and sx(x*)) = 0 for some x² E Rd. Assumption (Bounded kernel derivatives). The kernel is twice differentiable and sup>,eRd max(Ik(x, v)1. 2 v) VI,,
ooll V/, v) 1)lp S net for in > O.
Moreover, for all i,j E 21. d). supxeR= V,, Ve, V., Va, ((x,)))== S x2 K2 > 0.
Assumption 3 (Decaying kernel derivatives). The kernel ls is differentiable and admits a ay IR such that, for all x. y E IRd satisfying ||æ- - vll2 2 1,
Vv. S 7/1l== v1l2-

---

Assumptions 1, 2, and 3 are both commonly invoked and commonly satisfied in the literature. For example, the Lipschitz score assumption is consistent with prior SVGD convergence analyses (17, 15, 22] and, by Gorham and Mackey [8, Prop. II. the score Sp is mean-zero under the mild integrability condition Ex-r[l (x()) < co. The bounded and decaying derivative assumptions have also been made in prior analyses [15, 9] and, as we detail in Appendix A, are satisfied by the kernels most commonly used in SVGD, like the Gaussian and inverse multiquadric (IMQ) kernels. Notably, in these cases, the bounds K1 and K2 are independent of the dimension d.
To leverage the continuous SVGD convergence rates of Salim al. [22], we additionally assume that the target P satisfies Talagrand's 's T₁ inequality [25, Def. 22. Remarkably, Villani [25, Thm. 22.10] showed that Assumption is equivalent to P being assumption holds for all strongly log concave P [23, Def. 2.9], all P satisfying the log Sobolev inequality [25, Thm. 22.17], and all distantly dissipative P for which KSD known to control weak convergence [9, Def. 4].
distribution. Hence, this mild
Assumption 4 (Talagrand's Ti inequality [25, Def. 22.1]). For P E Pi, there exists X > 0 such that, for all J E Pı,
Wi,, 2KL((|/P)/x
Finally we make use of the following notation specific to the SVGD algorithm.
Definition 1 (Stein operator). For any differentiable vector-valued function 9 Rd + Rd, the Langevin Stein operator for P satisfying Assumption is defined by
(T) & (o((z),(()) + V g(æ) for all x E Rd.
Definition 2 foccto-vvllued Stein operator). For any differentiable function h Rd + R. the vector-valued Langevin Stein operator for P satisfying Assumption is defined by
(z) e sp(z)h(z) + Vh(x) for all x E ER..
Definition (SVGD transport map and pushforward), The SVGD transport map [18] a target P satisfying Assumption a kernel k satisfying Assumption step size 2 0, and an approximating distribution E Pi takes the form
(x)(()) 2 x + elE (xxxxx((xkp(
for all E E
Moreover, the SVGD pushforward & (H) represents the distribution of (X) when X μt.
Definition (Kemel Stein discrepancy). The Langevin kernel Stein discrepancy [KSD, 4, 19, for P satisfying Assumption 1, k satisfying Assumption 2, and measures μr, V E Pi is given by
(1ll x KSDp(u, v) - sup
[T [T[gg
Notably, the KSD so-defined is symmetric in its two arguments and satisfies the triangle inequality. Lemma (KSD symmetry and triangle inequality). Under Definition 4, for all μ., v, E Pi. KSDp(H,P) = KSDp(v. p)) and KSDP(H, < KSDP(H, T) + KSDP(T,V),
Proof. Fix any MT E PI. For symmetry, we note that 9 E Hd + f = -g Hdd so KSDP(U,T)
sup E,, E, [Teg] sup E, Tp E, [Tp]] KSDP(T, IIfi 11
asll S1
To establish the triangle inequality, we write
KSDr(H,)) sup 1 F, [Tg)
F2, 17, [Trg) R, [Trg] E., [Trg]
I supllally 21 [E,, [pg] - E, (Tpg)) + sup I (1xxz (Ppx - Ep (Pph))
KSDp(1 T) + KSDp(TT,
3

---

3 Wasserstein Discretization Error of SVGD
Our first main result concerns the discretization error of SVGD and shows that n-particle SVGD remains close to its continuous SVGD limit whenever the step size sum b -x= 6x is sufficiently small.
Theorem (Wasserstein discretization error SVGD). Suppose Assumptions 1, 2, and 3 hold. For any Po 10 E PI, the outputs μr = SVGD(HG; and μi = SVGD(HO .r) of Algorithm satisfy
Wi W1 Wi (18 16)
log
b ([(AAABexxxpCX Bexp(C(b,
for b A Ex Co. A (ci + (1) (1+ + pp.a)) B mg 16 C =n + 1). C1 = max( 12), and 02 = xL + 1) + max(7; k2).
We highlight that Theorem 1 applies to any Pi initialization SVGD: the initial particles supporting Hü could, for example, be drawn i.idd from a convenient auxiliary distribution 140 or even generated deterministically from some quadrature rule. To marry this result with the continuous SVGD convergence bound of Section 5, we will ultimately require p to be a continuous distribution with finite (L [P). Hence, our primary desideratum for SVGD initialization is that μá have small Wasserstein distance to some n with ( < co. Then, by Theorem 1, the SVGD discretization error Wi (mf,, 14,5) will remain small whenever the step size sum not too large.
The proof of Theorem 1 in Section 6 relies on two lemmas. The first, due to Gorham et al. [10]. shows that the one-step SVGD pushforward map &. (Definition 3) is pseudo-Lipschitz with respect to the 1- L-Wasserstein d whenever the score function V log and kernel k fulfill commonly- satisfied pseudo-Lipschitzz condition. Here, for any Rdd - IR we define the Lipschitz constant Lip(g) A sup,,=eRd lzg(z) g(>)]l///l //1l==111= [|z 2112-
Lemma 2 (Wasserstein
Lipschitzness of SVGD [10, Lem. 12]). For P satisfying Assump- tion 1, suppose that the following pseudo-Lipschir, bounds hold
Lip(s(())M<r,)) V V_k(z,))) )) ci + || x= x²11)); Lip(sph(;, 2) + Vak(, 2)) S c2(1 + I| x² 122)
for some constants C1, C2 E and all x, E R.d. Then, for any ,s, v E PI.
W1(#. (v))) & Wi(H, + ecp,v):
where D. is the one-step SVGD pushforward (Definition 3) and Cp.v ei (1++m
In Section 6, we will show that, under Assumptions 1, 2. and 3, the preconditions of Lemma 2 are fulfilled with e₁ and 02 exactly in Theorem 1. The second lemma, proved in Section 7, controls the growth of the first and second absolute moments under SVGD.
Lemma 3 (SVGD moment growth). Suppose Assumptions and 2 hold, and let C = x27(I.. 1). Then the SVGD output pr of Algorithm 2 with b A Ex= C, satisfies
p. I Mpp,P P S Mo I c, S ug.PP P exp(CC,-11)
Mp, S Mp IT (1 + 2) < Mp..P P exp (2Cb,-1).
The key the proof of Lemma 3 is that we show the norm of any SVGD update, i.e., (x) x 21|2- is controlled by m, the first absolute moment of measured against P. This is mainly due to the Lipschitzness of the score function Sp and our assumptions on the boundedness of the kernel and its derivatives. Then, we can use the result to control the growth of m across iterations since 2 The same strategy applies to the second absolute moment M,. The proof of Theorem 1 then follows directly from Lemma 2 where we plug in the first moment bound of Lemma 3.
My.+11.P Ex (xxx [IIT,,......))
We say map & P1- + Pi is pseudo-Lipschite with respect to 1- 1-Wasserstein distance if, for a constant Cp E L., some xx Rdd and all u.u Pi. (I()(H), ((v)) S WI(H,)) (1 + My.z My.x" Ca.

---

KSD Discretization Error of SVGD
Our next result translates the Wasserstein
bounds of Theorem into KSD error bounds.
Theorem (KSD discretization error of SVGD). Suppose Assumptions 1, 2, and 3 hold. For any M0 p E Pi, the output of Algorithum 2, μ. SVGD(P) r) and μu, = SVGGD (p0 r), satisfy KSDp(pP a ( S (Nr + k2d)wn, exp(b,- (A + exxp(Cb,-1))
+ +Kid! / 22222M2 ,0 exp(b,- (2C + A+ B Bexp(Cb,-1))/2)
for Wonn A (i ) and A, B, C defined as in Theorem 1.
Our proof of Theorem 2 relies on the following lemma, proved in Section 8, that shows that the KSD controlled by the 1-Wasserstein distance.
Lemma (KSD- Wasserstein bound). Suppose Assumptions I and 2 hold. For any μ. E Pı.
KSDP(u, v) S (k) k2d)Wi () + 22,,,
Lemma 4 is proved in two steps. We first linearize (z) in the KSD definition through the Lipschitzness of 8p and the boundedness and Lipschitzness of RKHS functions. Then, we assign a I-Wasserstein optimal coupling of (H, 1) to obtain the Wasserstein bound on the right.
Proof of Theorem 2 The result follows directly from Lemma 4, the second moment bound of Lemma 3, and Theorem
5 A Finite-particle Convergence Rate for SVGD
To establish our main SVGD convergence result, we combine Theorems and 2 with the following descent lemma for continuous SVGD eπror due to Salim et al. [22] which shows that continuous SVGD decreases the KI. divergence to and drives the KSD) P to zero.
Lemma 5 (Continuous SVGD descent lemma [22, Thm. 3.21). Suppose Assumptions 1, 2, and hold, and consider the outputs 117 SVGD(u& ,) and 1,21 SVGD(uō + +1) of Algorithm with po
<< P. 1f maxomasssr S R for some a > 1 and
Ro A min P
milltaz] ( (a- (a-1)(1 Lmn S + + [KL(u81P)) for po {1,2},
(1)
then
(L(1E4 KL(U P) -c, -, 11-nilbta cr KSDr(u,,
x(((+a))
By summing the result (2) over r E {O..... f}, we obtain the following corollary. Corollary 1. Under the assumptions and notation of Lemma suppose maxogr Ep S Ra,1 for
some > and let n., Eiwo dr.) for c(c) A <(1 xF(Ltaa))) :). Since & I c(c)
c(c,))
have
Σt T., KSD p) 2e c(E,) KL( S
2. 2 kL P).
Finally, arrive main result that bounds the approximation error of n-particle SVGD in terms of the chosen step size sequence and the initial discretization error W, (48 ())).
Theorem (KSD error of finite- paritce SVGD). Suppose Assumptions 1, 2, 3. and 4 hold, fix any
HD < P and pa PL and let Wo,n & W1 (4ö p maxosr<tt S Ra.1 for some 1 and Ra,1 defined in Lemma 5, then the Algorithm 2 outputs μ. = SVGD(40 rr) satisfy
minggrsi KSDp(uP, P) S Ei KSDP a v R (L(
2
(3)
for n, as defined in Lemma (A, C.) as defined Theorem 1, b.-1 A Dt-1 cy and
a a-1 - (ky + kyd) exp(b. (A + exp(Cb,-1)))
(4)
/4 22,, pwo,, exp(br-1 A+ B Bexx((b(-11)/2)
Note that the value assigned does not have any impact the algorithm that generates μu when
5

---

Proof. By the triangle inequality (Lemma 1) and Theorem we have
KSDp(p?. P) - KSDp P)1
14) S a-
for each Therefore
Er=0 or (KSDDpppp ax-1)² S Er= ; P) R (L(P)))))
(5)
where the last inequality follows from Corollary 1. Moreover, by Jensen's inequality.
E'= TH (KSDDr(( P) ar-1) EE ,, 7 Ei= T
(6)
Combining (5) and (6), we have
D KSDr(uF, P) S Er=o T V Ru,i kL P).
We finish the proof by noticing that Ei= T, maxogrsi Pr-1 = ac-1.
The following corollary, proved in Appendix B, provides an explicit SVGD convergence bound and rate by choosing the step size sum to balance the terms on the right-hand side of (3). In particular, Corollary 2 instantiates an explicit SVGD step size sequence that drives the kernel Stein discrepancy to zero at an order 1/ //olog log(n) rate.
Corollary 2 (A finite-particle convergence for SVGD). Instantiate the notation and assumptions of Theorem 3, let (wo,,, A, B, C) be any upper bounds on (Wo A, B, C) respectively, and define the growth functions
<(w)= a log log(e" ( + 1) and (B,,(E, - & logg max(B, 3 log 1 -v))
If the step size sum b Er c for
* min
(b / (() ) A,B1) ; B.C Wo, (W),,)) A 28, 82))
31 A max
1, 1, (w. (Wo.))
and
32 A max
(1, (oo, (() ,, 20,1))
then
KSD (H, P)) 0SrSt
min
(KI + won + 1 kidd/4 L 2 no puoo +
2
6 P)
if =
V
Bu,1
(x2d) trd P
2KL(M
otherwise
Ra.1t y loRl
lng(1/(gg,
(l -A-20))
(.o, 0.13]
-0 Mog log(ee wg.
(8)
If, in addition, p EE
Sa, for
Ud p with Mage Euz 11:112]
then
Mage (dd(n)
Wa,
antava W0,n
with probability at least 1 - cō for universal constant > O. Hence, with this choice of wo...
minogr KSDp(u;,P) o
Vlog log(16)
with probability at least cg.
Specifically, given any upper bounds (wa... A, the quantities (Wo,n- A, B,C) defined in Theorem 3, Corollary 2 specifies a recommended step size sum s to achieve an order
1/ log log(e" + 1 rate SVGD convergence KSD. Several remarks are in order. First, To,-

---

the target step size sum sn is easily computed given (wo,n, A, A. C). Second, we note that the target S can equal when the initial Wasserstein upper bound W is insufficiently small since log( B max B, 1 log + -))) = log( B = 0 for small arguments x. In this case, the setting 6 = 0 amounts to not running SVGD at all or, equivalently, to setting all step sizes to 0.
3
Third, Corollary also implies time complexity for achieving order 1/ / /log log(e=
error rate. Recall that Theorem 3 assumes that maxogr<t Er S Ra,1 for Ra,1 defined in (1). Hence, t* & [ rounds of SVGD are necessary to achieve the recommended setting Σx- 6 s while also satisfying the constraints of Theorem 3. Moreover, 1 rounds are also sufficient if each step size is chosen equal to //,"". In addition, since * Ollg log(e" + "e.. )). Corollary 2 implies that SVGI
W0...
deliver minosrsi- KSDp(u,, P) < A in t* (1)/2²) rounds. Since the computational complexity of each SVGD round is dominated by ((n²) kernel gradient evaluations (i.e., evaluating (1i, .ty) for each pair of particles (zi, Ry)), ) the overall computational complexity to achieve the order 1/ log log(e"
error rate is (n² [s 12,1 (n² log log(e" )),))
6 Proof of Theorem 1: Wasserstein discretization error of SVGD
In order to leverage Lemma 2, first show that the pseudo-Lipschitzness conditions of Lemma hold given our Assumptions to 3. Recall that 8p is Lipschitz and x satisfies s sp(x") = 0 by Assumption 1. Then, by the triangle inequality, the definition of II-llap- [[k(r, 2)112 S x? and | V.Vkkar =)pp S nî from Assumption 2, and Cauchy-Schwartz,
Lip(sp + Vak(z,)) V
- +,=" IVV
-| - =0 Tul) V (id,,,)). l)pp
ul) + V.VV,, =)
max(x
Letting с max(xf x and taking supremum over z proves the first pseudo-Lipschitzness condition. Similarly, we have
Lip(spk(( 2) + 2))(+
< supreR Lip(sp) (k)sss)((( (z, 2)1 + (x) (1(x") 2)1(2 k/ 2)
S L + supzEra L||. - x² ll V aak(r; z)l12 + x
(10)
where we used the Lipschitzness of s, from Assumption I and |k(x, =)1 S kス from Assumption 2. Now we consider two cases separately: when || 21|2 2 1 and || =||2 < 1.
V |
2) <
Case 1: || - =112 2 1. Recall that there exists y > 0 such that V/, 2)112 S 7/|l - =1|2 by
Assumption 3. Then, using this together with the triangle inequality, we have
||x x 2 2)122 s =11== +|1,++1====11 lla 7(1 + ||= x= 112)
(11)
--=1|
Case 2: ||æ 2ll2 1. Then, using |V,,( =) 2)1 S nΩ from Assumption 2 and by the triangle inequality, have
|| - x 112l 2)122 I (1 =||2 + || - x x*1l2 < x1 [1 ||> x*1))).
(12)
Combining (11) and (12) and using the triangle inequality, we get
a x 1*1|2 V k(z 2)11 S max(7, x1) + ||2- x 12))
(13)
Plugging (13) back into (10), we can show the second pssuddoLLisschiee condition holds for c2 max(k? 1) + maxxy xf), max(y, x²t) x² 1) + L mmx((y,x)))
7

---

Now we have proved that both gseudo-Lipschizznss preconditions of Lemma 2 hold under our Assumptions 1 3. By repeated upplication of Lemma and the inequality (1 + x) S E², we have
: ee (M,", Der (44 S (1+ (1,
S Wi mo)
II == (1+c, - Wi(ui po exp( Σ x=0 EgDs) (14)
for D3 c1(1 m)y, + c2(1 m.)xx.)
Using the result from Lemma 3, we have
Dot1 S A B exxp(bb.)
for A = (0i + 02)(1 + mp ), B ei cmg P + p2 P, and C = =n((3I. + d). Therefore
Ex D2 S maNoswsr D2 E. I + Bexp(Ch,-1)) s (A (A- + B exp(Cb,))
Plugging this back into (14) proves the result.
7 Proof of Lemma 3: SVGD moment growth
From Assumption 2 we know [k(y,,))] S ni and [[Vik(y, 1)pp.p S xg. The latter implies
IV (v, V ==,,,))) - xilly - 2112-
Recall that 8p Lipschitz and satisfies E-]s by Assumption 1. Let μ be any probability measure. Using the above results, Jensen's 's inequality and the fact that (z)r(((Ar((;x))((2) = 0. we have
[x) - 211, S (e](Bxx((((44p((()))))))))
= ( + (k(X,)) - ((Z,z))(ssxx - Ep(sp()))
+ (Vxk(X V
(10x::))_n00P(((2223]]]]|,,1 Sp
(I(X,=)) + (k(Z,))) - Ey~rlsp(Y)ll
+ +IVVx((X, x) - [
< elE <1 - - + + 2 -Y
ex1 1) 10) - 2112]
eCmp.p..
(15)
The last step used the definitions mG,P B(x - 2112] and C = x2 + 1). Then, applying the triangle inequality and (15), we have
Mar+1 = E (x, 8P ||| - 2 = [( Il (X)- -
< -(x,z)~n,08 ||T er.e, (X) xx)-X11+ X - 2112] S (1 c.C)mpr.P
X11
(16)
M
E(x, 2)- 1r 1188 X -13] Fxx.2)//..rll/Tu....
-2113
S Ex ((x | price (X) -x1/ + 21|T Mr ...,...... (X) X1 Z11 + ||X
-
C S ( + 22, -2, u. Ma < (1 + Cr,C + 2,202) )
=1+
(17)
where the second last step used Jensen's inequality m p S M Mp Then, we repeatedly apply (16) and (17) together with the triangle inequality and the bound 1 + x0 S et to get
Mp. S MP I (1 + c2 S M exp(2C Σ.= (x) s Ma exp(2Cb,-1) and
Man." -p S P S P I (1 + C) Myo. exw(Cbpp..... (Cb,-1).
8

---

8 Proof of Lemma 4: KSD-Wasserstein bound
Our proof generalizes that of Gorham and Mackey [9, Lem. 18]. Consider any E 7d satisfying |لااا _ Ei= |1 l S 1. From Assumption 2 we know
| - (x,, Ei S mt, [1( - [V - E Ei= Va.g tgllaatr(V Va
(18)
- d|
l= S Endd, and
(19)
VV(V -(x)))1²
= Σ ビコ=1 V
V (1)))(()) S d E 2 Va,
<dΣ _
(v V. DE V., k(a, v) w rzde
Suppose X, Y. Z are distributed so that (X, Y) is I-Wasserstein optimal coupling of (j, v) and Z independent of (X; Y). Since 8p is L-Lipsshitz with [sppp] = (Assumption 1), y is bounded (18), and and V are Lipschitz (19), repeated use of Cauchy-Schwal gives gives
[Tgg]] [Trg] = =EIV (X) - V g()]+ (X)
- -, gXY))
I (x22d + ky L)W (14, + LEI Z11 min(2k1, NY V -
Since our choice of g was arbitrary, the first advertised result now follows from the definition of KSD (Definition 4). The second claim then follows from Cauchy-Schwarz and the inequality min(a, 6)2 ab for a, 2 0, since
- Yl12)] s M. E[min vdljx 112 Y| 2112 min K -
$ pte d /E[|| Y = (H,
=
9 Conclusions and Limitations
In summary, we have proved the first unified convergence bound and rate for finite-particle SVGD, In particular, our results show that with a suitably chosen step size sequence, SVGD with n-particles drives the KSD to zero at an order l/vloo log(n) rate. The assumptions we have made on the target and kernel are mild and strictly weaker than those used in prior work to establish KSD weak convergence control [9, 3, 12, 1]. However, we suspect that, with additional effort, the Lipschitz score assumption (Assumption 1) can be relaxed to accommodate pseudo- "seudo-Lipschin Lipschitz scores as in Erdogdu al. [7] or weakly-smooth scores as Sun al. [24]. A second limitation of this work is that the obtained rate of convergence is quite slow. However, we hope that this initial recipe for explicit, non non-asymptotic convergence will serve as both a template and a catalyst for the field to develop refined upper and lower bounds for SVGD error. To this end, we leave the reader with several open challenges. First, can one establish a non-trivial minimax lower bound for the convergence SVGD? Second, can one identify which types of target distributions lead to worst-case convergence behavior for SVGD? Finally, can one identify commonly met assumptions on the target distribution and kernel under which the guaranteed convergence rate of SVGD can be significantly improved? Promising follow-up work has already begun investigating speed-ups obtainable by focusing on the convergence of finite set of moments [20] by modifying the SVGD algorithm [5].
References
[1] Alessandro Barp, Carl-Johann and convergence with kernel discrepancies. arXiv preprint (tt.::20091123355 2022. 1, 2,
Mark Girolami, and Lester Mackey. Targeted separation
[2] Alain Berlinet and Christine Thomas- Thomas-Agnan. Reproducing kernel Hilbert spaces in probability and statistics. Springer Science & Business Media, 201
3] Wilson Ye Chen, Lester Mackey, Jackson Gorham, François-Xave Briol, and Chris Oates. Stein points.
In International Conference Machine Learning, pages 2018. 2, 9

---

[4] Kacper Chwialkowski, Heiko Strathmann, and Arthur Gretton. A kernel test of goodness of fit. In International Conference on Machine Learning, pages 2606-2615, 2016. 1,3
[5] Aniket Das and Dheeraj Nagaraj. Provably fast finite particle variants of svgd via virtual particle stochastic approximation. arXiv preprint arXiv:2305. 2023."
[6] Andrew Duncan, Nikolas Nüsken, and Lukasz Szpruch. On the geometry of Stein variational gradient descent, arXiv preprint 19X1::992200094 2019.
[7] Murat A. Erdogdu, Lester Mackey, and Ohad Shamir. Global non-convex optimization with discretized diffusions. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada,
pages 1694-97033 2018." 9
[8] Jackson Gorham and Lester Mackey. Mcasuring sample quality with Stein's 's method. In Advances Neural Information Processing Systems, pages 226 204, 2015.
[9] Jackson Gorham and Lester Mackey. Mcasuring sample quality with kernels. International Conference on Machine Learning, pages 1292-1301, 2017. 2, 9,
[10] Jackson Gorham, Anant Raj, and Lester Mackey. Stochastic Stein discrepancies. Advances in Neurul Information Processing Systems, 33:17931-119 117422, 2020. 1,4
[11] Tuomas Haarnoja. Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International Conference Machine Learning, pages 1352-1361, 2017.
[12] Jonathan Huggins and Lester Mackey, Random feature Stein discrepancies. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems, pages 1903-1913. 2018. 2,
[13] Priyank Jaini, Lars Holdijk, and Max Welling. Learning equivariant energy based models with equivariant Stein variational gradient descent. Advances in Neurul Information Processing Systems, 34:16727-16737, 2021. 1
[14] Heishiro Kanagawa, Arthur Gretton, and Lester Mackey, Controlling moments with kernel stein discrepan- cies. arXiv preprint wrXiv:2211.05444 2022.
[15] 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, 2020. 2,
[16] Jing Lei. Convergence and concentration of empirical measures under wasserstein distance in unbounded functional spaces. Bernoulli, 26(1):767-796 2020. 14
[17] Qiang Liu. Stein variational gradient descent as gradient flow. In Advances in Neural Information Processing Systems, pages 31 15111-331 1--3123, 2017. 1,3
[18] Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose Bayesian inference algorithm. Advances in Neural Information Processing Systems, 29:2378-2386, 2016. 1, 3, 13
[19] Qiang Liu, Jason Lee, and Michael Jordan. A kernelized Stein discrepancy for goodness-of- tests. In International Conference on Machine Learning, pages 284,284. 2016. 1,3
[20] Tianle Liu, Promit Ghosal, Krishnakumar Balasubramanian, and Natesh Pillai. Towards understanding the dynamics of gaussian stein variational gradient descent. arXiv preprint arXiv:2305. 14076, 2023, 9
[21] Yang Liu, Prajit Ramachandran, Qiang Liu, and Jian Peng. Stein variational policy gradient. In 33rd Conference on Uncertainty in Artificial Intelligence, 2017.
[22] Adil Salim, Lukang Sun, and Peter Richtarik. A convergence theory for SVGD in the population limit under Talagrand's inequality T1. In International Conference on Machine Learning, pages 19139-19152. PMI.R, 2022. 1, 2,2,35 5,5
[23] Adrien Saumard and Jon A Wellner. Log-concavity and strong log-concavity: a review. Statistics surveys, 8:45, 2014. 3
[24] Lukang Sun. Avetik Karagulyan, and Peter Richtarik. Convergence of Stein variational gradient descent under weaker smoothness condition. arXiv preprint arXiv:2206.00550 2022. 1,9
10

---

[25] Cédric Villani. Optimal trunsport: old and new, volume 338. Springer, 2009. 3
[26] Dilin Wang and Qiang Liu. Learning to draw samples: With application to amortized MLE for generative adversarial learning, arXiv preprint arXiv: 1tfv:6611.000 1.01722,, 2016.
[27] Dilin Wang, Zhe Zeng, and Qiang Liu. Stein variational message passing for continuous graphical models.
In International Conference Machine Learning, pages 5219-5227, 2018.
[28] Jingwei Zhuo, Chang Liu, Jiaxin Shi, Jun Zhu, Ning Chen, and Bo Zhang. Message passing Stein variational gradient descent. In International Conference on Machine I Learning, pages 6018-6027, 2018.

---

A Kernel Assumptions
To show that Assumptions 2 and 3 met by the most commonly used SVGD kernels with constants independent of dimension, we begin by bounding the derivatives of any radial kernel of the form
k(z, - 6[|1 /ll/22 2) with o : R + R four times differentiable. By the reproducing property and Cauchy-Schwarz we have
|k<2,, v) (A(x,, )) k(y, ))xl = || 1l, = 2 o(0),
V V,,, w)ll2 = [a[[llr- - /ll//2)lll ulle.
V,k,,, - 1-d"(1== - vll:/2 v) - v) - 2(1lx - /11.22111
- 10" - v1l/22 || v1l + d0 v1l/22), and
V2 d' - 2x - y)(x - y) T + +'(11= =1l
- <00 - v12. 2) || v1l2 + (0 2
Similarly, the partial derivatives take the form
V k(x,8) d'(1 vll2/2)(23 V3))
8 k(r +'(11= 012/22 [I= 2ll2 221²
V R4 8, k(,,)) = - -o"(1z u11/ 22)z - y.) "01 (11/2)(05 2 - Vs)
I -]22"((1= vl2/2)(xx - v))
-0"(11= - v11 - -1))
Iii + =100" v1l3/2((; ;z; V/)
+ Ii =
2)(x) x2,3 - 20" (I| - v1l222( - 9:))
V., V0 V., k(r,,) < 10]lz--11jp >11l/2)(( - y:)² + o (|æ -21//2)
= (1|xr /22/ -x,) 2,)) 11)2
+ + vl1 -2,))
+I = >1 (||= (01//2)(0 x2,²² + 66= y112/2((x xx)
+ 20x( - v2l
x² ([|o vll./2 (1f/2)((xx; v1)² (xz v5)9) + 0" ((| yll/22
+ """ (| - v112/2) 2) -x,) =z)((z, - v1)²
+ I "1(10"((11 2112/2((1 =x:²² + +20 v11/22))
so that both [k(x, 8) and
D4 V. V,, u, V.
+ 1Ii -0)20
are bounded (Assumption 2) by constants independent of dimension.
Gorham and Mackey [9] popularized the use of IMQ kernels for SVGD, by establishing the convergence -ettrmming properties of the associated KSD. The corresponding ø satisfies
<(t) (c² + +1) for <> O and | E (-1,0),
d'(t) 23((2 + 21) and d²(t) = 4,8B8 1)(c² + 22)8-22
In this case, V,ke,, v) Ilop and V2 v) are bounded (Assumption 2) by constants inde- pendent of dimension as
((< v11/221 223(c² + || v11)
< 223 min ||0 y
112 28 28-2 2) < 2232282 and
(0" /
21122 = 4 1) + | v12 3-2 - v112
S 4/3 - () + | v13)a s $43(3 - 1)628-2
For [,, 122 consider two cases:
12

---

When 2 - vll2 2 1,
10 /22/22]11 x - vll2 S -2 u1l2 0128--2 2|x -yll2 -223| - u112 2/121-1
I -23/| 2ll2 I -23.
When | 8||2 < 1, |0' u15--112. /11//2|||== yll2 < l0' -
Therefore, V (x, 2 is also bounded (Assumption 2) by constants independent of dimension, and Assumption 3 holds with 7 = -23.
The original SVGD paper [18] used Gaussian kernels in all experiments, and they remain perhaps the most common choice in the literature. In this case, & satisfies
((t)
22at 2at for > O, ('(t) -2x 2nd -2xx(()) and (²) (a²
e-
Using the incquality e-- find that
16' 01|1 - y 2 = 20r - v0 & min(2a, 2/(e|l - yll)) and
lo" (I= / 22 | ق|ا 4a c - wll o v12 - 4a/e
so that V, y) 1opp V2k(2, y) llop and V y) 2|ا are bounded (Assumption 2) by con- stants independent of dimension, and Assumption 3 holds with y 2/c.
B Proof of Corollary 2: A finite-partich convergence rate for SVGD
We begin by establishing a lower bound on - Let
6 B.B.o ( o Wo n. ). 81) and 618) B. o(wo, A 2C,
so that b,-1 min(b (1 ) Since 31, 32, (wo,n) 2 1, we have
81 = max(1, _ log( B (log
A)))
Wa.n Vl(@o.))
< max(1, _/2 log( 1 (log
B
Ba.n / Vo(
- ))) and max(1, _ log( # (log
Wo,.. 82 max(1, + log( $ (log To Bann ((
- A A- 2(1)
< max(1, _/2 log( B (log "o. 1))
S max(1, A log( + (log ))))))
Hence, (( 2 1 implies that
1 log( 1 log ma nu /ocoonn
-A))
C
B max log B (log
log w otwo.nt
j/ log( $ mlx 1 log( (log wo. 1))
- and
(20)
(2) 2 a log B max log( + (log
log mo.. di
A - 2C))..
We divide the remainder of proof into four parts. First prove each of the two cases in the generic KSD bound (7) in Appendices B.1 and B.2. Next we show in Appendix B.3 that these two cases yield the generic convergence rate (8). Finally, prove the high probability upper estimate (9) for Wp,n under i.i.d. initialization in Appendix B.4.
B.1
Case 6, =
In this case, the error bound (7) follows directly from Theorem 3.
13

---

B.2
Case b > 0
We first state and prove a useful lemma.
Lemma 6, Suppose x (B) for non-increasing function f R - R and 3 max(1, f(1). Then x S 3 and x I f(x).
Proof. Because f is non-increasing and [3 2 x, ((3) f(1) S 3 Since S and f is non-increasing, we further have f(x) 2 f(5) = x: as advertised.
Since B.C is non-increasing in its third argument, Lemma implies that 6/ S 31 and
(I) S n (w / (.) A, 1,1 b
Rearranging the terms and noting that
B < log
-A b/
log
A
uo ((
V (()o,))
since 6 2 bb-1 > O, we have
wn exp(t (exp(C((())) S (
(21)
Similarly, we have 1,21 S BB.C Wo, log log mo... A 2Ō, 1,3) and
Wu,n exp(b, (2) (2C A+ B exp ( (2) ())
(22)
Since 1--1 = min the inequalities (21) and (22) are also satisfied when by is substituted
for ((2) and ( Since the error term ax-1 (4) non-decreasing in each of (wo,m: A, B, C),, we have
a--1 S (K1 + a2d + +ndd 1/d L 22 ((woo..
Since bi-1 min(b,2), (2) ) the claim (7) follows from this estimate, the lower bounds (20), and Theorem 3.
B.3
Generic convergence rate
The generic convergence rate (8) holds as, by the lower bounds (20), bi = min(t > 0 whenever
(B+A+22) Wo Cl (w),)) and D(B+A+20)/C
( (B
condition which occurs whenever th,n is sufficiently small since the right-hand hand side of each inequality converges to zero as Wø O.
B.4 Initializing with i.i.d. particles
We begin by restating an expected Wasserstein bound due to Lei [16].
Lemma (Lei [16, Thm. 3.1]). Suppose pă + Er 8r, for vs us ne with Mag & Rng [11-12]]
0o. Then, for a universal constant c > 0,
ldg(
B[ (Mū po < cM n1/(2vd)
Together, Lemma 7 and Markov's inequality imply that
log(n) Hid-2)
Wi(48, < E[W (Aū n (c(())) S Mag with probability at least - cδ, proving the high probability upper estimate (9).
n//evv /8
14


Reviews:
[{"review_id": "oJrDFNeRVQ", "reviewer": "Reviewer_g2wP", "summary": "This work studies the non-asymptotic convergence rate of Stein variational gradient descent (SVGD), an algorithm for approximating a target probability distribution with a collection of particles. This work presents a finite-particle convergence rate for SVGD, which provides a measure of how quickly the algorithm converges to the target distribution with a finite number of particles. The convergence rate formula drives the kernel Stein discrepancy to zero at an order 1/√log log n rate, but the authors suspect that the dependence on n can be improved and hope that their proof strategy will serve as a template for future refinements.\n", "questions": "I am at an educative level but quite enjoy reading on this topic. I quite like the generic / infinite-particle continuum manner SVGD Algorithm 2 is written instead of the $n$-particle SVGD Algorithm 1. I wondered if this continuous-time approximation is the critical reason for the success of the non-asymptotic rate first established by the authors.", "limitations": "This paper contributes as a theoretical work and does not raise negative social impacts.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This work provides the first finite-particle convergence rate for Stein variational gradient descent (SVGD), which is a popular algorithm for approximating a probability distribution with a collection of particles. This work presents an explicit, non-asymptotic proof strategy for the convergence rate formula --- which drives the kernel Stein discrepancy to zero at an order $1/\\sqrt{\\log \\log n}$ rate providing a measure of how quickly the algorithm converges to the target distribution with a finite $n$ particles. Prior to this work, relatively little is known about SVGD's non-asymptotic approximation quality, despite that SVGD has demonstrated promising results for various inferential tasks. The authors also claims that it serves as a template for future refinements to improve the dependence on $n$. I highly believe in this, due to the soundness of technical tools the work adopted.\n\nThe authors provide a thorough discussion of the assumptions and conditions required for the convergence rate formula to hold, which helps to clarify the limitations and applicability of the formula. Finally, this work also includes a comprehensive list of references to related work, which provides a useful starting point for further research on SVGD and related algorithms.", "weaknesses": "Despite its success in providing the first non-asymptotic convergence rate, this work assumes a level of familiarity with the mathematical concepts and notation for experts, which may make it difficult for readers without a strong background in probability theory and optimization to follow. In addition, this work does not provide any experimental results or comparisons with other algorithms to demonstrate the practical usefulness of the convergence rate formula, and does not provide any specific information on how the dependence on $n$ can be improved, which may limit its usefulness for researchers looking to optimize the performance of SVGD. Lastly, this work focuses exclusively on SVGD and does not provide any insights or comparisons with other algorithms for approximating probability distributions, which may limit its broader relevance to the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback. We are pleased that the reviewer found our technical tools sound, our discussion of assumptions thorough, and also shared our vision for future refinements. Below is our detailed response:\n\n### Assumed familiarity of optimization/probability theory concepts and notations\nThank you for this feedback. We endeavor to make the final version maximally accessible, with all notation and concepts defined in Section 2. If there are particular concepts that the reviewer finds unclear, please let us know!\n\n### Experimental results and comparisons with other algorithms\nThe main focus of our work was not to propose a new algorithm or even to advocate for SVGD over alternative algorithms but rather to address the longstanding open question of whether a  unified convergence bound for finite-particle SVGD could be derived. As such, we believe that an experimental comparison with other algorithms would be out of scope in this work. There are however many empirical comparisons of SVGD with other algorithms in the cited literature, and, in the introduction, we do compare our theoretical result with prior work (including Liu [16], Gorham et al. [9], Korba et al. [14], and Salim et al. [20]) that studies the convergence of SVGD without providing unified convergence bounds or rates.\n\n### How the dependence on n can be improved\nPlease see our response to questions shared by the reviewers. \n\n### This work focuses only on SVGD.\n\nThank you for highlighting this opportunity to further contextualize our work. While the focus of this work is wholly on solving the open problem of establishing any unified convergence bound for finite-particle SVGD and we believe this initial rate will be improved in the future, we will better contextualize the initial rate and highlight what may be achievable in the future by comparing to other algorithms for approximating probability distributions. For example, MCMC methods like the unadjusted Langevin algorithm admit a much faster rate (see, e.g., the polynomial rate bounds of Balasubramanian et al. (2022)). However, as agreed upon by the reviewer and other reviewers (igw1,awG8), this work is still a “significant technical leap” to achieve the first non-asymptotic convergence rate for SVGD. We will also discuss a promising follow-up to this work by an independent research group (for anonymity reasons we omit the citation here) that has already begun investigating improved rates by modifying the SVGD algorithm. \n\nOur analysis also provides a template for studying convergence rates for SVGD-like algorithms. For example, Shi et al. (2021) proposed SVGD-like methods for sampling in constrained domains. However, their convergence analysis lacks a unified bound and rate. We could apply similar proof techniques in this submission to obtain a convergence rate for their algorithm. \n\nReference: \n* Balasubramanian, K., Chewi, S., Erdogdu, M. A., Salim, A., & Zhang, S. (2022). Towards a theory of non-log-concave sampling: first-order stationarity guarantees for langevin monte carlo. In Conference on Learning Theory (pp. 2896-2923).\n* Shi, J., Liu, C., & Mackey, L. (2021). Sampling with mirrored Stein operators. arXiv preprint arXiv:2106.12506.\n\n### The role of infinite-particle continuum manner SVGD\nWe appreciate your positive response to how we present the continuous SVGD. The formulation in Algorithm 2 is indeed critical to our analysis. Our proof relies on an error bound for the continuous SVGD established by Corollary 1 and uses a discretization error bound (Theorem 2) to relate the continuous SVGD to n-particle SVGD. \n"}, {"review_id": "UiXA0zbqRH", "reviewer": "Reviewer_igw1", "summary": "The authors provide the first convergence guarantee for finite particle Stein Variational Gradient Descent (SVGD). Although I am not an expert on this topic, I believe this problem remained open for a long time, and it should be the first of many finite particle results to come. \n\nWhile $(\\log\\log n)^{-1/2}$ is a fairly slow rate, I believe we should overlook the rate, but consider the significance of the technical leap taken by the authors to achieve a finite particle result at all. For this reason, I will recommend accept fro this paper. ", "questions": "Given that I am not an expert on this subject, I would like the authors to clarify a couple of questions for me. \n\n1. What was the main conceptual challenge in establishing a finite particle guarantee, and how did this work overcome it? For me Theorem 3 reads like a bit of magic, and the desired result just appears without much intuition. I would like to understand how this came to be. \n\n2. What do the authors perceive as the next challenge preventing improvements to this result? Similar to the previous question, I don't quite see on an intuitive level where the $log log n$ dependence came about, which the authors also believe can be improved. I would appreciate the authors can elaborate further on this topic. ", "limitations": "N/A", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. This is the first finite particle convergence guarantee for SVGD. \n2. The contents are well organized and presented. \n3. The proof is concise and clean. ", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback. We are glad that you found our contribution significant, our work well presented, and our proof concise and clean. We provide responses to the detailed comments below.\n\n### Main conceptual challenge in establishing a finite particle guarantee, and how this work overcomes it.\nSVGD is originally derived from finding descent directions of KL divergence between an approximation and the target distribution. Most prior convergence analyses [16,14,20] heavily rely on this KL-descent property, which ultimately yields a bound on KSD error but is only applicable to continuous SVGD because KL divergence is ill-defined between the n-particle discrete approximation and the continuous target distribution. Our work overcomes the difficulty, by explicitly controlling the 1-Wasserstein distance between the continuous and n-particle SVGD through a discretization error bound (a key challenge in deriving the explicit Theorem 1 was that the Wasserstein pseudo-Lipschitz constant of SVGD itself depends on the moment growth of the measures being compared, so our proof carefully tracks this growth in tandem with the discretization error) and, unlike [9], translating the resulting Wasserstein error into KSD error to enable its combination with convergence results for continuous SVGD.\n\n### Intuition behind Theorem 3\nWe will clarify that the aim of Theorem 3 is to combine Theorem 2 (the error of using n-particle SVGD to approximate continuous SVGD) and Corollary 1 (the error bound of continuous SVGD) into an error bound of n-particle SVGD. Since both bounds are formulated with the KSD metric, we used the triangle inequality of KSD to prove the result. \n\n### The next challenge preventing improvements to this result; where the $\\\\log \\\\log n$ dependence came about\nPlease see our response to questions shared by the reviewers. \n"}, {"review_id": "VG9XGhaZVi", "reviewer": "Reviewer_bq3E", "summary": "In this work, the authors present a novel analysis of finite-particle Stein Variational Gradient Descent (SVGD) and derive a unified convergence bound for this algorithm. The convergence bound provides an explicit measure of how close the finite-particle SVGD algorithm gets to its target. To establish this convergence bound, the authors first introduce a bound on the discretization error of the 1-Wasserstein distance between the finite-particle and continuous SVGD. They make certain assumptions that are commonly satisfied in SVGD applications and compatible with Kernelized Stein Discrepancy (KSD) weak convergence control. \n\nOverall, this work contributes to the understanding of finite-particle SVGD and provides a unified convergence bound that quantifies the algorithm's convergence to its target. The derived bounds enable better control and evaluation of the accuracy of finite-particle SVGD in practical applications.", "questions": "None.", "limitations": "None.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The strengths are:\n* The authors have proved the first unified convergence bound and rate for finite-particle SVGD.\n* They show that SVGD with n-particles drives the KSD to zero at an order $1/ \\sqrt{\\log\\log(n)}$ rate.", "weaknesses": "In my perspective, this paper would be more suitable for an optimization journal, as it would provide an environment where the technical contributions of the study can undergo a more comprehensive evaluation through an extended rebuttal cycle. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging our contributions and for the feedback. We respond to the comment about suitable venues below. \n\n### Optimization journal vs. NeurIPS\nWe firmly believe that NeurIPS is an ideal venue for this work, as the original SVGD algorithm and analysis were published at NeurIPS [17], the bulk of all subsequent analyses were published at NeurIPS or ICML [16,9,14,20,25], and SVGD has since gained widespread use in the machine learning community in particular.  We thus believe that this work will be of the greatest interest and relevance to the NeurIPS community. \n"}, {"review_id": "EfrlxruMl0", "reviewer": "Reviewer_awG8", "summary": "This paper provides an analysis of the convergence rate of finite-sample Stein Variational Gradient Descent (SVGD) for sub-Gaussian targets with Lipschitz scores. In contrast to previous works such as Liu 2017, Duncan et al. 2019 and Korba et al. 2020, the presented results offer convergence guarantees that hold for finite samples and rely on weaker assumptions. The authors present two key results regarding the discretization error of finite-sample SVGD compared to infinite-sample SVGD, measured in terms of Wasserstein (Theorem 1) and KSD (Theorem 2), respectively. These results are then combined to establish a finite-sample bound on the KSD error between a finite-sample approximation and the target distribution (Theorem 3). By carefully selecting step sizes, the authors demonstrate that this error decays at a rate of $1 / \\sqrt{\\log \\log n}$ (Corollary 2).", "questions": "1. There are a few places that say “the Algorithm 2 outputs $\\mu_r^n = SVGD(\\mu_0^n, r)$…”, e.g. L166. Since this output is based on a discrete measure $\\mu_0^n$, should it be “the **Algorithm 1** outputs …” instead?\n2. COuld you elaborate on the suggested step size scheme in Corollary 2? Specifically, what is the dependence on the sample size $n$ and on the dimension $d$? How easy is it to construct the upper bounds $(\\overline{w}_{0, n}, \\overline{A}, \\overline{B}, \\overline{C})$ in practice?\n3. As also mentioned in the paper, the established rate $1 / \\sqrt{\\log \\log n}$ is very slow. Could you provide some insights into which parts of the proof strategy could possibly have led to this slow rate? Is the bound (3) tight? How does this convergence rate compare with empirical performance in numerical simulations?", "limitations": "The assumptions on the target distribution, its score function and the positive definite kernel are summarised in Section 2, accompanied by interpretations and discussions on their connections to related literature. Limitations are also discussed in Section 9. Overall, I think the discussions on assumptions and limitations are adequately covered. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Quality**: This paper provides a rigorous study of the convergence of finite-sample SVGD and delivers clear and well-supported results. The main findings (Theorem 1, 2, 3) build upon existing results (Lemma 1 and 4) but require sophisticated combinations and detailed arguments. The authors provide extensive discussions and overview the proof strategy, which appears reasonable and comprehensive (although I did not examine the proofs in depth).\n\n**Novelty**: This paper offers a crucial contribution by bridging the gap between the existing convergence guarantees of infinite-sample SVGD and the practical implementation of finite-sample approximations, which is currently lacking in the literature. Whilst the established convergence rate is slow, this work stands out as the first to provide an explicit, non-asymptotic guarantee for SVGD approximations under reasonably mild assumptions on the target distribution. This, in my view, is the primary novelty and significance of this paper.\n\n**Clarity**: The paper demonstrates clear motivation and objectives. Despite the technical nature of the content, the exposition is highly comprehensible. The intuitive explanations and remarks provided before and after each main theorem are particularly valuable in aiding understanding.", "weaknesses": "**Slow convergence rate**: As mentioned above and in the paper, the established rate $1 / \\sqrt{\\log \\log n}$  is notably slow, suggesting that the bound (3) is likely to be very loose. Although the authors acknowledge the potential of the presented proof strategy as a starting point for refining the bounds, it is not entirely clear whether or not or how the proof could be adapted to achieve an improved bound. Including discussions on potential avenues for enhancing the convergence rate would be valuable and insightful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback. We are pleased that the reviewer found our proof strategy reasonable, our contribution crucial, and our exposition comprehensive. We respond to the detailed comments below.\n\n### “the Algorithm 2 outputs …”, e.g. L166 \nThank you for pointing that out! Indeed, it should be Algorithm 1.\n\n### “Could you elaborate on the suggested step size scheme in Corollary 2?”\n\nThe step size scheme is constructed such that the two terms in the unified error bound (Theorem 3) balance with each other as there is a tradeoff between them—the discretization error bound (i.e., $a_{t-1}$) grows with the step size sum while the continuous SVGD error decreases proportional to it. The optimal step size sum is \n\n$O(\\\\log\\\\log(e^e+\\\\frac{1}{ \\\\bar{w}_{0,n} })),$\n\nand after plugging in the upper bound in eq. (9): \n\n$O(\\\\log\\\\log(e^e + \\\\frac{ \\\\delta n^{1/(2\\\\vee d)} }{ M_{\\\\mu_0^{\\\\infty}}\\\\log(n)^{\\\\mathbf{1}[d=2]} }) ).$ \n\nAs is used above, an upper bound for $w_{0,n}$ is given in eq. (9).\nTo get upper bounds $\\\\bar{A}, \\\\bar{B}, \\\\bar{C}$ it suffices to produce the following upper bounds:\n* Kernel constant upper bounds: $\\\\kappa_1, \\\\kappa_2, \\\\gamma$. These are straightforward to compute explicitly, and we have provided these values in Appendix A for Gaussian and IMQ kernels.\n* Lipschitz constant of the score upper bound: This can be derived from the observable score function (which does not require knowledge of the normalizing constant of the target density) and is a standard input to score-based distributional approximation like Langevin Monte Carlo.\n* Moment upper bounds: It suffices to provide any upper bound on $\\\\mathbb{E}_{P}[\\\\|\\\\cdot\\\\|_2]$ as \n\n$m_{P, x^*} \\\\leq \\\\|x^*\\\\|_2 +  \\\\mathbb{E}_P [\\\\|\\\\cdot\\\\|_2],$ \n\n$m_{\\\\mu_0, x^*} \\\\leq \\\\mathbb{E}_{\\\\mu_0}[\\\\|\\\\cdot\\\\|_2] +  \\\\mathbb{E}_P [\\\\|\\\\cdot\\\\|_2],$  \n\ncan $x^*$ be identified efficiently by running gradient ascent to find a stationary point, and $\\\\mathbb{E}_{\\\\mu_0}[\\\\|\\\\cdot\\\\|_2]$ can be numerically estimated. \n\n### Is the bound (3) tight? How does this convergence rate compare with empirical performance in numerical simulations?\n\nWe believe the first part of the bound ($a_{t-1}$) can be further improved (please see our response to questions shared by the reviewers for detailed reasons) and as suggested in the submission we expect our worst case rate (which holds for any initialization and a broad class of target distributions and step size sequences) to be slower than the true convergence rate observed in practice for many distributions, initializations, and step size settings. We believe that developing a non-trivial lower bound for SVGD performance to assess tightness is an important open question.\n"}]

Author rebuttal:
# Response to questions shared by Reviewer g2wP, igw1, and awG8:

### Source of $n$ dependence, potential avenues for rate improvement, and challenges involved.
The unified error bound of Theorem 3 reveals that the dependence on n arises from the tradeoff between the KSD discretization error bound ($a_{t-1}$), which grows double exponentially as the step size sum $b_{t-1}$ increases, and the infinite-particle SVGD error, which decreases proportionally to $\sqrt{b_{t-1}}$. The $\log\log n$ dependence is mainly caused by the double exponential growth of $a_{t-1}$, which can be traced back to Theorem 1. A key challenge in deriving the explicit Theorem 1 was that the Wasserstein pseudo-Lipschitz constant of SVGD itself depends on the moment growth of the measures being compared, so our proof carefully tracks this growth in tandem with the discretization error.  Any improvement in this discretization error bound growth rate would translate immediately into an improved approximation error rate for SVGD.  Moreover, one may be able to derive tighter bounds by analyzing the discretization error of KSD directly or by using an alternative intermediate metric in place of the 1-Wasserstein distance; finding the right metric that simultaneously remains small across the SVGD trajectory and is tractable to analyze is the main challenge.  

Alternatively, instead of measuring convergence to an arbitrary sub-Gaussian target with respect to a large non-parametric measure like KSD, one could focus on the convergence of a more restricted set of moments (like means and variances) or a more restricted set of targets.  Our submission has already stimulated promising follow-up work (we have withheld the title and reference to preserve anonymity, but please let us know if we should reveal it) from an independent research group demonstrating rate improvements when the function class is more restricted and the target is Gaussian or strongly log concave.  Since the posting of our preprint on arXiv, another independent research group has built upon our work to show that a variant of SVGD converges at a much faster O(1/poly(n)) rate.  We will highlight these avenues for improvement and cite these follow-up works in the revision.


Meta-review: Most of the reviewers deem the paper interesting. Please revise the paper and make it more readable for the machine learning audience.
Decision: Accept (poster)