Conferences - Seminars

  Thursday 13 December 2018 16:15 - 17:30 BC 420

IC Colloquium: Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation

By: Moses Charikar - Stanford University

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.

Moses Charikar is a professor of Computer Science at Stanford University. He obtained his PhD from Stanford in 2000, spent a year in the research group at Google, and was on the faculty at Princeton from 2001-2015. He is broadly interested in approximation algorithms (especially the power of mathematical programming approaches), metric embeddings, algorithmic techniques for big data, efficient algorithms for computational problems in high-dimensional statistics and optimization problems in machine learning. He won the best paper award at FOCS 2003 for his 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 jointly awarded the 2012 Paris Kanellakis Theory and Practice Award for his work on locality sensitive hashing inspired by random hyperplane rounding, and was named a Simons Investigator in theoretical computer science in 2014.

More information

Contact Host: Michael Kapralov

Accessibility General public

Admittance Free

This event is internal