  Estimating entropy and mutual information consistently is important for many
machine learning applications. The Kozachenko-Leonenko (KL) estimator
(Kozachenko & Leonenko, 1987) is a widely used nonparametric estimator for the
entropy of multivariate continuous random variables, as well as the basis of
the mutual information estimator of Kraskov et al. (2004), perhaps the most
widely used estimator of mutual information in this setting. Despite the
practical importance of these estimators, major theoretical questions regarding
their finite-sample behavior remain open. This paper proves finite-sample
bounds on the bias and variance of the KL estimator, showing that it achieves
the minimax convergence rate for certain classes of smooth functions. In
proving these bounds, we analyze finite-sample behavior of k-nearest neighbors
(k-NN) distance statistics (on which the KL estimator is based). We derive
concentration inequalities for k-NN distances and a general expectation bound
for statistics of k-NN distances, which may be useful for other analyses of
k-NN methods.
