On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems

Abstract

This paper analyzes the trajectories of stochastic gradient descent (SGD) to help understand the algorithm's convergence properties in non-convex problems. We first show that the sequence of iterates generated by SGD remains bounded and converges with probability $1$ under a very broad range of step-size schedules. Subsequently, going beyond existing positive probability guarantees, we show that SGD avoids strict saddle points/manifolds with probability $1$ for the entire spectrum of step-size policies considered. Finally, we prove that the algorithm's rate of convergence to Hurwicz minimizers is $\mathcal{O}(1/n^p)$ if the method is employed with a $\Theta (1/n^p)$ step-size schedule. This provides an important guideline for tuning the algorithm's step-size as it suggests that a cool-down phase with a vanishing step-size could lead to faster convergence; we demonstrate this heuristic using ResNet architectures on CIFAR.

32 pages, 8 figures

Cited by in corpus (12)

• Tackling the Curse of Dimensionality with Physics-Informed Neural Networks
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball
• Global Convergence and Stability of Stochastic Gradient Descent
• On the existence of optimal shallow feedforward networks with ReLU activation
• Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses
• Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes
• Stochastic Gradient Descent on Nonconvex Functions with General Noise Models
• Unconstrained optimisation on Riemannian manifolds
• Accelerated Almost-Sure Convergence Rates for Nonconvex Stochastic Gradient Descent using Stochastic Learning Rates
• Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization
• Stochastic Subgradient Descent on a Generic Definable Function Converges to a Minimizer