Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation

Summary

The authors propose a implementable stochastic approximation algorithm based on Stein Variational Gradient Descent, which the idea is based on a stochastic approximation at the probability measure level. The efficiency and convergence analysis of the proposed algorithm, i.e. VP-SVGD and GB-SVGD, are presented. A better convergence rate for the proposed algorithm is proved given a weaker assumption for the potential function

Strengths

The authors propose a new algorithm, a stochastic approximation at the probability measure level according to the authors, to study the SVGD. The focus is to improve the convergence rate and make the algorithm more efficient. The idea of the proposed algorithm in (3) seems to be new. The intuition and design of the algorithm is interesting, and it seems to work as shown in the numerical experiments.

Weaknesses

The reviewer feels that the intuition and the theoretical results have some gaps. To be more precise, some of the arguments are only explained at the intuition level without rigorous proof. It might be possible the reviewer missed the key point of the proof, if this is the case, please correct me.

Questions

1. What is exactly the mild assumption for potential function F, which is weaker then Poincare and Talagrand inequality? How significantly different for this condition, e.g. regarding the proof ? 2. Section 3 is not well presented. The push-forward map $(\cdot)_{\sharp}$ is not defined, but only mentioned, which is not clear. But this is a key step in designing the algorithm. 3. Section 4, the notation for filtration is not good, $\mathcal F_t$ should be measurable up to time $t$, but here it is measurable up to time $t-1$, which results the notation $\mu_t|\mathcal F_t$ confusing. 4. Up this this point, updates in (2) is not rigorously derived, but only intuitively mentioned. Then the algorithm (3) is based on (2), which is not clear to me why (3) is a stochastic approximation? It seems to be deterministic given the previous time step particle values. The same questions for $\mu_t|\mathcal F_t$, the conditional measure based on updated in (3) does not seem to be random. If there is a better way to present this idea, please clarify. 5. The random function $g_t(\mathbf X)$ is not clear, where does the randomness come? 6. the mini batch size comes in Algorithm 1. which does not show before in section 4. There is a gap between the Algorithm 1 & 2 and (2)(3)(4). 7. What is exactly the role of countably infinite many particles, as in the algorithm only $KT+n-1$ are used? I seems that this assumption is important, if this can be explained more clear, it should help improving the presentation.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

see above

Summary

This study analyzed the finite particle behavior of Stein Variational Gradient Descent (SVGD) in an asymptotic manner. For that purpose, the authors designed two computationally efficient variants of SVGD, namely VP-SVGD and GB-SVGD, and prove their convergence rates. In those methods, the authors introduced a new concept of "virtual particles" and develop a new stochastic approximation of the population-limited SVGD dynamics in the probability measure space. The proposed algorithm shows a significant improvement of the convergence rates under looser conditions than the usual SVGD.

Strengths

- The convergence rates in this paper are significantly better than existing methods. - The idea of virtual particles introduced for the analysis is very novel and very interesting in itself. - Numerical experiments, although simple, suggest that the proposed method is indeed an improvement over existing methods.

Weaknesses

- Notation in Sec 4 is very confusing, especially about $l, s, t$ - In the explanation of Sec 4, only the case of K=1 is clearly stated, and I had to spend a lot of time thinking about what happens when K>2. I think an additional explanation of K > 2 is needed in the Appendix. - The algorithm of GB-SVGD is difficult to understand. In particular, the third line mentions "l", but "l" does not appear at all in the fourth line. This may be because the "l" in the third line may be a mistake for "s". - I am not sure if the theoretical comparison of the convergence order with the existing analysis is justified since the VP-SVGD is no longer the original SVGD. The GB-SVGD is close to the existing SVGD, but it is also difficult to compare with the existing SVGD because of the approximation errors as shown in Theorem 2.

Questions

- What is $\nabla_2$ in Line 143 ? Partial derivative with respect to the second variable? - Is my following understanding correct? Intuitively, the motivation for introducing virtual particles is to ensure that the resulting particles are i.i.d, which is required to use Lemma 7 in the theoretical analysis. - Algorithm 1 requires a larger number of particles in proportion to the time step T than ordinary SVGD, and therefore the number of gradient calculations increases considerably. To achive $KSD(particles,\pi^*)\leq \epsilon$, does VP-SVGD increase the order of magnitude of the number of the gradient calculation compared to standard SVGD? - I was wondering why S is taken randomly in Algorithm 1 line 6 and Algorithm 2 line 7, etc., and I thought it would greatly reduce the practical performance. But after reading the proof, I understand that this is necessary to convert the bounds of $\frac{1}{T}$KSD^2(\mu_t|\pi^*)$ to KSD(\bar{\mu}|\pi^*}) as shown in Theorem 1. Is this understanding correct? - In the numerical experiment, are random $S$ used as written in TAlgorithm 1 and 2? Since the objective function is convex, such random S may not have such a strong effect on the final performance. I wonder how harmful this random $S$ is when the objective distribution is non-log concave?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

Theoretical limits are discussed in detail.

Summary

The paper studies Stein Variational Gradient Descent (SVGD) which is a popular variational inference algorithm that simulates an interacting particle system to approximately sample from a target distribution. The authors propose two variants of SVGD, Virtual Particle SVGD (VP-SVGD) and Global Batch SVGD (GB-SVGD), that differ in their implementation details and computational efficiency. Both variants use the so-called "virtual particles", which are additional particles that evolve in time but are not part of the output, to compute information about the current population-level distribution of the real particles and enable exact implementation of the stochastic approximation using only a finite number of particles. The use of virtual particles allows for faster variants of SVGD with provably fast finite-particle convergence.

Strengths

This paper introduced two variants of SVGD, VP-SVGD and GB-SVGD, that use virtual particles to enable the exact implementation of the stochastic approximation using only a finite number of particles. The authors present a non-asymptotic analysis of the convergence of VP-SVGD and GB-SVGD to the target distribution, which demonstrates a double exponential improvement over the best-known finite-particle analysis of SVGD. The paper proposes a new algorithm, VP-SVGD, that achieves provably fast finite-particle convergence and is computationally more efficient than ordinary SVGD. The paper is well-organized and clearly written, with detailed explanations of key concepts and technical details that make it accessible to a wide range of readers. Literature review of related work on SVGD and its variants was conducted comprehensively, which helps to contextualize the proposed algorithms and their contributions. I went through the proofs of Theorem 1 and Corollary 1 or 2 in Section E in detail, and believe they are technically sound. The KSD metric satisfies the triangle inequality where the upper bound is in two additional parts. In (34), the KSD metric satisfies a triangle inequality, and the first term (probability kernel vs population limit) is polynomial with a polynomial decaying exponent that is independent of dimension $d$ ($d^{1/3}T^{-1/6}$ when subgaussian). The second term appears dominating, where the polynomial decaying exponent in Wasserstein-1 distance is $\Theta(1/d)$, which is due to Lemma 8 by Lei [29].

Weaknesses

Despite its significant contributions, this work assumes a certain level of familiarity with the concepts of variational inference and particle methods and is relatively specialized and may make it difficult for readers who are not already familiar with or not working on the topic of SVGD and its variants to follow. Despite the technical contributions of proposed SVGD-style algorithms and their convergence properties, the authors did not provide a detailed discussion of the limitations of the proposed algorithms or potential avenues for future research, which may limit their impact and relevance in the long term it and make it less accessible to readers who are more interested in the broader implications of the work. Lastly, the work does not provide sufficient details on the proposed algorithms' empirical evaluations of real-world datasets, which limits the ability to assess their practical usefulness. These weaknesses did affect my current rating, but I reserve the possibility to raise the score if any of the above points can be resolved in the authors' rebuttal.

Questions

I am not a leader in the topic of SVGD but had a chance to work on the topic at a senior educative level. Hence I recognize the importance of this topic. Some questions are as follows: How do the VP-SVGD and GB-SVGD variants of SVGD differ from the original SVGD introduced by Liu and Wang [32]? My understanding is that the key difference between VP-SVGD and GB-SVGD variants of SVGD is that VP-SVGD is a stochastic approximation of the exact SVGD dynamics, while GB-SVGD is a specific random-batch approximation of SVGD which enjoys computationally more efficient than ordinary SVGD. Is that correct? Can you explain more about the concept of virtual particles and how they are used in these algorithms? I understand that virtual particles are additional particles that evolve in time but are not part of the output (i.e., real particles) which are used only to compute information about the current population-level distribution of the real particles. Are they absolutely necessary --- are there any equivalent or similar implementations that do not necessarily require the introduction of virtual particles? In the technical analysis of Corollary 2, is there any hope to make the decaying exponent in polynomial rate dimension-free or have a weaker dependence on dimension (perhaps using an alternative metric or developing new analytic tools to yield an improved bound)?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

The work is purely theoretical and admits no negative social impacts.

Summary

This paper propose two variants of stein variational gradient descent (SVD) named as Virtual Particle SVGD (VP-SVGD) and Global Batch SGVD (GB-SVGD) with provably fast finite-particle convergence rates to a target distribution. Introducing the notion of virtual particles, the authors show that VP-SVGD is an exactly implementable finite-particle stochastic approximation of population-limit SVGD dynamics in the space of probability measures. Viewing VP-SVGD as a specific random-batch SVGD algorithm, the authors argue that the output particles from GB-SVGD after T time steps with batch-size K are as good as sampling iid from a distribution whose Kernel Stein Discrepancy (KST) to a sub-gaussian target distribution is at most $O(d^{1/3}/(KT)^{1/6})$. Furthermore, under mild growth conditions, the authors show that the empirical distribution of the n-output particles from both VP-SVGD and GB-SVGD converges to the target in KSD at a rate of $O(d^{2}/(n)^{\Theta(1/d)})$. The authors note that this is a doubly exponential improvement over the state-of-the-art finite-particle analysis of SVGD under weaker assumptions. Finally, the authors provide numerical experiments to show fast convergence of GB-SVGD which is computationally more efficient than SVGD.

Strengths

1)Originality: This paper is introduces two new variants of SVGD appealing to a novel construction involving countably many virtual particles. Although the analysis involves infinitely many particles, a finite-number of particles exactly suffice for the actual algorithm VP-SVGD. This enables the authors to claim that VP-SVGD performs a finite-particle stochastic approximation of the population (infinite-particle) dynamics of SVGD over the space of probability distributions. Finally, they show VP-SVGD and the computationally efficient GB-SVGD behave very closely. 2)Quality: I think this paper is technically quite solid. The theoretical claims are all sound and the assumptions are reasonable. 3)Clarity: This paper is well written. It is easy to follow the main ideas including the problem statement, technical challenges, relevance to past works, and the contributions. 4)Significance: It is quite significant to improve the SOTA result doubly exponentially under weaker assumptions. Besides, the virtual particle method is worthwhile studying by itself ( I am not aware of a similar method discussed somewhere else).

Weaknesses

It wasn't easy for me to parse some of the theoretical results, which can be expected as this paper is theory heavy. A table of past works comparing the results in terms of assumptions, method, and the convergence rate might be a helpful addition.

Questions

I suspect there are a few typos in the text. 1)bold x with varying subscript in line 249 vs bold x with varying superscript in the equation after line 250. also the index runs to T but I would expect T-1. 2)bold x instead of bold y in line 224 3) In line 204, we are already given that $g_s(x) = ...$ and then in line 306 we are told that $g_s(x) \approx ...$, Is this a typo ?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Limitations and future works are discussed.

Thank You!

We thank the reviewer for their prompt and helpful response.