📊 statistics

Edgeworth Accountant: An Analytical Approach to Differential Privacy Composition

Cet article présente l'Edgeworth Accountant, une méthode analytique basée sur l'expansion d'Edgeworth et le cadre de la $f$ -differential privacy qui permet de calculer efficacement et avec précision les garanties de confidentialité non asymptotiques pour la composition de mécanismes d'apprentissage automatique privé, sans que le coût computationnel n'augmente significativement avec le nombre de mécanismes.

Auteurs originaux : Hua Wang, Sheng Gao, Huanyu Zhang, Milan Shen, Weijie J. Su, Jiayuan Wu

Publié 2026-03-17

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Hua Wang, Sheng Gao, Huanyu Zhang, Milan Shen, Weijie J. Su, Jiayuan Wu

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 êtes un chef cuisinier très soucieux de la vie privée de vos clients. Vous préparez un grand banquet (c'est votre algorithme d'apprentissage automatique) en utilisant des ingrédients très sensibles (les données personnelles).

Pour protéger vos clients, vous utilisez une technique magique appelée Différentielle Privée (DP). Cette magie fonctionne comme un voile : elle ajoute un peu de "bruit" (du brouillard) à chaque étape de la cuisine pour que personne ne puisse dire exactement quel ingrédient précis a été utilisé, tout en gardant le goût global du plat (la qualité des données).

Le problème, c'est que cuisiner un grand banquet ne se fait pas en une seule étape. C'est une longue série de milliers de petites étapes (des itérations). À chaque fois que vous ajoutez un peu de bruit, vous utilisez un peu de votre "magie de protection".

Le Problème : Le Compteur de Magie

La question cruciale est : Combien de magie reste-t-il après 10 000 étapes ?
Si vous utilisez trop de magie, le voile devient trop épais et le plat devient immangeable (les données deviennent inutiles). Si vous ne l'utilisez pas assez, le voile est trop fin et les clients sont en danger (fuite de données).

Les méthodes actuelles pour calculer cette "consommation de magie" ont deux gros défauts :

Elles sont trop conservatrices : Elles disent "Attention, il ne reste plus rien !" alors qu'il en reste encore un peu. C'est comme si vous jetiez un plat délicieux parce que vous aviez peur qu'il soit gâché.
Elles sont trop lentes : Pour calculer la magie restante après 10 000 étapes, les vieux ordinateurs doivent faire des calculs interminables, comme essayer de compter chaque grain de sable d'une plage à la main.

La Solution : Le "Comptable Edgeworth"

C'est là que l'article que vous avez lu entre en jeu. Les auteurs proposent une nouvelle méthode appelée Edgeworth Accountant (le Comptable Edgeworth).

Voici comment cela fonctionne, avec des analogies simples :

1. Au lieu de compter grain par grain, on regarde la forme du nuage

Les anciennes méthodes essayaient de suivre chaque grain de bruit individuellement. C'est lent et compliqué.
Le Comptable Edgeworth, lui, utilise une astuce mathématique appelée l'expansion d'Edgeworth.

L'analogie : Imaginez que vous lancez des milliers de pièces de monnaie. Au début, le résultat est chaotique. Mais si vous lancez assez de pièces, la forme des résultats ressemble à une cloche parfaite (une courbe en forme de cloche).
Les méthodes classiques (comme le "Central Limit Theorem" ou CLT) disent : "Bon, on va juste dessiner une cloche parfaite et on espère que ça colle." C'est rapide, mais pas très précis si vous n'avez pas encore lancé assez de pièces.
Le Comptable Edgeworth dit : "Attendez, la cloche n'est pas tout à fait parfaite. Elle a un petit creux ici, un petit renflement là." Il ajoute des corrections fines à la forme de la cloche pour qu'elle corresponde exactement à la réalité, même si vous n'avez pas encore lancé des milliards de pièces.

2. La vitesse de la lumière

Le plus impressionnant avec ce nouveau comptable, c'est sa vitesse.

Les anciennes méthodes (FFT) : C'est comme essayer de traverser une forêt en comptant chaque arbre un par un. Plus il y a d'arbres (d'étapes de calcul), plus ça prend du temps.
Le Comptable Edgeworth : C'est comme avoir un hélicoptère. Peu importe si vous avez 100 arbres ou 100 000, il vous dit la réponse en une fraction de seconde. Il calcule la "forme globale" du bruit sans avoir besoin de tout détailler.

3. Deux outils en un

Les auteurs ont créé deux versions de ce comptable pour s'adapter à tous les besoins :

AEA (Le Prévisionniste Rapide) : Il donne une estimation très précise et rapide de la magie restante. C'est parfait pour les chefs qui veulent ajuster leur recette en temps réel pendant la cuisson.
EEAI (Le Gardien de Sécurité) : Il donne une fourchette de sécurité (un minimum et un maximum) garantie. C'est comme un garde du corps qui vous dit : "Vous avez au moins autant de magie que ça, et au plus autant que ça." C'est infaillible et ne prend pas de temps de calcul, même pour des milliards d'étapes.

Pourquoi c'est important pour vous ?

Aujourd'hui, les intelligences artificielles (comme celles qui reconnaissent votre visage ou traduisent des textes) apprennent sur des données sensibles.

Avec les anciennes méthodes, les entreprises devaient soit trop protéger les données (rendant l'IA moins intelligente), soit calculer si lentement qu'elles ne pouvaient pas vérifier la sécurité.
Avec le Comptable Edgeworth, on peut entraîner des IA très puissantes tout en sachant exactement, en quelques millisecondes, que la vie privée des utilisateurs est parfaitement protégée, sans gaspiller de ressources informatiques.

En résumé : Ce papier propose un nouveau "compteur de magie" pour les algorithmes secrets. Il est plus rapide (il ne compte pas grain par grain), plus précis (il corrige les imperfections de la forme de cloche) et plus fiable que tout ce qui existait avant, permettant de construire des intelligences artificielles plus intelligentes et plus respectueuses de la vie privée.

1. Problématique

L'analyse de données préservant la vie privée repose souvent sur des algorithmes complexes composés de multiples blocs de construction privés (par exemple, le NoisySGD pour l'apprentissage profond ou l'analyse fédérée). Le défi central réside dans le calcul efficace et précis de la perte de privacy globale résultant de la composition de ces mécanismes.

Les méthodes existantes présentent des limitations majeures :

Compteur des moments (Moments Accountant) et DP de Rényi (RDP) : Bien que computaionnellement efficaces, ils fournissent des bornes supérieures souvent trop lâches (non serrées) lors de la conversion vers les garanties $(\varepsilon, \delta)$ -DP, car la conversion de la DP de Rényi vers la DP standard est imparfaite.
Méthodes numériques (FFT) : L'utilisation de la transformée de Fourier rapide (FFT) pour composer les distributions de perte de privacy offre des bornes précises et non asymptotiques. Cependant, leur complexité temporelle augmente rapidement avec le nombre de compositions $m$ (souvent $O(m^{2.5})$ ou $O(\sqrt{m})$ ), les rendant coûteuses pour les grands nombres d'itérations typiques du Deep Learning.
Approximation par le Théorème Central Limite (CLT) : Les approches basées sur la DP Gaussienne (GDP) utilisent le CLT pour approximer la distribution. Bien que rapides ( $O(1)$ ou $O(m)$ ), elles ne fournissent pas de garanties non asymptotiques (à échantillon fini) et peuvent être imprécises pour un nombre modéré de compositions.

L'objectif de cet article est de développer une méthode qui combine l'efficacité computationnelle des méthodes analytiques avec la précision et les garanties non asymptotiques des méthodes numériques, tout en évitant les coûts computationnels élevés de ces dernières.

2. Méthodologie

Les auteurs proposent le Edgeworth Accountant, une approche analytique basée sur le cadre de la f-DP (f-Differential Privacy) et l'expansion d'Edgeworth.

A. Cadre théorique : f-DP et PLLRs

Le travail s'appuie sur la f-DP, qui caractérise la privacy via une fonction de compromis (trade-off function) entre les erreurs de type I et II d'un test d'hypothèse.
Les auteurs introduisent les Rapports de Vraisemblance de Perte de Privacy (PLLRs - Privacy-Loss Log-likelihood Ratios). Pour une composition de $m$ mécanismes, la perte de privacy globale est liée à la somme de variables aléatoires indépendantes (les PLLRs).
La fonction de compromis exacte $(\varepsilon, \delta)$ peut être exprimée en fonction des fonctions de répartition (CDF) de la somme de ces PLLRs.

B. Approximation par l'Expansion d'Edgeworth

Au lieu d'utiliser le Théorème Central Limite (CLT) simple (qui correspond à une approximation d'ordre 0), les auteurs appliquent l'expansion d'Edgeworth.

C'est une correction d'ordre supérieur du CLT qui intègre les cumulants d'ordre supérieur (skewness, kurtosis, etc.) pour améliorer le taux de convergence de l'approximation de la distribution.
Cela permet d'obtenir une approximation de la distribution de la somme des PLLRs avec une erreur de l'ordre de $O(m^{-(p+1)/2})$ pour une expansion d'ordre $p$ .

C. Deux variantes de l'algorithme

Compteur Edgeworth Approximatif (AEA - Approximate Edgeworth Accountant) :
- Fournit une estimation asymptotiquement cohérente de la perte de privacy sous forme d'une expression fermée reliant $\varepsilon$ et $\delta$ .
- Plus précis que les méthodes basées sur le CLT (GDP) et plus rapide que les méthodes FFT.
Intervalle de Compteur Edgeworth Exact (EEAI - Exact Edgeworth Accountant Interval) :
- Fournit des bornes supérieures et inférieures non asymptotiques (à échantillon fini) pour la vraie perte de privacy.
- Utilise des bornes d'erreur explicites (de type Berry-Esseen) pour l'expansion d'Edgeworth afin de garantir que la vraie valeur se situe dans l'intervalle calculé.
- Gère spécifiquement les mécanismes avec échantillonnage (sub-sampling) en utilisant une famille de séquences de PLLRs et le lemme de la double conjugaison.

3. Contributions Clés

Complexité temporelle optimisée :
- Pour $m$ mécanismes identiques : Complexité $O(1)$ (temps constant).
- Pour $m$ mécanismes hétérogènes : Complexité $O(m)$ (linéaire).
- Cela contraste fortement avec les méthodes FFT qui sont polynomiales en $m$ .
Précision et Garanties Non Asymptotiques :
- Première méthode dans la littérature DP à fournir des bornes d'erreur à échantillon fini explicites pour l'expansion d'Edgeworth appliquée aux PLLRs.
- Les bornes sont serrées (tight) et évitent les pertes d'information inhérentes à la conversion RDP $\to$ $(\varepsilon, \delta)$ .
Stabilité Numérique :
- Contrairement aux méthodes FFT qui souffrent d'instabilités numériques (erreurs d'arrondi, valeurs négatives pour $\varepsilon$ ) lorsque $m$ est très grand, l'approche analytique du Edgeworth Accountant reste stable et précise même pour des millions de compositions.
Généralité :
- La méthode s'applique à n'importe quel mécanisme d'ajout de bruit (gaussien, Laplace, etc.) tant que les moments d'ordre 4 sont bornés.

4. Résultats Expérimentaux

Les auteurs comparent leur méthode (AEA et EEAI) avec le Compteur des Moments (MA/RDP), l'approximation GDP (CLT) et la méthode FFT sur des scénarios réalistes (NoisySGD, Analyse Fédérée).

Précision : L'AEA surpasse nettement les méthodes RDP et GDP, fournissant des estimations très proches de la vérité terrain (approximée par FFT pour de petits $m$ ).
Échelle : Pour des nombres de compositions très élevés ( $m > 10^5$ ), la méthode FFT devient instable ou imprécise, tandis que l'EEAI maintient des bornes fiables et stables.
Efficacité : Le temps de calcul du Edgeworth Accountant reste constant ou linéaire, permettant une estimation rapide des paramètres de privacy pour de nombreux hyperparamètres lors de l'entraînement de modèles.

5. Signification et Impact

Le Edgeworth Accountant représente une avancée significative dans le domaine de la comptabilité de la privacy (Privacy Accounting) :

Pour la recherche et la pratique : Il comble le fossé entre les méthodes rapides mais imprécises (RDP/GDP) et les méthodes précises mais lentes (FFT). Il permet aux praticiens d'obtenir des garanties de privacy rigoureuses et serrées pour des modèles d'apprentissage profond à grande échelle sans coût computationnel prohibitif.
Apport théorique : L'établissement de bornes d'erreur non asymptotiques pour l'expansion d'Edgeworth dans le contexte de la DP est une contribution mathématique indépendante qui ouvre la voie à de meilleures analyses de convergence pour d'autres problèmes statistiques.
Applicabilité : La méthode est particulièrement adaptée aux environnements d'apprentissage fédéré et au Deep Learning privé, où le nombre d'itérations est massif et où une estimation précise de la privacy est cruciale pour la conformité réglementaire.

En résumé, cette méthode offre un outil robuste, rapide et précis pour le suivi de la privacy, permettant de mieux équilibrer l'utilité des données et la protection de la vie privée dans les systèmes modernes d'IA.