2026-07-21T19:38:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17149 2024-03-06T10:59:05Z ddc:004 open_access

Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing Chakraborty, Sourav Fischer, Eldar Ghosh, Arijit Mishra, Gopinath Sen, Sayantan Distribution Testing Tolerant Testing Non-tolerant Testing Sample Complexity 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 𝒪(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 𝒪(s) many samples. The learning procedure adapts to the input, and works without knowing s in advance. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sourav Chakraborty and Eldar Fischer and Arijit Ghosh and Gopinath Mishra and Sayantan Sen 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.27 urn:nbn:de:0030-drops-171497 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.27 eng https://creativecommons.org/licenses/by/4.0/legalcode