Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

Technische Samenvatting: Stochastische Compositional Optimalisatie via Hybrid Momentum Frank–Wolfe

Probleemformulering
Dit werk behandelt het stochastische compositional optimalisatieprobleem van het minimaliseren van doelfuncties van de vorm:
$$\min_{x \in X} \phi(x) := F(f(x), x)$$
waarbij $X \subset \mathbb{R}^d$ een convexe en compacte verzameling is, $f: X \to \mathbb{R}^n$ een innerlijke afbeelding is die alleen toegankelijk is via ruisende stochastische queries ($f(x) = \mathbb{E}_\xi[\tilde{f}(x; \xi)]$), en $F: \mathbb{R}^n \times X \to \mathbb{R}$ een deterministische buitenfunctie is.

De primaire uitdaging in de stochastische setting is dat naïeve plug-in schatters vertekend zijn vanwege de ongelijkheid van Jensen ($\mathbb{E}[F(\tilde{f}(x; \xi), x)] \neq F(\mathbb{E}[\tilde{f}(x; \xi)], x)$). Hoewel bestaande stochastische methoden (bijv. SCGD, NASA, SCSC) deze vertekening aanpakken met momentum-gebaseerde trackers en de kettingregel, vereisen ze fundamenteel dat de buitenfunctie $F$ continu differentieerbaar is. Deze aanname sluit vele kritieke toepassingen uit die niet-gladde buitenfuncties omvatten, zoals robuuste max-of-losses, Conditional Value-at-Risk (CVaR) en normregularisatoren. Bovendien vertrouwen bestaande projectievrije stochastische methoden (bijv. LiNASA+ICG) ook op de gladheid van $F$.

Methodologie
De auteurs stellen het Hybrid Momentum Stochastic Frank–Wolfe-algoritme voor, de eerste projectievrije methode voor volledig compositional problemen die niet-gladde buitenfuncties aankan. De kerninnovatie ligt in het vervangen van de standaard gradiëntgebaseerde update door een Generalized Linear Minimization Oracle (GLMO) die werkt op een stochastisch affien surrogaat.

Het algoritme onderhoudt twee stochastische trackers bij elke iteratie $k$:

1. Jacobian Tracker ($V_k$): Een Polyak-stijl momentum-schatter voor de Jacobiaan $\nabla f(y_k)$.
2. Functie Tracker ($z_k$): Een schatter voor de functiewaarde $f(y_k)$.

Het algoritme biedt twee varianten voor de functie-tracker om het geheugengebruik en de aannames in evenwicht te brengen:

• Variant I (Polyak): Geheugenloos, maar vereist dat de innerlijke functie $f$ Lipschitz-continu is.
• Variant II (Taylor-correctie): Vereist het opslaan van de vorige iteratie, maar elimineert de Lipschitz-aanname op $f$ door gebruik te maken van een eerste-orde Taylor-extrapolatie ($V_k(y_k - y_{k-1})$) om de functiewaarde te voorspellen, waardoor de trackingfout wordt gereduceerd tot een kwadratische restterm.

Bij elke stap construeert het algoritme een affien surrogaat $\tilde{l}_k(x) = z_k + V_k(x - y_k)$ en voert dit in bij de GLMO:
$$x_{k+1} \in \arg\min_{x \in X} F(\tilde{l}_k(x), x)$$
Cruciaal is dat de GLMO $F$ behandelt als een black box, deze direct minimaliseert over de lineariseerde innerlijke functie zonder een subgradiënt van $F$ te vereisen. Dit stelt de methode in staat om niet-gladde $F$ (bijv. $\ell_p$-normen, max-functies) efficiënt te hanteren, waarbij de oracle-aanroep vaak wordt gereduceerd tot een Lineair Program (LP) of Second-Order Cone Program (SOCP).

Belangrijkste Bijdragen

1. Algoritmische Noviteit: Introductie van het eerste stochastische projectievrije algoritme voor volledig compositional optimalisatie met niet-gladde buitenfuncties.
2. Theoretische Garanties onder Heavy-Tailed Noise: De analyse gaat ervan uit dat de stochastische oracle begrende $r$-de momenten heeft ($r \in (1, 2]$), wat heavy-tailed noise-scenario's dekt.
   • Niet-Convex Geval: Het algoritme bereikt een convergentiesnelheid van $O(K^{-(r-1)/(3r-2)})$ in de generaliseerde Frank–Wolfe gap. Voor eindige variantie ($r=2$) levert dit $O(K^{-1/4})$ op, wat overeenkomt met de minimax-optimale ondergrens voor single-sample projectievrije stochastische methoden onder verwachte gladheid.
   • Convex Geval: Onder gezamenlijke convexiteitsaannames is de primate snelheid $O(K^{-(r-1)/(2r-1)})$, wat $O(K^{-1/3})$ oplevert wanneer $r=2$.
3. Deterministische Interpolatie: Het algoritme interpolatiert naadloos met het deterministische regime. Wanneer de oracle exact is (nul ruis), herstelt het instellen van momentumparameters op 1 de deterministische Basic Method van Vladarean et al. [2023] met zijn optimale snelheden ($O(1/K)$ voor convex, $\tilde{O}(1/\sqrt{K})$ voor niet-convex).
4. Versnelling: Onder sterkere $r$-average gladheidsaannames (of begrende Hessian-noise momenten) integreert het kader met STORM variantiereductie of Hessian-corrected momentum om de niet-convexe snelheid te versnellen naar $O(K^{-1/3})$ (bij $r=2$).

Resultaten en Experimenten
Het paper valideert de theoretische bevindingen door middel van numerieke experimenten op drie real-world problemen met niet-gladde $F$ en heavy-tailed noise:

• Robuuste Minimax Sparse Regression: Minimaliseren van de worst-case loss over dataversnellingen.
• CVaR Portfolio Optimalisatie: Risico-averse optimalisatie op S&P 500 rendementen.
• Robuuste Matrix Completion: Gebruik van $\ell_1$-loss op het MovieLens-100K dataset.

Experimentele resultaten tonen aan dat standaard stochastische compositional Frank–Wolfe (Vanilla SCFW) faalt om te convergeren vanwege vertekening, en dat geknipte varianten plateau vormen. Daarentegen bereiken beide voorgestelde varianten (Polyak en Taylor) de voorspelde $O(K^{-1/4})$ convergentiesnelheid. De Taylor-variant (Variant II) blijkt theoretisch robuust te zijn, zelfs wanneer de Lipschitz-aanname op $f$ niet kan worden geverifieerd, hoewel de Polyak-variant iets beter presteert in regimes waar de aanname geldt.

Betekenis
Het paper claimt een open probleem opgelost te hebben geïdentificeerd door Vladarean et al. [2023] met betrekking tot de stochastische uitbreiding van projectievrije methoden voor volledig compositional optimalisatie. Door de gladheidseis op de buitenfunctie $F$ te verwijderen, stelt dit werk de toepassing van projectievrije optimalisatie in staat op een bredere klasse van risico-averse, robuuste en fairnes-geconstraineerde leerverwervingsproblemen. De methode bereikt optimale complexiteitssnelheden voor projectievrije stochastische methoden terwijl het computationele efficiëntie behoudt (vereist slechts één GLMO-aanroep per iteratie, in tegenstelling tot eerdere methoden die dure innerlijke lussen vereisten).