Algorithms, Summer 2020 at CIS.

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)

Design and analyze algorithms! We will put new focus on first and second order methods in this class.

Grading is based on 3 homeworks each worth 10%, an exam worth 20%, a final project worth 40%, and class participation worth 10%

We encourage homework solutions, scribe notes, and final projects to be typeset in LaTeX. If you are not familiar with LaTeX, see this introduction.

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)

Materials from the following course might be useful in various parts of this course:

Maintained by David Woodruff