# Concentration Bounds for Discrete Distribution Estimation in KL Divergence

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 21 references that are in the map.
- First posted on arXiv 14 Feb 2023.

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

- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [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)

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

- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability](https://mlsanity.com/paper/2507.17316/) (2025)
- [Near-Optimal Degree Testing for Bayes Nets](https://mlsanity.com/paper/2304.06733/) (2023)
- [Ratio Covers of Convex Sets and Optimal Mixture Density Estimation](https://mlsanity.com/paper/2602.16142/) (2026)
- [On the KL-Divergence-based Robust Satisficing Model](https://mlsanity.com/paper/2408.09157/) (2024)
- [Online Episodic Convex Reinforcement Learning](https://mlsanity.com/paper/2505.07303/) (2025)
- [Limitations on Autoregressive Token Generation via Sequential Sampling](https://mlsanity.com/paper/2610.14615/) (2026)

## Abstract (arXiv)

We study the problem of discrete distribution estimation in KL divergence and provide concentration bounds for the Laplace estimator. We show that the deviation from mean scales as √k/n when n ≥ k, improving upon the best prior result of k/n. We also establish a matching lower bound that shows that our bounds are tight up to polylogarithmic factors.