**Lecture:** Monday/Wednesday 5:00-6:30pm

**Instructor:** Prasad Raghavendra

Office hours: Tuesday 2:30-3:30pm (zoom link in piazza)

**TA:** Emaan Hariri

Office hours: TBD

Continuous Optimization (5 lectures)

Gradient Descent,

Mirror Descent,Multiplicative weights

Regret minimization, online convex optimization.

Ellipsoid Algorithm

Application: Solving LPs via multiplicative weights

Linear algebraic primitives (4 lectures)

PCA, Power iteration

Tensors, power iteration, Jenrich's algorithm, Applications.

Embeddings: (3 lectures)

Dimension reduction, Johnson-Lindenstrauss

Locality Sensitive Hashing, Nearest Neighbor Search

Low stretch spanning trees.

Spectral Graph Theory (3 lectures)

Cheeger's inequality

Mixing of Markov chains

Electrical Flows

Application: Laplacian Solvers

Semidefinite Programming: (4 lectures)

MaxCut

Matrix multiplicative weights

Sum of Squares SDPs: Proofs to Algorithms

Robust Linear Regression

Differential Privacy (1 lecture)

Other topics?

Interior point methods

Near-linear time Max Flow

Compressed sensing

Robust and heavy-tailed Statistics

Sparsest cut

Iterative rounding of linear programs

Primal-dual algorithms

Date | Lecture | Suggested Reading | Scribe notes |

1/20 | Gradient Descent and its variants | section 2.1-2.6 in book by Nisheeth Vishnoi for mathematical preliminaries. Notes from Anupam Gupta | |

1/25 | Mirror Descent and multiplicative weights | Notes from Anupam Gupta | |

1/27 | |||

2/1 | |||

2/3 | |||

2/8 | |||

2/10 | |||

2/15 | President's Day | ||

2/17 | |||

2/22 | |||

2/24 | |||

3/1 | |||

3/3 | |||

3/8 | |||

3/10 | |||

3/15 | |||

3/17 | |||

3/22 | Spring Break | ||

3/24 | Spring Break | ||

3/29 | |||

3/31 | |||

4/5 | |||

4/7 | |||

4/12 | |||

4/14 | |||

4/19 | |||

4/21 | |||

4/26 | |||

4/28 | |||

Regular bi-weekly homeworks (collaboration allowed): 35%

1 take-home final (collaboration prohibited): 25%

Scribe 1 lecture: 10%

Project: In groups of 2 or 3, write a survey on an area of active research : 30%