Comparing distributions: š“1 geometry improves kernel two-sample testing

Meyer Scetbon, Gaƫl Varoquaux

Abstract

Are two sets of observations drawn from the same distribution? This problem is a two-sample test. Kernel methods lead to many appealing properties. Indeed state-of-the-art approaches use the $L^2$ distance between kernel-based distribution representatives to derive their test statistics. Here, we show that $L^p$ distances (with $p\geq 1$) between these distribution representatives give metrics on the space of distributions that are well-behaved to detect differences between distributions as they metrize the weak convergence. Moreover, for analytic kernels, we show that the $L^1$ geometry gives improved testing power for scalable computational procedures. Specifically, we derive a finite dimensional approximation of the metric given as the $\ell_1$ norm of a vector which captures differences of expectations of analytic functions evaluated at spatial locations or frequencies (i.e, features). The features can be chosen to maximize the differences of the distributions and give interpretable indications of how they differs. Using an $\ell_1$ norm gives better detection because differences between representatives are dense as we use analytic kernels (non-zero almost everywhere). The tests are consistent, while much faster than state-of-the-art quadratic-time kernel-based tests. Experiments on artificial and real-world problems demonstrate improved power/time tradeoff than the state of the art, based on $\ell_2$ norms, and in some cases, better outright power than even the most expensive quadratic-time tests.

Introduction

The "two-sample test" is a fundamental problem in statistics: given two sets of data, do they come from the same underlying probability distribution? This is crucial for various machine learning tasks, such as data integration or evaluating the fidelity of generative models like GANs.

State-of-the-art kernel methods, such as the Maximum Mean Discrepancy (MMD), are powerful because they can detect any difference between distributions without assuming a specific parametric shape. However, the standard MMD has a significant drawback: its computational cost scales quadratically ($O(n^2)$) with the number of samples, making it impractical for massive datasets. While linear-time approximations exist—typically comparing distributions at specific "test locations" using $\ell_2$ distances—this paper argues that $\ell_2$ is a sub-optimal geometry. Instead, the authors demonstrate that $\ell_1$ geometry provides a much more sensitive "lens" for detecting differences.

Methodology

The core contribution is a new family of metrics based on $L^p$ distances (where $p \geq 1$) between kernel mean embeddings, with a specific focus on the $L^1$ geometry.

  1. L1-ME (Mean Embedding): This test compares the expectations of a kernel function at $J$ specific spatial locations. Unlike the $\ell_2$ approach which squares differences, L1-ME sums the absolute differences.
  2. L1-SCF (Smooth Characteristic Function): A frequency-domain variant that compares distributions based on their characteristic functions at $J$ frequencies.
  3. Analytic Kernels: The authors prove that when using "analytic" kernels (like the Gaussian kernel), the difference between distribution representatives is "dense"—meaning it is non-zero almost everywhere. The $\ell_1$ norm is mathematically better at detecting these widespread, subtle differences than the $\ell_2$ norm, which can be dominated by a few large outliers.
  4. Optimization: To maximize sensitivity, the authors optimize test locations and kernel parameters by maximizing a lower bound on the test's power, effectively "learning" where the distributions differ most.

Experimental Results

The proposed methods were evaluated against synthetic benchmarks (Gaussian Mean Difference, Gaussian Variance Difference, and "Blobs") and real-world datasets (Higgs boson signatures and geographic restaurant footprints).

High-Dimensional Robustness

A key finding is that $\ell_1$ tests maintain performance as dimensionality increases. In high-dimensional spaces, differences between distributions often become spread across many features. The $\ell_1$ norm's sensitivity to these dense differences allows it to outperform $\ell_2$ methods, which see their power drop off significantly.

Power and Scalability

In terms of the power-to-time tradeoff, the optimized $\ell_1$ tests (L1-opt-ME/SCF) significantly outperformed their $\ell_2$ counterparts. Remarkably, in several tasks like the Gaussian Variance Difference (GVD), these linear-time tests achieved higher power than even the expensive, quadratic-time MMD-quad test.

Discussion and Conclusion

By switching from $\ell_2$ to $\ell_1$ geometry, the authors have developed a class of two-sample tests that are both computationally efficient ($O(n)$) and statistically powerful. The "dense difference" intuition—that analytic kernels produce differences everywhere—justifies why $\ell_1$ is a superior metric for these embeddings.

While the $\ell_1$ objective function is non-smooth and requires careful optimization via automatic differentiation, the resulting tests offer a compelling alternative to traditional methods. Future work may extend this geometry to goodness-of-fit testing and explore specialized optimization algorithms for non-smooth kernel objectives.

Summary updated

Abstract

Are two sets of observations drawn from the same distribution? This problem is a two-sample test. Kernel methods lead to many appealing properties. Indeed state-of-the-art approaches use the $L^2$ distance between kernel-based distribution representatives to derive their test statistics. Here, we show that $L^p$ distances (with $p\geq 1$) between these distribution representatives give metrics on the space of distributions that are well-behaved to detect differences between distributions as they metrize the weak convergence. Moreover, for analytic kernels, we show that the $L^1$ geometry gives improved testing power for scalable computational procedures. Specifically, we derive a finite dimensional approximation of the metric given as the $\ell_1$ norm of a vector which captures differences of expectations of analytic functions evaluated at spatial locations or frequencies (i.e, features). The features can be chosen to maximize the differences of the distributions and give interpretable indications of how they differs. Using an $\ell_1$ norm gives better detection because differences between representatives are dense as we use analytic kernels (non-zero almost everywhere). The tests are consistent, while much faster than state-of-the-art quadratic-time kernel-based tests. Experiments on artificial and real-world problems demonstrate improved power/time tradeoff than the state of the art, based on $\ell_2$ norms, and in some cases, better outright power than even the most expensive quadratic-time tests.
BibTeX
@inproceedings{scetbon2019comparing,
  author = {Meyer Scetbon and Gaƫl Varoquaux},
  title = {{Comparing distributions: š“1 geometry improves kernel two-sample testing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=hoxcFAvFft2},
}
Figure