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 this 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 setting, 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, SGD+Nesterov and Adam.
The authors present a new first order optimization method that adds a corrective term to Nesterov SGD. They demonstrate that this adjustment is necessary and sufficient to benefit from the faster convergence of Nesterov gradient descent in the stochastic case. In the full-batch (non deterministic) setting, their algorithm boils down to the classical formulation of Nesterov GD. Their approach is justified by a well conducted theoretical analysis and some empirical work on toy datasets. 
Positive points:
- The approach is elegant and thoroughly justified. The convergence to Nesterov GD when the batch size increase is comforting.
- The empirical evaluation, even if it is still preliminary and larger scale experiments will have to be conducted before the method could be widely adopted, are suitable and convincing.
- Some interesting observations regarding the convergence regimes (in respect to the batch size) are made. It would have been interesting to see how the results from fig3 generalize to the non convex problems considered in the paper.
Possible improvements:
- In H2, it is mentioned that the algorithm is restarted (the momentum is reset) when the learning rate is annealed. Was this also done for SGD+nesterov? Also, I think it is an important implementation detail that should be mentioned outside of the appendix
- Adam didn’t get the same hyper-parameter tuning as MaSS did. It is a bit disappointing, as I think the superior performance (in generalization) of non-adaptive methods would still hold and the experiment would have been more convincing. Rate of convergence is also not reported for Adam in fig 5.
I think this is definitely a good paper that should be accepted. I’m looking forward to see how it performs on non-toy models and if the community adopt it.