# The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternatives

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 60 references that are in the map.
- First posted on arXiv 29 May 2023.

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

- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [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)
- [Hypothesis Testing For Densities and High-Dimensional Multinomials: Sharp Local Minimax Rates](https://mlsanity.com/paper/1706.10003/) (2017)
- [Hypothesis Testing for High-Dimensional Multinomials: A Selective Review](https://mlsanity.com/paper/1712.06120/) (2017)
- [ℓp Testing and Learning of Discrete Distributions](https://mlsanity.com/paper/1412.2314/) (2014)
- [Sharp Constants in Uniformity Testing via the Huber Statistic](https://mlsanity.com/paper/2206.10722/) (2022)

## Abstract (arXiv)

We study the problem of testing the goodness of fit of categorical count data to a Poisson distribution uniform over the categories, against a class of alternatives defined by excluding an ℓp ball, p ≤ 2, of radius ε around the uniform rate sequence. We characterize the minimax risk for this problem as the expected number of samples n and the number of categories N go to infinity. Our result enables constant-factor comparisons among the many estimators previously proposed for this problem, rather than comparisons only at the level of convergence rates or scaling orders of sample complexity. The minimax test relies exclusively on collisions in the small sample limit, but behaves like the chi-squared test otherwise. Empirical studies across a range of parameters show that the asymptotic risk estimate is accurate in finite samples, and that the minimax test outperforms both the chi-squared test and a test based on collisions under the least favorable alternative. Our analysis involves a reduction to a structured subset of alternatives, establishing uniform asymptotic normality for a family of linear test statistics, and solving an optimization problem over N-dimensional sequences akin to classical results from signal detection in Gaussian white noise. Finally, we discuss the connection to the fixed-sample-size multinomial model, arguing that the Poisson minimax risk derived here also characterizes the minimax risk of the multinomial problem.