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
Contents: This seminar will be about quadratic
optimization over the hypercube, in particular the
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
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
- 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
- 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,
- 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.
- 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))
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),
- 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.
- 11 (14.05 -> 28.05) ** Sherrington-Kirkpatrick:
Computational Hardness of Upper Bound: Main result
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.