Exponential Concentration of a Density Functional Estimator
We analyze a plug-in estimator for a large class of integral functionals of one or more continuous probability densities. This class includes important families of entropy, divergence, mutual information, and their conditional versions. For densities on the d-dimensional unit cube [0,1] d that lie in a β-Hölder smoothness class, we prove our estimator converges at the rate O n − β β+d . Furthermore, we prove the estimator is exponentially concentrated about its mean, whereas most previous related results have proven only expected error bounds on estimators.
α → 1 limit case), and L p divergence. Divergence estimators can be used to extend machine learning algorithms for regression, classification, and clustering from the standard setting where inputs are finite-dimensional feature vectors to settings where inputs are sets or distributions [22,18]. Entropy and mutual information (MI) can be estimated as special cases of divergences. Entropy estimators are used in goodness-of-fit testing [5], parameter estimation in semi-parametric models [33], and texture classification [6], and MI estimators are used in feature selection [20], clustering [1], optimal experimental design [13], and boosting and facial expression recognition [25]. Both entropy and mutual information estimators are used in independent component and subspace analysis [10,29] and image registration [6]. Further applications of divergence estimation are in [11].
Despite the practical utility of density functional estimators, little is known about their statistical performance, especially for functionals of more than one density. In particular, few density functional estimators have known convergence rates, and, to the best of our knowledge, no finite sample exponential concentration bounds have been derived for general density functional estimators. One consequence of this exponential bound is that, using a union bound, we can guarantee accuracy of multiple estimates simultaneously. For example, [14] shows how this can be applied to optimally analyze forest density estimation algorithms. Because the CMI of variables X and Y given a third variable Z is zero if and only X and Y are conditionally independent given Z, by estimating CMI with a confidence interval, we can test for conditional independence with bounded type I error probabilty.
Our main contribution is to derive convergence rates and an exponential concentration inequality for a particular, consistent, nonparametric estimator for large class of density functionals, including conditional density functionals. We also apply our concentration inequality to the important case of Rényi-α CMI.
QUALITYThe results are interesting, relevant for practice (e.g. for designing conditional mutual independence tests) and the technical development is o.k. as far as I could check. I do have two issues though (one which is related to the 'as far as I could check' - there are various unclarities in the math part of the paper, see below).(1) you claim that your results can be applied to Renyi and hence KL divergences, but these are *not* of the form (3) because p_1 and p_2 are defined on the same set X_1 there , so taking a product integral makes no sense. I suspect that this can be handled using similar techniques as you use in Section 6 for CMI estimation, which is also of different form; but you should definitely point out in the beginning of the paper that some modifications are needed; this had me confused for quite a while. (2) there is a step in the argument in Section 6 (which is crucial given the paper's motivation) which I really can't follow, on the bottom of page 7: first, where does the |1 - \alpha| in the formula come from/go to? Second, it seems you use the triangle inequality and the mean value theorem in a single step. This needs to be separated (and probably decomposed in smaller steps even further). Where does the \kappa_2 and \log \kappa* come from? I really don't get it. In fact my recommendation below is conditional on getting more information about this derivation in the author feedback. CLARITYThe goals and presentation are clear. I do have an issue with the notation of the main formula, i.e. the display on page 1 and eq. (3): why do you write p_1(x), ..., p_k(x) there and not p_1(x_1), ..., p_k(x_k) and then  explain that the x in dx stands for x = (x1, ..., x_k). The current definition makes, strictly speaking, no sense (p_i is a function of x_i, not x !). Am I correct or did I miss something? (Again my positive recommendation below is conditional on getting a reply to this question!)ORIGINALITYModerate - this is a step further in a direction of which it has recently become apparent that it is both significant and that interesting results are obtainable. SIGNIFICANCESubstantial - it is definitely useful to have estimates with exponential concentration.FURTHER REMARKS- Why is eq. (11) needed? Isn't this just a repetition of (9)? Better use this space for more explanation about what goes on further below...- When you refer to Renyi divergences: perhaps good to quote Van Erven and Harremoes' recent IEEE paper, which contains 'all you ever wanted to know about Renyi divergence' and seems to be rapidly becoming a standard reference (note I am neither Van Erven nor Harremoes)- I wonder whether the following papers are relevant, you might want to check them out. They deal with countably infinite outcome spaces but otherwise similar concerns as yours, and predate most of what you cite (again, I am not one of the authors :-). On the lower limits of entropy estimation.AJ Wyner, D Fostersubmitted to IEEE Transactions on Information Theory (apparently never officially published!?) Nonparametric entropy estimation for stationary processes and random fields, with applications to English textI Kontoyiannis, PH Algoet, YM Suhov, AJ WynerInformation Theory, IEEE Transactions on 44 (3), 1319-1327- The final sentence of the second paragraph of page 2 is grammatically incorrect and incomprehensible UPDATEAfter having seen the author's response, I updated my score to a 7. I would still like to insist though that my issue with Eq. (3) (see under CLARITY above) is explicitly dealt with in the final paper; either correct the formula (if I am correct) or explain in more detail how to read the formula (if I was wrong and the formula was correct) (the authors remained silent about this in their reply).