Finite-Sample Analysis of Fixed-k Nearest Neighbor Density Functional Estimators
We provide finite-sample analysis of a general framework for using k-nearest neighbor statistics to estimate functionals of a nonparametric continuous probability density, including entropies and divergences. Rather than plugging a consistent density estimate (which requires k → ∞ as the sample size n → ∞) into the functional of interest, the estimators we consider fix k and perform a bias correction. This is more efficient computationally, and, as we show in certain cases, statistically, leading to faster convergence rates. Our framework unifies several previous estimators, for most of which ours are the first finite sample guarantees.
The paper gives a finite sample analysis (bias and variance bounds) for a framework of nonparametric methods, estimating functionals of densities (such as divergences and entropies) by plugging in a k-nearest neighbor density estimate and taking a sample average. The interesting property of the methods being analyzed is that instead of increasing k with the sample size-- which leads to consistent density estimates-- k is fixed. The implication of considering fixed k is that the variance of the density estimate does not go to zero asymptotically.   The non vanishing variance in the density estimate manifests as bias in the estimate of the functional. The methods being considered do some correction to obtain an asymptotically unbiased estimator. The variance of the functional estimate is asymptotically 0, in spite of the non vanishing variance of the density estimate, because of a sample averaging.   The paper derives finite sample bounds for the bias and the variance of such methods under certain weak assumptions on the underlying density.  The paper argues that the bounds are superior to most of the state of art approaches and those approaches that might have better convergence are computationally too demanding, concluding that the fixed-k approach with bias correction gives competitive convergence with significant computational advantage.   
Congratulations to the authors for their excellent work.   Quality: This is a high quality paper with significant theory and sophisticated math. The claims of the paper are well supported by the derived error bounds, though, I have a some concerns about the math at a couple of places (see under Concerns). The authors have clearly stated the assumptions under which the bounds apply and have given an objective comparison of their work with previously known results.  Clarity: Overall the paper is very well written and reads easily. The authors have provided intuition which makes it easy to follow the math. The assumptions are very well motivated and discussed. Though there are some formatting issues, typos and notation reuse.   Originality: The error bounds proved in the paper are novel. The proofs are non trivial and interesting. The authors have done an exceptional job of discussing the related work.   Significance: The problem of estimating functionals of densities is very important in several machine learning and statistics problems. The competitive error bounds derived in the paper and the computational advantage of fixed-k nearest neighbor based methods  justify using them for estimation.   Main concern: As I understand, the argument used to apply lemma 4 to derive bounds on $E[f(\epsilon_k(x))]$, is that $f(\epsilon_k(x))$ can be expressed as $f(h(z))$ where $z=\frac{p_*(x)}{\hat{p}_k(x)}$ and h(z)=(\frac{kz}{cnp_*(x)})^{1/D}, and $f o h$ is an increasing function.  However, the definition of $h$ is not independent of z; its definition changes with its argument $z$ because it contains $p_*(x)$ as well in the denominator. In this light, it is not straightforward how lemma 4 can be applied.   The appendix version of lemma 4 seems to derive the bounds on $E[f(\epsilon_k(x))]$ directly. The proof starts with defining $g$, but never uses it. Also, it might be better to have the same result in the appendix and the main paper or lemma with a detailed proof should be added to derive one from the other.  (Line 236) Expression for C_f when f(x)=log(x) is given. It seems like the M_{f,p}(x) is evaluated to be 1. However, I do not see how it can be a constant. Also the expectation should be with respect to p, but the integral is with respect to the borel measure.  In lemma 4, line 218 says that the inequality 7 is a lower bound, however, it is actually an upper bound. Also upper bound for E(f)  =E(f_+)-E(f_-) cannot be derived with <= in 7.  From the expression for the variance bound (line 254), it seems that the upper bound increases with k, instead of decreasing as one would expect.    Minor comments: There are some typos below Theorem 5: line 233 M_{f,o}, Equation below line 233 the second term should be E w.r.t q, not p.  Line 232 gives the impression that q and p should have the same L, it might be better to have L_1, L_2.   Before line 235, it would be good to have expression for the bias bounds for functionals of p and q and perhaps a lemma in the appendix.   Notation reuse: r is used as the exponent in the norm as well as the radius of the ball.  It would be good to include proofs that  all the functionals in table 1 satisfy the assumptions of the theorems.   The intuition provided in line 208 about asymmetry and bias is not is not obvious.  Line 274 about testing problems is difficult to parse.  Overall, I recommend accepting the paper if they address my concerns.  After author's response: The authors have responded to my concerns satisfactorily. Though, I would like to suggest them to add few technical comments to Lemma 4 and Theorem 5 for more clarity.