Abstract
The Maximum Mean Discrepancy (MMD) has been the state-of-the-art nonparametric test for tackling the two-sample problem. Its statistic is given by the difference in expectations of the witness function, a real-valued function defined as a weighted sum of kernel evaluations on a set of basis points. Typically the kernel is optimized on a training set, and hypothesis testing is performed on a separate test set to avoid overfitting (i.e., control type-I error). That is, the test set is used to simultaneously estimate the expectations and define the basis points, while the training set only serves to select the kernel and is discarded. In this work, we propose to use the training data to also define the weights and the basis points for better data efficiency. We show that 1) the new test is consistent and has a well-controlled type-I error; 2) the optimal witness function is given by a precision-weighted mean in the reproducing kernel Hilbert space associated with the kernel; and 3) the test power of the proposed test is comparable or exceeds that of the MMD and other modern tests, as verified empirically on challenging synthetic and real problems (e.g., Higgs data).
Introduction
The two-sample problem is a foundational task in statistics: given two sets of data, do they originate from the same probability distribution? This problem is central to various fields, from bioinformatics to A/B testing. Currently, the Maximum Mean Discrepancy (MMD) is the gold standard for nonparametric testing. However, standard MMD-based tests are often data-inefficient. Typically, researchers split their data into a training set to select an appropriate kernel and a test set to perform the actual hypothesis test. In this paradigm, the training data is discarded after the kernel is chosen.
We introduce the Witness Two-Sample Test (WiTS), which improves statistical power by more effectively utilizing the training data. Instead of merely selecting a kernel, WiTS uses the training set to learn an optimal one-dimensional "witness function" that acts as a custom-tailored detector for the differences between the two specific datasets.
Methodology
The WiTS framework operates in a two-stage process:
- Stage I (Learning): On a training set $\mathbb{Z}_{\text{tr}}$, we learn a witness function $h$. The objective is to maximize the Signal-to-Noise Ratio (SNR), essentially finding the direction in the feature space where the two distributions are most distinct relative to their variance.
- Stage II (Testing): On a held-out test set $\mathbb{Z}_{\text{te}}$, we calculate the difference in the means of the witness function applied to the two samples to determine if the null hypothesis can be rejected.
A key contribution is the KFDA-Witness approach. By utilizing a Reproducing Kernel Hilbert Space (RKHS), the optimal witness function is derived via Kernel Fisher Discriminant Analysis (KFDA). This results in a "precision-weighted" mean embedding—it doesn't just look at the difference in means, but weights that difference by the inverse of the covariance to ignore noisy directions. Because the witness function is fixed after Stage I, the test statistic in Stage II is asymptotically normal, allowing for analytic test thresholds.
Empirical Evaluation
The researchers evaluated WiTS on two primary benchmarks:
- Blobs: A synthetic dataset consisting of a grid of Gaussian mixtures. It is designed to be difficult because the distributions have the same mean but different rotations or covariances, making simple tests fail.
- HIGGS: A high-dimensional real-world dataset from high-energy physics. The task is to distinguish between "background" physical processes and those that produce Higgs bosons.
As shown in the results, KFDA-Witness significantly outperforms standard MMD and deep-learning-based classifier tests (C2ST) on the Blobs dataset. In the HIGGS physics benchmark, WiTS achieved higher rejection rates than other modern tests like MMD-D (Deep MMD), demonstrating superior sensitivity to subtle signals.
Key Insights and Discussion
The "aha" moment of this work is that the standard MMD witness function is simply the difference of mean embeddings. WiTS improves this by applying a "precision" term $(\Sigma + \lambda I)^{-1}$. This de-emphasizes directions in the feature space where the data is naturally noisy, making the actual signal of the difference stand out.
By reducing the problem to a single, well-optimized 1D projection, WiTS provides a simpler theoretical framework and better data efficiency. While the authors generally recommend a 50/50 split between training and testing data, the optimal ratio can vary by dataset. Future work could explore using deep neural networks to learn the witness function directly using the SNR objective, extending the framework beyond kernel methods.
Summary updated