Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

Résumé technique : Coefficients de Dobrushin des mécanismes privés au-delà de la confidentialité différentielle locale

Énoncé du problème
L'article traite des limites de l'utilisation de la confidentialité différentielle locale (LDP) comme unique métrique pour quantifier la confidentialité des noyaux de Markov discrets (mécanismes de confidentialité). Bien que la LDP soit largement adoptée, les auteurs notent deux problèmes principaux :

1. Sur-restrictivité : Dans les applications statistiques telles que l'estimation de paramètres, l'obtention de garanties LDP strictes (petit $\epsilon$) peut entraîner une dégradation extrême des performances d'estimation (risque minimax élevé).
2. Comportement contre-intuitif avec les probabilités nulles : La définition standard de la LDP produit un coût de confidentialité infini si un mécanisme assigne une probabilité nulle à un résultat pour une entrée donnée ($K_{Y|X=x}(y) = 0$). Cela traite les mécanismes avec une randomisation significative (par exemple, $K_1$ dans l'exemple de l'article) de la même manière que les applications identités ou les mécanismes triviaux (par exemple, $K_2$) si tous deux contiennent des entrées nulles, échouant ainsi à distinguer les comportements « bruités » des comportements « déterministes » en termes de fuite de confidentialité.

Pour remédier à ces problèmes, les auteurs étudient les coefficients de Dobrushin (coefficients de contraction de la distance de variation totale) pour des mécanismes qui satisfont une Fuite Maximale Ponctuelle (PML) plutôt qu'une LDP stricte. La PML est une adaptation ponctuelle de la fuite maximale qui dépend de la distribution des données $P_X$. Les auteurs analysent spécifiquement les mécanismes où la distribution d'entrée $P_X$ possède une masse de probabilité minimale bornée au-dessus de zéro par une constante $c > 0$ (c'est-à-dire $\min_x P_X(x) \geq c$). Ce cadre permet l'analyse de mécanismes avec des assignations de probabilité nulle qui seraient autrement considérés comme ayant une confidentialité infinie (ou une fuite infinie) sous la LDP.

Méthodologie
L'article emploie des outils de la théorie de l'information pour dériver des bornes sur la contraction des $f$-divergences à travers les mécanismes de confidentialité.

• Définitions : Les auteurs définissent la $(\epsilon, c)$-PML comme une contrainte où la PML est bornée par $\epsilon$ pour toutes les distributions d'entrée dans l'ensemble $Q_X(c) = \{P_X : \min_x P_X(x) \geq c\}$. Cela généralise la LDP, car la LDP correspond à la limite $c \to 0$.
• Coefficients de contraction : L'objet central d'étude est le coefficient de Dobrushin $\eta_{TV}(\epsilon, c)$, défini comme la suprême de la contraction de la distance de variation totale (TV) sur tous les noyaux satisfaisant la $(\epsilon, c)$-PML.
• Réduction aux sorties binaires : Les auteurs prouvent que pour trouver le coefficient de Dobrushin maximal, il est suffisant de considérer des mécanismes avec des espaces de sortie binaires ($|Y|=2$). Cela simplifie considérablement le problème d'optimisation.
• Inégalités : La dérivation utilise l'inégalité de Binette (une généralisation de l'inégalité de Pinsker inversée) pour étendre les bornes de TV aux $f$-divergences générales (telles que l'entropie relative et la divergence de Hellinger).

Contributions clés et résultats

1. Bornes atteignables sur les coefficients de Dobrushin :
   L'article dérive une borne supérieure serrée sur le coefficient de Dobrushin $\eta_{TV}(\epsilon, c)$ pour tout noyau satisfaisant la $(\epsilon, c)$-PML. La borne est donnée par :
   $$\eta_{TV}(\epsilon, c) \leq \min\left( \frac{e^\epsilon - 1}{e^\epsilon(1 - Nc) + 1}, 1 \right)$$
   où $N$ est la taille de l'alphabet d'entrée.

• Analyse de régime : Les auteurs montrent que si $\epsilon \geq \log(2/Nc)$, le coefficient de contraction est 1 (aucune contraction ne se produit). Si $\epsilon < \log(2/Nc)$, le coefficient est strictement inférieur à 1, indiquant une contraction induite par la confidentialité.
• Récupération de la LDP : Lorsque $c \to 0$, la borne récupère le résultat connu pour la $\epsilon$-LDP : $\eta_{TV} \leq \frac{e^\epsilon - 1}{e^\epsilon + 1}$.
• Construction de mécanismes : L'article fournit des constructions explicites de mécanismes (spécifiquement des mécanismes à sortie binaire) qui atteignent ces bornes, démontrant que les bornes sont atteignables.

2. Extension aux $f$-divergences générales :
   En utilisant l'inégalité de Binette, les auteurs étendent les bornes de TV aux $f$-divergences générales. Ils dérivent des inégalités de traitement de données fortes (SDPI) pour l'entropie relative et la divergence de Hellinger sous les contraintes $(\epsilon, c)$-PML. Ces bornes dépendent du facteur de contraction de la TV et des ratios extrémaux des distributions de sortie.

3. Application au risque minimax :
   Les bornes dérivées sont appliquées à l'estimation minimax privée. En utilisant la méthode de Le Cam à deux points et la propriété de tensorisation des $f$-divergences, les auteurs montrent que la complexité d'échantillonnage requise pour atteindre un certain niveau de risque augmente par un facteur proportionnel à l'inverse du coefficient de Dobrushin privé. Plus précisément, si le coefficient est 1, la complexité d'échantillonnage correspond au cadre non privé ; si il est inférieur à 1, la taille d'échantillon effective est réduite.

Signification et revendications
L'article affirme fournir un cadre plus nuancé pour analyser les mécanismes de confidentialité que la LDP seule. En introduisant le paramètre $c$, les auteurs peuvent quantifier la fuite de confidentialité pour des mécanismes qui contiennent des entrées de probabilité nulle, qui sont exclus ou traités de manière pathologique sous la LDP standard.

• Bornes plus serrées : Pour les mécanismes satisfaisant la LDP, les bornes proposées sont plus serrées ou plus adaptables que les résultats précédents lorsque la distribution d'entrée possède une masse minimale $c$ connue.
• Au-delà de la LDP : Le cadre étend l'analyse des coefficients de contraction à toute la classe des noyaux discrets, y compris ceux qui ne satisfont aucune garantie LDP finie.
• Interprétation opérationnelle : Les résultats lient les coefficients de contraction théoriques directement à la dégradation des performances d'estimation statistique, offrant un outil pour quantifier le « coût » de la confidentialité en termes de risque accru ou de complexité d'échantillonnage.

Les auteurs soulignent que leur travail récupère les résultats existants de la LDP comme un cas particulier tout en offrant une interpolation continue entre les contraintes de distribution uniforme et le régime complet de la LDP, répondant ainsi à la nature « sur-restrictive » de la LDP dans des contextes statistiques spécifiques.