CS 531: Advanced Optimization Algorithms


Course Description

This is a graduate-level course on optimization algorithms. The course covers continuous and discrete optimization through the lens of convex optimization. Convex optimization has 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 first part of the course covers the theory of convex optimization and its applications. The second part covers discrete optimization techniques that build on the machinery covered in the first part. For more information, see the syllabus.

Syllabus

Collaboration and Honesty Policy

Piazza

Gradescope for submitting homeworks. Sign up using the entry code 9J23VP.


Course Staff

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: aene @ bu . edu
Office Hours: Mondays 2:30pm - 4pm in MCS 110.

Teaching Fellow: Andrew Suh
Email: asuh9 @ bu . edu
Office Hours: Fridays 2:30pm - 4pm in EMA 302.

Lectures

Mon/Wed 4:30pm - 5:45pm, in CAS 225

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.

Lecture Topic Annotated Slides Other
Mathematical background and introduction to optimization
Lecture 1 (1/22/20) Course overview and introduction. Linear classification and the Perceptron algorithm Lecture 1
Lecture 2 (1/27/20) Review of concepts from linear algebra Lecture 2 Jupyter notebook
Lecture 3 (1/29/20)
Review of concepts from multivariate calculus
Lecture 3
Lectures 4, 5 (2/3/20, 2/5/20)
Convex functions and sets
Lectures 4,5
Lectures 6, 7 (2/10/20, 2/12/20)
Introduction to optimization. Examples of discrete and continuous optimization problems: classification and learning problems (least squares, LASSO, SVM), maximum flows and minimum cuts, maximum cut, minimum independent set
Lectures 6,7 Jupyter notebook
Continuous Optimization
Lectures 8, 9 (2/18/20, 2/19/20)
Optimality conditions for general and convex problems
Lectures 8,9
Lectures 10, 11 (2/24/20, 2/26/20)
Oracle models, iterative methods, and gradient descent
Lectures 10,11
Lecture 12 (3/2/20 )
Gradient descent for smooth and strongly convex functions
Lecture 12
Lectures 13, 14 (3/4/20, 3/16/20)
Prediction using expert advice: majority algorithms, multiplicative weights update algorithm
Lectures 13,14
Lecture 15 (3/18/20)
Applications of multiplicative weights update framework
Lecture 15
Lecture 16 (3/23/20)
Midterm exam (take home exam, lecture cancelled)
Lecture 17 (3/25/20)
Online optimization and learning, follow the leader algorithm for online convex optimization
Lecture 17
Lecture 18 (3/30/20)
Online convex optimization continued: follow the regularized leader, online gradient descent. Introduction to linear programming.
Lecture 18
Lecture 19 (4/1/20)
Modeling using LPs, LP duality
Lecture 19
Lecture 20 (4/6/20)
Applications of duality I: 2-player games, Nash equilibria, minimax theorem
Lecture 20
Lectures 21, 22 (4/8/20, 4/13/20)
Applications of duality II: minimax theorem, boosting theorem, maxflow-mincut theorem
Lecture 21, 22
Discrete Optimization
Lectures 23, 24 (4/15/20, 4/22/20)
Maximum flows and minimum cuts in networks (guest lectures by Adrian Vladu)
Lecture 23, Lecture 24
Lecture 25 (4/27/20)
Course recap
Lecture 25
Lecture 26 (4/29/20)
Midterm exam (take-home exam, lecture cancelled)

Acknowledgments: Many pictures used in the lecture slides are courtesy of Google Images and their respective authors. I am indebted to my colleagues at other institutions for some of the material in the lectures. In particular, Amir Ali Ahmadi's course at Princeton has been a great source of inspiration and material. The specific references/credits are on the References slide at the end of each lecture.



Homeworks

Homeworks are released on Wednesday before class, and are due in two weeks on Wednesday at midnight. Expect a homework every two weeks except for the midterm exam week.