Analysis of KNN Density Estimation
This work provides theoretical guarantees for kNN density estimation, addressing convergence issues in statistical learning, but it is incremental as it builds on existing analysis frameworks.
The paper analyzes the convergence rates of k-nearest neighbor (kNN) density estimation under ℓ₁ and ℓ∞ criteria, showing minimax optimality for bounded support with known boundaries and near-optimal ℓ∞ error for unbounded smooth densities, with ℓ₁ error outperforming kernel 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.