Understanding the Variance Collapse of SVGD in High Dimensions
Authors: Jimmy Ba
Murat A Erdogdu
Marzyeh Ghassemi
Shengyang Sun
Taiji Suzuki
Denny Wu
Tianzong Zhang
Venue: ICLR 2022 Poster (2022)
Keywords: Stein Variational Gradient Descent
Approximate Inference
Particle-based Variational Inference

Abstract: Stein variational gradient descent (SVGD) is a deterministic inference algorithm that evolves a set of particles to fit a target distribution. Despite its computational efficiency, SVGD often underestimates the variance of the target distribution in high dimensions. In this work we attempt to explain the variance collapse in SVGD. On the qualitative side, we compare the SVGD update with gradient descent on the maximum mean discrepancy (MMD) objective; we observe that the variance collapse phenomenon relates to the bias from deterministic updates present in the "driving force" of SVGD, and empirically verify that removal of such bias leads to more accurate variance estimation. On the quantitative side, we demonstrate that the variance collapse of SVGD can be accurately predicted in the proportional asymptotic limit, i.e., when the number of particles $n$ and dimensions $d$ diverge at the same rate. In particular, for learning high-dimensional isotropic Gaussians, we derive the exact equilibrium variance for both SVGD and MMD-descent under certain near-orthogonality assumption on the converged particles, and confirm that SVGD suffers from the "curse of dimensionality".

Published as a conference paper at ICLR 2022
UNDERSTANDING THE VARIANCE COLLAPSE OF SVGD IN HIGH DIMENSIONS
Jimmy Ba! Murat A. Erdogdu', Marzyeh Ghassemi! Shengyang Sun Taiji Suzukiš, Denny Wull2, Tianzong Zhang
University of Toronto, Vector Institute, Unniversity of Tokyo, *RIKEN AIP, TTinggua University
{iba, erdogdu, marzyeh, ssy, dennywu]@cs http://wess..ooottttoo.o www.too..oooooooooo edu, taijismist Sestt...uutooio tokyooooccc.. jp, ztz16@mails, tsinghua. ewwphhuaaedd.coomm
ABSTRACT
Stein variational gradient descent (SVGD) is a deterministic inference algorithm that evolves a set of particles to fit target distribution. Despite its computational efficiency, SVGD often underestimates the variance of the target distribution high dimensions. In this work we attempt to explain the variance collapse in SVGD. On the qualitative side, we compare the SVGD update with gradient descent the maximum mean discrepancy (MMD) objective; collapse phenomenon relates to the bias from deterministic updates present in the "driving force" of SVGD, and empirically verify that removal of such bias leads to more accurate variance estimation. On the quantitative side, we demonstrate that the variance collapse of SVGD can be accurately predicted in the proportional asymptotic limit, i.e., when the number of particles n and dimensions d diverge at the same rate. In particular, for learning high-dimensional isotropic Gaussians, we derive the exact equilibrium variance for both SVGD and MMD-descem under certain empirically verified near-orthogonality condition on the converged particles, and confirm that SVGD suffers from the "curse of dimensionality".
find that the variance
INTRODUCTION
typical challenge in Bayesian learning to efficiently and accurately learn a complex posterior distribution. Markov Chain Monte Carlo (Robert and Casella, 2013) provides asymptotically accurate samples, but simulating the chain till convergence can be come-consuming. On the other hand, variational inference (Wainwright et al., 2008) approximates the intractable target distribution with parametric families by minimizing the KL divergence, which can be more computationally efficient. Among plethora of variational approximations, particle- based inference algorithms are particularly compelling as they bypass the inherent distributional assumptions on the variational family.
As noticeable example, Stein Variational Gradient Descent (SVGD) (Liu and Wang. 2016) is a deterministic particle-based inference algorithm that iteratively transports the particles by the functional gradient of KL divergence in the reproducing kernel Hilbert space (RKHS). The functional gradient takes the form of a kernelized Stein's operator and only requires access to the unnormalized target density. Despite the empirical successes of SVGD (Liu, 2017; Haarnoja et al., 2017; Kim et al., 2018 8), very few convergence guarantees have been established except in the mean-field limit, i... the number of particles n - oo under fixed dimensionality d, for which has been shown that the distribution of particles converges to the true invariant solution (Liu, 2017; Lu et al.. 2019). Moreover, it has been observed that as the problem dimensionality becomes larger, the variance estimated by SVGD can be much smaller than variance of the target distribution (Zhuo et al., 2017). This observation, which we refer to as the variance collapse phenomenon (see Figure 1), is highly undesirable for practitioners due to two reasons: (i)) underestimating the variance leads to failure in explaining the uncertainty of model predictions, which is key benefit of being Bayesian; (ii) modern Bayesian inference problems usually high- -igh-iimensiona;;; for instance, training Bayesian neural networks (BNNs) (MacKay, 1992) requires inferring the posterior distribution of network weights, which could be more than millions of dimensions in real-world problems (Krizhevsky et al., 2012).

---

Published as a conference paper at ICLR 2022
Our Contribution. We study the algorithmic bias of SVGD that leads variance collapse in high dimensions. We focus on the commonly-use Euclidean distance kernel (e.g., Gaussian RBF kernel), and provide: (i) qualitative understanding on the pitfall of SVGD by comparing it to another interacting particle algorithm termed MMD-descent; (ii) quantitative understanding the variance underestimation in learning simple target distributions. Our findings can be summarized as follows.
In Section 3 we connect SVGD with MMD- a kernel-based particle inference algorithm that performs maximum mean discrepancy (MMD) minimization, and empirically show that despite their similar updates, MMD-descent does not collapse the variance in high dimensions.
In Section 4 we identify the log derivative driving force as the problematic term in SVGD, and design experiments illustrate that the combination of this driving force and the deterministic bias, i.e. the absence of particle resampling, prevents accurate variance estimation in high dimensions.
In Section 5 we argue that the proportional asymptotic limit: d - co, d/n + 7 (0, oc), is more relevant to understanding the variance collapse phenomenon. As an example, we derive the exact dimension-averaged variance of SVGD and MMD-descent in learning Gaussian distribution in the proportional limit, under certain concentration assumption which we empirically verify. Our analysis confirms that variance estimated by SVGD scales inversely with the dimensionality.
BACKGROUND
2.1 INTEGRAL PROBABILITY METRIC
To measure the "closeness" between distributions on X' C Rd one may consider the maximum discrepancy between the target p and sample distribution q over test functions F: (p 9) = supaer [x(z)] - E [h(y)]. known as the integral probability metric (IPM) (Müller, 1997).
If is unit ball the reproducing kernel Hilbert space (RKHS) H. the resulting D is termed the maximum mean discrepancy (MMD) (Gretton et al., 2012), and its squared value can be evaluated as:
MMD² (p, q) Ex [k(2,, x') + En, k(y, 3 2E (x y)l
(1)
where æ, x' P. y. 1 ~ q, and the kernel k Rd Rd R satisfies M(x x) 00.
Stein's Discrepancy. When integration under the target p is intractable, Stein's 's method (Stein et al., 1972) can be used to construct zero-mean test functions w.r.t. p. For diffcrentiable h in the Stein Class of p, i.e., Je Va (d) = 0, the Stein's 's discrepancy (Gorham and Mackey, 2015) is given as
DStein (p. q) suphe E2 V logp(æ) + [z)(
Note that the Stein's discrepancy only involves the score of p and thus the normalization constant is not required. When h is restricted in the product RKHS Hd with inner product (f (. Ei (Ji.gh Ru. the corresponding maximum discrepancy, known as kernel Stein discrepancy (KSD), can be estimated efficiently from samples (Liu et al., 2016; Chwialkowski et al., 2016).
2.2 (DETERMINISTIC) PARTICLE INFERENCE ALGORITHMS
We now consider the approximation of p using particles constructed as follows: starting from the initial particles X {x,}"_ iteratively optimize their positions using the update: x, x; + A(xx)) where 77 is the step size, and A(-) d + Rd is the update direction. Motivated by the SVGD algorithm, we focus on the setting where the update A is deterministic, in which case the particles may converge to deterministic fixed point. Note that there exist other particle-based algorithms that do not fit into this description, such as sequential Monte Carlo (Doucet et al., 2001), and stochastic variants of the particle gradient descent method (Chen et al., 2018a; Gallego and Insua, 2018), which our current analysis does not cover (see Appendix A.4 for discussion on these alternative algorithms).
Stein Variational Gradient Descent. SVGD constructs the update direction A as the optimal perturbation in the RKHS that decreases Kullback-Leible divergence. In particular, constrain A in RKHS unit ball, and take q = 1 En Sn, the update for each partiele given as:
SVGD (x) = Eg E [k(w', V. log logp(x') V ki (0/(20/20) x))
S (w, x) + S2 x)). (2)
driving force
repulsive force
2

---

Published as a conference paper at ICLR 2022
Intuitively, the log derivative term in the update rule S (1 x:) ;= k( x) Vx, log p(x,) corresponds
to driving force that guides particles towards high likelihood regions, whereas the kernel derivative
term S2 (2;; a) V az k(x, x) provides repulsive force prevent the particles from collapsing into the mode. Typically-used kernels in SVGD include the Gaussian RBF kernel k(x, x') =
exp(-11æ æ' 2 (Liu and Wang, 2016; Zhuo et al., 2017) and the inverse multi-quadratic 2/1 / (2x2) (Gorham and Mackey, 2017).
(IMQ) kernel k(ær, x²) 1/v1+
|
CONNECTING SVGD WITH MMD MINIMIZATION
In this section, we introduce another particle inference algorithm termed MMD-descent whose update rule closely relates to that of SVGD. Despite the similarity, we empirically observe MMD-descent accurately estimates the target variance independent of the dimensionality. By analyzing the similarity of the update rules and contrast in the algorithmic performances, variance collapse of SVGD. In this work we focus on the following class of kernel functions.
identify factors that lead to the
Definition 1. Euclidean Distance Kernel can be written as: k(x, y) f (I - 011//²2)
For example, the Gaussian RBF kernel and IMQ kernel both satisfy this definition. Note that is the tunable bandwidth that usually scales with the distance between particles.
We now construct kernel- particle inference algorithm termed MMD- MMD-deecent, which draws inspiration from the kernel herding algorithm (Welling. 2009) and particle gradient descent (Chizat and Bach, 2018). Instead of greedily reducing the MMD by adding one particle time, consider an update rule similar to SVGD that transport all particles together to approximate the target distribution, by minimizing the MMD between the particles and the target via gradient descent:
MMD (x) =
Eyya V Kn y) + Eag!
Va, x
driving forve
repulsive Force
This update can be seen as the finite-particle discretization of the MMD gradient flow (Arbel et al., 2019). For Euclidean distance kernels we have -v,k(x,,,') = wark(ar x') = S2 a); hence, MMD-descent and SVGD share the same repulsive force. Furthermore, when &: is in the Stein class of p, the driving force of MMD-descent can be connected SVGD via a simple integration by parts:
< y)] - Eyru V (1x, y)] Eyyplk(( y) V logp(y)) = (s., (3)
Therefore, the MMD-descent update for a set of particles fa; Ji= can be equivalently written as:
1 Σ (2(
A MMD (x)= Ey
+
We remark that MMD-descent is not a practical algorithm due to the required integration under which is typically intractable. Instead, the purpose of introducing MMDDdescent is compare the update with SVGD and understand the cause of the variance collapse phenomenon.
SVGD vs. MMDDdescent. By comparing SVGD (2) and MMD-descent (4), we observe that:
SVGD and MMD-descent have identical repulsive force.
In MMD-descent, the driving force is integrated under the target distribution p. whereas in SVGD the expectation under the current particle distribution q.
At the infinite particle limit, p q is fixed point for both update rules. In fact, under certain conditions, uniqueness of this fixed point has been established for both updates in this mean-fiell limit (Lu et al., 2019; Arbel et al., 2019). However, in the practical setting where the particle size is not significantly greater than the dimensionality, reasonable "approximation" to the target distribution; (ti) converge to similar fixed points. Given the analogous updates, one natural question to ask is: do SVGD and MMD-descent reliably estimate the target variance in high dimensions, and do they converge to similar solutions?
not clear if the two algorithms: (i) provide a
The empirical answer is in the negative: SVGD and MMD-descent converge to completely different solutions: SVGD is known to underestimate the marginal variance in high dimensions, simple Gaussian targets (Zhuo et al., 2017). In contrast, MMD-descent does not exhibit the same issue empirically. Figure illustrates this discrepancy in Bayesian neural network (BNN) experiment.
for
3

---

Published as a conference paper at ICLR 2022
model output
-0.
model output
-42
model output
-22
HMC (ground truth)
-14
SVGD
MMD descent
input
input
input
Figure I: Comparison SVGD and MMD-deseent in training a two-hidden-layer BNN on synthetic ID dataset. The target distribution is approximated via HMC, and 100 particles is used for SVGD and MMD-descan SVGD (middle) significantly underestimates the target variance, but MMD-descent (right) generates diverse samples.
We consider a two-hidden-layer BNN with 100 hidden units each, so that inference in the weight space is a high-dimensional problem. We obtain (approximate) target samples via Hamiltonian Monte Carlo (HMC) (Neal et al., 2011), and then initialize 100 particles from the target to be optimized by SVGD or MMD-descent with the Gaussian RBF kernel (for detailed setup see Appendix D). Observe that although we used the same number of particles for SVGD and MMD- SVGD severely underestimates the variance, whereas MMD-descent generates diverse predictions similar HMC.
UNDERSTANDING THE PITFALL OF SVGD
We now qualitatively characterize the algorithmic bias of SVGD. Motivated by the observation that SVGD and MMD-descent only differs the driving force which involves Si, we first compare S and S2 in SVGD and argue that the former term is more likely problematic in high dimensions due to larger fluctuation. We then design controlled experiments by modifying the updates of SVGD and MMD-descen to show that when the log derivative S1 is coupled with the deterministic bias (i.e., absence of particle resampling), the algorithm does not reliably estimate the target variance.
4.1 HIGH VARIANCE FROM INTEGRATION BY PARTS
Recall that the update rule of SVGD involves driving force (log derivative) term 1 Ei= S1 x)) n
n and repulsive force (kernel derivative) term 1 Σ (2 æ). From integration by parts we have the following equality: Egy=p[Si [ x]] - Ey--p (52()) x)] Thus the target distribution is fixed point of SVGD when the number of particles tends to infinity. However, in the finite sample setting, the fluctuations in S1 and S2 might have impact on the converged solution.
In many settings, we expect the log derivative driving force S to have higher variance. For instance, in the case of unit Gaussian target p and Gaussian RBF kernel ke( x²) exp(-IIz: xx' 1/1 11/20²), we know that S1 (y, a)) yy .²) and (2y x) a - y) ky, æz). Roughly speaking, when the norm of x. y and the bandwidth a scale with v vd, ||S 1122 increases with the dimensionality. whereas || remains bounded. The large magnitude of S₁ results in large fluctuation in the driving force term in SVGD. In Figure 2(a), we visualize the distributions of S₁ and S2 when the particles x are drawn i.i.d. from Gaussian distributions, and indeed observe the higher variance of St. The following proposition quantifies this discrepancy in an idealized setting.
Proposition 2. Define the mean squared error as: MSE,[f = Ep(a) l1f(w) - Ep(f())]1 Then for y (aa, Ia) where ||a|? 2 O(d), Gaussian RBF kernel k(xx,, y) -xp(- || 1ax-vll. v11 /202) with bandwidth a = ((vi) and x E (d))(vV)), we have
Odd MSE,|S1 x)] O(d).
More generally, for a E gd (V=)( strongly log-concave p. and Euclidean distance kernel with Lips- chitz f and nower-bounder by scaled Gaussian kernel, MSE.,/S1 x)] = R(d)) MSEp1S2(y/ m)).
The proposition indicates that when particles are i.i.d. sampled from some target p. then S₁ would have much larger fluctuation than S2 Intuitively speaking, the higher variance in S suggests that more samples are required to estimate the term accurately. Therefore, when the dimensionality is large compare to the particle size, poor estimation of S may relate to the variance collapse. The following subsection empirically demonstrate that this is indeed the case; in particular, we show that in the presence of deterministic bias, the high-variance S₁ leads to "biased" particles in SVGD.
Note that particles optimized by SVGD cannot be considered as i...d. samples from some distribution, and thus Proposition 2 does not rigorously apply to particles obtained by the actual algorithm.
4

---

Published as a conference paper at ICLR 2022
1250
log derivalive 15g)
1.0
1000
kernel derivative
1.5
Marginal veriience
0.8
count
variance
1.0
6.66
SVGD tresampled 5
SVGD foriginali
SVGD (resampled S,)
500
0.4
target variance
250
0.5
derivativa (resamplcd)
kernel dertvative (ftxed)
-0.05
0.00
0.05
0.10
1000
2000
3000
20
60
100
sample mean
number of iterations
Dimensionality (d)
(a) Distribution of Sr. S2.
(b) Deterministic bias in MMD.
(c) SVGD with resampling.
Figure 2: (a) Distribution of sample means of S and S2 for Gaussian target and Gaussian RBF kernel. (b) Particle variance of MMD-descent initialized from (O, 0.21a). Darker color indicates larger particle size. Resampling or A MMDD (fixed) results in correct variance, but A/ (fixed) diverges. (c) SVGD (n=20) with resampled S₁ accurately estimates the variance, but resampled S2 still leads to variance collapse.
4.2 BIAS FROM DETERMINISTIC UPDATE
In this subsection we isolate cause of variance collapse that relates to the deterministic nature of the update rule. Observe that in the derivation of SVGD. particles {æx )==) are assumed be sampled from some underlying distribution q. But due to the deterministic update, q is entirely represented by the same set of particles, and redrawing i.i.d. samples is not feasible during optimization. We now demonstrate that this failure to resample, which we refer to as the deterministic bias, when combined with the log derivative driving force 51, may cause the algorithm to converge to the wrong target.
Deterministic Bias in MMD-descent. We start with an illustration of deterministic bias in MMD- descent. Given samples {y:} p drawn from the target, we have distinct MMD-gradient updates (connected via integration by parts (3)) that differs in the driving force.
A AMMD (x:
1 m
S1 (1),
E S2(1,
AND
MMD (x)
m Σ S2 x) 55a(2: x).
12
We refer to A MMD and MMD as the log derivative update and the kernel derivative update, respectively. Section 4.1 suggests that A AMD tend to have larger fluctuation than AMD For both update rules, we consider the two variations: (i) fixed particles, where we draw {y, in the beginning and use this same set of target samples throughout optimization; (ii) resampled particles, where we redraw new i.i.d samples { fy from p at each iteration. In this construction, the fixed exed-particle update (i) emulates the deterministic bias in S1, due to the absence of resampling from p.
We simulate the two variants of MMD-descent in Figure 2(b), which the target is a 50-dimensional unit Gaussian, n = 50 and we vary m from 50 to 1000. First observe that the log derivative update with fixed particles (solid red), which combines the high variance S1 and the deterministic bias, results in diverged particles. In contrast, the log derivative update with resampled particles (dashed red), in which S is present but not the deterministic bias, converges to the desired variance. Moreover, if the driving force is estimated by Sz, then the variance is accurate even in the presence of deterministic bias, as shown in the kernel derivative update with fixed particles (solid blue). This indicates that the combination of deterministic bias and the log derivative driving force S₁ leads to biased convergence".
Particle Resampling in SVGD. The previous experiment on MMD-descent suggests that the deterministic bias arises from the algorithm not being able to "redraw" i.i.d. samples. We fur- ther validate this observation in SVGD by con- structing variant that achieves particle resam- pling. The modified update exhibits a double- loop structure (see Algorithm I): at iteration i of the outer loop, we obtain a new set of particles indexed as ys after (i-1) inner loop steps. In the inner loop, we first draw n i.i.d. particles q from the initial distribution qo- and then update z via (i (i-1) SVGD steps to obtain qi at each step j of the inner loop, either the driving force Si or the repulsive force S2 is computed between 0; and qj. as opposed to between particles within q. as in the original SVGD.
Algorithm 1 SVGD with Particle Resampling
Input: Initial density qo. Number Steps S.
for s = 1 to S do
Sample {æi H ~ (zx). for = 1 to
do
either Compute
from resampled particles: a <- 2x + Σ5= Si az) (2 at).. or Compute S2 from resampled particles:
x +- a 2 Σ,= S1 x; ( a
end for end for Output (x:))
Due to the different driving force, the log derivative update of MMD-descent with fixed particles results in divergence instead of variance collapse (see Appendix A.3 for more discussion).
5

---

Published as a conference paper at ICLR 2022
We remark that this resampled update resembles transport-based particle algorithms (e.g. Nitanda and Suzuki (2017)), where old particles define a transport map that the new particles (initialized from qo) follow. By construction, at each outer loop iteration, and updated: importantly, one of S1 and S2 is not evaluated on the same set of particles themselves, and hence deterministic bias is not present. However, the complexity of such resampled updates scales quadratically with the iterations, which renders the algorithm computationally prohibitive'.
set of independent particles are generated
Figure 2(c) compares the modified SVGD updates (with Gaussian RBF kernel) in learning Gaussian target. Observe that when the driving force S computed on resampled particles (blue), SVGD accurately estimates the target variance even with small particle size (n = 20) at each step. In contrast, if only the repulsive force S2 is evaluated on particles resampled from qo- then the variance is still underestimated (green), due to deterministic bias in Sj. This confirms our argument that combination of log derivative S1 and deterministic bias leads to the algorithmic bias of SVGD.
SVGD IN THE PROPORTIONAL LIMIT
While the previous discussion provides qualitative understanding of the algorithmic bias of SVGD, no quantitative characterization is provided. In this section, we make use of the deterministic nature of the SVGD update, and directly analyze the particle fixed point; this allows us to precisely compute the variance of SVGD particles and confirm the variance collapse in simple settings.
5.1 SCALING LIMIT AND BASIC ASSUMPTIONS
Previous works have considered the infinite-particle limit of SVGD under fixed dimensionality, which is known as the mean-field limit (Lu et al., 2019; Duncan et al., 2019). In this regime, the particle dynamics of SVGD is described by nonlinear PDE: a,p- V (p(K' (Vp VVP))). which converges weakly to the unique target measure as + oo under certain non-degeneracy assumptions. However, since the invariant solution is the desired target distribution, the mean-field limit does not capture the variance collapse phenomenon. Moreover, similar guarantees can also be derived for MMD-descent under similar assumptions (Arbel al., 2019). Therefore, the mean-field limit does not explain the observed discrepancy between SVGD and MMD-descent (Figure I in Section 3).
Instead, we propose to analyze the algorithm in the proportional asymptotic limit:
(A1) Proportional Limit. n, d + oc and d/n Y; we also assume 7 >>> 1.
Note that larger y is analogous higher dimensionality or smaller particle size; focus on the > regime, where the number of particles is less than the problem dimensionality - this is common feature of modern Bayesian inference problems. In this asymptotic limit, prior works studied spectral properties of the kernel matrix (c.g., El Karoui et al. (2010)), which the SVGD update crucially depends upon. However, these random matrix results typically require the particles to be i..d., which is not satisfied by SVGD due to the interacting update. To overcome this technical difficulty, we make an additional assumption on the fixed point:
(A2) Near-orthogonality The optimized particles {æ: satisfy |a, a; dul < vea l (oTayl- Veg for all i + j. some > 0, and d 1/2 + 0 as d + oo with probability 1.
The above assumption ensures that the particles tend to equilibrate at fixed point where they "repel" one another as much as possible (due to the repulsive force), as shown in Figure 3 for the case of Gaussian target. While this is condition only the fixed point of the SVGD algorithm, not on the particles produced by the SVGD iterations (unless initialized at the fixed point), we note that it is still stronger than making an assumption on the sampling problem. We refer Appendix A.2 for additional empirical verification and leave the rigorous justification as future work.
a12)
Gousttn cernel
MO soriet meil bardwist
g
ga.0
Reed o-
$a.0
0.04
50
100
150
200
250
number of particess
Figure 3: Empirical verification
of (A2) for SVGD in learning isotropic Gaussian (? 3).
Under assumptions (A1) and (A2), we can approximate the Gram matrix via Taylor expansion of the kernel matrix, which allows us to simplify the fixed point equation. We restrict ourselves to the following class of kernels:
"Resampling can also be achieved via kernel density estimation (KDE) each iteration, in Dai et al. (2016). However, KDE is also known to be less effective in high dimensions.

---

Published as a conference paper at ICLR 2022
(A3) Kernel Function. k( y) =
where f: :200 - R. is bounded, monotonically
2
decreasing, and differentiable on R20-
Remark. (A3) covers common choices of Euclidean distance kernels with decaying tail, such as the Gaussian RBF kernel, the IMQ kernel and the log- inverre kernel. Our analysis also allows for different choices of bandwidth o, which we specify the sequel.
5.2 LEARNING HIGH-DIMENSIONAL GAUSSIANS
We now consider simple example in which SVGD does not reliably estimate the variance learning an isotropic Gaussian target (empirically observed in Zhuo et al. (2017)). Note that our goal is to demonstrate negative result: we do not claim that SVGD underestimates the variance in all settings; instead, we show that variance collapse is present even in learning the simplest target distribution.
(A4) Gaussian Target. p(a:) exp (- x).
Remark, We assume (A4) for simple and concise presentation, and we believe that the result can be extended to more general Gab-Gaasiinn targets. In addition, since Gaussian prior is widely used in Bayesian inference, it is natural to expect that largel potentials in many real-world problems are "Gaussian-like -ikee" (i.e., exhibit quadratic growth) outside of some radius (Cheng el al., 2018a). Indeed, our empirical observations on BNN align with our theoretical predictions for Gaussian target.
We compute the dimension-averager marginal variance: e v= + Var, ((æ;)==), where (-) is the particle variance at the j-th coordinate. Since v is scalar quantity, accurate estimation in the proportional limit (A1) ) is not impossible; in fact, in Appendix A.4 show that running Langevin Monte Carlo (LMC) for ((d) iterations using one particle would suffice. In the following subsections we derive the equilibrium variance of SVGD under two different choices of kernel bandwidth.
Kernels with Adaptive Bandwidth. We first consider the case where the bandwidth a is adaptively tuned based on the optimized particles. In particular, we analyze the median heuristic (Scholkopf
and Smola, 2001):
/ Med 1/112)/,, /2, which is the most common choice made in practice. Under the previous assumptions, we have the following result for SVGD with median bandwidth.
Proposition 3. Given (AI-4) and the choice of bandwidth = - Medk - = particles driven by SVGD (Equation (2)) equilibriate at the dimension-averaged variance
SVGD = (()) f(o)]='
Remark. The proposition precisely captures our observation that SVGD underestimates the dimension-averagee variance inversely proportional to the problem dimensionality (T = d/ In contrast, previous analysis (Zhang al.. 2020) predicts that SVGD would collapse to zero variance as +-++oo oc, which does not align with the empirical observations.
For Gaussian kernel, we also provide a precise contrast between SVGD and MMD-descent.
Corollary 4. Given (Al-4), for the Gaussian RBF kernel f(x) = exp(-a) with the median band- width, SVGD converges the following dimension-averagge variance: DVGD 1)) 1, 111-1 1, whereas MMD MeD-descent (Equation (4)) leads to y MMD = 1.
In other words, as the problem dimensionality y increases, more particles are required for SVGD to reliably estimate the dimension-averagee variance (specifically, the number of particles should grow linearly with d). In contrast, the variance estimated by MMD-descent remains accurate and is independent to y; this aligns with the empirical observations in Section 3. Remarkably, Figure 4(a) demonstrates that Proposition is accurate even for reasonably small n, d: observe that once 7 > (i.e., d > n)), the prediction (black) becomes well-aligned with the empirical value.
Kernels with Fixed Bandwidth. One possibility remains that the culprit of variance collapse is the median bandwidth. Specifically in kernel Stein discrepancy (KSD), has been argued that the IMQ kernel can outperform the Gaussian RBF kernel (Gorham and Mackey, 2017), and the IMQ kernel is often employed without an adaptive bandwidth. Due to the connection between KSD and SVGD, one may speculate that the IMQ kernel with fixed bandwidth can alleviate the variance collapse problem.
For the median bandwidth, only require local differentiability around 1, similar to El Karoui et al. (2010).
7

---

Published as a conference paper at ICLR 2022
Target veriance (n-50)
10-1.
0.8
Target variance
80.8
Marginal poriel/yarrnoott
SVGD (n=25)
(n=25)
0.66
[n=25]
0.6
vid in-50)
6x10
y-2
MMD (n=
0.
prediction
4 xx10-
0.2
0.2
y
3x10
0ld (1))
50
100
150
200
50
160
150
200
10
10" Dimensionality (d)
2
Dimensionality (d)
Dimensionality (4)
(a) Gaussian RBF Kernel (median). (b) IMQ Kernel (a = + d)
(c) IMQ Kernel (ar = 1).
Figure 4: Stationary variance of SVGD and MMD--escent; predictions (black) are given by Proposition 3 and S. (a) Gaussian kernel with median heuristic: SVGD underestimates the variance, but MMD-deecent (blue) does not. (b) IMQ-SVGD underestimates the variance under both the median heuristic (red) and fixed a = vd (bluc). (c) When = 1, IMQ-SVGD asymptotically collapses the variance to 0 at rate of d=1/3 (black).
We show that this is unfortunately not the case. We first provide general characterization: Proposition 5. Given (Al-4) and fixed bandwidth a = vd, the SVGD variance satisfies f' (V - 7 [ f(0)]
In addition, f' is also monotone Rz0, then sooD decreases as y increases.
Note that the monotonicity assumption again satisfied by many Euclidean distance kernels of interest. While the equation may not provide an explicit expression of the stationary variance, we can verify that the variance decreases as the problem becomes more high-dimensional (i.e., larger ?). Our next proposition specifically handles the IMQ kernel considered in Gorham and Mackey (2017).
Corollary 6. Given (Al-4), the IMQ kernel f(x) = (1 +1+23 x) -1/2 with fixed bandwidth, we have the following stationary variance of SVGD under two different scalings:
When Vd, SvGD and is decreasing as 7 > increases.
When = 1, woo + as n, d + oo at a rate of d d-1/3,
This corollary suggests that the IMQ kernel with fixed bandwidth is not remedy to the variance collapse problem. We remark that the second setting (o 1) is considered in Gorham and Mackey (2017) for KSD. In both cases (and including the median bandwidth covered by Proposition 3), SVGD- IMQ underestimates the target variance as the dimensionality increases (large 7). The agreement between the theoretical predictions and the empirical simulations (using finite particles) is illustrated in Figure 4()) Finally, in Appendix A we include a more general (but less precise) characterization of variance collapse beyond Gaussian target, as well additional empirical evidence.
5.3 A MODIFICATION OF SVGD
We have thus far shown that in the simple setting of learning nigh-dimensional Gaussian, SVGD underestimates the dimension-averaged variance unless the number of particles is larger than the di- mensionality. Now we further validate our theoretical findings by introducing heuristic modification of SVGD that corrects for this variance collapse in the overparameterized regime".
The starting observation is that the variance collapse indicates that the deterministic bias causes the driving force term to dominate, Because during each update every particle æ; is most "correlated" with itself, one should expect S₁ (æ; .x.) to contribute significantly to this bias. We thus consider modification of SVGD which simply shrinks (damps) the term S (æ., 2x)) by X min (1)
(')) (0)), where À is chosen such that when d > the equilibrium variance matches the target variance in the setup of Proposition 3. We refer to this update as damped SVGD:
Damp (x:) )- = [I),(E) + (2(2,, x;) + XS (x.,
(5)
372
Remark. At high level, (5) resembles the annealed SVGD algorithm (D' A'Angelo and Fortuin, 2021), that they both "weaken" " the driving force St. However, annealed SVGD uses a heuristic learning to modify the strength of S1, whereas we derive our X to ensure that the dimension dimension-avvragee variance is correct under (Al-4) in the > n regime.
rate schedule
Note that the fixed bandwidth can he arbitrary, as constants can be absorbed into the function f. The modified update in Section 4 also alleviate the variance collapse, but is computationally intractable.
8

---

Published as a conference paper at ICLR 2022
Simulating Toy Densities. We demonstrate the use- fulness of this birs-correction term in learning sim- ple target distributions. We stack 250 independent 2- dimensional distributions to create a high-dimensional target distribution, and visualize the first two dimen- sions in Figure 5, We optimize 50 particles using SVGD or SVGD (damped) with the Gaussian RBF kernel and median bandwidth.
34000
24000 rpeii
As shown in Figure 5 (top), SVGD collapses its par- ticles to the mode, whereas damped SVGD generates more dispersed particles with variance exactly match- ing that of the Gaussian target. It is also possible that the heuristic modification leads to more accurate sam- ples for other "Gaussian-like" target distributions' shown in the second row of Figure 5. We provide additional experimental results in Appendix A.3.
Figure 5: Points represent converged particles of SVGD (middle) and damped SVGD (right). We also report the dimension-averrged variances in the figure. In the Gaussian case (top), SVGD (damped) exactly Iearns the target variance.
6 RELATED WORKS
Guarantees and Applications of SVGD, Liu and Wang (2018); Lu et al. (2019) characterized SVGD in the mean-field limit and showed the weak convergence to the target distribution. Under further assumptions on the potential and kernel, quantitative convergence rate can be derived (Duncan et al., 2019; Korba et al., 2020). In addition, Liu and Wang (2018) shows SVGD using kernels with fiiit-ddimensional feature maps, exactly estimates the expectations for some set of functions, casting SVGD as moment matching method. In the high-dimensional setting, Zhuo al. (2017); Wang et al. (2018) observed in experiments that particles driven by SVGD tend to underestimate the marginal variance, but did not provide any quantitative understanding of the phenomenon.
On the application side, Haarnoja et al. (2017); Liu et al. (2017) adopt SVGD to learn a stochastic sampling network to approximate the policy in Q-learning (Sutton et al., 1998), whereas in Gangwani et al. (2018), SVGD encourages diverse policies for exploration. SVGD can be used in meta-learning to quickly obtain parameter samples from training sets (Yoon al., 2018). Recent works also applied SVGD in Batch Bayesian optimization (Gong et al., 2019) and the learning of mixture models (Wang and Liu, 2019). Leveraging the Markov blanket structure, SVGD also achieves strong performance in learning graphical models (Zhuo al., 2017; Wang et al., 2018).
Stein's 's Method. Stein's method provides powerful tools in approximating probability distributions and specifying convergence rates (Erdogdu, 2016; Gorham et al., 2016). Liu and Wang (2016) utilizes the connection between Stein's s operator and the gradient of KL divergence to construct particle inference algorithm. Stein's lemma is also useful in implicit variational inference (Huszár, 2017) to estimate the score using samples from an implicit distribution (Li and Turner, 2017: Shi et al., 2018). Related to our analysis in Section 4, Erdogdu al. (2016) observed that algorithms that equivalent in expectation via Stein's lemma might have different convergence properties. In addition, the "curse of dimensionality" of kernel Stein estimators has also been studied in Oates al. (2016).
7 CONCLUSION
We analyzed the variance collapse of SVGD in high dimensions based on a connection between SVGD and proposed MMD MeD-descentto algorithm. We qualitatively identified factors that lead to this phenomenon, and also quantitatively characterized the equilibrium variance in the proportional limit for simple models. Looking forward, we believe that understanding interacting particle systems (SVGD, two-layer neural nets, etc.) in the proportional limit instead of the mean-field limit is an important direction. In addition, while our analysis confirms the variance collapse of the original algorithm, it remains possible that certain dimension reduction schemes could alleviate the issue; Chen and Ghattas (2020); Gorham al. (2020); Gong al. (2020) proposed pereensioo-rdducce versions of SVGD, and it would be interesting to theoretically justify these approaches.
We however note that due to the ceeributioo-speciffi derivation X we should not expect the proposed modification to be a general solution to the variance collapse problem of SVGD.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
JB was supported by NSERC Grant (2020-06904), CIFAR AT Chairs program, Google Research Scholar Program and Amazon Research Award. MAE was supported by NSERC Grant [2019-06167] Connaught New Researcher Award, CIFAR AI Chairs program, and CIFAR AI Catalyst grant. MG was supported in part by Microsoft Research and a Canadian CIFAR AI Chair held at the Vector Institute. TS was partially supported by JSPS KAKENHI (18H03201), Japan Digital Design and JST CREST. SS was supported by a Connaught New Researcher Award and a Connaught Fellowship.
REFERENCES
Arbel, M., Korba, A., Salim, A., and Gretton, A. (2019). Maximum mean discrepancy gradient flow. In Advances in Neural Information Processing Systems, pages 6484 6494.
Bach, F., Lacoste-Julien, S., and Obozinski, G. (2012). On the equivalence between herding and conditional gradient algorithms. arXiv preprint arXiv:1203.4523.
Bordenave, C. et al. (2013). On euclidean random matrices in high dimension. Electronic Communi- cations in Probubility, 18.
Chen, C.,, Zhang, R., Wang, W., Li, B., and Chen, L. (2018a). A unified particle opttiiiioo framework for scalable bayesian sampling. arXiv preprint 1rXiv:1805. 1659.
Chen, P. and Ghattas, O. (2020). Projected stein variational gradient descent. arXiv preprint arXiv:2002.03469.
Chen, W. Y., Barp. A., Briol, F.-X., Gorham, J., Girolami, M., Mackey, I.., and Oates, C. (2019). Stein point markov chain monte carlo. In International Conference on Machine Learning, pages 1011-1021. PMLR.
Chen, W. Y., Mackey, I.., Gorham, J., Briol, F--.., and Oates, C. (2018b). Stein points. In International Conference on Machine Learning, pages 844-853 PMLR.
Cheng, X., Chatterji, N. S., Abbasi- Yadkori, Y., Bartlett, P. L., and Jordan, M. I. (2018a). Sharp con- vergence rates for langevin dynamics in the nonconvex setting. arXiv preprint 1805, 01648.
Cheng, X., Chatterji, N. S., Bartlett, P. L., and Jordan, M. (2018b). Underdamped langevin meme: A non-asymptotic analysis. In Conference Learning Theory, pages 300-323. PMLR.
Chizat, L. and Bach, F. (2018). On the global convergence of gradient descent for wer-parameterized models using optimal transport. arXiv preprint arXiv: 1005.0955.
Chwialkowski. K., Strathmann, H., and Gretton, A. (2016). A kernel test of goodness of fit. JMLR: Workshop and Conference Proceedings.
Dai. B., He, N., Dai. H., and Song. L. (2016). Provable bayesian inference via particle mirror descent. In Artificial Intelligence and Statistics, pages 985-994.
Dalalyan, A. S. (2014). Theoretical guarantees for approximate sampling from smooth and log- concave densities. arXiv preprint 14Xi::1412.7392.
D' Angelo, and Fortuin, V. (2021). Annealed stein variational gradient descent. arXiv preprint arXiv:2101.09815.
Doucet, A., De Freitas, N., Gordon, N. J., al. (2001). Sequential Monte Carlo methods in practice, volume 1. Springer.
Duncan, A., Nuesken, N., and Szpruch, I.. (2019). On the geometry of stein variational gradient descent. arXiv preprint arXiv:1912.000 1912.0089..
Durmus, A. and Moulines, E. (2017). Nonasymptotic convergence analysis for the unadjusted langevin algorithm. The Annals of Applied Probability, 275))1551
10

---

Published as a conference paper at ICLR 2022
El Karoui, N. et al. (2010). The spectrum of kernel random matrices. The Annals of Statistics, 38(1):1-50.
Erdogdu, M. A. (2016). Newton-stein method: an optimization method for gims via stein's 'si lemma. The Journal of Machine Learning Research, 17(1):5565-716.
Erdogdu, M. A., Bayati, M., and Dicker, L. H. (2016). Scalable approximations for generalized linear problems. arXiv preprint arXiv: 1.1666666
Erdogdu, M. A. and Hosseinzadeh, R. (2020). On the convergence of langevin monte carlo: The interplay between tail growth and smoothness. arXiv preprint arXiv:2005.13097,
Erdogdu, M. A., Hosseinzadeh, R., and Zhang, M. (2021). Convergence of langevin monte carlo in chi-squared and rényi divergence.
Gallego, V. and Insua, D. R. (2018). Stochastic gradient meme with repulsive forces. arXiv preprint arXiv:1812.00077.
Gangwani, T., Liu, Q., and Peng, J. (2018). Learning self- self-imitating diverse policies. arXiv preprint arXiv:1805. 10309.
Garreau, D.. Jitkrittum, W., and Kanagawa, M. (2017). Large sample analysis the median heuristic. arXiv preprint arXiv: 1707 .07269.
Gong, C., Peng, J., and Liu, Q (2019). Quantile stein variational gradient descent for batch bayesian optimization. In International Conference on Machine Learning, pages 2347-2356.
Gong, W., Li, Y., and Hernández-Lobato, J. M. (2020). Sliced kernelized stein discrepancy. arXiv preprint arXiv:2006. 16531.
Gorham, J., Duncan, A. B., Vollmer, S. J., and Mackey, L. (2016). Measuring sample quality with diffusions. arXiv preprint 1611v:161..0697.
Gorham, J. and Mackey, L. (2015). Measuring sample quality with stein's method. In Advances in Neural Information Processing Systems, pages 226-234.
Gorham, J. and Mackey, L. (2017). Measuring sample quality with kernels. In Proceedings of the 34th International Conference on Machine Learning-Volle Voluue 70, pages 1292-1301. JMLR. org.
Gorham, J., Raj, A., and Mackey, L. (2020). Stochastic stein discrepancies. arXiv preprint arXiv:2007.02857.
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. (2012). A kernel two-sample test. Journal of Machine Learning Research, 13(Mar):723-773.
Haarnoja, T., Tang, H., Abbeel, P., and Levine, S. (2017). Reinforcement learning with deep energy- based policies. In Proceedings of the 34th International Conference on Machine Kharning-Volume 70, pages 1352-1361. JMLR. org.
Huszár, F. (2017). Variational inference using implicit distributions. arXiv preprint 17Xiv:1702.08235.
Huszár, F. and Duvenaud, D. (2012). Opeihhel herding is bayesian quadrature. arXiv preprint arXiv: 1664.
Jordan, R., Kinderlehrer, D., and Otto, F. (1998). The variational formulation of the fokker-planck equation. SIAM journal on mathematical analysis, 29(1):1-17.
Kim, T. Yoon, J., Dia, O., Kim, S., Bengio, Y., and Ahn, S. (2018). Bayesian model-agnostic meta-nearning. arXiv preprint arXiv: 03836.
Korba, A., Aubin-Frankowse P.-C., Majewski, S., and Ablin, P. (2021). Kernel stein discrepancy descent. arXiv preprint arXiv:2105.099:
Korba, A., Salim, A., Arbel, M., Luise, G., and Gretton, A. (2020). A non-asymptotic analysis for stein variational gradient descent. arXiv preprint arXiv:2006.09797.
11

---

Published as a conference paper at ICLR 2022
Krizhevsky, A., Sutskever, I., and Hinton, G. E. (2012). Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pages 1097-1105.
Li, Y. and Turner, R. E. (2017). Gradient estimators for implicit models. arXiv; 1XXY::705..71077
arXiv preprint
Liu, Q. (2017). Stein variational gradient descent gradient flow. In Advances neural information processing systems, pages 3115-3123.
Liu, Q.. Lee, J., and Jordan, M. (2016). A kernelized stein discrepancy for goodness-of-fit tests, In International Conference on Machine Learning, pages 276-284.
Liu, Q. and Wang. D. (2016). Stein variational gradient descent: general purpose bayesian inference algorithm. In Advances In Neural Information Processing Systems, pages 2378-253 2386.
Liu, Q and Wang, D. (2018). Stein variational gradient descent moment matching. In Advances in Neural Information Processing Systems, pages 1868-8877
Liu, Y., Ramachandran, P., Liu, Q., and Peng, J. (2017). Stein variational policy gradient. arXiv preprint arXiv: 023999299.
Lu, J., Lu, Y., and Nolen, J. (2019). Scaling limit of the stein variational gradient descent: The mean field regime. SIAM Journal on Mathematical Analysis, 51(2):648-671
MacKay, D. J. (1992). A practical Bayesian framework for backpropagation networks. Neural Computatioo, 472.
Mattingly, C., Stuart, A. M., and Higham, D. (2002). Ergodicity for sdes and approximations: locally lipschitz vector fields and degenerate noise. Stochastic processes and their applications, 101(2):185-232.
Müller, A. (1997). Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429 443.
Neal, R. M. et al. (2011). Meme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(11):2.
Nitanda, A. and Suzuki, T. (2017). Stochastic particle gradient descent for infinite ensembles. arXiv preprint arXiv:1712.05438.
Oates, C. J., Cockayne, J., Briol, F.-X., and Girolami, M. (2016). Convergence rates for a class of estimators based on stein's method. arXiv preprint 1rXiv:1603.0330
Robert, C. and Casella, G. (2013). Monte Carlo statistical methods. Springer Science & Business Media.
Roberts, G. O. and Tweedie, R. L. (1996). Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, 2(4):341-363.
Scholkopf, B. and Smola, A. J. (2001). Learning with kernels: support vector machines, regulariza- tion, optimization, and beyond. MIT press.
Shi, J., Sun, S., and Zhu, J. (2018), A spectral approach to gradient estimation for implicit distributions. arXiv preprint arXiv: 1806.08066..555
Stein, C. et al. (1972). bound for the error in the normal approximation the distribution of sum of dependent random variables. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statisties and Probability, Volume 2: Probability Theory. The Regents of the University of California.
Sutton, R. S., Barto, A. G., et al. (1998). Introduction to reinforcement learning, volume 2. MIT press Cambridge.
Vempala. S. and Wibisono, A. (2019). Rapid convergence the unadjusted langevin algorithm: Isoperimetry suffices. In Advances Neural Information Processing Systems, pages 8094-8106
12

---

Published as a conference paper at ICLR 2022
Wainwright, M. J., Jordan, M. al. (2008). Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning. 1(1-2):1-305.
Wang, D. and Liu, Q. (2019). Nonlinear stein variational gradient descent for learning diversified mixture models. In International Conference on Machine Learning, pages 6576-6585.
Wang, D., Zeng, Z., and Liu, Q. (2018). Stein variational message passing for continuous graphical models. In International Conference on Machine Learning, pages 5206-5214.
Welling, M. (2009). Herding dynamic weights for partially observed random field models. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 599- 606. AUAI Press.
Yoon, J., Kim, T., Dia, O., Kim, S., Bengio, Y., and Ahn, S. (2018). Bayesian model-agnostic meta-learning. In Advances in Neural Information Processing Systems, pages 7332-7342.
Zhang, J., Zhang, R., Carin, L., and Chen, C. (2020). Stochastic particle-opimiization sampling and the non-asymptotic convergence theory. International Conference on Artificial Intelligence and Statistics, pages 1877-1887.
Zhuo, J., Liu, C., Shi, J., Zhu, J., Chen, N., and Zhang, B. (2017). Message passing stein variational gradient descent, arXiv preprint 171:4:171..0425.
13

---

Published as a conference paper at ICLR 2022
TABLE OF CONTENTS
Introduction
Background
2.1 Integral Probability Metric
2.2
(Deterministic) Particle Inference Algorithms
3
Connecting SVGD with MMD Minimization
4 Understanding the Pitfall of SVGD
4.1 High Variance from Integration by Parts
4.2 Bias from Deterministic Update
SVGD in the Proportional Limit
5.1
Scaling Limit and Basic Assumptions
5.2
Learning High-dimensional Gaussians
5.3
A Modification of SVGD
Related Works
7
Conclusion
A Additional Results
15
A.1 Additional Results for Section
15
A.2 Empirical Verification of (A2)
16
A.3 Additional Results for Modified SVGD
17
A.4 Discussion on Other Sampling Algorithms
18
A.5 Additional Figures for Section
19
B Derivation of Propositions in Section 4
20
Derivation of Propositions in Section 5
21
C.I Gaussian Kernel with the Median Bandwidth
22
C.2 General Kernel with Adaptive Bandwidth (Median Heuristic)
................................
24
C,3 General Kernel with Fixed Bandwidth
25
C.4 "Alsost-Gaussian" Target
26
D Experiment Setup
26
14

---

Published as a conference paper at ICLR 2022
A ADDITIONAL RESULTS
A.1 ADDITIONAL RESULTS FOR SECTION 5
We include additional figures to illustrate our analytic results in Section 5. Figure we plot the stationary variance of SVGD and MMD--escent (with the Gaussian RBF kernel and median bandwidth heuristic) under fixed dimensionality d against varying number of particles n. As shown in Figure 6(a), the particle variance of SVGD scales linearly with 1/d when > 1 (i.e., d d> 11), as predicted by Proposition 3 and Corollary 4; this again confirms the variance collapse phenomenon. When >> d, our analysis cannot predict the stationary variance accurately, but the value empirically approaches the target variance from below as y decreases.
non-asymptotic Correction for MMDD-deccent As noted in Section 5, there is small gap be- tween the empirical particle variance of MMD-descent and the prediction of Proposition 3, due to finite-particle error in the empirical simulation. To characterize this discrepancy, we now consider a regime where is fixed and d is large. In this case, we show that SVGD collapses all the particles to O, whereas MMD--escent with the Gaussian RBF kernel can still estimate the marginal variance up to ((/nn) error (see Appendix C for derivation).
Proposition 7. Consider the setting of fixed and d co, co, then given (A2)A3), particles driven by SVGD (2) collapses to zero variance: SVGG -> O, whereas MMD-descent (4) with the Gaussian RBF kernel leads to e MMD + (n- 1) 1).
Figure 6(b) demonstrates the agreement between the proposition and finite-particle behavior of MMD- descent. Observe that the umite-particlt error decays at 1/n and is independent to the dimensionality, In other words, our analysis suggests that to achieve non-trivial estimation of the target variance, SVGD requires ((d) particles, whereas for MMD-descent Oa(1) particles suffice.
Based on this observation, we speculate that to match the accuracy of MMD-descent with n particles (in terms of marginal variance). SVGD requires N nd particle. This conjecture empirically confirmed in Figure 6(C): when we increase the number of particles in SVGD by an additional factor of d, then the equilibrium variance on longer depends on the dimensionality and becomes similar to that of MMD descent with n particles. This again suggests that SVGD may not be reliable unless the number particles scale with the problem dimensionality.
2.0
1.00
1.00
0.95
0.8
predictedd
0.90
0.90
0.6
0.85
0.4
0.80
0.80
25
50
d 20 serticeo)
0.70
0.70
number of particles
number of particies
number of partides
(a) SVGD (n particles).
(b) MMDD-escent (n particles).
(c) SVGD (N nd particles).
Figure 6: Dimension- avvergged marginal variance of particles converged under (a) SVGD, (b) MMD and (c) SVGD with N = nd particles. The target is unit Gaussian, and we employ the Gaussian RBF kernel with median bandwidth. Dashed lines correspond to predicted values. (a) when d jointly scales and d > the variance of SVGD scales linearly with and 1/d as predicted by Proposition 3. (b) for small n, variance of MMD-descent approaches n increases (independent to d), which agrees with Proposition 7. (c) if the particle size of SVGD is up-scaled by a factor of d, then the underestimation of variance is of order ((1/z).
Variance Collapse in Almost-Gaussian Target. In Section 5 focus Gaussian target for precise characterization of the stationary variance. For more general target distributions, if the potential behaves "Gaussian-like" outside of certain radius (smaller than the true target variance), then under the same assumption on the fixed point particles (A3), we intuitively expect SVGD to underestimate the marginal variance when 7 = d/n is large.
Corollary 8. Given p(x) exp(-f(z)) satisfying Ep|a] Eςxx Lt. and assume exhibits Gaussian tail growth outside a Euclidean ball with radius 1, then given (Al-3), there exists 7" = d/n such that SVGD underestimates the dimension-averager variance for > 7"-
15

---

Published as a conference paper at ICLR 2022
While the proposition above only considers quadratic growth of the potential (similar to Mattingly et al. (2002)), we empirically verify that SVGD underestimates the target variance under anisotropy as well different tail growth condition. In Figure 7(a) construct the target distribution to be mixture of two Gaussians with mean 11 142 such that P1 + #2 = O. I| - /2ll2 = 1, whereas in Figure 7(b) consider factorized distribution with subic-growth potential: log p(æ) I (z(1))3/3 In both cases we observe similar variance collapse phenomenon of SVGD across different choices of kernel and bandwidth.
Log-inverse Kernel.
We also illustrate the variance collapse phenomenon of SVGD with the log- inverse kernel proposed in (Chen et al., 2018b). This heavy-tailed kernel is defined as k(x,
One can easily verify that it is Euclidean distance kernel satisfying assumption (A2), and thus we also expect variance collapse to occur in learning the unit Gaussian target (A3). This is indeed confirmed in Figure (d))(d), where we that the log-inverse kernel with both the median heuristic and fixed bandwidth (a = 1) underestimates the marginal variance, and the case of median bandwidth, can analytically predict the equilibrium variance for y > 1 via Proposition 3.
(a+ log(1 + || - x112 /0²)
2V50 1+-25
2930 (1:50
Cassrian fDr Steat IMQ mediat
Cauautan for Steat
IVD oxedent
Bsed
125
20 TV
100
100
202
(a) SVGD (cubic potential).
(b) SVGD (MoG potential).
(c) log-inverse kernel (median).
(c) log-inverss kernel
(fixed a = 1).
Figure 7: (a)(b) Empirical demonstration of variance collapsc beyond Gaussian target. (c)(d) For unit Gaussian target, SVGD with the log-inverse kernel also underestimates the marginal variance.
A.2 EMPIRICAL VERIFICATION OF (A2)
We empirically validate the near-orthogonality assumption in Section 5 in learning Gaussian targets. In particular, we plot the following quantities for particles driven by SVGD and MMD-descent till convergence (from random initialization):
d 1/2 1/2 max, 111=;112 vd]; (ii) d 1/2
d max,,; ( a,).
Note that for (A2) to hold, the above quantity should decay with the dimensionality d.
6x12
Caxio
(M))
numbor o1 poreece
Nurber pam
d' 1/2 m-x/ 1 bd}
1./2 1// {x) x d 1/2 m-1/2max, max,
[| 21 vd} (MoG target).
d max., {x) 25}
(Gaussian target).
(Gaussian target).
(MoG target).
Figure 8: Quantities of interest in Assumption (A2). We fix > 1 and vary n, d to verify the dependence d. Particles are randomly initialized from from ((, 21a) and optimized till convergence. (a)(b) unit Gaussian target with 7 = 2. (c)(d) MoG target with 7
In Figure 8 we validate this hypothesis for both SVGD and MMD-descent on two different kernels: the Gaussian RBF kernel and the IMQ kernel, and two target distributions: unit Gaussian and mixture of Gaussians (MoG). For the Gaussian RBF kernel we use the median bandwidth heuristic, and for the IMQ kernel we set the bandwidth o = Vd. The MoG model consists of two Gaussians with mean 14 24g = 0. ||p - Hzll, 1. For both algorithms initialize the particles from (/ 21a). Observe that in all cases the quantities of interest indeed decrease with d. We leave the rigorous justification of this observation future work.
16

---

Published as a conference paper at ICLR 2022
A.3 ADDITIONAL RESULTS FOR MODIFIED SVGD
In Section 5 we proposed a modification of SVGD based on derivations of learning a unit Gaussian target distribution in high dimensions (and kernels with the median bandwidth).
Damp (x:) = (at,, + S2(1),, m;)] + XSi (2:,, mx),,
j#
where À -())()) Note that À recovers the original SVGD update, whereas under extreme overparameteriiztion (p > n) we have À = f(1)/f(0) < 1 due to (A3). In addition, larger À implies smaller stationary variance of SVGD, vice versa. the figures below we refer to the SVGD update with Xmin min (1, (J(1) (0))(()) as "fully-damped", and the update with in between Amin and as "intermetidate".
Bayesian Neural Network. We now apply this modified update to the BNN setting discussed in Section 3 (for detailed setup see Section D). We initialize 100 particles from a standard normal distribution and then optimize them via (modified) SVGD with the Gaussian RBF kernel and median bandwidth for 50000 steps with learning rate 5e - 3. As shown in Figure 9, the original SVGD update (Figure (b), original) significantly underestimates the target variance (estimated using HMC), and as we decrease X, the variance of the predictions gradually increases (Figure (c), intermediate). Observe that at our proposed damping factor (Figure (d), dalleddamped), the modified update produces diverse samples similar to HMC.
model output
model output
model
modal
HMC (ground truth)
0/2
16
ff
input
input
inputx x
input
(a) HMC (ground truth).
SVGD (original).
(c) SVGD (intermediate). (d) SVGD (fully-damped.
Figure BNN experiment (y 100) for the proposed modification of SVGD (Gaussian RBF kernel). Observe that the original SVGD update (b) significantly underestimates that target variance, whereas the proposed modification (d) leads to more diverse predictions.
In real-world problems, it not likely that our proposed modification (derived for Gaussian target) always results in optimal performance. This being said, Figure 9 suggests that practitioners could tune damping term in the range [ justification of our modified update is left as future work.
and adjust the desired level of uncertainty. Theoretical
Bayesian Logistic Regression. We also conduct additional experiment of the modified (damped) SVGD update in Bayesian logistic regression problem. Given input Z {2+) E Rmxd labels J V Rm and parameter f Rd, we model the Bernoulli conditional distribution with probability Pr(s = 1|z:) 1/(1 exp z:)). We place an isotropic Gaussian prior 0; the
posterior density is given as
p(0) exp y T
Σ log(1 + exp((000 -T))))0))))))))))))))))))))))- 1 1011
Following Dalalyan (2014), we sample the coordinates of z; from Rademacher distribution and then normalize the vector by its Fuclidean norm; the labels are generated from Bernoulli distribution with true parameters l_ Lai we set 500, d 100, and the regularization parameter 1.
We report the diveneeon-averaaeed marginal variance of the particles (in the n < regime) optimized by variants of SVGD in Figure 10(b). We use the Gaussian RBF kernel with the median bandwidth, and for the "intermediate" update we set Amia = min (f(1) 2y 1 ff truth variance is estimated by Langevin Monte Carlo (see Appendix A.4 for more discussion). Figure 10(b) illustrates that for this problem, the original SVGD update (red) underestimates the target variance, similar to the Gaussian case. However, heuristic modification (fully damped,
f((1))/f(0); The ground
17

---

Published as a conference paper at ICLR 2022
0.25
SVCD loriginal)
dimention a verogeo verieno
2,0
SVCD (original)
0.20
-
SVGD ffulyy damped)
SVGD lintemediate)
Marrana vartance
1.5
Target variance
NMO (M0)
0.15
0.2
0.05
0.3
0.5
ground truth
20
40
60
80
100
20
40
60
80
100
0.0
200
400
600
800
1000
number particles
number particles
Number Ferations
(a) BLR (MMD).
(b) BLR (variance).
(c) damped SVGD (A 0).
Figure 10: (a)b) MMD (IMQ kernel) and dimension -veerged variance SVGD particles in Bayesian logistic regression experiment. Observe that the modified update (blue) leads to smaller MMD (a), but may overestimate the target variance in the small-particle regime (b). (c) Modified SVGD with À = 0 leads to diverging particles. Darker color represents larger particle size
blue) does not remove this bias completely - this not surprising because the correction term is derived only for the isotropic Gaussian target. In particular, the damped update might overestimate the cumension-averagee variance in the small-particle regime. Nevertheless, we observe that the proposed modification generates more diverse samples (with variance closer to the true value).
To further quantify the convergence of the particles, in Figure 10(a) we report the MMD between the SVGD particles and (approximate) ground-truth samples obtained from LMC; we employ the V-statistics MMD with the IMQ kernel (fixed bandwidth). Observe that the modified update (blue, green) results in smaller MMD compared to the original algorithm (red).
Complete Removal of S (z, æ;). Recall that the SVGD update can be decomposed into three terms: 1) driving force from each particle itself S1 (Z,, æ,); 2) driving force from other parti- cles Σjz; Si (ar,, 3) repulsive force Σj (2 æ.)) (note that (2,;, = 0). Specifically, Si (wy, x.) has large impact on the update and the variance collapse: in the modification above, we are able to generate diverse samples just by decreasing the strength of this single term.
One might speculate that instead of using the specific À derived for Gaussian target, an easier alternative would be to completely remove (Ix 22),, i.e. setting X = 0. This is however not the case. Following the same derivation as Appendix C, one can see that when X = O, Equation 13 does not equilibriate at any finite variance for > 1. We empirically validate this finding in Figure 10(c), where we fix d = 50 and vary the particle size n from 25 to 500, and optimize the particle using (modified) SVGD with the Gaussian RBF kernel and the median bandwidth. Observe that while the original SVGD (red) underestimates the target variance, setting X = 0 (blue) leads to significant overestimation
divergence when d >
One minor remark is that heuristically speaking, SVGD with = roughly resembles MMD-descent with fixed log derivative S₁ (see Figure 2(b) in Section 4), due to the presence of deterministic bias, and that the driving force in both updates involves the log derivative S1, but does not include the "self" term Sn (a., a.:). As result, we observe overestimation of marginal variance (or diverging particles) in both modified updates.
A.4 DISCUSSION ON OTHER SAMPLING ALGORITHMS
In addition to SVGD and MMD-descent, there are many other approaches to draw (approximate) samples from given target distribution. We briefly discuss two popular methods: Langevin Monte Carlo (LMC) and Herding. In particular, show that LMC does not suffer from variance collapse high dimensions; in fact, under some conditions, one particle suffices to estimate the dimension- averaged variance of the target.
Langevin Algorithm. Langevin Monte Carlo (LMC) is a time discretization of the Langevin diffusion, which can be interpreted as the (Wasserstein) gradient flow of relative entropy (Jordan et al., 1998). Convergence rate of the discrete-tima algorithm has been analyzed under various metrics (Dalalyan, 2014; Durmus and Moulines, 2017; Erdogdu et al., 2021) and assumptions on the target distribution (Vempala and Wibisono, 2019; Erdogdu and Hosseinzadeh, 2020).
18

---

Published as a conference paper at ICLR 2022
Here we provide short sketch that existing quantitative convergence guarantee of LMC impliee that the algorithm does not underestimate the dimension-averaged variance. For strongly convex and smooth potentials (which includes the Gaussian setting in Section 5), Erdogdu et al. (2021, Theorem 4) showed that when the strong convexity parameter is dimension-free, then under appropriate choice of step size, running LMC for T = (dd) iterations leads to (2rlllpp) = (1). We denote the covariance Ex *I = Σ, and assume E [x] 0, Tr(2) d WLOG. By properties of the x" --vveegeence and strongly log-coneave concentration. given sample a drawn from Qr.
Pr (1 || E ||ا|||| 1) x exp (xp(-1t) (-t))
This concentration directly implies that in the high-ding -igh-dimensional limit d + oo (Assumption 1), have || 1l Tr(E) 2 In other words, the dimension averaged variance Tr<E)/4 /d can be reliably estimated using one single particle driven by LMC for (dd) steps. We remark that similar results are expected to hold true under more general conditions such as the log-Sobolev inequality on the target distribution, as well as other variants of the algorithm (Roberts and Tweedie, 1996; Cheng al., 2018b). We therefore speculate that variance collapse is a unique property of certain interacting particle algorithms such as SVGD.
aaaeeniio-avvraaed
Kernel Herding. Consider the approximation of an intractable distribution p(æ) with a set of particles X = {z,)_=1- To generate these particles, the kernel herding algorithm introduced by Welling (2009) to minimize the MMD between the particles and the target distribution. The algorithm proceeds in a greedy manner: given the current set of selected particles {x1,"'. In-1), the next particle is chosen based on the following:
Σ Sm, + 5z 820) ))
Ztp +- argmin MMD?
=argmax argmax Eyrp (k(a,, y)] - Σ k( a.)..
p. n
x
Intuitively, the first term encourages sampling in high density areas for the target, whereas the second term discourages drawing samples close existing ones. It has been shown that the kernel herding algorithm reduces the MMD at a rate O 1 ) for mitte-dimensionl Hilbert spaces H. (Welling, 2009; N
Bach et al., 2012; Huszár and Duvenaud, 2012).
Note that the same procedure can also be used to greedily minimize the kernel Stein discrepancy (Chen et al., 201 8b; 2019). In addition, the non-greedy gradient descent update KSD (analogous to MMDDdescent) has been recently analyzed (Korba et al., 2021). We leave the high-dimensional characterization of these algorithms future work.
A.5 ADDITIONAL FIGURES FOR SECTION 4
In Section 4 we conducted experiments that qualitatively identified the cause of variance collapse, primarily for the Gaussian RBF kernel. Here we reproduce these findings for the IMQ kernel:
k(x, y) 1/v V 1+ | yll2 2202), which is also commonly-used in SVGD, As shown in Figure 11, results are qualitatively similar to that of Gaussian RBF kernel.
log MSE to true value
55.0
Marghaa varange
-7.5
variance
0.8
(oniinaa))
-10.0
log faative 5,
1.0
0.6
SVGD (resampled
SVGD (nwwmpped 5,1
target variance
-1.55
0.5
target
log derivative (fwed) kemel dericative ctsedt
-550
200
40D
600
800 1000
1000
2000 3000 4000 5000
20
40
60
80
100
number of particles
number of iterations
Dimonsiooaaily (d)
(a) MSE in estimating S₁ and S2 (IMQ).
(b) MMD-descent (IMQ).
(b) Resampled SVGD (IMQ).
Figure 11: Learning an isotropic Gaussian using the IMQ kernel. (a) Integration by parts with the IMQ kernel leads to large discrepancy in the variance of S and Sz. (b) MMD with IMQ kemel leads to divergence under A MMD (log derivative) with fixed target samples. (c) IMQ-VVGD with resampled S; (blue) correctly estimates the target variance, but redrawing S2 (green) fails to provide more accurate samples.
19

---

Published as a conference paper at ICLR 2022
Finally, we provide additional empirical evidence that SVGD with proper resampling procedure (see algorithm 1) reliably es- timates the target variance. We consider the cubic-growth poten-
0.8
vartance manaa
SVGD (origina))
tial: p(z) x exp (- (z()))3)) and optimize the particles using SVGD with the Gaussian RBF kernel (fixed bandwidth Vd). As shown in Figure 12, the original SVGD update (red) underestimates the dimension-averaged marginal variance inversely proportional to the problem dimensionality; in contrast, when S1 is resampled (blue), then the estimated variance is stable as d increases.
SVGD (resampled
(resampled Sx)
0.2
Dimensionaiity (d)
Figure 12: Resampled SVGD in learning the cubic-growth potential defined in Appendix A.
B DERIVATION OF PROPOSITIONS IN SECTION 4
Proof of Proposition 2. For simplicity we first assume the target is zero-centerede y ~N(0, Ia). In this case when the kernel is Gaussian RBF, the expectation of Si, which we denote as Max has the following closed-form: Pa= = (1+02)1/2-1 exp of interest follow:
24200
|| æ. We compute the mean squared error
[SEp[S x]]
|| x) - pellppy)dd
yk(x, 3) M 113 p(y)dy
/ k22 k (a. y)
Th y ply)dy 22 / k(E, y)y + Popo ply)dy
y
c 1ml13
1-13 x 2d
2e
2d
(2||z) 12 + do?)
||
(2 + 22) 02)d/2+1
(1 + o 22)d42
(1 + 02)d42
1=13
lel
x
2e
21
0²
4/2
11
0²
d
de
|
0² 2 0²
d/2+1
02
+ 02
(o2 1)
1 0²
Similarly, for the kernel derivative 82 we have,
[SE,((22(,, m]
[|82(y, x) - (1mm))13(()dd x y k( y) + Mz 12 r()dd
2x
2p
J k(x, ply
(2,,)) ypl
k2
o²
y
y
+ x" TT
x / 12 (( +
2x T Um
/
/
+ T
p(y)dy
y
1mm1
lmmi3
lim1
2402 gd-4
4e 200 gdd
2e 1+o 2d-2
(2 + 02)d/221 (2|x0 + do2)
[20| +
||0||
(2 + o. /d/2+1
(1 + o² d+2
|
1
2e 1 2d-2
IT 2d
+
(2 + 2 2224/2+11
(2 + |||||
(1 02 d+1
x
2 +
(1 (1+o2dd-zl
||
|
2+20
0²
d/2+1 1
(d + |
3
1+
d
|
2 2+
(1+ (1+
1
20

---

Published as a conference paper at ICLR 2022
The simplification above largely follows from Nv,,Nu, ~ (a,, Ia). note that replacing ||ح| with ||æ all does not affect the order dependence on d as long as ||a|| (dd), and therefore the order that we aim to estimate remains the same.
u Tr(E). For non-centered
Given the bandwidth heuristic a @(vd) and || d. can easily verify that:
(SE =)] E ((d=)) MSE,[Si (y. m)] E (d).
To extend the result to general Euclidean distance kernel k(0, y) x 1 concave distributions satisfying | | 11 O(d) and Br()) |Il = (d), first note that
and strong log-
2n
By~ppll [| = Byrpl |I V (y
2 y
yl1
2
02
2g
2
C20
E Eyup
||
u1l Oat
where (i) is by Cauchy-Sehie Sauchy-Schwarz and the Lipschitzity of f. Similarly, following the expansion of MSE, [22] and the assumptions that k is upper-bounded one can verify that MSEp|SS(y, x)] = O(1).
Finally, we lower-bound the variance of S1 via the following calculation,
E Eynp [15 x)
Me 12]
Eyru
[1V log p(y)11 k²xx,)) (<<,)) v)] |1
Ci Ey-p
|1u1
22: y) - || l12
- C2Ey-N(o.n)
|101
1mm-113
|
(1t) s2dd)
where (i) is by the strongly log-concavity of p and the fact that the kernel being lower-bounded by scaled Gaussian RBF kernel, and (ii) directly follows from result the Gaussian case. Combining the calculations yields the desired statement.
C DERIVATION OF PROPOSITIONS IN SECTION 5
In this section aim calculate the equilibrium variance of SVGD and MMD-Descent under the proportional asymptotics. We first restate and comment on the Assumptions in Section 5.
(A2) Near-orthogonality. Particles at fixed point of SVGD (or MMDD-deccent) ao x;; dul < UCd, | æz5 < vca for all + j. some v > 0, and d d - 0 as > oc with probability
satisfy
(A4) Gaussian Target. p(x) & exp (-1 zz)
is to draw samples from a unit Gaussian distribution, Under (A4) the goal of SVGD or -vveraged variance of the particles evolved by the two and we aim calculate the dimension updates. Note that since both SVGD and MMD--descet form interacting particle system, one can no longer treat the converged particles as i.i.d Gaussian samples, i.e. æ; NO, v7). This significantly complicates the analysis in the proportional limit.
However, empirical results (see Figure 8) demonstrate that starting from non-degenerate random initialization, the equilibrium solution of both algorithms admits thin-shell concentration around the radius. i... the norm of concentrates around vdv. and particles are almost orthogonal one another. This observation is captured by (A2). We conjecture that such property holds for the updates consider due to the repulsive force pushing the particles away from another, and thus leading to this near- orthogonal configuration.
Under assumptions (A2)(44), MMD-descent in the asymptotic limit. We first provide a detailed derivation for the case of Gaussian RBF kemel, and then extend the analysis more general settings.
able to compute the stationary variance of both SVGD and
21

---

Published as a conference paper at ICLR 2022
C.I GAUSSIAN KERNEL WITH THE MEDIAN BANDWIDTH
Stationary Variance of SVGD in Proportional Limit. We aim to solve the stationary point of
SVGD update (2). Under (A2) and the median heuristic condition for the Gaussian RBF kernel is given
Med æ, / the fixed point
A (
k(w,, x4 + du
k(x, (x)xx - -xx) = 0,
(6)
71
for all k, equivalently
Σ (z x2k xx) du +
Σ k(z,, xk) Dk.
(7)
Note that for the left hand side of (7), have the following equivalence,
LHS = Σ k(,,, ax) = X Xkss
where X = [21,... nn E Rdxx is the data matrix, ky = [k(11. Ix).... k(x,, TT) E R is the k--th column of kernel Gram matrix K Rax", As for the RHS of Equation (7), note that for i A k, (A2) allows us to take the following Taylor expansion on entries of the kernel matrix around its concentrated value, i.e.,
||:; x
k k( (K) = exp
= +0t).
2dv
Where dd//2 0. Similarly for = lt we have k( xxx) 1. Combining the equations above,
n n e + +(e)
RHS du +1 k( mt.)
(dv 1)e
Equating the RHS and LHS of Eq (7) in matrix form (over all k) we have
X K n n+e-ly + X diag(e).
(dv l)e
where diag(E) is squared matrix where the i-th diagonal element is the error from Taylor expansion 6 = Oc). Define
n n+c m du +
The fixed point of SVGD thus simplifies to
X (K mI, - diag(E)) =
Denote A K mln diag(e), Recall that the K is an Euclidean kernel matrix with Kij k(æ,, æx) exp (((ddu) ||æ0 æ* 2l) From Theorem 4 in Bordenave et al. (2013), it follows that the empirical spectrum of A, which we write ((A) n - -i dx(())) converges weakly to the following quantity.
2 m(A) 11- m
1 1 x + p(diag(e)),
-
e
du
In addition, define S nn/nn- 1)4m 1/(n 1)1,, I, then by the Hoffman- Hoffman-Wiclandt inequality (see Bordenave et al. (2013, Lemma 6)) we have
(1xxxx) xTx))
.((S)) xxTx))((s)
1
-Vn-I.(nO(e) 0. X
-S) 2
W2 1
V
du
do
22

---

Published as a conference paper at ICLR 2022
where we used (A2), and (2( () is the 2- Wasserstein distance. Hence, we know that
m(A) +
m
+
1 e
xxxx)
x) + u(diag(e))
e
du
1
+ m
+
μ (5) + u(diag(e)).
(9)
When y (i.e. d > n., Equation (8) requires (u()) 0. Consequently,
1 e(n ((n-1) m
m-1-e"
Therefore, from the definition of m we have the desired result.
1 1
5VGD
(10)
d(e
--11 1
Stationary Variance of MMD-descent Proportional Limit. First note that for the Gaussian RBF kernel, the driving force of MMD-descent (4) admits the following closed-form,
||011
Ey--pS22yy, x)]
(1 + o2)d/241 exp
x.
2 + 2o
This can be verified via simple numerical calculation:
ply)k(x y) log p(y dy
/
e
20
dy
(2
Vie02
ye
20
2420 dy
V(2 da
2+202 C.
+ 22)d/2+1*
Therefore, the stationary point of
satisfies
Az
ad (1 + 02)0/2+1
212
xb +
1
Σ
k( (x) xzi) = 0,
no²
itf
yk, or equivalently,
du
d/2+1
|
Σ k (eek,a:)arr æ:)
21200
nark
Σ k( az, )a
+ du
Under assumptions (A2)(A3), similar to the SVGD case, we have the matrix form the fixed point,
1 1te I 1)- (1- du du
d/2+1
24205
X + Xdiag(e) XK.
with o(1). Following an anlogous calculation, as n, + oo with d/n = 7 E (1, oc) we obtain,
1+e-t(n - 1)- du
d/2+1
e 2122
+
(11)
du
Moreover, observe that lim (dv/(1 + du))
d/2+1 du))
1/(2o) We arrive at the desired result,
MND + 1.
Following the exact same reasoning, one can show that for fixed bandwidth o = cy for some constant ((1), MMD--escent also estimates the variance correctly, i.e., MMD 1.
23

---

Published as a conference paper at ICLR 2022
SVGD and MMD-descent with Finite and Large d. From (A2) we have the following decom- position for + J.
2n
c 2 11 = |x + ||0; 2x, x; = 2dv + 2(n 1)- do + 0(e)
do + O(de).
π1 1
For finite n, this indicates that the Euclidean distance between two particles concentrates around 2(n (---] ndd (instead of 2dv); this is say, the Gaussian RBF kernel admits the the following Taylor expansion for + j.
|| - = = n- +.(c).
k< 23) = exp
2dv
Therefore, for the MMD-descent algorithm, (11) reduces to
de
d/2+1
1+e (n
de
Hence the converged particles of MMD-descent with finite n and infinite d has variance
MMD
π
And for SVGD, one can use the exact same argument to obtain that
SVGD O.
Note that this result agrees with our characterization in the proportional asymptotic limit by taking 7 2o (i.e., d >> n2).
C.2 GENERAL KERNEL WITH ADAPTIVE BANDWIDTH (MEDIAN HEURISTIC)
vil 2n
Recall the definition of the (bandwidth- (bandwidth-adjustte)) Euclidean distance kernel: k( y)
Under (A2) and the median heuristic σ be equivalently written as k( yy) following fixed point condition.
V Med x; x, ||///,,, we know that the kernel can
v11
Following the same procedure, we have the
2de
(mxx) = Σ
x B&
- 9'
<2. 3e 11
(aos - 2::)
= 0.
(12)
2dv
du
2dv
for all k, equivalently
[ xx11
| xxl12
|20,
xxl1
x
f
2kk-
2dv
do
2dv
du
2dv
Similar the previous calculation on the Gaussian RBF kernel, applying (A2) and the differentiability of f around 1, we Taylor-expand the kernel and obtain the following equivalence:
1 _')= f(0) (n (1) do
X (K
X diag(E).
du
where K is the Gram matrix of the kernel k, K' is the Gram matrix of its derivative with Ky f' [ ) Apply Theorem 4 of Bordenave et al. (2013) to K and K', we have the following relation under (A1)(A2),
2do
f(0) f(1) - (f(0) f(0) + (n 1)f(
(13)
du
du
which gives the expression of the equilibrium variance.
f(1
y
SVGD
f(1)-f(0)
24

---

Published as a conference paper at ICLR 2022
Heuristic Derivation of the Modified (Damped) Update. We provide brief sketch of the modi- fied algorithm in Section for the median bandwidth. Recall that our proposed update introduces damping tern Af (0) in the driving force Sr. To derive the optimal À for unit Gaussian target, we incorporate this damping term into the fixed point Equation (12), which leads to the following modification of Equation (13):
f(0) - f() 1 - - f()))
= (1 1)5(0) f(0) + (n - (1)
dc
du
Recall the true target variance 1; this gives following choice of A:
A -=((0)-((((()
(f(1)
(14)
Since our goal is to "weaken" the driving force SJ (Z): axx), we take the minimum between the derived value in (14) and the default X
C.3 GENERAL KERNEL WITH FIXED BANDWIDTH
We now consider Euclidean distance kernel with invariant (fixed) bandwidth that scales with the dimensionality d, which write as k(æ, y) f(1l 3112 /2d). Following (12), we have the following equilibrium condition for the particles,
f (1E 2x112 22112/2d 5 (I::;- - 2x112 /2d) x, =
f (Iz: Σ 1=1
x2112 /2d ok.
Under Taylor expansion around the fixed point condition entails that the stationary variance satisfies,
f(0) f(v) d (5(00 ( f'())
(110)
(n
f'(v) f(v) - f(0) = 7
(15)
Note that given (A3) and monotone I', the numerator of the RHS of (15) takes a negative value that increases with v, whereas the denominator is also negative but decreases with This implies that when 7 becomes larger, needs to decay towards order to satisfy the equation.
For the Gaussian RBF kernel with fixed bandwidth = Vd, the equation can be easily solved as,
1 7
RBF
loog
1 +
< 1,
which is decreasing function of y > 1.
On the other hand, for the IMQ kernel with fixed bandwidth Vd, standard calculation yields,
47(7 + 3)
IMQ
(374 + 27) 8,6 + 16,55 3 +2774) 1/3
0//1/3(8) + 27) 88 - 36y + 27 1/3
2
72
One can numerically verify that the value less than for 7 and also non-increasing.
IMQ Kernel with Dimension-inndeeedeer Bandwidth. Finally, note that in the context of kernel Stein discrepancy (KSD), the IMQ kernel is often employed without the dimension- dependent bandwidth (Gorham and Mackey, 2017). In this
write the kernel as k(æ y) f[[x v12 /2), which gives the following stationary condition,
Σ f (| 221l2/2) (Iæ; 1x212/2) x; = Σ f (1 - xxx12 ac.-
1=1
25

---

Published as a conference paper at ICLR 2022
Taking Taylor expansion around de gives
f(0) - f(vd) - (0) f(dd) - (n (m))))(m Note that the LHS (1) by (A2); order for the inequality to hold asymptotically, we need to have (vvv = (n !). On the other hand, for the fixed- bandwihhd IMQ kernel,
f(a) = (1 + a)-1/2 2f -(1 + +a)
This implies that as d increases, the stationary variance decays to 0 at rate of v = ((d-1/3). Following the exact same procedure, one can show that the log-inverse kernel with fixed dimension- independent bandwidth also asymptotically collapses the variance of SVGD particles to when
y > 1; we omit the derivation.
C.4 "ALMOST-GAUSSIAN" TARGET
For general p(z) x exp(-f(x)), the fixed point equation of æy is given as,
1 Σ
x z 1
1 2
x 1
(axx)
ff(x;)
(ax
xz,) 0.
n1
20
0²
20
Assume that SVGD does not underestimate that marginal variance, then by (A2) and the quadratic growth, we know that there exists some >> 0 such that for every particle 24 and coordinate [d].
Σ af
x =xx11
1 f
| x
Σ
n
26 12
I
20
20
20
For kernels with the median bandwidth, followings the same simplification as in (13), we get
aKK (aK
1 ! (K) f(0) (n 11)
X
- diag(c).
do
du
Solving the inequality yields,
f'(1)
f(1--(0)
Therefore, given any dimension-indee indeppendent growth of the potential there exists a large enough y such that < 1, i.e. SVGD underestimates the marginal variance. The case for fixed bandwidth follows from the same line of reasoning, the details of which omit.
D EXPERIMENT SETUP
Bayesian Neural Network. We consider BNN with two hidden layers of 100 units. In each layer, the preactivations S141 are computed via S14-1 = (W,a, + b,) /h, + 1, where a, E IR are the input activations. The target function is BNN with the same architecture, whose weights and biases are randomly generated from standard normal distributions. For the training set, we sampled 10 input locations uniformly from 2-2.5, -1.5] and [1.5, 2.5), respectively. We add random noises to the observations, = f(x) + e, ~ (0,0, 0.01).
We first adopt the Hamiltonian Monte Carlo (HMC) (Neal et al., 2011) generate asymptotic posterior samples. HMC used 50 independent chains and each chain selected 50 particles with the frequency of 100 iterations after 5k burn-in iterations. HMC generates diverse particles as shown in Figure ((a). We then simulate SVGD and MMD-descent dynamics on this problem. For both updates we use the Gaussian RBF kernel with the median bandwidth heuristic. For SVGD, we evolve 100 particles for 50k iterations using learning rate 7) 5e 3, whereas for MMD-descem we evolve 10 particles using HMC particles as approximate target samples to compute the driving force term. The particles either initialized from the (approximate) target distribution (as in Figure 1), or from standard normal distribution (as in Figure 9). Note that the plots do not include observation variance.
Hyperparameter Setting in Section 5. For all experiments in Section 5, we initialize the particles from (O, 0.8I,), and rum SVGD (or MMD-descent) with learning rate = 10- for 20k iterations. For experiments in the proportional limit (Figure 4(a)(b)), fix 50 and vary d. For the median heuristic (following Garreau et al. (2017)). we compute the median of Euclidean distance between all particles each iteration.
26


Reviews:
[{"review_id": "njLNB1ud_pe", "reviewer": "Reviewer_du4P", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "# Pros\n- The paper is well written and easy to follow.\n- There is a complete set of experiments to support the authors' argument.\n- Theory in simplified settings is provided to justify the understanding. \n\n# Cons\n- The presented theory is a bit unsatisfactory in the sense that (1) the target data distribution is too simplified and (2) the proposional assumption ($d/n \\to \\gamma > 1$) weakens the theory for explaining the experimental results. In specific:\n   *  Based on my understanding of the proof (note that I did not look in detail), (1) greatly simplifies the argument in that the studied problem is basically 1-dimensional. I believe the theory could be much more interesting if (1) can be relaxed to allow general PSD matrix as the covariance of the target distribution.\n   * When I went through the paper, which is enjoyable process, I did not realize the necessity of  (2) until Section 5. In particular, the experimental observation, e.g., Figs 1 and 2, does not seem to satisfy (2), and in these experiments the variance collapse issue still exists in SVGD. It feels like (2) is invented only for the purpose of making up a theory. \n\n", "summary_of_the_paper": "This work studies the variance collapse phenomenon of SVGD. By comparing to MMD-descend, the authors argue that the driving force of SVGD suffers from a bias caused by reusing data, and thus tends to underestimate the variance of the target distribution. Theory are developed in the setting of estimating standard Gaussian with a proposal limit (i.e., $d/n \\to \\gamma$), and explains the understanding in the overparameterized/high-dim setting (i.e., $\\gamma > 1$). Experiments are also conducted to verify the understanding. Finally, motivated by the understanding, new algorithm is proposed to fix the issue of SVGD by damping the driving force term in SVGD.", "summary_of_the_review": "First of all I am not an expert on SVGD thus I tend to be conservative in evaluating the paper. \nOverall I think the paper is written very well & I have enjoyed much going through it. The problem studied in the paper, the variance collapse of SVGD, seems to be important and interesting in my perspective. I think the authors have made sharp observation towards understanding this issue & how to mitigate it. The main pitfall of this work, in my perspective, is the theory part; as explained above, I think the presented theory has quite some gaps from the experimental findings. \n\nI am leaning to weak acceptance for now. Authors feedbacks are welcome as I may have missed some important points.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JjU9VLqM2iu", "reviewer": "Reviewer_PPJd", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "## Strength\nThis paper attempts to analyze one important problem of SVGD. Although this phenomenon has been identified in many previous works, this paper is the first one that theoretically quantifies the converged variance beyond the mean-field assumption. Qualitatively, the connection between MMD-descent and SVGD is intuitive (although I am still a bit confused about why introducing MMD-descent is necessary). Personally, I believe the theoretical analysis under the proportion limit is a significant contribution to the community, which is much closer to the actual empirical behaviour than the typical mean-field assumption. However, I still have several confusions.\n\n## Weakness\nMy first question is why the connection between MMD-descent and SVGD is necessary? I understand that they share identical repulsive forces and similar driving forces, but they are still different. Thus, any finding from analyzing MMD-descent cannot be directly transferred to SVGD, no? For example, in section 4.1, proposition 2 revealed the large variance of the driving force in MMD-descent. However, you only analyze its effect on MMD-descent, not SVGD. Specifically, whether the driving force in SVGD has a large variance or its empirical effects are not analyzed. So what is the purpose of introducing MMD-descent and analyzing the large variance of the driving force?\n\nProposition 2 only confirms that the driving force in MMD-descent has a large variance. Is it still true for SVGD?\n\nI also find that Section 4 and 5 are a bit disconnected. In Section 4, the argument is that the variance collapse problem is due to the deterministic bias of the driving force, which is confirmed empirically. However, the theoretical analysis in section 5 does not reveal why this bias causes the variance collapse problem. Also, I recommend that the author should add a sentence explaining where the deterministic bias assumption is used in the analysis. \n\nIf I understand correctly, the entire analysis is based on the Euclidean distance kernel assumption. However, there are many types of kernels. Do they still suffer from the variance collapse problem? In other words, do you think the variance collapse problem is due to the SVGD itself or the kernel associated with it?\n\nFor the empirical verification of (A2), how do you select $\\epsilon_d$? \n", "summary_of_the_paper": "This paper analyzed the curse-of-dimensionality problem of the vanilla SVGD with Euclidean distance kernel in a qualitative and quantitative way. Specifically, the author first built a connection of SVGD to MMD-descent, where they share identical repulsive forces with different driving forces (if Euclidean distance kernel is adopted). Then, the author argued that the variance collapse problem is rooted in (1) high variance and (2) the deterministic bias of the driving force, which were confirmed by sampling from the isotropic Gaussian. Quantitatively, the author analyzed the stationary variance of MMD-descent and SVGD with isotropic Gaussian under the proportional limit, which confirms the curse-of-dimensionality problem of SVGD. ", "summary_of_the_review": "Overall, this paper is written clearly and easy to follow. It also has significant theoretical contributions about the SVGD dynamics under the proportion limit. Although I am a little confused about the motivation of introducing MMD-descent, this paper has more merits than its drawbacks.  ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JIwVx1aMufK", "reviewer": "Reviewer_SH8F", "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": "Strengths:\n1. It is a good paper to analyze the limit and weaknesses of SVGD, especially the variance collapse issue on high-dimensional distributions. It is worth reading for the researchers working on Bayesian inference.\n2. The proposed MMD-descent motivates some modifications to the original SVGD.\n3. The experiments on toy datasets perfectly validate the claims of this paper.\n\nWeaknesses:\n1. Only toy datasets are used to validate the proposed approach. I would like to see a more practical experiment. E.g., in the original SVGD paper, Bayesian logistic regression and Bayesian Neural nets (BNN) on practical datasets are discussed. I would like to know on real scenario any advantage could be found with the proposed method.", "summary_of_the_paper": "In this paper, the authors analyze the underestimation issue of stein variational gradient descent (SVGD), and propose the maximum mean discrepancy (MMD) descent. From the perspective of the decomposition of the gradient term (driving force and repulsive force), this paper suggested to use another driving force term instead of the original one in SVGD. But the new driving force makes MMD-descent impractical since it depends on an intractable integral of the desired distribution $p$. In addition, the paper identify the log derivative driving force as the problematic term in SVGD, and propose a modified SVGD with particle resampling. They also argue that the proportional asymptotic limit is more relevant to understanding the variance collapse phenomenon. The theoretical dimensional analysis of SVGD on Gaussian also suggested another modified (damped) SVGD.", "summary_of_the_review": "Overall, this is a good paper with solid analysis. It should be of interest to the area of Bayesian inference. But I think more practical validation should be addressed.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "59OjK2PANdO", "reviewer": "Reviewer_r5Ry", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "I really enjoyed the paper and learned a lot from it. I was not familiar with this issue, but I appreciated the dedication and the in-depth study: it is rare to see a paper dedicated to \"understanding\" these days. All my congrats to the authors also for the nice writing and the nice figures.\n\nMy acceptance is only \"weak\" though since I would have loved to see the following:\n\n1) a more thorough investigation of the \"fixed SVGD\": this only takes a page, and though some additional results are presented in the appendix I feel it deserves more space, or potentially also a few weeks of \"rethinking\" by the authors. Do you maybe have some ideas on how to make this section more complete? For instance, it would be great if the authors were able to show how damping provably fixes variance collapse in the high-dim Gaussian case. Examples are often underrated, yet these specified proofs often highlight nice ideas and concepts.\n\n2) I feel that the method under investigation is only SVGD, yet many other methods exist to estimate probability densities. I think the paper would really profit from a comparison with other methods, just to set the right context.\n\nAll the rest is really good, though it maybe can be shortened a bit to leave space to more experimental results or more results (potentially a consistency theorem) for damped SVGD. ", "summary_of_the_paper": "This paper provides an understanding of the variance collapse phenomenon of SVGD. The paper first (1) introduces the reader to the most important concepts and phenomena, then (2) gives an explanation for why this problem occurs, thanks to a comparison with an accurate (yet computationally intensive) algorithm they call MMD-descent. Finally (3) the paper shows how to fix SVGD with damping. The paper provides experiments and theory, nicely combined.", "summary_of_the_review": "A great paper, well written. The topic is nice. Some things can be improved (taken a step forward) to make the paper truly valuable also for practical uses.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes new analysis on Variance Collapse of SVGD in High Dimensions. The analysis provides some new insights despite of some limitations.
Decision: Accept (Poster)