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.
We have recently shown [Javamard, Montanari, Ricci-Tersenghi, 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 high-dimensional statistical problems.
I will dedicate a particular attention to 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/