Downhill: Gradient Descent, and the Two Steps Everyone Skips

Restated so this chapter stands on its own: the eight parts from the conveyor belt of Chapter 1, but asked a different question. Not accept or reject — that comes back later — but predict a part's weight from its width.

import numpy as np

WIDTH  = np.array([18.0, 19.5, 20.2, 21.0, 24.0, 25.5, 23.0, 26.0])
WEIGHT = np.array([47.0, 52.0, 49.0, 55.0, 61.0, 66.0, 70.0, 58.0])

x = WIDTH  - WIDTH.mean()      # 22.15 mm
y = WEIGHT - WEIGHT.mean()     # 57.25 g

The measurements are centred, exactly as in Chapter 1 and for a reason that returns with interest before this chapter is over. The model is a line, $\hat{y} = a x + b$, and the loss is the mean squared error the previous chapter derived:

Two parameters. Why not just try lots of values? Let us actually do it — a grid from $a = 0$ to $5$ and $b = -5$ to $5$, in steps of $0.01$:

grid 501 x 1001 = 501,501 evaluations in 3.67 s
  best found: a = 2.1000, b = -0.0000, L = 24.592450

Half a million evaluations to pin two numbers down to two decimal places — and that second is wall clock on one machine, so a rerun lands anywhere from three to six; the evaluation count and the minimum are the part that reproduces. Gradient descent, at the end of this chapter, gets four decimal places in eight steps and the full float64 answer in thirty-six.

But speed is not the argument, and this is the point that decides the whole course. Grid search costs $k^P$ evaluations for $P$ parameters at $k$ values each. With a thousand values per axis:

The third row is not a big number, it is a meaningless one — there are roughly $10^{80}$ atoms in the observable universe. Search does not get slower as models grow; it stops existing. Everything that follows exists because of that table.

Fix $b = 0$ for a moment so there is one parameter and one curve, which is the picture the last chapter left you with. Take a point on it, $a = 1$, and ask: if I nudge $a$ by a small amount $h$, how much does the loss move, per unit of nudge?

That ratio is a rise over run — the slope of the straight line through two points on the curve. As $h$ shrinks, the two points slide together and the line becomes the tangent. Its slope is the derivative $L'(a)$: the rate at which the loss changes per unit of change in $a$. Not an approximation of anything, and not an infinitely small quantity. A limit of ordinary ratios.

It is worth running, because the numbers say something the definition does not:

def loss1(a):
    return np.mean((a * x - y) ** 2)

for h in [1.0, 1e-2, 1e-4, 1e-6, 1e-8, 1e-10, 1e-12, 1e-14]:
    q = (loss1(1.0 + h) - loss1(1.0)) / h
    print(f"h = {h:<8.0e}   slope estimate = {q:.10f}   error = {abs(q + 16.385):.3e}")

h = 1e+00      slope estimate = -8.9400000000    error = 7.445e+00
h = 1e-02      slope estimate = -16.3105500000   error = 7.445e-02
h = 1e-04      slope estimate = -16.3842555001   error = 7.445e-04
h = 1e-06      slope estimate = -16.3849925556   error = 7.444e-06
h = 1e-08      slope estimate = -16.3850003787   error = 3.787e-07
h = 1e-10      slope estimate = -16.3850444324   error = 4.443e-05
h = 1e-12      slope estimate = -16.3851154866   error = 1.155e-04
h = 1e-14      slope estimate = -17.0530256582   error = 6.680e-01

Two things happen here and both are load-bearing.

The error is not vaguely proportional to $h$ — it is exactly $7.445\,h$. Divide $h$ by a hundred, the error divides by a hundred, to four significant figures every time. That constant is not decoration: it is half the second derivative of the loss, and it is the first appearance of an idea two sections from now — that a curve near a point looks like a line plus a correction proportional to $h^2$.

And then the pattern breaks. Below $h = 10^{-8}$ the estimate gets worse, and at $10^{-14}$ it is wrong in the second digit. Nothing mathematical happened; the last chapter's floating-point box did. $L(a+h)$ and $L(a)$ agree in their first ten digits, subtracting them destroys those digits, and dividing the wreckage by a tiny number amplifies what is left. There is a best $h$ — here around $10^{-8}$, roughly the square root of the machine epsilon — and going smaller is not more careful, it is less. Remember that; a function at the end of this chapter depends on it.

The exact slope, from calculus rather than measurement, is $-16.385$. So we can stop measuring and start deriving.

Here is the idea the rest of the course is built on, stated once, plainly.

To compose two functions is to feed one into the other: $(f \circ g)(x) = f(g(x))$. Nothing more.

A deep network is not like a composition. It is one. A layer is a function; stacking layers is composing them; "depth" is the number of functions in the chain. When Chapter 5 builds a network, it is building $f_4 \circ f_3 \circ f_2 \circ f_1$ and nothing else. Which means the single most important rule of calculus, for our purposes, is the one that differentiates a composition:

Rates multiply. If $g$ changes three times as fast as $x$, and $f$ changes twice as fast as $g$, then $f$ changes six times as fast as $x$. That is the whole content, and it is why a signal passing back through ten layers gets multiplied by ten numbers — which is why Chapter 6 spends a section on what happens when those numbers are all slightly less than one.

Use it on our loss. Write the residual $r_i = a x_i + b - y_i$, so that $L = \frac{1}{n}\sum r_i^2$. Each $r_i$ depends on $a$ through the inner function $a x_i$, whose derivative is $x_i$. Chain rule, term by term:

Those curly $\partial$ symbols mark a partial derivative: differentiate with respect to one variable and treat every other as a constant. Nothing new happens — it is the same limit as before, taken along one axis. Collect the partials into a vector and you have the gradient:

At the point $(a, b) = (1, 4)$ that vector is $(-16.385,\ 8.0)$. Two numbers. The question is what they mean, and this is the first step everyone skips.

The gradient is a vector of slopes along the axes. That is all we have proved. It is not obvious — it should not be obvious — that assembling them into a vector produces something that points anywhere in particular.

So define the thing we actually want. Pick a unit vector $\mathbf{u}$, a direction. The directional derivative is the rate the loss changes as you walk that way:

The chain rule turns this into something computable. Walking along $\mathbf{u}$ changes $a$ at rate $u_1$ and $b$ at rate $u_2$, and the contributions add:

The rate of change in any direction is the dot product of the gradient with that direction. And now the punchline, which is one line of geometry. Writing the dot product with the angle $\phi$ between the vectors,

since $\mathbf{u}$ has length 1. The only thing you control is $\cos\phi$, which is largest at $\phi = 0$ and smallest at half a turn, $\phi = 180$ degrees. So:

• The steepest ascent is along $\nabla L$ itself, and the slope there is exactly $\lVert \nabla L \rVert$.
• The steepest descent is along $-\nabla L$, and the slope there is $-\lVert \nabla L \rVert$.
• Perpendicular to the gradient, the loss does not change at all. That is why a contour map's lines cross the gradient at right angles.

That is the minus sign. Not a convention, not a sign flip someone chose: the direction of fastest decrease is the negative gradient because $\cos\phi$ is minimised at half a turn, and for no other reason.

Since this is a claim about all directions, test it against all directions. Sample 3,600 of them, one per tenth of a degree, and measure each one by nudging:

theta = np.array([1.0, 4.0])
g = grad(theta)
print("gradient      ", g)
print("its length    ", np.linalg.norm(g))
print("its angle     ", np.degrees(np.arctan2(g[1], g[0])) % 360, "degrees")

best = max(
    ((loss(theta + 1e-6 * u) - loss(theta - 1e-6 * u)) / 2e-6, np.degrees(ang))
    for ang, u in (
        (a, np.array([np.cos(a), np.sin(a)])) for a in np.arange(3600) * 2 * np.pi / 3600
    )
)
print("steepest slope", best[0], "at", best[1], "degrees")

gradient       [-16.385   8.   ]
its length     18.23371122399386
its angle      153.97598928042032 degrees
steepest slope 18.233709624837502 at 154.0 degrees

A search that knows nothing about gradients, over 3,600 directions, finds its steepest climb at 154.0 degrees — the gradient's own direction, to within the 0.1-degree resolution of the search. And the slope it finds there, 18.2337, is the gradient's length to six figures. The theorem is not a story about what gradients mean; it is a measurable fact, and that is the measurement.

Now the second skipped step. We know which way is down. It does not follow that walking that way lowers the loss, because "down" is a statement about an infinitesimal nudge and a step is not infinitesimal.

The bridge is linearisation. Near a point, a smooth function is its tangent plus a correction:

That is the first-order Taylor expansion. The discarded $O(\lVert\boldsymbol{\delta}\rVert^2)$ is the curvature — the same term that made the slope table's estimate wrong by exactly $7.445\,h$. Put in the step we intend to take, $\boldsymbol{\delta} = -\eta \nabla L$:

The loss drops by $\eta \lVert \nabla L \rVert^2$. Every part of that is non-negative, so the promise is real — for a small enough $\eta$, because the neglected term grows like $\eta^2$ and eventually eats it. That is the whole theory. Here is the promise being kept, and then broken:

eta = 0.2       promised    66.49364500   delivered   -16.01619240   ratio -0.240868
eta = 0.1       promised    33.24682250   delivered    12.61936315   ratio  0.379566
eta = 0.01      promised     3.32468225   delivered     3.11840766   ratio  0.937957
eta = 0.001     promised     0.33246822   delivered     0.33040548   ratio  0.993796
eta = 0.0001    promised     0.03324682   delivered     0.03322620   ratio  0.999380
eta = 1e-05     promised     0.00332468   delivered     0.00332448   ratio  0.999938

Read it from the bottom. As $\eta$ shrinks the delivered drop converges on the promised one — ratio 0.99938, then 0.99994 — which is Taylor's theorem being correct. Read it from the top and at $\eta = 0.2$ the delivered "drop" is negative sixteen. The step went downhill and the loss went up.

So the update rule is

and it comes with a condition nobody states, which is that $\eta$ is small enough. Small enough compared to what, exactly, is the next section.

Start with the simplest valley there is, $f(x) = x^2$, where $f'(x) = 2x$. One step of gradient descent is

The position is multiplied by $(1 - 2\eta)$ every step. That is a geometric sequence, and geometric sequences have exactly one rule: they shrink when the multiplier is smaller than 1 in absolute value and grow otherwise. So $\lvert 1 - 2\eta \rvert < 1$, which is $0 < \eta < 1$.

The boundary is at $\eta = 1$ exactly. Not "around 1", not "1 is usually too big". At $\eta = 1$ the multiplier is $-1$ and the point bounces between $x$ and $-x$ forever, neither approaching nor escaping. Below it, converge; above it, diverge. The interval splits again at $\eta = 0.5$, where the multiplier changes sign: below that the approach is monotone, above it the point overshoots and alternates sides, and at exactly $0.5$ the multiplier is 0 and one single step lands on the minimum.

Four regimes, from four lines of algebra. Go and cross the boundaries yourself:

And now the interesting one:

Now the general rule, which falls out of the same argument. The multiplier $1 - 2\eta$ was really $1 - \eta f''$, and near a minimum a multi-parameter loss has one such number per direction — the eigenvalues of the matrix of second derivatives. Every direction has to be stable at once, so the ceiling is set by the largest:

For $f(x) = x^2$, $f'' = 2$, ceiling 1, which is what we just derived. For our belt, the second-derivative matrix is $\frac{2}{n} A^{\top} A$ with $A$ the two-column matrix of inputs, and its eigenvalues are 2 and 14.89, so the ceiling is $2 / 14.89 = 0.13432$. That is a prediction with five significant figures in it. Test it:

lr=0.1343    -> L =      24.5924
lr=0.13431   -> L =      24.5924
lr=0.13432   -> L =       4707.8       BLEW UP
lr=0.13433   -> L =  4.00452e+16       BLEW UP
lr=0.1344    -> L = 1.18229e+107       BLEW UP

Five decimal places of agreement between a line of linear algebra and a hundred thousand iterations of a for loop.

And here is where Chapter 1 comes back. Everything above used the centred measurements. Run the identical code on raw millimetres and grams and the eigenvalues are 0.0298 and 998.1 instead of 2 and 14.89. The ceiling collapses from 0.134 to 0.002004 — just as exactly, converging at lr=0.002003 and blowing up at lr=0.002004.

Worse than the ceiling is the ratio between the eigenvalues. The condition number measures how far from round the valley is: a long thin trench forces a rate small enough for the steep walls, and then the floor of the trench gets walked at that same crawl. Ours goes from 7.44 centred to 33,452 raw. With the best rate each version can take:

Same data, same code, same answer at the end — and eight thousand times the work, because nobody subtracted a mean. In Chapter 1 the same omission cost the perceptron a factor of six thousand in epochs, and the diagnosis there was geometric: the data floated far from the origin. It is the same geometry here in an optimisation costume, and it is why input normalisation is not hygiene advice but arithmetic.¹

Nothing above needed a library. Here is the whole optimiser.

def loss(theta):
    a, b = theta
    return np.mean((a * x + b - y) ** 2)


def grad(theta):
    a, b = theta
    residual = a * x + b - y
    return np.array([np.mean(2 * residual * x), np.mean(2 * residual)])


def descend(theta, lr, steps):
    theta = np.array(theta, dtype=float)
    for _ in range(steps):
        theta = theta - lr * grad(theta)   
    return theta


theta = descend([0.0, 0.0], lr=0.05, steps=60)
print(theta, loss(theta))

[ 2.10040296e+00 -2.76445533e-15] 24.592448791134984

The closed-form least-squares answer for these eight points is $a = 2.100403$, $b = 0$, with a loss of $24.592449$. The loop found it to eight significant figures without knowing that a closed form exists — which matters, because from Chapter 5 onward there will not be one.

The trajectory, since watching it is the point:

   0 a=0.000000 b=0.000000 L=57.437500
   1 a=1.563750 b=0.000000 L=26.736582
   2 a=1.963288 b=-0.000000 L=24.732418
   5 a=2.098116 b=-0.000000 L=24.592488
  10 a=2.100400 b=-0.000000 L=24.592449
  60 a=2.100403 b=-0.000000 L=24.592449

Most of the distance is covered in the first two steps, because the gradient is largest when you are furthest from the bottom and shrinks as you approach. Gradient descent slows down automatically near a minimum. That is a feature and it is also, in Chapter 6, a problem.

The argument so far has a hole in it. The step stops when $\nabla L = \mathbf{0}$, and we have been calling that "the minimum". A point with zero gradient is a critical point, and being a minimum is only one of the ways to be one:

• a local minimum: uphill in every direction, but possibly not the lowest such point anywhere;
• a local maximum: downhill in every direction;
• a saddle point: uphill in some directions and downhill in others. The surface $f(x,y) = x^2 - y^2$ has $\nabla f = (2x, -2y)$, which is zero at the origin, where the function is a minimum along the $x$-axis and a maximum along the $y$-axis at the same time.

Gradient descent cannot tell these apart, because it only ever looks at the gradient, and the gradient is zero at all three.

Our line has one critical point and it is the answer — a squared-error loss over a linear model is convex, a single bowl, and descent on it cannot fail to find the global minimum. That property does not survive contact with this course. The loss of a neural network is not convex, and from Chapter 5 onward "the minimum" is not a thing that exists: there are many, of different depths, and which one you get depends on where you started. That is one sentence and stays one sentence, because the theory is large and the practical consequence is small.

You can see the whole consequence on one curve. Take $f(x) = \tfrac{x^4}{4} - \tfrac{x^2}{2} + \tfrac{x}{10}$, which has two valleys of different depths:

   x =  -1.046681   f(x) =  -0.352386   minimum
   x =   0.101031   f(x) =   0.005026   maximum
   x =   0.945649   f(x) =  -0.152639   minimum

Landing in the shallow valley is 56.7% worse in loss, and the algorithm has no way to know, because from inside a valley every direction is uphill. There is no repair for this in gradient descent and none is coming. What there is, in practice, is the finding that it matters far less than this picture suggests — in the very high dimensions of a real network most critical points turn out to be saddles rather than traps,² and Chapter 5 measures how often a small network actually gets stuck.

One thing about grad above should bother you: it sums over the entire dataset for every step. Eight parts is nothing. A million is a million gradient computations to move the parameters once.

The escape is that the gradient is an average, and an average can be estimated from a sample. Compute it on a random handful — a minibatch — and step on that. The estimate is noisy; it is also unbiased, and hundreds of cheap noisy steps beat one expensive exact one. On a hundred thousand synthetic parts, counting per-example gradients rather than steps:

Two hundred and nineteen times less arithmetic to reach the same place. And the extreme — one example at a time, the original stochastic approximation of Robbins and Monro³ — is not the winner: it is five times worse than batches of 32, because 32 examples cost almost nothing more than one on hardware that multiplies matrices, while the noise falls off with the square root of the batch size. That trade-off is why every training script you will ever read has a batch_size in it.

Momentum is the other cheap fix, and it is aimed squarely at the trench. In a badly conditioned valley the steps zig-zag across the narrow direction while creeping along the long one. Momentum keeps a running average of past gradients, so the oscillating components cancel and the consistent one accumulates:⁴

Two extra lines. On the raw uncentred belt — condition number 33,452, the worst case we have — at the best rate plain descent can take:

momentum beta=0.0   ->    79,513 steps to 1%
momentum beta=0.9   ->     1,609 steps to 1%
momentum beta=0.99  ->       461 steps to 1%

A factor of 172 for two lines of code. Chapter 6 turns this into Adam; the mechanism is already here.

Every gradient in this chapter was derived by hand and could therefore be wrong. The fix is the slope table from the beginning: measure the derivative numerically and compare. Use the central difference, $\frac{L(\theta+h) - L(\theta-h)}{2h}$, which cancels the leading error term and is a great deal more accurate for the same $h$.

def numeric_grad(f, theta, h=1e-5):
    theta = np.asarray(theta, dtype=float)
    out = np.zeros_like(theta)
    for i in range(theta.size):
        bump = np.zeros_like(theta)
        bump[i] = h
        out[i] = (f(theta + bump) - f(theta - bump)) / (2 * h)     
    return out


def gradcheck(f, df, theta, h=1e-5):
    analytic = np.asarray(df(theta), dtype=float)
    numeric = numeric_grad(f, theta, h)
    return np.max(np.abs(analytic - numeric) / np.maximum(1e-8, np.abs(analytic) + np.abs(numeric)))

The relative form of the comparison matters: an absolute difference of $10^{-4}$ is a disaster on a gradient of size $10^{-3}$ and irrelevant on one of size $10^{6}$.

relative error: 1.8929136036763527e-11
with 2 dropped: 0.33333333331650744

The first line is the hand-derived gradient above. The second is the same function with the factor of 2 left off one component — a typo of a single character — and the check catches it immediately. Anything below about $10^{-7}$ is agreement; anything above $10^{-4}$ is a bug. Keep this function: Chapter 5 uses it to debug an automatic differentiation engine, and it is the only reason a wrong gradient is findable at all.

Everything in this chapter rested on one assumption that was never stated: that you can write $\partial L / \partial \theta$ down.

For a line with two parameters, that was a line of algebra. It stops being one almost immediately. Ask a symbolic algebra system for the derivative of a network's loss with respect to a single first-layer weight, for a single example, and count the arithmetic in the answer:

The third row is a network with 57 parameters — a network so small it would be a footnote in Chapter 6 — and writing its gradient out by hand means about 97,869 operations for one training example. There is no notation that rescues this. What rescues it is the observation that the chain rule applied to a composition has enormous structure, that the same intermediate quantities appear over and over, and that computing them in the right order gets all the derivatives for roughly the price of one forward pass. That is Chapter 5.

But there is a smaller problem first, and it is waiting immediately.

We now have a machine that will roll downhill on any differentiable loss. Point it at the belt's original question — accept or reject, a target that is 1 or 0 — put a sigmoid on the output so it predicts a probability, and minimise squared error. It will run. It will also barely move when it is most wrong, and the gradient says why:

A model that is confidently, catastrophically wrong — predicting 0.0000454 when the answer is 1 — produces a squared-error gradient of $9 \times 10^{-5}$. It has no idea it is in trouble. The other column, from a loss we have not derived yet, reports 1.0: maximum urgency, exactly where it is deserved.

Which raises the question the next chapter opens with. The last chapter said a loss is an assumption about the noise, and squared error assumes Gaussian noise. What noise model does a yes-or-no answer have — and what loss comes out when you run the same derivation on it?

The method is older than all of these: Cauchy described it in a note to the Académie des Sciences in 1847, as a way of solving systems of equations by walking downhill on the sum of their squared residuals. Also worth reading alongside this chapter: Sebastian Ruder's An overview of gradient descent optimization algorithms (arXiv:1609.04747), which covers momentum through Adam in fourteen readable pages; chapter 3 of Nocedal and Wright's Numerical Optimization (2nd ed., Springer, 2006), whose theorem 3.3 gives the convergence rate of steepest descent on a quadratic in terms of the condition number — it is the theory behind why conditioning decides the step count, though it treats line search rather than the fixed-step $2/\lambda_{\max}$ ceiling measured above, or §5.8 and §7.1 of Deisenroth, Faisal and Ong's Mathematics for Machine Learning for the same ground with less machinery; §6.1 of Prince's Understanding Deep Learning and §4.3 of Goodfellow, Bengio and Courville's Deep Learning; Dive into Deep Learning §12.1–12.3, which has the minibatch analysis with more measurements than there is room for here; and chapter 4 of Géron's Hands-On Machine Learning (3rd ed.), the most practical treatment of the learning rate as a thing you tune rather than derive. The MIT 6.390 notes put gradient descent before classification, as this course does and for the same reason.