2025-11-16T17:31:12.997131

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

Jin, Zhou

Stochastic variance reduced gradient (SVRG) is an accelerated version of stochastic gradient descent based on variance reduction, and is promising for solving large-scale inverse problems. In this work, we analyze SVRG and a regularized version that incorporates a priori knowledge of the problem, for solving linear inverse problems in Hilbert spaces. We prove that, with suitable constant step size schedules and regularity conditions, the regularized SVRG can achieve optimal convergence rates in terms of the noise level without any early stopping rules, and standard SVRG is also optimal for problems with nonsmooth solutions under a priori stopping rules. The analysis is based on an explicit error recursion and suitable prior estimates on the inner loop updates with respect to the anchor point. Numerical experiments are provided to complement the theoretical analysis.

academic

線形逆問題に対する確率的分散縮減勾配法の収束性について

基本情報

論文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$

研究の動機

大規模問題への需要：線形逆問題はコンピュータ断層撮影、陽電子放出断層撮影など実際の応用に広く現れ、データ規模が膨大
既存手法の限界：従来の反復法は大規模問題に対して計算効率が低い
SVRGの利点：確率的分散縮減勾配法は優れたスケーラビリティを持つが、逆問題における理論分析がまだ不完全
正則化の必要性：標準SVRGは早期停止規則を必要とするが、先験知識の組み込みがこれを改善する可能性

核心的貢献

理論分析の完善：線形逆問題を解くSVRGと正則化SVRG（rSVRG）の完全な収束理論を確立
最適収束率：適切な条件下で両手法が最適収束率 $O(\delta^{2\nu/(1+2\nu)})$ を達成することを証明
正則化特性：rSVRGは内在的な正則化機構を持ち、早期停止を不要にする。標準SVRGも先験的停止下で正則化特性を持つ
期待値と一様収束：期待値意味と一様意味での収束率を同時に確立し、既存結果を拡張
条件の緩和：既存研究と比べて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（アルゴリズム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（アルゴリズム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$ を満たす主要な特異値を保持。

核心的仮定（仮定2.1）

ステップサイズ条件： $\eta_j = c_0 \leq L^{-1}$ 、ここで $L = \max_{1\leq i\leq n}\|A_i\|^2$
ソース条件： $\nu > 0$ と $w \in N(A_\dagger)^\perp$ が存在して $x_\dagger - x_0 = B_\dagger^\nu w$
作用素近似： $a > 0$ の場合、 $A$ は切り詰められたSVDにより構築され、 $\sigma_j \geq a\delta^b$ の特異値を保持

技術的革新点

誤差分解戦略：誤差をバイアスと分散の2つの部分に分解し、それぞれを正確に推定
錨点分析：内ループ更新の錨点に対する相対的な動作を分析することで、重要な事前推定を確立
統一的枠組み：標準SVRGと正則化SVRGを扱うための統一的な理論枠組みを提供

実験設定

データセット

Regutoolsパッケージの3つの標準逆問題を使用：

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）：理論指導の停止準則を使用

実験結果

主要な理論結果（定理2.1）

仮定2.1の下で、 $k,n,\delta$ に無関な定数 $c^*$ が存在して：

期待値収束率： $E[\|e_k^\delta\|^2]^{1/2} \leq c^*k^{-\min(\nu,1/2)} + c^*\begin{cases} \delta^{2\nu/(1+2\nu)}, & a > 0 \\ n^{-1/2}\sqrt{k}\delta, & a = 0 \end{cases}$

一様収束率： $\|e_k^\delta\| \leq \sqrt{n}c^*k^{-1/2+\max(1/2-\nu,0)} + c^*\begin{cases} \delta^{2\nu/(1+2\nu)}, & a > 0 \\ n^{-1/2}\sqrt{k}\delta, & a = 0 \end{cases}$