CS6550/8803: Continuous Algorithms: Optimization and Sampling

Spring 2025. MW: 2-3:15pm, Klaus 2447

Santosh Vempala, Klaus 2222, Office hour: TBD.
TAs: Yunbum Kook, Daniel Zhang, TBD.

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. These techniques include:

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

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

Textbook (draft, with Yin Tat Lee)

Grading:
HW: Biweekly HW. You are encouraged to collaborate on HW, but must write your own solutions. Submit via gradescope (link on canvas).
Two in-class mid-term exams.
Send comments on textbook each week via this form.
Bonus: simpler proofs, new exercises.

Schedule (tentative):

1. Introduction
   Jan 6. Course overview. Convexity. HW1 (due Jan 10 by noon).
   Jan 8. Gradient descent.
   Jan 13. Gradient-based Sampling: Langevin dynamics.
   
2. Elimination
   Jan 15. Cutting Plane Method: Ellipsoid Algorithm.
   Jan 20. MLK Holiday
   Jan 22. Cutting Plane Method: Center of Gravity.
   Jan 27. CPM: Computing the Volume.
   
3. Reduction
   Jan 29. Oracles and Duality.
   Feb 3.
   Feb 5. Optimization from Membership.
   
4. Geometrization I: Euclidean
   Feb 10,12. Markov chains and conductance.
   Feb 17. Sampling convex bodies: the Ball Walk.
   Feb 19. Logconcave functions.
   Feb 24. Isoperimetry and the Localization Lemma.
   Feb 26. Sampling and Volume in Polynomial Time.
   
5. Geometrization II: Non-Euclidean
   Mar 3. The Central Path Method.
   Mar 5. The Newton Method.
   Mar 10. Interior-Point Algorithms.
   Mar 12. Midterm I.
   Mar 17, 19. Spring break
   Mar 24. Simulated Annealing.
   Mar 26.
   
6. Acceleration
   Mar 31. Nesterov and Ball method.
   Apr 2. Gaussian Cooling.
   Apr 7. Midterm II.
   Apr 9, 14. Algorithmic Diffusion.
   Apr 16. (Riemannian) Hamiltonian Monte Carlo.
   
7. Discretization
   Apr 21. Lattices and Basis Reduction.