2015/03/27 by Alon Orlitsky, Orlitsky, Alon, Ananda Theertha Suresh +1 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Imbalanced Data Classification Techniques #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Statistics Theory (math.ST) #cs.DS #cs.IT #cs.LG #math.IT #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.1503.07940
15 pages
arxiv created 2015/03/27 · openalex publication_date 2015/03/27 · arxiv updated 2015/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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,O(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 O(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.