Seminars
View all Seminars | Download ICal for this eventExploring the Gap between Tolerant and Non-tolerant Distribution Testing
Series: Bangalore Theory Seminars
Speaker: Sayantan Sen Indian Statistical Institute, Kolkata
Date/Time: Dec 05 11:00:00
Location: CSA Lecture Hall (Room No. 112, Ground Floor)
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.
Moreover, we prove lower bounds on the sample complexities of non-tolerant as well as tolerant testing for a special class of distribution properties, namely non-concentrated distribution properties, where the probability mass of the distributions in the property is sufficiently spread out. Finally, we design an algorithm that can learn a concentrated distribution even when its support set is unknown apriori.
This is a joint work with Sourav Chakraborty, Eldar Fischer, Arijit Ghosh and Gopinath Mishra.
Speaker Website Link
Microsoft teams link:
Link
Hosts: Aditya Abhay Lonkar, Rahul Madhavan and Rameesh Paul