CS6550: Advanced Algorithms: Techniques for Optimization and Sampling

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

Santosh Vempala, Klaus 2222, Office hour: Tue 1-2pm.
TAs: Aryan Patel, OH: M 3:30-4:30pm, T: 2-3pm and Rahul Garg, OH: TR 3-4pm.

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 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 (30%): Biweekly HW. You are encouraged to collaborate on HW, but must write your own solutions. Submit via gradescope (link on canvas).
Three in-class mid-term exams (20%+25%+20% 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. Notes. HW1 (due Jan 15).
   Jan 14. Ch 2: Gradient descent. Notes
   Jan 19. MLK Holiday
   Jan 21, 26. Ch 2, Ch 8: Strong convexity; Gradient flow, Langevin Diffusion. Notes
   Jan 26,28. Ch 8: Sampling and Diffusion. Notes
   
2. Elimination
   Feb 2. Ch 3: Cutting Plane Method: Ellipsoid Algorithm. Notes
   Feb 4. Ch 3: Cutting Plane Method: Center of Gravity. Notes
   
3. Reduction
   Feb 9. Ch 9: Cutting Plane Method: Computing the Volume.
   Feb 11. Ch 4: Oracles and Duality.
   Feb 16. Ch 4: Optimization and Separation from Membership.
   Feb 18. Midterm I.
   
4. Geometrization I: Euclidean
   Feb 23, 25. Sampling, Markov chains and Conductance.
   Mar 2. Polytime Sampling.
   Mar 4. Euclidean Isoperimetry and the Localization Lemma.
   
5. Geometrization II: Non-Euclidean
   Mar 9. Hit-and-Run: Rapid Mixing from any start.
   Mar 11. The Proximal Sampler.
   Mar 16. Midterm II.
   Mar 18. The Central Path Method.
   Mar 23, 25. Spring break
   
6. Acceleration
   Mar 30. The Newton Method. Apr 1. The Interior-Point Method.
   Apr 6. Simulated Annealing and Gaussian Cooling.
   Apr 8. Integration and Rounding.
   Apr 13. (Riemannian) Hamiltonian Monte Carlo.
   Apr 15. *buffer*
   
7. Discretization
   Apr 20. Midterm III.
   Apr 22. Lattices and Basis Reduction.
   Apr 27. Students' choice!