Backend
Settling the Sample Complexity of R\'enyi Entropy Estimation
arXiv math.IT0 views
arXiv:2610.10389v1 Announce Type: new Abstract: R\'enyi 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\'enyi entropy estimation of integer order has been settled. In this paper, we settle the sample complexity of R\'enyi entropy estimation of noninteger order, thereby completing the complexity picture of R\'enyi 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\'enyi 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.
Source:https://arxiv.org/abs/2610.10389PreviousPathwise Information Certificates for Decentralized Adaptive SensingNextPolarforming for MIMO Covert Communications
Related posts
Turn Today’s Messy Notes Into Tomorrow’s Checklist With AI
0dev.to AI
A 763B MoE at "2 Bits": Where the Bytes Really Go in the GSQ-RCO GGUFs, and Why 100% Recovery Sits Inside the Noise
0dev.to AI
How I ship fixes to open-source projects maintainers actually merge (with AI in the loop)
0dev.to AI
Prompt Injection Through Documents: How to Harden an LLM Extraction Pipeline
0dev.to AI
Keeping noindex, the sitemap and the image sitemap in agreement for programmatic pages
0dev.to AI
3 Things in AI You Should Know: Character.AI Files for Bankruptcy
0dev.to AI