CS6550/8803: Continuous Algorithms: Optimization and Sampling
Spring 2023. MW: 2-3:15pm, Weber SST III, L1
Santosh Vempala, Klaus 2222, Office hour: Wed 3:30-4:30pm.
TAs: Max Dabagia, Jai Moondra, Disha Aravind.
The design of algorithms is traditionally a discrete endeavor. However, many advances have come from a
continuous viewpoint. Typically, a continuous process, deterministic or randomized is designed (or shown) to have
desirable properties, such as approaching an optimal solution or a desired distribution, and an algorithm is
derived from this by appropriate discretization. We will use this viewpoint to develop several general techniques and build up to the state-of-the-art in polynomial algorithms for optimization and sampling.
Prerequisite: basic knowledge of algorithms, probability, linear algebra.
(in progress, with Yin Tat Lee)
HW: Biweekly HW, including one longer HW towards the end. You are encouraged to collaborate on HW, but must write your own solutions. Submit via gradescope (link on canvas).
6550: HW, one mid-term exam. Send comments on textbook each week via this form.
8803: No exam. HW; comment on textbook each week.
Bonus: suggesting simpler proofs, exercises, figures.
Jan 9. Course overview. Chap 1. Notes. HW1 (due Tue, Jan 17th)
Jan 11. Gradient descent. Chap 2. Notes.
Jan 16. MLK holiday.
Jan 18. Gradient-based Sampling: Langevin dynamics. Chap 8. Notes.
Jan 25. Cutting Plane Method: Ellipsoid Algorithm. Chap 3. Notes.
Jan 30. Cutting Plane Method: Center of Gravity. Chap 3. Notes.
Feb 1. CPM: Computing the Volume. Chap 9. Notes.
Feb 6. Oracles and Duality. Chap 4. Notes
Feb 8,13. Duality and Duality. Chap 4. Notes
Feb 15. Optimization from Membership. Chap 4. Notes
- Geometrization I: Euclidean
Feb 20. Markov chains and conductance. Notes.
Feb 22. Sampling convex bodies: the Ball Walk. Notes.
Feb 27. Local conductance and Warm starts. Notes.
Mar 1. Euclidean Isoperimetry and the Localization Lemma. Notes.
Mar 6. A Rapidly Mixing Markov Chain for Convex Bodies. Notes.
Mar 8. Sampling and Volume in Polynomial Time. Notes.
- Geometrization II: Non-Euclidean
Mar 13. The Central Path Method. Notes.
Mar 15. Midterm.