Stochastic Gradient Descent for Nonconvex Learning Without Bounded Gradient Assumptions

By Yunwen Lei, Ting Hu, Guiying Li, Ke Tang. 2019

144 citations recorded by the source corpus.

Stochastic gradient descent (SGD) is a popular and efficient method with wide applications in training deep neural nets and other nonconvex models. While the behavior of SGD is well understood in the convex learning setting, the existing theoretical results for SGD applied to nonconvex objective functions are far from mature. For example, existing results require to impose a nontrivial assumption on the uniform boundedness of gradients for all iterates encountered in the learning process, which is hard to verify in practical implementations. In this article, we establish a rigorous theoretical foundation for SGD in nonconvex learning by showing that this boundedness assumption can be removed without affecting convergence rates, and relaxing the standard smoothness assumption to Hölder continuity of gradients. In particular, we establish sufficient conditions for almost sure convergence as well as optimal convergence rates for SGD applied to both general nonconvex and gradient-dominated objective functions. A linear convergence is further derived in the case with zero variances.

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

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “In the interpolation case, we obtain linear convergence to the optimum with a constant step-size equal to that used in Vaswani et al. (2019a); Lei et al. (2019).”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, background): “As a result, there has been a recent surge in trying to avoid these assumptions on the stochastic gradients for several classes of smooth functions: strongly convex [14, 25, 31], convex [14, 25, 40, 42], or even nonconvex functions [20, 24, 25].”
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, background): “On the other extreme, we see that for b = 1 , that is SGD without minibatching, we obtain the convergence rate 1 − µ 2 / 3 LL max which matches the current state-of-the-art rate [54, Thm. 4], [19, Thm. 2] and [24, Thm 4] known under the exact same assumptions.”
Better Theory for SGD in the Nonconvex World (2020, background): “Convergence under the PL condition One of the popular generalizations of strong convexity in the literature is the Polyak-Łojasiewicz condition (Karimi et al., 2016; Lei et al., 2019).”
Stochastic Gradient Descent on Nonconvex Functions with General Noise Models (2021, background): “…et al. [2018], Asi and Duchi [2019], Lei et al. [2019], Patel [2020], Khaled and Richtárik [2020]; relax the global, uniform Hölder continuity assumption of [Lei et al., 2019]; and relax the global, Lipschitz continuity assumption of Bottou et al. [2018], Patel [2020], Khaled and Richtárik [2020].”
Decentralized Federated Averaging (2021, methodology): “A particular idea is leveraging unbounded gradient convergence analysis [57], [58], and the core technique is using the inequality for functions with the Lipschitz gradient established in [59].”