CSE 535: Theory of Optimization and Continuous Algorithms

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

We hope that these concepts will help students become a designer instead of a consumer of continuous algorithms.

This course is offered in Georgia Tech at the same time by Santosh Vempala.

Administrative Information:

  • Instructor: Yin Tat Lee
  • Office Hours: By appointment, email me at yintat@ignoreme-uw.edu
  • Lectures: Tue, Thu 10:00-11:20 at ARC G070
  • Course evaluation: Homework (100%)
  • Prerequisite: basic knowledge of algorithms, probability, linear algebra.

Assignments

Submitted via Canvas.

  • Assignment 1 due Sunday, 20-Jan 11:59PM
  • Assignment 2 due Sunday, 3-Feb 11:59PM
  • Assignment 3 due Sunday, 17-Feb 11:59PM
  • Assignment 4 due Sunday, 3-Mar 11:59PM
  • Assignment 5 due Sunday, 17-Mar 11:59PM

Tentative Schedule:

Introduction

  • Jan 08:
  • Jan 10:
  • Jan 15:

Reduction

  • Jan 17:
  • Jan 22:
  • Jan 24:

Elimination

  • Jan 29:
  • Jan 31:

Conditioning

  • Feb 05:
  • Feb 07:

Geometrization

  • Feb 12:
  • Feb 14:

Expansion

  • Feb 19:
  • Feb 21:
  • Feb 26:

Sparsification

  • Feb 28:
  • Mar 5:

Acceleration

  • Mar 7:

Decomposition

  • Mar 12:
  • Mar 14: