CS 8803: Dynamics to Algorithms: Optimization, Sampling, and Games

Description: Algorithms are the fundamental building blocks of computation. In practice, algorithms run in discrete time. However, many algorithms can be derived as discretization of continuous-time dynamical systems. Studying the dynamics in continuous time are useful to highlight the underlying properties that make them work for solving the problems, and to guide the development and analysis of algorithms in discrete time. In this course, we will survey continuous-time dynamics to solve fundamental problems in three domains: Optimization, Sampling, and Games, motivated by applications in  computer science and machine learning. We will study the convergence guarantees of the dynamics in continuous time, and how to implement the dynamics as discrete-time algorithms while translating the desired convergence guarantees (or understand why the translation fails).

Tentative topics:

1. Optimization:

1. • Gradient flow and discretization: gradient descent, proximal method, forward-backward method

   • Accelerated gradient flow (heavy ball), accelerated gradient descent

   • Natural gradient flow (on Hessian manifold), mirror flow, mirror descent

   • Wasserstein gradient flow (on the space of probability distributions)

   • Hamiltonian flow for optimization

2. Sampling:

   • Langevin dynamics and discretization: Unadjusted Langevin algorithm, proximal sampler

• Mirror Langevin dynamics and discretization

2. • Kinetic (underdamped) Langevin dynamics and discretization

   • Hamiltonian Monte Carlo and discretization

   • Diffusion models and discretization

3. Games:

   • Min-max gradient flow and discretization:  min-max gradient descent, proximal, alternating

   • Min-max mirror flow and discretization: min-max mirror descent, proximal, alternating

   • Min-max Langevin dynamics and discretization for games on the space of distributions

4. Techniques and tools:

   • Descent lemma and energy identity for greedy flows/methods

   • Lyapunov functions for accelerated/kinetic methods

   • Principle of least action, Euler-Lagrange equations

   • Continuity equations (density evolutions for differential equations)

   • Fokker-Planck equations (density evolutions for stochastic differential equations)

   • Geometry of Wasserstein space, Otto calculus, optimal transport

   • Isoperimetric inequalities (Poincaré and log-Sobolev inequalities)

   • Time-reversal of stochastic processes

   • Data processing inequalities

Topics may be adjusted based on students' interests. Students are encouraged to pursue research or review projects on related topics that are not covered in class