Skip to content

Lesson 31 · 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