Résumé technique : Le spectre d'indiscernabilité des distributions normales et son application à l'apprentissage automatique préservant la vie privée

1. Énoncé du problème

La confidentialité différentielle (CD) est la définition standard pour protéger les données sensibles, exigeant que la sortie d'un algorithme randomisé reste indiscernable lorsqu'un enregistrement unique est ajouté ou supprimé de la base de données d'entrée. Bien que le « mécanisme gaussien » (ajout de bruit gaussien à une requête déterministe) soit un outil fondamental de CD, de nombreux algorithmes modernes d'apprentissage automatique et statistiques produisent naturellement des sorties gaussiennes multivariées où à la fois la moyenne et la matrice de covariance dépendent de l'ensemble de données d'entrée.

Les analyses de confidentialité existantes pour de tels algorithmes reposent souvent sur des bornes supérieures lâches, des divergences indirectes ou des arguments de sensibilité dans le pire des cas. Ces approches échouent à capturer la perte de confidentialité précise lorsque des ensembles de données voisins induisent des sorties gaussiennes avec des matrices de covariance différentes. Cette lacune conduit à deux questions de recherche fondamentales :

1. Existe-t-il une méthode générale et exacte pour décrire l'indiscernabilité (IS) entre deux distributions gaussiennes multivariées arbitraires ?
2. Une caractérisation serrée de cette IS peut-elle être utilisée pour concevoir de nouveaux mécanismes CD plus efficaces pour les algorithmes à sorties gaussiennes ?

2. Méthodologie : Le lemme NDIS et la boîte à outils

Les auteurs introduisent le spectre d'indiscernabilité des distributions normales (NDIS), un lemme analytique sous forme fermée qui caractérise exactement la divergence en forme de hockey $\delta_{X,Y}(\epsilon)$ entre deux gaussiennes multivariées quelconques $X \sim \mathcal{N}(\mu_1, \Sigma_1)$ et $Y \sim \mathcal{N}(\mu_2, \Sigma_2)$.

Le lemme NDIS

Le lemme exprime l'indiscernabilité comme l'espérance d'une fonction charnière appliquée à un polynôme quadratique d'une variable aléatoire normale standard $Z \sim \mathcal{N}(0, I_d)$ :
$$\delta_{X,Y}(\epsilon) = \mathbb{E}\left[ \left( 1 - \exp(g_\epsilon(Z)) \right)_+ \right]$$
où $g_\epsilon(Z)$ est une forme quadratique déterminée par les moyennes et les covariances de $X$ et $Y$. Plus précisément, $g_\epsilon(Z)$ implique les valeurs propres de la matrice $M = \Sigma_1^{1/2}\Sigma_2^{-1}\Sigma_1^{1/2}$ et un terme linéaire dérivé de la différence de moyennes.

La boîte à outils NDIS

Pour rendre le lemme NDIS pratique, les auteurs développent une « boîte à outils » de résultats :

1. Lien avec les distributions $\chi^2$ généralisées : Les auteurs prouvent que le calcul de $\delta_{X,Y}(\epsilon)$ se réduit à l'évaluation des fonctions de répartition (CDF) de deux variables aléatoires $\chi^2$ généralisées. Cela permet un calcul numérique efficace en utilisant des algorithmes établis (par exemple, des méthodes de type Imhof ou de type Davies).
2. Simplifications analytiques :
   • Décalage de moyenne (Covariance égale) : Retrouve le profil de confidentialité sous forme fermée bien connu du mécanisme gaussien standard.
   • Décalage de covariance (Moyenne égale) : Fournit des bornes supérieures analytiques pour les cas où les covariances diffèrent mais sont comparables dans l'ordre de Loewner (par exemple, $\Sigma_2 \succeq \Sigma_1$). Cela inclut un seuil de « fuite nulle » où la CD pure $\epsilon$ est atteinte.
   • Cas général : Pour des décalages de moyenne et de covariance arbitraires, les auteurs décomposent le problème en une étape de décalage de moyenne et une étape de décalage de covariance, combinant leurs bornes via l'inégalité triangulaire pour la divergence CD.
3. Propriété d'asymétrie : Les auteurs établissent que si $\Sigma_1 \succeq \Sigma_2$, alors $\delta_{X,Y}(\epsilon) \geq \delta_{Y,X}(\epsilon)$. Cela identifie une direction « difficile » pour la perte de confidentialité, simplifiant l'analyse du pire des cas.

3. Contributions et résultats clés

A. Caractérisation serrée de la projection aléatoire (RP)

Les auteurs appliquent la boîte à outils NDIS à la projection aléatoire gaussienne, une technique utilisée pour la réduction de dimensionnalité (par exemple, dans les PCA et les SVM).

• Problème : Les analyses précédentes de la RP-CD reposaient sur la borne de la plus petite valeur singulière (LSV) de la matrice d'entrée, qui est un proxy conservateur pour la confidentialité.
• Résultat : En utilisant NDIS, les auteurs dérivent une caractérisation exacte de la confidentialité basée sur le score de levier ($p(i)$) de l'enregistrement supprimé. Ils prouvent que la perte de confidentialité est une fonction monotone du score de levier.
• Mécanisme ($M_{RP}$) : Ils proposent un mécanisme qui régularise la base de données d'entrée (via une régularisation de ridge) pour garantir que le score de levier maximal reste en dessous d'un seuil $p^*$ dérivé de la cible $(\epsilon, \delta)$.
• Amélioration : Les expériences montrent que l'étalonnage basé sur le levier permet un levier admissible significativement plus grand (et donc moins de régularisation/bruit) par rapport aux méthodes basées sur la LSV, offrant un compromis confidentialité-utilité strictement meilleur.

B. Élévation des algorithmes généraux à sorties gaussiennes

Les auteurs proposent un cadre général pour « élever » n'importe quel algorithme à sorties gaussiennes en un mécanisme CD.

• Définition de la sensibilité : Ils définissent un modèle de sensibilité NDIS comparable dans l'ordre de Loewner, qui borne le décalage de la moyenne et le changement relatif de la covariance (via les valeurs propres) entre des ensembles de données voisins.
• Étalonnage : Étant donné ces bornes de sensibilité, le cadre calcule automatiquement le bruit gaussien isotrope minimal ($\sigma I$) requis pour satisfaire la CD $(\epsilon, \delta)$.
• Applications : Ce cadre est démontré sur la régression logistique bayésienne et la régression par processus gaussiens, fournissant les premières garanties CD serrées pour ces procédures spécifiques à sorties gaussiennes.

C. Outil d'audit en boîte blanche

L'article présente un outil pour l'audit en boîte blanche des mécanismes à sorties gaussiennes.

• Méthode : En exploitant le lien entre NDIS et les CDF $\chi^2$ généralisées, un auditeur peut calculer (ou estimer de manière serrée) le $\delta$ exact pour une paire spécifique d'entrées voisines, en ne disposant que de la moyenne et de la covariance des sorties.
• Signification : Contrairement aux auditeurs en boîte noire qui fournissent des estimations probabilistes, cet outil (en supposant un oracle CDF) fournit une borne inférieure déterministe sur la vraie perte de confidentialité, permettant la détection de violations de confidentialité avec une grande confiance.

4. Importance et affirmations

L'article affirme que NDIS fournit un cadre unifié et exact pour analyser la confidentialité des algorithmes à sorties gaussiennes, dépassant les limitations du mécanisme gaussien standard.

• Impact théorique : Il résout le problème ouvert de la caractérisation des paramètres optimaux $(\epsilon, \delta)$ pour des paires arbitraires de distributions gaussiennes, en particulier celles avec des covariances différentes.
• Impact pratique :
  • Il permet des mécanismes économes en bruit (par exemple, dans la projection aléatoire) en remplaçant les bornes conservatrices du pire des cas par des étalonnages exacts basés sur le levier.
  • Il offre une recette générale pour privatiser des algorithmes statistiques complexes (comme l'inférence bayésienne) sans avoir à redémontrer les preuves de confidentialité à partir de zéro pour chaque nouvel algorithme.
  • Il fournit un outil d'audit rigoureux pour vérifier les affirmations de confidentialité des algorithmes à sorties gaussiennes.

Les auteurs soulignent que leur approche ne repose pas sur des approximations asymptotiques ou des structures algorithmiques spécifiques, mais plutôt sur la géométrie fondamentale des distributions gaussiennes, la rendant applicable à une large classe de tâches d'apprentissage automatique préservant la vie privée.