The Library
Exploring the gap between tolerant and non-tolerant distribution testing
Tools
Chakraborty, Sourav, Fischer, Eldar, Ghosh, Arijit, Mishra, Gopinath and Sen, Sayantan (2022) Exploring the gap between tolerant and non-tolerant distribution testing. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), Online, 19-21 Sep 2022. Published in: Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), 245 pp. 1-23. ISBN 9783959772495. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.27 ISSN 1868-8969.
|
PDF
WRAP-Exploring-the-gap-between-tolerant-and-non-tolerant-distribution-testing-Mishra-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (840Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022....
Abstract
The framework of distribution testing is currently ubiquitous in the field of property testing. In this model, the input is a probability distribution accessible via independently drawn samples from an oracle. The testing task is to distinguish a distribution that satisfies some property from a distribution that is far in some distance measure from satisfying it. The task of tolerant testing imposes a further restriction, that distributions close to satisfying the property are also accepted.
This work focuses on the connection between the sample complexities of non-tolerant testing of distributions and their tolerant testing counterparts. When limiting our scope to label-invariant (symmetric) properties of distributions, we prove that the gap is at most quadratic, ignoring poly-logarithmic factors. Conversely, the property of being the uniform distribution is indeed known to have an almost-quadratic gap.
When moving to general, not necessarily label-invariant properties, the situation is more complicated, and we show some partial results. We show that if a property requires the distributions to be non-concentrated, that is, the probability mass of the distribution is sufficiently spread out, then it cannot be non-tolerantly tested with o(√n) many samples, where n denotes the universe size. Clearly, this implies at most a quadratic gap, because a distribution can be learned (and hence tolerantly tested against any property) using O(n) many samples. Being non-concentrated is a strong requirement on properties, as we also prove a close to linear lower bound against their tolerant tests.
Apart from the case where the distribution is non-concentrated, we also show if an input distribution is very concentrated, in the sense that it is mostly supported on a subset of size s of the universe, then it can be learned using only O(s) many samples. The learning procedure adapts to the input, and works without knowing s in advance.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics T Technology > TK Electrical engineering. Electronics Nuclear engineering |
|||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Uniform distribution (Probability theory), Streaming technology (Telecommunications), Linear systems, Algorithms, Probabilities | |||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
Journal or Publication Title: | Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) | |||||||||
Publisher: | Schloss Dagstuhl — Leibniz-Zentrum für Informatik | |||||||||
Place of Publication: | Dagstuhl, Germany | |||||||||
ISBN: | 9783959772495 | |||||||||
ISSN: | 1868-8969 | |||||||||
Official Date: | 15 September 2022 | |||||||||
Dates: |
|
|||||||||
Volume: | 245 | |||||||||
Page Range: | pp. 1-23 | |||||||||
Article Number: | 27 | |||||||||
DOI: | 10.4230/LIPIcs.APPROX/RANDOM.2022.27 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||
Date of first compliant deposit: | 1 November 2022 | |||||||||
Date of first compliant Open Access: | 2 November 2022 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Online | |||||||||
Date(s) of Event: | 19-21 Sep 2022 | |||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year