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.

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

  1. Introduction
    Jan 7. Course overview. Gradient descent
    Jan 9. Langevin dynamics
  2. Elimination
    Jan 14. Ellipsoid/CoG/Cutting Plane for Optimization
    Jan 16. ... for Volume computation
  3. Reduction
    Jan 21. MLK holiday
    Jan 23. Duality (LP duality, SDP duality, ...) and Equivalences (Optimization, Membership, Separation; OPT, Integration->Sampling; Maxflow, Bipartite Matching)
  4. Geometrization I: Optimization
    Jan 28. Newton method, IPM
    Jan 30. IPM for LP (LS barrier)
  5. 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
  6. Acceleration
    Feb 18. Accelerated Gradient Descent, SGD, SVRG
    Feb 20. Conjugate Gradient
  7. Expansion
    Feb 25. Taylor expansion (Matrix inverse, Ax=b). ODE
    Feb 27. Complex analysis. Collocation method for ODE
  8. Decomposition
    Mar 4. Cholesky Decomposition
    Mar 6. Ax=b
    Mar 11. Maxflow
    Mar 13. Buffer
    Mar 18,20 (Spring break)
  9. Multiplication
    Mar 25, 27. Volume, Integration
  10. 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.