Improving and extending the testing of distributions for shape-restricted properties

DOI10.4230/LIPICS.STACS.2017.31zbMATH Open1402.68193arXiv1609.06736OpenAlexW2963553954MaRDI QIDQ4636629FDOQ4636629

Authors: Eldar Fischer, Oded Lachish, Yadu Vasudev 

Publication date: 19 April 2018

Abstract: Distribution testing deals with what information can be deduced about an unknown distribution over $1,ldots,n$, where the algorithm is only allowed to obtain a relatively small number of independent samples from the distribution. In the extended conditional sampling model, the algorithm is also allowed to obtain samples from the restriction of the original distribution on subsets of $1,ldots,n$. In 2015, Canonne, Diakonikolas, Gouleakis and Rubinfeld unified several previous results, and showed that for any property of distributions satisfying a "decomposability" criterion, there exists an algorithm (in the basic model) that can distinguish with high probability distributions satisfying the property from distributions that are far from it in the variation distance. We present here a more efficient yet simpler algorithm for the basic model, as well as very efficient algorithms for the conditional model, which until now was not investigated under the umbrella of decomposable properties. Additionally, we provide an algorithm for the conditional model that handles a much larger class of properties. Our core mechanism is a way of efficiently producing an interval-partition of $1,ldots,n$ that satisfies a "fine-grain" quality. We show that with such a partition at hand we can directly move forward with testing individual intervals, instead of first searching for the "correct" partition of $1,ldots,n$.

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

Recommendations

• Improving and extending the testing of distributions for shape-restricted properties
• Testing shape restrictions of discrete distributions
• Testing shape restrictions of discrete distributions
• On the power of conditional samples in distribution testing
• Testing probability distributions using conditional samples

zbMATH Keywords

statisticsproperty testingconditional samplingdistribution testing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Distribution theory (60E99)

Cited In (9)

• Proofs of Proximity for Distribution Testing
• Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
• Imposing and Testing for Shape Restrictions in Flexible Parametric Models
• Property Testing on Product Distributions
• Parameterized property testing of functions
• The shapes of non-generic figures, and applications to collinearity testing
• A Hierarchy Theorem for Interactive Proofs of Proximity
• Testing shape restrictions of discrete distributions
• Collision-based Testers are Optimal for Uniformity and Closeness

This page was built for publication: Improving and extending the testing of distributions for shape-restricted properties

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