Improved Distribution Estimation in $\ell_\infty$
This work provides theoretical improvements in distribution estimation for researchers working on statistical learning theory, resolving specific open problems in the field.
This paper improves bounds for estimating discrete probability distributions under the $\\ell_\\infty$ norm, providing minimax bounds in expectation and high-probability tail bounds. It resolves open questions from Kontorovich and Painsky (JMLR, 2025), including a fully empirical version of their tightest risk bound and identifying the worst-case extremal distribution.
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.