Two-sample hypothesis testing-determining whether two sets of data are drawn from the same distribution-is a fundamental problem in statistics and machine learning with broad scientific applications. In the context of nonparametric testing, maximum mean discrepancy (MMD) has gained popularity as a test statistic due to its flexibility and strong theoretical foundations. However, its use in large-scale scenarios is plagued by high computational costs. I will show how a Nyström approximation of the MMD can be used to design a computationally efficient and practical testing algorithm while preserving statistical guarantees. I will present some techniques we used to obtain a finite-sample bound on the power of our permutation-based test and discuss its optimality.

Based on a joint work with Antoine Chatalic, Marco Letizia, and Lorenzo Rosasco (https://arxiv.org/abs/2502.13570v2)