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.
- Instructor: Peng Zhao (zhaop@lamda.nju.edu.cn)
- TA: Yu-Hu Yan (yanyh@lamda.nju.edu.cn) & Yu-Yang Qian (qianyy@lamda.nju.edu.cn)
- Location: Room 125, Duxia Library, Xianlin Campus (仙林校区杜厦图书馆125)
- Office hour: appointment by email
Announcement
- [ New! 2022.12.14] The homework ddl is postponed by 72 hours, please submit it on time.
- [2022.12.12] The twelfth lecture will take place on 12.13 (14:00-17:00), by Tencent meeting!
- [2022.12.12] The homework will due in one week, please do it as soon as possible.
- [2022.12.06] The eleventh lecture will take place on 12.06 (14:00-16:30), in person!
- [2022.11.28] The tenth lecture will take place on 11.29 (14:00-16:30) by Tencent meeting!
- [2022.11.22] The ninth lecture will take place on 11.22 (14:00-16:30), in person!
- [ New! 2022.11.19] Our homework is finally out, see details in the next section!
- [2022.11.15] The eighth lecture will take place on 11.15 (14:00-16:30), in person!
- [2022.11.07] The seventh lecture will take place on 11.08 (14:00-16:30), in person!
- [2022.11.01] The sixth lecture will take place on 11.01 (14:00-16:30) by Tencent meeting (due to COVID situation in Nanjing)!
- [2022.10.25] The fifth lecture will take place on 10.25 (14:00-16:30), in person!
- [2022.10.17] The forth lecture will take place on 10.18 (14:00-16:30), in person!
- [2022.10.11] Due to conflicted schedules, we have to cancel today’s lecture!
- [2022.10.02] The third lecture will take place on 10.04 (14:00-16:30) by Tencent meeting!
- [2022.09.26] The second lecture will take place on 09.27 (14:00-16:30), in person!
- [2022.09.19] Due to conflicted schedules, we have to postpone our first lecture for 1 hour. The first lecture will take place on 09.20 (15:00-17:30) by Tencent meeting.
- [2022.09.16] We now have a course website! The first lecture will take place on 09.20 (14:00-16:30).
Homework
- Homework file: homework_file.zip [update history]
- Instruction: submission rules.html
- ID List of who already submitted: list.txt
- DDL: 12.22 (Thursday) 18:00 Beijing time
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.
- Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. Foundation and Trends in Machine Learning, 2015.
- Amir Beck. First-Order Methods in Optimization. MOS-SIAM Series on Optimization, 2017.
- Elad Hazan. Introduction to Online Convex Optimization (second edition). MIT Press, 2022.
- Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2021.
- Francesco Orabona. A Modern Introduction to Online Learning. Lecture Notes, 2022.
Some related courses:
- CSCI 659: Introduction to Online Optimization/Learning, Fall 2022. University of South California, Haipeng Luo.
- CS292F (Spring 2020) Convex Optimization. UC Santa Barbara, Yu-Xiang Wang.
- COS 511: Theoretical Machine Learning, Fall 2022. Princeton University, Elad Hazan.
Last modified: 2022-12-18 by Peng Zhao