🤖 machine learning

Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds

Ce papier établit des bornes supérieures et inférieures fermées, serrées et transparentes pour la fonction de compromis du Descent de Gradient Stochastique Privé Différentiellement (DP-SGD) avec échantillonnage par mélange aléatoire, démontrant que cette méthode offre une interprétabilité supérieure et des compromis favorable entre vie privée et utilité par rapport à l'échantillonnage de Poisson, en particulier dans les régimes où le multiplicateur de bruit est suffisamment élevé.

Auteurs originaux : Marten van Dijk, Murat Bilgehan Ertan

Publié 2026-05-08

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Marten van Dijk, Murat Bilgehan Ertan

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'enseigner à un ordinateur à reconnaître des chats dans des photos sans jamais permettre à l'ordinateur de « voir » la photo d'une personne spécifique. C'est l'objectif de la Confidentialité Différentielle (CD). Pour ce faire, l'ordinateur apprend à partir de petits groupes de photos (appelés « mini-lots ») et ajoute un peu de « statique » ou de « bruit » au processus d'apprentissage, comme augmenter le volume d'une radio pour couvrir un chuchotement.

La grande question que cet article répond est : Combien de bruit devons-nous ajouter pour garantir la confidentialité lorsque nous mélangons les photos au hasard ?

Le Problème : Le « Mélange » vs Le « Lancer de Pièce »

Dans le monde réel, lorsque nous entraînons des modèles d'IA, nous prenons généralement une énorme liste de données, la mélangeons au hasard (comme mélanger un jeu de cartes), puis la coupons en morceaux de taille égale pour enseigner au modèle. Cela s'appelle le Mélange Aléatoire.

Cependant, depuis des années, les mathématiciens analysant la confidentialité ont principalement étudié une méthode différente appelée Échantillonnage de Poisson. Imaginez qu'au lieu de mélanger un jeu de cartes, vous lanciez une pièce pour chaque photo : « Pile, incluez-la ; Face, passez-la ». C'est mathématiquement plus facile à calculer, mais ce n'est pas ainsi que fonctionnent la plupart des systèmes réels.

Parce que les mathématiques utilisées pour analyser la méthode du « lancer de pièce » ne correspondent pas parfaitement à la méthode du « mélange », nous n'avions pas de manuel clair et précis pour déterminer à quel point la méthode du « mélange » était réellement privée. Nous devinions.

La Solution : Un Nouveau Manuel Clair

Les auteurs de cet article ont dérivé une formule fermée et serrée (une équation claire et exacte) pour mesurer la confidentialité de la méthode du « mélange ». Ils n'ont pas seulement deviné ; ils ont utilisé des outils statistiques avancés (comme le théorème de Berry-Esseen, qui est comme une règle ultra-précise pour mesurer à quel point un tas de données désordonné est proche d'une courbe en cloche parfaite) pour créer une borne supérieure et inférieure stricte sur la confidentialité.

Pensez-y ainsi :

Ancienne méthode : « Si vous mélangez les cartes, vous êtes probablement en sécurité, mais nous ne pouvons pas vous dire exactement à quel point vous êtes en sécurité sans exécuter un million de simulations. »
Nouvelle méthode : « Si vous mélangez les cartes et ajoutez cette quantité spécifique de bruit, voici la garantie mathématique exacte que personne ne peut tricher avec le système. »

Résultats Clés en Langage Simple

1. Le « Point Doux » pour le Bruit
L'article révèle qu'il existe une plage spécifique de bruit où les mathématiques fonctionnent à merveille.

Trop peu de bruit : Si le bruit est trop faible, le système est comme un chuchotement dans une pièce calme ; un attaquant peut facilement entendre le secret. L'article confirme qu'en dessous d'un certain seuil, il est impossible de garantir la confidentialité.
Juste ce qu'il faut : Si le bruit est au-dessus d'un certain niveau (spécifiquement, lorsque le multiplicateur de bruit $\sigma$ est approximativement supérieur à $\sqrt{3/\ln M}$ ), les auteurs fournissent une formule claire montrant que le système est extrêmement privé.
Le Résultat : Pour un seul tour d'entraînement (un « epoch »), si vous avez environ 11,4 millions de points de données et que vous les divisez en 1,14 million de petits groupes, l'ajout d'une quantité standard de bruit ( $\sigma=1$ ) vous offre une garantie de confidentialité très forte. Elle est si forte qu'un attaquant se contente essentiellement de deviner, comme s'il lançait une pièce pour décider si les données d'une personne spécifique ont été utilisées.

2. Le Piège du « Multi-Tour »
Que se passe-t-il si vous entraînez le modèle pendant de nombreux tours (epochs) ?

Le Danger Linéaire : Si vous additionnez simplement la perte de confidentialité de chaque tour, la garantie de confidentialité se dégrade très rapidement. C'est comme traverser un champ de mines ; si vous faites 100 pas, vous avez 100 fois plus de chances de marcher sur une mine. L'article montre qu'avec leur formule actuelle, si vous entraînez pendant trop de tours, la garantie de confidentialité s'effondre à moins d'avoir un ensemble de données imensément vaste.
L'Espoir Asymptotique : Les auteurs ont également examiné ce qui se passe dans le « long terme » (à mesure que l'ensemble de données devient infiniment grand). Ils ont constaté que la perte de confidentialité croît beaucoup plus lentement que nous ne le pensions — comme la racine carrée du nombre de tours, plutôt que le nombre de tours lui-même. C'est une amélioration énorme, suggérant que dans la limite, vous pouvez entraîner pendant plus de tours sans perdre toute votre confidentialité. Cependant, ils admettent ne pas avoir encore de formule simple pour calculer cela pour des ensembles de données réels et finis.

3. Pourquoi Cela Compte
Cet article comble le fossé entre la théorie et la pratique.

Apprentissage Fédéré : Cela est crucial pour des technologies comme l'Apprentissage Fédéré, où votre téléphone entraîne un modèle sur vos données sans envoyer celles-ci à un serveur central. Dans ces scénarios, les données sont souvent mélangées et traitées par lots.
Fin des Devinettes : Avant cela, les ingénieurs devaient utiliser des estimations conservatrices (en supposant le pire des cas) ou s'appuyer sur des simulations informatiques complexes difficiles à interpréter. Désormais, ils disposent d'une formule claire et transparente pour définir leurs paramètres.

La Conclusion

Les auteurs ont créé une « calculatrice de confidentialité » précise pour la méthode la plus courante avec laquelle nous entraînons réellement les modèles d'IA (le mélange aléatoire). Ils ont prouvé qu'avec la bonne quantité de bruit et un ensemble de données suffisamment vaste, nous pouvons atteindre des garanties de confidentialité très fortes en un seul passage d'entraînement. Bien que l'entraînement sur de nombreux tours reste un défi, ce travail fournit la première carte mathématique claire pour naviguer dans la confidentialité dans le monde réel, nous éloignant des estimations vagues vers des nombres exacts et dignes de confiance.

Résumé technique : Fonctions de compromis pour le DP-SGD avec sous-échantillonnage basé sur le mélange aléatoire

Énoncé du problème

La descente de gradient stochastique privée différentiellement (DP-SGD) est le mécanisme standard pour l'entraînement de modèles d'apprentissage profond sous contraintes de confidentialité. Bien que le cadre de la confidentialité différentielle $f$ ( $f$ -DP) fournisse la caractérisation la plus serrée possible des garanties de confidentialité via des fonctions de compromis entre les taux de faux positifs et de faux négatifs, les analyses existantes se sont principalement concentrées sur le sous-échantillonnage de Poisson (où les points de données sont inclus indépendamment dans les mini-lots avec une probabilité fixe).

Cependant, les implémentations pratiques de la DP-SGD et de l'optimisation stochastique utilisent généralement le mélange aléatoire, où l'ensemble de données est permuté une fois par époque et partitionné en mini-lots de taille fixe. Cette divergence entre l'algorithme analysé (Poisson) et l'algorithme déployé (mélange) a laissé les garanties de confidentialité des systèmes réels caractérisées de manière imprécise. Les travaux antérieurs sur la DP-SGD mélangée n'ont fourni que des bornes supérieures sur la fonction de compromis (bornes inférieures sur la perte de confidentialité) via des événements adverses explicites ou des évaluations numériques, sans expressions fermées et transparentes. De plus, des résultats d'impossibilité récents indiquent que pour de faibles multiplicateurs de bruit ( $\sigma \le 1/\sqrt{2 \ln M}$ ), la fonction de compromis est prouvée bornée loin de la diagonale idéale du hasard ( $1-a$ ), mais le comportement dans le régime de bruit élevé restait une question ouverte nécessitant une analyse serrée et sous forme fermée.

Méthodologie

Les auteurs dérivent une analyse serrée et sous forme fermée de la fonction de compromis pour la DP-SGD avec mélange aléatoire dans le cadre $f$ -DP. La méthodologie procède par les étapes suivantes :

Réduction à l'adversaire : Le problème est réduit à un problème de test d'hypothèse scalaire. Sous le modèle d'adversaire le pire (qui peut isoler la contribution d'un seul enregistrement différent), l'adversaire observe $M$ rounds. Sous l'hypothèse nulle ( $H_0$ ), toutes les observations sont un bruit pur $N(0, 1)$ . Sous l'hypothèse alternative ( $H_1$ ), exactement un round (choisi uniformément au hasard par la permutation de mélange) contient une observation décalée $N(1/\sigma, 1)$ , tandis que le reste demeure du bruit.
Test du rapport de vraisemblance : Par le lemme de Neyman-Pearson, le test optimal seuille le rapport de vraisemblance, ce qui se réduit au seuillage de la moyenne d'échantillon de variables log-normales $Y_j = \exp(X_j/\sigma - 1/(2\sigma^2))$ , où $X_j \sim N(0, 1)$ .
Analyse non asymptotique (Berry-Esseen) : Pour une seule époque, les auteurs appliquent le théorème de Berry-Esseen pour borner le taux de convergence de la moyenne d'échantillon de ces variables log-normales vers une distribution normale. Cela produit une borne inférieure concrète et non asymptotique sur la fonction de compromis $f(a)$ pour le régime $\sigma \ge \sqrt{3/\ln M}$ . La borne est exprimée comme $f(a) \ge 1 - a - \delta$ , où $\delta$ est une fonction explicite du multiplicateur de bruit $\sigma$ et du nombre de rounds $M$ .
Analyse asymptotique (Développement d'Edgeworth) : Pour améliorer les bornes de Berry-Esseen, limitées par un terme d'erreur $O(1/\sqrt{M})$ , les auteurs introduisent une technique de preuve basée sur un développement d'Edgeworth à deux termes. Cette généralisation du théorème central limite permet une estimation asymptotique plus fine de la distribution de la somme de variables log-normales. Cette approche établit le comportement asymptotique de la fonction de compromis lorsque $M \to \infty$ avec le nombre d'époques $E$ évoluant comme $E = c_M^2 M$ où $c_M \to 0$ .

Contributions clés

Borne inférieure sous forme fermée pour une seule époque : L'article fournit la première borne inférieure serrée et sous forme fermée pour la fonction de compromis de la DP-SGD mélangée dans le régime de bruit élevé ( $\sigma \ge \sqrt{3/\ln M}$ ). La borne est donnée par :
$f(a) \ge 1 - a - \delta$
où $\delta$ est explicitement défini en termes de $\sigma$ et $M$ (Théorème 4.1). Ce résultat est serré à des facteurs constants près dans le cadre de la preuve de Berry-Esseen.
Recommandations de paramètres concrètes : Les auteurs dérivent des paramètres spécifiques pour une confidentialité différentielle significative. Pour une seule époque ( $E=1$ ) avec $\sigma=1$ et $\delta=10^{-2}$ , ils montrent qu'un ensemble de données de taille $N \approx 1,14 \times 10^7$ partitionné en $M \approx 1,14 \times 10^6$ rounds suffit. Cela démontre qu'une confidentialité significative est réalisable dans des contextes d'apprentissage fédéré avec de grands ensembles de données et une seule époque.
Caractérisation asymptotique de la DP gaussienne : En utilisant des développements d'Edgeworth, l'article établit que pour un $\sigma$ fixe, lorsque $M \to \infty$ et $E = c_M^2 M$ avec $c_M \to 0$ , la fonction de compromis composée $E$ fois converge uniformément vers la diagonale du hasard ( $1-a$ ). Cela améliore la dépendance au nombre d'époques par rapport à la pénalité linéaire $O(E)$ suggérée par une composition naïve, vers une séparation asymptotique $O(\sqrt{E})$ (Corollaire 5.3).
Comparaison avec le sous-échantillonnage de Poisson : Les auteurs comparent leurs résultats asymptotiques avec l'asymptotique correspondante du sous-échantillonnage de Poisson. Ils constatent que dans la limite de faible bruit ( $\sigma \to 0$ ), le mélange aléatoire est asymptotiquement un facteur $\sqrt{2}$ plus proche de la diagonale idéale du hasard que le sous-échantillonnage de Poisson, tandis que les deux régimes deviennent équivalents dans la limite de bruit élevé ( $\sigma \to \infty$ ).

Résultats

Validité du régime : L'analyse est valide pour $\sigma \ge \sqrt{3/\ln M}$ . Ce régime est complémentaire au résultat d'impossibilité d'Ertan et van Dijk [12], qui montre que pour $\sigma < 1/\sqrt{2 \ln M}$ , la fonction de compromis est bornée loin de $1-a$ . Ensemble, ces résultats cartographient le paysage de confidentialité de la DP-SGD mélangée.
Bornes de composition :
- Non asymptotique : L'itération de la borne d'une seule époque donne $f^{\otimes E}(a) \ge (1-\delta)^E - a$ , impliquant une dépendance linéaire en $E$ pour la perte de confidentialité.
- Asymptotique : L'analyse basée sur Edgeworth suggère une dépendance plus serrée, où la séparation par rapport à la diagonale évolue comme $O(\mu \sqrt{E})$ plutôt que $O(\mu E)$ , à condition que $E$ évolue de manière sous-linéaire avec $M$ .
Implications pratiques : L'article identifie le régime d'une seule époque comme le « point idéal pratique » pour la DP-SGD mélangée. Dans les scénarios d'apprentissage fédéré où les clients participent à peu d'époques, des garanties de confidentialité significatives ( $\delta \approx 0,01$ ) sont réalisables avec des tailles d'ensembles de données réalistes. À l'inverse, l'article met en évidence une « explosion multi-époque » où l'augmentation de $E$ sous la borne de composition linéaire rend rapidement la taille d'ensemble de données requise $N$ impraticable (par exemple, nécessitant $N \sim 10^{11}$ pour $E=100$ ).

Importance et revendications

L'article revendique fournir une analyse serrée et sous forme fermée qui résout le décalage entre les algorithmes analysés dans la littérature (Poisson) et ceux déployés en pratique (mélange aléatoire). En dérivant des bornes transparentes et interprétables, les auteurs permettent aux praticiens de lire directement les exigences en paramètres sans dépendre d'outils numériques opaques.

L'importance de ce travail réside dans :

Le pont entre théorie et pratique : Valider que le mélange aléatoire, standard dans les frameworks d'apprentissage automatique, admet une analyse de confidentialité rigoureuse qui est souvent plus favorable que le sous-échantillonnage de Poisson dans les régimes de faible bruit.
La définition du paysage de confidentialité : Compléter les résultats d'impossibilité existants pour définir les seuils de bruit précis requis pour une confidentialité significative dans la DP-SGD mélangée.
L'orientation de la sélection de paramètres : Offrir des formules concrètes pour sélectionner $M$ , $N$ et $\sigma$ afin d'atteindre des budgets de confidentialité spécifiques, particulièrement pertinent pour les applications d'apprentissage fédéré.

Les auteurs restent modestes concernant les travaux futurs, notant que si les résultats asymptotiques suggèrent une dépendance améliorée en $\sqrt{E}$ pour plusieurs époques, la dérivation d'une preuve concrète et sous forme fermée de cette dépendance (par opposition à la limite asymptotique) reste un problème ouvert. De plus, rendre explicites les suites $\delta_M$ et $\gamma_M$ dans le développement d'Edgeworth pour obtenir une borne multi-époque concrète est identifié comme une direction pour la recherche future.