We analyze the statistical efficiency of the probability density estimation problem when the density function is highly non-smooth. The problem of density estimation appears in various situations, and significantly affects statistics and machine learning. In the existing studies, smoothness of density functions is necessary to measure the statistical efficiency of the estimation. By contrast, the estimation of non-smooth density functions remains an open question, although the non-smooth density functions frequently appear in the application fields. In this paper, we propose a Szemeredi density estimator (SDE) which is an estimator for non-smooth density functions based on graph theory. We derive the speed of convergence of SDE, then clarify the statistical efficiency for the estimation of non-smooth densities. Furthermore, we discuss optimal and adaptive properties of SDE, and experiments to verify the efficiency results of SDE.
This is joint work with Takanori Maehara (RIKEN).