Advanced Optimization (2022 Fall)

Course Information

This course aims to provide an overview of modern optimization theory designed for machine learning, particularly focusing on stochastic optimization and online optimization, which serve as the foundational optimization tools for modern large-scale learning tasks.

Announcement

Homework

Course agenda

Week Date Topic
Slides
Lecture Notes/ Readings
1 09.20 Introduction; Mathematical Background Lecture 1 on matrix norm
2 09.27 Convex Optimization Basics Lecture 2 Chapter 3.2 of Boyd and Vandenberghe’s book (on operations that preserve convexity)
Chapter 3 of Amir Beck’s book (on subgradients)
3 10.04 Function Properties Lecture 3 Chapter 5 of Amir Beck’s book (on smoothness and strong convexity)
4 10.11 no lecture
5 10.18 GD Methods I: GD method, Lipschitz optimization Lecture 4 Chapter 8.2 of Amir Beck’s book (on GD methods for convex and strongly convex functions)
6 10.25 GD Methods II: GD method, smooth optimization, Nesterov’s AGD, composite optimization Lecture 5 Chapter 3.2 of Bubeck’s book (on GD methods for smooth functions)
Chapter 10 of Amir Beck’s book (on composite optimization and proximal gradient)
7 11.01 Online Convex Optimization: OGD, strongly convex, exp-concave functions Lecture 6 Chapter 3 of Hazan’s book (on OGD for convex and strongly convex functions)
Chapter 4 of Hazan’s book (on ONS for exp-concave functions)
8 11.08 Prediction with Expert Advice: Hedge, minimax bound, lower bound Lecture 7 Lecture Note 2 of Luo’s course (on PEA problem)
9 11.15 Online Mirror Descent: OMD, FTRL, dual averaging Lecture 8 Chapter 6 of Orabona’s note (on OMD)
Chapter 7 of Orabona’s note (on FTRL)
Chapter 4 of Bubeck’s book (on MD and Dual Averaging)
10 11.22 Adaptive Online Convex Optimization: optimistic OMD, small-loss bound, variance bound, gradient-variation bound, self-confident tuning Lecture 9 Lecture Note 4 of Luo’s course (on small-loss PEA)
Chapter 4.2 of Orabona’s note (on small-loss OCO)
Chapter 7.11 of Orabona’s note (on variance/variation bound of OCO)
11 11.29 Online Learning in Games: two-player zero-sum games, repeated play, minimax theorem, fast convergence Lecture 10 Chapter 8 of Hazan’s book (on games and repeated play)
Lecture Note 7 of Luo’s course (on fast-convergence games )
12 12.06 Adversarial Bandits: MAB, IW estimator, Exp3, lower bound, bandit convex optimization, gradient estimator Lecture 11 Lecture Note 12 of Luo’s course (on adversarial MAB)
Chapter 12 of Lattimore and Szepesvári’s book (on Exp3.IX algorithm for high-probability regret)
13 12.13 Stochastic Bandits: MAB, UCB, linear bandits, self-normalized concentration, generalized linear bandits Lecture 12 Lecture Note 14 of Luo’s course (on stochastic MAB)
Lecture Note 15 of Luo’s course (on stochastic linear bandits)
Chapter 6 & 7 of Lattimore and Szepesvári’s book (on ETC and UCB)

Prerequisites

Familiar with calculus, probability, and linear algebra. Basic knowledge in convex optimization and machine learning.

Reading

Unfortunately, we don’t have a specific textbook for this course. In addition to the course slides and lecture notes (will write if time permits), the following books are very good materials for extra readings.

Some related courses:



Last modified: 2022-12-18 by Peng Zhao