CS 531: Advanced Optimization Algorithms

Course Description

This is a graduate-level course on the design and analysis of iterative algorithms for convex and non-convex optimization. Iterative methods based on gradient descent have had a profound impact on many areas of computer science and engineering, including algorithms and theoretical computer science, machine learning, data mining, finance, and operations research. The main topics covered are the design and analysis of gradient descent methods for convex problems; adaptive, stochastic and non-convex optimization; linear programming and duality; online learning; mirror descent.

Syllabus

Collaboration and Honesty Policy

Piazza

Gradescope for submitting homeworks. Sign up using the entry code X3DBV4.

Course Staff

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: aene @ bu . edu
Office Hours: Tuesdays and Thursdays, 2pm - 3pm, in MCS 103/105

Teaching Fellow: Fabian Spaeh
Email: fspaeh @ bu . edu
Office Hours: Mondays 4pm - 5pm, Fridays 2:15pm - 3:15pm, in MCS 103/105

Lectures

Tue/Thu 3:30pm - 4:45pm, in CAS 324

The schedule is tentative and subject to change (e.g., snow days).

You can try the Jupyter notebooks in your browser here. You can make changes and run the code in the browser. The changes will not be saved, when you hit refresh all the changes will be gone.

Lectures and discussions will be primarily on the board. Lecture, discussion, and homework handouts will be posted on Piazza.

Lecture	Topic
Mathematical background and introduction to optimization
1/20	Course overview and introduction. Linear classification and the Perceptron algorithm.
1/25, 1/27	Review of concepts from linear algebra.
2/1	Review of concepts from multivariate calculus.	Jupyter notebook
2/3, 2/8	Convex functions and sets.
2/10, 2/15	Introduction to optimization. Examples of optimization problems.	Jupyter notebook
2/17	Optimality conditions for general and convex problems.
2/22	Monday schedule (no lecture)
Iterative methods for convex optimization
2/24	Oracle models, iterative methods, and gradient descent.
3/1, 3/3	Analysis of gradient descent. Smoothness and strong convexity.
3/8, 3/10	Spring break (no lectures)
3/15	In-class midterm exam
3/17	Frank-Wolfe algorithm.
Adaptive methods, stochastic and non-convex optimization
3/22	Adaptive methods.
3/24	Stochastic gradient descent.
3/29, 3/31	Supervised learning. Neural networks, backpropagation algorithm, ADAM algorithm.
Linear programming and duality, discrete optimization
4/5	Introduction to linear programming. Modeling using LPs.
4/7, 4/12	LP duality. Applications of LP duality.
4/14, 4/19	Discrete optimization.
Learning from experts, mirror descent
4/21	Prediction using expert advice, majority algorithms.
4/26, 4/28	Multiplicative weights update algorithm, online convex optimization.
5/3	Mirror descent.