Seminar: The Jacob Ziv Communication and Information Theory seminar
The Minimax Risk in Uniformity Testing under Missing Ball Alternatives
Date:
March,28,2024
Start Time:
14:30 - 15:30
Location:
1061, Meyer Building
Zoom:
Zoom link
Add to:
Lecturer:
Alon Kipnis
Research Areas:
| We study the problem of testing the goodness of fit of occurrences of items from many categories to an identical Poisson distribution over the categories. This problem is intimately related to “uniformity testing” in a multinomial model. As a class of alternative hypotheses, we consider the removal of an $\ell_p$ ball of radius $\epsilon$ around the uniform rate sequence for $p \leq 2$ within a hypercube. When the number of samples $n$ and number of categories $N$ go to infinity while $\epsilon$ is small, the minimax risk $R_\epsilon^*$ asymptotes to $2\Phi(-n N^{2-2/p} \epsilon^2/\sqrt{8N})$; $\Phi(x)$ is the normal CDF. As it turns out, the minimax test relies on collisions in the very small sample limit but otherwise behaves like the chisquared test. Empirical studies over a range of problem parameters show that our estimate is accurate in finite samples and that the minimax test is significantly better than the chisquared test or a test that only uses collisions.
Our result settles several known challenges in uniformity and “identity” testing from the last two decades. In particular, it allows the comparison of the many estimators previously proposed for this problem at the constant level rather than at the rate of convergence of the risk or the scaling order of the sample complexity. Our analysis introduces several new methods by adapting techniques previously used by Ingster and Suslina for Gaussian signal detection. |
| Alon Kipnis is a Senior Lecturer at the Efi Arzi School of Computer Science at Reichman University. He received his B.Sc. degree in mathematics (summa cum laude) and his B.Sc. degree in electrical engineering (summa cum laude), both in 2010, and his M.Sc. degree in mathematics in 2012, all from Ben-Gurion University of the Negev. He received his Ph.D. degree in electrical engineering from Stanford University in 2017. Between 2017-2021, he was a postdoctoral research fellow and a lecturer in the Department of Statistics at Stanford University, hosted by David Donoho and funded by the Koret Foundation. His research interests include mathematical statistics and information theory.
|