On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood
This work provides an incremental improvement in universal symmetric property estimation for statistical inference, matching a known theoretical limit.
The paper tackles the problem of efficiently estimating symmetric properties of distributions from samples, improving the accuracy threshold for sample optimality from ε ≫ n^{-1/4} to ε ≫ n^{-1/3} using a profile-maximum-likelihood-based estimator.
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}$.