The first Princeton meeting will be on Monday Sept 19, 1:30pm-4:20pm, location TBA
In this graduate seminar we will cover recent research on the use of mathematical programming for problems arising from optimization, machine learning, computational complexity and more, with a particular focus on the Parrilo-Lasserre “Sum of Squares” semidefinite programming hierarchy. We will discuss both lower and upper bounds, as well as how such mathematical programs give rise to a general theory of computational difficulty, computation vs. sample size tradeoffs, and computational analogs of Bayesian probabilities.
More concretely, we will touch some of the following topics:
However, this is a fast moving research area and our plans may change as new results, as well as new understandings of old results, come to light. The course will not require much mathematical background beyond so called “mathematical maturity”. However, some familiarity with notions such as convexity, linear programming duality, separation oracles, eigenvalues/eigenvectors and positive semidefiniteness, could be helpful.
See this blog post for a longer introduction to this course.
|Lecture no.||Date/Place||Lecture notes / pre-reading||Notes / Homeworks||Videos|
|1||9.9 at MIT||pre-reading and exercises, introduction , Lecture 1: definitions||Lecture 1 slides||lecture 1 video|
|2||9.17 at Harvard||Pre-reading: max-cut (html ) , Cheeger ( html ) , Grothendieck ( html )||–||lecture 2 video|
|3||Monday 5pm 9.26 at Harvard 60 Oxford St Room 330||Lower bounds for max cut ( html ), Lower bounds for CSPs ( html ), Raghavendra’s theorem ( html )||–||Lecture 3 video|
|4||9.30 at MIT||ARV algorithm ( html )||–||Video|
|5||10.14 at Harvard (MD G125)||Bayesian view (html ) General sos ( html ) Planted clique ( html )||–||video|
|6||10.21 at Harvard (MD G125)||Symmetric SOS and flag algebras||–||Lecture 6 video|
|7||10.28 at MIT||Optimizing vectors over the sphere ( html ) Planted sparse vector problem ( html ) Tensor decomposition (html ) Dictionary learning ( html )||lecture 7 video|
|8||11.4 at MIT||Quantum entanglement, log rank conjecture, and sos||Lecture 8 video|
|9||Monday 5pm 11.14 at Harvard 60 Oxford St Room 330||sos and the unique games conjecture: a love-hate relationship ( html ) small set expansion problem ( html )||video|
|10||11.18 at Harvard (MD G125)||On the optimality of sos ( html ) Digression to multiplicative weights ( html ) Lee-Raghavendra-Steurer Theorem ( html)||–||lecture video|
|11||12.2 at MIT||Beyond SOS? summary of course||–|