11. Gradient descent: calculus turned into an algorithm

§10.5 proved the gradient \nabla f points toward the steepest increase of a function, and §13.0 built Euler's method — repeated small steps following a local direction. This opening lesson of the module combines both ideas into the single algorithm underneath nearly all of modern machine learning: step repeatedly in the direction opposite the gradient, and a function's minimum comes within reach, even when §10.6's algebraic critical-point-finding is impossible because the function has thousands (or millions) of variables.

The algorithm

\vec x_{n+1}=\vec x_n-\alpha\nabla f(\vec x_n)

Starting from an initial guess \vec x_0, repeatedly step in the direction -\nabla f(\vec x_n) — the direction of steepest descent (§10.5's steepest-ascent result, negated) — scaled by a learning rate \alpha>0 controlling the step size.

This is Euler's method (§13.0), applied to the "flow" $\vec x'=-\nabla f(\vec x)$ — a differential equation whose solution curves always move toward lower values of f, discretized into fixed steps exactly the way Euler's method discretized any other differential equation. Just as Euler's method approximates a curve without solving the underlying differential equation in closed form, gradient descent approximates a minimum without ever solving \nabla f=\vec0 algebraically — which matters enormously once f depends on millions of variables (a neural network's weights), where §10.6's exact system is far too large to solve directly.

Why steepest descent, and why it works

At any point \vec x_n where \nabla f(\vec x_n)\ne\vec0, moving in the direction -\nabla f(\vec x_n) decreases f faster than moving in any other direction — the direct mirror of §10.5's steepest-ascent result, since the direction that increases f fastest is, by the same logic, exactly the direction that decreases f fastest when reversed. Taking a small enough step in that direction is therefore guaranteed to decrease f's value (this is exactly §10.3's linear approximation at work: for small \alpha, $f(\vec x_n-\alpha\nabla f)\approx f(\vec x_n)-\alpha|\nabla f(\vec x_n)|^2