Kiru Lab  /  Classical Machine Learning  /  Learning From Data

Gradient Descent, By Hand

One update rule powers the whole field. Feel it on a surface you can see.

Hands-On Lab  ·  about 35 minutes

The update rule is one line: move each parameter a small distance opposite its gradient. Everything sophisticated in optimization — momentum, Adam, learning rate schedules — is an attempt to choose that small distance better.

w <- w - lr * grad_w Loss

The three flavors

  • Batch: compute the gradient over all data. Accurate, slow, and prone to settling in the nearest basin.
  • Stochastic: one example at a time. Noisy, fast, and the noise itself helps escape poor minima.
  • Mini-batch: a compromise, and what everyone actually uses. Batch size trades gradient noise against hardware utilization.
Watching descent on a visible surface
import numpy as np

# An ill-conditioned bowl: steep in one direction, shallow in the other.
A = np.array([[10.0, 0.0], [0.0, 1.0]])
loss = lambda p: 0.5 * p @ A @ p
grad = lambda p: A @ p

p = np.array([1.0, 1.0])
path = [p.copy()]
for _ in range(60):
    p = p - 0.09 * grad(p)
    path.append(p.copy())

# Plot `path` over a contour of `loss`. The zig-zag is the condition number,
# visible: 10:1 curvature ratio means the step size that is safe for the steep
# direction is far too small for the shallow one.

That zig-zag is why momentum exists. Momentum accumulates a running average of past gradients, which cancels the oscillating component and reinforces the consistent one. Adam goes further and keeps a per-parameter scale estimate, effectively giving each direction its own learning rate.

The same picture, later

When the robotics track shows a manipulator moving slowly and awkwardly near a singularity, it is this contour plot again: a direction in which the mapping is nearly flat, requiring enormous input for tiny output.

Hold on to

  • One update rule underlies every model in this curriculum
  • Batch size trades gradient noise against hardware efficiency
  • Momentum and Adam are responses to anisotropic curvature

Work through

Try each one before opening the solution. Getting it wrong first is most of where the learning happens.

  1. Reproduce the zig-zag plot, then add momentum and show the path straighten.
    Hint

    Momentum keeps a running velocity: v = beta*v + grad, then step along v.

    Solution

    Momentum cancels the oscillating component across the steep direction — successive gradients there point opposite ways and average out — while reinforcing the consistent component along the shallow one. The path visibly straightens and convergence is several times faster on the same learning rate.

    import numpy as np

A = np.array([[10.0, 0.0], [0.0, 1.0]])
grad = lambda p: A @ p

def descend(lr=0.09, beta=0.0, steps=60):
    p, v, path = np.array([1.0, 1.0]), np.zeros(2), []
    for _ in range(steps):
        v = beta * v + grad(p)
        p = p - lr * v
        path.append(p.copy())
    return np.array(path)

plain = descend(beta=0.0)
with_momentum = descend(beta=0.9, lr=0.02)
print(np.linalg.norm(plain[-1]), np.linalg.norm(with_momentum[-1]))
  2. Find the largest stable learning rate for the ill-conditioned bowl and relate it to the largest eigenvalue of A.
    Hint

    Gradient descent on a quadratic is stable when lr < 2 / largest eigenvalue.

    Solution

    The largest eigenvalue of A is 10, so the stability threshold is 2/10 = 0.2. Above that the steep direction diverges even though the shallow one would be perfectly happy with a much larger step. That mismatch — one learning rate serving two very different curvatures — is the entire motivation for adaptive optimizers.

    import numpy as np

A = np.array([[10.0, 0.0], [0.0, 1.0]])
print("threshold:", 2 / np.linalg.eigvalsh(A).max())   # 0.2

for lr in (0.15, 0.19, 0.21, 0.25):
    p = np.array([1.0, 1.0])
    for _ in range(100):
        p = p - lr * (A @ p)
    print(lr, np.linalg.norm(p))   # explodes above 0.2
    Check your work

    Paste this after your own code. If it runs without raising, you have it. 

    import numpy as np
assert abs(2 / np.linalg.eigvalsh(np.array([[10.0, 0.0], [0.0, 1.0]])).max() - 0.2) < 1e-9
print("ok")

In the Bio Mirror

Basal Ganglia and the Dopamine Signal

Sign in to track your progress through the lab.

← Linear Regression From Scratch Back to track →