Technische Samenvatting: LOSCAR-SGD

Probleemstelling

Gedistribueerd leren, met name in omgevingen voor grootschalig en federatief leren, ondervindt een aanzienlijke bottleneck door communicatiekosten. Hoewel standaardbenaderingen zoals gesynchroniseerde Minibatch SGD communicatie vereisen bij elke iteratie, zijn er drie primaire strategieën ontwikkeld om dit te mitigeren: lokaal trainen (het uitvoeren van meerdere lokale stappen voordat er wordt gesynchroniseerd), communicatiecompressie (het verzenden van verspreide of gekwantiseerde data) en overlappen van communicatie en berekening (het voortzetten van lokale optimalisatie terwijl berichten onderweg zijn).

Hoewel deze technieken afzonderlijk goed bestudeerd en praktisch effectief zijn, ontbreekt er theoretische analyse voor methoden die alle drie de componenten gelijktijdig combineren. Bovendien hebben bestaande theorieën vaak moeite om heterogeniteit van workers te verklaren, waarbij workers verschillende rekensnelheden hebben en dus een verschillend aantal lokale stappen uitvoeren binnen hetzelfde tijdsvenster. Het artikel adresseert de lacune in het begrijpen hoe verspreidheid, overlap en heterogene aantallen lokale stappen interageren om convergentie en trainingtijd te beïnvloeden.

Methodologie: LOSCAR-SGD

De auteurs stellen LOSCAR-SGD (Local SGD with Overlapped Sparse Corrected AveRaging) voor, een raamwerk ontworpen voor data-homogene gedistribueerde optimalisatie dat vier kerncomponenten integreert:

1. Lokaal Trainen: Workers voeren meerdere stochastische gradiëntafdaal (SGD)-stappen lokaal uit.
2. Verspreide Modelgemiddelde: In plaats van het volledige model te synchroniseren, communiceren workers alleen een willekeurige subset van $K$ coördinaten (verspreidingsniveau).
3. Overlappen van Communicatie en Berekening: Workers blijven niet inactief tijdens de communicatiefase. Ze blijven lokale SGD-stappen uitvoeren terwijl de verspreide modelupdate wordt geaggregeerd en verzonden.
4. Worker-specifieke Aantallen Lokale Stappen: Het algoritme komt tegemoet aan heterogene workersnelheden door verschillende workers toe te staan een verschillend aantal lokale stappen te nemen ($N_i$ voor communicatie en $Q_i$ tijdens communicatie) op basis van hun individuele rekentijden $\tau_i$.

De Vertraging-gecorrigeerde Samenvoegregel

Een cruciale innovatie van LOSCAR-SGD is de samenvoegregel. Bij standaard overlap-methoden overschrijven workers bij het aankomen van een vertraagde gesynchroniseerde bericht vaak gewoon hun lokale coördinaten met het gemiddelde van de server. Dit gooit de vooruitgang behaald tijdens de overlap-fase weg.

LOSCAR-SGD hanteert een vertraging-gecorrigeerde samenvoegregel. Wanneer het verspreide gemiddelde van de server $\bar{y}_r$ (gebaseerd op modellen $y_r$ aan het begin van communicatie) aankomt, combineert de worker dit met zijn huidige lokale model $z_r$ (dat tijdens communicatie is gevorderd). Voor de gesynchroniseerde coördinaten $j \in S_r$ is de update:
$$x_{i,j}^{r+1} = \bar{y}_{r,j} + (z_{i,j}^r - y_{i,j}^r)$$
Dit voegt effectief de correctie van de server toe aan de lokale vooruitgang van de worker ($z - y$) in plaats van de lokale staat te overschrijven. Voor niet-gesynchroniseerde coördinaten behoudt de worker simpelweg zijn laatste lokale iteratie $z_{i,j}^r$.

Belangrijkste Bijdragen

1. Unificerend Raamwerk: Het artikel introduceert het eerste theoretische raamwerk dat gelijktijdig lokaal trainen, verspreide synchronisatie, het overlappen van communicatie en berekening, en worker-specifieke aantallen lokale stappen analyseert.
2. Vertraging-gecorrigeerde Samenvoeging: De auteurs stellen een samenvoegregel voor en analyseren deze die lokale vooruitgang behaald tijdens de communicatie-overlap behoudt, in contrast met naïef overschrijven.
3. Convergentiegaranties: Het artikel biedt convergentiegaranties voor gladde niet-convexe doelfuncties. De afgeleide grenzen tonen aan dat:
   • De leidende stochastische term de standaard lineaire versnelling van minibatch met $n$ behoudt.
   • De extra kosten geïntroduceerd door lokaal trainen, verspreiding en overlap alleen als hogere-orde termen verschijnen (schaalend met $\eta^2$).
   • De grenzen expliciet kwantificeren hoe verspreidheid ($K$), overlapduur ($\zeta$) en heterogeniteit ($H_{max}$) de convergentiesnelheid beïnvloeden.
4. Tijdcomplexiteitsanalyse: De auteurs leiden grenzen voor de wandkloktijdcomplexiteit af, waarbij blijkt dat de leidende term afhangt van het harmonisch gemiddelde van de rekentijden van workers, terwijl de overhead van overlap en verspreiding gecontroleerd blijft.

Experimentele Resultaten

De auteurs evalueerden LOSCAR-SGD met behulp van een op PyTorch gebaseerde logica-tijd simulator op het a9a-logistieke regressie-dataset, evenals CIFAR-10 en Tiny ImageNet met neurale netwerken. Belangrijkste bevindingen zijn:

• Overlap-efficiëntie: Het overlappen van communicatie en berekening reduceert consistent de traintijd in vergelijking met blokkerende verspreide gemiddelden, omdat het inactieve communicatietijd omzet in nuttige lokale berekening.
• Superioriteit van de Samenvoegregel: De vertraging-gecorrigeerde samenvoegregel presteert consistent beter dan naïef overschrijven, vooral wanneer communicatievertragingen groot zijn. Het naïeve overschrijven gooit de vooruitgang behaald tijdens de overlap-fase weg, wat leidt tot langzamere convergentie.
• Verspreidheidsafweging: Aggressieve verspreiding (bijvoorbeeld het communiceren van slechts 0,1% van de coördinaten) reduceert communicatiekosten met ordes van grootte met slechts een bescheiden straf in optimalisatieprestaties in homogene data-omgevingen.
• Robuustheid: De vertraging-gecorrigeerde variant blijft stabiel over verschillende lokale berekeningsbudgetten en niveaus van worker-heterogeniteit, terwijl blokkerende methoden gevoeliger zijn voor deze parameters.

Opmerking: De auteurs merken op dat in sterk heterogene data-regimes (niet-I.I.D.) agressieve overlap kan leiden tot client-drift en suboptimale convergentie, een beperking van de huidige theorie die data-homogeniteit veronderstelt.

Betekenis en Claims

Het artikel claimt de eerste theoretische analyse te bieden die de combinatie van lokaal trainen, verspreide synchronisatie, het overlappen van communicatie en berekening, en worker-heterogeniteit bestrijkt.

De betekenis ligt in het aantonen dat deze praktische efficiëntietechnieken kunnen worden gecombineerd zonder theoretische convergentiegaranties op te offeren. De auteurs tonen aan dat de "extra fout" veroorzaakt door de veroudering inherent aan overlap en verspreiding een gecontroleerde, hogere-orde term is. Bijgevolg bereikt de methode de standaard minibatch-versnelling in de leidende term, terwijl het praktische reducties in wandkloktijd biedt. Het werk overbrugt de kloof tussen praktische heuristieken voor gedistribueerd trainen en rigoureuze convergentietheorie, en valideert dat het "verbergen" van communicatielatentie door overlap en het corrigeren voor de resulterende veroudering een theoretisch onderbouwde strategie is voor grootschalig gedistribueerd leren.