Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

Riepilogo Tecnico: Ottimizzazione Composita Stocastica tramite Frank–Wolfe Ibrido con Momento

Formulazione del Problema
Questo lavoro affronta il problema di ottimizzazione composita stocastica di minimizzare obiettivi della forma:
$$\min_{x \in X} \phi(x) := F(f(x), x)$$
dove $X \subset \mathbb{R}^d$ è un insieme convesso e compatto, $f: X \to \mathbb{R}^n$ è una mappatura interna accessibile solo tramite query stocastiche rumorose ($f(x) = \mathbb{E}_\xi[\tilde{f}(x; \xi)]$), e $F: \mathbb{R}^n \times X \to \mathbb{R}$ è una funzione esterna deterministica.

La sfida principale nell'impostazione stocastica è che gli stimatori di inserimento diretto (plug-in) sono distorti a causa della disuguaglianza di Jensen ($\mathbb{E}[F(\tilde{f}(x; \xi), x)] \neq F(\mathbb{E}[\tilde{f}(x; \xi)], x)$). Sebbene i metodi stocastici esistenti (ad esempio SCGD, NASA, SCSC) affrontino questo bias utilizzando traccianti basati sul momento e la regola della catena, richiedono fondamentalmente che la funzione esterna $F$ sia continuamente differenziabile. Questa ipotesi esclude molte applicazioni critiche che coinvolgono funzioni esterne non lisce, come il massimo robusto delle perdite, il Conditional Value-at-Risk (CVaR) e i regolarizzatori di norma. Inoltre, i metodi stocastici esistenti privi di proiezione (ad esempio LiNASA+ICG) dipendono anch'essi dalla regolarità di $F$.

Metodologia
Gli autori propongono l'algoritmo Frank–Wolfe Stocastico Ibrido con Momento, il primo metodo privo di proiezione per problemi completamente compositi in grado di gestire funzioni esterne non lisce. L'innovazione fondamentale risiede nella sostituzione dell'aggiornamento basato sul gradiente standard con un Oracolo di Minimizzazione Lineare Generalizzato (GLMO) che opera su un surrogato affine stocastico.

L'algoritmo mantiene due traccianti stocastici ad ogni iterazione $k$:

1. Tracciante Jacobiano ($V_k$): Uno stimatore di tipo Polyak per il momento della matrice Jacobiana $\nabla f(y_k)$.
2. Tracciante Funzione ($z_k$): Uno stimatore per il valore della funzione $f(y_k)$.

L'algoritmo offre due varianti per il tracciante della funzione per bilanciare l'uso della memoria e le ipotesi:

• Variante I (Polyak): Senza memoria ma richiede che la funzione interna $f$ sia lipschitziana.
• Variante II (Corretta con Taylor): Richiede la memorizzazione dell'iterata precedente ma elimina l'ipotesi di lipschitzianità su $f$ utilizzando un'estrapolazione di Taylor del primo ordine ($V_k(y_k - y_{k-1})$) per prevedere il valore della funzione, riducendo l'errore di tracciamento a un residuo quadratico.

Ad ogni passo, l'algoritmo costruisce un surrogato affine $\tilde{l}_k(x) = z_k + V_k(x - y_k)$ e lo invia al GLMO:
$$x_{k+1} \in \arg\min_{x \in X} F(\tilde{l}_k(x), x)$$
Crucialmente, il GLMO tratta $F$ come una scatola nera, minimizzandola direttamente sulla funzione interna linearizzata senza richiedere un sottomariente di $F$. Ciò permette al metodo di gestire $F$ non lisce (ad esempio, norme $\ell_p$, funzioni max) in modo efficiente, riducendo spesso la chiamata all'oracolo a un Programma Lineare (LP) o a un Programma a Cono di Secondo Ordine (SOCP).

Contributi Chiave

1. Novità Algoritmica: Introduzione del primo algoritmo stocastico privo di proiezione per l'ottimizzazione completamente composita con funzioni esterne non lisce.
2. Garanzie Teoriche sotto Rumore a Coda Pesante: L'analisi assume che l'oracolo stocastico abbia momenti $r$-esimi limitati ($r \in (1, 2]$), coprendo scenari di rumore a coda pesante.
   • Caso Non Convesso: L'algoritmo raggiunge un tasso di convergenza di $O(K^{-(r-1)/(3r-2)})$ nel gap generalizzato di Frank–Wolfe. Per varianza finita ($r=2$), ciò produce $O(K^{-1/4})$, corrispondente al limite inferiore minimassimo ottimale per metodi stocastici privi di proiezione con singolo campione sotto regolarità attesa.
   • Caso Convesso: Sotto ipotesi di convessità congiunta, il tasso primale è $O(K^{-(r-1)/(2r-1)})$, recuperando $O(K^{-1/3})$ quando $r=2$.
3. Interpolazione Deterministica: L'algoritmo interpola senza soluzione di continuità con il regime deterministico. Quando l'oracolo è esatto (rumore zero), impostando i parametri del momento a 1 si recupera il Metodo Base deterministico di Vladarean et al. [2023] con i suoi tassi ottimali ($O(1/K)$ per convesso, $\tilde{O}(1/\sqrt{K})$ per non convesso).
4. Accelerazione: Sotto ipotesi più forti di regolarità media $r$ (o momenti limitati del rumore dell'Hessiano), il framework si integra con la riduzione della varianza STORM o con il momento corretto dall'Hessiano per accelerare il tasso non convesso a $O(K^{-1/3})$ (per $r=2$).

Risultati ed Esperimenti
Il documento convalida le scoperte teoriche attraverso esperimenti numerici su tre problemi del mondo reale caratterizzati da $F$ non liscia e rumore a coda pesante:

• Regressione Sparsa Minimax Robusta: Minimizzazione della perdita nel caso peggiore su sottoinsiemi di dati.
• Ottimizzazione di Portafoglio CVaR: Ottimizzazione avversione al rischio sui rendimenti dell'S&P 500.
• Completamento di Matrici Robusto: Utilizzo della perdita $\ell_1$ sul dataset MovieLens-100K.

I risultati sperimentali dimostrano che il Frank–Wolfe composito stocastico standard (Vanilla SCFW) non converge a causa del bias, e le varianti troncate raggiungono un plateau. Al contrario, entrambe le varianti proposte (Polyak e Taylor) raggiungono il tasso di convergenza previsto di $O(K^{-1/4})$. La variante Taylor (Variante II) risulta teoricamente robusta anche quando l'ipotesi di lipschitzianità su $f$ non può essere verificata, sebbene la variante Polyak performi leggermente meglio nei regimi in cui l'ipotesi vale.

Significato
Il documento afferma di risolvere un problema aperto identificato da Vladarean et al. [2023] riguardante l'estensione stocastica dei metodi privi di proiezione per l'ottimizzazione completamente composita. Rimuovendo il requisito di regolarità sulla funzione esterna $F$, questo lavoro consente l'applicazione dell'ottimizzazione priva di proiezione a una classe più ampia di problemi di apprendimento avversi al rischio, robusti e vincolati dall'equità. Il metodo raggiunge tassi di complessità ottimali per i metodi stocastici privi di proiezione, mantenendo al contempo l'efficienza computazionale (richiedendo una sola chiamata GLMO per iterazione, a differenza dei metodi precedenti che necessitavano di costosi cicli interni).