Statistical and Geometrical properties of the Kernel Kullback-Leibler divergence

We thank the reviewer for careful reading the paper and for his relevant suggestions. We have addressed each of your comments below. Please don't hesitate to let us know if you have any further questions.

• Weakness: "Proposition 1 still assumes $p$ is absolutely continuous with respect to $q$ ."

Reply: Thank you for spotting the typo, please see the general comment.

• Weakness : "The bound in Proposition 3 becomes trivial since it approaches $\infty$ as $\alpha \rightarrow 1$."

*Reply: This is true that the bound becomes trivial as $\alpha$ goes to 1. However, our objective in calculating this upper bound was to prove that when $\alpha$ tends to 0, the regularized KKL converges to the true KKL. We are therefore mainly interested in this bound for small values of alpha.

• Question: "Can the authors comment on how the performance of KKL compares with that of skewed KL divergence which is kernel-free and not restricted by a kernel, though the later one can be computationally more expensive?"

Reply The skewed KL is well defined even if $p$ is not absolutely continuous with respect to $q$, but it seems to us that if $p$ and $q$ are atomic measures, and that the support of $p$ will move (for instance in the gradient flow setting as in our paper), then one would need to use kernel-based density estimates at each iteration. This could be an interesting idea to compare with the regularized KKL. We originally did not include it, because from [1], it is known that the KKL is a better approximation of the KL than a KL between smooth estimates of $p,q$ for a specific smoothing kernel, see Equation (8) in [1] which states that $KL(\tilde{p}||\tilde{q}) \le KKL(p||q) \le KL(p||q)$, where $\tilde{p}$ and $\tilde{q}$ are smoothed version of $p$ and $q$. However, this is a simple baseline to implement that we will include in our experiments in the revised manuscript.

• Question: "You mention your algorithm is robust to the choice of $\alpha$. But I was wondering when $\alpha$ is close to 1, as suggested in Figure 1 even for $\alpha = 0.5$, the value of the divergence is always small, so it will be hard to distinguish between different distributions. Can you comment on this?"

Reply: We agree with the reviewer, and this is a problem that would appear with the regular KL - see section A.2 that recalls the monotony of skewed KL with respect to the skewness parameter $\alpha$. One of our contributions is to show that the skewed KKL verifies the same property (see Proposition 2). This is the reason why we tend to use small values of alpha in the rest of the experiments, see for instance Appendix C describing the hyperparameters for different experiments, $\alpha$ is typically of order $10^{-2}$ or $10^{-3}$. For larger values of $\alpha$, i.e. $\alpha=0.5$, an alternative idea would be to consider a "Jensen-Shannon" (JS) version of regularized KKL. Indeed alpha= 0.5 in the skewed (standard- KL can be used to design a JS divergence (see Remark 1) and the second term is used to balance this phenomenon. We think that this is an interesting idea, and will include illustrative experiments with a Jensen-Shannon version of our KKL divergence for the same experimental settings considered in our paper.

• Question : "Why does Figure 2(a) begin with different particles across different methods at $T=0$ ?"

Reply: You indeed spotted a mistake, for KKL, we plotted at T= 1 instead of T = 0 and this is why the initialisation looks different. In the submitted version, we corrected this mistake. You can see the corrected figure in a pdf in the general comment.

Thank you for your feedback and time. We have addressed each of your comment below. If you have any further question, please don't hesitate to let us know.

• Weakness: " The gradient flows built via kernel methods do not seem to perform particularly well, perhaps due to the well-known lack of expressivity. One might have hope that the covariance embeddings in these new divergence would have helped compared to MMD based gradient flow but the authors experiments do not make that case."

Reply We respectfully strongly disagree. We see (visually) on Figures 2.a and 2.b on page 9 that the KKL flow converges to a better particle configuration than the MMD one, even after carefully tuning all the hyperparameters, including for MMD (that is notoriously hard to optimize, see [1]). This is also seen when reporting the convergence with respect to different metrics in the Appendix C (see paragraph "3 rings" starting l683 and Figure 10). We do not understand why the reviewer claims the converse statement. Moreover, it has also been shown the paper cited above [1], that MMD gradient flow alone does not converge well even on simple experiments, e.g. between Gaussians as in Figure 2 in [1]. KKL flow also works better than KALE in the case where L-BFGS method is used, a method which cannot be used for the KALE flow as it doesn't have a closed form expression for its loss and gradient (that are requirements for L-BFGS). If the reviewer disagree or has questions on the experiments, please let us know so that we can clarify.

• Question "Is there a reasonable expectation that their flows to scale up to high dimension? Or what is the obstacle?"

Reply: Notice that in Appendix C, we conduct experiments on mixture of Gaussians up to dimension 10, see paragraph starting l669 and figures at the top of p26). We acknowledge that we did not try to use KKL in higher dimensions such as the one of images or in a more challenging generative modeling setting. A first step would be to work on reducing the computational complexity of KKL (which is $O((n+m)^3)$ as discussed l251 wrt to the number of samples, that should be multiplied by $d$ which is the kernel computation cost) to work on high-dimensional and large datasets. We leave this study for future work.

• Question "It seems to the reviewer that Wasserstein gradient flow based on kernel methods do not seem to perform well compared to gradient flows using neural network architecture. This occurs in the case of SVGD but also for plain Wasserstein gradient flows. For example the gradient flows in [2] based on Lipschitz regularization of KL-divergence are comparable in spirit to the MMD of Kernel-KL flows considered here. Is the reviewer mistaken? Can the authors provide some insights on these issues."

Reply: There might be a slight confusion here, but let us know please if we misunderstood. There exists 2 types of kernel-based approximations of the Kullback-Leibler divergence that were proposed in the literature: (a) the one we propose here, based on kernel covariance embeddings and (b) the "variational one" (see Equation (12) in our paper). The paper you are referring to is analog to the second type; the difference being that the variational family there is defined by neural networks. Regarding the performance of this divergence compared to ours, there are two ingredients at play: (1) first, the type of approximation, and (2) second the parametric family. Regarding (1), it is not clear how our kernel-based approximation of the standard KL (i.e. type (a)) is "better" than the variational approximation such as KALE (i.e. type (b)). Our work, through numerical experiments, is a first tentative for comparing these different techniques, through comparing KKL with Kale.
Then, the choice of parametric family is crucial indeed. In the reference mentioned by the reviewer, the variational family is approximated through neural networks instead of a Gaussian RKHS as in KALE. As explained in Section 1 therein, when the variational family is an RKHS ball, these approximated divergences interpolate between MMD and KL divergence, while if it is the class of 1-Lipschitz functions, it interpolates between Wasserstein-1 (which has much better topological and geometrical properties than MMD) and KL. In [2], the space of 1-Lipschitz functions is approximated by a space of neural network. A possible (and fair) comparison in our framework (i.e. type (a) using the KKL) may be to learn a kernel feature map with neural networks before applying KKL formula - instead of considering directly Gaussian kernels as in our paper. We think this is an interesting but deep question that requires further investigation.

[1] Arbel, Korba, Salim, Gretton. Maximum Mean Discrepancy Gradient Flow, Neurips, 2019.

[2] Gu, Birmpa, Pantazis, Ret-Belley, A. Katsoulakis, Lipschitz-Regularized Gradient Flows and Generative Particle Algorithms for High dimensional Scarce Data, 2023

Thank you for your careful reading and relevant suggestions. We have addressed your comments point-by-point below. Please don't hesitate to let us know if you have any further questions.

• Question: "The decreasing property of $KKL_{\alpha}$ in Proposition 2 needs the condition that $p$ is absolutely continuous with respect to $q$. However, in the definition of $KKL_{\alpha}$ (L144-L145) there is no need for this absolutely continuous. My question does this property still valid without $p \ll q$ ? The same remark for the result in Proposition 4."

Reply: See the first point of general comment for the reply concerning Proposition 2.

Concerning Proposition 4, it is an interesting and important point that you bring up. We chose to make the assumption $p\ll q$ similarly than in Proposition 3, which shows the convergence of the regularized KKL to the true KKL in the case where $p \ll q$ as the regularization parameter $\alpha \to 0$. Under this common assumption, we can thus use Proposition 3 and 4 simultaneously to control the deviation of the regularized KKL on empirical distributions versus the unregularized KKL between $p$ and $q$. Additionally, under this assumption, the bound in Proposition 4 scales with respect to the regularization parameter $\alpha$ as $\mathcal{O}(1/\alpha)$.

The reviewer is right that this assumption is not the minimal assumption one could work with to obtain guarantees on the finite-sample approximation guarantees as we derive in Proposition 4. Indeed, it is possible to derive a similar rate of convergence without the assumption of absolute continuity, i.e. a bound that scales similarly with the number of samples $n,m$, by slightly modifying the proof (see details below). However, in this case, the bound would scale with respect to the regularization parameter as $\mathcal{O}(1/\alpha^2)$. We chose to propose only the first one in the paper as it scales better with $\alpha$ when $\alpha$ is small, but we realize thanks to the comment of the reviewer that this is an important point, and we will provide the alternative one.

We provide in this paragraph more details about why the scale with respect to $\alpha$ changes depending on the hypothesis. In the proof, we repeatedly upper bound different terms by a quantity depending on $C(\beta) = \sup_x \langle \varphi(x), (\Sigma_p + \beta I)^{-1} \varphi(x) \rangle$, using by taking advantage of the assumption that $c = \int C(\beta)^2 d\beta$ is finite. Also, we regularly have to deal with terms in which the operator $(N + \beta I)^{-1}$ appears, where $N = \alpha \Sigma_p + (1-\alpha) \Sigma_q$. Under the assumption $p\ll q$ and $dp/dq \le 1/\mu$, by operator inequality, the operator $(N + \beta I)^{-1}$ is upper bounded by $\frac{1}{(1- \alpha)\mu}(\Sigma_p + \beta I)^{-1}$, using the inequality $N \succeq (1-\alpha) \Sigma_q \succeq (1-\alpha) \mu \Sigma_p$. This will result ultimately in only one $\alpha$ in the denominator of our bound, i.e. the scale $\mathcal{O}(1/\alpha)$ mentioned above. Alternatively, it is possible to bound $(N + \beta I)^{-1}$ by $\frac{1}{\alpha}(\Sigma_p + \beta I)^{-1}$ using the simpler $N \succeq \alpha \Sigma_p$ and this does not require absolute continuity of $p\ll q$. However, this ultimately results in an additional factor $\frac1{\alpha}$ in our bound compared to the previous case, hence the scale $\mathcal{O}(1/\alpha^2)$, that is less favorable when the regularization parameter $\alpha$ is small. The corresponding bound is this one:

$\mathbb{E} | KKL_{\alpha}(\hat{p}||\hat{q}) - KKL_{\alpha}(p||q) | \leqslant \frac{32}{\alpha \sqrt{m \wedge n}} (2 \sqrt{c} + \log n) + \frac{2}{m \wedge n} \left(\frac{1}{\alpha} + \frac{c(26 \log n)^2}{\alpha^2} (1 + \frac{n}{m \wedge m})\right).$

Thank you for pointing out this essential point, which we will clarify in the paper by giving an alternative proof and an alternative bound.

• Question: "In Proposition 4, the definition of $\varphi(x)$ needs to be recalled."

Reply: Thanks for the suggestion, we will indeed recall that $\varphi(x)$ is the feature map of $x \in \mathbb{R}^d$ in the RKHS $\mathcal{H}$.

• Question: "In Proposition 4, could you please motivate the condition on the Radon-Nikodym derivative to be bounded above by $\frac1{\mu}$." .

Reply: see answer above; in summary it enables us to get a tighter bound with respect to the regularization parameter $\alpha$ when it gets smaller.

• Question: "To facilitate the lecture on the bound given in Equation (5), I think it will be better to write its order."

Reply: Thanks for the suggestion, we already worked on this post submission and think that this is an excellent suggestion to present our results in this simplified manner. A simplified bound is provided in the general comment to all the reviewers.

• Question: "In Proposition 5, I didn't understand the definition of the gram kernels $K_x$, $K_y$, $K_{xy}$. Do these operators design the covariance operator or other more general kernels?

Reply: Our notations here were confusing and we changed them. In the submission, $K_x$ and $K_y$ as defined in l207 refer to standard Gram matrices related to the kernel $k$ and the sample set $x_1,\dots, x_n$ or $y_1,\dots, y_m$. The matrix $K_{xy}$ is the Gram matrix related to the two sample sets. These notations hence refer to Gram matrices and not covariance operators. In a nutshell, our statement in Proposition 5 shows that the regularized KKL for two empirical distributions $\hat{p},\hat{q}$ writes as a simple function of Gram kernel matrices. \vspace{2mm}

• Minor typos: thanks for spotting these, we corrected accordingly.

Thank you for your valuable feedback and time. We have addressed your comments point-by-point below. Please don't hesitate to let us know if you have any further questions.

• Weaknesses: "the title does not reflect the contributions of the paper"

  Reply: We acknowledge the title does not reflect the fact that we are studying the regularized KKL and it is not clear that we are doing gradient flows on it, we will add this precision in the title.

• Questions: "line 124 -- what do you mean by "if is compact"

Reply: "$\mathbb{R}^d$ is compact" is a typo, it was originally a subset of $\mathbb{R}^d$. Thank you for this correction.

• Questions: tightness of Prop 4

Reply: See general comment please.