Replicable Uniformity Testing
Authors: Sihan Liu
Christopher Ye
Venue: NeurIPS 2024 poster (2024)
Keywords: Replicability
Uniformity Testing
Primary area: learning_theory
TL;DR: We give the best known algorithm for replicable uniformity testing, and a matching lower bound for the natural class of symmetric algorithms.

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.

Replicable Uniformity Testing
Sihan Liu University of California San Diego La Jolla, CA si1046@ucsd.cm edu
Christopher Ye
University of California San Diego La Jolla, CA czye@ucsd.
Abstract
Uniformity testing arguably one of the most fundamental distribution testing problems. Given sample access to an unknown distribution p [ri]. one must decide p is uniform or e-far from uniform (in total variation distance). A long line of work established that uniformity testing has sample complexity ((vri 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 pー2 factor overhead in sample complexity, we obtain replicable uniformity tester using only Ö Ö(yne=2p-1) samples. To our knowledge, this is the first replicable learning algorithm with (nearly) linear dependence on p.
Lastly, we consider class of "symmetric" algorithms (FOCS '00] whose outputs are invariant under relabeling of the domain [n), which includes all existing unifor- mity testers (including ours). For this natural class of algorithms, we prove nearly matching sample complexity lower bound for replicable uniformity testing.
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 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 TCS perspective [5, 4], 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 Given sample access to some unknown distribution on [n] = (1, n), one tries to decide whether p uniform far from being uniform.
of the most fundamental distribution testing problems:
When the unknown distribution promised to be either uniform or at least e-far from being uniform in total variation (TV) distance, a line of work in the field [28, 40, 47, 20, 16] has led to efficient testers that achieve information theoretically optimal sample complexity, i.e. O(vnle²²). However, the testers are only guaranteed to provide reliable answers when p fulfills the input promise is either Un, or far from it. In practical scenarios, due to number of reasons such as model misspecification,
inaccurate measurements, such promises tester no longer has a correctness constraint to adhere to, it may have arbitrarily volatile behavior. Ideally, hope for algorithmic stability for all distributions, not only those fulfilling the promises. Consider the scenario where two group of scientists, as an intermediate step of some scientific study, trying independently test the uniformity of some ground-truth distribution p*. If the groups
rarely guaranteed [13]. Since the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 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 + Y is p-replicable if for all distributions p on X, PT (A(T;r) = A(T": 2 1- p. where 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 replicabiliit 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 can design testers that conform to the above replicability requirement, consistencies of their outputs can be guarantced even when there are no promises the data distribution. This then motivates the study of replicable uniformity testing.
Definition 1.2 (Replicable Uniformity Testing). Let n E Zi4, and e. E (0, 10,1/2). A randomized algoritium A. given sample access to some distribution on [n], is said to solve (n, s, p)- replicable uniformity testing if A is p-replicable and it satisfies the following: (1) If p is uniform, A should
accept with probability at least 1 - p. (2) If p is from the uniform distribution in TV distance, A should reject with probability at least p.
As observed in [30], learning algorithms usually incurs additional sample complexity overhead in the replicability parameter p 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, E. (under mild assumptions on the testers).
1.1 Relationship with Tolerant Testing
An alternative approach to address the stringency of the promises in the formulation of uniformity testing is the concept of tolerant festing [41]. At a high level, given some & < e, the unknown distribution is now relaxed to be either e far from Un or & close to U, 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 e is some constant 2, the sample complexity of tolerant testing quickly grows from strongly sublinear, i.e., @(vri) to barely sublinear, i.e, ((n/ log n) as E increases from to e/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 Un) < E. Instead, for all possible distributions p. the testers are only required to give replicable answers (with high probability). While we can construct an (n,=', p) prrepiccabl uniformity testing algorithm using tolerant testing by randomly sampling some threshold r E (0, E') and performing tolerant testing with & = r pe' and r + pE', the sample complexity of such an approach will be barely sublinear in even for constant p as discussed above. Notably, the replicable algorithm in our work has sample complexity that remains strongly sublinear in n.
1.2 Our Results
When 2, uniformity testing amounts to distinguishing fair coin from e-biased coin. It is well known that the task requires (((-2) samples without the replicable requirement. When the tester is required to be p-replicable, [30] shows that @(s-2p- many samples are necessary and sufficient
'n 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 replicable with probability at least - p. one can see that A must also correct with probability at least - p.
"Se [13] for the dependency and for the full landscape of the problem.

---

for replicable coin testing, demonstrating a quadratic blowup in p compared to the non non-replicable counterpart of the problem. For large n. the sample complexity of non-replicable uniformity testing has been resolved after long line of work [28, 40, 47], and shown to be ((vng-)). Following the pattern, one naturally expect that replicable uniformity testing would have sample complexity 5(v'mp²2=-)) In fact, this is exactly the sample complexity reached if one views the outcome of an optimal non-replicable uniformity tester convert the given uniformity tester into a replicable one.
coin flip, and uses an optimal replicable coin tester to
Somewhat surprisingly, we show that the sample complexity from this blackbox reduction is sub- optimal for replicable uniformity testing - it is possible additionally shave one p factor and make the dominating term's '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 E Z4, E, E (0, Algorithm
I solves (n, E, rreplicaae uniformity testing with sample complexity Ô 22p + )
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 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 nearly matching sample complexity lower bound for natural class of testers whose outputs are invariant under relabeling of the domain elements [n). The class of testers commonly referred as Symmetric Algorithms, and first studied in the work of [5].
Definition 1.5 (Symmetric Algorithms, Definition 13 of [5]). Let ff [n]] + {0, 1} be a binary function. We say that f is symmetric if for any sample set (-1,---In E [n|x>T and any permutation π E Sn, we have that [x1,,... Imm) = (x((),,, ... , (Im)). We say an algorithm A(rr) is symmetric if it computes some symmetric function fr 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 simple observation that uniformity itself is symmetric property: if p is uniform 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 E Z+, E, E (0, Any symmetric algo- rithm solving the (n, e, p)reeliiaallee uniformity testing problem requires á 22p + pre
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.
1.3 Limitations, Discussion, and Future Work
In this paper, we present a replicable algorithm for uniformity testing using 2 samples. We provide matching lower bound for natural class of symmetric uniformity testers aaggorithms 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 anconditionally and leave it as an open question. We discuss some issues in generalizing our current approach 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 closeness and independence testing [18].
20 hides polylogarithmic factors in n,
3

---

1.4 Technical Overview
Vnp Barriers for l based Statisties. Most of the well known non-replicable uniformity testers compute an unbiased estimator for the &y norm of the the unknown distribution p. i.e., 1Ip1 Σi=1 př from the number of occurrences X; of each element among the observed samples. These include the testers from [28, 17], which are based on counting pair-wise collisions, i... 2 E Xx, - 1), and the ones from [14, 1, 47, 20], which are based on variants of the x² statistic, i.e., Σi=1 ((X; - m/n)² X.) (m//n). As one can see, these estimators all rely heavily on computing the quantities X?, 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 x" based statistics, which we defer to Appendix C.I.
Given an unknown distribution P. the expected number of pairs of collision will be exactly EE ("r) pp. If p is uniform, the expected value of the test statistic will be about m² 2n- If p is E-far from being uniform, the expected value will be least m²(1+e") To construct replicable 2n uniformity tester from the collision statistics, a natural idea is to select a random threshold r between the two extrema 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 statístics computed in two different runs deviate by A, the above events happens with probability exactly A 2n maga Hence, for the tester to be p-replicable, the test statistics will need to deviate by no more than A = O (m² p2pp/) with constant probability.
To focus on the dependency on p. we let e be a small constant. We now construct hard instance that makes collision-based statistics violate the above concentration requirement unless m >> Vnp= Consider a distribution with a single heavy element with probability mass p > 1/Vn. 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 (H), which deviates by S (mp./mp) 9(m / 2/14) from its mean with constant probability. Consequently, over two runs of the algorithm, with constant probability the numbers of collisions may differ by 2(m //3/1). Therefore, the tester will fail to be p-replicable unless 33/2 /12// & pmn² /nn or equivalently m >
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] 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:
1 Σ 115/m-1/n// = S
2 i=1
where X, 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,. For heavy element X,, the contribution to the empirical total variation distance is (up to normalization) at most X, with variance Var(X,) θ (mp)= θ (m/n²/2) opposed to Var(X?) θ /n3/). Intuitively, this allows to obtain tighter concentration bounds on the test statistic S, thereby improving the final sample complexity.
First, we observe that when the distribution is e-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 fmm n, E) (see Equation (2) for the full expression). To establish replicable tester in the super-linear case (m = O (ne 2 1) 2 n), we use McDiarnid's inequality to directly argue that the TV test statistic deviates by most (m,, n,,e) with high probability. Hence, if we use random threshold that lies within the gap interval, the threshold will be pf(m, n, e) close to the expected value of the test statistic with probability at most Opp), ensuring replicability of the final result.
'Interestingly, the large variance caused by heavy elements is usually not issue in the non-replicable setting where the distribution promised be either uniform far from uniform. This is because heavy elements could only exist in the latter case. In that case, the expected value 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.

---

The key challenge lies in obtaining the desired concentration in the sublinear regime, i.e. m I n. In this regime, the expectation gap is given by (m, n. =²m= elements, i.e., element with mass p; 2 1/m, can still make the test statistic have high variance. As a result, it becomes challenging to obtain the desired concentration of pf [m, n,,)) on the test statistic. However, in the presence of very heavy elements (e.g., P; 2 m/nz which causes the variance of the test statistic 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 e-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
n² Unfortunately, the presence of heavy
particular, in Lemma 3.3 we show that, whenever V VVa(S)) > (f n,E, ps"m² it holds that
n²
E [S]] - VVr((S) 2 (U,)), + + /n²
where ((U,,) is the expected value of S under the uniform distribution Un. At a high level, Equa- tion (1) is shown by rewriting S with indicator variables representing whether some sample collides with another, and we use correlation inequalities to show that these collision indicators are "almost" independent of each other (see proof sketch of Lemma 3.3 for more detail). Combining Equation (1) with Chebyshev's inequality, we then have that S >> (((,))+=*n / with high constant probability (which can be easily boosted to 1 - P with the standard "median trick"). As we choose our random threshold from the interval (u(Un),
+ =n=)" it follows that the tester must consistently reject. Otherwise, we have / /Va S (f n, E). Applying Chebyshev's 's inequality gives that Pr (IS - E [S] > pf n, e) << 1. The rest of the argument is similar to the super-linear case.
Sample complexity Lower Bound
At a high level, we present a family of distributions (p(E)}e parametrized by some parameter [0, satisfying the following: no symmetric tester that takes fewer than 5 <v
many samples can be replicable with high probability against a random distribution from the family. Since we have fixed the testing instance distribution, using minimax style argument similar [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(s) is e-far from uniform (ii) for any two distributions p(E). P(E + 6), where 6 < Ep, within the family, no symmetric tester taking fewer than Ω (vπE 2 ') many samples can reliably distinguish them. By (i) and the correctness guarantee of the algorithm, the acceptance probabilities of the tester should be near under p(0) and near under p(E). This implies that there exists some 5 within the range such that the acceptance probability is 1/2 under P( ) By property (ii), p((*) cannot be distinguished from p(g* + (ep)) by the tester, which immediately implies that the acceptance probability of the tester is near 1/2 whenever { 5* + (Ee)), and therefore not replicable with constant probability. Thus, if we sample & uniformly from [0, e]. the tester will fail to replicate with probability at least (p)).
The construction of p(E) is natural and simple: half of the elements will have mass (1 + /)/n /n and the other half will have mass (1 - f).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 among the samples (as elements having frequencies more than 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 about
m² ((1 + E)² + (1 E) /n 2m 2m (1+ g2)/n
many frequency-2 elements under p(E) in expectation. On the other hand, the standard deviation of the number of such elements is about /m²/n- = m/V7. Hence, for the tester to successfully distinguish the two distributions, m needs to be sufficiently large such that
m² ((1 + ( (1 + +2) ~ n
m² + Ep)ep
m
n2
'More precisely, pick "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. 'n omitted technical detail is that our construction ensures that the acceptance probability is continuous function of {.
5

---

which yields m
?
(E+ep)ep
To formalize the above intuition, we will use information theoretic argument 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(E) 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 + f)/n with those with mass (1 6)/n and randomly swap their orders. Since pairs are ordered randomly, no algorithm can hope identify heavy/light elements without taking a significant number of samples. Thus, this creates distribution families containing p and p( + 5) that are information theoretically hard to distinguish even for asymmetric testers. Consequently, this shows the existence of some permutation ag of [x] such that the permuted distributions #ę P({) and #g P(ć 8) are hard to distinguish. However, recall that in the replicability argument we need to first fix some 5" such that p({*) = 1/2. Thus, we have to prove specifically that p()) and p(C + 5) themselves are hard to distinguish. Fortunately, for symmetric testers, the acceptance probabilities of T p({) and Te p(g + 6) must be identical to those of p and p(ε + 6) respectively. Consequently, no symmetric tester can easily distinguish P(E) and p(E + 0d).
2 Preliminaries
For any positive integer n. let [n] (1.2...., 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 Pa denote the probability of x in p. For subset 8 C [n]. Ps = Eres Pz. P2. For distributions p, q over [n]. the total variation distance is drv (P, q) = 2 Ex rxji IP= qu = maxsc(n) Ps - qs- We also recall the definition of mutual information. Let X, be random variables over domain X. The
P=((X.))=(e..))) mutual information of X, Y is T(X: Y) -)=E,,exx Pr((X, (z, u)) log P((()) We use >> b (resp. < b) to denote that is a large (resp. small) constant multiple of b.
3 Replicable Uniformity Testing Algorithm
Algorithm Overview At a high level, our algorithm computes the TV-distance statistic and com- pares 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 better understanding of the concentration properties of the test statistic when the unknown distribution is neither uniform nor E-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 E-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 [ni] such that & dry (p. Un). For any distribution p. let p(p) denote the expectation of the test statistic S = > X, given m samples drawn from P. For all m 2 6,n 2 2, there is a constant C such that
m S n n < m < n S
n
u(p) M(U,) 2 R:
E2
m
(2)
n
E
We require the following structural lemmas, whose formal proofs can be found in Appendix A, on the test statistic Smedian- These lemmas show that the test statistic S (and therefore Smedian) concentrates
'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.

---

Algorithm I BUNIFORMITTTESTER
Input
:Sample access to distribution on domain [n]]
Parameters tolerance, p replicability
Output
:ACCEPT if Un is uniform, REJECT if drv (p, Un) 2
m 6 pC V log " + p: mo + 1/p).
2 for 1 1 S mg do
Dj gets samples from p
- 2 -
where X; is the occurrences of i [n] in D2
5 meedian < median of {S
6 (U(,) is expectation of 2 E X, _ under uniform distribution.
7 Set threshold r +- (((U), + ro R (R given by Lemma 3.1) where ro + Unif (1 4).
8 return ACCEPT if Smedian < r. Reject otherwise.
around its expectation p(p) = [p] in the sublinear (m < n) and superlinear (m 2 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 's inequality to obtain the desired concentration result.
Lemma 3.2 (Superlinear Concentration). Assume that are in the superlinear regime (i.e., 2 n). Denote by ((() the expectation of the test statistic S under the distribution p. If S m I 22, then Pr (|Smedian (()) P16
4 If 2 I m, then Pr ([Smedian p(P) 2 16
C < G.
For the sublinear case, provide a proof sketch below, deferring the details to Appendix A. then E [[]] Var(S) () > p(UU). ) + Ce2m²n-2 where p(Un) is the expectation of S under the uniform distribution and C given by Lemma 3. As a consequence, with probability at least p/4, have Smediaa > p(Ua) + Ce2mnn
Lemma 3.3 (Sublinear Concentration), Suppose m S n. If Var(S) 2 (C/64)p²=*m'nr
On the other hand, if Var(S) S (C/64))d'''m'>
then it holds that p/4. Furthermore, for the uniform distribu-
Pr (|Smedian - [(()) 2 pe22mn tion Un. Var(S) S (C/64))2e'm'1
Proof Sketch. the proof sketch, for simplicity, we assume that E 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 Smedian then follows from the standard median trick.
In the rest of the sketch we focus on the case Var(S) Z (C/64))pe"m*nn= In this case, the key is show that
E [S] Var(S)= > (lU,) + Ce2
(3)
the claim Smodian > (UU)) + C=2m2n=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, as the number of occurrences of element i [m). We begin with an
observation from [16] stating that the test statistic S Z/n where Z = {i t. X, = 0}| denotes the write Z
number of "empty" buckets. Furthermore, whether the i-th sample collides with a previous sample j < i. Then, Var(S) = Var(Z)/
m + Eis1 Y, where Y; indicates m
Var(_ Y.)/n², To bound the variance, we argue that the indicators Y; are "almost" negatively correlated using correlation inequalities (specifically Kleitman's 's Theorem Lemma A.8), so that (roughly) Var(E < Σ, Var(Y;) << E [Y]] (see Lemma A.5 for the accurate statement).
Observe that under Un. we have EY S m2n so that E [S] ((Un) > E | /n /n- m² /n2 It follows that
[ V -ar(S)-((U,)
E
Σ
E
Σ
x
/n (m
By our assumption, E EΣ > Var(S( > fo-m-n-2 > so that it suffices to show E E Y2 > (C T)m² n Since Var(S) (C -4 which is further bounded from
below by m² /n3 whenever m > 22 conclude E [Σ Yy 2 n² vava(()) > m² /n. L
7

---

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, Smedian S p(Un)) + R/16 v
((Un) + R/4 I with probability at least 1 - { so the algorithm outputs ACCEPT.
Otherwise, if n & m, have by Lemma 3.2 that with probability least 1 4. Smedian S (UU)) + R/16 S p(U,)+ + R/4 S so that the algorithm outputs ACCEPT.
On the other hand, suppose the test statistic S using θ ((v n l0g(1/)) + log(1/p))e*
dtv (p, Un) 2 We note that the algorithm of [16] computes
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] > p/ /000, which further implies that Pr[Smed > r] 2 p/4.
We now proceed to replicability. Consider two executions of the algorithm. If is uniform or {= drv (p. U,) 2 E, then following a union bound on the correctness condition, two executions of the algorithm output different values with probability at most p/2. Then, suppose m S n and By Lemma 3.3, both samples lead the algorithm to output REJECT with probability at least / so that the algorithm is p-replicable.
Var(S) 2 c2"
Otherwise, Lemma 3.2 and Lemma 3.3 guarantees strong concentration of the test statistic Smedian- In particular, with probability at least 1 - / 2, we have [Smedian - ,u(p)] S to R over both samples, in Equation (2). In particular, whenever the random
where R is the expectation gap defined threshold r does not fall in the interval (u(p) + pRf16) both executions output the same result. Since r is chosen uniformly at random, this occurs with probability most (pR/8)/ union bound, we observe that Algorithm is p-replicable.
p/4. By
Finally, the sample complexity is immediately obtained by our values of m my-
4 Lower Bound for Replicable Uniformity Testing
In this section, we outline the important lemmas used in showing the sample complexity lower bound for p-replicable symmetric uniformity testers, and give their proof sketches. The formal argument can be found in Appendix B.
Note that the lower bound á (p- 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 á (vñs-2p-1). Consider the canonical hard instance for uniformity testing where half of the elements have probability mass
(1 + f)/n and the other half have probability mass (1 g)/n:
-- if mod 2= 0,
P();
=
= otherwise.
Our hard instance for replicable uniformity test is as follows: we choose from the interval [0,e] uniformly at random, and let the tester observe samples from p(E).
Fix some uniformity tester Am that takes m samples. We will argue that if Am is p-replicable and correct with probability at least 0.99, then we must have m {((nn==>p=>
At high level, we follow the framework of [30]. First, we fix some good random string such that the induced deterministic algorithm Am (:r) is replicable with probability at least 10p, and is correct p00 and p(E) with probability at least 0.99. Then, consider the function Acc (E) that denotes the acceptance probability of (S: when the samples are taken from P(E). Note that Acc,, (E) must be continuous function. Moreover, by the correctness of (iT). it holds that Acc, 2 0.99 and Acc,..e) < 0.01. Hence, there must be some value g" such that AC*) = 1/2. To show the desired lower bound on m, it suffices to show that Acc + 5) must not be too far from Acc(g") for any 5 & ep m = o(yne=2pp))
Proposition 4.1 (Lipschitz Continuity of Acceptance Probability). Assume that =ō o(VnE-2p
Let (;(;)) be a deterministic symmetric tester that takes m samples. and define the acceptance probability function Accm(E) (E) Pis-p(e)am [A(S:r) = 1], where p(E) is defined as in Equation (4).
Let Eo E1 (0,z) be such that e Eo Ep. Then it holds that (ECm (E1) 0.1.
8

---

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 {(p)) if m implying that the algorithm is not ((p)-replicable. The proof of Proposition 4.1 is
Ø( Vns-pp ---ppp)) 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 C0,&1 be defined as in Proposition 4.1. At a high level, we construct two families of probability distributions, which we denote by MM and M₁, that satisfy the following properties: (i) M, contains distributions that are identical to p(e:) up to domain element relabeling. (ii) Any tester that uses at most mn samples cannot effectively distinguish between random probability distribution from Mo and random one from MM. For the sake of contradiction, assume that there a deterministic symmetric tester using m samples such that the acceptance probabilities on (E) and p(ς + 8) differ by at least 0.1. Since all distributions within Mo are identical to p({) up to element relabeling, it follows that the acceptance probabilities of the symmetric tester any of the distribution within Mo must be the same (and similarly for M1)). This then further implies that the tester can successfully distinguish random distribution from Mo versus one from M1, contradicting property (ii). Proposition 4.1 thereby follows.
It then remains to construct the two families of distributions. Recall that M, contains distributions that are identical to p(ε)) up to element relabeling. We will consider all distributions that can be obtained by performing "local swaps" p(=,). In particular, first group the elements into n//2 many adjacent pairs, and then randomly exchange the labels within each pair.
Definition 4.2 (Local Swap Family), Let n be an even number, and p be probability distribution on [n]] We define the Local Swap Family of P as the set of all distributions ý such that
(p(E));: ((6)))+)())))) = for all odd numbers j E [n]]
or (p(E.),,
(p(E)))-L.P(EE)))
Lemma 4.3 (Indistinguisaable Distribution Families), Let m mmm==olvm =on-nE- and En < E1 E (0, be such that $ - 6o < Ep. Let p(Eo), p(ε1) be defined as in Equation (4), and Mi be the Local Swap Families (see Definition 4.2) of p(eu), p($1) respectively. Let S be m samples drawn from either random distribution from Mu random one from M1. 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 random unbiased bit X that controls whether we sample from a random distribution from Mo or a random distribution from MI. 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 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, standard reduction based argument using the fact that Poisson distributions are highly concentrated. The formal statement of the mutual information bound is provided below.
can show that this is without loss of generality by
Lemma 4.4. Let Mo, Mi be defined in Lemma 4.3. Let X be a random unbiased bit, ÿ a random probability distribution from Mx, and S be Poi (m) many samples from p. Moreover, let M₁ be the occurrences of element among S. Then it holds that
I(X: M1,-. M,,)) = 0 E0 EE'
m² log 1og"(m) + o(1).
To show Lemma 4.4, we first note that if we group the random variables into n1/2 many adjacent pairs, the pairs (M, M,+1) are conditionally independent and identical given X. Therefore, we can bound I(X: M2, ... .Mn) from above by 2 I(X: : Mr, M2). To tackle I(X: .M1, M2), we break into three regimes depending on the relative sizez of m, n, 8: the sub-linear regime (approximately vn < n)), the super-linear regime (approximately
< < n/e²), and the super-learning regime (approximately m > n/e²). The formal proofs involves writing the probability distributions of M,s as Taylor expansions in The calculations are rather technical and therefore deferred to Appendix B.

---

Acknowledgments and Disclosure of Funding
The authors would like thank Max Hopkins, Russell Impagliazzo, and Daniel Kane for many helpful discussions and suggestions.
Sihan Liu is supported by NSF Award CCF-1553288 (CAREER) and Sloan Research Fellowship. Christopher Ye is supported by NSF Award AF: Medium 2212136, NSF grants 1652303, 1909046, 2112533, and HDR TRIPODS Phase II grant 2217058.
References
[1] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. Advances in Neural Information Processing Systems, 28, 2015. 1.4, C.1
[2] Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016. A.8, A.1
[3] Monya Baker. 1,500 scientists lift the lid on reproducibility. Nature, 533(7604), 2016.
[4] Tugkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 142-451. IEEE, 2001.
[5] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing that distributions are close. In 41st Annual Symposium on Foundations of Computer Science, 2000. 1, 1.2, 1.5
[6] Tugkan Batu, Ravi Kumar, and Ronitt Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 381 381-390, 2004. 1
[7] C Glenn Begley and Lee M Ellis. Raise standards for preclinical cancer research. Nature, 483(7391):531-533 2012.
[8] Mark Bun, Mareo Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, pages 520-527. ACM, 2023. 1
[9] Clément L Canonne. A survey distribution testing: Your data is big, but is it blue? Theory of Computing, pages 1-100, 2020.
[10] Clément L Canonne, llaas Diakonikolas, Daniel M Kane, and Sihan Liu. Near-optimal bounds for testing histogram distributions. arXiv preprint arXiv:2207.0653 2022.
[11] Clément L Canonne, Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Testing bayesian networks. Conference on Learning Theory, pages 370-448. PMLR, 2017. 1
[12] Clément L Canonne et al. Topics and techniques in distribution testing: A biased but rep- resentative sample. Foundations and Trendy@ in Communications and Information Theory, 193611033-,198, 2022.
[13] Clément L Canonne, Ayush Jain, Gautam Kamath, and Jerry Li. The price of tolerance in distribution testing. In Conference on Learning Theory, pages 573-624. PMLR, 2022. 1, 1.1,
[14] Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the twenty-fitth annual ACM-SIAM symposium on Discrete algorithmss, pages 193--1203 SIAM, 2014. 1.4, C.I
[15] Zachary Chase, Bogdan Chornomaz, Shay Moran, and Amir Yehudayoff. Local borsuk-ulan stability, and replicability. arXiv preprint arXiv:2311.01599 2023.
[16] Hias 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. 1, 1.4, 1.4, 3, 8, 3.1, 8, A.
10

---

[17] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Collision-badd based testers are optimal for uniformity and closeness. Chic. Theor. Comput. Sci, 25:1-21, 2019, 1.4
[18] Ilias Diakonikolas and Daniel M Kane. new approach for testing properties of discrete distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685 695. IEEE, 2016. 1.3, 1.4
[19] Ilaas Diakonikolas, Daniel M Kane, and Sihan Liu. Testing closeness of multivariate distributions via ramsey theory. arXiv preprint arXiv:2311.1315/ 2023.
[20] Ilias Diakonikolas, Daniel M Kane, and Vladimir Nikishkin. Testing identity of structured distributions. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1841-1854. SIAM, 2014. 1.4, C.1
[21] Ilias Diakonikolas, Daniel M Kane, and Vladimir Nikishkin. Optimal algorithms and lower bounds for testing closeness of structured distributions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1183-1202. IEEE, 2015.
[22] Ilias Diakonikolas, Daniel M Kane, and Vladimir Nikishkin. Near-optimal closeness testing of discrete histogram distributions. arXiv preprint 1rXXvv/703.00913: 2017.
[23] Peter Dixon, A Pavan, Jason Vander Woude, and NV Vinodchandran. List and certificate complexities in replicable learning. Advances in Neural Information Processing Systems, 36, 2024.1
[24] Eric Eaton, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning, arXiv preprint arXiv:2305. 2023.
[25] Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. 1
[26] Hossein Esfandiari, Amin Karbasi, Vahab Mirrkkn, Grigoris Velegkas, and Felix Zhou. Repli- cable clustering. CoRR, abs/2302.10359, 2023.
[27] Oded Goldreich. The uniform distribution is complete with respect to testing identity to fixed distribution. In Electronic Colloquium on Computational Complexity (ECCC), volume 23, page 1, 2016. 1.4, C.3, C.2
[28] Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computatioon: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pages 68 78-75, 2011. 1, 1.2, 1.4
[29] Max Hopkins, Russell Impagliazzo, Daniel M Kane, Sihan Liu, and Christopher Ye. Replicabil- ity in high dimensional statistics. unpublished, N.D. 7.4
[30] Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In 54th Annual ACM SIGACT Symposium on Theory of Computing STOC, 2022. 1, 1.1, 1, 1.2. 1.4, 4, 4, B.4
[31] John PA loannidis. Contradicted and initially stronger effects in highly cited clinical research. Jama, 194(2):21-22288 2005.
[32] John PA loannidis. Why most published research findings are false. PLoS medicine, 2(8):e 124, 2005.
[33] Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, and Felix Zhou. Replicable learning of large-margin halfspaces. arXiv preprint arXiv:2402.13857 2024. 1
[34] Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguisha- bility of learning algorithms. In International Conference on Machine Learning, ICMI., 2023.
11

---

[35] Junpei Komiyama, Shinji Ito, Yuichi Yoshida, and Souta Koshino. Improved algorithms for replicable bandits. 2023.
[36] Erich Leo Lehmann, Joseph Romano, and George Casella. Testing statistical hypotheses, volume 3. Springer, 1986. I
[37] Robert K Merton. Priorities in scientific discovery: chapter in the sociology of science. American sociological review, 22(6):633-60) 659, 1957. 1
[38] Shay Moran, Hilla Schefler, and Jonathan Shafer. The bayesian stability 7oo. CoRR, abs/2310.18428, 2023.
[39] Jerzy Neyman and Egon Sharpe Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231(664-706)) 706))2890)) 1933.
[40] Liam Paninski. coincidence- test uniformity given very sparsely sampled discrete data. IEEE Transactions Information Theory, 54(100)4750-4755 2008. 1, 1.2
[41] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012-1042, 2006. 1.1
[42] Felipe Romero Toro. Novelty vs. replicability: Virtues and vices in the reward system of science. Philosophy of science: Official journal of the Philosophy of Science Association, 2017.
[43] Ronitt Rubinfeld. Taming big probability distributions. XRDS: Crossroads, The ACM Magazine for Students, 19(1):24 2:24-28, 2012.
[44] Stefan Schmidt. Shall we really do it again? the powerful concept of replication is neglected in the social sciences. Review of general psychology, 13(2):90-100, 2009.
[45] Gregory Valiant and Paul Valiant. A clt and tight lower bounds for estimating entropy. In Electronic Colloquium on Computational Complexity (ECCC), volume 17, page 9, 2010. 1.1
[46] Gregory Valiant and Paul Valiant. Estimating the unseen: A sublinear-sample canonical estimator of distributions. In Electronic Colloquium on Computational Complexity (ECCC), volume 17, page 2010. 1.1
[47] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing, 46(1):429-4555 2017. 1, 1.2, 1.4, C.1
[48] Gregory Valiant and Paul Valiant. Estimating the unseen: improved estimators for entropy and other properties. Journal of the ACM (JACM), 64(6)) 2017. 1.1
12

---

A Omitted Proofs for Replicable Uniformity Testing Upper Bound
A.1 Concentration the Total Variation Distance Statistic
We now prove the required lemmas for Theorem 1.3. This section is dedicated to proving the required lemmas regarding the concentration properties of meddian-
Superlinear Case: m 2 n
First, consider the superlinear case, when 2
Lemma 3.2 (Superlinear Concentration). Assume that are in the superlinear regime (i.e., 2 n). Denote by μ(()) the expectation of the test statistic under the distribution p. If S m S a. then
Pr ([Smedian (()) P16
C
C [ If S m, then Pr ([Smedian p()) 2 16 < <
Proof. Recall that Algorithm uses the median trick to boost the success probability. Here we focus on the statistic S Sj computed in single iteration [mo]. An essential tool the analysis is McDiarmid's Inequality.
Theorem A.1 (McDiarmid's Inequality). Let X1....,X,, be independent random variables taking values in X. Let xm I be a function such that for all pairs of tuples Tm)) (Ih,... I'm) E x such that x; = x/ for all but one E [m].
|f(11.... Imn
v//) B,
Then,
2t
Pr (I ...., X,) E[f(X, .........l..l.llll..l... 2 exxp
mB
Observe that the samples Tj are independent and a change in Tj changes by at most 1 since at most two values X; change by at most 2m each. Then, applying Theorem A.1 to S = [(Ti,..... Tm). obtain
1_2 (-
Pr Pr p(p) 2 < 2exp
2 exx (-2mt²).
(5)
m
When S m < n. we can conclude
C Pr Is- u()) 2 p 16
20 202
1
< 2 exp
162n
10"
The first inequality follows from Equation (5) and the second holds whenever sufficiently large constant factor. Finally, we show Smedian is concentrated with high probability. i.c.
for some
pe
Pr [Smeddian - u(p) 2
m
P 4
16
Note that the median fails to satisfy the concentration condition only if at least half of the intermediate statisties S, do not satisfy the concentration condition. By a Chernoff bound, this occurs with probability most p for mn
(log) 1) sufficiently large constant.
Now consider the case m 2
n
Note
Pr (ss - m()) 2p p. 16 E)) < 2 exp ss
(
p_
162
10
whenever 2 2 @ (pte2) Concentration of Smedian then follows from a similar argument as above.
13

---

Sublinear Case: m S n
We now consider the sublinear case. Again, we consider single iteration j and examine the concentration the test statistic S = Sy. Following an observation from [16], we rewrite the test statistic
X; m
X; m
1
2 7
Z
S
1[x; = = 72
(iis.t. X; = 031 n
11
where we define the random variable Z = 1ft s.t. X; = 0}}-
Our goal now is to bound the variance of Z. To do so, we further define some useful random variables.
Preliminaries Let E [n] be the m samples drawn, i..., T, denotes the element corresponding to the i-th sample. We use ....., Ym to denote whether the i-th sample collides with any samples j < i, ie.. Y = if and only if there exists some , < such that T; = T). We will consider decomposition of the domain into "heavy" and "light" elements.
Definition A.2. Let p be distribution on [m]. For each k [n], is heavy if 3 log 1on and
light otherwise. Let H n. denote the number of heavy and light elements respectively.
Let bk.p 1[p 2 2. log 10m] indicate whether k is heavy element p. When the distribution is clear, we omit p and write bj.
m
define Yi,...,ye Ym to indicate that the i-th sample comes from some light element and collides with some previous sample: Y, Y; 1 (by, 0}. Let denote the number of occurrences of heavy elements among the samples: / = s.t. by, = 1/. Finally, define ZH, Zr to be the contributions to from heavy and light elements respectively:
ZH = (i s.t. by and X, 0}} s.t.
Z = ii s.t. by 0 and X; 0}}
We then show the following.
Lemma A.3. Var (Z) S
10m Σ E [Y). In particular, Var(S) Var(2) + 32logg
0a
500
n2
500m
32
log
10n
> T E [Yi].
1
Proof of Lemma A.3. Recall the random variables Yi.... Ym to indicate whether the i-th sample collides with any samples j < i. Then, we obtain the following identities:
2 = n m +
Y,
ZH + Zz.
2=1
Zμ = Hi s.t. s.t.
X; = 0 and by = 1H
Z1 Hi s.t. X; and 0}} nn (m H) Σ
We will bound the variance of ZH, Zr. separately. First, we that ZH with high probability. In particular, the probability that an element with b = 1 does not occur in m samples is at most
(1 Pm ) that applying the union bound the probability that some heavy element does In particular,
not occur is most T0 showing Pr(Zn
0)
o²
1000n
Var(Zn)
Pr(Zn E)E
t=
S n 1000n2
p²
1000
14

---

In the remaining proof, we bound the variance of Z7. To bound the variance of Zz. we separately bound the variance of H and Σ Y, since 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 constant multiple of the expected number of collisions.
Lemma A.4.
B
E
Σ P E 2 Var(H). b,=
Proof of Lemma A.4. Note that H is binomial random variable that its expectation is upper bound on its variance. Since the Y, are non-negative random variables and E [Y;] is increasing in i, suffices show the following lower bound:
Y
24 4
Σ
B|Y] 2 2mlE [Ym/2] 2 m Σ Pe
1=m/2
b==1
equivalently
E [2/22] Pr(Y m/2 = 1)
Σ Pk. b==1
Consider element & such that by
equivalently P& 2 3. log 10n Then, the probability that
m
k does not occur in the first m/2 samples is at most (m--1/10)$/² most n elements, each element with by = occurs in the first m samples with probability at least
/10)3// < _ Union bounding over at
2
1 10 2 9 10- Conditioned on this, Pr(Ym./2 = 1) 2 Σb
Pk so that we conclude
Pr(Ym/2 = 1) 2 Σ
P
10
by
Now, we move on to the term Σ Y.
Lemma A.5.
Var
Σ
Y2
<
1 + 3 log
10n
Σ
EY]
E
Proof. Using linearity expectation, we have
272
EE
Σ
E
Y:Y,
i
since Y, is indicator variable. Considering the second term, introduce the variables Zi,; denoting whether the i-th and j-th samples collide, i.c. Z,, 1[T Ty] We can write
For the first term, E
?
E Y
Y = Pr(Mi = Pr Pr = 1, Z = 1) + Pr Pr(Y; = 1, Zz, = 0).
We now bound the first term.
Lemma A.6.
10n m
10n
m
Σ Pr(YYY,Z,, = 1) 3 1
Y
3 log
E
[Y]]
p
:=1
Proof of Lemma A.6. The event V/, 8,y,,11 = Zz.j = such that
happens when there is some element k [M]
15

---

1. by = 0
2. both samples T; = =
=k
3. some samples from Tæx falls in We denote this event as Ei
We compute as follows:
Pr(Yy = 1)=
Σ
Pr(Ea, = 1) (T - = k)
by
Pr(EA, 1)pk
11 =0
3
10n Σ
log
Pa Pr(Fix =)
b==0
3
10n
log
E
where in the inequality we have used by = 0 gives an upper bound on ps. Then, for each i we sum over m m indices j # to conclude the proof.
For the second term, argue it can be upper bounded by Pr(Y, 1) Pr(Y =1) with Kleitman's Lemma. We define monotonically increasing and decreasing subsets.
Definition A.7. Let σ, 1," We say I 3 y is 2; S y for all E [n]] A subset SC 1, is monotonically increasing if x E S and x 3 y implies E S. S is monotonically decreasing if S and y S x implies y S.
In fact, we require small modification of Kleitman's Lemma.
Lemma A.8 (Kleitman's 's Lemma [2]). Let Q be a distribution over random bit strings 1,,1. Let A, B be two subsets of {0, 1, 1, such that A is monotonically increasing and monotonically decreasing. Then, it holds
Pr (A(Q)B(Q) S Pr Pr (B(Q)),
where (QQ)B(QQ denotes the event that random string draw from Q lies in A, B.
Proof. Kleitman's 's Lemma is proven for distributions over random bit strings (0, 1)" or equivalently subsets of [n]. replacing the < relation with S inclusion. Given distribution Q over {0. 1,2 we design a distribution Q' over [2n] as follows. Let u E (0. 1, 2)" We map v to the subset U S; where S; 0 if v; 0, S (2i) if v; = and S; = [2i 1, 2 if e; 2. Denote this mapping as f. This naturally induces a distribution Q' over subsets of [2m]. Let (f(a) s.t. a E A) and 18' = (f(b) s.t. BJ.
Note that we can add sets with probability under Q' to A' (resp. B3' ensure that they monotonically increasing (resp. decreasing) without changing Pr((A") (resp. Pr(B')). In particular, suppose there is set X A' and Y A' such that X C Y. Since A is monotonically increasing subset of {0, 1, 2) Y & A' implies that Y; = {2i 1} for some E [ni]. but this set has probaility 0 under the distribution Q', so we can safely add A'. In particular, applying Kleitman's 's Lemma
[2], we obtain
Pr (A(Q)B(Q)) = Pr Pr (P (()
Using Lemma A.8, we bound the collision probability of distinct buckets.
Lemma A.9. For i j. have Pr(ý, V, 1, Z., 0) < Pr(y; 1) Pr(V; =1)
Proof of Lemma A.9. Without loss of generality, we assume i < j. Recall Te: = =TT2.... T;-1). The event 8, y, = 1, Zz,5 happens when there exists two distinct elements * l E [m] such that:
16

---

1. the i-th sample is S; = k, the j-th sample is Sj = =(
2. some samples from Seg fall in k. some samples from Sej fall in f. We denote the two events as Eig and E respectively.
Hence, we can write
Pr[y Y, 1, ر = =0
E k
Pr[ErR, Ey,el Phe pe.
(6)
Fix pair of & < L. Consider the string g(k.() such that 3(1..) 0 if the i-th sample falls in the k-th bucket, 3 3(8.6) 1 the i-th sample fall in neither k-th nor E-th bucket, 3(t..) = 2 the i-th sample falls in the f-th bucket. Then, both events E Ej are completely determined by the string 3(k.)) Moreover, the set of strings for which Éi holds is monotonically decreasing and the set of strings for which Eje holds is monotonically increasing. As a result, from Lemma A.8 we have
Pr(E,,&E,,) S Pr(zz))
Substituting this into Equation (6) then gives us
Pr(tr 1, 10 s
Pr(Ege) Pr( Pr(EEx)) Pe
< Σ Pr(Ee,))Pb
Σ Pr(E,,))p
&
< Pr(O Pr(y =1)
To bound the total contribution to the variance of the second term, we sum and obtain
Σ
Pr(f, 1, Ziy=o) - E
E Y
1
Note that Eizs E
Yi
E
Y
is most E
Σ Yi
that we bound the variance
27
Var
Σ
E
Y
10n
+ 3 log
[Y]]
+
Σ
Y
10m
1 + 3 log
Σ E. [Y
P
Li
We thus obtain the following bound on the variance of Z, proving Lemma A.3. In particular,
Var(Z) < (Var(ZH) + Var(Zz))
p²
m
<
+4
4
Var(H)) Var
500
0
10n
7
20
[Y:]
12 log
E
500
P
p²
10n
+
32
log
[
500
P
1=1
17

---

We are now ready to prove the required lemma.
Lemma 3.3 (Sublinear Concentration). Suppose m S. n. If Var(S) 2 (C/64))2=*m"n" then [[s] - / (Sr > ju(Un) Ce mi n² where p(Un) is the expectation of S under the uniform distribution and given by Lemma 3.1. As a consequence, with probability least p/4, we have Smedian > p(Un)) + C²?m²n -2
On the other hand, if Var(S) S (C/64))=="m"mm
then it holds that p/4. Furthermore, for the uniform distribu-
Pr meddann [u()) (C/16)
tion Un. Var(5)
Proof. Our proof considers two sub-cases. In particular, argue that when the variance of the test statistic 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)= 2 (C/64)p"''m*r>
We 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 S n. Let p(Un) be the expectation of S given a sample from Un- Then
m
((U))
Proof of Lemma A. For each i, note that there most m distinct elements sampled before the i-th sample. In particular, EE [Y:] Pr(Y; = 1) v m for all i. Then, since the sub-linear regime m we have the identities
= 72 171 +
Σ Y,
We can write the expectation of S as
E [
n m +
Em E [Y]
(UU)) = E [S]
so that
n (U,( = -
V E
<
m
111
Now, show that when the variance of S is large, with probability at least 38 S ((U,) Ce m where C' is the constant given by Lemma 3.1. Since S = 2 this holds if and only if
Z 2 ((U,). + C
The expectation of Z is
[Z| = n n m
[Y]]
From Lemma A.3, we have Var(Z)= = 0 (p² log(n/ Em E [Y]). By Chebyshev's inequality, we have that
1
Pr Z
10Var(Z)
10
18

---

Therefore, it suffices to show E E beyond the random threshold and the algorithm outputs REJECT. We rearrange the desired inequality as follows:
100Var(2) 2 p(Un) + Ca nz. If this holds, then S is
E|Z] V 10Var(()) 2 n ((Un) Co m
n12
10Var(2) 2 Ce² 2 n
E [2] - n ()U,))
Plugging in E [2] - n u(UU) 2
E
[X] suffices to show
i=
m
m²
10Var(Z) 2 Co m
[
n
12
which is true as long as
v 10Varr(Z) 2 20 m2
E [
Thus, applying Lemma A.3, remains to show
m
10n m B
m
10n
m
m
Σ
[Y]]
+ 320 log
B
320 log
R
B 2 20
50
n
1=1
1=1
f=1
since va + b < va + vb and v p5050 < 1. Finally, we observe that by our choice of m, we have 2Cm² >> 1 so that it suffices to show
m
10m
[Y] > 3C m2
Σ
E
320 log
E
We simplify the left hand side with the following lemma.
Lemma A.11. For any x 2 1280 log 10n
p we have
10n x
320 log
P
2
Proof. Suppose x 2 log 10n, Then the inequality holds if and only if
T 2 320 log
10n
2
10n P
V2 2 2 320 log
10n p
x 2 log
We now lower bound Σ E [Y.]. First, from Lemma A.3 we have
Var(Z)
p²
Var(S)n²
pa
E E 2
500
500
32 logo loloo1100 10n/p)
32 log (2llo((0//// (10n/p)
By assumption on Var(S) 2 (C/64)p m "m'n we obtain
m
(C/64)p²=* m 'n -2 -000//500
E EY]]
32 1221(110// (0n/p)
19

---

Finally, since m >> V Vlog(n/p) for some sufficiently large constant, we have
log (n/p)
(C/64)p==<m"n" p²/500
p²
Then,
Log"(n//
2 1280 log "
R
log(n/)
Thus, we conclude by
B [X]]
320
10m
m
E
[Y]]
2 Σ E [r]
2 20 m
7
where the final equality follows from
(C/64))p² m p² /500
log (n/p)
log(n/p)
Σ 2
(8)
56 log 110//p)
22 log(n/p)
p2ed
and
log(n/p) m o
p2gd
and if we choose an arbitrary large constant factor of m, left hand side Σ TE [Y;] 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 -- Again applying a Chernoff bound, Smedian does not lie above any random threshold with probability at most 4.
For the high variance case, it remains to show the inequality
E S Var(S) 2 u(Un)) + C²
2
m²
122
From the identities S = Z/n and Z = n m Σ Y,, Lemma A.3 and Lemma A.10, we can rewrite the above equation as
Σ EE m² //
32
10n
m2
log
N
CE
500n
n²
n?
and we can lower bound the left hand side as
E Y
m
32
10n
ΣE YY
32 log
10n Σ
F (Y:
m
log
Σ
E[Y
2
n
72
n
n2
Σ E Y
m²
2n
n
12
where obtain the first term by using Va+bb < Vā+ and /² by grouping similar terms, and the final term by our assumption on Var(S) and therefore IF [Σ Yi). Therefore, suffices to show
and
(5/000)) n2, 2, the second term
m²
+ Cea m
Σ 2
or since m²n 1.
Σ EE > ma 1) m²
which follows from the lower bound EE given by Equation (8).
20

---

Low Variance - Var(S) & (C/64))²²
We show that whenever the number of expected collisions is low, the test statistic well concentrated. By Chebyshev's inequality, we have for any iteration j that
Pr (s, (18,-168 (18)-1(p) u(p)
m n² = Pr Ss, 11()) > 4
C m 64
16 06
pe
<
ni
10
Using a Chernoff bound as previously, we obtain the same concentration result for Smedian with high probability.
Finally, we show that for the uniform distribution Un, we have
Var(S) S (C/64))p='m**a
We observe that for the uniform distribution, EE [Xi] S since the i-th sample can collide with at
most S m elements before it and therefore Σ [Y I m² Then, from Lemma A.3,
Var(Z) n²
24 @Alog(10m/p
24m log 1og(10n//p)
Var(8)
[X]]
n²
n13
We thus require
24m log(10n/p)
I (C/64))'='m'''
n3
1536n
log(10n/p))
I m
Cp
Vn
log
<<
2
p
which is satisfied by our sample complexity m.
B Omitted Proofs for Replicable Uniformity Testing Lower Bound
B.1 Proof of Lemma 4.4
We begin by bounding the mutual information of the sub-linear regime.
Lemma B.1. Let m to < 1. Les 8 |c0 E and & max(Eo, 81). Then,
Pr(M = a. .2 b X 0) Pr(PPrMMMM a, M2
1))²
(2 n²
50
(9)
Pr(M: a, M2 b)
o.bEN
Proof. First, let us expand the conditional probabilities for a fixed a, b. Expanding the definition of the random variables M1, M2, X and applying the probability mass function of Poisson distributions, we arrive at the expression
Pr(M = a, M2 = X = 0) 2a!b!
exp
2m
m
a+6
(11 =v) (1 =0)" + + - (1- (1 + (1+))))))
2m
m
a+b
(1 (1+6)) (1 - (1) + -0 (1+)1))
Pr(M: = a, M₂ = b X = 1) 2a!b!
exp
Define the function
fa.((z) = (1+ (1 2)² + (1 x) =)².
21

---

Then we have
(Pr(M1 a, M2 = X = 0) Pr(M = = a2 = X = 1))²
Pr(M1 0, M2 b)
a,bEN
1
2m
a+b
- Sab(ee) + Sa,b(50)
0(1
exp
a,eEN
a!b!
n
01)
Σ
a!b!
exp
2m
m
maNcosusei (gs (a,(aa)) (el - 80)
fa,s(Eo) + fa,b(11)
(10)
a,NEN
where in the last line the mean value theorem. The main technical step will be bound from above the quantity
maXeos=Se, ( (alas))) Specifically, we show the following technical claim. (o.llo))
Claim B.2. There exists an absolute constant C such that
{
iff+tbs1 (at + b+)²² if < 5
( (a,aa(()))
max COC
(Ja,(55) Sab(Ei))
=C
a+b b)2 (1#:)
fatbbe-
Proof. If & 1, fu,(() = Thus, 4 fa,(() = 0, which gives the first case.
We next analyze the case 2 a ba+bse= Note that (z. is an even function with respect to æ, i... fa,(()) = (f,0(-x)) This allows us to write fa,((z) = & (fa,(()) + fa,((-z)). As a result, we can conclude that (z) does not contain any monomial of with odd degree. Thus, write
Sab(x)
cabb
Σ
(a) 0 d
dE(a+b] is even
for some coefficients (d) that depend on a, b only. This implies that
á = fab(z)=
de(d) de xd
Ox
(E( is even
(d) When 2 < a b-+ 1/212 the coefficients ca,b is of order (att). Since x < must have that (d) Id Cab 2d-1| decreases exponentially fast in d. This shows that 2 fa.(()z) is dominated by the contribution from the monomial ke.b/o). which implies that
max 5o C3<
dx fao(z)
s O(1) (a b)²..
(11)
To finish the analysis for this case, it then suffices bound from below fa,((E)) + fa,6(E1). Without loss of generality, assume that < b. Then we have
(a,((1)) 2 (1 e 2(1 ae 2 2(1);
(12)
where the last inequality follows from a S + b b<b /2 and E < E. Combining Equation (11) and Equation (12) then concludes the proof of the second case.
Lastly, we analyze the case (a + b) 1 In this case, for en S E1, note that
dr (a) (1 x)) (1a
b
1+ 1-x) (1- x1 - 2/²
1+x
then follows that
0 dr
la (x)(
$ 50(a + b) ((1 + x1 - 3)²² + (1 x1 + +z)²)
<( ((1 x))* (1 +1)
(13)
22

---

where in the first inequality we use that Iu v| I uut + v for any u, > 0, and the second inequality simply follows from x < We can therefore conclude that
fmb())) Ser (a,(50) + (ab(ei) x (a)
+ +
max
(1+6)) - (1- (1+61) --1) 61)
(1+ (1+
< {(()aa++ +)²
(1-
(1 =1-
1 (1+ E1
S 50()((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 E and bound from below the denominator by fe,((E), ).). in the second incquality we use the fact that (u + u)² S 2u² 2u², and in the last inequality we use that (1 + )1)". (1 =1)- are increasing in and (1 + =1);, (1 ex) 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
(Pr(M a, M2 bl X = 0) - Pr(M = a, M2 bb X 1))² 0.
(14)
Pr(M] a, M2 = b)
0,b:0-bb2
Consider the terms with 2 2 a 5= From Equation (10) and Claim B.2, we have that
(Pr(M a, M2 b X 0) Pr(M a, M₂ b X 1))²
Σ
Pr(M = a, M2 = b)
a.b:25abbe-11p 1/2
20(1)
Σ
exp
(_2m n
2m
a+6
(a + 62)
a!b!
n
a.b:gotbge 1/2
Σ
Σ
a
m
a+b
Σ
m
a+b
(15)
a!b! aENb:25o+bse 1
a!b!
bEN a:25a+bee /2
Define
A
EnEN Emtogatoge=12 al!
m
a+b
and
EDEN Eessatbse-1p 12 aldl n
m2 a+b One can see the two terms are similar to each other.
So we focus on the term A. We have that
/2
A
Σ
1+b
a
Σ
1
n
D!
brb2Ca+bSe-1p
1/2
$ 01)
(
m
+11)
a
a!
2>2
I (1)
(m)
m
2
+ (1) cxp(m/n)
Σ cxp(-m/n) a(a a(a-1) 1) + a(a 1)(a - -2)(a -3) x22
m
n
a!
n
m
< (11)
+ +11 exp(m/n) Ey-Poi(m/m)) Ivly - 1) + v(v - 1) 2y - 3)]
m
< 0(1)
n
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, the second inequality we use the fact that at is at most 10 (a(a- - + a(a- 1)(a 2) - -3) for all 2 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 use the fact that
23

---

By--Po(t))l(( - +)+ - - 2) 3)] = X2 X². One can show the same upper bound for
B via an almost identical argument. Substituting the bounds for A, B into Equation (15) then gives
(Pr(M) = a, M2 = b X 0) Pr(M = a, M2 = x = 1))² S O m
2
Σ
Pr(M1 a, M2 b)
a.b.gaabbe 1/2
(16)
then remains to analyze the terms where a b 2 e- 1-1/2. Again from Equation (10) and Claim B.2, we have that
(Pr(M) a, M2 b1 X 0) PM(M = a, M2 = b X 1))²
Pr(MI a, M2 = b)
a,
s <0(8²
Σ
1
m a+b
(a + b)j
1
a!b!
1- E
abba 1/2
0(8
Σ
m
1
1+
a!b!
856- 12
abb
20(89)
Σ
m 1 1+
8²
n 1
Ls/2J!
8>6-1/2 /2
g3
m 1+
)
00(
<0(0'>2(m//)) s=8-1/2
(17)
8/2J!
2 n
where in the second inequality use the observation that we must have either 2 8/2 or b 2 8/2 a + b = 5, in the third inequality we note that the summation over 8 decreases exponentially and is therefore dominated by the term where 122 and in the last inequality we use that s²/ [s/22/ S O(), (m/n)="*/2 (m/n)?, (1+=)/(((1=)) 0.9, and that 0.9= for sufficiently small e.
/2 < poly (s)
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 |80- s and max($o. Let n < < 0
Then,
log n
(Pr(M, a, .2 b X = 0) Pr(M a, M2 b X 1))² Pr(M1 = 0, M₂ = b)
==00mm² log' +o(1/n). 50
n
a.DEN
Proof. We note that for a Poisson random variable y with mean À 2 1. we have by >| VAlogn with probability most o(1 /n) We can focus the terms where E [A vo n, A vAlog no 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 function
+ +(1 (1-x)) (1) =) fa,((z)= (1 + x1 (1- 2)"h (1-
Instead of computing the derivative of fa, directly, we will first rewrite it slightly.
fx) = exp (a log(1 + 1) + blog(1 - x)) + exp (a (og(11 - x) + 6 blog + r))
= 2 + aoo - z²) + blog(1 - -1²) ,²)
(a log(1 1 + x) + blog(1 z))² + log(1 x) + blog x))²
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, define
(a log + x) + blog(1 - x=))
(x(x) = log(1 - =²²), ())bb()) =
i!
24

---

Then we have
fa,((x)= = - (x( + 96(z) + ha,((a)) + ho,b( xxx).
(18)
We first analyze Ia (z). When E [A - VAlog n, A + log ni,, we have that
- c 1- E 1 a
1 c
(9a(E1) 9a(E)) = alogg
1- E
(Eo + E1 l80 E1 S 0
logn)
(19)
- of
n
where in the first inequality we use the fact [log(=)] S x - for x 2 1, in the second inequality we use our assumption that max(fu. S E and (gg E1 - 6, and our assumption that |a m/n/ < log / m/n n. Using a similar argument, one can also derive that
l9b(21) (50) S 0 m 8 logn).
(20)
We then turn to the term (x)) The derivative with respect to x given by
①
b
lalog(1 + xx) + b blo((1 x²)²-1
dr h ha,b(x)=
1 +
x
1 1-
(i 1)!
b
(a1 + x) (1+ x)²² 1)
1+ 1-x
where the second equality follows from the observation that the summation exactly the Taylor approximation of exp (a log(1 + =:) + blog(1 - =)) without the constant term. We next proceed
to bound from above 0 dir (x)( First, when is sufficiently small and a, b lie in the range
m log n, note that n
b
la b ((x)(a (0 b)
+ 27
< aa bl + (a bz)((z)
2/ log 2 2-x
2 m
log(n)æ
n
n
0 log n
(21)
m
where in the first line we approximate I4s and T-z with 1 (xr) and + Ozz) 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 / log is the dominating term when x e and m < n//e2. Next, under the same set of assumptions, we have that
((1 + =1 a:)² 1) - (1 - x. 222 + 11)la-bl -1) -1)
< ((1 Obbz))((()))))) O(la b1)xz) -1) 1)
0
m
log
(22)
n
where in the second inequality note that since bx? 0 mh c2)) < and la b/ O (v n log(n)e) < we can approximate (1- =2)0 and (1 + 27)a- by (1 O(ba2)) and
O(la b))x) respectively, and in the last inequality we use the assumption on the range of a, and x <. Thus, combining Equations (21) and (22), we arrive at the upper bound
max xE(eo.e1l Oz (a) 5
m log" n)
n
25

---

when m - mm/nnoon I a. m + Vm/nlogn. Therefore, by the mean value theorem, we have that
(a,b(E1) ha,b( s O (=8" m log" n)
(23)
n
Following similar argument, one can also derive the upper bound
hh,b(-E1) ha,b(-Eo)) - 0 (s8 m
log n)
(24)
Combining Equations (18) to (20), (23) and (24) then gives that (fa,((E)) fa fa,b(Eo)1 S O (co m
log
(25)
Recall that in the proof of Lemma B.1, we have that
(Pr(M1 M2 = b X 0) Pr(M1 = M2 = b X 1))²
Pr(MI a, M2 = b)
a,
0(1)
Σ
exp
2m (-n n
a+b (fa,(E)) fa,(E))) Sap((1)) + Sa,b(Eo)
(26)
a!b!
a.bEN
Hence, we proceed to bound from below fa,0(E0) + fa,((E1). Note that we have
(a,(50) + fa,b(51) 2 (1 - x2)min((.b) (1 + x)) la ba 2 1 O(min(a, b))2))))====))))))))))) 2 2(1),
(27)
whether b, in the second inequality we approximate (1 x² miin(a,b) by - (a,in(a, b)x²) since (a, b)z² = o(1) for b in the
where the first inequality follows from case analysis
assumed range and r < e. Combining Equations (25) to (27) then gives that
(Pr(M, M2 b b| X 0) Pr(M, a, M2 b X 1))²
Pr( M| a, M22 = b))
a.bEN
00
Σ a.eEN
1
log a.b
log
exp
2m
a+b
2²8²
2
log
n
a!b!
n
m
(1-
Pr a,bxPoll(m/n)
m/n - v mm/nlog & a, b S m/n + v mmmmn//nn log
< 282
m
2
log* n o(1/n).
This concludes the mutual information bound for the super-linear case.
I Lastly, we present the mutual information bound for the super-learning parameter regime, i.e., m 2 Ω (n/e2).
Lemma B.4. Let 8 JEo sil and (1) Let m Ω (
Then it holds
( (=2 log? n
I(X MI, 12) 0
n²
We are going to use the following facts regarding KL-divergence and mutual information.
Claim B.5 (Convexity KL-divergence). Let w E (0, 1), and Pr, P2, 9ı 92 be probability distribu- tions over the same domain. Then it holds
KL(wp1 + (1 w
w))pllluy wwq + (1 - w)q2)= S WKL(pz (lq:) + (1 -1- KL-W)KK((pllll
Claim B.6 (Additivity of KL -ileeivegeence.. Let E (0, 1), and P1,P2, Q1 U2 be probability distribu- tions such that P1, qi share the same domain and P2, q2 share the same domain. Then it holds
KL(pi @ p2llę1 & 92) KL(pilla1) + XL(p2ll92)
26

---

Claim B.7 (Mutual Informtion Identity), Let X be an indicator variable. and Ho. H1 be a pair of distributions. Let H be the random variable that follows the distribution of Ho if X and X, if X =1 Then it holds
1(x: H) - - KL Ho 2 (H] =Ho)) + +Z (11 (1I +Ho)
Proof of Lemma B.4. When X = O. the pair (M1, M2) is distributed as a even mixture of two distributions that are both product of Poisson distributions:
(M1MMb | (x= =) ~ Ho = 2
Pooi
m + EU
m
Poi
m
Eu
m
+ Poi
m
ED
m
2
Poi
m
+
Eo
m)
m n
n
n
n
Similarly, we have
(M, M2) | (X= = 1) H1 =
Poi
m
+
S1
m
Poi
m
m E1
+ Poi
m
61
m
69
Poi
m
+
E1
m -
n
n
n
From Claim B.7 and Claim B.5, we know that it suffices to show that the Ki--dieengences between Hu and H1 are at most 52 log", n²
We focus on the argument for KL(Ho H1) as the one for
KL(H, Ho) is symmetric.
By the definition of Ho and H1, we have that
KL H11 -
KL
Poi
m
+
m
Poi
m
m
Poi
m
+
E1
m
Poi
m
m72
+ KL
Poi
m
90
m
Poi
m
+
80
m
|Poi
m
61
m
8
Poi
m
+
E1
m
2
n
n
n
= KL
Poi
m
+ co
m
|Poi
m
+
mm
m
+ KL.
Poi
m
60
m
|Poi
m
E1
where in the first line we use Claim B.5, and in the last line we use Claim B.6.
Let Å > A2 O. Note that we have the following closed form for KL divergence between pair of Poisson distributions:
A X2
+ A2 - A1 (Λ1 - A2)
KL(PPi (Ar) ||Poi (Aa)) = Aı log(A1 + A22 - A1 S A
A2
where in the first inequality use the bound log(x) x for all
0. Hence, it follows that
m (51 - E0)
HL(Ho
< 0(1) 8
m1
(1++1)
But notice that this is at most O assumed parameter regime in this lemma.
==26 log² log²""
n² as long as m > (2ng which is our
By setting 5 = |e - cul = O(p)), follows from Lemmas B.1, B.3 and B.4 that I(X : M1, M2) < O
2 log' +0(1n)). Since the pairs M,, Mo+1 are conditional independent and have identical n distributions given X, follows that
T(X; M1, M,, T(X; M1, M2) 50 c=00mm² log" 11 los²") o(1).
n
This concludes the proof of Lemma 4.4.
B.2 Proof of Lemma 4.3
Proof. Let T' be set of samples. In case one, 7' is made up of samples from random distribution from Mg. In case two, 7 is made up of m samples from a random distribution from Mi. Assume that there exists tester A that can distinguish between the two cases given S with probability at least 0.9. We will show that this implies that = ÿ2 (Vn=-2pp) Recall that Lemma 4.4 has the following setup. Let X be unbiased binary random variable. If X 0, S will be Poi (2m)
27

---

samples from a random distribution from Mo. If = 1, S will be Poi (2m) samples from random distribution from M₁. Then we can use A to predict X given S in the following way: if S contains more than samples, we feed A the first m samples and take its output; otherwise, we declare failure. By the concentration property of Poisson distributions, holds that 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 is at least ((1). However, Lemma 4.4 says that the mutual information is at most
2 log (n)) + o(1).
O
p
n
This therefore shows that
62p 0² m
log (n) (ng)(n== 21(1)
which further implies that
m == 2 @V=loo (n)s -2--)
This concludes the proof Lemma 4.3.
B.3 Proof of Proposition 4.1
Proof. Let m = o (v'ne" 2pp=)pp-) For the sake of contradiction, assume that
|Acem (su) - Accm (=1)l > 0.1
for some deterministic symmetric tester A(;r). r). Let Mo: MM be the local swap family of p(0)) and P(E1) respectively. We show that this could be used to distinguish between random distribution from Mo and a random distribution from M₁. 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 My must be exactly equal to Accm (Eo) (and similarly for M1). This immediately implies tester that takes samples and could distinguish between random distribution from Mg and a random distribution from M1 with probability at least 1/2 + for some small constant c. This further implies that if we takes 100mc many samples, can boost the success probability to 0.99. Yet, since 100me-1 Ō (Vre" (/-1)-pp11) this clearly contradicts Lemma 4.3, and hence concludes the proof of Proposition 4.1.
B.4 Proof of Theorem 1.6
Proof. The lower bound 0(==2pp follows from the fact that testing whether an unknown coin has bias 1/2 or 1/2 + replicably requires 52 (s-2p-²) many samples as shown in [30]. In the rest of the proof, we therefore focus on establishing the lower bound 52( ((VTE=-2p 2p-1).
Let p(E) be the distribution instance defined as in Equation (4). Let A be a p-replicable uniformity tester that takes 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 such that (i) A(:r) accepts the uniform distribution with probability at least 1p)(p) (ii) A(;r) rejects the distribution p(e) with probability at least 1 (p)) (iii) A(; ) is replicable with probability at least
(pp) against p(E) for & sampled uniformly from [0, =). By the correctness guarantees of A, a large constant fraction of random strings must satisfy (i) and (ii). By the replicability requirement of A. large constant fraction of random strings 7 must satisfy (iii). By the union bound, there must exist some random string that satisfies (i), (ii) and (iii) at the same time. Define the acceptance probability function
Pr [A(S:)) 1]. Accm (E) S~u(() cm
Note that Acc,, (E) is a continuous function in since the acceptance probability can be expressed as a polynomial in E. Moreover, holds that Acc,, > 1 -(p)) and Acc,,, < O(p). Therefore, there must exist some 5" such that Ac*m 1/2. Assume for the sake of contradiction that m ö(vnE pp-1) ). By Proposition 4.1, it follows that
ACCm(E) [Accm (E*) 0.1, Accm. + 0.1] [0.4,
28

---

for any such that 15 - [ S pe. In other words, if we sample & randomly from [0, whenever Ç falls into the interval k p + pel, the algorithm will fail to be replicable with constant probability. It is not hard to see that the interval has mass (pp) under the uniform distribution over [0,e]. This would then imply that the tester would not O(p)-replicable, contradicting property (iii). This shows that m (D(vi==2 2ppppp 1), and hence concludes the proof of Theorem 1.6.
C Further Discussion and Omitted Proofs
In this section we give additional discussions and omitted proofs.
C.1 Barriers for x2 -Stttistisss
We show similar barrier for using the x2-test statistics. These statistics used in the several uniformity testing algorithms, including [14, 1, 47, 20]. The x² test statistic (of [1] for example) computes
(X; -m/n)² X;
Σ ieIn
m/n
where the algorithm takes Poi (m) samples and computes X; to be the frequency of the i-th element among the samples. For uniform distribution. the test statistic is expected to be at most mE² mE²/500 /500, while the test statistic is far from uniform the test statistic is at least mE² /5, leading to an expectation gap with around ma? (Lemma 2 of [1D. Suppose a tester compares the test statistic with random threshold sampled from the interval [ms² /500, me² /5). For the tester to be ((p)-replicable, we require that the test statistics deviate by more than Oppns?) with high constant probability, in other words the variance must be at most (pp (p2
As before, we fix constant > 0 so that we can ignore the dependency with sample complexity, and consider a hard instance of a distribution with single heavy element with probability p: = n 1/2, In particular, we will have X, Poi (mp:) = Poi (m/ mn//)). Since m/ / > 1, there exists some constant small constant such that
Pr[X, m/ cymmm// c,
Pr[X, < m/Vn - c/mnmm////////
However, in the two cases above, the contributions the 2tttest statistic from X, differ by
vn
1//
V
n
+ 2c
mm n17
Ω
3/2 n
+
1/4
m/n
m/n
Ω
(/mn2/1
Following our previous discussion, for the tester to be Oep)-eellcc,ll,, therefore require that m. 1/4 < pm or 2 p
C.2 Discussion of Lower Bounds against Asymmetric Algorithms
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 harrier hit by our lower bound argument for asymmetric testers. Suppose want prove lower bound against general algorithms. The known techniques for lower bounds against replicable algorithms first fix a random seed such that A(;r) is both correct and replicable with high probability given distribution drawn from the adversarial instance (in lower bound the instance draws distributions p(E) uniformly from & E [0, s). Given a fixed random seed,
'I our lower bound, we use the local swap family to restrict the adversary to subset of permutations. In this discussion, allow more generic adversary that could permute the domain arbitrarily.
29

---

we now have deterministic algorithm A(;r) that accepts p00 and rejects any permutation of p(E). By continuity, for any fixed permutation и, there is some & such that A(;r) accepts with probability
1 1/2 given samples drawn from p({=) permuted according to æ. It remains to argue that algorithms with low sample complexity m < /np-ig-2 cannot successfully distinguish nearby distributions P(a):: ). P({) (both permuted according л) for any E (Ex Pe)) so that the acceptance probability of A(₃r) must be close to 1/2 in this region and therefore A(;r) r) is not replicable with probability s(p).. However, our arguments in Appendix B only show that the families p(E.), P()) are indistinguishable when permuted by a random permutation T not necessarily when permuted by the permutation æ. In fact our proof only allows to argue that for any 5' [0, E], the families indistinguishable when permuted by a constant fraction of permutations x' However, the permutations for which the families P(5'), p(' pE) are indistinguishable may not be the permutations for which En: 5 are close.
C.3 Replicable Identity Testing
The formal definition of replicable identity testing is given below.
Definition C.1 (Replicable Identity Testing). Let n Z.,, and e.P (0, 1/2). A randomized algorithm A, given sample access to some distribution on [n], is said to solve (n, p)- replicable identity testing if A p-replicable and satisfies the following for every fixed distribution X:
1. If is X, A should accept with probability at least 1
2. If p is e-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 [ni with known explicit description. There is a (randomized) algorithmm T such that given m independent samples to a distribution on [n] and e > O, generates m independent samples from distribution p' on [6n] such that:
1. If = p.pp' is uniform on [6n].
2. I is E-far from q in total variation distance, then p' is s/3-far from uniform in total variation distance.
Furthermore, this algorithm runs in (m) time.
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 '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.
As in the case of uniformity testing, we do not focus on the dependence of the sample complexity with the parameter.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the claimed algorithms and lower bounds are proven in the paper. Further- more, we qualify the limitation of our lower bound (only holds against a specific but broad class of algorithms) in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The primary limitation of work is that the lower bound holds only for symmetric algorithms. While symmetric algorithms a natural class and encompass all known algorithms in uniformity testing, it would be nice have lower bound that holds in general. We discuss this in our paper.
Guidelines:
The answer NA means that the paper has 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 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 few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
31

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
Justification: Yes, all claims are proven either in the main body or the appendix. For results not proven in the main body, we provide proof sketch and leave details to the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
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 or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
32

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.
wwreinissssnoooiiiioooo onPolicyl for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips.
wwwbbbmmsssooooiicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. 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: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
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: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
33

---

The method for calculating the error bars should be explained (closed form formula, call 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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative еттоr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: / http//eerrip..eee cc/pppblictBBiiccccuu.dllll.llll inees
Answer: [Yes]
Justification: Yes, the research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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 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.
34

---

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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include 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.
35

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
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 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 the supplemental material is fine, but if the main contribu- tion 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.
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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
36

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
37


Reviews:
[{"review_id": "7YSKtMRWt8", "reviewer": "Reviewer_H8kM", "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.\n\nThe 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.", "questions": "None.", "limitations": "None.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main strength of the paper is the improved upper bound. At this point several different approaches for the non-replicable uniformity testing are well-known. The authors manage to show that the empirical TV approach in fact gives the best bounds under replicability constraints.", "weaknesses": "The main weakness I believe is the lack of an unconditional tight sample-complexity lower bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "While our lower bound holds only against symmetric algorithms, we remark that all known uniformity testers in prior works are indeed symmetric. Moreover, in our opinion, symmetric algorithms are natural for the problem of uniformity testing as the property itself is invariant under domain relabeling. It is unclear whether there is any natural/intuitive way to exploit asymmetry in replicable algorithm design. We believe the fact that our lower bound holds only against symmetric algorithms is more of a technical issue than a conceptual gap, and we leave it as an important future direction to develop a fully unconditional lower bound.", "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": "vXla4wNODx", "reviewer": "Reviewer_MK1R", "summary": "The concept of \"reproducible\" learning was introduced in STOC 22 paper and the concept is a very relevant to modern day research. \nThey also showed how algorithms based on statistical estimations can be easily converted to reproducible algorithm with a little overhead. \nIn 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.", "questions": "NA", "limitations": "NA", "rating": 4, "confidence": 5, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "NA", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. While we have reviewed the extensive line of work on uniformity testing to the best of our abilities, we admit that our survey might not be complete. Thus, we would greatly appreciate any pointers to missing citations.\n\nIndeed, there is an extensive literature on uniformity testing, with a variety of algorithmic techniques. However, none of these algorithms explicitly guarantee replicability when the input distribution is neither uniform nor far from uniform. While there is a simple transformation to obtain replicable algorithms (by treating the outcome of a non-replicable algorithm as a coin flip), any such reduction introduces quadratic overhead in the replicability parameter. In particular, these algorithms require $\\sqrt{n} \\rho^{-2} \\varepsilon^{-2}$ samples.\n\nOur key technical contribution is a replicable algorithm that achieves sample complexity $\\sqrt{n} \\rho^{-1} \\varepsilon^{-2}$ in the worst case, and is thus the first algorithm (as far as we know for any statistical task, not just uniformity testing) that has linear overhead in the replicability parameter. While the algorithm is a simple modification of known algorithms, our primary technical contributions are new analyses in the concentration of the test statistic. Furthermore, as discussed in the technical overview, it is not immediately clear which of the many uniformity algorithms can be made replicable with linear overhead. We find one such test statistic that admits a replicable variant, and introduce new analysis to show that this is the case.", "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": "gNyoCQdwLV", "reviewer": "Reviewer_sPzn", "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).", "questions": "1. Related to weakness. Can you the high-level intuition?", "limitations": "None", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The cost of replicability (in terms of sample complexity) is not well understood. ILPS shows that a blow-up of 1/\\rho^2 is needed when the sample space size in 2. I belive this is the only known result.  It is natural to expect that a similar lowerbound holds for high-dimensional distributions. However, rather surprisingly, this work shows that this is not necessarily the case. Further elucidating the point hat the tradeoff between sample complexity and replicability needs much further investigation by the community. I really like the contribution of the work.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the encouraging comments. Below we provide some more succinct explanation of this surprising linear dependency on $\\rho$. First we note that this sample complexity is perhaps not so surprising if one focuses on designing testers for the specific hard instance we constructed in our lower bound section. In particular, for constant $\\varepsilon$, the i-th element of the distribution has probability mass of the form $( \\pm  \\xi) / n $, where $\\xi$ will be some randomly sampled value bounded from above by some constant $\\varepsilon$.\n\nIn that case, it amounts to estimating the squared  $\\ell_2$ norm of the distribution up to accuracy $\\rho / n$ (which is simply $\\rho$ times the usual expectation gap for uniformity testing). For this particular instance, since there are no elements whose mass is heavier than $2 / n$, the variance of the usual collision statistics is at most of order $m^2 / n$. Solving $m^2 / n < \\sqrt{\\rho / n}$ then gives the sample complexity bound of $m = \\Theta( \\sqrt{n} / \\rho )$. In short, at least in this case, the reason we have this surprising linear dependency on $\\rho$ is conceptually similar to the birthday paradox phenomenon (where we expect an $n$ dependency for uniformity testing but $\\sqrt{n}$ turns out to be sufficient).\n\nThe main technical challenge is to analyze the case when there are heavy elements. \nWhile the presence of heavy elements makes collision-based test statistics sub-optimal (as discussed in the technical overview), it turns out that their presence quickly pushes the expected value of the TV test statistics to the soundness regime, leading to replicable rejection.", "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": "elcUtv9Dcs", "reviewer": "Reviewer_g6cx", "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.", "questions": "Please see the question in the weaknesses section.\n\nCould 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": "Addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I find this work pretty interesting. I think uniformity testing is a natural application domain for the definition of replicability, since the decisions of the algorithm are binary so the discrete metric on the output space (which is what the definition is asking for) is a natural one for this problem. \n\nMoreover, the $\\sqrt{n}/(\\varepsilon^2 \\rho)$ sample complexity is interesting and has not appeared in the replicability line of work before.\n\nFrom a technical point of view, the upper bound is achieved by a standard modification of some non-replicable algorithm using a random thresholding trick. However the correctness is based on a concentration argument that requires subtle technical work, dependent on different regimes of the parameters that come into play.\n\nSimilarly, the lower bound follows the high-level template that has been introduced by prior work. Nevertheless, the technical details are not straightforward.\n\nI think another aspect of the results that the authors could consider highlighting is that, in this setting, replicability does not require any blow-up in the sample complexity with respect to the ambient dimension. This is in contrast with other tasks such as replicable mean estimation. The straightforward generalization of the approach of [Impagliazzo, Lei, Pitassi, Sorrell '22] to the $\\ell_\\infty$ estimation of the means of $n$ coins requires a blow-up of $n^2/\\rho^2$ samples. There is a (computationally inefficient) approach by [Karbasi, Velegkas, Yang, Zhou '23] that shaves off  a factor of $n$, and was recently shown to be optimal [Hopkins, Impagliazzo, Kane, Liu, Ye '24]. Similar results hold for the $\\ell_2$ estimation.\n\nOverall, I believe that the paper studies a useful problem, the results are interesting, and the technical contribution is above the bar for NeurIPS.", "weaknesses": "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).\n\nI 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments! In the proof sketch we have focused on the sub-linear regime ($m \\leq n$). The dependence $1/(\\varepsilon^{2} \\rho^{2})$ is incurred to handle the super-learning regime ($m \\geq n/\\varepsilon^2$). We redirect the reviewer to the proof of Lemma 3.2 (Appendix A.1) for the analysis of this case. We will also add this dependence to the discussion in the main body.\n\nOur approach incurs a $\\log (1/\\delta)$ overhead in the sample complexity. In particular, for arbitrary error parameter $\\delta$, we may replace $m_0 \\gets \\log (1/\\rho)$ with $m_0 \\gets \\log(1/\\min(\\rho, \\delta)) = \\log(1/\\delta)$ (assuming $\\delta \\leq \\rho$). This guarantees that in the completeness and soundness regimes, the test statistic is sufficiently concentrated such that the random threshold will lie on the correct side of the empirical test statistic. Using our approach, this $\\log(1/\\delta)$ approach seems necessary, however, we do not know if this is tight. We hope to investigate in future work whether this dependence is necessary in general, or if better sample complexity (say $\\sqrt{\\log(1/\\delta)}$) is possible.", "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:

Meta-review: 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.
Decision: Accept (poster)