View all Seminars  |  Download ICal for this event

The Bethe and Sinkhorn Permanents of Structured Matrices and its Implications for Profile Maximum Likelihood

Series: Department Seminar

Speaker: Mr. Kiran Shiragur Ph.D student Stanford University USA

Date/Time: Dec 27 16:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor:

Here we consider the problem of computing the likelihood of the profile of a discrete distribution, i.e. the probability of observing the multiset of element frequencies, and computing a profile maximum likelihood (PML) distribution, i.e. a distribution with the maximum profile likelihood. For each problem we provide polynomial time algorithms that given $n$ i.i.d samples from a discrete distribution, achieve an approximation factor of $expleft(-O(sqrt{n} log n) right)$, improving upon the previous best-known bound achievable in polynomial time of $exp(-O(n^{2/3} log n))$ (Charikar, Shiragur and Sidford, 2019). Through the work of Acharya, Das, Orlitsky and Suresh (2016), this implies a polynomial time universal estimator for symmetric properties of discrete distributions in a broader range of error parameter. We achieve these results by providing new bounds on the quality of approximation of the Bethe and Sinkhorn permanents (Vontobel, 2012 and 2014). We show that each of these are $exp(O(k log(N/k)))$ approximations to the permanent of $N times N$ non-negative matrices with at most $k$ distinct columns, improving upon the previous known bounds of $exp(O(N))$. To obtain our results on PML, we exploit the fact that the PML objective is proportional to the permanent of a certain Vandermonde matrix with $sqrt{n}$ distinct columns. As a by-product of our work we establish a surprising connection between the convex relaxation in prior work (CSS19) and the well-studied Bethe and Sinkhorn approximations. This is in joint work with Moses Charikar and Aaron Sidford.

Speaker Bio:
Kiran Shiragur is a fourth year PhD student at Stanford University co-advised by Prof. Moses Charikar and Prof. Aaron Sidford. His primary research interests lie in learning theory, algorithmic statistics and optimization. Prior to Stanford, he obtained his masters degree from Indian Institute of Science. He also spent a year at Microsoft Research India as a research fellow.

Host Faculty: Dr. Anand Louis