Testing Shape Restrictions of Discrete Distributions

By Clément Louis Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld. 2015

90 citations recorded by the source corpus.

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 P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {P}$\end{document}, the goal is to distinguish between D ∈ P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {P}$\end{document} and ℓ1(D, P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {P}$\end{document}) > ε. 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.

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, methodology): “This uses the aforementioned test from [18], [19]; c > 0 is as in Theorem 13.”
Differentially Private Identity and Equivalence Testing of Discrete Distributions (2018, background): “After two decades of study, this “worst-case” regime is well-understood: for many properties of interest there exist sample-optimal testers (matched by information-theoretic lower bounds) (Paninski, 2008; Daskalakis et al., 2013; Chan et al., 2014; Valiant & Valiant, 2014; Diakonikolas et al., 2015b”
Hypothesis Testing for High-Dimensional Multinomials: A Selective Review (2017, methodology): “A complete minimax theory for this case is not yet available, but many special cases have been studied [Batu, Kumar and Rubinfeld (2004), Acharya, Daskalakis and Kamath (2015), Indyk, Levi and Rubinfeld (2012), Canonne et al. (2016)].”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, background): “In the past two decades there has been a lot of work from the computer science, information theory, and statistics community on various distribution testing problems in the non-asymptotic (small-sample) regime, where the domain size k could be potentially larger thanm (See [13, 12, 37, 10, 49, 4, 3,”
Communication and Memory Efficient Testing of Discrete Distributions (2019, background): “…exist sample-efficient testers Paninski (2008); Chan et al. (2014); Valiant and Valiant (2014); Diakonikolas et al. (2015a); Acharya et al. (2015); Canonne et al. (2016); Diakonikolas and Kane (2016); Diakonikolas et al. (2016); Canonne et al. (2018); Goldreich (2017); Diakonikolas et al.…”
Differentially Private Identity and Closeness Testing of Discrete Distributions (2017, background): “After two decades of study, this “worst-case” regime is well-understood: for many properties of interest there exist sample-optimal testers (matched by information-theoretic lower bounds) [24, 10, 9, 26, 15, 14, 2, 13, 6, 11, 8, 16].”