The Nearest Neighbor Information Estimator is Adaptively Near Minimax Rate-Optimal
We analyze the Kozachenko-Leonenko (KL) fixed k-nearest neighbor estimator for the differential entropy. We obtain the first uniform upper bound on its performance for any fixed k over Hölder balls on a torus without assuming any conditions on how close the density could be from zero. Accompanying a recent minimax lower bound over the Hölder ball, we show that the KL estimator for any fixed k is achieving the minimax rates up to logarithmic factors without cognizance of the smoothness parameter s of the Hölder ball for s ∈ (0, 2] and arbitrary dimension d, rendering it the first estimator that provably satisfies this property.
Paper 1614  This paper studies the Kozachenko-Leonenko estimator for the differential entropy of a multivariate smooth density that satisfy a periodic boundary condition; an equivalent way to state the condition is to let the density be defined on the [0,1]^d-torus. The authors show that the K-L estimator achieves a rate of convergence that is optimal up to poly-log factors.   The result is interesting and the paper is well-written. I could not check the entirety of the proof but the parts I checked are correct. I recommend that the paper be accepted.   Some questions and remarks:  * The periodic boundary condition is unnatural, though one can imagine that the problem is much harder without it. Can the authors comment on whether anything can be shown for densities over R^d?  * Can the weighted KL estimator proposed in [1] be used to control the bias and handle cases where s > 2 ?   * It seems that the Besicovitch (typo on line 99) covering lemma implies the Hardy-Littlewood maximal inequality. I only see the variance bound use the former so perhaps the latter result need not be mentioned. On an unrelated note, I am curious whether the authors know what the dependence of the C_d constant on dimensionality d is in the Besicovitch covering lemma.   * Can similar estimator and analysis be used for estimating the Renyi entropy?  [1] T. Berrett, R. Samworth, and M. Yuan, Efficient multivariate entropy estimation via nearest k-neighbor estimators.