Paper Characterizes Tight Sample Bounds for Renyi and Min-Entropy Estimation
abeirami · x · 2026-08-19
The paper 'Tight Sample Bounds for Renyi and Min-Entropy Estimation' characterizes the sample complexity for estimating Rényi and min-entropy. It proves that estimating min-entropy to constant additive accuracy has a sample complexity of $\Theta(k\log k)$, requiring $\Theta(\log^2 k)$ more samples than Shannon entropy and correcting a prior $\Theta(k/\log k)$ characterization. For integer orders $\alpha$ ($2 \le \alpha \le c0 \log k$), it establishes matching bounds of $\Theta(\alpha k^{1-1/\alpha})$, showing the factor $\alpha$ is unavoidable.
More from Research
- Visualizing GANs: Interactive Diagram Explains Adversarial Training — ProfTomYeh · 2026-08-19
- Study: Short videos power down the brain's control network — alex_verem · 2026-08-19
- Microsoft's Agent Lightning boosts SWE-bench score to 56.4% with 6K samples — omarsar0 · 2026-08-19
- ReForce introduces force-aware retargeting for robot teleoperation — chris_j_paxton · 2026-08-19
- GLM Beats Grok in Path Error: Robot Controller Benchmark Comparison — MaziyarPanahi · 2026-08-19
- Animation showcases Tilted ERM for robustness from ICLR 2021 — abeirami · 2026-08-19