Two Accelerations for First-Order Optimization: A Comparative Review of Heavy Ball and Nesterov Acceleration

This review compares Polyak’s heavy ball method and Nesterov’s accelerated gradient method through the precise claims supported by their analyses. Although both methods combine a gradient step with momentum, their guarantees depend on different function classes, recurrences, observables, and horizons. We derive the heavy ball characteristic roots and a finite-time bound from positive-definite quadratics; connect the strongly convex Nesterov recurrence to its estimate-sequence guarantee; and review performance estimation, integral quadratic constraints, Lyapunov functions, and low- and high-resolution continuous-time models. The numerical section reports objective errors and iteration counts on a quadratic ravine and two smooth strongly convex nonquadratic problems over three condition numbers. These experiments illustrate parameter–regime matching and the possible failure of quadratic-tuned heavy ball outside the quadratic class. The numerical results are presented separately from the worst-case theorems. Implementation mappings and a short discussion of stochastic momentum and adaptive methods connect the deterministic theory with machine-learning practice.