Gradient descent: learning by walking downhill

Derive the gradient descent update from the tangent line, prove exactly which learning rates converge on a parabola, and watch it train a line on real data.

23 min·Early college·Updated October 2026

AssumesWhat "learning" means: fitting a line to data What is a derivative? Speed at a single instant The gradient: which way is uphill?

Gradient descent training a line on four house prices: 200 steps at learning rate 0.1, starting from the flat line $\hat y = 3$. On the right, the same run as a path over the loss map: a few zigzags across the valley, then a long slide along its floor to the lowest point.

Monocurl source

let fd = DataFrame([-2.05, 0.1, 0], 2.7, 2.8)
let fm = MapFrame([2.05, 0.05, 0])
let PATH = descend(HX, [0, 3], 0.1, 200)
let Run = |u| {
    let p = spot(PATH, u)
    return [
        LineOn(fd, p[0], p[1]),
        Houses(fd),
        Walk(fm, PATH, u),
        center{[-1.0, 1.95, 0]} scale{1.1} color{INK} Number(floor(u + 0.0001), 0),
        center{[0.1, 1.95, 0]} scale{1.1} color{ROSE} Number(loss(p[0], p[1]), 2)
    ]
}
mesh plots = [DataPlot(fd), LossMap(fm)]
mesh names = [
    center{[-1.6, 1.95, 0]} Cap("step", 0.76, INK),
    center{[-0.45, 1.95, 0]} Cap("loss", 0.76, ROSE)
]
mesh run = Run(u: 0)

slide "descend"
    play Wait(0.8)
    run.u = 200
    play Lerp(9, [&run], |t| t ^ 2.6)
    play Wait(1.6)

Uses the shared definitions for this lesson's figures.

You are standing on a hillside in fog so thick that you cannot see your own feet. You want to reach the valley floor. What do you do?

Almost everyone gives the same answer: feel which way the ground slopes under your boots, take a step downhill, and repeat. It uses no map and no plan, only the slope at the one point where you stand. Yet it is how nearly every machine learning model is trained, including ones with billions of adjustable numbers. It also has a trap that the hillside story hides: take your steps a little too long, and each one carries you higher than the last, however carefully you measured the slope.

The problem: a surface with no formula for its bottom

In the previous lesson we fitted a line $\hat y = wx + b$ to four house sales. The model has two parameters, the slope $w$ and the intercept $b$. Its loss, the mean of the squared errors, is a function of those two numbers,

$$ L(w, b) = 7.5w^2 + 5wb + b^2 - 20.5w - 7b + 14.25, $$

and training meant finding the $(w, b)$ where $L$ is smallest. Algebra found it: the loss surface is a bowl whose lowest point is at $w = 1.2$, $b = 0.5$, where $L = 0.2$.

The algebra worked because $L$ is quadratic. For the models of the coming lessons it is not, and no formula gives the lowest point. What we can still do, for any loss built from differentiable pieces, is evaluate two things at whatever parameters we currently hold: the loss, and its slope. That is the walker in the fog. We will turn “step downhill” into a precise rule, find out exactly when it works on a case simple enough to solve completely, and then run it on the house data, where we know the answer it should reach.

One dial: stepping down a parabola

Start with one parameter and the simplest bowl there is, $f(w) = w^2$, whose lowest point is at $w = 0$. Suppose we are at $w = 2$. The derivative $f'(w) = 2w$ is the slope of the graph, and $f'(2) = 4$ is positive: the curve rises to the right, so downhill is to the left.

How far should we step? A reasonable first rule: in proportion to the slope. Where the curve is steep we are probably far from the bottom and can afford a long step; where it is nearly flat we should tread carefully. Pick a positive number $\eta$ (the Greek letter eta) to set the proportion, and move from $w$ to $w - \eta f'(w)$.

Try $\eta = 0.1$. From $w = 2$ the slope is 4, so we move to $2 - 0.1 \times 4 = 1.6$. There the slope is $3.2$, so we move to $1.6 - 0.32 = 1.28$, then to $1.28 - 0.256 = 1.024$. The steps shrink as the slope does, and $w$ creeps toward 0.

Pause and try

Run the same rule from $w = 2$ with $\eta = 0.4$ for three steps. Then look at your numbers and at $2, 1.6, 1.28, 1.024$: in each run, what is the ratio of each $w$ to the one before?

Show answerHide answer

With $\eta = 0.4$: $2 - 0.4 \times 4 = 0.4$, then $0.4 - 0.4 \times 0.8 = 0.08$, then $0.016$. Each value is $0.2$ times the previous one; in the first run the ratio was $0.8$. The larger $\eta$ gets to the bottom much faster.

So a bigger $\eta$ is better? Push it and see.

Pause and try

Run three steps from $w = 2$ with $\eta = 0.9$, and three more with $\eta = 1.1$. What is different about the two?

Show answerHide answer

With $\eta = 0.9$: $2 - 0.9 \times 4 = -1.6$, then $-1.6 + 0.9 \times 3.2 = 1.28$, then $1.28 - 0.9 \times 2.56 = -1.024$. The step jumps clear over the bottom and lands on the opposite wall, but lower than where it started: each value is $-0.8$ times the last. With $\eta = 1.1$: $2 - 4.4 = -2.4$, then $-2.4 + 1.1 \times 4.8 = 2.88$, then $2.88 - 1.1 \times 5.76 = -3.456$. Each landing is higher than the take-off: the ratio is $-1.2$.

Learning rate 0.1: the walker creeps down one side.
Learning rate 0.4: three steps and it is nearly at the bottom.
Learning rate 0.9: it jumps over the bottom every time, but lands lower.
Learning rate 1.1: every hop lands higher, and the walker leaves the plot.

Gradient descent on $f(w) = w^2$ from $w = 2$ at four learning rates. Each hop goes from one value of $w$ to the next, and the column on the right lists the values.

Monocurl source

let f1 = Frame(-3.2, 3.2, 0, 10.5, [-0.95, 0.15, 0], 4.9, 3.0)
let RATES = [0.1, 0.4, 0.9, 1.1]
let RUNS = map(RATES, |e| iterate(|w| 2 * w, 2, e, 6))
let on_curve = |ws| map(ws, |w| [w, sq(w)])
let Hop = |ws, u, col| Walk(f1, on_curve(ws), u, col)
let Side = |i, col| [
    center{[2.75, 1.75, 0]} Math(str_join(["\eta = ", to_string(RATES[i], 1)]), 0.95, col),
    center{[2.75, 1.25, 0]} Note("values of w", 0.72),
    map(range(0, 6), |k| center{[2.75, 0.82 - 0.4 * k, 0]} Math(to_string(RUNS[i][k], 3), 0.76, INK)),
    center{[2.75, -1.75, 0]} Math(str_join(["\times\,", to_string(1 - 2 * RATES[i], 1), "\text{ each step}"]), 0.8, col)
]
mesh plot = PlotFrame(f1, [-3, -2, -1, 0, 1, 2, 3], [2, 4, 6, 8, 10], "parameter w", "f(w) = w²")
mesh curve = Graph(f1, sq, -3.2, 3.2, AZURE, 4)
mesh hop = []
mesh side = []

slide "Learning rate 0.1: the walker creeps down one side."
    hop = Hop(RUNS[0], u: 0, EMBER)
    side = Side(0, EMBER)
    play Fade(0.5)
    hop.u = 6
    play Lerp(3, [&hop], linear)

slide "Learning rate 0.4: three steps and it is nearly at the bottom."
    hop = []
    side = []
    play Fade(0.3)
    hop = Hop(RUNS[1], u: 0, LEAF)
    side = Side(1, LEAF)
    play Fade(0.4)
    hop.u = 6
    play Lerp(3, [&hop], linear)

slide "Learning rate 0.9: it jumps over the bottom every time, but lands lower."
    hop = []
    side = []
    play Fade(0.3)
    hop = Hop(RUNS[2], u: 0, PLUM)
    side = Side(2, PLUM)
    play Fade(0.4)
    hop.u = 6
    play Lerp(3.5, [&hop], linear)

slide "Learning rate 1.1: every hop lands higher, and the walker leaves the plot."
    hop = []
    side = []
    play Fade(0.3)
    hop = Hop(RUNS[3], u: 0, ROSE)
    side = Side(3, ROSE)
    play Fade(0.4)
    hop.u = 3
    play Lerp(3, [&hop], linear)

Uses the shared definitions for this lesson's figures.

Three questions come out of this experiment. Why step in proportion to the slope at all? Why does a downhill rule sometimes go uphill? And where exactly is the boundary?

Where the rule comes from

The first two questions have one answer. The derivative $f'(w)$ is the slope of the tangent line at $w$, and near the point of tangency the curve and the line are close. So for a small change $\Delta$ in the parameter,

f(w + \Delta) \approx f(w) + f'(w)\,\Delta.

This is the first-order approximation of $f$ at $w$. It reduces our problem to a question about a straight line, and the answer is immediate: $f(w) + f'(w)\Delta$ is smaller than $f(w)$ for any $\Delta$ whose sign is opposite to that of $f'(w)$. The choice $\Delta = -\eta f'(w)$ with $\eta > 0$ always has that property, and it predicts

f\bigl(w - \eta f'(w)\bigr) \approx f(w) - \eta\, f'(w)^2.

The predicted change, $-\eta f'(w)^2$, is negative whenever the slope is not zero.

This is the rule we ran by hand. Notice what its justification does not say. The approximation is trustworthy only for small $\Delta$, and $\Delta = -\eta f'(w)$ is small only if $\eta$ is. The tangent line promises a drop of $\eta f'(w)^2$, and the more you ask of it the less the curve agrees.

What the tangent line promises and what the curve delivers, for one step from w = 2 on f(w) = w^2. For \eta = 0.1 the two nearly agree. For \eta = 0.4 the line promises a height of -2.4, which the function never reaches. For \eta = 0.9 the promise is far below the plot. — What the tangent line promises and what the curve delivers, for one step from $w = 2$ on $f(w) = w^2$. For $\eta = 0.1$ the two nearly agree. For $\eta = 0.4$ the line promises a height of $-2.4$, which the function never reaches. For $\eta = 0.9$ the promise is far below the plot.

Exactly which learning rates work

The third question can be answered completely for a parabola. On $f(w) = w^2$ every run multiplied $w$ by the same number at each step: $0.8$, $0.2$, $-0.8$, $-1.2$ for $\eta = 0.1, 0.4, 0.9, 1.1$. Those multipliers are all $1 - 2\eta$, because $w - \eta \cdot 2w = (1 - 2\eta)\,w$. The same happens for a parabola of any steepness.

For $f(w) = w^2$ we have $a = 1$, so the boundary is $\eta = 1$: the rate $0.9$ converged and $1.1$ did not. Shifting the parabola changes nothing: for $f(w) = a(w - w^*)^2 + c$ the update gives $w_{k+1} - w^* = (1 - 2a\eta)(w_k - w^*)$, so the same five cases describe the distance from $w^*$.

The multiplier m = 1 - 2\eta for f(w) = w^2, as a function of the learning rate. Each step multiplies the distance from the minimum by m. Gradient descent converges exactly where m lies strictly between -1 and 1, that is, for 0 < \eta < 1. — The multiplier $m = 1 - 2\eta$ for $f(w) = w^2$, as a function of the learning rate. Each step multiplies the distance from the minimum by $m$. Gradient descent converges exactly where $m$ lies strictly between $-1$ and $1$, that is, for $0 < \eta < 1$.

The boundary depends on $a$, which measures how sharply the parabola curves: its second derivative is $f'' = 2a$, so the condition reads $\eta < 2/f''$. A sharply curved bowl demands small steps. The reason is the error of the first-order approximation. For $f(w) = aw^2$ direct expansion gives

f\bigl(w - \eta f'(w)\bigr) = f(w) - \eta\,(1 - a\eta)\,f'(w)^2,

which is the tangent line’s promise multiplied by $(1 - a\eta)$: nearly kept when $a\eta$ is small, reversed when $a\eta > 1$.

Two dials: the gradient

Now return to the houses and their two parameters. A function of two variables has two slopes at each point, one for each variable, called partial derivatives: $\partial L/\partial w$ is the derivative of $L$ with respect to $w$ with $b$ held fixed, and $\partial L/\partial b$ the reverse. Together they form a vector, the gradient:

\nabla L = \Bigl(\frac{\partial L}{\partial w}, \frac{\partial L}{\partial b}\Bigr) = \bigl(15w + 5b - 20.5,\; 5w + 2b - 7\bigr).

The first-order approximation now reads $L(w + \Delta_w, b + \Delta_b) \approx L(w, b) + \frac{\partial L}{\partial w}\Delta_w + \frac{\partial L}{\partial b}\Delta_b$, and the last two terms are the dot product of the gradient with the step $\Delta = (\Delta_w, \Delta_b)$. We want the step that makes it most negative. Since $\nabla L \cdot \Delta = |\nabla L|\,|\Delta| \cos\theta$, where $\theta$ is the angle between the two vectors, a step of given length does best when $\cos\theta = -1$: when $\Delta$ points directly opposite to the gradient. Taking $\Delta = -\eta\,\nabla L$ predicts a change of $-\eta\,|\nabla L|^2$, as in one variable.

For a loss that is a mean over data, the gradient is computed from the errors. With $e_i = wx_i + b - y_i$ and $L = \frac1n\sum e_i^2$, the chain rule gives

\frac{\partial L}{\partial w} = \frac2n\sum e_i x_i, \qquad \frac{\partial L}{\partial b} = \frac2n\sum e_i.

Let us run it by hand. Start from the flat line $\hat y = 3$, which guesses $300,000 for every house: $w = 0$, $b = 3$. The prices are $1.5, 3.5, 3.5, 5.5$ at sizes $1, 2, 3, 4$, so the errors are $1.5, -0.5, -0.5, -2.5$ and the loss is $(2.25 + 0.25 + 0.25 + 6.25)/4 = 2.25$. Then $\sum e_i = -2$ and $\sum e_ix_i = 1.5 - 1 - 1.5 - 10 = -11$, so

\nabla L(0, 3) = \bigl(\tfrac24(-11),\; \tfrac24(-2)\bigr) = (-5.5, -1).

Pause and try

Take one step from $(0, 3)$ with learning rate $\eta = 0.05$. Where do you land, and what is the loss there? (Use $L = 7.5w^2 + 5wb + b^2 - 20.5w - 7b + 14.25$.)

Show answerHide answer

$w = 0 - 0.05 \times (-5.5) = 0.275$ and $b = 3 - 0.05 \times (-1) = 3.05$. The loss is $7.5(0.0756) + 5(0.8388) + 9.3025 - 5.6375 - 21.35 + 14.25 \approx 1.326$. One step took the loss from $2.25$ to $1.33$. The tangent approximation promised a drop of $\eta\,|\nabla L|^2 = 0.05 \times 31.25 \approx 1.56$, and the surface delivered $0.92$.

The second step starts from $(0.275, 3.05)$, where the gradient is $(-1.125, 0.475)$, and lands at $(0.331, 3.026)$ with loss $1.269$. The first step lowered the loss by $0.92$ and the second by only $0.06$.

At the start the gradient is (-5.5, -1). The arrow points the opposite way: downhill, straight across the level curves.
Learning rate 0.05, two steps. The first is a long hop to the valley floor and the second is already short.
Forty steps at 0.05. The path creeps along the valley floor.
Forty steps at 0.11. Every step overshoots the floor and lands on the opposite wall, a little lower each time.
Forty steps at 0.125. Now every overshoot lands higher than the last, and the path leaves the map.

Gradient descent on the loss map of the four houses, starting from the flat line at $(w, b) = (0, 3)$, for three learning rates. Both axes use the same scale, so each step leaves at a right angle to the level curve it starts on. The green dot is the minimum at $(1.2, 0.5)$.

Monocurl source

let fm = MapFrame([-0.75, 0.05, 0])
let P05 = descend(HX, [0, 3], 0.05, 40)
let P11 = descend(HX, [0, 3], 0.11, 40)
let P12 = descend(HX, [0, 3], 0.125, 40)
let Side = |eta, path, n, col| [
    center{[2.3, 1.3, 0]} Math(str_join(["\eta = ", eta]), 1.0, col),
    center{[2.3, 0.55, 0]} Note("steps taken", 0.76),
    center{[2.3, 0.1, 0]} Math(to_string(n), 1.0, INK),
    center{[2.3, -0.6, 0]} Note("loss now", 0.76),
    center{[2.3, -1.05, 0]} Math(to_string(loss(path[n][0], path[n][1]), 2), 1.0, ROSE)
]
let G0 = grad_on(HX, 0, 3)
mesh map_ = LossMap(fm)
mesh arrow = []
mesh walk = []
mesh side = []

slide "At the start the gradient is (-5.5, -1). The arrow points the opposite way: downhill, straight across the level curves."
    arrow = [Tip(at(fm, 0, 3), at(fm, 0.77, 3.14), INK, 3.5, 0.17), Pt(at(fm, 0, 3), INK, 0.08)]
    side = [
        center{[2.3, 0.85, 0]} Note("gradient at the start", 0.76),
        center{[2.3, 0.35, 0]} Math(str_join(["(", to_string(G0[0], 1), ",\ ", to_string(G0[1], 1), ")"]), 0.95, INK),
        center{[2.3, -0.45, 0]} Note("direction of the step", 0.76),
        center{[2.3, -0.95, 0]} Math(str_join(["(", to_string(-G0[0], 1), ",\ ", to_string(-G0[1], 1), ")"]), 0.95, INK)
    ]
    play Fade(0.6)

slide "Learning rate 0.05, two steps. The first is a long hop to the valley floor and the second is already short."
    arrow = []
    side = []
    play Fade(0.3)
    walk = Walk(fm, P05, u: 0, EMBER)
    side = Side("0.05", P05, 2, EMBER)
    play Fade(0.5)
    walk.u = 2
    play Lerp(2, [&walk], linear)

slide "Forty steps at 0.05. The path creeps along the valley floor."
    side = []
    play Fade(0.3, [&side])
    walk.u = 40
    play Lerp(3.5, [&walk], linear)
    side = Side("0.05", P05, 40, EMBER)
    play Fade(0.4, [&side])

slide "Forty steps at 0.11. Every step overshoots the floor and lands on the opposite wall, a little lower each time."
    walk = []
    side = []
    play Fade(0.3)
    walk = Walk(fm, P11, u: 0, PLUM)
    play Fade(0.3)
    walk.u = 40
    play Lerp(4, [&walk], linear)
    side = Side("0.11", P11, 40, PLUM)
    play Fade(0.4, [&side])

slide "Forty steps at 0.125. Now every overshoot lands higher than the last, and the path leaves the map."
    walk = []
    side = []
    play Fade(0.3)
    walk = Walk(fm, P12, u: 0, ROSE)
    play Fade(0.3)
    walk.u = 40
    play Lerp(4, [&walk], linear)
    side = Side("0.125", P12, 40, ROSE)
    play Fade(0.4, [&side])

Uses the shared definitions for this lesson's figures.

Why the valley is slow

The figure shows the cases of the one-dial theorem in two directions at once. Across the valley the surface is a steep parabola, and the walker behaves as in cases 1, 3 and 5. Along the valley it is a very shallow parabola, with a multiplier close to 1. Here is why the two directions can be treated separately.

The minimum is $p^* = (1.2, 0.5)$. Writing $\Delta_w = w - 1.2$ and $\Delta_b = b - 0.5$, the gradient formula becomes $\nabla L = (15\Delta_w + 5\Delta_b,\; 5\Delta_w + 2\Delta_b)$, as you can check by expanding. So the gradient is a linear function of the displacement from the minimum. Test two displacements. For $(\Delta_w, \Delta_b) = (0.322, -0.947)$, which points along the valley, the gradient is $(15 \times 0.322 - 5 \times 0.947,\; 5 \times 0.322 - 2 \times 0.947) = (0.095, -0.284)$, which is $0.299$ times the displacement, up to rounding. For $(0.947, 0.322)$, across the valley, the gradient is $(15.82, 5.38)$, which is $16.7$ times the displacement. In these two directions the gradient points along the displacement, so a step of gradient descent just rescales it:

\text{along the valley: } \Delta \leftarrow (1 - 0.299\,\eta)\,\Delta, \qquad \text{across it: } \Delta \leftarrow (1 - 16.7\,\eta)\,\Delta.

Every displacement is a sum of a piece along the valley and a piece across it, and because the gradient is linear the two pieces evolve independently, each obeying the one-dial theorem with $2a$ equal to $0.299$ or $16.7$. (The two directions are the eigenvectors of the matrix of second derivatives of $L$. Such a perpendicular pair exists for every quadratic bowl, by the spectral theorem for symmetric matrices; here we verified it by multiplication.)

Convergence across the valley needs $|1 - 16.7\eta| < 1$, that is $\eta < 2/16.7 \approx 0.120$, which is why $0.11$ zigzagged home and $0.125$ blew up. But with $\eta$ capped near $0.12$, the multiplier along the valley is at best $1 - 0.299 \times 0.12 \approx 0.964$. With $\eta = 0.05$ it is $0.985$, and shrinking the valley error by a factor of 100 takes $\ln 0.01 / \ln 0.985 \approx 305$ steps. The steep direction sets the speed limit, and the shallow direction has to live with it.

There is a cure for this valley, and it is used everywhere. The valley exists because the sizes $1, 2, 3, 4$ all lie on one side of zero, so tilting the line and shifting it have overlapping effects. Subtract the mean size, $2.5$, from every size and fit $\hat y = w(x - 2.5) + c$ instead. This is the same family of lines, with $c = b + 2.5w$. Its loss is $1.25(w - 1.2)^2 + (c - 3.5)^2 + 0.2$, by the formula of the previous lesson, and the two directions now have $2a = 2.5$ and $2a = 2$: a nearly round bowl.

The same data and the same starting line, before and after centering the sizes. Left: with raw sizes, 40 steps at learning rate 0.05 leave the walker far from the minimum. Right: with the mean size subtracted, the bowl is nearly round, a learning rate of 0.4 is safe, and 5 steps are enough.

Cheaper gradients: stochastic and mini-batch descent

The gradient of a mean is the mean of the gradients: $\nabla L = \frac1n\sum \nabla\ell_i$, where $\ell_i = e_i^2$ is the loss on example $i$ alone. With four houses that is nothing. With ten million examples, each step as defined above reads all ten million. Stochastic gradient descent instead picks one example at random and steps along $-\eta\,\nabla\ell_i$; mini-batch gradient descent averages over a small random subset, typically a few dozen to a few thousand examples. Either is an estimate of the true gradient that is right on average and noisy on any one step. The path jitters, but each step is far cheaper, and in practice that trade wins. What we found about learning rates carries over, with the extra requirement that the noise be tamed, usually by shrinking $\eta$ as training proceeds.

When the surface is not a bowl

For the line-fitting loss, the previous lesson proved that the surface is convex: a single bowl. Then any point where the gradient is zero is the lowest point, and gradient descent, if it converges, converges to the best parameters. Most models lose that guarantee.

Consider the one-parameter function $f(w) = w^4 - 2w^2 + 0.5w$. Its derivative $f'(w) = 4w^3 - 4w + 0.5$ vanishes at three places: $w \approx -1.057$, $w \approx 0.127$ and $w \approx 0.930$.

Its graph has two dips, at $-1.057$ and $0.930$, separated by a hump at $0.127$. A walker that starts at $w = 0.3$, to the right of the hump, feels a negative slope, moves right, and settles in the right dip, where $f \approx -0.52$. A walker that starts at $-0.2$ settles in the left dip, where $f \approx -1.51$. The first walker ends at a point that is not the lowest.

Two runs of gradient descent on $f(w) = w^4 - 2w^2 + 0.5w$, both with learning rate 0.05 for 60 steps. They start on opposite sides of the hump at $w \approx 0.13$, only half a unit apart, and settle in different dips. The right dip is a local minimum; the left one is lower.

Monocurl source

let fn = Frame(-1.7, 1.6, -1.8, 2.4, [0, 0.15, 0], 6.2, 3.0)
let f = |w| w ^ 4 - 2 * w * w + 0.5 * w
let fp = |w| 4 * w ^ 3 - 4 * w + 0.5
let RA = iterate(fp, 0.3, 0.05, 60)
let RB = iterate(fp, -0.2, 0.05, 60)
let pos = |ws, u| {
    let k = min(to_int(floor(u + 0.0001)), len(ws) - 2)
    return ws[k] + clamp(u - k, 0, 1) * (ws[k + 1] - ws[k])
}
let Ball = |ws, u, col| [
    map(take(ws, step_of(ws, u) + 1), |w| Pt(at(fn, w, f(w)), col, 0.04)),
    Ring(at(fn, pos(ws, u), f(pos(ws, u))), col, 0.11, 4)
]
let Both = |u| [Ball(RA, u, EMBER), Ball(RB, u, PLUM), center{[2.9, 1.93, 0]} scale{1.05} color{INK} Number(floor(u + 0.0001), 0)]
mesh plot = PlotFrame(fn, [-1.5, -1, -0.5, 0, 0.5, 1, 1.5], [-1, 0, 1, 2], "parameter w", "f(w)", 1)
mesh zero = Seg(at(fn, -1.7, 0), at(fn, 1.6, 0), SLATE, 2)
mesh curve = Path(filter(map(sample(-1.7, 1.6, 200), |w| at(fn, w, f(w))), |p| p[1] < fy(fn, 2.4)), AZURE, 4)
mesh labels = [
    center{at(fn, 0.93, -1.0)} Cap("local minimum", 0.72, EMBER),
    center{at(fn, -0.28, -1.55)} Cap("global minimum", 0.72, PLUM),
    center{[2.3, 1.93, 0]} Cap("step", 0.76, INK)
]
mesh both = Both(u: 0)

slide "settle"
    play Wait(0.8)
    both.u = 60
    play Lerp(6, [&both], |t| t ^ 2)
    play Wait(1.5)

Uses the shared definitions for this lesson's figures.

Gradient descent stops moving exactly at stationary points, since the update is $-\eta\nabla L$. It cannot tell a local minimum from a global one, because both are flat. Which one it reaches depends on where it started.

In two or more dimensions there is a third kind of stationary point, which is neither a dip nor a peak. Take $g(x, y) = x^2 - y^2$. Its gradient $(2x, -2y)$ vanishes at the origin. Along the $x$ axis the origin is the bottom of the parabola $x^2$; along the $y$ axis it is the top of the parabola $-y^2$. Such a point is called a saddle point. Gradient descent on $g$ multiplies $x$ by $1 - 2\eta$ and $y$ by $1 + 2\eta$ at every step, so $x$ shrinks and $y$ grows.

Gradient descent on the saddle $g(x, y) = x^2 - y^2$ (orange where $g > 0$, blue where $g < 0$), learning rate 0.1, 30 steps. A walker started exactly on the $x$ axis (black, with a wider line and a square marker) slides into the saddle point and stays. A walker started 0.01 above the axis (purple, round marker) follows it, nearly stops, and then escapes downhill.

Monocurl source

let fs = Frame(-1.7, 1.7, -1.7, 1.7, [-0.6, 0.1, 0], 3.4, 3.4)
let g = |x, y| x * x - y * y
let gshade = |v| lerp(PAPER, tint([AZURE, EMBER][v > 0], 0.5), clamp(abs(v) / 2.6, 0, 1))
let saddle_run = |y0| {
    var p = [1.5, y0]
    var out = [p]
    for (k in range(0, 30)) {
        p = [p[0] - 0.1 * 2 * p[0], p[1] + 0.1 * 2 * p[1]]
        out .= p
    }
    return out
}
let SA = saddle_run(0)
let SB = saddle_run(0.01)
let hyper = |c, s| map(sample(-1.7, 1.7, 80), |t| [[s * sqrt(max(c + t * t, 0)), t], [t, s * sqrt(max(t * t - c, 0))]][c < 0])
mesh field = stroke{alpha{0} PAPER, 0} point_map{|p| at(fs, p[0], p[1])}
    ColorGrid(|p, idx| gshade(g(p[0], p[1])), [-1.7, 1.7, 61], [-1.7, 1.7, 61], 1)
mesh curves = [
    map([0.5, 1, 2, -0.5, -1, -2], |c| [Clipped(fs, hyper(c, 1), SLATE, 1.8), Clipped(fs, hyper(c, -1), SLATE, 1.8)]),
    Seg(at(fs, -1.7, -1.7), at(fs, 1.7, 1.7), SLATE, 1.8),
    Seg(at(fs, -1.7, 1.7), at(fs, 1.7, -1.7), SLATE, 1.8)
]
mesh frame = [
    Outline([at(fs, -1.7, -1.7), at(fs, 1.7, -1.7), at(fs, 1.7, 1.7), at(fs, -1.7, 1.7)], SLATE, 2.5),
    map([-1, 0, 1], |v| [
        center{[fx(fs, v), fy(fs, -1.7) - 0.3, 0]} Math(to_string(v), 0.72, SLATE),
        center{[fx(fs, -1.7) - 0.3, fy(fs, v), 0]} Math(to_string(v), 0.72, SLATE)
    ]),
    center{[fx(fs, 1.55), fy(fs, -1.7) - 0.3, 0]} Math("x", 0.82, SLATE),
    center{[fx(fs, -1.7) - 0.3, fy(fs, 1.55), 0]} Math("y", 0.82, SLATE)
]
# the on-axis walker gets a square marker, so it stays visible around the purple ring while the two overlap
let SquareMark = |c, r = 0.17| fill{PAPER} stroke{INK, 4} Polygon([[c[0] - r, c[1] - r, 0], [c[0] + r, c[1] - r, 0], [c[0] + r, c[1] + r, 0], [c[0] - r, c[1] + r, 0]])
let Under = |path, u| {
    let p = spot(path, u)
    let seen = take(path, step_of(path, u) + 1)
    return [Clipped(fs, seen .. p, INK, 8), SquareMark(at(fs, p[0], p[1]))]
}
let Two = |u| {
    let a = spot(SA, u)
    let b = spot(SB, u)
    return [
        Under(SA, u),
        Walk(fs, SB, u, PLUM),
        center{[2.72, 0.72, 0]} scale{1.05} color{INK} Number(g(a[0], a[1]), 2),
        center{[2.72, -0.78, 0]} scale{1.05} color{PLUM} Number(g(b[0], b[1]), 2),
        center{[2.9, 1.75, 0]} scale{1.05} color{INK} Number(floor(u + 0.0001), 0)
    ]
}
mesh names = [
    center{[2.25, 1.75, 0]} Cap("step", 0.76, INK),
    SquareMark([1.62, 1.15, 0], 0.11),
    center{[2.72, 1.15, 0]} Cap("on the axis: g =", 0.72, INK),
    Ring([1.62, -0.35, 0], PLUM, 0.09, 3.5),
    center{[2.72, -0.35, 0]} Cap("just off it: g =", 0.72, PLUM)
]
mesh two = Two(u: 0)

slide "saddle"
    play Wait(0.8)
    two.u = 30
    play Lerp(7, [&two], linear)
    play Wait(1.5)

Uses the shared definitions for this lesson's figures.

Only starts exactly on the $x$ axis are drawn into this saddle. Any other start eventually escapes, though it may loiter for many steps while the gradient is tiny. In large models, slow progress near saddle points and flat regions is a more frequent complaint than a poor local minimum.

So the guarantees are these. For a convex differentiable loss, every stationary point is a global minimum (a theorem of convex analysis), so a convergent run has found the best parameters. For a general loss, a convergent run has found a stationary point, and nothing more is promised.

Worked examples

Stepping back

The hard part was the learning rate. The update rule falls straight out of the tangent approximation, but that approximation is local and the rule takes steps of finite size, so everything turns on how far the function departs from its tangent over one step, which is to say on curvature. On a parabola we could compute this exactly, and the answer, $\eta < 1/a$, explained both the divergence and the slow crawl along a valley.

The update rule never mentions lines or houses, only a loss and its gradient. The next lesson applies it to a model whose loss has no formula for its minimum, so that descent is the only way to train it. For a neural network even the gradient takes work to compute, and backpropagation is the method for that.

Check yourself

Gradient descent on $f(w) = 4w^2$ is started at $w_0 = 1$ with learning rate $\eta = 0.3$. What happens?

Recap

Gradient descent updates parameters by $p \leftarrow p - \eta\,\nabla L(p)$. In one variable, $w \leftarrow w - \eta f'(w)$.
The rule comes from the first-order approximation $L(p + \Delta) \approx L(p) + \nabla L \cdot \Delta$, which is most negative, for a given step length, when $\Delta$ is opposite to the gradient.
On $f(w) = aw^2$ each step multiplies $w$ by $1 - 2a\eta$. It converges if and only if $0 < \eta < 1/a$: from one side below $\frac{1}{2a}$, alternating above it, diverging beyond $\frac1a$.
On a quadratic bowl in two parameters, two perpendicular directions each behave like their own parabola. The sharpest limits $\eta$, and the shallowest then converges slowly. Centering the inputs makes the bowl rounder.
Descent stops only at stationary points: the global minimum for a convex loss, otherwise possibly a local minimum or a saddle point.

Problems

The first two are computations, the next two combine ideas, and the last two go beyond the lesson.

Problem 1

For $f(w) = 3w^2$ and $w_0 = 1$, compute $w_1, w_2, w_3$ with $\eta = 0.1$. What is the largest learning rate for which gradient descent converges, and which learning rate reaches the minimum in one step?

Show solutionHide solution

$f'(w) = 6w$, so $w \leftarrow w - 0.6w = 0.4w$: $w_1 = 0.4$, $w_2 = 0.16$, $w_3 = 0.064$. With $a = 3$, convergence holds exactly for $0 < \eta < \frac13$: there is no largest such rate, since $\frac13$ itself fails (the walker bounces between $1$ and $-1$). One step suffices when $\eta = \frac{1}{2a} = \frac16$: then $w_1 = 1 - \frac16 \times 6 = 0$.

Problem 2

On the house loss $L = 7.5w^2 + 5wb + b^2 - 20.5w - 7b + 14.25$, compute the gradient at $(w, b) = (1, 1)$, take one step with $\eta = 0.05$, and compare the loss before and after. One of the partial derivatives is zero at $(1, 1)$. Does that mean that dial is already at its best value?

Show solutionHide solution

$\nabla L = (15 + 5 - 20.5,\; 5 + 2 - 7) = (-0.5, 0)$. The step is to $(1 + 0.025, 1) = (1.025, 1)$. Before, $L(1, 1) = 0.25$. After, $L = 7.5(1.050625) + 5.125 + 1 - 21.0125 - 7 + 14.25 = 0.2422$ to four places. The zero partial derivative means that $b = 1$ is the best intercept for the slope $w = 1$. It is not the best overall, which is $0.5$. As soon as $w$ changes, $\partial L/\partial b = 5w + 2b - 7$ is no longer zero: at $(1.025, 1)$ it is $0.125$, and the next step lowers $b$.

Problem 3

A student proposes a simpler rule: “Do not multiply by the slope. Just move a fixed distance $\delta$ in the downhill direction at every step.” Run this rule on $f(w) = w^2$ from $w_0 = 2$ with $\delta = 0.3$ until the pattern is clear. What goes wrong, and how does the gradient descent rule avoid it?

Show solutionHide solution

Downhill is toward 0, so the values are $2, 1.7, 1.4, 1.1, 0.8, 0.5, 0.2$. From $0.2$ the slope is positive, so the walker moves left by $0.3$ to $-0.1$. There the slope is negative, so it moves right to $0.2$, then back to $-0.1$, forever. It never settles: once within $\delta$ of the minimum it oscillates between two points. A smaller $\delta$ shrinks the oscillation but slows the approach in the same proportion. Gradient descent’s step $\eta f'(w)$ shrinks as the slope does, so it is long far from the minimum and short near it.

Problem 4

Using the multipliers found in the lesson: (a) with raw sizes and $\eta = 0.05$, the valley direction is multiplied by $1 - 0.299 \times 0.05$ per step. How many steps reduce that component by a factor of 1000? (b) With centered sizes, the loss is $1.25(w - 1.2)^2 + (c - 3.5)^2 + 0.2$ and $\eta = 0.4$. Find the multiplier in each direction, and the number of steps that reduce the error by a factor of 1000.

Show solutionHide solution

(a) The multiplier is $0.98505$. We need $0.98505^k \le 0.001$, so $k \ge \ln 0.001 / \ln 0.98505 = 6.908 / 0.015063 \approx 458.6$: 459 steps. (b) In the $w$ direction $a = 1.25$, so the multiplier is $1 - 2 \times 1.25 \times 0.4 = 0$: that coordinate is exact after one step. In the $c$ direction $a = 1$ and the multiplier is $1 - 0.8 = 0.2$. Since $0.2^4 = 0.0016$ and $0.2^5 = 0.00032$, five steps are enough. Centering turned 459 steps into 5.

Problem 5

(No single safe rate.) Let $f(w) = w^4$ and fix $\eta > 0$. (a) Show that the update is $w_{k+1} = w_k\,(1 - 4\eta w_k^2)$. (b) Prove that if $4\eta w_0^2 < 2$ and $w_0 \neq 0$, then $|w_k|$ decreases and converges to 0. (c) Show that if $4\eta w_0^2 > 2$ then $|w_k|$ increases without bound. (d) What does this say about choosing a learning rate for a function that is not quadratic?

Show solutionHide solution

(a) $f'(w) = 4w^3$, so $w_{k+1} = w_k - 4\eta w_k^3 = w_k(1 - 4\eta w_k^2)$.

(b) Put $t_k = 4\eta w_k^2$, so $|w_{k+1}| = |w_k|\,|1 - t_k|$. If some $w_k$ is 0, every later term is 0 and the claim holds, so suppose none is. If $0 < t_k < 2$ then $|1 - t_k| < 1$, so $|w_{k+1}| < |w_k|$, and therefore $t_{k+1} < t_k < 2$ as well. By induction the sequence $|w_k|$ is decreasing. A decreasing sequence of nonnegative numbers has a limit $\ell \ge 0$. Letting $k \to \infty$ in $|w_{k+1}| = |w_k|\,|1 - 4\eta w_k^2|$ gives $\ell = \ell\,|1 - 4\eta\ell^2|$, so either $\ell = 0$ or $|1 - 4\eta\ell^2| = 1$, which means $4\eta\ell^2 = 0$ or $2$. But $4\eta\ell^2 \le t_1 < 2$, so $\ell = 0$.

(c) If $t_k > 2$ then $|1 - t_k| = t_k - 1 > 1$, so $|w_{k+1}| > |w_k|$ and $t_{k+1} > t_k > 2$. By induction $|w_k|$ increases, and at each step it is multiplied by at least $t_0 - 1 > 1$, so it grows without bound.

(d) For $w^4$ the boundary between convergence and divergence is $|w_0| = 1/\sqrt{2\eta}$: every learning rate works for starts close enough to 0 and fails for starts far enough away. The curvature $f''(w) = 12w^2$ is not constant, so the safe rate depends on where the walker is.

Problem 6

For the saddle $g(x, y) = x^2 - y^2$ and a learning rate $0 < \eta < 1$: (a) write the gradient descent update for $x$ and for $y$; (b) show that the run converges to the saddle point $(0, 0)$ if and only if $y_0 = 0$; (c) with $\eta = 0.1$ and $y_0 = 0.01$, how many steps pass before $|y|$ exceeds 1?

Show solutionHide solution

(a) $\nabla g = (2x, -2y)$, so $x \leftarrow (1 - 2\eta)x$ and $y \leftarrow (1 + 2\eta)y$. (b) After $k$ steps, $x_k = (1 - 2\eta)^kx_0$ and $y_k = (1 + 2\eta)^ky_0$. Since $0 < \eta < 1$, $|1 - 2\eta| < 1$ and $x_k \to 0$ for every $x_0$. Since $1 + 2\eta > 1$, $|y_k| \to \infty$ unless $y_0 = 0$, in which case $y_k = 0$ for all $k$. So the run converges to $(0, 0)$ exactly when $y_0 = 0$. (c) $y_k = 0.01 \times 1.2^k$ exceeds 1 when $1.2^k > 100$, that is $k > \ln 100/\ln 1.2 = 4.605/0.1823 \approx 25.3$. So $|y|$ first exceeds 1 at step 26.

Shared definitions used by this lesson's figures

# house kit: prepended to every essay figure after the std imports

# palette. AZURE and EMBER are the two actors, LEAF marks an answer, ROSE a problem
let PAPER = [1, 1, 1, 1]
let INK = [0.08, 0.09, 0.11, 1]
let SLATE = [0.40, 0.44, 0.50, 1]
let MIST = [0.85, 0.86, 0.88, 1]
let AZURE = [0.13, 0.42, 0.68, 1]
let EMBER = [0.89, 0.42, 0.12, 1]
let LEAF = [0.13, 0.55, 0.36, 1]
let ROSE = [0.78, 0.22, 0.24, 1]
let PLUM = [0.47, 0.30, 0.66, 1]
let GOLD = [0.85, 0.62, 0.08, 1]

background = PAPER

# an opaque pastel of col; use for fills so overlaps do not darken
let tint = |col, amount = 0.18| [
    1 - (1 - col[0]) * amount,
    1 - (1 - col[1]) * amount,
    1 - (1 - col[2]) * amount,
    1
]

# text: Cap for labels, Note for quiet labels, Math for typeset maths
let Cap = |txt, size = 0.75, col = INK| color{col} Text(txt, size, "Charter")
let Note = |txt, size = 0.65| color{SLATE} Text(txt, size, "Charter")
let Math = |tex, size = 0.9, col = INK| color{col} Tex(tex, size)

# a paper rectangle to sit behind text that crosses lines
let Plate = |pos, size| center{pos} fill{PAPER} stroke{alpha{0} PAPER, 0} Rect(size)

# shapes with fill and stroke both set, so no stray black appears
let Pt = |pos, col = INK, r = 0.075| center{pos} fill{col} stroke{col, 1} Circle(r, 48)
let Ring = |pos, col = INK, r = 0.1, w = 3| center{pos} fill{PAPER} stroke{col, w} Circle(r, 48)
let Seg = |a, b, col = INK, w = 3| stroke{col, w} Line(a, b)
let Path = |pts, col = INK, w = 3| stroke{col, w} Polyline(pts)
let Region = |pts, col| fill{col} stroke{alpha{0} col, 0} Polygon(pts)
let Outline = |pts, col = INK, w = 3| fill{alpha{0} PAPER} stroke{col, w} Polygon(pts)
let Shape = |pts, col, amount = 0.18, w = 3| fill{tint(col, amount)} stroke{col, w} Polygon(pts)
let Disc = |pos, r, col, amount = 0.18, w = 3| center{pos} fill{tint(col, amount)} stroke{col, w} Circle(r, 96)
let Box = |pos, size, col, amount = 0.18, w = 3| center{pos} fill{tint(col, amount)} stroke{col, w} Rect(size)
# a line from a to b ending in a small solid arrowhead
let Tip = |a, b, col = INK, w = 3, head = 0.17| {
    let d = normalize([b[0] - a[0], b[1] - a[1], 0])
    let n = [-d[1], d[0], 0]
    let base = [b[0] - d[0] * head, b[1] - d[1] * head, 0]
    return [
        stroke{col, w} Line(a, base),
        fill{col} stroke{col, 1} Polygon([
            b,
            [base[0] + n[0] * head * 0.42, base[1] + n[1] * head * 0.42, 0],
            [base[0] - n[0] * head * 0.42, base[1] - n[1] * head * 0.42, 0]
        ])
    ]
}

# plots. a frame is [x0, x1, y0, y1, centre, width, height]: a data window and the scene box it fills
let Frame = |x0, x1, y0, y1, c = [0, 0, 0], w = 6.4, h = 3.6| [x0, x1, y0, y1, c, w, h]
let fx = |fr, x| fr[4][0] + (x - (fr[0] + fr[1]) / 2) * fr[5] / (fr[1] - fr[0])
let fy = |fr, y| fr[4][1] + (y - (fr[2] + fr[3]) / 2) * fr[6] / (fr[3] - fr[2])
let at = |fr, x, y| [fx(fr, x), fy(fr, y), 0]

# axes through the data origin (or the nearest edge of the window), with optional names
let Axes = |fr, x_name = "", y_name = "", col = SLATE| {
    let ox = clamp(fr[0], 0, fr[1])
    let oy = clamp(fr[2], 0, fr[3])
    var parts = [
        Tip(at(fr, fr[0], oy), [fx(fr, fr[1]) + 0.25, fy(fr, oy), 0], col, 2.5, 0.15),
        Tip(at(fr, ox, fr[2]), [fx(fr, ox), fy(fr, fr[3]) + 0.25, 0], col, 2.5, 0.15)
    ]
    if (x_name != "") {
        parts .= center{[fx(fr, fr[1]) + 0.5, fy(fr, oy), 0]} Math(x_name, 0.8, col)
    }
    if (y_name != "") {
        parts .= center{[fx(fr, ox), fy(fr, fr[3]) + 0.5, 0]} Math(y_name, 0.8, col)
    }
    return parts
}

# tick marks with numbers at the listed data values
let XTicks = |fr, xs, col = SLATE, places = 0| block {
    let oy = fy(fr, clamp(fr[2], 0, fr[3]))
    for (x in xs) {
        . Seg([fx(fr, x), oy - 0.07, 0], [fx(fr, x), oy + 0.07, 0], col, 2)
        . center{[fx(fr, x), oy - 0.33, 0]} Math(to_string(x, places), 0.72, col)
    }
}
let YTicks = |fr, ys, col = SLATE, places = 0| block {
    let ox = fx(fr, clamp(fr[0], 0, fr[1]))
    for (y in ys) {
        . Seg([ox - 0.07, fy(fr, y), 0], [ox + 0.07, fy(fr, y), 0], col, 2)
        . center{[ox - 0.36, fy(fr, y), 0]} Math(to_string(y, places), 0.72, col)
    }
}

# faint grid lines at the listed data values
let GridLines = |fr, xs, ys, col = MIST| block {
    for (x in xs) {
        . Seg(at(fr, x, fr[2]), at(fr, x, fr[3]), col, 1.5)
    }
    for (y in ys) {
        . Seg(at(fr, fr[0], y), at(fr, fr[1], y), col, 1.5)
    }
}

# the graph of f over [a, b], drawn in the frame. values are clamped to the window
let Graph = |fr, f, a, b, col = AZURE, w = 4, n = 160|
    stroke{col, w} Polyline(map(sample(a, b, n), |x| at(fr, x, clamp(fr[2], f(x), fr[3]))))

# the region between the graph of f and the x axis over [a, b]
let AreaUnder = |fr, f, a, b, col = AZURE, amount = 0.2, n = 80| {
    var pts = [at(fr, a, 0)]
    for (x in sample(a, b, n)) {
        pts .= at(fr, x, clamp(fr[2], f(x), fr[3]))
    }
    pts .= at(fr, b, 0)
    return fill{tint(col, amount)} stroke{alpha{0} col, 0} Polygon(pts)
}

# the four houses of the previous lesson: size (1000 sq ft) and price ($100k)
let HX = [1, 2, 3, 4]
let HY = [1.5, 3.5, 3.5, 5.5]
let CX = [-1.5, -0.5, 0.5, 1.5]
let loss_on = |xs, w, b| mean(map(range(0, 4), |i| (w * xs[i] + b - HY[i]) ^ 2))
let grad_on = |xs, w, b| [
    2 * mean(map(range(0, 4), |i| (w * xs[i] + b - HY[i]) * xs[i])),
    2 * mean(map(range(0, 4), |i| w * xs[i] + b - HY[i]))
]
let loss = |w, b| loss_on(HX, w, b)
# n steps of gradient descent with learning rate eta; returns the list of n + 1 points
let descend = |xs, start, eta, n| {
    var p = start
    var out = [start]
    for (k in range(0, n)) {
        let g = grad_on(xs, p[0], p[1])
        p = [p[0] - eta * g[0], p[1] - eta * g[1]]
        out .= p
    }
    return out
}
let LMIN = loss(1.2, 0.5)
# position after u steps, u fractional, moving in straight hops
let step_of = |path, u| min(to_int(floor(u + 0.0001)), len(path) - 2)
let spot = |path, u| {
    let k = step_of(path, u)
    let f = clamp(u - k, 0, 1)
    return [path[k][0] + f * (path[k + 1][0] - path[k][0]), path[k][1] + f * (path[k + 1][1] - path[k][1])]
}
let inside = |fr, p| p[0] >= fr[0] and p[0] <= fr[1] and p[1] >= fr[2] and p[1] <= fr[3]
# draw the parts of a list of data points that fall inside the frame
let Clipped = |fr, pts, col, th| block {
    var cur = []
    for (p in pts) {
        if (inside(fr, p)) {
            cur .= at(fr, p[0], p[1])
        } else {
            if (len(cur) >= 2) { . Path(cur, col, th) }
            cur = []
        }
    }
    if (len(cur) >= 2) { . Path(cur, col, th) }
}
let Walk = |fr, path, u, col = EMBER| {
    let k = step_of(path, u)
    let p = spot(path, u)
    let seen = take(path, k + 1)
    return [
        Clipped(fr, seen .. p, col, 3),
        map(filter(seen, |q| inside(fr, q)), |q| Pt(at(fr, q[0], q[1]), col, 0.04)),
        map(filter([p], |q| inside(fr, q)), |q| Ring(at(fr, q[0], q[1]), col, 0.09, 3.5))
    ]
}
# the plane of the two dials with equal scales on both axes: slope w across, intercept b up
let MapFrame = |c, s = 0.9, b0 = -0.1| Frame(-0.5, 2.7, b0, b0 + 3.7, c, 3.2 * s, 3.7 * s)
let shade = |v| lerp(tint(AZURE, 0.04), tint(AZURE, 0.6), clamp(ln(max(v, 0.2) / 0.2) / ln(80), 0, 1))
let Shaded = |fr, f| stroke{alpha{0} PAPER, 0} point_map{|p| at(fr, p[0], p[1])}
    ColorGrid(|p, idx| shade(f(p[0], p[1])), [fr[0], fr[1], 61], [fr[2], fr[3], 61], 1)
let LEVELS = [0.5, 1, 2, 4, 8]
# level curve loss = c for the raw sizes, and for the centered sizes
let level = |c| map(sample(0, TAU, 300), |t| {
    let w = 1.2 + sqrt((c - LMIN) / 1.25) * cos(t)
    return [w, 3.5 - 2.5 * w + sqrt(c - LMIN) * sin(t)]
})
let level_c = |c| map(sample(0, TAU, 200), |t| [1.2 + sqrt((c - LMIN) / 1.25) * cos(t), 3.5 + sqrt(c - LMIN) * sin(t)])
let MapTicks = |fr, bs, bname = "b"| [
    Outline([at(fr, fr[0], fr[2]), at(fr, fr[1], fr[2]), at(fr, fr[1], fr[3]), at(fr, fr[0], fr[3])], SLATE, 2.5),
    map([0, 1, 2], |v| [
        Seg(at(fr, v, fr[2]), [fx(fr, v), fy(fr, fr[2]) - 0.08, 0], SLATE, 2),
        center{[fx(fr, v), fy(fr, fr[2]) - 0.3, 0]} Math(to_string(v), 0.72, SLATE)
    ]),
    map(bs, |v| [
        Seg(at(fr, fr[0], v), [fx(fr, fr[0]) - 0.08, fy(fr, v), 0], SLATE, 2),
        center{[fx(fr, fr[0]) - 0.3, fy(fr, v), 0]} Math(to_string(v), 0.72, SLATE)
    ]),
    center{[fx(fr, 2.55), fy(fr, fr[2]) - 0.3, 0]} Math("w", 0.82, SLATE),
    center{[fx(fr, fr[0]) - 0.3, fy(fr, fr[3]) - 0.15, 0]} Math(bname, 0.82, SLATE)
]
let LossMap = |fr| [
    Shaded(fr, loss),
    map(LEVELS, |c| Clipped(fr, level(c), AZURE, 2)),
    MapTicks(fr, [0, 1, 2, 3]),
    Pt(at(fr, 1.2, 0.5), LEAF, 0.08)
]
# data plot
let DataFrame = |c, w, h| Frame(0, 5, 0, 7, c, w, h)
let DataPlot = |fr| [
    GridLines(fr, [1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6, 7]),
    Seg(at(fr, 0, 0), at(fr, 5, 0), SLATE, 2.5),
    Seg(at(fr, 0, 0), at(fr, 0, 7), SLATE, 2.5),
    map([1, 2, 3, 4], |v| center{[fx(fr, v), fy(fr, 0) - 0.3, 0]} Math(to_string(v), 0.72, SLATE)),
    map([2, 4, 6], |v| center{[fx(fr, 0) - 0.28, fy(fr, v), 0]} Math(to_string(v), 0.72, SLATE)),
    center{[fx(fr, 2.5), fy(fr, 0) - 0.66, 0]} Note("size (1000 sq ft)", 0.72),
    center{[fx(fr, 0) + 0.6, fy(fr, 7) + 0.28, 0]} Note("price ($100k)", 0.72)
]
let Houses = |fr| map(range(0, 4), |i| Pt(at(fr, HX[i], HY[i]), INK, 0.09))
let LineOn = |fr, w, b, col = EMBER, th = 4| {
    var lo = 0.05
    var hi = 4.95
    if (w > 0.01) {
        lo = max(lo, (0.05 - b) / w)
        hi = min(hi, (6.95 - b) / w)
    }
    return Seg(at(fr, lo, w * lo + b), at(fr, hi, w * hi + b), col, th)
}
# one dial: the parabola f(w) = w^2 and gradient descent on it
let sq = |w| w * w
let iterate = |fp, w0, eta, n| {
    var w = w0
    var out = [w0]
    for (k in range(0, n)) {
        w = w - eta * fp(w)
        out .= w
    }
    return out
}
let PlotFrame = |fr, xs, ys, xname, yname, places = 0| [
    GridLines(fr, xs, ys),
    Seg(at(fr, fr[0], fr[2]), at(fr, fr[1], fr[2]), SLATE, 2.5),
    Seg(at(fr, fr[0], fr[2]), at(fr, fr[0], fr[3]), SLATE, 2.5),
    map(xs, |v| center{[fx(fr, v), fy(fr, fr[2]) - 0.3, 0]} Math(to_string(v, places), 0.72, SLATE)),
    map(ys, |v| center{[fx(fr, fr[0]) - 0.34, fy(fr, v), 0]} Math(to_string(v), 0.72, SLATE)),
    center{[fx(fr, (fr[0] + fr[1]) / 2), fy(fr, fr[2]) - 0.66, 0]} Note(xname, 0.74),
    center{[fx(fr, fr[0]) + 0.1, fy(fr, fr[3]) + 0.28, 0]} Note(yname, 0.74)
]