Certifying the Right to Be Forgotten: Primal-Dual Optimization for Sample and Label Unlearning in Vertical Federated Learning

Dit artikel introduceert FedORA, een methode op basis van primal-dual optimalisatie die het effectief en efficiënt verwijderen van specifieke data of labels mogelijk maakt in verticaal federatief leren, terwijl de modelprestaties behouden blijven en de communicatie- en rekenkosten worden verlaagd.

De kern

Stel je voor dat je een gigantische, gezamenlijke kookclub hebt. In deze club (wat we Verticale Federated Learning noemen) bereiden verschillende mensen samen een gerecht. Maar hier is de twist: niemand deelt zijn eigen ingrediënten.

• Persoon A heeft alleen de groenten.
• Persoon B heeft alleen de kruiden.
• Persoon C heeft alleen het vlees en de saus.

Samen maken ze een geweldig recept (een AI-model). Maar wat als Persoon A later zegt: "Wacht even, ik wil niet dat mijn specifieke groenten in dit recept zitten. Vergeet ze!" Of wat als de wet zegt: "We mogen geen vlees meer gebruiken, vergeet dat hele ingrediënt!"

In het verleden was de enige oplossing om de hele pot leeg te gooien en het recept vanaf nul opnieuw te koken. Dat kost enorm veel tijd en energie.

Deze paper introduceert FedORA, een slimme nieuwe manier om specifieke ingrediënten uit het gerecht te "vergeten" zonder de hele pot te hoeven herstarten. Hier is hoe het werkt, vertaald in alledaags taal:

1. Het Probleem: Het "Vergeten" is lastig

In een normale situatie zou je proberen het recept te "ongedaan maken" door het recept bewust te verpesten (zoals een chef die de groenten bitter maakt). Maar dat werkt vaak slecht: je verpest ook de smaak van de rest van het gerecht, of je vergeet de groenten niet echt, maar maakt ze alleen maar raar.

2. De Oplossing: FedORA (De Slimme Chef)

FedORA is een algoritme dat werkt met een Primaal-Duale strategie. Laten we dit vergelijken met een gesprek tussen twee chefs:

• De Primaal-Chef (De Kijker): Deze chef kijkt naar de rest van het gerecht en zorgt dat het lekker blijft smaken. Hij wil dat de groenten en kruiden die wel blijven, perfect samensmelten.
• De Duale Chef (De Vergeter): Deze chef kijkt alleen naar de ingrediënten die weg moeten. Zijn taak is niet om ze bitter te maken, maar om ze onvoorspelbaar te maken.

De Gouden Regel van FedORA:
In plaats van te zeggen: "Maak deze groente bitter!" (wat de hele pot verpest), zegt FedORA: "Maak deze groente zo onduidelijk, dat niemand meer weet of het spinazie of sla is."
Als het model niet meer zeker weet wat het ziet, is het effectief "vergeten". Het is alsof je de groente in een nevel van onzekerheid gooit.

3. De Slimme Trucs van FedORA

FedORA heeft drie speciale trucs om dit snel en veilig te doen:

• Truc 1: De "Onzekerheids-Loss" (De Nevel)
  Normale methoden proberen het model dwingen om fouten te maken met de te vergeten data. FedORA doet iets slimmers: het vraagt het model om twijfel te tonen. Het model moet zeggen: "Ik weet het niet, het kan alles zijn." Dit is veiliger en verpest de rest van het recept niet.

• Truc 2: De Adaptieve Stapgrootte (De Dans)
  Stel je voor dat je probeert een danspas te leren. Als je te hard trapt, val je om. Als je te zacht trapt, kom je nergens. FedORA past zijn "stapgrootte" continu aan. Als het model stabiel is, maakt het grotere stappen om sneller klaar te zijn. Als het wankelt, maakt het kleinere, voorzichtigere stappen. Dit zorgt voor een soepele dans zonder valpartijen.

• Truc 3: Asymmetrisch Bakken (De Halfvolle Pan)
  Dit is misschien wel de slimste truc.

  • Voor de ingrediënten die weg moeten, kookt FedORA de hele pan uit (alle data wordt bekeken).
  • Voor de ingrediënten die blijven, hoeft hij niet de hele pan te roeren. Hij pakt er maar een klein beetje uit (een steekproef).
  • Waarom? Omdat de resterende ingrediënten al bekend zijn met het recept. Ze hoeven niet opnieuw te worden "geleerd", alleen even opgefrist. Dit bespaart enorm veel tijd en energie.

4. Waarom is dit belangrijk?

De paper bewijst wiskundig dat FedORA net zo goed werkt als het volledig opnieuw koken van het gerecht (vanaf nul), maar dan veel sneller en met minder energie.

• Privacy: Als iemand vraagt om zijn data te vergeten (het "Recht om vergeten te worden"), kan FedORA dit doen zonder dat de rest van de club (de andere data) last heeft.
• Veiligheid: Het zorgt ervoor dat hackers niet kunnen achterhalen of een specifiek ingrediënt (data) in het recept zat, en dat "versteekte" smaken (zoals achterdeurtjes in de software) echt verdwijnen.

Samenvatting in één zin

FedORA is een slimme, efficiënte manier om specifieke data uit een gezamenlijk AI-model te verwijderen door het model te leren "twijfelen" over die data, terwijl het de rest van het model intact en snel houdt, zonder dat je alles opnieuw hoeft te bouwen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Certifying the Right to be Forgotten: Primal-Dual Optimization for Sample and Label Unlearning in Vertical Federated Learning" in het Nederlands.

Titel

Certificeren van het Recht om Vergeten te Worden: Primaal-Duale Optimalisatie voor Steekproef- en Label-Vergeten in Verticale Federatie Learning.

1. Het Probleem

In de context van Federated Learning (FL) ontstaan privacyzorgen doordat AI-modellen gevoelige gegevens kunnen "onthouden" tijdens het trainingsproces. Reguleringen zoals de GDPR eisen het "recht om vergeten te worden", wat betekent dat niet alleen de ruwe data moet worden verwijderd, maar ook de invloed van die data op het getrainde model.

Hoewel "federated unlearning" (het verwijderen van data-invloed) veel bestudeerd is in Horizontale Federated Learning (HFL), blijft dit een grote uitdaging in Verticale Federated Learning (VFL). In VFL delen meerdere partijen (partijen) dezelfde gebruikers, maar hebben ze elk verschillende, complementaire kenmerken (features) van die gebruikers.

• Uitdagingen: Het verwijderen van specifieke steekproeven (sample unlearning) of volledige klassen (label unlearning) vereist coördinatie tussen alle partijen. Bestaande methoden (zoals gradient ascent) zijn vaak instabiel, leiden tot "catastrophic forgetting" (het model vergeet te veel en verliest nuttige kennis) of zijn computatief te duur omdat ze het hele model opnieuw moeten trainen.

2. Methodologie: FedORA

De auteurs stellen FedORA (Federated Optimization for data Removal via primal-dual Algorithm) voor. Dit is een nieuw raamwerk dat unlearning formuleert als een beperkt optimalisatieprobleem opgelost met een primaal-dual (primal-dual) framework.

Kerncomponenten van FedORA:

• Primaal-Duale Formulering:

  • Het doel is om de verliezen op de overgebleven data te minimaliseren, terwijl de verliezen op de te vergeten data boven een bepaalde drempel ($\gamma$) worden gehouden.
  • Dit wordt opgelost via Lagrange-multiplicatoren. De primaalvariabelen (modelparameters) zorgen voor het behoud van prestaties op de resterende data. De duale variabelen fungeren als een certificaat voor de sterkte van het vergeten; ze verhogen de druk op het model om de doeldata te vergeten als de constraint niet wordt voldaan.

• Nieuwe Verliesfunctie (Uncertainty-based Loss):

  • In tegenstelling tot traditionele methoden die proberen de doeldata verkeerd te classificeren (wat instabiliteit veroorzaakt), streeft FedORA naar classificatie-onzekerheid.
  • De loss-functie maximaliseert de entropie van de voorspellingen voor de te vergeten data en minimaliseert de Kullback-Leibler (KL)-divergentie ten opzichte van een uniforme verdeling. Dit dwingt het model om de doeldata "niet te kennen" in plaats van ze actief verkeerd te labelen.

• Adaptieve Stapgrootte:

  • Om convergentie te stabiliseren, past FedORA de stapgroottes (voor zowel primaal als duaal) dynamisch aan op basis van de verandering in modelparameters tussen iteraties. Als de veranderingen te groot zijn, wordt de stap verkleind; bij kleine veranderingen wordt deze vergroot.

• Asymmetrische Batch-ontwerp:

  • Om de rekentijd te verminderen, behandelt FedORA de twee datasets verschillend:
    • Te vergeten data: Wordt volledig verwerkt (full batch) om zeker te zijn van volledige verwijdering.
    • Overgebleven data: Wordt slechts verwerkt via een klein deel van de batches (asymmetrisch). Omdat deze data al invloed heeft gehad tijdens de initiële training, is volledige hertraining niet nodig om de prestaties te behouden. Dit vermindert de communicatie- en rekentijd aanzienlijk.

3. Belangrijkste Bijdragen

1. Eerste Primal-Dual Methode voor VFL: FedORA is de eerste methode die unlearning in VFL (voor zowel samples als labels) formuleert als een beperkt optimalisatieprobleem, wat een betere balans biedt tussen vergeten en prestatiebehoud.
2. Uncertainty Loss: Introductie van een loss-functie die onzekerheid bevordert in plaats van misclassificatie, wat de instabiliteit van bestaande methoden (zoals gradient ascent) oplost.
3. Efficiëntie en Stabiliteit: Combinatie van een adaptieve stapgrootte-mechanisme en een asymmetrische batch-strategie die de computatiekosten verlaagt zonder de kwaliteit van het vergeten te compromitteren.
4. Theoretische Garantie: De auteurs bewijzen wiskundig dat het verschil tussen het FedORA-model en een model dat volledig opnieuw is getraind ("Train-from-scratch") begrensd is, wat de effectiviteit van het vergeten garandeert.

4. Resultaten

FedORA werd geëvalueerd op diverse datasets (tabulaire data: Income; beelddata: MedMNIST, CIFAR-10, CIFAR-100, Tiny-ImageNet) en vergeleken met bestaande methoden (Retrain, Gradient Ascent, ICO, CVFU).

• Prestatiebehoud (Utility Preservation): FedORA behaalt testnauwkeurigheden die zeer dicht bij de "Train-from-scratch" benchmark liggen, vaak beter dan andere unlearning-methoden, vooral op complexe datasets.
• Effectiviteit van Vergeten: FedORA toont een lagere nauwkeurigheid op de te vergeten data (betere prestatie voor vergeten) vergeleken met concurrenten.
• Aanvalbestendigheid:
  • Lidmaatschapsinferentie-aanvallen (MIA): De successkans van aanvallen (MIA-ASR) ligt dicht bij 50% (random guessing), wat aangeeft dat het model de lidmaatschap van de data niet meer kan onderscheiden.
  • Backdoor-aanvallen: De successkans van backdoor-aanvallen (BD-ASR) is zeer laag (<10%), wat aantoont dat de achterdeuren die in de te vergeten data zaten, effectief zijn verwijderd.
• Efficiëntie: FedORA is aanzienlijk sneller dan "Retrain" en vermindert de communicatie- en rekentijd door de asymmetrische batch-strategie, terwijl het sneller convergeert dan methoden zoals ICO.

5. Betekenis en Conclusie

Dit werk is van groot belang voor de implementatie van privacy-vriendelijke AI-systemen in verticale federale omgevingen. Het biedt een wiskundig onderbouwd en praktisch efficiënt mechanisme om aan de "Right to be Forgotten" te voldoen zonder de hele infrastructuur opnieuw te moeten trainen.

Door het probleem te herformuleren als een constrained optimization probleem en gebruik te maken van dualiteit, biedt FedORA niet alleen een oplossing voor de technische complexiteit van VFL, maar ook een certificering van de effectiviteit van het vergeten. De methode is robuust tegen verschillende data-distributies (IID en non-IID) en compatibel met privacy-bevorderende technieken zoals differentieel privacy (DP), wat het toepasbaar maakt voor real-world scenario's waar privacy en efficiëntie cruciaal zijn.