Optimal rates for k-NN density and mode estimation
We present two related contributions of independent interest: (1) high-probability finite sample rates for k-NN density estimation, and (2) practical mode estimators -based on k-NN -which attain minimax-optimal rates under surprisingly general distributional conditions.
This paper presents a finite-sample analysis of k-NN density estimation. The paper begins by establishing uniform high-probability bounds for sup_{x \in R^d} | fk(x) - f(x) |, where fk(x) is the density estimate and f(x) the true density. The paper then uses this result to show that k-NN density estimation induces mode estimates that converge at an optimal rate.I enjoyed reading this paper, and found it to be clearly written. The technical development was well explained, making it possible to get a good feel for the main ideas used in the proof. The theoretical results also seem useful and relevant.Minor comments:- In Section 2.1, do any of the prior bounds hold simultaneously for all x in Rd? If not, it might be worth emphasizing this.- Lemma 2, I'm not sure \mathcal{F} has been defined.- Is there a reason lemmas 3 and 4 are not combined into a single result? To me, these two lemmas together form one of the most important results in the paper; I think if it were called a theorem it would be easier for the casual reader to take note.- On line 319, you say that "A_{x_0} is a level set." It is not clear to me that this is true given the assumptions made? Unless I'm missing something, you did not assume f(x) to be continuous outside of Ax0, so f(x') could get arbitrarily close to f(x0) for some x' that is far from x0.- The notation S + B(0, r) in Definition 6 should be defined.- Finally, the expressions "e.g." and "i.e." need to be surrounded by commas on both sides, e.g., like just there.