Metraipolis › archive › dc_ad2f89ba18a0

Settling the Sample Complexity of Rényi Entropy Estimation — arXiv:2610.10389

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.10389
License (as archived)
CC0-1.0
Archived
2026-10-08T12:42:57.024Z
SHA-256 of the archived text
c11bddd1d465584b1e2b57f83d1fde5f9a32ce17b80486aa689a76c06ee8c5f0
Stable URL of this page
https://metraipolis.com/documento/dc_ad2f89ba18a0

How to cite

Settling the Sample Complexity of Rényi Entropy Estimation — arXiv:2610.10389 — arXiv (en), https://arxiv.org/abs/2610.10389 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ad2f89ba18a0 (Metraipolis archive dc_ad2f89ba18a0, sha256 c11bddd1d465584b1e2b57f83d1fde5f9a32ce17b80486aa689a76c06ee8c5f0)
BibTeX
@misc{dcad2f89ba18a0,
  title = {Settling the Sample Complexity of Rényi Entropy Estimation — arXiv:2610.10389},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.10389},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ad2f89ba18a0; sha256 c11bddd1d465584b1e2b57f83d1fde5f9a32ce17b80486aa689a76c06ee8c5f0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10389. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\alpha > 0$, it is sufficient and necessary to use \[ \Theta\!\left(\frac{d^{\max\{1/\alpha,1\}}}{\varepsilon^{1/\alpha}\log(d)} + \frac{d^{|1-1/\alpha|}}{\varepsilon^2}\right) \] samples to estimate the Rényi entropy of order $\alpha$ of an unknown discrete distribution over an alphabet of size $d$ to within additive error $\varepsilon$. 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 $\alpha$-th moments, which is of independent interest.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.ST, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT) ; Data Structures and Algorithms (cs.DS); Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2610.10389 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:16:15.211Z dalla pagina https://arxiv.org/list/math.ST/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).