Technische Samenvatting: RanSOM

1. Probleemstelling

Het artikel behandelt een fundamentele beperking in stochastische optimalisatie voor deep learning: kromme-geïnduceerde bias in standaard momentum-methoden (zoals Polyak's Heavy Ball) wanneer deze worden toegepast op niet-convexe landschappen.

In stochastische settings aggregeert het momentum-vector $m_t$ gradiënten van eerdere iteraties. Naarmate de optimizer van $x_{t-1}$ naar $x_t$ beweegt, zorgt de kromming van het verlieslandschap ervoor dat de gradiëntrichting verandert. Bijgevolg wordt $m_{t-1}$ een "verouderde" schatter van de huidige gradiënt $\nabla f(x_t)$. Deze bias, evenredig met het integraal van de Hessian langs het update-pad, verhindert dat standaard momentum-methoden de optimale $O(\epsilon^{-3})$ steekproefcomplexiteit bereiken die vereist is voor niet-convexe optimalisatie, waardoor ze vaak beperkt blijven tot suboptimale $O(\epsilon^{-4})$ rates.

Bestaande correctiestrategieën kampen met een "bias-variatie bottleneck":

• Op verschil gebaseerde schatters (bijv. STORM): Vereisen individuele steekproef-gladheid (vaak geschonden door ReLU-activaties) of lijden onder hoge variatie.
• Deterministische Second-Order Momentum (SOM): Vereist sterke globale Lipschitz-aannames over de Hessian (begrensde derde afgeleiden).
• Stochastische SOM (SOM-Unif): Verslapt gladheidsaannames maar leidt tot prohibitieve computatiekosten door het vereiste van extra "vooruitkijkende" queries (3 forward/backward passes per iteratie).

2. Methodologie: Het RanSOM-kader

De auteurs stellen RanSOM (Randomized Second-Order Momentum) voor, een unifyend kader dat kromme-bias elimineert zonder extra aannames of computatiekosten. De kerninnovatie is het vervangen van deterministische stapgroottes door gerandomiseerde stapgroottes getrokken uit specifieke verdelingen.

2.1 Grandomiseerde Integratie per Delen

In plaats van een vaste stap $\eta_t$, wordt de stapgrootte $s_t$ behandeld als een stochastische variabele met gemiddelde $\mathbb{E}[s_t] = \eta_t$. Door gebruik te maken van Stein-achtige identiteiten (formules voor integratie per delen), relateert de methode het eindige verschil van gradiënten (de bias) aan een enkele Hessian-Vector Product (HVP) geëvalueerd op het random eindpunt.

Het kader maakt gebruik van twee specifieke identiteiten:

1. Exponentiële Identiteit (Onbeperkt): Als $s \sim \text{Exp}(\lambda)$, dan:
   $$\mathbb{E}[g(s) - g(0)] = \frac{1}{\lambda} \mathbb{E}[g'(s)]$$
   Dit stelt de bias $\nabla f(x_{t+1}) - \nabla f(x_t)$ in staat om geschat te worden door de HVP bij $x_{t+1}$ te schalen met $\eta_t$.
2. Beta Identiteit (Beperkt): Als $s \sim \text{Beta}(1, K)$, dan:
   $$\mathbb{E}[g(s) - g(0)] = \mathbb{E}\left[ \frac{1-s}{K} g'(s) \right]$$
   Dit houdt rekening met de compacte drager van de Beta-verdeling, waardoor haalbaarheid in beperkte optimalisatie wordt gewaarborgd.

2.2 Algorithmische Instantiaties

Het kader wordt geïnstancierd in twee algoritmen:

• RanSOM-E (Onbeperkt): Gebruikt exponentieel verdeelde stappen. Het integreert met een Linear Minimization Oracle (LMO) om diverse geometrische updates te unifyen, en herstelt Normalized SGD ($L_2$-bol), SignSGD ($L_\infty$-bol), en Muon-achtige spectrale updates.
• RanSOM-B (Beperkt): Gebruikt Beta-verdeelde stappen op $[0, 1]$. Dit zorgt ervoor dat de update $x_{t+1} = (1-s_t)x_t + s_t v_t$ (waarbij $v_t$ de LMO-richting is) strikt binnen de convexe haalbare set $C$ blijft, waardoor projectie-operaties worden vermeden.

2.3 Computatie-efficiëntie

Een kritisch voordeel van RanSOM is de computatiekost. De correctieterm vereist een HVP bij $x_{t+1}$. In moderne automatische differentiatie-frameworks (zoals PyTorch, JAX) kan deze HVP via Pearlmutter's truc worden berekend in een enkele gecombineerde backward pass naast de standaard gradiëntberekening.

• Kost: $2(F_c + B_c)$ (equivalent aan twee forward/backward passes).
• Vergelijking: Dit komt overeen met de kost van standaard variatie-gereduceerde methoden zoals STORM en is aanzienlijk goedkoper dan SOM-Unif, dat een dedicated extra query vereist ($3(F_c + B_c)$).

3. Belangrijkste Bijdragen

1. Unifyend Kader: Een methode die kromme-geïnduceerde bias elimineert met behulp van randomiseerde stapgroottes en Stein-identiteiten, toepasbaar op zowel onbeperkte als beperkte optimalisatie.
2. Optimale Convergentie-rates: Theoretische analyse bewijst dat RanSOM de optimale $O(\epsilon^{-3})$ steekproefcomplexiteit bereikt onder standaard aannames van begrensd ruis.
3. Robuustheid tegen Heavy Tails: De methode breidt zich uit naar uitdagende settings met heavy-tailed gradiëntruis ($p \in (1, 2]$) en generaliseerde $(L_0, L_1)$-gladheid (waarbij de Hessiaannorm groeit met de gradiëntnorm), zonder dat de Hessian Lipschitz-continu moet zijn.
4. Geen Extra Overhead: In tegenstelling tot eerdere second-order correcties, vereist RanSOM geen extra "vooruitkijkende" punten, waardoor de standaard query-complexiteit van $2(F_c + B_c)$ behouden blijft.
5. Klip-vrij: De methode bereikt optimale rates zonder expliciete gradiënt-klipping, in plaats daarvan vertrouwend op de intrinsieke normalisatie die wordt geboden door de LMO-updates en de statistische eigenschappen van de randomiseerde stappen.

4. Theoretische Resultaten

Het artikel stelt convergentie vast voor niet-convexe optimalisatie onder de volgende voorwaarden:

• Aannames: Het doel is van onderen begrensd en voldoet aan puntsgewijze $(L_0, L_1)$-gladheid. Stochastische gradiënten en HVP's zijn onbevooroordeeld met affiene heavy-tailed ruis (momenten $p, q \in (1, 2]$).
• Onbeperkt (RanSOM-E): Convergeert naar een stationair punt met rate:
  $$\frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}[\|\nabla f(x_t)\|_*] \leq O\left( T^{-\frac{q(p-1)}{2q(p-1)+p}} \right)$$
  Voor het standaardgeval ($p=q=2$) herstelt dit de optimale $O(T^{-1/3})$ rate.
• Beperkt (RanSOM-B): Convergeert in termen van de Frank-Wolfe gap $G(x)$ met dezelfde optimale rate $O(T^{-1/3})$ voor $p=q=2$.

De analyse benadrukt een asymmetrische schaling van de momentum-parameter $\beta$: een kleinere $\beta$ helpt hoge-variatie gradiënten uit te middelen, terwijl een grotere $\beta$ de krommecorrectie effectiever maakt. De optimale $\beta$ balanceert deze effecten.

5. Experimentele Resultaten

De auteurs evalueren RanSOM op drie niet-convexe taken:

1. Binair Classificatie (SPLICE): RanSOM-E (Muon-variant) behaalde de hoogste testnauwkeurigheid (84,90%) met aanzienlijk lagere variatie vergeleken met STORM (73,35% ± 10,77%).
2. Sequentie Classificatie (MNIST1D): RanSOM-E (Muon) bereikte 91,90% nauwkeurigheid, presteerde beter dan STORM (88,83%) en klassieke SOM, en behield tegelijkertijd hoge stabiliteit (std dev ±0,36 versus ±1,38 voor STORM).
3. Beperkte Matrix Voltooiing (MovieLens): RanSOM-B convergeerde naar een lagere finale RMSE dan Stochastic Frank-Wolfe baselines (SFW-Polyak, SFW-SOM), wat effectiviteit aantoont bij het navigeren door complexe constraint-geometrieën.

6. Betekenis en Claims

Het artikel claimt dat RanSOM het "dilemma" van second-order momentum-correcties oplost: het bereikt de optimale convergentierate van $O(\epsilon^{-3})$ zonder de restrictieve aannames van Lipschitz-Hessians of individuele steekproef-gladheid, en zonder de computatiekosten van extra sampling.

Door stapgroottes te behandelen als stochastische variabelen, maakt RanSOM robuuste second-order bias-correctie mogelijk die:

• Aannames-arm is: Gaat om met niet-gladde individuele verliezen (bijv. ReLU-netwerken) en heavy-tailed ruis.
• Computatie-efficiënt is: Komt overeen met de kost van standaard SGD met momentum.
• Geometrisch flexibel is: Generaliseert natuurlijk naar genormaliseerde optimalizers en beperkte settings via LMO's.

De auteurs positioneren RanSOM als een unifyende oplossing voor moderne niet-convexe optimalisatie, met name in deep learning-architecturen waar standaard gladheidsaannames falen en computatie-efficiëntie van het grootste belang is.