On the insufficiency of existing momentum schemes for Stochastic Optimization
Momentum based stochastic gradient methods such as heavy ball and Nesterovs accelerated gradient descent method are widely used in practice for training deep networks and other supervised learning models, as they often provide significant improvements over stochastic gradient descent.Rigorously speaking, fast gradient methods have provable improvements over gradient descent only for the deterministic case, where the gradients are exact.In the stochastic case, the popular explanations for their wide applicability is that when these fast gradient methods are applied in the stochastic case, they partially mimic their exact gradient counterparts, resulting in some practical gain.This work provides a counterpoint to this belief by proving that there exist simple problem instances where these methods cannot outperform SGD despite the best setting of its parameters.These negative problem instances are, in an informal sense, generic; they do not look like carefully constructed pathological instances.These results suggest that HB or NAGs practical performance gains are a by-product of minibatching.", "Furthermore, this work provides a viable alternative, which, on the same set of problem instances, significantly improves over HB, NAG, and SGDs performance.", "This algorithm, referred to as Accelerated Stochastic Gradient Descent, is a simple to implement stochastic algorithm, based on a relatively less popular variant of Nesterovs Acceleration.Extensive empirical results in this paper show that ASGD has performance gains over HB, NAG, and SGD.The code for implementing the ASGD Algorithm can be found at https://github.com/rahulkidambi/AccSGD.
Existing momentum/acceleration schemes such as heavy ball method and Nesterov's acceleration employed with stochastic gradients do not improve over vanilla stochastic gradient descent, especially when employed with small batch sizes.