# Testing Closeness of Multivariate Distributions via Ramsey Theory

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 71 references that are in the map.
- First posted on arXiv 22 Nov 2023.

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

- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [Testing Identity of Structured Distributions](https://mlsanity.com/paper/1410.2266/) (2014)
- [Sample-Optimal Density Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1506.00671/) (2015)
- [Optimal Testing of Discrete Distributions with High Probability](https://mlsanity.com/paper/2009.06540/) (2020)
- [The Price of Tolerance in Distribution Testing](https://mlsanity.com/paper/2106.13414/) (2021)
- [Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions](https://mlsanity.com/paper/1508.05538/) (2015)
- [Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms](https://mlsanity.com/paper/1411.0169/) (2014)
- [Efficiently Learning Structured Distributions from Untrusted Batches](https://mlsanity.com/paper/1911.02035/) (2019)
- [Near-Optimal Closeness Testing of Discrete Histogram Distributions](https://mlsanity.com/paper/1703.01913/) (2017)
- [Testing Identity of Multidimensional Histograms](https://mlsanity.com/paper/1804.03636/) (2018)
- [Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms](https://mlsanity.com/paper/1802.08513/) (2018)
- [Learning Representations for Axis-Aligned Decision Forests through Input Perturbation](https://mlsanity.com/paper/2007.14761/) (2020)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Testing Poisson Binomial Distributions](https://mlsanity.com/paper/1410.3386/) (2014)

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

- [An Auditing Test To Detect Behavioral Shift in Language Models](https://mlsanity.com/paper/2410.19406/) (2024)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation](https://mlsanity.com/paper/2502.05730/) (2025)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding](https://mlsanity.com/paper/2503.07475/) (2025)
- [Are Two Datasets Close Enough With Statistical Significance? A Kernel Distributional Closeness Testing Approach](https://mlsanity.com/paper/2507.12843/) (2025)
- [Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more](https://mlsanity.com/paper/2606.11469/) (2026)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

## Abstract (arXiv)

We investigate the statistical task of closeness (or equivalence) testing for multidimensional distributions. Specifically, given sample access to two unknown distributions mathbf p, mathbf q on mathbb Rd, we want to distinguish between the case that mathbf p=mathbf q versus |mathbf p-mathbf q|Ak > ε, where |mathbf p-mathbf q|Ak denotes the generalized Ak distance between mathbf p and mathbf q -- measuring the maximum discrepancy between the distributions over any collection of k disjoint, axis-aligned rectangles. Our main result is the first closeness tester for this problem with em sub-learning sample complexity in any fixed dimension and a nearly-matching sample complexity lower bound. In more detail, we provide a computationally efficient closeness tester with sample complexity Oleft((k6/7/ polyd(ε)) logd(k)right). On the lower bound side, we establish a qualitatively matching sample complexity lower bound of Omega(k6/7/poly(ε)), even for d=2. These sample complexity bounds are surprising because the sample complexity of the problem in the univariate setting is Theta(k4/5/poly(ε)). This has the interesting consequence that the jump from one to two dimensions leads to a substantial increase in sample complexity, while increases beyond that do not. As a corollary of our general Ak tester, we obtain dmathrm TV-closeness testers for pairs of k-histograms on mathbb Rd over a common unknown partition, and pairs of uniform distributions supported on the union of k unknown disjoint axis-aligned rectangles. Both our algorithm and our lower bound make essential use of tools from Ramsey theory.