On the convergence of stochastic variance reduced gradient for linear inverse problems

Basic Information

• Paper ID: 2510.14759
• Title: On the convergence of stochastic variance reduced gradient for linear inverse problems
• Authors: Bangti Jin, Zehui Zhou (Department of Mathematics, Chinese University of Hong Kong)
• Classification: math.NA cs.NA math.OC
• Publication Date: October 16, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.14759

Abstract

Stochastic Variance Reduced Gradient (SVRG) is an accelerated version of stochastic gradient descent based on variance reduction, showing promise for solving large-scale inverse problems. This paper analyzes SVRG and its regularized version incorporating prior knowledge for solving linear inverse problems in Hilbert spaces. The study proves that under appropriate constant step-size schedules and regularity conditions, regularized SVRG achieves optimal convergence rates with respect to noise level without requiring any early stopping rule; standard SVRG is also optimal for non-smooth solutions under a priori stopping rules. The analysis is based on explicit error recursions and appropriate a priori estimates regarding inner-loop updates around anchor points.

Research Background and Motivation

Problem Description

This paper studies linear inverse problems in Hilbert spaces: $A_\dagger x = y_\dagger$

where:

• $A_\dagger: X \to Y = Y_1 \times \cdots \times Y_n$ is the system operator
• $x \in X$ is the unknown signal, $y_\dagger \in Y$ is the exact data
• Only noisy data $y^\delta = y_\dagger + \xi$ is available, with noise level $\delta = \|\xi\|_Y$

Research Motivation

1. Large-scale problem demands: Linear inverse problems arise widely in practical applications such as computed tomography and positron emission tomography, with massive data scales
2. Limitations of existing methods: Traditional iterative methods suffer from low computational efficiency on large-scale problems
3. SVRG advantages: Stochastic variance reduced gradient methods possess excellent scalability, but their theoretical analysis in inverse problems remains incomplete
4. Regularization requirements: Standard SVRG requires early stopping rules for regularization, while incorporation of prior knowledge may improve this situation

Core Contributions

1. Refined theoretical analysis: Establishes complete convergence theory for SVRG and regularized SVRG (rSVRG) solving linear inverse problems
2. Optimal convergence rates: Proves that both methods achieve optimal convergence rate $O(\delta^{2\nu/(1+2\nu)})$ under appropriate conditions
3. Regularization properties: rSVRG possesses intrinsic regularization mechanism without requiring early stopping; standard SVRG also exhibits regularization properties under a priori stopping
4. Expected and uniform convergence: Establishes convergence rates in both expected and uniform senses, extending existing results
5. Relaxed conditions: Compared to existing work, conditions for SVRG optimality are more relaxed

Methodology Details

Problem Formulation

Consider the optimization problem: $J(x) = \frac{1}{2n}\|A_\dagger x - y^\delta\|_Y^2 = \frac{1}{n}\sum_{i=1}^n f_i(x)$ where $f_i(x) = \frac{1}{2}\|A_{\dagger,i}x - y^\delta_i\|_{Y_i}^2$

Algorithm Architecture

Standard SVRG (Algorithm 1)

Initialization: x₀^δ = x₀, frequency M, step-size {ηₖ}
for K = 0,1,... do
    Compute gₖ = J'(x_{KM}^δ) = (1/n)A_†*(A_†x_{KM}^δ - y^δ)
    for t = 0,1,...,M-1 do
        Randomly sample i_{KM+t} ∈ {1,...,n}
        Update x_{KM+t+1}^δ = x_{KM+t}^δ - η_{KM+t}(A*_{i_{KM+t}}A_{i_{KM+t}}(x_{KM+t}^δ - x_{KM}^δ) + gₖ)
    end
end

Regularized SVRG (Algorithm 2)

Replaces operator $A_\dagger$ with approximate operator $A$ obtained through truncated singular value decomposition: $A(\cdot) = \sum_{j=1}^J \sigma_j\langle\phi_j, \cdot\rangle\psi_j$ where singular values satisfying $\sigma_j \geq a\delta^b$ are retained.

Core Assumptions (Assumption 2.1)

1. Step-size condition: $\eta_j = c_0 \leq L^{-1}$, where $L = \max_{1\leq i\leq n}\|A_i\|^2$
2. Source condition: There exist $\nu > 0$ and $w \in N(A_\dagger)^\perp$ such that $x_\dagger - x_0 = B_\dagger^\nu w$
3. Operator approximation: When $a > 0$, $A$ is constructed via truncated SVD, retaining singular values $\sigma_j \geq a\delta^b$

Technical Innovations

1. Error decomposition strategy: Decomposes error into bias and variance components with precise estimation for each
2. Anchor point analysis: Establishes critical a priori estimates by analyzing inner-loop updates relative to anchor points
3. Unified framework: Provides a unified theoretical framework for handling both standard SVRG and regularized SVRG

Experimental Setup

Datasets

Three standard inverse problems from the Regutools package:

• s-phillips: Mildly ill-posed problem
• s-gravity: Severely ill-posed problem
• s-shaw: Severely ill-posed problem

All problems are discretized into finite-dimensional linear systems with $n = m = 1000$.

Experimental Parameters

• Exact solution generation: $x_\dagger = \|(A_\dagger^*A_\dagger)^\nu x_e\|_{\ell^\infty}^{-1}(A_\dagger^*A_\dagger)^\nu x_e$
• Noise setting: $y^\delta_i = y_{\dagger,i} + \epsilon\|y_\dagger\|_{\ell^\infty}\xi_i$, $\xi_i \sim \mathcal{N}(0,1)$
• Step-size: Landweber method uses $c_0 = \|A_\dagger\|^{-2}$, (r)SVRG uses $c_0 = O(c)$, where $c = L^{-1}$
• Frequency: $M = 2n$
• Maximum iterations: $10^5$ rounds

Comparison Methods

• Landweber Method (LM): Classical iterative regularization method with discrepancy principle stopping
• Standard SVRG: Uses optimal error point stopping
• Regularized SVRG (rSVRG): Uses theoretically guided stopping criterion

Experimental Results

Main Theoretical Result (Theorem 2.1)

Under Assumption 2.1, there exists a constant $c^*$ independent of $k, n, \delta$ such that:

Expected convergence rate: