Error Lower Bounds of Constant Step-size Stochastic Gradient Descent
This work addresses a gap in theoretical understanding for researchers in optimization and machine learning, offering foundational insights into SGD's limitations.
The paper tackles the problem of deriving error lower bounds for constant step-size Stochastic Gradient Descent (SGD) on potentially non-convex objective functions with Lipschitz gradients, providing the first such analysis without assuming strong convexity.
Stochastic Gradient Descent (SGD) plays a central role in modern machine learning. While there is extensive work on providing error upper bound for SGD, not much is known about SGD error lower bound. In this paper, we study the convergence of constant step-size SGD. We provide error lower bound of SGD for potentially non-convex objective functions with Lipschitz gradients. To our knowledge, this is the first analysis for SGD error lower bound without the strong convexity assumption. We use experiments to illustrate our theoretical results.