Technische Samenvatting: Audit van Unlearning-algoritmen

Probleemstelling

Machine unlearning beoogt de invloed van specifieke trainingsvoorbeelden uit een getraind model te verwijderen, idealiter resulterend in een model dat ononderscheidbaar is van een model dat vanaf nul is hertraind op de resterende data. Hoewel exacte unlearning sterke garanties biedt, is dit voor diepe netwerken vaak computationeel onhaalbaar. Bijgevolg zijn er benaderde unlearning-methoden ontstaan, variërend van heuristische benaderingen (bijv. gradiëntascensie op de forget set, Hessian-gebaseerde scrubbing) tot gecertificeerde methoden die $(\varepsilon, \delta)$-ononderscheidbaarheidsgaranties bieden.

Een kritieke openstaande uitdaging is de empirische evaluatie van deze claims. Bestaande theoretische grenzen vertrouwen vaak op aannames (bijv. convexiteit) die in de praktijk mogelijk niet standhouden, en er is een gebrek aan praktische instrumenten om te verifiëren of een geclaimde unlearning-garantie daadwerkelijk standhoudt. Dit artikel adresseert de behoefte aan een auditor die met empirisch bewijs unlearning-garanties test, specifiek gericht op het verwerpen van de hypothese dat de unlearning-parameter $\varepsilon$ onder een bepaalde ondergrens ligt ($\varepsilon < \varepsilon_{LB}$).

Methodologie

Dreigingsmodel

De auteurs hanteren een sterk black-box-adversary-model. De adversary heeft kennis van:

1. Het leeralgoritme ($A$) en het unlearning-algoritme ($U$).
2. De data-loading shuffler (willekeurige permutatie $\pi$).
3. De initiële modelgewichten ($x_0$) aan het begin van de training.
   De adversary ziet niet de specifieke willekeurige realisaties (bijv. gradiëntruis) tijdens de training of unlearning, noch heeft hij toegang tot de interne staat van de algoritmen. Dit model versterkt de adversary ten opzichte van standaarddefinities, maar is consistent met de garanties van gecertificeerde algoritmen zoals Model Clipping en Rewind-to-Delete (R2D).

Het Auditor-framework

Het voorgestelde auditor is een hypothese-toetsingsframework ontworpen om een data-afhankelijke ondergrens $\varepsilon_{LB}$ te berekenen op de ware unlearning-parameter $\varepsilon$.

1. Setup: De trainingsdataset wordt verdeeld in een retain set ($D_r$) en een forget set ($D_f$). $D_f$ wordt verder onderverdeeld in $m$ kandidaat-batches.
2. Sign Vectoren: De auditor samplet een gebalanceerde sign vector $S \in \{\pm 1\}^m$, waarbij $+1$ aangeeft dat een batch is opgenomen in de trainingsset (en dus onderhevig is aan unlearning), en $-1$ aangeeft dat deze is uitgesloten.
3. Executie: Voor elke run $\ell$:
   • Een trainingsset $D(S^{(\ell)})$ wordt geconstrueerd op basis van de sign vector.
   • Het model wordt getraind en vervolgens ontleerd om $f_u^{(\ell)}$ te produceren.
   • De auditor probeert de sign vector $S^{(\ell)}$ te voorspellen vanuit $f_u^{(\ell)}$.
4. Scoring: De auditor berekent een overlap score $V^{(\ell)}$, waarbij het aantal correcte non-zero voorspellingen wordt geteld (waar de voorspelde sign overeenkomt met de ware sign).
5. Reductie naar LDP: De audit wordt gereduceerd tot een Local Differential Privacy (LDP) probleem. Als het unlearning-algoritme $(\varepsilon, 0)$-gecertificeerd is, kan worden aangetoond dat de auditor-mechanisme $(2\varepsilon, 0)$-LDP is.
6. Hypothese-toetsing: Gebruikmakend van de distributie van overlap scores over meerdere onafhankelijke runs, berekent de auditor een ondergrens $\varepsilon_{LB}$. Als de geobserveerde overlap significant groter is dan willekeurig gokken, wordt de nulhypothese ($H_0: \varepsilon \le \varepsilon_{LB}$) verworpen, wat duidt op zwakke unlearning.

Auditor-instantiaties

Twee specifieke instantiaties van de auditor-mechanisme $M$ worden voorgesteld:

• Instantiatie I (Batchwise): Geschikt wanneer $m$ groot is. Het past Gaussian-distributies toe op logit-scores voor elke batch onafhankelijk (geïnspireerd door LiRA) om inclusie/exclusie te voorspellen.
• Instantiatie II (Joint Sign-Vector): Geschikt wanneer $m$ klein is (telbaar). Het behandelt de gehele sign vector als een hypothese, legt cross-batch correlaties vast, en selecteert de vector met de hoogste cumulatieve waarschijnlijkheid.

Belangrijkste Bijdragen

1. Praktisch Auditor-ontwerp: Het artikel introduceert een meta-algoritme dat differential privacy auditing-technieken uitbreidt naar de unlearning-setting, specifiek afgestemd op subset-niveau forget sets in plaats van enkelvoudige single-point buren.
2. Theoretische Grenzen: De auteurs leiden nieuwe theoretische grenzen af (Theorem 4.2) die de empirische overlap scores omzetten in een geldige ondergrens op $\varepsilon$ met een gecontroleerde Type I-fout, specifiek voor het geval $\delta=0$.
3. Empirische Falsificatie: Het framework biedt een instrument om unlearning-claims empirisch te falsificeren. Het onderscheidt algoritmen met rigoureuze theoretische garanties van algoritmen die slechts heuristisch zijn.

Resultaten

De auditor werd geëvalueerd op CIFAR-100 (met behulp van een TinyNet-model) en de Shakespeare tekstdataset (met behulp van een LSTM). De experimenten bestreken zowel gecertificeerde als ongecertificeerde unlearning-algoritmen.

Scherpe Separatie tussen Gecertificeerde en Ongecertificeerde Methoden

• Gecertificeerde Algoritmen: Methoden met formele garanties, zoals Model Clipping (Koloskova et al., 2025) en Rewind-to-Delete (R2D), leverden consistent zeer kleine $\varepsilon_{LB}$-waarden op (vaak nabij 0). Dit geeft aan dat het empirische bewijs hun theoretische garanties niet falsifieert.
• Ongecertificeerde/Heuristische Algoritmen: Methoden zonder formele garanties, waaronder Hessian-gebaseerde unlearning, Interleaved Ascent-Descent (IDA), Ascent op de Forget Set, en Pure Fine-tuning op de Retain Set, vertoonden grote $\varepsilon_{LB}$-waarden, die vaak de 50–60 overschreden.
  • Opvallend genoeg leverde de Hessian-gebaseerde methode (Zhang et al., 2025), die certificering claimt onder convexiteit, een $\varepsilon_{LB}$ van 142.5 op CIFAR-100 (een niet-convexe regime), wat aantoont dat de auditor succesvol de mislukking van de precondition van de methode heeft gesignaleerd.
  • Pure fine-tuning en forget-set ascent vertoonden vergelijkbaar hoge grenzen, wat duidt op slechte unlearning-prestaties.

Impact van Data-splits

De studie observeerde dat uniforme splits (waarbij forget en retain sets dezelfde feature support delen) over het algemeen hogere $\varepsilon_{LB}$-waarden resulteerden vergeleken met adversarial splits (disjuncte labelklassen). Dit suggereert dat residuele memorisatie en semantische nabijheid in uniforme splits het effectief bereiken van unlearning moeilijker maken.

Convex vs. Non-Convex Regimes

In experimenten op convexe losses (cubic en logistic) was het gat tussen de gecertificeerde $\varepsilon$ en de empirische $\varepsilon_{LB}$ veel kleiner dan in de niet-convexe deep learning setting. Dit bevestigt dat de auditor strakker is in analytisch hanteerbare settings, en dat de grote grenzen geobserveerd in deep learning waarschijnlijk te wijten zijn aan echte unlearning-fouten in heuristische methoden in plaats van enkel auditor-slack.

Betekenis en Claims

Het artikel claimt het eerste praktische instrument te bieden voor het empirisch falsificeren van unlearning-garanties via een hypothese-toetsingsframework. De primaire betekenis ligt in de diagnostische waarde van de auditor:

• Het onthult dat heuristische methoden, die vaak in de praktijk worden gebruikt voor efficiëntie, frequent falen in het verwijderen van data-invloed, zoals blijkt uit hoge $\varepsilon_{LB}$-waarden.
• Het valideert dat gecertificeerde methoden (wanneer hun aannames kloppen) hun garanties handhaven, zelfs onder een sterke adversary.
• Het benadrukt de fragiliteit van certificeringsclaims die rusten op aannames (zoals convexiteit) die mogelijk niet standhouden in real-world deep learning scenario's.

De auteurs concluderen dat hoewel hun analyse momenteel beperkt is tot $\delta=0$, de voorgestelde auditor een rigoureuze standaard biedt voor het evalueren van de effectiviteit van machine unlearning-algoritmen, waarbij zij onderscheid maken tussen die met echte garanties en die die slechts lijken te vergeten.