Error Lower Bounds of Constant Step-size Stochastic Gradient Descent

2019/10/18 by Zhiyan Ding, Ding, Zhiyan, Yiding Chen +5
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and ELM #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1910.08212

openalex publication_date 2019/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Making Gradient Descent Optimal for Strongly Convex Stochastic\n Optimization
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains

Related

• Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
• Stochastic Gradient Descent in Non-Convex Problems: Asymptotic Convergence with Relaxed Step-Size via Stopping Time Methods
• Convex SGD: Generalization Without Early Stopping
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependence