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

arXiv: https://arxiv.org/abs/1603.08578 · HTML: https://mlsanity.com/paper/1603.08578/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2016.

## Built on by (most cited first, 6 of 6)

- [f-IRL: Inverse Reinforcement Learning via State Marginal Matching](https://mlsanity.com/paper/2011.04709/) (2020)
- [Trajectory Inference via Mean-field Langevin in Path Space](https://mlsanity.com/paper/2205.07146/) (2022)
- [State Entropy Regularization for Robust Reinforcement Learning](https://mlsanity.com/paper/2506.07085/) (2025)
- [Towards Few-shot Inductive Link Prediction on Knowledge Graphs: A Relational Anonymous Walk-guided Neural Process Approach](https://mlsanity.com/paper/2307.01204/) (2023)
- [Regularized f-Divergence Kernel Tests](https://mlsanity.com/paper/2601.19755/) (2026)
- [A Unified View of cGANs with and without Classifiers](https://mlsanity.com/paper/2111.01035/) (2021)

## Abstract (arXiv)

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.