Concentration Bounds for Discrete Distribution Estimation in KL Divergence
This work addresses a fundamental problem in statistics and machine learning for distribution estimation, offering improved theoretical guarantees with practical implications for data analysis.
The paper tackles the problem of estimating discrete distributions in KL divergence by providing concentration bounds for the Laplace estimator, showing that deviation scales as √k/n for n ≥ k, improving upon prior results of k/n, and establishing a matching lower bound to prove tightness up to polylog factors.
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 $\sqrt{k}/n$ when $n \ge 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.