Optimal Testing for Properties of Distributions

Introduction

The quintessential scientific question is whether an unknown object has some property, i.e. whether a model from a specific class fits the object’s observed behavior. If the unknown object is a probability distribution, $p$, to which we have sample access, we are typically asked to distinguish whether $p$ belongs to some class $\mathcal{C}$ or whether it is sufficiently far from it.

This question has received tremendous attention in the field of statistics (see, e.g., [Fis25, LR06]), where test statistics for important properties such as the ones we consider here have been proposed. Nevertheless, the emphasis has been on asymptotic analysis, characterizing the rates of convergence of test statistics under null hypotheses, as the number of samples tends to infinity. In contrast, we wish to study the following problem in the small sample regime:

The problem has been studied intensely in the literature on property testing and sublinear algorithms [Gol98, Fis01, Rub06, Ron08, Can15], where the emphasis has been on characterizing the optimal tradeoff between $p$’s support size and the accuracy $\varepsilon$ in the number of samples. Several results have been obtained, roughly clustering into three groups, where (i) $\mathcal{C}$ is the class of monotone distributions over $[n]$, or more generally a poset [BKR04, BFRV11]; (ii) $\mathcal{C}$ is the class of independent, or $k$-wise independent distributions over a hypergrid [BFF+01, AAK+07]; and (iii) $\mathcal{C}$ contains a single-distribution $q$, and the problem becomes that of testing whether $p$ equals $q$ or is far from it [BFF+01, Pan08, VV14].

With respect to (iii), [VV14] exactly characterizes the number of samples required to test identity to each distribution $q$, providing a single tester matching this bound simultaneously for all $q$. Nevertheless, this tester and its precursors are not applicable to the composite identity testing problem that we consider. If our class $\mathcal{C}$ were finite, we could test against each element in the class, albeit this would not necessarily be sample optimal. If our class $\mathcal{C}$ were a continuum, we would need tolerant identity testers, which tend to be more expensive in terms of sample complexity [VV11], and result in substantially suboptimal testers for the classes we consider. Or we could use approaches related to generalized likelihood ratio test, but their behavior is not well-understood in our regime, and optimizing likelihood over our classes becomes computationally intense.

In this paper, we obtain sample-optimal and computationally efficient testers for $\Pi(\mathcal{C},\varepsilon)$ for the most fundamental shape restrictions to a distribution. Our contributions are the following:

A useful building block and interesting byproduct of our analysis is extending Birgé’s oblivious decomposition for single-dimensional monotone distributions [Bir87] to monotone distributions in $d\geq 1$, and to the stronger notion of $\chi^{2}$-distance. See Section C.1.

Moreover, we show that $O(\log^{d}n)$ samples suffice to learn a monotone distribution over $[n]^{d}$ in $\chi^{2}$-distance. See Lemma 5 for the precise statement.

For the classes $\mathcal{C}=\mathcal{LCD}_{n}$, $\mathcal{C}=\mathcal{MHR}_{n}$ and $\mathcal{C}=\mathcal{U}_{n}$ of log-concave, monotone-hazard-rate and unimodal distributions over $[n]$, we require an optimal $\Theta\left({\sqrt{n}\over\varepsilon^{2}}\right)$ number of samples. Our testers for $\mathcal{LCD}_{n}$ and $\mathcal{C}=\mathcal{MHR}_{n}$ are to our knowledge the first for these classes for the low sample regime we are studying—see [HVK05] and its references for statistics literature on the asymptotic regime. Our tester for $\mathcal{U}_{n}$ improves the dependence of the sample complexity on $\varepsilon$ by at least a factor of $2$ in the exponent, and shaves all logarithmic factors in $n$, compared to testers based on testing monotonicity.

A useful building block and important byproduct of our analysis are the first computationally efficient algorithms for properly learning log-concave and monotone-hazard-rate distributions, to within $\varepsilon$ in total variation distance, from ${\rm poly}(1/\varepsilon)$ samples, independent of the domain size $n$. See Corollaries 5 and 7. Again, these are the first computationally efficient algorithms to our knowledge in the low sample regime. [ADLS15, CDSS14] provide algorithms for density estimation, which are non-proper, i.e. will approximate an unknown distribution from these classes with a distribution that does not belong to these classes. On the other hand, the statistics literature focuses on maximum-likelihood estimation in the asymptotic regime—see e.g. [CS10] and its references.

For all the above classes we obtain matching lower bounds, showing that the sample complexity of our testers is optimal with respect to $n$, $\varepsilon$ and when applicable $d$. See Section 10. Our lower bounds are based on extending Paninski’s lower bound for testing uniformity [Pan08].

$p$ and $q$ are $O(\varepsilon^{2})$-close in $\chi^{2}$ distance; this case corresponds to $p\in\mathcal{C}$.

We draw a comparison with robust identity testing, in which one must distinguish whether $p$ and $q$ are $c_{1}\varepsilon$-close or $c_{2}\varepsilon$-far in total variation distance, for constants $c_{2}>c_{1}>0$. In [VV11], Valiant and Valiant show that $\Omega(n/\log n)$ samples are required for this problem – a nearly-linear sample complexity, which may be prohibitively large in many settings. In comparison, the problem we study tests for $\chi^{2}$ closeness rather than total variation closeness: a relaxation of the previous problem. However, our tester demonstrates that this relaxation allows us to achieve a substantially sublinear complexity of $O(\sqrt{n}/\varepsilon^{2})$. On the other hand, this relaxation is still tight enough to be useful, demonstrated by our application in obtaining sample-optimal testers.

We note that while the $\chi^{2}$ statistic for testing hypothesis is prevalent in statistics providing optimal error exponents in the large-sample regime, to the best of our knowledge, in the small-sample regime, modified-versions of the $\chi^{2}$ statistic have only been recently used for closeness-testing in [ADJ+12, CDVV14] and for testing uniformity of monotone distributions in [AJOT13]. In particular, [ADJ+12] design an unbiased statistic for estimating the $\chi^{2}$ distance between two unknown distributions.

In Section 4, we show that a version of the $\chi^{2}$ statistic, appropriately excluding certain elements of the support, is sufficiently well-concentrated to distinguish between the above cases. Moreover, the sample complexity of our algorithm is optimal for most classes. Our base tester is combined with the afore-mentioned extension of Birgé’s decomposition theorem to test monotone distributions in Section 5 (see Theorem 3 and Corollary 1), and is also used to test independence of distributions in Section 7 (see Theorem 6).

Naturally, there are several bells and whistles that we need to add to the above skeleton to accommodate all classes of distributions that we are considering. For log-concave and monotone-hazard distributions, we are unable to obtain a cheap (in terms of samples) learner that $\chi^{2}$-approximates the unknown distribution $p$ throughout its support. Still, we can identify a subset of the support where the $\chi^{2}$-approximation is tight and which captures almost all the probability mass of $p$. We extend our tester to accommodate excluding subsets of the support from the $\chi^{2}$-approximation. See Theorems 7 and 8 in Sections 8 and 9.

For unimodal distributions, we are even unable to identify a large enough subset of the support where the $\chi^{2}$ approximation is guaranteed to be tight. But we can show that there exists a light enough piece of the support (in terms of probability mass under $p$) that we can exclude to make the $\chi^{2}$ approximation tight. Given that we only use Chebyshev’s inequality to prove the concentration of the test statistic, it would seem that our lack of knowledge of the piece to exclude would involve a union bound and a corresponding increase in the required number of samples. We avoid this through a careful application of Kolmogorov’s max inequality in our setting. See Theorem 5 of Section 6.

Related Work.

For the problems that we study in thie paper, we have provided the related works in the previous section along with our contributions. We cannot do justice to the role of shape restrictions of probability distributions in probabilistic modeling and testing. It suffices to say that the classes of distributions that we study are fundamental, motivating extensive literature on their learning and testing [BBBB72]. In the recent times, there has been work on shape restricted statistics, pioneered by Jon Wellner, and others. [JW09, BW10] study estimation of monotone and $k-$ monotone densities, and [BJR11, SW14] study estimation of log-concave distributions.

As we have mentioned, statistics has focused on the asymptotic regime as the number of samples tends to infinity. Instead we are considering the low sample regime and are more stringent about the behavior of our testers, requiring $2$-sided guarantees. We want to accept if the unknown distribution is in our class of interest, and also reject if it is far from the class. For this problem, as discussed above, there are few results when $\mathcal{C}$ is a whole class of distributions. Closer related to our paper is the line of papers [BKR04, ACS10, BFRV11] for monotonicity testing, albeit these papers have sub-optimal sample complexity as discussed above. Testing independence of random variables has a long history in statisics [RS81, AK11]. The theoretical computer science community has also considered the problem of testing independence of two random variables [BFF+01, LRR13]. While our results sharpen the case where the variables are over domains of equal size, they demonstrate an interesting asymmetric upper bound when this is not the case. More recently, Acharya and Daskalakis provide optimal testers for the family of Poisson Binomial Distributions [AD15].

Finally, contemporaneous work of Canonne et al [CDGR15a, CDGR15b] provides a generic algorithm and lower bounds for the single-dimensional families of distributions considered here. We note that their algorithm has a sample complexity which is suboptimal in both $n$ and $\varepsilon$, while our algorithms are optimal. Their algorithm also extends to mixtures of these classes, though some of these extensions are not computationally efficient. They also provide a framework for proving lower bounds, giving the optimal bounds for many classes when $\varepsilon$ is sufficiently large with respect to $1/n$. In comparison, we provide these lower bounds unconditionally by modifying Paninski’s construction [Pan08] to suit the classes we consider.

Preliminaries

We use the following probability distances in our paper.

The total variation distance between distributions $p$ and $q$ is defined as

The $\chi^{2}$-distance between $p$ and $q$ over $[n]$ is defined by

The Kolmogorov distance between two probability measures $p$ and $q$ over an ordered set ($e.g.$, ${\bf R}$) with cumulative density functions (CDF) $F_{p}$ and $F_{q}$ is defined as

Our paper is primarily concerned with testing against classes of distributions, defined formally as follows:

Given $\varepsilon\in(0,1]$ and sample access to a distribution $p$, an algorithm is said to test a class $\mathcal{C}$ if it has the following guarantees:

If $p\in\mathcal{C}$, the algorithm outputs Accept with probability at least $2/3$;

The Dvoretzky-Kiefer-Wolfowitz (DKW) inequality gives a generic algorithm for learning any distribution with respect to the Kolmogorov distance [DKW56].

We note the following useful relationships between these distances [GS02]:

In this paper, we will consider the following classes of distributions:

Monotone distributions over $[n]^{d}$ (denoted by $\mathcal{M}_{n}^{d}$), for which $i\lesssim j$ implies $f_{i}\geq f_{j}$This definition describes monotone non-increasing distributions. By symmetry, identical results hold for monotone non-decreasing distributions.;

Unimodal distributions over $[n]$ (denoted by $\mathcal{U}_{n}$), for which there exists an $i^{*}$ such that $f_{i}$ is non-decreasing for $i\leq i^{*}$ and non-increasing for $i\geq i^{*}$;

Log-concave distributions over $[n]$ (denoted by $\mathcal{LCD}_{n}$), the sub-class of unimodal distributions for which $f_{i-1}f_{i+1}\leq f_{i}^{2}$;

Monotone hazard rate (MHR) distributions over $[n]$ (denoted by $\mathcal{MHR}_{n}$), for which $i<j$ implies $\frac{f_{i}}{1-F_{i}}\leq\frac{f_{j}}{1-F_{j}}$.

An $\eta$-effective support of a distribution $p$ is any set $S$ such that $p(S)\geq 1-\eta$.

The flattening of a function $f$ over a subset $S$ is the function $\bar{f}$ such that $\bar{f}_{i}=p(S)/|S|$.

Let $p$ be a distribution, and support $I_{1},\ldots$ is a partition of the domain. The flattening of $p$ with respect to $I_{1},\ldots$ is the distribution $\bar{p}$ which is the flattening of $p$ over the intervals $I_{1},\ldots$.

Throughout this paper, we use the standard Poissonization approach. Instead of drawing exactly $m$ samples from a distribution $p$, we first draw $m^{\prime}\sim\rm Poisson(m)$, and then draw $m^{\prime}$ samples from $p$. As a result, the number of times different elements in the support of $p$ occur in the sample become independent, giving much simpler analyses. In particular, the number of times we will observe domain element $i$ will be distributed as $\rm Poisson(mp_{i})$, independently for each $i$. Since $\rm Poisson(m)$ is tightly concentrated around $m$, this additional flexibility comes only at a sub-constant cost in the sample complexity with an inversely exponential in $m$, additive increase in the error probability.

Overview

Our algorithm for testing a distribution $p$ can be decomposed into three steps.

Our first step requires a learning algorithm with very specific guarantees. In proper learning, we are given sample access to a distribution $p\in\mathcal{C}$, where $\mathcal{C}$ is some class of distributions, and we wish to output $q\in\mathcal{C}$ such that $p$ and $q$ are close in total variation distance. In our setting, given sample access to $p\in\mathcal{C}$, we wish to output $q$ such that $q$ is close to $\mathcal{C}$ in total variation distance, and $p$ and $q$ are close in $\chi^{2}$-distance on an effective supportWe also require the algorithm to output a description of an effective support for which this property holds. This requirement can be slightly relaxed, as we show in our results for testing unimodality. of $p$. From an information theoretic standpoint, this problem is harder than proper learning, since $\chi^{2}$-distance is more restrictive than total variation distance. Nonetheless, this problem can be shown to have comparable sample complexity to proper learning for the structured classes we consider in this paper.

Computation of distance to class.

The next step is to see if the hypothesis $q$ is close to the class $\mathcal{C}$ or not. Since we have an explicit description of $q$, this step requires no further samples from $p$, i.e. it is purely computational. If we find that $q$ is far from the class $\mathcal{C}$, then it must be that $p\not\in\mathcal{C}$, as otherwise the guarantees from the previous step would imply that $q$ is close to $\mathcal{C}$. Thus, if it is not, we can terminate the algorithm at this point.

At this point, the previous two steps guarantee that our distribution $q$ is such that:

If $p\in\mathcal{C}$, then $p$ and $q$ are close in $\chi^{2}$ distance on a (known) effective support of $p$;

We can distinguish between these two cases using $O(\sqrt{n}/\varepsilon^{2})$ samples with a simple statistical $\chi^{2}$-test, that we describe in Section 4.

Using the above three-step approach, our tester, as described in the next section, can directly test monotonicity, log-concavity, and monotone hazard rate. With an extra trick, using Kolmogorov’s max inequality, it can also test unimodality.

For a known distribution $q$, there exists an algorithm with sample complexity

$\chi^{2}(p,q)<\varepsilon^{2}/10$ versus

This theorem follows from our main result of this section, stated next, slightly more generally for classes of distributions.

Suppose we are given $\varepsilon\in(0,1]$, a class of probability distributions $\mathcal{C}$, sample access to a distribution $p$ over $[n]$, and an explicit description of a distribution $q$ with the following properties:

If $p\in\mathcal{C}$, then $\chi^{2}(p,q)\leq\frac{\varepsilon^{2}}{500}$.

Then there exists an algorithm with the following guarantees:

If $p\in\mathcal{C}$, the algorithm outputs Accept with probability at least $2/3$;

The time and sample complexity of this algorithm are $O\left(\frac{\sqrt{n}}{\varepsilon^{2}}\right)$.

As stated in Theorem 2, Property 2 requires that $q$ is $O(\varepsilon^{2})$-close in $\chi^{2}$-distance to $p$ over its entire domain. For the class of monotone distributions, we are able to efficiently obtain such a $q$, which immediately implies sample-optimal learning algorithms for this class. However, for some classes, we cannot learn a $q$ with such strong guarantees, and we must consider modifications to our base testing algorithm.

For example, for log-concave and monotone hazard rate distributions, we can obtain a distribution $q$ and a set $S$ with the following guarantees:

If $p\in\mathcal{C}$, then $\chi^{2}(p_{S},q_{S})\leq O(\varepsilon^{2})$ and $p(S)\geq 1-O(\varepsilon)$;

A further modification can handle even weaker learning guarantees. We could handle the previous case because the tester “knows what we don’t know” – it can explicitly ignore the support over which we do not have a $\chi^{2}$-closeness guarantee. A more difficult case is when there may be a low measure interval hidden in our effective support, over which $p$ and $q$ have a large $\chi^{2}$-distance. While we may have insufficient samples to reliably identify this interval, it may still have a large effect on our statistic. A naive solution would be to consider a tester which tries all possible “guesses” for this “bad” interval, but a union bound would incur an extra logarithmic factor in the sample complexity. We manage to avoid this cost through a careful analysis involving Kolmogorov’s max inequality, maintaining the $O(\sqrt{n}/\varepsilon^{2})$ sample complexity even in this more difficult case.

Being more precise, we can handle cases where we can obtain a distribution $q$ and a set of intervals $S=\{I_{1},\dots,I_{b}\}$ with the following guarantees:

If $p\in\mathcal{C}$, then $p(S)\geq 1-O(\varepsilon)$, $p(I_{j})=\Theta(p(S)/b)$ for all $j\in[b]$, and there exists a set $T\subseteq[b]$ such that $|T|\geq b-t$ (for $t=O(1)$) and $\chi^{2}(p_{R},q_{R})\leq O(\varepsilon^{2})$, where $R=\cup_{T}I_{j}$;

This allows us to additionally test against the class of unimodal distributions.

Proof of Theorem 2: Theorem 2 is proven by analyzing Algorithm 1. As shown in Section A, $Z$ has the following mean and variance:

where by $p_{\mathcal{A}}$ and $q_{\mathcal{A}}$ we denote respectively the vectors $p$ and $q$ restricted to the coordinates in $\mathcal{A}$, and we slightly abuse notation when we write $\chi^{2}(p_{\mathcal{A}},q_{\mathcal{A}})$, as these do not then correspond to probability distributions.

Assuming Lemmas 2 and 3, Theorem 2 is now a simple application of Chebyshev’s inequality.

Testing Monotonicity

As an application of our testing framework, we will demonstrate how to test for monotonicity. Let $d\geq 1$, and ${\bf i}=(i_{1},\ldots,i_{d}),{\bf j}=(j_{1},\ldots,j_{d})\in[n]^{d}$. We say ${\bf i}\succcurlyeq{\bf j}$ if $i_{l}>j_{l}$ for $l=1,\ldots,d$.

A distribution $p$ over $[n]^{d}$ is monotone (decreasing) if for all ${\bf i}\succcurlyeq{\bf j}$, $p_{{\bf i}}\leq p_{{\bf j}}$.

Our main result of this section is as follows:

For any $d\geq 1$, there exists an algorithm for testing monotonicity over $[n]^{d}$ with sample complexity

and time complexity $O\left(\frac{n^{d/2}}{\varepsilon^{2}}+\operatorname*{poly}(\log n,1/\varepsilon)^{d}\right)$.

In particular, this implies the following optimal algorithms for monotonicity testing for all $d\geq 1$:

Fix any $d\geq 1$, and suppose $\varepsilon>\frac{\sqrt{d\log n}}{n^{1/4}}$. Then there exists an algorithm for testing monotonicity over $[n]^{d}$ with sample complexity $O\left(n^{d/2}/\varepsilon^{2}\right)$.

Our analysis starts with a structural lemma about monotone distributions. In [Bir87], Birgé showed that any monotone distribution $p$ over $[n]$ can be obliviously decomposed into $O(\log(n)/\varepsilon)$ intervals, such that the flattening $\bar{p}$ (recall Definition 6) of $p$ over these intervals is $\varepsilon$-close to $p$ in total variation distance. [AJOS14] extend this result, giving a bound between the $\chi^{2}$-distance of $p$ and $\bar{p}$. We strengthen these results by extending them to monotone distributions over $[n]^{d}$. In particular, we partition the domain $[n]^{d}$ of $p$ into $O((d\log(n)/\varepsilon^{2})^{d})$ rectangles, and compare it with $\bar{p}$, the flattening over these rectangles.

Let $d\geq 1$. There is an oblivious decomposition of $[n]^{d}$ into $O((d\log(n)/\varepsilon^{2})^{d})$ rectangles such that for any monotone distribution $p$ over $[n]^{d}$, its flattening $\bar{p}$ over these rectangles satisfy $\chi^{2}(p,\bar{p})\leq\varepsilon^{2}$.

This effectively reduces the support size to logarithmic in $n$. At this point, we can apply the Laplace estimator (along the lines of [KOPS15]) and learn a $q$ such that if $p$ was monotone, then $q$ will be $O(\varepsilon^{2})$-close in $\chi^{2}$-distance.

The final step before we apply our $\chi^{2}$-tester is to compute the distance between $q$ and $\mathcal{M}_{n}^{d}$. This subroutine is similar to the one introduced by [BKR04]. The key idea is to write a linear program, which searches for any distribution $f$ which is close to $q$ in total variation distance. We note that the desired properties of $f$ (i.e., monotonicity, normalization, and $\varepsilon$-closeness to $q$) are easy to enforce as linear constraints. If we find that such an $f$ exists, we will apply our $\chi^{2}$-test to $q$. If not, we output Reject, as this is sufficient evidence to conclude that $p\not\in\mathcal{M}_{n}^{d}$. Note that the linear program operates over the oblivious decomposition used in our structural result, so the complexity is polynomial in $(d\log(n)/\varepsilon)^{d}$, rather than the naive $n^{d}$.

At this point, we have precisely the guarantees needed to apply Theorem 2, directly implying Theorem 3. Proof of the lemmas in this section are provided in Section C. We note that the class of monotone distributions is the simplest of the classes we consider. We now consider testing for log-concavity, monotone hazard rate, and unimodality, all of which are much more challenging to test. In particular, these classes require a more sophisticated structural understanding, more complex proper $\chi^{2}$-learning algorithms, and non-trivial modifications to our $\chi^{2}$-tester. We have already given some details on the required adaptations to the tester in Remark 1.

Our algorithms for learning these classes use convex programming. One of the main challenges is to enforce log-concavity of the PDF when learning $\mathcal{LCD}_{n}$ (respectively, of the CDF when learning $\mathcal{MHR}_{n}$), while simultaneously enforcing closeness in total variation distance. This involves a careful choice of our variables, and we exploit structural properties of the classes to ensure the soundness of particular Taylor approximations. We encourage the reader to refer to the proofs of Theorems 5, 7,and 8 for more details.

Testing Unimodality

One striking feature of Birgé’s result is that the decomposition of the domain is oblivious to the samples, and therefore to the unknown distribution. However, such an oblivious decomposition will not work for the unimodal distribution, since the mode is unknown. Suppose we know where the mode of the unknown distribution might be, then the problem can be decomposed into monotone functions over two intervals. Therefore, in theory, one can modify the monotonicity testing algorithm by iterating over all the possible $n$ modes. Indeed, by applying a union bound, it then follows that

(Follows from Monotone) For $\varepsilon>1/n^{1/4}$, there exists an algorithm for testing unimodality over $[n]$ with sample complexity $O\left(\frac{\sqrt{n}}{\varepsilon^{2}}\log n\right)$.

However, this is unsatisfactory, since our lower bound (and as we will demonstrate, the true complexity of this problem) is $\sqrt{n}/\varepsilon^{2}$. We overcome the logarithmic barrier introduced by the union bound, by employing a non-oblivious decomposition of the domain, and using Kolmogorov’s max-inequality.

Our main result for testing unimodality is the following theorem, which is proved in Section D.

Suppose $\varepsilon>n^{-1/4}$. Then there exists an algorithm for testing unimodality over $[n]$ with sample complexity $O(\sqrt{n}/\varepsilon^{2})$.

Testing Independence of Random Variables

Let $p=p^{1}\times p^{2}\ldots\times p^{d}$, and $q=q^{1}\times q^{2}\ldots\times q^{d}$ be two distributions in $\Pi_{d}$. Then

Along the lines of learning monotone distributions in $\chi^{2}$ distance we obtain the following result, proved in Section E.

samples from a distribution $p$ in $\Pi_{d}$ and outputs a distribution $q\in\Pi_{d}$ such that with probability at least $5/6$,

For any $d\geq 1$, there exists an algorithm for testing independence of random variables over $[n_{1}]\times\ldots[n_{d}]$ with sample and time complexity

There exists an algorithm for testing if two distributions over $[n]$ are independent with sample complexity $\Theta(n/\varepsilon^{2})$.

Testing Log-Concavity

In this section we describe our results for testing log-concavity of distributions. Our main result is as follows:

There exists an algorithm for testing log-concavity over $[n]$ with sample complexity

and time complexity $\operatorname*{poly}(n,1/\varepsilon)$.

In particular, this implies the following optimal tester for this class:

Suppose $\varepsilon>1/n^{1/5}$. Then there exists an algorithm for testing log-concavity over $[n]$ with sample complexity $O\left(\sqrt{n}/\varepsilon^{2}\right)$.

Our algorithm will fit into the structure of our general framework. We first perform a very particular type of learning algorithm, whose guarantees are summarized in the following lemma:

Given $\varepsilon>0$ and sample access to a distribution $p$, there exists an algorithm with the following guarantees:

If $p\in\mathcal{LCD}_{n}$, the algorithm outputs a distribution $q\in\mathcal{LCD}_{n}$ and an $O(\varepsilon)$-effective support $S$ of $p$ such that $\chi^{2}(p_{S},q_{S})\leq\frac{\varepsilon^{2}}{500}$ with probability at least $5/6$;

The sample complexity is $O(1/\varepsilon^{5})$ and the time complexity is $\operatorname*{poly}(n,1/\varepsilon)$.

Then, given the guarantees of Lemma 8, Theorem 7 follows from Theorem 2To be more precise, we require the modification of Theorem 7 which is described in Section 4, in order to handle the case where the $\chi^{2}$-distance guarantees only hold for a known effective support.. The details of these results are presented in Section F.

Testing for Monotone Hazard Rate

In this section, we obtain our main result for testing for monotone hazard rate:

There exists an algorithm for testing monotone hazard rate over $[n]$ with sample complexity

and time complexity $\operatorname*{poly}(n,1/\varepsilon)$.

This implies the following optimal tester for the class:

Suppose $\varepsilon>\sqrt{\log(n/\varepsilon)}/n^{1/4}$. Then there exists an algorithm for testing monotone hazard rate over $[n]$ with sample complexity $O\left(\sqrt{n}/\varepsilon^{2}\right)$.

We obey the same framework as before, first applying a $\chi^{2}$-learner with the following guarantees:

Given $\varepsilon>0$ and sample access to a distribution $p$, there exists an algorithm with the following guarantees:

If $p\in\mathcal{MHR}_{n}$, the algorithm outputs a distribution $q\in\mathcal{MHR}_{n}$ and an $O(\varepsilon)$-effective support $S$ of $p$ such that $\chi^{2}(p_{S},q_{S})\leq\frac{\varepsilon^{2}}{500}$ with probability at least $5/6$;

The sample complexity is $O(\log(n/\varepsilon)/\varepsilon^{4})$ and the time complexity is $\operatorname*{poly}(n,1/\varepsilon)$.

As with log-concave distributions, this implies the following proper learning result:

Again, combining the learning guarantees of Lemma 9 with the appropriate variant of Theorem 2, we obtain Theorem 8. The details of the argument and proofs are presented in Section G.

Lower Bounds

We now prove sharp lower bounds for the classes of distributions we consider. We show that the example studied by Paninski [Pan08] to prove lower bounds on testing uniformity can be used to prove lower bounds for the classes we consider. They consider a class $\mathcal{Q}$ consisting of $2^{n/2}$ distributions defined as follows. Without loss of generality assume that $n$ is even. For each of the $2^{n/2}$ vectors $z_{0}z_{1}\ldots z_{n/2-1}\in\{-1,1\}^{n/2}$, define a distribution $q\in\mathcal{Q}$ over $[n]$ as follows.

Each distribution in $\mathcal{Q}$ has a total variation distance $c\varepsilon/2$ from $U_{n}$, the uniform distribution over $[n]$. By choosing $c$ to be an appropriate constant, Paninski [Pan08] showed that a distribution picked uniformly at random from $\mathcal{Q}$ cannot be distinguished from $U_{n}$ with fewer than $\sqrt{n}/\varepsilon^{2}$ samples with probability at least $2/3$.

Suppose $\mathcal{C}$ is a class of distributions such that

The uniform distribution $U_{n}$ is in $\mathcal{C}$,

then testing $\mathcal{C}$ is not easier than distinguishing $U_{n}$ from $\mathcal{Q}$. Invoking [Pan08] immediately implies that testing the class $\mathcal{C}$ requires $\Omega(\sqrt{n}/\varepsilon^{2})$ samples.

The lower bounds for all the one dimensional distributions will follow directly from this construction, and for testing monotonicity in higher dimensions, we extend this construction to $d\geq 1$, appropriately. These arguments are proved in Section H, leading to the following lower bounds for testing these classes:

For any $d\geq 1$, any algorithm for testing monotonicity over $[n]^{d}$ requires $\Omega(n^{d/2}/\varepsilon^{2})$ samples.

For $d\geq 1$, any algorithm for testing independence over $[n_{1}]\times\cdots\times[n_{d}]$ requires $\Omega\left(\frac{(n_{1}\cdot n_{2}\ldots\cdot n_{d})^{1/2}}{\varepsilon^{2}}\right)$ samples.

Any algorithm for testing unimodality, log-concavity, or monotone hazard rate over $[n]$ requires $\Omega(\sqrt{n}/\varepsilon^{2})$ samples.

Acknowledgements

The authors thank Clément Canonne and Jerry Li; the former for several useful comments and suggestions on previous drafts of this work, and both for helpful discussions and thoughts regarding independence testing.

References

Appendix A Moments of the Chi-Squared Statistic

We analyze the mean and variance of the statistic

where each $X_{i}$ is independently distributed according to \rm Poisson(\text{mp_{i}}).

The third equality is by noting the random variable has expectation $\lambda_{i}$ and the fourth equality substitutes the values of centralized moments of the Poisson distribution.

We first prove the key lemmas in the analysis of our $\chi^{2}$-test.

Proof of Lemma 2: The former case is straightforward from (1) and Property 2 of $q$.

Partitioning the support into $\mathcal{A}$ and $\bar{\mathcal{A}}$, we have

We consider the following cases separately:

$p(\bar{\mathcal{A}})\leq\varepsilon/2$: In this case,

$p(\bar{\mathcal{A}})>\varepsilon/2$: In this case, by the reverse triangle inequality,

Proof of Lemma 3: We bound the terms of (2) separately, starting with the first.

The second inequality is the AM-GM inequality, the third inequality uses that $q_{i}\geq\frac{\varepsilon}{50n}$ for all $i\in\mathcal{A}$, the last equality uses (1), and the final inequality substitutes a value $m\geq 20000\frac{\sqrt{n}}{\varepsilon^{2}}$.

The second term can be similarly bounded:

We now consider the two cases in the statement of our lemma.

Combining this with our expression for variance we get:

Appendix C Details on Testing Monotonicity

In this section, we prove the lemmas necessary for our monotonicity testing result.

Birgé [Bir87] showed that any monotone distribution is estimated to a total variation $\varepsilon$ with a $O(\log(n)/\varepsilon)$-piecewise constant distribution. Moreover, the intervals over which the output is constant is independent of the distribution $p$. This result, was strengthened to the Kullback-Leibler divergence by [AJOS14] to study the compression of monotone distributions. They upper bound the KL divergence by $\chi^{2}$ distance and then bound the $\chi^{2}$ distance. We extend this result to $[n]^{d}$. We divide $[n]^{d}$ into $b^{d}$ rectangles as follows. Let $\{I_{1},\dots,I_{b}\}$ be a partition of $[n]$ into consecutive intervals defined as:

The $\chi^{2}$ distance between $p$ and $\bar{p}$ can be bounded as

For ${\bf j}=(j_{1},\ldots,j_{d})\in\mathcal{S}_{\rm large}$, let ${\bf j}^{*}=(j_{1}^{*},\ldots,j_{b}^{*})$ be

We bound the expression above as follows.

Recall that $\gamma=2\log(n)/b>1/b$, implies that the expression above is at most $(1+2\gamma)^{d}-1$. This implies Lemma 4.

C.2 Monotone Learning

Our algorithm requires a distribution $q$ satisfying the properties discussed earlier. We learn a monotone distribution from samples as follows.

Before proving this result, we prove a general result for $\chi^{2}$ learning of arbitrary discrete distributions, adapting the result from [KOPS15]. For a distribution $p$, and a partition of the domain into $b$ intervals $I_{1},\ldots,I_{b}$, let $\bar{p}_{i}=p(I_{i})/|I_{i}|$ be the flattening of $p$ over these intervals. We saw that for monotone distributions there exists a partition of the domain such that $\bar{p}$ is close to the underlying distribution in $\chi^{2}$ distance.

Suppose we are given $m$ samples from a distribution $p$ and a partition $I_{1},\ldots,I_{b}$. Let $m_{j}$ be the number of samples that fall in $I_{j}$. For $i\in I_{j}$, let

Let $S_{j}=\sum_{i\in I_{j}}p_{i}^{2}$. The expected $\chi^{2}$ distance between $p$ and $q$ can be bounded as follows.

Suppose $\gamma=O(\log(n)/b)$, and $b=O(d\cdot\log(n)/\varepsilon^{2})$. Then, by Lemma 4,

Appendix D Details on testing Unimodality

Recall that to circumvent Birgé’s decomposition, we want to decompose the interval into disjoint intervals such that the probability of each interval is about $O(1/b)$, where $b$ is a parameter, specified later. In particular we consider a decomposition of $[n]$ with the following properties:

There are at most two intervals with $p(I)\leq 1/{2b}$.

Every other interval $I$ satisfies $p(I)\in\left[\frac{1}{2b},\frac{2}{b}\right]$.

Let $I_{1},\ldots,I_{L}$ denote the partition of $[n]$ corresponding to these intervals. Note that $L=O(b)$.

There is an algorithm that takes $O(b\log b)$ samples and outputs $I_{1},\ldots,I_{L}$ satisfying the properties above.

The first step in our algorithm is to estimate the total probability within each of these intervals. In particular,

There is an algorithm that takes $m^{\prime}=O(b\log b/\varepsilon^{2})$ samples from a distribution $p$, and with probability at least 9/10 outputs a distribution $\bar{q}$ that is constant on each $I_{L}$. Moreover, for any $j$ such that $p(I_{j})>1/2b$, $\bar{q}(I_{j})\in(1\pm\varepsilon)p(I_{j})$.

Consider any interval $I_{j}$ with $p(I_{j})\geq 1/2b$. The number of samples $N_{I_{j}}$ that fall in that interval is distributed $Binomial(m^{\prime},p(I_{j})$. Then by Chernoff bounds for $m^{\prime}>12b\log b/\varepsilon^{2}$,

where the last inequality uses the fact that $p(I_{j})\geq 1/2b$. ∎

The next step is estimate the distance of $q$ from $\mathcal{U}_{n}$. This is possible by a simple dynamic program, similar to the one used for monotonicity. If the estimated distance is more than $\varepsilon/2$, we output Reject.

Our next step is to remove certain intervals. This will be to ensure that when the underlying distribution is unimodal, we are able to estimate the distribution multiplicatively over the remaining intervals. In particular, we do the following preprocessing step:

Add the (at most 2) intervals with mass at most $1/2b$ to $A$.

Add all intervals $j$ with $q(I_{j})/|I_{j}|<\varepsilon/50n$ to $A$

If the distribution is unimodal, we can prove the following about the set of intervals ${A^{c}}$.

$p(I_{A^{c}})\geq 1-\varepsilon/25-1/b-O\left(\log n/(\varepsilon b)\right).$

Except at most one interval in ${A^{c}}$ every other interval $I_{j}$ satisfies,

If this holds, then the $\chi^{2}$ distance between $p$ and $q$ constrained to $A^{c}$, is at most $\varepsilon^{2}$. This lemma follows from the following result.

Let $C>2$. For a unimodal distribution over $[n]$, there are at most $\frac{4\log(50n/\varepsilon)}{C\varepsilon}$ intervals $I_{j}$ that satisfy $\frac{p_{j}^{+}}{p_{j}^{-}}<(1+\varepsilon/C)$.

To the contrary, if there are more than $\frac{4\log(50n/\varepsilon)}{C\varepsilon}$ intervals, then at least half of them are on one side of the mode, however this implies that the ratio of the largest probability and smallest probability is at least $(1+\varepsilon/C)^{j}$, and if $j>\frac{2\log(50n/\varepsilon)}{C\varepsilon}$, is at least $50n/\varepsilon$, contradicting that we have removed all such elements. ∎

We have one additional pre-processing step here. We compute $q(A^{c})$ and if it is smaller than $1-\varepsilon/25$, we output Reject.

Suppose there are $L^{\prime}$ intervals in $A^{c}$. Then, except at most one interval in $L^{\prime}$ we know that the $\chi^{2}$ distance between $p$ and $q$ is at most $\varepsilon^{2}$ when $p$ is unimodal, and the TV distance between $p$ and $q$ is at least $\varepsilon/2$ over $A^{c}$. We propose the following simple modification to take into account, the one interval that might introduce a high $\chi^{2}$ distance in spite of having a small total variation. If we knew the interval, we can simply remove it and proceed. Since we do not know where the interval lies, we do the following.

Let $Z_{j}$ be the $\chi^{2}$ statistic over the $i$th interval in $A^{c}$, computed with $O(\sqrt{n}/\varepsilon^{2})$ samples.

Let $Z_{l}$ be the largest among all $Z_{j}$’s.

If $\sum_{j,j\neq l}Z_{j}>m\varepsilon^{2}/10$, output Reject.

The objective of removing the largest $\chi^{2}$ statistic is our substitute for not knowing the largest interval. We now prove the correctness of this algorithm.

We only concentrate on the final step. The $\chi^{2}$ statistic over all but one interval are at most $c\cdot m\varepsilon^{2}$, and the variance is bounded as before. Since we remove the largest statistic, the expected value of the new statistic is strictly dominated by that of these intervals. Therefore, the algorithm outputs Accept with at least the same probability as if we removed the spurious interval.

This is the hard case to prove for unimodal distributions. We know that the $\chi^{2}$ statistic is large in this case, and we therefore have to prove that it remains large even after removing the largest test statistic $Z_{l}$.

We invoke Kolmogorov’s Maximal Inequality to this end.

In this section we prove Lemma 7. The proof is analogous to the proof for learning monotone distributions, and hinges on the following result of [KOPS15]. Given $m$ samples from a distribution $q$ over $n$ elements, the add-1 estimator (Laplace estimator) $q$ satisfies:

Now, suppose $p$ is a product distribution over ${\cal X}=[n_{1}]\times\cdots\times[n_{d}]$. We simply perform the add-1 estimation over each coordinate independently, giving a distribution $q^{1}\times\cdots\times q^{d}$. Since $p$ is a product distribution the estimates in each coordinate is independent. Therefore, a simple application of the previous result and independence of the coordinates implies

where (17) follows from $e^{x}\geq 1+x$. Using $e^{x}\leq 1+2x$ for $0\leq x\leq 1$, we have

when $m\geq\sum_{l}n_{l}$. Therefore, following an application of Markov’s inequality, when $m=\Omega((\sum_{l}n_{l})/\varepsilon^{2})$, Lemma 7 is proved.

Appendix F Details on Testing Log-Concavity

Proof of Lemma 8: We first draw samples from $p$ and obtain a $O(1/\varepsilon^{3/2})$-piecewise constant distribution $f$ by appropriately flattening the empirical distribution. The proof is now in two parts. In the first part, we show that if $p\in\mathcal{LCD}_{n}$ then $f$ will be close to $p$ in $\chi^{2}$ distance over its effective support. The second part involves proper learning of $p$. We will use a linear program on $f$ to find a distribution $q\in\mathcal{LCD}_{n}$. This distribution is such that if $p\in\mathcal{LCD}_{n}$, then $\chi^{2}(p,q)$ is small, and otherwise the algorithm will either output some $q\in\mathcal{LCD}_{n}$ (with no other relevant guarantees) or Reject.

Let $a$ be the minimum $i$ such that $p_{i}\geq\varepsilon^{3/2}/5$, and let $b$ be the maximum $i$ satisfying the same condition. Let $M=\{a,\dots,b\}$ or $\emptyset$ if $a$ and $b$ are undefined. By the guarantee provided by the DKW inequality, $p_{i}\geq\varepsilon^{3/2}/10$ for all $i\in M$. Furthermore, $\hat{p}_{i}\in p_{i}\pm\varepsilon^{3/2}/10\in(1\pm\varepsilon)\cdot p_{i}$. For each $i\in M$, let $f_{i}=\hat{p}_{i}$. We note that $|M|=O(1/\varepsilon)$, so this contributes $O(1/\varepsilon)$ constant pieces to $f$.

We now divide the rest of the domain into $t$ intervals, all but constantly many of measure $\Theta(\varepsilon^{3/2})$ (under $p$). This is done via the following iterative procedure. As a base case, set $r_{0}=0$. Define $I_{j}$ as $[l_{j},r_{j}]$, where $l_{j}=r_{j-1}+1$ and $r_{j}$ is the largest $j\in[n]$ such that $\hat{p}(I_{j})\leq 9\varepsilon^{3/2}/10$. The exception is if $I_{j}$ would intersect $M$ – in this case, we “skip” $M$: set $r_{j}=a-1$ and $l_{j+1}=b+1$. If such a $j$ exists, denote it by $j^{*}$. We note that $p(I_{j})\leq\hat{p}(I_{j})+\varepsilon^{5/2}/10\leq\varepsilon^{3/2}$. Furthermore, for all $j$ except $j^{*}$ and $t$, $r_{j}+1\not\in M$, so $p(I_{j})\geq 9\varepsilon^{3/2}/10-\varepsilon^{3/2}/5-\varepsilon^{5/2}/10\geq 3\varepsilon^{3/2}/5$. Observe that this lower bound implies that $t\leq\frac{2}{\varepsilon^{3/2}}$ for $\varepsilon$ sufficiently small.

For this part of the algorithm, we only care about the guarantees when $p\in\mathcal{LCD}_{n}$, so we assume this is the case.

For the domain $[n]\setminus M$, we let $f$ be the flattening of $\hat{p}$ over the intervals $I_{1},\dots I_{t}$. To analyze $f$, we need a structural property of log-concave distributions due to Chan, Diakonikolas, Servedio, and Sun [CDSS13]. This essentially states that a log-concave distribution cannot have a sudden increase in probability.

Let $p$ be a distribution over $[n]$ that is non-decreasing and log-concave on $[1,x]\subseteq[n]$. Let $I=[x,y]$ be an interval of mass $P(I)=\tau$, and suppose that the interval $J=[1,x-1]$ has mass $p(J)=\sigma>0$. Then

Recall that any log-concave distribution is unimodal, and suppose the mode of $p$ is at $i_{0}$. We will first focus on the intervals $I_{1},\dots,I_{t_{L}}$ which lie entirely to the left of $i_{0}$ and $M$. We will refer to $I_{j}$ as $L_{j}$ for all $j\leq t_{L}$. Note that $p$ is non-decreasing over these intervals.

The next steps to the analysis are as follows. First we show that the flattening of $p$ over $L_{j}$ is a multiplicative $(1+O(1/j))$ estimate for each $p_{i}\in L_{j}$. Then, we show that flattening the empirical distribution $\hat{p}$ over $L_{j}$ is a multiplicative $(1+O(1/j))$ estimate of $p(i)$ for each $i\in L_{j}$. Finally, we exclude a small number of intervals (those corresponding to $O(\varepsilon)$ mass at the left and right side of the domain, as well as $j^{*}$) in order to get the $\chi^{2}$ approximation we desire on an effective support.

First, recall that $p(L_{j})\leq\varepsilon^{3/2}$ for all $j$. Also, letting $J_{j}=[1,r_{j-1}]$, we have that $p(J_{j})\geq(j-1)\cdot 3\varepsilon^{3/2}/5$. Thus by Lemma 14, $p(r_{j})\leq p(l_{j})(1+2/(j-1))$. Since the distribution is non-decreasing in $L_{j}$, the flattening $\bar{p}$ of $p$ is such that $\bar{p}(i)\in p(i)(1\pm\frac{2}{j-1})$ for all $i\in L_{j}$.

We have that $p(L_{j})\geq 3\varepsilon^{3/2}/5$, and $\hat{p}(L_{j})\in p(L_{j})\pm\varepsilon^{5/2}/10$, so $\hat{p}(L_{j})\in p(L_{j})\cdot(1\pm\frac{\varepsilon}{6})$, and hence $\hat{p}(i)\in\bar{p}(i)\cdot(1\pm\frac{\varepsilon}{6})$ for all $i\in L_{j}$. Combining with the previous point, we have that

A symmetric statement holds for the intervals that lie entirely to the right of $i_{0}$ and $M$. We will refer to $I_{j}$ as $R_{t-j}$ for all $j>t_{L}$.

To summarize, we have the following guarantees for the distribution $f$:

For all $i\in M$, $f(i)\in p(i)\cdot(1\pm\varepsilon)$;

For all $i\in L_{j}$ (except $L_{1}$ and $L_{j^{*}}$), $f(i)\in p(i)\cdot\left(1\pm\frac{22}{3j}\right)$;

For all $i\in R_{j}$ (except $R_{1}$), $f(i)\in p(i)\cdot\left(1\pm\frac{22}{3j}\right)$;

Note that, in particular, we have multiplicative estimates for all intervals, except those in $L_{1}$, $L_{j^{*}}$, $R_{1}$ and the interval containing $i_{0}$. Let $S$ be the set of all intervals except $L_{j^{*}}$, $L_{j}$ and $R_{j}$ for $j\leq 1/\sqrt{\varepsilon}$, and the one containing $i_{0}$ Then, since each interval has probability mass at most $O(\varepsilon^{3/2})$ and we are excluding $O(1/\sqrt{\varepsilon})$ intervals, $p(S)>1-O(\varepsilon)$.

We now compute the $\chi^{2}$-distance induced by this approximation for elements in $S$. For an element $i\in L_{j}\cap S$, we have

Summing over all $i\in L_{j}\cap S$ gives

since the probability mass of $L_{j}$ is at most $\varepsilon^{3/2}$. Summing this over all $L_{j}$ for $j\geq 1/\sqrt{\varepsilon}$ and $j\neq j^{*}$ gives

Part 2.

To obtain a distribution $q\in\mathcal{LCD}_{n}$, we write a linear program. We will work in the log domain, so our variables will be $Q_{i}$, representing $\log q(i)$ for $i\in[n]$. We will use $F_{i}=\log f(i)$ as parameters in our LP. There will be no objective function, we simply search for a feasible point. Our constraints will be

If we run the linear program, then after a rescaling and summing the error over all the intervals in the LP gives us that the distance between $p$ and $q$ to be $O(\varepsilon^{2})$ $\chi^{2}$-distance in a set $S$ which has measure $p(S)\geq 1-4\varepsilon$, as desired.

If the linear program finds a feasible point, then we obtain a $q\in\mathcal{LCD}_{n}$. Furthermore, if $p\in\mathcal{LCD}_{n}$, this also tells us that (after a rescaling of $\varepsilon$), summing the error over all intervals implies that $\chi^{2}(p_{S},q_{S})\leq\frac{\varepsilon^{2}}{500}$ for a known set $S$ with $p(S)\geq 1-O(\varepsilon)$, as desired. If $M\neq\emptyset$, this algorithm works as described. The issue is if $M=\emptyset$, then we don’t know when the $L$ intervals end and the $R$ intervals begin. In this case, we run $O(1/\varepsilon)$ LPs, using each interval as the one containing $i_{0}$, and thus acting as the barrier between the $L$ intervals (to its left) and the $R$ intervals (to its right). If $p$ truly was log-concave, then one of these guesses will be correct and the corresponding LP will find a feasible point. $\hfill\qed$

Appendix G Details on MHR testing

Proof of Lemma 9: As with log-concave distributions, our method for MHR distributions can be split into two parts. In the first step, if $p\in\mathcal{MHR}_{n}$, we obtain a distribution $q$ which is $O(\varepsilon^{2})$-close to $p$ in $\chi^{2}$ distance on a set $\mathcal{A}$ of intervals such that $p(\mathcal{A})\geq 1-O(\varepsilon)$. $q$ will achieve this by being a multiplicative $(1+O(\varepsilon))$ approximation for each element within these intervals. This step is very similar to the decomposition used for unimodal distributions (described in Section D), so we sketch the argument and highlight the key differences.

The analysis will rely on the following lemma from [CDSS13], which roughly states that an MHR distribution is “almost” non-decreasing.

Let $p$ be an MHR distribution over $[n]$. Let $I=[a,b]\subset[n]$ be an interval, and $R=[b+1,n]$ be the elements to the right of $I$. Let $\eta=p(I)/p(R)$. Then $p(b+1)\geq\frac{1}{1+\eta}p(a)$.

As before, with unimodal distributions, we start by taking $O(\frac{b\log b}{\varepsilon^{2}})$ samples, with the goal of partitioning the domain into intervals of mass approximately $\Theta(1/b)$. First, we will ignore the left and rightmost intervals of mass $\Theta(\varepsilon)$. For all “heavy” elements with mass $\geq\Theta(1/b)$, we consider them as singletons. We note that Lemma 15 implies that there will be at most $O(1/\varepsilon)$ contiguous intervals of such elements. The rest of the domain is greedily divided (from left to right) into intervals of mass $\Theta(1/b)$, cutting an interval short if we reach one of the heavy elements. This will result in the guarantee that all but potentially $O(1/\varepsilon)$ intervals have $\Theta(1/b)$ mass.

Next, similar to unimodal distributions, considering the flattened distribution, we discard all intervals for which the per-element probability is not within a $(1\pm O(\varepsilon))$ multiplicative factor of the same value for both neighboring intervals. The claim is that all remaining intervals will have the property that the per-element probability is within a $(1\pm O(\varepsilon))$ multiplicative factor of the true probability. This is implied by Lemma 15. If there were a point in an interval which was above this range, the distribution must decrease slowly, and the next interval would have a much larger per-element weight, thus leading to the removal of this interval. A similar argument forbids us from missing an interval which contains a point that lies outside this range. Relying on the fact that truncating the left and rightmost intervals eliminates elements with low probability mass, similar to the unimodal case, one can show that we will remove at most $\log(n/\varepsilon)/\varepsilon$ intervals, and thus a $\log(n/\varepsilon)/b\varepsilon$ probability mass. Choosing $b=\Omega(\varepsilon^{2}/\log(n/\varepsilon))$ limits this to be $O(\varepsilon)$, as desired. At this point, if $p$ is indeed MHR, the multiplicative estimates guarantee that the result is $O(\varepsilon^{2})$-close in $\chi^{2}$-distance among the remaining intervals.