ANC Seminar: Federico RicciTersenghi, Deptartment of Physics, Universita Sapienza
Phase Transitions in Semidefinite Relaxations (a fast & robust algorithm for community detection)
What 


When 
Feb 02, 2016 from 11:00 AM to 12:00 PM 
Where  IF Room 4.31/4.33 
Add event to calendar 
vCal iCal 
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 wellsuited for a broad range of problems where data take the form of matrices or graphs.
We have recently shown [Javamard, Montanari, RicciTersenghi, arxiv:1511.08769] how to compute detection thresholds for SDP relaxations and the corresponding estimation error by mapping the problem to statistical mechanics models with vector spins in the limit of a large number of spin components.
We have studied some classical SDP relaxations for statistical problems motivated by graph synchronization and community detection in networks.
Our results clarify the effectiveness of SDP relaxations in solving highdimensional statistical problems.
I will mainly discuss the problem of community detection in sparse graphs for which we have shown SDP relaxation to be quasi optimal. A robust and fast algorithm inspired by the SDP relaxation is presented, which is able to detect communities in very large graphs. The code is publicly available at http://web.stanford.edu/~montanar/SDPgraph/