Testing Properties of Collections of Distributions

By Reut Levi, Dana Ron, Ronitt Rubinfeld. 2013

73 citations recorded by the source corpus.

We propose a framework for studying property testing of collections of distributions, where the number of distributions in the collection is a parameter of the problem. Previous work on property testing of distributions considered single distributions or pairs of distributions. We suggest two models that differ in the way the algorithm is given access to samples from the distributions. In one model the algorithm may ask for a sample from any distribution of its choice, and in the other the choice of the distribution is random. Our main focus is on the basic problem of distinguishing between the case that all the distributions in the collection are the same (or very similar), and the case that it is necessary to modify the distributions in the collection in a non-negligible manner so as to obtain this property. We give almost tight upper and lower bounds for this testing problem, as well as study an extension to a clusterability property. One of our lower bounds directly implies a lower bound on testing independence of a joint distribution, a result which was left open by previous work.

Subfields: Artificial Intelligence

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

Citations in the corpus

Learning Discrete Distributions from Untrusted Batches (2017, background): “Both [LRR13] and [TKV17], however, crucially rely on the assumption that the data consists of independent draws from the m distributions, and the algorithms and results do not extend to the present setting where some non-negligible fraction of the data is arbitrary/adversarial.”
Priv'IT: Private and Sample Efficient Identity Testing (2017, background): “, (Batu et al., 2001; Paninski, 2008; Levi et al., 2013; Valiant & Valiant, 2014; Acharya et al., 2015; Canonne et al., 2016; Diakonikolas & Kane, 2016; Daskalakis et al., 2016), and (Canonne, 2015) for a survey), where the focus has instead been on the finite sample regime, rather than asymptotics.”
Learning Populations of Parameters (2017, background): “Also related to the current work are the works [9, 10] on testing whether certain properties of collections of distributions hold.”
Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, background): “In a significant body of work spanning more than a decade [2, 7, 8, 13, 14, 23, 26, 37, 39, 43, 44, 55, 57], a myriad of properties has been investigated under this lens.”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “The optimal sample complexity for the independence testing problem where both observations are from the same set [k] was studied in [16], [41], and shown to be (k/ε2) in [6], [26].”
Two Party Distribution Testing: Communication and Security (2018, methodology): “The independence testing problem has been studied in [BFF + 01, LRR13, ADK15, DK16].”