Gradient descent

Gradient descent

Backpropagation gives the gradient of the loss with respect to every parameter. An optimizer uses those gradients to change the parameters so the loss falls. This note covers plain gradient descent and two popular upgrades, momentum and Adam.

Gradient descent

The gradient points in the direction where the loss rises fastest. Gradient descent steps the other way. For a parameter \(\theta\) with learning rate \(\epsilon\):

\[ \theta \leftarrow \theta - \epsilon \, \nabla_\theta J(\theta) \]

Worked example

Let \(\theta = 2\), \(\nabla_\theta J = 3\), and \(\epsilon = 0.1\). Then \(\theta\) becomes \(2 - 0.1(3) = 1.7\). The parameter moved against the gradient.

The learning rate sets the step size. A rate that is too small makes training slow. A rate that is too large makes the loss jump around or grow.

Stochastic gradient descent

The exact gradient of the cost uses every training example. Stochastic gradient descent, or SGD, estimates it from a small random batch of examples, called a minibatch. Each step is cheaper and a little noisy. Over many steps the noise averages out.

Worked example

One minibatch gives \(g = 4\). With \(\theta = 2\) and \(\epsilon = 0.05\), the step gives \(\theta = 2 - 0.05(4) = 1.8\). The next minibatch gives a different \(g\).

Momentum

Momentum keeps a velocity \(v\) that remembers past gradients. The decay factor \(\alpha\), between \(0\) and \(1\), sets how long it remembers:

\[ v \leftarrow \alpha v - \epsilon g, \qquad \theta \leftarrow \theta + v \]

Steps that agree build up speed. Steps that flip back and forth cancel out.

Worked example

Start with \(\theta = 2\), \(v = 0\), \(\alpha = 0.9\), \(\epsilon = 0.1\), and \(g = 3\) on every step.

  • Step 1: \(v = 0 - 0.3 = -0.3\), so \(\theta = 1.7\).
  • Step 2: \(v = 0.9(-0.3) - 0.3 = -0.57\), so \(\theta = 1.13\).

The second step is larger than the first because it carries the first step's velocity.

Adam

Adam keeps two running averages for each parameter: \(s\) for the gradient and \(r\) for the squared gradient. With decay rates \(\rho_1\) and \(\rho_2\) and step count \(t\):

\[ s \leftarrow \rho_1 s + (1 - \rho_1) g, \qquad r \leftarrow \rho_2 r + (1 - \rho_2) g^2 \]

Both averages start at zero, so early values are too small. Adam divides by a correction factor:

\[ \hat{s} = \frac{s}{1 - \rho_1^t}, \qquad \hat{r} = \frac{r}{1 - \rho_2^t} \]

The update divides by the root of the squared-gradient average. A tiny constant \(\delta\) prevents division by zero:

\[ \theta \leftarrow \theta - \epsilon \, \frac{\hat{s}}{\sqrt{\hat{r}} + \delta} \]

Each parameter gets its own effective step size. A parameter with large gradients takes smaller steps, and one with small gradients takes larger steps.

Worked example

On the first step, let \(g = 2\), \(\rho_1 = 0.9\), and \(\rho_2 = 0.999\). Then \(s = 0.2\) and \(r = 0.004\). The corrections give \(\hat{s} = 0.2 / 0.1 = 2\) and \(\hat{r} = 0.004 / 0.001 = 4\). The step direction is \(2 / \sqrt{4} = 1\), so the first step moves \(\theta\) by about \(\epsilon\).

Optimizer state

The values an optimizer stores between steps are its state.

Optimizer State per parameter Shared state
Gradient descent none none
Momentum velocity \(v\) none
Adam averages \(s\) and \(r\) step count \(t\)

A network with 3 parameters needs 3 velocities with momentum. With Adam it needs 3 values of \(s\), 3 values of \(r\), and one step count.

In Python

This code minimizes \(J(\theta) = (\theta - 3)^2\), whose gradient is \(2(\theta - 3)\). Each optimizer starts at \(\theta = 0\) and takes 50 steps.

import math


def grad(theta):
    return 2 * (theta - 3)


def gradient_descent(steps=50, rate=0.1):
    theta = 0.0
    for _ in range(steps):
        theta -= rate * grad(theta)
    return theta


def momentum(steps=50, rate=0.1, alpha=0.5):
    theta, v = 0.0, 0.0
    for _ in range(steps):
        v = alpha * v - rate * grad(theta)
        theta += v
    return theta


def adam(steps=50, rate=0.3, rho1=0.9, rho2=0.999, delta=1e-8):
    theta, s, r = 0.0, 0.0, 0.0
    for t in range(1, steps + 1):
        g = grad(theta)
        s = rho1 * s + (1 - rho1) * g
        r = rho2 * r + (1 - rho2) * g * g
        s_hat = s / (1 - rho1**t)
        r_hat = r / (1 - rho2**t)
        theta -= rate * s_hat / (math.sqrt(r_hat) + delta)
    return theta


print(f"gradient descent {gradient_descent():.4f}")
print(f"momentum         {momentum():.4f}")
print(f"Adam             {adam():.4f}")

All three end near the minimum at \(\theta = 3\). On this simple bowl, Adam circles the minimum for a while before it settles. Adam helps most when different parameters have gradients of very different sizes, as in large networks.

Sources


Cards

What is the gradient descent update for a parameter \(\theta\) with learning rate \(\epsilon\)?

Reveal
\[ \theta \leftarrow \theta - \epsilon \, \nabla_\theta J(\theta) \]

The parameter moves against the gradient of the cost.

Apply one gradient descent step with \(\theta = 5\), \(\nabla_\theta J = -2\), and \(\epsilon = 0.25\).

Reveal

\(\theta = 5 - 0.25(-2) = 5.5\).

What goes wrong when the learning rate is too large?

Reveal

The steps overshoot the minimum, so the loss jumps around or grows.

How does stochastic gradient descent estimate the gradient?

Reveal

From a small random batch of training examples, called a minibatch. Each step is cheaper and a little noisy.

What are the momentum update equations?

Reveal
\[ v \leftarrow \alpha v - \epsilon g, \qquad \theta \leftarrow \theta + v \]

The velocity \(v\) remembers past gradients, and \(\alpha\) sets how long it remembers.

With momentum, start at \(\theta = 1\) and \(v = 0\), with \(\alpha = 0.8\), \(\epsilon = 0.1\), and \(g = 2\). What are \(v\) and \(\theta\) after one step?

Reveal

\(v = 0.8(0) - 0.1(2) = -0.2\), so \(\theta = 1 - 0.2 = 0.8\).

What two running averages does Adam keep for each parameter?

Reveal

An average \(s\) of the gradient and an average \(r\) of the squared gradient. Both decay over time and are bias-corrected before each update.

Why does Adam bias-correct its running averages?

Reveal

Both averages start at zero, so their early values are too small. Dividing by \(1 - \rho^t\) scales them back up during the first steps.

What state does each optimizer store per parameter?

Reveal

Plain gradient descent stores nothing. Momentum stores one velocity. Adam stores two averages, \(s\) and \(r\), plus one shared step count.