# Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 39 references that are in the map.
- First posted on arXiv 23 Jul 2025.

## Builds on (most cited first, 8 of 8)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu](https://mlsanity.com/paper/2011.04144/) (2020)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Concentration Bounds for Discrete Distribution Estimation in KL Divergence](https://mlsanity.com/paper/2302.06869/) (2023)
- [Estimation of discrete distributions in relative entropy, and the deviations of the missing mass](https://mlsanity.com/paper/2504.21787/) (2025)

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

- [Ratio Covers of Convex Sets and Optimal Mixture Density Estimation](https://mlsanity.com/paper/2602.16142/) (2026)
- [Minimax Optimality of Score-Entropy Discrete Diffusion](https://mlsanity.com/paper/2608.20635/) (2026)
- [Estimation of discrete distributions with high probability under chi2-divergence](https://mlsanity.com/paper/2510.25400/) (2025)
- [Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size](https://mlsanity.com/paper/2610.07655/) (2026)

## Abstract (arXiv)

We consider the fundamental problem of estimating a discrete distribution on a domain of size K with high probability in Kullback-Leibler divergence. We provide upper and lower bounds on the minimax estimation rate, which show that the optimal rate is between big(K + ln(K)ln(1/δ)big) /n and big(Klnln(K) + ln(K)ln(1/δ)big) /n at error probability δ and sample size n, which pins down the rate up to the doubly logarithmic factor ln ln K that multiplies K. Our upper bound uses techniques from online learning to construct a novel estimator via online-to-batch conversion. Perhaps surprisingly, the tail behavior of the minimax rate is worse than for the squared total variation and squared Hellinger distance, for which it is big(K + ln(1/δ)big) /n, i.e. without the ln K multiplying ln (1/δ). As a consequence, we cannot obtain a fully tight lower bound from the usual reduction to these smaller distances. Moreover, we show that this lower bound cannot be achieved by the standard lower bound approach based on a reduction to hypothesis testing, and instead we need to introduce a new reduction to what we call weak hypothesis testing. We investigate the source of the gap with other divergences further in refined results, which show that the total variation rate is achievable for Kullback-Leibler divergence after all (in fact by he maximum likelihood estimator) if we rule out outcome probabilities smaller than O(ln(K/δ) / n), which is a vanishing set as n increases for fixed K and δ. This explains why minimax Kullback-Leibler estimation is more difficult than asymptotic estimation.