Improved Distribution Estimation in $\ell_\infty$

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.

Estimating a probability distribution from samples is a basic task in machine learning and statistics, but many applications need control of the largest error on any single outcome, not just average error. We prove improved guarantees for this largest-error setting, including worst-case bounds and high-probability bounds. We also give a fully data-based confidence bound that can be computed from the observed samples, and show that a simple two-outcome distribution is essentially the hardest case. These results make sharp theory more practical and clarify when estimation is difficult because of rare outcomes in the tail of the distribution.