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

Sur la convergence du gradient stochastique à variance réduite pour les problèmes inverses linéaires

Informations de base

ID de l'article: 2510.14759
Titre: On the convergence of stochastic variance reduced gradient for linear inverse problems
Auteurs: Bangti Jin, Zehui Zhou (Département de Mathématiques, Université Chinoise de Hong Kong)
Classification: math.NA cs.NA math.OC
Date de publication: 16 octobre 2025 (prépublication arXiv)
Lien de l'article: https://arxiv.org/abs/2510.14759

Résumé

La méthode du gradient stochastique à variance réduite (SVRG) est une version accélérée de la descente de gradient stochastique basée sur la réduction de variance, prometteuse pour résoudre les problèmes inverses à grande échelle. Cet article analyse le SVRG et sa version régularisée combinant les connaissances préalables pour résoudre les problèmes inverses linéaires dans les espaces de Hilbert. L'étude démontre que, sous un calendrier de pas constant approprié et des conditions de régularité, le SVRG régularisé peut atteindre un taux de convergence optimal en fonction du niveau de bruit, sans aucune règle d'arrêt anticipé; le SVRG standard est également optimal pour les problèmes à solutions non lisses sous une règle d'arrêt préalable. L'analyse repose sur des récursions d'erreur explicites et des estimations préalables appropriées concernant les mises à jour de la boucle interne par rapport aux points d'ancrage.

Contexte et motivation de la recherche

Description du problème

Cet article étudie les problèmes inverses linéaires dans les espaces de Hilbert: $A_\dagger x = y_\dagger$

où:

$A_\dagger: X \to Y = Y_1 \times \cdots \times Y_n$ est l'opérateur système
$x \in X$ est le signal inconnu, $y_\dagger \in Y$ sont les données exactes
En pratique, seules les données bruitées $y^\delta = y_\dagger + \xi$ sont disponibles, avec le niveau de bruit $\delta = \|\xi\|_Y$

Motivation de la recherche

Besoin de problèmes à grande échelle: Les problèmes inverses linéaires apparaissent largement dans les applications pratiques telles que la tomographie par ordinateur et la tomographie par émission de positons, avec des volumes de données considérables
Limitations des méthodes existantes: Les méthodes itératives traditionnelles manquent d'efficacité computationnelle sur les problèmes à grande échelle
Avantages du SVRG: La méthode du gradient stochastique à variance réduite possède une excellente scalabilité, mais son analyse théorique dans les problèmes inverses reste incomplète
Besoin de régularisation: Le SVRG standard nécessite une règle d'arrêt anticipé pour réaliser la régularisation, et l'intégration de connaissances préalables pourrait améliorer cette situation

Contributions principales

Analyse théorique complète: Établissement d'une théorie de convergence complète pour le SVRG et le SVRG régularisé (rSVRG) appliqués aux problèmes inverses linéaires
Taux de convergence optimal: Preuve que les deux méthodes atteignent le taux de convergence optimal $O(\delta^{2\nu/(1+2\nu)})$ sous des conditions appropriées
Propriétés de régularisation: Le rSVRG possède un mécanisme de régularisation intrinsèque sans nécessiter d'arrêt anticipé; le SVRG standard possède également des propriétés de régularisation sous arrêt préalable
Convergence en espérance et presque sûre: Établissement simultané des taux de convergence en espérance et au sens presque sûr, étendant les résultats existants
Conditions assouplies: Par rapport aux travaux antérieurs, les conditions pour la convergence optimale du SVRG sont plus souples

Détails de la méthode

Définition de la tâche

Considérer le problème d'optimisation: $J(x) = \frac{1}{2n}\|A_\dagger x - y^\delta\|_Y^2 = \frac{1}{n}\sum_{i=1}^n f_i(x)$ où $f_i(x) = \frac{1}{2}\|A_{\dagger,i}x - y^\delta_i\|_{Y_i}^2$

Architecture de l'algorithme

SVRG standard (Algorithme 1)

Initialisation: x₀^δ = x₀, fréquence M, pas {ηₖ}
pour K = 0,1,... faire
    Calculer gₖ = J'(x_{KM}^δ) = (1/n)A_†*(A_†x_{KM}^δ - y^δ)
    pour t = 0,1,...,M-1 faire
        Échantillonner aléatoirement i_{KM+t} ∈ {1,...,n}
        Mettre à jour x_{KM+t+1}^δ = x_{KM+t}^δ - η_{KM+t}(A*_{i_{KM+t}}A_{i_{KM+t}}(x_{KM+t}^δ - x_{KM}^δ) + gₖ)
    fin pour
fin pour

SVRG régularisé (Algorithme 2)

Remplacer l'opérateur $A_\dagger$ par un opérateur approché $A$ , obtenu par décomposition en valeurs singulières tronquées: $A(\cdot) = \sum_{j=1}^J \sigma_j\langle\phi_j, \cdot\rangle\psi_j$ où sont conservées les valeurs singulières principales satisfaisant $\sigma_j \geq a\delta^b$ .

Hypothèses principales (Hypothèse 2.1)

Condition de pas: $\eta_j = c_0 \leq L^{-1}$ , où $L = \max_{1\leq i\leq n}\|A_i\|^2$
Condition source: Il existe $\nu > 0$ et $w \in N(A_\dagger)^\perp$ tels que $x_\dagger - x_0 = B_\dagger^\nu w$
Approximation d'opérateur: Lorsque $a > 0$ , $A$ est construit par SVD tronquée, conservant les valeurs singulières $\sigma_j \geq a\delta^b$

Points d'innovation technique

Stratégie de décomposition d'erreur: Décomposition de l'erreur en parties de biais et de variance, avec estimation précise de chacune
Analyse des points d'ancrage: Établissement d'estimations préalables clés par analyse du comportement des mises à jour de la boucle interne par rapport aux points d'ancrage
Cadre unifié: Fourniture d'un cadre théorique unifié pour traiter le SVRG standard et le SVRG régularisé

Configuration expérimentale

Ensembles de données

Utilisation de trois problèmes inverses standard du package Regutools:

s-phillips: Problème faiblement mal posé
s-gravity: Problème fortement mal posé
s-shaw: Problème fortement mal posé

Tous les problèmes sont discrétisés en systèmes linéaires de dimension finie avec $n = m = 1000$ .

Paramètres expérimentaux

Génération de solution exacte: $x_\dagger = \|(A_\dagger^*A_\dagger)^\nu x_e\|_{\ell^\infty}^{-1}(A_\dagger^*A_\dagger)^\nu x_e$
Configuration du bruit: $y^\delta_i = y_{\dagger,i} + \epsilon\|y_\dagger\|_{\ell^\infty}\xi_i$ , $\xi_i \sim \mathcal{N}(0,1)$
Pas: Méthode de Landweber utilisant $c_0 = \|A_\dagger\|^{-2}$ , (r)SVRG utilisant $c_0 = O(c)$ , où $c = L^{-1}$
Fréquence: $M = 2n$
Itérations maximales: $10^5$ tours

Méthodes de comparaison

Méthode de Landweber (LM): Méthode itérative de régularisation classique, utilisant le principe de discordance pour l'arrêt
SVRG standard: Utilisant l'arrêt au point d'erreur optimal
SVRG régularisé (rSVRG): Utilisant le critère d'arrêt guidé par la théorie

Résultats expérimentaux

Résultat théorique principal (Théorème 2.1)

Sous l'Hypothèse 2.1, il existe une constante $c^*$ indépendante de $k,n,\delta$ telle que:

Taux de convergence en espérance:

undefined