Settling the Sample Complexity of Rényi Entropy Estimation
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 \[ Θ\!\left(\frac{d^{\max\{1/α,1\}}}{\varepsilon^{1/α}\log(d)} +…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.10389
curl -X POST /api/v1/records/arxiv/2610.10389/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.10389/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'