Testing for Families of Distributions via the Fourier Transform *
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 P, we want to distinguish (with high probability) between the case that P ∈ P and the case that P 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.
Summary The paper studies the problem of testing membership to a family of distributions. In this problem the goal is to decide if an unknown distribution belongs in some pre-specified class of distributions or if it is at least eps-far in total variation distance from any distribution in the class. While the problem of testing identity to a single distribution is well understood, testing membership to a class is significantly more challenging.   This paper proposes a novel framework for testing membership to classes whose Fourier spectrum is sufficiently concentrated over some small domain. The main idea of the work is that in such cases it is possible to learn the distribution with few samples not only in total variation distance eps but also in L2 distance eps/sqrt(N) where N is the size of the effective support. This allows applying a testing via learning approach that does not work for TV distance as it requires a tolerant identity tester. In contrast, tolerant testing for L2 distance is known to be significantly more sample efficient.  The paper applies the framework to families of distributions that can be expressed as sums of independent random variables and log-concave distributions. The sampling complexities that are achieved are: - Poisson Binomial Distributions (PBD): ~n^(1/4)/eps^2 - Sums of k Integer Random Variables (kSIIRV): ~(kn^(1/4) + k^2)/eps^2 - Poisson Multinomial Distributions (PMD): ~n^((k-1)/4)/eps^2 - Log-Concave Distributions: ~sqrt(n)/eps^2 + 1/eps^2.5  The first result and fourth results are improvements over prior work removing additive terms of the sample complexity in the order of 1/eps^6 and 1/eps^5 respectively. The achieved results are nearly tight. Prior work has established that ~n^(1/4)/eps^2, sqrt(k) n^(1/4)/eps^2 are necessary for the cases of PBD and kSIIRV respectively, while a sqrt(n)/eps^2 lower bound follows from lower bounds for uniformity testing. In addition, this work provides a ~n^((k-1)/4)/eps^2 lower bound for the case of PMD.  Comments The proposed method based on Fourier Transform is quite interesting and the paper nicely illustrate its power and applicability through a range of different settings obtaining near optimal sample complexity bounds that qualitatively match the information theoretic lower bounds.   An important weakness of this work is its presentation. There is very little content in the main body of the paper. Apart from the framework, no detail is given about how it is applied in the results. The explanation in the introduction is quite vague and only mentions difficulties in applying the framework but not how it is applied. Right now everything is pushed to the supplementary materials which is highly technical and hard to read. It should be possible to give a more concrete outline with simplified versions of the algorithms in the main body of how the framework is applied and what Fourier properties of the families of distributions are used. I understand that the NIPS format gives limited space but I find that its use was not well optimized.  Another point missing in the paper is a unified summary of related work. There has been a lot of directly related work for testing families of distributions which is only partially invoked when comparing the results of the paper.    Recommendation Overall, I believe that the proposed framework is quite interesting and novel, and is able to improve on prior work of the literature and get near optimal bounds to many interesting problems. The main drawback I find is the presentation of the results. The current submission contains very little content in the main body. I think an outline of the algorithms and how the framework is applied to the families of distributions considered are necessary to be included.