Moses Charikar
Efficient Profile Maximum Likelihood for Universal Symmetric Property
Estimation
Symmetric properties of distributions arise in multiple settings. For
each of these, separate estimators and analysis techniques have been
developed. Recently, Orlitsky et al showed that a single estimator
that maximizes profile maximum likelihood (PML) is sample competitive
for all symmetric properties. Further, they showed that even a
2^{n^{1-delta}}-approximate maximizer of the PML objective can serve
as such a universal plug-in estimator. (Here n is the size of the
sample). Unfortunately, no polynomial time computable PML estimator
with such an approximation guarantee was known. We provide the first
such estimator and show how to compute it in time nearly linear in
n. We also present some preliminary experimental results.
Joint work with Kiran Shiragur and Aaron Sidford.