## 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):

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

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

- 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

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

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

- Discretization

Apr 24. Lattices and Basis Reduction. Notes.