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

Speaker: 
Afonso S. Bandeira, PACM Graduate Student - Princeton University
Date: 
Oct 1 2014 - 3:00pm
Event type: 
IDeAS
Room: 
110 Fine Hall
Abstract: 

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.