﻿ Theory of Convex Optimization and Sampling, Spring 2021.

## 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 Lectures Assignments Projects References

### 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.

• 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.