pipette
ENEnglish

Birthday Estimators Are Uniformly Optimal for Renyi Entropy

Maciej Sk\'orski

Preprint

En palabras de los autores

Collisions are a basic probe of unknown distributions, used for testing and for counting substructures in graphs, and they underlie R\'enyi entropy, a fundamental measure of uncertainty with applications in cryptography, machine learning, physics, and biology. Motivated by this, we study the natural birthday estimator. We prove Bernstein-type concentration for it and show that it is minimax optimal, uniformly and jointly in alphabet size, order, accuracy, and confidence, with no sample splitting, clipping, or median aggregation. This, in particular, settles the sample complexity of integer-order R\'enyi entropy estimation up to absolute constants in all regimes, closing the gap between the best known upper and lower bounds. Our concentration bound rests on a sensitivity analysis of collision count, and the matching lower bound on a sharp analysis of detecting a hidden spike in a plateau distribution.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.