The Nearest Neighbor Information Estimator is Adaptively Near Minimax Rate-Optimal

Jiantao Jiao, Weihao Gao, Yanjun Han

Abstract

Estimating Shannon differential entropy from finite samples is a cornerstone of non-parametric statistics, yet a rigorous theoretical understanding of the popular Kozachenko–Leonenko (KL) estimator has remained elusive. Specifically, existing proofs often rely on the restrictive assumption that the underlying probability density is bounded away from zero. This paper provides a breakthrough by proving that the KL estimator is adaptively near-minimax rate-optimal for distributions with smoothness $s \in (0, 2]$. By employing tools from harmonic analysis, the authors demonstrate that the estimator achieves optimal convergence rates without prior knowledge of the density's smoothness or the assumption of a strictly positive lower bound on the density.

Introduction

Differential entropy, defined as $h(f) = -\int f(x) \ln f(x) dx$, is a fundamental quantity in information theory and machine learning. It serves as a key metric in feature selection, independent component analysis, and causal discovery. Despite its importance, estimating entropy from a finite set of $n$ samples is a challenging non-parametric problem.

In practice, the Kozachenko–Leonenko (KL) $k$-nearest neighbor estimator is the tool of choice due to its simplicity and computational efficiency. However, a significant gap has existed between its empirical success and its theoretical justification. Most existing convergence rate proofs rely on the "bounded density" assumption—the requirement that the density $f(x)$ never drops below a certain positive constant. In real-world applications, densities frequently decay to zero in the tails or contain regions of zero probability, rendering these traditional proofs insufficient. This paper addresses these shortcomings by providing a robust analysis of the KL estimator under more realistic conditions.

The Kozachenko–Leonenko Estimator

The KL estimator operates on the principle that the distance to the $k$-th nearest neighbor of a sample point $X_i$ is inversely proportional to the local density at that point. Let $R_{i,k}$ be the Euclidean distance from $X_i$ to its $k$-th nearest neighbor in a sample of size $n$. The estimator leverages the relationship between the volume of a $d$-dimensional ball of radius $R_{i,k}$ and the probability mass it contains.

While the intuition is straightforward, the mathematical analysis of its error—specifically the bias and variance—is complex. The estimator must account for the fact that the density $f(x)$ varies across the space, and the neighborhood sizes $R_{i,k}$ are random variables that depend on the global distribution of points.

Theoretical Framework and Methodology

To move beyond the limitations of previous research, the authors utilize a sophisticated mathematical framework centered on Hölder balls on a torus. The use of a torus allows the analysis to bypass boundary effects, which often complicate non-parametric estimation, and focus purely on the relationship between the estimator and the smoothness of the density function.

To handle the "zero density" problem, the authors depart from standard Taylor expansion techniques, which fail when the density approaches zero. Instead, they employ two powerful tools from harmonic analysis and measure theory:

  1. Besicovitch Covering Lemma: This lemma is used to manage the geometry of the neighborhood balls. It provides a way to bound the overlaps of these balls, ensuring that the local estimates can be aggregated into a global estimate without over-counting or losing control of the error in low-density regions.
  2. Generalized Hardy–Littlewood Maximal Inequality: This tool is used to bound the behavior of the density function. It allows the authors to control the fluctuations of the density even when it approaches zero or exhibits high local variability.

Key Insights: Adaptivity and Optimality

The paper’s most significant contribution is the proof of adaptivity. In non-parametric statistics, an "optimal" estimator usually requires the user to tune parameters based on the unknown smoothness ($s$) of the underlying distribution. The authors prove that the KL estimator is naturally adaptive: it achieves near-optimal rates for any $s \in (0, 2]$ without the algorithm needing to know the value of $s$ beforehand.

Convergence Rates

The authors establish a new upper bound on the mean squared error (MSE) of the KL estimator. For a density with smoothness $s \in (0, 2]$ in $d$ dimensions, the error scales as:

$$\text{MSE} \lesssim n^{-\frac{2s}{2s+d}} (\ln n)^\alpha$$

This rate matches the known minimax lower bound for this class of functions, save for a small logarithmic factor. This result is particularly notable because it holds for arbitrary dimensions $d > 1$ and does not require the density to be bounded away from zero.

The $s=2$ Ceiling

The analysis also clarifies a known limitation of the standard KL estimator: it cannot exploit smoothness higher than $s=2$. Because the estimator effectively uses a uniform "box kernel" (by counting points within a ball), it behaves like a second-order kernel estimator. In the world of non-parametric estimation, positive kernels are mathematically limited to a bias reduction corresponding to $s=2$. To achieve higher rates for $s > 2$, a different class of estimators (such as those using kernels that can take negative values) would be required.

Discussion and Future Work

While this paper provides a near-complete theoretical picture for the KL estimator, two areas remain open for further investigation:

  • The Logarithmic Gap: There remains a factor of $\ln n$ between the proven upper bound and the theoretical minimax lower bound. The authors suggest that this gap might be an artifact of the proof technique rather than a property of the estimator itself, and future work may tighten this bound.
  • Extensions to Other Metrics: The framework developed here—specifically the use of the Besicovitch lemma and maximal inequalities—could potentially be applied to other information-theoretic estimators. This includes the KSG estimator for Mutual Information and estimators for Kullback–Leibler divergence, which are widely used but lack similarly robust theoretical guarantees in high dimensions.

Conclusion

By providing the first proof that the KL estimator is adaptively near-minimax optimal without restrictive density assumptions, this paper reconciles decades of empirical success with rigorous statistical theory. It confirms that the $k$-nearest neighbor approach is not just a heuristic, but a mathematically sound method for entropy estimation in complex, high-dimensional settings.

Summary updated

BibTeX
@inproceedings{jiao2018nearest,
  author = {Jiantao Jiao and Weihao Gao and Yanjun Han},
  title = {{The Nearest Neighbor Information Estimator is Adaptively Near Minimax Rate-Optimal}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=HkVxqD-d-r},
}
Figure