Title: Approximating Profile Maximum Likelihood Efficiently: New Bounds on the Bethe Permanent

Description: Speaker: Kiran Shiragur

Time: Wednesday, 08 January 2020, 2:00pm
Venue: CC 109

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. The PML objective is related to the permanent of a certain Vandermonde matrix. A surprising connection between the convex relaxation we introduce and the Bethe free energy approximation originating in statistical physics leads to new bounds on the Bethe permanent of non-negative matrices.

This is in joint work with Moses Charikar and Aaron Sidford

Speaker Profile:
Kiran Shiragur is a PhD student at Stanford university. His area of research is operations research and theoretical computer science.


Rohit Gurjar

Date: Wednesday, 8 January, 2020
Time: 2:00pm IST
Access: Public
Category: Talk*
Created by: Department Calendar
Updated: Wednesday, 1 January, 2020 4:29am IST
Send Reminder: Yes  -  182 hours 51 minutes before start
Participants: Department Calendar
_NUC_department <all@cse.iitb.ac.in> (External User)