Poster
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood
Moses Charikar · Zhihao Jiang · Kirankumar Shiragur · Aaron Sidford
Hall J (level 1) #817
Keywords: [ profile maximum likelihood ] [ symmetric property estimation ] [ property estimation ]
Abstract:
We provide an efficient unified plug-in approach for estimating symmetric properties of distributions given independent samples. Our estimator is based on profile-maximum-likelihood (PML) and is sample optimal for estimating various symmetric properties when the estimation error . This result improves upon the previous best accuracy threshold of 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 -Lipschitz property when .
Chat is not available.