Testing Identity of Structured Distributions

By Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin. 2014

110 citations recorded by the source corpus.

We study the question of identity testing for structured distributions. More precisely, given samples from a {\em structured} distribution $q$ over $[n]$ and an explicit distribution $p$ over $[n]$, we wish to distinguish whether $q=p$ versus $q$ is at least $\epsilon$-far from $p$, in $L_1$ distance. In this work, we present a unified approach that yields new, simple testers, with sample complexity that is information-theoretically optimal, for broad classes of structured distributions, including $t$-flat distributions, $t$-modal distributions, log-concave distributions, monotone hazard rate (MHR) distributions, and mixtures thereof.

How researchers see this paper

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

Citations in the corpus

Distributed Simulation and Distributed Inference (2018, methodology): “Most pertinent to our work is uniformity testing [GR00, Pan08, DGPP17], the prototypical distribution testing problem with applications to many other property testing problems [BKR04, DKN15, Gol16, CDGR17].”
The uniform distribution is complete with respect to testing identity to a fixed distribution (2016, background): “1 The tight lower and upper bound of Θ( √ n/ǫ2) on the sample complexity of both problems were presented in [11, 4, 13] (see also [6, 5]).”
Instance optimal learning of discrete distributions (2016, background): “One vein considers diﬀerent common types of structure that a distribution might possess—such as monotonicity, unimodality, skinny tails, etc., and how such structure can be leveraged to yield improved algorithms (e.g. [14, 9, 15, 11]).”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, background): “In the past two decades there has been a lot of work from the computer science, information theory, and statistics community on various distribution testing problems in the non-asymptotic (small-sample) regime, where the domain size k could be potentially larger thanm (See [13, 12, 37, 10, 49, 4, 3,”
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)).”
Communication and Memory Efficient Testing of Discrete Distributions (2019, background): “The following lemma, which is an adaptation of an analogous lemma in Diakonikolas et al. (2016)), will give us the minimum number of samples per player required for the tester to work given our choice of parameters:”
Differentially Private Identity and Closeness Testing of Discrete Distributions (2017, background): “After two decades of study, this “worst-case” regime is well-understood: for many properties of interest there exist sample-optimal testers (matched by information-theoretic lower bounds) [24, 10, 9, 26, 15, 14, 2, 13, 6, 11, 8, 16].”