Continuous Algorithms for Optimization and Sampling, Spring 2024

Traditional algorithms in computer science are designed in a discrete manner. Nonetheless, recent years have witnessed great advances from a continuous perspective, particularly in the design of optimization and sampling algorithms. There is a deep connection between optimization and sampling, either through optimization as the limit of sampling, or through sampling as optimization in the space of probability measures. Motivated by this viewpoint, this course aims to develop a systematic way to design and analyze algorithms for both areas from the continuous perspective. More particularly, this course starts from continuous optimization, discusses stochastic optimization in detail, introduces optimal transport as a bridge connecting optimization and sampling, and finally delves into sampling.

Course Information

• Syllabus

• Instructor: Jiaming Liang

• Meeting Information: 11:05 am-12:20 pm, Tuesday/Thursday, Meliora Hall 209

• Textbooks

  • Amir Beck. First-order methods in optimization. SIAM, 2017.

  • Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on Stochastic Programming: Modeling and Theory. SIAM, 2021.

  • Cédric Villani. Topics in Optimal Transportation. American Mathematical Society, 2021.

  • Sinho Chewi. Log-Concave Sampling. Draft, 2023.

Topics

• Interface between optimization and sampling [slides]
  

• Subgradient method [notes]
  

• Mirror descent [notes]
  

• Proximal gradient method [notes]
  

• Frank-Wolfe method [notes]
  

• Stochastic approximation [notes]
  

• Differential privacy [notes]
  

• Langevin Monte Carlo [notes]
  

• Proximal sampling [notes]
  

• Wasserstein space [notes]
  

• Revisiting differential privacy [notes]