On the Saturation Phenomenon of Stochastic Gradient Descent for Linear Inverse Problems

2020/10/21 by Bangti Jin, Jin, Bangti, Zehui Zhou +3
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Numerical Analysis (math.NA) #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2010.10916

openalex publication_date 2020/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Stochastic gradient descent (SGD) is a promising method for solving large-scale inverse problems, due to its excellent scalability with respect to data size. The current mathematical theory in the lens of regularization theory predicts that SGD with a polynomially decaying stepsize schedule may suffer from an undesirable saturation phenomenon, i.e., the convergence rate does not further improve with the solution regularity index when it is beyond a certain range. In this work, we present a refined convergence rate analysis of SGD, and prove that saturation actually does not occur if the initial stepsize of the schedule is sufficiently small. Several numerical experiments are provided to complement the analysis.

Citations

• A Stochastic Approximation Method
• An Iteration Formula for Fredholm Integral Equations of the First Kind

Related

• Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization
• On the Discrepancy Principle for Stochastic Gradient Descent
• On the convergence of stochastic variance reduced gradient for linear inverse problems
• On the Convergence of Stochastic Gradient Descent for Linear Inverse Problems in Banach Spaces
• On the Convergence of Stochastic Gradient Descent for Nonlinear Ill-Posed Problems