On the Generalization of Stochastic Gradient Descent with Momentum
  While momentum-based methods, in conjunction with stochastic gradient descent
(SGD), are widely used when training machine learning models, there is little
theoretical understanding on the generalization error of such methods. In this
work, we first show that there exists a convex loss function for which the
stability gap for multiple epochs of SGD with standard heavy-ball momentum
(SGDM) becomes unbounded. Then, for smooth Lipschitz loss functions, we analyze
a modified momentum-based update rule, i.e., SGD with early momentum (SGDEM),
and show that it admits an upper-bound on the generalization error. Thus, our
results show that machine learning models can be trained for multiple epochs of
SGDEM with a guarantee for generalization. Finally, for the special case of
strongly convex loss functions, we find a range of momentum such that multiple
epochs of standard SGDM, as a special form of SGDEM, also generalizes.
Extending our results on generalization, we also develop an upper-bound on the
expected true risk, in terms of the number of training steps, the size of the
training set, and the momentum parameter. Our experimental evaluations verify
the consistency between the numerical results and our theoretical bounds. SGDEM
improves the generalization error of SGDM when training ResNet-18 on ImageNet
in practical distributed settings.
