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

2018/11/06 by Raef Bassily, Mikhail Belkin, Bassily, Raef +3 · 18 citations
Computer Science · Engineering · Mathematics · #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1811.02564

arxiv created 2018/11/06 · arxiv updated 2018/11/08

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.

Cited by

• A Generalized Energy-Based Adaptive Gradient Method for Optimization
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Distributed Optimization for Over-Parameterized Learning
• Large-Time Analysis of the Langevin Dynamics for Energies Fulfilling Polyak-Łojasiewicz Conditions
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Phase retrieval of complex-valued objects via a randomized Kaczmarz method
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• DINO: Distributed Newton-Type Optimization Method
• Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings
• Global Convergence and Stability of Stochastic Gradient Descent
• Stagewise Training Accelerates Convergence of Testing Error Over SGD
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives
• Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions
• A Stochastic Gradient Descent Method for Globally Minimizing Nearly Convex Functions
• Identity Crisis: Memorization and Generalization under Extreme Overparameterization
• Statistical Inference for Online Algorithms

Related

• Stagewise Training Accelerates Convergence of Testing Error Over SGD
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• Aiming towards the minimizers: fast convergence of SGD for overparametrized problems