# Estimation of discrete distributions in relative entropy, and the deviations of the missing mass

arXiv: https://arxiv.org/abs/2504.21787 · HTML: https://mlsanity.com/paper/2504.21787/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2025.

## Built on by (most cited first, 4 of 4)

- [Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability](https://mlsanity.com/paper/2507.17316/) (2025)
- [Ratio Covers of Convex Sets and Optimal Mixture Density Estimation](https://mlsanity.com/paper/2602.16142/) (2026)
- [Estimation of discrete distributions with high probability under chi2-divergence](https://mlsanity.com/paper/2510.25400/) (2025)
- [Discrete Diffusion Models are Minimax Optimal Under Sparsity](https://mlsanity.com/paper/2610.19020/) (2026)

## Abstract (arXiv)

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 bounds on the expected risk 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 establishing its optimality among confidence-independent estimators. We then characterize the minimax-optimal high-probability risk and show that it is achieved by a simple confidence-dependent smoothing technique. Notably, the optimal non-asymptotic risk incurs an additional logarithmic factor compared to the ideal asymptotic rate. Next, motivated by regimes in which the alphabet size exceeds the sample size, we investigate methods that adapt to the sparsity of the underlying distribution. 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 our analysis, we also derive a sharp high-probability upper bound on the missing mass.