# 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@ 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: