Statistical and Geometrical properties of the Kernel Kullback-Leibler divergence
Authors: Anna Korba
Francis Bach
Clémentine Chazal
Venue: NeurIPS 2024 poster (2024)
Keywords: kernels; optimisation; optimal transport
Primary area: probabilistic_methods
TL;DR: In this paper, we study the statistical and geometric properties of the Kullback-Leibler divergence with kernel covariance operators (KKL) introduced by [Bach, 2022, Information Theory with Kernel Methods].

Abstract: In this paper, we study the statistical and geometrical properties of the Kullback-Leibler divergence with kernel covariance operators (KKL) introduced by [Bach, 2022, Information Theory with Kernel Methods]. Unlike the classical Kullback-Leibler (KL) divergence that involves density ratios, the KKL compares probability distributions through covariance operators (embeddings) in a reproducible kernel Hilbert space (RKHS), and compute the Kullback-Leibler quantum divergence. 
This novel divergence hence shares parallel but different aspects with both the standard Kullback-Leibler between probability distributions and kernel embeddings metrics such as the maximum mean discrepancy. 
A limitation faced with the original KKL divergence is its inability to be defined for distributions with disjoint supports. To solve this problem, we propose in this paper a regularised variant that guarantees that divergence is well defined for all distributions. We derive bounds that quantify the deviation of the regularised KKL to the original one, as well as concentration bounds. 
In addition, we provide a closed-form expression for the regularised KKL, specifically applicable when the distributions consist of finite sets of points, which makes it implementable. 
Furthermore, we derive a Wasserstein gradient descent scheme of the KKL divergence in the case of discrete distributions, and study empirically its properties to transport a set of points to a target distribution.

Statistical and Geometrical Properties of Regularized Kernel Kullback-Leibler Divergence
Clémentine Chazal CREST, ENSAE, IP Paris
Anna Korba CREST, ENSAE, IP Paris
clementine. chazal@ensae. fr
kon.keobb@e
Francis Bach
INRIA Ecole Normale Supérieure
PSL Research university
francis bwch@inria.f.....
Abstract
In this paper, we study the statistical and geometrical properties of the Kullback- Leibler divergence with kernel covariance operators (KKL) introduced by Bach [2022]. Unlike the classical Kullback-Leible (KL) divergence that involves density ratios, the KKL compares probability distributions through covariance operators (embeddings) in reproducible kernel Hilbert space (RKHS), and compute the Kullback-Leibler quantum divergence. This novel divergence hence shares parallel but different aspects with both the standard Kullback- distributions and kernel embeddings metrics such as the maximum mean discrep- ancy. A limitation faced with the original KKL divergence is its inability be defined for distributions with disjoint supports. To solve this problem, we propose in this paper a regularized variant that guarantees that the divergence well defined for all distributions. We derive bounds that quantify the deviation of the regularized KKL to the original one, as well as saitee bounds. In addition, we provide a closed-form expression for the regularized KKL, specifically applicable when the distributions consist of finite sets of points, which makes it implementable. Fur- thermore, we derive Wasserstein gradient descent scheme of the KKL divergence in the case discrete distributions, and study empirically its properties transport set of points to a target distribution.
between probability
Introduction
A fundamental task in machine learning is to approximate target distribution q. For example, in Bayesian inference [Gelman et al. 1995]. it is of interest to approximate posterior distributions of the parameters of statistical model for predictive inference. This has led to the vast development of parametric methods from variational inference [Blei et al.] [017]] or non-parametric ones such as Markov Chain Monte Carlo (MCMC) [Roberts and Rosenthal 2004), and more recently particle- based optimization [Liu and Wang 2016 Korba et al. [021]] In generative modelling [Brock et al.)
2019 Ho et al. 2020 2 [Song al.) 2020 Franceschi
[023] only samples from q are available and the goal is to generate data whose distribution is similar to the training set distribution. Generally, this
problem can be cast as an optimization problem over P(R.). the space of probability distributions
over IRd, where the optimization objective is chosen or divergence) between probability distributions, that only vanishes at q. Starting from an initial distribution Po. descent scheme can then be applied such that the trajectory (pt) approaches g. In particular, on the space of probability distributions with bounded second moment P2 (RR), one
dissimilarity function D(-lq) distance
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

can consider the Wasserstein gradient flow of the functional F(p) = D(p) q). The latter defines a path of distributions, ruled by a velocity field, that of steepest descent for JF with respect to the Wasserstein-22 distance from optimal transport.
This approach has led large variety of algorithms based the choice of specific dissimilarity functional F, often determined by the information available on the target q. For example, in Bayesian or variational inference, where the target's density is known up an intractable normalizing constant, a common choice for the cost is the Kullback-Leibler (KL) divergence, whose optimization is tractable
in that setting [Wibisono] 2018 Ranganath et al. 2014]. When only samples of q are available, is not convenient to choose the optimization cost as the KL, as it is only defined for probability distributions p that are absolutely continuous with respect to 9. In contrast,
more convenient to choose an F that can be written as integrals against for instance, maximum mean discrepancy (MMD) [Arbll et al., 2019 Hertrich et al. 2024b), sliced- Wasssertenn distance [Liutkus et al. 2019] or Sinkhorn divergence (Genevay et al. 2018). However, Wareeddttssrsteiin distances, that average optimal transport distances of 1-dimensional projections of probability distributions (slices) over an infinite number of directions, have to be approximated by finite number of directions in practice TTnguyy et al.] 2023]: and Sinkhorn divergences involve solving a relaxed optimal transport problem. In contrast, MMD can be written in closed-form for discrete measures thanks to the reproducing property of positive definite kernels. The MMD represents probability distributions through their kernel mean embeddings in reproducing kemel Hilbert space (RKHS), and compute the RKHS norm of the difference of embeddings (namely, the witness function). Moreover, the MMD flow with smooth kernel (e.g., Gaussian) as in Arbel et al. [219]] is easy to implement, as the velocity field is expressed as the gradient of the witness function, and preserve discrete measures. However, due to the non-convexity of the MMD in the underlying Wasserstein geometry [Arbel et al. 2019), its gradient flow is often stuck in local minimas in practice even for simple target as Gaussian calling for adaptive schemes tuning the level of noise or kernel hyperparameters (Xu et al. 2022
Galashov et al. 2024), or regularizing the kernel [Chen et al. 2024). MMD with non-smooth kernels, e.g., based on negative distances (Sejdinovic al. 2013), , have also attracted attention recently, as their gradient flow enjoys better empirical convergence properties than the previous ones [Hertrich al. 20244ab b). However, their gradient flow does not preserve discrete measures; and their practical simulation rely on implicit time discretizations (Hertrich et al. 2024a] or slicing [Hertrich et al. 2024b].
In contrast to the MMD with smooth kernels, the KL divergence is displacement convex [Villani 2009. Definition 16.5] when the target is log-concave (i.e., q has density q e with V convex), and its gradient flow enjoys fast convergence when satisfies log-Sobolev inequality (Bakry et al. 2014). In this regard, it enjoys better geometrical properties than the MMD. Moreover, the KL divergence is equal to infinity for singular p and g, which makes its gradient flow extremely sensitive to mismatch of support, so that the flow enforees the concentration on the support of q as desired. On the downside, while the Wasserstein gradient flow of KL divergences is well-defined [Chewi et al., 2020). its associated particle-based discretization difficult simulate when only samples of q are available, and a surrogate optimization problem usually needs to be introduced [Gao et al. 2019 Ansari et al. 2020 Simons et al. 2022, Birrell et al., 2022a Liu et al. 2022 However, is unclear whether this surrogate optimization problem preserves the geometry of the KL flow.
Recently, Bach| [2022] introduced alternative divergences based on quantum divergences evaluated through kernel covariance operators, that we call here a kernel Kullback-Leibler (KKL) divergence. The latter can be seen as second-order embeddings of probability distributions, in contrast with first-order kernel mean embeddings (as used in MMD). In Bach 2022]. it was shown that the KKL enjoys nice properties such as separation of measures, and that it framed between a standard KL divergence (from above) and smoothed KL divergence (from below), i.c., a KL divergence between smoothed versions of the measures with respect to a specific smoothing kernel. Hence, it cannot directly be identified to a KL divergence and corresponds to a novel and distinct divergence. However, many of its properties remained unexplored, including a complete analysis of the KKL for empirical measures, tractable dlosed-form expression and its optimization properties. In this paper, we tackle the previous questions. We propose a regularized version of the KKL that is well-defined for any discrete measures, in contrast with the original KKL. We establish upper bounds that quantify the deviation of the regularized KKL to its unregularized counterpart, and convergence for empirical distributions. Morcover, derive tractable closed-fone ffom for the regularized KKL and its derivatives that writes with respect to kernel Gram matrices, leading to a practical optimization algorithm. Finally,
2

---

we investigate empirically the statistical properties of the regularized KKL, as well as its geometrical properties when using an objective target a probability distribution q.
This paper is organized as follows. Section 2 inttroduces the necessary background and the regularized KKT.. Section presents our theoretical results on the deviation and inite-sample properties of the latter. Section provides the closed-form of regularized KKL for discrete measures as well as the practical optimization scheme based on an explicit time-discretisation of its Wasserstein gradient flow. Section [ discusses closely related work including distances or divergences between distributions based on reproducing kernels. Finally, Section 6 iillustrates the statistical and optimization properties of the KKL on variety of experiments.
2 Regularized kernel Kullback-Leibler (KKL.) divergence
In this section, we state our notations and previous results on the (original) kernel Kullback-Leibler (KKL) divergence introduced by Bach [2022] before introducing our proposed regularized version.
Notations. Let P ((IR)) the set of probability measures on IR Let P2( the set of probability measures on Rd with finite second moment, which becomes a metric space when equipped with Wasserstein-2 (W2) distance [Villani 2009).
For p ((R)), we denote that p absolutely continuous w.r.t. g using p < q, and we use dp/ to denote the Radon-Nikodym derivative. We recall the standard definition of the Kullback-Leibler divergence, (pllg) = f log(dp/ dq)dp if < q. to0 else.
g R RR" is differentiable, we denote by Jg Rd + Rrdd its Jacobian. If r 1, we denote by Vg the gradient of and Hg its Hessian. If = d, V g denotes the divergence of i.e., the trace of the Jacobian. We also denote by Ag the Laplacian of g, where Ag = V Vg. We also denote T the identity matrix or operator.
For positive semi-definite kernel k IRd Rd R. its RKHS H is Hilbert space with inner product (-, 7) and norm || ||H. For E (2 such that I' ['(zzx)dq(() < 0o, the inclusion operator 6n 7 - (g), ( ~ f is a bounded operator with its adjoint being 1 L
(g) + H. / f ((()))))(( [Steinwart and Christmann 2008 Theorem 4.26 and 4.27]. The covariance operator w.r.t. is defined as Mn = k(. x) k( rz)((()) = Sgt where (a @ b)c = (b, caaa for a, b. c E H. It can also be written Σ, = fge (()) dq(x) where denotes the transposition in H. (recall that for E H. uar" H + H denotes the operator uu" (f) (f, u) z for any f E H).
Kernel Beobback-Leiblee divergence (KKT). For P,d E P((T)), the kernel Kullback-Leibler divergence (KKT.) is defined in Bach 2022 as:
Alog (?) (fx, 9-)
KKL()llg) (TE log Ep) Tr(E, log Eg)
Σ
(I)
(A.))A,XA,
where Ap and Ag are the set of eigenvalues of the covariance operators Σp and Eg. with associated eigenvectors (J^)AEA, and (0x)veA,- The KKT, ① evaluates the Kullbac--Leibler divergence between operators on Hilbert Spaces, that is well-defined for any couple of positive Hermitian operators with finite trace, at the operators E, and Egg From Bach [2022] Proposition 4), if p and q are supported on compact subset of Idd, and if I is a continuous positive definite kernel with k(xr,)) x)) = 1 for all x E R&d and if 122 is universal [Steinwart and Christmann, 2008| Definition 4.52), then (pL (q) = 0 if and only p q. In [achh [2022]. it also was proven that the KKL is upper bounded by the (standard) KI-ddiergennee between probability distributions (see Proposition therein) and lower bounded by the same KL but evaluated at smoothed versions of the distributions, where the smoothing is a convolution with respect to a specific kernel (see Section 4 therein). Thus, the KKL defines a novel divergence between probability measures. It defines then an interesting candidate as to compare probability distributions, for instance when used as an optimization objective over P (RR)), in order to approximate a target distribution
Definition of the regularized KKL.. A major issue that the KKT shares with the standard Kullhack- Leibler divergence between probability distributions, is that it diverges if the support of p is not
3

---

included in the one of q (. Indeed, for the KKL(pl (q) to be finite. we need Ker(Eg) C Ker(Ep) This condition is satisfied when the support of p is included in the support of q. Indeed, if f Ker(E.g) then (f, F h= = fea [(x)
0. and so f is zero the support of q, then also on the support of p. Hence, the KKT. not a convenient discrepancy when g is discrete measure (in particular, if is also discrete with different support than Q) A simple fix that we propose in this paper is to consider a regularized version KKL which is, for a eJ0, 1[,
KKLa (p) (g) = (KL(plI(1 - a + ap) = Tr(Ep Ep) - Tr(Ep log((1 - aJH, + aL,)). (2)
The advantage of this definition is that KKL is finite for any distribution p, q. It smoothes the distribution q by mixing it with the distribution p. to degree determined by the parameter a. This divergence approximates the original KKL divergence without requiring the distribution p to be absolutely continuous with respect to for finiteness. Moreover, for any eJ0, 1[, KKL (pl lg) and only if p q. As a - O, we recover the original KKT. and as a + 1, this quantity converges pointwise zero.
consider in 22) has also been considered for the standard KL divergence [eee| 2000]. These objects, as well as their symmetrized version, were also referred to in the literature skewed divergences [Kimura and Hino, 202T). The most famous one is Jensen- Shanmon divergence, recovered as a symmetrized skewed KL. divergence for a 2 JS(pllg) = KL(pI ppp + 1)) + KL(gll p + (1))
Remark 1.
The regularization
that is defined as
3 Skewness and concentration of the regularized KKL
In this section we study the skewness of the regularized KKT, due to the introduction of the parameter o, as well as its concentration properties for empirical measures.
Skewness. We will first analyze how the regularized KKL behaves with respect the regularization parameter a. First, we show is monotone with respect to a in the following Proposition.
Proposition 2. Let p & q. The function o + KKT, (pllg) is decreasing on [0, 1].
Proposition[Sshow that the regularized KKL shares similar monotony behavior than the regularized. or skewed, (standard) KI. between probability distributions, as recalled in Appendix A. The proof of Proposition can be found in Appendix B.T relies on the positivity of the KKT, divergence, and the use of the identity [Ando 1979
/ Tr( + - Tr + BT) 1))-
Tr(Ep(log Ep - log Egg)
(3)
where 7 is the identity operator, that is used in all our proofs. We now fix a ejo, 1 and provide a quantitative result about the deviation of the regularized (or skewed) KKL to its original counterpart.
Proposition 3. Let p. E P(RR). Assume that < q and that
dp < 1 ju for some μ > O. Then, dq
(KL,g( - (KTT()ll)) & (a(1 (1=1] + a
1
(22 )) Tr (Ep log En)
1
Proposition recooerss a similar quantitative bound than the one we can obtain for the standard KL between probability distributions, see Appendix [A.2] and state that the skewness of the regularized KKT. can be controlled by the regularization parameter a. especially when the latter small, However, the tools used derive this inequality are completely different by nature than for the KL case. Its complete proof can be found Appendix B.2 but we provide here a sketch.
Sketch of proof. =et atip + (1 a Mi. We write KKL(pll)), KKL(pllg) Tr 2p log M, Tr Σp log I' that we write as (3 In order to upper bound this integral we use the operator equalities, for two operators
and B, - B- A- B- = A-1(B A)A A A ++ 31 and B Σ. + BT. We then use the assumption
A)B-1(B - A)A-1 which we apply to A r J.E.p * Y. and carefully apply upper bounds on positive semi-definite operators, using the matrix inequality results from Appendix A.3 conclude the proof.

---

Statistical properties. We now focus on the regularized KKL for empirical measures and derive saite- guarantees.
dq H for some < μ & and let E 2. We remind that x(z) is the feature map of R in the RKHS H. Assume also that c= -o (uPpeR=(((())) ( (E,, +111) (/(3)=/a((()))))) ( is finite. Let p. q supported on n, m i..dd samples from p and q respectively. We have:
Proposition 4. Let p.q E P(RR). Assume that p & with dp <
35
BJKKLa - KKLa (plla))
& Vm A ou
(2Vo + log
mAn (1+ L
c(24logn)² (1
(5)
f
ax²
m m
possible calculate a similar bound for the above proposition which does not require the condition < This bound, which can be found at the end of Appendix B.3.3 worsens
Remark 5.
as a approaches 0 because scales in O 2[2 instead of ( above.
The latter proposition extends significantly Bach 2022 on the entropy term only, i.c., the first term
Proposition 7] that provided an upper bound
[ Tr<Ep log Ep) - log < 1 c(8logn))
17 vn
+ (2Vc logn).
(6)
Our bound 5 is explicit in the number of samples n, for and for
recover similar
terms as 6 Our contribution is to upper bound the cross term, i.c. the second term in (T). involving both p and g. We do so by closely follow the proof of [Bach] [022) Proposition 7] in order to bound the cross terms difference.
consequence, our proof involves technical intermediate results, among which concentration of sums of random self-adjoint operators, and estimation of degrees of freedom. The proof of Proposition 4 can be found in Appendix B.3 but we provide here a sketch.
Sketch of proof. We denote f = aIg + (1 - E.g and I its population counterpart. In order to bound the cross term we write Tr Ep log F Tr E, log I using 33). We split the integrals in three terms, with respect to two parameters 0 < 3g < B1 that we introduce: (a) one for 3 between 0 and 3g. (b) one for / between 31 and infinity and (c) intermediate one. The 30 quantity is chosen to be dependent of m and n, so that converge to zero as n and m go to infinity. This way, for (a) the integral between 0 and Bg we simply have to bound Tr Ep + 3I)- and Tr E,f + 33) - by constant or integrable quantities close to O. Then, for (b), 31 chosen that it goes infinity when n and m go to infinity and (b) is bounded by 1/3,. Finally we upper bound finely enough (c) to compensate for the fact that the bounds of the integrals tend towards 0 and infinity. [
4 Time-discretized regularized KKL gradient flow
In this section, we show that the regularized KKL can be implemented in closed-fon for discrete measures, well as its Wasserstein gradient, making its optimization tractable.
regularized KKL closed-form. We first describe how to compute the regularized KKL for (any, not necessarily empirical) discrete measures in practice. This will be useful for mentation of regularized KKL optimization coming next. We provide closed-form for the latter, involving kernel Gram matrices between supports of the discrete measures.
the practical imple-
Proposition Let P = Σ 82, and q = Ex= Sy two discrete distributions. Define Kµ = (kl(a, 2;)) )), == E Baxn, Kg = ()),, RRmm K (k(1,, Wimm E RRax. Then, for any E Ej0, 16, we have:
1 KKL, (pll Tr (1 Kglog K2)
Tr (olllg(())
n
11 0
0)
K
a(1-a)) nm
Kod
where Ta
and K
(7)
a(1-aa
K q.
I-a
K
5

---

Proposition 6 extends non-trivially the result of Bach [0022] Proposition 6] that only provided closed-form for the entropy term Tr<E, log(E,) Ex)) that corresponds to our first term in Equation 7
Its complete proof can be found in Appendix B.4 but we provide here sketch.
Sketch of proof. Our goal there is to derive a closed-form for the cross-term in p. 9 of the KKL., that is Tr(E,p Log(aE + (1 a)Eg)). ) It is based on the observation that if we define dx B, (f((1)) (o(yy)...... ..... ((ym))) and di the concatenation of / o2 and then the covariance operators write Σp L and aEpp + (1- a) = = Then, the matrices Kg and K write K3 Lh eh and u'r²" = K. Finally, we apply an intermediate result (Lemma 12 to obtain the expression of log(a Lo + (1 - a)>a)) as a function of log K.
m Pv.
Gradient flow and closed-form for the derivatives. We now discuss how to optimize p + <KLa(pll ()) for a given target distribution q. For a given functional F: P2( - RR, a Wasserstein gradient flow of F can be thought as an analog object to Euclidean gradient flow in the metric space (PR( W2) (Santabbrogio 2017], which defines a trajectory (Pr)e20 in (2( following the steepest descent for JF with respect to the W2 distance. It can be characterized by continuity equation:
Oep. + V (Pe =0,
(8)
where F((p): Rd - R is the first variation of F p p E (R)))). We recall that the first variation at p E (2 as defined in Ambrosio et al. (2005 Lemma 10.4.1] is defined, if it exists, as the function F² Rd + IR such that
lim 1 +0 C
= / F(()(x)dE(())
for any q E P2 ). To optimize KKL it is then natural to consider its Wasserstein P. gradient flow and discretize it in time and space. Since KKL is well-defined for discrete measures p. 9. we directly derive its first variation for this setting. Our next result yields a closed-form for the first variation of the regularized KKL.
Proposition 7. Consider & and the matrices Kp, K as defined in Proposition 6 Then, the first variation of F KKT, (-114) p is. for any Rdd
Let g(x)= logz
F())(x)= = 1+ g(x))(((()))))))))))))) ((x)))(x)) ( g(K)T(z) - -x(x)* AT(x),
(10)
where
(20 (1, 21)
1
k(z, 2n)) T(x)= - (v k(0,00)
1 m
k(I, a(c..r)....))
S(x)
Vn
Vn
and A ntm ||
log f1j
log tkk (aj, cxct
c
1=1 nj
n2 Th
where (cj) are the eigenvectors of K, and (az); the vectors first n terms (ct)r-
The proof of Proposition can be found in Appendix B.5 we provide a sketch below.
Sketch of proof. Our proof deals separately with the entropy and the cross term, writing F Fi Starting from the definition (,, we denote = eEg.. For Fi, we write Fi + aε) - Fi Σ (x, + A)) - (Ep)). To write this term, we use the residual formula, which can be used to differentiate eigenvalues of functions. Indeed, we can write, for an operator A with finite number of positive eigenvalues, ExEA(A) f(A) f, f(z) Tr - - A)-1)d dz where 7 is loop in C surrounding all the positive eigenvalues of A. Appllying this to our case, if we choose 7y such that it surrounds both the eigenvalues of Σgp and of ΣB + +4, we obtain En ((, + A)) fA,, =
2 f [() Tr((=/ - Σn- - -)-1) - f()) Tr (=xT xp) 1) dz. Using the identity A-1 B-1
A (B (B--A)A-++0 o[B A), the previous quantity becomes E (2, + A)) (A,(p)
f(2) 25 f Σズ ( dz Tr(fi fx + o(E). Under the integral we recognise holomorphic function
with isolated singularities and we can therefore apply the residue formula again. Concerning F2, we proceed the same way, with the difference that as we have a cross term, eigenvectors will appear in the calculation and in the final result.

---

Leveraging the analytical form for the first variation given by Proposition] 7 the Wasserstein gradient of F , at p is given by (F)( E= + R by taking the gradient with respect to x in Equation (TO) Notice that the latter only involves derivatives with respect to the kernel k. and can be computed ((n + m))) due to the singular value decomposition of the matrix K' defined in
Proposition 6
Starting from some initial distribution po. and for some given step-size y > a forward (or explicit) time-discretization of (8) corresponds to the Wasserstein gradient descent algorithm, and can be written each discrete time iteration 2 1 as:
Pt-1 (Id (id=vFF((pi)e:::
(11)
where Id is the identity map in (p)) and # denotes the pushforward operation. For discrete
measures Jrn = 1/m >i=1 Set, we can define F(X")= == F(p,) where X = (ar ..... x=" since the
functional F is well defined for discrete measures. The Wasserstein gradient flow of J (8) becomes
the standard Fuclidean gradient flow of the particle based function F. Furthermore, Wasserstein
gradient descent writes as Euclidean gradient descent on the position of the particles.
Related work
Divergences based on kermels embeddings. Kernels have been used extensively to design useful distances or divergences between probability distributions, as they provide several ways to represent probability distributions, e.g., through their kernel mean or covariance embeddings. The Maximum Mean Discrepancy (MMD) [Gretton et al., [0022) is maybe the most famous one. It is defined as the RKHS norm of the difference between the mean embeddings mp := f (ax, -)dp(z) and my := k( )dq (..)..................)) i.e. MMD g) mp myyle llay- When l is characteristic, MMD ()
if and only if = (Sriperumbudur et al. 2010 MMD belongs to the family of integral probability metries [Müller, 1997| as it can be written as MMD lg) sup supse..ll51 [xx)] - [
Alternatively, it can be seen as an 2 distance between kernel density estimators. It became popular in statistics and machine learning through its applications in two-sample test (Gretton et al. 2012]. or
more recently in generative modeling [Binkowski et al.) 2018).
However, kernel mean embeddings are not the only way (and maybe not the most expressive) to represent probability distributions. For instance, MMD may not be discriminative enough when the distributions differ only in their higher-order moments but have the same mean embedding, For this reason, several works have resorted to test statistics that incorporate the kernel covariance operator of the probability distributions. For instance, Harchaoui et al. (2007) construct test statistic that resembles and regularizes the MMD(pll9) by incorporating covariance operators (more precisely, [|EEtt 3I) (mmp (mp m,))lx) yielding in some sense chi-square divergence between the two
distributions. This work has been recently generalized in HHagrass et al. [2022] more general spectral regularizations, and in Chen et al. (2024) with a different covariance operator. A similar regularized MMD statistic employed by Balasubramanian et al. [2021] Hagrass et al. [2023 in the
context of the goodness-of-i test.
Kernel variational approximation of the KL. An alternative use of kernels to compute probability divergences is through approximation of variational formulations of f-divergences (Nguyen et al.) 2010 Birrell et al. 2022bb of which KL-divergence is an example. Indeed, the KL divergence between p and y writes sup
gdp- I' e dd where M, denotes the set of all bounded measurable functions on Rdd. For instance, Glaser et al. (202)) consider variational formulation of the KI. divergence restricted to RKHS functions, namely the KALE divergence:
/ gdp fedd- 11l -
(ALE(pp)g) = (1 + A) max
(12)
gEH
Recently, Neumayyr et al. 2024] extended the latter work and studied kernelized variational formula- tion of general f-divergences, referred to as Moreau envelopes of f-divergences in RKHS, including the KALE as particular case. They prove that these functionals are lower semi-continuous, and that their Wasserstein gradient flows are well defined for smooth kernels (i.e., the functionals are X-convex, and the subdifferential contains a single element). However, the KALE does not have closed form expression (in constrast to the kernelized variational formulation of chi-square, which writes
Decently,Neumayeer
7

---

regularized MMD, see (Chen et al., 2024)). )) For discrete distributions and supported on atoms, the KALE divergence can be written a strongly convex n-dimensional problem. and can be solved using standard Fuclidean optimization methods. Still, this makes the simulation of KALE Wasserstein gradient flow (e-g., gradient descent on the positions of particles) computationally demanding, as requires solving an inner optimization problem at each iteration. This inner optimization problem solved calling another optimization algorithm. Glaser et al. [202]] use various methods in their experiments, including Newton's 's method (that scales as ( due to the matrix inversion), computationally demanding ones such as gradient descent (GD) or coordinate descent. For large values of the regularization parameter X, using plain GD works reasonably well, but for small values of X, the problem becomes quite ill-condttioned and GD needs to be run with smaller step-sizes. Moreover, KALE (and its gradient) not available in closed-form. they cannot be used with fast and hyperparameter-ffer methods, such as L-BFGS [Liu and Nocedal 1989) which requires exact gradients. This contrasts with regularized KKL divergence and its gradient, which are available in clomed-form. In our experiments, we will investigate further the relative performance of KALE and KKI.
less
6 Experiments
In this section, we illustrate the validity of our theoretical results and the performance of gradient descent for the regularized KKL. In all our experiments, we consider Gaussian kernels k(r, y) = | yl=
exp
where denotes the bandwith. Our code is available on the github repository
https: //gg://iiin github.... coom//ceementinechaeee BatpaaaaalKKKL-iiiiaa /ive- gradient-flen git
Illustrations of skewness and concentration of the KKI. We first illustrate our results of Proposi- tion[Jand Proposition 4 i.e. the skewness and con- centration properties of KKL., We investigate these properties for various settings of p, q two fixed prob- ability distributions on Rdd varying the choice of o, dimension d, and distributions p. q. We consider em- pirical measures p. 9 supported on n i.i.d. samples of p, q (in this section take the same number of samples for both distributions, i.c., n = m in the notations of Section 3). and observe the concen- tration of KKL, (f. 9) around its population limit as the number of samples (particles) go infinity.
8
1c:05
a= 0,0001
(6)1))
0,001
a= 0.01
0.5
2
0.
250
500
750
1000
number of particules
Figure Concentration of empirical KKT,, for d = 10, = 10, p.g q Gaussians.
Each time, we plot the results obtained over 50 runs, randomizing the samples drawn from each distribu- tion. Thick lines represent the average value over these multiple runs. We represent the dependence in a and n in dimension 10 in Figure [ for p. q anisotropic Gaussian distributions with different means and variances. Alternttiv settings and additional results are deferred to the Appendix C such as different distributions (e.g. a Gaussian p versus an Exponential ④) as well as the dimension dependence for fixed a. We can clearly see in Figure T the monotony of KKL with respect to a (as stated in Proposition[2) and the concentration of the empirical KKL around its population version, which happens faster for larger value of a, predicted by our finite-sample bounds in Proposition
Sampling with KKL gradient descent. Finally, study the performance of KKL gradient descent in practice, as described in Section 4 We consider two settings already used by Glaser et al. [02T for KALE gradient flow, reflecting different topological properties for the souree-target pair: pair with a target supported on hypersurface (zero volume support) and a pair with disjoint supports of positive volume. Alternative settings, e.g. Gaussians source and mixture of Gaussians target that are pairs of distributions with positive density supported on Rd are deferred to Appendix C We also report there additional plots related to the experiments of this section.
We have treated a as a hyperparameter here, and in this section for simplicity of notations we refer to KKL as the objective functional. As both KKL and its gradient can be explicitly computed, one can
8

---

implement descent either using a constant step-size, or through quasi-Newton algorithm such as L-BFGS (Liu and Nocedal 1989.. The latter is often faster and more robust than the conventional gradient descent and does not require choosing critical hyper-parameters, such as a learning rate, since L.-BFGS performs a line-search to find suitable step-sizes. It only requires a tolerance parameter on the norm of the gradient, which is in practice set to machine precision. In contrast, as said in the previous section, the KALE and its gradient are not available in closed-form.
The first example is a target distribution supported (and uniformly distributed) on a lower- dimensional surface that defines three non-overlapping rings, see Figure 2 The initial source is a Gaussian distribution with a mean in the vicinity of the target 9. We compare Wasserstein gradient descent of KKL, Maximum Mean Discrepancy [Arbel al. 2019] and KALE [Glaser et al., 2021] using the code provided in these references. For each method. we choose bandwith σ 0.1. and we optimize the step-size for each method, and sample n 100 points from the source and target distribution. Our method is robust to the choice of a and generally performs very well on this example, as shown in Figure 2 We can notice that since MMD not sensitive to the difference of support between and q, the particles may leave the rings; while for the regularized KKL flow, as for KALE flow, the particles follow closely the support of the target distribution.
The second example consists of source and target pair p: q that are supported on disjoint subsets, each with finite, positive volume, in contrast with the previous example. The source and the target are uniform supported on heart and a spiral respectively. We again run MMD, KALE and KKL gradient descent. In this example, both KKL and KALE recover the spiral shape, much before the MMD flow trajectory; but both have a harder time recovering outliers, disconnected from the main support of the spiral.
T=30
T=60
T-10
T-30
T-60
T-39
MMD
O
MMD
KKL
000
KXL
Figure 2: MMD, KALE and KKL flow for 3 rings target.
Figure 3: Shape transfer
7 Conclusion
In this work, we investigated the properties of the recently introduced Kernel Kullback-Leibler (KKL) divergence tool for comparing probability distributions. We provided several theoretical results, among which quantitative bounds on the deviation from the regularized KKL to the original one, and finite-sample guarantees for empirical measures, that are validated by our numerical experiments. We also derived a closed-form and computable expression for the regularized KKL as well as its derivatives, enabling implement (Wasserstein) gradient descent for this objective. Our experiments validate the use of KKL as a tool to compare discrete measures, as its gradient flow is much better behaved than the one of Maximum Mean Discrepancy which relies only on mean (first moments) embeddings of probability distributions. It can also be computed in closed-form, in contrast to the KALE divergence introduced recently in the literature, and can benefi from fast and hyperparameter- free methods such as L-BFGS.
While our study has advanced understanding of the KKL divergence, several limitations must be acknowledged. Firstly, theoretical guarantees for the convergence of the KKL flow remain unestab- lished. Secondly, reducing the computational cost crucial for practical applications. Investigating the use of random features presents a promising avenue for making the computations more efficient.
8 Acknowledgments
A. Korba and C. Chazal acknowledge the support of ANR PEPR PDE-AI.
9

---

References
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Springer Science & Business Media, 2005.
Tsuyoshi Ando. Concavity of certain maps on positive definite matrices and applications to hadamard products. Linear Algebra and its Applications, 26:203-241, 1979.
Abdul Fatir Ansari, Ming Liang Ang, and Harold Soh. Refining deep generative models via discrimi- nator gradient flow. arXiv preprint arXiv:20/2.00778 2020.
Michael Arbel, Anna Korba, Adil Salim, and Arthur Gretton. Maximum mean discrepancy gradient flow. Advances in Neural Information Processing Systems, 32, 2019.
Francis Bach. Information theory with kernel methods. IEEE Transactions on Information Theory, 69(2):752-775, 2022.
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and Geometry of Markov Diffusion Operators, volume 103. Springer, 2014.
Krishnakumar Balasubramanian, Tong Li, and Ming Yuan, On the optimality of kernel-embedding based goodness-of-ff tests. Journal of Machine Learning Research, 22(1):1-45, 2021.
Rajendra Bhatia. Positive Definite Matrices. Princeton University Press, 2009.
Mikotaj Biñkowski, Danica Sutherland, Michael Arbel, and Arthur Gretton. Demystifying MMD gans. International Conference on Learning Representations (ICLR). 2018.
Jeremiah Birrell, Paul Dupuis, Markos A Katsoulakis, Yannis Pantazis, and Luc Rey-Bellet. (ggamma)-divergenees Interpolating between f-divergences and integral probability metrics. Journal of Machine Learning Research, 23(39):1-70, 2022a.
Jeremiah Birrell, Markos A Katsoulakis, and Yannis Pantazis. Optimizing variational representations of divergences and accelerating their statistical estimation. IEEE Transactions on Information Theory, 68(7):4553-455) 2022b.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational Inference: A Review for Statisticians. Journal of the American statistical Association, 1125518):559-877, 2017.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale GAN training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2019.
Zonghao Chen, Aratrika Mustafi, Pierre Glaser, Anna Korba, Arthur Gretton, and Bharath K Stiperumbudur. -eee-laggl maximum mean discrepancy gradient flow. arXiv preprint arXiv:2409. 14980, 2024.
Sinho Chewi, Thibaut Le Gouic, Chen Lu, Tyler Maunu, and Philippe Rigollet. SVGD kerne-- ized Wasserstein gradient flow of the chi-squared divergence. Advances in Neural Information Processing Systems, 0122098-2109) 2020.
Jean- Jean-Yves Franceschi, Mike Gartrell, Ludovic Dos Santos, Thibaut Issenhuth, Emmanuel de Bézenac, Mickaël Chen, and Alain Rakotomamonjy. Unifying GANs and score-based diffusion generative particle models. arXiv preprint arXiv:2305.16150 2023.
Alexandre Galashov, Valentin de Bortoli. and Arthur Gretton. Deep MMD gradient flow without adversarial training. arXiv preprint arXiv:2405.06780, 2024.
Yuan Gao, Yuling Jiao, Yang Wang, Yao Wang, Can Yang, and Shunkang Zhang. Deep generative learning via variational gradient flow. In International Conference on Machine Learning, pages 2093-2101 PMLR, 2019.
Andrew Gelman, John B. Carlin, Hal Stern, and Donald B. Rubin. Bayesian data analysis. Chapman and Hal//CRC, 1995.
10

---

Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning generative models with Sinkhorn divergences. In International Conference on Artificial Intelligence and Statisties, pages 1608-1617. 2018.
Pierre Glaser, Michael Arbel, and Arthur Gretton. KALE flow: A relaxed KL gradient flow for probabilities with disjoint support. Advances in Neural Information Processing Systems, 34: 8018-8031, 2021.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Omar Hagrass, Bharath K. Sriperumbudur, and Bing Li. Spectral regularized kernel two-sample tests. arXiv preprini arXi::2212.092011 2022.
Omar Hagrass, Bharath K. Sriperumbudur, and Bing Li. Spectral regularized kernel goodness-of tests, 2023.
Zaid Harchaoui, Francis Bach, and Eric Moulines. Testing for homogeneity with kernel Fisher discriminant analysis. Advances in Neural Information Processing Systems, 20, 2007.
Johannes Hertrich, Manuel Gräf, Robert Beinert, and Gabriele Steidl. Wasserstein steepest descent flows of discrepancies with Riesz kernels. Journal of Mathematical Analysis and Applications, 531(1): 2024a.
Johannes Hertrich, Christian Wald, Fabian Altekrüger, and Paul Hagemann. Generative sliced MMD flows with Riesz kernels. International Conference on Learning Representations, 2024b.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pages 6840-6855 2020.
Masanari Kimura and Hideitsu Hino. a-geodesical skew divergence. Entropy, 23(5):528, 2021.
Anna Korba, Pierre-Cyri Aubin-Frankooski. Szymon Majewski, and Pierre Ablin. Kernel Stein discrepancy descent. In International Conference on Machine Learning, pages 5719-5730, 2021.
Lillian Lee. Measures of distributional similarity. arXiv preprint cs/0001012, 2000.
Dong Liu and Jorge Nocedal. the limited memory BFGS method for large scale optimization.
Mathematical programming, 45(1-3):503-528, 1989.
Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose Bayesian inference algorithm. Advances in Neural Information Processing Systems, 29, 2016.
Song Liu, Jiahao Yu, Jack Simons, Mingxuan Yi, and Mark Beaumont. Minimizing f-divergences by interpolating velocity fields. arXiv preprint arXiv:23055 15577, 2022.
Antoine Liutkus, Umut Simsekli, Szymon Majewski, Alain Durmus, and Fabian-Robert Stöter.
Sliced-Wasserstedd flows: Nonparametric generative modeling via optimal transport and diffusions. In International Conference on Machine Learning, pages 4104-4113, 2019.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429 443, 1997.
Sebastian Neumayer, Viktor Stein, and Gabriele Steidl. Wasserstein gradient flows for Moreau envelopes of f-divergences in reproducing kernel hilbert spaces. arXiv preprint arX1v:2402.04613, 2024.
XuanLong Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56( 36(11):584755811 2010.
Rajesh Ranganath, Sean Gerrish, and David Blei. Black box variational inference. In Artificial Intelligence and Statistics, pages 814-822. PMLR, 2014.

---

Gareth O. Roberts and Jeffrey S Rosenthal. General state space Markov chains and MCMC algorithms. Probability Surveys, 1:20-71, 2004.
Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. Advances in Neural Information Processing Systems, 30, 2017.
Filippo Santambrogio. (Euclidean, metric, and Wasserstein) gradient flows: An overview. Bulletin of Mathematical Sciences, 7:87-154, 2017.
Dino Sejdinovie, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu. Equivalence of distance-based and RKHS AKHSd-baeed statistics in hypothesis testing. The Annals of Statistics, 41(5): 2263 2291, 2013.
Jack Simons, Song Liu, and Mark Beaumont. Variational likelihood-free free gradient descent. In Fourth Symposium on Advances Approximate Bayesian Inference, 2022.
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13356, 2020.
Bharath K Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert RG Lanckriet. Hilbert space embeddings and metries on probability measures. The Journal Machine Learning Research, 11:1517-1561, 2010.
Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer Science & Business Media, 2008.
Eloi Tanguy, Rémi Flamary, and Julie Delon. Properties of discrete Sliced Wasserstein losses. arXiv preprint arXiv:2307. arX1v:2307.10352, 2023.
Cédric Villani. Optimal Transport: Old and New, volume 338. Springer, 2009.
Andre Wibisono. Sampling optimization in the space of measures: The Langevin dynamics composite optimization problem. In Conference on Learning Theory, pages 2093-3027. PMLR, 2018.
Lantian Xu, Anna Korba, and Dejan Slepcev. Accurate quantization of measures via interacting bartecle-based optimization. In International Conference on Machine Learning, pages 24576- 24595, 2022.
12

---

A Additional Background
A.1 Monotonicity of the KLa divergence
Proposition 8. The function KT[(pllpp + (1) is decreasing on [0, 1].
Proof. Let 0 < a' <a 1.
KL(pllap + (1 (1-))q) (1
(log(1 + a' - d)) - log(4 + -(p--(pp))))))) d))
/ (log(a+ + d' (p 4)) loglo + -ap-aapp-((())e)) (add (1 a)dg)
+ (1 (1 n)) (log(1 + a' 9)) - log(4 a(p ()) - dq)
We have f(log(a a 4)) log(4 a(p- (adp (1- a)dg) KL(ap (1 (1 a)g)lla'p+
d')g) & O. For the second term, note that because of the increasing nature
of the log, for the points for which p - q > O, log(g + a'(p q)) & log(g + a(p q)) and vice versa. Hence
(1 foosl + a'pp- - 4) - log(a + alp (d)) dg) & 0.
This concludes the proof.
A.2 Skewness of the KL, divergence
Proposition 9. Suppose that dp/dg < +
KL(pllap + (1 (1- a)g) KL(pllg)] < aa (1+
+ + a² 1 p2 ))/
log qdp
p 1-a
Proof. First, we have
/ /[log loglq + a(p q))) dp.
[L(pp|ap + (1 a)4) KL(pplg)
Now, we remind the following identity which is the real-valued analog of Equation 33) Let x. y > 0.
log logy (--
(
1
1
V+B
d3.
x
x
Hence,
l - loglg + a(p 9)) =
d3
1 + a(p () +
a+1 3
+00
(q+3)2
(q ( -)
(1 B) (++))(a+afs q) 3)
d3
(9 8)2(g + a(p q) + 3)
-alp - () 9)
d3
(q+ a(p +)+
-ap(p-)²²- - aap- (g a q) + 3)
d3
(g 2 + a(p 9) +
a
+oo
(p- (p-q) q
2
1
d3
p- g d3.
q 9
g + alp 9) +
J0
(g 8)2
(13)
13

---

The first term in 13 can be bounded as
to0
a
(q
p q
+ 3)2
d3
Sa
(9 8)+
p
d3 +a
o
() 3)2 d3
q
00
too
1
a 0 Mly 3)
d3 +
d3
(q+
a - +1+1
log q-
where the penultimate inequality uses po for the first term. The second term in 13 can be bounded similarly as:
p P-9 2
1
p² +
d3 & a²
(q+ 3)2 q a 3 + alp g) d3
a 3 + +alp 9)
2
+
log
1 - a
4
Finally,
Kppp a))) KL(Pllg)] < @ (0(1+1)
a²
(1 |
)) log dp.
+
p
- a
A.3 Background operator monotony
We recall here results about matrix and operator monotony, that we extensively use in all our proofs. These matrix- matrix-monotony and convexity/ see [Bhatia] 2009 for more complete reference. For 2 operators A and B in H. we denote A < B the operators inequality in the sense Vz H. xx Ax & x² Br. Let S being the set of symmetric operators and S the set of symmetric positive operators. We have
set out in the blog post https://frandisaachc com/
i) If A, B E S,X another operator in H, A & B = X XXB.
ii) If A, B, M 0, A B = TrAMM) Tr(BM).
iii) If B is invertible, A B = B 1/2 AB 1/2 I
iv) If B S, B = BB" I.
v) A, S A A //2 & B1/2
vi) If S and are invertible, A x B B-1 & AA-
B Proofs
B.1 Proof of Proposition 2
Let 0 < a' < a. We have:
KKLa - KKLxg(P))))
= =Tr Ep log (E, + a' (E,, - En)) Tr log + - -Eg)
= =Tr (aE, + (1 a)E,) log (E, + a' aEE - Eg)) - Tr + (1 -
a)).)) (1-a)En)
log (En + a Eg))
+ (1 a) Tr(E, - Egy) [log(2 + a - Eg)) - log + a(E Eyy)]-
(14)
For the first term in 14 we recognize
Tr + (1 a)E log + a' a'E TT)) + +1- log + a(E En))
= -KKKL (1 (0ggaa)gll/p a')g) <
14

---

For the second term in 14 we write
(1-a) a) Tr(E,- - Eg) [oogE a' - mn) loggEE + a - En]]
=(1- 0)
Tr(Ep- mg) (E + 3T + a - (Eg + + + a' - =g)) dB
-(1 a)(a' aax
I. Tr(Ep- -
+ 3I aZ +
Eg))
- Eg)(E + 3I+ - ds.
where the last equality uses (AX)" AX, where A = (2ig + 31 + a(Z, - -E,) and X = Σn Mgg hence it is positive. Then, knowing that - a))(aa - a) & O. we conclude that the second term in (I4) negative. Finally,
- A A)B-1 The term under the integral writes as
KKL. (vllg) KKL. (pllg) < O.
B.2 Proof of Proposition
This proof makes repeated use of the results about matrix monotony, some of which we recall in Appendix A.3 The reader may refer to Appendix A.2 for analog computations in the KL case. We
denote 1 = a + (1 a)M; = En + a('p 2.). We write using direct integration [Ano 1979
KKL(Pllg) KKLa = Tr Ep log Eg- -r Iog
(Tr + - +
Tr
+1) d3
Tr Tr (Eg + +1) - (Eg - Ep) + 31) -d3
a
+00
2
- - 2p) + - - Ex) + + ds Tr (2, + +1) (E,
= (a) - (b).
We will first upper bound (a) in absolute value, since it is not necessarily positive. We first bound
1 (Eg + 81)-1,
(Eg (1) =1) + * (Eg BT) and (Eg BT) Ex(( + (1) &
where we used for the second term the matrix inequalities E, ক 1 # S.. Hence, we have
Th + - + (E, - Ep)(En + -1) E
Tr ",, Tr 1E (1) + B1) 2
< Tp (Eg + +111) - T (I, + 31)
= (1+ Tr E -T)
We can then upper bound [(a) as:
a Ex + 31) 1 +2) d3 <a (1+ |r Mp
1T log Eg
We now turn to (b) which we can upper bound without absolute value since it is positive term. Since I' > (1 - a) a E [0, 1) and we are dealing with p.s.d. operators, we can bound the inverse
as (T + B1)-1 & - (Z. + - ( + -3) and so, using Tr(AM) S Tr(BM) for
A < B and M >> O, we have:
Tr Tr (E + (T) (E, - -,,
1
Tr (E, + +1) Ep,(E, + B1) - -Ep)(E, + 31)
a
15

---

We will split the r.h.s. of the previous inequality in four terms, involving twice Egg. two cross terms (bounded similarly) with pp En and twice Sp. We have for the first one:
Tr 2 (2, + B1) ",, + 111 (2 + 31) 31) 2ー
< Tr 2 (2, + +111 22 + 31) 311-
Tr E + -11
For the cross-term we have:
Tr (2ig + 31) 31) + -1) 22 + + <0.
and for the last we have:
1 1 TrEp(E. + B1)
31) +11) Tr Ep + 31) "E))"EE (1) 21)
Finally, combining our bounds for the terms in (b) and integrating with respect to 8, get
a²
Tr Tp + B1i [T + 31) 22) + +B
a²
1 - 1+ 42
Tr Ep log Eg.
Adding the bounds on (a) and (b) concludes the proof.
B.3 Proof of Proposition
B.3.1 Intermediate result 1: Concentration of sums of random self-adjoint operators
Lemma 10. Assume the conditions of Proposition hold. Denote f aL - ax) ox) and I' its population counterpart. Let 3 > 0, D (T 31) =(' [)([ + B1) and ((3)
(((x)) (Ep + 31) ((())) Then. for 1
((Amax(D) > u) & 0()) 1+
48
C(3)
(-(m A n)u² 8( (8(CL))
um(m An)
+
6
exp
C1.)
+ 4)
where Amax D) is the maximal eigenvalue of (D2)1/2.
Proof. Denoting
X; = (T
and Y, = (T + )(0)))))))) ++)
we have +1'+ -1-+ = B[X]. (T' + -1)-1 -1) E| and so + (1 aY]] We can thus write
+ -1) 31)
- -/
D = (X - E[X]) + a 2 (Y, E(Y]) 1=1
However, for two operators A and we have ||A + Bllop Amaz A + B) & Xmax (A) ()= + Amax (B). Then,
& || + ||B| which means that
Amax (D) & Amax
Σ 1=1
ax, E[ax]] + Amax
1 Σ
(1 a)Y, - -E[(1
=((1-a))1) ))r1)
which is equivalent to
(a(T+ - (p)(T++31)
Amax (D) < Amaa
Amax (11 -1-aa) a) + 31) - Ex)( + B1)
16

---

The quantities Amax (Dp) Amax (a(T + +1) (Ep Ep)(T + 31) $) and Amax (D₂)
-1)-
Amax (11 (1- + 31) 1 (Eeg - En + 31) are positive so
IP (Amaxx ()) > u) x PP Xmaax (Dp) > ) + +P (Amax (D₂) > 2)
Then Bach 2022
Lemma 2] can be applied twice to ((xx) va(l" + 11) 81)-1/2pp(x) and to ((v)= (11 (T (11)-1122((0))
For the term with Dy.
[+(2) = [V + 111-3111 pxx)) alf(x), (T (1) ((1)
(f((r, + B1) ((())) & C(B), where we used r >> pp and define C(3) = sup (f(x), + inequality, also obtain
+ 31) (()) Using the same
1/2 Tr(I' + (1) aL,, (T' -12 Tr(x, + 31) -1)) +11 31)
= -11 31)
f (0(00) + +131 x & C((),
and
Amaz ((T + -1) 1/2 aT + 31) 1/3) = ([ + 1-111)112200
1/2 aE, + 111--1112 1/2 1lop $ 1.
Then,
P Amax (Dp)
4 5 < C(3)
(1+
u'n² ((33) + )) exp (T8(C(9) + x)
48
2)
nu²
For the term with Dg. using the matrix inequalities r (1 ax and Eg 1 with similar computations we get
| < - C(O), Tr(T +1) (1-))) 31)-1/2 < C(B),
and Amax
-1/2 - aT + 31) -12-1 1 ( + 31)-
(T+
Then,
P AAmax (D₂)
C(3)
48
C(3)
+ u
mu²
2
1
u'm
/
exp
8( C(e)
+
We can combine both results on Dp and D, and use μ < 1 to get
2 C(B) 1+ 48
((3)
+ "
(m A n)u
IP (Amax (D) > u) & P
exp
um n)2
6
8 C(8) 2
B.3.2 Intermediate result 2: Degrees of freedom estimation
The Proposition below adapts the proof of Bach 2022 between the empirical covariance operators p and op + (1 -ag..
Proposition 15] to bound the cross terms
Proposition 11 (Estimation of skewed degrees of freedom). Assume the conditions of Proposition
hold. Denote F = aLip + a1-a) and I' its population counterpart. We have:
E
Tr Tr Tr Ep (1) -
(p + 31)
12 opp
m A T6C(3B)
6
(=+11
[1
28
(1 -
1)
n exp
C(B)
C(B).
(15)
/
m
ap?
n
m
where C(B) supeER (p(x), (E, + (.) (=-))((=))) is supposed to be inferior ((mAn)
17

---

Proof. We will denote
A
31)
= -r - +1)
Tr Tr B1) - f +1)
(16)
In expectation, the first term in 16 can be upper-bounded follows, using that Tr(( - Ep](I'+ + -111) is the sum of zero-mean random variables:
(T ET)(T 31)
Bl(p(z), (T + (1++)))))(())8
Blip(a), (Ep + u(1 a) 1) 1)- (x))
111 a) V
C' C
B
11 11(11 -a)
101 a)
1 n2
C(B),
(17)
where the third inequality uses r > (1 11-a- a)E > 1( Ep and the fourth uses the definition of C(3) for 0. The last inequality is due to the facts that < 1 and 1 < and also that μ < 1
2 I-a
So
9 p(I-a) > 3 and because B + C' is non increasing on J0, +oo%, we have C' (
C(3).
These simplifications are used many times in this proof.
The second term in (16) can be written follows. Consider D (T'+ + 31) -1)- TT 31)
defined in Lemma 10 and consider the case where Amaz (D) < < 1. Then D < I. Using the
identity D(I D) D(I D) (D D), the proof of [Rudi and Rosasco 2017]. can write
B = Tr +1) + 31)
Tr (T 31) DD B1)
TT + (()+++)+++++)))0) - D(T
-)) D) -I- +8))+ + Tr (T + -1)-2. (18)
We have for the first term in 18 using f > aEp:
Tr (r+
T
3p -
a
and, by the definition of above.
-Amax x (T + 31) - + 31) x Amax(D))
where Amaxe (D) is the absolute value of the maximal eigenvalue of (D2) So
(T -1+ + B1) & (Amax (D) + 1)I.
(19)
this case,
1 Dr - + -1- DD < 1 Amax (D) Tr D.
(20)
a
a
18

---

Still considering that Amax (D) < 1 we have for the second term in (88
Tr (T + BT) DI D D(T + 33)
[[T + ( Tr(D(I--D)
+ Amax (D)
- (D Tr D2
Amax (
Dr
(21)
a(1 - Amax (D)
where in the second inequality we used Eg < f and 19 Let < u < 1. Combining
17
20
and 21 we have:
|A| (m)a + 11 (D)G
1 1+
Tr Dr + 1+
1
(Dsaa)) + (D)E
DD + V n
ax11 - 11)
a
+ u
1 Tr Tr D2
2 V
< 1 Axmax (D)>al Al
C(B).
(22)
a(1 u)
a
We now bound the first term of 22 by upperbounding, going back to the formula given in [6. Using
I' > a(1-a) the term Tr p, -1) is bounded by mi-a0 C
<
by
hypothesis. And with > a 2.p. we have both Tr Tr + 31) < 2 Tr
(2ip
+ < _ and
Tr (T < [T-a)p C(3) & 2 (3) & nAm
Then, almost surely, |A| & max
n
nAm
<
12
12
2m Then, 22
becomes:
2n
1 a(1 - u)
1+ TrD
T2
B|A|
P(Amax (D)
u)
+
E
Dr +
+ V nn
C(B)
With Lemma 10 we have
2
48
C(3)
u
(m A n)u²
P P(Amax (D)
<
1+
w A An)
6
exp
8( C(9)
Using the hypothesis that C(B) < u(nAm)
24
4n
48
M An
+ m)²
2)
(m A nz)2²
E
E
p.c
C(B)
1
u
(m A ))
exp
8( C(9)
+ )
#
+
2
Tr D2
Tr
+
C(B).
(23)
aa(1
- u)
a
n
We now turn to bounding T[ D). We have
T < V [[ BI) - f) + -1) $
(24)
and denoting
X; = Tr(T + + (())) + 3
Y, Tr( + 31) 2 (w) (T + 81) 3
we have
a
E
+ - -
E
E X
X₂)
(E[X] Xx)]
n
i
(1 a)- m
aa1
a)
Y (E
1i)
E[[[ X.) -Y))
m
nm
11=1
19

---

The variables X1. Xn, ,,...,
..., Ym are independent so we get
B[[Tr([T+ + 31) $ (T (T +
2
a²
"
E x a1=a)²
a(1 - a)
"
Σ
EYyY
Σ F[
n²
m²
nm
M==1
1,=1
a² (n - B[X +
a1
(1
) 1) E
B[X²1
B 21
m
m
+ 2a(1 -a)-a)))66) [)
a²
(AE (B|X²) - - + (1 a1= (E|Y - - (aE + + (1-
a² Var[X]
(1 a1= Var[Y].
n
m
The last equality is due to Blaxp(x))(()) + -11-0))(0) = 0. We have
Var[X] = Var Tr( + 31) (r=)(((o()))())))0)00000 + 31) $
= + Varl (1) (T))) }]
< B[ + ((0))))))) (I) -
[l((((()), (T (T)
and the equivalent inequality also verified for Y. Then,
[[ + 31) à (r - P) + 21) +)
a² Blp((x), (L' +
(1 (1-a)² a)²
B((p(y), (T' + (
m
+ [
3
+ 1
)C
C(B)
12(1 a)
11(1 a))
m
8o we 24
becomes
2
1
1
E
DJ
&
V
+
C(3).
1
n
m
Using similar calculations, we obtain
4
1
Tr D
C(B)2
112
n
m
Finally, 23 becomes
n (1
48
m A n
u 2
(m A n)uu
E|A < aj
um(mm A An2
24
+
6
exp
8( C(3)
+ (
C(3)
+ 1 + u
| + m
1
1 1+
2 C(B).
ax1 1 u) n²
C(3)2 +
V
+ m
+
Taking u= = 3
4 we get the final bound
160
m A n
1
2
9(m nz)
E|A <
aj
n
1
+
(m A
24
+
exp
16(8
C10) + +1)
C(3)
28
1
11
1
+
C(B)
+
V
+ m
C(B)
app
n
m
2/
aj
12
n cxp
-H
m n 166((3)
+ 6
V
1
+ m
_
C(B) +
a4²
28 (1 (1+
+ m
c(3).. -
20

---

B.3.3
Final proof of Proposition
From
Bach
2022
Proposition 7] we already have a bound on the entropy term:
+ c(8 c))
17
E
Tr log
Tr(Ep log Ep)ll
Vn (2Vc + logn).
(25)
T2
In the following we will closely follow the proof of [Bach, 2022 Proposition 7] in order to bound the
cross terms difference. We can write with the integral representation Bach [002] (Eq 5),
-Tr--rr Tr 2p log - Tr log
(T+ Tr 'd.
We will treat separately the integral part close to infinity, the one close zero and the central part. Let B1 > 30 > O. From 31 to infinity we have
Tr (T+ - Ex 31) Tr Ep log (f + +B11) Ep log(( + B11)
1
log(1 + +1) log 31 & 31
From 0 to Bo we have
80
Tr Ep + -1)-1118
<
Tr
- ((1=)((1)))),, + +11
30
3
TF 2 C2p +
1)
111 a)
J
111
%
18
2 10
2
sup (p(x), (Eip M(1 w(1-a) 1) 1) (()))
C(3)d3,
P11 a)
#ERU
1
where C(3) = SuPpER (f(xx, (Ep -)))) ø. We also have
(f + 31) d8 & / Tr + 31) &
1 -n30
By Proposition
we have
E Tr Eg log f
Tr Σp log
1
//m %
n430
C(3)d8 +
Tr Tr log
Tr log l'd3
131
a
9o
1
-npBu=
30
C(B)dB +
12
12 exp
m An -M T6C(3b)
6 P
_
1
f So
C(B)dB
pr3
a
J
arp
28
[-+1)
1
1
91
C(3)243.
apt
m
3o
We now take So such that C(B)) = 24 log(n). The function B + C(3) being non-increasing
nAm
J0, oof, the condition of Proposition
which is C(B)
((mAn)) is well satisfied between Bg and
24
31 for this choice of Sp. We then have
12 n exp -H4 16C(()))
An
12 n1 exp
24
12
12 1 ap
aj
<
16
16
log(n)
Vn
n
m
and also, g C(3)2d3 & c. Then,
1
1
80
EJ Tr Log i - Tr Ep log Il <
+
nnp30
+
C(3)d3
1131
j
18
1
1
+ 28c (1
(1+1 1
C(3)dB
api
n1
m
80
apd n m
21

---

The function 3 -> C(3) is decreasing so, C(3) < 12/2 C(3)23 & c and so, C(3) < V We also deduce from that
24 24 u(m A n)
3o & 2c
(26)
Hence
nupB + L/d no
2c (4 C(0)d8
96clog(n)
u(m An)
p(n A m)
We now take B1 30 n. We have
31 J
go+1
30 +
C(B)dB <
C(8)dB log
< log n + (21 Bo).
No
30 +
Then, plugging the bound on 30 given by 266
2c xn (24 n)²
96c log(n))
B/ Tr Ep log i - Tr Exp log TI < im
+
p(m A An2
p(n m)
18 ap V
(=
2c (24logn)²
28c
(1
_1
(logn + 2/ c(1 4 (mAn)²
+
n +
(27)
m
ap²
m
Concatenating with 25 we get
1 (8))
2c n m(24logn)
17
[IKKLa(Pl6)) - 1KLK (pllg)
<
(2VC+ logn)
pa
(m A nn)
Vn
28c ajp
(1 n m
1 )
96clog(n)
ap / (2 ) (logn 2 c01
18
2c (24
+
)) (28)
p(n A m)
n
m
n2 (m A nn2
Using increments such that 1 & logn < (log nog 1
and a, p 1, we can
nAm
vmA
upperbound 28 by simpler bound, while still retaining the main convergence rates in log and vmAn
(log n This bound is
in
mAn
35
(KL - (KLa(Pll)) <
(2/c + logn)
Vm A au
1
1+ 1+- +++++200 +24loggn)
m A m (29)
n
ono (1
m A n
As mentioned in Remark 5 it is possible to re- re-write this proof without considering the assumptions that p & and de < 1 and to derive bound similar to this one but which scales in O 0(1) instead
dg
of O()). This bound
32 a. A
(lKLL, (plla)
(2 logn)
c(26 n)2
m m m )) (30)
n
+
(1+
m Ann
a
a
To get this new upper bound, the operator inequality > (1-a) 2)E, > (1 a)HE must be replaced,
each time is used, by x aL' This way, the operator inequality (I' 31'+ -1 |ilajj (2i+ 311
becomes (I' B1)-1 1 (EE + =1)=1 which explains the additional factor 1 in the final bound.
22

---

B.4 Proof of Proposition 6
According |Bach 2022 Proposition 6] we have that the eigenvalues of Ep (resp Σg) are the same than the ones of Fn and we also have that for an eigenvalue À of 1/nKp with associated eigenvector a, the function
Ei=1 arp((z;) is an eigenvector of Σg associated to the same eigenvalue. Hence, denoting (A=) the eigenvalues of 1/n K and a the associated normalized
eigenvectors, the first term writes:
1 Tr(Epp log Epp = Tr ( K3 log - k
Σ X Aogg(A)))
=
n
We now turn to the second term in (2. Let Os = ((p(a1),..... (((an)) By = (f(())....,
a
Or
1
and t
We have Eg = TT
sb and aLg + (1 - aoLog- = et a We
1-
Py
also remark that girb" spectrum. we will replace aLpp + (1-a) - by K in the expression of KKLa, which we can do with
= K. Knowing that the operator v² vo and the matrix upy" have the same
the following lemma.
Lemma 12. If +h E Raxr with r, IR+ - R and yo²" is invertible, then g(b 3) = tt ( g(be) (wb')))))))))) 2g
Proof. Let & UDiag(S)VT the singular value decomposition of di with U e R and Ve E Rdddd orthonormal matrices. We have thas U (Sa and oh SS so, ((bbe) = (Diog(o(S"))UT and g( v)) = ( And so, g(
VU" ((vb" JUVT. Noticing that (win² d UVT concludes the proof.
By Lemma 12 we can write the second term in (2 as:
Tr(2, lo (1 a)Eig) Tr
2
a
1
sbaet (e ( log( (vr) 1og(vrr")((b )
0
Tr
n
0
K log(K)
0
Tr
(())
11
0
K log(K)
0
where the last equality results from the fact that K3 and log K commute because they have the same eigenbasis.
B.5 Proof of Proposition 7
We write F Fi+ and derive the first variation each functional in the next two lemmas. Then, we conclude on the first variation of F.
Lemma 13. Let P as defined Proposition 6 The first variation of Fi : + Tr(Ep log Ep) at P is. for x E supp(ō):
(()))))) = Tr(((t))((=)((11 log Ep)).
and too else.
Proof. In this proof we use residual formula which is useful to derive spectral functions Indeed, we can write TrC2, log Σn) Σ (2,() with f CVR + C, - 2 log z. Consider perturbation & PRR)), & > 0 and A EEg. Let C. Using the linearity of p ト Ep. we have
(og() Tr(E, log Mp) = Tr((E, + A) lo + A)) - Tr(E, log Ep)
= Σ S(N(2 + A)) - f(A((E))).
23

---

Let be a closed directed contour in C\R which surrounds all the positive eigenvalues of Ep and
Ep + A. We have
2im f, f(z)
f(A(EE -((())))))))))
Ep)-1)d
2iπ $ TT= - - -) (=I -pp ))
where
- (=I- 11-3--A1 A)- ( ( -o()))))))
Hence, denoting Σn - Arfes; the singular value decomposition of Eg, we have
Tr((IB + A) log( + A)) - -Tr Trrp log Dp
2i f.
1 -())))((-- -))--)d= o(e)
$ f(=) Tr ΣΣ
fuft (2- (z>x - Av2)
2i Jy
d= d2 o(E)
n
f(z)
dz Tr(SEJkA) o(e).
2im
(2
Xx )
The residue of 1(2) residue formula have
f(z)
2 log xx-)2]²
X is
Res(h, 2x) + llgg de- Applying again the
[8 -z
Tr((Ep + log(E + A)) - Tr(Ep log Ep) = Σ (1 + log )x) Tr(fffTA)+ +(E)
k=1
= =Tr((1 - log Mg 4) + o(E)
= =1+ (r(lo ) (
This concludes the proof by dividing the later quantity by and taking the limit as + 0.
Lemma 14. Let P.q as defined in Proposition 6 Tr(E, Log(a (1 ai))))) at p is, for any x E supp(p):
The first variation of F2 : p +
Fz(0)(x) = Ir (log(aZi (1 -())))(())((()
a+m hy E
log log mh E p(o)ele))): (31)
T
JFk Th
1
where (115 (1 hi) mm are the eigenvalues and eigenvectors aF + (1 a ))E...
Proof. Denote f (1 - a)La gz As for Lemma
let A E.g.. We have: 13
Tr log(a224s (1 (1-1)) a)2ia)) TH(2, A)
[ as) TT(2ip) log 1
-Tr((Ep + log ( + + Tr (2. + log
Tr (Eg log f) Tr EEp log log()) f)
-Th (E f + as) log log()) Tr A log
The second term on the r.h.s. is already linear in A as desired, hence we focus on the first one. Using singular value decomposition of í + a and I' we write:
Tr (Epp(lo [ (+ + - -log(")
m+m Σ
log n + an)), )) Tr
n+m
log oy ([)ng)) )
Tr
Σn
Σ
Using that if h(2) =
(a= then Res(h, A) = f" (z) where f(z) = z zlog(z). Recall that Res(h, X)
f(a
Z f, h(2)dz where is contour circling strictly X.
24

---

where ( are the eigenvectors of positive eigenvalues of + aa. Let y loop surrounding all the cigenvalues Ty aA) and m2 (T'), then,
m log n adAlinhi 1 (o(=)) aa)
2im f
R+
2it f. log(z)(zI- - -f
and
Σ ==1
log my (T)hhh)
Moreover, we have (2l - ad) (2l -
a1 - -T-- + o(E). Hence,
Th TT(Eg(1og( ( + ad)= - -log 11)
log
2ith j. Tr Ep (0) n -)) d= a(s)
(2 Mh (z m1 )
h Sha
log(z) TT
Epp
2im
jik=1
log(2)
dz Tr Eippileethi (halitt
(z 11 (=
176b
J.kml
With the residue theorem, for j * k. 8, (=-0g](=-r)) dz
low(s)
Ing TJ
log 1ip 775
(ng (15-m)) m1)
lox(2) dz 2im log log uh and for & = J. fr, (=-1))
2i5 We then have:
Tr Eg(log( f (+aa) log1")
Tr h (p
n-
log flj
log M Tr Tr(hshiEphhii + o(s).
+ a
fJ
77
JE
We note that if Dg an Eg were diagonalizable the same eigenbasis, then the previous quantity would be equal to Eø=1 Ai [hyhh A) Tr I A where I' is the pseudo inverse of I', We "i conclude again dividing the latter quantity by and considering its limit as e + 0.
We can now write the matrix expression for the first variation of F using Lemma (p(#1)")
12
We remind
that dhe )*
(resp σby) and vi
and that of aLp + (1 a)Σ, and
py.
m
abebT = K. We remark that Ep 1 oo dn and d. = 1 Kg. By Lemma vn vn
we have
TT(log(Ep)) Tr
log
1 n
Kg
(1 n
Kg
(2((0)((())))
n
S(x) gl K S(x))
since S(x) = @xp(2). We show the same way that Tr Togog(a + (1 (1=))[n)((z)p(()) = (K))((z)
For the third term in the first variation of = + F2, i.e. the second one in Equation
31 our
goal is to rewrite Tr (hih E A in terms of matrices. We have h2 "x/c//l// e₁ (idem
25

---

where is an eigenvector of K of eigenvalue 7e and 1 cxl12 T|bT"cll" f Kcx - 7m- Hence,
yoo cack ( (mnos))
Tr(hahh = Tr
chb (0)
11
0)
Keacf(arn /(mn)))
Tr
K
a
1
Th(ec
Tr
1
a
0
0
cack v
Tr
cjee"
(0
0)
O (ac de(x))
We have <b(((z)))(())" we note Cj b;)
(xx)V(x)² where V(x) (2) (o)) and if
1
0
c2 = (aj, ax)
c
0
cjck.
Finally,
Tr( (Epp(log) ( +tad) - log 11)
a+m
| 12
log 11 -log Tk
Tr
(aj. an) v(x)V())². (32)
J
C Additional Experiments
Skewness and concentration of the KKT. In these examples, we plot KKT,, (pllg) as the number of m samples of two distributions p. q increases. In Figure we plot the KKT, for two Gaussians by varying the dimension d. It can be seen that the larger is, the less KKL oscillates. We can also remark that the value of KKL increases with the dimension, reflecting the effect of the constants of Proposition 4 Figure 5 is the same experiment We can also see here that KKL, is monotone in a. We can also see that convergence to the value of KKL in population is faster in this case than for d = 10. The third experiment in Figure i in dimension and the distribution of g is an exponential distribution with parameter = 1, while is Gaussian distribution. We notice few points, such for example that the values taken by KKI. are smaller and that it varies less with a than the case of Figure 5
in the main text, except that the dimension is 2.
10.0
2.0
4.0
7.5
1.5
3.5
5.0
1.0
2.5
0.5
500
1000
0
500
1000
500
1000
number of particules
number particules
number of particules
Figure 4: a 0.01, p,g Gaus- sians, o is the square of the mean of distances between á and q.
Figure 5: = 0.1, a = 2.
Figure 6: N(1, ~ 8(1), a 0.1,
Sampling with KKL gradient descent on Gaussians and mixtures of Gaussians. We are in- terested in sampling on Gaussians or mixtures of Gaussians by varying the dimension. Fig- ure and Figure 8 show the evolution of the KKL value during the gradient descent of different dimensions d, starting with a Gaussian p and taking g to a mixture of 2 Gaussians for Fig- ure 7 and p and q Gaussians distributions for Figure 8 In Figure 7 and Figure g the stepsize
26

---

h= # (Eng ||:
My w)ll²) 1/2 n (//1/(d4), For each d, we report the average and error bars of our results for 20 runs, varying the samples drawn from the initialization and the thick lines represents the average value. We can see that in both cases the convergence is faster for small values of d. On Figure 9 we observe the evolution of (ýll)) the 2 Wasserstein distance, during gradient descent in dimension 10 for various parameters a. The distribution p and q are respectively a Gaussian and mixture of 2 Gaussians. The values of W2 at each iteration / is computed as the mean of Wa (ūi i) on runs of the gradient descent where for each the mean of p is drawn at random. We can see that if the value is too high, then convergence in 2- 2-Wasserstein is slower, whereas if it is too small, convergence is faster at the beginning, but does not lead to an optimal value in Wasserstein distance at the end of the algorithm.
1.0
10
330001
-0.01
0.8-
0.6
W2 ((A)
0.6-
0.4
0.4
0.2
0.24
0.0
25
50
100
50 iterations
75
100
100
200
300
iterations
iterations
Figure 7: a = 0.01, p is a Gaus- sian distribution and q mixture 2 Gaussians, a the square of the mean of distances between P and q.
0.01, p and g are Gaussians. Bandwidth o is the mean of the square distances between P and 9 points.
Figure 8:
Figure 9: a 10, h 5, p is Gaussian and q is a mixture of 2 Gaussians.
3 rings. Appendix C compares the evolution of the gradient flows of MMD, Kale and KKL in terms of Wassertsein distance and Energy distance in the case where optimisation of KKL is done with L-BEGS linesearch Figure 2 We observe that both Kale and KKL seem to converge towards 0 in terms of energy distance and Wasserstein distance but KKT, is faster to converge, in term of number of iterations than Kale. The MMD flow decreases the energy distance but does not converge to 0 in 2- 2-Wasserstein distance, unlike Kale and KKL,, reflecting the fact that some particles are not supported on the target support. The bandwidth of k is fixed at o = 0.1 for Kale and MMD and at 0.3 for KKL. In Figure this time repeat the experiment but for simple gradient descent for KKL with constant step h = 0.01. We see that this case the speed convergence in terms of iterations for KKL is slower than for Kale (there only about 100 iterations necessary for Kale and MMD and 300 for KKL) but it ends up obtaining (see Figure 12). in terms of Wassertsein distance, a similar limit. On the other hand, the execution time of the gradient descent for 300 iterations of KKL is about the same as for Kale and MMD for 100 iterations.
0.8
0.8
KSL
MNO
energy distance
0.4
W/2 distance
0.6
W42 distance
0.6
KALE
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
25
100
100
200
300
Iterations
Iterations
Iterations
Figure 10: L-BFGS, = 0.3, Figure 11: L-BFGS, = 0.3, Figure 12: Constant step size
= 0.01
= 0.01
-= 0.01, 0 = 0.3, a 0.001
27

---

T=0
T=2
T=99
T=300
KALE
MMD
O
O
Figure 13
D
NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: the abstract and introduction list our contributions, i.e. introduction of a novel divergence, theoretical and empirical novel results..
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the
contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification; we clearly state the limitations of our work, among which the lack of theoretical guarantees for the convergence of the Regularized KKL gradient flow, and more efficient operations.
numerical implementations resorting on state-of-the-arr techniques for kernels matrices
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
28

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
For each theoretical result, we worked with minimal and justified assumptions, making all the dependencies of the problem clear. We provide a clear and detailed proof in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
For each experimental result, provide all the detailed setting including choice of hyperparameters to reproduce We took several example datasets used in papers that close to work.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
29

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We will provide link to a public github repository with Python code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
Soaedddeeeoooetubbaaaaassooooeee public/guides//Ce
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
//wpss.c/ppubll. wtt.c//ppplcggg.ii.ee Seeuuddde/Coeeeuueuaeeee swi.bbmiiiiiooooiccccc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: we specify all details for all our experiments, report the variability of our experiments over a set of different runs.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
30

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report enror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For our experiments we provide averages and error bars for the results over set of runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma eгror bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Our experiments run standard laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://wwrrppp..cpppucccttttttta
Answer: [Yes]
Justification: our opinion, this papper does not address socictal impact directly, and consider the generie problem of optimization measures and sampling.
Guidelines:
31

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: In our opinion the paper does not have direct positive or negative social impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., dep.oymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Our paper does not present such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
32

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: all original owners of assets are credited, for instance regarding our experi977 ments, cite the public papers and code that were used as benchmarks for comparison.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: we do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
experiments do not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
33

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: our study do not involve risk for participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "PQN4CeKq4F", "reviewer": "Reviewer_r7ey", "summary": "### Summary:\n\n \n\nIn this paper, the authors study kernel KL divergences (Equation 1). First, they extend the definition of kernel KL to a new setting via regularization that works for distributions with disjoint support (Equation 2). \nIn Propositions 2,3, they prove the approximation results for the regularized kernel KL divergence compared to the unregularized version of it. \nSecond, they derive convergence rates for finite sample estimation of kernel KL divergences (Proposition 3). Moreover, they obtain a closed-form expression for the new divergence (Proposition 5). They also study Wasserstein GF of the new divergence in the paper.", "questions": "### Questions/Comments:\n\nI recommend changing the title of the paper. The whole draft is devoted to the study of \"regularized kernel KL divergence\" but in the title there is no reference to being regularized. \n\n\n- line 124 -- what do you mean by \"if $\\mathbb{R}^d$ is compact\"\n\n- line 131 -- typo \"an interesting\"\n\n- how tight Proposition 4 is?", "limitations": "N/A", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "### Pros:\n\n\n- very well-written paper\n- well-motivated setting with comprehensive results", "weaknesses": "## Cons:\n\n- the title does not reflect the contributions of the paper", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n- Weaknesses: \"the title does not reflect the contributions of the paper\"\n\n    **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.\n    \n- Questions: \"line 124 -- what do you mean by \"if \n is compact\"\n\n **Reply:** \"$\\mathbb{R}^d$ is compact\" is a typo, it was originally a subset of $\\mathbb{R}^d$. Thank you for this correction.\n\n- Questions: tightness of Prop 4\n\n **Reply:** See general comment please.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FQZzsI1OPn", "reviewer": "Reviewer_19Wg", "summary": "Comparing probability measures is a fundamental task in many statistical and machine learning problems. One of the metrics that has been ubiquitously used is Kullback-Leibler (KL) divergence. KL contrasts the information contained in two probability distributions. Statistical learning using KL divergence involves density ratios and needs the fact that the supports of probability measures in question should be not disjoint. \n\nA kernel variant of KL called kernel KL (KLL) divergence was proposed in Bach (2022, IEEE Trans. Info.). KLL compares probability measures through covariance operators in an RKHS space.  As the standard KL, the KLL shares the limit of inability to compare measures with disjoint supports. This paper proposes a regularized variant of KLL that guarantees calculating divergence for all distributions. The authors derive bounds that quantify the deviation of regularized KLL to the original KLL.  they further propose a closed form for KLL for empirical measures. Numerical experiments are conducted on simulated data to corroborate the theoretical results.", "questions": "**Minor Typos**\n\n- L108: the notation $p$ is used for denoting probability measure and the dimension $\\mathbb{R}^p$.\n- L368: there is no caption of the figure and for (b) Shape transfer, the iteration $T=99$ is the same.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Proposing $KKL_\\alpha$ a regularized version of standard KLL, that allows calculating divergence for all distributions.\n- Presenting statistical properties of $KKL_\\alpha$.\n- Providing a closed for KLL between empirical measures.\n- Plugging $KKL_\\alpha$ in a Wasserstein gradient flow learning.", "weaknesses": "**Weakness and Questions**\n\n- The decreasing property  of $KLL_\\alpha$ in Proposition 2 needs the condition that $p$ is absolutely continuous with respect to $q$. However, in the definition of $KLL_\\alpha$  (L144-L145) there is no need for this absolutely continuous. My question does this property still valid without $p<<q$ ? The same remark for the result in Proposition 4.\n- In Proposition 4, the definition of $\\varphi(x)$ needs to be recalled. \n- In Proposition 4, could you please motivate the condition On the Radon-Nikodym derivative to be bound above by $1/\\mu$.\n- To facilitate the lecture on the bound given in Equation (5), I think it will be better to write its order. \n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n- 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 \n $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.\"\n\n**Reply:** See the first point of general comment for the reply concerning Proposition 2.\n\nConcerning 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 \ncontrol 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)$. \n\nThe 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.\n\nWe 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:\n\n$$\\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).$$\n\n\nThank you for pointing out this essential point, which we will clarify in the paper by giving an alternative proof and an alternative bound.  \n\n\n\n- Question: \"In Proposition 4, the definition of $\\varphi(x)$ needs to be recalled.\"\n\n**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}$. \n\n\n- Question: \"In Proposition 4, could you please motivate the condition on the Radon-Nikodym derivative to be bounded above by $\\frac1{\\mu}$.\"\n.\n\n**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.\n\n \n\n- Question: \"To facilitate the lecture on the bound given in Equation (5), I think it will be better to write its order.\"\n\n**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.\n\n- 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?\n\n\n**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.\n\\vspace{2mm}\n\n\n- Minor typos: thanks for spotting these, we corrected accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2BlWF62qTT", "reviewer": "Reviewer_ffGL", "summary": "The authors generalize and analyze the kernel Kullback-Leibler divergence introduced by Francis Bach a few years ago. The main contributions are 1) use a skew divergence (like in JS) tinstead of KL  consider non-absolutely continuous divergences, 2) provide an explicit formula of the divergence for discrete measure which allows a direct implementation for data, 3) provide refined finite sample guarantees. The divergence is used then to build a Wasserstein gradient flow and generative modeling. Some low-dimensional numerical examples are provided.", "questions": "1) Is there a reasonable expectation that their flows to scale up to high dimension? Or what is the obstacle?\n\n2) 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 Gu et al (https://arxiv.org/abs/2210.17230) 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.", "limitations": "The limitations of the work are properly addressed.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work extend the original work by F. Bach in several aspects. In particular the explicit formula of the divergence for discrete measures is a nice and very useful results which wiil come handy  in applications. The paper is very clearly and nicely written and the proof looked sound to the reviewer.", "weaknesses": "The reviewer find the applications somewhat underwhelming. 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.  Kernel methods have the advantages that provide explicit formula for the velocity vector field and one would hope that this allow to consider high-dimensional problem but no such experiment have been provided so it is not clear if the proposed model scales up.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n- 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.\"\n\n**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. \n\n\n- Question \"Is there a reasonable expectation that their flows to scale up to high dimension? Or what is the obstacle?\" \n\n**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. \n\n- 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.\"\n\n**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). \nThe 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. \nRegarding (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)). \nOur work, through numerical experiments, is a first tentative for comparing these different techniques, through comparing KKL with Kale.  \nThen, 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. \nA 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.\n\n\n\n\n[1] Arbel, Korba, Salim, Gretton. Maximum Mean Discrepancy Gradient Flow, Neurips, 2019.\n\n[2] Gu, Birmpa, Pantazis, Ret-Belley, A. Katsoulakis, Lipschitz-Regularized Gradient Flows and Generative Particle Algorithms for High dimensional Scarce Data, 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gfsXnwKygH", "reviewer": "Reviewer_6zq3", "summary": "This paper proposes the regularized kernel KL divergences. With the kernelization, the authors derive closed form formula and makes it computationally cheap to optimize using gradient methods. Theoretically, a new finite sample estimation convergence bound is derived. Numerical simulations suggest this proposed divergences are not only easy to implement, but also suitable for sampling complicated distributions.", "questions": "1. Typo at line 301: ''For small values of the regularization parameter'' $\\to$ ''For large values of the regularization parameter'.\n\n2. 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? \n\n3. 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?\n\n4. Why does Figure 2(a) begin with different particles across different methods at $T=0$?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow.\n\n2. Finite sample approximation bound is derived.\n\n3. Numerical simulations demonstrate good performance over other related divergences.", "weaknesses": "1. Proposition 1 still assumes $p$ is absolutely continuous with respect to $q$.\n\n2. The bound in Proposition 3 becomes trivial since it approaches $\\infty$ as $\\alpha\\to 1$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n- Weakness: \"Proposition 1 still assumes $p$ \n is absolutely continuous with respect to $q$\n.\"\n\n**Reply:** Thank you for spotting the typo,  please see the general comment.\n\n- Weakness : \"The bound in Proposition 3 becomes trivial since it approaches $\\infty$ as $\\alpha \\rightarrow 1$.\"\n\n**Reply:* This is true that the bound becomes trivial as $\\alpha$ goes to 1. \nHowever, 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.\n\n- 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?\"\n\n**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.  \n\n- 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?\"\n\n**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.\n\n- Question : \"Why does Figure 2(a) begin with different particles across different methods at $T=0$ ?\"\n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for their positive comments on our paper, as well as for their relevant suggestions and questions. We adress here the general comments and questions.  If we have adequately addressed the reviewer's concerns, a re-evaluation would be greatly appreciated. For any unresolved issues, we are ready to engage further. 


- Contributions (to all reviewers): We propose a kernel-based divergence relying on kernel covariance operators (in contrast to kernel mean embeddings operators as used in the Maximum Mean Discrepancy)
that is computable in closed-form (see our Proposition 5). We derive theoretical results on this divergence, including monotony with respect to the regularization parameter, statistical rates, and well-posedness and closed-form for its derivatives. This enabled us to use the latter object in a gradient flow setting to study its empirical behavior when approximating probability distributions and performs better than the MMD and is more practical than alternative kernel-based approximations of the Kullback-Leibler divergence such as KALE (which is not closed-form).
We think our study motivates that using higher order moments (eg covariances instead of mean embeddings) enables to compare probability distributions in a more powerful manner than Maximum Mean Discrepancy, while being closed-form and tractable. 

- About the assumption $p\ll q$ in Proposition 2 (reviewer 19Wg and  6zq3) : This is a typo and we thank the reviewers for spotting this incoherence. This condition is not necessary to ensure the decreasing property of the regularized KKL in $\alpha$ for $\alpha \in ]0,1[$, as can be seen in its proof in Section  B.1, as $KKL_{\alpha}$ can be defined even without $p \ll q$. 

- About the bound in Proposition 4 and its tightness (reviewers 19Wg and r7ey), we simplified our bound which yields the following : $$ \mathbb{E} | KKL_{\alpha}(\hat{p}||\hat{q}) - KKL_{\alpha}(p||q) | \leqslant \frac{35}{\sqrt{m \wedge n}} \frac1{\alpha \mu} (2 \sqrt{c} + \log n) + \frac{1}{m \wedge n} \left(1+\frac1{\mu} +   \frac{c (24 \log n)^2}{\alpha \mu^2} (1 + \frac{n}{m \wedge m})\right).$$ This makes it easier to see which terms dominate the upper bound. And we see, as mentioned on line 184, that if we put $n=m$, we find a bound similar to that of Proposition 7 of [1].  Notice that this is a similar rate (up to log factors) as the one of MMD that is minimax [2] and that rely on the estimation of similar Bochner integrals (kernel mean embeddings instead of kernel covariance operators). 
We did not tackle the study of lower bounds, as the calculation of our upper bound was already very technical (see the sketch of proof line 190, full proof is deferred to the appendix); we leave the question of lower bound for future work.

- About Figure 2.a (reviewer 6zq3), we have attached a pdf containing the corrected version of Figure 2.a.

[1] Bach, F. Information Theory with Kernel Methods, IEEE Transactions in Information Theory,  2023.

[2] Tolstikhin, I., Sriperumbudur, B. K.,  Mu, K.  Minimax Estimation of Kernel Mean Embeddings, JMLR, 2017.

Meta-review: The paper proposes a regularized version of the Kernel Kullback-Leibler divergence (KKL, Bach 2022) and studies its statistical properties, including in particular a finite-sample bound and the associated Wasserstein gradient flow.

Reviewers all agree that the presented results are novel and of interest to the community.

Additional comments:

- The title should be changed, as suggested by Reviewer r7ey.

- Eq(3): the second term on the right hand side should read $\Sigma_p(\Sigma_q + \beta I)^{-1}$. The exact reference for this identity in Ando (1979), i.e. which equation, page in that paper, should be given.

- Proposition 3: as mentioned by Reviewer  6zq3, this bound is trivial when $\alpha \rightarrow 1$, so it's a loose bound.

- In Proposition 4, the assumption that $p << q$ is a weakness, since the regularized KKL is supposed to be finite for all pairs p,q. One should be able to obtain finite-sample complexity in this general setting.
Decision: Accept (poster)