Vi anser att problemet med PAC-lärande från distribuerade data och analysera grundläggande kommunikations komplexitet frågor inblandade. Vi tillhandahåller allmänna övre och nedre gränser för den mängd kommunikation som behövs för att lära sig bra, vilket visar att förutom VC-dimension och att täcka antal, mängder såsom undervisning-dimension och misstag bundna av en klass spelar en viktig roll. Vi presenterar också snäva resultat för ett antal gemensamma konceptklasser inklusive samband, paritetsfunktioner och beslutslistor. För linjära avskiljare visar vi att för icke-koncentrerade distributioner kan vi använda en version av Perceptronalgoritmen för att lära oss med mycket mindre kommunikation än det antal uppdateringar som ges av den vanliga marginalen. Vi visar också hur boosting kan utföras på ett generiskt sätt i den distribuerade inställningen för att uppnå kommunikation med endast logaritmiskt beroende av 1/ på någon konceptklass, och visa hur nyligen arbete på agnostiskt lärande från klass-villkorliga frågor kan användas för att uppnå låg kommunikation i agnostiska inställningar också. Vi presenterar dessutom en analys av integritet, med tanke på både differential integritet och en uppfattning om distributionsintegritet som är särskilt tilltalande i detta sammanhang.
REF studerade problemet med PAC-lärande från distribuerade data och analyserade kommunikationskomplexiteten i termer av olika komplexa mått på hypotesutrymmet.
Distributed Learning, Communication Complexity and Privacy
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}