Estimation of discrete distributions in relative entropy, and the deviations of the missing mass
This work addresses statistical estimation challenges for discrete distributions, particularly in high-dimensional or sparse settings, with incremental improvements in risk bounds and adaptivity.
The paper tackles the problem of estimating discrete distributions with high-probability guarantees in relative entropy, showing that the Laplace estimator is optimal among confidence-independent methods and that optimal non-asymptotic risk includes an extra logarithmic factor. It also introduces a data-dependent smoothing estimator that adapts to distribution sparsity, with bounds depending on sparsity parameters and a sharp bound on missing mass.
We study the problem of estimating a distribution over a finite alphabet from an i.i.d. sample, with accuracy measured in relative entropy (Kullback-Leibler divergence). While optimal expected risk bounds are known, high-probability guarantees remain less well-understood. First, we analyze the classical Laplace (add-one) estimator, obtaining matching upper and lower bounds on its performance and showing its optimality among confidence-independent estimators. We then characterize the minimax-optimal high-probability risk, which is attained via a simple confidence-dependent smoothing technique. Interestingly, the optimal non-asymptotic risk exhibits an additional logarithmic factor over the ideal asymptotic risk. Next, motivated by scenarios where the alphabet exceeds the sample size, we investigate methods that adapt to the sparsity of the distribution at hand. We introduce an estimator using data-dependent smoothing, for which we establish a high-probability risk bound depending on two effective sparsity parameters. As part of the analysis, we also derive a sharp high-probability upper bound on the missing mass.