Search Mailing List Archives
[theory-seminar] Montanari speaks tomorrow 4PM in Applied Math Seminar
tim at cs.stanford.edu
Tue Dec 1 09:31:37 PST 2015
---------- Forwarded message ----------
From: Andrea Montanari <montanar at stanford.edu>
Date: Tue, Dec 1, 2015 at 8:54 AM
To: "tim at cs.stanford.edu" <tim at cs.stanford.edu>
I am giving this seminar in applied math. Perhaps some people in
CS might be interested.
Wednesday, December 2, 4pm: Applied Math Seminar, Sloan Math Center Room 384H
Andrea Montanari, Stanford Statistics and Electrical Engineering
"Phase transitions in semidefinite 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.
[Based on Joint work with Adel Javanmard, Federico Ricci-Tersenghi and
More information about the theory-seminar