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 68ZEXX.

Course Staff

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: aene @ bu . edu
Office Hours: TBD

Teaching Fellow: Duy Le
Email: duyle @ bu . edu
Office Hours: TBD

Lectures

Tue/Thu 9:30am - 10:45am, in PSY B35

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

Lecture	Topic
Mathematical background. Introduction to optimization.
9/3	Course overview and introduction. Linear classification and the Perceptron algorithm.
	Review of concepts from linear algebra and multivariate calculus.
	Introduction to optimization, examples of optimization problems.
	Optimality conditions for general problems.
Convex optimization. Gradient descent algorithms.
	Convex functions and sets, optimality conditions for convex problems.
	Oracle models, iterative methods, and gradient descent.
	Gradient descent algorithms for convex optimization problems.
Supervised learning. Stochastic and adaptive gradient descent.
	Supervised learning. Linear models. Algorithms for linear regression.
	Algorithms for linear classification.
	Neural network models. Stochastic gradient descent.
	Adaptive gradient descent algorithms.
Linear programming. LP duality. Algorithmic frameworks based on LPs and duality.
	Introduction to linear programming. Modeling using LPs.
	LP duality.
	Algorithmic frameworks based on LPs and duality.
	Duality applications: flows and cuts, zero-sum games.
Optimization under uncertainty: online learning, online algorithms
	Prediction using expert advice. Majority algorithms.
	Multiplicative weights update algorithm. Application to classification: Winnow algorithm.
	Multiplicative weights update algorithm applications: solving positive LPs.
	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.