Summary
This paper provides an analysis of the convergence rate of finite-sample Stein Variational Gradient Descent (SVGD) for sub-Gaussian targets with Lipschitz scores. In contrast to previous works such as Liu 2017, Duncan et al. 2019 and Korba et al. 2020, the presented results offer convergence guarantees that hold for finite samples and rely on weaker assumptions. The authors present two key results regarding the discretization error of finite-sample SVGD compared to infinite-sample SVGD, measured in terms of Wasserstein (Theorem 1) and KSD (Theorem 2), respectively. These results are then combined to establish a finite-sample bound on the KSD error between a finite-sample approximation and the target distribution (Theorem 3). By carefully selecting step sizes, the authors demonstrate that this error decays at a rate of $1 / \sqrt{\log \log n}$ (Corollary 2).
Strengths
**Quality**: This paper provides a rigorous study of the convergence of finite-sample SVGD and delivers clear and well-supported results. The main findings (Theorem 1, 2, 3) build upon existing results (Lemma 1 and 4) but require sophisticated combinations and detailed arguments. The authors provide extensive discussions and overview the proof strategy, which appears reasonable and comprehensive (although I did not examine the proofs in depth).
**Novelty**: This paper offers a crucial contribution by bridging the gap between the existing convergence guarantees of infinite-sample SVGD and the practical implementation of finite-sample approximations, which is currently lacking in the literature. Whilst the established convergence rate is slow, this work stands out as the first to provide an explicit, non-asymptotic guarantee for SVGD approximations under reasonably mild assumptions on the target distribution. This, in my view, is the primary novelty and significance of this paper.
**Clarity**: The paper demonstrates clear motivation and objectives. Despite the technical nature of the content, the exposition is highly comprehensible. The intuitive explanations and remarks provided before and after each main theorem are particularly valuable in aiding understanding.
Weaknesses
**Slow convergence rate**: As mentioned above and in the paper, the established rate $1 / \sqrt{\log \log n}$ is notably slow, suggesting that the bound (3) is likely to be very loose. Although the authors acknowledge the potential of the presented proof strategy as a starting point for refining the bounds, it is not entirely clear whether or not or how the proof could be adapted to achieve an improved bound. Including discussions on potential avenues for enhancing the convergence rate would be valuable and insightful.
Questions
1. There are a few places that say “the Algorithm 2 outputs $\mu_r^n = SVGD(\mu_0^n, r)$…”, e.g. L166. Since this output is based on a discrete measure $\mu_0^n$, should it be “the **Algorithm 1** outputs …” instead?
2. COuld you elaborate on the suggested step size scheme in Corollary 2? Specifically, what is the dependence on the sample size $n$ and on the dimension $d$? How easy is it to construct the upper bounds $(\overline{w}_{0, n}, \overline{A}, \overline{B}, \overline{C})$ in practice?
3. As also mentioned in the paper, the established rate $1 / \sqrt{\log \log n}$ is very slow. Could you provide some insights into which parts of the proof strategy could possibly have led to this slow rate? Is the bound (3) tight? How does this convergence rate compare with empirical performance in numerical simulations?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The assumptions on the target distribution, its score function and the positive definite kernel are summarised in Section 2, accompanied by interpretations and discussions on their connections to related literature. Limitations are also discussed in Section 9. Overall, I think the discussions on assumptions and limitations are adequately covered.