## Continuous Algorithms

### Santosh Vempala

#### Spring 2019. MW 9:30-10:45am. Howey N210

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. In interesting and general settings, the current fastest
methods are a consequence of this perspective. We will discuss several examples of algorithms for
high-dimensional optimization and sampling, and use them to understand the following concepts in detail.

- Reduction
- Elimination
- Conditioning
- Geometrization
- Expansion
- Sparsification
- Acceleration
- Decomposition
- Discretization

The course is also being taught on the West coast by

Yin Tat Lee.

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

**Lecture notes**.

**Schedule** (tentative):

- Introduction

Jan 7. Course overview. Gradient descent

Jan 9. Langevin dynamics
- Elimination

Jan 14. Ellipsoid/CoG/Cutting Plane for Optimization

Jan 16. ... for Volume computation
- Reduction

Jan 21. MLK holiday

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

Jan 28. Newton method, IPM

Jan 30. IPM for LP (LS barrier)
- Geometrization II: Sampling

Feb 4. Ball walk. Isoperimetry

Feb 6. Isotropic transformation, Simulated annealing

Feb 11. Hit-and-Run, Dikin walk

Feb 13. Riemannian HMC
- Acceleration

Feb 18. Accelerated Gradient Descent, SGD, SVRG

Feb 20. Conjugate Gradient
- Expansion

Feb 25. Taylor expansion (Matrix inverse, Ax=b). ODE

Feb 27. Complex analysis. Collocation method for ODE
- Decomposition

Mar 4. Cholesky Decomposition

Mar 6. Ax=b

Mar 11. Maxflow

Mar 13. Buffer

Mar 18,20 (Spring break)

- Multiplication

Mar 25, 27. Volume, Integration

- Student presentations

Apr 1,3

Apr 8,10

Apr 15,17

**Format**: This course is a research seminar. I will give most of the lectures and class participants will give the
rest.

A student taking the class for credit is expected to (possibly partnering with another student):

(a) Each week: Proofread lecture notes and suggest improvements OR do one HW problem.

(b) Present in class

(c) Study in more depth the topic of (a) or (b) and prepare an expository note and/or work on a related open problem.