Instance-Optimality for Private KL Distribution Estimation

Jiayuan Ye, Vitaly Feldman, Kunal Talwar

We study the fundamental problem of estimating an unknown discrete distribution $p$ over $d$ symbols, given $n$ i.i.d. samples from the distribution. We are interested in minimizin…