Improved Distribution Estimation in ${\ell }_{\infty }$

Abstract

We present improved bounds for estimating discrete probability distributions under the ${\ell }_{\infty }$ norm. These include minimax bounds in expectation and high-probability tail bounds. We resolve some of the open questions posed in Kontorovich and Painsky (JMLR, 2025) -- including a fully empirical version of the tightest risk bound they presented and identifying the form of the worst-case extremal distribution. Encouraging empirical results are reported as well.

24 pages, 3 figures