# Testing with Non-identically Distributed Samples

arXiv: https://arxiv.org/abs/2311.11194 · HTML: https://mlsanity.com/paper/2311.11194/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 19 Nov 2023.

## Builds on (most cited first, 11 of 11)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Testing Identity of Structured Distributions](https://mlsanity.com/paper/1410.2266/) (2014)
- [Collision-based Testers are Optimal for Uniformity and Closeness](https://mlsanity.com/paper/1611.03579/) (2016)
- [Learning Discrete Distributions from Untrusted Batches](https://mlsanity.com/paper/1711.08113/) (2017)
- [Maximum Likelihood Estimation for Learning Populations of Parameters](https://mlsanity.com/paper/1902.04553/) (2019)
- [Optimal Robust Learning of Discrete Distributions from Batches](https://mlsanity.com/paper/1911.08532/) (2019)
- [Learning Structured Distributions From Untrusted Batches: Faster and Simpler](https://mlsanity.com/paper/2002.10435/) (2020)
- [Testing Properties of Multiple Distributions with Few Samples](https://mlsanity.com/paper/1911.07324/) (2019)

## Built on by (most cited first, 1 of 1)

- [Non-iid hypothesis testing: from classical to quantum](https://mlsanity.com/paper/2510.06147/) (2025)

## Abstract (arXiv)

We examine the extent to which sublinear-sample property testing and estimation apply 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, p1, p2,ldots,pT, and we obtain c independent draws from each distribution. Suppose the goal is to learn or test a property of the average distribution, pavg. 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/varepsilon2) samples are necessary and sufficient to learn pavg to within error varepsilon in ℓ1 distance. To test uniformity or identity -- distinguishing the case that pavg is equal to some reference distribution, versus has ℓ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 ≥ 2, we recover the usual sublinear sample testing guarantees of the i.i.d. setting: we show that O(√k/varepsilon2 + 1/varepsilon4) total samples are sufficient, matching the optimal sample complexity in the i.i.d. case in the regime where varepsilon ≥ k-1/4. Additionally, we show that in the c=2 case, there is a constant ρ > 0 such that even in the linear regime with ρ k samples, no tester that considers the multiset of samples (ignoring which samples were drawn from the same pi) can perform uniformity testing. We also extend our techniques to the problem of testing "closeness" of two distributions.