# Demystifying Fixed k-Nearest Neighbor Information Estimators

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

## Key facts

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

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

- [DICE: Diversity in Deep Ensembles via Conditional Redundancy Adversarial Estimation](https://mlsanity.com/paper/2101.05544/) (2021)
- [Disentanglement via Latent Quantization](https://mlsanity.com/paper/2305.18378/) (2023)
- [Beyond Normal: On the Evaluation of Mutual Information Estimators](https://mlsanity.com/paper/2306.11078/) (2023)
- [Tight Mutual Information Estimation With Contrastive Fenchel-Legendre Optimization](https://mlsanity.com/paper/2107.01131/) (2021)
- [No Free Prune: Information-Theoretic Barriers to Pruning at Initialization](https://mlsanity.com/paper/2402.01089/) (2024)
- [Contextual Bandits for Unbounded Context Distributions](https://mlsanity.com/paper/2408.09655/) (2024)
- [A Reverse Jensen Inequality Result with Application to Mutual Information Estimation](https://mlsanity.com/paper/2111.06676/) (2021)
- [Nearest-Neighbor Sampling Based Conditional Independence Testing](https://mlsanity.com/paper/2304.04183/) (2023)
- [Improving Mutual Information based Feature Selection by Boosting Unique Relevance](https://mlsanity.com/paper/2212.06143/) (2022)
- [REMEDI: Corrective Transformations for Improved Neural Entropy Estimation](https://mlsanity.com/paper/2402.05718/) (2024)
- [A Neural Difference-of-Entropies Estimator for Mutual Information](https://mlsanity.com/paper/2502.13085/) (2025)
- [TENDE: Transfer Entropy Neural Diffusion Estimation](https://mlsanity.com/paper/2510.14096/) (2025)
- [Pitfalls of Climate Network Construction: A Statistical Perspective](https://mlsanity.com/paper/2211.02888/) (2022)
- [When Does Text Inform? Benchmarking Information-Theoretic Metrics for Multimodal Time-Series Forecasting](https://mlsanity.com/paper/2609.11282/) (2026)

## Abstract (arXiv)

Estimating mutual information from i.i.d. samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is one proposed by Kraskov and St"ogbauer and Grassberger (KSG) in 2004, and is nonparametric and based on the distances of each sample to its krm th nearest neighboring sample, where k is a fixed small integer. Despite its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the bias as a function of number of samples. We argue that the superior performance benefits of the KSG estimator stems from a curious "correlation boosting" effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a byproduct of our investigations, we obtain nearly tight rates of convergence of the ℓ2 error of the well known fixed k nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.