Bounding the Error From Reference Set Kernel Maximum Mean Discrepancy

Alexander CloningerarXiv 2018 · OpenReview

Abstract

In this paper, we bound the error induced by using a weighted skeletonization of two data sets for computing a two sample test with kernel maximum mean discrepancy (MMD). The error is quantified in terms of the speed in which heat diffuses from those points to the rest of the data, as well as how flat the weights on the reference points are, and gives a non-asymptotic, non-probabilistic bound. The result ties into the problem of the eigenvector triple product, which appears in a number of important problems. The error bound also suggests an optimization scheme for choosing the best set of reference points and weights. The method is tested on several two sample test examples.

Introduction

In machine learning and statistics, the Kernel Maximum Mean Discrepancy (MMD) is a cornerstone for two-sample testing, answering whether two datasets $X$ and $Y$ originate from the same distribution. However, the standard MMD calculation is computationally prohibitive for large-scale data, scaling at $O(N^2)$ where $N$ is the number of samples.

To address this, researchers have proposed "reference set" or "asymmetric" tests, where data is compared against a small set of landmark points (a skeletonization). While empirically successful, these methods lacked a rigorous theoretical framework to quantify the approximation error. This work provides a non-asymptotic safety net for such skeletonization, linking statistical accuracy to the physical intuition of heat diffusion.

Methodology: Heat Diffusion and Spectral Bounds

The core of our approach treats the dataset as a manifold where kernels represent the probability of a random walk (diffusion) between points. We define a weighted skeletonization where a small set of reference points $R$ is assigned weights $a_w$.

Visualization of two datasets separated by a distance $\delta$

Our primary theoretical contribution, Theorem 2 (The Diffusion Bound), establishes that the error between the true MMD and the reference set MMD is determined by how "flat" the heat distribution becomes after diffusing from the reference points. If heat spreads evenly across the data manifold in a short time, the reference set serves as a high-fidelity proxy for the entire population. This allows us to move from $O(N^2)$ complexity to $O(N \cdot |R|)$, where $|R| \ll N$.

Experimental Evaluation and Results

We evaluated the method on several challenging benchmarks, including 5D Gaussians with high-density anomalies and manifold local shifts on 5D spheres. These tests were designed to see if the reference set could detect subtle geometric deformations or "needle in a haystack" anomalies.

Convergence and Power

The error bound proves that as reference points are added, the approximation converges to the true MMD at a rate of $1/\sqrt{|R|}$. Crucially, the "low-frequency" assumption holds: the broad shapes of distributions (captured by the lower end of the spectrum) are more significant for MMD than high-frequency noise.

Error $\epsilon$ as a function of eigenvalues kept for various $\delta$

As shown in the figure above, the error $\epsilon$ decreases consistently as more spectral information (eigenvalues $L$) is retained. Furthermore, in anomaly detection tasks, the weighted reference MMD matched the statistical power of the full $O(N^2)$ MMD while using only a tiny fraction of the data points.

Conclusion

This work demonstrates that weighting reference points is often more critical than the selection of the points themselves. By optimizing weights to ensure the reference set "covers" the data geometry effectively, we can maintain high testing power with minimal computational overhead. Future work will focus on solving the "triple product problem" of eigenfunctions to provide even tighter analytical bounds and reducing the pre-computation costs associated with global structure estimation.

Summary updated

Abstract

In this paper, we bound the error induced by using a weighted skeletonization of two data sets for computing a two sample test with kernel maximum mean discrepancy. The error is quantified in terms of the speed in which heat diffuses from those points to the rest of the data, as well as how at the weights on the reference points are, and gives a non-asymptotic, non-probabilistic bound. The result ties into the problem of the eigenvector triple product, which appears in a number of important problems. The error bound also suggests an optimization scheme for choosing the best set of reference points and weights. The method is tested on a several two sample test examples.
BibTeX
@misc{cloninger2018bounding,
  author = {Alexander Cloninger},
  title = {{Bounding the Error From Reference Set Kernel Maximum Mean Discrepancy}},
  year = {2018},
  eprint = {1812.04594},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1812.04594},
}
Figure