Timezone: »

 
Poster
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood
Moses Charikar · Zhihao Jiang · Kirankumar Shiragur · Aaron Sidford

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #817
in Poster Session 1 »
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}$.
Keywords: profile maximum likelihood · symmetric property estimation · property estimation
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Moses Charikar (Stanford University)
Zhihao Jiang (Stanford University)
Kirankumar Shiragur (MIT and Broad Institute)
Aaron Sidford (Stanford)

More from the Same Authors