Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation
Authors: Aniket Das
Dheeraj Mysore Nagaraj
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Stein Variational Gradient Descent
Variational Inference
Sampling
TL;DR: Novel, computationally efficient variants of SVGD that exhibit provably fast convergence in the finite-particle regime..

Abstract: Stein Variational Gradient Descent (SVGD) is a popular particle-based variational inference algorithm with impressive empirical performance across various domains. Although the population (i.e, infinite-particle) limit dynamics of SVGD is well characterized, its behavior in the finite-particle regime is far less understood. To this end, our work introduces the notion of *virtual particles* to develop novel stochastic approximations of population-limit SVGD dynamics in the space of probability measures, that are exactly realizable using finite particles. As a result, we design two computationally efficient variants of SVGD, namely VP-SVGD and GB-SVGD, with provably fast finite-particle convergence rates. Our algorithms can be viewed as specific random-batch approximations of SVGD, which are computationally more efficient than ordinary SVGD. We show that the $n$ particles output by VP-SVGD and GB-SVGD, run for $T$ steps with batch-size $K$, are at-least as good as i.i.d samples from a distribution whose Kernel Stein Discrepancy to the target is at most $O(\tfrac{d^{1/3}}{(KT)^{1/6}})$ under standard assumptions. Our results also hold under a mild growth condition on the potential function, which is much weaker than the isoperimetric (e.g. Poincare Inequality) or information-transport conditions (e.g. Talagrand's Inequality $\mathsf{T}_1$) generally considered in prior works. As a corollary, we analyze the convergence of the empirical measure (of the particles output by VP-SVGD and GB-SVGD) to the target distribution and demonstrate a **double exponential improvement** over the best known finite-particle analysis of SVGD. Beyond this, our results present the **first known oracle complexities for this setting with polynomial dimension dependence**, thereby completely eliminating the curse of dimensionality exhibited by previously known finite-particle rates.

Provably Fast Finite Particle Variants of SVGD via
Virtual Particle Stochastic Approximation
Aniket Das Google Research Bangalore, India ketddgoogle. com
Dheeraj Nagaraj
Google Research
Bangalore, India
Abstract
Stein Variational Gradient Descent (SVGD) is popular particle-based variational inference algorithm with impressive empirical performance across various domains. Although the population (i.e, infinite-partie parttcle limit dynamics of SVGD is well characterized, its behavior in the fnite-partich regime is far less understood. To this end, our work introduces the notion of virtual particles to develop novel stochastic approximations of population-limit SVGD dynamics in the space of probability measures, that are exactly realizable using finite particles. As a result, we design two computationally efficient variants SVGD, namely VP-SVGD and GB-SVGD, with provably fast mautee-article convergence rates. Our algorithms can be viewed as specific random-batch approximations of SVGD, which are computationally more efficient than ordinary SVGD. We show that the n particles output by VP-SVGD and GB-SVGD, run for T steps with batch-size K, are at- least as good as i.i.d samples from a distribution whose Kernel Stein Discrepancy to the target is at most O(d""//(<T)// under standard assumptions. Our results also hold under mild growth condition on the potential function, which is much weaker than the isoperimetric (c.g. Poincare Inequality) or conditions (e.g. Talagrand's 's Inequality T1) generally considered in prior works. As a corollary. we analyze the convergence of the empirical measure (of the particles output by VP-SVGD and GB-SVGD) to the target distribution and demonstrate a double exponential improvement over the best known finite- inite-particle analysis of SVGD. Beyond this, our results present the first known oracle complexities for this setting with polynomial dimension dependence, thereby completely eliminating the curse of dimensionality exhibited by previously known finite-particle rates.
Introduction
Sampling from a distribution over Rdd whose density 7 (x) exp(-F'(x)) is known only upto
normalizing constant, is a fundamental problem in machine learning [52] 20 statistics [1 36).
theoretical computer science (28 17 and statistical physics (39 15 A popular approach this
the Stein Variational Gradient Descent (SVGD) algorithm introduced by Liu and Wang [iI, which
uses positive definite kernel l to evolve a of interacting particles ie[mi,AEN as follows:
(
Σ
k(x)
(1) (FF(F()))
(2k(x) x())]
(I)
SVGD exhibits remarkable empirical performance in variety of Bayesian inference, generative
modeling and reinforcement learning tasks [31] [1] 54 22 50
19 and usually converges
rapidly to the target density while using only few particles, often outperforming Markov Chain Monte Carlo (MCMC) methods. However, in contrast to its wide practical applicability, theoretical
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

analysis of the behavior SVGD is relatively unexplored problem. Prior works on the analysis mainly consider the population limit, where the number of particles + co. These works assume that the initial distribution of the (infinite number of) particles has a finite KI. divergence to the target x and subsequently, interpret the dynamics of population- SVGD as projected gradient descent updates for the KL. divergence on the space of probability measures, equipped with the Wasserstein geometry. Under appropriate assumptions on the target density, one can then use the theory of Wasserstein Gradient Flows to establish non-asymptotic (in time) convergence of population-ling
of SVGD 26 30 42 7
SVGD to π in the Kernel Stein Discrepancy (KSD) metric.
While the framework of Wasserstein Gradient Flows suffices to explain the behavior of SVGD in the population limit, the same techniques are insufficient effectively analyze SVGD in the umite-particle regime. This is primarily due to the fact that the empirical measure ja(m) of finite number of particles does not admit a density with respect to the Lebesgue measure, and thus, its KL divergence to the target is always infinite (i.e. KL (f(") = oo). In such a setting, a direct analysis of the dynamics of finite-po maaite-prttile SVGD becomes prohibitively difficult due to complex inter-partich dependencies. To the best of our knowledge, the pioneering work of Shi and Mackey [43] is the only result that obtains an explicit convergence rate of finite-particle SVGD by tracking the deviation between the law of nt-aarticl SVGD and that of its population-limit. To this end, Shi and Mackey
4 show that
for subgaussian target densities, the empirical measure of r--article SVGD converges to x a rate
of O(
poly(d) Tog log w in KSD The obtained convergence rate is quite slow and fails to adequately explain the impressive practical performance of SVGD.
Our work takes starkly different approach to this problem and deliberately deviates from tracking population-limit SVGD using a finite number of particles. Instead, we directly analyze the dynamics of KL divergence along carcfully constructed trajectory in the space of distributions. To this end, our proposed algorithm, Virtual Particle SVGD (VP-SVGD) devises an unbiased stochastic approximation (in the space of measures) of the population- limit dynamics of SVGD. We achieve this by considering additional particles called virtual particles 3 which evolve in time but aren't part of the output (i.e. real particles). These virtual particles are used only compute information about the current population-leve level distribution of the real particles, and enable exact implementation of our stochastic approximation to population-linge SVGD, while using only a finite number of partieles.
Our analysis is similar in spirit to non-asymptotic analyses of stochastic gradient descent (SGD) that generally do not attempt to track gradient descent (analogous to population-limit SVGD in this case). but instead directly track the evolution of the objective function along the SGD trajectory using appropriate stochastic descent lemmas 24 II] The key feature of our proposed stochastic approximation is the fact that it can be implemented using only a finite number of particles. This allows us design faster variants of SVGD with provably fast finite-partichs convergence.
1.1 Contributions
VP-SVGD and GB-SVGD We propose two variants of SVGD that enjoy provably fast finite- marteeparticle convergence guarantees to the target distribution: Virtual Partiele SVGD (VP-SVGD in Algorithm| I and Global Batch SVGD (GB-SV SVGD in Algorithm 2}. VP-SVGD is a conceptually elegant stochastic approximation (in the space of probability measures) of population- SVGD, and GB-SVGD is practically efficient version of SVGD which achieves good empirical performance. Our analysis of GB-SVGD builds upon that of VP-SVGD. When the potential F is smooth and satisfies a quadratic growth condition (which holds under subgaussianity of πτ" a common assumption in prior works 42 43) ). we show that the n particles output by T' steps of our algorithms, run with batch-size K, are at least as good as i.i.d draws from a distribution whose Kernel Stein Discrepancy to π² is at most ((a/9//Kr)>/>> Our results also hold under a mild subquadratic growth condition for F, which is much weaker than isoperimetric (c.g. Poincare Inequality) or information transsoorttt (c.g. Talagrand's 2
Inqquality T1) assumptions generally considered in the sampling literature 47
State-of-the-art Finite Particle Guarantees As corollaries of the above result, we establish that VP-SVGD and GB-SVGD exhibit the best known finite-particle guarantees in the literature which significantly outperform that of prior works. Our results are summarized in Table I In particular,
We explicate the dimension dependence in Shi and Mackey + (roughlyy analogous to virtual particles in quantum field theory that enable interactions between real particles
by closely following their analysis

---

Oracle Complexity
Result
Algorithm
Assumption
Rate
Population Limit
Unitornly Bounded
Not
Korba et al. 26
SVGD
KSD, (Mell=*)
polyid)
Implementable
Population Limit
Not
d
Salim et al.
42
SVGD
Sub gabb-gassian n²*
Implementable
VT
Shi and Mackey
43
SVGD
Sub-gaussian n²*
poly(d)
poly(d) g (d
Vlog log wo(
Ours, Corollary
VP-SVGD
Sub-gaussian T²'
(4/n) M+ (4/x)
41/20
Ours, Corollary
GB-SVGD
Sub-gaussian n²*
d //2// + (4/a)
6/22
Ours, Corollary
VP-SVGD
Sub-exponential
1/aa
2/20
n//o n
Ours, Corollary
GB-SVGD
Sub-exponential
6/20
Comparison of our results with prior works. d, T, and n denote the dimension, no. of iterations and of output particles respectively. Oracle Complexity denotes number of evaluations of VF needed to achieve KSD,, (-||TT) S e and Rate denotes convergence rate w.r.t KSD metric. Note that: 1. Population Limit SVGD is not implementable as it requires infinite particles 2. The uniformly bounded KSD=* [[r'' assumption cannot be verified apriori and is much stronger than
Table I:
subgaussianity (see 42 Lemma C.1)
under subgaussianity of the target distribution '²' show that the empirical measure of the particles output by VP-SVGD converges to x* in KSD at rate of O((%)))* (4))) Similarly, the empirical measure of the n output particles of GB-SVGD converges to n at a KSD rate of 0d + (2) Both these results represent a double exponential improvement over the 00 poly(d)
Vlog log ( KSD rate of n-particle SVGD obtained by Shi and Mackey 43 which, to our
knowledge, is the best known prior result for SVGD in the finite particle regime. When benchmarked in terms of gradient oracle complexity, i.e., the number of evaluations of F required by an algorithm to achieve KSD,- x. (-I|=*) S 6, we demonstrate that for subgaussian '², the oracle complexity of VP-SVGD is (2)) while that of GB-SVGD is (dd"ee") To the best of our knowledge, our result presents the first known oracle complexity guarantee with polynomial dimension dependence, and consequently, does not suffer from a curse of dimensionality unlike prior works. Furthermore, as discused above, the conditions under which our result holds far weaker than subgaussianity of x², and as such, includes sub-exponential targets and beyond. In particular, our guarantees for sub-exponential target distributions are (to the best of our knowledge) the first of its kind.
Computational Benefits: VP-SVGD and GB-SVGD can be viewed as specific random batch approx- imations SVGD. Our experiments (Section 8 show that GB-SVGD obtains similar performance as SVGD but requires fewer computations. In this context, different kind of random batch method that divides the particles into random subsets of interacting particles, has been proposed by Li et al. [29]. However, the objective in Li et al. [29 is to approximate maite-particle SVGD dynamics using the random batch method, instead of analyzing convergence of the random batch method itself. Beyond this, their guarantees also suffer from an exponential dependence on the time T. As explained below, their approach is also conceptually different from our method since we use the same random batch to evolve every particle, allowing to interpret this as a stochastic approximation in the space of distributions instead of in the path space.
1.2 Technical Challenges
We resolve the following important conceptual challenges, which may be of independent interest.
Stochastic Approximation in the Space of Probability Measures Stochastic approximations are widely used in optimization, control and sampling (27 52 23 In the context of sampling,
stochastic approximations are generally implemented in path space. e.g., Stochastic Gradient Langevin
Dynamics (SGLD) [52) takes random batch approximation of the drift term via the update X v E,) + /2nE,, E (N I) where [x] {,)|x,] F(x:). Such stochastic
X; x Ej=o K-1
approximations are then analyzed using the theory of stochastic processes over Rdd 12 55 25
However, when viewed in the space of probability measures (i.e, μ4 = Law(x;)) the time-evolution

---

of these algorithms is deterministic. In contrast, our approach designs stochastic approximations in the space of probability measures. In particular, the time-evolution of the law of any particle in VP-SVGD and GB-SVGD are a stochastic approximation of the dynamics of population-lin limi SVGD. We ensure that requires only a finite number of particles for exact implementation.
Tracking KL Divergence in the Finite-Particle Regime The population limit (n + oc) ensures that the initial empirical distribution (fo) of SVGD admits density (w.r.t the Lebesgue measure). When the KL divergence between ol and x² is finite, prior works on population-limit SVGD analyze the time-evolution of the KL divergence to πτ. However, this approach cannot be directly used to analyze tiite-partich SVGD since the empirical distribution of finite number of particles does not admit a density, and thus its KL divergence to π infinite. Our analysis of VP-SVGD and GB-SVGD circumvents this obstacle by considering the dynamics of an infinite number of particles, whose empirical measure then admits a density. However, the careful design ensures that the dynamics of n of these particles can be computed exactly, using only a finite total number of (real + virtual) particles. When conditioned on the virtual particles, these particles are i.i.d. and their conditional law is close to the target distribution with high probability.
2 Notation and Problem Setup
We use || ||. (+--) denote the Euclidean norm and inner product over RA respectively, All other norms and inner products are subscripted to indicate their underlying space. Pa denotes the space of probability measures on Rd with finite second moment, with the Wasserstein-2 metric denoted as W2 (p. for μ. V/ E (R For any two probability measures j4, 2, we denote their KL divergence as KL (ellz). For any function f X + Y and any probability measure μ over X, we let + I denote the law of [(x) x ~ μs. Given a sigma algebra F over some space 52, and measurable space X. :-) F x X - IR is probability kernel if for every x E X, ju(: x) is a measure over FF and for every A EF F. the map x - (A(A x is measurable. We make use of probability measures u(:;x; ix) where is a random element of some appropriate space X. resulting in random probability measures. We use [m]] and (m) to denote the sets {l...., m) and (o..... m - 1} respectively. For any finite set A. S denotes the group of all permutations of A. We use the O notation to characterize the dependence of our rates on the number of iterations T, dimension d and batch-size K, suppressing numerical and -eoeededde constants. We use to denote upto universal constants.
We fix a symmetric positive definite reproducing kernel k Rd Rd E and let the corresponding reproducing kernel Hilbert space (RKHS) [44] be denoted as Ho. We denote the product RKHS
as 7 IT Ho, equipped with the standard inner product for product spaces. We assume k is differentiable in both its arguments and let V2k(x, denote the gradient of k(:,)) with respect to the second argument. For any μ E P2(Rd)) we assume C (T²( and the inclusion map iu H >> (1)) is continuous. We use P,, (1) - H to denote the adjoint of ino i.e., the unique operator which satisfies (f,( (12)))) = (Paf, (u for any f E [.)()), 9 E H. Carmeli et al. (6) shows that Pμ. can be expressed as a kernel convolution, i.e., (P,f)(x)= = k(x,))
We define the function h Rd x H + R as h(x, k(x,)) as h = (Vx log( d (x))) for any μ E P2((R.). Integration by parts shows that h (x) fh(x, ydd(()) The convergence metric we use is the Kernel Stein Discrepancy (KSD) metric. which is widely used for comparing probability distributions (32 9 and analyzing SVGD 42 26
V2ki(x,)) y) and hy H
Definition 1 (Kernel Stein Discrepancy). Define the Langevin Stein Operator of n" acting on any differentiable g IRd + Rdd
(Tx-))x)==VV v - (VF(x). g(x))
For any two probability measures μ, v, the Kernel Stein Discrepancy between μ and v (with respect to x²)) ), denoted as KSD,, (Sl,+( is defined as
KSD (pllv) = sup [T
Eyp (x..g)
Ilsll
Using integration by parts (see Chwialkowssi et al. (.). i follows that KSD,, (Hill) = 1// - Now ||
Organization:
We review population-limit SVGD in Section 3 and derive VP-SVGD and GB-
SVGD in Section We state our technical assumptions in Section 5 main results in Section and provide proof sketch in Section 7 We present empirical evaluation in Section g

---

3 Background on Population-Limit SVGD
We briefly introduce the analysis of population-limit SVGD using the theory of Wasserstein Gradient Flows and refer the readers to Korba et al. [26] and Salim et al. 42 for a detailed treatment.
The space P2 (2(()) equipped with the 2- Wasserstein metric W2 is known the Wasserstein space, which admits the following Riemannian structure For any μa E (2RR),, the tangent space T (R) can be identified with the Hilbert space (M).. We can then define differentiable functionals C : (IR + R and compute their Wasserstein gradients, denoted as Vw, C. Note that the target ' is the unique minimizer over P2( for the functional Ciu] = KL (+!l The Wasserstein Gradient of Clu] is Vw, [in] Vx log( dx
du (x)) I This powerful machinery has served as a backbone for
the analysis of algorithms such LMC 53 2 and population- SVGD 14 26 42 45
The updates of population-limi SVGD can be viewed as Projected Gradient Descent in the Wasser- du
stein space. Recall from Section that the function (x) = Pa log(
)x) = f (x y)du(y), dx
Let foz denote the empirical measures of the SVGD particles (x: )ee[n] at timestep We note that the SVGD updates in ( can be recast as f (1 aha # In the limit of infinite particles n + 0o, suppose the empirical measure ji," converges to the population measure ta. In this population limit, the updates of SVGD can be expressed as,
(1)
Mi+1 (1 - haa Pt (1 (1-7Pp, (olog( log log((##)) de
Jr (1- (Vw, KL (Hell=*))) ))) # Pi
Recall from Section that PR. : (z.) - H is the Hilbert adjoint of ip,, Since H C (Tx)). the updates of SVGD in the population limit can be seen Projected Wasserstein Gradient Descent for [[r] = KL (j|[(=*), with the Wasserstein Gradient at each step being projected onto the RKHS H. Assuming KL ("oll=*) < 20, convergence of population limit SVGD is then established by tracking the evolution of KL (pellT") under appropriate structural assumptions (such as subgaussianity) on T².
4 Algorithm and Intuition
In this section, we derive VP-SVGD (Algorithm D. and build upon it obtain GB-SVGD. Consider
a countably infinite collection of particles x)" E IRd, E No {0), sampled i.i.d from a measure No. having density w.r.t. the Lebesgue measure. By the strong law of large numbers, the empirical
measure of X is almost surely equal to μuu (see Dudley [3] Theorem 11.4.1]). Let batch size K E N
denote the batch size, and Fe denote the filtration Fi, t as F. ((x | Kt-Kt)),).))))) 1)), Vt N. with Fo being the trivial a algebra. For ease of exposition, we discuss the case of K = in this section and present complete derivation for arbitrary K 2 in Appendix C Recall from Section that the updates of population-limit SVGD in (RR can be expressed as follows:
Mo+1 (T >hap)
We aim to design stochastic approximation in P2(( for the updates such that it admits finite-particle realization. To this end, we propose the following dynamics in Rd
x (+) >h(x)"
(ENU
(1) )i>ı (called the lower Now, for each time-stept t, focus the time evolution of the particles (x,"
triangular evolution). From B. we observe that for any t E N and 1 2 f. x depends only on
(0)
x x Hence, there exists deterministic, measurable function H, such that:
(1-1) (1)
= Hx (0)
x ((-1) x0)); for every / 2 I.
Since X Xg Xx
(0)
(1-1) (1) t.i.d.
μo. we conclude from 4 that (x, (1) Jızr are i.i.d when conditioned
on x1 x
(t-1)
To this end, we define the random measure Fe|F, as the law of x conditioned
on Fe, i.e., FelFF is a probability kernel p4(- xxx (0) ..... x "), where HolFF == noa By the strong (x))
law of large numbers, Me|FF is equal to the empirical measure of (xx") Juze conditioned on F,. We
will use ne Fe and pe(: 1xp ..... x ((-1)) interchangeably.
(0)
5

---

Define the random function Ir IR4 + IR as (x) == h(x, xxx,x(") () From 4 we note that yt is Fi+1
measurable. From we infer that the particles satisfy the following relation:
1+1 = (1 (g)))))
22t+1
Recall that x x x
(0)
(t)
pe+1 Fi++ for any t Furthermore, from Equation we
note that for 1, X
(a) depends only X ,..., X 1) and x Hence, we conclude that
(0)
Law(x)") 1x0 ,...., x Law(x) Xg ....: X ) Fe With this insight, the dynamics
of the lower-triangular evolution in P2(R that the following holds almost surely:
Mc F (1-)9)) Fe
(5)
x; ( ~ pelF; implies (x) = 1F. (x). Thus lower triangular dynamics a stochas- tic approximation P2((R") to the population limit of SVGD (2). Setting the batch size to general K and tracking the evolution of the first KT + particles, we obtain VP-SVGD (Algorithm I
Algorithm Virtual Particle SVGD (VP- (VP-SVGD)
Input: Number of steps T, number of output particles n, batch size K, Initial positions (T+KT-1) t.j.d. μo: Kernel k step size ?-
x
(0)
1: for t E (O....,,T 1 do
2:
for s (0,... ...,. KT + 1) do [k(x X
3:
x = x x=11=xx
k EE K--
(1K (1++)
(1K (x+t0) )V(( (ktt))) V2k(x, Xi
4: end for
5: end for
6: Draw S uniformly random from {0, ....... T
7: Output (..,,..,((n-1))) = (xg (T)) x (TK+n-1))
Virtual Particles In Algorithm|
KTSISKT are the real particles which constitute the output. (xx") KT are virtual particles which propagate information about the probability measure Me F, to enable computation of gt. unbiased estimate of the projected Wasserstein gradient A
(x+
without-replacemmntt random- batch approximation of SVGD I where a different batch is used across timesteps, but the same batch is across particles given a fixed timestep. With i.i.d. initialization, picking the 'virtual particles' in a fixed order or from random permutation does not change the evolution of the real particles. With this insight, we design GB-SVGD (Algorithm{) [ where we consider particles and output n particles (instead of wasting KT particles 'virtual particles') via random-batch approximation of SVGD.
VP-SVGD as SVGD Without Replacement VP-SVGD
Algorithm 2 Global Batch SVGD (GB-SVGD)
(0) Input: # of time steps T, # of particles X ...., x (n-1) iid.d.
no. Kernel k, step size Batch
size K, Sampling method E (with replacement, without replacement)
1: for E (0....,77 T 1}
1} do
2: Kr, random subset of [n] of size K (via. sampling method) 1} do
3: for 3 (O....,
4: x = x(") Erex, (k(x (e) ( (()(((")))
(e)
,x,
5: end for
6: end for
7: Draw S uniformly at random from f0, I,... T - 1}
8: Output (y(0), . p(a-1)))))))
(xg)
(0) (n-1) (1-1))
In Algorithm with replacement sampling means selecting a batch of K particles i.i.d. from the uniform distribution over [n]. Without replacement sampling means fixing a random permutation a over (0, ....... 1} and selecting the batches in the order specified by the permutation.

---

5 Assumptions
In this section, we discuss the key assumptions required for our analysis of VP-SVGD and GB-SVGD. Our first assumption is smoothness of F, which is standard in optimization and sampling.
Assumption (L-Smoothnesss.
V F exists and is L Lipschitz. Moreover VF S VL.
is easy find a point such that VF((x)) & (c.g, using ((1) gradient descent steps (37] and center the initialization Mu at x". For clarity, we take x without loss of generality. We now impose the following growth condition on F.
Assumption (Growth Condition). There exist at d1, d2 > 0 such that
F(x) 2 d1 | d2 Vx E R
Note that Assumption ensures a S 2. Assumption is essentially a tail decay assumption on the target density x* (x) e F(x), In fact, as we shall show in Appendix B Assumption 2 ensures that the tails of n² decay as x e [xll" Consequently, Assumption 2 holds with a when ' is subgaussian and with a = when n' is subexponential. Subgaussianity is equivalent to x satisfying 5 49 commonly assumed in prior works on SVGD
the Tn inequality that subexponentiality is implied when x² satisfies the Poincare Inequality
42
We also note 4 Section 4], which is
This makes Assumption [ significantly weaker than the isoperimetric or information-transpon assumptions considered in prior works.
considered a mild condition in the sampling literature [47 2
Next, we impose a mild assumption on the RKHS of the kernel ls which has been used by several prior works 42 26 45 43).
Assumption 3 (Bounded RKHS Norm). For any y ERRd, k( satisfies [|+(;) B. Furthermore, V2k(..)) E H. and 22 < B
Assumption B Jensures that the adjoint operator Pu., used in Sections and 3 well-defined. We
also make the following assumptions on the kernel k which is satisfied by a large class of standard kernels such Radial Basis Function kernels and Matérn kernels of order 2 3/2.
Assumption (Kernel Decay). The kernel satisfies the following for constants A1, A2, As > 0.
0 S k(x, S
A. -
[V2k(x, < A2, 1 Azk(x,))
Finally, we make the following mild assumption on the initialization.
Assumption 5 (Initialization). The initial distribution pi is such that KL (pollz²) < co. Furthermore, (4g is supported B(R), the &g ball of radius R
Since prior works usually assume Gaussian initialization non-standard. However, this is not drawback. In fact, whenever R ((vd + polylog(*/s)). Gaus- sian initialization can be made indistinguishable from Uniform(B(( R)) initialization, with probability at least 1 5, via coupling argument. To this end, impose Assumption 5 for ease of exposition and our results can be extended to consider Gaussian initialization. In Appendix B we show that taking R = ddhr. and μa = Uniform(BI R)) suffices to ensure KL (Holl>** (d))
42 47 Assumption may seem slightly
6 Results
6.1 VP-SVGD
Our first result, proved in Appendix shows that the law of the real particles of VP-SVGD, when conditioned on the virtual particles, is close to Æ² in KSD. As a consequence, it shows that the particles
output by VP-SVGD are i..d. samples from random probability measure [(-: (0) ..... ...
(KT -1)
which is close to xt in KSD. We also present high- probabibbabylitty version of this result in Appendix
Theorem 1 (Convergence of VP-SVGD). Let μ4 be as defined in Section Let Assumptions 72
3 satisfied and let y S min(3/2A1L, B)B. There exist (Ci)osiss depending polynomially
7

---

on A1, A2, A3, B. L, B,L. d2 for any fixed a E (0. such that whenever 75 S
1 2B
with &
Co (1,T) (2(72 V/ + R2 the following holds:
E |KSD" (m Fill=t]] S 2KL ) +B(++ t=0
7/T
K
(KT) and s (T), Pl so..... TKTT-,,,, == Ps( ;0,,.... ,.55..)) and pa( ; ,KKT-,,, 0) == no(-). Con-
Define the probability kernel p(- ;.) as follows: For any 2 E Rd,
.Ks--) ditioned on x. Ir, S = s for every E (KT), the outputs y(0), ....,, y(n of VP-SVGD are
i.dd samples from pl ;... I -1 s). Furthermore,
2KL (Holl**) yB(4+ + L)E²
B[KSD x- (nl: ; x x 1) s)][=>]]
7T
K
Convergence Rates Taking μi Uniform(B(RT) with 4/4 ensures KL (NO (Fol = (d)
(see Appendix Under this setting, choosing 7 O
(Kd) ensures that EjKSD x. [
O
d=# where 17 2[1+a] Thus. for 2, (i.e, sub-Gaussian π²), KSD* O (KTY*
[ For
d/
(i.e, uub-Expoeential ' r"), the rate (in squared KSD) becomes O( knowledge, our convergence guarantee for sub-exponential n* is the first of its kind.
(/CT) 1/4 ). To the best of our
Comparison with Prior Works Salim et al. 42 analyzes population-limit SVGD for subgaussian
n², obtaining KSD /T) rate. We note that population-linis SVGD (which requires infinite particles) is not implementable whereas VP-SVGI is an implementable algorithm whose outputs are conditionally i.i.d samples from distribution with guaranteed convergence n²
6.2 GB-SVGD
We now use VP-SVGD as the basis analyze GB-SVGD. Assume n > KT. Then, with probability at least 1 - k2T'"// /n (for with-replacement sampling) and 1 (for without-replacemenn sampling), the random batches KG, in GB-SVGD (Algorithm 2 are disjoint and contain distinct elements. When conditioned on this event ε, we note that the KT particles that were not included in any random batch Kr, evolve exactly like the n real particles of VP-SVGD. With this insight, we show that, conditioned on ε, the outputs of VP-SVGD and GB-SVGD can be coupled such that the first KT particles of both the algorithms are exactly equal. This allows us to derive the following squared KSD bound between the empirical measures of the outputs of VP-SVGD and GB-SVGD. The proof of this result is presented in Appendix D
(y.(0)...,, y((-1)) and Theorem 2 (KSD Bounds for GB-SVGD). Let KT and let Y -y ....,."....
Y = (g) p(n.)))( denote the outputs of VP-SVGD and GB-S GB-SVGD respectively. Moreover, let ((m)) = - Eyih and p(m) = 1 Σ dyto denote their respective empirical measures. Under there exists a coupling of Y and Y such that
the assumptions and parameter setlings of Theorem 1 the following holds:
2K2T262 nd
(without replacement sampling) (with replacement sampling)
EJKSD ( (c(m) <
T2
(1 K2T2
2 +
n
n
(6)
6.3 Convergence of the Empirical Measure to the Target
As corollary of Theorem I and Theorem 2 we show that the empirical measure of the output of VP-SVGD and GB-SVGD rapidly converges to T²" in KSD. We refer to Appendix D for the full statement and proof.
Corollary 1 (VP-SVGD and GB-SVGD: Fast Finite Particle Rates). Let the assumptions and parameter settings of Theorem I be satisfied. Let f((m) be the empirical measure of the n particles
output by VP-SVGD, run with run with KT = =d2+a, R == /a/L and appropriately chosen 7/. Then:
8/
EJKSD (A |m']] < O
d2tar +
a
2
8

---

Similarly. let 5/1) be the empirical measure of the output of GB-SVGD without replacement, run with KT nT, R V and appropriately chosen Then, the following holds:
B[KSD ( O
[|=]]
d1+a
11
142a Y2 2(1++)))
== 2), VP-SVGD has finite unite-particle rate of T (1/00) [[=]] = (((4') + (2) while that of GB-SVGD E[KSD,, (1(")][=*']
Comparison to Prior Work For subgaussian x" (i.e. a=
Oad /n + (2)))))).. Both these rates are double exponential improvement over the 0
poly(d))
KSD rate obtained by Shi and Mackey 43 for SVGD with subgaussian n².
v log log (tt/a)
1) the KSD rate of VP-SVGD is o (.dz) while that of ). To our knowledge, both these results are the first of their kind.
For subexponential 't (i.e.
GB-SVGD O d'/ 4/16 + d n
Oracle Complexity As illustrated Section for subgaussian n², the oracle complexity of VP-SVGD to achieve e-convergence in KSD is O (2²) and that of GB-SVGD is O(d"/²"), To our knowledge, these results are the first known oracle complexities for this problem with polynomial
dimension dependence, and significantly improve upon the O (oll(()) ( (d(ee"nld "oyld)/)))) oracle complexity of SVGD implied by Shi and Mackey 43). For subexponential n², the oracle complexity of VP-SVGD is (44 and that of GB-SVGD (dd
7
Proof Sketch
We now present a sketch of our analysis. As shown in Section 4 the particles (x "12 Ke are i.i.d conditioned on the filtration Fe, and the random measure Me]JF is the law of (x2 (K()) conditioned on X
(0) ..... x (Kt-1) Moreover, from equation (5) we know that PelF, : is stochastic approximation 79t) + Me Fr. Lemma (similar to Salim et al. [42] Proposition 3.1] and Korba et al. (26) Proposition 51) shows that under appropriate conditions, the KL divergence between μe and x* satisfies (stochastic) descent lemma. Hence Ft admits a density and KL (ft (ell is almost surely finite.
of population limit SVGD dynamics. i.e., Me+1 Fe+1
Lemma (Descent Lemma for 24 F.). Let Assumptions 7 S be satisfied and let 1 be an 3-1 the following holds almost surely BB
arbitrary constant. On the event +11 S
S KL (nr - - (P + 72 L)B
KL
19
Lemma 1 analogous the noisy descent lemma which is used in the analysis of SGD for smooth functions. Notice that E [[g][FF] N1.,1. (when interpreted as Gelfand-Pettis integral [46). as discussed in Appendix B and Appendíx CC and hence in expectation, the KI. divergence decreases in time. In order to apply Lemma I we establish an almost-sure bound on x below.
Lemma 2. Let Assumptions
and 5 hold. For 7 S 1/2A,L, L, the following holds almost surely, [| = + (T(TT) + (2()2T)) 1/2 + C2R
7
2
where So: S1, S2 and C3 which depend polynomially on A,, A2, A3, B, 3, d2, L for any fixed c.
Let K = for clarity. To prove Lemma 2 we first note via smoothness of F()) and Assumption
3 that
l1g:ll I Collx! || and then bound [|x{") Now, 9. (x) k(x, x (V V2k(x,
When (xx*) x|| is large, (lgx(x)) is small due to decay assumptions on the kernel (Assumption
implying that the particle does not move much. When x x, have ga (x) R k(x, x! V
V2k(x, x))) and k(x,, { 2 0. This approximately a gradient descent update on F()) along with
bounded term V 72k(x (x x! ()) Thus, the value of F(x cannot grow too large after T iterations.
By Assumption Fxx)
(1) being small implies that [x] is small.
Equipped with Lemma 2 we set the step-size y to ensure that the descent lemma (Lemma I always holds. The remainder the proof involves unrolling through Lemma taking iterated expectations
on both sides. To this end we control (hy,) gt), and [|ge l in expectation, in Lemma 3

---

Lemma 3. Let Assumptions 12 3 5
hold and & be as defined in Lemma 2 Then, for S 1/2A1 b,
(
Fi]
and
Ellgg Iid - 8/K++ 11
Experiments
We compare the performance of GB-SVGD and SVGD. We take 100 and the Laplace kernel with / = 1 for both. We pick the stepsize 7 by grid search for each algorithm. Additional details are presented in Appendix G We observe that SVGD takes fewer iterations converge, but the compute time for GB-SVGD is lower. This is similar to the typical behavior of stochastic optimization algorithms like SGD.
SVGD GB-SVGD (K 10)
SVGD GB-SVGD (K 10)
MMD Distance
MMD Distance
0.20
0.20
0.10
0.10
0.05
0.002 0.004 0,006 0.008 0.010 0.012 0.00
0.000
0
10
15
20
25
30
Wall Clock Time (seconds)
Iterations
MMD vs Compute Time
(b) MMD Iterations
Figure 1: Gaussian Experiment Comparing SVGD and GB-SVGD averaged over 10 experiments.
Accuracy
Accuracy
SVGD
SVGD
5000
10000
12500 15000
Clock (Seconds)
Iterations
(a) Accuracy vs Compute Time
(b) Accuracy Iterations
Figure 2: Covertype Experiment, averaged over 50 runs. The error bars represent 95% Cl.
Sampling from Isotropic Gaussian (Figure I
As a sanity check, we set x- = -0 I) with d = 5. pick K = 10 for GB-SVGD. The metric of convergence MMD with respect to the empirical measure of 1000 i.i.d. sampled Gaussians.
Bayesian Logistic Regression (Figure 2 We consider the Covertype dataset which contains 580, 000 data points with d' = 54. We consider the same priors suggested in Gershman et al. [16] and implemented in Liu and Wang [31]. We take K 40 for GB-SVGD, For both VP-SVGD and GB-SVGD, we use AdaGrad with momentum to set the step-sizes as per Liu and Wang B1
9 Conclusion
We develop two computationally efficient variants of SVGD with provably fast convergence guar- antees in the finite mnite-particle regime, and present wide range of improvements over prior work. A promising avenue of future work could be to establish convergence guarantees for SVGD with general non-logconcave targets, as was considered in recent works on LMC and SGLD 12]. Other important avenues include establishing minimax lower bounds for SVGD and related particle-based variational inference algorithms. Beyond this, we also conjecture that the rates of GB-SVGD can be improved in the regime < KT. However, we believe this requires new analytic tools.
10

---

Acknowledgements
We thank Jiaxin Shi, Lester Mackey and the anonymous reviewers for their helpful feedback. We are particularly grateful to Lester Mackey for providing insightful pointers on the properties of Kernel Stein Discrepancy, which greatly helped us in removing the curse of dimensionality from our finite-particle convergence guarantees.
References
[1] L. Ambrosio, N. Gigli, and G. Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science Business Media, 2005.
[2] K. Balasubramanian, S. Chewi, M. A. Erdogdu, A. Salim, and S. Zhang. Towards a theory of non-log-concave samplinggfisstorder stationarity guarantees for langevin monte carlo. In P.-L. Loh and M. Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2896 2923. PMLR, 02 05 html
Jul 2022. URL htttps://procedding
mlr
[3] E. Bernton. Langevin monte carlo and jko splitting. In Conference On Learning Theory, pages 1777-1798. PMLR, 2018.
[4] Bobkov and M. Ledoux. Poincaré's inequalities and talagrand's s concentration phenomenon for the exponential distribution. Probability Theerr and Related Fields, (07:383-400, 1997.
[5] S. G. Bobkov and F. Götze. Exponential integrability and transportation cost related to logarith- mie sobolev inequalities. Journal of Functional Analysis, 163(1):1-25 1999.
[6] C. Carmeli, E. De Vito, A. Toigo, and V. Umanitá. Vector valued reproducing kemel hilbert spaces and universality. Analysis and Applications, 1901):19-61,22
[7] S. Chewi, Le Gouie, Lu, T. Maunu, and P. Rigollet. Svgd as a kernelized wasserstein gradient flow of the chi-squared divergence. Advances in Neural Information Processing Systems, 33:2098-2109, 2020.
[8] Chewi, M. A. Erdogdu, M. Li, R. Shen, and S. Zhang. Analysis of langevin monte carlo from poincare log-sobolev. In P.-L. Loh and M. Raginsky, editors, Proceedings of Thirty Fifth Con- ference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1-2. PMLR, 02 05-05 Jul 2022. URL httpp:://poceedie
chewi22a mlr wwwpppressssseee whtps//v11///eeee122
html
[9] K. Chwialkowski, H. Strathmann, and A. Gretton. A kernel test of goodness of fit. In International conference on machine learning, pages 2606-2615. PMLR, 2016.
[10] B. Conway. course in functional analysis, volume 96. Springer, 2019.
[11] A. Das, B. Schölkopf, and M. Muchlebach. Sampling without replacement leads to faster rates in finite-sum minimax optimization. Advances in Neural Information Processing Systems, 2022.
[12] A. Das, D. Nagaraj, and A. Raj. Utilising the clt structure in stochastic gradient based sampling: Improved analysis and faster algorithms. In Conference on Learning Theory, 2023.
[13] R. M. Dudley, Real analysis and probability, CRC Press, 2018.
[14] A. Duncan, N. Nüsken, and L. Szpruch. On the geometry of stein variational gradient descent. arXiv preprint arXiv: 19/20009//,0094,,, 2019.
[15] A. El Alaoui, A. Montanari, and M. Sellke. Sampling from the sherrington-kiikparriik gibbs measure algorithmic stochastic localization. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 323-334, IEEE, 2022.
[16] S. Gershman, M. D. Hoffman, and D. M. Blei. Nonparametric variational inference. In Proceedings of the 29th International Conference on International Conference on Machine Learning, 2012.
11

---

[17] S. Gopi, Y. T. Lee, and D. Liu. Private convex optimization via exponential mechanism. In Conference on Learning Theory, pages 1948-1989. PMLR, 2022.
[18] J. Gorham, A. Raj, and L. Mackey. Stochastic stein discrepancies. Advances in Neural Information Processing Systems, 33:17931-17944 2020.
[19] Haarnoja, H. Tang, Abbeel, and Levine. Reinforcement learning with deep energy- based policies. In International conference on machine learning, pages 1352-1361. PMLR, 2017.
[20] J. Ho, A. Jain, and P. Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840 18511 2020.
[21] P. Jain, D. M. Nagaraj, and P. Netrapalli. Making the last iterate of sgd information theoretically optimal. SIAM Journal on Optimization. 31(2):108--113 2021.
[22] P. Jaini, L. Holdijk, and M. Welling. Learning equivariant energy based models with equivariant stein variational gradient descent. Advances in Neural Information Processing Systems, 34: 16727-16737, 2021.
[23] S. Jin, L. Li, and J.-G. Liu. Random batch methods (rbm) for interacting particle systems. Journal of Computational Physics, 400:108877, 2020.
[24] A. Khaled and P. Richtárik. Better theory for sgd the nonconvex world. arXiv preprint arXiv:200..03329, 2020.
[25] Y. Kinoshita and T. Suzuki. Improved convergence rate of stochastic gradient langevin dynamics with variance reduction and its application to optimization. arXiv preprint 4rXiv:2203.16217, 2022.
[26] A. Korba, A. Salim, M. Arbel, G. Luise, and A. Gretton. A non-asymptotic analysis for stein variational gradient descent. Advances in Neural Information Processing Systems, 33: 4672-4682, 2020.
[27] H. J. Kushner and D. S. Clark. Stochastic approximation methods for constrained and uncon- strained systems, volume 26. Springer Science & Business Media, 2012.
[28] Y. T. Lee and S. S. Vempala. The manifold joys of sampling (invited talk). In 49th International Colloquium Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2022.
[29] L. Li, Y. Li, J.-G. Liu, Z. Liu, and J. Lu. A stochastic version of stein variational gradient descent for efficient sampling. Communications in Applied Mathematics and Computational Science, 15(1):37-63, 2020.
[30] Q. Liu. Stein variational gradient descent gradient flow. Advances in neural information processing systems, 30, 2017.
[31] Q. Liu and D. Wang. Stein variational gradient descent: A general purpose bayesian inference algorithm. Advances in neural information processing systems, 29, 2016.
[32] Q Liu, J. Lee, and M. Jordan. A kernelized stein discrepancy for goodness-of-ff tests. In International conference machine learning, pages 276-284. PMLR, 2016.
[33] T. Liu, P. Ghosal, K. Balasubramanian, and N. S. Pillai. Towards understanding the dynamics of gaussian-stein variational gradient descent, 2023.
[34] Y. Liu, P. Ramachandran, Q. Liu, and J. Peng. Stein variational policy gradient. arXiv preprint 17Xvv:1704.02399, 2017.
[35] J. Lu, Y. Lu, and J. Nolen. Scaling limit of the stein variational gradient descent: The mean field regime. SIAM Journal on Mathematical Analysis, 51(2):6886671 2019.
[36] R. M. Neal et al. Meme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(11):2, 1.
12

---

[37] Y. Nesterov, Introductory lectures on convex programming volume i: Basic course. Lecture notes, 3(4)5, 1998.
[38] N. Nüsken and D. Renger. Stein variational gradient descent: many-particle and long-time asymptotics, arXiv preprint arXiv:2102. 2021.
[39] G. Parisi. Correlation functions and computer simulations. Nuclear Physics 180(3):37--384,
1981.
[40] M. Raginsky, A. Rakhlin, and M. Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference on Learning Theory, pages 1674-1703, PMLR, 2017.
[41] G. O. Roberts and R. L. Tweedie. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, pages 341-363, 1996.
[42] A. Salim, L. Sun, and P. Richtarik. convergence theory for svgd in the population limit under talagrand's inequality tl. In International Conference Machine Learning, pages 19139-19152. PMLR, 2022.
[43] Shi and L. Mackey. A finite- paritee convergence rate for stein variational gradient descent. arXiv preprini arXiv:2211.0972.1 2022.
[44] I. Steinwart and A. Christmann. Support vector machines. Springer Science & Business Media, 2008.
[45] I.. Sun, A. Karagulyan, and P. Richtarik. Convergence of stein variational gradient descent under weaker smoothness condition. In International Conference on Artificial Intelligence and Statistics, pages 3693-3717. PMLR, 2023.
[46] M. Talagrand. Pettis integral and measure theory. American Mathematical Soc., 1984.
[47] S. Vempala and A. Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
[48] R. Vershynin. High--dimensoonal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[49] C. Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
[50] D. Wang and Q. Liu. Learning to draw samples: With application to amortized mle for generative adversarial learning, arXiv preprint
2016.
[51] D. Wang, Z. Zeng, and Q. Liu. Stein variational message passing for continuous graphical models. In International Conference on Machine Learning, pages 5219-5227. PMLR, 2018.
[52] M. Welling and Y. W. Tch. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11), pages 68 6818688, 2011.
[53] A. Wibisono. Sampling as optimization in the space of measures: The langevin dynamics as composite optimization problem. Conference on Learning Theory, pages 2093-3027. PMLR, 2018.
[54] J. Zhuo, C. Liu, J. Shi. J. Zhu, N. Chen, and B. Zhang. Message passing stein variational gradient descent. In International Conference on Machine Learning, pages 6018-6027. PMLR, 2018.
[55] D. Zou, P. Xu, and Q Gu. Faster convergence of stochastic gradient langevin dynamics for con-log-concave sampling. In Uncertainty in Artificial Intelligence, pages 152-1162. PMLR, 2021.
13


Reviews:
[{"review_id": "bro2Jy9NU8", "reviewer": "Reviewer_9R2A", "summary": "This paper propose two variants of stein variational gradient descent (SVD) named as Virtual Particle SVGD (VP-SVGD) and Global Batch SGVD (GB-SVGD) with provably fast finite-particle convergence rates to a target distribution. Introducing the notion of virtual particles, the authors show that VP-SVGD is an exactly implementable finite-particle stochastic approximation of population-limit SVGD dynamics in the space of probability measures. Viewing VP-SVGD as a specific random-batch SVGD algorithm, the authors argue that  the output particles from GB-SVGD after T time steps with batch-size K are as good as sampling iid from a distribution whose Kernel Stein Discrepancy (KST) to a sub-gaussian target distribution is at most $O(d^{1/3}/(KT)^{1/6})$. Furthermore, under mild growth conditions, the authors show that the empirical distribution of the n-output particles from both VP-SVGD and GB-SVGD converges to the target in KSD at a rate of $O(d^{2}/(n)^{\\Theta(1/d)})$. The authors note that this is a doubly exponential improvement over the state-of-the-art finite-particle analysis of SVGD under weaker assumptions. Finally, the authors provide numerical experiments to show fast convergence of GB-SVGD which is computationally more efficient than SVGD.\n\n\n\n\n\n\n", "questions": "I suspect there are a few typos in the text.\n\n1)bold x with varying subscript  in line 249 vs bold x with varying superscript in the equation after line 250. also the index runs to T but I would expect T-1.\n\n2)bold x instead of bold y in line 224\n\n3) In line 204, we are already given that $g_s(x) = ...$ and then in line 306 we are told that $g_s(x) \\approx ...$, Is this a typo ?\n", "limitations": "Limitations and future works are discussed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1)Originality: This paper is introduces two new variants of SVGD appealing to a novel construction involving countably many virtual particles.  Although the analysis involves infinitely many particles, a finite-number of particles exactly suffice for the actual algorithm VP-SVGD. This enables the authors to claim that VP-SVGD performs a finite-particle stochastic approximation of the population (infinite-particle) dynamics of SVGD over the space of probability distributions. Finally, they show VP-SVGD and the computationally efficient GB-SVGD behave very closely.\n\n2)Quality: I think this paper is technically quite solid. The theoretical claims are all sound and the assumptions are reasonable.\n\n3)Clarity: This paper is well written. It is easy to follow the main ideas including the problem statement, technical challenges, relevance to past works, and the contributions.\n\n4)Significance: It is quite significant to improve the SOTA result doubly exponentially under weaker assumptions. Besides, the virtual particle method is worthwhile studying by itself ( I am not aware of a similar method discussed somewhere else).", "weaknesses": "It wasn't easy for me to parse some of the theoretical results, which can be expected as this paper is theory heavy.\n\nA table of past works comparing the results in terms of assumptions, method, and the convergence rate might be a helpful addition. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\newcommand{\\cF}{\\mathcal{F}} \\newcommand{\\vx}{\\mathbf{x}} \\newcommand{\\mub}{\\bar{\\mu}} \\newcommand{\\KL}[2]{KL\\left(#1||#2\\right)} \\newcommand{\\bE}{\\mathbb{E}} \\newcommand{\\KSDs}[3]{KSD^{2}\\_{#1}(#2||#3)} \\newcommand{\\iidsim}{{\\overset{\\mathrm{iid}}{\\sim}}}$ Thank you for your kind and thoughtful review and your helpful suggestions which we have incorporated in our updated draft. In particular, our updated draft presents a more detailed account of related work, including a table that compares our results to that of prior work.  \n\n## Line 224\nThank you for pointing this out. Our updated draft corrects for this typo.\n\n## Regarding $g_s(\\vx) \\approx \\dots$\n\nWe note that $g_s(\\vx) = k(\\mathbf{x}, \\mathbf{x}^{(s)}_s) \\nabla F(\\mathbf{x}^{(s)}_s) - \\nabla_2 k(\\mathbf{x}, \\mathbf{x}^{(s)}_s)$ as per Lines 204 and 305. In Line 307, we state that, *whenever* $\\mathbf{x} \\approx \\mathbf{x}^{(s)}_s$, $g_s(\\mathbf{x}) \\approx k(\\mathbf{x}, \\mathbf{x}^{(s)}_s) \\nabla F(\\mathbf{x}) - \\nabla_2 k(\\mathbf{x}, \\mathbf{x}^{(s)}_s)$ *is satisfied*. This holds because the smoothness assumption on the potential $F$ (Assumption 1) ensures that $\\nabla F(\\mathbf{x}) \\approx \\nabla F(\\mathbf{x}^{(s)}_s)$ whenever $\\mathbf{x} \\approx \\mathbf{x}^{(s)}_s$ (note that since $\\\\| \\nabla F(\\mathbf{x}) - \\nabla F(\\mathbf{x}^{(s)}_s)\\\\| \\leq L \\\\| \\mathbf{x} - \\mathbf{x}^{(s)}_s \\\\|$, $\\\\| \\nabla F(\\mathbf{x}) - \\nabla F(\\mathbf{x}^{(s)}_s)\\\\|$ is small whenever $\\\\| \\mathbf{x} - \\mathbf{x}^{(s)}_s \\\\|$ is small) \n\n## Equation after Line 250\n\nThank you for the pointer! For arbitrary $K \\geq 1$, the indexing should indeed be $\\bE[\\KSDs{\\pi^*}{\\mub(\\cdot; \\vx^{(0)}\\_{0}, \\dots, \\vx^{(KT-1)}\\_{0})}{\\pi^*}]$. We have corrected this in our updated draft. To the best of our understanding, the use of bold $\\vx$ with varying superscript is not a typo. To observe this, we note that $\\mub$ is defined as $\\mub(\\cdot;x\\_0, \\dots, x\\_{KT-1}, s) := \\mu\\_s(\\cdot;\\vx^{(0)}\\_{0} = x\\_0, \\dots, \\vx^{(Ks-1)}\\_{0} = x\\_{Ks-1}) = Law(\\vx^{(Ks)}\\_s | (\\vx^{(l)}\\_0)\\_{l < Ks} = (x\\_{0}^{(l)})\\_{l < Ks})$ (by convention, $\\mub(\\cdot;x\\_0, \\dots, x\\_{KT-1}, s=0) := \\mu\\_0(\\cdot)$). In particular, $\\mub(\\cdot; x\\_0, \\dots, x\\_{KT-1}, s)$ gives us a distribution corresponding to any value $(x\\_{0}^{(l)})\\_{l < KT} \\in \\mathbb{R}^{d\\times KT},s \\in \\\\{ 0, \\dots, T \\\\}$ . Thus, we interpret $\\mub(\\cdot ; \\vx^{(0)}\\_{0}, \\dots, \\vx^{(KT-1)}\\_{0},S)$ as a random probability measure, with the randomness being induced by $\\vx^{(0)}\\_{0}, \\dots, \\vx^{(KT-1)}\\_0 \\ \\iidsim \\ \\mu_0$ and $S \\sim Unif(\\\\{0, \\dots, T-1\\\\})$."}, {"review_id": "iHGqvRgbnC", "reviewer": "Reviewer_T9Sw", "summary": "The paper studies Stein Variational Gradient Descent (SVGD) which is a popular variational inference algorithm that simulates an interacting particle system to approximately sample from a target distribution. The authors propose two variants of SVGD, Virtual Particle SVGD (VP-SVGD) and Global Batch SVGD (GB-SVGD), that differ in their implementation details and computational efficiency. Both variants use the so-called \"virtual particles\", which are additional particles that evolve in time but are not part of the output, to compute information about the current population-level distribution of the real particles and enable exact implementation of the stochastic approximation using only a finite number of particles. The use of virtual particles allows for faster variants of SVGD with provably fast finite-particle convergence.", "questions": "I am not a leader in the topic of SVGD but had a chance to work on the topic at a senior educative level. Hence I recognize the importance of this topic. Some questions are as follows:\n\nHow do the VP-SVGD and GB-SVGD variants of SVGD differ from the original SVGD introduced by Liu and Wang [32]?\nMy understanding is that the key difference between VP-SVGD and GB-SVGD variants of SVGD is that VP-SVGD is a stochastic approximation of the exact SVGD dynamics, while GB-SVGD is a specific random-batch approximation of SVGD which enjoys computationally more efficient than ordinary SVGD. Is that correct?\n\nCan you explain more about the concept of virtual particles and how they are used in these algorithms? I understand that virtual particles are additional particles that evolve in time but are not part of the output (i.e., real particles) which are used only to compute information about the current population-level distribution of the real particles. Are they absolutely necessary --- are there any equivalent or similar implementations that do not necessarily require the introduction of virtual particles?\n\nIn the technical analysis of Corollary 2, is there any hope to make the decaying exponent in polynomial rate dimension-free or have a weaker dependence on dimension (perhaps using an alternative metric or developing new analytic tools to yield an improved bound)?", "limitations": "The work is purely theoretical and admits no negative social impacts.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper introduced two variants of SVGD, VP-SVGD and GB-SVGD, that use virtual particles to enable the exact implementation of the stochastic approximation using only a finite number of particles. The authors present a non-asymptotic analysis of the convergence of VP-SVGD and GB-SVGD to the target distribution, which demonstrates a double exponential improvement over the best-known finite-particle analysis of SVGD. The paper proposes a new algorithm, VP-SVGD, that achieves provably fast finite-particle convergence and is computationally more efficient than ordinary SVGD.\n\nThe paper is well-organized and clearly written, with detailed explanations of key concepts and technical details that make it accessible to a wide range of readers. Literature review of related work on SVGD and its variants was conducted comprehensively, which helps to contextualize the proposed algorithms and their contributions.\n\nI went through the proofs of Theorem 1 and Corollary 1 or 2 in Section E in detail, and believe they are technically sound. The KSD metric satisfies the triangle inequality where the upper bound is in two additional parts. In (34), the KSD metric satisfies a triangle inequality, and the first term (probability kernel vs population limit) is polynomial with a polynomial decaying exponent that is independent of dimension $d$ ($d^{1/3}T^{-1/6}$ when subgaussian). The second term appears dominating, where the polynomial decaying exponent in Wasserstein-1 distance is $\\Theta(1/d)$, which is due to Lemma 8 by Lei [29].", "weaknesses": "Despite its significant contributions, this work assumes a certain level of familiarity with the concepts of variational inference and particle methods and is relatively specialized and may make it difficult for readers who are not already familiar with or not working on the topic of SVGD and its variants to follow.  Despite the technical contributions of proposed SVGD-style algorithms and their convergence properties, the authors did not provide a detailed discussion of the limitations of the proposed algorithms or potential avenues for future research, which may limit their impact and relevance in the long term it and make it less accessible to readers who are more interested in the broader implications of the work. Lastly, the work does not provide sufficient details on the proposed algorithms' empirical evaluations of real-world datasets, which limits the ability to assess their practical usefulness. These weaknesses did affect my current rating, but I reserve the possibility to raise the score if any of the above points can be resolved in the authors' rebuttal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$ \\newcommand{\\iidsim}{{\\overset{\\mathrm{iid}}{\\sim}}} \\newcommand{\\cH}{\\mathcal{H}} \\newcommand{\\hmu}{\\hat{\\mu}^{(n)}}$ \nThank you for your thoughtful review and suggestions, which have significantly helped us improve our work. We have updated our draft to include a detailed discussion of the limitations and broader applications of our results which could be interesting avenues of future work (some of which are discussed below). We also present a more elaborate comparison of our results to that of prior work. Since our work is primarily theoretical, we perform our experiments on a few of the simple (yet high-dimensional) benchmarks considered in prior work [2] to illustrate the efficacy of our algorithm. Empirical evaluation of our algorithms on sophisticated architectures and datasets is an important avenue of future work which we intend to pursue. We hope our response below addresses your questions.\n\n## Dimension-Free Exponent in Corollary 2 & 3\nThank you for the pointer! Based on your suggestion, we remove the dimension dependence in the $n$ exponent of Corollary 2 and 3 and show that for subgaussian $\\pi^*$, VP-SVGD has a finite-particle KSD rate of $O(\\tfrac{d^{1/4}}{n^{1/4}} + \\tfrac{d^{1/2}}{n^{1/2}})$ while GB-SVGD has a finite-particle KSD rate of $O(\\tfrac{d^{1/3}}{n^{1/12}} + \\tfrac{d^{1/2}}{n^{1/2}})$ (the constant factors in the exponents may be further improved via careful analysis). We briefly discuss this result in our common response and present a full proof in our updated draft. A proof sketch for VP-SVGD is presented below:\n\nRecall that the outputs of VP-SVGD are $(\\vx^{(l)}\\_S)_{KT \\leq l \\leq KT+n-1}$ where $S \\sim Unif(\\\\{0, \\dots, T-1 \\\\})$. Let $\\hmu$ be their empirical measure. By defn of KSD, $\\KSDs{\\pi^*}{\\hmu}{\\pi^*} = \\\\|h\\_{\\hmu}\\\\|^2\\_\\cH = \\\\| \\tfrac{1}{n} \\sum\\_{l=0}^{n-1} h(., \\vx^{(KT+l)}\\_S) \\\\|^{2}\\_{\\cH}$. Let $V$ denote the conditioning on the virtual particles $(\\vx^{(l)}\\_0)\\_{l < KT}$. Conditioning on $V$ and the event $S=t$, we get: \n$$\\bE[\\KSDs{\\pi^*}{\\hmu}{\\pi^*}|S=t,V] = \\bE[\\\\|\\tfrac{1}{n} \\sum\\_{l=0}^{n-1} h(., \\vx^{(KT+l)}\\_t)\\\\|^{2}\\_{\\cH} |V] = \\bE[\\\\|\\tfrac{1}{n} \\sum\\_{l=0}^{n-1} h(., \\vx^{(KT+l)}\\_t)\\\\|^{2}\\_{\\cH} |(\\vx^{(l)}\\_{0})\\_{l < KT}]$$\nwhere we use Equation 14 from Appendix C.1 to note that $\\vx^{(KT+l)}_t$ depends only on $(\\vx^{(s)}\\_0)\\_{s < Kt}$ & $\\vx^{(KT+l)}\\_0$. Recall that $$\\bE[\\\\|\\tfrac{1}{n} \\sum\\_{l=0}^{n-1} h(., \\vx^{(KT+l)}\\_t)\\\\|^{2}\\_{\\cH} |(\\vx^{(l)}\\_{0})\\_{l < KT}] = \\bE[\\\\|\\tfrac{1}{n} \\sum\\_{l=0}^{n-1} h(., \\vx^{(KT+l)}\\_t)\\\\|^{2}\\_{\\cH} |\\cF\\_t]$$\nNote that $(\\vx^{(l)}\\_t)\\_{KT \\leq l \\leq KT+n-1}$ are conditionally i.i.d samples from $\\mu_t | \\cF_t$. Applying the same arguments as Lemma 3, we get:\n$$\\bE[\\\\|\\tfrac{1}{n} \\sum\\_{l=0}^{n-1} h(., \\vx^{(KT+l)}\\_t)\\\\|^{2}\\_{\\cH} |\\cF\\_t] \\leq \\tfrac{\\xi^2}{n} + \\\\| h\\_{\\mu_t | \\cF_t} \\\\|^{2}\\_{\\cH} = \\tfrac{\\xi^2}{n} + \\KSDs{\\pi^*}{\\mu_t | \\cF_t}{\\pi^*}$$\nTaking expectations over $S$ and the virtual particles gives us:\n$$\\bE[\\KSDs{\\pi^*}{\\hmu}{\\pi^*}] \\leq \\tfrac{\\xi^2}{n} + \\tfrac{1}{T} \\sum\\_{t=0}^{T-1} \\bE[\\KSDs{\\pi^*}{\\mu_t | \\cF_t}{\\pi^*}]$$\nWe conclude by substituing the bound of Theorem 1 and setting $\\eta$ & $KT$ appropriately.\n\n## VP-SVGD and Concept of Virtual Particles\nWe refer to the common response for a detailed explanation on the similarities and differences between SVGD & VP-SVGD, as well as the key concepts behind the use of virtual particles. \n\n## GB-SVGD and the Necessity of Virtual Particles\n\nYes, GB-SVGD is a specific random batch approximation of SVGD (discussed in Section 1.2 Lines 87-96) which is computationally more efficient than ordinary SVGD (SVGD needs $n^2 T$ evaluations of $\\nabla F$ while GB-SVGD needs $nKT$ evaluations, and typically $K \\ll n$). We show that because of the random batches used in every timestep, GB-SVGD behaves similar to VP-SVGD (see Lines 204-207 and 260-266), and thus can also be viewed as an approximation to mean-field (infinite-particle) SVGD. This insight helps us prove a fast finite-particle rate for GB-SVGD (Corollary 3) which is double-exponentially faster than the best known finite-particle rate for SVGD [1].\n\nWe highlight that **GB-SVGD does not require any virtual particles in its implementation** (see Algorithm 2 and Lines 205-207) and the comparison to VP-SVGD (Theorem 2) is only for the sake of mathematical analysis. In fact, Corollary 3 GB-SVGD needs only $n$ input particles to output $n$ particles whose empirical measure rapidly converges to $\\pi^*$ in KSD.\n\n## Potential Future Directions\nA few interesting avenues of future work include: 1. Extensions of VP-SVGD and GB-SVGD for sampling from manifolds by considering kernelized Riemannian Wasserstein gradient flows [3]; 2. Learning-rate free variants of VP-SVGD and GB-SVGD by applying techniques from parameter-free online optimization [4]. Beyond this, we believe our virtual particle technique is of independent interest beyond sampling and can be applied to obtain provably converging finite-particle implementations of more sophisticated mean-field dynamics (such as Mean-Field Langevin Dynamics [5] and Wasserstein Fisher-Rao Gradient Flows [6]) \n\n1. Shi et.al.'22, A Finite Particle Convergence Rate for SVGD\n2. Liu & Wang'16, SVGD\n3. Ohta'09, Gradient flows on Wasserstein spaces over compact Alexandrov spaces\n4. Cutkosky et.al.'18, Blackbox Reductions for Parameter-Free Online Learning in Banach Spaces\n5. Chizat et.al.'22, Trajectory Inference via Mean-Field Langevin in Path Space\n6. Chizat et.al.'18, An interpolating distance between Optimal Transport and Fisher–Rao metrics. "}, {"review_id": "YoObySadyh", "reviewer": "Reviewer_UYmX", "summary": "This study analyzed the finite particle behavior of Stein Variational Gradient Descent (SVGD) in an asymptotic manner. For that purpose, the authors designed two computationally efficient variants of SVGD, namely VP-SVGD and GB-SVGD, and prove their convergence rates. In those methods, the authors introduced a new concept of \"virtual particles\" and develop a new stochastic approximation of the population-limited SVGD dynamics in the probability measure space. The proposed algorithm shows a significant improvement of the convergence rates under  looser conditions than the usual SVGD.", "questions": "- What is $\\nabla_2$ in Line 143 ? Partial derivative with respect to the second variable?\n\n- Is my following understanding correct? Intuitively, the motivation for introducing virtual particles is to ensure that the resulting particles are i.i.d, which is required to use Lemma 7 in the theoretical analysis.\n\n- Algorithm 1 requires a larger number of particles in proportion to the time step T than ordinary SVGD, and therefore the number of gradient calculations increases considerably. To achive $KSD(particles,\\pi^*)\\leq \\epsilon$, does VP-SVGD increase the order of magnitude of the number of the gradient calculation compared to standard SVGD?\n\n- I was wondering why S is taken randomly in Algorithm 1 line 6 and Algorithm 2 line 7, etc., and I thought it would greatly reduce the practical performance. But after reading the proof, I understand that this is necessary to convert the bounds of $\\frac{1}{T}$KSD^2(\\mu_t|\\pi^*)$ to KSD(\\bar{\\mu}|\\pi^*}) as shown in Theorem 1. Is this understanding correct?\n\n- In the numerical experiment, are random $S$ used as written in TAlgorithm 1 and 2? Since the objective function is convex, such random S may not have such a strong effect on the final performance. I wonder how harmful this random $S$ is when the objective distribution is non-log concave?\n\n\n", "limitations": "Theoretical limits are discussed in detail.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The convergence rates in this paper are significantly better than existing methods.\n\n- The idea of virtual particles introduced for the analysis is very novel and very interesting in itself.\n\n- Numerical experiments, although simple,  suggest that the proposed method is indeed an improvement over existing methods.", "weaknesses": "- Notation in Sec 4 is very confusing, especially about $l, s, t$\n\n-  In the explanation of Sec 4, only the case of K=1 is clearly stated, and I had to spend a lot of time thinking about what happens when K>2. I think an additional explanation of K > 2 is needed in the Appendix.\n\n- The algorithm of GB-SVGD is difficult to understand. In particular, the third line mentions \"l\", but \"l\" does not appear at all in the fourth line. This may be because the \"l\" in the third line may be a mistake for \"s\".\n\n- I am not sure if the theoretical comparison of the convergence order with the existing analysis is justified since the VP-SVGD is no longer the original SVGD. The GB-SVGD is close to the existing SVGD, but it is also difficult to compare with the existing SVGD because of the approximation errors as shown in Theorem 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\newcommand{\\e}{\\epsilon} \\newcommand{\\gd}{\\nabla} \\newcommand{\\KSD}[3]{KSD\\_{#1}(#2||#3)}$ Thank you for your constructive feedback. We hope to address your questions in our response below:\n## Notation in Sec. 4\nThanks for the suggestion! This is incorporated in our updated draft where we consistently use $\\vx^{(l)}\\_t;l, t\\geq0$ to denote the particles. As before, our indices start from $0$ (as is common in comp. sci. literature).  \n\n## $l,s$ in GB-SVGD\nThanks for the pointer! $l$ in the third line of Algorithm 2 should be $s$. This typo is fixed in our updated draft.\n\n## Batchsize $K>2$ in VP-SVGD\nFor ease of exposition, the discussion in Sec. 4 considers $K=1$. Our analysis of VP-SVGD in Appendix C presents a complete proof for $K \\geq 1$ (see Appendix C.1)\n\n## $\\gd\\_2$ in Line 143\nYes, it refers to the derivative w.r.t second variable. This is mentioned in Section 2 Lines 138-139.\n\n## Oracle Complexity of VP-SVGD & SVGD\n We compare the gradient oracle complexity of VP-SVGD & ordinary SVGD as implied by [1], which to our knowledge, is the best known finite-particle rate for SVGD. Note that $T$ iterations of $n$-particle SVGD needs $n^2 T$ evaluations of $\\gd F$. Carefully following the analysis of [1] shows that the oracle complexity of SVGD for $KSD\\leq\\e$ is $\\tilde{O}(\\frac{poly(d)}{\\e^2}\\exp(\\Theta(d\\exp(\\tfrac{poly(d)}{\\e^2}))))$\n\nVP-SVGD run for $T$ iterations with batch-size $K$ & $n$ real particles requires $K^2 T^2 + KTn$ evaluations of $\\gd F$. From Corollary 1, we find that the oracle complexity of VP-SVGD for $KSD \\leq \\epsilon$ is $\\tilde{O}(\\exp(\\Theta(d \\log(\\tfrac{d^2}{\\e}))))$. This is a **double exponential improvement** over SVGD. Note that GB-SVGD (which needs $KTn$ evaluations of $\\nabla F$) also enjoys this improved gradient complexity. Thus, we conclude that **VP-SVGD requires far fewer gradient evaluations than SVGD** due to its superior convergence rate. Our updated draft shows a complete derivation of the oracle complexity of SVGD, VP-SVGD & GB-SVGD, where we also show that **our improved analysis of the finite-particle convergence of VP-SVGD & GB-SVGD** (see common response) **leads to further improvements in oracle complexity.** \n\n## Comparing Ordinary SVGD & VP-SVGD\nWe respectfully disagree with the reviewer's claim that ordinary SVGD & VP-SVGD are not comparable. We refer the reviewer to our common response where we elucidate that **both ordinary SVGD & VP-SVGD are finite-particle approximations of the same mean-field dynamics**. Thus we firmly believe that the two algorithms can be justifiably compared. \n\n## Motivation Behind Virtual Particles\nWe note that Lemma 7 (i.e. the descent lemma of [6]) holds without any conditional independence requirement. As such, we do not use the conditionally i.i.d structure of VP-SVGD outputs to apply Lemma 7. We refer the reviewer to our common response where we explain the key ideas behind the use of virtual particles in VP-SVGD. We note that the **conditionally i.i.d structure is used for applying the empirical-to-population Wasserstein bound of Lemma 8**, which is a key step in our proof of the finite-particle rate for VP-SVGD (Corollary 2)\n\n## Comparing ordinary SVGD and GB-SVGD\nWe note that **GB-SVGD is a random batch approximation of ordinary SVGD** (see Section 1.2 Lines 87-96). Thus, we firmly believe that **they can be meaningfully compared just like SGD is compared to GD in optimization [2] & SGLD is compared to LMC in sampling [3,4]**. Moreover, Theorem 2 does not say anything about the approximation error of GB-SVGD w.r.t ordinary SVGD, but instead is a Wasserstein-1 comparison bound between the empirical measures of the outputs of GB-SVGD and VP-SVGD (used to prove Corollary 3)\n\n## Use of Uniform Random $S$\nYes, using $S \\sim Unif(\\\\{0, \\dots, T-1\\\\})$ allows us to convert the average bound $\\tfrac{1}{T} \\sum\\_{t=0}^{T-1} \\bE[\\KSDs{\\pi^*}{\\mu\\_t | \\mathcal{F}\\_t}{\\pi^*}]$ into a bound in terms of $\\bE[\\KSDs{\\pi^*}{\\bar{\\mu}}{\\pi^*}]$. This ensures that the particles output by VP-SVGD are (conditionally i.i.d) samples from a distribution which is provably close to $\\pi^*$ in KSD. Such average bounds are commonplace in prior works on SVGD [1,5,6], sampling in general [4,7], and optimization [2,8].\n\nWe note that obtaining last iterate guarantees, even in optimization, involves sophisticated techniques & algorithmic modifications [9,10]. We believe achieving this in the context of SVGD-type sampling algorithms (using only tail decay assumptions on $\\pi^*$) is an important future direction.\n\n## $S$ in Experiments\nFor all algorithms considered, we benchmark the performance of the current iterate against iterations/wall clock time. We note that this is standard practice in stochastic optimization [9,10,11]. Our updated draft states this explicitly. \n\nRegarding the performance w.r.t non-log-concave $\\pi^*$: Based on our intuition from stochastic convex optimization, we do not believe that such an averaging will theoretically affect the performance since: 1. $\\mu \\to \\KL{\\mu}{\\pi^*}$ & $\\mu \\to \\KSD{\\pi^*}{\\mu}{\\pi^*}$ are both convex functionals of probability distributions, 2. The algorithm can be seen as a projected/kernelized stochastic gradient descent of $\\KL{\\mu}{\\pi^*}$ in the space of probability distributions. Further investigation is necessary to answer these questions precisely.\n\n1. Shi et.al.'22, A Finite Particle Rate for SVGD\n2. Hazan'19, Optimization for ML\n3. Welling et.al.'11, Bayesian Learning via SGLD\n4. Das et.al.'23, Utilising the CLT Structure in SGLD\n5. Korba et.al.'20, A Nonasymptotic Analysis of SVGD\n6. Salim et.al.'21, Convergence Theory for SVGD in Pop. Limit\n7. Balasubramanian et.al.'22, Towards a Theory of Non-Logconcave Sampling\n8. Polyak et.al.'92, Acceleration of Stochastic Approx. by Averaging\n9. Shamir'12, Open Problem: Is Averaging Needed for Str. Cvx. SGD?\n10. Rakhlin et.al.'12, Making GD Optimal for Str. Cvx. Stochastic Opti.\n11. Shalev-Shwartz et.al.'11, Pegasos"}, {"review_id": "HdY3B3L00s", "reviewer": "Reviewer_ArA7", "summary": "The authors propose a implementable stochastic approximation algorithm based on Stein Variational Gradient Descent, which the idea is based on a stochastic approximation at the probability measure level.  The efficiency and convergence analysis of the proposed algorithm, i.e. VP-SVGD and GB-SVGD,  are presented. A better convergence rate for the proposed algorithm is proved given a weaker assumption for the potential function", "questions": "1. What is exactly the mild assumption for potential function F, which is weaker then Poincare and Talagrand inequality? How significantly different for this condition, e.g. regarding the proof ?\n\n2. Section 3 is not well presented. The push-forward map $(\\cdot)_{\\sharp}$ is not defined, but only mentioned, which is not clear. But this is a key step in designing the algorithm. \n\n3. Section 4, the notation for filtration is not good, $\\mathcal F_t$ should be measurable up to time $t$, but here it is measurable up to time $t-1$, which results the notation $\\mu_t|\\mathcal F_t$ confusing. \n\n4. Up this this point,  updates in (2) is not rigorously derived, but only intuitively mentioned. Then the algorithm (3) is based on (2), which is not clear to me why (3) is a stochastic approximation? It seems to be deterministic given the previous time step particle values. The same questions for $\\mu_t|\\mathcal F_t$, the conditional measure based on updated in (3) does not seem to be random. If there is a better way to present this idea, please clarify. \n\n5. The random function $g_t(\\mathbf X)$ is not clear, where does the randomness come? \n\n6. the mini batch size comes in Algorithm 1. which does not show before in section 4. There is a gap between the Algorithm 1 & 2  and (2)(3)(4). \n\n7. What is exactly the role of countably infinite many particles, as in the algorithm only $KT+n-1$ are used? I seems that this assumption is important, if this can be explained more clear, it should help improving the presentation. ", "limitations": "see above", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The authors propose a new algorithm, a stochastic approximation at the probability measure level according to the authors, to study the SVGD. The focus is to improve the convergence rate and make the algorithm more efficient. The idea of the proposed algorithm in (3) seems to be new. The intuition and design of the algorithm is interesting, and it seems to work as shown in the numerical experiments. ", "weaknesses": "The reviewer feels that the intuition and the theoretical results have some gaps. To be more precise, some of the arguments are only explained at the intuition level without rigorous proof. It might be possible the reviewer missed the key point of the proof, if this is the case, please correct me. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\newcommand{\\vxl}[1]{\\vx^{(l)}\\_{#1}} \\newcommand{\\s}[1]{\\\\{0, \\dots, #1\\\\}} \\newcommand{\\muFt}{\\mu\\_t | \\cF\\_t} \\newcommand{\\xtt}{\\vx^{(t)}\\_t} \\newcommand{\\XS}[1]{\\vx^{(0)}\\_0, \\dots, \\vx^{(#1)}\\_0}$Thanks for your helpful feedback! The reviewer mentions that some of our proofs are not rigorous/complete. We believe all our results are proved fully rigorously, with many proofs shown in the Appendix (as is common for NeurIPS papers) due to page limits. We are happy to discuss any specific proofs which the reviewer believes are not rigorous. We hope our response below addresses your questions\n## Assumption on $F$\nAssumption 2 imposes a mild growth condition on $F$. As stated in Sec. 5 (Lines 217-223) & proved in Appendix B (Lines 526-573) , Assmp. 2 is implied by Talagrand's inequality $T\\_1$ (used by prior works on SVGD [1,2]), as well as Poincare inequality (considered a mild condition in sampling [3]). We use Assmp. 2 to bound $\\\\|g_t\\\\|\\_{\\mathcal{H}}$ (Lemma 2) which is essential for applying the descent lemma for VP-SVGD (Lemma 1)\n## Defn. of Pushforward\nIt is defined in Sec. 2, Lines 126-127\n## Batchsize in VP-SVGD\nFor ease of exposition, we motivate VP-SVGD in Sec. 4 using batchsize $K=1$ (see Line 178). Our analysis of VP-SVGD in Appendix C presents a complete proof for any $K\\geq1$ (Appendix C.1) \n## Derivation of Eqn. 2\nEqn. 2 refers to the dynamics of ordinary SVGD in the mean-field (i.e. infinite particle) limit, which has been well established in several prior works [1,4,5]. Due to page limits & the fact that mean-field SVGD is the key object of study in many prior works, we provide a brief exposition of Eqn. 2 in Sec. 3, where we also refer the readers to prior works [1,5] for a more detailed treatment\n## Notation for Filtration\nWe use the comp. sci. convention of starting indices from zero. Thus, the particles are indexed as $\\vxl{t};l,t\\geq0$. Thus, for $K=1$ we denote the filtration $\\cF_t$ as $\\cF_t = \\sigma(\\\\{\\vxl{0}| l \\in \\s{t-1} \\\\})$. \n## $g_t$ is a Random Function\nFrom Sec. 4, Line 190, we infer that $g_t(\\vx) = h(\\vx, \\xtt)$ is a random vector $\\forall \\vx \\in \\mathbb{R}^d$ since $\\xtt$ is a random vector. Thus, $g_t$ is a random function due to the randomness induced by $\\xtt$\n## $\\muFt$ is a Random Measure\nFor $K=1$, $\\muFt$ is the conditional distribution of the random vector $\\xtt$ when conditioned on the virtual particles $\\XS{t-1}$, i.e., $\\muFt = Law(\\xtt | \\XS{t-1})$ (Sec. 4 Lines 186-189). Since $\\muFt$ is a conditional distribution, it can be expressed as a probability kernel $\\muFt = \\mu\\_t(.;\\XS{t-1})$ (see [6, Sec. 4.1.3]). Since $\\XS{t-1}$ are random vectors, $\\mu_t | \\cF_t := \\mu_t(\\cdot ; \\mathbf{x}^{(t)}_0, \\dots, \\mathbf{x}^{(t-1)}_0)$ is a random probability distribution, where the randomness comes from $\\XS{t-1}$\n## VP-SVGD as a Stochastic Approx. to Mean-Field SVGD\nVP-SVGD is an unbiased stochastic approximation to mean-field SVGD **in the space of probability measures**. This differs significantly from the path-space stochastic approximations usually considered in the literature (see Sec. 1.2 Lines 99-109). We briefly describe this as follows (see Section 4, Appendix C & our common response for details). From (3), we note that $\\vxl{t+1} = (I - \\gamma g_t)(\\vxl{t}) \\ \\forall l\\geq t+1$ & $g_t(\\vx) = h(\\vx, \\xtt)$ is an $\\cF\\_{t+1}$ measurable random function (as $\\xtt$ is $\\cF\\_{t+1}$ measurable). Now, $\\forall t \\geq0,l\\geq t;\\vxl{t}$ depends only on $\\XS{t-1}, \\vxl{0}$ and $Law(\\xtt |\\XS{t-1}) = \\muFt$. Thus, $\\forall l\\geq t+1,Law(\\vxl{t}|\\XS{t})=Law(\\vxl{t}|\\XS{t-1})=\\muFt$ and $Law(\\vxl{t+1}|\\XS{t})=\\mu\\_{t+1} | \\cF\\_{t+1}$. Hence, The dynamics of VP-SVGD in the space of measures is $\\mu\\_{t+1} | \\cF_{t+1} = (I - \\gamma g_t)\\_{\\\\#} \\muFt$. Finally, note that $\\bE[g_t(\\vx)|\\cF_t] = h_{\\muFt}(\\vx)$ which is the kernelized Wasserstein gradient of $\\KL{.}{\\pi^*}$. Comparing with the mean-field SVGD update $\\mub\\_{t+1} = (I - \\gamma h_{\\mub\\_t})\\_{\\\\#} \\mub_t$, we conclude that VP-SVGD is indeed an unbiased stochastic approximation to mean-field SVGD in the space of measures\n## Countably Infinite Particles\nOur analysis of VP-SVGD considers the dynamics of countably infinite particles, whose initial positions $(\\vxl{0})\\_{l\\geq0}$ are drawn i.i.d. from an initial density $\\mu_0$. **This is done only for the purposes of our analysis** (as Algo. 1 needs only $KT+n$ particles to converge) **i.e., the particles $(\\vxl{0})_{l\\geq n+KT}$ are fictitious and are not used anywhere except for our proofs**. The advantages of this approach is described in Section 1.2 Lines 110-120, which we summarize below:\n\nAs discussed in Sec. 3, mean-field SVGD is analyzed by tracking the KL divergence, i.e., $\\KL{\\mub_t}{\\pi^*}$. This approach doesn't apply to finite particle SVGD since the empirical measure $\\hmu_t$ of $n$ particles does not admit a density w.r.t the Lebesgue measure, i.e., $\\KL{\\hmu_t}{\\pi^*}=\\infty$. To overcome this, we note that the empirical measure of countably infinitely many i.i.d random vectors is almost surely equal to it's population measure by Strong Law of Large Numbers [6]. Thus, in each timestep $t$, we consider countably infinitely many conditionally i.i.d. samples from $\\muFt$. By choosing $\\mu_0$ such that $\\KL{\\mu_0}{\\pi^*}<\\infty$, we ensure $\\muFt$ admits a density at each step using Lemmas 1 & 2, which allows us to track $\\KL{\\muFt}{\\pi^*}$. Our algorithm design ensures that VP-SVGD needs only $KT+n$ particles to output $n$ conditionally i.i.d samples from $\\muFt$. *We contrast this to mean-field SVGD which actually requires infinite particles for exact implementation, and thus, is not practically realizable*.\n\n1. Shi et.al.'22, Finite-Particle Rate for SVGD\n2. Salim et. al., Convergence Theory for SVGD Under Talagrand's Inequality T1\n3. Chewi et.al.'21 LMC from Poincare to LSI\n4. Liu'17, SVGD as Gradient Flow\n5. Korba et.al.'20,  Non-Asymptotic Analysis of SVGD\n5. Durrett'05, Probability Theory and Examples"}]

Author rebuttal:
$\newcommand{\cF}{\mathcal{F}} \newcommand{\vx}{\mathbf{x}} \newcommand{\mub}{\bar{\mu}} \newcommand{\KL}[2]{KL\left(#1||#2\right)} \newcommand{\bE}{\mathbb{E}} \newcommand{\KSDs}[3]{KSD^{2}\_{#1}(#2||#3)}$ 
We thank the reviewers for their thoughtful comments & feedback that have significantly helped improve our work. We have updated our draft to incorporate their suggestions (e.g. adding a table of past works as suggested by Reviewer 9R2A, further discussion of limitations & future work as suggested by Reviewer T9Sw). 

**Motivated by Reviewer T9Sw's suggestions, we show that for both VP-SVGD & GB-SVGD, the exponent of $n$ in the finite-particle rates (Corollary 2 & 3) can be made dimension free**. We note that the key lemmas required to prove this were already present in our work. We discuss this further below.

**If permitted by the Area Chair & the reviewers, we would be happy to share a fully anonymized version of our updated draft**

We answer some common questions raised by the reviewers below & address specific queries in the individual responses

## Comparing VP-SVGD to SVGD & Concept of Virtual Particles

The reviewers asked several insightful questions on the similarities & differences between SVGD & VP-SVGD, & on the motivation behind virtual particles. We hope to address these as follows: 

We recall several prior works ([1,2,3,4]) which show that SVGD is a finite-particle approximation of the kernelized/projected Wasserstein gradient descent of the KL divergence (i.e. $\KL{.}{\pi^*}$), in the infinite dimensional space of probability measures. This approximation becomes exact in the mean-field (i.e. infinite particle) limit, such that the mean-field SVGD update is given  by  $\mub_{t+1} = (I - \gamma h_{\mub\_t})\_\\# \mub_{t+1}$ ($\mub_t$ is a probability measure & $h_{\mub_t}$ is the kernelized Wasserstein Gradient, See Sec. 2 & 3).

The mean-field update is not computationally implementable as it describes a dynamical system in an infinite dimensional space. To this end, SVGD was originally derived in [1] by first deriving the mean-field dynamics, & then deploying a tractable particle-based Monte Carlo approximation of the update ([1, Sec. 3.2], [2, Sec. 2], [3, Sec. 2.4.1]). Notably, at iteration $t$, SVGD uses $n$ particles $(\vx^{(l)}\_{t})\_{0 \leq l \leq n-1}$ to approximate $\mub_t \approx \tfrac{1}{n} \sum\_{l=0}^{n-1}  \delta_{\vx^{(l)}\_{t}}$ & **reuses the same particles** to approximate $h_{\mub\_{t}} \approx \tfrac{1}{n} \sum_{l=0}^{n-1} h(., \vx^{(l)}\_{t})$. This is a **biased discretization** of the mean-field update (as $Law(\vx^{(l)}\_{t}) \neq \mub_t$ & ${h}\_{\mub\_{t}} \neq \tfrac{1}{n} \sum_{l=0}^{n-1} \bE[h(., \vx^{(l)}\_{t})]$) due to its complex inter-particle dependencies. 

VP-SVGD, like ordinary SVGD, is also a particle based approximation of the mean field SVGD updates. The key difference between the two is that **VP-SVGD is an unbiased stochastic approximation (in the space of measures) to the dynamics of mean-field SVGD**, which can be implemented exactly with only finite particles (see Section 1.2 Lines 99-109 & Section 4). This is achieved by using **$K$ virtual particles in each iteration to construct an unbiased stochastic approximation of $h\_{\mu_t | \cF_t}$.** (via the function $g_t$) & **$n$ real particles to approximate $\mu_t | \cF_t$**. From the lens of finite dimensional optimization, this is similar to how Stochastic Gradient Descent is an unbiased stochastic approximation to population-level Gradient Descent. To justify this, we recall the VP-SVGD update $\mu_{t+1}|\cF_{t+1} = (I - \gamma g_t)\_\\# \mu_t | \cF_t$. Note that, when conditioned on the virtual particles: 1. $\bE[g_t(\vx) | \cF_t] = h\_{\mu_t | \cF_t}$ (i.e. the dynamics is an unbiased stochastic approximation) 2. The $n$ real particles $(\vx^{(l)}\_t)\_{KT \leq l \leq KT+n-1}$ are i.i.d draws from $\mu\_t | \cF\_t$ (discussed in Section 4 and proved in Appendix C). To this end, **the use of virtual particles allows VP-SVGD to exactly track the time-evolution of $\mu_t | \cF_t$ using only finite particles. Additionally, it ensures that the particles $(\vx^{(l)}\_t)\_{KT \leq l \leq KT+n-1 }$ are conditionally i.i.d samples from $\mu_t | \cF_t$**. This allows us to derive fast finite-particle convergence rates.   

## Dimension-Free $n$ Exponent in Finite-Particle Rates

Based on the insightful feedback of Reviewer T9Sw, we show that the exponent of $n$ in our finite-particle rates can be made dimension-free. For subgaussian $\pi^*$, we show that VP-SVGD has a finite-particle KSD rate of $O(\tfrac{d^{1/4}}{n^{1/4}} + \tfrac{d^{1/2}}{n^{1/2}})$ while GB-SVGD has a finite-particle KSD rate of $O(\tfrac{d^{1/3}}{n^{1/12}} + \tfrac{d^{1/2}}{n^{1/2}})$. We believe the constant factors in the exponents (for both algorithms) may be further improved via careful analysis. We sketch the proof of this result in our response to Reviewer T9Sw and our updated draft presents a complete proof for more general targets (including subexponential $\pi^*$ and beyond). This result uses two novel techniques: 1. A new KSD bound between the empirical measures of the outputs of VP-SVGD & GB-SVGD 2. A direct approach for bounding $\bE[\KSDs{\pi^*}{\hat{\mu}^{(n)}}{\pi^*}]$  in terms of $\bE[\KSDs{\pi^*}{\mub}{\pi^*}]$ (where $\hat{\mu}^{(n)}$ is the empirical measure of VP-SVGD outputs and $\bar{\mu}$ is the population measure) which does not invoke any empirical-to-population Wasserstein bounds and consequently avoids the $n^{-\Theta(1/d)}$ dependence of Lemma 8 (which is unimprovable in general, see [5, Sec. 3] and [6])

1. Liu and Wang'16, SVGD
2. Liu'17, SVGD as Gradient Flow
3. Salim et. al.'21,  Convergence Theory for SVGD in Pop. Limit
4. Korba et. al.'20,  Nonasymptotic Analysis for SVGD
5. Lei'18, Convergence of Empirical Measures under Wasserstein Distance
6.  Fournier. et.al.'13, Rate of Convergence in Wass. Distance of the Empirical Measure


Meta-review: This paper make significant progress on a major open problem in the Stein variational gradient descent literature: namely, finite-particle convergence guarantees for SVGD algorithms.
Decision: Accept (spotlight)