**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. (scribe notes) (board) (video)

Chapter 3 in Moitra's book

(Feb 24) Dimension Reduction, Johnson-Lindenstrauss, Oblivious subspace embeddings. (scribe notes) (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. (scribe notes) (board) (video)

Section 2.8 in Matousek's lecture notes on metric embeddings

(Mar 3) Nearest neighbors, Locality sensitive hashing. (scribe notes) (board) (video)

lecture 16 and lecture 17 from Moses Charikar's class.

Section 2.9 in Matousek's lecture notes on metric embeddings

(Mar 8) Low-diameter decompositions and HSTs (scribe notes) (board) (video)

Lecture 5 in Anupam Gupta's course.

(Mar 10) Graph expansion, uniform sparsest cut and Bourgain's embedding. (scribe notes) (board) (video)

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

(Mar 15) Cheeger's Inequality. (scribe notes) (board)(video)

Chap 2, Chap 21 in Spielman's book on spectral graph theory.

(Mar 17) Second eigenvalue of planar graphs, random walks, s-t connectivity. (scribe notes) (board) (video)

Chap 25 in Spielman's book on spectral graph theory.

scribe notes from Williamson's class.

(March 30) Effective resistances, commute times.(board) (video)

scribe notes from Williamson's class.

(April 6) Approximate maximum flow in undirected graphs (board) (video)

Lec 15 from Anupam Gupta's course.

(April 8) Semidefinite programming, Maximum cut.

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