On the Saturation Phenomenon of Stochastic Gradient Descent for Linear Inverse Problems
arXiv:2010.10916
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.
arXiv commentto appear at SIAM/ASA J. Uncertainty Quantification, with error corrected
References in corpus (5)
- Optimal Rates for Multi-pass Stochastic Gradient Methods
- Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
- Lower error bounds for the stochastic gradient descent optimization algorithm: Sharp convergence rates for slowly and fast decaying learning rates
- Stochastic Learning under Random Reshuffling with Constant Step-sizes
- Beyond the Bakushinskii veto: Regularising linear inverse problems without knowing the noise distribution