CMPT 409/981 - Optimization for Machine Learning
Course overview
Numerical optimization plays a key role in designing better algorithms for data science and artificial intelligence. This course introduces the foundational concepts of convex and non-convex optimization with applications to machine learning. It will give the students experience in 1. Proving theoretical guarantees for optimization algorithms, 2. Analyzing machine learning (ML) problems from an optimization perspective and 3. Developing and analyzing new optimization methods for ML applications.
Prerequisites
Probability (e.g. CMPT 210, STAT 270, STAT 271), Linear Algebra (e.g. MATH 240), Basics of Multivariable Calculus (e.g. MATH 251). It is encouraged (though not necessary) for students to have taken (or be simultaneously taking) an introductory course on machine learning (e.g. CMPT 410/726).
Topics
- Basics: Subdifferentials, Optimality conditions, Lipschitz continuity, Convexity
- (Non)-Convex minimization: (Projected) Gradient Descent, Nesterov/Polyak momentum, Mirror Descent, Newton method
- (Non)-Convex minimization: Stochastic gradient descent (SGD), Variance reduction techniques, Adaptivity for SGD, Coordinate Descent
- Applications to training ML models (logistic regression, neural networks)
- Online optimization: Regret minimization, Follow the (regularized) leader, Adaptive gradient methods (AdaGrad, Adam, AMSGrad)
- Applications to Imitation learning, Reinforcement learning
- Min-Max optimization: Gradient Descent-Ascent, Extragradient
- Applications to GANs, Robust optimization
Lecture slides and readings
| Topic | Slides | References |
|---|---|---|
| Lipschitz continuity, Smoothness | Lecture 1 | [Matrix Cookbook] [List of inequalities] [Linear Algebra Recap] |
| Gradient descent convergence for smooth non-convex functions | Lecture 2 | [Multivariable Calculus] |
| Exact line-search, Convergence of GD with Back-tracking Armijo Line-search, Convex sets/functions | Lecture 3 | Nocedal and Wright (3.1, 3.2), Boyd (2, 3) |
| Convergence of GD for smooth, convex functions | Lecture 4 | Bubeck (3.2, 3.4), [Convex Optimization Cheat Sheet] |
| Nesterov acceleration and its convergence, Strongly-convex functions and GD convergence | Lecture 5 | Bubeck (3.7) |
| Heavy-Ball momentum | Lecture 6 | |
| Convergence of Heavy-Ball momentum for quadratics, Preconditioned Gradient Descent and Newton method | Lecture 7 | [Notes] |
| Convergence of Newton method for smooth, strongly-convex functions | Lecture 8 | Boyd (9.5) |
| Dealing with constrained domains, Stochastic gradient descent and its convergence for smooth functions | Lecture 9 | [Equivalent definitions of smoothness] [Equivalent definitions of strong convexity] |
| Stochastic Gradient Descent and its convergence for smooth, convex functions | Lecture 10 | |
| Convergence of SGD for smooth, strongly-convex functions, Interpolation | Lecture 11 | [SGD proof for smooth, strongly convex functions] [SGD under interpolation] |
| SGD under interpolation, Stochastic Line-Search | Lecture 12 | [Stochastic Line-Search] |
| Variance reduction & Convergence of SVRG, Lipschitz, convex functions | Lecture 13 | [SVRG], Bubeck (3.1) |
| Convergence of Subgradient Descent, Introduction to Online Optimization | Lecture 14 | Bubeck (3.1) |
| Online Convex Optimization, Online Gradient Descent, Online Mirror Descent | Lecture 15 | Orabona (2.1 - 2.2, 4.1, 7.1-7.3) |
| Online Mirror Descent | Lecture 16 | Bubeck (4.2-4.3) |
| Follow the (regularized) leader | Lecture 17 | Orabona (4.1, 4.2, 7.1-7.3) |
| AdaGrad and its regret bound | Lecture 18 | [Original AdaGrad paper] [AdaGrad for smooth functions] |
| Convergence of AdaGrad, Adam | Lecture 19 | [Original Adam paper] |
| Non-convergence of Adam | Lecture 20 | [Non-convergence of Adam and AMSGrad] |
| Min-Max Optimization, Gradient Descent Ascent and its convergence, Extra Gradient | Lecture 21 | |
| Convergence of Extra Gradient | Lecture 22 |
Books and references
- Lectures on Convex Optimization, Nesterov, 2018
- Convex Optimization, Boyd and Vandenberghe, 2004
- Convex Optimization: Algorithms and Complexity, Bubeck, 2014
- Numerical Optimization, Nocedal and Wright, 2006
- First-order Methods in Optimization, Beck, 2017
- A Modern Introduction to Online Learning, Orabona, 2019