CS6550/8803: Continuous Algorithms: Optimization and Sampling

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

Santosh Vempala, Klaus 2222, Office hour: Tue 3-4pm.
TAs: Yunbum Kook (OH: Mon 9-11am), Daniel Zhang (OH: Thu 1-3pm), Aditya Lonkar (OH: Fri 9-11am).

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: CS6515 (graduate algorithms) or equivalent, basic knowledge of probability and linear algebra.

Textbook (draft, with Yin Tat Lee)

Grading:
HW (35%): 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 (30% each).
Send comments on textbook via this form (up to 0.5% per chapter and 5% total).
Bonus (up to 10%): simpler proofs, new exercises.

Schedule (tentative):

1. Introduction
   Jan 6. Course overview. Ch 1: Convexity. Notes. HW1 (due Jan 10 by noon).
   Jan 8. Ch 2: Gradient descent. Notes
   Jan 13. Ch 2, Ch 8: Strong convexity; Gradient flow; Langevin dynamics. Notes.
   Jan 15, 22. Ch 8: Sampling and Diffusion. Notes. HW2 (due Jan 24 by noon).
   Jan 20. MLK Holiday
   
2. Elimination
   Jan 27. Ch 3: Cutting Plane Method: Ellipsoid Algorithm. Notes.
   Jan 29. Ch 3: Cutting Plane Method: Center of Gravity. Notes.
   
3. Reduction
   Feb 3. Ch 9: CPM: Computing the Volume. Notes.
   Feb 5,10. Oracles and Duality. Notes.
   Feb 12,17. Optimization from Membership. Notes.
   
4. Geometrization I: Euclidean
   Feb 19, 24. Sampling, Markov chains and Conductance. Notes.
   Feb 26. Polytime Sampling with the Ball Walk. Notes.
   Mar 3. Euclidean Isoperimetry and the Localization Lemma. Notes.
   
5. Geometrization II: Non-Euclidean
   Mar 5. Hit-and-Run: Rapid Mixing from any start. Notes.
   Mar 10. The Central Path Method. Notes.
   Mar 12. Midterm I.
   Mar 17, 19. Spring break
   Mar 24. The Central Path Method. Notes.
   Mar 26. Newton Method. Notes.
   
6. Acceleration
   Mar 31, Apr 2. The Interior-Point Method. Notes.
   Apr 7. Midterm II.
   Apr 9. Simulated Annealing and Gaussian Cooling. Notes.
   Apr 14. Integration and Rounding. Notes.
   Apr 16. (Riemannian) Hamiltonian Monte Carlo. Notes.
   
7. Discretization
   Apr 21. Lattices and Basis Reduction.