Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Experts

Technische Samenvatting: Een herziening van Incrementele Stochastische Majorisatie-Minimalisatie Algoritmen met Toepassingen op Mixture of Experts

Probleemstelling
De verwerking van hoog-volume, stromende data heeft traditionele batch-modus algoritmen onpraktisch gemaakt vanwege hun vereiste voor herhaalde passes over volledige datasets. Hoewel incrementele stochastische schattingsmethoden, zoals het incrementele stochastische Expectation-Maximization (EM) algoritme, zijn ontwikkeld om dit aan te pakken, leunen deze vaak op restrictieve aannames, met name de expliciete representatie van latente variabelen en de aanname dat het doelmodel tot de exponentiële familie behoort. Deze beperkingen beperken hun toepasbaarheid op complexe modellen zoals de Softmax-Gated Mixture of Experts (MoE), waarbij de objectieffunctie (negatieve log predictieve dichtheid) over het algemeen niet tot een exponentiële familie behoort en geen globale regulariteitseigenschappen bezit zoals Lipschitz-continuïteit, $L$-gladheid of convexiteit. Bijgevolg falen bestaande incrementele stochastische EM en MM varianten vaak bij het leveren van geldige surrogaten of convergentiegaranties voor softmax-gated MoE modellen.

Methodologie
De auteurs herzien en analyseren een incrementele stochastische variant van het Majorization-Minimization (MM) algoritme, geformuleerd binnen het Stochastic Approximation kader. De kernmethodologie omvat:

1. Gegeneraliseerd MM Kader: De aanpak versoepelt de vereiste dat het doelmodel tot de exponentiële familie behoort. In plaats daarvan vereist het dat de majorizer surrogate functie tot een exponentiële familie behoort. Het algoritme construeert een sequentie van majorizers gedefinieerd door $g(\theta, z; \tau) = -\psi(\theta) + \langle \bar{S}(\tau; z), \phi(\theta) \rangle$, waarbij $\bar{S}$ een hulpstatistiek is die wordt bijgewerkt via stochastische benadering.
2. Algoritmische Structuur: Het voorgestelde Incremental Stochastic MM Algoritme (Algoritme 1) onderhoudt een hulpstatistiek sequentie $\{s_n\}$ die wordt bijgewerkt door de recursie $s_{n+1} = s_n + \gamma_{n+1}(\bar{S}(\bar{\theta}(s_n); z_{n+1}) - s_n)$. De parameter-iteratie $\theta_{n+1}$ wordt vervolgens deterministisch verkregen door de surrogate functie te minimaliseren met betrekking tot de bijgewerkte statistiek: $\theta_{n+1} = \bar{\theta}(s_{n+1})$.
3. Toepassing op Softmax-Gated MoE: De methode wordt specifiek toegepast op twee varianten van softmax-gated MoE modellen:
   • Continue Output (SGMoE): Gebruikmakend van Gaussische experts met polynomiale regressie voor gating en mean functies.
   • Discrete Output: Gebruikmakend van multinomiale logistische regressie experts met polynomiale gating.
     Voor deze modellen leiden de auteurs specifieke exponentiële familie majorizer surrogaten af die de noodzaak omvatten dat de oorspronkelijke objectieffunctie tot de exponentiële familie behoort. Ze construeren geldige majorizers met behulp van kwadratische bounds en specifieke matrix-ongelijkheden (bijv. betrokken bij de matrix $B_{n,K}$) om de niet-convexiteit en het gebrek aan gladheid te behandelen die inherent zijn aan de softmax gating en de Gaussische likelihood termen.
4. Theoretische Garanties: Onder een reeks regulariteitsaannames (P1–P5) en stabiliteitscondities (Assumptions 1–8) stellen de auteurs vast dat het algoritme een sequentie genereert die bijna zeker convergeert naar een stationair punt van de objectieffunctie (waar de gradiënt verdwijnt). Deze consistentie-resultaat berust op de existentie van een Lyapunov-functie en de eigenschappen van stochastische benadering.

Belangrijkste Bijdragen

• Generalisatie van Incremental Stochastic MM: Het werk generaliseert het incrementele stochastische EM algoritme, waardoor een bredere toepasbaarheid mogelijk is voor modellen waar expliciete latente variabele representaties moeilijk zijn of waar het model niet voldoet aan de exponentiële familie structuur.
• Theoretische Consistentie: De auteurs bieden rigoureuze theoretische garanties die bewijzen dat de iteraties convergeren naar stationaire punten gekenmerkt door een verdwijnende gradiënt, een eigenschap die vaak afwezig is bij veelgebruikte stochastische optimizers zoals SGD, RMSProp, Adam en Sophia wanneer deze worden toegepast op complexe latente modellen.
• Nieuwe Toepassing op Softmax-Gated MoE: Het artikel demonstreert dat de voorgestelde methode de eerste incrementele stochastische algoritme is die effectief softmax-gated MoE modellen kan fitten, een setting waar bestaande incrementele EM en MM varianten falen door restrictieve regulariteitscondities (bijv. het falen van Lipschitz-continuïteit en convexiteit in de SGMoE objectieffunctie).
• Correctie van Bounds: De auteurs herzien en corrigeren een bound gepresenteerd in Lemma 2 van een eerder werk [5], waarbij ze een meer expliciete en rigoureuze formulering bieden die wordt gebruikt om geldige majorizers voor multinomiale logistische regressie contexten te construeren.

Experimentele Resultaten
De methode werd geëvalueerd op synthetische en real-world datasets, waarbij de prestaties werden vergeleken met state-of-the-art stochastische optimizers (SGD, RMSProp, Adam, AdamW, Sophia).

• Synthetische Data: Op zowel laag-dimensionale als hoog-dimensionale synthetische datasets presteerde het Incremental Stochastic MM algoritme consistent beter dan de baseline methoden in termen van schattingsfout (MSE, MAPE, NRMSE) en predictiefout. Het demonstreerde snellere convergentiesnelheden en grotere stabiliteit, met name bij het gebruik van Polyak averaging.
• Real-World Data:
  • Dent Maize Genotypes: In een bio-informatica studie betreffende droogtestress en proteomica-data, leverde de voorgestelde methode stabiele winsten in predictieve prestaties op vergeleken met de baselines.
  • Communities and Crime: Op socio-economische misdaaddata toonde de methode opnieuw superieur of vergelijkbaar presterende resultaten met een lagere variantie over cross-validatie folds.
• Initialisatie Robuustheid: Het algoritme presteerde robuust onder zowel geperturbeerde ground-truth initialisatie als data-gedreven initialisatie (via K-means), waarbij de ware parameters succesvol werden gerecupereerd en de log-likelihood werd geminimaliseerd.

Betekenis en Claims
Het artikel claimt dat het voorgestelde Incremental Stochastic MM framework een robuust en theoretisch gefundeerd alternatief biedt voor het optimaliseren van complexe latente variabele modellen in stromende datamgevingen. Door de strikte aannames te versoepelen die vereist zijn voor EM-gebaseerde methoden (zoals convexiteit en expliciete latente representaties), verbreedt de aanpak de reikwijdte van incrementele stochastische schatting. De auteurs benadrukken de centrale rol van softmax-gated MoE architecturen in hedendaagse deep learning voor heterogene datamodellering en stellen dat hun methode een kritieke kloof vult door een levensvatbare optimalisatiestrategie te bieden waar voorheen onbruikbaar voor incrementele stochastische benaderingen. Het werk suggereert dat dit framework als een fundamenteel instrument kan dienen voor toekomstige ontwikkelingen in statistisch leren, met name voor modellen die flexibele, niet-Gaussische of deep neural network-gebaseerde expert componenten vereisen.