Skip to content
Tutorials Center
My learning

Topics

Lesson 63 of 68 ยท Projects

Project: Gradient Descent from Calculus

Build gradient descent from first principles: derive loss gradients, tune the learning rate, add momentum, fit a line and a curve, verify with finite differences.

Gradient descent is the engine behind most of modern machine learning, and it is nothing more than calculus used in a loop. The gradient of a function points uphill, so stepping a little way in the opposite direction makes the function smaller. Repeat that step enough times and you slide down to a minimum.

In this project you write the whole thing yourself with nothing but numpy. You derive the gradient of a loss function with the chain rule, check it against finite differences, discover what the learning rate does, speed up a slow problem with momentum, and finally fit a curve. Along the way you will see why the theory of Optimization in Several Variables and Gradient and Directional Derivatives is not just textbook material.

flowchart LR
    A["Start: guess<br/>w, b"] --> B["Compute loss L(w, b)"]
    B --> C["Compute gradient<br/>dL/dw, dL/db"]
    C --> D["Step downhill<br/>w = w - lr * dL/dw"]
    D --> E{"Gradient<br/>small?"}
    E -- no --> B
    E -- yes --> F["Done: a minimum"]

The whole algorithm: evaluate, differentiate, step, repeat.

The problem: fit a line

We have 40 points scattered around the line y = 2x + 1, with noise added. We want the best slope w and intercept b. "Best" must be defined as a number, and the usual choice is the mean squared error:

L(w, b) = (1/n) * sum of (w*x_i + b - y_i)**2

This is a function of two variables whose minimum we want. Write e_i = w*x_i + b - y_i for the error of point i. The chain rule applied to a square gives d(e_i**2)/dw = 2*e_i * x_i, because the derivative of e_i with respect to w is x_i, and d(e_i**2)/db = 2*e_i * 1. So

  • dL/dw = (2/n) * sum of e_i * x_i
  • dL/db = (2/n) * sum of e_i

In numpy that is two lines. But a derivative done by hand deserves a check, and finite differences are the standard one. The central difference (L(w + h) - L(w - h)) / (2h) approximates dL/dw with an error proportional to h**2. Because the loss is quadratic, the setting h = 1e-6 gives agreement to six or more digits unless round-off interferes.

Python Gradients of a loss, checked by finite differences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At the starting guess (w, b) = (-1, 3) both gradients agree to six decimals: (-2.087434, 4.158074). Gradient descent will move opposite to this vector, so it raises w and lowers b. At the exact minimiser, found by setting both partial derivatives to zero and solving the resulting linear system (lstsq), the gradient is zero up to round-off (about 1e-16) and the loss is 0.026, close to the noise variance 0.2**2 = 0.04 (a fit always does a little better than the truth on its own training data).

Make gradient checking a habit. A wrong gradient does not crash; it makes the optimiser quietly misbehave. Comparing against central differences at one random point takes five lines and catches most sign errors and missing factors of two.

Step 1: the learning rate

The update rule is w = w - lr * dL/dw, and likewise for b. The learning rate lr is the step size, and it is the single most important number. Too small and progress crawls. Too large and each step overshoots the valley and lands higher on the far wall, so the loss grows.

For a quadratic loss we can say exactly where the boundary lies. Near the minimum, each coordinate along an eigenvector of the Hessian (the matrix of second derivatives, see Eigenvalues and Eigenvectors in Engineering) is multiplied by 1 - lr * lambda each step, where lambda is the matching eigenvalue. That factor has magnitude below 1 only if lr < 2 / lambda_max. Here the Hessian is 2 * [[mean(x**2), mean(x)], [mean(x), 1]], and since the points are centred, mean(x) = 0 and its largest eigenvalue is 2. So the limit is lr < 1.

Python Learning rate: too small, just right, too big

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With lr = 0.01 the loss is still 1.745 after 60 steps and w has barely left zero: stable but painfully slow. lr = 0.1 is already close (loss 0.0266), and lr = 0.5 lands on the optimum (0.02611, w = 1.978, b = 0.921). It is the best choice because the intercept direction has lambda = 2, so 1 - 0.5*2 = 0 and b is corrected in a single step. Above the limit of 1, everything diverges: at lr = 1.2 the loss reaches 1e18, and lr = 1.5 is worse. Right at lr = 1 the intercept error would flip sign every step without shrinking.

Step 2: momentum

Real problems are rarely this friendly. Take a long narrow valley, f = 0.5*(x**2 + 50*y**2): steep across, almost flat along. The steep direction forces a small learning rate (below 2/50 = 0.04), and that small step makes progress along the flat direction painfully slow.

Momentum keeps a running velocity v. Each step is v = beta*v - lr*grad followed by p = p + v. Gradients that point the same way step after step build up speed, and gradients that flip sign across the valley cancel out. With beta = 0.9 the effective step along a consistent direction is about ten times larger. The stability bound loosens too, to roughly lr*lambda_max < 2*(1 + beta).

Python Momentum on a stretched valley

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After 100 steps at lr = 0.01, plain descent has f = 6.7, a small momentum of 0.5 reaches 0.84, and beta = 0.9 reaches 5.6e-4, four orders of magnitude better for the same cost per step. The last two lines show the second benefit: lr = 0.05 is above the plain-descent limit of 0.04 and explodes to 2.8e8 in 20 steps, but with beta = 0.9 the same step size is stable and reaches 5e-8 in 200 steps.

Step 3: fit a curve

Nothing in the method needs the model to be a line. Fit y = a*x**2 + b*x + c to 60 noisy points. Put the three features into a matrix X with columns x**2, x and 1, so the prediction is X @ theta and the loss is mean((X @ theta - y)**2). The chain rule gives the gradient in one line: (2/n) * X.T @ (X @ theta - y). The same code works for any model that is linear in its parameters, with any number of features.

The fit is also a linear least-squares problem, so np.polyfit solves it exactly, which gives us a reference answer.

Python Fitting a curve with gradient descent

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The finite-difference check passes (mismatch about 1e-10). The loss falls from 2.76 to 0.553 after 10 updates and 0.0712 after 100, then flattens at 0.07103 by 1,000 updates. The final parameters [0.479, -0.997, 0.326] agree with np.polyfit to three decimals. They differ slightly from the true [0.5, -1.0, 0.3] because of the noise in the 60 points, not because of the optimiser.

Notice that the convergence slows down at the end. Near the minimum the gradient itself shrinks, so each step shrinks too. That is why practical optimisers stop when the gradient norm falls below a tolerance rather than after a fixed number of steps.

Where this goes next

  • Non-convex losses have several minima and saddle points, covered in Optimization in Several Variables. Gradient descent finds a minimum, not necessarily the lowest.
  • Stochastic gradient descent estimates the gradient from a small random batch of points, which is cheap and noisy and works surprisingly well.
  • Automatic differentiation computes exact gradients of arbitrary code by applying the chain rule mechanically, replacing hand derivation (see Floating-Point Error and Conditioning).
  • Feature scaling matters: if one feature is 1,000 times larger than another, the Hessian eigenvalues differ by 1,000,000 and the valley becomes extremely narrow.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. For the loss L = mean((w*x + b - y)^2), what is dL/db?

    The chain rule gives 2*e times the derivative of e with respect to b, which is 1. Averaging over the points gives 2 * mean(e).
  2. 2. Why compare an analytic gradient with a central finite difference?

    A wrong gradient does not raise an error; it just makes the optimiser misbehave. A numerical check at one point reveals the mistake quickly.
  3. 3. In the line-fitting example the stability limit is lr < 1. What happens at lr = 1.2?

    Above 2 / lambda_max each step multiplies the error component by a factor of magnitude greater than 1, so the iterates diverge.
  4. 4. What does momentum do on a long narrow valley?

    The velocity adds up gradients that keep pointing along the valley while gradients that flip sign across it cancel, so progress along the flat direction speeds up.
  5. 5. The quadratic fit by gradient descent gave [0.479, -0.997, 0.326], not the true [0.5, -1.0, 0.3]. Why?

    The minimiser of the loss on noisy data is not the true curve. Both gradient descent and the exact least-squares solution land on the same noisy-data optimum.

Summary

  • Gradient descent repeats p = p - lr * grad(L); the gradient comes straight from the chain rule.
  • Always verify a hand-derived gradient with central differences (error proportional to h**2).
  • For a quadratic loss, descent converges only if lr < 2 / lambda_max of the Hessian; here the limit was 1 and lr = 0.5 was ideal.
  • Momentum (v = beta*v - lr*grad) speeds up narrow valleys and allowed a step size that diverged without it.
  • Any model linear in its parameters has gradient (2/n) * X.T @ (X @ theta - y), and the result matches np.polyfit.
  • Convergence slows near the minimum because the gradient shrinks; stop on a gradient tolerance.

Next: Project: A Signal Analysis Lab.