Decentraliserad maskininlärning är ett lovande framväxande paradigm med tanke på globala utmaningar när det gäller dataägande och integritet. Vi överväger att lära oss linjär klassificering och regressionsmodeller, i den miljö där träningsdata är decentraliserad över många användarenheter, och inlärningsalgoritmen måste köras ondevice, på ett godtyckligt kommunikationsnät, utan en central samordnare. Vi föreslår COLA, en ny decentraliserad utbildningsalgoritm med starka teoretiska garantier och överlägsen praktisk prestanda. Vårt ramverk övervinner många begränsningar av befintliga metoder, och uppnår kommunikation effektivitet, skalbarhet, elasticitet samt motståndskraft mot förändringar i data och möjliggör opålitliga och heterogena deltagande enheter. * Dessa två författare bidrog lika 32:a konferensen om neurala informationsbehandlingssystem (NeurIPS 2018), Montréal, Kanada. Bidrag. I detta dokument är vårt huvudsakliga bidrag att föreslå COLA, ett nytt decentraliserat ramverk för utbildning, generaliserade linjära modeller med konvergensgarantier. Vårt system löser både beskrivna frågor i befintliga strategier, med hjälp av tekniker från primal-dual optimering, och kan ses som en generalisering av COCOA [Smith et al., 2018] till den decentraliserade inställningen. Mer specifikt, den föreslagna algoritmen erbjuder - Konvergens Garantier: Linjära och sublinjära konvergensgrader garanteras för starkt konvexa respektive allmänna konvexa mål. Våra resultat är fria från de restriktiva antaganden som gjorts av stokastiska metoder, Wang et al., 2017, vilket kräver i.i.d. Datadistribution över alla enheter. -Kommunikationseffektivitet och användbarhet: Genom att använda ett data-lokalt subproblem mellan varje kommunikationsrunda uppnår COLA inte bara kommunikationseffektivitet utan gör det också möjligt att återanvända befintliga effektiva enmaskinslösare för inlärning på en enhet. Vi tillhandahåller praktiska decentraliserade primal-dual certifikat för att diagnostisera inlärningen framsteg. -Elasticitet och feltolerans: Till skillnad från summerade metoder som SGD, är COLA bevisligen motståndskraftig mot förändringar i data, i nätverket topologi, och deltagande enheter försvinner, stryper eller återkommer i nätverket. Vårt genomförande är offentligt tillgängligt under github.com/epfml/cola. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Mer exakt, W ij  till [0, 1] betecknar anslutningen styrka mellan noder i och j, med en icke-noll vikt som indikerar förekomsten av en parvis kommunikationslänk. Vi antar att W är symmetriskt och dubbelt stokastiskt, vilket betyder att varje rad och kolumn av W summor till en. De spektralegenskaper av W som används i detta papper är att eigenvärdena av W är verkliga, och 1 = λ 1 (W) ≥ · · · ≥ λ n (W) ≥ −1. Låt den näst största magnituden av eigenvärdena av W vara β := max{ och λ 2 (W) på,  till λ n (W)}. 1 − β kallas spektralgapet, en mängd som är välstuderad i grafteori och nätverksanalys. Den spektralgap mäter graden av anslutning mellan noder. I det extrema fallet när W är diagonal, och därmed en identitetsmatris, den spektral gap är 0 och det finns ingen kommunikation mellan noder. För att säkerställa konvergens av decentraliserade algoritmer, kräver vi
REF tar upp den mer specifika problemklassen av generaliserade linjära modeller.
COLA: Decentralized Linear Learning
{'venue': 'NeurIPS', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}