ml.lab
Python sleeps until you run code
05 Derivatives, gradients and Jacobians

Lesson 5 of 6

Gradient descent

Step against the gradient and repeat. Why that works, exactly how large a step can be before training blows up, why narrow valleys make it crawl, and how momentum speeds it up.

About 70 minutes
By the end you can
  • Explain from the linear approximation why a small step against the gradient lowers the loss.

  • Derive wk+1−w∗=(1−ηa)(wk−w∗)w_{k+1} - w^* = (1 - \eta a)(w_k - w^*) for a one-dimensional quadratic and read off the stable range 0<η<2/a0 < \eta < 2/a.

  • Use the Hessian's eigenvalues to predict the learning-rate limit 2/λmax⁡2/\lambda_{\max} and the slowdown caused by a large condition number.

  • Explain what momentum changes, derive why no direction can shrink faster than β\sqrt{\beta} per step, and implement it.

You can now compute the gradient of a loss: the direction in which it climbs fastest. The algorithm that trains nearly every neural network, including the largest language models, is the natural next move. Take a small step the opposite way, recompute the gradient, and repeat:

w←w−η ∇L(w).\mathbf{w} \leftarrow \mathbf{w} - \eta\,\nabla L(\mathbf{w}).

The arrow means "replace w\mathbf{w} by". The number η\eta (the Greek letter eta) is the learning rate: how far to step, as a multiple of the gradient. Everything interesting hides in the word "small". Too small and training wastes days of compute. Too large and the loss explodes.

This lesson works out exactly where the line is and why it sits there. First one step, with every number. Then one dimension, where everything can be solved by hand. Then many weights, where the shape of the valley matters. Finally momentum, the first fix. The next lesson moves to real data.

Step against the gradient

Why should a step against the gradient lower the loss at all? The forecast from the gradients lesson, L(w+h)≈L(w)+∇L(w)⋅hL(\mathbf{w} + \mathbf{h}) \approx L(\mathbf{w}) + \nabla L(\mathbf{w})\cdot\mathbf{h}, answers it in two moves. Write g=∇L(w)\mathbf{g} = \nabla L(\mathbf{w}) for the gradient at the current weights. The step is h=−η g\mathbf{h} = -\eta\,\mathbf{g}.

  1. Put the step into the forecast:

    L(w−η g)≈L(w)+g⋅(−η g).L(\mathbf{w} - \eta\,\mathbf{g}) \approx L(\mathbf{w}) + \mathbf{g}\cdot(-\eta\,\mathbf{g}).
  2. Pull the number −η-\eta out of the dot product, and use the fact that a vector dotted with itself is its squared length, g⋅g=∣g∣2\mathbf{g}\cdot\mathbf{g} = |\mathbf{g}|^2:

    L(w−η g)≈L(w)−η ∣g∣2.L(\mathbf{w} - \eta\,\mathbf{g}) \approx L(\mathbf{w}) - \eta\,|\mathbf{g}|^2 .

Since ∣g∣2|\mathbf{g}|^2 is positive whenever the gradient is not zero, a small enough step lowers the loss, by about η∣g∣2\eta|\mathbf{g}|^2. The forecast ignores curvature, and curvature is exactly what bites when η\eta is large; the rest of the lesson measures it. When the gradient is zero the step is zero and descent stops. That happens at a minimum, but also at a maximum or at a saddle point, a point where the surface curves up in some directions and down in others.

A worked example in one dimension. Take the loss from the start of the module, L(w)=(w−3)2L(w) = (w - 3)^2, whose minimum is at w=3w = 3. With one weight the gradient is the ordinary derivative, L′(w)=2(w−3)L'(w) = 2(w - 3). Use the learning rate η=0.1\eta = 0.1 and start at w0=0w_0 = 0. One full step:

  1. Loss at the start. L(0)=(0−3)2=9L(0) = (0 - 3)^2 = 9.
  2. Slope at the start. L′(0)=2(0−3)=−6L'(0) = 2(0 - 3) = -6.
  3. The step. −η L′(0)=−0.1×(−6)=+0.6-\eta\,L'(0) = -0.1 \times (-6) = +0.6. The minus sign turns a negative slope into a step to the right, toward the minimum.
  4. The new weight. w1=0+0.6=0.6w_1 = 0 + 0.6 = 0.6, where L(0.6)=(0.6−3)2=(−2.4)2=5.76L(0.6) = (0.6 - 3)^2 = (-2.4)^2 = 5.76.
  5. Compare with the forecast. The forecast drop is η ∣g∣2=0.1×(−6)2=0.1×36=3.6\eta\,|g|^2 = 0.1 \times (-6)^2 = 0.1 \times 36 = 3.6. The real drop is 9−5.76=3.249 - 5.76 = 3.24, a little less, because the curve bends up away from its tangent.

The diagram draws that step on the curve, then three more, then what a much larger learning rate does. On screen are the pink loss curve L(w)=(w−3)2L(w) = (w - 3)^2 with its minimum marked on the axis at w=3w = 3, and the current weight as a white dot on the curve. Beside it a table fills in one row per iterate kk: the weight wkw_k, its loss LL (pink), the slope there (amber) and the step it produces (lime). Step through with Next.

Here are the first four iterates at η=0.1\eta = 0.1 in one table, with the distance still to go:

step kkwkw_kgradient 2(wk−3)2(w_k - 3)wk+1=wk−0.1×gradientw_{k+1} = w_k - 0.1 \times \text{gradient}distance 3−wk3 - w_k
000−6-60.60.633
10.60.6−4.8-4.81.081.082.42.4
21.081.08−3.84-3.841.4641.4641.921.92
31.4641.464−3.072-3.0721.77121.77121.5361.536

The distance shrinks by the same factor at every step: 2.4/3=0.82.4 / 3 = 0.8, 1.92/2.4=0.81.92 / 2.4 = 0.8 and 1.536/1.92=0.81.536 / 1.92 = 0.8. At η=1.1\eta = 1.1 the distances were 33, 3.63.6, 4.324.32 and 5.1845.184, each 1.21.2 times the one before, on alternating sides. Why 0.80.8, and why 1.21.2? The next section solves the one-dimensional case exactly.

One dimension, solved exactly

Near its minimum, every smooth loss looks like a bowl. So working out what gradient descent does on the simplest bowl, exactly, tells you what it does near any minimum.

Take a quadratic with its minimum at w∗w^*:

L(w)=a2 (w−w∗)2,a>0.L(w) = \frac{a}{2}\,(w - w^*)^2, \qquad a > 0 .

Its derivative is L′(w)=a2×2(w−w∗)=a (w−w∗)L'(w) = \frac{a}{2} \times 2(w - w^*) = a\,(w - w^*), and its second derivative is L′′(w)=aL''(w) = a. So aa is the curvature: how quickly the slope changes, or how sharply the bowl bends. Our example (w−3)2(w - 3)^2 is this bowl with w∗=3w^* = 3 and a=2a = 2, since (w−3)2=22(w−3)2(w - 3)^2 = \frac{2}{2}(w - 3)^2.

Go slower: The error after one step, and after many

Step 1, write out the update. Gradient descent replaces wkw_k by wk−η L′(wk)w_k - \eta\,L'(w_k). Substitute L′(wk)=a (wk−w∗)L'(w_k) = a\,(w_k - w^*):

wk+1=wk−η a (wk−w∗).w_{k+1} = w_k - \eta\,a\,(w_k - w^*).

Step 2, subtract w∗w^* from both sides.

wk+1−w∗=(wk−w∗)−η a (wk−w∗).w_{k+1} - w^* = (w_k - w^*) - \eta\,a\,(w_k - w^*).

Step 3, factor out (wk−w∗)(w_k - w^*).

wk+1−w∗=(1−ηa) (wk−w∗).w_{k+1} - w^* = (1 - \eta a)\,(w_k - w^*).

Step 4, repeat. Call the error ek=wk−w∗e_k = w_k - w^*. Every step multiplies it by the same number, ek+1=(1−ηa) eke_{k+1} = (1 - \eta a)\,e_k, so after kk steps

ek=(1−ηa)k e0.e_k = (1 - \eta a)^k\,e_0 .

Step 5, when does it shrink? Powers of a number go to zero exactly when the number's size is below 1: ∣1−ηa∣<1|1 - \eta a| < 1. That means −1<1−ηa<1-1 < 1 - \eta a < 1, two inequalities to solve one at a time.

The right one, 1−ηa<11 - \eta a < 1: subtract 1 to get −ηa<0-\eta a < 0, so ηa>0\eta a > 0, and since a>0a > 0, η>0\eta > 0.

The left one, −1<1−ηa-1 < 1 - \eta a: add ηa+1\eta a + 1 to both sides to get ηa<2\eta a < 2, so η<2/a\eta < 2/a.

Together:

0<η<2a.0 < \eta < \frac{2}{a}.

For our example the factor is 1−ηa=1−0.1×2=0.81 - \eta a = 1 - 0.1 \times 2 = 0.8: the factor in the table. With η=1.1\eta = 1.1 it is 1−1.1×2=−1.21 - 1.1 \times 2 = -1.2. The minus sign is the jump to the other side, and the size 1.21.2 is the growth. The limit is 2/a=2/2=12/a = 2/2 = 1, and 1.11.1 is above it.

Here is every regime, for a bowl with curvature a=4a = 4, L(w)=2(w−1)2L(w) = 2(w - 1)^2:

learning rate η\etafactor 1−4η1 - 4\etawhat happens
0.10.10.60.6smooth approach from one side
0.25=1/a0.25 = 1/a00lands on the minimum in one step
0.40.4−0.6-0.6overshoots, alternates sides, still converges
0.5=2/a0.5 = 2/a−1-1bounces between two points forever
0.60.6−1.4-1.4overshoots further every step: diverges

A negative factor means the step jumps past the minimum to the other side. Its size decides whether each jump lands closer or farther. This is the repeated multiplication from module 4 in its simplest form: a number with size below 1, raised to higher and higher powers, dies away, and one above 1 explodes.

The widget runs the same rule on a round bowl, L=x2+y2L = x^2 + y^2, seen from above as a contour map: pink lines of equal loss, shading that darkens toward the bottom, and a lime cross at the minimum. It has two weights, but it curves the same way in every direction, with curvature 2, exactly like (w−3)2(w - 3)^2, so each step multiplies the distance to the minimum by 1−2η1 - 2\eta. The blue dot is the start, (−2.6,1.8)(-2.6,\allowbreak 1.8); the path collects a white dot per step; the amber arrow shows where the next step goes. Among the controls, a stability panel gives the factor per step, a coral tick under the learning-rate slider marks the limit, and a chart at the bottom plots the loss after each step.

Now run three steps by hand on a sharper bowl, and find the learning rate at which it breaks.

On paperThree steps by hand, and the breaking point

Run gradient descent on L(w)=3(w−2)2L(w) = 3(w - 2)^2 from w0=0w_0 = 0 with learning rate η=0.1\eta = 0.1.

  1. Compute w1w_1, w2w_2 and w3w_3, showing the gradient at each step.
  2. Write LL in the form a2(w−w∗)2\frac{a}{2}(w - w^*)^2 and find the factor 1−ηa1 - \eta a. Check that the distance to the minimum shrinks by that factor.
  3. Find the learning rate at and above which gradient descent no longer converges on this loss. What happens at η=0.3\eta = 0.3?

To check your work, enter w1w_1, w2w_2, w3w_3 and then the threshold learning rate, in that order, as decimals (you may enter the threshold as a fraction, such as 2/5).

Work it on real paper: writing each step is the point. Then check your final answer here and compare your working with the walk-through.

w₁, w₂, w₃, then the threshold

One entry per box, top to bottom. 0.25, -2, 3/4 and sqrt(2) all work. Enter moves to the next empty box and checks once all are filled.

Many weights: the Hessian

With one weight, one number described the bowl's curvature. With many weights, curvature depends on direction: a valley can be steep across and nearly flat along its floor. We need an object that records curvature in every direction.

That object is the Hessian, the matrix of second derivatives:

Hij=∂2L∂wi ∂wj,H_{ij} = \frac{\partial^2 L}{\partial w_i\,\partial w_j},

meaning: differentiate LL with respect to wjw_j, then differentiate the result with respect to wiw_i. Equivalently, the Hessian is the Jacobian of the gradient. For the smooth functions in this course the order of the two derivatives does not matter, so Hij=HjiH_{ij} = H_{ji} and the Hessian is symmetric.

An example: L(w)=12(w12+10 w22)L(\mathbf{w}) = \tfrac{1}{2}(w_1^2 + 10\,w_2^2).

  1. The gradient. ∂L∂w1=12×2w1=w1\frac{\partial L}{\partial w_1} = \tfrac{1}{2} \times 2w_1 = w_1 and ∂L∂w2=12×10×2w2=10 w2\frac{\partial L}{\partial w_2} = \tfrac{1}{2} \times 10 \times 2w_2 = 10\,w_2, so ∇L=(w1, 10 w2)\nabla L = (w_1,\allowbreak \ 10\,w_2).
  2. Differentiate each entry again. w1w_1 has partials 11 (by w1w_1) and 00 (by w2w_2); 10 w210\,w_2 has partials 00 and 1010.
  3. The Hessian. H=[10010]\mathbf{H} = \begin{bmatrix} 1 & 0 \\ 0 & 10 \end{bmatrix}: this valley is ten times more curved across w2w_2 than along w1w_1.

Why study quadratic bowls? Recall Taylor's formula from derivatives by experiment: value, plus slope times the step, plus 12\tfrac{1}{2} curvature times the step squared. In many dimensions the gradient plays the slope and the Hessian plays the curvature. At a minimum w∗\mathbf{w}^* the gradient is zero, so the formula has no first-order term and starts with the curvature term:

L(w)≈L(w∗)+12 (w−w∗)⊤H (w−w∗),L(\mathbf{w}) \approx L(\mathbf{w}^*) + \tfrac{1}{2}\,(\mathbf{w} - \mathbf{w}^*)^\top\mathbf{H}\,(\mathbf{w} - \mathbf{w}^*),

with H\mathbf{H} the Hessian at w∗\mathbf{w}^*. Near any minimum, a smooth loss looks like a quadratic bowl, so what gradient descent does on bowls is what it does near minima. On this bowl the gradient is H(w−w∗)\mathbf{H}(\mathbf{w} - \mathbf{w}^*), by the quadratic-form rule from the gradients lesson (the 12\tfrac{1}{2} cancels the 2). For the example, with w∗=0\mathbf{w}^* = \mathbf{0}, that is (w1, 10 w2)(w_1,\allowbreak \ 10\,w_2), as we found.

Go slower: Gradient descent on a bowl, one eigen-direction at a time

Step 1, the error update. Let ek=wk−w∗\mathbf{e}_k = \mathbf{w}_k - \mathbf{w}^*. The gradient at wk\mathbf{w}_k is H ek\mathbf{H}\,\mathbf{e}_k, so the update is wk+1=wk−η H ek\mathbf{w}_{k+1} = \mathbf{w}_k - \eta\,\mathbf{H}\,\mathbf{e}_k. Subtract w∗\mathbf{w}^* from both sides:

ek+1=ek−η H ek=(I−η H) ek.\mathbf{e}_{k+1} = \mathbf{e}_k - \eta\,\mathbf{H}\,\mathbf{e}_k = (\mathbf{I} - \eta\,\mathbf{H})\,\mathbf{e}_k .

So the error is multiplied by the same matrix every step, and ek=(I−ηH)k e0\mathbf{e}_k = (\mathbf{I} - \eta\mathbf{H})^k\,\mathbf{e}_0.

Step 2, use the eigenvectors. H\mathbf{H} is symmetric, so (module 4) it has perpendicular unit eigenvectors v1,…,vn\mathbf{v}_1,\allowbreak \ldots,\allowbreak \mathbf{v}_n with real eigenvalues λ1,…,λn\lambda_1,\allowbreak \ldots,\allowbreak \lambda_n. Write the starting error in that basis: e0=c1v1+⋯+cnvn\mathbf{e}_0 = c_1\mathbf{v}_1 + \cdots + c_n\mathbf{v}_n.

Step 3, each direction on its own. Since Hvi=λivi\mathbf{H}\mathbf{v}_i = \lambda_i\mathbf{v}_i, we get (I−ηH) vi=vi−ηλivi=(1−ηλi) vi(\mathbf{I} - \eta\mathbf{H})\,\mathbf{v}_i = \mathbf{v}_i - \eta\lambda_i\mathbf{v}_i = (1 - \eta\lambda_i)\,\mathbf{v}_i. Applying the matrix kk times multiplies each piece by its own factor kk times:

ek=(1−ηλ1)k c1v1+⋯+(1−ηλn)k cnvn.\mathbf{e}_k = (1 - \eta\lambda_1)^k\,c_1\mathbf{v}_1 + \cdots + (1 - \eta\lambda_n)^k\,c_n\mathbf{v}_n .

Each eigen-direction is a separate one-dimensional problem with curvature λi\lambda_i.

Step 4, the limit. Every piece shrinks only if ∣1−ηλi∣<1|1 - \eta\lambda_i| < 1 for every ii, which means η<2/λi\eta < 2/\lambda_i for all of them, and the binding one is the largest eigenvalue: η<2/λmax⁡\eta < 2/\lambda_{\max}.

Step 5, the best single learning rate. The slowest piece decides the pace, so choose η\eta to make the worst factor as small as possible. As η\eta grows, ∣1−ηλmin⁡∣|1 - \eta\lambda_{\min}| shrinks while ∣1−ηλmax⁡∣|1 - \eta\lambda_{\max}| eventually grows. The best balance is where the two sizes are equal. At that rate the flat direction's factor 1−ηλmin⁡1 - \eta\lambda_{\min} is still positive, while the steep direction's factor is negative, with size ηλmax⁡−1\eta\lambda_{\max} - 1. So the balance reads 1−ηλmin⁡=ηλmax⁡−11 - \eta\lambda_{\min} = \eta\lambda_{\max} - 1. Add 1+ηλmin⁡1 + \eta\lambda_{\min} to both sides: 2=η(λmin⁡+λmax⁡)2 = \eta(\lambda_{\min} + \lambda_{\max}), so η=2λmin⁡+λmax⁡\eta = \frac{2}{\lambda_{\min} + \lambda_{\max}}.

Step 6, the factor at that rate. Substitute into 1−ηλmin⁡1 - \eta\lambda_{\min}: 1−2λmin⁡λmin⁡+λmax⁡=λmax⁡−λmin⁡λmax⁡+λmin⁡1 - \frac{2\lambda_{\min}}{\lambda_{\min} + \lambda_{\max}} = \frac{\lambda_{\max} - \lambda_{\min}}{\lambda_{\max} + \lambda_{\min}}. Divide the top and bottom by λmin⁡\lambda_{\min} to get κ−1κ+1\frac{\kappa - 1}{\kappa + 1}, where κ=λmax⁡/λmin⁡\kappa = \lambda_{\max}/\lambda_{\min}.

So far. The Hessian records curvature in every direction. Along each of its eigenvectors, gradient descent is the one-dimensional problem again, with curvature λi\lambda_i and factor 1−ηλi1 - \eta\lambda_i per step.

The condition number

Two numbers fall out of the eigen-direction picture, and together they explain why training can be unstable and slow at the same time.

  • The learning-rate limit 2/λmax⁡2/\lambda_{\max}, set by the steepest direction.
  • The condition number κ=λmax⁡/λmin⁡\kappa = \lambda_{\max}/\lambda_{\min}. When it is large, any learning rate small enough for the steep direction is far too small for the flat one. Even the best single rate shrinks the error only by a factor of κ−1κ+1\frac{\kappa - 1}{\kappa + 1} per step, which is close to 1.

Take the valley H=diag(1,10)\mathbf{H} = \mathrm{diag}(1,\allowbreak 10) from above, with κ=10/1=10\kappa = 10 / 1 = 10.

  1. The limit. η<2/λmax⁡=2/10=0.2\eta < 2/\lambda_{\max} = 2/10 = 0.2.
  2. A rate near the limit, η=0.18\eta = 0.18. The factors are 1−0.18×1=0.821 - 0.18 \times 1 = 0.82 along w1w_1 and 1−0.18×10=−0.81 - 0.18 \times 10 = -0.8 across w2w_2. The w2w_2 coordinate flips sign at every step, so the path zig-zags across the valley while creeping along it.
  3. The best rate. η=21+10=211≈0.182\eta = \frac{2}{1 + 10} = \frac{2}{11} \approx 0.182, with factor 10−110+1=911≈0.818\frac{10 - 1}{10 + 1} = \frac{9}{11} \approx 0.818 in both directions. Shrinking the error a thousandfold takes 35 steps, since (9/11)35<0.001<(9/11)34(9/11)^{35} < 0.001 < (9/11)^{34}.
  4. Worse conditioning. With κ=100\kappa = 100 the best factor is 99101≈0.980\frac{99}{101} \approx 0.980, and the same thousandfold shrink takes 346 steps.

Ten times worse conditioning, ten times more steps. The code runs the κ=10\kappa = 10 valley from (1,1)(1,\allowbreak 1) at three learning rates and plots the loss:

⌘+Enter runs · edit freelyPython sleeps until you run code

At η=0.05\eta = 0.05 both coordinates shrink smoothly but w1w_1 crawls (11, 0.950.95, 0.9020.902, 0.8570.857). At 0.180.18 the second coordinate alternates sign (11, −0.8-0.8, 0.640.64, −0.512-0.512: the zig-zag) and the loss falls fast. At 0.210.21, just past the limit, the second coordinate grows by a factor of 1.11.1 per step (11, −1.1-1.1, 1.211.21, −1.331-1.331) and the loss explodes.

The widget runs this same valley, L=12x2+5y2L = \tfrac{1}{2}x^2 + 5y^2, whose Hessian is diag(1,10)\mathrm{diag}(1,\allowbreak 10). The steep direction is yy, across the valley; the flat one is xx, along its floor. The run starts at (−2.8,1.6)(-2.8,\allowbreak 1.6) with η=0.05\eta = 0.05. The stability panel lists each curvature λ\lambda with its factor per step, and the coral tick under the learning-rate slider marks the limit 0.20.2.

This is why learning rates are tuned by experiment when you train networks in module 6, and why the optimizers used to train LSTMs in module 8 rescale different directions differently. The eigenvalues are not known in advance for a real network, and they change during training, but the logic is the same: the sharpest direction caps the step, and the flattest direction sets the pace.

So far. The largest curvature caps the learning rate at 2/λmax⁡2/\lambda_{\max}. The smallest curvature then sets the pace, and their ratio κ\kappa says how slow even the best single learning rate must be.

Find a learning-rate limit from a Hessian you compute yourself.

Work it outThe largest safe learning rate

The loss is L(w)=1.5 w12+w1w2+1.5 w22L(\mathbf{w}) = 1.5\,w_1^2 + w_1w_2 + 1.5\,w_2^2. Find its Hessian, then the learning rate at which gradient descent stops converging. Enter that learning rate as a decimal.

largest stable η

Type a number: 0.25, -2, 3/4 and sqrt(2) all work. Enter checks.

Now run the reasoning backwards: from three training runs, bracket the curvature.

Quick checkRead the curvature off three runs

You train the same model three times with full-batch gradient descent, starting close to a minimum. With η=0.01\eta = 0.01 the loss falls slowly and steadily. With η=0.1\eta = 0.1 it falls fast. With η=0.3\eta = 0.3 it grows by roughly the same factor every step. Treating the loss near the minimum as a quadratic bowl, what can you conclude about the largest Hessian eigenvalue λmax⁡\lambda_{\max}?

Choose one answer, then check.

Momentum

The zig-zag suggests its own fix. Across the valley, successive gradients point in opposite directions. Along the valley floor, they point the same way every time. If we averaged recent gradients, the across-valley parts would cancel and the along-valley parts would add up.

That is momentum. Keep a running "velocity" v\mathbf{v} and step along it:

v←β v+∇L(w),w←w−η v,\mathbf{v} \leftarrow \beta\,\mathbf{v} + \nabla L(\mathbf{w}), \qquad \mathbf{w} \leftarrow \mathbf{w} - \eta\,\mathbf{v},

with v\mathbf{v} starting at zero and β\beta between 0 and 1, often 0.90.9. Write gk\mathbf{g}_k for the gradient at step kk and unroll the first three velocities:

  • v1=β⋅0+g1=g1\mathbf{v}_1 = \beta \cdot \mathbf{0} + \mathbf{g}_1 = \mathbf{g}_1,
  • v2=β v1+g2=g2+β g1\mathbf{v}_2 = \beta\,\mathbf{v}_1 + \mathbf{g}_2 = \mathbf{g}_2 + \beta\,\mathbf{g}_1,
  • v3=β v2+g3=g3+β g2+β2 g1\mathbf{v}_3 = \beta\,\mathbf{v}_2 + \mathbf{g}_3 = \mathbf{g}_3 + \beta\,\mathbf{g}_2 + \beta^2\,\mathbf{g}_1.

The pattern continues: the velocity is a weighted sum of all past gradients, vk=gk+β gk−1+β2 gk−2+⋯\mathbf{v}_k = \mathbf{g}_k + \beta\,\mathbf{g}_{k-1} + \beta^2\,\mathbf{g}_{k-2} + \cdots, with weights fading geometrically. Two consequences:

  • Where the gradient keeps the same value g\mathbf{g}, the velocity grows toward g(1+β+β2+⋯ )=g/(1−β)\mathbf{g}(1 + \beta + \beta^2 + \cdots) = \mathbf{g}/(1 - \beta), the sum of a geometric series. With β=0.9\beta = 0.9 that is g/0.1=10 g\mathbf{g}/0.1 = 10\,\mathbf{g}: a step ten times larger along steady directions.
  • Where the gradient alternates sign, g,−g,g,…\mathbf{g},\allowbreak -\mathbf{g},\allowbreak \mathbf{g},\allowbreak \ldots, successive terms largely cancel. The velocity settles at g/(1+β)\mathbf{g}/(1 + \beta) in size, about 0.53 g0.53\,\mathbf{g} with β=0.9\beta = 0.9, so the zig-zag is damped instead of amplified.

The picture behind the name is a heavy ball rolling down the valley: its inertia carries it along the floor and smooths out the side-to-side bouncing.

A long narrow valley seen from above as nested elongated ellipses. A thin path bounces from wall to wall across the valley in a tight zig-zag and gets a little over halfway to the center. A heavy ball's smooth path from the same start swings across the floor a few times, each swing smaller than the last, then runs along the middle of the floor and gets much closer to the lowest point at the center.Momentum: the side-to-side pushes cancel, the steady pull along the floor adds up.

The method is often called Polyak's heavy-ball method, after Boris Polyak, who analyzed it in 1964. On the valley H=diag(1,100)\mathbf{H} = \mathrm{diag}(1,\allowbreak 100), starting at (1,1)(1,\allowbreak 1) with η=0.01\eta = 0.01, plain gradient descent needs 1,375 steps to get within 10−610^{-6} of the minimum; with momentum β=0.9\beta = 0.9 and the same η\eta it needs 264. The momentum coefficient is itself a knob, not a free lunch: on the same problem, β=0.5\beta = 0.5 takes 671 steps, 0.80.8 takes 192 and 0.950.95 takes 498, because too much momentum overshoots and oscillates along the floor.

Why does momentum help so much here, and why does more momentum stop helping? Along each eigen-direction of the Hessian, momentum turns the one-step error rule of the last section into a two-step rule, and that rule has a simple bound: a limit on how fast any direction can shrink.

Go slower: Momentum along one eigen-direction

Take one eigen-direction with curvature λ\lambda. Let eke_k be the error along it (the distance to the minimum, with a sign) and vkv_k the velocity along it, starting at v0=0v_0 = 0. The gradient along it is λ ek\lambda\,e_k, so the two updates are

vk+1=β vk+λ ek,ek+1=ek−η vk+1.v_{k+1} = \beta\,v_k + \lambda\,e_k, \qquad e_{k+1} = e_k - \eta\,v_{k+1}.

Step 1, multiply the velocity update by η\eta.

η vk+1=β η vk+ηλ ek.\eta\,v_{k+1} = \beta\,\eta\,v_k + \eta\lambda\,e_k .

Step 2, remove the velocity. The second update says η vk+1=ek−ek+1\eta\,v_{k+1} = e_k - e_{k+1}, and one step earlier η vk=ek−1−ek\eta\,v_k = e_{k-1} - e_k. Substitute both:

ek−ek+1=β (ek−1−ek)+ηλ ek.e_k - e_{k+1} = \beta\,(e_{k-1} - e_k) + \eta\lambda\,e_k .

Step 3, solve for the new error. Move ek+1e_{k+1} to the left side alone and collect the eke_k terms:

ek+1=(1+β−ηλ) ek−β ek−1.e_{k+1} = (1 + \beta - \eta\lambda)\,e_k - \beta\,e_{k-1}.

Each error now depends on the two before it. With β=0\beta = 0 this is the old rule ek+1=(1−ηλ) eke_{k+1} = (1 - \eta\lambda)\,e_k.

Step 4, look for a constant factor. Try ek=rke_k = r^k, an error multiplied by the same number rr every step. Substitute: rk+1=(1+β−ηλ) rk−β rk−1r^{k+1} = (1 + \beta - \eta\lambda)\,r^k - \beta\,r^{k-1}. Divide by rk−1r^{k-1} and move everything to one side:

r2−(1+β−ηλ) r+β=0.r^2 - (1 + \beta - \eta\lambda)\,r + \beta = 0 .

This quadratic has two roots r1r_1 and r2r_2, and the error is a mix of r1kr_1^k and r2kr_2^k. The root with the larger size sets the pace. When the roots are complex, the error oscillates as it shrinks: the overshooting you see along the valley floor.

Step 5, a bound on the speed. A quadratic r2+br+cr^2 + br + c with roots r1,r2r_1,\allowbreak r_2 factors as (r−r1)(r−r2)=r2−(r1+r2)r+r1r2(r - r_1)(r - r_2) = r^2 - (r_1 + r_2)r + r_1 r_2, so the product of its roots is its constant term cc. Here r1r2=βr_1 r_2 = \beta, so the sizes multiply to ∣r1∣ ∣r2∣=β|r_1|\,|r_2| = \beta. They cannot both be below β\sqrt{\beta}, or their product would be below β×β=β\sqrt{\beta} \times \sqrt{\beta} = \beta. So the larger root has size at least β\sqrt{\beta}, whatever η\eta and λ\lambda are. With β=0.9\beta = 0.9, no direction can shrink faster than 0.9≈0.949\sqrt{0.9} \approx 0.949 per step.

Step 6, the stability limit. For a tiny η\eta both roots lie between −1-1 and 11 (they are close to 11 and to β\beta), and as η\eta grows they move continuously. Complex roots have size exactly β<1\sqrt{\beta} < 1, so they cannot escape. Real roots can only escape by passing through r=1r = 1 or r=−1r = -1. Putting r=1r = 1 in the quadratic gives 1−1−β+ηλ+β=ηλ=01 - 1 - \beta + \eta\lambda + \beta = \eta\lambda = 0, which never happens. Putting r=−1r = -1 gives 1+1+β−ηλ+β=2(1+β)−ηλ=01 + 1 + \beta - \eta\lambda + \beta = 2(1 + \beta) - \eta\lambda = 0. So descent with momentum is stable exactly when ηλ<2(1+β)\eta\lambda < 2(1 + \beta): momentum raises the limit from 2/λmax⁡2/\lambda_{\max} to 2(1+β)/λmax⁡2(1 + \beta)/\lambda_{\max}.

Now the step counts make sense. On diag(1,100)\mathrm{diag}(1,\allowbreak 100) with η=0.01\eta = 0.01, plain descent's flat direction shrinks by 1−0.01×1=0.991 - 0.01 \times 1 = 0.99 per step, and 0.991375≈10−60.99^{1375} \approx 10^{-6}. Momentum 0.90.9 brings every direction down to the bound 0.9≈0.949\sqrt{0.9} \approx 0.949, and 0.949264≈10−60.949^{264} \approx 10^{-6}. The best β\beta balances two effects: large enough to speed up the flat direction, small enough to keep the bound β\sqrt{\beta} low. At β=0.5\beta = 0.5 the flat direction still shrinks only by about 0.9800.980 per step (671 steps); at 0.80.8 its factor is about 0.9270.927 (192 steps); at 0.950.95 the bound has risen to 0.95≈0.975\sqrt{0.95} \approx 0.975 (498 steps). And on a milder valley, where plain descent already beats 0.9490.949 per step, momentum 0.90.9 makes things worse: a milder valley wants a smaller β\beta.

The widget runs the valley from before, L=12x2+5y2L = \tfrac{1}{2}x^2 + 5y^2, with the same learning rate, 0.050.05, now with momentum β=0.6\beta = 0.6. The formula panel shows both updates with live numbers, the velocity first. The stability panel shows each direction's factor, and the coral tick marks the raised limit 2(1+β)/λmax⁡2(1 + \beta)/\lambda_{\max}.

In short. Momentum adds a fraction β\beta of the last step to each new one. Steady directions speed up by up to 1/(1−β)1/(1 - \beta), alternating ones are damped, and no direction can shrink faster than β\sqrt{\beta} per step, so the best β\beta depends on how badly conditioned the valley is.

Now build both methods, check the stability limit, and reproduce the step counts above.

Code itGradient descent and momentum on a bowl

Explore gradient descent on the bowl L(w)=12(w−w∗)⊤H (w−w∗)L(\mathbf{w}) = \tfrac{1}{2}(\mathbf{w} - \mathbf{w}^*)^\top\mathbf{H}\,(\mathbf{w} - \mathbf{w}^*), whose gradient is H(w−w∗)\mathbf{H}(\mathbf{w} - \mathbf{w}^*).

  • gd_path(H, w_star, w0, lr, steps): every iterate, start included, as an array of shape (steps + 1, d).
  • max_stable_lr(H): the limit 2/λmax⁡2/\lambda_{\max}.
  • momentum_path(H, w_star, w0, lr, beta, steps): the same with momentum, v←βv+∇L\mathbf{v} \leftarrow \beta\mathbf{v} + \nabla L and w←w−ηv\mathbf{w} \leftarrow \mathbf{w} - \eta\mathbf{v}, starting from v=0\mathbf{v} = \mathbf{0}.
  • steps_to_reach(path, w_star, tol): the first index whose distance to w∗\mathbf{w}^* is below tol, or None.

The code at the bottom races plain descent against momentum on the valley diag(1,100)\mathrm{diag}(1,\allowbreak 100). It should reproduce the lesson's 1,375 and 264 steps.

⌘+Enter runsPython sleeps until you run code
Write your code where the starter says raise NotImplementedError, then press Run tests. Each check says what it expects.

Everything in this lesson used the exact gradient of a loss written as one short formula. A real training loss is an average over millions of examples, and computing its exact gradient on every step is too expensive. The next lesson estimates it from small random batches, meets Adam, and fits a real model both exactly and by descent.