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\):
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:
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\):
Both averages start at zero, so early values are too small. Adam divides by a correction factor:
The update divides by the root of the squared-gradient average. A tiny constant \(\delta\) prevents division by zero:
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
- Ian Goodfellow, Yoshua Bengio, and Aaron Courville, Deep Learning, Chapter 4: Numerical Computation, section 4.3
- Ian Goodfellow, Yoshua Bengio, and Aaron Courville, Deep Learning, Chapter 8: Optimization for Training Deep Models, sections 8.3 and 8.5
- Diederik P. Kingma and Jimmy Ba, Adam: A Method for Stochastic Optimization, 2014
Cards
What is the gradient descent update for a parameter \(\theta\) with learning rate \(\epsilon\)?
Reveal
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
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.