# Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 15 Apr 2025.

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

- [Revisiting Classifier Two-Sample Tests](https://mlsanity.com/paper/1610.06545/) (2016)
- [Classification accuracy as a proxy for two sample testing](https://mlsanity.com/paper/1602.02210/) (2016)
- [A new graph-based two-sample test for multivariate and object data](https://mlsanity.com/paper/1307.6294/) (2013)
- [Methods for Quantifying Dataset Similarity: a Review, Taxonomy and Comparison](https://mlsanity.com/paper/2312.04078/) (2023)
- [Tight Hardness Results for Maximum Weight Rectangles](https://mlsanity.com/paper/1602.05837/) (2016)
- [The power of online thinning in reducing discrepancy](https://mlsanity.com/paper/1608.02895/) (2016)
- [Computing Approximate Statistical Discrepancy](https://mlsanity.com/paper/1804.11287/) (2018)
- [Online Discrepancy Minimization for Stochastic Arrivals](https://mlsanity.com/paper/2007.10622/) (2020)
- [Algorithmic Discrepancy Beyond Partial Coloring](https://mlsanity.com/paper/1611.01805/) (2016)
- [A Higher-Order Kolmogorov-Smirnov Test](https://mlsanity.com/paper/1903.10083/) (2019)
- [Accelerated Computation of a High Dimensional Kolmogorov-Smirnov Distance](https://mlsanity.com/paper/2106.13706/) (2021)
- [Optimal Approximations Made Easy](https://mlsanity.com/paper/2008.08970/) (2020)
- [Integral Probability Metrics Meet Neural Networks: The Radon-Kolmogorov-Smirnov Test](https://mlsanity.com/paper/2309.02422/) (2023)

## Abstract (arXiv)

We revisit extending the Kolmogorov-Smirnov distance between probability distributions to the multi-dimensional setting, and make new arguments about the proper way to approach this generalization. Our proposed formulation maximizes the difference over orthogonal dominating rectangular ranges (d-sided rectangles in R^d), and is an integral probability metric. We also prove that the distance between a distribution and a sample from the distribution converges to 0 as the sample size grows, and bound this rate. Moreover, we show that one can, up to this same approximation error, compute the distance efficiently in 4 or fewer dimensions; specifically, the runtime is near-linear in the size of the sample needed for that error. With this, we derive a delta-precision two-sample hypothesis test using this distance. Finally, we show these metrics and approximation properties do not hold for other popular variants.