# Efficient Estimation of Mutual Information for Strongly Dependent Variables

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2014.

## Built on by (most cited first, 30 of 46)

- [To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review](https://mlsanity.com/paper/2304.09355/) (2023)
- [Causal Influence Detection for Improving Efficiency in Reinforcement Learning](https://mlsanity.com/paper/2106.03443/) (2021)
- [Farewell to Mutual Information: Variational Distillation for Cross-Modal Person Re-Identification](https://mlsanity.com/paper/2104.02862/) (2021)
- [Beyond Normal: On the Evaluation of Mutual Information Estimators](https://mlsanity.com/paper/2306.11078/) (2023)
- [MINDE: Mutual Information Neural Diffusion Estimation](https://mlsanity.com/paper/2310.09031/) (2023)
- [On the Surrogate Gap between Contrastive and Supervised Losses](https://mlsanity.com/paper/2110.02501/) (2021)
- [Simpler, Faster, Stronger: Breaking The log-K Curse On Contrastive Learners With FlatNCE](https://mlsanity.com/paper/2107.01152/) (2021)
- [Approximating mutual information of high-dimensional variables using learned representations](https://mlsanity.com/paper/2409.02732/) (2024)
- [Tight Mutual Information Estimation With Contrastive Fenchel-Legendre Optimization](https://mlsanity.com/paper/2107.01131/) (2021)
- [VNE: An Effective Method for Improving Deep Representation by Manipulating Eigenvalue Distribution](https://mlsanity.com/paper/2304.01434/) (2023)
- [Sample Complexity of Probability Divergences under Group Symmetry](https://mlsanity.com/paper/2302.01915/) (2023)
- [Assessing Neural Network Representations During Training Using Noise-Resilient Diffusion Spectral Entropy](https://mlsanity.com/paper/2312.04823/) (2023)
- [Network Binarization via Contrastive Learning](https://mlsanity.com/paper/2207.02970/) (2022)
- [Robust Concept Erasure via Kernelized Rate-Distortion Maximization](https://mlsanity.com/paper/2312.00194/) (2023)
- [A Benchmark Suite for Evaluating Neural Mutual Information Estimators on Unstructured Datasets](https://mlsanity.com/paper/2410.10924/) (2024)
- [Bird's Eye: Probing for Linguistic Graph Structures with a Simple Information-Theoretic Approach](https://mlsanity.com/paper/2105.02629/) (2021)
- [L2M: Mutual Information Scaling Law for Long-Context Language Modeling](https://mlsanity.com/paper/2503.04725/) (2025)
- [miCSE: Mutual Information Contrastive Learning for Low-shot Sentence Embeddings](https://mlsanity.com/paper/2211.04928/) (2022)
- [On the Effectiveness of Hybrid Mutual Information Estimation](https://mlsanity.com/paper/2306.00608/) (2023)
- [MIND: Inductive Mutual Information Estimation, A Convex Maximum-Entropy Copula Approach](https://mlsanity.com/paper/2102.13182/) (2021)
- [A Reverse Jensen Inequality Result with Application to Mutual Information Estimation](https://mlsanity.com/paper/2111.06676/) (2021)
- [A robust estimator of mutual information for deep learning interpretability](https://mlsanity.com/paper/2211.00024/) (2022)
- [Many Perception Tasks are Highly Redundant Functions of their Input Data](https://mlsanity.com/paper/2407.13841/) (2024)
- [A Distance Correlation-Based Approach to Characterize the Effectiveness of Recurrent Neural Networks for Time Series Forecasting](https://mlsanity.com/paper/2307.15830/) (2023)
- [MMG: Mutual Information Estimation via the MMSE Gap in Diffusion](https://mlsanity.com/paper/2509.20609/) (2025)
- [Trying to Outrun Causality with Machine Learning: Limitations of Model Explainability Techniques for Identifying Predictive Variables](https://mlsanity.com/paper/2202.09875/) (2022)
- [Towards a Rigorous Analysis of Mutual Information in Contrastive Learning](https://mlsanity.com/paper/2308.15704/) (2023)
- [An Information Theoretic Approach to Interaction-Grounded Learning](https://mlsanity.com/paper/2401.05015/) (2024)
- [INFO-SEDD: Continuous Time Markov Chains as Scalable Information Metrics Estimators](https://mlsanity.com/paper/2502.19183/) (2025)
- [Accurate Estimation of Mutual Information in High Dimensional Data](https://mlsanity.com/paper/2506.00330/) (2025)

## Abstract (arXiv)

We demonstrate that a popular class of nonparametric mutual information (MI) estimators based on k-nearest-neighbor graphs requires number of samples that scales exponentially with the true MI. Consequently, accurate estimation of MI between two strongly dependent variables is possible only for prohibitively large sample size. This important yet overlooked shortcoming of the existing estimators is due to their implicit reliance on local uniformity of the underlying joint distribution. We introduce a new estimator that is robust to local non-uniformity, works well with limited data, and is able to capture relationship strengths over many orders of magnitude. We demonstrate the superior performance of the proposed estimator on both synthetic and real-world data.