Fast Two-Sample Testing with Analytic Representations of Probability Measures

By Kacper P. Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, Arthur Gretton. 2015

169 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “In the context of MMD, many recent studies have addressed this issue (Zaremba et al. 2013, Cruz Cortés and Scott 2014, Ji Zhao 2015, Chwialkowski et al. 2015).”
Interpretable Distribution Features with Maximum Testing Power (2016, methodology): “Although the distribution of λ̂n under H1 was not derived, Chwialkowski et al. (2015) showed that if k is analytic, integrable and characteristic (in the sense of Sriperumbudur et al.”
A Kernel Test of Goodness of Fit (2016, methodology): “An L2 distance between Parzen window estimates can also be used (Bowman & Foster, 1993), giving the same expression again, although the optimal choice of (2)An alternative linear-time test, based on differences in analytic functions of the sample and following the recent work of (Chwialkowski et al.”
Revisiting Classifier Two-Sample Tests (2016, methodology): “onal data. Examples of these tests include the MMD test (Gretton et al., 2012a), which looks for differences in the empirical kernel mean embeddings of two samples, and the Mean Embedding test or ME (Chwialkowski et al., 2015; Jitkrittum et al., 2016), which looks for differences in the empirical ke”
A Comprehensive Survey on Transfer Learning (2019, background): “[145] also present the mean embedding test for distribution adaptation.”
Proposal : Scalable , Active and Flexible Learning on Distributions (2015, unknown): “This natural approximation, or its equivalents, have been consideredmany times quite recently (Mehta and Gray 2010; Li and Tsang 2011; Zhao and Meng 2014; Chwialkowski et al. 2015; Flaxman et al. 2015; Jitkrittum et al. 2015; Lopez-Paz et al. 2015; Sutherland, J. B. Oliva, et al. 2015; Sutherland an”
Learning Deep Kernels for Non-Parametric Two-Sample Tests (2020, methodology): “There are also several closely related methods, including tests based on checking for differences in mean embeddings evaluated at specific locations (Chwialkowski et al., 2015; Jitkrittum et al., 2016) and kernel Fisher discriminant analysis (Harchaoui et al.”
Transferable Representation Learning with Deep Adaptation Networks (2019, methodology): “The ME test [14] is a form of Hotelling’s T-squared statistic to compare distributions.”
Large-scale kernel methods for independence testing (2016, methodology): “Random Fourier feature (RFF) approximations [28], however, due to their relationship with evaluations of empirical characteristic functions, do have a rich history in the context of statistical testing – as discussed in [9], which also proposes an approach to scale up kernel-based two sample tests b”
Under Review as a Conference Paper at Iclr 2017 Learning in Implicit Generative Models (2017, methodology): “Sriperumbudur et al. (2009) showed that f -divergences and integral probability metrics (MMD, Wasserstein) intersect only at the total variation distance.”