Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 46 ยท Optimization Models

Gradient descent and fitting models

Learn gradient descent from scratch: the update rule, why the learning rate matters, how to fit a line to data, and why a start point can change the answer.

Calculus and linear programming need a formula or straight-line limits. What if your objective is a messy function of many parameters, such as the total error of a model against thousands of data points? Then you search: stand at a guess, find which direction goes downhill, take a step, repeat. This is gradient descent, the engine behind curve fitting, logistic regression and the training of neural networks. You can write it in five lines.

Elliptical contour lines of a bowl-shaped function with a pink path of dots that zigzags toward the minimum at the centre; a card shows the update rule and the effect of the learning rate.
The path zigzags because the bowl is steeper in y than in x. Too large a step makes the zigzag grow instead of shrink.

What you will learn

  • The gradient descent update ฮธ โ† ฮธ โˆ’ ฮทยทโˆ‡f(ฮธ) and what the gradient means.
  • Why the learning rate ฮท must be small enough, and how to compute the limit.
  • How to fit a line to data by minimizing the sum of squared errors.
  • Why different starting points can end at different minima.

Key terms

Gradient (โˆ‡f): the vector of partial derivatives; it points in the direction of steepest increase.

Learning rate (ฮท): the multiplier that sets the step length.

Loss function: a number that measures how badly the model fits; we minimize it.

Local minimum: a point lower than all its neighbours but not necessarily the lowest overall.

The update rule

For a function f(x, y) the gradient is โˆ‡f = (โˆ‚f/โˆ‚x, โˆ‚f/โˆ‚y). It points uphill, so we step the other way:

ฮธ_new = ฮธ_old โˆ’ ฮท ยท โˆ‡f(ฮธ_old)

Take f(x, y) = xยฒ + 5yยฒ, a bowl that is five times steeper in y than in x. Its gradient is (2x, 10y), and the update is

x_new = xยท(1 โˆ’ 2ฮท), y_new = yยท(1 โˆ’ 10ฮท).

Each coordinate is multiplied by a constant factor every step. The iteration converges only if both factors have absolute value below 1: |1 โˆ’ 2ฮท| < 1 needs ฮท < 1, and |1 โˆ’ 10ฮท| < 1 needs ฮท < 0.2. The steepest direction sets the speed limit. With ฮท = 0.15 the y factor is โˆ’0.5: y flips sign each step while shrinking, which is the zigzag in the picture. With ฮท = 0.21 the factor is โˆ’1.1, and y grows without bound.

This is a universal rule of thumb: the largest curvature of the loss limits the learning rate, and the smallest curvature limits how fast you converge. Elongated valleys are slow.

Python Four learning rates

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.

Fitting a line by descent

Here is a typical use. We have data points (xแตข, yแตข) and want the line y = mยทx + c that fits best. Define the loss as the mean squared error:

L(m, c) = (1/n) ยท ฮฃ (mยทxแตข + c โˆ’ yแตข)ยฒ

Its gradient is โˆ‚L/โˆ‚m = (2/n) ฮฃ (mยทxแตข + c โˆ’ yแตข)ยทxแตข and โˆ‚L/โˆ‚c = (2/n) ฮฃ (mยทxแตข + c โˆ’ yแตข). Descent adjusts m and c until the gradient vanishes. For this quadratic loss there is also an exact formula (least squares, next chapter), so we can check that descent got the right answer.

A practical trick: subtract the mean of x before fitting. Centered data makes the valley rounder, so descent converges much faster. In the demo below we fit the centered model and convert back.

Python Gradient descent against least squares

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.

Common misconceptions

"Gradient descent always finds the best answer." It finds a place where the gradient is zero, which can be a local minimum or a flat saddle. Only for convex losses (like squared error for a line) is every minimum a global one.

"A bigger learning rate is always faster." Only up to the stability limit. Beyond it the iteration diverges, so progress is not slower but negative.

"The gradient points to the minimum." It points steeply uphill from where you stand. In a long thin valley it points mostly across the valley, which is why the path zigzags.

Local minima: the start matters

Take the one-variable function f(x) = xโด โˆ’ 3xยฒ + x. Its derivative 4xยณ โˆ’ 6x + 1 has three roots, near โˆ’1.30 (a deep valley), 0.17 (a hilltop) and 1.13 (a shallower valley). Gradient descent starting on the left finds the deep valley; starting on the right it settles in the shallower one and never learns that something better exists.

Practical answers: start from several points and keep the best (multi-start), add random noise, or use a method designed for global search. In many fitting problems the loss is convex or nearly so, and a single start is fine.

Python Two starting points, two answers

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.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the gradient of f point toward?

    The gradient points uphill; gradient descent subtracts it to go downhill.
  2. 2. For f(x, y) = x^2 + 5y^2, which learning rate makes gradient descent diverge?

    The y factor is 1 - 10 eta, which has absolute value above 1 when eta is above 0.2.
  3. 3. Why does centring the x data help when fitting a line by descent?

    Centred inputs make the slope and intercept directions less correlated, improving conditioning.
  4. 4. Which loss is guaranteed to have only one minimum?

    For a convex function every local minimum is a global minimum.
  5. 5. For f(x) = x^4 - 3x^2 + x, gradient descent from x = 2 ends at:

    Starting on the right it slides down into the nearer, shallower valley.

Summary

  • Gradient descent repeats ฮธ โ† ฮธ โˆ’ ฮทยทโˆ‡f(ฮธ).
  • The learning rate must be below a limit set by the steepest curvature (0.2 in our bowl).
  • Fitting a line means minimizing squared error; descent agrees with least squares.
  • Non-convex problems have local minima, so the starting point matters.

Next: Chapter 6 review