**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: Thursday 2:00-3:00pm (zoom link in piazza)

(Jan 20) Gradient Descent and its variants (scribe notes)(board) (video)

section 2.1-2.6 in book by Nisheeth Vishnoi for mathematical preliminaries.

(Jan 25) Mirror Descent and multiplicative weights (scribe notes)(board) (video)

Proof of projected gradient descent (Theorem 3.2 in Bubeck's book)

(Jan 27) NO LECTURE

(Feb 1) Mirror Descent, Online Convex Optimization, Solving LPs via online convex optimization. (scribe notes)(board)(video)

Proof of Mirror descent (Theorem 4.2 in Bubeck's book)

(Feb 3) Centroid and Ellipsoid Algorithm (scribe notes) (board) (video)

(Feb 8) Solving linear systems, Preconditioninng, PCA, SVD, Power method (scribe notes) (board) (video)

Chapter 3 in Blum-Hopcroft-Kannan

Chapter 15 in Vishnoi's book

Conjugate Gradient Descent in Chapter 16 of Vishnoi's book

(Feb 10) Applications of PCA: Gaussian Mixtures, Robust Mean estimation. (scribe notes) (board) (video)

Chapter 3 in Blum-Hopcroft-Kannan

Section 2.1,2.2,2.3 in survey by Diakonikolas-Kane

(Feb 17) Robust Mean Estimation, Tensors. (scribe notes) (board) (video)

Section 2.1,2.2,2.3 in survey by Diakonikolas-Kane

Chapter 3 in Moitra's book

(Feb 22) Tensors, Jenrich's algorithm, Independent component analysis. (board) (video)

Chapter 3 in Moitra's book

(Feb 24) Dimension Reduction, Johnson-Lindenstrauss, Oblivious subspace embeddings. (board) (video)

Section 10.2,10.3, 10.4 in Anupam Gupta's notes

Section 2.1 in David Woodruff's survey

(Mar 1) Compressed sensing, RIP property, Metric embeddings, Nearest neighbors.

Section 2.8 in Matousek's lecture notes on metric embeddings

(Mar 3) Nearest neighbors, Locality sensitive hashing.

Section 2.9 in Matousek's lecture notes on metric embeddings

(Mar 8) Bourgain's embedding, sparsest cut.

section 4.2,4.3 in Matousek's lecture notes on metric embeddings.

(Mar 10) Tree embeddings

Lecture 5 in Anupam Gupta's course.

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%

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