Wednesday, October 15, 2014
4:00 PM -
5:00 PM
Annenberg 213
Special Seminar in Computing + Mathematical Sciences
Average-case tightness of semidefinite relaxations of maximum likelihood estimation problems
Afonso Bandeira,
Program in Applied and Computational Mathematics,
Princeton University,
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.
Event Sponsors:
For more information, please contact Sydney Garstang by email at [email protected].