2023/02/14 by Clément L. Canonne, Canonne, Clément L., Ziteng Sun +3 · 1 citation
Computer Science · Mathematics · #Advanced Statistical Methods and Models #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Probability (math.PR) #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2302.06869
openalex publication_date 2023/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of discrete distribution estimation in KL divergence and provide concentration bounds for the Laplace estimator. We show that the deviation from mean scales as √(k)/n when n ≥ k, improving upon the best prior result of k/n. We also establish a matching lower bound that shows that our bounds are tight up to polylogarithmic factors.