Source-linked AI summary
Optimal Algorithms for Testing Closeness of Discrete Distributions
Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, Paul Valiant
TL;DR
The paper asks how to distinguish equal from ε-far discrete distributions using samples. It presents new testers for ℓ1 and ℓ2 closeness, achieving information-theoretically optimal sample complexity, with a robust ℓ2 guarantee. The main scope boundary is that optimality for larger robust ℓ2 distances is not established in the stated approximation result.
Problem
The paper studies whether two unknown discrete distributions are equal or ε-far in ℓ1 or ℓ2 distance while using few samples and efficient computation.
Method
The paper designs simple, direct testers for ℓ1 closeness and robust ℓ2 closeness, with linear-time or sample-efficient procedures.
Results
The testers have information-theoretically optimal sample complexity to constant factors; for ℓ1, the complexity is Θ(max{n^2/3/ε^4/3, n^1/2/ε^2}).
Takeaways & Limitations
The paper resolves the sample complexity of closeness testing up to constant factors and provides robust ℓ2 testing at the same optimal sample scale.
Takeaways & Limitations
For robust ℓ2 testing, optimality is not shown when the tested distance is more than a b^-1/2 factor larger than ε.
Abstract
from arXiv · showhide
We study the question of closeness testing for two discrete distributions. More precisely, given samples from two distributions $p$ and $q$ over an $n$-element set, we wish to distinguish whether $p=q$ versus $p$ is at least $\eps$-far from $q$, in either $\ell_1$ or $\ell_2$ distance. Batu et al. gave the first sub-linear time algorithms for these problems, which matched the lower bounds of Valiant up to a logarithmic factor in $n$, and a polynomial factor of $\eps.$ In this work, we present simple (and new) testers for both the $\ell_1$ and $\ell_2$ settings, with sample complexity that is information-theoretically optimal, to constant factors, both in the dependence on $n$, and the dependence on $\eps$; for the $\ell_1$ testing problem we establish that the sample complexity is $Θ(\max\{n^{2/3}/\eps^{4/3}, n^{1/2}/\eps^2 \}).$
1 Introduction
The paper studies closeness testing for discrete distributions and develops sample- and time-efficient testers that resolve optimal complexity in both ℓ1 and ℓ2 settings.
- Problem: Closeness testing distinguishes p=q from distributions at least ε-far in ℓ1 or ℓ2 distance using independent samples.The distributions are supported on an n-element set, and the tester succeeds with probability at least 2/3.
- Motivation: Testing directly can use fewer samples than learning each distribution to ℓ1 accuracy ε, which requires Θ(n/ε^2) samples.The paper emphasizes computational efficiency, with running time polynomial in the sample size.
- ℓ1 results: The ℓ1 tester improves prior results by closing a polynomial gap in ε while preserving sublinear dependence on n.Earlier work was tight in n up to logarithmic factors but had a polynomial ε-dependence gap.
- ℓ1 results: Θ(max{n^2/3/ε^4/3, n^1/2/ε^2}) samples are necessary and sufficient for ℓ1 closeness testing, up to constant factors.The algorithm runs in time linear in its sample size and succeeds with probability at least 2/3.
- ℓ2 results: The ℓ2 tester robustly distinguishes ||p−q||2≤ε from ||p−q||2≥2ε using O(b/ε^2) samples when b bounds both distributions’ squared ℓ2 norms.This bound is information-theoretically optimal; an infinity-norm bound can also serve as b.
- Approach and scope: A reduction through the ℓ2 tester reaches O(n^2/3/ε^2) for ℓ1 testing, so the paper’s direct approach is needed for optimal ε-dependence.The paper also notes that its techniques may apply to related distribution-testing problems, but does not pursue that direction.
2 Closeness testing in ℓ1 norm
The section presents a simple ℓ1 closeness tester based on a statistic whose expectation separates equal from ε-far distributions. Its sample complexity is optimal, with linear running time in the sample size.
- The algorithm outputs EQUAL or DIFFERENT after processing count statistics for the sampled domain elements.Its input consists of m samples from p and q, represented by occurrence counts Xi and Yi.
- The tester distinguishes p = q from ||p −q||1 ≥ε with probability at least 2/3 when m ≥C′ max{n2/3/ε4/3, n1/2/ε2}.The guarantee applies to Poissonized samples from distributions supported on [n].
- The estimator has expectation zero when p = q and a lower-bounded expectation when p and q differ in ℓ1 distance.The equal-distribution calculation conditions on Xi + Yi and uses a fair-coin interpretation; the unequal case is related to ||p −q||1.
- Its variance is bounded through conditional variance decomposition and control of the variation in Xi + Yi.The analysis separates variance conditioned on the pooled count from variance caused by that count’s variation.
- The two sample regimes yield m = Ω(n2/3/||p −q||1^4/3) for m < n and m = Ω(n1/2/||p −q||1^2) for m ≥n.Together these bounds produce the maximum appearing in the tester’s sample complexity.
3 Robust ℓ2 testing
The section develops an optimal robust closeness tester for the ℓ2 norm. It estimates the distance using a linear Poisson-count estimator, with guarantees parameterized by an upper bound on distributional ℓ2 norm-squared.
- The parameter b upper-bounds ||p||2^2 and allows the sample guarantee to adapt to distributions that are easier or harder to test.The analysis also notes that ||p||2^2 ≤maxi pi, enabling a corresponding bound using maximum point probability.
- The estimator uses counts Xi and Yi from samples of p and q and outputs an estimate of ||p −q||2.Its core statistic is Zi = (Xi −Yi)2 −Xi −Yi, whose expectation is m2 · |pi −qi|2.
- The tester estimates ||p −q||2 to within ±ε with probability at least 3/4 using the sample bound stated in Proposition 6.The guarantee follows from bounding the estimator’s variance and applying Chebyshev’s inequality.
- The statistic is unbiased for m2||p −q||2^2 under Poissonized sampling.The variance calculation yields terms involving (pi −qi)2(pi + qi)m3 and (pi + qi)2m2.
- For distances greater than the stated B−1/2 factor above ε, the paper does not show optimality.Here B bounds the maximum probability of an element of p or q.
4 Lower bounds
The section proves information-theoretic lower bounds for ℓ1 and ℓ2 closeness testing using moment-based indistinguishability machinery and prior uniformity bounds. These bounds match the proposed testers in their supported regimes.
- The lower-bound arguments apply machinery from Valiant and Valiant–Verbin to both ℓ1 and ℓ2 closeness testing.The section explicitly presents the lower bounds as applications of these prior frameworks.
- The ℓ1 lower bound also incorporates the Ω(√n/ε2) lower bound known for uniformity testing.The paper uses this prior result together with Proposition 9 to establish the lower bound of Theorem 1.
- For ℓ1 testing, ε ≥4^3/4 n−1/4 implies that Ω(n2/3ε−4/3) samples are necessary for 0-versus-ε testing.The construction uses disjoint support subsets and produces distribution pairs with ℓ1 distance 2ε.
- Moment matching makes the constructed ℓ1 distribution pairs indistinguishable to testers using the specified sample budget.The proof bounds the relevant moment expression by O(c), yielding indistinguishability through Theorem 8.
- For ℓ2 testing, a family of perturbed distributions remains hard to distinguish from a reference distribution under the stated sample bound.The construction controls the ℓ2 norms and maximum probabilities of both reference and perturbed distributions.
- The ℓ2 indistinguishability result transfers to robust testing, showing that a tester separating zero from ε/2 would contradict the lower-bound construction.The reduction compares samples from (p, p) with samples from (p, q).
A An O(n2/3/ε2) ℓ1-tester
The tester separates heavy and light elements, learning the heavy parts and applying an ℓ2 tester to transformed light distributions. Choosing b = Θ(n^-2/3) yields O(n^2/3/ε^2) samples in the stated regime, while this reduction cannot achieve the paper’s optimal ε dependence.
- A An O(n2/3/ε2) ℓ1-tester: The tester first filters b-heavy elements, then applies an ℓ2 closeness tester to the light parts.The light versions p′ and q′ are constructed after testing the heavy parts.
- A An O(n2/3/ε2) ℓ1-tester: The heavy parts have support size at most 2/b and can be learned to ℓ1 error ε using O((1/b)/ε^2) samples.The method permits a small fraction of heavy elements to remain undetected, avoiding the extra log(1/b) factor from identifying all heavy elements.
- A An O(n2/3/ε2) ℓ1-tester: The two stages use s1 = O((1/b)/ε^2) and s2 samples, with their sum minimized at b = Θ(n^-2/3).At this choice, both stages require O(n^2/3/ε^2) samples.
- A An O(n2/3/ε2) ℓ1-tester: The reduction-based tester appears unable to obtain the optimal ε dependence because each stage already has individually optimal sample complexity.The paper therefore supports using a more direct approach to achieve optimal dependence on ε.
- A An O(n2/3/ε2) ℓ1-tester: O(n^2/3/ε^2) samples suffice when ε ≥ 1/√n, with acceptance and rejection probability at least 2/3.The algorithm sets b = n^-2/3 and uses the heavy-part and light-part tests with this total sample complexity.