Gradient Descent

Last lecture we hand-computed a forward and a backward pass through a \(2\)-\(2\)-\(1\) network, then applied the same matrix formulas to sixty-four hidden neurons and three hundred spiral points. For larger problems, we need to derive gradients automatically and avoid summing over the entire dataset at every step. The latter costs \(O(nd)\) arithmetic for \(n\) data points and \(d\) parameters. Automatic differentiation derives the gradient without changing it. Stochastic gradient descent reduces the computation per step by estimating the full gradient from a batch. This reduces the cost per step at the expense of sampling noise. Schedules and averaging address that noise, while momentum and adaptive scaling address the stretched bowl from the Optimization lecture.

Automatic Differentiation

Every computation we hand-derived last lecture is a computational graph: a directed graph whose nodes are values and whose edges record which value was computed from which.

In the diagram, the gray pills are the given data \(x\) and \(y\), the teal pills are the computed values (the pre-activation \(z\), the hidden activation \(h\), the prediction \(\hat y\), the loss \(\mathcal{L}\)) and the parameters \(w_1\) and \(w_2\), entering where they multiply; the teal arrow is the forward pass and the cardinal arrow is the backward pass, running the same edges in reverse.

Automatic differentiation (autodiff) computes derivatives from this graph. Each node applies one elementary operation, and every elementary operation has a one-line local derivative with respect to its own inputs: a product node contributes the other factor, a ReLU node contributes \(\mathbb{1}[z > 0]\), a squaring node contributes twice its input. The multivariate chain rule from last lecture then composes them into a gradient for the whole graph: \[ \frac{\partial \mathcal{L}}{\partial u} = \sum_{v} \frac{\partial \mathcal{L}}{\partial v}\cdot\frac{\partial v}{\partial u}, \] where the sum runs over the nodes \(v\) that \(u\) feeds directly. The rule depends on the graph’s local operations, so changing the architecture does not require a new symbolic derivation.

A backward sweep from \(\mathcal{L}\) toward the parameters visits each node and edge once and produces the derivative of one loss with respect to every node in the graph. A forward calculation that nudges one weight at a time would require a separate pass per parameter.

Autodiff removes the need to derive a gradient by hand, but evaluating a full-data gradient still requires summing over the dataset.

Stochastic Gradient Descent

Recall the shape of every loss we have written this semester, an average over data points with one term per example: \[ \mathcal{L}(\mathbf{w}) = \frac{1}{n}\sum_{i=1}^n \mathcal{L}_i(\mathbf{w}), \] where \(\mathcal{L}_i\) is the loss on example \(i\) alone. Its gradient inherits the same shape, so name the term belonging to one example the per-example gradient: \[ \mathbf{g}^{(i)} = \nabla_\mathbf{w}\mathcal{L}_i(\mathbf{w}) \in \mathbb{R}^d, \qquad \nabla_\mathbf{w}\mathcal{L}(\mathbf{w}) = \frac{1}{n}\sum_{i=1}^n \mathbf{g}^{(i)} . \] The full gradient is an average of \(n\) vectors, and Unit 1 spent an entire lecture on what to do with an average too expensive to compute exactly: sample it.

Draw a uniformly random batch of indices \(S \subseteq \{1,\ldots,n\}\) of size \(B\) and average over the batch alone: \[ \hat{\mathbf{g}}^{\mathrm{batch}} = \frac{1}{B}\sum_{i \in S}\mathbf{g}^{(i)} \in \mathbb{R}^d . \] Stepping along \(-\hat{\mathbf{g}}^{\mathrm{batch}}\) in place of the full gradient is stochastic gradient descent (SGD): \[ \mathbf{w}^{(t+1)} = \mathbf{w}^{(t)} - \alpha\, \hat{\mathbf{g}}^{\mathrm{batch}} . \] The hat marks an estimator of the full gradient in the sense of the Monte Carlo lecture. We will compute its expectation and typical error, as we did for the sample mean \(\hat\mu_n\).

The first one was our in-class exercise.

Claim: For a uniformly random batch \(S\) of size \(B\) drawn without replacement, the minibatch gradient is an unbiased estimator of the full gradient: \[ \mathbb{E}_S\big[\hat{\mathbf{g}}^{\mathrm{batch}}\big] = \nabla_\mathbf{w}\mathcal{L}(\mathbf{w}). \]

Proof of Claim

Rewrite the batch average as a sum over all \(n\) examples, with an indicator deciding which ones are present: \[ \hat{\mathbf{g}}^{\mathrm{batch}} = \frac{1}{B}\sum_{i=1}^n \mathbb{1}[i \in S]\,\mathbf{g}^{(i)} . \] Every index is equally likely to land in a uniformly random batch of size \(B\), so \(\Pr(i \in S) = B/n\) for every \(i\), and the expectation of an indicator is the probability of its event. Taking expectations gives: \[ \begin{align*} \mathbb{E}_S\big[\hat{\mathbf{g}}^{\mathrm{batch}}\big] &= \frac{1}{B}\sum_{i=1}^n \mathbb{E}_S\big[\mathbb{1}[i\in S]\big]\,\mathbf{g}^{(i)} \\&= \frac{1}{B}\sum_{i=1}^n \frac{B}{n}\,\mathbf{g}^{(i)} \\&= \frac{1}{n}\sum_{i=1}^n \mathbf{g}^{(i)} = \nabla_\mathbf{w}\mathcal{L}(\mathbf{w}). \end{align*} \] The first equality is linearity of expectation, which moves it inside the sum and past the fixed vectors \(\mathbf{g}^{(i)}\); the second substitutes \(\Pr(i \in S) = B/n\); the third cancels the \(B\). The argument does not require independence between the examples that land in a batch. Linearity of expectation holds regardless of their dependence, as it did for \(\hat\mu_n\) in Unit 1.

This is the Monte Carlo estimator with a vector in place of a scalar: the full gradient is the unknown mean \(\mu\), one example’s gradient is a single sampled score, and the batch is the sample. The sample-mean results from Unit 1 therefore describe batch gradients. Their variance determines how far \(\hat{\mathbf{g}}^{\mathrm{batch}}\) typically lies from the full gradient.

Batch Size, Variance, and the Learning Rate

Let \(\sigma^2\), the gradient noise, measure how much a single example’s gradient disagrees with the full gradient, averaged over the dataset: \[ \sigma^2 = \frac{1}{n}\sum_{i=1}^n\big\|\mathbf{g}^{(i)} - \nabla_\mathbf{w}\mathcal{L}(\mathbf{w})\big\|_2^2 . \] It is large exactly when different examples pull the weights in different directions. Averaging a batch of \(B\) of those disagreements shrinks the expected squared error of the estimate: \[ \mathbb{E}_S\Big[\big\|\hat{\mathbf{g}}^{\mathrm{batch}} - \nabla_\mathbf{w}\mathcal{L}(\mathbf{w})\big\|_2^2\Big] \approx \frac{\sigma^2}{B} . \] That is the Monte Carlo lecture’s rate for \(\mathrm{Var}(\hat\mu_n)\) with \(B\) in place of \(n\): the typical error of one batch gradient is \(\sigma/\sqrt{B}\), so halving it costs four times the batch. Problem 12 turns this rate into a sampling decision. When many augmented examples share one underlying source, their gradient errors share a component, so the correlation floor from Problem 1 determines how a fixed batch budget should be spread across sources.

In the plot, the teal dots are the measured error \(\|\hat{\mathbf{g}}^{\mathrm{batch}} - \nabla_\mathbf{w}\mathcal{L}(\mathbf{w})\|_2\) of a batch gradient, and the black line is the predicted \(\sigma/\sqrt{B}\): on log-log axes, the straight line of slope \(-\frac12\) from Unit 1’s advantage roll.

One batch gradient costs \(O(Bd)\) rather than \(O(nd)\), so for the compute of a single full-batch step we can take \(n/B\) stochastic ones: the number of affordable steps scales like \(1/B\) while the error of each scales only like \(1/\sqrt{B}\). That mismatch of exponents is the argument for SGD, since shrinking the batch buys steps faster than it costs accuracy.

Near the minimum, the full gradient approaches zero while \(\sigma^2\) need not, since individual examples can favor different minimizers. With a constant learning rate, the update \(-\alpha\hat{\mathbf{g}}^{\mathrm{batch}}\) then has typical length \(\alpha\sigma/\sqrt{B}\), so SGD fluctuates around the minimum instead of converging to it exactly. The demo shows this floor: the full-batch run’s distance keeps decreasing while the stochastic runs flatten out. Increasing \(B\) lowers the floor but increases the arithmetic per step; decreasing \(\alpha\) lowers it without increasing that arithmetic.

Learning Rate Schedules

A learning rate schedule makes the learning rate a function of the step count instead of a constant: \[ \alpha^{(t)} = \frac{\alpha^{(0)}}{1 + t/\tau}, \] where \(\alpha^{(0)} > 0\) is the starting learning rate and \(\tau > 0\) is the step count at which it has fallen to half of that. Early, when the true gradient dwarfs the noise, \(\alpha^{(t)} \approx \alpha^{(0)}\) and the steps are long; late, when the gradient is mostly noise, \(\alpha^{(t)}\) has shrunk and the noise ball closes in along with it. A schedule gets the small final error of a small learning rate without the slow start, which no constant \(\alpha\) can do.

(In practice the decay curve is chosen empirically, usually linear or cosine decay toward zero, often preceded by a short warmup that increases \(\alpha\) gradually while early gradients may be poorly scaled.)

A schedule reduces the effect of gradient noise near the minimum, but it does not change the bowl’s conditioning.

Momentum

Recall that shape: writing \(\lambda_{\max}\) and \(\lambda_{\min}\) for the largest and smallest curvature of the loss, the Optimization lecture showed that gradient descent’s trouble is governed by their ratio: \[ \kappa = \frac{\lambda_{\max}}{\lambda_{\min}} . \] A step size small enough not to overshoot the steep direction is far too small for the shallow one, so the path zig-zags across the valley and the error contracts by only \(\frac{\kappa - 1}{\kappa + 1}\) per step.

The mechanical fix starts from noticing that the zig-zag is self-cancelling: across the valley the gradient alternates sign, while along the valley it points the same way every step, so averaging the gradients over time cancels the alternating part and keeps the consistent one. Momentum implements this average. Write \(\hat{\mathbf{g}}^{(t)}\) for the batch gradient at step \(t\), and keep a running velocity \(\mathbf{v}^{(t)} \in \mathbb{R}^d\): \[ \mathbf{v}^{(t+1)} = \beta\,\mathbf{v}^{(t)} + \hat{\mathbf{g}}^{(t)}, \qquad \mathbf{w}^{(t+1)} = \mathbf{w}^{(t)} - \alpha\,\mathbf{v}^{(t+1)}, \] where \(\mathbf{v}^{(0)} = \mathbf{0}\) and \(\beta \in [0,1)\) (often \(0.9\)) sets how much of the previous velocity survives. Physically it is a ball rolling downhill: a new push changes its velocity but does not erase the speed it already had.

Substituting the velocity definition recursively until the chain reaches \(\mathbf{v}^{(0)} = \mathbf{0}\) gives: \[ \begin{align*} \mathbf{v}^{(t+1)} &= \hat{\mathbf{g}}^{(t)} + \beta\,\mathbf{v}^{(t)} \\&= \hat{\mathbf{g}}^{(t)} + \beta\,\hat{\mathbf{g}}^{(t-1)} + \beta^2\,\mathbf{v}^{(t-1)} \\&= \hat{\mathbf{g}}^{(t)} + \beta\,\hat{\mathbf{g}}^{(t-1)} + \beta^2\,\hat{\mathbf{g}}^{(t-2)} + \beta^3\,\mathbf{v}^{(t-2)} \\&= \sum_{k=0}^{t}\beta^k\,\hat{\mathbf{g}}^{(t-k)} . \end{align*} \] The velocity is a weighted average of every gradient so far, with weights decaying geometrically into the past. The weights sum to nearly \(\frac{1}{1-\beta}\), which is \(10\) at \(\beta = 0.9\), so momentum’s effective step is about ten times what the same \(\alpha\) would give plain SGD, and raising \(\beta\) means lowering \(\alpha\). As in Unit 1, averaging several noisy gradients reduces variance. With momentum, however, the averaged gradients were measured at older weights, so variance reduction can come with staleness bias. If you raised \(\beta\) from \(0.9\) to \(0.99\) and wanted the effective step to stay where it was, what would \(\alpha\) have to become?

Consider one step, as we will at the board, on the univariate quadratic of curvature \(\lambda\): \[ \mathcal{L}(w) = \tfrac{\lambda}{2}w^2, \qquad \nabla_w\mathcal{L}(w) = \lambda w . \] Set \(\lambda = 1\), learning rate \(\alpha = 0.3\), momentum \(\beta = 0.8\), and starting point \(w^{(0)} = 4\). The first step is identical for both methods because \(v^{(0)} = 0\), so the momentum term is zero: \[ v^{(1)} = 0.8\cdot 0 + 4 = 4, \qquad w^{(1)} = 4 - 0.3\cdot 4 = 2.8 . \] The second step is where they separate, since plain gradient descent takes another ordinary step from \(w^{(1)} = 2.8\) while momentum adds the remembered velocity first: \[ w^{(2)}_{\text{gd}} = 2.8 - 0.3\cdot 2.8 = 1.96, \qquad v^{(2)} = 0.8\cdot 4 + 2.8 = 6.0, \qquad w^{(2)}_{\text{mom}} = 2.8 - 0.3\cdot 6.0 = 1.0 . \]

In the plot, the black circle and square mark the shared start and first step, and the two colored points are where the second step lands. Momentum ends at \(1.0\) against plain gradient descent’s \(1.96\), twice as close to the minimum after the same two gradient evaluations. One dimension has no zig-zag to cancel. Here the accumulated velocity produces a longer step after several consecutive gradients point in the same direction.

In more than one dimension, momentum both cancels alternating components and accumulates consistent components. Eliminating \(\mathbf{v}\) turns the two update rules into a single two-term recurrence in \(\mathbf{w}\), and tracking that recurrence’s roots gives the per-step contraction of momentum with well-chosen \(\alpha\) and \(\beta\): \[ \frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1} \qquad\text{against}\qquad \frac{\kappa-1}{\kappa+1} \quad\text{for plain gradient descent.} \] At the \(\kappa = 15\) of the demo’s bowl that is \(0.59\) against \(0.88\) per step. Momentum replaces the condition number with its square root.

Momentum smooths the direction of a step, but it still applies one \(\alpha\) to every parameter. A single learning rate must therefore serve directions of different curvature.

Adaptive Methods

The last family adapts the size of the step per parameter, using gradient history as a stand-in for curvature: a consistently large gradient marks a steep direction that should take small steps, and a consistently small one marks a shallow direction that should take large steps.

Adagrad accumulates the squared gradients of each parameter \(j\) and divides that parameter’s step by the square root of the total: \[ s_j^{(t)} = \sum_{r=1}^{t}\big(\hat g_j^{(r)}\big)^2, \qquad w_j^{(t+1)} = w_j^{(t)} - \frac{\alpha}{\sqrt{s_j^{(t)}} + \epsilon}\,\hat g_j^{(t)}, \] where \(\hat g_j^{(t)}\) is coordinate \(j\) of the batch gradient at step \(t\) and \(\epsilon\) (around \(10^{-8}\)) keeps the denominator away from zero. Because \(s_j^{(t)}\) is a sum of squares, it only increases, so the effective learning rate decays toward zero even if training is unfinished.

RMSProp replaces that running sum with an exponential moving average, the same construction as momentum’s velocity applied to squared gradients: \[ s_j^{(t)} = \beta_2\, s_j^{(t-1)} + (1-\beta_2)\big(\hat g_j^{(t)}\big)^2 , \] with \(\beta_2\) close to \(1\). The geometric decay limits the influence of old gradients, so the step size in a coordinate can increase after its recent gradients become smaller.

Adam (Kingma and Ba) runs both averages at once: \[ v_j^{(t)} = \beta_1 v_j^{(t-1)} + (1-\beta_1)\hat g_j^{(t)}, \qquad s_j^{(t)} = \beta_2 s_j^{(t-1)} + (1-\beta_2)\big(\hat g_j^{(t)}\big)^2 , \] with \(\beta_1 = 0.9\) and \(\beta_2 = 0.999\) as the usual defaults. The step then divides momentum’s smoothed direction by RMSProp’s per-parameter scale: \[ w_j^{(t+1)} = w_j^{(t)} - \alpha\,\frac{v_j^{(t)} / (1-\beta_1^t)}{\sqrt{s_j^{(t)} / (1-\beta_2^t)} + \epsilon} . \] Both averages start at zero, so early steps are biased toward zero. Dividing by \(1 - \beta_1^t\) and \(1 - \beta_2^t\), the total weights used so far, corrects that bias. That bias correction makes the weighted average comparable across early and late iterations.

The class demo runs gradient descent, SGD, and Adam on this same stretched bowl built out of data, then increases the batch size to measure the lower noise floor. Adam’s path is smoother than the gradient descent and SGD paths because its per-coordinate scaling reduces the effect of the bowl’s anisotropy. That scaling does not reduce the variance of the batch gradient; increasing the batch size does.

Gradients Through Deep Networks

Last lecture’s hand computation included a dead ReLU that zeroed an entire gradient path. In a network with many layers, repeated small or zero derivatives can prevent early layers from receiving a useful gradient; next lecture develops methods that control this effect.

Once a gradient is estimated by averaging sampled data, its bias and variance become part of the training analysis, and averaging can reduce only the uncorrelated part of its noise.