[Ml-stat-talks] IDeAS Seminar today at 3:00 pm

Amit Singer amits at math.Princeton.EDU
Wed Oct 1 12:48:35 EDT 2014

DATE: Wednesday  October 1 , 2014


PLACE: 110 Fine Hall 

TIME: 3:00 pm 

SPEAKER: Afonso S. Bandeira, PACM Graduate Student - Princeton University.

TITLE: Average-case tightness of semidefinite relaxations of maximum
likelihood estimation problems

Many maximum likelihood estimation problems are known to be
intractable in the worst case. A common approach is to consider convex
relaxations of the maximum likelihood estimator (MLE), and
semidefinite relaxations are among the most popular. Fortunately,
there are many instances for which, under random models, the solution
to the semidefinite programming relaxation can be shown to recover the
ground truth parameters. Perhaps more remarkable is that these
relaxations are often tight (meaning that their solution exactly
recovers the MLE) even when the MLE does not coincide with the ground
truth. We treat graph clustering and angular synchronization problems
as illustrative examples of this phenomenon. This average case
analysis of the MLE is achieved by analyzing the solutions of certain
randomized Grothendieck problems. 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/ml-stat-talks/attachments/20141001/a5a08a67/attachment.html>

More information about the Ml-stat-talks mailing list