Concentration Bounds for Discrete Distribution Estimation in KL Divergence

MaRDI QIDQ6426398zbMATH OpenFDO

Authors Clement L. Canonne, Ziteng Sun, Ananda Theertha Suresh

Publication date 14 February 2023

Abstract: 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 $sqrtk/n$ when $ngek$, 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.

This page was built for publication: Concentration Bounds for Discrete Distribution Estimation in KL Divergence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426398)