Timezone: »

 
Poster
Testing for Families of Distributions via the Fourier Transform
Alistair Stewart · Ilias Diakonikolas · Clément L Canonne

Wed Dec 05 07:45 AM -- 09:45 AM (PST) @ Room 210 #93
in Wed Poster Session A »

We study the general problem of testing whether an unknown discrete distribution belongs to a specified family of distributions. More specifically, given a distribution family P and sample access to an unknown discrete distribution D , we want to distinguish (with high probability) between the case that D in P and the case that D is ε-far, in total variation distance, from every distribution in P . This is the prototypical hypothesis testing problem that has received significant attention in statistics and, more recently, in computer science. The main contribution of this work is a simple and general testing technique that is applicable to all distribution families whose Fourier spectrum satisfies a certain approximate sparsity property. We apply our Fourier-based framework to obtain near sample-optimal and computationally efficient testers for the following fundamental distribution families: Sums of Independent Integer Random Variables (SIIRVs), Poisson Multinomial Distributions (PMDs), and Discrete Log-Concave Distributions. For the first two, ours are the first non-trivial testers in the literature, vastly generalizing previous work on testing Poisson Binomial Distributions. For the third, our tester improves on prior work in both sample and time complexity.

Keywords: Learning Theory · Algorithms
[ Paper] 

Author Information

Alistair Stewart (University of Southern California)
Ilias Diakonikolas (University of Southern California)
Clément L Canonne (Stanford University)

More from the Same Authors