An Optimal Witness Function for Two-Sample Testing

Jonas M. Kübler, Wittawat Jitkrittum, Bernhard Schölkopf, Krikamol Muandet

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 data originate from the same distribution—is a fundamental challenge in statistics and machine learning. Applications range from detecting data drift in production environments to identifying signals in bioinformatics. The current state-of-the-art approach is the Maximum Mean Discrepancy (MMD), which typically involves splitting data into a training set for kernel selection and a test set for the hypothesis test. However, this standard approach is often data-inefficient, as the training data is discarded after kernel selection, and MMD's reliance on high-dimensional feature spaces can introduce significant noise.

The Witness Two-Sample Test (WiTS)

The proposed Witness Two-Sample Test (WiTS) addresses these inefficiencies by explicitly learning an optimal witness function from the training data. Rather than just "picking a kernel," WiTS uses training data to define the weights and basis points of a one-dimensional projection that maximizes the signal-to-noise ratio (SNR).

Two-Stage Framework

The WiTS test operates in a two-stage framework. In Stage I, training data is used to learn a witness function $h$ that maximizes the SNR. In a Reproducing Kernel Hilbert Space (RKHS), this objective is equivalent to performing Kernel Fisher Discriminant Analysis (KFDA). In Stage II, the fixed witness function $h$ is applied to the held-out test data. The test statistic is simply the difference in average values of $h$ between the two samples. Because $h$ is fixed before seeing the test data, the test statistic follows a simple normal distribution, simplifying the calculation of p-values.

Algorithm for the Witness Two-Sample Test showing the two-stage process of optimizing the witness function and performing the permutation test.

To handle large-scale data, the authors implement KFDA-WITNESS using the "FdaFalkon" algorithm, which utilizes Nyström approximations and conjugate gradient methods to avoid the $O(N^3)$ cost of traditional kernel methods.

Empirical Results

The authors evaluated WiTS against several baselines, including deep MMD and classifier-based tests, on synthetic and real-world datasets such as the "Blobs" synthetic grid and the HIGGS high-energy physics dataset.

Key Findings

WiTS, specifically the KFDA-Witness variant, consistently achieved higher rejection rates (test power) than standard MMD and deep-learning-based MMD (MMD-D) across various sample sizes. On the HIGGS dataset, WiTS outperformed several modern benchmarks, including Classifier-to-Sample Tests (C2ST), proving its effectiveness on high-dimensional, real-world data.

Comparison of testing methods and performance metrics. The table summarizes the properties of various witness-based tests, while the plots illustrate the impact of splitting ratios and sample sizes on rejection rates.

Experiments regarding the splitting ratio $r$ suggested that a 50/50 split is generally robust. However, when distributions are very similar, allocating slightly more data to training the witness function can be beneficial for maximizing testing power.

Conclusion

By shifting the focus from coarse kernel selection to fine-grained learning of an optimal witness function, WiTS provides a more data-efficient and powerful framework for two-sample testing. While the method requires data splitting to maintain Type-I error control, its superior performance on complex datasets like HIGGS demonstrates its practical utility. Future directions include extending the witness framework to other function classes, such as neural network architectures tailored for domain-specific data like graphs or sequences.

Summary updated

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).
BibTeX
@inproceedings{kubler2022optimal,
  author = {Jonas M. Kübler and Wittawat Jitkrittum and Bernhard Schölkopf and Krikamol Muandet},
  title = {{An Optimal Witness Function for Two-Sample Testing}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=H5zCSZeBc7},
}
Figure