# Finite-Sample Unbiased Variance of MMD under Unbalanced Sampling: Exact Estimation and Quasi-Linear Computation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 20 Jan 2026.

## Builds on (most cited first, 9 of 9)

- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Learning Deep Kernels for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2002.09116/) (2020)
- [MMD Aggregated Two-Sample Test](https://mlsanity.com/paper/2110.15073/) (2021)
- [FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test](https://mlsanity.com/paper/1405.2664/) (2014)
- [Fast Computing for Distance Covariance](https://mlsanity.com/paper/1410.1503/) (2014)
- [MMD-B-Fair: Learning Fair Representations with Statistical Testing](https://mlsanity.com/paper/2211.07907/) (2022)
- [One-Class Support Measure Machines for Group Anomaly Detection](https://mlsanity.com/paper/1303.0309/) (2013)
- [Unbiased estimators for the variance of MMD estimators](https://mlsanity.com/paper/1906.02104/) (2019)
- [Maximum Mean Discrepancy with Unequal Sample Sizes via Generalized U-Statistics](https://mlsanity.com/paper/2512.13997/) (2025)

## Abstract (arXiv)

Accurately and efficiently estimating the variance of the Maximum Mean Discrepancy (MMD) remains challenging, particularly for unbalanced sample sizes. In this paper, we derive a finite-sample unbiased estimator of the MMD variance. To overcome the traditional O(N2) computational bottleneck, we develop a recursive prefix-suffix accumulation scheme for the Laplace kernel, reducing the computational complexity to O(N log N) while requiring O(N) memory. Experimental results verify the theoretical exactness and numerical stability of the proposed estimator and demonstrate its scalability on large datasets. Furthermore, the method proves effective for monitoring distributional convergence during the training of Time-series Generative Adversarial Networks (TimeGAN).