Renyi entropy estimation revisited Conference Paper

Author(s): Obremski, Maciej; Skórski, Maciej
Title: Renyi entropy estimation revisited
Title Series: LIPIcs
Affiliation IST Austria
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^{(1-1/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^{1-1/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 falling-power 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.
Keywords: Rényi entropy; Convex optimization; entropy estimation; sample complexity
Conference Title: APPROX/RANDOM: Approximation, Randomization, and Combinatorial Optimization
Volume: 81
Conference Dates: August 16 - 18, 2017
Conference Location: Berkeley, CA, USA
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Date Published: 2017-01-01
Start Page: Article number: 20
Copyright Statement: CC BY
Sponsor: ERC Horizon 2020 research and innovation programme (grant agreement No 669255); ERC consolidator grant (682815-TOCNeT).
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.20
Open access: yes (OA journal)
IST Austria Authors
Related IST Austria Work