ICML 2026poster0 citations
Improved Distribution Estimation in $\ell_\infty$
Doron Cohen, Aryeh Kontorovich, Yonatan Livshitz
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.
TheoryRetrieval
BibTeX
@inproceedings{
cohen2026improved,
title={Improved Distribution Estimation in \${\textbackslash}ell\_{\textbackslash}infty\$},
author={Doron Cohen and Aryeh Kontorovich and Yonatan Livshitz},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=wwqrH4mwGq}
}