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:
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=Truegives 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).