CS 591 E1: 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 MV54N6.

Grading Instructions

Course Staff

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: aene @ bu . edu
Office Hours: Wednesdays 4:30pm - 6pm or by appointment (please email to make an appointment), in MCS 291.

Lectures

Tues/Thurs 3:30 - 4:45pm, in MCS B25

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

Lecture Topic Reading
Mathematical background and introduction to optimization
Lecture 1 (9/4/18) Course overview and introduction. Linear classification and the Perceptron algorithm Slides
Lecture 2 (9/6/18) Review of concepts from linear algebra Slides
Lecture 3 (9/11/18)
Review of concepts from multivariate calculus
 Slides
Lecture 4 (9/13/18)
Convex functions and sets
Slides
Lectures 5, 6 (9/18/18, 9/20/18)
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
Slides
Continuous Optimization
Lectures 7, 8 (9/25/18, 9/27/18)
Optimality conditions for general and convex problems
Slides
Lectures 9, 10 (10/2/18, 10/4/18)
Oracle models, iterative methods, and gradient descent
 Slides
Lecture 11 (10/9/18)
No Class (Monday schedule)
Lecture 12 (10/11/18)
Gradient descent for smooth and strongly convex functions
 Slides
Lectures 13, 14 (10/16/10, 10/18/18,)
Prediction using expert advice: majority algorithms, multiplicative weights update algorithm
 Slides
Lecture 15 (10/23/18)
Applications of multiplicative weights update framework, online optimization and learning
 Slides
Lecture 16 (10/25/18)
Midterm review
Slides
Lecture 17 (10/30/18)
In-class midterm exam
Lecture 18 (11/1/18)
Introduction to linear programming, modeling using LPs
 Slides
Lecture 19 (11/6/18)
LP duality
Slides
Lectures 20, 21, 22 (11/8/18, 11/13/18, 11/15/18)
Applications of duality: maxflow-mincut theorem, minimax theorem in game theory, learning and boosting
 Slides
Discrete Optimization
Lecture 23 (11/20/18)
Introduction to discrete optimization
 Slides
Lecture 24 (11/27/18)
Submodular functions and optimization
 Slides
Lecture 25 (11/29/18)
Maximum flows and minimum cuts in networks (guest lecture by Adrian Vladu)
Lecture 26 (12/4/18)
Submodular optimization continued
 Slides
Lecture 27 (12/6/18)
Final exam review
 Slides
Lecture 28 (12/11/18)
Course recap

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.


Homeworks

Homeworks are released on Thursdays before class, and are due in one week on Thursdays at midnight. The hw schedule is as follows (see Piazza for the pdf/tex):