Advanced Optimization (2026 Fall)

Course Information

This course aims to provide an overview of modern optimization theory designed for machine learning, particularly focusing on the gradient-based first-order optimization methods (with offline and online deployments), which serve as the foundational optimization tools for modern large-scale learning tasks.

Announcement

[2025.02.10] The lecture note will be updated in this website:** https://www.pengzhao-ml.com/course/AOptLectureNote

Homework

There will be two HWs. You will have a budget of 24 hours throughout the semester for which there is no late penalty. No further delayed hw will be accepted.

HW1 (2026.10.20 - 11.20)

 

Course agenda

Week Date Topic
Slides
Lecture Notes/ Readings
1 09.11 Course Introduction; Preliminaries Lecture 1 (v0911) on matrix norm
Chapter 3.2 of Boyd and Vandenberghe’s book (on basics of convexity)
Chapter 2.1 of Nesterov’s book (on "invention" of convexity)
2 09.18 Convex Problems Lecture 2 (v0918) Chapter 3 of Amir Beck’s book (on subgradients)
Chapter 5 of Amir Beck’s book (on smoothness and strong convexity)
  09.25 no lecture (due to Mid-Autumn Festival Holiday)    
  10.02 no lecture (due to National Holiday)    
3 10.09 GD Methods I: GD method, Lipschitz optimization, gradient descent lemma, Polyak step size Lecture 3 (v1009) Chapter 8.2 of Amir Beck's book (on GD methods for convex and strongly convex functions)
4 10.09 GD Methods II: GD method, smooth optimization, one-step improvement, Polyak's momentum, Nesterov's AGD, composite optimization Lecture 4 (v1009) Chapter 3.2 of Bubeck’s book (on GD methods for smooth functions)
Chapter 14 & 15 of Ashok Cutkosky's lecture note (on momentum and acceleration)
Chapter 10 of Amir Beck’s book (on composite optimization and proximal gradient)
5 10.16 Online Optimization I: interactive optimization, online gradient descent, convex, strongly convex; online-to-batch conversion, weighted O2B, SGD Lecture 5 (v1017) Chapter 3 of Hazan's book (on OGD for convex and strongly convex functions)
Chapter 3 of Orabona's book (on online to batch conversion)
  10.23 no lecture    
6 10.30 Online Optimization II: exp-concave, online Newton step, expert problem, Hedge Chapter 4 of Hazan's book (on ONS for exp-concave functions)
Lecture Note 2 of Luo's course (on PEA problem)
7 11.06 Online Mirror Descent: geometry, mirror descent, Bregman divergence, stability lemma, Bregman proximal inequality, mirror map, FTRL, dual averaging 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)
8 11.13 Adaptive Online Optimization: small-loss bound, self-confident tuning, optimistic OMD, conceptual OMD, predictable sequence, Lecture Note 4 of Luo’s course (on small-loss PEA)
Chapter 4.2 of Orabona’s note (on small-loss OCO)
9 11.20 Optimistic OMD: small-loss bound, gradient-variance bound, gradient-variation bound, implication to offline opt, Accelerated Methods, stabilized online-to-batch conversion Chapter 7.12 of Orabona’s note (on variance/variation bound of OCO)
Lecture Note 9: Optimism for Acceleration
10 11.27 Adversarial Bandits: MAB, IW loss estimator, Bandit Convex Optimization, Gradient Estimator, Self-concordant Barrier Lecture 6 of Luo’s course (on adversarial MAB)
Lecture 9 of Luo’s course (on self-concordant barrier for adversarial bandits)
11 12.04 Stochastic Bandits: MAB, exploration-exploitation dilemma, instance-dependent lower bound, ETC, epsilon-greedy, Upper confidence bound, Thompson Sampling Lecture Note 14 of Luo’s course (on stochastic MAB)
Chapter 6 & 7 of Lattimore and Szepesvári’s book (on ETC and UCB)
Chapter 16 of Lattimore and Szepesvári’s book (on instance-dependent lower bound)
12 12.11 Contextual Bandits: linear bandits, LinUCB, self-normalized concentration, generalized linear bandits, online reinforcement learning Lecture Note 15 of Luo’s course (on stochastic linear bandits)
Chapter 19 of Lattimore and Szepesvári’s book (on stochastic linear bandits)
Chapter 20 of Lattimore and Szepesvári’s book (on self-normalized concentration)
13 12.18 Final review and Advanced Topics see the references in the slides

Past courses

You may use the following links to access lecture slides and related materials from my past courses. While the overall structure remains consistent each year, I continually refine the content by adding new topics and improving the logical flow based on the feedback and my latest research understanding.

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: 2026-10-20 by Yifan Yang