Unit 10 fixed the ground: change the units and the canyon becomes a bowl. This unit fixes the walker. The slope under your feet says which way is down, but not how long that slope lasts — so one stride never suits every direction. We give the walker three instincts: memory, so pushes that agree add up; its own stride for every knob, based on that knob's history; and forgetting, so old history stops mattering. Momentum, AdaGrad, RMSProp and Adam are those instincts in four mixes, and all five walkers race the same valley above. Then we build a wall. The answer moves onto the wall, the slope there is not zero, and every test you know stops working. So we build a new one — and it turns every wall into a price.
≈ 110 min read + play15 interactive widgets · 14 in 3D · a wall you can slide and price20 inline checks🧾 23 proofs, folded away — open "if you want the algebra" when you are ready✍ 14 solved practice problems
drag the landscape to orbit
1
Your feet feel the tilt, not the turn
Imagine this
You are on a hill trek and the torch dies. It is pitch dark.
You can still feel one thing very well: how much the ground slopes under your shoes. So you lean downhill and take a step.
But your feet cannot tell you how long that slope lasts. A gentle slope that runs for 50 metres, and the same slope that ends at a drop 5 cm away, feel exactly the same. Take a big confident step on the second one and you fall.
Your feet feel the tilt, not the turnA lit valley, one walker, and a tilt disc under its boots: the disc knows the slope here and nothing about where the slope changes. Drag to orbit.
Try: Click η = 0.20 · the edge and press ▶. The walker hops between two glowing pads for ever, because the steep factor 1−10η is exactly −1. Then open the cliff tab and watch a confident step go straight off a ledge the slope never warned about.
drag the picture to orbit
—
One step multiplies w1 by 1−η and w2 by 1−10η, so no single η suits both. The tilt disc knows the slope here; it cannot see the ledge.
A computer walking down a loss is in the same spot. It can measure the slope where it stands. That slope has a name: the gradient. But the gradient says nothing about how quickly the slope is about to change.
That missing information does exist. It sits in the second derivatives, a square table called the Hessian. For a model with a million knobs, the table has a million × a million = a trillion numbers. Nobody computes that every step. So we walk with the slope alone.
The valley tab shows the quiet cost. The loss is J=21w12+5w22. It is gentle along w1 and much steeper along w2. At the start [1,1] the slope reads (1,10): one direction pushes ten times harder than the other.
One step moves you by "stride η times the slope" (η is read "eta"). Work it out for each coordinate and you get something simple. Each coordinate is just multiplied by a number every step:
w1 is multiplied by 1−η.
w2 is multiplied by 1−10η.
Try η=0.1. The steep coordinate is multiplied by 1−1=0, so it hits the floor in one step. The gentle one is multiplied by 0.9 each time. It needs 44 steps to get within 1 % of zero, since 0.944≈0.0097.
So take a bigger stride? At η=0.2 the steep factor is 1−2=−1. Now w2 flips +1,−1,+1,−1 for ever. It never settles and never blows up. Go past 0.2 and it blows up. The steep direction sets the speed limit, and the gentle direction crawls under it.
Unit 10 fixed this by reshaping the ground: standardise the columns and the ten-to-one becomes one-to-one. That is the first thing to try. But in a deep network the steepness comes from the layers, not just the inputs, and it changes during training.
So this unit takes the other road. Leave the ground alone and change the walker. We give it three instincts, each one line of arithmetic: memory, a stride for each knob, and forgetting.
The realization
w1←(1−η)w1w2←(1−10η)w2
Each step multiplies every direction by its own number, and all those numbers share one η. Pick η for the steep direction and the gentle one crawls. Pick it for the gentle one and the steep one blows up. No single stride serves both.
Pause & predict
On J=21w12+5w22 you set η=0.2 exactly. What does the steep coordinate w2 do?
If you want the algebra · 2 proofs, step by step
Prove it · one stride, one factor per direction
Claim. On J=21∑iλiwi2, one step of plain descent multiplies each coordinate by 1−ηλi; the walk converges in every direction exactly when 0<η<2/λmax; and on J=21w12+5w22 at η=0.1 the gentle coordinate needs 44 steps to fall inside 1% of zero.
1
The gradient separates, because the loss does: ∂J/∂wi=λiwi, with no other coordinate in it.
A diagonal quadratic is d one-dimensional problems wearing one coat. Everything below is a statement about one coordinate.
2
So one step is a multiplication:
wiwi(k)←wi−ηλiwi=(1−ηλi)wi,=(1−ηλi)kwi(0).No approximation anywhere — this is the exact iterate after k steps.
3
A geometric sequence shrinks to zero exactly when its ratio is strictly inside (−1,1):
∣1−ηλi∣<1⟺0<ηλi<2⟺0<η<λi2.
All directions survive only if the tightest bound holds, so η<2/λmax.
The stiffest direction alone sets the speed limit. Every other direction is then travelling slower than it could.
4
Here λ=(1,10), so η<0.2. At η=0.1 the factors are 0.9 and 0: the steep coordinate drops to zero in one step, and for the gentle one
0.9k≤0.01⟺k≥ln0.9ln0.01=43.7⇒k=44.
At η=0.2 the second factor is exactly −1, so w2 alternates ±1 for ever: no convergence, no divergence.
∎One step for one coordinate, forty-four for the other, from the same η. That ratio is the condition number κ=10.
Prove it · what your feet could not tell you, written down
Claim. If ∇f does not change faster than a rate L (that is, ∥∇f(u)−∇f(v)∥≤L∥u−v∥), then one step guarantees f(w−η∇f)≤f(w)−η(1−2ηL)∥∇f∥2 — so progress is guaranteed exactly while η<2/L, and is largest at η=1/L.
1
A Lipschitz gradient bounds the Taylor remainder: for any u,v,
f(v)≤f(u)+∇f(u)⊤(v−u)+2L∥v−u∥2.This is the only place the missing second-order information enters — as a worst case, not a measurement. L is how sharply the tilt is allowed to turn.
2
Put v=w−η∇f(w) and u=w, writing g=∇f(w):
f(w−ηg)≤f(w)−η∥g∥2+2Lη2∥g∥2=f(w)−η(1−2ηL)∥g∥2.The first correction pays you η∥g∥2; the second charges you 21Lη2∥g∥2. One is linear in the stride, the other quadratic, so the charge wins eventually.
3
The bracket is positive exactly when η<2/L, and η(1−ηL/2) is largest at η=1/L, where the guaranteed drop is ∥g∥2/(2L).
∎Read it as the blindfold argument, quantified: the safe stride is set by how fast the tilt can turn, and your feet never measured that. On a quadratic L=λmax and this reproduces the bound above.
In one sentence: The slope tells you which way is down but not how long it lasts, so one shared stride must suit every direction at once — and when directions differ tenfold, no stride can.
2
Momentum — give the walker weight
Imagine this
You push a fully loaded trolley at D-Mart. It has a wonky wheel that jerks it left, then right, then left. You hardly notice. In something heavy, a jerk one way and a jerk the other way cancel out.
Once the trolley rolls down the aisle, every small push in the same direction adds speed. It goes faster and faster.
And you already know the price. At the billing counter, you cannot stop it in time.
The loaded trolleyGive the walker mass. Its comet tail is its velocity; the two chains laid on the floor are the last ten pushes, end to end — one chain stacks, the other folds back on itself. Drag to orbit.
Try: Press ▶ at β=0.90. At step 2 the trolley rolls straight through the valley floor, while the plain walker stops on it. Then set β=0.97 and count the crossings in the chip at the top.
drag the picture to orbit
—
A push from k steps ago still counts βk. Pushes that agree add up to 1/(1−β) times one push; pushes that flip nearly cancel.
Momentum turns the walker into that trolley. Look at the two chains on the floor of the scene. Each chain is the last ten pushes, laid end to end.
Along the gentle direction w1, every push points the same way. That chain grows into one long bar. Along the steep direction w2, the push flips sign every step. That chain folds back on itself, and almost nothing is left.
The trolley never learned which direction was which. It just adds up its recent pushes. Adding up is enough: pushes that agree grow, pushes that flip cancel.
To write it down we need one extra list of numbers, the velocityv. It is simply your last move. The rule in words: new move = a faded copy of the last move + a fresh push downhill. The dial β (read "beta", between 0 and 1) says how much of the last move survives. At β=0 you get the plain walker back. (The stride is written α here; the slider calls it η. Same thing.)
How much faster does it go? If the push is the same every step, the faded copies add up: 1+β+β2+⋯=1/(1−β). At β=0.9 that is 10 times one plain step.
Now the price. Run the defaults and watch the loss: 5.5→0.405→4.309. It went up. After step 1 the steep coordinate sits exactly on the floor, so the fresh push there is zero. But the velocity still says "you were falling fast, keep going". It carries w2 straight through the floor to −0.9.
That is not a bug. It is what heavy rolling things do. Momentum does not promise a lower loss every step. It promises faster progress over many steps.
One warning: never set β≥1. Friction is the only thing that calms the swing. Without it, the trolley swings for ever or flies off.
The realization
v←βv−α∇Jw←w+v,v0=0
Each move is a faded copy of the last move plus a fresh push. Pushes that agree pile up to 1/(1−β) times one push — ten times at β=0.9. Pushes that flip cancel. You pay for the speed with overshoot.
Pause & predict
After one momentum step the walker sits at w2=0, right on the floor of the steep direction. The fresh slope there is 0. What does step 2 do to w2?
Pause & predict
A direction gets the same slope g at every step. With β=0.9 and stride α, how big does each step become in the end?
If you want the algebra · 2 proofs, step by step
Prove it · the speed-up is 1/(1−β)
Claim. If a direction receives the same gradient g at every step, momentum's step size rises from αg to αg/(1−β) — a factor of 10 at β=0.9.
1
Unroll the velocity from v0=0 with g fixed:
v1v2vt=−αg=βv1−αg=−αg(1+β)=−αg(1+β+β2+⋯+βt−1).Each old push survives multiplied by β once more, so the surviving copies form a geometric series.
2
Sum it. Since 0≤β<1,
k=0∑t−1βk=1−β1−βtt→∞1−β1,v∞=−1−βαg.At β=0.9 the limit is 10αg, and the series is already at 0.9 of it by step 22.
3
Now the other half. If the gradient alternates, g,−g,g,−g,…, the same unrolling gives vt=−αg(1−β+β2−⋯)→−αg/(1+β), which at β=0.9 is 0.53αg — about a twentieth of the consistent case.
∎The ratio of the two limits is (1+β)/(1−β)=19 at β=0.9. That single number is why the bars stack in one strip and cancel in the other, and it also shows why β≥1 is fatal: the first series stops converging.
Prove it · the two ways of writing momentum are the same rule
Claim.vt=βvt−1−α∇J(wt−1),wt=wt−1+vt is identical to wt=wt−1−α∇J(wt−1)+β(wt−1−wt−2); and on J=21w12+5w22 with α=0.1,β=0.9 the first three points are [0.9,0], [0.72,−0.9], [0.486,−0.810].
1
From the second line, vt=wt−wt−1 — the velocity is the last move. Shift the index: vt−1=wt−1−wt−2.
Nothing has been assumed; this is just naming the same quantity twice.
2
Substitute into the first line:
wt−wt−1=β(wt−1−wt−2)−α∇J(wt−1),
which rearranges to the second form exactly.
So "keep a velocity" and "add β times the last move" are the same instruction. Different books pick different halves; nothing changes.
3
Run it. ∇J=(w1,10w2), start [1,1], v0=0:
v1v2v3=−0.1(1,10)=(−0.1,−1),w1=[0.9,0]=0.9(−0.1,−1)−0.1(0.9,0)=(−0.18,−0.9),w2=[0.72,−0.9]=0.9(−0.18,−0.9)−0.1(0.72,−9)=(−0.234,0.09),w3=[0.486,−0.810]
and J reads 5.5→0.405→4.3092→3.3986.
∎Step 2 is the overshoot in numbers: the fresh push on w2 is zero and the memory carries it to −0.9. Step 3 is the return: the slope at w2=−0.9 is −9, so the fresh push finally turns it around.
In one sentence: Momentum adds a faded copy of the last move, so pushes that agree pile up to 1/(1−β) times a plain step and pushes that flip cancel — at the cost of overshoot, where the loss may rise for a while.
3
AdaGrad — a stride for each knob, from a record that never clears
Imagine this
A hostel warden keeps a register. Every night, next to each student's name, she notes how much noise they made. Loud nights count extra.
Each student's freedom depends on their total. A noisy history means short leashes. A quiet history means lots of freedom.
And the register is never erased. A student who calms down still carries the old total. That last part will cost us.
The permanent recordTwo block towers on the floor, one per weight: every step drops a block whose height is that step's squared slope, and the towers never shrink. The stride is divided by the square root of the tower. Drag to orbit.
Try: Press ▶ on two steps. The first step is 0.1000 in both weights, though one slope is 1 and the other 10 — so the path leaves at exactly 45°. Then open the long run: the towers grow and the walker slows to a stop short of the star.
drag the picture to orbit
—
On step one, αg/g2=αsign(g): only the direction survives. A never shrinks, so the stride can only fall.
Momentum kept one shared stride. AdaGrad stops sharing. Every knob gets its own register, called A: a running total of that knob's squared slopes. Each knob's step is then divided by A. Loud history gives small steps. Quiet history gives big steps.
Now watch the first step. It is the most surprising number in this unit. The slopes are 1 and 10. After one step the register holds A=[1,100], so A=[1,10]. The steps are 0.1×1/1=0.1 and 0.1×10/10=0.1.
Both knobs move by exactly 0.1. The ten-to-one mismatch of §1 is gone, and nobody reshaped anything.
Why? On step 1 the register holds only this step's own square. Its square root is just the size of the slope. A slope divided by its own size is +1 or −1. Only the direction survives.
This is why AdaGrad is loved for rare features. Think of a word that appears in one document out of ten thousand. Its weight rarely gets a slope, so its register stays small and its steps stay long. Common words get slowed down. You get this for free.
Now the catch. A is a running total, so it only grows. So α/A only shrinks, even if the knob has not arrived. Two steps in, the stride is already down from 0.1 to 0.0669. On a steady slope it falls like α/t.
Open the long run tab: the walker slows to a crawl short of the star. A shrinking step is a brake, not an arrival.
The realization
A←A+∇J⊙∇Jw←w−Aα⊙∇J
(⊙ means "multiply entry by entry".) Each knob divides its step by the root of its own total. On step one this leaves exactly α for every knob, whatever its slope. But the total never shrinks, so the steps only ever get smaller.
Pause & predict
Two knobs start together. Knob A feels a slope of +0.1 every step. Knob B feels +100, then −100, then +100, for ever. After many steps, which knob is AdaGrad still moving with long strides?
If you want the algebra · 2 proofs, step by step
Prove it · AdaGrad's first step is exactly α, whatever the slope
Claim. With A0=0, the first AdaGrad step moves every coordinate by exactly α in the direction −sign(gi).
1
After one update, Ai=0+gi2=gi2, so Ai=∣gi∣.
The record contains exactly one entry: this step's own square. Its root is therefore the size of this step's own slope.
2
The step is then
Aiαgi=∣gi∣αgi=αsign(gi).∎The size of the slope cancels against itself. Only its sign reaches the update — the direction is data, the distance is a constant you chose.
3
Check on the session's valley: ∇J([1,1])=(1,10), A=[1,100], A=[1,10], step =0.1⋅[1/1,10/10]=[0.1,0.1], so w(1)=[0.9,0.9].
The ten-to-one mismatch of §1 is gone on step one, with no standardisation and no knowledge of the landscape.
Prove it · why the record becomes a brake
Claim. On a constant slope g, AdaGrad's step at time t is α/t; the total distance it can ever cover in T steps grows only like 2αT, so reaching a target distance D costs about (D/2α)2 steps.
1
With g fixed, At=At−1+g2 and A0=0 give At=tg2, so At=t∣g∣.
A running total of identical squares is just t copies of one square.
2
The step size is therefore
t∣g∣α∣g∣=tα.The slope cancels at every step, not just the first. What remains depends only on how long you have been walking.
3
Add up the first T steps and compare with an integral:
t=1∑Ttα≈α∫1Ttdt=2α(T−1).
Setting that equal to D gives T≈(D/2α+1)2.
∎The distance still grows without limit — AdaGrad is not stuck in theory. But it grows like T, so doubling the distance costs four times the steps, and in practice you run out of patience long before you run out of hill.
In one sentence: Divide each knob's step by the root of everything it has ever felt, and the first step is exactly α for every knob — but the record never clears, so the brake never lifts.
4
RMSProp — judge by recent form
Imagine this
Cricket selectors do not pick a team on career averages. They look at recent form: the last ten innings, with the latest ones counting most. A bad patch from nine seasons ago says nothing about today.
AdaGrad judges every knob on its whole career. RMSProp keeps the "one stride per knob" idea and adds one word: forget.
There is a catch every selector knows. After just one innings, "recent form" is a wild guess.
Form, not career averageThe same two towers, but old blocks evaporate at rate ρ: the towers stay short, the stride stays alive. A dim red ghost walks the AdaGrad path beside the walker and stalls. Drag to orbit.
Try: Click ρ = 0.999. The first step throws the walker right off the map, because it is now 31.6× too big instead of 3.16×. It comes back on step 2.
drag the picture to orbit
—
The average remembers about the last 1/(1−ρ) steps. Starting it at zero makes step 1 too big by 1/1−ρ; Adam fixes that.
RMSProp changes one line of AdaGrad. Instead of a total that grows for ever, it keeps a fading average. Each step, keep a share ρ of the old average (read "rho") and let in 1−ρ of the new square.
A slope from t steps ago now counts only ρt as much as a fresh one. At ρ=0.9 the average mostly remembers the last 1/(1−ρ)=10 steps. And because A can now fall as well as rise, the brake can be released. The stride never dies.
On our valley the difference shows fast. RMSProp's first two strides are 0.3162 and 0.1849. The loss falls 5.5→2.57→1.37. After the same two steps, AdaGrad is still at 3.82.
But look at that first stride again. 0.3162 is about three times α=0.1. Where did that come from?
The average starts at zero. After one step it holds only (1−ρ)g2, a tenth of the real size. Its root is too small by 0.1. Dividing by something too small makes the step too big, by 1/1−ρ=3.16.
At ρ=0.999, a common setting, the first step is 31.6 times what you asked for. RMSProp just lives with this: the average fills up in a few steps and the problem goes away. The next method fixes it properly.
The realization
A←ρA+(1−ρ)∇J⊙∇Jw←w−Aα⊙∇J
Swap the running total for a fading average, and the stride settles at a healthy size instead of dying. On a steady slope it settles at exactly α. The price is a first step that is 1/1−ρ times too big.
Pause & predict
You raise the forgetting dial from ρ=0.9 to ρ=0.99. What happens to the very first step?
Pause & predict
A knob has felt the same slope g for hundreds of steps. Where does RMSProp's stride settle, and what does AdaGrad's do?
If you want the algebra · 2 proofs, step by step
Prove it · a fading average converges, a running total does not
Claim. On a constant slope g, RMSProp's accumulator is At=g2(1−ρt)→g2, so its step size tends to α and never dies.
1
Unroll At=ρAt−1+(1−ρ)g2 from A0=0:
At=(1−ρ)g2(1+ρ+ρ2+⋯+ρt−1).Each old square is multiplied by ρ once per step, which is what "fades as ρt" means.
2
Sum the geometric series and simplify:
At=(1−ρ)g2⋅1−ρ1−ρt=g2(1−ρt)t→∞g2.The (1−ρ) that scaled the new square is exactly cancelled by the (1−ρ) in the denominator of the sum. The average converges to the thing being averaged — which is the whole point of an average.
3
So the step size is α∣g∣/(∣g∣1−ρt)=α/1−ρt→α. Compare AdaGrad's α/t→0.
∎Same slope, same α, two different fates: one method settles into a working stride, the other brakes itself to a stop. The only difference is whether the accumulator is a total or an average.
Prove it · the zero start inflates the first step by 1/1−ρ
Claim. RMSProp's first step is α/1−ρ — 3.162α at ρ=0.9 and 31.62α at ρ=0.999.
1
Put t=1 in the formula above: A1=g2(1−ρ), so A1=∣g∣1−ρ.
The average is holding only a (1−ρ) share of the true size, because the other ρ share is still the zero it started from.
2
Hence
A1α∣g∣=∣g∣1−ρα∣g∣=1−ρα.
At ρ=0.9: α/0.1=3.1623α, which is the 0.3162 the widget prints at α=0.1.
∎Dividing by a root that is too small makes the step too big, and the longer the memory the worse it is — the opposite of the intuition that more memory means more caution.
3
How long does it last? The inflation at step t is 1/1−ρt, which is within 1% of 1 once ρt<0.02, i.e. t>ln(0.02)/lnρ — about 37 steps at ρ=0.9, but about 3900 at ρ=0.999.
That is why the fix matters: at the popular ρ=0.999 the "start-up transient" lasts thousands of steps.
In one sentence: Swap the permanent record for a fading one and the stride survives all the way down — at the price of a first step that is 1/1−ρ times too big, because an average that starts at zero is a wild guess after one reading.
5
Adam — two notebooks and a warm-up
Imagine this
A new analyst joins your team. For each project she keeps two notebooks. One notes which way things have been heading. The other notes how big the swings have been.
In her first week both notebooks are nearly empty, so they give a misleading picture. A sensible manager corrects for that: strongly at first, a little less each week.
A few months in, the notebooks are full and can be read as they are. The correction switches itself off.
Two notebooks and a probationTwo glass notebooks fill with ink as the walker goes — one remembers which way, one how loud — and a lamp over the walker is the rate on probation: dim while the books are nearly empty, bright once they are full. Drag to orbit.
Try: Drag t from 1 to 12. The lamp dims to its darkest as αt falls to 0.015224. Keep going and it brightens by itself toward α=0.1: the warm-up switches off.
drag the picture to orbit
—
—
Step =αtF/A, with αt=α1−ρt/(1−ρft). Count t from 1: at t=0 you divide by zero.
You have met both notebooks already. The direction notebook F is momentum, written as a fading average of slopes. The loudness notebook A is RMSProp's fading average of squared slopes. Adam keeps both, for every knob, and steps by F divided by A.
Why that ratio? F averages signed slopes, so pushes that disagree cancel. A averages squares, and squares never cancel. So a knob pushed steadily gets a ratio near ±1. A knob shaken back and forth gets a ratio near 0. Noise is quieted automatically.
Now the warm-up fix. Both notebooks start at zero, so early on they are only partly full. After t steps, F is filled to a share 1−ρft and A to a share 1−ρt. Adam divides each notebook by its own share. All of that folds into one number, the rate αt. (The drawer below shows the algebra.)
Drag the step slider to t=1. The stride is exactly 0.1 in both knobs. RMSProp's 0.3162 jump is gone.
Keep dragging and watch αt. It starts at 0.0316 and dips to its lowest, 0.015224 at t=12. It dips first because the two notebooks fill at different speeds. Then it climbs back to the plain α=0.1 and stays there. The warm-up ends by itself.
Two practical notes. Libraries call (ρf,ρ) by the names (β1,β2), with defaults 0.9 and 0.999. And count t from 1, not 0: at t=0 the bottom of αt is 1−ρf0=0, and you divide by zero. This off-by-one is a very common bug.
Step = average direction ÷ root of average loudness, times a warm-up rate αt. Pushes that disagree cancel, loudness divides out, and the very first step is exactly α.
Pause & predict
One knob's slope goes +4,−4,+4,−4,…. Another knob's slope stays at +4. Both use Adam. Which one takes bigger steps, and why?
If you want the algebra · 2 proofs, step by step
Prove it · where Adam's probation rate αt comes from
Claim. Correcting both zero-started averages for how full they are turns the RMSProp step into αtF/A with αt=α1−ρt/(1−ρft) — the square root landing on the A correction only.
1
A zero-started fading average of a constant c reaches c(1−ρft) after t steps (the same geometric sum as §4). So F is systematically short by exactly that factor, and the fair estimate is
F=1−ρftF,A=1−ρtA.This is a division by "how full the notebook is", nothing more. Each notebook fills at its own rate, so each gets its own correction.
2
Put the corrected pair into an RMSProp-shaped step and separate the constants from the raw averages:
αAF=αA/1−ρtF/(1−ρft)=αtα1−ρft1−ρt⋅AF.∎The whole correction collapses into one scalar multiplying the uncorrected ratio — which is why implementations can keep the raw F and A and just scale the stride. And the square root sits only on A's correction because only A was under a root.
3
Limits and shape. As t→∞ both ρt and ρft shrink to zero, so αt→α. With the defaults ρf=0.9,ρ=0.999, αt/α reads 0.3162,0.2353,0.2020,…, dips to 0.15224 at t=12, then climbs back.
Non-monotone, because the two notebooks fill at very different speeds — F is nearly full by step 20 while A needs thousands. The correction is not a schedule somebody tuned; it is bookkeeping that retires itself.
Prove it · Adam's first step is exactly α per knob
Claim. At t=1, Adam moves every coordinate by exactly α in the direction −sign(gi) — RMSProp's 1/1−ρ spike is cancelled precisely.
1
At t=1 the two notebooks hold one reading each:
FiAi=(1−ρf)gi,Ai=(1−ρ)gi2,=1−ρ∣gi∣.Both are short by their own factor — and those are exactly the factors α1 is built from.
2
And α1=α1−ρ/(1−ρf). Multiply:
α1AiFi=α1−ρf1−ρ⋅1−ρ∣gi∣(1−ρf)gi=α∣gi∣gi=αsign(gi).∎Every factor cancels — (1−ρf) against (1−ρf), 1−ρ against 1−ρ, ∣gi∣ against gi. What survives is the stride you asked for and the direction the data gave.
3
On the valley: F=[0.1,1], A=[0.001,0.1], A=[0.031623,0.31623], F/A=[3.1623,3.1623], α1=0.031623, step =[0.1,0.1]. Compare RMSProp's [0.3162,0.3162] at the same point.
Same landscape, same α, one method three times too eager and the other exactly right — because of one scalar.
In one sentence: Adam keeps a signed average and a squared average for every knob, steps by their ratio so disagreement cancels and loudness divides out, and uses a warm-up rate αt that makes the first step exactly α and then switches itself off.
6
Five walkers, one valley — and the dial that decides the race
Imagine this
School sports day. Five runners, one track, one whistle. Same start, same stride length. The only difference is the rule each one uses to pick the next step.
Then the teacher makes the track narrower and steeper, and runs the race again. Watch who copes.
Five walkers, one valleyThe same start, the same stride, five rules — and a stiffness dial that reshapes the valley under their feet. The camera runs with the leader; the loss curves burn on the glass behind.
Try: Drag stiffness to 300 and press ▶. The valley becomes a narrow canyon. The blue walker is thrown over the rim on its first step, and the three adaptive walkers barely notice.
drag the picture to orbit
—
Plain descent is safe only while α<2/c; the adaptive methods never see c. This race is tiny and noise-free, so learn the mechanisms, not the finishing order.
Same valley, same start [1,1], same stride α=0.1, five rules. At the lecture setting, each walker shows its character:
Plain descent looks great. But only because α=0.1 happens to send the steep direction to zero in one step. That is luck.
Momentum pays early: the loss rises to 4.31 at step 2. Then it swings its way down.
AdaGrad evens out the two directions at once, then runs out of stride.
RMSProp reaches the floor first, by far.
Adam walks at a steady pace, rolls past the bottom around step 11 (it carries momentum), and swings back.
Method
w(1)
w(2)
J after 2
J after 25
Gradient descent
[0.9,0]
[0.81,0]
0.3281
0.00258
Momentum
[0.9,0]
[0.72,−0.9]
4.3092
0.196
AdaGrad
[0.9,0.9]
[0.8331,0.8331]
3.8173
0.547
RMSProp
[0.6838,0.6838]
[0.4989,0.4989]
1.3688
3.6×10−13
Adam
[0.9,0.9]
[0.8004,0.8004]
3.5236
0.179
Now, do not crown a winner. This valley is tiny, clean, free of noise and only ten-to-one steep, and α was picked to suit it. Change any of that and the order changes. The dial is how you see it.
Push the stiffness to c=300, with the same α=0.1. Plain descent is now past its safety limit (2/300≈0.0067) and flies off the map within five steps. Momentum does too. The three adaptive walkers barely notice.
Drop α to 0.005 to save plain descent. Now it survives, but it crawls. A stride small enough for the steep direction is far too small for the gentle one. That is §1's problem again, at a bigger scale.
This is the real reason Adam (and its cousin AdamW) is the default for transformers and large language models. There, slope sizes differ between layers by huge factors, they drift during training, and every reading is noisy. Nobody can hand-tune a stride for each layer. A method that scales itself, calms the noise and starts fairly is the sensible pick.
The realization
safe stride: α<λmax2steps needed∼κ=λminλmax
The steepest direction sets the safe stride. The gentlest direction sets how many steps you need. Their ratio κ (read "kappa", the condition number) is the tax plain descent pays. The adaptive methods divide each slope by its own size, so they never see κ at all.
Pause & predict
You make the valley 100 times steeper (λmax up by 100×) and change nothing else. What happens to plain gradient descent's largest safe stride?
Pause & predict
On that steeper valley, why do AdaGrad, RMSProp and Adam keep working without you touching α?
If you want the algebra · 1 proof, step by step
Prove it · the best shared stride, and the price of a bad condition number
Claim. On J=21∑λiwi2 the stride that minimises the worst per-step factor is η⋆=λmin+λmax2, and at that stride every coordinate shrinks by at best κ+1κ−1 per step, where κ=λmax/λmin.
1
From the first drawer, coordinate i is multiplied by 1−ηλi each step, so after k steps the worst-behaved coordinate governs:
r(η)=imax1−ηλi=max{∣1−ηλmin∣,∣1−ηλmax∣}.The maximum over an interval of λ is attained at an end, because ∣1−ηλ∣ is a V in λ.
2
As η grows, 1−ηλmin falls from 1 and ∣1−ηλmax∣ eventually rises. The maximum of a falling and a rising curve is smallest where they cross:
1−ηλmin=−(1−ηλmax)⟹η⋆=λmin+λmax2.At the best stride the softest direction creeps forward and the stiffest one flips sign every step by the same fraction. Optimal does not mean pretty.
3
Substitute back:
r(η⋆)=1−λmin+λmax2λmin=λmax+λminλmax−λmin=κ+1κ−1.∎At κ=1 the rate is 0: one step and you are done. At κ=10 it is 9/11=0.818 and you need ≈23 steps per decimal place. At κ=1000 it is 0.998 and you need ≈1150. That curve is the whole reason the adaptive family exists.
In one sentence: Plain descent's safe stride is set by the steepest direction and its speed by the gentlest, so it pays the condition number in steps — while every adaptive method divides each slope by its own size and never notices.
7
Then someone builds a wall
Imagine this
You want to park as close to the mall entrance as you can. But the first two rows are reserved.
So you park in the first row you are allowed: row 2. You would happily move closer. The rule is the only thing stopping you.
Notice what that means. At your parking spot, "closer" is still better. You have not reached a flat bottom. You have reached a wall.
Then someone builds a wallThe old test — "stop where the slope is zero" — stops being true the moment the answer is pressed against something
Try: On the first tab, slide the wall from c=−1 up past 0. The walker is pushed off the bottom of the bowl and pinned to the glass. Its downhill arrow now pushes into the wall instead of shrinking to nothing.
drag the picture to orbit
—
Standard form: minimise f with every rule written as "≤0" or "=0". A ≥ is multiplied by −1, and a strict < is not allowed, because then there may be no answer.
Here is the same thing in symbols. Find the smallest value of f(x)=x2, but you may only pick x≥2. The bowl's bottom is at x=0, which is banned. So you slide as close as the rule allows and stop at x=2, where f=4.
That took three seconds, and it breaks every method in this course so far. At x=2 the slope of f is 4. Not zero. Every method we have — set the derivative to zero, walk until the ground is flat — is hunting for a flat spot that is not there.
Slide the wall in the widget. While c≤0, the wall is not in your way: the free answer x=0 is allowed, and the slope there is zero, just like before. As soon as c>0, three things happen at once:
The free answer is thrown out. The rule does not adjust it; it replaces it.
The new answer sits exactly on the wall.
The slope there is not zero. It points straight into the wall — which is exactly why you cannot move.
Point 3 is why the rest of this unit exists. We need a new test for "I have arrived". It must say: the slope is not zero, but every direction that would use it is blocked.
First, we write every problem in one shape. Open the standard form tab. Two simple moves do it. Turn any ≥ into ≤ by multiplying by −1. Then move everything to the left side. So x≥2 becomes 2−x≤0.
One more rule: you never see a strict <. Try to minimise f(x)=x with x>2. Is 2.1 the answer? No, 2.01 is allowed and smaller. Then 2.001, then 2.0001… You get closer for ever and never arrive. That problem has no answer at all. Allowing the edge makes the answer exist, and the answer usually sits on the edge.
The realization
xminf(x)subject toe(x)=0,gi(x)≤0
Three roles, three pictures. f is the score: you want it small. e=0 is the path: you must stay exactly on it. Each gi≤0 is a fence: you must stay behind it. So x≥2 becomes g=2−x≤0, whose slope is ∇g=−1. Watch that minus sign — it is where most marks are lost.
Pause & predict
Minimise f(x)=(x−5)2 with x≤1. Where is the answer, and what is the slope there?
If you want the algebra · 1 proof, step by step
Prove it · a strict inequality can leave a problem with no answer
Claim.minx subject to x>2 has infimum 2 and no minimiser; replacing > by ≥ makes the answer exist, at x=2.
1
Every feasible x satisfies x>2, so 2 is a lower bound for the objective.
A lower bound always exists here; the question is whether anything attains it.
2
Suppose some feasible x0 were the minimum. Then x0>2, so the midpoint x1=2x0+2 satisfies 2<x1<x0: it is feasible and strictly better.
The assumption defeats itself, and it does so for any candidate — there is no special point where the argument fails.
3
So no feasible point is minimal: the infimum 2 is approached (2.1,2.01,2.001,…) and never reached. With x≥2 the point x=2 is feasible and clearly optimal.
∎This is not pedantry, because constrained answers usually sit on the boundary. A form that excluded the boundary would throw away the answer in the typical case, not the exceptional one.
In one sentence: Put a wall in a problem and the answer moves onto the wall, where the slope is not zero — so "stop where it is flat" must be replaced, starting by writing every problem as minf with e=0 and gi≤0.
8
Pushing a box against a wall
Imagine this
You are shifting house. You push a heavy almirah at an angle, so it presses against the wall of the corridor.
As long as your push has any part that runs along the wall, the almirah slides. It stops only when your push points straight into the wall, with nothing left along it.
That is not just a fact about furniture. It is the stopping rule for every problem with a fence.
Pushing a box against a wallSplit the downhill push into the part that runs along the wall and the part that shoves into it. The box slides while the along-part lasts; it stops when that part is gone.
Try: Drag the gold box along the glass wall and watch the violet arrow (the part along the wall) shrink. Where it reaches zero, the push and the wall's arrow line up. The stretch between them is the multiplier.
drag the picture to orbit · drag the box to slide it
—
At the answer nothing is left along the fence, so ∇f=−μ∇g with μ≥0. On a path (an = rule) the stretch may have either sign.
Drag the box along the wall. The downhill push −∇f is split into two parts: the part that runs along the wall, and the part that pushes into it.
While the along-part exists, you are not done. Slide that way and the score gets better, and you are still allowed. The along-part shrinks as you get close, and it is zero exactly at the answer.
Once the along-part is gone, the whole push points straight across the wall. There is only one "straight across" direction: the wall's own arrow ∇g, which points out of the allowed side. So the two arrows lie on one line. That is an equation.
They are parallel, not equal. The two arrows almost never have the same length. The number μ (read "mu") is the stretch between them.
A small example from the widget. On the straight fence x+y=4, the answer is (2,2). There the score's arrow is ∇f=(4,4) and the fence's arrow is (1,1). Same line, stretch 4. Writing "∇f=∇g" is the most common slip in this topic.
There is a second way to see it. Draw the contour lines of f and shrink them until the smallest one still touches the allowed set. It touches but does not cross. At a touching point the two curves share a tangent, so their arrows line up. Same rule, seen from another side.
Open the budget circle tab: you have met this before. Ridge regression is usually taught as "error +λ∑βj2". Its original form is a fenced problem: make the error small, with a budget∑jβj2≤s on how big the coefficients can be.
The grey rings are the error. The red circle is the budget. The answer is where the smallest reachable ring touches the circle, and the λ in your notes is the stretch μ at that point. Lasso is the same picture with a diamond, and its corners are where coefficients become exactly zero.
The realization
∇f(x⋆)=−μ∇g(x⋆),μ≥0
At the answer, nothing is left to slide along the fence. So the score's arrow and the fence's arrow lie on one line. They are parallel, not equal, and μ is the stretch between them. Soon μ will turn out to be a price.
Pause & predict
At a point on a fence, you find that ∇f has a part of size 0.7 running along the fence. What does that tell you?
If you want the algebra · 1 proof, step by step
Prove it · nothing left to slide means the two gradients are parallel
Claim. At a minimum sitting on an active fence g=0 (with ∇g=0), the component of ∇f along the fence must be zero, hence ∇f(x⋆)=−μ∇g(x⋆) for some μ≥0.
1
Split ∇f into the part along the fence and the part across it. Writing n=∇g/∥∇g∥ for the unit normal,
∇f=across(∇f⊤n)n+p=along∇f−(∇f⊤n)n.A plain orthogonal decomposition. p is the piece that lives in the fence's tangent direction.
2
Suppose p=0. Move a small ε along −p. To first order this keeps you on the fence (∇g⊤p=0, so g does not change) and changes the score by
∇f⊤(−εp)=−ε∥p∥2<0.A legal move that strictly lowers the score. So the point was not a minimum — exactly the box that is still sliding.
3
Therefore p=0 at any minimum, so ∇f is a multiple of n, i.e. of ∇g: write ∇f=−μ∇g.
Parallel, not equal — μ absorbs the difference in length, which is typically large.
4
The sign. Moving into the feasible side means moving along −∇g, and that must not lower f:
∇f⊤(−∇g)=(−μ∇g)⊤(−∇g)=μ∥∇g∥2≥0⟹μ≥0.∎If μ were negative you could step inwards, legally, and improve — so the fence was not holding you at all. That is the geometric twin of §9's guard argument.
In one sentence: You stop when nothing is left to slide along the fence, so ∇f and ∇g lie on one line with a stretch μ≥0 between them — and that stretch is about to become a price.
9
Turn the wall into a fine
Imagine this
A city wants people to stop parking past a line. It can build a concrete barrier. Or it can put up a sign: "Fine: ₹μ for every metre past this line."
Park behind the line and you pay nothing. Park past it and you pay. Now there is no barrier, only a bill.
You want the bill small. The traffic police would be happy if you strayed, so they want it big. That tug-of-war is the whole method.
Turn the wall into a fineAn infinite wall is not a function you can differentiate. A straight-line fine is. Raise the rate until the fine does the wall's whole job.
Try: Press ▶. The green bead climbs toward the dashed p∗=4 line as the fine rises, and touches it exactly at μ=4. Then drag μ below zero: the amber walker runs off the right edge, because a negative fine pays you to cross.
—
maxμ≥0μg is 0 when g≤0 and +∞ when g>0: the wall, rebuilt from straight lines. Swap the min and the max and you get the dual.
Why a fine? We know how to solve problems with no rules: take the derivative, set it to zero. So we want to turn each rule into something we can differentiate.
First try: write the wall as a function. Charge 0 inside and ∞ outside. That is exactly right: every illegal point now scores infinity, so the answer does not change. But you cannot differentiate a vertical cliff.
The fix: put a straight line under the wall, and make it steeper. The line μg is zero at the fence. On the allowed side g≤0, so the line is zero or negative there — no charge. On the banned side it climbs.
The line always stays below the wall. But as μ grows it does more and more of the wall's job. Let the guard pick the worst μ for you, and you get the wall back exactly.
See it on a small problem (lower panel): f(x)=(x−3)2 with the fence x≤1. The true answer is x=1, with score 4. Slide μ and watch minxL. That is a plain no-rules problem, and its answer works out to 2μ−μ2/4. It climbs towards 4 and touches it exactly at μ=4. At that price, the straight line does the whole wall's job.
Two sign rules come out of this picture. They are not conventions.
Fence fines must be μi≥0. Drag μ below zero in the top panel. Now the line dips below zero on the banned side, so crossing the fence would lower your bill. The optimiser would run out of bounds on purpose. A fine must raise the bill. This rule is called dual feasibility.
The path fine λ can be any sign (read "lambda"). A path e=0 can be left in either direction, and both are equally illegal. So its fine has no natural sign. Negative λ values come up all the time, and they are correct.
The realization
μ≥0maxμg={0,+∞,g≤0g>0
L(x,λ,μ)=f(x)+λe(x)+i∑μigi(x),μi≥0
Obey the fence and the guard's best fine is μ=0: you pay nothing. Break it and the guard raises μ without limit. So the LagrangianL — score, plus a fine for leaving the path, plus a fine for each fence — is not a rough copy of the problem. It is the problem, with rules turned into prices.
Pause & predict
Why is a negative fence fine μi<0 not allowed, when a negative path fine λ is fine?
Pause & predict
You minimise f with one fence. Your candidate point sits comfortably inside the allowed region. What does the guard charge?
If you want the algebra · 2 proofs, step by step
Prove it · the infinite wall, rebuilt out of straight lines
Claim.μ≥0maxμg={0,+∞,g≤0g>0 — the indicator of the fence, exactly.
1
If g≤0: for every μ≥0 the product μg≤0, and the value 0 is achieved at μ=0. So the maximum is 0.
On the allowed side the guard's best move is to charge nothing — any positive rate would reduce the bill the guard is trying to raise.
2
If g>0: taking μ=M gives Mg→∞ as M→∞. So the supremum is +∞.
On the banned side the guard is unbounded, and one violated fence is enough to make the whole bill infinite.
3
Hence for every x,
μ≥0maxL(x,μ)=f(x)+i∑μi≥0maxμigi(x)={f(x),+∞,xfeasibleotherwise,
so minxmaxμ≥0Lis the constrained problem.
∎Nothing was relaxed or approximated. The Lagrangian with a maximising guard is the original problem written in a form we can differentiate.
Prove it · why a fence fine can never be negative
Claim. If some μi<0 were allowed, the minimiser of L would be pushed outside the feasible set on purpose, and the construction above would fail.
1
Take one fence and a point with g(x)>0 — illegal. The term contributed to the bill is μg.
This is the only place the rule enters the objective, so this term alone decides whether breaking the rule is punished or rewarded.
2
With μ<0 and g>0, μg<0: the bill falls. And it falls further the more the fence is broken, since μg→−∞ as g→∞.
A subsidy, not a fine. The minimiser will chase it out of bounds and never come back.
3
Correspondingly, maxμ∈Rμg is +∞ for g=0 and 0 only at g=0 — the indicator of the equalityg=0, not of g≤0. Restricting to μ≥0 is exactly what turns it into the one-sided rule.
∎So the sign rule is not a convention: it is the difference between "stay behind the fence" and "sit exactly on it". And it explains λ at once — for a genuine equality we want the two-sided version, so λ is left free.
In one sentence: You cannot differentiate an infinite wall but you can differentiate a straight line, and letting the guard raise the line's slope rebuilds the wall exactly — so L=f+λe+∑μigi with μi≥0 is the fenced problem itself.
10
Room left, and the rule that falls out of it
Imagine this
Your phone plan gives you 2 GB of data a day. Today you used 1.2 GB. There is room left. The limit cost you nothing: with a 3 GB plan, your day would have been exactly the same.
Tomorrow you hit exactly 2 GB and your video stops. Now the limit is what is holding you back, and one more GB would be worth real money to you.
So: room left means the limit is worth nothing. No room means it may be worth a lot. Never room and a price at once.
Room left, and the rule that falls out of itEither you have room and the fine is zero, or you are touching and the fine may be positive. Never both, never neither — the bead rides two rails and never falls into the chasm between them.
Try: Drag the walker from deep inside to hard against the glass. The gold bead runs along the green rail to the corner, then climbs the orange one. It never enters the dark pit, and μ⋅g stays 0.000 all the way. Drag past the wall and it turns red: not allowed.
drag the picture to orbit
—
μg=0 says the fine is charged only when you are touching. Writing g+t2=0 builds g≤0 into the algebra, since a square is never negative.
Let us give that "room left" a name. The fence g≤0 is an inequality, and calculus is bad at inequalities. So turn it into an equation by adding the room: g+t2=0. Here t2 is the room left, called the slack.
Why a square? A square is never negative, so the rule g≤0 is built right into it. And a square is smooth, so we can still differentiate.
Now differentiate the Lagrangian with respect to t. The slack t appears only in μt2, so the derivative is 2μt=0. Multiply by t and halve: μt2=0. Since t2=−g, that is μg=0. This is why the rule is called complementary slackness: it comes from the slack.
A product is zero only if one of its parts is zero. So for every fence, one of two worlds holds. (The dark quadrant in the widget is the world that cannot happen.)
Room to spare:gi<0, strictly inside. Then μi=0. The fence is inactive (or slack). Delete it and the answer does not move.
Touching:gi=0, pressed against the edge. Now μi may be positive, and usually is. The fence is active (or tight). It is holding you back.
Two easy traps. First: "active" and "on the edge" are the same world, not two. Second, and it costs more marks: on the edge the fine is not forced to zero. With gi=0, the product μigi is zero for any μi. A positive fine on a touched fence is normal. In §13 you will meet one with μ⋆=4.
And the fine is a price, just like the data plan. Loosen fence i by a small amount ε, and the best score improves by about μiε. A fence with μi=0 is not worth paying to remove. It was never in your way.
The realization
gi(x)+ti2=0⟹μigi(x⋆)=0
Write the room left as a square and differentiate. Out comes μigi=0: either you have room and the fine is zero, or you are touching and the fine may be positive. Never room and a fine at once.
Pause & predict
At the answer you find μ3=0 for the third fence. What can you say about g3(x⋆)?
If you want the algebra · 1 proof, step by step
Prove it · complementary slackness, in four lines, from the room left
Claim. Writing each fence as gi(x)+ti2=0 and differentiating L with respect to ti gives μigi(x⋆)=0.
1
The substitution loses nothing: ti2=−gi, and a square is never negative, so −gi≥0, which is gi≤0 — the original fence, recovered.
The inequality has been absorbed into the algebra. Every rule in the problem is now an equation, apart from the sign rule on μi.
2
With the slacks in, L(x,λ,μ,t)=f+λe+∑iμi(gi+ti2). The only term containing ti is μiti2, so
∂ti∂L=2μiti=0.A new unknown means a new equation — and this is the one that books usually state without ever deriving.
3
Multiply by ti and halve: μiti2=0.
Multiplying by ti is legal even when ti=0; it simply keeps the identity true in both worlds.
4
Substitute ti2=−gi:
μi(−gi(x⋆))=0⟹μigi(x⋆)=0.∎A product is zero only if a factor is, so per fence: either ti=0 (room left) forcing μi=0, or μi=0 forcing ti=0, i.e. the fence is touched. The name is literal — the rule came out of the slack.
In one sentence: Write the room left as a square, differentiate, and out comes μigi=0 — either there is room and the fine is zero, or you are touching and the fine may be positive.
11
Five conditions, and checking every case
Imagine this
A room has a lamp and two switches, and you don't know the wiring. The sure way to find what works: try all four settings. Off-off, off-on, on-off, on-on. With three switches, eight tries.
That is exactly how you solve a fenced problem by hand. Each fence is a switch: touching, or not touching. Try every setting, and throw out the ones that break a rule.
First, the rules each try must pass. They are the famous KKT conditions, named after Karush, Kuhn and Tucker. They are not a new idea. They are the oldest idea in the course, set every derivative to zero, done on the Lagrangian with the slack in it. Each kind of unknown gives one condition. Only the sign rule is added by hand.
Condition
In everyday words
In symbols
1 · Balance
The score's push and the fences' arrows cancel out (§8).
∇f+λ∇e+∑iμi∇gi=0
2 · On the path
You are exactly on the path.
e(x⋆)=0
3 · Behind the fences
You are on the allowed side of every fence.
gi(x⋆)≤0
4 · Room or fine
Each fence has room, or a fine — never both (§10).
μigi(x⋆)=0
5 · Fines are not rewards
A fence fine is never negative (§9).
μi≥0
Condition 1 comes from differentiating by x, condition 2 by λ, 3 by μi and 4 by the slack ti. Condition 1 is stationarity, 4 is complementary slackness, 5 is dual feasibility. Note that λ has no sign rule.
Now the procedure. Condition 4 gives two choices per fence: the fine is zero, or the fence is touched. Guess one for each fence. Solve the equations. Then let conditions 3 and 5 throw out the guesses that fail.
The widget's problem: minimise x2+2y2 on the path x+y=1, with two fences x≥0 and y≥0. Two fences, so four cases. Work through them:
Five conditions, a branching interrogationEach fence is either doing work or not. Guess, solve, and let the conditions throw out the guesses that lie.
Try: Click a branch of the tree, or press ▶ to test all four. Three branches burn red and their beads fall through the map. One turns green, and a star lands on the path at (2/3, 1/3).
drag the picture to orbit
—
Balance · on the path · behind the fences · room or fine · fence fines ≥0. The path fine λ may be any sign; the fence-fine sign rule does most of the rejecting.
Three of the four cases died, each in its own way.
Cases 2 and 3 gave a clean point, then a negative fine: μ=−2 and μ=−4. That is not a sign to fix. It means the guess was impossible: the fence would have to pull you towards it. Throw the case out.
Case 4 guessed both fences touching, so x=0 and y=0. That breaks the path x+y=1 before any fine is even computed. The survivor is case 1: the point (2/3,1/3), with λ⋆=−4/3. Negative, and perfectly fine, because λ has no sign rule.
How many cases in general? Each fence doubles the count, so m fences give 2m. The classic slip is to write m2. The two agree at m=2 (both 4) and m=4 (both 16), which is why the slip survives. At m=3 the truth is 8, not 9. Paths add no cases, because a path is always touched.
Three small notes. A point can have μi=0 and gi=0 at once, so it may show up in two cases. A case may give no point, one point, or many. And 2m grows fast: 10 fences give 1024 cases, and a support vector machine has one fence per training point. Listing cases is a tool for small problems. Real solvers use the dual (§13).
The realization
each fence: μi=0orgi=0⟹2mcases
KKT is "set every derivative to zero" on the Lagrangian, plus the sign rule. To use it by hand, guess for each fence whether it is touching, solve, and throw out any guess that gives a negative fine or breaks a rule.
Pause & predict
You are testing a case where you guessed a fence is touching. The algebra gives μ2=−3. What do you do?
Pause & predict
A problem has one path (an equality) and three fences (inequalities). How many cases does complementary slackness create?
If you want the algebra · 1 proof, step by step
Prove it · the five conditions are four derivatives and a sign
Claim. Setting every partial derivative of L(x,λ,μ,t)=f+λe+∑iμi(gi+ti2) to zero yields conditions 1–4, and condition 5 is the sign rule of the previous drawer.
1
In x (n equations). The slack terms carry no x, so they drop:
∇f(x⋆)+λ∇e(x⋆)+i∑μi∇gi(x⋆)=0.This is §8's two-arrows statement, written for many rules at once: ∇f is a combination of the constraint gradients, so nothing of it is left running along the feasible directions.
2
In λ. Only λe(x) contains λ, and it is linear in it, so the derivative is e(x⋆)=0.
Our own path constraint, handed back. A good sign: the machinery did not lose a rule.
3
In μi. Only μi(gi+ti2) contains μi, so gi(x⋆)+ti2=0, i.e.
gi(x⋆)=−ti2≤0.Our own fences, handed back — and with the inequality restored for free by the square.
4
In ti. The previous drawer: μigi(x⋆)=0. And the sign:μi≥0, which no derivative will give you — it comes from the guard argument.
∎Four kinds of unknown, four conditions, plus one rule about what a fine is. Some books list four conditions by folding the sign rule into the setup; count five when you write an answer, so nothing can be said to be missing.
5
Counting: n variables, one λ, m multipliers, m slacks — n+2m+1 unknowns, matched by n+1+m+m equations plus m sign rules. And condition 4 splits into 2m branches, since each μigi=0 can be satisfied two ways.
Books that skip slacks report n+m+1 unknowns. Both counts are right; they describe different setups, and only the slack version hands you condition 4 for free.
In one sentence: KKT is "set every derivative to zero" on the Lagrangian plus the sign rule, and room-or-fine turns it into 2m cases to check, most of which die on a negative fine.
12
Which problems you can trust
Imagine this
Drop a marble into a kadai. Wherever it starts, it rolls to the one bottom. Drop it into an egg tray and it gets stuck in whichever dip is nearest.
Here is a test you can do with a string. Stretch it tight between two points on the inside of the kadai. The string always stays above the surface. Now stretch it between two dips of the egg tray. It cuts through the hump in between.
A shape that passes the string test everywhere has one bottom and no traps.
Which problems you can trustTwo tests for a bowl — the chord and the tangent — and one test for a set. They always agree, and together they decide whether a stopping point is the answer or only a candidate.
Try: Pick the wavy surface and drag the two pins. Wherever the string passes under the surface, it glows red. Press ▶ to try 200 pairs: 119 go red. Then switch to the tangent test and slide the glass plane over the same region.
drag the picture to orbit · drag a pin to move it
convex ⇒ a KKT point is THE answer. Not convex ⇒ a KKT point is only a candidate.
—
A bowl is a surface no string passes under — the same as never dipping below its tangent planes. You can trust a problem when the score is a bowl and the allowed region is convex.
On a curve, the test goes like this. Pick two points on the graph and join them with a straight string (a chord). If the curve never rises above the string — for any two points — the function is convex, a bowl.
Drag the two points and read the two heights. The string's height is θf(x)+(1−θ)f(y), where θ (read "theta", between 0 and 1) says how far along the string you are. The curve's height right below is f(θx+(1−θ)y). Convex means the curve is never higher.
The tangent tab shows the same fact another way. Lay a tangent line at any point. For a bowl, the curve never dips below that line, anywhere. On x2 the string test fails 0 times in 200 random pairs. On x4−3x2 it fails 119 times.
Why do we care? The tangent version says: the slope at your feet is a promise about the whole landscape. On a bowl, a local reading tells you something global.
The same test works for sets (third tab). A set is convex if the straight line between any two of its points stays inside. A disc passes. A crescent and a ring fail.
A convex problem has a bowl score, bowl-shaped fences and straight (linear) paths. Then the allowed region is convex too, and there is nothing to get trapped in.
Now the payoff. It has two halves that people often mix up.
KKT is necessary. Every true answer passes the test — as long as the fences behave well at the answer. The usual condition is that the arrows of the touching fences are linearly independent there. (Its name is a constraint qualification.) Two touching fences with parallel arrows can break it, and then the test can miss the answer.
KKT is sufficient only if the problem is convex. Then a point passing all five conditions is the best point, full stop. If the problem is not convex, the point could be a maximum or a saddle, and you must check another way.
Two convex shapes cover most of what you will meet. A linear program has a straight-line score and straight-line rules: minc⊤x subject to Ax≤b. A quadratic program has a bowl score and straight-line rules: min21x⊤Qx+c⊤x subject to Ax≤b. Ridge, lasso and the support vector machine are all quadratic programs. The drawer below works out both duals.
The realization
f(θx+(1−θ)y)f(y)≤θf(x)+(1−θ)f(y)is the same as≥f(x)+∇f(x)⊤(y−x)
The curve stays under every string, or, the same thing, above every tangent. The tangent form means one slope reading is a promise about the whole function. On a convex problem, a point that passes the five conditions is the answer.
Pause & predict
You run the five conditions on a problem, and one point passes all of them. Is it the minimum?
If you want the algebra · 2 proofs, step by step
Prove it · the chord test implies the tangent test
Claim. If f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y) for all θ∈[0,1], then f(y)≥f(x)+∇f(x)⊤(y−x) for all x,y.
1
Rewrite the chord condition with the roles arranged around x. Put zθ=x+θ(y−x); then zθ=(1−θ)x+θy, so
f(zθ)≤(1−θ)f(x)+θf(y).Same statement, parametrised by how far along the segment you have walked.
2
Subtract f(x) from both sides and divide by θ>0:
θf(x+θ(y−x))−f(x)≤f(y)−f(x).The left side is a difference quotient along the direction y−x. The right side does not contain θ at all — so it is an upper bound that survives any limit.
3
Let θ→0+. The left side is the directional derivative ∇f(x)⊤(y−x), giving
∇f(x)⊤(y−x)≤f(y)−f(x).∎Read it as a promise: the tangent plane at x lies below the whole surface. So if ∇f(x)=0 then f(y)≥f(x)everywhere — one local measurement certifies a global minimum. That is the entire practical value of convexity.
Prove it · the duals of a linear program and a quadratic program
Claim. For minc⊤x s.t. Ax≤b the dual is max−λ⊤b s.t. c+A⊤λ=0,λ≥0; for min21x⊤Qx+c⊤x s.t. Ax≤b with Q invertible it is max−21(c+A⊤λ)⊤Q−1(c+A⊤λ)−λ⊤b s.t. λ≥0.
1
Linear. Write the Lagrangian and collect the x terms:
L=c⊤x+λ⊤(Ax−b)=(c+A⊤λ)⊤x−λ⊤b.It is linear in x, which makes the inner minimisation trivial and brutal.
2
Minimising a linear function over all of Rd gives −∞ unless its coefficient vector is zero. So
d(λ)={−λ⊤b,−∞,c+A⊤λ=0otherwise.
Maximising over λ≥0 therefore forces the equation as a constraint of the dual.
The −∞ region is not a nuisance; it is where the dual's own constraints come from. A dual variable that sends the inner problem to −∞ is a price nobody would ever quote.
3
Note the shape swap: the primal has d variables and m rules; the dual has m variables and d rules. Solve whichever is smaller.
This is reason one from §13, in its purest form.
4
Quadratic. Now L=21x⊤Qx+(c+A⊤λ)⊤x−λ⊤b; setting ∇xL=0 gives Qx+(c+A⊤λ)=0, so x=−Q−1(c+A⊤λ).
A bowl in x has a genuine minimum, so nothing runs off to −∞ and there is no hidden constraint this time.
5
Substituting back and writing u=c+A⊤λ:
d(λ)=21u⊤Q−1u−u⊤Q−1u−λ⊤b=−21u⊤Q−1u−λ⊤b.∎A concave quadratic in λ with only the sign rules left — and ridge, lasso and the support vector machine are all of exactly this shape. The last one is worked in §14.
In one sentence: A bowl never rises above its strings and never dips below its tangents — and on a bowl with bowl fences, a point that passes the five conditions is the answer; anywhere else it is only a candidate.
13
Who moves first — and what a wall is worth
Imagine this
You need an auto-rickshaw. If you first tell the driver where you are going, and how urgently, he quotes the worst fare he can get away with.
If instead the driver must put up a fixed rate card first, you then choose knowing the rates. You can only do as well or better.
Moving second is an advantage. That one idea is all of duality.
Who moves firstThe same number seen from two sides — and the reason the view from below is always a bowl turned upside down, however ugly the problem is
Try: Open a bundle of rods and drag the highlight. Every rod is straight, yet the lit ridge under all forty bends downward. Press ▶ to sweep along. That is why the dual is always a hill.
drag the picture to orbit
—
For each x, L(x,μ) is a straight rod in μ, and the dual is the lowest of them, so it always bends downward. d∗≤p∗ is free; equality needs more.
Our bill has two players. You choose x and want L small. The guard chooses μ and wants L big.
If you move first, the guard sees your choice and answers with the worst μ for you: 0 if you obeyed the fence, ∞ if you did not (§9). So every illegal point scores infinity and every legal point scores its real value. This is just the original problem, called the primal. Its best value is p⋆.
If the guard moves first, he announces a price μ, and you then minimise L freely. What you get is the dual functiond(μ)=minxL(x,μ), a plain no-rules problem. The guard then picks the μ that makes it biggest. That best value is d⋆.
Moving second is an advantage, so d⋆≤p⋆ — always, for every problem. That is weak duality. The difference p⋆−d⋆ is the duality gap. When the gap is zero, we have strong duality.
Example: our fine problem from §9, f(x)=(x−3)2 with x≤1. Its dual function is d(μ)=2μ−μ2/4. It peaks at μ=4, where d⋆=4=p⋆. No gap.
Now open a bundle of lines. Fix any x. Then L(x,μ)=f(x)+μg(x), as a function of μ, is a straight line with height f(x) and slope g(x). One line for every x. The dual function is the lowest of all those lines.
The lowest edge of a bundle of straight lines always bends downward. So d is concave — a hill — always, however bumpy f and g are. A hill has one top and no traps.
Why bother with the dual? Three reasons.
Fewer unknowns. The primal has one unknown per parameter. The dual has one per constraint.
No traps. The dual is always a hill.
The unknowns change meaning. In a support vector machine, the dual has one fine per training point. That swap is what lets kernels in (Units 13 and 14).
Does the gap ever open? Look at the gap tab. Two allowed bands is not convex, but the gap closes anyway: p⋆=d⋆=−2. Two wells is not convex, and the gap stays open: p⋆=0.3894 while d⋆=0.
So: weak duality is free. A convex problem with at least one point strictly inside all the fences is guaranteed no gap. Without that, you might get lucky, but you cannot count on it.
The realization
p⋆=xminμ≥0maxL(x,μ)≥μ≥0maxxminL(x,μ)=d⋆
Left, you move first: the primal. Right, the guard moves first: the dual. Moving second is an advantage, so the dual is always a lower bound. And the dual is the lowest of many straight lines, so it is always a hill.
One thing is left: what the fine μ really means. We have called it a stretch, a fine, a price. Let us make "price" exact.
What a wall is worthThe multiplier is not bookkeeping. It is the price of the wall: move the wall a little and it tells you the new answer before you re-solve anything.
Try: Slide the wall from 3.00 to 2.90. On the back panel, the green bead (the price's guess) says 9.60, the gold bead (the truth) says 9.62, and the red tick is the gap. Move the wall down to 2 and it dims: it is not touching anything any more.
drag the picture to orbit
—
dp∗/dc=μ∗: the price is how fast the best score changes as you push the wall. At c=2 the wall stops touching, the price drops to 0 and the curve goes flat.
The widget's problem: minimise x2+y2 on the path x+y=4, with a wall x≥c. Drag the wall. The answer slides along the path, the score changes, and the chip compares two numbers: what the fine predicted and what really happened.
At c=3 the answer is (3,1), with μ⋆=4 and p⋆=10. Move the wall back to c=2.9. The fine predicts the score falls by about 4×0.1=0.4, to 9.60. Solve it properly: the answer is (2.9,1.1), with score 8.41+1.21=9.62. Very close. The small 0.02 gap is there because the prediction is a straight-line guess on a curve.
Now slide the wall down to c=2. There the wall stops touching, μ⋆ drops to 0, and the score curve goes flat. A wall you are not touching is worth nothing. That is room-or-fine again, seen from the money side.
This is why multipliers are called shadow prices in applied work. The λ in ridge regression is the price of the coefficient budget. In a factory plan, μ is what one more machine-hour is worth to you — before you buy it.
The realization
μ⋆=d(how tight the fence is)dp⋆
The fine is the slope of the best score as you move the wall. It is exact for tiny moves and a good guess for small ones. A wall you are not touching has price zero.
Pause & predict
A colleague works out the dual of a nasty, non-convex problem and gets d⋆=7. What does that prove about the primal answer p⋆?
Pause & predict
At the best plan of a factory, the fine on "at most 40 machine-hours" comes out as μ⋆=0. A supplier offers you one extra hour. What is it worth?
If you want the algebra · 3 proofs, step by step
Prove it · moving second is never worse (the minimax inequality)
Claim. For any function φ of two arguments, ymaxxminφ(x,y)≤xminymaxφ(x,y).
1
Name the two optima: let the left side be attained at (xA,yA) and the right side at (xB,yB), so LHS =φ(xA,yA) and RHS =φ(xB,yB).
Two numbers, four points' worth of information. The whole proof is comparing them through a shared middle term.
2
Fix y=yA. The left side's inner operation is a minimum over x, and it returned xA, so it is no larger than the value at any other x — in particular xB:
φ(xA,yA)≤φ(xB,yA).A minimum is ≤ any particular value.
3
Fix x=xB. The right side's inner operation is a maximum over y, and it returned yB, so it is no smaller than the value at any other y — in particular yA:
φ(xB,yB)≥φ(xB,yA).A maximum is ≥ any particular value. The middle term φ(xB,yA) is the same in both lines — that is the whole trick.
4
Chain them: φ(xA,yA)≤φ(xB,yA)≤φ(xB,yB).
∎With φ=L, x=x, y=μ: d⋆≤p⋆. No convexity, no differentiability, no assumptions at all — which is why weak duality is free.
5
The one-line version, worth memorising. For any feasible x and any μ≥0,
d(μ)=zminL(z,μ)≤L(x,μ)=f(x)+μ⊤g(x)≤f(x),
because μ≥0 and g(x)≤0. Take the best on each side.
Every dual value you ever compute is a certified lower bound on the primal answer — even if you never solve the primal.
Prove it · the dual function is always concave
Claim.d(μ)=minx[f(x)+μ⊤g(x)] is concave in μ, whatever f and g are.
1
Fix any single x. As a function of μ, L(x,μ)=f(x)+μ⊤g(x) is affine: a constant height f(x) plus a constant slope g(x).
All the nastiness of f and g has been frozen into two numbers. This is the step that does the work.
2
d is the pointwise minimum of that whole family of affine functions, one per x. Take any μ1,μ2 and θ∈[0,1], and let xθ attain the minimum at θμ1+(1−θ)μ2. Then
d(θμ1+(1−θ)μ2)=L(xθ,θμ1+(1−θ)μ2)=θL(xθ,μ1)+(1−θ)L(xθ,μ2)≥θd(μ1)+(1−θ)d(μ2),
the middle line because L is affine in μ, the last because L(xθ,⋅)≥d(⋅) by definition of a minimum.
∎That is exactly the chord test with the inequality reversed: concave. The picture in the widget is this proof — forty straight lines, and the thing underneath them all bends downward.
3
Say it precisely: the dual function is concave; the dual problem, "maximise a concave function over μ≥0", is a convex optimization problem. Both statements are true and they are about different objects.
"The dual is convex" is loose talk that costs marks. Be specific about which object you mean.
Prove it · the multiplier is the slope of the value function
Claim. Let p⋆(b)=minf(x) subject to g(x)≤b. Then dp⋆/db=−μ⋆ — relaxing the fence by ε improves the best score by about μ⋆ε.
1
Write the Lagrangian with the level b in it: L=f(x)+μ(g(x)−b). At the optimum, strong duality gives p⋆(b)=L(x⋆(b),μ⋆(b)).
The value function is the Lagrangian evaluated along the optimal pair — which is what lets us differentiate it.
2
Differentiate in b. The terms coming from x⋆ and μ⋆ moving are multiplied by ∂L/∂x=0 (stationarity) and ∂L/∂μ=g−b=0 (the fence is active), so both vanish. Only the explicit b survives:
dbdp⋆=∂b∂L=−μ⋆.∎This is the envelope argument: at an optimum, first-order changes in the decisions cost nothing, so only the direct effect of the parameter is left.
3
Check it on minx2+y2 s.t. x+y=4,x≥c. For c≥2 the answer is (c,4−c), so p⋆(c)=c2+(4−c)2 and dp⋆/dc=4c−8, which is 4 at c=3 — exactly μ⋆. Predicting c=2.9: 10−4(0.1)=9.60; the truth is 8.41+1.21=9.62.
The 0.02 is the curvature of the value function; the multiplier is a derivative, so it is exact only in the limit. And at c≤2 the fence stops binding, μ⋆=0, and p⋆ goes flat at 8 — a wall you are not touching is worth nothing.
In one sentence: Letting the guard move first gives the dual, which is the lowest of many straight lines — so it is always a hill and always a lower bound — and the fine it hands back is the price of the wall.
14
Two points and a line — where all of this is going
Imagine this
Two houses stand on a straight lane: one at +1, one at −1. The town wants to build a road between them, as wide as possible, with a centre line down the middle.
You already know the answer: centre line at 0, road from −1 to +1.
What you may not know: finding it properly uses every idea from the second half of this unit. And the last idea explains why these machines are called support vector machines.
Two points and a lineThe widest gap is the smallest 21w2 that still clears both constraints — and the answer is built out of the multipliers of the points that touch
Try: On add a point, drag the third lantern from 3 toward 0.5. It stays dim and nothing moves until it crosses 1. Then it lights up, and the boundary shifts to the new answer.
drag the picture to orbit · drag the third lantern
—
Every point with αi=0 could be deleted from the training set and the classifier would not move. That one sentence is where Unit 14 begins.
Now make the houses data. The point x=+1 is labelled positive (y=+1). The point x=−1 is labelled negative (y=−1). The boundary is where wx+b=0.
First, turn "widest gap" into a fenced problem. Scale the boundary so that every point clears it by at least 1: yi(wxi+b)≥1. Then the gap's width is 2/∣w∣. So the widest gap means the smallest ∣w∣. The problem is: minimise 21w2, with two fences. An ordinary quadratic program.
On the first tab, slide w. As soon as w<1, the two fences go red. So w=1 is the smallest value that clears both.
Now solve it the dual way, which is how these machines are really trained. Call the two fines α1,α2 (read "alpha"). Setting the derivative in w to zero gives w=α1+α2. Setting the derivative in b to zero gives α1=α2. Put both back, and w and b disappear. What is left is a hill in one unknown: q(α)=2α−2α2.
Its top is at α⋆=21, where q=21. That matches the primal: 21⋅12=21. No gap.
Now rebuild the boundary from the fines. w⋆=α1+α2=1. Since α1>0, that point's fence is touched, so w+b=1, which gives b⋆=0. Boundary at x=0, edges at ±1, width 2.
Now the big idea. On the last tab, a third positive point sits at x=3, well outside the road. Its fence has room, so its fine is α3=0. The boundary does not move. You could delete that point and get the same machine. Drag it inside the road and its fine comes alive, and the boundary shifts.
That is what "support vector" means: the points whose fences are touched, with αi>0. They alone hold the answer up. A million training points, a handful of non-zero fines, and the rest could be thrown away. This sparsity is room-or-fine, nothing else.
In the dual, the data also appear only as products xixj. That is the door kernels walk through. Units 13 and 14 open that door. You now have the key.
The realization
q(α)=2α−2α2α⋆=21,d⋆=21=p⋆
The boundary is built from the fines: in general w=∑iαiyixi, with ∑iαiyi=0. Points far from the boundary get αi=0 and could be deleted. Only the touching points — the support vectors — matter.
Pause & predict
A trained classifier reports αi=0 for 9970 of its 10000 training points. What does that mean, and what may you do with those points?
If you want the algebra · 1 proof, step by step
Prove it · the widest margin, solved through its dual
Claim. For x1=+1 (class +1) and x2=−1 (class −1), minimising 21w2 subject to yi(wxi+b)≥1 has dual q(α)=2α−2α2 with α⋆=21, giving w⋆=1, b⋆=0, boundary x=0 and margin width 2; and a third point at x3=3 gets α3=0.
1
Standard form. For i=1: (+1)(w⋅1+b)≥1, so g1=1−w−b≤0. For i=2: (−1)(w⋅(−1)+b)≥1, i.e. w−b≥1, so g2=1−w+b≤0. Then
L(w,b,α1,α2)=21w2+α1(1−w−b)+α2(1−w+b),αi≥0.Two fences, so m=2; the multipliers are traditionally called α here rather than μ.
2
Stationarity in the primal variables:
∂w∂L∂b∂L=w−α1−α2=0⇒w=α1+α2,=−α1+α2=0⇒α1=α2.These are the general identities w=∑iαiyixi and ∑iαiyi=0, written out for this data. The second is what makes b drop out of the dual entirely.
3
Substitute. Group L=21w2−w(α1+α2)−b(α1−α2)+(α1+α2); with α1=α2=α the b term drops out and w=2α:
q(α)=21(2α)2−(2α)(2α)+2α=2α2−4α2+2α=2α−2α2.Two primal variables gone, one dual variable left, and the result is a downward parabola — concave, as §13 promised.
4
Maximise over α≥0: q′(α)=2−4α=0⇒α⋆=21≥0 ✓, and d⋆=q(21)=1−21=21.
Check the sign rule before reporting — a peak with α<0 would be out of bounds and the best allowed value would sit at α=0.
5
Recover the classifier. w⋆=α1+α2=1. Since α1=21>0, complementary slackness forces g1=0, i.e. w+b=1, so b⋆=0. Primal value 21(1)2=21=d⋆: zero gap. Boundary x=0, margin lines x=±1, width 2/∣w⋆∣=2, both points tight and therefore support vectors.
Note how b was recovered — not from stationarity (which only gave α1=α2) but from a tight constraint identified by a positive multiplier. That is the standard trick.
6
Add x3=3, class +1. Its constraint is 3w+b≥1, which at (1,0) reads 3≥1: slack, so g3<0 and complementary slackness forces α3=0. The point contributes nothing to w=∑αiyixi and can be deleted. If instead x3<1, it and the negative point become the binding pair, giving w=x3+12 and b=1+x31−x3 — at x3=0.5, w=1.3333, b=0.3333, boundary −0.25, margin 1.5.
∎A million training points, a handful of nonzero multipliers, and the rest deletable: the sparsity of a support vector machine is complementary slackness and nothing else.
In one sentence: The widest road is the smallest 21w2 that clears every point, its dual has one fine per training point, and room-or-fine makes almost all of them zero — so the machine rests on a few support vectors.
15
What to carry forward
Two halves, one thread. The first half changes the walker, because one stride can never suit every direction. The second half accepts that sometimes the place you want is not allowed, and builds a test for arriving where the ground is still sloped.
The picture
What it says
The maths it becomes
Trek in the dark
you feel the slope, not how long it lasts; one stride, many factors
wi←(1−ηλi)wi
The loaded trolley
pushes that agree pile up, pushes that flip cancel; speed costs overshoot
v←βv−α∇J; speed-up 1/(1−β)
The warden's register
a stride per knob from its own history; first step exactly α, then the brake never lifts
A←A+∇J⊙∇J; step α/t
Recent form
forget old slopes and the stride survives; the zero start makes step 1 too big
A←ρA+(1−ρ)∇J⊙2; too big by 1/1−ρ
Two notebooks
signed average over root of squared average; disagreement cancels, loudness divides out
αt=α1−ρt/(1−ρft)
The race
the steepest direction sets the safe stride, the gentlest sets the step count
α<2/λmax; cost κ
The parking rule
the answer moves onto the wall, where the slope is not zero
minf s.t. e=0,gi≤0
The almirah
you stop when nothing of the push runs along the wall
∇f=−μ∇g, parallel not equal
The parking fine
a wall rebuilt from straight lines; a negative fine pays you to cross
L=f+λe+∑μigi,μi≥0
The data plan
room left, or a price — never both
g+t2=0⇒μigi=0
The light switches
each fence touching or not; guess, solve, throw out negative fines
five conditions; 2m cases
Kadai and egg tray
never above its strings, never below its tangents; then a candidate is the answer
f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)
The auto fare
moving second is an advantage; the lowest of many lines is always a hill
d⋆≤p⋆; d concave
The price of a wall
the fine is the slope of the best score; untouched walls cost nothing
μ⋆=∣dp⋆/db∣
The widest road
the boundary is built from the fines, and almost all are zero
q(α)=2α−2α2; αi=0⇒ deletable
The one thing to remember
Divide by what you have felt, and put a price on what blocks you.
Every adaptive method makes the same move. Measure how loud each knob's slopes have been, and divide its step by that. Momentum adds memory so agreeing pushes pile up. Forgetting stops the brake from lasting for ever. Adam does all three, with a warm-up that switches itself off.
Every fenced method makes the other move. Replace each wall by a straight line with a price. That price tells you three things at once: where the answer is pinned, whether the wall matters at all, and what you would pay to move it.
In one sentence: Optimisers divide each step by what that knob has felt, and fenced problems turn every wall into a price — and the price tells you which walls matter.
16
Practice arena — fourteen problems, solved in full
Fourteen problems, easy to hard, across both halves: descent on a two-knob fit and recovering the stride from where it landed, four logged runs read backwards, exact line search, momentum's hyperparameters recovered from three numbers, AdaGrad against RMSProp on a long slope, RMSProp in vector form on badly scaled columns, Adam by hand with its bias correction — then framing a word problem, standard form and the branch count, a quadratic form on the unit circle where the multiplier is the eigenvalue, a fence tested both ways, the full four-case enumeration, a primal-and-dual round trip with the shadow price, and a two-point classifier built from its multipliers. Every number is machine-verified.
Three habits do most of the work. For any optimizer question, tabulate before you calculate — one row per step, columns for the gradient, the accumulators and the new point, in that fixed order; nearly every lost mark is a value used one step out of date. For any constrained question, write the standard form first and keep the minus signs — x≥2 is g=2−x, so ∇g=−1. And never stop at the first case that works: test every branch, or say in writing why a branch is impossible.
Problem 1easy
A straight line y^=wx+b is fitted to the two points (1,3) and (2,5) by minimising L(w,b)=21[(w+b−3)2+(2w+b−5)2]. (a) Derive ∂L/∂w and ∂L/∂b in simplest form and write the two update lines. (b) From (w0,b0)=(0,0) with α=0.1, run two iterations; report (w1,b1), (w2,b2) and the loss after each. (c) A second run started from the same (0,0) with a different rate and landed at (0.26,0.16) after one step. Recover that rate and check it on both coordinates. (d) From the Hessian of L, give the two eigenvalues, the largest safe rate, and decide whether α=0.3 is safe — and by how much.
The five rules used throughout this set. All start from the current point wt with gt=∇f(wt); squares, roots and divisions of vectors are taken element by element; ϵ≈10−8 only prevents division by zero and is dropped in hand calculation.
What this tests. Chain rule into a gradient, the plain rule run without slips, the fact that one step is exactlyα times the gradient vector — so a landing point hands α back — and the speed limit α<2/λmax. Plan. Differentiate each square by the chain rule and collect; then per iteration in this order: gradient at the current point, update both knobs with that same gradient, loss at the new point; for (c) write one step with α unknown and solve from each coordinate; for (d) read trace and determinant off the Hessian.
Show the full solution
(a) Step 1 — differentiate, do not expand. Each term is 21(stuff)2, whose derivative is (stuff)×(derivative of the stuff). The w-derivative of w+b−3 is 1; of 2w+b−5 it is 2:
∂w∂L=(w+b−3)(1)+(2w+b−5)(2)=w+b−3+4w+2b−10=5w+3b−13.
Both b-derivatives are 1:
∂b∂L=(w+b−3)+(2w+b−5)=3w+2b−8.
So the two update lines are
wb←w−α(5w+3b−13),←b−α(3w+2b−8).
(b) Step 2 — iteration 1 from (0,0). Gradient first:
∂w∂L(0,0)∂b∂L(0,0)L0=5(0)+3(0)−13=−13,=3(0)+2(0)−8=−8,=21[(−3)2+(−5)2]=21(34)=17.
Now move both knobs with that one gradient:
w1b1=0−0.1(−13)=1.3,=0−0.1(−8)=0.8.
The new loss, residual by residual:
w1+b1−32w1+b1−5L1=1.3+0.8−3=−0.9,=2.6+0.8−5=−1.6,=21[0.81+2.56]=21(3.37)=1.685.
Step 3 — iteration 2. New gradient at (1.3,0.8):
∂w∂L∂b∂L=5(1.3)+3(0.8)−13=6.5+2.4−13=−4.1,=3(1.3)+2(0.8)−8=3.9+1.6−8=−2.5.w2b2=1.3+0.1(4.1)=1.71,=0.8+0.1(2.5)=1.05.w2+b2−32w2+b2−5L2=1.71+1.05−3=−0.24,=3.42+1.05−5=−0.53,=21[0.0576+0.2809]=21(0.3385)=0.16925.
The whole run on one page:
t
(wt,bt)
∇L
L
0
(0,0)
(−13,−8)
17
1
(1.3,0.8)
(−4.1,−2.5)
1.685
2
(1.71,1.05)
—
0.16925
Two steps cut the bill from 17 to 0.169, a factor of about 100. (The exact fit is w=2,b=1, where L=0.)
(c) Step 4 — read the rate off the landing point. One step from (0,0) with the gradient (−13,−8) is
(w1,b1)=(0+13α,0+8α).
Match each coordinate:
13α8α=0.26⇒α=130.26=0.02,=0.16⇒α=80.16=0.02.
Both coordinates give α=0.02 — the agreement is the check that the run really was plain gradient descent.
(d) Step 5 — curvature, eigenvalues, speed limit. Differentiate the two partials once more:
H=[5332],trH=7,detH=10−9=1.
Eigenvalues from λ2−(tr)λ+det=0:
λ2−7λ+1λλmaxλmin=0,=27±49−4=27±45,=6.854102,=0.145898.
The safe range is α<2/λmax:
λmax20.3−0.291796=6.8541022=0.291796,=0.008204.
So α=0.3 is not safe — but it misses by only 0.008204, about 2.8% over the limit, so the divergence would be slow and easy to mistake for noise. (The condition number λmax/λmin=46.98 is what makes the safe window so narrow in the first place.)
answers at a glance: (a) ∂L/∂w=5w+3b−13, ∂L/∂b=3w+2b−8. (b) L0=17; (w1,b1)=(1.3,0.8), L1=1.685; (w2,b2)=(1.71,1.05), L2=0.16925. (c) α=0.02, from both coordinates. (d) λ=6.854102,0.145898; safe for α<0.291796; 0.3 is unsafe by 0.008204.
Remember
One step is exactly α times the gradient vector, which is why a landing point gives α back — and why both coordinates must agree. The classic slip is updating w first and then using the neww inside the b-gradient: both knobs must move on the same old gradient. The second slip is testing safety against λmin; the speed limit is set by the steepest direction, 2/λmax.
Problem 2easy
Four runs on f(x)=x2 were logged, all starting from x0=1. A:1,0.8,0.64,0.512. B:1,−0.5,0.25,−0.125. C:1,−1.2,1.44,−1.728. D:1,0.8,0.54,0.302. (a) Three of the four are plain gradient descent. Name them, give each one's α, and list the five bands of behaviour of α on this loss. (b) Name the odd run out, recover its α and its β (momentum, v0=0), and verify them on its third step. (c) Re-run B with the decaying rate αt=0.75/(1+t): give α0,α1,α2 and x1,x2,x3. (d) Give the first t with αt<0.1 and that αt; the percentage drop from α0; and the first t at which the factor 1−2αt turns positive, so the sign stops flipping.
What this tests. Diagnosis: on x2 every plain run is a geometric sequence, so the ratio is the fingerprint, and a run whose ratio drifts must be carrying the loaded trolley. Plan. Divide each term by the one before; a constant ratio identifies plain descent and gives α from 1−2α; for the drifting run use v0=0 to get α from step 1 alone, then β from step 2, then check step 3; finally do the decay arithmetic with two inequalities.
Show the full solution
(a) Step 1 — the fingerprint. On f=x2 the gradient is 2x, so plain descent reads
xt+1=xt−α(2xt)=(1−2α)xt.
Every step multiplies by the same number, so a constant ratio means plain descent, and the ratio is 1−2α. Divide:
run
ratios
1−2α
α
behaviour
A
0.8,0.8,0.8
0.8
0.1
monotone
B
−0.5,−0.5,−0.5
−0.5
0.75
oscillating, shrinking
C
−1.2,−1.2,−1.2
−1.2
1.1
diverging
D
0.8,0.675,0.5593
—
—
not plain
The three α values come straight out of 1−2α:
1−2α1−2α1−2α=0.8⇒α=0.1,=−0.5⇒α=0.75,=−1.2⇒α=1.1.
The five bands, all read off ∣1−2α∣:
range of α
factor 1−2α
what happens
0<α<0.5
in (0,1)
monotone descent
α=0.5
0
lands on 0 in one step
0.5<α<1
in (−1,0)
oscillates, still converges
α=1
−1
permanent oscillation ±1
α>1
<−1
diverges
(b) Step 2 — D is the loaded trolley. Its ratios 0.8,0.675,0.5593 shrink instead of repeating, so no single α explains it. Momentum starts with an empty trolley, v0=0, so its first step is pure descent:
v1x1v1=−αg(1)=−α(2)=−2α,=1−2α=0.8⇒α=0.1,=−0.2.
Now step 2 is the only place β appears:
g(0.8)v2x2=1.6,=β(−0.2)−0.1(1.6)=−0.2β−0.16,=0.8+v2=0.64−0.2β.
Set that to the logged 0.54:
0.64−0.2β=0.54⇒β=0.5.
Step 3 — verify on the third step. With β=0.5, v2=−0.2(0.5)−0.16=−0.26:
g(0.54)v3x3=1.08,=0.5(−0.26)−0.1(1.08)=−0.13−0.108=−0.238,=0.54−0.238=0.302.
That is the logged value exactly, so (α,β)=(0.1,0.5) is confirmed. ✓
(c) Step 4 — B again, with a fading rate.αt=0.75/(1+t):
α0α1α2=10.75=0.75,=20.75=0.375,=30.75=0.25.
The factors 1−2αt are −0.5,0.25,0.5, so
x1x2x3=(−0.5)(1)=−0.5,=(0.25)(−0.5)=−0.125,=(0.5)(−0.125)=−0.0625.
Compare with the constant-rate run B — 1,−0.5,0.25,−0.125 — which flipped sign every single step. Fading the rate killed the flipping after one step and still reached a smaller ∣x∣ by step 3 (0.0625 against 0.125).
(d) Step 5 — three small inequalities. First, when the rate drops below 0.1:
1+t0.751+tt<0.1>7.5≥7,α7=80.75=0.09375.
The drop from the start:
0.750.75−0.09375=0.750.65625=0.875=87.5%.
Finally, when the factor stops being negative:
1−1+t1.51+tt>0>1.5≥1.
So t=1 is the first index with a positive factor: the step taken at t=0 is the last one that flips the sign, and from x1 onward every iterate stays negative — exactly what the numbers in (c) show.
answers at a glance: (a) A, B, C are plain, with α=0.1,0.75,1.1; bands 0<α<0.5 monotone, α=0.5 one step, 0.5<α<1 oscillating convergence, α=1 permanent oscillation, α>1 divergence. (b) D is momentum with α=0.1, β=0.5; step-3 check x3=0.302. (c) α=0.75,0.375,0.25; x=−0.5,−0.125,−0.0625. (d) t=7, α7=0.09375; 87.5% drop; the factor turns positive at t=1.
Remember
On a quadratic, plain descent is a geometric sequence — so always divide consecutive iterates first. A constant ratio means plain descent and hands you α; a drifting ratio means something is carrying memory. The slip is trying to fit β from step 1, where the trolley is still empty and β cannot appear: step 1 gives α, step 2 gives β, step 3 checks them both.
Problem 3medium
Let f(x,y)=2x2+xy+y2−2x−y, which is 21w⊤Aw−b⊤w with A=[4112] and b=(2,1); start at w0=(0,0), where ∇f=(4x+y−2,x+2y−1). (a) With direction d1=(1,0), show it is a descent direction, write h(α)=f(w0+αd1), minimise it exactly, and give w1 and f(w1). (b) Take d2=−∇f(w1) and repeat: give h(α), α2∗, w2 and f(w2). (c) Derive the closed form α∗=−d⊤Ad∇f(w)⊤d and evaluate it for (a) and (b). (d) Give the exact minimiser w∗ and f∗, and the amount by which f(w2) still exceeds f∗. Also verify the free check ∇f(w1)⊤d1=0 and ∇f(w2)⊤d2=0.
What this tests. That "how far do I walk?" is itself a one-variable minimisation, that on a quadratic it has a formula, and that an exact line search always leaves the new gradient perpendicular to the direction just walked. Plan. Substitute the line into f to get a parabola in α; set h′(α)=0; step; repeat once; then do the same substitution with symbols to get the formula, and finish with ∇f=0 for the exact answer.
Show the full solution
(a) Step 1 — is d1 downhill? At w0=(0,0),
∇f(w0)=(−2,−1),∇f⊤d1=−2<0,
so yes: moving along +x lowers f.
Step 2 — the walk becomes a parabola. Put (x,y)=(α,0) into f:
h(α)=2α2+α(0)+0−2α−0=2α2−2α.
Minimise it:
h′(α)α1∗=4α−2=0,=0.5,h′′=4>0.w1f(w1)=(0,0)+0.5(1,0)=(0.5,0),=2(0.25)−2(0.5)=−0.5.
(b) Step 3 — the second leg. The gradient at w1:
∇f(w1)d2=(4(0.5)+0−2,0.5+0−1)=(0,−0.5),=−∇f(w1)=(0,0.5).
The line is (0.5,0.5α). Substitute, term by term:
2x2xyy2−2x=2(0.25)=0.5,=0.5(0.5α)=0.25α,=0.25α2,=−1,−y=−0.5α.
Add:
h(α)=0.25α2+0.25α−0.5α+0.5−1=0.25α2−0.25α−0.5.h′(α)α2∗w2f(w2)=0.5α−0.25=0,=0.5,=(0.5,0)+0.5(0,0.5)=(0.5,0.25),=0.25(0.25)−0.25(0.5)−0.5=0.0625−0.125−0.5=−0.5625.
(c) Step 4 — the formula, once and for all. Expand f(w+αd) with f=21w⊤Aw−b⊤w:
f(w+αd)=21(w+αd)⊤A(w+αd)−b⊤(w+αd).
Because A is symmetric, w⊤Ad=d⊤Aw, so the two cross terms merge:
=f(w)+αd⊤(Aw−b)+2α2d⊤Ad.
But Aw−b=∇f(w), so this is a parabola in α with slope ∇f⊤d and curvature d⊤Ad. Setting the derivative to zero:
α∗=−d⊤Ad∇f(w)⊤d.
Check it on both legs:
(a)d1⊤Ad1α1∗(b)∇f(w1)⊤d2d2⊤Ad2α2∗=4,=−4−2=0.5✓=−0.25,=2(0.5)2=0.5,=−0.5−0.25=0.5✓
(d) Step 5 — the exact bottom, and how close we got. Set ∇f=0:
4x+yx+2y=2,=1.
From the first, y=2−4x; substitute:
x+2(2−4x)−7xy=1,=−3,x=73,=2−712=72.
Evaluate over a denominator of 49:
f∗=4918+496+494−4942−4914=−4928=−74≈−0.571429.
Two exact line searches got to −0.5625, still
−0.5625−(−0.571429)=0.008929
above the floor.
Step 6 — the free check. After an exact line search the parabola is at its bottom, so the directional derivative along d is zero — i.e. the new gradient is perpendicular to the direction just walked:
∇f(w1)⊤d1∇f(w2)∇f(w2)⊤d2=(0,−0.5)⋅(1,0)=0,=(0.25,0),=(0.25,0)⋅(0,0.5)=0.
Both are exactly zero, which is why consecutive exact-search directions turn a right angle — the zig-zag is not a bug, it is a theorem.
answers at a glance: (a) descent since −2<0; h=2α2−2α, α1∗=0.5, w1=(0.5,0), f=−0.5. (b) h=0.25α2−0.25α−0.5, α2∗=0.5, w2=(0.5,0.25), f=−0.5625. (c) α∗=−∇f⊤d/(d⊤Ad); 2/4=0.5 and 0.25/0.5=0.5. (d) w∗=(3/7,2/7), f∗=−4/7≈−0.571429, excess 0.008929; both orthogonality checks give 0.
Remember
"How far?" is its own one-variable problem, and on a quadratic its answer is −∇f⊤d/(d⊤Ad) — slope over curvature, measured along the direction you are actually walking. Always spend the one line on ∇f(wnew)⊤d=0: if it is not zero, the line search was not exact. The slip is minimising f over (x,y) instead of over the single number α.
Problem 4medium
A run of momentum on f(x)=(x−5)2 starts at x0=0 with v0=0; the log records x1=1.0 and x2=2.6, and nothing else. (a) Recover α and β, in that order, saying why the order is forced. (b) Continue the run: give f′(x2), v3, x3, f′(x3), v4 and x4. (c) Run plain gradient descent from x0=0 with the same α for four steps, and give the two distances from the target x=5 after four steps — one for momentum, one for plain descent — saying which is past and which is short.
What this tests. Reading the loaded trolley backwards: v0=0 makes the first step pure descent, so α falls out alone and β shows up only at step 2 — and then whether you can see the overshoot that memory buys. Plan. One step with α unknown; one step with β unknown; then roll the recursion forward two more rows; finally run the plain map x←0.8x+1 four times and subtract.
Show the full solution
(a) Step 1 — step 1 has no β in it. The gradient is f′(x)=2(x−5), so f′(0)=−10. With v0=0,
v1x1α=β(0)−α(−10)=10α,=0+10α=1.0,=0.1,v1=1.0.
The empty trolley is what makes this identification possible: β multiplies v0=0 and disappears.
Step 2 — β from the second step.f′(1.0)=2(1−5)=−8:
v2x21.8+βv2=β(1.0)−0.1(−8)=β+0.8,=1.0+β+0.8=1.8+β,=2.6⇒β=0.8,=1.6.
(b) Step 3 — two more rows.f′(2.6)v3x3=2(2.6−5)=−4.8,=0.8(1.6)−0.1(−4.8)=1.28+0.48=1.76,=2.6+1.76=4.36.f′(4.36)v4x4=2(4.36−5)=−1.28,=0.8(1.76)−0.1(−1.28)=1.408+0.128=1.536,=4.36+1.536=5.896.
Note what happened at the last row: the pull 0.128 was tiny, but the trolley still carried 1.408 — so the walker sailed straight past 5.
t
xt
f′(xt)
vt+1
0
0
−10
1.0
1
1.0
−8
1.6
2
2.6
−4.8
1.76
3
4.36
−1.28
1.536
4
5.896
—
—
(c) Step 4 — the same rate without the trolley. Plain descent is
x←x−0.1⋅2(x−5)=x−0.2x+1=0.8x+1.
Four applications from 0:
x1x2x3x4=0.8(0)+1=1,=0.8(1)+1=1.8,=0.8(1.8)+1=2.44,=0.8(2.44)+1=2.952.
The two distances after four steps:
momentum: plain: 5.896−5=0.896past,5−2.952=2.048short.
Same α, same four steps: memory covered 5.896 of the ground while plain descent covered 2.952 — but it bought that speed with an overshoot of 0.896, which it will now have to walk back.
answers at a glance: (a) α=0.1 (from step 1, where v0=0 hides β), then β=0.8. (b) f′(2.6)=−4.8, v3=1.76, x3=4.36; f′(4.36)=−1.28, v4=1.536, x4=5.896. (c) plain run 1,1.8,2.44,2.952; momentum ends 0.896 past the target, plain descent 2.048 short of it.
Remember
v0=0 is the crack that lets you read a momentum log backwards: step 1 is pure descent and gives α; only step 2 can give β. The slip is fitting both at once from step 2 and getting a whole family of answers. The second thing to keep: momentum overshoots by design — the trolley keeps rolling after the slope has flattened — which is exactly what makes it fast in a long valley and jumpy near the bottom.
Problem 5medium
A single weight sits on a long, perfectly straight slope: dL/dw=g=4 at every iteration. Take α=1 and ignore ϵ. (a) Give AdaGrad's accumulator Gt in closed form, show its step size is α/t, and give the first four step sizes. (b) Give the first t at which AdaGrad's step has fallen below 10% of α. (c) For RMSProp with ρ=0.5, prove At=g2(1−ρt) by unrolling the geometric series, then give the first four step sizes and the value they approach. (d) Give the two limits as t→∞ and the step each method takes at t=100, plus the ratio between them.
What this tests. The permanent record against form-not-career-average, on the one input where they visibly disagree: a slope that never changes. Plan. Sum t copies of g2 for AdaGrad and cancel g against g2; for RMSProp unroll At=ρAt−1+(1−ρ)g2 into a geometric series and use 1+ρ+⋯+ρt−1=(1−ρt)/(1−ρ); then two limits and one division.
Show the full solution
(a) Step 1 — the permanent record never forgets. AdaGrad adds g2 every iteration and never subtracts, so after t iterations
Gt=ttermsg2+g2+⋯+g2=tg2=16t.
The step size is therefore
Gtαg=tg2αg=∣g∣tαg=tα
for g>0. The size of the slope cancels completely — only the count of steps survives. With α=1:
t=1:t=2:t=3:t=4:1/1=1,1/2=0.70711,1/3=0.57735,1/4=0.5.
(Arithmetic check: G1=16,16=4,αg/G1=4/4=1 ✓; G2=32,32=5.65685,4/5.65685=0.70711 ✓.)
(b) Step 2 — when the record strangles the walker.tαtt<0.1α>10>100,
so from t=101 onward. At t=100 the step is exactly 0.1α; at t=101 it is 0.099504α. Nothing about the problem changed — the brake came purely from the step count.
(c) Step 3 — unroll RMSProp. Write c=1−ρ and start from A0=0:
A1A2A3At=cg2,=ρcg2+cg2=cg2(1+ρ),=cg2(1+ρ+ρ2),=cg2(1+ρ+⋯+ρt−1).
The bracket is a geometric series:
1+ρ+⋯+ρt−1At=1−ρ1−ρt,=(1−ρ)g2⋅1−ρ1−ρt=g2(1−ρt).
So the step size is
g2(1−ρt)αg=1−ρtα.
With ρ=0.5 and α=1:
t=1:t=2:t=3:t=4:1/0.5=1.41421,1/0.75=1.15470,1/0.875=1.06904,1/0.9375=1.03280.
As t grows, ρt→0 and the step settles at α=1. Notice it comes down toα from above: the empty notebook at t=1 makes the first step 1/1−ρ=1.41421 times too big, and that inflation fades.
(d) Step 4 — the two limits, side by side.AdaGrad: RMSProp: tα⟶0,1−ρtα⟶α=1.
At t=100:
AdaGrad: RMSProp: ratio: 1001=0.1,1−0.51001=1.0000,0.11.0000=10.
(0.5100≈7.9×10−31, so RMSProp's step at t=100 is 1 to thirty decimal places.) On a slope that genuinely never ends, AdaGrad is ten times slower than RMSProp by step 100 and the gap keeps widening as t.
answers at a glance: (a) Gt=16t, step =α/t: 1,0.70711,0.57735,0.5. (b) from t=101. (c) At=g2(1−ρt), step =α/1−ρt: 1.41421,1.15470,1.06904,1.03280→α=1. (d) limits 0 and α=1; at t=100, 0.1 versus 1.0000, a ratio of 10.
Remember
Both methods divide by a root of remembered squares; the only difference is whether the memory is a permanent record (AdaGrad, sum) or recent form (RMSProp, fading average). On a constant slope that difference is α/t→0 against α/1−ρt→α — a brake that never lifts, against one that lifts after a few steps. The slip is thinking AdaGrad's shrinking step means "converging": here nothing has converged at all, the walker has simply been throttled.
Problem 6hard
A model y^=w1x1+w2x2 is fitted to two rows, (10,1)↦21 and (10,−1)↦19, with L=21∑i(y^i−yi)2. (a) Write ∂L/∂wj in terms of the residuals and evaluate ∇L at w0=(0,0). (b) Give H=X⊤X, the range of α for which plain descent is stable, the optimum w∗, and — at α=0.005 — the first move of w2, its per-step contraction factor, the number of steps it needs to close 99% of its gap, and what w1 does in one step. (c) Run RMSProp with ρ=0.9, α=0.3 for two steps, showing At, At and the step vector each time. (d) Give w2 after two RMSProp steps and after two plain steps at α=0.005, and the ratio.
What this tests. The whole reason per-weight step sizes exist: one column is ten times bigger than the other, so the curvature ratio is a hundred, and one shared rate cannot serve both. Plan. Residual times feature, summed, gives the gradient; X⊤X gives the curvature and the speed limit; then run RMSProp in vector form keeping every intermediate to six decimals — the point is that its two steps come out equal on the first iteration even though the gradients differ by a factor of 200.
Show the full solution
(a) Step 1 — gradient as residual times feature. With ri=y^i−yi,
∂wj∂L=i∑rixij.
At w0=(0,0) both predictions are 0, so r=(−21,−19) and
∂w1∂L∂w2∂L=(−21)(10)+(−19)(10)=−210−190=−400,=(−21)(1)+(−19)(−1)=−21+19=−2.
So ∇L=(−400,−2): the two partials differ by a factor of 200 at the very first point, purely because column 1 is ten times larger.
(b) Step 2 — curvature, speed limit, optimum. With X=[10101−1],
X⊤X=[100+10010−1010−101+1]=[200002].
Diagonal, so the two coordinates never talk to each other; the eigenvalues are 200 and 2 and the condition number is 100. Stability needs α<2/λmax:
0<α<2002=0.01.
The optimum solves X⊤Xw=X⊤y with X⊤y=(400,2):
w∗=(200400,22)=(2,1).
Now take the largest rate the problem allows on the small side, α=0.005:
Δw2factor0.99nn=0.005×2=0.01,=1−0.005(2)=0.99,≤0.01≥ln0.99ln0.01=458.21,
so 459 steps — call it about 460 — for w2 to close 99% of its gap. Meanwhile
factor for w1=1−0.005(200)=0,
so w1 lands exactly on 2 in a single step and then never moves again. One rate, two completely different lives: one knob finished before the first step ended, the other needs four hundred and fifty-nine.
(c) Step 3 — RMSProp, first iteration.ρ=0.9, α=0.3, A0=0, g0=(−400,−2):
A1A1=0.1g02=0.1(160000,4)=(16000,0.4),=(126.4911,0.632456).stepw1=126.49110.3(−400),0.6324560.3(−2)=(−0.948683,−0.948683),=(0.948683,0.948683).
The two moves are identical although the gradients differed by 200×: on the first step A1=0.1∣g∣, so g cancels and every coordinate moves α/1−ρ=0.948683 in the downhill direction.
Step 4 — second iteration. New predictions and residuals:
y^1r1y^2r2=10(0.948683)+0.948683=10.435516,=10.435516−21=−10.564484,=10(0.948683)−0.948683=8.538150,=8.538150−19=−10.461850.
New gradient:
g1,1g1,2=10(−10.564484)+10(−10.461850)=−210.263340,=(−10.564484)−(−10.461850)=−0.102633.
Fade the notebook and add the new squares:
A2A2=0.9(16000,0.4)+0.1(44210.67,0.010534)=(18821.067,0.3610534),=(137.189895,0.600877).stepw2=137.1898950.3(−210.263340),0.6008770.3(−0.102633)=(−0.459793,−0.051242),=(1.408477,0.999925).
Two steps have taken w2 to within 0.000075 of its optimum 1.
(d) Step 5 — the comparison in one line. Two plain steps at α=0.005 leave w2 at
w2(1)w2(2)=0+0.005(2)=0.01,=0.01+0.005(1.98)=0.0199.
Against RMSProp's 0.999925:
0.01990.999925=50.25.
RMSProp has moved the stiff knob fifty times further in the same two steps — and it did it without needing to know that column 2 was small, because the notebook measured that for itself.
answers at a glance: (a) r=(−21,−19), ∇L=(−400,−2). (b) H=diag(200,2), stable for 0<α<0.01, w∗=(2,1); at α=0.005: Δw2=0.01, factor 0.99, 459 steps for 99%, and w1's factor is 0 so it lands in one step. (c) w1=(0.948683,0.948683); w2=(1.408477,0.999925). (d) 0.999925 versus 0.0199, a ratio of 50.25.
Remember
Divide by the root of a remembered square and the gradient's size cancels — what is left is its direction, times a step the method sets for each weight separately. That is why RMSProp's first move is α/1−ρ in every coordinate no matter how lopsided the columns are. The slip is fading the notebook with the new squared gradient on the first step and forgetting the 1−ρ factor: A1=(1−ρ)g02, not g02.
Problem 7hard
Three gradients were logged for one weight: g0=6,g1=−4,g2=2. Run Adam by hand with α=0.1, β1=0.9, β2=0.999, m0=v0=0 and w0=1. (a) Tabulate t=1,2,3: first the two correction denominators 1−β1t and 1−β2t, then mt,vt,m^t,v^t,v^t, the ratio m^t/v^t and wt. (b) Give the three iterates plain gradient descent would have produced at the same α on the same gradients. (c) Give the three Adam step sizes, and give the number m^2/v^2 together with the two averages that produced it — say which average can cancel and which cannot.
What this tests. The two notebooks and the probation rate, in full arithmetic: a signed average on top, a squared average underneath, and a start-up correction that makes step 1 honest. Plan. Compute the two denominators first — they are the same every run and are where most slips live — then one row at a time; never reuse a corrected value in the next row's recursion (the recursion runs on the raw mt,vt).
Show the full solution
(a) Step 1 — the two probation denominators.1−β1t1−β2t:0.1,0.19,0.271,:0.001,0.001999,0.002997001.
(1−0.92=1−0.81=0.19; 1−0.93=1−0.729=0.271; 1−0.9992=1−0.998001=0.001999; 1−0.9993=1−0.997002999=0.002997001.) Both start tiny and climb toward 1, which is exactly what inflates the nearly empty notebooks back to honest size.
Step 2 — t=1, using g0=6.m1v1m^1v^1v^1v^1m^1w1=0.9(0)+0.1(6)=0.6,=0.999(0)+0.001(36)=0.036,=0.10.6=6,=0.0010.036=36,=6,=66=1,=1−0.1(1)=0.9.
The ratio is exactly 1: after correction the first step is α in the downhill direction, whatever the gradient was.
Step 3 — t=2, using g1=−4.m2v2=0.9(0.6)+0.1(−4)=0.54−0.4=0.14,=0.999(0.036)+0.001(16)=0.035964+0.016=0.051964.m^2v^2v^2v^2m^2w2=0.190.14=0.736842,=0.0019990.051964=25.994997,=5.098529,=0.144521,=0.9−0.1(0.144521)=0.885548.
Step 4 — t=3, using g2=2.m3v3=0.9(0.14)+0.1(2)=0.126+0.2=0.326,=0.999(0.051964)+0.001(4)=0.051912036+0.004=0.055912036.m^3v^3v^3v^3m^3w3=0.2710.326=1.202952,=0.0029970010.055912036=18.655995,=4.319259,=0.278509,=0.885548−0.0278509=0.857697.
The whole run:
t
mt
vt
m^t
v^t
ratio
wt
1
0.6
0.036
6
6
1
0.9
2
0.14
0.051964
0.736842
5.098529
0.144521
0.885548
3
0.326
0.055912
1.202952
4.319259
0.278509
0.857697
(b) Step 5 — what plain descent would have done.w←w−0.1g on the same three gradients:
w1w2w3=1−0.1(6)=0.4,=0.4−0.1(−4)=0.8,=0.8−0.1(2)=0.6.
Plain descent lurched 0.6, then 0.4 back, then 0.2 forward — total travel 1.2 to end 0.4 from the start. Adam travelled 0.142 in total and ended 0.142 from the start: same three gradients, a tenth of the thrashing.
(c) Step 6 — the three step sizes, and why the middle one is tiny. Each step is α times the ratio:
t=1:t=2:t=3:0.1(1)=0.1,0.1(0.144521)=0.014452,0.1(0.278509)=0.027851.
The middle ratio is m^2/v^2=0.736842/5.098529=0.144521. Look at what each average did with the pair (6,−4):
signed top: squared bottom: 0.9(0.6)+0.1(−4)=0.14,0.999(0.036)+0.001(16)=0.051964.
The top averages signed gradients, so +6 and −4 nearly cancel and the numerator collapses to 0.14. The bottom averages squares, which are all positive and can never cancel, so it stays large. A ratio of about 0.14 is Adam saying: "the last two reports disagreed about the direction, so take a small step until they agree again."
answers at a glance: (a) denominators 0.1,0.19,0.271 and 0.001,0.001999,0.002997001; w1=0.9, w2=0.885548, w3=0.857697. (b) plain descent gives 0.4,0.8,0.6. (c) step sizes 0.1,0.014452,0.027851; m^2/v^2=0.144521, small because the signed average 0.14 nearly cancelled while the squared average 0.051964 could not.
Remember
Adam divides a signed average by the root of a squared average: disagreement shrinks the numerator but never the denominator, so conflicting gradients automatically produce small steps. The probation correction is what makes step 1 come out at exactly α. The slip is feeding the corrected m^t,v^t back into the next row — the recursion always runs on the raw mt,vt, and the correction is applied fresh each time.
Problem 8easy
You have 20 metres of fencing and want to enclose the largest possible rectangular plot. (a) Name the decision variables, the objective and the constraint, and reduce the perimeter equation to its simplest form. (b) Solve with one multiplier: give λ∗, x∗, y∗ and the area A∗, and confirm it is a maximum by eliminating one variable. (c) The fencing budget rises to 22 metres. Give the new optimum and area, the gain the multiplier predicts, the gain that actually occurs, the difference between them, and the exact value function A∗(s) together with its slope at s=10.
What this tests. Framing — what may I choose, what do I want, what limits me — and then the multiplier's second life as the price of a wall: how much the best attainable value improves per unit of extra budget. Plan. Three sentences of framing, then ∇f=λ∇h and the constraint; then re-solve at the new budget and compare λΔs against the true jump, and explain the difference with the value function.
Show the full solution
(a) Step 1 — frame it in three lines. Let x>0 be the width and y>0 the height, in metres. The area to maximise is f(x,y)=xy. The fencing is all used, so the perimeter is
2x+2y=20⟹h(x,y)=x+y−10=0.
Framed problem: maxx,yxy subject to x+y=10. Call the half-perimeter s=10 the budget; it is the thing whose price we will ask for in (c).
(b) Step 2 — one multiplier.∇f=(y,x) and ∇h=(1,1), so ∇f=λ∇h reads
yx=λ(1)=λ,=λ(1)=λ.
Both equations say the same thing, x=y=λ. Feed that into the constraint:
λ+λλ∗A∗=10,=5,x∗=y∗=5,=5×5=25m2.
Confirm it is a maximum without any second-derivative test: on the constraint line y=10−x, so
A(x)=x(10−x)=10x−x2,
a downward parabola whose single critical point is its peak, and whose value collapses to 0 at both ends x→0 and x→10. The square wins.
(c) Step 3 — the price of a wall. With 22 m the budget becomes s=11, i.e. x+y=11; the same algebra gives
x∗=y∗A∗=5.5,=5.5×5.5=30.25m2.
Compare the prediction with the fact:
predicted gaintrue gaindifference=λ∗Δs=5(1)=5,=30.25−25=5.25,=0.25.
Step 4 — where the missing 0.25 lives. Solve at a general budget s: x∗=y∗=s/2, so the exact value function is
A∗(s)=(2s)2=4s2,dsdA∗=2s.
At s=10 that slope is 5 — which is exactly λ∗. So the multiplier is the derivative of the best attainable value with respect to the budget, and a derivative is only exact for an infinitesimal change. Over a whole unit the curve bends upward:
A∗(11)−A∗(10)linear partcurvature part=4121−100=421=5.25,=5,=4(Δs)2=0.25.
The 0.25 is precisely the quadratic term of s2/4. Ask the multiplier for a small favour and it answers exactly; ask it for a big one and it under-promises.
answers at a glance: (a) variables x,y>0; maxxy subject to x+y−10=0. (b) λ∗=5, x∗=y∗=5, A∗=25 m². (c) new optimum 5.5,5.5 with A∗=30.25; predicted gain 5, true gain 5.25, difference 0.25; A∗(s)=s2/4 with slope s/2=5 at s=10.
Remember
The multiplier is not a bookkeeping nuisance — it is the price of one more unit of budget, λ=dA∗/ds, available before you re-solve anything. The slip is expecting that price to be exact for a large change: it is a slope, so it captures the straight-line part and misses the curvature (here 5 predicted against 5.25 delivered). The second slip is forgetting to divide the perimeter by 2 and carrying 2x+2y−20, which scales λ by a half.
Problem 9easy
(a) Put each of these into the standard form minf subject to e=0,g≤0, keeping every sign explicit and giving the gradient of each converted rule: (i) x≥2; (ii) x+2y≥5; (iii) 3x−y≤7; (iv) x+y=1; (v) maxxy; (vi) x>2 — for this last one, state what goes wrong and name the value that cannot be attained. (b) Complementary slackness splits the search into branches. Give the number of branches for m=1,2,3,4,10 fences, and say for which of m=2,3,4 the guess m2 happens to agree with the true count and for which it fails, with both numbers. (c) For a problem with one path and no fences, name which of the five conditions are empty and write down what survives. (d) In the slack formulation with n variables and m fences, count the unknowns; evaluate for n=2,m=2.
What this tests. The bookkeeping that everything else rests on — every rule pushed to the ≤0 side, every maximisation flipped — and the size of the branching interrogation that complementary slackness sets up. Plan. Move everything to one side so the right-hand side is 0 and the sense is ≤; negate the objective to flip a max; then count branches as 2 per inequality and nothing per equality.
Show the full solution
(a) Step 1 — six conversions.
as written
standard form
gradient
x≥2
g=2−x≤0
∇g=(−1)
x+2y≥5
g=5−x−2y≤0
∇g=(−1,−2)
3x−y≤7
g=3x−y−7≤0
∇g=(3,−1)
x+y=1
e=x+y−1=0
∇e=(1,1)
maxxy
min(−xy)
∇f=(−y,−x)
x>2
not allowed
—
A ≥ becomes a ≤ by multiplying through by −1, which also flips the gradient — that sign is the whole content of the first two rows. The last row is different in kind: with x>2 the feasible set is open, the infimum is 2, and 2 is excluded. For any allowed x the point (x+2)/2 is still allowed and strictly better, so no minimiser exists. Every fence in this subject is closed: ≤, never <.
(b) Step 2 — how big is the interrogation? Each fence contributes exactly two branches — its fine is zero, or it is touched — and the branches multiply. An equality contributes none, because it is always active. So with m fences the count is 2m:
m=1:m=2:m=3:m=4:m=10:21=2,22=4,23=8,24=16,210=1024.
The tempting guess m2 agrees by coincidence at m=2 (4=4) and at m=4 (16=16), and fails at m=3, where the truth is 8 and m2 says 9. Two agreements are not a pattern: 210=1024 against m2=100 settles it.
(c) Step 3 — one path, no fences. Of the five conditions — stationarity, path feasibility, fence feasibility, complementary slackness, and non-negative fines — the last three are about fences, so with no fences they are empty. What survives is exactly two lines:
∇f+λ∇e=0,e=0.
That is the plain Lagrange recipe: the constrained problem with only equalities never needs a case split, and λ is free to take either sign.
(d) Step 4 — counting unknowns in the slack formulation. Writing each fence as gi+ti2=0 with a slack ti, the unknowns are
+++=nvariables1path multiplier λmfence multipliers μimslacks tin+2m+1.
For n=2 variables and m=2 fences: 2+4+1=7 unknowns — which is why the branching version, solving four small systems, beats the one big system in practice.
answers at a glance: (a) 2−x≤0(∇=−1); 5−x−2y≤0(∇=(−1,−2)); 3x−y−7≤0(∇=(3,−1)); x+y−1=0(∇=(1,1)); min(−xy); x>2 is not allowed — the infimum 2 is excluded, so no minimiser exists. (b) 2,4,8,16,1024; m2 agrees at m=2 and m=4, fails at m=3 (8, not 9). (c) fence feasibility, complementary slackness and μ≥0 are empty; ∇f+λ∇e=0 and e=0 survive. (d) n+2m+1; for n=2,m=2 that is 7.
Remember
Standard form first, every time: right-hand side 0, sense ≤, maximisation negated. A ≥ that is not flipped puts the wrong sign on ∇g and then the fine comes out negative and the whole branch is thrown away for the wrong reason. And count branches as 2m in the number of inequalities only — equalities never branch, because they are never slack.
Problem 10medium
Maximise and minimise f(v)=v⊤Av with A=[5222] subject to v⊤v=1. (a) Write ∇f and ∇h, impose ∇f=λ∇h, and simplify the resulting system to one familiar matrix equation. (b) Give the characteristic equation and both values of λ. (c) Give the maximum and minimum of f and the unit vectors where each is attained, to six decimals. (d) Verify the maximum by direct substitution, showing the arithmetic, and verify that the two optimisers are orthogonal.
What this tests. That the tangency condition on the unit circle is the eigenvalue equation, and that the constrained values of a quadratic form are exactly the eigenvalues. Plan. Differentiate both sides, divide out the 2, read off Av=λv; then trace and determinant give the characteristic polynomial; then f=v⊤Av=v⊤(λv)=λ on a unit eigenvector, so the values need no further work.
Show the full solution
(a) Step 1 — the condition is the eigenvalue equation. With f=5x2+4xy+2y2 and h=x2+y2−1,
∇f∇h=(10x+4y,4x+4y)=2Av,=(2x,2y)=2v.
So ∇f=λ∇h reads 2Av=λ2v; cancel the 2:
Av=λv.
The candidates are not "some points found by calculus" — they are the unit eigenvectors of A, and the multiplier is the eigenvalue. Moreover, at any such candidate
f=v⊤Av=v⊤(λv)=λ∥v∥2=λ,
so the constrained values are the eigenvalues.
(b) Step 2 — the two eigenvalues.trA=7, detA=10−4=6:
λ2−7λ+6(λ−6)(λ−1)λ=0,=0,=6 or λ=1.
(c) Step 3 — the two directions. For λ=6, solve (A−6I)v=0:
−x+2yv=0⇒x=2y,=5(2,1)=(0.894427,0.447214).
For λ=1, solve (A−I)v=0:
4x+2yv=0⇒y=−2x,=5(−1,2)=(−0.447214,0.894427).
Both signs work, since −v is also a unit eigenvector. So
maxfminf=6at±(0.894427,0.447214),=1at±(−0.447214,0.894427).
(d) Step 4 — two checks. Substitute (2,1)/5 into f=5x2+4xy+2y2, pulling out the 1/5:
f=51[5(4)+4(2)(1)+2(1)]=51[20+8+2]=530=6.
That is λmax, as promised. ✓ And the two optimisers are perpendicular:
(2,1)⋅(−1,2)=−2+2=0.
A symmetric matrix always hands back orthogonal directions for distinct eigenvalues, which is why the largest and smallest values of a quadratic form sit at right angles to each other — the long and short axes of the same ellipse.
answers at a glance: (a) ∇f=2Av, ∇h=2v, so Av=λv. (b) λ2−7λ+6=0, λ=6,1. (c) maxf=6 at ±(0.894427,0.447214); minf=1 at ±(−0.447214,0.894427). (d) direct check gives 30/5=6; dot product =0.
Remember
"Maximise a quadratic form on the unit sphere" is the eigenvalue problem wearing a different hat — which is exactly how the first principal component is found. Once you recognise Av=λv, stop computing: on a unit eigenvector f equals λ, so the answers are already on the page. The slip is forgetting to normalise: (2,1) gives f=30, not 6, because f scales with ∥v∥2.
Problem 11medium
Minimise f(x)=(x−3)2 subject to x≤1. (a) Put it in standard form and work both branches of the fine-or-no-fine split; say which branch dies and on which condition, give μ∗, check all five conditions, and give p∗. (b) Write the Lagrangian and minimise it over x for a fixed μ, confirming it really is a minimum. (c) Substitute back to get d(μ) in closed form and say what shape it is. (d) Solve maxμ≥0d(μ): give μ∗, d∗ and the gap p∗−d∗; recover x∗ from μ∗ and verify complementary slackness.
What this tests. The same one-fence problem answered twice — once by the branching interrogation, once by turning the wall into a fine — and the fact that the two answers agree. Plan. Branch on μ=0 versus g=0 and kill the loser on a named condition; then build d(μ)=minxL by substituting the inner minimiser, and maximise the resulting parabola over μ≥0.
Show the full solution
(a) Step 1 — the branching interrogation, two branches. Standard form: g(x)=x−1≤0, and stationarity of L=(x−3)2+μ(x−1) is
2(x−3)+μ=0.Branch 1, μ=0 (the fence does nothing). Then 2(x−3)=0, so x=3. Check the fence: g(3)=3−1=2>0. The point is outside. Rejected on fence feasibility. Branch 2, g=0 (pressed against the fence). Then x=1, and stationarity gives
2(1−3)+μ−4+μμ∗=0,=0,=4(≥0✓).
All five conditions at (x,μ)=(1,4): stationarity −4+4=0 ✓; no path to check; fence feasibility g=0≤0 ✓; complementary slackness μg=4(0)=0 ✓; μ=4≥0 ✓. So
p∗=(1−3)2=4.
(b) Step 2 — turn the wall into a fine.L(x,μ)=(x−3)2+μ(x−1).
For a fixed μ this is a parabola in x opening upward, so its minimum is where the derivative vanishes:
∂x∂Lx∂x2∂2L=2(x−3)+μ=0,=3−2μ,=2>0⇒a minimum.
Read that inner answer: at zero fine the walker goes straight to 3 and ignores the wall; each unit of fine drags it back by 21.
(c) Step 3 — the dual function. Substitute x=3−μ/2 back into L. The first bracket becomes −μ/2 and the second becomes 2−μ/2:
d(μ)=(−2μ)2+μ(2−2μ)=4μ2+2μ−2μ2=2μ−4μ2.
The μ2 coefficient is 41−21=−41<0, so d is an upside-down parabola — concave, with a single peak. Every value it takes is a guaranteed floor under p∗: d(0)=0, d(2)=4−1=3, d(6)=12−9=3, all at or below 4.
(d) Step 4 — climb the hill and compare.d′(μ)μ∗d∗=2−2μ=0,=4(≥0✓),=2(4)−416=8−4=4.
The gap:
p∗−d∗=4−4=0,
zero — strong duality. Recover the primal point from the inner minimiser at μ∗:
x∗=3−24=1✓
which is the same x∗ branch 2 produced, and complementary slackness holds there:
μ∗g(x∗)=4(1−1)=4(0)=0.✓
Two completely different routes — case analysis on the primal, hill-climbing on the dual — and they meet at the same μ=4, the same x=1, the same value 4.
answers at a glance: (a) branch μ=0 gives x=3 and dies on fence feasibility (g=2>0); branch g=0 gives x∗=1, μ∗=4, all five conditions hold, p∗=4. (b) x=3−μ/2, with ∂2L/∂x2=2>0. (c) d(μ)=2μ−μ2/4, a concave (downward) parabola. (d) μ∗=4, d∗=4, gap =0; recovered x∗=1 and μ∗g(x∗)=0.
Remember
Rejecting a branch is progress, not failure — but you must name which condition killed it: μ=0 here died on feasibility, and a branch that returns μ<0 dies on the sign condition instead. The other thing to keep: the dual is built by substituting the inner minimiser back in, so it is a function of μ alone — if an x is still visible in your d(μ), the substitution was not finished.
Problem 12medium
Minimise f(x,y)=x2+2y2 subject to x+y=1, x≥0 and y≥0. (a) Put it in standard form, say how many cases the interrogation has, and write the Lagrangian. (b) Write the two stationarity equations as expressions for μ1 and μ2, and use the path to eliminate y from the second. (c) Work all four cases: for each, give the point, the multipliers, and either the value of f or the exact condition that rejects it. (d) Give λ∗ and say why its sign is legal; give μ1∗,μ2∗ and verify directly what they claim about the two fences; and state why the surviving point is the global minimum.
What this tests. A complete four-case interrogation with one path and two fences, and the discipline of rejecting each losing case on a named condition rather than by eye. Plan. Standard form and the Lagrangian; differentiate once in x and once in y to get the two fines as formulas; then walk the four patterns in order, each time solving the small linear system the pattern leaves behind and checking what the pattern did not enforce.
Show the full solution
(a) Step 1 — standard form. The path is e=x+y−1=0; the two fences are
g1=−x≤0,g2=−y≤0.
Two fences means 22=4 cases. The Lagrangian, with λ free and μ1,μ2≥0:
L=x2+2y2+λ(x+y−1)−μ1x−μ2y.
(b) Step 2 — stationarity, rearranged.∂x∂L∂y∂L=2x+λ−μ1=0⇒μ1=2x+λ,=4y+λ−μ2=0⇒μ2=4y+λ.
The path gives y=1−x, so the second becomes
μ2=4(1−x)+λ=4−4x+λ.
Everything is now in x and λ, which is what makes each case a two-line solve.
(c) Step 3 — case 1: both fences slack (μ1=0,μ2=0).00=2x+λ⇒λ=−2x,=4−4x+λ⇒λ=4x−4.
Equate:
−2x6xyλ=4x−4,=4,x=32,=1−32=31,=−2(32)=−34.
Everything checks: x>0 and y>0 so both fences are respected, both fines are 0 so complementary slackness holds, and μi=0≥0. The value:
f=(32)2+2(31)2=94+92=32.Survives.
Step 4 — the three losers.Case 2: μ1=0, y=0. Then the path forces x=1, and
λμ2=−2x=−2,=4(0)+λ=−2<0.Rejected — a negative fine breaks the sign condition. (A fence is allowed to push, never to pull.) Case 3: x=0, μ2=0. Then y=1, and
0μ1=4(1)+λ⇒λ=−4,=2(0)+λ=−4<0.Rejected on the same sign condition. Case 4: both fences touched, x=0 and y=0. Then
x+y=0=1,
so the point is not on the path at all. Rejected on path feasibility — and note this happens before any multiplier is computed.
case
point
multipliers
verdict
1 (μ1=μ2=0)
(32,31)
λ=−34
survives, f=32
2 (μ1=0,y=0)
(1,0)
λ=−2,μ2=−2
rejected: μ2<0
3 (x=0,μ2=0)
(0,1)
λ=−4,μ1=−4
rejected: μ1<0
4 (x=0,y=0)
(0,0)
—
rejected: off the path
(d) Step 4 — read the answer. Two computable readings of the surviving multipliers.
λ∗=−34<0,
and that is perfectly legal: only fence multipliers carry a sign restriction. A path may be pushed from either side, so λ is free.
μ1∗=μ2∗=0,
which claims both fences are slack. Verify it directly rather than trusting the claim:
g1g2=−x∗=−32<0✓=−y∗=−31<0✓
Both hold with room to spare, so the fences are doing no work — remove them and the answer would not move. Finally, the objective x2+2y2 is a bowl and both rules are linear, so the problem is convex: the single surviving point is the global minimum, not just a candidate.
answers at a glance: (a) e=x+y−1, g1=−x, g2=−y; 4 cases; L=x2+2y2+λ(x+y−1)−μ1x−μ2y. (b) μ1=2x+λ, μ2=4y+λ=4−4x+λ. (c) case 1 survives at (32,31), λ=−34, f=32; case 2 μ2=−2, case 3 μ1=−4, case 4 x+y=0=1. (d) λ∗=−34 is legal because paths are unsigned; μ1∗=μ2∗=0 with g1=−32<0 and g2=−31<0; convex, so it is the global minimum.
Remember
Every case must die of a named cause: infeasible point, or a negative fine. Those are the only two ways out. The classic slip is demanding λ≥0 — the sign condition belongs to fences alone, and a perfectly good answer gets thrown away when a negative λ is treated as an error. The second slip is forgetting to check the conditions the case pattern did not assume: assuming μ1=0 does not make x≥0 true, it must still be verified.
Problem 13hard
Minimise f(x,y)=x2+y2 subject to x+y=4 and x≥3. (a) Put it in standard form, write the Lagrangian and give the two stationarity equations. (b) Work both cases; give x∗,y∗,λ∗,μ∗ and p∗, and say what kills the losing case. (c) Minimise L over (x,y) for fixed multipliers and substitute back to get d(λ,μ), showing where each of the three quadratic coefficients comes from. (d) Give the dual Hessian, its determinant and trace, and both eigenvalues, and conclude the shape of d. (e) Solve the dual: give λ∗,μ∗,d∗, the gap, and the recovered (x∗,y∗). (f) The wall moves to x≥2.9: give the predicted new p∗, the actual one, the exact value function p∗(c) for c≥2, its slope, and the slope's values at c=3 and c=2.
What this tests. The full round trip — primal case analysis, dual construction, dual optimisation, recovery — and then the multiplier read as the price of a wall, including the point where the wall stops being worth anything. Plan. Two cases on the primal; then minimise L in x and y separately, substitute, and collect μ2,λ2,λμ coefficient by coefficient; then two linear equations for the dual optimum; finally differentiate the exact value function.
(b) Step 2 — two cases.Case μ=0. Then 2x+λ=0 and 2y+λ=0 give x=y, and the path gives x=y=2. Check the wall:
g(2)=3−2=1>0,
outside. Rejected on fence feasibility. Case g=0. Then x=3, and the path gives y=1:
2(1)+λ2(3)+(−2)−μ=0⇒λ=−2,=0⇒μ=4(≥0✓).
All five hold — stationarity ✓, path 3+1−4=0 ✓, fence g=0≤0 ✓, μg=4(0)=0 ✓, μ≥0 ✓ — so
p∗=32+12=10.
(c) Step 3 — build the dual. For fixed (λ,μ), L is a sum of two upward parabolas, so its minimiser is
2x+λ−μ=02y+λ=0⇒x=2μ−λ,⇒y=−2λ.
Substitute, one term per line:
x2y2λ(x+y−4)μ(3−x)=4μ2−2λμ+4λ2,=4λ2,=2λμ−λ2−4λ,=3μ−2μ2+2λμ.
(For the third line, x+y=2μ−λ−2λ=2μ−λ.) Now collect the three quadratic coefficients:
μ2:λ2:λμ:41−21=−41,41+41−1=−21,−21+21+21=+21,
and the linear part is −4λ+3μ, so
d(λ,μ)=−4μ2−2λ2+2λμ−4λ+3μ.
(d) Step 4 — the dual is a hill. Second derivatives:
Hd=[−12121−21],detHdtrHd=21−41=41>0,=−1−21=−23<0.
A positive determinant makes the eigenvalues share a sign; a negative trace makes that sign negative. Explicitly, from λ2+23λ+41=0:
λ1,2=4−3±5=−0.190983,−1.309017.
(Check: their sum is −23 and their product is 169−5=41 ✓.) Both negative, so d is concave: one peak, no ridges, no local traps — which is why the dual is always the easy side to optimise.
(e) Step 5 — climb to the top.∂λ∂d∂μ∂d=−λ+2μ−4=0⇒λ=2μ−4,=−2μ+2λ+3=0⇒μ=λ+6.
Substitute the second into the first:
λ2λμ∗=2λ+6−4=2λ−1,=−1,λ∗=−2,=−2+6=4(≥0✓).d∗=−416−24+2(−2)(4)−4(−2)+3(4)=−4−2−4+8+12=10.
So d∗=10=p∗: the gap is 0. Recover the primal point from the inner minimiser:
x∗y∗=24−(−2)=3,=−2−2=1.✓
(f) Step 6 — what the wall is worth. Move it to x≥2.9, a relaxation of 0.1. The multiplier is the price per unit of wall, so
predicted p∗≈10−μ∗(0.1)=10−0.4=9.60.
The truth: the wall is still binding, so x=2.9, y=1.1, and
p∗=(2.9)2+(1.1)2=8.41+1.21=9.62.
Prediction 9.60, fact 9.62 — off by 0.02, the curvature again. Exactly, with the wall at x≥c:
p∗(c)dcdp∗=c2+(4−c)2,c≥2,=2c−2(4−c)=4c−8.
At c=3 the slope is 4, which is μ∗. ✓ At c=2 the slope is 0: there the wall has slid back to the unconstrained answer (2,2), the fence stops biting, and its price falls to nothing. For c<2 the wall is slack, p∗ stays flat at 8, and μ∗=0.
answers at a glance: (a) e=x+y−4, g=3−x; 2x+λ−μ=0, 2y+λ=0. (b) μ=0 gives (2,2) with g=1>0, rejected; g=0 gives x∗=3,y∗=1,λ∗=−2,μ∗=4, p∗=10. (c) d=−4μ2−2λ2+2λμ−4λ+3μ. (d) Hd=[−12121−21], det=41, tr=−23, eigenvalues −0.190983,−1.309017: concave. (e) λ∗=−2, μ∗=4, d∗=10, gap 0, recovered (3,1). (f) predicted 9.60, actual 9.62; p∗(c)=c2+(4−c)2, slope 4c−8, equal to 4 at c=3 and 0 at c=2.
Remember
At the optimum the multiplier is the slope of the value function, so μ∗ tells you what the wall is costing you before you re-solve. Follow that slope far enough and it hits zero, at the moment the wall stops touching the answer — after which relaxing it further buys nothing. The slip is quoting the dual optimum without checking μ≥0: the dual problem is max over μ≥0, and an unconstrained stationary point with μ<0 is not the dual answer.
Problem 14hard
A one-dimensional dataset has two points: x1=+1 with y1=+1, and x2=−1 with y2=−1. The largest-margin classifier solves minw,b21w2 subject to yi(wxi+b)≥1. (a) Write both constraints in standard form and give the Lagrangian with α1,α2≥0. (b) Give the two stationarity equations and reduce the Lagrangian to a function q(α) of a single variable. (c) Maximise q: give α∗, d∗, w∗, b∗, the primal value, the gap, the decision boundary, the margin edges, the margin width, and the number of support vectors. (d) A third point x3=3 with y3=+1 is added: give α3 and say what happens to the classifier. Then, with a point at x3<1 of class +1 and the point at −1 both binding, derive w and b as formulas in x3, and evaluate them, the boundary and the margin at x3=0.5.
What this tests. Every move of the unit chained together — framing, standard form, Lagrangian, dual, solve, recover, read the slackness — on the problem the whole subject is built toward. Plan. Write the two constraints out; differentiate in w and in b (the b-equation is what collapses two multipliers into one); substitute to get a one-variable concave parabola; solve it; then use αi>0⇒ constraint tight to pin b.
Show the full solution
(a) Step 1 — the two constraints, written out. For i=1: y1(wx1+b)=(+1)(w+b)≥1. For i=2: y2(wx2+b)=(−1)(−w+b)=w−b≥1. In standard form,
g1g2=1−w−b≤0,=1−w+b≤0,L=21w2+α1(1−w−b)+α2(1−w+b),αi≥0.
(b) Step 2 — stationarity, and the collapse to one variable.∂w∂L∂b∂L=w−α1−α2=0⇒w=α1+α2,=−α1+α2=0⇒α1=α2.
(These are the two standard identities w=∑iαiyixi and ∑iαiyi=0, written out for this data.) Regroup L:
L=21w2−w(α1+α2)−b(α1−α2)+(α1+α2).
Write α1=α2=α, so the b-term vanishes and w=2α:
q(α)=21(2α)2−(2α)(2α)+2α=2α2−4α2+2α=2α−2α2.
(Cross-check against ∑iαi−21∑i,jαiαjyiyjxixj: here every product yiyjxixj=1, so it reads 2α−21(2α)2=2α−2α2 — the same function.)
(c) Step 3 — solve, recover, read.q′(α)α∗d∗=2−4α=0,=21(≥0✓),=q(21)=1−21=21.
Recover the classifier:
w∗=α1∗+α2∗=21+21=1.
Because α1∗=21>0, complementary slackness forces its constraint tight:
w+bb∗=1,=1−1=0.
Consistency: the second constraint gives w−b=1−0=1, also tight, matching α2∗>0. The primal value is 21(1)2=21=d∗, so the gap is 0. Geometry:
boundary: margin edges: width: w∗x+b∗=0⇒x=0,w∗x+b∗=±1⇒x=±1,∣w∗∣2=2.
Both αi>0, so both points are support vectors: 2 of them, out of 2.
(d) Step 4 — a point that does not matter. Adding x3=3 with y3=+1 adds the constraint 3w+b≥1. At the current answer (w,b)=(1,0) it reads
3(1)+0=3≥1,
slack by 2. In standard form g3=1−3w−b=−2<0, and complementary slackness α3g3=0 with g3=0 forces
α3=0.
Since w=∑iαiyixi, a point with αi=0 contributes nothing: the classifier does not move, and the point can be deleted from the training set without changing a thing.
Step 5 — now move that point inside. Suppose instead the +1 point sits at x3<1, close enough that its constraint becomes tight, with the −1 point at −1 also tight:
wx3+bw−b=1,=1⇒b=w−1.
Substitute:
wx3+w−1w(x3+1)w=1,=2,=x3+12,b=1−wx3=x3+1x3+1−2x3=1+x31−x3.
At x3=0.5:
wbboundary xmargin =1.52=1.3333,=1.50.5=0.3333,=−wb=−1.33330.3333=−0.25,=∣w∣2=1.5.
Dragging the positive point from 3 (where it was ignored entirely) in to 0.5 squeezes the margin from 2 to 1.5 and shifts the boundary from 0 to −0.25. Nothing about the point changed except whether its constraint was tight — and that is the whole difference between a data point that matters and one that does not.
answers at a glance: (a) g1=1−w−b≤0, g2=1−w+b≤0; L=21w2+α1g1+α2g2. (b) w=α1+α2, α1=α2; q(α)=2α−2α2. (c) α∗=21, d∗=21, w∗=1, b∗=0, primal 21, gap 0; boundary x=0, edges x=±1, width 2, 2 support vectors. (d) α3=0 and the classifier does not move; w=2/(x3+1), b=(1−x3)/(1+x3); at x3=0.5, w=1.3333, b=0.3333, boundary −0.25, margin 1.5.
Remember
Complementary slackness is why these classifiers are sparse: αi=0 means the point sits strictly outside the margin and can be thrown away, while αi>0 means its constraint is tight and it is holding the boundary up. The multiplier is the answer to "which data matter". The slip is solving for b from stationarity — ∂L/∂b only gives ∑iαiyi=0 and never mentions b; b comes from setting a support vector's constraint to equality.
You have just maximised a quadratic form on the unit circle and watched the multiplier come out as an eigenvalue. That was not a coincidence — it is the whole of principal component analysis in miniature. Unit 12 asks what a cloud of data looks like from its own best angle, why the directions of greatest spread are the eigenvectors of a covariance matrix, and how much you can throw away before the picture stops being the picture.