# An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jan 2019.

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

- [Adversarial Attacks are Reversible with Natural Supervision](https://mlsanity.com/paper/2103.14222/) (2021)
- [How Much Can RAG Help the Reasoning of LLM?](https://mlsanity.com/paper/2410.02338/) (2024)
- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [Fairness through Aleatoric Uncertainty](https://mlsanity.com/paper/2304.03646/) (2023)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [PRSA: Prompt Stealing Attacks against Real-World Prompt Services](https://mlsanity.com/paper/2402.19200/) (2024)
- [Non-Iterative Recovery from Nonlinear Observations using Generative Models](https://mlsanity.com/paper/2205.15749/) (2022)
- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors](https://mlsanity.com/paper/2108.03570/) (2021)
- [RecFusion: A Binomial Diffusion Process for 1D Data for Recommendation](https://mlsanity.com/paper/2306.08947/) (2023)
- [On the Statistical Complexity of Estimation and Testing under Privacy Constraints](https://mlsanity.com/paper/2210.02215/) (2022)
- [How many samples are needed to train a deep neural network?](https://mlsanity.com/paper/2405.16696/) (2024)
- [Retraining with Predicted Hard Labels Provably Increases Model Accuracy](https://mlsanity.com/paper/2406.11206/) (2024)
- [On the well-spread property and its relation to linear regression](https://mlsanity.com/paper/2206.08092/) (2022)
- [On Average-Case Error Bounds for Kernel-Based Bayesian Quadrature](https://mlsanity.com/paper/2202.10615/) (2022)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)
- [Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data](https://mlsanity.com/paper/2409.03335/) (2024)
- [Diffuse Thinking: Exploring Diffusion Language Models as Efficient Thought Proposers for Reasoning](https://mlsanity.com/paper/2510.27469/) (2025)
- [Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints](https://mlsanity.com/paper/2311.03376/) (2023)
- [Learning Single Index Models with Diffusion Priors](https://mlsanity.com/paper/2505.21135/) (2025)
- [Tackling the Inherent Difficulty of Noise Filtering in RAG](https://mlsanity.com/paper/2601.01896/) (2026)
- [Separating Oblivious and Adaptive Models of Variable Selection](https://mlsanity.com/paper/2602.16568/) (2026)
- [Adaptive Confidence Regularization for Multimodal Failure Detection](https://mlsanity.com/paper/2603.02200/) (2026)
- [Entropy-driven Unsupervised Keypoint Representation Learning in Videos](https://mlsanity.com/paper/2209.15404/) (2022)
- [Contrastive Learning to Fine-Tune Feature Extraction Models for the Visual Cortex](https://mlsanity.com/paper/2410.06067/) (2024)
- [No-Regret Gaussian Process Optimization of Time-Varying Functions](https://mlsanity.com/paper/2512.00517/) (2025)
- [Informationally Compressive Anonymization: Non-Degrading Sensitive Input Protection for Privacy-Preserving Supervised Machine Learning](https://mlsanity.com/paper/2603.15842/) (2026)
- [On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization](https://mlsanity.com/paper/2603.18514/) (2026)
- [On the Invariance and Generality of Neural Scaling Laws](https://mlsanity.com/paper/2605.07546/) (2026)
- [On the Structural Limits of Machine Learning Decision Systems: An Information-Theoretic, Interaction-Based, and Stochastic-Dynamical Perspective](https://mlsanity.com/paper/2608.13510/) (2026)

## Abstract (arXiv)

Information theory plays an indispensable role in the development of algorithm-independent impossibility results, both for communication problems and for seemingly distinct areas such as statistics and machine learning. While numerous information-theoretic tools have been proposed for this purpose, the oldest one remains arguably the most versatile and widespread: Fano's inequality. In this chapter, we provide a survey of Fano's inequality and its variants in the context of statistical estimation, adopting a versatile framework that covers a wide range of specific problems. We present a variety of key tools and techniques used for establishing impossibility results via this approach, and provide representative examples covering group testing, graphical model selection, sparse linear regression, density estimation, and convex optimization.