Unit 10 · Optimization I — Gradients that Work

1

The bill for being wrong — and why the squares are squares

The tailor's patches

A tailor cuts three sleeves to a rule of thumb — "sleeve length is w times the arm measurement". Each sleeve comes out a little long or a little short, and every miss costs a square patch of cloth with the miss as its side: miss by 1 cm, pay for 1 cm²; miss by 3 cm, pay for 9 cm². Short and long cost the same, and one big miss costs more than three small ones. The bill is the total area of the patches. Turn the knob w and watch the patches grow and shrink:

Try: drag $w$ from 0 toward 2.36 and watch the three squares shrink together, then press ▶ descend with $\eta=0.02$ — the bead on the bill curve hops $78\to15.3\to3.1\to0.78$ . Then push $\eta$ past $0.0714$ and press ▶ again: the squares grow.

slope w0

stride η0.02

—

$J(w)=\sum_i (w x_i-y_i)^2 = 14w^2-66w+78$ is a parabola in $w$ : its slope is $28w-66$ , zero at $w^*=33/14$ . One descent step multiplies the distance to $w^*$ by $1-28\eta$ , so the walk shrinks only while $\eta<1/14$ .

Everything a model does while "training" is on that picture. The knob is a parameter. The three points are the data. The bill is the loss, and the squares are not a metaphor: the loss is the total area of the squares. Slide the knob and the areas change together — the first square wants the line steeper, the third wants it flatter, and the knob settles where they stop being able to shrink at once. That is the bottom of the bill curve on the right: slope zero, bill smallest.

For one knob you can read the bottom off the curve. With many knobs the bill is still a sum of squares — one square per data row, now with the side "what I predicted minus what was true" — and there is no curve to look at, only the tilt under your feet. The tilt has a beautiful shape once you see the squares: each square pushes the knobs in the direction of its own data row, harder when its miss is bigger. The uphill direction is just all those pushes added up.

The realization

$J(\mathbf w)=\sum_{i}\big(\mathbf w^{\top}\mathbf X_i-y_i\big)^2,\qquad \nabla J=2\sum_i\underbrace{(\mathbf w^{\top}\mathbf X_i-y_i)}_{\text{the miss}}\;\underbrace{\mathbf X_i}_{\text{its row}}$

Each row pulls the knobs along its own feature vector, in proportion to its miss. Positive miss (predicted too much) ⇒ push the knobs down along that row. That one sentence is the whole gradient of least squares — and it is the sentence you would have written after watching the squares.

Press ▶ on the tailor's bill with the stride $\eta=0.02$ : the knob hops $0\to1.32\to1.90\to2.16$ , the bill $78\to15.3\to3.1\to0.8$ . Each hop closes the remaining gap to the bottom by the same fraction, $1-28\eta=0.44$ — the bouncing ball of Unit 9, now with a bill attached. Push $\eta$ past $1/14$ and the hops overshoot by more than they gain: the squares grow. Keep that number in mind; the whole unit is about what sets it.

Pause & predict

The tailor's three misses are currently $(-2,\,-5,\,-7)$ : every sleeve is too short (the line is below all three points). Which way does the bill's tilt push the knob $w$ ?

If you want the algebra · 2 proofs, step by step

Prove it · the gradient of the least-squares bill

Claim. For $J(\mathbf w)=\sum_i(\mathbf w^{\top}\mathbf X_i-y_i)^2$ , $\ \nabla J=2\sum_i(\mathbf w^{\top}\mathbf X_i-y_i)\,\mathbf X_i$ .

1

Name each miss:

r_i=\mathbf w^{\top}\mathbf X_i-y_i

. Then

J=\sum_i r_i^2

. A sum of squares of something simple is the easiest shape to differentiate.

2

The miss is linear in

\mathbf w

:

\nabla_{\mathbf w}\,r_i=\mathbf X_i

.

r_i=\sum_j w_jx_{ij}-y_i\ \Rightarrow\ \frac{\partial r_i}{\partial w_j}=x_{ij}.

Knob

j

touches row

i

only through the product

w_jx_{ij}

; its derivative is the feature value.

3

Chain rule on one square, then add the rows:

\nabla\,r_i^2=2r_i\,\nabla r_i=2r_i\mathbf X_i,\qquad \nabla J=2\sum_i r_i\mathbf X_i.

∎ Read it: every row pulls the knobs along its own feature vector, in proportion to its miss. With

r_i=\hat y_i-y_i

the sign is

+

and the minus sign lives in the update

\mathbf w\leftarrow\mathbf w-\eta\nabla J

.

Prove it · the tailor's bill has its bottom at

w^*=33/14

Claim. For $x=(1,2,3)$ , $y=(2,5,7)$ and $\hat y=wx$ : $J(w)=14w^2-66w+78$ , $w^*=33/14\approx2.357$ , $J^*=3/14\approx0.214$ , and the per-step factor at stride $\eta$ is $1-28\eta$ .

1

Expand the three squares and add:

\begin{aligned}(w-2)^2&=w^2-4w+4\\ (2w-5)^2&=4w^2-20w+25\\ (3w-7)^2&=9w^2-42w+49\\ J(w)&=14w^2-66w+78.\end{aligned}

The coefficient

14=\sum x_i^2

is the column's size squared — the stiffness of this one knob.

2

Set the slope to zero:

J'(w)=28w-66=0\Rightarrow w^*=66/28=33/14

. And

J''=28>0

: a valley. One knob, one parabola, one bottom.

3

The bill at the bottom:

\begin{aligned}J^*&=\frac{14\cdot33^2}{14^2}-\frac{66\cdot33}{14}+78\\ &=\frac{1089-2178+1092}{14}=\frac{3}{14}.\end{aligned}

Not zero: three points do not lie on one line through the origin, and

3/14

is the area the best line cannot remove.

4

One step of descent:

w-\eta(28w-66)=w^*+(1-28\eta)(w-w^*)

, since

28w-66=28(w-w^*)

. ∎ The gap to the bottom is multiplied by

1-28\eta

each step:

0.44

at

\eta=0.02

, and the walk diverges once

28\eta>2

, i.e.

\eta>1/14

.

In one sentence: The loss is the total area of one square per data row, and its tilt is the sum of each row's push — miss times row — which is why the same recipe works for one knob or a billion.

2

The parachute drop — where you start

The drop

Before the walk in the fog there is a parachute drop: somebody has to choose where the walker lands. Two mistakes are famous. Drop from too high, in the wrong place, and the first step is so violent it throws you off the map. And drop a whole team on the same square metre, all facing the same way, and they will take exactly the same steps for ever — a team of one. Watch the first mistake happen in numbers:

Try: press ▶ and watch the bars climb the ladder by $79\times$ a step until they hit the float64 ceiling. Then slide $\log_{10}\eta$ below $-4.6$ — the same start is suddenly forgiven, because $\eta<1/x^2$ .

log₁₀ |w₀|1

log₁₀ η0.001

—

With one feature the update is $w\leftarrow w-2\eta x(wx-y)$ , i.e. the miss is multiplied by $1-2\eta x^2$ each step. For $x=200$ and $\eta=10^{-3}$ that factor is $-79$ : no starting point survives — the feature's size, not the start, is the culprit. And two knobs that start equal on a symmetric loss receive identical gradients for ever.

The overflow ladder is the surprising one. A modest start ( $w_0=1$ ), a plain feature ( $x=200$ ), a small-looking stride ( $\eta=0.001$ ) — and the error does not shrink by a factor, it multiplies by $79$ every step. By step 163 the number is larger than any a computer can hold; it becomes $\infty$ , then $\infty-\infty$ , which is $\mathrm{NaN}$ , and the whole run is dead. Now slide $w_0$ anywhere you like: nothing changes. The start was never the culprit. The factor per step is $1-2\eta x^2$ , and with $x=200$ that is $1-80$ . The feature's size, squared, is what set the speed limit, and the only escape is a stride under $1/x^2=2.5\times10^{-5}$ — absurdly tiny, because $x$ is absurdly big. That is why the lecture's advice for the start is so modest: small numbers in $[-1,1]$ (or $[0,1]$ when the knobs must stay positive). Small starts do not cause overflow; they just do not add to a problem the data's units have already created. Sections 4 and 10 fix the units.

The clones tab is the second mistake. Two knobs that play symmetric roles, started at exactly the same value, receive exactly the same tilt — so they stay equal after every step, for ever. Two neurons started as clones never stop being clones: the network has half the neurons it seems to have. Nudge one start a little (drag separation off zero) and the tie breaks at once. That is the whole reason initialisation is random: randomness costs nothing and it is the only thing that lets identical knobs become different.

The realization

Start small, central and random. Small: $w_0\in[-1,1]$ , so you do not throw the first step off the map. Random: so no two symmetric knobs are clones. And when the numbers blow up anyway, look at the factor $1-2\eta x^2$ — it is the data's units, not your start, that need fixing.

Pause & predict

With $x=200$ and $\eta=0.001$ every start overflows. You halve the start to $w_0=0.5$ . What happens?

If you want the algebra · 1 proof, step by step

Prove it · why the start is not the culprit

Claim. For the one-feature bill $(wx-y)^2$ , gradient descent multiplies the error $wx-y$ by $1-2\eta x^2$ every step, whatever $w_0$ is; it converges iff $\eta<1/x^2$ .

1

The gradient is

2x(wx-y)

, so the update is

w\leftarrow w-2\eta x(wx-y)

. Chain rule on one square: outer

2(wx-y)

, inner

x

.

2

Multiply by

x

and subtract

y

to follow the error

e=wx-y

:

e_{\text{new}}=(w-2\eta x\,e)\,x-y=e-2\eta x^2e=(1-2\eta x^2)\,e.

The error obeys a one-line rule with a constant factor.

w_0

only sets

e_0

; the factor is

x

and

\eta

alone.

3

Convergence needs

|1-2\eta x^2|<1

, i.e.

0<\eta<1/x^2

. With

x=200

:

\eta<2.5\times10^{-5}

; at

\eta=10^{-3}

the factor is

-79

. ∎

79^k|e_0|

passes

1.8\times10^{308}

(the largest float64) at

k=163

for

e_0\approx193

: overflow, then

\infty-\infty=\mathrm{NaN}

. Halving

w_0

delays this by

\ln2/\ln79\approx0.16

of a step.

In one sentence: Land small, central and random — and when the numbers explode anyway, blame the feature's size squared in the factor

1-2\eta x^2

, not the place you landed.

3

Full marks by memorising — knobs versus facts

Last year's paper

Two students sit the same three-question test. One learned the subject and gets 96 %. The other memorised last year's answer key — and this year's paper happens to be the same three questions, so she scores 100 %. Which one would you hire? The trap is that the number you can see says the memoriser is better. The lecture's data has exactly this shape: three rows, five knobs, and the truth is simply y ≈ x₁. Drag the unseen point:

Try: switch to the memoriser — it sits exactly on all three training dots ( $J=0$ ). Now drag the unseen point along the diagonal: the truth moves, the memoriser's prediction stays glued to $62$ .

unseen x₁50

—

Rows $(x_1,x_2,x_3,x_4,y)$ : $(61,2,3,0.1,59)$ , $(40,0,4,0.5,40)$ , $(68,0,10,1,70)$ . Three equations in five unknowns leave two knobs free — so a model can score $J=0$ using variables that have nothing to do with the answer. Training error measures fit, not understanding; only a row the model never saw measures learning.

The honest model has one knob set to 1 and the rest to 0: it says y = x₁. On the three rows it misses by $2,0,-2$ , a bill of $8$ . The memoriser ignores $x_1$ altogether and uses the other columns and the constant to hit all three rows exactly — a bill of $0$ . Any optimiser told "make the bill smallest" will choose the memoriser without a flicker of doubt.

Now drag the unseen point. Its truth slides along the diagonal, because the truth really is $y\approx x_1$ . The honest model's prediction slides with it. The memoriser's prediction is a flat line at $62$ : it does not contain $x_1$ , so it cannot respond to it. At $x_1=50$ it is off by $12$ — and that is a typical error, not an unlucky one. Zero on the training rows, hopeless on the world.

How was zero even possible? Count. Five knobs, three facts. Three equations in five unknowns have infinitely many exact solutions — two knobs are left completely free. Being told "two numbers add to 10" does not tell you the numbers. The data never pinned the knobs down, so the optimiser handed you one of the infinitely many settings that fit, and it has no way of knowing which one means something. The honest model's $8$ is not a failure to fit; it is the size of the noise in the three rows. Chasing that last $8$ to zero is where learning turned into memorising.

The realization

More knobs than facts ⇒ zero training bill is free ⇒ zero training bill means nothing. Judge a model on rows it has never seen. (Later units will make the memoriser expensive by adding a penalty on big knobs — a regulariser — so that "fits the data with small knobs" beats "fits the data with any knobs".)

Errata — check this against your slides

The deck quotes the memorising solution as $w_2=7,\ w_3=5,\ w_5=20$ . Check row 1: $7\cdot2+5\cdot3+20=49$ , but $y_1=59$ . Solving the three equations properly gives $w_3=5,\ w_5=20,\ w_2=12$ (the drawer below and Practice Problem 8 do it line by line). The lesson is untouched; only the arithmetic needed a nudge.

Pause & predict

A model has $8$ knobs and you train it on $6$ rows. The training bill lands on exactly $0$ . How pleased should you be?

Pause & predict

You drag the unseen point from $x_1=50$ to $x_1=70$ (truth $\approx70$ ). What do the two models predict?

If you want the algebra · 2 proofs, step by step

Prove it · the memoriser, solved (and the slide's slip)

Claim. With $w_1=w_4=0$ , the three rows are hit exactly by $w_3=5,\ w_5=20,\ w_2=12$ ; the slide's $w_2=7$ does not hit row 1.

1

Write the three rows as equations in

w_2,w_3,w_5

:

\begin{aligned}2w_2+3w_3+w_5&=59\\4w_3+w_5&=40\\10w_3+w_5&=70.\end{aligned}

Rows 2 and 3 have

x_2=0

, so

w_2

drops out of them — two equations in two unknowns.

2

Subtract row 2 from row 3:

6w_3=30\Rightarrow w_3=5

. Back into row 2:

20+w_5=40\Rightarrow w_5=20

. Elimination, exactly as in Unit 1.

3

Into row 1:

2w_2+15+20=59\Rightarrow w_2=12

. Check the slide's triple:

7\cdot2+5\cdot3+20=49\neq59

. ∎ On the unseen row

(50,1,6,0.3)

the memoriser says

12+30+20=62

whatever

x_1

is; the truth is about

50

.

Prove it · more knobs than facts ⇒ a zero bill is free

Claim. If a linear model has $d$ knobs and $n<d$ training rows whose feature vectors are independent, there are infinitely many $\mathbf w$ with $J(\mathbf w)=0$ .

1

J=0

means every miss is zero:

X\mathbf w=\mathbf y

, a system of

n

equations in

d

unknowns,

X

being

n\times d

. A sum of squares is zero only when every square is.

2

With independent rows,

\operatorname{rank}X=n

, so

X\mathbf w=\mathbf y

is consistent and its solution set is a particular solution plus the null space, of dimension

d-n\ge1

. Unit 1's rank–nullity:

d-n

free parameters, hence a whole line, plane, … of exact fits.

3

Every point of that set has a zero bill, so an optimiser told only "minimise

J

" cannot prefer one; which it returns depends on the start and the walk, not on the truth. ∎ The lecture's case:

d=5

,

n=3

, two free knobs. A penalty

\lambda\sum_jw_j^2

breaks the tie in favour of small knobs — the honest model here has a single knob equal to

1

.

In one sentence: With more knobs than facts a zero bill is free and therefore meaningless — the memoriser hits every training row and cannot see the one variable that matters.

4

The hair-trigger and the stiff knob

Two knobs, one hand

An old radio has two knobs. One is a hair-trigger: a millimetre of turn swings the station wildly. The other is stiff: you can spin it and almost nothing happens. Now imagine you are only allowed to turn both by the same amount per move. Any move gentle enough not to over-turn the hair-trigger is far too gentle to budge the stiff one. You will overshoot on one dial and crawl on the other. That is precisely what one stride $\eta$ does to two parameters whose features have different sizes:

Try: press serve the stiff knob and then ▶ — the age needle swings past its mark and back while the college needle finally moves. Press protect the hair-trigger: now the college needle barely stirs in 8 steps.

age x₁50

college x₂4

log₁₀ η1e−5

—

For $y=w_1x_1^2+w_2x_2^2$ the gradient is $(x_1^2 r,\;x_2^2 r)$ : the age knob is $x_1^2/x_2^2$ times more sensitive than the college knob, and both get the same $\eta$ . The only way both dials behave is to make the two features the same size — the next widget.

The lecture's model predicts wealth from age and years of college: $y=w_1x_1^2+w_2x_2^2$ . Age runs to $100$ ; college runs to $10$ . At a typical person ( $x_1=50$ , $x_2=4$ ) the bill is $2500$ times more sensitive to the age knob than to the college knob — because sensitivity is the feature's value, squared, and $50^2/4^2=156$ . Same stride, so the age knob moves $156$ times further per step. Press ▶ and watch the needles: the age dial swings past its mark and back; the college dial creeps.

Try to fix it with the stride alone. Protect the hair-trigger (a stride that moves $w_1$ by $0.01$ ) and the stiff knob needs thousands of steps per unit. Serve the stiff knob and the hair-trigger swings by whole units and oscillates. There is no stride that suits both, because the imbalance is not in the stride — it is in the units of the features. Age in years and college in years are both "years", but their sizes differ by ten, and the bill feels sizes squared. The only real fix is to make the two features the same size. That is the next section, and — after a detour through valleys and canyons — the whole of Section 10.

The realization

$\partial y/\partial w_j = x_j^2$ : a knob's sensitivity is its feature's size, squared. One stride $\eta$ moves knob $j$ by $\eta\,x_j^2\,|\text{miss}|$ . Different feature sizes ⇒ one knob overshoots while another crawls, and no $\eta$ can serve both. Normalisation exists to make $x_j$ the same size for every $j$ .

Pause & predict

At the current step, $\partial J/\partial w_1=-640$ and $\partial J/\partial w_2=-1.6$ , and one stride $\gamma=10^{-3}$ serves both. How far does each knob move this step, and roughly how many steps does $w_2$ need to travel one unit?

If you want the algebra · 1 proof, step by step

Prove it · the two knobs move

x_1^2/x_2^2

times differently

Claim. For $y=w_1x_1^2+w_2x_2^2$ and a squared-error bill, one stride $\eta$ moves $w_1$ by $\eta x_1^2|r|$ and $w_2$ by $\eta x_2^2|r|$ per row — a ratio of $x_1^2/x_2^2$ ( $156$ at $x_1=50,\ x_2=4$ ).

1

Sensitivities of the prediction:

\partial y/\partial w_1=x_1^2

,

\partial y/\partial w_2=x_2^2

. Each knob multiplies its own feature-squared; the derivative is that feature-squared.

2

For the bill

\tfrac12(y-t)^2

with miss

r=y-t

:

\partial J/\partial w_1=r\,x_1^2

,

\partial J/\partial w_2=r\,x_2^2

(chain rule). The same miss multiplies both; only the feature-squared differs.

3

The update moves

w_j

by

\eta\,|r|\,x_j^2

. Ratio:

x_1^2/x_2^2=2500/16=156.25

. ∎ A stride that moves

w_1

by

0.01

moves

w_2

by

0.000064

per unit miss; a stride that moves

w_2

by

0.01

moves

w_1

by

1.56

. No single

\eta

is sane for both.

In one sentence: A knob's sensitivity is its feature's size squared, so features of different sizes turn one stride into a hair-trigger on one knob and a stiff crawl on the other — and no stride can fix what only the units can.

5

Three ways to fix the units — centre, standardise, min–max

The same map, redrawn

A map of a country drawn with kilometres east and metres north is a long thin smear: every route looks like it runs east–west. Nothing about the country is thin; the units are. Redraw the north axis in kilometres and the shape reappears. The data is the map. Here are the three redrawings the lecture uses, side by side, on a cloud you can watch move:

Try: click standardise and watch the smear squeeze into a round blob around the origin. Then pick the outlier cloud and click min–max — one point pins the corner and crushes everyone else.

unseen x₁0.9

—

Every repair is a per-column affine map fixed by the training statistics, and the same map must be applied to new data. After standardising, every column has mean 0 and variance 1: "one unit" means "one standard deviation of surprise" in every column. Min–max is bounded and simple, but a single outlier sets the box.

Three operations, each a motion you just saw. Centring subtracts each column's mean: the cloud slides so its centre sits on the origin. Shape unchanged; it only removes the "everything is around 15" offset that makes all columns look alike to a knob. Standardising also divides each column by its spread: the cloud squeezes so that every column has spread $1$ . After this, "one unit" means "one standard deviation of surprise" in every column — the radio's two knobs now have the same stiffness. Min–max squashes every column into $[0,1]$ : the cloud is pressed into a box. Simple and bounded, but look at the outlier preset: one wild point squashes everybody else into a corner, and a new value beyond the training maximum lands outside the box ( $1.25$ on the practice column, where standardising would have said an unremarkable $z=2.12$ ).

One rule the widget insists on: the unseen point is transformed with the training statistics. The mean and spread are part of the model now. Recompute them with the test point and the test point has leaked into the training.

Repair	Formula	What moves	Use it when
centre	$x_{ij}\leftarrow x_{ij}-\mu_j$	the cloud slides onto the origin; shape unchanged	the offset is the problem, not the scale
standardise	$x_{ij}\leftarrow (x_{ij}-\mu_j)/\sigma_j$	slides, then squeezes to spread $1$ per column	almost always — the default before gradient descent
min–max	$x_{ij}\leftarrow (x_{ij}-\min_j)/(\max_j-\min_j)$	pressed into the unit box	bounded inputs matter and there are no outliers

The realization

Normalisation changes the units, not the meaning. Standardised columns each have mean $0$ and $\sum_i z_{ij}^2=n$ — every column is now the same size — so one stride can serve every knob. What it does not remove is a tilt: two columns that rise and fall together stay tilted after standardising. That leftover is Section 10's last word.

Pause & predict

A training column has $\mu=40,\ \sigma=8$ , minimum $20$ and maximum $60$ . A new value $x=72$ arrives. What do standardising and min–max make of it?

If you want the algebra · 1 proof, step by step

Prove it · a standardised column has mean

0

and

\sum z^2=n

Claim. For $z_i=(x_i-\mu)/\sigma$ with $\mu=\frac1n\sum x_i$ and $\sigma^2=\frac1n\sum(x_i-\mu)^2$ : $\sum_iz_i=0$ and $\sum_iz_i^2=n$ .

1

\sum_i(x_i-\mu)=\sum_ix_i-n\mu=n\mu-n\mu=0

, so

\sum_iz_i=0

. Subtracting the mean makes the deviations cancel exactly.

2

\sum_iz_i^2=\dfrac{1}{\sigma^2}\sum_i(x_i-\mu)^2=\dfrac{n\sigma^2}{\sigma^2}=n

. ∎ This is why, after standardising, every diagonal of

2Z^{\top}Z

is the same

2n

: every column is now the same size. On the practice column

(30,\dots,110)

:

z=(-1.414,-0.707,0,0.707,1.414)

, sum

0

, sum of squares

5

.

In one sentence: Centre slides, standardise squeezes, min–max boxes — all three redraw the data's units so that every column is the same size, and all three are applied to new data with the training statistics.

6

The wrong valley — the watershed and the combination lock

Rain on a ridge

Rain falls on a mountain ridge. Every drop rolls downhill and ends in a lake — but which lake was decided the instant it landed, by which side of the ridge it fell on. A drop one centimetre left of the crest ends in the shallow lake; one centimetre right, in the deep one. The crest is the watershed. Gradient descent is a raindrop. Drop a few dozen on the lecture's landscape and watch them sort themselves:

Try: press ▶ drop the marbles and watch the rain split at the watershed $x=1.634$ : about $59\%$ reach the deep valley. Then open the lock tab with 10 dials — $0.6^{10}\approx0.006$ is the chance of opening it in one go.

starts from0

starts to4

marbles24

stride η0.02

—

$F'(x)=4x^3-24x^2+42x-22$ vanishes at $1$ , $1.634$ and $3.366$ . A downhill walker never climbs the watershed, so the start alone picks the valley; with $d$ knobs each having $k$ flat spots there are $k^d$ settings of $\nabla F=0$ and restarts alone cannot search them.

The lecture's curve has two valleys: a shallow one at $x=1$ (height $0$ ) and a deep one at $x=3.37$ (height $-4.85$ ), with a hilltop between them at $x=1.63$ . Every marble that lands left of the hilltop rolls into the shallow valley and stops there, reporting success, with a valley five units deeper sitting next door. It never had a hint. The walk in Unit 9 only ever found "the valley downhill from here"; this is the price. Drop the marbles on $[0,4]$ and about $59\,\%$ reach the deep valley — the share of the range that lies right of the watershed. Nothing about the walk changed that number; only the drop zone did.

So restart from several random places and keep the best? On a line, yes: with a $0.59$ chance per drop, six drops find the deep valley $99\,\%$ of the time. Now open the lock tab. A landscape with many knobs is a combination lock: if each knob's own curve has $k$ flat spots, the whole landscape has a flat spot for every combination — $k^d$ of them, and exactly one is the true bottom. Ten dials with three notches each: $59{,}049$ valleys. Fifty dials: about $7\times10^{23}$ . And the chance that a single drop lands right on every dial multiplies too: $0.6^{10}\approx0.006$ . Restarts cannot rescue that. (Deep learning lives with it: on the landscapes of large networks most valleys turn out to be about equally good, and Section 11 says what to do when they are not.)

The realization

For a loss that splits into one-knob pieces, $F=A_1(x_1)+\dots+A_d(x_d)$ , the tilt in knob $i$ is $A_i'(x_i)$ alone — so any choice of one flat spot per knob is a flat spot of $F$ . Count: $\prod_i k_i$ local minima. With independent per-knob odds $p$ , one run lands in the global basin of every knob with probability $p^d$ , and $k$ restarts fail with probability $(1-p)^k$ .

Pause & predict

Marbles are dropped uniformly on $[0,4]$ of the lecture's curve, whose watershed is at $x=1.634$ . What fraction reaches the deep valley, and how many independent drops make the chance of at least one success reach $99\,\%$ ?

Pause & predict

A loss splits into $10$ one-knob pieces, each with $3$ flat spots of which one is its true bottom, and a random start lands in each knob's best basin with probability $0.6$ . How many flat spots does the whole loss have, and what is the chance one run lands in the best basin of every knob?

If you want the algebra · 3 proofs, step by step

Prove it · the lecture's curve has a watershed at

(5-\sqrt3)/2

Claim. $F(x)=(x-1)^2\big((x-3)^2-1\big)$ is flat at $x=1$ , $1.634$ , $3.366$ : valley ( $F=0$ ), hilltop ( $F=0.348$ ), valley ( $F=-4.848$ ).

1

Product rule with

u=(x-1)^2

,

v=(x-3)^2-1

:

\begin{aligned}F'&=2(x-1)\,v+(x-1)^2\cdot2(x-3)\\ &=2(x-1)\big[(x-3)^2-1+(x-1)(x-3)\big].\end{aligned}

Pull out the common

2(x-1)

first; it hands you the root

x=1

for free.

2

Simplify the bracket:

(x^2-6x+8)+(x^2-4x+3)=2x^2-10x+11

. So

F'=2(x-1)(2x^2-10x+11)=4x^3-24x^2+42x-22

. Two quadratics added; nothing cancels except the arithmetic.

3

2x^2-10x+11=0\Rightarrow x=\dfrac{10\pm\sqrt{100-88}}{4}=\dfrac{5\pm\sqrt3}{2}=1.634,\ 3.366

. The discriminant

12=4\cdot3

is what makes

\sqrt3

appear.

4

F''=12x^2-48x+42

:

F''(1)=6>0

,

F''(1.634)=-4.39<0

,

F''(3.366)=16.39>0

. Heights

F(1)=0

,

F(1.634)=0.348

,

F(3.366)=-4.848

. ∎ Valley, hilltop, valley. A downhill walker from

x_0<1.634

ends at

F=0

with

F=-4.848

next door.

Prove it · the combination lock —

\prod k_i

local minima

Claim. If $F(x_1,\dots,x_d)=A_1(x_1)+\dots+A_d(x_d)$ and $A_i$ has $k_i$ local minima, then $F$ has $\prod_ik_i$ local minima.

1

\partial F/\partial x_i=A_i'(x_i)

: every other term is a constant as far as

x_i

is concerned. Separable means each knob sees only its own piece.

2

So

\nabla F=0

exactly when every

A_i'(x_i^*)=0

, and

F

curls up in every direction exactly when every

A_i''(x_i^*)>0

(the Hessian is diagonal with entries

A_i''

). A local minimum of

F

is a choice of a local minimum of each piece, independently.

3

Independent choices multiply:

k_1k_2\cdots k_d

. With

k=3

,

d=10

:

59{,}049

;

d=50

:

3^{50}\approx7\times10^{23}

. ∎ Only one combination is the global bottom; a random start lands in it with probability

\prod p_i

(

0.6^{10}\approx0.006

).

Prove it · how many restarts

Claim. If one run finds the global valley with probability $p$ , $k$ independent runs (keep the best) succeed with probability $1-(1-p)^k$ ; for $p=0.6$ and a $99\,\%$ target, $k=6$ .

1

All

k

fail with probability

(1-p)^k

(independence); at least one succeeds otherwise. "At least one" is always easiest through its complement.

2

Require

0.4^k\le0.01

:

0.4^5=0.01024

(just fails),

0.4^6=0.004096

(works). So

k=6

, success

0.9959

. ∎ Compute the powers exactly;

k=5

misses by a hair. In general

k=\lceil\ln0.01/\ln(1-p)\rceil

.

In one sentence: Which valley you reach is decided by which side of the watershed you land on, and with many knobs the valleys multiply like the settings of a combination lock —

k^d

of them — so restarts alone cannot save a walker in high dimensions.

7

The salt flat — where the walk slows to nothing

Level ground in fog

You have come down a cliff at a run and stepped onto a salt flat. The ground is level in every direction. Your one rule — "feel the tilt, step that way, and step further the steeper it is" — now gives you almost nothing to act on. You are not at the bottom of anything; you are on a plateau, and you shuffle across it in steps you can barely see. Watch the footprints:

Try: press ▶ from the cliff and watch the footprints: sparse on the slope, then a dense glowing band across the shelf where every step is tiny. Read the height chart — a long horizontal ledge before the final drop.

drag the picture to orbit

stride γ0.3

steps300

—

The step is $\gamma\nabla f$ : where the ground is flat the gradient is tiny and the step is tinier still — the walker is not at a minimum, just slow. A plateau of tilt $10^{-3}$ crossed at $\gamma=0.01$ moves $10^{-5}$ per step: two units of flat take $\approx 200\,000$ steps.

The footprints are the whole story. Sparse on the cliff, where every step is long. Then a dense glowing band across the shelf, where two hundred steps pile up in the space a handful covered on the slope. Then long strides again down into the bowl. Nothing is wrong with the walker; the step is $\gamma$ times the tilt, and on the flat the tilt is tiny. The height chart on the right shows the same thing as a long horizontal ledge before the final drop.

The arithmetic is brutal. Tilt $0.001$ , stride $0.01$ : each step moves $10^{-5}$ . A flat two units wide takes $200{,}000$ steps — hours of compute to go nowhere, on a plateau that is not a minimum and never was. Unit 9 already showed the walk slowing down as it nears a valley bottom; that is the same effect and there it is welcome. On a plateau it is a trap: the walker slows for the same reason (small tilt) in a place that deserves no slowing.

The realization

Step length $=\gamma\,\lvert\nabla f\rvert$ . Small tilt ⇒ small step, whether or not you are near a minimum. Steps to cross a flat of width $W$ and tilt $g$ : about $W/(\gamma g)$ . The cures are the next unit's: momentum, which carries speed across the flat instead of re-deciding at every footstep, and strides that grow when the tilt stays small.

Pause & predict

The loss has barely moved for $500$ steps: $6.00,\ 5.99,\ 5.99,\ 5.98,\dots$ Which is the wrong conclusion?

If you want the algebra · 1 proof, step by step

Prove it · steps to cross a plateau

Claim. Crossing a flat of width $W$ where the tilt is about $g$ takes roughly $W/(\gamma g)$ steps — $200{,}000$ for $W=2$ , $g=0.001$ , $\gamma=0.01$ .

1

Each step moves

\gamma|\nabla f|\approx\gamma g

along the flat. The update is

-\gamma\nabla f

; on a plateau the direction barely changes and the size is

\gamma g

.

2

Steps

=W/(\gamma g)=2/(0.01\cdot0.001)=2\times10^5

. ∎ Near a true minimum the same slowing is harmless (you are where you want to be); on a plateau it is pure waste. Momentum, next unit, is the cure.

In one sentence: Steps are stride times tilt, so a plateau — small tilt, no minimum — swallows hundreds of thousands of steps, which is the one place slowing down is a trap rather than a comfort.

8

The canyon — why the fastest way down is the wrong way down

Skiing a gully

You are skiing down a narrow gully. The way you actually want to go is along the gully, gently downhill. But the steepest slope under your skis points at the wall. So you shoot across, hit the far wall, shoot back. Every run is downhill; you are barely getting anywhere. Two bowls, one round and one stretched, and the same walker on both:

Try: press ▶ at $c=4$ , $\eta=0.24$ : $y$ flips sign every step $(10\to-9.2\to8.46)$ while $x$ creeps $(10\to5.2\to2.7)$ . Set $c=1$ and $\eta=0.5$ — one step lands at the origin.

drag the picture to orbit

stiffness c4

stride η0.24

steps8

—

Each coordinate is its own one-dimensional problem: $x\leftarrow(1-2\eta)x$ , $y\leftarrow(1-2c\eta)y$ . The stiff direction caps $\eta$ at $1/c$ , and at that cap the soft direction shrinks by only $1-2/c$ per step. Only when $c=1$ does the gradient point at the bottom, and then $\eta=1/2$ finishes in one step.

Set $c=1$ : a perfectly round bowl. From anywhere, the tilt points straight at the bottom — the two arrows lie on top of each other — and a stride of $\eta=0.5$ lands every point on the bottom in one step. Now set $c=4$ : the lecture's elliptical bowl, four times stiffer across than along. The tilt no longer points at the bottom (watch the angle between the two arrows open up). Press ▶ at the lecture's stride $\eta=0.24$ : the $y$ -coordinate flips sign every step, $10\to-9.2\to8.5\to-7.8$ , each time correcting the overshoot of the last; the $x$ -coordinate creeps, $10\to5.2\to2.7$ . After six steps $x$ is essentially solved and $y$ is still at $6$ . Most of the motion was sideways.

The two shrink bars say why nothing better was available. Each coordinate is its own one-dimensional problem, multiplied by its own factor each step: $1-2\eta$ along the floor, $1-2c\eta$ across the walls. The stiff wall demands $\eta<1/c$ or it explodes; at that cap the floor factor is $1-2/c$ , which for a stiff wall is close to $1$ — a crawl. Serve the wall and the floor crawls; serve the floor and the wall blows up. This is the radio of Section 4 again, now drawn as a landscape: different curvatures in different directions are the same disease as different feature sizes. The lecture's phrase is exact: steepest descent is only the best instantaneous direction, never the best direction for the long run.

The realization

On $L=x^2+c\,y^2$ : $x\leftarrow(1-2\eta)x,\quad y\leftarrow(1-2c\eta)y$ . Stability needs both factors inside $(-1,1)$ , so the stiffest direction sets the speed limit $\eta<2/\lambda_{\max}=1/c$ , and the ratio $\kappa=\lambda_{\max}/\lambda_{\min}=c$ — the condition number — says how badly the soft direction crawls at that limit. $\kappa=1$ is a round bowl and one step; big $\kappa$ is a canyon and a zig-zag.

Pause & predict

On $L=x^2+4y^2$ with $\eta=0.24$ you start at $(10,10)$ . Where are you after one step, and which coordinate is misbehaving?

Pause & predict

For $L=x^2+9y^2$ , what is the largest stride that does not blow up, and which direction sets it?

If you want the algebra · 2 proofs, step by step

Prove it · each direction shrinks by its own factor; the stiffest sets the limit

Claim. On $L=x^2+cy^2$ , gradient descent gives $x_{k+1}=(1-2\eta)x_k$ , $y_{k+1}=(1-2c\eta)y_k$ ; it converges iff $\eta<1/c$ (for $c\ge1$ ), and the $y$ -coordinate bounces (sign flips) once $\eta>1/(2c)$ .

1

\nabla L=(2x,\,2cy)

, so

x\leftarrow x-2\eta x

,

y\leftarrow y-2c\eta y

. The bowl has no cross term, so the two coordinates never talk to each other: two one-dimensional problems.

2

Each is a geometric sequence:

x_k=(1-2\eta)^kx_0

,

y_k=(1-2c\eta)^ky_0

. Convergence needs

|1-2\eta|<1

and

|1-2c\eta|<1

, i.e.

\eta<1

and

\eta<1/c

. The stiffer direction's condition is the tighter one:

\eta<1/c=2/\lambda_{\max}

with

\lambda_{\max}=2c

.

3

For

1/(2c)<\eta<1/c

the

y

-factor is negative:

y

overshoots the floor every step. At

c=4

,

\eta=0.24

: factors

0.52

and

-0.92

; from

(10,10)

:

(5.2,-9.2)

,

(2.70,8.46)

,

(1.41,-7.79)

. ∎ At the cap

\eta\to1/c

the floor factor is

1-2/c

: for

c=4

,

0.5

— fine; for

c=1487

,

0.9987

— the crawl of Section 10.

Prove it · the one-step finish on a round bowl, and why a canyon has none

Claim. On $L=x^2+y^2$ , $\eta=1/2$ sends every point to the origin in one step; on $L=x^2+cy^2$ with $c\neq1$ no single $\eta$ does.

1

Round bowl: both factors are

1-2\eta

; at

\eta=1/2

both are

0

, so

(x_1,y_1)=(0,0)

. The gradient

(2x,2y)

points straight at the origin, and

\eta=1/2

walks exactly that far.

2

Canyon: a one-step finish needs

1-2\eta=0

and

1-2c\eta=0

at once, i.e.

\eta=1/2

and

\eta=1/(2c)

— impossible unless

c=1

. ∎ The condition number

\kappa=\lambda_{\max}/\lambda_{\min}=c

measures exactly this conflict;

\kappa=1

is the only case where one stride suits every direction.

In one sentence: In a canyon the tilt points at the wall, not along the floor; each direction shrinks by its own factor

1-\eta\lambda

, the stiffest sets the speed limit, and the ratio

\kappa

of stiff to soft is how much of the walk is wasted bouncing.

9

Why the compass crosses the contour lines at a right angle

Walking a hillside path

A path that runs level along a hillside — neither climbing nor descending — is a contour line. Stand on it and ask: which way is straight up? Not along the path (that stays level). Straight across it. Every hiker knows this without a formula: the steepest way up a hill is at a right angle to the level path. Drag the point and watch the compass needle:

Try: drag the point around the ellipse and watch the chip: the gradient stays at $90.0^\circ$ to the contour but drifts up to $60^\circ$ away from the straight line to the centre. Switch to the circle — the two arrows fuse.

—

Along a level curve $F$ does not change, so for a tiny move $\delta\mathbf x$ along it $\nabla F\cdot\delta\mathbf x=0$ : the gradient is perpendicular to the contour. On a round bowl "across the contour" and "toward the centre" coincide; on a stretched one they differ, and the difference is the zig-zag of the next widget's walker.

Wherever you put the point, the uphill needle meets the contour through it at exactly $90^\circ$ . The reason is one sentence: a tiny move along the contour does not change the height, and the change in height for a tiny move is "tilt dotted with the move" — so tilt dotted with the along-the-contour move is zero, which is what a right angle means. Press ▶ and the point glides around its own contour while the needle rotates to stay perpendicular.

Now the payoff. On the round bowl, "across the contour" happens to be "toward the centre", so the needle points at the answer from anywhere: that was the one-step finish of Section 8. On the stretched bowl the contours are ellipses, and across an ellipse is not toward its centre — the angle between the needle and the straight line to the bottom is the third readout, and it is the exact size of the zig-zag. On the tilted bowl the ellipses are turned, so even a walker who has fixed the scale of each axis still sees a gap. That tilt is correlation between the features, and it is the one thing the next section's fix does not remove.

The realization

Along a contour $F$ is constant, so for a small step $\delta\mathbf x$ along it $F(\mathbf x+\delta\mathbf x)\approx F(\mathbf x)+\nabla F\cdot\delta\mathbf x$ gives $\nabla F\cdot\delta\mathbf x=0$ : the gradient is perpendicular to every contour. It points at the minimum only when the contours are circles.

Pause & predict

On $F=x^2+4y^2$ at the point $(2.2,\,1.1)$ , what is the angle between the gradient and the contour through the point — and between the gradient and the straight line to the minimum?

If you want the algebra · 1 proof, step by step

Prove it · the gradient is perpendicular to every contour

Claim. If $\delta\mathbf x$ is a small displacement along a contour of $F$ , then $\nabla F\cdot\delta\mathbf x=0$ .

1

First-order Taylor (Unit 8):

F(\mathbf x+\delta\mathbf x)\approx F(\mathbf x)+\nabla F\cdot\delta\mathbf x

. The change in height for a small move is the tilt dotted with the move.

2

Along a contour the height does not change:

F(\mathbf x+\delta\mathbf x)=F(\mathbf x)

. Hence

\nabla F\cdot\delta\mathbf x=0

. ∎ Zero dot product means a right angle. On

F=x^2+4y^2

at

(2.2,1.1)

:

\nabla F=(4.4,8.8)

, tangent

(-8.8,4.4)

, dot

0

; the line to the origin

(2.2,1.1)

makes

\cos\theta=0.8

,

\theta\approx36.9^\circ

with the gradient.

In one sentence: A step along a contour changes nothing, so the tilt is at a right angle to every contour — which points at the bottom only when the contours are circles, and the gap on stretched or tilted contours is the zig-zag.

10

Change the units, not the model — the canyon becomes a bowl

Guns and butter

Three countries, two numbers each — guns per person ( $0.1,\ 0.8,\ 0.4$ ) and ounces of butter per person ( $25,\ 10,\ 10$ ) — and a happiness score to predict ( $7,\ 1,\ 4$ ). The butter numbers are thirty times the gun numbers, so the bill is over a thousand times stiffer in the butter knob than in the gun knob. The landscape is a razor blade. You hold the dial that standardises the two columns. Turn it:

Try: press ▶ at $t=0$ : forty steps bounce wall to wall and barely move along the trench. Slide $t$ to 1 ( $\kappa$ falls from $1487$ to $10$ ) and press ▶ again — the same forty steps walk straight in.

drag the picture to orbit

how standardised t0

η as share of 2/λ_max0.9

steps30

—

$J(\mathbf w)=\sum_i(\mathbf w^{\top}\mathbf z_i-y_i)^2$ has Hessian $2Z^{\top}Z$ . Re-measuring the columns changes $Z$ , hence the Hessian, hence $\kappa=\lambda_{\max}/\lambda_{\min}$ — but not the model, the data's meaning or the best fit. Standardising removes scale; the leftover tilt is correlation, and removing it (whitening) is Unit 12's job.

At $t=0$ the surface is the trench from the top of the page: stiff wall, soft floor, $\kappa\approx1487$ . Press ▶: forty steps just under the speed limit bounce wall to wall and barely move along the floor. Now slide $t$ to $1$ . The trench opens under your finger into a bowl — a slightly tilted one, $\kappa\approx10$ — and the same forty steps walk nearly straight in. Look at what changed and what did not. The data means exactly what it meant. The model is the same two knobs. The best fit is the same fit, written in new units. Only the units of the columns moved, and $\kappa$ fell by a factor of $145$ , the safe stride grew from $0.0012$ to $0.18$ , and the number of steps to shrink the error a hundredfold along the soft direction fell from thousands to a couple of dozen. This is the cheapest win in all of machine learning, and it is the sentence Sections 4, 5 and 8 were building toward.

Why does standardising land so precisely on the fix? Because the stiffness in each knob is (twice) the sum of squares of its column — the bill feels the columns squared, so a column thirty times bigger is a wall nine hundred times stiffer. Dividing every column by its own spread forces every column's sum of squares to $n$ , so every diagonal stiffness becomes the same $2n$ . The walls are now the same height by construction.

And the leftover tilt? The bowl at $t=1$ still leans, and $\kappa$ is $10$ , not $1$ . The lean comes from the off-diagonal: guns and butter rise and fall together in this data (correlation $-0.82$ ), so the two knobs are not independent, and Section 9's tilted contours are exactly what you see. Scaling equalises the axes; it does not straighten them. Try the whiten preset: standardise and then rotate onto the bowl's own axes, and $\kappa$ becomes exactly $1$ — a perfect round bowl, one step to the bottom. Finding those axes is what Unit 12 is for (it is called PCA); the adaptive strides of the next unit are the practical version of the same wish.

The realization

The least-squares bill has Hessian $H=2X^{\top}X$ : stiffness in knob $j$ is $2\sum_i x_{ij}^2$ , the column's size squared. Standardising makes every column's $\sum_i z_{ij}^2=n$ , so every diagonal becomes $2n$ — the walls level out. On this data: $\kappa\ 1487\to10.2$ , speed limit $2/\lambda_{\max}\ 0.0012\to0.18$ . The off-diagonal $2\sum_i z_{i1}z_{i2}$ — correlation — survives; removing it is whitening, a rotation, not a rescaling.

Pause & predict

You standardise the two columns of the guns-and-butter data. Which of these changes?

Pause & predict

After standardising, $\kappa$ is $10.2$ rather than $1$ . What is the leftover, and which repair would remove it?

If you want the algebra · 2 proofs, step by step

Prove it · the Hessian of least squares is

2X^{\top}X

, and standardising levels its diagonal

Claim. For $J(\mathbf w)=\sum_i(\mathbf w^{\top}\mathbf X_i-y_i)^2$ : $H=2\sum_i\mathbf X_i\mathbf X_i^{\top}=2X^{\top}X$ , with $H_{jj}=2\sum_ix_{ij}^2$ . After standardising, every $H_{jj}=2n$ .

1

From the first drawer,

\nabla J=2\sum_ir_i\mathbf X_i

with

r_i=\mathbf w^{\top}\mathbf X_i-y_i

. Differentiate once more:

\nabla r_i=\mathbf X_i

, so

H=2\sum_i\mathbf X_i\mathbf X_i^{\top}

. The targets

y_i

vanish: the bowl's shape depends only on the features. Its position depends on

y

.

2

Entry by entry:

H_{jk}=2\sum_ix_{ij}x_{ik}

; on the diagonal

H_{jj}=2\sum_ix_{ij}^2

— the column's size, squared. Guns and butter: sums

0.81,\ 14.5,\ 825

give

H=\begin{pmatrix}1.62&29\\29&1650\end{pmatrix}

. A column thirty times bigger is a wall nine hundred times stiffer;

1650/1.62\approx1019

.

3

Standardise:

\sum_iz_{ij}^2=n

for every column (Section 5's drawer), so

H_{jj}=2n=6

. Off-diagonal:

2\sum_iz_{i1}z_{i2}=2(-2.466)=-4.93

.

H_{\text{std}}=\begin{pmatrix}6&-4.93\\-4.93&6\end{pmatrix}

. ∎ The walls are level by construction; the off-diagonal is

2n

times the correlation coefficient (

-0.822

), and it is what keeps

\kappa

at

10.2

rather than

1

.

Prove it · a symmetric 2×2 with equal diagonals has eigenvalues

a\pm b

— so

\kappa

falls from

1487

to

10.2

Claim. The symmetric matrix with equal diagonals $a$ and off-diagonal $b$ has eigenvalues $a+b$ and $a-b$ ; hence $H_{\text{std}}$ has $10.93$ and $1.07$ , $\kappa\approx10.2$ , against $1650.5$ and $1.11$ , $\kappa\approx1487$ , before.

1

\begin{pmatrix}a&b\\b&a\end{pmatrix}\begin{pmatrix}1\\1\end{pmatrix}=(a+b)\begin{pmatrix}1\\1\end{pmatrix}

and

\begin{pmatrix}a&b\\b&a\end{pmatrix}\begin{pmatrix}1\\-1\end{pmatrix}=(a-b)\begin{pmatrix}1\\-1\end{pmatrix}

. Unit 4: two eigenvectors found by inspection — the diagonal directions of the tilted bowl.

2

With

a=6

,

b=-4.93

:

\lambda=1.07,\ 10.93

;

\kappa=10.93/1.07\approx10.2

; speed limit

2/10.93\approx0.183

. The eigenvectors

(1,1)

and

(1,-1)

are exactly the axes whitening rotates onto.

3

Before: for

\begin{pmatrix}1.62&29\\29&1650\end{pmatrix}

,

\lambda=825.81\pm\sqrt{824.19^2+29^2}=1650.51,\ 1.11

;

\kappa\approx1487

; limit

2/1650.5\approx0.00121

. ∎

\kappa

improved

145\times

and the admissible stride

151\times

— and neither the data's meaning, the model, nor the best fit changed.

In one sentence: The bill feels each column squared, so dividing every column by its own spread levels every wall to the same height —

\kappa

collapses, the safe stride explodes, the model and the data's meaning are untouched — and only the tilt of correlation remains, for a rotation to remove.

11

The training clinic — read the loss curve like a doctor

Six patients

A doctor does not see the disease; she sees the chart. You will not see the landscape either — only the loss, step after step. Everything in this unit has a signature on that chart. Six recorded runs, one diagnosis each. Read the curve, name the cause, pick the fix:

Try: case 2 — the train loss falls to $0$ while the test loss turns around at step 25 and climbs. Pick the diagnosis; a right answer overlays the healthy curve the fix would have produced.

—

The toolkit, as a checklist: NaN → overflow (huge start, unscaled features, $\eta$ too big); train $\downarrow$ test $\uparrow$ → overfitting; sawtooth → $\eta>2/\lambda_{\max}$ ; fast-then-crawl → a badly conditioned canyon; flat → plateau or $\eta$ too small; seed-dependent → several minima.

Once you have diagnosed all six, notice that the fixes come in only two families. Reshape the landscape so the plain walk works: scale the features, initialise sensibly, add a penalty on big knobs. That is this unit. Give the walker better instincts: momentum that keeps rolling across a flat, a private stride per knob so the stiff one is not held hostage by the hair-trigger, or a feel for the curvature and not just the slope. That is the next unit. Almost every trick in modern optimisation is one of the two.

The chart says	What is going on	What to do
loss becomes $\infty$ / NaN in a few steps	overflow: huge start or unscaled features	start in $[-1,1]$ ; scale the features; lower $\eta$
training loss $\to0$ , test loss climbs	memorising: more knobs than facts	more data, fewer knobs, a penalty on big knobs, stop early
sawtooth that grows	$\eta>2/\lambda_{\max}$ in the stiff direction	reduce $\eta$ ; standardise
falls fast, then crawls for ever	zig-zag in a canyon (big $\kappa$ )	standardise; momentum, adaptive strides
flat from the very first step	a plateau, a dead start, $\eta$ far too small — or a wrong gradient	raise $\eta$ ; momentum; better start; audit the gradient
different runs, different answers	several valleys, different watersheds	restarts, keep the best — or accept it

Pause & predict

A run's loss goes $12,\ 4,\ 11,\ 5,\ 13,\ 6,\dots$ — a sawtooth that slowly grows. What is wrong, and what is the first thing to try?

In one sentence: Every failure in this unit has a signature on the loss curve — explosion, the train/test scissors, a growing sawtooth, fast-then-crawl, flat from the start, run-to-run lottery — and every fix either reshapes the landscape or gives the walker better instincts.

12

What to carry forward

Four ways the walk goes wrong, one fix that does most of the work, and a picture for each.

The picture	What it says	The line of math it becomes
The tailor's patches	the bill is the area of the squares; each row pushes along itself, by its miss	$\nabla J=2\sum_i(\mathbf w^{\top}\mathbf X_i-y_i)\mathbf X_i$
The parachute drop	land small, central, random; blow-ups come from the units, not the start	$w_0\in[-1,1]$ ; factor $1-2\eta x^2$
Last year's paper	more knobs than facts makes a zero bill free and meaningless	$d>n\Rightarrow$ infinitely many exact fits
Two knobs, one hand	sensitivity is the feature's size squared; no stride serves both	$\partial y/\partial w_j=x_j^2$
The map redrawn	centre slides, standardise squeezes, min–max boxes; use training statistics	$z=(x-\mu)/\sigma$ , $(x-\min)/(\max-\min)$
Rain on a ridge	the watershed decides the valley; valleys multiply like a combination lock	$\prod_i k_i$ minima; $p^d$ ; $1-(1-p)^k$
The salt flat	small tilt, small step — a plateau is not a minimum, just slow	steps $\approx W/(\gamma g)$
Skiing the gully	each direction shrinks by its own factor; the stiffest sets the limit	$1-\eta\lambda_i$ ; $\eta<2/\lambda_{\max}$ ; $\kappa$
The hillside path	the tilt crosses every contour at a right angle; it points at the bottom only on circles	$\nabla F\cdot\delta\mathbf x=0$
Guns and butter	standardising levels every wall to $2n$ ; only correlation's tilt remains	$H=2X^{\top}X$ ; $\kappa\ 1487\to10$
Six patients	every failure has a signature on the loss curve	reshape the landscape, or teach the walker

The one thing to remember

Change the units, not the model. The bill feels every feature squared, so features of different sizes make a canyon: one stride overshoots on the stiff wall and crawls along the soft floor. Standardise the columns and the canyon becomes a bowl — same data, same model, same best fit, a hundred times fewer steps. Then remember the other three: land small and random, judge the model on rows it never saw, and know that the valley you find is the one downhill from where you landed.

13

Practice arena — twelve problems, solved in full

Twelve problems, easy to hard, covering every picture in the unit: the three repairs on a real column and an unseen value, the imbalance one stride creates, the tailor's bill walked and solved, the round bowl against the canyon, standardisation's effect on the gradient and on the Hessian, the least-squares gradient derived and used, knobs versus facts, a walk into the wrong valley, basins and restarts, and the guns-and-butter canyon opened into a bowl. Every number is machine-verified.

Two habits do most of the work: for any stride question, write the per-direction factors first — $1-\eta\lambda_i$ is the whole story of stability, oscillation and speed; and for any scaling question, compute the sums of squares of the columns, because the Hessian of least squares is $2X^{\top}X$ and the feature sizes enter it squared.

Problem 1easy

A feature column holds the five values $\{30,\,50,\,70,\,90,\,110\}$ . (a) Apply min–max scaling $x'=(x-\min)/(\max-\min)$ to all five. (b) Standardise the column (subtract the mean, divide by the population standard deviation) and check that the $z$ -values sum to $0$ and their squares sum to $5$ . (c) A new value $x=130$ arrives later. Transform it under both schemes using the training statistics, and say whether the min–max result lies in $[0,1]$ .

What this tests. Two of the three repairs (standardise, min–max) as plain arithmetic, and the one habit that matters at test time: reuse the training statistics, never recompute them. Plan. Read off min, max and range; then mean, deviations, variance, $\sigma$ ; divide; run the two sanity sums; finally push $130$ through both formulas with the numbers already on the page.

Show the full solution

(a) Step 1 — min–max. Here

\min=30

,

\max=110

, range

=80

:

\begin{aligned} 30&\mapsto\tfrac{0}{80}=0, & 50&\mapsto\tfrac{20}{80}=0.25,\\ 70&\mapsto\tfrac{40}{80}=0.5, & 90&\mapsto\tfrac{60}{80}=0.75,\\ 110&\mapsto\tfrac{80}{80}=1. \end{aligned}

Evenly spaced inputs give evenly spaced outputs — min–max is a pure stretch-and-shift.

(b) Step 2 — mean and deviations.

\begin{aligned} \mu&=\frac{30+50+70+90+110}{5}=\frac{350}{5}=70,\\ x-\mu&=(-40,\,-20,\,0,\,20,\,40). \end{aligned}

Step 3 — variance and standard deviation. Square the deviations and average over

n=5

:

\begin{aligned} \sigma^2&=\frac{1600+400+0+400+1600}{5}\\ &=\frac{4000}{5}=800,\\ \sigma&=\sqrt{800}\approx28.28. \end{aligned}

Step 4 — divide, then check.

z=(x-70)/28.28

:

\begin{aligned} z&=\Big(\tfrac{-40}{28.28},\ \tfrac{-20}{28.28},\ 0,\\ &\qquad\tfrac{20}{28.28},\ \tfrac{40}{28.28}\Big)\\ &=(-1.414,\,-0.707,\,0,\,0.707,\,1.414). \end{aligned}

Sanity sums:

\begin{aligned} \textstyle\sum z&=-1.414-0.707+0+0.707+1.414=0,\\ \textstyle\sum z^2&=2+0.5+0+0.5+2=5=n. \end{aligned}

Both hold, so the column now has mean

0

and variance

5/5=1

. ✓

(c) Step 5 — the unseen value, training statistics only.

\begin{aligned} x'&=\frac{130-30}{80}=\frac{100}{80}=1.25,\\ z&=\frac{130-70}{28.28}=\frac{60}{28.28}\approx2.12. \end{aligned}

1.25

lies outside

[0,1]

: the promise "everything lands in

[0,1]

" was only ever a promise about the training column. The

z

-score

2.12

is unusual (two standard deviations up) but perfectly well defined —

z

-scores are unbounded by design.

(a) $0,\ 0.25,\ 0.5,\ 0.75,\ 1$ . (b) $\mu=70$ , $\sigma\approx28.28$ , $z=(-1.414,-0.707,0,0.707,1.414)$ ; $\sum z=0$ , $\sum z^2=5$ . (c) min–max $1.25$ (outside $[0,1]$ ); $z=2.12$ .

Remember

"Change the units, not the model": both repairs are invertible bookkeeping, and the bookkeeping is done once, on the training column. The slip on this type is recomputing $\min$ , $\max$ , $\mu$ , $\sigma$ with the new point included — that silently changes every training value too. Min–max is fragile to a new extreme; standardisation degrades gracefully.

Problem 2easy

At the current iterate a loss has partial derivatives $\partial J/\partial w_1=-640$ and $\partial J/\partial w_2=-1.6$ , and one learning rate $\gamma=10^{-3}$ serves both knobs. (a) Compute the update to each parameter and the ratio of the two moves. (b) If gradients of this size persist, how many steps does $w_2$ need to move by one unit, and how far does $w_1$ travel in that time? (c) Choose $\gamma$ instead so that $w_1$ moves a modest $0.01$ per step; give the new $\gamma$ , the new $w_2$ move and the new step count for a one-unit move of $w_2$ . (d) State, in one line, what standardising the two feature columns does to the two partials.

What this tests. The hair-trigger knob in pure arithmetic — one stride length, two wildly different slopes — and the cost of protecting either knob at the other's expense. Plan. $\Delta w_j=-\gamma\,\partial J/\partial w_j$ twice; divide $1$ by the small move; scale $\gamma$ down so the big move is $0.01$ and redo the count; then name the repair as a computable claim.

Show the full solution

(a) Step 1 — the two moves.

\begin{aligned} \Delta w_1&=-10^{-3}\,(-640)=0.64,\\ \Delta w_2&=-10^{-3}\,(-1.6)=0.0016,\\ \frac{\Delta w_1}{\Delta w_2}&=\frac{0.64}{0.0016}=400. \end{aligned}

One stride, but a

400:1

imbalance in how far each knob turns.

(b) Step 2 — the slow coordinate.

N\approx\frac{1}{0.0016}=625\ \text{steps}

for

w_2

to move one unit. Meanwhile

w_1

moves

625\times0.64=400\ \text{units}

— long since past its target and bouncing.

(c) Step 3 — protect $w_1$ instead. Require

\gamma\times640=0.01

:

\begin{aligned} \gamma&=\frac{0.01}{640}=1.5625\times10^{-5},\\ \Delta w_2&=1.5625\times10^{-5}\times1.6=2.5\times10^{-5},\\ N&\approx\frac{1}{2.5\times10^{-5}}=40\,000\ \text{steps}. \end{aligned}

The hair-trigger knob is now tame; the stiff knob crawls

64

times more slowly than before.

(d) Step 4 — the repair. After standardising both columns, the two partials come out of the same order of magnitude (a ratio near

1

instead of

400

), so a single

\gamma

serves both knobs — Problem 5 does this arithmetic on real columns and watches

576

turn into

1.07

.

(a) $\Delta w_1=0.64$ , $\Delta w_2=0.0016$ , ratio $400:1$ . (b) $\approx625$ steps, during which $w_1$ moves $400$ units. (c) $\gamma=1.5625\times10^{-5}$ , $\Delta w_2=2.5\times10^{-5}$ , $\approx40\,000$ steps. (d) standardising makes the partials comparable, so one $\gamma$ fits both.

Remember

The stride $\gamma$ is the same for every knob; it is the gradient that differs, so the actual move $\gamma\times$ gradient is what you compare. Serve the slow knob and the fast one oscillates; serve the fast knob and the slow one takes $40\,000$ steps. No choice of $\gamma$ escapes — only changing the units does.

Problem 3easy

Three receipts: $x=(1,2,3)$ , $y=(2,5,7)$ , model $\hat y=wx$ with no intercept. (a) Write the bill for being wrong $J(w)=\sum(wx_i-y_i)^2$ and expand it to the form $aw^2+bw+c$ . (b) Find $w^*$ by setting the slope to zero, confirm it is a minimum, and compute $J(w^*)$ exactly. (c) Run gradient descent from $w_0=0$ with $\eta=0.02$ for five steps, tabulating $w$ , the slope and $J$ . (d) Give the per-step factor $1-\eta\lambda$ and the largest $\eta$ for which the iteration converges.

What this tests. The smallest possible training run, done twice — once by formula, once by feel — and the fact that the two agree. Plan. Expand three squares and add; differentiate; solve; evaluate $J^*$ as a fraction with denominator $14$ ; fill a five-row table; then read the curvature $28$ for the factor and the speed limit $2/28$ .

Show the full solution

(a) Step 1 — write and expand the scorecard.

J(w)=(w-2)^2+(2w-5)^2+(3w-7)^2.

Each square on its own line:

\begin{aligned} (w-2)^2&=w^2-4w+4,\\ (2w-5)^2&=4w^2-20w+25,\\ (3w-7)^2&=9w^2-42w+49. \end{aligned}

Add columns:

\begin{aligned} J(w)&=(1+4+9)w^2-(4+20+42)w+(4+25+49)\\ &=14w^2-66w+78. \end{aligned}

(b) Step 2 — slope zero, curvature positive.

\begin{aligned} \frac{dJ}{dw}&=28w-66=0\\ w^*&=\frac{66}{28}=\frac{33}{14}\approx2.357,\\ \frac{d^2J}{dw^2}&=28>0\ \Rightarrow\ \text{a minimum.} \end{aligned}

Step 3 — the lowest possible bill, exactly. Put everything over

14

:

\begin{aligned} J(w^*)&=14\Big(\tfrac{33}{14}\Big)^2-66\cdot\tfrac{33}{14}+78\\ &=\tfrac{1089}{14}-\tfrac{2178}{14}+\tfrac{1092}{14}\\ &=\tfrac{1089-2178+1092}{14}=\tfrac{3}{14}\approx0.214. \end{aligned}

(

14\cdot33^2/14^2=33^2/14=1089/14

;

66\cdot33=2178

;

78\cdot14=1092

.)

(c) Step 4 — the parachute drop and the walk. Update

w\leftarrow w-0.02\,(28w-66)

, one row per step:

$k$	$w_k$	slope $28w_k-66$	new $w$	$J(w_k)$
0	$0$	$-66$	$0+0.02\cdot66=1.3200$	$78$
1	$1.3200$	$36.96-66=-29.04$	$1.3200+0.5808=1.9008$	$15.27$
2	$1.9008$	$53.22-66=-12.78$	$1.9008+0.2556=2.1564$	$3.13$
3	$2.1564$	$60.38-66=-5.62$	$2.1564+0.1124=2.2688$	$0.78$
4	$2.2688$	$63.53-66=-2.47$	$2.2688+0.0495=2.3183$	$0.32$
5	$2.3183$	$64.91-66=-1.09$	—	$0.24$

Two of the

J

values in full, to see the arithmetic:

\begin{aligned} J(1.3200)&=14(1.7424)-66(1.3200)+78\\ &=24.39-87.12+78=15.27,\\ J(1.9008)&=14(3.6130)-66(1.9008)+78\\ &=50.58-125.45+78=3.13. \end{aligned}

The slope column shrinks every step:

66\to29\to13\to5.6\to2.5\to1.1

. Descent naturally decelerates as it nears the floor, and the limit is

w=2.357

,

J=0.214

— the formula's answer, reached by feel.

(d) Step 5 — the per-direction factor and the speed limit. Subtract

w^*

from both sides of the update:

\begin{aligned} w_{k+1}-w^*&=w_k-w^*-\eta\,(28w_k-66)\\ &=(1-28\eta)(w_k-w^*). \end{aligned}

With

\eta=0.02

the factor is

1-0.56=0.44

: the distance to

w^*

is multiplied by

0.44

each step (check:

2.357-1.320=1.037

;

0.44\times2.357=1.037

✓). Convergence needs

|1-28\eta|<1

, i.e.

0<\eta<\frac{2}{28}=\frac{1}{14}\approx0.0714.

At

\eta=1/28

the factor is

0

and one step finishes; between

1/28

and

1/14

the iterates alternate sides of

w^*

; beyond

1/14

they blow up.

(a) $J(w)=14w^2-66w+78$ . (b) $w^*=33/14\approx2.357$ , $J''=28>0$ , $J^*=3/14\approx0.214$ . (c) $w:0,1.320,1.901,2.156,2.269,2.318$ ; $J:78,15.27,3.13,0.78,0.32,0.24$ . (d) factor $1-28\eta=0.44$ ; converges for $\eta<1/14\approx0.0714$ .

Remember

For one knob the formula wins; the walk exists because for a billion knobs there is no formula. Keep the table — point, slope, new point, $J$ — and check it against the closed form: the gap to $w^*$ must shrink by exactly $1-\eta\lambda$ each row. The slip is evaluating $J$ at the new $w$ but writing it in the old row.

Problem 4easy

Two bowls: the circle $L=x^2+y^2$ and the canyon $L=x^2+4y^2$ . (a) For the circle, write both gradient-descent updates as multiplications by a constant factor and give the $\eta$ that sends every starting point to $(0,0)$ in one step. (b) For the canyon, write the two factors, find the range of $\eta$ for which the iteration is stable, and say which coordinate sets it. (c) Trace $\eta=0.24$ from $(10,10)$ for three steps, with $L$ at each point. (d) Give the Hessian and the condition number $\kappa$ , and the two per-step factors that explain the trace.

What this tests. The canyon problem in its cleanest form — same convexity, same minimiser, and yet one bowl is easy and the other bounces off the walls. Plan. Gradient, factor per coordinate; the one-step $\eta$ is where a factor hits $0$ ; stability is $|1-\eta\lambda|<1$ for the larger $\lambda$ ; then multiply through a table and read the signs of the two factors.

Show the full solution

(a) Step 1 — the circle.

\nabla L=(2x,\,2y)

, so

\begin{aligned} x&\leftarrow x-\eta(2x)=(1-2\eta)\,x,\\ y&\leftarrow y-\eta(2y)=(1-2\eta)\,y. \end{aligned}

Both coordinates shrink by the same factor. Choose

\eta=0.5

:

1-2(0.5)=0

, so

(x,y)\to(0,0)

in a single step from anywhere. The gradient points straight at the centre because the contours are circles.

(b) Step 2 — the canyon.

\nabla L=(2x,\,8y)

, so

\begin{aligned} x&\leftarrow(1-2\eta)\,x,\\ y&\leftarrow(1-8\eta)\,y. \end{aligned}

Stability needs each factor inside

(-1,1)

:

\begin{aligned} |1-2\eta|<1&\ \Rightarrow\ 0<\eta<1,\\ |1-8\eta|<1&\ \Rightarrow\ 0<\eta<0.25. \end{aligned}

The

y

-coordinate, with

\partial^2L/\partial y^2=8

, sets the ceiling

\eta<0.25

— even though

x

would happily accept a stride four times longer.

(c) Step 3 — trace $\eta=0.24$ . Factors:

x

:

1-0.48=0.52

;

y

:

1-1.92=-0.92

.

$k$	point	gradient $(2x,8y)$	new point	$L=x^2+4y^2$
0	$(10,\,10)$	$(20,\,80)$	$(5.2,\,-9.2)$	$100+400=500$
1	$(5.2,\,-9.2)$	$(10.4,\,-73.6)$	$(2.704,\,8.464)$	$27.04+338.56=365.6$
2	$(2.704,\,8.464)$	$(5.408,\,67.71)$	$(1.406,\,-7.787)$	$7.31+286.56=293.9$
3	$(1.406,\,-7.787)$	—	—	$1.98+242.55=244.5$

The new points come straight from the factors:

0.52\times10=5.2

,

-0.92\times10=-9.2

;

0.52\times5.2=2.704

,

-0.92\times(-9.2)=8.464

;

0.52\times2.704=1.406

,

-0.92\times8.464=-7.787

.

(d) Step 4 — Hessian, $\kappa$ , and what the trace shows.

H=\begin{bmatrix}2&0\\0&8\end{bmatrix},\qquad\kappa=\frac{8}{2}=4.

In three steps

x

has gone

10\to1.4

(factor

0.52

each time, monotone);

y

has gone

10\to-9.2\to8.5\to-7.8

, flipping sign every step and losing only

8\%

of its size each time (factor

-0.92

). Most of the motion is sideways across the canyon, not down it —

L

fell only from

500

to

244.5

.

(a) $x\leftarrow(1-2\eta)x$ , $y\leftarrow(1-2\eta)y$ ; $\eta=0.5$ finishes in one step. (b) factors $1-2\eta$ , $1-8\eta$ ; stable for $0<\eta<0.25$ , set by $y$ . (c) $(5.2,-9.2)$ , $(2.704,8.464)$ , $(1.406,-7.787)$ ; $L=500,365.6,293.9,244.5$ . (d) $H=\operatorname{diag}(2,8)$ , $\kappa=4$ ; factors $0.52$ and $-0.92$ .

Remember

Everything about the canyon is in two numbers, the per-direction factors $1-\eta\lambda_i$ : the largest $\lambda$ caps $\eta$ at $2/\lambda_{\max}$ , a negative factor means zig-zag, and $\kappa=\lambda_{\max}/\lambda_{\min}$ is the difficulty score. Answer "why is the canyon slow?" with the two factors, not with prose.

Problem 5medium

House price $y$ is modelled as $\hat y=w_1x_1+w_2x_2$ from area $x_1=(1000,1500,2000)$ and bedroom count $x_2=(2,3,3)$ , with $y=(50,75,90)$ and $J(\mathbf w)=\sum_i(w_1x_{i1}+w_2x_{i2}-y_i)^2$ . (a) Compute $\partial J/\partial w_1$ and $\partial J/\partial w_2$ at $\mathbf w=(0,0)$ , and their ratio. (b) Standardise both columns (population $\sigma$ ) and recompute both partials at $\mathbf w=(0,0)$ . (c) Give the new ratio.

What this tests. Knobs and units: the feature scale multiplies straight into the gradient, and standardising both columns brings the two partials to the same order of magnitude. Plan. At $\mathbf w=0$ every prediction is $0$ , so each partial is $-2\sum y_ix_{ij}$ ; compute the two sums; then $\mu,\sigma,z$ for each column; redo the two sums with $z$ in place of $x$ ; divide.

Show the full solution

(a) Step 1 — raw partials at the origin. With

r_i=\hat y_i-y_i

, the chain rule gives

\partial J/\partial w_j=2\sum_ir_ix_{ij}

. At

\mathbf w=0

all

\hat y_i=0

, so

r_i=-y_i

and

\partial J/\partial w_j=-2\sum_iy_ix_{ij}

:

\begin{aligned} \frac{\partial J}{\partial w_1}&=-2\big[1000(50)+1500(75)\\ &\qquad+2000(90)\big]\\ &=-2\,[50\,000+112\,500+180\,000]\\ &=-2\,(342\,500)=-685\,000,\\ \frac{\partial J}{\partial w_2}&=-2\big[2(50)+3(75)+3(90)\big]\\ &=-2\,[100+225+270]\\ &=-2\,(595)=-1190. \end{aligned}

Ratio:

\frac{685\,000}{1190}\approx576.

The bill is about

576

times more sensitive to

w_1

, purely because square feet are numerically huge.

(b) Step 2 — standardise $x_1$ .

\begin{aligned} \mu_1&=\frac{1000+1500+2000}{3}=1500,\\ x_1-\mu_1&=(-500,\,0,\,500),\\ \sigma_1&=\sqrt{\frac{250\,000+0+250\,000}{3}}\\ &=\sqrt{166\,667}\approx408.25,\\ z_1&=(-1.2247,\,0,\,1.2247). \end{aligned}

Step 3 — standardise $x_2$ .

\begin{aligned} \mu_2&=\frac{2+3+3}{3}=\frac{8}{3}\approx2.667,\\ x_2-\mu_2&=(-0.667,\,0.333,\,0.333),\\ \sigma_2&=\sqrt{\frac{0.4444+0.1111+0.1111}{3}}\\ &=\sqrt{0.2222}\approx0.4714,\\ z_2&=(-1.4142,\,0.7071,\,0.7071). \end{aligned}

Step 4 — the partials again, with $z$ in place of $x$ .

\begin{aligned} \frac{\partial J}{\partial w_1}&=-2\big[(-1.2247)(50)+0(75)\\ &\qquad+(1.2247)(90)\big]\\ &=-2\,[-61.24+0+110.22]\\ &=-2\,(48.99)=-97.98,\\ \frac{\partial J}{\partial w_2}&=-2\big[(-1.4142)(50)+(0.7071)(75)\\ &\qquad+(0.7071)(90)\big]\\ &=-2\,[-70.71+53.03+63.64]\\ &=-2\,(45.96)=-91.92. \end{aligned}

(c) Step 5 — the new ratio.

\frac{97.98}{91.92}\approx1.07.

From

576

to

1.07

: the two knobs now feel the same stride in the same way, so one

\gamma

drives both at similar speeds — no oscillation in

w_1

while

w_2

crawls.

(a) $-685\,000$ and $-1190$ , ratio $\approx576$ . (b) $z_1=(-1.2247,0,1.2247)$ , $z_2=(-1.4142,0.7071,0.7071)$ ; partials $-97.98$ and $-91.92$ . (c) ratio $\approx1.07$ .

Remember

At $\mathbf w=0$ the gradient is $-2\sum y_ix_{\cdot j}$ , so a column's scale multiplies straight into its partial. Quote the before/after ratio — $576\to1.07$ — as the whole result. The slip is using the sample $\sigma$ (dividing by $n-1$ ) when the population $\sigma$ was asked for; the $z$ 's then change by $\sqrt{2/3}$ .

Problem 6medium

Consider $L(x,y)=9x^2+y^2$ . (a) Write the gradient-descent updates as multiplications by constant factors and find the exact range of $\eta$ for convergence, naming the coordinate that sets it. (b) With $\eta=0.1$ , trace three steps from $(1,3)$ ; say which coordinate oscillates and give the threshold of $\eta$ above which it does. (c) Give the Hessian and $\kappa$ ; give the $\eta$ that finishes in one step on the equal-curvature bowl $9x^2+9y^2$ , and the two values of $\eta$ that one-step convergence would need simultaneously on $L$ .

What this tests. The canyon again with the stiff direction along $x$ this time — checking you read the factors from the curvatures and not from habit. Plan. $\nabla L=(18x,2y)$ ; factors $1-18\eta$ , $1-2\eta$ ; stability from the larger curvature; multiply through three rows; then $\kappa=18/2$ and the one-step condition $1-\eta\lambda=0$ .

Show the full solution

(a) Step 1 — decoupled updates.

\nabla L=(18x,\,2y)

, so

\begin{aligned} x_{k+1}&=(1-18\eta)\,x_k,\\ y_{k+1}&=(1-2\eta)\,y_k. \end{aligned}

Stability needs both factors inside

(-1,1)

:

\begin{aligned} |1-18\eta|<1&\ \Rightarrow\ \eta<\tfrac{2}{18}=\tfrac{1}{9},\\ |1-2\eta|<1&\ \Rightarrow\ \eta<1. \end{aligned}

The stiff direction is

x

(curvature

18

), so the range is

0<\eta<\tfrac19\approx0.111.

(b) Step 2 — trace $\eta=0.1$ . Factors:

x

:

1-1.8=-0.8

;

y

:

1-0.2=0.8

.

$k$	point	gradient $(18x,2y)$	new point	$L$
0	$(1,\,3)$	$(18,\,6)$	$(-0.8,\,2.4)$	$9+9=18$
1	$(-0.8,\,2.4)$	$(-14.4,\,4.8)$	$(0.64,\,1.92)$	$5.76+5.76=11.52$
2	$(0.64,\,1.92)$	$(11.52,\,3.84)$	$(-0.512,\,1.536)$	$3.686+3.686=7.373$
3	$(-0.512,\,1.536)$	—	—	$2.359+2.359=4.719$

Both coordinates lose

20\%

of their size per step, but

x

flips sign every time: its factor is negative because

\eta=0.1

exceeds

1/18\approx0.056

, the value at which

1-18\eta

crosses zero. Each step overshoots the floor in the stiff direction and lands on the opposite wall;

y

descends monotonically. (The two halves of

L

stay equal because

9x^2

and

y^2

both shrink by

0.64

per step.)

(c) Step 3 — Hessian, $\kappa$ , the ideal bowl.

H=\begin{bmatrix}18&0\\0&2\end{bmatrix},\qquad\kappa=\frac{18}{2}=9.

Descent is fastest when curvature is equal in every direction,

\kappa=1

: on

9x^2+9y^2

both factors are

1-18\eta

, so

\eta=1/18

makes both zero and every start reaches

(0,0)

in one step. On

L

itself one-step convergence would need

1-18\eta=0

and

1-2\eta=0

, i.e.

\eta=1/18

and

\eta=1/2

at once — impossible with a single stride.

(a) $x\leftarrow(1-18\eta)x$ , $y\leftarrow(1-2\eta)y$ ; $0<\eta<1/9\approx0.111$ , set by $x$ . (b) $(-0.8,2.4)$ , $(0.64,1.92)$ , $(-0.512,1.536)$ ; $x$ oscillates (factor $-0.8$ ) because $\eta>1/18\approx0.056$ ; $y$ descends (factor $0.8$ ). (c) $H=\operatorname{diag}(18,2)$ , $\kappa=9$ ; $\eta=1/18$ finishes $9x^2+9y^2$ in one step; $L$ would need $1/18$ and $1/2$ simultaneously.

Remember

Three thresholds per direction: $\eta<1/\lambda$ smooth, $\eta=1/\lambda$ one-step, $1/\lambda<\eta<2/\lambda$ zig-zag, beyond that blow-up. The largest $\lambda$ owns the speed limit, the smallest owns the crawl, and $\kappa$ is their ratio. The slip is putting the stiff factor on $y$ out of habit — read it from the coefficient.

Problem 7medium

For the least-squares bill $J(\mathbf w)=\sum_{i=1}^n(\mathbf w^{\top}X_i-y_i)^2$ : (a) derive $\nabla J(\mathbf w)=2\sum_i(\mathbf w^{\top}X_i-y_i)\,X_i$ . (b) For $X_1=(2,1)$ , $y_1=4$ , $X_2=(1,3)$ , $y_2=5$ , compute $J$ and $\nabla J$ at $\mathbf w_0=(0,0)$ , take one step with $\gamma=0.02$ , and compute the new residuals and $J_1$ ; give the fraction of the loss removed.

What this tests. The engine behind every gradient in this unit — residual times feature vector, summed — derived once and then run once. Plan. Name the residual $r_i$ , differentiate the square by the chain rule, note $\nabla r_i=X_i$ ; then residuals at the origin, two scaled vectors added, one update, two new residuals, compare.

Show the full solution

(a) Step 1 — the chain rule. Write

J=\sum_ir_i^2

with

r_i=\mathbf w^{\top}X_i-y_i

. Since

\mathbf w^{\top}X_i

is linear in

\mathbf w

, its gradient is the vector

X_i

, and

y_i

is a constant:

\nabla_{\mathbf w}r_i=X_i.

Differentiate each square:

\begin{aligned} \nabla J&=\sum_i2r_i\,\nabla_{\mathbf w}r_i\\ &=2\sum_i(\mathbf w^{\top}X_i-y_i)\,X_i. \end{aligned}

Reading: each row pulls

\mathbf w

along its own feature vector, in proportion to its current error.

(b) Step 2 — at the origin. Predictions are

0

, so

\begin{aligned} r_1&=0-4=-4, & r_2&=0-5=-5,\\ J_0&=16+25=41. \end{aligned}

The gradient:

\begin{aligned} \nabla J(\mathbf w_0)&=2\big[(-4)(2,1)+(-5)(1,3)\big]\\ &=2\big[(-8,-4)+(-5,-15)\big]\\ &=2\,(-13,\,-19)=(-26,\,-38). \end{aligned}

Step 3 — one step.

\begin{aligned} \mathbf w_1&=(0,0)-0.02\,(-26,-38)\\ &=(0.52,\ 0.76). \end{aligned}

Step 4 — verify the drop. New residuals:

\begin{aligned} r_1&=0.52(2)+0.76(1)-4\\ &=1.04+0.76-4=-2.20,\\ r_2&=0.52(1)+0.76(3)-5\\ &=0.52+2.28-5=-2.20,\\ J_1&=(-2.2)^2+(-2.2)^2=4.84+4.84=9.68. \end{aligned}

9.68<41

✓. Fraction removed:

\frac{41-9.68}{41}=\frac{31.32}{41}\approx0.76,

i.e.

76\%

of the bill in a single step.

(a) $\nabla J=2\sum_i(\mathbf w^{\top}X_i-y_i)X_i$ . (b) $r=(-4,-5)$ , $J_0=41$ , $\nabla J=(-26,-38)$ , $\mathbf w_1=(0.52,0.76)$ , new $r=(-2.20,-2.20)$ , $J_1=9.68$ ; $76\%$ removed.

Remember

"Residual times feature vector, summed" is the whole gradient; restricting the sum to a sample gives the mini-batch version, and Problem 5's arithmetic is this formula at $\mathbf w=0$ . Watch the sign convention: with $r_i=\hat y_i-y_i$ the formula is $+2\sum r_iX_i$ and the minus sign lives in the update; with $r_i=y_i-\hat y_i$ it moves into the gradient.

Problem 8medium

Knobs versus facts. Three rows $(x_1,x_2,x_3,x_4,y)$ : $(61,2,3,0.1,59)$ , $(40,0,4,0.5,40)$ , $(68,0,10,1.0,70)$ ; the model has five knobs, $\hat y=w_1x_1+w_2x_2+w_3x_3+w_4x_4+w_5$ , and the real-world truth is $y\approx x_1$ . (a) For the honest model $\mathbf w=(1,0,0,0,0)$ give the three predictions, the three errors and $J$ . (b) The memoriser sets $w_1=w_4=0$ and hits all three rows exactly using $w_2,w_3,w_5$ : write the three equations, solve them, and give its $J$ . (c) Check the candidate $\mathbf w=(0,7,5,0,20)$ : compute its row-1 prediction and its $J$ . (d) On an unseen row $x=(50,1,6,0.3)$ with true $y\approx50$ , give both models' predictions and errors. (e) Count unknowns and equations for the full model, and state how many free parameters remain in the set of zero-error solutions.

What this tests. Overfitting as arithmetic: more knobs than facts means zero training error is always available and means nothing. Plan. Honest model first (three subtractions); then a $3\times3$ linear system by elimination; then plug the candidate into row 1 and recompute $J$ ; then one unseen row through both models; finally the count $5-3$ .

Show the full solution

(a) Step 1 — the honest model $\hat y=x_1$ .

row	$\hat y=x_1$	$y$	error $\hat y-y$	squared
1	$61$	$59$	$+2$	$4$
2	$40$	$40$	$0$	$0$
3	$68$	$70$	$-2$	$4$

J=4+0+4=8.

Close to zero, not zero.

(b) Step 2 — the memoriser's three equations. With

w_1=w_4=0

, row by row:

\begin{aligned} 2w_2+3w_3+w_5&=59 &&\text{(row 1)}\\ 4w_3+w_5&=40 &&\text{(row 2)}\\ 10w_3+w_5&=70 &&\text{(row 3)} \end{aligned}

Row 3 minus row 2 kills

w_5

:

\begin{aligned} 10w_3-4w_3&=70-40\\ 6w_3&=30\\ w_3&=5. \end{aligned}

Into row 2:

4(5)+w_5=40\ \Rightarrow\ w_5=20.

Into row 1:

\begin{aligned} 2w_2+3(5)+20&=59\\ 2w_2+35&=59\\ 2w_2&=24\\ w_2&=12. \end{aligned}

So the memoriser is

\hat y=12x_2+5x_3+20

. Check all three rows:

24+15+20=59

✓,

20+20=40

✓,

50+20=70

✓. Its

J=0

exactly.

(c) Step 3 — the candidate $(0,7,5,0,20)$ . Row 1:

7(2)+5(3)+20=14+15+20=49\neq59.

Rows 2 and 3 do not involve

w_2

and are still exact. So

J=(49-59)^2+0+0=(-10)^2=100,

not

0

: that triple is not a zero-error solution,

w_2=12

is.

(d) Step 4 — one unseen row.

x=(50,1,6,0.3)

, truth

y\approx50

:

\begin{aligned} \text{honest:}\quad\hat y&=x_1=50, & \text{error}&=0,\\ \text{memoriser:}\quad\hat y&=12(1)+5(6)+20\\ &=12+30+20=62, & \text{error}&=12. \end{aligned}

Perfect on the three training rows, off by

12

on the first row it has never seen — it was memorising with variables that have nothing to do with the answer.

(e) Step 5 — the count. The full model has

5

unknowns; the data supply

3

equations (one per row). Three independent equations in five unknowns leave

5-3=2

free parameters: the zero-error solutions form a two-parameter family — infinitely many of them — and the optimiser hands you one of them with no idea which is meaningful. The memoriser of (b) is the member with

w_1=w_4=0

.

(a) $\hat y=(61,40,68)$ , errors $(2,0,-2)$ , $J=8$ . (b) $w_3=5$ , $w_5=20$ , $w_2=12$ ; $J=0$ . (c) row 1 gives $49$ , so $J=100$ . (d) honest $50$ (error $0$ ); memoriser $62$ (error $12$ ). (e) $5$ unknowns, $3$ equations, $2$ free parameters — infinitely many zero-error solutions.

Remember

More knobs than facts $\Rightarrow$ zero training error is available $\Rightarrow$ zero training error means nothing; judge on a row the model has not seen. Solve the small system honestly — a plausible-looking triple like $(7,5,20)$ is one row-1 check away from being exposed. Regularisation later makes the memoriser (weights $12,5,20$ ) expensive and the honest model (weight $1$ ) cheap.

Problem 9medium

Let $F(x)=(x-1)^2\big((x-3)^2-1\big)$ . (a) Find $F'(x)$ in factored and expanded form, and all stationary points. (b) Classify them with $F''$ and give $F$ at each. (c) Run gradient descent from $x_0=0.5$ with $\eta=0.02$ for four steps, tabulating $x$ , $F'$ and $F$ ; state the limit and which starting points end there. (d) On a plateau where $|F'|=0.001$ , with $\eta=0.01$ , give the step length and the number of steps to cross a plateau of width $2$ .

What this tests. One knob, two valleys: the walk converges beautifully into the wrong one and never gets a hint the other exists; plus the salt-flat arithmetic. Plan. Product rule, pull out $2(x-1)$ , quadratic formula; $F''$ at three points; four table rows with the expanded $F'$ ; then step $=\eta|F'|$ and divide the width by it.

Show the full solution

(a) Step 1 — product rule. With

u=(x-1)^2

,

v=(x-3)^2-1

:

u'=2(x-1)

,

v'=2(x-3)

, so

\begin{aligned} F'&=u'v+uv'\\ &=2(x-1)\big[(x-3)^2-1\big]+(x-1)^2\cdot2(x-3)\\ &=2(x-1)\big[(x-3)^2-1+(x-1)(x-3)\big]. \end{aligned}

Simplify the bracket:

\begin{aligned} (x-3)^2-1&=x^2-6x+8,\\ (x-1)(x-3)&=x^2-4x+3,\\ \text{sum}&=2x^2-10x+11. \end{aligned}

Hence

F'(x)=2(x-1)(2x^2-10x+11).

Expanded:

\begin{aligned} F'&=2\,(2x^3-10x^2+11x-2x^2+10x-11)\\ &=2\,(2x^3-12x^2+21x-11)\\ &=4x^3-24x^2+42x-22. \end{aligned}

Step 2 — stationary points. Either

x=1

, or

2x^2-10x+11=0

:

\begin{aligned} x&=\frac{10\pm\sqrt{100-88}}{4}=\frac{10\pm\sqrt{12}}{4}\\ &=\frac{10\pm2\sqrt3}{4}=\frac{5\pm\sqrt3}{2}. \end{aligned}

Numerically

1.634

and

3.366

. Three stationary points:

x=1,\ 1.634,\ 3.366

.

(b) Step 3 — curvature and depth.

F''(x)=12x^2-48x+42

:

\begin{aligned} F''(1)&=12-48+42=6>0,\\ F''(1.634)&=32.04-78.43+42=-4.39<0,\\ F''(3.366)&=135.96-161.57+42=16.39>0. \end{aligned}

So

x=1

is a minimum,

1.634

a maximum,

3.366

a minimum. Values:

\begin{aligned} F(1)&=0^2\cdot(4-1)=0,\\ F(1.634)&=(0.634)^2\big[(-1.366)^2-1\big]\\ &=0.4020\times0.866=0.348,\\ F(3.366)&=(2.366)^2\big[(0.366)^2-1\big]\\ &=5.598\times(-0.866)=-4.848. \end{aligned}

The valley at

x=1

has floor

0

; the valley at

3.366

has floor

-4.848

. The watershed between them is the hilltop at

1.634

.

(c) Step 4 — the walk from $x_0=0.5$ . Update

x\leftarrow x-0.02\,F'(x)

:

$k$	$x_k$	$F'(x_k)$	new $x$	$F(x_k)$
0	$0.5000$	$-6.500$	$0.5+0.1300=0.6300$	$1.3125$
1	$0.6300$	$-4.065$	$0.63+0.0813=0.7113$	$0.6321$
2	$0.7113$	$-2.829$	$0.7113+0.0566=0.7679$	$0.3532$
3	$0.7679$	$-2.089$	$0.7679+0.0418=0.8097$	$0.2146$
4	$0.8097$	—	—	$0.1376$

The first row in full:

\begin{aligned} F'(0.5)&=4(0.125)-24(0.25)+42(0.5)-22\\ &=0.5-6+21-22=-6.5,\\ F(0.5)&=(-0.5)^2\big[(-2.5)^2-1\big]\\ &=0.25\times5.25=1.3125. \end{aligned}

|F'|

shrinks every step — the walk decelerates as it nears a floor — and the limit is

x=1

,

F=0

. It reports success while

F=-4.848

existed the whole time. Every start below the watershed

1.634

ends at

x=1

; only a start above it finds the good valley.

(d) Step 5 — the salt flat. Step length

=\eta|F'|

:

\begin{aligned} \text{step}&=0.01\times0.001=10^{-5},\\ \text{steps}&=\frac{2}{10^{-5}}=200\,000. \end{aligned}

Not at a minimum, just on level ground, inching.

(a) $F'=2(x-1)(2x^2-10x+11)=4x^3-24x^2+42x-22$ ; stationary at $1$ , $(5-\sqrt3)/2\approx1.634$ , $(5+\sqrt3)/2\approx3.366$ . (b) $F''=6$ (min, $F=0$ ), $-4.39$ (max, $F\approx0.348$ ), $16.39$ (min, $F\approx-4.848$ ). (c) $x=0.5,0.630,0.7113,0.7679,0.8097$ ; $F=1.3125,0.6321,0.3532,0.2146,0.1376$ ; limit $x=1$ , $F=0$ , for every start below $1.634$ . (d) step $10^{-5}$ ; $200\,000$ steps.

Remember

The watershed is the local maximum between the valleys; which side of it the parachute lands decides everything, and the walk itself carries no information about the other valley. The plateau arithmetic is the same deceleration seen at a true minimum, happening far from one. The slip is calling the deeper valley "the answer" — descent from $0.5$ never sees it.

Problem 10hard

For $F(x)=3x^4-4x^3-12x^2+5$ , small-step gradient descent converges to the local minimum at $x=-1$ from any start $x_0<0$ and to the global minimum at $x=2$ from any start $x_0>0$ ; the watershed sits at $x=0$ . Verify these three facts from $F'$ and the values $F(-1)$ , $F(2)$ , $F(0)$ . The start $x_0$ is drawn uniformly from $[-2,3]$ . (a) Compute the probability that a single run finds the global minimum. (b) With $k$ independent restarts (keep the best), find the smallest $k$ for which the global minimum is found with probability at least $0.99$ , and give that probability. (c) If a separable ten-dimensional objective has this landscape in every coordinate (per-coordinate success $0.6$ , independent), compute the chance that one run lands in the global basin of all ten coordinates at once.

What this tests. Basins as lengths, restarts as "at least one success", and the combination lock: probabilities multiply across coordinates just as basins do. Plan. Factor $F'$ and evaluate $F$ at the three roots; favourable length over total length; $1-0.4^k\ge0.99$ with powers computed exactly; then $0.6^{10}$ .

Show the full solution

Step 1 — the landscape.

\begin{aligned} F'(x)&=12x^3-12x^2-24x\\ &=12x\,(x^2-x-2)\\ &=12x\,(x-2)(x+1). \end{aligned}

Roots

-1,\,0,\,2

. Values:

\begin{aligned} F(-1)&=3+4-12+5=0,\\ F(0)&=5,\\ F(2)&=48-32-48+5=-27. \end{aligned}

F''(x)=36x^2-24x-24

:

F''(-1)=36>0

,

F''(0)=-24<0

,

F''(2)=72>0

. So

x=-1

is a local minimum (floor

0

),

x=0

the hilltop between the valleys (the watershed),

x=2

the global minimum (floor

-27

). Left of

0

the slope pushes toward

-1

; right of

0

toward

2

.

(a) Step 2 — one run. Success needs

x_0>0

(the single point

x_0=0

has probability zero under a continuous draw). Favourable length over total length:

p=\frac{3-0}{3-(-2)}=\frac{3}{5}=0.6.

(b) Step 3 — restarts. One run fails with probability

0.4

; all

k

fail with probability

0.4^k

. Require

1-0.4^k\ge0.99\iff0.4^k\le0.01.

Compute the powers exactly:

\begin{aligned} 0.4^5&=0.01024>0.01\quad\text{(fails)},\\ 0.4^6&=0.004096\le0.01\quad\text{(works)}. \end{aligned}

So

k=6

, with success probability

1-0.004096=0.995904\approx0.9959

. Five restarts just miss at

1-0.01024=0.98976

.

(c) Step 4 — ten dials at once. By independence,

P=0.6^{10}=0.0060466\approx0.006,

about

0.6\%

. With per-coordinate odds well above a half, joint success collapses exponentially — the combination lock has

2^{10}=1024

settings here and only one opens the door.

$F'=12x(x-2)(x+1)$ ; $F(-1)=0$ , $F(0)=5$ , $F(2)=-27$ . (a) $p=3/5=0.6$ . (b) $0.4^5=0.01024$ fails, $0.4^6=0.004096$ works: $k=6$ , success $\approx0.9959$ . (c) $0.6^{10}\approx0.006$ .

Remember

"At least one success in $k$ tries" is $1-(1-p)^k$ ; compute the powers precisely, because these numbers are built so that $k=5$ barely fails. Basins multiply across coordinates, so probabilities multiply too — restarts rescue one dial, not a lock with ten.

Problem 11hard

Guns and butter: $x_1=(0.1,0.8,0.4)$ , $x_2=(25,10,10)$ , $y=(7,1,4)$ , model $\hat y=w_1x_1+w_2x_2$ , $J=\sum(\hat y_i-y_i)^2$ . (a) Write $J(\mathbf w)$ out, compute the Hessian $H=2\begin{bmatrix}\sum x_1^2&\sum x_1x_2\\\sum x_1x_2&\sum x_2^2\end{bmatrix}$ , its eigenvalues, $\kappa$ and the speed limit $2/\lambda_{\max}$ . (b) Standardise both columns (population $\sigma$ ), recompute the three sums, $H_{\mathrm{std}}$ , its eigenvalues, $\kappa$ and $2/\lambda_{\max}$ . (c) Give the improvement factors in $\kappa$ and in the admissible stride, and compute the correlation coefficient of the two columns that explains why $\kappa$ is $10$ and not $1$ .

What this tests. Bad scaling and bad curvature meeting: feature scales enter the Hessian squared, standardising forces both diagonals to $2n$ , and what is left over is correlation. Plan. Three sums, double them; eigenvalues from the $2\times2$ formula; then $\mu,\sigma,z$ per column, the three sums again, $a\pm b$ eigenvalues; divide before by after; finally $\sum z_1z_2/n$ .

Show the full solution

(a) Step 1 — the bill, written out.

\begin{aligned} J(\mathbf w)&=(0.1w_1+25w_2-7)^2\\ &\quad+(0.8w_1+10w_2-1)^2\\ &\quad+(0.4w_1+10w_2-4)^2. \end{aligned}

Its second derivatives are

2\sum x_{i1}^2

,

2\sum x_{i2}^2

and

2\sum x_{i1}x_{i2}

.

Step 2 — the three sums and $H$ .

\begin{aligned} \textstyle\sum x_1^2&=0.01+0.64+0.16=0.81,\\ \textstyle\sum x_2^2&=625+100+100=825,\\ \textstyle\sum x_1x_2&=2.5+8+4=14.5. \end{aligned}

\begin{aligned} H&=2\begin{bmatrix}0.81&14.5\\14.5&825\end{bmatrix}\\ &=\begin{bmatrix}1.62&29\\29&1650\end{bmatrix}. \end{aligned}

Step 3 — eigenvalues, $\kappa$ , speed limit. For a symmetric

\begin{bmatrix}p&q\\q&s\end{bmatrix}

,

\lambda=\tfrac{p+s}{2}\pm\sqrt{\big(\tfrac{s-p}{2}\big)^2+q^2}

:

\begin{aligned} \tfrac{p+s}{2}&=\tfrac{1651.62}{2}=825.81,\\ \tfrac{s-p}{2}&=\tfrac{1648.38}{2}=824.19,\\ \lambda&=825.81\pm\sqrt{824.19^2+29^2}\\ &=825.81\pm\sqrt{679\,289+841}\\ &=825.81\pm824.70, \end{aligned}

so

\lambda_{\max}\approx1650.5

,

\lambda_{\min}\approx1.11

. Then

\begin{aligned} \kappa&=\frac{1650.5}{1.11}\approx1487,\\ \frac{2}{\lambda_{\max}}&=\frac{2}{1650.5}\approx0.00121. \end{aligned}

A canyon about

\sqrt{1487}\approx39

times longer than it is wide, and a stride capped near

10^{-3}

in the

w_1

direction, whose curvature is only

1.62

.

(b) Step 4 — standardise the guns column.

\begin{aligned} \mu_1&=\tfrac{0.1+0.8+0.4}{3}=\tfrac{1.3}{3}=0.4333,\\ x_1-\mu_1&=(-0.3333,\,0.3667,\,-0.0333),\\ \sigma_1^2&=\tfrac{0.1111+0.1344+0.0011}{3}=0.0822,\\ \sigma_1&=\sqrt{0.0822}=0.2867,\\ z_1&=(-1.163,\,1.279,\,-0.116). \end{aligned}

Step 5 — standardise the butter column.

\begin{aligned} \mu_2&=\tfrac{25+10+10}{3}=\tfrac{45}{3}=15,\\ x_2-\mu_2&=(10,\,-5,\,-5),\\ \sigma_2^2&=\tfrac{100+25+25}{3}=\tfrac{150}{3}=50,\\ \sigma_2&=\sqrt{50}=7.071,\\ z_2&=(1.414,\,-0.707,\,-0.707). \end{aligned}

Step 6 — the three sums again.

\begin{aligned} \textstyle\sum z_1^2&=1.352+1.635+0.014=3.000,\\ \textstyle\sum z_2^2&=2.000+0.500+0.500=3.000,\\ \textstyle\sum z_1z_2&=-1.644-0.904+0.082=-2.466. \end{aligned}

The first two are exactly

3=n

— dividing a column by its own

\sigma

forces

\sum z^2=n

, so every diagonal entry of the Hessian becomes

2n

.

H_{\mathrm{std}}=\begin{bmatrix}6&-4.93\\-4.93&6\end{bmatrix}.

Equal diagonal, so the eigenvalues are

a\pm b

:

\begin{aligned} \lambda&=6\pm4.93=10.93,\ 1.07,\\ \kappa&=\frac{10.93}{1.07}\approx10.2,\\ \frac{2}{\lambda_{\max}}&=\frac{2}{10.93}\approx0.183. \end{aligned}

(c) Step 7 — the improvement, and what is left.

\begin{aligned} \frac{\kappa_{\text{raw}}}{\kappa_{\text{std}}}&=\frac{1487}{10.2}\approx145,\\ \frac{0.183}{0.00121}&\approx151. \end{aligned}

About

145\times

in

\kappa

and

151\times

in the admissible stride, without touching the model, the algorithm or the data's meaning. The leftover

\kappa=10.2

comes from the off-diagonal

-4.93

: the columns are correlated,

\rho=\frac{\sum z_1z_2}{n}=\frac{-2.466}{3}\approx-0.822.

Scaling equalises the axes; it does not decorrelate them, so the contours stay tilted. Removing the tilt is what PCA-whitening is for.

(a) $H=\begin{bmatrix}1.62&29\\29&1650\end{bmatrix}$ ; $\lambda\approx1650.5,\,1.11$ ; $\kappa\approx1487$ ; $2/\lambda_{\max}\approx0.00121$ . (b) $z_1=(-1.163,1.279,-0.116)$ , $z_2=(1.414,-0.707,-0.707)$ ; sums $3,3,-2.466$ ; $H_{\mathrm{std}}=\begin{bmatrix}6&-4.93\\-4.93&6\end{bmatrix}$ ; $\lambda=10.93,\,1.07$ ; $\kappa\approx10.2$ ; $2/\lambda_{\max}\approx0.183$ . (c) $\approx145\times$ in $\kappa$ , $\approx151\times$ in stride; $\rho\approx-0.822$ .

Remember

Standardising forces every diagonal of $H$ to $2n$ ; whatever $\kappa$ survives is correlation, read off the off-diagonal. Two handy facts: eigenvalues of $\begin{bmatrix}a&b\\b&a\end{bmatrix}$ are $a\pm b$ , and for general $2\times2$ symmetric use mean $\pm$ half-difference-and- $q$ . The slip is forgetting the factor $2$ in $H$ and so in $2/\lambda_{\max}$ .

Problem 12hard

A linear model $\hat y=w_1x_1+w_2x_2$ is trained on $x_1=(100,500,900)$ and $x_2=(0.9,0.3,0.6)$ , with $J=\sum(\hat y_i-y_i)^2$ and Hessian $H=2\sum_iX_iX_i^{\top}$ . (a) Compute $H$ , its eigenvalues (use $\lambda_{\min}=\det H/\lambda_{\max}$ ), the largest stable stride $\gamma_{\max}=2/\lambda_{\max}$ and $\kappa$ . (b) Min–max normalise both columns, recompute $H'$ , its eigenvalues, $\gamma'_{\max}$ and $\kappa'$ . (c) By what factor did the admissible stride improve?

What this tests. The grand synthesis: a $10^3$ gap in feature scale becomes a $10^6$ gap in curvature, which caps the stride at $10^{-6}$ ; min–max scaling buys it back. Plan. Three sums, double them; $\lambda_{\max}\approx H_{11}$ because the off-diagonal is tiny in comparison, $\lambda_{\min}$ from the determinant; then scale, three new sums, $a\pm b$ ; divide the two strides.

Show the full solution

(a) Step 1 — raw sums and $H$ .

\begin{aligned} \textstyle\sum x_1^2&=10^4+25\times10^4+81\times10^4\\ &=107\times10^4=1\,070\,000,\\ \textstyle\sum x_1x_2&=90+150+540=780,\\ \textstyle\sum x_2^2&=0.81+0.09+0.36=1.26. \end{aligned}

\begin{aligned} H&=2\begin{bmatrix}1\,070\,000&780\\780&1.26\end{bmatrix}\\ &=\begin{bmatrix}2.14\times10^6&1560\\1560&2.52\end{bmatrix}. \end{aligned}

Step 2 — eigenvalues, stride, $\kappa$ . The off-diagonal

1560

is tiny next to

2.14\times10^6

, so

\lambda_{\max}\approx H_{11}=2.14\times10^6

. The other eigenvalue comes from the determinant:

\begin{aligned} \det H&=(2.14\times10^6)(2.52)-1560^2\\ &=5\,392\,800-2\,433\,600=2\,959\,200,\\ \lambda_{\min}&=\frac{\det H}{\lambda_{\max}}=\frac{2\,959\,200}{2.14\times10^6}\approx1.38. \end{aligned}

Then

\begin{aligned} \gamma_{\max}&=\frac{2}{2.14\times10^6}\approx9.3\times10^{-7},\\ \kappa&=\frac{2.14\times10^6}{1.38}\approx1.6\times10^6. \end{aligned}

Any stride above

\sim10^{-6}

blows up, and at

10^{-6}

the

w_2

direction (curvature

1.38

) moves by a factor

1-1.38\times10^{-6}

per step — glacially.

(b) Step 3 — min–max both columns. Column 1:

\min=100

, range

800

; column 2:

\min=0.3

, range

0.6

:

\begin{aligned} x_1'&=\Big(\tfrac{0}{800},\tfrac{400}{800},\tfrac{800}{800}\Big)=(0,\,0.5,\,1),\\ x_2'&=\Big(\tfrac{0.6}{0.6},\tfrac{0}{0.6},\tfrac{0.3}{0.6}\Big)=(1,\,0,\,0.5). \end{aligned}

Step 4 — the new Hessian.

\begin{aligned} \textstyle\sum x_1'^2&=0+0.25+1=1.25,\\ \textstyle\sum x_1'x_2'&=0+0+0.5=0.5,\\ \textstyle\sum x_2'^2&=1+0+0.25=1.25. \end{aligned}

H'=2\begin{bmatrix}1.25&0.5\\0.5&1.25\end{bmatrix}=\begin{bmatrix}2.5&1\\1&2.5\end{bmatrix}.

Equal diagonal, so

\lambda=a\pm b

:

\begin{aligned} \lambda&=2.5\pm1=3.5,\ 1.5,\\ \gamma'_{\max}&=\frac{2}{3.5}\approx0.571,\\ \kappa'&=\frac{3.5}{1.5}\approx2.33. \end{aligned}

(c) Step 5 — the improvement.

\frac{\gamma'_{\max}}{\gamma_{\max}}=\frac{0.571}{9.3\times10^{-7}}\approx6\times10^5.

The stride grew by roughly six orders of magnitude, and

\kappa

fell from

\sim10^6

to

2.33

— the quantitative content of "scale your features before descending".

(a) $H=\begin{bmatrix}2.14\times10^6&1560\\1560&2.52\end{bmatrix}$ ; $\lambda_{\max}\approx2.14\times10^6$ , $\lambda_{\min}\approx1.38$ ; $\gamma_{\max}\approx9.3\times10^{-7}$ ; $\kappa\approx1.6\times10^6$ . (b) $x_1'=(0,0.5,1)$ , $x_2'=(1,0,0.5)$ ; $H'=\begin{bmatrix}2.5&1\\1&2.5\end{bmatrix}$ ; $\lambda=3.5,1.5$ ; $\gamma'_{\max}\approx0.571$ ; $\kappa'\approx2.33$ . (c) $\approx6\times10^5$ .

Remember

Feature scales enter $H$ squared, so a $10^3$ scale gap is a $10^6$ curvature gap and a $10^{-6}$ speed limit. Scaling is not cosmetic; it is a computable $10^5$ – $10^6\times$ speed-up. For a nearly diagonal $2\times2$ , $\lambda_{\max}\approx$ the big diagonal entry and $\lambda_{\min}=\det/\lambda_{\max}$ — never read $\lambda_{\min}$ off the small diagonal entry ( $2.52$ , not $1.38$ ).

Next up

Unit 11 · Optimization II — Five Ways Down One Valley →

You reshaped the ground; Unit 11 reshapes the walker. Memory so that agreeing pushes stack and flapping ones cancel, a private stride per knob built from its own history, and forgetting so that history never becomes a life sentence — momentum, AdaGrad, RMSProp and Adam, raced on one valley. Then someone builds a wall, the answer moves onto it with the gradient still tilted, and a whole new test has to be built: the Lagrangian as a fine, complementary slackness, the five KKT conditions, and the dual that prices the wall from the other side.

← All units