mlsanityData to 14 Oct 2026

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

arXiv 2502.13570 ↗First posted 19 Feb 2025stat.ML cs.LG math.STcited by 6

Not on the map. Why?

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.

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

32 of 71 references.

References · 32

  1. 2021MMD Aggregated Two-Sample Testcited by 75
  2. 2016Interpretable Distribution Features with Maximum Testing Powercited by 63
  3. 2015Fast Two-Sample Testing with Analytic Representations of Probability Measurescited by 53
  4. 2018On Fast Leverage Score Sampling and Optimal Learningcited by 41
  5. 2016Kernel Distribution Embeddings: Universal Kernels, Characteristic Kernels and Kernel Metrics on Distributionscited by 40
  6. 2024CaloChallenge 2022: A Community Challenge for Fast Calorimeter Simulationcited by 35
  7. 2023MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splittingcited by 33
  8. 2016Large-Scale Kernel Methods for Independence Testingcited by 32
  9. 2022Efficient Aggregated Kernel Tests using Incomplete U-statisticscited by 27
  10. 2018Random Feature Stein Discrepanciescited by 23
  11. 2021A Witness Two-Sample Testcited by 23
  12. 2022Nystr"om Kernel Mean Embeddingscited by 22
20 more
  1. 2014Fast Randomized Kernel Methods With Statistical Guaranteescited by 21
  2. 2019On the Optimality of Gaussian Kernel Based Nonparametric Tests against Smooth Alternativescited by 21
  3. 2022Learning new physics efficiently with nonparametric methodscited by 21
  4. 2022A Permutation-free Kernel Two-Sample Testcited by 21
  5. 2022AutoML Two-Sample Testcited by 20
  6. 2022Spectral Regularized Kernel Two-Sample Testscited by 20
  7. 2017On the Optimality of Kernel-Embedding Based Goodness-of-Fit Testscited by 19
  8. 2014FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Testcited by 17
  9. 2015Adaptivity and Computation-Statistics Tradeoffs for Kernel and Distance based High Dimensional Two Sample Testingcited by 14
  10. 2021Fast Statistical Leverage Score Approximation in Kernel Ridge Regressioncited by 14
  11. 2023Compress Then Test: Powerful Kernel Testing in Near-linear Timecited by 14
  12. 2018Post Selection Inference with Incomplete Maximum Mean Discrepancy Estimatorcited by 11
  13. 2018Relating Leverage Scores and Density using Regularized Christoffel Functionscited by 10
  14. 2023Differentially Private Permutation Testscited by 10
  15. 2023Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Samplingcited by 10
  16. 2024Refereeing the Referees: Evaluating Two-Sample Tests for Validating Generators in Precision Sciencescited by 9
  17. 2019Nystr"om landmark sampling and regularized Christoffel functionscited by 8
  18. 2024Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Featurescited by 5
  19. 2020Bayesian Kernel Two-Sample Testingcited by 3
  20. 2023Kernel-Based Testing for Single-Cell Differential Analysiscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 4.

6 papers.

  1. 2026DriftXpress: Faster Drifting Models via Projected RKHS Fieldscited by 3
  2. 2026Nystr"om Kernel Stein Discrepancy Testscited by 2
  3. 2026Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSDcited by 2
  4. 2025Minimax-Optimal Two-Sample Test with Sliced Wassersteincited by 1
  5. 2025Sparse, self-organizing ensembles of local kernels detect rare statistical anomaliescited by 1
  6. 2026Kernel-based External Validity of Experimental Studiescited by 0