Week 7: Momentum and Acceleration

Why momentum?#

Recall Week 4's ill-conditioned problem: $f(w) = \frac{1}{2}(w_1^2 + 100 w_2^2)$ with $\kappa = 100$. GD with $\eta = 1/L$ makes rapid progress along $w_1$ (steep direction) but crawls along $w_2$ (shallow direction). The iterates zigzag down a narrow valley.

Momentum fixes this by adding inertia. Instead of the gradient alone determining the step, a fraction of the previous step's direction is retained:

$v_{k+1} = \beta v_k - \eta \nabla f(w_k)$ $w_{k+1} = w_k + v_{k+1}$

where $v_k$ is the velocity and $\beta \in [0, 1)$ is the momentum coefficient.

The zigzag: oscillations in the steep direction cancel out when averaged over time, while progress in the shallow direction accumulates. The result is a smoother, faster trajectory.

Heavy-ball momentum#

The heavy-ball method (Polyak, 1964) is the classic momentum formulation:

$v_{k+1} = \beta v_k - \eta \nabla f(w_k)$ $w_{k+1} = w_k + v_{k+1}$

Unrolling the velocity update reveals it as an exponential moving average:

$v_{k+1} = -\eta \sum_{t=0}^k \beta^{k-t} \nabla f(w_t)$

Recent gradients have weight $\approx 1$, while gradients $m$ steps ago have weight $\beta^m$. The effective "memory" of momentum is roughly $1/(1-\beta)$ steps: with $\beta = 0.9$ about 10 steps, and with $\beta = 0.99$ about 100 steps.

Practical choices for $\beta$:

• $\beta = 0$: recovers plain GD/SGDStochastic Gradient Descent
• $\beta = 0.9$: standard setting, good for most problems
• $\beta = 0.99$: longer memory, useful when gradients are very noisy (SGD with small batch)
• $\beta = 0.999$: very long memory, used in Adam's first-moment estimate

Physical analogy: A ball rolling down a hill. The gradient is the slope (instantaneous force), momentum keeps the ball rolling in the direction it's already going. If the slope direction changes slowly, the ball accelerates; if it oscillates (zigzag valley), the oscillations cancel.

Interpreting momentum#

For a 1D quadratic $f(w) = \frac{a}{2} w^2$, the momentum iteration becomes a second-order linear recurrence:

$w_{k+1} = (1 + \beta - a\eta) w_k - \beta w_{k-1}$

The eigenvalues of this recurrence determine convergence. The optimal $\beta$ and $\eta$ for a quadratic with curvature $a$ are:

$\eta^* = \frac{4}{(\sqrt{L} + \sqrt{\mu})^2}, \quad \beta^* = \left(\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}\right)^2$

The resulting convergence factor is $\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}$, compared to $\frac{\kappa - 1}{\kappa + 1}$ for plain GD. For $\kappa = 100$, GD needs $\approx 200$ iterations for a constant-factor reduction; momentum needs $\approx 20$, a 10× speedup.

Nesterov accelerated gradient#

Nesterov (1983) proposed a subtle but important modification:

$\tilde w_k = w_k + \beta v_k$ $v_{k+1} = \beta v_k - \eta \nabla f(\tilde w_k)$ $w_{k+1} = w_k + v_{k+1}$

The difference is that the gradient is evaluated at $\tilde w_k = w_k + \beta v_k$, the point reached by continuing with the current velocity, instead of at the current position $w_k$. This "look-ahead" gradient provides a correction before we commit to the velocity direction.

For convex quadratics, Nesterov achieves the provably optimal convergence rate: $\mathcal{O}(1/k^2)$ for smooth convex (vs GD's $\mathcal{O}(1/k)$) and $\mathcal{O}(\sqrt{\kappa} \log(1/\varepsilon))$ for strongly convex.

In deep learning practice, the distinction between heavy-ball and Nesterov momentum is often minor. Both work well, and the choice is usually dictated by framework defaults.

Convergence benefit#

For a convex $L$-smooth function, Nesterov's accelerated gradient achieves:

$f(x_K) - f(x^*) \leq \frac{2L \|x_0 - x^*\|^2}{K^2}$

Compare to GD: $\frac{2L\|x_0 - x^*\|^2}{K}$. The acceleration improves the denominator from $K$ to $K^2$, a quadratic improvement in the number of iterations. To reach accuracy $\varepsilon$, GD needs $\mathcal{O}(1/\varepsilon)$ iterations; Nesterov needs $\mathcal{O}(1/\sqrt{\varepsilon})$.

When does momentum actually help?

• Ill-conditioned convex problems: large speedup
• Well-conditioned problems: little benefit (GD is already fast)
• Nonconvex problems (deep nets): empirical benefit from dampening oscillations and escaping shallow regions, though theoretical guarantees are weaker
• SGD with momentum: reduces variance in the update direction, acting as a variance-reduction technique alongside the adaptive step-size role

Knowledge check#

Browser lab: momentum vs Nesterov#

Compare GD, momentum, and Nesterov on an ill-conditioned 2D quadratic ($\kappa \approx 100$). Plot iterate trajectories and loss vs iteration.

import numpy as np
import matplotlib.pyplot as plt

Q = np.diag([100.0, 1.0])

def f(w): return 0.5 * (w @ Q @ w)
def grad(w): return Q @ w

L = 100.0; mu = 1.0
eta_gd = 1.0 / L
eta_mom = 4.0 / (np.sqrt(L) + np.sqrt(mu))**2
beta_mom = ((np.sqrt(L/mu) - 1) / (np.sqrt(L/mu) + 1))**2

w0 = np.array([0.5, 10.0])
K = 200

def run_gd(w0, K, eta):
    w = w0.copy(); path = [w.copy()]; losses = [f(w)]
    for _ in range(K):
        w = w - eta * grad(w)
        path.append(w.copy()); losses.append(f(w))
    return np.array(path), np.array(losses)

def run_momentum(w0, K, eta, beta, nesterov=False):
    w = w0.copy(); v = np.zeros(2)
    path = [w.copy()]; losses = [f(w)]
    for _ in range(K):
        if nesterov:
            g = grad(w + beta * v)
        else:
            g = grad(w)
        v = beta * v - eta * g
        w = w + v
        path.append(w.copy()); losses.append(f(w))
    return np.array(path), np.array(losses)

path_gd, loss_gd = run_gd(w0, K, eta_gd)
path_mom, loss_mom = run_momentum(w0, K, eta_mom, beta_mom, nesterov=False)
path_nes, loss_nes = run_momentum(w0, K, eta_mom, beta_mom, nesterov=True)

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 5))
ax1.plot(path_gd[:, 0], path_gd[:, 1], alpha=0.6, label="GD")
ax1.plot(path_mom[:, 0], path_mom[:, 1], alpha=0.6, label="Momentum")
ax1.plot(path_nes[:, 0], path_nes[:, 1], alpha=0.6, label="Nesterov")
ax1.plot(0, 0, "kx", markersize=8)
ax1.set_xlabel("w1"); ax1.set_ylabel("w2")
ax1.set_title("Iterate Paths"); ax1.legend()
ax2.semilogy(loss_gd, label="GD"); ax2.semilogy(loss_mom, label="Momentum")
ax2.semilogy(loss_nes, label="Nesterov")
ax2.set_xlabel("Iteration"); ax2.set_ylabel("Loss")
ax2.set_title("Loss vs Iteration"); ax2.legend(); ax2.grid(True, alpha=0.3)
plt.tight_layout(); plt.show()

print(f"Final loss  GD={loss_gd[-1]:.2e}  Momentum={loss_mom[-1]:.2e}  Nesterov={loss_nes[-1]:.2e}")
print("Notice: on this ill-conditioned problem (κ ≈ 100), momentum and Nesterov reach low loss in far fewer iterations than GD.")

Key takeaways#

• Heavy-ball momentum adds a velocity term, turning the update into an exponential moving average of past gradients with memory about $1/(1-\beta)$ steps.
• It damps oscillation in steep directions while accumulating progress in shallow ones, precisely the ill-conditioned zigzag from Week 4.
• For a quadratic, the right momentum changes the convergence factor from $(\kappa-1)/(\kappa+1)$ to $(\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)$: a $\sqrt{\kappa}$ speedup, about 10× at $\kappa = 100$.
• Nesterov evaluates the gradient at the look-ahead point $w_k + \beta v_k$ and achieves the optimal $\mathcal{O}(1/K^2)$ rate for smooth convex functions.
• In deep learning the heavy-ball versus Nesterov distinction is usually minor; momentum's real value is variance reduction and escape from shallow regions.
• Momentum is the first-moment component inside Adam.

Further reading#

• Boris T. Polyak, "Some methods of speeding up the convergence of iteration methods" (USSR Computational Mathematics and Mathematical Physics, 1964). The original heavy-ball method.
• Yurii Nesterov, "A method of solving a convex programming problem with convergence rate $O(1/k^2)$" (Soviet Mathematics Doklady, 1983). The accelerated gradient method and its optimal rate.
• Ilya Sutskever, James Martens, George Dahl & Geoffrey Hinton, "On the importance of initialization and momentum in deep learning" (ICML 2013). Momentum as it is actually used in deep networks.