Long-time asymptotics of noisy SVGD outside the population limit

Thank you for your positive review and thoughtful questions. Please find our responses below.

The paper poses a question on SVGD, but then in fact does not answer this question (What does SVGD, $\lambda=0$, converge to?), nor does the bulk of the paper seem particularly interested in answering it.

When $\lambda = 0$, the algorithm converges to a set of measures that includes the target $\pi$ as well as some probability measures without density (the addition of the noise allows to avoid measure witout density). However, you are correct that we should not have emphasized this point. As you suggested, we have removed the italics in the updated version.

Indeed, a large noise ($\lambda \gg 1$) will not bias the algorithm. As demonstrated in the newly added Section C, by setting $\lambda$ large, NSVGD behaves like the Langevin algorithm. In fact, it effectively becomes a Langevin algorithm with a step size of $\lambda\gamma\_k$. Therefore, to ensure convergence, it is necessary to have $\lambda\gamma\_k \ll 1$.

Do the theorems allow any uniformity in the dimension d of the underlying problem, say in the case of a log-sobolev constants?

In our proof technique, we cannot establish bounds that provide a definitive answer. However, we can state that the number of particles ($n$) should depend exponentially on the dimension. Indeed, the larger the space, the more particles are needed to adequately cover it. Moreover, the time has a linear dependence on the dimension. Specifically, by examining the proof of Lemma 7, we observe that the constant $C$ (which serves as an upper bound for the Kullback-Leibler divergence) depends linearly on $d$. Additionally, the log-Sobolev constant corresponds to the convexity constant of $F$, where we recall that the target distribution is proportional to $\exp(-F)$.

To summarize, we believe there exists a strong dependency on the dimension $d$.

This version corrects grammatical issues and improves the clarity and flow of the text. Can you provide further experiments, evaluating performance of NSVGD vs SVGD and Langevin sampling? Is there any setup, in particular where lambda=0 is favorable?

We hope to satisfy your requirements in Section C of the updated version of our manuscript. To summarize, we used the toy example of a Neal funnel density. In this setup, SVGD outperforms the Langevin algorithm. We show that by setting $\lambda$ small enough, NSVGD retains the performance of SVGD. Therefore, NSVGD is advantageous as it performs similarly to SVGD and better than Langevin, while also providing convergence guarantees. But, in this particular setup, $\lambda=0$ yields better performance.

The law of those $n$ points may very well have a density, and moreover the law of a randomly selected point could be close to $\pi$. Why is the discreteness of this measure a problem? (You also mention this on l84). Furthermore, even if this were a problem, shouldn't one just change the metric?

By stating that SVGD converges to $\pi$, we mentioned in line 51 that this means the empirical measure $\mu\_k^n$ converges to $\pi$. In this case, for SVGD, one can only hope for $n \to \infty$.

As you said, one could alternatively define the convergence of SVGD as the law of a single particle converging to $\pi$.
But, SVGD works because, in the population limit $n = \infty$, the Kullback–Leibler divergence $D\_{KL}(\mu\_k^\infty \| \pi)$ decreases along $k$. This property cannot hold for finite $n$, since $D\_{KL}(\mu \| \pi)$ is defined only for measures $\mu$ admitting a density. To the best of our knowledge, $D\_{KL}(\text{Law}(X\_k^{1,n}) \| \pi)$ does not decrease for $n<\infty$.

Why should all particles need converge, instead of the evolution of a tagged particle converges?

By Assumption 1-(ii), the particles at time $k =0$ share the same distribution. Furthermore, by the definition of the algorithm, we can verify that all particles $X\_k^{1,n}, \dots, X\_k^{n,n}$ also share the same distribution at any time $k$. Consequently, we can only expect all the particles to converge or none at all.

l.386. There is some double limit notation not properly introduced, l.517. ``usefull''

Thank you for your careful reading. This has now been corrected in the updated version (the definition of the double limit is in l.139.).

We agree with you that it would be interesting to establish a convergence result when the dimension $d$ grows with $k$ and $n$. However, at present, we are unable to establish such a result. We hope we have clarified the reason why it is necessary to study the set of all particles rather than focusing on a single selected particle. Additionally, we hope the new Section C in the updated manuscript provides clarity on the behavior of NSVGD compared to SVGD. If you are satisfied with our response, we would be deeply grateful if you would consider raising your score.

We thank you for your positive review and your kind comments. Please find our responses below.

Figure 1 is illustrative of the fact that NSVGD does not suffer from variance collapse, while regular SVGD does. In that sense, it is a correct validation of the theory presented in the paper. However, it would also be interesting to compare empirically NSVGD to Langevin dynamics. That is, is the SVGD term in NSVGD actually useful, or is the reason for the success of NSVGD simply the Langevin term? Should practitioners use NSVGD or just Langevin? In my view, resolving this issue is critical for NSVGD to be considered a useful algorithm. I’ll be happy to raise my score if this is addressed.

We address your concern in Section C of the updated version of our manuscript. To summarize, we used the toy example of a Neal funnel density. In this setup, SVGD outperforms the Langevin algorithm. We show that by setting $\lambda$ small enough, NSVGD retains the performance of SVGD. Therefore, NSVGD is advantageous as it performs similarly to SVGD and better than Langevin, while also providing convergence guarantees.

While introducing the Langevin terms is useful to fix variance collapse, do the authors know if NSVGD is uniformly better than SVGD? For example, oftentimes SDEs may require a larger number of steps than ODEs to obtain numerical errors below a certain threshold. Can the authors comment on that?

It is true that the Euler scheme for an SDE often requires a smaller step size than the Euler scheme for an ODE. This could be another reason why SVGD may perform better than the Langevin algorithm in some cases.

We did not address the convergence speed of the algorithm. However, it is worth noting that in stochastic approximation, it is common to introduce noise into an algorithm. In cases where the algorithm performs well, adding noise may decrease its performance. However, in more challenging cases, noise can help the algorithm explore the space more effectively and avoid getting trapped in local minima.

In NSVGD, the Langevin regularization plays a similar role. As you pointed out, since SDEs are harder to approximate than ODEs, this regularization can slow down the algorithm in cases where it already performs well. However, in more challenging scenarios, such as high-dimensional problems ($d \gg 1$), SVGD alone may struggle, as the particles tend to cluster and the algorithm can get stuck in a trap. In such cases, NSVGD's regularization can provide an advantage by avoiding these issues.

To answer your question, NSVGD is not uniformly better than SVGD but has better performance in certain challenging cases.

Typos: In line 246, SGVD -> NSVGD. In line 517, usefull -> useful. Thank you for your careful reading. We have addressed this in the updated version of the manuscript.

We hope that the new Section C in the updated version highlights the value of NSVGD compared to Langevin. If you are satisfied with our experiments and explanations regarding the role of Langevin noise, we would be grateful if you could consider raising your score.

We thank you for your review. Please find our responses below.

Why didn't earlier papers prove such results before?

Convergence of the SVGD algorithm when the time grows can only be rigorously established in the population limit $n = \infty$. Therefore, to analyze the convergence of the SVGD algorithm in the finite particle regime, we must show that the finite particle system converges to the population limit as $n \to \infty$. This property is known as propagation of chaos.

A well-known challenge with propagation of chaos is that it typically holds only on a finite time window, due to the use of Grönwall’s inequality. As a consequence, with this type of result, the convergence of SVGD can only be guaranteed if the number of particles grows exponentially with the number of iterations.

If indeed the results are novel, what's the main barrier for theoretical analysis that was overcome?

Instead of using the classical approach based on coupling, we employed a method relying on a tightness argument, specifically designed to study the long-time convergence of particle systems. However, a significant challenge with our approach is that it does not guarantee the avoidance of spurious stationary measures. Since such spurious stationary measures are observed in practice, we introduce a noise term to fix SVGD and ensure convergence to the desired distribution.

We hope to have clarified the importance of this work. SVGD is a well-known algorithm in the variational inference literature, liked for its elegant mathematical properties and strong performance across various applications. We believe we have made significant progress in addressing an important question: "Does SVGD converge?" We would be happy to answer any further questions, and we would greatly appreciate it if you would consider raising your score.

Thank you for the time you spent on the paper. Please find our responses below.

The main weakness is that the noisy version of SVGD deviates a lot from the SVGD used in practice.

We have added a new experiment in Section C of the updated manuscript. In this section, we demonstrate that by setting $\lambda$ sufficiently small, NSVGD exhibits the same dynamics as SVGD.

Presumably, the main reason for analyzing this particular version of noisy SVGD is to resolve certain technical challenges in the proof.

The noise not only resolves certain technical issues in the proof but also addresses a major problem of SVGD: mode collapse (see Section 6).

Is it possible to prove noisy SVGD with other types of noise? What would be the technical challenges there?

We chose to add noise of the form $-\lambda\gamma\_{k+1} \nabla F(X^{i,n}\_k) + \sqrt{2\lambda\gamma\_{k+1}} \xi^{i,n}\_k$, where $(\xi\_k^{i,n})\_{i, k}$ are i.i.d. centered Gaussian random variables with variance 1. However, $\xi\_k^{i,n}$ could, in fact, be any i.i.d. random variable with variance 1, zero mean, and finite fourth-order moments. The proof would remain the same since the limiting McKean-Vlasov equation would be the same.

Alternatively, we could consider noise of the form $\sqrt{2\gamma\_{k+1}\lambda} \xi^{i,n}\_k$, where $\xi^{i,n}\_k$ is a centered random variable with variance 1 with finite fourth-order moments. However, such noise would bias the algorithm, causing convergence to a set $S\_\lambda$ that depends on $\lambda$. As $\lambda \to 0$, $S\_\lambda$ would converge (in the sense of the Hausdorff distance) to the singleton $\{\pi\}$.

We hope that the new Section C in the updated version demonstrates that we have proven the convergence of an algorithm whose behavior resembles SVGD. In proving the convergence of an algorithm whose dynamics resemble those of SVGD, we believe we have made significant progress in understanding the convergence properties of SVGD. We also believe that SVGD requires some noise to ensure convergence. While various types of noise could have been considered, in our manuscript, we chose the simplest form of noise that does not bias the algorithm. We hope this addresses your concerns, and if so, we would greatly appreciate it if you could consider raising your score.