# Compress Then Test: Powerful Kernel Testing in Near-linear Time

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 55 references that are in the map.
- First posted on arXiv 14 Jan 2023.

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

- [EMNIST: an extension of MNIST to handwritten letters](https://mlsanity.com/paper/1702.05373/) (2017)
- [Learning Deep Kernels for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2002.09116/) (2020)
- [Generative Models and Model Criticism via Optimized Maximum Mean Discrepancy](https://mlsanity.com/paper/1611.04488/) (2016)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [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)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Two-sample Testing Using Deep Learning](https://mlsanity.com/paper/1910.06239/) (2019)
- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [A Permutation-free Kernel Two-Sample Test](https://mlsanity.com/paper/2211.14908/) (2022)
- [Learning Kernel Tests Without Data Splitting](https://mlsanity.com/paper/2006.02286/) (2020)
- [Distribution Compression in Near-linear Time](https://mlsanity.com/paper/2111.07941/) (2021)
- [FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test](https://mlsanity.com/paper/1405.2664/) (2014)
- [Post Selection Inference with Incomplete Maximum Mean Discrepancy Estimator](https://mlsanity.com/paper/1802.06226/) (2018)
- [The Mean and Median Criterion for Automatic Kernel Bandwidth Selection for Support Vector Data Description](https://mlsanity.com/paper/1708.05106/) (2017)

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

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [The Representation Jensen-Shannon Divergence](https://mlsanity.com/paper/2305.16446/) (2023)
- [KerJEPA: Kernel Discrepancies for Euclidean Self-Supervised Learning](https://mlsanity.com/paper/2512.19605/) (2025)
- [Robust Kernel Hypothesis Testing under Data Corruption](https://mlsanity.com/paper/2405.19912/) (2024)
- [Low-Rank Thinning](https://mlsanity.com/paper/2502.12063/) (2025)
- [A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations](https://mlsanity.com/paper/2502.13570/) (2025)
- [A Unified View of Optimal Kernel Hypothesis Testing](https://mlsanity.com/paper/2503.07084/) (2025)
- [Efficient and Accurate Explanation Estimation with Distribution Compression](https://mlsanity.com/paper/2406.18334/) (2024)
- [Supervised Kernel Thinning](https://mlsanity.com/paper/2410.13749/) (2024)
- [Kernel-Based Evaluation of Conditional Biological Sequence Models](https://mlsanity.com/paper/2510.15601/) (2025)
- [Minimax-Optimal Two-Sample Test with Sliced Wasserstein](https://mlsanity.com/paper/2510.27498/) (2025)
- [Partial identification of kernel based two sample tests with mismeasured data](https://mlsanity.com/paper/2308.03570/) (2023)
- [Flexible and Efficient Drift Detection without Labels](https://mlsanity.com/paper/2506.08734/) (2025)
- [Stein Kernelized Molecular Dynamics for Active Learning of Interatomic Potentials](https://mlsanity.com/paper/2606.04100/) (2026)

## Abstract (arXiv)

Kernel two-sample testing provides a powerful framework for distinguishing any pair of distributions based on n sample points. However, existing kernel tests either run in n2 time or sacrifice undue power to improve runtime. To address these shortcomings, we introduce Compress Then Test (CTT), a new framework for high-powered kernel testing based on sample compression. CTT cheaply approximates an expensive test by compressing each n point sample into a small but provably high-fidelity coreset. For standard kernels and subexponential distributions, CTT inherits the statistical behavior of a quadratic-time test -- recovering the same optimal detection boundary -- while running in near-linear time. We couple these advances with cheaper permutation testing, justified by new power analyses; improved time-vs.-quality guarantees for low-rank approximation; and a fast aggregation procedure for identifying especially discriminating kernels. In our experiments with real and simulated data, CTT and its extensions provide 20--200x speed-ups over state-of-the-art approximate MMD tests with no loss of power.