- A New Approach for Distrib...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in October 2016
A New Approach for Distribution Testing
Speaker:
Ilias Diakonikolas
, University of Southern California
Date: Wednesday, October 12, 2016
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: Seminar Room G575
Event Type:
Room Description:
Host: Pritish Kamath and Akshay Degwekar
Contact: Akshay Dhananjai Degwekar, akshayd@csail.mit.edu
Relevant URL: http://www.mit.edu/~pritish/acseminar.html
Speaker URL: None
Speaker Photo:
None
Reminders to:
seminars@csail.mit.edu, theory-seminars@csail.mit.edu
Reminder Subject:
TALK: A New Approach for Distribution Testing
Abstract: We study problems in distribution property testing: Given sample access to one or more unknown discrete distributions, we want to determine whether they have some global property or are $\eps$-far from having the property in $\ell_1$ distance. We provide a simple and general approach to obtain upper bounds in this setting, by reducing $\ell_1$-testing to $\ell_2$-testing. Our reduction yields optimal $\ell_1$-testers, by using a standard $\ell_2$-tester as a black-box.
Using our framework, we obtain optimal estimators for a wide variety of $\ell_1$ distribution testing problems, including the following: identity testing to a fixed distribution, closeness testing between two unknown distributions (with equal/unequal sample sizes), independence testing (in any number of dimensions), closeness testing for collections of distributions, and testing $k$-flatness. For several of these problems, we give the first optimal tester in the literature. Moreover, our estimators are significantly simpler to state and analyze compared to previous approaches.
As our second main contribution, we provide a direct general approach for proving distribution testing lower bounds, by bounding the mutual information. Our lower bound approach is not restricted to symmetric properties, and we use it to prove tight lower bounds for all the aforementioned problems.
Joint work with Daniel Kane.
Research Areas:
Impact Areas:
Created by Akshay Dhananjai Degwekar at Tuesday, October 11, 2016 at 11:33 PM.