First-Order Algorithms for Communication Efficient Distributed Learning

QC 20220221

Abstract

Enorma framsteg inom maskininlärningsalgoritmer förbättrar centrala tillämpningar av artificiell intelligens, från naturlig språkbehandling till autonom körning, tack vare innovation inom numerisk optimering och högpresterande datorsystem. Dessa optimeringsbaserade algoritmer använder miljarder maskiner för att samordnat lösa storskaliga problem inom önskvärd träningstid. Emellertid utgör de utmaningar, från hårdvaru- och dataheterogenitet (eftersom olika enheter har olika datorkraft och data) till integritets- och säkerhetsproblematik (där data kan extraheras från de överförda parametrarna). Bland dessa utmaningar utgör kommunikationsoverhead en stor del av prestandaflaskhalsen för algoritmerna. Att kommunicera miljoner problemparametrar mellan maskiner har rapporterats förbruka upp till 80% av träningstiden. För att lätta kommunikationsflaskhalsen utvecklar vi teori och strategier i denna avhandling för att designa kommunikationseffektiva optimeringsalgoritmer. I den första delen tillhandahåller vi enhetliga analysramverk för att analysera prestanda för första ordningens optimeringsalgoritmer med direkt eller felkompenserad komprimering, på en enda maskin och över flera maskiner. Vi skisserar först definitioner av kompressionstekniker som täcker in många kompressorer av praktiskt intresse. Sedan analyserar vi konvergens av första ordningens algoritmer som använder antingen deterministisk eller stokastisk kompression. Våra resultat påvisar den explicita effekten av kompressionsnoggrannhet och asynkrona fördröjningar på steglängd, konvergenshastighet och lösningsnoggrannhet för direktkomprimeringsalgoritmer. Vi vänder sedan vår uppmärksamhet till felkompenserade komprimeringsalgoritmer. Vi utvecklar teoretiska förklaringar till varför felkompenserade komprimeringsalgoritmer uppnår lösningar med godtyckligt högre noggrannhet än direkta komprimeringsalgoritmer. Våra resultat visar starka konvergensgarantier för felkompenserade komprimeringsalgoritmer för distribuerade och federerade inlärningsproblem. I den andra delen tillhandahåller vi flexibla inställningsramverk för att optimera konvergensprestanda för komprimeringsalgoritmer för en mängd olika systemarkitekturer. Vi börjar med att analysera databeroende komplexitet som förklarar varför direktkomprimeringsalgoritmer är mer kommunikationseffektiva än fullprecisionsalgoritmer i praktiken. Denna komplexitet leder till automatiska inställningsstrategier som möjliggör populära komprimeringsalgoritmer på olika kommunikationsnätverk för att maximera både framskridandet av konvergensen mot lösningen och kommunikationseffektiviteten. Vi riktar sedan vår uppmärksamhet mot steglängdsminskningsscheman för att maximera konvergenshastigheten för de algoritmer som använder stokastiska gradienter. Vår analysram baseras på två klasser av system som kännetecknar steglängdernas inverkan på hastigheten av stokastiska gradientalgoritmer. Våra resultat visar att sådana steglängdsscheman gör det möjligt för dessa algoritmer att åtnjuta den optimala hastigheten. Simuleringar av algoritmer i denna avhandling på verkliga problem med referensdatamängder validerar våra teoretiska resultat.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-308978