Distribution Estimation under the Infinity Norm

Aryeh Kontorovich, Amichai Painsky

We present novel bounds for estimating discrete probability distributions under the ${\ell }_{\infty }$ norm. These are nearly optimal in various precise senses, including a kind of inst…