An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- How well can we estimate a sparse vector?Applied and Computational Harmonic Analysis, 2013
- Lower Bounds for the Minimax Risk Using $f$-Divergences, and ApplicationsIEEE Transactions on Information Theory, 2011
- Channel Coding Rate in the Finite Blocklength RegimeIEEE Transactions on Information Theory, 2010
- Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy SettingIEEE Transactions on Information Theory, 2009
- A New Lower Bound for Multiple Hypothesis TestingIEEE Transactions on Information Theory, 2005
- Phase transitions in phylogenyTransactions of the American Mathematical Society, 2003
- Minimax nonparametric classification .I. Rates of convergenceIEEE Transactions on Information Theory, 1999
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Approximation dans les espaces m triques et th orie de l'estimationProbability Theory and Related Fields, 1983
- The separating property of random matricesMathematical Notes, 1978