Seminars

View all Seminars  |  Download ICal for this event

Exploring 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