Testing with Non-identically Distributed Samples
Authors: Shivam Garg
Chirag Pabbaraju
Kirankumar Shiragur
Gregory Valiant
Venue: Accepted by TMLR ()

Abstract: We examine the extent to which sublinear-sample property testing and estimation applies to settings where samples are independently but not identically distributed. Specifically, we consider the following distributional property testing framework: Suppose there is a set of distributions over a discrete support of size $k$, $p_1, p_2,\ldots,p_T$, and we obtain $c$ independent draws from each distribution.  Suppose the goal is to learn or test a property of the average distribution, $p_{\mathrm{avg}}$.  This setup models a number of important practical settings where the individual distributions correspond to heterogeneous entities --- either individuals, chronologically distinct time periods, spatially separated data sources, etc.  From a learning standpoint, even with $c=1$ samples from each distribution, $\Theta(k/\varepsilon^2)$ samples are necessary and sufficient to learn $p_{\mathrm{avg}}$ to within error $\varepsilon$ in $\ell_1$ distance.  To test uniformity or identity --- distinguishing the case that $p_{\mathrm{avg}}$ is equal to some reference distribution, versus has $\ell_1$ distance at least $\varepsilon$ from the reference distribution, we show that a linear number of samples in $k$ is necessary given $c=1$ samples from each distribution.  In contrast, for $c \ge 2$, we recover the usual sublinear sample testing guarantees of the i.i.d. setting: we show that $O(\sqrt{k}/\varepsilon^2 + 1/\varepsilon^4)$ total samples are sufficient, matching the optimal sample complexity in the i.i.d. case in the regime where $\varepsilon \ge k^{-1/4}$. Additionally, we show that in the $c=2$ case, there is a constant $\rho > 0$ such that even in the linear regime with $\rho k$ samples, no tester that  considers the multiset of samples (ignoring which samples were drawn from the same $p_i$) can perform uniformity testing.  We further extend our techniques to the problem of testing ''closeness'' of two distributions: given $c=3$ independent draws from each of $p_1, p_2,\ldots,p_T$ and $q_1, q_2,\ldots,q_T$, one can distinguish the case that $p_{\mathrm{avg}}=q_{\mathrm{avg}}$ versus having $\ell_1$ distance at least $\varepsilon$ using $O(k^{2/3}/\varepsilon^{8/3})$ total samples, where $k$ is an upper bound on the support size, matching the optimal sample complexity of the i.i.d. setting up to the $\varepsilon$-dependence.

Published in Transactions on Machine Learning Research (11/2025)
Testing with Non-identically Distributed Samples
Shivam Garg
shévvam.garrg55@mmai... com
Microsoft Research
Chirag Pabbaraju Stanford University
cpabbara@stanfordd edu
Kirankumar Shiragur
kshörugur Sattrnguur@mmiirossf.f..ccom
Microsoft Research
Gregory Valiant
gralian(Sstanforde edu
Stanford University
Reviewed on OpenReview: https: openreview. net/ forum? id= FU2uztzB1
Abstract
We examine the extent to which sublincar-sand sammle property testing and estimation apply to seltings where samples independently but identically distributed. Specifically, we consider the following distributional property testing framework: Suppose there is set of distributions over a discrete support of size k, Pr, ....... Pr. and we obtain independent draws from each distribution. Suppose the goal is to learn or test property of the average distribution, Pavg- This setup models a number of important practical set tings where the individual distributions correspond to heterogeneous entities either individuals, chronologically distinct time periods, spatially separated data sources, etc. From learning standpoint, even with e samples from each distribution, (kk/=²) samples are necessary and sufficient to learn Pavg to within error in & distance. To test uniformity identity distinguishing the case that Pavg is equal to some reference distribution, versus has & distance at least ε from the reference distribution, we show that linear mumber of samples in k is necessary given = samples from each distribution. In contrast, for 2 2, we recover the usual sublincar sample testing guarantees of the i.i.d. setting: we show that O(VK/e2 + 1/E*) total samples are sufficient, matching the optimal sample complexity in the i..d. case the regime where E 2 k 11/4 Additionally, there is constant p 0 such that even in the lincar regime with pk samples, no tester that considers the multiset of samples (ignoring which samples were drawn from the same P,) can perform uniformity testing. We further extend our techniques to the problem of testing "closeness" of two distributions: given c = independent draws from each of P1, P2...., Pr and qn, . 4r, one can distinguish the case that Pavg = 4avg versus having & distance at least using O(k2/3 /c3/3) total samples, where A is upper bound on the support size, matching the optimal sample complexity of the i.i.d. setting up to the e-dependence.
show that in the
case,
1 Introduction
The problem of estimating statistics of an unknown distribution, determining whether the distribution in question possesses a property of interest has been studied by the Statistics community for well over a century. Interest in these problems from the TCS community was sparked by the seminal paper of Goldreich (Goldreich Ron, 2000), demonstrating the surprising result that such tasks might be accomplished given a sample size that scales sublinearly with the support of the underlying distribution. Over the subscquent 20+ years, the lay of the land of sublinear sample property testing and estimation has largely been worked out: for number of natural properties of distributions (or pairs of distributions), testing or estimation can be

---

Published in Transactions on Machine Learning Research (11/2025)
accomplished with sample size that is sublinear in the support size of the distributions in question, and in most settings, the optimal sample complexities are now known to constant subconstant factors.
More recently, these questions have been revisited with an eye towards relaxing the assumption that samples are drawn iid.. from the distribution in question. The majority of such departures focused on relaxing the independence assumption; this includes work from the robust statistics perspective where some portion of samples may be adversarially corrupted, as well as other models of dependent sampling.
In this work, we consider the implications of relaxing the more innocuous seemiing assumption of identical samples. Given samples drawn independently from a collection of distributions, PI.....PP7 Pr, there are a number of different questions one can ask, including estimating properties of how the various distributions are related. Here, however, we focus on the practically motivated question of lesting or estimating propert ies of the average distribution Pavg = 7 Ep, p, To what extent is sublinear sample testing or estimation still possible in this sctting, and do existing estimators suffice? Below, we describe several concrete practical settings that motivate these questions.
Example 1. The "Federated" " Setting: Consider the setting where there are a number of users/ individuals, each with a corresponding distribution (over online purchases, language, biometrics, etc.) and the gool is to test whether the average distribution is close to some reference. There might be significant heterogeneity between users, and the number of samples (i.e.; amount of data) collected from each user might be very modest, due to privacy, bandwidth, power considerations. Analogous settings arise when compiling training datasets for LLMs, as there is significant heterogeneity between documents, websites, or clusters of websites, and lightweight lools for lesling properlies of the average/ average/oggrregg /oggregale distribution are useful.
Example 2. Chronological Heterogeneily: Consider selling where samples are collected chronologically, and the underlying distribution varies over time. Consider wearable technology that periodically samples biometric statistics, or language spoken. The goal may be to test whether the averuge distribution is close to some reference (with the goal of providing an early worning of illness in the case of biometries, or for early detection of dementia in the case of sampling words spoken). Ideally, this test can be successfully accomplished with far less data than would be required to learn. There is significant heterogeneity across time but samples collected close logether can be regarded as being sampled from the same distribulion, Pt-
Example 3. Spatially Segregated Sampling: Consider a selling where the goal is to sample species (of animals, bacteria, etc.) and test whether the overall distribution is close a reference distribution. In mony such settings, the distribution of species has significant spatial variation - the distribution of soil bacteria in grassy spot is quite different from the distribution in dense forest, similarly, the distribution of wildlife observed by trail-cameras in national parks varies according to the location of the cameras. Again, the goal is to accomplish this statistical test with less data than would be required to learn the underlying average distribution.
In some of these motivating settings, one may assume some structure in how the various distributions relate to each other- for example in chronological settings, for most indicos i, P, is similar to P: Nevertheless, it is still worth understanding whether such assumptions must be leveraged. Indeed, for learning the average distribution Pavg to within total variation distance E, the sample complexity is the same as in the i.i.d. case, Okks²) where k is the support size, without any assumptions on the p,s. At the highest level, our results demonstrate that as soon as one draws at least distributed setting recovers much of the power of sublinear-sample property testing. The caveat is that one must design new algorithms for this setting that are cognizant of which distribution each sample was drawn from; as we show, testers that return a function of the multiset of examples do not suffice.
2 samples from each distribution, this non-identically
1.1 Summary of Results
First, we establish that in the case that we draw c= samples from each distribution Pi...., Prr,...Pry Pry one con learn the average distribution with the same sample complexity as in the i.i.d. setting. Despite this, with c c= I sample from each distribution, sublinear-sample uniformity or identity testing is impossible:
Claim 1.1 (Learning the distribution, proof in Appendix A). Given access to T distributions, PI...., Pr. each supported on a common domain of size S k, for any O, given e = samples drawn from each.
2

---

Published in Transactions on Machine Learning Research (11/2025)
Ps. one can output distribution Pavg such that with probability at leost 2/3, drv (Pavg: Pavg) S E, provided Pr Pang for such
T = Okk/s)). Furthermore, Q(k//=)) samples are necessary, even is Pi guarantee.
Claim 1.2 (Impossibilityy result with c= proof in Appendix B). Given access to T S 2//2 distributions, PL...., Pr, and c= 1 sample drawn from each distribution, tester can distinguish the that the average distribulion, Pavg: is the usiform distribution of support k, versus has total varialion dislance at least 1/4 from Uk), with probability of success greater than 2/3.
The above impossibility of sublincar-sample testing in the case of c= sample from each distribution follows from the following simple construction, which also provides intuition behind the positive results for e < 2 Consider the instance where T = k/2, and each p, is a point mass on a distinct element, versus the instance where each P, is a uniform distribution over two distinet domain elements that are disjoint from the supports of Pj for j * i. In both instances, given c 1 sample from each distribution, one will obscrve T = k/2 distinct elements each observed exactly once. Despite this, in the second instance, Pavg is uniform over support k, whereas in the former the average distribution has total variation distance 1/4 from Uni.
Our first main result is that with just c 2 samples from each distribution, we recover the full strength of sublinear sample uniformity (and identity) testing. The key intuition is that with two samples from each distribution, we can count both the collision statistics within distributions, as well as the collisions across distributions, and build an unbiased estimator for [|Pavgll:: We then leverage techniques from Diakonikolas et al. (2016) and adapt them to this setting of non-identical samples to bound the variance of our estimator to get the following sublinear sample complexity for uniformity testing.
Thcorem 1.3 (Uniformity testing, proof Scction 3). There is an absolute constant, a, such that given access to T distributions, P1...., Pr, each supported on common domain of size k, for any e > 0, provided T 2 22a(k//s a(Vk/=² + 1/E²) and given = samples drawn from each Ps, there cxists a testing algorithm that succeeds with probability 2/3 and distinguishes whether,
Pavg (nif(k)
versus
dTv Unif(k)) E
Note that when e 2 k-1/4 our sample complexity for uniformity testing simplifies to O(Vk/E?), which matches the optimal sample complexity for testing uniformity in the i.i.d. setting. Since the setting of non- identical samples is a generalization of the i.i.d. selting, the lower bound of D(Vk/e²) for testing uniformity in the i.i.d, setting also holds in our setting; hence we get optimal sample complexity in the regime where 2 1/44
Our results also hold for identity testing, through standard reduction techniques. In particular, we can adapt the reduction from identity testing to uniformity testing of Goldreich (2016) to our setting with non-identical distributions, yielding the following result on the reduction from an instance of identity testing to an instance of uniformity testing.
Lemma 1.4 (Identity to uniformity testing, proof in Section 4). Given an orbitrary reference distribution supported on < k elements, there crists a pair (Φy. Vyy that maps distributions and samples over [k] to distributions and sumples over [4k), and satisfies the following,
For a sequence of distributions 9..... gr such that avg(q).... 4r) = q, the map by satisfies,
avg(O, ... #g((r)) = Uni((4k:).
For two sequences of distributions pl.. pl...., p and pi .i.... pr. the map by satisfies,
avg( 2 ).t.)))
(ar(avv(4 21(p)))))))))
(p?
1 4 drv ..... pt) avg(p? ..... pf))
The above result combined with the result for uniformity testing, immediately yields the following result for identity testing. Our bounds for identity testing are optimal in the worst case for large values of 2 1-141
3

---

Published in Transactions on Machine Learning Research (11/2025)
Corollary 1.5 (Identity testing). There is an absolute constant, a, such that given reference distribution q supported on S k elements and c = 2 samples from each of T distribulions, Pi..... Pr, there caists a lesting algorithm that succeeds with probability 2/3 and distinguishes whether,
Pavg =
versus
dTv(Pavg: 9) 2 e
provided 2 /
We note that our sublinear sample testing algorithms leverage the knowledge of which distribution each sample was drawn from. As the following theorem asserts, this is necessary there is a constant >> 0 such that even in the linear regime with ph samples, there is no testing algorithm that simply returns a function of the multiset of samples, throwing away the information about which samples were drawn from the same distributions.
Theorem 1.6 (Lower bound for "pooled" estimators, proof in Section 5). There is on absolute constant, p > O, such that given access to distributions Pi..... Ppk supported on a domain of size k, given = 2 samples from each of PI..... Pok. tester that returns a function of the multiset of samples (i.e., ignoring the information about which samples were drowm from the same distributions) can distinguish the cose.
Pavg = -k)
versus
dr Unif(k)) 2 0.01
with success probability at least 2/3.
Our positive results, and the intuition behind the uniformity testing algorithm also naturally extend to testing properties of pairs of distributions. In particular, we consider the "closeness" testing problem in this non-i.i.d. setting: given two sequences of distributions supported
set of size k, P1..... Pr and q....., 9r and e ii.d. draws from each of the distributions, how many total samples are required to distinguish between Pave = avvx versus drv drv (Pavg: gavg) > s? In this setting, we show that, given c= 3 samples from each distribution, we recover the optimal sample complexity of O from the i.i.d. setting, up to the dependence (Batu et al., 2013; Chan et al., 2014). While our proof leverages = 3 samples to simplify some of the analysis, we strongly believe that an identical result holds for = 2 examples from each distribution.
Theorem 1.7 (Closeness lesting, proof in Appendix G). There is an absolule conslanl, a, such that for two sequences of distributions, supported on common domain of size k, Pı...., Pr, and ......, qr, given c = 3 samples from each of the distributions, there crists a testing algorithm that succeeds with probability 2/3 and dästinguishes whether
Pavg = lavg versus drv (Pavg: lovg) 2 E,
provided 2 a(k2/3/68/3)
Finally, we note that the interesting phase shift between e == and e >> 1 holds only the non-Poisson setting. Results in the Poisson setting remain the same as that of the i.id. setting. In particular, if instead of samples, are given Poi(c) samples from each distribution, then even in the case of c = 1, we recover all testing results known in the i..d. setting. This follows from the following basic fact: receiving Poi(c) samples from every distribution is equivalent in distribution to receiving Poi(cT) samples from the average distribution. A more formal version of this result is stated in Appendix C for identity testing, but such a result also holds for testing other properties. To see how this bypasses the obstruction discussed in Claim 1.2, note that with Poi(1) samples per distribution, the point-mass case, each distribution yields repeated draws of its single element, whereas when the distributions have support on two distinct elements, within-group collisions start to occur.
Proving our upper bounds mostly involves adapting the techniques from the ii.d. case to our setting, Establishing the lower bound for pooled samples is more complex, involving a new construction that might be of independent interest. Nonetheless, more than the techniques, our main contribution is the problem definition and conceptual takeaways. Commonly, when collecting samples, heterogeneity invariably arises, particularly when these samples are gathered over various time points, geographical locations, or from different. users, as highlighted in the examples above. Thus, it is natural to ask whether sublinear sample testers are robust to such departures from the i.i.d. setting. We demonstrate that while existing testers are not.
4

---

Published in Transactions on Machine Learning Research (11/2025)
directly applicable (as evidenced by our lower bound for pooled samples), they can be effectively adapted, provided one collects multiple samples per distribution and leverages the source information of samples. For example, for identity testing, standard estimator involves counting collisions,, treating all collisions similarly. In contrast, our modified estimator uses a weighted collision count, with weights varying based on whether collisions occur within samples from the same distribution or not.
1.2 Future Directions
There are many possible directions for future work. From a technical standpoint, a concrete goal to match the ii.d. s-dependence for uniformity and closeness. For uniformity, the gap comes from rariaine-reducing terms in the i.i.d. analysis that are not available when distributions differ (see Remark 5). For closeness, the current e-8/3 dependence comes from the classical collision analysis (Batu et al., 2013); matching the i.i.d. s 4/3 will likely require a new analysis beyond collisions (e.g., adapting the counts- bastd statistic of Chan et al. (2014) to the non-i.idd setting). It is not clear to us whether that optimal s-dependence is achievable here.
Another direction improving the number of samples per distribution. For closeness, we currently use c to keep the collision-based & estimate independent of the heavy/light estimation; with more careful reuse of the same samples and explicit dependency tracking, = 2 may suffice. For uniformity, we show that is impossible in the worst case; it is natural to ask for structural conditions under which = 1 becomes feasible. If all p3 equal Pavg, the i.idd guarantees apply; more generally, if each is sufficiently close to Pavg we expect i.i.d. rates to persist with a small additional failure probability. As a simple check, suppose each is within 8/T TV distance of Pavg. Then the joint distribution of the T samples is within TV distance S 8 of T i.i.d. samples from Pavg- Hence any optimal i.i.d. tester applies with an extra failure probability 5. It. would be interesting to study whether larger deviations beyond this naive bound can be tolerated.
Finally, beyond the specific problems addressed in this work, there are many obvious directions, including mapping the sample complexities for other natural property testing and estimation problems within the framework of non-identically distributed samples. Studying properties of the average distribution is a natural starting point, though other summary statistics of a collection of distributions are also worth considering. For example, in chronological settings, one might be interested in how certain properties vary over time, or predicting propertics of future distributions. More broadly, probing the robustness of sublincar sample testing from other perspectives may yield further surprises with practical implications.
2 Related Work
Interest from the theoretical compuler science community on distribution lesting, given i.i.d. sample access, was sparked by the problem of distinguishing whether an unknown probability distribution was the uniform distribution over support k versus has total variation distance at least E from this uniform distribution. The early work of Goldreich & Ron (2000) proposed collision-based estimator, demonstrating that testing this property could be accomplished given significantly fewer samples than would be required to learn the distribution in question. Since then, a line of work eventually pinned down the exact sample complexity of @(Vk/E?) - optimal to constant factors including the dependence on the probability of the tester failing (Paninski, 2008; Valiant & Valiant, 2017; Diakonikolas et al., 2014; 2016; 2017). For a comprehensive exposition of this line of work, we refer the reader to Chapters 2 and 3 in Canonne (2022).
A closely related problem to uniformity testing is testing identity, where the task is to determine if an unknown probability distribution, p, is equal to versus far from fixed reference distribution, q, given i.dd sample access (Batu et al., 2001). While "instancc-optimal" estimators - estimators that are optimal for every q are known (Valiant & Valiant, 2017), among reference distributtions supported on < k elements, the uniform distribution is the most difficult to test. Beyond this, building off Diakonikolas & Kane (2016), Goldreich (2016) gave a reduction from identity testing to uniformity testing, showing that any uniformity testing algorithm can be leveraged in a black-box fashion for identity testing. We leverage both the high-level design of the optimal uniformity testing algorithms, and this reduction.
5

---

Published in Transactions on Machine Learning Research (11/2025)
For the problem of "closeness" testing, the goal is still to distinguish p q from the case that these two distributions have distance at least e, though now q is not fixed reference distribution, and instead we are given samples from both distributions. In the i.i.d. sample setting, for distributions of support size k a sample complexity of O log k//33) was established in Batu et al. (2001; 2013), with the optimal sample complexity of (max()22))) /e (/33 22)) later pinned down in Chan et al. (2014).
Beyond uniformity, identity, and closeness testing, there is an enormous body of work on testing or estimating other distribution properties or properties of pairs of distributions. Broadly speaking, the optimal sample complexities for these tasks are now pinned down to constant factors, at least in the setting where one obtains i.i.d. samples
Beyond i.i.d. samples: The questions of learning, property test and estimation have also been considered in various settings that deviate from the idealized setting of samples drawn i.i.d. from a fixed distribution. These include works from the perspective of robust statistics, where some portion of the samples may be adversarially corrupted (see e-g-; Diakonikolas et. al. (2019); Diakonikolas & Kane (2019); Charikar et al. (2017), as well as the broad area of time-series analysis where observations are drawn from time-varying distributions (e.g., Chernoff & Zacks (1964); Kolar et al. (2010); Lampert (2015)).
Most similar to the present paper are works that explore learning and testing questions in various settings where there are a number of data sources, each providing a batch of samples. In Qiao & Valiant (2018) and the followup papers Jain & Orlitsky (2020); Chen et al. (2020), it is assumed that an unknown 1 fraction of data sources correspond identical distributions, each providing a batch of e ii.d. samples, and no assumptions are made about the samples in the remaining batches. The main results here are that increases, the batches can be leveraged for learning; specifically, the distribution of the 1 1 fraction can be learned to accuracy O(e/ve). The papers Tian et al. (2017); Vinayak el. al. (2019) explore the setting where batches of size are drawn iidd from collection of heterogeneous distributions, and the goal is to learn the multisct of distributions. The punchlinc here is that the multiset of distributions can be learned given asymptotically fewer draws from each distribution than would be necessary to learn them in isolation. While the focus in these works is on the setting where the distributions have support size 2 (i.e. the setting corresponds to flipping coins with heterogeneous probabilities), the results apply more broadly. The paper of Levi et al. (2013) considered the setting of a collection of T distributions over large support size, and explored the question of testing whether all distributions in the collection are the same, versus have significant variation. They considered two sampling models a "query" model where one can adaptively choose which distribution to draw a sample from, and a weaker model where each sample is drawn from a distribution selected uniformly at random from the T distributions. We note that in this latter model, testing properties of the average distribution trivially reduces to the i.i.d. setting. Later works by Diakonikolas & Kane (2016); Aliakbarpour et al. (2016) improve the results obtained by Levi et al. (2013). Finally, the paper by Aliakbarpour & Silwal (2019) considers the setting with a collection of distributions, and given one sample (in expectation) from each distribution, the task is to distinguish whether all the distributions are equal to a reference distribution, or all distributions are far from it. In contrast, our focus is on distinguishing whether the average distribution is equal to or far from a reference distribution. They also consider the case where we only have sample access to the reference distribution. General non-vacuon vacuous results are not possible in their setting given a single sample from each distribution. To bypass this, they impose a structural condition on the collection of distributions, We also face a similar issue and show that it can be bypassed in our setting by drawing multiple samples from each distribution.
3 Uniformity testing from non-identical samples
In this section, prove sample complexity results for uniformity testing in the setting of non-identical samples. Our tester for uniformity in the setting of non-identical samples is based on collisions and constructs an unbiased imator for IlPavlll: As IlPavgl1 equals E when Pavg is uniform and is larger than (1 (1++²) when Pavg is e-far from uniform, we use this separation to solve the testing problem. The main part of the proof constitutes bounding the variance of the estimator that we construct in order to show that it concentrates around its mean. We adapt the proof from Diakonikolas et al. (2016) to the setting of non-identical samples to bound the variance of our estimator.
6

---

Published in Transactions on Machine Learning Research (11/2025)
To test uniformity, build unbiased estimator for IPavyll:- In the following, provide description of this estimator. For each / E (7), let (Xx(1) Xx(2)) denote the 2 i.idd. samples drawn from the distribution Pt- For each E [2', we define,
Y = (1) = X2(2)) and Ysr (1) X.(1))
Note that E[Y.] = 1p,11 and [[ = (p). P.) for all 8, E [7]. Using these random variables, we define an estimator Z as follows,
7
Y
Evs)
T
:E(T)
Z is an unbiased estimator of Pavgll.. In the lollowing we formally state this result and bound the variance of the estimator.
Lemma 4. The estimator Z defined in Equation (1) satisfies the following:
48 T
B|Z| Pavell2 and Var[Z] S 7
Pavg
12
Pave
Proof of Lemma 4. The expectation of the random variable Z is given by
1
Ip,
l + (p.. ||Pavg
T
LET
Therefore is an unbiasod estimator for llPavg this estimator Z.
l1.. In the remainder of the proof, we bound the variance of
Var[Z] = (Z-B(Z)) T
Σ AE(T)
(Yr ([y))(Y))
EYs. E(y I.
sct
Define
c, Y, -E and V., = Yst -E(Yat]
and note that E[ = 0 and E|G.d = 0. Rewriting the variance Z terms of these now random variables we get the following,
Var[Z]
1
E
Y, +
Σ
st 0
2
(
Σ
81)
+ Σ Yac) I
74
[E[T]
e<t
[E[T]
<<t
E T
8.) 2
4 (E )))
(2)
AE(T]
In the second inequality, we used (a + 6)² < 2(a² + b2). In the final inequality, we used the linearity of expectation. To bound the variance Z, we bound the terms in the final expression separately. We start with the first term.
Σ (E(T)
=E -E
1.)
8 +2
> Y.y EE.
Σ
E|Ý?1 + Σ EEY Σ E|Y?3
(E(T]
rE[T]
TE[T]
(E| E[rd?)
<
E|y? = Σ
E|y =
(3)
EE[T]
:E(T]
1E
In the first equality, we expanded the expression. In the second equality, we used the fact that the random variables Y,, Y, are independent for all s, E [T] and * In the third equality, we used E| for all E (T). The fourth and fifth inequalities are immediate. The sixth equality follows because Y, is an indicator
7

---

Published in Transactions on Machine Learning Research (11/2025)
random variable. In the seventh inequality, substituted the value of E[Y;] /|p/112. Similar to the above, now bound the second term of Equation (2).
E Σ Ys 8<8
) E
)
Yss
E
Σ e<2
ot
2
+
Σ
Y Yabl +
E
Σ
P[VseVand
E
(4)
ect
acc
ach (a.ta.bb11=4
(a.t.o,b)
33
terms
termns
terms
The first term above is equal to (P P.) - we can club this together with the summands in the summation in the last term that are of the form E[Y,,]². For the third term, observe that if the indices 8, L, a, are all distinct, the random variables Yst and Yas are independent, and hence B Yas) = B[ [Yass) But all these summands are also included in the summation in the last term, and hence will get canceled out. Finally, are left with the second term Observe that for any fixed distinct values, there are 6 possible orderings of the indices 8 < f and < such that the multiset. (s,1,0, a, bj has exactly these distinct values. Further, for each of these orderings, the random variable Y,, Yab is non-zero if and only if the first sample at the three distinct indices is the same. Thus, we have that,
=6 Σ Σ pa(0po(0)p())== = 6 Σ Pa.
(5)
a<b<e t=1
a<bee
[(st00))1=3
Putting the above together with the remaining terms corresponding to |(,, a, byl in the last summation, get
[ Yor
2 Σ
Pr. (p. Pp. Pa)(1 (P).P.) +6 Σ (Pa.Ps. Ps. Ps.
E
SCt
actice
Σ
(Pa Po) Po) Po) + Pa + (Pa Pa) (P).
(6)
a<b<<
(P.. + 6
Σ (Pa Pb. Pa)
(7)
<<(
a<bic
$ Po P.) +
P
s<t
LE[T]
Substituting the above inequality, along with Equation the variance of Z,
(3) into Equation (2), get the following bound for
Var 7
<
2
||,
11
+
(P:s P.) + +44
Σ Pt
7
8<8
AE(TT]
4
2
48
3
2
48
3
<
T
P
2
T4
P
3
T
P
aavk
2
+
T
Pavk
3
(8)
LE|T
KELT
We can now use the variance bound from the above lemma along with Chebyshev's inequality prove Theorem 1.3,
Proof of Theorem 1.3. We divide the proof into two cases.
8

---

Published in Transactions on Machine Learning Research (11/2025)
Uniform case: In this case, we are promised that the Pavg ug- Therefore, it is immediate that | Pavg I and I|Pavgll E which further gives us that,
9422 Var
Pr 7 2 (1
3 k = Pr
22 2
1
+
Var [2]
3
e
e
ex
9k2
4
48
36k
432
+
T
TK2
E77
Tea
In the first inequality, we used that E = 1/k: In the second inequality, we used the Chebyshev's inequality, In the third and fourth incquality, we substituted the values of E[Z] and Var[Z] [Z] respectively; to upper bound the variance we used bounds from Equation (8). In the final inequality, we simplified the expression. Note
that when T> 2600 the second term above is smaller than 1/6, and for T>
216/E the first term is smaller c²
than 1/6. Therefore, we have that, for T= max 2600 216// = O max
VB 2
8² 11 k
Pr z 2 1
1/3
Therefore, Z is smaller than (1 + +2/3)) with probability at least 2/3 in the uniform case, that is, when Pavg = Ug.
Far from uniform case: In this case, we are promised that, llPave - uzlli 2 e, which further implies
E|Z] = Pavgll =
L+o 2 +(( (1+++* =), where a² def
= kl|p kllpavg
Us 1 2 s². In the following, we upper bound the
&
probability that Z takes a value smaller than (1 + +2/333)
Pr 2 s
1
3 Pr
H
2 5
1 + 3
1 + a
Pr <
1 + 3
B|Z]
1
+ a²
h
1 a²
Pr 2 2 (1
a²
22
E[Z]
< Pr 2 < (1
a² a²
3
E[2]
1 a²
1 a²
2a²
5 9(1 + a 2²)2
Pr Z < 11
E E[2]
Varl
3(1 + a²)
4ax 2
9(1 o²)²
9(1
a²)²
108(1 02)²
Pavg
Var[Z]
40 4 Pavgl1
T2a P Pavgle 1
Ta
Pavg
9k(1 + a2)
108A
T204
To
P
(9)
In the first equality, we multiplied and divided by the term (1 + a?). In the second equality, we used the 1 definition of a. In the third equality, we used I+o² = 1 - 2²-5. In the fourth inequality, we used a² 2 g²
and in the fifth equality, we simplified the expression. In the sixth incquality, we used Chebyshev's incquality.
In the seventh and eighth incquality, we used E[Z] = Il 1B and substituted the bound on the variance of Z from Equation (8). In the final expression, we used the definition of a. To upper bound the above probability term, we next bound each of the terms in the final expression separately. The first term above bounded by,
9h(1 + a²) 9k(1 9h(1+ T S
18k T2g
(10)
T2g4
In the first inequality, we used the fact that for x > 0, the function 1t is decreasing in x and also a² 2 s². The final inequality follows because & S 1. To upper bound the second term in Equation (9), we first note that,
| 113 = =11paag - us + un Σ ((P (1) (x)( + ug (1))
9

---

Published in Transactions on Machine Learning Research (11/2025)
PavR (8) - [k)) + u1)² + 3(P (avv(() (i) - (1) us (1) Pavz (i)
3
1
3
Pavg
u&ll3
|13
k2
k
Pavg
(1)²
k
Pavg
u
13
122
K
Pavs
u
i=1
3
3a
1
< P
us
112
Pavg
P
1
1
k2
1
The first five equalities follow from simple algebraic manipulation. The sixth inequality holds because |l lla s ll ll2. In the final equality, we used the definition of a. Thus, the second term is bounded as,
108k
PAVE || - Ta
108k2
a
3a
108V
324
108
+
To
/-3/2
k2
122
To
Ta
Ta4
108 Vk
324
108
(11)
Te
Te²
Te4
In the final inequality, used 2 E. Substituting Equation (10) and Equation (11) in Equation (9), we get the following bound on the probability,
Pr = (1
c² ))
18K
108
324
108
18h
432V
108
I
3
T2g
Ts
T=a
Tet
g
T=²
T=4
618 Note that for T > 2600 the sum of the first two terms is smaller than 1/6, and for T 2 gd is smaller than 1/6. Thus, we have that for T 0( max (2A4 ++))
the last term
}
Pr 6 S 1+ 3 T. S 1/3.
Therefore, Z is larger than (1 + =33))/3 with probability at least 2/3 in the far from uniform case, that is + +
when Pavx uell lI 2 e. In conclusion, for T = 0 vI Pavg = ug from ||aagg usll1 2 E, for any > O. We conclude the proof.
we can test uniformity, that is we can separate
Remark 5 (Optimal sample complexity). We can compare the bound on the variance in Equation (8) to the similar bound in the tight analysis (e.g., Equation (2.9), Theorem 2.1 in Canonne (2022)) of the standard i.i.d setting. would appear that we are missing a term of the form -+ PPvy 1 which helps reduce the variance. In fact, if we had a term of this form, we would be able to shed the O(1/E*) factor obtain the optimal sample complerity of O(Vk/e?) even in the non-i.idd setting. The main hurdle in the analysis above for gelting this crucial variance-reduucing term can be seen in Equation (6). In the i.i.d selling with one distribution the terms of the form (Par Po) (Pa. Pa) are all the same and equal || (which is at least A ). But in our setting, these terms can even be (if Pa: Phs Pe have disjoint supports), and hence, we cannot conveniently lower bound the contribution of these terms in reducing the variance. That is why, for lack of better bound, we had to drop all these (6()) many!) terms in going from Equation (6) to Equation (7), which ultimately results in the stated sample complexity.
4 Identity testing from non-identical samples
We now prove our result which reduces the problem of identity testing to uniformity testing. Such reduction for the i.i.d. setting is already known (Goldreich, 2016) (see also (Canonne, 2022, Section 2.2.3)), and we adapt the same reduction for the setting of non-identical samples. In particular, we use the same reduction functions from that of the i.i.d case and show that they work even in the case of a sequence of changing distributions. A more formal statement of this reduction, along with its proof for a sequence of distributions is provided below.
10

---

Published in Transactions on Machine Learning Research (11/2025)
Lemma 1.4. Given arbitrary reference distribution q supported on S k elements, there evists pair ( q. vg) that maps distribulions and samples over [K] to distributions and samples over [4k]], and solisfies the following,
For a sequence of distributions .....,, dr such that avg( av.., ,,....,rr) = the map D satisfies, urg(Do(qn).) ....... 2g(or)) = Unif(4k).
-For lwo sequences of distributions ph...., p and př.... p the may by salissies,
o (P))) avg (pi). (r(()))) 2 1
_ drv(avg(p',.. ..... pT) ,..(((...,,p)))
Proof. We divide the definition of our maps ( p) into three parts:
def Φ о +
2 $
q
V def W vr 4
We first define the map &. which we divide into three parts b 42 and dy The map D2 D. A is defined follows,
(p) 2D+ Unif(k).
Let k' 4k and r r= (q(()) 1 1 Uk). The map 03 As + De+1 is defined as follows,
[K(())) Mr(())
p(i)
for all i E [k]
(1) = 11 ΣjE(H) Wr())
(12)
[k((())
p() for k ++.
Let == 22 (r) (q)) and define k; = k s(i) for E [K + 1]. Let Si,..., Sa+1 be any partition of [k' such that |S| = k; for all E [k + 1]. Then the map Ø2 A&+1 + As is defined as follows,
p
& (p) = V
Σ
1 (i))))
JE[K+1]
Using these definitions, we now prove the two claims stated in the theorem.
Claim 1: For any E [T], let,
I2 = (g 31 (2(x)) and 2, [y(c))
In the following, we show that,
avg( 1114 = avg(21,.....
=1
We prove the above statement entry-wisc and we consider ith entry of the average distribution. We divide the proof into two cases. Let i be such that i Sj for some E [k), then note that,
(rg(2((9)) (q.).... o ( (1))
1 T
Σ
(1)
1
Σ LE|T
Σ
ve((")
1(i S5),
T
s('))
EE(T)
J'E|++1]
vr( 1
(r(i)
xx(i)
FrG)
TW
s())
Tk
s(j)
1E|T
1E/T]
[k(r))]
z xe(i)
Σ
KrO
Σ
Tk
TR
r())
EE|T
EE[T]
11

---

Published in Transactions on Machine Learning Research (11/2025)
2q.(1 + + ())
TW
r())
[E[T]
(q()) } Unif(
T
Tk
r())
k
In the second equality, we substituted the value = = In the third equality, we used the assumption that i E Sj. In the fourth and fifth inequality, we substituted the values of yt and 8 respectively. We simplified the expression in the sixth equality and substituted the value of it in the seventh equality. In the eighth equality, we used the definition of q = avg(q...... .7). In the final equality, we used the dcfinition of r.
Let E S then note that,
= (g(( 1)
1 T
Σ
(1)
Σ
Σ
Be(i) 1(1 E Sy),
T
s(i))
TE
j'E[k+1]
ΣjE( [Kr(1)] xx(())
V/
Fr
TF
s(A + 1)
Tk
s(k + 1)
EE(T]
:E(T]
1
Σ
1 Σ
[Kr()))
=2(0)) ) Wr(()
TV' s(k +1)
rE(T]
jE(M
1
1
T
Σ
ze(i)
Tk' s(k + 1)
kr((i)
T
JEIN
LE[T]
1
[r(U
(a6)) + [Umi(()()))
1
1-
1. s(k:
+
kr())
jEL
1
1- Σ
|r(Ui k'
s(k 1)
W s(k +1)
k' s(k +1)
jEl
1
K'
In the second equality, we substituted the value x, = + (w:). In the third equality, we used the assumption that e Sk+1- In the fourth equality, we substituted the values of yr and simplified the expression in the fifth and sixth equality. In the seventh equality, substituted the value of x and used the definition of q ... Qr). In the eighth and ninth equality, we used the definition of and respectively.
Combining the above two derivations, we have that, for all i i [k + 1].
1
avg(dg ...,..... (q))))) K'' 4h
Therefore,
usk
Claim 2: For any t E [T], let,
xt = 03 v/ = (2 and 25 =2((1)) for a E {1,2).
In the remainder of the proof, we show that
drv(avg(2)..... =t), avg(=?..... ... = drv(avg(@(p)).... +(pt)) avg(o(?))....
12

---

Published in Transactions on Machine Learning Research (11/2025)
drv(avg(p).... ... ..t.......,,).aaa.. avg(() ... ....))
4
It is immediate that, (rv(av((2)........ 2)) ,7,
21.) = dTv(avg(u)........ avv.. ..))
Furthermore, note that for E [k]]
.v. T Σ
Kr(D]] kr(1)
=1(()
[Kr((i]]
( (2Pav + 1 Unir
wr(()
and,
[Kr())]
avg(v)....., + = T Σ
xx((i)
kr(j)
JEIA]
=1 Σ
[Kr(1))
(2Pávg(5) (Pagg(i) + (n)())
1
1
kr((i)
JE
In the following we bound drv(avg(y) drv(avg(<)).... 24)), avg(=?, 2
..). ,.,)).,,)))), which in turn bounds the quantity
dTv ... vt), avgly)...................... v2t))
[T((1]]
1
[Kr()]] 1 1 Unif()))))
Σ
( avg (i) + (nif(k)(
( Pav (i)
kir(1)
kr(()
ic[k]
[r(())] 1
( P Pavg (1) + 3 Unif(k)
k'r(j)
Je(k]
[kr(i)) 1
( Pa (1) + (UMI((A)O))
1-
kr(())
JE(A)
[Kr(i)]
[kr(i)) 1
1 (i) Pivg(ti)
(i)
+ Σ
kr((j) 2 Pavg (i) - Phvy (i)
k'r(1)
2
SE
JE
[Kr(i)] k'r(i)
|Piv (i) Payg
(i)
Pavg (1) -P (1)
2
AE|R]
In the first equality, we substituted the values of avg(s f4) for a E {1,2} that were computed carlier. In the second and third equality, we simplified the expression. The last inequality follows because r(i) 2 2k k'r(i) 2 2 and [Kr(i)] 2 kr((i) Putting all together, we have that,
drv (avg (pp)).).....(())) (vg()(p)),.... ((p))
1
drv(avg(p).. ..........ppp........ avg(pi .w..pp......ppp arg
4
and we conclude the proof for this case.
Sampling:
In the remainder of the proof, we state the maps v v2 v which help us generate the samples from the mapped distributions. The definitions of these sampling maps are pretty straightforward and we state them below to conclude the proof.
33 Given i E [k], return i with probability 1/2 and a uniformly random element of [k] otherwise.
T2 Given E [k], return i with probability
[Kr(]]] and l + otherwise. Wr())
T1 Given E [k 1), return uniformly random element from St-
q
13

---

Published in Transactions on Machine Learning Research (11/2025)
5 Lower bound for pooling-based estimators
In this section, we prove the indistinguishabiiity result for pooling- based estimators given in Theorem 1.6. First, we observe that uniformity of the average distribution is symmetric property, and thus, labels of the samples do not matter for testing algorithm. Thus, without loss of generality, the testing algorithm takes input the pooled multiset of samples and operates only on the fingerprint of the pooled multiset (refer to Appendix E for formal discussion on this). Here, the fingerprint is the count of elements that occur exactly zero times, once, twice etc. In what follows, we will construct two sequences of distributions: one whose average is the uniform distribution and another whose average is lar from uniform. However, we show that the total varialion distance between the distributions of their corresponding fingerprints is small, implying impossibility of uniformity testing with pooled samples. Below, describe the key proof steps:
can assume that
Step 1: We construct two sequences of distributions a and b (Definition 8) such that avg(a) is uniform and avg(b) is far from uniform (Claim 5.1). Moreover, these sequences are chosen in such a way that when we draw 2 samples from each distribution in the sequence, no element can be observed more than 4 times in the pooled multisct. The building blocks nceded for defining these sequences of distributions are introduced in Lemma 6.
Step 2: Next, we show that when we draw 2 samples from each distribution in the sequences, the fingerprints of the pooled multisets have the same mean (Claim 5.2), and similar covariances (Claim 5.3). A minor detail here is that we show this for the collision counts instead of fingerprints, but this is not an issue, as one can use an invertible linear transform to relate the two (Appendix D).
Step& 3: We want to eventually show that the distributions of fingerprints are close, and hence cannot be distinguished. For this, we will first show that the distributions of these fingerprints are close, in total variation distance, to the multivariate Gaussian distributions G. and Gb of corresponding mean and covariance, that have been discretized by rounding all probability mass to the nearest point in the integer lattice (Lemma 11). We show this via a CLT (Lemma 10). One slight complication in proving this CLT is that in our setting, the fingerprints no longer correspond to a generalized multinomial distribution, and hence we cannot directly leverage multivariate CLTs for such distributions (e-g., Valiant & Valiant (2011))- Instead, we will show that the distribution of fingerprints is represented as sum of independent samples, supported on the all-zero vector, the basis vectors, and the vector [2, 0,0,0,,... ... Our proof essentially "splits" each distribution into the component supported on the zero vector and the basis vectors, and a component supported on the zero vector and the 0,0. vector. The portion supported on the basis vectors is a generalized multinomial, and hence is close to the corresponding discretized Gaussian by the CLT in Valiant & Valiant (2011), and the remainiin portion is simply a binomial, scaled by a factor of 2. We then argue that the convolution of these distributions is close to discretized Gaussian.
Step 4: Having shown that the distributions of fingerprints are close to corresponding discretized multivariate Gaussian distributions, we are left with the tractable task of showing that the TV distance between these two (discretized) Gaussians is small. This is shown in Lemma 12 and relies on certain technical results proved in Lemma 16 and Lemma 17. Here, we use the fact that the two collision-count distributions have the same mcan and similar covariances as discussed in Step above. Finally, triangle inequality yields the desired result (Lemma 13).
We now proceed towards the proof details of the above steps. We start by defining some distributions which are the building blocks for our hard instance. We will tile up these distributions over disjoint supports to form the overall hard instance
Lemma 6 (Building block). There exist distributions Pte P2, a1 42 T1, T2, 81, 82, each supported on m elements, satisfying the following:
(1) avg(P P2) = avg(ri, r2) (ni.(m).
14

---

Published in Transactions on Machine Learning Research (11/2025)
(2) (av P2), avg(a,, 92)) 2 16v2
and
drv(avg ri, T2), $1, 82)) 2 16v2
1
(3) Let FP(p)= [FP(1)2, FP(()s, FP())a] be the random variable represenling the luple of counts of elements observed enactly 2 times, 9 times and 4 times respectivcly, when we draw c= 2 samples i.idd each from P1 and P2 (i.e. we obtain total 4 samples). Note that FP(p) is supported on Furthermore, let Cp (2 cg. eg'l be the 3-dimensional vector of 2-way, 3-way and 4-way collisions observed when we draw 2 samples i.i.d each from P1 and p2- Similarly define Cg. Cr. C.. There crists an a E (0,
[0. 00,0,00 0) [1,0, 0]. [0, 1, 0]. [0,0, [2.0.0]. Similarty, define (Q) FP(),
such that,
BlaCp+ + (1-a)C,) = - a)C)). ElaFP(p)) (1- = =BlaPP(g) + + (1- (1-a)
Proof. First, we describe the distributions Pt, P2, rI, r2. Let P1 - P2 E Am be the uniform distribution on m elements. Let rı E Am be such that it assigns mass 2 each on the first elements of [m]. Let r2 Am be such that it assigns mass 2 cach on the last m 2 clements of (m]. This is illustrated more clearly in Figure la. It is clear that avg(P1, P2) = avg(r1, r2) = Uni,(m), and hence part (1) of the lemma holds.
m
Next, we describe the distributions q1 S1. Set e v2 each on the first elements, and mass I-E each on the remaining 2 m
1 Let q1 E Am be such that qı has a mass 1te m elements. Next, consider q2 E Am
defined as follows: Of the first m elements, 92 has mass 1= each on the first 7 fraction, and a mass Ite m each on the remaining g fraction. Similarly, of the latter 7 elements, 9 has mass Itc each on the first. th
7th fraction, and mass 1-s each on the remaining 1 th fraction. Further, set s qı and s = 92- This 8
m is illustrated more clearly in Figure 1b.
We can readily see that [|avg(P, P2) v part (2) of the lemma holds.
= ||avg(ri, r2) - A g. Recalling that
Now, we prove the last part. Fix 8 = J. Let cg, cg. et denote the number of 2away, 3-way and 4- 4-way collisions respectively when we draw 2 samples from qı and 2 samples from q2-
11 27
11+5
2
2
m
2
m
1 ++
1 - E
(1
3)m
[1+s]
2
1--
11
+ 4
8m
+
m
m
m
m
2m
Elcg] 4
(1
3)m
+ 8
+
-
3
2
m
m
2
8m
1 ++
--E
1 ++E
1 1-6
3
m
m
m
m
m²
Elcq|
(1 - p)
1+E
+
1 -
+ 3m
1
1
-
5
3
2
m
m
m
m
4m
Since q1 81 and q2 $2, for any E (0, 1),
Tacy + (1 a)
11/2m
E
E
E
ac + (1 a)
3/m²
(13)
ac + (1 o)
3/4m3
I mm-wa collisions also formally defined in Appendix D.
15

---

Published in Transactions on Machine Learning Research (11/2025)
Pi Pa
7R
701
2
Fi
4 5g
17
77
avg(g 9t 9u) avg(s), #g)
avg(pr.P.) Pa) avg(ri.
1
(a) Average is uniform
(b) Average far from uniform Figure 1: Building block for the hard instance defined in Definition 8.
Now, set a = 3 and P2. If we observe tails, we will draw two samples each from rı and r2. We can calculate the expected number of 2/3/4-way collisions in the samples obtained via this process.
4. Say we toss a coin with bias a. If we observe heads, we will draw two samples each from P
2 2 +
2a +
11
Elach + (1 -1- a1-a) = a
+ (1 -a)
a)
2
2m
4a 3
Baac + - (1-o))
m
m
3
Elacf + (1 a)/]]
m 4m
These are precisely the expressions for the expectations in Equation (13). Finally, the collision counts are related linearly to the fingerprint (Lemma 14), and this completes the proof of the part (3).
Remark 7. Note that as we draw only 4 samples from the building block given above, the number of elements that occur exactly zero times and exactly once are a deterministic function of the number of elements that occur exactly 2,3 and & times. Furthermore, since we will tile up the above instance over disjoint supports of m elements, no element will ever occur more than 4 times. Thus, restrict our attention only to the fingerprint of elements appearing 2,3 and & times.
Now, we propose sequences of distributions = (ai, ar) and b (b.,... br) such that avg(a) is uniform and avg(b) is far from uniform.
Definition 8. Divide the support [k] into n disjoint blocks, each of size m, so that = mn. Each block corresponds the support of 2 distributions in sequence, so that the total number of distributions 2n. Assume that is large enough and m is a large constant independent of k. being large enough and being constant ensures that T +kk) is also large enough.
16

---

Published in Transactions on Machine Learning Research (11/2025)
First, we specify each block in the first on many blocks (where a = and n will be some multiple of 4) fir the 2th such block of size m, where 1 S i is on. Let Pi, P2, n. o correspond to distribulions Pt:P2: Ii 92 respectively (as defined in Lemma 6), supported on this block. For the first distribution supported on this block, that is for t t= 2i - 1, we will set 02i-1 = pi, 1=-1199 qi. For the second distribution supported on this block, that is for = 2i, we will set a2 = p2, by = T2-
Now, we specify each block in the remaining (1 a')n many blocks fir the ith such block of size m, where an +1 Si S n. Let ry. r2, si sy correspond to distributions Tı, 22, 81, 82 respectively (as defined in Lemma 6), supported on this block. For the first distribution supported on this block, that is for t 2i 1, we will set 02i-1 ri. 1 = st. For the second distribution supported on this block, that is for t = 2i, we will set 02: = r2 b2: = 82
These sequences and b are the entry-point to Step 1 in the proof steps described above.
Claim 5.1. Let and b be the sequences constructed in Definition 8. avg(a) is uniform [R) [mn] and avg(b) is for from uniform with drv dTv(Unif(()), avg(b)) 16v2
Proof. Observe that from Lemma 6, in every block S i S n, avg(azi-1, a2x) Unif(m). Furthermore, since all blocks have disjoint supports of size m, we conclude that avg(a) = aaggai,...... a2n) ) Umn Un.
Also, from Lemma 6, in every block 1 s S n, ||avg(a2i-1, az;) avg( b2.)ll - This immediately L. Thus, drv(avg(a), avg(b)) = drv(Uni[(k),
-
8/2
gives us |lvg(a), a2.) - avg(bi, b2n) II
Sv2'
16v2
Next, we proceed to Step 2 in the outline above, which shows that the first two moments of the collision vectors are close.
Claim 5.2 (Means match). Let C. and C& be the 3-dimensional vectors of 2-way, 3-way and 4-way collisions observed for the sequences a and respectively over all the n blocks. Then,
E [Ca] = EC
Proof. Let Ca: be the 3-dimensional vector of 2-way, 3-way and 4-way collisions observed for a in the 5th block (i.e. samples each from a and az)). Similarly, define Cb. Then, the total number of 2-way, 3-way and 4-way collision across all blocks will be Eie(n) CaN and Eie(n Cb,- Now, recall that exactly on many blocks are of one kind, where each C.: = Cp (respectively, Cn, = Cg) independently, and the remaining (1 a)n many blocks are of the second kind, where each Ca. = Cr (respectively, Cb, = =Ca independently. Thus we have that
on
n
Ca:
E
Σ Ca, = nnBlaCC + (1-
EE m
i=ant
n(Eaaaa + (1- ca)
(from Lemma 6)
a
E
Co.
Σ
Cb.
= E
Σ EE ml
Cb,
i=ant1
Claim 5.3 (Covariances match approximately). Let Ca and Co be the 3-dimensional vectors of 2- 2-way, 3-way and 4-way collisions observed for the sequences and b respectively over all the n blocks. Then the covoriance matrices are as follows:
71/m
n2/m²
7a/m²² Y2a/ m3
0 Tan/m²
ana/m"
Σ [CC. =n
71/m²
722/m²
+
012/m3
a22/m33 m a222/
a23/m²
T/a/
Y/2 723/m² m
7/33 m3
013/m
0:23 0223/ m
0aa/m4
17

---

Published in Transactions on Machine Learning Research (11/2025)
71/m
T13/ ma/m² m 123/m²
/m/ mm
d dnp/m² m/3 d2a/m² m
d dza/ m agg f
E [[C]] = n
712/m
722/m²
n
[1a/m² 1
723/m²
733/m²)
d1a/m
with losyl. lolgb hay bounded by constants independent of m (for large enough).
Proof. As in Claim 5.2, we have that Ca === Ca, and cb= Cb. where Ca, is either Cp or Cr, and Cb, is either Cq or Cs. Further, since the samples in each block are independent, the covariances add up. Thus, we only need to compute the covariance in one block, which we recall supports two distributions and contributes samples. Suppressing subscripts for now, we have that
Eic²] E[c²] 1
E[e2c3] E|ey E[ca] E[e]] B |²
E Eloycı] E E
c1
[[[|
C3
E c2 E
E Neaccl Efcil
C E c4]
E E[e2ca]
E B/cl
B/cac4]
Eles E(ca]
E/c| 1
Let Yau be the indicator that the elements at indices a and & collide. Note that S a, b S 4, since we have samples in each block. Then,
E Ele
=
E
Σ Yub axch
ΣXI
Yij
isj
E
y2 ab
+ 6
Σ
Yahc +6
Σ YadYed
aab
a<cicc
asbresd
E
Y ab
+ +6. R
Σ Yobc
+ +6. 31)
Lacb
Lacbec
E(02]
+
6 Pr[first two samples collide] Pr[second two samples collide].
In similar manner, obtain the following expressions for the remaining terms:
E[ E [C[c]] + 12 E[(c]]
B[c]] [[(ca]
E E(e2ca] = 3 E[[c]] 12 [[[c]]
E|e2c1] = 6 E[c|]
E E[cac4] = 4 E[ca]-
Thus, we have expressed all the entries the covariance matrices terms of just the expected number of 2-way, 3-way and 4-way collisions. We have already computed explicit expressions for these for each of p, q, and in the proof of Lemma 6. Plugging these in, obtain
6
12
12
P
m
75
m-3
E[cp]
+
m
172
"1"
T
m
TVE
m
172
12222
[[C,]
0
0
33
2g
21g
2m
81g
E[G.] E[C,]
m
m
4
2mm
m
4mm
Smz
4m
16m
Finally, recall that
am
n Σ
ECC.]
Σ
Σ
Ca.
+
Cai amp a)nE(Ct]
Limont1
18

---

Published in Transactions on Machine Learning Research (11/2025)
on
[(Cb]
Σ Cb:
+ Σ
Σ
Cb:
= am + [x)
Lian++1
for = and hence, substituting the values above, we get
2yn 213"
3
2n3
E[aa] = 7
"
3
3
+
0
my3
3 m
12
"
2m
771
27
778
2g
2xg
4mp
2m
813
[[C]] = 7
"
2gg
9 172
2m
m
8m
16m
For the terms 9/m² - 12/m² and 9/m²² 9/m*, we can write them (9 /m) and 9-9/m respectively. Thus
for m large enough, we can write all the terms in the matrices in the form specified in the claim, completing the proof.
We now prove a CLT (Step 3) which helps us approximate the distributions of the fingerprints by multivariate Gaussians having the same mean and covariance.
Lemma Consider o-dimensiooal distribution (for e S 10) supported on [0,0..... .), the c-dimensional basis vectors, and 0.... 0], such that the masses the non-origin support points are fized positive constonts, ...,,
and the mass on origin [0, ...... is at least 1 - 10-16 Then for i large enough, the distribution of the sum of f i.i.d samples from this distribution has total variation distance at most 0.002 from the Gaussian with corresponding mean and covariance, whose mass has been discrelized to the nearest poinl in the inleger lallice.
Proof. Let ug = Pr([0.00 0, 0,....0)), and #n = Pr([1,0..... .0....,)))....... U2 = Pr([O, 1r.,,, O1,...,),,.......4 = Pr( O..... 1]) ........)) and v Pr([2, ....................... 0)). We draw a sample from this distribution as follows: first flip a fair coin, and if the coin lands heads, sample from the distribution over [0, 0,...... .......0 0] and the basis vectors, given by respective probabilities
Σ u; 2u, 2u2, ,u,- If the coin lands tails, we sample from the distribution over J0,0..... 0], [2, 0, .... with respective probability 1 - 2v, 2v. Note that this sampling procedure yields sample from the original distribution. Here, are using that v, Ei= it are both at most 10-16 for the probabilities to be well-defined.
Given É independent samples sampled from the distribution in this way, let us consider the distribution of the sum the samples, conditioned on exactly t of the e fair coins having landed heads. Note that for large E, with probability at least 0.999, E [e/2 4Ve, 2/2 4VE].
Thus for all / in this range, if we can show that the sum of E i.i.d. samples has TV distance at most from the desired discretized Gaussian, this would imply total variation distance of at most 0.001 + without conditioning on t. Thus we would focus on the distribution conditioned on t taking value in [e/2 4v22-4V2,44 4/2-4
Conditioned on a value of t, the distribution corresponds to the convolution of independent draws from the multinomial distribution given by the distribution corresponding to the coin landing heads, and the distribution corresponding the f-t samples from the distribution supported on [0, ........) and [2, 0. 0.......... 0), which is a binomial random variable in the first coordinate, scaled by factor of 2.
Let us first reason about the l independent draws from the multinomial distribution. Leveraging multivariate CLT, the distribution of the sum of the t draws from the multinomial will have total variation distance at
most O ()ogr))/5 2/3 from the multivariate Gaussian of corresponding mean and covariance, discretized to the g1/s
nearest point in the integer lattice ( (Valiant & Valiant, 2011, Theorem 4); see Section F.2 for restatement). Here, o² denotes the smallest eigenvalue of the covariance of the sum vector of the l draws which will be (()).
19

---

Published in Transactions on Machine Learning Research (11/2025)
To see this, observe that this sum vector has mean t. [2u1:-.. ................................ 2ull,., and covariance
2uy (1 2u1)
Auiuz
Auuug
4u Me
4u1u2
2uz(1 2wz)
Auzils
4u
t.
Ue the
Augzee
2uo(1 - 2uo)
The determinant of the matrix above, without the t scaling, is exactly
2u1 2u2
2ue- 1 2
U4
For constant e, and by the assumption that u, > for all i and Ei= U S 10-16, this determinant is a positive constant independent of f. This implies that the smallest eigenvalue of this (positive semidefinite) matrix is at least (and at most) a positive constant. Together with the scaling of t, we get that o² Ot(), meaning that ((vt). Thus, the total variation distance goes to 0 as t gets large. Consequently, we take f to be large enough so that for each L under consideration, this distance is at most 10-5
Similarly instantiating the CLT on the sum vector of the { --t t samples corresponding to the coin landing tails, which, recall is simply a scaled binomial random variable in the first coordinate (and zero elsewhere) yields that for large enough é, this vector has TV distance at most 10-5 close to a Gaussian having the corresponding mean and covariance (discretized to the closest integer) in the first coordinate, and zero elsewhere. Also, note that the variance of first coordinate is O()) (for in the assumed range) which is large for large enough.
Thus, the sum of vectors corresponding to coin landing heads and f vectors corresponding to coin landing tails has distance at most 2- 10-5 from the convolution of the corresponding discrctized Gaussians. Now we can apply Lemma 21 which gives us that the convolution of the discretized Gaussians here has distance at most 10-3 - to the discretization of the convolution of two Gaussians (here we use the fact that the variance of the first coordinate of the vector corresponding to coin landing tails large enough and all its other coordinates are zero). By a triangle inequality, we get that the sum of t vectors corresponding to coin landing heads and f f-1 1 vectors corresponding to coin landing tails has distance at most 3 10-5 from the discretized Gaussian of corresponding mean and covariance.
- So far, we have shown that for any t E [1/2- 4VE,E/2+4VE, sum of t vectors corresponding to coin landing
heads and L - 1 vectors corresponding to coin landing tails has distance at most 3 10-5 from the discretized Gaussian of corresponding mean and covariance. In Lemma 23, we show that all these Gaussians have TV distance at most. 10-5 from the desired Gaussian (the Gaussian having mean and covariance same as mean and covariance of sum of f i.idd samples from our original distribution). Lemma 23 uses the fact that uo is close to 1 and e is small constant. This Lemma essentially involves showing that the difference between 5th coordinate of the means of the Gaussians is roughly u, w.VE whereas the standard deviation is roughly Vu.V.. Thus for un large enough, u, will be small, and the standard deviation will be much larger than the difference between the means.
Combining the above arguments, we get that sum of E i.i.d. samples from our distribution has TV distance at most 0.001 + 10-5 + 10-3 s 0.002 from the discretized Gaussian with corresponding mean and covariance.
Lemma 10. Consider two distributions supported on 0), the basis vectors, and [2,0,0) such that the proobility of [0, 0, 0] is at least 1 - 10- Let for the first distribution, mass all these vectors is guaranteed to be non-zero, and for the secoad distribution, mass on [0,0, 0, 0). (1,0, 0] and 02,0,0) is guaranteed to be non-zero. Then for constant a E (0, 1), and n large enough, the distribution of the sum of an i.i.d samples from the first distribution and (1 - a.)n i.dd samples from the second distribution has total variation distance at most 0.01 from a Gaussian with corvesponding mean and covariance, where the mass has been discretized to the nearest point in the integer lattice.
Proof. Using Lemma 9, we know that the sum of an i.d. samples from the first distribution and sum of (1 a)n i.i.d. samples from the second distribution has TV distance at most 0.002 from the corresponding
20

---

Published in Transactions on Machine Learning Research (11/2025)
discretized Gaussians. Here, for the first distribution apply Lemma 9 with 3 and for second distribution, we use S 3 depending on whether it has non-zero mass on [0, 1, 0] and (0,0, 1]. All that remains, is to prove that the convolution of two discretized Gaussians is close, in total variation distance, to the discretization of the convolution of the two Gaussians. This is true for any Gaussians in constant dimension such that the minimum eigenvalue of covariance of al least, one of the Gaussians super-constan, (Lemma 18). In our case, the Gaussian corresponding to the sum of an samples from the first distribution has minimum eigenvalue (n). This is because the per-sample covariance for the first distribution ΣΙ has det(E,) > 0 and |Σ = O(1) (both independent of n), so with Lan an Σ1 we get Amin(Ean) 2 an det(En) / 1l (()) (see Lemma 22 for detailed proof). Taking to be large enough, we get that convolution of the two discretized Gaussians has distance at most 10-5, to the discretization of the convolution of the two Gaussians. Applying a triangle inequality, we get that the sum of n i.i.d. samples produced as above has TV distance at most. 0.004 + 10 5 < 0.01 from the corresponding discretized Gaussian.
Let (a)(a) and (b) be 3 dimensional random variables containing the number of elements observed exactly 2, 3 and 4 times, for samples drawn from and b respectively. Let G. be random variable corresponding to picking sample from gaussian with same mean and covariance as FP((a) and rounding each coordinate to the nearest integer. Similarly, Gb corresponds to FP(b).
Lemma 11 (Fingerprints close to discretized Gaussians). dTv(FP((), G.) & 0.01 and (Fv((F()), Gb) S 0.01.
Proof. Recall that FP(a) and (b) are 3-dimensional random variables containing number of elements appearing exactly 2, and times in samples drawn according to a and b respectivcly. Due the structure of and b (see Definition 8), we can decompose F P(a) and PPb))
FP(a) Σ FP(D')+
Σ FP(r'),
1=1
1=0++1
FP(b) = Σ FP(()+
Σ FP(s').
(=
Here, P(D'') denotes the fingerprint vector when we obtain 2 samples from pi and 2 samples from pi. Note that as we vary i, FP(p') corresponds to independent samples from the same distribution. FP(q'), FP(r') and F(tss) are defined analogously. Note that each of FP(p'), FP(''), FP(r)) and FP('') are supported on [0, 0, OJ, the basis vectors and [2, 0, 0]. Here, FP(''), FP(q'), FP((') has non-zero mass on all of these vectors, and FP(r") has non-zero mass on [0, 0, 0j. 0, 0J, (2)
Also, note that FP('') = [0, 0J corresponds to the event that when we draw 2 samples each from pf and ph. the 4 samples so obtained are distinct. The probability of this event is equal to (1 - (1 (12mmm(1 - 3/m) which is at least 1 - 10-16 if we choose m to be large enough. Similarly, one can verify that for m large enough constant, for each of F(q'), FP(r') and FP(('), the probability of these random variables being 10,0, 0] at least 1 10-16.
By applying Lemma 10, we get dTv(FP(a)) G.) < 0.01 and drv (Fv(FP()) s 0.01, which completes the proof.
Finally, we conclude with the calculations required in Step 4 of the outline.
Lemma 12 (Discretized Gaussians are close). drv Go) < 0.02.
Proof. Let Gy be random variable corresponding to picking a sample from gaussian with same mean and co- variance as FP(a) (without any rounding). Similarly, G² corresponds to FPb).. By data processing inequality, rounding each coordinate can only decrease the total variation distance, drv(Ga, Gb) < drv Gb).
By Lemma 14, given samples from a finite support, there exists an invertible linear map, say A, such that can go from a vector of fingerprints to vector of collisions by applying A to the vector of fingerprints.
21

---

Published in Transactions on Machine Learning Research (11/2025)
Since can decompose and b into disjoint supports from each of which we are getting 4 samples, applying A also lets us go from vector of fingerprints to vector of collisions for samples obtained from and b.
We apply A to random variables Ga and G. Since A is invertible, drv(AG,, AG,, = drv G,))) Here AG", is a 3 dimensional Gaussian random variable with mean and covariance same as the mean and covariance of the vector containing number of 2-way, 3-way and 4-way collisions the samples produced by a. AC, is related to in the same fashion.
From Claim 5.2, we know that expectations of AG', and AG,, match. Let us denote the expectation by p. From Claim 5.3, we know that covariances of AG and AG,, are as follows:
an/m² 012/m1 m
012/m²
a1s/m²
dn/mm² 022 d//mm² /m
a/z/m" / dis/m* d2a/m" ags lm//m²
E(AG.) E1 +
0222
/
023/m²
E(AG)) Ei
013/m*
023/m²
a33 /m²
d13/m² /
a2//m²
where
Tu/m
722/m²
M13/ 113/m31
Σ1 =
Y2a 12a/m² n2/m²
Y23/ m
m3//m3
723/m²
Let G1 be random variable distributed as Gaussian with mean μ and covariance E1. From Lemma 17, which is a technical lemma that bounds the TV distance between Gaussians having the same mean and similar covariances, and whose proof is given in Appendix F, we have that dTv(G1, AG,) s 0.01 and drv(G; (G,,)G)) & 0.01 (compared to the lemma statement there, covariances here have an additional factor of n but that does not change the TV distance). Using triangle inequality, we get , I 0.02. Since drv Gb) S drv(G"a G%)) = drv dAV(,A,, AG)), this completes the proof.
Lemma 13 (Fingerprints are close). (FvvFP((o)) (), FP())) & 0.04.
Proof. (Fv(FP(a), F(())) S dTv(FP(a), Ga) + dTv Gb) + drv(Ga, Gb) by triangle inequality which is at most 0.04 due to Lemma 11 and Lemma 12.
With this, we have shown that the TV distance between the distribution fingerprints of the two sequences is small, even when the total variation distance between the corresponding average distributions is at least some constant. We can then invoke the Neyman-Pearson lemma (Neyman & Pearson, 1933), (Canonne, 2022, Lemma 1.4) to say that no testing algorithm can distinguish between these two cases with high probability. This concludes the proof of Theorem 1.6.
6 Conclusion
We show that sublincar sample complexity property tosting extends to the non-i.id. sctting where the samples are drawn from different distributions, and we are interested about the average distribution. In particular, natural collision-based testers with just constant number of samples from each distribution suffice to solve the identity and closeness testing problems. While our analysis is optimal with respect to the support size, it is still sub-optimal with respect to the distance parameter g-resolving this is an interesting future direction. Another iorection could be to chart the landscape of the problem when T (number distributions) is fixed, and e (number of samples from each distribution) varies.
Acknowledgments
S.G. did part of this work al Stanford where he was supported by a Stanford Interdisciplinary Graduate Fellowship, and part of at Harvard, where he was supported by a postdoctoral fellowship from Harvard's Digital Data Design Institute. C.P. was supported by Moses Charikar's and Gregory Valiant's Simons Investigator Awards. K.S. was supported, in part, by funding from the Eric and Wendy Schmidt Center the Broad Institute of MIT and Harvard. G.V. was supported, in part, by Simons Investigator Award.
22

---

Published in Transactions on Machine Learning Research (11/2025)
References
Maryam Aliakbarpour and Sandeep Silwal. Testing properties of multiple distributions with few samples. arXiv preprint arXim:1111.073 2019.
Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld. Learning and testing junta distributions. In Conference Learning Theory, pp. 19-46. PMLR, 2016.
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, pp. 442-451 TEFF, 2001.
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing closeness of discrete distributions. Journal of the ACM (JACM), 60(1):1 25, 2013.
Clément I, Canonne. A short note on learning discrete distributions. arXiv preprint arXiv:2002. 1100000..11140 11457, 2020.
Clément L. Canonne. Topics and techniques in distribution testing: A biased but representative sample. Foundations and Trends0 in Communications and Information Theory, 19(6):1032-1198, 2022. ISSN 1567-2190. doi: 10. 100.1511/000 1/51100000000144 URL http://dx. http::/dxxdoi...../ org/ /0///10.11 10.115110100000011
Siu-On Chan, Tlis Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the twenty-fifth annual ACM-SIAM symepssium on Discrele algorithms, pp. 1193-1203, SIAM, 2014.
Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Arnaul ACM SIGACT Symposium on Theory of Computing, pp. 67-60, 2017.
Sitan Chen, Jerry Li, and Ankur Moitra. Learning structured distributions from untrusted batches: Faster and simpler. Advances in Newral Information Processing Systems, 33:4512-4523, 2020.
Herman Chernoff and Shelemyahu Zacks. Estimating the current mean of normal distribution which is subjected to changes in time. The Annals of Mathematical Statistics, 35(3):909-1018 1964.
llias Diakonikolas and Daniel M Kane, A new approach for testing properties of discrete distributions. In 2016 IEEE 57th Anneua Symposium on Foundations of Computer Science (FOCS), pp. 685 694. IEEE, 2016.
Tlass Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimennsioall robust statistics. arXiv preprint
11.09911,, 2019.
Tliss Diakonikolas, Daniel M Kane, and Vladimir Nikishkin. Testing identity of structured distributions. In Proceedings of the swenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pp. 1841-1854. SIAM, 2014.
Tlis Diakonikolas, Themis Goulcakis, John Peebles, and Eric Price. Collision-based testers are optimal for uniformity and closeness. arXiv preprint arxiv: frXiv:1611.0357,, 2016.
Taas Diakonikolas, Themis Goulcakis, John Peebles, and Eric Price. Optimal identity testing with high probability. orXiv preprinl arXiv:1708. 7080027788.02728,, 2017.
Ilis Diakoníkolas, Gautam Kamath, Danicl Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability. STAM Journal on Compuling, 48 (2):742-864, 2019.
Oded Goldreich. The uniform distribution complete with respect to testing identity to a fixed distribution.
In Electron. Colloqušum Comput. Complex., volume 23, pp. 15, 2016.
Oded Goldreich and Dana Ron. On testing expansion in bounded-degres graphs. 2000.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
23

---

Published in Transactions on Machine Learning Research (11/2025)
Ayush Jain and Alon Orlitsky, Optimal robust learning of discrete distributions from batches. In International Conference on Machine Learning, pp. 4651-4660. PMLR, 2020.
Mladen Kolar, Le Song, Amr Ahmed, and Eric P Xing. Estimating time-varying networks. The Anmals of Applied Statistics, pp. 94-123, 2010.
Christoph H Lampert. Predicting the future behavior of a time time-varying probability distribution. In Proceedings of the IEEE conference computer vision and pottern recognition, pp. 942-950, 2015.
Reut Levi, Dana Ron, and Ronitt Rubinfeld. Testing properties collections of distributions. Theory of Computing, 988):295-347 2013. doi: 10. 10.4/000..2220 1ew.c2003.00000000 URL htt::://hthoorooooooooooo .rgg articlessv009a008.
Jerzy Neyman and Egon Sharpe Pearson. Ix. the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematioal or Physical Character, 231 2816647706))2285 229-::::7-377 1933.
Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions Information Theory, 54(10):4750-47 4755, 2008.
Mingda Qiao and Gregory Valiant. Learning discrete distributions from untrusted batches. Anna R. Karlin (ed.), 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIes, pp. 47:1-47:20. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2018. doi: (2230//IIles.ITSSS... 201 URL hatps://ddon wowoo.oorg//11/ 4230/LIPICa.IIII ITCS. 2018.47.
Kevin Tian, Weihao Kong, and Gregory Valiant. Learning populations of parameters. Advances in neural information processing systems, 30, 2017.
Gregory Valiant and Paul Valiant. Estimating the unseen: n/log (n) (n)-sample estimator for entropy and support size, shown optimal via new clts. In Proceedings of the forty-third annual ACM symposium Theory of computing, pp. 655, 2011.
Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. STAM Journal on Computing, (1l))42244555 2017.
Ramya Korlakai Vinayak, Weihao Kong, Gregory Valiant, and Sham Kakade. Maximum likelihood estimation for lcarning populations of parameters. In International Conference on Machine Learning, pp. 6448-6457, PMLR, 2019.
A Learning the average distribution
In this section, we show that the sample complexity of learning the average distribution in the setting of non-identical samples is asymptotically equal to that of the i.i.d. setting.
Claim 1.1. Given access to T distributions, Pr...., Pr. each supported for any E > O, given = samples drawm from each P., one can output distribution Pang such that with probability at least 2/3, (Tv Pavg) S E, provided T = Okk)²)) Furthermore, (kk/E2) samples are necessary, even if P1
common domain of size S k
Pr = Pang for such a guarantee.
Proof. The lower bound for the setting of non-identical samples follows directly from the lower bound of the standard ii.d setting, that is we let p, = p, Vt E [T). For the upper bound, we follow the proof in (Canonne, 2020, Theorem 1). Consider the empirical estimator given by,
P Pavg
1 T
Σ [E[T]
1[x, = i].
24

---

Published in Transactions on Machine Learning Research (11/2025)
We have that
E Pavg
Pavgl2 11
E
(1( (p)())
T
1E|T]
$ T
Σ
Σ
Pr(1)
TE[T]
P Σ
Pavy
T
T
Thus, by Markov's inequality, the squared & distance of this estimator from Pavg smaller than probability least 3. By Cauchy-Schwartz, the & distance of this estimator from Pavg is at most probability at least and thus, this distance is smaller than if T Okk/e2).
T with
3k with
B Impossibility Result with c c=
Claim 1.2. Given access to T S k/2 distributions, Pi...., PT, and c= 1 sample drawn from each distribution, no tester can distinguish the case that the average distribution, Pavgr is the uniform distribution of support k, versus has lotal variation distance at least 1/4 from Unif(k), with probability of success greater than 2/3.
We prove the following equivalent claim.
Claim B.1. For all ei 0, there is k 2 ci such that for any T S k/2, given e= sample drown from each of PI..... Pr, there erists no testing algorithm that succeeds with probability greater than 1/2 and tests whether
Pavg =
Unif(k)
versus drv (Paag Unif(k)) 2 1/4
Proof. All the logarithms in the proof below are base 2. Let be the smallest power of 2 greater than or equal to C1
2 llgee]
For T 5 k/2, let k/T, so that r 7 2. We set r' to be the smallest power of 2 greater than or equal to r,
r' 2 logr]]
Let T" k/r'' By construction T kk/2, T is integral, and T
We now consider two distributions Dj and D2 over sequences distributions (P.... Pr) such that for all sequences (P)... Pr) the support of D1, avg(p)... ... ...p)))..p)))) = Unif(k) and for all sequences the support of D2, drv(avg(P) ... Pr), Uni 1/4. Further, we will show that the samples drawn from distribution soquences drawn from Dj are indistinguishable from samples drawn from distribution sequences drawn from D2 (that is, corresponding distributions have total variation distance 0). This implies that there exists no testing algorithm that succeeds with probability greater than 1/2 and tests whether average distribution is the uniform distribution versus average distribution has total variation distance at least 1/4 from the uniform distribution.
Here the procedure draw a sequence of distribution (Pr... Pr) from D1:
Draw a permutation æ [k] + [k] uniformly at random.
Use the permutation to partition the domain into T" scts of size r' cach where for i i T', cach Pa corresponds to uniform distribution over distinct set. That is, for 1sis T", p, corresponds to uniform distribution over (x ((i 1) * r' + 1), m ((i -) x +2)
For T' +1 +1 P, corresponds uniform distribution over the whole support [k], that is p; = Unif(k).
25

---

Published in Transactions on Machine Learning Research (11/2025)
Here is the procedure to draw sequence of distributions (P1... .p)) from D2:
1. Draw permutation и [k] + [k] uniformly at random.
Use the permutation и to partition the domain into T" sets of size r' each where for i S. T", each P. corresponds to point-mass distribution supported over an element of distinct set: For 1 $ S T Pj corresponds to a point-mass distribution with probability mass 1 on element ((i 1) * +
3. For T +1 +1sist T, P, corresponds to uniform distribution over the whole support [k], that is P. (k).
Note that all the distributions sequences in the support of D1 satisfy avg(P) .P) ug. Next, we show that all the distribution sequences in the support of D2 satisly drv (avg((1 ... Pr), ..r))) Uni((k)) 2 1/4. For such T"
distribution sequences, avg(P1 ... pr) has mass _ TE on T" domain elements and mass $ TE on
k T" domain elements. From this, we get
drv(avg(Pi ... Pr), Unif(k)) (k - T
Tk:
1
4
where for the last inequality, we used T" ST <//2 and / 2 1/2.
Now, will show that the samples drawn from distribution sequences drawn from D1 indistinguishable from samples drawn from distribution sequences drawn from D2 which will complete the proof. Let D be the distribution corresponding to c = 1 sample drawn from each of Pı...., Pr. where (Pi... ... Pr) is drawn from Dj (with c= = 1). We define D analogously. We want to show that dTv ) ) O. Note that in both DVr and DØ cach of last (T - T') samples (XiheTT-T) are drawn from (ni independent of the first T' samples (erre And the first samples (Xiherr) correspond to choosing T distinct domain elements uniformly at random. Thus DV and D are the same distributions.
C Poissonized setting
In this section, we state and prove some results for the non-i.i.d. setting, where we are also allowed to use Poissonization. We will use the following standard facts about Poisson distributions.
Let Poi(A) denote a Poisson random variable with mean parameter 2 O.
Fact C.1. For any Å1, A2 2 0, if X1 and X2 are independent random variables distributed as X1 ~ Poi(A1) and X2 ~ Poi()2), then X1 X2 Poi(A1 + >2)
Fact C.2. Given Poi(c) samples from a distribution p E Ae, the frequency of any elemend j [k] follows the distribution Poi(c p(j)..
We are now ready to prove the following theorem.
Claim C.3 (Poisson identity testing). For any > 0 and reference distribution q DE. with Poi(c) samples from each of Pi.....PP Pr and T = O(v (T)))) there exists a testing algorithm that succeeds with probability at least 2/3 and tests whether,
Pavg
versus
dr ② EE,
for any c 2 1.
Proof. Note that we are given Poi(c) samples from each distribution for all / & [T]- For each /. E [T), let N₂ denote the number of samples drawn from P Note that N, ~ Poi(c). For i [K]] let Ni(1) the random variable that denotes the frequency of clement samples X,, that is, N.(1) = [j E [N,] X,() = (7). By Fact C.2, we know that
(1) Poi(e P(())
26

---

Published in Transactions on Machine Learning Research (11/2025)
Furthermore, if we let N(t) Eiem No(1), then by Fact C.1, we get that,
N(1) Poi Poi(c. Σ Pp((0) Poi(eT Pavg (i)
1E[T]
Therefore, N()) has the same distribution as the frequency of element when we are given Poi(cT) i.i.d samples from distribution Parg As cT E O(vk/E") and since we just argued that we are under the setting of having drawn Poi(cT) samples from Pavgs can invoke existing identity testing algorithms that use Poissonization for the iid setting to solve the problem with success probability 2/3, even with == 1. ]
Collisions and Fingerprints
We relate the collision statistics and the fingerprint of sample by an invertible lincar map. To recall, the number of m-way collisions in sample S= (XI...,, Xn) ) is equal to Ei Zic-in [[x, =... = X The fineeprrnt of the sample is a count array, where for each i, we list the count the number support clements that appeared exactly times in S.
Lemma 14 (Collisions to fingerprint). Let Iı, 12,22, E [m] for m > 4. Let 62n cz Cs denote the number of 2-way, 3-woy and 4-way collisions amongsl It, I2, F3, T4- Purther, let n2, ny n4 denote the number of elements in [m] occurring exactly times, times and 4 times respectively in æ1, 22, 2z, 24. Then, the vectors
C2
72
c3
and
are related by an inverllble linear map. In particular,
C4
n4
1
-3
6
Q2
f3
=
0
4
C3
f444
C4
Proof. Observe that
714 C4. 7g
03
14 C3
4c4
4
n2 C2
n33
11 C -3(cs 4cs) - 6c₁ C2 3cg + 6c4.
2
The matrix associated with the linear map has determinant 1, therefore the map is invertible.
E Sufficiency of fingerprint for gooling-based testing algorithms
We first formally state the definition of pooling- based testing algorithm.
Definition E.1 (Pooling-basee testing algorithm). Fix e and let Perm(cT) denote drawing a uniformly
random permutation over cf' elements. A pooling-based testing algorithm A for property C A with sample complexity eT is a (possibly randomized) algorithm which, when given randomly shuffled pooled multiset of e samples drawn independently from each of Pi....,Pr i.c., S = -K= ...,,.".."" и ~ Pe)m(eTT), S (S), produces output A(S) E {0, 1) satisfying the following
x!00 ~ p.).
If Pavg P, then Prs... ( 1] 2 2/3.
dfv (Pavg avg P) 2 e, then PrS.:.A[A[S] = 0] 2 2/3.
The following lemma states that the fingerprint of the combined sample captures all the information required for pooling-based testing algorithm to test symmetric property of the average distribution.
27

---

Published in Transactions on Machine Learning Research (11/2025)
Lemma 15. Let A be pooling-based testing algorithm having sample complexity cT that tests symmetric properly P S De of the average distriuution Pavg avg(Pp:..... -P)) Then, there erists pooling-based algorithm A' for the same task having the same sample complerity which takes as input only the fingerprint of the combined sample.
Proof. Let the fingerprint of the combined sample S be denoted by f fi, fer). Here, Si is the number of elements in [k] that occur exactly times in the combined sample. Given as input f. the algorithm A' constructs a sequence S in the following way:
Initially, S Φ, e
For i= .....,,T:: cT:;
While Ji 0:
Append i copies of to S.
e et fit 1.
3. Draw Te ~ Perm(k).
4. For every E S:
Set (8).
Draw 35 ~ (T)
Set S + TS(S).
The algorithm A' then feeds S constructed above to A, and returns A's output.
Observe that the distribution of S constructed as above is identical to the distribution of S obtained in the following way:
Draw ne ~ Perm(k).
Draw S 0 t=1 (x(1) ,..., x!!) (p.).
Draw Fg (cT.
4. Set S + TS()).
Here, (p) denotes permuting the probability distribution p according to π ie. T(p); = Pr(s)- Now, for fixed permutation Th, observe that avg( (
(PT)) = Ta (avg(p)..... Pr)) = Th (Pagg). Further, recall that. the property P we are thinking about symmetrie. Thus, if Pavg P,, then (P P for any ih (krm(k). Similarly, if Pawg & P, then (P(wg)) P for any TT E Perm(k). Thus, for any fixed Th: A correctly tests if avg( (Pt)............. (Pr)) has the property P ( ( avg(P).... Pr) has the property P). Consequently, A (and hence A²) correctly tests for a randomly chosen क well.
F Technical Results for Section 5
We prove a technical lemma that bounds the TV distance between Gaussians having the same mean and similar covariances.
28

---

Published in Transactions on Machine Learning Research (11/2025)
Lemma 16. Let A and D be defined as follows:
012/m
013/m²
1/m²
0
0
A
m12/m²
0/2/m
O2a/mm
and matric D
1
1/m
ana/m²
a23/m²
0s3/m"
0
1/m²
where Oii are bounded by constants independent of m. For large enough m, there evists a positive constant a such that,
-aD 1 AA3aD
Proof. Let 11 [1,1,0], 02 [1,0,1] and U3 [0, 1. Note that,
A
01 m
U1 u
+
013
2222 +
m 2ans + D',
023
m
where D' is diagonal matrix, whose entries are follows:
Or1
012
011
0
m2
172
D'=
011
222 m
(14)
0
0:38
0.13 7/
9:23 m
m
Note that, it is immediate that, Uj fi N are defined as follows,
2D1,
0202
3
2D2 and Uzug = 2D3,
where matrices Dr, D2 and D3
1
0
0
1
0
0
0
0
0
D1
0 1
0
D2
0
0
0
and D3
0
1
0
0
0
0
0
0
1
0
0 1
This is because for any E R3, x
"oTuea (z) + x2)² 2(x + =23)
2xx TTDDD Diæ, and similarly (æ) + 2z)² =
2(z + 23) and (x2 + zz)² < 2(x3 + +33).
Furthermore, as all 0zy8 are bounded independent of m, we have that the matrix D' satisfies, D' c- D for some positive constant c.
Combining all the above inqqualities we get that,
Q13 m
0:23 U2
ugug + +D' 2/012| m
2 2/01s| m
2 2/022l m²
= m
U1
+ m
D₁
D2
D3
D
The matrix in the final expression simplifies to,
2/012| m
2ossl
+
m2
m
0
20al
2|mgal m
O
m
mm
0
2/ar mi
2
0r2al
As all ags are bounded by constants, have that the above matrix is upper bounded by D for some large constant a > 0. Therefore A < D.
The proof for the other side, that is -a D < A follows exactly the same argument when applied to -A and we conclude the proof.
Lemma 17. Let G1 be distributed as N En) and G2 be distributed as N (1,, E2) where
71/m 7m/mm
n22/m²
h//mm²
ann/m² a12/m3 a13/m**
012 h2/m3
a13/m
= =
7/22/m m
1/23 m3
and En = E1 +
O:a /m3
023 m
T/s//m m
'/zs/ m
"/ss/ 7/ss/m²
0zz /
ass/ m
for Yig and as such that lyyl and Jacyl ore bounded by constants independent m. Then drv Gz) S 0.01, for large enough.
29

---

Published in Transactions on Machine Learning Research (11/2025)
Proof. In proof, show that, for sufficiently large m, the covariance matrices Σ₁ and Eg satisty: (1 -- a 3 E2 3 (1 + a/m)> for some constant a > 0. Equivalently, all the eigenvalues of the matrix L --"2)(L")-- lie in the range [] - a/m, 1+ 1-a/mmmmmm a/ml, where D = LL" is the Cholesky decomposition of matrix Σ1. Note that, by the TV distance bound in Fact F.3 this result immodiately implics the following upper bound on drv(G1, G2) between the two Gaussian distributions,
max (As, x,
0(1mm) V2Te
drv(Gr, G2) S
I 0(1/m)
V2TE
Here, while applying Fact F.3, used that 1₁ and G2 have the same mean. Now note that, for sufficiently large m, get the desired upper bound on the drv(Gi, G2).
Therefore to prove our lemma, all that remains is to show that, constant a > 0. In the remainder of the proof, we prove this claim. First we show invertibility of Σ1. Since Σ1 is a covariance matrix in our construction, the diagonal coefficients 711: 722, T33 are fixed positive constants (independent of m). Thus the diagonal permutation contributes 733/ /m" det(E1), while any other permutation includes at least off-diagonal of order 1/m2 1/m² and hence has magnitude 0(1/m²). Therefore, for large enough,
N Eg I (1 a/m) for some
711722783
(et(Ei) N
0,
2 2m
Σ1 is invertible.
Now let
an//m²
012/m²
013/ m
E
a12/m3
0:22/ 0:2//m²
mma m
023/ m²
(15)
Q13/m*
0:33/ 023/m² /m
Gr3/ m
To prove the claim, we in turn show that,
Eg = E En.
By Lemma 16, we know that there exist constants and 02 such that, -an D) D F 3 on and 0 E = a2mD, where
1/m2
0
0
D =
0
1
1/m3
0
1/m²
Here the bound 0 = 11 I agmD follows by applying Lemma 16 to m m112, which has the same (1/m², 1/m2, 11m²)) structure with cocfficients aij V
In the following, we prove 3 Σn for some constant a > 0. We first show that D N 1 En for some constant.
7. as 2 D, we conclude that 1 -V, Towards this end, we now prove that D I 2Σ, for some constant y. Equivalently, we wish to show that the smallest eigenvalue of the matrix F D D-1/211 E D 1/2 1-2 is lower bounded by some constant. Note that is PSD and is equal to,
?11
72/m212
T1a/m
F=
72/m3/2
722 723/m1/2 1/2
723/m
713mm
733
Its trace is Tr(F)= M11 + 722 + 733 O(1). Moreover, the determinant satisfies
71122273
det(F) >
Co
>
2
for all sufficiently large m (the diagonal term dominates, while all off-diagonal permutations are o(1).. By Gershgorin circle theorem (Fact F.1), the spectral norm is bounded:
Xmaxx (F) S max (Th
Irs m1/3
S Co,
30

---

Published in Transactions on Machine Learning Research (11/2025)
for some constant Cu and all large m. Therefore, with eigenvalues A1 X1 d As 20,
Amin (m)n(F)== =F)=A 2 del(F)
A1
Equivalently, D 3 11E E1, Le. D 2 Σl with = 1/a. Hence E 3 a1 D 3 21 E1, iee. E 2 for a := a17.
E 3 E follows exactly the same argument when applied to The proof for the other side, that is a and we conclude the proof.
-a. m
Lemma 18 (Dieretiiationncomolutiiii convolution almost commute for Gaussians). Let X Nuxx, Ex) and Y M(ay, E be independent in Rd (with d constant), and assume at least of Ex, By is positive definite." Let Disc(-) be coordinale-wise rounding to the nearest inleger (lies ure immalerial since Gaussians pul zero moss on boundaries). Then
Vd
min (iTEV))E')) (T((ET")
(rv(Disc(X) + Disc(Y), Disc(X + +Y) s
4
In particular, if Amin (mx)(Ex) - Do or Amin )min(Ey) + 00; the left-hand side is O(1/VAmin)) and tends to
Proof. Without loss of generality assume Ny > 0; otherwise swap X and Y. Let f and g be the densities of X and Y. For m zd, write Cm:= [- 2 1dd. Define
P(m): = Pr(Disc(X) Disc(Y) = m) = E
(1/, f(x) dx) (fc Cm
g(v) glv)dy).
aEZA
= m)) = /
| f(x) g(z x)) dx dz.
Q(m)= = Pr(Disc(XXX) + +Y)=
Cm _
For Ca, set 8(x) = a x E 11- 1. 1.. Changing variables z = y + in ((m yields
Q(m)= = Σ - (
( glv (()+8(x)) dy) f(x) de,
aeRd Co
and hence
(s(0) - s(v + 8(x)) dy) f(x) dr. Σ E [. aEEN Co
P
(16)
Bounding Σm PP()) - Q(m)l by an expectation times a norm Summing equation 16 in absolute value over m and using that the cubes Jm are disjoint and partition Rd
(P((m) Q(m)) & E/ f(x) (f_lo(e)) g(v + 8(x)) dy) do
meZd
/ f(x) (19()) -(:+ dr.
(17)
( (e used Em Jcm-o'1 Em Em Scm... 1.1 = Spal 1, since Jm partition Rd.))
Apply Lemma 19 with h and = 5(x) pointwise in to get
(9()) g( + 8(z)) s [|8(z)]l2 lV
(18)
2I covariance singular, bound below with that matrix should read as +00; the inequality is then applied with the other (positive definite) covariance.
31

---

Published in Transactions on Machine Learning Research (11/2025)
Plugging equation 18 into equation 17 and factoring out the constant
VVlll yields
Σ
P(m) - Q(m)l = [ [[[[6(X)]a]) V
(19)
MEZ
Since X E (isc(X)) almost surely, 8(X) Disc(X) - X E 1 21 and thus
vd ||ö12
[[16(()]
S
sup S1/2
(20)
2
Computing / For Y ~ N(vr, Er),
Vg(u) Ex (v-
V /
- 2112].
1/2
where Z Ia). By Cauchy Schwarz,
IVgla S VV IT(E))).
(21)
Combining equation 19, equation 20, and equation 21,
Σ IP(m) - Q(m)) - Vd VIH2TT)),
MEZK
hence
Vd drv(Disc(X)) + Disc(Y), Disc + +Y) Σ - & 4 VIrezT))
m
By symmetry, the same bound holds with Σx; taking the minimum proves the claim.
Lemma 19. Let h. : Rd - IR be locally absolutely continuous with Va E (.T)))). Then for every E Rd
|| + u) - h(-))lzz < /
Proof. Fix E Idd and consider the path ++ y By the fundamental theorem of calculus,
My + u) - S (Vh(y tu), u) dt,
so [h(y u) (vr) < ||u|2 fo + by Cauchy Schwarz. Integrating in and using Fubini with the change variables y + + u (unit Jacobian) gives
| [hy u) h(2) dy S |ulla /''' / [Vhhyy + +t) = ||u||a Vhhle
Lemma 20. Let X1 and X2 be independent with distributions ((u1, and N(2, oz), respectively. Let ::= max oz)- Then, for large enough,
drv(Disc(Xi) Disc(X2), Disc(X1 + X2)) < 0.00001.
Proof. Apply Lemma 18 with d= 1:
1
1
drv(Disc(X1) + Dis)(X2), Disc(Xi + X2)) < min o. d2
4vi
Thus the bound is & 10-5 vi. 25,000, i.e. 1 6.25 108.
32

---

Published in Transactions on Machine Learning Research (11/2025)
Lemma 21. Let X and Y be n-dimensiionl independent random variables, where X is multivariate Goussian and Y has first coordinate distributed as (0, and all other coordinates identically 0. Then, for large. enough,
(rv(Disc(X) + Disc(Y), Disc(X + +)) & 0.00001,
where Disc(-) denotes coordinate-wise discretization to the nearest integer.
Proof. The idea is that Y perturbs only the first coordinate. Let X-1 denote the last n-1 coordinates of X. After discretization, the last (n-1) coordinates of Disc(X) + Disc(Y) equal Disc(X-1), and those of Disc(X X +Y) equal Disc(X-1) as well. Thus, conditioned on X-1, the event + Discc(Y) E A} depends only on the first coordinate, and likewise for (Disc(X + Y) E A}. We therefore reduce to the one-dimensional case of Lemma 18 on the first coordinate and then average over X-1. We formalize this below.
Write (X1, and Y = (Yi, O, .,.,.,,.)))............... with Y1 ~ .V(0 independent of X. For any S Z" and
u R" mp_1__ define
A, = {m1 E Z: (m1, Disc(u)) E A}.
Condition on X-1 and apply Lemma 18 in dimension 1 (to the pair (X1, Yi)) to get
Pr(Disc(X,)) + DVi) E Ax_, (x-1) - Pr(Diis(Xx + V1) E Ax_, xx))| AVT
In the above, we conditioned on X-1 = which freezes the last n-1 coordinates; thus (X1, Yi) is onc-dimensional with Y1 ~ (V t) independent of X1. We then applied Lemma 18 1, yiclding a bound < 1/(4Vl) uniformly u since the right-hand side depends only on
Averaging over X-1 and taking the supremum over A therefore gives
1 4V7
(rv(Disc(X) Disc(Y), Disc(X + +Y)
10-5 for t 6.25 10a.
Lemma 22. Let X be sample from distribution supported on [0,0,.0, c1, e2. c3, 2e1} with probabilities
uo. U1 U2, U3, such that u1, U2 U3, v > O and un 2 - 10-16 (all parameters independent of n). Let Σ1 Cov(X) and let Ean be the covariance of the sum of an i.i.d. copies of X. Then there erist constants C.: C+ > O depending only on (Mi, u2, u3,v) v) (hence independent. of n) such that
S Amin (oan) S >maxx(aa)) S C. on.
In particular, Amin(Enr)) (n))
Proof. Write μ [[X] (ui + 2v, u2, uz) and D E| diag(u) + 4u, u2, uz), so Ei D pppp By the matrix determinant lemma,
'm) = (m1 +40)uzzg 1 (w) + 2u)² det(E,) = ded D-
112 13 2 44-442222s (wo = Cdet > 0,
"1 + 4u
using #1+4" < "1 + 2v and uo = 1 (w) + + U3 + v). Also E, 1 D, hence \maxx S >maxx (D)
(u]+2u)²
max(u) + 4u, 02, [a} =: ep < cc. If the eigenvalues of ΣS are \ 2 A2 2 Aa > 0, then
del(E1)
Glet
Amin (En) As 2
2
Co > 0.
d1d22
CD
For the sum of an i..d. draws, Ean an Σ1, so Amin (Ean) an Amin (En) 2 acon and Amax(Ean) an Amax(Ee) acpn. Take e, = co and C. = cD to complete the proof.
33

---

Published in Transactions on Machine Learning Research (11/2025)
Lemma 23. Let X1 (T En), X2 ~ (V Ex) and X3 (Fpz Es) be e-dimensional Gaussians, for S 10, where
2u1
2u1 (1 2u1)
4211 U2
4u1 We
2u2
-4u1 U2
242 2wz)
2
1
E1
:
2
-44144 Ue
4ugue
2uc(1 - -2uc)
4v
8v(1 - 2v)
0
0
0
0
0
112
Σ2
0
0]
M1
+ 2u
+ 4v (ui + 2v)²
- (u1 + 2u)u2
- (ui + 2v)ua u2
U2
[u] + 20)u2
u2 u2)
P3
Σ3 =
(u1 + 2u)ue
U2
uc(1 - ue)
and furthermore, 1) + E, u, S 10 and 2) us are positive constants. Now, let Z1 be the sum of independent draws of X3. Let Zz be the of + n independent. draws of X1 and independent draavs of X2. As gets large, for any n E [-4V1,4V1],
drv (1, (2) s 10
Proof. First, note that both Z1 and Zg are also Gaussians, because linear combination of independent Gaussians is Gaussian. Let μr, En and μ2, En respectively be the mean and covariance of Zı and Zz2 Then,
A1 = P3:
Σ = 1 Eg
μ22 (1/2 + n)T + (1/2 n)
Σg (1/2 n) (1/2 n)E2
Let Z be the Gaussian with mean μr and covariance diag Σj), where diag(E,) is simply the matrix E₁ with all non-diagonal entries zeroed out. We will first show that drv Zi) I 10 10-14 13
Consider the matrix diag ( 1122, Σ₁ diag(E.) 1/2 Let us denote this matrix by M1 and it is equal to
+22)aa
+21
Vor02
u2
1
MaMe
/ //
V020
[wy 20)uu
where U1 U1 40 (n1 + 20)2 and v, ux(1 u.) for 2 2. Note that because each u, I 16 and
S 10616 16
U1 +
"1 +
W1 + /4u(1 v)
2v
(1 u1) + 4v - v) Auje 5
S 2((uu vD)
U1
(ur un)
and also, for 2, 2,...,
U;
< 22
V /uu
34

---

Published in Transactions on Machine Learning Research (11/2025)
Thus, the sum of absolute values of off-diagonal elements in any row i of M1 is at most
Σ u Σ Vuuj & 8 c. 10 < 10-14.
j#L
Then, by the Gershgorin circle theorem (Fact F.1), all the cigenvalues of this matrix are contained
[] 10-14, 1 + 10-14). Using corollary 24 that bounds the TV distance between multivariate Gaussian distributions, get
drv dr 21)
21) <
10
mmax
11-10-1 14 10-11) -1) 10011.
1
1+10-14
V2Te
Now, let Z2 be the Gaussian with mean (42 and covariance diag(Ei). We will next show that drv 22) s 10 10-12
Again, consider the matrix diag(En)~1/2 1/22. Eg (ing((I)~11 Let us denote this matrix by M2 and this is equal to
(1+ 26 ) 2 (1-20)1-)))))) 221))+ 88((1 22)
+1+
2m
2 Me
2z
u.
2u1 +8v 10:0-110 +20)
T
Vejez ez 2ug T-
/
(1 + 2n 2u1 ua
(1 2n
(1
2n
2ug 1/2//
V0102
T
- (1 + 2n 2 ue
- (1 + 2n
2Ngue
(1 + 2p))
1- 201
V01u.
V02uc
T-
where V1,- Vi,..., Me are the same as above. Again, using a similar calculation as above, the sum of absolute values of off-diagonal entries in any row is at most
2 21+ 71 1+
2n
Σ
Σ Yuu
2 2
1+
2n
10 < 10
10
where the last inequality holds for large enough I.
Diagonals of M2: For i == 1, write
(M2) A 7
B
A = 2n (1-2u))+80(1-22 B :: 2u (1-22))--u(1-1 D 2u, -80u +20)?
When n = 0, a direct expansion gives A = D - -((1) - 2u)² hence
(M2) 1| 2(41 - 22)²
2(u + 20)²
S 12 11
10-16
< 10-13
D
2u1 Se 2( + 2012
using u1, v < 10-16 For the dependent term,
2n B
2/ml
2u1 + 8y
16
<
e D
2u, Se 2(u + 20)2
since |n| < 4v and the ratio is < 2 for these parameters; thus (M2)11 E [1 - 10-13 enough. For 2 2,
1+ 10-131 for large
(M2),² (1 2n /))
20; (M2) 1 1/5 vl 1 U S Vi
8
8
+2- 10-16
uq
Hence, for sufficiently large e, all diagonal entries of M2 lie in []
10 10 1 10 13].
Thus by the Gershgorin circle theorem (Fact F.1), all the eigenvalues of this matrix M2 are contained in [ 2 10-13 1 + 2 20 10-13]. Again using corollary 24 that bounds the TV distance between multivariate Gaussian distributions, we get
10
1
+ 10 10 -1) & 10
drv( 72) 5 /2Te
max 1
2 10-13 13
35

---

Published in Transactions on Machine Learning Research (11/2025)
Finally, we bound drv (Z1, Zz). Note that both 1 and Z2 Gaussians with the same diagonal covariance diag(Ei), but their means are di and #2 respectively. Since the covariance is diagonal, can upper-bound the total variation distance between the product distributions by the sum of the total variation distances between the coordinate-wise one-dimensional Gaussians. Namely, denoting by of....,o? the c diagonal entries diag(E1),
dTv(21,72) -
of)) +... dTv(N(mi oc), 121 01 1
ddv N
M11 01
.W
+ drv N MIC oe 1) NN P2ee
(N(tte
1)
0c
where in the last equality, used the property that total variation distance is invariant to affine trans- the formula for bounding the total variation distance between
formations. For each of these, one-dimensional Gaussians given in Fact F.2 to gel
|mn 1221
Me 122
drv Z2) v
2t
01
Oe
|m||
12u1 4vl
2u Vuo(1
VIT
V u1 (1 2u1) + 4v(1 v) 4u10
Ue
4/
(Vo + Vui +.. Vue))
(using un and at most 10 10-1)
16
(Vo + vui + vu)
V
16
11-10-
11
VT
< 10-5
Putting everything together, we get using the triangle inequality that
dTv(ZI, S dTv 21) + dTv(Zz, Z2) + (2,,
$ 10-33 + +10 12 10-
10-5
< 10-4
F.1 Other useful facts
Fact F.1 (Gershgorin circle theorem). (Horn & Johnson, 2012, Theorem 6.1.1) Let A = (aiz) E Caxd and sel R3 = Ejji (igl- Then all eigenvalues of lie in
Uf2EC 12- 12- anl aal Rs
In particular, if A E IRdxd symmetric, all its eigenvalues are real and lie
d Ula: R., + Ra).
1=1
Fact F.2 ((Valiant& Valiant, 2011, Fact 29)). Letting N(u, 0²) denote the univariate Gaussian distribution,
a
drv(N(H,, 1), N(u + a, 5
2T
36

---

Published in Transactions on Machine Learning Research (11/2025)
Fact F.3 ((Valiant & Valiant, 2011, Fact 31)). Let G1 (H Σ1 TTT be the Cholesky decomposition of Et. Let X denole the ith the eigenvalue of T-11-27- then
Σ1) and G2 (N Ez) in Rm and let
mR
max 1ax - -1) + TT- -12)1
drv(G1, S
Vme
V2T
We use the following corollary of this fact:
Corollary 24. Let G NN,, Σ1) and G2 N(,, E2) in Rn and suppose En is diagonal with posilive entries. Then, with T = 1//² (so 1-2-2 Mi
1/11 ΣiΣ ) we get
m
(Tv(GI,Ga) <
max (xx
2Te
where .I,..., Am are the eigenvalues of E 1/2 ,, Σ 1/2
F.2 Restating CLT from Valiant Valiant (2011)
Definition 25 (Generalized Multinomial). Let n 2 1 and & 2 1. For each r E [I,...,n] let Pr.l.... :P.k E [0,1] with Ex Pri S 1. Let X (0,e),...,,a.) e C lk be independent with
Pr[x(r) = =c]] Pr.b
Pr[x(() =0==1- Σ Pr.
The sum = EF=1 X E 1 is said to be distributed as generalized multinomial.
Definition 26 (Discretized Gaussian). For μ. R. and positive semidefinite Σ R let N(1, E) denote the k-dimensional Gaussian. (p, Σ) denotes the distribution corresponding obtaining draw from N(,,)) Σ) and rounding each coortinale to the nearest. integer.
Theorem 27 (Valiant & Valiant (2011, Thm. 4)). Let S be k- d-dimensional Generolized Multinomial with parameters above, meon p,, covariance E, and 0² Amin (E). Then,
k//
drv(S, (1s E)) S
2.2 (3.1 0.83logn) 2/3
o1/3
Corollary 28. For conslant k,
drv(S, Naine E)) = 0 ((00g)))
(logn)2/3
0/33
G Closeness Testing
Our tester for testing closeness follows the proof of Batu et al. (2001). Specifically, we divide the analysis into two parts: heavy elements B and light elements S. We show that we can estimate the distance ΣIEB PPav (i) (i)) up to accuracy 6 using the provided samples. On light elements, since the norms corresponding these elements is bounded, we can apply the &2 tester to get the desired closeness tester. We divide the analysis into four sections. In the first section, provide the &g tester, whose sample complexity depends on the norm of the underlying distributions. Therefore invoking & tester only on light elements reduces our sample complexity their corresponding norm is low. Further, in the second and third section we show several properties of light and heavy elements. In particular, for the heavy elements we show that the we can estimate the & distance for these elements quite well. Furthermore, the same section, we also show that the norm of the light elements low, sctting ourselves use E tester on these elements. Finally in the last section, we provide the final theorem, which invokes the results from sections one and two get the desired bounds the closeness testing.
37

---

Published in Transactions on Machine Learning Research (11/2025)
G.1 lg tester
To Lest closeness in f2, we build an unbiased estimator for the terms ||Pavg l6 | 11 and (Pavg Lavg)- In the following, we provide a description of these estimator. For each t E [2], let (Xx(2), Xx(3) and (21(2), (33) denote the 2nd and 3rd i..d samples drawn from the distribution P, and q, respectively. For each t E [7), wo define,
= 1[x = Xx(3) and Y., ((x Xx(3))
Y ( x((3) and Y2, n[x X²(3))
Note that B|Y] = |p. B| = ///.1 and B[ = (p) E|Yad (q. 9e) for all 8, E (7]. Using these random variables, we define an estimator Z and Z' as follows,
Z T2
Y +
Ya)
EE(T]
z'
Yi + Y'
T
EE(T]
Lemma 29.
The eslimator and z' defoned in Equation (1) satisfy the following,
48
B[2] | and Var[Z] S
7
Pavg
T
Pavg
1,2
48
3
E Z 9wvgl 122 and Var[Z"| <
Lavg
aavg
T
T
13
The proof of the above lemma follows immediately from Lemina Next, define
C.t 1[x,(2) x()2)
Q 1 Σ C..). T2
SJE([T]
Lemma 30. The estimator Q defined above satisfies the following,
[[] (Pavg: lovg).
1
Var[Q] T (Pavg: Uwvg) + 7 (Pavg: Lovg: Uavg) + (Pavg: Pavgr lavg))
Proof. The expectation of the estimator Q is as follows.
E[
Σ P.. q
-
Σ
P T
Σ 9i) = -Paags aavg).
T
S.E[[]]
<E(T]
SE(T]
In the following we bound the variance, define Č2t = Cst CCC.t]
T Σ (Ecn) Car) )
M.E[[T]
38

---

Published in Transactions on Machine Learning Research (11/2025)
st '
21
E Σ
Cat
)
E
6,6
Σ
E C
Σ
Caul +
E
Cabl
E
Σ
Cat
a.b
0.
2
terms
o((3)
terms
terma
E B[C21
[Cal²)+ +
Σ
Cabb
B[Cas|E(Cat))
Σ
(B(C,cCab)
E[C.s|
0,
o.
(=
E C.
E
CB(C,,Cob - [(Ca)) +
Σ
Cas - E[C,,)
8,1
a.b
a.b
(
[s.ta.6)]
Σ s,t syfa
E
C
Cacl
E [[Cao]E(CCad]
Σ
(B(CatCosl E(Cai]E(Caa))
a,
a.b
tzb
In the last step, we used the fact that B[Cs [[Cas = 0 when & + and t + Further, since E[Ca for all 8, we get
E B[( Σ ST
Oct 2
S
Σ
E
[C
Σ
Cae))
Cabl)
(22)
a.c
0.h
tfb
Now, we look at individual terms in the above expression. The last two terms can be bounded as follows:
Σ Cacd = ΣΣΣ P. (0) = ΣΣ Peer Pas Ac)
(23)
*#a
a.c Issta
3 ( (Pavg: Pavgr 9uvg)
(24)
Σ Cat) >ΣΣ> (0an))))))) ==
(=)(()=))))))))) 140
Pa: 9: 9b)
(25)
a.t
(xb 1=1
0,b
b
TT. (aagg Javg: Javg)
3
(26)
The first term can be bounded follows:
Σ
E (2el T (Pavg Yavg)
(27)
8,8
Substituting these in Equation 22, and using Var(Q] = f/ f bound.
(ER((Entep)) (Eater Cot) we get the desired variance
Lemma 31. Let F Z Z' 2Q, then note that,
E[F] llPavg alvzl12.
0(1) [ar[F] < T
(1l (1gnvg11 112 + Pavg 112 + (aag anvg)) + ((1)
T ((Page lavg Unwz) + (Pavgy Pang: Anvg))
39

---

Published in Transactions on Machine Learning Research (11/2025)
Proof. The expression for E[ follows immediately by combining bias terms in Lemma 29 and Lemma 30. The variance bound follows by using the fact that Var[F] S 8(Var(Z) + War(Z") + Var(Q)) and further using
variance bounds on Z, Z', Q from Lemma 29 and Lemma 30.
Lemma 32. We can test if ll Yavgl12
e/3
P
Lavg 12
>
e using T
0( 1lav 1 & Powell + Poog::wre)) + ((Pwwg Aove Awvd (Pavy Pova Avve)) samples.
Proof. It is sufficient to bound the probability of P(FF - [[P] > e/3). By Chebyshev's inequality, we get
that P([F - E[F] c/3) & Var(F)/e² Substituting the upper bound on the variance F, we get that,
P([F B[F]| ² 233 - ((1)
T2 (llgavgl2 Pavg l2 (Pag Lavg))
O(1)
Tel ((Pavg: Aavg Anvg) + (Pavg: Pavg 9avg))
The above inequality is further upper bounded by small constant for the value of T specified in the conditions of the lemmaa.
]
G.2 Heavy elements
Let (1) and X((1) be the 1st i.i.d. sample from distribution Pt and q, respectively. Let p(i) 1
T Exerry 1 [X,(1) = i] and ((t) 1 Exe (X((1) = :]. We further define big elements and small ele-
ments as follows,
B, = {i E [&] (() 2 b} and S, = {i E [M] ((1) < <b>
B, ii e [ ((i) 2 b} and S = [k] ((1) b)
where b = (c/l)/2/3 Lemma 33. Let Bp and Bg be random sets as defined above and let B Bp U Bg. If O (( then the following conditions holds,
P
((t))
Pavg (i) c/12) 1/100.
iEB
and
P
7 lavg (i) > e/12) < 1/100.
BEB
Proof. Note that B is a random set that includes at most 2/b elements. Given any fixed subset A S [n]], note that,
P
p(i) Pavy Pavg(1)) (i)l e/12) P(3 A Ç such that f(A') Pavg (A') > e/12)
TEA
< Al e (xp(-O(ne))).
Recall in the above expression ((A') = EiE (() and Pavg (A') Pavg(A') -iEA Pavg( (i). In the last inequality, we used the fact that, P(p(A') Pang (Avy(A') E/12) S exp(-ne? /144) and did union bound over all subsets of A. Therefore for any fixed A such that,
|4| - 2/b, have that,
1
P((((A) (A) > e/12) <
100
P((((B Pavg > c/12)
Σ
P(P(B) Pavg (B) > c/12/B A)P(B= A)
(28)
Σ
P(D(A) Pavg (1)) c/12)\B A)
(29)
40

---

Published in Transactions on Machine Learning Research (11/2025)
Σ
1 P(B A) s 1/100.
(30)
100
The analogous proof also holds for Aavg and we conclude the proof.
Lemma 34. Let Bp and By be random sets as defined above and let B = Bp U Bq. Ifn = O(2)), then the sollowing conditions holds,
P(I Σ (0(1) ((1) - Σ EE
Pavg( (i) lavg (i) 2 c/6) - 1/50
iEB
ie (8(1) Pavg and H Eien lā(i) Aavg(1)) (i)1. Note that, E < F + G + H and F < E G H. Combining these two inequalities we get that,
Proof- Let. E. EieB (i(1) ((i),, F Eien P Pavg Javg (i),, G = EieB
E - -
(31)
Using the above inequality we get that,
P( - Fl 2 c/6) -
H H $ P P 2 c/12) s 1/50.
(32)
The last expression follows from Lemma 33.
G.3 Light elements
Lemma 35 (Light elements). Let S denole the complement of B, correspording to the random set containing elements with empirical probability less than in both f and q. The following norm bounds hold:
2 Pavg (1) 4b/8) S and P()
E Pavg 8b² /8) 55.
P
lovg (i)2 4b/8) S 8 and P
Σ
Lavg (i)² > 812 18) 58,
IES
EES
2 Pavg (avg 4b/0) 8, P1 iE9
Pavg (i) lavg (i) 812 /0) S 5 and P
E Pavg (i) Lavg (1) 812 5
Proof. This argument is essentially identical to the proof of Theorem 20 in Chan (2014).
Let H E [k][ (ave(() 2b} and recall that S = (i [k]](()) b and ((t) b). Here provide the proof for P(Eies (1) > b/00 < for t E {2, 3} and the proof for all the other probability statements follow the same argument.
To prove PiEies Paug (i) ( 1/8) s 8 for t E (2,3) we first show that,
E E Pavg (0)22''' iES
and the lemin statements follow immediately by applying Markov Inequality. Therefore, the remainder of the proof, we focus on proving the upper bound on the expectation.
Note that, E|Eies Pavg (1) E EIEESn Pavg (i) EissnH= Pavg (1) 2'-18--1 Eiesn (t) In the last inequality, we used Pavg(1) (i) < 2b for all E H Therefore all that remains is to show that, E E'Eiesni Pavg(() (1)*] < 21-1
For E S,H, let Pavg(1) (1) = ba and note that 2; 2 2. Then we have that,
E( Σ Pavg (i) Σn Pavg (i)
iE5nH
icH
41

---

Published in Transactions on Machine Learning Research (11/2025)
Σ iCH
Pavg(i)0 P(Pavg (PPww)) xz and p(i) b).
In the last inequality, we used Pavg (1) = z; and P(i E S) P(Pavg (1) = x, and p(i) < b).
Note that, by Chernoff bound it is immediate that, P(i E 9) I exp(-Cbn) I exp(-Cra/ee for some constant C just dependent on L. Substituting this probability upper bound back in the expectation we gel. that,
E Paug Pavg(1) cbt-1
El
iESOH
for some constant dependent on and we conclude the proof.
G.4 l tester
Here we finally present our & tester.
Theorem 36. For any > k-133, there crists algorithm -i-isslncce- Test that, for O ( samples from Pı...., Pr and ...... 4r has the following behavior: it rejects with probability 2/3 when Pavg qavg 1 2 and accepts with probability 2/3 when p
Proof. Let = (c/k)2/3_ Note that n = (b)/(be)). Our & tester works as follows. 1) It uses the first set of samples from P1 .....P. Pr and q1 qr to estimate the heavy elements, which are defined as follows.
Bp = Eie [k] ((1) 2 b) and B, = {i E [+] b))
Define = By U B... Bg. By Lemma 34, we know that with a good probability, EiEg li(1) [()] estimates the quantity DIED (i) (1) qavg (i)l upto c/6 accuracy. Therefore, if |l 4avg la 2 c/3, then this implies that EvEn [0(i) ((i) e/6. In this particular case, we know that we are in the case of || - gavg [1a 2 E and we reject the instance. Therefore in the remainder of the proof we focus on the case, where DiEn Paag qav, S c/3.
. Here we define new distributions .i... PP' and qí '4' focused on light elements as follows: Sample an element from Pt. If this sample is in S output it; otherwise, output uniformly random element from [K]. Define d' similarly. We generate two samples from and Lavg be respective averages.
and qi ....... d using this procedure. Let Pave
Note that, for E S. Paag Puvg (i)+ (i) Pavg (B)/k k and Layg(1) Aavg( (1) + qavg (B)/k. For E B, we have that, Pavg( (i) -avg (Byg(BB/k and Lovg gavg BB)/k.
Note that, when Pavg 9avg. have that, Plag Lavg. Furthermore in the other case, when || Pavg 9avg //1 > and ΣiEB [Pavy (i) Lavg (i)s/ S c/3, we get that, ||p - -Vvyll 2 c/3.
Note that by Lemma 35, we get that, the 2nd and 3rd order norms for Plvg and Livg are bounded by 0(b)
and O(b2) respectively with very tiny constant probability. Therefore we get that, ||P Vaaggl2 < Eies Pavg (i)2 (i)
((1kk) S O + 1/k), || l2 I Eies (1) + O(1kk) S O + 1/k) and (Paeg: 9avg) < 0 + 1/k). Similarly, the third order norms are also bounded, || 13 iEs Pavg (i)8+ +3/ks> Lies Pavg ( (1) < O(b² b/k 1/k32 and || ll < E Eies 4avg(() (i) + +3/k Lies 9avg (i)2 + O(1/k) S 0 bbk 1/k?),
(Paugr 9avg, 9avg) S Ob² + + 1/k²) and (Paug: Pavg 9avg) 0 b/k + 1/k2). We then invoke the l tester with e' e/10vk: Ke Further using the sample complexity bounds from Lemma 32, we get the following upper bound,
o(vb+1/kje" 112 b/kk + 11/K++113)/68 80))))))))))))))))))))))))))))))
which is the required sample complexity.
42


Reviews:
[{"review_id": "phnmzsPDPz", "reviewer": "Reviewer_7HxZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts: \nThe problem setting of testing properties with non-i.i.d. samples across distributions is well-motivated, but the technical contributions of the paper seem to be as incremental The positive results (Theorem1.3 and Corollary1.4) essentially show that known distribution testing algorithms (collision-based $\\ell_2$-statistics) can be adapted to the heterogeneous scenario as long as $c\\ge 2$. The sample complexity achieved matches the classical results in the regime of interest. This is certainly a nice observation, but it might not be viewed as a deep new technique — it is leveraging existing tools (with some variance analysis tweaks). The most novel contribution is the negative result (Theorem 1.5) demonstrating the necessity of using label information (or multiple samples per distribution). Please correct me if I am misunderstanding. That lower bound is quite technically involved and appears to be the main theoretical innovation. \n\nWeaknesses\nThe paper has a number of  minor typographical and presentation issues ( listed below) that detract from its clarity. Clarity issues + suggestions/questions: \n\nThe proof of Theorem1.5 (lower bound for “pooled” estimators) is very intricate, spanning multiple appendices (Appendix D, E, F). While I did not find a specific fatal flaw in the reasoning, the construction and analysis are difficult to parse and verify. For example, the authors construct pairs of distributions with carefully chosen “collisions” properties and then use the Gershgorin circle theorem and “a fact” from Valiant & Valiant to bound the total variation between outcome distributions. I would suggest creating an appendix with such useful “facts” to be included (with refernce ofcourse) within the paper itself to make it self-sufficient. Similarly in Appendix E and F, the authors claim the two constructed sample-output distributions $G_1$ and $G_2$ (corresponding to the two scenarios) have very close fingerprint distributions (frequency count profiles), ultimately within $0.01$ in total variation. The argument relies on showing certain moment or covariance matrices are almost identical (all eigenvalues in $[1-10^{-14},,1+10^{-14}]$ for a matrix difference, etc.). These steps invoke advanced tools (e.g. linear algebraic facts) without much explanation, which should/could be included in the “useful facts” in the additional appendix. It is hard to verify at a glance that all conditions for applying those tools are satisfied. In particular, ensuring that the perturbation bounds (like those from Gershgorin’s theorem) are tight enough to imply the desired $d_TV \\le 0.01$ which requires careful error accounting. the lower bound proof contains no clear mathematical \\emph{error} that I could pinpoint, but its presentation lacks sufficient detail to be easily checkable. This is a concern in terms of completeness and rigor: the authors should consider elaborating the proof (or at least providing a high-level outline in the main text) to convince the reader that each step is valid. \n\nit would be helpful if the authors explicitly clarified in the main text why the Poisson model avoids the impossibility result of Claim 1.2. In particular, the statement “receiving $ Poi(c)$ samples from every distribution is equivalent to receiving $ Poi(cT)$ samples from $p_{avg}$” should be qualified: this equivalence holds in distribution (the pooled sample count from each element of the domain is Poisson with mean $cT p_{avg}}(x)$, by the Poisson superposition property). Thus all tests that depend only on the overall counts cannot distinguish between getting samples in one batch vs. across $T$ groups. This subtle point is essentially left to the reader. While not a flaw, it is a mathematical detail that should be stated for completeness. \n\nI would suggest the author’s claim of O(k^{2/3}/ \\varepsilon^{8/3}) should hold for c=2 should be explicitly marked as a conjecture in the future work. Is there a reason the authors believe this to be true ? Is it because of prior works of Batu et al for two distribution testing?  What are the main obstacles preventing the extension of Theorem1.6 to the case $c=2$? Do the authors think that $\\varepsilon^{-8/3}$ is tight in the non-identical sample setting, or is it an artifact of the proof techniques? In particular, which part of the analysis causes the deterioration from $4/3$ to $8/3$ (for example, is it a union bound over many distributions, a higher moment bound, or something about needing a small success probability to “amplify”)? If one were to attempt to improve the $\\varepsilon$-dependence to match the i.i.d. optimal rate, what modifications to the tester or its analysis might be required? I realize this may not be a direct/easy question to answer and does not reflect upon the paper’s evaluation, I am just curious about this.\n\nThe paper makes it clear that without multiple samples per distribution, one cannot test properties of the average distribution in general. Prior work (Aliakbarpour & Silwal 2019, etc.) got around this by assuming some structure or limited variation in the distributions. Do the authors have insight into what kinds of structural assumptions on $p_i$ could potentially substitute for having $c>1$? For example, if we assume that all $p_i$ are themselves close to $p_{avg}$ (say each $p_i$ is within $\\delta$ in total variation of $p_ {avg}$), could one design a tester for $p_{avg}}$ with $c=1$? Or if all $p_i$ come from a parametric family (like all are Binomial or Zipf distributions with different parameters), would that make uniformity testing feasible with one sample each… do the authors think the lower bound of Claim 1.2 is completely general or if it breaks under natural restrictions … in other words, aside from collecting more samples per source, are there any other reasonable ways to overcome the $c=1$ barrier? Any comments on this would help place the results in context and possibly suggest directions for future work.\n\nMinor:\nAbstract: applies --> apply\nPg 4: “extends” --> extend\n“are are” \n“and and” – appendix \n“for for” –appendix \nTheres two Lemma 4 which seem to be hard-coded since these do not follow the paper’s numbering scheme (Theorem1.3, Corollary1.4, Theorem1.5 … etc)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of \\emph{sublinear-sample distribution property testing} under a relaxation of the usual i.i.d. assumption. Specifically, the authors consider $T$ distinct discrete distributions $p_1,\\dots,p_T$ (each supported on at most $k$ elements) and assume we can draw $c$ independent samples from each $p_i$. The goal is to test properties of the  average distribution $p_{avg} = \\frac{1}{T}\\sum_{i=1}^T p_i$, such as uniformity, identity to a given reference, or the closeness of two sequences of distributions. This setting models practical scenarios with heterogeneous data sources (different users, time periods, etc.) where data are independent but not identically distributed. The paper’s primary contributions are theoretical results characterizing how the sample complexity of property testing depends on the number of samples $c$ per distribution. The theoretical results are stated clearly with conditions (e.g. explicit constants $\\alpha$, regimes for $\\varepsilon$) and seem to be mathematically rigorous and to what I could verify to the best of my ability are correct. The submission provides detailed proofs, adapting techniques from sources like Diakonikolas et al. (collision-based testing) and Goldreich’s reduction for identity testing. The authors acknowledge where their analyses mirror prior proofs (for instance, variance bounds adapted from the i.i.d. case) and where new ideas are needed (such as the pooled-sample lower bound). There is no empirical evaluation which is fine for a theoretical paper.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please fix the (minor) typos, add more clarity so the proofs are easier to read and understand, and if possible clearly state future open directions; more details in the strenghts in weaknesses.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bNUBVqh8hU", "reviewer": "Reviewer_iUE2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Uniformity/Identity/Closeness testing are classical problems in statistical learning. Early work in the area assumed samples are drawn i.i.d from an unknown distribution $p$. Many recent works (both in testing and learning) have looked into relaxing this assumption, typically allowing some sort of light dependence between samples. The authors of this work introduce a new natural model relaxing the identically distributed assumption. They give reasonable motivation for this setting (e.g. testing distributions across spatially separated populations, or chronologically separated…) and essentially characterize when sublinear testing is possible in the model, up to the dependence on the testing error $\\varepsilon$ where they leave the correct polynomial dependence open. Broadly speaking, the paper is also well written and fairly easy to follow (with a few exceptions noted in the requested changes below).\n\nAs the authors say, the main contribution of the work is really the introduction and basic analysis of a new model. At a technical level, most of the results are a straightforward adaptation of the standard collision based methods in the i.i.d uniformity testing setting. The lower bound against algorithms using count statistics does require some new insight and technical work, but the ideas therein are still fairly standard. In and of itself this is not a big weakness (since I do think the model is interesting and worth studying), but its disappointing the authors only study these basic adaptations *and* fail to achieve the right dependence in their bounds, e.g. the dependence 1/eps^4 vs 1/eps^2 (also missing epsilon dependence in some of the lower bounds). The work would be much stronger if the authors were able to give some new ideas beyond those used in the standard i.i.d setting to resolve the barriers they hit in the error dependence using standard techniques. The work could also be made stronger if the authors studied properties beyond testing $p_{avg}$ (which, while natural, does seem like a pretty limited setting), and seems like it may require more new ideas beyond standard techniques from the i.i.d setting.\n\nOverall, the work introduces a nice model relaxing the classical i.i.d assumption and makes progress explaining when sublinear testing is possible largely using known techniques. I think the model is interesting and may inspire followup research, but the work itself would feel `more complete’ if they achieved tighter bounds or introduced more substantially new techniques to handle their introduced relaxation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors initiate the study of uniformity testing (and its variants) over a finite universe [k] with respect to independent but *not identically* distributions $p_1,\\ldots,p_T$. Roughly speaking, the authors show that when only 1 sample is available from each distribution, sublinear property testing is impossible, and testing requires $\\Omega(k)$ samples. On the other hand, as soon as one as at least 2 samples from each $p_i$, it is possible to test in only $O(\\sqrt{k})$ samples, recovering (up to error dependence) classical results from uniformity testing.\n\nIn slightly more detail, the authors are interested in testing whether the *average distribution* $p_{avg}= \\sum\\limits_{I \\in T} p_i$ is uniform or $\\varepsilon$-far from uniform when a fixed number $c$ samples are drawn from each distribution and we think of $T$ (number of distributions) and $k$ (universe size) as growing. \n\nThe authors prove three main results in this setting: first, any uniformity testing algorithm with only $c=1$ samples per distribution requires $T \\geq \\Omega(k)$. Second, there exists an algorithm using only $c=2$ samples per distribution in the sublinear regime, namely whenever $T \\geq \\frac{\\sqrt{k}}{\\varepsilon^2}+\\frac{1}{\\varepsilon^4}$. Finally, any sublinear uniformity testing algorithm must use information about the \"position\" of the samples, i.e. which p_i they came from. In other words, any algorithm which only uses the `fingerprint’ (set of overall counts of each element) and not their positions requires $T \\geq \\Omega(k)$.\n\nThe authors also adapt the standard reduction from identity testing to uniformity testing to show a similar upper bound for the setting of testing whether $p_{avg}$ is close to some fixed distribution $q$ (rather than uniform). Finally, they prove a variant of their upper bound for *closeness testing*, where one is given $c=3$ samples from distributions $p_1,\\ldots,p_T$ and $p’_1,\\ldots,p’_T$ and wishes to test if their averages are $\\varepsilon$-far. In this case they give an algorithm in the sublinear regime whenever $T \\geq k^{2/3}/\\varepsilon^{8/3}$\n\nAt a technical level, the authors adapt the classical method of using collision statistics to measure distance from uniformity. Namely they introduce a basic unbiased estimator for $p_{avg}$ using collisions within each $p_i$ and between $(p_i,p_j)$ pairs and prove the variance is low to show the estimator concentrates sufficiently in sublinear samples. Roughly speaking, this also explains why $c=1$ samples per distribution is insufficient (cannot measure intradistribution collisions), while $c=2$ is sufficient for sublinear testing. A similar argument is used in the closeness testing result, but the authors require an extra sample ($c=3$) in order to separately handle with `heavy’ elements with a standard estimator.\n\nMost of the technical work in the paper actually lies in proving the lower bound against algorithms that just use count statistics. Here the authors construct two sequences of distributions which are far in total variation, but whose count statistics over $c=2$ samples from each distribution are close in total variation. The construction itself is elementary (simply distributing weight among a few different partitions of the universe), but showing the total variation bound requires some work relating the count statistics to discretized gaussians (then comparing the discretized gaussians themselves).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Revision requests:**\n\nThere are several places throughout the work where inconsistent notation is used and/or not defined. For instance, p_a^l is used e.g. in Eq (5) and not defined (this is already bad notation since it could be a power). You later use similar notation to mean something else to denote different distributions, then later in Eq (30), you use p_a(ell) instead to mean the same thing. Please go over your work more carefully and unify the notation used in different sections.\n\n\n**Minor comments:**\n\nWhen you use a period and it is not the end of a sentence, like in i.i.d., you need to “escape” the period in latex by writing ./ . Otherwise you get a double space as is seen in your pdf.\n\nIn Example 1, it’s not really clear what privacy has to do with collecting few samples per user. In fact to ensure privacy you need to do the opposite — collect many samples then add noise.\n\nTypos: “are are that”, “smaller than greater than”, “ours map”, “uniformity random element”, “and and whose”\n\nPg 8: one place bold u_k is used, then just u? Similar, sometimes p(i) is used and sometimes p^I?\n\nBelow Eq (12), dropped subscript on $\\Phi$", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "PQ1PeVlKJK", "reviewer": "Reviewer_incz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of the paper is indeed the new model regarding testing properties of averages of distributions. The authors have motivated it well and it is also a natural generalization of the standard distribution testing. Many of the techniques used are standard. Personally, I think that the lower bound regarding the so-called \"pooled estimators\", i.e., testing in the absence of information about what sample was drawn from what distribution, is quite interesting. \n\nThe following is not really a weakness of the paper. I am curious if the sample complexity of uniformity testing or related problems could be improved if one were to increase $c$. In general, it is worth exploring tradeoffs between $c$ and $T$ for general values of these parameters for various problems.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper initiates a systematic study of learning and testing the average $p_{\\text{avg}}$ of $T$ distributions $p_1, \\dots, p_T$, each supported over a discrete set $[k]$, when given access to samples from the individual distributions. This is a generalization of the standard distribution learning/testing framework where $T = 1$. The paper presents several interesting results in this setting. The questions answered in the paper have the following general flavor: When one receives exactly $c$ samples from each distribution, what are the lower and upper bounds on the number $T$ of distributions whose average can be learned/tested? The results in the paper affirms the intuition that when $c$ is smaller, $T$ needs to be larger. \n\nThe specific results are the following: \n\n(1) If $c = 1$, then $T = \\Theta(k/\\epsilon^2)$ for the problem of learning $p_{\\text{avg}}$ up to a total variation (TV) distance of $\\epsilon$. \n\n(2) If $c = 1$, then $T = \\Omega(k)$ for testing properties of $p_{\\text{avg}}$.\n\n(3) If $c = 2$, then $T = O(\\sqrt{k})$ for uniformity (and identity) testing of $p_{\\text{avg}}$ for constant $\\epsilon$.\n\n(4) If $c = 3$, then for $T = O(k^{2/3})$, one can test closeness of $p_{\\text{avg}}$ and $q_{\\text{avg}}$ for two sequences $p_1, \\dots, p_T$ and $q_1, \\dots, q_T$ of distributions supported over $[k]$.\n\n(5) If one does not have the information regarding which sample is drawn from which distribution, then testing properties of $p_{\\text{avg}}$, in general, requires $T = \\Omega(k)$ even for $c = 2$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think that the paper is quite well-written and have no specific comments here.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)