Gradient Descent

machine-learning optimisation calculus

Definition

Gradient Descent

Gradient descent is a first-order gradient-based optimisation algorithm for minimising a differentiable objective $f:{\mathbb{R}}^d\to \mathbb{R}$. Starting from an initial parameter vector ${\theta }_0\in {\mathbb{R}}^d$, it repeatedly moves in the negative gradient direction:

$${\theta }_{t+1}={\theta }_t-{\eta }_t\nabla f({\theta }_t),$$

where ${\eta }_t>0$ is the learning rate. Since $\nabla f({\theta }_t)$ points in the direction of steepest local increase, the vector $-\nabla f({\theta }_t)$ points in the direction of steepest local decrease. In machine learning, $f$ is usually a loss function over model parameters.

Principle

The update is forced by the first-order local model of the objective. Near $\theta$, differentiability gives

$$f(\theta +d)\approx f(\theta )+\nabla f(\theta {)}^{\top }d.$$

To make this approximation smaller, choose $d$ with negative inner product against the gradient. The steepest such direction under the Euclidean norm is the negative gradient direction. The learning rate then decides how far to trust that local information.

A useful equivalent view is that gradient descent chooses the step $d_t$ that minimises a linear approximation of $f$ plus a quadratic penalty for moving too far:

$$d_t=\arg \underset{d}{\min }\left\{\nabla f({\theta }_t{)}^{\top }d+\frac{1}{2{\eta }_t}\Vert d{\Vert }_2^2\right\}=-{\eta }_t\nabla f({\theta }_t).$$

Thus the algorithm is local: it trusts the current slope, but only within a radius controlled by ${\eta }_t$.

Algorithm

Gradient descent

Given a differentiable objective $f$, an initial point ${\theta }_0$, and learning rates ${\eta }_t>0$:

1. compute the gradient $g_t=\nabla f({\theta }_t)$;
2. take the step ${\theta }_{t+1}={\theta }_t-{\eta }_t{g}_t$;
3. stop when the gradient, parameter change, or objective decrease is sufficiently small.

For empirical risk minimisation, full gradient descent computes the gradient using the whole training set at every step. stochastic gradient descent replaces this with a noisy gradient estimate from one example or a mini-batch.

Step size

The learning rate is the main control parameter.

• If ${\eta }_t$ is too small, descent is stable but slow.
• If ${\eta }_t$ is too large, the method can overshoot, oscillate, or diverge.
• If ${\eta }_t$ decreases over time, early steps can move quickly while later steps refine the solution.

For an $L$-smooth objective, the standard descent bound is

$$f({\theta }_{t+1})\le f({\theta }_t)-{\eta }_t\left(1-\frac{L{\eta }_t}{2}\right)\Vert \nabla f({\theta }_t){\Vert }_2^2.$$

So any fixed $0<{\eta }_t<2/L$ guarantees a decrease whenever $\nabla f({\theta }_t)\ne 0$. The formula expresses the basic trade-off: the step should be large enough to use the slope, but not so large that the local linear picture becomes false.

Guarantees and limitations

For a convex function, every local minimum is global, so gradient descent can converge to a global minimiser under suitable smoothness and step-size assumptions. For a non-convex objective, the same update may converge to a local minimum, a saddle point, or a flat region.

Gradient descent also depends on scaling. If different coordinates of $\theta$ have very different curvature, the method may zig-zag through narrow valleys. Adaptive methods and second-order methods modify the step geometry; plain gradient descent uses the same Euclidean geometry in every coordinate.