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 , 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 and returns a guess at the
corresponding . 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.
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 better than another.
Choosing the loss, and why squared
Call the difference between what the model says and what actually happened the residual:
We need to collapse twelve residuals into one number. Adding them up is no good, because a miss of and a miss of 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.
- It is differentiable everywhere. has a corner at zero, and the whole method we are building runs on derivatives. This is a convenience, not a principle.
- It punishes outliers harder. One residual of contributes ; ten residuals of contribute 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.
- 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:
The half is pure bookkeeping. Differentiating a square brings a 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 , 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.
Notice what is a function of. Not of , and not of ; those are fixed the moment the data arrives and never change again. 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: is a sum of squares of expressions that are linear in , so expanded out it is a quadratic in and 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:
There is the half earning its keep: the from the square and the out front cancelled, and both partials are just averages of the residual, the second one weighted by .
Set both to zero. Multiply through by , expand, and collect the sums:
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 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.
The line the data was actually generated from was . Least squares recovered and 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 system, ten would give , and writing out the sums each time would become unbearable. So stack the data. Let be the design matrix whose -th row is the -th input, with a leading column of ones so that the intercept is just another weight, and let be the column of targets. Then the vector of all predictions is the single product , the vector of residuals is , and
The gradient of that, by the same differentiation compressed into vector notation, is
and setting it to zero gives the normal equations in the form you will meet everywhere else:
Check the shapes, because shape-checking is the cheapest debugging in all of machine learning. is , so is , is , and is . The two sums we computed by hand are literally the four entries of and the two entries of in the case . Nothing new has happened; the notation just stopped growing with .
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 takes work and solving with it takes . With that is nothing. With features, which is a modest text model, is and the matrix alone wants 800 megabytes. Gradient descent never forms at all: each step costs , 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. squares the condition number of .
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 is the vector of partial derivatives, and it points in the direction of steepest increase of . 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:
That is gradient descent, complete. One line. 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 ,
and if you set then that dot product becomes , 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.
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.
The learning rate is not a mystery
Every introduction says: if 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 , the matrix of second derivatives, is
and notice that it does not depend on at all: the curvature of a paraboloid is the same everywhere. Since is symmetric it has an orthonormal eigenbasis. Write the error in that basis. Because for a quadratic, one descent step does
which in the eigenbasis decouples completely: the component of the error along the eigenvector with eigenvalue is multiplied by every single step, independently of every other component.
That one factor explains everything you have ever been told about learning rates.
- If for every eigenvalue , every component shrinks geometrically and the method converges. That holds exactly when . This is the stability threshold, and for our data , so must stay below . Plate IV diverged at and converged at for precisely this reason.
- If is a little under , the factor is negative and close to : the error flips sign each step while barely shrinking. That is the visible oscillation at .
- The slowest component is the one with the smallest eigenvalue, since is the factor closest to . So the number of steps is governed by the ratio , the condition number. Our problem has , which is why forty steps suffice. Real problems have 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 enormously, and gradient descent notices.
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 . 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 up from small: watch the crawl become a stride, watch the path start to zigzag as approaches , then watch it leave the frame entirely. Then set back to something sensible and switch the optimizer to momentum: the same bowl, a visibly different route.
| x | -2.0 | -1.9 | -1.6 | -1.2 | -0.7 | -0.3 | 0.2 | 0.8 | 1.3 | 1.6 | 1.9 | 2.0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| y | -3.78 | -3.92 | -3.21 | -2.40 | -1.92 | -1.03 | -0.58 | 0.66 | 1.56 | 1.72 | 2.44 | 2.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.
w -= eta * g
Vanilla gradient descent: one step straight downhill.
v = beta * v + g w -= eta * v
Velocity carries past gradients, smoothing the path and coasting through shallow stretches; the β slider sets how much memory it keeps.
s = rho * s + (1 - rho) * g**2 w -= eta * g / (sqrt(s) + eps)
Each coordinate gets its own step, scaled down where gradients have been large; the ρ slider sets the averaging window.
m = b1*m + (1-b1)*g s = b2*s + (1-b2)*g**2 mh, sh = m/(1-b1**t), s/(1-b2**t) w -= eta * mh / (sqrt(sh) + eps)
Momentum and RMSProp combined, with bias-corrected moments; the β₁ and β₂ sliders set the two decay rates.
w -= eta * grad
The learning rate sets step length. Small eta crawls; past the stability threshold 2 / lambda_max it diverges.
g = (X.T @ (X @ w - y)) / n
Every step recomputes the gradient at the current weights, then hands it to the optimizer.
norm(grad) < tol
Stop when the surface is nearly flat underfoot; the tolerance slider sets how flat.
norm(w_new - w) < tol
Stop when the weights barely move between steps; the tolerance slider sets the threshold.
abs(L_new - L) < tol
Stop when the loss stops improving; the tolerance slider sets the threshold.
w = start.copy()
Where descent begins. Click the plane, or pick a preset.
Z = loss(W0, W1)
Lift every weight pair to its loss and the contours become a bowl the walk descends.
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:
Use the central difference, not the forward one. The forward difference has error ; the central difference has error , for the price of one extra function evaluation. At 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 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 to 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 is not a derivation, it is a hope.
What it costs
| Closed form | Gradient descent | |
|---|---|---|
| Time | , once | per step, times the number of steps |
| Space | for | for the weights and the gradient |
| Tuning | none | learning rate, stopping test, sometimes more |
| Answer | exact, to floating point | approximate, to whatever tolerance you set |
| Sensitive to feature scale | no | very |
| Survives a non-quadratic loss | no | yes |
| Survives having no closed form | no | yes |
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.
On paper, the half. We defined with a factor of . Suppose you had defined it with instead. Which of the following change, and which do not: the location of the minimiser , the value of the gradient at a given , the stability threshold on , and the number of steps descent takes at a fixed ? Justify each answer in one sentence. Then say what this tells you about comparing learning rates between two people’s code.
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 , 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 alone, is it still true? Say precisely which step of the argument you lose.
On paper, the threshold. For a single standardised feature (mean zero, variance one) together with an intercept column, compute explicitly. What are its two eigenvalues, what is the condition number, and what is the largest stable ? 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.
Check your own gradient. Write
numeric_gradient(w, data, eps), returning the central finite-difference estimate of the gradient, andmax_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 kbPlate 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 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
iinrange(len(w)), build two fresh copies ofwwithlist(w), addepsto entryiof one and subtractepsfrom entryiof the other, evaluatelosson both, and divide the difference by2 * eps. Collect the results in a list, in index order.Hint two
max_abs_diffis one line if you usemaxover a generator: the largest ofabs(x - y)asx, yrun overzip(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 loss evaluations, so it costs 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.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 belowtolin 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 kbPlate VIII The training loop, graded. Six checks: convergence to the closed-form optimum, early stopping, a step count that grows as shrinks, the loss matching 0.009901, the degenerate case burning the full budget without moving, and divergence past . 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 testreturn w, kimmediately. Otherwise build the newwand continue. Mind whether you are counting the step you did not take.Hint two
The
eta = 0check 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 allmax_stepstimes 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_stepsTesting before the step rather than after it is what makes the
eta = 0case return exactlymax_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.