Convergence of SVGD in KL divergence via approximate gradient flow

Answer to weakness points and questions

• For weakness and the 2nd question: We agree that Assumption 6 is strong, which is one of the limitations of our study. In the present study, this assumption was adopted because the priority is to first provide a convergence guarantee of SVGD in KL divergence. Pursuing convergence guarantees grounded in milder assumptions represents a crucial avenue for future research. We also believe that, even with such a strong assumption, our results will encourage research on guaranteed convergence under more realistic assumptions by making them available to the public.

• To the 1st question: Regrettably, our AGF-based analysis only informs us of the existence of a time-independent constant $c_{0}$. A more intricate analysis is requisite to ascertain the qualitative properties of this constant. However, such an investigation exceeds the scope of this paper, as our primary focus is to ensure sub-linear convergence in KL divergence. Nonetheless, based on your advice, we will consider exploring the detailed nature of this constant for a comprehensive understanding of SVGD convergence in our future work.

• To the 3rd question: As suggested in works like [Liu et al. (2018)], there is a possibility of exhibiting oscillatory behavior around the fixed point in the setting with finite particles. We hypothesize that a similar phenomenon may have occurred in our experiment. In the SVGD context, much is still unknown about the convergence of SVGD with finite particles in the KL divergence, partly because this paper is the first proof for the infinite particle setting.

Reference:

[Liu & Wang (2018)]: Q. Liu and D. Wang. Stein Variational Gradient Descent as Moment Matching. In Advances in Neural Information Processing Systems, volume 31, pp. 8868–8877, 2018.

Answer to weakness points and questions

• For weaknesses 2-3, and question 3:

  • The assertion that $\delta=0$ in our AGF is not readily evident from existing knowledge, such as LSI. Instead, it is a theoretical result that becomes apparent through analyzing the gradient flow of SVGD under our AGF, employing spectral decomposition and others. To commence, as [Duncan et al. (2023)] noted, conducting convergence analysis with (stein) LSI on RKHS has proven challenging. In this context, we have shown that we can evaluate convergence through "LSI-like" inequalities by demonstrating that SVGD, under the infinite particle setting, achieves $\delta=0$ in our introduced AGF. Utilizing this finding, we show the sub-linear convergence of SVGD in KL divergence. All our theoretical analysis results are non-trivial and can be attained by introducing our AGF rather than relying solely on conventional LSI.
  • Further discussion is needed to elucidate the connection between Eq. (7) outlined in [Duncan et al. (2023)] and our findings. Indeed, our results are tied to Eq. (7); however, [Duncan et al. (2023)] assert that satisfying Eq. (7) for ANY distribution $\mu$ is challenging. While speculative, the distribution $\mu$ may satisfy such inequality within a context that aligns with the assumptions discussed in our paper. The demonstration by [Liu et al. (2023)] of linear convergence in the KL divergence for SVGD, with the constrained assumption that the target distribution is Gaussian, may imply that Eq. (7) might be valid under specific and restricted conditions.

• For question 1 (related to weakness 1):

  • Assumptions 5 and 6 do not contradict. Assumption 6 states that each eigenvalue $\lambda_{i}$ (for all $i$) has a positive upper and lower bound independent of $t$. Let us focus on the RBF kernel $k_{\mathrm{RBF}}$ for simplicity. In this case, it is known that $\lambda_{i} = \mathcal{O}(e^{-i \log i})$, thereby establishing $\lambda_{i} = \Omega(e^{-i \log i})$ (refer to Example 12.25 in [Wainwright, 2019]). This fact verifies the fulfillment of Assumption 6, as $\lambda_{i}$ is a constant order w.r.t. $t$. Additionally, given that the RBF kernel satisfies all conditions of Mercer's theorem (refer to Section 12.3 in [Wainwright, 2019]), we can employ the Mercer expansion for $k_{\mathrm{RBF}}$ to derive $k_{\mathrm{RBF}}(x,x) = \sum_{i=1}^{\infty} \lambda_{i}\phi_{i}^{2} < \infty$. This observation confirms the validity of Assumption 5.

• For question 2 (related to weakness 1): Thank you for taking the time to peruse the proofs. This concern is similar to reviewer Spa3's Q.2, so please see our response to it (please see p.20 of the modified version of this paper).

Reference:

[Duncan et al. (2023)]: A. Duncan, N. N ̈usken, and L. Szpruch. On the geometry of Stein variational gradient descent. Journal of Machine Learning Research, 24(56):1–39, 2023.

[Liu et al. (2023)]: T. Liu, P. Ghosal, K. Balasubramanian, and N. S. Pillai. Towards understanding the dynamics of Gaussian-Stein variational gradient descent. arXiv preprint arXiv:2305.14076, 2023.

[Wainwright, 2019]: M. J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.

For weakness

Your diligence in raising this crucial point is appreciated. To find our responses, kindly consult our official comments addressed to all reviewers. We have integrated a discussion of this specific matter into the newly introduced "Limitation & Conclusion" section.

Answers to questions

• To the 1st question: We apologize for the unclear explanation. What we would like to explain here is that MCMC tends to be computationally intensive. We modified this sentence as follows:

  • “While MCMC provides guarantees of producing asymptotically unbiased samples from the target density, it tends to be computationally intensive (Robert & Casella, 2004).”

• To the 2nd question: We agree with your opinion. We modified some sentences and explanations. It would be too complicated to describe the corrections here, so please see p.20 of the modified version of this paper.

Answers to comment

Thank you for pointing that out. We agree that [1] and [2] should have been cited. We will include the following sentences with the references of these papers in the third and fourth paragraphs of Sec. 1 for both papers:

• …like gradient descent. Beyond the infinite particle setting, Shi & Mackey (2023) also showed that the SVGD with $n$ finite particles and an appropriate step size converges at the $\mathcal{O}(1/\sqrt{ \log \log n })$ order if the target distribution is sub-Gaussian with a Lipschitz score...

• …function of SVGD. Recently, Liu et al. (2023) showed that SVGD with finite particles achieves linear convergence in KL divergence under a very limited setting where the target distribution is Gaussian. However, the analytical approach presented in previous studies makes it difficult to conduct convergence analysis based on KL divergence in a more global setting. The reason…

Thanks for the responses. The proofs in the revised version look good to me now. I have the following a minor comment on the Assumption 6:

1. In [He et al., 2022]: He, Y., Balasubramanian, K., Sriperumbudur, B.K. and Lu, J., 2022. Regularized Stein variational gradient flow. arXiv preprint arXiv:2211.07861. Convergence of R-SVGD, which degenerates to SVGD when the parameter is 0, in KL-divergence was studied under assumptions of the RKHS kernel as well. Is it possible to compare their assumptions and Assumption 6 in this paper? This may provide more insights to finding the optimal kernels in SVGD.

Answers to questions (2)

• To the 3rd question: Thank you for bringing up this important point. For our responses, please refer to our official comments to all reviewers. We have incorporated a discussion of this particular point into the newly added "Limitation & Conclusion" section.

For MISC

Thank you for your careful reading. We have modified almost all the matters you pointed out. Please see the revised version of our paper. By labels in Fig. 1, do you mean the labels for the y-axis values in the third figure from the left? We don't consider the values between $10^{0}$ and $10^{-1}$ essential since it is sufficient to understand that the KSD value converges to smaller values as they approach the infinite particle setting. Concerning the y-axis range, it's important to note that KSD and KL values are incomparable. These plots aim to assess whether KSD and KL achieve sub-linear convergence in a finite particle setting. Adjusting both scales to match could result in a figure that obscures this behavior. We believe the current state provides the most intuitive means to examine sub-linear convergence.

Reference

[Liu et al., 2016]: Q. Liu and D. Wang. Stein variational gradient descent: A general purpose Bayesian inference algorithm. In Advances in Neural Information Processing Systems, volume 29, pp. 2378–2386, 2016.

[Korba et al., 2020]: A. Korba, A. Salim, M. Arbel, G. Luise, and A. Gretton. A non-asymptotic analysis for Stein variational gradient descent. Advances in Neural Information Processing Systems, 33:4672–4682, 2020.

[Salim et al., 2022]: A. Salim, L. Sun, and P. Richtarik. A convergence theory for SVGD in the population limit under Talagrand’s inequality T1. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pp. 19139–19152, 2022.

[Shi et al.,, 2023]: T. Liu, P. Ghosal, K. Balasubramanian, and N. S. Pillai. Towards understanding the dynamics of Gaussian-Stein variational gradient descent. arXiv preprint arXiv:2305.14076, 2023.

[Shi & Mackey, 2023]: J. Shi and L. Mackey. A finite-particle convergence rate for Stein variational gradient descent. arXiv preprint arXiv:2211.09721, 2023.

For weakness

• About outlined proof: We believe that proof outlines, as in Section 4.2, constitute a vital aspect of this paper and should be articulated rigorously, even if their presentation is somewhat dense. What kind of intuitive or qualitative explanation would facilitate a more precise understanding? We would greatly appreciate it if you could provide an example of the type of explanation you would find helpful, even if it is based on personal opinion.
• Broader impact and applicability: Our study revealed that the sample obtained by SVGD converges to the target density in KL divergence, albeit exclusively in the infinite particle setting. This suggests weak convergence of SVGD with infinite particles, affirming its capability to approximate the expectation by the target distribution without bias, akin to MCMC. This finding could enhance users' confidence in the effectiveness and reliability of SVGD. In our future work, we aim to offer theoretical guarantees for the convergence of SVGD with finite particles in KL divergence, as outlined in the official comments. These discussions and official comments are summarized in a new section titled "Limitations and Conclusions."
• About the conclusion section: We agree with your opinion. We have introduced a new section titled "Limitations and Conclusions," specifically addressing the content outlined in the above official comment. Please see the revised version of our paper.
• About lack of numerical experiments and take-away message from numerical experiments: Our study analyzes SVGD in the infinite particle setting, acknowledging its unimplementability as an initial step towards furnishing a realistic convergence guarantee for SVGD. To corroborate the validity of the analytical results derived from the infinite particle setup through numerical experiments with finite particles, it is essential to formulate an experimental design capable of completion within a realistic computation time, even when employing a huge number of particles to simulate a near-infinite particle setup. To attain this goal, employing simple examples like the log-concave distribution experiment proves useful. We believe that the discussion of numerical experiments on convergence in more practical experimental settings will constitute a vital element in our forthcoming study on ensuring the convergence of SVGD in the KL divergence within the finite particle setting detailed in our official comment.

Answers to questions

• To the 1st question: MCMC faces scalability issues in handling big data, while VI efficiently approximates posterior distributions, transforming Bayesian inference into a deterministic or stochastic optimization problem. However, the accuracy of VI is influenced by the choice of the set of variational distributions, introducing bias when approximating complex target distributions with simpler ones. To reduce this bias, methods based on importance sampling have been studied; however, they pose the additional challenge that their effectiveness depends on the accuracy of the composition of the proposal distribution (e.g., $q(x; \theta)$ constructed by the neural network in [1]). In this context, SVGD was developed as a more efficient and less biased algorithm that eliminates the need for the bias-reduction methods described above by allowing the removal of constraints imposed by variational distribution sets (refer to Sec. 1 in [Liu et al., 2016] for details). To clarify this point, we modified the 1st and 2nd paragraphs of Sec. 1 as follows:

  • In the 1st paragraph: “... While MCMC provides guarantees of producing asymptotically unbiased samples from the target density, it tends to be computationally intensive (Robert & Casella, 2004). On the other hand, VI achieves a computationally efficient approximation of the target distribution through stochastic optimization under a simpler alternative distribution; however, it does not come with a guarantee of obtaining unbiased samples (Blei et al., 2017).”
  • In the top of the 2nd paragraph: “To alleviate such sample bias while maintaining computational efficiency of VI as much as possible, Liu & Wang (2016) introduced Stein variational gradient descent (SVGD), which allows the direct approximation of the target distribution without the need for alternative distributions.”

• To the 2nd question: Since the RBF kernel is the most standard one employed in SVGD, many studies have adopted this kernel in the theoretical or empirical analysis (e.g., [Korba et al., 2020], [Salim et al., 2022], and [Shi et al., 2023]). We followed this context as well. In other kernels employed in SVGD, the IMQ kernel ([Shi & Mackey, 2023] focused on this kernel, for example) may be able to satisfy these assumptions.

(Our responses follow in the next thread.)

I've read the updated version of the manuscript. I acknowledge the effort of the authors in addressing all my concerns. For this reason, I decided to increase my score.

I think the paper is much clearer now. Unfortunately, I got very sick over the past five days and did not come up with a satisfying idea for an outlined proof. Nevertheless, I believe the paper already benefitted from the improvements suggested by the referees.

As far as the labels in Fig. 1 are concerned, I meant all the labels were a bit too small, in my opinion. I think they may be hard to read for the general public without zooming in. I understand that the values between $10^0$ and $10^{-1}$ are not relevant for the analysis, though this was not my main concern.