Optimization Methods for Machine Learning
Stochastic Gradient Descent (SGD), in one form or another, serves as the workhorse method for training modern machine learning models. Amidst its myriad variations, the SGD domain is both extensive and burgeoning, presenting a significant challenge for both practitioners and even experts to understand its landscape and inhabitants. This course offers a mathematically rigorous and comprehensive introduction to the field, drawing upon the most recent advancements and insights. It meticulously constructs a theory of convergence and complexity for SGD's serial, parallel, and distributed variants across strongly convex, convex, and nonconvex settings, incorporating randomness from subsampling, compression, and other sources.
The curriculum also delves into advanced techniques such as acceleration through Polyak momentum or Nesterov extrapolation. A notable portion of the course is dedicated to a unified analysis of a large family of SGD variants. Historically, these variants have demanded distinct intuitions, convergence analyses, and applications, evolving separately across various communities. This framework includes but not limited to the useful techniques: variance reduction, data sampling, coordinate sampling, arbitrary sampling, importance sampling, mini-batching, quantization, sketching, dithering, and sparsification, as well as their combinations. This comprehensive exploration aims to equip learners with a deep understanding of SGD's intricate landscape, fostering the ability to adeptly apply and innovate upon these methods in their work.
The curriculum also delves into advanced techniques such as acceleration through Polyak momentum or Nesterov extrapolation. A notable portion of the course is dedicated to a unified analysis of a large family of SGD variants. Historically, these variants have demanded distinct intuitions, convergence analyses, and applications, evolving separately across various communities. This framework includes but not limited to the useful techniques: variance reduction, data sampling, coordinate sampling, arbitrary sampling, importance sampling, mini-batching, quantization, sketching, dithering, and sparsification, as well as their combinations. This comprehensive exploration aims to equip learners with a deep understanding of SGD's intricate landscape, fostering the ability to adeptly apply and innovate upon these methods in their work.
Lecturer
Date
16th April ~ 11th June, 2024
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Tuesday,Thursday | 19:10 - 21:35 | A3-2-303 | ZOOM 11 | 435 529 7909 | BIMSA |
Prerequisite
Linear Algebra, Calculus, Convex Analysis, Probability theory
Syllabus
1. Introduction
2. Basic Tools from Convex Analysis, Optimization and Probability
3. Gradient Descent
4. Stochastic Gradient Descent (with Sampling and Minibatching)
5. Acceleration (Polyak Momentum and Nesterov Acceleration)
6. Adaptive Learning Rate (AdaGrad, RMSProp, AdaDelta and ADAM)
7. SGD with Gradient Shift
8. SGD with Control
9. Variance Reduction (SVRG and Loopless-SVRG, SAG and SAGA)
10. Distributed Training: Compressed Gradient Descent (CGD)
11. Randomized Coordinate Descent (RCD)
12. Federated Learning and Local Gradient Descent
13. General Convergence Analysis in the Convex Setting
14. General Convergence Analysis in the Nonconvex Setting
15. Stochastic Newton Method
16. Randomized BFGS
2. Basic Tools from Convex Analysis, Optimization and Probability
3. Gradient Descent
4. Stochastic Gradient Descent (with Sampling and Minibatching)
5. Acceleration (Polyak Momentum and Nesterov Acceleration)
6. Adaptive Learning Rate (AdaGrad, RMSProp, AdaDelta and ADAM)
7. SGD with Gradient Shift
8. SGD with Control
9. Variance Reduction (SVRG and Loopless-SVRG, SAG and SAGA)
10. Distributed Training: Compressed Gradient Descent (CGD)
11. Randomized Coordinate Descent (RCD)
12. Federated Learning and Local Gradient Descent
13. General Convergence Analysis in the Convex Setting
14. General Convergence Analysis in the Nonconvex Setting
15. Stochastic Newton Method
16. Randomized BFGS
Reference
1. Lectures on Convex Optimization – Y. Nesterov
2. Learning Theory from First Principles – F. Bach
3. First-Order Methods in Optimization – A. Beck
4. Large-Scale Convex Optimization: Algorithms and Analyses via Monotone Operators – E.K. Ryu and W.T. Yin
5. First-order and Stochastic Optimization Methods for Machine Learning – G.H. Lan
6. Accelerated Optimization for Machine Learning: First-Order Algorithms – Z.C. Lin, H. Li, C. Fang
2. Learning Theory from First Principles – F. Bach
3. First-Order Methods in Optimization – A. Beck
4. Large-Scale Convex Optimization: Algorithms and Analyses via Monotone Operators – E.K. Ryu and W.T. Yin
5. First-order and Stochastic Optimization Methods for Machine Learning – G.H. Lan
6. Accelerated Optimization for Machine Learning: First-Order Algorithms – Z.C. Lin, H. Li, C. Fang
Audience
Undergraduate
, Advanced Undergraduate
, Graduate
, Postdoc
, Researcher
Video Public
Yes
Notes Public
Yes
Language
English
Lecturer Intro
Yi-Shuai Niu is an Associate Professor at the Beijing Institute of Mathematical Sciences and Applications (BIMSA), specializing in optimization, scientific computing, machine learning, and computer science. He also holds a dual appointment at Tsinghua University (Qiuzhen College), where he teaches optimization- and AI-related courses and supervises graduate and undergraduate research. Before joining BIMSA, he was a Research Fellow at The Hong Kong Polytechnic University (2021–2022) and an Associate Professor at Shanghai Jiao Tong University (2014–2021), where he founded the Optimization and Interdisciplinary Research Group and held concurrent appointments at the SJTU-ParisTech Elite Institute of Technology and the School of Mathematical Sciences. His earlier positions included Postdoctoral Fellow at the University of Paris 6 (2013–2014), Junior Researcher at CNRS and Stanford University (2010–2012), and Lecturer at INSA Rouen (2007–2010). He received his Ph.D. in Mathematics–Optimization in 2010 and master’s degrees in "Pure and Applied Mathematics" and "Engineering Mathematics" in 2006.
His research focuses on optimization theory, machine learning, high-performance computing (HPC), and scientific software, with applications in natural language processing, autonomous driving, finance, image processing, turbulent combustion, polymer science, quantum computing, and plasma physics. He develops new theories and algorithms for large-scale nonconvex and nonsmooth optimization, together with efficient HPC-based solvers and scientific computing packages. He has developed more than 36 software packages and published over 40 papers in leading journals and conference proceedings, including the SIAM Journal on Optimization, Journal of Scientific Computing, and Combustion and Flame. He has served as PI of 7 research grants, including an NSFC Key Project, and as a core member of 5 international collaborative projects.
His honors include the Beijing High-Level Overseas Talent Programs, core membership in the Beijing Strategic Scientist Program, the First Prize of the 2017 Shanghai Teaching Achievement Award, and First Prizes of the Shanghai Jiao Tong University Teaching Achievement Awards in 2016 and 2017; he has received 17 MCM/ICM awards, including the 2017 INFORMS Best Paper Award. In 2026, he was selected for the International Congress of Basic Science (ICBS) Innovation Award and named a "Li Bing Engineering Innovation Scholar".
His research focuses on optimization theory, machine learning, high-performance computing (HPC), and scientific software, with applications in natural language processing, autonomous driving, finance, image processing, turbulent combustion, polymer science, quantum computing, and plasma physics. He develops new theories and algorithms for large-scale nonconvex and nonsmooth optimization, together with efficient HPC-based solvers and scientific computing packages. He has developed more than 36 software packages and published over 40 papers in leading journals and conference proceedings, including the SIAM Journal on Optimization, Journal of Scientific Computing, and Combustion and Flame. He has served as PI of 7 research grants, including an NSFC Key Project, and as a core member of 5 international collaborative projects.
His honors include the Beijing High-Level Overseas Talent Programs, core membership in the Beijing Strategic Scientist Program, the First Prize of the 2017 Shanghai Teaching Achievement Award, and First Prizes of the Shanghai Jiao Tong University Teaching Achievement Awards in 2016 and 2017; he has received 17 MCM/ICM awards, including the 2017 INFORMS Best Paper Award. In 2026, he was selected for the International Congress of Basic Science (ICBS) Innovation Award and named a "Li Bing Engineering Innovation Scholar".