Gradient Descent

An iterative optimisation algorithm that repeatedly moves in the direction of the negative gradient to find a local minimum of a loss function.

Gradient descent — following the negative gradient downhill

α=0.050

Definition

Gradient descent is an algorithm for finding the minimum of a function by repeatedly stepping in the direction of steepest decrease.

Starting at a point $x_0$ , the update rule is:

$x_{t+1} = x_t - \alpha \nabla f(x_t)$

where $\alpha > 0$ is the learning rate (step size). We subtract the gradient because the gradient points uphill — we want to go downhill.

The algorithm terminates when $\|\nabla f\|$ is near zero (a stationary point), or after a fixed number of steps.

Key properties

Each step moves in the direction that locally decreases $f$ the fastest, but only locally — it has no view of the global landscape
A fixed point of the update ( $\nabla f(x) = 0$ ) is a critical point, not necessarily a minimum
Convergence speed and stability both depend heavily on the learning rate $\alpha$
For convex functions, gradient descent (with a suitable step size) is guaranteed to converge to the global minimum

Common mistakes

Setting the learning rate too high: the algorithm can overshoot and diverge instead of converging
Assuming convergence means reaching a global minimum: on non-convex functions, gradient descent only guarantees reaching a stationary point — which could be a local minimum or, in high dimensions, a saddle point

Minimizing a parabola

$f(x) = x^2$ , so $f'(x) = 2x$ . Starting at $x_0 = 3$ , $\alpha = 0.1$ :

$x_1 = 3 - 0.1 \times 6 = 2.4$

$x_2 = 2.4 - 0.1 \times 4.8 = 1.92$

Each step is 80% of the previous value — the algorithm converges geometrically to 0.

Try it

For $f(x) = (x-5)^2$ , find the update rule and verify that the minimum is reached in one step if $\alpha = 0.5$ .

Solution

$f'(x) = 2(x-5)$ . Starting at $x_0$ :

$x_1 = x_0 - 0.5 \times 2(x_0 - 5) = x_0 - (x_0 - 5) = 5$ .

With $\alpha = 0.5$ on a perfect quadratic, gradient descent reaches the exact minimum in one step. This is a special property of quadratics; it doesn't hold for other functions.

Related concepts

Euler's Method Logistic Regression Newton's Method Regularization

View in full concept graph →