Multivariate f -Divergence Estimation With Confidence
The problem of f -divergence estimation is important in the fields of machine learning, information theory, and statistics. While several nonparametric divergence estimators exist, relatively few have known convergence properties. In particular, even for those estimators whose MSE convergence rates are known, the asymptotic distributions are unknown. We establish the asymptotic normality of a recently proposed ensemble estimator of f -divergence between two distributions from a finite number of samples. This estimator has MSE convergence rate of O 1 T , is simple to implement, and performs well in high dimensions. This theory enables us to perform divergence-based inference tasks such as testing equality of pairs of distributions based on empirical samples. We experimentally validate our theoretical results and, as an illustration, use them to empirically bound the best achievable classification error.
Paper ID:  1260Title:  Multivariate $f$-Divergence Estimation With ConfidenceNOTE: Due to the short reviewing time and out of fairness to the other papers I was reviewing, I DID NOT do more than glance over the supplementary material.  In most cases, I therefore did not verify that results claimed by the authors are correct, but instead checked that they are plausible.Summary:  The authors consider an estimator for $f$-divergences based on the following procedure: given samples from two distributions $f_1$ and $f_2$, compute $k$-nn density estimators for Quality, clarity, originality and significance:  This paper proves a second-order result on estimators for information-theoretic/statistical functionals of pairs of distributions.  From a statistics/probability perspective this is an important result, since $k$-nn density estimators are relatively straightforward to compute.  The manuscript is not written in a way that is easy to read for the non-expert; the problem setup would be difficult to follow for the average NIPS attendee.  I therefore lowered my score.  The proofs (as determined from the sketches provided) are novel and appear to have broader applicability.Recommendation:  Overall, with some reorganization of the material with an eye towards helping the target audience (i.e., NIPS attendees) understand the results, this would be a nice addition to the program.  Without such reorganization, I would find it difficult to recommend acceptance.Comments:  (comments are numbered to allow for easy reference in the rebuttal)1)  In the related work, when discussing drawbacks of previous work, it might be nice to indicate which of the problems with that work the current result addresses, and which problems it does not address.2)  In the setup of the problem it would be best to be clear (for the reader) the space in which the estimators take their value.  For example, it does not seem that the results can handle vector-valued parameters, but perhaps I am mistaken.  A bit more mathematical precision/rigor earlier in the paper goes a long way.3)  The paper is more-or-less written with the expert in mind, which I find unfortunate.  The actual setup of the problem does not appear until the bottom of page 3 -- the estimator is given two sets of samples from $f_1$ and $f_2$ and must estimate a particular $f$-divergence.  It would *really* help the reader to have this setup first before talking about weighting ensembles of estimators etc. etc.4)  In the optimization before (1), what is the intuition behind the relaxation?5)  How is $N$ chosen?  6)  Why is the estimator in [1] defined using data X and Y and the plug-in estimator using X and X?  Is there a significance to the notation change?7)  When constructing the plug-in divergence estimator, is the estimate at $\mathbf{X}_j$ for $j \le N$ formed using the $k$-nn density estimate?  This is actually *not* specified in the manuscript as written.8)   The sketch of Lemma 4 is unintelligible to someone who is not going to read the proof (as opposed to the comments after Lemma 3) -- I would dramatically shorten it to make room for a more gentle introduction of the problem.  Just relegate the whole proof to the supplementary material.9)  The Broad Implications ("broader impacts?") in Section 3.2 seem appealing but also somewhat speculative.  While I appreciate the context, I am not sure this is the right location for these comments.  Perhaps move them to the conclusion?10)  In the conclusion: I realize that one must always put in some sort of "further work" to make it seem like the current result is building somewhere.  However, I am a little unconvinced that "deriving the nonasymptotic distribution of the estimator" is actually something that people will want to do.  To me the more convincing follow-up work would be the application of the main ideas of the proof here to other problems as outlined in section 3.2.11)  I didn't quite understand from the experiment section how the QDA classifier was trained -- perhaps a little more detail here would be appropriate -- there is still space in the paper to provide it, and it might give the reader who is not going to read the proof something concrete to look at.12)  Perhaps describing the estimator in an \begin{algorithm} \end{algorithm} environment would be helpful to the reader who wants to implement this procedure.  This may take up too much space.  However, it would make the result/approach more accessible.13)  One thing that is not at all clear from the description in Section 2 is that the index set $l$ is indexing over different neighborhood sizes for the $k$-nn density estimate.  Because a lot of the intuition/construction of the actual estimator is obscured by the author's writing, the overall idea of the proof is rather difficult to understand.Small things:- [Introduction] I think it's fairer to say that the idea of $f$-divergence generalizes several measures, rather than saying that many $f$-divergences have been defined -- it's a little more historically accurate.- there seems to be an overfull \hbox on page 5Please summarize your review in 1-2 sentences:  The authors prove the asymptotic normality of an estimator of $f$-divergence given two samples from two unknown distributions $f_1$ and $f_2$.  The estimator is formed by taking a plug-in estimate after kernel density estimation on each of the two distributions.Quality Score (1-10):  7Impact Score (1-2):  1Confidence (1-5):  4ADDITION AFTER AUTHOR FEEDBACK:  The detailed feedback from the authors has made me even more sanguine about this paper and I am revising my score upward to an 8.Quality Score (1-10):  8