On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood
Abstract
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 $\epsilon \gg n^{-1/3}$. This result improves upon the previous best accuracy threshold of $\epsilon \gg n^{-1/4}$ achievable by polynomial time computable PML-based universal estimators \cite{ACSS20, ACSS20b}. Our estimator reaches a theoretical limit for universal symmetric property estimation as \cite{Han20} 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 $\epsilon \ll n^{-1/3}$.
Cite
Text
Charikar et al. "On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood." Neural Information Processing Systems, 2022.Markdown
[Charikar et al. "On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood." Neural Information Processing Systems, 2022.](https://mlanthology.org/neurips/2022/charikar2022neurips-efficient/)BibTeX
@inproceedings{charikar2022neurips-efficient,
title = {{On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood}},
author = {Charikar, Moses and Jiang, Zhihao and Shiragur, Kirankumar and Sidford, Aaron},
booktitle = {Neural Information Processing Systems},
year = {2022},
url = {https://mlanthology.org/neurips/2022/charikar2022neurips-efficient/}
}