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

The tremendous progress in large-scale statistical inference and learning in recent years has been spurred by both practical and theoretical advances, with strong interactions between the two: Algorithms that come with a priori performance guarantees are clearly desirable, if not crucial, in practical applications, and practical issues are indispensable in guiding the theoretical studies. Complementary to performance bounds for specific algorithms, a key role is also played by algorithmindependent impossibilityresults, stating conditions under which one cannot hope to achieve a certain goal. Such results provide definitive benchmarks for practical methods, serve as certificates for near-optimality, and help guide the practical developments towards directions where the greatest improvements are possible. Since its introduction in 1948, the field of information theory has continually provided such benefits for the problems of storing and transmitting data, and has accordingly shaped the design of practical communication systems. In addition, recent years have seen mounting evidence that the tools and methodology of information theory reach far beyond communication problems, and can provide similar benefits within the entire data processing pipeline. While many information-theoretic tools have been proposed for establishing impossibility results, the oldest one remains arguably the most versatile and widespread: Fano's inequality [1]. This fundamental inequality is not only ubiquitous in studies of communication, but has been applied extensively in statistical inference and learning problems; several examples are given in Table 1. When applying Fano's inequality to such problems, one typically encounters a number of distinct challenges compared to those found in communication problems. The goal of this chapter is to introduce the reader to some of the key tools and techniques, explain their interactions and connections, and provide several representative examples.