# The Broad Optimality of Profile Maximum Likelihood

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2019.

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

- [Finite-Sample Symmetric Mean Estimation with Fisher Information Rate](https://mlsanity.com/paper/2306.16573/) (2023)
- [Learning to be a Statistician: Learned Estimator for Number of Distinct Values](https://mlsanity.com/paper/2202.02800/) (2022)
- [On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood](https://mlsanity.com/paper/2210.06728/) (2022)
- [Anonymized Histograms in Intermediate Privacy Models](https://mlsanity.com/paper/2210.15178/) (2022)
- [Testing Support Size More Efficiently Than Learning Histograms](https://mlsanity.com/paper/2410.18915/) (2024)

## Abstract (arXiv)

We study three fundamental statistical-learning problems: distribution estimation, property estimation, and property testing. We establish the profile maximum likelihood (PML) estimator as the first unified sample-optimal approach to a wide range of learning tasks. In particular, for every alphabet size k and desired accuracy varepsilon: Distribution estimation Under ℓ1 distance, PML yields optimal Theta(k/(varepsilon2log k)) sample complexity for sorted-distribution estimation, and a PML-based estimator empirically outperforms the Good-Turing estimator on the actual distribution; Additive property estimation For a broad class of additive properties, the PML plug-in estimator uses just four times the sample size required by the best estimator to achieve roughly twice its error, with exponentially higher confidence; boldsymbolα-R'enyi entropy estimation For integer α>1, the PML plug-in estimator has optimal k1-1/α sample complexity; for non-integer α>3/4, the PML plug-in estimator has sample complexity lower than the state of the art; Identity testing In testing whether an unknown distribution is equal to or at least varepsilon far from a given distribution in ℓ1 distance, a PML-based tester achieves the optimal sample complexity up to logarithmic factors of k. Most of these results also hold for a near-linear-time computable variant of PML. Stronger results hold for a different and novel variant called truncated PML (TPML).