[Ml-stat-talks] FW: IDeAS Seminar Wed. 1/21/15 (Afonso Bandeira)

Amir Ali Ahmadi a_a_a at princeton.edu
Mon Jan 19 21:01:32 EST 2015

Dear all,

The talk below may be of interest. It is a practice job talk by Afonso Bandeira of our PACM department who is a hot candidate on the market this year.


From: Afonso Bandeira [afonsobandeira at gmail.com]
Sent: Monday, January 19, 2015 6:55 PM
To: Amir Ali Ahmadi
Subject: Fwd: IDeAS Seminar Wed. 1/21/15

---------- Forwarded message ----------
From: Valerie Marino <vmarino at math.princeton.edu>
Date: Thu, Jan 15, 2015 at 9:06 AM
Subject: IDeAS Seminar Wed. 1/21/15

DATE: Wednesday January 21, 2015


PLACE: 110 Fine Hall

TIME: 3:00 pm

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

TITLE: Tightness of convex relaxations for certain inverse problems on graphs


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 relaxations
based on semidefinite programming (SDP) are among the most popular. We
will focus our attention on a certain class of graph-based inverse
problems and show a couple of remarkable phenomena.

In some instances of these problems (such as community detection under
the stochastic block model) the solution to the SDP matches the ground
truth parameters (i.e. achieves exact recovery) for information
theoretically optimal regimes. This is established using new
nonasymptotic bounds for the spectral norm of random matrices with
independent entries.

On other instances of these problems (such as angular
synchronization), the MLE itself tends to not coincide with the ground
truth (although maintaining favorable statistical properties).
Remarkably, these relaxations are often still tight (meaning that the
solution of the SDP matches the MLE). For angular synchronization we
can understand this behavior by analyzing the solutions of certain
randomized Grothendieck problems. However, for many other problems,
such as the multireference alignment problem in signal processing,
this remains a fascinating open problem.

Afonso S. Bandeira
Program in Applied and Computational Mathematics,
Princeton University

More information about the Ml-stat-talks mailing list