Better Theory for SGD in the Nonconvex World

By Ahmed Khaled, Peter Richtárik. 2020

242 citations recorded by the source corpus.

Large-scale nonconvex optimization problems are ubiquitous in modern machine learning, and among practitioners interested in solving them, Stochastic Gradient Descent (SGD) reigns supreme. We revisit the analysis of SGD in the nonconvex setting and propose a new variant of the recently introduced expected smoothness assumption which governs the behaviour of the second moment of the stochastic gradient. We show that our assumption is both more general and more reasonable than assumptions made in all prior work. Moreover, our results yield the optimal $\mathcal{O}(\varepsilon^{-4})$ rate for finding a stationary point of nonconvex smooth functions, and recover the optimal $\mathcal{O}(\varepsilon^{-1})$ rate for finding a global solution if the Polyak-Łojasiewicz condition is satisfied. We compare against convergence rates under convexity and prove a theorem on the convergence of SGD under Quadratic Functional Growth and convexity, which might be of independent interest. Moreover, we perform our analysis in a framework which allows for a detailed study of the effects of a wide array of sampling strategies and minibatch sizes for finite-sum optimization problems. We corroborate our theoretical results with experiments on real and synthetic data.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research, 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 Theory and Mathematics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…might be restrictive or never be satisﬁed 5 and proposed alternative conditions [Nguyen et al., 2018, Vaswani et al., 2018, Gower et al., 2019, 2021, Khaled et al., 2020, Khaled and Richtárik, 2020, Assran et al., 2019, Koloskova et al., 2020, Patel and Zhang, 2021, Loizou et al., 2020, 2021].”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, background): “However, for large classes of convex functions, it has been shown that these assumptions do not to hold [20, 31].”
Stochastic Gradient Descent on Nonconvex Functions with General Noise Models (2021, methodology): “While there are many works that have provided insight, understanding SGD’s global behavior has been notably advanced by several recent works [Asi and Duchi, 2019, Lei et al., 2019, Patel, 2020, Khaled and Richtárik, 2020] that we overview presently.”
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, methodology): “In contrast, by using a step size which depends on the total number of iterations, the same convergence rate can be achieved without the need for the bounded gradient assumption (Khaled and Richtarik, 2020).”