Settling the Sample Complexity of Rényi Entropy Estimation

Abstract

Rényi entropy estimation has been comprehensively investigated by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015; IEEE Trans. Inf. Theory 2017) and consequent works, whereas only the sample complexity of Rényi entropy estimation of integer order has been settled. In this paper, we settle the sample complexity of Rényi entropy estimation of noninteger order, thereby completing the complexity picture of Rényi entropy estimation. Specifically, we show that for any noninteger α> 0, it is sufficient and necessary to use Θ (d^max{1/α,1}/ε^1/αlog(d) + (d^|1−1/α|)/ε²) samples to estimate the Rényi entropy of order α of an unknown discrete distribution over an alphabet of size d to within additive error ε. For the upper bound, we reduce the bias using a refined polynomial approximation estimator for large probabilities. For the lower bound, we employ a different hard instance equipped with a new moment matching construction. The constructive moment matching has constant bounded high-order moments, while attaining a fixed ratio between the α-th moments, which is of independent interest.

Optimal Rényi and Logarithmic Additive Functional Entropy Estimation
Arman Adibi, Piotr Krysta
arXiv20 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
SENECA: Small-Sample Discrete Entropy Estimation via Self-Consistent Missing Mass
Lucas H. McCabe, H. Howie Huang
arXiv25 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Counterexamples to additivity of minimum output p-Rényi entropy of quantum channels for all p≥ 0
Debbie Leung, Benjamin Lovitz, Ion Nechita +1
arXiv5 Oct 2026PreprintCC BY 4.0Full textMathematical physics ProbabilityarXiv
Birthday Estimators Are Uniformly Optimal for Renyi Entropy
Maciej Skórski
arXiv20 Oct 2026PreprintCC BY 4.0Full textProbability StatisticsarXiv
A New Perspective on Cumulative Residual Rényi Entropy
Shubham Babasaheb Alte, Swaroop Georgy Zachariah, Mohd. Arshad
arXiv14 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{wang2026settling,
  title = {{Settling the Sample Complexity of Rényi Entropy Estimation}},
  author = {Qisheng Wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.10389},
  eprint = {2610.10389},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.10389},
}

RIS

TY  - UNPB
TI  - Settling the Sample Complexity of Rényi Entropy Estimation
AU  - Qisheng Wang
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.10389
UR  - https://arxiv.org/abs/2610.10389
AB  - Rényi entropy estimation has been comprehensively investigated by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015; IEEE Trans. Inf. Theory 2017) and consequent works, whereas only the sample complexity of Rényi entropy estimation of integer order has been settled. In this paper, we settle the sample complexity of Rényi entropy estimation of noninteger order, thereby completing the complexity picture of Rényi entropy estimation. Specifically, we show that for any noninteger α> 0, it is sufficient and necessary to use Θ (d^max{1/α,1}/ε^1/αlog(d) + (d^|1−1/α|)/ε^2) samples to estimate the Rényi entropy of order α of an unknown discrete distribution over an alphabet of size d to within additive error ε. For the upper bound, we reduce the bias using a refined polynomial approximation estimator for large probabilities. For the lower bound, we employ a different hard instance equipped with a new moment matching construction. The constructive moment matching has constant bounded high-order moments, while attaining a fixed ratio between the α-th moments, which is of independent interest.
ER  -

Abstract

Related

Cite