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