Strong error analysis for stochastic gradient descent optimization algorithms

DOI10.1093/IMANUM/DRZ055zbMATH Open1460.65071arXiv1801.09324OpenAlexW2786773456WikidataQ126576349 ScholiaQ126576349MaRDI QIDQ4964091FDOQ4964091

Authors: Arnulf Jentzen, Benno Kuckuck, Ariel Neufeld, Philippe von Wurstemberger 

Publication date: 24 February 2021

Published in: IMA Journal of Numerical Analysis (Search for Journal in Brave)

Abstract: Stochastic gradient descent (SGD) optimization algorithms are key ingredients in a series of machine learning applications. In this article we perform a rigorous strong error analysis for SGD optimization algorithms. In particular, we prove for every arbitrarily small $varepsilonin(0,infty)$ and every arbitrarily large $pin(0,infty)$ that the considered SGD optimization algorithm converges in the strong $L^p$-sense with order $frac12-varepsilon$ to the global minimum of the objective function of the considered stochastic approximation problem under standard convexity-type assumptions on the objective function and relaxed assumptions on the moments of the stochastic errors appearing in the employed SGD optimization algorithm. The key ideas in our convergence proof are, first, to employ techniques from the theory of Lyapunov-type functions for dynamical systems to develop a general convergence machinery for SGD optimization algorithms based on such functions, then, to apply this general machinery to concrete Lyapunov-type functions with polynomial structures, and, thereafter, to perform an induction argument along the powers appearing in the Lyapunov-type functions in order to achieve for every arbitrarily large $pin(0,infty)$ strong $L^p$-convergence rates. This article also contains an extensive review of results on SGD optimization algorithms in the scientific literature.

Full work available at URL: https://arxiv.org/abs/1801.09324

Recommendations

• Lower error bounds for the stochastic gradient descent optimization algorithm: sharp convergence rates for slowly and fast decaying learning rates
• Stochastic gradient descent with noise of machine learning type. I: Discrete time analysis
• New Convergence Aspects of Stochastic Gradient Algorithms
• Convergence rates for the stochastic gradient descent method for non-convex objective functions
• Convergence of stochastic gradient descent in deep neural network

zbMATH Keywords

stochastic gradient descentstochastic approximation algorithmsstrong error analysis

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Stochastic programming (90C15)

Cited In (15)

• Lower error bounds for the stochastic gradient descent optimization algorithm: sharp convergence rates for slowly and fast decaying learning rates
• Uniform-in-time weak error analysis for stochastic gradient descent algorithms via diffusion approximation
• Analysis of stochastic gradient descent in continuous time
• Concentration inequalities for additive functionals: a martingale approach
• Convergence of stochastic gradient descent in deep neural network
• Machine learning approximation algorithms for high-dimensional fully nonlinear partial differential equations and second-order backward stochastic differential equations
• Stochastic gradient descent with noise of machine learning type. I: Discrete time analysis
• Overall error analysis for the training of deep neural networks via stochastic gradient descent with random initialisation
• Stability and optimization error of stochastic gradient descent for pairwise learning
• Performance analysis of stochastic gradient algorithms under weak conditions
• Sublinear convergence of a tamed stochastic gradient descent method in Hilbert space
• A proof of convergence for gradient descent in the training of artificial neural networks for constant target functions
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• Analysis of biased stochastic gradient descent using sequential semidefinite programs
• Full error analysis for the training of deep neural networks

This page was built for publication: Strong error analysis for stochastic gradient descent optimization algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4964091)