Projects per year
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 epsilonfar from having the property in
L1 distance (equivalently, total variation distance, or “statistical distance”). In this work, we give a novel general approach for distribution testing. We describe two techniques: our first technique gives sample–optimal testers, while our second technique gives matching sample lower bounds. As a consequence, we resolve the sample complexity of a wide variety of testing problems.
Our upper bounds are obtained via a modular reduction based approach. Our approach yields optimal testers for numerous problems by using a standard L2identity tester as
a blackbox. Using this recipe, we obtain simple estimators for a wide range of problems, encompassing many problems previously studied in the TCS literature, namely: (1) identity testing to a fixed distribution, (2) closeness testing between two unknown distributions (with equal/unequal sample sizes),
(3) independence testing (in any number of dimensions), (4) closeness testing for collections of distributions, and (5) testing histograms. For all of these problems, our testers are sampleoptimal, up to constant factors. With the exception of (1),
ours are the first sampleoptimal testers for the corresponding problems. Moreover, our estimators are significantly simpler to state and analyze compared to previous results.
As an important application of our reductionbased technique, we obtain the first adaptive algorithm for testing equivalence between two unknown distributions. The sample complexity of our algorithm depends on the structure of the unknown distributions – as opposed to merely their domain size
– and is significantly better compared to the worstcase optimal L1tester in many natural instances. Moreover, our technique naturally generalizes to other metrics beyond the L1distance. As an illustration of its flexibility, we use it to obtain the first nearoptimal equivalence tester under the Hellinger distance.
Our lower bounds are obtained via a direct information theoretic approach: Given a candidate hard instance, our proof proceeds by bounding the mutual information between appropriate random variables. While this is a classical method in information theory, prior to our work, it had not been used in this context. Previous lower bounds relied either on the birthday paradox, or on momentmatching and were thus restricted to symmetric properties. Our lower bound approach does not suffer from any such restrictions and gives tight sample lower bounds for the aforementioned problems.
L1 distance (equivalently, total variation distance, or “statistical distance”). In this work, we give a novel general approach for distribution testing. We describe two techniques: our first technique gives sample–optimal testers, while our second technique gives matching sample lower bounds. As a consequence, we resolve the sample complexity of a wide variety of testing problems.
Our upper bounds are obtained via a modular reduction based approach. Our approach yields optimal testers for numerous problems by using a standard L2identity tester as
a blackbox. Using this recipe, we obtain simple estimators for a wide range of problems, encompassing many problems previously studied in the TCS literature, namely: (1) identity testing to a fixed distribution, (2) closeness testing between two unknown distributions (with equal/unequal sample sizes),
(3) independence testing (in any number of dimensions), (4) closeness testing for collections of distributions, and (5) testing histograms. For all of these problems, our testers are sampleoptimal, up to constant factors. With the exception of (1),
ours are the first sampleoptimal testers for the corresponding problems. Moreover, our estimators are significantly simpler to state and analyze compared to previous results.
As an important application of our reductionbased technique, we obtain the first adaptive algorithm for testing equivalence between two unknown distributions. The sample complexity of our algorithm depends on the structure of the unknown distributions – as opposed to merely their domain size
– and is significantly better compared to the worstcase optimal L1tester in many natural instances. Moreover, our technique naturally generalizes to other metrics beyond the L1distance. As an illustration of its flexibility, we use it to obtain the first nearoptimal equivalence tester under the Hellinger distance.
Our lower bounds are obtained via a direct information theoretic approach: Given a candidate hard instance, our proof proceeds by bounding the mutual information between appropriate random variables. While this is a classical method in information theory, prior to our work, it had not been used in this context. Previous lower bounds relied either on the birthday paradox, or on momentmatching and were thus restricted to symmetric properties. Our lower bound approach does not suffer from any such restrictions and gives tight sample lower bounds for the aforementioned problems.
Original language  English 

Title of host publication  Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on 
Publisher  Institute of Electrical and Electronics Engineers (IEEE) 
Pages  685694 
Number of pages  10 
ISBN (Electronic)  9781509039333 
ISBN (Print)  9781509039340 
DOIs  
Publication status  Published  15 Dec 2016 
Event  57th Annual Symposium on Foundations of Computer Science  New Brunswick, United States Duration: 9 Oct 2016 → 11 Oct 2016 http://dimacs.rutgers.edu/archive/FOCS16/ 
Publication series
Name  

Publisher  IEEE 
ISSN (Print)  02725428 
Conference
Conference  57th Annual Symposium on Foundations of Computer Science 

Abbreviated title  FOCS 2016 
Country/Territory  United States 
City  New Brunswick 
Period  9/10/16 → 11/10/16 
Internet address 
Fingerprint
Dive into the research topics of 'A New Approach for Testing Properties of Discrete Distributions'. Together they form a unique fingerprint.Projects
 1 Finished

Sublinear Algorithms for Approximating Probability Distribution
Diakonikolas, I.
1/09/14 → 31/08/15
Project: Research