# Direct Estimation of Information Divergence Using Nearest Neighbor Ratios

arXiv: https://arxiv.org/abs/1702.05222 · HTML: https://mlsanity.com/paper/1702.05222/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2017.

## Built on by (most cited first, 11 of 11)

- [MAUVE Scores for Generative Models: Theory and Practice](https://mlsanity.com/paper/2212.14578/) (2022)
- [Action Noise in Off-Policy Deep Reinforcement Learning: Impact on Exploration and Performance](https://mlsanity.com/paper/2206.03787/) (2022)
- [Discriminative Estimation of Total Variation Distance: A Fidelity Auditor for Generative Data](https://mlsanity.com/paper/2405.15337/) (2024)
- [The Representation Jensen-Shannon Divergence](https://mlsanity.com/paper/2305.16446/) (2023)
- [The Conditional Cauchy-Schwarz Divergence with Applications to Time-Series Data and Sequential Decision Making](https://mlsanity.com/paper/2301.08970/) (2023)
- [The Stanford Drone Dataset is More Complex than We Think: An Analysis of Key Characteristics](https://mlsanity.com/paper/2203.11743/) (2022)
- [Improving Privacy Benefits of Redaction](https://mlsanity.com/paper/2501.17762/) (2025)
- [A Theoretical Perspective on Subnetwork Contributions to Adversarial Robustness](https://mlsanity.com/paper/2307.03803/) (2023)
- [A Unifying Information-theoretic Perspective on Evaluating Generative Models](https://mlsanity.com/paper/2412.14340/) (2024)
- [Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding](https://mlsanity.com/paper/2503.07475/) (2025)
- [Local polynomial density ratio estimation](https://mlsanity.com/paper/2609.38412/) (2026)

## Abstract (arXiv)

We propose a direct estimation method for R'enyi and f-divergence measures based on a new graph theoretical interpretation. Suppose that we are given two sample sets X and Y, respectively with N and M samples, where η:=M/N is a constant value. Considering the k-nearest neighbor (k-NN) graph of Y in the joint data set (X,Y), we show that the average powered ratio of the number of X points to the number of Y points among all k-NN points is proportional to R'enyi divergence of X and Y densities. A similar method can also be used to estimate f-divergence measures. We derive bias and variance rates, and show that for the class of γ-H"older smooth functions, the estimator achieves the MSE rate of O(N-2γ/(γ+d)). Furthermore, by using a weighted ensemble estimation technique, for density functions with continuous and bounded derivatives of up to the order d, and some extra conditions at the support set boundary, we derive an ensemble estimator that achieves the parametric MSE rate of O(1/N). Our estimators are more computationally tractable than other competing estimators, which makes them appealing in many practical applications.