Sulla convergenza del gradiente stocastico con varianza ridotta per problemi inversi lineari

Informazioni Fondamentali

• ID Articolo: 2510.14759
• Titolo: On the convergence of stochastic variance reduced gradient for linear inverse problems
• Autori: Bangti Jin, Zehui Zhou (Dipartimento di Matematica, Università Cinese di Hong Kong)
• Classificazione: math.NA cs.NA math.OC
• Data di Pubblicazione: 16 ottobre 2025 (preprint arXiv)
• Link Articolo: https://arxiv.org/abs/2510.14759

Riassunto

Il metodo del gradiente stocastico con varianza ridotta (SVRG) è una versione accelerata della discesa del gradiente stocastico basata sulla riduzione della varianza, che mostra promesse nella risoluzione di problemi inversi su larga scala. Questo articolo analizza SVRG e la sua versione regolarizzata che incorpora conoscenze a priori, per la risoluzione di problemi inversi lineari nello spazio di Hilbert. La ricerca dimostra che, con opportuni programmi di step-size costante e condizioni di regolarità, SVRG regolarizzato può raggiungere il tasso di convergenza ottimale rispetto al livello di rumore, senza necessità di alcuna regola di arresto anticipato; SVRG standard è ottimale anche per problemi con soluzioni non lisce sotto una regola di arresto a priori. L'analisi si basa su ricorrenze di errore esplicite e opportune stime a priori riguardanti gli aggiornamenti del ciclo interno rispetto al punto di ancoraggio.

Contesto di Ricerca e Motivazione

Descrizione del Problema

Questo articolo studia problemi inversi lineari nello spazio di Hilbert: $A_\dagger x = y_\dagger$

dove:

• $A_\dagger: X \to Y = Y_1 \times \cdots \times Y_n$ è l'operatore di sistema
• $x \in X$ è il segnale incognito, $y_\dagger \in Y$ sono i dati esatti
• In pratica si possono ottenere solo dati rumorosi $y^\delta = y_\dagger + \xi$, con livello di rumore $\delta = \|\xi\|_Y$

Motivazione della Ricerca

1. Necessità di Problemi su Larga Scala: I problemi inversi lineari si presentano ampiamente in applicazioni pratiche come la tomografia computerizzata e la tomografia a emissione di positroni, con volumi di dati considerevoli
2. Limitazioni dei Metodi Esistenti: I metodi iterativi tradizionali mostrano bassa efficienza computazionale su problemi su larga scala
3. Vantaggi di SVRG: Il metodo del gradiente stocastico con varianza ridotta possiede eccellente scalabilità, ma la sua analisi teorica nei problemi inversi rimane incompleta
4. Necessità di Regolarizzazione: SVRG standard richiede regole di arresto anticipato per realizzare la regolarizzazione, mentre l'incorporazione di conoscenze a priori potrebbe migliorare questa situazione

Contributi Fondamentali

1. Analisi Teorica Completa: Stabilisce la teoria di convergenza completa per SVRG e SVRG regolarizzato (rSVRG) nella risoluzione di problemi inversi lineari
2. Tasso di Convergenza Ottimale: Dimostra che entrambi i metodi possono raggiungere il tasso di convergenza ottimale $O(\delta^{2\nu/(1+2\nu)})$ in condizioni appropriate
3. Proprietà di Regolarizzazione: rSVRG possiede un meccanismo di regolarizzazione intrinseco, senza necessità di arresto anticipato; SVRG standard possiede anche proprietà di regolarizzazione sotto arresto a priori
4. Convergenza in Aspettativa e Quasi Certa: Stabilisce simultaneamente tassi di convergenza in senso di aspettativa e quasi certo, estendendo i risultati esistenti
5. Rilassamento delle Condizioni: Rispetto ai lavori precedenti, le condizioni per la convergenza ottimale di SVRG sono più rilassate

Dettagli del Metodo

Definizione del Compito

Considerare il problema di ottimizzazione: $J(x) = \frac{1}{2n}\|A_\dagger x - y^\delta\|_Y^2 = \frac{1}{n}\sum_{i=1}^n f_i(x)$ dove $f_i(x) = \frac{1}{2}\|A_{\dagger,i}x - y^\delta_i\|_{Y_i}^2$

Architettura dell'Algoritmo

SVRG Standard (Algoritmo 1)

Inizializzazione: x₀^δ = x₀, frequenza M, step-size {ηₖ}
for K = 0,1,... do
    Calcola gₖ = J'(x_{KM}^δ) = (1/n)A_†*(A_†x_{KM}^δ - y^δ)
    for t = 0,1,...,M-1 do
        Campiona casualmente i_{KM+t} ∈ {1,...,n}
        Aggiorna 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 Regolarizzato (Algoritmo 2)

Sostituire l'operatore $A_\dagger$ con un operatore approssimato $A$, ottenuto mediante decomposizione ai valori singolari troncata: $A(\cdot) = \sum_{j=1}^J \sigma_j\langle\phi_j, \cdot\rangle\psi_j$ dove si conservano i valori singolari principali che soddisfano $\sigma_j \geq a\delta^b$.

Ipotesi Fondamentali (Assunzione 2.1)

1. Condizione di Step-Size: $\eta_j = c_0 \leq L^{-1}$, dove $L = \max_{1\leq i\leq n}\|A_i\|^2$
2. Condizione di Sorgente: Esistono $\nu > 0$ e $w \in N(A_\dagger)^\perp$ tali che $x_\dagger - x_0 = B_\dagger^\nu w$
3. Approssimazione dell'Operatore: Quando $a > 0$, $A$ è costruito mediante SVD troncata, conservando i valori singolari $\sigma_j \geq a\delta^b$

Punti di Innovazione Tecnica

1. Strategia di Decomposizione dell'Errore: Decompone l'errore in componenti di bias e varianza, stimando ciascuna precisamente
2. Analisi del Punto di Ancoraggio: Attraverso l'analisi del comportamento degli aggiornamenti del ciclo interno rispetto al punto di ancoraggio, stabilisce stime a priori critiche
3. Framework Unificato: Fornisce un framework teorico unificato per trattare SVRG standard e SVRG regolarizzato

Configurazione Sperimentale

Insiemi di Dati

Utilizza tre problemi inversi standard dal pacchetto Regutools:

• s-phillips: Problema leggermente mal posto (mildly ill-posed)
• s-gravity: Problema gravemente mal posto (severely ill-posed)
• s-shaw: Problema gravemente mal posto (severely ill-posed)

Tutti i problemi sono discretizzati in sistemi lineari a dimensione finita con $n = m = 1000$.

Parametri Sperimentali

• Generazione della Soluzione Esatta: $x_\dagger = \|(A_\dagger^*A_\dagger)^\nu x_e\|_{\ell^\infty}^{-1}(A_\dagger^*A_\dagger)^\nu x_e$
• Impostazione del Rumore: $y^\delta_i = y_{\dagger,i} + \epsilon\|y_\dagger\|_{\ell^\infty}\xi_i$, $\xi_i \sim \mathcal{N}(0,1)$
• Step-Size: Metodo di Landweber usa $c_0 = \|A_\dagger\|^{-2}$, (r)SVRG usa $c_0 = O(c)$, dove $c = L^{-1}$
• Frequenza: $M = 2n$
• Iterazioni Massime: $10^5$ cicli

Metodi di Confronto

• Metodo di Landweber (LM): Metodo iterativo di regolarizzazione classico, con arresto mediante principio di discrepanza
• SVRG Standard: Utilizza arresto al punto di errore ottimale
• SVRG Regolarizzato (rSVRG): Utilizza criterio di arresto guidato dalla teoria

Risultati Sperimentali

Risultato Teorico Principale (Teorema 2.1)

Sotto l'Assunzione 2.1, esiste una costante $c^*$ indipendente da $k,n,\delta$ tale che:

Tasso di Convergenza in Aspettativa: