Description
Mathematical programming relaxations of integer programming formulations are a popular way to apply convex optimization techniques to hard combinatorial optimization problems. Such relaxations can be made closer to their integer programming counterparts by adding constraints; a systematic way to achieve this is via hierarchies of relaxations. Several such hierarchies are well-studied in the literature: Lovasz-Schrijver, Sherali-Adams and the Parrilo-Lasserre sum-of-squares (SoS) hierarchy.
Recently, these hierarchies have received a lot of attention due to their potential to make progress on long standing algorithmic questions, and connections to various other areas such as computational complexity, combinatorial and polynomial optimization, quantum computing, proof complexity and so on. This course we will cover recent research results in this area for problems arising from optimization, machine learning, computational complexity and more, discussing both lower and upper bounds.
Tentative Syllabus
- Introduction to Lovasz-Schrijver, Sherali-Adams and Parillo-Lasserre SoS hierarchies
- alternate viewpoints: locally consistent probability distributions (pseudo expectations), vector representations, proof systems, etc.
- Applications in approximation algorithms
- graph coloring, densest subgraph, sparsest cut, directed steiner tree, scheduling, graph partitioning via global correlation rounding
- Applications in machine learning:
- planted sparse vector, tensor decomposition, dictionary learning
- Lower bounds
- local-global phenomena in metric embeddings, proof complexity, unique games conjecture
- Extension complexity
- nonnegative factorization, postive semidefinite rank, communication complexity
Lecture Notes
- Lecture 1 Introduction and Overview
- Lecture 2 Lasserre Hierarchy - Introduction
- Lecture 3 Lasserre Hierarchy - Properties and Applications
- Lecture 4 Polynomial Optimization - Sum of Squares
- Lecture 5 Max-Cut, Expansion and Groethendick’s Inequality
- Lecture 6 Sum-of-Squares and Tensor Decomposition
- Lecture 7 Guest Lecture by Sam Hopkins: Robust Tensor Decomposition
- Lecture 8 Guest Lecture by Pravesh Kothari: Statistical vs Computational Complexity Tradeoffs via SoS.
Exercises
Running list of exercises given in class.
Project
List of projects.
Reference
- Convex Relaxations and Integrality Gaps Eden Chlamtac, Madhur Tulsiani
- The Lasserre hierarchy in Approximation algorithms (lecture notes) Thomas Rothvoss
- Sum-of-squares proofs and the quest toward optimal algorithms Boaz Barak, David Steurer
- Proofs, beliefs, and algorithms through the lens of sum-of-squares (lecture notes) Boaz Barak, David Steurer
- Hierarchies reading group at CWI
Logistics
- Instructor: Moses Charikar, OH Wed 1:30-2:30, Gates 472
- Spring 2017
- Fri 1:30-4:20
- Location: 200-217
- Piazza: piazza.com/stanford/spring2017/cs369h
- Teaching Assistant: Paris Syminelakis, OH Fri 10:30 - 12:30 Gates 482
- Units: 3
- Requirements:
2-3 problem setsrunning set of exercises to clarify lecture material (complete 50% by quarter end) and research project/paper presentation; scribe notes for one lecture. - Prerequisites: Mathematical maturity (required), exposure to algorithms (strongly recommended) and optimization (recommended).
Student Projects
Spring 2017
- B. Barak et al., “A nearly tight sum-of-squares lower bound for the planted clique problem.” presented by Mona Azadkia [pdf] [slides]
- E. Chlamtáč, M. Dinitz, Y. Makarychev. “Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion.” presented by Vaggos Chatziafratis [pdf] [slides]
- Chan et al. “Approximate constraint satisfaction requires large LP relaxations.” presented by Neha Gupta [pdf] [slides]
- Xue Chen, “Integrality gaps and approximation algorithms for dispersers and bipartite expanders.” James Hong [pdf] [slides]
- J.R. Lee, P. Raghavendra, D. Steurer, “Lower bounds on the size of semidefinite programming relaxations.” presented by Weihao Kong [pdf]
- R. Meka, A. Potechin, A. Wigderson, “Sum-of-squares lower bounds for planted clique.” Kiran Shiragur [pdf] [slides]
- B. Barak, J.A. Kelner, D. Steurer, “Rounding sum-of-squares relaxations.” presented by Andy Tsao [pdf] [slides]
- V. Chandrasekaran, M.I. Jordan, “Computational and statistical tradeoffs via convex relaxation.” Carrie Wu [pdf] [slides]
- Chlamtáč et al., “Approximation algorithms for label cover and the log-density threshold.” presented by Jimmy Wu [pdf] [slides]