Unit 9 · Gradient Descent — The Math Behind the Machine

1

Downhill in the fog

Imagine this

Night, a mountainside, fog so thick you can see one metre of ground around your boots and nothing else. You want the bottom of the valley. No map, no view, no idea where the bottom is. But you have one sense that works perfectly: you can feel which way the ground tilts under your feet. So you face straight downhill, take a step, stop, feel again, turn a little, step again. That is the entire method, and it is enough. Try it — the landscape below is real, and you can only see the lit disc:

Try: press ▶ walk and watch the lit disc slide downhill until the ground goes flat under the walker. Then press lift the fog — there were two valleys all along, and the walk found the one downhill from where it started.

drag the picture to orbit · drag the glowing walker to move it

fog radius R0.9

step size γ0.25

—

Nothing in the rule $\mathbf x\leftarrow\mathbf x-\gamma\nabla f(\mathbf x)$ needs the landscape: only the tilt of the ground under your feet, which the gradient gives. That is the whole reason it scales to a million dimensions — and the whole reason it can only find the valley downhill from where it starts. Drag the walker onto the hilltop to feel a flat spot that is not a bottom.

Three things to take from the fog, because everything else in the unit is a variation on them.

You never needed the map. The walker reached a valley bottom without ever seeing one. All it used, step after step, was the tilt of the ground at its own feet. That matters more than it sounds: a modern model has millions of knobs, so its landscape lives in millions of dimensions — nobody can see it, draw it, or search it. But "tilt under the feet" is a quantity you can compute at any point, in any number of dimensions. The fog is not a limitation we tolerate. It is the situation we are always in, and the method was designed for it.

Downhill is a direction, and the tilt tells you which. Lift the fog and look at the arrows: the orange one points the way the ground rises fastest, and the green step points exactly opposite. In the unit's language the orange arrow is the gradient, written $\nabla f$ ; it is the compass needle that always points uphill, and its length says how steep. The walker's whole strategy in one line:

The realization

$\text{new position}=\text{position}-\gamma\,\nabla f(\text{position})$

Take the uphill needle, flip it, scale it by a stride $\gamma$ , step. The formula is not a rule imposed on the picture; it is the picture, written down.

You find the valley downhill from where you started. Press lift the fog after a walk: there were two valleys all along, and the walker never knew. It went to the one its slope led to. Start on the far side and it goes to the other. Gradient descent finds a low point, the nearest one downhill — not the lowest. Keep this in your pocket; it comes back in Section 3 and again at the very end.

One more word, then we start walking for real. The walk assumes there are no fences — you may put your feet anywhere. Real problems sometimes fence you in (parameters that must stay positive, weights that must add to one); that is constrained optimization and it gets its own unit. Here, the whole mountainside is yours.

Pause & predict

Under your feet the ground tilts so that the uphill needle is $\nabla f=(3,\,-4)$ . Which way is your next step, and how steep is it here?

In one sentence: Learning is a walk in fog — feel the tilt, step the other way — and that is exactly why it works in a million dimensions and exactly why it only finds the valley downhill from where it starts.

2

Why there is a landscape at all

Four receipts

A print shop has four receipts: 1 box of paper cost 3.1, 2 boxes cost 4.9, 3 boxes cost 7.3, 4 boxes cost 9.1. The owner wants a rule of thumb — price ≈ a × boxes + b — so she can quote any order in her head. Any pair $(a,b)$ is a guess. Some guesses are terrible (a flat line at zero), some are close, one is best. Now ask the question that creates the landscape: how wrong is each guess, as a single number?

Draw the guess as a line through the four points. Each receipt sits some distance above or below the line — those red sticks in the picture are the misses. Square each miss (so above and below both count, and a big miss counts a lot) and add them up. That total is the guess's wrongness, and it is the height of the ground at the point $(a,b)$ . Every pair of knob settings has a height; put them all together and you have a landscape. Turn the knobs and watch the line tilt and the ball climb or fall:

Try: press ▶ descend from the origin and watch the ball zig-zag down the narrow trench before crawling along it. Then push $\gamma$ past $0.030$ and press ▶ again — the steps grow instead of shrinking.

drag the picture to orbit

slope a0

intercept b0

step size γ0.02

steps20

—

The loss $L(a,b)=\sum_i\big(y_i-(ax_i+b)\big)^2$ is a bowl, but a lopsided one: its Hessian has one stiff eigenvalue ( $\approx 66.8$ ) and one flat ( $\approx 1.2$ ). Gradient descent must keep $\gamma<2/66.8\approx0.030$ to survive the stiff direction, and at that speed it barely moves along the flat one — the trench you see the ball crawl along.

So the landscape is not a metaphor we imported. It is manufactured, automatically, the moment you say what "wrong" means. Any model, any way of scoring it, gives you one — a height for every setting of the knobs. Training a model means walking that landscape down. The fitting bowl here has two knobs so you can see it; a neural network's has millions, and nobody ever sees it, which is why Section 1 mattered.

Two things you can read straight off the picture, before any formula.

The tilt has an obvious meaning. Start at $a=b=0$ , the line lying flat on the floor with every receipt above it. Which way is downhill? Obviously "tilt the line up toward the points". And that is what the ball does: the first step raises both $a$ and $b$ . When the line is above the data, the misses are negative and the tilt points the other way. The gradient of the wrongness is just "which way should the line move to reduce its misses" — the residuals decide the sign, the inputs decide how strongly each knob feels it.

The realization

With misses $r_i=y_i-(ax_i+b)$ , the wrongness is $L=\sum r_i^2$ and its tilt is $\nabla L=\big(-2\sum x_ir_i,\;-2\sum r_i\big)$ : the intercept feels the plain sum of misses, the slope feels each miss weighted by its $x$ . Positive misses ⇒ push the line up. That is all the formula says.

The bowl is a trench, not a dish. Orbit the stage: the valley is long and narrow. Nudge the slope $a$ and the wrongness shoots up — a small change of slope moves the far points a lot. Nudge the intercept $b$ and almost nothing happens. Two knobs, two very different stiffnesses. The number that measures this, the ratio of stiff to soft, is about $56$ here. Remember the shape: it is the single biggest reason the walk in Section 4 will zig-zag, and the reason step sizes are hard in Section 5.

You might object: this bowl has a formula for its bottom ( $a^*=2.04,\ b^*=1$ ; Practice Problem 11 finds it in three lines). True — and the line is the last model for which that will ever be the case. Make the model any bigger and no formula exists. The walk is not one option among many; it is the only one. That is why we practise it here, where we can check the answer.

Pause & predict

Start at $a=b=0$ : the line lies flat on the floor and all four receipts sit above it. What does the first descent step do to the slope $a$ ?

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

Prove it · the gradient of the squared-error loss

Claim. With residuals $r_i=y_i-(ax_i+b)$ , $\ \dfrac{\partial L}{\partial a}=-2\sum_i x_i r_i\$ and $\ \dfrac{\partial L}{\partial b}=-2\sum_i r_i$ .

1

Name the inside of each square:

r_i=y_i-ax_i-b

. Then

L=\sum_i r_i^2

. Giving the residual a name turns a messy expression into "a sum of squares of something", which is easy to differentiate.

2

Differentiate one square by the chain rule:

\frac{\partial}{\partial a}\,r_i^2=2r_i\cdot\frac{\partial r_i}{\partial a}=2r_i\cdot(-x_i)=-2x_ir_i.

Outer derivative (

2r_i

) times inner derivative. Inside

r_i

, the only place

a

appears is

-ax_i

, whose derivative is

-x_i

.

3

Same for

b

: inside

r_i

,

b

appears as

-b

, so

\dfrac{\partial r_i}{\partial b}=-1

and

\frac{\partial}{\partial b}\,r_i^2=2r_i\cdot(-1)=-2r_i.

The intercept touches every residual in the same way, so its partial is just the plain sum of residuals.

4

A derivative of a sum is the sum of the derivatives:

\nabla L=\Big(-2\sum_i x_ir_i,\ \ -2\sum_i r_i\Big).\ \ \text{That is the claim.}

∎ Read it: if the residuals are mostly positive (the line sits below the data), both partials are negative, so the descent step

-\gamma\nabla L

raises

a

and

b

— the line tilts up toward the points. The compass agrees with common sense.

In one sentence: Say what "wrong" means and a landscape appears by itself — a height for every setting of the knobs — and its tilt is simply "which way should the line move to miss less".

3

Where the walk ends — flat ground comes in three kinds

The marble

Drop a marble on a curved floor: it rolls until the floor under it is level, and there it stops. But level floor is not the same as "the bottom". A marble balanced on top of a hill is on level floor too — one breath and it rolls off. And a marble on a saddle (the middle of a Pringle) is level yet falls if nudged sideways. Flat ground is where the walker stops; whether it stopped somewhere sensible is a second question.

Take the smallest landscape that has all three kinds of flat spot — one dimension, a bumpy curve — and put a probe on it. The probe's tangent is the tilt; where the tangent is level the walk would end. Then press ▶ and let it walk:

Try: put the probe at $x=-1.3$ and press ▶ walk downhill: it slides into the valley at $x\approx0.66$ . Now start at $x=-1.6$ , one hair to the left of the hilltop, and it falls into the deep valley at $x\approx-4.48$ instead.

probe x-1.3

step size γ0.02

—

The rule is $x\leftarrow x-\gamma f'(x)$ : the slope's sign says which way is downhill, its size says how far to go. At a flat spot the walk stops — but flat is not the same as low: $f''$ tells a valley from a hilltop, and nothing in the rule can tell a local valley from the global one.

Watch the probe on the quartic curve. Three flat spots: a deep valley on the left, a hilltop in the middle, a shallow valley on the right. Start the walk anywhere right of the hilltop and it slides into the shallow valley and stops — with a much deeper valley sitting a short distance away behind the hill. It cannot get there. Every step goes downhill from where it is, and getting to the deep valley would mean going up first. Section 1's fog again, now with a number attached: the deep valley is $43$ units lower, and the walker will never know.

How do you tell the three flat spots apart without the picture? By the way the ground curves under your feet. In a valley the ground curls up on both sides of you — like standing in a bowl; on a hilltop it curls down on both sides; on a saddle it curls up one way and down the other. The number that records the curl is the second derivative, and its sign is the whole test:

The realization

Flat ( $f'=0$ ) and curling up ( $f''>0$ ) ⇒ a valley, the walk is done. Flat and curling down ( $f''<0$ ) ⇒ a hilltop, a nudge sends you rolling. In two or more dimensions the "curl" becomes the Hessian from Unit 8 and the same three verdicts (bowl, dome, saddle) apply. Nothing new — Unit 8's judge was built for exactly this moment.

Why does the curl decide? Picture the ground right next to a flat spot as a parabola — the closest simple shape. A parabola that opens up has its bottom at the flat spot; one that opens down has its top there. The second derivative is just "which way, and how tightly, does the parabola open". For the tiny landscapes of a textbook you can skip the walk entirely: find the flat spots by algebra, test the curl at each, done. For anything real you cannot, and the walk plus the test is all you have.

Pause & predict

You start the walk on the quartic curve at $x_0=0$ . Where does it end?

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

Prove it · the second-derivative test, from Taylor

Claim. If $f'(c)=0$ and $f''(c)>0$ , then $c$ is a local minimum; if $f''(c)<0$ , a local maximum.

1

Write Taylor's formula about

c

with the remainder from Unit 8, for a small step

h

:

\begin{aligned}f(c+h)&=f(c)+f'(c)\,h+\tfrac12 f''(\xi)\,h^2\\ &\text{for some }\xi\text{ between }c\text{ and }c+h.\end{aligned}

Value, slope times step, half the bend times step squared — with the bend taken at a secret nearby point so the formula is exact.

2

The slope term dies because

f'(c)=0

:

f(c+h)-f(c)=\tfrac12 f''(\xi)\,h^2.

At a flat spot the only thing left to decide "up or down" is the bend.

3

h^2\ge0

always. If

f''(c)>0

, then by continuity

f''(\xi)>0

for all small enough

h

, so the right side is

\ge0

:

f(c+h)\ge f(c)

on both sides of

c

— a valley. If

f''(c)<0

the right side is

\le0

— a hilltop. ∎ The sign of

h

never mattered: a square erases it. That is exactly why the second derivative alone decides. (If

f''(c)=0

the test is silent — the ground is flatter than a parabola and you must look further, as in Unit 8.)

In one sentence: The walk stops on flat ground; the curl of the ground says whether that is a valley, a hilltop, or a saddle; and the valley you get is the one downhill from where you started.

4

The rule, and the trench that makes it zig-zag

A ball on a spring

Pull a ball away from the centre of a bowl and let go: it is pulled back, harder the further you pulled. That is the simplest landscape there is — a bowl — and its tilt is a spring: the pull is proportional to how far you are from the bottom. Now make the bowl a trench: a stiff spring across the trench, a soft spring along it. The ball is pulled back hard across, gently along. Every step of gradient descent on a bowl is a ball obeying two springs of different strength. Watch what that does to the path:

Try: on the lecture's valley set $\gamma=0.09$ and press ▶: the walker bounces across the steep walls (factor $-0.81$ ) while inching along the floor (factor $0.82$ ). Then switch to exact line search and watch every step turn exactly 90°.

drag the picture to orbit

step size γ0.05

steps20

—

For $f(\mathbf x)=\tfrac12\mathbf x^{\top}A\mathbf x+\mathbf b^{\top}\mathbf x$ the gradient is $A\mathbf x+\mathbf b$ and the minimiser is $\mathbf x^*=-A^{-1}\mathbf b$ . Along each eigen-direction of $A$ a fixed step multiplies the error by $1-\gamma\lambda$ : the stiff direction (big $\lambda$ ) forces $\gamma$ small, and then the flat direction barely moves. Exact line search picks the $\gamma$ that minimises $f$ along the ray — which is exactly why consecutive steps are perpendicular.

On the lecture's valley the walk does something that looks wrong and is not: it bounces from wall to wall while creeping along the floor. The stiff spring (across the trench, stiffness about $20$ ) flings the ball to the other side each step; the soft spring (along it, stiffness about $2$ ) barely tugs. One step size has to serve both, and it cannot serve both well. Set $\gamma=0.09$ and press ▶: the wall-to-wall bouncing is the stiff spring, the slow crawl is the soft one, and the ratio of the two stiffnesses — ten here, fifty-six on the fitting trench of Section 2 — is how bad the zig-zag gets. This is the picture to keep. Section 5 puts numbers on it; Unit 10's whole reason to exist is to fix it.

Now the rule itself, which you have already used a hundred times in the widgets without reading it:

The realization

$\mathbf x_{i+1}=\mathbf x_i-\gamma\,\nabla f(\mathbf x_i)\qquad\text{and for a bowl}\quad \nabla f(\mathbf x)=A\mathbf x+\mathbf b,$

which reads: the tilt of a bowl is a spring — a matrix $A$ of stiffnesses times the displacement, plus a constant offset $\mathbf b$ that says where the bottom sits ( $\mathbf x^*=-A^{-1}\mathbf b$ , the point where the springs balance to zero). The eigenvalues of $A$ are the stiffnesses of the springs along the trench's own axes.

Two claims hide inside the rule, and both are things you can see rather than take on trust. First: "against the tilt" really is the steepest way down. Stand on a slope and turn slowly through a full circle: the ground drops fastest when you face exactly away from the uphill needle, and any other facing drops less — the drop is the needle's length times the cosine of the angle you turned. Second: a short enough step against the tilt always lowers the height, because close to your feet the ground is nearly a plane, and on a plane a step downhill goes down. The word "short enough" is doing real work — it is Section 5's whole subject. (The algebra for both, and for the spring formula, waits at the end of the section.)

Pause & predict

On the lecture's valley the walker starts at $\mathbf x_0=(-3,-1)$ . The springs pull it with $\nabla f=A\mathbf x_0+\mathbf b$ . Which way does the first step go, and which coordinate moves more?

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

Prove it · the gradient points the steepest way up

Claim. Among all unit directions $\mathbf u$ , the rate of change of $f$ along $\mathbf u$ is largest when $\mathbf u$ points along $\nabla f$ , and that largest rate is $\|\nabla f\|$ .

1

From Unit 6, the rate of change of

f

along a unit direction

\mathbf u

(the directional derivative) is a dot product:

D_{\mathbf u}f=\nabla f\cdot\mathbf u.

Walk a tiny distance

t

along

\mathbf u

;

f

changes by about

t\,\nabla f\cdot\mathbf u

.

2

Cauchy–Schwarz (Unit 3) bounds any dot product by the product of lengths:

\nabla f\cdot\mathbf u\le\|\nabla f\|\,\|\mathbf u\|=\|\nabla f\|\cdot1.

A dot product is

\|\mathbf a\|\|\mathbf b\|\cos\theta

, and

\cos\theta\le1

.

3

Equality holds exactly when

\cos\theta=1

, i.e.

\mathbf u

points the same way as

\nabla f

:

\mathbf u=\nabla f/\|\nabla f\|

. Then

D_{\mathbf u}f=\|\nabla f\|

, the largest possible. Turning

\mathbf u

the opposite way gives

\cos\theta=-1

and the most negative rate,

-\|\nabla f\|

: the steepest descent. ∎ So the uphill compass is not a metaphor. The gradient direction is the unique winner of "which way is steepest", and its length is the steepness.

Prove it · a small step against the gradient lowers f

Claim. If $\mathbf g=\nabla f(\mathbf x)\neq\mathbf 0$ , then for all small enough $\gamma>0$ , $\ f(\mathbf x-\gamma\mathbf g)<f(\mathbf x)$ .

1

Unroll the step into one variable, the line trick from Unit 8:

h(\gamma)=f(\mathbf x-\gamma\mathbf g)

. Its derivative at

\gamma=0

is, by the chain rule,

h'(0)=\nabla f(\mathbf x)\cdot(-\mathbf g)=-\mathbf g\cdot\mathbf g=-\|\mathbf g\|^2<0.

Moving along

-\mathbf g

means the directional derivative is the gradient dotted with

-\mathbf g

. A nonzero vector dotted with itself is strictly positive, so with the minus sign the slope of

h

at the start is strictly negative.

2

Taylor for

h

at

0

with the remainder:

\begin{aligned}h(\gamma)&=h(0)+h'(0)\,\gamma+\tfrac12h''(\xi)\,\gamma^2\\ &=f(\mathbf x)-\gamma\|\mathbf g\|^2+\tfrac12h''(\xi)\,\gamma^2.\end{aligned}

The value, a drop proportional to

\gamma

, and a correction proportional to

\gamma^2

.

3

For small

\gamma

the

\gamma

term beats the

\gamma^2

term: if

|h''|\le M

nearby, then

\begin{aligned}f(\mathbf x-\gamma\mathbf g)&\le f(\mathbf x)-\gamma\|\mathbf g\|^2+\tfrac12M\gamma^2\\ &=f(\mathbf x)-\gamma\Big(\|\mathbf g\|^2-\tfrac12M\gamma\Big),\end{aligned}

and the bracket is positive as soon as

\gamma<2\|\mathbf g\|^2/M

. So

f

goes down. ∎ Notice what the proof also warns: the guarantee is only for

\gamma

small enough, and "small enough" depends on the bend

M

. Too big a step and the

\gamma^2

term wins — the step overshoots and

f

can go up. Section 5 turns that warning into an exact number.

Prove it · the gradient of a quadratic bowl is Ax + b

Claim. For symmetric $A$ , $f(\mathbf x)=\tfrac12\mathbf x^{\top}A\mathbf x+\mathbf b^{\top}\mathbf x$ has $\nabla f=A\mathbf x+\mathbf b$ , and its only flat point is $\mathbf x^*=-A^{-1}\mathbf b$ .

1

Write the two pieces out in coordinates:

\tfrac12\mathbf x^{\top}A\mathbf x=\tfrac12\sum_{j}\sum_{k}A_{jk}x_jx_k,\qquad \mathbf b^{\top}\mathbf x=\sum_jb_jx_j.

A quadratic form is a double sum of "entry times two coordinates"; the linear part is a plain dot product.

2

Differentiate with respect to one coordinate

x_i

. In the double sum,

x_i

appears in the terms with

j=i

(giving

\sum_kA_{ik}x_k

) and in the terms with

k=i

(giving

\sum_jA_{ji}x_j

); by symmetry these two are equal, so

\begin{aligned}\frac{\partial}{\partial x_i}\Big(\tfrac12\mathbf x^{\top}A\mathbf x\Big)&=\tfrac12\Big(\sum_kA_{ik}x_k+\sum_jA_{ji}x_j\Big)\\ &=\sum_kA_{ik}x_k=(A\mathbf x)_i,\\ \frac{\partial}{\partial x_i}\big(\mathbf b^{\top}\mathbf x\big)&=b_i.\end{aligned}

The

\tfrac12

in front was put there precisely to cancel the 2 that symmetry produces — that is why the lecture writes the bowl as

\tfrac12\mathbf x^{\top}A\mathbf x

.

3

Stack the coordinates:

\nabla f=A\mathbf x+\mathbf b

. Setting it to zero,

A\mathbf x=-\mathbf b

, so

\mathbf x^*=-A^{-1}\mathbf b

. For the lecture's numbers,

A^{-1}=\tfrac1{39}\begin{bmatrix}20&-1\\-1&2\end{bmatrix}

and

-\mathbf b=(5,3)

, giving

\begin{aligned}\mathbf x^*&=\tfrac1{39}\begin{bmatrix}100-3\\-5+6\end{bmatrix}=\Big(\tfrac{97}{39},\tfrac1{39}\Big)\\ &\approx(2.487,\,0.026),\qquad f^*\approx-6.256.\end{aligned}

∎ So for this valley we know exactly where the walk should end, and can watch it get there — or fail to. Run it:

In one sentence: On a bowl the tilt is a spring,

\nabla f=A\mathbf x+\mathbf b

, and a trench is two springs of unequal stiffness — which is why one step size bounces across it while crawling along it.

5

How long a step — the bouncing ball

Stairs in the dark

Going down a staircase with the lights off, you can shuffle an inch at a time (safe, and you will be there by morning) or leap three steps (fast, until you overshoot a landing and stumble back up a flight). There is a stride that is just right, and it depends on the stairs: steep, tight stairs demand short strides. Gradient descent has exactly this dial, and on a bowl you can see everything it does with a single bouncing ball:

Try: press sweet — with $\gamma\lambda=1$ a single step lands exactly at the bottom. Then press edge: $\gamma\lambda=2$ bounces between $\pm x_0$ forever, and one notch more explodes.

curvature λ2

step size γ0.3

—

On $f=\tfrac12\lambda x^2$ the update is $x_{k+1}=x_k-\gamma\lambda x_k=(1-\gamma\lambda)\,x_k$ : a pure geometric sequence. The factor must sit strictly inside $(-1,1)$ — that is the rule $\gamma<2/\lambda$ . In two dimensions each eigen-direction has its own factor, and the stiffest one (the largest $\lambda$ ) sets the speed limit for all.

Play with the one-dimensional tab and you will discover the whole story in four presets. Crawl: tiny stride, the ball inches down the same side, forever. Sweet: one stride lands it exactly at the bottom. Bounce: a bigger stride overshoots the bottom, lands on the far wall a little lower, overshoots back — a shrinking zig-zag that still gets there. Edge: the ball bounces between the same two heights for ever. One notch more and every bounce is higher than the last: the walk explodes.

There is one number behind all of it. On a bowl of stiffness $\lambda$ , a step of size $\gamma$ does not move the ball by a fixed amount — it multiplies its distance from the bottom by the same factor every time:

The realization

$\text{distance after the step}=(1-\gamma\lambda)\times\text{distance before.}$

Read the factor like a volume dial. Between $0$ and $1$ : shrinking, same side (crawl when near $1$ ). Exactly $0$ : one perfect step. Between $-1$ and $0$ : shrinking but flipping sides (bounce). At $-1$ : bouncing forever. Beyond $-1$ : growing. So the stride must keep $\gamma\lambda$ below $2$ — the speed limit $\gamma<2/\lambda$ . Stiffer bowl, shorter stride, exactly like the stairs.

Now switch to the two-dimensional tab and the zig-zag of Section 4 explains itself. A trench is two springs, so it is two factors at once: $1-\gamma\lambda_{\text{stiff}}$ across and $1-\gamma\lambda_{\text{soft}}$ along. The stride has to obey the stiff spring's speed limit, and once it does, the soft spring's factor is stuck near $1$ — the ball is on the bounce setting across the trench and on the crawl setting along it, at the same time, with the same $\gamma$ . Press zig-zag: factors $-0.90$ and $0.81$ . That pair of numbers is the zig-zag. The ratio of stiffnesses (the condition number) is how badly any single stride is torn between the two.

So what does a practitioner do, not knowing the stiffnesses? Two honest answers. The lazy one: watch the height. If a step made things worse, you were too bold — undo it and halve the stride; if it helped, be a little bolder. You only ever keep steps that go down, so the height can never rise; Section 8 turns this reflex into an algorithm. The clever one: let the ground choose the stride, which is the next section.

Pause & predict

A trench has stiffnesses $20$ (across) and $2$ (along). You choose $\gamma=0.15$ . What happens?

Pause & predict

The fitting trench of Section 2 has stiffnesses about $66.8$ and $1.2$ . Roughly what stride is safe, and what does the soft direction do at that stride?

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

Prove it · the speed limit γ < 2/λ

Claim. On $f=\tfrac12\lambda x^2$ , gradient descent converges to $0$ from any start if and only if $0<\gamma<2/\lambda$ ; it lands exactly at $0$ in one step when $\gamma=1/\lambda$ .

1

Apply the update

k

times. The factor is the same each time, so

x_k=(1-\gamma\lambda)^k\,x_0.

A geometric sequence: the position after

k

steps is the start times the factor to the power

k

.

2

A number to the power

k

goes to

0

exactly when its size is below

1

:

\begin{aligned}|1-\gamma\lambda|<1&\iff-1<1-\gamma\lambda<1\\ &\iff0<\gamma\lambda<2\\ &\iff0<\gamma<\frac2\lambda.\end{aligned}

Subtract 1 from all three parts, multiply by

-1

(which flips the inequalities), divide by

\lambda>0

.

3

Read the four regimes off the factor.

0<1-\gamma\lambda<1

(

\gamma<1/\lambda

): shrinks, same side each time — smooth descent, slow when the factor is near

1

.

1-\gamma\lambda=0

(

\gamma=1/\lambda

):

x_1=0

, done in one step.

-1<1-\gamma\lambda<0

(

1/\lambda<\gamma<2/\lambda

): shrinks but flips sign — overshoots the bottom every step, still converging.

|1-\gamma\lambda|\ge1

(

\gamma\ge2/\lambda

): never shrinks; at exactly

2/\lambda

it bounces

\pm x_0

forever, beyond that each step is bigger than the last. ∎ Steeper valley (bigger

\lambda

) means a lower speed limit

2/\lambda

. That is the dark staircase: steep stairs, short strides.

Prove it · each direction has its own factor — the zig-zag explained

Claim. On $f=\tfrac12(\lambda_1x^2+\lambda_2y^2)$ with $\lambda_1>\lambda_2>0$ , a fixed step $\gamma$ must satisfy $\gamma<2/\lambda_1$ , and then the $y$ -direction converges with factor $1-\gamma\lambda_2$ , which is close to $1$ when $\lambda_1/\lambda_2$ is large.

1

The gradient is

(\lambda_1x,\ \lambda_2y)

, so the two coordinates update independently:

x_{k+1}=(1-\gamma\lambda_1)x_k,\qquad y_{k+1}=(1-\gamma\lambda_2)y_k.

The bowl has no cross-term, so each coordinate lives on its own parabola and gets its own factor.

2

Both factors must have size below

1

. The stricter demand comes from the larger

\lambda

:

\gamma<\frac2{\lambda_1}\quad(\text{the steep direction sets the limit}).

If the stiff direction diverges, the whole walk diverges — one bad coordinate is enough.

3

With

\gamma

held under that limit, the gentle direction's factor is

1-\gamma\lambda_2>1-\frac{2\lambda_2}{\lambda_1}.

For the lecture's valley

\lambda_1\approx20.06,\ \lambda_2\approx1.94

, so this factor is above

0.81

no matter what: at best the

y

-error shrinks by a fifth per step while the

x

-error, near the limit, flips sign with a factor near

-1

— bouncing across the trench while creeping along it. ∎ The ratio

\lambda_1/\lambda_2

is the condition number. Big ratio, long trench, slow zig-zag walk. For a general bowl

\tfrac12\mathbf x^{\top}A\mathbf x

the same argument runs in the eigenbasis of

A

(Unit 4): the eigenvalues of the Hessian are the

\lambda

's.

In one sentence: Each step multiplies the distance to the bottom by

1-\gamma\lambda

; the stiffest spring sets the speed limit

\gamma<2/\lambda_{\max}

, the softest sets the crawl, and the gap between them is the zig-zag.

6

Let the ground choose the stride — line search

Sliding the foot

Back on the dark staircase, try this instead of guessing a stride: point your foot downhill and slide it forward along the floor, feeling, until the floor stops going down and starts coming up. Put your weight there. You have found the lowest point along that line. Then feel the tilt again — it will point somewhere new — and slide again.

That is line search: fix the direction (against the tilt), and let the landscape tell you how far. Along the ray the whole landscape collapses to a single curve — height against distance — and "how far" is just "where is the bottom of that curve". Drag the bead along the ray and watch the little curve on the right:

Try: drag $\gamma$ slowly and watch the orange gradient arrow at the bead swing round; press snap to γ* and it stands exactly at right angles to the ray, where the ray just kisses a contour. Then take the step and repeat from the new point.

bead at γ0.09

—

Along the ray $\mathbf x_k-\gamma\mathbf g$ the bowl becomes a one-variable function $h(\gamma)=f(\mathbf x_k-\gamma\mathbf g)$ . Its derivative is $h'(\gamma)=-\mathbf g^{\top}\nabla f(\text{bead})$ , so $h'(\gamma^*)=0$ says precisely that the new gradient has no component along the old direction — the two are perpendicular. For a quadratic, $\gamma^*=\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g$ in closed form.

Slide the bead slowly and watch the orange arrow — the tilt at the bead's own position. Early on it leans back along the ray: you are still going down, keep sliding. Slide too far and it leans forward: you have passed the bottom. Exactly at the best spot it is perpendicular to the ray, and at that same spot the ray just kisses a contour line without crossing it. Those are the same fact seen twice: a contour is a line of constant height, the tilt is always perpendicular to contours, and the lowest point along a straight line is where the line touches a contour rather than cutting through to a lower one.

The realization

The best stride $\gamma^*$ is where the tilt at the new point is at right angles to the direction you just walked. On a bowl it has a closed form, $\gamma^*=\dfrac{\mathbf g^{\top}\mathbf g}{\mathbf g^{\top}A\mathbf g}$ with $\mathbf g$ the tilt where you stand — the stride you would get by sliding your foot, written as a fraction. On the stretched bowl from $(2,2)$ it is $5/28$ , and one slide removes $89\%$ of the height.

Press take the step a few times and a pattern appears that no fixed stride ever shows: every corner is a right angle. The walk turns exactly $90^\circ$ at each step, because each new tilt is perpendicular to the last direction. Beautiful — and still a zig-zag on a long trench, just a tidier one: each step is the best possible in its direction, but the direction is still "straight against the tilt", which on a trench is mostly "across". Better strides do not fix a bad direction; that is Unit 10's job.

Is it used? Less than you would think. Sliding your foot costs a whole one-variable minimisation per step, and each height check on a real loss means a pass over the data. So plain gradient descent settles for an inexact slide — "far enough that the height clearly dropped" (the Armijo rule of Section 7) — and saves the exact version for methods like Newton's that genuinely need it.

Pause & predict

From $(2,2)$ on the stretched bowl the exact slide lands at $(9/7,-1/7)$ , where the tilt is $(18/7,\,-6/7)$ . Dot it with the old tilt $(4,12)$ . What do you get, and why?

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

Prove it · the lecture's line search on x² + 3y²

Claim. For $f=x^2+3y^2$ the best step from $(x,y)$ is $\gamma^*=\dfrac{x^2+9y^2}{2x^2+54y^2}$ ; from $(2,2)$ it is $5/28$ , landing at $(9/7,\,-1/7)$ .

1

The gradient is

\nabla f=(2x,\ 6y)

. The trial point a distance

\gamma

down the ray is

(x-2\gamma x,\ \ y-6\gamma y)=\big((1-2\gamma)x,\ (1-6\gamma)y\big).

Each coordinate keeps its own factor, exactly as in Section 5 — but now

\gamma

is a variable we will choose.

2

Put the trial point into

f

:

h(\gamma)=(1-2\gamma)^2x^2+3(1-6\gamma)^2y^2.

A quadratic in

\gamma

with a positive leading coefficient — a parabola in

\gamma

with a single bottom.

3

Differentiate with respect to

\gamma

(chain rule: inner derivatives

-2

and

-6

) and set to zero:

h'(\gamma)=-4(1-2\gamma)x^2-36(1-6\gamma)y^2=0.

2(1-2\gamma)\cdot(-2)=-4(1-2\gamma)

and

3\cdot2(1-6\gamma)\cdot(-6)=-36(1-6\gamma)

.

4

Expand, collect the

\gamma

terms, solve:

\begin{aligned}-4x^2+8\gamma x^2-36y^2+216\gamma y^2&=0\\ \gamma\,(8x^2+216y^2)&=4x^2+36y^2\\ \gamma^*&=\frac{4x^2+36y^2}{8x^2+216y^2}\\ &=\frac{x^2+9y^2}{2x^2+54y^2}.\end{aligned}

Divide top and bottom by

4

. It is a minimum because

h''=8x^2+216y^2>0

.

5

At

(2,2)

:

\gamma^*=\dfrac{4+36}{8+216}=\dfrac{40}{224}=\dfrac5{28}

. The new point is

\begin{aligned}&\Big((1-\tfrac{10}{28})\cdot2,\ (1-\tfrac{30}{28})\cdot2\Big)\\ &=\Big(\tfrac{18}{28}\cdot2,\ -\tfrac{2}{28}\cdot2\Big)=\Big(\tfrac97,\ -\tfrac17\Big),\end{aligned}

and

f

drops from

16

to

\tfrac{81}{49}+\tfrac3{49}=\tfrac{12}7\approx1.71

. ∎ One landscape-chosen step removed 89% of the height. Notice

y

overshot past

0

to

-1/7

: even the best step along the gradient overshoots in the stiff direction. The next step's

\gamma^*

is

5/12

, landing at

(3/14,3/14)

.

Prove it · the general line-search step for a quadratic

Claim. For $f=\tfrac12\mathbf x^{\top}A\mathbf x+\mathbf b^{\top}\mathbf x$ with $A$ symmetric positive-definite and $\mathbf g=\nabla f(\mathbf x)=A\mathbf x+\mathbf b$ , the best step along $-\mathbf g$ is $\gamma^*=\dfrac{\mathbf g^{\top}\mathbf g}{\mathbf g^{\top}A\mathbf g}$ .

1

h(\gamma)=f(\mathbf x-\gamma\mathbf g)

. By the chain rule,

h'(\gamma)=\nabla f(\mathbf x-\gamma\mathbf g)\cdot(-\mathbf g)

. Derivative of

f

along a moving point = gradient at that point dotted with the point's velocity, which here is

-\mathbf g

.

2

The gradient at the trial point is

A(\mathbf x-\gamma\mathbf g)+\mathbf b=(A\mathbf x+\mathbf b)-\gamma A\mathbf g=\mathbf g-\gamma A\mathbf g

. So

h'(\gamma)=-\mathbf g^{\top}(\mathbf g-\gamma A\mathbf g)=-\mathbf g^{\top}\mathbf g+\gamma\,\mathbf g^{\top}A\mathbf g.

The gradient of a quadratic is linear in the point, so it splits cleanly into "the old gradient" minus "

\gamma

times

A\mathbf g

".

3

Set

h'(\gamma)=0

:

\gamma^*=\frac{\mathbf g^{\top}\mathbf g}{\mathbf g^{\top}A\mathbf g},

a minimum because

h''=\mathbf g^{\top}A\mathbf g>0

for positive-definite

A

. ∎ Check it against the lecture: for

x^2+3y^2

,

A=\mathrm{diag}(2,6)

,

\mathbf g=(2x,6y)

, so

\mathbf g^{\top}\mathbf g=4x^2+36y^2

and

\mathbf g^{\top}A\mathbf g=8x^2+216y^2

— the same fraction as before. Practice Problems 6, 7 and 9 use this formula.

Prove it · after an exact step, the new gradient is perpendicular to the old direction

Claim. If $\alpha_t$ minimises $J(\mathbf w_t+\alpha\mathbf g_t)$ over $\alpha$ , then $\mathbf g_t^{\top}\nabla J(\mathbf w_{t+1})=0$ , where $\mathbf w_{t+1}=\mathbf w_t+\alpha_t\mathbf g_t$ .

1

Suppose not:

\mathbf g_t^{\top}\nabla J(\mathbf w_{t+1})\ne0

. Move a tiny extra

\pm\delta

along the same direction and use first-order Taylor at

\mathbf w_{t+1}

:

J(\mathbf w_{t+1}\pm\delta\mathbf g_t)\approx J(\mathbf w_{t+1})\pm\delta\,\mathbf g_t^{\top}\nabla J(\mathbf w_{t+1}).

Value plus (step) dot (gradient). This is exactly the line trick from Unit 8, one derivative deep.

2

The correction

\pm\delta\,\mathbf g_t^{\top}\nabla J

is nonzero, and we get to pick its sign: choose

+\delta

if the dot product is negative,

-\delta

if it is positive. Either way,

J(\mathbf w_{t+1}\pm\delta\mathbf g_t)<J(\mathbf w_{t+1}).

A nonzero slope along the line means one of the two ways along the line goes down.

3

But that is a point on the same ray — at

\alpha=\alpha_t\pm\delta

— with a lower value of

J

, contradicting that

\alpha_t

was the minimiser. So the dot product must be zero:

\mathbf g_t\perp\nabla J(\mathbf w_{t+1})

. ∎ In one-variable language:

h'(\alpha_t)=\mathbf g_t^{\top}\nabla J(\mathbf w_{t+1})

, and the minimiser of a smooth function has zero derivative. Geometrically: the ray stops exactly where it is tangent to a contour, and the gradient is always perpendicular to contours. Consequence: steepest descent with exact line search turns a right angle at every corner — a zig-zag of perfect squares, which on a long trench is still a lot of corners.

In one sentence: Slide along the ray until the ground stops dropping — that is where the ray kisses a contour and the new tilt is at a right angle to the step — and on a bowl the stride is the fraction

\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g

.

7

Finding the bottom of one line — the radio dial

The radio dial

An old radio: somewhere on the dial the station comes in clearest, but you cannot see signal strength, only hear hiss. So you play a game. Pick a spot, nudge the knob a hair to the right, and ask: better or worse? Better means the sweet spot is further right, worse means it is to the left. Each answer throws away half the dial. Ten answers and you are within a thousandth of the station — without ever knowing where it was.

Section 6 left one job open: on a real loss there is no fraction for the best stride, only the ability to ask the ground its height at any distance along the ray. That is the radio. The curve of height-against-distance usually has one dip — down, bottom, up, no side dips — and a curve like that can be cornered by squeezing a bracket around its bottom. Three ways to squeeze, and one way to cheat:

Try: step the binary search on the practice function and read the brackets: $[0,4]\to[2,4]\to[2,3]\to[2,2.5]$ . Then switch to the bumpy function — the bracket can squeeze down on the wrong dip and lose the true minimiser.

—

Bracketing methods assume $h$ is unimodal on $[a,b]$ — one dip, nothing else — and then squeeze: binary search halves the width each time (two evaluations per step), golden section shrinks it by $0.618$ with only one new evaluation. Armijo asks a humbler question: is $h(\alpha)\le h(0)+c\,\alpha\,h'(0)$ ? If not, halve $\alpha$ and ask again.

Binary is the radio game exactly: check the slope at the middle of the bracket (compare the height at the midpoint with the height a hair to the right), keep the half that goes down. Every round halves the bracket, so $9$ rounds take $[0,4]$ to a width under $0.01$ — you can count the rounds with a logarithm and nothing else. Golden-section is the same game for someone who cannot measure slope, only height: put two probes inside the bracket, keep the side with the lower one. Its trick is where to put the probes — at $38\%$ and $62\%$ of the bracket — because after the cut, one old probe is already sitting at the right fraction of the new bracket and can be reused. One new height per round instead of two; that is the whole reason the golden ratio shows up. Armijo gives up on finding the bottom. It starts with a bold stride and asks only "did the height drop by a decent fraction of what the tilt promised?" — if yes, take it; if no, halve and ask again. It does not need the curve to have one dip, it costs a handful of height checks, and it is what ordinary gradient descent actually uses. The exact squeezes are for the methods that truly need the bottom.

The realization

Bracket width after $k$ halvings is $(b-a)/2^k$ ; golden cuts shrink it by $0.618$ per round and reuse a probe; Armijo accepts any stride with $h(\alpha)\le h(0)+c\,\alpha\,h'(0)$ for a small $c$ — "a decent fraction of the promised drop".

Pause & predict

Binary search over $[0,4]$ : at the midpoint $2$ the height a hair to the right is lower than at $2$ . Which half do you keep, and how wide is the bracket after three such rounds?

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

Prove it · how many squeezes, and why the golden ratio

Claim. Binary search reaches a bracket of width $\le w$ from $[a,b]$ in $k=\lceil\log_2\big((b-a)/w\big)\rceil$ rounds; golden-section search shrinks the bracket by $\varphi=(\sqrt5-1)/2\approx0.618$ per round and re-uses one point each time.

1

Binary: each round halves the width, so after

k

rounds the width is

(b-a)/2^k

. Demanding

(b-a)/2^k\le w

:

2^k\ge\frac{b-a}{w}\iff k\ge\log_2\frac{b-a}{w}.

For

[0,4]

and

w=0.01

:

\log_2 400\approx8.64

, so

k=9

(width

4/512\approx0.0078

). Take the logarithm base 2 of both sides; round up because

k

counts whole rounds. This is Practice Problem 12.

2

Golden: put

m_1=b-\varphi(b-a)

and

m_2=a+\varphi(b-a)

. Suppose we keep

[a,m_2]

, whose width is

\varphi(b-a)

. Where does the old

m_1

sit inside it, as a fraction from the left?

\frac{m_1-a}{m_2-a}=\frac{(1-\varphi)(b-a)}{\varphi(b-a)}=\frac{1-\varphi}{\varphi}.

We want this to equal

1-\varphi

, the left golden fraction, so that

m_1

can serve as the new bracket's left interior point without a fresh evaluation.

3

Demand

\dfrac{1-\varphi}{\varphi}=1-\varphi

, i.e.

1-\varphi=\varphi-\varphi^2

, i.e.

\varphi^2+\varphi-1=0

, whose positive root is

\varphi=\frac{-1+\sqrt5}{2}\approx0.618.

∎ So the golden ratio is not decoration — it is the unique fraction that lets each round re-use a point. Width after

k

rounds:

(b-a)\varphi^k

; for

[0,4]

and

w=0.01

,

k=\lceil\ln(0.0025)/\ln0.618\rceil=13

rounds, but only 13 new evaluations against binary search's 18 (two per round). Fewer evaluations per unit of squeeze — that is the whole point when each

h

costs a pass over the data.

In one sentence: With no formula for the bottom of the ray, squeeze a bracket around it — halve it, golden-cut it, or take Armijo's "good enough" stride, which is what real training does.

8

Bold early, careful late — schedules and the bold driver

Parking the car

Nobody parks at one speed. Far from the wall you drive fast, because the wall is far; as it comes near you slow to a crawl, because a fast car near a wall overshoots. A learning rate is a speed. Section 5's bouncing ball was the car at one fixed speed — fine early, bouncing off the walls later. The cure is obvious the moment you say it: start bold, finish careful.

Three ways to slow down on a timer, and one way to slow down by feel. Compare the timers, then watch the driver find the speed limit on its own:

Try: set $k=0.05$ and read the three rates at $t=10$ : $0.485$ , $0.533$ , $0.089$ . Then open the bold driver tab and press ▶ — the rate climbs 5 % a step until the first overshoot, then halves on the spot.

start α₀0.8

decay k0.05

epochs shown30

read at t10

—

Exponential decay $\alpha_0e^{-kt}$ shrinks geometrically, inverse decay $\alpha_0/(1+kt)$ only harmonically, step decay $\alpha_0/3^{\lfloor t/5\rfloor}$ drops in cliffs. The bold driver ignores the clock: after every step it looks at the loss — improved? grow $\alpha$ by 5 %; worse? undo the step and halve $\alpha$ .

The timers: exponential loses the same fraction every epoch (fast to fall — after $1/k$ epochs it is at $37\%$ ); inverse loses less and less (half at $1/k$ , a third at $2/k$ , a slow tail); step holds steady and then drops off a cliff every few epochs. Which is right depends on how far the walk still has to go — a rate that dies too fast leaves the walker stranded above the bottom; one that dies too slowly keeps it jittering. Section 11 will show why, with noisy tilts, the slowing down is not a nicety but the only way the walk ever ends.

The bold driver replaces the timer with a reflex. After each step, look at the height. Lower than before? Press the accelerator a touch — rate up $5\%$ . Higher? You overshot: undo the step, halve the rate, try again from where you were. Kept steps only ever go down, so the height can never rise; and the rate drifts up until it hits the speed limit of Section 5, gets knocked back, drifts up again. In the widget it hovers around $2/\lambda_{\text{stiff}}=0.1$ — it has discovered the stiffest spring by bumping into it. One honest caveat, which points at Section 10: if the height you look at is only an estimate (a spoonful of the data, not the pot), it can go up by chance, and the driver panics for no reason. Then judge every few steps, not every step.

The realization

$\alpha_t=\alpha_0e^{-kt}$ (exponential), $\alpha_t=\alpha_0/(1+kt)$ (inverse), divide-by-a-constant-every-few-epochs (step); $t$ counts epochs, so the rate is fixed within one pass over the data. Bold driver: $\times1.05$ on success, undo and $\times0.5$ on failure.

Pause & predict

Training starts at $\alpha_0=0.8$ . Under step decay that divides the rate by $3$ every $5$ epochs, what is the rate during epoch $12$ ?

Pause & predict

A bold driver is at rate $0.08$ . The next step makes the height go up. What does it do?

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

Prove it · the two half-way marks

Claim. Inverse decay halves the learning rate exactly at $t=1/k$ ; exponential decay multiplies it by $1/e\approx0.37$ at the same $t$ .

1

Inverse: set

\dfrac{\alpha_0}{1+kt}=\dfrac{\alpha_0}{2}

. Cross-multiplying,

1+kt=2\iff t=\frac1k.

For

k=0.05

that is epoch

20

:

0.8/(1+1)=0.4

. Practice Problem 3.

2

Exponential at the same

t

:

\alpha_0e^{-k\cdot(1/k)}=\alpha_0e^{-1}\approx0.37\,\alpha_0

. Already below half — and at

t=2/k

it is

e^{-2}\approx0.14

against inverse decay's

1/3

. ∎ Exponential decay is geometric (a fixed fraction lost per epoch), inverse decay is harmonic (it loses less and less). Which is right depends on how far the walk still has to go: a rate that dies too fast leaves the walker stranded short of the bottom, one that dies too slowly keeps it jittering. Section 11 shows the second danger with noisy gradients, where decay is not a convenience but a requirement.

In one sentence: A learning rate is a speed that should fall as the wall approaches — on a timer (exponential, inverse, step) or by feel (bold driver: up

5\%

on success, undo and halve on failure).

9

Is my compass even right? — the known weight

The known weight

Before an inspector trusts a shopkeeper's scale, she puts a known one-kilogram weight on it. If it reads $1.0$ , fine. If it reads $1.3$ , every sale that day was wrong and nobody noticed. A gradient computed by code — hand-written derivatives, or backprop from Unit 7 — is that scale. It will confidently steer a million-knob walk, and if it is off by a sign or a factor, the walk goes confidently to the wrong place. So you put a known weight on it.

The known weight is the meaning of "tilt" itself: nudge one knob by a tiny $\Delta$ , see how much the height moves, divide. That is the tilt, measured rather than computed, and it should match the code. Two ways to nudge — forward only, or a little each way — and they are not equally good. Slide $\Delta$ and watch the two error curves:

Try: at $\Delta=0.1$ read the two estimates of $\partial J/\partial w_1$ : forward $13.61$ , central $13.01$ , truth $13$ . Halve $\Delta$ and the forward error halves while the central error drops fourfold — then slide below $10^{-6}$ and watch both curves turn back up.

log₁₀ Δ0.1

—

$J(w_1,w_2)=w_1^3+w_1w_2^2$ at $(2,1)$ . Taylor says the forward difference is off by $\tfrac12\Delta\,J''$ and the central one by $\tfrac16\Delta^2J'''$ — the slopes 1 and 2 on the log-log chart. But each $J$ carries a rounding error of about $10^{-16}$ , and dividing that by $\Delta$ makes it explode as $\Delta\to0$ : the sweet spot is around $10^{-5}$ , not zero.

The picture has three regions, and each teaches something. On the right (large $\Delta$ ) both estimates are poor — a wide secant is nowhere near the tangent. In the middle, the two curves are straight lines with different slopes: shrink $\Delta$ tenfold and the forward error drops tenfold, but the central error drops a hundredfold. Nudging both ways cancels the ground's curl (the second-derivative term) that the one-sided nudge leaves behind — Unit 8's Taylor lines say exactly which terms survive. On the left (tiny $\Delta$ ) both curves turn back up: the height moves by less than the computer's sixteen digits can tell, the true digits cancel, and what is left is rounding noise divided by a tiny number. The sweet spot is a moderately small $\Delta$ , and the audit is a spot check of a few knobs — never the way you compute gradients for real.

The realization

Forward: $\dfrac{J(w+\Delta)-J(w)}{\Delta}$ , error $\approx\tfrac12J''\Delta$ . Central: $\dfrac{J(w+\Delta)-J(w-\Delta)}{2\Delta}$ , error $\approx\tfrac16J'''\Delta^2$ . On $J=w_1^3+w_1w_2^2$ at $(2,1)$ with $\Delta=0.1$ : true $13$ , forward $13.61$ , central $13.01$ .

Pause & predict

With $\Delta=0.1$ the central estimate of a tilt is off by $0.01$ . You shrink $\Delta$ to $0.01$ . Roughly what is the new error?

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

Prove it · forward error ∝ Δ, central error ∝ Δ²

Claim. For a smooth one-variable $J$ , the forward difference errs by about $\tfrac12J''\Delta$ and the central difference by about $\tfrac16J'''\Delta^2$ .

1

Taylor at

w

, one step forward and one step back:

\begin{aligned}J(w+\Delta)&=J+J'\Delta+\tfrac12J''\Delta^2+\tfrac16J'''\Delta^3+\cdots\\ J(w-\Delta)&=J-J'\Delta+\tfrac12J''\Delta^2-\tfrac16J'''\Delta^3+\cdots\end{aligned}

Same series, with

\Delta

replaced by

-\Delta

: odd powers flip sign, even powers do not.

2

Forward: subtract

J

and divide by

\Delta

:

\begin{aligned}\frac{J(w+\Delta)-J(w)}{\Delta}&=J'+\tfrac12J''\Delta+\cdots\\ \text{error}&\approx\tfrac12J''\,\Delta.\end{aligned}

The leading leftover is the bend term; it shrinks only as fast as

\Delta

.

3

Central: subtract the backward series from the forward one — every even-power term cancels — and divide by

2\Delta

:

\begin{aligned}\frac{J(w+\Delta)-J(w-\Delta)}{2\Delta}&=\frac{2J'\Delta+\tfrac13J'''\Delta^3+\cdots}{2\Delta}\\ &=J'+\tfrac16J'''\Delta^2+\cdots\end{aligned}

∎ The bend term is gone; the error is

\Delta^2

-sized. Halve

\Delta

and the forward error halves but the central error quarters. On the widget's example,

J=w_1^3+w_1w_2^2

at

(2,1)

with

\Delta=0.1

: forward

13.61

(error

0.61\approx\tfrac12\cdot12\cdot0.1

), central

13.01

(error

0.01=\tfrac16\cdot6\cdot0.01

). Practice Problem 8.

In one sentence: Audit a coded gradient by nudging a few knobs; nudging both ways is a hundred times better for a tenfold smaller nudge, until rounding drowns everything.

10

Three ways to walk — batch, minibatch, stochastic

One spoon, not the pot

A cook checking whether the soup needs salt does not drink the whole pot. One spoonful, stirred from anywhere, is enough to decide "a pinch more". She adds it, stirs, tastes another spoon. Fifty small, slightly-wrong decisions get the soup right faster than one perfect measurement that requires drinking the pot. A real loss is the pot: the wrongness is a sum over every example, so the tilt costs one pass over all the data — every single step. The spoonful is the whole idea of this section.

There are three walkers, and they differ in exactly one thing: how much of the data they read before each step. Batch reads everything, so its tilt is exact. Minibatch reads a handful — a spoonful — and steps on the tilt of that handful. Stochastic reads a single example and steps on that. Put all three on the same bowl, same start, same stride, and race them. Then change what "fair" means:

Try: press ▶ in the fair per step view and batch looks best. Switch to fair per data read and press ▶ again: while batch is still reading its first 40 points, the stochastic walker has already sprinted to the bottom — then jitters there until you switch on decay.

drag the picture to orbit

minibatch |S|8

step size γ0.04

—

A full gradient costs all $N$ residuals; a minibatch of $|S|$ costs $|S|$ , with the same expected direction and noise shrinking like $1/\sqrt{|S|}$ . Judged per step, batch wins. Judged per point of data read — the only budget that matters when $N$ is millions — the noisy walkers are far ahead, and a decaying step size lets them settle at the end.

The race has two verdicts, and both are right. Judged per step, batch looks best: smooth, straight, no wobble; the other two jitter. Judged per point of data read — the only budget that matters when the data is millions of examples — the picture flips completely. By the time batch has read its first forty points and taken one step, the stochastic walker has taken forty and is already most of the way down. The loss chart on the right is the whole lesson: against data read, the noisy walkers plunge and the exact one ambles. That is not a trick of this example. It is why every large model you have heard of was trained on minibatches.

Why can a spoonful steer at all? Because it is right on average. Each example's tilt points a little differently, but the true tilt is their average, so a random handful's tilt scatters around the true one — not to one side of it. Over many steps the scatter cancels and the drift is exactly the batch walker's direction. And the scatter shrinks as the spoon grows: four times the batch, half the noise. Bigger spoon, calmer walk, dearer step. Minibatch is the dial between the two extremes, and in practice it is set by the hardware (whatever fits in memory at once) as much as by the maths.

	Batch	Minibatch (\|S\| points)	Stochastic
reads before each step	all $N$ examples	a random handful, $\|S\|$	one random example
cost of one step	$N$	$\|S\|$	$1$
tilt used	exact	right on average, noise $\propto1/\sqrt{\|S\|}$	right on average, noisiest
the path	smooth, slow per data read	slightly wobbly, fast	jittery, fastest early, never settles at fixed stride
the bottom	reaches it exactly	hovers within a small cloud; settles with a decaying stride	hovers in a bigger cloud; settles with a decaying stride
use it when	data is small, or the exact tilt matters	almost always — this is deep learning's default	streaming data, one example at a time

The realization

The loss is a sum, $L=\sum_n L_n$ , so the tilt is a sum of per-example tilts. A random handful $S$ gives $\nabla J(S)=\sum_{i\in S}\nabla L_i$ , and scaled by $N/|S|$ its average is exactly $\nabla L$ — unbiased. Its noise falls like $1/\sqrt{|S|}$ . Step on the handful's tilt: $\mathbf w\leftarrow\mathbf w-\alpha\,\nabla J(S)$ . That is minibatch gradient descent; $|S|=1$ is stochastic gradient descent; $|S|=N$ is what we did all unit.

Pause & predict

You have a million examples. One batch step reads all of them. With minibatches of $100$ , how many steps do you get for the same reading, and how good are they?

Pause & predict

In the race, switch from fair per step to fair per data read. Why does the ranking flip?

In one sentence: Batch, minibatch and stochastic differ only in how much data they read before each step; a random spoonful's tilt is right on average with noise

\propto1/\sqrt{|S|}

, so per point of data read the noisy walkers win — which is why deep learning trains on minibatches.

11

Noise, tamed — and noise as a friend

The nervous hand

Try to place a coin exactly on a mark while your hand trembles. Big, confident movements get you close fast — and then the tremble keeps knocking the coin off the mark. The fix every steady-handed person uses without thinking: make the final movements small, so the tremble, which is a fraction of each movement, becomes a fraction of something tiny. A noisy tilt is a trembling hand. The stride is the size of the movement.

Watch one noisy walker up close, with the true tilt and the spoonful's tilt drawn at every step, then switch on a decaying stride:

Try: set the batch to 1 and press ▶: the walk jitters around the bottom and never settles. Switch to the decay tab — the same noisy steps, shrinking with $t$ , calm down onto the minimiser.

batch size4

step size γ0.1

steps80

—

The full gradient averages a residual term over all $N=40$ points; a minibatch averages the same term over $|S|$ of them. The estimate is unbiased — on average it is the true gradient — with variance shrinking like $1/|S|$ . Each step costs $|S|$ residuals instead of $N$ , so a batch of 4 buys ten steps for the price of one exact one.

With a fixed stride the walker never stops. Near the bottom the true tilt is nearly zero, but the spoonful keeps saying "a bit this way", "a bit that way", and the walker jitters in a small cloud around the bottom. The cloud is not a bug in the example; it is what a trembling hand does at any fixed movement size, and its size is proportional to the stride — halve $\gamma$ , halve the cloud. So Section 8's slowing down is not a refinement here: it is the only way the walk ever ends. Shrink the stride over time (fast enough that the cloud closes, slowly enough that the walker still gets wherever it needs to go) and the jitter dies onto the bottom. That is the content of the theorem the lecture quotes — with a suitably decaying rate, stochastic descent settles into a local minimum almost surely — and the widget's decay tab is the theorem happening.

One last turn of the story, and it flips the villain. Remember the two valleys of Section 1 and the shallow dip of Section 3: an exact walker that rolls into a shallow dip is stuck there for ever, because every exact step goes down. A noisy walker is not. Its trembling steps sometimes go up, and on a bumpy landscape a few upward stumbles are enough to hop out of a shallow dip and find a deeper valley. The fog and the noise, the two things that made the walk hard, turn out to be the two things that make it work at scale — and the second one is even, sometimes, the thing that finds a better answer.

The realization

On a bowl of stiffness $\lambda$ with tilt noise of size $\sigma$ , a fixed stride $\gamma$ leaves the walker in a cloud of variance $\approx\gamma\sigma^2/2\lambda$ — proportional to $\gamma$ . A schedule with $\sum\gamma_t=\infty$ and $\sum\gamma_t^2<\infty$ (for instance $\gamma_0/(1+kt)$ ) closes the cloud without stranding the walker.

Pause & predict

You run the single-example walker with a fixed stride. The loss falls fast, then stops improving and wobbles slightly above the minimum. What is going on, and what fixes it?

Pause & predict

Two walkers start in the same shallow dip of a bumpy landscape: one uses exact tilts, one uses single-example tilts. Which can end up in the deeper valley next door, and why?

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

Prove it · the minibatch gradient is unbiased

Claim. If $S$ is a random sample of $m$ indices out of $N$ (each index equally likely to be included), then the scaled sample gradient $\dfrac Nm\sum_{i\in S}\nabla L_i$ has expected value exactly $\nabla L$ .

1

Write the sample sum with an indicator for each example:

\mathbb 1_n=1

if

n\in S

, else

0

. Then

\sum_{i\in S}\nabla L_i=\sum_{n=1}^{N}\mathbb 1_n\,\nabla L_n.

Summing over "the chosen ones" is the same as summing over everyone with a switch that is on only for the chosen.

2

Take expectations. The gradients

\nabla L_n

are fixed numbers; only the switches are random, and each is on with probability

m/N

:

\begin{aligned}\mathbb E\Big[\sum_{n}\mathbb 1_n\nabla L_n\Big]&=\sum_n\mathbb E[\mathbb 1_n]\,\nabla L_n\\ &=\sum_n\frac mN\,\nabla L_n=\frac mN\,\nabla L.\end{aligned}

Expectation of a sum is the sum of expectations; the expectation of a 0/1 switch is the probability it is on. Every example is in the sample with the same chance,

m/N

.

3

Multiply by

N/m

:

\ \mathbb E\big[\tfrac Nm\sum_{i\in S}\nabla L_i\big]=\nabla L

. ∎ "Unbiased" means: on average, over many spoonfuls, the estimate is exactly the true gradient. It does not mean any single spoonful is right — a single one can point well off. The scale factor

N/m

is absorbed into the learning rate in practice, which is why the lecture's update simply uses

\nabla J(S)

.

Prove it · bigger spoon, less noise — variance falls like 1/|S|

Claim. If the per-example gradients are drawn independently with variance $\sigma^2$ (per component), the average of $m$ of them has variance $\sigma^2/m$ .

1

Let

g_1,\ldots,g_m

be the sampled gradients (one component) and

\bar g=\tfrac1m\sum_i g_i

their average. Pulling the constant out of a variance squares it:

\operatorname{Var}(\bar g)=\frac1{m^2}\operatorname{Var}\Big(\sum_ig_i\Big).

\operatorname{Var}(cX)=c^2\operatorname{Var}(X)

.

2

For independent draws the variance of a sum is the sum of variances:

\operatorname{Var}\Big(\sum_ig_i\Big)=\sum_i\sigma^2=m\sigma^2.

Independence kills the cross-terms; each draw contributes

\sigma^2

.

3

So

\operatorname{Var}(\bar g)=\dfrac{m\sigma^2}{m^2}=\dfrac{\sigma^2}{m}

, and the typical size of the noise (the standard deviation) is

\sigma/\sqrt m

. ∎ Four times the batch, half the noise. That is the lecture's last line — large minibatches give lower variance — and the trade it names: a bigger spoon is a better estimate but a dearer step. In the widget,

|S|=4

out of

40

buys ten steps for the price of one exact one, with half the noise of a single example.

Prove it · a constant step leaves a jitter cloud proportional to γ

Claim. On $f=\tfrac12\lambda x^2$ with a noisy gradient $\lambda x_k+\varepsilon_k$ (noise of mean $0$ , variance $\sigma^2$ , independent step to step) and a constant $\gamma<2/\lambda$ , the iterates settle into a cloud around $0$ of variance $\dfrac{\gamma\sigma^2}{\lambda(2-\gamma\lambda)}\approx\dfrac{\gamma\sigma^2}{2\lambda}$ .

1

The noisy update is

x_{k+1}=x_k-\gamma(\lambda x_k+\varepsilon_k)=(1-\gamma\lambda)\,x_k-\gamma\varepsilon_k.

Section 5's factor, plus a random kick of size

\gamma\varepsilon_k

every step.

2

Square and take expectations. The cross-term vanishes because

\varepsilon_k

has mean

0

and is independent of

x_k

:

\mathbb E[x_{k+1}^2]=(1-\gamma\lambda)^2\,\mathbb E[x_k^2]+\gamma^2\sigma^2.

(a-b)^2=a^2-2ab+b^2

; the middle term's expectation is

2(1-\gamma\lambda)\gamma\,\mathbb E[x_k]\mathbb E[\varepsilon_k]=0

.

3

In the long run the spread stops changing:

\mathbb E[x_{k+1}^2]=\mathbb E[x_k^2]=V

. Then

\begin{aligned}V&=(1-\gamma\lambda)^2V+\gamma^2\sigma^2\\ V\big(1-(1-\gamma\lambda)^2\big)&=\gamma^2\sigma^2\\ V&=\frac{\gamma^2\sigma^2}{\gamma\lambda(2-\gamma\lambda)}=\frac{\gamma\sigma^2}{\lambda(2-\gamma\lambda)}.\end{aligned}

∎

1-(1-\gamma\lambda)^2=\gamma\lambda(2-\gamma\lambda)

(difference of squares). For small

\gamma

this is

\approx\gamma\sigma^2/2\lambda

: the cloud's variance is proportional to $\gamma$ . Halve the step and you halve the cloud; only

\gamma\to0

shrinks it to a point — which is exactly what a decaying schedule does.

In one sentence: A noisy tilt is a trembling hand — a fixed stride leaves a jitter cloud proportional to

\gamma

, a decaying stride closes it, and the same tremble is what lets a walker hop out of a shallow dip.

12

What to carry forward

One reflex — feel the tilt, step the other way — and every section was a picture of one question about that step.

The picture	What it says	The line of math it becomes
The fog	you only ever need the tilt under your feet — and you find the valley downhill from where you start	$\mathbf x\leftarrow\mathbf x-\gamma\nabla f$
The four receipts	say what "wrong" means and a landscape appears; its tilt is "which way should the line move"	$\nabla L=(-2\sum x_ir_i,\,-2\sum r_i)$
The marble	flat ground comes as valley, hilltop, saddle — the curl decides	$f'=0$ , sign of $f''$ (the Hessian in 2-D)
The two springs	a bowl's tilt is a spring; a trench is a stiff and a soft one	$\nabla f=A\mathbf x+\mathbf b$ , eigenvalues = stiffnesses
The bouncing ball	each step multiplies the distance by a factor; the stiffest spring sets the speed limit	$1-\gamma\lambda$ , $\ \gamma<2/\lambda_{\max}$
Sliding the foot	stop where the ray kisses a contour; the next tilt is at a right angle	$\gamma^*=\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g$
The radio dial	squeeze a bracket: halve it, golden-cut it, or accept "good enough"	$(b-a)/2^k$ , $0.618$ , Armijo
Parking the car	fast far away, slow near the wall	$\alpha_0e^{-kt}$ , $\alpha_0/(1+kt)$ , step; bold driver
The known weight	test the compass by nudging; two-sided nudges are far better	error $\propto\Delta$ vs $\propto\Delta^2$
One spoon, not the pot	a random handful's tilt is right on average; per data read, noisy wins	$\mathbb E[\nabla J(S)]\propto\nabla L$ , noise $\propto1/\sqrt{\|S\|}$
The trembling hand	a fixed stride leaves a cloud; a shrinking stride closes it; the tremble can hop a lip	cloud $\propto\gamma$ ; $\sum\gamma_t=\infty,\ \sum\gamma_t^2<\infty$

The one thing to remember

Feel the slope, step against it, and let the stiffest direction set your stride. The tilt is the only map you get in the fog; a stride under $2/\lambda_{\max}$ always goes down; a trench makes that stride tiny and the walk a zig-zag; and when the data is too big to read, a random spoonful of it points the right way on average. Everything the next units add — momentum, Newton, constraints — is a way of walking the same fog more cleverly.

13

Practice arena — twelve problems, solved in full

Twelve problems, easy to hard, covering the whole walk: classifying flat spots, tracing gradient-descent steps by hand, learning-rate schedules, the line-search stride derived and applied, gradient checking, a coupled bowl, training a straight line by descent, and a bracketing trace. Every number below is machine-verified.

Two habits do most of the work: trace steps in a table — point, tilt, new point, height — so nothing is lost in the bookkeeping; and for any stride question, find the stiffest spring first, because $2/\lambda_{\max}$ is the limit and $1-\gamma\lambda$ is the whole story of the approach.

Problem 1easy

Let $f(x)=2x^3-9x^2+12x+5$ . (a) Find every stationary point of $f$ . (b) Classify each one with the second-derivative test and give the value of $f$ there. (c) Does $f$ have a global minimum over the whole real line? Say why.

What this tests. The one-variable routine that every descent method is built on — set the slope to zero, read the curvature, and then ask the question people skip: what happens far away. Plan. Differentiate and factor (try small integers first); evaluate $f''$ at each root; compute the values; finish by looking at $x\to\pm\infty$ before saying anything about "global".

Show the full solution

(a) Step 1 — set the slope to zero. Differentiate term by term and pull out the common factor:

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

So

f'(x)=0

exactly at

x=1

and

x=2

. These are the two stationary points.

(b) Step 2 — read the curvature. The second derivative is

f''(x)=12x-18

:

\begin{aligned} f''(1)&=12-18=-6<0 &&\Rightarrow\ \text{local maximum at }x=1,\\ f''(2)&=24-18=+6>0 &&\Rightarrow\ \text{local minimum at }x=2. \end{aligned}

Step 3 — the values. Substitute each point into

f

, one term at a time:

\begin{aligned} f(1)&=2(1)-9(1)+12(1)+5=2-9+12+5=10,\\ f(2)&=2(8)-9(4)+12(2)+5=16-36+24+5=9. \end{aligned}

The local maximum is

10

at

x=1

; the local minimum is

9

at

x=2

. Notice the hill top is only

1

higher than the valley floor — a gentle wobble in the middle of a steep cubic.

(c) Step 4 — look far away. The leading term

2x^3

has odd degree, so as

x\to-\infty

the function runs off to

-\infty

. For instance

f(-10)=-2000-900-120+5=-3015

, far below

9

. A function that goes below every level has no global minimum;

x=2

is a local minimum only.

(a) $x=1$ and $x=2$ . (b) $x=1$ : local maximum, $f=10$ ( $f''=-6$ ); $x=2$ : local minimum, $f=9$ ( $f''=+6$ ). (c) No — a cubic is unbounded below, so there is no global minimum.

Remember

"Slope zero" finds candidates; "curvature sign" sorts them; only a look at $\pm\infty$ earns the word global. The usual slip on this type is stopping after step 2 and calling $x=2$ the minimum of $f$ , when a cubic has no floor at all — and gradient descent started far to the left would simply run away forever.

Problem 2easy

Apply gradient descent to $f(x,y)=x^2+2y^2$ with step size $\gamma=0.1$ , starting at $(x_0,y_0)=(4,2)$ . (a) Write the update equations for $x$ and $y$ . (b) Carry out two iterations, reporting the point and the value of $f$ after each. (c) Check that $f$ went down at every step.

What this tests. The update rule itself on a bowl whose two coordinates do not talk to each other — and the discipline of keeping a table. Plan. Compute the gradient symbolically first, so each coordinate's update becomes "multiply by a constant"; then fill a row per iteration: point, gradient, new point, $f$ ; finally read the $f$ column top to bottom.

Show the full solution

(a) Step 1 — the update rule, coordinate by coordinate. The gradient is

\nabla f=(2x,\,4y)

. The update rule

\mathbf x_{k+1}=\mathbf x_k-\gamma\nabla f(\mathbf x_k)

then reads

\begin{aligned} x_{k+1}&=x_k-0.1\,(2x_k)=x_k-0.2x_k=0.8\,x_k,\\ y_{k+1}&=y_k-0.1\,(4y_k)=y_k-0.4y_k=0.6\,y_k. \end{aligned}

Each coordinate simply shrinks by its own fixed factor,

1-\gamma\times(\text{its curvature})

:

1-0.1\cdot2=0.8

for

x

and

1-0.1\cdot4=0.6

for

y

.

(b) Step 2 — iterate in a table.

$k$	point $(x_k,y_k)$	gradient $(2x_k,4y_k)$	new point	$f(x_k,y_k)$
0	$(4,\,2)$	$(8,\,8)$	$(4,2)-0.1(8,8)=(3.2,\,1.2)$	$16+2\cdot4=16+8=24$
1	$(3.2,\,1.2)$	$(6.4,\,4.8)$	$(3.2,1.2)-0.1(6.4,4.8)=(2.56,\,0.72)$	$10.24+2\cdot1.44=10.24+2.88=13.12$
2	$(2.56,\,0.72)$	—	—	$6.5536+2\cdot0.5184=6.5536+1.0368=7.5904$

The shortcut from part (a) gives the same points with no gradient at all:

0.8\cdot4=3.2

,

0.6\cdot2=1.2

; then

0.8\cdot3.2=2.56

,

0.6\cdot1.2=0.72

.

(c) Step 3 — read the $f$ column.

24\ >\ 13.12\ >\ 7.5904.

The value fell at both steps. Both coordinates are heading for the minimiser

(0,0)

, and

y

gets there faster because its factor

0.6

is smaller than

0.8

— the steeper direction is the quicker one when the step size is safely small.

(a) $x_{k+1}=0.8x_k$ , $y_{k+1}=0.6y_k$ . (b) $(3.2,1.2)$ with $f=13.12$ ; then $(2.56,0.72)$ with $f=7.5904$ . (c) $24>13.12>7.5904$ : strictly decreasing.

Remember

Always work in a table — point, gradient, new point, $f$ — so no arithmetic goes missing between rows. On a separable bowl each coordinate shrinks by its own factor $1-\gamma\lambda$ ; this is the same number that decides stability in Problem 11. The common slip is subtracting the gradient without the $\gamma$ , or evaluating $f$ at the old point instead of the new one.

Problem 3easy

Training starts with learning rate $\alpha_0=0.8$ and decay constant $k=0.05$ . (a) Compute $\alpha_t$ at $t=10$ and $t=20$ under exponential decay $\alpha_t=\alpha_0e^{-kt}$ and under inverse decay $\alpha_t=\alpha_0/(1+kt)$ . (b) Under step decay that divides $\alpha$ by $3$ every $5$ epochs, what is $\alpha$ during epoch $t=12$ ? (c) At which epoch does inverse decay first reach $\alpha_0/2$ ?

What this tests. The three decay schedules as plug-in formulas, plus one small piece of reasoning about how a schedule reads its counter. Plan. Compute $kt$ once for each $t$ and reuse it in both formulas; for step decay count how many divisions have happened before epoch 12; for (c) set the formula equal to half and solve for $t$ .

Show the full solution

(a) Step 1 — exponential versus inverse. With

k=0.05

:

kt=0.5

at

t=10

and

kt=1

at

t=20

.

\begin{aligned} \text{exponential:}\quad \alpha_{10}&=0.8\,e^{-0.5}=0.8\times0.6065=0.4852,\\ \alpha_{20}&=0.8\,e^{-1}=0.8\times0.3679=0.2943;\\[4pt] \text{inverse:}\quad \alpha_{10}&=\frac{0.8}{1+0.5}=\frac{0.8}{1.5}=0.5333,\\ \alpha_{20}&=\frac{0.8}{1+1}=\frac{0.8}{2}=0.4. \end{aligned}

Exponential decay is the more aggressive of the two: geometric shrinking beats the slow

1/t

fade of the inverse schedule.

(b) Step 2 — step decay. The rate is divided by

3

at

t=5

and again at

t=10

; the next division is at

t=15

. So epoch

12

sits in the third block, after two divisions:

\alpha=\frac{0.8}{3^2}=\frac{0.8}{9}\approx0.0889.

(c) Step 3 — when inverse decay halves. Set the formula equal to

\alpha_0/2

and cancel

\alpha_0

:

\begin{aligned} \frac{\alpha_0}{1+kt}&=\frac{\alpha_0}{2}\\ 1+kt&=2\\ kt&=1\\ t&=\frac1k=\frac{1}{0.05}=20\ \text{epochs}. \end{aligned}

A pleasing pattern: at the same

t=1/k

, exponential decay has multiplied the rate by

1/e

(that is the

0.2943

from part (a)).

(a) exponential: $0.4852$ at $t=10$ , $0.2943$ at $t=20$ ; inverse: $0.5333$ and $0.4$ . (b) $0.8/9\approx0.0889$ . (c) $t=1/k=20$ .

Remember

In the update $\mathbf w_{t+1}=\mathbf w_t-\alpha_t\nabla J$ the counter $t$ is in epochs, so $\alpha$ is constant inside an epoch. The one place this type goes wrong is the step schedule — count the divisions that have already happened (two by epoch 12), not the block number.

Problem 4easy

Let $f(x,y)=x^2+y^2-2x-4y+5$ . (a) Find the exact minimiser $(x^*,y^*)$ and the minimum value. (b) Run two gradient-descent iterations from $(0,0)$ with $\gamma=0.25$ , reporting $f$ each time.

What this tests. Knowing the destination before you start walking — complete the square, then watch every iterate land closer to it. Plan. Rewrite $f$ as a sum of squares to read off the minimiser (and confirm with $\nabla f=\mathbf 0$ ); then two table rows; finally compare each $f$ with the previous one and spot the fixed ratio.

Show the full solution

(a) Step 1 — complete the square. Group the

x

terms and the

y

terms:

\begin{aligned} f&=(x^2-2x)+(y^2-4y)+5\\ &=(x-1)^2-1+(y-2)^2-4+5\\ &=(x-1)^2+(y-2)^2. \end{aligned}

A sum of two squares is smallest when both squares are zero, so the minimiser is

(x^*,y^*)=(1,2)

with

f^*=0

. The same point comes from the gradient:

\nabla f=(2x-2,\ 2y-4)=(0,0)

gives

x=1,\ y=2

.

(b) Step 2 — iteration 1. At

(0,0)

the value is

f=1+4=5

and the gradient is

\nabla f(0,0)=(2\cdot0-2,\ 2\cdot0-4)=(-2,\,-4).

Step:

\begin{aligned} (x_1,y_1)&=(0,0)-0.25\,(-2,-4)=(0.5,\ 1),\\ f(x_1,y_1)&=(0.5-1)^2+(1-2)^2\\ &=(-0.5)^2+(-1)^2=0.25+1=1.25. \end{aligned}

Step 3 — iteration 2. At

(0.5,1)

:

\begin{aligned} \nabla f(0.5,1)&=(2\cdot0.5-2,\ 2\cdot1-4)=(-1,\,-2),\\ (x_2,y_2)&=(0.5,1)-0.25\,(-1,-2)=(0.75,\ 1.5),\\ f(x_2,y_2)&=(0.75-1)^2+(1.5-2)^2\\ &=(-0.25)^2+(-0.5)^2=0.0625+0.25=0.3125. \end{aligned}

So

f:\ 5\to1.25\to0.3125

, closing in on

(1,2)

.

Step 4 — the pattern behind the numbers. Both curvatures equal

2

, so each coordinate's distance to the target is multiplied by

1-\gamma\cdot2=1-0.5=0.5

per step: the point moves exactly halfway to

(1,2)

every time. Since

f

is a squared distance, it shrinks by

0.5^2=\tfrac14

:

5/4=1.25

,

1.25/4=0.3125

. If you needed

f\le0.01

, keep dividing by

4

:

0.078,\ 0.0195,\ 0.0049

— three more steps, five in total.

(a) $(x^*,y^*)=(1,2)$ , $f^*=0$ . (b) $(0.5,1)$ with $f=1.25$ , then $(0.75,1.5)$ with $f=0.3125$ ; $f$ is divided by $4$ at every step.

Remember

Completing the square first gives you the answer key: every iterate can be checked against the destination, and the ratio $1-\gamma\lambda$ tells you how fast you approach it. The slip to watch for here is a sign error when the gradient is negative — subtracting $\gamma\times(-2)$ adds $0.5$ .

Problem 5medium

Let $f(x,y)=x^3-3x+y^2-2y$ . (a) Find all critical points (where $\nabla f=\mathbf 0$ ). (b) Classify each one using the Hessian. (c) Evaluate $f$ at each critical point and say which one gradient descent can converge to.

What this tests. The two-variable version of Problem 1, and the fact that "gradient zero" is where descent stops, not necessarily where it should. Plan. The two gradient equations separate, so solve each on its own; the Hessian is diagonal, so its eigenvalues are just the diagonal entries; evaluate, then ask which point a descent path can actually settle at.

Show the full solution

(a) Step 1 — solve $\nabla f=\mathbf 0$ .

\nabla f=\big(3x^2-3,\ 2y-2\big)=(0,0).

The first equation gives

3x^2=3

, so

x=\pm1

; the second gives

2y=2

, so

y=1

. Two critical points:

P_1=(1,1),\qquad P_2=(-1,1).

(b) Step 2 — the Hessian.

f_{xx}=6x,\ f_{yy}=2,\ f_{xy}=0

:

H(x,y)=\begin{bmatrix}6x&0\\0&2\end{bmatrix}.

A diagonal matrix has its eigenvalues on the diagonal, so the classification is immediate:

\begin{aligned} P_1=(1,1):&\quad H=\begin{bmatrix}6&0\\0&2\end{bmatrix},\ \text{eigenvalues }6,2>0\ \Rightarrow\ \text{local minimum};\\ P_2=(-1,1):&\quad H=\begin{bmatrix}-6&0\\0&2\end{bmatrix},\ \text{eigenvalues }-6,2\ \Rightarrow\ \text{saddle}. \end{aligned}

At

P_2

the surface curves down along

x

and up along

y

: a mountain pass.

(c) Step 3 — values and the reachable point.

\begin{aligned} f(1,1)&=1-3+1-2=-3,\\ f(-1,1)&=-1+3+1-2=1. \end{aligned}

Gradient descent from any sensible start heads for the local minimum

P_1=(1,1)

. At the saddle

P_2

the gradient is also zero, so a path that landed exactly there would stop — but the slightest nudge in

x

(either way:

f(-1.1,1)<1

and

f(-0.9,1)<1

) sends it downhill again. Note also that

f

has no global minimum:

x^3-3x\to-\infty

as

x\to-\infty

, so a start far to the left of the saddle slides away forever.

(a) $(1,1)$ and $(-1,1)$ . (b) $(1,1)$ : eigenvalues $6,2$ , local minimum; $(-1,1)$ : eigenvalues $-6,2$ , saddle. (c) $f(1,1)=-3$ , $f(-1,1)=1$ ; descent targets $(1,1)$ .

Remember

$\nabla f=\mathbf 0$ alone never proves a minimum — saddles satisfy it too, and gradient descent is blind to the difference until a nudge comes along. For a diagonal Hessian the eigenvalues are the diagonal entries: all positive is a bowl, mixed signs is a saddle. The slip on this type is forgetting the negative root $x=-1$ .

Problem 6medium

Let $f(\mathbf x)=\tfrac12\mathbf x^{\top}A\mathbf x-\mathbf b^{\top}\mathbf x$ with $A=\begin{bmatrix}4&1\\1&3\end{bmatrix},\qquad \mathbf b=\begin{bmatrix}1\\2\end{bmatrix}.$ (a) Write $\nabla f$ and find the exact minimiser $\mathbf x^*$ and $f(\mathbf x^*)$ . (b) From $\mathbf x_0=(0,0)$ take one step with fixed $\gamma=0.1$ and evaluate $f$ . (c) Show that the exact line-search step from $\mathbf x$ along $-\mathbf g$ , where $\mathbf g=\nabla f(\mathbf x)$ , is $\gamma^*=\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g$ ; use it from the same $\mathbf x_0$ and compare with (b).

What this tests. The quadratic model in matrix language — gradient $A\mathbf x-\mathbf b$ , minimiser from a linear system — and the three-line derivation of the line-search formula. Plan. Solve $A\mathbf x=\mathbf b$ by substitution; use $A\mathbf x^*=\mathbf b$ to shortcut $f^*$ ; do the fixed step in pieces ( $A\mathbf x$ , then the two dot products); derive $\gamma^*$ by differentiating $h(\gamma)=f(\mathbf x-\gamma\mathbf g)$ ; then plug the numbers in and line the three values up.

Show the full solution

(a) Step 1 — gradient and minimiser. For this quadratic,

\nabla f(\mathbf x)=A\mathbf x-\mathbf b

. Setting it to zero means solving

A\mathbf x=\mathbf b

:

4x+y=1,\qquad x+3y=2.

From the first,

y=1-4x

. Substitute into the second:

\begin{aligned} x+3(1-4x)&=2\\ x+3-12x&=2\\ -11x&=-1\\ x&=\tfrac1{11},\qquad y=1-\tfrac4{11}=\tfrac7{11}. \end{aligned}

So

\mathbf x^*=\big(\tfrac1{11},\tfrac7{11}\big)\approx(0.091,\,0.636)

. Since

4>0

and

\det A=12-1=11>0

,

A

is positive-definite and this is the unique global minimum.

Step 2 — the minimum value, the short way. Because

A\mathbf x^*=\mathbf b

, we have

\mathbf x^{*\top}A\mathbf x^*=\mathbf x^{*\top}\mathbf b=\mathbf b^{\top}\mathbf x^*

, so

\begin{aligned} f(\mathbf x^*)&=\tfrac12\,\mathbf b^{\top}\mathbf x^*-\mathbf b^{\top}\mathbf x^*=-\tfrac12\,\mathbf b^{\top}\mathbf x^*\\ &=-\tfrac12\Big(1\cdot\tfrac1{11}+2\cdot\tfrac7{11}\Big)=-\tfrac12\cdot\tfrac{15}{11}=-\tfrac{15}{22}\approx-0.682. \end{aligned}

(b) Step 3 — one fixed step, $\gamma=0.1$ . At the origin

\mathbf g_0=\nabla f(\mathbf 0)=A\mathbf 0-\mathbf b=(-1,-2)

, so

\mathbf x_1=\mathbf 0-0.1\,(-1,-2)=(0.1,\ 0.2).

Evaluate

f(\mathbf x_1)

in pieces:

\begin{aligned} A\mathbf x_1&=(4\cdot0.1+0.2,\ 0.1+3\cdot0.2)=(0.6,\ 0.7),\\ \mathbf x_1^{\top}A\mathbf x_1&=0.1\cdot0.6+0.2\cdot0.7=0.06+0.14=0.2,\\ \mathbf b^{\top}\mathbf x_1&=1\cdot0.1+2\cdot0.2=0.1+0.4=0.5,\\ f(\mathbf x_1)&=\tfrac12(0.2)-0.5=0.1-0.5=-0.4. \end{aligned}

(c) Step 4 — derive the line-search formula. Let

h(\gamma)=f(\mathbf x-\gamma\mathbf g)

. By the chain rule, with

\nabla f(\mathbf z)=A\mathbf z-\mathbf b

,

\begin{aligned} h'(\gamma)&=-\mathbf g^{\top}\nabla f(\mathbf x-\gamma\mathbf g)\\ &=-\mathbf g^{\top}\big(A\mathbf x-\gamma A\mathbf g-\mathbf b\big)\\ &=-\mathbf g^{\top}\big(\underbrace{A\mathbf x-\mathbf b}_{=\,\mathbf g}\big)+\gamma\,\mathbf g^{\top}A\mathbf g\\ &=-\mathbf g^{\top}\mathbf g+\gamma\,\mathbf g^{\top}A\mathbf g. \end{aligned}

Setting

h'(\gamma)=0

:

\gamma^*=\frac{\mathbf g^{\top}\mathbf g}{\mathbf g^{\top}A\mathbf g}.

It is a true minimum of

h

, because

h''=\mathbf g^{\top}A\mathbf g>0

for positive-definite

A

.

Step 5 — apply it at $\mathbf x_0$ . With

\mathbf g_0=(-1,-2)

:

\begin{aligned} \mathbf g_0^{\top}\mathbf g_0&=1+4=5,\\ A\mathbf g_0&=(-4-2,\ -1-6)=(-6,\ -7),\\ \mathbf g_0^{\top}A\mathbf g_0&=(-1)(-6)+(-2)(-7)=6+14=20,\\ \gamma^*&=\tfrac{5}{20}=0.25. \end{aligned}

The line-search point and its value:

\begin{aligned} \mathbf x_1^{\mathrm{LS}}&=\mathbf 0-0.25\,(-1,-2)=(0.25,\ 0.5),\\ A\mathbf x_1^{\mathrm{LS}}&=(1+0.5,\ 0.25+1.5)=(1.5,\ 1.75),\\ \mathbf x^{\top}A\mathbf x&=0.25\cdot1.5+0.5\cdot1.75=0.375+0.875=1.25,\\ \mathbf b^{\top}\mathbf x&=0.25+1.0=1.25,\\ f(\mathbf x_1^{\mathrm{LS}})&=\tfrac12(1.25)-1.25=-0.625. \end{aligned}

Step 6 — compare.

after one step	$f$
fixed $\gamma=0.1$	$-0.400$
exact line search, $\gamma^*=0.25$	$-0.625$
optimum $f^*$	$-0.682$

Same direction, better length: one line-search step covers most of the way to the bottom, while the fixed step covers about a third of it.

(a) $\nabla f=A\mathbf x-\mathbf b$ ; $\mathbf x^*=(1/11,\,7/11)$ , $f^*=-15/22\approx-0.682$ . (b) $\mathbf x_1=(0.1,0.2)$ , $f=-0.4$ . (c) $\gamma^*=\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g=0.25$ , $\mathbf x_1^{\mathrm{LS}}=(0.25,0.5)$ , $f=-0.625$ .

Remember

For a quadratic, the line-search formula $\gamma^*=\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g$ comes from three lines — differentiate $h$ , recognise $A\mathbf x-\mathbf b$ as $\mathbf g$ , set to zero — so re-derive it rather than recall it. Watch the sign convention: with $-\mathbf b^{\top}\mathbf x$ in $f$ the gradient is $A\mathbf x-\mathbf b$ and the optimum solves $A\mathbf x=\mathbf b$ ; with $+\mathbf b^{\top}\mathbf x$ both signs flip.

Problem 7medium

Gradient descent is applied to $f(x,y)=3x^2+y^2$ from $(x_0,y_0)=(1,3)$ , choosing at each step the $\gamma$ that minimises $h(\gamma)=f\big((x,y)-\gamma\nabla f(x,y)\big)$ . (a) Show that $h(\gamma)=3(1-6\gamma)^2x^2+(1-2\gamma)^2y^2$ and derive $\gamma^*=\dfrac{9x^2+y^2}{54x^2+2y^2}$ . (b) Evaluate $\gamma^*$ at $(1,3)$ ; compute the new point and the new value of $f$ .

What this tests. Building the one-variable function $h$ by hand and minimising it — the line-search formula derived from scratch on a separable bowl. Plan. Write the trial point with a factor $(1-c_i\gamma)$ on each coordinate, where $c_i$ is that coordinate's gradient coefficient; substitute into $f$ ; differentiate in $\gamma$ ; solve the linear equation; then put the numbers in.

Show the full solution

(a) Step 1 — build $h$ . The gradient is

\nabla f=(6x,\,2y)

, so the trial point is

\big(x-\gamma\cdot6x,\ y-\gamma\cdot2y\big)=\big((1-6\gamma)\,x,\ (1-2\gamma)\,y\big).

Substituting into

f=3x^2+y^2

:

h(\gamma)=3(1-6\gamma)^2x^2+(1-2\gamma)^2y^2.

Step 2 — minimise $h$ . Differentiate with the chain rule (the inner derivatives are

-6

and

-2

):

\begin{aligned} h'(\gamma)&=3\cdot2(1-6\gamma)(-6)\,x^2+2(1-2\gamma)(-2)\,y^2\\ &=-36x^2(1-6\gamma)-4y^2(1-2\gamma). \end{aligned}

Set

h'(\gamma)=0

, expand, and collect the

\gamma

terms:

\begin{aligned} -36x^2+216\gamma x^2-4y^2+8\gamma y^2&=0\\ \gamma\,(216x^2+8y^2)&=36x^2+4y^2\\ \gamma^*&=\frac{36x^2+4y^2}{216x^2+8y^2}=\frac{9x^2+y^2}{54x^2+2y^2}, \end{aligned}

dividing top and bottom by

4

in the last line. It is a minimum because

h''(\gamma)=216x^2+8y^2>0

.

(b) Step 3 — evaluate at $(1,3)$ .

\gamma^*=\frac{9(1)+9}{54(1)+2(9)}=\frac{18}{72}=\frac14.

Step 4 — new point and new value. Use the factors from Step 1 with

\gamma=\tfrac14

:

\begin{aligned} x_1&=\big(1-6\cdot\tfrac14\big)\cdot1=\big(1-\tfrac32\big)=-\tfrac12,\\ y_1&=\big(1-2\cdot\tfrac14\big)\cdot3=\tfrac12\cdot3=\tfrac32. \end{aligned}

Before and after:

\begin{aligned} f(1,3)&=3+9=12,\\ f\big(-\tfrac12,\tfrac32\big)&=3\cdot\tfrac14+\tfrac94=\tfrac34+\tfrac94=\tfrac{12}{4}=3. \end{aligned}

One optimally sized step removed three quarters of the objective. Notice

x

overshot past

0

to

-\tfrac12

: the stiff direction (curvature

6

) was pushed too far by a step that was right for the whole line.

(a) $h(\gamma)=3(1-6\gamma)^2x^2+(1-2\gamma)^2y^2$ , $\gamma^*=\dfrac{9x^2+y^2}{54x^2+2y^2}$ . (b) $\gamma^*=\tfrac14$ at $(1,3)$ ; new point $\big(-\tfrac12,\tfrac32\big)$ ; $f:12\to3$ .

Remember

For any $f=ax^2+by^2$ the safe routine is: trial point with factors $(1-c_i\gamma)$ , substitute, differentiate, solve the linear equation for $\gamma$ . Re-derive it every time — a memorised formula breaks the moment the coefficients change. The slip to avoid is dropping the inner derivative $(-6)$ or $(-2)$ when differentiating the squares.

Problem 8medium

Your code computes gradients of $J(w_1,w_2)=w_1^3+w_1w_2^2$ , and you audit it at $(2,1)$ with $\Delta=0.1$ . (a) Compute the analytic gradient at $(2,1)$ . (b) Estimate both partials with the forward difference $\big(J(\dots,w_i+\Delta,\dots)-J(\dots)\big)/\Delta$ and report the absolute errors. (c) Re-estimate $\partial J/\partial w_1$ with the central difference and compare the orders of the two errors.

What this tests. The finite-difference audit — the cheap check that catches a wrong gradient before it silently corrupts every descent step — and why the symmetric version is so much better. Plan. Differentiate by hand first; compute the three needed values of $J$ exactly; form the two quotients; then explain the error sizes with the second and third derivatives.

Show the full solution

(a) Step 1 — the analytic gradient.

\begin{aligned} \frac{\partial J}{\partial w_1}&=3w_1^2+w_2^2 &&\Rightarrow\ 3(4)+1=13\ \text{at }(2,1),\\ \frac{\partial J}{\partial w_2}&=2w_1w_2 &&\Rightarrow\ 2(2)(1)=4\ \text{at }(2,1). \end{aligned}

So

\nabla J(2,1)=(13,\,4)

.

(b) Step 2 — forward differences. The base value is

J(2,1)=8+2=10

. For

w_1

, nudge to

2.1

:

\begin{aligned} J(2.1,1)&=2.1^3+2.1\cdot1^2=9.261+2.1=11.361,\\ \frac{J(2.1,1)-J(2,1)}{0.1}&=\frac{11.361-10}{0.1}=\frac{1.361}{0.1}=13.61\qquad(\text{error }0.61). \end{aligned}

For

w_2

, nudge to

1.1

:

\begin{aligned} J(2,1.1)&=8+2\cdot1.1^2=8+2(1.21)=8+2.42=10.42,\\ \frac{J(2,1.1)-J(2,1)}{0.1}&=\frac{10.42-10}{0.1}=\frac{0.42}{0.1}=4.20\qquad(\text{error }0.20). \end{aligned}

(c) Step 3 — central difference for $w_1$ . One more value, at

1.9

:

\begin{aligned} J(1.9,1)&=1.9^3+1.9=6.859+1.9=8.759,\\ \frac{J(2.1,1)-J(1.9,1)}{2(0.1)}&=\frac{11.361-8.759}{0.2}=\frac{2.602}{0.2}=13.01\qquad(\text{error }0.01). \end{aligned}

Step 4 — why the errors are what they are. Taylor-expand

J

in

w_1

about

2

. The forward quotient picks up the whole second-order term:

\text{forward error}\approx\frac{\Delta}{2}\,\frac{\partial^2J}{\partial w_1^2}=\frac{0.1}{2}\cdot6w_1=\frac{0.1}{2}\cdot12=0.6,

which matches the

0.61

we saw (the extra

0.01

is the third-order term). In the central quotient the

\pm\Delta

evaluations cancel every even-order term, so the first surviving error is third order:

\text{central error}\approx\frac{\Delta^2}{6}\,\frac{\partial^3J}{\partial w_1^3}=\frac{0.01}{6}\cdot6=0.01,

exactly what we found. Forward is

O(\Delta)

, central is

O(\Delta^2)

: shrink

\Delta

tenfold and the forward error drops tenfold (to

0.0601

) but the central error drops a hundredfold (to

0.0001

). For

w_2

the forward error was exactly

\tfrac{\Delta}{2}\cdot\partial^2J/\partial w_2^2=0.05\cdot4=0.20

, because

J

is only quadratic in

w_2

.

(a) $\nabla J(2,1)=(13,4)$ . (b) Forward $(13.61,\,4.20)$ , errors $(0.61,\,0.20)$ . (c) Central $13.01$ , error $0.01$ : forward error $\sim\Delta\cdot6$ , central error $\sim\Delta^2\cdot1$ .

Remember

The central difference costs one extra evaluation and buys an extra order of accuracy — always use it for an audit. A deliberately large $\Delta$ makes the orders visible in your own arithmetic; a tiny $\Delta$ like $10^{-15}$ is worse, not better, because floating-point round-off then swamps the quotient. The usual slip is dividing the central difference by $\Delta$ instead of $2\Delta$ .

Problem 9medium

Steepest descent with exact line search is applied to $J(x,y)=x^2+4y^2$ at $\mathbf w_0=(2,1)$ . (a) Write the descent direction at $\mathbf w_0$ and derive the optimal step $\gamma^*$ by minimising $h(\gamma)=J\big(\mathbf w_0-\gamma\nabla J(\mathbf w_0)\big)$ . (b) Compute $\mathbf w_1$ and the drop in $J$ .

What this tests. The same line-search recipe as Problem 7 on a different bowl, with numbers in place of symbols from the start — and a look at what the optimal step does to the stiff coordinate. Plan. Gradient at the point; write the ray; expand $h'$ into a linear function of $\gamma$ ; solve; substitute; keep everything as exact fractions until the last line.

Show the full solution

(a) Step 1 — direction at $\mathbf w_0$ .

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

, so

\nabla J(2,1)=(4,\,8),\qquad\text{descent direction }=-(4,8).

Step 2 — the ray and $h$ . The trial point is

(2-4\gamma,\ 1-8\gamma)

, hence

h(\gamma)=(2-4\gamma)^2+4(1-8\gamma)^2.

Step 3 — minimise $h$ .

\begin{aligned} h'(\gamma)&=2(2-4\gamma)(-4)+4\cdot2(1-8\gamma)(-8)\\ &=-8(2-4\gamma)-64(1-8\gamma)\\ &=-16+32\gamma-64+512\gamma\\ &=544\gamma-80. \end{aligned}

Set to zero:

\gamma^*=\frac{80}{544}=\frac{5}{34}\approx0.147,

a minimum since

h''=544>0

.

(b) Step 4 — new point and drop in $J$ .

\begin{aligned} \mathbf w_1&=\Big(2-4\cdot\tfrac5{34},\ 1-8\cdot\tfrac5{34}\Big)=\Big(\tfrac{68-20}{34},\ \tfrac{34-40}{34}\Big)\\ &=\Big(\tfrac{48}{34},\ -\tfrac{6}{34}\Big)=\Big(\tfrac{24}{17},\ -\tfrac{3}{17}\Big)\approx(1.412,\ -0.176). \end{aligned}

Values:

\begin{aligned} J(\mathbf w_0)&=4+4=8,\\ J(\mathbf w_1)&=\Big(\tfrac{24}{17}\Big)^2+4\Big(\tfrac{3}{17}\Big)^2=\frac{576+36}{289}=\frac{612}{289}=\frac{36}{17}\approx2.118. \end{aligned}

The single optimal step removed about

74\%

of the objective.

Step 5 — what the sign of $y_1$ is telling you. The

y

-coordinate overshot past

0

, to

-\tfrac3{17}

, while

x

is still on its way. On an elongated bowl even the best step along the gradient goes too far in the stiff direction and not far enough in the gentle one. The next gradient,

\big(\tfrac{48}{17},-\tfrac{24}{17}\big)

, is perpendicular to

(4,8)

— the perpendicularity property of exact line search — so the path must turn a right angle and zig-zag its way down the valley.

(a) direction $-(4,8)$ ; $h'(\gamma)=544\gamma-80$ , so $\gamma^*=5/34\approx0.147$ . (b) $\mathbf w_1=(24/17,\,-3/17)\approx(1.41,-0.18)$ ; $J:8\to36/17\approx2.12$ .

Remember

Keep the fractions: $80/544$ reduces to $5/34$ , and $612/289$ to $36/17$ — decimals hide the check that the two answers are consistent. Overshooting in the stiff coordinate is not a mistake, it is the reason steepest descent zig-zags; every exact line-search step ends where the new gradient is perpendicular to the old one.

Problem 10hard

Consider the coupled quadratic $f(x,y)=x^2+xy+y^2$ . (a) Find the minimiser analytically and confirm it is a minimum via the Hessian. (b) From $(x_0,y_0)=(2,0)$ with $\gamma=0.2$ , perform two gradient-descent iterations, reporting the gradient, the new point and $f$ each time. (c) Explain, with one computed number, why the coordinates can no longer be treated independently.

What this tests. Careful differentiation when a cross term is present — $\partial f/\partial x=2x+y$ , not $2x$ — and seeing what the off-diagonal Hessian entry does to a descent path. Plan. Solve the two linear gradient equations; read the Hessian's eigenvalues from the $a\pm b$ pattern; run the table with the full gradient at every row; then point at the one number that shows the coupling.

Show the full solution

(a) Step 1 — the analytic minimiser.

\nabla f=\big(2x+y,\ x+2y\big)=(0,0).

From the first equation

y=-2x

; from the second

x=-2y

. Substituting one into the other,

x=-2(-2x)=4x

, so

3x=0

,

x=0

, and then

y=0

. The only critical point is

(0,0)

, with

f(0,0)=0

. The Hessian is constant:

H=\begin{bmatrix}2&1\\1&2\end{bmatrix},\qquad\text{eigenvalues }2\pm1=3\ \text{and}\ 1,

both positive, so

H

is positive-definite and

(0,0)

is the global minimum. (For any matrix

\begin{bmatrix}a&b\\b&a\end{bmatrix}

the eigenvalues are

a\pm b

, with eigenvectors

(1,1)

and

(1,-1)

.)

(b) Step 2 — iteration 1. At

(2,0)

:

\begin{aligned} \nabla f(2,0)&=\big(2(2)+0,\ 2+2(0)\big)=(4,\ 2),\\ f(2,0)&=4+0+0=4,\\ (x_1,y_1)&=(2,0)-0.2\,(4,2)=(2-0.8,\ 0-0.4)=(1.2,\ -0.4),\\ f(1.2,-0.4)&=1.44+(1.2)(-0.4)+0.16\\ &=1.44-0.48+0.16=1.12. \end{aligned}

Step 3 — iteration 2. At

(1.2,-0.4)

:

\begin{aligned} \nabla f&=\big(2(1.2)-0.4,\ 1.2+2(-0.4)\big)\\ &=(2.4-0.4,\ 1.2-0.8)=(2.0,\ 0.4),\\ (x_2,y_2)&=(1.2,-0.4)-0.2\,(2.0,0.4)\\ &=(1.2-0.4,\ -0.4-0.08)=(0.8,\ -0.48),\\ f(0.8,-0.48)&=0.64+(0.8)(-0.48)+0.2304\\ &=0.64-0.384+0.2304=0.4864. \end{aligned}

So

f:4\to1.12\to0.4864

, heading for

(0,0)

.

$k$	point	gradient	new point	$f$
0	$(2,\,0)$	$(4,\,2)$	$(1.2,\,-0.4)$	$4$
1	$(1.2,\,-0.4)$	$(2.0,\,0.4)$	$(0.8,\,-0.48)$	$1.12$
2	$(0.8,\,-0.48)$	—	—	$0.4864$

(c) Step 4 — why no decoupling. At

(2,0)

the

y

-coordinate already sits at its "own" best value

0

, yet

\frac{\partial f}{\partial y}(2,0)=x+2y=2+0=2\neq0,

so the first step drags

y

to

-0.4

purely because

x

is large. The cross term

xy

makes each partial depend on both variables; updates of the form

x_{k+1}=(\text{constant})\,x_k

no longer exist. The coupling is the off-diagonal

1

in

H

. What does decouple is the eigenvector frame: along

(1,1)

the function is

f(t,t)=3t^2

(curvature

3

) and along

(1,-1)

it is

f(t,-t)=t^2

(curvature

1

); in those coordinates the two factors are

1-0.2\cdot3=0.4

and

1-0.2\cdot1=0.8

.

(a) Minimiser $(0,0)$ ; $H=\begin{bmatrix}2&1\\1&2\end{bmatrix}$ with eigenvalues $3,1$ — positive-definite. (b) $(1.2,-0.4)$ with $f=1.12$ , then $(0.8,-0.48)$ with $f=0.4864$ . (c) At $(2,0)$ , $\partial f/\partial y=2\neq0$ although $y=0$ .

Remember

A cross term is there to test whether you differentiate carefully: $\partial f/\partial x=2x+y$ . Everything else — the update rule, the table — is unchanged. The eigenvalue fact for $\begin{bmatrix}a&b\\b&a\end{bmatrix}$ , namely $a\pm b$ , is worth keeping; it is where the coordinates do come apart.

Problem 11hard

The line $\hat y=ax+b$ is fitted to the four points $x=(0,1,2,3)$ , $y=(1,3,5,7)$ by minimising $L(a,b)=\sum_{i=1}^4\big(y_i-(ax_i+b)\big)^2$ . (a) Find the exact minimiser $(a^*,b^*)$ from the normal equations and interpret $L^*$ . (b) From $(a_0,b_0)=(0,0)$ with $\gamma=0.05$ , perform two gradient-descent iterations; report the gradient, the parameters and $L$ after each. (c) The Hessian of $L$ is $H=2\begin{bmatrix}\sum x_i^2&\sum x_i\\\sum x_i&n\end{bmatrix}$ , with eigenvalues $\approx33.6$ and $\approx2.4$ . Compute the largest usable step size $\gamma_{\max}=2/\lambda_{\max}$ and use it to explain the path seen in (b).

What this tests. The whole story in one place: the normal equations give the destination, descent gives the journey, and the Hessian explains the driving style. Plan. Compute the four sums once and reuse them everywhere; keep residuals in a row so the gradient is two dot products; after each update recompute predictions, residuals, $L$ ; finally compare $\gamma$ with $2/\lambda_{\max}$ and read the sign of $1-\gamma\lambda_{\max}$ .

Show the full solution

(a) Step 1 — the four sums.

\begin{aligned} \sum x_i&=0+1+2+3=6, & \sum y_i&=1+3+5+7=16,\\ \sum x_i^2&=0+1+4+9=14, & \sum x_iy_i&=0+3+10+21=34, \end{aligned}

and

n=4

.

Step 2 — the normal equations.

\begin{aligned} a^*&=\frac{n\sum x_iy_i-\sum x_i\sum y_i}{n\sum x_i^2-\big(\sum x_i\big)^2}=\frac{4(34)-6(16)}{4(14)-36}=\frac{136-96}{56-36}=\frac{40}{20}=2,\\ b^*&=\frac{\sum y_i-a^*\sum x_i}{n}=\frac{16-2\cdot6}{4}=\frac{16-12}{4}=1. \end{aligned}

Check the fit:

y=2x+1

gives

1,3,5,7

— every point exactly. So

L^*=0

: the data are perfectly linear, and the minimum of the loss is a perfect fit.

(b) Step 3 — the gradient formulas. With residuals

r_i=y_i-(ax_i+b)

,

\frac{\partial L}{\partial a}=-2\sum x_ir_i,\qquad \frac{\partial L}{\partial b}=-2\sum r_i.

Step 4 — iteration 1. At

(0,0)

the predictions are all

0

, so

r=(1,3,5,7)

:

\begin{aligned} \sum x_ir_i&=0+3+10+21=34, & \sum r_i&=16,\\ \nabla L&=(-2\cdot34,\ -2\cdot16)=(-68,\ -32), & L_0&=1+9+25+49=84. \end{aligned}

Update:

(a_1,b_1)=(0,0)-0.05\,(-68,-32)=(3.4,\ 1.6).

New predictions

\hat y=3.4x+1.6

and residuals:

\begin{aligned} \hat y&=(1.6,\ 5.0,\ 8.4,\ 11.8),\\ r&=(1-1.6,\ 3-5.0,\ 5-8.4,\ 7-11.8)=(-0.6,\ -2.0,\ -3.4,\ -4.8),\\ L_1&=0.36+4+11.56+23.04=38.96. \end{aligned}

Step 5 — iteration 2. From those residuals:

\begin{aligned} \sum x_ir_i&=0-2.0-6.8-14.4=-23.2, & \sum r_i&=-10.8,\\ \nabla L&=(-2(-23.2),\ -2(-10.8))=(46.4,\ 21.6). \end{aligned}

Update:

\begin{aligned} (a_2,b_2)&=(3.4,1.6)-0.05\,(46.4,21.6)\\ &=(3.4-2.32,\ 1.6-1.08)=(1.08,\ 0.52). \end{aligned}

New predictions and residuals:

\begin{aligned} \hat y&=(0.52,\ 1.60,\ 2.68,\ 3.76),\\ r&=(0.48,\ 1.40,\ 2.32,\ 3.24),\\ L_2&=0.2304+1.96+5.3824+10.4976=18.0704\approx18.07. \end{aligned}

$k$	$(a_k,b_k)$	$\nabla L$	new $(a,b)$	$L$
0	$(0,\,0)$	$(-68,\,-32)$	$(3.4,\,1.6)$	$84$
1	$(3.4,\,1.6)$	$(46.4,\,21.6)$	$(1.08,\,0.52)$	$38.96$
2	$(1.08,\,0.52)$	—	—	$18.07$

The pattern:

a

jumped past its target

2

(to

3.4

), then back below it (to

1.08

), yet

L:84\to38.96\to18.07

keeps falling.

(c) Step 6 — the step-size speed limit. With the sums from Step 1,

H=2\begin{bmatrix}14&6\\6&4\end{bmatrix}=\begin{bmatrix}28&12\\12&8\end{bmatrix},\qquad \operatorname{tr}H=36,\quad \det H=224-144=80.

The eigenvalues solve

\lambda^2-36\lambda+80=0

:

\begin{aligned} \lambda&=\frac{36\pm\sqrt{1296-320}}{2}=\frac{36\pm\sqrt{976}}{2}=18\pm\sqrt{244}\\ &=18\pm15.62\ \Rightarrow\ \lambda_{\max}\approx33.62,\ \ \lambda_{\min}\approx2.38. \end{aligned}

The speed limit is

\gamma_{\max}=\frac{2}{\lambda_{\max}}\approx\frac{2}{33.62}\approx0.0595.

Our

\gamma=0.05

is just under it. Along the stiff eigen-direction the error is multiplied each step by

1-\gamma\lambda_{\max}\approx1-0.05\times33.62\approx-0.68:

magnitude below

1

, so the loss keeps shrinking, but negative, so the parameters flip from one side of the optimum to the other — exactly the overshoot-and-return seen in (b). A smaller

\gamma

, say

0.02

, gives

1-0.02\times33.62\approx+0.33

: a smooth, one-sided approach, but a slower one along the gentle direction (

1-0.02\times2.38\approx0.95

).

(a) $(a^*,b^*)=(2,1)$ , $L^*=0$ — a perfect fit. (b) $(3.4,1.6)$ , $L=38.96$ ; then $(1.08,0.52)$ , $L\approx18.07$ : oscillating but improving. (c) $\lambda\approx33.62,\ 2.38$ ; $\gamma_{\max}\approx0.0595$ ; $1-\gamma\lambda_{\max}\approx-0.68$ is negative, so the iterates alternate sides of the optimum.

Remember

The reusable diagnostic is the single number $1-\gamma\lambda$ : its size sets the speed, its sign says whether the approach is smooth ( $+$ ) or oscillating ( $-$ ), and $|1-\gamma\lambda_{\max}|<1$ is the same statement as $\gamma<2/\lambda_{\max}$ . The slip on this type is forgetting the factor $2$ in the Hessian (and so in $\gamma_{\max}$ ), or dropping the $-2$ from the gradient of a squared residual.

Problem 12hard

A line search must minimise the unimodal $h(\alpha)=\alpha^2-5\alpha+8$ over $[0,\alpha_{\max}]=[0,4]$ . (a) Trace three iterations of binary search: at each midpoint $m$ decide from the sign of the slope (compare $h(m)$ with $h(m+\epsilon)$ , $\epsilon=10^{-6}$ ) whether the minimum lies to the left or the right, and give the new interval. (b) What is the bracket width after $k$ iterations, and how many iterations guarantee a width $\le0.01$ ?

What this tests. The bracketing trace — a decision rule applied mechanically — and the halving count that follows. Plan. Fix the rule before starting: slope negative at $m$ means the minimum is to the right, keep $[m,b]$ ; slope positive means keep $[a,m]$ . Then three midpoints; then the width formula and one logarithm.

Show the full solution

(a) Step 1 — iteration 1. Interval

[0,4]

, midpoint

m=2

. The slope is

h'(\alpha)=2\alpha-5

, so

h'(2)=4-5=-1<0\qquad\big(\text{equivalently }h(2+\epsilon)<h(2)\big).

h

is still going down at

m

, so the minimum lies to the right: new interval

[2,4]

.

Step 2 — iteration 2. Midpoint

m=3

:

h'(3)=6-5=+1>0\qquad\big(h(3+\epsilon)>h(3)\big).

h

is going up at

m

, so the minimum lies to the left: new interval

[2,3]

.

Step 3 — iteration 3. Midpoint

m=2.5

:

h'(2.5)=5-5=0.

Numerically the probe still decides:

h(2.5+\epsilon)=h(2.5)+\epsilon^2>h(2.5)

(since

h(2.5+t)-h(2.5)=t^2

exactly), so the rule treats

m

as "going up" and keeps the left half: new interval

[2,2.5]

.

Step 4 — sanity check. The true minimiser is

\alpha^*=2.5

(where

h'=0

), and it sits inside every bracket:

[0,4]\supset[2,4]\supset[2,3]\supset[2,2.5].

✓ (Its value is

h(2.5)=6.25-12.5+8=1.75

; at the two earlier midpoints

h(2)=h(3)=2

.)

(b) Step 5 — the width count. Each iteration halves the bracket, so

\text{width after }k\text{ iterations}=\frac{4}{2^k}.

Require

4/2^k\le0.01

:

\begin{aligned} 2^k&\ge400\\ k&\ge\log_2400\approx8.64\\ k&=9\qquad\big(\text{width }4/512\approx0.0078\big). \end{aligned}

Eight iterations leave

4/256\approx0.0156

, still too wide; nine is the first that works.

(a) $[0,4]\to[2,4]\to[2,3]\to[2,2.5]$ . (b) width $=4/2^k$ ; $k=9$ iterations guarantee width $\le0.01$ ( $4/512\approx0.0078$ ).

Remember

Fix the decision rule before you start and the trace runs itself; the width formula $(b-a)/2^k$ plus one $\log_2$ finishes the count. If golden-section search is used instead, the bracket shrinks by $0.618$ per evaluation and the same target takes $13$ steps; and if $h$ is not unimodal, no bracketing method is safe — the inexact Armijo rule is the fallback.

Next up

Unit 10 · Optimization I — Gradients that Work — coming soon

You can now walk downhill, choose a stride, and afford the walk on big data. Unit 10 asks why the plain walk is so slow in a trench and fixes it: momentum that remembers the last step, strides that adapt per knob, and the difference between a landscape that is a bowl and one that only looks like it.

← All units