Local KL Convergence Rate for Stein Variational Gradient Descent with Reweighted Kernel
Authors: Xunpeng Huang
Hanze Dong
Cong Fang
Venue: Submitted to ICLR 2023 (2023)
Keywords: SVGD
asymptotic analysis

Abstract:  We study convergence properties of Stein Variational Gradient Descent (SVGD) algorithm for sampling from a non-normalized probabilistic distribution $p_*({x})\propto\exp(-f_*({x}))$. Compared with Kernelized Stein Discrepancy (KSD) convergence analyzed in previous literature, KL convergence as a more convincing criterion can better explain the effectiveness of SVGD in real-world applications. In the population limit, SVGD performs smoothed gradient descent with kernel integral operator. Notably, SVGD with smoothing kernels suffers from gradient vanishing in low-density areas, which makes the error term between smoothed gradient and Wasserstein gradient not controllable. In this context, we introduce a reweighted kernel to amplify the smoothed gradient in low-density areas, which leads to a bounded error term to Wasserstein gradient. When the $p_*({x})$ satisfies log-Sobolev inequality, we develop the convergence rate for SVGD in KL divergence with the reweighted kernel. Our analysis points out the defects of conventional smoothing kernels in SVGD and provides the convergence rate for SVGD in KL divergence.

Under review as a conference paper at ICLR 2023
LOCAL KL CONVERGENCE RATE FOR STEIN VARIA- TIONAL GRADIENT DESCENT WITH REWEIGHTED KER- NEL
Anonymous authors Paper under double-blind review
ABSTRACT
We study the convergence properties of Stein Variational Gradient Descent (SVGD) algorithm for sampling from non-normalized probabilistic distribution p. (x) ex)(=f-(x)). Compared with Kernelized Stein Discrepancy (KSD) convergence analyzed in previous literature, KL convergence as a more convincing criterion can better explain the effectiveness of SVGD in real-world applications. In the population limit, SVGD performs smoothed gradient descent with kernel integral operator. Notably, SVGD with smoothing kernels suffers from gradient vanishing in low-density areas, which makes the error term between smoothed gradient and the Wasserstein gradient not controllable. In this context, we introduce reweighted kernel to amplify the smoothed gradient in low-density areas, which leads to a bounded error term. When the (x) satisfies fog-Sobolev inequality, we develop the convergence rate for SVGD in KL divergence with the reweighted kernel. Our analysis points out the defects of conventional smoothing kernels in SVGD and provides the convergence rate for SVGD in KL divergence.
INTRODUCTION
Sampling from non-normalized distributions is crucial task in statistics. In partieular, in Bayesian inference, Markov Chain Monte Carlo (MCMC) and Variational Inference (VI) are considered two mainstream lines to handle the intractable integration of posterior distributions. On the one hand, although methods based on MCMC, e.g., Langevin Monte Carlo (Durmus & Moulines] 2019 Welling & Teh 2011) (LMC) and Metropolis-adjuste Langevin algorithm (Xifara et al. 2014)) (MALA), are able to provide approximate target distributions with arbitrarily small error (Wibisono) 2018). the sample efficiency low due to the lack of repulsive force between samples (Duncan et al. 2019 Korba al. 2020). On the other hand, VI-based sampling methods (Blei al. 2017 Ranganath et al., 2014) can improve the sampling efficiency by reformulating inference as an optimization problem. However, restricting the search space of the optimization problem to some parametric distributions in VI usually causes a huge gap between its solution and the target distribution p..
Inspired by conventional VI, series of recent works analyze LMC the optimization problem of Kullback-Leibler (KL) divergence (Wibisono) 2018 Bernton 2018 Durmus et al. 2019). i.e..
p p(z) In p(x)
arg min Hp. (p) = (plpp)) = (RP)(R))
dx
P. (x
where (2RR)) is the set of Radon-Nikodym derivatives of probability measures v over Lebesgue measure such that p(z)= = dr(z)/dz. | |"p(z)dx < oc. LMC is considered as a discrete scheme of the gradient flow of the relative entropy by driving particles with stochastic and energy energy-induced force. Besides, to take the best of both MCMC and VI, Stein Variational Gradient Descent (Liu & Wang 2016) (SVGD) was proposed as non-parametric VI method. It replaces the stochastic force in LMC with the interaction between particles and approximates the target distribution by driving force in Reproducing Kernel Hilbert space (RKHS). It means the gradient flow of SVGD is defined by the functional derivative projection of Eq. D to RKHS. The empirical performance of SVGD and its variants have been largely demonstrated in various tasks such learning deep probabilistic models (Liu & Wang, 2016 Pu et al.) 2017), Bayesian inference (Liu & Wang 2016 Feng et al. 2017 Detommaso et 2018), and reinforcement learning (Liu et al. 2017).

---

Under review as a conference paper at ICLR 2023
In addition to rich applications, there is lot of work on the theoretical analysis of SVGD. For example, Kernelized Stein Discrepancy (KSD) convergence properties of SVGD under asymptotic
and non-asymptotic settings are investigated by Liu (2017); Lu et al. (2019) and Korba et al. (2020);
Salim et al. (2021 2022), respectively. However, different from the convergence of KI. divergence in the analysis of LMC (Cheng & Bartlett 2018 Vempala & Wibisono 2019) KSD convergence cannot deduce the effectiveness of SVGD in some real-world applications, c.g., posterior sampling (Welling) & TTThg201 201T) and non-convex learning (Raginsky al. 2017). Then, provide KL convergence, some other works (Duncan et al. 2019; Korba et (0020) present a linear convergence of SVGD with Stein log- log-Sobolev inequality (SLSI) (Duncan et al. 2019). Nonetheless, different from the clear meaning and criteria of standard log-Sobolev inequality (LST) in the analysis of LMC (Vempala Wibisono 2019), the establishment of SLSI requíres the property of the coupling designed smoothing kernels and the target distribution, which can hardly be verified in commonly used kernels (Duncan et al. 2019). In addition, SLSI in higher dimensions is more challenging to hold.
To fill these gaps, in this paper, we aim to provide the convergence rate of SVGD (in the infinite particle regime) in terms of KL objective, when P. = e- satisfies standard LSI. Specifically, first point out that the SVGD with smoothing kernel, e.g., RBF kernel, suffers from gradient vanishing in low-density areas due to the extra Pe( scaling. Then, we denote the importance of reweighted kernels by dividing pt (x))) or (ar), where the scaling of smoothed gradients can
be normalized. With the reweighting scaling p. 1/2 (x:) p01ppp11/0/ (y) for kernel k( y) and regularity conditions, SLSI in higher dimensions can be nearly established with additional term controlled by kernel approximation error. Finally, by choosing a proper reweighted smoothing kernel, the KL divergence of SVGD dynamics obtains local linear convergence rate to any neighborhood of p. (x) under mild assumptions when the initialization po (x) is relatively close to p. (z).
The main contributions of the paper are as follows:
We introduce reweighted kernels to SVGD which replaces traditional smoothing kernels and overcomes the gradient vanishing problem in low-density areas.
We study the KL convergence rate of SVGD algorithm. Under the standard LSI and some mild assumptions, we show SVGD with reweighted kernel has local linear convergence rate to any neighborhood of p. (ar).
PRELIMINARIES
In this section, first introduce important notations used in the following sections. Then, explain how to optimize functionals on Wasserstein space by continuous updates in the infinite particle regime. After that, we show that the key condition LSI on the target distribution obtain the KI convergence rate of LMC. However, the convergence rate of SVGD dynamics is non-trivial with this assumption.
Notations. In following sections, bold letters æ, y, z denote vectors in Rd. and B(x, means the open ball centered at æ with radius r > 0. For function f Rd + R. V VJ() and 4² ((()) refer to its gradient and Hessian matrix respectively. For function f Rd Rd. V V)( and V f()) present the Jacobian matrix and divergence. For function with multiple variables, V. means the gradient w.r.t i-th variable. The distributions are assumed to be absolutely continuous with respect the Lebesgue measure, which produces density function p. The probability density function of the target posterior denoted by P.. The density at time is Pt- Notation || denotes 2-norm for both vectors and matrix. In Hilbert space H equipped with the inner product 2e- the norm is induced as || 1| The set P22 (x)) is consist of probability measure y on 2' with finite second order moment. i denotes a function smoother, such as exp(- exp(-[[<<]3) ||x]) max(0, 1 ||]]]]]
2.1 OPTIMIZATION IN THE WASSERSTEIN SPACE
Sampling algorithms can be considered as optimizing some given functionals in the Wasserstein space as Eq. [ Generally, they only update particles, which causes the evolution of the particles' distribution. Such an evolution finally affects the objective functional.
In particular, given initial distribution æp Po (=( and function class H. suppose the update of æ; is
da. (xx)))
2

---

Under review as a conference paper at ICLR 2023
where Φ1 R² - Rd H. By the continuity equation, have the differential equation for (c
dx)
dt - (a)(
For any suitable functional F w.r.t Pt, its evolution can be presented as
F(r)) /rc (pr)0ap,d
8F 8p
5J
(p:) or (1
di
öp
where /op denotes the (IR)) ( derivative (Villani 2009 ing that Hp., we have Proposition 2.1. The evolution of KL divergence with Eq. is
Duncan et al. 2019).
Assum-
(pt) = - ()(x))o((z) In Pe da.
(3)
dl
(x()))
direct result of the functional derivative for KL divergence, where 8F/6p Inp Inp (Chapter 15 of Villani (2009)). By choosing de which decreases KI. divergence via Eq. 3
Proposition 2.1
we can optimize pt to approach P...
2.2 LOG-SOBOLEV INEQUALITY
In the Wasserstein space optimization literature, LSI is particularly crucial to obtaining the conver- gence rate, which is an analogue to Polyak-Lojasiewicz (PL) inequality Euclidean space. LSI applies to wider class of measures than log-concave distributions and can be checked by Bakry- Emery criterion Bakry & Émery 1985). Specifically, bounded perturbation and Lipschitz mapping can preserve the establishment of LSI Vempala Wibisono (2019), where log-concavity would be failed. For example, subtracting some small Gaussians from strongly log-concave distribution will destroy the log.concavity of the original distribution, while it still satisfies LSI as long as the Gaussians subtract small enough. When the target distribution p. satisfies μ-LSI, it denotes
Ep. [g In g²] Ep. [g"] In [o'] 1 E [
(4)
for any differentiable function g E (v). Such an inequality usually provides some connection between the sufficient descent of functional evolution and its exact values.
Coupling log-Sobolev inequality with Langevin dynamics. In particular, the most popular algo- rithm, Langevin dynamics Vempala & Wibisono (2019) chooses
(x)
dp)(a) V (p(())V Pe(x))
(x)
V In
p. to decrease the KL functional (Eq. which is equivalent to the particles' update,
Pe (x)
di
dæ; fz)ddt v2dB,
(5)
where B, is standard Brownian motion. The introduction of randomness can also convert V (x) tractable form and the dynamics becomes
dHp. (pt)
Pt(x) (x)
(x()))
V In pa
dx
(6)
dt
where the absolute value of RHS in Eq. ils called relative Fisher information. Taking g² pe/p.. we have
(x
H (p:) S
(x))
In
dæ.
2/
p. (x)
Then LSI provides a lower bound for gradient norm, leading to sufficient descent for KL divergence. Combining Eq. ( and Eq. we have
dHp (Pr). S 2I (pt).
(8)
dt
for some 0. By applying Gronwall's ' lemma, Eq. 8 yields Hp. (p:) I Hp. (Po) (up(-2 which indicates the linear convergence rate of Langevin dynamics. Nonetheless, coupling LSI with SVGD is challenging due the introduction of RKHS.

---

Under review as a conference paper at ICLR 2023
KL divergence descent with asymptotic SVGD. As shown in Lemma 3.2 Liu & Wang (2016) the key point of continuous SVGD is to minimize the RHS of Eq. in the unit ball of the RKHS H follows
S(p: p.) max / dEH
Pe (x) Pr x
(x()))())) T V In
dx,
such that ||ll S
where S(ee, p.) called Kernelized Stein's 's discrepancy (KSD), Assume that the RKHS associated with kernel k(x:, y) Rd RR - R, such that k(x,, y) (0(x)) ((y)) and H is the d-times Cartesian product space of Ho that contains Frobenius-normalized linear functions from to Rd i.e., (0e, diix < 1. Note that Eq. 10 defines a functional gradient in RKHS, which indicates the steepest KL decreasing direction with a normalized functional vector. Using integration by parts, Eq. 1 can be rewritten as
/ (Vae)( + Vo(x))dx, such that l S S(pt. q). (10)
Ø arg max
dEH
The explicit form for (x())) is presented as follows.
Proposition 2.2. Assume that satisfies Eq. 70 Then we have
(x(x) = pu(y) (hnp))))
Vik(y,
(11)
where (xx) can be estimated by particle samples from Pt-
Proposition 2.2 (as Lemma 3.2 proved in Liu & Wang (2016)) makes Eq. 2 become a practically
tractable algorithm by Monte Carlo estimation Eq. where particle samples from (ry). Note that Eq. 2 and Eq. 11 naturally lead to the algorithm of SVGD.
Combining Proposition 2.1 and 2.2 can be obtained,
the dissipation of the KL divergence along continuous SVGD
dHp. (px)
/
/ k(x, v)p( V
(r(x)) p'(a)
Pr(3)) p²(z)
In
dydæ.
(12)
dt
When the kernel is strictly positive definite, RHS Eq, T2 is negative, leading to the decrease of KL divergence. Unlike the sufficient descent bounded by the functional value in Eq. 7 LSI cannot be conducted on the RHS Eq. 12 due to the kernelization, which also causes the KL convergence rate be unknown. Instead, previous works (Liu 2017 Lu et al. 2019) provided an (1/tt) KSD) convergence as
Pp) S ( S(p..p.)ds S (p))
S(p,, p.) O
min
(13)
KL CONVERGENCE OF SVGD
In this section, we first show, compared with KSD convergence proved in most previous works on SVGD Liu 2017); : Ju et al. (2019): Korba et al. (2020): Salim et al. (2021) 2022), KI. convergence more powerful in explaining the practical performance real-world applications. After that, we explain Stein log- Sobolev Incquality (SLSI) the necessary condition for analyzing KL convergence of SVGD can hardly be verified. In order to investigate more reasonable conditions, our assumptions proposed and validated empirically in some simple cases. Finally, provide the main theorem, ie., the KL convergence of SVGD under these mild assumptions. Due to the page limit, we left the comparison with previous works by list in Appendix A
3.1 SAMPLING TASKS REQUIRE KL CONVERGENCE
Sampling algorithms widely used in real-world applications for solving corresponding machine learning problems. Although different tasks usually require different criteria for convergence analysis, most of these criteria be deduced by KI. convergence.
4

---

Under review as a conference paper at ICLR 2023
In Bayesian learning Welling & Tch (011), people expect capture parameter uncertainty via Markov chain Monte Carlo (MCMC) techniques. Specifically, they prefer to sample the parameter vector from posterior distribution presented
7
p(w|z) p(w) II p(z,lw),
where 2 = { denotes given dataset. The update of w in (Neal el al. 2011
Aw
1)t V ((w) + T v log (og + 2 dB,
(14)
equivalent to minimizing the KI. divergence w.r.t between p(w)22 and ps (un|z) where
(w]lz) arg min Hp(w) IT= P(./ww) (p').
It means the convergence of Bayesian learning is directly dependent on KL convergence. Another important application of sampling algorithms is to minimize the expected excess risk as
E [F(w)]-1 F
(15)
where F denotes the objective function of the stochastic optimization under the unknown data distribution P
F F(w) = Ex [sw,, 2)] = S. ( P(dz),
and F denotes inf weRa F(w). When L-smooth, previous gradient-based MCMC methods would like to analyze the convergence with the general framework by
[F(w))] F =E [F [[
FF*
/ p())
[/ee
((w) (w))) [ F( + [[[(WW)) F
(dz) LLC W2(Pn,z,
-E
E [F(WW)] F
Training error
(16)
where the netuple (data) = {21. ..,..., 2nd } of i.idd samples are drawn from P. It means the minimization of Wasserstein 2 distance between pt. (MCMC samples at time f) and p=,=(xr) xx p(w]2) leads to convergence of expected excess risk. The aforementioned results can be directly with
deduced by the KL convergence (Raginsky et al. 2017 Xu et al. 2018)
(V (Tn.)) ((px))(
H HHp.. (Pk.z) (Hri.
Wa(pe.z. s CC
2
Unfortunately, the connection between W2(pk.2. and S(pk,z p=.=) depends on the choice of RKHS, which is highly specialized and non-general. From theoretical perspective, when the RKHS is over-smooth with a sufficient large bandwidth, k(x,, y) = a a exp( - yll 2 2/2) with large a, the corresponding kernelized gradient tend diminish, i.e., lim Ep. [kxx, y) V In Pe(y) 0. That means the KSD can be arbitrarily small with improper RKHS choices. In this condition, the convergence of KSD does not make much sense about the quality of Pt. since it can be simply controlled by some special RKHS.
p_(g)
3.2 KL CONVERGENCE OF SVGD WITH DIFFERENT ASSUMPTIONS
To investigate KI. convergence of SVGD, some previous works (Duncan et al. 2019 Korba et al. 2020 Salim et al. 202I) introduce the following assumption.
Assumption 1. The probability density p. satisfies Stein fog-Sobolev inequality (SLSI) with constant > O, for any Ps. E (R.))) it has
Hp (p:) S S(p..p.). P.).
(17)
24
5

---

Under review as a conference paper at ICLR 2023
We immediately obtain
(r(x)) Pa (x))
V In Pr(y) p. p.
Hp. (p:) S
k( y (.))())
V In
dydæ,
(18)
21 g RR
and linear KL convergence can be achieved by combining Eq. 12 and Eq. [8| for SVGD Duncan itt al., 2019 Korba et al. 2020; Salim et al., 2021). However, the verification of this assumption is highly non-trivial because we cannot test all Ps (2 Only when the designed RKHS overly regular, the RHS of Eq. 18 can be estimated. In the meanwhile, an overly regular kernel, i.c.,
f
In (a, -V (a) Vikke x)
ka x) V2h(w, x x) < 00,
(19)
will make SLSI fail, which is indicated (Duncan et al. 2019). Besides, Eq. holds for the most widely used smoothing kernels, such as Radial basis function (RBF) kernel. The contradiction between Eq. and Eq. makes the current analysis in KL divergence highly restricted.
In this condition, we expect more reasonable assumptions to investigate KL convergence of SVGD. Similar to (Arbel et al. 2019), we have additional assumptions on trajectory of pt. Specifically, we assume the following.
[A p. satisfies wwwloo-Sooolllooo Sobolev Inequality (Eq. 4) and f. is L-smooth, i.e., for any æ, y E Rd. (z) - (3)ll I L||x-
yll- -
[Ag] fe is L-smooth where P: = c ft.
[Ag] p: is warm: SuPRER* (x / p. (x() S 3 for some constant / 2 1.
are similar to the convexity geometry and L-smoothness in conventional Euclidean optimization. Assumption [Ag] restricts the domain of our proof: the tail of pa should be lighter than p., which is widely used in Langevin dynamics. Compared with SLSI, due to the decoupling of requirements of the target distribution p. and designed kernels k.
Assumption [A] and a
verify these
assumptions in several ways. The establishment of LSI of the target distribution p. can be checked by
the criterion mentioned in Section [.2] For the trajectory assumptions, i.e., [Ag] and [ [Ag]] provide
the empirical validation by showing the estimation of density ratio and smoothness of Pt. in some
simple cases with the growth of (Fig D Then, we have the following theorem.
Theorem 3.1. Suppose Assumption [A [Aa] are satisfied, and chi-square Dx (po. S 1/4. For any > 0, if we set reweighted kernel k:
k(x y) = (x.( 112 ko (x,, y) (1)) 1/2 (o y) = hin - y) = ~N(l ( -y),
f |B1l k(z)dd - M, and
1 - Jad 10 y)dy S 2/22
1
(20)
where
1 12LM (16C&+
93Cd
+ +6 +6/BL+3CL BBCCLLBBL)) )
min
(21)
2M
C = f Vp)dd)d then the KL divergence between Pt and p. satisfies
(pe S max (0. (o.(HHp.
64c
( exp
μ ))
.cxp
ful
+
64c
(22)
16
should be noted that C < 0o is proven in Lemma B. Although we require the trajectory of the algorithm to satisfy some assumptions, the actual requirements are much looser. For example, we allow the coefficients L of smoothness in Assumption) (osumption[A2)]] and the maximum density ratio 3 in Assumption [Aa]to increase with the number of iteration t growth. Even if the rate of growth is polynomial, ((1/c) convergence rate can still be obtained by decreasing og in the reweighted kernel in Eq. 22 which is shown in Remark 3 Assumption [A is actually introduced control Rényi divergence between Pt and p. will not be infinity in some region near the target, which can be easily obtained in Langevin dynamics.
Remark 1.

---

Under review as a conference paper at ICLR 2023
Wermess
Smrodhhmess
Partiriee 100
of Partidess 100
540 par1p (000000
Pfrtiiddeess 500
of Partides 500
Particles 1000
Portictes 1000
20
50
208
20 50
258
Figure 1: Illustration of warmmess and smoothness evolution, where po ~O(0,..25) p. (0.
This theorem demonstrates that, by introducing reweighted kernel k( y) and controlling the variance a of smoothing kernel k, SVGD initialized local region will provide linear convergence rate to any e-neighborhood of the target distribution. To validate this result, provide experiments in synthetic data in Appendix D and illustrate SVGD with reweighted kernels usually achieves a lower KL divergence compared with traditional SVGD. It should be noticed that commonly used kernels, e-g., RBF kernel and Bump kernel, proper k. Besides, the linear convergence shows all the parameters will not deteriorate the convergence of SVGD when a small enough.
4 REWEIGHTED KERNEL FOR KL CONVERGENCE
In this section, we mainly explain why we should introduce reweighted kernels in Theorem 3.1 The intuition can be split into 2 parts: (1) the infeasibility of the usage of LSI due to the kernel approximation error; (2) the tractable kernel approximation error form with a reweighted kernel.
4.1 KERNEL APPROXIMATION
Intuitively, to measure the error between Wasserstein gradient and its kernelized one, the most direct idea is to control the егтоr of relative Fisher information and make use of LSI. However, this idea will encounter some fatal bottlenecks.
The bottleneck of SVGD analysis with Eq. 7
If we directly upper bound the descent of KI.
divergence by Eq. 7 we have
dHp. (px)
s s-1 (((x))
Pr a
V In
dæ
dt
2
pa (x)
sufficient descent
(23)
If pilu)k(e, v)
Ps (r(y)
Pa (x) (r(x))
+
pr(
dy
V In
dæ,
Rd
kernel approximation
where the kernel approximation error can hardly be upper bounded due Pt (3) in integration. means if we directly plug some smoothing kernels into the iteration of SVGD, kernel approximate error may dominate RHS of Eq. 23 and cause SVGD converge limit different from the target distribution with an uncontrollable bias.
Failures Smoothing Kernels. Smoothing Kernels (kernel smoothers), such as radial basis function kernel, are widely used in SVGD, due to their universal approximation capability to smooth
functions Park & Sandberg, 1991 Micchelli al. 2006). Assume that ko y) Ko (x y)
TT (x y)) is smoothing kernel with parameter > O, where is called the bandwidth of the kernel. The variance o² the smoothing kernel tends to control the smoothness the estimated gradient. A large makes kernelized gradient well-estimated with finite samples while the kernel approximation eиror is large. In the population limit, where randomness from Pe Pyyy) ) is ignored, the optimal smoothing kernel should be Dirac delta function dzz (z). where the kernel bandwidth is sufficiently small to estimate Wasserstein gradient. For each point the kernelized gradient becomes
(x) In (a) which means that for those low-density areas pa (x) O, the kernelization suffers (al))
7

---

Under review as a conference paper at ICLR 2023
(a) Wasserstein Gradient
(b) With Smoothing kernel
(c) With Reweighted kernel
Figure Illustration of gradient vanishing with smoothing kernel. The vector field illustrates V In (ar) for data distribution (00, diag(1, 0.5²))
from gradient vanishing. Such biased Wasserstein gradient estimation in smoothing kernel SVGD will have additional Pr ferm, which hampers the sufficient descent of each iteration and even the convergence rate. This indicates that SVGD is not compatible with smoothing kernels in low-density parts. Ideally, the kernel should be reweighted by some (x))p which can balance the vanishing scaling in the current SVGD. However, Ps unknown in general, this reweighting cannot provide algorithmic insight to improve SVGD.
To solve this problem, very intuitive idea balance the order of Pe. we may require kernel it to be related to Pt through the following proposition.
Proposition 4.1. If we use the kernel k(xx, y) = (pe(z)) 11/2
(De(2)))11/2 T (x, y) (p:(y)) 1/2 by choosing
delta function as the smoothing kernel Ko (x, y) = 8n (y), kernel approximation ervor is and SVGD equivalent the Wasserstein gradient flow.
Unfortunately, the reweighting strategy with pr (x) makes the iteration of SVGD (Eq. computa- tionally intractable as (xx) and (2:) are unknown in general. If we consider the local convergence expect lower kernel approximation error by replacing -1/2 in Proposition 4.1 with p- 1/221/ as follows
of SVGD, when (a() approaching p. (3x),
k(x: y) = (x)) 1/2 Re (2. y) (v)) 1122
(24)
where k, denotes the smoothing kernel, and it satisfies
S | (ac x yydy < x and
( x y)dy S
(25)
Rd
2/2
Notice that many popular kernels satisfies Eq. 25 etc.
e.g., standard RBF kernel, Bump function (Eq. 26
(z) exp
|| B(0,
(26)
/02
Therefore, the dynamics of KL divergence in such reweighted kernel is
dH (p:)
S to (o,
(xx)
(z( p. (x)
(r
(x p. (
V
dydæ.
(27)
(w)
Vp
Similar to the requirement of a delta function in small is preferred in our setting, since our analysis is based on the population limit of (.)) Besides, our analysis would indicate the kernel choice to obtain the convergence.
Compared with utilizing smoothing kernel directly, we may expect smaller kernel approximation error by introducing kernels as Eq. 24 We also validate this phenomenon by Figure 2 which has shown the gradient vanishing phenomenon with the smoothing kemel. Figure (a) is the vector field of Wasserstein gradient V In p. (x)) which is a linear function in Gaussian case. However, when using smoothing kernel the low low-density area in Figure 2 (b) has almost gradient, which makes the particle in this area stuck. Our proposed reweighted kernel amplifies the gradient in low-density areas, the resulting gradient is similar to the Wasserstein gradient.
8

---

Under review as a conference paper at ICLR 2023
4.2 ERROR REWEIGHTING
To achieve better kernel approximation error with reweighted smoothing kernel Eq. 24 we require corresponding local version of log-Sor Sog-Sooleev inequality to control the sufficient descent of the evolution of the KI. divergence (Fq.. 27
Local version of log-Sobolev inequality. In this context, the sufficient descent term should be reformulated to obtain a well-behaved kernel approximation error. The choice of g in Eq. Eq.38 may
convert the kernel approximation error to tractable form. By choosing g(x) the upper bound KI. divergence by x2 version of Rényi information.
P.(a)] we can find (=))
Lemma 4.2. Suppose p. satisfies the A-log-Soboles inequality (LSI) with a constant μ > When any probability density function Pt satisfies xx² (Pt. P.) I 1/2, we have
#1 Hp. (pe)
/ po()))
(e(
V Pe( P. (x:
dx.
(28)
p. (a)
Lemma 4.2 indicates that the KL divergence is also bounded by the Wasserstein gradient of x² divergence. If pt/p- bounded, Eq. 28 provides tighter upper bound of KL divergence compared with that in Eq. E especially for the tail part. Thus, controlling the error term in this form has more potential. With such a construction, the decreasing of KL divergence satisfies
d Hp. (pt) (p)) s dt
(r(z) V In
(x 2
p. (x) gd
dæ
(x)
pa
sufficient descent
(29)
(e(
(r(x)) (x(
Pr(y) Vp (y)
Po(y)
+
(a
Vn
dy
da.
(p.
kernel approximation error
Lemma 4.3. Assume that Inp, and In are L-smooth; is warm: sup (x))/).(<)) S 8 and
Hp. (po) < (28)-1. Then by choosing min O
B p we have
J/ pe(ce)
In ((()) Vp.(m) (x=
(m.
dy (p) p. (w)
Pi(U)
V ((())
2 Am de 7 po(
pe(x)) p-(
In p=(w) p.(w)
da,
where Fg satisfies requirements in Eq. 25
In this condition, we nearly establish the "Stein log-Sobolev Inequality" with arbitrary small e by combining Eq. 27 Eq.
28 and Eq. 29 as follows
# Hp. (pt) Jz
J To (x. y)
(x( (v-(w)
Pr(x)) Po(3) (x) (p) pa p-())
In (c( dydæ + 4e. (30)
V In
Therefore, reweighted kernels can be considered as sufficient condition for establishing local "Stein log-Sobolev Inequality" near the target distribution p..
CONCLUSIONS
In this paper, we prove the local linear convergence for SVGD with reweighted kernel KL divergence. In particular, our analysis is based on the smoothing kernel for SVGD algorithm and point out that the conventional smoothing kernel fails to provide valid gradient scaling low-density areas. Thus, highlight that the reweighting is necessary for smoothing kernels SVGD algorithm. With (p. (xx) (x)) -1/2 weighting for k( y), provides the KL convergence rate for SVGD algorithm locally for log- Soboloo p. (x). Our analysis provide new insights on the kernel design in S SVGD, especially for gradient amplification in the low-density area.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Milton Abramowitz. Abramowitz and stegun: Handhook of mathematical functions. US Department of Commerce, 10, 1972.
Michael Arbel, Anna Korba, Adil Salim, and Arthur Gretton. Maximum mean discrepancy gradient flow. Advances in Neural Information Processing Systems, 32, 2019.
Dominique Bakry and Michel Emery. Diffusions hypercontractives. In Seminaire de probabilités XIX 1983/84, pp. 177-206. Springer, 1985.
Espen Bernton. Langevin monte carlo and jko splitting. Conference On Learning Theory, pp- 1777-1798. PMLR, 2018
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for statisticians. Journal of the American statistical Association, 1126518):89-887, 2017.
Xiang Cheng and Peter Bartlett. Convergence of langevin meme in kl-divergence. Algorithmic Learning Theory, pp. 186-211. PMLR, 2018.
Gianluca Detommaso, Tiangang Cui, Youssef Marzouk, Alessio Spantini, and Robert Scheichl. A stein variational newton method. Advances in Neural Information Processing Systems, 31, 2018.
Andrew Duncan, Nikolas Nüsken, and Lukasz Szpruch. On the geometry of stein variational gradient descent. arXiv preprint arXiv: 19/2.00894, 2019.
Alain Durmus and Eric Moulines. biigh-dimensional bayesian inference via the unadjusted langevin algorithm. Bernoulli, 25(4A):2854-285) 2882, 2019.
Alain Durmus, Szymon Majewski, and Blažej Miasojedow. Analysis of langevin monte carlo via convex optimization. The Journal of Machine Learning Research, 20(1):2660))) 1126666-222) 1106662271,, 2711, 2019.
Yihao Feng, Dilin Wang, and Qiang Liu. Learning to draw samples with amortized stein variational gradient descent. arXiv preprint 1XXv:1707.06626, 2017.
Anna Korba, Adil Salim, Michael Arbel, Giulia Luise, and Arthur Gretton. A non-asymptotic analysis for stein variational gradient descent. Advances in Neural Information Processing Systems, 33, 2020.
Michel Ledoux. Concentration of measure and logarithmic sobolev inequalities. In Seminaire de probabilites XXXIII, pp. 120-216. Springer, 1999.
Qiang Liu. Stein variational gradient descent as gradient flow. Advances in neural information processing systems, 30, 2017.
Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose bayesian inference algorithm. Advances in neural information processing systems, 29, 2016.
Yang Liu, Prajit Ramachandran, Qiang Liu, and Jian Peng. Stein variational policy gradient. arXiv preprint arXiv: 170..0239.999,, 2017.
Jianfeng Lu, Yulong Lu, and James Nolen. Scaling limit of the stein variational gradient descent:
The mean field regime. SIAM Journal on Mathematical Analysis, 51()):64--671, 2019.
Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine Learning Research, 7(12), 2006.
Radford M Neal al. Meme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(1 (),2), 2011.
Jooyoung Park and Irwin W Sandberg. Universal approximation using radial-basis-funccion networks. Neural computation, 3(2):246-25 257, 1991.
Yuchen Pu, Zhe Gan, Ricardo Henao, Chunyuan Li, Shaobo Han, and Lawrence Carin. Vae learning via stein variational gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
10

---

Under review as a conference paper at ICLR 2023
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotie analysis. Conference on Learning Theory, pP- 1674-1703. PMLR, 2017.
Rajesh Ranganath, Sean Gerrish, and David Blei. Black box variational inference. In Artificial intelligence and statistics, pp. 814-822. PMLR, 2014.
Adil Salim, Lukang Sun, and Peter Richtárik. Complexity analysis of stein variational gradient descent under talagrand's inequality tl. arXiv preprint arXiv:2106.03076 2021.
Adil Salim, Lukang Sun, and Peter Richtarik. A convergence theory for svgd in the population limit under talagrand's inequality t1. In International Conference Machine Learning, pp- 19139-19152. PMLR, 2022.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference machine learning (ICML-II), pp. 681-688. Citeseer, 2011.
Andre Wibisono. Sampling as optimization in the space of measures: The langevin dynamics as composite optimization problem. In Conference on Learning Theory, pp. 2093-3027. PMLR. 2018.
Tatiana Xifara, Chris Sherlock, Samuel Livingstone, Simon Byrne, and Mark Girolami. Langevin diffusions and the metropolli-adjuuted langevin algorithm. Statistics & Probability Letters, 91: 14-19, 2014.
Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of langevin dynamics based algorithms for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.

---

Under review as a conference paper at ICLR 2023
A CONVERGENCE RATE COMPARISON IN SECTION 3
The assumptions are listed as follows
[AS]] p. satisfies ju-log-Sobolev Inequality (Fq. 4
[AS2] P. satisfies Talagrand Inequality.
[AS,] The Stein log-Sobolev inequality with constant i.e. KL (pllp") S 3 (pllp*)
2X
[AS,] fx is L-smooth, i.e., for any 2, y E R
[V] V S L| y|l-
[AS,] fa L-smooth where p. = e
[ASa] is warm: supZeRd Pt(x:/p.. S 3 for some constant 3 2 1.
[AS7] P: SVGD satisfy:
/ (())))) < co.
(31)
[ASg] Kernel regularization assumption 1:
| logg" Ilpp k(æ, x)) + Vo } <00
sup
(32)
[ASg] Kernel regularization assumption 2:
(2. B and V (1lz4 S
(33)
[A Bounded moment assumptions:
sup / ||||| pe < oo.
(34)
We compare our theoretical results with all previous work where Stein discrepancy is abbreviated as SD.
Table I: Comparison of convergence rate for sampling algorithms
Algorithm
Assumptions
Criterion
Asymptotic
Rate
ULA Vempala & Wibisono 2019
IAS
[AS
KL
No
((e
SVGD Liu
2017
AS+
KL
Yes
N/A
SVGD
Liu
2017)
[AS
AS
7
[AS&]
SD
Yes
O(1/t)
SVGD Korba et
2020)
ASS
ASS
[AS
KL
Yes
O
SVGD
Korba et al.
2020
[AS
AS
ASg
[AS
SD
No
O(1/t)
SVGD Salim et al.
2021)
[AS
[AS
[AS
[ASp]
SD
No
O(1/t)
Ours
[SS]
[AS
(AS5)
[AS
KL
0
B IMPORTANT LEMMAS IN SECTION
In order facilitate the lemma in Chapter 4 first revisit the dynamics of SVGD.
Remark With a slight abuse of notation, Pt SVGD follows the continuity equation:
Oep: V (prot) = the sense of distribution (rather than almost sure), where
(35)
Φe (x) = (I: (x. y) V Inp, (3) + V y (x, y)) dp.(v).
(36)
Notice that Eq. 35 holds in the sense of distribution here means
f @.p(())((a))dd Vo(x)) (x))p....))
(37)
for all v(x:) C (R&))
12

---

Under review as a conference paper at ICLR 2023
B.1 PROOF OF PROPOSITION 4.1
Proof. When k(æ,v) (vi(z)) Ri (æ, v) (po(w)) 1/2 and ko v) (2)) we have
(1)
d2)
k(z,y)= (p((z)) 1/2 (pe())) pr(y)
Thus,
1 pr(y)
dm (y)
Vhn Pr (+(y) dy (u
V In px(x)) p. (x)
(1()))
(v)
which indicates that (x())) is exactly the Wasserstein gradient and the kernel approximation error is
0.
B.2 PROOF OF LEMMA 4.2
Proof.
With LSI, all smooth function g: R² E with Ep. [g²] < 0c.
Ep. [9 In g²] Ep. [g] In Ep. [g I - Ep.
[|V
(38)
l
Suppose g Pr/pe, we have [97] DDt pa) +1 1 < and
f pz(x))
(c()
In (p((2)
2
dæ
P. (x:)
(x
S (ax))
(x
2
Pc(x))
2
dæ In
(a(x))
dæ
(39)
P. (x)
p. (x)
2
(x)
2
(r(
V In (x)
<= (x(x)
dæ
(=x))
pe (x dæ.
11 Rd
P. (x)
Rd
(x))
With the fact In x Sx x -
and In x 2 1 when x 2 0, we have
/
(r(
dæ S /
Pr(x)) -1 dx (x)
In
(x)
Pe(xx)
(xx
Rd
(40)
(xx
pi(
p(()))
Po(xr) (xx)))
(a)
da
In
dæc
Rd p.
(x)
(
Ju pa
(x)
p- (x)
Plugging the previous inequality into LHS of Eq. 39
we have
(xx) 2 (xxx))
(ar) (x(x)
2
LHS
(x())
In
da
(e( dæ
p px(x)
(c(x)) (xx
(x)
In
dæ
JRd
(x)
Rd P. (xx
(P)(
2
In P((w))
(c(()))
2
Pe(())
(m()
da J Ps (a())
da
(x.
(x(x)
p. (x:)
Pa (x:
(41)
/ (m)) ((P((z)
(x(
2
Pr p((
da
In
dar
(x))
RA Pa (x:
p.
22 Dy2 (pc, - 1). / (x))
Pt (a:
In
dæ
Rd
P. (ax)
p- (z)
1
(P((x)
2
(x)
2 2 Rd
(x)
In
dæ,
(x))
(x)
13

---

Under review as a conference paper at ICLR 2023
where the last inequality follows from Xxa (pt, Pa) $ 1/2. Besides, we have
S/c. px(x)-
(p((z) (a(x))
2
Pr (a)
p(( JRd (a
Pr p((x)) In (( (zt
In
dæ
dæ
P. (z)
P. (x
(42)
pr(xx) R2 (x))
(t
pr( In (r( de Hp. (pt), P- p_(m)
(x In
dæ
p. (z)
where the last inequality follows from (x 1) In x 2 0 for all x 2 Combining Eq. 39 Eq Eq. 42] complete the proof, and obtain
and
# Hp. (pt) S / pa(x))
(x
Vin (e( P. (x)
dæ.
(43)
4
P. (x)
B.3 PROOF OF LEMMA 43
Before providing the Kernel Approximation Error (KAE) in Lemma 4.3 we need to introduce some lemmas.
Lemma B.I. Assume that p(x) is T-smooth and log-Sobolev, then for any a >
I p(az) do < 0c
Proof. By Ledoux (199), when p(æ) is log-Sobolev, there exists 0 such that
f p(x))elle11 dx <
then
/ (nol))+ dx
Thus, there exists or > 0, for sufficient large || > Cr.
Imp(x) < =c| and 1 Mallza (0 < / -acllel do
2nd
ca
For
J I (w))d < / J ( da (ddd
where C(d, Cz. aL) is constant depend on d, C.. aL.
Lemma B.2. (A Variant of Lemma. 11 in Vempala & Wibisono 2019 Suppose p(æ) - ef()m) x Rd, f is L-smooth and p(x) satisfies
[ Vp(x)de & C/2,
then we have
/ v V [V[()) & LCd;
Proof. Since f(x) is L-smooth, we have for any
v - LT
14

---

Under review as a conference paper at ICLR 2023
Using integration by parts, have
/
(1-10)/2 ( ( de
(44)
= / e- (ff(2) 22)
(45)
= <2Ld / c- (=f(m)/2dd LCd
(46)
Proof. In the following, we mainly focus on providing the upper bound of Kernel Approximation Error (KAE), and have
(x(
Vln Pa(x)
ko - y) Pt( y)
Pr(x - y)
KAB
V In
dy
dæ
Rdd
P. (x)
(a)))
Vp. - -y) Pa (I y)
<2 {
Pt(
Vn Pr(xz)
Pi(x y)
Pe(x 8)
Nio (2000 x -
dy
dæ
gd
(x)
(xx)
Vp. - y)
p+ y)
/
(1-
(x(
V In Pr(ar)
+
Tho az, v)dy
dæ.
(x)
p- (x)
Rd
Bit
(47)
where the first equation follows from the change of variable. With the requirement of k, we have
Ro (x, y) = Fx y) = 1 -
(x
y)
J |1yl| k(y)dd S M
(48)
and | - /
1
ko x - yydy
I 2
Ra
In this condition, suppose y az Eq.
xz == σ2, then have
(x(x)
(x(
(x(=)z)
KAE <4
k((z)
In
dz dx
Rdd
(x))
P.( /p((x.))
p. (xx)
(49)
Term
(x(x))
Vn (xr) dx.
+
P. (x()
4 gd
(x)
(x)
For any x E Rdd we have
(x)
V In Pr(x))
(x)
(Vf.(z) (x))
where pr(x) -f((()) px)(x) (-((())pp_xx) = -
Vp, (x)
(x) (x)
15

---

Under review as a conference paper at ICLR 2023
Plugging such an equation into Eq.
49
we have
(x(
pr(xzz)
Term
k(z)
Vf-(x)
(fx()z))
Rd R2
(p)
(1z(1))
12
(x()
Vfe(a)) (x(2)
V(i(mz))
dz dæ
(x)
(xz)
2
1pc. k(())
Pc(x))
pr(az)
2 Rd
Vf-(a))
(f((z)) dz dæ
(xx
Vx=
1pee k(x))
Pe(ar)
Vf((x) ((x22
||
2 Jud
(xx2 Vfe((zz) dz dæ
(vr(
(
(JL b(z))zz [ R(z))
Pc(x))
(((xx))
ffr((()) ) dz dæ
22
(f((x)
(x))
[(z))z (1
2
/
/ k(xx)
Pr(x))
Pt (2x)
+
fx)
V v((((z)
dz dæ
Jud
(Vp(xx)
Vps (xx)
Po(x)
(<(2*))
<3
i((z)
f((()))
(xx) V(((2(z)
dzdæ
Rd JRd
Vp.(x)
Tern 1.1
((( (z) Po(2zz) V. (axz)
+
k((z)
dzdæ
JRd
JRd
(p.
(x.(x=))
Term 1.2
(50)
where the first inequality follows from Minkowski inequality, the second inequality follows from Schwarz inequality, and the third inequality follows from Eq. 48
Consider Term 1.1, we have,
Pr(
(r(=)))
Term 1.1
Jg Jdd
k(z))
Vf((()
ff((x)
(x))
Vp. (xx2)
+ ()())))
[f((z) (xxx))
vfe(xz)) ) dzdx
Vp+(I*
vp=(az)
Pc(x))
p((x*)
<2
k(z)
(x)) dzdæ
JRd Jdd
(p)
(p.(2:z)
(+(x))
+2
T((2)
(Vf((w)) f(((=)))
dzdæ
RRd JBc
Vpr(arz)
(x(x)
pr(x*)
kx(z)
fx() dzdæ
JR JRd
Vx)(x)
(px(2z)
2
p((xx))
+2 JRd
x(2) |
dædz
(xr)
(r(x))
52
k((z)
f((())
dzdæ + 202 + 1),
Rdd .Rdd
p/p(())
(xx)
(51)
16

---

Under review as a conference paper at ICLR 2023
where the second inequality follows from L-smoothness of pı(a) and the Fubini's theorem, and the third inequality follows from Pt warm (Assumption 3) and the fact Jga llyll -(y)dkyyyy s D in Eq. 48
In the following, we focus on the first term of RHS of Eq. 51] and have
(x) (x()) exp 2 fi(xz)
(52)
P. (x)
For each RR, suppose high dimensional Rdd can divided into two parts:
fa(x)) fe(x:) -
f1(2z)
(x(x))
f(((xz)
(53)
(x) {2) [x())
f.(22) - f(((Ez)
f((2)) 2
2
2
For E (x)), we have
(x==
Pe(x))
Pe(2;2)
(1-exp/ ((fala))
f((z)) - [.((zz) f((xz)
v Po (xx))
Vp.(x)
Vpr(x*)
2
(x(x))
(x0z)
[x(x) - fi(x))
f1(0z))
pa (xx)
(r(
3Lo²
2 (a) Vf.(x)) f. oz))
2 + =Vo
||
Vp((xz)
2+ 5L
(x=))=)) + V T=+
4 ||
P. (xx)
2
(54)
where the first inequality follows from - e- x for any x 2 1, the second and third inequality follows from L-smoothness of f. and fe. Therefore, we have
J Rd
/
(a)
(=(
k(z) J::
V ff((z)
dædæ
(x)
Vpa (xxx))
kx)))
(x()
[ Vf.(()) +
2
5lo2
||=1]]
V.((x))
dzdæ
Rd B
(xx)
4
k(z)
5Lo²
(zz)(zz) T + fvx))) Tz
||//2
PP: (12
20
B,
(pr(a)))15
[ vf(xz)) + vi(x>>))' )1? dædæ
R
B
2
(x(x))
||= Vp((az) ( (V 2 3 [ )1 +
5L20²
2 ||
dædæ
B:
o. ok()). (pr(2z))
+
(IVf((=))]( 2 L ||
dzdæ
p=(xx)
Rd
B:
/Bo
h(=)||=1| [SL Vp.(xx)
[Vf. 2xxd dæd=
Jdd
30
?(=)|1=1 / (Vf 2 dædx + 5L?03 S {(=)|<=]| [ Vpe(x=)dadz
+ 2
[
M(z) ( Vp((a2) (V) dadd + 33.2203 / h(z)]|2|2 / Vir(az)dada
+ +B0 Ba
20
nd
1 SVBOaL(M + 1)- + + 1 VBCLLM. o² + 33L.CCLL a a } 3L + 03.
(55)
can be noticed that the first inequality follows from Eq. 54 the second and the third incqualities follow from Cauchy-Schwarl inequality, the fourth inequality follows from the --warm during
17

---

Under review as a conference paper at ICLR 2023
the update, the fourth inequality follows from the B-warm during the update, Lemma B.2 and the following fact
Js. k(2)dz &
k(z)dz.
Rd
Besides, the constant C' is provided by Lemma B. as
(x))d S C.
For E (x)), we have
(x)
(x)))))
(m)
(x=2)
(T)
((Fuloz)) -f((z)))
[s(ar) -f((x))
1 1-exp exp
(x)
(x)
[x)
[(((z) - (IL(Wx)
-(A((e)) S(((az)
(56)
(x)
2
(()
(V. (xx) - V/-(x) + v.((x)) - VV (ar)= 3Lo²
||
(x)
(x)
5Lo²
f.. (z)z oVf (x))
||21|
(p)(#)
Similar to Eq. 55
we have
2
[ J
(xx)
k(z)
V.f((z))
dædæ
(p)
(xx(xx)
(r(
0 Vf. (x)z - oV (x)z +
5Lo²
k(2))
(z)z-oVi
|||
(x)
dzdæ
Rd
B.
pp. (x)
2
4
k(z)
f.. (x)) -VV, (x)z + 5Lo²
||
Pt (x)ddda
Rd
B.
20
2
4
k(2)0
(p,(z)) 155
+
[V)(())] dzdæ
B.
(xx
[[2)||=1|
Vp((a)
(1 [[ + 3
1
[VTA(()))1
5L202
||=13) dzdæ
Rd
B.
2
(m(())))
+
[+((() dzdæ
(x)
Rd.
B.
VB0
x(z)||=1 [ Ve.(=) dæd= ///
30
S h(x)]1211 / Vp((x) | [x))l dædx
JRU
00203
k(z)|l=]1 /s. Vpi(x)dedz +
90
/ k(z)
/ /p((z)|lVfi dæd=
+
JRd
2
Rdd
S SVBCaL(M + 1) a +3 +1 t /BCLLMMOR o²+ .o* 3
33s
(57)
Plugging Eq 55 Eq 57
into Eq. 51
we have
Term 1.1 <16 < + 1 + CdL o 23L2((M (M + +1
(58)
+ +5//CLLM o² + CL
With the same techniques in Eq.
we have 51
Term 1.2 1.2 2 { /
(xx))
Ps (x(x))
{(z)
Vf((x)
dzdæ + 5L2
(59)
24 3300,r)
vp- (xz)
18

---

Under review as a conference paper at ICLR 2023
Similar to Eq.
55
when (x),, we have
2
pr(
k(z)
V V..
dzdæ
R
B,
(x)
(Tz)
3 [x=)(( + 11=11
5220²
k(z)) ||=1|²
+
dzdæ
Rd
B:
[
(pr(2)))
+
a ..)(z).
(Iv.f )1 L²002 |
dædæ
pa(a)))
B:
180
Je (Dx( [+++(=))11 dæd=
2
Ra
30
b(2)112| { VP((=z)
[Vf( dædæ + 5L203
/ ((x))22)l* J Vpe(xz)
+
2
Rd
JRt
2
k(()) (s2 V (V.. dadz dad= + 31.03 / b(z)||=||² f Vii(az)dadlz
+
30
gd
SVBCaLAM + a + + VBCI.M o² + 3.333scl. Cdl 1 g1. 1) 1).0",
(60)
where the last inequality utilizes additional 3-warm condition comparing with Eq. 55
Similar to Eq.
57 when E Bu (2)), we have
1 / k(z)
(r(
(xxx))
(.)(())
dædæ
B.
(v)
Vp-(22)
[ a. [(()) ||2 Vp((z). 2 [[
3 [f(()))
5T262
|| dzdæ
+ 2
Bu
2
[ RR B..
h(2)0 (pr(2))
[x))l dædæ
(x(x)
VBo
[ (pr(z) dxd= + 30
[ x(<)]|=|| [ Vpr(#) [V
x(x)||=|2
dædæ
2
Rd
2
h=(2)1=111 ( Vp((x)dadz + 80
/ k((z) / VI(l dædæ
2
.Bd
2
Rd
VBCL2M.Cl o3+ 3 CL
/BCCLLM + - o 1)
(61)
Combining Eq.
Eq. 61 with Eq.
we have
Term 1.2
<1
BCdL(M +1) o a + CdL- a 20 BL +1)
(62)
+ 5/FCIM o² + C (M + 1
Without loss of generality, we suppose o & and M 2 1. Plugging Eq. 58 and Eq. 62
into Eq.
50
have
Term 1 <12LM /Bo (16C2+ 93Cd
2M + 6 6 BL DL + 3CL+++CCLCC BCL).
(63)
which means if we set
('12LM (16Cd+
93Cd
+ BIBBI.3+TT BBTT+
min
(64)
2M
KAE satisfies
(x(x))
(x
KAE < 4e +
p+(x))
V In
dx,
Rd
po (x)
p- (=())
and the proof is completed.
19

---

Under review as a conference paper at ICLR 2023
C
THE MAIN THEOREM IN SECTION 3
Before providing the main theorem, i.e., Theorem 3.1 we need to introduce some lemmas.
Lemma C.1. Suppose Assumption [A, A are satisfied, and po near to the target pa satisfying (p.o p.) S 1/4,ff for any time T In where (163C)-3, we have
Dx(pr. p.) 1/2.
Proof. We denote Dx² (pr. P.) as chi-square distance between Pt and P.. We have the following functional derivative
dDx dDx(Pt.P.)
8D (Pt.
(pr)0rp,de = J Sa 2 Pr(a) d.pi (x))xx (a(x)
(65)
dl
R2
öp
Combining the result with Remark
2 we have
dD (Pt(
2V (t(x))
J Pc(B))(Zz.) 3) VIn P((
dydæ
dt
Jd
px(x)
(z
(66)
2V (t(
[ (-(y)k(a,,))
Pr( dyda p. (.)
Rd
(x)
Plugging 20 to the previous equation, we have
dDx(pt (pt, P.)
/
(r(
Pt(a:)
/ ((2,8) P.
Pr dyda (y)
dt
Rd (p)
(x(x)
gd
= =- 2 / P)(x))
(a:)
dx - 2 P+(x:)
V Pt(x))
V
Rd
Da (x(
JRd (p)
(2
( Rd
P:(y))
Pe (x)
Tax 4)
P. (g)
Vp.(z)) v
dar
(V)
p. (xx)
(67)
f Rd
4 (x)
(x))
dæ
P+ (xx
+ / (c(x))
1 k(æ, y) Vp.
v pi(u) p.(v)
Pr(x)) (=x
Vp.(x))
dæ
nd (x)
399 KAE
where the last inequality follows from the pt warm assumption. Suppose we control the KAE by Eq. 64 which means 0 (Pt. P.) S 48c, and time T = -C' In which leads pt to the target region, ie., KL(p, < e by the linear convergence, when e is small enough, e.g., c S (163C) -2 and (2o,, 1/4 have
(PT.TPP)) s (x p.) 43ET Dx p.) 4C Dy + < 1/2.
Hence, the proof is completed.
With these Lemmas, we provide the main theorem proof in the following.
Proof. Suppose Hp. (p.) (T.(p.llp.) for abbreviation. According to the time derivative of KI. divergence along any flow, we have
[
811p
Hp. (p+) (0i)= öp
(pe) d.peda.
(68)
Therefore, along Remark 2 we have
d Hp. (pt) =
In (x(x)
-
(x)))
dt
(x)
Rd
(69)
= 1 J
(c( Pr(y)
k( (2)))))))))
dydæ.
(x) (v)
Rd
20

---

Under review as a conference paper at ICLR 2023
which follows from Eq. 36 By taking
k( v) = (v=( 1/2 (a, v) (v+(
Equ
69
satisfies
d
11 (pt) - fps (((
In Pc(xx)
(1
In pr(y)
dæ
Ki (xx, (2,
dy
dl
(x)
Po (z)
Jzd
(p-(1)
p.(
(x(
In (x
[ Tro (xx,
Pt
V In pr(y) dy (+(
(2)
Pe (x))
BRd
P+ (y)
P((x)
In (a(
Pr (x
V In pr(x))
dæ
(p)
P+ (x)
V Pa a
P. (x
Pc(
Pr (x
Jud (z)
In
dæ
(x
(x(x)
(c(
VI (c(
| Too (xx y)
Pr(y)
Vn Pe(y) dy pv(
(70)
(x)
P+ (x)
(p)
(a(
In (c
dæ.
VP)
P+ (x)
(x)
V In (x)
2
< 2 Rd
(xx)
dæ
Pa (x)
Po (ar)
(x)
(x
Pr(y)
v In Pe(y) dy Ps (
+ 2 Rd
In
(a y)
dx
Vp+(2))
P+ (x)
Rd
(y)
Kernel Approximation EKror(KAE)
the decreasing of KL divergence of SVGD at time satisfies
((( (x)
V Pc(x)
1
Hp (pt) v P. (xx).
dæ + 4e
dt
Rd
(x(
(71)
/ Hp. (pt)
<
+ 4c,
16
where the first inequality follows from I Lemma 4.3 and the second one follows from Lemma 4.2
However, Lemma 4.2 requires a local condition Pt which we proved Lemma C.T
By applying
Gronwall's lemma, Eq. 71 implies the desired bound
Hp. (pt) max (0. (H.,
64c mn
)) exp
64c
(72)
1
16
Hence, the proof is completed.
Remark 3. Actually, instead of the constant upper bound of the density ratio provided in Assump- tion A we allow the upper bound of the density ratio to be upper-bounder as
sup (c(x)/p.(et P(t).
where P(I) denotes polynomial function. Without loss of generality, we suppose P(() (1 1)9. In this condition, reweighted SVGD can achieve an (11 (11/c) when we choose
min (1,6-
(73)
21

---

Under review as a conference paper at ICLR 2023
In the following. will show how this choice affects the kernel approximation error shown in Lemma 4.3 Similar to Eq. 63 we can obtain the following inequality
(16Ca+ 192ILMCd V P(t)a 54LCd.
9P(t)Cd
Term S12LM V P(t)o,
2M
(74)
P(
+ 36I /((t)a, + 1CL P(t)
We will easily obtain that
(1 (1+ (1+1.5g)² (..11.g)55pp 55q e 11-1.
plo (L,0 = + 1)1..1 e -(+1) &
t+1 1
and
Term (192LMCd 54LCd+ 36L2 12L2MC) (1+ + 1.5q)' .5q .5.. -1-1.5 (t+1)²
For abbreviation, we suppose
C. (192LMCd++ 5 36L M + 12L2MC) (1 + (.5g)') .5q 11-149
Then, Similar to Eq.
71 we have
d
Hp. (pt) S -1 1
Pr(x))
In (r(x)
4C
(a()).
V
dx +
dt
4 l2u
(x)
p. (x)
1
(75)
11
H (pt)
4C.
16
1+t
It means the KL divergence Hp. (pt) satisfies
u(t [[
u(t + 1)
-ut
Hp. S 4C, exp
Ei
+ (p))
cxp
(76)
16
16
16
where is denoted as
exp(- t
Ei(r)
dt.
According AAbramowitz 1972
we have
In(1 2
-Ei(r))
S
2
cu(
1(t+1)
32
64C²s
4C's exp
Ei
S -C2, In(1 pll
5
16
16
p(l 1)
32'
where the last inequality follows from In(x) 2 1/x. Hence, by requiring RHS of Eq. 76 to be smaller than we have 2 64CC/(ue) + 32/u.
In the following, we will show that a convergence rate can be obtained by approximating an unknown normalizing constant of the target distribution p. (similar to Theorem 3.I.
[ [As] are satisfied, chi-square D (po. 1/4 and PDF of target distribution p. (x)) can be estimated by (xx) satisfying
Proposition C.2. Suppose Assumption
(-
(f(())
(=(x)
(x())
where 0 O<C., <
C.
For any 0, if we set reweighted kernel k: i( y) = (x)) 1/2 T (z. 3) (y)) 11/2 1/2
Tz v) = h - y) = 0
-Til (x -y),
1 1 k(y)dy - M, and
1
T y)dy S 2
JRd
(77)
22

---

Under review as a conference paper at ICLR 2023
where
min 11 (16C&+
93Cd
BCL)
+ +6 +6/BL+3CL 3CL 3 (78)
2M
then the KL divergence between Pt and p. satisfies
Hp (p:) S max (o, (0.(1p.00))
64c 6ig
)
jtt C
64c
exp
(79)
1
C
Proof. We suppose the following reweighted kernels
k(n, y) = 1/2 (x (p. (1)) (1))- -1/2 k(x y) = (0.(x)) 1/2 ko (x, (f. 1/2
lead to different update rules which are
Φe (x) =
(K: (ax, y) Vln,, (3) + Vy (a: v)) dpr(y)
/ k(z,g) In pr(y) (.(
dp:
de (x) / ((x,)) V Vnng. (y) + v y (z. v) dy:(y)
/ (k (2.y) Vinp. ( + V v (z. (). dp((z)
/ M(x,)) v)
Pr y)
v In
p+ y (3)
where the second and the last equations follow from integration by part. Hence, the dynamic of KL divergence under &e becomes
d dl
(pt) = / In
(c( (a
Hp.
(x)).
Rd
Vn (((x)
di (x)))()))
(80)
C. Rd
p. (x(x)
Č (
1-11-
Hp. (pt) +
C.
where the equation follows from the definition of ht and the inequality follows from Theorem 3.1 By applying Gronwall's 'ss lemma, Eq. 80 implies the desired bound
Hp. (p:) I max (0, (HH,
64c
)) .exp
1ul
64c
+
(81)
11
16
C,
#
This proposition demonstrates that approximating unknown normalizing constant will not harm the linear convergence rate of SVGD with reweighted kernels, and only provides an additional factor
C/C, in total complexity. The very common question is that it seems that the convergence can be arbitrarily fast when the factor Ć/C, is large enough. Actually, should notice this convergence rate only establishes in asymptotic analysis, which means the discretization error cannot be controlled without a tiny step size when C/CC large. That means a large C/C. usually implics a small step size in practice rather than arbitrarily fast convergence.
23

---

Under review as a conference paper at ICLR 2023
Ncwikiites Hared
Rowe shood Sore!
Novoliiee Brre
82. Oherrggono
Karations 180
120
1309
Ecration
(a) Po [ 0J, d0.gg(0.2, 0.25)) (b) N[O (0.g 0.5))
(c) N(, diag(1, 1))
Figure 3: Reweighted vs smoothing kernel (IK particles), p. (NO, 0J, diag(5, 1)).
Sneerinng Newaghted Hurd
Sayothiin loni groad famal
Novegeted kord
KL. dvoogoncc
divegeence
23
52 180 300
Dho
200 aho
26
20
2008 100
250
188
23 28
180 300
1860
100 180
(a) = (NO 0], doddiii0.22 (0.25, 0.25))
(b) = =N 0J, d0.5
(c) = NV 0J, diag(1, 1))
Figure 4: Reweighted vs smoothing kernel (0.5K particles). p. = (N00 0], diag(5, 1)).
D EXPERIMENTAL RESULTS
In this section, we conduct the SVGD with reweighted kemelss in some synthetic data to validate our claims, i.e., compared with traditional SVGD, SVGD with reweighted kernels can achieve any e-neighborhood with a linear convergence. To validate our theoretical results in asymptotic settings, we choose different particle sizes and show that sampling by SVGD with reweighted kernels can obtain a lower KL divergence.
To demonstrate the efficiency and stability of SVGD, we provide a numerical illustration for these two algorithms in Figure It is clear that Langevin dynamics suffer from the introduction of the stochasticity, which makes the particle highly unstable. Thus, it is necessary to use more particles to perform the task to guarantee the stability.
(a) SVGD (seed = 1)
(b) SVGD (seed = 2)
(c) SVGD (seed = 3)
(a) Langevin dynamics (seed 1)
(b) Langevin dynamics (seed 2)
(c) Langevin dynamics (seed 3)
Figure 5: SVGD vs Langevin dynamics.
24


Reviews:
[{"review_id": "ZUrMBW8Kij", "reviewer": "Reviewer_ecWW", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 using a reweighted kernel by the target distribution for Stein variational gradient descent (SVGD) and provides its convergence analysis. Specifically, the authors show the convergence of the proposed method under the standard log-Sobolev inequality (LSI) with additional assumptions on the trajectory which are empirically verified by the synthetic experiment.", "summary_of_the_review": "The paper certainly contributes to the context by giving a specific example for Stein LSI. But there are still limitations compared to Langevin dynamics. Examples that satisfy additional assumptions (A2) and (A3) would increase the significance of the paper.\n\n-- After reading the author's response --\nMy concerns have been well addressed. Indeed, I agree with reviewer 8ZrX that assumptions are rather strong. However, I think this paper suggests a new strategy for the convergence analysis of SVRG under Stein LSI, which is a quite challenging problem. Thus, I would like to keep the score.", "strength_and_weaknesses": "**Strengths**:\n\nThe convergence analysis of SVGD is challenging because of the vanishing gradient phenomenon caused by the kernel smoothing of the gradient. Previously, Stein LSI was used for the convergence analysis in the related studies, but examples which satisfy this condition are very limited. Instead, this work managed to show the convergence by exploiting the standard LSI  like Langevin dynamics. Moreover, it is also clarified that a reweighted kernel basically provides a sufficient condition for Stein LSI. Thus, this work well contributes to this context.\n\n**Weaknesses**:\n\n- There are several limitations in the main result (Theorem 3.1) compared to Langevin dynamics. For instance, the theory requires a warm start condition $D_X(p_0,p/*)\\leq 1/4$ and bounded and smoothness conditions on the trajectory of $\\{p_t\\}$ in Assumptions (A2) and (A3).  Although the latter conditions are verified empirically in a synthetic experiment, it would be nice if the authors could provide a specific example. Such an example will make the paper stronger.\n\n- A reweighted kernel involves the value of the target distribution $p_*$. Thus, the computation of the normalization term is needed. This computation is not trivial and approximation error to the normalization usually remains. How does the error affect the convergence rate? It would be better to clarify this.\n\n- SVGD with a reweighted kernel using a small $\\sigma$ will finally get close to the Wasserstein gradient flow of KL-divergence when $p_t$ is close to $p_*$. Thus, I’m wondering what the advantage is over Langevin dynamics. The empirical or theoretical comparison with Langevin dynamics will be helpful if possible.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "4wWPdXQpTr", "reviewer": "Reviewer_8ZrX", "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 studies the problem of sampling wrt to a distribution p* proportional to exp(-V) given access to the gradient of V. The authors consider the mean field limit of Stein Variational Gradient Descent (SVGD). More precisely, SVGD algorithm is an algorithm that relies on updating sequentially the location of a finite number of particles in order to their empirical distribution to approximate the target distribution p*. To run SVGD algorithm, one has to select a RKHS and use its kernel in the update. In continuous time, and with an infinite number of particles, SVGD algorithm converges to a PDE called the SVGD PDE, or in this paper, just SVGD. This PDE rules the evolution of the distribution p_t of the particles. \n\nSVGD can be seen as a dynamics to minimize the KL divergence w.r.t. p*. One issue with this perspective is that the time derivative of KL along SVGD is equal to the opposite of the squared kernelized gradient of the KL. One would like to obtain the squared gradient of KL in order to use Polyak Lojasiewicz inequality (called Log Sobolev Inequality in this setting). This paper develops a technique to do that.\n\nThe main result is that, under LSI and using the reweighted kernel, SVGD PDE converges linearly (in terms of KL) up to a neighborhood.", "summary_of_the_review": "The paper uses interesting techniques but the exposition is below the standard (especially from Section 3). Besides, the assumptions are too strong, and I wonder if the main message of the paper (linear convergence in KL up to a neighborhood) is actually true.", "strength_and_weaknesses": "Strength:\n\n- I have been wondering for a long time how to use a target distribution specific kernel for SVGD, and the reweighting technique sheds some light.\n\n-Section 1 and 2 are well written and I appreciate the overview of Section 2.\n\nWeaknesses:\n\n- This paper considers the infinite particle regime and the continuous time. Although it sheds light on SVGD algorithm, it is still far from the practice of SVGD (I know that the finite particle regime is an open problem). Besides there is some confusion in the paper about continuous and discrete time. In continuous time, the current analyses of SVGD are rather easy and they do not require the kernel to be bounded. Boundedness of the kernel is used in discrete time to establish the descent lemma (Liu'17, Korba et al' 20 and Salim et al 21). So, in my opinion there is no contradiction between Eq 18 and Eq 19 in continuous time.\n\n- In particular, I am worried about how all these results carry in discrete time, since this is where the kernel usually needs to be smooth.\n\n-Assumptions A2 and A3 are conditions on the trajectory of the dynamics, I don't think that they are more reasonable than a bounded kernel. They would need to be proven. This problem is acknowledged and studied empirically though. But A2 and A3 seem cooked up in order to obtain the final result.\n\n- I would have liked to see a comparison between KSD convergence and KL convergence, and why KSD convergence is weaker (even if I understand the intuition)\n\n-I expect the paper to be difficult to read for non-experts (see below).", "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": {}}, {"review_id": "22_zopAG5J8", "reviewer": "Reviewer_sU2Z", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 the convergence rate of SVGD with a reweighted kernel. The main theoretical result is the local linear convergence rate to the target in the sense of KL divergence using the reweighted kernel. ", "summary_of_the_review": "This paper proves the convergence rate of SVGD with a reweighted kernel. The paper is clearly written. But the empirical results are weak.", "strength_and_weaknesses": "**Strength**\n- The idea of introducing a reweighted kernel is well-motivated. \n- The paper proves the convergence rate of KL divergence in a neighborhood of the target.\n\n**Weakness**\n- The reweighting requires the knowledge of $p_*$ or $p_t$. They might not be tractable, e.g. the normalizing constant is unknown. The idea doesn't lead to a practical algorithm.\n- The experiments only have toy examples (2d Gaussian with diagonal covariance). SVGD is expected to sample from much more challenging distributions. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject