A Martingale Kernel Two-Sample Test

Anirban Chatterjee, Aaditya Ramdas
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-44, 2026.

Abstract

The Maximum Mean Discrepancy (MMD) is a widely used multivariate distance metric for two-sample testing. The standard MMD test statistic has an intractable null distribution typically requiring costly resampling or permutation approaches for calibration. In this work we leverage a martingale interpretation of the estimated squared MMD to propose martingale MMD (mMMD), a quadratic-time statistic which has a limiting standard Gaussian distribution under the null. Moreover we show that the test is consistent against any fixed alternative and for large sample sizes, mMMD offers substantial computational savings over the standard MMD test, with only a minor loss in power.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-chatterjee26a, title = {A Martingale Kernel Two-Sample Test}, author = {Chatterjee, Anirban and Ramdas, Aaditya}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--44}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/chatterjee26a/chatterjee26a.pdf}, url = {https://proceedings.mlr.press/v313/chatterjee26a.html}, abstract = {The Maximum Mean Discrepancy (MMD) is a widely used multivariate distance metric for two-sample testing. The standard MMD test statistic has an intractable null distribution typically requiring costly resampling or permutation approaches for calibration. In this work we leverage a martingale interpretation of the estimated squared MMD to propose martingale MMD (mMMD), a quadratic-time statistic which has a limiting standard Gaussian distribution under the null. Moreover we show that the test is consistent against any fixed alternative and for large sample sizes, mMMD offers substantial computational savings over the standard MMD test, with only a minor loss in power.} }
Endnote
%0 Conference Paper %T A Martingale Kernel Two-Sample Test %A Anirban Chatterjee %A Aaditya Ramdas %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-chatterjee26a %I PMLR %P 1--44 %U https://proceedings.mlr.press/v313/chatterjee26a.html %V 313 %X The Maximum Mean Discrepancy (MMD) is a widely used multivariate distance metric for two-sample testing. The standard MMD test statistic has an intractable null distribution typically requiring costly resampling or permutation approaches for calibration. In this work we leverage a martingale interpretation of the estimated squared MMD to propose martingale MMD (mMMD), a quadratic-time statistic which has a limiting standard Gaussian distribution under the null. Moreover we show that the test is consistent against any fixed alternative and for large sample sizes, mMMD offers substantial computational savings over the standard MMD test, with only a minor loss in power.
APA
Chatterjee, A. & Ramdas, A.. (2026). A Martingale Kernel Two-Sample Test. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-44 Available from https://proceedings.mlr.press/v313/chatterjee26a.html.

Related Material