Testing probability distributions underlying aggregated data

DOI10.1007/978-3-662-43948-7_24MaRDI QIDQ5167749zbMATH OpenOpenAlexFDO

Authors Clement L. Canonne, Ronitt Rubinfeld

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.3835

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

Abstract: In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution $D$ over $[n]$. More precisely, we define both the dual and cumulative dual access models, in which the algorithm $A$ can both sample from $D$ and respectively, for any $iin[n]$, - query the probability mass $D(i)$ (query access); or - get the total mass of $1,dots,i$, i.e. $su{m}_{j=1}^{i}D(j)$ (cumulative access) These two models, by generalizing the previously studied sampling and query oracle models, allow us to bypass the strong lower bounds established for a number of problems in these settings, while capturing several interesting aspects of these problems -- and providing new insight on the limitations of the models. Finally, we show that while the testing algorithms can be in most cases strictly more efficient, some tasks remain hard even with this additional power.

Recommendations

• Testing probability distributions using conditional samples
• Testing equivalence between distributions using conditional samples
• Testing similar means

Cited in

(20)

• Sublinear-time algorithms for counting star subgraphs via edge sampling
• A generalized test for perfect aggregation
• Describing the Pearson \(R\) distribution of aggregate data
• Big data on the rise? Testing monotonicity of distributions
• scientific article; zbMATH DE number 1254177 (Why is no real title available?)
• Sampling correctors
• A chasm between identity and equivalence testing with conditional queries
• Testing k-monotonicity
• Proofs of proximity for distribution testing
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Instance Optimal Distribution Testing and Learning
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Testing probability distributions using conditional samples
• Topics and Techniques in Distribution Testing: A Biased but Representative Sample
• Lifting uniform learners via distributional decomposition
• Range (Rényi) entropy queries and partitioning
• On the complexity of estimating the effective support size
• Daisy Bloom filters
• Range entropy queries and partitioning
• Better sum estimation via weighted sampling

This page was built for publication: Testing probability distributions underlying aggregated data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167749)