# Distribution Estimation under the Infinity Norm

arXiv: https://arxiv.org/abs/2402.08422 · HTML: https://mlsanity.com/paper/2402.08422/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2024.

## Built on by (most cited first, 2 of 2)

- [Near Optimal Inference for the Best-Performing Algorithm](https://mlsanity.com/paper/2508.05173/) (2025)
- [Improved Distribution Estimation in ℓ_∞](https://mlsanity.com/paper/2605.30509/) (2026)

## Abstract (arXiv)

We present novel bounds for estimating discrete probability distributions under the ℓ_∞ 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.