BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20221205T120000Z
UID:e561370827450e4a956ce0a7cc48d209-367
DTSTAMP:19700101T120011Z
DESCRIPTION:Exploring the Gap between Tolerant and Non-tolerant Distribution Testing
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/367/exploring-the-gap-between-tolerant-and-non-tolerant-distribution-testing/
SUMMARY: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	https://sites.google.com/view/sayantans/home



Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

Hosts: Aditya Abhay Lonkar, Rahul Madhavan and Rameesh Paul
DTSTART:20221205T120000Z
END:VEVENT
END:VCALENDAR