Testing shape restrictions of discrete distributions

DOI10.1007/S00224-017-9785-6MaRDI QIDQ1702847zbMATH OpenOpenAlexFDO

Authors Clement L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld

Publication date 1 March 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.03558, https://drops.dagstuhl.de/opus/volltexte/2016/5726/

zbMATH Keywords

algorithmsdiscrete distributionslower boundsprobability distributionsproperty testingdistribution testing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We study the question of testing structured properties (classes) of discrete distributions. Specifically, given sample access to an arbitrary distribution $D$ over $[n]$ and a property $mathcalP$, the goal is to distinguish between $DinmathcalP$ and $el{l}_1(D,mathcalP)>varepsilon$. We develop a general algorithm for this question, which applies to a large range of "shape-constrained" properties, including monotone, log-concave, $t$-modal, piecewise-polynomial, and Poisson Binomial distributions. Moreover, for all cases considered, our algorithm has near-optimal sample complexity with regard to the domain size and is computationally efficient. For most of these classes, we provide the first non-trivial tester in the literature. In addition, we also describe a generic method to prove lower bounds for this problem, and use it to show our upper bounds are nearly tight. Finally, we extend some of our techniques to tolerant testing, deriving nearly-tight upper and lower bounds for the corresponding questions.

Recommendations

• Testing shape restrictions of discrete distributions
• Testing identity of structured distributions
• Testing \(k\)-modal distributions: optimal algorithms via reductions
• Improving and extending the testing of distributions for shape-restricted properties
• Improving and extending the testing of distributions for shape-restricted properties

Cites work

• scientific article; zbMATH DE number 5485485 (Why is no real title available?)
• scientific article; zbMATH DE number 1330768 (Why is no real title available?)
• scientific article; zbMATH DE number 3390139 (Why is no real title available?)
• A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data
• Algorithmic and analysis techniques in property testing
• An automatic inequality prover and instance optimal identity testing
• Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator
• Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
• Constrained Statistical Inference
• Efficient density estimation via piecewise polynomial approximation
• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
• Fitting algebraic curves to noisy data
• Improving and extending the testing of distributions for shape-restricted properties
• Inference and modeling with log-concave distributions
• Learning \(k\)-modal distributions via testing
• Learning mixtures of structured distributions over discrete domains
• Log-concave probability and its applications
• On testing expansion in bounded-degree graphs
• Optimal algorithms for testing closeness of discrete distributions
• Property testing. A learning theory perspective
• Sample-optimal density estimation in nearly-linear time
• Some Results for Discrete Unimodality
• Statistical-Mechanical Foundation of the Ubiquity of Lévy Distributions in Nature
• Streaming and sublinear approximation of entropy and information distances
• Sublinear algorithms for testing monotone and unimodal distributions
• Survival models for heterogeneous populations derived from stable distributions
• Testing Poisson binomial distributions
• Testing Symmetric Properties of Distributions
• Testing \(k\)-modal distributions: optimal algorithms via reductions
• Testing identity of structured distributions
• Testing probability distributions using conditional samples
• The Complexity of Approximating the Entropy
• The Power of Linear Estimators
• The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality

Cited in

(13)

• Improving and extending the testing of distributions for shape-restricted properties
• Improving and extending the testing of distributions for shape-restricted properties
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Testing shape restrictions of discrete distributions
• Testing identity of structured distributions
• Testing convexity of a discrete distribution
• The Discrete Moment Problem with Nonconvex Shape Constraints
• Learning \(k\)-modal distributions via testing
• Topics and Techniques in Distribution Testing: A Biased but Representative Sample
• Testing Poisson binomial distributions
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• Learning \(k\)-modal distributions via testing
• Testing \(k\)-modal distributions: optimal algorithms via reductions

This page was built for publication: Testing shape restrictions of discrete distributions

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