Speaker: Professor Andrea Montanari, Stanford University

Title: Phase transitions in semi-definite relaxations

Abstract: Statistical inference problems arising within signal processing, data mining, and machine learning naturally give rise to hard combinatorial optimization problems. These problems become intractable when the dimensionality of the data is large, as is often the case for modern datasets. A popular idea is to construct convex relaxations of these combinatorial problems, which can be solved efficiently for large scale datasets. Semidefinite programming (SDP) relaxations are among the most powerful methods in this family, and are surprisingly well-suited for a broad range of problems where data take the form of matrices or graphs. It has been observed several times that, when the `statistical noise' is small enough, SDP relaxations correctly detect the underlying combinatorial structures.

I will present a few asymptotically exact predictions for the `detection thresholds' of SDP relaxations, with applications to synchronization and community detection. Apart from being successful in theory, SDP-based methods can be implemented on large instances: I will discuss an implementation that can be used to cluster graphs of size 10^5 in a matter of minutes. [Based on Joint work with Adel Javanmard, Federico Ricci-Tersenghi and Subhabrata Sen]

List of Distinguished Speaker Seminars.