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.

• Reduction
• Elimination
• Conditioning
• Geometrization
• Expansion
• Sparsification
• Acceleration
• Decomposition
• Discretization

Prerequisite: basic knowledge of algorithms, probability, linear algebra.

Textbook (in progress, with Yin Tat Lee)

Grading:
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.

Schedule (tentative):

1. Introduction
   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.
   
2. Elimination
   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.
   
3. Reduction
   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
   
4. 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.
   
5. Geometrization II: Non-Euclidean
   Mar 13. The Central Path Method. Notes.
   Mar 27. The Newton Method. Notes.
   Mar 29, Apr 3. Interior-Point Algorithms. Notes. Summary.
   Apr 5. Norms, Metrics, Hessians. Notes.
   Apr 10, 12. Affine-Invariant Sampling. Dikin, (R)HMC and beyond.
   Apr 17, 19. Simulated Annealing for Volume Computation.
   
6. Discretization
   Apr 24. Lattices and Basis Reduction. Notes.