Analysis of KNN Density Estimation
  We analyze the $\ell_1$ and $\ell_\infty$ convergence rates of k nearest
neighbor density estimation method. Our analysis includes two different cases
depending on whether the support set is bounded or not. In the first case, the
probability density function has a bounded support and is bounded away from
zero. We show that kNN density estimation is minimax optimal under both
$\ell_1$ and $\ell_\infty$ criteria, if the support set is known. If the
support set is unknown, then the convergence rate of $\ell_1$ error is not
affected, while $\ell_\infty$ error does not converge. In the second case, the
probability density function can approach zero and is smooth everywhere.
Moreover, the Hessian is assumed to decay with the density values. For this
case, our result shows that the $\ell_\infty$ error of kNN density estimation
is nearly minimax optimal. The $\ell_1$ error does not reach the minimax lower
bound, but is better than kernel density estimation.
