# A Permutation-free Kernel Two-Sample Test

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 27 Nov 2022.

## Builds on (most cited first, 8 of 8)

- [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)
- [A Witness Two-Sample Test](https://mlsanity.com/paper/2102.05573/) (2021)
- [On the Optimality of Gaussian Kernel Based Nonparametric Tests against Smooth Alternatives](https://mlsanity.com/paper/1909.03302/) (2019)
- [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)
- [Dimension-agnostic inference using cross U-statistics](https://mlsanity.com/paper/2011.05068/) (2020)
- [Comparing a Large Number of Multivariate Distributions](https://mlsanity.com/paper/1904.05741/) (2019)

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

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [Compress Then Test: Powerful Kernel Testing in Near-linear Time](https://mlsanity.com/paper/2301.05974/) (2023)
- [A Practical Introduction to Kernel Discrepancies: MMD, HSIC & KSD](https://mlsanity.com/paper/2503.04820/) (2025)
- [A Permutation-Free Kernel Independence Test](https://mlsanity.com/paper/2212.09108/) (2022)
- [Boosting the Power of Kernel Two-Sample Tests](https://mlsanity.com/paper/2302.10687/) (2023)
- [An Efficient Doubly-Robust Test for the Kernel Treatment Effect](https://mlsanity.com/paper/2304.13237/) (2023)
- [A Bias-Variance-Covariance Decomposition of Kernel Scores for Generative Models](https://mlsanity.com/paper/2310.05833/) (2023)
- [Robust Kernel Hypothesis Testing under Data Corruption](https://mlsanity.com/paper/2405.19912/) (2024)
- [A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations](https://mlsanity.com/paper/2502.13570/) (2025)
- [A High-dimensional Convergence Theorem for U-statistics with Applications to Kernel-based Testing](https://mlsanity.com/paper/2302.05686/) (2023)
- [Locally minimax optimal confidence sets for the best model](https://mlsanity.com/paper/2503.21639/) (2025)
- [Kernel Embeddings and the Separation of Measure Phenomenon](https://mlsanity.com/paper/2505.04613/) (2025)
- [Post Hoc Inference for Component Attribution in Multivariate Change-Point Detection](https://mlsanity.com/paper/2607.14814/) (2026)
- [Permutation-Free High-Order Interaction Tests](https://mlsanity.com/paper/2506.05963/) (2025)
- [Likelihood Ratio Tests by Kernel Gaussian Embedding](https://mlsanity.com/paper/2508.07982/) (2025)
- [Anchor-based Maximum Discrepancy for Relative Similarity Testing](https://mlsanity.com/paper/2510.10477/) (2025)
- [Minimax-Optimal Two-Sample Test with Sliced Wasserstein](https://mlsanity.com/paper/2510.27498/) (2025)
- [Maximum Mean Discrepancy with Unequal Sample Sizes via Generalized U-Statistics](https://mlsanity.com/paper/2512.13997/) (2025)
- [Are Two Datasets Close Enough With Statistical Significance? A Kernel Distributional Closeness Testing Approach](https://mlsanity.com/paper/2507.12843/) (2025)
- [Kernel Two-Sample Testing via Directional Components Analysis](https://mlsanity.com/paper/2508.08564/) (2025)
- [Data Fusion with Distributional Equivalence Test-then-pool](https://mlsanity.com/paper/2603.11867/) (2026)

## Abstract (arXiv)

The kernel Maximum Mean Discrepancy~(MMD) is a popular multivariate distance metric between distributions that has found utility in two-sample testing. The usual kernel-MMD test statistic is a degenerate U-statistic under the null, and thus it has an intractable limiting distribution. Hence, to design a level-α test, one usually selects the rejection threshold as the (1-α)-quantile of the permutation distribution. The resulting nonparametric test has finite-sample validity but suffers from large computational cost, since every permutation takes quadratic time. We propose the cross-MMD, a new quadratic-time MMD test statistic based on sample-splitting and studentization. We prove that under mild assumptions, the cross-MMD has a limiting standard Gaussian distribution under the null. Importantly, we also show that the resulting test is consistent against any fixed alternative, and when using the Gaussian kernel, it has minimax rate-optimal power against local alternatives. For large sample sizes, our new cross-MMD provides a significant speedup over the MMD, for only a slight loss in power.