Unit 9 · Gradient Descent — The Math Behind the Machine

1

Downhill in the fog

Imagine this

You are trekking down a hill in Munnar at six in the morning. The mist is so thick that you can see only the patch of ground around your shoes. Somewhere below is the village, at the bottom of the valley. You have no map and no view.

But you can still feel one thing: which way the ground slopes under your feet. So you turn to face straight downhill. You take one step, stop, and feel again. Step by step, you reach the bottom.

That is the whole method of this unit. Try it below. The landscape is real, but you only see the lit patch.

Try: press ▶ walk and watch the lit patch slide downhill until the ground goes flat. Then press lift the fog: there were two valleys all along.

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

fog radius R0.9

step size γ0.25

—

The walker only ever uses the slope under its feet, $\nabla f$ . Drag it onto the hilltop to feel a flat spot that is not a bottom.

Three lessons hide in that walk. Everything else in this unit grows out of them.

1 · You never needed the map. The walker reached a valley without ever seeing it. It only used the slope under its own feet. This matters because a real model has millions of knobs. Its landscape lives in millions of dimensions, and nobody can draw it. But the slope at one point can always be computed.

2 · The slope is an arrow. Lift the fog and look at the orange arrow. It points the way the ground rises fastest, and its length says how steep it is. Mathematicians call this arrow the gradient and write it $\nabla f$ (read it: "grad f"). The green step points the exact opposite way.

A tiny example. You stand at $(1,1)$ , and the uphill arrow there is $\nabla f=(2,1)$ . You choose a stride $\gamma=0.5$ (read it: "gamma"; machine learning calls it the learning rate). Turn the arrow around, shrink it by the stride, and step:

$(1,1)-0.5\times(2,1)=(0,\ 0.5).$

3 · You find the valley below you, not the deepest one. After a walk, press lift the fog. There were two valleys all along. The walker went into the one its slope led to. Start somewhere else and it may end in the other. Gradient descent finds a low point, not always the lowest.

One note before we go on. Here you may put your feet anywhere. Real problems sometimes add fences, such as "this number must stay positive". That is called constrained optimization, and it gets its own unit later.

The realization

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

Read it: new position equals old position, minus the stride times the uphill arrow at the old position. Take the arrow, turn it around, shrink it to your stride, and step. This one line is the picture you just played with, written in symbols.

Pause & predict

Under your feet, the uphill arrow is $\nabla f=(3,\,-4)$ . Which way do you step, and how steep is the ground here?

In one sentence: learning is a walk in fog — feel the slope, step the other way, repeat — which works in any number of dimensions, but finds only the valley below where you started.

2

Why there is a landscape at all

Imagine this

A stationery shop near your college sells printer paper by the box. Here are four old bills, in hundreds of rupees: 1 box cost 3.1, 2 boxes cost 4.9, 3 boxes cost 7.3, and 4 boxes cost 9.1.

The owner wants a quick rule to quote any order: price ≈ a × boxes + b. Here $a$ is the price per box and $b$ is a fixed charge. Every pair $(a,b)$ is a guess. Some guesses are terrible. One is best.

So ask one question: how wrong is each guess, as a single number? The answer builds a landscape.

Draw a guess as a straight line through the four bills. Each bill sits a little above or below the line. That gap is a miss. Its formal name is a residual, written $r_i$ .

Square each miss, so that misses above and below both count, and big misses count a lot. Then add them up. That total is the guess's wrongness. Its formal name is the loss, written $L(a,b)$ .

Two guesses, worked out:

Guess $(a,b)$	Line predicts	Misses	Wrongness $L$
(0, 0)	0, 0, 0, 0	3.1, 4.9, 7.3, 9.1	$169.72$
(2, 1)	3, 5, 7, 9	0.1, −0.1, 0.3, 0.1	$0.12$

Now the key step. Treat $L$ as a height above the point $(a,b)$ . Every guess gets a height. Put them all together, and you have a landscape. Turn the knobs below and watch the line move and the ball rise or fall.

Try: press ▶ descend and watch the ball zig-zag down the narrow trench, then crawl along it. Now 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

—

One direction of this trench is about $56$ times stiffer than the other (stiffness $66.8$ against $1.2$ ). The stride must stay under $2/66.8\approx0.030$ , and at that stride the flat direction barely moves.

So the landscape is not just a nice picture. It appears by itself the moment you say what "wrong" means. Training any model means walking down such a landscape. This one has two knobs, so you can see it. A neural network has millions, which is why the fog of Section 1 matters.

The slope has a plain meaning. Start at $a=b=0$ . The line lies flat on the floor, below all four bills. Which way is downhill? "Lift the line up toward the bills." That is exactly what the first step does: both $a$ and $b$ go up. In symbols, with misses $r_i=y_i-(ax_i+b)$ :

$L=\sum_i r_i^2,\qquad \nabla L=\Big(-2\sum_i x_i r_i,\ \ -2\sum_i r_i\Big).$

Read it aloud. The fixed charge $b$ feels the plain total of the misses. The price per box $a$ feels each miss weighted by its number of boxes.

The bowl is a long trench, not a round dish. Orbit the picture. Change $a$ a little and the wrongness shoots up, because the 4-box bill moves a lot. Change $b$ a little and almost nothing happens. The steep direction is about $56$ times stiffer than the flat one. Remember this trench. It makes the walk zig-zag in Section 4, and it makes choosing a step hard in Section 5.

This small problem also has a direct formula. The best line is $a^*=2.04,\ b^*=1$ , with wrongness $0.072$ . Bigger models have no such formula. Walking downhill is the only way, so we practise it here, where we can check the answer.

The realization

Wrongness is the sum of squared misses, $L=\sum_i\big(y_i-(ax_i+b)\big)^2$ . Its slope, $\nabla L=\big(-2\sum x_ir_i,\,-2\sum r_i\big)$ , just says "move the line toward the points". If the misses are mostly positive, push the line up.

Pause & predict

Start at $a=b=0$ . The line lies flat on the floor, and all four bills sit above it. What does the first downhill step do to the price per box $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 — one height for every setting of the knobs — with a slope that says which way the line should move.

3

Where the walk ends — flat ground comes in three kinds

Imagine this

Drop a small lemon into an empty kadhai. It rolls down and stops at the bottom, where the metal is level.

Now turn the kadhai upside down and balance the lemon on top. The metal is level there too. But one tiny push and the lemon rolls off.

Last, picture a Pringles chip. Along one edge it curves up; along the other it curves down. The very middle is level, yet a lemon placed there would slide off sideways. This shape is called a saddle.

So "level ground" comes in three kinds. The walker stops on any of them.

Level ground means the slope is zero. For a curve $f(x)$ , the slope is the derivative $f'(x)$ (read it: "f prime of x"). So the walk can only stop where $f'(x)=0$ . These are the flat spots. Their formal name is stationary points.

How do you tell the three kinds apart without seeing them? Feel how the ground bends. Inside a kadhai it bends up on both sides. On an upside-down kadhai it bends down. The bend is measured by the second derivative $f''(x)$ (read it: "f double prime").

Flat spot	In everyday words	The test
Valley (minimum)	lemon inside a kadhai: it stays	$f'=0$ and $f''>0$
Hilltop (maximum)	lemon on an upside-down kadhai: it rolls off	$f'=0$ and $f''<0$
Saddle	lemon on a Pringles chip: slides off sideways	in 2-D: bends up one way, down the other

A tiny example: $f(x)=x^2-4x$ . The slope is $f'(x)=2x-4$ , which is zero at $x=2$ . The bend is $f''(x)=2$ , which is positive. So $x=2$ is a valley, at height $f(2)=-4$ .

Below, a probe sits on a curve. Its tangent line shows the slope. Press ▶ to let it walk downhill.

Try: put the probe at $x=-1.3$ and press ▶: it slides into the valley at $x\approx0.66$ . Now start at $x=-1.6$ , just left of the hilltop: 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, its size says how far. The walk stops on any flat spot, and it cannot tell a shallow valley from the deepest one.

Look at the quartic curve. It has three flat spots: a deep valley on the left, a hilltop in the middle, and a shallow valley on the right.

Start anywhere to the right of the hilltop, and the probe rolls into the shallow valley. The deep valley is $43$ units lower, just behind the hill. But the walker cannot get there. Each step goes downhill, and reaching the deep valley would mean climbing first. This is Section 1's warning again, now with numbers.

In two or more dimensions, the bend becomes a small table of second derivatives: the Hessian from Unit 8. It gives the same three verdicts: bowl, dome or saddle.

The realization

The walk stops where the slope is zero, $f'(x)=0$ . The bend decides what kind of stop it is: $f''>0$ is a valley, $f''<0$ is a hilltop. And the valley you reach is the one below your start, not always the deepest.

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 level ground; the bend tells a valley from a hilltop or a saddle; and you land in the valley below where you started.

4

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

Imagine this

Think of the concrete drain along a city road: a long, U-shaped channel. Its sides are steep. Along its length it is almost flat.

Drop a marble onto one side wall. It does not roll along the drain toward the far end. It rolls across, up the other wall, and back again — side to side — and only slowly drifts along.

That side-to-side dance is the most famous problem with gradient descent. This section shows where it comes from.

First, the rule in symbols. You have already used it many times:

$\mathbf x_{\text{new}}=\mathbf x-\gamma\,\nabla f(\mathbf x).$

Now take the simplest landscape of all: a bowl. Its slope works like a spring. The further you are from the bottom, the harder it pulls you back.

A tiny example. On the round bowl $f=x^2+y^2$ the slope is $\nabla f=(2x,\,2y)$ . From $(3,4)$ , with stride $\gamma=0.25$ :

$(3,4)-0.25\times(6,8)=(1.5,\ 2).$

The distance to the bottom halved in one step, in both directions at once. A round bowl is easy.

A trench is a bowl with two different springs: a stiff one across it and a soft one along it. For a general bowl $f(\mathbf x)=\tfrac12\mathbf x^{\top}A\mathbf x+\mathbf b^{\top}\mathbf x$ , the slope is

$\nabla f(\mathbf x)=A\mathbf x+\mathbf b.$

The matrix $A$ holds the springs. Its eigenvalues are the stiffness along each of the trench's own directions. The bottom is where the springs balance: $A\mathbf x+\mathbf b=\mathbf 0$ , so $\mathbf x^*=-A^{-1}\mathbf b$ .

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

drag the picture to orbit

step size γ0.05

steps20

—

Orange is the uphill arrow $\nabla f=A\mathbf x+\mathbf b$ ; green is the step. Each direction shrinks by its own factor $1-\gamma\lambda$ , so the stiff one limits the stride and the soft one crawls.

On the lecture's valley the stiffnesses are about $20$ across and $2$ along. One stride has to serve both springs, and it cannot serve both well. Set $\gamma=0.09$ and press ▶. Across the trench, each step multiplies the distance by about $-0.81$ : it flips to the other wall. Along the trench it multiplies by about $0.82$ : a slow crawl.

The ratio of the two stiffnesses, about $10$ here, says how bad the zig-zag gets. On the paper-bill trench of Section 2 it is about $56$ . Keep this picture. Section 5 puts numbers on it, and Unit 10 is about fixing it.

Two facts make the rule trustworthy. (The proofs are in the drawer below.)

①Stepping against the gradient is the steepest way down. Turn slowly in a full circle: the ground drops fastest when you face exactly away from the uphill arrow.
②A short enough step that way always goes down. Close to your feet, the ground is almost a flat ramp. "Short enough" is the topic of Section 5.

The realization

The rule is $\mathbf x_{\text{new}}=\mathbf x-\gamma\nabla f(\mathbf x)$ . On a bowl the slope is a spring, $\nabla f=A\mathbf x+\mathbf b$ , and the bottom is $\mathbf x^*=-A^{-1}\mathbf b$ . A trench has one stiff spring and one soft one, so a single stride bounces across it while crawling along it.

Pause & predict

On the lecture's valley, $A=\begin{bmatrix}2&1\\ 1&20\end{bmatrix}$ and $\mathbf b=(-5,-3)$ . The walker starts at $\mathbf x_0=(-3,-1)$ , where the slope is $\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 slope is a spring, $\nabla f=A\mathbf x+\mathbf b$ ; a trench has a stiff spring and a soft one, so one stride bounces across it while it crawls along it.

5

How long a step — the bouncing ball

Imagine this

You are setting the water in a shower with a mixer tap. It is too cold, so you turn the knob.

🐢Turn it a tiny bit each time: safe, but it takes ages to warm up.
🎯Turn it just right: perfect in one go.
↔Turn it too far: now it is too hot. Turn back too far: too cold. You swing back and forth, but get closer each time.
💥Turn it much too far each time: the swings get worse — hotter, colder, hotter.

The size of your turn is the step size $\gamma$ . Gradient descent has exactly these four moods.

Take the simplest bowl, one number wide: $f(x)=\tfrac12\lambda x^2$ . Here $\lambda$ (read it: "lambda") is the stiffness — how sharply the bowl curves. The slope is $\lambda x$ , so one step gives

$x_{\text{new}}=x-\gamma\lambda x=(1-\gamma\lambda)\,x.$

So each step multiplies your distance from the bottom by the same number, $1-\gamma\lambda$ . Call it the factor. That one number tells the whole story.

Try it with $\lambda=2$ , starting at $x_0=1.8$ :

Stride $\gamma$	Factor $1-\gamma\lambda$	First steps	What happens
0.3	0.4	1.8 → 0.72 → 0.288	smooth, same side
0.5	0	1.8 → 0	one perfect step
0.8	−0.6	1.8 → −1.08 → 0.648	flips sides, but shrinks
1.0	−1	1.8 → −1.8 → 1.8	bounces for ever
1.2	−1.4	1.8 → −2.52 → 3.528	grows: blows up

Now turn the dial below and watch the ball hop.

Try: press sweet, then ▶: with $\gamma\lambda=1$ one hop lands exactly at the bottom. Then press edge: $\gamma\lambda=2$ hops between the two walls for ever, and blow up flies out of the bowl.

drag the picture to orbit

curvature λ2

step size γ0.3

—

Each hop multiplies the distance to the bottom by $1-\gamma\lambda$ . It must stay between $-1$ and $1$ , so $\gamma<2/\lambda$ ; in two dimensions the stiffest direction sets that limit.

The rule hiding in that table: the factor must stay between $-1$ and $1$ . That means $\gamma\lambda$ must stay below $2$ . This is the speed limit:

$\gamma<\frac{2}{\lambda}.$

A stiffer bowl (bigger $\lambda$ ) needs a smaller stride, just as a touchy tap needs gentler turns.

Now switch to the two-dimensional tab. A trench has two stiffnesses, so every step has two factors: one across and one along. The stride must obey the stiff spring's speed limit. At that stride, the soft spring's factor is close to $1$ , so that direction crawls.

Press zig-zag. With stiffnesses $20$ and $2$ and $\gamma=0.095$ , the factors are $1-0.095\times20=-0.90$ across and $1-0.095\times2=0.81$ along. Bounce across, crawl along: that pair of numbers is the zig-zag. The ratio of the stiffest to the softest is called the condition number.

In practice, nobody knows the stiffnesses. There are two ways out. Watch the height, and shrink the stride when it goes up (Section 8). Or let the ground choose the stride for you (Section 6).

The realization

Each step multiplies the distance to the bottom by $1-\gamma\lambda$ . Keep that between $-1$ and $1$ , which means $\gamma<2/\lambda$ . With many directions, the stiffest one ( $\lambda_{\max}$ ) sets the limit for all, and the softest one sets how slowly you crawl.

Pause & predict

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

Pause & predict

The paper-bill trench of Section 2 has stiffnesses of 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$ , so keep $\gamma<2/\lambda_{\max}$ — and the gap between the stiffest and softest directions is what makes the walk zig-zag.

6

Let the ground choose the stride — line search

Imagine this

You are walking along a straight road that dips under a railway bridge. The road goes down, reaches its lowest point under the bridge, and climbs back up.

You want to stop at the lowest point. You don't need to know in advance where it is. Just keep walking while the road goes down. The moment it starts to rise, stop.

That is the whole idea of this section: pick a direction, then walk along it until the ground stops going down.

Gradient descent picks the direction for you: straight against the slope. Along that straight line, the whole landscape becomes just a dip in a road — height against distance.

Call the distance along the line $\gamma$ . The height after sliding that far is

$h(\gamma)=f(\mathbf x-\gamma\,\mathbf g),\qquad \text{where } \mathbf g=\nabla f(\mathbf x).$

(Read $h(\gamma)$ as "the height after sliding a distance gamma".) The best stride, $\gamma^*$ (read it: "gamma star"), is simply the bottom of this dip. The method is called line search.

A worked example on $f=x^2+3y^2$ , starting at $(2,2)$ . The slope there is $\mathbf g=(4,12)$ , so the line is $(2-4\gamma,\ 2-12\gamma)$ . The bottom of the dip is at $\gamma^*=5/28\approx0.179$ . You land at $(9/7,\,-1/7)\approx(1.29,\,-0.14)$ , and the height falls from $16$ to $12/7\approx1.71$ . One slide removes $89\%$ of the height.

Try: drag $\gamma$ and watch the glowing height ring at the bead shrink. Press snap to γ*: the ring just touches the line, and the orange slope arrow stands at a right angle to it. Then take the step and repeat.

drag the picture to orbit

bead at γ0.09

—

Along the line the bowl is a simple dip, $h(\gamma)=f(\mathbf x_k-\gamma\mathbf g)$ , drawn small beside the picture. Its bottom is $\gamma^*=\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g$ , where the new slope is perpendicular to the old one.

Watch the orange arrow at the bead as you slide. At first it leans back along the line: you are still going down. Slide too far and it leans forward: you have passed the bottom. At the best point it stands at a right angle to the line.

At that same point, the line just touches a contour ring without crossing it. (A contour is a ring of equal height, like a water line inside a bowl.) This is the same fact seen twice. If the line crossed the ring, it would reach lower ground inside it.

Press take the step a few times. Every corner of the path is a right angle, because each new slope is perpendicular to the last direction. On a long trench this is still a zig-zag, just a neater one. A better stride cannot fix a poor direction; Unit 10 does that.

For a bowl, there is a formula for the best stride:

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

Check it on our example. Here $A=\begin{bmatrix}2&0\\ 0&6\end{bmatrix}$ , so $\mathbf g^{\top}\mathbf g=16+144=160$ and $\mathbf g^{\top}A\mathbf g=2\cdot16+6\cdot144=896$ . And $160/896=5/28$ , as before.

In real training, each height check means a pass over the data, so an exact slide costs too much. Plain gradient descent settles for "far enough that the height clearly dropped". That is the Armijo rule of Section 7.

The realization

Line search fixes the direction $-\mathbf g$ , then slides to the bottom of $h(\gamma)=f(\mathbf x-\gamma\mathbf g)$ . At the best stride, the new slope is at a right angle to the step. On a bowl, that stride is $\gamma^*=\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g$ .

Pause & predict

From $(2,2)$ on $f=x^2+3y^2$ , the exact slide lands at $(9/7,\,-1/7)$ . The slope there is $(18/7,\,-6/7)$ . Take its dot product with the old slope $(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 downhill line until the ground stops dropping — there the new slope is at a right angle to your step — and on a bowl the best stride is $\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g$ .

7

Finding the bottom of one line — higher or lower?

Imagine this

A friend thinks of a number from 1 to 100. You may only ask "higher or lower?". The smart move is to ask about the middle every time. Each answer throws away half of what is left. After 7 questions you know the number, because $2^7=128$ is more than 100.

Finding the bottom of a dip works the same way. At the middle, ask one question: "is the ground still going down here?" If yes, the bottom is to the right. If no, it is to the left.

Section 6 left one job open. On a real loss there is no formula for the best stride. You can only measure the height at any distance you choose. So how do you find the bottom of the dip?

If the dip has just one low point — down, bottom, up, nothing else — you can trap the bottom inside an interval and squeeze. That interval is called a bracket. The widget shows three ways to choose a step:

①Binary search. Check the slope at the middle and keep the half that goes down. The bracket halves every round.
②Golden section. Put two probes inside, at $38\%$ and $62\%$ of the bracket, and keep the side with the lower probe. One old probe is already in the right place for the next round, so each round costs only one new height. The bracket shrinks to $0.618$ of its width per round.
③Armijo backtracking. Don't hunt for the bottom at all. Try a bold stride. If the height dropped "enough", take it. If not, halve the stride and try again.

A worked example: $h(\alpha)=\alpha^2-5\alpha+8$ on $[0,4]$ , whose bottom is at $\alpha=2.5$ . At the middle, $2$ , the ground still goes down, so keep $[2,4]$ . At the next middle, $3$ , it goes up, so keep $[2,3]$ . Then $[2,2.5]$ . Three questions, and the width went $4\to2\to1\to0.5$ .

Try: press one iteration three times on the practice function and read the brackets: $[0,4]\to[2,4]\to[2,3]\to[2,2.5]$ . Then switch to bumpy: the bracket can close in on the wrong dip.

—

Binary halves the bracket using two heights per round; golden section shrinks it to $0.618$ using one new height. Armijo only asks: is $h(\alpha)\le h(0)+c\,\alpha\,h'(0)$ ? If not, it halves $\alpha$ .

After $k$ rounds of binary search the width is $(b-a)/2^k$ . To squeeze $[0,4]$ below $0.01$ takes $9$ rounds, since $4/2^9\approx0.008$ . Golden section needs $13$ rounds. But each of its rounds costs one height instead of two, so it uses fewer measurements overall: $15$ against $18$ .

Armijo is the humble one. Its test for "dropped enough" is

$h(\alpha)\le h(0)+c\,\alpha\,h'(0),$

with a small number $c$ (the widget uses $c=0.1$ ). In words: the drop must be at least a small share of what the slope promised. On our example, try $\alpha=4$ . The height is $h(4)=4$ , and the test allows at most $8+0.1\times4\times(-5)=6$ . Since $4\le6$ , accept.

Armijo doesn't need a single dip, and it costs only a few height checks. That is why ordinary gradient descent uses it. On the bumpy function, the bracket methods can trap the wrong dip. That is the price of assuming there is only one.

The realization

Trap the bottom in a bracket and squeeze. Halving leaves width $(b-a)/2^k$ after $k$ rounds; golden cuts shrink it by $0.618$ per round and reuse a probe. Or skip the hunt: Armijo accepts any stride with $h(\alpha)\le h(0)+c\,\alpha\,h'(0)$ .

Pause & predict

Binary search on $[0,4]$ . At the middle, $2$ , the height just 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: when there is no formula for the best stride, trap it in a bracket and squeeze — or, like real training, take Armijo's "good enough" stride.

8

Bold early, careful late — schedules and the bold driver

Imagine this

You are pouring chai from a kettle into a small cup. At first you pour fast: the cup is empty, and there is a long way to go. As the tea nears the brim, you slow right down. Pour fast till the end and it spills over.

The learning rate is your pouring speed. Section 5's bouncing ball poured at one fixed speed: fine at first, spilling near the end. The cure is simple: start fast, finish slow.

A rule for lowering the learning rate over time is called a schedule. We write the rate at time $t$ as $\alpha_t$ (read it: "alpha at time t"). Here $t$ counts epochs, which are full passes over the data. So the rate stays fixed during one pass.

Three common schedules, all starting at $\alpha_0=0.8$ with $k=0.05$ , read at epoch $t=10$ :

Schedule	Formula	In everyday words	At epoch 10
Exponential	$\alpha_0e^{-kt}$	lose the same share every epoch	0.485
Inverse	$\alpha_0/(1+kt)$	lose less and less; a long, slow tail	0.533
Step	$\alpha_0/3^{\lfloor t/5\rfloor}$	stay flat, then divide by 3 every 5 epochs	0.089

( $\lfloor t/5\rfloor$ means " $t/5$ rounded down", so it counts the drops so far.) A fourth way ignores the clock and watches the loss itself. It is called the bold driver.

Try: with $k=0.05$ , read the three rates at $t=10$ : $0.485$ , $0.533$ , $0.089$ . Then open bold driver and press ▶: the rate grows $5\%$ a step until it overshoots, then halves.

start α₀0.8

decay k0.05

epochs shown30

read at t10

—

Exponential falls by the same share each epoch, inverse falls more and more slowly, and step drops in cliffs. The bold driver ignores the clock: good step, ×1.05; bad step, undo and ×0.5.

Which schedule is best depends on the road ahead. A rate that drops too fast leaves the walker stuck above the bottom. One that drops too slowly keeps it bouncing. Section 11 shows that with noisy slopes, slowing down is the only way the walk ever settles.

The bold driver drives like you do on a new road. While the road is smooth, you speed up a little. Hit a speed-breaker hard, and you brake. In numbers, after each step it looks at the height:

✓Lower than before? Keep the step and raise the rate by $5\%$ (multiply by $1.05$ ).
✗Higher? Undo the step, go back, and halve the rate (multiply by $0.5$ ).

Only downhill steps are kept, so the height never rises. In the widget, the rate creeps up until it hits the speed limit of Section 5, $2/\lambda_{\text{stiff}}=0.1$ . It gets knocked back, then creeps up again. It finds the speed limit by bumping into it.

One warning, for Section 10. If the height you see is only an estimate from a small sample, it can go up by chance. Then the driver brakes for nothing. The fix is to judge over several steps, not after every one.

The realization

Start bold, finish careful. On a clock: $\alpha_0e^{-kt}$ , $\alpha_0/(1+kt)$ , or divide by a constant every few epochs. By feel: the bold driver multiplies the rate by $1.05$ after a good step, and undoes and halves after a bad one.

Pause & predict

Training starts at $\alpha_0=0.8$ . Step decay 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: the learning rate is a speed that should drop as you near the bottom — on a timer (exponential, inverse, step) or by feel (the bold driver).

9

Is my compass even right? — the known weight

Imagine this

Before a weights-and-measures inspector trusts a vegetable seller's scale, she puts a known 1 kg 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 — written by hand, or by backprop from Unit 7 — is like that scale. It steers the whole walk. If it is off by a sign or a factor of 2, the walk goes confidently to the wrong place. So we test it with a "known weight".

The known weight is the meaning of slope itself: nudge one knob a tiny bit, see how much the height changes, and divide. That gives a measured slope, and it should match the code's slope. This test is called a gradient check. The nudges are called finite differences.

There are two ways to nudge, with a small nudge $\Delta$ (read it: "delta"):

Name	How you nudge	Formula
Forward	one way only	$\dfrac{J(w+\Delta)-J(w)}{\Delta}$
Central	a little each way	$\dfrac{J(w+\Delta)-J(w-\Delta)}{2\Delta}$

A worked example: $J(w_1,w_2)=w_1^3+w_1w_2^2$ at $(2,1)$ . The true slope in $w_1$ is $3w_1^2+w_2^2=13$ . The heights we need are $J(2,1)=10$ , $J(2.1,1)=11.361$ and $J(1.9,1)=8.759$ . With $\Delta=0.1$ :

→Forward: $(11.361-10)/0.1=13.61$ . Off by $0.61$ .
↔Central: $(11.361-8.759)/0.2=13.01$ . Off by only $0.01$ .

Try: at $\Delta=0.1$ , read the two estimates of $\partial J/\partial w_1$ : forward $13.61$ , central $13.01$ , truth $13$ . Slide $\Delta$ smaller: the central error falls twice as steeply — until, below $10^{-6}$ , both curves turn back up.

log₁₀ Δ0.1

—

Here $J=w_1^3+w_1w_2^2$ at $(2,1)$ . The forward error shrinks like $\Delta$ , the central one like $\Delta^2$ — until rounding noise, divided by a tiny $\Delta$ , takes over.

The chart has three zones. On the right, with a big $\Delta$ , both guesses are poor. In the middle, shrink $\Delta$ tenfold and the forward error drops tenfold, but the central error drops a hundredfold. Nudging both ways cancels the bend of the curve, which a one-sided nudge leaves behind.

On the left, with a tiny $\Delta$ , both errors climb back up. A computer keeps only about 16 digits. When $\Delta$ is tiny, the two heights agree in almost all of them. What is left is rounding noise, divided by a tiny number. So the best $\Delta$ is small, but not too small: around $10^{-5}$ for the central nudge.

A gradient check tests a few knobs by hand. It is never how you compute gradients for real. It would be far too slow for millions of knobs.

The realization

To audit a slope, nudge and divide. Forward, $\dfrac{J(w+\Delta)-J(w)}{\Delta}$ , is off by about $\tfrac12J''\Delta$ . Central, $\dfrac{J(w+\Delta)-J(w-\Delta)}{2\Delta}$ , is off by about $\tfrac16J'''\Delta^2$ . So use central, with a small but not tiny $\Delta$ .

Pause & predict

With $\Delta=0.1$ , the central estimate of a slope 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: check a coded slope by nudging a few knobs; the two-way nudge is far more accurate, until the nudge is so tiny that rounding takes over.

10

Three ways to walk — batch, minibatch, stochastic

Imagine this

Your mother is cooking a big pot of sambar and wants to check the salt. She does not drink the whole pot. She stirs, tastes one spoonful, and adds a pinch. Stir, taste again, adjust again.

Each spoonful is a little different from the whole pot. But on average it tells the truth, and it is quick. Many fast tastes beat one perfect but impossible measurement.

A real loss is the pot. It is a sum over every example in the data, so the exact slope needs a pass over all of it — for every single step. The spoonful is the idea of this section.

Three walkers differ in just one thing: how much data they read before each step.

🍲Batch reads everything. Its slope is exact, but each step is expensive.
🥄Minibatch reads a random handful — a spoonful — and steps on the slope of that handful.
💧Stochastic (which means "random") reads one single example and steps on that.

In symbols: the loss is a sum over examples, $L=\sum_n L_n$ , so its slope is a sum too, $\nabla L=\sum_n\nabla L_n$ . A minibatch $S$ is a random set of $|S|$ examples (read $|S|$ as "the size of S"). It uses only its own part of that sum.

A quick count. You have $1{,}000$ examples, and one batch step reads all of them. For the same reading, minibatches of $10$ give you $100$ steps. The stochastic walker gets $1{,}000$ steps.

Below, all three walk the same bowl, from the same start, with the same stride. Race them. Then change what "fair" means.

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

drag the picture to orbit

minibatch |S|8

step size γ0.04

—

A minibatch step costs $|S|$ reads instead of $N$ , points the right way on average, and has noise shrinking like $1/\sqrt{|S|}$ . Per data read — the budget that matters for big data — the noisy walkers win.

The race has two verdicts, and both are true. Judged per step, batch looks best: smooth and straight. The other two wobble.

Judged per data read, it flips. By the time batch has read its first $40$ points and taken one step, the stochastic walker has taken $40$ steps and is most of the way down. This is why large models are trained on minibatches.

Why can a spoonful steer at all? Because it is right on average. Each example's slope points a little differently, and the true slope is their average. So a random handful's slope scatters around the true one, not off to one side. Over many steps, the scatter cancels out.

A bigger spoon means less scatter. The noise shrinks like $1/\sqrt{|S|}$ : four times the batch gives half the noise. In practice, the batch size is often set by what fits in the computer's memory.

	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$
slope used	exact	right on average; noise $\propto1/\sqrt{\|S\|}$	right on average; noisiest
the path	smooth, but slow per data read	a little wobbly, fast	jittery, fastest early
at the bottom	arrives exactly	hovers in a small cloud, unless the stride shrinks	hovers in a bigger cloud, unless the stride shrinks
use it when	the data is small	almost always — deep learning's default	data arrives one example at a time

The realization

The loss is a sum over examples, so its slope is too. A random handful gives $\nabla J(S)=\sum_{i\in S}\nabla L_i$ ; scaled by $N/|S|$ , it is right on average, and its noise shrinks like $1/\sqrt{|S|}$ . Step on it: $\mathbf w\leftarrow\mathbf w-\alpha\,\nabla J(S)$ . That is minibatch gradient descent; $|S|=1$ is stochastic, and $|S|=N$ is batch.

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, you 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 per step; a random spoonful is right on average, so per data read the noisy walkers win — which is why deep learning uses minibatches.

11

Noise, tamed — and noise as a friend

Imagine this

Try threading a needle on a moving train. Your hands shake a little with every jolt.

Far from the needle, you move boldly; the shaking hardly matters. Close to the needle's eye, big movements plus shaking make you miss again and again. So you make your last movements tiny. Now the shake is a small part of a small movement, and the thread goes in.

A noisy slope is a shaking hand. The step size is the size of your movement.

Near the bottom, the true slope is almost zero. But a spoonful's slope is not. It keeps saying "a bit this way", "a bit that way". So with a fixed stride, the walker never settles. It jitters in a small cloud around the bottom.

The size of that cloud grows with the stride: halve $\gamma$ , and you roughly halve the cloud. Below, one noisy walker is shown up close. At each step you can see the true slope and the spoonful's slope side by side.

Try: set the batch size to 1 and press ▶: the walk jitters around the bottom and never settles. Switch to decaying γ: the same noisy steps shrink over time and calm down onto the bottom.

batch size4

step size γ0.1

steps80

—

A batch of 4 costs 4 points per step instead of 40, and is right on average. Its variance shrinks like $1/|S|$ : bigger batches give calmer but dearer steps.

So the slowing down of Section 8 is not optional here. It is the only way the walk ends. Shrink the stride over time: fast enough to close the cloud, but slowly enough that the walker still reaches the bottom. The decay tab shows exactly this.

Mathematicians write the rule for a good schedule in two parts:

$\sum_t\gamma_t=\infty\qquad\text{and}\qquad\sum_t\gamma_t^2<\infty.$

In words: the strides must add up to an unlimited distance, so you can travel as far as you need. But their squares must add up to a finite total, so the shaking dies out. The schedule $\gamma_0/(1+kt)$ passes both tests. With such a schedule, the noisy walk settles into a valley bottom (a local minimum) with probability one.

Now a surprise. Remember the two valleys of Section 1 and the shallow valley of Section 3. An exact walker in a shallow dip is stuck for ever, because every exact step goes down. A noisy walker is not. Its shaky steps sometimes go up by chance. On a bumpy landscape, a few lucky upward steps can carry it over the rim into a deeper valley.

So the noise that made the walk messy can also help it find a better answer.

The realization

With a noisy slope and a fixed stride, the walker ends in a cloud around the bottom whose size grows with the stride: its variance is about $\gamma\sigma^2/2\lambda$ , where $\sigma$ is the size of the noise. A shrinking stride with $\sum\gamma_t=\infty$ and $\sum\gamma_t^2<\infty$ closes the cloud. The same shake can lift a walker out of a shallow dip.

Pause & predict

You run the one-example walker with a fixed stride. The loss falls fast, then stops improving and wobbles a little 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 slopes; the other uses one-example slopes. 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 slope is a shaking hand — a fixed stride leaves a jitter cloud, a shrinking stride closes it, and the same shake can hop a walker out of a shallow dip.

12

What to carry forward

The whole unit is one habit: feel the slope, step the other way. Each section asked one question about that step. Here they are side by side.

The picture	What it says	The maths it becomes
The misty trek	you only need the slope under your feet — and you reach the valley below your start	$\mathbf x\leftarrow\mathbf x-\gamma\nabla f$
The paper bills	say what "wrong" means and a landscape appears; its slope says which way the line should move	$\nabla L=(-2\sum x_ir_i,\,-2\sum r_i)$
The lemon and the kadhai	level ground is a valley, a hilltop or a saddle — the bend decides	$f'=0$ ; sign of $f''$ (the Hessian in 2-D)
The road-side drain	a bowl's slope is a spring; a trench has a stiff one and a soft one	$\nabla f=A\mathbf x+\mathbf b$ ; eigenvalues = stiffnesses
The shower tap	each step multiplies the distance by a factor; the stiffest direction sets the speed limit	$1-\gamma\lambda$ ; $\gamma<2/\lambda_{\max}$
The road under the bridge	slide until the ground stops dropping; the next slope is at a right angle	$\gamma^*=\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g$
Higher or lower?	trap the bottom and squeeze — or accept "good enough"	$(b-a)/2^k$ ; $0.618$ ; Armijo
Pouring chai	fast far away, slow near the brim	$\alpha_0e^{-kt}$ , $\alpha_0/(1+kt)$ , step; bold driver
The 1 kg weight	test the slope by nudging; nudging both ways is far better	error $\propto\Delta$ vs $\propto\Delta^2$
A spoonful of sambar	a random handful's slope is right on average; per data read, noisy wins	$\mathbb E[\nabla J(S)]\propto\nabla L$ ; noise $\propto1/\sqrt{\|S\|}$
Threading a needle on a train	a fixed stride leaves a cloud; a shrinking stride closes it; the shake can hop a rim	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 slope is the only map you get in the fog. A stride under $2/\lambda_{\max}$ always goes down. A trench makes that stride small and the path a zig-zag. And when the data is too big to read, a random spoonful points the right way on average. The next units — momentum, Newton's method, constraints — are cleverer ways to walk the same fog.

In one sentence: gradient descent is one reflex — step against the slope — and this whole unit is about how big, how exact and how cheap that step should be.

13

Practice arena — twelve problems, solved in full

Twelve problems, from easy to hard. They cover the whole walk: sorting flat spots, tracing steps by hand, schedules, line search, gradient checks, a bowl with a cross term, fitting a line by descent, and a bracket trace. Every number has been checked by computer.

Two habits do most of the work. Trace steps in a table — point, slope, new point, height — so nothing gets lost. And for any stride question, find the stiffest direction first: $2/\lambda_{\max}$ is the limit, and $1-\gamma\lambda$ tells you the rest.

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 →

You can now walk downhill, choose a stride, and afford the walk on big data. Unit 10 is about the four ways that walk quietly goes wrong — a bad start, memorising instead of learning, the wrong valley or a salt flat, and a canyon that makes every step bounce — and the cheapest fix in machine learning: change the units of the data, not the model, so the canyon becomes a bowl.

← All units