\ n

\n

\n

\nSymmetric proper ties of distributions arise in multiple settings. For each of these\, sepa rate estimators and analysis techniques have been developed. Recently\, Or litsky et al showed that a single estimator that maximizes profile maximum likelihood (PML) is sample competitive for all symmetric properties. Furt her\, 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 PM L 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.

\n

\nJoint work with Kiran Shiragur and Aaron Sidford.

\n

\ n

\nMoses Charikar is a professor of Computer Scie nce at Stanford University. He obtained his PhD from Stanford in 2000\, sp ent a year in the research group at Google\, and was on the faculty at Pri nceton from 2001-2015. He is broadly interested in approximation algorithm s (especially the power of mathematical programming approaches)\, metric e mbeddings\, algorithmic techniques for big data\, efficient algorithms for computational problems in high-dimensional statistics and optimization pr oblems in machine learning. He won the best paper award at FOCS 2003 for h is work on the impossibility of dimension reduction\, the best paper award at COLT 2017 and the 10 year best paper award at VLDB 2017. He was jointl y awarded the 2012 Paris Kanellakis Theory and Practice Award for his work on locality sensitive hashing inspired by random hyperplane rounding\, an d was named a Simons Investigator in theoretical computer science in 2014.

\n

\n