Data-Driven Distributed Optimization via Aggregative Tracking and Deep-Learning

Technische Samenvatting: Data-gestuurde Gedistribueerde Optimalisatie via Aggregatieve Tracking en Deep Learning (DELTA)

Probleemformulering
Het artikel behandelt de uitdaging van gedistribueerde optimalisatie binnen een aggregatief kader waarbij een netwerk van $N$ agenten gezamenlijk de som van lokale kostenfuncties minimaliseert. In tegenstelling tot standaard gedistribueerde optimalisatie, hangt de lokale kostenfunctie $f_i$ van een agent niet alleen af van de eigen beslissingsvariabele $x_i$, maar ook van een globale aggregatieve variabele $\sigma(x)$, die wordt gedefinieerd als het gemiddelde van de lokale bijdragen $\phi_i(x_i)$.

Het specifieke scenario dat wordt overwogen is data-gestuurd en onbekend:

1. De functies $f_i$ zijn volledig onbekend voor de agenten.
2. Agenten kunnen slechts één feedbackmonster van hun lokale kosten verkrijgen per iteratie (een "1-punt" evaluatie) op een gekozen punt $(u_{x,i}, u_{\sigma,i})$.
3. Globale grootheden (de aggregatieve variabele $\sigma(x)$ en de afgeleide van de globale kosten met betrekking tot deze variabele) zijn lokaal niet beschikbaar.

Deze opzet wordt gemotiveerd door toepassingen in coöperatieve robotica en gepersonaliseerde optimalisatie, waarbij kostenfuncties bijvoorbeeld de ontevredenheid van een gebruiker of fysieke beperkingen kunnen vertegenwoordigen die moeilijk analytisch te modelleren zijn, maar wel kunnen worden gesampled via sensoren of gebruikersfeedback.

Methodologie: Het DELTA-algoritme
De auteurs stellen DELTA voor (DEep-Learning aggregative TrAcking), een gedistribueerd algoritme dat opereert op één enkele tijdschaal en drie gelijktijdige componenten integreert:

1. Leergerichte Module:

   • Elke agent $i$ gebruikt een lokale neurale netwerk (NN) $\hat{f}_i(\cdot, \theta_i)$ om de onbekende kostenfunctie $f_i$ en de bijbehorende gradiënten te benaderen.
   • In plaats van het netwerk tot convergentie te trainen tussen de optimalisatiestappen (wat rekenintensief is en meerdere monsters vereist), wordt de NN bijgewerkt via een single-step gradiëntafdaling met behulp van het enkele kostenmonster dat in elke iteratie wordt verkregen.
   • Om persistente excitatie voor het leerproces te waarborgen, injecteert het algoritme dither-signalen ($d_{x,i}, d_{\sigma,i}$) in de samplingpunten.
   • De NN benadert de daling-richting, wat effectief de noodzaak voor expliciete kennis van de gradiënt vervangt.

2. Optimalisatiegerichte Routine:

   • Agenten voeren een gedistribueerde gradiënt-achtige update uit met behulp van de benaderde gradiënten die door hun lokale NNs worden geleverd.
   • De update-regel combineert de lokale gradiëntschatting $\nabla_1 \hat{f}_i$ met een term die de afgeleide van de aggregatiefunctie $\nabla \phi_i$ en de geschatte globale gradiëntcomponent bevat.

3. Trackinggerichte Mechanisme:

   • Omdat globale grootheden zoals $\sigma(x)$ en de som van de lokale gradiëntafgeleiden niet beschikbaar zijn, houden agenten hulpvariabelen ($w_i$ en $z_i$) bij.
   • Deze variabelen worden bijgewerkt via geperturbueerde consensusdynamiek (gebruikmakend van een dubbel stochastische adjacency matrix) om de ontbrekende globale aggregatieve variabele en de globale gradiëntcomponent lokaal te reconstrueren.

Theoretische Analyse en Resultaten
De stabiliteit en convergentie van DELTA worden geanalyseerd met behulp van instrumenten uit de systeemtheorie, specifiek tijdschaalscheiding (timescale separation) en discrete-tijd middelingstheorie. De analyse behandelt het algoritme als een tijdvariërend twee-tijdschaal systeem, waarbij de snelle dynamiek (tracking en leren) wordt gescheiden van de langzame dynamiek (optimalisatie).

• Convergentiegarantie: Onder aannames van sterke convexiteit van de globale kosten en Lipschitz-continuïteit van de functies en hun benaderingen, bewijzen de auteurs dat het algoritme lineair convergeert naar een omgeving van de optimale oplossing $x^*$.
• Foutbereik: De straal van deze omgeving is expliciet afhankelijk van de parameter $\epsilon$, die de maximale reconstructiefout van de neurale netwerken vertegenwoordigt (d.w.z. de nauwkeurigheid van de NN-benadering bij convergentie).
• Ideaal geval: In het theoretische limiet waar de neurale netwerken een perfecte schatting bereiken ($\epsilon = 0$), convergeert het algoritme exact naar de optimale oplossing.
• Robuustheid: Het ontwerp maakt het mogelijk dat het algoritme zich aanpast aan tijdvariërende kostenfuncties of verstoringen zonder dat een volledige herstart van de trainings- of trackingprocessen nodig is.

Belangrijkste Bijdragen

1. Nieuwe Integratie: Het artikel introduceert een nieuw schema dat neurale netwerkleren combineert met gedistribueerde aggregatieve optimalisatie en gradiënt tracking, specifiek afgestemd op scenario's met slechts enkele kosten-evaluaties per iteratie.
2. Overwinnen van 1-Punt Beperkingen: Standaard zeroth-order 1-punt methoden lijden vaak aan slechte convergentiesnelheden of hoge variantie. DELTA pakt dit aan door een dynamische leerstrategie (NN's) te implementeren die de richting van de daling leert zonder het aantal kosten-evaluaties per iteratie te verhogen.
3. Rigoureuze Convergentiebewijs: De auteurs leveren een formeel bewijs van lineaire convergentie in een omgeving van het optimum, waarbij de afruil tussen de benaderingsnauwkeurigheid van het neurale netwerk en de uiteindelijke optimalisatiefout expliciet wordt gekarakteriseerd.
4. Omgaan met Onbekende Omgevingen: Het framework is ontworpen voor volledig onbekende kostenfuncties, wat het onderscheidt van eerdere werken waarbij delen van de kostenfunctie bekend waren of waarbij meerdere monsters per iteratie vereist waren.

Betekenis en Claims
Het artikel beweert dat DELTA een praktische oplossing biedt voor gepersonaliseerde optimalisatie en coöperatieve controle in onbekende of niet-stationaire omgevingen (bijv. mens-robot samenwerking). Door gebruik te maken van de synergie tussen leren, optimalisatie en tracking, past het algoritme zich dynamisch aan veranderingen in kostenfuncties aan.

De auteurs merken op dat hoewel een voorlopige versie van dit werk bestond voor tijdvariërende settings met meerdere monsters en volledige NN-training, de huidige bijdrage technisch veeleisender is: het werkt met enkele monsters per iteratie en single-step NN-training, wat een complexere integratie van leer-dynamica analyse met optimalisatie en consensusdynamiek vereist. Numerieke simulaties op een netwerk van 20 agenten valideren de theoretische resultaten, waarbij wordt aangetoond dat het algoritme convergeert naar de optimale omgeving en robuust is tegen plotselinge veranderingen in lokale kostenfuncties.