Lectures: M,W 1.00-2.30pmin MCS B31.
Instructor: Prof. Lorenzo Orecchia, MCS 135D. Office hours: TBA
Homework 1 is out! Find it here.
Please sign-up for two sections of scribing on this google-doc
| Date | Topic | Overleaf Link |
| 9/7 | Graph Matrices, Linear Algebra Review | link |
| 9/12 | Linear Algebra Review, Spectral Theorem | link |
| 9/14 | Courant-Fischer, Connected Components | Notes by Spielman |
| 9/19 | PSD Matrices and Graph Approximations | link |
| 9/21 | Markov Chains and their Convergence to Stationary | link |
| 9/26 | Rate of Convergence of Random Walks on Graphs I | link |
| 9/28 | Rate of Convergence or Random Walks on Graphs II | link |
| 10/5 | Conductance and Its Relation to the SpectralGap | link |
| 10/11 | Metric Embeddings and the Cut Cone | link |
| 10/17 | Proof of Cheeger's Inequality | link |
| 10/19 | Eigenvector Computation | Notes by Vishnoi |
| 10/24 | Homework Review, Intro to Spectral Clustering | link |
| 10/26 | Singular Value Decomposition, Subspaces and Principal Angles | link |
| 10/31 | More Principal Angles | link |
| 11/2-7 | Davis-Kahan Theorem and SMB | Notes by Montanari |
| 11/9 | Electrical Circuits | soon… |
| 11/14-16 | Effective Resistance | old notes |
| 11/21 | Power Method and Gradient Descent | Notes by Vishnoi and old notes |
| 11/28 | Chebyshev Iteration and Conjugate Gradient | Notes by Vishnoi and old notes |
| 11/30 | Preconditioning | soon … |
| Homework 1 | Due: October 12, in class | link |
| Homework 2 | Due: December 12, in class | link |
Course Outline: Iterative methods allow us to trade-off precision and running time to produce theoretically sound, fast algorithms for many optimization problems. These methods rely on a very “continuous” interpretation of the problem, incorporating techniques such as steepest-descent and coordinate descent that strongly rely on geometric intuition. In this class, we will turn this perspective on his head and show that iterative methods can be extremely useful in understanding and efficiently solving fundamental combinatorial problems on graphs, a characteristically discrete structure. This has important implications at a time when input graphs may have even billions of nodes and any super-linear running time is practically infeasible.
Tentative Syllabus: The following topics will be covered:
Spectral Graph Theory: Graph Matrices and Graph Eigenvalues, Random Walks, Applications to Clustering
Electrical Circuits as Graphs: Laplacian systems, Preconditioning, Fast Solvers
Iterative Methods in Convex Optimization: Basics of Convex Optimization, Gradient Descent, Coordinate Descent, Application to Graph Problems
Some of the following topics may also be included:
Metric Embeddings
Semidefinite Programming
Matrix Concentration Bounds for Sparsification and Random Graphs
Prerequisites
While the class will not depend heavily on background material, it will require familiarity with fundamental algorithmic problems and techniques at the level of CS330 or equivalent. A working knowledge of basic linear algebra is also required. Do not hesitate to contact me if you are not sure whether your previous preparation will allow you to benefit from the class.
Workload
There will be three components to the workload in this class: scribing, homework and final exam.
In most lectures, two students will act as scribes. These students are expected to collaborate to produce high-quality lecture notes in Latex through the collaborative Latex editor overleaf.com. The scribes should submit a final draft of their notes within 5 days of the class. The quality and clarity of the notes will be part of the evaluation. No student will be asked to scribe more than 3 times.
There will be 3-5 homework assignments. There will be 3 homework assignments. You are encouraged to collaborate on the solution of the homeworks, but you must write up your own answers. If you do collaborate, you must acknowledge your collaborators.
This will be a take-home exam, on which collaboration is not allowed.
In both homeworks and in the exam, you may rely on published or online material, but you must ackowledge your sources.
Evaluation
The grading will roughly work out as follows: Scribing 50%, Homeworks and Final 50%.