Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture I of IV

Lecture I · Machine Learning

Linear Regression & Gradient Descent

Machine learning is not, at bottom, a subject about neural networks. It is a subject about fitting: you have some data, you have a family of functions, and you want the member of that family that misses the data by the least. Every lecture in this series is that same sentence with a different family of functions and a different definition of “misses”.

So we start with the smallest honest instance of the problem. The family is lines. The data is twelve points. And by the end of the lecture we will have solved it twice: once exactly, with algebra, and once approximately, by rolling downhill. The exact solution is the one you would actually use on twelve points. The approximate one is the one that still works when there are twelve million, and it is the reason the rest of the field exists.

The problem, stated plainly

Here is the data: twelve pairs (xi,yi)(x_i, y_i), which for the sake of having something to picture you may call twelve readings of some instrument.

We want a line, a rule that takes an xx and returns a guess at the corresponding yy. A line has two numbers in it, an intercept and a slope, and we will carry them together in a list w = [w0, w1] and call them the weights, because that is what the rest of the field calls them.

y^=w0+w1x.\hat{y} = w_0 + w_1 x.

That is the model. It is the entire model. The interesting question is not what the model is; it is what makes one choice of ww better than another.

Choosing the loss, and why squared

Call the difference between what the model says and what actually happened the residual:

ri=y^i−yi=w0+w1xi−yi.r_i = \hat{y}_i - y_i = w_0 + w_1 x_i - y_i.

We need to collapse twelve residuals into one number. Adding them up is no good, because a miss of +5+5 and a miss of −5-5 would cancel and report a perfect fit. So the residuals have to be made non-negative first, and there are two obvious ways to do that: take absolute values, or square.

Squaring wins, for three reasons, and it is worth being clear that only the third is a real one.

  1. It is differentiable everywhere. ∣r∣|r| has a corner at zero, and the whole method we are building runs on derivatives. This is a convenience, not a principle.
  2. It punishes outliers harder. One residual of 1010 contributes 100100; ten residuals of 11 contribute 1010 between them. Whether that is a feature or a bug depends entirely on your data, and if the data has genuine outliers it is a bug. Absolute error is the more robust choice and does get used when robustness matters.
  3. It has a closed-form solution and a probabilistic justification. Squared error is the negative log-likelihood of the data under the assumption that the noise is Gaussian with constant variance. If you believe that assumption, least squares is not a heuristic; it is the maximum-likelihood estimate. That is the real argument, and a later lecture returns to it when the assumption stops holding.

So the loss is the mean of the squared residuals, and we will carry a factor of one half in front:

L(w)=12n∑i=1n(w0+w1xi−yi)2.L(w) = \frac{1}{2n} \sum_{i=1}^{n} (w_0 + w_1 x_i - y_i)^2.

The half is pure bookkeeping. Differentiating a square brings a 22 down in front, and the half is there to cancel it, so that the gradient comes out clean. It changes where the minimum sits not at all: scaling a function by a positive constant moves nothing about the location of its minimum.

Run the loss on four candidate lines and read the residual table under it. The last block prints, for the candidate w=[0,1]w = [0, 1], each point’s prediction, its residual, and the square that goes into the sum. This is the only figure in the lecture where you can see the loss as the pile of small numbers that it is.

python runs in your browser · first run downloads ~240 kb
Plate I The loss, evaluated. Four candidate lines against the twelve-point training set, then the residual table for one of them. Notice that w=[−0.7,1.6]w = [-0.7, 1.6], very nearly the line the data was generated from, scores about 0.0101, while w=[−3,3]w = [-3, 3] scores about four hundred and sixty times worse. Edit the candidate list and re-run: the loss is a function you can probe by hand long before you differentiate it.

Notice what LL is a function of. Not of xx, and not of yy; those are fixed the moment the data arrives and never change again. LL is a function of the two weights, and only of them. It is a surface over a two-dimensional plane, and everything that follows is about finding the lowest point of that surface.

Solving it exactly

The surface is a paraboloid, and that claim is strong enough to be worth justifying: LL is a sum of squares of expressions that are linear in ww, so expanded out it is a quadratic in w0w_0 and w1w_1 whose quadratic part is positive definite. A quadratic with positive-definite curvature is a bowl. A bowl has exactly one bottom, and at the bottom both partial derivatives are zero.

So take them. Differentiating the sum term by term, and using the chain rule on each square:

∂L∂w0=1n∑i=1n(w0+w1xi−yi),∂L∂w1=1n∑i=1n(w0+w1xi−yi) xi.\frac{\partial L}{\partial w_0} = \frac{1}{n} \sum_{i=1}^{n} (w_0 + w_1 x_i - y_i), \qquad \frac{\partial L}{\partial w_1} = \frac{1}{n} \sum_{i=1}^{n} (w_0 + w_1 x_i - y_i)\, x_i.

There is the half earning its keep: the 22 from the square and the 12\tfrac12 out front cancelled, and both partials are just averages of the residual, the second one weighted by xx.

Set both to zero. Multiply through by nn, expand, and collect the sums:

n w0+(∑ixi)w1=∑iyi,(∑ixi)w0+(∑ixi2)w1=∑ixiyi.\begin{aligned} n\, w_0 + \Big(\textstyle\sum_i x_i\Big) w_1 &= \textstyle\sum_i y_i, \\[2pt] \Big(\textstyle\sum_i x_i\Big) w_0 + \Big(\textstyle\sum_i x_i^2\Big) w_1 &= \textstyle\sum_i x_i y_i. \end{aligned}

These are the normal equations. They are two linear equations in two unknowns, and every coefficient is a sum you can accumulate in one pass over the data. Solve the 2×22 \times 2 system and you are done, exactly, with no iteration, no learning rate, and no tuning of anything.

The plate below does exactly that, then checks its own answer by nudging each weight in both directions and confirming that the loss goes up every time.

python runs in your browser · first run downloads ~240 kb
Plate II Least squares in closed form. Four running sums, a 2×22 \times 2 solve, and the exact minimiser w∗=[−0.681628, 1.595356]w^* = [-0.681628,\ 1.595356] with L(w∗)=0.009901L(w^*) = 0.009901. The nudge table underneath is the numerical reading of "both partials are zero": every perturbation of ±0.05\pm 0.05 in either weight raises the loss, which is what sitting at the bottom of a bowl means.

The line the data was actually generated from was y=1.6x−0.7y = 1.6x - 0.7. Least squares recovered 1.59541.5954 and −0.6816-0.6816 from twelve noisy points. That gap is not error in the method; it is the noise, and no method could have done better on this data, because these particular noisy points genuinely are better explained by the slightly different line.

The same thing, in matrices

Two features would give a 3×33 \times 3 system, ten would give 11×1111 \times 11, and writing out the sums each time would become unbearable. So stack the data. Let XX be the n×dn \times d design matrix whose ii-th row is the ii-th input, with a leading column of ones so that the intercept is just another weight, and let yy be the column of targets. Then the vector of all nn predictions is the single product XwXw, the vector of residuals is Xw−yXw - y, and

L(w)=12n∥Xw−y∥2.L(w) = \frac{1}{2n} \lVert Xw - y \rVert^2 .

The gradient of that, by the same differentiation compressed into vector notation, is

∇L(w)=1nXT(Xw−y),\nabla L(w) = \frac{1}{n} X^{\mathsf T}(Xw - y),

and setting it to zero gives the normal equations in the form you will meet everywhere else:

XTX w=XTy⟹w∗=(XTX)−1XTy.X^{\mathsf T} X\, w = X^{\mathsf T} y \qquad\Longrightarrow\qquad w^* = (X^{\mathsf T} X)^{-1} X^{\mathsf T} y .

Check the shapes, because shape-checking is the cheapest debugging in all of machine learning. XX is n×dn \times d, so XTXX^{\mathsf T}X is d×dd \times d, XTyX^{\mathsf T}y is d×1d \times 1, and ww is d×1d \times 1. The two sums we computed by hand are literally the four entries of XTXX^{\mathsf T}X and the two entries of XTyX^{\mathsf T}y in the case d=2d = 2. Nothing new has happened; the notation just stopped growing with dd.

So why gradient descent at all?

We have an exact answer in closed form. It is tempting to stop here. Three things stop us.

Cost. Forming XTXX^{\mathsf T}X takes O(nd2)O(nd^2) work and solving with it takes O(d3)O(d^3). With d=2d = 2 that is nothing. With d=10,000d = 10{,}000 features, which is a modest text model, d3d^3 is 101210^{12} and the matrix alone wants 800 megabytes. Gradient descent never forms XTXX^{\mathsf T}X at all: each step costs O(nd)O(nd), and if you are willing to use a subset of the rows per step (the stochastic variant, the subject of a later lecture) it costs rather less than that.

Conditioning. (XTX)−1(X^{\mathsf T}X)^{-1} squares the condition number of XX. If the features are nearly collinear, that inverse is numerically dangerous in a way the iterative method simply is not. Nobody actually calls a matrix inverse in production code, incidentally; you solve the system with a QR or Cholesky factorisation, which is better conditioned and faster. Writing inv(X.T @ X) @ X.T @ y in real work is a small tell.

Generality. This is the real reason. The closed form exists because the loss is quadratic and the model is linear. Change either one and it evaporates. Logistic regression has no closed form. A neural network has no closed form. There is no algebraic expression for the weights of a transformer. Gradient descent does not care: it needs a loss you can differentiate, and nothing else.

So we are about to solve, by a slow approximate method, a problem we can already solve exactly. That is on purpose. This is the only setting in the whole series where we can grade the iterative answer against the truth to six decimal places, and we should use it while we have it.

Rolling downhill

The gradient ∇L(w)\nabla L(w) is the vector of partial derivatives, and it points in the direction of steepest increase of LL. That last word is the one students drop, and dropping it is how you end up with a sign error that trains your model to be as wrong as it can manage. To go down, step against it:

w←w−η ∇L(w).w \leftarrow w - \eta \, \nabla L(w).

That is gradient descent, complete. One line. η\eta is the learning rate, a positive number you choose, and choosing it is most of the practical difficulty of the method.

Why does this work? Because the gradient is the best linear model of the surface near where you are standing. For a small step Δw\Delta w,

L(w+Δw)≈L(w)+∇L(w)⋅Δw,L(w + \Delta w) \approx L(w) + \nabla L(w) \cdot \Delta w,

and if you set Δw=−η∇L(w)\Delta w = -\eta \nabla L(w) then that dot product becomes −η∥∇L(w)∥2-\eta \lVert \nabla L(w)\rVert^2, which is negative whenever the gradient is not zero. So a sufficiently small step is guaranteed to reduce the loss. The word “sufficiently” is carrying a great deal, and we are about to make it precise.

The plate below computes the gradient at the origin and then does the sign check by brute force: it takes one step with the gradient and one step against it, and prints both losses. Stepping with the gradient makes things worse. That is not a proof, but it is the check you should run the first time you write a gradient in any new setting.

python runs in your browser · first run downloads ~240 kb
Plate III The gradient, and its sign. At w=[0,0]w = [0, 0] the gradient is [0.6683,−3.2821][0.6683, -3.2821]: the loss falls fastest if we decrease the intercept slightly and increase the slope a great deal, which is right, since the origin is a flat line through zero and the data slopes upward. The last two lines take one step each way with η=0.3\eta = 0.3; against the gradient the loss drops from 2.856 to about 0.508, with it the loss climbs to about 7.24.

The whole algorithm

Wrap the update in a loop and you have the training procedure that, in one form or another, is running on every GPU cluster on earth.

def descend(data, eta, steps):
    w = [0.0, 0.0]
    for _ in range(steps):
        g = gradient(w, data)
        w = [w[0] - eta * g[0], w[1] - eta * g[1]]
    return w

Four lines. Initialise, differentiate, step, repeat. Nearly everything the field has added since is a modification of the third line (momentum, RMSProp, Adam), of the second line (backpropagation, automatic differentiation), or of the choice of which rows go into data on each pass (minibatching).

Now run it at four learning rates and watch what changes.

python runs in your browser · first run downloads ~240 kb
Plate IV Four learning rates, forty steps each, against a closed form we already know. At η=0.03\eta = 0.03 the walk is still visibly short of the optimum after forty steps. At η=0.3\eta = 0.3 it is correct to six decimals well before step forty. At η=0.9\eta = 0.9, just under the stability threshold, it converges but visibly oscillates on the way: the intercept settles almost immediately while the slope swings from 2.95 to 0.43 to 2.59 before it starts closing in. At η=1.05\eta = 1.05, just over the threshold, the slope swings the same way but wider every time, and by step forty it is at −688-688 with a loss near half a million. The threshold is not a rule of thumb; it is 2/λmax⁡≈0.97052/\lambda_{\max} \approx 0.9705, derived below.

The learning rate is not a mystery

Every introduction says: if η\eta is too small, convergence is slow; if it is too large, the method diverges; tune it. That is true, and for a general loss it is about as much as anyone can say. But our loss is quadratic, and for a quadratic the threshold is exactly computable, so we should compute it rather than gesture at it.

The Hessian of LL, the matrix of second derivatives, is

H=∇2L(w)=1nXTX,H = \nabla^2 L(w) = \frac{1}{n} X^{\mathsf T} X,

and notice that it does not depend on ww at all: the curvature of a paraboloid is the same everywhere. Since HH is symmetric it has an orthonormal eigenbasis. Write the error e=w−w∗e = w - w^* in that basis. Because ∇L(w)=H(w−w∗)\nabla L(w) = H(w - w^*) for a quadratic, one descent step does

e←e−ηHe=(I−ηH) e,e \leftarrow e - \eta H e = (I - \eta H)\,e,

which in the eigenbasis decouples completely: the component of the error along the eigenvector with eigenvalue λ\lambda is multiplied by (1−ηλ)(1 - \eta\lambda) every single step, independently of every other component.

That one factor explains everything you have ever been told about learning rates.

  • If ∣1−ηλ∣<1|1 - \eta\lambda| < 1 for every eigenvalue λ\lambda, every component shrinks geometrically and the method converges. That holds exactly when 0<η<2/λmax⁡0 < \eta < 2/\lambda_{\max}. This is the stability threshold, and for our data λmax⁡=2.0609\lambda_{\max} = 2.0609, so η\eta must stay below 0.97050.9705. Plate IV diverged at 1.051.05 and converged at 0.90.9 for precisely this reason.
  • If ηλ\eta\lambda is a little under 22, the factor (1−ηλ)(1 - \eta\lambda) is negative and close to −1-1: the error flips sign each step while barely shrinking. That is the visible oscillation at η=0.9\eta = 0.9.
  • The slowest component is the one with the smallest eigenvalue, since (1−ηλmin⁡)(1 - \eta \lambda_{\min}) is the factor closest to 11. So the number of steps is governed by the ratio κ=λmax⁡/λmin⁡\kappa = \lambda_{\max} / \lambda_{\min}, the condition number. Our problem has κ=2.06\kappa = 2.06, which is why forty steps suffice. Real problems have κ\kappa in the thousands, and then gradient descent crawls along a narrow valley, forced to take tiny steps in the direction it needs to travel furthest.

That last bullet is the entire motivation for momentum, for RMSProp, and for Adam. They are not tricks; they are attempts to stop the condition number from dictating the step count. The plate further down puts all four optimizers on the same bowl so you can watch them negotiate it differently.

Conditioning, and the cheapest fix in machine learning

The condition number is a property of your features, not of your algorithm, and it is trivially easy to wreck. Multiply one feature by a thousand, say by recording a length in millimetres instead of metres, and you have not changed the problem in any meaningful sense; the closed-form solution just comes back with that weight divided by a thousand. But you have changed XTXX^{\mathsf T} X enormously, and gradient descent notices.

python runs in your browser · first run downloads ~240 kb
Plate V What a change of units does to a solver. The same twelve points with xx in three different scalings: rescaling xx by a thousand multiplies λmax⁡\lambda_{\max} by about a million, drives the condition number from 2.1 to over two million, and drops the largest safe learning rate from about 0.97 to about 10−610^{-6}. Standardising the feature (subtract the mean, divide by the standard deviation) puts it back, and better than back: the condition number falls to almost exactly 1. Nothing about the underlying fit changed in any of the three cases, only the solver's difficulty.

Hence the advice you will hear everywhere: standardise your features. Subtract the mean, divide by the standard deviation, and every feature arrives at the optimiser on the same footing. It is one line of preprocessing and it routinely does more for convergence than any amount of fiddling with η\eta. It is also why a closed-form solver is untroubled by any of this: solving the system exactly does not care about curvature ratios, only about the matrix being invertible.

The plate: a surface you can walk

Everything above is one picture. The loss is a bowl over the plane of weights, gradient descent is a walk down it, and the learning rate decides whether the walk is a crawl, a stride, or a fall off the side.

The plate below is that picture, live. The left panel is weight space: contour rings of the loss, the ochre cross at the closed-form optimum we computed in Plate II, and the path your chosen optimizer takes drawn on top. The 3D toggle lifts the contours into the surface itself. The right panel is the same twelve points with the current fit line, so you can watch the line swing into place as the walk proceeds. Every control carries an explainer: hover it, or focus it by keyboard, and the exact update rule and the line of Python it corresponds to appear underneath.

Push on it in this order. Set the optimizer to plain SGD and the start to the origin, then move η\eta up from small: watch the crawl become a stride, watch the path start to zigzag as η\eta approaches 0.970.97, then watch it leave the frame entirely. Then set η\eta back to something sensible and switch the optimizer to momentum: the same bowl, a visibly different route.

The twelve (x, y) training points fitted by this figure.
x -2.0-1.9-1.6-1.2-0.7-0.30.20.81.31.61.92.0
y -3.78-3.92-3.21-2.40-1.92-1.03-0.580.661.561.722.442.44

With JavaScript enabled this plate runs four optimizers (SGD, momentum, RMSProp, Adam) live on the loss surface. On the data above, the normal equations give the exact optimum w₀* = -0.68, w₁* = 1.60; the point every convergent descent walks toward.

Optimizer
Start
Stop when
Run
View
Weight space (w₀, w₁)
Data · current fit ŷ = w₀ + w₁x
Reading the update

Plate VI Gradient descent on the linear-regression loss surface. Pick an optimizer (SGD, momentum, RMSProp, Adam), a starting point, a learning rate, and a stopping test, then Step or Run. The ochre cross is w∗=[−0.681628, 1.595356]w^* = [-0.681628,\ 1.595356], the exact answer from the normal equations in Plate II; every optimizer is trying to reach it, and the interesting question is how many steps each one spends doing so. The 3D toggle lifts the contours into the loss surface and can be dragged to rotate; its height slider exaggerates the drawn surface only and never touches a loss value or a weight, so the walk you watch is exactly the walk the arithmetic takes. Reduced motion jumps to the final state instead of animating.

Checking that the gradient is real

Here is the discipline that matters more than anything else in this lecture, and it is the rule the pyml repository is built around: every analytic gradient is checked against finite differences, entry by entry, in the test suite.

The reason is that a wrong gradient does not usually crash. It trains. It produces a loss curve that goes down, slowly, to somewhere that is not the minimum, and you spend a week tuning learning rates on a model whose derivative has a transposed matrix in it. Meanwhile the check is four lines and runs in milliseconds:

∂L∂wi≈L(w+εei)−L(w−εei)2ε.\frac{\partial L}{\partial w_i} \approx \frac{L(w + \varepsilon e_i) - L(w - \varepsilon e_i)}{2\varepsilon}.

Use the central difference, not the forward one. The forward difference (L(w+ε)−L(w))/ε(L(w + \varepsilon) - L(w))/\varepsilon has error O(ε)O(\varepsilon); the central difference has error O(ε2)O(\varepsilon^2), for the price of one extra function evaluation. At ε=10−5\varepsilon = 10^{-5} that is the difference between agreeing to five digits and agreeing to ten.

There is a floor, though, and it is worth knowing why. Too large an ε\varepsilon and the cubic term of the Taylor expansion pollutes the estimate; too small and you are subtracting two nearly equal floating-point numbers, and the cancellation eats your significant digits. Somewhere around 10−510^{-5} to 10−710^{-7} in double precision is the sweet spot, and the fact that there is a sweet spot is the best argument for deriving gradients analytically rather than estimating them. A derivation that cannot survive (L(w+ε)−L(w−ε))/2ε(L(w+\varepsilon) - L(w-\varepsilon))/2\varepsilon is not a derivation, it is a hope.

What it costs

Closed formGradient descent
TimeO(nd2+d3)O(nd^2 + d^3), onceO(nd)O(nd) per step, times the number of steps
SpaceO(d2)O(d^2) for XTXX^{\mathsf T}XO(d)O(d) for the weights and the gradient
Tuningnonelearning rate, stopping test, sometimes more
Answerexact, to floating pointapproximate, to whatever tolerance you set
Sensitive to feature scalenovery
Survives a non-quadratic lossnoyes
Survives having no closed formnoyes

Read those last two rows as the summary of the whole lecture. For this problem the closed form wins on every line that matters, and you should use it. We built the iterative method anyway, on a problem where it could be graded against the truth, because it is the method that survives contact with every other problem in the series.

What comes next

The model was linear and the loss was quadratic, and that combination is exactly what made the closed form exist. Lecture II keeps gradient descent and breaks the model: a small neural network, a nonlinearity between the layers, and a gradient that has to be assembled by the chain rule running backwards through the computation. The loss stops being a bowl and the optimum stops being unique. Every single thing in this lecture (the sign of the step, the stability threshold, the finite-difference check) carries over unchanged.

Problems

Work these in order. The last two run their own checks; make every row green.

  1. On paper, the half. We defined LL with a factor of 12n\tfrac{1}{2n}. Suppose you had defined it with 1n\tfrac{1}{n} instead. Which of the following change, and which do not: the location of the minimiser w∗w^*, the value of the gradient at a given ww, the stability threshold on η\eta, and the number of steps descent takes at a fixed η\eta? Justify each answer in one sentence. Then say what this tells you about comparing learning rates between two people’s code.

  2. On paper, the intercept. Show that at the least-squares optimum the residuals sum to exactly zero, and therefore that the fitted line passes through (xˉ,yˉ)(\bar{x}, \bar{y}), the centroid of the data. One of the two partial derivatives gives you the whole result. Then the follow-up: if you drop the intercept and fit y^=w1x\hat{y} = w_1 x alone, is it still true? Say precisely which step of the argument you lose.

  3. On paper, the threshold. For a single standardised feature (mean zero, variance one) together with an intercept column, compute H=1nXTXH = \tfrac{1}{n}X^{\mathsf T}X explicitly. What are its two eigenvalues, what is the condition number, and what is the largest stable η\eta? You should get a suspiciously round set of answers, and the roundness is the point: standardising a single feature makes this problem perfectly conditioned. Check your answer against the third row of Plate V.

  4. Check your own gradient. Write numeric_gradient(w, data, eps), returning the central finite-difference estimate of the gradient, and max_abs_diff(a, b), returning the largest absolute difference between two equal-length lists. Two things to be careful about: nudge one coordinate at a time, and never mutate the caller’s list, because a check that silently corrupts the weights it was auditing is worse than no check at all. The later checks confirm that your comparison actually catches a wrong gradient, which is the only property that makes it worth running.

    The checks · run against your code

    # the numeric gradient matches the analytic one at the origin
    g = gradient([0.0, 0.0], DATA)
    ng = numeric_gradient([0.0, 0.0], DATA)
    assert max_abs_diff(g, ng) < 1e-6
    # and at an off-centre point
    g = gradient([1.5, -0.5], DATA)
    ng = numeric_gradient([1.5, -0.5], DATA)
    assert max_abs_diff(g, ng) < 1e-6
    # the check does not mutate the weights it is handed
    w = [0.3, 0.4]
    numeric_gradient(w, DATA)
    assert w == [0.3, 0.4]
    # at the optimum both gradients are essentially zero
    opt = [-0.681628, 1.595356]
    assert max_abs_diff(gradient(opt, DATA), [0.0, 0.0]) < 1e-5
    assert max_abs_diff(numeric_gradient(opt, DATA), [0.0, 0.0]) < 1e-5
    # a WRONG gradient is caught: drop the 1/n and the check fails loudly
    def bad_gradient(w, data):
        g0 = g1 = 0.0
        for x, y in data:
            r = w[0] + w[1] * x - y
            g0 += r
            g1 += r * x
        return [g0, g1]
    assert max_abs_diff(bad_gradient([0.0, 0.0], DATA), numeric_gradient([0.0, 0.0], DATA)) > 1.0
    # the comparison itself is sane: zero on identical lists, and symmetric
    assert max_abs_diff([1.0, 2.0], [1.0, 2.0]) == 0.0
    assert max_abs_diff([1.0, 5.0], [1.5, 2.0]) == max_abs_diff([1.5, 2.0], [1.0, 5.0])
    python runs in your browser · first run downloads ~240 kb
    Plate VII The audit, as a test. Eight checks: agreement at two different points, no mutation of the input, both gradients vanishing at the optimum, a deliberately broken gradient (the 1/n1/n dropped) getting caught, and two sanity properties of the comparison itself. If the "caught" row fails, your comparison is too forgiving to be worth running.
    Hint one

    For each index i in range(len(w)), build two fresh copies of w with list(w), add eps to entry i of one and subtract eps from entry i of the other, evaluate loss on both, and divide the difference by 2 * eps. Collect the results in a list, in index order.

    Hint two

    max_abs_diff is one line if you use max over a generator: the largest of abs(x - y) as x, y run over zip(a, b).

    The solution

    Two nudges per coordinate, and a copy each time:

    def numeric_gradient(w, data, eps=1e-5):
      out = []
      for i in range(len(w)):
          hi = list(w)
          lo = list(w)
          hi[i] += eps
          lo[i] -= eps
          out.append((loss(hi, data) - loss(lo, data)) / (2 * eps))
      return out
    
    def max_abs_diff(a, b):
      return max(abs(x - y) for x, y in zip(a, b))

    The two list(w) calls are the whole of “do not mutate the caller’s list”, and they are cheap. The routine runs 2d2d loss evaluations, so it costs O(nd2)O(nd^2) overall and is strictly a debugging tool, never a training one. Note that it needs nothing whatever from your derivation. That independence is exactly what makes it a check: it can catch an error that your algebra and your code are making in agreement with each other.

  5. Descent with a stopping test. Write descend(data, eta, max_steps, tol), which starts at [0.0, 0.0], steps against the gradient, and stops early when both components of the gradient are below tol in absolute value. Return the pair (w, steps_taken). The checks pin the answer against the closed form from Plate II, confirm that a smaller learning rate takes strictly more steps to reach the same place, and confirm that a rate past the stability threshold blows up rather than quietly returning nonsense.

    The checks · run against your code

    # a sane learning rate finds the closed-form optimum
    w, k = descend(DATA, 0.3)
    assert abs(w[0] - (-0.681628)) < 1e-4
    assert abs(w[1] - 1.595356) < 1e-4
    # it stops early rather than burning all 5000 steps
    assert k < 5000
    # a smaller rate reaches the same place, but takes strictly longer
    w2, k2 = descend(DATA, 0.05)
    assert abs(w2[0] - (-0.681628)) < 1e-4
    assert k2 > k
    # the loss at the answer matches the closed form
    assert abs(loss(w, DATA) - 0.009901) < 1e-5
    # eta = 0 never moves, and burns the whole budget
    w3, k3 = descend(DATA, 0.0, max_steps=50)
    assert w3 == [0.0, 0.0]
    assert k3 == 50
    # a rate past the stability threshold 2/lambda_max = 0.9705 blows up
    w4, k4 = descend(DATA, 1.2, max_steps=200)
    assert abs(w4[0]) > 1e3 or abs(w4[1]) > 1e3
    python runs in your browser · first run downloads ~240 kb
    Plate VIII The training loop, graded. Six checks: convergence to the closed-form optimum, early stopping, a step count that grows as η\eta shrinks, the loss matching 0.009901, the degenerate case η=0\eta = 0 burning the full budget without moving, and divergence past 2/λmax⁡2/\lambda_{\max}. That last one is the interesting check: it asserts that a bad learning rate fails loudly, and a solver that fails quietly is the one that costs you a week.
    Hint one

    The loop body is three lines: compute the gradient, test it against tol, and if it passes the test return w, k immediately. Otherwise build the new w and continue. Mind whether you are counting the step you did not take.

    Hint two

    The eta = 0 check is what catches an off-by-one: with a zero learning rate the weights never move, the gradient never shrinks, and the loop must run all max_steps times and return that number exactly.

    The solution

    The four-line loop, with the flat-ground test in front of the step:

    def descend(data, eta, max_steps=5000, tol=1e-9):
      w = [0.0, 0.0]
      for k in range(max_steps):
          g = gradient(w, data)
          if abs(g[0]) < tol and abs(g[1]) < tol:
              return w, k
          w = [w[0] - eta * g[0], w[1] - eta * g[1]]
      return w, max_steps

    Testing before the step rather than after it is what makes the eta = 0 case return exactly max_steps, and it is the more honest order in general: the test asks “am I already done?”, which is a question about where you are standing, not about where you are going. Note that this stopping test is on the gradient, not on the change in loss. Both are defensible; the gradient test is sensitive to the scale of the targets, the loss-delta test can trigger on a plateau that is not a minimum, and Plate VI lets you switch between them and watch them disagree.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.