Spring 2022: Sum-of-Squares Optimization (CPSC 663)

Course Description

This course is a survey of sum-of-squares (SOS) polynomial proofs and their applications in and connections to various fields of mathematics and computer science. SOS proofs try to bound polynomial optimization problems or show that polynomial systems of equations cannot be solved by using the fact that squared polynomials are non-negative. While this may sound simple or a bit naive, in fact searching for SOS proofs has turned out to be a powerful algorithmic technique that is now ubiquitous in theoretical computer science.

The course will be organized in four parts.

Part 1: The mathematical history of algebraic proofs, including Hilbert's "Nullstellensatz" and 17th problem, classical moment problems, and more recent "Positivstellensatz" results.

Part 2: Recent developments relating SOS proofs to questions in optimization and computer science. We will see how to search for SOS proofs using semidefinite programming, and how such algorithms have yielded theoretical breakthroughs for many problems of current interest.

Part 3: Lower bounds against these algorithms, which give some of the strongest evidence we have of computational hardness, especially for high-dimensional random problems coming from combinatorial optimization, statistics, and machine learning.

Part 4: Some further results that situate SOS algorithms in the "big picture" of computation and the theory of algorithms. In particular, we might look at the efficiency of SOS and recent work seeking to make SOS-based algorithms faster, comparisons between SOS and other convex relaxations, and/or perspectives on SOS from convex geometry.

Contact & Office Hours

The best way to contact me is by email, at dmitriy [dot] kunisky [at] yale.edu.

Office hours will be held by appointment at least for the first two weeks, while classes are online. Email me to schedule a time to talk. We will discuss choosing a time for regular office hours at our first in-person meeting. My office is Room 337 at 17 Hillhouse Avenue (YINS, the Yale Institute for Network Science); outside office hours and appointments, you're welcome to try your luck finding me there.

Schedule

Class will meet Mondays and Wednesdays, 1pm to 2:15pm. In-person classes will be held in the Watson Center (WTS), Room A68. (Please note this is not Watson Hall (AKW)!)

A few details concerning the start of the semester:

  • Per university policy, our first meeting will be on Wednesday, January 26 instead of January 19.
  • We will have a meeting on Friday, January 28, when classes meet on a Monday schedule.
  • Also per university policy, we will hold the course meetings marked in  pale blue  online. For Zoom links, see the Canvas page.

Below is a tentative schedule, to be updated as the semester progresses.

Date Details
Week 1
Jan 26 Course logistics + an invitation to SOS for computer scientists (approximating MaxCut and the Goemans-Williamson relaxation through the lens of SOS)
[Zoom Blackboard Notes]
Jan 28 History I: theorems about certificates, Hilbert's results and 17th problem, Motzkin's polynomial, Artin's theorem and other results on global SOS proofs
[Zoom Blackboard Notes]
Week 2
Jan 31 History II: The "Positivstellensatz" results of Krivine, Stengle, Schmudgen, Putinar, and other variations for SOS proofs with constraints
[Zoom Blackboard Notes]
Feb 2 Lasserre and Parrilo formulations of bounded degree SOS optimization as a semidefinite program + Goemans-Williamson revisited
[Zoom Blackboard Notes]
Week 3
Feb 7 Introduction to the "proofs to algorithms" technique + Planted sparse vector I
Feb 9 Planted sparse vector II
Week 4
Feb 14 The "method of pseudomoments" + Tensor decomposition I
Feb 16 Tensor decomposition II
Week 5
Feb 21 Robust mean estimation I: background, multi-dimensional medians, and the Lugosi-Mendelson estimator construction
Feb 23 Robust mean estimation II: Hopkins' sum-of-squares algorithm
Week 6
Feb 28 First lower bounds: Grigoriev-Laurent lower bound for knapsack/parity
Mar 2 Knapsack/parity lower bound II
Week 7
Mar 7 Grigoriev-Schoenebeck lower bound for 3-XOR-SAT
Mar 9 3-XOR-SAT lower bound II
Week 8
Mar 14 Planted clique lower bound I: problem setting, basic algorithms, Feige-Krauthgamer degree 2 lower bound
Mar 16 Planted clique lower bound II: Feige-Krauthgamer moments, Kelner's polynomial, and the pseudocalibration relation
Week 9
Mar 21 Spring Break
Mar 23 Spring Break
Week 10
Mar 28 Planted clique lower bound III: deriving calibrated pseudomoments, truncation
Mar 30 Planted clique lower bound IV: fixing pseudocalibration and concentration results for constraints
Week 11
Apr 4 Planted clique lower bound V: introduction to graphical matrices
Apr 6 Planted clique lower bound VI: canonical factorization and sketch of positivity proof strategy
Week 12
Apr 11 Planted clique lower bound VII: wrapping up details of canonical factorization and last positivity proof ideas
Apr 13 Pseudocalibration to low-degree polynomial algorithms I
Week 13
Apr 18 Pseudocalibration to low-degree polynomial algorithms II: low-degree predictions in general Bernoulli models and the overlap parameter
Apr 20 Pseudocalibration to spectral algorithms I
Week 14
Apr 25 Pseudocalibration to spectral algorithms II
Apr 27 Student project presentations
Lecture Notes and Materials

You do not need to buy any books for this course. You can find the lecture notes here. I will try to make these as thorough as possible and to update them with each lecture's materials, probably with more elaboration than we have time for in class. In particular, the bibliography and list of open problems in the notes is a great place to look for project topics, in addition to the list below.

Assignments

Homework will be posted here, and is to be submitted to me by email, in PDF format produced with LaTeX, by the due date indicated. Please try to talk to me in advance if you need more time for an assignment. You do not need to solve all exercises in the notes—only those posted here. (But you are welcome to solve more, and might find it helps you internalize the material.)

Assigned Due Link and Details
Jan 4 Never

Assignment 0; Survey

A few problems for you to check that you're prepared for this course (they won't be graded), as well as a survey about your background and interests.
Feb 12 Mar 4

Assignment 1

Mar 14 Apr 4

Assignment 2

Apr 10 May 6

Assignment 3

Final Project

Most of your grade will be based on a final project, for which I would like you to read a substantial research paper, work on an open theoretical problem, or run an interesting numerical experiment, and make a short oral presentation and written report about what you find. You do not need to make a new discovery to get a good grade; I do, however, expect you to engage seriously with your topic—if you read a paper then try to present it in the most digestible way possible (even if that is different from what the authors wrote), if you work on a problem and get stuck then tell us what you think makes it difficult to make progress, and so forth.

Here are some possible topics and associated references, roughly grouped by theme. Any open problem or substantial reference from the notes will also work. I would also be glad to hear about further ideas that you've seen in the literature or where you think SOS might be relevant to your research (if you are doing other independent work). Email me if you have suggestions!

SOS Algorithms and Lower Bounds

  • SOS and the Unique Games Conjecture
    • [arXiv:1205.4484] Hypercontractivity, sum-of-squares proofs, and their applications. Boaz Barak, Fernando G.S.L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou.
  • Technicalities and applications of pseudocalibration
    • [arXiv:1604.03423] Graph matrices: Norm bounds and applications. Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin.
    • [arXiv:2009.01874] Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes. Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran.
    • [CCC 2021] SOS lower bound for exact planted clique. Shuo Pang.
  • "Equivalence" of SOS and spectral algorithms
    • [arXiv:1710.05017] The power of sum-of-squares for detecting hidden structures. Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer.
  • The local statistics hierarchy of algorithms for hypothesis testing problems
    • [arXiv:1911.01960] Local statistics, semidefinite programming, and community detection. Jess Banks, Prasad Raghavendra, and Sidhanth Mohanty.
    • [arXiv:2008.12237] Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs. Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein.
  • Differential privacy through SOS
    • [arXiv:2111.12981] Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid.

Real(ish) Applications of SOS

  • Control theory and dynamical systems
    • [Springer] Positive polynomials in control. Editors: Didier Henrion and Andrea Garulli.
    • [IEEE Design and Control 2002] On the construction of Lyapunov functions using the sum of squares decomposition. Antonis Papachristodoulou and Stephen Prajna.
    • [IEEE Design and Control 2003] Some controls applications of sum of squares programming. Zachary Jarvis-Wloszek, Ryan Feeley, Weehong Tan, Kunpeng Sun, and Andrew Packard.

This survey by Georgina Hall is a great starting point to look for more references about applications.

SOS as a Proof Assistant

  • Computing bounds on packing problems
    • [arXiv:1311.3789] A semidefinite programming hierarchy for packing problems in discrete geometry. David de Laat and Frank Vallentin.
    • [arXiv:1912.03373] Globally optimizing small codes in real projective spaces. Dustin G. Mixon and Hans Parshall.
  • Inequalities in probability theory
    • [SIAM J. Optim., 15(3)] Optimal inequalities in probability theory: a convex optimization approach. Dimitris Bertsimas and Ioana Popescu.
  • Rational coefficients
    • [Theoretical CS, 408(2)] Computing sum of squares decompositions with rational coefficients. Helfried Peyrl and Pablo Parrilo.
    • [J. Symbolic Computation 47(1)] Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients. Erich Kaltofen, Bin Li, Zhengfeng Yang, and Lihong Zhi.

Geometric and Algebraic Aspects of SOS

  • Length and complexity of SOS representations
    • [ICFST 2004] On the complexity of Hilbert's 17th problem. Nikhil Devanur, Richard Lipton, and Nisheeth Vishnoi.
    • [Book] Quadratic forms with applications to algebraic geometry and topology. Albrecht Pfister. (Let me know if you are looking for a copy of this.)
    • [Note] Pfister's theorem on sums of squares. Keith Conrad.
  • SOS in the presence of symmetry and applications of representation theory
    • [arXiv:1606.05639] Symmetric sums of squares over k-subset hypercubes. Annie Raymond, James Saunderson, Mohit Singh, and Rekha R. Thomas.
  • Non-commutative analogues of SOS and their applications