Distribution Estimation under the Infinity Norm
<|reference_start|>Distribution Estimation under the Infinity Norm: 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 instance-optimality. Our data-dependent convergence guarantees for the maximum likelihood estimator significantly improve upon the currently known results. A variety of techniques are utilized and innovated upon, including Chernoff-type inequalities and empirical Bernstein bounds. We illustrate our results in synthetic and real-world experiments. Finally, we apply our proposed framework to a basic selective inference problem, where we estimate the most frequent probabilities in a sample.<|reference_end|>
@article{kontorovich2024distribution,
    title={Distribution Estimation under the Infinity Norm},
    author={Aryeh Kontorovich and Amichai Painsky},
    journal={arXiv preprint arXiv:2402.08422},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08422},
    primaryClass={math.ST cs.LG stat.TH}
}