Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms Siu-On Chan Xiaorui Sun Columbia University

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