# 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.

- Elimination
- Reduction
- Geometrization
- Acceleration
- Sparsification
- Decomposition

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
- TA Office hours: Fri 2:45-4:00, CSE 021
- Lectures: Tue, Thu 10:00-11:20 at ARC G070
- Lecture Note: https://www.dropbox.com/s/wdxhrlcnjz3tecj/main.pdf
- Course evaluation: Homework (100%)
- Prerequisite: basic knowledge of algorithms, probability, linear algebra.

## Assignments

Submitted via Gradescope. Check emails.

## Tentative Schedule:

### Introduction

- Jan 08: Gradient Descent (1.1, 1.2, 1.4)
- Jan 10: Langevin Dynamics (1.3, 1.5, 1.6)

### Elimination

- Jan 15: Cutting Plane Methods (2.1, 2.2, 2.3, 2.4)
- Jan 17: Sphere and Parabola Method (2.6, 2.7)

### Reduction

- Jan 22: Equivalences (3.1, 3.2, 3.3)
- Jan 24: Equivalences (3.4)
- Jan 29: Duality (3.5)

### Geometrization (Optimization)

- Jan 31: Mirror Descent
- Feb 07: Frank-Wolfe
- Feb 07: Newton Method & L-BFGS
- Feb ??: Interior Point Method

### Geometrization (Sampling)

- Feb 14: Ball walk & Isoperimetry
- Feb 19: Isotropic Transformation & Simulated Annealing.
- Feb 21: Hit-and-Run, Dikin walk
- Feb 26: RHMC

### Sparsification

- Feb 28: Stochastic Gradient Descent & Variance Reduction
- Mar 5: Leverage Score Sampling

### Acceleration

- Mar 7: Chebyshev Expansion & Conjugate Gradient
- Mar 12: Accelerated Gradient Descent

### Decomposition

- Mar 14: Cholesky decomposition