A Survey on Distribution Testing: Your Data is Big. But is it Blue?

By Clément Louis Canonne. 2020

257 citations recorded by the source corpus.

The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offsprings, distribution testing. This subfield, at the junction of property testing and Statistics, is concerned with studying properties of probability distributions. We cover the current status of distribution testing in several settings, starting with the traditional sampling model where the algorithm obtains independent samples from the distribution. We then discuss different recent models, which either grant the testing algorithms more powerful types of queries, or evaluate their performance against that of an information-theoretically optimal “adversary” (for a given number of samples). In each setting, we describe the state of the art for a variety of testing problems. We hope this survey will serve as a self-contained introduction for those considering research in this field. ∗Research supported by NSF CCF-1115703 and NSF CCF-1319788. ACM Classification: G.3, F.2.2 AMS Classification: 68Q32, 68W20, 68Q17, 68Q87

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

Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “setting of interest to us has received a lot of attention in the past decade, especially in the computer science literature; see [8], [17], [41] for surveys.”
Pan-Private Uniformity Testing (2019, background): “Since Poisson ( m ) concentrates around m [14], a uniformity tester on Poisson ( m ) samples implies a uniformity tester on a constant factor more samples with a constant decrease in success probability (see Section D.4 in the survey of Canonne [13] for a more detailed discussion of Poissonization).”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, methodology): “…of work culminated in efﬁcient and sample-optimal testing algorithms [Pan08, VV17, ADK15, Gol16, DGPP18]; we refer the reader to the surveys [Rub12, Can15, BW18], as well as the recent book [Gol17] (Chapter 11) for further details on identity testing, and the more general ﬁeld of distribution…”
Two Party Distribution Testing: Communication and Security (2018, methodology): “We refer the reader to the surveys [Gol17, Can15, Rub12, Rub06] for further references.”
An approximate sampler for energy-based models with divergence diagnostics (2022, background): “Canonne (2020, Theorem 12.9, p. 58) shows that such algorithms require O (1 / ( ε 1 − ε 2 ) 2 ) samples from ω if the probabilities ω ( x ) are known; whereas Canonne et al. demonstrating the benefits of having explicit estimates of divergence measures.”
Hypothesis Testing for High-Dimensional Multinomials: A Selective Review (2017, background): “…theory and theoretical computer science and we provide an overview of some important results from these different communities in this paper.2 2Theoretical computer science centric surveys of a subset of these results include the papers Rubinfeld (2012), Goldreich (2017) and Canonne (2018).”
The uniform distribution is complete with respect to testing identity to a fixed distribution (2016, background): “For a general survey of the areas, the interested reader is referred to Canonne [3].”
Communication and Memory Efficient Testing of Discrete Distributions (2019, background): “The field of distribution property testing Batu et al. (2000) has been extensively investigated in the past couple of decades, see, e.g., the surveys Rubinfeld (2012); Canonne (2015); Goldreich (2017).”
Minimax optimal conditional independence testing (2020, methodology): “[11] Clément L Canonne.”
Differentially Private Identity and Equivalence Testing of Discrete Distributions (2018, background): “…two decades, distribution property testing (Batu et al., 2000) – whose roots lie in statistical hypothesis testing (Neyman & Pearson, 1933; Lehmann & Romano, 2005) – has received considerable attention by the computer science community, see (Rubinfeld, 2012; Canonne, 2015) for two recent surveys.”
Introduction to Property Testing (2017, background): “The interested reader is referred to Canonne’s survey [68] (which also reviews alternative models such as the model of conditional sampling [70]).”
Test without Trust: Optimal Locally Private Distribution Testing (2018, background): “This literature itself spans the last two decades; we refer an interested reader to surveys and books [30, 11, 24, 8] for a comprehensive review.”
Differentially Private Identity and Closeness Testing of Discrete Distributions (2017, background): “Related Work During the past two decades, distribution property testing [3] – whose roots lie in statistical hypothesis testing [23, 22] – has received considerable attention by the computer science community, see [25, 7] for two recent surveys.”