Comparing distributions: $\ell_1$ geometry improves kernel two-sample testing

NeurIPS 2019

TL;DR

This paper introduces a new kernel-based method for two-sample testing that uses the $\ell_1$ norm instead of the traditional $\ell_2$ norm. This seemingly small change significantly improves the power of the tests, allowing them to detect differences between distributions more effectively and efficiently, especially in high-dimensional settings.

What Problem Does This Paper Address?

The fundamental problem addressed is the two-sample test: determining whether two sets of observations come from the same underlying probability distribution. This is a crucial task in many fields, from machine learning (e.g., evaluating generative models) to statistics and data analysis. Kernel methods have been a popular approach, often relying on the Maximum Mean Discrepancy (MMD) which uses the $\ell_2$ distance between "mean embeddings" of distributions in a Reproducing Kernel Hilbert Space (RKHS). While powerful, these methods can be computationally expensive, especially for large datasets or high-dimensional data. The paper aims to improve both the statistical power and computational efficiency of these kernel-based tests.

Methods

The core innovation lies in replacing the $\ell_2$ distance with the $\ell_1$ distance when comparing kernel-based distribution representatives (specifically, mean embeddings). The authors show that $\ell_p$ distances for $p \ge 1$ can metrize weak convergence of probability measures, making them theoretically sound for two-sample testing.

Key methodological contributions include:

  • $\ell_1$-based test statistic: A new test statistic, $\delta_{\ell_1, \mu, J}$, is derived based on the $\ell_1$ norm of the difference between mean embeddings evaluated at $J$ chosen locations.
  • Asymptotic analysis: The paper provides theoretical guarantees for the new statistic, showing it converges to a sum of Nakagami variables under the null hypothesis and can be arbitrarily large under the alternative, leading to consistent tests.
  • Optimization of test locations: Similar to prior work, the authors propose optimizing the $J$ locations where the mean embeddings are evaluated to maximize test power. This optimization is crucial for the $\ell_1$ norm's effectiveness.
  • Smooth Characteristic Function (SCF) variant: An analogous $\ell_1$-based test is developed using smooth characteristic functions in the frequency domain, offering an alternative for translation-invariant kernels.
  • Computational efficiency: The proposed $\ell_1$-based tests are shown to be faster than quadratic-time $\ell_2$-based MMD tests, especially when combined with efficient approximations.

Datasets

The paper evaluates its proposed methods on a combination of synthetic and real-world datasets:

  • Synthetic Datasets:
    • Same Gaussian (SG)
    • Gaussian Mean Difference (GMD)
    • Gaussian Variance Difference (GVD)
    • Blobs (a mixture of Gaussians)
  • Real-world Datasets:
    • Higgs dataset: Used for distinguishing Higgs bosons from background noise.
  • Fast food restaurants dataset: A Kaggle dataset of over 10,000 restaurant locations across the USA, used to compare spatial distributions of different brands.
  • Newsgroups text dataset: Used as a high-dimensional example for distinguishing text articles based on word distributions.

The paper does not introduce new benchmark datasets but uses established ones to compare its methods against prior art.

Key Insights and Ideas

  • $\ell_1$ geometry is more powerful for detecting differences: The paper's central insight is that the $\ell_1$ norm, by capturing "dense" differences (due to analytic kernels), provides better detection power than the $\ell_2$ norm. This is particularly true when distributions differ in subtle or widespread ways.
  • Optimizing locations is key: The effectiveness of the $\ell_1$-based tests is significantly boosted by optimizing the $J$ locations where distribution representatives are evaluated. This allows the tests to focus on regions where the distributions are most distinct.
  • High-dimensional benefits: The $\ell_1$ norm's advantage becomes more pronounced in higher dimensions, aligning with theoretical findings that $\ell_1$ distances are more robust to dimensionality.
  • Interpretable features: The optimized locations identified by the $\ell_1$-based tests can offer interpretable insights into where the distributions differ, providing more than just a binary reject/accept decision.
  • Computational trade-off: While optimizing locations can be computationally intensive, the resulting $\ell_1$-based tests are still competitive or superior in power and often faster than existing methods, especially compared to quadratic-time $\ell_2$-based MMD.

Key Results

  • Improved Power: Across synthetic and real-world experiments, the $\ell_1$-based tests (particularly the optimized versions, L1-opt-ME and L1-opt-SCF) consistently demonstrated higher test power than their $\ell_2$-based counterparts (ME-full, SCF-full) and MMD-based tests, especially at smaller sample sizes or in challenging scenarios (e.g., GVD, Blobs, high dimensions).
  • Efficiency: The proposed methods achieve competitive or better power with potentially faster computation, especially when compared to quadratic-time MMD.
  • High-Dimensional Performance: In high-dimensional settings, the $\ell_1$-based tests showed a clear benefit, maintaining good power where other methods degraded.
  • Interpretability: The optimized test locations provided insights into the differences between distributions, as illustrated in Figure 3.
  • Conservatism: In some cases (e.g., SG problem), the $\ell_1$-ME tests were observed to be more conservative, exhibiting lower type-I errors than specified.

Limitations and Future Work

  • Optimization Complexity: While optimizing test locations is beneficial, it can be computationally intensive, especially for a large number of locations ($J$). The paper notes that this optimization leads to non-smooth objective functions.
  • Generalization to other metrics: The paper focuses on $\ell_1$ and $\ell_2$ norms. Future work could explore other $p$-norms or different distance metrics on distribution embeddings.
  • Goodness-of-fit testing: The authors suggest extending their $\ell_1$ geometry framework to goodness-of-fit testing, where $\ell_1$ geometry has shown empirical promise.
  • Theoretical guarantees for SCF: While the SCF test is proposed, the theoretical analysis for its $\ell_1$ variant is less detailed than for the ME-based test.
  • Computational cost of quantiles: For some statistics, computing the exact null distribution quantiles remains computationally challenging, necessitating bootstrap or permutation procedures.

The paper concludes that the $\ell_1$ geometry offers a significant advantage for kernel two-sample testing, providing a powerful and often more efficient alternative to existing $\ell_2$-based methods.

Summary updated

BibTeX
@inproceedings{2019comparing,
  title = {{Comparing distributions: $\textbackslash\{\}ell\_1$ geometry improves kernel two-sample testing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure