Descend or Rewind? Stochastic Gradient Descent Unlearning

Cet article établit des garanties théoriques d'oubli certifié pour les versions stochastiques des algorithmes D2D et R2D sur des fonctions non convexes, en démontrant que D2D est optimal pour les fonctions fortement convexes tandis que R2D convient mieux aux cas convexes et non convexes.

L'essentiel

Imaginez que vous avez un grand chef cuisinier (l'intelligence artificielle) qui a appris à cuisiner en goûtant des milliers de plats différents (les données d'entraînement). Maintenant, un client demande : « Hé, j'ai oublié ce plat que j'ai apporté, pouvez-vous l'effacer de votre mémoire pour que vous ne sachiez plus jamais le cuisiner ? »

C'est le défi du « Machine Unlearning » (l'oubli machine).

Le problème ? Si le chef oublie ce plat, la méthode la plus simple serait de tout jeter, de recommencer à zéro et d'apprendre à nouveau avec tous les autres plats. Mais c'est trop long et ça coûte trop cher (en énergie et en temps).

Les chercheurs de cet article, Siqiao Mu et Diego Klabjan, comparent deux méthodes pour faire oublier ce plat spécifique sans tout recommencer. Ils appellent ces méthodes « Descendre » (Descent) et « Rembobiner » (Rewind).

Voici l'explication simple de leur découverte :

1. Les deux stratégies pour oublier

Imaginez que le chef est en train de descendre une montagne (l'apprentissage) pour trouver le point le plus bas (le meilleur modèle).

• La méthode « Descendre » (D2D) :
  Le chef est arrivé tout en bas de la montagne (le modèle final). Le client dit : « Oublie ce plat ! ». Le chef reste où il est, mais essaie de se « décoller » légèrement du sol pour ne plus penser à ce plat, puis continue de descendre un tout petit peu plus bas.

  • Le problème : Si la montagne est plate ou pleine de creux (ce qui arrive souvent avec les réseaux de neurones complexes), le chef risque de rester coincé dans un petit trou local. Il pense avoir oublié, mais en réalité, il est juste bloqué et n'a pas vraiment changé.

• La méthode « Rembobiner » (R2D) :
  Le chef se souvient qu'il avait pris une photo de lui-même il y a 10 minutes, alors qu'il était encore à mi-pente de la montagne. Au lieu de rester en bas, il rembobine le temps pour revenir à ce moment précis. Ensuite, il redescend la montagne, mais cette fois en ignorant le plat à oublier.

  • L'avantage : En revenant en arrière, le chef a plus d'espace pour se réorienter. Il évite de rester coincé dans les petits trous et s'assure de vraiment changer de trajectoire pour ne plus penser au plat interdit.

2. La grande découverte de l'article

Les chercheurs ont prouvé mathématiquement (avec des formules complexes, mais le résultat est clair) :

• Si la montagne est parfaitement lisse et simple (fonctions « fortement convexes »), la méthode « Descendre » fonctionne très bien et est très précise.
• MAIS, pour les montagnes réelles, complexes et accidentées (les réseaux de neurones modernes, ou « fonctions non convexes »), la méthode « Rembobiner » est bien meilleure. Elle garantit que le chef a vraiment oublié le plat, sans rester coincé.

3. L'analogie du « Couplage » (La magie des jumeaux)

Pour prouver que leur méthode fonctionne, les chercheurs utilisent une astuce mathématique appelée « couplage ». Imaginez deux jumeaux identiques :

1. Le jumeau A apprend avec le plat interdit.
2. Le jumeau B apprend sans le plat interdit.

Normalement, ils prennent des chemins différents à chaque pas à cause du hasard (le bruit de l'apprentissage). Les chercheurs ont trouvé un moyen de les forcer à faire exactement les mêmes pas (les mêmes choix de données) sauf pour le moment où le plat interdit est présent.

Grâce à cette astuce, ils peuvent mesurer exactement la différence entre les deux jumeaux. Ils ajoutent ensuite un peu de « brouillard » (du bruit mathématique) à la fin pour s'assurer que personne ne peut deviner quel jumeau a mangé quel plat. C'est comme ajouter un peu de flou artistique pour protéger la vie privée.

En résumé

• Le problème : On veut effacer des données d'une IA sans tout recommencer à zéro.
• L'ancienne idée (Descendre) : On essaie de corriger le modèle final. Ça marche parfois, mais souvent, l'IA reste bloquée et n'oublie pas vraiment.
• La nouvelle idée (Rembobiner) : On revient en arrière à un moment précis du passé, puis on réapprend sans la donnée interdite.
• Le verdict : Pour les IA modernes (complexes), Rembobiner est la méthode gagnante. Elle est plus sûre, plus fiable et garantit que l'IA a vraiment « oublié » ce qu'on lui a demandé d'oublier.

C'est comme si, au lieu d'essayer de changer d'avis à la fin d'une longue conversation, vous décidiez de revenir au début de la discussion pour la reprendre en excluant le sujet gênant. Le résultat est beaucoup plus naturel et efficace !

Résumé technique

1. Problématique

L'oubli machine (Machine Unlearning) vise à supprimer l'influence de données spécifiques d'un modèle entraîné sans avoir à le réentraîner intégralement à partir de zéro, ce qui serait trop coûteux en calcul, surtout pour les grands modèles (LLMs, réseaux de neurones profonds).

Le défi principal réside dans la fourniture de garanties certifiées d'oubli, généralement définies par le cadre de la différence de confidentialité $(\varepsilon, \delta)$. Cela signifie que la distribution du modèle après l'oubli doit être statistiquement indiscernable de celle obtenue par un réentraînement complet sur le jeu de données restant.

Les méthodes existantes souffrent de limitations majeures :

• Les méthodes d'ordre supérieur (utilisant la Hessienne) sont trop coûteuses.
• Les méthodes d'ordre inférieur basées sur le gradient complet (Full-batch) ne sont pas applicables aux grands modèles.
• Les approches basées sur le Descente de Gradient Stochastique (SGD) existantes manquent souvent de garanties théoriques solides pour les fonctions non convexes, ou ne s'appliquent qu'à des cas convexes.

Deux approches de premier ordre existent déjà : D2D (Descent-to-Delete) et R2D (Rewind-to-Delete). Bien que la version stochastique de D2D soit souvent utilisée comme référence ("finetuning"), elle manque de fondement théorique pour les fonctions non convexes. L'article se demande si les versions stochastiques de ces deux algorithmes peuvent offrir des garanties certifiées.

2. Méthodologie

Les auteurs analysent et prouvent les garanties d'oubli pour les versions SGD de deux algorithmes :

• SGD-D2D (Descent-to-Delete) : L'algorithme d'oubli commence à partir du modèle final entraîné ($\theta_T$) et effectue $K$ étapes de descente sur le jeu de données retenu ($D'$).
• SGD-R2D (Rewind-to-Delete) : L'algorithme d'oubli "rembobine" le modèle à un checkpoint antérieur ($\theta_{T-K}$) avant d'effectuer $K$ étapes de descente sur $D'$.

Approche théorique principale :
Au lieu de chercher des bornes de sensibilité déterministes (difficiles à obtenir en SGD), les auteurs utilisent une analyse par couplage (coupling argument) :

1. Couplage des trajectoires : Ils couplent le processus aléatoire de l'entraînement (sur $D$) et celui de l'oubli/réentraînement (sur $D'$) en synchronisant l'échantillonnage des mini-batchs autant que possible.
2. Analyse des systèmes perturbés : Ils modélisent l'entraînement sur $D$ comme un SGD biaisé (ou perturbé) sur la fonction de perte de $D'$.
3. Propriétés de contraction : Ils exploitent les propriétés de contraction des systèmes de gradient :
   • Convexité forte : Contraction (les trajectoires convergent l'une vers l'autre).
   • Convexité : Semi-contractante (divergence linéaire).
   • Non-convexité : Expansive (divergence exponentielle).
4. Bornes de sensibilité : En utilisant le couplage, ils dérivent une borne de sensibilité sur la distance entre les trajectoires d'oubli et de réentraînement en espérance ($L_1$ ou $L_2$).
5. Injection de bruit : Une fois la borne de sensibilité en espérance ($\Sigma$) établie, ils ajoutent un bruit gaussien à la fin du processus. En combinant cette borne avec l'inégalité de Markov, ils obtiennent une borne de queue (tail bound) garantissant l'indiscernabilité $(\varepsilon, 2\delta)$.

3. Contributions Clés

• Preuves de certitude pour SGD-R2D : Démonstration de garanties d'oubli certifiées $(\varepsilon, \delta)$ pour SGD-R2D (avec et sans projection) sur des fonctions fortement convexes, convexes et non convexes.
• Preuves de certitude pour SGD-D2D : Extension des garanties à SGD-D2D pour les fonctions fortement convexes, en utilisant une nouvelle approche de preuve qui contourne les hypothèses restrictives des travaux précédents (comme la Lipschitzianité globale).
• Analyse comparative théorique :
  • Pour les fonctions fortement convexes, D2D offre des bornes probabilistes plus serrées (meilleure dépendance en $\delta$).
  • Pour les fonctions convexes et non convexes, R2D est supérieur car il évite l'accumulation de perturbations en repartant d'un point plus proche de la solution optimale de $D'$.
• Efficacité computationnelle : Ils montrent que pour les fonctions fortement convexes, le nombre d'itérations d'oubli $K$ nécessaire pour atteindre une certaine précision peut converger vers une constante lorsque le nombre d'itérations d'entraînement $T$ augmente, offrant un avantage computationnel potentiellement infini par rapport au réentraînement.

4. Résultats Expérimentaux

Les auteurs ont évalué les algorithmes sur des jeux de données réels (eICU pour des données tabulaires, Lacuna-100/VGGFace2 pour la classification d'images) avec des modèles MLP et ResNet-18.

• Performance d'oubli (Distance $L_2$) :
  • R2D déplace le modèle de manière fiable vers la position du modèle réentraîné, réduisant la distance $L_2$ avec ce dernier.
  • D2D montre des résultats mitigés sur les fonctions non convexes : le modèle peut s'écarter à la fois du modèle original et du modèle réentraîné, ou stagner dans un point stationnaire, indiquant un échec partiel de l'oubli.
• Performance du modèle :
  • R2D réduit la performance du modèle sur les données oubliées (ce qui est souhaitable) tout en maintenant la performance sur les données retenues.
  • D2D peut parfois améliorer la performance sur toutes les données (y compris les données oubliées), ce qui suggère que le modèle n'a pas vraiment "oublié" mais a simplement trouvé une nouvelle direction de descente, rendant l'oubli inefficace ou trompeur.
• Attaques par inférence d'appartenance (MIA) :
  • R2D réduit plus efficacement le succès des attaques MIA (AUC plus faible), indiquant une meilleure protection de la vie privée.
  • D2D peut parfois laisser des traces plus visibles ou être moins robuste face aux attaques sophistiquées (MIA-U).

5. Signification et Impact

Cet article est une avancée significative pour le domaine de l'oubli machine certifié :

• Théorie : Il comble le fossé théorique entre les méthodes d'oubli certifiées et la pratique réelle du Deep Learning (SGD, non-convexité). Il démontre que le "rembobinage" (Rewinding) est théoriquement et pratiquement supérieur à la simple "descente" (Descending) pour les problèmes non convexes.
• Pratique : Les algorithmes proposés sont des boîtes noires ("black-box") faciles à implémenter. Ils ne nécessitent pas de modifications pendant l'entraînement, mais seulement l'ajout de bruit à la fin du processus d'oubli.
• Réglementation : Ces résultats renforcent la capacité des organisations à respecter les réglementations comme le RGPD (droit à l'oubli) sans sacrifier la performance des modèles ou la sécurité des données, en offrant des garanties mathématiques solides plutôt que des métriques empiriques peu fiables.

En conclusion, l'article établit que SGD-R2D est la méthode de choix pour l'oubli certifié dans les scénarios modernes de Deep Learning non convexe, tandis que SGD-D2D reste pertinent mais limité aux problèmes fortement convexes où des bornes plus serrées sont requises.