Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 38 ยท Proximal and Stochastic Methods

Momentum, Nesterov and Adam

See why plain gradient descent crawls in narrow valleys and how momentum, Nesterov acceleration and Adam fix it. Implement each one and race them on an ill-conditioned problem.

Gradient descent has a weakness: in a long, narrow valley, the gradient points mostly across the valley, not along it. The iterates zigzag from wall to wall and make slow progress toward the minimum. Three popular fixes keep the same cheap gradient step but add memory or per-coordinate scaling.

An ill-conditioned test problem

Consider the quadratic f(x) = ยฝ (xโ‚ยฒ + 100 xโ‚‚ยฒ). Its Hessian is diag(1, 100), so the curvature differs by a factor of 100 between directions. This ratio is the condition number ฮบ = L / ฮผ = 100 (largest over smallest curvature). The gradient is (xโ‚, 100 xโ‚‚).

Plain gradient descent must use a step t โ‰ค 1/L = 0.01 to be stable in the steep direction. In the shallow direction, each step then shrinks xโ‚ by only the factor 1 โˆ’ tยทฮผ = 0.99. Reaching f < 10โปโถ from (1, 1) takes hundreds of iterations.

Momentum (heavy ball)

Momentum keeps a running velocity v of past gradients, like a ball rolling downhill with inertia:

Text
v โ† ฮฒ v โˆ’ t โˆ‡f(x)
x โ† x + v

Gradients that keep pointing the same way build up speed; gradients that flip sign (the cross-valley zigzag) cancel out. A typical ฮฒ is 0.9. For a quadratic with curvatures between ฮผ and L, the best choice is t = 4 / (โˆšL + โˆšฮผ)ยฒ and ฮฒ = ((โˆšฮบ โˆ’ 1)/(โˆšฮบ + 1))ยฒ. The error then shrinks by about (โˆšฮบ โˆ’ 1)/(โˆšฮบ + 1) per step instead of (ฮบ โˆ’ 1)/(ฮบ + 1): a big gain when ฮบ is large.

Nesterov accelerated gradient

Nesterov's variant evaluates the gradient at the look-ahead point reached by the momentum step:

Text
y โ† x + ฮฒ (x โˆ’ x_prev)
x_prev โ† x
x โ† y โˆ’ t โˆ‡f(y)

For convex functions with L-Lipschitz gradient, this achieves the optimal O(1/kยฒ) rate for first-order methods; FISTA from the proximal gradient lesson is this idea plus a prox step. For strongly convex problems with t = 1/L, the constant choice ฮฒ = (โˆšฮบ โˆ’ 1)/(โˆšฮบ + 1) works.

Adam

Adam (Adaptive Moment Estimation) adds a second idea: scale each coordinate by the recent size of its gradient. It tracks two running averages:

Text
m โ† ฮฒโ‚ m + (1 โˆ’ ฮฒโ‚) g          (average of gradients)
s โ† ฮฒโ‚‚ s + (1 โˆ’ ฮฒโ‚‚) gยฒ         (average of squared gradients, elementwise)
mฬ‚ = m / (1 โˆ’ ฮฒโ‚แต),  ล = s / (1 โˆ’ ฮฒโ‚‚แต)      (bias correction at step k)
x โ† x โˆ’ ฮท ยท mฬ‚ / (โˆšล + ฮต)

Common defaults are ฮฒโ‚ = 0.9, ฮฒโ‚‚ = 0.999, ฮต = 10โปโธ. Dividing by โˆšล gives every coordinate a step of about size ฮท regardless of its gradient scale, which helps when features have very different scales. Adam is the default for training neural networks. For well-behaved convex problems it can wander or settle slightly off the exact minimum with a constant ฮท, so it needs a decaying ฮท for high accuracy.

Racing the methods

Each method below runs from (1, 1) and counts the iterations needed to reach f(x) < 10โปโถ (stopping at 5,000).

Python Gradient descent, momentum, Nesterov and Adam

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.

Plain gradient descent needs 653 iterations, while heavy ball (69), Nesterov (84) and Adam (82) need roughly an eighth as many. The ranking depends on the problem and on your settings: the momentum methods here are tuned with the known L and ฮผ, whereas Adam needs no such knowledge.

Watching the paths

The next example records the first few iterates, so you can see the zigzag in gradient descent and the smoother path with momentum. We print the distance from the minimum x = (0, 0) at several iteration counts.

Python Distance to the minimum over time

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 methods are not monotone: the objective can go up for a step before falling. That is expected, and it is why momentum can beat the best monotone method.

Practical advice

  • Start with plain SGD plus momentum 0.9 for convex or well-scaled problems; start with Adam (ฮท around 0.001) for neural networks.
  • If the loss explodes, lower the step size first.
  • Scale or standardize features before using non-adaptive methods; it reduces the condition number.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the condition number ฮบ = L/ฮผ measure?

    A large ฮบ means a long, narrow valley, the situation in which plain gradient descent is slow.
  2. 2. How does Nesterov's method differ from heavy-ball momentum?

    Nesterov's gradient is taken after the momentum move, which gives the optimal rate for smooth convex problems.
  3. 3. What does Adam divide each coordinate's step by?

    That normalization gives every coordinate a step of comparable size even when gradient scales differ greatly.
  4. 4. Why does heavy-ball momentum reduce zigzagging?

    The velocity averages past gradients: oscillating parts cancel, steady parts build up.

Summary

  • Ill-conditioned problems (ฮบ large) make gradient descent slow because of cross-valley zigzag.
  • Momentum adds a velocity; Nesterov evaluates the gradient at a look-ahead point and gives the O(1/kยฒ) rate for smooth convex problems.
  • Adam rescales each coordinate by a running average of squared gradients and is the standard for neural networks.
  • Results depend on tuning; compare methods on your own problem before choosing.

Next: Ridge Regression as an Optimization Problem