Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation

Weihao Gao, Sewoong Oh, Pramod Viswanath

Introduction

Estimating entropy and mutual information (MI) from finite samples is a cornerstone of modern data science, underpinning tasks from feature selection to representation learning. However, traditional estimators often struggle with the "bandwidth barrier." Non-parametric $k$-nearest neighbor ($k$-NN) methods, while adaptive to local density, suffer from significant bias when data resides on low-dimensional manifolds or near boundaries. Conversely, Kernel Density Estimation (KDE) requires a delicate balance in choosing a global bandwidth; too large a bandwidth oversmooths the density, while too small a bandwidth introduces excessive noise.

This paper introduces the $k$-LNN estimator, a novel framework that "breaks" this barrier by combining the local adaptivity of $k$-NN with the structural modeling of local likelihood density estimation. By mathematically accounting for the resulting bias, the authors provide a simple correction method that significantly outperforms state-of-the-art estimators.

Methods: Local Likelihood and Universal Bias

The $k$-LNN estimator leverages Local Likelihood Density Estimation (LLDE). Instead of simple point counting, it fits a local polynomial of degree $p$ to the log-density of the data within a neighborhood defined by the $k$-th nearest neighbor.

Local structure adaptation: The k-LNN estimator (green ellipses) captures local curvature and orientation, unlike standard k-NN (red circle).

Key innovations include:

  • Closed-form Solutions: For $p \leq 2$, the authors derive efficient, closed-form expressions using Gaussian kernels, avoiding the need for iterative numerical optimization.
  • Universal Bias Correction: A major theoretical contribution is the proof that for a fixed $k$, the asymptotic bias of the local estimator depends only on $k$ and the dimension $d$, and is independent of the underlying data distribution. This allows for a simple, precomputed bias-correction constant ($B_{k,d}$).
  • Geometric Adaptation: By using a quadratic fit ($p=2$), the estimator accounts for local curvature and orientation, effectively correcting for the "boundary bias" that plagues standard $k$-NN methods.

Experimental Evaluation

The performance of the $k$-LNN estimator was rigorously tested against synthetic datasets where ground truth entropy and MI are known, including jointly Gaussian variables with varying correlations, mixtures of Gaussians, and high-dimensional manifolds.

Performance comparison: The p=2 estimator (green) maintains low MSE across extreme correlations and converges significantly faster with sample size than the standard KL estimator.

Key Results

  • Robustness to Correlation: As variables become highly correlated ($r \to 1$), data collapses toward lower-dimensional structures. While traditional estimators like Kozachenko-Leonenko (KL) see errors spike by orders of magnitude, the $p=2$ $k$-LNN estimator remains stable and accurate.
  • Sample Efficiency: The proposed method demonstrates superior convergence rates. In high-dimensional tests, it reaches lower error levels with significantly fewer samples than traditional KDE or $k$-NN approaches.
  • Superior Accuracy: Across diverse multi-modal and non-linear distributions, the degree-2 $k$-LNN estimator consistently achieved lower Mean Squared Error (MSE) than state-of-the-art baselines.

Conclusion and Future Work

The $k$-LNN estimator provides a powerful, computationally efficient tool for information-theoretic estimation. By mathematically accounting for the bias introduced by local bandwidths, it bridges the gap between geometric and kernel-based methods.

While highly effective, future research could further explore optimal selection strategies for $k$ and provide a formal theoretical treatment of convergence rates on embedded manifolds. Despite the increased local computation required for quadratic fitting, the gains in accuracy and sample efficiency make $k$-LNN a compelling choice for high-dimensional data analysis.

Summary updated

BibTeX
@inproceedings{gao2016breaking,
  author = {Weihao Gao and Sewoong Oh and Pramod Viswanath},
  title = {{Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=BJW25_WubH},
}
Figure