Improved Finite-Particle Convergence Rates for Stein Variational Gradient Descent

Thank you for your thoughtful questions and your positive evaluation. We have added a notation section for easier reference to commonly used symbols.

Why do you integrate it from $0$ to $N$?

The first two bounds in Thm 1 apply to any $N$ and $T$. From those bounds, one can obtain rates for general $N$ and $T$. However, for the KSD to converge to zero, one needs both $N$ and $T$ to jointly go to infinity. If you assume $C^*< \infty$ and $\limsup_{N \rightarrow \infty} KL (p^N(0) ||\pi^{\otimes N})/N < \infty$, then one obtains a KSD bound of $O(\frac{1}{N} + \frac{1}{T})$. Thus, taking $T=N$ gives the optimal decay rate in this upper bound.

What is $\mathcal{L}$ in Assumption 4?

$\mathcal{L}(X)$ denotes the law of the random variable $X$. We have stated this explicitly in the `Notation' section.

Growth condition in Assumption 2

As discussed in Remark 3, the growth condition essentially interpolates between the exponential and Gaussian target distribution tail behaviors as $\alpha$ varies from $0$ to $1/2$, and does not impose any convexity on the potential $V$.

For analyzing discrete-time MCMC sampling algorithms, $V$ is typically assumed to be gradient-Lipschitz. Our growth condition required for Theorem 3 (which is focussed on the discrete-time case) is comparable to such smoothness assumptions, whereas Theorem 1 (for the continuous time case) does not require such a growth condition.

Functional inequalities (like log Sobolev and Poincare inequalities) are curvature or convexity-type conditions that are used in particular to obtain guarantees in the stronger Renyi and KL divergences for MCMC algorithms. One of the significant contributions of this work is that for the KSD results, we do not assume any convexity or functional inequality and thus our results are applicable to a wide range of potentials and kernels.

However, as also pointed out by Reviewer xwur, even for the population limit SVGD (infinite particle limit), obtaining KL guarantees is an interesting and open problem. Note that existing results require the Stein log Sobolev inequality which is not as well-understood as their classical counterparts.

Table for comparison

Since there is only one prior work (Shi and Mackey, 2024) on analyzing discrete-time finite-particle SVGD, such a table will not be too meaningful in our opinion. If you still insist on adding a table, we will be happy to oblige in the camera-ready version.

Smoothness constant in Theorem 3

Good point. Actually all the constants appearing in Assumption 2 are important in quantifying the convergence rates. However, the bounds would become quite clunky and hard to parse if we made all such dependence explicit. That is why we chose to only distill out the effect of the most important parameters $d$ and $N$ in the bounds.

Wasserstein, KSD and CoD

We have added a discussion in Remark 6 providing an intuitive understanding of this phenomenon. Convergence in KSD captures convergence of expectations for a class of test functions that is much smaller than that for Wasserstein convergence (see Gorham and Mackey, 2017 and Kanagawa et al., 2022). The latter class is large enough to be highly sensitive to the effect of growing dimension, thereby exhibiting the curse-of-dimensionality.

In principle, Theorem 3.2 from Kanagawa et al., 2024, could be used to get a Wasserstein bound based on KSD bound. However, Theorem 3.2 is extremely abstract and hence we work with the Matern kernel for obtaining tangible rates. A practical comparison of the different choices of kernels for SVGD algorithms, although interesting, is beyond the scope of this current work.

Gaussian mixing time

Definitely not, especially when sampling from Gaussian targets. However, we give the first poly-time complexity order for a deterministic sampling algorithm for non-parametric targets with minimal assumptions on the $V$ and $k$. For Gaussian targets and bi-linear kernels, with Gaussian initialization, Liu et al., 2024, provides more detailed results on convergence rates exploiting the parametric form (by tracking the flow of means and covariances) in comparison to the whole empirical distributions in the non-parametric case.

Improving the rates of SVGD or other deterministic particle methods or proving lower bounds for such methods provides a clearer understanding of deterministic and randomized sampling. The eventual goal is to mark the territories where deterministic or randomized sampling algorithms perform better.

We sincerely hope that we have addressed many of your questions, in which case, we would greatly appreciate if you could increase your score as you see fit.

Thank you for your thoughtful review and positive feedback on our paper.

N-fold product target measure

Thanks for this suggestion, we have now added this definition in the notation section.

Matérn-family of kernels and Computational Clarity

In principle, one can use Theorem 3.2 from Kanagawa et al., 2024, to obtain a Wasserstein-$q$ bound based on KSD bound. However, as can be seen from the presentation of this theorem, such a result will be extremely abstract. This is a main reason why we work with the Matern kernel for obtaining tangible rates. We have reworded the discussion in the draft now to reflect our choice more accurately (see page 9).

Thank you for your meticulous reading of the paper, insightful questions and positive evaluations. We have fixed the typos in the revision.

Derivations starting from line 281

Please see the updated derivation in page 6. In particular, the first term vanishes due to the regularity of the density shown in Lemma 1 and by the fact that derivative of constant is zero.

In order to obtain (17)

Good question. Note that under our assumption, we have $f(n)^{2\alpha} \leq 1+ f(n)$ and hence the claim holds as we have set $D_3 = D_1 + D_2$.

line 927: Routine computations

Thanks for the suggestion. We have now added the skipped steps.

Notation: $P(x_1(t) \in dx)$

We have defined this notation formally in the notation section in page 4.

Superscript $N$

We have followed the convention that in the statements, we use the superscript. While in the proof we drop it for notation convenience (and as it is clear from the context). We have also added this explicitly in the notation section in page 4.

Initial distribution

The condition $\underset{N \to \infty}{\limsup}~\text{KL} (p^N(0) ||\pi^{\otimes N})/N < \infty$ holds, for example, if we set the law of $\underline{x}^N(0) = (x^N_1(0), \dots, x^N_N(0))$ to be $\mu_{\circ}^{\otimes N}$, where $\mu_{\circ}$ is any probability measure on $\mathbb{R}^d$ satisfying $\text{KL}(\mu_{\circ} || \pi)< \infty$. We have added this as part of Remark 1.

Avoiding averaging completely

As the particle dynamics are deterministic given the initial locations, the time-averaging creates the necessary `smoothing' in the absence of additional noise to enable us to prove such a result. It is a great (and open) question whether such POC results hold at the last-iterate level.

Thank you for your thoughtful review and positive evaluation. We have addressed all the typos in the revised draft. The equality in Assumption 2(d) is indeed an equality as there is a $\sup$ on the left hand side.

Section 5 on propagation of chaos (POC)

Thanks for this suggestion. We have added a line stating that such results allow us to draw multiple i.i.d. approximate samples from the target distribution $\pi$, in comparison to a single run of traditional MCMC schemes.

Proof of Theorem 3

This is a very good question. Indeed such uniform-in-time (number of iterations) bounds would significantly improve numerous results in the paper and, in some sense, is the key challenge in SVGD. The few models for which such uniform-in-time estimates can be established involve exploiting some convexity in the driving vector field (through functional inequalities) or a gradient form representation of this vector field. In SVGD, the kernelized projection, which facilitates the particle discretization, comes at the cost of lack of convexity or a suitable gradient form. In the absence of such structure, the typically used method is Grönwall's lemma which gives exponentially growing bounds (in number of iterations) on the magnitude and the Lipschitz-ness of the update operator. Our key observation in Lemmas 3 and 4 is that the positive definiteness of the kernel can be exploited to produce polynomially growing bounds instead of exponentially growing ones. Although such bounds grow with number of iterations, it can still be used to obtain fairly good estimates on the convergence rate as displayed in Theorem 3.

Convergence of SVGD in KL divergence

No, to the best of our knowledge for standard SVGD. To translate the KSD bounds to KL bounds, one would need a good understanding of a Stein log Sobolev inequality. Although some attempts have been made before (see, for example, Duncan et al., 2023), such results seem to be out of reach (especially for $d >1$). For a regularized version of SVGD, He et al., 2024 obtained KL convergence in the infinite particle regime. But regularized SVGD leads to a different dynamics compared to SVGD although it is still a deterministic sampling algorithm. Whether our approach can be used to obtain KL convergence in the finite-particle setup for regularized SVGD is work in progress.

Long-time propagation of chaos for the last-iterate

As the particle dynamics are deterministic given the initial locations, the time-averaging creates the necessary `smoothing' in the absence of additional noise to enable us to prove such a result. It is a great (and open) question whether such POC results hold at the last-iterate level.