Title: The Sharp Minimax Risk for High-Dimensional Uniformity Testing and Applications to Model Calibration
Abstract: Testing whether high-dimensional categorical data follow a specified distribution is a fundamental problem in statistics, learning, and theoretical computer science. We derive an expression for the asymptotic minimax risk in terms of the number of categories, the sample size, and the separation between the alternative class and the uniform distribution null. This result settles an open problem related to identity and uniformity testing in computer science and nonparametric hypothesis testing on distributions in mathematical statistics.
Abstract: Testing whether high-dimensional categorical data follow a specified distribution is a fundamental problem in statistics, learning, and theoretical computer science. We derive an expression for the asymptotic minimax risk in terms of the number of categories, the sample size, and the separation between the alternative class and the uniform distribution null. This result settles an open problem related to identity and uniformity testing in computer science and nonparametric hypothesis testing on distributions in mathematical statistics.
The sharp characterization enables comparison among competing tests at the level of exact constants rather than asymptotic rates, revealing differences invisible under standard sample-complexity analyses. Interestingly, commonly used chi-squared and collision statistics are asymptotically minimax under fixed sample sizes but fail to retain this property under Poisson sampling. We derive a new statistic that is asymptotically minimax in both settings. The proof combines ideas from signal detection in white noise with a new conditional central limit theorem that overcomes the de-Poissonization challenge.
As a practical consequence, the sharp constant answers a longstanding design question in calibration testing:
How many bins should one use when testing calibration using the probability integral transform?
We derive an explicit formula for the largest number of bins that guarantees a prescribed minimax risk, replacing heuristic bin selection by a statistically optimal design rule.
This talk is partly based on the following work, which received the best non-student paper award in an AISTATS 2026 workshop.
A. Kipnis, "Calibrating the Calibration Tester: Optimal Binning and Minimax Calibration Testing for Continuous Predictive Models", Towards Trustworthy Predictions: Theory and Applications of Calibration for Modern AI @ AISTATS 2026 (https://openreview.net/forum?id=dy7XNC3W0g)
Bio: Alon Kipnis is a Senior Lecturer (Assistant Professor) at the Efi Arazi School of Computer Science, Reichman University, Israel. He received the Ph.D. in Electrical Engineering from Stanford University in 2017, and was a Koret Foundation Postdoctoral Fellow in Statistics at Stanford University from 2018 to 2021. His research focuses on mathematical statistics, information theory, signal processing, and machine learning.