Moses Charikar - Approximating Profile Maximum Likelihood Efficiently

From Katie Gentilello September 30th, 2019

24 plays 0 comments

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.

Joint work with Kiran Shiragur and Aaron Sidford.

Tags: algorithms and randomness centerarc colloquiumgeorgia techrecorded by gtlibraryfall 2019

name: Moses Charikar
Date: September 9th, 2019
Appears In: Open Scholarship

Comments
Related Media

Add a comment

Moses Charikar - Approximating Profile Maximum Likelihood Efficiently

Related Media