Towards Certified Unlearning for Deep Neural Networks

1. Problemstellung

Im Bereich des maschinellen Lernens gewinnt das „Machine Unlearning" (das gezielte Vergessen von Daten) aufgrund von Datenschutzgesetzen wie der DSGVO (GDPR) und dem CCPA an Bedeutung. Benutzer haben das Recht, die Löschung ihrer Daten aus trainierten Modellen zu verlangen.

• Herausforderung: Der naive Ansatz, ein Modell komplett neu zu trainieren („Retraining from Scratch"), ist rechnerisch zu teuer und für große Deep Neural Networks (DNNs) unpraktikabel.
• Lücke: Bestehende Methoden für „Certified Unlearning" (zertifiziertes Vergessen), die theoretische Garantien bieten, funktionieren bisher hauptsächlich bei konvexen Modellen (z. B. lineare Regression). DNNs sind jedoch hochgradig nicht-konvex, was die Anwendung dieser theoretischen Garantien bisher unmöglich oder unzuverlässig machte. Bisherige Ansätze für DNNs basierten oft nur auf empirischen Annäherungen ohne strenge theoretische Zertifizierung.

2. Methodik

Die Autoren schlagen einen Rahmen vor, der Certified Unlearning auf nicht-konvexe DNNs überträgt, indem sie den Prozess in zwei Schritte unterteilen:

1. Schätzung des neu trainierten Modells: Berechnung einer Approximation des Modells, das erhalten würde, wenn man die Daten neu trainieren würde.
2. Hinzufügen von Rauschen: Hinzufügen von zufälligem Rauschen, das proportional zum Approximationsfehler ist, um die Zertifizierung (basierend auf Differential Privacy) zu gewährleisten.

Kern-Techniken der Methode:

• Anpassung des Newton-Updates: Anstatt eines einfachen Newton-Schritts (der Konvexität voraussetzt), nutzen die Autoren eine modifizierte Ein-Schritt-Newton-Aktualisierung. Um die Approximationsfehlergrenze auch für nicht-konvexe Funktionen zu sichern, führen sie zwei wesentliche Modifikationen ein:
  1. Lokale Konvexitäts-Approximation: Durch Hinzufügen eines $\ell_2$-Regularisierungsterms ($\lambda$) zur Hesse-Matrix wird sichergestellt, dass die Matrix invertierbar ist und die Nicht-Konvexität lokal beherrscht wird.
  2. Einschränkung der Parameternorm: Die Optimierung wird durch eine Einschränkung der Norm der Modellparameter ($\|w\|_2 \le C$) gesteuert (gelöst via Projected Gradient Descent). Dies verhindert, dass der Approximationsfehler unkontrolliert anwächst.
• Effiziente Inverse Hesse-Matrix: Da die direkte Berechnung der inversen Hesse-Matrix bei DNNs zu teuer ist ($O(p^3)$), nutzen die Autoren den LiSSA-Algorithmus (Linear-time Stochastic Second-Order Approximation). Dieser schätzt die inverse Hesse-Matrix iterativ über Hesse-Vektor-Produkte, was die Komplexität auf $O(sp^2)$ reduziert (unabhängig von der Datengröße $n$).
• Erweiterung auf reale Szenarien:
  • Nicht-Konvergenz: Die Methode wird so angepasst, dass sie auch funktioniert, wenn das Training vor Erreichen des globalen Optimums gestoppt wird (z. B. Early Stopping).
  • Sequentielles Unlearning: Der Ansatz wird auf Fälle erweitert, in denen Benutzer zu unterschiedlichen Zeitpunkten Löschungsanfragen stellen. Das Modell wird sequentiell aktualisiert, wobei die theoretischen Garantien erhalten bleiben.

3. Hauptbeiträge

• Theoretische Erweiterung: Erste strenge theoretische Garantien für Certified Unlearning bei nicht-konvexen DNNs, ohne auf unrealistische Konvexitätsannahmen zurückzugreifen.
• Effizienzsteigerung: Entwicklung einer effizienten Berechnungsmethode für die inverse Hesse-Matrix mittels LiSSA, die die Komplexität drastisch senkt, ohne die Zertifizierungsgrenzen zu verletzen.
• Robustheit: Erweiterung der Theorie auf nicht-konvergente Trainingszustände und sequentielle Löschungsanfragen, was die Anwendbarkeit in der Praxis erhöht.
• Fehlergrenzen: Herleitung einer oberen Schranke für den Approximationsfehler, die unabhängig von der Größe der zu löschenden Datenmenge ist.

4. Ergebnisse

Die Methode wurde auf drei realen Datensätzen (MNIST, CIFAR-10, SVHN) und drei verschiedenen DNN-Architekturen (MLP, All-CNN, ResNet18) evaluiert.

• Vergleich mit Baselines: Im Vergleich zu Methoden wie „Fine-Tuning", „Negative Gradient", „Fisher Forgetting" und „L-CODEC" sowie dem idealen „Retraining from Scratch":
  • Privatsphäre: Die vorgeschlagene Methode entfernt Informationen über die gelöschten Daten am effektivsten. Dies wurde durch Membership Inference Attacks (Angriffe, die prüfen, ob ein Datensatz im Training war) gemessen. Die Angriffsrate (Accuracy/AUC) war bei der zertifizierten Methode am niedrigsten.
  • Nützlichkeit (Utility): Die Leistung des Modells auf den verbleibenden Daten (Retained Set) und Testdaten bleibt nahe am Niveau des neu trainierten Modells, während die Leistung auf den gelöschten Daten (Unlearned Set) signifikant sinkt (wie gewünscht).
  • Effizienz: Die Methode ist über 10-mal schneller als ein komplettes Neutraining, bleibt aber deutlich genauer als andere schnelle Approximationsmethoden.
• Ablationsstudien: Die Experimente bestätigten, dass sowohl die lokale Konvexitäts-Approximation ($\lambda$) als auch die Norm-Einschränkung ($C$) entscheidend für die Reduzierung des Approximationsfehlers sind.

5. Bedeutung

Dieses Paper schließt eine kritische Lücke zwischen der Theorie des zertifizierten Vergessens und der Praxis des Deep Learning.

• Es beweist, dass strenge Datenschutzgarantien (im Sinne von Differential Privacy) auch für komplexe, nicht-konvexe neuronale Netze machbar sind.
• Es bietet einen praktischen Algorithmus, der nicht nur theoretisch fundiert, sondern auch rechnerisch effizient ist.
• Die Berücksichtigung von nicht-konvergentem Training und sequentiellen Anfragen macht die Methode für reale Produktionsumgebungen geeignet, in denen Benutzerdaten dynamisch hinzugefügt und entfernt werden.

Zusammenfassend stellt die Arbeit einen bedeutenden Schritt hin zu vertrauenswürdigen und regulatorisch konformen KI-Systemen dar, die das „Recht auf Vergessenwerden" effizient und mathematisch nachweisbar umsetzen können.