Teaching · CS 331
Stochastic Gradient Descent Methods
CS 331 · Fall 2026 · Department of Computer Science, KAUST
Sundays 14:30–17:30 · Building 9, Room 3221 · 30 August–10 December 2026
Syllabus (subject to change)
Instructor: Peter Richtárik (peter.richtarik@kaust.edu.sa), office 3145, building 12, by appointment
TA: Majied Ammar Mahran (majiedammar.mahran@kaust.edu.sa)
About
Stochastic gradient descent (SGD), in one or another of its many variants, is the workhorse method for training modern supervised machine learning models. The world of SGD methods is vast and expanding, which makes it hard for practitioners and even experts to understand its landscape. This course is a mathematically rigorous and comprehensive introduction to the field, based on the latest results and insights.
We develop a convergence and complexity theory for serial, parallel, and distributed variants of SGD, in the strongly convex, convex, and nonconvex setup, with randomness coming from sources such as subsampling and compression. Additional topics such as acceleration via Nesterov momentum or curvature information will be covered as well. A substantial part of the course offers a unified analysis of a large family of SGD variants that have so far required different intuitions, convergence analyses, and applications, and that were developed separately in various communities. This includes methods with and without variance reduction, data sampling, coordinate sampling, arbitrary sampling, importance sampling, mini-batching, quantization, sketching, dithering, and sparsification, and their combinations.
Prerequisites
Strong experience with at least one high-level computing language (Python, Julia, C, MATLAB, or similar), mathematical maturity (the ability to read and write proofs), linear algebra, matrix theory, multivariate calculus, and probability.
Materials
Detailed lecture slides, including all necessary material and proofs, will be handed out before each lecture. Relevant papers are optional reading.
Assessment
- 35% homework (14 assignments, a mix of theoretical and coding problems; 2.5 points each)
- 30% midterm exam
- 30% final exam
- 5% active participation
Attendance at lectures is compulsory. No late submissions. Submit whatever you have done by the deadline, even if the assignment is incomplete.