401-3940-20L  Student Seminar in Mathematics and Data: Optimization of Random Functions
(Spring 2020, ETHZ)

Afonso S. Bandeira

Meets: Thu 13-15 at HG G 3

 Office Hours: Posted weekly
 
Piazza page available here.

Topic choice poll here.
Contents: This seminar will be about quadratic optimization over the hypercube, in particular the problem:
Given A an n*n matrix, find max_x x^TAx where x is constrained to be an n-dimensional vector taking values -1 or +1.
We will start with approximation algorithm for deterministic, but structured, matrices A. Then move to random instances corresponding to inverse problems in graphs, and end with the state of the art in understanding this optimization problem for a matrix A with iid gaussian entries. Not all papers are written in the context of this optimization problem, but you will see that all of them are analyzing version of this problem (with different structure, or distribution, of A). I think this list of papers tells a story I like very much, hope you also enjoy it!

 Format: The first meeting will be solely about logistics. In the remaining 12 meetings, each of the 12 students will lead the discussion on one of the 12 topics described below. Many of the papers below are not written in the context of this optimization problem, but you will see that all of them are analyzing a version of this problem (with different structure or distribution). Each student should prepare a presentation of around 40-50 minutes, the rest of the time will be spent with questions and discussion; or presentations on related topics.

Please sign up for your topic here. I tried to give a rough estimation of difficulty of each topic, giving them * for the easier ones, and *** for the hardest. This is of course a rough estimate (and difficulty is not very well defined).
If you prefer, feel free to use a pseudonym on the doodle poll and email me to let me know the pseudonym belongs to you.

I am here to help: If you have any question, want to discuss a problem, a question about one of the papers, or brainstorm about any research idea, just stop by office hours or email me and we'll schedule a time to meet.
Feedback: Also, if you have any comment or feedback on the class please let me know, submit a comment to this google form (or in person, or through email). Having direct feedback from you is the best way for me to organize the seminar you like! (keep in mind that I don't know who sent me the comment or feedback and there is no way for me to answer, for questions use piazza or email, piazza tends to receive replies faster).

List of Papers/Topics: 
  • 1 (27.02)  * Goemans-Williamson Approximation of Max-Cut: Description of the Semidefinite Programming Algorithm for Approximating Max-Cut proposed and analyzed here: M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefine programming. Journal of the Association for Computing Machinery, 42:1115–1145, 1995. This is also describe in Section 8.1. of my Lecture Notes, and in many other places online. (Notice that this corresponds to the case where A is the Laplacian of a graph).
  • 2 (05.03)  * Little Grothendieck Inequality: The goal here is to give an approximation ratio (similar to the one above) when A is positive semidefinite. A good place to read this argument, and a discussion about their connection to a celebrated inequality of Grothendieck, is N. Alon and A. Naor. Approximating the cut-norm via Grothendieck’s inequality. In Proc. of the 36 th ACM STOC, pages 72–80. ACM Press, 2004. see for example Section 5.2. here, or simply follow Problem 1.5 this this homework set.
  • 3 (12.03)  * Non-PSD little Grothendieck Inequality: In M. Charikar and A. Wirth. Maximizing Quadratic Programs: Extending Grothendieck's Inequality. FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004 a (non-constrant) approximation ratio is obtained for general A. See, for example, Theorem 1 here.
  • 4 (19.03)  ** Random Matrix, BBP, and Z2 Synchronization: From here one we will treat random matrices A and show that the approximation ratios above are pessimistic when considering certain random matrices A. The idea is to consider A = vv^T + Gaussian noise and understand this optimization through random matrix theory. There are many good references, Sections 2 and 4.1. of this paper are a good reference (you would have to consider +1/-1 rather than unit norm complex numbers as in the paper, but this only makes things easier.  A. Singer. Angular synchronization by eigenvectors and semidefinite programming. Appl.
    Comput. Harmon. Anal., 30(1):20 – 36, 2011. For a -1/+1 discussion see Section 2.1. of this paper. Message-passing algorithms for synchronization problems over compact groups. A. Perry, A. S. Wein, A. S. Bandeira, A. Moitra. Communications on Pure and Applied Mathematics, 2018.
  • 5 (26.03)   ** Community Detection and the Stochastic Block Model: Partial Recovery: The Goal here is to describe the Stochastic Block Model and the Statistical Physics Predictions for partial recovery. A. Decelle, F. Krzakala, C. Moore, and L. Zdeborov´a. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E, 84, December 2011. When reading this, focus on just two communities. See also Section 9.2. and 9.3. of these Lecture Notes.
  • 6 (02.04)   *  Community Detection and the Stochastic Block Model: Exact Recovery: Main result of this paper. Focus only in the threshold, not the algorithms. Exact Recovery in the Stochastic Block Model. E. Abbe, A. S. Bandeira, G. Hall. IEEE Transactions on Information Theory, vol.62, no.1, pp.471-487, 2016.
  • SEMINARS AFTER THIS DATE WERE MOVED FORWARD BY A WEEK
  • 7 (09.04 -> 23.04)   *  Community Detection and the Stochastic Block Model: Semidefinite Program (SDP): Main result of this paper. A. S. Bandeira, Foundations of Computational Mathematics, Foundations of Computational Mathematics, 2018.
  • 8 (23.04 -> 30.04)   **  Sherrington-Kirkpatrick: Upper bound with Slepian: From here one we remove the ``planted structure'' and try to understand the problem with A simply being gaussian, meaning that there is no ``planted correct x''. This essentially follows a modified version of Problem 1.1. in this Homework, where x in the L2 sphere gets replaced by x taking values in +1/-1. The idea is to study problem (1) in this paper (see also reference therein). The value is given in (2). By following the proof outlined in the homework above you will prove a good upper bound on this. A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian. D. Kunisky and A. S. Bandeira
  • 9 (30.04 -> 07.05)   **  Sherrington-Kirkpatrick: True Value and Spectral algorithm: The goal here is to give an algorithm that produces a good answer. Start with a short description of how the true value is obtained (the value described in (2) of the paper mentioned above). A simple spectral algorithm is described in Example 1.1. namely (equations (5) and (6)) of this paper (look also at references therein). Computational Hardness of Certifying Bounds on Constrained PCA Problems. A. S. Bandeira, D. Kunisky, A. S. Wein. Innovations in Theoretical Computer Science (ITCS20), 2020.
  • 10 (07.05 -> 14.05) *  Sherrington-Kirkpatrick: SDP bound: The idea here is to give an upper bound based on semidefinite programming, this is done in this paper. Andrea Montanari and Subhabrata Sen. Semidefinite programs on sparse random graphs and their application to community detection. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 814–827. ACM, 2016. A description is also available in Theorem 1.8. in this paper. A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian. D. Kunisky and A. S. Bandeira
  • 11 (14.05 -> 28.05) ** Sherrington-Kirkpatrick: Computational Hardness of Upper Bound: Main result of this paper. Computational Hardness of Certifying Bounds on Constrained PCA Problems. A. S. Bandeira, D. Kunisky, A. S. Wein. Innovations in Theoretical Computer Science (ITCS20), 2020.
  • 12 (28.05) *** Sherrington-Kirkpatrick: ``Optimal'' algorithm: Main result in this paper. Optimization of the Sherrington-Kirkpatrick Hamiltonian. Andrea Montanari.