Analysis of k-Nearest Neighbor Distances with Application to Entropy Estimation

Abstract

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.

References in corpus (8)

• Information theory in molecular biology
• Estimation of Rényi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs
• Rates of Convergence for Nearest Neighbor Classification
• Ensemble estimation of multivariate f-divergence
• Undercomplete Blind Subspace Deconvolution
• Exponential Concentration of a Density Functional Estimator
• Ensemble estimators for multivariate entropy estimation
• Estimating Mutual Information by Local Gaussian Approximation

Cited by in corpus (11)

• Computing spatially resolved rotational hydration entropies from atomistic simulations
• Nonparanormal Information Estimation
• Bootstrapping Persistent Betti Numbers and Other Stabilizing Statistics
• No MCMC for me: Amortized sampling for fast and stable training of energy-based models
• Geometric Estimation of Multivariate Dependency
• Density Functional Estimators with k-Nearest Neighbor Bandwidths
• f-IRL: Inverse Reinforcement Learning via State Marginal Matching
• Minimax Optimal Estimation of KL Divergence for Continuous Distributions
• Adaptive Non-Parametric Regression With the $K$-NN Fused Lasso
• Measuring Information Leakage in Website Fingerprinting Attacks and Defenses
• Analysis of KNN Information Estimators for Smooth Distributions