E0 313: Theory of Convex Optimization and Sampling, Spring 2021
- Instructors: Ankit Garg
and Anand Louis
- Time: Tuesdays & Thursdays, 3:30 PM - 5 PM, Online (Teams).
Course Description
This course is intended to teach students in theoretical computer science and related areas about the theory of convex optimization.
Our goal is that at the end of the course, students should know some of the common algorithmic techniques used for optimizing
convex functions and sampling from convex bodies. The topics covered will be a subset of the following.
- Introduction to Gradient descent and cousins,
- Cutting plane methods,
- Interior point methods,
- Sampling from convex bodies,
- Connections to combinatorial optimization.
Lectures (Dropbox link (download to view full lectures) to lecture videos is here)
- Lecture 1: Gradient descent and analysis for smooth convex functions [Notes]
- Lecture 2: Application to maximum flow [Notes]
- Lecture 3: Mirror descent over the simplex [Notes]
- Lecture 4: Newton's method [Notes]
- Lecture 5: Analysis of Newton's method and start of IPMs [Notes]
- Lecture 6: Analysis of Interior Point Methods [Notes]
- Lecture 7: Analysis of IPMs [Notes]
- Lecture 8: Cutting plane methods [Notes]
- Lecture 9: Introduction to sampling from convex bodies [Notes]
- Lecture 10: Mixing times, conductance etc. [Notes]
- Lecture 11: Bounding conductance [Notes]
- Lecture 12: Lovasz-Simonovits [Notes]
- Student presentation (Prathik Diwakar and Sundararajan Srinivasan): Laplacian linear system solvers [Notes]
- Student presentation: Sampling matroid bases (Sruthi Gorantla and Bhargav Thankey) [Notes] [Notes]
References
We will be teaching materials from multiple books/sources. Some of them are the following.
- Yin Tat Lee and Santosh Vempala. Theory of Optimization and Continuous Algorithms. 2019.
- Nisheeth Vishnoi. Algorithms for convex optimization. 2021.
- Sebastien Bubeck. Convex Optimization: Algorithms and Complexity, 2015.
Assignments