SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation

Abstract

Stochastic Gradient Descent (SGD) is being used routinely for optimizing non-convex functions. Yet, the standard convergence theory for SGD in the smooth non-convex setting gives a slow sublinear convergence to a stationary point. In this work, we provide several convergence theorems for SGD showing convergence to a global minimum for non-convex problems satisfying some extra structural assumptions. In particular, we focus on two large classes of structured non-convex functions: (i) Quasar (Strongly) Convex functions (a generalization of convex functions) and (ii) functions satisfying the Polyak-Lojasiewicz condition (a generalization of strongly-convex functions). Our analysis relies on an Expected Residual condition which we show is a strictly weaker assumption than previously used growth conditions, expected smoothness or bounded variance assumptions. We provide theoretical guarantees for the convergence of SGD for different step-size selections including constant, decreasing and the recently proposed stochastic Polyak step-size. In addition, all of our analysis holds for the arbitrary sampling paradigm, and as such, we give insights into the complexity of minibatching and determine an optimal minibatch size. Finally, we show that for models that interpolate the training data, we can dispense of our Expected Residual condition and give state-of-the-art results in this setting.

arXiv commentProceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS) 2021

References in corpus (16)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Gradient Descent Learns Linear Dynamical Systems
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• Better Theory for SGD in the Nonconvex World
• Gradient methods for convex minimization: better rates under weaker conditions
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• L4: Practical loss-based stepsize adaptation for deep learning
• SGD Converges to Global Minimum in Deep Learning via Star-convex Path
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• Towards closing the gap between the theory and practice of SVRG
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip

Cited by in corpus (4)

• Global Convergence and Stability of Stochastic Gradient Descent
• Stochastic Gradient Descent on Nonconvex Functions with General Noise Models
• AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods
• On The Convergence of First Order Methods for Quasar-Convex Optimization