Weight Adaptation for Improving Parallel Performance of Adaptive Stochastic Natural Gradient

Technische Samenvatting: Gewichtsaanpassing voor het Verbeteren van de Parallelle Prestaties van Adaptive Stochastic Natural Gradient

Probleemstelling
Probabilistische modelgebaseerde evolutionaire algoritmen (PMBE's), zoals Estimation of Distribution Algorithms (EDA's), vertrouwen op het updaten van een zoekdistributie op basis van de natuurlijke gradiënt van de verwachte utiliteit. Hoewel het Adaptive Stochastic Natural Gradient (ASNG) algoritme erin slaagt zijn leersnelheid aan te passen om aan voldoendeheidsvoorwaarden voor monotone verbetering te voldoen, maakt het gebruik van vaste gewichtsparameters die aan samples worden toegewezen op basis van hun rangorde. Terwijl rekenkracht de parallelle evaluatie van grotere populatiegroottes mogelijk maakt, blijft de optimale instelling voor deze gewichtsparameters in discrete domeinen (specifiek binaire optimalisatie) onduidelijk. Vaste gewichten zijn mogelijk niet geschikt voor variërende probleeminstellingen of grote populatiegroottes, wat de optimalisatie-efficiëntie en robuustheid kan beperken.

Methodologie
De auteurs stellen Weight Adaptation ASNG (WA-ASNG) voor, een methode die een mechanisme voor gewichtsaanpassing integreert in het bestaande ASNG-raamwerk. De kernmethodologie omvat:

1. Signaalinschatting: Het algoritme schat het "signaal" van de update-richting in, gedefinieerd als de gekwadrateerde norm van de verwachte natuurlijke gradiënt ($\|E[G_t^\theta]\|_{F(\theta_t)}^2$). Dit signaal wordt benaderd met behulp van accumulaties van de natuurlijke gradiënt ($s_t$) en de gekwadrateerde norm van de gradiënt ($\gamma_t$), afgeleid uit de theoretische relatie tussen de signaal-ruisverhouding (SNR) en de leersnelheidsaanpassing in ASNG.
2. Gradiëntascens op Gewichten: WA-ASNG behandelt de gewichtsparameters ($w$) als variabelen die geoptimaliseerd moeten worden. Het voert een gradiëntascens uit om het geschatte signaal $\|s_{t+1}\|^2 - \gamma_{t+1}$ te maximaliseren. De update-regel wordt gegeven door $\bar{w}_{t+1} = w_t + \eta_w \cdot \nabla_w S(w_t)$, waarbij $S(w_t)$ de signaalfunctie is.
3. Implementatiedetails:
   • Om stabiliteit te garanderen, vinden gewichtupdates plaats met intervallen van $L$ iteraties in plaats van bij elke stap.
   • Het algoritme gebruikt een archief van eerdere records om gradiënten te berekenen over een venster van iteraties.
   • Na de gradiëntupdate worden de gewichten in afdescenderende volgorde gesorteerd om de op rang gebaseerde structuur te behouden die vereist is door het algoritme.
   • Het mechanisme voor leersnelheidsaanpassing van het oorspronkelijke ASNG wordt behouden om te voldoen aan de voldoendeheidsvoorwaarde voor monotone verbetering, terwijl het nieuwe mechanisme voor gewichtsaanpassing gericht is op het maximaliseren van de snelheid van deze verbetering.

Belangrijkste Bijdragen

• Nieuw Aanpassingsmechanisme: Het artikel introduceert het eerste gewichtsaanpassingsmechanisme voor stochastische natuurlijke gradiëntmethoden in de context van binaire optimalisatie, waarbij de focus verschuift van theoretische analyse van optimale gewichten naar dynamische, online aanpassing.
• Duale Aanpassingsstrategie: WA-ASNG combineert leersnelheidsaanpassing (om monotone verbetering te garanderen) met gewichtsaanpassing (om de omvang van die verbetering te maximaliseren), wat theoretisch de beperkingen van vaste gewichten in parallelle settings aanpakt.
• Robuustheid tegen Ruis: De methode is ontworpen om prestaties te behouden, zelfs in de aanwezigheid van sterke evaluatieruis, een veelvoorkomende uitdaging in real-world black-box optimalisatie.

Experimentele Resultaten
De auteurs evalueerden WA-ASNG op binaire optimalisatie benchmarks: OneMax, BinVal, en LeadingOnes, met dimensies $N \in \{100, \dots, 500\}$ en populatiegroottes $\lambda_\theta \in \{25, 50, 75, 100\}$.

• Prestaties t.o.v. Baselines: WA-ASNG presteerde over het algemeen beter dan zowel het originele ASNG als Population-Based Incremental Learning (PBIL). Het bereikte het kleinste aantal evaluaties om de optimale oplossing te bereiken op BinVal in alle settings en op LeadingOnes voor grotere populatiegroottes ($\lambda_\theta \ge 50$).
• Convergentiedynamiek: Op BinVal en LeadingOnes vertoonde WA-ASNG een snellere convergentie van het gemiddelde van de waarschijnlijkheidsvector naar de optimale oplossing vergeleken met ASNG en PBIL. Dit werd toegeschreven aan het feit dat WA-ASNG een hogere leersnelheid handhaafde tijdens de optimalisatie.
• Vergelijking met Vaste Gewichten: De auteurs vergeleken WA-ASNG met ASNG-varianten die verschillende vaste gewichtsschema's gebruiken (default, lineair, CMA-ES, en CMA-ES genormaliseerd). De resultaten gaven aan dat de optimale instelling voor vaste gewichten sterk afhankelijk is van het specifieke type probleem, de dimensionaliteit en de populatiegrootte. WA-ASNG bood robuuste prestaties over deze variërende condities zonder dat handmatige afstemming nodig was.
• Ruisrobuustheid: In experimenten met Gaussische ruis op de OneMax-functie behaalde WA-ASNG de laagste SP1-waarde (gemiddeld aantal evaluaties gedeeld door het succespercentage) en het hoogste succespercentage vergeleken met alle ASNG-varianten, zelfs naarmate de ruisvariantie toenam.
• Geobserveerde Beperkingen: Op het LeadingOnes-probleem met een kleine populatiegrootte ($\lambda_\theta = 25$) en hoge dimensionaliteit ($N=400, 500$), presteerde WA-ASNG minder goed dan ASNG. De auteurs schrijven dit toe aan fluctuaties in de waarschijnlijkheidsvector van de latere componenten, waarbij het gewichtsaanpassingsmechanisme probeert het signaal te maximaliseren te midden van willekeurige veranderingen, wat tot instabiliteit leidt.

Betekenis en Claims
Het artikel claimt dat WA-ASNG effectief de uitdaging aanpakt van het instellen van geschikte gewichten voor grote populatiegroottes in parallel black-box optimalisatie. Door gewichten adaptief bij te werken om het signaal van de update-richting te maximaliseren, verbetert de methode de optimalisatie-efficiëntie en robuustheid, met name in ruisgevoelige omgevingen. De auteurs positioneren dit werk als een stap naar robuustere en breder toepasbare optimalisatiealgoritmen, hoewel zij erkennen dat verdere validatie op deceptieve functies, categorische variabelen en continue domeinen noodzakelijk is om de overdraagbaarheid van het voorgestelde mechanisme volledig vast te stellen.