Optimal Algorithms for Testing Closeness of Discrete Distributions

By Siu On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant. 2013

245 citations recorded by the source corpus.

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 e-far from q, in either e1 or e2 distance. Batu et al [BFR+00, BFR+13] gave the first sub-linear time algorithms for these problems, which matched the lower bounds of [Val11] up to a logarithmic factor in n, and a polynomial factor of e. In this work, we present simple testers for both the e1 and e2 settings, with sample complexity that is information-theoretically optimal, to constant factors, both in the dependence on n, and the dependence on e for the e1 testing problem we establish that the sample complexity is Θ(max{n2/3/e4/3, n1/2/&epsilon2}).

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Test without Trust: Optimal Locally Private Distribution Testing (2018, methodology): “We now propose our testing mechanism based on Rappor, which, in essence, uses a privatized version of a χ2-type statistic of [12, 4, 32].”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, methodology): “We privatize the closeness testing algorithm of [19].”
Hypothesis Testing for High-Dimensional Multinomials: A Selective Review (2017, background): “Chan et al. (2014) also showed that the (centered) χ2 statistic”
Introduction to Property Testing (2017, methodology): “23 Note (22)Recall that the alternatives include the testers of [221] and [73] or the collision probability test (of Algorithm 11.”
Property Testing For Differential Privacy (2018, background): “Chan et al. (2014b) proved that there exists a property tester T that takes as input a description of the discrete distribution P and O ( √ 2 ) samples from an distribution Q .”
Minimax optimality of permutation tests (2020, methodology): “Following Chan et al. (2014) and Diakonikolas and Kane (2016), we use the threshold C‖pY ‖2n 1 for some constant C and reject the null when Un1,n2 > C‖pY ‖2n 1 where Un1,n2 is the U -statistic considered in Proposition 4.”
Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain (2018, background): “A related area of research is that of property testing, i.e. to test whether a distribution satisfies some property such as uniformity or monotonicity, from a sample (see e.g. Chan et al. (2014); Canonne and Rubinfeld (2014); Diakonikolas et al. (2015); Valiant (2011)).”
Two Party Distribution Testing: Communication and Security (2018, methodology): “…2) or “far” (when We note that an immediate corollary of our lower bound is an alternative proof that ˜Ω( n 2 / 3 ) samples are necessary to solve closeness testing (in the vanilla testing setting), albeit the resulting bound is oﬀ by polylogarithmic factors from the best known ones [CDVV14, DK16].”
Testing Identity of Structured Distributions (2014, methodology): “To prove Theorem 4 we show that a variant of Pearson’s chi-squared test [Pea00] – which can be viewed as a special case of the recent “chi-square type” testers in [CDVV14, VV14] – has the desired L 2 guarantee.”