Strong error analysis for stochastic gradient descent optimization algorithms

DOI10.1093/IMANUM/DRZ055MaRDI QIDQ4964091zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

stochastic approximation algorithmsstochastic gradient descentstrong error analysis

Mathematics Subject Classification ID

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

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.

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

Cited in

(25)

• Convergence analysis of gradient descent stochastic algorithms
• Uniform-in-time weak error analysis for stochastic gradient descent algorithms via diffusion approximation
• Analysis of biased stochastic gradient descent using sequential semidefinite programs
• Concentration inequalities for additive functionals: a martingale approach
• Convergence of stochastic gradient descent in deep neural network
• Analysis of stochastic gradient descent in continuous time
• 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
• Lower error bounds for the stochastic gradient descent optimization algorithm: sharp convergence rates for slowly and fast decaying learning rates
• Machine learning approximation algorithms for high-dimensional fully nonlinear partial differential equations and second-order backward stochastic differential equations
• Full error analysis for the training of deep neural networks
• Sublinear convergence of a tamed stochastic gradient descent method in Hilbert space
• Stability and optimization error of stochastic gradient descent for pairwise learning
• 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
• A Convergence Study of SGD-Type Methods for Stochastic Optimization
• Backward error analysis and the qualitative behaviour of stochastic optimization algorithms: application to stochastic coordinate descent
• A hybrid two-level MCMC framework to accelerate posterior mean estimation with deep learning surrogates for Bayesian inverse problems
• Non-convergence to global minimizers for Adam and stochastic gradient descent optimization and constructions of local minimizers in the training of artificial neural networks
• A Global-in-Time Neural Network Approach to Dynamic Portfolio Optimization
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks
• The one step Malliavin scheme: new discretization of BSDEs implemented with deep learning regressions
• Non-convergence to global minimizers in data driven supervised deep learning: Adam and stochastic gradient descent optimization provably fail to converge to global minimizers in the training of deep neural networks with ReLU activation
• Stochastic optimization algorithms for biomedical image classification
• Performance analysis of stochastic gradient algorithms under weak conditions

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)