## Continuous Algorithms: Optimization and Sampling

#### Spring 2020. TR: 9:30-10:45. Arch.(East) 207.

#### Santosh Vempala, OH: Tue 11-12, Klaus 2222.

TA: He Jia, OH: Thu 2-4, Arthita Ghosh: OH: Mon 11-1.

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

The course is offered simultaneously at UW by

Yin Tat Lee.

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

**Textbook** (in progress)

**Grading**:

6550: 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).

Send comments on lecture notes each week, either in dropbox or by email.

8803: HW optional. Comment on lecture notes each week.

Bonus: suggesting simpler proofs, exercises, figures.

**Schedule** (tentative):

- Introduction

Jan 7. Course overview.

Jan 9. Gradient descent. Notes.

**HW1** has been posted on gradescope, due Jan 20.

Jan 14. Gradient descent (contd.) Notes.
- Elimination

Jan 16. Cutting Plane method; Ellipsoid. Notes (and from a while ago)

Jan 21. Center-of-Gravity. Notes

Jan 23. Ball method; lower bounds.
- Reduction

Jan 28, 30. Duality (LP duality, SDP duality, ...) and Equivalences (Optimization, Membership, Separation; OPT, Integration->Sampling; Maxflow, Bipartite Matching).
- Geometrization I

Feb 4. Mirror Descent, Frank-Wolfe

Feb 6. Newton method

Feb 11. Interior Point Method

Feb 13. IPM for LP.
- Sparsification

Feb 18. Regression and subspace embeddings.

Feb 20. Matrix approximation.

Feb 25. Coordinate Descent.

Feb 27. Stochastic Gradient Descent.
- Acceleration

Mar 3. Conjugate Gradient and Chebychev Expansion.

Mar 5. Accelerated Gradient Descent.
- Decomposition

Mar 10.

Mar 12.

Mar 17,19 (Spring break)

- Sampling

Mar 24. Langevin Dynamics and SDE.

Mar 26. Conductance, Ball walk

- Geometrization II

Apr 7. Mixing of ball walk, Isoperimetry, Isotropy.

Apr 9. Hit-and-Run, Dikin walk

Apr 14. (Riemannian) HMC

Apr 16. ODE. Complex analysis.