Demystifying fixed k-nearest neighbor information estimators

By Weihao Gao, Sewoong Oh, Pramod Viswanath. 2016

150 citations recorded by the source corpus.

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 Stogbauer and Grassberger (KSG) in 2004, and is nonparametric and based on the distances of each sample to its kth 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 ℓ2 error as a function of number of samples. We argue that the 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.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

Data-Efficient Mutual Information Neural Estimator (2019, background): “[15] provided a comprehensive review and studied the consistency and of asymptotic confidence bound of the KSG estimator [16].”
The Nearest Neighbor Information Estimator is Adaptively Near Minimax Rate-Optimal (2017, background): “There exists some analysis of the KSG estimator [21] but we suspect the upper bound is not tight.”