Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration
This work provides a theoretical understanding of classical momentum in stochastic mini-batch optimization for deep learning practitioners, addressing a known gap in theory.
The paper develops a theory of stochastic momentum acceleration for optimization over quadratics in the interpolation regime, showing that acceleration from classical momentum is directly proportional to mini-batch size, enabling perfect parallelization. The theory provides a simple momentum parameter choice that is empirically effective.
Accelerating stochastic gradient methods with classical momentum schemes, such as Polyak's heavy ball, has proven highly successful in training large-scale machine learning models, particularly when combined with the hardware acceleration of large mini-batch computations. Yet, the effect of classical momentum on stochastic mini-batch optimization has been poorly understood theoretically, with prior works requiring strong noise assumptions and extremely large mini-batches. In this work, we develop a general theory of stochastic momentum acceleration for optimizing over quadratics in the interpolation regime, a popular abstraction for studying deep learning dynamics which also includes classical methods such as randomized Kaczmarz and coordinate descent. Our framework encompasses both heavy ball and Nesterov-style momentum, allows for arbitrary mini-batch sizes, and makes minimal assumptions on the stochastic noise. In particular, we show that acceleration from classical momentum is directly proportional to the gradient mini-batch size (up to a natural saturation point), thereby enabling perfect parallelization of mini-batch computations. Our theory also provides a simple choice for the momentum parameter, which is shown to be effective empirically.