Gradient Descent: The Optimization Algorithm Behind Machine Learning

Calculus & Optimization

Chapter 6 · Gradient Descent: The Optimization Algorithm Behind Machine Learning

Chapter 5 proved the negative gradient points toward steepest decrease. This chapter turns that single geometric fact into a repeatable algorithm — the literal procedure that trains linear regression, logistic regression, and every deep neural network in production use.

The Algorithm

Gradient descent, in full

Start at some point. Repeat: compute the gradient there; move a small step in the negative gradient direction — x_new = x_old − α·∇f(x_old), where α (the learning rate) controls the step size. Stop when the gradient is close enough to zero, or after a fixed number of steps.

A Fully Traced, Verified Minimization

Minimizing f(x,y) = (x−3)² + (y+1)² + 5 — true minimum at (3,−1), value 5 — starting from (0,0), learning rate α=0.1:

Verified directly

iter 0: (0,0), f=15.0 → iter 1: (0.6,−0.2), f=11.4 → iter 2: (1.08,−0.36), f=9.096 → iter 5: (2.017,−0.672), f=6.074 → iter 9: (2.597,−0.866), f=5.180 — steadily, monotonically approaching the true minimum. After 50 iterations: (2.999957, −0.999986), f=5.00000000 — converged.

The Learning Rate: Five Regimes, All Verified

The same starting point, the same function, five different learning rates — the outcome changes completely.

Learning rate	What happens
α=0.1 (above)	Smooth, monotonic convergence to the minimum
α=0.5	Converges to the exact minimum in a single step
α=1.0	Oscillates forever between two points, never converging or diverging
α=1.1	Genuinely diverges — cost grows every iteration
α=1.5	Diverges explosively — cost roughly quadruples every iteration

Verified directly — α=0.5, the single-step-optimal rate for this function

Starting at (0,0): after exactly one step, (x,y) = (3.0, −1.0), f=5.0 — the exact true minimum, reached immediately, and stable there forever after.

Verified directly — α=1.0, the exact oscillation boundary

(0,0) → (6,−2) → (0,0) → (6,−2) → (0,0) → (6,−2), forever — f stuck at exactly 15.0 on every single iteration, neither improving nor getting worse.

Verified directly — α=1.1 and α=1.5, genuine divergence

At α=1.1: f climbs 15.0 → 19.4 → 25.7 → 34.9 → 48.0 → 66.9 → 94.2 → 133.4. At α=1.5: f climbs 15.0 → 45.0 → 165.0 → 645.0 → 2565.0 → 10245.0 — roughly quadrupling every step, a genuine runaway.

Why: the Exact Convergence Threshold

For this specific function, each gradient descent step is a simple linear update: x_new = x·(1−2α) + 6α. Whether this converges depends entirely on |1−2α|.

Verified directly, exactly matching every regime observed above

α=0.1: |1−0.2|=0.8 < 1 — converges. α=0.5: |1−1|=0 exactly — the fastest possible convergence, a single step. α=1.0: |1−2|=1 exactly — the precise oscillation boundary. α=1.1: |1−2.2|=1.2 > 1 — diverges. α=1.5: |1−3|=2 > 1 — diverges roughly twice as fast, matching the observed near-quadrupling (each step's error multiplies by 2, and cost grows with the square of the distance from the minimum).

Why this matters beyond this one example

Every real function has its own version of this threshold, tied to how sharply it curves — this is exactly why choosing a learning rate is a genuinely important, non-trivial part of training any real model, not an arbitrary setting.

Gradient Descent in Code

def f(x, y): return (x-3)**2 + (y+1)**2 + 5
def gradient(x, y): return (2*(x-3), 2*(y+1))

def gradient_descent(x, y, lr, iterations):
    for _ in range(iterations):
        gx, gy = gradient(x, y)
        x, y = x - lr*gx, y - lr*gy   # step in the NEGATIVE gradient direction
    return x, y

print(gradient_descent(0, 0, 0.1, 50))   # (2.999957, -0.999986) -- converged
print(gradient_descent(0, 0, 0.5, 1))    # (3.0, -1.0) -- exact, one step

Hands-On Exercises

Exercise 1

For f(x) = (x−5)², run one step of gradient descent starting at x=0 with learning rate α=0.2, showing the gradient computed and the resulting new x value.

📄 View solution

Exercise 2

Using this chapter's own convergence-threshold reasoning (|1−2α|) applied to f(x)=(x−5)², what learning rate would reach the exact minimum in a single step, starting from any point? Verify your answer by running one step of gradient descent from x=0 with that learning rate.

📄 View solution

Exercise 3

A colleague sets a learning rate of α=1.05 for training a model and says "it's close enough to 1, it should be fine." Using this chapter's own verified findings about α=1.0 and α=1.1, explain specifically why this reasoning is dangerous, even though 1.05 genuinely is close to 1.0.

📄 View solution

Chapter 6 Quick Reference

Gradient descent: x_new = x_old − α·∇f(x_old), repeated until the gradient is near zero
Verified: 50 iterations at α=0.1 converge to within 0.00005 of the true minimum
Learning rate genuinely changes the outcome: too small is just slow, but too large causes real, verified divergence — not merely inefficiency
An exact convergence threshold exists per function (|1−2α|<1 for this chapter's own quadratic) — α=1.0 is the precise boundary, verified to oscillate forever rather than converge or diverge
A well-chosen learning rate can converge in a single step for a simple quadratic — verified directly at α=0.5
Next chapter: Convexity, local vs. global minima, and optimization landscapes