Optimal Algorithms for Augmented Testing of Discrete Distributions
Authors: Maryam Aliakbarpour
Piotr Indyk
Ronitt Rubinfeld
Sandeep Silwal
Venue: NeurIPS 2024 poster (2024)
Keywords: distribution testing
learning-augmented algorithms
data driven algorithm
hypothesis testing
hypothesis selection
distribution learning
Primary area: learning_theory
TL;DR: We study hypothesis testing of distributions in an augmented setting where learned information about the underlying distribution is available.

Abstract: We consider the problem of hypothesis testing for discrete distributions. In the standard model, where we have sample access to an underlying distribution $p$, extensive research has established optimal bounds for uniformity testing,  identity testing (goodness of fit), and closeness testing (equivalence or two-sample testing). We explore these problems in a setting where a predicted data distribution, possibly derived from historical data or predictive machine learning models, is available. We demonstrate that such a predictor can indeed reduce the number of samples required for all three property testing tasks. The reduction in sample complexity depends directly on the predictor’s quality, measured by its total variation distance from $p$. A key advantage of our algorithms is their adaptability to the precision of the prediction. Specifically, our algorithms can self-adjust their sample complexity based on the accuracy of the available prediction, operating without any prior knowledge of the estimation’s accuracy (i.e. they are consistent). Additionally, we never use more samples than the standard approaches require, even if the predictions provide no meaningful information (i.e. they are also robust). We provide lower bounds to indicate that the improvements in sample complexity achieved by our algorithms are information-theoretically optimal. Furthermore, experimental results show that the performance of our algorithms on real data significantly exceeds our worst-case guarantees for sample complexity, demonstrating the practicality of our approach.

Optimal Algorithms for Augmented Testing of Discrete Distributions
Maryam Aliakbarpour
Piotr Indyk MIT Cambridge, MA
Ronitt Rubinfeld MIT Cambridge, MA ronitt@csail. mit edu
Rice University
Houston, TX
maryama@rice.. edu
indyk@mit edu
Sandeep Silwal UW-Madison Madison, WI silwal@cs. wisc edu
Abstract
We consider the problem of hypothesis testing for discrete distributions. In the standard model, where we have sample access to an underlying distribution p. extensive research has established optimal bounds for uniformity testing, identity testing (goodness of fit), and closeness testing (equivalence or two-sample testing). We explore these problems in setting where predicted data distribution, possibly derived from historical data or predictive machine learning models, is available. We demonstrate that such predictor can indeed reduce the number of samples required for all three property testing tasks. The reduction in sample complexity depends directly the predictor's quality, measured by its total variation distance from p. A key advantage our algorithms is their adaptability to the precision of self-adjust their sample complexity
the prediction. Specifically, our algorithms based on the accuracy of the available prediction, operating without any prior knowledge of the estimation's 's accuracy (i.c. they consistent). Additionally, never use more samples than the standard approaches require, even if the predictions provide meaningful information (i.e. they also robust). We provide lower bounds to indicate that the improvements sample complexity achieved by our algorithms
optimal. Furthermore, experimental results show that the performance of our algorithms on real data significantly exceeds our worst-case guarantees for sample complexity, demonstrating the practicality of our approach.
1 Introduction
Property testing of distributions is fundamental task that lies the heart of many scientific endeavors: Given sample access to an underlying unknown distribution p. the goal is to infer whether has a certain property or it e-far from any distribution that has the property (in some reasonable notion of distance, such as total variation distance) with as few samples as possible. Over the past century [66], this problem has been extensively explored in statistics, machine learning, and theoretical computer science. Indeed, distribution testing (also called hypothesis testing) is now a major pillar of modern learning theory and algorithmic statistics, with applications in learning mixtures of distributions such as Gaussians, Poisson Binomial Distributions and robust learning [40, 45, 36, 75, 34, 45]. The framework has also been extensively studied under privacy [56, 14, 27, 18. 26, 3, 72, 50] and low-memory constraints [8].
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

One of the most natural and well-studied questions in this framework is: given sample access to an unknown distribution p. can we determine whether p is equal to another distribution q. or e-far from it (e.g. in total variation distance)? This problem has been studied under various assumptions about how we access q: It is called uniformity testing when q is a uniform distribution, identity testing (or "goodness-of-fi"s when a description of q is known, and closeness festing ("two-sample testing" or "equivalence testing") when we only have sample access to q. The primary goal in solving these tasks is to design algorithms that use as few samples as possible. Optimal sample complexity bounds have been established for discrete distributions p and q over a domain of size n: ((vT/(²)) samples
for uniformity testing [52. 15, 69, 38] and identity testing [76, 5, 391, and θ (122/3/e /e4/3 + vn/e²) samples for closeness testing [16. 30, 38, 39]. Other related versions of uniformity, identity, and closeness testing are presented in [63, 6, 19, 51, 46, 74, 12, 13, 68].
Given that the aforementioned results are tight and cannot be improved, any further progress requires equipping the algorithm with additional functionality. A natural approach to leverage the fact that in numerous applications, the underlying distribution is not completely unknown; some prediction of the underlying distribution may be available or can be learned via a predictive machine learning model. For example, if distributions evolve slowly over time, earlier iterations can serve approximations for later ones, e.g., network traffic data and search engine queries. Such estimations can often be learned from "older" data by using it to train predictor regressor. In linguistics and text processing tasks that involve distributions over words, the length of a word can approximate its frequency, since longer words are known to be less frequent. Another example is when data is available at different "scales." For instance, deemograpemoo data on loan defaults at the national level could be informative for data from specific areas.
One challenge to using such information is that it rarely comes with a guarantee of precision. This fact leads to the information being deemed unreliable, as it may poorly predict the underlying distribution. For example, while the national loan default rate might be close to that of a typical area code, it could differ significantly in affluent areas. Thus a natural algorithmic question that arises is how to design algorithms that can exploit predictive information as much as possible without any prior assumptions about its accuracy. The goal is then to design an algorithm that solves the problem with as few samples as possible, given the quality of the prediction.
In this work, we study the fundamental problems of uniformity, identity, and closeness testing in the setting where a prediction of the underlying distribution is provided. This prediction can be formalized by assuming that the distribution testing algorithm has access to predicted distribution ý of p'. This is in addition to having sample access to p as in the standard model (without access to prediction). Our algorithms achieve the optimal reduction in the number of samples used compared to the standard case, where the improvement depends on the quality of the predictor á in terms of its total variation distance from p. Our algorithms can also self-adjust their sample complexity to the accuracy of p. minimizing sample complexity wherever fcasible, without prior knowledge of p's accuracy. Our approach ensures that the algorithm is resilient to inaccuracies in predictions and does not exceed the optimal sampling bound in the standard model, even when e significantly deviates from the actual p. Furthermore, our matching lower bounds demonstrate the optimality of our algorithms. Experimental results additionally confirm the practicality of our algorithms.
Measuring accuracy of predictor. We use the total variation distance between the prediction P and the unknown distribution p as our measure of predictor accuracy. Previous work often assumed strong dementtwwie guarantees, where P. is within a constant multiplicative factor of p; for all domain elements i, a constraint that becomes limiting especially for small ps (see Section 1.3). This paper is the first to study a notion of average error between p and p. measuring via the TV distance. This metric was chosen for its prevalent use in statistical inference and its intuitive interpretation.
1.1 Our approach and problem formulation
Our approach to solving distribution testing problem (uniformity, identity, or closeness testing) consists of two components: search and test. At a high level, search aims to guess ||p - pllTV, and test performs the actual distribution testing using the guess of the accuracy provided by search as a suggested accuracy level.
We assume we know all of the probability values of the prediction ş all domain elements.
2

---

More precisely, our augmented test component aims to evaluate whether q, while receiving P and a suggested accuracy level a (which may or may not reflect the true distance between p and p). In addition to two possible outcomes of accept and reject in the standard setting', our augmented test component may output inaccurate information when it determines that the á is not a-close to p. Our requirements for the augmented fest component are the following: i) If the test is conclusive, i.e., it chooses to output accept or reject, the answer should be correct regardless of p's accuracy. ii) If p is indeed a-close to p. the test component should not output inaccurate information.
We emphasize that the guess a is not guaranteed to correct or may not even be valid upper bound on the true TV distance. Thus, the algorithm is afforded a degree of flexibility to forego solving the problem when the distributions are not within a proximity (and can try again with a new guess).
Our search component aims to identify an appropriate accuracy level a such that the test component can test in a conclusive manner by returning accept reject. Since the true value distance ||p Tl|TT is not known, we start by guessing a small a, corresponding to the most accurate p and the fewest samples needed, run the augmented test component with this and p. and verify the conclusiveness of the testing. If inconclusive, our guess a is increased to a level that we can afford testing by doubling the sample size, and the search component proceeds with the next a. continues until the desired accuracy is reached, and accept or reject is returned. Then, search halts with that result.
Clearly, if the accuracy level guess is at least lpp - plaTv. the test component has to output accept or reject with high probability. Thus, we show that it is unlikely that search proceeds when >> 1pp - -llTVV Therefore, this method does not significantly increase the sample complexity, potentially increasing it by at most an (log (o)(n/)) factor in expectation. The search component is applicable all of the problems we study and we defer all details of the search component Section B. The remainder of the main body focuses on designing the augmented testers, i.e. the test component.
Definition 1.1 (Augmented tester). Suppose we are given parameters, a E [0, 1]. E 1), E (0, n E N, and two underlying distributions p and q, along with a prediction distribution P over [m]. Suppose A is an algorithm that receives all these parameters, and the description of p as input, and has sample access to p and q. We say algorithm is an (a, c, (. tester for closeness testing if the following holds for every q. and p over [n]:
If p and p are a-close in total variation distance, the algorithm outputs inaccurate informa- tion with probability at most 8/2.
p mp=0 4. then the algorithm outputs reject with a probability at most 8/2.
If is e-far from q, then the algorithun outputs accept with a probability at most 5/2.
In this definition, if the description of q is known to the algorithm instead of having sample access, we say is an (a, c, (,,,,,))-a)) -augmenntd tester for identity testing. If q is uniform distribution over [ni] then we say A is (a,e, (a,,,,8)auge ( -aaumeeeed tester for uniformity testing.
To highlight the distinction between this definition and the standard definition, note that in the standard regime, no prediction ş is available to the algorithm, and the algorithm lacks the option of outputting inaccurate information.
Remark 1. We assume that 5 is a small constant, but, standard amplification technique via Chernoff bounds can achieve an arbitrarily small confidence parameter with a (log(1/6)) overhead.
1.2 Our results
Our theoretical results: In this paper we demonstrate that predictions can indeed reduce the number of samples needed solve the three aforementioned testing problems. Our algorithms are parameterized by both e and a. We provide tight sample complexity results (matching upper and lower bounds) for these problems. The sample complexity drops drastically compared the standard case, depending on the total variation distance between and p. Our algorithms are also robust: if the prediction error is high, our algorithm succeeds by using (asymptotically) the same number of samples as the standard setting without predictions.
2If = 4. the standard tester must output accept with high probability. And, if p is c-far from y. the standard tester must output reject with high probability. If p & q. but c-close g. either answer is considered correct.
3

---

Theorem (Informal version of Theorem 7). Augmented uniformity and identity testing for distribu- tions over [n]. with parameters a, 6, and 2/3, require the following number of samples:
ifd
min
(d-ayz
v +t
ifd
where d - 11g -l/Tv (q is the known distribution, for identity testing, the uniform distribution for uniformity).
Remark 3. Note that d is not an input parameter the algorithm. However, d is determined by p and 9, which are known to the algorithm, allowing us to compute
For closeness testing, we prove the following.
Theorem (Informal version of Theorem 9). Augmented closeness testing for distributions over [n]. with parameters a, c, and = 2/3, requires @(n2/3 1/ //3
4/3 + vn/e²) samples.
It can be seen that c.g., for closeness testing, non-trivial predictor improves over the best possible sampling bound in the standard model. Specifically, as long as a = o(1), our bound the augmented model improves over the prior work. At the same time, even if a (1), our sampling bounds do not exceed those in the standard model. Note that all theorems complemented by tight lower bounds. We highlight that all of our algorithms also computationally efficient, running in polynomial time with respect to and 1/e. The results are summarized in Table 1.
algorithms
resilient:
Table 1: Optimal sample complexity bounds in the standard model versus the augmented bounds. is the suggested accuracy level for the L1 distance between p and p. denotes the total variation distance between the known distribution q and p.
Property
Standard sample complexity
Augmented sample complexity (this paper)
Closeness
273
+
ynn
[30, 69]
θ
g73
Vn
1/3
22
4/3
θ
if
i
Identity/Uniformity
[69.
+ min
if
(d-a)²*
Our empirical Results: We empirically evaluate our augmented closeness testing algorithm on synthetic and real distributions and refer all details to Section E.
As summary, algorithm indeed leverage predictions to obtain significantly improved sample complexity over the SOTA approach without pre- dictions, as well as SOTA algorithms needing very accurate predictions [28].
Closeness Tester Hard Instance
40
Closeness Tester Augmented Testor
For distributions similar to our lower bound instances, our augmented algorithm achieves >20x reduction in sample complexity to obtain comparable accuracy as the standard un-augmented algorithm, as shown in Figure 1. On real distributions curated from network traffic data, we sample complexity reductions of up to 40%. Furthermore, our algorithm is empirically robust to noisy predictions, in contrast to prior state of the art approaches which assume very accurate, wise predictions (CRS' 15 in Figure 1).
% Error
30
CRS '15
20
10
1000
3750
10500
13250
20000
# Samples
is worth noting that our experiments on network traffic data reveal that the actual sample complexity is much lower than the anticipated worst-case sample complexity of our algorithm. In particular, this holds
Figure 1: Error vs sample complexity for the theoretically hard instance (See Sec. E).

---

even when ő is far from in terms of total variation distance. Empirically, if ý accurately reflects the high-probabille elements in p. our algorithm can significantly reduce the sample complexity needed for testing by utilizing these heavy hitter "hints" from P. This is validated by our results and depicted in Figures 5 and 7(b).
1.3 Related works
To the best of our knowledge, there have been only three prior works that studied any distribution property testing algorithms with predictions, each assuming a much stronger prediction model:
Distribution testing with perfect predictors [29]: this work studied distribution testing problems, including closeness, identity and uniformity, assuming query access to a perfect predictor, i.e., ý p. They show that, given perfect predictor, it is possible to obtain highly efficient testers for a wide variety of problems with a small number of queries to the prediction. Unfortunately, the perfect-predictor assumption is often too strong hold in practice, as demonstrated e.g., in [48] and in our experiments.
Distribution testing with (1++)-approxing used in the above paper, requiring only that P. (1 + c/2)p; for all i and sufficiently small c 0. requiiiii
predictors [28, 67]: these works relax the assumption
However, this assumption is still quite restrictive, especially for low values of c. Indeed in our experimental setting, such algorithms
not robust to prediction errors (see Section E).
Support estimation with c-approximate predictors [48]: this work focused on the single problem of support estimation, i.e., estimating the fraction of coordinates such that p; > 0. It further relaxes the assumption in [67] by allowing the predicted probabilities P; to be within a factor of c of the true probabilities Ps, for any constant approximation factor c > 1. This algorithm has been shown to work well in practice. However, the techniques presented in that paper seem to be applicable exclusively to support estimation. Furthermore, their result provably does not hold under the assumption that p and P are close in TV distance, as in this paper.
In summary, prior results required either highly restrictive assumptions, or were applicable to only a single problem. None of the previous algorithms worked under the TV distance assumption used this paper which is arguably the most natural. Further exploration of measures such as Lp -p--distacess KL-divergence, and Hellinger distance are interesting open questions.
We remark that we can mathematically show that these alternative oracles yield provably more power compared to ours (i.e., we make weaker assumptions about the predictor). We provide an alternative to our upper bound techniques for these alternate prediction models in Section G. We demonstrate how variant of our algorithm, in conjunction with these stronger predictions, implies that uniformity testing, identity testing, and closeness testing in these models can be conducted using only O ((Vn/e²) samples. This low sample complexity effectively circumvents our lower bound for closeness testing, suggesting that these models provide stronger, and arguably less realistic, predictions.
Other related works: Other related works discussing algorithms with predictions and general distribution testing are discussed in Appendix A.
1.4 Notation and organization
Notation: We use [n] to denote the set (1, All of our distributions will be over the domain [n),, and we assume is always known. For distribution p. we denote the probability of the i-th element by ps. For any subset of the domain S C [n|] we denote the probability mass of S according to by P(S). We use p to denote the probability distribution of s i.i.d. samples drawn from p. We say p is a known distribution, if we have access to every p;- We say p is an unknown distribution if we have only sample access to We use Poi(A) to denote a random variable from a Poisson distribution with mean Similarly, Ber(A) indicates a random variable from the Bernoulli distribution that is one with probability X. Given two distributions p and q over domain X,, we use ||p - q||Tv= == supscx (p(S) - (S) to denote the total variation distance between p and q. We say and are e-close (e-far), if the total variation distance between p and g is at most (larger than e).
nn..
Organization: We provide an overview of our theoretical results in Section 2. The upper bound on augmented closeness testing is presented in Section 3. The search algorithm is detailed in Section B.
5

---

Augmented uniformity and identity testing are discussed in Section C, where the upper bounds are presented in Section C.I, and the lower bounds are provided in Sections C.2 and C.3.
Augmented closeness testing is discussed in Section D. with the lower bounds provided in Section D. 1. Our empirical evaluations are presented in Section E.
2 Overview of our proofs
Search algorithm: The search algorithm seeks to find the smallest value of a for which the problem is solvable via the augmented tester. It starts with the lowest value of a (most accurate prediction). Then, it iteratively increases the sample budget across rounds. In each round i, it selects an a, for the augmented tester, A. ensuring operation within the current sample budget. If A outputs accept or reject, the algorithm echoes this outcome. If inaccurate information is returned, the sample budget doubles for the next round. It is worth noting that this search scheme is applicable to a general distribution testing algorithm with polynomial sample complexity. The algorithm's 's pseudocode and its performance proof are in Section
Upper bound for augmented identity testing Let d represent the distance between ş and q (the prediction and the known distribution). For establishing the upper bound, it is essential to assume d a. If not, the prediction proves unhelpful, and we might as well resort to the standard tester.
Our upper bound relies on a simple but fundamental observation regarding the total variation distance: this distance is the maximum discrepancy between the probability masses that two distributions assign to any subset of their domain. To prove that total variation between two distributions is small entails proving that the discrepancy across every domain subset is small. In contrast, to prove a large total variation distance. one only needs to identify a single subset with a large discrepancy as evidence of large total variation distance. We use the Scheffé set of P and e-hharacterizeed as the collection of elements x [n]] where p(x) < ((x), symbolized by S-as evidence of p's divergence from either q or P. More precisely, is known that S maximizing the discrepancy between the probability masses of p and q. implying: d == |1g pl[TV= = ((()) p(S) Next, we estimate the probability of set S according to p with reasonably high accuracy, Given g(S) and ((5), then P(S) is either significantly different from g(S), or it deviates from ((S). In the first scenario, this discrepancy serves as evidence that p + q. allowing us to output reject. In the second scenario, the deviation confirms that p is a-distant from p. leading us to output inaccrrate information. Further details can be found in Section C.I.
Lower bound for augmented uniformity testing We provide two lower bounds for augmented uniformity testing. One is purely based on reduction to standard uniformity testing for the case where a 2 d. (Recall that d was the total variation distance between q and p). See Section C.2.
The other lower bound applies to the setting where < d. One challenge of this problem was that it is hard find two difficult distributions that the tester has to distinguish between; usually, for a pair of distributions, we could come up with one valid output that could serve them both. For example, for both uniform distribution, and the famous c-far uniform distribution that assigns probabilities (1 + e)/n to the elements, the algorithm may be able to output inaccurate information. Hence, we cannot draw lower bounds just by asking the algorithm to distinguish between two distributions.
For this reason, we provide three distributions that look similar when we draw too few samples. We formalize the similarity of these three distributions using a multivariate coupling argument. We show that these distributions are such that there is no possible answer that is valid for all three of them. Now, (similar Le Cam's 's method), suppose we feed the algorithm with samples from one of these three distributions (each with probability 1/3). For any sample set, the algorithm outputs an answer (which may be randomized); however, this answer is considered wrong for least one of the underlying distributions. This is due to the fact that there is no universally valid answer that is sinultaneously correct for all three distributions. Hence, if the algorithm outputs a valid answer with high probability, it must be able to distinguish the underlying distributions to some degree. On the other hand, the indistinguishability result says it impossible to tell these distributions apart. Thus, reach contradiction. And, the lower bound is concluded. See Section C.3 for further details.
6

---

Lower bound for augmented closeness testing: We provide two separate lower bounds for close- ness testing based on the relationship between a and c. Further details are available in Section D.I.
Our first lower bound, as detailed in Theorem 11, employs a reduction strategy from standard closeness testing augmented closeness testing when
c. This is achieved by taking instances used in standard closeness testing for distributions over [n - 1] and embedding them into the first n domain elements of a new distribution p defined over [n]. The key this strategy is to put the majority of the distribution's 's mass ((1 - a) mass) on its final element, and we set the prediction p to be singleton distribution over the last element, which is a-close to p. Clearly, the prediction does not reveal any information about the first n 1 elements of p, implying that testing the closeness of p in the augmented setting is as challenging as in the standard setting, once the parameters are appropriately scaled. Our second lower bound, outlined in Theorem 12, is more involved. In the standard setting, the lower bound for closeness testing is derived from the hard instances for uniformity testing with one crucial adjustment: adding new elements with large probability (approximately n n-2/3) in the distributions. These large elements have identical probability masses in both p and q. indicating they do not contribute to the distance between the two distributions. However, their presence in the sample set confuses the algorithm: due to their high probabílities, their behavior in the sample set may misleadingly suggest non-uniformity, complicating the algorithm's 's task of determining the uniformity of the rest of the distribution. Therefore, the algorithm requires s Rs n²/3 samples to first identify these large elements before it can test the uniformity of the remaining distribution. Surprisingly, this requirement of R 222/3 samples is significantly higher than the O(yn) samples typically sufficient for testing uniformity.
The challenge in our case arises because P may disclose the large elements to the algorithm. To establish the lower bound, we set P to be the uniform distribution, we generate hard instances of p by adding as many large elements as possible, without altering p. by keeping the overall probability mass of the large elements limited to a. More precisely, p assigns approximately (1 a)/n probability mass to (n) elements chosen at random, and assigns approximately n 2/3 probability mass to a 2/3 elements in the domain. Now, q has two scenarios. Half the time, q identical to p. The other half, retains the same large elements but deviates slightly from uniformity for the rest of the distribution. Specifically, q assigns probabilities (1 (())) a)/n n to the randomly chosen (n) elements, making it c-far from p. It is not hard to show that testing closeness of and q is a symmetric property (since permuting the domain elements does not affect our construction). By leveraging the wishful thinking theorem from [78], we demonstrate that these two scenarios are indistinguishable unless 2(n2/3 a 1/3) samples are drawn.
3 Upper bound for closeness testing
Our upper bound is based on a technique called flattening, which has been previously proposed by Diakonikolas and Kane [42]. This technique is instrumental in reducing the variance of the statistic used for closeness testing by reducing the & fo-norm of the input distributions. We adapt this technique for use in the augmented setting, aiming not only to flatten the distribution based on the samples received from it but also exploiting the prediction distribution p. We demonstrate that augmented flattening can significantly reduce the fn-norm of p. our algorithm, we initially check if the l ng-norm of p is reduced after flattening to the desired bound. If not, this indicates that the prediction sufficiently accurate, leading us to output inaccurate. Conversely, if the fz-norm of is small, we proceed with an efficient testing algorithm that requires fewer samples. We describe the standard flattening technique in Section 3.1. Our flattening technique presented in Section 3.2. Finally, we provide our algorithm in Section 3.2.1.
not
3.1 Background on flattening
Suppose we are given n parameters m., .2...., ..p. One can create randomized mapping F that assigns each [r]] to a pair (i.j), where j is drawn uniformly at random from [m.]. Now, consider a given distribution p over in] and a sample i drawn from p. This mapping induces a distribution over pairs (i, j)'s in D = {(i.j) E [n] and j E [m.]]. We denote this new distribution by p(F) satisfying the relation: (F)
((..) = Ps/m; The core idea of the above mapping is to divide
7

---

the probability of the i-th element into my buckets. If the values of m, 's are large for elements in p with higher probabilities, then the resulting distribution plP) will avoid having any elements with disproportionately large probabilities, thereby naturally lowering its fn-nom.. Diakonikolas and Kane [42] showed that if we draw Poi(t) samples from p. and set each m, to be the frequency of element among these samples plus one, then have:
2
1
E
where the expectation is taken over the randomness of the samples.
Connection distribution testing: Chan et al. in [30] showed that one can test closeness of two distributions over [n] using On max l samples. Diakonikolas et al. [42] used this tester in combination of the flattening technique to map distributions to distributions over slightly larger domains with the goal of reducing their fz-norms. They have shown that if we use the same mapping to reduce the f--norm of both p and q, the fz-distance between the two distribution does not change the & distance between distributions.
Fact 3.1 ([42)). For any flattening scheme F, the e -ddistancee is preserved under F. That is, for every pair of distributions p and we have:
|p 1p-9lli 9l11 = 11110) -0 11.
Therefore, test p and q, draw samples
up with the flattening F reduce the f--norm of one of the underlying distributions. Then, we can test the closeness of p(F) and g(
with (n maax([pp(]]]] [|g[() [ ())/"²) new samples. Later, Aliakbarpour et al. in [9] showed that Onn min(lpll2 (laell))/ samples is sufficient.
The exact sample complexity determined by balancing the samples needed to determine the flattening and the samples needed test closeness of (P)) and (F)) Note that flattened distributions have larger domain size. Thus, one must also balance the gains obtained from the reduction in & norm with the increase in the domain.
3.2 Augmented flattening
We adapt the flattening argument in [42] to the augmented setting.
Lemma 3.2. Suppose we have an unknown distribution == (PI.P2.... P2...., Pn.) over [n] and Poi(s;) samples from Assume we are given a known distribution p that is a-close to in TV distance. Then for every S 1, there exists a flattening F which increases the domain size by 1/u + s expectation and the expected (3- (-norm of the FFF F) is bounded by:
1:]]
2a
<
+4.v.
2
8f
The expectation above is laken over the randomness of the samples from p.
Proof. Let 8y == Poi(sy) be a Poisson random variable with mean sy. Let Sy denote the multiset of & samples from p. Let fr denotes the frequency of clement in Sy. For every i, we define the number of buckets for element as follows:
Ps
my ==
+ Sa +
(1)
Let (FF) denote the flattened version of p where we split every element into m, buckets. We show that the expected fg-nrmm of p!F) is low. Define A; to be p: Pt- Suppose A is set of indices E [n] for which A, 2 Ps. For every i E A, Pt is bounded from above by 2 A, On the other hand, for every i E [na] A, p: is bounded by 2 p..

---

if Lp 30 2 2A; Pi
p 1 E E
p (i,s)
Σ
P
Σ
(2
mi
m;
m,
iE[n] jE imml
iE[n]
iE
2 24, Ps
(2
fi ++1
Ds/V
RE/DIA
2 2 pr
+4..
ft ++1
EEA
shown in [42], the expected value of pi/(fs + 1) taken over the randomness in the Sy is bounded by 1/sy:
1
Ep
85
Therefore, obtain:
24;
2a
EF
4v S
4v.
8/
81
iE
The last inequality above is due to the fact that:
((A) s
11p-1110 pllTV = a.
KEA
3.2.1 The algorithm
In this section, we provide an algorithm for testing closeness of two distribution in the augmented setting. Our algorithm receives a suggested accuracy level a. Based on a, we draw 5y (which depends samples from and use them to flatten p. If the resulting distribution has sufficiently small Ez-orrm we proceed to the testing phase. Otherwise, we declare that the accuracy level provided is not correct. The pseudocode of our algorithm is provided in Algorithm 1, and we prove its performance in Theorem
Algorithm An augmented tester for testing closeness of p and with suggested value a
1: procedure AUCMEENEDD--LLLLEESSSSSSSSSSSSS
a, c, 81 0.1, 82 2/33, p. sample access
p and q)
2: 8f & min 1/3/3/113//413,,
3:
8 + Poi(s;)
8 > 10 then
5:
return reject.
6:
F + F(mi, m2, mn) where m, are define in Equation 2.
7:
i== mi, 0.05) Lg ESTIMATE- (F)) i= mi, 0.05)
Ip + ESTIMATE- 12
(p(F) E
then return inaccurate information.
10:
11:
else
12:
if I.
> 90
2x + + then
my
13:
return reject.
14:
else
15:
return CLOSENESS-TESE TESTER (c, 8= b b 90
2n oy
+ a) p(F), g(F)).
Theorem For any given parameters n, a, e, and any two unknown distributions and q and a known predicted distribution for Algorithm is (a,, é, = 0.3) -agg-netdd tester for testing closeness of p and q which 2/3 2/3 / samples.
9

---

Proof. We begin the proof by setting our parameters. Set 8y = min 222/0a/33/44// n)). Suppose
we draw & = Poi(sy) ) samples from p. We flatten the distribution according to the augmented flattening we described in Section 3.2 replacing v with 1/n. We denote the flattening by F
F F(m1,..,, m)) where m;'s 's are defined in Equation (I):
m. = In Pi] + ft 1.
(2)
In the above definition, fs is the frequency of element among the š drawn samples.
Proof of correctness: Suppose we flatten both and according to F. The algorithm estimates the 2B of p(F) and (f According to Fact F.1, these estimates are within a constant factor of their true values each with probability at least 0.05:
||
3 |10
and 1 2
3 | < Lg
Lp
(3)
2
2
To prove the correctness of the algorithm, we show the three desired property of an augmented tester which are defined in Definition 1.1. First, assume ý a-close p. We show the probability of outputting inaccurate information is small. Using Lemma 3.2, after applying F, the expected @-norm of y(P) is bounded by:
E D
[.]
2a 8f
4
Using Markov's inequality, with probability at least 0.95, &3-ormm of p(F) is at most 20 times the above bound. Combined by the upper bound for T,p in Equation (3) and the union bound, in this case Lp is bounded by 30 (2a/sy + 4/n) with probability at least 0.9. Hence, we the algorithm does not output inaccurate information in Line 10 with probability more than O.I.
the algorithm outputs reject with small probability. We may output reject in three cases: 1) in Line 2) in Line 13 and 3) in Line 15. Using Markov's inequality, a Poisson random variable is more than 10 times its expectation with probability at most 0.1. We show the other two cases are unlikely as long as Lp and Lng are accurate estimates of the E3s of p(F) and ((²)) (which happens with probability of 0.9). If p algorithm Lp and Lg are the estimations of the & 22-norm of the same distribution. Note that we output reject in Line 13, only when Lp < 3Lg. Using Equation (3), this event does not happen unless at least of the estimates are inaccurate (which has a probability at most 0.1). Furthermore the estimated Eg f--nrrm are accurate, the minimum lg -nom of p and q( are bounded by 90 (2a/s) + 4/n) implying the tester would work correctly with probability at least 0.9. Using the union bound, the probability of outputting reject bounded by 0.3.
Second, we show that if
p(F)) and g(²)) are identical. Therefore, in the
Third and last, we show that if p is e-far from gf the probability of outputting accept is small. We only output accept in Line 15. Similar to the second case we have discussed, as long as the norm are accurate, the tester does not make mistake with probability more than 0.1. Therefore, the overall probability of making a mistake is bounded by 0.2.
Analysis of sample complexity: For the flattening step we have used & S 10sy. After flattening, the new domain size is bounded from above by:
Σ m. 1=1
n
+ 12n.
Using Fact F.1, estimation of Lg fg-norm requires ((vn) samples. Using Fact F.2, the number of samples we use for the test in Line 15 is O(n b/e2) samples. Hence, the total sample complexity is:
n b-b bb)
18 v /2a/s; 81 + 4/n
# samples =0 (0
Vn+
=0
2
2²
T 2
2/3 a
1/3
+
4/3
In the last line we use that sy = min (n2 1/3 /6/3, nn). Thus, the proof is complete.
C
10

---

Acknowledgments
Part of this work was conducted while the authors were visiting the Simons Institute for the Theory of Computing. M.A. was supported by NSF awards CNS-2120667. CNS-2120603, CCF-1934846, and BU's Hariri Institute for Computing. This work was initiated while M.A. was affiliated with Boston University and Northeastern University and was done in part while M.A. was a research fellow at the Simons Institute for the Theory of Computing. P.I. was supported by the NSF TRIPODS program (award DMS-2022448) and Simons Investigator Award. R.R. was supported by the NSF TRIPODS program (award DMS-2022448) and CCF-2310818.
References
[1] Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk. Shyam Narayanan, and Sandeep Silwal. Data structures for density estimation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 1-18. PMLR, 23-29 Jul 2023.
[2] Anders Aamand, Justin Y. Chen, Huy Lê Nguyen, Sandeep Silwal, and Ali Vakilian. Improved frequency estimation algorithms with and without predictions. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[3] J. Acharya, C. Canonne, C. Freitag, and H. Tyagi. Test without trust: Optimal locally private distribution testing. In Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pages 2067-2076. PMLR, 2019.
[4] Acharya, Z. Sun, and H. Zhang. Differentially private testing of identity and closeness of discrete distributions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, pages 6879-6891, 2018.
[5] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath, Optimal testing for properties of distributions. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 3591-3599, 2015.
[6] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda T. Suresh. Sublinear algorithms for outlier detection and generalized closeness testing. In IEEE ISIT, pages 3200-3204, 2014.
[7] Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld. Learning and testing junta distributions. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, pages 19-46, 2016.
[8] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Hypothesis selection with memory constraints. To appear in NeurIPS 2023, 2023.
[9] Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, and Ronitt Rubinfeld. Private testing of distributions via sample permutations. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 10877-10888, 2019.
[10] Maryam Aliakbarpour, Ilias Diakonikolas, and Ronitt Rubinfeld. Differentially private identity and equivalence testing of discrete distributions. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pages 169-178. 2018
[11] Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinya- nee. Towards testing monotonicity of distributions over general posets. In Proceedings of the Thirty-Second Conference on Learning Theory, COLT, pages 34-82, 2019.
11

---

fuer [12] Maryam Aliakbarpour, Ravi Kumar, and Ronitt Rubinfeld. Testing mixtures of discrete dis- tributions. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Secons Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 83-114, Phoenix, USA, 25-28 Jun 2019. PMIR.
[13] Maryam Aliakbarpour and Sandeep Silwal. Testing Properties of Multiple Distributions with Few Samples. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPlcs), pages 69:1-69:41, Dagstuhl, Germany, 2020. Schloss Brgsstul-Leibniz-ZZe Informatik.
[14] Kareem Amin, Matthew Joseph, and Jieming Mao. Pan-private uniformity testing. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 183-218. PMLR, 2020.
[15] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing that distributions are close. 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12- 14 November 2000, Redondo Beach, California, USA, pages 259-269, 2000.
[16] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing closeness of discrete distributions. JACM, 60(1 (001):4::144:) 2013.
[17] Tugkan Batu, Ravi Kumar, and Ronitt Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, II., USA, June 13-16, 2004, pages 381-390, 2004.
[18] Thomas Berrett and Cristina Butucea. Locally private non-asymptotic testing of discrete distri- butions is faster using interactive mechanisms. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell,
Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[19] Bhaswar B. Bhattacharya and Gregory Valiant. Testing closeness with unequal sized samples. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems Information P Processing Systems 2015, December 721 2015, Montreal, Quebec, Canada, pages 2611-2619, 2015.
28: Annual Conference on Neural
[20] Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant. Testing monotonicity of distributions over general partial orders. Electronic Colloquium on Computational Complexity (ECCC), 17:27, 2010.
[21] B. Cai, C. Daskalakis, and G. Kamath. Priv'it: Private and sample efficient identity testing. In International Conference on Machine Learning, ICML, pages 635-644, 2017.
[22] Clément L. Canonne. Big data on the rise: Testing monotonicity of distributions. In ICALP, 2015.
[23] Clément L. Canonne. Corrigendum: Are few bins enough: Testing histogram distributions. In SGGACT-SIGA/ Symposium on Principles of Database
Proceedings of the 42nd ACM Systems, PODS 2023, Seattle, WA, USA, June 18-23, 2023, page 359. ACM, 2023.
[24] Clément L. Canonne, Ilias Diakonikolas, Daniel Kane, and Sihan Liu. Nearly-tight bounds for testing histogram distributions. In Advances in Neural Information Processing Systems 35 (NeurIPS), 2022. To appear.
[25] Clément L. Canonne, Ayush Jain, Gautam Kamath, and Jerry Li. The price of tolerance distribution testing. In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 624.. PMLR, 2022.
12

---

[26] Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam D. Smith, and Jonathan R. Ullman. The structure of optimal private tests for simple hypotheses. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 310-321. ACM, 2019.
[27] Clément L Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Lydia Zakynthi- nou. Private identity testing for high- -ighesiiensional distributions. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 10099-10111. Curran Associates, Inc., 2020.
[28] Clément L Canonne, Dana Ron, and Rocco A Servedio. Testing probability distributions using conditional samples. SIAM Journal on Computing. 44(3):540 616, 2015.
[29] Clément L.
Canonne and Ronitt Rubinfeld. Testing probability distributions underlying ag- gregated data. In Automata, Languages, and Programming 41st International Colloquium, ICALP, pages 283-295, 2014.
[30] Siu-on Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In SODA, pages 1193-1203, 2014.
[31] Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, and Michael Zhang. Triangle and four cycle counting with predictions in graph streams. In 10th International Conference on Learning Representations, ICLR, 2022.
[32] Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. Learning and testing junta distribu- tions with sub cube conditioning. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1060-1113, PMLR, 15-19 Aug 2021.
[33] Edith Cohen, Ofir Geri, and Rasmus Pagh. Composable sketches for functions of frequencies: Beyond the worst case. In Proceedings of the 37th International Conference Machine Learning, 2020.
[34] Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. Learning poisson binomial distributions. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 22, 2012, pages 709-728. ACM, 2012.
[35] Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, and Paul Valiant. Testing k-modal distributions: Optimal algorithms via reductions. In Proceedings of the Twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 11, pages 1833-1852, Philadelphia, PA, USA, 2013. Society for Industrial and Applied Mathematics.
[36] Constantinos Daskalakis and Gautam Kamath. Faster and sample near-al algorithms for proper learning mixtures of gaussians. In Conference Learning Theory, pages 183-1213. PMLR, 2014.
[37] Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, and Sankeerth Rao. Communication and memory efficient testing of discrete distributions. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1070-1106. PMLR, 25-28 Jun 2019.
[38] Ilias Diakonikolas, Themis Gouleakis, J. Peebles, and Eric Price. Collision-based testers are optimal for uniformity and closeness. Chicago Journal of Theoretical Computer Science, 2019(1), MAY 2019.
[39] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Sample-optimal identity testing with high probability. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 41:1-41: 2018.
[40] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust matims in high-dimensions without the computational intractability. SIAM J. Comput., 48(2):742-864, 2019.
13

---

[41] Ilis Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis. Efficient testable learning of halfspaces with adversarial label noise. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023.
[42] Ilias Diakonikolas and Daniel M. Kane. A new approach for testing properties of discrete distributions. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 685-694, 2016.
[43] Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin. Optimal algorithms and lower bounds for testing closeness of structured distributions. In FOCS, pages 118--1202, 2015.
[44] Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin. Testing identity of structured distributions. In SODA, pages 1841-1854, 2015.
[45] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Properly learning poisson binomial distributions in almost polynomial time. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings. pages 850-878. JMLR.org. 2016.
[46] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Sharp bounds for generalized uniformity testing. In NeurlPS, pages 6204-6213, 2018.
[47] Elbert Du, Franklyn Wang, and Michael Mitzenmacher. Putting the "learning" into learning- augmented algorithms for frequency estimation. In Proceedings of the 38th International Conference on Machine Learning, pages 2860-2869, 2021.
[48] Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner. Learning-basee support estimation in sublinear time. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[49] M. Gaboardi, H. W. Lim, R. M. Rogers, and S. P. Vadhan. Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing. In International Conference on Machine Learning, ICML, pages 21 2111-2120, 2016.
[50] M. Gaboardi and R. Rogers. Local private hypothesis testing: Chi-square tests. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, pages 1612-1621, 2018
[51] Oded Goldreich. The uniform distribution is complete with respect to testing identity to a fixed distribution. In Computational Complexity and Property Testing On the Interplay Between Randomness and Computation, pages 152-172. 2020.
[52] Oded Goldreich and Dana Ron. On Testing Expansion in Bounded- -eegree Graphs, pages 68-75. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
[53] Aravind Gollakota, Adam Klivans, and Pravesh K. Kothari. A moment-matching approach to testable learning and new characterization of rademacher complexity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023, pages 1657-1670, New York, NY, USA, 2023, Association for Computing Machinery.
[54] Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Tester- learners for halfspaces: Universal algorithms. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[55] Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. An efficient tester-learner for halfspaces. The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-1,, 2024, 2024.
14

---

[56] Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, and Huanyu Zhang. Locally private hypothesis selection. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 1785-1816. PMLR, 2020.
[57] Chen- Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning- frequency estimation algorithms. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[58] Piotr Indyk, Reut Levi, and Ronitt Rubinfeld. Approximating and testing k-histogram distribu- tions in sub-linear time. In PODS, pages 15 22, 2012.
[59] Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning bearning-based low-rank approximations. In Advances in Neural Information Processing Systems, pages 7400-7410, 2019.
[60] Tanqiu Jiang. Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff. data stream algorithms. In International Conference on Learning Representations, 2020.
[61] Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Learning intersections of halfspaces with distribution shift: Improved algorithms and SQ lower bounds. In The Thirty Seventh Annual Conference on Learning Theory, June 30 July 3, 2023, Edmonton, Canada, Proceedings of Machine Learning Research. PMLR, 2024.
[62] Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Testable learning with distribution shift. In The Thirty Seventh Annuul Conference on Learning Theory, June 30 July 3, 2023, Edmonton, Canada, Proceedings of Machine Learning Research. PMLR, 2024.
[63] Reut Levi, Dana Ron, and Ronitt Rubinfeld. Testing properties of collections of distributions. Theory of Computing, 9())2995-344 -477 2013.
[64] Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, and David Woodruff. Learning the positions in countsketch. In Ith International Conference on Learning Representations, ICLR, 2023.
[65] Shyam Narayanan. Private high- ligh-dimessoonal hypothesis testing. In Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 3979-4027. PMLR, 2022.
[66] Jerzy Neyman and Egon S. Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical or Physical Character, 23 (616669770)
1933.
[67] Krzysztof Onak and Xiaorui Sun. Probabilit-rreveainng samples. In International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Reseurch, pages 2018-2026 PMLR, 2018.
[68] Aadil Oufkir, Omar Fawzi, Nicolas Flammarion, and Aurélien Garivier. Sequential algorithms for testing closeness of distributions. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 11655-11664, 2021.
[69] Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Trans. Inf. Theory, 54(10):4550-47555 2008
[70] Sampriti Roy and Yadu Vasudev. Testing properties of distributions in the streaming model. In 34th International Symposium on Algorithms and Computation, ISAAC 2023, December 3-6, 2023, Kyoto, Japan, volume 283 of LIPles, pages 56:1-56:17, 2023.
[71] Ronitt Rubinfeld and Arsen Vasilyan. Testing distributional assumptions of learning algorithms. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1643-1656, New York, NY, USA, 2023. Association for Computing Machinery.
[72] O. Sheffet. Locally private hypothesis testing. In Proceedings of the 35th International Conference Machine Learning, ICML 2018, pages 4612-4621, 2018.
15

---

[73] Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, and Seyed Mehran Kazemi. Kwikbucks: Correlation clustering with cheap-weak and expensive- strong signals. In The Eleventh International Conference Learning Representations, 2023.
[74] Alistair Stewart, Ilias Diakonikolas, and Clément L. Canonne. Testing for families of distribu- tions via the Fourier transform. In NeurIPS, pages 10084-10095, 2018.
[75] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour, Near-optimal- sample estimators for spherical gaussian mixtures. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, 2014.
[76] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. SICOMP, 46(1))429944555 2017.
[77] Gregory Valiant and Paul Valiant. Estimating the unseen: Improved estimators for entropy and other properties. J. ACM, 64(6):37:1137:41, 2017.
[78] Paul Valiant. Testing symmetric properties of distributions. SIAM J. Comput., 40(6):197--168,, 2011.
16

---

A Other related works
General property testing of distributions: Testing properties of distributions has been extensively studied over the past few decades. Distribution testing under computational constraints has also been explored in [37, 70]. Hypothesis testing (and hypothesis selection) have received significant interest within the privacy community in machine learning [49, 21, 10, 4, 50, 72, 26, 27, 65]. Examples of other distributional properties that have been examined include testing monotonicity [20, 22, 11], testing histograms [24, 23], testing junta-ness [7,32] 32], and testing under structural properties [17, 58,
35, 44, 43].
Connections to tolerant testing: Tolerant testing asks us estimate the true TV distance between a known distribution and another which we only have sample access to, up to small additive error. Readers familiar with strong lower bounds in tolerant testing (see e.g.. [78, 77, 25] where it's shown that (nn/ lo)(n)) samples are needed in the case where the known distribution is uniform, compared to only ((yn) samples needed for uniformity testing) might find our results surprising. It incorrect to conclude that our algorithm in Section B, i.e. the search component (which is adaptive to the distance between á and p), can perform tolerant testing between p and p. In reality, the algorithm finds an which allows the testing component to terminate (either with accept reject). Thus, while we know that the a found by our algorithm is never larger than ||p - pllTv, it could in fact be much lower than l|p pl|TV, meaning the found by the search algorithm not good estimate for [p- - pllTV.
Testable learning: Our framework bears some resemblance to testable learning as introduced in [71]. In this framework, the focus on designing learning algorithms that can check whether the required underlying assumptions hold. If the assumptions do not hold, the algorithm may forego solving the problem. However, if chooses to solve the problem, it must do so accurately, regardless of whether the assumptions hold. This is similar to our notion of testing with suggested accuracy level, where the algorithm can either forego solving the problem if the assumption does not hold solve it accurately regardless. Some examples of results in this framework are presented in [53, 54, 41, 55, 62, 61].
Algorithms with predictions: Recently, there has been a burgeoning interesting in augmenting classical algorithm design with learned information. Most relevant to us are works which study augmene- algorithms under sublinear constraints, such as memory or sample complexity [57, 59, 60, 33, 47, 48, 31, 64, 73, 2]. We refer to the interested reader to the website https: //algorithmn whagsrrttttttto wiseewwiiil with trith-predi wewpppreiiiinoo cosiostiins..i.m woons.githee github. io/ for up-to-date collection of literature on learning-augmented algorithms.
B Searching for the appropriate accuracy level
Early on, we defined the augmented tester for testing identity, uniformity, and closeness. We generalize this concept for other properties of distributions. More formally, property P is set of distributions, and we say a distribution has property P iff it is in P. The goal is to distinguish whether unknown distribution p is in P, or it is far from all distributions that have the property. Similar to Definition 1.1, we define the notion of an augmented tester for P as follows:
Definition B.1. Suppose we are given three parameters, a E [0, e E (0, 1), 8 E (0. 1). Assume A is an algorithm that receives all these parameters, and the description of known distribution Po as input, and it has sample access to an unknown underlying distribution We say algorithm A is an (a, e, - auggmettdd tester for property P for every p. g, and p over [n]:
if and p are a-close in total variation distance, the algorithm outputs inaccurate informa- tion with probability at most 8/2.
If PP then the algorithm outputs reject with a probability at most 5/2.
p from every member P, then the algorithm outputs accept with a probability at most 8/2.
17

---

With this definition in mind, suppose we have augmented tester for a property P. Our goal is to find an appropriate a such that the augmented tester solves the problem: it outputs accept or reject, but also, it does not use too many samples. In this section, we introduce a search algorithm that seeks to find this appropriate a. It important to note that the a identified by our algorithm may not necessarily match the true accuracy level of the prediction, i.e., llp pl/ Instead, it corresponds to the minimum number of samples that the augmented tester can solve the problem.
Our search algorithm runs in rounds, each set by sample budget that increases as the process progresses. In round i, the algorithm determines an appropriate value for a; and invokes the augmented tester, namely A. with this chosen a; The value of a; is selected such that the augmented tester operates within the sample budget allocated for that round. If the tester outputs accept or reject, the search algorithm replicates this response. However, if the tester returns inaccurate information, we double the sample budget and proceed the next round. The pseudocode for this procedure provided in Algorithm 2. In the following theorem, we prove its performance.
Algorithm An augmented property tester without knowledge of a
1:
procedure AUGMENTED--EETTEE -ITHR---IT---- WITT--SARCH(C, 8', description of function f. algorithm .A)
2: 8min 10,1) fla 1/3)
5max f- m [0.1] f(a, 1/3)
t
log2
Smax Emit
5:
t+
8'
F41
6:
for
= 0, f-1 ( Smin)
-0. do
8:
O + the output of A with suggested accuracy level a; and confidence parameter 8
i (accept, reject} then
10:
return O
11:
Run the standard tester (without any prediction) with confidence parameter d and return the answer.
Theorem Fix a parameter 8 < 1/2. Suppose A is an (a, e, 8) auggmented tester for property that receives a suggested accuracy level a and confidence parameter 8. Let f (0, [0, N be non-decreasing function for which A uses fa o)²² samples when it is invoked with parameter a and aims for the confidence parameter 5. Algorithm 2 is a (", d''d-ma-eeetedd tester, without knowledge of a, for property P where
8' 8 8. 11
log maxae [(a) [(a))(()
minag((,11 f(a)) )
In addition, a" is the true accuracy level, then Algorithm 2 uses O({(a)) samples in expectation.
Proof. First, we define the notation we use in this proof. Let Smin and 8max represent the smallest and largest sample sizes used by A, respectively. 8min may be one higher, and smax is the sample size when the prediction did not make any improvements (the sample complexity of a standard tester). Let L log2 (Smax/8mml 8min). ). The algorithms runs in L + rounds i (0, .......),, (). In round < L, our sample budget is 2' 8min- We run the algorithm with a parameter o; ensuring the sample complexity of A remains at most 2:-1. Smin samples. In cases where multiple a values satisfy this criterion, we select the largest. We use (abuse in fact) the inverse function notation, defining as a; = f- (2' smin). If A finds an answer (accept or reject), we return the answer, Otherwise, we proceed to the next round. In round i = 4, where we have 8max RJ 8min samples, we run the
standard tester and return its answer.
Now, we focus on proof of correctness. Note that (may) call A / times and the standard tester time. Each of these tester works with probability at least 1 - 8. Thus, by the union bound, we can assume that they return the correct answer with probability least 1 8' where 8' 6/(t 1). As we have noted in Definition 1.1, A is resilient to inaccuracies, implying that even if the suggested accuracy level not valid, if the tester does not output false accept reject with probability more than 8/2. The same statement is correct for the standard tester. Now, our algorithm here replicates the
Here, omit the dependence to other non- non-varying parameters such as and
18

---

On the other hand, the probability that algorithms end round i 1' cannot be too high. If the algorithm ends at round or later, it means that A in rounds i", i" + I,...,, must have returned inaccurate information. However, given assumption, the true accuracy is not worse than de which makes outputting inaccurate information wrong. And, this event does not happen in each output that is produced by one of the testers. Thus. if they all of them outputs the correct answer, our algorithm outputs the correct answer as well. And, this event happens with probability at least 8'.
Next, we focus on the analysis of the sample complexity of this algorithm. Let a" be the true prediction aceuracy, and let i" be the first round where o; 2 a". Recall that assume that oş is the largest such that f(a)) S 2' Smin- In addition, we assume that f is non-decreasing. Thus, we have":
2
8min < <((a)) S [(az=) 2 8min
If the algorithm ends at round i, we have used the following number of samples:
samples for the first i rounds
Σ 2 Smin S 22 Smin
j=0
(4)
S 2 (2--1,
smmn) < 22 f(a").
round with probability more than 8/2 for each round independently. Let fend indicate a random variable that indicates the index of the round for which the algorithms ends. Thus, we have for every 2 it:
8 i-s" 2
Pr[ 2 i]
(5)
Now, we are ready to bound the expected value of the number of samples we use. Let denote the number of samples use. Then, we have:
E[S] _ E(S Lend = i] Pr[ = i]
1=0
<4f(a")
2-- Pr[lend = i]
(by Eq. (4))
1=0
1-
$4f(a")
Pr Pr[ lnn i] + Σ
1
Σ
2
Pr Pri! =i]
i=0
i=1+11
コ=
i-s'-1 -1
= =4f(a*)
Σ
Pr[ Tend = 1] +
Σ
Σ
Pr Tend = i]
1=0
i=
1=0
"Without loss of generality assume, f(a-1) 0.
19

---

Next, we write the second sum in terms of new variable it ===--" 1. Then, we swap the order of the summations on k and j:
E[S] <4f(a")
1+
Σ
2
Pr[ =
k=0
3=0
t-2"-1
(-
$4f(a")
1+
Σ
Pr[los=k+i+1]]
1=
1-
$4f(a))
1+
Σ
2
Pr(
end 25+ +11
1=0
1-1-11 1
8 j+1
s4s(a))
Σ
2
(by Eq. (5))
2
<6ʃ(a)).
(assuming ó < 1/2)
C Iddentit and uniformity testing
In this section, we focus on the problem of identity testing, which involves testing the equality between a known distribution q and an unknown distribution Specifically, our goal is to determine whether p = q or if they are e-far from each other. In an augmented setting, we are provided with another known distribution P. predicted to represent along with a suggested level of accuracy a. Surprisingly, our findings indicate that the sample complexity for this problem influenced by a new parameter: the total variation distance between q and p, denoted by d. In particular, we have the following theorem:
Theorem 7. Fix arbitrary parameters E (0, 1] and E [0, 1). Algoritlum 3 is an (a, 0.1)-
augmented tester for identity that uses the following number of samples s, where:
O min
(T-aaz
))
(T
i
and d refers to pl.vv. For any E 0, and e E [0, 1/2), we show the same number of samples is necessary for any (a, 6, (0/d=223))agmee -augmeneed identity tester. In fact, the lower bound holds even when q is uniform distribution over [n].
The proof of this theorem follows from Proposition C.I, Proposition C.2, and Proposition C.3.
Remark 8. A particular instance of this problem is uniformity testing, where q is uniform distri- bution over [n]. In Theorem 7, our upper bound applies to any arbitrary g. Furthermore, our tight lower bound is based on a hard instance, where is uniform distribution. These results establish optimal upper and lower bounds for both identity testing and uniformity testing simultaneously.
C.1 Upper bound for identity testing
Our upper bound relies on fundamental observation regarding the total variation distance: this distance is the maximum discrepancy between the probability masses that two distributions assign any subset of their domain. Demonstrating a small total variation distance between two distributions entails proving that the discrepancy across every domain subset minimal. contrast, to prove a large total variation distance, one only needs to identify single subset with significant discrepancy. We employ the Scheffé set of P and defeiid as the set of elements denoted by S-to serve as witness for the farness of from either p. It is known that S maximizing the discrepancy between the probability masses of p and q. implying:
[m] where p(x) < ((x).
d lq QlTV Iq(S) ((S)
20

---

In scenarios where the distance d >> accurately estimating the probability of S according to with an accuracy of (d-aa (d-=)/44 provides a basis for distinguishing the fareess from either q or p. If the probability masses assigned to S by q and differ by more than (d ax) /4, it clearly indicates that p is not identical q, leading to outputting reject. Conversely, if the estimated probability of p(S) is close to g(S),, then the discrepancy between p(S) and p(S) must exceed a, leading to outputting inaccurate information. The pseudocode of our algorithm presented Algorithm 3. We prove the performance of our algorithm in the following proposition:
Proposition C.1. Fix two arbitrary parameters e E (0.1) and a E [0, Algorithm 3 is an (a,c,ō 0.1)-augmented tester for identity that uses the following number of samples 8, where:
y
if a
(min (d-apa
idd
and d refers |1q pllz..
Algorithm An augmented tester for testing identity of and with a suggested value a a, 6, = 0.1, T P. sample access to p)
1: procedure AUGAENNTED-DDENTTYYTTTSTTT
2: d + ||g TlT
3: if dl S a or T--of
then
4:
return the standard testers answer.
S Scheffé set p and q
D [m] is in the Scheffé set S iff f(x) < ((x).
Draw m = 0 (d-o)² samples from p
7:
fraction of samples that are in S if (n) al > d-a then
8:
return reject.
10:
else
11:
return inaccurate information.
The proof of theorem is trivial the setting where S and [d-a)= >> v 5 In these cases, we use the standard tester for identity testing (e.g., [76, 30, 5]) with = 6/2 = 0.05. Clearly, a wrong answer was produced with probability less than 8/2. is known that these tester only use O(yn/e²) samples.
Proof.
Now, suppose d probability of the Scheffé set of q and p. S, up to error (d - ax)4 with probability 0.95 using O(1((d 2)) samples. We refer to this estimate a, and we have with probability 0.95:
Simple application of Chernoff's bound shows that
estimate the
d-a
- P-S(S) 4
(6)
Note that if p = 9. then
= 110--ppp d a
aa =
Hence, do not output reject with probability more than 0.05 5/2. On the other hand, assume pp - pllTv S a, then we show it is unlikely for us to output inaccurate information.
> - pVTTV > lo()) - ((S)
z IØ(S) - ((S) - (p(S)) - ((S)
(by triangle inequality) (by definition of Scheffé set)
||g -- - -lp(S) ((S) = dp-(p(S) q(S)
d a
la -(()] - - ((S) 2 dd
lla ((S)
4
(by triangle inequality and Eq. (6)
Therefore, we obtain that with probability 0.95:
3 (d a)
10 (--((S) >
4
21

---

Hence, we do not output inaccurate information with probability more than 0.05 6/2. Hence, Algorithm 3 is an (a, e, 6 aagumngee tester for identity. The sample complexity of the algorithm, in the case where d and (d-a)² I v complete.
2 is O(1((d - aa)). Thus, the proof is
C.2 Lower bound for uniformity testing when
In this section, we focus on the case where a 2 d. We observed for this problem the number of samples depends
additional parameter: the distance between y and p. If this distance most a then prediction does not help the algorithm. The algorithm would still be required to draw Q(n/e* samples (which is the sufficient amount of sample for the standard case). Our proof is based on a reduction from standard identity testing to the augmented version of this problem which establishes the desired lower bound.
Proposition C.2. Suppose we are given two known distributions q and D. and unknown distribution over [n]. Let d == 1|g - pllrv. For any a in [0, 1}. if a 2 d, then any (ar, e, = 2 -uugeeted tester requires Qi (n/r)) samples.
Proof. We prove that standard identity lesting can be reduced to augmented version this problem if 2 d. For the standard tester,
given a known distribution q and unknown distribution p. Let & be any arbitrary distribution that is in distance d from q. Consider .A as an (a, e, = 2/3)- augmented tester. The procedure for the standard tester is straightforward: Run A p, P. and q. If it returns accept, we also return accept; if returns reject or inaccurate information, we return reject.
reject inaccurate information
accept
reject
Figure A diagram indicating the valid answer for the augmented tester based on the total variation distances of from y and ý assuming d S a. The standard tester requires to output accept if p = q, the green dot, and reject if ||p rl 2 e, the red shaded region, with high probability, In addition, the augmented tester may output inaccurate information for when || gllrv and |pp - TT 2 a.
We show that the augmented tester distinguishes between the cases where = and ||p - qllrv > e. See Figure 2. More precisely, Note that if q. then p is within distance of p. Thus, the only valid answer AA in this case is accept. In this case, according to Definition 1.1, A returns reject and inaccurate information each with probability of at most 8/2 1/6. Therefore, by the union bound, we return accept with probability of at least 2/3. When and q are c-far from each other, A returns accept with probability of at most 6/2 1/6. Consequently, output the correct answer with a probability greater than 2/3.
This reduction indicates that A must use at least many samples as required for identity testing. Considering the existing lower bound for uniformity testing (where g is uniform distribution over [n]),, augmented identity testing necessitates Ol ((vn/²²) samples [69].
22

---

C.3 Lower bound for uniformity testing when a < d
In this section, we consider the lower bound for the uniformity testing problem in the setting where a < d. On the other hand, if d - a is not too small, the required lower bound is only 22(1/(d a)²). Otherwise, ((Vr/ () samples needed (as it required for the standard tester).
At a high level, our proof consists of the following steps. First, we construct three distributions that look similar when draw too few samples. We formalize the similarity of these three distributions using a multivariate coupling argument. Next, we describe valid answers for each of the distributions. The main message of this part is that there no possible answer that valid for all three distributions. Now, (similar to Le Cam's 's method), suppose we feed the algorithm with samples from one of these three distributions (each with probability 1/3). For any sample set, the algorithm outputs an answer (which may be randomized), however, this answer is considered as wrong for at least one of the underlying distributions. This is due to the fact that there no universally valid answer that is simultancously correct for all three distributions, Hence, if the algorithm outputs a valid answer with high probability, it must be able to distinguish the underlying distributions to some degree. On the other hand, the indistinguishably result says, it is impossible to tell these distributions apart. Thus, we reach contradiction. And, the lower bound concluded. More formally, we have the following proposition:
Proposition C.3. Suppose we are given two known distributions and p. and an unknown distribution p over [n]. Let d == l19 pllTV. For any a E [0. 1], CE [o, 1/2), and d E [0, 1/2], if d > a any ca,c,8 = 2/3)-augmented algorithm for testing identity of p and q with prediction p requires y samples.
= Ω min
Proof. Without loss of generality, assume - a S 0.4. Otherwise, we are required to establish a lower bound of ((1), which is necessary for any non-trivial testing problem. 5 As we have discussed it early, we prove this proposition in the following steps:
Construction of distributions: We assume q Un is uniform distribution over [n]. Without loss of generality assume n is even. Otherwise, we can set the probability of one of the elements in all the distributions to zero. We define the prediction distribution follows for every i [n]]
2d i even;
Y1
2d i is odd.
It is not hard to assert that |1 - Un|/TV is d satisfying the assumption we had in the statement of the proposition. Next, we construct two distributions p² and pº.
Suppose we have random vector Z in [-1,+1} where each coordinate Z; is one with probability 1/2 independently. Now, we define the following distributions over [n]:
Z:/2 E
i is even;
pf =
(7)
2 (141)/2
i odd.
n
1 + 2 (d - -a)
i is even;
pt
n
(8)
1 2 (d a))
i is odd.
It is not hard to see that the probabilities of each distributions sum up to one by observing the probability of two consecutive elements is 2/n.
*As long as the problem does not have determeerdded answer that works for all distributions, one must draw at least one sample.
23

---

Indistinguishably of the distributions Fix the number of samples s, and let SIp denote random variable that is a sample set of size s drawn from p. We show that S Slpe. and p are three random variables with small total variation distances between each pair. These distances are small that it is practically impossible for the algorithm tell them apart. We formalized this by providing a multivariate coupling between these random variables. We extend Le Cam's is method for three random variables, and show that no algorithm with low error probability exists unless s large, establishing the desired lower bound for the problem.
Lemma C.A. Suppose we are given the following parameters e, d, a, n, and Assume d S 0.4. Let Un denote the uniform distribution over [m], and let p" and pº be the distributions defined in Equation (7) and Equation (8). Let Sw., Sipe and Si yr be three random variables that are sample sets of size s from each of these distributions. If S min
[0000005 0.004 ). then there exists a [d-o]=2
distribution over triples of three sample sets of size (that is ([n]*)²), which we call a multivariate coupling C. between S Un Slp,, and Sip such that:
The marginals of C correspond to the three probability distributions U@ 88 p S
and p S8.
More precisely, for a sample (S1, S2 S3) drawn from C, and every S E [n] we have:
Pr(s..S..s.-c(55 Si S] Pro UR
[S S]
P S2 = 5] Prs rop
Spp 5]
Pr( S3 = S] prop 80
S = S]
Pros..s.. = 52 Sz] 0.98.
For the proof, see Section C. This lemma states that when the number of samples is small, the sample sets looks very similar in all three cases: Un. = p., and p = p".
cannot output reject
d
q
n
cannot output
inaccurate information
cannot output accept
Figure 3: A diagram indicating the invalid answer for the three distributions Un. p", and pº.
Valid answers for each distributions: We focus the valid output of the algorithm in these three cases using the Definition 1.1. According to this definition, we have:
If p = q. then reject is not valid answer.
If [|p allrv > c, then accept is not valid answer.
If [|p 6 TV < then inaccurate information is not considered valid answer.
24

---

We denote the set of valid output for each case by Vpp- An accurate augmented tester with confidence parameter has to output an answer in Vi with probability least 6.
1. p = Un In this case we have
Un. Clearly, in this case, reject is not a valid answer:
reject & Viu..
p p=p": The total variation distance between y = Un and yd is 6. Thus, accept not considered valid output:
accept & Vpp
p p=p² pp It is not hard to see that 1pp -V a. Thus, inaccurate information is a valid answer:
inaccurate information $ Vip.
The diagram of the invalid outputs is shown in Figure 3 for an instance of these distributions. Let us explain what these valid sets are implying. The intersection of the three valid sets is empty. because among all possible outputs each set lacks at least one of them
Vi8, n 1pp p- 0.
Therefore, there is no possible output that is considered valid on all the three distributions And, since these distributions are indistinguishable with high probability, no algorithm should perform well under all three possibilities.
Deriving a contradiction. Our proof is via contradiction. Suppose there exists an (a, 6,, augmented tester, called A, for uniformity testing that uses s samples.
3 (1 8) < Prspu UU [A(S Viu.] Prs ~p* [A(S Vip=] + pr [A(S E Vipa)
Let I represent the internal coin tosses of the algorithm. Since the probability of AA outputting an invalid answer is bounded by 6, we have:
8 2 Pr,, Sien ~ [A(S & Viv.] E
S|u, ~ Prr [((SU,)) E Viv.]] ]]
Es. ~UR
Prr [((S reject]] Es Pry reject]
2 E. (r: = reject] Si = S2 = Sa] Sr. Si = S2 = Sa] (by law total expectation)
We can write the above equation for p" and and sum of them up. Thus, obtain:
8 2 Pr((s.ss..))-C(S5 = S2 = =Sa] E (e.ss,,)--(Prr((ACC reject] + Pr,((A(ss) = accept]
3
+ Prr(A((ss) inaccurate information] Si = S2 [Sa]
Pr.S......) = S Sz].
For the last line above, note that when S1 S2 Sz, the terms inside the expectations the sum of probabilities all possible outputs for A. Hence, the sum of these probabilities is one.
Recall that earlier, we assumed that 8 = 0.3, and using the properties of the coupling, we know that S S2 = Sa with probability at least 0.98. Thus, we get:
0.98
0 = 62 Pr(s..S...)ccSS. = S2 S,=S,] 2 > 0.32.
3
Hence, reach contradiction. Thus, such algorithm like A exists.
'It worth noting that pair of valid sets may have some overlap. That is. the algorithm can output an answer that is correct for both of the distributions. In other words, technically the algorithm does not have distinguish any pair of these distributions long there is valid answer which works for both of them.
25

---

C.3.1 Multivariate coupling between the three hard distributions
In this section, we prove the lemma on coupling that we used to prove our lower bound. This lemma implies indistingusshabiity between Siu,, Sip=, and Slpe. For a definition and some basics on coupling, see Section F.3.
Lemma C.4. Suppose we are given the following parameters E, d, a, n, and s. Assume d - a S 0.4. Let Un denote the uniform distribution over [n], and let pd and p² be the distributions defined in Equation (7) and Equation (8). Let Siu., Sipe, and Sipe be three random variables that are sample sets of size s from each of these distributions. If S minn
(0.00005 0.004 v'm ). then there exists a (d-aa²)
distribution over triples of three sample sets of size (that is ([n]*)"), which we call a multivariate coupling C. between S U,,' Sipe and pip= such that:
The marginals of C correspond to the three probability distributions U p= St and p S*.
More precisely, for a sample (S1, S2, Sg) drawn from C, and every S E [n]] we have:
Pr(ss.s,.so)~c(55 [S| S] Prsju ~
[S =S]
Pr(s..s..s) S2 = S] = Prs I up の0
Sppp = 5]
Pr(s,.s,,s)vel (Sa S] Prsporpoo 60 1lp0 5]
St = 52 55=5 1 0.98.
Proof. We start by bounding the total variation distance between two pairs of distributions: ||
llv, and ||US* @
In [69], the author has shown that the total variation distance between Siu, and Sn is bounded by:
x2
(2,)4 n
exp
ITV
S 0.01.
(9)
The last inequality above comes from our assumption that s
0.004
Next, we focus on the total variation distance between Sipe and Sig.. Note that pd is a distribution that has some bias towards the even elements, but it is uniform on both sets of odd and even elements. Therefore, to bound the total variation distance between US* and p t0s we use similar argument for showing lower bound of 1211 /// )2 distinguish whether coin is fair or it has a bias of (1 A)2 Below is our formal argument.
It is not hard to see that one can the following process to generate sample from pº. First, we draw a sample X ~ Ber + (d - a)) from the Bernoulli distribution with a success probability 1/2+ (d - a). If X 1, we pick an even element (uniformly); Otherwise, we pick odd element. Similarly, we can draw samples from a uniform distribution as follows: draw X' ~ Ber(1/2) from the Bernoulli distribution with success probability 1/2. If X' = 1, we pick even element (uniformly); Otherwise, we pick an odd element. One can view this process of generating a sample in [n]] from binary variable (X or X') channel. The data processing inequality says that the distance (more precisely any f-divergences) between two random variables does not increases after they pass through a channel. Hence, we use this fact and bound the total variation distance between p th and USa
I -
| S
V 2
KT. (U (US8)))08))
(by Pinsker's inequality)
KLL (U,
(since samples are drawn i.i.d.)
KL (Ber(1/2) Ber + (d a))).
2
(by data processing incquality) (when 2 (d - a) S 0.8)
I /28 s. (d a)
26

---

Since we had this assumption where s is at most 0.00005
(d-a)2 we get.
1 0 TT S 22 (d - 5.01 0.01
(10)
So far, have shown that || p x I|VV and | - Tl are at most 0.01. Using the coupling lemma (See Fact F.3), there exist two maximal couplings C' and C between the following pairs of distributions: (Un,, pd x*) and (U%,, po The properties of these maximal couplings are:
The marginals of the couplings are equal to the two pairs of probability distributions. That is:
Ci U and C
C. U and C² p p0
S [S] S²] 2 0.99, and Pr.s [S] = S2] 2 0.99.
For every S e [n] let Sis be probability distribution over [n]] m. The probability of S' according to C2S is:
s = (
S S5
S].
With these definitions in mind, we create our multivariate coupling C by essentially joining the two couplings C and C The following randomized procedure produces a random sample S2, Sz) from C:
1. Let (2) be sample from C*.
2. Let S3 be sample from C2ss,
Output (S1, S2, S3) as a sample from
Given the definition of C*, clear that the first two marginals of C are exactly U@** and p 0* To see that the third marginal of is equal to p", we have the following for every S E [n]
Pr[S3 S')
Σ
Pr(s Pr(s(,s))~=115) = Si] C2s,
S1E(n]m m
Σ
Pr S0 = S1] Pr co = S'1S" = Si]
SyE(n] m
Σ
= S1] Pr sp 1 = S'1S Si]
S,Eln] p
Σ
CO CG
STE(n]
Now, we show that SI, S2, and S3 are equal with high probability. This stems from the fact that C* and Co were maximal couplings, and with high probability, the pairs drawn from them equal. More formally, via the union bound, we have:
S. S2, Sz] 1 Prcs T... S. + S2] S. + Sa]
Pr(s).S.. S1 Sz] Pr(si.sa>~ [S] # Sz]
Σ P S and S3 $] Pr Pr.ssS))-C*SS Sz]
SE|nJm
Σ CS(S.))
Pr(s ( + Sz]
SEIN]
(With similar argument as above) Pr((s,S))-Ct Sz] - Pr(s, Sz]
0.99 (1 0.99) = 0.98.
(by Eq. 9 and Eq. 10)
27

---

Hence, the proof is complete.
D Augmented closeness testing
In this section, focus the problem of closeness testing in the augmented setting. More formally, we have the following theorem.
Theorem 9. For every a and in 1), there exists an algorithm for augmented closeness testing that uses ② algorithm for this task is required to use 12
2/3 678
Vn e²
samples and succeeds with probability at least 2/3. addition, any samples.
For the proof of the upper bound see section And, for the proof of lower bound see section D.I.
D.1 Lower bound for closeness testing
In this section, prove lower bound for augmented closeness testing where a known distribution ý is provided satisfying [pp - pl = a. We have the following theorem.
Theorem 10. Suppose we are given a and (0,1), 1). Any (a, 6, = 11/24))augmentee tester for closeness testing of distributions over [ni] uses even when a is provided to the algorithm.
n 2/3
+
samples. The lower bound holds
4/3
Proof. The O( ( term comes from the existing lower bound for uniformity testing since reduce uniformity testing to augmented closeness testing as follows: Suppose we wish to test whether distribution q over [n] is uniform e-far from uniform. Suppose A is an (a, e, aaggmeeeed closeness tester. Set p to be the uniform distribution over [m)] Let ş be any distribution that is o-far from uniform. For instance,
half of the elements and (1 an on the other half. Since A is an augmented tester, can be used to distinguish whether p p- q or 1p- g//Tv > e with probability 11/24.
be distribution that is (1 xx)
Upon receiving á and samples from p and q. if A returns inaccurate information or reject, we output reject; otherwise, we output accept. Given Definition 1.1, if is uniform, we will not output inaccurate information or reject with probability more than 11/24. And, if is e-far from the uniform distribution (equivalently p). will not output accept with probability more than 11/48. Hence, we have a tester with confidence parameter 11/ 48 for uniformity testing. Thus, s must be ((Vn/ 2), which is the number of samples required for uniformity testing [69].
To prove the lower bound of Ω (n2 //////3////))))////////////3))) 4/3) samples, we only need to focus on the case where 1/3 / e/3 O D(vn/62), making the lower bound trivial due the > (Vne2)-1. Otherwise, n
2(vn/e2) lower bound shown earlier. We consider the following cases depending on e:
Case 1: 6 < (vnc2)-1. Therefore, in this case, the interesting regime of parameter for is that a 2 c. We prove the lower bound for this case in Theorem 11 in Section D.1.1.
Case <> (Vne²)-1
this case, addition to considering the case where a 2 e, we also need study the case where a is in ((vRe?)-1 -t))) We prove the lower bound for this case in Theorem 12 in Section D.1.2.
This completes the proof.
D.1.1 Lower bound for a 2
Below, we provide a lower bound for augmented closeness testing when a e. At high level, Theorem 11 achieves this lower bound by creating a challenging instance. This involves embedding the difficult instances of the standard closeness testing problem into another distribution, spanning a domain of (n 1] elements, while concentrating the majority of the distribution's mass the last
28

---

element. The prediction, being a singleton distribution centered on the last element, does not facilitate solving the standard closeness testing problem, which embedded within the first 1] elements.
Theorem 11. Suppose we are given a and e in (0, 1). Assume we have two unknown distributions and q and known distribution p over the domain [n]. If a 2 then any (a, e, == 11 11/24)- augmented tester for testing closeness of p and q requires the following number of samples:
11
2/3
1/3
Vna
= S2
4/3
22
Proof. Our proof is based on reduction from standard closeness testing to augmented closeness testing. Assume there exists an algorithm, A, that upon receiving ý and samples from p and q, can distinguish whether p q or llp 4llrv 2 with probability 1 11/24. We show that this algorithm can then be used test closeness of two distributions, and q over 1] with proximity parameter é' := e/c.
Suppose have sample access to p and q. We construct p and q based on p and q as follows:
Vi E [n 1], E [n 11
Pn at
0:
4n a.
Note that given sample from P (respectively ①) we can generate a sample from p (respectively q) by outputting that sample with probability a and otherwise. Also, if p is equal to q. then p and g are equal. And, if || TV 2 e', then |pp g||Tv 2 e due to the following:
1p <||Tv
Σ p: al iE
Σ iE
P.
7 = a 15- লl/TV.
Let ý be the singleton distribution on (i.e., Pn. 1). In this case, |p - pllTV equals a. We feed A with p and samples from and q. Now, if A outputs p is ffar from q. Given our construction, this answer is true with probability 11/24.
we declare p - ÿ. Otherwise, we declare
Note that in this process, in expectation, we draw as samples from P and q. Thus, using Markov's s inequality, the probability of drawing more than 100 samples from each of p and 9 is at most 0.01. Hence, using A, there exists an algorithm for testing closeness of ç and q with probability 1- /1 0.01) 0.53 that uses a samples from ý and Using the existing lower bound for the closeness testing problem (see Theorem 4 in [69] and Proposition 4.1 in [30]), we have:
(
11/33 Vn 44/3
1/3 a 4/3
Vnaaa
100 Ω
c²2
4/3
Thus, by dividing by 100a, get the following bound as desired:
( 2/3
1/3
Vnw
=
4/3
+
22
D.1.2 Lower bound for a in (c.
.c)
We extend the existing lower bound for closeness testing to the augmented setting. In the standard setting, the lower bound for closeness testing is derived from the hard instances for uniformity testing with one key adjustment: introducing elements with large probability (x 2/3) in the distributions. These large elements share identical probability masses in both p and q. indicating that they do not contribute to the distance between the distributions. However, their presence in the sample set confuses the algorithm: Because of their large probabilities, their behaviour the sample set may be deceivingly hint "not uniform". making it difficult for the algorithm to decide whether the rest of the distributions are uniform not. Therefore, the algorithm needs zs 2/3 samples first identify these large elements, and then it can test the uniformity on the rest of the distributions. The surprising part about this result that s 2/3 is much larger than the /ni samples which suffice for testing uniformity.
29

---

The challenge in our case is that may give away the large elements to the algorithm. Hence, to prove the lower bound, we create hard instances by adding as many large elements as possible, without changing P by limiting the overall probability mass of the large elements to a.
Here is instance: assume ÿ is the uniform distribution; p assigns (1 -1-a)/n probability mass O(n) elements chosen at random, and assigns n-23 probability mass
.n many elements in the domain. Now, has two options. Half the time, is equal to p. The other half, q shares the same large elements, but it is not quite uniform the of the distributions. In particular, assigns probabilities (1 + (1))) - a)/n. n. to the chosen ( elements randomly, making it e-far from p. Using this construction, we use result of Valiant [78] to show that these two cases are indistinguishable unless draw 2/n samples. More precisely, we have the following theorem:
Theorem 12. Suppose we are given the following parameters: a positive integer n, c E (0, 1/6), and a ((vne²)=1 (with this implicit assumption that ( (ynee)-1 less than c). There exists a distribution and family of pairs of distribution p and q such that any augmented algorithm for closeness testing must use
2/3
1/33
Ω
4/3
samples.
Proof. Let k be an integer that is at most
2/2 1/3
Ck
(1I)
E t/3
for a sufficiently small absolute constant C which we determine later. Assume we have samples from p and q that are available to the algorithm. We show that there are two (families of) distribu- tions that any augmented tester has to distinguish them with high probability. However, they are theoottll indistinguishable using only k samples.
Setting up parameters: First, focus determining series of parameters which use in our proof. We define l as follows:
n2 2/3 4/3
==
1/3
1 no
2/a3
44/3
mod 2)
(12)
not hard to see that is an integer. For our proof, we require that and n are either both even or both odd. Here, the role of the indicator variable is to reduce E by one in case they are not. Also, E is positive, since due to the range of a and e, we have:
2/3 4/3
2/3
4/3
1
6^ 2
2 2/3
2 2/33
VTEEZ
2c
Given this definition, there exists an absolute constant G2 0.5, such that f = ce n/233 //3 ///3//4// We use this identity as the definition of É throughout this proof. Given the assumption about the range of a, we also have:
Cj . a/2 4/3
< <
2/3 <
n -
(13)
A/3
Let L denote a set of l random elements in [n]] to our large elements. L = [n]] L denotes the set of small elements. Since n and are either both even or both odd, has even number of elements. Now, partition L. to two random subset of the same size In and Lz. Set e' = 6 < 1. Set
C
C == min
5080320 ce' 2000'
2000
"Our parameters in this discussion precise. See proof for rigorous setting of parameters.
30

---

2
1/n
p
Aurge
Ammill
Ataga
(1+c)
Amaal
(1 e Amail
T Figure 4: A visualization of p. pt, and p
Constructing the distributions: We set be uniform distribution over [n]. That is, Pr 1/n for every [n]. We construct two distributions pt and as follows. For every E [n]. the probability mass of i according to these distributions follows:
a
i L
l
1
- +
iEL
n1
(1+ (1+E))
i i L
p
P =
1 a
n
n
iEL
n-
(1
(1 (1-c)
i ie Lz
n
For a visual representation of these distributions, refer to Figure 4. It is not hard to verify that the probability masses sum up one since LL| = l, and [T] = f. Also, these probabilities are non-negative due Equation (13) and the fact that a e 1/6:
a 0.
n/2
Also, given these definitions, p* is a-close to P. and pt and p are e-far from each other:
1
11
pllTV
a
2
n1
iEL
i3L
1p+ 1 1|V
Σ IET
1
a
e'
11 1-
1 2
2
2
2
2
Proof of indistinguishabiity::
Now, consider two pairs of distributions (p p+ . p+) and
(p = p= - = -- Given the distances above any algorithm for augmented closeness testing should output accept on ; and reject on (p* p- ). To establish our lower bound, we show these pairs of distributions are indistinguishable with high probability.
use the moment based indistinguishably result for symmetric properties of pairs of distributions in [78].
'A symmetric property of pair of distribution is property that does not change if we permute the domain elements of two distribution via the same permutation. The closeness testing of p and in context
31

---

Before stating their theorem, we need to define the notion of the (k, k--- moments of a pair distributions (p: 9) as follows:
Definition D.1 ((k, k--based moments). For every positive integer & the (k, bb--bsedd moments of a pair of distributions p and q are the following values:
M (p. = ka+b
pig
AE(m]
for every non-negative integers and b.
Fact D.2 (Adapted from [78]). Given an integer k. suppose we have four distributions, p') p,2). and g(2) over [n] where the maximum probability that each of them assigns to element less than 1/(1000 k). If
.90)
Mat (p .1th)))))) -Ma (0(2)g((1)
Σ 022
(14)
12 1 max (Mil (p(1), g(2)). Mal (p(2),(21)))
360
then no algorithm can distinguish the pair (p(), 1000)) from (pl2), (((2)) with a success probability more than 13/24 upon receiving Poi(k) samples from each distribution in the pair.
First, we verify that all the domain elements of pt and p- have probability masses 1/11000 k) according to both p* and p-. Recall that e < 1. Observe that it suffices to show that 1/n 1/(0000 k) and a/L 1/(2000 k). The first inequality holds due the fact that is (Vne") (/m=²)=2 e):
1/3
k
C n 2/3 1/3
1/3 <c. C (aE))
1
n e/3
Cl
(Vnc2}3
<a.
2000
And, the second inequality comes from the definitions of ki and ok:
4/3 c n2/3 a/3 et n2/3 1/3 ct k
A/3
2000 k
For the rest of this proof, we focus on showing Equation (14) for the pairs ip*.p*) and (p+.p* For simplicity in our equations, we use the following notation:
1
Aarge
Asmall
(15)
l
Using the Definition D.I, it is not hard to see that:
M(K) a,b (pt, ,p*) k0ts
Atage
a+b +
Σ
Asmall a+b
katb (e. Alarge
a+h + (n - E) Asmall a+b)
VeL
VEL
M00 (p= = katb
Σ
Atarge a+b + Σ (1+6')6
-amalll a-b +
Σ -')6 -emaall atb
VEL
sEI,
VEIz
atb + (n - E) Aumall atb (1 (1+ + - (000)++11100 (1-692)
katb
(. Atange
2
Therefore, get:
Ma (p+ .p*) ((() (pt.p") (n- Numan a-b (1 +1 (1+))++11-)) -1) -1).
2
symmetric property since permuting the labels of the elements does not change the distance between and Furthermore, is identical for every permutation of domain elements.
32

---

On the other hand, we have:
V 1 + max (Mel) (p()),(1)) Mib (pl)), .(2)))
2 katt l- Maage a+b
Using the equations above, we bound the right hand side of Equation (14):
kla+6)/2
Asmall a+b
(1+t)) + (1 c()
(1))) -1)
RHS of Eq. (14) S n
Σ a+h22
VL
1 1 (a+b)/2
2
Note that for = 0 or 1, the term in the sum is zero. Hence, we only need to iterate over all b 2 and Then, we can write the above equation the following form:
a 2 0. Let 7 denote /k/ Atagee
>small-
- Vi
Σ T
T (1
)
1
(T (1 e())
RHS of Eq. (14) S
2
2
622
2
2
To bound these terms, have the following lemma:
Lemma D.3. For x E R, we have
80
(1 + x)e"
and for x E 1.33, we have:
x²
+
3
x²
x
+
+3x
We start by splitting the terms corresponding to odd and even i's in the sum, and obtain the following:
Proof.
2i+1 (1+x)
2j (1+x)) e²
j!
j!
j!
The last equality above due to the Taylor expansion e + 1/1l 32/21 + about y 0.
Next, we have:
1= (et
(e)))((())) -1).
Now, if y S 1.79, then the following inequality holds: y ed - < y 3²2 Thus, for E (0, (.33,, we have:
22 (1+x) s (6- (1+2)
2 <22+243344
Now, assume ( +e)) S 1.33. We continue bounding the right hand side of Equation (14) via the above fact:
33

---

n -
7
( (1 60)
1
T (1-6))
RHS of Eq. (14) S
2 622
[2
2
12
2
a20
622
622
n
(1 T) e
(1 (1. (1+ 2) (1+,)(11)+77 +T (1+
+37 (1+6)*)
Vi
+ 2
(Iº. (1 (1- -)² + +7 (1-6)3 + +37 (1-E)-) - -7² -23
(1+E) + -1 72 + (( + (1- E¹) -1) .78
14. Vt
2
3(1+c) 33 - c7-) -c22) TT
< 14 (62 + 36 T 247*)
(using e' S 1)
We can bound ' from above given the trivial bounds we have that Asmall S 1/n and Atarge 2 2a/Eb their definitions in Equation (15):
k Alarge
k.E. E
1 VC Ck (n213a
1/3
T
Amall
S
Voe- Ck (
a
n
n
(16)
< Voz Ck
< 6 é'.
The second to last inequality above is due the range assumed for it is greater than (vnc?)-1 For the last inequality, we assumed that a < c. Moreover, using C S (5080320 ce) we have VCe Ck 6. Therefore, obtain:
RHS of Eq. (14)
n Vt
18-28-1 (T)
(using 12 T in Eq. (16))
$ (14 28. 6²)
n
k-
n²
(since é' = 6c and T S Vk. f/a/n in middle of Eq. (16)
2k
Vi S (14112 6e) 4/3 k
14112. an
(using f = c (/3
n2/3 1/3
1
14112 C Ck <
360
For the last inequality, recall that early on we set l to be at most (n2/3 / and c is defined to be at most (5080320- -e) Therefore, the requirements in Fact D.2 hold as desired in our setting. Thus, the proof is complete.
E Empirical Evaluation
We evaluate our algorithm empirically on real and synthetic data on the closeness testing problem. Recall that given samples to two unknown distributions p and & over the domain [n)] we wish to test if if ||p- gll TV 2 They are referred to as the (p.p) case the (p, q) case respectively. Our experiments test the performance our algorithm and baselines.
Datasets.
Hard Instance: This is a simplified version of the hard instance described in Section D.1 for Theorem 12. conceptually similar hard instance also used in the classical closeness testing setting without any learned augmentation, as detailed in Section D.1.2
Let [n] be the domain. In the instance used in the experiments, p and agree on the first m ==
2/3 clements. Both distributions have probability mass // 1/(2m) on these domain elements. p
34

---

Augmented Tester, 103 Samples
35
Augmented Tester
30
Error
25
20
15
10
5
0.0
0.1 0.2
0.3 0.4 0.5 0.6 0.7
Ilp
Figure 5: Error as a function of prediction quality for the 'Hard Instance' dataset
Augmented Tester, 10 Samples
Un Un-augmented Tester, 10 Samples
p q [| 91v 1/2
p= q
20
25
- -1- 1/2
Frequency
Frequency
20
15
10
10
0
100
0
100
200
300
400 500
600
500
0
500
1000
1500
Estimator Value
Estimator Value
(a) Distribution (augmented)
(b) Distribution of Z (un- (un-auemeeted)
Figure 6: Additional figures for the 'Hard Instance' dataset
also has probability mass 2/n on domain elements between n/2 and 3n/4 and has probability mass 2/n domain elements between 3n/4 and n. All other probability masses are O. We can check that l|p gllrv 1/2. The first m domain elements represent 'heavy hitters' which conspire to fool any testing algorithm and the rest of the domain are items which contribute to all the TV distance but are rarely sampled. Indeed, we built upon this intuition to prove a formal lower bound in Theorem 12.
We consider hints of the form ý (1-3) B--Uni((() where Unif(n) is the uniform distribution on [n] elements and a E [0, 1] an interpolation parameter. 0 corresponds a perfect hint and the quality of the hint degrades as increase. When a = 1, we receive ò = Unif(n), i.e. a hint which require any learned information instantiate. our experiments, we n, the domain size, to = 10 and our goal is to determine if we are sampling from (p. p) or (p. g).
IP: The data is internet traffic data collected at backbone link of a Tierl ISP in a data center". Using the preprocessing in [1], we construct the empirical distribution
source IP addresses in consecutive chunks of time. Each distribution represents approximately 170ms of empirical network traffic data. The support size each distribution
45, 000 while the total domain size is > 2.5 10s Distributions curated from network traffic closer in time are closer in TV distance. This dataset has been used other distribution testing literature [1, 48).
FFro CAIDA internet traces 2019, see settps:/wwiee caida. org/ wtw.aiid..rg//aaallaggoooooooooo wttpaa//log..tttttt//oooooiocaa passive-equinix-ny
35

---

IP Traffic Data
IP Traffic Data
35
Closeness Tester
40
30
P
Closeness Tester
25
P2
% Error
Augmented Tester
% Error
20
CRS '15
20
15-
10
10
5
0
100
200
300
400 500
600
100
200
300
400
500
600
Samples
# Samples
(a) Error vs samples
(b) Comparison hetween two predictors
Figure Results for the IP dataset
We p be distribution for the first chunk of time and let q be the distribution for the last chunk of time. Empirically, we have l|p <||Tv Rs 0.72. The hint is for p. denoted as P. is the second chunk of time. Unlike the previous case, the hint is relatively far from p terms of TV distance (llp pll x 0.59). Nevertheless, they share similar 'heavy' items (IP addresses with large probability mass), since p and P represent distributions of network traffic which are close in time.
Baselines. We compare our main algorithm with the following baselines.
CRS '15. This is the state of the art algorithm with access to almost-perfect predictions from [28]. More precisely, they assume predictions to both distributions p and g. denoted as á and ý. Furthermore, they require p(i) (1 + e/ /100))(() and g(t) = (1 + e/ (t) for all i E [n]. Note that we only assume access to (much weaker) predictions for only p.
Closeness Tester This is the state the art algorithm of [42] without any predictor access. We refer to this algorithm the standard the un un-augmented tester well.
Error Measurement. At high level, both our algorithm (denoted as 'Augmented Tester' and the prior SOTA un-augmented approach, (abbreviated 'Closeness Tester') compute estimator Z based on the samples requested. Then, both algorithms threshold the value of Z to determine which we in (either q or [|p- q 4/lTv& 2 e. Note that Z is random variable in both cases (since it depends on random samples). Idcally, the distribution of Z is well-separated in the two different hypotheses.
Thus in our experiments, given a sample budget, we compute the empirical distribution of Z for both algorithms under both hypothesis cases across 100 trials. For fixed algorithm, our error measurement computes the dissimilarity of the two empirical histograms: if the histograms are well-separated then we know the algorithm can adequately distinguish the two hypotheses. On the other hand, if the histograms of Z in the two cases are highly overlapping, then it is clear that the algorithm cannot distinguish well. Thus, given the two empirical histograms, best empirical threshold which best separates them. This is done for both algorithms, ours and the classical Closeness Tester. Then we measure the fraction of data points in the histogram which are misclassified as the error. Calculating the best empirical threshold also makes both of the algorithms more practical as the theoretical thresholds only stated asymptotically with un-optimized constant factors, making the theoretical values impractical. Finally, note that it is trivial to get 50% error.
calculate the
CRS '15 is fundamentally different algorithm. Rather than calculating estimator, it queries the hints و and & on the samples received and check if they are consistent with each other. If all samples i satisfy p(i) (1 + (i), the algorithm declares we in the p- = qq case.
Note that as implemented, our algorithm and the standard Closeness Tester do not require the knowledge of (E is not needed to calculate the estimator Z). On the other hand CRS '15 crucially
36

---

requires the knowledge of E. Thus, we make this baseline even stronger by providing it with the exact knowledge of (which the other two algorithms do not have access to).
Results.
Hard Instance. Our results are shown in Figures and 5. We now describe the plots. Figure 1 displays the performance of all algorithms as a function of the number of samples seen. Note that the y axis measures the fraction of times In Figure 1, our algorithm has access to f = p and CRS '15 has access to P = p. Furthermore, it has access to a hint which satisfies Ilğ q TV < 0.002. hat is created by removing a small fraction of the mass on a small fraction of the heavy domain elements between 1 and m.
distinguish the two hypotheses across 100 trials.
We see that the performance of both our Augmented Tester and the standard Closeness Tester improves as the sample complexity increases. On the other hand, CRS '15 essentially always obtains the trivial guarantee of 50% error even when it is fed a large number of samples. This is because with decent probability, we sample an element where ( 0 and p(i) o 0. Thus in the p q case, it is very likely to output the incorrect answer.
Figure also demonstrates that our augmented tester achieves up to 20x reduction in error than the standard Closeness Tester. also requires > 2x fewer samples to achieve 0% error empirically.
Our improvements are due to the fact that the empirical estimators of in the two cases of p = g and p o q are very well-separated for the Augmented Tester. In fact, shown in Figures 6(a) and 6(b), if we fix the number of samples to 10*, the empirical distributions of Z in the two cases do not overlap at all for the augmented algorithm. On the other hand, thee is a significant overlap for the un- mungeeeented tester (the standard Closeness Tester). This implics that the Closeness Tester baseline cannot distinguish the cases well as the augmented algorithm.
IP Data. Our results are shown in Figure 7(a). Again we see the same qualitative behavior: CRS '15 is quite brittle prediction errors: in the case (p. case, we feed CRS '15 with the perfect prediction for the first distribution, and P for the second. In this case, it typically outputted the incorrect answer. Furthermore, our augmented algorithm has a better sample vs error trade-off than the un-augmented approach. Indeed, we observed that while the augmented tester only required 500 samples obtain 0% error in 100 trials, the standard tester required > 700 samples, implying our augmented approach is > 40% more efficient.
Robustness to Prediction Error. Our experiments also demonstrate the robustness of our augmented approach to the quality of the predictions. Our theory crisply quantifies how the theoretical sample complexity is affected by a predictor which satisfies ||p pllTv a, and correspondingly in practice, we observe that our algorithm is able to take advantage of predictors of varying quality.
Indeed, for the hard instance, than the standard tester, even if ||p pll is high. This is demonstrated in Figure 5 where we monotonically increase / (as described above). The plot shows that while the error also increases monotonically, it is only when ||p - أ TV 2 .7 that the quality is comparable to the standard closeness tester.
observe that the augmented approach still obtains better error
Indeed, even at high values of 3, e is still informative of the heavy-hitter structure of p. Therefore, the augmented algorithm can still reliably use p to perform a suitable flattening.
The phenomenon repeats itself in for the IP data. In Figure 7(b), we compare the performance of using two different predictors. P1 is the same predictor as Figure 7(a) whereas Pa is the IP distribution that in between p and g (it is formed using the chunk of time that is exactly in between the first and the last). We observed that now |p P2llTV ~ 0.69 which is much higher than ||p Pu lV Nevertheless, is still the case that many heavy-hitters between p and ÿ2 are shared. Thus even though the TVV distribution between p and the hint Ω2 maybe high, our algorithm can still exploit the shared heavy-hitter structure to obtain improved sample complexity over the augmenedt approach. This demonstrates the practical versatility of our algorithm beyond the precise theoretical bounds.
37

---

Algorithm L3 --norm estimation
1: procedure ESTIMATE- CaATT------ (sample access to n, 6)
2:
for = 1...., (log (1))) do
3:
$ + + 0 (vn log (1))))
21, 01,32,..: 1 I. Draw & samples from p.
5:
x 2 i- i+1
1 my
b Number of collisions
6:
I x/()
7:
Output the median of L;'s
F
Background and existing results
E1
Estimating the f--norm
In this section, show that estimate the f--norm of distribution via the number of collisions among O(vn) samples. This result was implicitly known from previous work including [52]. Here, include formal statement and proof for the sake of completeness.
Fact F.1. [Adapted from [52]] Suppose we have parameter ó E (0, 1) and an arbitrary distribution p
over [n]] for which we have sample access to. Algorithm receives n and and s = O (yn log(1/8)
samples from p and outputs estimate L of the the (z-orrm of p such that with probability 1
we have:
|pll2 2
3 l|pl12
S
2
Proof. Suppose have samples drawn from p: 3i, ..,......,. Let X denote the number of collisions among these samples. That is, the number of pairs of equal samples == Eiej 1a,
In [52]. they have shown that E[x] (2)
|Ipll2 and Var[X] is at most 2 (E[x]) Hence,
using Chebyshev's 's inequality, we obtain:
X
1p 2
Var x/
8 E
|
Pr
1p11
2
|lpl
8
8
& 0.1
1/2 1lrl2
(s/2) 1/vn
The second to the last inequality holds since the fn-morm of any discrete distribution over [n] is at most 1/ And, the last inequality holds for > 160.77. The above inequality implies that each Li in the algorithm is within the desired bound with probability at least 0.9.
To find an accurate estimate with probability 6, repeat this process (log(1/0) times and take the median these estimates. Using the Chernoff bound, one can show that median is accurate with probability at least 1 8.
standard amplification technique: We
F.2 Standard closeness tester
In this section, we present the result of [30] for robust fa-distance estimation between two un- known distributions p and q. Their results implies fi-tester for closeness testing of p and y as it has been used in [42]. The important feature of this tester is its adaptive sample complexity to max (1P112 (1a)))) which combined with the flattening technique would achieve optimal sample complexities for several distribution testing problems. Later [9] have shown that
modify the this closeness tester such that the sample complexity only deepens on min (Irll (Irlll.1lal1)) llall)).
Fact F.2 (Adapted from [30, 42, 9]), Suppose we have two unknown distributions and over [n]. Let b 2 min (1P21 l1 Algorithm can distinguish whether p = or e-far from each other with probability 1 1-6 6 using Onn/b/e) samples.
38

---

Algorithm l3 norm estimation
procedure STANDARD CLOSENESS TESTER(sample access p. n.
2: Lp --STIMATEE-E (55 n, 6/3)
3: Ly ESTIMATTE- (q. n, 6/3)
4:
if Lg [1/3,3] 3] then
5:
return reject
6:
t (
7:
m +
accept-count - 0
9:
for -,,,.,,,6 ,d. do
10:
Draw m samples from p and G-
11:
Let X, and Y; denote the number occurrences of element in the samples drawn from
distributions p and q respectively.
(X; YJ X; Y
12:
Z
m
13:
if Z 2 then
14:
accept-count +- accept-count
15:
if accept-count 2 t/2 then
16:
return accept
17:
return reject
F3
Useful facts
Coupling: Suppose have two probability distributions and q finite domain Q. A coupling between and is a joint distribution over !? where the two marginals of C are and g. Below is the fundamental coupling lemma:
Fact F.3. (Coupling Lemma) For every probability distributions over a finite domain Ω, have:
For any coupling C of and q, we have:
x12
There exists maximal coupling C* (also known optimal coupling) for which the above inequality holds:
Pr * Y] =--==p--pp0 gllzv.
G Augmented flattening for guarantees other than total variation distance
Below, we provide simple lemma that indicates how one can use ý to flatten distribution based on various guarantees of the prediction. Suppose our target G--orm which we desire is v. In the following lemma, we propose flattening /' to decrease the & to up to some multiplicative factor that depends on the quality of the estimates.
Lemma G.1. Suppose we have an unknown distribution every [n] we are give an estimate p.. Then for every v 1, there exists flattening such that it increases the domain size by 1/v and the fz-norm of the p! (F) bounded by:
(p1, PP..PP...... Pn) over [n]. Assume for
p
<
v
Proof. For every i E [ni), set m, follows:
P
my
+
39

---

It is not hard to see:
Pi
P
S
Σ
p
m4
m
Ps/U
p
In addition, the new domain size bounded follows:
Σ my Snnn Σ
p:
2=1
Using Ei=1 P. 1, conclude the statement of the lemma.
In the following, we discuss a few cases for which we have some guarantee on the accuracy the estimates and how it affects the f--norm reduction. Note that desired case here is not blow up the domain size by more than a constant factor and bring down the f--norm to O(1/vn).
Exact values: Assume P. = P:- By setting v = 1/n, the e--norm reduces to ( vn). and the new domain size is (n)).
2. Multiplicative upper bounds: Suppose for every i, we are given an estimate P. such that P. 2 op; for parameter a 1. Then, we have E pd /ps is at most 1/ax. Also, let 3 denote Σ P.. Thus, the sample complexity of the tester [30], is:
new domain size min (Ilp) 112 (112)
# samples
22
(n B/v) Voja
(Bla+B//oor " nVv/a+B/Vau
6²
Vn B/a
=0
Note that the last inequality is achieved by minimizing over v and setting v 3/n. Moreover, this bound gives us the optimal sample complexity for constant and J.
40

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
All theoretical claimed are backed by full proofs.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We prove tight lower bounds for our setting and discuss alternate prediction
models.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theorems have full, formal proofs.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: A Jupyter notebook is included in the submission which shows has the full code.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We include link to the CAIDA dataset and Jupyter notebook is attached the submission.
Experimental Setting/Details
Question: Does the paper specify all the training and test details (e-g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details are given in Section E.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: See e.g. Figures 6(a), 6(b).
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification: We use sample complexity as a measure of efficiency, not computational time (although all of our algorithms very efficient).
41

---

9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://errr.pp..cpppttttttttbtia
Answer: [Yes]
Justification: The paper conforms to the NeurIPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
There is no societal impact the work performed.
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper has no language models, image generators, or scraped datasets and poses no such risks.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The datasets used are fully described in Section E.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification: No new assets introduced.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects used.
42


Reviews:
[{"review_id": "C5eWGRNf0I", "reviewer": "Reviewer_BZRn", "summary": "This paper studies the task of identity/closeness testing when the tester is augmented with predictions of the unknown distribution involved apriori. In particular, in identity testing, in addition to sample access to the unknown distribution $p$, the algorithm is also given some $\\hat p$ that may or may not satisfy the guarantee $ \\text{TV}(p, \\hat p) \\leq \\alpha$. If the guarantee does not hold, the algorithm is allowed to answer **inaccurate**. Otherwise, the algorithm is asked to perform the standard testing task: return YES if $p$ equals to some known distribution $q$, and NO if $p$ is at least $\\epsilon$-far from $q$ in total variation distance. For closeness testing, though both $p$ and $q$ are unknown, the authors assume that such prior prediction $\\hat p$ is only available for one of the distributions. \n\nFor identity testing, the sample complexity goes through a phase transition depending on the relative size of the prediction error tolerance parameter $\\alpha$ and $d = \\text{TV}(q, \\hat p )$, the TV distance between the prediction distribution and the known distribution. When $d<\\alpha$, the sample complexity is the same as the usual identity testing. When $d > \\alpha$, the sample complexity is $\\min\\left( \\frac{1}{ (d - \\alpha)^2 }, \\frac{\\sqrt{n}}{\\epsilon^2} \\right)$. Intuitively, this is saying that the prediction could potentially help a lot if it predicts that the test is in the soundness case (as $\\hat p$ is indeed far from $q$) but not so much if it predicts the test is in the completeness case. This intuition is clear from their upper bound approach. They leverages the Scheffé set $S$ (the set that realizes the maximum discrepancy between $\\hat p$ and $q$), and test for discrepancy between $p(S)$, $q(S)$ and $\\hat p(S)$. This will either invalidate the prediction or lead to rejection. Furthermore, since this is simply a 1-dimensional bias estimation problem, they could avoid any dependency on the doamin size (when $d$ is sufficiently separated from $\\alpha$). The above strategy is not so helpful when there is no significant discrepancy between $p(S)$, $q(S)$ and $\\hat p(S)$, and therefore their algorithm fall back to the standard identity tester when the prediction says that the test is in the completeness case.\n\nFor closeness testing, they show that the sample complexity is given by $\\sqrt{n} \\alpha^{1/3} / \\epsilon^{4/3} + \\sqrt{n} / \\epsilon^2$. Here the Scheffé set strategy no longer applies as $q$ is also unknown to us. However, the authors show that the prior $\\hat p$ is still very useful in an important closeness testing sub-routine (commonly referred as **flattening**). At a high level, when the unknown distributions have large $\\ell_2$ norm, standard collision-based test statistics may have large variance. Flattening techniques could then be used to transform the distributions to reduce their $\\ell_2$ norms, and hence also the variance of the test statistics. The authors show that such a routine can be implemented in a more sample-efficient way if the algorithm is equipped with a prediction $\\hat p$.", "questions": "Have the authors considered situation when we have prior knowledge about both of the unknown distributions in closeness testing? Then it seems like the Scheffé set may again become useful, and could lead to huge sample complexity improvements.\n\nComment: The setup bears some similarities to the notion of testable learning, where the algorithm is given some prior distribution assumption that may or may not hold. In particular, the algorithm is also given the ability to output ``reject'' when this prior knowledge is false.", "limitations": "Yes, they have.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Identity/closeness testings are fundamental problems in many different areas. In the standard setting, the sample complexity scales polynomially with respect to the domain size, making the tests prohibitively expensive for distributions with large supports. The authors demonstrated that the sample complexity may be significantly improved if the tester is augmented with a prediction of the unknown distribution. The surprising part is that the prediction need not to be an accurate one. While the tester draws significantly fewer samples if the prediction is accurate, even if the prediction is not, the tester is guaranteed not to be misguided. In particular, it can identify inaccuracies in the prediction, and simply fall back to the standard testing approach in that case. Lastly, the bounds are optimal up to constant factors and technically solid.", "weaknesses": "The authors mention that the potential application is when the unknown distribution evolves over time. In that case, the ``unknown'' distribution is not completely unknown to us as we may extract information from past data. It will be more compelling if the authors could provide more detailed mathematical setup of this. For example, it will be interesting to see analysis of the behavior of augmented testers when we face a sequence of tests where the unknown distribution may go through random distribution shifts from one task to another.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Clarification on evolving distributions** \n\nFor our results, the algorithm requires access to a prediction distribution $\\hat{p}$, which is intended to be close to the unknown distribution $p$ (in addition to samples from $p$). Our algorithms are applicable in settings where the extra information available about $p$ can be translated into a distribution $\\hat{p}$. In our introduction, we strive to depict various scenarios where such predictions can be available, including slowly evolving distributions such as network traffic data or search engine queries. Mathematically, we consider a series of slowly changing unknown distributions: $p_1, p_2, \\ldots, p_t$. In this setting, the empirical distribution of the samples from $p_1, p_2, \\ldots, p_{t-1}$ can serve as a prediction for $p_t$. For example, the distributions of search queries change slightly every hour or so. However, the overall empirical distribution of search queries from the past year could be a good prediction for the distribution at a particular hour. We will clarify this in our introduction. Continual testing while the distributions undergo small perturbations at every step is a very interesting open question. Although our results do not directly address this problem, we believe that some techniques from augmented flattening could potentially be helpful in solving this problem as well.\n\n\n**Studying two predictions**\n\nThank you for suggesting an interesting open direction. We did not consider this case in our paper. First, we would like to mention that our upper bound still holds when two predictions are provided. It is not too difficult to adapt our augmented flattening to incorporate both $\\hat{p}$ and $\\hat{q}$. The sample complexity in this setting is proportional to the minimum of $\\alpha_p^{1/3}$ and $\\alpha_q^{1/3}$. However, the lower bounds do not hold. As you pointed out, one can hope to achieve better sample complexity if the distance between the two predictions is more than $\\alpha_p + \\alpha_q + \\epsilon$. In particular, estimating the probability of the Scheffé set gives us either a 'reject' or 'inaccurate information' result for one of the distributions. On the other hand, when $\\hat{p}$ and $\\hat{q}$ are identical, our lower bound indicates that one cannot hope for better sample complexity. It remains an open question to study the case where the distance between the two predictions is smaller than $\\alpha_p + \\alpha_q + \\epsilon$, but larger than zero.\n\n\n**Connection to testable learning**\n\nYes, in both cases, the algorithm is given an option of forgoing to solve the problem when the underlying assumption does not hold. Although there is no notion of ``augmentation’’ in that line of work.", "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": "", "extra_scores": {}}, {"review_id": "pYaOG2mbFh", "reviewer": "Reviewer_Zhut", "summary": "The paper looks at the problem of hypothesis testing for discrete distributions where a predicted data distribution is available. The paper gives algorithms (Algorithm 1; closeness testing, Algorithm 3; identity and uniform testing) which either reduces the number of samples required for testing, or do no worse than standard approaches. Lower bounds on samples are given, and experiments are done to validate the performance on real data.", "questions": "These questions may be straightforward to those familiar with the relevant literature, but these are the questions I have:\n - Are there certain types of data where making weak assumptions about the predictor (compared to related works) might give bad results (or similar results to existing methods)?\n - Is there a reason why experiments for identity testing and uniformity testing are not given?", "limitations": "N/A", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is extremely thorough and detailed, giving an overview of the important results (including experiments), as well as a roadmap of the intuition required behind the proofs for the upper bound and lower bounds.\n\nThe appendix also includes motivation and explanation for the numerous proofs involved.\n\nThe main contributions of needing significantly fewer sample sizes for hypothesis testing compared to CRS'15 or [41] is also significant.", "weaknesses": "I am not sure whether this is an appropriate venue mostly due to the heavy technical details in the paper, and with a lot of key details in the appendix ; but to be fair, the conference format makes it difficult to present detailed work like this.\n\nUnfortunately, this is not mostly in my area of speciality, so I am unable to give meaningful comments about potential weaknesses (or strengths).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Suitability for the conference**\n\nWe would like to point out that many related works on distribution testing have appeared in recent ML conferences such as NeruIPS/ICML/ICLR. These works are relevant to the learning-theory, privacy, algorithmic statistics, and sublinear algorithms community within ML. Please see below for a small sample of such related works that appeared in recent NeurIPS conferences that we cite in our work. Our references in our submission list additional related works in other top ML venues.\n[4] J. Acharya, Z. Sun, and H. Zhang. Differentially private testing of identity and closeness of\ndiscrete distributions. NeurIPS 2018\n \n[5] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. NeurIPS 2015\n \n [8] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Hypothesis selection with memory\nconstraints. NeurIPS 2023 \n[9] Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, and Ronitt Rubinfeld. Private testing of distributions via sample permutations.  NeurIPS 2019\n \n[24] Clement L. Canonne, Ilias Diakonikolas, Daniel Kane, and Sihan Liu. Nearly-tight bounds for testing histogram distributions. NeurIPS 2022\n \n[27] Clement L Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Lydia Zakynthinou. Private identity testing for high-dimensional distributions. NeurIPS 2020\n \n[45] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Sharp bounds for generalized uniformity testing. NeurIPS 2018\n\n\n**Weaker assumptions about prediction**\n\nThank you for suggesting an interesting open direction! It is not clear to us if our predictor assumption can be relaxed while retaining similar guarantees. We believe our model is quite natural, but there could certainly be other weaker assumptions which are powerful enough to give improved sample complexity. However, we note that our algorithms are robust, so even if the predictor assumptions do not hold, we never lose asymptotically on the sample complexity compared to classical algorithms without predictions.\n\n\n**Experiments on identity testing and uniformity testing**\n\nWe focused on closeness testing since it is the hardest statistical task out of the three distribution testing problems we studied: it generalizes identity and uniformity testing, and a larger sample complexity is required, both in the classical and augmented settings. We suspect that one can see similar qualitative gains from using our augmented algorithms, provided that appropriate predictions are available.", "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": "", "extra_scores": {}}, {"review_id": "ActMNq3SuU", "reviewer": "Reviewer_bNNx", "summary": "The paper studies the problem of property testing (specifically uniformity, identity, and closeness testing) in the context of the learning-augmented algorithms framework. They show how a prediction about the underlying distribution could be harnessed to provably reduce the number of samples required when the prediction is of high quality. They give efficient algorithms and provide experimental evaluation with code.", "questions": "- In the paragraph starting on Line 177: given \"perfect predictors\", why does one even need additional samples from the distribution? From my limited understanding, that paper talks about having additional access to other kinds of queries on the underlying distribution (apart from just drawing IID samples) and \"samples\" may refer to those other kinds of queries (for instance, one can query the probability mass of an element and get its true mass in $p$). I'm not sure how that directly compares with your setting where \"samples\" mean IID samples only.\n- How do you obtain an **upper bound** expression for the final big-O containment for the equation block between Lines 378-379? To be precise, we have $s_f \\leq = \\min\\{\\frac{n^{2/3} \\alpha^{1/3}}{\\varepsilon^{4/3}}, n\\} \\leq \\frac{n^{2/3} \\alpha^{1/3}}{\\varepsilon^{4/3}}$ so $\\frac{n}{\\varepsilon^2} \\cdot \\sqrt{\\frac{\\alpha}{s_f}} \\geq \\frac{n^{2/3} \\alpha^{1/3}}{\\varepsilon^{4/3}}$, which is a **lower bound** right? Where did I mess up?\n\nPossible typos:\n- Line 266: \"...strategy is put the...\" should be \"...strategy is **to** put the...\"?\n- First line of the equation between Lines 328-329: Should the last equality be $\\leq$?\n- Line 375: Should it be $\\leq 100 s_f$ instead?\n- Line 376: Should it be $\\leq 102 n$ instead?", "limitations": "Nil", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is well-motivated and the paper is well written.", "weaknesses": "I did not check the proofs in the appendix in detail but the intuition given for the approaches make sense.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comparisons to the previous work** \n\n[29] is an example of studying distribution testing when both samples and a prediction distribution $\\hat{p} = p$ are available. However, their algorithm does not receive $p$ directly and can only query $p$. Since they do not see the whole $p$, they would require samples from it as well. They consider two types of queries: querying the probability of a certain domain element $p(i)$, or querying the probability of the first $i$ elements for a given $i$. In comparison to our model, their assumption on the accuracy of the prediction is very strong as they assume $p = \\hat{p}$. They also consider an alternative model with multiplicative noise, which is still a stronger assumption compared to ours. However, their model is weaker in another sense, as they do not have access to $\\hat{p}$ for free. The total cost of their algorithm involves the number of queries they make to $\\hat{p}$ and the number of samples (which they describe it as queries to the sampling oracle). For testing uniformity and identity, they have shown that $\\Theta(1/\\epsilon)$ queries are necessary and sufficient. Given their upper bounds and our lower bounds, it can be concluded that solving the problem in our model is more difficult, meaning it would require many more samples.  Please see Section 1.3 for more detailed comparison to prior related works.\n\n\n**Sample complexity**\n\nFor $s_f$, we have two possibilities, either it is equal to $n^{2/3} \\alpha^{1/3} / \\epsilon^{4/3}$ or it is equal to $n$. For the first case, it is not too hard to see that the equation will be $O(s_f) = O(n^{2/3} \\alpha^{1/3} / \\epsilon^{4/3})$. Now, assume $s_f$ is $n$. This case, implies that:\n$$n \\leq n^{2/3} \\alpha^{1/3} / \\epsilon^{4/3} \\leq n^{2/3}/\\epsilon^{4/3}.$$\nHence, there is an interdependence between the parameters: $n \\leq 1/\\epsilon^4$. Therefore, one can conclude $n \\leq \\sqrt{n}/\\epsilon^2$. Therefore, both expressions in the sample complexity equate to $O(\\sqrt{n}/\\epsilon^2)$.\nMaybe it is helpful to note that in this case: $\\sqrt{n}/\\epsilon^2 \\geq n^{2/3}/\\epsilon^{4/3} \\geq n^{2/3} \\alpha^{1/3}/\\epsilon^{4/3}$. Hence, our lower bound is not violated.\n[In case we did not answer this question adequately, please leave us a comment, and we will try to clarify further.]", "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": "", "extra_scores": {}}, {"review_id": "YiHtZzJOYT", "reviewer": "Reviewer_qguF", "summary": "This paper consider the problem of hypothesis testing for discrete distributions, including identity testing, closeness testing and uniformity testing. The authors investigated these testing problems under the setting where a predicted data distribution is available. Utilizing this additional information, the authors propose \"augmented tester\", which can reduce the sample complexity when the given predicted distribution is accurate (when it is inaccurate, the proposed algorithm is still robust). Lower bounds are also provided for justifying the optimality of the proposed algorithm.", "questions": "I am curious about the intuition behind your algorithm, i.e., how to utilize the additional information.  It will be good if the authors could provide more explanation of the proposed algorithm.", "limitations": "no limitations are stated.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea of augmenting hypothesis testing using additional information is interesting. The proposed algorithm can reduce the sample complexity when the given prediction is accurate enough, which is satisfactory. Lower bounds are also provided, making this paper comprehensive.", "weaknesses": "A possible weakness is that, the structure of this paper is a little bit weird. You first give your theorems in the introduction when your proposed algorithm is not mentioned yet. Then you provide the proofs in section 2, and state the upper bound again in section 3. The algorithm has not been mentioned until the last.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**presentation**\n\nThank you for your feedback.  The algorithm is given on page 8 of the main body. We give technical overview in Section 2 before the algorithm to give a high level picture about how our upper bounds and lower bounds (in the appendix) fit together to give a complete characterization of the augmented distribution testing problems we study.\n\n\n**Intuition behind our algorithm**\n\nFor the closeness testing problem, we use the hint distribution to $\\hat{p}$ to reduce the $\\ell_2$ norm of $p$, the unknown distribution. Intuitively, we can do this by looking at the ‘heavy hitters’ of $\\hat{p}$: the domain elements that $\\hat{p}$ assigns a high probability mass to. Then we split the mass of all heavy elements equally among many synthetically created domain elements. If we see such an element $i$ from our sample from $p$, we perform a thought experiment where we instead sample uniformly from the synthetically created domain elements corresponding to $i$. This does not change any of the TV distances, but significantly reduces the $\\ell_2$ norm of $p$ (formalized in Lemma 3.1). A smaller $\\ell_2$ norm makes the testing problem significantly easier, as done in prior works. Please see Section 2 for intuition about our other results. For further details, please see Section 2 and Section 3 in the main body.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their feedback. We will integrate all your editorial comments regarding the presentation of our paper in the future version.

Meta-review: This paper studies the problem of identity/closeness testing when the tester is augmented with predictions of the unknown distribution involved apriori. Under this setting, the paper presents sample complexity bounds for uniformity, identity, and closeness testing problems and shows them to be smaller than that of their classical counterparts. Moreover, lower bounds are presented to establish the optimality. All the reviewers are positive about the paper's novelty and contributions, which I agree with. Based on the discussion with the reviewers, I think the paper is a nice contribution to the property testing literature and therefore I am recommending acceptance. I strongly urge the authors to incorporate all the reviewer comments along with any clarifications they provided in the rebuttal into the camera-ready version.
Decision: Accept (poster)