Sample Complexity of Estimating Entropy
summary
Establishes sample complexity for entropy variants: Shannon needs about K / log K samples, Rényi with alpha<1 needs ~K^(1/alpha) (superlinear), noninteger alpha>1 still needs linear samples, but integer alpha allow a sharp improvement to K^(1-1/alpha); in particular Rényi order 2 uses Θ(√K) samples. Proofs use Poisson sampling, profile (occupancy) statistics, moment-matching lower bounds via polynomial root shifts, and an unbiased bias-corrected estimator for integer α; simulations show practical constants much smaller than worst-case theory.
AI-written summary · about
chapters (12)
- 0:00Intro
- 3:16Sample Complexity of Estimating Shannon Entropy
- 5:43Estimating Renyi Entropy
- 7:21Which Renyi Entropy is the easiest to Estimate?
- 10:36Related Work
- 12:39Empirical or Plug-in Estimator
- 14:39Poisson Sampling
- 16:33A Bias-Corrected Estimator
- 18:14Performance of the Bias-Corrected Estimator
- 20:09The General Approach
- 21:17Distance between Profile Distributions
- 23:13Derivation of our Lower Bounds: Key Construction
related talks
01h 05mDistribution Estimation and Applications III
59mCompositional Properties of Statistical Procedures: An Information-Theoretic View
01h 12mLearning probability distributions; what can, what can't be done
01h 00mDifferential Privacy And The Complexity Of Simple Queries
01h 02mSampling for Linear Algebra, Statistics, and Optimization II
44mSomething for Almost Nothing: Advances in Sub-Linear Time Algorithms
48mLearning by Local Entropy Maximization
38mAn Information Theoretic View of Hypercontractivity