Résumé Technique : Limites de la Personnalisation des Budgets de Confidentialité Différentielle

Énoncé du Problème

En Confidentialité Différentielle (CD), le choix d'un budget de confidentialité ($\epsilon$) approprié constitue un défi fondamental : un $\epsilon$ plus faible garantit une confidentialité plus forte mais dégrade l'utilité (précision) du calcul. Alors que la CD classique impose un budget uniforme à tous les participants, une extension naturelle est la CD personnalisée (ou hétérogène), où chaque agent $i$ possède une exigence de confidentialité distincte $\epsilon_i$. Cette approche est motivée par le fait que les agents ont des attitudes face à la confidentialité variables et que la personnalisation élargit théoriquement l'espace des algorithmes réalisables, améliorant potentiellement le compromis confidentialité-précision.

Cependant, les mécanismes entièrement personnalisés (par exemple, les estimateurs affines qui réattribuent des poids aux points de données en fonction des $\epsilon_i$ individuels) sont complexes à auditer, à communiquer et à adapter. Une alternative plus simple est un estimateur par seuillage, qui écarte les points de données ayant des exigences de confidentialité trop strictes et applique un budget de confidentialité unique, soigneusement choisi, aux données restantes.

La question centrale abordée dans cet article est : la complexité de la personnalisation complète produit-elle des gains significatifs en utilité (spécifiquement pour l'estimation de la moyenne) par rapport à la base de référence par seuillage plus simple ? Les auteurs examinent si la « valeur marginale » de la personnalisation complète est substantielle ou si les gains sont modestes dans la plupart des régimes pratiques.

Méthodologie et Modèle

Les auteurs se concentrent sur le problème de l'estimation de la moyenne pour une distribution $P$ à support borné $[-1/2, 1/2]$, étant donné $n$ points de données i.i.d. où chaque point $x_i$ possède un budget de confidentialité spécifique $\epsilon_i$.

Estimateurs Comparés

1. Estimateur Affine Optimal (Entièrement Personnalisé) :

   • Il s'agit de l'estimateur le plus connu pour la CD hétérogène. Il utilise une moyenne pondérée des points de données : $\hat{\mu} = \sum w_i x_i + Z$, où $Z$ est un bruit de Laplace.
   • Les poids $w_i$ sont optimisés pour minimiser l'Erreur Quadratique Moyenne (EQM).
   • La stratégie optimale implique un « écrêtage » des niveaux de confidentialité : un seuil $\tau$ est sélectionné, et les niveaux de confidentialité effectifs sont fixés à $\bar{\epsilon}_i = \min(\epsilon_i, \tau)$. Les poids sont proportionnels à ces niveaux écrêtés ($w_i \propto \bar{\epsilon}_i$), et l'échelle du bruit est déterminée par la sensibilité maximale par rapport aux budgets écrêtés.
   • L'EQM est caractérisée par :
     $$\text{EQM}_{\text{aff}}(\epsilon) = \inf_{\tau>0} \left( \frac{q_\tau}{4s_\tau^2} + \frac{2}{s_\tau^2} \right)$$
     où $s_\tau = \sum \min(\epsilon_i, \tau)$ et $q_\tau = \sum \min(\epsilon_i, \tau)^2$.

2. Estimateur à Seuil Unique $\epsilon$ (Base de Référence Simplifiée) :

   • Cet estimateur sélectionne un seuil global unique $\epsilon$.
   • Il écarte tous les points de données pour lesquels l'exigence individuelle $\epsilon_i < \epsilon$.
   • Il applique un budget de confidentialité uniforme $\epsilon$ aux $n_\epsilon$ points de données restants.
   • L'EQM est minimisée par rapport au choix de $\epsilon$ :
     $$\text{EQM}_{\text{thr}}(\epsilon) = \inf_{\epsilon>0} \left( \frac{1}{4n_\epsilon} + \frac{2}{\epsilon^2 n_\epsilon^2} \right)$$

Métrique

La performance est mesurée par l'Erreur Quadratique Moyenne Robuste aux Distributions (pire cas d'EQM sur les distributions à support borné). Les auteurs analysent le rapport d'approximation $\frac{\text{EQM}_{\text{thr}}}{\text{EQM}_{\text{aff}}}$ pour quantifier la perte d'utilité lors de l'utilisation de l'approche par seuillage simple plutôt que du mécanisme affine optimal.

Contributions et Résultats Clés

L'article fournit des bornes précises sur l'écart de performance entre l'estimateur par seuillage et l'estimateur affine optimal à travers trois régimes distincts :

1. Combinaison de Données Publiques et Privées

• Contexte : Un mélange de $n_1$ points de données privés (budget $\epsilon_1$) et de $n_2$ points de données publics (effectivement $\epsilon_2 = \infty$).
• Résultat : L'estimateur par seuillage atteint une approximation de 2 par rapport à l'estimateur affine optimal.
• Perspective : L'écart est serré et approche 2 uniquement dans une région étroite où les contributions de variance des parties privée et publique sont équilibrées. Dans la plupart des autres configurations, le rapport est proche de 1, indiquant un gain négligeable de la personnalisation.

2. Deux Niveaux de Confidentialité Finis

• Contexte : Les points de données possèdent l'un des deux budgets de confidentialité finis, $\epsilon_1 < \epsilon_2$.
• Résultat : Le rapport d'approximation se dégrade de 2 à 4.
• Perspective : Les auteurs fournissent un contre-exemple montrant que le rapport peut dépasser 2. Cependant, ils prouvent que le rapport est borné par 4, indépendamment des valeurs spécifiques de $\epsilon_1, \epsilon_2$ ou des comptes de données. Cela implique que même dans ce contexte légèrement plus complexe, l'approche par seuillage capture la grande majorité de l'utilité.

3. Nombre Arbitraire de Niveaux de Confidentialité ($m$ niveaux)

• Contexte : Les points de données possèdent $m$ niveaux de confidentialité distincts ($0 < \epsilon_1 < \dots < \epsilon_m$).
• Résultat : Aucune approximation à facteur constant n'est possible en général.
  • Borne Inférieure : Les auteurs construisent un cas spécifique où le rapport croît quadratiquement avec le nombre de niveaux : $\Omega(m^2)$. Plus précisément, si $m \approx \log_2 n$, le rapport est $\Omega((\log_2 n)^2)$.
  • Borne Supérieure : Ils prouvent que pour tout cas, le rapport est borné par $\min((1 + \log_2 n)^2, m^2)$.
• Perspective : Bien que l'écart puisse théoriquement croître avec le nombre de niveaux de confidentialité, cette croissance est limitée (quadratique en $m$ ou logarithmique en $n$). Les scénarios « pire cas » nécessitent des distributions spécifiques, quelque peu artificielles, de niveaux de confidentialité et de comptes de données.

Importance et Affirmations

L'article soutient que le facteur dominant pour atteindre une utilité élevée en CD hétérogène est le choix du bon budget de confidentialité effectif plutôt que la mise en œuvre d'une personnalisation complète.

• Gains Modestes : Dans les scénarios les plus courants et pratiques (combinaison de données publiques/privées ou gestion de deux niveaux de confidentialité), les gains des estimateurs affines entièrement personnalisés sont limités à des facteurs constants (au maximum 4x).
• Praticité du Seuillage : L'estimateur par seuillage offre des avantages pratiques significatifs : il est plus facile à auditer, permet une communication plus claire des garanties de confidentialité et s'adapte plus simplement aux changements de la base d'utilisateurs. Il offre également une confidentialité « gratuite » aux agents qui sont plus généreux avec leurs données.
• Limites Théoriques : Bien que l'article établisse que l'écart peut croître avec le nombre de niveaux de confidentialité ($m$), les auteurs notent que les estimateurs personnalisés optimaux ne sont même pas connus pour $m > 2$ dans le cas général. Ainsi, l'approche par seuillage reste une heuristique robuste, quasi-optimale pour l'estimation de la moyenne.

Les auteurs concluent que pour l'estimation de la moyenne, la complexité de la personnalisation complète n'est souvent pas justifiée par les gains marginaux d'utilité, suggérant que des stratégies de seuillage plus simples suffisent pour la plupart des régimes d'intérêt. Ils émettent l'hypothèse que des enseignements similaires pourraient s'appliquer à des tâches d'apprentissage plus larges, bien que cela reste un domaine ouvert pour la recherche future.