Paper 2017/588

Renyi Entropy Estimation Revisited

Maciej Obremski and Maciej Skorski

Abstract

We revisit the problem of estimating entropy of discrete distributions from independent samples, studied recently by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015), improving their upper and lower bounds on the necessary sample size $n$. For estimating Renyi entropy of order $\alpha$, up to constant accuracy and error probability, we show the following (a) Upper bounds $n = O(1) \cdot 2^{\left(1-\frac{1}{\alpha}\right)H_{\alpha}}$ for integer $\alpha>1$, as the worst case over distributions with Renyi entropy equal to $H_{\alpha}$. (b) Lower bounds $n=\Omega(1)\cdot K^{1-\frac{1}{\alpha}}$ for any real $\alpha>1$, as the worst case over all distributions on $K$ elements. Our upper bounds essentially replace the alphabet size by a factor exponential in the entropy, which offers improvements especially in low or medium entropy regimes (interesting for example in anomaly detection). As for the lower bounds, they were previously given conditionally for sufficiently small accuracy, whereas our result applies even to constant accuracy. Moreover, we prove that small accuracy $\delta$ contributes to the complexity independently on the alphabet, by an extra factor $\delta^{-\frac{1}{\alpha}}$. The argument for upper bounds derives a clean identity for the variance of falling-power sum of a multinomial distribution. Our approach for lower bounds utilizes convex optimization to find a distribution with worse estimation performance, and may be of independent interest.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Renyi Entropy EstimationRenyi EntropySample ComplexityExtreme points
Contact author(s)
obremski @ cs au dk
History
2017-06-20: received
Short URL
https://ia.cr/2017/588
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/588,
      author = {Maciej Obremski and Maciej Skorski},
      title = {Renyi Entropy Estimation Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2017/588},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/588}},
      url = {https://eprint.iacr.org/2017/588}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.