CS 531: Advanced Optimization Algorithms

Course Description

This is a graduate-level course on the design and analysis of iterative algorithms for continuous and discrete 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; adaptive and stochastic gradient descent; linear programming and duality; online learning and multiplicative weight update method; and how these frameworks can be used to obtain very efficient algorithms for classification, regression, discrete optimization, and beyond.

Syllabus

Collaboration and Honesty Policy

Piazza

Gradescope for submitting homeworks. Sign up using the entry code 8ENJZ2.

Course Staff

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: aene @ bu . edu
Office Hours: Tue 2-3pm, Thu 1-3pm. Location: Blue lounge next to CDS 1028 (backup: open area next to CDS 1021)

Teaching Fellow: Fabian Spaeh
Email: fspaeh @ bu . edu
Office Hours: Wed, Fri 2:30-3:30pm. Location: Blue lounge next to CDS 1028 (backup: open area next to CDS 1021)

Lectures

Tue/Thu 3:30pm - 4:45pm, in MCS B33

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

Lecture	Topic
Mathematical background. Introduction to optimization.
9/5	Course overview and introduction. Linear classification and the Perceptron algorithm.
9/7	Review of concepts from linear algebra.
9/12	Review of concepts from multivariate calculus.
9/14	Introduction to optimization, examples of optimization problems.
9/19	Optimality conditions for general problems.
Convex optimization. Gradient descent algorithms.
9/21	Convex functions and sets, optimality conditions for convex problems.
9/26	Oracle models, iterative methods, and gradient descent.
9/28	Gradient descent for convex functions that are smooth.
10/3	Gradient descent for convex functions that are non-smooth but Lipschitz.
10/5	Gradient descent for well-conditioned and strongly convex functions.
10/10	No class (Monday schedule)
10/12	In-class midterm exam (covers all material up to and including 10/3 lecture)
Supervised learning. Stochastic and adaptive gradient descent.
10/17	Applications to algorithm design: linear regression.
10/19	Applications to algorithm design: linear classification.
10/24, 10/26	Neural networks. Stochastic gradient descent.
10/31	Adaptive gradient descent algorithms.
Linear programming. LP duality. Algorithmic frameworks based on LPs and duality.
10/31, 11/2	Introduction to linear programming. Modeling using LPs. LP duality.
11/7, 11/9	Algorithmic frameworks based on LPs and duality.
11/14, 11/16	Further applications of duality: flows and cuts, zero-sum games, boosting.
11/21	No class (pre-Thanksgiving)
11/23	No class (Thanksgiving break)
Learning from experts. Multiplicative weights update algorithms.
11/28	Guest lecture by TF Fabian Spaeh. Prediction using expert advice, majority algorithms.
11/30	Guest lecture by Prof. Huy Nguyen. Multiplicative weights update algorithm. Applications to algorithm design: Winnow algorithm for supervised classification.
12/5, 12/7	Applications to algorithm design: packing/covering LPs, zero-sum games, boosting.
12/12	Guest lecture by Prof. Adam Smith.

Acknowledgments: I am indebted to my colleagues at other institutions for some of the material in the lectures: Amir Ali Ahmadi's course at Princeton, Yaron Singer's course at Harvard, Nick Harvey's course at UBC, ... . The specific references/credits are on the References slide at the end of each lecture.