Accelerating SGD with momentum for over-parameterized learning

Abstract

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.

arXiv commentnew version

References in corpus (11)

• Adam: A Method for Stochastic Optimization
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• On the Convergence of Adam and Beyond
• Reconciling modern machine learning practice and the bias-variance trade-off
• An Analysis of Deep Neural Network Models for Practical Applications
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• To understand deep learning we need to understand kernel learning
• Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron

Cited by in corpus (21)

• Optimization for deep learning: theory and algorithms
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Mixing ADAM and SGD: a Combined Optimization Method
• Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings
• Training Neural Networks for and by Interpolation
• Hyperparameter Optimization Is Deceiving Us, and How to Stop It
• Training Deep Neural Networks with Adaptive Momentum Inspired by the Quadratic Optimization
• Guarantees for Tuning the Step Size using a Learning-to-Learn Approach
• Feedback Gradient Descent: Efficient and Stable Optimization with Orthogonality for DNNs
• Explicit Regularization of Stochastic Gradient Methods through Duality
• The Minimax Complexity of Distributed Optimization
• Student Specialization in Deep ReLU Networks With Finite Width and Input Dimension
• DEED: A General Quantization Scheme for Communication Efficiency in Bits
• Convergence Analysis of Accelerated Stochastic Gradient Descent under the Growth Condition
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum
• Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models
• Painless step size adaptation for SGD