Optimal Testing for Properties of Distributions
Given samples from an unknown discrete 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 received tremendous attention in statistics, focusing primarily on asymptotic analysis, as well as in information theory and theoretical computer science, where the emphasis has been on small sample size and computational complexity. Nevertheless, even for basic properties of discrete distributions such as monotonicity, independence, logconcavity, unimodality, 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 samples from an unknown distribution p, and a known distribution q, are p and q close in 2 -distance, or far in total variation distance? The optimality of our testers is established by providing matching lower bounds, up to constant factors. Finally, a necessary building block for our testers and an important byproduct of our work are the first known computationally efficient proper learners for discrete log-concave, monotone hazard rate distributions.
This manuscript aims to the determine the number of observations required to distinguish an unknown distribution $p$ from some class of distributions $\mathcal{C}$ that is at least $\epsilon$ away in total variation distance. Different classes of $\mathcal{C}$ considered include monotone, log-concave, unimodal and moonotone hazard rate distributions.Below are a few questions and comments which will hopefully help the author(s) improve the manuscript:A. Motivations I feel that the motivations for imposing shape-related constraints on discrete distributions remain to be explained further in this manuscript. Discrete distributions are mainly useful for modelling (i) the frequencies of observed objects (e.g. IP addresses) and (ii) counting data. In (i), applying monotone constraint means that one has to impose an ordinal structure on the objects; furthermore, one needs a metric associated with the ordinal structure to use the log-concave constraint. These implications somewhat limit the use of the proposed method, since not all the objects have a natural order.B. Theory. B1. Proof of Theorem 1.In order to have (1) and (2), one needs independence between the observations $X_i$ and the newly-drawn distribution $q$ (which satisfies Properties 1 and 2). This is not always the case, unless the observations used to estimate $q$ are discarded for the rest of the analysis. This requirement should be stated more explicitly.  B2. Use of Lemma 5.In the monotone case, Lemma 5 states that one can find $q$ such that $\mathbb{E}[\chi^2(p,q)]\le \epsilon^2/500$. However, in order to invoke Theorem~1, one requires $\chi^2(p,q) \le \epsilon^2/500$. So there is a gap in between. B3. Continuous case vs discrete case.Birges (1987) was cited a few times in the development of the theory. To my knowledge, the work of Birges only deals with density estimation. Could the author(s) state the particular result from Birges (1987) that has been referred to many times in the manuscript?B4. Log-concavity vs unimodality.In the proof of Lemma 7, as well as in Section H.2 in the appendix, it is stated that `any log-concave distribution is unimodal'. However, this is false in view of the definition given in Section~2 (i.e. $f_{i-1}f_{i+1} \le f_i^2$). For example, consider $n=7$, $f_1 = f_4 = f_7 = 1/3$ and $f_2 = f_3 = f_5 = f_6 = 0$. B5. Rate for testing log-concavity.It is stated in the abstract that testing log-concavity requires $O(sqrt{n}/\epsilon^2)$ samples. However, in view of Theorem 4, this is true when $\epsilon > n^{-1/4}$. Clearly, this statement is not precise when we are in the region of `fixing $n$ and decreasing $\epsilon$'. C. Connections to Statistics. It is worth pointing out that here the author(s) assumed that the distribution of interest, i.e. $p$, is discrete. In addition, in the development of theory, the support of $p$ is assumed to be $[n]$ (i.e., $\{1,2,\ldots,n\}$), which grows with respect to $n$. This setting is quite popular in Computer Science, though perhaps is not very well-known in Statistics. The author(s) cited work such as Hall and Van Keilegom (2005) and Cule and Samworth (2010). However, the cited work only deal with the continuous case. For more relevant work on estimating/testing a discrete monotone and log-concave distribution, see Jankowski and Wellner(2009) and Balabdaoui et.al.(2013). ReferencesJankowski, H. and Wellner, J.A. (2009). Estimation of a discrete monotone distribution. Electronic Journal of Statistics, 3, 1567--1605.Balabdaoui, F., Jankowski, H., Rufibach, K. and Pavlides, M. (2013). Asymptotic distribution of the discrete log-concave MLE and related applications, Journal of Royal Statistical Society Series B, 75, 769-790.