| Date | Topic, Readings, and Deliverables |
|---|---|
| Fri 9/8 |
Introduction & Clustering Overview of the course; center-based clustering; algorithms for k-center Lecture Notes References: Williamson-Shmoys Section 2.2, Chekuri, Section 9.1; |
| Tue 9/12 |
Nets for metric spaces and nearest neighbor search Lecture Notes (same as above) Also, introduction to the k-median problem PS1 out |
| Fri 9/15 |
Local Search for k-Median The k-median problem; bicriteria approximation using LP rounding; analysis of local search Lecture Notes Readings: Williamson-Shmoys Section 9.2, Chekuri, Sections 9.3-9.4; PS1 out |
| Tue 9/19 |
Clustering and Perturbation Stability Perturbation stability; Optimal k-median solution under perturbation stability Lecture Notes References: Roughgarden notes; [AMM17] |
| Fri 9/22 |
Linear Programming: Introduction and Applications Formal definitions; formalizing optimization problems and relaxations as LPs; applications; rounding LP relaxations Lecture Notes References: Goemans notes (Sections 1-7); Roughgarden notes |
| Tue 9/26 |
Linear Programming: Rounding and Geometry Rounding LP relaxations; Geometry of LP polytopes; extreme point solutions; iterative rounding Lecture Notes References: Goemans notes (Sections 7-8) PS1 due |
| Fri 9/29 |
Linear Programming: Duality Weak and strong duality; Dual-fitting and Primal-Dual Schema Lecture Notes References: Goemans notes (Sections 7-8); Williamson-Shmoys (Sections 7.1,7.3) PS2 out |
| Tue 10/3 |
Linear Programming Wrapup Rounding algorithms and Primal-Dual Schema Lecture Notes References: Goemans notes (Sections 7-8); Williamson-Shmoys (Sections 7.1,7.3) |
| Fri 10/6 |
Principal Component Analysis Dimensionality reduction; goal of PCA; use cases; characterizing principal components Lecture Notes References: Roughgarden-Valiant notes (one and two) |
| Tue 10/10 |
Singular Value Decomposition and Applications SVD introduction; SVD vs PCA; low-rank approximation; application to clustering; intro to high-dimensional geometry Lecture Notes References: Blum-Hopcroft-Kannan (Chapter 3; sections 2.3-2.4, 2.6) |
| Fri 10/13 |
Clustering in High-Dimensional Spaces Geometry of high-dimensional spaces; Unit ball and spherical Gaussians; Clustering mixture of Gaussians Lecture Notes References: Blum-Hopcroft-Kannan (Chapter 3; section 2.8) |
| Tue 10/17 |
Random Projections The Random Projection Theorem; Johnson-Lindenstrauss Lemma; Intro to compressed sensing Lecture Notes References: Blum-Hopcroft-Kannan (Section 2.7); Fresken (Sections 1.1-1.3) for summary, variants, uses |
| Fri 10/20 |
Compressed Sensing Warmup: discrete sparse recovery; Compressed sensing; Applications Lecture Notes References: Musco notes; Roughgarden-Valiant notes PS2 due |
| Tue 10/24 |
Compressed Sensing Wrapup and Intro to Smoothed Analysis Complete compressed sensing proof; Notions of smoothed analysis and complexity Lecture Notes References: Roughgarden notes |
| Fri 10/27 |
Smoothed Analysis of Local Search Analysis of 2-OPT heuristic for TSP Lecture Notes References: Roughgarden notes PS3 out |
| Tue 10/31 |
Smoothed Complexity and Pseudo-polynomial Time Algorithms Equivalence between poly-time smoothed complexity and pseudo-polynomial time algorithms for binary optimization Lecture Notes References: Beier-Vocking 2004 PS3 out |
| Fri 11/3 |
Online Learning The online learning framework; regret; analysis of weighted majority References: Elad Hazan (Chapter 1) Lecture Notes |
| Tue 11/7 |
Rajmohan away; no class |
| Fri 11/10 |
Online Learning, continued; basics of convex optimization The Hedge algorithm; Introduction to convex optimization; gradient descent; step sizes and convergence bounds Lecture Notes References: Elad Hazan (Chapter 2) |
| Tue 11/14 |
Online Convex Optimization: Stochastic Gradient Descent Complete analysis of gradient descent The optimization powering all of deep learning; convergence analysis Lecture Notes References: Elad Hazan (Chapter 3) |
| Fri 11/17 |
Rajmohan away; no class |
| Tue 11/21 |
Project Proposal Presentations PS3 due |
| Fri 11/24 |
Thanksgiving (no class) |
| Tue 11/28 |
Online Algorithms and Competitive Analysis Wrap-up stochastic gradient descent; intro to competitive analysis: ski rental, paging Readings: Buchbinder-Naor monograph, chapter 3; Lecture Notes Nagarajan notes |
| Fri 12/1 |
Online Randomized Algorithms Randomized upper and lower bounds Lecture Notes Readings: Buchbinder-Naor monograph, chapter 4 |
| Tue 12/5 |
Online Primal-Dual Paradigm Online primal-dual algorithm for set cover; pointers to many applications Lecture Notes |
| Fri 12/8 |
Project Presentations |
| Tue 12/12 |
Project Presentations |
| Fri 12/15 |
Project Presentations |