Nearest Neighbor Density Functional Estimation From Inverse Laplace Transform

J. Jon Ryu, Shouvik Ganguly, Younghan Kim, Yung-Kyun Noh, Daniel D. Lee

TL;DR

This paper introduces a novel, unified framework for estimating general density functionals using k-nearest neighbor (k-NN) distances. By leveraging the inverse Laplace transform, their method provides a consistent way to estimate various information-theoretic quantities, unifying existing estimators and discovering new ones. This work offers a principled approach to density functional estimation with theoretical guarantees on consistency and convergence rates.

What Problem Does This Paper Address?

Estimating density functionals – quantities derived from probability density functions (like entropy, divergences, etc.) – is crucial in many fields, from machine learning to signal processing. Traditional methods often rely on plug-in estimators that require density estimates, which can be inconsistent for fixed k in k-NN approaches. Existing methods for specific functionals often involve ad-hoc bias corrections or are limited in scope. This paper addresses the challenge of developing a unified, principled, and consistent method for estimating a broad class of density functionals, including those for which existing methods are insufficient.

Methods

The core of the paper's contribution lies in a novel estimator design based on the inverse Laplace transform. The authors show that for a general density functional $T_f(p) = \mathbb{E}_p[f(p(X))]$, the corresponding k-NN estimator function $\phi_k(u)$ can be derived from the inverse Laplace transform of $f(p)$ scaled by $p^k$. Specifically, $\phi_k(u) = \frac{1}{u^{k-1}} \mathcal{L}^{-1}\{f(\cdot)\}(u)$. This $\phi_k(u)$ is then used in a k-NN based estimator: $\hat{T}_f^{(k)}(X_{1:m}) = \frac{1}{m} \sum_{i=1}^m \phi_k(U_{k,m}(X_i))$, where $U_{k,m}(X_i)$ is a normalized k-NN distance. This approach naturally unifies existing estimators and provides a systematic way to derive new ones. The paper also rigorously establishes theoretical guarantees for this estimator, including asymptotic unbiasedness and convergence rates in mean-squared error, under mild regularity conditions on the densities.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and uses synthetic data for simulations.

Key Insights and Ideas

  • Unified Framework: The inverse Laplace transform provides a single, elegant mathematical tool to derive estimators for a wide range of density functionals, unifying previously disparate methods.
  • Principled Design: Instead of ad-hoc bias correction, the paper offers a principled way to construct estimators by directly linking the functional's form to the estimator's structure via Laplace transforms.
  • Generalization: The method extends naturally to functionals of two densities, handling divergences and other cross-density measures.
  • Theoretical Guarantees: The paper provides strong theoretical backing, proving L2-consistency and establishing convergence rates for general functionals under relatively mild density assumptions.
  • Adaptive k: While the paper primarily focuses on fixed $k$, it hints at adaptive choices of $k$ that can improve convergence rates, suggesting future research directions.

Key Results

  • L2-Consistency: The proposed k-NN estimator is proven to be L2-consistent for a broad class of densities and general density functionals.
  • Convergence Rates: For smooth, bounded densities, the paper establishes convergence rates in mean-squared error (MSE) as a function of sample size $m$. The rates depend on the functional's properties (via exponents $a$ and $b$) and the dimension $d$.
  • Unification of Existing Estimators: The framework recovers known k-NN estimators for Shannon entropy, Rényi entropies, KL divergence, and Rényi divergences.
  • New Estimators: The method discovers consistent estimators for functionals like logarithmic entropies and divergences, which were not easily obtainable with previous approaches.
  • Empirical Validation: Simulations demonstrate that the estimators converge to the true functional values, with observed rates aligning with theoretical predictions.

Limitations and Future Work

  • Minimax Optimality: The authors acknowledge that the derived convergence rates are not generally minimax optimal. This is attributed to suboptimal bias rates, particularly for higher-order smoothness of densities.
  • Curse of Dimensionality: Similar to other density estimation methods, the performance can degrade in high dimensions, although the paper's framework aims to mitigate this.
  • Adaptive $k$ Analysis: While the paper suggests adaptive $k$ can improve rates, a full theoretical analysis for adaptive $k$ is left as future work.
  • General Metric Measure Spaces: The current framework assumes Euclidean distance. Extending it to general metric measure spaces is mentioned as a future direction, requiring careful adaptation of technical lemmas.
  • Ensemble Methods: The paper suggests that ensemble approaches (averaging estimators with different $k$) could potentially overcome some limitations, particularly regarding minimax optimality and adapting to higher smoothness, but this is left for future investigation.

Summary updated

Abstract

A new approach to $L_2$-consistent estimation of a general density functional using $k$-nearest neighbor distances is proposed, where the functional under consideration is in the form of the expectation of some function $f$ of the densities at each point. The estimator is designed to be asymptotically unbiased, using the convergence of the normalized volume of a $k$-nearest neighbor ball to a Gamma distribution in the large-sample limit, and naturally involves the inverse Laplace transform of a scaled version of the function $f.$ Some instantiations of the proposed estimator recover existing $k$-nearest neighbor based estimators of Shannon and Rényi entropies and Kullback--Leibler and Rényi divergences, and discover new consistent estimators for many other functionals such as logarithmic entropies and divergences. The $L_2$-consistency of the proposed estimator is established for a broad class of densities for general functionals, and the convergence rate in mean squared error is established as a function of the sample size for smooth, bounded densities.
BibTeX
@article{ryu2022nearest,
  author = {J. Jon Ryu and Shouvik Ganguly and Younghan Kim and Yung-Kyun Noh and Daniel D. Lee},
  title = {{Nearest Neighbor Density Functional Estimation From Inverse Laplace Transform}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  doi = {10.1109/tit.2022.3151231},
}
Figure