Testing Shape Restrictions of Discrete Distributions

Introduction

Inferring information about the probability distribution that underlies a data sample is an essential question in Statistics, and one that has ramifications in every field of the natural sciences and quantitative research. In many situations, it is natural to assume that this data exhibits some simple structure because of known properties of the origin of the data, and in fact these assumptions are crucial in making the problem tractable. Such assumptions translate as constraints on the probability distribution – e.g., it is supposed to be Gaussian, or to meet a smoothness or “fat tail” condition (see e.g., [Man63, Hou86, TLSM95]).

As a result, the problem of deciding whether a distribution possesses such a structural property has been widely investigated both in theory and practice, in the context of shape restricted inference [BDBB72, SS01] and model selection [MP07]. Here, it is guaranteed or thought that the unknown distribution satisfies a shape constraint, such as having a monotone or log-concave probability density function [SN99, BB05, Wal09, Dia16]. From a different perspective, a recent line of work in Theoretical Computer Science, originating from the papers of Batu et al. [BFR+00, BFF+01, GR00] has also been tackling similar questions in the setting of property testing (see [Ron08, Ron10, Rub12, Can15] for surveys on this field). This very active area has seen a spate of results and breakthroughs over the past decade, culminating in very efficient (both sample and time-wise) algorithms for a wide range of distribution testing problems [BDKR05, GMV06, AAK+07, DDS+13, CDVV14, AD15, DKN15b]. In many cases, this led to a tight characterization of the number of samples required for these tasks as well as the development of new tools and techniques, drawing connections to learning and information theory [VV10, VV11a, VV14].

In this paper, we focus on the following general property testing problem: given a class (property) of distributions $\mathcal{P}$ and sample access to an arbitrary distribution $D$, one must distinguish between the case that (a) $D\in\mathcal{P}$, versus (b) ${\lVert D-D^{\prime}{\rVert}}_{1}>\varepsilon$ for all $D^{\prime}\in\mathcal{P}$ (i.e., $D$ is either in the class, or far from it). While many of the previous works have focused on the testing of specific properties of distributions or obtained algorithms and lower bounds on a case-by-case basis, an emerging trend in distribution testing is to design general frameworks that can be applied to several property testing problems [Val11, VV11a, DKN15b, DKN15a]. This direction, the testing analog of a similar movement in distribution learning [CDSS13, CDSS14b, CDSS14a, ADLS15], aims at abstracting the minimal assumptions that are shared by a large variety of problems, and giving algorithms that can be used for any of these problems. In this work, we make significant progress in this direction by providing a unified framework for the question of testing various properties of probability distributions. More specifically, we describe a generic technique to obtain upper bounds on the sample complexity of this question, which applies to a broad range of structured classes. Our technique yields sample near-optimal and computationally efficient testers for a wide range of distribution families. Conversely, we also develop a general approach to prove lower bounds on these sample complexities, and use it to derive tight or nearly tight bounds for many of these classes.

Moreover, for the specific problems of identity and closeness testing,Recall that the identity testing problem asks, given the explicit description of a distribution $D^{\ast}$ and sample access to an unknown distribution $D$, to decide whether $D$ is equal to $D^{\ast}$ or far from it; while in closeness testing both distributions to compare are unknown. recent results of [DKN15b, DKN15a] describe a general algorithm which applies to a large range of shape or structural constraints, and yields optimal identity testers for classes of distributions that satisfy them. We observe that while the question they answer can be cast as a specialized instance of membership testing, our results are incomparable to theirs, both because of the distinction above (testing with versus testing for structure) and as the structural assumptions they rely on are fundamentally different from ours.

1 Results and Techniques

We then instantiate this result to obtain “out-of-the-box” computationally efficient testers for several classes of distributions, by showing that they satisfy the premise of our theorem (the definition of these classes is given in Section 2.1):

We remark that the aforementioned sample upper bounds are information-theoretically near-optimal in the domain size $n$ (up to logarithmic factors). See Table 1 and the following subsection for the corresponding lower bounds. We did not attempt to optimize the dependence on the parameter $\varepsilon$, though a more careful analysis can lead to such improvements.

To complement our upper bounds, we give a generic framework for proving lower bounds against testing classes of distributions. In more detail, we describe how to reduce – under a mild assumption on the property $\mathcal{C}$ – the problem of testing membership to $\mathcal{C}$ (“does $D\in\mathcal{C}$?”) to testing identity to $D^{\ast}$ (“does $D=D^{\ast}$?”), for any explicit distribution $D^{\ast}$ in $\mathcal{C}$. While these two problems need not in general be related,As a simple example, consider the class $\mathcal{C}$ of all distributions, for which testing membership is trivial. we show that our reduction-based approach applies to a large number of natural properties, and obtain lower bounds that nearly match our upper bounds for all of them. Moreover, this lets us derive a simple proof of the lower bound of [AD15] on testing the class of PBDs. The reader is referred to Theorem 6.1 for the formal statement of our reduction-based lower bound theorem. In this section, we state the concrete corollaries we obtain for specific structured distribution families:

Testing log-concavity, convexity, concavity, MHR, unimodality, $t$-modality, $t$-histograms, and $t$-piecewise degree-$d$ distributions each require ${\Omega\left({\sqrt{n}}/{\varepsilon^{2}}\right)}$ samples (the last three for $t=o(\sqrt{n})$ and $t(d+1)=o(\sqrt{n})$, respectively), for any $\varepsilon\geq 1/n^{O(1)}$.

Testing the classes of Binomial and Poisson Binomial Distributions each require ${\Omega\left({n^{1/4}}/{\varepsilon^{2}}\right)}$ samples, for any $\varepsilon\geq 1/n^{O(1)}$.

There exist absolute constants $c>0$ and $\varepsilon_{0}>0$ such that testing the class of $k$-SIIRV distributions requires \Omega\big{(}k^{1/2}n^{1/4}\big{)} samples, for any $k={o\left(n^{c}\right)}$ and $\varepsilon\leq\varepsilon_{0}$.

Tolerant testing of log-concavity, convexity, concavity, MHR, unimodality, and $t$-modality can be performed with O\big{(}\frac{1}{(\varepsilon_{2}-\varepsilon_{1})^{2}}\frac{n}{\log n}\big{)} samples, for $\varepsilon_{2}\geq C\varepsilon_{1}$ (where $C>2$ is an absolute constant).

Tolerant testing of the classes of Binomial and Poisson Binomial Distributions can be performed with O\big{(}\frac{1}{(\varepsilon_{2}-\varepsilon_{1})^{2}}\frac{\sqrt{n\log({1}/{\varepsilon_{1}})}}{\log n}\big{)} samples, for $\varepsilon_{2}\geq C\varepsilon_{1}$ (where $C>2$ is an absolute constant).

Tolerant testing of log-concavity, convexity, concavity, MHR, unimodality, and $t$-modality each require ${\Omega\left(\frac{1}{(\varepsilon_{2}-\varepsilon_{1})}\frac{n}{\log n}\right)}$ samples (the latter for $t=o(n)$).

Tolerant testing of the classes of Binomial and Poisson Binomial Distributions each require ${\Omega\left(\frac{1}{(\varepsilon_{2}-\varepsilon_{1})}\frac{\sqrt{n}}{\log n}\right)}$ samples.

We point out that our main theorem is likely to apply to many other classes of structured distributions, due to the mild structural assumptions it requires. However, we did not attempt here to be comprehensive; but rather to illustrate the generality of our approach. Moreover, for all properties considered in this paper the generic upper and lower bounds we derive through our methods turn out to be optimal up to at most polylogarithmic factors (with regard to the support size). The reader is referred to Table 1 for a summary of our results and related work.

2 Organization of the Paper

We start by giving the necessary background and definitions in Section 2, before turning to our main result, the proof of Theorem 1.1 (our general testing algorithm) in Section 3. In Section 4, we establish the necessary structural theorems for each classes of distributions considered, enabling us to derive the upper bounds of Table 1. Section 5 introduces a slight modification of our algorithm which yields stronger testing results for classes of distributions with small effective support, and use it to derive Section 1.1, our upper bound for Poisson Binomial distributions. Second, Section 6 contains the details of our lower bound methodology, and of its applications to the classes of Table 1. Finally, Section 6.2 is concerned with the extension of this methodology to tolerant testing, of which Section 7 describes a generic upper bound counterpart.

Notation and Preliminaries

We give here the formal descriptions of the classes of distributions involved in this work. Recall that a distribution $D$ over $[n]$ is monotone (non-increasing) if its probability mass function (pmf) satisfies $D(1)\geq D(2)\geq\dots D(n)$. A natural generalization of the class $\mathcal{M}$ of monotone distributions is the set of $t$-modal distributions, i.e. distributions whose pmf can go “up and down” or “down and up” up to $t$ times:Note that this slightly deviates from the Statistics literature, where only the peaks are counted as modes (so that what is usually referred to as a bimodal distribution is, according to our definition, $3$-modal).

Fix any distribution $D$ over $[n]$, and integer $t$. $D$ is said to have $t$ modes if there exists a sequence $i_{0}<\dots<i_{t+1}$ such that either $(-1)^{j}D(i_{j})<(-1)^{j}D(i_{j+1})$ for all $0\leq j\leq t$, or $(-1)^{j}D(i_{j})>(-1)^{j}D(i_{j+1})$ for all $0\leq j\leq t$. We call $D$ $t$-modal if it has at most $t$ modes, and write $\mathcal{M}_{t}$ for the class of all $t$-modal distributions (omitting the dependence on $n$). The particular case of $t=1$ corresponds to the set $\mathcal{M}_{1}$ of unimodal distributions.

A distribution $D$ over $[n]$ is said to be log-concave if it satisfies the following conditions: (i) for any $1\leq i<j<k\leq n$ such that $D(i)D(k)>0$, $D(j)>0$; and (ii) for all $1<k<n$, $D(k)^{2}\geq D(k-1)D(k+1)$. We write $\mathcal{L}$ for the class of all log-concave distributions (omitting the dependence on $n$).

A distribution $D$ over $[n]$ is said to be concave if it satisfies the following conditions: (i) for any $1\leq i<j<k\leq n$ such that $D(i)D(k)>0$, $D(j)>0$; and (ii) for all $1<k<n$ such that $D(k-1)D(k+1)>0$, $2D(k)\geq D(k-1)+D(k+1)$; it is convex if the reverse inequality holds in (ii). We write $\mathcal{K}^{-}$ (resp. $\mathcal{K}^{+}$) for the class of all concave (resp. convex) distributions (omitting the dependence on $n$).

It is not hard to see that convex and concave distributions are unimodal; moreover, every concave distribution is also log-concave, i.e. $\mathcal{K}^{-}\subseteq\mathcal{L}$. Note that in both Section 2.1 and Section 2.1, condition (i) is equivalent to enforcing that the distribution be supported on an interval.

A distribution $D$ over $[n]$ is said to have monotone hazard rate (MHR) if its hazard rate $H(i)\stackrel{{\scriptstyle\rm def}}{{=}}\frac{D(i)}{\sum_{j=i}^{n}D(j)}$ is a non-decreasing function. We write $\mathcal{MHR}$ for the class of all MHR distributions (omitting the dependence on $n$).

It is known that every log-concave distribution is both unimodal and MHR (see e.g. [An96, Proposition 10]), and that monotone distributions are MHR. Two other classes of distributions have elicited significant interest in the context of density estimation, that of histograms (piecewise constant) and piecewise polynomial densities:

A distribution $D$ over $[n]$ is said to be a $t$-piecewise degree-$d$ distribution if there is a partition of $[n]$ into $t$ disjoint intervals $I_{1},\dots,I_{t}$ such that $D(i)=p_{j}(i)$ for all $i\in I_{j}$, where each $p_{1},\dots p_{t}$ is a univariate polynomial of degree at most $d$. We write $\mathcal{P}_{t,d}$ for the class of all $t$-piecewise degree-$d$ distributions (omitting the dependence on $n$). (We note that $t$-piecewise degree- distributions are also commonly referred to as $t$-histograms, and write $\mathcal{H}_{t}$ for $\mathcal{P}_{t,0}$.)

Finally, we recall the definition of the two following classes, which both extend the family of Binomial distributions $\mathcal{BIN}_{n}$: the first, by removing the need for each of the independent Bernoulli summands to share the same bias parameter.

It is not hard to show that Poisson Binomial Distributions are in particular log-concave. One can generalize even further, by allowing each random variable of the summation to be integer-valued:

2 Tools from previous work

Let $D$ be a distribution on a domain $S$. (a) If $\max_{i\in S}D(i)\leq(1+\varepsilon)\min_{i\in S}D(i)$, then ${\lVert D{\rVert}}_{2}^{2}\leq(1+\varepsilon^{2})/\left\lvert S\right\rvert$. (b) If ${\lVert D{\rVert}}_{2}^{2}\leq(1+\varepsilon^{2})/\left\lvert S\right\rvert$, then ${\lVert D-\mathcal{U}_{S}{\rVert}}_{1}\leq\varepsilon$.

To check condition (b) above we shall rely on the following, which one can derive from the techniques in [DKN15b] and whose proof we defer to Appendix A:

If ${\lVert D-\mathcal{U}_{I}{\rVert}}_{2}>{\varepsilon}/{\sqrt{\left\lvert I\right\rvert}}$, then the algorithm outputs no with probability at least $1-\delta$;

If ${\lVert D-\mathcal{U}_{I}{\rVert}}_{2}\leq{\varepsilon}/{2\sqrt{\left\lvert I\right\rvert}}$, then the algorithm outputs yes with probability at least $1-\delta$.

Finally, we will also rely on a classical result from Probability, the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality, restated below:

Let $D$ be a distribution over $[n]$. Given $m$ independent samples $x_{1},\dots,x_{m}$ from $D$, define the empirical distribution $\hat{D}$ as follows:

In particular, this implies that ${O\left(1/\varepsilon^{2}\right)}$ samples suffice to learn a distribution up to $\varepsilon$ in Kolmogorov distance.

The General Algorithm

In this section, we obtain our main result, restated below: See 1.1

Turning to the proof, we start by defining formally the “structural criterion” we shall rely on, before describing the algorithm at the heart of our result in Section 3.1. (We note that a modification of this algorithm will be described in Section 5, and will allow us to derive Section 1.1.)

$\displaystyle\max_{i\in I_{j}}D(i)\leq(1+\gamma)\cdot\min_{i\in I_{j}}D(i)$.

Further, if $\mathcal{I}(\gamma,D)$ is dyadic (i.e., each $I_{k}$ is of the form $[j\cdot 2^{i}+1,(j+1)\cdot 2^{i}]$ for some integers $i,j$, corresponding to the leaves of a recursive bisection of $[n]$), then $\mathcal{C}$ is said to be $(\gamma,L)$-splittable.

If $\mathcal{C}$ is $(\gamma,L)$-decomposable, then it is $(\gamma,{O\left(L\log n\right)})$-splittable.

In order to complete the proof of the lemma, notice that the two conditions in Section 3 are closed under taking subsets. ∎

1 The algorithm

Theorem 1.1, and with it Section 1.1 and Section 1.1 will follow from the theorem below, combined with the structural theorems from Section 4:

Let $\mathcal{C}$ be a class of distributions over $[n]$ for which the following holds.

$\mathcal{C}$ is $(\gamma,L(\gamma,n))$-splittable;

Then, the algorithm TestSplittable (Algorithm 1) is a ${O\left(\max\left({\sqrt{nL}}\log n/{\varepsilon^{3}},L/{\varepsilon^{2}}\right)\right)}$-sample tester for $\mathcal{C}$, for $L=L(\varepsilon,n)$. (Moreover, if $\textsc{ProjectionDist}_{\mathcal{C}}$ is computationally efficient, then so is TestSplittable.)

2 Proof of Theorem 3.1

We now give the proof of our main result (Theorem 3.1), first analyzing the sample complexity of Algorithm 1 before arguing its correctness. For the latter, we will need the following simple lemma from [ILR12], restated below:

Let $D$ be a distribution over $[n]$, and $\delta\in(0,1]$. Given $m\geq C\cdot\frac{\log\frac{n}{\delta}}{\eta}$ independent samples from $D$ (for some absolute constant $C>0$), with probability at least $1-\delta$ we have that, for every interval $I\subseteq[n]$:

if $D(I)\geq\frac{\eta}{4}$, then $\frac{D(I)}{2}\leq\frac{m_{I}}{m}\leq\frac{3D(I)}{2}$;

if $\frac{m_{I}}{m}\geq\frac{\eta}{2}$, then $D(I)>\frac{\eta}{4}$;

if $\frac{m_{I}}{m}<\frac{\eta}{2}$, then $D(I)<\eta$;

where $m_{I}\stackrel{{\scriptstyle\rm def}}{{=}}\left\lvert\left\{\;j\in[m]\;\colon\;x_{j}\in I\;\right\}\right\rvert$ is the number of the samples falling into $I$.

3 Sample complexity.

The sample complexity is immediate, and comes from Steps 6 and 22. The total number of samples is

4 Correctness.

Say an interval $I$ considered during the execution of the “Decomposition” step is heavy if $m_{I}$ is big enough on Step 9, and light otherwise; and let $\mathscr{H}$ and $\mathscr{L}$ denote the sets of heavy and light intervals respectively. By choice of $m$ and a union bound over all $\left\lvert I\right\rvert^{2}$ possible intervals, we can assume on one hand that with probability at least $9/10$ the guarantees of 3.2 hold simultaneously for all intervals considered. We hereafter condition on this event.

We first argue that if the algorithm does not reject in Step 15, then with probability at least $9/10$ we have ${\lVert D-\Phi(D,\mathcal{I}){\rVert}}_{1}\leq\varepsilon/20$. Indeed, we can write

If $I^{\prime}\in\mathscr{H}$, then by our choice of threshold we can apply Section 2.2 with $\delta=\frac{1}{10L}$; conditioning on all of the (at most $L$) events happening, which overall fails with probability at most $1/10$ by a union bound, we get

If $I^{\prime}\in\mathscr{L}$, then we claim that $D(I^{\prime})\leq\max(\kappa,2c\cdot\frac{\sqrt{\left\lvert I^{\prime}\right\rvert}}{m\varepsilon^{2}}\log\frac{1}{\delta})$. Clearly, this is true if $D(I^{\prime})\leq\kappa$, so it only remains to show that $D(I^{\prime})\leq 2c\cdot\frac{\sqrt{\left\lvert I^{\prime}\right\rvert}}{m\varepsilon^{2}}\log\frac{1}{\delta}$. But this follows from 3.2 i, as if we had $D(I^{\prime})>2c\cdot\frac{\sqrt{\left\lvert I^{\prime}\right\rvert}}{m\varepsilon^{2}}\log\frac{1}{\delta}$ then $m_{I^{\prime}}$ would have been big enough, and $I^{\prime}\notin\mathscr{L}$. Overall,

for a sufficiently big choice of constant $C>0$ in the definition of $m$; where we first used that $\left\lvert\mathscr{L}\right\rvert\leq L$, and then that $\sum_{I^{\prime}\in\mathscr{L}}\sqrt{\frac{\left\lvert I^{\prime}\right\rvert}{\left\lvert I\right\rvert}}\leq\sqrt{L}$ by Jensen’s inequality.

Overall, this happens except with probability at most $1/10+1/10+1/10<1/3$.

Assume $D\in\mathcal{C}$. Then the choice of of $\gamma$ and $L$ ensures the existence of a good dyadic partition $\mathcal{I}(\gamma,D)$ in the sense of Section 3. For any $I$ in this partition for which i holds ($D(I)\leq\frac{\gamma}{L}<\frac{\kappa}{2}$), $I$ will have $\frac{m_{I}}{m}<\kappa$ and be kept as a “light leaf” (this by contrapositive of 3.2 ii). For the other ones, ii holds: let $I$ be one of these (at most $L$) intervals.

If $m_{I}$ is too small on Step 9, then $I$ is kept as “light leaf.”

Structural Theorems

In this section, we show that a wide range of natural distribution families are succinctly decomposable, and provide efficient projection algorithms for each class.

For all $\gamma>0$, the class $\mathcal{M}$ of monotone distributions on $[n]$ is $(\gamma,L)$-splittable for $L\stackrel{{\scriptstyle\rm def}}{{=}}{O\left(\frac{\log^{2}n}{\gamma}\right)}$.

Note that this proof can already be found in [BKR04, Theorem 10], interwoven with the analysis of their algorithm. For the sake of being self-contained, we reproduce the structural part of their argument, removing its algorithmic aspects:

if $D(I^{(j)}_{i})\leq\frac{\gamma}{L}$, then $I^{(j)}_{i}$ is added as element of $\mathcal{I}^{(j+1)}$ (“marked as leaf”);

else, if $D(b^{(j)}_{i})\leq(1+\gamma)D(a^{(j)}_{i})$, then $I^{(j)}_{i}$ is added as element of $\mathcal{I}^{(j+1)}$ (“marked as leaf”);

otherwise, bisect $I^{(j)}$ in $I^{(j)}_{\rm L}$, $I^{(j)}_{\rm R}$ (with $\left\lvert I^{(j)}_{\rm L}\right\rvert=\left\lceil\left\lvert I^{(j)}\right\rvert/2\right\rceil$) and add both $I^{(j)}_{\rm L}$ and $I^{(j)}_{\rm R}$ as elements of $\mathcal{I}^{(j+1)}$.

The recursion above defines a complete binary tree (with the leaves being the intervals satisfying a or b, and the internal nodes the other ones). Let $t$ be the number of recursion steps the process goes through before converging to $\mathcal{I}$ (height of the tree); as mentioned above, we have $t\leq\log n$ (as we start with an interval of size $n$, and the length is halved at each step.). Observe further that if at any point an interval $I^{(j)}_{i}=[a^{(j)}_{i},b^{(j)}_{i}]$ has $D(a^{(j)}_{i})\leq\frac{\gamma}{nL}$, then it immediately (as well as all the $I^{(j)}_{k}$’s for $k\geq i$ by monotonicity) satisfies a and is no longer split (“becomes a leaf”). So at any $j\leq t$, the number of intervals $i_{j}$ for which neither a nor b holds must satisfy

where $a_{k}$ denotes the beginning of the $k$-th interval (again we use monotonicity to argue that the extrema were reached at the ends of each interval), so that $i_{j}\leq 1+\frac{\log\frac{nL}{\gamma}}{\log(1+\gamma)}$. In particular, the total number of internal nodes is then

For all $\gamma>0$, the class $\mathcal{M}_{1}$ of unimodal distributions on $[n]$ is $(\gamma,L)$-decomposable for $L\stackrel{{\scriptstyle\rm def}}{{=}}{O\left(\frac{\log^{2}n}{\gamma}\right)}$.

For any $D\in\mathcal{M}_{1}$, $[n]$ can be partitioned in two intervals $I$, $J$ such that $D_{I}$, $D_{J}$ are either monotone non-increasing or non-decreasing. Applying Theorem 4.1 to $D_{I}$ and $D_{J}$ and taking the union of both partitions yields a (no longer necessarily dyadic) partition of $[n]$. ∎

The same argument yields an analogue statement for $t$-modal distributions:

For any $t\geq 1$ and all $\gamma>0$, the class $\mathcal{M}_{t}$ of $t$-modal distributions on $[n]$ is $(\gamma,L)$-decomposable for $L\stackrel{{\scriptstyle\rm def}}{{=}}{O\left(\frac{t\log^{2}n}{\gamma}\right)}$.

For all $\gamma>0$, the classes $\mathcal{L}$, $\mathcal{K}^{-}$ and $\mathcal{K}^{+}$ of log-concave, concave and convex distributions on $[n]$ are $(\gamma,L)$-decomposable for $L\stackrel{{\scriptstyle\rm def}}{{=}}{O\left(\frac{\log^{2}n}{\gamma}\right)}$.

This is directly implied by Section 4.1, recalling that log-concave, concave and convex distributions are unimodal. ∎

For all $\gamma>0$, the class $\mathcal{MHR}$ of MHR distributions on $[n]$ is $(\gamma,L)$-decomposable for $L\stackrel{{\scriptstyle\rm def}}{{=}}{O\left(\frac{\log n}{\gamma}\right)}$.

For all $\gamma>0$, $t,d\geq 0$, the class $\mathcal{P}_{t,d}$ of $t$-piecewise degree-$d$ distributions on $[n]$ is $(\gamma,L)$-decomposable for $L\stackrel{{\scriptstyle\rm def}}{{=}}{O\left(\frac{t(d+1)}{\gamma}\log^{2}n\right)}$. (Moreover, for the class of $t$-histograms $\mathcal{H}_{t}$ ($d=0$) one can take $L=t$.)

The last part of the statement is obvious, so we focus on the first claim. Observing that each of the $t$ pieces of a distribution $D\in\mathcal{P}_{t,d}$ can be subdivided in at most $d+1$ intervals on which $D$ is monotone (being degree-$d$ polynomial on each such pieces), we obtain a partition of $[n]$ into at most $t(d+1)$ intervals. $D$ being monotone on each of them, we can apply an argument almost identical to that of Theorem 4.1 to argue that each interval can be further split into $O(\log^{2}n/\gamma)$ subintervals, yielding a good decomposition with $O(t(d+1)\log^{2}n/\gamma)$ pieces. ∎

2 Projection Step: computing the distances

We focus in this section on achieving the sample complexities stated in Section 1.1, Section 1.1, and Section 1.1. While almost all the distance estimation procedures we give in this section are efficient, running in time polynomial in all the parameters or even with only a polylogarithmic dependence on $n$, there are two exceptions – namely, the procedures for monotone hazard rate (Section 4.2) and log-concave (Section 4.2) distributions. We do describe computationally efficient procedures for these two cases as well in Section 4.2.1, at a modest additive cost in the sample complexity.

We here give a naive algorithm for these two problems, based on an exhaustive search over a (huge) $\varepsilon$-cover $\mathcal{S}$ of distributions over $[n]$. Essentially, $\mathcal{S}$ contains all possible distributions whose probabilities $p_{1},\dots,p_{n}$ are of the form $j\varepsilon/n$, for $j\in\{0,\dots,n/\varepsilon\}$ (so that $\left\lvert\mathcal{S}\right\rvert={O\left((n/\varepsilon)^{n}\right)}$). It is not hard to see that this indeed defines an $\varepsilon$-cover of the set of all distributions, and moreover that it can be computed in time $\operatorname*{poly}(\left\lvert\mathcal{S}\right\rvert)$. To approximate the distance from an explicit distribution $D$ to the class $\mathcal{C}$ (either $\mathcal{MHR}$ or $\mathcal{L}$), it is enough to go over every element $S$ of $\mathcal{S}$, checking (this time, efficiently) if ${\lVert S-D{\rVert}}_{1}\leq\varepsilon$ and if there is a distribution $P\in\mathcal{C}$ close to $S$ (this time, pointwise, that is $\left\lvert P(i)-S(i)\right\rvert\leq\varepsilon/n$ for all $i$) – which also implies ${\lVert S-P{\rVert}}_{1}\leq\varepsilon$ and thus ${\lVert P-D{\rVert}}_{1}\leq 2\varepsilon$. The test for pointwise closeness can be done by checking feasibility of a linear program with variables corresponding to the logarithm of probabilities, i.e. $x_{i}\equiv\ln P(i)$. Indeed, this formulation allows to rephrase the log-concave and MHR constraints as linear constraints, and pointwise approximation is simply enforcing that $\ln(S(i)-\varepsilon/n)\leq x_{i}\leq\ln(S(i)+\varepsilon/n)$ for all $i$. At the end of this enumeration, the procedure accepts if and only if for some $S$ both ${\lVert S-D{\rVert}}_{1}\leq\varepsilon$ and the corresponding linear program was feasible. ∎

Before proving it, we describe how this will enable us to get the desired time complexity for $\textsc{ProjectionDist}_{\mathcal{H}_{t}}$. Phrased differently, the claim above allows us to run our dynamic program using the ${O\left(1/\eta\right)}$ endpoints of the ${O\left(1/\eta\right)}$ instead of the $n$ points of the domain, paying only an additive error $O(t\eta)$. Setting $\eta=\frac{\varepsilon}{4t}$, the guarantee for $\textsc{ProjectionDist}_{\mathcal{H}_{t}}$ follows.

Turning now to $\textsc{ProjectionDist}_{\mathcal{P}_{t,d}}$, we apply the same initial dynamic programming approach, which will result on a running time of ${O\left(n^{2}t\cdot T\right)}$, where $T$ is the time required to estimate (to sufficient accuracy) the distance of a given (sub)distribution over an interval $I$ onto the space $\mathcal{P}_{d}$ of degree-$d$ polynomials. Specifically, we will invoke the following result, adapted from [CDSS14a] to our setting:

Combining these ideas yield the following distance estimation lemmas:

If there is $P\in\mathcal{MHR}$ such that ${\lVert D-P{\rVert}}_{1}\leq\varepsilon$ and ${\lVert D^{\prime}-P{\rVert}_{\rm Kol}}\leq\varepsilon^{3}$, then the procedure returns yes;

If there is $P\in\mathcal{L}$ such that ${\lVert D-P{\rVert}}_{1}\leq\varepsilon$ and ${\lVert D^{\prime}-P{\rVert}_{\rm Kol}}\leq\frac{\varepsilon^{2}}{\log^{2}(1/\varepsilon)}$, then the procedure returns yes;

Going Further: Reducing the Support Size

Given $\varepsilon>0$, the $\varepsilon$-effective support of a distribution $D$ is the smallest interval $I$ such that $D(I)\geq 1-\varepsilon$.

The last definition we shall require is of the conditioned distributions of a class $\mathcal{C}$:

For any class of distributions $\mathcal{C}$ over $[n]$, define the set of conditioned distributions of $\mathcal{C}$ (with respect to $\varepsilon>0$ and interval $I\subseteq[n]$) as $\mathcal{C}^{\varepsilon,I}\stackrel{{\scriptstyle\rm def}}{{=}}\left\{\;D_{I}\;\colon\;D\in\mathcal{C},D(I)\geq 1-\varepsilon\;\right\}$.

Finally, we will require the following simple result:

Let $D$ be a distribution over $[n]$, and $I\subseteq[n]$ an interval such that $D(I)\geq 1-\frac{\varepsilon}{10}$. Then,

If $D\in\mathcal{C}$, then $D_{I}\in\mathcal{C}^{\frac{\varepsilon}{10},I}$;

The first item is obvious. As for the second, let $P\in\mathcal{C}$ be any distribution with $P(I)\geq 1-\frac{\varepsilon}{10}$. By assumption, ${\lVert D-P{\rVert}}_{1}>\varepsilon$: but we have, writing $\alpha=1/10$,

We now proceed to state and prove our result – namely, efficient testing of structured classes of distributions with nice concentration properties.

Let $\mathcal{C}$ be a class of distributions over $[n]$ for which the following holds.

there is a function $M(\cdot,\cdot)$ such that each $D\in\mathcal{C}$ has $\varepsilon$-effective support of size at most $M(n,\varepsilon)$;

for every $\varepsilon\in$ and interval $I\subseteq[n]$, $\mathcal{C}^{\varepsilon,I}$ is $(\gamma,L)$-splittable;

By the choice of $m$ and the DKW inequality, with probability at least $23/24$ the estimate $\hat{D}$ satisfies ${\lVert D-\hat{D}{\rVert}_{\rm Kol}}\leq\frac{\varepsilon}{60}$. Conditioning on that from now on, we get that $D(I)\geq\hat{D}(I)-\frac{\varepsilon}{30}\geq 1-\frac{\varepsilon}{10}$. Furthermore, denoting by $j$ and $k$ the two inner endpoints of $J$ and $K$ in Steps 6 and 7, we have $D(J\cup\{j+1\})\geq\hat{D}(J\cup\{j+1\})-\frac{\varepsilon}{60}>\frac{\varepsilon}{60}$ (similarly for $D(K\cup\{k-1\})$), so that $I$ has size at most $\sigma+1$, where $\sigma$ is the $\frac{\varepsilon}{60}$-effective support size of $D$.

Finally, note that since $D(I)={\Omega\left(1\right)}$ by our conditioning, the simulation of samples by rejection sampling will succeed with probability at least $23/24$ and the algorithm will not output FAIL.

If $D\in\mathcal{C}$, then by the setting of $\tau$ (set to be an upper bound on the $\frac{\varepsilon}{60}$-effective support size of any distribution in $\mathcal{C}$) the algorithm will go beyond Step 8. The call to TestSplittable will then end up in the algorithm returning ACCEPT in Step 14, with probability at least $2/3$ by Section 5, Theorem 1.1 and our choice of parameters.

Similarly, if $D$ is $\varepsilon$-far from $\mathcal{C}$, then either its effective support is too large (and then the test on Step 8 fails), or the main tester will detect that its conditional distribution on $I$ is $\frac{7\varepsilon}{10}$-far from $\mathcal{C}$ and output REJECT in Step 14.

Overall, in either case the algorithm is correct except with probability at most $1/24+1/24+1/3=5/12$ (by a union bound). Repeating constantly many times and outputting the majority vote brings the probability of failure down to $1/3$. ∎

2 Application: Testing Poisson Binomial Distributions

In this section, we illustrate the use of our generic two-stage approach to test the class of Poisson Binomial Distributions. Specifically, we prove the following result:

This is a direct consequence of Theorem 5.1 and the lemmas below. The first one states that, indeed, PBDs have small effective support:

For any $\varepsilon>0$, a PBD has $\varepsilon$-effective support of size ${O\left(\sqrt{n\log(1/\varepsilon)}\right)}$.

It is clear that if $D\in\mathcal{PBD}_{n}$ (and therefore is unimodal), then for any interval $I\subseteq[n]$ the conditional distribution $D_{I}$ is still unimodal, and thus the class of conditioned PBDs $\mathcal{PBD}_{n}^{\varepsilon,I}\stackrel{{\scriptstyle\rm def}}{{=}}\left\{\;D_{I}\;\colon\;D\in\mathcal{PBD}_{n},D(I)\geq 1-\varepsilon\;\right\}$ falls under Section 4.1. The last piece we need to apply our generic testing framework is the existence of an algorithm to compute the distance between an (explicit) distribution and the class of conditioned PBDs. This is provided by our next lemma:

For all $n,\gamma>0$, there exists a set $\mathcal{S}_{\gamma}\subseteq\mathcal{PBD}_{n}$ such that:

$\mathcal{S}_{\gamma}$ is a $\gamma$-cover of $\mathcal{PBD}_{n}$; that is, for all $D\in\mathcal{PBD}_{n}$ there exists some $D^{\prime}\in\mathcal{S}_{\gamma}$ such that ${\lVert D-D^{\prime}{\rVert}}_{1}\leq\gamma$

$\left\lvert\mathcal{S}_{\gamma}\right\rvert\leq n\left({1/\gamma}\right)^{{O\left(\log{1/\gamma}\right)}}$

$\mathcal{S}_{\gamma}$ can be computed in time $n\left({1/\gamma}\right)^{{O\left(\log{1/\gamma}\right)}}$

and each $D\in\mathcal{S}_{\gamma}$ is explicitly described by its set of parameters.

We further observe that the factor $n$ in both the size of the cover and running time can be easily removed in our case, as we know a good approximation of the support size of the candidate PBDs. (That is, we only need to enumerate over a subset of the cover of [DKS15], that of the PBDs with effective support compatible with our distribution $D$.)

Combining the above, we invoke Theorem 5.1 with $M(n,\varepsilon)=O(\sqrt{n\log(1/\varepsilon)})$ (5.2) and L(m,\gamma)=O\big{(}\frac{\log^{2}m}{\gamma}\big{)} (Section 4.1). This yields the claimed sample complexity; finally, the efficiency is a direct consequence of Section 5.2. ∎

Lower Bounds

We now turn to proving converses to our positive results – namely, that many of the upper bounds we obtain cannot be significantly improved upon. As in our algorithmic approach, we describe for this purpose a generic framework for obtaining lower bounds.

In order to state our results, we will require the usual definition of agnostic learning. Recall that an algorithm is said to be a semi-agnostic learner for a class $\mathcal{C}$ if it satisfies the following. Given sample access to an arbitrary distribution $D$ and parameter $\varepsilon$, it outputs a hypothesis $\hat{D}$ which (with high probability) does “almost as well as it gets”:

The motivation for our result is the observation of [BKR04] that “monotonicity is at least as hard as uniformity.” Unfortunately, their specific argument does not generalize easily to other classes of distributions, making it impossible to extend it readily. The starting point of our approach is to observe that while uniformity testing is hard in general, it becomes very easy under the promise that the distribution is monotone, or even only close to monotone (namely, ${O\left(1/\varepsilon^{2}\right)}$ samples suffice). This can give an alternate proof of the lower bound for monotonicity testing, via a different reduction: first, test if the unknown distribution is monotone; if it is, test whether it is uniform, now assuming closeness to monotone.

More generally, this idea applies to any class $\mathcal{C}$ which (a) contains the uniform distribution, and (b) for which we have a ${o\left(\sqrt{n}\right)}$-sample agnostic learner $\mathcal{L}$, as follows. Assuming we have a tester $\mathcal{T}$ for $\mathcal{C}$ with sample complexity ${o\left(\sqrt{n}\right)}$, define a uniformity tester as below.

test if $D\in\mathcal{C}$ using $\mathcal{T}$; if not, reject (as $\mathcal{U}\in\mathcal{C}$, $D$ cannot be uniform);

otherwise, agnostically learn $D$ with $\mathcal{L}$ (since $D$ is close to $\mathcal{C}$), and obtain hypothesis $\hat{D}$;

check offline if $\hat{D}$ is close to uniform.

By assumption, $\mathcal{T}$ and $\mathcal{L}$ each use ${o\left(\sqrt{n}\right)}$ samples, so does the whole process; but this contradicts the lower bound of [BFR+00, Pan08] on uniformity testing. Hence, $\mathcal{T}$ must use ${\Omega\left(\sqrt{n}\right)}$ samples.

This “testing-by-narrowing” reduction argument can be further extended to other properties than to uniformity, as we show below:

Let $\mathcal{C}$ be a class of distributions over $[n]$ for which the following holds:

there exists a semi-agnostic learner $\mathcal{L}$ for $\mathcal{C}$, with sample complexity $q_{L}(n,\varepsilon,\delta)$ and “agnostic constant” $c$;

there exists a subclass $\mathcal{C}_{\rm Hard}\subseteq\mathcal{C}$ such that testing $\mathcal{C}_{\rm Hard}$ requires $q_{H}(n,\varepsilon)$ samples.

Suppose further that $q_{L}(n,\varepsilon,1/10)={o\left(q_{H}(n,\varepsilon)\right)}$. Then, any tester for $\mathcal{C}$ must use ${\Omega\left(q_{H}(n,\varepsilon)\right)}$ samples.

The above theorem relies on the reduction outlined above, which we rigorously detail here. Assuming $\mathcal{C}$, $\mathcal{C}_{\rm Hard}$, $\mathcal{L}$ as above (with semi-agnostic constant $c\geq 1$), and a tester $\mathcal{T}$ for $\mathcal{C}$ with sample complexity $q_{T}(n,\varepsilon)$, we define a tester $\mathcal{T}_{\rm Hard}$ for $\mathcal{C}_{\rm Hard}$. On input $\varepsilon\in(0,1]$ and given sample access to a distribution $D$ on $[n]$, $\mathcal{T}_{\rm Hard}$ acts as follows:

call $\mathcal{T}$ with parameters $n$, $\frac{\varepsilon^{\prime}}{c}$ (where $\varepsilon^{\prime}\stackrel{{\scriptstyle\rm def}}{{=}}\frac{\varepsilon}{3}$) and failure probability $1/6$, to $\frac{\varepsilon^{\prime}}{c}$-test if $D\in\mathcal{C}$. If not, reject.

otherwise, agnostically learn a hypothesis $\hat{D}$ for $D$, with $\mathcal{L}$ called with parameters $n$, $\varepsilon^{\prime}$ and failure probability $1/6$;

check offline if $\hat{D}$ is $\varepsilon^{\prime}$-close to $\mathcal{C}_{\rm Hard}$, accept if and only if this is the case.

Observing that the overall sample complexity is $q_{T}(n,\frac{\varepsilon^{\prime}}{c})+q_{L}(n,\varepsilon^{\prime},\frac{1}{10})=q_{T}(n,\frac{\varepsilon^{\prime}}{c})+{o\left(q_{H}(n,\varepsilon^{\prime})\right)}$ concludes the proof. ∎

Finally, we derive a lower bound on testing $k$-SIIRVs from the agnostic learner of [DDO+13] (which has sample complexity $\operatorname*{poly}(k,1/\varepsilon)$ samples, independent of $n$): See 1.1

2 Tolerant Testing

This lower bound framework from the previous section carries to tolerant testing as well, resulting in this analogue to Theorem 6.1:

Let $\mathcal{C}$ be a class of distributions over $[n]$ for which the following holds:

there exists a semi-agnostic learner $\mathcal{L}$ for $\mathcal{C}$, with sample complexity $q_{L}(n,\varepsilon,\delta)$ and “agnostic constant” $c$;

there exists a subclass $\mathcal{C}_{\rm Hard}\subseteq\mathcal{C}$ such that tolerant testing $\mathcal{C}_{\rm Hard}$ requires $q_{H}(n,\varepsilon_{1},\varepsilon_{2})$ samples for some parameters $\varepsilon_{2}>(4c+1)\varepsilon_{1}$.

Suppose further that $q_{L}(n,\varepsilon_{2}-\varepsilon_{1},1/10)={o\left(q_{H}(n,\varepsilon_{1},\varepsilon_{2})\right)}$. Then, any tolerant tester for $\mathcal{C}$ must use ${\Omega\left(q_{H}(n,\varepsilon_{1},\varepsilon_{2})\right)}$ samples (for some explicit parameters $\varepsilon^{\prime}_{1},\varepsilon^{\prime}_{2}$).

The argument follows the same ideas as for Theorem 6.1, up to the details of the parameters. Assuming $\mathcal{C}$, $\mathcal{C}_{\rm Hard}$, $\mathcal{L}$ as above (with semi-agnostic constant $c\geq 1$), and a tolerant tester $\mathcal{T}$ for $\mathcal{C}$ with sample complexity $q(n,\varepsilon_{1},\varepsilon_{2})$, we define a tolerant tester $\mathcal{T}_{\rm Hard}$ for $\mathcal{C}_{\rm Hard}$. On input $0<\varepsilon_{1}<\varepsilon_{2}\leq 1$ with $\varepsilon_{2}>(4c+1)\varepsilon_{1}$, and given sample access to a distribution $D$ on $[n]$, $\mathcal{T}_{\rm Hard}$ acts as follows. After setting $\varepsilon^{\prime}_{1}\stackrel{{\scriptstyle\rm def}}{{=}}\frac{\varepsilon_{2}-\varepsilon_{1}}{4}$, $\varepsilon^{\prime}_{2}\stackrel{{\scriptstyle\rm def}}{{=}}\frac{\varepsilon_{2}-\varepsilon_{1}}{2}$, $\varepsilon^{\prime}\stackrel{{\scriptstyle\rm def}}{{=}}\frac{\varepsilon_{2}-\varepsilon_{1}}{16}$ and $\tau\stackrel{{\scriptstyle\rm def}}{{=}}\frac{6\varepsilon_{2}+10\varepsilon_{1}}{16}$,

otherwise, agnostically learn a hypothesis $\hat{D}$ for $D$, with $\mathcal{L}$ called with parameters $n$, $\varepsilon^{\prime}$ and failure probability $1/6$;

check offline if $\hat{D}$ is $\tau$-close to $\mathcal{C}_{\rm Hard}$, accept if and only if this is the case.

Observing that the overall sample complexity is $q_{T}(n,\frac{\varepsilon^{\prime}_{1}}{c},\frac{\varepsilon^{\prime}_{2}}{c})+q_{L}(n,\varepsilon^{\prime},\frac{1}{10})=q_{T}(n,\frac{\varepsilon^{\prime}}{c})+{o\left(q_{H}(n,\varepsilon^{\prime})\right)}$ concludes the proof. ∎

There exists an absolute constant $\varepsilon_{0}>0$ such that the following holds. Any algorithm which, given sampling access to an unknown distribution $D$ on $\Omega$ and parameter $\varepsilon\in(0,\varepsilon_{0})$, distinguishes with probability at least $2/3$ between (i) ${\lVert D-\operatorname{Bin}\!\left(n,1/2\right){\rVert}}_{1}\leq\varepsilon$ and (ii) ${\lVert D-\operatorname{Bin}\!\left(n,1/2\right){\rVert}}_{1}\geq 100\varepsilon$ must use ${\Omega\left(\frac{1}{\varepsilon}\frac{\sqrt{n}}{\log n}\right)}$ samples.

The proof relies on a reduction from tolerant testing of uniformity, drawing on a result of Valiant and Valiant [VV10]; for the sake of conciseness, the details are deferred to Appendix D. With Theorem 6.3 in hand, we can apply Theorem 6.2 to obtain the desired lower bound: See 1.1

We observe that both Section 1.1 and Section 1.1 are tight (with regard to the dependence on $n$), as proven in the next section (Section 7).

A Generic Tolerant Testing Upper Bound

To conclude this work, we address the question of tolerant testing of distribution classes. In the same spirit as before, we focus on describing a generic approach to obtain such bounds, in a clean conceptual manner. The most general statement of the result we prove in this section is stated below, which we then instantiate to match the lower bounds from Section 6.2:

Let $\mathcal{C}$ be a class of distributions over $[n]$ for which the following holds:

there exists a semi-agnostic learner $\mathcal{L}$ for $\mathcal{C}$, with sample complexity $q_{L}(n,\varepsilon,\delta)$ and “agnostic constant” $c$;

for any $\eta\in$, every distribution in $\mathcal{C}$ has $\eta$-effective support of size at most $M(n,\eta)$.

Applying now the theorem with $M(n,\varepsilon)=\sqrt{n\log(1/\varepsilon)}$ (as per Section 5.2), we obtain an improved upper bound for Binomial and Poisson Binomial distributions: See 1.1

Somewhat similar to the lower bound framework developed in Section 6, the gist of the approach is to reduce the problem of tolerant testing membership of $D$ to the class $\mathcal{C}$ to that of tolerant testing identity to a known distribution – namely, the distribution $\hat{D}$ obtained after trying to agnostically learn $D$. Intuitively, an agnostic learner for $\mathcal{C}$ should result in a good enough hypothesis $\hat{D}$ (i.e., $\hat{D}$ close enough to both $D$ and $\mathcal{C}$) when $D$ is $\varepsilon_{1}$-close to $\mathcal{C}$; but output a $\hat{D}$ that is significantly far from either $D$ or $\mathcal{C}$ when $D$ is $\varepsilon_{2}$-far from $\mathcal{C}$ – sufficiently for us to be able to tell. Besides the many technical details one has to control for the parameters to work out, one key element is the use of a tolerant testing algorithm for closeness of two distributions due to [VV11b], whose (tight) sample complexity scales as $n/\log n$ for a domain of size $n$. In order to get the right dependence on the effective support (required in particular for Section 1.1), we have to perform a first test to identify the effective support of the distribution and check its size, in order to only call this tolerant closeness testing algorithm on this much smaller subset. (This additional preprocessing step itself has to be carefully done, and comes at the price of a slightly worse constant $C=C(c,\kappa)$ in the statement of the theorem.)

1 Proof of Theorem 7.1

As described in the preceding section, the algorithm will rely on the ability to perform tolerant testing of equivalence between two unknown distributions (over some known domain of size $m$). This is ensured by an algorithm of Valiant and Valiant, restated below:

There exists an algorithm $\mathcal{E}$ which, given sampling access to two unknown distributions $D_{1},D_{2}$ over $[m]$, satisfies the following. On input $\varepsilon\in(0,1]$, it takes $O(\frac{1}{\varepsilon^{2}}\frac{m}{\log m})$ samples from $D_{1}$ and $D_{2}$, and outputs a value $\Delta$ such that $\lvert{\lVert D_{1}-D_{2}{\rVert}}_{1}-\Delta\rvert\leq\varepsilon$ with probability $1-1/\operatorname*{poly}(m)$. (Furthermore, $\mathcal{E}$ runs in time $\operatorname*{poly}(m)$.)

For the proof, we will also need this fact, similar to Section 5, which relates the distance of two distributions to that of their conditional distributions on a subset of the domain:

Let $D$ and $P$ be distributions over $[n]$, and $I\subseteq[n]$ an interval such that $D(I)\geq 1-\alpha$ and $P(I)\geq 1-\beta$. Then,

${\lVert D_{I}-P_{I}{\rVert}}_{1}\leq\frac{3}{2}\frac{{\lVert D-P{\rVert}}_{1}}{D(I)}\leq 3{\lVert D-P{\rVert}}_{1}$ (the last inequality for $\alpha\leq\frac{1}{2}$); and

${\lVert D_{I}-P_{I}{\rVert}}_{1}\geq\frac{}{}{\lVert D-P{\rVert}}_{1}-2(\alpha+\beta)$.

where we used the fact that $\left\lvert P(I)-D(I)\right\rvert\leq{\operatorname{d_{\rm TV}}\!\left({D,P}\right)}=\frac{1}{2}{\lVert D-P{\rVert}}_{1}$. Turning now to the second item, we have:

With these two ingredients, we are in position to establish our theorem:

The algorithm proceeds as follows, where we set $\varepsilon\stackrel{{\scriptstyle\rm def}}{{=}}\frac{\varepsilon_{2}-\varepsilon_{1}}{17\kappa}$, $\theta\stackrel{{\scriptstyle\rm def}}{{=}}\varepsilon_{2}-((6+c)\varepsilon_{1}+11\varepsilon)$, and $\tau\stackrel{{\scriptstyle\rm def}}{{=}}2\frac{(3+c)\varepsilon_{1}+5\varepsilon}{2}$:

invoke $\mathcal{L}$ on $D$ with parameters $\varepsilon$ and failure probability $\frac{1}{10}$, to obtain a hypothesis $\hat{D}$;

call $\mathcal{E}$ (from Theorem 7.2) on $D_{I}$, $\hat{D}_{I}$ with parameter $\frac{\varepsilon}{6}$ to get an estimate $\hat{\Delta}$ of ${\lVert D_{I}-\hat{D}_{I}{\rVert}}_{1}$;

output REJECT is $\Delta+\hat{\Delta}>\theta$, and output ACCEPT otherwise.

The claimed sample complexity is immediate from Steps 2 and 3, along with Theorem 7.2. Turning to correctness, we condition on both subroutines meeting their guarantee (i.e., ${\lVert D-\hat{D}{\rVert}}_{1}\leq c\cdot{\textsc{opt}}+\varepsilon$ and ${\lVert D-\hat{D}{\rVert}}_{1}\in[\hat{\Delta}-\varepsilon,\hat{\Delta}+\varepsilon]$), which happens with probability at least $8/10-1/\operatorname*{poly}(n)\geq 3/4$ by a union bound.

and the algorithm does not reject in Step 4. To conclude, one has by 7.3 that

Finally, the testing algorithm defined above is computationally efficient as long as both the learning algorithm (Step 2) and the estimation procedure (Step 5) are.

References

Appendix A Proof of Section 2.2

We now give the proof of Section 2.2, restated below: See 2.2

To do so, we first describe an algorithm that distinguishes between ${\lVert D-\mathcal{U}{\rVert}}_{2}^{2}\geq\varepsilon^{2}/{n}$ and ${\lVert D-\mathcal{U}{\rVert}}_{2}^{2}<\varepsilon^{2}/(2n)$ with probability at least $2/3$, using $C\cdot\frac{\sqrt{n}}{\varepsilon^{2}}$ samples. Boosting the success probability to $1-\delta$ at the price of a multiplicative $\log\frac{1}{\delta}$ factor can then be achieved by standard techniques.