Algorithms, Summer 2020 at CIS
- Instructor: David Woodruff
- Lectures: M-F 7:00am-9:00 for A class, 9:00am-11:00 for B class, Beijing time
- Office hours: TBD
- TAs: Jieling Cai (caijieling0709@gmail.com) and Tianrui Liu (lynette990217@yahoo.com)
Course Description
Design and analyze algorithms! We will put new focus on first and second order methods in this class.
Grading
Grading is based on 3 homeworks each worth 10%, an exam worth 20%, a final project worth 40%, and class participation worth 10%
Latex
We encourage homework solutions, scribe notes, and final projects to be typeset in LaTeX. If you are not familiar with LaTeX, see this introduction.
Lectures
- Properties of convex sets. See these slides at CMU for similar material
- More convex geometry and convex functions. See these slides at CMU for similar material
- Gradients, Hessians, first and second order characterizations of convexity (mostly whiteboard).
- Gradient descent and some motivation for second order methods (mostly whiteboard)
- Linear programming
- Linear programming II
- Linear programming III
- SGD, mini-batch, Momentum, RMSProp, Adam, proofs of convergence (mostly whiteboard)
- Projected gradient descent, line search, backtracking line search (mostly whiteboard)
- Linear convergence of GD with strong convexity, coordinate descent (mostly whiteboard)
- Newton's method, Lagrangian duality, support vector machines (mostly whiteboard)
Problem Sets
References
Materials from the following course might be useful in
various parts of this course:
Maintained by David Woodruff