A Modular Analysis of Provable Acceleration via Polyak's Momentum:
  Training a Wide ReLU Network and a Deep Linear Network
  Incorporating a so-called "momentum" dynamic in gradient descent methods is
widely used in neural net training as it has been broadly observed that, at
least empirically, it often leads to significantly faster convergence. At the
same time, there are very few theoretical guarantees in the literature to
explain this apparent acceleration effect. Even for the classical strongly
convex quadratic problems, several existing results only show Polyak's momentum
has an accelerated linear rate asymptotically. In this paper, we first revisit
the quadratic problems and show a non-asymptotic accelerated linear rate of
Polyak's momentum. Then, we provably show that Polyak's momentum achieves
acceleration for training a one-layer wide ReLU network and a deep linear
network, which are perhaps the two most popular canonical models for studying
optimization and deep learning in the literature. Prior work Du at al. 2019 and
Wu et al. 2019 showed that using vanilla gradient descent, and with an use of
over-parameterization, the error decays as $(1- \Theta(\frac{1}{ \kappa'}))^t$
after $t$ iterations, where $\kappa'$ is the condition number of a Gram Matrix.
Our result shows that with the appropriate choice of parameters Polyak's
momentum has a rate of $(1-\Theta(\frac{1}{\sqrt{\kappa'}}))^t$. For the deep
linear network, prior work Hu et al. 2020 showed that vanilla gradient descent
has a rate of $(1-\Theta(\frac{1}{\kappa}))^t$, where $\kappa$ is the condition
number of a data matrix. Our result shows an acceleration rate $(1-
\Theta(\frac{1}{\sqrt{\kappa}}))^t$ is achievable by Polyak's momentum. All the
results in this work are obtained from a modular analysis, which can be of
independent interest. This work establishes that momentum does indeed speed up
neural net training.
