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

By John C. Duchi, Martin J. Wainwright. 2013

74 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, methodology): “We avoid this complication by relying instead on a slightly modified form of the classic Fano’s argument from [22]; this form of Fano’s argument was used in [34] as well to obtain a lower bound for the sample complexity of learning under communication constraints.”
Minimax Optimal Procedures for Locally Private Estimation (2016, background): “Let ρ V be a metric on the set V , and for t ≥ 0 define the neighborhood size for the set V by and the separation function (18) Then we have the following generalization (Duchi and Wainwright 2013, Corollary 1) of the Fano bound: for any t ≥ 0, (19)”
Optimality guarantees for distributed statistical estimation (2014, methodology): “The following variant [12] of Fano’s inequality controls this type of error probability: Lemma 2.”
Information-theoretic lower bounds for distributed statistical estimation with communication constraints (2013, methodology): “The result extends a result of Duchi and Wainwright [8]; for completeness we provide a proof in Appendix H.”
On Bayes Risk Lower Bounds (2014, background): “This inequality recently appeared in Duchi and Wainwright (2013, Proposition 2) who termed it the continuum Fano inequality.”
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints (2020, methodology): “The proof relies on applying the recently developed chi-squared contraction method [4] and a variant of Fano’s inequality in [20].”