Obremski, Maciej ;
Skorski, Maciej
Renyi Entropy Estimation Revisited
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
* Upper bounds n = O(1) 2^{(11/alpha)H_alpha} for integer alpha>1, as the worst case over distributions with Renyi entropy equal to H_alpha.
* Lower bounds n = Omega(1) K^{11/alpha} for any real alpha>1, with the constant being an inverse polynomial of the accuracy, 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, our proof explicitly shows how the complexity depends on both alphabet and accuracy, partially solving the open problem posted in previous works. The argument for upper bounds derives a clean identity for the variance of fallingpower sum of a multinomial distribution. Our approach for lower bounds utilizes convex optimization to find a distribution with possibly worse estimation performance, and may be of independent interest as a tool to work with Le Cam’s two point method.
BibTeX  Entry
@InProceedings{obremski_et_al:LIPIcs:2017:7569,
author = {Maciej Obremski and Maciej Skorski},
title = {{Renyi Entropy Estimation Revisited}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {20:120:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7569},
URN = {urn:nbn:de:0030drops75699},
doi = {10.4230/LIPIcs.APPROXRANDOM.2017.20},
annote = {Keywords: Renyi entropy, entropy estimation, sample complexity, convex optimization}
}
11.08.2017
Keywords: 

Renyi entropy, entropy estimation, sample complexity, convex optimization 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Issue date: 

2017 
Date of publication: 

11.08.2017 