# On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 42 references that are in the map.
- First posted on arXiv 13 Oct 2022.

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

- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation](https://mlsanity.com/paper/1905.08448/) (2019)
- [The Broad Optimality of Profile Maximum Likelihood](https://mlsanity.com/paper/1906.03794/) (2019)
- [Estimating Renyi Entropy of Discrete Distributions](https://mlsanity.com/paper/1408.1000/) (2014)
- [Approximate Profile Maximum Likelihood](https://mlsanity.com/paper/1712.07177/) (2017)
- [Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance](https://mlsanity.com/paper/1802.08405/) (2018)
- [Instance Based Approximations to Profile Maximum Likelihood](https://mlsanity.com/paper/2011.02761/) (2020)
- [A General Framework for Symmetric Property Estimation](https://mlsanity.com/paper/2003.00844/) (2020)
- [The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood](https://mlsanity.com/paper/2004.02425/) (2020)
- [On the High Accuracy Limitation of Adaptive Property Estimation](https://mlsanity.com/paper/2008.11964/) (2020)

## Abstract (arXiv)

We provide an efficient unified plug-in approach for estimating symmetric properties of distributions given n independent samples. Our estimator is based on profile-maximum-likelihood (PML) and is sample optimal for estimating various symmetric properties when the estimation error ε gg n-1/3. This result improves upon the previous best accuracy threshold of ε gg n-1/4 achievable by polynomial time computable PML-based universal estimators [ACSS21, ACSS20]. Our estimator reaches a theoretical limit for universal symmetric property estimation as [Han21] shows that a broad class of universal estimators (containing many well known approaches including ours) cannot be sample optimal for every 1-Lipschitz property when ε ll n-1/3.