Comparing distributions: 퓁1 geometry improves kernel two-sample testing

Meyer Scetbon, Gaël Varoquaux

This NeurIPS 2019 paper by Meyer Scetbon and Gaël Varoquaux challenges a long-standing convention in statistical testing: the reliance on Euclidean ($L^2$) geometry. By switching to the Manhattan ($L^1$) distance, the authors demonstrate a significant boost in the power of kernel-based two-sample tests, particularly in high-dimensional settings.

The Challenge of Two-Sample Testing

Two-sample testing asks a fundamental question: "Are these two sets of data drawn from the same underlying distribution?" This is a cornerstone of data science, used in everything from clinical trials to detecting "data drift" in machine learning models.

The current "gold standard" is the Maximum Mean Discrepancy (MMD), which measures the distance between distributions in a high-dimensional feature space (a Reproducing Kernel Hilbert Space, or RKHS). However, MMD has two major drawbacks:

  1. Computational Cost: Standard MMD scales quadratically ($O(n^2)$) with the number of samples, making it sluggish for large datasets.
  2. The Geometry Gap: Most existing methods use $L^2$ (Euclidean) distances to compare distribution representatives. In high-dimensional spaces, Euclidean distances often fail to distinguish between points effectively—a facet of the "curse of dimensionality."

Proposed Method: Embracing $L^1$ Geometry

The authors propose a new family of metrics based on $L^p$ distances (where $p \ge 1$) between distribution representatives, focusing specifically on the $L^1$ case.

To make this computationally tractable, they avoid comparing the full distributions. Instead, they evaluate the differences between distribution representatives at a small number ($J$) of specific "test locations" or frequencies, resulting in a $J$-dimensional vector. They introduce two primary variants:

  • L1-ME (Mean Embedding): Compares expectations of analytic functions at spatial locations.
  • L1-SCF (Smooth Characteristic Function): Compares distributions in the frequency domain.

The Secret Sauce: Optimization. Unlike older methods that picked test locations randomly, the authors optimize these locations and the kernel parameters (like the width of a Gaussian) to maximize the test's power. They prove that under the null hypothesis (distributions are the same), their $\ell_1$-based statistic follows a Nakagami distribution, allowing for simple and fast calculation of p-values.

Key Insights and Results

Dense Differences: When using "analytic" kernels (like the Gaussian kernel), the difference between two different distributions is non-zero almost everywhere. The authors argue that the $\ell_1$ norm is better at "capturing" these dense, small differences across many features than the $\ell_2$ norm, which tends to be dominated by a few large outliers.

High-Dimensional Robustness: The paper confirms that $\ell_1$ geometry is significantly more robust as dimensionality increases.

Type I and Type II errors across varying dimensions. L1-opt-SCF maintains its statistical power even as dimensionality scales, whereas traditional tests collapse.

As seen in the Gaussian Variance Difference (GVD) and Gaussian Mean Difference (GMD) experiments, while the power of $L^2$-based tests often collapses in high dimensions, the $\ell_1$ tests maintain their ability to detect differences.

Better Power/Time Tradeoff: The proposed $\ell_1$ tests (specifically L1-opt-SCF) consistently outperformed quadratic-time MMD tests in the GVD problem, despite being significantly faster to compute.

Real-World Success: The authors evaluated their methods on several real-world benchmarks, including the Higgs dataset (distinguishing Higgs boson signatures from background noise) and the Fastfood dataset (comparing spatial distributions of competing restaurant chains).

Results on the Higgs and Fastfood datasets demonstrating L1-based tests' real-world efficacy.

On the Higgs dataset, the $\ell_1$ version of the test showed a clear advantage over its $\ell_2$ counterpart. In the Fastfood dataset, the L1-opt-ME test correctly identified differences between competing brands (e.g., McDonald's vs. Burger King) while matching the performance of the much more expensive "gold standard" MMD-quad test.

Interpretability: Because the test relies on specific spatial locations ($J$), researchers can plot these locations on a map or graph. This tells the researcher exactly where the two distributions differ most, providing qualitative insight alongside the statistical result.

Limitations and Future Work

  • Optimization Complexity: The $\ell_1$ objective function used for tuning test locations is non-smooth. This makes it more difficult to optimize via standard gradient descent compared to smoother $\ell_2$ objectives.
  • Proxy Objectives: The authors use a lower bound on the test power as a proxy for optimization. While effective, there may be more direct ways to optimize the test.
  • Expansion: The authors suggest that this $\ell_1$ geometry approach could be extended beyond two-sample testing to "goodness-of-fit" testing (comparing a sample to a theoretical model).

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. This performance gain is retained even in high dimensions.
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