# A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations

arXiv: https://arxiv.org/abs/2502.13570 · HTML: https://mlsanity.com/paper/2502.13570/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 71 references that are in the map.
- First posted on arXiv 19 Feb 2025.

## Builds on (most cited first, 30 of 32)

- [MMD Aggregated Two-Sample Test](https://mlsanity.com/paper/2110.15073/) (2021)
- [Interpretable Distribution Features with Maximum Testing Power](https://mlsanity.com/paper/1605.06796/) (2016)
- [Fast Two-Sample Testing with Analytic Representations of Probability Measures](https://mlsanity.com/paper/1506.04725/) (2015)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Kernel Distribution Embeddings: Universal Kernels, Characteristic Kernels and Kernel Metrics on Distributions](https://mlsanity.com/paper/1604.05251/) (2016)
- [CaloChallenge 2022: A Community Challenge for Fast Calorimeter Simulation](https://mlsanity.com/paper/2410.21611/) (2024)
- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [Large-Scale Kernel Methods for Independence Testing](https://mlsanity.com/paper/1606.07892/) (2016)
- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [Random Feature Stein Discrepancies](https://mlsanity.com/paper/1806.07788/) (2018)
- [A Witness Two-Sample Test](https://mlsanity.com/paper/2102.05573/) (2021)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [On the Optimality of Gaussian Kernel Based Nonparametric Tests against Smooth Alternatives](https://mlsanity.com/paper/1909.03302/) (2019)
- [Learning new physics efficiently with nonparametric methods](https://mlsanity.com/paper/2204.02317/) (2022)
- [A Permutation-free Kernel Two-Sample Test](https://mlsanity.com/paper/2211.14908/) (2022)
- [AutoML Two-Sample Test](https://mlsanity.com/paper/2206.08843/) (2022)
- [Spectral Regularized Kernel Two-Sample Tests](https://mlsanity.com/paper/2212.09201/) (2022)
- [On the Optimality of Kernel-Embedding Based Goodness-of-Fit Tests](https://mlsanity.com/paper/1709.08148/) (2017)
- [FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test](https://mlsanity.com/paper/1405.2664/) (2014)
- [Adaptivity and Computation-Statistics Tradeoffs for Kernel and Distance based High Dimensional Two Sample Testing](https://mlsanity.com/paper/1508.00655/) (2015)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [Compress Then Test: Powerful Kernel Testing in Near-linear Time](https://mlsanity.com/paper/2301.05974/) (2023)
- [Post Selection Inference with Incomplete Maximum Mean Discrepancy Estimator](https://mlsanity.com/paper/1802.06226/) (2018)
- [Relating Leverage Scores and Density using Regularized Christoffel Functions](https://mlsanity.com/paper/1805.07943/) (2018)
- [Differentially Private Permutation Tests](https://mlsanity.com/paper/2310.19043/) (2023)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Refereeing the Referees: Evaluating Two-Sample Tests for Validating Generators in Precision Sciences](https://mlsanity.com/paper/2409.16336/) (2024)
- [Nystr"om landmark sampling and regularized Christoffel functions](https://mlsanity.com/paper/1905.12346/) (2019)
- [Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features](https://mlsanity.com/paper/2407.08976/) (2024)

## Built on by (most cited first, 6 of 6)

- [DriftXpress: Faster Drifting Models via Projected RKHS Fields](https://mlsanity.com/paper/2605.12183/) (2026)
- [Nystr"om Kernel Stein Discrepancy Tests](https://mlsanity.com/paper/2605.25173/) (2026)
- [Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD](https://mlsanity.com/paper/2607.24235/) (2026)
- [Minimax-Optimal Two-Sample Test with Sliced Wasserstein](https://mlsanity.com/paper/2510.27498/) (2025)
- [Sparse, self-organizing ensembles of local kernels detect rare statistical anomalies](https://mlsanity.com/paper/2511.03095/) (2025)
- [Kernel-based External Validity of Experimental Studies](https://mlsanity.com/paper/2610.13625/) (2026)

## Abstract (arXiv)

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. In this work, we use a Nystr"om approximation of the MMD to design a computationally efficient and practical testing algorithm while preserving statistical guarantees. Our main result is a finite-sample bound on the power of the proposed test for distributions that are sufficiently separated with respect to the MMD. The derived separation rate matches the known minimax optimal rate in this setting. We support our findings with a series of numerical experiments, emphasizing applicability to realistic scientific data.