# Fast Two-Sample Testing with Analytic Representations of Probability Measures

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2015.

## Built on by (most cited first, 30 of 53)

- [The "Beatrix'' Resurrections: Robust Backdoor Detection via Gram Matrices](https://mlsanity.com/paper/2209.11715/) (2022)
- [Calibrated Selective Classification](https://mlsanity.com/paper/2208.12084/) (2022)
- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [A Witness Two-Sample Test](https://mlsanity.com/paper/2102.05573/) (2021)
- [PEARL: Data Synthesis via Private Embeddings and Adversarial Reconstruction Learning](https://mlsanity.com/paper/2106.04590/) (2021)
- [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)
- [Calibration tests beyond classification](https://mlsanity.com/paper/2210.13355/) (2022)
- [Meta Two-Sample Testing: Learning Kernels for Testing with Limited Data](https://mlsanity.com/paper/2106.07636/) (2021)
- [Neural Tangent Kernel Maximum Mean Discrepancy](https://mlsanity.com/paper/2106.03227/) (2021)
- [PCF-GAN: generating sequential data via the characteristic function of measures on the path space](https://mlsanity.com/paper/2305.12511/) (2023)
- [Compress Then Test: Powerful Kernel Testing in Near-linear Time](https://mlsanity.com/paper/2301.05974/) (2023)
- [An Asymptotic Test for Conditional Independence using Analytic Kernel Embeddings](https://mlsanity.com/paper/2110.14868/) (2021)
- [CADet: Fully Self-Supervised Out-Of-Distribution Detection With Contrastive Learning](https://mlsanity.com/paper/2210.01742/) (2022)
- [E-Valuating Classifier Two-Sample Tests](https://mlsanity.com/paper/2210.13027/) (2022)
- [Boosting the Power of Kernel Two-Sample Tests](https://mlsanity.com/paper/2302.10687/) (2023)
- [Context-Aware Drift Detection](https://mlsanity.com/paper/2203.08644/) (2022)
- [Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples](https://mlsanity.com/paper/2103.00394/) (2021)
- [Kernel Two-Sample Tests for Manifold Data](https://mlsanity.com/paper/2105.03425/) (2021)
- [Characteristic Circuits](https://mlsanity.com/paper/2312.07790/) (2023)
- [Quantization Algorithms for Random Fourier Features](https://mlsanity.com/paper/2102.13079/) (2021)
- [Variable Selection for Kernel Two-Sample Tests](https://mlsanity.com/paper/2302.07415/) (2023)
- [Deep anytime-valid hypothesis testing](https://mlsanity.com/paper/2310.19384/) (2023)
- [Kernel Robust Hypothesis Testing](https://mlsanity.com/paper/2203.12777/) (2022)
- [A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations](https://mlsanity.com/paper/2502.13570/) (2025)
- [DUAL: Learning Diverse Kernels for Aggregated Two-sample and Independence Testing](https://mlsanity.com/paper/2510.11140/) (2025)
- [Nystr"om M-Hilbert-Schmidt Independence Criterion](https://mlsanity.com/paper/2302.09930/) (2023)
- [A Unified View of Optimal Kernel Hypothesis Testing](https://mlsanity.com/paper/2503.07084/) (2025)
- [Nystr"om Kernel Stein Discrepancy](https://mlsanity.com/paper/2406.08401/) (2024)

## Abstract (arXiv)

We propose a class of nonparametric two-sample tests with a cost linear in the sample size. Two tests are given, both based on an ensemble of distances between analytic functions representing each of the distributions. The first test uses smoothed empirical characteristic functions to represent the distributions, the second uses distribution embeddings in a reproducing kernel Hilbert space. Analyticity implies that differences in the distributions may be detected almost surely at a finite number of randomly chosen locations/frequencies. The new tests are consistent against a larger class of alternatives than the previous linear-time tests based on the (non-smoothed) empirical characteristic functions, while being much faster than the current state-of-the-art quadratic-time kernel-based or energy distance-based tests. Experiments on artificial benchmarks and on challenging real-world testing problems demonstrate that our tests give a better power/time tradeoff than competing approaches, and in some cases, better outright power than even the most expensive quadratic-time tests. This performance advantage is retained even in high dimensions, and in cases where the difference in distributions is not observable with low order statistics.