Résumé technique : Rates optimales pour les tests d'hypothèses à confidentialité différentielle avec des valeurs-e

Énoncé du problème

Ce travail aborde le problème fondamental du test d'hypothèse simple sous les contraintes de la confidentialité différentielle (CD) centrale. Plus précisément, les auteurs étudient le test d'un jeu de données $X \sim P^n$ (hypothèse nulle) contre $X \sim Q^n$ (hypothèse alternative) en utilisant des valeurs-e.

Dans le cadre classique, la performance d'un test est mesurée par sa puissance (taux de vrais positifs). Dans le cadre des valeurs-e, la performance est mesurée par la puissance-e, définie comme $\mathbb{E}_Q[\log E]$, où $E$ est une variable aléatoire non négative satisfaisant $\mathbb{E}_P[E] \le 1$. La question centrale est : Quelle est la puissance-e maximale réalisable pour une valeur-e $\varepsilon$-CD lors du test de $P$ contre $Q$ ?

Les auteurs considèrent deux cadres :

1. Cadre par lots (Batch) : Tous les $n$ points de données sont disponibles simultanément.
2. Cadre séquentiel : Les données arrivent une par une, et l'analyste choisit un temps d'arrêt $N$ de manière adaptative. L'objectif est de minimiser le temps d'arrêt attendu $\mathbb{E}_Q[N]$ requis pour atteindre un niveau spécifique de preuve statistique.

Bien que des travaux antérieurs existent sur les tests d'hypothèses à confidentialité différentielle dans le cadre décisionnel (sorties binaires) et sur les valeurs-e sous CD locale, cet article se concentre sur les valeurs-e à CD centrale, un cadre où peu de travaux antérieurs existent (spécifiquement Csillag et Mesquita [10], qui était restreint aux rapports de vraisemblance bornés).

Méthodologie

1. Caractérisation de la puissance-e optimale (Cadre par lots)

Les auteurs découplent le mécanisme de confidentialité de la construction de la variable-e. Ils observent que pour tout mécanisme $\varepsilon$-CD fixe $M$, le post-traitement optimal pour créer une variable-e est le rapport de vraisemblance des distributions de sortie, $dM(Q^n)/dM(P^n)$. Ainsi, le problème se réduit à maximiser la divergence de Kullback-Leibler (KL) entre les distributions de sortie du mécanisme :
$$R_{\varepsilon}(Q \| P) = \lim_{n \to \infty} \sup_{M \in \varepsilon\text{-CD}} \frac{1}{n} KL(M(Q^n) \| M(P^n))$$

Pour résoudre cela, les auteurs introduisent une distribution intermédiaire $\tilde{Q}$. Ils construisent $\tilde{Q}$ en modifiant la densité de $Q$ par rapport à $P$ dans des régions spécifiques définies par le rapport de vraisemblance $q(x)/p(x)$ :

• Région A (Faible rapport de vraisemblance) : $q(x) < c_1 p(x)$. Ici, $\tilde{q}(x) = c_1 p(x)$.
• Région B (Fort rapport de vraisemblance) : $q(x) > c_2 p(x)$. Ici, $\tilde{q}(x) = c_2 p(x)$.
• Région M (Intermédiaire) : $\tilde{q}(x) = q(x)$.

Les constantes $c_1, c_2$ et les régions sont déterminées par un multiplicateur de Lagrange $\lambda^*$ qui résout une équation implicite assurant que $\tilde{Q}$ est une distribution de probabilité valide. Cette construction minimise le fonctionnel $KL(Q' \| P) + \varepsilon \cdot TV(Q', Q)$.

Les auteurs prouvent que le taux optimal est exactement :
$$R_{\varepsilon}(Q \| P) = KL(\tilde{Q} \| P) + \varepsilon \cdot TV(\tilde{Q}, Q)$$

Ils construisent ensuite une variable-e non privée $E^*$ basée sur ce $\tilde{Q}$ (spécifiquement, un rapport de vraisemblance tronqué) qui possède une sensibilité logarithmique bornée $\varepsilon$. Pour la privatiser, ils proposent une fonction de fusion $\Lambda_n$ basée sur les travaux de Vovk et Wang, ajoutant un bruit de Laplace avec un compensateur soigneusement calibré pour maintenir la propriété de variable-e tout en préservant l'optimalité asymptotique.

2. Cadre séquentiel et temps d'arrêt

Dans le cadre séquentiel, les auteurs définissent un processus-e $\varepsilon$-CD comme une séquence de valeurs-e générées par un mécanisme $\varepsilon$-CD. Ils établissent une borne inférieure sur le temps d'attendu pour tout processus de ce type.

En utilisant un argument de fonction de potentiel impliquant un couplage entre la distribution vraie $Q$ et la distribution intermédiaire $\tilde{Q}$, ils prouvent que pour tout temps d'arrêt $N$ :
$$\mathbb{E}_Q[\log E_N] \le \mathbb{E}_Q[N] \cdot R_{\varepsilon}(Q \| P)$$
Cela implique une borne inférieure sur la complexité en échantillons requise pour atteindre une certaine puissance.

Pour atteindre cette borne, ils proposent l'Algorithme 1, une « Conversion de lot en processus-e ». Cet algorithme :

• Prend une variable-e non privée avec une sensibilité logarithmique bornée.
• Traite les données par lots de taille croissante.
• Applique une fonction de fusion privatisée (similaire au cas par lots) à la fin de chaque lot.
• Utilise une relation de récurrence spécifique pour déterminer les tailles de lots, optimisant le compromis entre le temps de « démarrage » initial et le ratio compétitif à long terme.

Contributions et résultats clés

1. Résultat de difficulté spécifique à l'instance (Théorème 2.2) : L'article fournit une formule explicite et calculable pour la puissance-e maximale réalisable sous CD $\varepsilon$. Ce taux est caractérisé par la divergence KL vers une distribution intermédiaire $\tilde{Q}$ plus une pénalité de variation totale.
2. Construction d'algorithme optimal (Théorème 2.4) : Les auteurs construisent une variable-e $\varepsilon$-CD qui atteint ce taux optimal asymptotiquement. La construction implique un tronquage spécifique du rapport de vraisemblance suivi d'un schéma de privatisation utilisant un bruit de Laplace et un terme compensateur.
3. Borne inférieure séquentielle (Théorème 3.1) : Ils dérivent une borne inférieure universelle sur le temps d'arrêt attendu de tout processus-e $\varepsilon$-CD, montrant qu'elle est inversement proportionnelle au taux de puissance-e optimal $R_{\varepsilon}(Q \| P)$.
4. Algorithme séquentiel optimal (Théorème 3.2) : Ils présentent l'Algorithme 1, qui convertit une variable-e non privée en un processus-e $\varepsilon$-CD. Cet algorithme correspond à la borne inférieure théorique sur les temps d'arrêt jusqu'à un facteur multiplicatif constant (ratio compétitif) pour tous les temps d'arrêt suffisamment grands.
5. Alternative indépendante de la distribution (Annexe C) : Reconnaissant que le calcul de l'optimal $\tilde{Q}$ peut être intraitable pour des distributions complexes, ils proposent une statistique de « rapport de vraisemblance tronqué et mis à l'échelle » (tsLR). Cette statistique indépendante de la distribution atteint un taux dans un facteur constant du taux optimal.

Validation expérimentale

Les auteurs ont mené des expériences numériques comparant leur Algorithme 1 au DP-SPRT (Test de rapport de vraisemblance séquentiel à confidentialité différentielle) proposé par Michel et al. [25].

• Configuration : Test de $P = \text{Bernoulli}(0.3)$ contre $Q = \text{Bernoulli}(q)$.
• Métrique : Fonctions de distribution cumulative (CDF) empiriques des temps d'arrêt.
• Résultat : À travers divers niveaux de confidentialité ($\varepsilon$) et distributions alternatives ($q$), le processus-e privé proposé s'est arrêté systématiquement plus tôt que le DP-SPRT. Notamment, ce gain de performance a été obtenu bien que l'algorithme proposé ne fasse aucune hypothèse paramétrique sur les données, tandis que le DP-SPRT est conçu spécifiquement pour les familles exponentielles.

Importance et affirmations

L'article affirme fournir une compréhension complète des limites fondamentales des tests d'hypothèses simples utilisant des valeurs-e sous confidentialité différentielle centrale.

• Fondement théorique : En caractérisant le taux optimal $R_{\varepsilon}(Q \| P)$ et en fournissant un algorithme qui le correspond, le travail établit une base de référence pour ce qui est réalisable dans l'analyse séquentielle préservant la confidentialité.
• Utilité pratique : Les algorithmes proposés nécessitent moins de données (moins de temps d'arrêt) que les méthodes de l'état de l'art existantes (DP-SPRT) dans une gamme de configurations.
• Perspectives futures : Les auteurs suggèrent que leurs résultats de difficulté et leurs techniques (spécifiquement l'utilisation de paires les plus défavorables) peuvent servir de fondation pour étendre ces résultats aux tests d'hypothèses composites et à l'estimation DP optimale pour l'instance, de la même manière que les travaux fondamentaux dans les cadres non privés ont stimulé les progrès dans ces domaines. Ils notent également que l'extension de ces résultats à la CD approximative ($\delta > 0$) reste une question ouverte.