A Note on Optimizing Distributions using Kernel Mean Embeddings

Boris Muzellec, Francis R. Bach, Alessandro RudiarXiv 2021 · OpenReview

Abstract

Kernel mean embeddings are a popular tool that consists in representing probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. When the kernel is characteristic, mean embeddings can be used to define a distance between probability measures, known as the maximum mean discrepancy (MMD). A well-known advantage of mean embeddings and MMD is their low computational cost and low sample complexity. However, kernel mean embeddings have had limited applications to problems that consist in optimizing distributions, due to the difficulty of characterizing which Hilbert space vectors correspond to a probability distribution. In this note, we propose to leverage the kernel sums-of-squares parameterization of positive functions of Marteau-Ferey et al. [2020] to fit distributions in the MMD geometry. First, we show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. Then, we provide algorithms to optimize such distributions in the finite-sample setting, which we illustrate in a density fitting numerical experiment.

Introduction: The Challenge of Distribution Optimization

Kernel Mean Embeddings and the Maximum Mean Discrepancy (MMD) are powerful tools in machine learning for comparing distributions. However, they face a major hurdle when it comes to optimizing distributions (e.g., in density fitting or distributionally robust optimization).

The problem is one of "validity": while every probability distribution has a unique mean embedding in a Reproducing Kernel Hilbert Space (RKHS), not every vector in that Hilbert space corresponds to a valid distribution. If you try to optimize a distribution by simply moving a vector around in the RKHS, you might end up with a "distribution" that has negative mass or doesn't integrate to one. Previous work often relaxed these constraints, leading to physically impossible solutions. This paper seeks a way to stay within the "manifold" of valid probability distributions during optimization.

Methods: Kernel Sums-of-Squares Parameterization

The authors propose using a Kernel Sums-of-Squares (SoS) representation for the density of the distribution.

  1. Parameterization: They define the density $p_A(x)$ as a quadratic form: $p_A(x) = \langle \phi(x), A\phi(x) \rangle_{\mathcal{H}}$, where $A$ is a positive semi-definite (PSD) operator. This construction automatically guarantees that the density is non-negative.
  2. Mass Constraint: The requirement for the distribution to have unit mass (integrate to 1) is expressed as a linear trace constraint on the operator $A$.
  3. Low-Rank Approximation: To make this computationally tractable, the problem is projected onto a finite-dimensional subspace spanned by $m$ support points. This turns the infinite-dimensional operator $A$ into a finite $m \times m$ PSD matrix $B$.
  4. Optimization Algorithm: MMD optimization is reformulated as a smooth convex problem. By using a clever change of variables, the complex trace constraint is transformed into a simple projection onto a simplex, allowing the use of standard accelerated gradient methods like FISTA.

Key Insights: Avoiding the "Negative Mass" Trap

A critical contribution of this work is identifying the "Negative Mass" Trap. Standard RKHS relaxations for Distributionally Robust Optimization (DRO) can fail spectacularly, producing "adversaries" that are essentially Dirac deltas with negative mass. By using the SoS parameterization, the optimization is constrained to the space of valid densities.

Figure 3: Illustration of the negative mass problem in standard RKHS relaxations versus valid adversaries.

Furthermore, the authors prove (Theorem 1) that distributions with SoS densities are "dense" in the space of all probability distributions. This means that, given a large enough kernel, this parameterization can approximate any distribution arbitrarily well. The SoS representation is also highly compatible with MMD, as distances can be computed using integrals of products of kernels, which often have closed-form solutions for common kernels like the Gaussian.

Key Results: Density Fitting on "Two Moons"

The method was evaluated on a synthetic "Two Moons" dataset, sampling $n=100$ points. Using a subset of $m$ points as "support points," the model successfully recovered the complex geometry of the underlying distribution.

Figure 5: Density fitting results showing the effects of regularization, bandwidth, and number of support points on the Two Moons dataset.

The experiments highlight several key behaviors:

  • Bandwidth ($\sigma$): Controls the smoothness of the fit.
  • Trace Regularization ($\lambda$): Prevents over-fitting to individual sample points.
  • Computational Efficiency: The proposed algorithm has a complexity of $O(mn + m^3/\epsilon^2)$. While the $m^3$ term suggests it is best suited for moderate numbers of support points, it remains efficient for many practical 2D and 3D tasks.

Limitations and Future Work

While promising, the SoS parameterization faces challenges in scaling to high dimensions, as computing integrals over the reference measure $\rho$ or choosing effective support points becomes difficult. Currently, support points are sampled from the data; optimizing their locations (the "pre-image problem") is a key area for future research. Additionally, while the theoretical framework for DRO is provided, future work should focus on benchmarking the SoS-DRO approach against existing relaxations in practical scenarios.

Summary updated

Abstract

Kernel mean embeddings are a popular tool that consists in representing probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. When the kernel is characteristic, mean embeddings can be used to define a distance between probability measures, known as the maximum mean discrepancy (MMD). A well-known advantage of mean embeddings and MMD is their low computational cost and low sample complexity. However, kernel mean embeddings have had limited applications to problems that consist in optimizing distributions, due to the difficulty of characterizing which Hilbert space vectors correspond to a probability distribution. In this note, we propose to leverage the kernel sums-of-squares parameterization of positive functions of Marteau-Ferey et al. [2020] to fit distributions in the MMD geometry. First, we show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. Then, we provide algorithms to optimize such distributions in the finite-sample setting, which we illustrate in a density fitting numerical experiment.
BibTeX
@misc{muzellec2021note,
  author = {Boris Muzellec and Francis R. Bach and Alessandro Rudi},
  title = {{A Note on Optimizing Distributions using Kernel Mean Embeddings}},
  year = {2021},
  eprint = {2106.09994},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.09994},
}
Figure