Example: gradient descent, from intuition to implementation

Optimization often begins with a simple question: which direction makes an error smaller? Gradient descent turns that local question into a repeatable procedure.

Start with a landscape

For a differentiable objective $L(\theta)$, the gradient points in the direction of steepest local increase in Euclidean space. A small step in the opposite direction is a useful first approximation to improvement.

Here $\eta > 0$ is the learning rate. Choosing it is part of the algorithm, not an incidental implementation detail.

A minimal implementation

For $L(x)=x^2$, the derivative is $2x$. Start at $x=4$ and take ten steps:

def minimize(x: float, rate: float, steps: int) -> float:
    for _ in range(steps):
        gradient = 2 * x
        x -= rate * gradient
    return x

print(minimize(x=4.0, rate=0.2, steps=10))
# Approximately 0.0242

This is intentionally small enough to inspect by hand. Every iteration multiplies $x$ by $1-2\eta$. Convergence therefore requires $|1-2\eta|<1$, or $0<\eta<1$.

Explore the learning rate

The control below computes one step for the same quadratic. At the largest rate it oscillates rather than improving.

Know the assumptions

A useful algorithm can still fail when its assumptions change. Nonconvex losses have saddle points; noisy gradients change the trajectory; poorly scaled coordinates slow progress.

Measure the objective as well as the parameter update. A moving parameter is not evidence of a better model.

Further reading

Boyd and Vandenberghe’s Convex Optimization develops the mathematical background.¹ For an infrastructure perspective, read the static publishing example.