Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

Sintesi Tecnica: Approssimazione Stocastica a Due Scale Temporali Non Espansiva

Enunciato del Problema
Il paper investiga i tassi di convergenza dell'approssimazione stocastica a due scale temporali (TTSA) in un regime in cui la mappa veloce è contrattiva, ma la mappa lenta ridotta è solo non espansiva. Questo scenario emerge nell'ottimizzazione minimax, nelle disuguaglianze variazionali e nell'approssimazione stocastica vincolata. A differenza della TTSA contrattiva, dove la variabile lenta converge a un equilibrio unico, il caso non espansivo presenta un insieme di punti fissi potenzialmente non singleton. Di conseguenza, la metrica di prestazione naturale è il residuo del punto fisso $p(y) = h(y) - y$ piuttosto che la distanza da un punto specifico.

Il lavoro precedente ha stabilito un tasso di residuo della media dei quadrati dell'ultimo iterato pari a $O(k^{-1/4+\epsilon})$ per questo regime. Il presente articolo mira a spiegare l'origine teorica di questo esponente $1/4$ e a determinare se modifiche algoritmiche possano migliorarlo.

Metodologia e Quadro Teorico
Gli autori decompongono la dinamica dell'errore in due componenti distinte: la convergenza intrinseca della ricorsione lenta non espansiva e la "perdita" (leakage) degli errori di inseguimento veloce nell'oracolo lento.

1. Nitidezza della Barriera KM a Step-Size Fisso:
   Il paper stabilisce innanzitutto che la classica scala del residuo di Krasnoselskii–Mann (KM), definita dall'inverso della somma $\sum \beta_i(1-\beta_i)$, è netta per qualsiasi schema di step-size lenta $(\beta_k)$ fisso. Utilizzando un esempio di rotazione planare, gli autori dimostrano un limite inferiore a orizzonte finito mostrando che nessun aggiornamento KM non regolarizzato può raggiungere un decadimento del residuo peggiore di questa scala per un dato schema. Ciò implica che migliorare il tasso richiede il cambiamento del regime algoritmico o della struttura dell'oracolo, non la mera raffinazione dell'analisi del tipico aggiornamento KM.

2. Diagnosi dell'Esponente $1/4$:
   Il paper identifica la "perdita della prima-ordine dalla varietà veloce" (first-order fast-manifold leakage) come l'ostacolo primario. Nella TTSA grezza, l'oracolo lento valuta la mappa al valore corrente dell'iterato veloce $X_k$ invece del vero equilibrio $x^*(Y_k)$. A causa della continuità Lipschitz della mappa lenta nella coordinata veloce, l'errore $g(X_k, Y_k) - h(Y_k)$ è del primo ordine rispetto all'errore di inseguimento $\|X_k - x^*(Y_k)\|$. L'errore di inseguimento stesso è governato da un bilanciamento tra la varianza stocastica veloce ($\alpha_k$) e il ritardo deterministico dietro il target mobile ($(\beta_k/\alpha_k)^2$). Anche sotto la standard condizione di separazione $\beta_k^2/\alpha_k^3 \lesssim 1$, la combinazione della scala KM netta e di questa perdita del primo ordine produce un numero totale di campioni di $T^{-1/4+o(1)}$. Violare la condizione di separazione non migliora il tasso; sposta semplicemente il collo di bottiglia dalla varianza statistica al ritardo del target mobile, che entra comunque come perturbazione del primo ordine.

3. Correzione del Bias tramite Precondizionamento del Residuo:
   Per superare la perdita del primo ordine, gli autori introducono un oracolo lento precondizionato dal residuo. Utilizzando le derivate delle mappe veloce e lenta, costruiscono un termine di correzione che annulla la dipendenza lineare dall'errore di inseguimento veloce.
   Nello specifico, se $A(y) = I - \nabla_x f(x^*(y), y)$ e $C(y) = \nabla_x g(x^*(y), y)$, il precondizionatore è $P^*(y) = C(y)A(y)^{-1}$. L'oracolo corretto è definito come:
   $$H_{corr}(x, y) = g(x, y) + P^*(y)(f(x, y) - x)$$
   L'espansione di Taylor mostra che questa correzione riduce il bias dell'oracolo lento dal primo ordine ($O(\|e\|)$) al secondo ordine ($O(\|e\|^2)$), dove $e$ è l'errore di inseguimento veloce.

Contributi Chiave e Risultati

Il paper presenta tre risultati teorici principali, progredendo dalla diagnosi del metodo grezzo ad algoritmi ottimizzati sotto assunzioni di oracolo strutturato.

1. Limite Inferiore per lo Schema a Step-Size Fisso:
   Gli autori dimostrano che per qualsiasi schema di step-size lenta fisso, il residuo della media dei quadrati dell'iterazione KM non regolarizzata non può migliorare uniformemente la scala $(\sum \beta_i(1-\beta_i))^{-1}$. Questo conferma che l'esponente $1/4$ nella letteratura precedente non è un artefatto di un'analisi debole, ma una conseguenza della scala netta KM combinata con la perdita del primo ordine.

2. Algoritmo Annidato con Correzione del Bias ($T^{-1/3}$):
   In un framework Tikhonov-KM annidato, gli autori applicano il precondizionamento del residuo.

• Non corretto: Il metodo annidato con un oracolo grezzo raggiunge un tasso di campionamento totale di $T^{-1/4+o(1)}$.
• Corretto: Utilizzando l'oracolo precondizionato, il bias al quadrato dell'oracolo lento diventa $O(n^{-2})$ (dove $n$ è il numero di campioni interni) invece di $O(n^{-1})$. Questo cambiamento strutturale migliora la complessità totale di campionamento a $T^{-1/3+o(1)}$.
• Nota: Questo risultato assume l'accesso al precondizionatore esatto $P^*(y)$ o a un estimatore che soddisfi specifiche condizioni di accuratezza del prodotto.

3. Precondizionatore Appreso a Ciclo Singolo ($T^{-1/2}$):
   Per evitare il costo ripetuto delle risoluzioni nei cicli interni del metodo annidato, gli autori propongono un algoritmo a ciclo singolo che traccia online l'equilibrio veloce, la variabile lenta e la matrice del precondizionatore.

• Questo metodo mantiene stime correnti di $X_k$, $Y_k$ e $P_k$ utilizzando osservazioni di derivate stocastiche.
• Sotto assunzioni di regolarità (differenziabilità delle mappe e accesso a oracoli di derivata), questo approccio raggiunge un tasso di campionamento totale di $T^{-1/2+o(1)}$ con $O(1)$ campioni primitivi per iterazione.
• Questo miglioramento si basa sulla capacità di apprendere online il precondizionatore della perdita (leakage), ammortizzando efficacementmente il costo della risoluzione interna.

Significatività e Rivendicazioni
Il paper sostiene di fornire una spiegazione teorica completa dell'esponente $1/4$ nella TTSA non espansiva, attribuendolo all'interazione tra la scala del residuo KM netta e la perdita del primo ordine della varietà veloce. Il contributo principale è dimostrare che questa barriera non è fondamentale per la classe di problemi, ma è specifica della struttura dell'oracolo "grezzo".

Introducendo un oracolo precondizionato dal residuo, gli autori mostrano che la perdita può essere ridotta al secondo ordine, migliorando così i tassi di convergenza. Il risultato $T^{-1/3}$ funge da certificato dell'efficacia della correzione del bias, mentre il risultato $T^{-1/2}$ dimostra che questi guadagni possono essere realizzati in un contesto a ciclo singolo se sono disponibili informazioni sulle derivate. Gli autori inquadrano esplicitamente questi risultati come successi di "oracoli strutturati", notando che essi si basano sulla differenziabilità e sull'accesso alle informazioni del Jacobiano, distinguendosi dai metodi a punti fissi non espansivi "black-box". Il lavoro non pretende di risolvere il problema per oracoli black-box generali, ma identifica la specifica modifica strutturale (cancellazione del bias) necessaria per accelerare la convergenza in presenza di regolarità (smoothness).