UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

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

Jin, B; Zhou, Z; Zou, J; (2021) On the Saturation Phenomenon of Stochastic Gradient Descent for Linear Inverse Problems. SIAM/ASA Journal on Uncertainty Quantification , 9 (4) pp. 1533-1588. 10.1137/20M1374456. Green open access

[thumbnail of Jin_20m1374456.pdf]
Preview
Text
Jin_20m1374456.pdf

Download (2MB) | Preview

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.

Type: Article
Title: On the Saturation Phenomenon of Stochastic Gradient Descent for Linear Inverse Problems
Open access status: An open access version is available from UCL Discovery
DOI: 10.1137/20M1374456
Publisher version: https://doi.org/10.1137/20M1374456
Language: English
Additional information: This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10133489
Downloads since deposit
45Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item