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

基本信息

• 论文ID: 2510.14759
• 标题: On the convergence of stochastic variance reduced gradient for linear inverse problems
• 作者: Bangti Jin, Zehui Zhou (香港中文大学数学系)
• 分类: math.NA cs.NA math.OC
• 发表时间: 2025年10月16日 (arXiv预印本)
• 论文链接: https://arxiv.org/abs/2510.14759

摘要

随机方差缩减梯度法(SVRG)是基于方差缩减的随机梯度下降加速版本，在解决大规模逆问题方面具有前景。本文分析了SVRG及其结合先验知识的正则化版本，用于求解Hilbert空间中的线性逆问题。研究证明，在合适的常数步长调度和正则性条件下，正则化SVRG可以在噪声水平方面达到最优收敛率，无需任何早停规则；标准SVRG在先验停止规则下对非光滑解问题也是最优的。分析基于显式误差递归和关于锚点的内循环更新的合适先验估计。

研究背景与动机

问题描述

本文研究Hilbert空间中的线性逆问题： $A_\dagger x = y_\dagger$

其中：

• $A_\dagger: X \to Y = Y_1 \times \cdots \times Y_n$ 是系统算子
• $x \in X$ 是未知信号，$y_\dagger \in Y$ 是精确数据
• 实际只能获得噪声数据 $y^\delta = y_\dagger + \xi$，噪声水平 $\delta = \|\xi\|_Y$

研究动机

1. 大规模问题需求：线性逆问题广泛出现在计算机断层扫描、正电子发射断层扫描等实际应用中，数据规模庞大
2. 现有方法局限：传统迭代方法在大规模问题上计算效率低下
3. SVRG优势：随机方差缩减梯度法具有优秀的可扩展性，但其在逆问题中的理论分析尚不完善
4. 正则化需求：标准SVRG需要早停规则来实现正则化，而先验知识的融入可能改善这一情况

核心贡献

1. 理论分析完善：建立了SVRG和正则化SVRG(rSVRG)求解线性逆问题的完整收敛理论
2. 最优收敛率：证明了在合适条件下两种方法都能达到最优收敛率 $O(\delta^{2\nu/(1+2\nu)})$
3. 正则化性质：rSVRG具有内在正则化机制，无需早停规则；标准SVRG在先验停止下也具有正则化性质
4. 期望和一致收敛：同时建立了期望意义和一致意义下的收敛率，扩展了已有结果
5. 条件放宽：相比已有工作，对SVRG最优收敛的条件更加宽松

方法详解

任务定义

考虑优化问题： $J(x) = \frac{1}{2n}\|A_\dagger x - y^\delta\|_Y^2 = \frac{1}{n}\sum_{i=1}^n f_i(x)$ 其中 $f_i(x) = \frac{1}{2}\|A_{\dagger,i}x - y^\delta_i\|_{Y_i}^2$

算法架构

标准SVRG (Algorithm 1)

初始化: x₀^δ = x₀, 频率M, 步长{ηₖ}
for K = 0,1,... do
    计算 gₖ = J'(x_{KM}^δ) = (1/n)A_†*(A_†x_{KM}^δ - y^δ)
    for t = 0,1,...,M-1 do
        随机采样 i_{KM+t} ∈ {1,...,n}
        更新 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

正则化SVRG (Algorithm 2)

将算子$A_\dagger$替换为近似算子$A$，通过截断奇异值分解获得： $A(\cdot) = \sum_{j=1}^J \sigma_j\langle\phi_j, \cdot\rangle\psi_j$ 其中保留满足$\sigma_j \geq a\delta^b$的主要奇异值。

核心假设 (Assumption 2.1)

1. 步长条件：$\eta_j = c_0 \leq L^{-1}$，其中$L = \max_{1\leq i\leq n}\|A_i\|^2$
2. 源条件：存在$\nu > 0$和$w \in N(A_\dagger)^\perp$使得$x_\dagger - x_0 = B_\dagger^\nu w$
3. 算子近似：当$a > 0$时，$A$通过截断SVD构造，保留$\sigma_j \geq a\delta^b$的奇异值

技术创新点

1. 误差分解策略：将误差分解为偏差和方差两部分，分别进行精确估计
2. 锚点分析：通过分析内循环更新相对于锚点的行为，建立关键的先验估计
3. 统一框架：提供了处理标准SVRG和正则化SVRG的统一理论框架

实验设置

数据集

使用Regutools包中的三个标准逆问题：

• s-phillips: 轻度病态问题 (mildly ill-posed)
• s-gravity: 严重病态问题 (severely ill-posed)
• s-shaw: 严重病态问题 (severely ill-posed)

所有问题离散化为$n = m = 1000$的有限维线性系统。

实验参数

• 精确解生成：$x_\dagger = \|(A_\dagger^*A_\dagger)^\nu x_e\|_{\ell^\infty}^{-1}(A_\dagger^*A_\dagger)^\nu x_e$
• 噪声设置：$y^\delta_i = y_{\dagger,i} + \epsilon\|y_\dagger\|_{\ell^\infty}\xi_i$，$\xi_i \sim \mathcal{N}(0,1)$
• 步长：Landweber方法用$c_0 = \|A_\dagger\|^{-2}$，(r)SVRG用$c_0 = O(c)$，其中$c = L^{-1}$
• 频率：$M = 2n$
• 最大迭代：$10^5$轮

对比方法

• Landweber方法(LM)：经典迭代正则化方法，使用差异原理停止
• 标准SVRG：使用最优误差点停止
• 正则化SVRG(rSVRG)：使用理论指导的停止准则

实验结果

主要理论结果 (Theorem 2.1)

在Assumption 2.1下，存在与$k,n,\delta$无关的常数$c^*$使得：

期望收敛率：