Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron

Abstract

Modern machine learning focuses on highly expressive models that are able to fit or interpolate the data completely, resulting in zero training loss. For such models, we show that the stochastic gradients of common loss functions satisfy a strong growth condition. Under this condition, we prove that constant step-size stochastic gradient descent (SGD) with Nesterov acceleration matches the convergence rate of the deterministic accelerated method for both convex and strongly-convex functions. We also show that this condition implies that SGD can find a first-order stationary point as efficiently as full gradient descent in non-convex settings. Under interpolation, we further show that all smooth loss functions with a finite-sum structure satisfy a weaker growth condition. Given this weaker condition, we prove that SGD with a constant step-size attains the deterministic convergence rate in both the strongly-convex and convex settings. Under additional assumptions, the above results enable us to prove an O(1/k^2) mistake bound for k iterations of a stochastic perceptron algorithm using the squared-hinge loss. Finally, we validate our theoretical findings with experiments on synthetic and real datasets.

arXiv commentAISTATS 2019

References in corpus (13)

• Adam: A Method for Stochastic Optimization
• ADADELTA: An Adaptive Learning Rate Method
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Understanding deep learning requires rethinking generalization
• Guaranteed Matrix Completion via Non-convex Factorization
• A Universal Catalyst for First-Order Optimization
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• On exponential convergence of SGD in non-convex over-parametrized learning
• Accelerating SGD with momentum for over-parameterized learning
• On Acceleration with Noise-Corrupted Gradients
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions

Cited by in corpus (15)

• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Accelerating SGD with momentum for over-parameterized learning
• SGD: General Analysis and Improved Rates
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• DeepReduce: A Sparse-tensor Communication Framework for Distributed Deep Learning
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization
• Towards Label-Free 3D Segmentation of Optical Coherence Tomography Images of the Optic Nerve Head Using Deep Learning
• About some works of Boris Polyak on convergence of gradient methods and their development
• AdaSub: Stochastic Optimization Using Second-Order Information in Low-Dimensional Subspaces
• Escaping Saddle-Points Faster under Interpolation-like Conditions
• Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD
• Stochastic Polyak Stepsize with a Moving Target