ELE539/COS512: Optimization for Machine Learning
ELE539/COS512: Optimization for Machine Learning
Fall 2024, Tue. Thu. 09:30 am - 10:50 am, Equad B205
Instructor: Chi Jin Office hour: Equad C332, Wed. 4:00 - 5:00 pm
TA: Ahmed Khaled Office hour: Equad C332, Thur. 4:00 - 5:00 pm
Contents: Optimization theory---algorithms and complexity analyses
Grades: 5 problem sets (60%), 1 final exam (40%).
No late homework will be accepted. If you encounter unavoidable delays, please email me at least one day before the deadline to request an extension, providing a valid reason. Each request will be reviewed on a case-by-case basis.
See past versions of the course here: 2023 Version, 2021 Version
Convex Optimization
Introduction [note].
Oracle complexity and black-box model [note].
Convexity and subgradients [note].
Ellipsoid method [note]
Gradient descent for Lipschitz function [note].
Gradient descent for smooth function [note].
Accelerated gradient descent [note].
Lower bounds: linear span algorithms [note].
Mirror descent
Mirror descent II [note for 9 & 10].
Stochastic gradient descent [note].
Stochastic Variance Reduced Gradient [note].
Intro to nonconvex optimization, eigenvector problems and power method [note].
Lanczos algorithm [note].
Finding stationary points [note].
Escaping saddle points [note].
Escaping saddle points II [note].
Examples, optimal rates, high-order saddle points [note].
Nonsmooth nonconvex optimization [note].
Minimax optimization, GDA [note]
Adaptive optimization [note]
Parallel and distributed optimization [note]
Convex Optimization:
Intro, black-box model
Subgradient methods, gradient methods
Nesterov's acceleration, momentum
Lower bounds [Homework 1 due]
Mirror descent
Stochastic algorithms, variance reduction [Homework 2 due]
Adaptive methods
Nonconvex Optimization:
Eigenvector problems, finding stationary point [Homework 3 due]
Escaping saddle point
Non-smooth (weakly convex) optimization [Homework 4 due]
Minimax Optimization:
Convex-concave: gradient descent ascent, extragradient method
Nonconvex-concave: Gradient descent with max-oracle [Homework 5 due]
*Federated Learning
Convex Optimization: Algorithms and Complexity, by Sebastian Bubeck
Lecture Notes: Optimization for Machine Learning, by Elad Hazan
Convex Optimization, by Stephen Boyd and Lieven Vandenberghe
Elad Hazan, Optimization for Machine Learning
Yuxin Chen, Large-Scale Optimization for Data Science