Descend or Rewind? Stochastic Gradient Descent Unlearning

Deze paper bewijst $(\varepsilon, \delta)$-gecertificeerde onthullingsgaranties voor de stochastische versies van de D2D- en R2D-algoritmen voor convex en niet-convex verlies, en concludeert dat D2D superieur is voor sterk convexe functies terwijl R2D beter geschikt is voor convex en niet-convex verlies.

De kern

Titel: Vergeten in de AI-wereld: Afdalen of Terugspoelen?

Stel je voor dat je een enorme bibliotheek hebt vol met boeken die je hebt geschreven om een slimme robot (een AI) te leren. Je robot is nu heel goed in het beantwoorden van vragen. Maar plotseling zegt iemand: "Hé, die ene pagina die ik heb geschreven, wil ik niet meer dat de robot die kent. Vergeet het!"

In de echte wereld is dit een recht: het "recht om vergeten te worden" (zoals in de Europese AVG-wetgeving). Het probleem is dat het opnieuw leren van de hele robot vanaf nul, zonder die ene pagina, extreem lang duurt en veel energie kost. Het is alsof je een heel jaar studeren moet herhalen omdat je één pagina uit je notitieboekje wilt verwijderen.

De onderzoekers van dit papier hebben gekeken naar twee slimme manieren om dit "vergeten" te doen zonder alles opnieuw te leren. Ze noemen deze methoden "Afdalen" (Descent) en "Terugspoelen" (Rewind).

Hier is hoe het werkt, vertaald in simpele taal:

1. De Twee Methodes

Methode A: Afdalen (Descent-to-Delete)

• Het idee: Je neemt de robot die nu klaar is (het eindresultaat) en laat hem een paar stappen "terug" doen op de helling van zijn kennis, maar dan zonder de pagina die je wilt vergeten.
• De analogie: Stel je voor dat je een bal hebt die je de berg afrolt tot hij op de bodem ligt (dat is je getrainde AI). Je wilt dat de bal de berg opduwt, maar dan een stukje verderop dan waar hij nu ligt, zodat hij de "vergeten" steen niet meer raakt.
• Het probleem: Op een ruwe, hobbelige berg (wat de meeste moderne AI-modellen zijn) kan deze bal vastlopen in een klein kuilje. Hij denkt dat hij op de bodem is, maar hij is eigenlijk vast komen te zitten in een lokale put. Hij beweegt niet genoeg om de vergeten informatie echt kwijt te raken, of hij rolt zelfs de verkeerde kant op.

Methode B: Terugspoelen (Rewind-to-Delete)

• Het idee: In plaats van te beginnen bij het eind, ga je terug naar een punt in het verleden waar de robot nog niet helemaal op de bodem zat (bijvoorbeeld halverwege de training). Vanaf dat punt start je de training opnieuw, maar dan zonder de pagina die je wilt vergeten.
• De analogie: Je kijkt in je video-opname van de training en klikt op "terugspoelen" naar 10 minuten geleden. Je laat de robot vanaf dat moment opnieuw leren, maar dan zonder de pagina die je wilt verwijderen. Omdat je verder naar achteren gaat, heb je meer ruimte om de route aan te passen zonder vast te lopen in een kuil.
• Het voordeel: Dit werkt veel beter op de ruwe, hobbelige bergen van moderne AI. De robot blijft soepeler bewegen en komt dichter bij de situatie waar hij de pagina nooit had geleerd.

2. Wat hebben de onderzoekers bewezen?

Voorheen dachten veel mensen dat "Afdalen" de beste manier was, vooral omdat het simpel leek. Maar de onderzoekers hebben met wiskunde bewezen dat:

• Voor simpele, ronde bergen (convexe functies): "Afdalen" werkt prima en is zelfs heel nauwkeurig.
• Voor de echte, hobbelige bergen (niet-convexe functies, zoals bij moderne AI): "Terugspoelen" is de winnaar. "Afdalen" loopt vaak vast of werkt niet goed genoeg. "Terugspoelen" zorgt ervoor dat de robot echt vergeet wat hij niet meer mag weten, zonder dat je alles opnieuw hoeft te leren.

Ze hebben ook bewezen dat je bij het "Terugspoelen" een beetje ruis (statistische verwarring) moet toevoegen aan het einde, zodat niemand kan achterhalen of de robot de pagina wel of niet heeft geleerd. Dit maakt het proces veilig en wettelijk goed.

3. Waarom is dit belangrijk?

• Snelheid: Het is veel sneller dan alles opnieuw leren.
• Veiligheid: Het garandeert wiskundig dat de robot de data echt "vergeten" is, niet alleen dat hij het even niet meer zegt.
• Praktijk: De onderzoekers hebben getest met echte datasets (zoals medische gegevens en gezichten). Ze zagen dat "Terugspoelen" de robot beter deed vergeten dan "Afdalen", terwijl "Afdalen" soms vastliep of zelfs beter ging presteren op de verkeerde data (wat betekent dat hij de informatie niet echt had gewist).

Conclusie

Als je een AI wilt laten vergeten wat hij heeft geleerd, is het vaak beter om terug te spoelen naar een eerdere fase en daar opnieuw te beginnen, dan om vanaf het einde te proberen de weg terug te vinden. Het is alsof je een fout in een boek wilt corrigeren: soms is het beter om een paar pagina's terug te gaan en de zin opnieuw te schrijven, dan om te proberen de zin aan het einde van het boek te wissen terwijl de rest van het verhaal er nog steeds op reageert.

Deze nieuwe regels ("Terugspoelen") zijn nu bewezen veilig en efficiënt, zelfs voor de meest complexe AI-systemen van vandaag.

Technische samenvatting

Titel: Descend or Rewind? Stochastic Gradient Descent Unlearning

Auteurs: Siqiao Mu en Diego Klabjan

---

1. Het Probleem

Machine unlearning (machinaal vergeten) heeft tot doel de invloed van specifieke trainingsdata uit een getraind model te verwijderen zonder het model volledig opnieuw te hoeven trainen. Dit is cruciaal vanwege privacyregels zoals de GDPR (het "recht om vergeten te worden") en de hoge rekenkosten van het hertrainen van grote modellen (zoals LLM's).

Hoewel er al methoden bestaan die theoretische garanties bieden (gecertificeerd unlearning), zijn deze vaak onpraktisch voor moderne diepe leermodellen:

• Veel methoden vereisen tweede-orde informatie (Hessiaan), wat te duur is.
• Bestaande eerste-orde methoden vereisen vaak het berekenen van volledige gradients of zijn beperkt tot convexe functies.
• De huidige "standaard" voor niet-convexe functies is vaak het "finetunen" van het model (een stochastische versie van Descent-to-Delete), maar dit mist een theoretische onderbouwing voor niet-convexe functies en presteert vaak slecht in de praktijk.

De kernvraag van dit paper is: Kunnen we stochastische gradient descent (SGD) versies van twee bestaande methoden, Descent-to-Delete (D2D) en Rewind-to-Delete (R2D), theoretisch garanderen voor niet-convexe functies, en welke methode is beter?

2. Methodologie

De auteurs analyseren twee benaderingen voor unlearning binnen het SGD-kader:

1. Descent-to-Delete (D2D): Start bij het eindpunt van het getrainde model ($\theta_T$) en voert $K$ extra SGD-stappen uit op het behouden dataset ($D'$).
2. Rewind-to-Delete (R2D): "Spoelt terug" naar een eerdere checkpoint ($\theta_{T-K}$) tijdens het trainen en voert vanaf daar $K$ SGD-stappen uit op $D'$.

Technische Aanpak:

• Gekoppelde Trajecten: De analyse gebruikt een "coupling argument". De auteurs koppelen de willekeurige keuzes (mini-batches) van het trainen, het hertrainen (vanaf scratch) en het unlearning-proces. Door de batches zo te kiezen dat ze zoveel mogelijk overeenkomen, kunnen ze de afstand tussen de trajecten minimaliseren.
• Verstoord Gradient Systeem: Ze modelleren het unlearning-proces als een "biased" of verstoord gradient systeem.
  • Voor sterk convex functies: Het systeem is contractief (trajecten komen samen).
  • Voor convex functies: Het systeem is semi-contractief.
  • Voor niet-convex functies: Het systeem kan expanderend zijn (trajecten kunnen uit elkaar drijven).
• Sensitiviteitsgrenzen: In plaats van een deterministische grens (zoals bij klassieke differentieel privacy), leiden ze een grens af voor de verwachte afstand tussen het unlearned model en het hergetrainde model. Door deze verwachtingswaarde te combineren met de Markov-ongelijkheid, verkrijgen ze een staartgrens die leidt tot $(\varepsilon, \delta)$-indistinguishability.
• Gaussian Noise: Aan het einde van het unlearning-proces wordt Gaussisch ruis toegevoegd om de $(\varepsilon, \delta)$-garantie te bereiken.

3. Belangrijkste Bijdragen

1. Theoretische Garanties voor SGD: Het paper bewijst $(\varepsilon, \delta)$-gecertificeerde unlearning garanties voor zowel SGD-R2D als SGD-D2D voor sterk convex, convex en niet-convex verliesfuncties. Dit is een doorbraak, omdat eerdere werken dit niet konden garanderen voor stochastische methoden op niet-convex functies.
2. Nieuw Bewijs voor D2D: Ze ontwikkelen een nieuwe bewijsstrategie voor SGD-D2D op sterk convex functies die de beperkende aannames van eerdere werken (zoals Lipschitz-continuïteit van de gradient) omzeilt.
3. Vergelijking van Benaderingen: Ze tonen aan dat:
   • D2D strakkere probabilistische grenzen biedt voor sterk convex functies.
   • R2D echter superieur en meer geschikt is voor convex en niet-convex functies, omdat het de accumulatie van verstoringen (door de ruis en het verwijderen van data) terugdraait door te "spoelen" naar een eerdere staat.
4. Efficiëntie: Voor sterk convex functies met constante ruis convergeert het aantal benodigde unlearning-iteraties ($K$) naar een constante, zelfs als het aantal trainingsiteraties ($T$) zeer groot is. Dit betekent dat R2D een potentiële oneindige rekenvoordeel heeft ten opzichte van volledig hertrainen.

4. Resultaten

De auteurs hebben experimenten uitgevoerd op twee datasets:

• eICU: Een tabulaire dataset voor medische voorspelling (gebruik van een MLP).
• Lacuna-100: Een beelddataset voor genderclassificatie (gebruik van ResNet-18).

Empirische Bevindingen:

• Niet-convex scenario's (ResNet): R2D werkt betrouwbaar. Het model beweegt weg van het originele model en nadert het hergetrainde model, terwijl de prestaties op het behouden dataset stabiel blijven.
• D2D in niet-convex scenario's: D2D faalt vaak. Het model stagneert vaak in stationaire punten (local minima) of verbetert zelfs de prestaties op het "vergeten" dataset, wat suggereert dat het model de data niet echt heeft vergeten, maar juist beter is gaan generaliseren op de resterende data. Dit is een gevaarlijk effect voor privacy.
• Membership Inference Attacks (MIA): R2D verdedigt succesvoller tegen aanvallen die proberen te bepalen of een data-punt in de training zat. D2D faalt hier vaak in niet-convex settings.
• Trade-off: Er is een duidelijke afweging tussen privacy ($\varepsilon$), nut (modelprestatie) en complexiteit (aantal iteraties $K$). R2D biedt een betere balans voor diepe leermodellen.

5. Betekenis en Impact

Dit werk is significant voor het veld van privacy-preserving machine learning:

• Praktische Toepasbaarheid: Het biedt een "black-box" oplossing die alleen ruis toevoegt na het trainen en het unlearning-proces, zonder dat er speciale procedures tijdens het trainen nodig zijn. Dit maakt het toepasbaar op bestaande, voorgeïmplementeerde modellen.
• Theoretische Validatie: Het lost een belangrijk open vraagstuk op door te bewijzen dat "rewinding" (terugspoelen) een theoretisch onderbouwde en superieure strategie is voor niet-convex deep learning, in tegenstelling tot de veelgebruikte "finetuning" (descend) methode.
• Toekomstige Richting: Het paper legt de basis voor het gebruik van stochastische methoden in gecertificeerd unlearning, wat essentieel is voor de schaalbaarheid van privacy-oplossingen in de era van grote taalmodellen en complexe neurale netwerken.

Kortom, de auteurs concluderen dat voor moderne, niet-convexe deep learning modellen, Rewind-to-Delete (R2D) de voorkeur verdient boven Descend-to-Delete (D2D), omdat het zowel theoretisch gegarandeerd is als empirisch robuuster presteert.