FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test

By Ji Zhao, Deyu Meng. 2014

108 citations recorded by the source corpus.

The maximum mean discrepancy (MMD) is a recently proposed test statistic for the two-sample test. Its quadratic time complexity, however, greatly hampers its availability to large-scale applications. To accelerate the MMD calculation, in this study we propose an efficient method called FastMMD. The core idea of FastMMD is to equivalently transform the MMD with shift-invariant kernels into the amplitude expectation of a linear combination of sinusoid components based on Bochner’s theorem and Fourier transform (Rahimi & Recht, 2007). Taking advantage of sampling the Fourier transform, FastMMD decreases the time complexity for MMD calculation from to , where N and d are the size and dimension of the sample set, respectively. Here, L is the number of basis functions for approximating kernels that determines the approximation accuracy. For kernels that are spherically invariant, the computation can be further accelerated to by using the Fastfood technique (Le, Sarlós, & Smola, 2013). The uniform convergence of our method has also been theoretically proved in both unbiased and biased estimates. We also provide a geometric explanation for our method, ensemble of circular discrepancy, which helps us understand the insight of MMD and we hope will lead to more extensive metrics for assessing the two-sample test task. Experimental results substantiate that the accuracy of FastMMD is similar to that of MMD and with faster computation and lower variance than existing MMD approximation methods.

Subfields: Statistics and Probability, Evaluation & Benchmarks

How researchers see this paper

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

In Statistics and Probability

In Evaluation & Benchmarks

Citations in the corpus

Generative Moment Matching Networks (2015, background): “This idea was recently explored for MMD in (Zhao & Meng, 2014).”
The Variational Fair Autoencoder (2015, background): “Zhao & Meng (2015) have successfully applied the idea of using random kitchen sinks to approximate MMD.”
Fast Two-Sample Testing with Analytic Representations of Probability Measures (2015, background): “In the statistical testing literature, the quantity d ϕ,J ( P, Q ) predates the MMD by a considerable time, and was studied in [12, 13, 7], and more recently revisited in [32].”
On the Error of Random Fourier Features (2015, neutral): “˜ z performs mildly better than ˘ z .”
Central Moment Discrepancy (CMD) for Domain-Invariant Representation Learning (2017, methodology): “In contrast, the authors in Zhuang et al. (2015) do so by minimizing a modified version of the Kullback-Leibler divergence of the mean activations (MKL).”
Learning Implicit Generative Models with the Method of Learned Moments (2018, background): “From Bochner’s Theorem for real kernels (Zhao and Meng, 2015): When K (0) = 1 , p ( ω ) is a probability measure.”
Smart Regularization of Deep Architectures (2015, methodology): “The idea of using random kitchen sinks has been successfully applied to approximate MMD in [30].”
Large-scale kernel methods for independence testing (2016, methodology): “Moreover, the approximation strategy of MMD and two-sample testing through primal representation using RFF have also been studied in [50, 42, 21].”
Multivariate Rank-Based Distribution-Free Nonparametric Testing Using Measure Transportation (2019, background): “[157] Zhao, J.”
Learning Domain Invariant Representations in Goal-conditioned Block MDPs (2021, methodology): “Then we use the following loss as a computationally efficient approximation of the MMD metric [32, 27].”