Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 38 · Gradient Descent

Momentum and Accelerated Gradient

Speed up gradient descent with heavy-ball momentum and Nesterov acceleration. Implement both from scratch and compare iterations on ill-conditioned problems.

Plain gradient descent forgets the past: each step looks only at the current gradient. A rolling ball behaves differently. It builds up speed along a consistent slope and damps the sideways wobble. Momentum methods copy that physics, and on stretched valleys they can be dramatically faster. This lesson implements two classics: heavy-ball momentum and Nesterov's accelerated gradient.

Heavy-ball (Polyak) momentum

Keep a running "velocity" v that blends the previous direction with the new gradient:

Text
v_{k+1} = β · v_k - t · ∇f(x_k)
x_{k+1} = x_k + v_{k+1}

The momentum parameter β (often 0.9) controls how much of the past survives. If the gradient keeps pointing the same way, the velocity grows (up to a factor 1/(1 - β) of one step). If the gradient flips sign each step (zigzag across a valley), the contributions cancel out.

Python Heavy-ball momentum versus plain GD

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Momentum needs a small fraction of the plain iteration count. For quadratics, the best heavy-ball parameters are t = 4 / (√L + √μ)² and β = ((√κ - 1)/(√κ + 1))², which reduce the iteration count from about κ to about √κ. Those are theory-optimal values for quadratics; for general functions heavy ball can misbehave.

Nesterov's accelerated gradient

Nesterov made a small but powerful change: compute the gradient at a look-ahead point instead of the current one. One common form for convex L-smooth f:

Text
y_k     = x_k + ((k - 1)/(k + 2)) · (x_k - x_{k-1})
x_{k+1} = y_k - (1/L) · ∇f(y_k)

This simple rule achieves

Text
f(x_k) - f* ≤ 2L‖x₀ - x*‖² / (k + 1)²

an O(1/k²) rate instead of O(1/k). It is known to be optimal among methods that use only gradients, in the sense that no first-order method can beat O(1/k²) on this problem class in the worst case.

Python Nesterov versus gradient descent

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At equal step counts the accelerated gap is much smaller once enough steps are taken. The problem has condition number 1000, exactly the kind of valley where acceleration pays off. (At only 10 steps both are still far from the optimum.)

Nesterov's iterates are not monotone: the objective can go up for a few steps before dropping. If that bothers you, restart the momentum when the objective increases ("adaptive restart").

Visualizing momentum on a narrow valley

Python Paths of plain GD and momentum

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When to use which

Method Rate (smooth convex) Notes
Gradient descent O(1/k) simple, monotone
Heavy ball quadratics: √κ factor can fail on general convex
Nesterov O(1/k²) optimal first-order rate, needs L or backtracking

In practice, deep-learning libraries use momentum with β = 0.9 and a tuned learning rate; convex solvers prefer Nesterov-style accelerated schemes with restarts.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In heavy-ball momentum, the parameter β controls

    The velocity update is v ← βv - t∇f, so β is the fraction of the past retained.
  2. 2. Nesterov's method evaluates the gradient at

    The gradient is taken at y_k, which extrapolates along the last movement.
  3. 3. The worst-case rate of Nesterov's method on smooth convex functions is

    That is the accelerated rate, and it is optimal for first-order methods on this class.
  4. 4. Which statement is true about Nesterov's iterates?

    Acceleration is not monotone; restarts can be used if monotone behavior is wanted.

Summary

  • Momentum adds a velocity term that accumulates consistent directions and damps oscillations.
  • Heavy ball helps on ill-conditioned quadratics (about √κ instead of κ iterations).
  • Nesterov acceleration uses a look-ahead gradient and gives the optimal O(1/k²) rate for smooth convex problems.
  • Accelerated methods are not monotone; restarting can help.

Next: Lagrange Multipliers for Equality Constraints