- Series
- Stochastics Seminar
- Time
- Thursday, October 17, 2019 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Alex Wein – New York University – awein@cims.nyu.edu – https://cims.nyu.edu/~aw128/
- Organizer
- Vladimir Koltchinskii
High-dimensional inference problems such as sparse PCA and planted clique often exhibit statistical-vs-computational tradeoffs whereby there is no known polynomial-time algorithm matching the performance of the optimal estimator. I will discuss an emerging framework -- based on the so-called low-degree likelihood ratio -- for precisely predicting these tradeoffs and giving rigorous evidence for computational hardness in the conjectured hard regime. This method was originally proposed in a sequence of works on the sum-of-squares hierarchy, and the key idea is to study whether or not there exists a low-degree polynomial that succeeds at a given statistical task.
In the second part of the talk, I will give an application to the algorithmic problem of finding an approximate ground state of the SK (Sherrington-Kirkpatrick) spin glass model. I will explain two variants of this problem: "optimization" and "certification." While optimization can be solved in polynomial time [Montanari'18], we give rigorous evidence (in the low-degree framework) that certification cannot be. This result reveals a fundamental discrepancy between two classes of algorithms: local search succeeds while convex relaxations fail.
Based on joint work with Afonso Bandeira and Tim Kunisky (https://arxiv.org/abs/1902.07324 and https://arxiv.org/abs/1907.11636).