# Estimation of discrete distributions with high probability under chi2-divergence

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 33 references that are in the map.
- First posted on arXiv 29 Oct 2025.

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

- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Large Language Models Struggle to Learn Long-Tail Knowledge](https://mlsanity.com/paper/2211.08411/) (2022)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Estimation of discrete distributions in relative entropy, and the deviations of the missing mass](https://mlsanity.com/paper/2504.21787/) (2025)
- [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)

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

- [Token-Efficient Change Detection in LLM APIs](https://mlsanity.com/paper/2602.11083/) (2026)

## Abstract (arXiv)

We investigate the high-probability estimation of discrete distributions from an iid sample under chi2-divergence loss. Although the minimax risk in expectation is well understood, its high-probability counterpart remains largely unexplored. We provide sharp upper and lower bounds for the classical Laplace estimator, showing that it achieves optimal performance among estimators that do not rely on the confidence level. We further characterize the minimax high-probability risk for any estimator and demonstrate that it can be attained through a simple smoothing strategy. Our analysis highlights an intrinsic separation between asymptotic and non-asymptotic guarantees, with the latter suffering from an unavoidable overhead. This work sharpens existing guarantees and advances the theoretical understanding of divergence-based estimation.