Week 8: Adaptive First-Order Methods

One Learning Rate Doesn't Fit All#

In deep networks, different parameters have vastly different scales:

• Weights in early layers might have typical gradient magnitudes of $10^{-2}$
• Weights in later layers might have gradients of $10^{-5}$
• Embedding parameters for rare words get updated very infrequently (sparse gradients)

A single global learning rate $\eta$ cannot serve all parameters well. If $\eta$ is tuned for the fastest-changing parameters, the slow-changing ones barely move. If $\eta$ is large enough for the slow parameters, the fast ones oscillate or diverge.

Adaptive methods solve this by maintaining a per-parameter effective learning rate, automatically scaled by the historical magnitude of that parameter's gradient.

AdaGrad#

AdaGrad (Duchi et al., 2011) was the first widely-used adaptive method. It accumulates the squares of all past gradients:

$G_k = \sum_{t=1}^k g_t \odot g_t \quad \text{(elementwise square and sum)}$

$w_{k+1} = w_k - \frac{\eta}{\sqrt{G_k + \varepsilon}} \odot g_k$

where $\odot$ is elementwise multiplication and $\varepsilon = 10^{-8}$ prevents division by zero.

How it works: Parameters that have historically received large gradients get their effective learning rate divided by a large number (slowing them down). Parameters with historically small gradients get divided by a small number (speeding them up).

The failure mode: $G_k$ is monotonically increasing — it never forgets. In the limit $k \to \infty$, $G_k \to \infty$ and the effective learning rate $\eta/\sqrt{G_k}$ goes to zero for all parameters. Training stalls. This is why AdaGrad fell out of favour for deep learning.

RMSProp#

RMSProp (Tieleman & Hinton, 2012) fixes AdaGrad's accumulating-divisor problem by replacing the sum with an exponential moving average (EMA):

$v_k = \beta_2 \, v_{k-1} + (1 - \beta_2) \, g_k \odot g_k$

$w_{k+1} = w_k - \frac{\eta}{\sqrt{v_k + \varepsilon}} \odot g_k$

where $\beta_2 \in [0, 1)$ (typically $0.999$) controls the memory length. The EMA forgets old gradients — approximately the last $1/(1-\beta_2) \approx 1000$ steps influence $v_k$.

RMSProp maintains adaptivity (each parameter gets its own scale) without the monotonic-stall problem. It became the default in many frameworks before Adam took over.

Adam#

AdamAdaptive Moment Estimation (optimizer) (Kingma & Ba, 2015) combines the best of both worlds:

1. Momentum (Week 7) for the gradient direction: $m_k = \beta_1 m_{k-1} + (1-\beta_1) g_k$
2. RMSProp for per-parameter scaling: $v_k = \beta_2 v_{k-1} + (1-\beta_2) g_k \odot g_k$

The full Adam update:

$m_k = \beta_1 m_{k-1} + (1 - \beta_1) g_k$ $v_k = \beta_2 v_{k-1} + (1 - \beta_2) g_k \odot g_k$ $\hat m_k = \frac{m_k}{1 - \beta_1^k}, \quad \hat v_k = \frac{v_k}{1 - \beta_2^k} \quad \text{(bias correction)}$ $w_{k+1} = w_k - \frac{\eta}{\sqrt{\hat v_k} + \varepsilon} \odot \hat m_k$

Bias correction: At initialisation, $m_0 = 0$ and $v_0 = 0$. The EMA estimates start biased toward zero. Dividing by $1 - \beta^k$ corrects this — at $k=1$, $m_1/(1-\beta_1) = g_1$ exactly, and as $k \to \infty$ the correction factor approaches 1.

Standard hyperparameters:

• $\eta = 0.001$ (or $1 \times 10^{-3}$)
• $\beta_1 = 0.9$ (momentum decay)
• $\beta_2 = 0.999$ (RMSProp decay)
• $\varepsilon = 10^{-8}$

These defaults work remarkably well across a wide range of deep learning problems — one reason Adam became the de facto standard.

Practice Defaults and What Adaptivity Hides#

When Adam works well:

• Sparse gradients (embeddings, NLP)
• Non-stationary objectives (GANs, RL — though care is needed)
• Default choice when you don't want to tune $\eta$ extensively

When to fall back to SGD + momentum:

• When you need the best possible generalisation on a well-understood problem
• Computer vision benchmarks (where SGD + momentum with careful tuning often beats Adam)
• When theoretical convergence guarantees matter

What adaptivity hides: Adam's per-parameter scaling can mask poor conditioning, obscuring the diagnosis. The theoretical convergence guarantees for Adam are weaker than for SGD — under certain adversarial constructions, Adam can diverge even on convex problems. The $\beta_2$ parameter needs to be close enough to 1 for the RMSProp term to provide a stable denominator.

Browser lab#

Compare AdamAdaptive Moment Estimation (optimizer) vs SGD + momentum on a toy nonconvex 2D loss with an elongated valley. Plot iterate paths to visualise the adaptivity.

import numpy as np
import matplotlib.pyplot as plt

def f(w):
    x, y = w[0], w[1]
    return 0.5 * x**2 + 5.0 * y**2 + 2.0 * np.sin(x) * np.sin(y)

def grad(w):
    x, y = w[0], w[1]
    return np.array([x + 2.0 * np.cos(x) * np.sin(y),
                     10.0 * y + 2.0 * np.sin(x) * np.cos(y)])

def adam(w0, K, eta=0.1, beta1=0.9, beta2=0.999, eps=1e-8):
    w = w0.copy(); m = np.zeros(2); v = np.zeros(2)
    path = [w.copy()]; losses = [f(w)]
    for t in range(1, K+1):
        g = grad(w)
        m = beta1 * m + (1 - beta1) * g
        v = beta2 * v + (1 - beta2) * g**2
        m_hat = m / (1 - beta1**t)
        v_hat = v / (1 - beta2**t)
        w = w - eta * m_hat / (np.sqrt(v_hat) + eps)
        path.append(w.copy()); losses.append(f(w))
    return np.array(path), np.array(losses)

def sgd_momentum(w0, K, eta=0.05, beta=0.9):
    w = w0.copy(); v = np.zeros(2)
    path = [w.copy()]; losses = [f(w)]
    for _ in range(K):
        v = beta * v - eta * grad(w)
        w = w + v
        path.append(w.copy()); losses.append(f(w))
    return np.array(path), np.array(losses)

w0 = np.array([3.0, 2.0])
K = 150
path_adam, loss_adam = adam(w0, K)
path_sgd, loss_sgd = sgd_momentum(w0, K)

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 5))
ax1.plot(path_adam[:, 0], path_adam[:, 1], label="Adam", linewidth=1.5)
ax1.plot(path_sgd[:, 0], path_sgd[:, 1], label="SGD+momentum", linewidth=1.5)
ax1.plot(w0[0], w0[1], "ko", markersize=6, label="Start")
ax1.set_xlabel("w1"); ax1.set_ylabel("w2")
ax1.set_title("Iterate Paths"); ax1.legend()
ax2.plot(loss_adam, label="Adam"); ax2.plot(loss_sgd, label="SGD+momentum")
ax2.set_xlabel("Iteration"); ax2.set_ylabel("Loss")
ax2.set_title("Loss vs Iteration")
ax2.set_yscale("log"); ax2.legend(); ax2.grid(True, alpha=0.3)
plt.tight_layout(); plt.show()