Nearly-Tight Bounds for Testing Histogram Distributions
Authors: Clement Louis Canonne
Ilias Diakonikolas
Daniel Kane
Sihan Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: distribution testing
histograms
binning
probability distributions
lower bounds
sub-linear algorithms

Abstract: We investigate the problem of testing whether a discrete probability distribution over an ordered domain  is a histogram on a specified number of bins. One of the most common tools for the succinct approximation of data, $k$-histograms over $[n]$, are probability distributions that are piecewise constant over a set of $k$ intervals. Given samples from an unknown distribution $\mathbf p$ on $[n]$, we want to distinguish between the cases that $\mathbf p$ is a $k$-histogram versus far from any $k$-histogram, in total variation distance. Our main result is a sample near-optimal and computationally efficient algorithm for this testing problem, and a nearly-matching (within logarithmic factors) sample complexity lower bound, showing that the testing problem has sample complexity $\widetilde \Theta (\sqrt{nk} / \epsilon + k / \epsilon^2 + \sqrt{n} / \epsilon^2)$.

Near-Optimal Bounds for Testing Histogram Distributions
Clément L. Canonne University of Sydney
Ilias Diakonikolas" University of Aisconsin-Maddise ilias@cs wisc. edu
clement. canonne@sydney edu.auuu au
Daniel M. Kane
Sihan Liu University California, San Diego si1046@ucsd.edd edu
University of California, San Diego dakane@es. ucsd.edu
Abstract
We investigate the problem of testing whether a discrete probability distribution over ordered domain is a histogram the most common tools for the succinct approximation of data, k-histograms over [n]] are probability distributions that piecewise constant over set of & intervals. Given samples from an unknown distribution p on [n]. we want distinguish between the cases that p is k-histogram versus far from any k- histogram, in total variation distance. Our main result a sample near-optimal and computationally efficient algorithm for this testing problem, and nearly-mate mathhin (within logarithmic factors) sample complexity lower bound.
specified number of bins. One of
1 Introduction
1.1 Background and Motivation
classical approach for the efficient exploration of massive datasets involves the construction of succinet data representations, see, e.g., the survey (CGHJ12). One of the most useful and commonly used compact representations are histograms. For dataset S, whose elements
from the universe [n] = [I....,,) J2., a k k-histogram is a function that is piecewise constant over & interval pieces. Histograms constitute the oldest and most popular synopsis structure in databases and have been extensively studied in the database community since their introduction in the 1980s [Koo80), see, e.g.. [GMP97 M CMN98 TGIK02 +GI+02 GKS06 ILR12 ADH+15 Can16), for partial list of references. In both the statistics and computer science literatures, several methods have been proposed to estimate histogram distributions a range of natural settings [Sco79 FD8T DL04
LN96 Kle09 CDSS14) ADH ADLSI7 DLSI8)
In this work, study the algorithmic task of deciding whether (potentially very large) dataset S over the domain [ni] is k-histogram (i.e., it has succinct histogram representation with & interval pieces) "far" from any k-histogram representation (in a well-defined technical sense). Our focus is on sublinear time algorithms [Rub06]. Instead of reading the entire dataset S, which could be highly impractical, one can instead use randomness sample a small subset of the dataset. Note that
'Supported by NSF Medium Award CCF-2107079, NSF Award CCF-1652862 (CAREER), Sloan Research Fellowship, and DARPA Learning with Less Labels (LwLL) grant. Some of this work was performed while the author was visiting the Simons Institute for the Theory of Computing.
Supported by NSF Medium Award CCF-2107547, NSF Award CCF-1553288 (CAREER), and Sloan Research Fellowship.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

sampling (uniformly) random element from S is equivalent to drawing sample from the underlying probability distribution p of relative empirical frequencies. This observation brings our algorithmic problem of "histogram testing" in the framework of distribution property testing (statistical hypothesis BFR + 131, see, e.g., [Can20) for a survey.
testing) BFR 000
Formally, we study the following task: for an integer 1 S k S n, denote by H2g the set of k-histogram distributions over {1, 2,............ ................................ n). i.e., the set of all distributions p such that there exists partition of [nx] into k consecutive intervals (not necessarily of the same size) with p being uniform on each interval. Given access i.i.d. samples from an unknown distribution p on [n] and a desired error tolerance 0 < E < 1, we want to correctly distinguish (with high probability) between the cases that P a k- k-histogram versus E-far from any k-histogram, in total variation distance (or, equivalently, (nnorm). It should be noted that the histogram testing problem studied here is not new. Prior work within the algorithms and database theory community has investigated the complexity of the problem in the past ten years (see, e.g., [LR12, ADH 15 Can and Section 1.4 for detailed summary of prior work). However, known algorithms for this task are sub-optimal, and in particular there is a polynomial gap between the best known upper and lower bounds on the sample complexity of the problem. At high level, the difficulty of our histogram testing problem in the sub-linear regime lies in the fact that the location and "length" of the k intervals defining the histogram representation (if one exists) is a priori unknown to the algorithm.
We believe that the histogram testing problem is natural and interesting in its own right. Moreover, a sample-efficient algorithm for this testing task can be used as a key primitive in the context of model selection, where the goal is to identify the "most succinet" data representation. Indeed, various algorithms are known for learning k-histograms from samples whose sample complexities (and running times) scale proportionally to the succinctness parameter & (and are completely independent of the domain size n)) [CDSS14 ADH 15 [DLSII7. Combined with an efficient tester for the property of being k-histogram (used to identify the smallest possible value of k such that p is a k-histogram, e.g., via binary search), one can obtain a sketch of the underlying dataset. See Appendix C for a detailed description.
1.2
Our Results
Our main contribution is a near-characterrizaionn of the sample complexity of the histogram testing problem. Specifically, we provide (1) a sample near-optimal and computationally efficient testing algorithm for the problem, and (2) a nearly-matching sample complexity lower bound (within logarithmic factors). In particular, we establish the following theorem:
Theorem 1 (Main Result). There exists a testing algorithm for the class of k-histograms on [m] with k/=2 k//2 + vn/=²) and running time poly(m). Moreover, for any E [n] and 0 < E < 1, any testing algorithm for the class of k-histograms on [n] requires at least Õ ((Vnk/s+ + k/E² + vn/=²) samples.
sample complexity m Ö(Vnk/E
(The Ō(-) and f2()) notation hides polylogarithmic factors in the argument.) Theorem 1 characterizes the complexity of the histogram testing problem within polylogarithmic factors. Note that there are three terms in the sample complexity; namely, Vnk/s, k/s", and vn/e². The sample complexity of the problem is dominated by one of these three different terms, depending the relative sizes of n, ls and 1/e. An illustration is given in Figure [
Prior to our work, the best previous histogram testing algorithm had sample complexity Ö(Vkn/e²) (CDGRI8), while the best known lower bound was M(vn/s² + k/s) 6
We note that previous upper and lower bounds exhibit a polynomial gap. even for constant values of & or k. For example, in the "large-k" regime where k = n²" for some constant 0 < c < 1, there was a gap between Onn and 122 in the sample complexity. In this regime, however, Theorem 1 results in the near-optimal bound of (nn-/2+e/2). Similarly, in the "high-accuracy" regime where = 1/n for some constant e > 0 (and, say, constant k), previous bounds only established that the sample complexity lies between 3/+333))) and 1/24222 while our result
3 As discussed in Section 1.4 while an upper bound of L0( T/ + k/E") is claimed in [Can16], the analysis of their algorithm is flawed: and, indeed, our work shows that the sample complexity bound stated in [an16 cannot hold, as it would contradict our lower bound.
2

---

1.5
kal 1.0 1o
Scrt[n]/e
k/e"
Sqrt[nkUee
0.5
0.0
0.0
0.2
0.6
0.8
1.0
Figure The æ-axis, y-axis are log(k) log(n) and log(1/s)/ log(n) respectively, Each point the graph corresponds to setting of n, k, and colored based on the corresponding dominating term.
shows the (nearly-tight) bound (nn1/2+e). These are only two specific examples: more generally, the previously known bounds are suboptimal by polynomial factors 1/s when E 2 / ///n; and by polynomial factors in all parameters k, n, 1/s when e S Vk/n. Theorem settles the sample complexity of the problem, up logarithmic factors, for every parameter setting.
At a technical level, our sample complexity lower bound construction conceptually differs from previ- work in distribution testing, drawing instead from sophisticated techniques from the distribution estimation literature. Our upper bound follows from the "Testing-vie via-Learning" framework proposed in [AK11)). The main technical innovation is sample- and time- efficient adaptive algorithm which can simultaneously learn an unknown histogram with unknown interval structure distribution and identify domain where the learned result is accurate. We elaborate these aspects next.
1.3 Overview of Techniques
Sample Complexity Lower Bound. We follow the typical high-level approach in proving sample complexity lower bound. Namely, we define two ensembles of distributions DYES and DNO such that, with high probability, the following conditions are satisfied: (1) random distribution from DYES is a h--hisogram, (2) a random distribution from Dxo is E-far from any k-histogram, and (3) given sample of appropriate size, is information theoretically impossible to distinguish random distribution drawn from DYES from random distribution drawn from DNO.
information-theorrttiallll
We start by describing our hard instances for the case that the accuracy parameter is a small universal constant. On the one hand we define DyES so that all p, are the same except for "small" number of domain elements i.c. k for small constant E (0, 1). On the other hand, for distribution drawn from Dso. p, will be randomly 0 or roughly 2/n, except for at most constant fraction the elements. It is not hard see that, with high probability, distribution drawn from Dyes (resp. DNO) will be a k k-histogram (resp. far from being a k-histogram).
To ensure that the underlying distributions are indistinguishable using small sample size, we want to guarantee that, for small values the number elements with exactly samples will roughly the same for DYES and DNO. this rules out any test statistic relying on counting the number of I-way collisions among the sample. Following (allT VVI3 equivalent showing that distributions drawn from DyeS and DNO match their low-degree moments.
WY16 this is essentially

---

In particular, for a random pair of distributions P. p' drawn from DYES and DNo respectively, we want that Σ, P and E': are roughly the same for all small values t. We note that the non-exceptional elements of a distribution p' drawn from DNO - which have probability mass either 0 or roughly 2/n will have second moment larger than the non-exceptional elements of distribution p drawn from DYES - which have probability mass roughly 1/n - by approximately 1/n.. To counteract this discrepancy. the (fewer than k) exceptional elements in DYES must have average mass at least 1/ /kn. Fortunately, using techniques from [VV13 WY+ 19), are able to construct distributions that match t - ( n) moments in which no individual bin has mass more than ((1//kn) Combining this construction with basic information -teeooiiionthheorttiic arguments gives us an Q v V/n) sample complexity lower bound. We note that this lower bound is tight in the sense that with more than MZ V (D(v)) samples one can reliably identify the exceptional elements, as they will each have relatively large numbers of samples with high probability, allowing us to distinguish DYES from DNo simply based on the uub-distributions over these elements.
Given the aforementioned construction (for constant E), it is easy to obtain a sample lower bound of S2( kt//// by mixing our hard instances with the uniform distribution (with mixing weights and 1 E respectively). In fact, even if the testing algorithm knows in advance which samples come from the uniform part and which samples come from the original hard instance, distinguishing would require ??( /kn) samples from the original hard instance, and therefore Ωi / (ki//)) samples overall. This sample size lower bound turns out to be tight for E relatively large, as one can still reliably identify the exceptional bins with only D(Vkn// samples. However, when & becomes sufficiently small, identifying the exceptional bins becomes more challenging. Indeed, if we take m samples, we expect that an exceptional bin has roughly me/ Vkn more samples than a non-exceptional bin. On the other hand, a non-exceptional bin will have roughly Poi(m/n) samples with standard deviation /m/n. When m/n >> me/V (which happens in the regime & < Vk/n), in order for the exceptional bins to be distinguishable, we would need that me/ /Kn >>>>> Vmn/n m > k/e² many samples. Using a careful information-theoreiic argument, we formalize this intuition to show that ((k/e2) is indeed sample lower bound in this regime.
Sample-Efticient Tester. The starting point of our efficient tester the Testing-vid-LLarniig approach of [ADK15]. Very roughly speaking, we first design a learning procedure which outputs distribution P that would be close to p in x² divergence, assuming that p was in fact k-histogram. Then we use a x²111 tolerant tester, in the spirit of the one introduced in [ADK15], to distinguish between the cases that p is close to p in x² divergence versus far from p fi-distance. This step is however significantly harder than this simple outline suggests, as it turns out challenging to perform the first step exactly. Instead, we design a specific learning algorithm with an implicit "hybrid" learning guarantee, (see Lemma which in turns requires us to considerably generalize and adapt the "tolerant testing part" to avoid spurious discrepancies (introduced in the imperfect learning stage) which may lead to false negatives.
To implement the first step, we follow the general "learn-and-sieve" idea suggested in [Can16), with important modifications to address the flaw in their approach and its analysis. In particular, suppose that p is a k-histogram. Then, if we knew the corresponding k intervals (that make up the partition for the k- k-histogram), it suffices to learn the mass of p on each interval, and let p be uniform on each interval (with the appropriate total mass). Of course, a key source of difficulty arises from the fact that we do not know the partition a priori. To circumvent this issue, we divide [rr] into (roughly) K = =kk) intervals and try to detect p is far in x" divergence from being uniform on any of these intervals. If an interval from our partition incurs large x² error (we call such an interval bad), we know that p must not be constant within this interval. Therefore, we proceed to subdivide these bad intervals into roughly equal parts, and recurse on the ((k) intervals in our new partition. Assuming P is a 6-histogram, we subdivide at most intervals in each iteration, since there could at most k intervals from any interval partition of [v] where p is not constant. Hence, in each iteration, we decrease the mass of the bad intervals by at least constant factor. We repeat the process for at most (log((/))) many iterations; after this many iterations, the total mass of the bad intervals will become OEE), and thus they may be safely ignored.
A significant difference between our method and the approach from [Can16] lies in the method of sieving. In [Can16) was only said that the algorithm would filter out a subset of breakpoint intervals based on the x2 statistics ([ADKT5) with the goal of reducing discrepancy; this is where

---

the main gap in their analysis lies, and the particular (flawed) approach they suggested does not seem to be fixable [[an2]]. On the contrary, we characterize the exact set of intervals that need (and can) be removed with the formal definition of bad intervals with respect to given partition I of [n] (See Definition (). Based on that, our approach to search for any sub-intervals J (not necessarily an interval in Z) on which the x² divergence between p and p. an approximation of p assuming is uniform over intervals within the given partition, is more than (2(=?) /k). For an interval I from the partition Z. we show the inclusion of such "bad sub-interval" J C I then certifies the "badness" of itself. To find such J, we need technique for accurately approximating p(J) simultaneously for all intervals J S [n]. in both absolute and relative error; a notion of approximation much stronger that what classical tools from statistical learning theory such as the VC inequality or the Dvoretzky- Kiefer-Wolfowiz (DKW) inequality provide. Notice that, for a fixed interval J C [n], taking the
empirical distribution over b samples gives an estimate q of p such that qq)) - p(J) < /D(J)/b with constant probability. By taking (log(n)) batches of samples (each containing b i.i.d. samples from p), and computing the median value of all of the q(J)ss 's. with high probability for each J. we then obtain an estimate (JJ) for which the above condition holds. Using the sub-routine, as long as b is at least $2(k/e²) we can ensure that (+( p( /JJ) < & and we can then safely use our estimate (J) as a proxy for pJ) for the detection of those "bad sub-intervals" for which [p(J) - (J) 2 /J) suffices unless p(J) is substantially larger than our estimate p(J).
is large, which in turns certify the bad intervals from given partition. This
Unfortunately, this bad case where p(J) > pJJ) can happen if p(J) is smaller than 1/b. In such a case, collection of b samples from p. we are likely to see no samples in J. and thus our empirical estimate (J) will be O. We can fix this issue (i.e., the case where (JJ is actually 0) by mixing both P and P with the uniform distribution, thus allowing us to assume that p(J) 2 |Jl/2m 2 1/ 12m). Yet, this still leaves a potential gap of roughly n/b between the ratio of p(J) and p(J). Fortunately, if we select b >> Vnnk/E, for losing a factor of b/n, we will still have that [+(]) - p(J) < e²/k. This implies that
will have that (}] [(J])/pp[] < nk, and even accounting
we will successfully detect any bad intervals and achieve our learning guarantees.
1.4 Prior Work
Motivated by the question of building provably good succinet representations of a dataset from only a small sub-sample of the data, [2 first introduced histogram testing as preliminary, ultra-efficient decision subroutine to find the best parameter k for the number of bins. They provided an algorithm for this task which required Ö(Vkn/e²) samples from the dataset, a sample complexity which beats the naïve approach (reading and processing the whole dataset) for small values of k and relatively large values of the accuracy parameter E. Subsequent work [CDGRTE] reduced the dependence on from quintic to cubic, giving an algorithm with sample complexity Ö Ö(Vkn//=)) This bound was, however, still quite far from the "trivial" lower bound of Ω2 ((vn/e²), which follows from reduction to uniformity testing (i.e., the case A = 1) [Pan08].
Prior to the current work, an Ö(Vn/E² + k/ee)) upper bound and an ( + k/c) lower bound were obtained [Can While the lower bound is theoretically sound (albeit, as it turns out, suboptimal), as pointed out in [Can22], the upper bound does not hold due to a technical flaw in the analysis, leaving the optimal sample complexity of the problem open for even constant E. Moreover, the lower bound of [Can based on a reduction of histogram testing to the well-studied problem of support size estimation, provably cannot be improved to provide either (i) a quadratic dependence on e, i.e., (2(k/E²2 or (ii) coupling between the two domain parameters k; n, i.e., 2 (((vkk/e). Our work remedies all those issues, fully resolving the question of histogram testing, for the whole parameter range, with logarithmic factors.
Finally, we note that number of works have obtained algorithms and lower bounds for related, yet significantly different, testing problems. Specifically, (DK16) gave a sample-optimal testing algorithm for the special case of our problem where the A intervals are known a priori. Moreover, number of works [DKN15b] DKN15a DKN17] have obtained identity and equivalence testers under the assumption that the input distributions are k-histograms.
'Notice that & is neither a distribution measure. but just a map from intervals to positive real values.
5

---

Preliminaries. We denote by TV q) the total variation (TV) distance between probability dis- tributions P.q over [n]] == {1. 2, ........,j,.. n). defined as (V q) == supsgim (P(S) q()) 2 Dh ((()) - q()), where p(S) = Eies p(i). We will make essential use of the x² -ivierggee p with respect to q. defined as dx= (p = -i= (p. -q)) /q.- We will also require gener- alizations of these definitions on restrictions of the domain. In particular, given S S [n], we use the notation TV (P. q) == (1/2) Ip(i) - q(i) and de (p]lq) == Eies (P. -.)² /u- We note that for any S - [n], it holds that TV (p. q)² = 1 (p/1q).
The asymptotic notation Ô (resp. ? suppresses logarithmic factors in its argument, i.c., (((())) = (n) log" f(n)) and (n((())) = (m)) /lg" f(n)), where e > 0 is a universal constant. The notations < and > intuitively mean "much less than" and "much greater than" respectively. Formally, we write (n) < g(n) to denote that (() < c. (T1),, for some universal constant 0 << c.
2 An efficient testing algorithm
preliminary simplification. Without loss of generality, we will assume that p(1) 2 2x for every i [n). Indeed, this can be ensured by mixing the unknown distribution with the uniform distribution u, on [n]] beforehand i.e. p' = 1/2 (p- + u,)) (See Fact in Appendix for how to sample from p' efficiently). It is easy to see that p' remains histogram after mixing: p' E HE if p E Hg. and p' at least (e/2)-far away from every histogram if p is e-far from every histogram.
Testing via Learning. The main approach is follow the Testing-via-Leariinn in [ADK15]. In particular, suppose we have learning algorithm capable of constructing P that is close to p in x2 divergence when p E H Then, (1) if p Hg. we will have that p and p are close and (as a consequence of this) that P is close to being a k-histogram. Yet, (2) if p is far from being a k-histogram, then by the triangle inequality we must have either that p is far from being a k-histogram, or that p and p are far from each other in & distance. We can use dynamic programming to check the explicit description is indeed close to k-histogram in E distance efficiently (See Lemma 4.11 of (CDGR18) To verify p and P are close, we will use result of [ADK 15) on tolerant identity testing. In particular, given an explicit description p. the tester takes sample from the unknown distribution p and decides whether p and are closed in x² divergence or far in & distance. We remark that P can be relaxed to be positive measure.
framework proposed
Lemma 1 (Adapted from Lemmas 2 and 3 (ADKI5)) Ler p and be a distribution and a positive measure defined on [n] respectively. Fix e E 10 and let A = {i E [n] -p()) 2 e/(5mn))- There exists a tester Aalerance-Identity---ee
which takes Poi(m) for m = θ (VT/E") i.i.d. samples
from and outputs Accept if dz. (pllp) S =²/500 and Reject if TV (p.P) 2 E with constant probability.
Outline for Learning. If p E HP and we know the partition of p in advance, one can learn p up to s² in x2 divergence with (kk/s") samples (following the analysis of Laplace estimator from (KOPST5). ). Without the partition information, we can nonetheless achieve a weaker guarantee. That is, can output fully specified measure p on [n). together with sub-domain C [n]]. such that L (p
achieve the guarantee in three steps. (i) Divide the domain [n] into >>>> k many intervals obliviously (Lemma 2). (ii) Output a suceinct measure p that is constant on each interval specified by Step (i) (Section 2. (iii) Identify the intervals I where x
p) (pllp)
is small. In particular,
d' (p) () large (Section 2.2 Denote B [n]].G. The fact that we only have p and p close in x² divergence on a sub-domain G is a reasonable compromise as long as (BB), D(B) < e: if p is e-far away from P in l distance on [n)]. p least (e p(B) f away from P on [n]] Otherwise, we may take more samples from p restricted to B and sub-divide the problematic intervals identified in Step (iii) Repeating the above steps iteratively then brings us to the case p(B) < E.
Equitable Partition. The first step is to divide the domain into (kk) many intervals over which the masses of p are approximately equal. As shown in (DKI5)), this can be done with ((k) many
samples through routine we denote as Approx-Divide. We also need a routine for sub-dividing a set of disjoint intervals into even lighter sub-intervals. Nonetheless, one can reduce the sub-dividing
task to domain partitioning by running Approx-Diviee on the sub-distribution restricted to the set of disjoint intervals. Proofs are provided in Appendix A.1

---

Lemma 2. There exists an algorithm Approx-Sub-Divide that, given parameters & E (0, 1] and integer B L, as well as a set of disjoint intervals I = II,,I2.... L1gh, given sample access to p on (nl, outputs a list of partitions Si...., SS.. where S; is the partition of the interval I; E I, such that the following holds with probability at least 1 - 8. (i) The algorithm uses O (B/p(ZZ) log (B/8)
samples. (ii) The output contains al most (8B +q) intervals in total. (iii) Every non-singleton interval S S
Sg satisfies p(S) S p(I) 1./B.
2.1 Simultaneously Estimating Mass of Intervals
In this section, we first introduce Sieevvl--MassEEstinee a sub-routine that can accurately approxi- mate the mass of (J) for all intervals J S [n]] simultaneously and then show how we can use it to learn p (assuming p E H
Maarraa--Ms---sttmmaa first divides the number of samples drawn into (1)) batches. For an interval we compute the estimate (number of samples falling in / divided by the batch size) for each batch separately and compute the median over the statistics. This is often referred as the "Median Trick" and is crucial in achieving the learning guarantees with high probability. Pseudo-code and analysis are provided in Appendix A.2
Lemma 3. Let be d be supported on [n] such that p(i) 2 1/(2n). b Z+ and 5 E (0, 1]. The algorithm Haterval-Mass-Estmmaa
takes 3b log(n/5) i.i.d. samples from p and outputs G. a map from sub-intervals of [n] to real values, such that, with probability at least 8. every sub-interval
I S [n] it holds that p ((I) S max(2, /n)b), (I)) S 3 and (1) p()) S VD(l)/b.
Let I be a partition of [n]. We try to learn p pretending that p is constant over each interval within I In particular, the algorithm uses Interval-Masse -asraa--------immatt to
with the routine Empirical-Leerrmin obtain estimations of the mass of I E I and then flatten the mass uniformly among elements i T. Notice that, due to the application of the median trick, the output is not necessarily distribution but rather a positive measur 5 P on [m] which is constant over each interval within I.
If is indeed a k-histogram, errors are only incurred on a special type of intervals (of which there most k)) which we refer as the breakpoint intervals.
Definition 1 (Breakpoint Intervals). Given a k--histogram p on [n]. we say that i [n]] is breakpoint with respect to P if p(i) * p(i + 1): and that an interval C [ra] is a breakpoint interval (with respect to p) if I contains at least one breakpoint.
With Definition are provided in Appendix [A.3]
iin in mind, we specify the formal learning guarantees. Pseudo-code and proofs
Lemma 4. Suppose p E Hy. Let I a partition of [n] into K intervals. Let Z+,
8 (0, 1] and given (Tb) i..dd. samples from p.
T == 3 log K/0). There exists an algorithm Empirical-Learr
outputs a positive measure p. which satisfies the following with probability at least 1 - 8. (i) p is constant within each interval in I. (ïi) For every sub-intervals J C T where T E I is non bre-horak interval with respect to p. we have p(J)/((J) S max(22 8 n/bb) and [D(J) - p(J) S /pbJ)
By combining the two guarantees in Lemma one can see the x² divergence between p and p. restricted to the bre-breakpoint intervals, will be at most e² with high probability if taking O @(KT)=*) many samples. However, following result from [KOPST5] [an]6). one only need ((K/E²) samples to learn a K K-histogram up to e² error in this restricted notion of x2 divergence. One may wonder whether this is enough for us, and the stronger (but less natural) guarantees provided by Lemma 4 which end up increasing the number of samples required, are necessary. As we will see in the next section, we indeed need not only that the x² divergence small, but also that the ratio p(T)/p(I) is bounded for all non- brea-oenkoinn intervals. In particular, this latter property enables us to compute relatively accurate estimates of the x" divergence restricted to sub-intervals and (consequently) to tell whether is constant or from far from being constant on an interval.
2.2 Bad Interval Detection
While large contributions to the x² divergence (assuming the learning phase was successful) will only come from breakpoint intervals, not all of them will necessarily contribute significantly to the
'hat is, P might not sum to one, and thus is not itself' probability distribution.
7

---

x2 divergence. In particular, a breakpoint interval is only considered "bad" and needs to be filtered out if the error incurred proportional the number of breakpoints within.
Definition 2 (e-Bad-Interval), Fix a partition I of [n]] containing K intervals. Let I E I be breakpoint interval of p. Furthermore, suppose I contains j - breakpoints i.e. P is j-piece-wise uniform in I. We say I an e-bad interval with respect p and I if d'z (p|[D) 2j.E²/K.
The definition suits our purpose for two reasons. (i) The total x² error between p and p on the set of "good" intervals (complement of the set of "bad" intervals) is small. Indeed, let g E Z be a set containing no e-bad intervals. Since there are at most K intervals contained in G and k breakpoints contained in the intervals in g, it is easy see that dl (p|l)) I O(s²). (ii) One can reliably separate bad intervals from non-breakpoint intervals assuming the learning phase was successful. To see why, note that in that case every non-breakpoint interval satisfies dz (p|lp) < s²/K K for all J C T with high probability. On the contrary, for any bad interval 7, we claim there must be a sub-interval Q C I where &e (p|lp) 2 e²/ K and both and p are constant within. In particular, if I is E-bad interval that contains (j 1) breakpoints, we then have partition {Q1, 223 of over which is pise constant and at least one of them will have x² error at least e²/ 2/K.
Our next step is to show how we can leverage the separating condition to design an efficient bad interval detection mechanism. This is where our method significantly differs from [ann At a high
level, we take another set of independent samples to get an estimate (Q() of p(Q) for all Q [n]
simultancously. Then, we compare (Q)) with p(Q) to see whether we have de (pll N E" =//K, which would in turns imply the interval I 2 Q from the given partition is e-bad. We next provide the pseudo-code for Learn-And-Sieve, which finds a positive measure P on [n]] and domain B such that d |
(p p) < O(²²) provided p E Hp. Its detailed analysis can be found in Appendix A.4
Algorithm -Learn-And-Sieve
Require: Sample access to p; a partition I of [n] containing K intervals; accuracy E; failure probability 8.
1: Let m = C- (K/=² + VKn/E) log(n/0) for sufficiently large constant C.
2: Draw 2m i.i.d. samples from p and split the samples evenly into S,,
3: p < Empirical-Learning (S1. 5/4), e 6 Masaaa-Ma------ttee((( 6/4), B < ().
4: for all intervals Q S for some I do
5: if ((Q)/p(() > max(1, /n/K) K) or (Q()) (((0)~p(1))) P(Q) > 0.5/ then
6: Add 7 to B.
7: Output Reject if contains more than intervals. Otherwise, return B, p.
Lemma 5 (Sieving Lemma). Given a partition I containing K intervals, sample access to p on [n] and 8 E (0, 1). Then, the output of Learn-And-Siers (Algorithm(]) satisfies the following. (i) Suppose
E Hp. Then the algorithm returns a positive measure Po and B such that d (pllp) < s² with probability at least 1 1- 8. (ii) The output B contains at most k intervals (if the algorithm does not reject). (iii) At most O(KK/e2 + v VKn/e) log(n/0)) samples are used.
Proof Sketch. We claim that, if p HG. B contains all the e-bad intervals and non- breakpoint intervals with high probability. Let be a non-breakpoint interval. For b (mm/ (nn))) = 0(K/=2 + VKn/s), we have, with high probability, I((Q) - p(Q) < / /bb [p(Q)= p[Q) < vp(Q)/b and p(Q)/p(Q) S max(2,8 8 n/b) which follow from Lemmas and 4 Combining this with triangle inequality and our choice of b implies the sec- ond condition of Line 5 will be false. The first condition can be shown to be false by rewriting ((Q)/P(Q) as (()) p Q) p(Q)/p(Q): which are themselves bounded, with high probability, by 3 and ((1) m1x /1, n/ K) again by Lemmas 3 and and our choice of b.
Let I be a breakpoint interval. We then have (Q)) p(Q) Z vP(Q) =2/K for some sub-in intervall QCI. I. If p(Q) is light (p(Q)= < 25/ Kn). we can show P(Q)/b < 1/44)((Q) e² /K making ppQ),, our estimation for p(Q), sufficiently accurate such that the second condition of Line 5 will
be true. Otherwise, as > VKn/e, the estimation ((Q) will be within multiplicative factors of p()). If p(Q) is not much lighter than p(Q), again show p(Q)/6 < 1/4 p(Q) =²/K.
8

---

Otherwise, the first condition of Wiil be true. Conditioned on that B includes all e-bad intervals and no non-breakpoint intervals, it is easy to see that B will contain no more than it intervals and 2 (pllø) S O(=²). We note that points (i) and (iii) follow from the definition of the algorithm. D
Learn-and-Sieve (Algorithm D outputs a fully specified description p and a sub-domain g == [ such that de (pl[i) is small given p E HC, For testing purposes, this is a reasonable divergence from the ideal guarantee that dx (p)lp) is small as long as p(B) is also small. If so, we can set p(1) =0 0 for i E and invoke Tolerant- Srrraant-deettty-Teee with p and p. If the test passes, we then know that TV (p. S e/2: this together with p(B) S e/2 then gives TV (p. p) S.
Unfortunately, running Learn-and-Sieve only once we may have p( (2().. To handle this, we will need more fine-grained sieving procedure, which uses Approx-Sub-- Sub-DDvide to further partition the bad intervals detected and invokes Learn-and-Sieve iteratively. In each iteration, the total mass of the bad intervals shrinks by a constant factor, allowing us to reach p(B) < in most (log((1/E) iterations. The pseudo-code (Algorithm 4 and detailed analysis are provided in Appendix A.5
3 Histogram Lower Bound
In this section, we describe the hard instance of histogram testing, which leads to an Miv/n/+////e lower bound. We will apply the so-called Poissonization trick: we will relax P. the unknown object being tested, to be a positive measure with total mass (1). We denote such a measure as an approximate probability vector and give the corresponding notion of histogram.
Definition 3 (Approximate Probability Vector). We define the set of v-approximate probability vectors (APV) on the domain [mi] by (m)) [P : P. E (0) Vi E [n], -1| S v)- Accordingly, the set of histogram APV is given by Hg(v)) = (P (M)) P E Hgg.
Under the Poisson sampling model, given an unknown P PER (D))). the goal it to decide whether P E (V)()) or P is at least c(1 + v) faa from any P' E Hg in e, distance when given the vector {Mi, M2, ... } where M; ~ Poi(m P.). We denote the sample complexity of the problem by poi (n, k, E, v) and provide its formal definition in Appendix
To lower bound mhist (n, k, E,), we follow the idea of moment matching illustrated in Vall VV13
W In particular, one first constructs two discrete non-negative random variables U, U" whose first few moments are identical. Moreover, U and U' will be designed to have different properties such that one can use i.i.d. copies of U (and U/) to generate random measures that are histograms (and awr- from histograms respectively).
Our construction of such pair of random variables is based on Chebyshev's 's polynomials, a standard tool in approximation theory and the parameter estimation literature. The two variables will be vkn
supported on the roots of the polynomial p(x) = x (x - 1.) (x )) Ta (1 C-log" 27) where Ta(-) is the Chebyshev's polynomial (of the first kind) and C' is sufficiently large constant. More precisely, U will be supported on roots r where the derivatives pr(r) < 0, will will be on roots where pr(r) > and the probabilities will be proportional p' (r) accordingly. Consequently, U will most likely be 1/n (hence useful for histogram construction) and U" will most likely be 0 or 2/n, each with non-trivial probabilities (hence appropriate for histogram construction). Besides, they will have their maximums bounded by Ö(1/Vkn) kk), which is crucial to achieve the nearly optimal lower bounds. The detailed construction and analysis are provided in Appendix B.I
Lemma 6. Given positive integers k. where k < n, there exists a pair of non-negative random variable U, U" supported on [o, 1) and absolute constants c, d' > O satisfying (i) Pr [ + _ < R
(ū) Pr PU' 0] >> 1/3 and Pr [U" = 21 > 1/3. (ii)) U < é' log" n/ Vln. (iv) E[U] = E(U')=
(1 (1-00///n/n k/n)). (v) E E(U") for S t S c- c- n.
We the proceed to construct two families of Approximate Probability Vectors, one of which belongs
to Hy and the other far from it using the random variables stated in Lemma 6 To do
'The extra (1+b) factor is to accommodate the fact that P may not be distribution i.e. 1 [P]|] < (1+v).

---

[ADLS17] J. Acharya, I. Diakonikolas, J. Li, and L. Schmidt. Sample-optimal density estimation in nearly-linear time. In Proceedings of the Twenty-Eighh Eighht Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 1278-1288 2017. Full version available at define H = (1/n+aa + . + =U H' (1/n+ =U")) ( , =U((m) where U ( are i.i.d. copies of U, U" in Lemma
We address the two regimes Vk/n I e log" nt and Vk/n 2 s slog² n separately. In the former case, the heaviest element among H and H' are roughly 0(e/Vkn) Hence, when the algorithm takes o( Vkn/ss) samples, it rarely sees any element appearing large number of times. By the moment- matching property of U and U", the probabilities of seeing some elements appearing for times for I I log almost identical under H and H', therefore making H and H' indistinguishable. In the latter case, we have sU < A. implying that no elements in the measures are significantly heavier than the rest. As a result, H and H!' are both almost uniform except with a different number of "bumps" (elements that are slightly heavier). Subsequently, the algorithm needs more samples (about ((k/s²)) to tell whether certain element is heavier than the rest, leading phase transition in the sample complexity of the problem. We remark that whether (?k//²?) or ((Vnk/e) dominates depends exactly on the relationship between / /k/ri and e (omitting poly-logarithmic factors). Combining the two regimes then gives the following lower bound, whose proof is provided in Appendix [.2 Proposition 2. There exists constant v E (0,1) such that for any sufficiently large and & E (0, 1/10), it holds m min (n, k, v) 2 (mma((Vkm//) logn), k/(c" log" n))).
Finally, we can easily translate our lower bound result in the Poissonized sampling model to the Multinomial (standard fixed-size) sampling model by a standard reduction. Combining it with the known O n bound (see [Can16] Proposition 4) then concludes our lower bound argument.
Formal proofs are given in Appendix B.3
References
[ADH+15] Acharya, Diakonikolas, C. Hegde, J. Li, and L. Schmidt. Fast and near-optimal algorithms for approximating distributions by histograms. In Tova Milo and Diego Calvanese, editors, Proceedings of the 34th ACM Symposium on Principles of Database ACM, 2015.
Systems, PODS 2015, pages
[ADKI5] J. Acharya, C. Daskalakis, and G. Kamath. Optimal testing for properties of distribu- tions. In NeurlPS, pages 3591-3599, 2015.
http://aarii.orggaa////.......
[BFR T. Batu, L. Fortnow, R. Rubinfeld, W.D. Smith, and P. White. Testing that distributions are close. In IEEE Symposium on Foundations of Computer Science, pages 259-269, 2000.
[BRR 13] T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing closeness of discrete distributions. J. ACM, 60(1):4, 2013.
[Can] C. L. Canonne. A short note on poisson tail bounds.
[Can16] C. L. Canonne. Are few bins enough: Testing histogram distributions. Proceedings Symposium on Principles of Database
of the 35th ACM Systems, PODS '16, page 455 463, New York, NY, USA, 2016. Association for Computing Machinery.
[Can20] C. L. Canonne. A Survey Distribution Testing: Your Data is Big, But is it Blue? Number 9 Graduate Surveys. Theory of Computing Library, 2020.
[Can22] C. L. Canonne, 2022. Personal communication. Corrigendum for [Can16) sent to the conference.
[CDGR18] C. L. Canonne, I. Diakonikolas, T. Gouleakis, and R. Rubinfeld. Testing shape restrictions of discrete distributions. Theory Comput. Syst. 62(1):4-62. 2018. Invited issue for STACS' 16.
10

---

[CDSS14] S. Chan, I. Diakonikolas, R. Servedio, and X. Sun. Near-optimal density estimation in near-linear time using variable-width histograms. NIPS, pages 1844-1852, 2014.
[CGHJ12] G. Cormode, M. Garofalakis, P. J. Haas, and C. Jermaine. Synopses for massive data: Samples, histograms, wavelets, sketches. Found. Trends databases, 4:1-294, 2012.
[CMN98] S. Chaudhuri, R. Motwani, and V. R. Narasayya. Random sampling for histogram construction: How much enough? In SIGMOD Conference, pages 436-447, 1998.
[DK16] I. Diakonikolas and D. M. Kane. A new approach for testing properties of discrete distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685-694 IEEE, 2016.
[DKN15a] Diakonikolas, D. M. Kane, and V. Nikishkin. Optimal algorithms and lower bounds for testing closeness of structured distributions. In IEEE 56th Annual Symposium Foundations of Computer Science, FOCS 2015, pages 1183-1202, 2015.
[DKN15b] Diakonikolas, M. Kane, and Nikishkin. Testing identity structured distribu- tions. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pages -184,, 2015.
[DKN17] I. Diakonikolas, D. M. Kane, and V. Nikishkin. Near-optimal closeness testing of discrete histogram distributions. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pages 8:1-8:18 2017.
[DL04] L. Devroye and G. Lugosi. Bin width selection in multivariate histograms by the combinatorial method. Test, 13(1):129-145, 2004.
[DLS18] Diakonikolas, J. Li, and L. Schmidt. Fast and sample near-optimal algorithms for learning multidimensional histograms. In Conference On Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 819-842. PMLR, 2018.
[FD81] D. Freedman and P. Diaconis. On the histogram as density estimator:12 theory. Zeitschrifi für Wahrscheinnichheissheerr und Verwandte Gebiete, 57(4)4453-476 1981.
02] A. C. Gilbert, Guha, Indyk, Y. Kotidis, Muthukrishnan, and M. Strauss. Fast, small-space algorithms for approximate histogram maintenance. In STOC, pages 389-398, 2002.
[GKS06] S. Guha, N. Koudas, and K. Shim. Approximation and streaming algorithms for histogram construction problems. ACM Trans. Database Syst, 31(1):996-338 2006.
[GMP97] P. B. Gibbons, Y. Matias, and V. Poosala. Fast incremental maintenance of approximate histograms. In VLDB, pages 466-475, 1997.
[Han19] Y. Han. Mixture mixture and moment matching, 2019.
[ILR12] P. Indyk, R. Levi, and R. Rubinfeld. Approximating and Testing k-Histogram Distribu- tions in Sub-linear Time. In PODS, pages 15-22, 2012.
[JKM+98] H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In VLDB, pages 275-286, 1998.
[VYHW15] J. Jiao, K. Venkat, Yanjun Y. Han, and T. Weissman. Minimax estimation of functionals of discrete distributions. IEEE Trans. Inform. Theory, 61(5):2835-22 2015.
[Kle09] J. Klemela. Multivariate histograms with data-dependent partitions. Statistica Sinica, 19(1):199-176, 2009.
[Ko080] R. P. Kooi. The Optimization of Queries in Relational Databases. PhD thesis, 1980.
11

---

[KOPS15] S. Kamath, A. Orlitsky, D. Pichapati, and A. T. Suresh. On learning distributions from their samples. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1066-1100, Paris, France, 03-06 Jul 2015. PMLR.
[LN96] G. Lugosi and A. Nobel. Consistency of data-driven histogram methods for density estimation and classification. Ann. Statist., 24(2):687-706, 04 1996.
[Pan08] L. Paninski. A coincidence- test for uniformity given very sparsely sampled discrete data. IEEE Transactions Information 7 54(10):4750--77) -7555 2008.
[Rub06] R. Rubinfeld. Sublinear time algorithms. Proceedings the International Congress of Mathematicians (ICM), 2006.
[Sco79] D. W. Scott. On optimal and data-based histograms. Biometrika, 66(3):605-61) 610, 1979.
[TGIK02) N. Thaper, S. Guha, P. Indyk, and N. Koudas. Dynamic multidimennsioaal histograms. In SIGMOD Conference, pages 428-439, 2002.
[Vall[] P. Valiant, Testing symmetric properties of distributions. SIAM J. Comput., 40(6))1927- 1968, 2011.
[VV13] G. Valiant and P. Valiant. Estimating the unseen: improved estimators for entropy and other properties. Advances in Neural Information Processing Systems, 26, 2013.
[WY16] Y. Wu and P. Yang. Minimax rates of entropy estimation large alphabets via best polynomial approximation. IEEE Trans. Inform. Theory, 62(6))370--3720, 2016.
19] Y. Wu, P. Yang, al. Chebyshev polynomials, moment matching, and optimal estimation of the unseen. Annals of Statistics, 47(2):857-883, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all thcoretical results? [Yes] See Theorem
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix (Supplementary Materials).
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
12

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' ro using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "eR98SEi4XJx", "reviewer": "Reviewer_YQdn", "summary": "The paper, as suggested in the title, provides a new algorithm for testing whether a given distribution is close to a k-histogram, where the measure of performance is the sample complexity, and provides a nearly matching lower bound.  ", "questions": "\nHave you implemented the algorithm?  i ask as you make claims to practical relevance, but also for these complex analyses I might suggest that an implementation is a good check that everything works (as subtle bugs in theoretical analyses are hard to find).\n\nI couldn't help but wonder about a related problem, focused on what is the importance here of the data being a histogram, with intervals having the same value.  What if instead it was just that p_i was supposed to be close to one of k values for all i, but they need not be arranged in intervals?  (That is, the data is a permutation of or could be permuted into a distribution that is close to a k-histogram.)  Is this problem known/understood?  What is the importance of \"intervals\" in the sample complexity here?", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nClear formal problem.\nProofs/arguments seem difficult and of high quality.\n\nWeaknesses:\nThis is a theoretical paper.  [It is my opinion that it would be \"more at home\" at a theoretical conference, ranging from COLT or RANDOM to SODA/FOCS/STOC, but I will not focus on scope in my evaluation.]  \nNo simulations to verify the work or compare with other approaches -- purely a theoretical result.\nTies to learning generally are weak (a paragraph devoted to model selection, that's about it).  \nSmall number of typos.\n\nOriginality:  Appears to be original theoretical results.\nSignificance:  Appears to be a significant advance on this problem.\nQuality:  Challenging theorems.\nClarify:  Definitely hard to follow and dense for someone not in the area, as one might expect for a theory paper.\nSignificance:  Worthwhile problem in something of a niche area.\n\nI think in this sort of paper it is worthwhile for the authors to make clear what their goal is.  Here their goal is apparently to get near-optimal upper and lower bounds.  But are these algorithms practical?   Are they actually better than the prior work they cite in a practical sense?  As a theoretical paper, the authors don't seem to care to address these issues, but since their motivation (for this conference at least) is that this may be useful for model selection, it does seem to me that some experimentation or even just showing they have implemented the algorithm would have been useful.   ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WQnG8z4uJSc", "reviewer": "Reviewer_oQwe", "summary": "This paper falls in the topic of testing properties of discrete distributions using *sublinear* number of independent samples. The testing problem considered is the following. Given independent samples from an unknown distribution $D$ over sample space $[n]$, an integer $k \\leq n$, and an error parameter $\\varepsilon$. Decide whether $D$ is a $k$*-histogram* over $[n]$ or $D$ is $\\varepsilon$-far (in total variation distance) from every $k$-histogram over $[n]$. A $k$-histogram is a distribution that is piecewise uniform over $k$ intervals over $[n]$. The goal is to design an efficient algorithm  that uses as little samples as possible,  and also to establish lower bounds on the number of samples needed.  \n\nThe main contribution of the  paper is an efficient algorithm with near-optimal sample complexity for this testing problem with a matching lower bound (up to polylog factors). In particular they (1) design a time efficient algorithm that uses $\\tilde{O}(\\sqrt{nk}/\\varepsilon+k/\\varepsilon^2+\\sqrt{n}/\\varepsilon^2)$ samples, (2) establish a lower bound of  $\\tilde{\\Omega}(\\sqrt{nk}/\\varepsilon+k/\\varepsilon^2+\\sqrt{n}/\\varepsilon^2)$ on the number of samples require.  This settles the sample complexity of the histogram-testing problem for all parameter regimes up to polylog factors.  ", "questions": "As mentioned, the limitation of the paper is its appeal to a wider audience. I think it is inherent in the problem considered. So it will be difficult, but it will be nice if the authors can motivate this problem for a wider audience.  ", "limitations": "I do not see any section addressing the limitations and potential negative societal impact of their work. However, for this work that may not be relevant. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:* Histogram testing problem has been of interest in the distribution testing literature for the past decade. This paper can be viewed roughly as a culmination of research on this problem, at least from a sample complexity perspective. While the basic approaches used are from earlier works, the paper is technically very strong. The paper is well written. \n\n*Weaknesses:* The histogram testing problem considered in this paper may not appeal to a broader community. While technical contribution is strong, the paper does not introduce any new approaches/techniques that may be of wider applicability. Thus this is a niche paper.  \n\nOverall, this is a strong paper in the specific area of distribution testing and I like it. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G8Ke_HiNxlJ", "reviewer": "Reviewer_ua2e", "summary": "This paper falls in the broad area of distribution property testing; the property studied in this paper being whether a given unknown discrete distribution over an alphabet of size $n$ is a $k$-histogram or is $\\epsilon$ away from any $k$-histogram in TV distance. Previous works showed a $\\tilde{O}(\\frac{\\sqrt{kn}}{\\epsilon^3})$ upper bound and a $\\tilde{\\Omega}(\\frac{\\sqrt{n}}{\\epsilon^2} + \\frac{k}{\\epsilon})$ lower bound on the sample complexity for constant probability of error. This work characterizes optimal dependence of the sample complexity on $n,k,\\epsilon$ up to log factors. \n\nThe tester largely builds on a previous work that had a flaw in its analysis. Specifically, at a high level, the tester in this paper learns an approximate measure that is close if the unknown distribution is a $k$-histogram. This approximate measure is learnt by partitioning the domain in $K$ intervals, constructing a \"histogram-measure\" on these intervals and then discarding 'bad intervals' that contribute to a large $\\chi^2$ divergence. The main innovation lies in the last part where the tester removes fewer 'bad' intervals. \n\nThe lower bound relies on constructing hard instances using moment-matching random variables that are supported on roots of an appropriately constructed Chebyshev polynomial. ", "questions": "I am not entirely convinced how practical the current formulation of the testing problem is, especially for histograms. For example, I can imagine a practitioner not knowing the value of $k$ precisely. In that case does it make sense to test against being $\\epsilon$-away from a $k$-histogram since potentially a $k+1$-histogram can be $\\epsilon$-away from a $k$-histogram? I do understand that the current formulation is ubiquitous in distribution property testing literature and perhaps makes analysis easier. But perhaps some discussion about why this formulation makes sense might improve the paper slightly. \n\nMinor comments\n1) m in Lemma 1 is not defined. \n2) Figure 1 is an interesting way to depict tradeoffs, but it's not polished. I'd suggest TeXing the legend and increasing size. ", "limitations": "I am satisfied with how the authors have addressed impact. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper settles the histogram testing problem which earlier had a polynomial gap between the upper bound and lower bound on the sample complexity and was first studied in the current framework about a decade ago. The techniques in the paper are interesting and novel, although the tester mostly builds on previous work. The paper is written clearly and flows well. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G29kin2EpT1", "reviewer": "Reviewer_VmGT", "summary": "Distribution testing is a field of sublinear algorithms that aims to certify that a input probability distribution has some property or is $\\epsilon$-far from it, e.g., in total variation distance. One such property is whether a distribution on $[n]$ is a $k$-histogram, i.e., the distribution's support can be partitioned into $k$ continuous intervals so that on each interval, the distribution is uniform. The so far best algorithm draws $\\tilde{O}(\\sqrt{kn} / \\epsilon^3)$ samples from the input, and a lower bound of $\\tilde{\\Omega}(\\sqrt{n} / \\epsilon^2 + k / \\epsilon)$ is known. If $k$ or $\\epsilon$ are a function of $n$ (i.e., only mild bucketing or high precision), these bounds are not tight. In this submission, the authors present an algorithm with complexity $\\tilde{O}(\\sqrt{nk} / \\epsilon + k / \\epsilon^2 + \\sqrt{n} / \\epsilon^2)$, and a matching lower bound (up to polylogarithmic factors).\n\nThe algorithm designed by the authors partially picks up a previous (and failed) attempt from related work and tests the distribution learning it first. In particular, the algorithm tries to learn a $k$-histogram model from the input and detects breaks between intervals that (are likely) uniformly distributed. The algorithms is adaptive, and iterates on these breaks to either reduce the uncertainty sufficiently or certify that the input is far from a $k$-histogram. The lower bound is based on a classic information-theoretic scheme, where the challenge lies in the analysis of the specific instance.\n\nRemark on the confidence of the rating: I didn't check all the math carefully. The arguments are plausible, but the whole proof (main part + appendix) that would need to be checked is too much.", "questions": "-", "limitations": "-", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* Upper and lower bounds matching in $n,k,\\epsilon$ up to polylogarithmic factors, which is quite strong as a as statement.\n* The theoretical analysis is sophisticated and highly non-trivial.\n\nWeaknesses:\n\n* For a proof of practical implications, it would be good to either have explicit bounds (with constants spelled out, no asymptotics) or experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept