Optimal Rényi and Logarithmic Additive Functional Entropy Estimation
Abstract
We characterize the minimax sample complexity of estimating Rényi entropy from independent samples on an alphabet of size at most k, when the known order α>1 may vary with k. For every fixed additive accuracy ε∈(0,1/2) and success probability 2/3, we prove matching bounds with constants independent of k and α. For 1<α<log k, the rate is Θε(αk1−1/αXα(k,ε)), where a monotone scalar inequality defines Xα at noninteger orders. The bounds remain uniform as the order approaches one or an integer, or grows with the alphabet. Integer orders below log k have rate Θε(αk1−1/α); orders at least log k and min-entropy have rate Θε(klog k). We extend the analysis to logarithms of positive additive functionals. For every fixed continuous f satisfying f(0)=0, f(x)>0 for x>0, and f(x)∼ axr at zero, with a>0 and r>1, estimating −β−1log∑i f(pi) at fixed accuracy, for fixed β>0, has sample complexity Θ(k1−1/r) for integer r and Θ(k/log k) otherwise. A replication reduction preserves the sampling experiment and transfers the rates for powers. Smooth flat functions show that regularity alone does not determine the complexity. The upper bound combines polynomial approximation, Gamma count statistics, and an independent pilot, with a global affine correction near order one. The lower bound uses interpolation to construct positive mean-one priors and controls their distinguishability and entropy separation after normalization. Exact count-variance identities and weighted approximation duality connect the two arguments.
Related
- Optimal von Neumann Entropy Estimation
- Optimal Linear Functional Estimation for Proportionally High-Dimensional Linear Models
- Optimal estimation for Functional Linear Regression with Noisy Discretized Data
- Optimal estimation and goodness-of-fit testing of the mean for sparse longitudinal functional data
- A finite-strain logarithmic viscoelastic model for Antarctic ice shelves based on an additive split
BibTeX
@misc{adibi2026optimal,
title = {{Optimal Rényi and Logarithmic Additive Functional Entropy Estimation}},
author = {Arman Adibi and Piotr Krysta},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28999},
eprint = {2610.28999},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28999},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Rényi and Logarithmic Additive Functional Entropy Estimation
AU - Arman Adibi
AU - Piotr Krysta
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28999
UR - https://arxiv.org/abs/2610.28999
AB - We characterize the minimax sample complexity of estimating Rényi entropy from independent samples on an alphabet of size at most k, when the known order α>1 may vary with k. For every fixed additive accuracy ε∈(0,1/2) and success probability 2/3, we prove matching bounds with constants independent of k and α. For 1<α<log k, the rate is Θ_ε(αk^1−1/αX_α(k,ε)), where a monotone scalar inequality defines X_α at noninteger orders. The bounds remain uniform as the order approaches one or an integer, or grows with the alphabet. Integer orders below log k have rate Θ_ε(αk^1−1/α); orders at least log k and min-entropy have rate Θ_ε(klog k). We extend the analysis to logarithms of positive additive functionals. For every fixed continuous f satisfying f(0)=0, f(x)>0 for x>0, and f(x)∼ ax^r at zero, with a>0 and r>1, estimating −β^−1log∑_i f(p_i) at fixed accuracy, for fixed β>0, has sample complexity Θ(k^1−1/r) for integer r and Θ(k/log k) otherwise. A replication reduction preserves the sampling experiment and transfers the rates for powers. Smooth flat functions show that regularity alone does not determine the complexity. The upper bound combines polynomial approximation, Gamma count statistics, and an independent pilot, with a global affine correction near order one. The lower bound uses interpolation to construct positive mean-one priors and controls their distinguishability and entropy separation after normalization. Exact count-variance identities and weighted approximation duality connect the two arguments.
ER -