Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation
Estimators of information theoretic measures such as entropy and mutual information are a basic workhorse for many downstream applications in modern data science. State of the art approaches have been either geometric (nearest neighbor (NN) based) or kernel based (with a globally chosen bandwidth). In this paper, we combine both these approaches to design new estimators of entropy and mutual information that outperform state of the art methods. Our estimator uses local bandwidth choices of k-NN distances with a finite k, independent of the sample size. Such a local and data dependent choice improves performance in practice, but the bandwidth is vanishing at a fast rate, leading to a non-vanishing bias. We show that the asymptotic bias of the proposed estimator is universal; it is independent of the underlying distribution. Hence, it can be precomputed and subtracted from the estimate. As a byproduct, we obtain a unified way of obtaining both kernel and NN estimators. The corresponding theoretical contribution relating the asymptotic geometry of nearest neighbors to order statistics is of independent mathematical interest.
The authors propose a new class of estimators for Shannon entropy (and Mutual Information (MI)). The estimators are density plug-in estimators based on the empirical average of the log of density estimates at points drawn from the underlying distribution. For density estimation, the authors use local likelihood density estimators (LLDE’s), which are higher-order generalizations of KDE and kNN density estimators.
The most potentially novel contribution of the paper is the discussion in section 6 where the authors show how adaptive bandwidths (i.e. k-nn) can be superior to fixed bandwidth (i.e. bandwidth is the same at all points). However, the discussion focuses on Shannon entropy only. If the results in this discussion can be applied to other distributional functionals (e.g. Renyi entropy and others), then it is indeed very novel. However, if it only applies to Shannon entropy, then it is quite limited. This similarly applies to all of the contributions. The authors should comment on the feasibility of extending these results to other distributional functionals. This is critical as all current state of the art estimators focus on more than just Shannon entropy.  Another contribution of the paper is the result that the empirical average converges to the true entropy plus a constant term B(k,p,d, K) that is independent of the underlying distribution for any choice of kernel K, order p, and parameter k. If the term B(k,p,d) were to be distribution-dependent, then typically k is required to go to infinity (but at a slower rate compared to n) in order to ensure convergence, which results in slower rates of convergence. But because the authors show that B(k,p,d) is independent of the underlying density, they can estimate this quantity using Monte-Carlo methods, and subtract this constant term from their empirical average to derive an estimator that converges to the true entropy even with k fixed. Results of this form have been established before for specific choices of kernel K and order p. For example, in [6], the result is established for p = 0 and the choice of a step kernel. This paper shows that [6] (and other estimators) are a special case of this very general result they have derived, which is a nice result.  Of course, this raises the question as to what the advantages are with using a estimator with different choice of kernel and higher values of p are relative to the existing estimators which correspond to p = 0. The authors claim that the advantage is that the finite sample performance of higher-order estimators is better, and mainly because they do better at the edges of the support of the density, where the higher order density estimators have lower bias by virtue of adapting to the contours of the distribution (see figure 1). They present experimental results, (but no theoretical results), and claim that the higher order estimators have better finite sample MSE compared to [6].  These are some of the issues with the paper:  1- In Section 2, the authors claim that higher order LLDE’s automatically correct for boundary bias. Do they mean that boundary bias is completely eliminated by using LLDE’s? Or do they mean that LLDE’s do a better job of accounting for some of the boundary bias but still do not completely eliminate it? If it is the former, then this is a very strong claim and the analysis in Section 2 does not convince me this is true. For instance, for samples drawn from a distribution with compact support, I believe the density estimates for points on the boundary of the support would be underestimated irrespective of the order of the LLDE. If it is the later, the authors should make this more clear in Section 2. 1.1- On a related note, figure 1(b) helps readers visualize a standard k-NN density estimate and understand why it suffers from boundary bias. But there is no illustration of the LLDE density estimator in this figure. Addition of this illustration would greatly hep readers get a sense for why LLDE’s better account for the boundary bias.  2- The flip side to using LLDE’s of higher order is that they are more expensive to implement. The authors attempt to address this by using subsets of samples for evaluating equation (10). It would be interesting to compare the computation time for lower order kernels like the one in [6] against the higher-order kernels to see what the trade-off is between MSE performance and computation time.  3-The simulations have some major flaws. The authors claim that their estimator outperforms the state of the art estimators. This claim is far too strong. First, they only compare to one state of the art estimator [5] and completely neglect the other state of the art estimators (in terms of MSE convergence rate), most especially ensemble methods (see [5R,6R] below).  Another state of the art estimator is included in [11R]. I am also not convinced that the authors implemented the Von mises estimator of [5] correctly as the MSE is nonmonotonic as the sample size increases in Figure 2. How did the authors choose the bandwidth and what kernel did they use? The authors should provide more details on these experiments. Also, in figure 2(b), the rate at which the MSE of the KL estimator is decreasing in sample size is much faster than the rate at which the p=2 LNN estimator’s MSE is decreasing. If the figure were extrapolated beyond n=1500 samples, it seems like the KL estimator would start to outperform the LNN estimator. Figure 3(b) seems to convey a similar story that the small sample performance of the LNN-KSG estimator is much better compared to the standard KSG, but again it is not clear that the rate of convergence of LNN-KSG is better than KSG. This is a critical issue that must be studied more carefully, especially given that the results presented are asymptotic convergence results and not finite sample analysis results. Finally, the authors only focus on the very low dimensional case. I suspect that in the higher dimensional setting, the state of the art estimators would outperform the proposed estimator which limits its applicability.  4- In addition to the KL and von-moses estimators for entropy, the KSG estimator for MI, and the estimators mentioned above, there are several other estimators in literature for these quantities that are important and have been neglected by the author. See the references below. Some if not all of these references should be included, especially those with known convergence rates.  5- Although the paper in its current form makes significant theoretical contributions, it would definitely be of interest to extend the results to obtain theoretical results that describe finite sample performance of these estimators (or equivalently, obtain the rate of convergence of the estimators). For instance, see [3R, 5R, 6R, 7R, 11R], where rates of convergence are obtained for various entropy and MI estimators. See also [12R] where the convergence rates of the KL estimator are derived.  6- In this paper, results are derived only for estimation of Shannon entropy and MI. As mentioned above, estimators for other forms of entropy and MI are also of interest.  6.1- For instance, see [7R, 8R, 9R] for work on Renyi entropy and divergence estimation. It would be useful to investigate if similar results to the ones derived in this paper hold for these Renyi measures. It has already been shown in [9R] that a bias correction term exists for Renyi entropy estimators (the factor C_k in section 3.1 in [9R]) - does a similar term exist for higher order  LLDE’s?  6.2-In addition to Renyi estimators, there has also been work on estimation of general functionals of densities - see [3R, 5R, 10R, 11R]. To the best of my knowledge, there has been no work on establishing that bias correction factors exist for estimators of these general functionals, and as a result, density plug-in estimators require that k also grow to infinity. It would be very interesting to see if the authors could extend their analysis to estimators for general functionals other than log(x)  (Shannon) and x^{a-1} (Renyi), and comment on whether bias correction factors exist for estimators of these general functionals.   6.3- This reviewer would be interested in hearing the authors take on whether they think their analysis is general enough to accommodate these more general functionals, and if not, if they could comment on what makes the log(.) function critical to their analysis.  In summary, I would not expect the authors to address all of these issues in the rebuttal. At a minimum, I would expect the authors to 1) address the issues wrt the boundary bias; 2) Provide more details on the experiments, especially when implementing the Von Mises estimator; 3) Either soften their language with regards to the experimental results (i.e. recognize that their approach only outperforms one state of the art estimator in rather limited circumstances and at lower dimensions) OR compare their estimator to other state of the art estimators and at higher dimensions; 4) Include at least the references where convergence rates are known; 5) Comment on the feasibility of extending this work to more general functionals.   If these issues are addressed, then I would recommend the paper be accepted for publication at NIPS. If any of the other issues are addressed, the paper would be even stronger.    Additional references:  [1R] Pál, Dávid, Barnabás Póczos, and Csaba Szepesvári. "Estimation of Rényi entropy and mutual information based on generalized nearest-neighbor graphs." Advances in Neural Information Processing Systems. 2010. [2R] Beirlant, Jan, et al. "Nonparametric entropy estimation: An overview."International Journal of Mathematical and Statistical Sciences 6.1 (1997): 17-39. [3R] Estimating divergence functionals and the likelihood ratio by convex risk minimization XL Nguyen, MJ Wainwright, MI Jordan - IEEE Transactions on Information Theory, 2010 [4R] Póczos, Barnabás, Liang Xiong, and Jeff Schneider. "Nonparametric divergence estimation with applications to machine learning on distributions."arXiv preprint arXiv:1202.3758 (2012). [5R] Moon, Kevin, and Alfred Hero. "Multivariate f-divergence estimation with confidence." Advances in Neural Information Processing Systems. 2014. [6R] Sricharan, Kumar, Dennis Wei, and Alfred O. Hero. "Ensemble estimators for multivariate entropy estimation." IEEE Transactions on Information Theory59.7 (2013): 4374-4388. [7R] Krishnamurthy, Akshay, et al. "Nonparametric Estimation of Renyi Divergence and Friends." ICML. 2014. [8R] Hero, Alfred O., et al. "Applications of entropic spanning graphs." IEEE signal processing magazine 19.5 (2002): 85-95. [9R] Leonenko, N., L. Prozanto, and V. Savani (2008), A class of r´enyi information estimators for multidimensional densities, Annals of Statistics, 36, 2153–2182. [10R] Sricharan, Kumar, Raviv Raich, and Alfred O. Hero. "Estimation of nonlinear functionals of densities with confidence." IEEE Transactions on Information Theory 58.7 (2012): 4135-4159. [11R] Singh and Poczos, "Exponential Concentration Inequality of a Density Functional Estimator," NIPS 2014. [12R] Biau and Devroye, "Entropy Estimation," In Lectures on the Nearest Neighbor Method," pp 75-91, Springer, 2015.  EDIT: Based on the comments of other reviewers, I have downgraded my score for the novelty of this paper. I think that the novelty of theorems 1 and 2 is sufficient to maintain the score at a "3". However, I think that the authors should give more reference to prior work in the other less novel results as Reviewer 4 discussed. I think that this and toning down their claims on the experiments is critical (as well as referencing more prior work in general).  Some of the other issues brought up by the other reviewers also lead me to leave the technical quality at a "2". These issues further seem to suggest that the authors' approach is mostly limited to Shannon entropy. If the authors had shown broader applicability to other functionals, I would have looked more favorably upon the paper despite these issues.