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

2020/06/18 by Robert M. Gower, Othmane Sebbouh, Gower, Robert M. +4 · 15 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.2006.10311

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

openalex publication_date 2020/06/18 · arxiv created 2021/03/22 · arxiv updated 2021/03/23 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28

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.

Citations

• Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
• A Stochastic Approximation Method
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• Numerical optimization

Cited by

• Continuized Nesterov Acceleration for Non-Convex Optimization
• Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients
• Adaptive SGD with Line-Search and Polyak Stepsizes: Nonconvex Convergence and Accelerated Rates
• Descend or Rewind? Stochastic Gradient Descent Unlearning
• Taking the Road Less Scheduled with Adaptive Polyak Steps
• Discrete State Diffusion Models: A Sample Complexity Perspective
• Smooth Quasar-Convex Optimization with Constraints
• Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential
• Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems
• Power-Constrained Policy Gradient Methods for LQR
• Global Convergence and Stability of Stochastic Gradient Descent
• Stochastic Gradient Descent on Nonconvex Functions with General Noise Models
• New Tight Bounds for SGD without Variance Assumption: A Computer-Aided Lyapunov Analysis
• Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization
• Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework

Related

• Better Theory for SGD in the Nonconvex World
• Demystifying the Myths and Legends of Nonconvex Convergence of SGD
• Tackling benign nonconvexity with smoothing and stochastic gradients
• Adaptive SGD with Line-Search and Polyak Stepsizes: Nonconvex Convergence and Accelerated Rates
• Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions