Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms

Siu-On Chan, Ilias Diakonikolas, Rocco A. Servedio +1

Let $p$ be an unknown and arbitrary probability distribution over $[0,1)$. We consider the problem of {\em density estimation}, in which a learning algorithm is given i.i.d. draws…