Distance-based and continuum Fano inequalities with applications to statistical estimation

Abstract

In this technical note, we give two extensions of the classical Fano inequality in information theory. The first extends Fano's inequality to the setting of estimation, providing lower bounds on the probability that an estimator of a discrete quantity is within some distance $t$ of the quantity. The second inequality extends our bound to a continuum setting and provides a volume-based bound. We illustrate how these inequalities lead to direct and simple proofs of several statistical minimax lower bounds.

16 pages, 1 figure

Cited by in corpus (15)

• Optimality guarantees for distributed statistical estimation
• On Bayes Risk Lower Bounds
• Optimal query complexity for private sequential learning against eavesdropping
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
• Risk of the Least Squares Minimum Norm Estimator under the Spike Covariance Model
• Phase Transitions in the Pooled Data Problem
• Principal Inertia Components and Applications
• Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models
• An information diffusion Fano inequality
• On Fundamental Limits of Robust Learning
• Strictly Proper Kernel Scoring Rules and Divergences with an Application to Kernel Two-Sample Hypothesis Testing
• Information-Theoretic Lower Bounds on Bayes Risk in Decentralized Estimation
• Information Theoretic Lower Bounds for Feed-Forward Fully-Connected Deep Networks
• Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints
• Regularized Loss Minimizers with Local Data Perturbation: Consistency and Data Irrecoverability