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

By Robert Mansel Gower, Othmane Sebbouh, Nicolas Loizou. 2020

104 citations recorded by the source corpus.

We provide several convergence theorems for SGD for two large classes of structured non-convex functions: (i) the Quasar (Strongly) Convex functions and (ii) the functions satisfying the Polyak-Lojasiewicz condition. Our analysis relies on the Expected Residual condition which we show is a strictly weaker assumption as compared to 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 are able to give insights into the complexity of minibatching and determine an optimal minibatch size. In particular we recover the best known convergence rates of full gradient descent and single element sampling SGD as a special case. 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.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, methodology): “While this choice yields fast convergence to the neighborhood of a minimizer, two main problems arise: (a) the optimal � depends on (often unknown) problem parameters — hence often requires heavy tuning ; and (b) it cannot be guaranteed that X ⇤ is reached in the limit [13, 16, 15].”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “Similar results have been shown in Gower et al. (2020) for the case of expected residual.”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, unknown): “More recently, variations of the Polyak stepsize have been proposed for stochastic optimization (Loizou et al., 2021; Prazeres & Oberman, 2021; Berrada et al., 2020; Gower et al., 2021).”