Replicable Uniformity Testing

Authors: sihan  liu
christopher  ye
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 01:58:50

Abstract: Uniformity testing is arguably one of the most fundamental distribution testing problems. Given sample access to an unknown distribution $\mathbf{p}$ on $[n]$, one must decide if $\mathbf{p}$ is uniform or $\varepsilon$-far from uniform (in total variation distance). A long line of work established that uniformity testing has sample complexity $\Theta(\sqrt{n}\varepsilon^{-2})$. However, when the input distribution is neither uniform nor far from uniform, known algorithms may have highly non-replicable behavior. 
Consequently, if these algorithms are applied in scientific studies, they may lead to contradictory results that erode public trust in science.

In this work, we revisit uniformity testing under the framework of algorithmic replicability [STOC '22], requiring the algorithm to be replicable under arbitrary distributions. While replicability typically incurs a $\rho^{-2}$ factor overhead in sample complexity, we obtain a replicable uniformity tester using only $\tilde{O}(\sqrt{n} \varepsilon^{-2} \rho^{-1})$ samples. To our knowledge, this is the first replicable learning algorithm with (nearly) linear dependence on $\rho$.

Lastly, we consider a class of ``symmetric" algorithms [FOCS '00] whose outputs are invariant under relabeling of the domain $[n]$, which includes all existing uniformity testers (including ours). For this natural class of algorithms, we prove a nearly matching sample complexity lower bound for replicable uniformity testing.

Main paper: 
 introduction: 
 Distribution property testing (see [43, 9, 12] for surveys of the field), originated from statistical hypothesis testing [39, 36] , aims at testing whether an unknown distribution satisfies a certain property or is significantly "far" from satisfying the property given sample access to the distribution.After the pioneering early works that formulate the field from a TCS perspective [5, 4] , a number of works have achieved progress on testing a wide range of properties [6, 21, 11, 22, 10, 19] . Within the field, uniformity testing [28] is arguably one of the most fundamental distribution testing problems: Given sample access to some unknown distribution p on [n] = {1, • • • , n}, one tries to decide whether p is uniform or far from being uniform.When the unknown distribution is promised to be either uniform or at least ε-far from being uniform in total variation (TV) distance, a line of work in the field [28, 40, 47, 20, 1, 16] has led to efficient testers that achieve information theoretically optimal sample complexity, i.e., Θ( √ n/ε 2 ). However, the testers are only guaranteed to provide reliable answers when p fulfills the input promisep is either U n or far from it. In practical scenarios, due to a number of reasons such as model misspecification, or inaccurate measurements, such promises are rarely guaranteed [13] . Since the tester no longer has a correctness constraint to adhere to, it may have arbitrarily volatile behavior. Ideally, we hope for algorithmic stability for all distributions, not only on those fulfilling the promises. Consider the scenario where two group of scientists, as an intermediate step of some scientific study, are trying to independently test the uniformity of some ground-truth distribution p * . If the groups reach inconsistent conclusions in the end (as noted in [31, 32, 7] , such replicability issues are fairly common in science), the public might naturally interpret the inconsistency to be caused by procedural or human errors on the part of one (or both) team(s), therefore eroding public trust in the scientific community [37, 44, 3, 42] . However, even when both teams follow the experimental procedure precisely, inconsistencies could still arise simply due to sample variance in the case where p * is neither uniform nor far from uniform. By ensuring that the algorithm is replicable, we can effectively rule out sample variance as a cause of inconsistency.In the work of [30] , a formal definition of replicability for learning algorithms has been proposed to mitigate non-replicability caused by statistical methods. Specifically, replicable learning algorithms are required to give identical outputs with high probability in two different runs where it is given sample access to some common, but potentially adversarially chosen data distribution. Definition 1.1 (Replicability [30] ). A randomized algorithm A : X n → Y is ρ-replicable if for all distributions p on X , Pr r,T,T ′ (A(T ; r) = A(T ′ ; r)) ≥ 1 -ρ, where T, T ′ are i.i.d. samples taken from p and r denotes the internal randomness of the algorithm A. .A number of works have explored the connection between replicability and other algorithmic stability notions [8, 34, 15, 38, 23] , and shown efficient replicable algorithms for a wide range of machine learning tasks [8, 34, 24, 25, 35, 26, 33] . In the context of uniformity testing, if we can design testers that conform to the above replicability requirement, consistencies of their outputs can be guaranteed even when there are no promises on the data distribution. This then motivates the study of replicable uniformity testing. Definition 1.2 (Replicable Uniformity Testing). Let n ∈ Z + , and ε, ρ ∈ (0, 1/2). A randomized algorithm A, given sample access to some distribution p on [n], is said to solve (n, ε, ρ)replicable uniformity testing if A is ρ-replicable and it satisfies the following: (1) If p is uniform, A should accept with probability at least 1 -ρ. 1 (2) If p is ε-far from the uniform distribution in TV distance, A should reject with probability at least 1 -ρ.As observed in [30] , learning algorithms usually incurs additional sample complexity overhead in the replicability parameter ρ compared to their non-replicable counterpart. In this work, we characterize the sample complexity of replicable uniformity testing up to polylogarithmic factors in all relevant parameters n, ε, ρ (under mild assumptions on the testers).An alternative approach to address the stringency of the promises in the formulation of uniformity testing is the concept of tolerant testing [41] . At a high level, given some 0 < ξ < ε, the unknown distribution is now relaxed to be either ε far from U n or ξ close to U n in TV distance. The tester is then required to reject in the former case but accept in the latter. As shown in [45, 46, 48, 13] , assuming that ε is some constant 2 , the sample complexity of tolerant testing quickly grows from strongly sublinear, i.e., Θ( √ n), to barely sublinear, i.e, Θ(n/ log n) as ξ increases from 0 to ε/2. In replicable uniformity testing the testers are not required to accept or reject for intermediate distributions p, i.e., p such that 0 < TV(p, U n ) < ε. Instead, for all possible distributions p, the testers are only required to give replicable answers (with high probability). While we can construct an (n, ε ′ , ρ)-replicable uniformity testing algorithm using tolerant testing by randomly sampling some threshold r ∈ (0, ε ′ ) and performing tolerant testing with ξ = r -ρε ′ and ε = r + ρε ′ , the sample complexity of such an approach will be barely sublinear in n even for constant ρ as discussed above. Notably, the replicable algorithm in our work has a sample complexity that remains strongly sublinear in n.When n = 2, uniformity testing amounts to distinguishing a fair coin from an ε-biased coin. It is well known that the task requires Θ(ε -2 ) samples without the replicable requirement. When the tester is required to be ρ-replicable, [30] shows that Θ(ε -2 ρ -2 ) many samples are necessary and sufficient for replicable coin testing, demonstrating a quadratic blowup in ρ compared to the non-replicable counterpart of the problem. For large n, the sample complexity of non-replicable uniformity testing has been resolved after a long line of work [28, 40, 47] , and shown to be Θ( √ nε -2 ). Following the pattern, one naturally expect that replicable uniformity testing would have sample complexity Θ( √ nρ -2 ε -2 ). In fact, this is exactly the sample complexity reached if one views the outcome of an optimal non-replicable uniformity tester as a coin flip, and uses an optimal replicable coin tester to convert the given uniformity tester into a replicable one.Somewhat surprisingly, we show that the sample complexity from this blackbox reduction is suboptimal for replicable uniformity testing -it is possible to additionally shave one ρ factor and make the dominating term's dependency on ρ linear. To our knowledge, this is the first replicable algorithm that has nearly linear dependence on the replicability parameter in the dominating term.Theorem 1.3 (Replicable Uniformity Testing Upper Bound). Let n ∈ Z + , ε, ρ ∈ (0, 1/2). Algorithm 1 solves (n, ε, ρ)-replicable uniformity testing with sample complexity Õ √ n ε 2 ρ + 1 ρ 2 ε 2 .3 Remark 1.4. [27] showed that the more general problem of identity testing, i.e., testing whether an unknown distribution p is equal or far from some known distribution q with explicit description, can be reduced to uniformity testing with only a constant factor loss in sample complexity. It is not hard to verify that this reduction preserves replicability. This immediately implies a replicable identity tester with the same asymptotic sample complexity (see Appendix C.3 for more detail).As our second result, we provide a nearly matching sample complexity lower bound for a natural class of testers whose outputs are invariant under relabeling of the domain elements [n] . The class of testers are commonly referred as Symmetric Algorithms, and first studied in the work of [5] . Definition 1.5 (Symmetric Algorithms, Definition 13 of [5] ). Let f : [n] ×m → {0, 1} be a binary function. We say that f is symmetric if for any sample set(x 1 , • • • x m ) ∈ [n] ×m and any permutation π ∈ S n , we have that f (x 1 , • • • x m ) = f (π(x 1 ), • • • , π(x m )).We say an algorithm A(; r) is symmetric if it computes some symmetric function f r under any fixed random seed r.Without the replicability requirement, it can be shown that assuming the algorithm is symmetric is without loss of generality for uniformity testing. This is due to a simple observation that uniformity itself is a symmetric property: if p is uniform or far from the uniform distribution, the property is preserved even if we permute the labels of the elements within [n] . Consequently, all known optimal uniformity testers, including our replicable uniformity tester, are indeed symmetric algorithms. For this natural class of testers, we show that the sample complexity achieved is essentially optimal (up to polylogarithmic factors).Theorem 1.6 (Symmetric Testers Lower Bound). Let n ∈ Z + , ε, ρ ∈ (0, 1/2). Any symmetric algorithm solving the (n, ε, ρ)-replicable uniformity testing problem requiresΩ √ n ε 2 ρ + 1 ρ 2 ε 2 samples.Unfortunately, when replicability is concerned, it is unclear whether we can still assume that the optimal algorithm is symmetric. Whether the above lower bound holds for all algorithms is left as one of the main open questions of this work.In this paper, we present a replicable algorithm for uniformity testing using Õ( √ nε -2 ρ -1 + ε -2 ρ -2 ) samples. We provide a matching lower bound for a natural class of symmetric uniformity testers -algorithms that essentially consider only the frequency of each element without discriminating between distinct labels. Since all known uniformity testing algorithms are symmetric, we tend to believe that the lower bound can be established unconditionally and leave it as an open question. We discuss some issues in generalizing our current approach to realize this goal in Appendix C.2.While uniformity testing is a central problem in distribution property testing, there are many other settings where it would be interesting to develop replicable algorithms, such as closeness and independence testing [18] .nρ -2 Barriers for ℓ 2 based Statistics. Most of the well known non-replicable uniformity testers compute an unbiased estimator for the ℓ 2 norm of the the unknown distribution p, i.e., ||p|| 2 2 = i=1 p 2 i , from the number of occurrences X i of each element i among the observed samples. These include the testers from [28, 17] , which are based on counting pair-wise collisions, i.e., 1 2 n i=1 X i (X i -1), and the ones from [14, 1, 47, 20] , which are based on variants of the χ 2 statistic, i.e., n i=1 (X i -m/n) 2 -X i /(m/n). As one can see, these estimators all rely heavily on computing the quantities X 2 i , which could have large variances even when there is a single heavy element. This poses serious challenges on designing replicable testers based on these statistics 4 . In the following paragraphs we discuss the challenge for collision based testers in more detail. A similar barrier exists for χ 2 based statistics, which we defer to Appendix C.1.Given an unknown distribution p, the expected number of pairs of collision will be exactlyn i=1 m 2 p 2 i .If p is uniform, the expected value of the test statistic will be about m 2 2n . If p is ε-far from being uniform, the expected value will be at least m 2 (1+ε 2 ) 2n . To construct a replicable uniformity tester from the collision statistics, a natural idea is to select a random threshold r between the two extrema to be the decision threshold. Consequently, the tester fails to replicate if and only if the random threshold falls between the realized values of the test statistics in two different runs. Conditioned on that the test statistics computed in two different runs deviate by ∆, the above events happens with probability exactly ∆ 2n m 2 ε 2 . Hence, for the tester to be ρ-replicable, the test statistics will need to deviate by no more than ∆ = O m 2 ε 2 ρ/n with constant probability.To focus on the dependency on ρ, we let ε be a small constant. We now construct a hard instance that makes collision-based statistics violate the above concentration requirement unless m ≫ √ nρ -2 . Consider a distribution with a single heavy element with probability mass p ≫ 1/ √ n. Let X ∼ Binom (m, p) denote the number of occurrences of this heavy element. It is not hard to see that this element contributes to the total collision counts by X 2 , which deviates by Ω mp √ mp = Ω(m 3/2 /n 3/4 ) from its mean with constant probability. Consequently, over two runs of the algorithm, with constant probability the numbers of collisions may differ by Ω(m 3/2 /n 3/4 ). Therefore, the tester will fail to be ρ-replicable unless m 3/2 /n 3/4 ≪ ρm 2 /n or equivalently m≫ √ n ρ 2 .Total Variation Distance Statistic To make the test statistics less sensitive to the counts of heavy elements, we compute the total variation statistic, which has been used in [16] to achieve optimal uniformity testing in the high probability regime. In particular, the test statistics measures the TV distance between the empirical distribution over samples and the uniform distribution:S = 1 2 n i=1 |X i /m -1/n|,where X i is the number of occurrences of the i-th element. Unlike collision-based statistics, note that the TV statistics depends only linearly on each X i . For a heavy element X i , the contribution to the empirical total variation distance is (up to normalization) at mostX i with variance Var(X i ) = Θ (mp) = Θ m/n 1/2 opposed to Var(X 2 i ) = Θ m 3 /n 3/2 .Intuitively, this allows us to obtain tighter concentration bounds on the test statistic S, thereby improving the final sample complexity.First, we observe that when the distribution is ε-far from uniform, [16] shows that the expected value of S exceeds the expected value of S under the uniform distribution by at least some function f (m, n, ε) (see Equation (2) for the full expression). To establish a replicable tester in the super-linear case (m = Θ( √ nε -2 ρ -1 ) ≥ n), we use McDiarmid's inequality to directly argue that the TV test statistic deviates by at most ρf (m, n, ε) with high probability. Hence, if we use a random threshold that lies within the gap interval, the threshold will be ρf (m, n, ε) close to the expected value of the test statistic with probability at most O(ρ), ensuring replicability of the final result.The key challenge lies in obtaining the desired concentration in the sublinear regime, i.e. m ≤ n. In this regime, the expectation gap is given by f (m, n, ε) = ε 2 m 2 n 2 . Unfortunately, the presence of heavy elements, i.e., element with mass p i ≥ 1/m, can still make the test statistic have high variance. As a result, it becomes challenging to obtain the desired concentration of ρf (m, n, ε) on the test statistic. However, in the presence of very heavy elements (e.g., p i ≥ m/n) which causes the variance of the test statistic to be too large, we observe that these elements cause the expectation of the test statistic to increase sufficiently beyond the expectation gap so that the tester rejects consistently, even though the distribution may not be ε-far from uniform. To formalize the intuition, we show that whenever the variance of the test statistic is large, so is its expected value, thereby ensuring consistent rejection. In particular, in Lemma 3.3 we show that, whenever Var(S) ≫ ρf (m, n, ε) = ρε 2 m 2 n 2 , it holds that Sample complexity Lower Bound At a high level, we present a family of distributions {p(ξ)} ξ parametrized by some parameter ξ ∈ [0, ε] satisfying the following: no symmetric tester that takes fewer than Ω √ nε -2 ρ -1 many samples can be replicable with high probability against a random distribution from the family. Since we have fixed the testing instance distribution, using a minimax style argument similar to [30] , we can assume that the testing algorithm is deterministic 5 . The family of distributions is constructed to satisfy the following properties: (i) p(0) is the uniform distribution and p(ε) is ε-far from uniform (ii) for any two distributions p(ξ), p(ξ + δ), where δ < ερ, within the family, no symmetric tester taking fewer than Ω √ nε -2 ρ -1 many samples can reliably distinguish them. By (i) and the correctness guarantee of the algorithm, the acceptance probabilities of the tester should be near 1 under p(0) and near 0 under p(ε). This implies that there exists some ξ * within the range such that the acceptance probability is 1/2 under p(ξ * ). 6 By property (ii), p(ξ * ) cannot be distinguished from p(ξ * ± O(ερ)) by the tester, which immediately implies that the acceptance probability of the tester is near 1/2 whenever ξ = ξ * ± O(ερ), and therefore not replicable with constant probability. Thus, if we sample ξ uniformly from [0, ε], the tester will fail to replicate with probability at least Ω(ρ).EQUATIONThe construction of p(ξ) is natural and simple: half of the elements will have mass (1 + ξ)/n and the other half will have mass (1 -ξ)/n. Property (i) follows immediately. The formal proof of Property (ii) is technical, but the high level intuition is straightforward. If we assume the underlying tester is symmetric, the most informative information is essentially the number of elements that have frequencies exactly 2 among the samples (as elements having frequencies more than 2 are rarely seen and the numbers of elements having frequencies 0 or 1 are about the same in the two cases.) If the tester takes m samples, it observes aboutm 2 (1 + ξ) 2 + (1 -ξ) 2 /n = 2m 2 (1 + ξ 2 )/nmany frequency-2 elements under p(ξ) in expectation. On the other hand, the standard deviation of the number of such elements is about m 2 /n = m/ √ n. Hence, for the tester to successfully distinguish the two distributions, m needs to be sufficiently large such thatm √ n ≪ m 2 n (1 + (ξ + ερ) 2 ) -(1 + ξ 2 ) ≈ m 2 (ξ + ερ)ερ n , which yields m ≫ √ n (ξ+ερ)ερ > Ω √ n ε 2 ρ .To formalize the above intuition, we will use an information theoretic argument 7 . Note that for such an argument to work, one often need to randomize the order of heavy and light elements [18, 16] . Otherwise, a tester could simply group the elements whose mass is above 1/n under p(ξ) into one giant bucket and reduce the problem into learning the bias of a single coin, which requires much fewer samples. To achieve this randomization, we consider the Local Swap Family (see Definition 4.2), where we pair the elements with mass (1 + ξ)/n with those with mass (1 -ξ)/n and randomly swap their orders. Since pairs are ordered randomly, no algorithm can hope to identify heavy/light elements without taking a significant number of samples. Thus, this creates distribution families containing p(ξ) and p(ξ + δ) that are information theoretically hard to distinguish even for asymmetric testers. Consequently, this shows the existence of some permutation π ξ of [n] such that the permuted distributions π ξ • p(ξ) and π ξ • p(ξ + δ) are hard to distinguish. However, recall that in the replicability argument we need to first fix some ξ * such that p(ξ * ) = 1/2. Thus, we have to prove specifically that p(ξ) and p(ξ + δ) themselves are hard to distinguish. Fortunately, for symmetric testers, the acceptance probabilities of π ξ • p(ξ) and π ξ • p(ξ + δ) must be identical to those of p(ξ) and p(ξ + δ) respectively. Consequently, no symmetric tester can easily distinguish p(ξ) and p(ξ + δ). 
preliminaries: 
 For any positive integer n, let [n] = {1, 2, . . . , n}. We typically use n to denote the domain size, p to denote a distribution over [n] and m to denote sample complexity. Given a distribution p over [n], let p x denote the probability of x in p. For a subset S ⊂ [n], p S = x∈S p x . For distributions p, q over [n], the total variation distance isd T V (p, q) = 1 2 x∈[n] |p x -q x | = max S⊆[n] p S -q S .We also recall the definition of mutual information. Let X, Y be random variables over domain X . Themutual information of X, Y is I(X : Y ) = x,y∈X Pr((X, Y ) = (x, y)) log Pr((X,Y )=(x,y))Pr(X=x) Pr(Y =y) . We use a ≫ b (resp. a ≪ b) to denote that a is a large (resp. small) constant multiple of b. 
replicable uniformity testing algorithm: 
 Algorithm Overview At a high level, our algorithm computes the TV-distance statistic and compares it with a random threshold. Correctness of the algorithm largely follows from the analysis of the test statistics from [16] . To show replicability of the algorithm, we need a better understanding of the concentration properties of the test statistic when the unknown distribution is neither uniform nor ε-far from being uniform. In particular, we show that when the variance of the test statistic is too large, even if the input distribution itself is not ε-far from uniform, the test statistic is with high probability larger than any random threshold that may be chosen, leading the algorithm to replicably reject in this case. On the other hand, when the variation is sufficiently small, we have sufficiently strong concentration in the test statistic, so that a randomly chosen threshold does not land between empirical test statistics computed from independent samples. Proof of Theorem 1.3. Our starting point is the "expectation gap" of the test statistic shown in [16] . Lemma 3.1 (Lemma 4 of [16] ). Let p be a distribution on [n] n given m samples drawn from p. For all m ≥ 6, n ≥ 2, there is a constant C such thatsuch that ξ = d T V (p, U n ).EQUATION)We require the following structural lemmas, whose formal proofs can be found in Appendix A, on the test statistic S median . These lemmas show that the test statistic S (and therefore S median ) concentrates if p ∼ U n is uniform, REJECT if d T V (p, U n ) ≥ ε m ← Θ √ n ρε 2 log n ρ + 1 ρ 2 ε 2 , m 0 ← Θ (log 1/ρ). for 1 ≤ j ≤ m 0 do D j gets m samples from p S j ← 1 2 n i=1 Xi m -1 n where X i is the occurrences of i ∈ [n] in D j S median ← median of {S j } µ(U n ) is expectation of 1 2 n i=1 Xi m -1 n under uniform distribution. Set threshold r ← µ(U n ) + r 0 • R (R given by Lemma 3.1) where r 0 ← Unif 1 4 , 3 4 . return ACCEPT if S median < r. Reject otherwise. around its expectation µ(p) = E p [S]in the sublinear (m < n) and superlinear (m ≥ n) cases respectively. For the superlinear case, we bound the sensitivity of S with respect to the input sample set T and apply McDiarmid's inequality to obtain the desired concentration result. Lemma 3.2 (Superlinear Concentration). Assume that we are in the superlinear regime (i.e., m ≥ n). Denote by µ(p) the expectation of the test statistic S under the distribution p.If n ≤ m ≤ n ε 2 , then Pr |S median -µ(p)| ≥ ρ C 16 ε 2 m n < ρ 4 . If n ε 2 ≤ m, then Pr |S median -µ(p)| ≥ ρ C 16 ε < ρ 4 .For the sublinear case, we provide a proof sketch below, deferring the details to Appendix A.Lemma 3.3 (Sublinear Concentration). Suppose m ≤ n. If Var(S) ≥ (C/64)ρ 2 ε 4 m 4 n -4 , then E [S] -Var(S) > µ(U n ) + Cε 2 m 2 n -2where µ(U n ) is the expectation of S under the uniform distribution and C is given by Lemma 3.1. As a consequence, with probability at least 1 -ρ/4, we haveS median > µ(U n ) + Cε 2 m 2 n -2 .On the other hand, if Var(S)≤ (C/64)ρ 2 ε 4 m 4 n -4 , then it holds that Pr |S median -µ(p)| ≥ (C/16)ρε 2 m 2 n -2 < ρ/4. Furthermore, for the uniform distribu- tion U n , Var(S) ≤ (C/64)ρ 2 ε 4 m 4 n -4 .Proof Sketch. In the proof sketch, for simplicity, we assume that ε is some small constant and ignore its dependency. When Var(S) is small, we simply apply Chebyshev's inequality to obtain the desired concentration of S. The concentration of S median then follows from the standard median trick.In the rest of the sketch we focus on the case Var(S) ≥ (C/64)ρ 2 ε 4 m 4 n -4 . In this case, the key is to show thatE [S] -Var(S) > µ(U n ) + Cε 2 m 2 n -2(3) as the claim S median > µ(U n ) + Cε 2 m 2 n -2 with high probability follows almost immediately by an application of Chebyshev's inequality (and the standard analysis for the median trick).Towards Equation (3), define X i as the number of occurrences of element i ∈ [n]. We begin with an observation from [16] stating that the test statistic S = Z/n where Z = |{i s.t. X i = 0}| denotes the number of "empty" buckets. Furthermore, we can write Z = n -m + m i=1 Y i where Y i indicates whether the i-th sample collides with a previous sample j < i. Then, Var(S) = Var(Z)/n 2 = Var( Y i )/n 2 . To bound the variance, we argue that the indicators Y i are "almost" negatively correlated using correlation inequalities (specifically Kleitman's Theorem Lemma A.8), so that (roughly)Var( Y i ) ≪ i Var(Y i ) ≪ E [Y i ] (see Lemma A.5 for the accurate statement). Observe that under U n , we have E [Y i ] ≤ m 2 n -1 so that E [S] -µ(U n ) ≥ E [ Y i ] /n -m 2 /n 2 . It follows that E [S] -Var(S) -µ(U n ) ≥ E Y i -E Y i /n -(m 2 /n 2 ).Y i ] ≥ n 2 Var(S) ≫ ρ 2 ε 4 m 4 n -2 ≫ 1 so that it suffices to show E [ Y i ] ≫ (C + 1)m 2 /n. Since Var(S) ≥ (C/64)ρ 2 ε 4 m 4 n -4 which is further bounded from below by m 2 /n 3 whenever m ≫ √ nε -2 ρ -1 we conclude E [ Y i ] ≥ n 2 Var(S) ≫ m 2 /n.We are now ready to show Theorem 1.3 -our main algorithmic result. We begin with correctness for the uniform distribution. Suppose m ≤ n. By Lemma 3.3, S median ≤ µ(U n ) + R/16 ≤ µ(U n ) + R/4 ≤ r with probability at least 1 -ρ 4 so the algorithm outputs ACCEPT. Otherwise, if n ≤ m, we have by Lemma 3.2 that with probability at least1 -ρ 4 , S median ≤ µ(U n ) + R/16 ≤ µ(U n ) + R/4 ≤r so that the algorithm outputs ACCEPT.On the other hand, suppose ξ = d T V (p, U n ) ≥ ε. We note that the algorithm of [16] computes the test statistic S using Θ ( n log(1/ρ) + log(1/ρ))ε -2 samples and compares S with some fixed threshold R that is strictly larger than the random threshold r of our choice. By the correctness guarantee of their algorithm, it holds that Pr[S > R] ≥ 1 -ρ/100, which further implies thatPr[S med > R > r] ≥ 1 -ρ/4.We now proceed to replicability. Consider two executions of the algorithm. If p is uniform or ξ = d T V (p, U n ) ≥ ε, then following a union bound on the correctness condition, two executions of the algorithm output different values with probability at most ρ/2. Then, suppose m ≤ n and Var(S) ≥ (C/64)ρ 2 ε 4 m 4 n -4 . By Lemma 3.3, both samples lead the algorithm to output REJECT with probability at least 1 -ρ so that the algorithm is ρ-replicable.Otherwise, Lemma 3.2 and Lemma 3.3 guarantees strong concentration of the test statistic S median . In particular, with probability at least 1 -ρ/2, we have |S median -µ(p)| ≤ ρ 16 R over both samples, where R is the expectation gap defined as in Equation ( 2). In particular, whenever the random threshold r does not fall in the interval (µ(p) ± ρR/16) both executions output the same result. Since r is chosen uniformly at random, this occurs with probability at most (ρR/8)/(R/2) = ρ/4. By a union bound, we observe that Algorithm 1 is ρ-replicable.Finally, the sample complexity is immediately obtained by our values of m • m 0 .• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: While the paper focuses on foundational research, replicable uniformity testing is aimed towards building an algorithmic framework for replicability in scientific analysis, helping build an efficient procedure to verify experimental procedures are followed correctly and building public trust in science. The authors are not aware of any potential negative impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
lower bound for replicable uniformity testing: 
 In this section, we outline the important lemmas used in showing the sample complexity lower bound for ρ-replicable symmetric uniformity testers, and give their proof sketches. The formal argument can be found in Appendix B.Note that the lower bound Ω ε -2 ρ -2 holds even for testing whether the bias of a coin is 1/2 or 1/2 + ε (see [30] ). We therefore focus on the more challenging bound of Ω √ nε -2 ρ -1 . Consider the canonical hard instance for uniformity testing where half of the elements have probability mass (1 + ξ)/n and the other half have probability mass (1 -ξ)/n:p(ξ) i = 1+ξ n if i mod 2 = 0 , 1-ξ n otherwise. (4)Our hard instance for replicable uniformity test is as follows: we choose ξ from the interval [0, ε] uniformly at random, and let the tester observe samples from p(ξ).Fix some uniformity tester A m that takes m samples. We will argue that if A m is ρ-replicable and correct with probability at least 0.99, then we must have m = Ω( √ nε -2 ρ -1 ).At a high level, we follow the framework of [30] . First, we fix some good random string r such that the induced deterministic algorithm A m (; r) is replicable with probability at least 1 -10ρ, and is correct on p(0) and p(ε) with probability at least 0.99. Then, consider the function Acc m (ξ) that denotes the acceptance probability of A m (S; r) when the samples S are taken from p(ξ).Note that Acc m (ξ) must be a continuous function. Moreover, by the correctness of A m (; r), it holds that Acc m (0) ≥ 0.99 and Acc m (ε) < 0.01. Hence, there must be some value ξ * such that Acc m (ξ * ) = 1/2. To show the desired lower bound on m, it suffices to show that Acc m (ξ * + δ) must not be too far from Acc(ξ * ) for any δ≪ ερ if m = õ( √ nε -2 ρ -1 ). Proposition 4.1 (Lipschitz Continuity of Acceptance Probability). Assume that m = õ( √ nε -2 ρ -1). Let A m (; r) be a deterministic symmetric tester that takes m samples, and define the acceptance probability function Acc m (ξ) = Pr S∼p(ξ) ⊗m [A(S; r) = 1] , where p(ξ) is defined as in Equation (4).Let ε 0 < ε 1 ∈ (0, ε) be such that ε 1 -ε 0 < ερ. Then it holds that |Acc m (ε 0 ) -Acc m (ε 1 )| < 0.1.Given the above proposition, since we choose ξ from [0, ε] uniformly at random, it follows that the acceptance probability of the algorithm is around 1/2 with probability at least Ω(ρ) if m = õ( √ nε -2 ρ -1 ), implying that the algorithm is not O(ρ)-replicable. The proof of Proposition 4.1 is based on an information theoretic argument based on ideas developed in [29] . We defer the formal proof of Proposition 4.1 to Appendix B.3 and give its proof outline below. Let m, ε 0 , ε 1 be defined as in Proposition 4.1. At a high level, we construct two families of probability distributions, which we denote by M 0 and M 1 , that satisfy the following properties: (i) M i contains distributions that are identical to p(ε i ) up to domain element relabeling. (ii) Any tester that uses at most m samples cannot effectively distinguish between a random probability distribution from M 0 and a random one from M 1 . For the sake of contradiction, assume that there is a deterministic symmetric tester using m samples such that the acceptance probabilities on p(ξ) and p(ξ + δ) differ by at least 0.1. Since all distributions within M 0 are identical to p(ξ) up to element relabeling, it follows that the acceptance probabilities of the symmetric tester on any of the distribution within M 0 must be the same (and similarly for M 1 ). This then further implies that the tester can successfully distinguish a random distribution from M 0 versus one from M 1 , contradicting property (ii). Proposition 4.1 thereby follows.It then remains to construct the two families of distributions. Recall that M i contains distributions that are identical to p(ε i ) up to element relabeling. We will consider all distributions that can be obtained by performing "local swaps" on p(ε i ). In particular, we first group the elements into n/2 many adjacent pairs, and then randomly exchange the labels within each pair.Let n be an even number, and p be a probability distribution on [n]. We define the Local Swap Family of p as the set of all distributions p such that(p(ε i ) j , p(ε i ) j+1 ) = (p(ε i ) j , p(ε i ) j+1 ) or (p(ε i ) j , p(ε i ) j+1 ) = (p(ε i ) j+1 , p(ε i ) j ) for all odd numbers j ∈ [n]. Lemma 4.3 (Indistinguishable Distribution Families). Let m = õ( √ nε -2 ρ -1), and ε 0 < ε 1 ∈ (0, ε) be such that ε 1 -ε 0 < ερ. Let p(ε 0 ), p(ε 1 ) be defined as in Equation (4), and M 0 , M 1 be the Local Swap Families (see Definition 4.2) of p(ε 0 ), p(ε 1 ) respectively. Let S be m samples drawn from either a random distribution from M 0 or a random one from M 1 . Given only S, no algorithm can successfully distinguish between the two cases with probability more than 0.6.The formal proof of Lemma 4.3 can be found in Appendix B.2. At a high level, we use an information theoretic argument. In particular, we consider a stochastic process where we have a random unbiased bit X that controls whether we sample from a random distribution from M 0 or a random distribution from M 1 . Let T be the obtained sample set. We show that T and X has little mutual information. A simple application of the data processing inequality then allows us to conclude the proof. To simplify the computation involved in the argument, we will also apply the standard "Poissonization" trick. In particular, we assume that the algorithm draws Poi (m) many samples instead of exactly m samples. The advantage of doing so is that we can now assume that the random variables counting the number of occurrences of each element are mutually independent conditioned on the probability distribution from which they are sampled. Moreover, one can show that this is without loss of generality by a standard reduction-based argument using the fact that Poisson distributions are highly concentrated. The formal statement of the mutual information bound is provided below. Lemma 4.4. Let M 0 , M 1 be defined as in Lemma 4.3. Let X be a random unbiased bit, p a random probability distribution from M X , and S be Poi (m) many samples from p. Moreover, let M i be the occurrences of element i among S. Then it holds thatI(X : M 1 , • • • , M n ) = O ε 4 ρ 2 m 2 n log 4 (n) + o(1).To show Lemma 4.4, we first note that if we group the random variables into n/2 many adjacent pairs, the pairs (M i , M i+1 ) are conditionally independent and identical given X. Therefore, we can bound I(X :M 1 , • • • , M n ) from above by n 2 I(X : M 1 , M 2 ).To tackle I(X : M 1 , M 2 ), we break into three regimes depending on the relative sizez of m, n, ε: the sub-linear regime (approximately m ≪ n), the super-linear regime (approximately n < m < n/ε 2 ), and the super-learning regime (approximately m > n/ε 2 ). The formal proofs involves writing the probability distributions of M i s as Taylor expansions in ε. The calculations are rather technical and therefore deferred to Appendix B.1.We now prove the required lemmas for Theorem 1.3. This section is dedicated to proving the required lemmas regarding the concentration properties of S median .Superlinear Case: m ≥ n First, we consider the superlinear case, when m ≥ n. Lemma 3.2 (Superlinear Concentration). Assume that we are in the superlinear regime (i.e., m ≥ n). Denote by µ(p) the expectation of the test statistic S under the distribution p.If n ≤ m ≤ n ε 2 , then Pr |S median -µ(p)| ≥ ρ C 16 ε 2 m n < ρ 4 . If n ε 2 ≤ m, then Pr |S median -µ(p)| ≥ ρ C 16 ε < ρ 4 .Proof. Recall that Algorithm 1 uses the median trick to boost the success probability. Here we focus on the test statistic S := S j computed in a single iteration j ∈ [m 0 ]. An essential tool in the analysis is McDiarmid's Inequality.Theorem A.1 (McDiarmid's Inequality). Let X 1 , . . . , X m be independent random variables taking values in X . Let f : X m → R be a function such that for all pairs of tuples(x 1 , . . . , x m ), (x ′ 1 , . . . x ′ m ) ∈ X m such that x i = x ′ i for all but one i ∈ [m], |f (x 1 , . . . , x m ) -f (x ′ 1 , . . . , x ′ m )| ≤ B, Then, Pr (|f (X 1 , . . . , X m ) -E [f (X 1 , . . . , X m )]| ≥ t) < 2 exp - 2t 2 mB 2 .Observe that the samples T j are independent and a change in T j changes S by at most 1 m , since at most two values X i change by at most 1 2m each. Then, applying Theorem A.1 to S = f (T 1 , . . . , T m ), we obtainEQUATION)When n ≤ m ≤ n ε 2 , we can concludePr |S -µ(p)| ≥ ρ • C 16 • ε 2 m n < 2 exp - 2C 2 ρ 2 ε 4 m 2 16 2 n < 1 10 .The first inequality follows from Equation ( 5) and the second holds whenever m ≥ Θ √ n ρε 2 for some sufficiently large constant factor. Finally, we show S median is concentrated with high probability, i.e.Pr |S median -µ(p)| ≥ ρ • C 16 • ε 2 m n < ρ 4 .Note that the median fails to satisfy the concentration condition only if at least half of the intermediate statistics S j do not satisfy the concentration condition. By a Chernoff bound, this occurs with probability at most ρ for m 0 = Θ log 1 ρ a sufficiently large constant. Now consider the case m ≥ n ε 2 . NoteEQUATIONwhenever m ≥ Θ 1 ρ 2 ε 2 .Concentration of S median then follows from a similar argument as above.We now consider the sublinear case. Again, we consider a single iteration j and examine the concentration of the test statistic S = S j . Following an observation from [16] , we rewrite the test statistic asS = 1 2 i=1 X i m - 1 n = 1 2 i=1 X i m - 1 n + 2 n • 1[X i = 0] = 1 n |{i s.t. X i = 0}| = Z n ,where we define the random variable Z = |{i s.t. X i = 0}|.Our goal now is to bound the variance of Z. To do so, we further define some useful random variables.Preliminaries Let T ∈ [n] m be the m samples drawn, i.e., T i denotes the element corresponding to the i-th sample. We use Y 1 , . . . , Y m to denote whether the i-th sample collides with any samples j < i, i.e., Y i = 1 if and only if there exists some j < i such that T i = T j . We will consider decomposition of the domain into "heavy" and "light" elements. Definition A.2. Let p be a distribution on We define Ỹ1 , . . . , Ỹm to indicate that the i-th sample comes from some light element and collides with some previous sample: Ỹi = Y i 1{b Ti = 0}. Let H denote the number of occurrences of heavy elements among the samples: H = |i s.t. b Ti = 1|. Finally, define Z H , Z L to be the contributions to Z from heavy and light elements respectively:[n]. For each k ∈ [n], k is heavy if p k ≥ 3 m logZ H = |{i s.t. b k = 1 and X i = 0}| Z L = |{i s.t. b k = 0 and X i = 0}|.We then show the following. n 2 ≤ ρ 3 500n 2 + 32 n 2 log 10n ρ m i=1 E [Y i ].Proof of Lemma A.3. Recall the random variables Y 1 , . . . , Y m to indicate whether the i-th sample collides with any samples j < i. Then, we obtain the following identities:Z = n -m + m i=1 Y i = Z H + Z L Z H = |{i s.t. X i = 0 and b i = 1}| Z L = |{i s.t. X i = 0 and b i = 0}| = n L -(m -H) + m i=1Ỹi ,We will bound the variance of Z H , Z L separately. First, we note that Z H = 0 with high probability.In particular, the probability that an element with b k = 1 does not occur in m samples is at mostEQUATION3 , so that applying the union bound the probability that some heavy element does not occur is at most ρ 3 1000n 2 , showing Pr(Z H > 0) < ρ 3 1000n 2 . In particular,Var(Z H ) ≤ n ℓ=0 Pr(Z H = ℓ)ℓ 2 ≤ n 2 ρ 3 1000n 2 ≤ ρ 3 1000 .In the remaining proof, we bound the variance of Z L . To bound the variance of Z L , we separately bound the variance of H and m i=1 Ỹi , since n L , m are fixed constants. We begin with the first term, beginning with an upper bound on the expectation of H. We show the expected number of heavy elements is at most a constant multiple of the expected number of collisions.Lemma A.4.4 m i=1 E [Y i ] ≥ m b k =1 p k = E [H] ≥ Var(H).Proof of Lemma A.4. Note that H is a binomial random variable so that its expectation is an upper bound on its variance. Since the Y i are non-negative random variables and E [Y i ] is increasing in i, it suffices to show the following lower bound:4 m i=1 E [Y i ] ≥ 4 m i=m/2 E [Y i ] ≥ 2mE Y m/2 ≥ m b k =1 p k ,or equivalentlyE Y m/2 = Pr(Y m/2 = 1) ≥ 1 2 b k =1 p k .Consider an element k such that b k = 1 or equivalently p k ≥ 3 m log 10n ρ . Then, the probability that k does not occur in the first m/2 samples is at most (ρn -1 /10) Proof. Using linearity of expectation, we haveE   m i=1 Ỹi 2   = m i=1 E Ỹ 2 i + i̸ =j E Ỹi Ỹj .For the first term, E Ỹ 2 i = E Ỹi since Ỹi is an indicator variable. Considering the second term, we introduce the variables Z i,j denoting whether the i-th and j-th samples collide, i.e.Z i,j = 1[T i = T j ].We can write E Ỹi Ỹj = Pr( Ỹi Ỹj = 1) = Pr( Ỹi Ỹj = 1, Z i,j = 1) + Pr( Ỹi Ỹj = 1, Z i,j = 0).We now bound the first term.Lemma A.6.i̸ =j Pr( Ỹi Ỹj Z i,j = 1) ≤ 3 log 10n ρ m i=1 E Ỹi ≤ 3 log 10n ρ m i=1 E [Y i ]Proof of Lemma A.6. The event Ỹi , Ỹj = 1, Z i,j = 1 happens when there is some element k ∈[n] such that 1. b k = 0 2. both samples T i = T j = k3. some samples from T <i falls in k. We denote this event as E i,k .We compute as follows:Pr( Ỹi Ỹj Z i,j = 1) = b k =0 Pr(E i,k = 1) Pr(T i = k) Pr(T j = k) = b k =0 Pr(E i,k = 1)p 2 k ≤ 3 m log 10n ρ b k =0 p k Pr(E i,k = 1) = 3 m log 10n ρ E Ỹiwhere in the inequality we have used b k = 0 gives an upper bound on p k . Then, for each i we sum over m -1 ≤ m indices j ̸ = i to conclude the proof.For the second term, we argue it can be upper bounded by Pr( Ỹi = 1) Pr( Ỹj = 1) with Kleitman's Lemma. We define monotonically increasing and decreasing subsets.Definition A.7. Let x, y ∈ {0, 1, 2} n . We say x ⪯ y is x i ≤ y i for all i ∈ [n]. A subset S ⊂ {0, 1, 2} n is monotonically increasing if x ∈ S and x ⪯ y implies y ∈ S. S is monotonically decreasing if x ∈ S and y ≤ x implies y ∈ S.In fact, we require a small modification of Kleitman's Lemma.Lemma A.8 (Kleitman's Lemma [2] ). Let Q be a distribution over random bit strings {0, 1, 2} n . Let A, B be two subsets of {0, 1, 2} n such that A is monotonically increasing and B is monotonically decreasing. Then, it holdsPr (A(Q)B(Q)) ≤ Pr (A(Q)) Pr (B(Q)) ,where A(Q), B(Q) denotes the event that a random string draw from Q lies in A, B.Proof. Kleitman's Lemma is proven for distributions over random bit strings {0, 1} n , or equivalently subsets of [n], replacing the ⪯ relation with ⊆ inclusion. Given a distribution Q over {0, 1, 2} n , we design a distribution Q ′ over [2n] as follows. Let v ∈ {0, 1, 2} n . We map v to the subset S = n i=1 S i where Note that we can add sets with probability 0 under Q ′ to A ′ (resp. B ′ ) to ensure that they are monotonically increasing (resp. decreasing) without changing Pr(A ′ ) (resp. Pr(B ′ )). In particular, suppose there is a setS i = ∅ if v i = 0, S i = {2i} if v i = 1 and S i = {2i -1, 2i} if v i = 2.X ∈ A ′ and Y ̸ ∈ A ′ such that X ⊂ Y . Since A is a monotonically increasing subset of {0, 1, 2} n , Y ̸ ∈ A ′ implies that Y i = {2i -1} for some i ∈ [n],but this set has probaility 0 under the distribution Q ′ , so we can safely add it to A ′ . In particular, applying Kleitman's Lemma [2] , we obtainPr (A(Q)B(Q)) = Pr (A ′ (Q ′ )B ′ (Q ′ )) ≤ Pr (A ′ (Q ′ )) Pr (B ′ (Q ′ )) = Pr (A(Q)) Pr (B(Q)) .Using Lemma A.8, we bound the collision probability of distinct buckets.Lemma A.9. For i ̸ = j, we have Pr( Ỹi Ỹj = 1, Z i,j = 0) ≤ Pr( Ỹi = 1) Pr( Ỹj = 1).Proof of Lemma A.9. Without loss of generality, we assume i < j. Recall T <i = (T 1 , . . . , T i-1 ).The event Ỹi Ỹj = 1, Z i,j = 0 happens when there exists two distinct elements k ̸ = ℓ ∈ [n] such that:1. the i-th sample is S i = k, the j-th sample is S j = ℓ 2. some samples from S <i fall in k, some samples from S <j fall in ℓ. We denote the two events as E i,k and E j,ℓ respectively.Hence, we can writeEQUATIONFix a pair of k < ℓ. Consider the string β (k,ℓ) such that β(k,ℓ) i = 0 if the i-th sample falls in the k-th bucket, β (k,ℓ) i = 1 if the i-th sample fall in neither k-th nor ℓ-th bucket, β (k,ℓ) i= 2 if the i-th sample falls in the ℓ-th bucket. Then, both events E i,k , E j,ℓ are completely determined by the string β (k,ℓ) . Moreover, the set of strings for which E i,k holds is monotonically decreasing and the set of strings for which E j,ℓ holds is monotonically increasing. As a result, from Lemma A.8 we havePr(E i,k E j,ℓ ) ≤ Pr(E i,k ) Pr(E j,ℓ ).Pr( Ỹi Ỹj = 1, Z i,j=0 ) ≤ k̸ =ℓ Pr(E j,ℓ ) Pr(E i,k )p k p ℓ ≤ k Pr(E i,k )p k ℓ Pr(E j,ℓ )p ℓ ≤ Pr( Ỹi = 1) Pr( Ỹj = 1).To bound the total contribution to the variance of the second term, we sum and obtain i̸ =jPr( Ỹi Ỹj = 1, Z i,j=0 ) ≤ i̸ =j E Ỹi E Ỹj . Note that i̸ =j E Ỹi E Ỹj is at most E Ỹi 2, so that we bound the variance asVar Ỹi = E Ỹi 2 -E Ỹi 2 ≤ 1 + 3 log 10n ρ E [Y i ] + i̸ =j E Ỹi E Ỹj -E Ỹi 2 ≤ 1 + 3 log 10n ρ E [Y i ] .We thus obtain the following bound on the variance of Z, proving Lemma A.3. In particular,Var(Z) ≤ 2 (Var(Z H ) + Var(Z L )) ≤ ρ 3 500 + 4 Var(H) + Var m i=1 Ỹi ≤ ρ 3 500 + 20 m i=1 E [Y i ] + 12 log 10n ρ m i=1 E [Y i ] ≤ ρ 3 500 + 32 log 10n ρ m i=1 E [Y i ] .We are now ready to prove the required lemma. Lemma 3.3 (Sublinear Concentration). Suppose m ≤ n. If Var(S) ≥ (C/64)ρ 2 ε 4 m 4 n -4 , thenE [S] -Var(S) > µ(U n ) + Cε 2 m 2 n -2where µ(U n ) is the expectation of S under the uniform distribution and C is given by Lemma 3.1. As a consequence, with probability at least 1 -ρ/4, we haveS median > µ(U n ) + Cε 2 m 2 n -2 .On the other hand, if Var(S) ≤ (C/64)ρ 2 ε 4 m 4 n -4 , then it holds that Pr |S median -µ(p)| ≥ (C/16)ρε 2 m 2 n -2 < ρ/4. Furthermore, for the uniform distribution U n , Var(S) ≤ (C/64)ρ 2 ε 4 m 4 n -4 . Proof. Our proof considers two sub-cases. In particular, we argue that when the variance of the test statistic S is large, the algorithm replicably outputs REJECT. On the other hand, when variance is small, the test statistic S is tightly concentrated.High Variance -Var(S) ≥ (C/64)ρ 2 ε 4 m 4 n -4We argue that when the variance of the test statistic is high, the test statistic must also be large with high probability so that the algorithm replicably outputs REJECT.First, let us consider the expectation of the test statistic if the input distribution is uniform.Lemma A.10. Suppose m ≤ n. Let µ(U n ) be the expectation of S given a sample from U n . Thenn • µ(U n ) ≤ n -m + m 2 n .Proof of Lemma A.10. For each i, note that there are at most m distinct elements sampled before the i-th sample. In particular, E [Y i ] = Pr(Y i = 1) ≤ m n for all i. Then, since in the sub-linear regime m ≤ n we have the identitiesS = Z n Z = n -m + m i=1 Y i .We can write the expectation of S asµ(U n ) = E [S] = E [Z] n = n -m + m i=1 E [Y i ] n so that n • µ(U n ) = n -m + m i=1 E [Y i ] ≤ n -m + m 2 n .Now, we show that when the variance of S is large, with probability at least 9 10 ,S ≥ µ(U n ) + Cε 2 m 2 n 2where C is the constant given by Lemma 3.1. Since S = Z n , this holds if and only ifEQUATIONThe expectation of Z isE [Z] = n -m + m i=1 E [Y i ] .From Lemma A.3, we haveVar(Z) = O ρ 3 + log(n/ρ) m i=1 E [Y i ]. By Chebyshev's inequality, we have thatPr Z < E [Z] -10Var(Z) < 1 10.[Z] -10Var(Z) ≥ n • µ(U n ) + Cε 2 m 2 n 2 .If this holds, then S is beyond the random threshold and the algorithm outputs REJECT. We rearrange the desired inequality as follows:E [Z] -10Var(Z) ≥ n • µ(U n ) + Cε 2 m 2 n 2 E [Z] -n • µ(U n ) -10Var(Z) ≥ Cε 2 m 2 n 2 .Plugging inE [Z] -n • µ(U n ) ≥ m i=1 E [Y i ] -m 2 n , it suffices to show m i=1 E [Y i ] - m 2 n -10Var(Z) ≥ Cε 2 m 2 n ,which is true as long asm i=1 E [Y i ] -10Var(Z) ≥ 2C m 2 n .Thus, applying Lemma A.3, it remains to showm i=1 E [Y i ] - ρ 3 50 + 320 log 10n ρ m i=1 E [Y i ] ≥ m i=1 E [Y i ] -1 -320 log 10n ρ m i=1 E [Y i ] ≥ 2C m 2 n . since √ a + b ≤ √ a + √ b and ρ 3 /50 ≪ 1.Finally, we observe that by our choice of m, we have2Cm 2 n -1 ≫ 1 so that it suffices to show m i=1 E [Y i ] -320 log 10n ρ m i=1 E [Y i ] ≥ 3C m 2 n .We simplify the left hand side with the following lemma.Lemma A.11. For any x ≥ 1280 log 10n ρ , we havex -320 log 10n ρ x ≥ x 2 .Proof. Suppose x ≥ 320 log 10n ρ . Then the inequality holds if and only ifx 2 ≥ 320 log 10n ρ x √ x ≥ 2 320 log 10n ρ x ≥ 1280 log 10n ρ .We now lower bound By assumption on Var(S) ≥ (C/64)ρ 2 ε 4 m 4 n -4 , we obtainm i=1 E [Y i ] ≥ (C/64)ρ 2 ε 4 m 4 n -2 -ρ 3 /500 32 log(10n/ρ) .Finally, since m ≫ √ nρ -1 ε -2 log(n/ρ) for some sufficiently large constant, we have(C/64)ρ 2 ε 4 m 4 n -2 -ρ 3 /500 ≫ log 2 (n/ρ) ρ 2 ε 4 .Then,m i=1 E [Y i ] ≫ log 2 (n/ρ) ρ 2 ε 4 log(n/ρ) ≥ 1280 log n ρ .Thus, we conclude bym i=1 E [Y i ] -320 log 10n ρ m i=1 E [Y i ] ≥ 1 2 m i=1 E [Y i ] ≥ 2C m 2 n .where the final equality follows fromEQUATIONandm 2 n = O log(n/ρ) ρ 2 ε 4 .and if we choose an arbitrary large constant factor of m, left hand side E [Y i ] takes this constant to the 4th power while the right hand side takes this constant to the 2nd power.Thus, whenever the variance of S is large, the test statistic S lies above any random threshold with probability at least 9 10 . Again applying a Chernoff bound, S median does not lie above any random threshold with probability at most ρ 4 . For the high variance case, it remains to show the inequalityE [S] -Var(S) ≥ µ(U n ) + Cε 2 m 2 n 2 .From the identities S = Z/n and Z = n -m + Y i , Lemma A.3 and Lemma A.10, we can rewrite the above equation asE [Y i ] -m 2 /n n - ρ 3 500n 2 + 32 n 2 log 10n ρ E [Y i ] ≥ Cε 2 m 2 n 2and we can lower bound the left hand side asE [Y i ] -m 2 n n - 1 n - 32 n 2 log 10n ρ E [Y i ] ≥ E [Y i ] -32 log 10n ρ E [Y i ] n - m 2 n 2 - 1 n ≥ E [Y i ] 2n - m 2 n 2 - 1 nwhere we obtain the first term by using √ a + b ≤ √ a + √ b and ρ 3 /(500n 2 ) ≤ n -2 , the second term by grouping similar terms, and the final term by our assumption on Var(S) and thereforeE [ Y i ]. Therefore, it suffices to show E [Y i ] ≥ 1 + m 2 n + Cε 2 m 2 n .or since m 2 n -1 ≫ 1,E [Y i ] ≥ 4 max(C, 1)m 2 n which follows from the lower bound on E [Y i ] given by Equation (8) . We now show that whenever the number of expected collisions is low, the test statistic is well concentrated. By Chebyshev's inequality, we have for any iteration j thatPr |S j -µ(p)| > C 16 ρε 2 m 2 n 2 = Pr |S j -µ(p)| > 4 • C 64 ρε 2 m 2 n 2 < 1 10.Using a Chernoff bound as previously, we obtain the same concentration result for S median with high probability.Finally, we show that for the uniform distribution U n , we haveVar(S) ≤ (C/64)ρ 2 ε 4 m 4 n -4 .We observe that for the uniform distribution, E [Y i ] ≤ m n since the i-th sample can collide with at most i ≤ m elements before it and thereforem i=1 E [Y i ] ≤ m 2n . Then, from Lemma A.3,Var(S) = Var(Z) n 2 ≤ 24 log(10n/ρ) n 2 m i=1 E [Y i ] ≤ 24m 2 log(10n/ρ) n 3 .We thus require24m 2 log(10n/ρ) n 3 ≤ (C/64)ρ 2 ε 4 m 4 n -4 1536n log(10n/ρ) Cρ 2 ε 4 ≤ m 2 √ n ρε 2 log n ρ ≪ mwhich is satisfied by our sample complexity m. We begin by bounding the mutual information of the sub-linear regime.EQUATION)Proof. First, let us expand the conditional probabilities for a fixed a, b. Expanding the definition of the random variables M 1 , M 2 , X and applying the probability mass function of Poisson distributions, we arrive at the expressionPr(M 1 = a, M 2 = b | X = 0) = 1 2a!b! exp - 2m n m n a+b (1 + ε 0 ) a (1 -ε 0 ) b + (1 -ε 0 ) a (1 + ε 0 ) b , Pr(M 1 = a, M 2 = b | X = 1) = 1 2a!b! exp - 2m n m n a+b (1 + ε 1 ) a (1 -ε 1 ) b + (1 -ε 1 ) a (1 + ε 1 ) b Define the function f a,b (x) := (1 + x) a (1 -x) b + (1 -x) a (1 + x) b .Then we have a,b∈NEQUATION)where in the last line we use the mean value theorem. The main technical step will be to bound from above the quantityEQUATION. Specifically, we show the following technical claim.There exists an absolute constant C such thatmax ε0<x<ε1 ∂ ∂x f a,b (x) 2 (f a,b (ε 0 ) + f a,b (ε 1 )) = C        0 if a + b ≤ 1 (a 4 + b 4 )ε 2 if 1 < a + b ≤ ε -1 /2 (a + b) 2 1+ε 1-ε a+b if a + b > ε -1 /2. Proof. If a + b ≤ 1, f a,b (x) = 2. Thus, d dx f a,b (x) = 0, which gives the first case. We next analyze the case 2 ≤ a + b ≤ ε -1 . Note that f a,b (x) is an even function with respect to x, i.e., f a,b (x) = f a,b (-x). This allows us to write f a,b (x) = 1 2 (f a,b (x) + f a,b (-x)).As a result, we can conclude that f a,b (x) does not contain any monomial of x with odd degree. Thus, we can writef a,b (x) = c (0) a,b + d∈[a+b] is even c (d) a,b x dfor some coefficients c EQUATIONTo finish the analysis for this case, it then suffices to bound from below f a,b (ε 0 ) + f a,b (ε 1 ). Without loss of generality, assume that a ≤ b. Then we haveEQUATION)where the last inequality follows from a ≤ a + b < ε -1 /2 and ε 1 < ε. Combining Equation (11) and Equation ( 12) then concludes the proof of the second case.Lastly, we analyze the case (a + b) > ε -1 /2. In this case, for ε 0 ≤ x ≤ ε 1 , we note that∂ ∂x f a,b (x) = (1 + x) a (1 -x) b a 1 + x - b 1 -x + (1 -x) a (1 + x) b b 1 + x - a 1 -x .It then follows thatEQUATIONwhere in the first inequality we use that |u -v| ≤ u + v for any u, v > 0, and the second inequality simply follows from 1 -x < 1. We can therefore conclude thatmax ε0≤x≤ε1 ∂ ∂x f a,b (x) 2 f a,b (ε 0 ) + f a,b (ε 1 ) ≤ O(1)(a + b) 2 (1 + ε 1 ) a + (1 + ε 1 ) b 2 (1 + ε 1 ) a (1 -ε 1 ) b + (1 + ε 1 ) b (1 -ε 1 ) b ≤ O(1)(a + b) 2 (1 + ε 1 ) a (1 -ε 1 ) b + (1 + ε 1 ) b (1 -ε 1 ) a ≤ O(1)(a + b) 2 1 + ε 1 1 -ε 1 a+b ,where in the first inequality we bound from above the numerator with the square of the right hand side of Equation ( 13) substituted with x = ε 1 , and bound from below the denominator by f a,b (ε 1 ), in the second inequality we use the fact that (u + v) 2 ≤ 2u 2 + 2v 2 , and in the last inequality we use that (1 + ε 1 ) a , (1 -ε 1 ) -a are increasing in a and (1 + ε 1 ) b , (1 -ε 1 ) -b are increasing in b. This concludes the proof of the third case and also Claim B.2.It immediately follows from the claim that a,b:a+b<2EQUATION)Consider the terms with 2 ≤ a + b ≤ ε -1 /2. From Equation ( 10) and Claim B.2, we have that So we focus on the term A. We have thata,b:2≤a+b≤ε -1 /2 (Pr(M 1 = a, M 2 = b | X = 0) -Pr(M 1 = a, M 2 = b | X = 1)) 2 Pr(M 1 = a, M 2 = b) ≤ O(1) a,b:2≤a+b≤ε -1 /2 1 a!b! exp - 2m n m n a+b (a 4 + b 4 )δ 2 ε 2 = O(δ 2 ε 2 )   a∈N b:2≤a+b≤ε -1 /2A = ε -1 /2-1 b=1 1 b! m n 1+b + a≥2 a 4 a! m n a b:b:2≤a+b≤ε -1 /2 1 b! m n b ≤ O(1) m n 2 + O(1) a≥2 a 4 a! m n a . ≤ O(1) m n 2 + O(1) exp(m/n) a≥2 exp(-m/n) a(a -1) + a(a -1)(a -2)(a -3) a! m n a ≤ O(1) m n 2 + O(1) exp(m/n) E y∼Poi(m/n) [y(y -1) + y(y -1)(y -2)(y -3)] , ≤ O(1) m n 2 .where in the first inequality we use the assumption m < n to bound from the above the summation over b by a geometric series with common ratio at most 1/2, in the second inequality we use the fact that a 4 is at most 10 (a(a -1) + a(a -1)(a -2)(a -3)) for all a ≥ 2, in the third inequality we observe that the summation over a can be bounded from above by the moments of some Poisson random variable with mean m/n, and in the last inequality we use the fact that E y∼Poi(λ) [y(y -1) + y(y -1)(y -2)(y -3)] = λ 2 + λ 4 . One can show the same upper bound for B via an almost identical argument. Substituting the bounds for A, B into Equation ( 15) then givesEQUATION)It then remains to analyze the terms where a + b ≥ ε -1 /2. Again from Equation ( 10) and Claim B.2, we have that a,b∈NEQUATION)where in the second inequality we use the observation that we must have either a ≥ s/2 or b ≥ s/2 if a + b = s, in the third inequality we note that the summation over s decreases exponentially and is therefore dominated by the term where s = ε -1 /2, and in the last inequality we use that 2(1-ε)) < 0.9, and that 0.9 ε -1 /2 ≪ poly (ε) for sufficiently small ε.s 3 / ⌈s/2⌉! ≤ O(1), (m/n) ε -1 /2 ≤ (m/n) 2 , (1+ε)/(Combining Equations ( 14), ( 16) and ( 17) then concludes the proof of Lemma B.1.We now bound the mutual information for the super-linear regime.Lemma B.3. Let δ = |ε 0 -ε 1 | and ε = max(ε 0 , ε 1 ). Let n < m < o n log 2 n ε 2 . Then, a,b∈N (Pr(M 1 = a, M 2 = b | X = 0) -Pr(M 1 = a, M 2 = b | X = 1)) 2 Pr(M 1 = a, M 2 = b) ≤ O ε 2 δ 2 m 2 log 4 n n 2 +o(1/n).Proof. We note that for a Poisson random variable y with mean λ ≥ 1, we have |y -λ| > √ λ log n with probability at most o(1/n). We can focus on the terms where l ∈[λ - √ λ log n, λ + √ λ log n].For reasons that will become clear soon, we will assume that a, b both lie in this range.As in the sub-linear case, we define the functionf a,b (x) := (1 + x) a (1 -x) b + (1 -x) a (1 + x) b .Instead of computing the derivative of f a,b directly, we will first rewrite it slightly.f a,b (x) = exp (a log(1 + x) + b log(1 -x)) + exp (a log(1 -x) + b log(1 + x)) = 2 + a log(1 -x 2 ) + b log(1 -x 2 ) + ∞ i=2 (a log(1 + x) + b log(1 -x)) i + (a log(1 -x) + b log(1 + x)) i i! ,where in the second equality we apply the Taylor approximation of the exponential function. We will analyze the expression terms by terms. In particular, defineg y (x) = y log(1 -x 2 ) , h a,b (x) = ∞ i=2 (a log(1 + x) + b log(1 -x)) i i! .Then we haveEQUATIONWe first analyze g a (x).When a ∈ [λ - √ λ log n, λ + √ λ log n],we have thatEQUATIONwhere in the first inequality we use the fact |log(x)| ≤ x -1 for x ≥ 1, in the second inequality we use our assumption that max(ε 0 , ε 1 ) ≤ ε and |ε 0 -ε 1 | ≤ δ, and our assumption that |a -m/n| < log n m/n. Using a similar argument, one can also derive thatEQUATIONWe then turn to the term h a,b (x). The derivative with respect to x is given by∂ ∂x h a,b (x) = a 1 + x - b 1 -x ∞ i=2 (a log(1 + x) + b log(1 -x)) i-1 (i -1)! = a 1 + x - b 1 -x (1 + x) a (1 -x) b -1where the second equality follows from the observation that the summation is exactly the Taylor approximation of exp (a log(1 + x) + b log(1 -x)) without the constant term. We next proceed to bound from above ∂ ∂x h a,b (x) . First, when x is sufficiently small and a, b lie in the rangeEQUATIONwhere in the first line we approximate 1 1+x and 1 1-x with 1 -O(x) and 1 + O(x) respectively for sufficiently small x, the second line follows from the triangle inequality, in the third line we use the assumption on the ranges of a, b, in the last line we note that m n log n is the dominating term when x < ε and m < n/ε 2 . Next, under the same set of assumptions, we have thatEQUATIONwhere in the second inequality we note that since bx2 = O m n ε 2 ≪ 1 and |a -b|x = O m n log(n)ε ≪ 1 we can approximate (1 -x 2 ) b and (1 + x) |a-b| by (1 -O(bx 2 )) and(1 + O(|a -b|)x) respectively, and in the last inequality we use the assumption on the range of a, b and x < ε. Thus, combining Equations ( 21) and (22) , we arrive at the upper boundmax x∈[ε0,ε1] ∂ ∂x h a,b (x) ≤ O ε m n log 2 n , when m n -m/n log n ≤ a, b ≤ m n + m/n log n.Therefore, by the mean value theorem, we have thatEQUATIONFollowing a similar argument, one can also derive the upper boundEQUATIONCombining Equations ( 18) to ( 20), ( 23) and ( 24) then gives thatEQUATIONRecall that in the proof of Lemma B.1, we have that a,b∈NEQUATIONHence, we proceed to bound from below f a,b (ε 0 ) + f a,b (ε 1 ). Note that we haveEQUATIONwhere the first inequality follows from a case analysis on whether a > b, in the second inequality we approximate(1 -x 2 ) min(a,b) by 1 -O(min(a, b)x 2 ) since min(a, b)x 2 = o(1)for a, b in the assumed range and x < ε. Combining Equations ( 25) to ( 27) then gives that a,b∈N(Pr(M 1 = a, M 2 = b | X = 0) -Pr(M 1 = a, M 2 = b | X = 1)) 2 Pr(M 1 = a, M 2 = b) ≤ O(1) a,b∈N 1 m n - m n log n ≤ a, b ≤ m n + m n log n 1 a!b! exp - 2m n m n a+b ε 2 δ 2 m n 2 log 4 n + O(1) 1 - Pr a,b∼Poi(m/n) m/n -m/n log n ≤ a, b ≤ m/n + m/n log n ≤ ε 2 δ 2 m n 2 log 4 n + o(1/n).This concludes the mutual information bound for the super-linear case.Lastly, we present the mutual information bound for the super-learning parameter regime, i.e.,m ≥ Ω n/ε 2 . Lemma B.4. Let δ = |ε 0 -ε 1 | and ε = max(ε 0 , ε 1 ). Let m > Ω n log 2 n ε 2 . Then it holds I(X : M 1 , M 2 ) ≤ O ε 2 δ 2 m 2 log 2 n n 2 .We are going to use the following facts regarding KL-divergence and mutual information. Claim B.5 (Convexity of KL-divergence). Let w ∈ (0, 1), and p 1 , p 2 , q 1 , q 2 be probability distributions over the same domain. Then it holdsKL(wp 1 + (1 -w)p 2 ||wq 1 + (1 -w)q 2 ) ≤ wKL(p 1 ||q 1 ) + (1 -w)KL(p 2 ||q 2 ).Claim B.6 (Additivity of KL-divergence). Let w ∈ (0, 1), and p 1 , p 2 , q 1 , q 2 be probability distributions such that p 1 , q 1 share the same domain and p 2 , q 2 share the same domain. Then it holdsKL(p 1 ⊗ p 2 ||q 1 ⊗ q 2 ) = KL(p 1 ||q 1 ) + KL(p 2 ||q 2 ).Claim B.7 (Mutual Informtion Identity). Let X be an indicator variable, and H 0 , H 1 be a pair of distributions. Let H be the random variable that follows the distribution of H 0 if X = 0 and X 1 if X = 1. Then it holdsI(X : H) = 1 2 KL H 0 : 1 2 (H 1 + H 0 ) + 1 2 KL H 1 : 1 2 (H 1 + H 0 ) .Proof of Lemma B.4. When X = 0, the pair (M 1 , M 2 ) is distributed as a even mixture of two distributions that are both product of Poisson distributions:(M 1 , M 2 ) | (X = 0) ∼ H 0 := 1 2 Poi m n + ε 0 m n ⊗ Poi m n -ε 0 m n + Poi m n -ε 0 m n ⊗ Poi m n + ε 0 m n .Similarly, we have(M 1 , M 2 ) | (X = 1) ∼ H 1 := 1 2 Poi m n + ε 1 m n ⊗ Poi m n -ε 1 m n + Poi m n -ε 1 m n ⊗ Poi m n + ε 1 m n .From Claim B.7 and Claim B.5, we know that it suffices to show that the KL-divergences between H 0 and H 1 are at most ε 2 δ 2 m 2 log 2 n n 2. We focus on the argument for KL(H 0 : H 1 ) as the one for KL(H 1 : H 0 ) is symmetric.By the definition of H 0 and H 1 , we have thatKL(H 0 : H 1 ) ≤ 1 2 KL Poi m n + ε 0 m n ⊗ Poi m n -ε 0 m n ||Poi m n + ε 1 m n ⊗ Poi m n -ε 1 m n + 1 2 KL Poi m n -ε 0 m n ⊗ Poi m n + ε 0 m n ||Poi m n -ε 1 m n ⊗ Poi m n + ε 1 m n . = KL Poi m n + ε 0 m n ||Poi m n + ε 1 m n + KL Poi m n -ε 0 m n ||Poi m n -ε 1 m n ,where in the first line we use Claim B.5, and in the last line we use Claim B.6.Let λ 1 > λ 2 > 0. Note that we have the following closed form for KL divergence between a pair of Poisson distributions:KL(Poi (λ 1 ) ||Poi (λ 2 )) = λ 1 log(λ 1 /λ 2 ) + λ 2 -λ 1 ≤ λ 1 λ 1 -λ 2 λ 2 + λ 2 -λ 1 = (λ 1 -λ 2 ) 2 λ 2 ,where in the first inequality we use the bound log(x) ≤ x -1 for all x > 0. Hence, it follows thatKL(H 0 ||H 1 ) ≤ m n (ε 1 -ε 0 ) 2 m n (1 + ε 1 ) ≤ O(1) m n δ 2 .But notice that this is at mostO ε 2 δ 2 m 2 log 2 n n 2as long as m ≥ Ω n/(2 log 2 (n)ε 2 ) which is our assumed parameter regime in this lemma.δ = |ε 1 -ε 0 | = O(ερ), it follows from Lemmas B.1, B.3 and B.4 that I(X : M 1 , M 2 ) ≤ O ε 2 δ 2 m 2 log 4 n n 2 +o(1/n).Since the pairs M i , M i+1 are conditional independent and have identical distributions given X, it follows thatI(X; M 1 , • • • , M n ) ≤ n 2 I(X; M 1 , M 2 ) ≤ O ε 2 δ 2 m 2 log 4 n n + o(1).This concludes the proof of Lemma 4.4.Proof. Let T be a set of samples. In case one, T is made up of m samples from a random distribution from M 0 . In case two, T is made up of m samples from a random distribution from M 1 . Assume that there exists a tester A that can distinguish between the two cases given S with probability at least 0.9. We will show that this implies that m = Ω √ nε -2 ρ -1 . Recall that Lemma 4.4 has the following setup. Let X be an unbiased binary random variable. If X = 0, S will be Poi (2m) samples from a random distribution from M 0 . If X = 1, S will be Poi (2m) samples from a random distribution from M 1 . Then we can use A to predict X given S in the following way: if S contains more than m samples, we feed A the first m samples and take its output; otherwise, we declare failure. By the concentration property of Poisson distributions, it holds that S contains more than m samples with high constant probability. Hence, the above routine will be able to correctly predict X with probability at least 0.6. This implies that the mutual information between X and S is at least Ω(1). However, Lemma 4.4 says that the mutual information is at mostO ε 4 ρ 2 m 2 n log 4 (n) + o(1).This therefore shows thatε 4 ρ 2 m 2 n log 4 (n) = Ω(1)which further implies thatm = Ω √ n log -2 (n)ε -2 ρ -1 .This concludes the proof of Lemma 4.3.Proof. Let m = õ √ nε -2 ρ -1 . For the sake of contradiction, assume that|Acc m (ε 0 ) -Acc m (ε 1 )| > 0.1for some deterministic symmetric tester A(; r). Let M 0 , M 1 be the local swap family of p(ε 0 ) and p(ε 1 ) respectively. We show that this could be used to distinguish between a random distribution from M 0 and a random distribution from M 1 . This would then contradict Lemma 4.3. In particular, since the output of A(; r) is invariant up to domain relabeling, the acceptance probability of A(; r) when it takes samples from a random distribution from M 0 must be exactly equal to Acc m (ε 0 ) (and similarly for M 1 ). This immediately implies a tester that takes m samples and could distinguish between a random distribution from M 0 and a random distribution from M 1 with probability at least 1/2 + c for some small constant c. This further implies that if we takes 100mc -1 many samples, we can boost the success probability to 0.99. Yet, since 100mc -1 = õ √ nε -2 ρ -1 , this clearly contradicts Lemma 4.3, and hence concludes the proof of Proposition 4.1.Proof. The lower bound Ω(ε -2 ρ -2 ) follows from the fact that testing whether an unknown coin has bias 1/2 or 1/2 + ε replicably requires Ω ε -2 ρ -2 many samples as shown in [30] . In the rest of the proof, we therefore focus on establishing the lower bound Ω( √ nε -2 ρ -1 ).Let p(ξ) be the distribution instance defined as in Equation ( 4). Let A be a ρ-replicable uniformity tester that takes m samples. We denote by r the random string representing the internal randomness of A.Following the framework of [30] , we will fix some random string r such that (i) A(; r) accepts the uniform distribution with probability at least 1 -O(ρ) (ii) A(; r) rejects the distribution p(ε) with probability at least 1 -O(ρ) (iii) A(; r) is replicable with probability at least 1 -O(ρ) against p(ξ) for ξ sampled uniformly from [0, ε]. By the correctness guarantees of A, a large constant fraction of random strings r must satisfy (i) and (ii). By the replicability requirement of A, a large constant fraction of random strings r must satisfy (iii). By the union bound, there must exist some random string r that satisfies (i), for any ξ such that |ξ -ξ * | ≤ ρε. In other words, if we sample ξ randomly from [0, ε], whenever ξ falls into the interval [ξ * -ρε, ξ * + ρε], the algorithm will fail to be replicable with constant probability. It is not hard to see that the interval has mass Ω(ρ) under the uniform distribution over [0, ε]. This would then imply that the tester would not be O(ρ)-replicable, contradicting property (iii). This shows that m = Ω( √ nε -2 ρ -1 ), and hence concludes the proof of Theorem 1.6.In this section we give additional discussions and omitted proofs.C.1 Barriers for χ 2 -StatisticsWe show a similar barrier for using the χ 2 -test statistics. These statistics are used in the several uniformity testing algorithms, including [14, 1, 47, 20] . The χ 2 test statistic (of [1] for example) computesi∈[n] (X i -m/n) 2 -X i m/nwhere the algorithm takes Poi (m) samples and computes X i to be the frequency of the i-th element among the samples. For a uniform distribution, the test statistic is expected to be at most mε 2 /500, while if the test statistic is far from uniform the test statistic is at least mε 2 /5, leading to an expectation gap with around mε 2 (Lemma 2 of [1] ). Suppose a tester compares the test statistic with a random threshold sampled from the interval [mε 2 /500, mε 2 /5]. For the tester to be O(ρ)-replicable, we require that the test statistics deviate by no more than O(ρmε 2 ) with high constant probability, in other words the variance must be at most O(ρ 2 m 2 ε 4 ).As before, we fix a constant ε > 0 so that we can ignore the dependency with sample complexity, and consider a hard instance of a distribution with a single heavy element with probability p i = n -1/2 . In particular, we will haveX i ∼ Poi (mp i ) = Poi (m/ √ n). Since m/ √ n ≫ 1, there exists some constant small constant c such thatPr[X i > m/ √ n + c √ m/n 1/4 ] > c , Pr[X i < m/ √ n -c √ m/n 1/4] > c. However, in the two cases above, the contributions to the χ 2 -test statistic from X i differ bym √ n + c √ m n 1/4 -m n 2 -m √ n -c √ m n 1/4 -m n 2 + 2c √ m n 1/4 m/n = Ω m 3/2 n 3/4 + √ m n 1/4 m/n = Ω √ mn 1/4 .Following our previous discussion, for the tester to be O(ρ)-replicable, we therefore require thatm 1/2 n 1/4 ≪ ρm or m ≥ n 1/2 ρ -2 .For non-replicable uniformity testing algorithms, we can typically assume that symmetry is without loss of generality when analyzing the sample complexity. A common reduction that turns an asymmetric algorithm into a symmetric algorithm is the following. The algorithm could apply all permutations to the samples observed, and output the majority answer. However, it is not clear that such a transformation preserves replicability.Below we discuss in more detail the barrier hit by our lower bound argument for asymmetric testers. Suppose we want to prove a lower bound against general algorithms. The known techniques for lower bounds against replicable algorithms first fix a random seed r such that A(; r) is both correct and replicable with high probability given a distribution drawn from the adversarial instance (in our lower bound the instance draws distributions p(ξ) uniformly from ξ ∈ [0, ε]). 8 Given a fixed random seed, we now have a deterministic algorithm A(; r) that accepts p(0) and rejects any permutation of p(ε). By continuity, for any fixed permutation π, there is some ξ π such that A(; r) accepts with probability 1/2 given samples drawn from p(ξ π ) permuted according to π. It remains to argue that algorithms with low sample complexity m ≪ √ nρ -1 ε -2 cannot successfully distinguish nearby distributions p(ξ π ), p(ξ) (both permuted according to π) for any ξ ∈ (ξ π ±ρε) so that the acceptance probability of A(; r) must be close to 1/2 in this region and therefore A(; r) is not replicable with probability Ω(ρ). However, our arguments in Appendix B only show that the families p(ξ π ), p(ξ) are indistinguishable when permuted by a random permutation π ′ , not necessarily when permuted by the permutation π. In fact our proof only allows us to argue that for any ξ ′ ∈ [0, ε], the families are indistinguishable when permuted by a constant fraction of permutations π ′ . However, the permutations for which the families p(ξ ′ ), p(ξ ′ + ρε) are indistinguishable may not be the permutations for which ξ π , ξ ′ are close.The formal definition of replicable identity testing is given below. Definition C.1 (Replicable Identity Testing). Let n ∈ Z + , and ε, ρ ∈ (0, 1/2). A randomized algorithm A, given sample access to some distribution p on [n], is said to solve (n, ε, ρ)replicable identity testing if A is ρ-replicable and it satisfies the following for every fixed distribution X:1. If p is X, A should accept with probability at least 1 -ρ. 92. If p is ε-far from X in TV distance, A should reject with probability at least 1 -ρ.[27] gives a reduction following reduction between uniformity and identity testing. Theorem C.2 ([27], restated). Let q be a distribution over [n] with known explicit description. There is a (randomized) algorithm T such that given m independent samples to a distribution p on [n] and ε > 0, generates m independent samples from a distribution p ′ on [6n] such that:1. If p = q, p ′ is uniform on [6n].2. If p is ε-far from q in total variation distance, then p ′ is ε/3-far from uniform in total variation distance.Furthermore, this algorithm runs in O(m) time.If we want to design a replicable identity tester, we can simply transform the samples using T from Theorem C.2 (note that we don't even need to share the randomness of T across different runs) and then feed the transformed dataset to the replicable uniformity tester from Theorem 1.3. The correctness guarantees follow immediately. Let p ′ be the output distribution of T . Since in both runs the replicable uniformity tester takes samples from p ′ , replicability of the process follows from Theorem 1.3. Lastly, it is not hard to see that the number of samples consumed is asymptotically the same as the uniformity tester.NeurIPS Paper Checklist Justification: The primary limitation of our work is that the lower bound holds only for symmetric algorithms. While symmetric algorithms is a natural class and encompass all known algorithms in uniformity testing, it would be nice to have a lower bound that holds in general. We discuss this in our paper. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or 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?Answer: [NA]Justification: The paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024).In this work, we do not focus on the dependency on the failure probability of the tester. The common formulation is that A should succeed with some large constant probability, i.e.,2/3. However, if A is at the same time required to be replicable with probability at least 1 -ρ, one can see that A must also be correct with probability at least 1 -ρ.2 See[13] for the dependency on ε and ξ for the full landscape of the problem.Õ hides polylogarithmic factors in n, ρInterestingly, the large variance caused by heavy elements is usually not an issue in the non-replicable setting where the distribution is promised to be either uniform or far from uniform. This is because heavy elements could only exist in the latter case. In that case, the expected value of the test statistic must also be large, thus adding more slackness to the concentration requirement of the test statistics. Unfortunately, to obtain replicability, we need to deal with distributions that have heavy elements but are still relatively close to the uniform distribution.More precisely, we pick a "good random string" such that the induced deterministic tester is correct and replicable at the same time against our fixed testing instance distribution with high probability.An omitted technical detail is that our construction ensures that the acceptance probability is a continuous function of ξ.The use of information theory in showing lower bounds for replicability has also appeared in the manuscript[29]. But our argument and construction are significantly more involved and exploit symmetries in the underlying algorithm.In our lower bound, we use the local swap family to restrict the adversary to a subset of permutations. In this discussion, we allow a more generic adversary that could permute the domain arbitrarily.As in the case of uniformity testing, we do not focus on the dependence of the sample complexity with the error parameter. 
 
 Appendix:  


Decision: The paper gives a new analysis of a uniformity test under replicability constraints, showing smaller blow up over the non-replicable setting than prior work, and a lower bound against symmetric testers that nearly matches the upper bound. The result is interesting and novel, and addresses a basic problem in a model that is new but has received a lot of attention recently.

Reviews: review: paper_summary: paper_summary: This paper studies uniformity testing under the replicability constraint. Given samples from an unknown distribution P, we need to decide whether P is uniform or eps far from uniform with high probability. Additionally, the algorithm needs to report the same answer in two different random input samples with high probability.

The main contribution is an algorithm that takes 1/rho factor more samples than the non-replicable counterpart for which tight sample complexity is well-known. When the sample space size is 2, a 1/rho^2-factor blowup is known to be necessary from prior work. Thus, the new algorithm shaves off a rho factor. Matching sample complexity lower bound is shown only under symmetric assumptions where the algorithm behaves identically under a renaming of the sample space.
strength_weakness: strength_weakness: The main weakness I believe is the lack of an unconditional tight sample-complexity lower bound.
questions: questions: None.
limitations: limitations: None.
paper_summary: paper_summary: The concept of "reproducible" learning was introduced in STOC 22 paper and the concept is a very relevant to modern day research. 
They also showed how algorithms based on statistical estimations can be easily converted to reproducible algorithm with a little overhead. 
In this paper the authors have tried to produce reproducible testing algorithm for uniformity testing.  Uniformity is indeed a very important problem is a lot of applications.
strength_weakness: strength_weakness: There are many algorithms for uniformity testing. Many of them are either already reproducible or since they are based on statistical estimations they can be easily converted into reproducible algorithms. Neither has the literature of the uniformity testing done thoroughly, nor has it been discussed why this algorithm is new. The same, or similar, algorithm has already been used in the literature.
questions: questions: NA
limitations: limitations: NA
paper_summary: paper_summary: This work studies uniformity testing in the context of replicable algorithms. Knon uniformity testing algorithms are non-replicable in the following sense:  a) If the unknown distribution equals the uniform, then they output 1 whp, b) if they are epsilon-away from uniform, output 0 whp c) when the distance is between 0 and epsilon, then they output 1 with arbitrary (could be 1/2) probability. Thus when (c) happens, two different runs of the algorithm may give two different answers, thus are not replicable.  The goal of this work is to design algorithms so that even when (c) happens, the algorithms are  \rho-replicable (jn the sense of ILPS22).  The obvious \rho-replicable algorithms will have a blow-up 1/\rho^2 in the sample complexity (compared to non-replicable algorithms). The main contribution of this work is to show that this can be achieved via only a 1/\rho-blowup in sample complexity. This work also shows that 1/\rho-bloup is necessary if the algorithms have certain property (permutation-invariant).
strength_weakness: strength_weakness: I am hoping to uncover a high-level explanation as  why the dependency on \rho is inverse-linear when $n$ is high.  The additive term has 1/\rho^2 term which is consistent with the lowerbound of ILPS.  To me, this suggests that there is an intuitive explanation of the sample complexity, however, I am not able to uncover such an explanation. The overview that the authors provide is more technical than intuitive.
questions: questions: 1. Related to weakness. Can you the high-level intuition?
limitations: limitations: None
paper_summary: paper_summary: In this paper the authors study the problem of replicable uniformity testing. The non-replicable version of the problem can be stated as follows: given some $\varepsilon > 0$ and sample access to some distribution $p$ on $[n]$ what is the minimum number of samples $m$ to distinguish whether $p$ is the uniform distribution or $\varepsilon$ far from it in TV distance? A long line of work has shown that the sample complexity for this task is $\Theta(\sqrt{n}/\varepsilon^2)$. The authors ask for algorithms that have the additional replicability requirement based on the definition of Impagliazzo et al. (2022), meaning that when the algorithm is executed twice on two i.i.d. sets of samples from the same distribution it will make the same decision with probability at least $1-\rho$. The authors design an algorithm that requires $\tilde{\Theta}(\sqrt{n}/(\varepsilon^2\rho) + 1/(\varepsilon^2\rho^2))$ many samples from the distribution $p$. This bound is achieved by considering a (non-replicable) uniformity tester that is based on some $\ell_1$ statistic, since testers based on $\ell_2$ statistics would incur a $tilde{\Theta}(\sqrt{n}/(\varepsilon^2\rho^2))$ sample complexity. Moreover, they provide an (almost) matching lower bound for a natural class of "symmetric" algorithms.
strength_weakness: strength_weakness: I think that the discussion prior to the statement of the main result could be improved by mentioning that there is a $1/(\varepsilon^2\rho^2)$ additive term in the sample complexity (maybe even in the discussion in the abstract).

I am bit confused about how the $\tilde{O}(1/(\varepsilon^2\rho^2))$ shows up in the upper bound. The proof sketch that is presented in the main body only considers the $\tilde{O}(\sqrt{n}/(varepsilon^2\rho))$ term. I understand that this is required even for $n=2$, I just don't see how it is used in the general case. Could you please elaborate on it?
questions: questions: Please see the question in the weaknesses section.

Could you also please elaborate on the dependence of the sample complexity with respect to some error parameter? I'm referring to your discussion in footnote 1.
limitations: limitations: Addressed.

Comments: title: Read the rebuttal
comment: Thanks for the reply from the authors. I have not found enough evidence to change my assessment of the paper.
Thanks for the detailed response.
Thank you for your response, after reading the rest of the reviews and your rebuttal I remain positive about the paper.
Thank you for the response.