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

arXiv: https://arxiv.org/abs/2006.10311 · HTML: https://mlsanity.com/paper/2006.10311/

## Key facts

- Cited by 67 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2020.

## Built on by (most cited first, 30 of 67)

- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023)
- [Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes](https://mlsanity.com/paper/2102.09385/) (2021)
- [MoMo: Momentum Models for Adaptive Learning Rates](https://mlsanity.com/paper/2305.07583/) (2023)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Aiming towards the minimizers: fast convergence of SGD for overparametrized problems](https://mlsanity.com/paper/2306.02601/) (2023)
- [Stochastic Polyak Stepsize with a Moving Target](https://mlsanity.com/paper/2106.11851/) (2021)
- [On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging](https://mlsanity.com/paper/2107.00464/) (2021)
- [Cutting Some Slack for SGD with Adaptive Polyak Stepsizes](https://mlsanity.com/paper/2202.12328/) (2022)
- [Global Convergence and Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2110.01663/) (2021)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [A Stochastic Proximal Polyak Step Size](https://mlsanity.com/paper/2301.04935/) (2023)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization](https://mlsanity.com/paper/2111.06328/) (2021)
- [SP2: A Second Order Stochastic Polyak Method](https://mlsanity.com/paper/2207.08171/) (2022)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [A Unified Convergence Theorem for Stochastic Optimization Methods](https://mlsanity.com/paper/2206.03907/) (2022)
- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024)
- [Sharpness-Aware Minimization: General Analysis and Improved Rates](https://mlsanity.com/paper/2503.02225/) (2025)
- [SGD with a Constant Large Learning Rate Can Converge to Local Maxima](https://mlsanity.com/paper/2107.11774/) (2021)
- [Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM](https://mlsanity.com/paper/2307.14528/) (2023)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [Locally Adaptive Federated Learning](https://mlsanity.com/paper/2307.06306/) (2023)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [Practical and Matching Gradient Variance Bounds for Black-Box Variational Bayesian Inference](https://mlsanity.com/paper/2303.10472/) (2023)
- [Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalization](https://mlsanity.com/paper/2310.01139/) (2023)

## Abstract (arXiv)

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.