Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 38 · Gradient Descent

Gradient Descent

Build gradient descent from scratch: the update rule, a stopping test, trajectories on a 2D bowl and least squares. See how the step size changes the path.

Gradient descent is the workhorse of optimization and machine learning. The idea fits in one sentence: from where you stand, take a small step in the direction that goes downhill fastest, then repeat. Because the gradient points uphill, the downhill direction is its negative.

The update rule

Start at a point x₀. At step k, compute the gradient and move:

Text
x_{k+1} = x_k - t · ∇f(x_k)

The positive number t is the step size (in machine learning, the learning rate). Stop when the gradient is tiny, for instance ‖∇f(x_k)‖ ≤ ε, because for a convex function a zero gradient means a global minimum.

Here is a complete implementation that records the path, so we can inspect it.

Python Gradient descent function

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 method finds (1, -2) after about ninety iterations. For this function the gradient is (2(x - 1), 8(y + 2)), which vanishes exactly there.

Watching the path

Level curves (contours) of the objective show the landscape from above. The path should walk across them toward the center.

Python Trajectory on contour lines

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.

You will see a zigzag. The valley is steeper in y than in x (the coefficient 4 makes it narrow), so early steps jump sideways across the valley before creeping along it. This zigzag is typical of elongated bowls and will matter a lot when we study conditioning.

Least squares with gradient descent

Fitting a line y ≈ w·x + b to data is a convex problem. With A the design matrix, the objective is f(θ) = (1/2n)‖Aθ - y‖² and its gradient is (1/n)Aᵀ(Aθ - y).

Python Fit a line 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 two answers should agree to about three decimals (the numbers near 3 and 2 reflect how the data were generated). Gradient descent trades the matrix algebra of the exact solution for simple repeated steps, which scales to huge problems.

Why does it work?

Near x, the function looks like its tangent plane: f(x + d) ≈ f(x) + ∇f(x)ᵀd. Among all steps of a fixed small length, d = -t∇f(x) makes this first-order change as negative as possible. If the step is small enough, the true function decreases too. If it is too large, the approximation breaks and the function may increase. That is the topic of the next lesson.

flowchart TD
    A["Start x0"] --> B["Compute gradient"]
    B --> C{"Gradient small?"}
    C -->|yes| D["Stop: x is (near) optimal"]
    C -->|no| E["x = x - t * gradient"]
    E --> B

The gradient descent loop.

Always keep a counter and a maximum number of iterations. A bad step size can make the loop run forever or blow up to infinity.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. The gradient descent update is

    We subtract the gradient because it points uphill and we want to go down.
  2. 2. A common stopping rule is

    A tiny gradient means we are near a stationary point, which is a global minimum for convex f.
  3. 3. Why does gradient descent zigzag on a narrow valley?

    In an elongated bowl the steepest direction is nearly perpendicular to the valley floor.
  4. 4. For least squares f(θ) = (1/2n)‖Aθ - y‖², the gradient is

    Differentiating the half squared residual gives Aᵀ times the residual, scaled by 1/n.

Summary

  • Gradient descent repeats x ← x - t∇f(x) until the gradient is small.
  • On convex problems, a zero gradient means a global minimum.
  • Elongated valleys cause zigzag paths; the step size controls stability.
  • Least squares is a natural test problem with an exact answer to compare against.

Next: Step Size and Line Search