Estimating Renyi Entropy of Discrete Distributions
This work addresses the fundamental problem of efficiently estimating entropy measures in statistics and information theory, with potential applications in data analysis and machine learning, though it is incremental in extending known Shannon entropy results to Rényi entropy.
The paper determines the sample complexity required to estimate Rényi entropy of order α for discrete distributions, showing it varies with α: super-linear for α < 1, near-linear for noninteger α > 1, and sub-linear for integer α > 1, with a log k reduction for noninteger α using polynomial approximation.
It was recently shown that estimating the Shannon entropy $H({\rm p})$ of a discrete $k$-symbol distribution ${\rm p}$ requires $Θ(k/\log k)$ samples, a number that grows near-linearly in the support size. In many applications $H({\rm p})$ can be replaced by the more general Rényi entropy of order $α$, $H_α({\rm p})$. We determine the number of samples needed to estimate $H_α({\rm p})$ for all $α$, showing that $α< 1$ requires a super-linear, roughly $k^{1/α}$ samples, noninteger $α>1$ requires a near-linear $k$ samples, but, perhaps surprisingly, integer $α>1$ requires only $Θ(k^{1-1/α})$ samples. Furthermore, developing on a recently established connection between polynomial approximation and estimation of additive functions of the form $\sum_{x} f({\rm p}_x)$, we reduce the sample complexity for noninteger values of $α$ by a factor of $\log k$ compared to the empirical estimator. The estimators achieving these bounds are simple and run in time linear in the number of samples. Our lower bounds provide explicit constructions of distributions with different Rényi entropies that are hard to distinguish.