Lower error bounds for the stochastic gradient descent optimization algorithm: Sharp convergence rates for slowly and fast decaying learning rates

Abstract

The stochastic gradient descent (SGD) optimization algorithm plays a central role in a series of machine learning applications. The scientific literature provides a vast amount of upper error bounds for the SGD method. Much less attention as been paid to proving lower error bounds for the SGD method. It is the key contribution of this paper to make a step in this direction. More precisely, in this article we establish for every $\gamma ,\nu \in (0,\infty )$ essentially matching lower and upper bounds for the mean square error of the SGD process with learning rates $(\frac{\gamma }{n^{\nu }}{)}_{n\in \mathbb{N}}$ associated to a simple quadratic stochastic optimization problem. This allows us to precisely quantify the mean square convergence rate of the SGD method in dependence on the asymptotic behavior of the learning rates.

42 pages

References in corpus (4)

• Strong error analysis for stochastic gradient descent optimization algorithms
• Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
• When Does Stochastic Gradient Algorithm Work Well?
• On SGD's Failure in Practice: Characterizing and Overcoming Stalling

Cited by in corpus (12)

• Solving the Kolmogorov PDE by means of deep learning
• Strong error analysis for stochastic gradient descent optimization algorithms
• Overcoming the curse of dimensionality in the approximative pricing of financial derivatives with default risks
• Full error analysis for the training of deep neural networks
• 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
• High-dimensional approximation spaces of artificial neural networks and applications to partial differential equations
• Convergence rates for gradient descent in the training of overparameterized artificial neural networks with piecewise affine activation
• Full history recursive multilevel Picard approximations for ordinary differential equations with expectations
• Error Lower Bounds of Constant Step-size Stochastic Gradient Descent
• A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functions
• On the Saturation Phenomenon of Stochastic Gradient Descent for Linear Inverse Problems