A Fast, Consistent Kernel Two-Sample Test

Abstract

A kernel embedding of probability distributions into reproducing kernel Hilbert\nspaces (RKHS) has recently been proposed, which allows the comparison of two\nprobability measures P and Q based on the distance between their respective embeddings:\nfor a sufficiently rich RKHS, this distance is zero if and only if P and\nQ coincide. In using this distance as a statistic for a test of whether two samples\nare from different distributions, a major difficulty arises in computing the significance\nthreshold, since the empirical statistic has as its null distribution (where\nP = Q) an infinite weighted sum of x2 random variables. Prior finite sample\napproximations to the null distribution include using bootstrap resampling, which\nyields a consistent estimate but is computationally costly; and fitting a parametric\nmodel with the low order moments of the test statistic, which can work well in\npractice but has no consistency or accuracy guarantees. The main result of the\npresent work is a novel estimate of the null distribution, computed from the eigenspectrum\nof the Gram matrix on the aggregate sample from P and Q, and having\nlower computational cost than the bootstrap. A proof of consistency of this estimate\nis provided. The performance of the null distribution estimate is compared\nwith the bootstrap and parametric approaches on an artificial example, high dimensional\nmultivariate data, and text.