Statistical and Geometrical properties of the Kernel Kullback-Leibler divergence

Anna Korba, Francis R. Bach, Clémentine Chazal

TL;DR

This paper introduces a regularized version of the Kernel Kullback-Leibler (KKL) divergence, a metric that compares probability distributions using covariance operators in a Reproducing Kernel Hilbert Space (RKHS). By mixing the target distribution with the source, the authors create a "skewed" divergence that remains well-defined even for non-overlapping distributions, providing a robust, closed-form tool for distribution approximation and particle-based optimization.

What Problem Does This Paper Address?

In machine learning, we often need to measure the "distance" between a model distribution $p$ and a target distribution $q$. Two common tools are the Kullback-Leibler (KL) divergence and the Maximum Mean Discrepancy (MMD).

However, both have flaws:

  • Standard KL is mathematically elegant but "breaks" (diverges to infinity) if the supports of $p$ and $q$ don't overlap perfectly—a common occurrence when dealing with discrete samples or low-dimensional manifolds.
  • MMD is easy to compute from samples but often suffers from poor "geometrical" properties, such as getting stuck in local minima during optimization because it only looks at the first moments (means) of the embeddings.

A recent alternative, the Kernel KL (KKL), uses second-order information (covariance operators) to bridge these worlds. But like the standard KL, the original KKL fails when distributions are disjoint. This paper tackles that specific limitation, making KKL a practical tool for real-world sampling and generative modeling.

Methods

The authors propose Regularized KKL ($KKL_\alpha$). Instead of comparing $p$ directly to $q$, they compare $p$ to a mixture: $(1-\alpha)q + \alpha p$. This "regularization" ensures the divergence is always finite and well-behaved for any $\alpha \in (0, 1)$.

Key technical contributions include:

  1. Theoretical Analysis: They prove that $KKL_\alpha$ is monotone with respect to $\alpha$ and provide "finite-sample bounds," showing how quickly the divergence calculated from $n$ points converges to the true underlying value.
  2. Closed-Form Expression: For discrete sets of points (particle clouds), they derive an explicit formula using Kernel Gram matrices. This is a major win for implementation, as it avoids the need for complex density estimations.
  3. Wasserstein Gradient Flow: They derive the "first variation" of the functional, which allows them to move particles along the steepest descent path to match a target distribution. Because the formula is closed-form, they can use efficient off-the-shelf optimizers like L-BFGS.

Datasets

The paper focuses on synthetic benchmarks designed to test the geometric and statistical properties of the divergence:

  • Anisotropic Gaussians: Used to validate the concentration bounds and show how the metric behaves in higher dimensions ($d=10$).
  • 3-Rings Target: A target distribution supported on three non-overlapping rings (a zero-volume hypersurface) to test how the gradient flow handles complex supports.
  • Shape Transfer: Moving particles from a "heart" shape to a "spiral" shape to evaluate performance on disjoint supports.
  • Gaussian vs. Exponential: Testing the metric's sensitivity when the source and target come from different families of distributions.

Key Insights and Ideas

  • Second-Order Advantage: While MMD relies on "mean embeddings" (first-order), KKL uses "covariance operators" (second-order). This makes it more discriminative, especially when distributions have the same mean but different shapes.
  • The "KALE" Comparison: The authors compare their work to KALE (Kernelized Aligned Likelihood Estimator). While KALE is also a kernel-based KL variant, it requires solving an internal optimization problem at every step. $KKL_\alpha$ is much faster because it has a direct, analytical formula.
  • Geometric Robustness: The gradient flow of $KKL_\alpha$ is "stickier" to the target support than MMD. In the "3-rings" experiment, MMD particles often drift away from the rings, whereas $KKL_\alpha$ particles follow the target geometry precisely.

Key Results

  • Statistical Convergence: The empirical estimate of $KKL_\alpha$ converges to the population limit at a rate of roughly $O(1/\sqrt{n})$, which is validated by their experiments.
  • Optimization Efficiency: By using L-BFGS with the derived closed-form gradients, the authors achieve faster and more robust convergence in distribution transport tasks compared to standard gradient descent or MMD-based flows.
  • Robustness to $\alpha$: The method is relatively insensitive to the choice of the regularization parameter $\alpha$, making it easier to tune than many other divergence-based algorithms.

Limitations and Future Work

  • Computational Complexity: The current implementation involves singular value decompositions (SVD) of matrices, leading to a cost of $O((n+m)^3)$. This limits the method to a few thousand particles. The authors suggest using random features or Nyström approximations to scale to larger datasets.
  • Theoretical Gaps: While the empirical results are strong, a formal proof for the convergence of the Wasserstein gradient flow (the path the particles take) remains an open theoretical challenge.
  • High-Dimensional Scaling: While it performs better than MMD, all kernel methods eventually face challenges as the dimension $d$ increases; further study is needed to see how $KKL_\alpha$ handles very high-dimensional latent spaces.

Summary updated

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.
BibTeX
@inproceedings{korba2024statistical,
  author = {Anna Korba and Francis R. Bach and Clémentine Chazal},
  title = {{Statistical and Geometrical properties of the Kernel Kullback-Leibler divergence}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=R0Fs4yt877},
}

Loading related content...

Figure