Hur man optimerar enhetsval och sparsitet i Federated Edge Learning

För att uppnå effektiv kommunikation och beräkningsresurser i Federated Edge Learning (FEEL) måste man ofta lösa komplexa optimeringsproblem som involverar enhetsval, sparsitet och låg rank. Ett sådant problem innebär att maximera antalet enheter som kan delta i varje kommunikationsomgång, samtidigt som man uppfyller minimikraven för medelkvadratiska fel (MSE) och andra systemrestriktioner. Det här kapitlet belyser hur en skillnad-av-konvexa funktioner (DC) representation kan användas för att ta itu med dessa problem.

Problemet börjar med ett mål att maximera antalet genomförbara MSE-begränsningar. I detta scenario söker vi att maximera mängden $S_t$ där varje enhet $i$ från $S_t$ kan väljas, under förutsättning att den relaterade MSE-begränsningen är uppfylld. Detta innebär att vi måste lösa ett optimeringsproblem där både sparsiteten av lösningen och ranken av matrisen $M$ måste beaktas.

Ett första steg är att formulera problemet för sparsitet. I det här fallet innebär det att minimera antalet icke-noll element i en vektor $x$, vilket motsvarar att reducera antalet enheter som är aktiva för att spara resurser. Den sparsity-inducerande modellen bygger på att lösa ett problem som innebär att minimera $\| x \|_0$ under förutsättning att vissa MSE-begränsningar är uppfyllda. För att hantera denna sparsitet och MSE-begränsningar används en matrisupplyftningsteknik som omvandlar problemet till ett problem med en positiv semidefinit matris $M$, där $\text{rank}(M) = 1$. Detta innebär att $M$ kan representera en vektor $m$ genom faktorisering, vilket är en effektiv metod för att hantera både sparsitet och rankbegränsningar samtidigt.

I det mer komplexa optimeringsproblemet presenteras en tvåstegs DC-metod för att först inducera sparsitet och sedan upptäcka feasilibilitet för enhetsval. I det första steget av DC-programmet löses en optimering som innebär att maximera sparsiteten, det vill säga minska antalet icke-noll element i $x$. I det andra steget detekteras feasilibiliteten för varje enhet genom att säkerställa att MSE-kraven är uppfyllda. Genom att lösa dessa problem sekventiellt kan man gradvis välja enheter, där varje vald enhet bidrar till att uppfylla MSE-kravet och håller systemet sparsigt och optimerat.

Denna metod kan formuleras som ett DC-program som innehåller både sparsitetspådrivande termer och en feasilitetsdetekteringsmekanism. Resultatet av det första steget är en lösning där enhetsvalet är sparsigt, medan det andra steget säkerställer att de valda enheterna kan uppfylla MSE-kraven. För att göra detta effektivt behöver man lösa optimeringsproblem som involverar både trace-norm och spektrala normer för att exakt säkerställa att ranken av matrisen $M$ är lika med ett, vilket är en grundläggande förutsättning för att hålla systemet lågrankigt.

För att ytterligare säkerställa effektiviteten och konvergensen av dessa algoritmer kan vi formulera problemen som skillnader mellan starkt konvexa funktioner, vilket gör det möjligt att tillämpa etablerade tekniker från optimeringsteori. Dessa representationer säkerställer att algoritmerna konvergerar snabbt och att lösningarna förblir stabila, även i komplexa system med många enheter och hårda begränsningar.

Det är viktigt att förstå att den här processen inte bara handlar om att minska antalet enheter utan också om att upprätthålla en balans mellan sparsitet och systemets kapacitet att uppfylla MSE-krav. Att effektivt välja de enheter som kan bidra utan att överskrida de beräknings- och kommunikationsresurser som finns tillgängliga är avgörande för att uppnå optimala resultat i FEEL.

Hur påverkar enheter och UAV-schemaläggning konvergensen i FEEL-träning?

I federerad kantlärning (FEEL) med hjälp av UAV:er (obemannade luftfarkoster) är det centralt att förstå den påverkan som kommunikations- och beräkningsparametrar har på träningsprocessen. En viktig aspekt är att hantera de tids- och energikostnader som uppstår under modellöverföringar, särskilt i förhållande till nätverksbetingelser och UAV:ns förmåga att optimera enhetens schemaläggning och rörelse.

När enheter laddar upp sina lokala träningsmodeller till UAV:n, är tiden för att göra detta en avgörande faktor för effektiviteten i FEEL-processen. Enhetens uppladdningstid vid varje runda n, betecknad som τk[n], beror på flera variabler, där bland annat systemets bandbredd B och enhetens sändningseffekt pk[n] är avgörande. Om vi antar att modellen är konstant i storlek, s, kan uppladdningstiden för en enhet k beräknas enligt (6.13). Det står klart att ju högre kanalvinsten är, desto snabbare sker uppladdningen. UAV:n har möjlighet att effektivisera denna process genom att optimera den direkta linjen för kommunikation och minska avstånden mellan enheterna och UAV:n.

För att beräkna energiförbrukningen under uppladdningen, används formeln i (6.14), där den totala energiförbrukningen för en enhet beror på dess uppladdningstid och sändningseffekt. Det är viktigt att beakta att denna energi inte bara handlar om den fysiska överföringen av data utan också om den tid det tar för UAV:n att utföra globala uppdateringar av modeller efter att alla enheter har skickat sina lokala modeller.

När alla enheter har laddat upp sina lokala modeller och UAV:n utfört en global uppdatering av modellen, skickas den uppdaterade modellen tillbaka till enheterna. Detta innebär en dubbel kommunikation; både för att hämta de uppdaterade globala modellerna och för att returnera uppdateringarna till varje enhet. Det här skapar ett mönster där UAV:n spelar en nyckelroll i att optimera fördröjningen och effektiviteten i hela träningscykeln.

Det är också värt att notera att den tid som UAV:n spenderar på att uppdatera den globala modellen och återföra den till enheterna inte alltid är lika lång som den tid enheter spenderar på sina lokala beräkningar. Detta beror på UAV:ns betydligt högre beräkningskapacitet, som gör att den snabbt kan slutföra den globala uppdateringen, vilket innebär att de första stegen i kommunikationskedjan kan ignoreras när UAV:n beräknar globala uppdateringar.

I den konvergensanalys som presenteras, ligger fokus på hur systemparametrarna påverkar den totala träningsprestationen, vilket leder till att ett träningsminimeringsproblem formuleras för att förbättra träningshastigheten och minska tiden för FEEL-processen. De viktigaste parametrarna här är kommunikationstid, enhetens schemaläggning och UAV:ns rörelsebana. Dessa variabler måste optimeras för att få bästa resultat, vilket ger ett potentiellt problem av blandad integer icke-konvex form, som ofta är svårt att lösa exakt.

För att säkerställa att systemet konvergerar till ett tillfredsställande resultat måste vissa antaganden uppfyllas. En av de viktigaste antagandena är att de förlorade funktionerna, eller "loss functions", är nedre-bundna och att gradienterna för lokala modeller inte överskrider en viss gräns. När vi analyserar den totala tiden för varje runda av träning, måste balansen mellan enheternas schemaläggning, kommunikationstid och UAV:ns rörelse optimeras. Detta säkerställer att varje enhet får den nödvändiga kommunikationstiden utan att överskrida de tillåtna tidsramarna för varje tidslucka, som definieras av systemets schemaläggning och UAV:ns rörelsebana.

För att kunna lösa träningsminimeringsproblemet effektivt måste vi ta hänsyn till det faktum att de schemalagda enheterna måste vara korrekt valda för att minska träningsfördröjningar. Om för många enheter schemaläggs samtidigt kan det orsaka stora kommunikationsbelastningar och förseningar, särskilt om några av enheterna lider av fördröjningar i kommunikationskanalerna. Detta är en av de största utmaningarna i federerad lärande med UAV:er. Lösningen kräver en finjustering av hur många enheter som bör aktiveras i varje runda och hur deras energi och tid ska fördelas.

En annan viktig aspekt är att vi bör analysera om lösningen på problemet är genomförbar innan vi fortsätter med optimeringen. Om den önskade konvergensgränsen inte kan uppnås med de valda parametrarna, eller om enheternas energi inte är tillräcklig för att stödja hela processen, kan systemet misslyckas med att uppnå de uppsatta målen. Därför är det avgörande att noggrant kontrollera systemets parametrar innan man påbörjar optimeringen.

Hur blockchain kan optimera trådlös federerad edge-lärande (B-FEEL)

För att analysera effektiviteten i ett trådlöst federerat edge-lärande system integrerat med blockchain, måste vi överväga flera faktorer, inklusive kanalens överföringskapacitet, latens och den beräkningsbelastning som införs genom användning av blockchain. I denna analys kommer vi att använda genomsnittlig kanalvinst över en överföringsrunda som en förenkling, representerad som $h_{tDk,B} = \frac{1}{S} \sum_{s=1}^{S} h_{tS+s}$, där $S$ är det totala antalet tidsluckor under en överföringsrunda och $t$ anger träningsrundan. Den överföringshastighet som kan uppnås från edge-enheten $D_k$ till edge-servern $B_m$ kan således uttryckas som

där $p_{D_k}$ är sändningseffekten från $D_k$, $h_{tD_k,B_m}$ är kanalvinsten från $D_k$ till $B_m$, och $N_0$ är den spektrala densiteten för additive white Gaussian noise (AWGN). För systemet definieras den maximala bandbredden som $b_{\text{max}}$, vilket innebär att alla edge-enheter och servern delar på den totala bandbredden.

Latensen för att överföra ett datapaket från en enhet till en server kan sedan beräknas med hjälp av denna överföringshastighet. Vidare måste vi förstå hur blockchain påverkar denna latens i varje steg av systemets drift.

Lokalt träningssteg och signaturverifiering

När edge-enheten tränar sitt lokala modell, krävs beräkningskraft för att köra algoritmen för backpropagation. Antalet CPU-cykler som krävs per exempel definieras som $\delta$, vilket innebär att latensen för att beräkna de lokala modellvikterna kan uttryckas som

där $f_{D_k}$ är CPU-frekvensen för enheten. Efter det lokala träningssteget kapslas den uppdaterade modellen in i en transaktion som inkluderar en digital signatur. Att skapa denna signatur kräver ytterligare beräkningskraft, och latensen för signaturgenereringen ges av

där $\rho$ är antalet CPU-cykler som krävs för att skapa signaturen. När transaktionen har skapats, sker överföringen av denna data till huvudservern. Latensen för överföring beror på kanalens överföringskapacitet och storleken på datan, vilket innebär att latensen för att överföra en transaktion kan skrivas som

där $S$ är storleken på transaktionen och $R_{tD_k,B_m}$ är den överföringshastighet som uppnås mellan enheten och servern under den aktuella träningsrundan.

Agregering av global modell och blockskapande

När transaktionerna, som innehåller de lokala modellerna, skickas till huvudservern, verifieras signaturerna för att bekräfta avsändarens identitet. Den globala modellen skapas sedan genom att använda en smart kontrakt, exempelvis den multi-KRUM algoritmen, för att säkerställa att modellerna slås samman på ett korrekt sätt. Efter att den globala modellen har skapats, paketerar huvudservern alla lokala modelltransaktioner och den globala modellen i ett nytt block. Blocket innehåller totalt $K + 1$ transaktioner, där $K$ är antalet enheter som bidragit med sina lokala modeller.

Verifiering av dessa transaktioner och aggregationen av den globala modellen kräver en beräkningslast, och den totala beräkningsbelastningen för huvudservern anges som

där $\sigma$ representerar antalet CPU-cykler som krävs för att genomföra den smarta kontraktsoperationen. Detta steg innebär en signifikant fördröjning i systemet, men är nödvändigt för att säkerställa korrektheten i den globala modellen.

Förberedelse- och validiteringsfas

När det nya blocket har skapats, sänder huvudservern ett förberedelsemeddelande till alla validatorer för att verifiera blockets giltighet. Denna fas kräver att validatorerna bekräftar digitala signaturer och validerar korrektheten i den globala modellen. Validatorerna beräknar den globala modellen och jämför den med den version som skapats av huvudservern. För att valideringen ska vara framgångsrik krävs det att 2f validatorer, där f är antalet potentiella fientliga noder i systemet, bekräftar blockets giltighet.

Kommunikationslatens och systembelastning

Vid varje steg av valideringen krävs kommunikationslatens för att sända meddelanden mellan servrar, vilket ytterligare påverkar systemets total latens. I förberedelsefasen och de efterföljande stegen måste alla meddelanden sändas mellan validatorer och den primära servern. För varje steg i konsensusprotokollet beräknas latensen för kommunikation, där varje server skickar sina meddelanden till alla andra servrar.

Vidare är beräkningskraven för varje validator för att validera signaturer och beräkna den globala modellen också en betydande källa till latens i systemet. För att säkerställa att systemet är både effektivt och korrekt är det viktigt att förstå dessa latenskomponenter och optimera processerna för att minska fördröjningarna och beräkningsbelastningen.

Viktiga överväganden

Förutom de latens- och beräkningskrav som beskrivs, är det också avgörande att förstå dynamiken i systemets bandbredd och hur denna delas mellan enheter och servrar. Den maximala tillgängliga bandbredden $b_{\text{max}}$ måste hanteras noggrant för att förhindra överbelastning av kommunikationskanalen. Att designa ett system som effektivt utnyttjar bandbredden kan minska fördröjningarna och öka systemets prestanda. Dessutom är säkerhetsprotokollen som används för att verifiera digitala signaturer och säkerställa integriteten av den globala modellen avgörande för systemets robusthet. Effektiv användning av blockchainteknologi gör det möjligt att genomföra dessa steg på ett säkert sätt, vilket ger ett transparent och pålitligt system.