# Competitive Distribution Estimation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2015.

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

- [Conformal Prediction Beyond the Seen: A Missing Mass Perspective for Uncertainty Quantification in Generative Models](https://mlsanity.com/paper/2506.05497/) (2025)

## Abstract (arXiv)

Estimating an unknown distribution from its samples is a fundamental problem in statistics. The common, min-max, formulation of this goal considers the performance of the best estimator over all distributions in a class. It shows that with n samples, distributions over k symbols can be learned to a KL divergence that decreases to zero with the sample size n, but grows unboundedly with the alphabet size k. Min-max performance can be viewed as regret relative to an oracle that knows the underlying distribution. We consider two natural and modest limits on the oracle's power. One where it knows the underlying distribution only up to symbol permutations, and the other where it knows the exact distribution but is restricted to use natural estimators that assign the same probability to symbols that appeared equally many times in the sample. We show that in both cases the competitive regret reduces to min(k/n,tildeO(1/√ n)), a quantity upper bounded uniformly for every alphabet size. This shows that distributions can be estimated nearly as well as when they are essentially known in advance, and nearly as well as when they are completely known in advance but need to be estimated via a natural estimator. We also provide an estimator that runs in linear time and incurs competitive regret of tildeO(min(k/n,1/√ n)), and show that for natural estimators this competitive regret is inevitable. We also demonstrate the effectiveness of competitive estimators using simulations.