Birthday estimators achieve optimal accuracy for Renyi entropy measurement
Birthday Estimators Are Uniformly Optimal for Renyi Entropy
Information TheoryData Structures and Algorithms
Summary
Measuring uncertainty in data requires estimating something called Rényi entropy, which is essential in many fields like cryptography and biology. The authors studied a simple method called the birthday estimator, which counts repeated data points (collisions), to estimate this entropy. They proved that this approach is mathematically the best possible across many conditions, requiring the least amount of data to achieve accurate results. This finding settles long-standing questions about how hard it is to estimate Rényi entropy precisely.
What this means in practice
- •For cryptography engineers: Optimize randomness assessment tools by using a proven optimal method to measure entropy with minimal data.
- •For machine learning developers: Implement more efficient uncertainty quantification in models using the birthday estimator with guaranteed accuracy and confidence.
A theory result. No direct application yet.
Authors
Maciej Skórski
Abstract
Collisions are a basic probe of unknown distributions, used for testing and for counting substructures in graphs, and they underlie Rényi 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ényi 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.