Unit 10 · Optimization I — Gradients that Work

1

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

Imagine this

Your local tailor uses one rule of thumb for sleeves: sleeve length = w × arm length. He picks a number for w and cuts three sleeves. Each one comes out a little too long or a little too short.

Now a strange rule. For every miss, he must buy a square patch of cloth whose side is the size of the miss. Miss by 1 cm: a 1 cm² patch. Miss by 3 cm: a 9 cm² patch.

His bill is the total area of the patches. His job is to find the w that makes the bill as small as possible. Keep this picture: the formula below is exactly this sentence.

Every model makes guesses. Every guess misses the truth by some amount. We need one number that says how bad all the misses are, taken together. We call it the bill. Mathematicians call it the loss and write it $J$ .

The most common bill is the tailor's: square each miss, then add them up. Squares are a good choice for three plain reasons:

①Short or long costs the same. $(-3)^2=3^2=9$ .
②One big miss hurts more than many small ones. One miss of 3 costs 9. Three misses of 1 cost only 3.
③Squares are smooth. So "which way is downhill" is easy to work out.

A tiny example. Three customers have arms of length 1, 2 and 3. They need sleeves of 2, 5 and 7. Start with $w=0$ , so every sleeve is 0. The misses are $-2,-5,-7$ , and the bill is $4+25+49=78$ .

Write the bill for any $w$ and it tidies up into one curve:

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

It is a U-shaped curve. Its lowest point is at $w^*=33/14\approx2.357$ (read $w^*$ as "w-star, the best w"). There the bill is $3/14\approx0.214$ . It is not zero, because no line of the form $y=wx$ passes through all three points.

Which way is downhill? The slope of the bill is $dJ/dw=28w-66$ (read it: "how fast the bill changes when you nudge w"). At $w=0$ it is $-66$ . Negative slope means: raise $w$ and the bill falls.

Now look where the $-66$ comes from. Each customer pushes with "2 × my miss × my arm length": $2\big[(-2)(1)+(-5)(2)+(-7)(3)\big]=2(-33)=-66$ . That pattern works for one knob or a billion. Each row of data pushes the knobs along its own row, in proportion to its miss. Add the pushes and you get the gradient, $\nabla J$ (read it: "grad J", the list of slopes, one per knob):

\nabla J=2\sum_i\text{miss}_i\,\mathbf X_i,\qquad \text{miss}_i=\mathbf w^{\top}\mathbf X_i-y_i.

Then comes the walk from Unit 9: step against the slope, $w\leftarrow w-\eta\times\text{slope}$ . Here $\eta$ (read "eta") is your stride. With $\eta=0.02$ the knob goes $0\to1.32\to1.90\to2.16$ , and the bill falls $78\to15.3\to3.1\to0.8$ .

Each step shrinks the gap to the best $w$ by the same factor, $1-28\eta=0.44$ . Push $\eta$ above $1/14\approx0.071$ and that factor drops below $-1$ . Then every step overshoots by more than it gains, and the patches grow. Remember this limit. The whole unit is about what sets it.

Try: drag $w$ towards $2.36$ and watch all three patches shrink. Press ▶ descend: the rod swings in hops and the bill falls $78\to15.3\to3.1\to0.8$ . Then push $\eta$ past $0.0714$ and press ▶ again: the patches grow.

drag the picture to orbit

knob w0

stride η0.02

—

$J(w)=14w^2-66w+78$ has slope $28w-66$ , zero at $w^*=33/14$ . Each step multiplies the gap to $w^*$ by $1-28\eta$ , so the walk settles only while $\eta<1/14$ .

The realization

The bill is the total area of the patches: $J=\sum_i\text{miss}_i^2$ . Its slope is every row's push, added up: $\nabla J=2\sum_i\text{miss}_i\,\mathbf X_i$ .

A row that guessed too high pushes the knobs down along itself. A row that guessed too low pushes them up. A bigger miss pushes harder.

Pause & predict

Right now ( $w=0$ ) every sleeve is too short: the misses are $-2$ , $-5$ and $-7$ . Which way should the knob $w$ move?

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

.

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

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:

\begin{aligned}\nabla\,r_i^2&=2r_i\,\nabla r_i=2r_i\mathbf X_i,\\ \nabla J&=2\sum_i r_i\mathbf X_i.\end{aligned}

∎ 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:

\small\begin{aligned}(w-2)^2&=w^2-4w+4\\ (2w-5)^2&=4w^2-20w+25\\ (3w-7)^2&=9w^2-42w+49\\ J&=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 bill is the total area of one square patch per data row, and its slope is each row's miss times that row, added up — the same recipe for one knob or a billion.

2

The parachute drop — where you start

Imagine this

You check into a hotel and step into the shower. The tap is very touchy. The water is too cold, so you turn the tap a bit. Now it is boiling, and further from comfortable than before. You turn it back a bit. Now it is icy, and further off again.

Every correction makes things worse. Would it help to start with the tap somewhere else? No. The problem is how touchy the tap is, not where it started.

And a second story. You hire two new cooks. You give them the same station, the same first dish and the same feedback every day. They will cook exactly the same thing, forever. You paid for two cooks and got one.

Before the walk can begin, someone must choose where it starts: the first values of the knobs. Two things can go wrong, and they are the two stories above.

Problem 1: the numbers blow up. Take one feature $x=200$ , a target $y=7$ , a start $w_0=1$ and a small-looking stride $\eta=0.001$ . The first guess is $\hat y=w_0x=200$ , a miss of $193$ .

Follow the miss from step to step. Each step multiplies it by the same number:

\text{new miss}=(1-2\eta x^2)\times\text{old miss}.

Here $2\eta x^2=2\times0.001\times40\,000=80$ , so the factor is $1-80=-79$ . The miss goes $193\to-15\,247\to1\,204\,513\to\cdots$ , flipping sign and growing 79 times each step. That is the touchy shower tap, in numbers.

After 163 steps the number passes $1.8\times10^{308}$ , the largest a computer can store (in the usual "float64" format). It becomes $\infty$ , then $\infty-\infty$ , which is NaN: "not a number". The run is dead.

Now notice what is not in the factor: the start $w_0$ . Changing the start changes nothing. The culprit is the feature's size, squared. The only safe stride is below $1/x^2=2.5\times10^{-5}$ , or you must shrink $x$ itself (Sections 4, 5 and 10 show how).

So the advice for the start is modest: pick small numbers, in $[-1,1]$ (or $[0,1]$ if the knobs must stay positive). A small start does not prevent a blow-up. It just does not add to one.

Problem 2: clones. Two knobs that play the same role, started at the same value, feel the same tilt at every step. So they stay equal forever, like the two cooks. The fix is to start them at random values. Randomness costs nothing, and it is the only thing that lets identical knobs become different.

Try: Press ▶ and watch each bar grow 79 times taller, until the computer runs out of numbers. Then slide log₁₀ η below −4.6: the same start now settles down.

log₁₀ |w₀|1

log₁₀ η0.001

—

Each step multiplies the miss by $1-2\eta x^2$ . The start is not in that factor; the size of $x$ is.

The realization

Start small, centred and random: small so the first step stays on the map, random so no two knobs are clones.

And when the numbers explode anyway, look at the factor $1-2\eta x^2$ . It is the size of the data, not your start, that needs fixing.

Pause & predict

With $x=200$ and $\eta=0.001$ , every start blows up. 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

:

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

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: start small 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 started.

3

Full marks by memorising — knobs versus facts

Imagine this

Two students prepare for a maths test. Meera learns how to solve the problems. Arjun memorises last year's answer key.

By chance, this year's test repeats last year's three questions. Arjun scores 100. Meera scores 96. On paper, Arjun is better.

Next week a new question arrives. Meera works it out. Arjun writes down an answer from the key, and it has nothing to do with the question. A score on questions you have already seen tells you nothing about learning.

A model can do exactly what Arjun did. The lecture's data has three rows and four features, $x_1$ to $x_4$ . The truth is simple: $y\approx x_1$ .

row	$x_1$	$x_2$	$x_3$	$x_4$	true $y$
1	61	2	3	0.1	59
2	40	0	4	0.5	40
3	68	0	10	1	70

The model has five knobs: one weight per feature, $w_1$ to $w_4$ , plus a constant $w_5$ .

The learner sets $w_1=1$ and the rest to 0. It says $\hat y=x_1$ (read $\hat y$ as "y-hat, the guess"). Its misses are $2,\ 0,\ -2$ , so its bill is $4+0+4=8$ .

The memoriser ignores $x_1$ completely. It uses $\hat y=12x_2+5x_3+20$ . Check row 1: $24+15+20=59$ . Row 2: $0+20+20=40$ . Row 3: $0+50+20=70$ . Every row is hit exactly, so its bill is $0$ .

Ask any optimiser for "the smallest bill", and it will pick the memoriser without a second thought.

Now try a new row it has never seen: $x_1=50$ , $x_2=1$ , $x_3=6$ , $x_4=0.3$ . The truth is about 50. The learner says 50. The memoriser says $12+30+20=62$ , off by 12. And if you change $x_1$ , the memoriser does not even notice: $x_1$ is not in its formula.

How was a zero bill even possible? Count. Five knobs, only three facts. Three equations with five unknowns have endlessly many exact solutions. It is like being told "two numbers add up to 10": you cannot tell which two.

So the data never pinned the knobs down. The optimiser handed back one of the many exact fits, with no way to know which one means something. The learner's bill of 8 is not a failure. It is the size of the noise in the three rows. Chasing that 8 down to 0 is where learning turned into memorising.

Try: Switch to the memoriser: it hits all three training dots exactly. Now drag the unseen row: the truth moves, but the memoriser stays stuck at $62$ .

unseen x₁50

—

Three rows, five knobs: two knobs are left free, so an exact fit costs nothing. Only a row the model has never seen can tell learning from memorising.

The realization

More knobs than facts means a zero training bill is free, so a zero training bill means nothing. Judge a model on rows it has never seen.

Later units add a small charge for big knobs (a regulariser). Then "fits the data with small knobs" beats "fits the data with any knobs", and the learner wins.

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. You train it on $6$ rows, and the training bill comes out exactly $0$ . How pleased should you be?

Pause & predict

You drag the unseen row from $x_1=50$ to $x_1=70$ (the truth is now about $70$ ). 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 so means nothing — the memoriser hits every training row and still cannot see the one feature that matters.

4

The hair-trigger and the stiff knob

Imagine this

You are filling two buckets from two taps. But both taps are on one handle: every turn opens both by the same amount.

Tap A is a fire hose. A tiny turn floods the floor. Tap B is a slow drip. Turn gently to keep A under control, and B's bucket takes all day. Turn hard to fill B, and A sprays everywhere.

No single turn suits both taps. The problem is not your hand. It is that the two taps have very different pressures.

Gradient descent has exactly one handle: the stride $\eta$ . Every knob gets the same stride. But the knobs can have very different "pressures".

The lecture's model predicts wealth from age $x_1$ and years of college $x_2$ :

y=w_1x_1^2+w_2x_2^2.

How much does the guess change when you nudge a knob? For $w_1$ it changes by $x_1^2$ . For $w_2$ it changes by $x_2^2$ . That is each knob's sensitivity, its pressure. Mathematicians write it $\partial y/\partial w_1$ (read: "how fast y changes when only $w_1$ moves").

A tiny example. Take a typical person: age $x_1=50$ , college $x_2=4$ . The sensitivities are $50^2=2500$ and $4^2=16$ . So the age knob is $2500/16\approx156$ times touchier than the college knob.

With a stride of $\eta=10^{-5}$ , one unit of miss moves the age knob by $0.025$ and the college knob by only $0.00016$ . The college knob needs about 6,250 steps to move one unit. The age knob gets there in 40.

Try to fix it with the stride alone. Protect the age knob, and the college knob crawls. Serve the college knob, and the age knob overshoots and swings. No stride suits both, because the problem is not the stride. It is the size of the features: age goes up to 100, college only up to 10, and the bill feels those sizes squared.

The only real fix is to make the two features the same size. That is the next section.

Try: Press serve the stiff knob, then ▶: the age needle swings past its mark. Now press protect the hair-trigger: the college needle barely moves in 8 steps.

age x₁50

college x₂4

log₁₀ η1e−5

—

The age knob is $x_1^2/x_2^2$ times touchier than the college knob, yet both get the same stride. Only making the features the same size fixes it.

The realization

A knob's sensitivity is its feature's size, squared: $\partial y/\partial w_j=x_j^2$ . One stride moves knob $j$ by $\eta\,x_j^2\times|\text{miss}|$ .

So features of different sizes make one knob overshoot while another crawls. No stride can serve both. Rescaling the features is the fix.

Pause & predict

This step, the slopes are $\partial J/\partial w_1=-640$ and $\partial J/\partial w_2=-1.6$ . One stride $\gamma=10^{-3}$ serves both. How far does each knob move? And about how many steps does $w_2$ need to move 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 fire hose on one knob and a drip on the other — and only rescaling the features can fix it.

5

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

Imagine this

You scored 80 out of 100 in the maths test and 9 out of 10 in a weekly quiz. Which did you do better on?

You cannot compare 80 with 9 directly. So you ask a better question: how far above the class average am I, measured in "typical gaps"?

Maths: class average 60, typical gap 10. You are $(80-60)/10=2$ gaps above. Quiz: class average 8, typical gap 0.5. You are $(9-8)/0.5=2$ gaps above. Equally good. You just put both marks on the same scale.

That is exactly how we fix the features. We re-measure each column so that all columns are the same size. Nothing about the data's meaning changes; only its units do. There are three common ways.

Repair	In everyday words	In symbols
Centre	"Above or below average?" Subtract the column's average. The cloud of points slides onto the origin; its shape stays the same.	$x-\mu$
Standardise	"How many typical gaps from average?" Subtract the average, then divide by the spread. Every column now has spread 1.	$z=\dfrac{x-\mu}{\sigma}$
Min–max	"What fraction of the way from lowest to highest?" Every column is squeezed into a box from 0 to 1.	$\dfrac{x-\min}{\max-\min}$

Here $\mu$ (read "mu") is the column's average, and $\sigma$ (read "sigma") is its spread, the standard deviation: the typical gap from the average.

A tiny example. A column holds $30,50,70,90,110$ . Its average is $\mu=70$ and its spread is $\sigma\approx28.28$ . Standardised, the values become $-1.414,\,-0.707,\,0,\,0.707,\,1.414$ . Min–max turns them into $0,\,0.25,\,0.5,\,0.75,\,1$ .

One firm rule. A new value must be treated with the training numbers. Say $130$ arrives later. Standardise it with the old $\mu$ and $\sigma$ : $z=(130-70)/28.28\approx2.12$ . Min–max it with the old min and max: $(130-30)/80=1.25$ , outside the box. Never recompute the average with the new value included. That quietly leaks test data into training.

Which to use? Standardising is the usual default before gradient descent. Min–max is simple and bounded, but one wild value (an outlier) sets the box and squashes everyone else into a corner. Try the outlier cloud below.

Try: Click standardise: the long smear becomes a round blob. Then pick cloud + one outlier and click min–max: one point grabs the corner and squashes the rest.

unseen x₁0.9

—

Every repair uses the training average, spread, min and max, and new data must use the same numbers. After standardising, one unit means "one typical gap" in every column.

The realization

Rescaling changes the units, not the meaning. After standardising, every column has average $0$ and $\sum_i z_i^2=n$ , so every column is the same size and one stride can serve every knob.

What rescaling does not fix: two columns that rise and fall together. That leftover comes back in Section 10.

Pause & predict

A training column has average $\mu=40$ , spread $\sigma=8$ , smallest value $20$ and largest $60$ . A new value $x=72$ arrives. What do standardising and min–max give?

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: centring slides, standardising squeezes, min–max boxes — all three put every column on the same scale, and all three treat new data with the training numbers.

6

The wrong valley — the watershed and the combination lock

Imagine this

Monsoon rain falls on the Western Ghats. A drop that lands just west of the crest flows down to the Arabian Sea. A drop that lands a few metres east travels hundreds of kilometres to the Bay of Bengal.

Where each drop ends up was decided the moment it landed, by which side of the crest it hit. The crest is called the watershed. Once a drop starts rolling, it never climbs back over.

Gradient descent is a raindrop. It only ever rolls downhill from wherever it starts.

So far our bills have had one valley. Real bills can have several. The lecture's curve is

F(x)=(x-1)^2\big((x-3)^2-1\big).

It has a shallow valley at $x=1$ (height $0$ ) and a deep valley at $x\approx3.37$ (height $\approx-4.85$ ). Between them is a small hilltop, the watershed, at $x\approx1.63$ .

A walker that starts left of $1.63$ rolls into the shallow valley and stops. It reports "done", with a valley almost five units deeper right next door. It never had a clue.

A tiny example. Drop marbles evenly between $0$ and $4$ . The share that lands right of the watershed is $(4-1.634)/4\approx0.59$ . So about 59 % reach the deep valley. The walk did not choose that number. The drop zone did.

The obvious fix: restart a few times and keep the best. Each drop misses the deep valley with chance $0.41$ . Six drops all miss with chance $0.41^6\approx0.005$ . So six restarts succeed more than 99 % of the time. On a line, this works.

With many knobs, it stops working. Think of a combination lock. Suppose each knob, on its own, has 3 dips to settle in. With 10 knobs there is a dip for every combination: $3^{10}=59{,}049$ of them. Only one is the true bottom.

Now suppose each knob lands in its best dip with chance $0.6$ . A single run must be lucky on all ten at once: $0.6^{10}\approx0.006$ , about one run in 165. Restarts alone cannot search that. (Large neural networks are kinder than this worst case: most of their valleys turn out to be about equally good.)

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

drag the picture to orbit

starts from0

starts to4

marbles24

stride η0.02

—

A marble only rolls downhill, so it never climbs the watershed: the start alone picks the lake. With $d$ knobs of $k$ dips each there are $k^d$ dips, far too many for restarts to search.

The realization

Descent finds the valley downhill from where it starts, and the watershed decides which one. Restarts give $k$ chances: all fail with probability $(1-p)^k$ .

With $d$ knobs of $k$ dips each, the dips multiply to $k^d$ , and the chance of being right on every knob shrinks to $p^d$ .

Pause & predict

Marbles are dropped evenly on $[0,4]$ . The watershed is at $x=1.634$ . What share reaches the deep valley? And how many drops give a $99\,\%$ chance of at least one success?

Pause & predict

A bill splits into $10$ separate one-knob pieces. Each piece has $3$ dips, and one of them is its best. A random start lands in each knob's best dip with chance $0.6$ . How many dips does the whole bill have? And what is the chance that one run lands in the best dip 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\\ &\quad+(x-1)^2\cdot2(x-3)\\ &=2(x-1)\big[(x-3)^2-1\\ &\qquad+(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: the side of the watershed you start on decides the valley you reach, and with many knobs the valleys multiply like the settings of a combination lock — so restarts alone cannot save you.

7

The salt flat — where the walk slows to nothing

Imagine this

You are walking in the Rann of Kutch at night, in thick fog. You want to reach the lowest point, and your only guide is the slope under your feet. Your rule: the steeper the ground, the bigger your step.

Coming down the rocky edge, the slope is steep, so you take big strides. Then you step onto the white salt flat. It is almost perfectly level. Your feet feel almost no slope, so your steps become tiny.

You are not at the bottom. You are just on flat ground, and you shuffle across it for hours.

A flat stretch of the bill, far from any valley, is called a plateau. On a plateau, gradient descent slows to a crawl for a simple reason. Each step is stride × tilt. Small tilt, small step.

A tiny example. The tilt is $0.001$ and the stride is $0.01$ . Each step moves $0.01\times0.001=10^{-5}$ . A flat stretch two units wide takes $2/10^{-5}=200{,}000$ steps. That can be hours of computing, spent getting nowhere.

In symbols: crossing a flat of width $W$ where the tilt is about $g$ takes roughly $W/(\gamma g)$ steps ( $\gamma$ , read "gamma", is the stride).

Unit 9 showed the same slowing near the bottom of a valley. There it is welcome: you are where you want to be. On a plateau it is a trap. The walker slows down for the same reason, in a place that deserves no slowing.

Try: Press ▶ from the cliff. The footprints are far apart on the slope, then pile up into a bright band on the flat, where every step is tiny.

drag the picture to orbit

stride γ0.3

steps300

—

Step = stride × tilt. On the flat the tilt is tiny, so the walker is slow — not finished.

The realization

Step length is stride × tilt: $\gamma\,|\nabla f|$ . Small tilt means small steps, whether or not you are near a valley. A flat of width $W$ and tilt $g$ costs about $W/(\gamma g)$ steps.

The cure comes next unit: momentum, which keeps rolling across the flat instead of deciding every footstep afresh.

Pause & predict

For $500$ steps the bill has barely moved: $6.00,\ 5.99,\ 5.99,\ 5.98,\dots$ Which conclusion is wrong?

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: each step is stride times tilt, so a plateau — small tilt, but no valley — can swallow hundreds of thousands of steps.

8

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

Imagine this

Drop a marble into a long, narrow rain gutter that tilts gently toward one end.

Does it roll neatly along to the end? No. The sides of the gutter are much steeper than its length. So the marble rocks from wall to wall, and only slowly drifts along.

Every movement is downhill. Most of them go sideways.

That gutter is the most common shape of a bill in machine learning. We call it a canyon: steep across, gentle along. The simplest one is

L(x,y)=x^2+c\,y^2.

The number $c$ says how much steeper the walls are than the floor. With $c=1$ you get a round bowl. With $c=4$ , the walls are four times steeper.

Each direction behaves on its own. One step of descent multiplies each coordinate by its own factor:

x\leftarrow(1-2\eta)\,x,\qquad y\leftarrow(1-2c\eta)\,y.

A tiny example. Take $c=4$ , $\eta=0.24$ , and start at $(10,10)$ . The factors are $1-0.48=0.52$ for $x$ and $1-1.92=-0.92$ for $y$ . After one step you are at $(5.2,-9.2)$ . Then $(2.70,8.46)$ , then $(1.41,-7.79)$ .

Look at $y$ . The minus sign flips it to the other wall every step, and it shrinks only 8 % each time. Meanwhile $x$ halves every step. After six steps $x$ is about $0.2$ , nearly solved, while $y$ is still about $6$ . That bouncing is the zig-zag.

Why not pick a better stride? The steep wall only stays under control while $|1-2c\eta|<1$ , that is $\eta<1/c$ . Go past that and $y$ blows up. But at that limit, the floor factor is $1-2/c$ . For a very steep wall, that is close to 1: the floor crawls.

Serve the wall and the floor crawls. Serve the floor and the wall blows up. This is the one-handle tap from Section 4 again, drawn as a landscape.

Naming the pieces. The steepness of the bill along a direction is its curvature, written $\lambda$ (read "lambda"). Here $\lambda=2$ along the floor and $\lambda=2c$ across the walls. The steepest direction sets the speed limit, $\eta<2/\lambda_{\max}$ . And the ratio of steepest to gentlest,

\kappa=\frac{\lambda_{\max}}{\lambda_{\min}}\quad(\text{read "kappa"}),

is the condition number. It says how badly the floor crawls at the speed limit. $\kappa=1$ is a round bowl, where one step of $\eta=0.5$ lands exactly on the bottom. A big $\kappa$ is a canyon and a long zig-zag.

Try: Press ▶ at $c=4$ , $\eta=0.24$ : $y$ flips to the other wall every step while $x$ creeps in. Then set $c=1$ and $\eta=0.5$ : one step lands on the bottom.

drag the picture to orbit

stiffness c4

stride η0.24

steps8

—

Each direction has its own factor: $1-2\eta$ along the floor, $1-2c\eta$ across the walls. The steep wall sets the limit $\eta<1/c$ .

The realization

Each direction shrinks by its own factor, $1-\eta\lambda$ . The steepest direction sets the speed limit, $\eta<2/\lambda_{\max}$ . At that limit the gentlest direction crawls, and $\kappa=\lambda_{\max}/\lambda_{\min}$ measures how badly.

Steepest descent is the best direction for this one step, never the best direction for the whole trip.

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 misbehaves?

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 each direction shrinks by its own factor $1-\eta\lambda$ , the steepest wall sets the speed limit, and $\kappa$ , steepest over gentlest, tells you how much of the walk is wasted bouncing.

9

Why the compass crosses the contour lines at a right angle

Imagine this

In the tea gardens of Munnar, the paths between the bushes run level around the hillside. Walk along one and you never climb or drop.

Stand on such a path and ask: which way is straight up the hill? Not along the path; that stays level. Straight across it, at a right angle.

Every tea picker knows this without a formula.

On a map, those level paths are contour lines: lines joining points of equal height. The gradient is the "straight up" direction. And it always crosses the contour at exactly $90^\circ$ .

Why? For a tiny move, the change in height is "tilt dotted with the move" (Unit 8), that is $\nabla F\cdot\delta\mathbf x$ . Along a contour the height does not change, so that dot product is zero. A zero dot product means a right angle.

The payoff. On a round bowl the contours are circles. "Straight across a circle" points at its centre, which is the bottom. So the gradient aims right at the answer. That is why the round bowl of Section 8 finished in one step.

On a stretched bowl the contours are ovals. Straight across an oval does not point at its centre. A tiny example: on $F=x^2+4y^2$ at the point $(2.2,1.1)$ , the gradient is $(4.4,8.8)$ . The straight line to the bottom points along $(2.2,1.1)$ . The angle between them is about $37^\circ$ . That gap is the zig-zag.

On a tilted bowl the ovals are also turned. Even after you fix the scale of each axis, a gap remains. That tilt comes from features that move together, and it is the one thing the next section's fix does not remove.

Try: Drag the point around the oval. The gradient always meets the contour at $90^\circ$ , but it points up to about $37^\circ$ away from the bottom. Switch to circle: the two arrows line up.

—

Moving along a contour does not change the height, so the gradient is at right angles to it. On a circle that points at the centre; on an oval it does not.

The realization

Along a contour the height does not change, so $\nabla F\cdot\delta\mathbf x=0$ : the gradient is at right angles to every contour.

It points at the bottom only when the contours are circles. On ovals, the angle between "steepest" and "towards the bottom" is the zig-zag.

Pause & predict

On $F=x^2+4y^2$ at the point $(2.2,\,1.1)$ : what angle does the gradient make with the contour? And with the straight line to the bottom?

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 gradient crosses every contour at a right angle — which points at the bottom only when the contours are circles.

10

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

Imagine this

A friend sends you a photo of a round steel thali. But your phone's app has stretched it: thirty times wider than it is tall. On your screen, the plate is a thin silver line.

Nothing about the plate is thin. Only the display is. Fix the aspect ratio and the round plate comes back.

A canyon-shaped bill is often exactly this: a round-ish bowl, drawn in badly mismatched units.

The lecture's data: three countries, two features each, and a happiness score to predict.

country	guns per person $x_1$	butter per person $x_2$	happiness $y$
A	0.1	25	7
B	0.8	10	1
C	0.4	10	4

The butter numbers are about thirty times bigger than the gun numbers. Remember Section 4: the bill feels each feature's size squared. So the butter wall is about a thousand times steeper than the gun wall.

The numbers. A column's steepness is 2 × the sum of its squares. Guns: $2(0.01+0.64+0.16)=1.62$ . Butter: $2(625+100+100)=1650$ . The condition number is $\kappa\approx1487$ : a razor-thin canyon. The safe stride is only about $0.0012$ .

Now standardise both columns (Section 5). The bill becomes a gently tilted bowl with $\kappa\approx10$ . The safe stride grows to about $0.18$ . Walking at 90 % of the safe stride, shrinking the error a hundredfold along the gentle direction drops from about 3,800 steps to about 24.

And look at what did not change. The data means the same thing. The model is the same two knobs. The best fit is the same fit, written in new units. Only the units moved. This is the cheapest win in all of machine learning.

Why does standardising land exactly on the fix? After standardising, every column's sum of squares is $n$ , the number of rows. So every wall has the same steepness, $2n=6$ here. The walls are level by construction.

What is left over? The bowl still leans, and $\kappa$ is 10, not 1. In this data, guns and butter move together (their correlation is $-0.82$ ): more guns tends to mean less butter. That tilts the bowl, like the tilted ovals of Section 9. Rescaling evens out the axes; it does not straighten them. Turning the axes to match the bowl (called whitening) gives $\kappa=1$ , a perfectly round bowl. Finding those axes is Unit 12's job (PCA).

Try: Press ▶ at $t=0$ : the 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 steps walk nearly straight in.

drag the picture to orbit

how standardised t0

η as share of 2/λ_max0.9

steps30

—

Changing the units changes the bowl's shape, not the model or the best fit. Standardising removes the stretch; the leftover tilt needs a rotation (Unit 12).

The realization

The bill's steepness in knob $j$ is $2\sum_ix_{ij}^2$ : the column's size, squared. The full table of steepnesses is $H=2X^{\top}X$ . Standardising makes every diagonal entry $2n$ , so the walls level out: here $\kappa$ falls from $1487$ to $10.2$ .

The part that survives is the off-diagonal, from columns moving together. Removing it takes 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$ , not $1$ . What is left over, and what 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 — the canyon becomes a bowl, the safe stride grows a hundredfold, and the model and the data's meaning stay untouched.

11

The training clinic — read the loss curve like a doctor

Imagine this

A doctor cannot see inside you. She reads the chart: your temperature, hour by hour. A spike, a slow climb, a fever that comes and goes. Each shape points to a different illness.

You cannot see the bill's landscape either. You only see the bill, step after step. And every problem in this unit leaves its own shape on that chart.

Here are six recorded training runs, one problem each. Read the curve, name the problem, choose the fix. The table below is your cheat sheet.

The chart shows	What is going on	What to do
bill becomes $\infty$ or NaN within a few steps	blow-up: a huge start, or features of very different sizes	start in $[-1,1]$ ; rescale the features; lower $\eta$
training bill falls to $0$ , test bill climbs	memorising: more knobs than facts	more data, fewer knobs, a charge for big knobs, or stop early
a zig-zag that grows	the stride is over the speed limit, $\eta>2/\lambda_{\max}$	lower $\eta$ ; standardise
falls fast, then crawls for ever	bouncing in a canyon (big $\kappa$ )	standardise; momentum; a separate stride per knob
flat from the very first step	a plateau, a stride far too small — or a bug in the gradient	raise $\eta$ ; momentum; a better start; check the gradient
different runs, different answers	several valleys, different watersheds	restart and keep the best — or accept it

Notice that the fixes come in just two families. Reshape the landscape so the plain walk works: rescale the features, start sensibly, charge for big knobs. That is this unit. Give the walker better instincts: momentum to roll across flats, a separate stride per knob, a feel for the curve and not just the slope. That is the next unit.

Try: Open case 2: the training bill falls to $0$ while the test bill turns up at step 25. Pick a diagnosis — a right answer draws the healthy curve the fix would give.

—

Six failures, six shapes on the loss curve. The cheat sheet above lists them all.

The realization

Every failure has a signature on the loss curve: blow-up, the train–test scissors, a growing zig-zag, fast-then-crawl, flat from the start, a different answer every run.

Every fix either reshapes the landscape or teaches the walker.

Pause & predict

A run's bill goes $12,\ 4,\ 11,\ 5,\ 13,\ 6,\dots$ — a zig-zag that slowly grows. What is wrong, and what do you try first?

In one sentence: every failure in this unit leaves its own shape on the loss curve, 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 maths 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 touchy shower tap	start small and random; blow-ups come from the feature's size, not the start	$w_0\in[-1,1]$ ; factor $1-2\eta x^2$
Last year's answer key	more knobs than facts makes a zero bill free, and meaningless	$d>n\Rightarrow$ endlessly many exact fits
Two taps, one handle	sensitivity is the feature's size squared; no single stride serves both	$\partial y/\partial w_j=x_j^2$
Maths out of 100, quiz out of 10	centre slides, standardise squeezes, min–max boxes; use the training numbers	$z=(x-\mu)/\sigma$ , $(x-\min)/(\max-\min)$
Rain on the Western Ghats	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 at night	small tilt, small step — a plateau is slow, not finished	steps $\approx W/(\gamma g)$
The marble in the gutter	each direction shrinks by its own factor; the steepest sets the limit	$1-\eta\lambda_i$ ; $\eta<2/\lambda_{\max}$ ; $\kappa$
The tea-garden path	the gradient crosses every contour at a right angle; it points at the bottom only on circles	$\nabla F\cdot\delta\mathbf x=0$
The stretched photo	standardising levels every wall to $2n$ ; only the tilt from correlation remains	$H=2X^{\top}X$ ; $\kappa\ 1487\to10$
The doctor's chart	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 then overshoots on the steep wall and crawls along the gentle 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: start small and random, judge the model on rows it has never seen, and know that the valley you find is the one downhill from where you started.

In one sentence: most training troubles are a badly shaped landscape, and the cheapest way to reshape it is to put every feature on the same scale.

13

Practice arena — twelve problems, solved in full

Twelve problems, from easy to hard, one for every picture in this unit. Every number has been checked by computer.

Two habits do most of the work. For any stride question, write down each direction's factor first: $1-\eta\lambda_i$ tells you whether it settles, bounces or blows up. For any scaling question, add up the squares of each column: the bill feels feature sizes squared, through $H=2X^{\top}X$ .

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