On convergence rates of stochastic gradient descent for linear inverse problems

Abstract

Stochastic gradient methods have gained increasing attention for solving large-scale inverse problems due to their computational efficiency. However, their theoretical justification in the context of ill-posed problems remains underdeveloped, particularly regarding convergence rate analysis, where existing results typically yield only suboptimal rates. In this paper, we address this gap by establishing order-optimal convergence rates for a stochastic gradient method applied to linear ill-posed problems in Hilbert spaces. Under Hölder-type source conditions with smoothness parameter $$\nu \in (0, 1/2]$$ ν ∈ ( 0 , 1 / 2 ] , we derive convergence rates both in expectation and almost surely, accommodating a broad class of step-size sequences, including constant and polynomially decaying ones. Our analysis is based on a delicate Lyapunov-type argument and an application of the Robbins–Siegmund theorem. As a byproduct, we also establish new convergence results that do not rely on any source conditions.