← module 11 · optimizers: momentum, rmsprop, adam, adamw
paywalled

Some Methods of Speeding up the Convergence of Iteration Methods

Boris T. Polyak

USSR Computational Mathematics and Mathematical Physics 4(5):1-17 (English translation); Zh. Vychisl. Mat. Mat. Fiz. 4(5):791-803 (Russian original)

about this write-up

The English translation is paywalled; the Russian original is listed on Math-Net.ru (https://www.mathnet.ru/eng/zvmmf7713). This write-up is from secondary sources and standard optimisation texts, not from a reading of the original.

the original →

the problem

Gradient descent is slow on a surface that's much steeper in one direction than another (a long narrow valley). The step must be small enough for the steep direction, so progress along the gentle direction crawls. The ratio of steepest to gentlest curvature is called the condition number, κ.

the idea: add inertia

Polyak studied updates that use the previous step as well as the current gradient. The best known is the heavy ball:

xk+1=xk−α∇f(xk)+β(xk−xk−1)x_{k+1} = x_k - \alpha \nabla f(x_k) + \beta (x_k - x_{k-1})

Picture a heavy ball rolling downhill. Its momentum carries it along directions that stay the same and damps the back-and-forth across the valley.

the result

With the step size and momentum tuned to the surface, the error shrinks each step by about (√κ − 1)/(√κ + 1), instead of (κ − 1)/(κ + 1) for plain gradient descent. κ becomes √κ. For a valley 100 times steeper one way, that's roughly 10 times fewer steps.

This guarantee holds near the bottom of smooth, bowl-shaped surfaces. For general surfaces the heavy ball has weaker guarantees, which was one reason Nesterov later designed his variant.

in deep learning

"SGD with momentum" is the heavy ball written with a velocity: v ← μv − η∇f, w ← w + v. Sutskever and colleagues later showed that momentum, especially Nesterov's version, with a good start trains deep networks well.

in this repo

  • SGD(lr, momentum=μ) is the heavy ball; nesterov=True gives Nesterov's version.
  • In the optimisers demo, on a valley 100 times steeper one way, Polyak's settings need 81 steps where the best plain gradient descent needs 559. The measured speed (0.8210 per step) matches the theory (0.8182).