# Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Aug 2015.

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

- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (2022)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [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)
- [When Are Trade-Off Functions Testable from Finite Samples?](https://mlsanity.com/paper/2605.10774/) (2026)
- [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 give a general unified method that can be used for L1 em closeness testing of a wide range of univariate structured distribution families. More specifically, we design a sample optimal and computationally efficient algorithm for testing the equivalence of two unknown (potentially arbitrary) univariate distributions under the Ak-distance metric: Given sample access to distributions with density functions p, q: I → ℝ, we want to distinguish between the cases that p=q and |p-q|Ak ≥ ε with probability at least 2/3. We show that for any k ≥ 2, ε>0, the em optimal sample complexity of the Ak-closeness testing problem is Theta(max k4/5/ε6/5, k1/2/ε2 ). This is the first o(k) sample algorithm for this problem, and yields new, simple L1 closeness testers, in most cases with optimal sample complexity, for broad classes of structured distributions.