Improved Stein Variational Gradient Descent with Importance Weights
Authors: Lukang Sun
Peter Richtárik
Venue: Submitted to ICLR 2023 (2023)
Keywords: SVGD
Importance Sampling
Importance Weights
Sampling
R\'enyi Divergence
KL-divergence

Abstract: Stein Variational Gradient Descent~(\algname{SVGD}) is a popular sampling algorithm used in various machine learning tasks. It is well known that \algname{SVGD} arises from a discretization of the kernelized gradient flow of the Kullback-Leibler divergence $\KL\left(\cdot\mid\pi\right)$, where $\pi$ is the target distribution. In this work, we propose to enhance \algname{SVGD} via the introduction of  {\em importance weights}, which leads to a new method for which we coin the name  \algname{$\beta$-SVGD}. In the continuous time and infinite particles regime, the time for this flow to converge to the equilibrium distribution $\pi$, quantified by the Stein Fisher information, depends on $\rho_0$ and $\pi$ very weakly. This is very different from the kernelized gradient flow of Kullback-Leibler divergence, whose time complexity depends on $\KL\left(\rho_0\mid\pi\right)$. Under certain assumptions, we provide a descent lemma for the population limit \algname{$\beta$-SVGD}, which covers the descent lemma for the population limit \algname{SVGD} when $\beta\to 0$. We also illustrate the advantages of \algname{$\beta$-SVGD} over \algname{SVGD} by simple experiments.

Under review as a conference paper at ICLR 2023
IMPROVED STEIN VARIATIONAL GRADIENT DESCENT WITH IMPORTANCE WEIGHTS
Anonymous authors Paper under double-blind review
ABSTRACT
Stein Variational Gradient Descent (SVGD) is popular sampling algorithm used in various machine learning tasks. It well known that SVGD arises from a discretization of the kemnliizdd gradient flow of the Kullback-Leibler divergence DKL (: π)) where æ the target distribution. In this work, we propose to enhance SVGD via the introduction of importance weights, which leads to for which we coin the name 3-SVGD. In the continuous time and infinite particles regime, the time for this flow converge the equilibrium distribution n, quan- tified by the Stein Fisher information, depends on Pu and π very weakly. This is very different from the kernelized gradient flow of Kullback-Leibler divergence. whose time complexity depends on DKL. (Po T).. Under certain assumptions, we provide descent lemma for the population limit 3-SVGD, which covers the de- scent lemma for the population limit SVGD when B + O. We also illustrate the advantages 3-SVGD over SVGD by simple experiments.
method
INTRODUCTION
The main technical task of Bayesian inference is estimate integration with respect to the posterior distribution
π (xx x e VV(x,
where V Rd IR is potential. In practice, this is often reduced to sampling points from the distribution т. Typical methods that employ this strategy include algorithms based on Markov Chain Monte Carlo (MCMC), such as Hamiltonian Monte Carlo (Neal 2011), also known as Hybrid Monte Carlo (HMC) (Duane et al., 1987, Betancourt, (017). and algorithms based on Langevin dynamics Dalalyan & Karagulyan| 2019: Durmus Moulines 2017 Cheng et al., 2018).
One the other hand, Stein Variational Gradient Descent (SVGD)-a different strategy suggested by Liu & Wang (2016) based on an interacting particle system. In the population limit, the interacting particle system can be seen as the kernelized negative gradient flow of the Kullback- Leibler divergence
DKL (p (T) == log (2) (x) dp(x);
see (Liu 2017 Duncan et al. 2019). SVGD has already been widely used in variety of machine learning settings, including variational auto-encoders (Pu al. 2017). reinforcement learning (Liu
et al. 2017). sequential decision making (Zhang et al. 2018 2019), generative adversarial net-
works (Tao et al. 2019) and federated learning (Kassab & Simeonel 2022). However, current theo-
retical understanding of SVGD is limited to its infinite particle version (Liu 2017 Korba et al., 2020)
Salim et al. 2021 Sun et al. 2022), and the theory on finite particle SVGD is far from satisfactory.
Since SVGD is built discretization of the kernelized negative gradient flow of we can learn about its sampling potential by studying this flow. In fact, a simple calculation (for example, see
Korba et al. (2020) reveals that
min
Istein (ps ②) < (po(p))
(
0
where Istein (px T) is the Stein Fisher information (see Definition 2 of P, relative to i, which is typically used to quantify how close to a are the probability distributions (p+) generated along

---

Under review as a conference paper at ICLR 2023
this flow. In particular, if our goal is to guarantee min Istein (Ps xx) S E, result 2 says that need take
(po(polm))
Unfortunately, and this the key motivation for our work, the quantity the initial KL divergence
DKL (eo I can be very large. Indeed, it can be proportional to the underlying dimension, which highly problematic in high dimensional regimes. Salim et al. (202I) and Sun et al. (2022) have recently derived an iteration complexity bound for the infinite particle SVGD method. However, similarly to the time complexity of the continuous flow, their bound depends on DRr. (po .T.
1.1 SUMMARY OF CONTRIBUTIONS
In this paper, we design a family of continuous time which we call 3-SVGD by combining importance weights with the kernelized gradient flow of the KL-divergence. Surpris- ingly, we prove that the time for this flow to converge to the equilibrium distribution т, that is minocest (ps T) I with (p=):=D generated along 3-SVGD flow, can be bounded by (+++] when B (),,0). This indicates that the importance weights can potentially accel- erate SVGD. Actually, we design 3-SVGD method based on a discretization of the 3-SVGD flow and provide descent lemma for its population limit version. Some simple experiments in Appendix D verify our predictions.
We summarize contributions in the following:
A new family of flows. We construct a family of continuous time flows for which we coin the name 3-SVGD flows. These flows not arise from time re-parameterization of the SVGD flow since their trajectories are different, nor can they be seen as the kernelized gradient flows the Rényi divergence.
Convergence rates, When 3 > O, this returns back to the kernelized gradient flow of the KT.-divergence (SVGD flow); when E (-1,0), the convergence rate of 3-SVGD flows is significantly improved than that of the SVGD flow in the case DKL (Po T) is large. Under Stein Poincaré inequality, we derive an exponential convergence rate of 2-Rényi divergence along 1-SVGD flow. Stein Poincaré inequality is proved to be weaker than Stein log-Sobolev inequality, however like Stein log-Sobolev inequality, is not clear to when it does hold.
Algorithm. We design 3-SVGD algorithm based on discretization of the 3-SVGD flow and we derive descent lemmas for the population limit 3-SVGD.
Experiments. Finally, we do some experiments to illustrate the advantages of 3-SVGD with negative B. The simulation results on 3-SVGD when B changes from positive to negative corroborate our theory.
1.2 RELATED WORKS
The SVGD sampling technique was first presented in the fundamental work of Liu & Wang (016))
Since then, number of SVGD variations have been put out. The following is a partial list: Newton
version SVGD (Detommaso et al., 2018). stochastic SVGD (Gorham et al. 22000). mirrored SVGD
(Shi et al. 2021, random-batch method SVGD (Li al. 2020) and matrix kernel SVGD (Wang et al. 2019). The theoretical knowledge of SVGD Is still constrained to population limit SVGD. The first work demonstrate the convergence of SVGD in the population limit was by Liu (017)): Korbal et al. (2020) then derived a similar descent lemma for the population limit SVGD using different approach. However, their results relied on the path information and thus were not self-contained, to provide clean analysis, Sallm et al. (2021) assumed Talagrand's Ti inequality of the target distribution π and gave the first iteration complexity analysis terms dimension d. Following the work of (aalm et al. (2021); Sun al. (2022) derived descent lemma for the population limit SVGD under a non- non-smooth potential V.
In this paper, consider a family of generalized divergences, Rényi divergence, and SVGD with importance weights. For these two themes, we name a few but non-exclusive related results. |Wang et al. 2018) proposed to use the /ddivergence instead of KT--divergence in the variational inference
2

---

Under review as a conference paper at ICLR 2023
problem, here f is convex function; Yu al. (2020) also considered variational inference with f-divergence but with its dual form. Han & Liu (2017) considered combining importance sampling with SVGD, however the importance weights were only used to adjust the final sampled points but not the iteration of SVGD as in this paper: Liu & Lee (017) considered importance sampling, they designed black-box scheme calculate the importance weights (they called them Stein importance weights in their paper) of any set of points.
2
PRELIMINARIES
We assume the target distribution т x e-V, and we have oracle to calculate the value e -V(a) for all R.
2.1 NOTATION
Let x = (#1...., . (31...., E Rd, denote (z. = E Jals and ||>|| == V (z.x)). For square matrix B Raxd the operator norm and Frobenius norm of B are de- fined respectively by ||Bllpp == o B) and | = v E Ei= Bī.. respectively, where e denotes the spectral radius.
easy to verify that || [| op S |B]| Let P2([R() denote the space of probability measures with finite second moment; that is, for any l E P2((R)) we have ||-|²² du(x)= < too. The Wasserstein 2-distance between p. J P2(R)) is defined by
VJ v1? dn(x, v),
W2 (p.H): = inf
mET(A.)
where I' (p, (I) is the set of all joint distributions defined on IR x Rd having and as marginals. The forh-forward distribution of p E P2 (Rd) by map T Rd + Rd denoted by Typ, is defined as follows: for any measurable set Ω E RR. T=p (S2) : p (9)) By defini- tion of the push-for nush-forward distribution,
not hard to verify that the probability densities satisfy Ty TTp(T (z))(())) det D (x)) = p(z), where D T is the Jacobian matrix of T. The reader can refer to
Villani 2009) for more details.
2.2 RÉNYI DIVERGENCE
Next, define the Rényi divergence which plays important role in information theory and many other areas such as hypothesis testing (Morales González et al., 2013) and multiple source adaptation (Mansour et al. 2012).
Definition (Rényi divergence) For two probability distributions and μ on Rd and < μ. the Rényí divergence of positive order is defined
+ log
(s(z)
(x) (z) d)(())
0< a a11
Da(p
log (1) (x) dp(x)
a=
If is not absolutely continuous with respect to μs, we set Dalp | n) = cc. Further, we denote DRL. (4) = D, p).
Rényi divergence is nen-negative, continuous and non-decreasing in terms of the parameter ag specifically, have DKL (p μ4 lim (a(p μ). More properties of Rényi divergence can be found in a comprehensive article by Van Erven & Harremos (2014). Besides Rényi divergence, there are other generalizations of the KT.-divergence, e.g., admissible relative entropies (Arnold) et al. 200T).
2.3
BACKGROUND ON SVGD
Stein Variational Gradient Descent (SVGD) is defined on Reproducing Kernel Hilbert Space (RKHS) Ho with non-negative definite reproducing kernel k Rdd x Rd R The

---

Under review as a conference paper at ICLR 2023
key feature of this space is its reproducing property:
f(x) = (f(.), Ho vf E Hos
(4)
where (,,) is the inner product defined on Ho- Let H be the d-fold Cartesian product of Ho- That is, f E H if and only if there exist fI.". fa Ho such that f (fi...., fa) Naturally, the inner product on H is given by
(f.9) Σ (f.. (f. f - fa) H.
(oI....,.ha 9a) E H.
(5)
For more details of RKHS, the readers can refer to Berlinet & Thomas-Agnan 2011).
It is well known (see for example Ambrosio al. (2005) that v log (+) is the Wasserstein gradient of DKL (- nt) at p E (R.)). Liu & Wang (2016) proposed a kernelized Wasserstein gradient of the KL-divergence, defined by
9p(x:) == f k(r, (a (4) (v) dp(y) E H.
(6)
Integration by parts yields
(r(x) = [V log ग (y)A{x, + (2,((,)) y)l dp(y).
Comparing the Wasserstein gradient V log ( with we find that the latter can be easily approx- imated by
90(x)= ~ 9p
v log logT(z.)((,,z)) + Va,k(z,
with م = N E 6eg and (x)) sampled from p. With the above notations, the SVGD update rule
24
V log (22 2 i= i N,
(9)
where y is the siep-size, can be presented in the compact form + - 19a) # P. When we talk about the infinite particle SVGD, or population limit SVGD, we mean + (1 - -gg)) 4 The metric used in the study of SVGD is the Stein Fisher information or the Kernelized Stein Discrep- ancy (KSD).
Definition 2 (Stein Fisher Information) Let p E P2(B)). The Stein Fisher Information of rela- five to n is defined by
Istein ( ④) ff ((. v) log (2) (x), V log (2) (v)) dp(x) dply)-
(10)
A sufficient condition under which lim Istein (Pn T implies Pre + x weakly can be found in Gorham Mackey (2017). which requires: the kernel to the form k(a, v)
(c² + || w112) for some 0 and 0 (-1,0); ii) e to be distant dissipative; roughly speaking, this requires to be convex outside a compact set, see Gorham & Mackey (2017) for an accurate definition.
In the study of the kernelized Wasserstein gradient 7 and its corresponding continuity equation
8p: at
+ div (p:gp.) = 0.
Duncan al. 2019) introduced the following kernelized log-Sobolev inequality to prove the expo- nential convergence of DKr. (pr т) along the direction 7
Definition (Stein log-Sobolev inequality) We say x satisfies the Stein log- hog-Sobolev inequality with constant À > 0 if
(KI.PP m) S 2X Iteiin (p m).
(11)
While this inequality can guarantee exponential convergence rate of Pt to n, quantified by the KL-divergence, the condition for π to satisfy the Stein log- Sobolev inequality is very restrictive. In fact, little is known about when [1] holds.
4

---

Under review as a conference paper at ICLR 2023
303 teralin, betavd
300" beration betb.ud
300
6.35
035
1.30
0:1
133
Figure 1: The performance of 3-SVGD with three choices of 3, but using the same step-size. The blue dashed line is the target distribution π:: the Gaussian mixture (222, 1) (6, 1). The green solid line is the distribution generated by 3-SVGD after 100 iterations; see Appendix D for more results and details.
3 CONTINUOUS TIME DYNAMICS OF THE 3-SVGD FLOW
In this section, we mainly focus on the continuous time dynamics of the 3-SVGD flow. Due to page limitation, we leave all of the proofs to Appendix
3.1 3 3-VVGD FLOW
In this paper, a flow refers to some time-dependent vector field v, Rd + Rdd. This time-dependent vector field will influence the mass distribution on Rd by the continuity equation or the equation of conservation of mass
3p: + div (pre)) = 0,
(12)
readers can refer to Ambrosio et al. (005) for more details.
Definition 4 (3-SVGD flow)
Given weight parameter 3 E (-1, +00), the 3-SVGD flow is given
by
of (x) (z): : - h(2, V) log (+) (v) dpc(y).
(13)
Note that when B = 0, this is the negative kernelized Wasserstein gradient
Note that we can not treat 3-SVGD flow as the kernelized Wasserstein gradient flow of the (3 1)- Rényi divergence. However, they are closely related, and we can derive the following theorem.
Theorem (Main result) Along the 3-SVGD flow
13
we have
DDg4iteoln (eolm)
B>
TB(++))
min Iteein (pt x) (E
(14)
T
E (-1,0)
TB(8+1)
Note the left hand side of 14 is the Stein Fisher information. When 3 decreases from positive to negative, the right hand side of [14] changes dramatically; it appears to be independent of Po and If we do not know the Rényi divergence between Pu and seems the best convergence rate is obtained by setting B = that is
min Istein (pe TT) < 4. (E[0,27
It is somewhat unexpected to observe that the time complexity is independent of Po and to be more precise, that it relies only very weakly on Po and æ when E (-1,0). We wish to stress that this is not achieved by time ce-parameterization. In the proof of Theorem I we can
In fact, in the proof in Appendix we know stronger result. When E (-1,0), the right hand side (PPps
of (14 is only weakly dependent po and и and should be
which is less than
7(94411)
TP0441
5

---

Under review as a conference paper at ICLR 2023
the term (5/p))² in 3-SVGD flow (13 is utilizedd to cancel term (P//=) in the Wasserstein gradient (3 + Ré-nn divergence. Actually, when 8 E (-1,0), this term has an added ad- vantage and can be seen the acceleration factor in front of the kernelized Wasserstein gradi- ent of -T--divergence. Specifically, the negative kernelized Wasserstein gradient of KT--divergence (x) = - ka,,, y) V log( _ (y)dpr(y) is the vector field that compels Pr approach n, while (T/p.)" f (x) is big (roughly speaking this means x is close to the mass concentration region of Pt but away from the one of тT), this factor will enhance the vector field at point x and force the mass around x move faster towards the mass concentration region of т; on the other hand, if (5/e.) ) (x) is small (this means is already near to the mass concentration region of x), this factor will weaken the vector field and make the mass surrounding r remain within the mass concentration region of æ. This is the intuitive justification for why, when 3 E (-1, 0), the time complexity for 3-SVGD flow to diminish the Stein Fisher information only depends on pa and π very weakly.
Remark While it may seem reasonable to suspect that the time complexity of the B-SVGD flow with 3 f -1 will also depend on Po and it very weakly, surprisingly, this is not true. In fact, we can prove that (see Appendix B
min Istein (pe T) S e 1>D 1>D-p(mleo) [E|O,2]
[TB(8+1]]
Dic.((rlpu), The regime when 3 S -1 is similar Letting 3 11, we get min Istein (px I π) S - to the 3 > regime in Theorem 7 the weak dependence on Po and π is caused by the concavity of the function S on E R when a = 3 10.
which heavily depends on Po and n. Mathematically speaking,
3.2 SVVVGD FLOW AND THE STEIN POINCARÉ INEQUALITY
Functional DKL (- is non-symmetrie; that is, DKL T) + DKL (T 1). and so their Wasser- stein gradient. The Wasserstein gradient of DKL (T at distribution E (P) is - - , (see Appendix A or, to put it another way, / V log( f), which may be regarded as the non-kernelized & 1-SVGD flow (module minus sigh) when compared [33. To conclude, the 1-SVGD flow
(x) = P. (z) k(z V log (#) (v) dp)
(15)
is the negative kernelized Wasserstein gradient flow of DKL. (T I.). Next, we will study the expo- nential convergence of 2-Rényi divergence along 1-SVGD flow under the Stein Poincaré inequality.
Definition 5 (Stein Poincaré inequality) We say that a satisfies the Stein Poincaré inequality with constant À > 0 if
lgl dm S SS k(x, (Vg(z), Vg(v)) (x) dr(2),,
(16)
for any smooth with I dx = 0.
2019) also introduced the Stein Poincaré inequality, they presented it in differ- form. Just Poincar inequality is a linearized log-Sobolev inequality (see for example (Bakry 2014] Proposition 1.3))). Stein Poincaré inequality is also a linearized Stein log-Sobolev in- equalit ity M Although Stein Poincaré inequality is weaker than Stein log-Sobolev inequality, the condition for it to hold is quite restrictive, as in the case of Stein log- Sobolev inequality; see the discussion in (Duncan et al. 2019 Section 6).
While Duncan et al.
ct al.
Lemma 1 (Stein log-Sobolev implies Stein Poincaré) If satisfies the Stein log-Sobolev inequal- ity (77) with constant > 0, then it also satisfies the Stein Poincaré inequality with the same constant X.
While the proof of the above lemma is routine task, for completeness we provide it in Appendix B The following theorem inspired by Cao et al. (2019), in which they proved the exponential conver- gence of Rényi divergence along Langevin dynamic under a strongly convex potential V. However, due to the structure of 1-SVGD flow, we can only prove the results for a a-Rényi divergence with (0,2) 2).

---

Under review as a conference paper at ICLR 2023
Theorem
Suppose satisfies the Stein Poincaré inequality with constant À > 0. Then the flow
13
satisfies
D2 (ee ()) S CDD (po ④)
(17)
P2(pplx)_ D2(pol7)
where C
Since Da, (p] Daz (pl x) for any 0 < 01 02 oc, the exponential convergence of a-Rényi divergence with a E (0 can be easily deduced from 17
Corollary Suppose л satisfies the Stein Poincaré inequality with constant > 0. Then the flow satisfies
13
Da (pel T)) S C. _1 for all a E (0, where C' = (poo))))
Da (pol σ) e
(18)
4 THE 3-SVGD ALGORITHM
The 8-SVGD algorithm proposed here is sampling method suggested by the discretization of the 3-SVGD flow Our method reverts to the traditional SVGD algorithm when O.
As in SVGD, the integral term in the B-VVGD flow 13 can be approximated by 8). However,
when 3 +f 0, we have to estimate the extra importance weight term (*/or) We can use the kernel method [Silverman] 2018) to estimate Pr. given points sampled from Pr. The idea behind the kernel density estimation simple. Assuming that Dirac 5(-) can be weakly approximated by kernel K(-),
that is for any bounded smooth function f E Cg (R""), we have
lim 1 I' fx)) (7) dx - f(=)(())d f(0).
R-0 ha
Then for p. smooth probability density function IRd we have
p(z) 8 - ((x-))p(u) dy = Ra [K((TT)) ply dy Nh Σ )( p(x),
with ( sampled from p. Usually, K will be a radially symmetric unimodal probability density function, for example, the standard multivariate Gaussian
mnge IT is the area of unit circle.
K Kg(x) (2m))
While unfortunately we only know the value of T(x) up to normalizing constant, this constant independent of x, allowing us to merge it into the step-size. One needs to keep mind though that (#/p.)² ) may explode from above. Therefore, in the implementation 3-SVGD we must truncate this value from above by a relatively big number M.
Remark 2 Note that the performance of kernel density estimation largely depends the sample size Parzen 1962); Devroye & Wagner (197)) and bandwidth h S/SShthhhr (20044) Optimal band- width difficult obtain even with good bandwidth selection heuristics Scout Sheather (985). Silverman 2018, Section 4.3. 1) showed that the approximately optimal bandwidth hopt in the sense of minimizing mean integrated square error (see the section in the book), should be of order N ats (see also Lemma in Appendix C suggests h ~ N b.
When lemma from Parzen 1962
4.1 NON-ASYMPTOTIC ANALYSIS FOR 3-SVGD
In this section, we study the convergence of the population limit 3-SVGD. Specifically, we establish descent lemma for it. The derivation of the descent lemma is based on several assumptions.
The first assumption postulates L-smoothness V; this is typically assumed the study of opti- mization algorithms, Langevin algorithms and SVGD.
For simplicity, we will often just call it /t3-VVG be confused with the 3-SVGD flow.

---

Under review as a conference paper at ICLR 2023
Algorithm Beta Stein Variational Gradient Descent (8-SVGD)
1: Input: The potential function V 12 - of the target distribution и & e density estimation kernel (-), the scaling parameter h. reproducing kernel k(-,)) -), set of initial particles (a. (u))im and iteration number
for 0, n
Estimate density: p.
NN EN
i I....,
Calculate weight with choice wf
A M
A Mi
choice 2: wi = -[(->x)))
A Mi //N, N, i == I...,,,,
Mi the truncating number
5: Update particles with step-size ye xft1 + at+nu Σラ [ 2) + V 2(tb
I.....N
6: end for Return: Particles (x. (I jim-
Assumption (L-smoothness) The potential function V of the larget distribution & e is L- smooth; that is,
V S L.
Our second assumption postulates two bounds involving the reproducing kernel k(.,-) and is also common when studying SVGD; see (Liu 2017, Korba et al., 2020 Salim et al. 2021 Sun et al., 2022).
Assumption Kernel is continuously differentiable and there exists [|[[ .) Ho S B and
> such that
&V,, Σ (0, s SB² Va Rdd
By the reproducing property this is equivalent to k( x) B² and Ei= 02, ky, ly=rs 2² for any x E Rd and this is easily satisfied by kernel of the form k(x,y) f(x y), where is some smooth function at point
already used by Liu 2017 Korba al. (2020), and later replaced by Salim et al.] (202T) it with a Talagrand inequality (Wasserstein distance can be upper bounded by KL-divergence) which depends on π only. However, 3-SVGD reduces the Rényi divergence instead of the KL-divergence. Since we do not have a comparable inequality for the Rényi divergence, we are forced adopt the one from Liu 2017
The third assumption
Korba et al.) 2020) here.
Assumption There exists C such that / Istein (pn ②)) s for all 0, O.1,...,
In the proof the descent lemma, the next two assumptions help us deal with the extra term (5/p.)
Note that the fourth assumption is very weak. In fact, as long as Z, (z(r, y)pn (z)p,,)) (v) is integrable on Rdd Rdd then by the monotone convergence theorem, the truncating number Mp, (6) always
attainable since (pn/=)² (x) (#/em)² A M is non-decreasing and converges point-wise to as M + +00.
Assumption 4 For any small 8 > 0, we can find M (8) > O such that A Mp.
Stein (pn 1 T) fʃ Pn) (x)
dpn(x) dpn(v) S 26. (19)
Pm
where Zn(a: v) = k( v) V log PP. (I)) V log (or) (v)).
Our fifth
and last assumption V. (*/o.) (a) (ʃ () (1)) (v)) ||- It also relatively weak, and achiev- able for example when the potential function of p. does fluctuate wildly.
a technical nature, and helps us bound
8

---

Under review as a conference paper at ICLR 2023
Assumption
v -
|
S Con (6) in the region x:
(mn
(x) S Man (6)
Though Assumptions 3 and 5 are relatively reasonable, as we stated, we do not know how to estimate constants C, p... and Cp, beforehand.
With all this preparation, we can now formulate our descent lemma for the population limit 3-SVGD when 3 E (-1 The proof can be found in Appendix B
Proposition 1 (Descent Lemma) Suppose 3 (-1,0), Istein (Pn x) 2 25 and Assumptions andd hold. Choosing
0 << 6(0pp (8)+ M
(8)) Stesin [T)
pm
0 1<T9 B Igson (p
2 Ssccin (6)+M (8])*)
(20)
(L 00
0 0<75
341
LNd (6) 10 Mpn (6))
we have the descent property
(D++1(n++1))) - DD++r(pal)) -333 1) ( Stein (Pa π)) -6).
(21)
Proposition coottains the descent lemma for the population limit SVGD Liu 2017 :: Korba et al. (220). Actually, let / and ő approach to O, the descent lemma for the population limit SVGD will be derived by L'Hospital rule. When B > O, we also have Equation (2I). however due to the sign change of -3, Equation 21 can not guarantee D3+1 (Pa+1 π) < D841 (po. T) anymore (for an asymptotic analysis, please refer to Appendix C).
The lack of descent lemma for 3-SVGD when 3 not a great loss for us, as explained in Section 3.1 negative 3 is preferable in the implementation of 3-SVGD. One can see from our experiments that 3-SVGD with negative B performs much better than the one with positive B, this verifies our theory in Section 3.7
Remark
The next corollary is a discrete time version of Theorem 1 sistent upper bound reasonable since intuitively Pn. will approach n, though we can verify this beforehand.
Letting Mp. (e) and Cp. (e) have con-
Corollary In Proposition L choose = s and suppose Assumptions 2 and 5 hold with uniformly bounded Mp. (E) and Cpa. (E), so that oy is uniformly lower bounded. Then we have at most
N Ω 3(6+1)E7
2
(22)
iterations to achieve minge (o.1.....NN N) Istein (ps T) < 3E.
+ 0 as N + oc, following Shi et al. (0221) or Korba et al. (2020). However, the existing methods either give qualitative analysis provide exponential bound under more restrictive assumptions, which can not provide useful information in
Remark We may show that W₂ + Ex=
the implementation of 3-SVGD. Interested readers can refer to Korba et al. 2020); Shi et al. 2027),
we will not include them in this paper.
5 CONCLUSION
We construct a family of continuous time flows called 3-SVGD flows on the space of probability distributions, when / (-,,0). its convergence rate is independent of the initial distribution and the target distribution. Based on 3-SVGD flow, we design family of weighted SVGD called 3- SVGD. 3-SVGD has the similar computation complexity SVGD, but achieves faster convergence rate in our analysis and experiments. We introduce 3-SVGD in this work, but there are still lots of questions we do not answer and deserve to explore, like how to tune the parameters make it more efficient, the performance of 3-SVGD in more complex model and etc.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2005.
Anton Arnold, Peter Markowich, Giuseppe Toscani, and Andreas Unterreiter. On convex Sobolev inequalities and the rate of convergence equilibrium for Fokker-Planck type equations. 2001.
Dominique Bakry, Ivan Gentil, Michel Ledoux, et Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
Alain Berlinet and Christine Thomas-Agnan. Reproducing kernel Hilbert spaces probability and statistics. Springer Science & Business Media, 2011.
Michael Betancourt. A conceptual introduction to Hamiltonian Monte Carlo. arXiv preprint
arXivv1701.02434, 2017.
Yu Cao, Jianfeng Lu, and Yulong Lu. Exponential decay of Rényi divergence under Fokker-Planck equations. Journal of Statistical Physics, 176(5): (76(5):1172-11 11-11172-11881 1184, 2019.
Xiang Cheng, Niladri S Chatterji, Peter L Bartlett, and Michael Jordan. Underdamped Langevin MCMC: A non-asymptotic analysis. In Conference learning theory, pp. 300-323. PMLR, 2018.
Arnak $ Dalalyan and Avetik Karagulyan. User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient. Stochastic Processes and their Applications, 129(12))5278-5311 2019.
Gianluca Detommaso, Tiangang Cui, Youssef Marzouk, Alessio Spantini, and Robert Scheichl. A Stein variational Newton method. Advances in Neural Information Processing Systems, 31, 2018.
LP Devroye and TJ Wagner. The l_1 convergence kernel density estimates. The Annals of Statis- tics, 7(5):1136-119, 1979.
Simon Duane, Anthony D Kennedy, Brian Pendleton, and Dunean Roweth. Hybrid Monte Carlo. Physics letters B, 195(2):216-22) 1987.
Andrew Duncan, Nikolas Nüsken, and Lukasz Szpruch. On the geometry of Stein variational gradi- ent descent. arXiv preprint 19Xiv:/912.00894, 2019.
Alain Durmus and Eric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, 27(3):1511-1587 2017.
Jackson Gorham and Lester Mackey. Measuring sample quality with kemels. In International
Conference on Machine Learning, pp. 1292-1301. PMLR, 2017.
Jackson Gorham, Anant Raj, and Lester Mackey, Stochastic Stein discrepancies. Advances in Neural Information Processing Systems, 33:17931- 2020.
Jun Han and Qiang Liu. arXiv: 174405270..0521,, 2017.
Stein variational adaptive importance sampling. arXiv preprint
Rahif Kassab and Osvaldo Simeone. Federated generalized Bayesian learning via distributed Stein variational gradient descent. IEEE Transactions on Signal Processing, 2022.
Anna Korba, Adil Salim, Michael Arbel, Giulia Luise, and Arthur Gretton. A non-asymptotic anal- ysis for Stein variational gradient descent. Advances in Neural Information Processing Systems, 33:4672-4682, 2020.
Lei Li, Yingzhou Li, Jian-Guo Liu, Zibu Liu, and Jianfeng Lu. A stochastic version of Stein vari- ational gradient descent for efficient sampling. Communications in Applied Mathematics and Computational Science, 15(1):37-63, 2020.
Qiang Liu. Stein variational gradient descent as gradient flow. Advances in Neural Information Processing Systems, 30, 2017.
10

---

Under review as a conference paper at ICLR 2023
Qiang Liu and Jason Lee. Black-box importance sampling. In Artificial Intelligence and Statistics, pp. 952-961. PMLR, 2017.
Qiang Liu and Dilin Wang. Stein variational gradient descent: general purpose bayesian inference algorithm. Advances Neural Information Processing Systems, 29, 2016.
Yang Liu, Prajit Ramachandran, Qiang Liu, and Jian Peng. Stein variational policy gradient. arXiv 2017.
preprint
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Multiple source adaptation and the Rényi divergence. arXiv preprini arXiv: 2012.
Domingo Morales González, Leandro Pardo Llorente, and Igor Vadja. Rényi statistics in directed families of exponential experiments. Ene, 9:30, 2013.
R. Neal. MCMC using Hamiltonian dynamics. Handbook of Markov Chain Monte Carlo, 2(11): 2, 2011.
Emanuel Parzen. On estimation of probability density function and mode. The annals of mathe- matical statistics, 3363):1065-1076, 1962.
Yuchen Pu, Zhe Gan, Ricardo Henao, Chunyuan Li, Shaobo Han, and Lawrence Carin. VAE learn- ing via Stein variational gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Adil Salim, Lukang Sun, and Peter Richtárik, Complexity analysis of Stein variational gradient descent under Talagrand's inequality T1. arXiv preprint vrXiv:2106.03000 2021.
David W Scott and Simon J Sheather. Kernel density estimation with binned data. Communications in Statistics-Thent and Methods, 1356)1333,,339, 1985.
Simon Sheather. Density estimation. Statistical science, pp. 588 597, 2004.
Jiaxin Shi, Chang Liu, and Lester Mackey, Sampling with mirrored Stein operators. arXiv preprint arXiv:210..1206, 2021.
Bernard W Silverman. Density estimation for statistics and data analysis. Routledge, 2018.
Lukang Sun, Avetik Karagulyan, and Peter Richtárik. Convergence of Stein variational gradient descent under a weaker smoothness condition. arXiv preprint arXiv:2206. 005000 2022.
Chenyang Tao, Shuyang Dai, Liqun Chen, Ke Bai, Junya Chen, Chang Liu, Ruiyi Zhang, Georgiy Bobashev, and Lawrence Carin. Variational annealing of GANs: A Langevin perspective. In International Conference on Machine Learning, pp. 6176-6185, PMLR, 2019.
Tim Van Erven and Peter Harremos. Rényi divergence and Kullback-Leible divergence. IEEE Transactions on Information Theory, 60(7):3797-3820, 2014.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Dilin Wang, Hao Liu, and Qiang Liu. Variational inference with tail-adaptive f-divergence. Ad- vances Neural Information Processing Systems, 31, 2018
Dilin Wang, Ziyang Tang, Chandrajit Bajaj, and Qiang Liu. Stein variational gradient descent with matrix-valued kernels. Advances in Neural Information Processing Systems, 32, 2019.
Lantao Yu, Yang Jiaming Song, and Stefano Ermon. Training deep mased models with f-divergence minimization. In International Conference Machine Learning, pp. 10957-10967. PMLR, 2020.
Ruiyi Zhang, Chunyuan Li, Changyou Chen, and Lawrence Carin. Learning structural weight un- certainty for sequential decision-making. In International Conference on Artificial Intelligence and Statistics, pp. 1137-1146. PMLR, 2018.
Ruiyi Zhang, Zheng Wen, Changyou Chen, and Lawrence Carin. Scalable Thompson sampling via optimal transport, arXiv preprint 1902 2019.


Reviews:
[{"review_id": "N9bbKdw-Ip", "reviewer": "Reviewer_1o9E", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\nThe paper proposes and studies an algorithm, $\\beta$-SVGD, which modifies the SVGD by multiplying a factor $-(\\frac{\\pi}{\\rho_t})^\\beta$ to the vector field. The main result is that when $\\beta\\in(-1,0)$, the convergence of the Stein Fisher information does not depend on the target $\\pi$ or the initialization $\\rho_0$. ", "summary_of_the_review": "The paper proposes $\\beta$-SVGD but is unable to show that the algorithm works in higher dimensions or more complex problems. \nThe convergence rate proof depends on unrealistic assumptions. ", "strength_and_weaknesses": "**Strength**\n\n- The paper proves the convergence of the proposed algorithm.\n\n**Weakness**\n- In order to compute the weight $\\pi/\\rho_t$, the paper proposes to use a kernel density regression to estimate $\\rho_t$. However, the number of samples needed by kernel density regression grows exponentially with dimension. So the algorithm won't apply in high dimensions.\n\n- The paper only has toy examples (1-dimensional 2-Gaussian mixture) in the experiments. SVGD is expected to work for much more challenging problems, not for such simple tasks.\n\n- The mathematical assumptions needed for the proof are too strong. For example, for Assumption 4 to hold for some uniform bound M, it essentially requires that $\\pi$ and $\\rho_0$ cannot be very different.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "E136vvJS0zd", "reviewer": "Reviewer_xAMu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies a generalization of Stein variational gradient descent by a particular preconditioner function (weight function). The objective is the same as the KL divergence. By assumptions, they show the convergence result. They also demonstrate the effectiveness of the method in simple numerical examples.  ", "summary_of_the_review": "The paper is overall written well with clear mathematics. However, much-related literature and many machine learning-related numerical examples are missing. I strongly suggest authors revise the paper accordingly. ", "strength_and_weaknesses": "Strength: The preconditioner function (importance weights) is an interesting idea. \n\nWeaknesses: \n\n1. Please do not use the red color in the abstract for the KL divergence. \n\n2. The authors miss much important literature in modified Wasserstein gradient flows. Please discuss them in the literature. \n\n(1) A. Garbuno-Inigo, F. Hoffman, W. Li, A. Stuart, Interacting Langevin Diffusions: Gradient Structure And Ensemble Kalman Sampler, 2019. \n(2) W.C. Li, L.X. Ying. Hessian transport gradient flows. Research in the Mathematical Sciences, 2019.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BssZAU6QTg", "reviewer": "Reviewer_Nor5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes enhancing SVGD using importance weights which scales the SVGD update directions by $(\\pi / \\rho_t)^\\beta$. The resulting $\\beta$-SVGD is then shown to have an exponential convergence rate in terms of 2-Renyi divergence under a Stein Poincare inequality assumption when $\\beta = 1$ and another descent lemma is proved for $\\beta \\in (-1, 0)$ under quite a few assumptions. \n", "summary_of_the_review": "Overall I think the proposed algorithm is well-motivated but its effectiveness has not been demonstrated, both in theory and in practice. Hence I'm leaning toward rejection.\n", "strength_and_weaknesses": "## Strengths:\n* Applying importance reweighting to the popular SVGD is a meaningful task that is well-motivated.\n* The resulting $\\beta$-SVGD algorithm is simple and clean.\n* Theoretical analyses demonstrate nice convergence properties of $\\beta$-SVGD compared to SVGD.\n\n\n## Weaknesses:\n* It is unclear to me what the optimal $\\beta$ is and the theories in Section 3 and Section 4 seem to suggest the opposite of each other. In Theorem 2 we take $\\beta = 1$ to obtain exponential convergence under the Stein Poincare inequality, while in Proposition 1 we need $\\beta \\in (-1, 0)$.\n* The selling point of the main Theorem 1 is that with $\\beta \\neq 0$ there is no dependence on $D_{KL}(\\rho_0 || \\pi)$. However, I do not consider (14) to be a strong result due to the minimization over $t \\in [0,T]$ on the left side. As Korba et al. (2020) commented on their Proposition 3 (which is straightforward from their (12)), \"the convergence of $I_{Stein}(\\mu_t | \\pi)$ itself can be arbitrarily slow\" unless with more assumptions. \n* It is also unclear to me whether the proofs contain novel techniques or are simple adaptations of existing techniques, especially given a large number of assumptions. As mentioned in the paragraph before Remark 1, the importance weights $(\\pi / \\rho_t)^\\beta$ is to cancel exactly the inverse term appearing in the Wasserstein gradient of $(\\beta+1)$-Renyi divergence. Are there other insights in the proofs other than this kind of cancellation which seems by design?\n* The algorithm is not very practical in my opinion, due to the presence of $\\pi/\\rho_t$ in the importance weights. In many applications (e.g. Bayesian inference with lots of samples), $\\pi$ can be numerically insignificant whereas only $\\log \\pi$ is numerically reliable. Furthermore, the authors claim we can ignore the normalizing constant in $\\pi$, yet this constant can change the step size drastically and must be addressed (this is not a problem of SVGD which only uses the score). Additionally, as already observed by the authors, $\\rho_t$ can be too small when using kernel density estimation and can cause overflow --- a rather ad-hoc clipping trick is adopted but I doubt its effectiveness. A more practical reweighting scheme is by Xu et al. [1] and it should be compared to.\n* The biggest weakness of the paper, to me, is that the paper has not demonstrated the effectiveness of the algorithm in any applications, despite the simple form of the algorithm. An extremely simple 1-D example is done in Figure 1 and in the appendix, and even then the proposed method does not seem to work well (in Figure 1 the green line is quite off from the target blue line). The authors wrote \"more complicated models on high dimension space are out of our interest and ability\" in the appendix, but such a statement is irresponsible. At the very least the authors should test on multivariate Gaussians in dimension 2 and above, and compute metrics (energy distance or Wasserstein distance) to evaluate the sample quality.\n\n\n[1] Xu, L., Korba, A. &amp; Slepcev, D.. (2022). Accurate Quantization of Measures via Interacting Particle-based Optimization. <i>Proceedings of the 39th International Conference on Machine Learning</i>, in <i>Proceedings of Machine Learning Research</i> 162:24576-24595 Available from https://proceedings.mlr.press/v162/xu22d.html.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject