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 BKJ6XW.

Course Staff

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: aene @ bu . edu
Office Hours: Tue, Thu 1:45pm - 3:15pm, in CDS 1027

Teaching Fellow: Ta Duy Nguyen
Email: taduy @ bu . edu
Office Hours: Mon 3pm - 4pm, Fri 12:15pm - 1:15pm, in the Blue lounge next to CDS 1027

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.
1/21	Course overview and introduction. Linear classification and the Perceptron algorithm.
1/23, 1/28	Review of concepts from linear algebra and multivariate calculus.
1/30, 2/4	Introduction to optimization, examples of optimization problems.
2/6	Optimality conditions for general problems.
Convex optimization. Gradient descent algorithms.
2/11, 2/13	Convex functions and sets, optimality conditions for convex problems.
2/18	No class (Monday schedule)
2/20	Oracle models, iterative methods, and gradient descent.
2/25, 2/27	Gradient descent algorithms for convex optimization problems.
Supervised learning. Stochastic and adaptive gradient descent.
3/4	Supervised learning. Linear models. Algorithms for linear regression.
3/6	In-class midterm exam (covers all material up to and including 2/27 lecture)
3/11, 3/13	No classes (Spring break)
3/18	Algorithms for linear classification.
3/20, 3/25	Neural network models. Stochastic gradient descent.
3/27	Adaptive gradient descent algorithms.
Linear programming. LP duality. Algorithmic frameworks based on LPs and duality.
4/1	Introduction to linear programming. Modeling using LPs.
4/3	LP duality.
4/8	Algorithmic frameworks based on LPs and duality.
4/10, 4/15	Duality applications: flows and cuts, zero-sum games.
Optimization under uncertainty: online learning, online algorithms
4/17	Prediction using expert advice. Majority algorithms.
4/22	Multiplicative weights update algorithm. Application to classification: Winnow algorithm.
4/24	Multiplicative weights update algorithm applications: solving positive LPs.
4/29, 5/1	Online algorithms: sky rental, caching, linked list maintenance.

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.