Timezone: »

 
Spotlight
Optimal Testing for Properties of Distributions
Jayadev Acharya · Constantinos Daskalakis · Gautam Kamath

Wed Dec 09 07:10 AM -- 07:35 AM (PST) @ Room 210 A
in Spotlight Session 5 »

Given samples from an unknown distribution, p, is it possible to distinguish whether p belongs to some class of distributions C versus p being far from every distribution in C? This fundamental question has receivedtremendous attention in Statistics, albeit focusing onasymptotic analysis, as well as in Computer Science, wherethe emphasis has been on small sample size and computationalcomplexity. Nevertheless, even for basic classes ofdistributions such as monotone, log-concave, unimodal, and monotone hazard rate, the optimal sample complexity is unknown.We provide a general approach via which we obtain sample-optimal and computationally efficient testers for all these distribution families. At the core of our approach is an algorithm which solves the following problem:Given samplesfrom an unknown distribution p, and a known distribution q, are p and q close in Chi^2-distance, or far in total variation distance?The optimality of all testers is established by providing matching lower bounds. Finally, a necessary building block for our tester and important byproduct of our work are the first known computationally efficient proper learners for discretelog-concave and monotone hazard rate distributions. We exhibit the efficacy of our testers via experimental analysis.

[ ] 

Author Information

Jayadev Acharya (Massachusetts Institute of Technology)
Constantinos Daskalakis (MIT)
Gautam Kamath (MIT)

More from the Same Authors