Lecture 25: Stochastic Gradient Descent

What this lecture covers

This guest lecture, given by Suvrit Sra, asks why stochastic gradient descent (SGD) — an old, crude optimization method — remains the workhorse for training large-scale machine learning systems. It sits alongside the course's other work on least squares and optimization, reframing gradient descent as too expensive when the training set has millions or billions of examples, and showing why replacing the full gradient with a single random example still makes progress.

After watching, you can explain why machine learning cost functions take the "finite sum" form, why computing a full gradient does not scale, and why a stochastic gradient's unbiasedness and variance explain both SGD's fast early progress and its fluctuation near the optimum.

Key ideas

• Finite sum problem: machine learning cost functions are usually a sum of per-example losses, f(x) = sum of f_i(x), which is why gradients can be computed one example at a time.
• Full gradient descent bottleneck: computing the gradient of the entire sum at every step is expensive when n (data points) or d (dimensions) is huge.
• Stochastic gradient: at each step, pick one training example at random and use its gradient instead of the full gradient, making each step roughly n times cheaper.
• Unbiased estimate: in expectation over the random choice, the stochastic gradient equals the true gradient, which is why the method can still converge.
• Variance controls speed: the amount of noise in the stochastic gradient, not just its unbiasedness, determines how fast and how well SGD converges.
• Region of confusion: in a simple 1D least-squares example, far from the optimum a stochastic gradient points in the same direction as the true gradient, so progress is fast; near the optimum this no longer holds, and the method fluctuates instead of settling.
• With vs. without replacement: SGD is only well analyzed mathematically when examples are drawn with replacement, but every practical deep learning toolkit streams through shuffled data without replacement.
• Mini-batches: averaging the gradient over a small batch of examples reduces variance and enables parallelism across GPU cores, but very large batches shrink the useful "region of confusion" and can hurt generalization.

Walkthrough

Finite sum problems in machine learning (4:31)

The lecture sets up the training data as raw feature vectors and labels, and explains that large-scale machine learning means both the number of examples and their dimensionality can be huge. It introduces the finite sum formulation f(x) = sum f_i(x) and shows that least squares, LASSO, SVMs, logistic regression, and deep neural network losses all fit this same template.

Least squares and the drawback of full gradient descent (7:11)

Least squares regression is expanded into finite-sum form as a concrete example. The lecture then writes out ordinary gradient descent for this class of problems and asks the class to identify its weakness: computing one gradient step requires summing over every training example, which is prohibitively slow when there are millions of them.

Introducing stochastic gradient descent (12:48)

Students suggest sampling a subset of the data instead of using the full sum. The lecture formalizes this as SGD: at each iteration, pick one training index at random and step using only that example's gradient, making the update n times faster per step. A simulation compares gradient descent (which always decreases the cost) with SGD (which does not decrease it at every step but still trends toward the optimum), and shows that larger step sizes cause larger fluctuations, especially once the iterate is near the solution.

Why a single random gradient still works (35:47)

Using a 1D least-squares example, the lecture shows that far from the optimum, a stochastic gradient has the same sign as the true gradient, so following it still makes progress; this region is contrasted with a "region of confusion" near the optimum where individual gradients can point either way. This explains SGD's typical pattern of rapid early progress followed by fluctuation. The key mathematical property is then stated generally: the stochastic gradient is an unbiased estimate of the true gradient, and the speed of convergence depends on its variance.

Convergence proof and practical variants (40:02)

The lecture notes that a proof of convergence for non-convex problems (relevant to neural networks) exists but is not worked through in this session. It then compares sampling with replacement (the version that is mathematically well understood) against sampling without replacement (the version every practical toolkit actually uses), noting this gap as an open problem.

Mini-batches and their trade-offs (44:26)

Mini-batch SGD averages the gradient over a small batch rather than one example, reducing variance and enabling parallel computation across GPU cores. The lecture explains that very large mini-batches make the method resemble full gradient descent, which reduces the useful noise that helps generalization and can hurt performance on unseen data — an active area of research.

Open practical challenges (49:30)

The lecture closes by listing the moving parts practitioners must tune — step size, mini-batch size and sampling scheme, and gradient computation via backpropagation — and notes that explaining why SGD-trained neural networks generalize so well remains an open research question.

Before you watch

• Be comfortable with gradient descent and the basic least-squares optimization problem, covered earlier in this course.
• Review what an expectation and variance of a random variable mean, since the lecture leans on these to explain SGD's convergence behavior.

Check your understanding

1. Why does the finite sum structure of machine learning loss functions make gradient computation expensive at scale?
2. What does it mean for a stochastic gradient to be an "unbiased estimate" of the true gradient, and why is that not sufficient on its own for fast convergence?
3. In the 1D example, why does a stochastic gradient share the sign of the true gradient far from the optimum but not near it?
4. Why do practical toolkits sample training data without replacement even though the with-replacement version is the one that is mathematically analyzed?
5. Why can very large mini-batches hurt a neural network's performance on unseen data, despite improving parallelism?