Accelerating SGD with momentum for over-parameterized learning
  Nesterov SGD is widely used for training modern neural networks and other
machine learning models. Yet, its advantages over SGD have not been
theoretically clarified. Indeed, as we show in our paper, both theoretically
and empirically, Nesterov SGD with any parameter selection does not in general
provide acceleration over ordinary SGD. Furthermore, Nesterov SGD may diverge
for step sizes that ensure convergence of ordinary SGD. This is in contrast to
the classical results in the deterministic scenario, where the same step size
ensures accelerated convergence of the Nesterov's method over optimal gradient
descent.
  To address the non-acceleration issue, we introduce a compensation term to
Nesterov SGD. The resulting algorithm, which we call MaSS, converges for same
step sizes as SGD. We prove that MaSS obtains an accelerated convergence rates
over SGD for any mini-batch size in the linear setting. For full batch, the
convergence rate of MaSS matches the well-known accelerated rate of the
Nesterov's method.
  We also analyze the practically important question of the dependence of the
convergence rate and optimal hyper-parameters on the mini-batch size,
demonstrating three distinct regimes: linear scaling, diminishing returns and
saturation.
  Experimental evaluation of MaSS for several standard architectures of deep
networks, including ResNet and convolutional networks, shows improved
performance over SGD, Nesterov SGD and Adam.
