CS6550: Continuous Algorithms: Optimization and Sampling

Spring 2026. MW: 2-3:15pm, Klaus 1447

Santosh Vempala, Klaus 2222, Office hour: TBD.
TAs: 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: CS6515 (graduate algorithms) or equivalent, basic knowledge of probability and linear algebra.

Textbook (draft, with Yin Tat Lee)

Grading:
HW (TBD%): 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 (TBD% 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 12. Course overview. Ch 1: Convexity. HW1 (due Jan 15 by 5pm).
   Jan 14. Ch 2: Gradient descent.
   Jan 19. MLK Holiday
   Jan 21. Ch 2, Ch 8: Strong convexity; Gradient flow; Langevin dynamics.
   Jan 26,28. Ch 8: Sampling and Diffusion.
   
2. Elimination
   Feb 2. Ch 3: Cutting Plane Method: Ellipsoid Algorithm.
   Feb 4. Ch 3: Cutting Plane Method: Center of Gravity.
   
3. Reduction
   Feb 9. Ch 9: CPM: Computing the Volume.
   Feb 11. Ch 4: Oracles and Duality.
   Feb 18. Ch 4: Optimization and Separation from Membership.
   
4. Geometrization I: Euclidean
   Feb 25, 27. Sampling, Markov chains and Conductance.
   Mar 4. Polytime Sampling with the Ball Walk.
   Mar 6. Euclidean Isoperimetry and the Localization Lemma.
   
5. Geometrization II: Non-Euclidean
   Mar 11. Hit-and-Run: Rapid Mixing from any start.
   Mar 13. Midterm I.
   Mar 18, 20. The Central Path Method.
   Mar 23, 25. Spring break
   Mar 30. The Newton Method.
   
6. Acceleration
   Apr 1. The Interior-Point Method.
   Apr 6. Midterm II.
   Apr 8. Simulated Annealing and Gaussian Cooling.
   Apr 13. Integration and Rounding.
   Apr 15. (Riemannian) Hamiltonian Monte Carlo.
   
7. Discretization
   Apr 20, 22. Lattices and Basis Reduction.
   Apr 27. Student's choice!