Momentum Improves Normalized SGD
  We provide an improved analysis of normalized SGD showing that adding
momentum provably removes the need for large batch sizes on non-convex
objectives. Then, we consider the case of objectives with bounded second
derivative and show that in this case a small tweak to the momentum formula
allows normalized SGD with momentum to find an $\epsilon$-critical point in
$O(1/\epsilon^{3.5})$ iterations, matching the best-known rates without
accruing any logarithmic factors or dependence on dimension. We also provide an
adaptive method that automatically improves convergence rates when the variance
in the gradients is small. Finally, we show that our method is effective when
employed on popular large scale tasks such as ResNet-50 and BERT pretraining,
matching the performance of the disparate methods used to get state-of-the-art
results on both tasks.
