# Sharp Constants in Uniformity Testing via the Huber Statistic

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 21 Jun 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [Optimal Identity Testing with High Probability](https://mlsanity.com/paper/1708.02728/) (2017)
- [Collision-based Testers are Optimal for Uniformity and Closeness](https://mlsanity.com/paper/1611.03579/) (2016)
- [Optimal Testing of Discrete Distributions with High Probability](https://mlsanity.com/paper/2009.06540/) (2020)
- [BPTree: an ℓ2 heavy hitters algorithm using constant memory](https://mlsanity.com/paper/1603.00759/) (2016)
- [Generalized Uniformity Testing](https://mlsanity.com/paper/1708.04696/) (2017)
- [Sharp Bounds for Generalized Uniformity Testing](https://mlsanity.com/paper/1709.02087/) (2017)
- [New Cardinality Estimation Methods for HyperLogLog Sketches](https://mlsanity.com/paper/1706.07290/) (2017)
- [Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm](https://mlsanity.com/paper/1708.06839/) (2017)
- [Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon](https://mlsanity.com/paper/2007.08051/) (2020)

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

- [The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternatives](https://mlsanity.com/paper/2305.18111/) (2023)

## Abstract (arXiv)

Uniformity testing is one of the most well-studied problems in property testing, with many known test statistics, including ones based on counting collisions, singletons, and the empirical TV distance. It is known that the optimal sample complexity to distinguish the uniform distribution on m elements from any ε-far distribution with 1-δ probability is n = Thetaleft(frac√m log (1/δ)ε2 + fraclog (1/δ)ε2right), which is achieved by the empirical TV tester. Yet in simulation, these theoretical analyses are misleading: in many cases, they do not correctly rank order the performance of existing testers, even in an asymptotic regime of all parameters tending to 0 or ∞. We explain this discrepancy by studying the constant factors required by the algorithms. We show that the collisions tester achieves a sharp maximal constant in the number of standard deviations of separation between uniform and non-uniform inputs. We then introduce a new tester based on the Huber loss, and show that it not only matches this separation, but also has tails corresponding to a Gaussian with this separation. This leads to a sample complexity of (1 + o(1))frac√m log (1/δ)ε2 in the regime where this term is dominant, unlike all other existing testers.