Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting

Technische Samenvatting: Gedecentraliseerde tijdvariërende optimalisatie voor streamende data via temporale weging

Probleemformulering
Dit werk adresseert de uitdaging van gedecentraliseerde optimalisatie in dynamische omgevingen waar data sequentieel binnenkomt via een netwerk van agenten. In tegenstelling tot klassieke statische optimalisatie of generieke tijdvariërende formuleringen die de evolutie van de doelstelling behandelen als een willekeurig proces, hanteert dit artikel een gestructureerde, op gewichten gebaseerde formulering specifiek voor streamende data.

Het systeem bestaat uit $N$ agenten die verbonden zijn via een ongerichte, samenhangende graaf. Op elk tijdstip $t$ observeert elke agent $n$ een nieuwe datasample en loopt een instantane verlies $\ell_{n,t}(w)$ op. Het globale doel $F_t(w)$ wordt gedefinieerd als een temporale gewogen gemiddelde van alle netwerkvliezen die tot tijd $t$ zijn waargenomen:
$$F_t(w) \triangleq \sum_{i=1}^t a_i(t) F_i(w),$$
waarbij $F_i(w)$ het gemiddelde instantane verlies op tijdstip $i$ is, en $a_i(t)$ temporale gewichten zijn die voldoen aan $\sum a_i(t) = 1$. Het doel is om de tijdvariërende minimizer $w^*_t = \arg\min_w F_t(w)$ te volgen met behulp van een gedecentraliseerd algoritme met een beperkt communicatie- en rekenbudget (d.w.z. een vast aantal innerlijke iteraties $E$ per tijdstap).

Methodologie
De auteurs analyseren Gedecentraliseerde Gradiëntafdalings (DGD) toegepast op deze streamende setting. Het algoritme werkt per tijdstap in twee fasen:

1. Doelupdate: Het netwerk integreert de nieuwe tijd-gewogen doelstelling $F_{t+1}$.
2. Innerlijke iteraties: Startend vanaf de vorige iteratie, voeren agenten $E$ stappen DGD uit op de bijgewerkte doelstelling. De updateregel is $w^{(k+1)}_t = M w^{(k)}_t - \eta \nabla f_{t+1}(w^{(k)}_t)$, waarbij $M$ de mengmatrix is en $\eta$ de stapgrootte.

De kern van de analytische aanpak maakt gebruik van theorie van vaste-puntoperatoren. De auteurs definiëren een tijdvariërende DGD-afbeelding $\phi_t(w) = Mw - \eta \nabla f_t(w)$. Onder aannames van sterke convexiteit en gladheid (Aanname 1) en begrenste minimalizers (Aanname 2) bewijzen zij dat $\phi_t$ een contractieafbeelding is. Bijgevolg bestaat er voor elke gefrieste tijd $t$ een unieke vaste punt $\tilde{w}_t$ zodanig dat $\tilde{w}_t = \phi_t(\tilde{w}_t)$.

De trackingfout (TE), gedefinieerd als $\|w_t - w^*_t\|$, wordt via de driehoeksongelijkheid ontleed in twee distincte componenten:

1. Vaste-punt trackingfout (FPTE): De afstand tussen de huidige iteratie $w_t$ en het bewegende vaste punt $\tilde{w}_t$. Deze term vangt het vermogen van het algoritme om binnen de beperkte $E$ iteraties te convergeren naar de huidige doelstelling.
2. Bias-term: De afstand tussen het vaste punt $\tilde{w}_t$ en de ware tijdvariërende optimizer $w^*_t$. Deze term ontstaat door de decentralisatie van data en de stapgrootte $\eta$.

Belangrijkste bijdragen en resultaten
Het artikel leidt expliciete trackingfoutgrenzen af voor twee canonieke strategieën voor temporale weging:

1. Uniforme gewichten: Alle eerdere samples worden gelijk gewogen ($a_i(t) = 1/t$).

   • Resultaat: De vaste-punt trackingfout neemt af met een snelheid van $O(1/t)$.
   • Asymptotisch gedrag: De totale trackingfout convergeert naar een niet-nul vloer die volledig wordt bepaald door de bias-term ($\eta \kappa \Lambda G$), welke afhankelijk is van de stapgrootte, conditiegetal, netwerktopologie en dataheterogeniteit. De bijdrage van het bewegende vaste punt verdwijnt na verloop van tijd.

2. Exponentieel gedempte gewichten: Oudere samples worden geometrisch afgenomen ($a_i(t) \propto \gamma^{t-i}$).

   • Resultaat: De vaste-punt trackingfout verdwijnt niet; deze induceert een niet-verdwijnende steady-state vloer die wordt gecontroleerd door de dempingsfactor $\gamma$.
   • Asymptotisch gedrag: De totale trackingfout convergeert naar een vloer die zowel de bias-term als een vaste-punt trackingvloer omvat die evenredig is met $(1-\gamma)$. Het algoritme kan het bewegende vaste punt niet volledig inhalen omdat de effectieve doelstelling blijft evolueren met een niet-verdwijnende snelheid als gevolg van de constante instroom van nieuwe, zwaar gewogen samples.

In beide gevallen onthult de analyse dat decentralisatie een extra bias-vloer introduceert onder een constante stapgrootte, welke evenredig is met de gradiëntgrootte bij de optimale oplossing (wat dataheterogeniteit weerspiegelt). Als data homogeen zou zijn over de agenten, zou deze bias verdwijnen.

Beteekenis
Het artikel stelt dat door weg te bewegen van generieke tijdvariërende modellen naar een gestructureerd perspectief op streamende data, het scherpere en meer interpreteerbare trackingfoutgaranties biedt. Specifiek:

• Het verduidelijkt de trade-off tussen de strategie voor temporale weging en de asymptotische trackingprestaties.
• Het demonstreert dat hoewel uniforme weging het algoritme in staat stelt om uiteindelijk het bewegende vaste punt in te halen (verdwijnende FPTE), gedempte weging deze capaciteit inherent beperkt, wat resulteert in een permanente trackingvloer.
• Het valideert deze theoretische bevindingen via numerieke simulaties op een netwerk van agenten met kwadratische verliezen, waarbij wordt aangetoond dat het verhogen van het aantal innerlijke iteraties ($E$) de transiënte prestaties verbetert, maar de asymptotische bias-vloer veroorzaakt door decentralisatie en stapgroottebeperkingen niet kan elimineren.

Het werk wordt gepresenteerd als een theoretische fundament voor het begrijpen van de fundamentele grenzen van gedecentraliseerd leren vanuit streamende data, met een onderscheid tussen fouten veroorzaakt door algoritmische vertraging (FPTE) en fouten veroorzaakt door netwerk-/datastructuur (Bias).