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:
- Computational Cost: Standard MMD scales quadratically ($O(n^2)$) with the number of samples, making it sluggish for large datasets.
- 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.
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).
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