REVIEW 3 cited by
An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 3 Pith papers
-
Separating Oblivious and Adaptive Models of Variable Selection
For l_infinity sparse recovery, the sample complexity is roughly k log d under independent ('oblivious') signals and k^2 log d under adversarially adaptive signals, a quadratic gap that does not exist for l2 recovery.
-
No-Regret Gaussian Process Optimization of Time-Varying Functions
A windowed sparse GP-UCB with DPP-selected expert re-queries achieves sublinear dynamic regret using o(1) extra queries per round on average, and a Fano lower bound shows Ω(T^{α/(α+1)}) queries are needed in fast-drif...
-
Fast quantum measurement tomography with optimal error bounds
A projected least-squares quantum measurement tomography protocol is shown to achieve dimension-optimal sample complexity (up to log factors) for worst-case and average-case distances, with a provable gap in the numbe...
Discussion (0). Continue with ORCID to comment.