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

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 n^2 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. Building on the same principle, we also develop near-linear time procedures for aggregating multiple kernel tests and estimating asymptotic test variance. On our real and simulated data experiments, CTT provides 100--200x speed-ups over state-of-the-art approximate MMD tests with no loss of power.