Renyi Entropy Estimation Revisited

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review



  • Maciej Obremski
  • ,
  • Maciej Skorski

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 , up to constant accuracy and error probability, we show the following Upper bounds n = O(1) . 2(1- 1 )H for integer > 1, as the worst case over distributions with Renyi entropy equal to H. Lower bounds n =(1) . K1- 1 for any real > 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.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 20th International Workshop, APPROX 2017 and 21st International Workshop, RANDOM 2017
EditorsJose D. P. Rolim, Klaus Jansen, David P. Williamson, Santosh S. Vempala
Number of pages15
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication year1 Aug 2017
Article number20
ISBN (print)978-3-95977-018-7
ISBN (Electronic)9783959770446
Publication statusPublished - 1 Aug 2017
EventApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - University of California, Berkeley , United States
Duration: 16 Aug 201718 Aug 2017
Conference number: 20 / 21


ConferenceApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Nummer20 / 21
LocationUniversity of California
LandUnited States
SeriesLeibniz International Proceedings in Informatics

    Research areas

  • Convex optimization, Entropy estimation, Renyi entropy, Sample complexity

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 120383590