Momentum and Acceleration

Vanilla gradient descent has a fundamental limitation: it's provably slow on ill-conditioned problems. When the loss surface is elongated (high condition number κ), gradient descent zig-zags back and forth, making painfully slow progress toward the optimum.

But what if we could remember our previous steps and build up velocity in consistent directions? This is exactly what momentum does. By incorporating a "memory" of past gradients, momentum methods can:

• Traverse flat directions faster
• Dampen oscillations in steep directions
• Achieve provably optimal convergence rates

Momentum is not just a heuristic—it's mathematically guaranteed to accelerate convergence. This page explores the theory and practice of momentum-based optimization.

Consider optimizing a quadratic with different curvatures along each axis:

$$J(\theta_1, \theta_2) = \frac{1}{2}(100\theta_1^2 + \theta_2^2)$$

This is an elongated ellipse with:

• High curvature (L = 100) along θ₁
• Low curvature (μ = 1) along θ₂
• Condition number κ = L/μ = 100

What happens with vanilla GD:

1. The gradient has a large component in the θ₁ direction (high curvature)
2. The learning rate is limited by θ₁: α ≤ 1/100 = 0.01
3. With this small α, progress in θ₂ is agonizingly slow
4. The trajectory zig-zags: overshooting in θ₁, crawling in θ₂

The fundamental issue: A single learning rate can't simultaneously:

• Take large steps in flat directions (θ₂ needs large α)
• Take small steps in steep directions (θ₁ needs small α)

Convergence rate reminder:

For L-smooth, μ-strongly convex functions, vanilla GD converges as: $$(1 - \mu/L)^t = (1 - 1/\kappa)^t$$

For κ = 100, each iteration reduces error by only 1%. To reduce error by 10⁶ requires: $$t \approx \kappa \ln(10^6) \approx 1,400 \text{ iterations}$$

Can we do better? Yes! With acceleration, we can achieve: $$(1 - 1/\sqrt{\kappa})^t$$

For κ = 100, this means only ~140 iterations—10× faster!

Classical momentum (also called Polyak momentum or heavy ball method) introduces a velocity vector that accumulates gradient information:

$$\mathbf{v}^{(t+1)} = \gamma \mathbf{v}^{(t)} + abla J(\boldsymbol{\theta}^{(t)})$$ $$\boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \alpha \mathbf{v}^{(t+1)}$$

where:

• $\mathbf{v}^{(t)}$ is the velocity (accumulated gradient direction)
• $\gamma \in [0, 1)$ is the momentum coefficient (typically 0.9)
• $\alpha$ is the learning rate

Interpretation:

The velocity $\mathbf{v}$ is an exponentially weighted moving average of gradients: $$\mathbf{v}^{(t)} = \sum_{k=0}^{t} \gamma^{t-k} abla J(\boldsymbol{\theta}^{(k)})$$

Recent gradients contribute more; older gradients decay exponentially with factor $\gamma$.

The physics analogy:

Imagine a ball rolling down a hilly landscape:

• Without momentum: The ball stops instantly when you stop pushing (friction = ∞)
• With momentum: The ball builds up velocity, coasting through small bumps

In optimization terms:

• Flat directions: Gradients are consistent → velocity builds up → faster progress
• Steep/oscillating directions: Gradients flip signs → velocity cancels out → dampened oscillation

Momentum acts as a low-pass filter on the gradients, smoothing out high-frequency oscillations while preserving the overall descent direction.

Nesterov momentum is a clever modification that provides provably optimal convergence rates. The key insight: compute the gradient at the "lookahead" position where momentum would take us, not at the current position.

Update equations:

$$\mathbf{v}^{(t+1)} = \gamma \mathbf{v}^{(t)} + abla J(\boldsymbol{\theta}^{(t)} - \alpha \gamma \mathbf{v}^{(t)})$$ $$\boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \alpha \mathbf{v}^{(t+1)}$$

Notice the gradient is evaluated at $\boldsymbol{\theta}^{(t)} - \alpha \gamma \mathbf{v}^{(t)}$, not $\boldsymbol{\theta}^{(t)}$.

Equivalent formulation (more practical):

$$\tilde{\boldsymbol{\theta}} = \boldsymbol{\theta}^{(t)} - \alpha \gamma \mathbf{v}^{(t)}$$ $$\mathbf{v}^{(t+1)} = \gamma \mathbf{v}^{(t)} + abla J(\tilde{\boldsymbol{\theta}})$$ $$\boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \alpha \mathbf{v}^{(t+1)}$$

Why lookahead helps:

Classical momentum computes the gradient at the current position, then applies momentum. This means we might accelerate in the wrong direction if the gradient is about to change.

Nesterov momentum asks: "If I'm going to move by momentum anyway, where will I end up? Let me compute the gradient there." This provides early correction:

• If we're about to overshoot, the lookahead gradient "sees" this
• The gradient at the lookahead position points back, slowing us down
• We course-correct before making the mistake, not after

The result: Nesterov momentum converges faster with less oscillation, especially near the optimum.

Let's understand why momentum provides acceleration through analysis of a simple quadratic.

Quadratic analysis:

Consider $J(\theta) = \frac{L}{2} \theta^2$. Vanilla GD with $\alpha = 1/L$: $$\theta^{(t+1)} = \theta^{(t)} - \frac{1}{L} \cdot L\theta^{(t)} = 0$$

One-step convergence! But with $\alpha = 1/(2L)$ (sub-optimal): $$\theta^{(t+1)} = (1 - 1/2) \theta^{(t)} = 0.5 \cdot \theta^{(t)}$$

Convergence rate is 0.5 per iteration.

Now add momentum (with $\gamma = 0.5$, $\alpha = 1/(2L)$):

The system becomes: $$\begin{pmatrix} \theta^{(t+1)} \ v^{(t+1)} \end{pmatrix} = \begin{pmatrix} 0.5 & -0.5/L \ L/2 & 0.5 \end{pmatrix} \begin{pmatrix} \theta^{(t)} \ v^{(t)} \end{pmatrix}$$

The eigenvalues of this matrix determine convergence. With proper tuning, they can be complex with modulus less than 1—producing spiraling convergence that's faster than pure contraction.

The acceleration mystery solved:

Why can momentum achieve $O(\sqrt{\kappa})$ while vanilla GD requires $O(\kappa)$?

Vanilla GD perspective: Limited by the steepest direction. Can only take steps of size $1/L$. Progress in flat direction is $(\mu/L) = 1/\kappa$ per step.

Momentum perspective: Accumulates velocity in flat direction while canceling oscillations in steep direction. Effectively takes larger steps in flat directions without destabilizing steep directions.

Mathematical intuition: Momentum transforms the optimization into a second-order dynamical system (position + velocity). This richer state space allows faster navigation of the geometry.

Optimal momentum coefficient for strongly convex problems: $$\gamma^* = \frac{\sqrt{L} - \sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}} = \frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}$$

For κ = 100: $\gamma^* \approx 0.82$. For κ = 10000: $\gamma^* \approx 0.98$.

Different frameworks implement momentum in slightly different (but equivalent) ways.

PyTorch-style (velocity accumulation):

v = gamma * v + gradient
theta = theta - learning_rate * v

TensorFlow-style (scaled velocity):

v = gamma * v + learning_rate * gradient
theta = theta - v

These are equivalent with appropriate parameter mapping. Be careful when porting code between frameworks!

Nesterov in PyTorch:

v = gamma * v + gradient
theta = theta - learning_rate * (gradient + gamma * v)

This "look-ahead" is applied differently but achieves the same effect.

Momentum introduces a new hyperparameter γ. How do we tune it effectively?

Typical values:

• γ = 0.9: The "standard" choice, works well in most cases
• γ = 0.99: More smoothing, useful for very noisy gradients
• γ = 0 to 0.5: For well-conditioned problems or when stability is priority

Learning rate interaction:

With momentum, you can often use a higher learning rate than vanilla GD:

• The effective step size is amplified by factor $\approx 1/(1-\gamma)$
• With γ = 0.9, steps are ~10× larger in consistent directions
• Reduce learning rate by ~10× when adding momentum, then tune

Momentum schedule:

Some practitioners use a momentum schedule:

1. Start with low momentum (γ = 0.5) for stability
2. Increase to high momentum (γ = 0.99) as training stabilizes

This provides aggressive exploration early and precise convergence late.

Momentum addresses part of the ill-conditioning problem by building velocity in flat directions. But it still uses a single learning rate for all parameters. Adaptive methods go further by maintaining per-parameter learning rates.

The key insight: Different parameters may need different step sizes. Weights connecting to frequently-active features see large gradients; weights to rare features see small gradients. A single learning rate can't serve both well.

Adam is particularly important—it's the default optimizer for most deep learning:

$$m_t = \beta_1 m_{t-1} + (1-\beta_1) g_t \quad \text{(momentum on gradients)}$$ $$v_t = \beta_2 v_{t-1} + (1-\beta_2) g_t^2 \quad \text{(momentum on squared gradients)}$$ $$\theta_{t+1} = \theta_t - \alpha \frac{\hat{m}_t}{\sqrt{\hat{v}_t} + \epsilon}$$

where $\hat{m}_t$ and $\hat{v}_t$ are bias-corrected estimates.

When to use what:

• SGD + momentum: Best final accuracy (if you can tune it)
• Adam: Easier to tune, good defaults, faster early progress
• AdamW: State-of-the-art for transformers (BERT, GPT, etc.)