On exponential convergence of SGD in non-convex over-parametrized learning

Abstract

Large over-parametrized models learned via stochastic gradient descent (SGD) methods have become a key element in modern machine learning. Although SGD methods are very effective in practice, most theoretical analyses of SGD suggest slower convergence than what is empirically observed. In our recent work [8] we analyzed how interpolation, common in modern over-parametrized learning, results in exponential convergence of SGD with constant step size for convex loss functions. In this note, we extend those results to a much broader non-convex function class satisfying the Polyak-Lojasiewicz (PL) condition. A number of important non-convex problems in machine learning, including some classes of neural networks, have been recently shown to satisfy the PL condition. We argue that the PL condition provides a relevant and attractive setting for many machine learning problems, particularly in the over-parametrized regime.

References in corpus (6)

• Guaranteed Matrix Completion via Non-convex Factorization
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Gradient methods for convex minimization: better rates under weaker conditions
• An Alternative View: When Does SGD Escape Local Minima?
• The loss landscape of overparameterized neural networks
• Diving into the shallows: a computational perspective on large-scale shallow learning

Cited by in corpus (24)

• Analyzing Upper Bounds on Mean Absolute Errors for Deep Neural Network Based Vector-to-Vector Regression
• Identity Crisis: Memorization and Generalization under Extreme Overparameterization
• Beyond Convexity -- Contraction and Global Convergence of Gradient Descent
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• Stagewise Training Accelerates Convergence of Testing Error Over SGD
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Global Convergence and Stability of Stochastic Gradient Descent
• Linear Convergence of Adaptive Stochastic Gradient Descent
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime
• Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes
• Distributed Optimization for Over-Parameterized Learning
• DINO: Distributed Newton-Type Optimization Method
• Student Specialization in Deep ReLU Networks With Finite Width and Input Dimension
• Escaping Saddle-Points Faster under Interpolation-like Conditions
• Phase retrieval of complex-valued objects via a randomized Kaczmarz method
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives
• Invexifying Regularization of Non-Linear Least-Squares Problems
• Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions