Unified Privacy Guarantees for Decentralized Learning via Matrix Factorization

Deze paper introduceert een geünificeerde matrixfactorisatiebenadering voor nauwkeurigere privacy-accounting in decentrale learning, wat leidt tot de ontwikkeling van het superieure MAFALDA-SGD-algoritme dat de privacy-utility-trade-off verbetert.

De kern

Stel je voor dat een groep vrienden een geheim recept wil bedenken, maar niemand wil zijn eigen ingrediëntenlijst aan de anderen laten zien. Ze zitten verspreid over de stad en communiceren alleen met hun directe buren. Dit is Decentralized Learning: een manier om samen slimme computers (modellen) te trainen zonder dat iemand zijn privé-data hoeft te delen.

Het probleem? Als ze gewoon met elkaar praten, kunnen slimme buren misschien toch raden wat de andere in zijn lijstje heeft staan. Om dit te voorkomen, voegen ze "ruis" (statistische ruis) toe aan hun berichten. Dit is Differential Privacy: het toevoegen van statische ruis zodat niemand precies kan zien wat er echt gezegd werd.

Maar tot nu toe was dit een lastig spelletje. De manier waarop ze de ruis berekenden, was vaak te conservatief. Het was alsof ze een enorme, zware deken over hun hoofd trokken om zich te beschermen, waardoor ze nauwelijks nog konden zien of bewegen (de resultaten waren niet goed genoeg).

De grote doorbraak in dit paper: De "Ruis-Orkestratie"

De auteurs van dit paper (uit Frankrijk en Oostenrijk) hebben een nieuwe manier bedacht om die ruis te regelen. Ze noemen hun methode MAFALDA-SGD.

Hier is hoe het werkt, vertaald naar een alledaags verhaal:

1. Het oude probleem: De losse flodders

Stel je voor dat elke vriend in het netwerk elke keer als hij spreekt, een nieuwe, willekeurige ruis toevoegt. Omdat ze allemaal apart werken, is het voor de "privacy-rekenmachine" heel moeilijk om te weten hoeveel ruis er precies is. De rekenmachine denkt dan: "Oh, er is zoveel ruis, we moeten heel streng zijn!" En als je te streng bent, wordt je model niet slim genoeg.

2. De nieuwe oplossing: Het Matrix-Factorisatie-Orkest

De auteurs zeggen: "Wacht even, we hoeven niet iedereen los te laten." Ze gebruiken een wiskundige techniek genaamd Matrix Factorization.

In plaats van dat iedereen zijn eigen losse ruis toevoegt, denken ze na over het geheel. Ze kijken naar het hele netwerk als één groot orkest.

• De analogie: Stel je voor dat de ruis niet uit losse, willekeurige geluidjes bestaat, maar uit een zorgvuldig samengesteld muziekstuk. Als vriend A een beetje ruis toevoegt, weet vriend B precies hoe die ruis klinkt en kan hij die "opheffen" of juist versterken op een slimme manier.
• Door de ruis gecorrleerd te maken (op elkaar af te stemmen), kunnen ze precies de hoeveelheid ruis toevoegen die nodig is voor privacy, zonder dat het de kwaliteit van het recept (het model) verpest.

3. Waarom is dit zo slim?

In het verleden dachten onderzoekers: "We moeten ruis toevoegen alsof we in eenzaamheid werken." Maar in een netwerk praten mensen met elkaar. De auteurs tonen aan dat je die gesprekken kunt gebruiken om de privacy te versterken.

Het is alsof je in een drukke kamer staat. Als je fluistert, hoor je niemand. Maar als iedereen tegelijkertijd fluistert met een specifiek ritme, kun je als luisteraar (de aanvaller) nog steeds niets verstaan, terwijl de sprekers elkaar perfect begrijpen.

Wat hebben ze gedaan?

1. Een nieuwe taal: Ze hebben bewezen dat je alle bestaande methoden voor decentraal leren kunt vertalen naar deze nieuwe "matrix-taal". Hierdoor kunnen ze de privacy van oude methoden veel nauwkeuriger berekenen. Het blijkt dat die oude methoden vaak veel veiliger waren dan gedacht, maar dat we het niet goed hadden gemeten.
2. Een nieuw algoritme (MAFALDA-SGD): Ze hebben een nieuw spelbedacht (een algoritme) dat deze nieuwe techniek gebruikt. In tests met echte data (zoals huizenprijzen voorspellen of handschrift herkennen) bleek dit nieuwe algoritme veel beter te presteren dan de oude methoden. Het leert sneller en maakt minder fouten, terwijl het net zo goed beschermd is.

De conclusie in één zin

De auteurs hebben ontdekt dat je in een decentraal netwerk de "ruis" die je toevoegt voor privacy niet als een lastige rommel moet zien, maar als een symfonie. Als je die ruis slim op elkaar afstemt (met hun nieuwe methode), kun je een veel slimmere AI bouwen zonder dat iemands geheimen worden onthuld.

Het is een stap voorwaarts naar een wereld waar we samenwerken aan slimme technologie, zonder dat we onze privacy hoeven op te geven.

Technische samenvatting

Probleemstelling

Decentraal Leren (DL) stelt gebruikers in staat om modellen gezamenlijk te trainen zonder ruwe data te delen, door lokale updates te middelen via een peer-to-peer netwerk. Hoewel dit schaalbaarheid biedt en data lokaal houdt, is decentralisatie op zichzelf onvoldoende voor privacy. Uitgewisselde berichten kunnen nog steeds gevoelige informatie lekken die leidt tot inferentie of reconstructie van lokale data.

Om privacy te waarborgen wordt vaak Differentiële Privacy (DP) gebruikt. Echter, in DL-contexten leidt de toepassing van DP vaak tot een slechtere afweging tussen privacy en bruikbaarheid (utility) vergeleken met centraal leren. Dit komt door twee hoofdoorzaken:

1. Beperkte accounting-methoden: Bestaande methoden voor het berekenen van privacyverliezen (privacy accounting) in DL zijn vaak ad-hoc en specifiek voor bepaalde algoritmen of vertrouwensmodellen. Ze negeren vaak de correlaties in ruis die ontstaan door redundante uitwisselingen tussen knooppunten over tijd en parallelle communicatie.
2. Conservatieve aannames: Veel analyses gaan uit van Local DP (LDP), waarbij wordt verondersteld dat een aanvaller alle berichten ziet. Dit is te conservatief voor realistischere modellen zoals Pairwise Network DP (PNDP) of Secret-based LDP (SecLDP), wat resulteert in overmatig pessimistische privacygrenzen.

Er is dus behoefte aan een geünificeerde, principiële aanpak om privacy in DL nauwkeuriger te analyseren en nieuwe, efficiëntere algoritmen te ontwerpen.

Methodologie

De auteurs introduceren een raamwerk dat Matrix Factorization (MF) uit centraal DP-SGD uitbreidt naar Decentraal Leren.

1. Unificatie via Matrix Factorization:

   • In centraal leren wordt MF gebruikt om ruis over iteraties te correleren, wat de privacy-utility trade-off verbetert. De auteurs tonen aan dat DL-algoritmen en diverse vertrouwensmodellen (LDP, PNDP, SecLDP) kunnen worden herschreven als een lineaire transformatie van gradiënten en ruis: $O_A = AG + BZ$.
   • Hierbij is $O_A$ de kennis van de aanvaller, $G$ de gradiënten, $Z$ de ruis, en $A, B$ matrices die de algoritme-dynamica en het vertrouwensmodel weergeven.
   • Ze bewijzen dat er altijd een factorisatie $A = BC$ bestaat, wat de basis vormt voor het toepassen van MF-mechanismen in DL.

2. Generalisatie van Privacy-Garanties:

   • Bestaande MF-resultaten vereisen dat de workload-matrix vierkant, vol-rang en onder-driehoekig is. De auteurs generaliseren deze theorie naar rechthoekige en rang-gedeficiëerde matrices (kolom-echelon vorm).
   • Ze definiëren een nieuwe gegeneraliseerde sensitiviteit ($\text{sens}_\Pi(C; B)$) die rekening houdt met de decoder-matrix $B$ (wat de aanvaller ziet) en de encoder-matrix $C$ (hoe ruis wordt toegepast).
   • Dit stelt hen in staat om adaptieve gradiënten en gedeeltelijke kennis van aanvallen (zoals in PNDP) correct te analyseren, wat leidt tot strakkere privacygrenzen.

3. Ontwerp van MAFALDA-SGD:

   • Gebaseerd op dit raamwerk stellen de auteurs MAFALDA-SGD (MAtrix FActorization for Local Differentially privAte SGD) voor.
   • Dit algoritme optimaliseert de correlatie van ruis specifiek voor DL. In tegenstelling tot eerdere methoden die ruis alleen binnen een knooppunt correleren of vaste patronen gebruiken, lost MAFALDA-SGD een optimalisatieprobleem op om de ruiscorrelatie te minimaliseren onder de gegeven privacybeperkingen.
   • Het algoritme gebruikt een lokale ruisstructuur ($C = C_{local} \otimes I_n$) om vertrouwen tussen knooppunten te vermijden, maar corrigeert de ruis binnen de tijdsserie van elk individueel knooppunt.

Belangrijkste Bijdragen

1. Unificatie: Een geünificeerde formulering die bestaande DL-algoritmen en vertrouwensmodellen (LDP, PNDP, SecLDP) onder één raamwerk van Matrix Factorization brengt.
2. Theoretische Generalisatie: Uitbreiding van de MF-theorie naar bredere klassen van matrices, waardoor striktere privacygaranties mogelijk zijn voor adaptieve DL-scenario's.
3. Nieuw Algoritme: De introductie van MAFALDA-SGD, een gossip-gebaseerd algoritme met geoptimaliseerde, gecorreleerde ruis op gebruikersniveau.
4. Verbeterde Accounting: Een methode om privacyverlies nauwkeuriger te berekenen voor bestaande algoritmen, wat leidt tot significante verbeteringen in de geschatte privacybudgetten.

Resultaten

De auteurs evalueren hun aanpak op synthetische en real-world grafen (o.a. Facebook Ego, PeerTube, Florentine Families) en datasets (Housing, FEMNIST).

• Strakkere Accounting voor PNDP: Bij het analyseren van bestaande algoritmen (zoals DP-D-SGD) onder het PNDP-model, toont hun methode een aanzienlijk strakkere privacyverliesberekening (tot een orde van grootte beter) vergeleken met eerdere methoden (Cyffers et al., 2022), vooral voor knooppunten die verder van de aanvaller verwijderd zijn.
• Superieure Prestaties van MAFALDA-SGD:
  • MAFALDA-SGD presteert aanzienlijk beter dan bestaande methoden (DP-D-SGD, AntiPGD) onder Local DP.
  • Op de Housing dataset bereikt het een 31% verbetering in testverlies (bij een vast privacybudget) of een 2-voudige reductie in het vereiste privacybudget $\epsilon$ (bij een vast testverlies).
  • Op de FEMNIST dataset (beeldclassificatie) behaalt het consistent hogere testnauwkeurigheid, met name bij hoge privacyniveaus waar gecorreleerde ruis de bruikbaarheid behoudt terwijl de privacy wordt gewaarborgd.
  • In sommige scenario's convergeren concurrenten niet (divergentie), terwijl MAFALDA-SGD wel convergeert.

Betekenis

Dit paper legt een fundamentele brug tussen twee onderzoeksvelden: Matrix Factorization voor privacy in centraal leren en Differentiële Privacy in decentraal leren. De belangrijkste implicaties zijn:

• Principiële Ontwerp: Het biedt een gestructureerde manier om nieuwe privacy-bewuste DL-algoritmen te ontwerpen in plaats van te vertrouwen op ad-hoc bewijzen.
• Efficiëntie: Het demonstreert dat door slimme correlatie van ruis (in plaats van onafhankelijke ruis toe te voegen), de privacy-utility trade-off in decentrale systemen drastisch kan worden verbeterd.
• Praktische Toepasbaarheid: De resultaten tonen aan dat decentraal leren met sterke privacygaranties praktischer en schaalbaarder wordt, wat essentieel is voor toepassingen in gezondheidszorg, sociale media en IoT waar data-souvereiniteit cruciaal is.

Kortom, de auteurs tonen aan dat decentraal leren niet per se een slechtere privacy-utility trade-off hoeft te hebben dan centraal leren, mits de ruiscorrelaties correct worden gemodelleerd en geoptimaliseerd via Matrix Factorization.