Machine Learning & Statistical Data Analysis

Imagine you’re hiking down into a valley wrapped in thick fog. You can’t see the bottom, you can’t see ten metres ahead — but you can feel the slope of the ground under your boots. So you do the only sensible thing: turn to face whichever way is steepest downhill, take a step, and repeat. Eventually, if the valley is well-behaved, you reach the lowest point. That is gradient descent. The whole algorithm. Every other detail is figuring out how big the step should be, and what to do when the terrain misbehaves.

To turn that picture into maths, you need three things. The terrain is the loss function $L(x,y)$L(x, y) — every point in the plane has a height, and we want the lowest. The slope under your feet is the gradient $\nabla L$\nabla L — it points in the direction of steepest increase, so the negative gradient points downhill. And the learning rate $\eta$\eta sets how big a step you take. The update is one line:

Let’s do one step by hand on the simplest surface. The Bowl is $L(x,y)=x^2+y^2$L(x, y) = x^2 + y^2, shaped like the inside of a salad bowl with its minimum at the origin. Its gradient is $\nabla L=(2x,2y)$\nabla L = (2x, 2y). Start at (2.5, 1.8); the gradient there is (5.0, 3.6). With $\eta =0.05$\eta = 0.05 the update subtracts 0.05·(5.0, 3.6) = (0.25, 0.18). Your new position is (2.25, 1.62). The loss dropped from 9.49 to 7.69. One step closer to the bottom.

Repeat that update and the trajectory walks straight into (0, 0). On a bowl the negative gradient always points roughly toward the centre, so every step gets you closer. Load the Bowl (vanilla) preset and watch the green dot do exactly this — it slows down as it approaches the minimum because the gradient itself shrinks. Near the bottom the slope is gentle, so the steps shrink in proportion and the iterates settle in.

The single most important knob is $\eta$\eta. Drag the Learning rate slider on the Bowl preset. At $\eta =0.001$\eta = 0.001 the dot crawls — each step is so timid it barely moves. At $\eta =0.05$\eta = 0.05 it lands neatly. Past about $\eta =0.5$\eta = 0.5 the step is so long it overshoots the bottom and lands on the opposite wall of the bowl, higher than it started. Crank it further and every step is longer than the last; the iterates fling off to infinity.

Vanilla gradient descent treats each step independently — every iteration restarts from rest. Momentum keeps a running velocity $v$v that the gradient nudges, with coefficient $\beta$\beta recycling the previous velocity:

A consistent downhill direction builds speed; transient zig-zags cancel. Compare Bowl (vanilla) ($\beta =0$\beta = 0) with Bowl (momentum) ($\beta =0.9$\beta = 0.9) — momentum reaches the minimum in roughly a quarter of the steps.

Where momentum really pays off: load the Rosenbrock valley preset. The surface is a narrow, curving canyon with the minimum at (1, 1). The gradient mostly points across the canyon walls — there’s barely any slope along the long axis. Vanilla GD bounces wall-to-wall and crawls toward the minimum at a snail’s pace. Momentum lets the long-axis component build up while the cross-wall oscillations cancel themselves out, so the dot threads the canyon at speed.

The other failure modes are on display in the remaining presets. Saddle escape drops you near a saddle point where the gradient is almost zero — vanilla GD stalls there indefinitely; momentum eventually drifts off the ridge. Vanishing plateau is the deep-learning nightmare: far from the minimum the gradient shrinks to almost nothing, so each step is tiny no matter what $\eta$\eta you pick. Cranking the learning rate or adding momentum is what unsticks you.

Try it yourself.

This same update is the engine underneath almost every model on this page. The polynomial regression demo below fits its coefficients by gradient descent on a least-squares loss, and the K-means image compression demo runs an analogous alternating minimisation that descends a clustering objective at each pass. The Featured Solution Gradient descent convergence for an L²-regularised quadratic makes the η story from step 5 precise — it proves the sharp bound on how large the learning rate can be before the iterates bounce instead of converging, and generalises everything you just watched to any convex quadratic.

Open a JPEG of a sunset on your phone and the file claims it uses thousands of distinct colours — sweeping oranges, pinks, dusty purples, near-blacks in the corners. Your eye can’t actually distinguish most of them. Now imagine you’re only allowed to keep sixteen colours, and you have to snap every pixel to whichever of those sixteen it most resembles. Pick the sixteen well and the image still looks like a sunset; pick them badly and it looks like paint-by-numbers. K-means is the algorithm that picks them well — automatically, from the image itself.

Strip the image away and start with six dots scattered on a page. We want two groups; that’s it. Drop two markers anywhere — call them seeds. Walk to each dot in turn, ask which seed it is closer to, and colour the dot to match. You’ve made a first guess at the clustering.

Now slide each seed to the average position of the dots wearing its colour — its new centre of gravity. Some dots are suddenly closer to the other seed than the one they’re wearing, so reassign them. Recompute the two centres again. Repeat. After a handful of rounds nothing changes — the seeds and the colourings stop moving and the clustering has settled.

That assign-then-update loop is the whole algorithm. There’s no derivative, no learning rate, no gradient. Each iteration does two cheap things — relabel every point, then recompute every centre — and the structure emerges from repetition alone. It’s the simplest non-trivial unsupervised method in the toolkit.

What is the loop actually optimising? Call $x_i$x_i a data point and ${\mu }_{c(i)}$\mu_{c(i)} the centre of the cluster it currently belongs to. Then the quantity we drive down is the within-cluster sum of squares $J={\sum }_i\Vert x_i-{\mu }_{c(i)}{\Vert }^2$J = \sum_i \|x_i - \mu_{c(i)}\|^2, sometimes called the inertia — total squared distance from every point to its own centre.

Here is the aha: the loop is coordinate descent on $J$J. The assignment step holds the centres fixed and picks the labels that minimise $J$J — each point picks its nearest centre, by definition the smallest contribution. The update step holds the labels fixed and picks the centres that minimise $J$J — the mean is provably the point that minimises sum of squared distances to a set. Neither step can ever increase $J$J, so the algorithm always converges.

Converges, yes — but not always to the best clustering. The loop is greedy and gets stuck at whichever local minimum of $J$J the initial seeds happen to fall into. Drop two seeds into the same dense blob and one cluster will starve while the other does all the work. k-means++ fixes most of this by spreading the seeds out — each new seed is sampled with probability proportional to its squared distance from the closest seed already chosen.

Now snap back to the image. Each pixel is a point in 3D RGB space — red, green, blue all between 0 and 255 — so a photo with thousands of unique colours is just thousands of points in a cube. K-means with $K=16$K = 16 hunts for the sixteen points in that cube whose neighbourhoods cover the colours best, then every pixel is recoloured to its nearest cluster centre. That is the entire compression.

Try it yourself.

This assign-then-update structure is more familiar than it looks. The gradient descent demo at the top of the page is coordinate descent in disguise once you fix the step size, and the polynomial regression demo next door is yet another loop that optimises a sum of squared distances — just with a parameter vector instead of a label per point. The same picture keeps recurring across the course: define an objective, alternate the variables you minimise over, and watch it converge.