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—determining whether two sets of samples originate from the same probability distribution—is a foundational task in statistics and machine learning. It is critical for applications ranging from bioinformatics to detecting data drift in production models. Currently, the Maximum Mean Discrepancy (MMD) is the gold standard for nonparametric testing. However, standard MMD workflows often suffer from data inefficiency. Typically, researchers split their data: a training set is used to select an optimal kernel, and then discarded to avoid overfitting. The actual hypothesis test is performed on a separate test set, where the "witness function"—the mathematical proof of the difference between distributions—is recalculated from scratch. This paper introduces the Witness Two-Sample Test (WiTS) to address this inefficiency by leveraging training data to learn the witness function itself.
Methodology
The WiTS framework operates in two distinct stages to maximize data utility while maintaining rigorous control over Type-I error:
- Stage I (Learning): Instead of merely selecting a kernel, the training data is used to learn an optimal witness function ($h$). The authors define "optimal" as the function that maximizes the Signal-to-Noise Ratio (SNR) of the test statistic.
- Stage II (Testing): This fixed function $h$ is then applied to the held-out test data. Because $h$ was learned on independent data, the test statistic follows a simple distribution, facilitating straightforward p-value calculation.
A key technical contribution is showing that when the witness function is optimized within a Reproducing Kernel Hilbert Space (RKHS), the solution is a precision-weighted mean, directly connecting two-sample testing to Kernel Fisher Discriminant Analysis (KFDA). Unlike standard MMD, the KFDA-witness "down-weights" directions in the feature space with high noise, making the signal of the distributional difference more apparent.
Experimental Results
The authors evaluated WiTS against several baselines, including deep MMD and classifier-based tests, using challenging synthetic datasets (e.g., "Blobs") and high-dimensional real-world data (e.g., the Higgs dataset from particle physics).
Key Findings: * Higher Power: On the Blobs dataset, the KFDA-witness reached a rejection rate (test power) of nearly 1.0 with far fewer samples than standard MMD or even "Deep MMD" variants. * Statistical Consistency: The authors proved that the test is consistent, meaning the probability of correctly detecting a difference approaches 100% as more data is provided. * Computational Efficiency: Because the Stage II test statistic is a simple difference of means of a fixed function, the null distribution can be simulated via permutations much faster than MMD-based tests.
Discussion and Future Work
While WiTS offers significant gains, it introduces practical considerations such as the data splitting ratio. While a 50/50 split is generally recommended, the optimal ratio remains an open question. Additionally, the KFDA-witness relies on a regularization parameter ($\lambda$) that requires careful cross-validation to avoid overfitting. Future work could involve extending the SNR-maximization objective to deep neural network architectures to further enhance representation learning in two-sample testing.
Summary updated