A First Taste of Algorithms · Learning as an Algorithm
Going downhill
So minimize L(w). And immediately, every tool in this book’s first act fails at once, for one reason: w is continuous. Try-everything is dead — there is no “everything”; between any two candidate slopes live infinitely many more. The table method is dead with it — Chapter 4’s notebook needs questions you can list, and a continuum cannot be listed. Six chapters of machinery, and the doorknob comes off in your hand.
What survives is local information. Stand at some w and ask Book 2’s question: what is the slope of L here — the derivative L′(w)? It points uphill; its size says how steep. You cannot see the whole landscape, but you can feel the ground under your feet — so take a small step downhill and ask again:
w ← w − η · L′(w)
— move against the slope, by a step proportional to steepness, scaled by a small number η (the learning rate, the size of your stride). Repeat. That is gradient descent, the algorithm under essentially all modern machine learning, and it fits in one line because it is one idea — and the idea has a name from Chapter 2. At every step, take the option that looks best from where you stand, commit, and never look back. Gradient descent is greedy, in continuous space, and you already know exactly what that means: sometimes provably perfect, sometimes confidently wrong, and the difference will be a property of the landscape.
Run it by hand first — three steps, the bowl f(x) = x², slope f′(x) = 2x, stride η = 0.25, starting at x₀ = 2:
- x₁ = 2 − 0.25·(4) = 1
- x₂ = 1 − 0.25·(2) = 0.5
- x₃ = 0.5 − 0.25·(1) = 0.25
Figure 8.2 — Three steps down the bowl: each stride is proportional to the slope, so the steps shrink as the floor flattens — the walk slows itself near the answer.
Halved, every step — and notice the built-in grace: nobody told the algorithm to slow down near the bottom, but the slope is smaller there, so the strides shrink on their own. The walk brakes automatically as it arrives. On this bowl that’s not a happy accident but an exact law: each step multiplies the position by (1 − 2η), and the Diamond has you turn that observation into the book’s first convergence proof — including the full strange taxonomy of strides: η = 0.5 lands exactly at the bottom in one step; η slightly under 1 converges while overshooting the bottom every single step, ringing like a struck bell; η = 1 bounces between 2 and −2 forever; η beyond 1 climbs out of the bowl, each step worse than the last. The learning rate is not a detail. It is the difference between arriving, ringing, and exploding, and in Lab 8 you will produce all three on purpose.
All 32 chapters of A First Taste of Algorithms · Foundations · All courses