Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation

Weihao Gao, Sewoong Oh, Pramod Viswanath

Estimating information-theoretic measures like entropy and mutual information is a cornerstone of modern data science, powering everything from unsupervised representation learning to computational biology. However, practitioners often face a dilemma: do you use geometric methods (like $k$-nearest neighbors) that are robust but biased near boundaries, or kernel-based methods that struggle with bandwidth selection in high dimensions?

In their paper "Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation," Weihao Gao, Sewoong Oh, and Pramod Viswanath bridge this gap. They introduce a new class of estimators that leverage local geometry to achieve state-of-the-art accuracy, particularly in the challenging regimes of high dimensionality and strong correlation.

TL;DR

The authors propose the $k$-LNN estimator, which combines local likelihood density estimation with adaptive $k$-NN bandwidths. By proving that the resulting asymptotic bias is "universal"—independent of the underlying data distribution—they provide a simple, pre-computable correction that significantly outperforms existing methods like KSG and KL.

What Problem Does This Paper Address?

Traditional non-parametric entropy estimators generally fall into two camps:

  1. $k$-Nearest Neighbor (k-NN) methods: These are popular because they adapt to the local density of data. However, they suffer from "boundary bias," especially when data lies on a lower-dimensional manifold or when variables are highly correlated.
  2. Kernel Density Estimation (KDE): These methods use a "bandwidth" parameter to smooth the data. Choosing a global bandwidth is notoriously difficult; too large, and you lose local detail; too small, and the variance explodes.

The "bandwidth barrier" refers to the fact that for consistency, the bandwidth must vanish slowly as the sample size increases. If it vanishes too fast (as it does in fixed $k$-NN methods), it introduces a non-vanishing bias that typically depends on the unknown distribution, making it impossible to correct.

Methods

The authors resolve this by integrating Local Likelihood Density Estimation (LLDE) with a local, data-dependent bandwidth choice.

  • Local Likelihood: Instead of a simple kernel, they fit a local polynomial (up to degree $p=2$) to the log-density of the data around each point.
  • Adaptive Bandwidth: They set the bandwidth for each point $i$ to be the distance to its $k$-th nearest neighbor ($\rho_{k,i}$).
  • Bias Correction: Because $k$ is fixed and small, the bandwidth vanishes rapidly, leading to bias. The paper's major theoretical contribution is proving that this bias is universal. It depends only on $k$, the dimension $d$, the kernel choice, and the polynomial degree—not the actual shape of the distribution.
  • Closed-Form Solutions: They derive efficient, closed-form expressions for the degree $p=1$ and $p=2$ cases using Gaussian kernels, avoiding the expensive numerical integrations required by previous local likelihood attempts.
The degree-2 local likelihood approximation (green contours) captures the local structure of the data much better than the standard k-NN approach (red circle), which assumes a uniform distribution and suffers from boundary bias.

Datasets

The authors evaluated their estimators using a variety of synthetic benchmarks designed to stress-test different scenarios:

  • Jointly Gaussian Variables: Used to test performance across varying levels of correlation ($r$).
  • Gaussian Mixtures: To evaluate performance on non-Gaussian, multi-modal distributions.
  • Functional Relationships: Testing mutual information estimation where $Y = f(X) + \text{noise}$ for various functions $f$ (linear, quadratic, cubic, exponential, and periodic).
  • High-Dimensional Data: Simulations in up to 6 dimensions to demonstrate how the estimator scales.

Key Insights and Ideas

  • The Geometry of Neighbors: The authors establish a fundamental connection between the asymptotic geometry of nearest neighbors and order statistics. They show that normalized neighbor distances converge to standardized uniform order statistics, while their directions converge to a Haar measure on a unit sphere.
  • Correcting the "Uncorrectable": By showing the bias is universal, they transform a "vanishing bandwidth" problem into a simple subtraction task. You can precompute the bias $B_{k,d}$ once for a given $k$ and $d$ and apply it to any dataset.
  • Unified View: The framework is a strict generalization. The classical Kozachenko-Leonenko (KL) estimator is revealed to be a special case of this framework (where degree $p=0$ and a step kernel is used).

Key Results

The proposed $k$-LNN estimator consistently outperforms state-of-the-art methods like the KL and KSG estimators.

  • Strong Correlation: As variables become more correlated ($r \to 1$), the gap between $k$-LNN and traditional methods widens significantly. In these "near-deterministic" regimes, $k$-LNN maintains low Mean Squared Error (MSE) while others fail.
  • High Dimensions: In 6-dimensional Gaussian tests, the degree-2 $k$-LNN estimator achieved orders of magnitude lower MSE than the KL estimator as the sample size increased.
Comparison of MSE for entropy estimation. The degree-2 k-LNN estimator (green) shows significantly lower error than competitors, especially as the number of samples increases.
  • Functional Robustness: The estimator proved highly robust in detecting mutual information in complex non-linear relationships (e.g., $Y = \cos(5\pi X(1-X)) + U$), where standard methods often underestimated the information content.

Limitations and Future Work

  • Computational Complexity: While they provide closed-form solutions, the degree-2 estimator is still more computationally intensive than simple $k$-NN. The authors use a truncation strategy (considering only the nearest $m$ neighbors) to keep it practical.
  • Manifold Adaptation: While the estimator performs well in high dimensions, the authors note it's an open question whether it automatically adapts to data lying on lower-dimensional manifolds without explicit knowledge of geodesic distances.
  • Extension to Other Metrics: The authors suggest this local estimation framework could be extended to other information measures, such as Rényi entropy.

Summary updated

Abstract

Estimators of information theoretic measures such as entropy and mutual information are a basic workhorse for many downstream applications in modern data science. State of the art approaches have been either geometric (nearest neighbor (NN) based) or kernel based (with a globally chosen bandwidth). In this paper, we combine both these approaches to design new estimators of entropy and mutual information that outperform state of the art methods. Our estimator uses local bandwidth choices of $k$-NN distances with a finite $k$, independent of the sample size. Such a local and data dependent choice improves performance in practice, but the bandwidth is vanishing at a fast rate, leading to a non-vanishing bias. We show that the asymptotic bias of the proposed estimator is universal; it is independent of the underlying distribution. Hence, it can be pre-computed and subtracted from the estimate. As a byproduct, we obtain a unified way of obtaining both kernel and NN estimators. The corresponding theoretical contribution relating the asymptotic geometry of nearest neighbors to order statistics is of independent mathematical interest.
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