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

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2014.

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

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [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)
- [Fair Representation: Guaranteeing Approximate Multiple Group Fairness for Unknown Tasks](https://mlsanity.com/paper/2109.00545/) (2021)
- [Compress Then Test: Powerful Kernel Testing in Near-linear Time](https://mlsanity.com/paper/2301.05974/) (2023)
- [A Practical Guide to Sample-based Statistical Distances for Evaluating Generative Models in Science](https://mlsanity.com/paper/2403.12636/) (2024)
- [Learning Domain Invariant Representations in Goal-conditioned Block MDPs](https://mlsanity.com/paper/2110.14248/) (2021)
- [Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples](https://mlsanity.com/paper/2103.00394/) (2021)
- [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)
- [The Conditional Cauchy-Schwarz Divergence with Applications to Time-Series Data and Sequential Decision Making](https://mlsanity.com/paper/2301.08970/) (2023)
- [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)
- [Error Estimation for Random Fourier Features](https://mlsanity.com/paper/2302.11174/) (2023)
- [Kernel-based potential mean-field games with unbiased random Fourier U-statistics](https://mlsanity.com/paper/2605.29371/) (2026)
- [Finite-Sample Unbiased Variance of MMD under Unbalanced Sampling: Exact Estimation and Quasi-Linear Computation](https://mlsanity.com/paper/2601.13874/) (2026)
- [A Splitting Method for SDE Terminal-Law Estimation](https://mlsanity.com/paper/2609.12513/) (2026)

## Abstract (arXiv)

The maximum mean discrepancy (MMD) is a recently proposed test statistic for 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 of Fourier transform, FastMMD decreases the time complexity for MMD calculation from O(N2 d) to O(L N d), 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 which determines the approximation accuracy. For kernels that are spherically invariant, the computation can be further accelerated to O(L N log d) by using the Fastfood technique (Le et al., 2013). The uniform convergence of our method has also been theoretically proved in both unbiased and biased estimates. We have further provided a geometric explanation for our method, namely ensemble of circular discrepancy, which facilitates us to understand the insight of MMD, and is hopeful to help arouse more extensive metrics for assessing two-sample test. Experimental results substantiate that FastMMD is with similar accuracy as exact MMD, while with faster computation speed and lower variance than the existing MMD approximation methods.