Résumé technique : Filtres de f-privacité différentielle : Validité et solutions approchées

Énoncé du problème

L'article aborde le défi de la prise en compte de la perte de confidentialité dans le cadre d'une composition entièrement adaptative en privacité différentielle (DP). Dans des contextes entièrement adaptatifs, le choix des mécanismes et de leurs paramètres de confidentialité peut dépendre de l'historique des sorties précédentes, un scénario courant dans les algorithmes itératifs tels que la descente de gradient stochastique privée (DP-SGD).

Bien que des filtres de confidentialité (règles d'arrêt) existent pour la $(\epsilon, \delta)$-DP et la DP de Rényi (RDP), la validité des filtres basés sur la f-privacité différentielle (f-DP) reste incertaine. La f-DP caractérise l'étendue complète des tests d'hypothèses adverses via des fonctions de compromis et retrouve la $(\epsilon, \delta)$-DP par l'intermédiaire de fonctions de compromis linéaires par morceaux. Il est établi que les produits tensoriels de f-DP fournissent les résultats de composition les plus serrés pour des contextes non adaptatifs. La question centrale est de savoir si un filtre f-DP « naturel » — qui suit le produit tensoriel cumulatif des fonctions de compromis et s'arrête lorsqu'une courbe prescrite est franchie — reste valide sous une adaptativité totale.

Méthodologie et cadre théorique

1. Analyse de la validité du filtre f-DP naturel

Les auteurs examinent le filtre f-DP « naturel », défini comme la poursuite de l'exécution tant que le produit tensoriel des fonctions de compromis réalisées $f_1 \otimes \dots \otimes f_t$ reste au-dessus d'une courbe de budget $f_B$.

• Construction d'un contre-exemple : L'article démontre que cette approche est fondamentalement invalide dans le cadre entièrement adaptatif. Même si les mécanismes individuels sont valides et que la fonction de compromis composée ne dépasse jamais le seuil le long d'un historique spécifique, la composition adaptative peut violer le budget.
• Mécanisme de l'échec : L'échec survient parce que le produit adaptatif des fonctions de compromis dépend de la réalisation spécifique des sorties, laquelle détermine la sélection des mécanismes subséquents. Si une famille de fonctions de compromis futures potentielles contient un « point d'étalonnage » (où les fonctions se croisent), la sélection adaptative peut exploiter cela pour obtenir un profil de perte de confidentialité strictement pire (fonction de compromis plus basse) que la borne inférieure du produit tensoriel des branches individuelles. Ce phénomène se produit même pour les mécanismes gaussiens sous-échantillonnés, le cheval de bataille de l'apprentissage automatique privé.

2. Caractérisation des conditions de validité

Les auteurs établissent des conditions nécessaires et suffisantes pour que le filtre f-DP naturel soit valide :

• Chaînes de Blackwell : Le filtre est valide si et seulement si la famille des fonctions de compromis disponibles (et leurs produits tensoriels) forme une chaîne de Blackwell. Une famille est une chaîne de Blackwell si deux fonctions quelconques de la famille sont totalement ordonnées (l'une domine l'autre point par point).
• Implication : Cela explique pourquoi la RDP et la DP gaussienne (GDP) admettent des filtres simples et valides : leurs garanties sont à valeurs scalaires (ou forment des chaînes de Blackwell comme les fonctions de compromis gaussiennes $G_\mu$ où $\mu$ est un scalaire), assurant la comparabilité. En revanche, les fonctions de compromis f-DP générales ne sont pas toujours ordonnées selon Blackwell, ce qui conduit à l'échec du filtre naturel.

3. Théorème central limite (TCL) entièrement adaptatif

Pour contourner l'invalidité des filtres f-DP exacts, l'article démontre un théorème central limite f-DP entièrement adaptatif.

• Approche : Les auteurs modélisent la perte de confidentialité comme un processus stochastique de variables aléatoires de perte de confidentialité (PLRV). En utilisant une variante de martingale de la borne de Berry–Esseen (Fan, 2019), ils démontrent que, sous des conditions de régularité spécifiques (moyennes et variances conditionnelles bornées, et moments d'ordre supérieur contrôlés), la perte de confidentialité cumulative converge vers une distribution gaussienne.
• Résultat : Cette convergence permet la construction de filtres GDP approximatifs. Au lieu de suivre la fonction de compromis complète, on peut suivre les moyennes et variances conditionnelles cumulatives des PLRV. L'erreur de cette approximation est quantifiée par le terme d'erreur du TCL, $\Delta$.

4. Filtre GDP approximatif pour les mécanismes gaussiens sous-échantillonnés

Comme instantiation concrète, les auteurs dérivent des approximations de moments sous forme close pour les mécanismes gaussiens sous-échantillonnés dans deux régimes asymptotiques :

• Faible sous-échantillonnage ($q \ll 1$) : La moyenne et la variance de la PLRV sont approximées à l'aide de développements de Taylor.
• Forte sous-échantillonnage ($q \approx 1$) : Des approximations similaires sont dérivées pour la limite où le taux d'échantillonnage approche 1.
• Algorithme : Ils proposent un algorithme qui suit ces approximations de moments pour imposer un budget. Ce filtre évite de suivre la fonction de compromis complète, offrant une alternative computationnellement efficace à la comptabilité numérique basée sur la transformée de Fourier rapide (FFT).

Résultats clés

1. Invalidité des filtres naturels : Le filtre f-DP naturel est invalide pour les compositions entièrement adaptatives de mécanismes gaussiens sous-échantillonnés. Des contre-exemples explicites montrent que la composition adaptative peut violer le budget même lorsque toutes les branches non adaptatives le satisfont.
2. Caractérisation de la validité : Le filtre naturel est valide si et seulement si la famille des fonctions de compromis forme une chaîne de Blackwell. Cela fournit une frontière théorique précise pour déterminer quand la comptabilité basée sur les fonctions de compromis est possible sous une adaptativité totale.
3. Approximation basée sur le TCL : Le TCL entièrement adaptatif établit que les pertes de confidentialité cumulatives convergent vers des distributions gaussiennes. Cela permet la construction de filtres GDP approximatifs qui sont prouvés valides dans des régimes asymptotiques.
4. Comparaison des performances :
   • Dans les régimes asymptotiques ($q \ll 1$ et $q \approx 1$), le filtre GDP approximatif proposé fournit des garanties de confidentialité strictement plus serrées que la comptabilité RDP entièrement adaptative (spécifiquement le filtre RDP d'ordre unique $(1, B)$).
   • L'article note que bien que la comptabilité basée sur la RDP soit connue pour être lâche, cette marge est montrée comme découlant de la réduction perteuse vers les divergences de Rényi plutôt que d'une barrière fondamentale dans la composition adaptative.
   • Cependant, l'approximation basée sur le TCL est connue pour être optimiste (sous-estimant la perte de confidentialité) à des taux de sous-échantillonnage réalistes et modérés (par exemple $q=0,1$), une limitation partagée avec les approximations TCL non adaptatives.

Importance et affirmations

L'article prétend résoudre une question ouverte centrale concernant les filtres f-DP :

• Résolution théorique : Il montre de manière définitive que l'extension intuitive de la composition f-DP standard aux filtres adaptatifs échoue, clarifiant pourquoi les notions basées sur les divergences (RDP) réussissent là où les notions basées sur les fonctions de compromis (f-DP générale) échouent sans contraintes structurelles.
• Contribution constructive : En démontrant le TCL entièrement adaptatif, l'article fournit une méthodologie générale pour construire des filtres GDP approximatifs pour toute famille de mécanismes où les moments des PLRV peuvent être approximés analytiquement.
• Implication pratique : Pour les mécanismes gaussiens sous-échantillonnés, le filtre proposé offre une alternative sous forme close et efficace à la comptabilité numérique. Dans les régimes de sous-échantillonnage extrêmes, il fournit des garanties strictement plus serrées que les filtres basés sur la RDP les plus avancés actuels, démontrant que la « marge » de la RDP est un artefact de la représentation et non un coût inhérent à l'adaptativité.

Les auteurs restent modestes concernant les limites, reconnaissant que l'approche basée sur le TCL est optimiste à des taux de sous-échantillonnage réalistes et que la réduction de l'écart à des taux modérés reste un défi ouvert. Ils notent également que la validité du filtre naturel est restreinte à des conditions structurelles spécifiques (chaînes de Blackwell) qui ne sont généralement pas remplies par des mécanismes f-DP arbitraires.