Distribution Estimation under the Infinity Norm
This work addresses a fundamental statistical estimation problem with applications in selective inference, though it appears to be an incremental improvement on existing methods.
The paper tackles the problem of estimating discrete probability distributions under the ℓ∞ norm, presenting novel bounds that are nearly optimal and significantly improve upon existing results for the maximum likelihood estimator.
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.